Processes and Scheduling

Introduction

See this document for a few basic concepts and considerations of

  • processes
  • scheduling
  • interrupts
  • device sharing

Processes All the Way Down

All activity in Oberon RTS is executed as a process.1 This includes scheduling,2 command handling, and the garbage collector. Nothing “happens” outside a process. This uniformity makes run-time error handling and device sharing conceptually simpler and easier.

Coroutines

Processes are implemented using coroutines, not tasks. Coroutines make handling of devices easier, as the corresponding processes can be suspended at any time to, say, await a buffer to not be full, without this showing up in the processes' code as a split into different task handlers and state conditions. This is also true for “virtual devices” such as semaphores.3

Process Priority and Type

Processes are assigned a priority, and higher priority processes run before the ones at lower priority, subject to their activation conditions (period, delay, signal, etc.). Processes can change their own priority at run-time.

Each process is of a certain type, indicating its importance:

  • system process (Processes.SystemProc)
  • essential process (Processes.EssentialProc)
  • other process (Processes.OtherProc)

System processes and essential processes are so called vital processes.

The process type is mostly relevant for run-time error handling. As the name implies, system processes are reserved for the bare, basic system without any control program, for example the garbage collector and the command handler and user interface.

Essential processes are for the core of the control program, that is, required to implement the control logic. Other processes are auxiliary, ie. non-essential, processes that don’t need to be kept running for the control logic.

Regarding concept and implementation, process timer period (see below), priority, and type are orthogonal. For example, priority and period are not connected, ie. short periods (high activation frequency) do not automatically mean higher priority. The process designer can choose to set higher frequency processes at a higher prio, but does not have to.

Scheduling

Processes are always run by the scheduler, and always yield control back to the scheduler. Processes are guaranteed to run until they yield control, even if they create or enable a process of higher priority.

Processes can be run in a periodic fashion based on a timer, but don’t have to be. A process can also await a signal from another process, or await a device-signal to run when a device is ready, or any other means to implement a well-coordinated set of processes. For example, a set of processes reading sensors run timed, and a process that evaluates the sensor data awaits a signal from each of these timed processes.

In fact, when a process is created and installed, either by a command, a start-up command, or another process, it is given a process type and priority, but no assumptions are made about the kinds of enabling triggers or synchronisation mechanics it will use. The new process will then configure itself.

Upon installation, a new process simply gets enabled, hence will be activated by the scheduler as soon as possible. It then can, for example, enable and set its allocated periodic timer in its initialisation sequence, or use any other await-to-continue facility during its execution, for example a signal from another process.

Each process is put into a linked list, which is sorted by priority. Right now, a new process of the same priority as a process already in the list will be added as the first process of that priority.4

The scheduler has two phases, Evaluation and Execution:

  • The Evaluation phase is only entered if any of the processes is ready to run, based on a simple and fast global check for all processes, ie. without evaluating single processes yet. If Evaluation is entered, the process list is traversed, and for each process is checked if its conditions to be executed are met. If yes, the process is set to the ready state. Execution is set to start with the first process in the list.

  • After Evaluation, the scheduler enters Execution. The process list is traversed, and processes in ready state are run. Since the list is sorted by priority, higher priority processes are run first. After each activation of one process, the global check to enter Evaluation is done. As long as Evaluation is not entered, the next ready process in the list is run, that is, Execution repeats for each ready process as long Evaluation is not entered. If, or when, Evaluation is run, Execution of ready processes will again start at the beginning of the list, to ensure the highest prio processes get executed first.

All timing, including delays and timeouts, is done in the FPGA hardware, that is, no corresponding bookkeeping is required in the scheduler.

Normally, one Execution phase should run all ready processes, else the control system is overloaded. This can be a temporary condition, for example if a higher prio process took an exceptionally long time to run, and may or may not be problematic. If it occurs frequently, or even continuously, the process design must be reviewed and revised. Measures include adjusting the timing periods, or dividing higher prio processes into shorted slices between yielding control. The current scheduler does check for this overload condition, but does not take any corrective actions.5

