Some Deadlock Properties of Computer Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Deadlock Properties of Computer Systems

Full text

Pdf (1.46 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 4 , Issue 3 (September 1972) table of contents

Pages: 179 - 196

Year of Publication: 1972

ISSN:0360-0300

Author

Richard C. Holt

Department of Computer Science and Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 32, Downloads (12 Months): 132, Citation Count: 69

Additional Information:

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

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	ATWOOD, J W ; CLARK, B L ; GRUSHCOW, M S., HOLT, R. C.; HORNIN~, J J.; SEVCIK, K. C ; AND TSICHmTZIS, D "Project SuE status report." Computer Systems Research Group, Techmcal Report CSRG-11, Umv Toronto, Toronto, Ontario, Canada, April 1972.
	2	BERGE, CLAUDE. The theory o} graphs John Wiley & Sons, New York, 1962 (originally pubhshed in French m 1958).
	3	Per Brinch Hansen, The nucleus of a multiprogramming system, Communications of the ACM, v.13 n.4, p.238-241, April 1970 [doi>10.1145/362258.362278]
	4	E. G. Coffman , M. Elphick , A. Shoshani, System Deadlocks, ACM Computing Surveys (CSUR), v.3 n.2, p.67-78, June 1971 [doi>10.1145/356586.356588]
	5	DIJKSTRA, E. W. "Cooperating sequential processes." Technological Univ, Emdhoven, The Netherlands, Sept. 1965.
	6	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]
	7	DRYER, MATTHEW. "User's manual for TopPs." Computer Systems Research Group, Umv Toronto, Toronto, Ontano, Canada, 1972.
	8	A. N. Habermann, Prevention of system deadlocks, Communications of the ACM, v.12 n.7, p.373-ff., July 1969 [doi>10.1145/363156.363160]
	9	HAVENDER, J W "Avoiding deadlock In multit~skmg systems." IBM Systems J. 7, 2 (1968), 74-84
	10	HOLT, A W., AND COMMONER, F. "Events and conditions" Record o} the pro2ect MAC con- }erence on concurrent systems and parallel computatwn, ACM, June 1970, 3-52
	11	Richard Craig Holt, On deadlock in computer systems, 1971
	12	HORNING. J J., AND RANDELL, B. "Structuring complex processes." Report RC2459, IBM Research Lab.. Yorktown Heights, N.Y, May 1969
	13	IBM Svstem/360 operating system supervisor and data management services IBM Form No C28-6646-2, IBM Corp, Nov 1968.
	14	IBM System/360 PL/I reference manual. IBM Form No C28-8201-1, IBM Corp, March 1968.
	15	IBM System/360 operating system: job control language IBM Form No C28-6359-8, IBM Corp, Nov. 1968.
	16	System/360 attached support processor system (ASP) (360S-CX-15X) version 2' system manual. IBM Form No. Y20-0305-0, IBM Corp, Dec. 1968.
	17	KARP. RICHARD M.; AND MILLER, RAYMOND E. "P~rallel program schemata." J Computer & Syst~em Sciences 3, 2 (May 1969), 147-195.
	18	Butler W. Lampson, A scheduling philosophy for multiprocessing systems, Communications of the ACM, v.11 n.5, p.347-360, May 1968 [doi>10.1145/363095.363144]
	19	MCKEAG, R M "The multlprogrammmg system." Queen's Umv. Belfast, Dept. Computer Scmnce, Belfast, N. Ireland, 1972
	20	MURPHY, J E. "Resource allocatmn with interlock detection m a mult~task system" In Proc. AFIPS 1968 Fall Joznt Computer Con}., Vol. 33. Pt 2, AFIPS Press, Montvale, N J., 1169-1176.
	21	RAPPAPORT, ROBERT L "Implementing multiprocess primitives m a multiplexed computer system" Masters Thesis. Dept Electrical Engineering (Project MAC), Massachusetts Institute Technology, Cambridge, Mass, Nov. 1968
	22	Robert David Russell, A model for deadlock-free resource allocation, 1972
	23	SALTZER, JEROME HOWARD "Traffic control in a multiplexed computer system" PhD Thes~s, Project MAC, Massachusetts Institute Technology, Cambridge, Mass, July 1966
	24	SHOSHANI, A ; AND COFFMAN, E G, Ja "Detectmn, preventmn, and recovery from deadlock m multi~)rocess, multiple resource systems." Techmcal Report 80, Computer Sciences Lab, Dept Electrical Engineering, Princeton Univ, Princeton, N J., Oct 1969.
	25	VERNER, YVES "On process commumcatmn and process synchronizatmn " Masters Thesis. Dept Computer Science. Umv Toronto, Toronto, Ontarm, Canada, Oct 1971

