IMPROVING THE PERFORMANCE OF LOCAL REAL-TIME SCHEDULING
Gabriel Wainer · 2007
IMPROVING THE PERFORMANCE OF LOCAL REAL-TIME SCHEDULINGGabriel A. WainerComputer Sciences Department.Facultad de Ciencias Exactas y Naturales.Universidad de Buenos Aires. Pabellon I - Ciudad Universitaria.Buenos Aires - [email protected]://www.angelfire.com/ga/gwAbstract: In this work the results of two simple strategies to improve the performance oflocal real-time schedulers are presented. The main goals are to increase system stabilityunder transient overloads and to improve the use of system resources when tasks havestochastic execution times. To do so, traditional schedulers are combined with a multiplequeue algorithm and an on-line guarantee test. Results obtained through simulationallowed to detect improvements in system time loading and stability.Keywords: Real-Time, scheduling algorithms, stability, stochastic parameters,performance analysis.1. INTRODUCTION presented. The policies can be combined withdifferent existing task models, and can be used withIn Real-Time systems the moment when a result is static or dynamic schedulers.computed is as important as its logical correctness.One way to meet systems' timing constraints is torely on a real-time scheduler. The scheduler shouldensure system predictability, but the restrictions inthese systems are so diverse that this guarantee is anNP-hard problem.One goal is to improve stability allowing theexecution of the most crucial tasks when the systemis overloaded. Another one is to increase resourceuse when execution times are below the worst cases.There are different ways used to lower thecomplexity of the guarantee tests. Some solutionsconsider all the system's restrictions (includingtimeliness, criticality, precedence, concurrence,communication, etc.) and use heuristics to reducethe search time. Other approaches use simpler taskmodels to solve less generic problems (most of thelocal schedulers use this policy). These simple taskmodels are usually improved to solve new problems,but at the cost of extra complexity (and overhead).In this work low overhead techniques to improvethe performance of local real-time schedulers are2. IMPROVING STABILITYSeveral scheduling algorithms rely on a well-knowntask model, usually called the periodic task's model.It considers the existence of two different kinds oftasks to schedule: the periodic and sporadic(aperiodic) ones. Periodic tasks have a continuousseries of regular invocations (whose time is calledthe period), and a worst case execution time(WCET). The task deadline is at the beginning ofthe next period. Aperiodic tasks have arbitraryarrival time and deadline, and a known WCET.