A new solution to the critical section problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new solution to the critical section problem

Full text

Pdf (222 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the tenth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 86 - 88

Year of Publication: 1978

Author

Howard P. Katseff

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 53, Citation Count: 13

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/800133.804335 What is a DOI?

ABSTRACT

A classical problem in concurrent program control is to provide a mechanism whereby several processes running concurrently can gain exclusive control of a resource. For each process, the section of its program in which it accesses the resource is called its critical section, and the problem is called the critical section problem. A solution to the critical section problem guarantees that no more than one process can be in its critical section at any time. The solution presented here improves on previous solutions by allowing processes to enter their critical sections on a first-come first-served basis.

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	Murray A. Eisenberg , Michael R. McGuire, Further comments on Dijkstra's concurrent programming control problem, Communications of the ACM, v.15 n.11, p.999, Nov. 1972 [doi>10.1145/355606.361895]
	3	Katseff, H. P. (1978), "A Solution to the Critical Section Problem with a Totally Wait-free FIFO Doorway," Internal Memorandum, Computer Science Division, University of California, Berkeley.
	4	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]
	5	Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
	6	Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
	7	Rivest, R.L. and Pratt, V.R. (1976), "The Mutual Exclusion Problem for Unreliable Processes: Preliminary Report," Proc. IEEE Symp. Found. Comp. Sci. 17, 1-8.

CITED BY 13

	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States
	Benton L. Leong , Joel I. Seiferas, New Real-Time Simulations of Multihead Tape Units, Journal of the ACM (JACM), v.28 n.1, p.166-180, Jan. 1981
	Jeffrey M. Jaffe, Decentralized Simulation of Resource Managers, Journal of the ACM (JACM), v.30 n.2, p.300-322, April 1983
	Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada
	Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986
	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
	Gary L. Peterson, A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.56-65, Jan. 1983
	Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983
	Edward A. Lycklama , Vassos Hadzilacos, A first-come-first-served mutual-exclusion algorithm with small communication variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.558-576, Oct. 1991
	Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bounded first-in, first-enabled solution to the l-exclusion problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.939-953, May 1994
	Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
	Amos Israeli , Ming Li, Bounded time-stamps, Distributed Computing, v.6 n.4, p.205-209, July 1993
	B. K. Szymanski, A simple solution to Lamport's concurrent programming problem with linear wait, Proceedings of the 2nd international conference on Supercomputing, p.621-626, June 1988, St. Malo, France