CST 334 – Week 4: Memory Virtualization (cont’d)

This week we continued to learn about how the OS handles virtual memory. The lectures and readings got into the details of how the OS works with hardware to optimize performance and solve problems that arise when dealing with virtual memory, while the assignments helped with learning how the mechanisms involved work.

Topics covered this week

This week’s lectures covered OSTEP chapters 17, 19, 20, 21, and 22.

OSTEP 17: Free-Space Management

This chapter/lecture explained how the OS keeps track of free (unused) memory. The main design goals include the following:

• Correctness: in-use memory should never be corrupted, and free memory should actually be unused; this is the most important goal.
• Speed: memory allocation should be as fast as possible.
• Avoid memory overhead: minimize space used for metadata to maximize space for actual memory allocations.
• Satisfy as Many Requests as Possible: memory allocation should not fail and should not be a bottleneck.

To achieve these goals, the OS can choose from different allocation policies, like first fit, best fit, and worst fit.

• Best fit: finds the smallest chunk of free memory that fits.
• Worst fit: finds the largest chunk of free memory.
• First fit: finds the first chunk of free memory that will fit.

We also discussed two mechanisms, splitting and coalescing, that work together to reduce wasted memory space.

• Splitting breaks large blocks of memory into smaller ones when allocating, so that the free space isn’t wasted.
• Coalescing combines smaller blocks of adjacent free memory into larger blocks, so that it becomes contiguous free space.

Together, these mechanisms keep memory efficient and flexible.

OSTEP 19: Translation Lookaside Buffers (TLBs)

This chapter/lecture explained the TLB and why we need it. Paging involves an extra memory lookup, which makes it slow compared to accessing the memory directly. The TLB solves this problem by providing a hardware cache that returns cache hits in a single clock cycle.

The TLB uses the locality of memory access patterns to determine what is cached:

• Temporal locality: caching memory that was used recently.
• Spatial locality: caching memory addresses that are near recently used ones, since they are more likely to be accessed soon.

We also learned how the TLB performs an address translation:

1. Split virtual address (VA) into VPN and offset.
2. Check the TLB cache for the VPN → PFN mapping.
   • If there is a cache hit, use the PFN from the cache.
   • If there is a cache miss, get the PFN from the page table and cache it for the next translation.
3. Check if the memory access is valid.
4. Use PFN plus offset to form the physical address (PA).

OSTEP 20: Multi-Level Paging

This chapter/lecture introduced a problem with paging and its solution. Each process needs its own page table, and much of the address space for each process is not used, which leads to a lot of wasted memory. The solution is multi-level paging, which only allocates the memory that is necessary and stores an index of page table chunks in the page directory. Both the page directory index and page table index are included in the VPN.

This improves memory utilization, but requires an additional step to perform address translations. The TLB caches the PFN to speed up memory access, so only TLB cache misses will require the additional PD lookup step.

OSTEP 21-22: Swapping

This lecture covered chapters 21 & 22 in OSTEP, which describe the mechanisms and policies involved with swapping memory. Storage space in RAM is limited, so the OS must store some memory pages in secondary storage, which has a lot more space to work with.

Swapping introduces the present bit, which indicates whether a page is in memory, or if the OS must fetch the page from disk. The mechanics of swapping look like this:

1. Check TLB for VPN.
   • If VPN is in the TLB, return the PFN.
2. Otherwise, lookup the VPN in the page table.
3. Check if the present bit is set in the PTE.
   • If it is set, cache the PFN in the TLB and return the PFN.
   • If it is not set, raise a page fault.

The OS handles the page fault by fetching the page from disk and storing it in memory.

The OS needs a policy to determine which pages get swapped out when memory is full. There are a few different policies for this:

1. FIFO: evict the oldest page.
2. LRU: evict the least recently used page.
3. Random: select a random page to evict.
4. Optimal (Belady): evict the page that is used furthest in the future.

The Optimal (Belady) strategy is not achievable in practice, since we can’t know the future, but it can be helpful for comparison when benchmarking.

There were two metrics described that are useful for benchmarking:

1. Cache hit rate: the percentage of requests that result in cache hits. Calculated as (hits / total requests) where total requests can include or exclude compulsory misses, when the page is first requested.
2. Average Memory Access Time (AMAT): the average time to access a page in memory, considering cache hits and misses. Calculated as (hit rate * memory access time) + (miss rate * disk access time).

Reflection

After reviewing the course material for this week and the previous week (which also covered virtual memory), I’m feeling like I have a better handle on the topic. Looking ahead, next week we’re going to learn about concurrency, which should be an interesting shift from memory management into how the OS can do multiple things at the same time.

Concurrency in programming is something that I’m familiar with, but haven’t learned about in detail, so it will be interesting to find out how it’s handled at the OS level. I know that some programming languages support multithreading, while others do not, so it will be a good opportunity to explore this topic more.