Deadlock detection and prevention mechanism for a computer system

Abstract

A method and apparatus for detecting a deadlock condition where two or more processes are waiting for events which cannot happen. Firmware 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.

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.

Description

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.

FIG. 8 is a schematic diagram of a system for addressing G-segments and in particular the queue of processes in the GO segment.

FIG. 9 is an exploded schematic diagram of a GO segment illustrating queue of processes and process linking.

FIGS. 10A through 10L are block diagrams of structures in the PCB.

FIGS. 11A through 11R are block diagrams of structures in the system base.

FIG. 12 is a schematic diagram of addressing schemes of user and system segments utilizing the system base and PCB structures.

FIGS. 13A-C are schematic diagrams of the control unit.

FIGS. 14A through 14I are flow diagrams of the dispatcher unit in firmware.

FIG. 15 is an exploded view of a semaphore descriptor segment and its arrangement.

FIGS. 16A through 16P are block diagrams of semaphore structures utilized by the invention in the system.

FIG. 17 is a schematic diagram of address development for the semaphore.

FIG. 18 is a schematic diagram showing the relationship of the semaphore descriptor segment with a GO segment.

FIGS. 19A-B are exploded schematic diagrams of the scratch pad memory of the logical store unit shown in FIG. 13 and illustrating the overall organization of its word structure.

FIGS. 20A-B are flow diagrams of the semaphore descriptor fetch subroutine used for all P and V instructions.

FIG. 21 is a flow diagram of the P instruction on semaphores without messages.

FIGS. 22A-E are flow diagrams of the P instruction on semaphores with messages.

FIGS. 23A-H are flow diagrams of the EVP subroutines called by both the P and V instructions for transferring the process in the running state into the wait state.

FIGS. 24A-D are flow diagrams of the PMZ subroutine for transferring a message without entering a queue on a semaphore.

FIGS. 25A-I are flow diagrams of the V instructions on a semaphore when the SCT field of the semaphore is negative.

FIGS. 26A-F are flow diagrams of the V instruction on a semaphore when the SCT field of the semaphore is positive.

I. INTRODUCTION

A. Scope and Organization of the Disclosure

The instrumentalities employed for an event management system in a large-scale-computer are necessarily complex. Moreover, a full appeciation of the teachings of the present invention can be obtained only if the reader has some familiarity with the environment in which such instrumentalities reside. For this reason, it is desirable to at least briefly explore the general architecture of a typical large-scale data processing system of the type in which the principles of the present invention may be utilized to advantage. It is also desirable to first establish and understand the basic concepts on which the present invention is based. Accordingly this disclosure will first review the basic support requirements and the traditional process synchronization mechanisms. Next, the more general support requirements are established and extended capabilities are outlined. The key event-related architectural entities are isolated, characterized and structured, and a general event management functionality of the extended semaphore architecture is defined. The computer system environment in which the instrumentalities of the concepts reside, is shown and described. Finally, hardware structures of the invention and its environment are shown and described.

As pointed out in Reference 5, implementation considerations generally involve two radically different concerns: functionality definition and hardware considerations. The present disclosure focuses on both--first on the function aspect and secondly on hardware implementation.

B. Basic Concepts

1. Basic Requirements

In its most elementary form, interprocess communication permits one process to set a variable whose contents may, at some later time, be inspected and reset by another process. Typically, and by pre-established convention, the setting of that variable represents the occurrence of an event which is significant to the other. For example, a process might accumulate information into some buffer area for processing by another. Once the buffer has been filled, a mutually accessible variable is set to indicate that buffer processing may commence.

We may thus define the basic elements of an interprocess communication facility as consisting of:

an event occurrence defined as the occurrence in one process (the event generator) of a condition which is significant to another process (the event handler).

a mutually accessible binary state variable (event variable) which may be asserted to an "on" state by the event generator, and which can be tested and reset to an "off" state by the event handler. In addition, execution of these operations must be serialized (test, then reset to off) and indivisible.

a context of interpretation for the event occurrence specifying the significance of the event and the nature of the reaction that is to be carried out.

Functionallty, the event generator process performs two major tasks:

event condition monitoring; and,

event variable setting (event posting). while the event handler performs:

event detection; i.e., sensing and resetting the event variable; and,

event reaction; i.e., execution of some procedure in response to the event occurrence.

An event mechanism constitutes a communication and synchronization device between cooperating processes. Event occurrences can be viewed as processing requests which are directed to the event handler and which gate its activity.

