The Mutual Exclusion Problem.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1970
- Accession Number
- AD0714181
Entities
People
- Thomas H. Bredt
Organizations
- Stanford University