SPRINT: Extending RUN to Schedule Sporadic Tasks

The RUN algorithm has proven to be a very effective tech- nique for optimal multiprocessor scheduling, thanks to the limited number of preemptions and migrations incurred by the scheduled task set. This permits to achieve high sys- tem utilisation rates typical of global scheduling approaches without paying too much penalty due to excessive preemp- tion and migration overheads. Unfortunately, the adoption of RUN in real-world applications is limited by the missing support to sporadic task sets: we address this problem by proposing SPRINT (SPoradic Run for INdependent Tasks). SPRINT is proven correct for the vast majority of task sets and successfully scheduled all those randomly generated dur- ing our experiments. Yet, its behaviour is not dened for some specic task sets, which are however extremely rare [1]. Interestingly, experimental results show that the favourable property of causing a small number of preemptions and mi- grations achieved by RUN is preserved with SPRINT.