2. Basic Synchronization Mechanisms

The event detection function consists of the recognition of event occurrences posted on the event variable. Efficiency and discrimination are two important characteristics of this mechanism.

The efficiency of the detection mechanism is related to the processing cost associated with the recognition of an event occurrence. More specifically, it can be measured by the quantity of processing consumed by the event handler while waiting for the next event occurrence. Using a simple test mechanism, the event handler periodically tests the event variable. Each time an event occurrence is detected, the event handler executes the appropriate reaction procedure and then returns to its testing activity. This repeated testing could consume large quantities of processing power with no useful results. A more efficient mechanism is achieved by the introduction of a "wait-for-event" in addition to the "test-for-event" facility. Under this scheme, the event handler may enter a dormant state pending the next event occurrence.

The discrimination of the detection mechanism pertains to its ability in recognizing each individual event occurrence. An event occurrence could escape detection in case of event occurrence "pile-up". This is a situation where the event occurs more than once between two consecutive detections. Using the test/wait mechanism, the discrimination is measured by the interval of time required to carry out the reaction procedure. In many cases, however, the entire reaction procedure need not necessarily by completed prior to the next event occurrence. Two types of reaction procedures can thus be distinguished: foreground and background. The foreground reaction procedure is that which must be completed prior to the next event occurrence; the background reaction can be carried out in a non-sequential fashion with respect to the event occurrences. Typically, the foreground reaction represents some critical activity which must be completed before the next event occurs while background processing may be handled in a more leisurely way.

Several mechanisms have been devised to exploit this opportunity. The trap mechanism (or internal interrupt) causes the event handler to perform an implicit out-of-sequence call to a foreground procedure upon detection of an event occurrence. Using the trap mechanism, the detection discrimination is improved by reducing the "blind" period to the duration of the foreground reaction procedure. Another important characteristic of the trap mechanism lies in its ability to react to an event occurrence even while the event handler is not specifically expecting it (i.e., not currently testing on it or waiting for it). This characteristic proves extremely helpful enabling a process to handle several event variables as we will see later.

To illustrate the use of the trap mechanism, consider the case of a communication line processor. An event occurrence (type 1) consists of the arrival of a new character in a one-character line buffer. Reaction to this event involves fetching the character from the buffer, performing some validation and editing and moving the edited character to a message buffer area. It is clear that until a newly arrived character is actually moved out of the buffer area, it stands the risk of being destroyed upon the arrival of the next character. On the other hand, there is no compelling reason for completing the editing activity prior to the arrival of the next character. We can therefore treat the buffer emptying operation as a foreground procedure while the validation and editing activities are performed in the background.

Assume that the detection mechanism consists of a traditional test/wait data complemented with a trap feature.

The processing is broken into the foreground (buffer empty work) signalled by an event occurrences of type 1, when a character arrives and the background character editing work signalled by an event occurrence of type 2 when a character has been save stored out of the buffer.

Assume that the line processor is initially processing an event occurrence of type 2. Upon arrival of the first character, an event occurrence (type 1) is posted. This traps the event handler and causes it to perform an implicit call to the foreground buffer emptying procedure. This procedure moves the character out of the buffer into some save area and then signals the required background activity (event occurrence type 2). Completing the foreground activity, the event handler returns to its interrupted activity. When it is complete, it checks the occurrence of another happening of event condition type 2 and finds the event occurrence (type 2) posted on the event variable, resets it, and proceeds with the background reaction. If no additional character arrivals cause interrupts prior to the completion of the background reaction, the line processor upon completion return to the event condition #2 gate and will find no pending background activity (event occurrence type 2). Thus it re-enters its wait state.

If, however, a new character arrives into the buffer prior to the completion of the background reaction, another event occurrence (type 1) is posted, and again, a trap occurs. An implicit call to the foreground reaction is automatically generated temporarily interrupting the execution of the background procedure. The event handler enters the foreground procedure, moves the second character to the save area, and then returns to its point of interruption to resume execution of the background procedure. Barring further event occurrence, the line processor completes the background reaction and returns to the gate where it finds the second event occurrence posted. It resets it and re-executes the background procedure for processing the second character.

A variation on the trap mechanism is the interrupt or external interrupt. Under the interrupt scheme, the foreground procedure is executed by another higher priority process while the event handler is temporarily suspended. The main distinction between traps and interrupts being that background and foreground reactions are performed within different process environments.

