George Lima

New paradigms in the design of optimal multiprocessor real-time scheduling
Federal University of Bahia, Brasil
12, Mar, 2013 11:00-12:00 (1 hour)
CISTER, Porto, Portugal

Multiprocessor and multicore architectures have become a standard for personal computers or other devices. Desktops, laptops, and even mobile phones equipped with multiple processing units can be found in the market. This trend seems to drive both technology and research in computer science area for now and future. Indeed, dealing with massive parallel architectures brings about new challenges in areas such as application design, programming languages and operating systems. In the end, the user application must be able to get the computer power out of the available processing parallelism if applications are suitably scheduled on the several processing units. In the real-time systems area, scheduling is not only a matter of system performance but also of system correctness. Application tasks must be scheduled on the available processing units to get their jobs done by predefined deadlines. Although well established solutions to the real-time scheduling problem do exist for uniprocessor systems, they are not straightforwardly applicable to multiprocessors. A usual consequence when trying to do so is to impose restrictions on system utilization. For example, when the optimal uniprocessor EDF scheduler is brought to the multiprocessor arena, the maximum guaranteed system utilization cannot exceed 50%. On the other hand, when 100% of processing resources is to be ensured, run-time overhead due to excessive context-switch usually becomes too high for making the approach practical. In this talk, we discuss why optimal uniprocessor scheduling algorithms fail to deliver optimality in multiprocessors. Then, we identify key properties that must be observed, pointing out the need for new paradigms for addressing the problem. One of such paradigms, called RUN, shows a way of applying a set of uniprocessor EDF schedulers to optimality deal with multiprocessor with low run-time overhead. Interestingly, RUN reduces the multiprocessor scheduling problem into a collection of uniprocessor scheduling problems, showing that scheduling real-time tasks on multiprocessors is actually as hard as on uniprocessors. We will end this talk by indicating some open issues to be addressed in the future.

George Lima received his B.Sc. (2003) from Federal University of Bahia, Brazil, his M.Sc. degree (2006) from the State University of Campinas, Brazil, and the Ph.D. degree (2003) from the University of York, all degrees in Computer Science. Since 2004, he has taken a permanent position at Federal University of Bahia as Professor, where he was the Head of Department from 2006 to 2008 and got involved in several relevant administrative activities since then. His main research interests are in the area of real-time systems, covering topics such as scheduling, fault tolerance, operating systems, communication networks and, distributed systems.

Auditorium, CISTER, ISEP
Rua Alfredo Allen, 535
4200-135 Porto, Portugal

07 Auditorium/Seminar Room
Level 0