Efficient distributed deadlock avoidance with liveness guarantees

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 , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: Luca de Alfaro , Vsihwanath Raman , Marco Faella , Rupak Majumdar, Code aware resource management, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086265]
• 4: Edsger Wybe Dijkstra, Cooperating Sequential Processes, Technical Report EWD-123, 1965
• 5: 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]
• 6: James W.Havender. Avoiding deadlock in multi-tasking systems. IBM Systems Journal 2:74--84, 1968.
• 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.
• 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.
• 10: Douglas C. Schmidt, Evaluating architectures for multithreaded object request brokers, Communications of the ACM, v.41 n.10, p.54-60, Oct. 1998 [doi>10.1145/286238.286248]
• 11: D. Schmidt , S. Mungee , S. Flores-Gaitan , A. Gokhale, Alleviating Priority Inversion and Non-Determinism in Real-Time CORBA ORB Core Architectures, Proceedings of the Fourth IEEE Real-Time Technology and Applications Symposium, p.92, June 03-05, 1998
• 12: Douglas C. Schmidt , Hans Rohnert , Michael Stal , Dieter Schultz, Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, John Wiley & Sons, Inc., New York, NY, 2000
• 13: Abraham Silberschatz , Peter Baer Galvin , Greg Gagne, Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 2001
• 14: Mukesh Singhal and Niranjan G. Shivaratri. Advanced Concepts in Operating Systems: Distributed, Database, and Multiprocessor Operating Systems McGraw-Hill, Inc., 1994.
• 15: William Stallings, Operating systems (3rd ed.): internals and design principles, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 16: Middleware Specialization for Memory-Constrained Networked Embedded Systems, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), p.306, May 25-28, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

General Terms:
Algorithms, Reliability, Theory

Keywords:
deadlock avoidance, distributed algorithms, scheduling