Page History: Publications

Björn Andersson and Eduardo Tovar
12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
August 2006 [pdf]

Consider the problem of scheduling a set of periodically arriving tasks on a multiprocessor with the goal of meeting deadlines. Processors are identical and have the same speed. Tasks can be preempted and they can migrate between processors. We propose an algorithm with a utilization bound of 66% and with few preemptions. It can trade a higher utilization bound for more preemptions and in doing so it has a utilization bound of 100%.

Björn Andersson and Eduardo Tovar
IPP-HURRAY technical Report HURRAY TR-060501
May 2004 [pdf]

Consider a set of periodically arriving real-time tasks scheduled on a single processor using rate-monotonic. We address the problem of deciding if and only if these tasks meet their deadlines; this is called exact schedulability analysis. We propose an algorithm for exact schedulability analysis of static-priority scheduled task sets and analyse its time-complexity. We prove that the time-complexity of the proposed algorithm can be expressed as a function of the utilisation (U) of the task set and that it is polynomial for any fixed U < 1. This is a major contribution to the state-of-the-art since, to the best of our knowledge, no other previously proposed schedulability analysis of static-priority scheduled task sets could claim to be exact while presenting polynomial time-complexity.

Liliana Cucu and Eduardo Tovar
ACM SIGBED Review, Volume 3, Number 1, January 2006; Also available as HURRAY TR-060102
January 2006 [pdf]

Real-time scheduling usually considers worst-case values for the parameters of task (or message stream) sets, in order to provide safe schedulability tests for hard real-time systems. However, worst-case conditions introduce a level of pessimism that is often inadequate for a certain class of (soft) real-time systems. In this paper we provide an approach for computing the stochastic response time of tasks where tasks have interarrival times described by discrete probabilistic distribution functions, instead of minimum inter-arrival (MIT) values.

Nuno Pereira, Eduardo Tovar, Berta Batista, Luis Miguel Pinho and Ian Broster
1st International Workshop on Probabilistic Analysis Techniques for Real-time and Embedded Systems
September 2004 [pdf]

Analytical models to provide timeliness guarantees tend to either be based on simplifications often leading to very pessimistic assumptions or consider more accurate techniques but at the cost of adding rather complex, difficult to handle, abstractions. Moreover, the more flexible and adaptive nature of current systems demand approaches for the timeliness evaluation problem based on probabilistic measures of meeting deadlines. It is in this context that simulation can emerge as an adequate solution to understand and analyze the timing behaviour of actual systems. However, special care must be taken with the obtained outputs under the penalty of obtaining results with lack of credibility. Particularly important, is to consider that we are more interested in values which are at the tail of a probability distribution (near worst-case probabilities), instead of deriving confidence on mean values. We approach this subject considering the randomness nature of simulation output data. In this, we will start by discussing well known approaches for estimating distributions out of simulation output, and the confidence which can be applied to its mean values. This will serve the basis to discuss on the applicability of these approaches to derive confidence on the tail of the distributions, where the worst-case is expected to be.