AN OVERVIEW OF THE MECHANISM

The multi-programming mechanism maintains three queues of ready processes. The ready queues are served in order of priority, with the highest priority queue reserved for real-time processes and the lowest priority queue reserved for a dummy ``idle'' process that is always ready. In addition, a pointer to the PCB of the currently executing process is maintained, as well as two global flags (``blocked'' and ``context switch requested'').

The effect of each of the routines making up the multi-programming mechanism interface, can be summarized as follows:

Make_ready (pcb)
The PCB is added to the end of the appropriate ready queue. If the process has a higher priority than the current process, a context switch is requested.

Execute_next (pcb)
The PCB is added to the front of the real-time queue and a context switch is requested. (This routine provides interrupt handlers for real-time devices with a way to get blocked ``high priority'' processes executing very soon after the interrupt was generated.)

Handle_slice_expired
The PCB of the current process is added to the end of the appropriate queue and a context switch is requested.

Block
A context switch is requested and the ``blocked'' flag is set to true. The PCB of the current process is presumed to be inserted into the appropriate data structure by the caller.

A point to note is that when a process becomes the ``current process'', its PCB is removed from its ready queue. And because a process can only block if it is the current process, it is never in a ready queue when it is the target of Block.

Of course, should the current process lose the processor without blocking, the PCB must be added to the end of the appropriate ready queue. This must be done carefully, since the current process may lose the processor more than once, as well as block, during a single run of the SRD. For example, while blocking itself a process expires its slice and is thus interrupted by the timer, and while this interrupt is being processed, an interrupt is received from an input device, with the result that a higher priority process is unblocked and the running process is preempted.

The simplest way to add the current process back into a ready queue at most once per run of the SRD, is to do it inside the uninterruptible termination sequence. Hence the SRD termination sequence must be extended as follows (making use of the global flags):

    IF action queue is empty THEN
      IF context switch requested THEN
        IF not blocked THEN
          add current PCB to end of appropriate ready queue
        ENDIF
        choose a new current process
      ENDIF
      restore the registers of the current process
      resume the execution of the current process
    ENDIF

In the implementation on which this paper is based, this requires at most 19 extra instructions to be executed in uninterruptible mode, bringing the maximum path length in this mode to 64 instructions. Should this be unacceptable, these instructions can be removed and the interruptable routines extended to test if previous routines have already placed the PCB back into a ready queue. It is also possible to somewhat reduce the remaining 45 instructions by resorting to coding tricks that make the code less readable. However, this was not felt to be necessary.

Some of the reasons for the rather high instruction count are given in the following sections.