Citation:
R. Carr and J. Hennesy, "WSCLOCK - A Simple and Effective Algorithm for 
Virtual Memory Management", Proceedings of the Eighth ACM Symposium on
Operating System Principles, December 1981, pp. 87-95.

* Summary

A new virtual memory management algorithm called WSCLOCK is presented
that combines the effectiveness of working set (WS) with the efficiency
of CLOCK. In addition, the loading task / running task (LT/RT) load
control mechanism is developed as a means to prevent overcommitment of
auxiliary memory. WSCLOCK is shown using simulation to be as effective
as WS in terms of processor utilization, and LT/RT is shown to improve 
the performance of WS.

* WSCLOCK Overview

WSCLOCK keeps the task isolation and predictive load control of WS,
but eliminates the WSscan, the last referenced time per task page, the
available frame set, and the page reclamation procedure. WSCLOCK
maintains the last referenced time per main memory page frame, which
is set to the task's virtual time during the clock scan if the use bit 
is set. A page fault places a request on the paging queue, and the 
replacement algorithm is initiated when the request is processed to 
make room for the newly requested page. The replacement algorithm acts
like CLOCK, progressing though the circular list of main memory page
frames, looking for a clean replacable page. A page is deemed
replacable if it is no longer in the task working set or the task is
not active. During the scan, if the use bit is not set and VT-LR(p)
is greater than theta (the WS interval parameter), then the page is
removed from the task's working set.

* LT/RT Overview

The loading phase is defined as the time when the task has very few
of its working set of pages resident, and is loading the necessary
pages. This phase is characterized by lots of page faults and low
virtual time. The running phase is entered once the necessary pages
have all been loaded. This phase is characterized by relatively few
page faults and the task executes efficiently. If many tasks are in
the loading phase at the same time, auxiliary memory can become
overcommitted even though main memory is not, and a form of thrashing
can occur. In order to prevent such a situation, the LT/RT load
control mechanism limits the number of concurrent loading tasks. A
is considered to be in the loading phase until it has exceeded
virtual time tau or has performed an I/O operation.

* Results

WSCLOCK and WS with LT/RT have almost identical performance, and LT/RT
improves CPU utilization for WS by 5 to 20%. WSCLOCK has lower
numbers of page faults over all three test configurations, but
slightly lower peak utilization and multiprogramming level.