Page Replacement
Hardware-Managed TLBs
-
On certain (common) architectures the MMU will search the page table itself to locate virtual-to-physical address translations missing from the TLB.
-
Pro: hardware is faster!
-
Con: operating system must set up the page tables in a fixed way that the hardware understands.
-
-
With a hardware-managed TLB, the kernel never sees TLB faults: they are handled in hardware.
-
Don’t worry: System/161 has a software-managed TLB, so you get to do all of the hard work and design your own page table structures!
Page Eviction
In order to swap out a page we need to choose which page to move to disk.
In order to swap in a page we might need to choose which page to swap out.
-
Cost:
-
Benefit:
Page Eviction FAIL: Thrashing
Thrashing is a colloquialism normally used to describe a computer whose virtual memory subsystem is in a constant state of paging, rapidly exchanging data in memory for data on disk, to the exclusion of most application-level processing. This causes the performance of the computer to degrade or collapse.
Maximizing Benefit
Benefit: the use of 4K of memory as long as the page on disk remains unused.
-
Pick the page to evict that will remain unused the longest!
The Best Bet
-
A page that will never be used again!
Break Out the Ball
Think back to scheduling algorithms. (This is a bit simpler.)
-
How long will it be before this page is used again?
The Past Didn’t Go Anywhere
-
determining what information to track,
-
figuring out how to collect that information, and
-
how to store it.
There Be Tradeoffs
-
Collecting statistics may be 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.
Simplest
-
Random.
-
Extremely simple.
-
Good baseline for algorithms that try to be smarter.
-
Too simple. We can probably do better.
Use The Past, Luke
-
Least Recently Used (LRU):
-
Choose the page that has not been used for the longest period of time.
-
Hopefully this is a page that will not be used again for a while.
-
Might be as good as we can do without predicting the future.
-
How do we tell how long it has been since a page has been accessed?
-
How do we store how long it has been since a page has been accessed?
LRU: Collecting Statistics
-
When we load the entry into the TLB!
-
No! Only the first. A page that is accessed once and one that is accessed 1,000 times are indistinguishable.
-
Too slow!
LRU: Storing Statistics
-
32 bits = 232 "ticks", but doubles the page table entry size!
-
8 bits = 256 "ticks".
-
Need some kind of efficient data structure holding all physical pages on the system that is searched on every page eviction.
Clock LRU
-
Simple and efficient LRU-like algorithm.
-
One bit of accessed information, set when loading a virtual address into the TLB.
-
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.
Clock Speed
-
Little memory pressure, or
-
We are making good decisions about what to evict.
-
Lots of memory pressure, or
-
We are making bad decisions about what to evict.
Memory Management Design Exercise: Copy-on-Write
Remember the problem with fork
?
-
Have to copy the entire address space of the parent!
-
If the parent has N pages allocated, we have to find N more free pages!
-
…and then the child calls exec anyway.
-
Copy-on-Write
Goal: don’t allocate any additional memory during fork, but preserve private address spaces.
-
During fork, point all 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 or read-mostly 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?