From nonpreemptive to preemptive scheduling
Mohammad Mahdi Jaghoori · 2011
The use of automata for specifying patterns of task generation has broaden the perspective of schedulability analysis; scheduling has moved from periodic or rate-monotonic to aperiodic and non-uniform tasks. The question of schedulability in this setting, however, is not always decidable; with a preemptive scheduler, it is shown to be decidable for very restricted task models, e.g., when a task is modeled merely as a fixed computation time. In this paper, we consider the possibility of specifying tasks using timed automata. We show that, in this more complex setting, decidability holds not only for non-preemptive schedulers but also for preemptive schedulers if a minimum delay is assumed between consecutive preemptions. In practice, this minimum can be a multiple of the CPU clock speed. We show further how to extend from a single processor to multi-processor models with shared and/or separate queues.