Method for determining earliest deadline first schedulability of non-preemptive uni-processor system

Patent metadata

Field	Value
Publication number	US-10296382-B2
Application number	US-201715598055-A
Country	US
Kind code	B2
Filing date	May 17, 2017
Priority date	May 17, 2017
Publication date	May 21, 2019
Grant date	May 21, 2019

Abstract

Earliest deadline first (EDF) scheduling algorithm is the most celebrated result for dynamic priority scheduling in real-time systems for both preemptive and non-preemptive cases. From complexity point of view, EDF is polynomial for preemptive scheduling of tasks. However, it becomes pseudo-polynomial under non-preemptive case. Described herein is a technique that determines EDF feasibility of non-preemptive task set by analyzing schedulability of the lowest priority task at common scheduling points generated by all higher priority tasks in the task set. The adjustment results in improving the computational cost of an existing test from O(n 2 p n /p 1 ) to O(p n /p 1 ), where n is the number of tasks in the system, while pn and p1 represent the task periods of largest and smallest periodic tasks respectively. With reduced computation cost, the described method of analyzing feasibility can be intergraded with online systems for testing feasibility of a special class of real-time systems under non-preemptive case.

First claim

The invention claimed is:

1. A method for determining feasibility of a set of non-preemptive tasks that is to be executed on a single processor, the method comprising:
receiving by circuitry, the set of non-preemptive tasks, each task being characterized by a task period that corresponds to a time-interval between successive occurrence of the task, a task deadline corresponding to a time by which the task is to be executed, and a task execution time, each task of the set of non-preemptive tasks having a unique task period;
sorting by circuitry, in an ascending manner, the received set of non-preemptive tasks based on the task period of each task;
generating, for each task of the set of non-preemptive tasks, a corresponding set of scheduling points, each set of scheduling points corresponding to time instances at which the respective task can be executed, and wherein each set of scheduling points has a unique magnitude;
determining by circuitry, a feasibility of the received task set, by determining whether the received task set satisfies a first condition and a second condition, the first condition corresponding to a utilization of the single processor being less than equal to one, and the second condition corresponding to verifying whether a lowest priority task is schedulable at its associated set of scheduling points; and
executing the set of non-preemptive tasks on the single processor based on the set of non-preemptive tasks being determined as being feasible.

2. The method of claim 1 , wherein a time complexity of determining whether the set of non-preemptive tasks is feasible is based on a ratio of a first period of the first task in the sorted task set, and a last period of a last task in the sorted task set.

3. The method of claim 1 , wherein each sorted task is assigned a unique priority that is based on the period of the task.

4. The method of claim 1 , wherein the set of scheduling points corresponding to the respective tasks of the non-preemptive task set includes at least one scheduling point in common.

5. The method of claim 1 , further comprising:
computing by circuitry, at a given time instant, a workload associated with each task, the computed workload being based on the respective task and higher priority tasks.

6. The method of claim 5 , wherein the workload for each task is computed as:
w i ( t )=Σ k=I i t/p k c k ,

wherein t corresponds to the time instant at which the workload is computed, p k corresponds to period of the task and c k corresponds to a deadline of the task.

7. A device for determining feasibility of a set of non-preemptive tasks that is to be executed on a single processor, the device comprising:
circuitry configured to
receive the set of non-preemptive tasks, each task being characterized by a task period that corresponds to a time-interval between successive occurrence of the task, a task deadline corresponding to a time by which the task is to be executed, and a task execution time, each task of the set of non-preemptive tasks having a unique task period;
sort in an ascending manner, the received set of non-preemptive tasks based on the task period of each task;
generate, for each task of the set of non-preemptive tasks, a corresponding set of scheduling points, each set of scheduling points corresponding to time instances at which the respective task can be executed, and wherein each set of scheduling points has a unique magnitude;
determine a feasibility of the received task set, by determining whether the received task set satisfies a first condition and a second condition, the first condition corresponding to a utilization of the single processor being less than equal to one, and the second condition corresponding to verifying whether a lowest priority task is schedulable at its associated set of scheduling points; and
execute the set of non-preemptive tasks on the single processor based on the set of non-preemptive tasks being determined as being feasible.

8. The device of claim 7 , wherein a time complexity of determining whether the set of non-preemptive tasks is feasible is based on a ratio of a first period of the first task in the sorted task set, and a last period of a last task in the sorted task set.

9. The device of claim 7 , wherein each sorted task is assigned a unique priority that is based on the period of the task.

10. The device of claim 7 , wherein the set of scheduling points corresponding to the respective tasks of the non-preemptive task set includes at least one scheduling point in common.

11. The device of claim 7 , wherein the circuitry is further configured to compute at a given time instant, a workload associated with each task, the computed workload being based on the respective task and higher priority tasks.

12. The device of claim 7 , wherein the workload for each task is computed as:
w i ( t )=Σ k=1 i t/p k c k ,

wherein t corresponds to the time instant at which the workload is computed, p k corresponds to period of the task and c k corresponds to a deadline of the task.

13. A non-transitory computer-readable medium including executable instructions, which when executed by circuitry, cause the circuitry to execute a method for determining feasibility of a set of non-preemptive tasks that is to be executed on a single processor, the method comprising:
receiving the set of non-preemptive tasks, each task being characterized by a task period that corresponds to a time-interval between successive occurrence of the task, a task deadline corresponding to a time by which the task is to be executed, and a task execution time, each task of the set of non-preemptive tasks having a unique task period;
sorting in an ascending manner, the received set of non-preemptive tasks based on the task period of each task;
generating, for each task of the set of non-preemptive tasks, a corresponding set of scheduling points, each set of scheduling points corresponding to time instances at which the respective task can be executed, and wherein each set of scheduling points has a unique magnitude;
determining a feasibility of the received task set, by determining whether the received task set satisfies a first condition and a second condition, the first condition corresponding to a utilization of the single processor being less than equal to one, and the second condition corresponding to verifying whether a lowest priority task is schedulable at its associated set of scheduling points; and
executing the set of non-preemptive tasks on the single processor based on the set of non-preemptive tasks being determined as being feasible.

14. The non-transitory computer readable medium of claim 13 , wherein a time complexity of determining whether the set of non-preemptive tasks is feasible is based on a ratio of a first period of the first task in the sorted task set, and a last period of a last task in the sorted task set.

15. The non-transitory computer readable medium of claim 13 , wherein each sorted task is assigned a unique priority that is based on the period of the task.

16. The non-transitory computer readable medium of claim 13 , wherein the set of scheduling points corresponding to the respective tasks of the non-preemptive task set includes at least one scheduling point in common.

17. The non-transitory computer readable medium of claim 13 , further comprising:
computing by circuitry, at a given time instant, a workload associated with each task, the computed workload being based on the respective task and higher priority tasks.

18. The non

Assignees

• Univ Imam Abdulrahman Bin Faisal

Inventors

• Alrashed Saleh
• Alhiyafi Jamal
• Shafi Aamir
• Min Allah Nasro

Classifications

• G06F9/4887 Primary

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

• G06F9/4831

  with variable priority · CPC title