Discussion: SchedulingOutlineIntroductionAssumption of environmentSlide 5Rate Monotonic SchedulingRMS (cont’d)Slide 8Slide 9Slide 10Deadline Driven SchedulingSlide 12Mixed scheduling algorithmMixed scheduling algorithm (cont’d)QuestionsEE 249, Fall 2002 1Discussion: SchedulingHaibo ZengAmit MahajanEE 249, Fall 2002 2OutlineProblem: multi-program scheduling on a single processorOptimum fixed priority scheduler – rate monotonic schedulingOptimum dynamic scheduling algorithm – deadline driven schedulingMixed scheduling algorithmEE 249, Fall 2002 3IntroductionEnvironment: hard-real-time vs. soft-real-timeScheduling: Preemptive and priority drivenFixed priority vs. dynamicEE 249, Fall 2002 4Assumption of environmentA1: The requests for all tasks with hard deadlines are periodicA2: Task deadline is its next requestA3: The tasks are independentA4: Run-time for each task is constantA5: Nonperiodic tasks have no deadlinesEE 249, Fall 2002 5OutlineProblem: multi-program scheduling on a single processorOptimum fixed priority scheduler – rate monotonic schedulingOptimum dynamic scheduling algorithm – deadline driven schedulingMixed scheduling algorithmEE 249, Fall 2002 6Rate Monotonic SchedulingAccording to their request rates onlyHigher request rates, higher prioritiesOptimum fixed priority scheduling: feasible if any feasible fixed priority assignment existsProof: Use the concept critical instant to analyze the case of scheduling two tasksEE 249, Fall 2002 7RMS (cont’d)Proof: Use the concept critical instant to analyze the case of scheduling two tasksResult: assign higher priorities to task with shorter request period; independent of their run-times. Generalize this result to m tasksEE 249, Fall 2002 8RMS (cont’d)Available Processor Utilization can be as low as:Analysis:Right hand side of the inequality is monotonic decreasing with m )12(//11mmiiimTCU%3.692ln)12(/1limmmmEE 249, Fall 2002 9RMS (cont’d)Question:Why utilization factor can’t reach 100%? Answer:Processor idle time: exampleQuestion:How to relax the utilization bound?Answer:For i=1,2,…,m-1,Better choice: dynamic priority assignmentiimTkT EE 249, Fall 2002 10OutlineProblem: multi-program scheduling on a single processorOptimum fixed priority scheduler – rate monotonic schedulingOptimum dynamic scheduling algorithm deadline driven schedulingMixed scheduling algorithmEE 249, Fall 2002 11Deadline Driven SchedulingAccording to their request rates: earliest deadline first (EDF)No processor idle time before overflowSchedulable iff processor use is less than 1Optimum scheduling algorithm: feasible if any feasible assignment existsEE 249, Fall 2002 12OutlineProblem: multi-program scheduling on a single processorOptimum fixed priority scheduler – rate monotonic schedulingOptimum dynamic scheduling algorithm – deadline driven schedulingMixed scheduling algorithmEE 249, Fall 2002 13Mixed scheduling algorithmNice for many applicationsInterrupt hardware: fixed priority schedulerOther software tasks: dynamic priority schedulerScheduling algorithmK tasks of shortest periods: RMSRemaining slower paced tasks: EDFEE 249, Fall 2002 14Mixed scheduling algorithm (cont’d)Comparison with RMS and EDF:Still can’t reach 100% utilizationBut much better than RMSExample with 3 tasksT1=3, T2=4, T3=5C1=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 15QuestionsOverhead we ignored?Dynamic schedulingPreemptionIf 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
View Full Document
Unlocking...