Implementing slot-based task-splitting multiprocessor scheduling

• Author(s): Sousa, Paulo Baltarejo ; Andersson, Björn ; Tovar, Eduardo
• Date: 2011
• Persistent ID: http://hdl.handle.net/10400.22/3810
• Origin: Repositório Científico do Instituto Politécnico do Porto
• Subject(s): Multiprocessor scheduling; Task-splitting; Semi-partitioned scheduling; Linux kernel
• Document Type: Article
• Language: English

Description

Consider the problem of scheduling a set of sporadic tasks on a multiprocessor system to meet deadlines using a task-splitting scheduling algorithm. Task-splitting (also called semi-partitioning) scheduling algorithms assign 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 particular type of task-splitting algorithms, called slot-based task-splitting dispatching, is of particular interest because of its ability to schedule tasks with high processor utilizations. Unfortunately, no slot-based task-splitting algorithm has been implemented in a real operating system so far. In this paper we discuss and propose some modifications to the slot-based task-splitting algorithm driven by implementation concerns, and we report the first implementation of this family of algorithms in a real operating system running Linux kernel version 2.6.34. We have also conducted an extensive range of experiments on a 4-core multicore desktop PC running task-sets with utilizations of up to 88%. The results show that the behavior of our implementation is in line with the theoretical framework behind it.