Uniprocessor schedulability testing for non-preemptive task sets

Patent metadata

Field	Value
Publication number	US-9766931-B2
Application number	US-201313873541-A
Country	US
Kind code	B2
Filing date	Apr 30, 2013
Priority date	Apr 30, 2012
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

A method of determining schedulability of tasks for uniprocessor execution includes defining a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. A determination of whether the task set is schedulable is made, such that a near-optimal amount of temporal resources required to execute the task set is estimated. Further, a method of determining schedulability of a subtask for uniprocessor execution includes defining a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. A determination of whether a subtask in the task set is schedulable at a specific time is made in polynomial time. Systems for implementing such methods are also provided.

First claim

We claim:

1. In a system comprising at least one computer having at least one memory storing computer-executable instructions, a method of determining schedulability of tasks for uniprocessor execution, the method comprising:
executing the instructions by at least one processing unit, the execution of the instructions resulting in the at least one computer performing the steps of:
receiving a well-formed, non-preemptive task set comprising a plurality of tasks, each task having a period and at least one subtask, wherein the task set is designated for execution by a uniprocessor;
performing a schedulability test on the task set by:
constructing, from the task set, a task superset defining relationships among subtasks of tasks in the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
calculating an upper bound on temporal resources required to execute the task superset; and
determining whether the task set is schedulable based on whether the upper bound exceeds a hyperperiod of the task set, wherein the hyperperiod of the task set comprises a sum of the periods of the tasks in the task set; and

upon determining that the task set is schedulable, configuring the uniprocessor to perform the tasks in the task set according to a schedule.

2. The method of claim 1 , wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

3. The method of claim 2 , wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

4. The method of claim 3 , wherein the intra-task deadline constraint comprises a hard constraint.

5. The method of claim 1 , wherein a first one of the tasks in the task set has a first number of subtasks and a second one of the tasks in the task set has a second number of subtasks, the second number of subtasks being different from the first number of subtasks.

6. The method of claim 5 , wherein the number of subtasks in each task in the task set is independent of the number of subtasks in each of the other tasks in the task set.

7. The method of claim 1 , wherein the schedulability test is performed in polynomial time.

8. The method of claim 1 , wherein the execution of the instructions further results in the at least one computer performing the step of determining in polynomial time whether a subtask in the task set is schedulable at a specific time.

9. The method of claim 1 , wherein the plurality of instances of a corresponding task in the task set comprises a number of instances equal to the hyperperiod of the task set divided by a period of the corresponding task in the task set.

10. A system for determining schedulability of tasks for uniprocessor execution, the system comprising:
at least one memory storing computer-executable instructions; and
at least one processing unit for executing the instructions, wherein execution of the instructions causes the at least one processing unit to:
receive a well-formed, non-preemptive task set comprising a plurality of tasks, each task having a period and at least one subtask, wherein the task set is designated for execution by a uniprocessor;
perform a schedulability test on the task set by:
constructing, from the task set, a task superset defining relationships among subtasks of tasks in the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
calculating an upper bound on temporal resources required to execute the task superset; and
determining whether the task set is schedulable based on whether the upper bound exceeds a hyperperiod of the task set, wherein the hyperperiod of the task set comprises a sum of the periods of the tasks in the task set; and

upon determining that the task set is schedulable, configure the uniprocessor to perform the tasks in the task set according to a schedule.

11. The system of claim 10 , wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

12. The system of claim 11 , wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

13. The system of claim 12 , wherein the intra-task deadline constraint comprises a hard constraint.

14. The system of claim 10 , wherein a first one of the tasks in the task set has a first number of subtasks and a second one of the tasks in the task set has a second number of subtasks, the second number of subtasks being different from the first number of subtasks.

15. The system of claim 14 , wherein the number of subtasks in each task in the task set is independent of the number of subtasks in each of the other tasks in the task set.

16. The system of claim 10 , wherein the at least one processing unit, in executing the instructions, is configured to perform the schedulability test in polynomial time.

17. The system of claim 10 , wherein the execution of the instructions further causes the at least one processing unit to determine in polynomial time whether a subtask in the task set is schedulable at a specific time.

18. In a system comprising at least one computer having at least one memory storing computer-executable instructions, a method of determining schedulability of a subtask for uniprocessor execution, the method comprising:
executing the instructions by at least one processing unit, the execution of the instructions resulting in the at least one computer performing the steps of:
receiving a well-formed, non-preemptive task set comprising a plurality of tasks, each task having at least one subtask, wherein the task set is designated for execution by a uniprocessor;
determining whether the task set can be scheduled according to a particular scheduling policy given constraints relating particular tasks in the task set to each other by calculating an upper bound on temporal resources required to execute a task superset constructed from the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
generating a schedule for the task set using the particular scheduling policy, the generating comprising determining in polynomial time whether a particular subtask in the task set is schedulable at a specific time; and
upon determining that the task set can be scheduled, configuring a uniprocessor to perform the tasks in the task set according to the schedule.

19. The method of claim 18 , wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

20. The method of claim 19 , wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

21. The method of claim 19 , wherein the determination of whether the particular subtask in the task set is schedulable is based at least in part on an intra-task deadline constraint of at least one other task in the task set.

22. The method of claim 18 , wherein the determination of whether the particular subtask in the task set is schedulable comprises determining whether a first subtask g

Assignees

• Massachusetts Inst Technology

Inventors

• Shah Julie Ann
• Gombolay Matthew Craig

Classifications

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title