22. Beyond Physical Memory: Policies Flashcards
What is AMAT? What is the formula?
AMAT stands for average memory access time. It is calculated as (AMAT = T + (Pm * Td), where T is cost of memory access, Pm is miss rate and Td is cost of disk access
How does optimal policy work? Is it used and how?
Replace the page that will be accessed further in the future. It’s not possible to implement it in general purpose OS so it’s only used a comparison marker.
What a replacement policy is compared to?
To an optimal policy.
What are three types of misses are there?
Compulsory (cold start) miss occurs because cache is empty. Capacity miss occurs because the cache is full and had to evict an item to bring new one in the cache. Conflict miss arises because of limits on where an item can be placed in hardware cache.
What are types of replacement policies are there?
FIFO - replace the page that came in first. Random - just evict randomly.
What are the two algorithms based on history and which metrics they use?
LFU (Least frequently used) and LRU (Least recently used). They are based on frequency and recency of pages.
What bit does LRU use for approximating? What approximating and not keeping all data to make a certain decision?
Use (or referrence) bit. Keeping all data is costly to navigate through.
How exactly is referrence bit used for approximating?
With a clock algorithm. When a replacement must occur, OS checks if the currently pointed page (with clock hand) has a referrence bit set to 0. If no, it clears the bit (sets from 1 to 0) and proceeds to next page. If it has 0, it evicts this page.
What is dirty bit and why is it used?
It’s a bit that specifies whether the page was modified while in memory. Evicting a dirty page is costly because requires writing it back to disk. While clean pages can be evicted for free since they are unchanged.
What technique can be used to optimize writing pages to disk?
Clusterring or groupping of pages.
What are other policies employed by VM subsystem?
Page selection policy (on demand, prefetching) and policy that determines how OS writes pages back to disk (clustering, grouping).
What property of a program improves cache hit rate?
Locality (spatial and temporal)
What is downside of LRU type algorithms?
We need to track the access to pages and update some data structure each time, which can decrease performance
What is the other policy used beside the page replacement policy?
Page selection policy (when to bring a page in memory). For most pages, OS uses demand paging (bring in page when it’s needed).
Also the writing to disk policy (grouping, clustering)
What is other technique different from demand paging?
Prefetching (guessing that a page is about to be used and fetching it)
