Browse Prior Art Database

Communication Protocol for Deadlock Detection in Computer Networks

IP.com Disclosure Number: IPCOM000081074D
Original Publication Date: 1974-Mar-01
Included in the Prior Art Database: 2005-Feb-27

Publishing Venue

IBM

Related People

Chandra, AN: AUTHOR [+3]

Abstract

As the power and impact of data processing continues to increase progressively, an ever concomitant need for information results. In many instances, the requested information is not obtainable from local records. In other instances, the requested information is a summary or composition of information from several different sources.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 10

Communication Protocol for Deadlock Detection in Computer Networks

As the power and impact of data processing continues to increase progressively, an ever concomitant need for information results. In many instances, the requested information is not obtainable from local records. In other instances, the requested information is a summary or composition of information from several different sources.

This situation has led to proposals for creating connected communities of computing facilities to process and access information sources located at disjoint and possibly remote sites. Once the proposal of connecting several computing facilities is made, consideration of the possibility of device extension and resource sharing begins.

These possibilities consist of allowing processes at one installation to access devices and/or resources located at some other installation. It is assumed that the communications and protocol mechanisms which are sufficient for providing these accesses do exist and are available at each of the connected installations. However, one serious problem still arises, generally termed "deadlock" or "deadly embrace".

Deadlock arises when a process, P(a), which has been allocated a resource, R(1), makes a request for resource R(2), while another process, P(b), which has already been allocated resource R(2), has requested resource R(1). When this occurs, neither process can continue until one of them has released its resource.

This problem also exists in a single computing facility, but the effect is much more serious when several independent computing facilities are connected together. The increased resources result from three factors. First, since the total community of users is probably larger, the probability of deadlock is larger. Second, since the processes that are involved may be located at different installations, the information necessary for detection must be available to all systems unless, of course, there is a single central installation that controls allocation. Third, once deadlock has been detected, the appropriate installations must be notified and corrective action must be synchronized.

One solution to this problem is to require that each process request all of the required resources at once regardless of their respective locations. If all requests can be satisfied, the process is allowed to begin execution. However, if one or more resources are not available, no allocations are made and the process must try the requests at a later time. This is so-called "static allocation" and is employed in many single system operating systems, such as OS/360 MFT and OS/360 MVT.

Because of the communication delays inherent in determining whether or not the requests can be satisfied and the increased probability of conflict, a static allocation scheme is not satisfactory for connected independent computing facilities. This is particularly true for processes which require different resources at different times duri...