More Web Proxy on the site http://driver.im/

article

Defining deadlock

Author:

Gertrude Neuman LevineAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 37, Issue 1

Pages 54 - 64

https://doi.org/10.1145/881775.881781

Published: 01 January 2003 Publication History

Abstract

Deadlock has been widely studied in many fields of computer science, notably in communications, database, and operating systems. Perhaps because (at least one state called) deadlock is tractable, there exists extensive literature on the subject. Deadlock was apparently decisively defined over thirty years ago, with its characteristics and handlers. Yet, much of the literature remains inconsistent in its treatment of this anomaly.A more precise definition is clearly needed to distinguish between the different states that are termed deadlock. A classification of dead states is required to distinguish the causes and appropriate handlers for each. We introduce a model to structure our research.

References

[1]

M. Andrews, B. Awerbuch, A. Fernandez, T. Leighto, Z. Liu, and J. Kleinberg, "Universal-stability Results and Performance Bounds for Greedy Contention-resolution Protocols," Journal of the ACM, vol. 48, no. 1, pp. 39--69, Jan. 2001.

Digital Library

[2]

P. Bernstein, and N. Goodman, "Concurrency Control in Distributed Database Systems," ACM Computer Surveys, vol. 13, no. 2, pp. 185--211, June 1981.

Digital Library

[3]

E. G. Coffman, E. G., M. J. Elphick, and A. Shoshani, "System Deadlocks," ACM Computing Surveys, vol. 3, no. 2, pp. 67--78, June 1971.

Digital Library

[4]

E. G. Coffman and P. J. Denning, Operating Systems Theory, Prentice Hall, Englewood Cliffs, NJ, 1973.

Digital Library

[5]

W. S. Davis and T. M. Rajkumar, Operating Systems, A Systematic View, 5 th ed., Addison-Wesley, Reading, Mass., p. 123, 2001.

Digital Library

[6]

E. W. Dijkstra, "Cooperating Sequential Processes," Programming Languages, Academic Press, London, 1965.

[7]

L. Dowdy and C. Lowery, P. S. to Operating Systems, Prentice Hall, Englewood Cliffs, NJ. 1993.

Digital Library

[8]

S. Floyd and K. Fall, "Promoting the Use of End-to-end Congestion Control in the Internet," IEEE/ACM Transactions on Networks, vol. 7, no. 4, pp. 458--472. Aug. 1999.

Digital Library

[9]

I. M. Flynn and A. M. McHoes, Understanding Operating Systems, Brooks/Cole, Australia, pp. 109--110, 2001.

Digital Library

[10]

R. C. Holt, "Some Deadlock Properties of Computer Systems," ACM Computing Surveys, vol. 4, no. 3, pp. 179--196, Sept. 1972.

Digital Library

[11]

D. Horner, Operating Systems, Concept and Applications, Scott, Foresman and Co. Glenville, III., pp. 160, 105, 182, 1989.

Digital Library

[12]

W. S. Lai, "Protocol Traps in Computer Networks- a Catalog. IEEE Transactions on Communications," Com-30, no. 6, pp. 1434--1448, June 1982.

[13]

G. N. Levine, "The Control of Starvation," International Journal of General Systems, vol. 15, pp. 113--127, 1989.

[14]

G. N. Levine, "A Model for Software Reuse," Proceedings of the 5th Workshop of Specification of Behavior Semantics, OOPSLA '96, pp. 71--87, Oct. 1996.

[15]

J. C. Mogul and K. K. Ramakrishnan, "Eliminating Receive Livelock in an Interrupt-driven Kernel," ACM Trans. on Computer Systems, vol. 15, no. 3, pp. 217--252, Aug. 1997.

Digital Library

[16]

G. Nutt, Operating Systems, a Modern Perspective, 2nd edition, Addison-Wesley, Reading, Mass., pp. 150, 279, 2000.

Digital Library

[17]

J. R. Pinkert and L. L. Weat, Operating Systems, Prentice Hall, Englewood Cliffs, NJ, p. 48, 1989.

[18]

P. J. Plauger, "On Being Fast Enough," Embedded Systems Prog., vol. 4, no. l, pp. 81--92, Jan. 1991.

[19]

D. J. Rosenkrantz, R. E., Stearns, and P. M. Lewis, "System Level Concurrency Control for Distributed Database Systems," ACM Trans. on Database Systems, vol. 3, no. 2, pp. 178--198, June 1978.

Digital Library

[20]

A. Silberschatz, P. B. Galvin, and G. Gagne, Operating Systems Concepts, 6th edition, Addison-Wesley, Reading, Mass., pp. 204, 243, 244, 266, 2002.

Digital Library

[21]

W. Stallings, Operating Systems, Internals and Design Principles, 3rd edition, Prentice Hall, Englewood Hills, NJ, pp. 254, 1998.

Digital Library

[22]

A. Tanenbaum, Computer Networks, 4th edition, Prentice Hall, Upper Saddler River, NJ. 2003.

Digital Library

[23]

A. Tanenbaum, Modern Operating Systems, 2nd edition, Prentice Hall, Upper Saddle River, NJ, p. 185, 2001.

Digital Library

[24]

A. Tanenbaum, Operating Systems, Design and Implementation, 2nd edition, Prentice Hall, Upper Saddle River, NJ, pp. 67--69, 1997.

Digital Library

[25]

