The WSClock Page Replacement Algorithm

The WSClock Page Replacement Algorithm

The main working set algorithm is unwieldy, since the entire page table has to be scanned at each page fault until a suitable candidate is located. An improved algorithm, that is based on the clock algorithm but also uses the working set information, is called WSClock (Carr and Hennessey, 1981). Due to its simplicity of implementation and good performance, it is commonly used in practice.

The data structure required is a circular list of page frames, as in the clock algorithm, and as shown in Figure 1(a). At first, this list is empty. When the first page is loaded, it is added to the list. As more pages are added, they go into the list to form a ring. Each entry includes the Time of last use field from the basic working set algorithm, as well as the R bit (shown) and the M bit (not  shown).

As with the clock algorithm, at each page fault the page pointed to by the hand is checked first. If the R bit is set to 1, the page has been used during the current tick so it is not an ideal candidate to remove. The R bit is then set to 0, the hand advanced to the next page, and the algorithm repeated for that page. The state after this sequence of events is shown in Figure 1(b).

Now look at what happens if the page pointed to has R = 0, as shown in Figure1(c). If the age is greater than τ and the page is clean, it is not in the working set and a valid copy exists on the disk. The page frame is simply claimed and the new page put there, as shown in Figure 1(d). On the other hand, if the page is dirty, it cannot be claimed immediately since no valid copy is present on disk. To avoid a process switch, the write to disk is scheduled, but the hand is advanced and the algorithm continues with the next page. After all, there might be an old, clean page further down the line that can be used immediately.

Technically, all pages might be scheduled for disk I/O on one cycle around the clock. To reduce disk traffic, a limit might be set, allowing a maximum of n pages to be written back. Once this limit has been reached, no new writes are scheduled.

What happens if the hand comes all the way around to its starting point? There are two cases to deal with:

1. At least one write has been scheduled.
2. No writes have been scheduled.

In the first case, the hand just keeps moving, looking for a clean page. Since one or more writes have been scheduled, ultimately some write will complete and its page will be marked as clean. The first clean page encountered is removed. This page is not necessarily the first write scheduled because the disk driver may reorder writes in order to optimize disk performance.

Operation of the WSClock algorithm

In the second case, all pages are in the working set, otherwise at least one write would have been scheduled. Lacking further information, the simplest thing to do is claim any clean page and use it. The location of a clean page could be kept track of during the sweep. If no clean pages exist, then the current page is chosen as the victim and written back to disk.



Tags

algorithm, page fault, wsclock