Scheduling of Offset Free Systems |
| |
Authors: | Goossens Joël |
| |
Affiliation: | (1) Département d'Informatique, Université Libre de Bruxelles, CP 212, Boulevard du Triomphe, 1050 Brussels, Belgium |
| |
Abstract: | In this paper, we study the problem of scheduling hard real-time periodic tasks. We consider independent tasks which are characterized by a period, a hard deadline and a computation time, but where the offsets may be chosen by the scheduling algorithm. We first show that we can restrict the problem by considering non-equivalent offset assignments. More precisely, we show that there are finitely many non-equivalent offset assignments and we propose a method to reduce significantly this number and consider only the minimal number of non-equivalent offset assignments. We then propose an optimal offset assignment rule which considers only the non-equivalent offset assignments. However the number of combinations remains exponential; for this reason, we also propose a nearly optimal algorithm with a more reasonable time complexity. |
| |
Keywords: | hard real-time scheduling periodic task set synchronous systems asynchronous systems rate monotonic deadline monotonic deadline driven scheduler |
本文献已被 SpringerLink 等数据库收录! |
|