3. The Semaphore Mechanism

The semaphore mechanism introduced by Dijkstra [1] features two important improvements over the elementary test/wait facility. First, the mechanism is symmetrical. A process can both post and detect event occurrences upon the same event variable. Secondly, the same event variable is generalized from a binary state variable to a positive integer. This permits the simultaneous posting of multiple event occurrences up to a prespecified limit. Event occurrence posting is performed by a V-operation which increments the event variable. Event detection is performed by a P-operation which senses and decrements the event variable. The V-operation returns an error if it finds the event variable already set to its maximum count. Conversely the P-operation causes the process that issues it to enter a wait state if the event variable (semaphore count) is equal to zero. This wait state persists until the next event occurrence is posted on the semaphore.

The detection discrimination of the semaphore mechanism is independent of the frequency of event occurrences. As long as the backlog of unprocessed event occurrences remain below the maximum count, no event occurrence will go undetected and unprocessed. However, once this backlog reaches the limit, the event posting mechanism becomes inhibited and remains that way until the next P-operation reduces the actual count of event occurrences below the maximum for the semaphore.

4. Multiple Event Processors

In the foregoing discussion, we have only dealt with situations involving a single pair of asynchronous processes: one process which generates event occurrences and the other one which handles them. We have defined the requirements for and examined basic mechanisms that support interprocess communication and synchronization. Let us turn now to the more general situation where the same event generator is associated with several event handlers through a single event variable. We will discuss this problem using two examples. The first one involves a simple message handler and a second deals with a more general resource management problem.

Consider a process which assembles messages into a buffer area and two identical message handling processes sharing a common event variable. Assume that each event occurrence signals the availability of a new message in a pre-designated buffer area. Our objective is to arrange so that both message handlers cooperate in processing the messages in a coherent manner. This means that messages must be distributed between processors so that each message gets processed at least once but not more than once. In other words, we must guarantee that access to a message by the processes is mutually exclusive. Let us examine how the semaphore mechanism can be applied to satisfy this requirement.

Assume that the initial number of posted occurrences (i.e. messages) is three at the time both message handling processes are simultaneously activated. Assume also that no further messages will be arriving in the course of this discussion. As each message handling process begins it issues a P-operation. By definition, such an operation is indivisible, and, therefore, event detection by the two processes will take place serially. The first process to issue the P-operation finds a count of three, reduces it to two, and implicitly gains control of the first message in the buffer area. Next, the other process issues the P-operation. It finds a count of two, reduces it to one, and gets control of the second message. Both message handling processes then proceed independently from one another until their processing is complete. At this point they return to the semaphore to secure another message. The first process to reach the semaphore finds a count of one, reduces it down to zero, seizes control of the third and last message and proceeds to process it. From that point on, either process returning to the semaphore will find the count equal to zero and, therefore, will enter a wait state. We have thus satisfied our requirement and insured that each message be processed once and only once.

This example illustrates the capability inherent in a semaphore mechanism to resolve a contention situation developing between several processes that are vying for the acquisition of the same resource. This capability derives from the indivisibility of the P-operation. Effectively, only one process at a time is able to detect the availability of a resource and acquire its control. Note that in the preceding example, the message handling processes requests for resource assignment were not directed to any particular message but rather to any message available for processing. The event variable was tied to the whole class of message objects, not to any particular member of that class. Also observe that the availability of a particular message object was a non-recurrent condition. Once assigned to a message handler, a message could not become available again for reassignment. In this case, a message constitutes a nonreusable resource.

5. The Basic Resource Management Problem

Consider now the case of a reusable resource object. This is a resource which can only be used by one process at a time. It may, however, be released and reassigned to another process. Mutually exclusive assignment is required so that each process can achieve full control over the state or information contents of an object.

A classical example illustrating this requirement is the order entry application. A stock inventory file is updated according to transactions originating from multiple on-line terminals. Each terminal is served by a distinct process. To fulfill an order, a process must access the database record corresponding to a given article, look up its contents and determine whether the inventory level is sufficient to fill the order. If so, the record is updated according to the quantity ordered. Because several other processes may also, in some unpredictable way, attempt to perform simultaneously the same update operation, some provision must be made to prevent interference. Specifically, only one process must be permitted to access a given record during the critical period between the time where the record is examined and the time where its updated contents is returned to the file.

