Method and system for deadline inheritance for resource synchronization

• US 10,628,221 B1
• Filed: 09/30/2015
• Issued: 04/21/2020
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Veprinsky, Alexandr, Shvaiger, Felix, Kucherov, Anton, Don, Arieh
• Primary Examiner(s): Puente, Emerson C
• Assistant Examiner(s): Labud, Jonathan R
• Application Number:
  US14/872,075
• Time in Patent Office: 1,665 Days
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Example embodiments of the present invention provide a method, a system, and a computer program product for managing tasks in a system. The method comprises running a first task on a system, wherein the first task has a first priority of execution time and the execution of which first task locks a resource on the system, and running a second task on the system, wherein the second task has a second priority of execution time earlier than the first priority of execution time of the first task and the execution of which second task requires the resource on the system locked by the first task. The system then may promote the first task having the later first priority of execution time to a new priority of execution time at least as early as the second priority of execution time of the second task and resume execution of the first task having the later first priority of execution time.

Claims

1. A method to prevent locking of a resource for a specific task comprising:

queuing a first task in a queue of tasks to be executed by at least one processor of a system, the first task having a first priority of execution time determined based at least in part on a first execution delay value associated with the first task;

queuing a second task in the queue of tasks, the second task having a second priority of execution time determined based at least in part on a second execution delay value associated with the second task, the second priority of execution time being earlier than the first priority of execution time;

queueing a third task in the queue of tasks, the third task having a third priority of execution time determined based at least in part on a third execution delay value associated with the third task, the third priority of execution time being earlier than the first priority of execution time and later than the second priority of execution time, wherein the time when the at least one processor of the system will execute each task is based at least in part on its respective priority of execution time, the respective priority of execution time of each task supplanting a priority associated with each task;

executing the first task by the at least one processor of the system, wherein the execution of the first task locks a resource on the system;

executing the second task by the at least one processor of the system, wherein the execution of the second task requires the resource on the system locked by the first task;

determining that the resource required for execution of the second task is locked by the first task;

responsive to determining that the resource required for execution of the second task is locked by the first task, promoting the first task having the first priority of execution time to a new priority of execution time at least as early as the second priority of execution time of the second task;

re-inserting the second task into the queue to wait for the first task to unlock the resource, the re-inserted second task having the second priority of execution time; and

continuing execution of the first task having the new priority of execution time by the at least one processor of the system, whereby promoting the first task having the first priority of execution time to the new priority of execution time at least as early as the second priority of execution time of the second task inhibits the third task having the third priority of execution time from executing and locking the resource prior to execution of the re-inserted second task having the second priority of execution time by the at least one processor of the system.

2. The method of claim 1 wherein executing the second task by the at least one processor of the system comprises preempting the first task having the first priority of execution time to begin execution by the at least one processor of the system of the second task having the second priority of execution time.

3. The method of claim 1 wherein the queue of tasks is configured to arrange the first, second and third tasks based at least in part on their respective priority of execution times.

4. The method of claim 1 wherein the system is a multi-core system and wherein executing the first task and the second task by the at least one processor of the system comprises one or more of executing the first task and the second task by the same core of the multi-core system and executing the first task and the second task by respective different cores of the multi-core system.

5. The method of claim 1 further comprising:

providing a plurality of task types having respective execution delay values; and

assigning one of the task types of the plurality of task types to each of the first, second and third tasks, wherein;

the first execution delay value corresponds to the execution delay value of the task type assigned to the first task;

the second execution delay value corresponds to the execution delay value of the task type assigned to the second task; and

the third execution delay value corresponds to the execution delay value of the task type assigned to the third task.

6. The method of claim 5 further comprising recording statistics in an execution table regarding times of execution of respective tasks by the at least one processor of the system in relation to the respective execution delay values of those respective tasks.

7. The method of claim 6 further comprising adjusting the execution delay values of one or more of the task types for new tasks queued in the queue of tasks based at least in part on the recorded statistics.

8. A system comprising:

memory;

at least one processor; and

computer program code that, when executed on the at least one processor, provides a task scheduler process configured to perform the operations of;

queuing a first task in a queue of tasks to be executed by at least one processor of the system, the first task having a first priority of execution time determined based at least in part on a first execution delay value associated with the first task;

queuing a second task in the queue of tasks, the second task having a second priority of execution time determined based at least in part on a second execution delay value associated with the second task, the second priority of execution time being earlier than the first priority of execution time;

queueing a third task in the queue of tasks, the third task having a third priority of execution time determined based at least in part on a third execution delay value associated with the third task, the third priority of execution time being earlier than the first priority of execution time and later than the second priority of execution time, wherein the time when the at least one processor of the system will execute each task is based at least in part on its respective priority of execution time, the respective priority of execution time of each task supplanting a priority associated with each task;

executing the first task by the at least one processor of the system, wherein the execution of the first task locks a resource on the system;

executing the second task by the at least one processor of the system, wherein the execution of the second task requires the resource on the system locked by the first task;

determining that the resource required for execution of the second task is locked by the first task;

responsive to determining that the resource required for execution of the second task is locked by the first task, promoting the first task having the first priority of execution time to a new priority of execution time at least as early as the second priority of execution time of the second task;

re-inserting the second task into the queue to wait for the first task to unlock the resource, the re-inserted second task having the second priority of execution time; and

