Lecture notes for 22C:116 Introduction to System Software, by Douglas W. Jones, University of Iowa Department of Computer Science
Most computer users take the main memory resources of computers for granted, assuming that they are completely implemented by hardware and thus, aside from the problem of storage allocation, not an object dealt with by system software. This is indeed the case for small computer systems, but not for many large systems. The reason is that very large high speed memories are expensive, so there is great economic pressure on system designers to use a small high speed memory and a large low speed memory where users expect a single high speed memory. This memory hierarchy frequently extends to more than two levels, for example, there might be a few thousand bytes of very high speed cache memory between the CPU and main memory; the main or primary memory itself may consist of a few megabytes of medium performance memory, and this might be backed up by hundreds of megabytes of secondary or backing storage implemented on a disk drive.
The interface between a cache memory and main memory is almost always managed by hardware, but the interface between main memory and backing storage is usually largely in software. On early systems, this interface was under user program control; when a program needed data or code, that program was responsible for bringing it into main memory. The problems of overlay management which result from this have consumed a tremendous amount of programmer effort and have motivated the development of complex software tools such as the overlay linkers discussed in Chapter 7. None of these solutions has been entirely successful, and in the early 1960's, an alternative was developed: virtual memory.
In a virtual memory system, the burden of overlay management is moved from the programmer to the operating system and the hardware, working in cooperation. When a program requests the use of an object which is not currently in main memory, the system is automatically informed by the hardware so that it can bring the needed object into main memory. The user program sees no difference between an access to a word of data which was previously in main memory and one which had to be moved from secondary memory except a difference in access time. Since most programs exhibit good locality of reference, most memory accesses will be fast, and the average speed of execution of a program will be near that which the program would attain if all of the memory were fast memory.
In addition to the sizes of the primary and secondary memory devices, three key questions must be answered to obtain a complete description of any virtual memory system. The first of these is: What are the units of transfer between main memory and the backing storage device? This has two common answers, pages, or fixed size blocks of information, and segments, or variable sized blocks. Typically, the page size used in a virtual memory system is a small multiple of the sector size of the backing storage device. When segments are used, each segment is typically a logical unit such as the code for a procedure, or a particular data object.
The second question is: What causes a transfer from backing storage to main memory? Demand transfers are those which are initiated by an attempt of a program to access a page or segment which is not currently in main memory, while anticipatory transfers are those made by the system in anticipation of a user demand. Some systems also allow a user program to request a transfer in anticipation of a specific later need.
The final question is: What policy is used to select objects in main memory which are to be moved back to the backing store when the space they occupy is needed for other pages or segments? There are a number of replacement policies, ranging from random replacement to least-recently used replacement. The choice of an appropriate replacement policy is one of the key variables determining the performance of a virtual memory system, since the premature replacement of a page or segment which is still being used can significantly slow the system.
The hardware being used largely determines whether a virtual memory system uses paging or segmenting, and indeed, whether a particular computer system can be used to implement virtual memory at all. If virtual memory is to be used, the hardware must provide some facilities for translating virtual addresses, as issued by a user program, to physical addresses, as used to access actual words or bytes in the main memory. This address translation hardware is responsible for detecting attempts by a program to access objects which are currently on secondary memory, and it isolates programs from any knowledge of the physical addresses actually being used to store objects in main memory. In this latter role, virtual memory hardware can be thought of as performing a run-time relocation function.
When segmented memory is used, each memory address issued by the user program must consist of the identity of a segment and the offset of the desired item within that segment, as shown in Figure 13.1.
segment number address within segment ____________ ____________________ |____________| |____________________|Figure 13.1. A segmented virtual address.
For example, on the Intel 80286 (and to a lesser extent, the Intel 8086), each memory reference is identified by the hardware as being addressed to either the current code segment, the current stack segment, or one of two additional segments known as the extra segments. Each segment may be from 0 to 64k bytes long, and each is described by a base register and a limit register. All later processors in the Intel 80x86 family support this addressing model, but this addressing model is rarely used on more recent family members.
On the 80286, all instruction fetches are from the instruction segment, and all operand references are, by default, from the stack segment. There is a special form of every memory reference instruction to override this default and explicitly control what segment is used for the operand. There are additional instructions for loading these base and limit registers; in protectec mode, these instructions load the base and limit registers from a 'segment description segment', the processor base segment, which lists all of the segments a program may currently access. A virtual memory system on this machine would quite naturally transfer data between primary and secondary memory in units of one segment.
When paged memory is used, each memory address issued by the user program is typically interpreted as a single integer by that program, but the hardware breaks the address into two fields. The most significant field is the page number, while the least significant field is the word (or byte) number within that page, as is shown in Figure 13.2.
address --- user view _______________________________ |___________|___________________| page number address within page --- system viewFigure 13.2. A paged virtual address.
For example, a 16 bit virtual address may be broken into an 8 bit page number, selecting one of 256 addressable pages, and an 8 bit specification of the byte desired from that page. Unlike segments, pages are all the same size, and user data and program structures are usually placed in memory without regard to how those structures are broken up into pages.
Independently of whether paged or segmented memory is used, it is conventional to refer to pages and segments as components of the user's address space, as opposed to referring to them as units of storage in memory or on disk. Thus, a particular page or segment may reside in main memory at some times and on disk at other times. The place where the segment is stored does not change its identity, and the segment may be moved from one place to another many times during the execution of a program.
When the virtual address space is broken up into pages, the term page frames or just frames is conventionally used to refer to the areas in main memory which may hold pages, and the term may also be used to refer to locations in secondary memory (disk) that hold pages, particularly if the page size is not one sector, and if pages may move from one disk address to another during the life of a program.
When a user attempts to address a page or segment which is not currently in some frame in main memory, that event is called a page fault. The term segment fault can be defined similarly, but there is nothing corresponding to a 'segment frame' because there is no standard segment size.
Most modern systems combine paging and segmenting; thus, each segment consists of one or more pages. This is a particularly useful when the maximum size of a segment is such that bringing an entire segment into main memory would be difficult. A second advantage of this is that it eliminates the need to allocate variable sized blocks of main memory to hold entire segments. When paging and segmenting are combined, the virtual address issued by a user program consists of a segment number and an integer offset within that segment, and the system interprets the offset as consisting of two fields, the first giving the page number within that segment, and the second giving the desired word in that page, as shown in Figure 13.3.
segment number address within segment --- user view ____________ _______________________________ |____________| |___________|___________________| segment number page number address within page --- system view or address --- user view ___________________________________________________ |_______________|_______________|___________________| segment number page number address within page --- system viewFigure 13.3. Paged, segmented virtual addresses.
The Intel 80386 and higher numbered processors (including all Pentiums) take this view, as do the Motorola 68030 and up, and most RISC processors, including the IBM/Apple Power PC, the HP PA-RISC and the SGI MIPS families of processors. In all these machines, addresses used by the user program are 32 or more bits, and are broken into 3 fields, as illustrated in the second example above. Some operating systems on these machines use segments to hold logical objects such as major parts of the program, while others allow users to ignore the hardware segment boundaries and treat the entire address as an integer.
Operating systems that support virtual addressing rely on the services of a hardware component called the memory management unit or MMU. The memory management unit sits logically between the CPU and the main memory. For some computers, the memory management unit is an optional component, while for others, including most modern microprocessors, the memory management unit is seen by the user as being part of the CPU, but however it is packaged, the memory management unit takes, as input, the virtual addresses issues by the program and produces, as output, the physical addresses used by the memory. This is illustrated in Figure 13.4.
____________ ________ | | | | | Central |<=====================================>| | | processing | ____________ | Memory | | Unit |===========>| |============>| | |____________| virtual | Memory | physical |________| address | Management | address | Unit | |____________|Figure 13.4. The memory management unit, in context.
When a user program issues a virtual address in a paged system, the memory management unit hardware must signal a page fault if the desired page is not in main memory, and the memory management unit must find the appropriate physical address if the page is in main memory. There are two approaches to this, one centered on the use of a page table, and one centered on the use of a frame table. A page table is an array, indexed by the page number field of a virtual address, which has entries for each page indicating where that page is currently stored. A frame table is an array, indexed by frame number, indicating which page is currently stored in each frame. In fact, most operating systems that use paged virtual memory have both tables, but the memory management unit hardware only needs to know about one or the other to do the address translation job.
The use of a page table is illustrated in Figure 13.5.
virtual address -- from CPU ___________________________ |___________|_______________| page number address in page | |___________________ | | | __________________ | | |_____|____________| | index | |_____|__ __| | into | |_____|__ page __| | table --->|_____|__ table __| | |_____|____________| | |_____|____________| | valid address | | | | | ____________________________ | |____________|_______________| To CPU <------ frame number address in page physical address -- to memoryFigure 13.5. The use of a page table.
As shown, the page number field of the virtual address is used as an index into the page table. Each page table entry has at least one bit indicating whether that entry refers to a page in main memory or to one in secondary memory; if the page is in main memory, the hardware considers a reference to that page to be valid; if not, it is an invalid address and the operating system must be informed. The remainder of the page table entry for a valid page is the frame number where that page is stored; for invalid pages, the software may use this field for something else, perhaps the disk address of the page.
If the virtual address space of a user program is small, for example, 256 pages, the entire page table may be held in special registers within the central processor. If the virtual address space is large, the page table must be held in main memory, in which case, there is typically a page-table-base register in memory management unit. When the page table is stored in main memory, it would appear that each memory access made by a user program would require an extra access to fetch the required page table entry, but most paging systems avoid most of these extra accesses by using a special cache memory inside the memory management unit to store the most recently used page table entries.
On most modern systems the page table itself can grow too large to fit conveniently in main memory. Some systems have overcome this problem by using combined paging and segmenting, so that only the page tables for recently used segments need be in memory at one time. Another approach is possible! The Digital Equipment Corproation (now part of Compaq) VAX family of computers, built between the mid 1970's and the early 1990's, stored the page table in the virtual address space; as a result, only the recently used pages of the page table would typically appear in main memory, whilt the remainder of the table would be stored on disk. Of course, this means that the VAX memory management unit may have to report an error in translating the address of the page holding the address of the page requested by the central processor, which complicates the picture.
The use of a frame table is illustrated in Figure 13.6.
virtual address -- from CPU ___________________________ |___________|_______________| page number address in page | |______________ | | page number | ___________ --- | |___________| | | |__ __| |----- search | |__ frame __| | | | |__ table __| --- | | |___________| | | |___________| | | miss ______|_____________|_______ | | | | | ---------------------------- | frame number address in page <--- to CPU physical address -- to memoryFigure 13.6. The use of a frame table.
If a frame table is used, the page number field of the virtual address must be compared with each entry in the table to determine which frame holds the desired page. If there is no match, the address is invalid and the operating system must be informed. If there is a match, the index of the table entry which matched is used as the frame number in constructing the physical address. The requirement that the frame table be searched with each memory reference may sound very expensive, but the frame table is usually stored in an associative memory, a special high speed memory that allows this search to be carried out in parallel, and as a result, it can be very fast!
When a valid physical address is found as a result of virtual address translation, the instruction execution cycle continues as it would for a simple machine with no virtual addressing; ideally, the memory management unit is so fast that the CPU operates at the same speed it would have had there been no virtual memory mechanism. If the virtual address is determined to be invalid, on the other hand, the execution of the current instruction must be terminated and the operating system must be informed. This is called a page fault.
The transfer of control from the user program to the system when a page fault is called a page fault trap. In general, traps are similar to interrupts, control is transferred from the program that was running to a trap service routine which is very similar to an interrupt service routine, and when the trap service routine is done, it may return to the program that was running. There are two primary differences between traps and interrupts. First, interrupts are caused asynchronous events such as the completion of an input output operation, while traps are a direct consequence of the execution of instructions on the processor. Second, if an interrupt is requested while the processor is in the middle of executing an instruction, the processor completes that instruction before it services the interrupt. On the other hand, if a trap is requested while the processor is in the middle of executing an instruction, the processor aborts that instruction and services the trap immediately.
If a system is to support demand paging, the invalid address trap service routine must update the page and frame tables after moving the desired page into main memory. After doing so, it must return to the program which caused the page fault in such a way that that program is able to continue the execution of the instruction which caused the page fault. The above description requires that the hardware possess two key properties: First, the service routine must be able to find the address referenced by the user that caused the page fault, and second, it must be possible to continue the execution of the user program after a return from the service routine.
Ideally, the hardware should load the virtual address which caused a page fault into a special register or memory location so that the trap service routine has immediate access to it. Many virtual memory systems have been constructed with much less convenient hardware, for example, some provide only values of all of the user's registers at the time of the trap. On such systems, the trap service routine must simulate the execution of the instruction which caused the trap in order to determine which memory addresses were issued by that instruction, and then test each of them to see if it would cause a page fault trap.
There are a number of ways that hardware can be built so that the execution of the user program can be continued after the cause of the page fault has been corrected. The approach most convenient for the software would involve having the CPU store all of its internal state information when a trap occurs; this would allow each instruction to be interrupted at any point and then resumed. In fact, this would require very expensive hardware, so most systems require that the instruction which was executing at the time of the trap be restarted after the trap has been serviced. As long as the instructions have no side effects prior to the occurence of a page fault, this approach leads to both simple hardware and software.
On most machines which support virtual memory, the instruction set is carefully designed so that the validity of all addresses issued by an instruction can be tested before the instruction has any side effects. There are exceptions to this; for example, on the Digital Equipment Corporation PDP-11/45, a segmented machine introduced in the mid 1970's, many instructions could increment or decrement up to two registers prior to the time a segment fault is detected. On this machine, special auxiliary registers were added to record which registers in the CPU were incremented by the current instruction, and by how much, prior to the fault. As a result, the trap service routine could undo any side-effects of the instruction prior to restarting it.
A significant number of machines have been constructed which have virtual address translation hardware but which do not have instruction sets which allow demand paging. On these machines, an invalid address trap cannot be interpreted as an indication of a page fault because there is no way to restart the instruction which caused the trap. The virtual address translation hardware is still useful for two reasons: First, although demand paging has been ruled out, the operating system may still allow programs to explicitly request that pages of their address space be moved in and out of main memory. Second, the use of virtual address translation can allow each user program to run in its own virtual address space, thus making unintended communication between user programs impossible and greatly enhancing system security.
In order to illustrate the construction of a page fault trap service routine, some assumptions must be made about the hardware. These involve such things as how virtual addresses are translated, what needs to be done to restart the instruction which caused the trap, and how disk input/output is done when the contents of a frame must be copied to or from disk. Additional assumptions must be made about how the software uses the disk for backing storage. These issues are discussed in the following paragraphs.
The example presented here will assume that the hardware for virtual address translation is based on a page table, as shown in Figure 13.5, where the table is stored in main memory at the address contained in a special page table base register within the memory management unit. As with the example peripheral device interface registers used in previous chapters, the page table base register will be assumed to be accessible using the inp and outp functions; this is typical of machines where the memory management unit is an optional device that was designed independently of the central processor.
The example will assume that the virtual address translation hardware maintains a register which always holds the most recent virtual address which caused a page fault trap. As a result, the page fault service routine need not try to simulate the instruction which caused the trap in order to find this address.
This example will assume that all instructions are restartable; that is, that no instruction has any side effects until all virtual addresses issued by that instruction have been translated to physical addresses. As a result, the page fault service routine need not try to undo any side effects before returning to retry the instruction which caused the trap. It will be assumed that a simple return from trap will restart the instruction in question; that is, the program counter passed to the trap service routine points to the instruction which caused the trap, and has not yet been incremented.
Finally, it will be assumed that all disk input/output requests use virtual addresses to specify the buffers being used. This complicates the disk interface, either at the hardware or low-level software level, but it simplifies our job in this section. Our virtual memory software will never attempt a disk transfer to or from a virtual address that is not currently in main memory.
As mentioned above, some assumption must be made about how virtual addresses are associated with disk addresses. The assumption which will be used here is that the virtual address space is mapped to a single disk file; as a result, each page of the virtual address space can be stored on one sector of that disk file, and the DISKREAD and DISKWRITE routines given in Figures 12.3 can be used for moving pages to and from disk.
One final issue must be addressed before a complete example can be presented: Where is the page fault trap service routine stored if all of memory is virtual? Certainly, the page fault trap service routine cannot be allowed to be copied out to disk! One solution to this problem is to permanently store the first few pages of the virtual address space in the first few frames, so that none of the interrupt service routines will ever be moved to disk. An alternate solution to this problem is to introduce two modes of central processor operation, one mode in which virtual address translation is turned on, and one mode in which it is turned off so that programs may directly access main memory; in this case, user programs run with virtual address translation turned on, but system programs such as the page fault service routine, input/output drivers, and other service routines run with virtual address translation turned off. The example page fault service routine presented here will assume the first solution.
The data structures which the example page fault service routine requires are shown in Figure 13.7.
const bytesperpage = ... { number of bytes per page }; maxpage = ... { highest page number in virtual address space }; maxframe = ... { highest frame number in main memory }; PAGETABLEBASE = ... { input/output register in MMU } TRAPADDRESS = ... { input/output register in MMU } type pagenumber = 0..maxpage; framenumber = 0..maxframe; var pagetable: array [pagenumber] of record frame: framenumber { what frame is this page in }; valid: boolean { true if page in main memory }; . . { other fields may be needed } . end; frametable: array [framenumber] of record page: pagenumber { what page is in this frame }; used: boolean { true if a page is in this frame }; . . { other fields may be needed } . end; pagefile: opendiskfile;Figure 13.7. Data structures for page fault management.
Initially, the page table base register is set to point to the page table, the page table is initialized so that its first few locations refer to the frames occupied by the operating system, and the remainder are initialized to invalid, indicating that the desired pages are currently on disk. The frame table is initialized to indicate which frames hold pages of the operating system, and the remainder are marked as unused. The frame table is, in a sense, redundant, since it can be reconstructed from the page table, but it is convenient to keep both data structures.
The page fault trap service routine that operates with the data structures from Figure 13.7 will typically be structured as follows:
procedure pagefaultservice; var trapaddress: integer; page: pagenumber; frame: framenumber; done: integer; begin { first, get the address of the instruction that caused the trap } trapaddress = inp(TRAPADDRESS); page := trapaddress div bytesperpage; { second, find a free frame } frame := findframe; { third, adjust the page table and frame table } pagetable[ page ].frame := frame; pagetable[ page ].valid := true; frametable[ frame ].page := page; frametable[ frame ].used := true; { copy the page from disk } DISKREAD( pagefile, makeaddress(page * bytesperpage), bytesperpage, page, done ); waitdiskdone( done ); { return to the user } end { pagefaultservice };Figure 13.8. A page fault service routine.
The findframe function in the code in Figure 13.8 searches the frame table for an idle frame; if such a frame is unavailable, it forces some page out to disk to create an idle frame. This code assumes that the makepointer function takes an integer representing a memory address and converts it to a pointer to that address, overriding the strict typechecking of Pascal.
The findframe function used in the page fault service routine shown in Figure 13.8 may occasionally find an idle frame, but it will usually have to force some other page out of main memory in order to make an idle frame. The particular policy used to decide which page to force out is called the page replacement policy. The selection of an appropriate page replacement policy can have a tremendous impact on the performance of a virtual memory system. For example, if the page which is forced out is one of the pages referenced by the instruction which caused the fault, there will be an immediate page fault when that instruction is restarted.
The optimal page replacement policy, developed by Laszlo Belady in the late 1960's, is to order the pages according to when they will be needed in the future, and replace that page which will be needed at the most distant future time. Unfortunately, Belady's optimal page replacement policy cannot be implemented without knowing the complete future history of the program which caused the fault. Since the only way to accurately predict the future is to wait until it is present, the only way to compute the future history of a program is to run it! As a result, the optimum sequence of page replacements can only be determined in retrospect. The fact that there is an optimal but impractical policy is useful because it allows more realistic policies to be judged in terms of how close to the optimum they come. We can run a program and collect the sequence of virtual addresses it references, compute how long the program would have taken to run using the optimal page replacement policy, and then compare this with actual run times under practical policies.
An eminently practical but somewhat stupid page replacement policy is to simply choose the page to be replaced at random. The random replacement policy makes no use of any knowledge of program performance, and can therefore be thought of as the worst policy that can be used without resorting to deliberately malicious policies. As such, the random policy also provides a useful benchmark for the judgement of other policies. Experimentally, random replacement has been shown to result in roughly three times as many page faults as Belady's optimal policy over a reasonable range of main memory sizes.
The first-in first-out page replacement policy is relatively easy to implement and has some intuitive appeal. In this policy, the page which has been in main memory the longest is selected for replacement. The intuitive appeal of this is that it seems fair, allowing all pages to stay in main memory for about the same amount of time, assuming page faults come at an approximately constant rate. Unfortunately, empirical tests of this policy have shown that it is no better than random replacement. Apparently, the fact that a page has been in memory a long time is not a good predictor of future use of that page.
The least recently used page replacement policy is much better, being perhaps the best policy which does not rely on actual prediction of future program behavior. This policy is based on the observation that most programs exhibit significant temporal locality. That is, if a page has been recently used, it is highly likely that it will be used again, and if it has been a long time since a page has been used, it is unlikely that it will be needed again. Least recently used replacement requires that the hardware record, for each reference to a page, the time of that reference (or something equivalent to the time). When it comes time to replace a page, a search of all page frames is conducted in order to find the frame holding the least recently used page. Although systems have been built which used this policy, the hardware required to record the time of last use is expensive, so most practical systems use some approximation. Empirical results suggest that least recently used replacement leads to no more than twice the number of page faults which would result from Belady's optimal policy over a wide range of practical memory sizes.
The clock replacement policy is a widely used example of an approximation of the least recently used policy. In this case, hardware is required to record references to each page, but only one bit is needed per page, the mark bit. When a page is used, the memory management unit sets the marked bit for that page in the page table; it is up to software to reset this bit. If the software periodically resets the bit, then those pages with the marked bit set were used more recently than those with the bit reset. As a result, it is easy to select one of the less recently used pages for replacement, but the particular page which is least recently used cannot be determined.
The name of the clock policy comes from the particular scheme used to reset the referenced bit and search for a replacible page. As shown in Figure 13.9, the clock policy considers the frames to be organized in a circle, and uses a 'clock hand' to point to the most recently replaced page.
12 frames 11 _ 1 / | 10 / / (2) / /----------- clock hand 9 o/ (3) (moves clockwise) (8) 4 7 (5) Marked frames are 6 parenthesizedFigure 13.9. An abstract view of clock replacement on 12 frames.
When a page fault occurs, the clock hand sweeps around the list of frames until it encounters a frame that is not marked. This is one of the less recently used pages, so it is the one selected for replacement. As the clock hand passes over frames during its search for an unmarked page, it erases the marks on the frames it skips. Given the initial state shown in Figure 13.9, after one page fault, the clock hand will point to frame number 4 and the marks on frames numbered 2 and 3 will be reset.
The rate at which the clock algorithm resets mark bits depends on the frequency of page faults. If there are few faults, the clock hand moves slowly and pages must remain unreferenced for a long time before they are considered to be candidates for replacement. If there are many faults, the clock hand moves quickly and pages need only remain unreferenced for a short time before they are considered for replacement. Empirically, the clock policy performs only slightly worse than the basic least recently used policy, so it is an excellent choice in real systems.
A natural implementation of the clock policy requires that the hardware keep one bit per frame, thus implying that the clock policy should be easiest to implement on systems where a frame table is used by hardware for virtual address translation. In fact, it is almost as easy to have the hardware associate a bit with each page in a page table, as is shown in Figure 13.10.
var pagetable: array [pagenumber] of record frame: framenumber { what frame is this page in }; valid: boolean { true if page in main memory }; mark: boolean { set by hardware if page used }; . . . end; clockhand: framenumber { the clock hand }; function findframe: framenumber; begin { rotate clock hand to candidate frame } clockhand := (clockhand + 1) mod (maxframe + 1); while frametable[ clockhand ].used and pagetable[ frametable[ clockhand ].page ].mark do begin pagetable[ frametable[ clockhand ].page ].mark := false; clockhand := (clockhand + 1) mod (maxframe + 1); end { while }; { hand now points to the frame which will be used } if frametable[ clockhand ].used then begin DISKWRITE( pagefile, makeaddress( frametable[ clockhand ].page * bytesperpage ), bytesperpage, page, done ); pagetable[ frametable[ clockhand ].valid := false; frametable[ clockhand ].used := false; end; { return the frame } findframe := clockhand; end { findframe };Figure 13.10. Code for the clock page replacement policy.
Note that the declaration of pagetable in Figure 13.10 is a modification of that given in Figure 13.7, and that the findframe function shown here is called from Figure 13.8. This implementation of the clock policy is typical of modern virtual memory implementations.
Empirical analysis of the behavior of programs in a virtual memory environment has shown that most programs have, at any time, what is called a working set of pages. Pages in the working set are frequently referenced, while pages outside the working set are not referenced at all. Intuitively, the working set holds the currently relevant procedures, the local data for those procedures, and any global data structures being manipulated by those procedures. Over time, the working set of a program may change, either gradually or abruptly. For example, the working set of a program which is slowly computing its way through an array will gradually change as the program advances from one page to the next of the array, but when the program finishes the computation there is likely to be an abrupt change in the working set as the program begins the next phase of its computation.
If the number of frames available to a program is smaller than the working set of that program, there will be a very high number of page faults and not much computation will be done. When this happens, the system is said to be thrashing. Where thrashing is a problem, it is quite common for immense performance improvements to result from the addition of very small amounts of main memory. If the number of frames available to a program is larger than its working set, the number of page faults depends primarily on the rate at which the working set changes and has little to do with the number of available frames. The number of page faults only falls to zero when the entire memory used by the program fits in main memory. In general, adding more memory to a system which is not thrashing will not have much impact on performance, and the price/performance ratio for a virtual memory system is typically minimized by buying just enough memory to avoid thrashing, but no more.
It should be noted that when a program is thrashing, some computation is still being done; the program is making progress, but memory behaves as if it is much slower than main memory. If the number of frames is below a certain threshold, however, no progress can be made at all! This absolute lower limit on the number of frames is determined by the number of different pages that a single instruction can reference. Traditional single operand machine instructions and modern RISC machine instructions require at least two page frames, one to hold the page from which the instruction is fetched, and one to hold the page to or from which the operand is transferred.
For complex instruction set machines, where instructions may span word boundaries and one instruction may address n distinct memory addresses, each of which may span a word boundary, single instructions may reference 2(n+1) pages. On the old DEC PDP-11 or the very similar Motorola 680x0 families, this means one instruction can touch as many as 10 pages (in both cases, the worst case is an indirect memory to memory move). Machines like the Intel Pentium may require even larger minimum numbers of frames for certain rarely used instructions.
The graph shown in Figure 13.11 summarizes the above observations about the performance of a virtual memory system as a function of the number of pages available for a typical program.
| infinite | | number of | | page faults | \ to complete | \_ program | \__ | \_______ | ---------_________ +------+-------+------------------------+- a b number of available frames a = maximum number of pages referenced by some instruction b = working set size c = total memory used by programFigure 13.11. Performance of a virtual memory system.
The concept of the working set of a program is strongly related to the concept of locality of reference. Programs with a great degree of locality have well defined working sets, while those which exhibit poor locality have no well defined working sets. An ideal page replacement policy should identify the working set of a program and keep that in main memory.
One approach to actually using the concept of working set in designing
a page replacement policy is to (somewhat arbitrarily) decide that any
page referenced fewer than t time units before a page fault is in the
working set, while any page referenced before that is a candidate
for replacement. As with pure LRU, this would require that there be
a record of the time of reference of each page, but it can be approximated
using the same hardware used for clock replacement. For example, if
a 'frame tracking' procedure is run every t/a
this can manage an age field associated with each frame.
The frame tracking procedure can do this by inspecting and clearing
the used field on each frame. If the frame was used, the tracking
procedure sets the age field to zero; if not, it increments the age field.
When a page fault occurs, any frame with an age greater than
The working set replacement policy described above is more complex
than the clock policy, and if only a fixed number of frames are available,
it serves no useful purpose on a single user system. On multiple user systems,
however, the simple clock policy favors
programs which have large well defined working sets while it takes page
frames away from programs with ill defined or small working sets. A policy
which, in effect, allocates frames to programs in proportion to the
sizes of their observed working sets can lead to much better response times,
especially for optimal systems, which (as noted previously) are on the
verge of thrashing.
The virtual memory page replacement policies outlined in the previous
sections will sometimes copy pages back from main memory to disk even though
the contents of those pages have not changed since they were last copied into
main memory. This is clearly an unnecessary cost, and most virtual memory
systems avoid it by using additional hardware to record, for each page,
whether or not it has been modified since it was last copied into main
memory. This takes only one additional bit per frame table entry
or per page table entry (depending on which is used by the hardware).
A page which has been modified is usually referred to as a dirty page,
a page which has not been modified is usually referred to as a
clean page, and the bit which records the difference is referred to
as the clean/dirty bit.
The set of frames can be divided into five disjoint subsets,
those which are ...
On systems where the backing storage is
able to transfer multiple consecutive pages in a time only slightly longer
than the time to transfer one page, anticipatory paging becomes
a practical option.
In the common demand paging policy, only the page which was actually referenced
by the page fault is fetched. Anticipatory paging is based on the observation
that a reference to a particular page is frequently a good sign that the next
page in sequence will be referenced in the near future. This is especially
true if the page size is relatively small. When anticipatory paging is done,
the page which has been brought into memory in anticipation of future use
may indeed not be needed, so it is a prime candidate for replacement. This
is why this policy would be inappropriate if a new disk seek were required
for each page fetched, but quite appropriate if pages were stored in
consecutive sectors, so there is no latency penalty for
anticipatory page transfers.
The above approaches to anticipating the behavior of programs are
automatic and take no advantage of advice the programmer can provide
about the future behavior of programs. Some virtual memory systems
provide special system services by which the programmer can provide advice
to the system about the future behavior of the program. For example, the
system might provide a service which allows a program to initiate
anticipatory fetches for pages which, in the programmers estimate, will
be needed in the near future. Another possible advisory service might
allow the program to tell the system that some page, although dirty,
will not be used again, or that some recently used page is a good candidate
for replacement. These services can be used to speed the transition of a
program from one working set to another, but will typically be of little
use when a program is in its steady state.
Some systems allow user programs to give advice by two services, one which
indicates that the user program expects to exhibit poor locality,
and the other indicating that good locality is expected. Although this
kind of advice is quite vague, it can be quite useful on systems which
try to make extensive use of locality. For example, the anticipatory
policies mentioned here will improve performance for programs exhibiting
good locality, but they will probably actually lead to performance
degradation for programs with more nearly random behavior. In many cases,
it is possible for the programmer to predict the points during the
execution of a program where that program will change from one kind of
behavior to the other, and advise the system of this so that the system
can choose the more appropriate policies.
In any case, most users will not modify their programs to give the system
advice about the expected behavior of their code, so these advisory
services will not be commonly used. Nonetheless, on many systems, there
are a few heavily used programs where slight improvements can have a
significant impact on user satisfaction; for example, database managers
or text editors. If a system provides advisory services such as are
described here, such programs can frequently make good use of them.
Although the terms virtual memory and demand paging are considered to be
almost synonymous by many people, virtual memory can be used to serve
other purposes. As already noted, virtual address translation hardware
can be viewed as performing a run-time relocation function. This is
particularly useful on multi-user systems where additional security
is gained by giving each user a different virtual address space.
The presence of virtual address translation hardware which uses data structures
describing the address space of user programs provides an opportunity to
further enhance security and provide for a better debugging environment
by marking each page in the address space with access rights information.
Thus, pages or segments containing code can be marked as executable, those
containing constants can be marked as read-only,
and those containing variables can be marked as read-write.
Most modern virtual memory hardware enforces such restrictions, and most
operating systems on such systems will mark pages appropriately; as a
result, errors such as attempting to change the value of a constant or
execute a variable are detected immediately and prevented by the hardware.
If each program running on a multiple user system is given its own virtual
address space, as defined by a page table, it is natural to assume that
the actual pages referenced by different programs will be different. In fact,
this need not be the case! It is quite possible to have two different
page table entries which refer to the same actual page; as a result, it is
possible for one page to be shared by two or more different virtual address
spaces. This provides for the possibility of tightly controlled sharing of
information between programs on such a system.
Some virtual memory systems allow programs to request that a file
be used as backing storage for some range of pages in their address space.
This allows programs to treat a file which has been inserted in their
virtual address space as a large array; any access to that array is
equivalent to input/output on that file. This is sometimes called virtual
file input/output.
On the MULTICS operating system,
where the address space consists of many segments, each of which consists
of many pages, the only way to read or write a disk file was to insert that
file in the virtual address space as a segment. To load and run a program
on such a system, all that must be done is to
map the object file into the virtual address space and then jump to the
starting address!
It is tempting to think that demand paged virtual memory eliminates the
need to consider memory limitations in the design of applications programs,
but this is not the case. Different algorithms and different top-level
designs for large programs will result in different working set sizes,
different page fault rates, and as a result, significant differences in
performance. Since optimal systems have just enough memory to avoid
thrashing, careless program design which leads to large working sets
can lead to very bad performance.
As an example, consider the problem of writing a compiler. Before virtual
memory was available, most compilers were organized as a series of passes,
with intermediate files to hold the data produced by one pass before it is
read by the next. For example, the lexical analyzer might produce a file
of lexemes for consumption by the syntax analyzer.
The availability of large address spaces (whether
virtual or not) encourages an alternate design, in which the different
passes are combined and run concurrently, with data flowing between them
through procedure calls. For example, the syntax analyzer might call
the lexical analyzer each time it needs a lexeme.
With the multipass approach mentioned above, the working sets of each
pass can be quite small and an abrupt working set change occurs at the
end of each pass. On the other hand, there is a large amount of explicit
input/output used to communicate between passes. With the single pass
approach, there is no input/output needed to communicate between passes,
but the working set of the program is the combined working sets of all of
the passes! It is not hard to estimate typical numbers for the simple
example of lexical analysis: A typical lexeme description might occupy only
a few words, so many lexemes can be moved per disk access to the intermediate
file used in the multipass approach. A typical lexical analyzer will have
a working set consisting of
a few pages of memory (for the code) plus perhaps one page for the stack
frame and a few pages for recently referenced symbols in the symbol table.
Thus, it is possible that a single call to the lexical analyzer might
involve as many as ten page faults, while processing the same lexeme in a
multipass compiler would require only a fraction of one disk access.
The reader should be familiar with the following general terms after reading
this section.
a) the hardware used virtual addresses for buffers?
b) the hardware used physical addresses for buffers?
a) LOAD X -- a single word instruction, including the operand address?
b) MOVE A,B -- a 3 word instruction (opcode and 2 operand address words)?
c) ADDF A,B,C -- a 4 word instruction (opcode, 3 operand addresses), where
each operand is two words long?
a) Outline an experiment you could perform to determine the best value for
t on a particular system.
b) Could the page fault service routine dynamically adjust t so that it
is automatically optimized?
a) estimate the run-time of the above code assuming that it takes one page
fault to bring each procedure into memory.
b) for which of the above procedures would it be profitable to initiate
anticipatory paging or anticipatory replacement? Modify the above code by
including calls to "anticipate(x)" and "replace(x)" where these would lead
to a maximum performance improvement.
c) where should calls be inserted in the above code to indicate that it has
good locality, and where should the system be told it has bad locality?
Rewrite the code with additional calls to "good" and "bad" for this purpose.
There is a good discussion of page replacement policies in Section 5.2 of
A brief introduction to virtual memory is included in Section 2.3.3 of
The classic survey paper on virtual memory is still
one of the best technical surveys of the subject.
It is interesting to look back on the first system which used demand
paging. This was the ATLAS system designed at Manchester University in
England. A good source is
It should also be noted that, although the bulk of the research on page
replacement policies was done in the late 1960's and early 1970's, work
continues. A good example is
Another good example of recent work is
Enhancing the Performance of Virtual Memory
Other Uses of Virtual Memory
The Limits of Virtual Memory
Terminology
pages segments
demand paging anticipatory paging
page replacement policy virtual address translation
primary memory secondary memory
main memory backing storage
frames page faults
page tables frame tables
address translation traps instruction restart
random page replacement Belady's optimal replacement policy
first-in first-out replacement least recently used replacement
clock replacement working set replacement
locality of reference thrashing
clean pages dirty pages
separate address spaces shared pages
read-only pages virtual file input/output
Exercises
The times quoted in the comments above are the run times of each procedure
when there are no page faults.
If you know that the average latency of the disk system is about .02 seconds,
and you know that the average lifetime of an unreferenced page in main memory
before it is replaced is about 3 seconds,
a { known to take about .03 seconds };
b { known to take about 5 seconds };
c { known to take about .01 seconds };
d { known to take about .01 seconds };
e { known to take about 10 seconds };
Readings
The Logical Design of Operating Systems
by Alan C. Shaw's
(Prentice Hall, 1974)
Operating System Elements
by Peter Calingaert's
(Prentice Hall, 1982)
"Virtual Memory," by Peter Denning in
Computing Surveys,
volume 2, number 2 (Sept. 1970) pages 153-189.
This has been reprinted in Sections 6.2 and 6.3 of
Software Systems Principles
by Peter Freeman (SRA, 1975)
"The ATLAS Supervisor"
by Kilburn and Payne in the
Proceedings of the 1961 Eastern Joint Computer Conference,
AFIPS Conference Proceedings Volume 20, pages 279 to 294,
This was reprinted on pages 661-682 of
Programming Systems and Languages,
by Rosen, (McGraw Hill, 1967).
"Converting a Swap-Based System to do Paging in an Architecture Lacking
Page-Referenced Bits," by Babaoglu and Joy, in
Proceedings of the 8th Symposium on Operating System Principles
(ACM, 1979) pages 78 to 86.
The title of this paper describes much of what it covers, but the system
described there also does a large amount of anticipatory paging, and the
system described is Berkeley UNIX, BSD 4.2, an important system in the history
of UNIX.
"WSClock - A Simple and Effective Algorithm for Virtual Memory Management,"
by Carr and Hennessy, in
Proceedings of the 8th Symposium on Operating System Principles
(ACM, 1979) pages 87-95.
This paper describes a simple combination of the working set page replacement
policy with the clock policy.