Report

THE UNIVERSITY of TEHRAN Mitra Nasri Sanjoy Baruah Gerhard Fohler October 2014 Mehdi Kargahi Benefits ◦ No context switches ◦ Cache and pipelines are not affected by other tasks More precise estimation of WCET ◦ Simpler mechanisms to protect critical sections In some systems, preemption is either not allowed or too expensive Benefits from the application’s point of view Minimum I/O delay (the delays between sampling and actuation) On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 22of of 29 29 Non-Preemptive Scheduling is NP-Hard ◦ For Periodic Tasks [Jeffay 1991] ◦ For Harmonic Tasks [Cai 1996] ◦ For Harmonic Tasks with Binary Period Ratio [Nawrocki 1998] ki = {1, 2, 4, 8, 16, …} τi τi -1 Ti Period Ratio Ti -1 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 3 of 29 Schedulability test for npEDF, npRM, and Fixed Priority ◦ [Kim 1980, Jeffay 1991, George 1996, Park 2007, Andersson 2009, Marouf 2010,…] Heuristic scheduling algorithms ◦ Clairvoyant EDF [Ekelin 2006], Group-Based EDF [Li 2007] Optimal scheduling algorithms for special cases ◦ [Deogun 1986, Cai 1996, Nasri 2014] On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 4 of 29 [Deogun 1986]: An optimal algorithm if tasks have ◦ Constant integer period ratio K ≥ 3 An optimal scheduling algorithm is the one which guarantees all ifdeadlines [Cai 1996]: An optimal algorithm tasks have whenever a ◦ Constant period ratio K = 2, orexists feasible schedule Period Ratio ◦ Integer period ratio ki ≥ 3 Limitations Linear time in the number of jobs, exponential time in the number of tasks! Constructs an offline time table with exponential number of entries On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 5 of 29 Precautious-RM [Nasri 2014] is optimal if tasks have ◦ Constant period ratio K = 2 ◦ Integer period ratio ki ≥ 3 ◦ Arbitrary integer period ratio ki ≥ 1 and enough vacant intervals Precautious-RM is online and has O(n) computational and memory complexity (in the number of tasks) On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 6 of 29 We study ◦ The existence of a utilization-based test ◦ The pessimism in the existing necessary and sufficient test ◦ The efficiency of the recent processor speedup approach Then for special cases of harmonic tasks we present ◦ The schedulability conditions ◦ A more efficient speedup factor On the Optimality of RM and EDF A Framework to Construct Customized for Harmonic Non-preemptive PeriodsHarmonic for RTS Tasks 7 of 25 29 Task set τ = {τ1, τ2, …, τn} Ti is the period of τi ci is the WCET of τi ki is the period ratio of τi to τi-1 Deadlines are implicit; Di = Ti τi τi -1 Ti Period Ratio Ti -1 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 88of of 29 29 Is it possible to have a utilization-based test for non-preemptive scheduling of periodic tasks? [Liu 1973] EDF [Bini 2003] RM (Hyperbolic Bound) On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 99 of of 29 29 Utilization of a non-preemptive task set which cannot be scheduled by any clairvoyant scheduling algorithm, can be arbitrarily close to zero. 2 τ2:(2, 1/ε ) τ1:(ε, 1) ε ~0 ⇒ U~0 1/ε ε missed … 1 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 10 of 29 It is impossible to find any relation between utilizations such that if it holds, schedulability of any scheduling algorithm is guaranteed. We build an infeasible task set with those utilizations At least one deadline miss cn = 2(T1-cr) +ε τn c1 + c2 + … + cn-1 c1 + c2 + … + cn-1 τ1 to τn-1 … … T1-cr T1-cr +ε τ1 to τn-1 : T1 = T1 = … = Tn-1 = an arbitrary value c1 = u1T1, c2 = u2T2, … , cn-1 = un-1Tn-1 τn: cn = 2(T1-cr)+ ε Tn = cn/un On the cr =Optimality c1 + c2 +of…RM+ and cn-1 EDF for Non-preemptive Harmonic Tasks 11 of 29 [Jeffay 1991]: Necessary and sufficient conditions for the schedulability of periodic tasks with unknown release offsets (with npEDF): (for npEDF) Yes! Does it provide necessary conditions for task sets with known release offset? On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 12 of 29 29 12 of For task sets with no or known release offset, Jeffay’s conditions are only sufficient. This task set is feasible by npEDF, but it is rejected in Jeffay’s test On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 13 of 29 ci τi τi ci/S Ti … Processor with speed 1 … Processor with speed S [Thekkilakattil 2013] On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 14 of 29 29 14 of The speed S that guarantees the feasibility of a non-preemptive execution of a harmonic task set is upper bounded by The proof can be done by finding the bound on the maximum possible execution time of a non-preemptive task! S≤8 It may reduce U=1 to U’=0.125 15 of 29 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 15 of 29 Can we find cases where npEDF and npRM are optimal? Can we find better speedup factor? On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 16 of 29 29 16 of Schedulable! Non-Schedulable! What if the execution times are limited to ci ≤ T1 – c1? 17 of 29 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 17 of 29 If we have U ≤ 1 and ci ≤T1 – c1 can we guarantee schedulability? Intuition: maximum blocking will be bounded to T1 – c1 Is it enough? On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 18 of 29 29 18 of npRM and npEDF are not optimal for harmonic tasks with U ≤ 1 and ci ≤T1 – c1 This task set is infeasible The relation between periods cannot be ignored easily! On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 19 of 29 We can count the vacant intervals to make sure each task has its own place to be scheduled! On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 20 of 29 29 20 of A vacant interval is constructed by the slack of τ1 The number of vacant intervals is defined as c3 = T1 – c1 τ3 c2 = T1 – c1 τ2 τ1 V3 = 2 V2 = 3 c1 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 21 of 29 npRM and npEDF have no deadline miss if in the harmonic task set we have U ≤1 ci ≤T1 – c1 Vi ≥ 1, 1 < i < n; and Vn ≥ 0 τi … ci = T1 – c1 τ1 22 of 29 … c3 = T1 – c1 τ3 τ2 ki > 1 c2 = T1 – c1 c1 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 22 of 29 npEDF and npRM guarantee schedulability if ci ≤T1 – c1 and ki > 1, or ci ≤T1 – c1 and Vi ≥ 1 [Deogun 1986] ci ≤ 2(T1 – c1) and K ≥ 3 [Cai 1996] ci ≤ 2(T1 – c1) and K = 2 or ki ≥3 S is bounded to 2 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 23 of 29 29 23 of npEDF and npRM with speedup factor 2 are optimal for task sets with enough vacant interval or integer period ratio greater than 1 In ECRTS 2014, we have introduced a framework to construct customized harmonic periods. On the Optimality of RM and EDF It can be used to increase the applicability of our results. for Non-preemptive Harmonic Tasks 24 of 29 29 24 of On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 25 25ofof29 29 Non-preemptive RM (npRM) Precautious-RM (pRM) [Nasri 2014] Cai’s Algorithm (GSSP) [Cai 1996] Group-Based EDF (gEDF) [Li 2007] npEDF + Speedup Factor of [Thekkilakattil 2013] (TSP-EDF) npEDF + Our Speedup Factor (OSP-EDF) On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 26 of 29 Task sets ci ≤ 2(T1 – c1) Vi ≥ 1 ki ∊ {1, 2, …, 6} Parameter: u1 from 0.1 to 0.9 OSP-EDF, TSP-EDF, and Precautious-RM have no misses. gEDF has the highest amount of miss ratio. In this case, it is worse than npRM. The goal is to show the efficiency of the speedup of TSP- and OSP-EDF. On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 27 of 29 Negative Results Non-existence of any utilization-based test npEDF npRM Pessimism in the existing test For tasks with known release time Inefficiency of the recent processor speedup approach for many cases of harmonic tasks On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 28 of 29 29 28 of New Results Schedulability conditions with limited execution time npEDF npRM Extending those conditions to task sets with ki > 1 Deriving more efficient speedup factor when the execution time is not limited On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 29 of 29 29 29 of Thank you On the Optimality of RM and EDF A Framework to Construct Customized for Harmonic Non-preemptive PeriodsHarmonic for RTS Tasks 30 of 25 29 The speedup factor that guarantees feasibility of npRM and npEDF for task sets with U ≤ 1 and ci ≤ 2(T1 – c1) and Vi ≥ 1 (for 1 < i < n), and Vn ≥ 0 is bounded to S is bounded to 2 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 31 of 29 U ≤1 ci ≤ 2(T1 – c1) We call it the Slack Rule On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 32 of 29 We can use a sort of packing in the tasks so that in the formula, each vacant interval can be occupied by different subset of tasks. c2 + c5 + … + c j τ2 , τ5 , … , τj … c1 T2 … … τ1 T1- c1 We might be able to show that the problem of finding the minimum number of Vis is NP-Complete because it can reduces to subset sum problem. On the Optimality of RM and EDF A Framework to Construct Customized for Harmonic Non-preemptive PeriodsHarmonic for RTS Tasks 33 of 25 29 [Kim 1980]: Exact schedulability analysis for npEDF [Jeffay 1991]: ◦ Necessary and sufficient conditions for schedulability of npEDF for periodic tasks with unknown release phase ◦ npEDF is optimal among non-work conserving algorithms [George 1996, Park 2007, Andersson 2009]: Sufficient conditions for RM and FP algorithms [Marouf 2010]: Schedulability analysis for strictly periodic tasks On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 34 of 29 Clairvoyant EDF [Ekelin 2006] ◦ It looks ahead in the schedule and tries to … ◦ Not optimal Group-Based EDF [Li 2007] ◦ Creates groups of tasks with close deadlines ◦ Selects a task with the shortest execution time from a group with the earliest deadline ◦ Efficient for soft real-time tasks ◦ Not optimal On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 35 of 29 General task sets with limited execution time ◦ ci ≤ 2(T1 – c1 ) ◦ ki ∊ {1, 2, …, 6} ◦ Parameter: U from 0.1 to 0.9 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 36 of 29 TSP-EDF is only optimal algorithm (it uses S ≤ 8). OSP-EDF has in average only 1% miss ratio, however, it cannot guarantee schedulability because of not having Vi ≥ 1 condition. Precautious-RM is very efficient among other algorithms, yet it is not optimal. Note: some of those task sets are infeasible. On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 37 of 29 General task sets ◦ ki ∊ {1, 2, …, 6} ◦ Parameter: U from 0.1 to 0.9 (with uUniFast) On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 38 of 29 TSP-EDF is only optimal algorithm (it uses speedup). OSP-EDF has in average only 0.02 miss ratio, however, it cannot guarantee schedulability Precautious-RM is very efficient among other algorithms, yet it is not optimal. Note: many of those task sets are infeasible. On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 39 of 29 Feasible task sets ◦ ◦ ◦ ◦ ci ≤ T1 – c1 Vi ≥ 1 ki ∊ {1, 2, …, 6} Parameter: u1 from 0.1 to 0.9 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 40 of 29 gEDF has a lot of misses. GSSP cannot handle ki =1 Others have no misses Before u1=0.5, Cmax is usually from other tasks, after that c1 becomes larger than others [Thekkilakattil 1013] On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 41 of 29 The speed S that guarantees the feasibility of a non-preemptive execution of a harmonic task set is upper bounded by For the proof we use necessary condition ci ≤ 2(T1 – c1), thus: ◦ Cmax is either 2(T1 – c1) or c1 ◦ Dmin is T1 S≤8 It may reduce U=1 to U’=0.125 On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 42 of 29 npRM and npEDF are identical if the period is the tie breaker (for npEDF) RM and EDF are also identical From now on, any result for npRM is applicable on npEDF as well On the Optimality of RM and EDF for Non-preemptive Harmonic Tasks 43 of 29