Deadlock detection and prevention mechanism for a computer system

Claims

We claim:

1. In combination with a multiprogram computer system having a plurality of resources and also having a plurality of processes, each process capable of assuming a running, ready, wait or suspended state, and having an extended semaphore mechanism associated with an event whose occurrence is the detection in any of a first plurality of processes of a condition which is significant to any of a second plurality of processes, a deadlock detection system for detecting the situation wherein any first of said processes is waiting for any one or a plurality of said resources which can never become available to said any first of said processes, said deadlock detection system comprising:

(a) first means for establishing on behalf of said any of said second processes an interest in at least one event occurrence in any of said first plurality of processes;

(b) second means, coupled to said first means, for specifying the condition which constitutes an event occurrence of interest to any of said second processes;

(c) third means, coupled to said first and second means, for monitoring on behalf of said any of said second plurality of processes for said event occurrence, in said any of said first plurality of processes; and

(d) fourth means coupled to said first and second means for notifying said first means that said one event occurrence in said any of said first plurality of processes cannot occur.

2. The deadlock detection system as recited in claim 1 including fifth means coupled to said first, third and fourth means, for preventing the establishment on behalf of any of said second processes an interest in said one event occurrence of said any of said first plurality of processes.

3. A deadlock detection mechanism for detecting in a computer system the situation wherein any of a first plurality of processes is waiting for any of a first plurality of resource which can never become available to said any first of said processes, said deadlock detection mechanism comprising:

(a) first means for requesting on behalf of said any first of said processes the assignment of any of a first plurality of resource to said any first of said processes;

(b) second means, coupled to said first means, for recording the assignment of any of a first plurality of resource if said any of a first plurality is currently available;

(c) third means, coupled to said second means, for notifying said any first of said processes of assignment of a resource of said first plurality of resources;

(d) fourth means, coupled to said first means, for causing said any first of said processes to assume the wait-state and to wait for the availability and assignment of requested said any of a first plurality of resource if all resources of said first plurality of resources are assigned to any second of said processes and not currently available;

(e) fifth means, coupled with said second means, for requesting the release of assignment of said resource of a first plurality of resources by said any second of said processes to which it is currently assigned;

(f) sixth means, coupled to said second and fifth means, for causing any first of said processes, which has been waiting upon the availability for assignment of any of a first plurality of resource, to assume the ready-state if said any of a first plurality of resource becomes available for assignment;

(g) seventh means, coupled to said second and fourth means, for examining the resource/process relationships of any process currently waiting upon the availability of a resource and any resource currently assigned to a process;

(h) eighth means, coupled to said seventh means, for determining when all said second of said resources are waiting upon the availability of any of a second plurality of resource which are currently assigned directly to said any first of said processes or which are assigned indirectly through third, fourth, etc. process/waiting/resource-assignment pairs to said any first of said processes which circular relationship would constitute a deadlock; and,

(i) ninth means, coupled to said eighth means, for notifying said any first of said processes of deadlock detection and the non assignment of any of a first plurality of resource.

4. In combination with a multiprogramming computer system having a plurality of resources and also having a plurality of processes, each process capable of assuming a running, ready, wait or suspended state and each resource capable of assuming a shareably assigned, exclusively assigned or available state a deadlock detection system for detecting the situation wherein any first of said processes is waiting for a resource which can never become available to said any first of said processes said deadlock detection system comprising:

(a) first means for requesting on behalf of said any first of said processes the shared assignment or exclusive assignment of any first of said resources to said any first of said processes;

(b) second means, coupled with first means for recording the exclusive assignment of said any first of said resources to said any first of said process if said any first of said resources is currently available for exclusive assignment;

(c) third means, coupled with first means, for recording the shared assignment of said any first of said resources to said any first of said processes if said any first of said resources is currently available for shareable assignment;

(d) fourth means, coupled with first means, for notifying said first of said processes of assignment of said any of said resources;

