2 Task management 12 University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met Whether the scheduling policy can guarantee the task deadlines if I<>0(i=1,2......n? o Response time p131 Properties of the scheduling policy o A set of tasks is said to fully utilize the processor if ..... o Theorem:If a task set is such that the processor utilization is no greater n2(1/m-1),the task set is schedulable under the policy(sufficient condition) > This scheduling policy is called RM (Rate-Monotonic) scheduling algorithm C.Liu,Layland,"Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment",Journal of ACM. Real-Time Systems Lab LIAO Yong
12 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 ? Whether the scheduling policy can guarantee the task deadlines if Ii<> 0 ( i =1 , 2…… n) ? o Response time p131 Properties of the scheduling policy o A set of tasks is said to fully utilize the processor if …… o Theorem: If a task set is such that the processor utilization is no greater n(2 (1/n) -1), the task set is schedulable under the policy (sufficient condition) This scheduling policy is called RM (Rate-Monotonic) scheduling algorithm C. Liu, Layland,“Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”, Journal of ACM
13 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 use the Theorem of RM scheduling algorithm > What can we learn from RM scheduling algorithm How to handling critical sections o Priority inversion Unpredictability of RM o Priority inheritance o Priority ceiling o Theorm:Any set of n periodic tasks that fully utilizes the processor under the RM scheduling policy must have, for each∈{1,2，. e/P+e/B+..+e/P +P=i(2w0-1) Real-Time Systems Lab LIAO Yong
13 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 handling critical sections o Priority inversion o Priority inheritance o Priority ceiling o Theorm: Any set of n periodic tasks that fully utilizes the processor under the RM scheduling policy must have, for each i ∈ {1,2,…n} e1 /P1+ e2 /P2+…+ ei /Pi+ bi /Pi<= i (2 (1/i) -1) How to use the Theorem of RM scheduling algorithm ? What can we learn from RM scheduling algorithm ? Unpredictability of RM
14 2 Task management University of Electronic Science Technology of China(UESTC) Other problems to be considered Handling critical sections If the tasks are not periodic...... o Reserve a fictitious highest priority task for sporadic tasks 0 EDF(Earliest Deadline First)Policy 1)Schedule the task whose absolute deadline is the earliest 2)No periodic assumption 3)Necessary and sufficient conditions for schedulability 之号≤1 re =1 Real-Time Systems Lab LIAO Yong
14 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management Other problems to be considered Handling critical sections If the tasks are not periodic …… o Reserve a fictitious highest priority task for sporadic tasks o EDF (Earliest Deadline First) Policy 1) Schedule the task whose absolute deadline is the earliest 2) No periodic assumption 3) Necessary and sufficient conditions for schedulability 1 1 n i i i e D also suitable for periodic task
15 2 Task management University of Electronic Science Technology of China(UESTC) Other problems to be considered o EDF(Earliest Deadline First)Policy 4)Drawbacks of EDF 5)Dynamic scheduling Static scheduling 0 DM (Deadline Monotonic) 1)Evaluation of DM >A simulator which can generate aperiodic tasks with Poisson arrivals,exponentially distributed execution times, and uniformly distributed deadlines. >Each point on each curve in the figures is the average of 10 experiments,each carried out for a sufficiently long time 33000 task arrivals).Multiple experiments per point to guard against bias for a particular random number generator seed. Real-Time Systems Lab LIAO Yong
15 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management Other problems to be considered o EDF (Earliest Deadline First) Policy 4) Drawbacks of EDF 5) Dynamic scheduling & Static scheduling o DM (Deadline Monotonic) 1) Evaluation of DM A simulator which can generate aperiodic tasks with Poisson arrivals, exponentially distributed execution times, and uniformly distributed deadlines. Each point on each curve in the figures is the average of 10 experiments, each carried out for a sufficiently long time 33000 task arrivals). Multiple experiments per point to guard against bias for a particular random number generator seed
16 2 Task management University of Electronic Science Technology of China(UESTC) >Metrics 1)Timeliness the measured CPU utilization 2)Success ratio:the percentage of tasks that make their deadlines .心 3)Efficiency:the number of tasks admitted using the admission control scheme divided by the number of tasks that meet their deadlines under the same scheduling policy if no admission control is used. 4)Effective utilization:the utilization due to tasks which meet their deadlines only. 5)Throughput 6)Overhead of scheduling Factors that affect the performance Real-Time Systems Lab LIAO Yong
16 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) Metrics 1) Timeliness & the measured CPU utilization 3) Efficiency: the number of tasks admitted using the admission control scheme divided by the number of tasks that meet their deadlines under the same scheduling policy if no admission control is used. 2) Success ratio: the percentage of tasks that make their deadlines. 4) Effective utilization: the utilization due to tasks which meet their deadlines only. 5) Throughput 6) Overhead of scheduling 2 Task management Factors that affect the performance