Accession Number : AD0714181

Title :   The Mutual Exclusion Problem.

Descriptive Note : Technical rept. no. 9,

Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS

Personal Author(s) : Bredt,Thomas H.

Report Date : AUG 1970

Pagination or Media Count : 71

Abstract : The paper discussed 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* 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 give 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. (Author)

Descriptors :   (*DATA PROCESSING, CONTROL SEQUENCES), LOGIC CIRCUITS, ALGORITHMS, COMPUTER LOGIC, FLOW CHARTING, TIME SHARING, DESIGN, MANAGEMENT PLANNING AND CONTROL, COMPUTER PROGRAMMING

Subject Categories : Computer Programming and Software
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE