Clock-Driven Static Scheduling Basics
Learn about clock-driven static scheduling and basic concepts such as periodic tasks, N-periodic tasks, rules for designing cyclic schedule, and cyclic executive design. Explore examples and understand how tasks are scheduled based on arrival time, execution time, period, and deadline attributes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Clock-driven Static scheduling 1 PAGES 83-87 CHAPTER 4 4/13/2025
Basic concepts (1) 2 A periodic task is denoted by {tai, ei ,pi, Di} where the attributes are arrival time, execution time, period and relative deadline for task i For example {0, 5, 12, 7} means period Execution time deadline Arrival time Next arrival time How will the timing diagram be for {1, 5, 12, 7} and for {0, 5,12, 12}? Discuss. 4/13/2025
N-periodic tasks 3 n periodic tasks with {tai, ei ,pi, Di} with i = 1..n need to be scheduled. Since the four parameters known ahead the scheduling is static and a cyclic executive can be designed to schedule (& execute) the tasks so that they meet their respective deadlines. Utilization Ui = (ei/pi) Improve utilization by slack stealing to schedule a aperiodic task from the queue of aperiodic tasks. 4/13/2025
Rules for designing cyclic schedule 4 0. if Utilization >1, the tasks cannot be scheduled in the same processor. If U is okay, Hyperperiod H is lcm (pi) + these constraints 1. Frame f max(ei) 2. Frame f should evenly divide H. 3. There should be at least 1 frame between release time of a task and its deadline: 2f gcd(pi,f) Di Very often Di and Pi are same for periodic task. For simplicity in discussion we will assume this default setting. 4/13/2025
Example 5 ti t1 t2 t3 t4 ri 0 0 0 0 ei 1 1.8 1.0 2.0 pi 4 5 20 20 Di 4 5 20 20 Given the task set above design the cyclic executive schedule or clock driven static schedule. 4/13/2025
Cyclic Executive Design 6 Hyper-period is integer multiple of lcm(pi)= lcm (4,5,20,20) = 20 Frame is max of ei s: max{1,1.8,2,2} = 2 f value of 2 evenly divides hyper-period value of 20 2f gcd(pi,f) Di (satisfied as shown below) 2X2 gcd(4,2) = 4-2 <= 4 2X 2 gcd(5,2) = 4-1 <= 5 2X2 gcd(20,4) = 4-4 <= 20 2X2 gcd(20,4) = 4-4 <= 20 Design f = 2, hyperperiod = 20 4/13/2025
t1,t2,t3,t4 t1,t2,t3,t4 t1 t2 t1 t2 t1 t1 t2 t1 1 t3 t2 t2 t1 2 3 t4 t4 t2 t2 t1 7 8 9 t2 t2 t1 12 13 14 15 16 17 t2 t2 t1 18 19 2 4 5 6 10 11 0 frame Hyper-period Burn or base or aperiodic tasks can use this slot repeats 7 4/13/2025
Static Schedule 8 { { t1(1); t3(1)} {t2(1.8}} {t1(1); burn(1)} {t4(2)} {t2(2)} {t1(1); burn(1)} {t2(2)} {t1(1);burn(1)} {t2(2)} {t1(1);burn(1)} } A cyclic executive of 10 frames with 2 slots each 4/13/2025
Summary 9 We studied formal design of a cyclic executive. The algorithm discussed is proven method to generate a cyclic executive for a set of period tasks defining a RTOS. Reference: Pages 83-87 of Chapter 4 of text book Clock-driven scheduling http://csperkins.org/teaching/rtes/lecture04.pdf Mars Pathfinder: pages 169-171, Chapter 8 4/13/2025
