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

• US 9,582,325 B2
• Filed: 11/05/2013
• Issued: 02/28/2017
• Est. Priority Date: 11/06/2012
• Status: Active Grant

• Current Assignee: Centre National De La Recherche Scientifique
• Original Assignee: Centre National De La Recherche Scientifique
• Inventors: Bilavarn, Sbastien, Bhatti, Muhammad Khurram, Belleudy, Ccile
• Primary Examiner(s): Kim, Sisley
• Application Number:
  US14/441,070
• Publication Number:
  US 20150293787A1
• Time in Patent Office: 1,211 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 1/26 Power supply means, e.g. regulation thereof for memories G11C
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A method for scheduling tasks with deadline constraints, based on a model of independent periodic tasks and carried out in the user space by means of API POSIX is provided.

Claims

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.