continuing execution of the first task having the new priority of execution time by the at least one processor of the system, whereby promoting the first task having the first priority of execution time to the new priority of execution time at least as early as the second priority of execution time of the second task inhibits the third task having the third priority of execution time from executing and locking the resource prior to execution of the re-inserted second task having the second priority of execution time by the at least one processor of the system.

9. The system of claim 8 wherein executing the second task by the at least one processor of the system comprises preempting the first task having the first priority of execution time to begin execution by the at least one processor of the system of the second task having the second priority of execution time.

10. The system of claim 8 wherein the queue of tasks is configured to arrange the first, second and third tasks based at least in part on their respective priority of execution times.

11. The system of claim 8 wherein the system is a multi-core system and wherein executing the first task and the second task by the at least one processor of the system comprises one or more of executing the first task and the second task by the same core of the multi-core system and executing the first task and the second task by respective different cores of the multi-core system.

12. The system of claim 8 wherein the task scheduler process is further configured to perform the operations of:

providing a plurality of task types having respective execution delay values; and

assigning one of the task types of the plurality of task types to each of the first, second and third tasks, wherein;

the first execution delay value corresponds to the execution delay value of the task type assigned to the first task;

the second execution delay value corresponds to the execution delay value of the task type assigned to the second task; and

the third execution delay value corresponds to the execution delay value of the task type assigned to the third task.

13. The system of claim 12 wherein the task scheduler process is further configured to perform the operation of recording statistics in an execution table regarding times of execution of respective tasks by the at least one processor of the system in relation to the respective execution delay values of those respective tasks.

14. The system of claim 13 wherein the task scheduler process is further configured to perform the operation of adjusting the execution delay values of one or more of the task types for new tasks queued in the queue of tasks based at least in part on the recorded statistics.

15. A tangible non-transitory media having computer executable code encoded thereon that when executed by at least one processor of a system causes the at least one processor to provide a task scheduler process to manage the execution of tasks in a queue of tasks to be executed by the at least one processor of the system, the computer executable code comprising:

computer program code for queuing a first task in the queue of tasks, the first task having a first priority of execution time determined based at least in part on a first execution delay value associated with the first task;

computer program code for queuing a second task in the queue of tasks, the second task having a second priority of execution time determined based at least in part on a second execution delay value associated with the second task, the second priority of execution time being earlier than the first priority of execution time;

computer program code for queueing a third task in the queue of tasks, the third task having a third priority of execution time determined based at least in part on a third execution delay value associated with the third task, the third priority of execution time being earlier than the first priority of execution time and later than the second priority of execution time, wherein the time when the at least one processor of the system will execute each task is based at least in part on its respective priority of execution time, the respective priority of execution time of each task supplanting a priority associated with each task;

computer program code for executing the first task by the at least one processor of the system, wherein the execution of the first task locks a resource on the system;

computer program code for executing the second task by the at least one processor of the system, wherein the execution of the second task requires the resource on the system locked by the first task;

computer program code for determining that the resource required for execution of the second task is locked by the first task;

computer program code for promoting the first task having the first priority of execution time to a new priority of execution time at least as early as the second priority of execution time of the second task responsive to determining that the resource required for execution of the second task is locked by the first task;

computer program code for re-inserting the second task into the queue to wait for the first task to unlock the resource, the re-inserted second task having the second priority of execution time; and

computer program code for continuing execution of the first task having the new priority of execution time by the at least one processor of the system, whereby promoting the first task having the first priority of execution time to the new priority of execution time at least as early as the second priority of execution time of the second task inhibits the third task having the third priority of execution time from executing and locking the resource prior to execution of the re-inserted second task having the second priority of execution time by the at least one processor of the system.

16. The tangible non-transitory media of claim 15 wherein the computer executable code further comprises computer program code for executing the second task by the at least one processor of the system comprises preempting the first task having the first priority of execution time to begin execution by the at least one processor of the system of the second task having the second priority of execution time.

17. The tangible non-transitory media of claim 15 wherein the queue of tasks is configured to arrange the first, second and third tasks based at least in part on their respective priority of execution times.

18. The tangible non-transitory media of claim 15 wherein the system is a multi-core system and wherein executing the first task and the second task by the at least one processor of the system comprises one or more of executing the first task and the second task by the same core of the multi-core system and executing the first task and the second task by respective different cores of the multi-core system.

19. The tangible non-transitory media of claim 15 wherein the computer executable code further comprises computer program code for:

providing a plurality of task types having respective execution delay values; and

assigning one of the task types of the plurality of task types to each of the first, second and third tasks, wherein;

the first execution delay value corresponds to the execution delay value of the task type assigned to the first task;

the second execution delay value corresponds to the execution delay value of the task type assigned to the second task; and

the third execution delay value corresponds to the execution delay value of the task type assigned to the third task.

20. The tangible non-transitory media of claim 19 wherein the computer executable code further comprises computer program code for recording statistics in an execution table regarding times of execution of respective tasks by the at least one processor of the system in relation to the respective execution delay values of those respective tasks.

21. The tangible non-transitory media of claim 20 wherein the computer executable code further comprises computer program code for adjusting the execution delay values of one or more of the task types for new tasks queued in the queue of tasks based at least in part on the recorded statistics.