Login

The Carousel-EDF Scheduling Algorithm for Multiprocessor Systems
Ref: CISTER-TR-130401       Publication Date: 19 to 21, Aug, 2013

The Carousel-EDF Scheduling Algorithm for Multiprocessor Systems

Ref: CISTER-TR-130401       Publication Date: 19 to 21, Aug, 2013

Abstract:
We present Carousel-EDF, a new hierarchical scheduling algorithm for a system of identical processors, and its overhead-aware schedulability analysis based on demand bound functions. Carousel-EDF is an offshoot of NPS-F and preserves its utilization bounds, which are the highest among algorithms not based on a single dispatching queue and that have few preemptions. Furthermore, with respect to NPS-F, Carousel-EDF reduces by up to 50% the number of context switches and of preemptions caused by the high-level scheduler itself. The schedulability analysis we present in this paper is grounded on a prototype implementation of Carousel-EDF that uses a new implementation technique for the release of periodic tasks. This technique reduces the pessimism of the schedulability analysis presented and can be applied, with similar benefits, to other scheduling algorithms such as NPS-F.

Authors:
Paulo Baltarejo Sousa
,
Pedro Souto
,
Eduardo Tovar
,
Konstantinos Bletsas


19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2013), IEEE, pp 12-21.
Taipei, Taiwan.

DOI:10.1109/RTCSA.2013.6732199.



Record Date: 4, Apr, 2013