InitRech 2015/2016, sujet 28

Summary

This article speaks about different scheduling techniques of dependent periodic tasks, without synchronization mechanisms.

The main goal of these techniques is to design algorithms for the scheduling of critical embedded systems by fixing priority scheduling policies for different classes of dependent tasks.

Usually, the set of (dependent) tasks are only sequencing manually or at system execution to be sure that the execution of the implementation is predictable and deterministic (meaning that the outputs of the system are always the same for a given sequence of inputs).

So, the purpose of this document is to investigate scheduling policies for critical embedded control systems, which support dependent tasks.

An embedded control implementation must respect a series of hard real-time constraints, control devices with different characteristics at different rates, respect deadline constraints (maximum latency requirement) and also be functionally deterministic.

Moreover, researchers only consider policies that don't require synchronization mechanisms (like semaphores for instance).

The authors begin by introducing the case study of flight application software and explain that they study the scheduling problem of periodic tasks with two kinds of precedence constraints: simple and extended precedences.

A task set is feasible under a given priority assignment if the schedule produced by this assignment respects all the constraints of the task set.

Researchers were initially inspired of a schedulability test for periodic tasks with simple precedences in general.

Tasks can then be scheduled using the deadline-monotonic (DM) policy but the respect of precedence constraints is ensured by semaphores. Then, they use a different approach by encoding precedences in task real-time attributes, adjusting the release times and the deadlines of the tasks in addition to earliest-deadline-first policy (EDF).

Researchers have first considered the problem of scheduling a set of periodic tasks with simultaneous release times, constrained deadlines and simple precedences.

They have used a derived from DM which consists in adjusting task dead-line and applying the DM policy on the adjusted task set. This policy has a square complexity and standard array sorting algorithms to sort tasks a complexity of "n log2(n)". The schedule obtained is computed until the longest first deadline of the tasks.

Then, researchers considered the problem with arbitrary release times, constrained deadlines and simple precedences.

They manipulate deadlines and release times by using a topological sort starting from tasks without predecessors. Task priorities can be assigned to tasks in order (starting from the lowest priority) and any priority assignment is feasible.

Finally, researchers take into account the problem with extended precedences.

They have extended the previous results to periodic extended precedences. But they considered in detail how instances of the tasks are related. For each precedences, only the initial release times must be adjusted in order to respects the previous property for all task instances. Moreover, deadlines relative are modified in the same way as simple precedences.

Main contribution

This article studies the scheduling of critical embedded systems, without synchronization mechanisms to prevent deadlocks or scheduling anomalies.

If we do not allow semaphore synchronizations, the system is not schedulable with a static priority policy.

Indeed, the task graph must be unfolded for the execution and this can lead to important computation overhead and high memory consumption as the scheduler needs to make its decisions according to a large task set.

With semaphore, during the execution, the system becomes unschedulable due to a task that does not take its complete wcet to execute.

Moreover, known schedulability tests for scheduling priorities with synchronization mechanisms only provide sufficient schedulability conditions and not necessary schedulability conditions.

At last, highly critical systems must go though certification processes and a system with policies without semaphore synchronizations are easier to certify, because of a more compact Operating System.