Challenges and Design Principles for Implementing Slot-Based Task-Splitting Multiprocessor Scheduling
Ref: HURRAY-TR-100911 Publication Date: 30, Nov to 3, Dec, 2010
Challenges and Design Principles for Implementing Slot-Based Task-Splitting Multiprocessor SchedulingRef: HURRAY-TR-100911 Publication Date: 30, Nov to 3, Dec, 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 offers these 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 discuss challenges and design principles for implementing slot-based task-splitting algorithms on multiprocessor systems running the Linux kernel.
31st IEEE Real-Time Systems Symposium (RTSS 2010), Work-In-Progress Session.
San Diego, U.S.A..