Model Approach

We consider the scheduling problem for non-independent task systems with firm deadlines. We are interested in off-line scheduling techniques: a valid schedule is computed before run-time, which is then stored within a table used by the dispatcher. These techniques are mainly model-oriented. They have two major advantages:
 
  • on the one hand, the processor overload due to scheduling is at most as possible reduced since no scheduling algorithm has to run;
  • on the other hand, these techniques are most often based on exhaustive exploration of the solution space (the set of all possible schedules) and thus, if one valid schedule exists, they will find it. These methods are thus more powerful than on-line strategies (which are mainly based on a priority-driven algorithm executed at run-time) since they make their decisions according to the global knowledge of the application, not only on the instantaneous state of the application.

We considerer model oriented approaches based on:

  • Petri nets;
  • discrete geometry;
  • markovian technique based models.

The problems that we address are:

  • taking explicitly conditional statements into account during scheduling: scheduling tree, strong scheduling;
  • using semantic properties for scheduling;
  • considering scalability properties of real-time applications such as task adjunction (either periodic or aperiodic), or processor failure;
  • geometrical characterization of fair behaviours;
  • measures of fairness for either the extraction of as fair as possible schedules or for a fair distribution of idle time units;
  • analysis of cyclicity properties in multiprocessor environment;
  • analysis of quality of scheduling processes.