2 University of Electronic Science Technology of China(UESTC) Chapter 4 Task Management Real-Time Systems Lab LIAO Yong
2 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) Chapter 4 Task Management
3 1 Overview University of Electronic Science Technology of China(UESTC) Task management Scheduling Policy Synchronization,Communication,Mutex Coordinate mechanism Memory management Inventory management mechanism Interruption Time management Event dealing mechanisms: Event-triggered mechanism Time-triggered mechanism Real-Time Systems Lab LIAO Yong
3 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 1 Overview Task management Synchronization,Communication,Mutex Memory management Interruption & Time management Event dealing mechanisms: Event-triggered mechanism Time-triggered mechanism Coordinate mechanism Inventory management mechanism Scheduling Policy
4 2 Task management University of Electronic Science Technology of China(UESTC) _What does the kernel do Scheduling What does the kernel scheduling Tasks >What are tasks Real-Time Systems(RTS)? >Characteristics of tasks o Concurrence (Simultaneousness) Scheduler o Dynamic o Asynchrony Independence (Synchrony dependence) 0… Real-Time Systems Lab LIAO Yong
4 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management What does the kernel do ? Scheduling What does the kernel scheduling ? Tasks What are tasks & Real-Time Systems (RTS)? Characteristics of tasks o Concurrence (Simultaneousness) o Dynamic o Asynchrony & Independence (Synchrony & dependence) o …… Scheduler
5 2 Task management University of Electronic Science Technology of China(UESTC) >Classification of tasks o Periodic tasks o Sporadic tasks o Aperiodic tasks Critical tasks Non-critical tasks Hard real-time tasks √Soft real--time tasks Real-Time Systems Lab LIAO Yong
5 Real-Time Systems Lab LIAO Yong University of Electronic Science & Technology of China (UESTC) 2 Task management Classification of tasks o Periodic tasks o Sporadic tasks o Aperiodic tasks Critical tasks Non-critical tasks Hard real-time tasks Soft real-time tasks
6 2 Task management University of Electronic Science Technology of China(UESTC) How to schedule tasks on processor to ensure that their deadlines are met >Tasks and their special requirements o Task: T（=1,2,n) o Task number: n o Period: P o Executing time: e; o Relative deadline: D o Absolute deadline: d What's the difference between task and process? o Release time: ri Time related parameters o Phasing: 工 Real-Time Systems Lab LIAO Yong
6 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 ? Tasks and their special requirements ? o Task: Ti ( i=1,2,…,n ) o Task number: n o Period: Pi o Executing time: ei o Relative deadline: Di o Absolute deadline: di o Release time: ri o Phasing: Ii What's the difference between task and process? Time related parameters
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