Mutual exclusion on record access can be insured by performing the record look-up and updating operations as a critical section, in the sense defined in Reference 1. Prior to examining the inventory level, each process requests exclusive assignment of the corresponding record. It then performs the update, replaces the record into the file and releases the record assignment. In this case, a semaphore-like binary event variable is associated with the record as a resource object. The state of availability of the resource is represented by the value of the event variable; one for available and zero for already assigned. A resource assignment request consists of issuing a P-operation on the event variable while resource release is accomplished by a V-operation on the same event variable.

Note that this arrangement is completely symmetrical. Each process alternately acts as an event handler when it requests assignment of a record and as an event generator when it releases it. This scheme can therefore be generalized and applied to control the assignment of resources between any number of processes, using one event variable to represent the state of availability of each reusable resource object.

6. Deadlock considerations

Earlier in this disclosure we have considered the use of a single event mechanism as a means for communication between several processes. In the architecture depicted above, we are allowing each process to be concerned with several event variables. This introduces the possibility of deadlock situations.

A deadlock is a situation where one or several processes are waiting for an event which cannot happen. A deadlock can only be resolved by external intervention, typically, by removing one or several processes from the system and releasing their resources. The simplest deadlock situation (and also the easiest to detect) develops if a process were permitted to wait for the availability of a resource which it already owns. Since only that process has the ability to fulfill the required condition by releasing the resource, it is clear that a deadlock will result if it were allowed to enter a wait state. This is, of course, a trivial case which should be treated as an error; the wait request should be rejected with appropriate notification:

A similar but less trivial deadlock situation involves two or more processes. A deadlock may develop if several processes are permitted to wait for the availability of resources which are already held by some member of that group. Deadlock detection, although more involved than in the case of a single process, is straightforward. With reference to the entity structure diagram shown in FIG. 1a, a deadlock is readily detected if the "pr--ro" and "ev--epd" set occurrences hierarchy, when traversed in an upward direction, (findowner) reveals an annular or closed loop structure.

C. Basic Event Management Architecture

1. Architecture Definition

At this point, it seems appropriate to consolidate our understanding of the event mechanism into a somewhat more formal architectural definition. To follow the approach suggested in [5], let us first identify and characterize the relevant architectural entities. Seven distinct entity classes can be isolated: system, process, resource class, resource object, event variable, event processing demand and event occurrences. Table 1 lists these entities and their attributes.

FIG. 1a is a particular entity structure diagram which portrays certain relationships between entity classes. These are also described in Table 2. A detailed explanation of the notations involved in entity structure diagrams can be found in Reference 6 infra. Briefly, each box represents a distinct entity class. Simple (1:n) relationships between entity classes are represented as set classes. Each arrow denotes a distinct set class. A set occurrence is owned by a unique entity occurrence which belongs to the class designated by the tail of the arrow. A set occurrence has zero, one or several member entity occurrences which belong to the class designated by the head of the arrow.

The set classes are designated by a pair of abbreviated entity class names, in the order: (owner)--(member). For example, "sys--pr" designates the process name space. It is a set class owned by a system entity and comprising every process known to that system. Similarly, "sys--ev" designates the event variable name space. It is the set of all event variables in a system.

2. Binary Semaphore

FIG. 1a portrays the most basic resource management structure. Reusable resource objects are assigned to independent processes. Each resource object is associated with its own event variable. The availability of a resource is evidenced by the presence of an event occurrence on the corresponding event variable. In this case, there can be no more than one concurrent event occurrence per event variable. We have also a one-for-one correspondence between resource objects and event variables. For the moment, we are talking about resource classes with only one resource object. The four entity classes: resource object, resource class, event variable, and the event occurrence are therefore related on a one-for-one basis. This is shown on the diagram by the close grouping of the corresponding boxes. Only one event processing demand can exist per process; therefore, the entity classes for process and event processing demand are joined on a one-for-one basis.

