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.