Networked Embedded Systems Lab

Prof. Marco Zimmerling

Introduction to Embedded Systems – WS 2022/23

Sample Solution to Exercise 4: Scheduling Periodic and Mixed Task Sets

Task 1: Earliest Deadline First (EDF) and Total Bandwidth Server (TBS)

Consider the following set of periodic tasks:

τ1 τ2 τ3
Ci 1 1 2
Ti 3 5 13
A Total Bandwidth Server (TBS) executes along with the periodic tasks above.

1. What can be the maximum value of Us such that the whole set (i.e., periodic tasks and the TBS) is
schedulable with EDF?
2. Now assume Us = 0.25. Construct the EDF schedule (in Figure 1) in the case in which three aperiodic
requests J4 (r4 = 0, C4 = 2), J5 (r5 = 15, C5 = 1) and J6 (r6 = 10, C6 = 1) are served by TBS. Assume
that the arrival time of the first instance/job of each periodic task is 0.

Solution to Task 1:

1. Maximum utilization of the Total Bandwidth Server:

Us,max = 1 − Up = 1 − (1/3 + 1/5 + 2/13) = 61/195 ≈ 0.3128
2. First, we need to order the tasks by increasing release time ri : J4 , J6 , J5 . Then, we calculate the
deadlines with di = max(ri , dk−1 ) + C
Us , where dk−1 denotes the previously calculated deadline (k − 1
k

means the predecessor in the ordering according to the release time):

d4 = max (r4 , d0 ) + 2/0.25 = 0 + 8 = 8
d6 = max (r6 , d4 ) + 1/0.25 = 10 + 4 = 14
d5 = max (r5 , d6 ) + 1/0.25 = 15 + 4 = 19
For the resulting EDF schedule see Figure 1.

1
 τ1

τ2

τ3

J4

J5

J6

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Time

Figure 1: EDF schedule solution for Task 1

Task 2: Schedulability Test for Fixed Priorities – Rate Monotonic (RM)

τ1 τ2 τ3
Ci 1 3 2
Ti 3 8 9
1. Test if the given task-set is schedulable under RM, using the sufficient test.
2. Test if the given task-set is schedulable under RM, using the necessary test.
3. Assume that the first job of each task arrives at time 0. Construct the schedule for the interval [0, 20]
and illustrate it graphically. In case they exist, identify deadline misses.

Solution to Task 2:

The priorities of the tasks are assigned statically, before the actual execution of the task set. Rate Monotonic
scheduling scheme assigns higher priority to tasks with smaller periods. It is preemptive (tasks are preempted
by the higher priority tasks). It is an optimal scheduling algorithm amongst fixed-priority algorithms; if a task
set cannot be scheduled with RM, it cannot be scheduled by any fixed-priority algorithm.

1. The sufficient schedulability test is given by:

n
X Ci
U= ≤ n(21/n − 1)
i=1
Ti

The term U is said to be the processor utilization factor (the fraction of the processor time spent on
executing task set). n is the number of tasks.
In our case: 1/3 + 3/8 + 2/9 = 0.93 6≤ 3(21/3 − 1) = 0.78 failed!
The above condition is not necessary, hence we don’t know whether the task set is schedulable with RM
or not. We can do a somewhat more involved sufficient and necessary condition test, as follows.
2. We have to guarantee that all the tasks can be scheduled, in any possible instance. In particular, if
a task can be scheduled in its critical instances, then the schedulability guarantee condition holds (a

2
 critical instance of a task occurs whenever the task is released simultaneously with all higher priority
tasks). In the following, we perform the iterative schedulability algorithm on slide 6-26 (for the details
of the algorithm, please have a look at page 99, Buttazzo’s book).
The tasks are first ordered by their priorities: τ1 , τ2 and τ3 . (In this case the tasks are already ordered.)
τ3 :
P2
R30 = k=1 Ck + C3 = 4 + 2 = 6 I30 = d 63 e1 + d 86 e3 = 2 + 3 = 5 5 + 2 6= 6
R31 = 5 + 2 = 7 I31 = d 73 e1 + d 87 e3 = 3 + 3 = 6 6 + 2 6= 7
2
R3 = 6 + 2 = 8 I32 = d 83 e1 + d 88 e3 = 3 + 3 = 6 6 + 2 = 8 . . . OK
(since R32 = 8 ≤ T3 = 9)
τ2 :
P1
R20 = k=1 Ck + C2 = 1 + 3 = 4 I20 = d 43 e1 = 2 2 + 3 6= 4
R21 = 2 + 3 = 5 I21 = d 53 e1 = 2 2 + 3 = 5 . . . OK (since R21 = 5 ≤ T2 = 8)
τ1 :
R10 = C1 = 1 I10 = 0 0 + 1 = 1 . . . OK (since R10 = 1 ≤ T1 = 3)
The necessary and sufficient test succeeds. This means that the task set is schedulable with RM.
3. The schedule is represented graphically in Figure 2. (There are no deadline misses. )

Figure 2: RM schedule of Task 2.

Task 3: Scheduling with Polling Server

