Introduction to Static Scheduling
This material corresponds to the first few sections in
Chapter 5 of Jane Liu's book.
Warning: Chapter 4 presents scheduling
concepts initially in terms of scheduling a single batch of jobs,
rather than the periodic or other recurring arrival patterns that
are typical of real-time systems. That is, the text glosses over
the distinction between a situation with a fixed finite set of
jobs and situations where there is an unbounded stream of jobs.
The algorithms generaly can be applied in both kinds of context,
but the schedulability analysis may be different.
Clock-driven scheduling overview
- a schedule of jobs is computed off-line
- all scheduling decisions are made a priori
- schedule is static, finite
(but generally is applied cyclically)
- the run-time scheduler is driven by a hardware timer
and simply follows this schedule
Variations
- Simple cyclic executive:
- periodic timer drives interrupt
- time divided into equal-sized frames
- frame boundaries enforce release times, detect missed deadlines and overruns
- usually, non-preemptive
- Preemptive clock-driven executive:
- programmed interval timer drives interrupt
- frames can be arbitrary in size
- more likely to be preemptive
Example: static schedules for two periodic tasks
Fitting in aperiodics
Jobs are queued and executed
- One option: run them during idle times
- easy to implement
- aperiodic response time may be poort
- Other options:
- reserve some frames for aperiodics
- slack stealing
Pro's of static scheduling
there is minimal runtime overhead
behavior is completely predictable
some variation can be accomodated using multiple tables
which apply to different operational modes of the system
it can be applied to handle multiple resource constraints (not just CPU time)
can eliminate mutual exclusion problems (if non-preemptive)
it can be applied to complex variations of the periodic model, including
complex jobs with precedence constraints
it can be optimized off-line, when execution time is not at a premium
Con's of static scheduling
- finding a schedule can be complex (NP-hard, in general)
- fragile:
- sensitive at run time to task execution time variations
- small changes to task parameters can break schedule, possibly even
make system unschedulable
- designs are constrained
- CPU time can be wasted due to over-reservation
(similar to internal fragmentation effect with memory allocation)