Method for scheduling with deadline constraints, in particular in Linux, carried out in user space

1. A method for scheduling tasks with deadline constraints, which is based on a model of independent periodic tasks and entirely performed in user space, in which:

each task to be scheduled is associated with a data structure, which is defined in user space and contains at least one time information item and an information item that is indicative of a state of activity of the task, said state of activity being chosen from a list comprising at least:

a state of a task being executed;

a state of a task awaiting the end of its execution period; and

a state of a task ready to be executed, awaiting a resumption condition;

in the course of its execution, each task modifies said information item that is indicative of its state of activity and, if need be, according to a predefined scheduling policy, calls a scheduler that is executed entirely in user space;

upon each call, said scheduler:

sets up a queue for the tasks that are ready to be executed, awaiting a resumption condition;

sorts said queue according to a predefined priority criterion;

if necessary, preempts a task being executed by sending it a signal forcing it to change to said state of a task ready to be executed, awaiting a resumption condition; and

sends said resumption condition at least to the task that is at the head of said queue;

said data structure containing information indicative of a thread associated with said task comprising:

a condition associated with said task;

subsequent deadline of said task;

worst case execution time of said task;

best case execution time of said task; and

actual execution time of said task;

said scheduler using a specific function for the allocation of said task on a processor, said method for scheduling tasks being executed under an operating system that is compatible with a POSIX standard, said operating system being a Linux system.

2. The method for scheduling as claimed in claim 1 , in which said scheduling policy is a preemptive policy, such as EDF, RM, DM or LLF.

3. The method for scheduling as claimed in claim 1 implemented in a multiprocessor platform, in which said data structure likewise comprises an information item relating to a processor to which the corresponding task is assigned, and in which said scheduler assigns to a processor of the system each task that is ready to be executed.

4. The method for scheduling as claimed in claim 3 , wherein upon each call for the scheduler, a “pthread” is created in order to ensure execution thereof, and in which the assignment of a task to a processor is performed by means of the CPU Affinity API.

5. The method for scheduling as claimed in claim 3 , wherein MUTEX is used in order to ensure the execution of a single instance of the scheduler at a time, and in which the assignment of a task to a processor is performed by mans of the CPU Affinity API.

6. The method for scheduling as claimed in claim 1 , in which said scheduler modifies the clock frequency and the power supply voltage of the or of at least one processor according to a DVFS policy.

7. The method for scheduling as claimed in claim 1 , having an initialization step, in the course of which:

the tasks to be scheduled are created, assigned to one and the same processor and put into a state awaiting a resumption condition, a global variable called a rendez-vous variable being incremented or decremented when each said task is created;

when said rendez-vous variable takes a predefined value indicating that all the tasks have been created, said scheduler is executed for the first time.

8. The method for scheduling as claimed in claim 1 , in which said data structure likewise contains information that is indicative of a thread associated with said task and with its worst-case execution time.

9. The method for scheduling as claimed in claim 1 , in which, upon each call for the scheduler, a “pthread” is created in order to ensure execution thereof.

10. The method for scheduling as claimed in claim 1 , involving the use of a MUTEX in order to ensure the execution of a single instance of the scheduler at a time.

11. The method for scheduling as claimed in claim 1 , in which said scheduling policy is a preemptive policy selected from the group consisting of EDF, RM, DM and LLF.

12. The method for scheduling as claimed in claim 1 , wherein upon each call for the scheduler, a “pthreacg” is created in order to ensure execution thereof.

13. The method for scheduling as claimed in claim 1 , wherein upon each call for the scheduler, a “pthread” is created in order to ensure execution thereof, and in which the assignment of a task to a processor is performed by means of the CPU Affinity API.

14. The method for scheduling as claimed in claim 1 , wherein MUTEX is used in order to ensure the execution of a single instance of the scheduler at a time, and in which the assignment of a task to a processor is performed by means of the CPU Affinity API.

15. The method for scheduling as claimed in claim 1 , involving the use of a MUTEX in order to ensure the execution of a single instance of the scheduler at a time.

16. The method for scheduling as claimed in claim 1 , in which said operating system is a Linux system, and in which, upon each call for the scheduler, a “pthread” is created in order to ensure execution thereof.

17. A computer program product comprising a non-transitory computer readable memory programmed with computer software, that, when executed by an apparatus, causes the apparatus to perform the method of claim 1 .