1. Suppose that the first sporadic job S1(0 , 8, 2) is released shortly after time 0. Since the density of S1 is only 0.25, the scheduler accepts it. The deadline 8 of S1 divides the future time into two intervals: I1 = (0 , 8] and I2 = (8,∞). The scheduler updates the total densities of active sporadic jobs in these intervals: s,1 = 0.25 and s,2 = 0. The scheduler then inserts S1 into the queue of ready periodic and sporadic jobs in the EDF order.
2. At time 2, the second sporadic job S2(2, 7, 0.5) with density 0.1 is released. Its deadline 7 is in I1. Since the condition 0.1 0.25 ≤ 0.5 defined by Eq. (7.11) is satisfied, the scheduler accepts and schedules S2. We now call the interval I2 I3. The interval I1 is divided into I1 = (2, 7] and I2 = (7, 8]. The scheduler increments the total density s,1 by the density of S2. Now, Δs,1 = 0.35, Δs,2 = 0.25, and Δs,3 = 0.
3. At time 4, S3(4, 14, 1) is released. S2 has already completed. The only sporadic job in the system is S1. Δs,1 = 0.25 (for interval I1 before 8) and Δs,2 = 0 (for interval I2 after 8). The deadline of S3 is in the interval I2. The conditions the scheduler checks are whether 0.25 0.1 and 0.1 are equal to or less than 0.5. Since both are satisfied, the scheduler accepts S3. The intervals maintained by the scheduler are now I1 = (4, 8], I2 = (8, 14], and I3 = (14,∞]. Moreover, Δs,i are 0.35, 0.1, and 0 for i = 1, 2, and 3, respectively.
4. At time 9, S4(9, 13, 2) is released. Now, the only active sporadic job in the system is S3. I1 is (9, 14] and I2 is (14,∞). Since for I1, the total density of existing active sporadic jobs is 0.1 and the density of S4 is 0.5, their sum exceeds 0.5. Consequently, the scheduler rejects S4.
Enhancements and Generalization. Two points are worthy of observing. First, the acceptance test is not optimal, meaning that a sporadic job may be rejected while it is schedulable. The reason is that the schedulability condition given by Theorem 7.4 is sufficient but not necessary. In the example above, the system becomes idle at time 9.5 and does not become busy again until time 12. So, S4 is acceptable. In fact, as we will see shortly, it would be acceptable even if its execution time were 4.0, making its density 1.0! An enhancement is to have the scheduler also compute the slack of the system. In this example, suppose that the scheduler were to compute the slack of the system dynamically at time 9. It would find that the current busy interval of the periodic tasks and accepted sporadic jobs ends at time 9.5 and the next busy interval does not begin until time 12. This leaves the system with 2.5 units of slack before time 13, the deadline of S4. Hence, S4 is acceptable. The shortcoming of an acceptance test that makes use of dynamic-slack computation is its high run-time overhead. The next subsection describes an optimal acceptance test algorithm that makes use of static-slack computation. According to that test, S4 would be acceptable as long as its execution time is no more than 4. However, that acceptance test can be used only when periodic tasks have little or no release-time jitters.
The second point worth noting is that the acceptance test described above assumes that every sporadic job is ready for execution upon its arrival. In general, its feasible interval may begin some time after its acceptance test time. (As an example, suppose that that S3 in the above example were offered to the scheduler for acceptance testing at time 3, but it is ready for execution at time 4.) We can modify the simple acceptance test in a straightforward fashion to accommodate arbitrary ready times of sporadic jobs. The ready times and deadlines of sporadic jobs in the system partition the future time into disjoint time intervals. The scheduler maintains information on these intervals and the total densities of active sporadic jobs in them in a similar manner, but now it may have to maintain as many as 2Ns 1 intervals, where Ns is the maximum number of sporadic jobs in the system.
