An alternative to event queues for synchronization in monitors

ABSTRACT

In the monitor concept, as proposed by Brinch Hansen and Hoare, event queues are used for synchronization. This paper describes another synchronizing primitive which is nearly as expressive as the conditional wait, but can be implemented more efficiently. An implementation of this primitive in terms of P and V operations is given together with a correctness proof. Two examples are presented: the readers and writers problem and the problem of information streams sharing a finite buffer pool.

REFERENCES

• 1: Brinch Hansen, P. A programming methodology for operating system design. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 394-397.
• 2: P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
• 3: Dahl, O.J., and Hoare, C.A.R. Hierarchical program structures. In Structured Programming, Academic Press, New York, 1972.
• 4: Dijkstra, E.W. Information streams sharing a finite buffer. Information Processing Letters 1, 5 (Oct. 1972), 179-180.
• 5: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 6: John H. Howard, Proving monitors, Communications of the ACM, v.19 n.5, p.273-279, May 1976 [doi>10.1145/360051.360079]
• 7: Michel Sintzoff , Axel Van Lamsweerde, Constructing correct and efficient concurrent programs, Proceedings of the international conference on Reliable software, p.319-326, April 21-23, 1975, Los Angeles, California
• 8: Wirth, N. The programming language PASCAL. Acta Informatica 1, 1 (1971), 35-63.

INDEX TERMS

Keywords:
conditional critical region, monitor, mutual exclusion, operating system, structuring concept, synchronization