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
15th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS'07, March 26-27, Long Beach, California, USA; Also available as HURRAY TR-070101
August 2007 [pdf]

Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor $p$ has the speed $S_p$. Tasks can be preempted but they cannot migrate between processors. We propose an algorithm which can schedule all task sets that any other possible algorithm can schedule assuming that our algorithm is given processors that are three times faster.

Björn Andersson and Eduardo Tovar
13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 21-24, Daegu, Korea; Also available as HURRAY TR-070402
August 2007 [pdf]

Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor $p$ has the speed $S_p$. Tasks can be preempted but they cannot migrate between processors. On each processor, tasks are scheduled according to rate-monotonic. We propose an algorithm that can schedule all task sets that any other possible algorithm can schedule assuming that our algorithm is given processors that are $3.41$ times faster. No such guarantees are previously known for partitioned static-priority scheduling on uniform multiprocessors.

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.