7 2 Task management University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met Special measures for Guaranteeing task deadlines o Preemptive 0 Periodic task o Relative deadline (D)=Period (P) 0 Priority is inversely related to the period (P) 0 Other assumptions: 1)The cost of Preemption is negligible 2) Only processing requirements are significant 3)Tasks are independent,no precedence constraints Real-Time Systems Lab LIAO Yong
7 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management How to schedule tasks on processor to ensure that their deadlines are met ? Special measures for Guaranteeing task deadlines o Preemptive o Periodic task o Relative deadline (Di ) o Priority o Other assumptions: 1) The cost of Preemption is negligible 2) Only processing requirements are significant 3) Tasks are independent, no precedence constraints is inversely related to the period (Pi ) = Period (Pi )
8 2 Task management University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met What does the scheduler do for Guaranteeing task deadlines 1)Which task should be executed by the processor? 2)When does a task begin to execute? 3)How long is a task executing Priority is inversely related to the period (P) Real-Time Systems Lab LIAO Yong
8 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management How to schedule tasks on processor to ensure that their deadlines are met ? What does the scheduler do for Guaranteeing task deadlines ? 1) Which task should be executed by the processor? 2) When does a task begin to execute? 3) How long is a task executing ? Priority is inversely related to the period (Pi )
9 2 Task management University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met How to know a given scheduling policy can Guarantee task deadlines 1)Schedulability analysis on the policy (following) Priority is inversely related to the period (P) Real-Time Systems Lab LIAO Yong
9 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management How to schedule tasks on processor to ensure that their deadlines are met ? How to know a given scheduling policy can Guarantee task deadlines ? 1) Schedulability analysis on the policy (following) Priority is inversely related to the period (Pi )
10 2 Task management University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met Necessary and sufficient conditions for schedulability If mine t ≤L,task7,isschedulable. yfs欧lmmg》s1,are化，网enne entire set T is schedulable. T={P,l=1,2,i;=1,2,…[P/P]} i={1,2,, Real-Time Systems Lab LIAO Yong
10 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management How to schedule tasks on processor to ensure that their deadlines are met ? Necessary and sufficient conditions for schedulability If , task Ti min 1 is schedulable. i i t W t If , for i∈{1,…,n},then the entire set T is schedulable. max {min } 1 {1,..., } i i i n t W t τi={lPi | j=1,2,…,i ; l=1,2,…,[ Pi /Pj ]} i={1,2,…,n}
11 2 Task management University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met >Example i e P 1 20 100 2 30 150 3 80 210 4 100 400 Real-Time Systems Lab LIAO Yong
11 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management How to schedule tasks on processor to ensure that their deadlines are met ? Example i ei Pi 1 20 100 2 30 150 3 80 210 4 100 400