Priority-Based Scheduling (Periodic Tasks)

Priority-Based Scheduling (Periodic Tasks)
• “A preemptive method where the priority of the process

determines whether it continues to run or is disrupted”
(most important process first)
• On-line scheduler (does not precompute schedule)
• Fixed priorities:
– same priority to all jobs in a task
• Dynamic priorities:
– different priorities to individual jobs in each task
– task-level dynamic priorities
– job-level fixed priorities
RMS: Rate Monotonic Scheduling

• On-line
• Preemptive
• Priority-based with static priorities
• Period Ti that is the shortest interval between its arrival

times
• Processes are assigned priorities dependent on length of
Ti, the shorter it is, the higher the priority (or the higher
the rate, the higher the priority)
T i < T j ! Pi > P j
• RM algorithm or RMS
Example Priority Assignment

Process Period Priority
a 25
b 60
c 42
d 105
e 75
1
Example
P1 P2 P3
• Period (Ti) 20 50 30
• WCET (ei) 10 10 5
• Priority high low medium
arrival time process

t=0 P1,P2,P3
t=20 P1
t=30 P3
t=40 P1
t=50 P2
t=60 P1,P3
0 10 20 30 40 50 60 70
time
preemption
Schedulability Test
• For n processes, RMS will guarantee their schedulability
if the total utilization U does not exceed the guarantee
level G = n * (21/n - 1)
• When test fails:

– try with the worst case: assume that all processes are released
simultaneously at time 0, and then arrive according to their
periods
– check whether each process meets its deadline for all releases
before the first deadline for the process with the lowest priority
• Otherwise:
– change U by reducing c i (code optimization, faster processor, …)
– or increase Ti for some process (possible?)
Process Set A
Process Period ComputationTime Priority Utilization
T C P U
a 50 12 1 0.24
b 40 10 2 0.25
c 30 10 3 0.33
• The combined utilization is 0.82 (or 82%)

• This is above the threshold for three processes (0.78)
and, hence, this process set fails the utilization test
2
Timeline for Process Set A
Process
a Process Release Time
Process Completion Time

Deadline Met
b Process Completion Time
Deadline Missed
Preempted
c
Executing
0 10 20 30 40 50 60
Time
Process Set B
T C P U
a 80 32 1 0.400
b 40 5 2 0.125
c 16 4 3 0.250
• The combined utilization is 0.775

• This is below the threshold for three processes (0.78)
and, hence, this process set will meet all its deadlines
Process Set C
T C P U
a 80 40 1 0.50
b 40 10 2 0.25
c 20 5 3 0.25

• This is above the threshold for three processes (0.78) but
the process set will meet all its deadlines
3
Timeline for Process Set C
Process
0 10 20 30 40 50 60 70 80
Time
Response Time Analysis

• Here task i's worst-case response time, R, is calculated
first and then checked (trivially) with its deadline
R i ≤ Di
Ri = Ci + I i
Where I is the interference from higher priority tasks
Calculating R
During R, each higher priority task j will execute a number of
times:
$R "
Number of Releases = # i !
#Tj !
The ceiling function gives the smallest integer greater than the fractional
number on which it acts. So the ceiling of 1/3 is 1, of 6/5 is 2, and of 6/3 is 2.
Total interference is given by:

$ Ri "
# !C j
#Tj !
4
Reponse Time Equation
%R #
Ri = Ci + ! $ i "C j
j&hp ( i ) T
$ j"
Where hp(i) is the set of tasks with priority higher than task i
Solve by forming a recurrence relationship:
% win #
win +1 = Ci + ! $ "C j
j&hp ( i )
$ Tj "
0 1 2 n
The set of values wi , wi , wi ,..., wi ,.. is monotonically non decreasing
When win = win +1 the solution to the equation has been found, wi0
must not be greater than Ri (e.g. 0 orCi )
Process Set D
Process Period ComputationTime Priority
T C P
a 7 3 3
b 12 3 2
c 20 5 1
wb0 = 3
Ra = 3 $3"
wb1 = 3 + # ! 3 = 6
#7!
2 $6"
wb = 3 + # ! 3 = 6
#7!
Rb = 6
wc0 = 5
$5" $ 5 "
wc1 = 5 + # ! 3 + # 3 = 11
#7! #12 !
!
$ 11 " $ 11 "
wc2 = 5 + # 3+ # 3 = 14
#7 ! ! #12 !!
$14 " $14 "
wc3 = 5 + # 3+ # 3 = 17
# 7 !! #12 !!
$17 " $17 "

wc4 = 5 + # 3+ # 3 = 20
#7 !! #12 !
!
$ 20 " $ 20 "
wc5 = 5 + # 3+ # 3 = 20
# 7 !! # 12 !
!
Rc = 20
5
Revisit: Process Set C
Process Period ComputationTime Priority Response
time
T C P R
a 80 40 1 80
b 40 10 2 15
c 20 5 3 5
• This was above the ulilization threshold for three
processes (0.78), therefore it failed the test
• The response time analysis shows that the process set
will meet all its deadlines
• RTA is necessary and sufficient
Response Time Analysis

• Is sufficient and necessary
• If the process set passes the test they will meet all their
deadlines; if they fail the test then, at run-time, a process
will miss its deadline (unless the computation time
estimations themselves turn out to be pessimistic)
Exact Schedulability Test
for (each task T j) {

I = 0;
do {
R = I + cj
if (R > dj) return UNSCHEDULABLE;
I = ∑R/pkck ; /* k = 1..j-1 */
} while (I + cj > R)
return SCHEDULABLE;
}
6
Deadline-Monotonic Algorithm (DM)
• Fixed-priority
• Uses relative deadlines: the shorter the relative deadline,
the higher the priority
• RM and DM are identical if the relative deadline is
proportional to its period
• Otherwise DM performs better in the sense that it can
sometimes produce a feasible schedule when RM fails,
while RM always fails when DM fails
Example
T1
0 50 100 150 200 250
T2
0 62.5 125 187.5
T3
T1
0 50 100 150 200 250
T2
0 62.5 125 187.5
T3

Priority-Based Scheduling (Periodic Tasks)

Uploaded by

Copyright:

Available Formats

Priority-Based Scheduling (Periodic Tasks)

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Priority-Based Scheduling (Periodic Tasks)

Uploaded by

Copyright:

Available Formats

Priority-Based Scheduling (Periodic Tasks)

• “A preemptive method where the priority of the process

RMS: Rate Monotonic Scheduling

• Period Ti that is the shortest interval between its arrival

Example Priority Assignment

arrival time process

• When test fails:

• The combined utilization is 0.82 (or 82%)

a Process Release Time

Process Completion Time

• The combined utilization is 0.775

• The combined utilization is 1.0

Response Time Analysis

Where I is the interference from higher priority tasks

Total interference is given by:

Solve by forming a recurrence relationship:

$17 " $17 "

Response Time Analysis

Exact Schedulability Test

for (each task T j) {

You might also like