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.

RED RATIONALE 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

    EMPTY_SLOTS (m)

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

    FULL_SLOTS (m)

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.

EXAMPLES

14.1.2  CONDITIONAL MESSAGE PASSING

If m is a mailbox, v is a message, and b is a boolean value, then elaboration of

    COND_SEND (m,v,b)

is similar to elaboration of

    SEND (m,v)

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

    COND_RECEIVE (m,v,b)

with similar rules.

EXAMPLES

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.

EXAMPLES

14.1.4  INTERRUPTS

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.

EXAMPLES

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:

active	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.
waiting	a boolean. Waiting is true if the activation associated with the ACT variable is currently waiting.
suspended	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

1. prevent the activation from being preempted by some other activation (even lf that other activation has a higher priority), and

2. temporarily ignore any EXTERMINATE invocations for the activation.

This can be achieved by elaborating

    CRITICAL;

at the beginning ot the critical area and elaborating

    NONCRITICAL;

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.

NOTES

     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.

RULES

An activation is eligible to run if

1. it is active;

2. it is not waiting;

3. 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.

14.3  WAITING

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

RULES

For each kind of waiting invocation of the form

    name(e1,e2,...,en)

the following five operations must be defined.

1. name_ST - a subtype. A variable with this subtype is created for every waiting invocation that is examined. For example,

       VAR v : name_ST;

2. 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.

3. 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.

4. 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.

5. 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.

EXAMPLES

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.

1. It does not do all error checking.

2. It is not particularly efficient.

3. Not all operations are specified.

4. 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.

1. 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.

2. 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.

NOTES

     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

RULES

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

1. Exits and gotos out of the body of a region must also cause UNLOCK to be invoked.

2. 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.

NOTES

     A variable with any type for which LOCK and UNLOCK procedures are defined can be used in the region statement.

EXAMPLES

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

    EXCESS_LOCKS (d)

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:

1. 0   - The lock is unlocked.

2. 1   - The lock is locked and there are no activations waiting.

3. >1 - There are activations waiting, attempting to lock the data lock.

14.4.3  LATCH

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.

RULES

Latches are either locked or unlocked. Elaboration of

    LOCK (t);

(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

    UNLOCK (t);

will unlock latch t. Elaboration of

    COND_LOCK (t,b);

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.

NOTES

     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. NOTES

     ACT assignment and equality are useful for creating queues of act variables.

14.5.2  LOW AND HIGH OPERATIONS

RULES

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

1. ua - The activation variable for the user-defined USER_ACT scheduler.

2. 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 activation.

The result of elaborating

    ME

during elaboration of the activation of t will be aa, and the result of elaborating

    ME [USER-ACT]

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

    SYNC_WAIT;

will cause the invocation

    SYNC_WAIT(ua);

to occur. This means that the synchronization operations need not directly invoke

    SYNC_WAIT(ME[USER_ACT]);

If this had been necessary, the synchronization operation would have needed knowledge of the type USER_ACT.

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

RULES


Task Invocation Statement

The task invocation statement has the form

        CREATE t(e1,e2,...,en) NAMED av;

The effect of elaborating this statement is

1. create a new variable of type ACT (for reference call it aa).

2. create a new activation of t, place information about it (e.g., starting address, stack locations, save area, etc.) in aa.
3. bind the actual parameters (e1,e2,...,en) to this activation.

4. 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.

5. elaborate the following procedure invocation:

           TASK_START(av,aa);

   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.

Task Completion

When a task activation has completed the elaboration of the task body, the invocation

        TASK_END(ME);

is elaborated. This allows the scheduler to remove the activation from its queues.

EXAMPLES

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.

RULES

Invocation of

        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.

RED RATIONALE 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);

EXAMPLES

1. 360 example