Concurrent control with “readers” and “writers”

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Concurrent control with “readers” and “writers”

Full text

Pdf (146 KB)

Source

Communications of the ACM archive
Volume 14 , Issue 10 (October 1971) table of contents

Pages: 667 - 668

Year of Publication: 1971

ISSN:0001-0782

Authors

P. J. Courtois	Carnegie-Mellon Univ., Pittsburgh, PA
F. Heymans	MBLE research Laboratory, Brussels, Belgium
D. L. Parnas	Carnegie-Mellon Univ., Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 57, Downloads (12 Months): 353, Citation Count: 99

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362759.362813 What is a DOI?

ABSTRACT

The problem of the mutual exclusion of several independent processes from simultaneous access to a “critical section” is discussed for the case where there are two distinct classes of processes known as “readers” and “writers.” The “readers” may share the section with each other, but the “writers” must have exclusive access. Two solutions are presented: one for the case where we wish minimum delay for the readers; the other for the case where we wish writing to take place as early as possible.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
	2	Donald E. Knuth, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.9 n.5, p.321-322, May 1966 [doi>10.1145/355592.365595]
	3	N. G. de Bruijn, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.10 n.3, p.137-138, March 1967 [doi>10.1145/363162.363167]
	4	Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]

CITED BY 99

	D. L. Parnas, On a solution to the cigarette smoker's problem (without conditional statements), Communications of the ACM, v.18 n.3, p.181-183, March 1975
	Jia Xu , David Lorge Parnas, On satisfying timing constraints in hard-real-time systems, ACM SIGSOFT Software Engineering Notes, v.16 n.5, p.132-146, Dec. 1991
	C. A. R. Hoare, Monitors: an operating system structuring concept, The origin of concurrent programming: from semaphores to remote procedure calls, Springer-Verlag New York, Inc., New York, NY, 2002
	Arvind , Kim P. Gostelow , Wil Plouffe, Indeterminacy, monitors, and dataflow, ACM SIGOPS Operating Systems Review, v.11 n.5, p.159-169, November 1977
	Jonathan Kepecs , Marvin Solomon, SODA: A simplified operating system for distributed applications, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.208-219, August 27-29, 1984, Vancouver, British Columbia, Canada
	J. E. Burns , G. L. Peterson, The ambiguity of choosing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.145-157, June 1989, Edmonton, Alberta, Canada
	Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977
	Jonathan Kepecs , Marvin Solomon, SODA: a simplified operating system for distributed applications, ACM SIGOPS Operating Systems Review, v.19 n.4, p.45-56, October 1985
	Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983
	Robert D. Dixon , David Hemmendinger, Analyzing synchronization problems by using event histories as languages, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.183-188, February 1986, Cincinnati, Ohio, United States
	C. V. Ravi, A distributed file system, Proceedings of the 1975 annual conference, p.193-197, January 1975
	Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada
	Thomas W. Doeppner, Jr., Parallel program correctness through refinement, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.155-169, January 17-19, 1977, Los Angeles, California
	Gregory R. Andrews, Synchronizing Resources, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.405-430, Oct. 1981
	Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978
	Mark S. Laventhal, A constructive approach to reliable synchronization code, Proceedings of the 4th international conference on Software engineering, p.194-202, September 17-19, 1979, Munich, Germany
	Patrick Keane , Mark Moir, A Simple Local-Spin Group Mutual Exclusion Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.673-685, July 2001
	Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada
	Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register, Journal of the ACM (JACM), v.41 n.2, p.311-339, March 1994
	E. G. Coffman, Jr. , Erol Gelenbe , Roger C. Wood, Optimal replication of parallel-read, sequential-write systems, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.209-216, Summer 1980
	Patricia Griffiths, SYNVER: A system for the automatic synthesis and verification of synchronization processes, Proceedings of the 1974 annual conference, p.167-173, January 1974
	Per Brinch Hansen, Monitors and concurrent Pascal: a personal history, ACM SIGPLAN Notices, v.28 n.3, p.1-35, March 1993
	Richard Bornat , Cristiano Calcagno , Peter O'Hearn , Matthew Parkinson, Permission accounting in separation logic, ACM SIGPLAN Notices, v.40 n.1, p.259-270, January 2005
	John M. Mellor-Crummey , Michael L. Scott, Scalable reader-writer synchronization for shared-memory multiprocessors, ACM SIGPLAN Notices, v.26 n.7, p.106-113, July 1991
	Prasad Jayanti, On the robustness of Herlihy's hierarchy, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.145-157, August 15-18, 1993, Ithaca, New York, United States
	J. Xu , D. L. Parnas, On Satisfying Timing Constraints in Hard-Real-Time Systems, IEEE Transactions on Software Engineering, v.19 n.1, p.70-84, January 1993
	J. L. W. Kessels, An alternative to event queues for synchronization in monitors, Communications of the ACM, v.20 n.7, p.500-503, July 1977
	Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998
	Patrick Keane , Mark Moir, A simple local-spin group mutual exclusion algorithm, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.23-32, May 04-06, 1999, Atlanta, Georgia, United States
	O. Roux , J. P. Elloy, ELECTRE: A language using control structure expressions to specify synchronization, Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspective, p.240-245, October 1985, Denver, Colorado, United States
	Carl Hewitt , Peter Bishop , Irene Greif , Brian Smith , Todd Matson , Richard Steiger, Actor induction and meta-evaluation, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.153-168, October 01-03, 1973, Boston, Massachusetts
	Patricia P. Griffiths , Charles J. Prenner, Verifying formal specifications of synchronous processes, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.192-208, January 19-21, 1976, Atlanta, Georgia
	Eugene W. Stark, Semaphore primitives and starvation-free mutual exclusion, Journal of the ACM (JACM), v.29 n.4, p.1049-1072, Oct. 1982
	Jon Kleinberg , Sendhil Mullainathan, Resource bounds and combinations of consensus objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.133-143, August 15-18, 1993, Ithaca, New York, United States
	Gregory R. Andrews , James R. McGraw, Language features for process interaction, ACM SIGOPS Operating Systems Review, v.11 n.2, p.114-127, April 1977
	Peter A. Buhr , Michel Fortier , Michael H. Coffin, Monitor classification, ACM Computing Surveys (CSUR), v.27 n.1, p.63-107, March 1995
	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983
	Gérald Belpaire , Jean Pierre Wilmotte, Semantic aspects of concurrent processes, ACM SIGPLAN Notices, v.8 n.9, p.42-45, September 1973
	Toby Bloom, Evaluating synchronization mechanisms, Proceedings of the seventh ACM symposium on Operating systems principles, p.24-32, December 10-12, 1979, Pacific Grove, California, United States
	C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974
	James E. Burns , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada
	Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983
	Takayuki Kimura, An algebraic system for process structuring and interprocess communication, Proceedings of the eighth annual ACM symposium on Theory of computing, p.92-100, May 03-05, 1976, Hershey, Pennsylvania, United States
	David P. Reed , Rajendra K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM, v.22 n.2, p.115-123, Feb. 1979
	John M. Mellor-Crummey , Michael L. Scott, Synchronization without contention, ACM SIGARCH Computer Architecture News, v.19 n.2, p.269-278, Apr. 1991
	Peter B. Henderson , Yechezkel Zalcstein, Synchronization Problems Solvable by Generalized PV Systems, Journal of the ACM (JACM), v.27 n.1, p.60-71, Jan. 1980
	Per Brinch Hansen, Structured multiprogramming, Communications of the ACM, v.15 n.7, p.574-578, July 1972
	Robert M. Keller, Formal verification of parallel programs, Communications of the ACM, v.19 n.7, p.371-384, July 1976
	Irene Greif, A language for formal problem specification, Communications of the ACM, v.20 n.12, p.931-935, Dec. 1977
	C. William Higginbotham , Ralph Morelli, A system for teaching concurrent programming, ACM SIGCSE Bulletin, v.23 n.1, p.309-316, Mar. 1991
	Gregory R. Andrews, Paradigms for process interaction in distributed programs, ACM Computing Surveys (CSUR), v.23 n.1, p.49-90, March 1991
	Leon Presser, Multiprogramming Coordination, ACM Computing Surveys (CSUR), v.7 n.1, p.21-44, March 1975
	Jayadev Misra, A Simple, Object-Based View of Multiprogramming, Formal Methods in System Design, v.20 n.1, p.23-45, January 2002
	Dennis W. Leinbaugh, High level description and implementation of resource schedulers, Proceedings of the ACM '82 conference, p.169-175, January 1982
	Michael J. Spier , Richard L. Hill , Timothy J. Stein , Daniel Bricklin, The TYPESET-10 Message Exchange Facility: a case study in systemic design, ACM SIGOPS Operating Systems Review, v.9 n.1, p.10-18, January 1975
	Per Brinch Hansen, The invention of concurrent programming, The origin of concurrent programming: from semaphores to remote procedure calls, Springer-Verlag New York, Inc., New York, NY, 2002
	Sten Andler, Predicate path expressions, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.226-236, January 29-31, 1979, San Antonio, Texas
	N. H. Gehani, Capsules: A Shared Memory Access Mechanism for Concurrent C/C++, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.795-811, July 1993
	Patricia K. Immich , Ravi S. Bhagavatula , Ravi Pendse, Performance analysis of five interprocess communication mechanisms across UNIX operating systems, Journal of Systems and Software, v.68 n.1, p.27-43, 15 October 2003
	James H. Anderson , Yong-Jik Kim , Ted Herman, Shared-memory mutual exclusion: major research trends since 1986, Distributed Computing, v.16 n.2-3, p.75-110, September 2003
	Ashis Tarafdar , Vijay K. Garg, Predicate control: synchronization in distributed computations with look-ahead, Journal of Parallel and Distributed Computing, v.64 n.2, p.219-237, February 2004
	Eric Freudenthal , Allan Gottlieb, Process coordination with fetch-and-increment, ACM SIGPLAN Notices, v.26 n.4, p.260-268, Apr. 1991
	Jean Bezivin, Some experiments in object-oriented simulation, ACM SIGPLAN Notices, v.22 n.12, p.394-405, Dec. 1987
	Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Yuh-Jzer Joung, The congenial talking philosophers problem in computer networks, Distributed Computing, v.15 n.3, p.155-175, July 2002
	Gerald M. Karam , Raymond J. A. Buhr, Temporal Logic-Based Deadlock Analysis for Ada, IEEE Transactions on Software Engineering, v.17 n.10, p.1109-1125, October 1991
	B. Bloom, Constructing Two-Writer Atomic Registers, IEEE Transactions on Computers, v.37 n.12, p.1506-1514, December 1988
	P. E. Lauer , M. W. Shields, Abstract specification of resource accessing disciplines: adequacy, starvation, priority and interrupts, ACM SIGPLAN Notices, v.13 n.12, p.41-59, December 1978
	David Hemmendinger, Specifying Ada Server Tasks with Executable Formal Grammars, IEEE Transactions on Software Engineering, v.16 n.7, p.741-754, July 1990
	A. Thomasian , V. F. Nicola, Performance Evaluation of a Threshold Policy for Scheduling Readers and Writers, IEEE Transactions on Computers, v.42 n.1, p.83-98, January 1993
	Christian Boulinier , Franck Petit , Vincent Villain, When graph theory helps self-stabilization, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Yuh-Jzer Joung, Asynchronous group mutual exclusion, Distributed Computing, v.13 n.4, p.189-206, November 2000
	I. Page , T. Jacob , E. Chern, Fast Algorithms for Distributed Resource Allocation, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.188-197, February 1993
	A. J. Gerber, Process synchronization by counter variables, ACM SIGOPS Operating Systems Review, v.11 n.4, p.6-17, October 1977
	James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
	G. M. Karam , R. J. A. Buhr, Starvation and Critical Race Analyzers for Ada, IEEE Transactions on Software Engineering, v.16 n.8, p.829-843, August 1990
	Per Brinch Hansen, Monitors and Concurrent Pascal: a personal history, History of programming languages---II, ACM Press, New York, NY, 1996
	Peter A. Buhr , Ashif S. Harji, Implicit-signal monitors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1270-1343, November 2005
	Barbara G. Ryder , Mary Lou Soffa , Margaret Burnett, The impact of software engineering research on modern progamming languages, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.4, p.431-477, October 2005
	Ajoy K. Datta , Maria Gradinariu , Michel Raynal, Stabilizing mobile philosophers, Information Processing Letters, v.95 n.1, p.299-306, 16 July 2005
	Per Brinch Hansen, Structured multiprogramming, The origin of concurrent programming: from semaphores to remote procedure calls, Springer-Verlag New York, Inc., New York, NY, 2002
	Knut H. Pedersen , Constantinos Constantinides, AspectAda: aspect oriented programming for ada95, ACM SIGAda Ada Letters, v.XXV n.4, p.79-92, December 2005
	M. Evangelist , N. Francez , S. Katz, Multiparty Interactions for Interprocess Communication and Synchronization, IEEE Transactions on Software Engineering, v.15 n.11, p.1417-1426, November 1989
	Gary D. Knott, A proposal for certain process management and intercommunication primitives, ACM SIGOPS Operating Systems Review, v.8 n.4, p.7-44, October 1974
	Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, APSS: proactive secret sharing in asynchronous systems, ACM Transactions on Information and System Security (TISSEC), v.8 n.3, p.259-286, August 2005
	Leslie Lamport, Arbitration-free synchronization, Distributed Computing, v.16 n.2-3, p.219-237, September 2003
	James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
	Karl N. Levitt, The application of program-proving techniques to the verification of synchronization processes, Proceedings of the December 5-7, 1972, fall joint computer conference, part I, December 05-07, 1972, Anaheim, California
	Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981
	Ifen Yang , William Moloney, Concurrent reading and writing with replicated data objects, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.414-417, February 1988, Atlanta, Georgia, United States
	Hai Huang , Padmanabhan Pillai , Kang G. Shin, Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.303-316, June 10-15, 2002
	Jayaram Bobba , Kevin E. Moore , Haris Volos , Luke Yen , Mark D. Hill , Michael M. Swift , David A. Wood, Performance pathologies in hardware transactional memory, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
	Shaohua Xie , Eileen Kraemer , R. E. K. Stirewalt, Design and Evaluation of a Diagrammatic Notation to Aid in the Understanding of Concurrency Concepts, Proceedings of the 29th International Conference on Software Engineering, p.727-731, May 20-26, 2007
	Leslie Lamport, What it means for a concurrent program to satisfy a specification: why no one has specified priority, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.78-83, January 14-16, 1985, New Orleans, Louisiana, United States
	Pierre Castori, Semaphores revisited with MMS, ACM SIGOPS Operating Systems Review, v.29 n.3, p.49-63, July 1995
	John A. Trono, A new exercise in concurrency, ACM SIGCSE Bulletin, v.26 n.3, p.8-10, Sept. 1994
	Pascal Ledru, Translation of the protected type mechanism in Ada 83, ACM SIGAda Ada Letters, v.XV n.1, p.64-69, Jan./Feb. 1995
	AspectC2C: a symmetric aspect extension to the C language, ACM SIGPLAN Notices, v.43 n.2, p.25-32, February 2008
	Yossi Lev , Victor Luchangco , Marek Olszewski, Scalable reader-writer locks, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada

INDEX TERMS

Keywords:
critical section, mutual exclusion, shared access to resources

Collaborative Colleagues:

P. J. Courtois: colleagues

F. Heymans: colleagues

D. L. Parnas: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player