22C:116, Lecture Notes, Lecture 13, Spring 2002

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Page Replacement with Multiple Address Spaces
  2. If a system has one address space per process, a new issue arises in selecting a page to replace: Do you do page replacement globally, for example, by replacing the least recently used page on a global scale, or do you pay attention to the relationship between pages and the processes that use them?

    Note that the working set is, in actuality, a property of the process or even the thread. One can speak of the global working set as the composite of all the process working sets, but (at least for single-threaded processes that share no data) the working set of each process is independent of the working set of the other processes.

    If page replacement is global, for example, using the LRU policy, a process that runs frequently will naturally claim more page frames than it really needs, while a process that runs infrequently will naturally lose page frames. As a result, even though the total physical memory available is larger than the sum of the working sets, the infrequent users of the CPU will be discriminated against in the sense that they will run at performance levels typical of a system starved for memory while the frequent CPU users see a memory surplus.

    Interactive users are good examples of infrequent CPU users. They want extremely fast response to keypresses and mouse clicks, but they spend long intervals staring at the screen and doing nothing (at least from the system's point of view). Background processes, things like computing the next digit of PI or computing the detailed shading on a frame of the next big special-effects movie, use all of the available CPU time, but they don't need to respond instantly when someone clicks on the mouse.

    The global working-set policy or the global clock policy, therefore, lead to a situation where mouse clicks or keypresses in an interactive process could well lead to a flurry of page faults, leaving the users angry and dissapointed at the system performance when there is a computationally intensive but non-interactive background process at work. This leads naturally to the desire to find page replacement policies that allow each process to keep its own working set in memory.

  3. WS Clock

    Given that clock replacement is the easiest to implement of the global page replacement policies, it is natural to seek a way to modify it to solve the problem outlined above. This is what led to the WS Clock page replacement policy.

    The WS Clock policy tries to keep the working set of each process in memory, in effect, running a separate clock replacement policy within the set of page frames allotted to each process. We can measure faults-per-second of CPU time for each process, and given this, we can say that the system is well balanced if all processes have the same fault rate under this measure. If a process has a higher rate than the others, that process needs more page frames. If a process has a lower rate than the others, it has more page frames than it needs. If the rates for all processes are unacceptably high, we should stop some process, perhaps the lowest-priority process on the system, and allocate its page frames to higher priority processes -- this will generally give finish all of the processes better than if we let all the processes begin to thrash.

  4. Swapping and Paging

    The original UNIX system used swapping so that multiple small processes could share a small main memory. Later but still early versions of UNIX divided slightly larger main memories into multiple regions, so that one process could run while another was being swapped in or out. On those UNIX systems, buying more main memory allowed more processes to be resident, and the swapper, itself a process, monitored the performance of the system and made sure that each ready process spent enough time in main memory to get a fair shot at the CPU.

    The first demand paged virtual memory versions of UNIX effectively abandoned the swapper, but this led to problems when the composite working set of the entire set of ready processes was too large for the number of available page frames. This was solved by new versions of the swapper that did not actually write processes out to disk, but rather, simply monitored the page fault rate, and if it got too high, blocked a low priority process so that the page replacement policy could reclaim its page frames and allocate them to higher priority processes.

    With the advent of page replacement policies like WSClock, this model of swapper function had to be modified, but the swapper remains a useful system process in today's UNIX systems.

  5. Shared Pages

    So long as pages are private to each process, policies like WSClock pose no special problem. New problems arise, however, when some pages are shared between processes while others are private. The problem is, the simple WSClock policy requires that each page frame be allocated to a process, but if the page it holds is shared, there is no obvious answer to the question "what process owns this page".

    Furthermore, if a page is shared between two address spaces, there is the problem of what to store in the frame table! In effect, the frame table needs to contain an open-ended list of all address spaces that hold the associated page, and for each address space, what virtual address that page has in that address space. Remember, the mechanisms we have discussed don't necessarily require that a shared page have the same virtual address in each space that shares that page!

    Many of these questions are easier to deal with if we focus not on pages but on segments. We can reasonably modify the WSclock policy so that it allocates page frames to segments and tracks the fault-rate per CPU second for each segment; when the segment active, attached to a running process's address space, it accumulates CPU seconds.

    Under this model, the unit of sharing is the segment, not the page, and therefore, the frame-table entry must merely report which segment each frame is currently allocated to and what page in that segment it holds. Under this model, the system must maintain a record, for each segment, of which address spaces contain that segment and what virtual address it has in that address space. Because there are many fewer segments than pages, we can generally afford the overhead of such record keeping.

  6. Power Management

    Power management systems pose new problems because, during extended periods of no page faults or other I/O, the disk subsystem may shut down the power to the disk. The result can be a dismayingly long page fault service time because the first page fault after such a long wait can require the disk to spin up to speed. It may take only a few milliseconds to service a page fault when the disk is already spinning, but starting a disk may take several seconds!

    In addition, since around 1970, many CPUs have included features allowing the CPU itself to power down when it is idle. Typically, this is done with an instruction called something like await interrupt that stops the CPU clock until an interrupt request. Typical logic circuitry consumes maximum power only when logic levels change from 0 to 1 or 1 to 0; when all values are constant, the power drain goes way down. This was as important for conserving battery power in UPS systems of the early 1970's as it is for conserving battery power in today's laptops and PDAs.

    The classical idle process looks something like this:

    	repeat
    	    relinquish
    	forever
    
    Given an await interrupt instruction we can modify the idle process as follows:
    	repeat
    	    if ready-list empty, await interrupt
    	    relinquish
    	forever
    
    As a result, when there is nothing to do, the scheduler transfers control to the idle process and it turns off the CPU until the next interrupt request. Each end-of-timeslice interrupt will wake it up briefly, but the important thing is that when an interrupt signals the completion of an I/O operation, the interrupt service routine will typically signal some application process that was waiting for that interrupt, making that application process ready so the ready list is no longer empty.

    Some storage managers have other uses for the ready process; for example, the ready process can constantly sweep through the list of idle page frames, running memory diagnostics on them and removing from use any frames that fail the diagnostic. In this case, we might extend the logic as follows:

    	repeat
    	    do a fixed small increment of housekeeping work
    	    if ready-list empty, await interrupt
    	    relinquish
    	forever