Simple Sporadic Servers In Deadline-driven Systems

Simple Sporadic Servers in Deadline-Driven Systems: When the periodic tasks are scheduled on the EDF basis, the priorities of the tasks vary as their jobs are released and completed. Consequently, the membership of the subset of tasks with higher priorities than the server varies with time. Some of the rules of simple sporadic servers stated earlier for fixed-priority systems must be modified for this reason. The rationales behind the modified rules remain the same: a simple sporadic server of period ps and budget es following the rules behave like a periodic task (ps , es).

The consumption and replenishment rules of simple sporadic servers in a system where all tasks are scheduled according to the EDF algorithm are stated below. We again use tr to denote the latest replenishment time. However the notation te, the effective latest replenishment time, has a different meaning from that of a fixed-priority sporadic server. Specifically, rule R2 below governs how the value of te is determined. The server is ready for execution only when it is backlogged (i.e., the aperiodic job queue is nonempty) and its deadline d (and hence its priority) is set. The server is suspended whenever its deadline is undefined or when the server is idle (i.e., the aperiodic job queue becomes empty).

Consumption Rules of Simple Deadline-Driven Sporadic Server: The server’s execution budget is consumed at the rate of one per unit time until the budget is exhausted when either one of the following two conditions is true. When these conditions are not true, the server holds its budget.
C1 The server is executing.
C2 The server deadline d is defined, the server is idle, and there is no job with a deadline before d ready for execution.

Replenishment Rules of Simple Deadline-Driven Sporadic Server:
R1 Initially and at each replenishment time, tr is the current time, and the budget = es . Initially, te and the server deadline d are undefined.
R2 Whenever te is defined, d = te ps , and the next replenishment time is te ps . Otherwise, when te is undefined, d remains undefined. te is determined (defined) as follows:

(a) At time t when an aperiodic job arrives at an empty aperiodic job queue, the value of te is determined based on the history of the system before t as follows:
i. If only jobs with deadlines earlier than tr ps have executed throughout the interval (tr , t), te = tr .
ii. If some job with deadline after tr ps has executed in the interval (tr , t), te = t .

(b) At replenishment time tr ,
i. if the server is backlogged, te = tr, and
ii. if the server is idle, te and d become undefined.
R3 The next replenishment occurs at the next replenishment time, except under the following conditions. Under these conditions, the next replenishment is done at times stated below.

(a) If the next replenishment time te ps is earlier than the time t when the server first becomes backlogged since tr , the budget is replenished as soon as it is exhausted.
(b) The budget is replenished at the end of each idle interval of the periodic task system T.

As you can see, the differences in rules of simple sporadic servers in deadline-driven and fixed-priority systems are small. It just so happens that if we schedule the periodic tasks in Figure 7–8 according to the EDF algorithm and make the sporadic server follow the rules of deadline-driven simple sporadic servers, the schedule segment we get is essentially the same as the one shown in the figure. The possible differences may arise if when the server has the same priority as the periodic tasks, we alway break the tie in favor of the server. Like SpSL servers, a deadline-driven sporadic server proposed by Ghazalie and Baker [GhBa], which we call a GhBa server, also consumes and replenishes its budget in chunks.

The consumption and replenishment rules of GhBa servers are given in Problem 7.13. Unlike the rules of SpSL servers given in [SpSL], these rules do ensure that each chunk is never replenished sooner than one server period since its last replenishment. Consequently, lowerpriority jobs never miss their deadlines because the server takes too much time. The rules of GhBa servers are somewhat more complex than the rules of simple deadline-driven sporadic servers. Both kinds of servers are considerably more complex than the constant utilization, total bandwidth, and weighted fair-queueing servers described in the next section.