Article

Efficient distributed deadlock avoidance with liveness guarantees

Authors:

César Sánchez,

Henny B. Sipma,

Christopher D. GillAuthors Info & Claims

EMSOFT '06: Proceedings of the 6th ACM & IEEE International conference on Embedded software

Pages 12 - 20

https://doi.org/10.1145/1176887.1176891

Published: 22 October 2006 Publication History

Abstract

We present a deadlock avoidance algorithm for distributed systems that guarantees liveness. Deadlock avoidance in distributed systems is a hard problem and general solutions are considered impractical due to the high communication overhead. In previous work, however, we showed that practical solutions exist when all possible sequences of resource requests are known a priori in the form of call graphs; in this case protocols can be constructed that perform safe resource allocation based on local data only, that is, no communication between components is required. While avoiding deadlock, those protocols, however, did not avoid starvation: they guaranteed that some process could always make progress, but did not guarantee that every individual process would always eventually terminate.In this paper we present a resource allocation mechanism that avoids deadlock and guarantees absence of starvation, without undue loss of concurrency. The only assumption we make is that the local scheduler is fair. We prove the correctness of the algorithm and show how it can be implemented efficiently.

References

[1]

Andrew D. Birrell. An introduction to programming with threads. Research Report 35, Digital Equipment Corporation Systems Research Center, 1989.]]

[2]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms MIT Press, second edition, 2001.]]

Digital Library

[3]

Luca de Alfaro, Vishwanath Raman, Marco Faella, and Rupak Majumdar. Code aware resource management. In Proceedings of the 5th ACM international conference on Embedded software (EMSOFT'05) pages 191--202.ACM Press, 2005.]]

Digital Library

[4]

Edsger W. Dijkstra. Cooperating sequential processes. Technical Report EWD-123, Technological University, Eindhoven, the Netherlands, 1965.]]

Digital Library

[5]

Arie N. Habermann. Prevention of system deadlocks. Communications of the ACM 12:373--377, 1969.]]

Digital Library

[6]

James W.Havender. Avoiding deadlock in multi-tasking systems. IBM Systems Journal 2:74--84, 1968.]]

Digital Library

[7]

César Sánchez, Henny B. Sipam, and Zohar Manna. On efficient deadlock avoidance for distributive recursive processes. Submitted for publication.]]

[8]

César Sánchez, Henny B. Sipma, Zohar Manna, Venkita Subramonian, and Christopher Gill. On efficient distributed deadlock avoidance for distributed real-time and embedded systems. In Proc. of the 20th IEEEInt'l Parallel and Distributed Processing Symposium (IPDP'06)IEEE Computer Society Press,2006.]]

Digital Library

[9]

César Sánchez, Henny B. Sipma, Venkita Subramonian, Christopher Gill, and Zohar Manna. Thread allocation protocols for distributed real-time and embedded systems. In Farn Wang, editor, 25th IFIP WG 2.6 International Conference on Formal Techniques for Networked and Distributed Systems (FORTE'05) volume 3731 of LNCS pages 159--173. Springer-Verlag, October 2005.]]

Digital Library

[10]

Douglas C. Schmidt. Evaluating Architectures for Multi-threaded CORBA Object Request Brokers. Communications of the ACM Special Issue on CORBA 41(10), October 1998.]]

Digital Library

[11]

Douglas C. Schmidt, Sumedh Mungee, Sergio Flores-Gaitan, and Aniruddha S. Gokhale. Alleviating priority inversion and non-determinism in real-time CORBA ORB core architectures. In Proc.of the Fourth IEEE Real Time Technology and Applications Symposium (RTAS'98) pages 92--101, June 1998.]]

Digital Library

[12]

Douglas C. Schmidt, Michael Stal, Hans Rohnert, and Frank Buschmann. Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, Volume 2 Wiley & Sons, NewYork, 2000.]]

Digital Library

[13]

Abraham Silberschatz, Peter B. Galvin,and Greg Gagne. Operating System Concepts John Wiley & Sons, Inc., Sixth edition, 2003.]]

Digital Library

[14]

Mukesh Singhal and Niranjan G. Shivaratri. Advanced Concepts in Operating Systems: Distributed, Database, and Multiprocessor Operating Systems McGraw-Hill, Inc., 1994.]]

Digital Library

[15]

William Stallings. Operating Systems: Internals and Design Principles Prentice Hall, Third edition, 1998.]]

Digital Library

[16]

Venkita Subramonian, Guoliang Xing, Christopher D. Gill, Chenyang Lu, and Ron Cytron. Middleware specialization for memory-constrained networked embedded systems. In Proc. of 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04)IEEE Computer Society Press, May 2004.]]

Digital Library

Cited By

