Report Number: CS-TR-70-173
Institution: Stanford University, Department of Computer Science
Title: The mutual exclusion problem
Author: Bredt, Thomas H.
Date: August 1970
Abstract: This paper discusses how n components, which may be programs or circuits, in a computer system can be controlled so that (1) at most one component may perform a designated "critical" operation at any instant and (2) if one component wants to perform its critical operation, it is eventually allowed to do so. This control problem is known as the mutual exclusion or interlock problem. A summary of the flow table model [Stanford University Department of Computer Science report STAN-CS-70-160] for computer systems is given. In this model, a control algorithm is represented by a flow table. The number of internal states in the control flow table is used as a measure of the complexity of control algorithms. A lower bound of n + 1 internal states is shown to be necessary if the mutual exclusion problem is to be solved. Procedures to generate control flow tables for the mutual exclusion problem which require the minimum number of internal states are described and it is proved that these procedures given correct control solutions. Other so-called "unbiased" algorithms are described which require 2.n! internal states but break ties in the case of multiple requests in favor of the component that least recently executed its critical operation. The paper concludes with a discussion of the tradeoffs between central and distributed control algorithms.