Scheduling policies
A scheduling policy is a rule that selects the
next running process.
General purpose operating systems try to
balance access to the CPU for all processes.
Real time operating systems must provide
control over real time behavior:
Priority driven scheduling ;
1
Real time Scheduling
Number and types of tasks, associated
parameters are not known in advance.
Scheduling must accommodate dynamic
changes
Online Scheduling are of two types:
Static Priority
Dynamic Priority
2
Real-Time Scheduling
Real-time tasks are executed repeatedly (usually
are periodic) under some time constraint
Task Task Task
Time
0ms 5ms 10ms
E.g., a task is released to execute every 5 msec, and each
invocation has a deadline of 5 msec
3
Worst-Case Execution Time -
WCET
Obtained by either measurement or analysis
The problem with measurement is that it is difficult to
be sure when the worst case has been observed
The drawback of analysis is that an effective model of
the processor (including caches, pipelines, memory wait
states and so on) must be available
Static vs. Dynamic
Scheduling
Real-time scheduling
classes
First-in, First-out scheduling
Round robin scheduling
Preemptive fixed priority scheduling
Most frequent first
Earliest deadline first
6
FIFO Scheduling
First-in, First-out scheduling
The first enqueued task of highest priority executes to completion
A task will only relinquish a processor when it is completed, yielded, or
blocked
Task 1 Task 2 Task 3
Time
7
Round Robin Scheduling
Among tasks of equal priority:
Rotate through all tasks
Each task gets a fixed time slice
Task Task Task Task Task Task Task Task Task
1 2 3 1 2 3 1 2 3
Time
8
Preemptive Fixed Priority
Scheduling
High Priority Task
Time
Low Priority Task
9
Preemptive Fixed Priority
Scheduling
High Priority Task
Time
Low Priority Task
10
Preemptive Fixed Priority
Scheduling
High & low priority
jobs arrived together
High Priority Task
Time
Low Priority Task
11
Preemptive Fixed Priority
Scheduling
High priority job is
executed first
High Priority Task
Time
Low Priority Task
12
Preemptive Fixed Priority
Scheduling
High Priority Task
Low priority job is
executed later
Time
Low Priority Task
13
Preemptive Fixed Priority
Scheduling
High priority job
High Priority Task arrived
Time
Low Priority Task
14
Preemptive Fixed Priority
Scheduling
Preempts low priority
High Priority Task job
Time
Low Priority Task
15
Preemptive Fixed Priority
Scheduling
High Priority Task
Lower priority job
resumes later
Time
Low Priority Task
16
Preemptive Fixed Priority
Scheduling
High Priority Task
Time
Low Priority Task
17
Preemptive Fixed Priority
Scheduling
High Priority Task
Time
Low Priority Task
18
Real-Time Scheduling
Under static-priority scheduling, different jobs
of the same task are assigned the same
priority.
Under dynamic-priority scheduling, different
jobs of the same task may be assigned
different priorities.
Optimal Scheduling
Algorithms
Rate Monotonic (RM)
The higher the rate (the shorter the period) is the
higher priority.
Optimal preemptive static priority scheduling
algorithm
Earliest Deadline First (EDF)
The earlier absolute deadline is the higher
priority
Optimal preemptive dynamic priority scheduling
algorithm
Rate Monotonic, RM
Each process is assigned a (unique) priority
based on its period; the shorter the period, the
higher the priority
T i T j Pi P j
I.e, for two processes i and j,
This assignment is optimal in the sense that if
any process set can be scheduled (using pre-
emptive priority-based scheduling) with a fixed-
priority assignment scheme, then the given
process set can also be scheduled with a rate
monotonic assignment scheme
Note, priority 1 is the lowest (least) priority
Rate Monotonic, RM
Simplest type of real time scheduling
- Tasks are periodic, with hard deadlines
- Tasks are completely independent and
do not communicate with each other
- Tasks are scheduled according to priority
and task priorities are fixed
- Computation time is known and constant
Example Priority
Assignment
Process Period, T Priority, P
a 25 5
b 60 3
c 42 4
d 105 1
e 75 2
5 is the highest priority
1 is the lowest priority
Rate Montonic Scheduling
A priority is assigned based on the inverse of its
period
Shorter periods = higher priority
Longer periods = lower priority
P1(20,50,50) and P2(40, 100, 100)
P1 is assigned a higher priority than P 2.
24
Missed Deadlines with Rate Monotonic Scheduling
P1(25,50,50) and P2(40, 80, 80)
25
Task Set A
Task Period ComputationTime Priority
T C P
a 50 12 1
b 40 10 2
c 30 10 3
Time-line for task Set A
task
a Task Release Time
Task Completion Time
Deadline Met
b Task Completion Time
Deadline Missed
Preempted
c
Executing
0 10 20 30 40 50 60
Time
Gantt Chart for Task Set A
c b a c b
0 10 20 30 40 50
Time
RM Example
RM Example
RM Example
Response Time
Deadline Monotonic
Tasks with shorter deadlines get higher
priority.
Static Scheduling.
If D(h) < D(l), then PR(h) > PR(l), where D
indicates the deadline. This is called
Deadline Monotonic priority assignment.
It is a Preemptive Scheduling Algorithm that
means if any task of higher priority comes
then, running task is preempted and higher
priority task is assigned to CPU.
Example
Suppose there are two tasks that
need to be executed.
T1 ( 7, 2, 6 )
T2 ( 5, 2, 4 )
Complete execution
process