Browse Prior Art Database

Deadlock Free Resource Allocation in Networks

IP.com Disclosure Number: IPCOM000076913D
Original Publication Date: 1972-May-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Collier, WW: AUTHOR

Abstract

Deadlock prevention in a computing system requires centralized resource allocation, but efficient resource allocation with the use of a network requires that resource allocation decisions be made at many different nodes of the network. The conflict between these two needs is resolved below.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 35% of the total text.

Page 1 of 3

Deadlock Free Resource Allocation in Networks

Deadlock prevention in a computing system requires centralized resource allocation, but efficient resource allocation with the use of a network requires that resource allocation decisions be made at many different nodes of the network. The conflict between these two needs is resolved below.

For the execution of a job in the computing system, the user has requested resources needed by the job in the job control language of the computer system. In response to a request for resources, the resource allocator in the system control program tests to see whether or not the requested resources are available prior to initiation of execution of each job, and whether or not there is a sequence of jobs which can safely use the system resources without danger of a deadlock. A sequence of jobs: JOB1, JOB2, ..., JOBN is called a Safe Sequence providing that, if every job in the next instant requests all the resources it claimed at initiate time, then JOB1, using the resources it now holds plus those currently free, can run to completion and so free up the resources it now holds; and then JOB2, using the resources it now holds plus those currently free plus those held by JOB1, can run to completion and so free up the resources it now holds; and then JOB3, ..., etc.

If a safe sequence exists then the system is assured that in the worst possible case of requests for resources, namely that every program asks for everything it has claimed, then the system can still find a way of running to completion all jobs which are currently on the system. DEFINITION.

Denote by R(A) the resource allocator for resource A. The resources of a network are partitioned by the resource allocators. The set of all resources in the system is divided into groups such that: (1) each system resource is assigned to only one resource allocator (RA), and (2) every resource in a given group can only be allocated by the one resource allocator assigned to that group.

To allocate resources across groups requires that there exist one or more levels of resource allocator coordinators (RAC's). A first level RAC coordinates RA's; each first level RAC is assigned to two or more RA's. A higher level RAC (if any) coordinates other RAC's, and each high level RAC is assigned to two or more RAC's in the next lower level. Thus a tree of RAC's results with the RA and their respective groups being the leaves of the tree network.

For any given set of resources, a root RAC of the tree network is entered to coordinate the allocation of the system resources uniquely grouped in the tree.

Jobs in computer systems may be classified as either local or distributed. Local jobs are those that use resources which fall entirely within a single resource group and hence are allocated under the jurisdiction of a single resource allocator. Distributed jobs are jobs which use resources in two or more groups in the tree network. RAC's are aware only of distributed jobs....