Page Replacement Flashcards
Virtual Memory Policies
1. Virtual Memory Policies are built on the Principle of Locality.
a) [4pts] Define locality. (Include both types!
Spatial Locality: If a memory location is accessed at a particular time, nearby locations in memory are likely to be accessed in the near future.
Temporal Locality: If a location in memory is accessed at a particular time, it is likely to be accessed again in the near future.
(b) [4pts] The virtual memory system and its policies exploit locality. Name two policies and/or pieces that do so.
Large page sizes (Spatial Locality???)
Working set (Temporal and Spatial Locality)
TLB (Temporal and Spatial Locality)
(c) [2pts] What is Belady’s anomaly?
The phenomenon that increasing the number of page frames can possibly result in an increase in the number of page faults in FIFO.
- A system that uses a demand-paged virtual memory system has been running for a long time. (A really long time. This user reboots once per semester.)
Assertion: Physical memory is either full or it is not.
(a) [3pts] If physical memory is full, what happens when an application is scheduled on the CPU for the first time?
Load balancing, a process is suspended and all of its resources are reclaimed
Due to demand paging, pages will be evicted
(b) [3pts] If physical memory is NOT full, what happens when an application is scheduled on the CPU for the time?
Load the application into frames in physical memory
(c) [3pts] Name two possible reasons a system that has been executing applications for months has empty frames in physical memory.
Working Set Algorithm
Page reclamation when processes finish
- [4pts] Suppose P1 and P3 both access valid virtual address 0x12345678. What happens?
The address is translated for both pages and the two pages are loaded into frames
Virtual Memory Short Answer
1. [2pts] A page replacement algorithm executes, and a page is selected to be evicted. What bit(s) in the page table must be inspected to determine whether the data in that page should be written?
the dirty/modified bit
- [8pts] The second chance page replacement algorithm inspects two bits. Identify the two bits and describe the actions the algorithm takes for each of the four possible combinations of the bit values.
Referenced bit and modified bit
(1) If (0,0), then replace.
(2) If (1,0), then clear the referenced bit.
(3) If (0,1), then clear dirty bit and initiate I/O to write the page in parallel.
(4) If (1,1), then clear the referenced bit.
- [4pts] When the second chance page replacement algorithm identifies a page that is not recently used but is modified. Should it schedule a write for that page immediately? Defend your answer.
No, it should make a note of it and continue the algorithm to find a page that has not been recently used and has not been modified. If the clock algorithm comes back around and hasn’t found another page to evict, then write the page to swap.
Alternatively, yes, but should continue its search for a page to evict in parallel
Paging Policies
1. When we began discussing page replacement algorithms in class, we started with FIFO because, well, because it is the easiest.
(a) [2pts] FIFO is easy to think about, but is it easy to implement? Defend your answer.
No because it is hard to keep track of which frame comes in first, we would have to store arrival times or some sort of comparable system
(b) [2pts] The next algorithm we considered was LRU. Is it efficient to implement? Defend your answer.
It is not efficient to implement because it would require additional overhead to keep track of the time that each page was used recently,
- [3pts] In the algorithms above, what happens to the page being evicted if it has been modified?
Must be written to swap
- You are implementing virtual memory for your company, LazyOS, which is trying to write the lowest overhead operating system possible. You have so far implemented paging with address translation and your favorite page replacement algorithm.
(a) [4pts] When your page replacement algorithm replaces a page, what should it do with that page?
If it’s modified, write it to the swap partition otherwise just overwrite the page.
(b) [4pts] You notice that, in testing, the physical memory of the system is filling quickly, and the page replacement algorithm is executing on every page fault. Given that the page replacement algorithm you’ve chosen (enhanced clock!) requires so much work at a time when a process is waiting for its page to appear AND that processes don’t seem to really be using all of their resident pages, you decide that you are going to implement the working set algorithm. What does it do and why might that be appropriate here?
The working set algorithm preemptively evicts pages that have not been used in a particular working set window. This is appropriate here because if pages are preemptively evicted, the memory will become full less often and page replacement will not have to run often.
