HomePublicationsTechnical Report

Implementing Slot-Based Task-Splitting Multiprocessor Scheduling
Ref: HURRAY-TR-100504       Publication Date: 16, May, 2010

Abstract:
Consider the problem of scheduling a set of sporadic tasks on a multiprocessor to meet deadlines even at high processor utilizations. We assume that task preemption and migration is allowed but because of their associated overhead,their frequency of use should be kept small. Task-splitting (also called semi-partitioning) is a family of algorithms that offer sthese properties. An algorithm in this class assigns most tasks to just one processor but a few tasks are assigned to two or more processors, and they are dispatched in a way that ensures that a task never executes on two or more processors simultaneously.A certain type of task-splitting algorithms, called slot-based split-task dispatching, is of particular interest because of its ability to schedule tasks at high processor utilizations.Unfortunately, no slot-based task-splitting algorithm has been implemented in a real operating system so far.Therefore, in this paper, we show that slot-based task splitting algorithms can be implemented in a real operating system. We discuss the challenges and the design principles for slot-based task-splitting algorithms on multiprocessor systems.We also present an implementation of a multiprocessor scheduling algorithm based on slot-based split task dispatching;it is based on the Linux kernel 2.6.28. We have conducted a range of experiments with a 4-core multicore desktop PC utilized to 88% with synthetic benchmark programs executing spin-loops with the operating system being set to run level 1(that is no windowing system) and the desktop PC being disconnected from the network. These experiments show good correspondence between theory and practice. Specifically, we observe that (i) no deadline misses occurred, (ii) the release jitter was at most 33 microseconds and (iii) the time when so-called reserves began deviates with at most 27microseconds from when they should occur.

Paulo Baltarejo Sousa

,

Björn Andersson

,

Eduardo Tovar

Document:

View
PDF Download
PDF