10.   MULTITASKING

The multitasking facilities provide a means for scheduling and synchronizing multiple concurrent elaborations. The basic unit of multitasking is a task, which is defined by a task declaration. A task is invoked using the task invocation statement, which produces an activation of the task. Each activation is "named" by a unique activation variable. Elaboration of task activations is under the control of schedulers which determine when elaboration of each activation can proceed.

Tasks can communicate in two basic ways: by message passing and by the use of shared variables. Message passing works well for distributed systems and contributes to program reliability. Several task activations can communicate via shared memory simply by importing the same variables, or by passing these variables as VAR or READONLY parameters. No automatic mutual exclusion is provided for shared variables; this must be accomplished by the user. The region statement is provided for this purpose.

Clocks and delays are also provided, both for real time and for activation times.

Non-busy multi-way waiting is available to wait for messages and for delays.

There are two levels of multitasking facilities.

1. High-level - These facilities will be used for most applications. Included here is a priority scheduler (via ACT variables), message passing (via MAILBOXes), and mutual exclusion (via DATA_LOCKs). These facilities are described in this chapter.

2. Low-level - These facilities are provided to allow system programmers to define new schedulers and synchronization schemes for applications where the standard high-level facilities are not appropriate. Once defined, these new facilities can be used by application programmers in a manner that is similar to that used for the built-in high-level facilities. Low-level facilities are described in Chapter 14. Included there is a detailed description of the semantics of the create, wait, and region statements. Also included is a discussion of the LATCH data type, the low-level details of the ACT priority scheduler, and of techniques for handling hardware interrupts.

10.1  TASK DECLARATION, TASK CREATION, AND ACTIVATION VARIABLES

C - identifier   2 - body   9 - imports   28 - variable
52 - formal parameters   53 - actual parameters   66 - formal trans time properties   67 - actual trans time properties

A task declaration is similar to a procedure declaration. Tasks, like procedures, are elaborated only when invoked. A task is invoked by a task invocation statement which creates an activation of the task which is elaborated concurrently with the elaboration of its invoker. When a task is invoked, an activation variable is specified as a way of "naming" that activation. All activations are named. For example,

In addition to "naming" the activation, the activation variable determines which scheduler is to control the activation. The type of the activation variable is used in this determination. The ACT type selects the built-in priority scheduler discussed in the next section. Other activation variable types can also be defined for other kinds of user-defined schedulers (see Section 14.5). For example, a task may be scheduled with a user-defined round robin scheduler as follows.

RULES

Task Declaration

Identifier 1 is defined to be a task in the scope in which the task declaration appears. Identifier 2 must be the same as identifier 1.

A task may not have OUT formal parameters.

The lifetime of a task begins at the beginning of elaboration of the scope in which it is declared, and ends at the end of elaboration of the scope in which it is declared.

When an activation is about to leave the scope of a task declaration, it waits for all the activation variables associated with activations of that task to be inactive.

Task Invocation

Elaboration of a task invocation statements consists of

1. elaboration of the actual parameters
2. binding of the actual parameters tot he formal parameters of the named task (see Section 7.3);
3. preparing the activation variable to elaborate the body of the task; and
4. changing the variable from inactive to active. If the variable is not inactive, then the X_CREATE exception is raised.

The lifetime of the activation variable in a task invocation statement must be greater than or equal to the lifetime of the invoked task.

Any actual parameters passed either READONLY or VAR must have a lifetime greater than or equal to that of the invoked task.

RED RATIONALE Care has been taken in RED to ensure that there are no "dangling reference" problems associated with activations. A dangling reference could occur if an activation had access to a variable with a shorter lifetime than its own.

NOTES

     A more detailed description of the semantics of the task invocation statement can be found in Section 14.5.3.

10.2  THE ACT PRIORITY SCHEDULER

C - identifier   2 - body   9 - imports   28 - variable
52 - formal parameters   53 - actual parameters   66 - formal trans time properties   67 - actual trans time properties  

There is a built-in priority scheduler. Elaboration of all task activations whose activation variables have type ACT is controlled by this scheduler. This section discusses the high-level operations for the ACT scheduler. Low-level ACT operations are discussed in Section 14. Techniques for defining other schedulers are discussed in Section 14.5.

ME

The result of the ME function is the activation variable of the activation that invokes ME.

Priorities

Scheduling of task activations whose activation variables have type ACT is determined based on priorities. Each activation has a priority which is an integer with subtype

    INT(0..255)

Priority 0 is the lowest priority (the priority least likely to be scheduled) and priority 255 is the highest priority (the priority most likely to be scheduled). The priority of an activation, av, can be obtained by invoking the function

    PRIORITY (av)

whose result is the priority of av.

The priority of any activation, av, can be set to value n by invoking the procedure

    SET_PRIORITY (av,n);

The initial priority of the main activation of a program is set by the user when the program is to be run. If no priority has been explicitly set, the initial priority of other activations is equal to the current priority of the activating activation.

Exterminate

