Previous [TOC] Next

| 10 Processes

This chapter describes the process mechanism implemented by the Mesa architecture. It includes a description of the data types and structures used to support processes, monitor locks, condition variables, and fault queues. It also defines the process instructions, the process queue-management routines, and the scheduling algorithms. The last section on scheduling includes a description of the state-vector allocation performed by the scheduler, as well as a discussion of exceptional conditions that invoke the scheduler (faults, interrupts, and timeouts) and the processing that they receive.

The process facilities are used for controlling the execution of multiple processes and guaranteeing mutual exclusion. The intended application of the process mechanism is the management of access to shared resources (such as the processor). Asynchronous communication with I/O devices is also supported by the process mechanism.

The process implementation is based on queues of small objects called Process State Blocks (`PSB`s), each representing a single process. When a process is not running, its `PSB` records the state associated with the process, including the process' Main Data Space, its evaluation stack (possibly), and the frame (context) it was last executing. Only in the case of a pre-emption is the stack saved in a state vector as part of the process state. In other cases, the stack is known to be empty. `PSB`s also record the process priority and a few flag bits associated with the process (see §10.1.2).

When a process is running, its state is contained in the processor's control registers described in §3.3.1. These registers include all of those that constitute a context (including the evaluation stack), plus the `PSB` and `MDS` registers The `PSB` register points to the process' `PSB`, and the `MDS` register addresses its Main Data Space. These registers are modified when a process switch takes place.

The contents of the `MDS` register is normally modified only by a process switch (it can also be read and written using the register instructions defined in §3.3.4). Several processes can share a single Main Data Space, or an `MDS` can be restricted to contain a single process. As long as the `MDS` register contains a legal value, the processor can execute programs in an environment containing no processes (that is, one in which the content of the `PSB` register and the current `PSB` are undefined). The processor begins execution in this state (Figure 4.7).

Each Process State Block is a member of exactly one process queue. There is one queue for each monitor lock, condition variable, and fault handler in the system. A process that is not suspended on a monitor lock, waiting on a condition variable, or faulted is either running or is on the ready queue, waiting for the processor. The semantics of each monitor and condition queue are assigned by the programmer. Except for the ready queue and the fault queues, there are no fixed assignments of queues to resources.

The primary effect of the process instructions and the scheduler is to move`PSB`s back and forth between the ready queue and a monitor or condition queue. A process moves from the processor to a monitor queue when it attempts to enter a locked monitor. It moves from the monitor queue to the ready queue when the monitor is unlocked (by some other process).

Similarly, a process moves from the processor to a condition queue when it waits on a condition variable, and moves to the ready queue when the condition variable is notified' or when the process has timed out.

Each time a process is requeued, the scheduler is invoked. The scheduler saves the state of the current process in its `PSB` and state vector, chooses the highest-priority runnable process, removes that process from the ready queue' and loads its state into the processor registers. To simplify the scheduler's task, all of the process queues are kept sorted by priority.

Certain exceptional conditions result in process switches rather than traps. These also manipulate the process queues and call the scheduler. Faults (in particular, page faults, write protect faults, frame allocation faults) cause the current process to be placed on a fault queue. The fault's associated condition variable is then notified. An interrupt causes one of the sixteen preassigned condition variables to be notified. Finally, a timeout causes a waiting process to be made ready, even though the condition variable on which it is waiting was not notified by another process.

### 10.1 Data Structures

A global data structure is used to store the Process State Blocks. This section describes that global data structure' called the Process Data Area (`PDA`) as well as the details of Process State Blocks, monitor locks, condition variables and process queue. Details of queue management, however, are postponed until §10.3.

### 10.1.1 Process Data Area

The Process Data Area is located at a fixed address in virtual memory and is 64K-aligned (the value of `mPDA`) is given in Appendix A):

    PDA: LONG POINTER TO ProcessDataArea = LOOPHOLE[mPDA];

The Process Data Area contains all of the process structures except for monitor locks and condition variables, which are allocated by the programmer. The `PDA` has the following structure:

    ProcessDataArea: TYPE = MACHINE DEPENDENT RECORD [
        SELECT OVERLAID * FROM
            header => [
                ready: Queue],
                Count: CARDINAL,
                unused: UNSPECIFIED,
                available: ARRAY [KS) OF UNSPECIFIED,
                state: StateAllocationTable,
                interrupt: InterruptVector,
                fault: FaultVector],
            blocks => [
                block: ARRAY  [0..0) OF ProcessStateBlock],
            ENDCASE];

The `PDA` contains a resident array of Process State Blocks indexed by a `PsbIndex`. The initial elements of the array are allocated to other global state information. The first `PSB` is at index `StartPsb`, after the `PDA` header. A zero index is used to denote the null process.

    PsbNull: PsbIndex = O;
    PsbIndex: TYPE = [0..1024);
    StartPsb: PsbIndex = (SIZE[ProcessDataArea]
        + SIZE[ProcessStateBlock] - 1)/SIZE[ProcessStateBlock];

The index of the currently running process is maintained in a processor register, also accessible to the programmer, which is

    PSB: PsbIndex;

The header of the Process Data Area includes the ready queue and a count of the number of `PSB`s (not including overhead) in the `PDA`. There is also a small block available to the programmer, a table of pointers to state vectors used to save the context and stack of pre empted processes (§10.4.2), an array of condition variables assigned to interrupt levels (§10.4.4), and a structure used to represent fault queues and their associated condition variables (§10.4.3). The `PSB`s and state vectors follow the header.

Design Note: The count field is used only to determine the number of processes involved in the timeout scan (§10.4.5). Additional `PSB`s may be allocated by the programmer.

A `PSB` is active if it is running or is on a process queue; only active `PSB`s may be referenced by the process instructions.

Programming Note: The programmer typically allocates a fixed number of `PSB`s, stores this number in the header as the count, and makes the `PSB`s active (by placing them on the ready queue) as processes are created. Because the timeout scan examines all the `PSB`s indicated by the count field, the timeout value associated with each inactive process must be set to zero (§10.4.5).