(e) fifth means, coupled to said first means, for causing said any first of said processes to assume the waitstate and to wait for the availability and assignment of requested said any first of said resources if said any first of said resources is assigned exclusively to any second of said processes and not currently available for either exclusive or shared assignment;

(f) sixth means, coupled to said first means, for causing said any first of said processes to assume the wait-state and to wait for the availability and assignment of requested said any first of said resources if said any first of said resources is assigned shareably to any one or several second of said processes and not currently available for exclusive assignment;

(g) seventh means, coupled to said second and third means, for requesting release of said assignment of said any second of said processes to which it is currently assigned;

(h) eighth means, coupled to said second, third and seventh means, for causing any first of said processes, which has been waiting upon the availability for assignment of said any first of said resources to assume the ready-state if said any first of said resources becomes available for assignment;

(i) ninth means, coupled with said second, third, fifth and sixth means for examining the process/resource relationships of any process currently waiting upon the availability of a resource and any resource currently assigned to a process;

(j) tenth means, coupled to said ninth means, for determining when said second of said processes is waiting upon the availability of any second said resource which is currently directly assigned to said any first of said processes or which is assigned indirectly through third, fourth, etc., process-waiting resource assigned pairs to said any first of said processes which circular relationship would constitute a deadlock; and,

(k) eleventh means, coupled to said tenth means, for notifying said any first process of deadlock detection and the non assignment of said first of said resources.

5. The combination as recited in claim 3 including

tenth means for determining whether said first of said processes, when waited, would be waiting for either a specific resource or any resource within a specific resource class which specific resource or all resources within the specific resource class can never become available to said any first of said processes.

6. The combination as recited in claim 4 including

twelfth means for determining whether said first of said processes, when waited, would be waiting for either a specific resource or any resource within a specific resource class which specific resource or all resources within the specific resource class can never become available to said any first of said processes.

7. A firmware/hardware deadlock detection system for a multiprogram computer system having semaphore architecture for interprocess communication and control, and having plural resource classes each with plural interchangeable resource objects, and plural processes each capable of assuming a running, ready, wait or suspended state, which comprises:

(a) event status requesting means responsive to said plural processes for communicating on behalf of said plural processes a request for exclusive access to resource object members of said plural resource classes;

(b) event status detection means responsive to said requesting means for defining a set of resource objects in a requested one of said plural resource classes and indicating the availability of each member of said set;

(c) process control means responsive to said requesting means for assigning a requesting one of said plural processes to a wait state;

(d) resource assignment means responsive to said detection means for exclusively assigning a member of said set to said requesting one of said plural processes; and

(e) deadlock detection means in electrical communication with said assignment means and said process control means for signalling the occurrence of a deadlock condition in accordance with a logic decision tree wherein each member of said set is assigned to processes waiting on resource classes which in turn are assigned to waiting processes, and each process in the decision tree of each member of said set is in a wait state.

8. A firmware/hardware deadlock detection system for a computer system having semaphore architecture for interprocess communication and control, and having plural resource classes each with a reuseable resource object and plural processes each capable of assuming a running, ready, wait or suspended state, which comprises:

(a) event status requesting means in electrical communication with said plural processes for communicating on behalf of said plural processes exclusive or shared access requests for said resource object classes;

(b) event status detection means responsive to said requesting means for indicating the availability of any requested one of said plural resource classes for exclusive and shared assignment;

(c) process control means responsive to said requesting means for assigning a requesting one of said plural processes to a wait state;

(d) resource assignment means responsive to said detection means for exclusively or sharedly assigning said any requested one of said plural resource classes; and

(e) deadlock detection means in electrical communication with said assignment means and said process control means for indicating the occurrence of a deadlock condition if said any requested one of said plural resource classes is assigned to a second of said plural processes waiting on a second of said plural resource classes assigned to said any requesting one process, or if said any requested one of said plural resource classes is assigned to a set of said plural processes and, in accordance with a logic decision tree wherein each member of said set is waiting on resource classes which in turn are assigned to waiting processes, each process in the decision tree of each member of said set is in a wait state.

