Chapter 6: Memory Management

Question 1

Physical Memory (RAM)

Answer 1

A hardware structure, consisting of a linear sequence of words that hold a program during execution.

Question 2

Word

Answer 2

A fixed-size unit of data (typically 4 bytes, but can be other sizes)

Question 3

physical address

Answer 3

is an integer in the range [0 : n-1] that identifies a word in a physical memory of size n. The address comprises a fixed number of bits. A memory of size n requires an address size of k bits, where n = 2^k.

Question 4

logical address space

Answer 4

an abstraction of physical memory, consisting of a sequence of imaginary memory locations in a range [0:m-1], where m is the size of the logical address space.

Question 5

logical address

Answer 5

an integer in the range [0:m-1] that identifies a word in a logical address space. Prior to execution, a logical address space is mapped to a portion of physical memory and the program is copied into the corresponding locations.

Question 6

source module

Answer 6

A program or a program component written in a symbolic language, like C, or an assembly language, that must be translated by a compiler into executable machine code.

Question 7

object module

Answer 7

The machine-language output of a compiler or assembler generated from a source module. An object module may be self-contained and executable or multiple object modules may be linked together into a load module by a linker or linkage editor

Question 8

load module

Answer 8

a program or combination of programs in a form ready to be loaded into main memory and executed.

Question 9

Program relocation

Answer 9

the act of moving a program component from one address space to another. The relocation may be between two logical address spaces or from a logical address space to a physical address space.

Question 10

Static relocation

Answer 10

binds all logical addresses to physical addresses prior to execution

Question 11

Dynamic relocation

Answer 11

postpones the binding of a logical address to a physical address until the addressed item is accessed during execution

Question 12

relocation register

Answer 12

contains the physical starting address of a program or program component in memory.

Question 13

First-fit

Answer 13

always starts the search from the beginning of the list and allocates the first hole large enough to accommodate the request

Question 14

Next-fit

Answer 14

starts each search at the point of the last allocation

Question 15

Best-fit

Answer 15

searches the entire list and chooses the smallest hole large enough to accommodate the request

Question 16

worst-fit

Answer 16

takes the opposite approach from best-fit by always choosing the largest available hole for any request

Question 17

external memory fragmentation

Answer 17

the loss of usable memory space due to holes between allocated blocks of variable sizes

Question 18

50% rule

Answer 18

if the probability of finding an exact match for a request approaches 0, one-third of all memory partitions are holes, and two-thirds are occupied by blocks. n = .5m where n is the number of holes and m is the number of occupied blocks.

Question 19

swapping

Answer 19

the temporary removal of a module from memory. The module is saved on disk and later moved back to memory. Dynamic relocation is necessary so that the module can be placed into a different location without modification.

Question 20

memory compaction

Answer 20

the systematic shifting of modules in memory, generally in one direction, to consolidate multiple disjoint holes into one larger hole.

Question 21

linking

Answer 21

The act of resolving external references among object modules and can be done statically, before loading, or dynamically, while the program is already executing.

Question 22

sharing

Answer 22

the act of linking the same copy of a module to multiple other modules. Sharing improves memory utilization by allowing multiple processes to share common routines or services (Ex: compilers, editors, word processors), or common data (Ex: dictionaries). Sharing is possible under both static and dynamic linking.

Question 23

page

Answer 23

A fixed-size contiguous block of logical address space identified by a single number, the page number.

Question 24

page frame

Answer 24

a fixed-size contiguous block of physical memory identified by a single number, the page frame number.

A page frame is the smallest unit of data for memory management and may contain a copy of any page.

Question 25

page table

Answer 25

an array that keeps track of which pages of a given logical address space reside in which page frames. each page table entry corresponds to one page and contains the starting address of the frame containing the page

Question 26

Address Translation Algo

Answer 26

1. Given a logical address (p, w), access the page table entry corresponding to page p.
2. Read the frame number, f, of the frame containing p.
3. Combine f with the offset w to find the physical address (f, w) corresponding to the logical address (p, w).

Question 27

Internal Fragmentation

Answer 27

The loss of usable memory space due to the mismatch between the page size and the size of a program, which creates a hole at the end of the program’s lat page.

Question 28

segment

Answer 28

a variable-size block of logical address space identified by a single number, the segment number.

With pure segmentation (no paging), a segment occupies a contiguous area of physical memory and is the smallest unit of data for memory management.

Question 29

segment table

Answer 29

An array that keeps track of which segment resides in which area of physical memory. Each entry corresponds to one segment and contains the starting address of the segment.

Question 30

address translation (logical -> physical)

Answer 30

1. Given a logical address (s, w), access the segment table entry at offset s and get the segment’s starting address, sa, and size, sze.
2. If w ≥ sze then reject the address as illegal.
3. Otherwise, add w to sa to form the physical address, sa + w, corresponding to the logical address (s, w).
4. Given a logical address (s, p, w), access the segment table at offset s to find the page table and the size, sze, of segment s.
5. If (p, w) ≥ sze then reject the address as illegal. Otherwise, access the page table at offset p and read the frame number, f, of the frame containing page p.
6. Combine f with the offset w to form the physical address, (f, w).

Question 31

transition lookaside buffer (TLB)

Answer 31

A fast associate memory buffer that maintains recent translations of logical addresses to frames in physical memory for faster retrieval.

Question 32

principle of locality

Answer 32

locations accessed recently are more likely to be accessed again than locations accessed in the distant past.

Question 33

hit ratio

Answer 33

The fraction of memory accesses that find a match in the TLB. The higher the TLB hit ratio, the lower the overhead of address translation.