A practical approach to managing resources and avoiding deadlocks

ABSTRACT

Resource scheduling and allocation can be expensive with regard to time and space in multiprogramming or time-sharing environments involving large numbers of tasks and resources with conflicting requirements. Detection and/or prevention of deadlocks can require massive amounts of additional overhead if efficient usage of resources is to be maintained. A resource management program is described which uses linked lists along with other techniques to overcome a large portion of this overhead. The program, which is currently running as part of a large scale general purpose operating system, keeps resources relatively active but does not detect or prevent all deadlocks in its implemented state. Certain changes, which would permit more comprehensive levels of deadlock prevention/detection at additional cost, have not been incorporated in the running system due to the infrequency of deadlock situations.

REFERENCES

• 1: Abell, V., Rosen, S., and Wagner, R. Scheduling in a general purpose operating system. Proc. AFIPS 1970 FJCC, Vol. 37, AFIPS Press, Montvale, N.J., pp. 89-96.
• 2: 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]
• 3: Collier, W.W. System deadlocks. Tech. Rep. No. TR00.1796- l, IBM Syst. Develop. Div., IBM Corp., Poughkeepsie, N.Y., Aug. 1971.
• 4: Collins, Arthur A. Private communication, 1972.
• 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: Havender, J.W. Avoiding deadlock in multi-tasking systems. IBM Systems J. 7, 2 (1968), 74-84.
• 7: 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]
• 8: Holt, Richard C. On deadlock in computer systems. Tech. Rep. CSRG-6, U. of Toronto, Computer Syst. Res. Group, Apr. 1971.
• 9: Iazeolla, G.G. Deadlock-free sequencing for multiple resources allocation in multiprocess systems: optimization perspectives. Rep. N.1-02, Universith di Roma, Insituto di Automatica, Rome, Italy, 1971.
• 10: Murphy, J.E. Resource allocation with interlock detection in a multi-task system. Proc. AFIPS 1968 FJCC, Vol. 33, P. 2, AFIPS Press, Montvale, N.J., pp. 1169-1176.

INDEX TERMS

Keywords:
deadlock, deadly embrace, multiprocessing, multiprogramming, resource allocation, resource management, scheduling, time-sharing