9. A firmware/hardware deadlock detection system for a multiprogram computer system having semaphore architecture for interprocess communication and control, and having plural resource classes each with plural interchangeable resource objects, and plural processes each capable of assuming a running, ready, wait or suspended state, which comprises:

(a) event status requesting means in electrical communication with said plural processes for communicating on behalf of said plural processes shared access requests for resource object members of said plural resource classes;

(b) event status detection means responsive to said requesting means for defining a set of resource objects in a requested one of said plural resource classes and indicating the availability of each member of said set for a shared assignment;

(c) process control means responsive to said requesting means for assigning a requesting one of said plural processes to a wait state;

(d) resource assignment means responsive to said detection means for sharedly assigning a member of said set to said requesting one of said plural processes; and

(e) deadlock detection means in electrical communication with said assignment means and said process control means for signalling the occurrence of a deadlock condition in accordance with a logic decision tree wherein each member of said set is assigned to processes waiting on resource classes which in turn are assigned to waiting processes, and each process in the decision tree of each member of said set is in the wait state.

10. A firmware/hardware method for detecting a deadlock condition in a multiprogram computer system having semaphore architecture for interprocess communication and control, and having plural resource classes each comprised of plural interchangeable resource object members, and plural processes each capable of assuming a running, ready, wait or suspended state, which comprises:

(a) upon a requesting one of said plural processes seeking access to a resource object member of a first of said plural resource classes, examining a state queue of said first class to detect the availability of class members;

(b) if at least one member of said first class is available, assigning said one member to said requesting one process;

(c) if no member of said first class is available, examining an assignment queue of any first member of said first class to identify any second of said plural processes to which said first member is assigned;

(d) comparing said requesting one process and said second process to detect an equivalence;

(e) if an equivalence occurs, examining said first class for any second member, and if said second member is not detected, indicating a deadlock condition;

(f) if said second member is detected, examining an assignment queue of said second member to detect any third of said plural processes to which said second member is assigned and repeating said method beginning at step (d) with said third process replacing said second process;

(g) if an equivalence is not detected at step (e), examining the state queue of said second process to detect a wait state or a running state;

(h) if a wait state is detected, examining the assignment queue of said second process to detect an any second of said plural resource classes which said second process is waiting upon;

(i) repeating said method beginning at step (a) with said second class replacing said first class, and assigning said requesting one process to a wait state if a process to which any member of said second class is assigned is in a running state, and otherwise indicating the occurrence of a deadlock condition;

(j) if a deadlock condition is detected in step (i), examining said first class for an any third member and indicating the occurrence of a deadlock condition if said first class is exhausted;

(k) if said first class is not exhausted, repeating said method beginning with step (c) with said third member replacing said first member; and

(l) if a running state is detected at step (g), assigning said requesting one process to a wait state pending the availability of any member of said first class.

11. A firmware/hardware method of detecting a deadlock condition in a multiprogram computer system having a semaphore architecture for interprocess communication between a plurality of processes each capable of assuming a running, ready, wait or suspended state, said computer system further having a plurality of resource classes each with a reuseable resource object, which comprises:

(a) upon one of said plurality of processes requesting either exclusive or shared access to a first resource object, examining the state queue of said first resource object to detect an available or an assigned state;

(b) if said first resource object is available, assigning said first resource object to said one process;

(c) if said first resource object is assigned, examining an assignment queue of said first resource object to identify any second of said plurality of processes to which said first resource object is assigned;

(d) comparing said one process to said second process, and indicating a deadlock condition to restart said one process if an equivalence occurs;

(e) if an equivalence does not occur, examining the state queue of said second process to detect a running or a wait state;

(f) if a running state is detected, examining the assignment queue of said first resource object to detect any third of said plurality of processes to which said first resource object is assigned, and if said third process is detected, repeating said method beginning at step (d) with said third process replacing said second process;

(g) if said third process is not detected, assigning said one process to a wait state pending the availability of said first resource object;

