Virtual Memory Part 2 Flashcards
(78 cards)
What 6 steps are required when handling a page fault?
1. OS figures out:
•Invalid reference
➔abort process
•Just not in memory
➔bring page in
2. Locate page on disk
3. Find a free page frame
4. Swap page from disk to frame (I/O operation)
5. Reset page table, set valid bit to 1
6. Restart the instruction that caused page faultIf the OS doesn’t have enough memory when swapping, it needs to ______ an __________ page in physical memory to make room for the _______ page
evict, existing, incoming
What does a page replacement policy do?
It handles the eviction of existing pages in physical memory to make room for the incoming page
What are 3 page replacement policies?
- First-in-first-out
- Least recently used
- Second-chance (Clock)
We can save swap out _______ if the victim page was ___ ________
overhead, not modified
The goal of Page Replacement Algorithms is to…
minimize page-fault rate
To evaluate a _____ __________ ________, we compute the number of page faults that will occur if we follow a set sequence of memory page references
Page Replacement Algorithm
We expect the number of page faults to ________ as the number of physical frames allocated to process ________
decreases, increases
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 3 page frames using the FIFO algorithm?
9
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the FIFO algorithm?
10
What is Belady’s Anomaly?
More frames may result in more page faults
A pro of the FIFO replacement algorithm is that it is…
easy to understand an implement
Why is performance not always good with the FIFO replacement algorithm?
- May replace a page that is used heavily
- Suffers from Belady’s Anomaly
The optimal replacement algorithm would replace the page that has not been used for the _______ time
longest
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the optimal replacement algorithm?
6
Can we implement the optimal replacement algorithm? If so, how? If not, why?
No, because we cannot predict the future
What is the optical replacement algorithm used for?
It is used as a benchmark for comparing algorithms
With the Least Recently Used Algorithm, we try to ________ the optimal policy by __________ the future based on the _______
approximate, inferring, past
With the Least Recently Used Algorithm, we replace the page that has not been used for the _________ time
longest
Why do we replace the page that has not been used for the longest time in the LRU algorithm?
The page may not be needed anymore. Ex. pages of an initialization module
Does LRU suffer from Belady’s Anomaly?
No
For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the LRU algorithm?
8
In the LRU counter implementation, each page-table entry has a ______-___-____ field
time-of-use
In the LRU counter implementation, the CPU ______ _____ is copied into the time-of-use field upon page ________
logical clock, reference
