22C:116, Lecture Notes, Sept. 8, 1995

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Page Faults

    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?

    What page in main memory should be replaced?

  2. LRU Replacement

    The best practical page replacement policy is to replace the Least Recently Used page, that is, the page which has not been referenced by the CPU 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.

    Demand paged virtual memory works, that is, it offers performance comparable to main memory performance, at a price comparable to secondary memory prices because programs exhibit what is called a working set. The working set of a program is the set of pages it needs, at some instant, to make progress. 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 paging.

    In practice, most programs exhibit a well defined working set that changes only slowly with time. That is, they exhibit strong locality of reference, making repeated references to the same pages holding the program's code and variables.

    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 sequential algorithm was used by the address translation unit, implemented in fast hardware:

       I = 0
       Fetch entry(I) into temp
       while I < cache_size
       and temp.page /= virtual_address.page do
         I = I + 1;
         exchange temp with entry(I)
       endloop
       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
         Copy the map entry from main memory into cache entry(0).
    
    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.

  3. Clock page replacement

    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).

    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.

  4. Modified Clock Replacement

    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".

  5. Dirty Pages

    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.