Discussion Scheduling Haibo Zeng Amit Mahajan EE 249 Fall 2002 1 Outline Problem multi program scheduling on a single processor Optimum fixed priority scheduler rate monotonic scheduling Optimum dynamic scheduling algorithm deadline driven scheduling Mixed scheduling algorithm EE 249 Fall 2002 2 Introduction Environment hard real time vs soft real time Scheduling Preemptive and priority driven Fixed priority vs dynamic EE 249 Fall 2002 3 Assumption of environment A1 The requests for all tasks with hard deadlines are periodic A2 Task deadline is its next request A3 The tasks are independent A4 Run time for each task is constant A5 Nonperiodic tasks have no deadlines EE 249 Fall 2002 4 Outline Problem multi program scheduling on a single processor Optimum fixed priority scheduler rate monotonic scheduling Optimum dynamic scheduling algorithm deadline driven scheduling Mixed scheduling algorithm EE 249 Fall 2002 5 Rate Monotonic Scheduling According to their request rates only Higher request rates higher priorities Optimum fixed priority scheduling feasible if any feasible fixed priority assignment exists Proof Use the concept critical instant to analyze the case of scheduling two tasks EE 249 Fall 2002 6 RMS cont d Proof Use the concept critical instant to analyze the case of scheduling two tasks Result assign higher priorities to task with shorter request period independent of their run times Generalize this result to m tasks EE 249 Fall 2002 7 RMS cont d Available Processor Utilization can be as low as m U Ci Ti m 21 m 1 i 1 Analysis Right hand side of the inequality is monotonic decreasing with m 1 m m 2 1 ln 2 69 3 lim m EE 249 Fall 2002 8 RMS cont d Question Answer Processor idle time example Question Why utilization factor can t reach 100 How to relax the utilization bound Answer For i 1 2 m 1 Tm kiTi Better choice dynamic priority assignment EE 249 Fall 2002 9 Outline Problem multi program scheduling on a single processor Optimum fixed priority scheduler rate monotonic scheduling Optimum dynamic scheduling algorithm deadline driven scheduling Mixed scheduling algorithm EE 249 Fall 2002 10 Deadline Driven Scheduling According to their request rates earliest deadline first EDF No processor idle time before overflow Schedulable iff processor use is less than 1 Optimum scheduling algorithm feasible if any feasible assignment exists EE 249 Fall 2002 11 Outline Problem multi program scheduling on a single processor Optimum fixed priority scheduler rate monotonic scheduling Optimum dynamic scheduling algorithm deadline driven scheduling Mixed scheduling algorithm EE 249 Fall 2002 12 Mixed scheduling algorithm Nice for many applications Interrupt hardware fixed priority scheduler Other software tasks dynamic priority scheduler Scheduling algorithm K tasks of shortest periods RMS Remaining slower paced tasks EDF EE 249 Fall 2002 13 Mixed scheduling algorithm cont d Comparison with RMS and EDF Still can t reach 100 utilization But much better than RMS Example with 3 tasks T1 3 T2 4 T3 5 C1 1 C2 1 C3 1 rate monotonic 2 mixed RMS U 1 3 1 4 1 5 78 3 Mixed scheduling algorithm U 1 3 1 4 2 5 98 3 EE 249 Fall 2002 14 Questions Overhead we ignored Dynamic scheduling Preemption If programs are nonterminating how about the resources Are the assumptions about environment always fine If A1 or A4 don t hold what do we do Is A3 suitable for embedded systems EE 249 Fall 2002 15
View Full Document
Unlocking...