Process scheduling

In an architecture optimised for the concurrent processing of a set of processes on an arbitrary number of processors there is a fair probability that each processor will be required to manage more than one process. Furthermore, each communication event will cause at least one process to become un-runnable, necessitating a context switch in at least one processor. In order to maintain a balanced architecture the time taken for a processor to swap contexts should be a small fraction of the average process grain-time. Looked at another way, a processor with a lengthy context switching time can only support correspondingly large grain-times for a given granular efficiency. It is this consideration which led to the adoption of hardware support for process management and context switching in the transputer.

At the heart of the transputer's process management functions is a process scheduler held in microcode. The occam processes that it manages can be in one of two states, either active or inactive, and each state has a number of sub-states, as shown in Figure 1.

The active processes waiting to be executed are automatically linked into one of two run-queues by the microcode of the instruction which caused the suspension of processing. These two queues implement two levels of priority in the scheduling algorithm, and naturally the scheduler will choose to run a high priority process if one is runnable. Furthermore if a high priority process becomes runnable whilst a low priority process is executing, the low priority process is preempted and replaced by the high priority process. Switching to a high priority process takes slightly longer than switching from a high priority to a low priority process, or between two low priority processes, since there is a greater quantity of volatile context in the processor registers which must be saved. The list structures maintained by the transputer are illustrated in Figure 2.

Each transputer also maintains two timers, a low priority timer which increments every 64 μs, and a high priority timer which increments every 1 μs. A single time-slice lasts for 1024 high priority time periods, and low priority processes are de-scheduled at the first suitable moment after two time-slices have been completed. High priority processes are never preempted. When a process is de-scheduled its Iptr is stored at location (Wptr-1) and the process is linked to the back of the relevant run-queue. When a process becomes halted as a result of a local channel I/O operation the process workspace pointer is simply placed in the word of memory allocated to the channel, effectively linking the waiting process to a single-element list identified implicitly by the channel address. When a matching communication event occurs the microcode re-links the halted process to the appropriate run-queue^†. The transputer also provides instructions to initiate and terminate processes.

† The least significant bit of the workspace pointer is always zero, and is therefore used to store the process priority; the priority then identifies the correct run-queue.