τ1 τ2 τ3
Ci 2 2 2
Di 6 8 16
Ti 6 8 16
In addition to the above periodic tasks, we have an aperiodic job Ja with computation time Ca = 1, and
relative deadline Da . The scheduling policy is RM. The aperiodic job is scheduled through a Polling Server
(PS).

1. Let the period and computing time of the polling server be Ts = 25 and Cs = 1, respectively. Compute
the aperiodic guarantee available to Ja , i.e., compute the minimum relative deadline of Ja which is
guaranteed not to be missed.
2. Using the sufficient test of RM, test if the polling server of (a) is schedulable along with the periodic
task-set?
3. [optional] Determine integer parameters (Cs , Ts ) of the polling server such that (1) the relative deadline
guaranteed to Ja is minimised, and (2) the RM schedule satisfies the sufficient schedulability test.
4. [optional] For the optimal setting of (c) devise a necessary schedulability test with the relative deadline
of the aperiodic task Da = 32.

3
Solution to Task 3:

Recall the way the polling server works. If at the start of a new period of the polling server, there are no
pending aperiodic jobs, then no aperiodic jobs are executed for the whole period. Thus, the worst-case arrival
time of an aperiodic job is just after the start of the period of the polling server. Then, the aperiodic guarantee
is given by

lC m
a
(1 + )Ts ≤ Da
Cs
1. By using the aperiodic guarantee and substitute the given parameters, we have Da = 50.
The above computation of Da holds only if the RM schedule meets all deadlines.
2. The sufficient schedulability test for RM (including the Polling Server introduced to handle the firm
aperiodic request Ja ) is given by:
n
X Ci Cs
+ ≤ (n + 1)(21/(n+1) − 1)
i=1
Ti Ts

Substituting the parameters of the task-set, we arrive at 0.748 ≤ 0.76. This is true, and hence the RM
schedule meets all deadlines.
3. Let Cs and Ts be unknown. Then the sufficient RM schedulability test implies that
n
Cs X Ci
≤ (n + 1)(21/(n+1) − 1) − = 0.7568 − 0.7083 = 0.0485
Ts T
i=1 i

Since, we use only integer values for Cs and Ts , we can set (Cs , Ts ) as (1, 21) or (2, 42) or (3, 63) and
so on.
For the optimal configuration of the server, we have Ts < 50 (as we managed to get a guarantee of 50
with the previous setting). Upon inspection, (1, 21) is the optimal solution with the minimum relative
deadline of 42.
4. The sufficient schedulability test guarantees Da = 42. We use the necessary test of RM to obtain a
smaller Da . Note that the polling server is the lowest priority task.
Ra0 = Ca = 1 Ia0 = d 16 e2 + d 18 e2 + d 16 1
e2 = 6 6 + 1 6= 1
1 1 7 7 7
Ra = 7 I3 = d 6 e2 + d 8 e2 + d 16 e2 = 8 8 + 1 6= 7
Ra2 = 9 I32 = d 96 e2 + d 98 e2 + d 16
9
e2 = 10 10 + 1 6= 9
3 3 11 11 11
Ra = 11 I3 = d 6 e2 + d 8 e2 + d 16 e2 = 10 10 + 1 = 11
The above analysis shows from the time of beginning of execution of Ja it needs 11 time units to finish.
But, as already mentioned, Ja can arrive just after the start of the polling server period. Thus, we have
Da = 11 + Ts = 11 + 21 = 32. This is indeed much smaller than the earlier value of 42.

Task 4: Periodic Scheduling with Fixed Priorities – DM

Given the following set of periodic tasks:

τ1 τ2 τ3
Ci 1 2 3
Di 5 4 8
Ti 5 6 10
1. Check the schedulability of the task set using the Deadline Monotonic (DM) policy.
2. Construct the schedule graphically. Let the phase Φi = 0 ∀i. In case they exist, identify deadline misses.

4
Solution to Task 4:

DM (Deadline Monotonic) scheduling scheme assigns priorities based on the relative deadlines of the periodic
tasks. Higher priority corresponds to a task having an earlier deadline.

1. One first schedulability test is (sufficient, not necessary): 1/5 + 2/4 + 3/8 = 1.075 6≤ 3(21/3 − 1) = 0.78
failed!
The other test to do follows the lines of the solution of the previous exercise: the tasks are ordered with
respect to their priorities τ2 , τ1 , τ3 .
τ3 :
R30 = C3 = 3 I30 = d 35 e1 + d 63 e2 = 1 + 2 = 3 3 + 3 6= 3
R3 = 3 + 3 = 6 I31 = d 65 e1 + d 66 e2 = 2 + 2 = 4 4 + 3 6= 6
1

R32 = 4 + 3 = 7 I32 = d 75 e1 + d 67 e2 = 2 + 4 = 6 6 + 3 6= 7
R33 = 6 + 3 = 9 I33 = d 95 e1 + d 69 e2 = 2 + 4 = 6 6 + 3 = 9 . . . 9 6≤ D3 = 8 failed!

The schedule is not feasible.

