When a program references a page that is marked in the page table as invalid, the memory management unit reports a page fault. This causes a page fault trap request to be reported to the CPU, aborting the execution of the current instruction and transferring control to the page-fault trap service routine.
This service routine faces two key choices; what page(s) should be copied into main memory from disk, and, assuming that main memory is full, what page(s) should be copied out from main memory to disk in order to make space.
What page should be copied into main memory?
* demand paged -- copy only the page that caused the fault * anticipatory paging -- try to guess other needed pages
What page in main memory should be replaced?
* FIFO -- as bad as random * LIFO -- really bad! * random -- not as bad as LIFO * LRU -- pretty good * CLOCK -- almost as good as LRU
FIFO or first-in first-out replacement is an obvious policy, where the page that has been in main memory the longest is the one replaced.
LIFO or last-in first-out replacement is an academic alternative, posed merely to illustrate that alternatives are available. It works very poorly because the page a program has most recently referenced is usually very likely to be referenced again in the near future.
There is actually an optimal but unimplementable replacement policy, called Belady's optimal algorithm. In this algorithm, the page replaced is the one that is will not be needed for the longest time into the future. Implementing this replacement policy requires a crystal ball or other means of predicting the future behavior of the program, but if it could be implemented, it can be proven to be optimal.
The best practical page replacement policy is to replace the Least Recently Used page, that is, the page which has not been referenced by any program for the longest time in the past.
This requires special hardware to track every memory access, for example, to put a timestamp on each page frame each time the page in that frame is referenced.
Short of using a fortune teller to predict the future, this is the best you can do!
Demand paged virtual memory works because programs exhibit what is called a working set. The working set of a program is the set of pages it needs frequent access to. If enough page frames are available to store the working set, the program will execute almost as quickly as it would if it was executing out of main memory with no virtual memory.
This assumes that the page replacement algorithm keeps the working set in main memory and only replaces pages that are not part of the current working set. Belady's optimal page replacement algorithm does this by looking into the future and replacing the page that will not be needed for the longest time into the future. This is hard to implement.
LRU is optimal among practical algorithms, although in some contexts, some anticipatory paging will improve things a little bit.
MULTICS on the GE 600 used true LRU replacement.
A cache of all currently available page frames was stored in a special high speed core memory, used to implement a cache. The Following algorithm was used:
I = 0
Fetch entry(I) into temp
while temp.page = virtual_address.page do
I = I + 1;
exchange temp with entry(I) -- in one read-modify-write cycle
until I = maximum
if temp.page = virtual_address.page
Store temp into entry(0)
else
Report a page fault for virtual_address.page
Report that temp.frame is the least recently used page frame
This keeps the entries in the cache ordered by recency of use.
This ordering guarantees that the cache will be fast for references
to recently used frames (those that are likely to be frequently used)
while it is slow for frames that weren't recently used (those that
are unlikely to be frequently used).
The MULTICS scheme is an elegant historical curiosity, of only limited practical value today because it is predicated on core memory technology.
The clock algorithm allows a good approximation of LRU replacement, although if there are two few page frames available, it degenerates to FIFO replacement.
Clock replacement requires that there be one bit per page frame to record whether that page has been recently referenced. This bit is set by hardware when the page frame is referenced, and it is reset by the page-fault service routine, in the process of deciding what page frame to replace.
To select a page frame to replace, the page fault service routine sweeps through the page frames, resetting the referenced bit on each page frame and stopping when it finds a page frame with this bit already reset. The page in this frame is the one that is replaced (copied out to disk to make an empty frame).
Aside: The clock algorithm is usually pictured with a clock face, where each minute on the clock face corresponds to a page frame. The clock hand remains fixed except during the execution of the page fault service routine. When a page fault occurs, the clock hand begins its sweep. The hand stops as soon as it sees an unmarked page frame. The clock hand removes the marks from each page frame it sweeps over.
It turns out that the clock algorithm can be modified to work without a hardware supported referenced bit.
As clock hand sweeps by a page frame, all page table entries referencing that frame are marked as invalid. In fact, the page is still in memory, but the memory management unit has been told that it is not there. This combination, page in memory but marked as if not, is used to mean "not referenced".
When the CPU references an invalid page, there is a page fault. If the page is actually in memory, this is called a soft page fault. The page table entry is simply changed from invalid to valid. This combination, page in memory and marked as being and marked as such, is considered to mean "referenced".
A dirty page is a page that has been modified since it was copied from disk to main memory. Dirty pages must be copied back to disk when the frames that hold them are preempted to hold other pages. Clean pages, those that are not dirty, need not be copied back to disk if original copy of the page on disk is still available. This can cut the time needed to service some page faults in half.
Tracking clean and dirty pages requires one bit per page frame; typically, we assume that this bit is set to mark the page as dirty whenever there is a write operation on that page, and we let the software reset this bit whenever it writes the contents of a page frame to disk. The latter operation is called cleaning the page frame.
This can be combined with the clock algorithm as follows:
As the clock hand sweeps by dirty page frames they are scheduled for cleaning; the actual write operations to disk take place in parallel with computation and are typically done in whatever order is convenient for the disk interface hardware and software.
The clock hand only stops its sweep when it encounters a page frame that is both unreferenced and clean.
This scheme (modified clock replacement) is typical of modern virtual memory operating systems. This scheme requires minimal hardware support and yet delivers performance comparable to LRU replacement.
If the computer does not include hardware to record the fact that a page is dirty, this may be done by software by marking clean pages as read-only. When a write operation is made to a read-only page, the resulting soft page fault marks the page as read-write, which is interpreted to mean that it is a dirty page.
Some implementations of such schemes are enhanced with anticipatory paging -- for example, when there is a page fault for page i, they might bring in pages i, i+1 and i+2. This assumes that a program that references page i is highly likely to use the following pages. Since this assumption is not always a good one, such systems usually provide a way to turn off the anticipation logic in the page replacement algorithm.