Efficient Multiple Processor Coordination.
Abstract
In recent years the concept of level-structured system organization has received growing acceptance as a computer operating system design technique. This approach treats the hardware of a computing system as the bottom level of a multilevel system which will be built up one level at a time. Each level creats an abstraction of the next lower level by implementing a new virtual machine which provides some features not previously available. This dissertation presents efficient solutions to certain problems of processor interaction which must be faced by the system designer at the lower levels of a strictly level-structured operating system. A loop-free algorithm is developed which solves Dijkstra's critical section problem, based on a rudimentary processor delay mechanism and the instruction set of a typical large computer of conventional architecture (DECsystem-10). A completely rigorous proof of the algorithm's correctness is given. The algorithm is used as the basis of a systematic procedure for obtaining efficient solutions to general processor coordination problems. The procedure is illustrated by solving several of the well-known reader/writer problems and a more complex new problem, the producer/consumer/distributor problem, which involves simultaneous use of several independent shared resources. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1976
- Accession Number
- ADA032803
Entities
People
- Bob E. Baker
Organizations
- Air Force Institute of Technology