(h) if a wait state is detected at step (e), examining the assignment queue of said second process to detect a second resource object upon which said second process is waiting and repeating said method beginning at step (c) with said second resource object replacing said first resource object;

(i) if a deadlock condition is not detected in step (h), examining the assignment queue of said first resource object to detect an assignment to any fourth of said plurality of processes and repeating said method beginning at step (d) with said fourth process replacing said second process; and

(j) if an assignment to said fourth process is not detected, assigning said one process to a wait state pending the availability of said first resource object.

12. A firmware/hardware method of detecting a deadlock condition in a multiprogram computer system having a semaphore architecture for interprocess communication between a plurality of processes each capable of assuming a running, ready, wait or suspended state, said computer system further having a plurality of resource classes each with plural interchangeable resource objects, which comprises:

(a) upon any first of said plurality of said processes requesting a shared access to a member of a first set of resource objects in any first of said plurality of resource classes, examining the state queue of said first resource class to detect the availability of each member of said first set;

(b) if at least one member of said first set is available, assigning said one member to said first process;

(c) if no member of said first set is available, examining an assignment queue of any first member of said first set to identify any second of said plurality of processes to which said first member is assigned;

(d) comparing said first process and said second process to detect an equivalence;

(e) if an equivalence is not detected, examining the state queue of said second process to detect a running or wait state;

(f) if a wait state is detected, examining the assignment queue of said second process to identify any second of said plurality of resource classes upon which said second process is waiting and repeating said method beginning at step (a) with said second resource class replacing said first resource class;

(g) if a deadlock condition is not detected in step (f), examining the assignment queue of said first member to detect and identify an any third process to which said first member is assigned;

(h) assigning said first process to a wait state if said third process is not detected, and repeating said method beginning with step (d) with said third process replacing said second process if said third process is detected;

(i) if a deadlock condition is detected at step (f), examining said first set to detect and identify an any second member, and indicating the occurrence of a deadlock condition to restart said first process if said second member is not detected;

(j) if said second member is identified at step (i), examining the assignment queue of said second member to identify an any fourth of said plurality of processes to which said second member is assigned and repeating said method beginning at step (d) with said second member and said fourth process respectively replacing said first member and said second process;

(k) if an equivalence is detected in step (d), examining said first set to detect and identify an any third member of said first set, and indicating a deadlock condition to restart said first process if said third member is not detected;

(l) if said third member is identified, examining the assignment queue of said third member to identify an any fifth of said plurality of processes to which said third member is assigned, and repeating said method beginning at step (d) with said third member and said fifth process respectively replacing said first member and said second process;

(m) if a running state is detected at step (e), examining the assignment queue of said first member to detect an any sixth of said plurality of processes to which said first member is assigned, and assigning said first process to a wait state if said sixth process is not detected; and

(n) if said sixth process is detected at step (m), repeating said method beginning with step (d) with said sixth process replacing said second process.

RELATED APPLICATIONS

The following applications are related the instant application.

1. "Buffer Store" invented by J. L. Curley, T. J. Donahue, W. A. Martland, and B. S. Franklin, filed on Oct. 5, 1972 having Ser. No. 295,301 and assigned to the same assignee named herein, now U.S. Pat. No. 3,820,078.

2. "Variable Masking for Segmented Memory" invented by Wallace A. Martland and John L. Curley, filed on Oct. 5, 1972 having Ser. No. 295,303 and assigned to the same assignee named herein, now U.S. Pat. No. 3,800,292.

3. "Override Hardware for Main Store Sequencer" invented by Thomas J. Donahue, filed on Oct. 5, 1972 having Ser. No. 295,418 and assigned to the same assignee named herein, now U.S. Pat. No. 3,820,081.

4. "Main Memory Sequencer" invented by T. J. Donahue, J. L. Curley, B. S. Franklin, W. A. Martland, and L. V. Cornaro, filed on Oct. 5, 1972 having Ser. No. 295,331 and assigned to the same assignee named herein, now U.S. Pat. No. 3,821,709.

