The WSClock Page Replacement Algorithm

Contrary to the textbook, the WSClock Page Replacement Algorithm is not really a natural outgrowth of the idea of a working set. It is, rather, a somewhat arbitrary hodge-podge of independent ideas, one of which is dimly connected to the idea of a working set. All the same it's worth teaching because: However, there's not much point in memorizing the details of this algorithm.

0. Let P be the process currently running. Records for active pages for P are kept in a circular list, as in the clock algorithm. In each record, there is an M and R bit set by hardware at each memory references, as in NRU. At each clock tick the R bit is reset to 0, as in NRU.

1. Each page record has a field for storing the time of the most recent reference. At each clock tick, the current cumulative CPU time for P is stored in the record of each page where the R bit is 1. Thus, the time field is an approximation to the time of the most recent reference, accurate to the clock period, so similar to the information needed in the LRU strategy, but does not require the imaginary hardware of having a clock time recorded at every memory reference. This is the most elegant idea in the WSClock algorithm.

2. One might think, now, that we would continue to approximate the LRU strategy by choosing the page with the earliest time field to replace. But instead, we do as follows: There is a fixed parameter Tau, and any page whose latest reference is older than Tau is considered equally a candidate for replacement. The presumption is that pages older than Tau are not in the working set. The OS designer works on tuning Tau so that this is more or less true in practice. This is where the influence of the idea of the working set comes into the algorithm.

The advantage of doing this is that you don't have to search through all the active pages to find the earliest time stamp; you can stop when you find one older than Tau.

If no pages have a reference older than Tau, then the page with the earliest time field is chosen for replacement.

3. We prefer, of course, to replace a clean page than a dirty page, because clean pages don't have to be copied out. So we search until we find a clean page that is older than Tau, if there is one; if not, we use a dirty page older than Tau.

4. On the other hand, if we encounter a dirty page that is older than Tau, then we may as well copy it out, on the presumption that it's not part of the working set, and it will have to be written out sooner or later in any case. Suppose we've decided to write out old dirty pages D1 through Dk and to replace old clean page C with new page N. Then we ask the disk driver to schedule these k writes and 1 read. We certainly have to block P until N is completely read in, but there's no need to block P to wait for the writings out of D1 through Dk. These can go on concurrently with P. (As we shall see, the order in which disk requests are taken is up to the disk driver, which has its own agenda.) Presumably, though Tanenbaum doesn't specifically say, the M bits of D1 through Dk are set to 0 as each is successfully written out.

Similarly, suppose we can't find an old clear page, so we've decided to write out old dirty pages D1 through Dk and to replace old dirty page D0 with new page N. Then P has to block until D0 has been written out and N has been read in, but does not have to block for D1 ... Dk.

5. However, we don't want to completely tie up the disk driver with this stuff, so we set a limit on the number k of dirty pages to be written out at once.

6. Finally, as in the clock algorithm, we keep the page table entries in a circular list. Each time we start searching circularly at the current value of the list pointer. As soon as we encounter an old clean page we stop. If there is not old clean page, we use an old dirty page. If there are no pages older than Tau, then we use the oldest page, clean or dirty. At the next search, we continue on from where the list pointer left off. I don't see that this circular structure buys you a whole lot, but presumably it prevents a situation where you always start by searching over the most frequently used pages. or it achieves some kind of fairness, or adds a soupcon of the FIFO strategy, or something.

That's the algorithm.