The Deadlock problem: a classifying bibliography

ABSTRACT

The desire for a better utilisation of resources and an acceleration of computing introduced the concept of parallelism with all its difficulties. Soon the danger of eternal delays of processes was discovered and called deadlock. For almost twenty years a lot of publications have dealt with problems considering deadlocks or their environment.Here we want to give a classification of our collected publications. We do not claim that this collection is complete in any sense, but we hope to have found essential articles (underlined) for nearly all the different topics fitting under the title "Deadlock".This classification regards different aspects of the problem and cannot always be given unambigiously so that many publications are listed several times. We would appreciate to get knowledge of other interesting articles or textbooks to this theme.

REFERENCES

• 1: {Ahu 79} V. Ahuja / Algorithm to Network States for Deadlock / IBM Research and Development, Vol. 23, No. 1, January 1979 C3, Dl
• 2: {Ahu 80} V. Ahuja / Determining Deadlock Exposure for a Class of Store and Forward Communication Networks / IBM Research and Development, Vol. 24, No. 1, January 1980 C3, D2
• 3: {Ba 82} P. Bathelt / Vergleich von Synchronisationsmechanismen / Arbeitsbericht des Insituts für mathematische Maschinen und Datenverarbeitung (Informatik), Band 15, Number 3, Universität Erlangen Nürnberg, May 1982, 1--38, (dt.) E2
• 4: {BiUn 79} P. Bittmann, K. Unterauer / Models and Algorithms for Deadlock Detection / in "Operating Systems: Theory and Practice", edited by D. Lanciaux, North-Holland Publishing Company, 1979, 101--111 C2, D1
• 5: {BłBo 81} J. Błazewicz, D. P. Bovet / Detection and Avoidance in Store and Forward Communication Networks / in Performance '81 editor: F. J. Kylstra, North-Holland Publishing Company, 1981 C3, D1, D2
• 6: {ChBoTr 74} D. D. Chamberlin, R. F. Boyce, I. L. Traiger / A Deadlock-free Scheme for Resource Locking in a Data-Base Environment / Information Processing 74, North-Holland Publishing Company, 1974 C2, D3, E3
• 7: A. Chesnais , E. Gelenbe , I. Mitrani, On the modeling of parallel access to shared data, Communications of the ACM, v.26 n.3, p.196-202, March 1983 [doi>10.1145/358061.358073]
• 8: 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]
• 9: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 10: {Da 72} D. W. Dawies / The Control of Congestion in Packet-Switching Networks / IEEE TRansactions on Communications, Vol. COM-20, No. 3, June 1972, 546--550 C3
• 11: {Dad 81} P. Dadam / Einführung in die Synchronisation von Datenbank-Systemen / Elektronische Rechenanlagen, 23. Jahrgang, Heft 1, 1981, 4--12, (dt.) E2
• 12: {De 74} R. Devillers / Prévention des interblocages dans un modèle à organigrammes / Ph.D. thèse, Université Libre de Bruxelles, Faculté des Sciences, 1974 (fr.) C1, D3
• 13: R. Devillers, Game interpretation of the deadlock avoidance problem, Communications of the ACM, v.20 n.10, p.741-745, Oct. 1977 [doi>10.1145/359842.359854]
• 14: {DeLa 78} R. E. Devillers, P. E. Lauer / A General Mechanism for Avoiding Starvation with Distributed Control / Information Processing Letters, Vol. 7, No. 3, January 1978 E1
• 15: {Di 68} E. W. Dijkstra / Cooperating Sequential Processes / Academic Press, New York, 1968 C1, E2
• 16: {Di 71} E. W. Dijkstra / Hierarchical Ordering of Sequential Processes / Acta Informatica, Vol. 1, No. 2, October 1971, 115--138 C1, E2
• 17: Rafael O. Fontao, A concurrent algorithm for avoiding deadlocks in multiprocess multiple resource systems, Proceedings of the third ACM symposium on Operating systems principles, p.72-79, October 18-20, 1971, Palo Alto, California, United States [doi>10.1145/800212.806502]
• 18: {GeRe 83} J. Geisberger, A. Reiser / Sperrprotokolle für Transaktionen mit Prioritäten / Technische Universität München, interner Bericht, TUM-I8304, February 1983, (dt.) C2, D1
• 19: {Gi 80} H. Giesen / Ein effizienter Algorithmus zur Vermeidung von Deadlocks / EWH Koblenz, Seminar für Infomatik, interner Bericht 4/80, 1980, (dt.) C1, D3
• 20: {GISh 80} V. D. Gligor, S. H. Shattuck / On Deadlock Detection in Distributed Systems / IEEE Transactions on Software Engineering, Vol. SE-6, No. 5, September 1980 C2, D1
• 21: {Go 78} M. Gold / Deadlock Prediction: Easy and Difficult Cases / SIAM Journal of Comput., Vol. Y, No. 3, August 1978, 320--336 A, C1, D2, D3
• 22: {GrHomObKo 81} J. Gray, P. Homan, R. Obermarck, H. Korth / A Straw Man Analysis of Waiting and Deadlock / IBM Research Laboratory, San Jose, California, RJ3066, 1981 F
• 23: 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]
• 24: A. Nico Haberman, A new approach to avoidance of system deadlocks, Operating Systems, Proceedings of an International Symposium, p.163-170, April 23-25, 1974
• 25: {Ha 77} A. N. Habermann / System Deadlocks / in "Current Trends in Programming Methodology", editors: K. M. Chandy, R. T. Yeh, Prentice Hall, 1978 C1, D3
• 26: {Hav 68} J. W. Havender / Avoiding Deadlock in Multitasking Systems / IBM Systems Journal, No. 2, 1968 C1, D3
• 27: {He 72} P. G. Hebalkar / A Graph Model for Analysis of Deadlock Prevention in Systems with Parallel Computations / Information Processing '71, North-Holland Publishing Company, 1972, 498--503 C1, D2
• 28: {HoRa 82} G. S. Ho, C. V. Ramamoorthy / Protocols for Deadlock Detection in Distributed Database Systems / IEEE Transactions on Software Engineering, Vol. SE-8, No 6, November 1982, 554--557 C2, D1, E3
• 29: Richard C. Holt, Comments on prevention of system deadlocks, Communications of the ACM, v.14 n.1, p.36-38, Jan. 1971 [doi>10.1145/362452.362486]
• 30: Richard C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys (CSUR), v.4 n.3, p.179-196, Sept. 1972 [doi>10.1145/356603.356607]
• 31: {Holz 82} G. J. Holzmann / A Theory of Protocol Validation / IEEE Transactions on Computers, Vol. C-31, No. 8, August 1982, 730--738 C3, D2, E2
• 32: {HofSch 82} J. Hofmann, H. Schmutz / Performance Analysis of Suspend Locks in Operating Systems / IBM Research and Development, Vol. 26, No 2, March 1982 F
• 33: John H. Howard, Jr., Mixed solutions for the deadlock problem, Communications of the ACM, v.16 n.7, p.427-430, July 1973 [doi>10.1145/362280.362290]
• 34: {IbKa 82} T. Ibaraki, T. Kameda / Deadlock-Free Systems for a Bound Number of Processes / IEEE Transactions on Computers, Vol. C-31, No. 3, March 1982, 188--193 C1, D2
• 35: Tiko Kameda, A polynomial-time test for the deadlock-freedom of computer systems, Proceedings of the 3rd GI-Conference on Theoretical Computer Science, p.282-291, March 28-30, 1977
• 36: Tiko Kameda, Testing Deadlock-Freedom of Computer Systems, Journal of the ACM (JACM), v.27 n.2, p.270-280, April 1980 [doi>10.1145/322186.322192]
• 37: Krishna Kant , Abraham Silberschatz, On the generalized critical region construct, ACM SIGOPS Operating Systems Review, v.16 n.3, p.4-16, July 1982 [doi>10.1145/850723.850724]
• 38: {KiLa 83} W. Kieling, G. Landherr / A Quantitative Comparison of Lockprotocols for Centralized Database / Technische Universität München, Bericht TUM-I8302, January 1983 C2, E1, E3
• 39: Henry Francis Korth, Locking protocols: general lock classes and deadlock freedom, 1981
• 40: Stanley A. Kurzban , Thomas S. Heines , Anthony P. Sayers, Operating systems principles (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1984
• 41: Yat Sang Kwong, On reductions and livelocks in asynchronous parallel computation., 1978
• 42: {Kw 78b} Y. S. Kwong / Livelocks in Parallel Programs - Part I: Basic Concepts, Classification and Proof Techniques; Part II: The Effects of Fair Scheduling Disciplines / McMaster University, Hamilton, Canada, reports 78-CS-15, 78-CS-16, August 1978 E1, E2
• 43: {Li 73} R. J. Lipton / On Synchrnous Primitive Systems / Departement of Computer Science, Carnegie - Mellon University, Pittsburgh, 1973 E2
• 44: 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 [doi>10.1145/509404.509423]
• 45: {Lo 80} D. B. Lomet / Subsystems of Processes with Deadlock Avoidance / IEEE Transactions on Software Engineering, Vol. SE-6, NO. 3, May 1980, 297--304 C2, D3, E1
• 46: Harold Lorin , Harvey M. Deitel, Operating Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1981
• 47: Stuart E. Madnick , John J. Donovan, Operating Systems, McGraw-Hill, Inc., New York, NY, 1974
• 48: {MeMun 79} D. A. Menasce, R. R. Muntz / Locking and Deadlock Detection in Distributed Data Bases / IEEE Transactions on Software Engineering, Vol. SE-5, No. 3, May 1979, 195--202 C2, D1, E3
• 49: Toshimi Minoura, Deadlock avoidance revisited, Journal of the ACM (JACM), v.29 n.4, p.1023-1048, Oct. 1982 [doi>10.1145/322344.322351]
• 50: {MoSeiZö 83} M. Mosen, H. Seiwert, D. Zöbel / Gegenüberstellung verschiedener Verfahren zur Deadlockvermeidung / EWH Koblenz Seminar für Informatik, report in preparation, (dt.) F
• 51: {Mu 68} J. E. Murphy / Resource Allocation with Interlock Detection in a Multitask System / Proceedings AFIPS, 1968, FJCC, vol. 33, part II, 1168--1176 D1
• 52: {Ne 79} G. Newton / Deadlock Prevention, Detection and Resolution: An Annotated Bibliography / ACM Operating Systems Review, Vol. 13, No. 2, April 1979, 33--44 A
• 53: {Ob 80} R. Obermarck / Global Deadlock Detection Algorithm / IBM Research Laboratory, San Jose, Cal., RJ2845, 1980 C2, D1
• 54: Christos H. Papadimitriou, A theorem in database concurrency control, Journal of the ACM (JACM), v.29 n.4, p.998-1006, Oct. 1982 [doi>10.1145/322344.322349]
• 55: Christos H. Papadimitriou, Theory of concurrency control, Proceedings of the 6th GI-Conference on Theoretical Computer Science, p.35-47, January 05-07, 1983
• 56: D. L. Parnas , A. N. Habermann, Comment on deadlock preventive method, Communications of the ACM, v.15 n.9, p.840-841, Sept. 1972 [doi>10.1145/361573.361586]
• 57: {Ri 77} L. Richter / Betriebssysteme / Teubner Studienbücher Informatik, Stuttgart, 1977, (dt.) B
• 58: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 59: {RieSm 82} D. R. Ries, G. C. Smith / Nested Transactions in Distributed Systems / IEEE Transactions on Software Engineering, Vol. SE-8, No. 3, May 1982, 167--172 C3, D1, E3
• 60: {Sc 78} W. Schulze / Ein graphentheoretisches Verfahren zur kostenminimalen Beseitigung von Prozeßverklemmungen / Elektronische Rechenanlagen, 21. Jahrgang, Heft 5, 1979, 217--225, (dt.) D1
• 61: {Si 79} J. Sifakis / Le Controle de Systèmes Asynchrones: Concepts, Proprietés, Analyse Statique / Thèse d'Etat, Institute Nationale Polytechnique de Grenoble, 1979(fr.) E2
• 62: {Si 83} J. Sifakis / A Note on Deadlocks in CA-Systems / EATCS - Bulletin, No. 20, June 1983, 153--159 C3, D2, E2
• 63: {SilKe 82} A. Silberschatz, Z. M. Kedem / A Family of Locking Protocols for Database Systems that are Modeled by Directed Graphs / IEEE Transactions on Software Engineering, Vol. SE-8, No. 6, November 1982, 558--562 C2, D1, E3
• 64: {SoMa 82} E. Soisalon-Soininen, H. Mannila / On Deadlock Detection in Distributed and Centralized Locking / Forschungsbericht der Universität Karlsruhe, Institut für angewandte Informatik, Bericht 118, October 1982 C2, D2, E3
• 65: Alfred Z. Spector , Peter M. Schwarz, Transactions: a construct for reliable distributed computing, ACM SIGOPS Operating Systems Review, v.17 n.2, p.18-35, April 1983 [doi>10.1145/1041478.1041481]
• 66: Eugene W. Stark, Semaphore primitives and starvation-free mutual exclusion, Journal of the ACM (JACM), v.29 n.4, p.1049-1072, Oct. 1982 [doi>10.1145/322344.322352]
• 67: Murat Mehmet Tanik, A graph model for deadlock prevention., 1978
• 68: Sam Toueg, The design of deadlock- and livelock-free packet switching networks, 1979
• 69: Dionysios C Tsichritzis, Operating systems, Academic Press, Inc., Orlando, FL, 1974
• 70: {We 82} G. Weck / Prinzipien und Realisierung von Betriebssystemen / Teubner Studienbücher Informatik, Stuttgart, 1982, (dt.) B
• 71: {YaPaKu 79} M. Yannakakis, C. H. Papadimitrious, H. T. Kung / Locking Policies: Safety and Freedom from Deadlock / Proc. 20th Ann. IEEE Symp. on Foundations of Computer Science, San Juan, Puerto Rico, 1979 C2, E3
• 72: {Ze 76} A. Zeyn / Algorithmen zur Deadlock-Vermeidung / Dissertation, Universität Dortmund, Abteilung Informatik, Bericht NO. 22/76, 1976, (dt.) C1, D3
• 73: {Zi 80} H. Zima / Betriebssysteme, Parallele Prozesse / Bibliographisches Institut, Reihe Informatik, Band 20, Mannheim, 2. ed., 1980, (dt.) B
• 74: {Zö 83} D. Zöbel / Zur Integration der Deadlockvermeidung in Betriebssysteme / EWH Koblenz, Seminar för Informatik, interner Bericht 1/83, (dt.) A, C1, D3, E1