Elaboration of the procedure invocation

    EXTERMINATE (a);

will cause the X_TERMINATE exception to be raised in the activation currently associated with activation variable a. The invocation has no effect if a is inactive. If a is waiting, then it becomes eligible to run.

Scheduling Algorithm

At any time, there will be some activations which are eligible to run. The ACT scheduling algorithm decides which of the activations are to be run. The language makes no assumptions about the number of activations which can be run concurrently. On some target systems, at most one activation will be running, while on other systems, several activations can be running concurrently.

For the set of activations which are eligible to run, an activation with a higher priority will be scheduled before an activation with a lower priority and, for activations having the same priority, those activations which have been eligible for the longest time will be scheduled over the other activations.

NOTES

     ME, PRIORITY, SET_PRIORITY, and EXTERMINATE are described in detail under the ACT type in Appendix C.10. The scheduling algorithm is described in detail in Section 14.2.

EXAMPLES

1. Setting priorities

   

   
   
   

10.3  MESSAGE PASSING USING MAILBOX VARIABLES

Message passing is done via mailboxes. Activations can send messages to a mailbox, and other activations can then receive these messages from the mailbox. A mailbox ls a variable having a mailbox type. For example,

    VAR m : MAILBOX[ STRING[ASCII](4) ] (3);

Here, m is a mailbox of size 3 capable of holding messages, each having the subtype STRING[A5CII](4). The size specifies that at any time up to 3 messages could have been sent but not yet received.

A mailbox is initially empty (i.e. holds no messages). The SEND procedure is used to send a message to a mailbox. For example,

    SEND(m, "MES1");

sends the message "MES1" to mailbox m. Additional messages can be sent to m by additional sends. For example,

    SEND(m, "MES2");
    SEND(m, "MES3");

The RECEIVE procedure is used to receive a message from a mailbox. For example,

    VAR v : STRING[ASCII] (4);
    RECEIVE(m,v);

will place the next available message from mailbox m into variable v. Messages are stored in a mailbox in order of arrival so that the first message to be received from a mailbox will be the first message sent to the mailbox. In the above example, the value of v after invoking RECEIVE would be "MESI". When a mailbox becomes full, no more messages can be sent. If an attempt is made to send a message to a full mailbox, then the sender will wait until the mailbox is no longer full. If there is more than one activation waiting as a result of attempting to send a message to a full mailbox, these senders are queued in the order in which the sends were done. The first sender will therefore be the first to complete the send. A similar queueing occurs when receives are attempted on an empty mailbox.

Mailboxes_with Size 0

When the size of a mailbox is 0, the sender can never get ahead of the receiver. For example,

    VAR m1 : MAILBOX[ STRING[ASCII](4) ] (0);

In this case, the SEND(m1, "ABCD") will wail unless there is some receive request outstanding. In this latter case, SEND(m1, "ABCD") will send the message "ABCD" directly to the requesting receiver.

RED RATIONALE One style of developing parallel programs is to separate the activations into disjoint groups that share no memory. Since synchronization to share common data is needed only within a group, and not between groups, the resulting program is easier to understand and verify. Furthermore, the partitioning is often natural, especially when the data are distributed on different computers of a network. In such a structure, inter-group communication is accomplished by sending and receiving messages.

RULES

Messages for mailboxes must have an assignable type.

Messages sent to a mailbox and received from that mailbox are handled on a first in (i.e., first sent to the mailbox) first out (i.e., first received from the mailbox) basis. In particular, the i'th receive wlll get the message from the i'th send.

NOTES

     The SEND and RECEIVE operations can also be used as waiting invocations in the wait statement (eee Section 10.5). In a typical program structure, each mailbox represents a service which can have several "server" activations that actually do the work. This structure allows the requester to be ignorant of the actual number of activations providing the service, and their identities.

    More details about the MAILBOX type can be found in Section 14.1.

EXAMPLES

1) Simple producer-consumer

10.4  CLOCKS AND DELAYS

There are two basic kinds of clocks: a single real-time clock and a clock for each activation. The real-time clock measures the elapsed real-time since the program began to run. An activation clock measures the total real-time that a particular activation has been actually running since it was created. All times are positive integers and are measured in ticks. Ticks are an implementation-dependent unit. There are standard integer configuration constants

    MILLISECONDS
    SECONDS
    MINUTES
    HOURS

whose values are the (closest integer to the) number of ticks that occur in each millisecond, second, minute, and hour. The function

    TIME

returns the value of the real-time clock in ticks. The function

    TIME (a)

returns the value of the activation clock for activation a in ticks.

An activation can be delayed for t ticks of real-time by elaborating

    DELAY(t);

An activation can be delayed until the value of the real-time clock is t by elaborating

    DELAY_UNTIL(t);

An activation can be delayed until the value of the activation clock for activation a has the value t by elaborating

    DELAY_UNTIL(t, a);

An activation can be delayed until some activation variable a becomes inactive by elaborating

    DELAY_UNTIL_INACTIVE(a);

