14. LOW-LEVEL FACILITIES
This section discusses low-level facilities for multitasking and for I/O. It is anticipated that most
programmers will use the high-level multitasking facilities (described in Chapter 10) and the high-level
I/O facilities (described in Appendix A). The low-level facilities are provided for system programmers
as tools for building new high-level facilities.
The philosophy is to make available the low-level primitives that are used in defining the high-level
facilities. These primitives can then be used to define alternative high-level facilities when needed.
Alternative methods of sending and receiving messages, delaying activations, controlling access to
shared data, and scheduling activations can all be defined. In each case a capsule will be defined
which provides one or more new types and associated operations.
The rationale for this philosophy is simply that not enough is known about multitasking to enforce
a single system design paradigm on all parallel systems.
14.1 MORE ABOUT MAILBOXES
Some of the low-level operations on mailboxes that were not described in Section 10.3 are
described below. The use of SEND and RECEIVE as waiting invocations is described in Section 14.3.
14.1.1 AVAILABLE COUNTS
If m is a mailbox, than the result of
is the number of messages that can be sent to m without waiting. This value is the number of empty
buffers in m plus the number of unsatisfied receive requests on m. Note that the result of invoking
EMPTY_SLOTS can change if messages are sent to m or if any of the receive requests are revoked.
If m is a mailbox, than the result of
is the number of messages that can be received from m without waiting. This value is the number of
full buffers in m plus the number of unsatisfied send requests on m. Note that the result can change if
messages are received from m, or if any of the send requests are revoked.
14.1.2 CONDITIONAL MESSAGE PASSING
If m is a mailbox, v is a message, and b is a boolean value, then elaboration of
is similar to elaboration of
except that when a wait would have been required, no send occurs and b is set to false.
If the send can complete without waiting, then b is set to true. There is also a conditional
receive procedure of the form
with similar rules.
14.1.3 ASSIGNMENT AND EQUALITY OF MAILBOXES
Mailboxes are implemented as indirect types. Assignment for mailboxes is a pointer assignment.
For the assignment
m1 := m2;
where m1 and m2 are both mailboxes, the message subtypes of both must be the same; however,
m1 and m2 need not have the same length. Equality returns true if both mailboxes have equal pointers.
Hardware interrupts are accessed via mailboxes with an INTERRUPT location. The subtype of the message
associated with a given interrupt are device and implementation dependent. When an interrupt occurs,
associated data is collected and sent as a message. The interrupt is then cleared.
Suppose a keyboard causes Interrupt 16 every time a character is typed. The interrupt is handled as follows:
14.2 MORE ABOUT THE ACT SCHEDULER
14.2.1 ACT VARIABLE STATES
Each ACT variable has a state that consists of three parts:
a boolean. Active is true if the ACT variable is associated with an activation list that
has been created, but is not yet completed, and false otherwise.
a boolean. Waiting is true if the activation associated with the ACT variable is currently waiting.
a boolean. An activation whose ACT variable has suspended set to true is not eligible to be run.
When an ACT variable is created, active, waiting, and suspended are automatically set to false.
If a is an act variable, then the following functions produce the current value of each of the three
parts of the state.
When an activation is associated with the act variable, the value of ACTIVE is true.
The suspended boolean is explicitly set by the user using the following procedures:
14.2.2 CRITICAL AREAS
When an activation is executing certain particularly critical areas of code lt ls desirable to
- prevent the activation from being preempted by some other activation (even lf that other
activation has a higher priority), and
- temporarily ignore any EXTERMINATE invocations for the activation.
This can be achieved by elaborating
at the beginning ot the critical area and elaborating
at its end. When an activation is created, it is noncritical. Invocation of CRITICAL makes it critical.
Invocation of NONCRITICAL make it again noncritical. When a running activation is critical it is never
preempted. When EXTERMINATE is invoked for some critical activation, no action is taken until the
activation becomes noncritical; at which time X_TERMINATE is raised.
An activation should be critical only for very short sections of code.
14.2.3 SCHEDULING ALGORITHM
This section gives the scheduling rules used by the ACT scheduler.
An activation is eligible to run if
- it is active;
- it is not waiting;
- it is not suspended.
If a and b are activations which are both eligible, the priority of a is higher than the priority of b,
and b is not critical, then a will be running if b is running.
If a and b are activations which are both eligible, both have the same priority, a became eligible
before b, and b is not critical, then a will be running if b is running.
If an activation is both running and critical, then it will continue to run until it becomes noncritical,
or until it waits.
If there are any activations that are eligible, then at least one of these will be running.
If two or more activations are running, no assumptions can be made about their relative speeds.
There are two kinds of operations used for the wait statement: synchronizing operations associated
with waiting invocations, and scheduler operations that cause the activation to wait. Such
operations can be defined to provide an alternative definition of the wait statement.
14.3.1 SYNCHRONIZING OPERATIONS FOR WAITING INVOCATIONS
For each kind of waiting invocation of the form
the following five operations must be defined.
- name_ST - a subtype. A variable with this subtype is created for every waiting
invocation that is examined. For example,
VAR v : name_ST;
- name_REQUEST (v, e1,e2,...,en) - a procedure. This operation is invoked to request that
the waiting invocation be enqueued on the appropriate wait queue. This operation is invoked
at most once for each waiting invocation in a wait statement.
- name_TEST (v, e1,e2,...,en) - a boolean function. The result of this function is true if the
waiting invocation can be successfully completed. The name_REQUEST procedure will have
been invoked prior to invoking name_TEST.
- name_COMPLETE (v, e1,e2,...,en) - a procedure. Invocation of this operation completes the
waiting invocation. It will be invoked only after name_TEST has produced true.
- name_REVOKE (v, e1,e2,...,en) - a procedure. This operation is invoked for every waiting
invocation for which name_REQUEST has been invoked. No other operations for a particular
waiting invocation will be invoked after name_REVOKE.
This example shows how the MAILBOX type could have been defined if it were not built-in. Note that
this definition has been simplified from the built-in MAILBOX type in four ways.
- It does not do all error checking.
- It is not particularly efficient.
- Not all operations are specified.
- It does not handle zero-length mailboxes.
This example assumes that a QUEUE[a] data type has been previously defined. Queues are
initially empty and have the following operations: INSERT, REMOVE, FIRST (gets first element without
removing it), SIZE, and DEQUEUE (removes a specified value from the queue).
14.3.2 ACT SCHEDULER OPERATIONS FOR WAITING
There are three ACT scheduler operations for waiting.
- SYNCH_RESET - a procedure. This procedure is invoked immediately before the name_TEST functions
are checked. Its effect is to override all previous SYNC_SIGNALS.
- SYNCH_WAIT - a procedure. This procedure is invoked after all name_TEST functions have
produced false. Waiting occurs if SYNC_SIGNAL has not been invoked for this activation
since the last time that SYNC_RESET was invoked.
SYNCH_SIGNAL (a) - a procedure (where a is a variable with type ACT). This procedure is invoked
to indicate that the result of one of the name_TEST operations of the specified activations will be different
when next invoked. If the activation is waiting, as a result of performing SYNC_WAIT, it will be awakened.
Extra invocations of SYNC_SIGNAL will not cause erroneous behavior since the name_TEST functions are again
invoked before completion of any waiting invocation.
14.3.3 EXPANSION OF THE WAIT STATEMENT
The wait statement
can be expanded to
Note that this is only one of the possible expansions. Translators are free to choose any expansion
that is consistent with the semantics of the language.
14.4 MORE ABOUT MUTUAL EXCLUSION
14.4.1 SEMANTICS OF THE REGION STATEMENT
A region statement has the form
and is roughly equivalent to
Note that LOCK is invoked at entry to the region and that UNLOCK is invoked at exit from the region
(even when the exit occurs as the result of an unhandled exception). Recall however, that a region
statement guarantees that the region will be unlocked no matter how it is left. There are two cases
where the rough expansion must be further refined
- Exits and gotos out of the body of a region must also cause UNLOCK to be invoked.
- If an EXTERMINATE occurs at certain critical points (such as after the LOCK but before the
GUARD), unlocking will not occur in the rough expansion. This problem is avoided by making
certain parts of the expansion be run as critical, so any exterminates will be deferred. In
particular, invocations of LOCK and UNLOCK will be run as critical, while the elaboration of the
body will not be critical.
A variable with any type for which LOCK and UNLOCK procedures are defined can be used in the region statement.
This example shows how monitors can be defined in the language. First an example is given of how
monitors can be used.
The two data types needed for monitors, MONITOR_LOCK and MONITOR_QUEUE, together with their
operations, are defined as follows:
14.4.2 MORE ABOUT DATALOCKS
In addition to lock and unlock, data lock variables also have operations EXCESS_LOCKS and OWNER.
If d is a data lock variable, then the result of
is the number of times that LOCK (d) has been invoked (but not necessarily completed) minus the
number of times UNLOCK (d) has been called. The values that result can be interpreted as follows:
- 0 - The lock is unlocked.
- 1 - The lock is locked and there are no activations waiting.
- >1 - There are activations waiting, attempting to lock the data lock.
Latches are the basic low-level synchronization type. Since LOCK and UNLOCK procedures are
available for latches, they can be used in the region statement.
Latches are either locked or unlocked. Elaboration of
(where t is a variable with type LATCH) will lock t if t is unlocked; otherwise, it will wait until t
becomes unlocked. If there are several activations waiting to lock a latch, which one will actually
succeed when the lock becomes unlocked is undefined. Elaboration of
will unlock latch t. Elaboration of
where bi is a boolean variable, will lock t, if t is unlocked, and set b to true; otherwise, t is not
changed and b is set to false.
The only virtue of latches is that they have an inexpensive implementation. In many cases, the waiting
can be done as busy waiting.
14.5 USER-DEFINED SCHEDULERS
In addition to the built-in priority ACT schedulers, users can define their own schedulers. The
scheduler to be used for an activation is determined, when the activation is created, by the type of
the activation variable specified (after NAMED) in the task invocation statement. User-defined
schedulers are capsules that define the type for their activation variables and a set of basic
scheduling operations. The operations are implemented in terms of invocation of the fundamental
operations of the built-in ACT scheduler. Synchronization schemes (including DATA_LOCK and
MAILBOXes) are designed in such a way that they will work correctly with any scheduler
14.5.1 ACT ASSIGNMENT AND EQUALITY
ACT is implemented as an indirect type. Assignment for variables with an ACT type is a pointer
assignment. The assignment
a1 := a2;
where al and a2 are both ACT variables, sets al to point to the same information as a2. Equality
returns true if both variables point to the same information. There is also a constant, NIL_ACT, which
has type ACT and is a nil pointer.
ACT assignment and equality are useful for creating queues of act variables.
14.5.2 LOW AND HIGH OPERATIONS
When an activation exists that is controller by a user-defined scheduler, there are really two
schedulers involved. The user-defined scheduler and the underlying ACT scheduler. There are also
two activation variables involved, one for each scheduler. For example,
VAR ua : USER_ACT;
CREATE t NAMED ua;
creates an activation of task t, which is controlled by the USER_ACT scheduler. The two
activation variables here are
- ua - The activation variable for the user-defined USER_ACT scheduler.
- Another variable of type ACT (which is not explicitly named, but for reference purposes
call it aa). The variable aa is the one by which the ACT scheduler controls scheduling of the
The result of elaborating
during elaboration of the activation of t will be aa, and the result of elaborating
during elaboration of the activation of t will be ua. The X_SCHED exception is raised if the activation
variable of the invoking activation does not have type USER_ACT. The function ME is called a
low-level operation (accessing the underlying ACT scheduler information), and the
function ME [USER_ACT] is called a high-level operation (accessing the specified
activation variable ua).
Variable ua normally contains sufficient information for the USER_ACT scheduler to find aa
(actually the information that aa points to). This can be done by including aa as a component of ua,
or by making ua an index into some scheduling queue that contains aa.
There are also two sets of scheduling operations available: one high-level set for the USER__ACT
scheduler, and another low-level set for the ACT scheduler. The high-level USER_ACT operations are:
These all invoke procedures defined for the USER_ACT scheduler. The low-level operations are:
These all invoke procedures defined for the ACT scheduler. The high-level operations will normally
invoke these low-level operations to actually achieve the scheduling.
To allow synchronization schemes to be independent of any particular scheduler, there is a way of getting
from ACT variable aa to the high-level operations upon the USER_ACT variable ua. This is
achieved by the following ACT scheduler operations:
The way in which these operations are achieved is described in the next subsection. These operations
allow synchronization operations to be ignorant of the particular scheduler that is being used.
For example, during the elaboration of the activation of t, invocation of
will cause the invocation
to occur. This means that the synchronization operations need not directly invoke
If this had been necessary, the synchronization operation would have needed knowledge of the type
Note that when activations are scheduled by the ACT scheduler (i.e., no user-defined scheduler is
involved), then the following operations are equivalent:
14.5.3 TASK ACTIVATION CREATION AND COMPLETION
Task Invocation Statement
The task invocation statement has the form
CREATE t(e1,e2,...,en) NAMED av;
The effect of elaborating this statement is
- create a new variable of type ACT (for reference call it aa).
- create a new activation of t, place information about it (e.g., starting address,
stack locations, save area, etc.) in aa.
- bind the actual parameters (e1,e2,...,en) to this activation.
- set up the following procedures
and place the address of each in aa. This allows access to the high-level scheduler, given only
the low-level activation variable aa.
- elaborate the following procedure invocation:
For activations scheduled by the ACT scheduler (i.e., when av has type ACT), this invokes
the ACT scheduler operation that starts up the activation. For activations scheduled by a
user-defined scheduler, this invokes the operation required for that scheduler.
When a task activation has completed the elaboration of the task body, the invocation
is elaborated. This allows the scheduler to remove the activation from its queues.
A ROUND ROBIN SCHEDULER
14.6 LOW-LEVEL I/O
Low-level I/O is provided to allow low-level access to the most primitive level of I/O provided in
the target computer. The high-level I/O described in Appendix A can be defined using low-level I/O,
together with the interrupt handling facilities described in Section 14.1.4.
LOW_IO (device, command, data);
will cause the specified command to be issued for the specified device, using the specified data. If
there is no data needed, the invocation
LOW_IO (device, command);
may also be available. The types of each of the parameters is implementation-dependent. The effect of
LOW_IO is implementation-dependent.
Steelman 8A requires that all high-level I/O be definable within the language. RED already has
mechanisms for specifying the exact representation and placement of data, and for handling interrupts.
Thus, the only remaining requirement is the ability to execute any of the primitive I/O instructions
defined by the hardware. This ability is provided by appropriate overloadings of the procedure
LOW_IO(device, command, data);
- 360 example