CprE 458/558: Real-Time SystemsUnderstanding FundamentalsPerformance MetricsUniprocessor - Some ResultsUniprocessor - More ResultsMultiprocessor – Some ResultMultiprocessor; Single Deadline; Non-premptiveMultiprocesing AnomaliesRun-time Anomaly - ExampleRate Monotonic Scheduling (RMS)Earliest Deadline First (EDF)CprE 458/558: Real-Time Systems (G. Manimaran) 1CprE 458/558: Real-Time Systems Scheduling ResultsRMS and EDF SchedulersCprE 458/558: Real-Time Systems (G. Manimaran) 2Understanding Fundamentals•Understanding the boundary between polynomial and NP-complete problems can provide insights into developing useful heuristics. •Understanding the algorithms that achieve some of the polynomial results can again provide basis for developing heuristics. •Understanding the fundamental limitations of on-line algorithms will help designers avoid scheduling anomalies and misconceptions.CprE 458/558: Real-Time Systems (G. Manimaran) 3Performance Metrics•Minimizing Schedule Length. •Minimizing Sum of Completion Times. •Maximizing Weighted Sum of Values (Useful in RT systems). •Minimizing the Maximum Lateness (useful in RT systems).CprE 458/558: Real-Time Systems (G. Manimaran) 4Uniprocessor - Some Results•One processor, Non-preemptive, Minimizing the Max. Lateness (Polynomial). •One processor, Non-preemptive, release time, Minimizing the Max. Lateness (NP-hard). •One processor, Preemptive, release time, Minimizing the Max. Lateness (Polynomial).CprE 458/558: Real-Time Systems (G. Manimaran) 5Uniprocessor - More Results•Result: When there are mutual exclusion constraints, it is impossible to find a totally on-line optimal scheduler. •Result: The problem of deciding whether it is possible to schedule a set of periodic tasks that use semaphores only to enforce mutual exclusion in NP-hard.•Overload Result: There does not exist an on-line scheduling algorithm with a competitive factor greater than 0.25.CprE 458/558: Real-Time Systems (G. Manimaran) 6Multiprocessor – Some Result•Result: The multiprocessing problem of scheduling on P processors with task preemption allowed and with minimization of the number of late tasks is NP-hard. •Result: EDF is not optimal in the multiprocessor case. •Result: For two or more processors, no deadline scheduling algorithm can be optimal without complete a prior knowledge of deadlines, computation times, and task ready times.•Result: No on-line scheduling algorithm can guarantee a cumulative value greater than one half for the dual processor case.CprE 458/558: Real-Time Systems (G. Manimaran) 7Multiprocessor; Single Deadline; Non-premptiveNP-completeness is mainly due to non-uniform task execution time and resource constraints.CprE 458/558: Real-Time Systems (G. Manimaran) 8Multiprocesing Anomalies•Assume that a set of tasks is optimally schedulable on a multiprocessor with some priority order, a fixed number of processors, fixed computation times, and precedence constraints.•Result: For the stated problem, changing the priority list, increasing the number of processors, reducing the computation times, or weakening the precedence constraints can increase the schedule length. •These anomalies may cause some of the already guaranteed tasks to miss their deadlines. •It can be shown that run-time anomalies cannot occur in a multiprocessor schedule when the tasks are independent.CprE 458/558: Real-Time Systems (G. Manimaran) 9Run-time Anomaly - ExampleRun-time anomaly may occur when the actual computation time of a task differs from its worst case computation time in a non-preemptive multiprocessor schedule with resource constraints. A processor is said to be work conserving if it is never idle when there is a task to execute. Any work conserving scheme may lead to run-time anomaly. Example: Ti=(ai ,ci ,di ) : T1=(0,20,22); T2=(0,12,25); T3=(10,8,26); T4=(8,10,30). T3 and T4 have resource conflicts; Actual computation time of T1 is 10.CprE 458/558: Real-Time Systems (G. Manimaran) 10Rate Monotonic Scheduling (RMS)•Schedulability check (off-line) - A set of n tasks is schedulable on a uniprocessor by the RMS algorithm if the processor utilization •Term n(21/n -1) approaches ln 2, (0.69 as n  ). - This condition is sufficient, but not necessary. •Schedule construction (online) - Task with the smallest period is assigned the highest priority. - At any time, the highest priority task is executed. RMS is an optimal preemptive scheduling algorithm with static priorities.CprE 458/558: Real-Time Systems (G. Manimaran) 11Earliest Deadline First (EDF)•Schedulability check (off-line) - A set of n tasks is schedulable on a uniprocessor by the EDF algorithm if the processor utilization - This condition is both necessary and sufficient. •Schedule construction (online) - Task with the smallest deadline is assigned the highest priority, - At any time, the highest priority task is executed. EDF is an optimal preemptive scheduling algorithm with dynamic priorities. EDF offers better schedulability than RMS, but it is more difficult to