5. "Main Memory Reconfiguration" invented by J. L. Curley, B. S. Franklin, W. A. Martland, T. J. Donahue and L. V. Cornaro filed on Oct. 5, 1972 having Ser. No. 295,417 and assigned to the same assignee named herein, now U.S. Pat. No. 3,796,996.

6. "Segmented Address Development" invented by Jacques Michel Jean Bienvenu, filed on May 16, 1974 and having priority date May 16, 1973 and having Ser. No. 470,496 and assigned to the same assignee named herein.

7. "Protection of Data in an Information Multiprocessing System by Implementing a Concept of Rings to Represent the Different Levels of Privileges Among Processes" invented by Marc Appell, et al, first filed on Nov. 30, 1973 in France and having French Ser. No. 73 42706 and further filed in the United States within the priority convention date of Dec. 2, 1974 and having Ser. No. 528,953 and assigned to the same assignee named herein, now U.S. Pat. No. 4,177,510.

8. "Procedure Calls and Stack Mechanism" invented by Marc Appell, et al, first filed on Nov. 30, 1973 in France having French Ser. No. 73 42705 and assigned to the same assignee named herein and further filed in the United States within the priority convention date of Dec. 2, 1974, and having Ser. No. 529,019 and assigned to the same assignee named herein.

9. "Process Management Structures and Hardware/Firmware Control" invented by Patrick Dufond, et al, first filed on Nov. 30, 1973 in France having French Ser. No. 73 42693 and further filed in the United States within the priority convention date of Dec. 2, 1974, and having U.S. Ser. No. 529,253 and assigned to the same assignee named herein.

10. "P and V Instructions on Semaphores for Process Synchronization" invented by Jacques Bienvenu, et al, first filed on Nov. 30, 1973 in France having French Ser. No. 73 42697 and further filed in the U.S. within the priority convention date of Dec. 2, 1974, and having Ser. No. 529,017 and assigned to the same assignee named herein.

11. "Method for Definition of Computer Architecture" invented by C. W. Bachman and Jacques Bouvard, filed on Nov. 24, 1972, and having U.S. Ser. No. 309,584 and assigned to the same assignee named herein, now abandoned.

12. "An Extended Semaphore Architecture" by C. W. Bachman and Jacques Bouvard, filed on Apr. 19, 1974, and having Ser. No. 462,551 and assigned to the same assignee named herein.

BACKGROUND

1. Field of the Invention

This invention relates generally to computer systems and more particularly to a deadlock detection mechanism for detecting a situation where one or several processes are waiting for events which cannot happen.

2. Description of the Prior Art

Electronic computers have grown from first generation hardware characterized mainly by vacuum tubes, to second generation hardware characterized by transistors, to third generation hardware characterized, in the main, by integrated circuits. Along with these different generations of hardware there were different generations of software, wherein first generation software was characterized mainly by machine language, assemblers and subroutines, and second generation software was characterized by high-level languages, monitors and macro assemblers. Third generation software is characterized by operating systems, on-line real-time systems multiprogramming systems, and data management systems.

The first generation hardware in combination with first generation software, and also the second generation hardware in combination with second generation software were primarily oriented toward batch processing where jobs were executed primarily in serial fashion. Moreover, the third generation of hardware/software systems are also batch-process oriented; however because of the advent of multiprogramming, several jobs may be executed in parallel rather than serial, and permits the acceptance of input information for processing as it is generated.

The fourth generation system will typically be classified as a communication and control system capable of widely diversified processor applications, and will be stimulated primarily by transmitted data rather than by batch programs (i.e. system control will be established primarily by input rather than by operator action) wherein submission of information will generally be in real time.