These four entity classes (resource object, resource class, event variable and event occurrence) represent concepts which are buried in the classis semaphore. At the risk of creating confusion, they are all identified here for the reader. Subsequent steps in the development of the generalized semaphore will require the surrender of the 1:1 relationship now being defined and will focus on their importance as independent concepts.

                                      TABLE 1
    __________________________________________________________________________
    Basic Event Management: Entity Classes
    ENTITY  ABBREVIATION            TYPICAL
    CLASS NAME
            NAME      DEFINITION    EVENT-RELATED ATTRIBUTES
    __________________________________________________________________________
    Event   evo       Instance of realization
                                    . Time of occurrence
    occurrence        of event condition
    Event             The request of a
                                    . Trap procedure name
    Processing
            epd       process upon an event
    Demand            variable for event detection
    Event   ev        Interprocess Communication
                                    . Name
    Variable          and Synchronization
                                    . State (Happened/not happened)
                      Facility      . Current count of posted event
                                     occurrences
                                    . Maximum count of posted
                                     event occurrences
                                    . Current count of waiting
                                     processes
    Process pr        Program under execution
                                    . Name
                                    . Relative priority
    Resource          A grouping of resource
                                    . Class name
    Class   rc        objects having some common
                                    . No. of objects within the
                      attributes     class
    Resource          An entity occurrence
    Object  ro        susceptible of assignment
                                    . object name
                      to a process
    System  sys       Root of entity structure
    __________________________________________________________________________


              TABLE 2
    ______________________________________
    Basic Event Management: Set Classes
    SET
    CLASS                  MEMBER-
    NAME   DEFINITION      SHIP      ORDER
    ______________________________________
    ev--epd
           Process waiting for
                           Sometimes . FIFO
           an event
    pr--ro Resource object assigned
                           Sometimes . FIFO
           to a process
    sys--ev
           Event variable name
                           Always    Alphabetical by
           space                     name
    sys--pr
           Process name space
                           Always    Alphabetical by
                                     name
    ______________________________________

                  TABLE 3a
    ______________________________________
    Function Definition Algorithm for "Wait-On-Event-Variable"
    ______________________________________
    wait -on event -variable: procedure (p -code, p -evptr, p -prptr);
    /* This primitive causes a resource object represented
    by an event variable (p -evptr) to be assigned to a process
    (p -prptr), provided that it is not already assigned to some
    other process. Otherwise the process is waited until the
    resource can be assigned.  */
    /* determine whether resource is already assigned  */
    if inserted (p -evptr, "pr --ro")
    then do;
    /* assign resource to process */
    call insert (p -evptr, "pr --ro", "after", p -prptr);
    p -code = 0;
    return;
    end;
    /* determine whether resource is currently held by process */
    call findowner (prptr, "pr --ro", p -evptr);
    if prptr = p -prptr
    then do;
    code = 1; -return; -end;
    /* determine whether wait would cause a deadly embrace */
    if deadly -embrace (p -evptr, p - prptr)
    then do;
    code = 3;
    return;
    end;
    /* wait process upon event processing demand */
    call insert (p -prptr, "ev --epd", "before", p -evptr);
    code = 0;
    call process -disptach (p -prptr);
    end wait -on -event -variable;
    ______________________________________

                  TABLE 3b
    ______________________________________
    Function Definition Algorithm for "Test-On-Event-Variable"
    ______________________________________
    test -on -event -variable: procedure (p -code, p -evptr, p -prptr);
    /* This primitive causes a resource object represented
    by an event variable (p -evptr) to be assigned to a process
    (p -prptr), provided that it is not already assigned. Otherwise
    the process is so notified */
    /* determine whether resource is already assigned */
    if inserted (p -evptr, "pr --ro")
    then do;
    /* assign resource to process */
    call insert (p -evptr, "pr --ro", "after", p -prptr);
    p -code = 0;
    return;
    end;
    /* Make resource available */
    /* determine whether resource is currently held by process */
    call findowner (prptr, "pr --ro", p -evptr);
    if prptr = p -prptr
    then p -code = 2;
    else p -code = 1;
    end test -on -event - variable;
    ______________________________________

                  TABLE 3c
    ______________________________________
    Function Definition Algorithm for "Post-On-Event-Variable"
    ______________________________________
    post -on -event -variable: procedure (p -code, p -evptr, p -prptr);
    /*  This primitive causes the release of the resource
    represented by an event variable (p -evptr) by the process
    (p -prptr) to which it is currently assigned. */
    /* validate that resource is currently assigned to process */
    call findowner (prptr, "pr --ro", p -evptr);
    if prptr = p -prptr
    then do;
    p -code = 1;
    return;
    end;
    /* determine whether there is a process waiting for the resource */
    call findnext(prptr, "ev --epd", p -evptr, eos);
    if eos
    then do;
    /* assign resource object to waiting process */
    call insert (p -evptr, "pr --ro", "after", prptr);
    /* dispatch waiting process */
    call remove (prptr, "ev --epd");
    call process -dispatch (prptr);
    end;
    p -code = 0;
    end post - on -event -variable;
    ______________________________________

                                      TABLE 4
    __________________________________________________________________________
    Basic Event Management: Extended Semaphore Set Classes
                               MEMBERSHIP
                                        TYPICAL
    NAME DEFINITION            TYPES    ORDER
    __________________________________________________________________________
    edp --pr
         Process waiting for fulfillment of an
                               Sometimes
                                        N/A
         event processing demand
    epd --evo
         Event occurrences assigned to an event
                               Sometimes
                                        FIFO
         processing demand where the process has
         not been notified as to the assignment
    ev --epd
         Event processing demands outstanding
                               Always   FIFO/
         on an event variable           Priority
    ev --evo
         Outstanding event occurrences posted
                               Sometimes
                                        FIFO/LIFO/
         on event variable but not assigned to
                                        Priority
         an event processing demand
    pr --epd1
         Event processing demands issued by a
                               Always   FIFO
         process and currently outstanding
         against event variables
    pr --epd2
         Event processind demands with unnotified
                               Sometimes
                                        FIFO
         event occurrences
    pr --ro
         Resource objects assigned to process
                               Sometimes
                                        N/A
    ro --ro
         Resource objects in a resource class
                               Always   N/A
    sys --ev
         Event variables in system
                               Always   Name
    sys --pr
         Processes in system   Always   Name
    __________________________________________________________________________

                  TABLE 5A:
    ______________________________________
    The Function Definition Algorithm for Initiate-Event-Processing
    ______________________________________
    initiate -event -processing: procedure (p -code, p -evptr, p -prptr,
    p -trap -procedure, p -max -occ - cnt);
    /* This function definition algorithm causes a process
    (p -prptr) to become an active candidate for processing an event
    occurrence posted on the event variable (p -evptr). A trap
    option may be specified by naming a procedure which is to be
    executed by the requesting process immediately upon the
    detection of the event occurrence, unless it is currently
    executing a trap procedure. The max -occ -cnt parameter species
    the maximum number of event occurrences which may be assigned
    to the process at any time (epd --evo set). */
    /* Check whether process is already active on event variable */
    call findnext (epdptr, "pr --epd", p -prptr, eos);
    do while  ( eos);
    call findowner (evptr, "ev --epd", epdptr);
    if evptr = p -evptr
    then do;
    p -code = 1;
    return;
    end;
    call findnext (epdptr, "pr --epd", epdptr, eos);
    end;
    /* create event processing demand for process and establish its
    attributes */
    call create (epdptr, "epd");
    epdptr .fwdarw. epd.trap = p -trap -procedure;
    epdptr .fwdarw. epd.max -occ -cnt = p -max -occ -cnt;
    /* insert event processing demand into "ev --epd and "pr --epd"
    sets */
    call insert (epdptr, "ev --epd", "before", p -evptr);
    call insert (epdptr, "pr --epd", "after", p -prptr);
    /* evaluate the initiate event */
    call evaluate -event (p -evptr);
    p -code = 0;
    end initiate -event -processing;
    ______________________________________


              TABLE 5B:
    ______________________________________
    Evaluate Event Procedure
    ______________________________________
    evaluate -event: procedure (p -evptr);
    /* This procedure is called whenever a resource is
    released, an event processing demand is created, a process
    executes a test -on -event -variable, a process executes
    a wait -on -event -variable, or a trap procedure is completed. */
    /* Search for an unsatisfied event processing demand as
    long as there is an available event occurrence. */
    call findnext epdptr, "ev --epd", p -evptr, eos);
    do while ( eos & empty (p -evptr, "ev --evo"));
    call findnext (evoptr, "epd --evo", epdptr, eos -2);
    do count = 1 to eptptr .fwdarw. epd.max -occ -cnt while (eos -2);
    call findnext (evoptr, "epd --evo", evoptr, eos -2);
    end;
    /* determine whether maximum count is satisfied */
    do while (count epdptr -epd.max -occ -cnt & empty (p -evptr,
    "ev --evo"));
    call findnext (evoptr, "ev  --evo", p -evptr, eos);
    call remove (evoptr, "ev -evo");
    /* assign resource to process */
    call findowner (prptr, "pr --epd1", epdptr);
    call insert (evoptr, "pr --ro", "after", prptr);
    /* determine whether trap or gate demand */
    if epdptr .fwdarw. epd.trap = " "
    then do;
    /* trap demand */
    /* determine whether process is currently
    in trap mode */
    if prptr .fwdarw. or.status = "trapped"
    then call trap (epdptr, evoptr);
    else do;
    call insert (evoptr, "epd --evo",
    "before", epdptr);
    if inserted (epdptr, "pr --epd2");
    /* alert process of delayed trap */
     then call insert (epdptr,
    "pr --epd2", "before", prptr);
    count = count + 1;
    end;
    end;
    else do;
    /* gate demand */
    /* determine whether process is
    currently waiting */
    if empty (epdptr, "epd --pr")
    then do;
     /* restart waiting process
    and notify of event */
    call findnext (prptr, epd --pr",
    epdptr);
    call remove (prptr, "epd --pr");
    call dispatch -process prptr,
    evoptr);
    end;
    else do;
    /* assign event occurrence to
    event processing demand */
    call insert (evopr, "epd --evo",
    "before", epdptr);
    count = count + 1;
    end;
    end;
    end;
    call findnext (epdptr, "ev --epd", epdptr, eos);
    end;
    end evaluate -event;
    ______________________________________

                  TABLE 5C;
    ______________________________________
    The Function Definition Algorithm for
    Terminate-Event-Processing
    ______________________________________
    terminate -event -processing: procedure (p -code, p -epdptr, p -prptr);
    /* Event occurrences currently assigned to the event
    resource object. They will be made available to any other
    unsatisfied event processing demand of other processes. */
    /* verify that referenced event processing demand belongs to
    the process */
    call findowner (prptr, "pr --epd", p -epdptr);
    if prptr = p -prptr
    then do;
    p -code = 1
    return;
    end;
    call findowner (evptr, "ev --epd", p -epdptr);
    /* release any unprocessed event occurrence */
    do while ( eos);
    call remove (evoptr, "epd --evo");
    call insert (evoptr, "ev --evo", "after",prptr;
    call remove (evoptr, "pr --ro");
    call findnext (evoptr, "epd --evo", p -evptr, eos);
    end;
    /* delete the event processing demand */
    call remove (p -epdptr, "ev --epd");
    call remove (p -epdptr, " pr --epd");
    call destory (p -epdptr, "epd");
    /* evaluate the terminate event */
    call evaluate -event (evptr);
    p -code = 0;
    end terminate -event -processing;
    ______________________________________

                  TABLE 5D:
    ______________________________________
    The Function Definition Algorithm for Wait-On-Event-Variable
    ______________________________________
    wait -on -event -variable: procedure (p -code, p -epdptr, p -prptr
    p-notification-message);
    /*This primitive determines whether an event processing
    demand established by a process has been satisfied. If the
    demand is satisfied then the process is so notified, else the
    process is waited until the demand has been satisfied. */
    /* verify that the event processing demand belongs to the
    process */
    call findowner (prptr, "pr --epd", p -epdptr);
    if prptr = p -prptr
    then do;
    p -code = 1;
    return;
    end;
    /* determine whether "gate" event processing demand */
    if p -epdptr .fwdarw. epd.trap = " "
    then do;
    p -code = 3;
    return;
    end;
    /* determine whether event has happened */
    if empty (p -epdptr, "epd --evo")
    then do;
    /* notify of event occurrence */
    call findnext (evoptr, "epd --evo", p -epdptr, eos);
    p  -notification -message = evoptr -evo.message;
    call remove (evoptr, "epd --evo");
    p -code - 0;
    return;
    end;
    /* determine whether wait would cause a deadly embrace */
    if deadly -embrace (p -epdptr, p -prptr);
    then return;
    /* wait process upon event processing demand */
    call insert (p -prptr, "epd --pr", "before", p -epdptr);
    p -code = 0;
    call process -dispatch (prptr);
    end wait -on -event -variable);
    ______________________________________

                  TABLE 5E:
    ______________________________________
    The Function Definition Algorithm for Test-On-Event-Variable
    ______________________________________
    test -on -event -variable; procedure (p -code, p -epdptr, p -prptr;
    p-notification-message);
    /* This primitive causes a resource object represented
    by an event processing demand (p -epdptr) to be assigned to a
    process (p -prptr), provided that it is not already assigned.
    Otherwise the process is so notified */
    /* verify that the event processing demand belongs to the
    process */
    call findowner (prptr, "pr --epd", p -epdptr);
    if prptr = p -prptr
    then do;
    p -code = 1;
    return;
    end;
    /* verify that this is a "gate" event processing demand */
    if p -epdptr -epd.trap = " "
    then do;
    p -code = 3;
    return;
    end;
    /* determine whether event has happened */
    if empty (p -epdptr, "epd --evo")
    then do;
    /* notify of event occurrence */
    call findnext (evoptr, "epd --evo" , p -epdptr, eos);
    p -notification -message = evoptr -evo.message;
    call remove (evoptr, "epd --evo");
    p -code = 0;
    end;
    else p -code = 2;
    end wait -on -event -assignment;
    ______________________________________

                  TABLE 5F:
    ______________________________________
    The Function Definition Algorithm for
    Release-Resource-Assignment
    ______________________________________
    release -resource -assignment: procedure (p -code, p -roptr,
    p -prptr, p-notification-message);
    /* This procedure releases the assignment of a resource
    (p -roptr currently assigned to a process p -prptr). This may
    cause an event occurr if the event variable representing the
    resource class has an unsatisfied event processing demand
    posted against it. */
    /* verify that resource is currently assigned to process */
    call findowner (prptr, "pr --ro", p -roptr);
    if prptr = p -prptr
    then do;
    p -code = 1;
    return;
    end;
    /* release resource */
    call remove (p -roptr, "pr --ro");
    /* insert event occurrence into "ev --evo"
    call findowner (rcptr, "rc --ro", p -roptr);
    call insert (p -roptr, "ev --evo", "before", pr --ptr);
    p -ro -ptr .fwdarw. evo.message = p-notification-message;
    call evaluate -event (rcptr);
    end release -resource -assignment;
    ______________________________________

                  TABLE 5G:
    ______________________________________
    Procedure for Deadlock Detection
    ______________________________________
    deadlock 1: procedure (p -evref, p -prref) returns (bit (1));
    call findownerx (prref, "pr --roa", p -evref);
    if prref = p -prref
    then return ("1"b);
    else if insertedx (prref, "ev --epd")
    then do;
    call findowner (evref, "ev --epd", prref);
    return (deadlock1 (evref, p -prref);
    and;
    else return ("0"b);
    end deadlock1;
    ______________________________________

                  TABLE 5H
    ______________________________________
    deadlock2: procedure (p -evref, p -prref) returns (bit (1));
    call findnext (roaref, "rc --ro", p -evref,oes);
    do while ( eos);
    call findowner (prref, "pr --roa", roaref);
    if prref = p -prref
    then;
    else if inserted (prref, "ev --epd")
    then do;
    call findowner (evref, "ev --epd", prref);
    if deadlock2 (evref, p -prref);
    then;
    else return ("0"b);
    end;
    call findnext (roaref, "rc --ro", eos);
    end;
    return ("1"b);
    end deadlock2;
    ______________________________________

                  TABLE 5I
    ______________________________________
    deadlock3: procedure (p -evref, p -prref returns (bit (1));
    call findnext (roaref, "ro --roa", p -evref, eos);
    do while ( eos);
    call findowner (prref, "pr --roa", roaref);
    if prref = p -prref
    then return ("1"b);
    else if inserted (prref, "ev --epd");
    then do;
    call findowner (evref, "ev --epd", prref);
    if deadlock3 (evref, p -prref)
    then return ("1"b);
    else;
    end;
    call findnext (roaref, "ro --roa", eos);
    end;
    return ("0"b);
    end deadlock3;
    ______________________________________

                  TABLE 5J
    ______________________________________
    deadlock4: procedure (p -evref, p -prref) returns (bit (1));
    call findnext (roref, "rc --ro", p -everf, eos);
    do while ( eos);
    deadly = "0"b;
    call findnext (roaref, "ro --roa", roref, eos);
    do while ( eos & deadly);
    call findowner (prref, "pr --roa", roaref);
    if prref = p -prref
    then deadly = "1"b;
    else if inserted (prref, "ev --epd")
    then do;
    call findowner (evref, "ev --epd", prref);
    if deadlock4 (evref, p -prref)
    then deadly = "1"b;
    else call findnext (roaref, "ro --roa", eos);
    end;
    else call findnext (roaref, "ro --roa", eos);
    end;
    if deadly
    then return ("0"b);
    else call findnext (roref, "rc --ro", eos);
    end;
    return ("1"b);
    end deadlock4;
    ______________________________________