2. The graphical representation of the failed scheduling is presented in Figure 3:

3.5

2.5

1.5

0.5

0
0 1 2 3 4 5 6 7 8 9 10

Figure 3: DM schedule (not feasible).

Task 5: Mixed Tasks – Polling Server

Two periodic tasks are given, with execution times and periods given in the following table (deadlines equal
periods). The phase of the periodic tasks is assumed to be Φi = 0 ∀i. The given set of tasks should be
scheduled with the Rate Monotonic scheduling scheme.

τ1 τ2
Ci 1 2
Ti 5 8

Construct a schedule graphically for following aperiodic requests (a Polling Server with integer parameters
should be introduced). The CPU utilization has to be maximized.

J1 J2 J3
ai 2 7 9
Ci 3 2 1

5
Solution to Task 5:

For the task set to be schedulable with RM (and the introduction of the Polling Server), one should have the
following condition satisfied:

Cs 1 2
+ ( + ) ≤ 3(21/3 − 1)
Ts 5 8
Cs
≤ 0.3298
Ts

With parameters chosen, for example: Cs = 1 and Ts = 4, the schedule, depicted in Figure 4 is feasible.

Figure 4: RM schedule - Polling Server with Cs = 1, Ts = 4

We could have also chosen different (integer-valued) server parameters, say Cs = 2 and Ts = 7. This solution
of the RM schedule is depicted in Figure 5.

Figure 5: RM schedule - Polling Server with Cs = 2, Ts = 7

The actual CPU utilization (by the time the aperiodic requests have been served) is greater in the second
case. U2 = 17/23 = 0.739 > 0.68 = 17/25 = U1 .

Actually, one could assign the server parameters in such a way that the task set is still schedulable (we can
show that this is the case by using the - somewhat more involved - test presented in the solution to the Task
2). For this task set, the parameters of the server may be even Cs = 2 and Ts = 4. (This is, wrt other
periodic tasks in the system, optimal for serving the aperiodic requests, as the server will become the highest
priority task in the system).

Task 6: Mixed Tasks – Total Bandwidth Server

We have to design a system that schedules periodic tasks with EDF and employs a total bandwidth server to
serve aperiodic requests. We know of one sporadic aperiodic request with computation time Ca = 2 and a
relative deadline Da = 7. What is the maximum processor utilization available for periodic tasks if we want
to guarantee that this aperiodic task completes within its deadline?

Solution to Task 6:

For a schedule to be feasible, the sufficient and necessary condition to hold is Up + Us ≤ 1. Therefore we have

6
 Ca 2 5
Up ≤ 1 − Us = 1 − =1− =
Da 7 7

The maximum processor utilization available for periodic tasks is 5/7 = 0.714.

Task 7: Periodic Scheduling

A processor is supposed to execute the following set of tasks described by their execution times C, relative
deadlines D and periods T .
τ1 τ2 τ3
Ci 2 2 4
Di 5 4 8
Ti 6 8 12
1. Execute the sufficient schedulability test under DM and calculate the result. What statement regarding
schedulability can be made based on your result?
2. Execute the sufficient and necessary schedulability test under DM and calculate the result. What
statement regarding schedulability can be made based on your result?
3. If there is a feasible schedule for the given task set, construct it graphically. Let the phase Φi = 0 ∀i.

Solution to Task 7:

1. A sufficient schedulability test for a given task set (and with respect to the fixed-priorities scheduling
schemes, DM in this case, since the deadlines are smaller than the periods) is given by:
n
X Ci
≤ n(21/n − 1)
i=1
D i

In our case, we have: 2/5 + 2/4 + 4/8 = 1.4 6≤ 0.78 = 3(21/3 − 1) failed!.
The above test was sufficient but not necessary. Hence the tasks might be schedulable by DM.
2. The sufficient and necessary test for DM can be done by determining the value of the longest response
time Ri = Ci + Ii of a periodic task τi at its critical instances.
(DM) The tasks are ordered with respect to their priorities (earlier deadline - higher priority): τ2 , τ1 and
τ3 .
Let’s first check for the lowest priority task τ3 :
R30 = C3 = 4 I30 = d 46 e2 + d 48 e2 = 2 + 2 = 4 4 + 4 6= 4
R31 = 4 + 4 = 8 I31 = d 68 e2 + d 88 e2 = 4 + 2 = 6 6 + 4 6= 8 failed!
Since R32 = 4 + 6 = 10 6≤ D3 = 8, the tasks are not schedulable with DM!
3. Despite the fact that the schedulability tests for DM have failed, there is a feasible schedule under EDF.
It is shown in Figure 6.

T3
T2
T1

0 1 2 3 4 5 6 8 10 12 14 16 18 20 22 24

Figure 6: EDF schedule

7
A necessary and sufficient test for EDF is to use the demand bound analysis, which is not covered in the
course. Interested reader may look at the following reference
S. Baruah, A. Mok, L. Rosier. Preemptive Scheduling Hard-Real-Time Sporadic Tasks on One Processor.
Proceedings of the Real-Time Systems Symposium, 182-190, 1990.