A concurrent algorithm for avoiding deadlocks in multiprocess multiple resource systems

ABSTRACT

In computer systems in which resources are allocated dynamically, algorithms must be executed whenever resources are assigned to determine if the allocation of these resources could possibly result in a deadlock, a situation in which two or more processes remain in an idle or blocked state indefinitely. In previous research, execution of the process requesting resources is suspended while an algorithm is executed to determine that the assignment could not cause a deadlock. In this paper, an algorithm is used to calculate all possible safe requests before they are made. This algorithm is executed concurrently with other processes between requests for resource allocations. If the determination of all safe requests has been completed and a process makes a request, the calculations required by the resource allocation are trivial.

REFERENCES

• 1: 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]
• 2: HAVENDER, J.W. Avoiding Deadlocks in Multi-tasking Systems. IBM Systems Journal 2,7 ( 1968 ), 74-84.
• 3: 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]
• 4: MURPHY, J.E. Resource Allocation with Interlock Detection in Multi-task Systems. Proc. AFIPS 1968 FJCC, vol. 33, Pt. 2, 1169-1176.
• 5: RUSSELL, R.D. A Model for Deadlock-Free Resource Allocation. Tech. Memos No. 93, 94 and 116 ( June, Oct. and Dec. 1970 respectively ), Stanford Linear Accelerator Center, Computer Group, Stanford University.
• 6: SHOSHANI, A. and E. G. COFFMAN Detection, Prevention and Recovery from Deadlocks in Multiprocess, Multiple Resource Systems. Tech. Rep. No. 80, Dept. of Elec. Eng., Comp. Sc. Lab., Princeton University, ( Oct. 1969).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Deadlock avoidance

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Pricing and resource allocation

General Terms:
Algorithms, Design, Management