Decentralized Simulation of Resource Managers

Abstract

There are two primary means of resource allocaUon in computer systems. One is the powerful mechanism of using a centrahzed resource manager to allocate the resources. An apparently weaker mechanism is for the asynchronous processes of the system to allocate resources with some type of message passing. A unifying treatment of these two methods is provided. It is shown that a managed system may be simulated by the processes using test and set instructions. As a corollary, a wide variety of synchronization algorithms may be accomplished without a manager. The simulation works correctly even m an environment where processes die in an undetectable manner. All memory cells are of size at most four. Thus this general simulation provides the first known algorithm for fairly synchronizing dying processes with bounded sized memory cells. In particular, the simulation solves the/-crmcal section problem with test-and-set instructions operating on bounded size memory. © 1983, ACM. All rights reserved.