SPRINT: Extending RUN to Schedule Sporadic Tasks
Ref: CISTER-TR-140905 Publication Date: 8 to 10, Oct, 2014
SPRINT: Extending RUN to Schedule Sporadic TasksRef: CISTER-TR-140905 Publication Date: 8 to 10, Oct, 2014
The RUN algorithm has proven to be a very effective technique for optimal multiprocessor scheduling, thanks to the limited number of preemptions and migrations incurred by the scheduled task set. This permits to achieve high system utilisation rates typical of global scheduling approaches without paying too much penalty due to excessive preemption 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 during our experiments. Yet, its behaviour is not defined for some specific task sets, which are however extremely rare . Interestingly, experimental results show that the favourable property of causing a small number of preemptions and migrations achieved by RUN is preserved with SPRINT.
22nd International Conference on Real-Time Networks and Systems (RTNS 2014).