Slide 1Basic concepts (1)N-periodic tasksRules for designing cyclic scheduleExampleCyclic Executive DesignSlide 7Static ScheduleSummaryPA G E S 8 3 - 8 7 C H A P T E R 401/14/20191Clock-driven Static schedulingBasic concepts (1)01/14/20192A periodic task is denoted by {tai, ei ,pi, Di} where the attributes are arrival time, execution time, period and relative deadline for task iFor example {0, 5, 12, 7} means Arrival timeExecution timedeadlineperiodNext arrival timeHow will the timing diagram be for {1, 5, 12, 7} and for {0, 5,12, 12}? Discuss.N-periodic tasks01/14/20193n 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.Rules for designing cyclic schedule01/14/201940. if Utilization >1, the tasks cannot be scheduled in the same processor.If U is okay, Hyperperiod H is lcm (pi) + these constraints1. 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.Example 01/14/20195ti ri ei pi Dit10 1 4 4t20 1.8 5 5t30 1.0 20 20t402.0 20 20Given the task set above design the cyclic executive schedule or clock driven static schedule.Cyclic Executive Design01/14/20196Hyper-period is integer multiple of lcm(pi)= lcm (4,5,20,20) = 20Frame is max of ei’s: max{1,1.8,2,2} = 2f value of 2 evenly divides hyper-period value of 202f – gcd(pi,f) ≤ Di (satisfied as shown below)2X2 – gcd(4,2) = 4-2 <= 42X 2 – gcd(5,2) = 4-1 <= 52X2 – gcd(20,4) = 4-4 <= 202X2 – gcd(20,4) = 4-4 <= 20Design f = 2, hyperperiod = 20t1t3t2t2t1t4t4t2t2t1t2t2t1t2t2t11 2 3 4 5 6 7 8 9 1011121314151617181920t1,t2,t3,t4frameHyper-periodt1 t2t1 t2t1t2t1t1,t2,t3,t4repeatsBurn or base or aperiodic taskscan use this slot01/14/20197Static Schedule01/14/20198{{ 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 eachSummary01/14/20199We 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 bookClock-driven schedulinghttp://csperkins.org/teaching/rtes/lecture04.pdfMars Pathfinder: pages 169-171, Chapter
View Full Document
Unlocking...