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.