Embedded Systems – Exercise 4:

Scheduling Periodic and Mixed Task Sets

Roman Trüb, [email protected]

Computer Engineering Group, ETH Zurich

Roman Trüb | 11./13.11.2020 | 1

Exercise Structure
Goal of today’s exercise:
▪ Learn and apply scheduling schemes for periodic and mixed task sets.
Agenda:
▪ Wednesday 16:15 – 17:00 Clicker quiz (recorded)
Lecture summary (recorded)
Solving a sample task (recorded)
Tasks of exercise 4 (recorded)
Q&A
▪ Friday 16:15 – 17:00 Solution discussion (recorded)
Q&A
Available Assistants:
▪ Roman Trüb - TA
▪ Joël Küchler - SA

Roman Trüb | 11./13.11.2020 | 2

Clicker Quiz

Roman Trüb | 11./13.11.2020 | 3

Clicker Quiz – Question 1

Schedulable with EDF

Test failed

Task set is not schedulable with EDF

Roman Trüb | 11./13.11.2020 | 4

Clicker Quiz – Question 2

Schedulable with RM

With this test result, no statement can be made since

schdulablility test condition is not necessary.
Task set could still be schedulable with RM.
Roman Trüb | 11./13.11.2020 | 5
Clicker Quiz – Question 3

Roman Trüb | 11./13.11.2020 | 6

Clicker Quiz – Question 4

Roman Trüb | 11./13.11.2020 | 7

Lecture Summary

Roman Trüb | 11./13.11.2020 | 8

Scheduling Algorithms

Periodic with Periodic with

Mixed Tasks
D=T D<T

Static
RM DM Polling Server
Priority

Total
Dynamic
EDF EDF Bandwidth
Priority
Server

Roman Trüb | 11./13.11.2020 | 9

Scheduling Periodic Task Sets [6-33f]

Periodic with Periodic with

Mixed Tasks
D=T D<T

Static
RM DM Polling Server
Priority

Total
Dynamic
EDF EDF Bandwidth
Priority
Server

Roman Trüb | 11./13.11.2020 | 10

Rate Monotonic (RM)
Static priority assignment:
Tasks with shorter period get higher priority

T1
t
T2
t
T3
t

t
Roman Trüb | 11./13.11.2020 | 11
Rate Monotonic (RM)
Static priority assignment:
Tasks with shorter period get higher priority

High

T2
t
T1
t
T3
t
Low

t
Roman Trüb | 11./13.11.2020 | 12
Rate Monotonic (RM)
Static priority assignment:
Tasks with shorter period get higher priority

High

T2
t
T1
t
T3
t
Low

t
Roman Trüb | 11./13.11.2020 | 13
Rate Monotonic (RM)
Static priority assignment:
Tasks with shorter period get higher priority

High

T2
t
T1
t
T3
t
Low

t
Roman Trüb | 11./13.11.2020 | 14
Rate Monotonic (RM)
Static priority assignment:
Tasks with shorter period get higher priority

High

T2
t
T1
t
T3
t
Low

t
Roman Trüb | 11./13.11.2020 | 15
Rate Monotonic (RM)
Static priority assignment:
Tasks with shorter period get higher priority

High

T2
t
T1
t
T3
t
Low

t
Roman Trüb | 11./13.11.2020 | 16
RM – Schedulability Test

Sufficient
(but not necessary)

Roman Trüb | 11./13.11.2020 | 17

Scheduling Periodic Task Sets [6-33f]

Periodic with Periodic with

Mixed Tasks
D=T D<T

Static
RM DM Polling Server
Priority

Total
Dynamic
EDF EDF Bandwidth
Priority
Server

Roman Trüb | 11./13.11.2020 | 18

Deadline Monotonic (DM)
Static priority assignment:
Tasks with smaller relative deadline get higher priority

T2
t
T3
t
T1
t

t
Roman Trüb | 11./13.11.2020 | 19
Deadline Monotonic (DM)
Static priority assignment:
Tasks with smaller relative deadline get higher priority

High
T3
t
T2
t
T1
t
Low

