Extended semaphore architecture4320451Abstract A generalized event management architecture based upon an analysis of the traditional interprocess communication and synchronization mechanisms is disclosed. An extended semaphore architecture is proposed which combines the properties of Dijkstra's semaphore with that of a trap facility. This model is further developed into a more general architecture capable of handling complex events, structured event condition variables and generalized assignments. The architecture is defined in terms of entity classes, relationship classes and functional primitives. Finally a typical hardware computer system utilizing these concepts is shown and described. Claims We claim: Description RELATED APPLICATIONS
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
to a process . object name
System sys Root of entity structure
__________________________________________________________________________
The dashed arrow "ev--epd" illustrates the concept of a "sometimes" relationship. It represents the set of event processing demands and thus processes that are waiting on an event variable. A given process may or may not be waiting on an event variable and therefore is or is not inserted into that set. The event processing demand is inserted only if the process is currently waiting on the event variable represented by the owner of that set. Similarly, the set "pr--ro" designates the set of resource objects currently assigned to a process. This is also a "sometimes" relationship. If a resource object is assigned to a process, then the entity resource object is inserted in that set. Otherwise, it is not inserted and the corresponding resource object is available for assignment upon request. There are three primitive operations associated with this basic event management architecture: "Wait", "Test" and "Post". These primitives are described below in two different forms. First, an English language description is given, then it is precisely described in the form of a function definition algorithm. This function definition algorithm is written in PL/1 languages and references standard database set manipulation primitives (e.g. find next, find owner, empty, etc. . . ). A complete definition of these primitives is given in (5). The Wait-On-Event-Variable primitive is a P-like operation. If a process issues a wait on an event variable while an event occurrence is outstanding, the corresponding resource is assigned to the process and the process is so notified. This involves inserting the resource object into the pr-ro set owned by the process. Otherwise, the process is inserted into the set ev--epd of processes waiting on the event variable. Table 3a is the precise definition of the Wait-On-Event-Variable primitive expressed as a function definition algorithm.
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 --dispatch (p --prptr);
end wait --on --event --variable;
______________________________________
The Test-On-Event-Variable primitive is a similar operation except that the process will not wait for an event to happen, it is only notified as to whether or not the event did occur and the resource object assigned. The function definition algorithm for Test-On-Event-Variable is contained in Table 3b.
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;
/* 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;
______________________________________
In the context of the architecture described in FIG. 1a Post-On-Event-Variable is a V-like operation which releases the assignment on the resource associated with the designated event variable. The operation involves removing the resource from the "pr--ro" set. If the set of waiting processes on that event variable is not empty ("ev--epd"), then the process at the head of the queue is removed and reactivated. This process detects the event occurrence and gains control of the resource just released. This is represented by the insertion of that resource into the "pr--ro" set owned by the reactivated process. See Table 3c.
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;
/* Make resource available*/
Call remove (evptr, "pr-ro)
/* 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;
______________________________________
3. Deadlock considerations Earlier we 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 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, reveals an annular or closed loop structure. FIG. 1b schematically illustrates an example of deadlock detection. Process #1 wants to have resource A assigned to it. It declares its intent to do so by executing a Wait-On-Event-Variable primitive. The primitive first finds that resource A is not available. It is assigned to process #3. Other processes are also waiting for it. Will process #1 be allowed to wait too? Not in the situation illustrated because: (a) resource A is assigned to process 3 (pr--ro set), (b) process 3 is waiting on resource c (ev--epd set), (c) resource C is assigned to process 7 (pr--ro set), (d) process 7 is waiting on resource F (ev--epd set), (e) resource F is assigned to process 1 (pr--ro set). If the statement "process 1 is waiting on resource A" were added, then a closed loop would result. In this case, ignoring cache memory opportunities, it requires only six memory fetches to discover and to reject the requested Wait-on-Event primitive. The "deadly embrace" procedure in Table 3d gives the PL/1 algorithmic description of the deadlock detection algorithm for the semaphore of FIG. 1a.
TABLE 3d:
______________________________________
Procedure for Deadlock Detection
______________________________________
deadly --embrace: procedure(p --evptr, p --prptr) returns(bit(1));
/*This function examines the request of a process (p --prptr)
to wait upon an event (p --evptr) and returns a true value ("1"b)
if a deadly embrace would result from the wait. Else it returns
a false value ("0"b). */
call findowner(prptr, "pr ----ro", p --evptr);
if prptr = p --prptr
then return ("1"b);
if inserted(prptr, "ev ----epd")
then return("0"b);
call findowner(p --evptr, "ev ----epd", prptr);
return(deadly --embrace evptr, prptr));
end simple --semaphore;
______________________________________
4. General Semaphore Architecture FIG. 1c describes a more general case where resource objects are assigned on the basis of requests directed against a resource class. Each resource object in the class is equally acceptable to the requesting process. Thus we see the first fracturing of the ro/rc/evo/ev quadruple. Here, we must treat event variables and event occurrence outstanding on an event variable. However, the event occurrence still represents the availability of a single resource object within the corresponding resource class. This is shown by the combined ro/evo entity. The "rc--ro" set defines all the resource objects in a resource class. The "ev--evo" set defines the "sometime" relationship between the event variable and the event occurrence. The sometime is defined as the time when the resource object is not assigned and therefore available. We still have a one-for-one relationship between resource class, and the event variable as shown by the rc/ev box. We still have the one-for-one relationship between event processing demand and process as shown by the epd/pr box. The "ev--pr" set of processes waiting on an event variable remains as before. So does the resource assignment set pr--ro. In the context of FIG. 1c, the Post-On-Event-Variable becomes an implicit operation. It is invoked as part of the Release-Resource-Assignment operation directed to a particular resource object. An event occurrence is posted on the event variable associated with the resource class which controls the released resource object. This is reflected by the insertion of the event occurrence entity associated with the released resource object into the "ev-evo" set of its event variable. If there is a process waiting on the event variable, the resource object is reassigned and the process redispatched as before. The explicit dissociation of the event variable and event occurrence entities imply that an event may have a condition and a reaction that involves distinct entities. Here, for example the event condition pertains to the availability of any member of a resource class while the event reaction involves the assignment of a particular resource object. Let us return for a moment to the message management problem. We did point out that the detection of an event occurrence entailed the assignment of a unique message to one of the message handling processes. We did not elaborate however on exactly how the message handler gets notified of the identity of the assigned message. This is a non-trivial problem owing to the asynchronous nature of the required information transfer. To resolve it, we will define an extension to the semaphore mechanism permitting a V-operation to append a unique message of descriptive information to each event occurrence. Conversely, an event occurrence detected by a P-operation will return the corresponding message to the process which issues it. This information may be stored, until it is needed, within the event occurrence entity. In the semaphore architecture depicted in FIG. 1c, the deadlock detection algorithm must survey the occurrences of three set classes, "pr-ro", rc--ro" and "ev-epd" to determine whether a waiting process would create the annular structure for all resource objects which would signify a deadly embrace. 5. Trap Semaphore Architecture Observe that the binary and general gating semaphore mechanism (FIGS. 1a & 1c) do not support the concept of foreground reaction. To introduce this feature into the semaphore architecture, we can retain the same entity classes but we must adjust the relationships between entity classes. This leads to defining several new set classes and functional primitives. FIG. 1d is an entity structure diagram describing the architecture of a semaphore mechanism with a trap feature. This trap semaphore is distinct from the binary and general gating semaphores which we have developed through FIGS. 1a and 1c. You should note that the event processing demand which had existed on a one-for-one basis with the process entity has now been detached and re-associated on a one-for-one basis with the event variable. Thus the "ev--epd" set has disappeared and a new "pr--epd1" set has been created. This is a "sometime" set meaning that an event processing demand in the role of member is sometimes inserted into a set. This time is when the owner process has a "Set-Trap-On-Event" primitive in effect upon the trap semaphore. We have also added the "pr-epd2" set. This is a sometime set where the insertion of an event processing demand signifies that there are event occurrences waiting which have not been made known to the process because the event occurrences happened while the process was executing a trap procedure and thus was not interruptable. The impact of the trap feature on the event posting mechanism can be summarized as follows: When an event occurrence is posted on the semaphore, the current state of the event processing demand is examined with regard to its insertion in the "pr--epd1" set. If the event processing demand is currently inserted into such a set, then a trap demand is in effect and the event occurrence is "assigned" to the process which owns the "pr--epd1" set. The resource object associated with the event occurrence is inserted into the "pr--ro" owned by that process. If the process is not currently in "trap" mode, a call is made to the trap procedure designated by the "Set-Trap-On-Event" primitive. That procedure would take whatever action was appropriate to the foreground activity associated with the event occurrence and then returns the process to what it was doing. If the process is currently executing a trap procedure, the event occurrence is inserted in the "epd--evo" set to make it known when the trap procedure can subsequently be executed. If the event processing demand is not currently inserted in a "pr--epd1" set then the trap is not set and the event occurrence is inserted in the "ev--evo" set rather than the "epd--evo" set. If the event happens several times (resource objects are released by processes) then all event occurrence representing the released resources are inserted into the "ev--evo" set. When a "Set-Trap-on-Event" primitive is executed, the event occurrences currently inserted in the "ev--evo" set may be removed and inserted in the "epd--evo". The number of event occurrences which may be removed and inserted is controlled by the maximum count parameter of the event processing demand. The count may be set at 1, 2 or more. For each event occurrence which is transferred, the trap procedure is executed. However, each such procedure execution is delayed until the prior execution is completed. Each "trap" event processing demand with unnotified event occurrences is inserted in the "pr--epd2" so they can await the completion of the currently active trap procedure. The normal event detection mechanism is disallowed with a trap semaphore. It is illegal for a process to wait/test such a trap semaphore as it is made known of event occurrences through the trap invoked procedure execution. The following example illustrates a typical application of the trap semaphore. Consider a process P1 whose operation is gated by recurring event occurrences gate posted on an event variable E1. Each occurrence is accompanied with a message indicating the nature of the required processing. Typically, this processing would be handled as a gate reaction, just as if using a single semaphore. Although the exact timing of each event occurrence cannot be predicted, there is an implicit assumption that such event will indeed occur. It is therefore appropriate for the process to wait on such event occurrences. Consider now a trap event variable E2 associated with an event whose occurrence is possible although not probable. This might be for example an exception situation requiring an urgent reaction on the part of the process P1. The problem is that P1 cannot really assume that E2 will ever occur and therefore it should not wait on it. In addition, there may be a sense of urgency associated with the reaction to an occurrence of E2 which should somehow pre-empt other routine work in progress such as that related to occurrences of E1. The use of the test operation would not therefore be satisfactory. The use of the trap semaphore offers a clean solution to this apparent dilemma. Occurrences posted on E1 are processed as before. E1 is treated as a gating event. The process P1 detects occurrences posted on E1 by a wait operation and processes them as a gated reaction. E2 is considered as a trap event. Its occurrences are detected using a trap operation and are processed by the specified trap procedure. Gating events are handled sequentially within an event handling process while exception events are processed as they happen. Note that a process can be in a wait state on a gating event variable and have concurrently a trap event processing demand in effect on one or several trap event variables. If the process is waiting on a gate event variable, the posting of an event occurrence on a trap event variable will cause the event occurrence to be assigned to the event processing demand, an implicit call to be made to the trap procedure, and the process to be reactivated. It will perform the trap procedure and then the wait operation will be reissued upon the return from the trap procedure. The example cited earlier of the communications line processor is a perfect case for the use of two event variables, one trap event variable is established, where each event occurrence defines the arrival of a byte in a buffer to be quickly be removed. A gated event variable is established, where each event occurrence defines a byte which has been removed from the buffer and is awaiting the necessary editing associated with it. A single process could handle the foreground emptying of the buffer with the trap procedure and the background editing with its gated procedure. The higher priority of emptying the buffer is recognized by the immediate interrupt of the process in either the wait state or the background editing state to execute the trap procedure which is assigned the task of emptying the buffer. As a single process may have a number of "Set-Trap-On-Event" primitives outstanding on different trap event variables, it could be monitoring several different communications buffers simultaneously. One of the most attractive characteristics of the trap semaphore is the opportunity it gives a process to pursue its normal activities while, asynchronously, the semaphore keeps track of the posting of trap event occurrences. In effect, the "Set-Trap-On-Event" operation amounts to registering the current process with the semaphore as a candidate for assignment of potential occurrences. 6. Extended Semaphore Architecture The gated semaphore (FIGS. 1a and 1c) and the trap semaphore (FIG. 1d), as described to this point, are both limited in a particular sense. The next stage is to eliminate these constraints. The gated semaphore, as described, only considers the request of a process when the process is actually waiting upon the event occurrence to happen. As a result, the process can attempt to acquire control of a resource only while waiting for it. And it cannot do any other processing while it waits. Secondly, if it wanted to acquire several resources which were controlled by separate semaphores, then it cannot wait on both or all concurrently. It is forced to serialize this resource acquisition and any actual processing that it could have been doing in parallel. In a similar way, the trap semaphore as previously described is limited in that only one process can have a trap event processing demand set upon it at a given time. This means that very rapid processing of the trap events is limited to the capability of a simple trap process to execute its trap procedure and get back to handle the next event occurrence. Both of these problems yield to the same basic change in the control structure. This change is specified in FIG. 1e. In this entity structure diagram the "event processing demand" entity has been separated from both the event variable process entities. The net result is that a many-to-many relationship can now exist between the "event variable" entity and the "process" entity. The "event processing demand" entity now clearly specifies that a process wants the event management mechanism to take a particular event variable under surveillance on its behalf. Further, this demand for surveillance can be in either "trap" or "gate" mode. From the point of view of the "gate" demand, the event mechanism can note the occurrence of an event and immediately assign it to the first available and unsatisfied "event processing demand" entity. Further, it would immediately assign the associated resource objects to the requesting process. Because several event processing demands may be outstanding concurrently, resources of several different resource classes may be collected simultaneously. Furthermore, the process is free to continue active processing until it must have the results of the event processing demand. Only then will it execute a wait upon the event processing demand so that it can be waited if the event has not happened, or continue if the event has occurred and has been assigned to it. From the point of view of the " trap" demand, it is now possible for several processes to set event processing demands on the same semaphore. In that manner, the simultaneous execution capabilities of independent processes can be brought to bear to handle whatever high priority trap demands that might exist at a moment. To set up this event monitoring, the "Set-Trap-On-Event" operation has been generalized into a "Initiate-Event-Processing" primitive, with or without the trap option. Because the process is free to continue processing it will also want a "Terminate-Event-Processing" primitive to remove the demand if its interests change. The Terminate-Event-Processing operation will release any event occurrences which have been assigned to the demand and reverses any resource object assignments which have taken place. The complete separation of the event processing demand entity from the event variable and process entities modifies the structure of the sets in which they participate. The "ev--epd" set from FIGS. 1a and 1c and the "pr--epd1" and "pr--epd2" from FIG. 1d all now appear as the semaphore can act as either a trap or gate semaphore. Both sets have been converted from "sometime" membership sets to required membership as an event processing demand, if it exists at all, must be inserted in both sets. A new set has been added, the "epd--pr" set where the process entity is a sometime member. The time is when the process is waiting upon an event processing demand of the gate type. Table 3 lists all the sets, and their definitions involved in the extended semaphore architecture.
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----epdl
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
rc----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
__________________________________________________________________________
The Initiate-Event-Processing primitive establishes the claim of a process upon any event occurrence which may become available under an event variable. Two options are granted with this primitive. The first option relates to whether the demand will be a "trap" demand or a "gate" demand. The second option provides for specifying of the multiple occurrences of the event to be queued for a process. Table 5A is the function definition algorithm of the Initiate-Event-Processing primitive written in PL/1. The Evaluate-Event procedure determines whether there are any event occurrences available and assigns them to the event processing demand, up to its maximum occurrence count. This procedure is shared by Initiate-Event-Processing with the other primitives. Table 5B lists this procedure.
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. This 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 --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;
______________________________________
The Terminate-Event-Processing primitive causes the event processing demand entity to be deleted, thus terminating the surveillance of the event variable for the process. Any event occurrences which have been assigned to the process, but for which the process has not received notice will be returned and made available to other event processing demands. Any resource objects controlled by the event occurrence will be released. Table 5C is the function definition algorithm of the Terminate-Event-Processing primitive. It references the evaluate event procedure (Table 5B) to see that any event occurrences which were made available will be void if possible.
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
processing demand are released along with their associated
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;
__________________________________________________________________________
The Wait-On-Event-Variable primitive for the extended semaphore closely parallels the same primitive for the binary and general semaphores. The main difference is that the extended semaphore will permit the process to collect a resource whenever it becomes available. Therefore there is a greater chance that when the Wait primitive is executed that it will not have to wait because the resource object will already be assigned. The function definition algorithm for Wait-On-Event-Variable is given in Table 5D. Because the extended semaphore assigns resource objects out of a resource class, a notification message is established to tell the process something about the resource occurrence. This was not necessary with the binary semaphore as the resource class had exactly one resource occurrence.
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->epd.trap = ""
p --code = 3;
return;
end;
/* determine whether event has happended */
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);
______________________________________
The deadlock detection algorithm for the extended semaphore is essentially the same as that for the general semaphore (FIG. 1c). It is called as part of the Wait-On-Event-Variable primitive to be assured that the process is not indirectly waiting upon itself. In that the wait implies waiting for any one member of a class of resource, the chances of deadlock are reduced. However, the possibility must be checked.
TABLE 5E:
__________________________________________________________________________
Deadlock Detection Function
__________________________________________________________________________
deadly --embrace: procedure ((p --epdptr), (p --prptr)) returns (bit
(1));
/* This function determines whether there is at least one
resource object in a resource class which is not directly or
indirectly assigned to a particlar process. */
call findowner(evptr, "ev --epd", p --epdptr);
call findnext(roptr, "rc ----ro", evptr, eos);
do while ( eos);
call findowner(prptr, "pr ----ro", roptr);
/* determine whether process is requesting process */
if prptr = p --prptr
then do;
/* determine whether process is running */
if inserted (prptr, "epd ----pr")
then return ("o"b);
/* determine whether process is waiting on the requesting
process */
call findowner(epdptr, "epd ----pr", prptr);
if deadly --embrace(epdptr, p --prptr);
then return ("o"b);
end;
/* see if an alternate resource object is releasable */
call findnext(roptr, "rc ----ro", roptr, eos);
end;
/* deadly embrace through all resource objects of resource
class */
return ("1"b);
end deadly --embrace;
__________________________________________________________________________
The Test-On-Event-Variable is similar to the Wait-On-Event-Variable primitive except the process receives a "not happened" signal rather than being waited if the event has not happened. The function definition algorithm for the test primitive is given in FIG. 5f. It is identical to the first eight percent of the Wait-On-Event-Variable primitive (FIG. 5b).
TABLE 5F:
______________________________________
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 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;
______________________________________
The Release-Resource Assignment primitive makes a resource object which has been assigned available to other event processing demands. It does this by first releasing the resource object and placing the event occurrence into the set owned by the event variable. It then checks to see whether there are any unsatisfied event process demands queued on the event variable. Table 5G is the function definition algorithm for the release primitive. Some information may be transmitted to the next user of the resource object through the notification message.
TABLE 5G:
______________________________________
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->evo.message = p-notification-message;
call evaluate --event(rcptr);
end release --resource --assignment;
______________________________________
II. DESCRIPTION OF A PREFERRED EMBODIMENT 1. General Discussion The invention operates typically in the hardware system environment, hereinafter described, coordinated by a hardware/firmware/software operating system. Referring to FIG. 2a the subsystems are the processor subsystem 101, the storage subsystem 102, and one or more--up to 32--peripheral subsystems 103. The processor subsystem contains a central processing unit (CPU) 104 and up to four input/output control units (IOC) 105. Each peripheral subsystem consists of a peripheral control unit (PCU) 106, a number of device adapters (DA) 107, and up to 256 peripheral I/O devices 108. The storage subsystem 102 consists of one to four semiconductor memory modules of 32 to 512 kilobytes each. In the processor subsystem 10, the CPU 104 performs the basic processing operations for the system, and interfaces with memory 102. The IOC 105 controls all information exchanges between the storage subsystem 102 and peripheral devices 106. A. Central Processing Unit The CPU includes a main memory synchronizer 109, a buffer store 110, various elements that comprise the computational unit 111, and optional emulation facilities 112. The main memory synchronizer 109 resolves conflicts for the use of main memory among the computational unit 111, the buffer store 110, and the IOC 109. Conflicts are resolved on a priority basis: the IOC has the highest priority followed by memory writes (from the computational unit) and then memory reads (into the buffer store). The main CPU also includes the address control unit ACU 131 which controls main memory addressing and the associative memory AS 132 used to store most recently used addresses of main memory. The buffer store 110 is a small high-speed buffer memory that reproduces a selected region of main memory and interfaces with the computational unit to decrease average memory access time. During each memory read, both the buffer store and main memory are accessed. If the information to be fetched is already in the buffer store, the main memory read is terminated and the information fetched from the buffer store. Otherwise the main memory 102 is read. Every time this is done, the CPU 104 fetches 32 bytes that contains the desired information. This information remains in the buffer store for future memory references. Since the buffer store is transparent to software, the program controlling the computer at any given moment cannot determine whether the information it is processing has been fetched from the buffer store or from main memory. The computational unit 11 performs all data processing and address generation within the CPU. A typical control store 130 within the computational unit (see a book entitled Microprogramming: Principles and Practices, Samir S. Husson, Prentice Hall, Inc.) contains firmware which initializes the system, controls the CPU 104 and IOC 105, and decodes an instruction set (not shown). Optionally the control store may provide scientific instructions, test routines, emulation packages, or special purpose features which extend the capabilities of the processor subsystem. As an option, the CPU provides emulation of systems other than the instant system. Emulators 112 are components of firmware, software, and in some instances hardware. B. Input-Output Control Unit The IOC 105 portion of the processor subsystem provides a data path between any peripheral subsystem 103 and the storage subystem 102. This path allows for the initiation of peripheral commands and controls the resulting data transfers. An IOC can typically handle up to 32 channel control units (not shown). C. Peripheral Subsystems In a peripheral subsystem 103 on FIG. 2a the PCU 106 is a stand-alone microprogramming processor that relieves the load on the CPU 104 by controlling the i/o devices 108 during i/o operations. The PCU does this by executing instructions contained in a channel program. This program results in arithmetic, logical, transfer, shift, and branch operations being performed in the PCU. There are several kinds of PCU's according to the kind of device each controls: i.e. unit record, mass (disk) storage, magnetic tape, communications, etc. Device adapters 107 mediate between every PCU and the devices it controls. Each contains the dedicated firmware and logic necessary to implement communication with a particular type of device. Depending on the type, a DA 107 controls one or several devices. The major functions performed by a peripheral subsystem 103 are as follows: 1. Transforming CPU instructions into a series of commands acceptable to the appropriate peripheral device. 2. Packing and unpacking data in the form needed by the CPU or the appropriate peripheral device. 3. Keeping the CPU informed of the status of the subsystem and of the devices under its control. 4. Independently initiating and processing error and recovery procedures. 5. Allowing on-line diagnosis of a device without disturbing the device-sharing capabilities of the associated peripheral processor. A CPU resolves conflicts for main memory between devices attached to it; however, the IOC resolves conflicts between PCU's. D. Storage Subsystem Each memory module 1-4 is 4 or 8 bytes wide. The number of modules, their size, and the data path width may vary according to size of computer. Memory modules are four-way interleaved in such a way that the four modules are accessed sequentially (module 1 contains the first 8 bytes, module 2 contains the second 8 bytes, etc.). Interleaving decreases the number of conflicts for access to main memory and thereby decreases the average memory access time. Memory is reconfigurable in case of failure; i.e., blocks of memory within a module may be removed without destroying contiguous addressing. Main memory 102 consists of a capacitive storage medium in the form of metal oxide semiconductor (MOS) chips. This medium operates on the refresh principle to maintain information. Each memory location is typically refreshed at least once every 2 milliseconds; the design ensures that few conflicts occur between refresh timing and memory accesses. (In cases of conflict, refreshing takes precedence). An area at the beginning of main memory is reserved for hardware and firmware. The upper limit of this area is defined by the content of a boundary address register (BAR - to be later described) which is visible to the system software. The BAR content is set at system initialization time. The memory area below the address specified in the BAR can contain IOC tables which define the configuration of the peripheral subsystems, firmware to control the CPU, or microprograms and tables for emulation. The size of the area below the address specified in the BAR depends on the system configuration. Whether microprograms are in main memory or control store depends on the system configuration and the applications run on the system. 2. Basic Machine Structures There are typically three basic data structures utilized in this hardware: data formats, software visible registers, and the instruction formats. A. Data Formats Information is transferred between memory and the CPU in multiples of 8 parallel bits. Each 8-bit unit of information is called a byte. Parity or error correction data is also transferred with data but cannot be affected by software. Therefore, in this patent specification the term data excludes the associated parity or error correction data. B. Bytes Bits within a byte are numbered 0 through 7 from left to right. Bytes are processed separately or in groups. Two bytes constitute a halfword, 4 bytes a word, 8 bytes a doubleword, and 16 bytes a quadword. These are the basic formats for all data, including instructions. C. Data Representation All data are in binary form, but may be interpreted as binary, decimal, or alphanumeric. Data bits are interpreted in groups of four, as binary coded decimal data; eight as alphanumeric, or 16 to 64 as binary digits. The latter are interpreted as signed, fixed, or floating-point numbers in binary notation. Any number of contiguous bits up to a doubleword may also be manipulated as a string. The alphanumeric character set is represented in EBCDIC. ASCII is supported as an alternate exchange code. D. Byte Addresses Byte locations in main memory are consecutively numbered starting with zero; each number is the address of the byte. A group of consecutive bytes is said to be halfword-, word-, doubleword-, or quadword-aligned, if the address of the left byte in a group is a multiple of 2, 4, 8, or 16, respectively. Whenever a halfword, word, doubleword, or quadword is so aligned, that unit can be fetched from that address. The location of data in main memory is specified by a data descriptor which is accessed indirectly during address development. (See patent application Ser. No. 470,496 filed May 16, 1974 and having priority date May 16, 1973 entitled Segmented Address Development and assigned to the same assignee as the instant application). E. Visible Registers There are 33 user-visible registers in the CPU 104 FIG. 2a whose contents collectively define the state of the CPU. There are four types: (See FIG. 2). 1. general registers 2. base registers 3. scientific registers (optional) 4. miscellaneous registers F. General Registers General registers (GR) 201 FIG. 2b are used to manipulate fixed-point binary numbers and bit strings. There are typically sixteen 32-bit general registers in the CPU 104--GR0 through GR15. General register GR8 through GR15 are also usable as index registers. When used as index registers, they are herein called X0 through X7: Indexing is performed using the 32-bit two's complement integer contained in a register. G. Base Registers Base registers (BR) have the same format as instruction counters IC and stack registers 202-203. Base registers are used during address computation to define a part of memory. There are typically eight 32-bit base registers, BR0 through BR7. H. Scientific Registers Scientific registers (SR) are optional equipment for computation with floating-point binary numbers. There are typically four 8-byte scientific registers which are referred to as SR0 through SR3. Scientific registers have the format 204-205 of FIG. 2b. I. Miscellaneous Registers There are five other registers: .cndot. instruction counter--having format 202-203; .cndot. status register--having format 207; .cndot. stack register (called the T register); .cndot. boundary address register--having format 202-203; and .cndot. hardware control mask register--having format 208. The instruction counter (IC) is a 32-bit register that contains the address of the instruction being executed. The status register (STR) 207 is an 8-bit register that records facts about the procedure currently being executed, for example, whether an underflow was caused by the most recent operation. The stack register also known as the T-register is a 32-bit register that contains a pointer to the top of a pushdown stack associated with the currently active procedure. Stacks to be described infra provide a work space, and a mechanism for saving local variables and preserving procedure entry, and return information. The boundary address register (BAR) 206 is a 28-bit register which specifies the lowest absolute main memory address accessible by software. This register is loaded during system initialization and can only be read by software. The hardware control mask register 208 is an 8-bit register which records machine condition information. J. Instruction Formats There are approximately 200 instructions although more or less may be utilized. Each instruction is one of four different lengths but always an even number of bytes long. Instructions are stored in consecutive storage locations. The address of the leftmost byte is a multiple of 2, and is the address of the instruction. The eight most significant bits (and in some cases bits 8 through 11 or 12 through 15) of an instruction represent the operation code, while the remaining bits represent one or more operands. An operand may be a register designator, displacement designator, address syllable (logical address), literal value, immediate literal value. The type and number of operands are determined by the instruction format. 3. SYSTEM ORGANIZATION A. Job Step and Task Work to be performed by the computer system is defined externally by a series of job steps via a job control language. A job step is a unit of work to which hardware resources are allocated. Typically a job step consists of several tasks. A task is the smallest unit of user defined work consisting of a stream of instructions executed without parallelism. B. Process The user-visible concepts of task and job step are represented in the hardware by a process and process group, respectively. A process is defined as an ordered sequence of instructions which can be executed asynchronously by the CPU (i.e., several processes can be active and sharing resources, but only one process is actually running at any one instant). A process group is a related set of processes necessary to perform one job step. C. Process Control Block and System Base Because processes can relinquish CPU control at various points during their execution, a storage area in main memory is made available to a process to save CPU status. This status information is utilized to precondition the CPU before a process regains control of the CPU. The storage area assigned to a process is called a process control block (PCB) 400 on FIG. 4. The data contained in a PCB include the addresses of memory areas (address space) assigned to the process, the contents of all pertinent registers, and the state of the process. Thus a PCB serves as a temporary storage area for information necessary to start or restart a process without any information loss. Each PCB is visible to the hardware and can be addressed by the operating system via a set of hardware tables developed during system initialization and modified during system operation (FIG. 5). There is an absolute main memory area which is referred to as the system base (FIGS. 5 and 6). This area is developed by firmware and is accessible via the base address register (BAR) 501 which can be read but not written. The system base 502 contains a number of system attributes which include a job step number and a process group number (J, P) respectively for the currently running process. Another attribute in the system base is a pointer to a hardware defined data structure known as the J table 503. This table contains an entry for every job step presently in the system. Each entry in the J table 503 points to an associated P table 504 which is also a hardware defined data structure. This table defines a process group and contains an entry for every process in the process group. Each P-table entry points to a PCB 400. Referring to FIG. 5 the J-table pointer 505 indexed by the J number via the arithmetic portion 506 of computational unit 111 (FIG. 2a) provides access to a J-table entry 503. This entry contains a P-table pointer which when indexed by the P number via computational unit 506 provides access to a P-table entry 504. The P-table entry contains a pointer 507 to the PCB of the current running process. Thus the operating system can access the active PCB using the contents of the BAR 501 and can access any other PCB given its associated (J, P) logic name. D. Memory Segmentation In a multiprocess environment, such as herein described there are many processes in memory at any given time. These processes vary in size and demand for memory which causes a memory allocation problem. The hardware herein described in cooperation with an operating system (not shown herein) solves the problem by dynamically allocating memory space. Due to the random nature of memory requirements, memory is allocated in variable size segments and the memory allocation can be restructured during process run time. Thus, a process may be allocated a number of noncontiguous memory segments. This memory allocation method is called segmentation. Segmentation presents an additional problem in that memory addresses have to be modified whenever part or all of a process is relocated. To alleviate this problem the system herein described provides a technique whereby addresses used by a process are logical rather than absolute main memory addresses. These logical addresses are used to develop absolute addresses. Segmentation also allows each process to access its own or related memory segments via a system of segment descriptors. By accessing a segment descriptor, a process can obtain the address of a segment. Segment descriptors are contained in main memory and are maintained by the operating system. Each process may have access up to 2068 memory segments. Normally, this would require an equal number of segment descriptors per process. However, since segments can be shared, the operating system groups segment descriptors into segment tables. This grouping is based on accessability by one process (task), a process group (job step), or globally (system wide). Each process may have up to 15 segment tables associated with it. This technique requires only one segment descriptor for each segment which can be accessed by a process via a segment table. Thus, the memory space required for segment descriptors is decreased; memory updating during relocation is reduced; and some program protection is provided. The main mechanism for program protection is the ring system. See U.S. patent application entitled "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 having French Ser. No. 73 42706 and further filed in the U.S. within the priority convention date of Dec. 2, 1974 and having U.S. Ser. No. 528,953 and assigned to the same assignee named herein. A process must be able to determine which segments it is allowed to access. Accordingly, the system provides a process with two segment table word arrays (STWA). These arrays contain the addresses of all segment tables accessible to a process. There are two segment table word arrays per process because there are two segment sizes, large and small. Large segments have a maximum size of 2.sup.22 bytes while small segments have a maximum size of 2.sup.16 bytes. All segments vary in size in 16-byte increments up to the maximum. A system can typically accomod | ||||||