We now enter the Memory Management part; this post introduces main memory.
Background
Main memory and registers are only storage CPU can access directly.
But main memory is slower to access than registers, which can cause memory stalls
Protection: base and limit registers ensure that a process can only access memory addresses within its own address space
Address binding: translating logical addresses into physical addresses, at compile time, load time, or execution time
MMU: Memory Management Unit, a hardware device responsible for translating logical addresses into physical addresses
Contiguous Memory Allocation
two partitions: OS and user processes(low and high memory)
Let the logical address be
Variable Partition
Memory is allocated on demand from holes (free memory regions), but this produces fragmentation (external fragmentation)
- First-fit: Allocate the first hole that is big enough
- Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
- Produces the smallest leftover hole
- Worst-fit: Allocate the largest hole; must also search entire list
Produces the largest leftover hole
Clearly, every one of these approaches causes a lot of fragmentation; it can be addressed by compaction, but the effect is limited
Non-contiguous Memory Allocation
Paging
In short, both physical memory and logical memory are divided into fixed-size units, called frames and pages respectively, and a page table maps between them (this reduces external fragmentation, but cannot reduce internal fragmentation)
In a paged memory management system, the logical address generated by the CPU is divided into two parts, a page number (p) and a page offset (d), which are used to translate the logical address into a physical address.
- Page number (p): the page number is an index into the page table, which stores the base address of each logical page in physical memory. Using the page number, the corresponding physical frame number can be found in the page table, establishing the mapping from virtual pages to physical frames. For example, if page number 3 in the page table corresponds to physical frame number 7, then when the CPU generates a logical address with page number 3, the corresponding physical frame 7 can be found.
- Page offset (d): the page offset is combined with the physical frame base address looked up in the page table to determine the physical address of the memory unit. Since pages and frames have the same size, the page offset denotes the same position within a virtual page and within a physical frame, so it can be combined directly with the physical frame base address to locate the physical address. For example, if the page size is 4KB (4096 bytes), the page offset is 100, and the physical frame base address is 8192, then the physical address is 8192 + 100 = 8292.
- Bit allocation: for a given logical address space of
and a page size of , the page number occupies bits and the page offset occupies bits. For example, with a logical address space of (a 32-bit address space) and a page size of (4KB), the page number occupies 32 - 12 = 20 bits and the page offset occupies 12 bits. This bit allocation ensures that logical addresses are mapped correctly to physical addresses.
TLB(Translation Lookaside Buffer)
Page table lookups are expensive in time (two memory accesses). The TLB is a small, fast cache that stores frequently used entries of the page table and is used to speed up the translation from logical addresses to physical addresses. On a hit, the physical frame number is obtained directly from the TLB; otherwise it is obtained from the page table.
Memory protection implemented by associating protection bit with each frame to indicate if read-only or read-write access is allowed.
Structure of the Page Table
One simple solution is to divide the page table into smaller units
- Hierarchical Paging: multi-level page tables, similar to a B+ tree?
- example: two-level page table
- Hashed Page Tables
- Inverted Page Tables
Hierarchical Paging
| Advantages | Disadvantages |
|---|---|
| Lower memory overhead: only the actively used parts of the address space are mapped | Higher memory access latency: translating a virtual address requires walking multiple page table levels, adding overhead |
| Scalability: accommodates larger address spaces without a proportional increase in memory overhead | Larger page table size: in systems with large address spaces, storing page table entries consumes a lot of memory |
| Better locality: exploits spatial locality, since virtual pages are often mapped to adjacent physical frames | Implementation complexity: more complex to implement and manage than a flat page table |
| Flexibility: different hierarchical structures can be adopted according to system requirements and memory characteristics | Fragmentation: in systems with sparse address spaces, fragmentation problems arise easily |
Hashed Page Tables
| Advantages | Disadvantages |
|---|---|
| Lower memory overhead: only the actively used parts of the address space are mapped | Collision handling: hash collisions can reduce lookup efficiency |
| Flexibility: adapts to different address space sizes | Implementation complexity: hash function design and collision handling are complex |
| Lower memory access latency: efficient lookups | Memory overhead: the hash table has a considerable storage overhead |
Inverted Page Tables
An inverted page table is a memory paging management scheme that differs from the traditional forward page table; it is used to solve the problem of page tables consuming too much memory under large address spaces.
- Basic principle: traditional page tables are organized per process; each process has its own page table recording the mapping from its virtual pages to physical frames. An inverted page table, by contrast, is indexed by physical frame, with one entry in the inverted page table for each physical frame. Each entry records the process identifier (PID) of the page stored in that physical frame and the page number of that page within the process’s virtual address space.
- Advantages: an inverted page table significantly reduces the memory occupied by page tables. In a system with a large address space, if traditional page tables are used, each process’s page table may occupy a lot of memory; an inverted page table only needs to maintain one entry per physical frame, so no matter how many processes there are, the size of the page table depends only on the number of physical frames, which effectively reduces memory overhead.
- Drawbacks and remedies: the main problem with inverted page tables is low lookup efficiency. During address translation, since the corresponding physical frame number cannot be found directly from the virtual page number, the entire inverted page table has to be traversed to match the process identifier and virtual page number. To solve this problem, a translation lookaside buffer (TLB) is usually used in combination. The TLB is a fast cache that stores recently used mappings from virtual pages to physical frames. During address translation, the TLB is searched first; if the mapping is found (TLB hit), the physical frame number is obtained quickly; if not (TLB miss), the inverted page table is traversed to find it, and the mapping found is added to the TLB so it can be accessed quickly next time.
Swapping
Used when memory resources are tight to move temporarily unused processes or parts of their data from memory to a backing store on disk, freeing up memory for processes that need it more; when a swapped-out process or its data needs to be used again, it is brought back from disk into memory.
Translated from the Chinese original.