An FPGA-based device measures the times spent in Evaluation and Execution, respectively, to assess the efficiency of the scheduler. This is an experimental feature for system development, not meant/planned to be included in an actual controller application. Right after start-up, with only the system processes running, the Evaluation phase uses about the same time as Execution. When fully loading the system with 15 processes (the system processes plus 12 test processes), the Evaluation phase’s run-time goes down to 10%, or even about 2% with some substantial processing by the test processes, of the Execution time (scheduler overhead).

Delays

A process can request a (non-blocking) delay for a certain time period. It will be suspended (ie. yields control) and then reactivated after the delay period.

Timeouts

Processes can set-up a timeout to ensure that they get a required “go ahead” signal or reply within a specified time period. Examples would include receiving a software or hardware signal, getting access to a shared resource via a semaphore, or a reply from an external hardware device. When activated, the process can check if it was triggered by the timeout or the “go ahead” signal or reply, and take action accordingly.

That is, the responsibility of detecting the error situation when a process is “not alive” anymore (starving), but awaits reactivating for too long (or even forever), is to be solved on the individual process level. The other common, “opposite” error situation of a process not yielding control within a defined period of time, is solved on system level by using a watchdog timer.

Process Timers

Each process can use one of eight timers. All processes on the same timer will be set to the ready state exactly at the same time, thus enforcing a fixed timing roster, and to avoid entering the Evaluation phase unnecessary due to minute differences between individual timers. The period of each timer is set during the system start-up.

Process Example: Garbage Collector

The process code (from module Oberon):

PROCEDURE gcc;
BEGIN
  Processes.SetPeriod(GCperiod);
  REPEAT
    Processes.Next;
    IF (gcCount = 0) OR (Kernel.allocated >= GClimit) THEN
      collect;
      gcCount := 1;
    END
  UNTIL FALSE
END gcc;
  • Processes.SetPeriod(GCperiod): the initialisation part sets the process up as periodically timed.
  • Processes.Next: yield control to the scheduler. It’s good practice to do the periodic yielding at the process loop start, to allow all other processes to run their initialisation sequence.
  • Check the conditions for the collector, and run it if needed.
  • collect corresponds to the relevant part of procedure GC in EO’s module Oberon, plus logging.

The process is created and installed by (defined in module Oberon, called in its body, see the start-up sequence):

PROCEDURE installGC;
  VAR res: INTEGER;
BEGIN
  heapSize := Kernel.heapLim - Kernel.heapOrg;
  GClimit := heapSize - (heapSize DIV GClimitDiv);
  gcCount := 1;
  NEW(gc);
  Processes.Init(gc, gcc, gcstack, GCstackHot, GCptype, GCprio, GCid);
  Processes.Install(gc, res)
END installGC;

Processes.Init takes the parameters as required by Processes.Process:

  • VAR gc: Processes.Process: the module variable to hold the process descriptor record
  • PROCEDURE gcc: the process code as outlined above
  • VAR gcstack: ARRAY GCstackSize OF BYTE: the process stack (CONST GCstackSize = 512)
  • CONST GCstackHot = 0: the size of the hot zone for the stack overflow monitor
  • CONST GCptype = Processes.SystemProc: the process type
  • CONST GCprio = 0: the process priority
  • CONST GCid = “gc”: the process id (Processes.ProcId)

res in Processes.Install(gc, res) will return an error code in case there are no process slots available anymore, which will never be the case for the garbage collector.


  1. After completion of the system start-up. ↩︎

  2. To be precise, the scheduler is implemented only as coroutine, as it does not need all the functionality and considerations of a process. For example, the scheduler does not need to be scheduled, evidently. ↩︎

  3. Also, coroutines are fun. ↩︎

  4. The process period cannot be considered, as not all processes are run periodically. ↩︎

  5. An overflow counter per process is incremented if found in ready state in the Evaluation phase. This counter is displayed by System.ShowProcesses. Note that running this command (or any command) can lead to overflow, most likely due to the serial outputs to the console. ↩︎