18. Page Replacement Flashcards
On certain architectures, the MMU will search the page table itself to locate virtual-to-physical address translations missing from the TLB. What are the pros and cons of this?
The pro is that hardware is way faster.
The con is that the OS must set up the page tables in a fixed way that the hardware understands.
With a hardware-managed TLB, the kernel sees TLB faults. They are handled in hardware.
What is a TLB fault?
A required virtual to physical address translation is not in the TLB
What is a page fault?
The contents of a virtual page are either not initialized or not in memory.
Note: Every page fault is preceded by a TLB fault
Why is every page fault preceded by a TLB fault?
If the contents of the virtual page are not in memory, a translation cannot exist for it.
Why is it that not every TLB fault generates a page fault?
If a page is in memory and the translation is the page table, the TLB fault can be handled without generating a page fault
When must we swap in a page?
When the virtual address is used by the process
What do we need to do first to swap out a page?
We need to choose which page to move to disk
When swapping in a page, what might we need to do first?
We might need to choose which page to swap out
What is the cost of swapping a page out (page eviction)?
Mainly the time and disk bandwidth required to move a page to and from the disk
What is the benefit of swapping a page out (page eviction)?
The use of 4K (or a page) of memory (as long as the page on disk remains unused)
What are three methods of improving performance of page translations?
- OS uses methods to minimize the cost of a page swap
- Algorithms can be designed to maximize the benefits of a page while it’s in memory
- Minimize the page fault rate
What is thrashing?
When a computer’s virtual memory subsystem is in a constant stage of paging, rapidly exchanging data in memory for data on disk.
This causes the performance of the computer to degrade or collapse.
How do we maximize the benefit of page eviction?
Pick the page to evict that will remain unused the longest
What is the absolute best page to evict, the one that page replacement algorithms dream about?
A page that will never be used again.
What would we like to know about a page when choosing one to evict?
How long it will be before this page will be used again.
It’ll allow us to choose the one that won’t be used for the longest
When we can’t predict the future, how do we choose the optimal page to swap out?
Use the past!
What are the three things required to do intelligent page replacement?
- Determine what [relevant] information to track
- Figure out how to collect that information
- Store that information
In a hardware assisted translation system, what information does the OS not have access to?
The OS won’t know how many times an address is used, so it won’t know how useful a given page is or isn’t.
The OS won’t know this information because it isn’t involved in the translation.
What are the CONS of collecting usage statistics for pages?
- Collecting statistics may be computationally expensive, slowing down the process of translating virtual addresses
- Storing statistics may be expensive, occupying kernel memory that could be better used for other things.
What is the simplest possible page replacement algorithm?
Random replacement
What are the PROS of a random page replacement algorithm?
It’s extremely simple and a good performance baseline for algorithms that try to be smarter than random
What are the CONS of a random page replacement algorithm?
It’s way too simple. We can definitely do better than this.
Think, do we want to risk randomly swapping out (evicting) a page used by a high-priority process?
What is an algorithm that uses a page’s past to predict its future?
Least Recently Used (LRU).
LRU chooses the page that has not been used for the longest period of time and hopes that this page will not be used again for a while
What are the PROS of the Least Recently Used (LRU) algorithm for page eviction?
It might be as good as we can do without actually predicting the future
What are the CONS of the Least Recently Used (LRU) algorithm for page eviction?
We need to know AND store data on how long it has been since a page has been accessed
When storing statistics for running a Least Recently Used algorithm for page eviction, how much access time information can we store?
32 bits = 2^32 “ticks”. This literally doubles the page table entry size.
8 bits = 256 bits. This is better.
Assuming we have the appropriate statistics, how do we find the least recently used page?
We need some kind of efficient data structure which holds all physical pages on the system that is searched on every page eviction
What are the three steps required to locate a page to evict in Clock LRU?
- Cycle through all pages in memory in a fixed order
- If a page accessed bit is clear, evict that page
- If a page accessed bit is set, clear the bit
Note: There is a record of where on the data structure the last cleared page was, that way the next time we need to evict a page we pick up one position past the last position (so as to not unfairly evict unused pages early in the “clock”)
What is the “Clock” LRU?
It is a simple and efficient LRU-like algorithm.
There is one bit of accessed information, set when loading a virtual address into the TLB.
Note: This tracks only if a page has been accessed AT ALL. It doesn’t track how many times after the first time it has been accessed.
What does it mean when the clock hand is turning slowly in Clock LRU?
Either there is little memory pressure (demand from processes) or we are making good decisions about which pages to evict
What does it mean when the clock hand is turning quickly in Clock LRU?
Either there is a lot of memory pressure (demand from processes) or we are making bad decisions about what to evict
What is the goal of the “copy-on-write” memory management technique?
Don’t allocate ANY additional memory during fork, but preserve private address spaces.
What are the 4 steps to implement the “copy-on-write” memory management technique?
- During fork, point all of the child’s PTEs to the same physical memory as the parent
- As long as the child and parent are both just reading from any shared page, we are OK (large parts of the address space may be read-only anyway)
- As soon as either the child or the parent modifies the contents of any shared virtual page, we have to make a private copy.
- How do we trap writes? Mark the page as read only in the TLB [?]
