InitRech 2015/2016, sujet 28

Summary

This article is 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 by a schedulability test for periodic tasks with simple precedences in general.

Then, tasks can 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 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 took into account the problem with extended precedences.

They extended the previous results to periodic extended precedences. But they considered in detail how instances of the tasks were related. For each precedences, only the initial release times must be adjusted in order to respect 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.

Applications

This research can improve stability and compactness in embedded systems.

For spacecraft and aircraft flight control systems for instance, we need to supervise the speed, attitude and position of the vehicle in real-time.

For a critical embedded system, we cannot afford an unexpected failure from a bad scheduling.

This kind of scheduling is very interesting for all systems considered as a real-time system, having lot of different input and output to manage.

We can use this to improve the security of self-driving cars for instance.

There are many parameters to manage, like distance, braking, cornering, engine, tracks, environment...