t
Roman Trüb | 11./13.11.2020 | 20
Deadline Monotonic (DM)
Static priority assignment:
Tasks with smaller relative deadline get higher priority

High
T3
t
T2
t
T1
t
Low

t
Roman Trüb | 11./13.11.2020 | 21
Deadline Monotonic (DM)
Static priority assignment:
Tasks with smaller relative deadline get higher priority

High
T3
t
T2
t
T1
t
Low

t
Roman Trüb | 11./13.11.2020 | 22
Deadline Monotonic (DM)
Static priority assignment:
Tasks with smaller relative deadline get higher priority

High
T3
t
T2
t
T1
t
Low

t
Roman Trüb | 11./13.11.2020 | 23
Deadline Monotonic (DM)
Static priority assignment:
Tasks with smaller relative deadline get higher priority

High
T3
t
T2
t
T1
t
Low

t
Roman Trüb | 11./13.11.2020 | 24
DM – Schedulability Test

Sufficient
(but not necessary)

Roman Trüb | 11./13.11.2020 | 25

RM & DM – Schedulability Test

Necessary &
Sufficient

Assumption: Tasks are

ordered according to their
priorities:

Ri Ri
Longest Response Time Ri
Worst-case
(computed iteratively)
Interference: +Ci
Roman Trüb | 11./13.11.2020 | 26
Scheduling Periodic Task Sets [6-33f]

Periodic with Periodic with

Mixed Tasks
D=T D<T

Static
RM DM Polling Server
Priority

Total
Dynamic
EDF EDF Bandwidth
Priority
Server

Roman Trüb | 11./13.11.2020 | 27

Earliest Deadline First (EDF)
Dynamic Priority Assignment:
Always execute the task with the currently closest deadline

T1
t
T2
t
T3
t

t
Roman Trüb | 11./13.11.2020 | 28
Earliest Deadline First (EDF)
Dynamic Priority Assignment:
Always execute the task with the currently closest deadline

T1
t
T2
t
T3
t

t
Roman Trüb | 11./13.11.2020 | 29
Earliest Deadline First (EDF)
Dynamic Priority Assignment:
Always execute the task with the currently closest deadline

T1
t
T2
t
T3
t

t
Roman Trüb | 11./13.11.2020 | 30
Earliest Deadline First (EDF)
Dynamic Priority Assignment:
Always execute the task with the currently closest deadline

T1
t
T2
t
T3
t

t
Roman Trüb | 11./13.11.2020 | 31
EDF – Schedulability Tests

Di= Ti Di< Ti

Necessary & Sufficient

Sufficient (but not necessary)

Utilization:

Roman Trüb | 11./13.11.2020 | 32

Mixed Task Scheduling

• Mixed (or hybrid) task set contains both periodic and

aperiodic tasks

• Basic idea for scheduling:

• Schedule the periodic tasks as usual
• Serve the aperiodic tasks via a "server" that behaves
like a periodic task but serves the aperiodic tasks

Roman Trüb | 11./13.11.2020 | 33

Scheduling Mixed Task Sets [6-64f]

Periodic with Periodic with

Mixed Tasks
D=T D<T

Static
RM DM Polling Server
Priority

Total
Dynamic
EDF EDF Bandwidth
Priority
Server

Roman Trüb | 11./13.11.2020 | 34

Polling Server (RM)
Idea: Introduce an artificial periodic task (Cs, Ts) which serves the aperiodic
requests

Schedulability test for mixed task set: Sufficient

(but not necessary)

Aperiodic guarantee (schedulability test for aperodic requests): Sufficient

(but not necessary)
Assumption: aperiodic task finishes
before new aperiodic request arrives

Roman Trüb | 11./13.11.2020 | 35

Scheduling Mixed Task Sets [6-64f]

Periodic with Periodic with

Mixed Tasks
D=T D<T

Static
RM DM Polling Server
Priority

Total
Dynamic
EDF EDF Bandwidth
Priority
Server

Roman Trüb | 11./13.11.2020 | 36

Total Bandwidth Server (EDF)

