Complementary replacement: a meta scheduling principle

ABSTRACT

A principle of scheduling is presented that includes a wide class of time and space allocation problems met in time sharing and virtual systems. Its essence is a method, based on symmetry, to use any of several rules for admission-to-service in a single server system to derive a space-replacement rule. This method, called complementary replacement includes several known job dispatching rules as well as some page-replacement algorithms such as the MIN and LRU (last-recently-used). A fundamental but unsolved problem with the principle is its range of applicability and the conditions under which it guarantees an optimum.

REFERENCES

• 1: H. Hellerman: "Some Principles of Time-Sharing Scheduler Strategies" IBM Systems Journal Vol. 8, No. 2 pp 94--117 (1969).
• 2: E. G. Coffman, L. Kleinrock: "Computer Scheduling Methods and Their Countermeasures" AFIPS Proc. Vol. 32, pp 11--21 (1968).
• 3: L. A. Belady: "A Study of Replacement Algorithms For a Virtual Storage Computer" IBM Systems Journal Vol. 5, No. 2 pp 78--101 (1966).