SPRINT: Extending RUN to schedule sporadic tasks

Andrea Baldovin, Geoffrey Nelissen, Tullio Vardanega, Eduardo Tovar

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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 [1]. Interestingly, experimental results show that the favourable property of causing a small number of preemptions and migrations achieved by RUN is preserved with SPRINT.

Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
PublisherAssociation for Computing Machinery, Inc
Pages321-330
Number of pages10
ISBN (Electronic)9781450327275
DOIs
Publication statusPublished - 8 Oct 2014
Externally publishedYes
Event22nd International Conference on Real-Time Networks and Systems, RTNS 2014 - Versailles, France
Duration: 8 Oct 201410 Oct 2014

Publication series

NameACM International Conference Proceeding Series
Volume08-10-October-2014

Conference

Conference22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Country/TerritoryFrance
CityVersailles
Period8/10/1410/10/14

Fingerprint

Dive into the research topics of 'SPRINT: Extending RUN to schedule sporadic tasks'. Together they form a unique fingerprint.

Cite this