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 Scheduling
Ref: HURRAY-TR-100911 Publication Date: 30, Nov to 3, Dec, 2010Abstract:
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.
Paulo Baltarejo Sousa
Björn Andersson
Eduardo TovarDocument:
View
Download31st IEEE Real-Time Systems Symposium (RTSS 2010), Work-In-Progress Session.
San Diego, U.S.A..
Record Date: 30, Sep, 2010