HomePublicationsPhD Thesis

Real-time Limited Preemptive Scheduling
Ref: CISTER-TR-150609       Publication Date: 24, Apr, 2015

Abstract:
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 strategies to achieve an intended set of properties or some performance level. The controllers’ implementation may range from the simpler mechanical or analog circuitry but more commonly are embodied as a recurrent set of commands on some computational boolean logic device. The dynamic properties of such physical phenomenons, paired with the designer intended behaviour, impose restrictions on the maximum delay between an event and the desired actuation. Real-time systems strive to provide a framework where the considerations about the overall system’s temporal feasibility are drawn. In a nutshell, real-time systems enable guarantees on the temporal properties of the computational apparatus which are used in such control loops. Any analysis used in the hard real-time framework should be proven safe. 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 of pessimism involved in the analysis – which leads to an abundance of false negatives or to an 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 necessary to accurately characterize the worst-case temporal behaviour of each application. The pessimism can only be mitigated by employing mechanisms where more abundant information about the worst-case run-time behaviour is available. These mechanism should nevertheless have a better or comparable performance to the ones with reduced certainties. In this thesis both scheduling algorithms and accompanying analysis tools are provided which, by enhancing the available information about what might happen at run-time, allow for a reduction on the level of pessimism associated with the analysis outcomes and bring a 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-emption occurs when an application is swapped for another in the execution platform to which it eventually returns. Besides from the time the pre-empting application prevents the preempted one from executing, some shared resources are accessed by the former which will potentially interfere with the remaining execution of the latter. The nature of the interference occurring at such resources as the caches or dynamic branch predictors just to name a few is highly complex to analyse and generally a single and oftenly quite isolated worst-case quantity is assumed in the state-of-the-art real-time analysis. The quantification of the worst-case penalty associated to pre-emptions and the bounding their frequency of occurrence constitutes the bulk of this thesis’ contribution. Both scheduling algorithms as well as analysis are provided that both decrease the worst-case number of pre-emptions and also diminish the penalty considered per instance of this event.

José Marinho

Document:

View
PDF Download
PDF