Idea: For every aperiodic request a deadline which is based on the server’s
parameters (Cs, Ts) is assigned. The aperiodic requests are then scheduled with
EDF as any other periodic instance.

Assignment of the deadlines to the aperiodic requests:

NOTE: recursive
computation!
Aperiodic requests
are assumed to be
ordered by increasing
release time ri

Roman Trüb | 11./13.11.2020 | 37

Total Bandwidth Server (EDF)

Schedulability test for mixed task set: Necessary &

Sufficient

Set of periodic tasks with

utilization Up and a Total
Bandwidth Server with utilization
Us is schedulable with EDF

Utilization of Total Bandwidth Server:

Utilization of the periodic tasks:

Roman Trüb | 11./13.11.2020 | 38

Sample Task
(Task 4a)

Roman Trüb | 11./13.11.2020 | 39

Roman Trüb | 11./13.11.2020 | 40
First Try Sufficient (But Not Necessary) Scheduling Test.

Test failed. No statement can be made (since test is sufficient but not necessary).

Roman Trüb | 11./13.11.2020 | 41

RM & DM – Schedulability Test

Necessary &
Sufficient

Assumption: Tasks are

ordered according to their
priorities:

Ri Ri
Longest Response Time Ri
Worst-case
(computed iteratively)
Interference: +Ci
Roman Trüb | 11./13.11.2020 | 42
Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):

Roman Trüb | 11./13.11.2020 | 43

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Roman Trüb | 11./13.11.2020 | 44

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Roman Trüb | 11./13.11.2020 | 45

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Roman Trüb | 11./13.11.2020 | 46

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Roman Trüb | 11./13.11.2020 | 47

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Roman Trüb | 11./13.11.2020 | 48

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Roman Trüb | 11./13.11.2020 | 49

Apply Sufficient and Necessary Scheduling Test [6-54]
1. Order tasks according to their priorities (relative deadlines for DM):
2. Apply iterative algorithm to find longest response time for each task, starting
with last task

Test failed.
Task set is not schedulable using the Deadline Monotonic scheduling scheme.
Roman Trüb | 11./13.11.2020 | 50
Exercise 4

Roman Trüb | 11./13.11.2020 | 51

Roman Trüb | 11./13.11.2020 | 52
Roman Trüb | 11./13.11.2020 | 53
Roman Trüb | 11./13.11.2020 | 54
Exercise 4 - Solution

Roman Trüb | 11./13.11.2020 | 55

Roman Trüb | 11./13.11.2020 | 56
Task 1 – Solution

a) Maximum utilization of the server:

b) Order tasks by increasing release time: J4, J6, J5

Then, calculate new deadlines recursively:

Roman Trüb | 11./13.11.2020 | 57

Task 1 – Solution

b) EDF schedule with aperiodic tasks:

Roman Trüb | 11./13.11.2020 | 58

Roman Trüb | 11./13.11.2020 | 59
Task 2 – Solution

a) Sufficient test:

Test failed! Since it is not necessary, we still don’t know if the task set is
schedulable with RM or not.

Roman Trüb | 11./13.11.2020 | 60

Task 2 – Solution

b) Necessary test: Iterative algorithm

1) Order tasks by their priority (already ok in this case)
2) Start with task which has lowest priority:

Necessary test succeeds task set is schedulable with RM

Roman Trüb | 11./13.11.2020 | 61

Task 2 – Solution

c) RM schedule

(there are no deadline misses)

Roman Trüb | 11./13.11.2020 | 62

Roman Trüb | 11./13.11.2020 | 63
Task 3 – Solution

a) Aperiodic guarantee:

Substituting values & considering minimum

b) Sufficient schedulability test for RM Polling Server:

Test succeeded!
Task set is schedulable with RM

Roman Trüb | 11./13.11.2020 | 64

Exercise Session is Over
▪ The assistants are now available until roughly 17:00 to answer questions.
▪ Zoom: Ask in this Zoom channel
▪ Matrix-Chatroom: Ask a question in the chatroom so other students can also profit from the
response (or respond even quicker!)
▪ Email: For individual questions, you can also reach me under [email protected] .

Roman Trüb | 11./13.11.2020 | 68