Real-time Limited Preemptive Scheduling
José Manuel Silva dos Santos Marinho · Open Repository of the University of Porto (University of Porto) · 2015
Physical phenomenons, regardless of its degree of human intervention, from the more pristine to the more vain facets of some human made appliance, require controlling strategiesto achieve an intended set of properties or some performance level. The controllers’ implementation may range from the simpler mechanical or analog circuitry but more commonlyare embodied as a recurrent set of commands on some computational boolean logic device.The dynamic properties of such physical phenomenons, paired with the designer intendedbehaviour, impose restrictions on the maximum delay between an event and the desired actuation. Real-time systems strive to provide a framework where the considerations aboutthe overall system’s temporal feasibility are drawn. In a nutshell, real-time systems enableguarantees on the temporal properties of the computational apparatus which are used insuch control loops. Any analysis used in the hard real-time framework should be provensafe. This generally means that the outcome of any analysis states whether all the temporal properties can be guaranteed or that some cannot be trusted upon. The quantity ofpessimism involved in the analysis – which leads to an abundance of false negatives or toan over-provisioning of resources – should be reduced as much as possible. Analysis’ pessimism can be thought of, in broad terms, as an artefact of the lack of information necessaryto accurately characterize the worst-case temporal behaviour of each application. The pessimism can only be mitigated by employing mechanisms where more abundant informationabout the worst-case run-time behaviour is available. These mechanism should neverthelesshave a better or comparable performance to the ones with reduced certainties.In this thesis both scheduling algorithms and accompanying analysis tools are providedwhich, by enhancing the available information about what might happen at run-time, allowfor a reduction on the level of pessimism associated with the analysis outcomes and bringa better performance in the average case situation. An interesting aspect pertaining to realtime systems is the nature and implications associated with pre-emption. A pre-emptionoccurs when an application is swapped for another in the execution platform to which iteventually returns. Besides from the time the pre-empting application prevents the preempted one from executing, some shared resources are accessed by the former which willpotentially interfere with the remaining execution of the latter. The nature of the interferenceoccurring at such resources as the caches or dynamic branch predictors just to name a fewis highly complex to analyse and generally a single and oftenly quite isolated worst-casequantity is assumed in the state-of-the-art real-time analysis.The quantification of the worst-case penalty associated to preemptions and the bounding their frequency of occurrence constitutes the bulk of this thesis’ contribution. Bothscheduling algorithms as well as analysis are provided that both decrease the worst-casenumber of preemptions and also diminish the penalty considered per instance of this event. FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Real-time Limited Preemptive Scheduling Jose Manuel Silva dos Santos Marinho Doutoramento em Engenharia Electrotecnica e de Computadores Orientador: Stefan Markus Ernst Petters (Dr.)