Introduction to Real-Time Scheduling

Three Practical Approaches to Real-Time Scheduling

• clock-driven
• weighted round-robin
• priority-driven

Warning: Chapter 4 of the text 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
• 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

Examples of Static Scheduling

This is just an introduction to the idea of static scheduling. Later in the courses we will look deeper into the art of building a static schedule, and its advantages and disadvantages, if there is time.

Weighted RR Scheduling Overview

• job executions are interleaved
• jobs are kept on a FIFO queue
• when the top job has used one time slice it goes around
  to the end of the queue
• can approximate n processors
• time slices may vary
  simulating processors of different speeds
• delays completion of all jobs
• can be good for pipelined jobs

Examples of Round-Robin Scheduling

Priority-Driven Scheduling Overview

• top-priority job gets to run until completion
• processor is never idle if jobs are waiting
• can be preemptive or non-preemptive
• can be applied to single or multiple processors

Examples of Priority-Driven Scheduling

Precedence Constraints, Effective Release Times & Deadlines

• effective release time r_i of job i =
  • r_i if i has no predecessors
  • max{r_j + e^-_j | j is predecessor of   i } otherwise
• effective deadline D_i of job i =
  • D_i, if i has no successors
  • min{D_j - e⁺_j | j is successor of   i }, otherwise

Note: The notation x here is intended as an HTML approximation to the symbol x with a horizontal line over it that is used in Jane Liu's text.

These definitions are helpful in reducing need for explicit consideration of precedence constraints.

Static vs. Dynamic Processor Assignment

Dynamic assignment generally results in intractable validation problems.

These problems will be discussed in more detail later in the course.