CITED BY 69

	Toshimi Minoura, Deadlock avoidance revisited, Journal of the ACM (JACM), v.29 n.4, p.1023-1048, Oct. 1982
	Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983
	Mario Gerla , Emilio Leonardi , Fabio Neri , Prasasth Palnati, Routing in the bidirectional shufflenet, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.91-103, Feb., 2001
	W. W. Chu , G. Ohlmacher, Avoiding deadlock in distributed data bases, Proceedings of the 1974 annual conference, p.156-160, January 1974
	Divyakant Agrawal , Amr El Abbadi, Locks with constrained sharing (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.85-93, April 02-04, 1990, Nashville, Tennessee, United States
	Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Clarence A. Ellis, On the probability of deadlock in computer systems, ACM SIGOPS Operating Systems Review, v.7 n.4, p.88-95, October 1973
	Peter Ladkin , Barbara Simons, Compile-time analysis of communicating processes, Proceedings of the 6th international conference on Supercomputing, p.248-259, July 19-24, 1992, Washington, D. C., United States
	Peter J. Denning, Fault Tolerant Operating Systems, ACM Computing Surveys (CSUR), v.8 n.4, p.359-389, Dec. 1976
	Philip A. Bernstein , Nathan Goodman, Concurrency control algorithms for multiversion database systems, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.209-215, August 18-20, 1982, Ottawa, Canada
	Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987
	Rakesh Agrawal , David J. Dewitt, Integrated concurrency control and recovery mechanisms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.10 n.4, p.529-564, Dec. 1985
	Fred J. Maryanski , Kirk A. Norsworthy, A model of the performance of a rollback algorithm, Proceedings of the 1979 annual conference, p.54-61, January 1979
	Gabriel Bracha , Sam Toueg, A distributed algorithm for generalized deadlock detection, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.285-301, August 27-29, 1984, Vancouver, British Columbia, Canada
	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
	Kevin T. Ryan, Software engineering and simulation, Proceedings of the 11th conference on Winter simulation, p.477-482, December 03-05, 1979, San Diego, CA, United States
	Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981
	John Plevyak , Xingbin Zhang , Andrew A. Chien, Obtaining sequential efficiency for concurrent object-oriented languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-321, January 23-25, 1995, San Francisco, California, United States
	R. Devillers, Game interpretation of the deadlock avoidance problem, Communications of the ACM, v.20 n.10, p.741-745, Oct. 1977
	Gregory R. Andrews , Gary M. Levin, On-the-fly deadlock prevention, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.165-172, August 18-20, 1982, Ottawa, Canada
	Fernando de Ferreira Rezende , Theo Härder, A lock method for KBMSs using abstraction relationships' semantics, Proceedings of the third international conference on Information and knowledge management, p.112-121, November 29-December 02, 1994, Gaithersburg, Maryland, United States
	Y. Birk, On-Line Control and Deadlock-Avoidance in a Page-Parallel Multiprocessor Rasterizer, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.155-163, February 1993
	Richard C. Holt , Marc S. Grushcow, A short discussion of interprocess communication in the sue/360/370 operating system, ACM SIGPLAN Notices, v.8 n.9, p.74-78, September 1973
	Charles M. Shub, A unified treatment of deadlock, Journal of Computing Sciences in Colleges, v.19 n.1, p.194-204, October 2003
	Henry F. Korth , Ravi Krishnamurthy , Anil Nigam , John T. Robinson, A framework for understanding distributed (deadlock detection) algorithms, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Dieter Zöbel, The Deadlock problem: a classifying bibliography, ACM SIGOPS Operating Systems Review, v.17 n.4, p.6-15, October 1983
	Pun H. Shiu , YuDong Tan , Vincent J. Mooney, III, A novel parallel deadlock detection algorithm and architecture, Proceedings of the ninth international symposium on Hardware/software codesign, p.73-78, April 2001, Copenhagen, Denmark
	Tiko Kameda, Testing Deadlock-Freedom of Computer Systems, Journal of the ACM (JACM), v.27 n.2, p.270-280, April 1980
	Chia-Shiang Shih , John A. Stankovic, Distributed deadlock detection in Ada run-time environments, Proceedings of the conference on TRI-ADA '90, p.362-375, December 03-06, 1990, Baltimore, Maryland, United States
	Abdel Aziz Farrag , M. Tamer Özsu, Using semantic knowledge of transactions to increase concurrency, ACM Transactions on Database Systems (TODS), v.14 n.4, p.503-525, Dec. 1989
	Scott D. Carson , Paul F. Reynolds, Jr., The geometry of semaphore programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.1, p.25-53, Jan. 1987
	Douglas Seeley, Well—formed models for discrete simulation, Proceedings of the 7th conference on Winter simulation, p.725-726, January 14-16, 1974, Washington, DC
	Waleed A. Muhanna, Composite Programs: Hierarchical Construction, Circularity, and Deadlocks, IEEE Transactions on Software Engineering, v.17 n.4, p.320-333, April 1991
	Ugur Halici , Asuman Dogac, An Optimistic Locking Technique for Concurrency Control in Distributed Databases, IEEE Transactions on Software Engineering, v.17 n.7, p.712-724, July 1991
	Sugath Warnakulasuriya , Timothy Mark Pinkston, A Formal Model of Message Blocking and Deadlock Resolution in Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.212-229, March 2000
	M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989
	B. E. Wojcik , Z. M. Wojcik, Sufficient Condition for a Communication Deadlock and Distributed Deadlock Detection, IEEE Transactions on Software Engineering, v.15 n.12, p.1587-1595, December 1989
	Ajay D. Kshemkalyani , Mukesh Singhal, A One-Phase Algorithm to Detect Distributed Deadlocks in Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.880-895, November 1999
	Rakesh Agrawal , Michael J. Carey , David J. DeWitt, Deadlock detection is cheap, ACM SIGMOD Record, v.13 n.2, p.19-34, January 1983
	Jaehwan Lee , Vincent John Mooney, III, A novel deadlock avoidance algorithm and its hardware implementation, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden
	Jaehwan John Lee , Vincent John Mooney, III, A novel O(n) parallel banker's algorithm for System-on-a-Chip, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Timothy Mark Pinkston , Sugath Warnakulasuriya, Characterization of Deadlocks in k-ary n-Cube Networks, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.904-921, September 1999
	A. D. Kshemkalyani , M. Singhal, Efficient Detection and Resolution of Generalized Distributed Deadlocks, IEEE Transactions on Software Engineering, v.20 n.1, p.43-54, January 1994
	H. Sturgis , J. Mitchell , J. Israel, Issues in the design and use of a distributed file system, ACM SIGOPS Operating Systems Review, v.14 n.3, p.55-69, July 1980
	David B. Lomet, A practical deadlock avoidance algorithm for data base systems, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada
	Gertrude Neuman Levine, Defining deadlock, ACM SIGOPS Operating Systems Review, v.37 n.1, p.54-64, January 2003
	Yong Ho Song , Timothy Mark Pinkston, A Progressive Approach to Handling Message-Dependent Deadlock in Parallel Computer Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.259-275, March 2003
	Soojung Lee, Fast, Centralized Detection and Resolution of Distributed Deadlocks in the Generalized Model, IEEE Transactions on Software Engineering, v.30 n.9, p.561-573, September 2004
	Jaehwan John Lee , Vincent John Mooney, III, An o(min(m, n)) parallel deadlock detection algorithm, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.3, p.573-586, July 2005
	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
	Shau-Dong Lang, An Extended Banker's Algorithm for Deadlock Avoidance, IEEE Transactions on Software Engineering, v.25 n.3, p.428-432, May 1999
	Toshihide Ibaraki , Hussein M. Abdel-Wahab , Tiko Kameda, Design of Minimum-Cost Deadlock-Free Systems, Journal of the ACM (JACM), v.30 n.4, p.736-751, Oct. 1983
	Tong Li , Carla S. Ellis , Alvin R. Lebeck , Daniel J. Sorin, Pulse: a dynamic deadlock detection mechanism using speculative execution, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.3-3, April 10-15, 2005, Anaheim, CA
	Ranganath Atreya , Neeraj Mittal , Ajay D. Kshemkalyani , Vijay K. Garg , Mukesh Singhal, Efficient detection of a locally stable predicate in a distributed system, Journal of Parallel and Distributed Computing, v.67 n.4, p.369-385, April, 2007
	Catriel Beeri , Ron Obermarck, A resource class independent deadlock detection algorithm, Proceedings of the seventh international conference on Very Large Data Bases, p.166-178, September 09-11, 1981, Cannes, France
	Michel E. Adiba , Jean-Claude Chupin , Robert Demolombe , Georges Gardarin , Jean Le Bihan, Issues in distributed data base management systems: a technical overview, Proceedings of the fourth international conference on Very Large Data Bases, p.89-110, September 13-15, 1978, West Berlin, Germany
	David L. Sims , Debra A. Hensgen , Lantz Moore, Performance of concurrent servers generated automatically from sequential servers, USENIX Systems on USENIX Experiences with Distributed and Multiprocessor Systems, p.10-10, September 22-23, 1993, San Diego, California
	Stanislaw Chrobot, Sharing Variables in Distributed Memory, Fundamenta Informaticae, v.44 n.1-2, p.63-81, January 2000
	Philip A. Bernstein , Nathan Goodman, A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper), Proceedings of the 8th International Conference on Very Large Data Bases, p.62-76, September 08-10, 1982
	M. H. Samadzadeh , B. S. Koshy, A display and analysis tool for process-resource graphs, ACM SIGOPS Operating Systems Review, v.30 n.1, p.39-62, Jan. 1996
	Lucia C. Sekino, Multiple concurrent updates, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts
	Richard Peebles , Eric Manning, A computer architecture for large (distributed) data bases, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts
	Jaehwan John Lee , Vincent John Mooney, A Novel {O(n)} Parallel Banker's Algorithm for System-on-a-Chip, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1377-1389, December 2006
	F. E. Heart , S. M. Ornstein , W. R. Crowther , W. B. Barker, A new minicomputer/multiprocessor for the ARPA network, Proceedings of the June 4-8, 1973, national computer conference and exposition, June 04-08, 1973, New York, New York
	Fernando C. Colon , Robert M. Glorioso , Walter H. Kohler , Dominic W. Li, Coupling small computers for performance enhancement, Proceedings of the June 7-10, 1976, national computer conference and exposition, June 07-10, 1976, New York, New York
	Paul F. King , Arthur J. Collmeyer, Database sharing: an efficient mechanism for supporting concurrent processes, Proceedings of the June 4-8, 1973, national computer conference and exposition, June 04-08, 1973, New York, New York
	Gertrude Neuman Levine, Defining defects, errors, and service degradations, ACM SIGSOFT Software Engineering Notes, v.34 n.2, March 2009
	Zakaria Suliman Zubi , Diaddeen S. Sidoon, System proposal for preventing, detecting and avoiding deadlocks in modern operating system, Proceedings of the 10th WSEAS international conference on evolutionary computing, p.29-35, March 23-25, 2009, Prague, Czech Republic
	Daniel D. Corkill, Hierarchical planning in a distributed environment, Proceedings of the 6th international joint conference on Artificial intelligence, p.168-175, August 20-23, 1979, Tokyo, Japan