Introduction

Taskadd is a scheduler of real-time tasks using Patrick Meumeu's algebra, including preemption costs. This is a very first version (1.0).

It treats a set of tasks, called a scenario, which are supposed to share a single resource (a processor) and having possible constraints.

Each task starts at some release time, has some possible initialisation time and some steady state. In steady state, a task executes a fixed number of time units, named duration within a fixed number of time units, named period (all these numbers are integers) which are repeated forever:

      initialisation         steady           (repeated)
          time               state
     ................|xxxxxxxxxxxxxx........|xxxxxxxxxxxxxx........|...
     ^                <--duration-->
     |                <--------period------>
  release
   time

When a scenario contains several tasks, they may conflict for the resource, and because of possible tasks having a higher priority (or other contraints), the execution of its time units may not start at the beginning of each period, and also, may be interrupted (preempted) and restart later to complete its "duration" time units.

Patrick Meumeu's algebra provides a function, named plus (written in his thesis) which applies to two tasks, the first one having a higher priority than the second one. The result is another task having the same structure as above (initialisation, steady state...) and whose period is the LCM (Least Common Multiple) of the period of the two tasks.

Applying the function "plus" to all tasks of the scenario, in decreasing priority order, the result is provided. But the function may fail (for example if a constraint fails, or if the processor is overloaded): in this case, the scenario is not schedulable.

The execution of an instance ("duration" time units) of a task must not overflow the task period, otherwise the scenario is considered as not schedulable. Another possible constraint is the deadline, a value less or equal to the period: in this case the instance cannot overflow the deadline value.

In the input scenario, the initialisation time is empty (zero). But when two tasks are "added", the initialisation time of the resulting task may be not empty.


Copyright 2010 Daniel de Rauglaudre (Inria)

Valid XHTML 1.1