All of the pointers contained in the Process Data Area (and in the State Allocation Table) are relative to the starting location of the `PDA` (just as short pointers are relative to the origin of an `MDS`). Like Main Data Spaces, the `PDA` is aligned on a 64K boundary.

    LengthenPdaPtr: PROCEDURE[ptr: POINTER] RETURNS[LONG POINTER] =
        BEGIN
        Offset: CARDINAL = LOOPHOLE[ptr];
        RETURN[PDA + LONG[OffSet]];
        END;

    OffsetPda: PROCEDURE[ptr: LONG POINTER] RETURNS [POINTER] =
        BEGIN
        IF HighHalf[ptr - PDA] # 0 THEN ERROR;
        RETURN[LowHalf[ptr - PDA]];
        END;

    FetchPda: PROCEDURE[ptr: POINTER] RETURNS [LONG POINTER] =
        BEGIN
        RETURN[Fetch[LengthenPdaPtr[ptr]]];
        END;

    StorePda: PROCEDURE[ptr: POINTER] RETURNS [LONG POINTER] =
        BEGIN
        RETURN[Store[LengthenPdaPtr[ptr]];
        END;

Implementation Note: Because the `PDA` is 64K word aligned and its relative pointers are restricted to a 64K range, a concatenation operation can replace the addition that appears above, and an extraction of the low-order word can replace the subtraction.

It is often convenient to reference `PSB`s using `PDA` relative pointers rather than indexes. The following routines convert between the two representations:

    PsbHandle: TYPE = POINTER TO ProcessStateBlock;

    Handle: PROCEDURE[index: PsbIndex] RETURNS[PsbHandle] =
        BEGIN
        RETURN[LOOPHOLE[index * SIZE[ProcessStateBlock]]];
        END;

    Index: PROCEDURE[handle: PsbHandle] RETURNS[PsbIndex] =
        BEGIN
        RETURN[LOOPHOLE[handle] / SIZE[ProcessStateBlock]];
        END;

Design Note: All of the process data structures containing a PsbIndex are laid out so that the low-order bit of the index lies at bit twelve of a word. Because `PSB`s are eight-word aligned, this allows the conversion from index to handle to be performed by masking out the low-order three and the high-order three bits of the word containing the index. Thus, the 10-bit index is extracted from a 16-bit word and converted into a PDA-relative pointer.

Implementation Note: Because the Process Data Area and the tables pointed to by it are resident, the processor need not maintain the dirty and referenced map flags of the pages containing these structures (§3.1.1).

### 10.1.2 Process State Blocks

A `PSB` records the state of a process, and it therefore contains the following fields:

- A link word, used for maintaining the queue structure. This word also contains the process' priority and some flag bits.
- A flag word containing fields used primarily by the programmer. This word also includes a single flag bit and a cleanup link used for maintaining the queue structure.
- A process context representation, which is either a pointer to the frame the process was last executing, or a pointer to a state vector containing the evaluation stack and the frame pointer.
- The timeout value associated with each process (see §10.4.3. The high-order sixteen bits of the (64K-aligned) address of the Main Data Space in which the process is running.
- Two words of sticky flags for floating-point operations.

Process State Blocks are therefore eight words long, and are always eight-word aligned.

    ProcessStateBlock: TYPE = MACHINE DEPENDENT RECORD [
        link(0): PsbLink,
        flags(1): PsbFlags,
        Context(2): POINTER,
        timout(3): Ticks,
        mds(4): CARDINAL,
        available(5): UNSPECIFIED,
        sticky(6): LONG UNSPECIFIED];

The link word, in addition to the process' priority and a queue link, contains three flag bits:

- failed indicates that the last instruction executed by the process was an unsuccessful (Monitor Entry (§10.2.1) or Monitor Reentry (§10.2.4);
- permanent indicates that the `PSB`'s context is a state vector that is permanently assigned to the process;
- preempted records whether the `PSB` was pre-empted. If it was pre-empted, the saved context includes the evaluation stack and the frame pointer, otherwise it contains only the frame pointer.

    Priority: TYPE = [0..7];
    PsbLink: TYPE = MACHINE DEPENDENT RECORD [
        priority(0: O..2): Priority,
        next(0: 3..12): PsbIndex,
        failed(0: 13.13): BOOLEAN,
        permanent(0:14..14): BOOLEAN,
        preempted(0: 1 15..15): BOOLEAN];

The flag word in addition to a cleanup link and several fields available to the programmer, contains flags that indicate whether the process is waiting on a condition queue and also whether there is an abort pending for the process. If the latter flag is set (by the programmer), the Monitor Reentry instruction causes a trap (§10.2.4).

    Psbflags: TYPE = MACHINE DEPENDENT RECORD [
        available(0: 0..2): (0..7),
        cleanup(0: 3..12): PsbIndex,
        reserved(0: 13..13): BOOLEAN,
        waiting(0: 14..14): BOOLEAN,
        abort(0: 15..15): BOOLEAN];

Design Note: Process State Blocks must be resident in real memory, and may not be write-protected. No reference to a `PSB` may cause a fault.

### 10.1.3 Monitor Locks

Unlike Process State Blocks, monitor locks are allocated by the programmer. They serve as queue headers, and therefore contain a PsbIndex pointing into the body of the queue (the queue structure is defined in §10.1.5). A monitor queue contains all of the processes suspended on the monitor lock.

In addition to the queue pointer, a monitor lock includes a lock bit; when set, the lock bit indicates that some process is executing inside the monitor. If another process attempts to enter the monitor while the lock is set, that process is suspended by placing it on the monitor queue.

    Monitor: TYPE = MACHINE DEPENDENT RECORD [
        reserved(0: O..2): [0..7)  0,
        tail(0: 3..12): PsbIndex,
        available(0: 13..14): [0..3),
        locked(0: 15..15): BOOLEAN];

Design Note: Monitor locks need not be resident (although some may be).

### 10.1.4 Condition Variables

Condition variables are also allocated by the programmer. Like monitor locks, they serve as queue headers, and contain a PsbIndex pointing into the body of the queue. A condition queue contains all of the processes waiting on the condition.

In addition to the queue pointer, a condition variable contains two flag bits:

- abortable is set (by the programmer) if processes waiting on the condition can be aborted (§10.2.4);
- wakeup is set in response to a fault (§10.4.3) or an interrupt (§10.4.4).

    Condition: TYPE = MACHINE DEPENDENT RECORD [
        reserved(0: 0..2): [0..7]  0,
        tail(0: 3..12): PsbIndex,
        available(0: 12..13): BIT,
        abortable(8: 14.14): BOOLEAN,
        wakeup(0: 15.15): BOOLEAN];

Design Note: Except for those contained in the `PDA`, condition variables need not be resident.

### 10.1.5 Process Queues

A queue is represented by a long pointer to a queue header, declared as type Queue. A queue header is either a monitor lock, a condition variable, a fault queue, or the ready field of the Process Data Area. The header contains a field called tail, which is the index of the last `PSB` on the queue (queue entries are always Process State Blocks).

    QueueHandle: TYPE = LONG POINTER TO Queue;
    Queue: TYPE = MACHINE DEPENDENT RECORD [
        reserved1(0: 0..2): [0..7]  0,
        tail(0: 3..12): PsbIndex,
        reserved2(0: 13..15): [0..7]];

Design Note: The formats of monitor locks and condition variables are carefully designed to match the structure of a Queue, so that they can function as queue headers. When functioning as queue headers, they define additional flags in the reserved2 field.

The last entry on the queue is chained to the first through its link field, which is also a `PSB` index, and each entry is chained to the next using its link field. If the queue contains one entry, the header points to it, and it is linked to itself. An empty queue is represented by a null index in the queue header. An overall diagram showing a hypothetical arrangement of `PSB`'s in the various queues is contained in Figure 1O.

### 10.2 Process Instructions

The process instructions are used to enter and exit monitors, to wait on condition variables and subsequently to re-enter the monitor. They are also used to notify and broadcast condition variables. Two primitives for manipulating the process queues are also available. The process instructions are all stack0 (§3.3.2); that is, their operands always begin at the bottom of the stack. This minimizes the cases in which a State Vector is needed to save the stack of a process (§10.4.2).

### 10.2.1 Monitor Entry

The Monitor Entry instruction is executed near the beginning of each monitor entry procedure. It either sets the monitor lock, or if the monitor is already locked, causes the current process to be suspended by placing it on the monitor queue.

#### ME Monitor Entry

    ME: PROCEDURE =
        BEGIN
        m: LONG POINTER TO Monitor = PopLong[];
        mon: Monitor;
        MinimalStack[];
        mon  Fetch[m];
        IF ~mon.locked THEN
            BEGIN
            mon.locked  TRUE;
            Store[m]  mon;
            Push[TRUE];
            END
        ELSE
            EnterFailed[m];
        END;

Figure 10.1 Process Queue Structures

If the monitor was entered successfully, Monitor Entry returns `TRUE` on the stack, which is tested by a Jump Zero Byte instruction immediately following the `ME`.

If monitor entry was not successful, the `PSB`'s failed bit is set, and the current process is moved to the monitor queue. The scheduler is then invoked (§10.4.1).

    EnterFailed: PROCEDURE [m: LONG POINTER TO Monitor] =
        BEGIN
        link: PsbLink  Fetch[@PDA.block[m].link];
        link.failed  TRUE;
        Store[@PDA.block[PSB].link]  link;
        Requeue[src: @PDA.ready, dst: m, psb: PSB];
        Reschedule[];
        END;

When the process later becomes ready, Reschedule notices that its failed bit had been set, and places `FALSE` onto the evaluation stack. `FALSE` causes the Jump Zero instruction following the `ME` to loop back to the instructions to acquire the monitor lock. This allows for a situation in which some other process has locked the monitor between the time a suspended process is made ready and the time it executes the Monitor Entry. This same technique is used by the Monitor Reentry instruction (§10.2.4), which also calls EnterFailed.

### 10.2.2 Monitor Exit

The Monitor Exit instruction is executed at the end of each monitor entry procedure. It unlocks the monitor and causes the highest priority process suspended on the monitor queue (if any) to be made ready.

#### MX Monitor Exit

    MX: PROCEDURE =
        BEGIN
        m: LONG POINTER TO Monitor = PopLong[];
        MinimalStack[];
        IF Exit[m] THEN Reschedule[];
        END;

The Exit routine clears the monitor lock and checks the contents of the monitor queue. If the queue is not empty, the first process on the queue is made ready. The Exit routine is also used by the Monitor Wait instruction (§10.2.3).

    Exit: PROCEDURE [m: LONG POINTER TO Monitor]
        RETURNS [requeue: BOOLEAN] =
        BEGIN
        mon: Monitor  Fetch[m] ;
        IF mon.locked = FALSE THEN ERROR;
        monlocked  FALSE;
        Store[m]  mon;
        IF requeue  (mon.tail # PsbNull) THEN
            BEGIN
            link: PsbLink = Fetch[@PDA.block[mon.tail].link];
            Requeue[src: m, dst: @PDA.ready, psb: link.next];
            END;
        END;

Programming Note:The programmer should ensure that a Monitor Exit instruction is executed only when the monitor is locked.

### 10.2.3 Monitor Wait

The Monitor Wait instruction is executed within a monitor to wait on a condition variable. It is always followed (statically) by a monitor re-entry sequence, which computes the monitor and condition pointers and executes a Monitor Reentry instruction (§10.2.4). Monitor Wait first unlocks the monitor, as in Monitor Exit. It then moves the current process onto the condition queue (also setting its waiting bit and timeout value) and calls the scheduler.

#### MW Monitor Wait

    MW: PROCEDURE =
        BEGIN
        t: Ticks = Pop[];
        c: LONG POINTER TO Condition = PopLong[];
        m: LONG POINTER TO Monitor = PopLong[];
        flags: Psbflags;
        cond: Condition;
        requeue: BOOLEAN;
        MinimalStack[];
        CleanupCondition[c];
        requeue  Exit[m];
        flags  Fetch[@PDA.block[Psb].flags];
        cond  Fetch[c];
        IF ~flags.aborted ~cond.abortable THEN
            BEGIN
            IF cond.wakeup THEN
                BEGIN
                cond.wakeup  FALSE;
                Store[c]  cond;
                END
            ELSE
                BEGIN
                Store[@PDA.block[PSB].timeout] + IF t = O THEN O
                    ELSE MAX[l, LowHalf[LONG[PTC[ 9 LONG[t]]];
                flags.waiting  TRUE;
                Store[@PDA.block[Psb].flags]  flags;
                Requeue[src: @Penready, dst: c, psb: ass];
                requeue  TRUE;
                END;
            END;
        IF requeue THEN Reschedule[];
        END;

There are two conditions under which the process executing the wait is not moved to the condition queue, but instead remains on the ready list: when the `PSB` of the process indicates that there is an abort pending, or when the condition variable indicates that there is a wakeup waiting (§10.4.4.2). Monitor Wait also sets the timeout value of the process to the current value of the process timeout counter plus the time interval supplied on the stack. A value of zero indicates that the process should not be timed out while waiting. Timeout processing is described more completely in §10.4.5; CleanupCondition is defined in §10.3.2.

### 10.2.4 Monitor Reentry

Monitor Reentry is used to re-enter a monitor after a wait. If the monitor is locked, the process will be placed on the monitor queue as in the Monitor Entry instruction. Reentry differs from entry because Monitor Reentry will clean up the condition variable and clear the `PSB`'s cleanup link.

#### MR Monitor Reentry

    MR: PROCEDURE =
        BEGIN
        c: LONG POINTER TO Condition = PopLong[];
        m: LONG POINTER TO Monitor = PopLong[];
        mon: Monitor;
        MinimalStack[];
        mon  Fetch[m];
        IF -mon.locked THEN
            BEGIN
            flags: PsbFlags;
            CleanupCondition[c];
            flags  Fetch[@PDA.block[psb].flags];
            flags.cleanup  PsbNull;
            Store[@PDA.block[Psb].flags]  flags;
            IF flags.abort THEN
                BEGIN
                cond: Condition = Fetch[c};
                IF cond.abortable THEN ProcessTrap[];
                END;
            mon.locked  TRUE;
            Store[m]  mon;
            Push[TRUE];
        END
        ELSE Enterfailed[m];
    END;

Monitor Reentry, like Monitor Entry, is always followed by a Jump Zero Byte instruction. Jump Zero Byte loops back to the instructions to acquire the monitor lock. This loop allows for a situation in which some other process still holds or has just locked the monitor between the time the notify (or timeout) signal causes the process to be made ready and the time it executes the Monitor Reentry. If the monitor is not locked, Monitor Reentry checks for a pending abort. If the condition variable allows aborts, a process trap is generated, so the monitor is not entered. Trap processing is described in detail in §9.5.

Programming Note: If the process trap handler intends to resume the trapped context, it must ensure that the monitor lock is acquired. This preserves the invariant that the lock is held when control is (textually) inside the monitor.

Programming Note: Between a Monitor Wait and the subsequent Monitor Reentry, a process must not execute another Monitor Wait. In particular, the program used to compute and load the monitor and condition pointers and the associated timeout interval onto the stack (and any trap routines invoked by this program) must not wait. See the programming note in §10.3.2.

### 10.2.3 Notify and Broadcast

The Notify Condition and Broadcast Condition instructions are used to wake up processes waiting on condition variables. A notify moves the first entry on a condition queue to the ready queue. A broadcast makes all entries on the queue ready.

#### NC Notify Condition

    NC: PROCEDURE =
        BEGIN
        c: LONG POINTER TO Condition = Popbong[];
        cond: Condition;  MinimalStack[];
        CleanupCondition[c];
        cond  Fetch[c];
        IF cond.tail # PsbNull THEN
            BEGIN
            WakeHead[c];
            Reschedule[];
            END;
        END;

If the condition queue is empty, a notify has no effect except to clean up the queue (§10.3.2).

#### BC Broadcast Condition

    BC: PROCEDURE =
        BEGIN
        c: LONG POINTER TO Condition = PopLong[];
        requeue: BOOLEAN;
        MinimalStack[];
        CleanupCondition[c];
        FOR cond: Condition  Fetch[c], cond  Fetch[c]
            WHILE con.dtail # PsbNull DO
            WakeHead[c];
            requeue  TRUE;
            ENDLOOP;
        IF requeue THEN Reschedule[];
        END;

The preceeding routine performs the equivalent of a Notify on each process on the condition queue. WakeHead is used to remove the head of the queue each time around the loop. If the condition queue is empty, a broadcast has no effect except to cleanup the queue (§10.3.2).

The following routine is used by the instructions Notify and Broadcast, and by the routine NotifyWakeup (§10.4.4.2). It moves the first `PSB` from a condition queue to the ready queue and clears the waiting flag.

    WakeHead: PROCEDURE [c: LONG POINTER TO Condition] =
        BEGIN
        cond: Condition = Fetch[c];
        link: Psbtink = Fetch[@PDA.block[cond.tail].link];
        flags: PsbFlags  Fetch[@PDA.block[link.next].flags];
        flags.waiting  FALSE;
        Store[@PDA.block[link.next].flags]  + flags;
        Store[@PDA.block[link.next].timeout] +O;
        Requeue[src: c, dst: @PDA.ready, psb: link.next];
        END;

WakeHead also clears the timeout value of the process, so that it will not be timed out while running. Timeouts are discussed in §10.4.5.

### 10.2.6 Requeue

The Requeue instruction gives programmers access to the process mechanism's queue handling primitives. It removes a process from the source queue and inserts it (according to priority) into the destination queue, unconditionally invoking the scheduler.

#### REQ Requeue

    REQ: PROCEDURE =
        BEGIN
        psb: PsbHandle = Pop[];
        dstque: QueueHandle = PopLong[];
        srcque: QueueHandle = PopLong[];
        MinimalStack[];
        Requeue[src: srcque, dst: dstque, psb: Index[psb]];
        Reschedule[];
        END;

Note that the Requeue instruction takes a PsbHandle, not an index.

Programming Note: In Requeue, the programmer should ensure that the psb is on the source queue (or that the source queue is zero).

### 10.2.7 Set Process Priority

The Set Process Priority instruction allows the programmer to change the priority of the current process.

#### SPP Set Process Priority

    SPP: PROCEDURE =
        BEGIN
        priority: Priority = Pop[];
        link: PsbLink;  MinimalStack[];
        link  Fetch[@PDA.block[PSB].link];
        link.priority  priority;
        Store[@PDA.block[PSB].link]  link;
        Requeue[src: @PDA.ready, dst: @PDA.ready, psb: PSB];
        Reschedule[];
        END;

### 10.3 Queue Management

This section defines the small number of primitives used to maintain the process queues. In particular, operations are defined to remove a `PSB` from a queue (Dequeue) and to insert a `PSB` into a queue in priority order (Enqueue). Section 10.3.2 discusses cleanup links.

### 10.3.1 Queuing Procedures

The routine is used to maintain the process queue structures. It removes the process indexed by psb from the source queue src and inserts it into a destination queue dst according to its priority. Requeue is implemented using the two more primitive operations, Dequeue and Enqueue.

    Requeue: PROCEDURE [src, dst: LONG POINTER, psb: PsbIndex] =
        BEGIN
        IF psb = PsbNull THEN ERROR;
        Dequeue[src, psb];
        Enqueue[dst, psb];
        END;

First, Dequeue is invoked to remove the psb from the source queue. Requeue traverses src looking for the process immediately preceeding psb (called prev), so that the psb can be removed from the queue.

Dequeue then updates the queue header, if it points to the `psb` being removed. The algorithm is complicated by the fact that the location of the queue header (condition variable) of the source queue may not be known (`src` = 0). This condition occurs when a waiting process is timed out (§10.4.5) and can possibly occur when the programmer executes a `Requeue` instruction In this latter case, the `psb's` cleanup link is set to the original value of its link field, pointing back to the source queue from which it will later be removed by CleanupCondition (described at the end of this section).

    Dequeue: PROCEDURE [src: LONG POINTER, psb: PsbIndex] =
        BEGIN
        link: Psblink;
        prev: PsbIndex;
        queue: Queue;
        que: QueueHandle = src;
        IF que # LOOPHOLE[0] THEN queue  Fetch[que];
        link  Fetch[@fw.block[psb].link];
        IF link.next = psb THEN  prev c PsbNull
        ELSE
            BEGIN
            temp: PsbLink;
            prev  IF que = LOOPHOLE[0] THEN psb ELSE queue-tail;
            DO temp  Fetch[@PDA.block[prev].link];
                IF temp.next = psb THEN EXIT;
                prev  temp.next;
                ENDLOOP;
            temp.next  link.next;
            Store[@PDA.block[prev].link]  temp;
            END;
        IF que = LOOPHOLE[0] THEN
            BEGIN
            flags: PsbFlags  Fetch[@PDA.block[psb].flags];
            flags.cleanup  link.next;
            Store[@PDA.block[psb].flags]  flags;
            END
        ELSE IF queue.tail = psb THEN
            BEGIN
            queue.tail  prev;
            Store[que]  queue;
            END;
        END;

Enqueue inserts the `psb` into the destination queue `dst` in priority order. First, it checks for the simple case, when dst is empty. Second, Enqueue tries to add `psb` to the end of `dst` if its priority is less-than or equal to the priority of the last entry in the queue. Failing that, it searches the destination queue and eventually inserts the `psb` after all other processes of equal or higher priority, just before the first process of lower priority.

    Enqueue: PROCEDURE [dst: LONG POINTER, psb: PsbIndex] =
        BEGIN
        que: QueueHandle = dst;
        queue: Queue  Fetch[que];
        Psblink  Fetch[@PDA.block[psb].link];
        IF queue.tail = PsbNull THEN
            BEGIN
            link.next  psb;
            Store[@PDA.block[psb].link]  link;
            queue.tail  psb; Store[que]  *queue;
            END
        ELSE
            BEGIN
            currentlink, nextlink: PsbLink;
            prev: PsbIndex  queue.tail;
            currentlink  Fetch[@mA.block[prev].link];
            IF currentlink.priority > = link.priority THEN
                BEGIN
                queue.tail  psb;  Store[que]  queue;
                END
            ELSE
                DO nextlink  Fetch[@mA.block[currentlink.next].link];
                    IF link.priority > nextlink.priority THEN EXIT;
                    prev  currentlink.next;
                    currentlink  nextlink;
                    ENDLOOP;
            link.next  currentlink.next;
            Store[@PDA.block[psb].link]  link;
            currentlink.next  psb;
            Store[@PDA.block[prev].link]  currentlink;
            END;
        END;

### 10.3.2 Cleanup Links

The CleanupCondition routine must be invoked before accessing a condition queue, since its queue pointer may not be correct. Inaccuracy occurs when the tail of a condition queue (pointed to by the header) is removed from the queue by a timeout: the location of the header is unknown in that case, so the pointer cannot be properly updated. (This situation may also occur when using the Requeue instruction.) Fortunately, in addition to the link described above, each `PSB` also contains a second queue link, called the cleanup link, which is used to maintain the queue structures when the location of the queue header is not known.

When Dequeue detects this situation (the source queue is zero), it sets the `PSB's` cleanup link to the old value of its link field, which points to the next `PSB` on the queue. CleanupCondition finds the correct head of the condition queue by following the cleanup link into the queue from which the `PSB` was removed. From there, it locates the tail to which the condition variable should point. Notice, however, that the cleanup link might point to a `PSB` that also has its cleanup link set because it was also removed from the queue by a timeout. CleanupCondition therefore follows the cleanup links until there are no more, declares the resulting `PSB` to be the head of the queue, and then follows the normal queue links until the tail is found.

    CleanupCondition: PROCEDURE [c: LONG POINTER TO Condition] =
        BEGIN
        link: PsbLink;
        flags: PsbFlags;
        psb, head: PsbIndex;
        cond: Condition  Fetch[c];
        IF (psb  cond.tail) # PsbNull THEN
            BEGIN
            flags  Fetch[@PDA.block[psb].ftaZas];
            IF flagscleanup # PsbNull THEN
                BEGIN
                DO
                    IF flags.cleanup = psb THEN
                        BEGIN
                        cond.wakeup  FALSE;
                        cond.tail  PsbNull;
                        Store[c]  cond;
                        RETURN;
                        END;
                    psb  flags.cleanup;
                    flags  Fetch[@PDA.block[psb].flags];
                    IF flags.cleanup = PsbNull THEN EXIT;
                    ENDLOOP;
                head  psb;
                DO
                    link  Fetch[@mA.block[psb].link];
                    IF link.next = head THEN EXIT;
                    psb  link.next;
                    ENDLOOP;
                cond.tail  psb;  Store[c]  cond;
                END;
            END;
        END;

Note that CleanupCondition itself updates only the condition variable; the cleanup links in the `PSB`s removed from the condition queue are reset by the Monitor Reentry instruction (§10.2.4).

Programming Note:Between a Monitor Wait and the subsequent Monitor Reentry, a process must not execute another Monitor Wait; in particular, the program used to compute and load the monitor and condition pointers and the timeout interval onto the stack (and any trap routines invoked by that program) must not wait. If the first wait times out, the `PSB`'s cleanup link will be set, Any subsequent wait would destroy the original cleanup link. Also, any fault that occurs between a Monitor Wait and the subsequent Monitor Reentry will result in the process being requeued, first, to a fault service queue and, later, to the Ready Queue again For example, a page fault on the code page is possible. The first of these requeues is carried out without calling CleanUpCondition, and the second must also avoid CleanUpCondition, or the cleanup link will be smashed. For this reason, the process must removed from the fault service queue to the Ready Queue by means of the `FEQ` opcode; Notify Condition and Broadcast Condition must not be used.

Design Note: CleanupCondition is an idempotent operation; that is, cleaning up a condition variable that is already clean has no effect. It is therefore permissible for an instruction to clean up a condition variable before checking for other possible traps or faults.

Design Note: Because only processes waiting on condition variables can be timed out, there is no need for a corresponding routine to clean up monitor locks.

### 10.4 Scheduling

The scheduler implements overall changes in the machine state called process switch. Process switches result when the current process yields control of the processor and a higher-priority process is ready, or when the current process is removed from the ready queue, either by its own commission or by a pre-emption. The current process may stop running as a result of performing any of the following actions:

- attempting to enter a monitor,
- exiting a monitor,
- waiting on a condition variable,
- attempting to reenter a monitor, or
- executing a REQ or SPP instruction.

In addition, any of the following pre-emptions may cause the current process to stop running:

- a fault, which notifies a fault handler (§10.4.3),
- an interrupt, which notifies a condition variable (§10.4.4), or
- a timeout, which makes a waiting process ready ($10.4.5).

All of these conditions result in a possible process switch by calling the scheduler (Reschedule) described in the next section. In all cases, process switches take place between instructions. Either the current instruction is completed, or the state of the processor at the beginning of the current instruction is restored. See §4.6.1 for a precise statement of the restart rule.

### 10.4.1 Scheduler

The scheduler is invoked whenever a process has moved to or from the ready queue. In particular, Reschedule is called by the process instructions that call Requeue and by the Fault, Interrupt, and TimeoutScan routines (described in later sections).

Reschedule finds the highest priority runnable process in the ready queue, saves the state of the current process (if any), and loads the state of the new process into the processor registers. In the case that no runnable process exits, the scheduler sets running to false, This action causes the main loop (§10.4.2.2).

    Reschedule: PROCEDURE [preemption: BOOLEAN  FALSE] =
        BEGIN
        link: PsbLink;
        psb: PsbIndex;
        queue: Queue;
        IF running THEN SaveProcess[preemption];
        queue  Fetch[@PDA.ready];
        IF queue.tail = PsbNull THEN GO TO BusyWait;
        link  Fetch[@PDA.block[queue.tail].link];
        DO
            psb  link.next; link  Fetch[@PDA.block[psb].link];
            IF link.permanent
                OR link.preempted
                OR EmptyState[link.priority] THEN EXIT;
            IF psb = queue.tail THEN GO TO BusyWait;
            ENDLOOP;
        PSB  psb;
        PC  savedpc  0;
        LF  LoadProcess[];
        running  TRUE;
        XFER[dst: LONG[LF], src: 0, type: processSwitch];
        EXITS
        BusyWait =>
            BEGIN
            IF InterruptsEnabled[] THEN RescheduleError[];
            running  FALSE;
            END;
        END;

Design Note: It is an invariant of the design that `PDA.state[PDA.block[PSB].link.priority] # 0 OR link.permanent`. That is, a state vector must be available in case the current process is preempted (see §10.4.2).

After saving the state of the current process (if any), Reschedule clears the `PC` register (and resets savedpc) to indicate that a process switch is in progress. This is necessary in case the subsequent `XFER` causes a trap or fault, which normally saves the `PC` in the current rame. This must be avoided if the frame is mapped out or the `PC` has not yet been loaded (because of a fault on the global frame, for example).

Implementation Note: Any invalid value of the `PC` can be used in the implementation as indicated by the following routine, which returns `FALSE` if a process switch is in progress. Eight is the minimum size of a code segment entry vector.

    ValidContext: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        RETURN[PC >= SIZE[CodeSegment] * 2];
        END;

If no runnable process can be found on the ready queue, Reschedule sets running to `FALSE`, causing the instruction interpreter (§10.4.4) or a timeout (§10.4.5). When in this state, interrupts must be enabled; otherwise, a trap occurs in the context of the last running process (§9.5).

Programming Note: A RescheduleError is fatal. If the trap handler attempts to resume normal process switching, the results are undefined. This condition is reported by the processor for debugging purposes only.

### 10.4.2 Process State

A process' state is saved in its `PSB` and perhaps also in one of a number of state vectors allocated to the process' priority level. A state vector preserves the process' stack and local frame pointer, and also has room for a fault parameter (the format is defined in $9.5.3), The process state saving and restoring routines and a description of the algorithms for state vector allocation and deallocation are included in this section.

### 10.4.2.1 Saving and Loading Process State

The SaveProcess and LoadProcess routines are used by the scheduler to save the state of a running process and to reload the state of a ready process The SaveStack and LoadStack routines are defined in §9.5.3.

The stack is empty when a process is moved to or from the ready queue by the process instruction For that reason a state vector is needed only in the case of a pre-emption caused by a fault, an interrupt, or a timeout. The state vector is obtained using the AllocState routine described in the next section. Otherwise, the state of the process is contained entirely within the `PSB`.

    SaveProcess: PROCEDURE [preemption: BOOLEAN] =
        BEGIN ENABLE Abort => ERROR;
        link: PsbLink  Fetch[@PDA.block[psb].link];
        IF ValidContext[] THEN StoreMds[@LocalBase[LF].pc]  PC;
        IF link.preempted  preemption THEN
            BEGIN
            state: StateHandle;
            IF link.permanent THEN state  AlIocState[link.priority]
            ELSE state  LengthenPdaPtr[Fetch[@PDA[block[psb].context]];
            SaveStack[state];
            Store[@state.frame]  LF;
            IF link.permanent THEN Store[@PDA.block[PSB].context]  OffsetPdajstate];
            END
        ELSE
            IF link.permanent THEN Store[@PDA.biock[PSB].context]  LF
            ELSE
                BEGIN
                state: StateHandle  LengthenPdaPtr[Fetch[@PDA.talsgk[PSB]context]];
                Store[@state.frame]  LF;
                END;
         Storef@PDA.biock[PSB].iink]  link;
         END;

Design Note: The `ENABLE` for Abort indicates that SaveProcess (and AllocState and SaveStack) can not generate page faults (or write-protect faults). The state vector must be resident because the fault parameter is saved in it. (see §10.4.3).

SaveProcess must check that the context is valid before saving the `PC` in the current local frame. This check covers the case of a trap or fault during a process switch that has not yet obtained a valid context. SaveStack handles the correct setting of `savedSP` as well as the stack pointer, `SP`.

Programming Note: Saving the process state does not update the mds field of the `PSB`. the program modifies the `MDS` register, it should also update the current `PSB` (if that is the effect desired).

The LoadProcess routine reverses the actions of SaveProcess, freeing the state vector if one was allocated. Note that LoadStack sets `savedSP` as well as `SP` to the value obtained from the state vector.

    LoadProcess: PROCEDURE RETURNS [frame: LocalFrameHandle] =
        BEGIN ENABLE Abort => ERROR;
        mds: CARDINAL;
        link: PsbLink  Fetch[@PDA.biock[PSB].link];
        frame  Fetch[@PDA.block[fw].context];
        IF link.preempted THEN
            BEGIN
            state: StateHandle  LengthenPdaPtr[frame];
            LoadStack[state];
            frame  Fetch[@state.frame];
            IF -tintrr~~rr;mu~~~~.priyris~a~e~;
            END
        ELSE
            BEGIN
            IF link.failed THEN
                BEGIN
                Push[FALSE];
                link.failed  FALSE;
                Store[@PDA.block[PAB].link]  link;
                END;
            IF link.permanent THEN
                BEGIN
                state: StateHandle  LengthenPdaPtr[frame];
                frame  Fetch[@state.frame];
                END;
            END;
        mds  Fetch[@PDA.biock[rw].mds];
        MDS  LongShift[LONG[mds], WordSize];
        END;

Design Note: The `ENABLE` for Abort indicates that B>LoadProcess (and LoadStack and FreeState) can not generate page faults (or write-protect faults); until the LoadProcess has completed, the state vector is unavailable for reuse by a subsequent fault. LoadProcess checks for the presence of the `failed` bit set by the Monitor Entry and Monitor Reentry instructions. In this case, it pushes `FALSE` nto the stack so that the following Jump Zero Byte instruction will loop back to the monitor entry sequence (see §10.2.1).

Implementation Note: In the case of a fault (see §10.4.3), some implementations of the processor may save additional processor state in the state vector for use by a subsequent load, however, except for the size of the state vector required (which must be constant for all processes), the presence of this additional information must be invisible to the programmer.

### 10.4.2.2 State Vector Allocation

State vectors are allocated much like frames, using an array of pointers to lists of free state vectors called the State Allocation Table (SAT). A separate list is provided for each priority level, but unlike frame allocation, there is no provision for indirect lists. All pointers in the SAT are relative to the base of the Process Data Area.

    StateAllocationTable: TYPE = ARRAY Priority OF POINTER TO StateVector;

The scheduler uses the following routine to ensure that a state vector is available at the correct priority level before running a process:

    EmptyState: PROCEDURE [pri: Priority] RETURNS [BOOLEAN] =
        BEGIN
        state: POINTER TO StateVector = Fetch[@PDA.state[pri]];
        RETURN[State = LOOPHOLE[0]];
        END;

The allocation routine simply returns the element of the array indexed by the requested priority, updating the array to point to the next item on the list. FreeState returns the state vector to the head of the list in the obvious way.

    AllocState: PROCEDURE [pri: Priority] RETURNS [state: StateHandle] =
        BEGIN
        Offset: POINTER = Fetch[@PDA.state[pri]];
        IF offset = LOOPHOLE[0] THEN ERROR;
        state  LengthenPdaPtr[offset];
        Store[@PDA.state[pri]]  Fetch[state];
        RETURN[St&?];
        END;

    FreeState: PROCEDURE [pri: Priority, state: StateHandle] =
        BEGIN
        Store[state]  Fetch[@PDA.state[pri]];
        Store[@PDA.state[pri]]  offsetPda[state];
        END;

There is no provision for trapping or faulting when a state vector ist is empty. The scheduler guarantees that, when it runs a process, there is a state vector available for the subsequent pre-emption that may occur.

Programming Note: Because there must be one state vector for each pre-emptible process, the number of state vectors in each list determines the degree of pre-emptive multi-programming allowed at the corresponding priority-level.

### 10.4.3 Faults

A fad is an exception that causes a process switch. There are three such exceptions: a page fault, a write protect fault, and a frame-allocation fault. Each type of fault has an associated queue where faulted processes are kept, as well as an associated fault-handler, represented by a condition variable that is notified when the fault occurs. This information is organized as a substructure of the `PDA`.

    FaultVector: TYPE = ARRAY Faultlndex OF FaultQueue;
    Faultlndex: TYPE = [0..8);
    FaultQueue: TYPE = MACHINE DEPENDENT RECORD [
        queue (0): Queue, condition (1): Condition];

Fault processing is logically much like trap processing (§9.5.2), with the following differences:

- The fault parameter is saved in the state vector of the current (faulted) process, rather than in the frame of the trap handler.
- The fault results in a process switch rather than a control transfer. The fault handler can therefore run in a Main Data Space different from the faulted process.

The precise actions that must be taken by the processor when a fault occurs are shown by FaultOne (single word parameter), FaultTwo (double word parameter), and the common Fault routine.

    FaultOne: PROCEDURE [fi: FaultIndex, parameter: UNSPECIFIED] =
        BEGIN
        psb: PsbIndex = Fault[fi];
        state: POINTER TO StateVector = Fetch[@PDA.block[psb].context];
        StorePda[@state.data[o]] + parameter;
        ERROR Abort;
        END;

    FaultTwo: PROCEDURE [fi: FaultIndex, parameter: LONG UNSPECIFIED] =
        BEGIN
        psb: PsbIndex = Fault[fi];
        state: POINTER TO StateVector = Fetch[@PDA.block[psb].context];
        StorePda[@state.data[o]]  LowHalf[parameter];
        StorePda[@state.data[l]]  HighHalf[parameter];
        ERROR Abort;
        END;

    Fault: PROCEDURE [fi: Faultlndex] RETURNS [PsbIndex] =
        BEGIN
        faulted: PsbIndex = PSB;
        Requeue[src: @PDA.ready, dst: @PDA.fault[fi].queue, psb: faulted];
        NotifyWakeup[@PDA.fault[fi].condition];
        PC  savedpc;
        SP  savedSP;
        Reschedule[preemption: TRUE];
        RETURN[faultedj;
        END;

Fault saves the `PSB` index of the faulted process, moves the process to the appropriate fault queue, and notifies the fault handler using NotifyWakeup (because there is no monitor controlling access to the fault condition variables; see §10.4.4.2). It then restores the `PC` and `SP` and invokes the scheduler. The fault routines store their parameters in the state vector of the faulted process. The three possible faults have the following parameters:

    Framefault: PROCEDURE [hi: FStndex] = {FaultOne[qFrameFault, fsi]);

A frame of the requested size (or larger) could not be allocated. The value of the parameter is the frame size index requested by `XFER` or >the Allocate Frame instruction (§9.2.2).

    PageFault: PROCEDURE [ptr: LONG POINTER] = {FaultTwo[qPageFault, ptr]};

    WriteProtectFault: PROCEDURE[page: LONG POINTER] =
        { FaultTwo[qWriteProtectFault, ptr]};

An access to an unmapped page (a store into a write rotected page) was attempted. The value of the fault parameter is the virtual address used by the memory reference that faulted (§:3.1.1). The sizes of fault parameters determine the value of CSV, the minimum size of a state vector; it is defined in the Appendix.

Because the fault routine always re-establishes the initial state of a faulted instruction, multiple faults on a single instruction are invisible to the programmer, and there is no need for the fault handler to concern itself with possible partial side effects of the instruction or with the continuation of partially completed instructions.

Programming Note: After correcting the cause of the fault, the fault handler must use the Requeue instruction (instead of NC or BC) to remove the faulted process from the fault queue and make it ready.

### 10.4.4 Interrupts

An array of reserved condition variables is allocated in the Process Data Area for servicing interrupts on one of sixteen interrupt-levels An interrupt is implemented by notifying one of these conditions:

    InterruptVector: TYPE = ARRAY InterruptLevel 0F InterruptItem;
    InterruptLevel: TYPE = [0..WordSize);
    InterruptItem: TYPE = MACHINE DEPENDENT RECORD [
        condition (0): Condition,
        available (1): UNSPECIFIED];

When an external event occurs that requires service from an interrupt process, a wakeup is generated. Wakeups include signals from devices and controllers, and perhaps also internal signals within the processor (for example, clocks or timers). Wakeups are held pending until completion of the current instruction, when they are translated into interrupts by the processor.

Design Note: Some interrupt levels may be reserved for internal use by the processor. One level typically is used to implement the check for timeouts (§10.4.5). The (read-only) wakeup mask register indicates the reserved levels (defined in Appendix A):

    WM: UNSPECIFIED = cWM;

This register has the same format as `WP`; bit i corresponds to interrupt level i (see below).

### 10.4.4.1 Checking for Interrupts

Because interrupts occur only between instructions, wakeups received during the execution of the current instruction are buffered in the wakeup pending register `WP`. A device or controller requesting service from the process assigned to interrupt level i sets bit i of this register to one. It must do so atomically with respect to reads and writes of this register performed by other devices and the processor.

    WP: UNSPECIFIED;

Before fetching and executing each instruction, which invokes the following routine to test for the presence of an calls CheckInterrupt:

    InterruptPending: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        RETURN[WP # 0 AND InterruptsEnabled[]];
        END;

Implementation Note: For maximum execution speed, the `WP # 0` test should always be done before the InterruptsEnabled test, since interrupts are almost always enabled.

The `WP` register saves only one wakeup request for each interrupt level per instruction execution, and the check for pending wakeups is made once before the beginning of each instruction (except for interruptible instructions; see below) by the main loop of the instruction interpreter (§8). They check for pending wakeups during execution and make special provisions for restart in the event of an interrupt.

The worst case response to the highest-priority interrupt will occur when the interrupt request is raised in conjunction both with the timeout scan and with an opcode that requires a long execution time without interrupt checks. To avoid making response time worse than it must be, opcodes should check for interrupts at intervals small compared to the timeout scan.

Programming Note: The software must be written to be robust in the face of lost wakeups. The timeout mechanism described in the next section is designed to assist the programmer with this requirement.

### 10.4.4.2 Interrupt Processing

The Interrupt routine translates each pending wakeup into a notify of the condition associated with that wakeup's interrupt level. Higher interrupt levels are always processed first. Notice that the interrupt level is independent of the priority of the process waiting on the condition variable. The level affects only the order in which interrupt processes with the same priority are moved to the ready queue.

    CheckForlnterrupts: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        IF InterruptPending[] THEN RETURN[Interrupt[]]
        ELSE RETURN[FALSE];
        END;

    Interrupt: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        mask: UNSPECIFIED:  ?;
        wakeups: UNSPECIFIED;
        tequeue: BOOLEAN  FALSE;
        wakeups  WP;
        WP  0;
        FOR kvd: hltC?ffUpt~evd DECREASING IN tntWfUpth/el DO
            i  AND[wakeups, mask] # O THEN
                fr Notif)@`b&~@@PoA.interrupt[level].condition]
                OR  `i requeue- y`iequeue; r&
                k  Shift[mask, i];
            ENDLOOP;
        RETURN[feqUW?];
        END;

Implementation Note: The two assignment operations `wakeups +=- `WP` and `WIB` + o must be performed atomically with respect to devices that write into the wakeup pending register.

Both faults and interrupts move process to the ready queue by performing a variatiom of the standard notify operation (§10.2.5). Condition variables iil the interrupt vector (and in the fault vector) make use of an additional bit. It records a wakeup in case no process is waiting on the condition. This record is necessary because another process (the device, in this case) can notify the condition without entering the monitor that normally protects a condition variable. If the device notifies the interrupt process between the time the process decides to wait on the condition variable (for example, it checks the status and finds the device busy) and the time the process actually executes the wait instruction, the notify would be lost. To prevent this, the processor converts a pending wakeup (and a fault) into a NotifyWakeup, which sets a wakeup bit in the condition variable if no process is waiting on the condition.

    NotifyWakeup: PROCEDURE [c: LONG POINTER TO Condition] RETURNS [BOOLEAN] =
        BEGIN
        cond: Condition;
        fequeue: BOOLEAN  FALSE;
        CleanupCondition[c];
        cond  Fetch[c];
        IF cond.tail = NULL THEN
            BEGIN
            cond.wakeup > TRUE;
            store[c]  cond;
            END
        ELSE
            BEGIN
            WakeHead[c];
            requeue   TRUE;
            END;
        RETURN[requeue];
        END;

`

The instructions (§10.2.3) do not wait when the wakeup bit is set.

Programming Note: Since interrupts (and faults) perform a notify rather than a broadcast, only a single process should be waiting on the conditions in the interrupt vector and the fault queue.

### 10.4.4.3 Disabling Interrupts

Generation of interrupts is controlled by the wakeup disable counter `WDC`. It counts the number of times interrupts have been disabled. The minimum value of `WdcMax` is given in Appendix A.

    WDC: CARDINAL;
    WdcMax: CARDINAL = cWDC;

    InterruptsEnabled: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        RETURN[WDC = O];
        END;

    Disablelnterrupts: PROCEDURE =
        BEGIN
        WDC  WDC + 1;
        END;

    Enablelnterrupts: PROCEDURE =
        BEGIN
        WDC  WDC - 1;
        END;

The instructions shown below allow the programmer to disable and enable interrupts. They generate a trap if the wakeup disable counter would be incremented decremented out of range (§9.5).

#### DI Disable Interrupts

    DI: PROCEDURE =
        BEGIN
        IF WDC = WdcMax THEN InterruptError[];
        Disablelnterrupts[];
        END;

#### EI Enable Interrupts

    EI: PROCEDURE =
        BEGIN
        IF WDC = 0 THEN InterruptError[];
        EnableInterrupts[];
        END;

ProgrammingNote: A counter (rather than a flag) allows the programmer to disable and enable interrupts without regard to the previous state of the register, provided that the maximum value of the counter is not exceeded.

### 1O.4.3 Timeouts

A process can be timed out by the processor, so it does not wait indefinitely on a condition queue. When a process executes a Monitor Wait instruction (§10.2.3), it specifies a time interval that limits the amount of time the process will spend in the condition queue. If the process is still on the queue after this interval has elapsed, it will be made ready by the processor When the process next executes, it appears to the programmer as if it had received a notify, Thus, lost notifies will not cause processes to wait forever.

To implement timeouts, each `PSB` has a timeout field which indicates when its corresponding process should be timed out. The Monitor Wait instruction (§10.2.3) generates this value by adding its time interval operand the current value of the time (obtained from a processor register; see below). A value of zero indicates that the process should not be timed out. Unless a process is waiting on a condition queue, its timeout is always zero; that is, only waiting processes can be timed out.

Timeouts are measured in ticks, where the conversion between ticks and real time is processor-dependent. A tick is on the order of 40 milliseconds. The upper and lower limits on the size of a tick are specified in Appendix A, is the size of the timeout interval measured in the units of the interval timer IT (§3.3.3).

    Ticks: TYPE = CARDINAL;
    TimeoutVal: LONG CARDINAL;

Design Note: The size of the timeout interval should be chosen so that the overhead of checking for process timeouts is acceptably low. Consider the expected number of processes in the system and the time required to perform fhe timeout scan, along with the minimum and maximum available timeout intervals.

The current value of the time, measured in ticks, is kept in a programmer-accessible processor register called the process timeout counter. The accuracy of this timer measured against real time is not specified by the architecture.

    PTC: Ticks;

Programming Note:Because the accuracy of the `PTC` is unspecified, programmers should use the interval timer `IT` whenever accurate knowledge of real or elapsed time is necessary. Moreover, there is no guarantee that a timeout will occur within the interval specified by a wait instruction only that it will occur at approximately that time.

The CheckforTimeouts routine is called by the main loop of the processor (§4.1). It checks to see if a timeout interval has elapsed by comparing the current value of the interval timer with its value at the last call (saved in the private global variable `time`). If interrupts are enabled and a timeout interval has elapsed, the processor increments the process timeout counter and calls TimeoutScan to check for `PSB`s that should be timed out.

    time: LONG CARDINAL;

    CheckForTimeouts: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        temp: LONG CARDINAL = IT;
        IF InterruptsEnabled[] AND temp - time >= TimeOutInterval THEN
            BEGIN
            time  temp;
            PTC  PTC + 1;
            IF[PTC = O] THEN PTC  PTC + 1;
            RETURN[TimeoutScan[]];
            END
        ELSE RETURN[FALSE];
        END;

Programming Note: The Process Timeout Counter does not tick while interrupts are disabled. If interrupts remain disabled for an extended period, the processor makes no attempt to timeout processes that should have been notified during that period.

Implementation Note: The implementation need not follow the above algorithm exactly, as long as it appears to the programmer that a timeout occurs only between instructions, and that the scan occurs at intervals of approximately one timeout interval. In particular, the scan may be initiated by an interrupt internal to the processor, rather than by a call from within the main loop, or the scan can be done in parallel with the processor, as long as the timeout itself is properly synchronized with instruction execution.

The timeout scan examines the timeout of each process in the timeout vector. Processes with zero timeouts are ignored. If the timeout is equal to the current value of the process timeout counter, the timeout is cleared and the process is moved from an unknown condition queue to the ready queue. At the end of the scan, if any processes have been made ready, the routine returns TRUE.

    TimeoutScan: PROCEDURE RETURNS [BOOLEAN] =
        BEGIN
        requeue: BOOLEAN  FALSE;
        count: CARDINAL = Fetch[@PDA.Count];
        FOR psb: PsbIndex IN [StartPsb..StartPsb + count) DO
            timeout: Ticks  Fetch[@PDA.block[psb].timeout];
            IF timeout # 0 AND timeout = PSB THEN
                BEGIN
                flags: PsbFlags  Fetch[@PDA.block[psb].flags];
                flags.waiting  FALSE;
                Store[@PDA.block[psb].flags]  flags;
                Store[@PDA.block[psb].timeout]  0;
                Requeue[src: LOOPHOLE[LONG[O]], dst: @PDA.ready, psb: psb];
                requeue  TRUE;
                END;
            ENDLOOP;
        RETURN[requeue];
        END;

Because the condition queue containing the process is unknown, zero is passed as the source queue to Requeue, which makes special provisions for handling this case (§10.3).

Design Note: It is the programmer's responsibility to ensure that the count reflects the PSBs that should be examined, and that the timeout of any `PSB` not representing an active process is set to zero (see §l0.l.1).

Previous [TOC] Next

[last edited 4/11/99 1:08AM]