Browse Prior Art Database

Protocol for Resource Allocation with Distributed Control

IP.com Disclosure Number: IPCOM000050042D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Kannan, K: AUTHOR [+2]

Abstract

In systems where processes have to compete for a finite number of resources, there is a need for a mechanism to allocate resources and to arbitrate between conflicting demands made by the processes. A class of systems with the above need is characterized by the presence of several processors coupled loosely with one another and by the presence of distributive control among them. For these systems, a protocol is proposed which allows the allocation and arbitration process to take place with good response time and few retries. The protocol will be contrasted to another protocol which relies on locking during the resource acquisition phase.

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

Page 1 of 2

Protocol for Resource Allocation with Distributed Control

In systems where processes have to compete for a finite number of resources, there is a need for a mechanism to allocate resources and to arbitrate between conflicting demands made by the processes. A class of systems with the above need is characterized by the presence of several processors coupled loosely with one another and by the presence of distributive control among them. For these systems, a protocol is proposed which allows the allocation and arbitration process to take place with good response time and few retries. The protocol will be contrasted to another protocol which relies on locking during the resource acquisition phase.

The multiprocessor systems for which we have proposed an allocation and arbitration mechanism have the following definitive properties: (a) There is no central agency to monitor the allocation process and to arbitrate between conflicting requests. (b) A mechanism for processor to processor communication as well as a mechanism for passive broadcasting by a processor to a selective subset of the remaining processors are assumed to be available in the system. (By passive broadcasting we mean the ability to broadcast a message to two or more processors with the knowledge that at least one of the intended recipients received the message. Passive broadcasting is to be contrasted with coercive broadcasting in which a method exists for the message broadcaster to determine if all of the intended recipients received the message.) (c) Finite non-zero delays exist between the time a message is transmitted and the time it is received. (d) Resources are considered to be autonomous in the sense that they are capable of deciding whether they are currently in use or free. This is in contrast to conventional resources whose statuses are maintained by an external agent.

In what follows, two protocols are presented; the first (called A1) is an adaptation of a protocol based on locking resources during the acquisition phase. The second protocol (called A2) does away with the need for locking and is based on probabilistic availability of resources. Protocol A1 1. The requestor (RQR) broadcasts (passively) a request for a a resource (RES) within a class. If the message is received by at least one of the intended recipients, then RQR starts a timer and waits for T1. If it does not get a response in time T1, it rebroadcasts the request or abandons the attempt to acquire a resource. 2. Resources which received the requestor's message and are available, commit themselves to the requestor and send 'resource committed' messages to the requestor. Each such resource starts a timer and waits for T2. If a 'confirm' or 'cancel' message from the requestor is not received within time T2, then a committed resource 'uncommits' itself and becomes av...