. navigate
13. Advanced Definitions left arrow
right arrow A. High-Level I/O
Red Reference Manual


Mailboxes     Available Counts     Conditional Message Passing     Mailbox Assignment & Equality     Interrupts
Act Scheduler     Act Variable States     Critical Areas     Scheduling Algorithm
Waiting     Synchronizing Ops     Act Scheduler Ops     Expansion of WAIT
Mutual Exclusion     Region     Data Locks     Latch
User-Defined Schedulers     Act Assignment & Equality     Low & High Ops
Task Activation Creation & Completion     Round Robin Scheduler Example Low-Level I/O


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.


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.


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

    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.


available counts example


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.


conditional message passing example


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.


assignment and equality of mailboxes example


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:

interrupt handling example



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.

states of act variable example

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:

suspended boolean set example


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


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.


This section gives the scheduling rules used by the ACT scheduler.


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.


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.



For each kind of waiting invocation of the form


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.


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

user-defined mailbox example


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.


     Extra invocations of SYNC_SIGNAL will not cause erroneous behavior since the name_TEST functions are again invoked before completion of any waiting invocation.


The wait statement

wait to be expanded example

can be expanded to

expanded wait example

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.




A region statement has the form

region example and is roughly equivalent to

region example

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.


     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.

monitor use example

The two data types needed for monitors, MONITOR_LOCK and MONITOR_QUEUE, together with their operations, are defined as follows:

monitor definition example


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:

  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.


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.


     The only virtue of latches is that they have an inexpensive implementation. In many cases, the waiting can be done as busy waiting.


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


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.



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


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:

high-level USER_ACT example

These all invoke procedures defined for the USER_ACT scheduler. The low-level operations are:

low-level USER_ACT example

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:

aa to ua example

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 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:

equivalent operations example



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

    task procedures example

    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:


    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


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



round robin scheduler example


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.


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.


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


  1. 360 example

    360 example

Mailboxes     Available Counts     Conditional Message Passing     Mailbox Assignment & Equality     Interrupts
Act Scheduler     Act Variable States     Critical Areas     Scheduling Algorithm
Waiting     Synchronizing Ops     Act Scheduler Ops     Expansion of WAIT
Mutual Exclusion     Region     Data Locks     Latch
User-Defined Schedulers     Act Assignment & Equality     Low & High Ops
Task Activation Creation & Completion     Round Robin Scheduler Example Low-Level I/O

13. Advanced Definitions left arrow
right arrow A. High-Level I/O



RED Reference
RED Rationale

Types in RED
Time/Life Computer Languages

Site Index

Overview             Reference ToC             Rationale ToC             Site Index

Home   Favorites   Map

IME logo Copyright © 2009, Mary S. Van Deusen