22. Swapping Policies Flashcards
What is average memory access time (AMAT)?
Cost of Accessing Memory + (Probability cache miss * cost of accessing disk)
What is the optimal replacement policy?
Assuming we have all the future page access data, we evict the page that will be accessed furthest in the future.
What is cold-start miss?
Cache miss in an empty cache state (unavoidable)
What is capacity miss?
Cache had to evict an item because the cache run out of space to add a new item
What is conflict miss?
Cache could not store an item because it is not fully associative. OS pages are fully associative
What is the FIFO replacement algorithm?
Evicts the page that arrives first
What is the random replacement algorithm?
Evicts a random page
What is the least recently used (LRU) algorithm?
Evicts the page that is the least recently used
What is the least frequently used (LFU) algorithm?
Evicts the page that is the least frequently used
What is the most recently used (MRU) algorithm?
Evicts the page that is the most recently used
What is the most frequently used (MFU) algorithm?
Evicts the page that is the most frequently used
What hardware support do we need to approximate LRU?
A use bit (aka reference bit) for every page. 1 indicates it was used, 0 means it wasn’t used
How does the clock algorithm work?
When a replacement is needed, it will scan for the first page that has a use bit of 0. If the use bit is 1, it will reset to 0 and move forward until it finds a suitable candidate for eviction.
This is done in a circular queue manner
What does the dirty bit do?
To indicate if the page that is in memory has been modified. If the page has been modified, the dirty bit is set to 1. This is because eviction of a clean page is free, but a dirty page has to be written to disk
What are page selection algorithm for?
To choose when to bring a page into memory
How does the OS write pages out of disk?
They typically do them in clusters because it is more efficiently than doing multiple small writes
What is prefetching?
Predicting which page will be used and fetching it beforehand
What is thrashing?
When the system is constantly paged
What are some methods of solving thrashing?
- Admission control: the OS decides not to run a subset of processes
- Out-of-memory killer: the OS kills the most memory-intensive process
- Buy more memory
