Scheduling

Real-time operating systems define recurring tasks. Real-time tasks are often periodically released. Basically, a periodic task gets its input data from sensors and commands the controlled process by sending data to actuators. Every execution of a task is called a job that must complete by its deadline. Most of real-time kernels implement a priority-driven schedule. The schedule is defined at run-line by choosing the highest priority task to run among available tasks. At any time, the task having the highest priority is executed. According to the on-line scheduling literature, real-time scheduling can be viewed as a on-line scheduling paradigm having only one parameter that is provided on-line: the exact execution requirements of tasks is know when they complete. Furthermore, the execution requirement of a task varies from one job to another. Thus, only an upper limit of execution requirements is known for every task– called the worst-case execution time -Wcet). A on-line real-line scheduling algorithm is optimal if the algorithm finds a feasible schedule for the considered task set, if any.

Two main problems are studied for any on-line scheduling problems: the feasibility analysis that to define a scheduling algorithm so that tasks meet their deadlines at run-time and the schedulability analysis that proves if a given scheduling algorithm will guarantee that no deadline failures will occur at run-time. Both problems highly depend on the task models, sharing resource protocols, task synchronization/communication mechanism and execution platforms characteristics. Feasibility/Schedulability analyses are highly combinatorial decision problems. For number of these problems, only sufficient feasibility/schedulablity conditions are known in order to prove that deadlines will be met at run-time.

The topics studied in our team are:

  • new schedulability analysis for transaction of tasks or dependent task;
  • approximation algorithms for response time analysis;
  • analysis of tasks allowed to self-suspend for performing Input/Ouput operations;
  • analysis and configuration of real-time distributed systems.