6.1 Contiguous Memory Allocation
In contiguous memory allocation, each process is placed into a single, unbroken block of physical memory. The operating system must decide how to partition RAM among multiple resident programs while mitigating memory fragmentation.
Figure 6.1: Internal fragmentation wastes space inside allocated slots; external fragmentation breaks free memory into unusable scattered holes.
Dynamic Partition Allocation Strategies
- First-Fit: Allocate the very first available free block that is large enough. Fast because search terminates on the first match.
- Best-Fit: Search the entire list to allocate the smallest hole that is large enough. Leaves behind tiny unusable leftover slivers of free space.
- Worst-Fit: Search the entire list to allocate the largest available hole. Produces the largest leftover hole, which may be useful for subsequent allocations.
6.2 Paging
Paging is a non-contiguous memory management scheme that completely eliminates external fragmentation. Physical memory is divided into fixed-size blocks called frames, while logical (virtual) memory is divided into blocks of the exact same size called pages.
Figure 6.2: Every CPU logical address split into page number (p) and offset (d). The page table maps p to physical frame f, while d passes through unchanged.
Translation Look-Aside Buffer (TLB)
Because the page table itself lives in main memory, every memory reference requires two accesses: one for the page table entry, and one for the actual byte. To accelerate translation, modern CPUs include a Translation Look-aside Buffer (TLB) ā an ultra-fast hardware associative cache storing recent $langle ext{page}, ext{frame} angle$ mappings.
Effective Memory Access Time (EMAT) Formula:
EMAT = Hit_Ratio × (TLB_access + Memory_access) + (1 − Hit_Ratio) × (TLB_access + 2 × Memory_access)
6.3 Segmentation
While paging divides memory into uniform physical blocks transparent to the programmer, Segmentation reflects the programmer's logical view of memory. A program is viewed as a collection of variable-length logical units called segments (e.g. main program, procedures, stack, global variables, symbol tables).
Figure 6.3: Each segment maps to physical memory via a Base (start address) and Limit (length). Offset must be strictly less than Limit.
