Page Replacement Algorithms in Operating Systems

Page Replacement Algorithms David Ferry CSCI 3500 Operating Systems Saint Louis University St. Louis, MO 63103 1

Recall: Paging Paging Divide a program s virtual memory into pages Divide physical memory into page frames Memory Program 1 Program 2 D A A A B B B A C C C B D D Pages are taken from the hard drive and placed in memory as needed Programs do not need to be contiguous in memory, don t even need to be in order Programs can be partially in memory CSCI 3500 - Operating Systems 2

Recall: Page Faults Memory Management Unit (MMU) Physical Memory (RAM) Disk Hit Virtual Address CPU Physical Address TLB Not Desired Page Frame Page Table Miss Present Page Frames Page Mapping Returned Data 1. CPU generates virtual address 2. If the page mapping is available in TLB; HIT, go directly to physical address If page mapping not available in TLB; MISS, go to page table to get mapping (also called a minor or soft page fault) 3. If the page is not currently loaded in memory, load it from disk (major or hard page fault) CSCI 3500 - Operating Systems 3

Why Page Faults Happen Two basic types of page faults: 1. Compulsory misses (cold misses) occur when a page is first referenced. These always occur and are generally unavoidable outside of pre- fetching strategies. 2. Conflict misses occur when a page is evicted from memory and then needed later. Avoidable if the working set size (number of pages needed at any given time) is smaller than the size of memory If the WSS is larger than memory, then we seek to minimize the number of page faults CSCI 3500 - Operating Systems 4

Page Replacement and Evictions Page Replacement and Evictions E.g. in the picture below we only have room for four page frames but there are eight pages needed Victim pages are evicted to make room for new pages (Hard) Page faults occur whenever a page is moved into memory Memory Program 1 Program 2 D A A A B B B A C C C B D D CSCI 3500 - Operating Systems 5

Page Replacement Cost 1. Page frames (i.e. memory) are a limited resource! 2. Page faults are extremely expensive Hard drive or SSD is orders of magnitude slower than memory Average Access Time: Microseconds 12000 120,000x difference 12000 10000 30,000x difference 8000 6000 3000 1000x difference 4000 2000 100 0.1 0 Low-End HDD High-End HDD SSD Memory CSCI 3500 - Operating Systems 6

Page Replacement (Eviction) Algorithms Problem: Suppose all page frames are full, and we need to load a new page into memory which existing page do we get rid of? Page Frames A ? ? B E Goal: Minimize conflict misses ? ? C D Procedure: Record a sequence of page accesses, then replay that sequence with different algorithms and record number of page faults Underlying idea: Exploit locality of reference CSCI 3500 - Operating Systems 7

Locality of Reference Spatial Locality of Reference assumption: future memory accesses will be physically nearby the current memory references Temporal Locality of Reference assumption: future memory accesses will be memory accesses that we have accessed recently Consider different use scenarios: Walking an array Walking a linked list Accessing a hash table Watching a DVD Playing a videogame Flipping through photos in a folder Caching Google search queries Caching Netflix content CSCI 3500 - Operating Systems 8

Eviction Algorithms Clairvoyant Evict the page that will be needed farthest into the future. Not possible in practice, but can be shown to be optimal. Useful as a point of comparison. FIFO Evict the page that was loaded farthest in the past. Simple algorithm. Least Recently Used (LRU) Evict the page that has not be used for the longest time. Hard to implement. Least Frequently Used (LFU) Evict the page that is used least frequently - e.g. count number of accesses. CSCI 3500 - Operating Systems 9

Clarivoyant Algorithm Example Suppose a sequence of page accesses: A B C B D B E A B A Memory And a memory with three page frames: (page faults in bold) A B CD XXE Clarivoyant: A B C B D B E A B A Compulsory misses: 5 Conflict misses: 0 CSCI 3500 - Operating Systems 10

FIFO Algorithm Example Suppose a sequence of page accesses: A B C B D B E A B A Memory And a memory with three page frames: (page faults in bold) A X D X B B X E C XA FIFO: A B C B D B E A B A Compulsory misses: 5 Conflict misses: 2 CSCI 3500 - Operating Systems 11

LRU Algorithm Example Suppose a sequence of page accesses: A B C B D B E A B A Memory And a memory with three page frames: (page faults in bold) D XA A X B C X E LRU: A B C B D B E A B A Compulsory misses: 5 Conflict misses: 1 CSCI 3500 - Operating Systems 12

Algorithm Comparison For this workload (important assumption): Clairvoyant had 0 conflict misses FIFO had 2 conflict misses LRU had 1 conflict miss In practice, if you were to build a new MMU and implement your own paging algorithm, your decision would be heavily dependent on workload assumptions. LRU and LRU-derivatives are frequently used in practice and yield 99%+ hit rates. CSCI 3500 - Operating Systems 13

LRU in Practice LRU would be hard to implement efficiently Would need to keep and update access time for all pages in memory Would need to search all access times to find the oldest Let s approximate instead: Not Recently Used (NRU) Define four classes: 1. Not referenced, not modified 2. Not referenced, modified 3. Referenced, not modified 4. Referenced, modified Algorithm: Evict a random page from the lowest numbered class available. CSCI 3500 - Operating Systems 14

Paging: Conclusion Paging is the modern solution to memory management- used by Linux, Windows, etc. and is supported in processor MMU hardware via TLB Processes live in a virtual memory space that looks like they are the only process that lives on the system Virtual (logical) addresses are seen by the processor and your program, but are translated transparently and seamlessly by the OS & MMU Strong process space protection and isolation most of the time (see Meltdown and Specter attacks for a recent breach here) Avoids the allocation problem and fragmentation caused by earlier approaches such as base & limit registers or partitioning real-mode memory CSCI 3500 - Operating Systems 15