When sporadic jobs arrive, they are both accepted and scheduled in EDF order
- In a dynamic-priority system, this is the natural order of execution
- In a fixed-priority system, the sporadic jobs are executed by a bandwidth preserving server, which performs an acceptance test and runs the sporadic jobs in EDF order
- In both cases, no new scheduling algorithm is required Definitions: –
- Sporadic jobs are denoted by Si(ri, di, ei) where ri is the release time, di is the (absolute) deadline, and ei is the maximum execution time
- The density of a sporadic job Δi =ei/(di –ri) The total density of a system of n jobs is Δ
=Δ1 +Δ2 + … +Δn
- The job is active during its feasible interval (ri,di ]
Sporadic Jobs in Dynamic Priority System:
Theorem:
A system of independent preemptable sporadic jobs is schedulable according to the EDF algorithm if the total density of all active jobs in the system ≤ 1 at all times.
- This is the standard schedulability test for EDF systems, but including both periodic and sporadic jobs.
- This test uses the density since deadlines may not equal periods; hence it is a sufficient test, but not a necessary test.
This means:
- If we can bound the frequency with which sporadic jobs appear to the running system, we can guarantee that none are missed.
- Alternatively, when a sporadic job arrives, if we deduce that the total density would exceed 1 in its feasible interval, we reject the sporadic job.