You are here: Home / RTLWS 1999-2017 / RTLWS Submitted Papers / 
2024-12-11 - 06:54

Dates and Events:

OSADL Articles:

2024-10-02 12:00

Linux is now an RTOS!

PREEMPT_RT is mainline - What's next?


2023-11-12 12:00

Open Source License Obligations Checklists even better now

Import the checklists to other tools, create context diffs and merged lists


2023-03-01 12:00

Embedded Linux distributions

Results of the online "wish list"


2022-01-13 12:00

Phase #3 of OSADL project on OPC UA PubSub over TSN successfully completed

Another important milestone on the way to interoperable Open Source real-time Ethernet has been reached


2021-02-09 12:00

Open Source OPC UA PubSub over TSN project phase #3 launched

Letter of Intent with call for participation is now available



Real Time Linux Workshops

1999 - 2000 - 2001 - 2002 - 2003 - 2004 - 2005 - 2006 - 2007 - 2008 - 2009 - 2010 - 2011 - 2012 - 2013 - 2014 - 2015

13th Real-Time Linux Workshop from October 20 to 22 at the Faculty of Electrical Engineering, Czech Technical University in Prague

Announcement - Hotels - Directions - Agenda - Paper Abstracts - Presentations - Registration - Abstract Submission - Sponsoring - Gallery

On the implementation of real-time slot-based task-splitting scheduling algorithms for multiprocessor systems

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.