CST-334 Week 4

This week is our fourth week in CST-334, also known as Operating Systems.

Operating Systems: Three Easy Pieces

This week we read chapters 18-22 of our textbook.

Chapter 18 discusses the basic concepts behind paging.

Key Takeaways:

Memory is split into many sections of the same size. These sections are called pages or page frames.
The OS keeps a list of free pages, known as a free list.
The OS keeps a page table for each process, which stores address translations for each of the virtual and physical pages associated with the process.
The OS virtual memory addresses into a VPN and an offset. The VPN is used to find the correct page, and the offset is used to find the correct location within a page.
An entry on a page table may have extra metadata bits, such as protection bits, valid bits, or dirty bits.

Chapter 19 discusses Transaction Lookaside Buffers (TLB), and how they can be used to speed up address translation.

Key Takeaways:

A TLB is a hardware cache of popular virtual-to-physical address translations.
The hardware first checks the TLB for address translations. If it doesn't find the translation in the TLB it looks at the page table, adds the translation to the TLB, and retries the instruction.
Temporal Locality states that memory that is accessed is likely to be accessed again in the near future.
Spatial Locality states that memory is likely to be accessed in the near future if it is near other memory that is accessed.

Chapter 20 discusses how to reduce page table overhead.

Key Takeaways:

Page tables become prohibitively large as address space size increases.
Reducing page size improves page table overhead, but increases fragmentation.
Multi-level page tables consist of a page directory and multiple page tables.
Multi-level page tables reduce overhead by only allocating page tables with valid pages.
An address's VPN is split for each level of the multi-level page table.

Chapter 21 discusses how TLBs and swap spaces.

Key Takeaways:

Storage, such as HDDs, can be used to store pages if the system runs out of memory.
Swap space is a portion of storage reserved for swapping pages in and out of memory.
The present bit in the TLB tracks whether a page is kept in memory.
A page fault occurs when a page is not in memory.

Chapter 22 discusses page-replacement policies.

Key Takeaways:

The average memory access time (AMAT) uses the cost of TLB misses and hits, and the probability of a miss, to calculate the average time a memory translation will take.
The optimal replacement policy replaces pages that will be accessed furthest in the future. It is used for benchmarks.
First In First Out (FIFO) replaces the page that was loaded first.
Random chooses which page to replace at random.
Least Recently Used (LRU) replaces the page that was used the least recently.