Chapter 6: Memory Management Flashcards
Physical Memory (RAM)
A hardware structure, consisting of a linear sequence of words that hold a program during execution.
Word
A fixed-size unit of data (typically 4 bytes, but can be other sizes)
physical address
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.
logical address space
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.
logical address
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.
source module
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.
object module
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
load module
a program or combination of programs in a form ready to be loaded into main memory and executed.
Program relocation
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.
Static relocation
binds all logical addresses to physical addresses prior to execution
Dynamic relocation
postpones the binding of a logical address to a physical address until the addressed item is accessed during execution
relocation register
contains the physical starting address of a program or program component in memory.
First-fit
always starts the search from the beginning of the list and allocates the first hole large enough to accommodate the request
Next-fit
starts each search at the point of the last allocation
Best-fit
searches the entire list and chooses the smallest hole large enough to accommodate the request
worst-fit
takes the opposite approach from best-fit by always choosing the largest available hole for any request
external memory fragmentation
the loss of usable memory space due to holes between allocated blocks of variable sizes
50% rule
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.
swapping
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.
memory compaction
the systematic shifting of modules in memory, generally in one direction, to consolidate multiple disjoint holes into one larger hole.
linking
The act of resolving external references among object modules and can be done statically, before loading, or dynamically, while the program is already executing.
sharing
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.
page
A fixed-size contiguous block of logical address space identified by a single number, the page number.
page frame
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.
page table
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
Address Translation Algo
- Given a logical address (p, w), access the page table entry corresponding to page p.
- Read the frame number, f, of the frame containing p.
- Combine f with the offset w to find the physical address (f, w) corresponding to the logical address (p, w).
Internal Fragmentation
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.
segment
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.
segment table
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.
address translation (logical -> physical)
- 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.
- If w ≥ sze then reject the address as illegal.
- Otherwise, add w to sa to form the physical address, sa + w, corresponding to the logical address (s, w).
- 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.
- 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.
- Combine f with the offset w to form the physical address, (f, w).
transition lookaside buffer (TLB)
A fast associate memory buffer that maintains recent translations of logical addresses to frames in physical memory for faster retrieval.
principle of locality
locations accessed recently are more likely to be accessed again than locations accessed in the distant past.
hit ratio
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.
