Paulo Sousa, CISTER Research Unit ISEP/IPP
Bjorn  Anderson, CISTER Research Unit ISEP/IPP
Eduardo Tovar, CISTER Research Unit ISEP/IPP

Consider the problem of scheduling a task set 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 to ensure 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. This is the class that provides the highest utilization bound.

In addition, its run-time dispatching does not depend on any data structures that are shared among all processors and therefore it has the potential to scale to multicore processors with a very large number of processors.

For these reasons, we believe an implementation of a slot-based task-splitting algorithm would be valuable.

We discuss challenges and design principles of an implementation of a slot-based task-splitting algorithm into Linux 2.6.34 version and also we show that this kernel version is provided by the required “tools” for implementing such scheduling algorithm.

Finally, we show that the real behavior of the scheduling algorithm is very close of the theoretical using several experiments on a 4core and also on a 24-core machines.