CST 334 week 4 (28/100)

 Josh Goldberg

CST334 40_2262

Mar 30, 2026

This week we went deeper into paging and free space management. We reviewed the malloc() and free() library functions and how they manage memory allocation with a free list. The free list contains chunks that have a size and a pointer to the next free node in a linked list. Behind these functions are the mechanisms that satisfy the memory allocation policies. Splitting will split a chunk into two to right-size a chunk for an allocation request and keep the remainder fragment in the free chunk list. Coalescing is the inverse. It will merge adjacent free chunks to reduce small fragments. Each chunk has a header that indicates the next chunk, whether this chunk is free or not, and a magic number for integrity checks. Following the header is the actual chunk space to be allocated. When a free(ptr) is called with a pointer to space, it’s pointing at the free space. We find the header at ptr - sizeof(header_t).

Allocator goals: correctness, speed, low overhead, and minimize fragmentation.

Faster paging is managed with the translation lookaside buffer. It is a hardware cache in the MMU that keeps a lookup table of VPN -> FPN translations. Because it is an associative cache, any lookup takes 1 clock cycle. On a TLB hit we get the physical address right away. On a miss, we have to find the page table, get the PFN, save the translation, then retry the lookup. This works because of temporal locality, meaning that recently accessed pages are likely to be accessed again like in a tight loop, and spatial locality, that nearby elements on the same page are likely to be accessed soon. Any access to a part of a page loads the whole page into the TLB so every lookup for any data in the page is 1 clock cycle.

We measure efficiency with average memory access time as AMAT = (hit rate * hit time) + (miss rate * miss penalty). The best case is a 100% hit rate => AMAT=1. So anything less than 100% means AMAT > 1.

On a context switch, we can either invalidate the whole TLB or better yet, use ASID to assign TLB entries to specific processes. This allows the TLB to be shared.

With a lot of memory, the page table would get overwhelmingly large. So we can either use big pages, hybrid paging+segmentation, or multi-level page tables, which is what most modern systems use. A page directory is added to each page to track sub pages. Each Page Directory Entry has a valid bit and PFN pointing to a page of PTEs. Each page table page has a set number of PTEs for a set of VPNs. MLPT lets us allocate only the space that is actually in use but a TLB miss requires multiple lookups and is more complex.

If memory is full then we need to swap. This means we save inactive pages to disk. When we try to lookup a page and its not in physical memory then it’s a page fault and we have to look it up on disk. The PTE manages data about a page’s presence in memory and its location on disk. When loading a page from disk we need to swap out some other page from physical memory to disk. This activity is blocking for the process requesting access.

Page replacement policy is set by some caching strategy. Belady’s algorithm is the benchmark but it has perfect future knowledge so it’s only theoretically possible. FIFO is a first in first out eviction policy, random picks a page at random to evict, LRU picks the least recently used page to evict. This is the best modern policy because of the temporal and spacial locality trends that we discussed earlier.