NOTES

     The TIME, DELAY, DELAY_UNTIL, and DELAY_UNTIL_INACTIVE procedures are described in Appendix C. The configuration constants MILLISECONDS, SECONDS, MINUTES and HOURS are described in Section 12.1.

EXAMPLES

1. Delayminsec waits for i minutes plus j seconds of real time.

   

   
   
   

2. Measuring the total time in seconds spent in running a procedure p.

   

   
   
   

3. Delayminsec waits for i minutes plus j seconds of real time.

   

   
   
   

4. Reusing an activation variable.

   

   
   
   

10.5  WAITING

2 - body   53 - actual parameters   67 - actual trans time properties  

The wait statement, like a case statement, contains a sequence of when clauses. A wait statement differs in that waiting invocations are specified instead of expressions. A wait statement permits waiting until one of the set of waiting invocations completes and, when it completes, elaborating the body associated with that waiting invocation.

The following waiting invocations are built-in.

The first two are used to send and receive messages from some mailbox (see Section 10.3). The last four are used to cause delays (see Section 10.4). Additional waiting invocations can be defined using the low-level facilities discussed in Section 14.3. Note that arbitrary procedure and function invocations cannot be used as waiting invocations.

RULES

Elaboration of a wait statement consists of examining the waiting invocations following WHEN. If at least one can complete immediately, one of those that can complete is allowed to complete and the associated body is elaborated. lf more than one could complete, only one will be allowed to complete; the one that actually completes is not defined. lf no waiting invocations can complete immediately, the task activation which elaborated the wait statement waits until one can complete.

For SEND's and RECElVE's used as waiting invocations, if none can complete immediately, the activation that elaborates the wait statement is placed on the FIFO waiting queue of each of the specified mailboxes. When one SEND or RECEIVE completes, the activation will be removed from the FIFO queues of the other mailboxes.

If a waiting invocation is SEND (m,v), the mailbox m must have a size which is greater than zero; otherwise, X_EMPTY_MAlLBOX is raised.

RED RATIONALE RED prohibits a send to a zero-length mailbox as a clause in a WAIT statement. This prohibition assures that use of the WAIT statement will not cause cycles of activations waiting to send and receive from zero-length mailboxes. If such cycles occurred, the activations involved would be deadlocked; the cycles could be prevented only by a global scheduling strategy.

NOTES

     Low-level details of the semantics of the wait statement are described in Chapter 14.

EXAMPLES

10.6  SHARED VARIABLES

A variable is said to be shared if two or more activations can use it. Some cases of sharing are considered to be dangerous sharing. Dangerous sharing occurs if two activations simultaneously modify the same shared variable or if one activation modifies a shared variable while some other activation is accessing that shared variable. The translator will issue warning messages for those cases where dangerous sharing might occur.

When dangerous sharing of some shared variable is possible, the user must ensure that the activations that can use that shared variable elaborate these uses in an orderly way. If simultaneous use does occur, the effect (including the state of the variable and any value accessed) is not defined. For a shared variable where the user has ensured orderly access, there is a pragmat available to suppress the warning messages for dangerous sharing of that shared variable (see Appendix B).

NOTES

     Let a1 and a2 be activations that share some variable v in a dangerous way. Orderly access can be ensured by either of the following means:

1. Using the region statement to surround any references to v in a1 and a2 so that only one of the refeences can happen at one time (see next section)
2. Synchronizing a1 and a2 by using messages so that references to v will not happen simultaneously (see example below).

EXAMPLES

10.7  REGION STATEMENT AND DATA LOCK VARIABLES

2 - body   28 - variable

Use of the region statement is one way of ensuring the orderly access to a shared variable by several activations. The region statement is normally used in conjunction with a data lock variable. For example,

    VAR d : DATA_LOCK;

A data lock variable has two possible states: locked and unlocked. Each data lock variable is automatically initialized to have the unlocked state.

Basically, the region statement is elaborated by elaborating its body. However, the region statement ensures that it several activations contain region statements, each specifying the same data lock variable, at most one of these activations will be elaborating the body of its region statement. If two or more activations attempt to elaborate region statements specifying the same data lock variable simultaneously, then all except one will wait (until that one completes elaboration of its region statement). If several activations are waiting for region access based on the same data lock variable, then access will be granted on a first-come first-served basis.

The region statement can also be defined to work for variables with types other than DATA_LOCK (see Section 14.4.1).

RULES

Elaboration of a region statement consists of the following steps:

1. lock the variable, wait if necessary until this can be done;

2. elaborate the body; and

3. unlock the variable.

Once the variable has been locked, it is guaranteed to be unlocked whenever the elaboration of the body completes. The unlocking will happen whether the body terminates normally, raises an exception, or does an exit, goto, or return.

NOTES

Tha DATA_LOCK type is described in Appendix C. Detailed semantics of the region statement and waya for using it with variables other than data lock variables are discussed in Chapter 14.

EXAMPLES

1. Simple mutual exclusion