The easiest trap to fall into is to implement a fancy scheduling algorithm. Even if the algorithm is particularly efficiently implemented, it is likely to execute hundreds rather than tens of instructions every time a scheduling decision is made. In practice, making a scheduling decision means deciding where in the ready queue a process must be inserted when it becomes ready or exceeds its slice. This means that scheduling decisions are made as often as context switches. And when context switches are made every few milliseconds (how else in an interactive or real-time environment?), the cost of a fancy scheduler cannot be justified.
Another trap is the manipulation of scheduler data structures from interrupt handlers. For example, letting the handler for the ``time slice expired'' interrupt enter the executing process into the ready queue. Or letting the handler for the ``time-out'' interrupt update the time-out list. Even relatively simple operations on data structures require multiple instructions and leave the data structure dangerously inconsistent if interrupted. Continually masking and unmasking interrupts as critical sequences of instructions are entered and exited, is error prone and inefficient. Moreover, such an approach may inadvertently result in interrupts being masked for longer than is tolerable in a real-time environment.
The 680XX-architecture also provides numerous problems. For instance, it is easy enough to say in pseudo code ``arrange that, when the last TRAP/ interrupt handler returns, it is not the current process that is resumed, but the SRD''.
The obvious way to do this is to copy the saved program counter (PC) and status register (SR) of the last stacked return frame to the PCB of the current process, and then to modify the return frame so that the corresponding RTE instruction branches to the SRD instead of back to the current process.
However, locating the PC and SR of the last return frame is a problem. The 680XX-architecture provides a separate supervisor stack, so one knows the address of the last word of the last frame. Unfortunately, there are different frame sizes and the offset of the PC+SR from the last word is different for different frame sizes. To compound the problem, an interrupt handler can be interrupted before even executing a single instruction. Thus it is not possible for an interrupt handler to reliably record its frame type in a suitable location.
Fortunately, the problem can be overcome by assuming all frames are of the same type, and relying on the handlers of interrupts with strange frames to inspect for, and fix up, incorrect ``arrangements'' before returning control (such handlers are rarely executed). Nevertheless, one would rather not have the problem in the first place.
Another simple pseudo code statement with a complicated realization on the 680XX-architecture, is ``save all registers'' meaning save the current processor context. One would like to do so as efficiently as possible, preferably with a single instruction. However, the MOVEM instruction is quite inadequate. First of all, context swapping takes place in supervisor mode, but involves the user mode stack pointer which is not visible to the MOVEM instruction in supervisor mode. The result is two extra instructions for each save/restore.
Moreover, in order to save the registers directly into the current PCB, rather than saving them on the stack and then copying the stacked copies to the PCB, a pointer to the PCB location must be kept in a register. However, this cannot be done because the registers have not been saved and hence cannot be changed. The result is three extra instructions.
Additionally, separate instructions are needed to save floating point registers, switch the memory map, invalidate the instruction cache, and so on. One can understand how this came about, but a dedicated ``current PCB register'' and appropriate context save/restore instructions now seem overdue, especially in the light of the introduction by the 68020 of a Master Stack Pointer which is of no use in the multi-programming mechanism described here.
Another problem on the 680XX-architecture is performing atomic insertions and removals of linked list elements. The 68020 purports to support this through its compare-and-swap instructions. However, instruction sequences using these instructions are difficult to construct and understand, and involve an unpredictable number of iterations through a loop. Dedicated linked list instructions would be more efficient as well as easier to use.
It is significant to note that, as far as one can tell from the description[8], the 680XX-like ``TRON'' architecture designed by the University of Tokyo, addresses both the above problems (as well as fixing some other 680XX quirks).
A further problem, not with the 680XX-processor architecture, but one that is present in many micro-computer systems, is the unsuitability of hardware timers for use by multi-programming mechanisms.
The target hardware of the implementation on which this paper is based, provides each processor with two Zilog Z8536 CIO Counter/Timer and Parallel I/O units. These timers are unsuitable for several reasons:
Points 3 and 4 combine to form yet another problem: The handler of an interrupt from the CIO must write to a CIO register in order to clear the interrupt. Hence, accessing CIO registers must be done with interrupts masked.
Together, these factors conspire to make the operation of starting and stopping a timer needlessly expensive and a major factor in the time taken by context switches.
A more ideal micro-computer design would provide an array of millisecond resolution timers - as many as the maximum number of processes that can be simultaneously executed (256 seems a reasonable number). Each of these timers should have a uniquely addressable register associated with it. Starting a timer should be as simple as writing the time period into its register. Stopping a timer and determining the time left, should be as simple as reading its register. Preferably, the value returned should not be the time left, but the time elapsed.
If a timer counts down to zero, it should interrupt and automatically enter the stopped state. Naturally, the interrupt request logic should be cleared by the processor hardware interrupt service logic, and the identity of the interrupting timer should be obtainable by means of a single read instruction.
The availability of such an array of timers will significantly simplify and speed up the implementation of the multi-programming/time-out mechanism described in this paper. Naturally, it would be too expensive to implement such an array using existing ``off the shelf'' chips. However, it should be possible to create a single custom VLSI chip providing such an array.
Prof Herman Venter