Haque WFontaine MVezina A(2017)Adaptive Deadlock Detection and Resolution in Real-Time Distributed Environments2017 IEEE 19th International Conference on High Performance Computing and Communications; IEEE 15th International Conference on Smart City; IEEE 3rd International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC-SmartCity-DSS.2017.74(571-577)Online publication date: Dec-2017
https://doi.org/10.1109/HPCC-SmartCity-DSS.2017.74
Eslamimehr MPalsberg JCheung SOrso AStorey M(2014)Sherlock: scalable deadlock detection for concurrent programsProceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2635868.2635918(353-365)Online publication date: 11-Nov-2014
https://dl.acm.org/doi/10.1145/2635868.2635918
Steghöfer JMandrekar PNafz FSeebach HReif W(2010)On deadlocks and fairness in self-organizing resource-flow systemsProceedings of the 23rd international conference on Architecture of Computing Systems10.1007/978-3-642-11950-7_9(87-100)Online publication date: 22-Feb-2010
https://dl.acm.org/doi/10.1007/978-3-642-11950-7_9
Show More Cited By

Index Terms

Efficient distributed deadlock avoidance with liveness guarantees
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management

Recommendations

Automatic repair for multi-threaded programs with Deadlock/Livelock using maximum satisfiability
ISSTA 2014: Proceedings of the 2014 International Symposium on Software Testing and Analysis

Deadlock-freedom is a major challenge in developing multi-threaded programs, as a deadlock cannot be resolved until one restarts the program (mostly by using manual intervention). To avoid the risk of blocking, a program may use the trylock operations ...
Asynchronous Operations in Distributed Concurrency Control

Distributed locking is commonly adopted for performing concurrency control in distributed systems. It incorporates additional steps for handling deadlocks. This activity is carried out by methods based on wait-for-graphs or probes. The present study ...
Subsystems of Processes with Deadlock Avoidance

A graph-oriented approach to deadlock avoidance, which treates both shared and exclusive locking, has been described [6]. The method is particularly suited for database systems. With enhancements introduced here, the problem of indefimite delay, i.e., ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '06: Proceedings of the 6th ACM & IEEE International conference on Embedded software

October 2006

346 pages

ISBN:1595935428

DOI:10.1145/1176887

General Chairs:
Sang Lyul Min
Seoul National University
,
Wang Yi
Uppsala University

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESWEEK06

Sponsor:

ESWEEK06: Second Embedded Systems Week 2006

October 22 - 25, 2006

Seoul, Korea

Acceptance Rates

Overall Acceptance Rate 60 of 203 submissions, 30%

Upcoming Conference

ESWEEK '24

Sponsor:
sigbed
sigbed
sigbed

Twentieth Embedded Systems Week

September 29 - October 4, 2024

Raleigh , NC , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Haque WFontaine MVezina A(2017)Adaptive Deadlock Detection and Resolution in Real-Time Distributed Environments2017 IEEE 19th International Conference on High Performance Computing and Communications; IEEE 15th International Conference on Smart City; IEEE 3rd International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC-SmartCity-DSS.2017.74(571-577)Online publication date: Dec-2017
https://doi.org/10.1109/HPCC-SmartCity-DSS.2017.74
Eslamimehr MPalsberg JCheung SOrso AStorey M(2014)Sherlock: scalable deadlock detection for concurrent programsProceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2635868.2635918(353-365)Online publication date: 11-Nov-2014
https://dl.acm.org/doi/10.1145/2635868.2635918
Steghöfer JMandrekar PNafz FSeebach HReif W(2010)On deadlocks and fairness in self-organizing resource-flow systemsProceedings of the 23rd international conference on Architecture of Computing Systems10.1007/978-3-642-11950-7_9(87-100)Online publication date: 22-Feb-2010
https://dl.acm.org/doi/10.1007/978-3-642-11950-7_9
Sánchez CSipma HManna Z(2007)A family of distributed deadlock avoidance protocols and their reachable state spacesProceedings of the 10th international conference on Fundamental approaches to software engineering10.5555/1759394.1759413(155-169)Online publication date: 24-Mar-2007
https://dl.acm.org/doi/10.5555/1759394.1759413
Sanchez CSipma HManna Z(2007)Generating Efficient Distributed Deadlock Avoidance Controllers2007 IEEE International Parallel and Distributed Processing Symposium10.1109/IPDPS.2007.370357(1-8)Online publication date: Mar-2007
https://doi.org/10.1109/IPDPS.2007.370357
Sánchez CSipma HManna Z(2007)A Family of Distributed Deadlock Avoidance Protocols and Their Reachable State SpacesFundamental Approaches to Software Engineering10.1007/978-3-540-71289-3_14(155-169)Online publication date: 2007
https://doi.org/10.1007/978-3-540-71289-3_14
Gill CBergamaschi RChoi K(2006)Resource virtualization in real-time CORBA middlewareProceedings of the 4th international conference on Hardware/software codesign and system synthesis10.1145/1176254.1176299(181-186)Online publication date: 22-Oct-2006
https://dl.acm.org/doi/10.1145/1176254.1176299
Sánchez CSipma HGill CManna Z(2006)Distributed priority inheritance for real-time and embedded systemsProceedings of the 10th international conference on Principles of Distributed Systems10.1007/11945529_9(110-125)Online publication date: 12-Dec-2006
https://dl.acm.org/doi/10.1007/11945529_9

View Options

Get Access

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 Table of Contents