Scheduling Of Sporading Jobs
Acceptance tests are performed on sporadic jobs in the EDF order. Once accepted, sporadic jobs are ordered among themselves in the EDF order. In a deadline-driven system, they are scheduled with periodic jobs on the EDF basis. In a fixed-priority system, they are executed by a bandwidth preserving server. In both cases, no new scheduling algorithm is needed.
A Simple Acceptance Test in Deadline-Driven Systems
Theorem 7.4 says that in a deadline-driven system where the total density of all the periodic tasks is , all the accepted sporadic jobs can meet their deadlines as long as the total density of all the active sporadic jobs is no greater than 1− at all times. This fact gives us a theoretical basis of a very simple acceptance test in a system where both the periodic and sporadic jobs are scheduled on the EDF basis.
Acceptance Test Procedure. The acceptance test on the first sporadic job S(t, d, e) is simple indeed. The scheduler accepts S if its density e/(d − t) is no greater than 1 − . If the scheduler accepts the job, the (absolute) deadline d of S divides the time after t into two disjoint time intervals: the interval I1 at and before d and the interval I2 after d. The job S is active in the former but not in the latter. Consequently, the total densities s,1 and s,2 of the active sporadic jobs in these two intervals are equal to e/(d − t) and 0, respectively.
We now consider the general case. At time t when the scheduler does an acceptance test on S(t, d, e), there are ns active sporadic jobs in the system. For the purpose of scheduling them and supporting the acceptance test, the scheduler maintains a nondecreasing list of (absolute) deadlines of these sporadic jobs. These deadlines partition the time interval from t to the infinity into ns 1 disjoint intervals: I1, I2, . . . , Ins 1. I1 begins at t and ends at the first (i.e., the earliest) deadline in the list. For 1 ≤ k ≤ ns , each subsequent interval Ik 1 begins when the previous interval Ik ends and ends at the next deadline in the list or, in the case of Ins 1, at infinity. (Some of these intervals have zero length when the sporadic jobs have nondistinct deadlines.) The scheduler also keeps up-to-date the total density s,k of the sporadic jobs that are active during each of these intervals.
Let Il be the time interval containing the deadline d of the new sporadic job S(t, d, e). Based on Theorem 7.4, the scheduler accepts the job S if
for all k = 1, 2, . . . l.
If these conditions are satisfied and S is accepted, the scheduler divides the interval Il into two intervals: The first half of Il ends at d, and the second half of Il begins immediately after d.We now call the second half Il 1 and rename the subsequent intervals Il 2, . . . , Ins 2. (Here, we rename the intervals for the sake of clarity. In the actual implementation of the acceptance test, this step is not necessary provided some appropriate data structure is used to allow efficient insertion and deletion of the intervals and update of the total densities associated with individual intervals.) The scheduler increments the total density s,k of all active sporadic jobs in each of the intervals I1, I2, . . . , Il by the density e/(d − t) of the new job. Thus, the scheduler becomes ready again to carry out another acceptance test. The complexity of this acceptance test is O(Ns) where Ns is the maximum number of sporadic jobs that can possibly be in the system at the same time.
As an example, we consider a deadline-driven system in Figure 7–21. The system has two periodic tasks T1 = (4, 1) and T2 = (6, 1.5). The relative deadline of each task is equal to the period of the task. Their total density is 0.5, leaving a total density of 0.5 for sporadic jobs.
