Scribd
Upload
28 views3 pages

Rtos Scheduling

The document introduces real-time scheduling, outlining three practical approaches: clock-driven, weighted round-robin, and priority-driven scheduling. It discusses the characteristics and applications of each method, including static and dynamic scheduling considerations, as well as precedence constraints and effective release times. The content serves as a foundational overview for deeper exploration of real-time scheduling concepts in future courses.

Uploaded by

Drishti Rani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views3 pages

Rtos Scheduling

The document introduces real-time scheduling, outlining three practical approaches: clock-driven, weighted round-robin, and priority-driven scheduling. It discusses the characteristics and applications of each method, including static and dynamic scheduling considerations, as well as precedence constraints and effective release times. The content serves as a foundational overview for deeper exploration of real-time scheduling concepts in future courses.

Uploaded by

Drishti Rani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Real Time Systems: Notes

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
This is also known as list, greedy, and work-conserving scheduling.

Examples of Priority-Driven Scheduling

Precedence Constraints, Effective Release Times & Deadlines


effective release time ri of job i =

ri if i has no predecessors

max{rj + e-j | j is predecessor of i } otherwise

effective deadline Di of job i =

Di, if i has no successors


min{Dj - 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.

© 1998, 2003, 2006 T. P. Baker.


$Id: introscheduling.html,v 1.2 2008/08/25 11:18:48 baker Exp baker $

You might also like