Processing in first generation hardware/software computer systems was relatively straightforward where the job or program was considered the basic processing unit. For each user initiated job or transaction a program generally ran with little or no interruption until the job or transaction was completed. Many straightforward jobs such as the compilation and execution of a high level language program, such as FORTRAN, could and did run as a single process. More difficult jobs, however, would require multitask operations and they would create other processes as they ran. (Note that a process is a concept implying the carrying on of some activity and should not be confused with the concept of a program, which is a process or activity description and can be used by one or more processes. We can speak either of a process or a processor executing a program. See Glossary of Definitions).

The concept of a process as being the basic processing unit developed to fill a need for the multiprogramming/multiprocessing environment of third generation computers. In such an environment where many users are demanding service simultaneously, it is natural to conceive of multiple processes competing for resources within the computer system. Each process consists of a program (i.e. an ordered collection of instructions and other data associated with the instructions) which is executed by the computer processor and a process state vector which defines the current status of the process. The process operates on data to perform a user's job or some phase of that job. Where many such processes are demanding simultaneous attention from the system, the task of communicating with and between such processes and the task of controlling and allocating resources to such processes particularly in view of the requirements of fourth generation systems becomes extremely complex.

In a multiprogramming/multiprocessing environment, it is essential that cooperation between two or more processes be efficiently and expeditiously realized. While many solutions to this problem have been proposed in the past, the technique of interprocess communication and control needed for the fourth generation computers has not, until now, been fully realized. The germination of the concepts required for a fourth generation computer, however, have been partially developed by E. W. Dijkstra in a paper entitled "Cooperative Sequential Processes from Programming Languages", NATO Advanced Study Institute, edited by F. Genuys of Paris and published in Academic Press, 1968. In this paper, Dijkstra postulates a basic concept of a semaphore for use in process synchronization and "P" and "V" instructions operating upon the semaphore. Unfortunately, Dijkstra provides for interprocess communication and process synchronization solely by software usage thus not only slowing down the operating time of the system but also decreasing the efficiency and extending the overall overhead required for such a system. More importantly, Dijkstra does not provide the concepts required for any significant exploitation of a fourth generation computer since he formulates only a basic premise in process synchronization. For one example, the transmission of messages from one process to another is not anticipated nor explained in Dijkstra's paper.

The concepts of P and V instructions have also been previously expounded by Edsger W. Dijkstra in the previously cited article. However, these concepts are presented only in generalized terms and do not provide the system configuration needed in a fourth generation computer. Moreover, Dijkstra merely provides a software basis for interpreting and using P and V instructions. Thus the memory organization necessary for rapidly accessing processes in addition to providing a systematic reallocation of the data processor has not been contemplated. As a result, not only are many of the P and V instructions necessary for delivering or receiving data by the executing processes not shown by Dijkstra but also the hardware/firmware basis for enabling process transferral in response to all P and V instructions is not envisioned.

Moreover in a multiprocessing environment, interprocess communication and synchronization facilities are essential to achieve smooth cooperation between loosely connected processes. Primitive hardware mechanisms such as traps and interrupts were initially devised to fill basic system needs. More advanced facilities such as Dijkstra's semaphores described in Reference 1 infra were later introduced and have been widely applied in one form or another. Please refer to References 2-4 attached hereto as an appendix under the caption References. User-oriented software control structures such as event control blocks were also provided for user intertask communication in a multitasking environment.

While these facilities have proved useful in the resolution of many specific problems, they have failed to provide a broad and unified interprocess communication capability well suited to general system and user needs in asynchronous processing applications.

By asynchronous processing, we refer to the type of activity carried out by a sequential process (as defined in Reference 1) in response to signals that are generated independently and asynchronously from that process (by some other process or device). Examples of this type of processing include:

handling hardware-generated traps which signal the occurrence of exception conditions such as machine error, program error, overflow, etc.;

handling hardware-generated interrupts which indicate the occurrence of significant external events including I/O transfer completion, I/O error detection, and timer run-out;

processing software interrupts generated upon detection of unusual results within a procedure; or those triggered by calls to the system supervisor;

processing activity performed by one software task in response to requests issued by some other task in a multitasking environment.

