Credit scheduler for ordering the execution of tasks
A method for scheduling the execution of tasks on a processor is disclosed. The purpose of the method is in part to serve the special needs of soft real-time tasks, which are time-sensitive. A parameter Δ is an estimate of the amount of time required to execute the task. Another parameter Γ is the maximum amount of time that the task is to spend in a queue before being executed. In the illustrative embodiment, the preferred wait time Γ i for a newly-arrived task T i is expected to be met though the insertion of the newly-arrived task T i into a position k in a queue such that position k respects the task's preferred wait time Γ i in light of the expected execution times of the other tasks already in the queue.
1. A method comprising:
receiving at time t i at a queue for execution on a processor a first task T 1 , wherein the first task T 1 has a first estimated execution time Δ i , and a first preferred wait time Γ i , and wherein the queue comprises at least one other task with a position j and an estimated execution time Δ j ;
receiving at time t 2 at the queue for execution on the processor a second task T 2 for execution on the processor, wherein time t i is before time t 2 , and wherein the second task T 2 has a second estimated execution time Δ m and a second preferred wait time Γ 2 ;
inserting the first task T 1 into the queue at a position k, wherein j≦k, such that:
Γ
i
≥
Δ
m
+
∑
j
=
1
k
-
1
Δ
j
and
Γ
i
<
Δ
m
+
∑
j
=
1
k
Δ
j
;
and
executing the second task T 2 on the processor before executing the first task T 1 when Γ 2 <Δ i ,
wherein j=1 represents the position at the head of the queue.
2. The method of claim 1 wherein the first task T i is a time-sensitive task.
3. The method of claim 1 wherein the position k is independent of the first estimated execution time Δ i .
4. The method of claim 1 wherein a time-sensitive domain comprises the first task T 1 .
5. The method of claim 1 further comprising: executing on the processor the task at the head of the queue with the position j=1.
6. The method of claim 5 wherein the first task T 1 is a time-sensitive task.
7. The method of claim 6 wherein the position k is independent of the first estimated execution time Δ i .
8. The method of claim 5 wherein a time-sensitive domain comprises the first task T 1 .
9. The method of claim 8 wherein the position k is independent of the first estimated execution time Δ i .
10. The method of claim 1 wherein the second task T 2 is a time-sensitive task.
11. The method of claim 10 wherein the order of execution of the first task T 1 and the second task T 2 is independent of the second estimated execution time Δ 2 .
12. The method of claim 1 wherein a time-sensitive domain comprises the second task T 2 .
13. The method of claim 12 wherein the order of execution of the first task T 1 and the second task T 2 is independent of the second estimated execution time Δ 2 .
14. A method comprising:
receiving at a queue for execution on a processor a first task T i , wherein the first task T i has a first estimated execution time Δ i and a first preferred wait time Γ i , and wherein the queue comprises at least one other task with a position j and an estimated execution time Δ j ;
inserting the first task T i into the queue at a position k, wherein j≦k, such that:
Γ
i
≥
∑
j
=
1
k
-
1
Δ
j
and
Γ
i
<
∑
j
=
1
k
Δ
j
,
wherein j=1 represents the position at the head of the queue; and
executing the first task T i on the processor before executing a second task T n when Γ i <Δ n ,
wherein the first task T i , was received at the queue after the second task T n , and wherein the second task T n has a second estimated execution time Δ n .
15. The method of claim 14 wherein the first task T i , is a time-sensitive task.
16. The method of claim 15 wherein the order of execution of the first task T i , and the second task T n is independent of the first estimated execution time Δ i .
17. The method of claim 14 wherein a time-sensitive domain comprises the first task T i .
18. The method of claim 17 wherein the order of execution of the first task T i , and the second task T n is independent of the first estimated execution time Δ i .