Beräkningskomplexitet inom schemaläggningsteori

Tidsperiod: 2019-01-01 till 2022-12-31

Projektledare: Pontus Ekberg

Finansiär: Vetenskapsrådet

Bidragstyp: Bidrag för anställning eller stipendier

Budget: 4 214 000 SEK

This project will study algorithmic questions in real-time scheduling theory, with a main focus on establishing the computational complexity of schedulability problems. A schedulability problem is to decide whether a given task set---a model of the system´s workload---is guaranteed to always meet all timing constraints when used with a particular combination of scheduling algorithm and computer platform.Such problems must routinely be solved when designing safety-critical real-time systems, often repeatedly during design-space exploration, and therefore efficient algorithms are needed for solving them. A wealth of research papers in the real-time systems community describe such algorithms, but many basic schedulability problems have resisted efficient solutions for decades. What the complexity of these are have been long-standing open questions in real-time scheduling theory. Recent work by the applicant have settled several of these questions for uniprocessors, and this project aims to further advance the state-of-the-art by studying these important problems in the multiprocessor setting.Multiprocessor real-time scheduling is a very active research area where many fundamental algorithmic questions are still unanswered. It is also an area where industry is struggling due to the move to multicore processors, so any progress will be important contributions to both theory and practice.