Several trends are contributing to enhance the significance of asynchronous processing. Among these are:

the trend of computer architecture toward multiprocessor configurations for central as well as peripheral sub-systems. Typical of this trend is the use of multiple central processors, or separate front-end and network processors to enhance system performance and system availability;

the trend toward distributed implementation of multiprogramming or time-sharing operation systems;

the trend toward fast-response on-line application systems providing a broad variety of services to a community of simultaneous users.

What is required for the fourth generation computer is a system which automatically integrates process communication and process control so as to not only enhance the operating efficiency of the system but also to provide sufficient flexibility to deal with the innumerable situations arising in the transfer of information from one process to another and in the management of events and messages. The system is the subject of a U.S. patent application Ser. No. 462,551, disclosing an invention by the same inventors of the instant invention entitled "An Extended Semaphore Architecture" and filed on an even date with the instant application and assigned to the same assignee, and incorporated herein by reference.

In such a fourth generation architecture where each process is concerned with several event variables, the possibility of a deadlock situation is introduced, wherein two or more processes are permitted to wait for related events which cannot happen.

OBJECTS OF THE INVENTION

It is a primary object of the invention to provide a deadlock detection mechanism for detecting a deadlock situation wherein two or more processes are waiting for related events which cannot happen.

Another object of the invention is to provide an improved deadlock detection mechanism.

Still another object of the invention is to detect and prevent a requesting process from waiting for the availability of resources which are already held by some other process which is itself already waiting directly or indirectly on the first process.

Yet a further object of the invention is to provide firmware and a method to examine the request of a first process of a group of processes for assignment of a first resource of a group of resources, and to determine whether said first resource is or is not currently assigned to a second process of said group of processes which said second process is already waiting directly or indirectly for a second resource of said group of resources which said second resource is currently assigned to the said first process.

A still further object of the invention is to provide a hardware/firmware mechanism which will quickly and efficiently search the system control tables and determine whether causing a requesting process to wait on the availability of a resource or other process would in fact cause a deadlock situation.

SUMMARY OF THE INVENTION

The foregoing objects are achieved by providing a deadlock detection and prevention mechanism which detects a situation where two or more processes are waiting for related events which cannot occur, and preventing a requesting process from waiting for the availability of a resource or resources which are already held by a second process which is waiting directly or indirectly upon the first process.

Firmware and a method is provided to examine the request of a first process of a group of processes for assignment of a first resource of a group of resources, and to determine whether said first resource is or is not currently assigned to a second process of said group of processes which said second process is already waiting directly or indirectly for a second resource of said group of resources which said second resource is currently assigned to the said first process.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features which are characteristic of the invention are set forth with particularity in the appended claims. The invention itself, however, both as to organization and operation together with further objects and advantages thereof may best be understood by references to the following description taken in conjunction with the drawings in which:

FIGS. 1A, 1C-1E, 1G, 1H, 1J, and 1L are entity structure diagrams useful in understanding the basic concepts of the invention. (Rules for constructing such diagrams are published in Reference 6).

FIG. 1F is a table for classifying four embodiments of the invention.

FIGS. 1B and 1I are schematic diagrams showing deadly embrace detection with exclusive assignment of resources and exclusive assignment of objects from a multiple object resource class respectively.

FIG. 1K is a table showing three operation states during which an assignment request may be honored, and three operation states during which a requesting process is caused to wait if a deadlock is not detected.

FIG. 2A is a block diagram of a multiprogramming system utilizing the invention.

FIG. 2B is a schematic representation of various hardware structures utilized by the invention.

FIG. 3 is a legend of terms used for reserved areas of storage in registers depicted in FIG. 2.

FIG. 4 is a schematic diagram of a process control block.

FIG. 5 is a schematic diagram of a system for addressing a process control block.

FIG. 6 is a schematic diagram of the system base of the computer system utilizing the invention.

FIGS. 7A and 7B are a schematic representation of a stack segment and a stack frame respectively.

F