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.