In the preceding sections we have described in detail how paging works and have given a few of the fundamental page replacement algorithms and shown how to model them. But knowing the bare mechanics is not sufficient To design a system, you have to know a lot more to make it work well. It is like the difference between knowing how to move the rook, knight, bishop, and other pieces in chess, and being a good player. In the following sections, we will consider other problems that operating system designers must take into account carefully in order to get good performance from a paging system.

Local versus Global Allocation Policies

In the previous sections we have explained various algorithms for choosing a page to replace when a fault takes place. A main issue associated with this choice (which we have carefully swept under the rug until now) is how memory should be assigned among the competing runnable processes.

Consider Figure 1(a). In this figure, three processes, A, B, and C, make up the set of runnable processes. Assume A gets a page fault. Should the page replacement algorithm try to find the least recently used page considering only the six pages currently allocated to A, or should it consider all the pages in memory? If it looks only at A's pages, the page with the lowest age value is A5, so we get the situation of Figure 1(b).

However, if the page with the lowest age value is removed without regard to whose page it is, page B3 will be selected and we will get the situation of Figure 1(c). The algorithm of Figure 1(b) is said to be a local page replacement algorithm, whereas that of Figure 1(c) is said to be a global algorithm. Local algorithms effectively correspond to allocating every process a fixed fraction of the memory. Global algorithms dynamically assign page frames among the runnable processes. In this way the number of page frames allocated to each process varies in time.

Normally, global algorithms work better, particularly when the working set size can vary over the lifetime of a process. If a local algorithm is used and the working set grows, thrashing will result, even if there are plenty of free page frames. If the working set shrinks, local algorithms waste memory. If a global algorithm is used, the system must continually decide how many page frames to allocate to each process. One way is to monitor the working set size as indicated by

Local versus global page replacement.

the aging bits, but this approach does not necessarily prevent thrashing. The working set may change size in microseconds, on the other hand the aging bits are a crude measure spread over a number of clock ticks.

Another approach is to have an algorithm for allocating page frames to processes. One way is to occasionally find out the number of running processes and allocate each process an equal share. Thus with 12,416 available (i.e., non-operating system) page frames and 10 processes, each process gets 1241 frames. The remaining six go into a pool to be used when page faults occur.

Although this method seems fair, it makes little sense to give equal shares of the memory to a 10-KB process and a 300-KB process. Instead, pages can be assigned in proportion to each process total size, with a 300-KB process getting 30 times the allotment of a 10-KB process. It is probably wise to give each process some minimum number, so that it can run no matter how small it is. On some machines, for example, a single two-operand instruction may need as many as six pages because the instruction itself, the source operand, and the destination operand may all straddle page boundaries. With an allocation of only five pages, programs containing such instructions cannot execute at all.

If a global algorithm is used, it may be possible to start each process up with some number of pages proportional to the process size, but the allocation has to be updated dynamically as the processes run. One way to manage the allocation is to use the PFF (Page Fault Frequency) algorithm. It tells when to increase or decrease a process page allocation but says nothing about which page to replace on a fault. It just controls the size of the allocation set.

For a large class of page replacement algorithms, including LRU, it is known that the fault rate decreases as more pages are assigned, as we discussed above. This is the assumption behind PFF. This property is shown in Figure 2.

Page fault rate as a function of the number of page frames assigned

Measuring the page fault rate is straightforward: just count the number of faults per second, probably taking a running mean over past seconds as well. One easy way to do this is to add the number of page faults during the immediately preceding second to the current running mean and divide by two. The dashed line marked A corresponds to a page fault rate that is unacceptably high, so the faulting process is given more page frames to reduce the fault rate. The dashed line marked B corresponds to a page fault rate so low that we can assume the process has too much memory. In this case page frames may be taken away from it. Therefore, PFF tries to keep the paging rate for each process within acceptable bounds.

It is important to note that some page replacement algorithms can work with either a local replacement policy or a global one. For instance, FIFO can replace the oldest page in all of memory (global algorithm) or the oldest page owned by the current process (local algorithm). Likewise, LRU  or some approximation to it can replace the least recently used page in all of memory (global algorithm) or the least recently used page owned by  the current process (local algorithm). The choice of local versus global is independent of the algorithm in some cases.

However, for other page replacement algorithms, only a local strategy makes sense. Especially, the working set and WSClock algorithms refer to some particular process and must be applied in that context. There really is no working set for the machine as a whole, and trying to use the union of all the working sets would lose the locality property and not work well.


paging, global algorithm, memory, working set, page faults, pff algorithm