Scheduling (Fixed Schedule, Prios, #1)

Starting Point

Here I have described a scheduling solution based on a fixed timing schedule. All processes are invoked based on FPGA-based timers. The scheduling algorithm goes round in the linked process ring, so all processes will be activated at some point.

Process Priorities

Process priorities are added using one ring of linked processes per priority level, as a direct extension of the existing concept.

  • The scheduling algorithm goes around in each ring separately. That is, each process in a priority ring will eventually be activated, if processes of its prio level are not locked out by higher prio processes.

  • Processes of a specific prio, which are ready based on timing or device signals, will be invoked before any lower ready prio processes. The other way around, lower prio processes can be locked out by higher prio ones, if the latters' run-times exceed their periods.

  • Priority and period are not connected. In particular, short periods 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.

  • There are three priority levels right now. Priorities are positive integers, including zero, with lower priority numbers meaning higher process priority.

The ring per prio is used to ensure that a process cannot lock out the other processes at the same prio. A simpler solution would be a single process list, sorted by priority and possibly process period.

Oberon.Loop

The Oberon.Loop uses the following algorithm. It puts value on the lightweight detection of the ready conditions as signalled by the FPGA devices for timing and device signalling, to only do any further checking and processing upon such condition. Other approaches are feasible, of course, such as checking for process state first.

As we now have to ensure that no process of higher prio is pending (ready) before even considering the next lower one, we have to work through the whole higher level ring. Therefore, the ready bits from timing and device signals are read in one go, and the checks per process are done one this loaded data word. This also has the advantage that all process checks are based on the same time time basis.

Per one loop of the Loop maximally one process gets invoked, at which point the evaluation of the process readiness is stopped, and the dance starts anew with the next run of the Loop. This gives command and upload handling a chance to run. When a process was invoked, the pointer into the corresponding ring gets advanced, and the process evaluation will start from there with the next loop.

MODULE Oberon;

  VAR
    procs: ARRAY NumPrios OF Process; (* process rings *)
    cp: Process;  (* current process *)

  PROCEDURE Loop*;
    VAR
      res, prio: INTEGER;
      ch: CHAR;
      done: BOOLEAN;
      p, p0: Process;
  BEGIN
    WriteLine("Starting scheduler");
    REPEAT
      IF Console.Available() > 0 THEN
        (* command and upload handling *)
      ELSE
        (* load ready bits *)
        ProcTimers.LoadReadyStatus;
        ProcDevSig.LoadReadyStatus;
        
        (* GC timing ... *)
        
        (* check the processes *)
        prio := 0; done := FALSE;
        WHILE ~done & (prio < NumPrios) DO
          IF procs[prio] # NIL THEN            
            p := procs[prio]; p0 := p;
            REPEAT 
              IF ProcDevSig.ProcessReady(p.pcNo) THEN (* device signals *)
                ProcDevSig.ResetSignals(p.pcNo);
                IF p.state = AwaitDevsigTo THEN
                  ProcTimers.CancelDelay(p.pcNo)
                END;
                p.retVal := OK;
                p.state := Active; cp := p; Coroutines.Transfer(loop, p.cor); cp := NIL;
                procs[prio] := procs[prio].next;
                done := TRUE;         
              ELSIF ProcTimers.ProcessReady(p.pcNo) THEN (* timing *)
                ProcTimers.SetPeriod(p.pcNo, p.period);
                p.retVal := OK;
                IF p.state = AwaitDevsigTo THEN
                  ProcDevSig.ResetSignals(p.pcNo);
                  p.retVal := Timeout
                END;
                IF ~(p.state IN {Suspended, AwaitDevsig}) THEN
                  p.state := Active; cp := p; Coroutines.Transfer(loop, p.cor); cp := NIL;
                  procs[prio] := procs[prio].next;
                  done := TRUE
                END
              END;
              p := p.next
            UNTIL done OR (p = p0)
          END;
          INC(prio)
        END 
      END
    UNTIL FALSE
  END Loop;

END Oberon.