Networked Embedded Systems Lab

Prof. Marco Zimmerling

Introduction to Embedded Systems – WS 2022/23

Sample Solution to Exercise 2: Cyclic-Executive Scheduling

Task 1: Feasibility

Given the task set and cyclic-executive schedule in Table 1, determine whether the cyclic-executive schedule
is feasible. Determine the initial phase for each task such that the execution of each task instance finishes
between its arrival and deadline. Note that the deadline should be after the frame in which the task instance
executes, and the arrival should be before the frame in which the task instance executes.

Task Period Deadline Execution Time Frames

1 15 9 2 2, 5, 9, 12
2 12 4 3 1, 4, 7, 10, 13
3 10 6 1 1, 3, 6, 8, 11, 13
4 6 6 2 2, 3, 5, 6, 8, 9, 11, 12, 14, 15

Table 1: A task set and schedule

Use period P = 60 and frame length f = 4.

Solution to Task 1:

We need to answer several questions to determine the feasibility of the schedule.

1. Is the period P a common multiple of all task periods?

Yes, as we see from Table 1.

2. Is the period P a multiple of the frame f ?

Yes, 15 · f = P .

3. Is the frame f sufficiently long?

Yes. We can see this by drawing the schedule, see Fig. 1, or by adding the execution times per frame,
see Table 2.

4. Determine offsets such that instances start after release time.

See (1).

5. Are deadlines respected?

Yes, as can be seen from (2).

1
 2 3 1 4 3 4 2 1 4 3 4 2 3 4 1 4 2 3 4 1 4 2 3 4 4

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60

Figure 1: The schedule in Task 1

Φi = min {(fi,j − 1)f − (j − 1)Ti }

1≤j≤P/Ti
 
(2 − 1)4 − (1 − 1)15

 4


 
(5 − 1)4 − (2 − 1)15
 
1
Φ1 = min = min = −1


 (9 − 1)4 − (3 − 1)15 

 2

 

(12 − 1)4 − (4 − 1)15 −1
 
 


 (1 − 1)4 − (1 − 1)12 

 0

 

(4 − 1)4 − (2 − 1)12 0

 

 
Φ2 = min (7 − 1)4 − (3 − 1)12 = min 0 = 0

 

(10 − 1)4 − (4 − 1)12

 0



 

 
(13 − 1)4 − (5 − 1)12 0
 
 


 (1 − 1)4 − (1 − 1)10 

 0

 




 (3 − 1)4 − (2 − 1)10 


 −2
 
(6 − 1)4 − (3 − 1)10
 
0
Φ3 = min = min = −2


 (8 − 1)4 − (4 − 1)10 

 −2

 

(11 − 1)4 − (5 − 1)10 0

 


 


 

(13 − 1)4 − (6 − 1)10 −2
 

 (2 − 1)4 − (1 − 1)6 
 4

 

(3 − 1)4 − (2 − 1)6 2

 


 


 

(5 − 1)4 − (3 − 1)6 4

 


 


 




 (6 − 1)4 − (4 − 1)6 


 2
 
(8 − 1)4 − (5 − 1)6
 
4
Φ4 = min = min =2 (1)


 (9 − 1)4 − (6 − 1)6 

 2

 

(11 − 1)4 − (7 − 1)6 4

 


 


 




 (12 − 1)4 − (8 − 1)6 


 2
 
(14 − 1)4 − (9 − 1)6
 





 4

 

(15 − 1)4 − (10 − 1)6 2
 

2
 Frame #1 #2 #3 #4 #5 #6 #7 #8
exec. time 3+1 2+2 1+2 3 2+2 1+2 3 1+2
Frame #9 # 10 # 11 # 12 # 13 # 14 # 15
exec. time 2+2 3 1+2 2+2 3+1 2 2

Table 2: Execution time per frame

(j − 1)Ti + Φi + Di ≥ fi,j f ∀i, 1 ≤ j ≤ P/Ti




 (1 − 1)15 − 1 + 9 = 8 ≥ 8 = 2 · 4

(2 − 1)15 − 1 + 9 = 23 ≥ 20 = 5 · 4




 (3 − 1)15 − 1 + 9 = 38 ≥ 36 = 9 · 4


(4 − 1)15 − 1 + 9 = 53 ≥ 48 = 12 · 4




 (1 − 1)12 + 0 + 4 = 4 ≥ 4 = 1 · 4


(2 − 1)12 + 0 + 4 = 16 ≥ 16 = 4 · 4



(3 − 1)12 + 0 + 4 = 28 ≥ 28 = 7 · 4


(4 − 1)12 + 0 + 4 = 40 ≥ 40 = 10 · 4






(5 − 1)12 + 0 + 4 = 52 ≥ 52 = 13 · 4




 (1 − 1)10 − 2 + 6 = 4 ≥ 4 = 1 · 4





 (2 − 1)10 − 2 + 6 = 14 ≥ 12 = 3 · 4

(3 − 1)10 − 2 + 6 = 24 ≥ 24 = 6 · 4




 (4 − 1)10 − 2 + 6 = 34 ≥ 32 = 8 · 4


(5 − 1)10 − 2 + 6 = 44 ≥ 44 = 11 · 4






(6 − 1)10 − 2 + 6 = 54 ≥ 52 = 13 · 4


 (1 − 1)6 + 2 + 6 = 8 ≥ 8 = 2 · 4


(2 − 1)6 + 2 + 6 = 14 ≥ 12 = 3 · 4






(3 − 1)6 + 2 + 6 = 20 ≥ 20 = 5 · 4









 (4 − 1)6 + 2 + 6 = 26 ≥ 24 = 6 · 4

(5 − 1)6 + 2 + 6 = 32 ≥ 32 = 8 · 4

(2)


 (6 − 1)6 + 2 + 6 = 38 ≥ 36 = 9 · 4


(7 − 1)6 + 2 + 6 = 44 ≥ 44 = 11 · 4









 (8 − 1)6 + 2 + 6 = 50 ≥ 48 = 12 · 4

(9 − 1)6 + 2 + 6 = 56 ≥ 56 = 14 · 4






(10 − 1)6 + 2 + 6 = 62 ≥ 60 = 15 · 4


Task 2: Manual Scheduling

Given the task set in Table 3, determine a feasible cyclic-executive schedule.

3
 Task Period Deadline Execution Time
1 15 3 3
2 10 5 3
3 6 6 3

Table 3: A task set and schedule

Solution to Task 2:

We see from the table that the period P is 30, and we can use 3 as the frame f . Since this task set is a small
one, we can derive a feasible schedule graphically, see Fig. 2.

1 2 3 3 2 1 3 3 2 3

0 3 6 9 12 15 18 21 24 27 30

Figure 2: The schedule in Task 2

Task 3: Bonus Practice

Given the task set in Table 4, determine a feasible cyclic-executive schedule.

Task Period Deadline Execution Time

1 15 3 2
2 10 5 2
3 6 5 1
4 6 5 1

Table 4: A task set and schedule

Solution to Task 3:

We see from the table that the period P is 30, and we can use 3 as the frame f . Since this task set is a small
one, we can derive a feasible schedule graphically, see Fig. 3.

3 1 4 2 3 4 3 2 4 1 3 4 3 2 4

0 3 6 9 12 15 18 21 24 27 30

Figure 3: The schedule in Task 3