@inproceedings{f29c47a005d440afa5dc495fae3b17cb,
title = "Multi-processor schedulability analysis of preemptive real-time tasks with variable execution times",
abstract = "In this paper, we study schedulability analysis problems for multi-processor real-time systems. Assume a set of real-time tasks whose execution times and deadlines are known. We use timed automata to describe the non-deterministic arrival times of tasks. The schedulability problem is to check whether the released task instances can be executed within their given deadlines on a multi-processor platform where each processor has a task queue to buffer task instances scheduled to run on the processor. On the positive side, we show that the problem is decidable for systems with non-preemptive schedulers or tasks with fixed execution times. A surprising negative result is that for multi-processor systems with variable task execution times and a preemptive scheduler, the schedulability analysis problem is undecidable, which is still an open problem in the single-processor setting.",
author = "Pavel Krcal and Martin Stigge and Wang Yi",
year = "2007",
doi = "10.1007/978-3-540-75454-1\_20",
language = "英语",
isbn = "9783540754534",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "274--289",
booktitle = "Formal Modeling and Analysis of Timed Systems - 5th International Conference, FORMATS 2007, Proceedings",
address = "德国",
note = "5th International Conference on Formal Modelling and Analysis of Timed Systems, FORMATS 2007 ; Conference date: 03-10-2007 Through 05-10-2007",
}