Game interpretation of the deadlock avoidance problem

ABSTRACT

The deadlock avoidance problem may be defined informally as the determination, from some a priori information about the processes, resources, operating system, etc., of the “safe situations” which may be realized without endangering the smooth running of the system. When each process specifies its future needs by a flowchart of need-defined steps, a global approach to the phenomenon and its interpretation as a game between the operating system and the processes allows formalization of risk and safety concepts. The bipartite graph representation of this game may then be used to construct explicitly the set of safe states and to study their properties.

REFERENCES

• 1: Devillers, R. Pr6vention des interblocages dans un module organigrammes. Ph.D. Th., Universit6 Libre de Bruxelles, Brussels, 1974.
• 2: 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]
• 3: Habermann, A.N. The equivalence of some deadlock-avoidance criteria. Tech. Rep. 52, U. of Newcastle upon Tyne, Newcastle upon Tyne, England, 1973.
• 4: Hebalkar, P.G. Deadlock-free sharing of resources in asynchronous systems. Sc.D. Diss. M.I.T. Cambridge, Mass., 1970.
• 5: 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]
• 6: Shoshani, A., and Coffman Jr., E.G. Sequencing tasks in multiprocess, multiple resource systems to avoid deadlocks. Tech. Rep. 78, Princeton U., Princeton, N.J., 1969.

INDEX TERMS

Keywords:
dead-lock, deadlock avoidance, deadly embrace, flowchart, interlock, multi-programming, operating system, resource allocation, time-sharing