Y. C. Tay and W. T. Loke, "On Deadlocks of Exclusive AND-requests for Resources," Distributed Computing, Springer-Verlag, #9, pp. 77--94, 1995.

Digital Library

[26]

D. Tsichritzis, and F. Lochovsky, Data Base Management Systems, Academic Press, London, p. 260, 1977.

[27]

R. Turner, Operating Systems Design and Implementations, Macmillan Pub. Co., London, p. 140, 1986.

[28]

R. J. Van Glabbeek, "Notes on the Methodology of CCS and CSP," Theoretical Computer Science, pp. 329--349, 1997.

Digital Library

[29]

H. Wu, W. Chin, and J. Jaffar, "An Efficient Distributed Deadlock Avoidance Algorithm for the AND Model," IEEE Trans. on Software Engineering, vol. 28, no. 1, pp. 18--29, Jan. 2002.

Digital Library

Cited By

Levine G(2014)Incorporating Service Degradations into a Security PlanProceedings of the 2014 IEEE International Conference on Software Science, Technology and Engineering10.1109/SWSTE.2014.10(1-9)Online publication date: 11-Jun-2014
https://dl.acm.org/doi/10.1109/SWSTE.2014.10
Levine G(2013)Computer security with service degradationsACM SIGSOFT Software Engineering Notes10.1145/2532780.253281038:6(1-7)Online publication date: 11-Nov-2013
https://dl.acm.org/doi/10.1145/2532780.2532810
Levine G(2012)Priority inversion with fungible resourcesACM SIGAda Ada Letters10.1145/2148436.214843831:2(9-14)Online publication date: 22-Feb-2012
https://dl.acm.org/doi/10.1145/2148436.2148438
Show More Cited By

Recommendations

Defining deadlock with fungible resources

In a previous paper we discussed resource deadlock within a classification of all dead states. We differentiated between the different types of anomalies that are called deadlock in the computer science literature. Our primary aim was to correct ...
Static lock capabilities for deadlock freedom
TLDI '12: Proceedings of the 8th ACM SIGPLAN workshop on Types in language design and implementation

We present a technique --- lock capabilities --- for statically verifying that multithreaded programs with locks will not deadlock. Most previous work on deadlock prevention requires a strict total order on all locks held simultaneously by a thread, but ...
Transparent runtime deadlock elimination
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

Thread based concurrent programming is hard due to the potential of concurrency bugs (e.g., data races, atomicity violations, deadlocks, and order violations). While data races and atomicity violations can be ameliorated with appropriate synchronization ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 37, Issue 1

January 2003

60 pages

ISSN:0163-5980

DOI:10.1145/881775

Issue’s Table of Contents

Copyright © 2003 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2003

Published in SIGOPS Volume 37, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
1,672
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Levine G(2014)Incorporating Service Degradations into a Security PlanProceedings of the 2014 IEEE International Conference on Software Science, Technology and Engineering10.1109/SWSTE.2014.10(1-9)Online publication date: 11-Jun-2014
https://dl.acm.org/doi/10.1109/SWSTE.2014.10
Levine G(2013)Computer security with service degradationsACM SIGSOFT Software Engineering Notes10.1145/2532780.253281038:6(1-7)Online publication date: 11-Nov-2013
https://dl.acm.org/doi/10.1145/2532780.2532810
Levine G(2012)Priority inversion with fungible resourcesACM SIGAda Ada Letters10.1145/2148436.214843831:2(9-14)Online publication date: 22-Feb-2012
https://dl.acm.org/doi/10.1145/2148436.2148438
Pun KSteffen MStolz V(2012)Deadlock checking by a behavioral effect system for lock handlingThe Journal of Logic and Algebraic Programming10.1016/j.jlap.2011.11.00181:3(331-354)Online publication date: Apr-2012
https://doi.org/10.1016/j.jlap.2011.11.001
Chengduan W(2010)The Designing and Implementing of Distributed Shared MemoryProceedings of the 2010 International Conference on Innovative Computing and Communication and 2010 Asia-Pacific Conference on Information Technology and Ocean Engineering10.1109/CICC-ITOE.2010.94(347-351)Online publication date: 30-Jan-2010
https://dl.acm.org/doi/10.1109/CICC-ITOE.2010.94
Levine G(2009)Defining defects, errors, and service degradationsACM SIGSOFT Software Engineering Notes10.1145/1507195.150720534:2(1-14)Online publication date: 28-Feb-2009
https://dl.acm.org/doi/10.1145/1507195.1507205
Zeng F(2007)A Reinforcement-Learning Approach to Failure-Detection SchedulingSeventh International Conference on Quality Software (QSIC 2007)10.1109/QSIC.2007.4385492(161-170)Online publication date: Oct-2007
https://doi.org/10.1109/QSIC.2007.4385492
Powers FAlaghband G(2007)The Hydra Parallel Programming SystemConcurrency and Computation: Practice and Experience10.1002/cpe.120520:1(1-27)Online publication date: 2-Aug-2007
https://doi.org/10.1002/cpe.1205
Levine G(2006)A Model for Anomalies of Software EngineeringAdvances in Systems, Computing Sciences and Software Engineering10.1007/1-4020-5263-4_39(243-250)Online publication date: 2006
https://doi.org/10.1007/1-4020-5263-4_39
Levine G(2005)Ada and the control of intrusionACM SIGAda Ada Letters10.1145/1102251.1102254XXV:3(32-39)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1145/1102251.1102254
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents