Priority Driven Scheduling of Aperiodic and Sporadic Tasks

Priority Driven Scheduling of Aperiodic and Sporadic Tasks

Assumptions and approaches

1. Single processors system with independent preemptable periodic task, which are scheduled using a priority driven algorithm:- (i) The parameters of all periodic tasks are known. (ii) In the absence of aperiodic and sporadic jobs, the periodic jobs meet deadlines.
2. Aperiodic and sporadic jobs may exist and they are independent of each other and of the periodic task. They can be preempted at any time.
3. The parameters of sporadic jobs become known after they are released.
4. Some sporadic jobs may not be possible to meet their deadlines.

Therefore, either reject the sporadic jobs that cannot complete in time or accept all sporadic jobs and allow some of them to complete late.

Objective, Correctness of Optimality

The operating system maintains priority queue of periodic, aperiodic and sporadic jobs. Acceptance jobs are placed into priority queue and each type of job is queued separately with queuing discipline as shown in the figure of system model below.

The scheduler selects the job at the head of the queue and provides to the processor in order to execute it.

The scheduling problems associated with the execution of a sporadic jobs is related with a determination of when aperiodic and sporadic jobs are executed. Based on the execution time and deadline of each newly arrived sporadic job, we can decide whether to accept or reject the job. Accepting the job means that the job will complete within the deadline without causing any aperiodic task or other sporadic task to missed their deadline.

The problem is also related with how to do acceptance test and how to schedule accepted jobs. For this, the aperiodic jobs are always accepted and executed as soon as possible without causing periodic jobs and accepted sporadic jobs to miss their deadlines.

Correctness

The correct schedule is one where all periodic tasks and any sporadic tasks that have been accepted do not miss deadlines. A scheduling algorithm supporting aperiodic and sporadic jobs is a correct algorithm if it only produces correct schedules for the system.

Optimality

If the queuing discipline used to order aperiodic jobs is given then an aperiodic job scheduling algorithm is optimal if it minimizes either.

1. The response time of the job at the of the aperiodic job queue or
2. The average response time of all aperiodic jobs for a given queuing discipline.

A sporadic job scheduling algorithm is optimal if it accepts a new sporadic job and schedules that job to complete y its deadline if and only if the new job can be correctly scheduled to complete in time. An optimal algorithm always produces a feasible schedule for the accepted jobs.

Deferrable Server

A deferrable server is the simplest of bandwidth-preserving servers. The deferrable server can be described based on consumption and replenishment rules that define the deferrable server (P_s, e_s).

The consumption rule is,

• The execution budget of the server is consumed at the rate of one per unit time whenever the server executes.

The replenishment rule is,

• The execution budget of the server is set to e_s at time instances kp_k for k = 0, 1, 2, . . . . . .

In the deferrable server, the budget is not allowed to cumulate from period to period. It means the budget is held by the server immediately before each replenishment time is lost.

Consider, a deferrable server T_DS (3, 1), T₁ = (2, 3.5, 1.5) and T₂ = (6.5, 0.5). These tasks are scheduled rate monotonically. Also, consider that aperiodic job A occur at t = 2.8 and its execution time is 1.7.

1. At time 0, the server is given 1 unit of budget. The budget stays at 1 until time 2.8. When A arrives, the deferrable server executes the job. Its budget decreases as it executes.
2. Immediately before the replenishment time 3.0, its budget is equal to 0.8. This 0.8 unit is lost at time 3.0, but the server acquires a new unit of budget. Hence, the server continues to execute.
3. At time 4.0, its budget is exhausted. The server is suspended, and the aperiodic job A waits.
4. At time 6.0, its budget replenished, the server resumes to execute A.
5. At time 6.5, job A completes. The server still has 0.5 unit of budget. Since no aperiodic job waits in the queue, the server suspends itself holding this budget

Sporadic Server

Definition:

T_H is the subset of periodic tasks with higher priorities than the server.

t_r is the lost time the servet budget replenished.

t_f is the first instant after tr at which the server begins to execute

t_e is the last effective replenishment time

1. BEGIN as the start of earliest busy interval in the most recent contiguous sequence of busy intervals of T_H starting before t.
2. END as the end of the last busy interval in this sequence if this interval ends before t and define END = ∞ if the interval ends after t.

Sporadic Server in Fixed-Priority Systems

The rules includes the following.

Consumption rule:

At any time t after t_r, if the server has budget and if either of the following two conditions is true, the server budget is consumed at the rate of one per unit time.

Condition 1 (C1): the server is executive.

Condition 2 (C2): the server has executed.

Replenishment Rule:

There are three rules:

R1: When the system begins executing and each time budget is replenished, set the budget to e_s and t_r = current time.

R2: When the server begins to execute,

if END = t_f, then

t_e = max(t_r, BEGIN)

else if END < t_f then t_e = t_f

the next replenishment time is set to t_e + P_s.

R3: The next replenishment occurs at the next replenishment time (te + Ps) except under the following conditions

1. If t_e + P_s is earlier than t_f, the budget is replenished as soon as it is exhausted.
2. If T becomes idle before t_e + P_S and becomes busy again at t_b, the budget is replenished at min(t_e + p_s, t_b).

Consider, the budget of the server (5,1.5) is 1.5 initially. It is scheduled rate-monotonically with three periodic tasks: T1 = (3, 0.5), T2 = (4, 1.0), and T3 = (19, 4.5). They are schedulable even when the aperiodic job queue is busy all the time.

1. From time 0 to 3, the aperiodic job queue is empty and the server is suspended. Since it has not executed, its budget stays at 1.5. At time 3, the aperiodic job A₁ with execution time 1.0 arrives; the server becomes ready. Since the higher-priority task (3, 0.5) has a job ready for execution, the server and the aperiodic job wait.
2. The server does not begin to execute until time 3.5. At the time, t_r is 0, BEGIN is equal to 3, and END is equal to 3.5. According to rule R2, the effective replenishment time t_e is equal to max(0, 3.0) = 3, and the next replenishment time is set at 8.
3. The server executes until time 4; while it executes, its budget decreases with time.
4. At time 4, the server is preempted by T₂. While it is preempted, it holds on to its budget.
5. After the server resumes execution at 5, its budget is consumed until exhaustion because it executes (C1) and then, when it is suspended again, T1 and T2 are idle (or equivalently, END, which is 5.0, is less than the current time) (C2).
6. When the aperiodic job A₂ arrives at time 7, the budget of the server is exhausted; the job waits in the queue.
7. At time 8, its budget replenished (R3), the server is ready for execution again.
8. At time 9.5, the server begins to execute for the time since 8. t_e is equal to the latest replenishment time 8. Hence the next replenishment time is 13. The server executes until its budget is exhausted at 11; it is suspended and waits for the next replenishment time. In the meantime, A₂ waits in the queue.
9. Its budget replenished at time 13, the server is again scheduled and begins to execute at time 13.5. This time, the next replenishment time is set at 18. However at 13.5, the periodic task system T becomes idle. Rather than 18, the budget is replenished at 15, when a new busy interval of T begins, according to rule R3b.
10. The behavior of the later segment also obeys the above-stated rules. In particular, rule R3b allows the server budget to be replenished at 19. (Liu 205-207)

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.