The Case for Non-Preemptive Scheduling in Distributed Real-Time Systems

Contrary to traditional belief, we show in this paper, that for distributed systems non-preemptive scheduling can per-form better than preemptive scheduling in the worst case in terms of task schedulability, under certain circumstances. We derive a worst-case delay bound for tasks scheduled us-ing non-preemptive scheduling in a distributed system, where the task ow paths form a directed acyclic graph. The delay bound leads to a reduction of the distributed system to an equivalent hypothetical uniprocessor system scheduled us-ing preemptive scheduling. This transformation enables the wealth of uniprocessor schedulability theory to be applied to analyze schedulability under non-preemptive scheduling in distributed directed acyclic systems. Our simulation stud-ies show that non-preemptive scheduling can perform bet-ter than preemptive scheduling for distributed systems. We also characterize through simulations the scenarios under which non-preemptive is better than preemptive scheduling, and scenarios where the opposite is true. We hope this paper will serve as a rst step towards more extensive study and use of non-preemptive scheduling in distributed systems. 1