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
