BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-70-173
       ENTRY:: November 06, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: The mutual exclusion problem
        TYPE:: Technical Report
      AUTHOR:: Bredt, Thomas H.
        DATE:: August 1970
       PAGES:: 72
    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.
       NOTES:: [Adminitrivia V1/Prg/19951106]
         END:: STAN//CS-TR-70-173