16, Mar, 2012 12:00-13:00 (1 hour)
CISTER, Porto, Portugal

ABSTRACT:
Dynamic parallel scheduling using work-stealing has gained popularity in academia and industry for its good performance, ease of implementation and theoretical bounds on space and time. Cores treat their own double-ended queues (deques) as a stack, pushing and popping threads from the bottom, but treat the deque of another randomly selected busy core as a queue, stealing threads only from the top, whenever they are idle. However, this standard approach cannot be directly applied to real-time systems, where the importance of parallelising tasks is increasing due to the limitations of multiprocessor scheduling theory regarding parallelism. Using one deque per core is obviously a source of priority inversion since high priority tasks may eventually be enqueued after lower priority tasks, possibly leading to deadline misses as in this case the lower priority tasks are the candidates when a stealing operation occurs. Our proposal is to replace the single non-priority deque of work-stealing with ordered per-processor priority deques of ready threads. The scheduling algorithm starts with a single deque per-core, but unlike traditional work-stealing, the total number of deques in the system may now exceed the number of processors. Instead of stealing randomly, cores steal from the highest priority deque.

SPEAKERS BIO:
Cláudio Maia, born in 1980, holds a degree (2007) in Computer Science Engineering at the Polytechnic Institute of Oporto. From 2006 to 2009, he was a researcher and software engineer at Critical Software S.A. During that time, his main areas of research were mobile and wireless communication systems and manufacturing systems. Since October 2009, he is a Researcher in the CISTER Research Unit, involved in the CooperatES project. His main research interests are in the fields of Dynamic Distributed Real-time Systems, Operating Systems and Mobile and Wireless Communication Systems.

CISTER's main roles: