Scheduling (Timed per Process)

Introduction

Strict scheduling requires timing per process. This could be implemented in software only, with the Loop updating each process' timer periodically. However, there’s this unused silicon in the FPGA. Also, process timers that run in hardware, independently of the software, appeared to be an ideal solution.

Here’s a first version, with an actual timer per process in the FPGA. Other variants are possible, eg. a fixed grid of possible periods, and will be evaluated as well (update: see here).

Oberon.Loop

Some relevant snippets from Oberon.mod, accordingly extended. This implementation is based on Coroutines, but that is not relevant for the timer concept.

MODULE Oberon;
  
  (* ... *)

  TYPE
    Process* = POINTER TO ProcessDesc;
    ProcessDesc* = RECORD
      state, period, startAfter, pcNo: INTEGER;
      cor: Coroutines.Coroutine
      (* ... *)
    END;

  VAR cp: Process; (* the current process, in a linked ring of processes *)

  (* ... *)

  PROCEDURE Loop;
  BEGIN
    IF Console.Available() THEN
      (* command and upload handling *)
    ELSE
      IF cp # NIL THEN
        cp := cp.next;
        IF ProcTimers.ProcessReady(cp.pcNo) THEN
          ProcTimers.SetPeriod(cp.pcNo, cp.period);
          IF cp.state # Suspended THEN
            cp.state := Active;
            Coroutines.Transfer(loop, cp.cor)
          END
        END
      END
    END
  END Loop;

  (* ... *)

END Oberon.

ProcTimers.mod

Module ProcTimers.mod implements the driver for the process timers in the FPGA.

MODULE ProcTimers;

  IMPORT SYSTEM;

  CONST
    CtrlAdr = -132;           (* write control data *)
    PeriodAdr = -136;         (* write period *)
    DelayAdr = -140;          (* write delay *)
    PrReadyAdr = PeriodAdr;   (* read process ready *)
    ProcNumShift = 27;
    ResetCtrl = ORD({1});

  PROCEDURE* SetPeriod*(pn: INTEGER; period: INTEGER);
  BEGIN
    SYSTEM.PUT(PeriodAdr, LSL(pn, ProcNumShift) + period)
  END SetPeriod;

  PROCEDURE* SetDelay*(pn; INTEGER; delay: INTEGER);
  BEGIN
    SYSTEM.PUT(DelayAdr, LSL(pn, ProcNumShift) + delay)
  END SetDelay;

  PROCEDURE* ResetTicker*(pn: INTEGER);
  BEGIN
    SYSTEM.PUT(CtrlAdr, LSL(pn, ProcNumShift) + ResetCtrl)
  END ResetTicker;

  PROCEDURE* ProcessReady*(pn: INTEGER): BOOLEAN;
  BEGIN
    RETURN SYSTEM.BIT(PrReadyAdr, pn)
  END ProcessReady;

END ProcTimers.

Each process has its own timer. The design allows for up to 32 processes, which is sufficient for control programs. My current RISC5 top file instantiates 16.

The IO addresses for each timer are the same, the number of the addressed timer is transmitted as bits [31:27] with the corresponding data, ie. the period or delay values.

Setting the period with SetPeriod in the Loop does not reset the running timer ticker, which simply restarts when the period value is reached, and the ready signal is set. Hence, even if in Loop the ready status would be detected with a delay, via ProcessReady, the overall timing of the process stays intact.

SetDelay serves for in-period non-blocking delays, eg. to implement a short delay to await a device’s response, such as with an I2C device sending data after it received the send command.

More Oberon.mod

Module Oberon.mod provides the following procedure for this purpose:

MODULE Oberon;

  PROCEDURE DelayMe*(delay: INTEGER);
  BEGIN 
    ProcTimers.SetDelay(cp.pcNo, delay);
    cp.state := Delayed;
    Coroutines.Transfer(cp.cor, loop)
  END DelayMe;

END Oberon.

With the following additional procedures in Oberon.mod we then can write a simple test program:

MODULE Oberon;

  PROCEDURE InitProc*(p: Process; proc: PROCEDURE; stk: ARRAY OF BYTE; period, startAfter: INTEGER);
  BEGIN
    (* ... *)
    p.state := Off;
    p.period := period;
    p.startAfter := startAfter; (* initial delay to allow staggered scheduling of processes with the same period *)
    NEW(p.cor); Coroutines.Init(p.cor, proc, stk)
  END InitProc;

  PROCEDURE InstallProc*(p: Process);
    VAR fpt: INTEGER;
  BEGIN
    IF p.state = Off THEN
      (* link p into the ring ... *)
      p.state := Idle;
      (* determine next free process timer, 'fpt' ... *)
      p.pcNo := fpt;
      ProcTimers.SetPeriod(fpt, p.startAfter);
      ProcTimers.ResetTicker(fpt)
    END
  END InstallProc;

  PROCEDURE NextProc*;
  BEGIN
    cp.state := Idle;
    Coroutines.Transfer(cp.cor, loop)
  END NextProc;

END Oberon.

Demo

The not very exciting example. It’s basically two interleaved “blinkers”, but with text output to better see what is going on (it’s also easier to present here).

MODULE TestProcTimers;

  IMPORT Oberon, Out;

  VAR
    p1, p2: Oberon.Process;
    s1, s2: ARRAY 1024 OF BYTE;

  PROCEDURE p1c;
    VAR cnt: INTEGER;
  BEGIN
    cnt := 0;
    REPEAT
      Out.String("p1--"); Out.Int(cnt, 4); Out.Int(Oberon.Time(), 10); Out.Ln;
      Oberon.DelayMe(500);
      Out.String("p1  "); Out.Int(Oberon.Time(), 14); Out.Ln;
      INC(cnt);
      Oberon.NextProc
    UNTIL FALSE
  END p1c;

  PROCEDURE p2c;
  BEGIN
    REPEAT
      Out.String("p2  "); Out.Int(Oberon.Time(), 18); Out.Ln;
      Oberon.NextProc
    UNTIL FALSE
  END p2c;

  PROCEDURE Run*;
  BEGIN
    Oberon.InstallProc(p1);
    Oberon.InstallProc(p2)
  END Run;

BEGIN
  NEW(p1); Oberon.InitProc(p1, p1c, s1, 1000, 0);
  NEW(p2); Oberon.InitProc(p2, p2c, s2, 1000, 200) (* note the initial delay *)
END TestProcTimers.

Here’s a snippet from the output in Astrobe’s terminal:

p1--  13   3588504
p2             3588704
p1         3589005
p1--  14   3589504
p2             3589704
p1         3590005
p1--  15   3590504
p2             3590704
p1         3591005
p1--  16   3591504
p2             3591704
p1         3592005
p1--  17   3592504
p2             3592704
p1         3593005

The timing of the two processes is exact: p1 and p2 are invoked every 1,000 milliseconds, with p2 lagging by 200 milliseconds, as requested via Oberon.InitProc. p1 prints its second line after a delay of 500 milliseconds, having yielded control to allow p2 to print its line in the meantime.

On close inspection you see that the time difference between the two lines printed by p1 is 501 milliseconds. The one millisecond in addition to the requested delay is caused by the busy waiting in the RS232 driver in Out.Int and Out.Ln during printing to the console1 (the related CPU processing is negligible in comparison).

However, the overall timing of p1 does not get disturbed by this. The process timers in the FPGA are very stubborn.

Note that delay takes precedence over period. That is, should a delay extends across the end of the process period, the ready signal for the process will not be set when the period terminates, but only after the delay. If a process requires a delay, it should be able to rely on the request, else hardware interactions, for example, could get messed up, resulting in run-time errors. The overall schedule of the process remains strict. Hence, if the delay extending across its period boundary was a one-off glitch, eg. caused by another process within the cooperative schedule, the process will simple skip one end-of-period invocation, but then fall back into its regular schedule. It’s the programmer’s responsibility to ensure that delays don’t extend across the period boundary on a regular basis.


  1. At 115,200 Baud: (10 bits / 1 char) * (1 s / 115,200 bits) * 12 chars = 1.042 ms ↩︎