Scribd
Upload
22 views4 pages

Cyclic Executive Scheduling Solution

1) The document provides a sample solution to determine the feasibility of a cyclic-executive scheduling problem for 4 tasks. 2) It determines that the schedule is feasible by showing that the period is a common multiple of all task periods, the period is a multiple of the frame, and the frame is sufficiently long to complete all task executions by their deadlines. 3) It calculates the initial phase for each task to ensure executions start after release and finish by the deadline.

Uploaded by

quoctrung244
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views4 pages

Cyclic Executive Scheduling Solution

1) The document provides a sample solution to determine the feasibility of a cyclic-executive scheduling problem for 4 tasks. 2) It determines that the schedule is feasible by showing that the period is a common multiple of all task periods, the period is a multiple of the frame, and the frame is sufficiently long to complete all task executions by their deadlines. 3) It calculates the initial phase for each task to ensure executions start after release and finish by the deadline.

Uploaded by

quoctrung244
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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

Common questions

Powered by AI

The task period dictates how frequently a task should be revisited, the execution time specifies how long it takes to complete, and the deadline determines the maximum allowable period for completion after its release. For a schedule to be feasible, these parameters must align such that the periodic executions adhere to timing constraints, maintaining continuous system operation without missing deadlines, as thoroughly developed in Tasks 1, 2, and 3 .

Using a graphical method to derive a feasible schedule for small task sets makes it easier to visualize and check the execution sequences against deadlines. This approach helps in quickly spotting feasibility issues and verifying timing constraints intuitively, as shown in the solutions to Task 2 and Task 3, where periods, frames, and task deadlines are easily illustrated .

Manual adjustments in cyclic-executive scheduling allow for tweaking the start times and sequences of tasks to better meet deadlines, handle task execution variances, and optimize resource utilization. These adjustments, as illustrated in various tasks from the source, can help achieve a feasible schedule where automated calculations may initially fail, especially in smaller or more nuanced task sets where specific conditions or priorities must be accounted for .

Verifying deadlines ensures that each task can be completed within its allowable time frame. It involves checking that after the initial release time and execution duration, the task does not exceed its specified deadline. This step is crucial for determining if all tasks in the schedule fit within legal time bounds, especially as shown in the given frames where execution time must not breach set deadlines for practical cyclic execution .

The frame length f must be sufficiently long to accommodate the maximum execution time of any task during one frame while ensuring that multiple tasks scheduled in a single frame do not exceed the frame's length. This is done by verifying that the sum of the execution times for all tasks scheduled for a particular frame is less than or equal to the frame length, which in this case is demonstrated through Table 2 and confirmed by drawing the schedule .

Task offset determination directly impacts when each task begins execution relative to its release. Correct offsets ensure that tasks do not start too early, thus violating time constraints, or too late, risking deadline breaches. The offsets calculated ensure that execution starts within set intervals, thus maintaining both task order and timely completion across overlapping cycles .

The period being a common multiple of task periods ensures that the task set can be scheduled cyclically without conflict. It aligns the tasks to repeat their schedules after the least common multiple, avoiding overlap and contention for resources, thus ensuring all task deadlines can be systematically met over the repeated cycle. For instance, in Task 1, the period P is a common multiple, allowing cyclic scheduling across 60 units without practical issue .

The initial phase for each task is determined by calculating offsets for each task instance such that the start of execution occurs after the release time. The formula used is Φi = min 1≤j≤P/Ti {(fi,j − 1)f − (j−1)Ti} for each task i, where fi,j is the frame in which the task instance executes. The specific offsets for each task are computed to satisfy this condition, ensuring the deadlines respected are greater than their respective arrival time plus offsets .

Cyclical scheduling is less effective for systems with dynamic task loads due to its inherent rigidity, as tasks must fit predetermined cycle slots without regard for real-time fluctuations. Fixed scheduling or adaptive approaches might better accommodate variability by dynamically addressing priorities and resource allocation on-the-fly, providing more flexibility and responsiveness compared to the structured but unadaptable setup of cyclic-executive schedules .

To determine if a cyclic-executive schedule is feasible, several factors must be considered: the period P should be a common multiple of all task periods (as ensured in Table 1), P should be a multiple of the frame length f (15 * f = P as given), the frame f should be sufficiently long to accommodate task execution times within their deadlines, and each task instance should start execution after its release and finish before its deadline. Using the offsets calculated, deadlines for task instances are verified against their respective release times and periods .

You might also like