The multi-programming mechanism presents the following four routines as its interface to the rest of the operating system:
Make_ready (pcb)
Execute_next (pcb)
Handle_slice_expired
Block
The first three routines are usually called by interrupt handlers, and the last is called by the handler of a TRAP instruction executed by the current process. The effect of the routines will be described in the next section and is illustrated by figure 1.
For a variety of reasons, it is complicated to write these routines such that they are safely interruptible by each other. On the other hand, it is highly undesirable to mask interrupts for the duration of each routine, since a routine may execute several hundred instructions.
Consequently, calling Make_ready from an interrupt handler does not cause the real routine to be immediately executed. Instead, a ``stub'' routine is executed which merely adds a request to execute the real Make_ready to an ``action queue''. The same applies to the other routines.
The action queue is serviced by the ``scheduler routine dispatcher'' (SRD) which executes the requests one by one - by calling the real scheduler routines. This way, the scheduler routines can be executed with interrupts enabled, but without the possibility of a (real) routine being invoked while another is still executing.
It is of course necessary that the operations of adding and removing action requests must be ``atomic''. This can be done either by appropriately using the 68020 compare-and-swap instructions, or by masking interrupts for the short duration of these operations.
Rather than require all interrupt handlers to branch to the SRD when they return control, interrupt handlers are allowed to return control in the normal fashion (using an RTE instruction). The scheduler stub routines arrange that the last RTE instruction (which would have resumed the interrupted process) branches to the SRD. This way, an interrupt handler only ``pays'' for multi-programming if it actually uses a scheduler routine. For example, an interrupt handler servicing a serial input port, has to ``pay'' for scheduling only when a carriage return is pressed and the process waiting for an input line from the port has to be unblocked. Since this handler only needs to save and restore the one or two registers its needs (rather than all the registers), the savings can be considerable.
The first action taken by the SRD is to save all registers in the process control block (PCB) of the current process. Next, the SRD removes a request from the action queue and calls the corresponding scheduler routine. This continues until the queue is empty. Note that scheduler routines have the free use of most registers.
Once the queue is empty, the SRD restores the saved registers from the current PCB and resumes the execution of the current process. It follows that a context switch is accomplished simply by changing the current PCB.
Any entries added to the action queue after a decision has been made to exit the SRD won't be served until the SRD is restarted. Arranging for the SRD to restart as soon as it completes its exit, is rather tricky. Consequently, the SRD masks interrupts before checking whether to exit, and keeps them masked throughout the exit sequence (should a decision be made to exit). The following sequence is thus executed atomically at the end of the SRD:
IF action queue is empty THEN
restore the registers of the current process
resume the execution of the current process
ENDIF
As already mentioned, the scheduler routine stubs that are called from interrupt/TRAP handlers arrange that the RTE instruction that would have resumed the interrupted process, instead branches to the start of the SRD. It is of course possible for the SRD to be interrupted, and for a scheduler routine stub to be executed by such an interrupt. In such a case, the stub must simply allow the interrupt to return normally, rather than arranging for it to branch to the start of the SRD.
Prof Herman Venter