FPDS in RTAI Linux
From Wikked
| This page describes Mark Bergsma's Master thesis project at the SAN group of the University of Technology, Eindhoven. |  |
Project description
The two in real systems most used mechanisms for fixed-priority scheduling are Fixed-Priority Preemptive Scheduling (FPPS) and Fixed-Priority Nonpreemptive Scheduling (FPNS). They exhibit rather different behaviour: where FPPS favours higher priority tasks by always immediately preempting lower priority tasks when higher priority tasks become available, FPNS favours lower priority tasks, as they will never be preempted and can run until completion regardless of any arrivals of higher priority tasks in the mean time. FPPS is optimal under the assumption that there is no overhead during context switches between tasks and therefore tasks can be preempted any number of times without incurring additional cost; however this assumption does not hold in practice. FPNS on the other hand does not incur any context switching overhead as a task will always run until completion, but this implies that higher priority tasks have to wait. FPPS and FPNS can thus be seen as two ends of a spectrum.
A compromise can be found in Fixed-Priority Scheduling with Deferred Preemption (FPDS), which is a generalisation of the two. FPDS splits up a task in arbitrarily many subjobs with preemption points between them, and thereby allows the granularity of the preemption to be selected by the programmer or compiler, finding a balance between the context switching overhead of FPPS and the coarse-grainedness of FPNS. Preemption points can be placed at positions which are deemed optimal, for efficiency reasons, and for access control of shared resources. The disadvantage of FPDS is, of course, an additional burden on the programmer or the compiler.
The goal of this Masters project is to extend the freely available RTAI real-time extension to Linux with support for FPDS scheduling, and reservations in the form of servers. RTAI is a free software community project that extends the Linux kernel with hard real-time functionality, and includes a basic FPPS scheduler for periodic and aperiodic tasks. By adding FPDS and servers with deferred preemption we hope to create an extendable, freely available implementation that can be used for future research of this topic.
Context: CANTATA
Timeline
- September - October 2008
- Studying literature, introductory chapter in thesis draft, first practical experiments with RTAI
- October 2008 - January 2009
- Research and design of FPDS implementation, research of current RTAI implementation, implementation of FPDS in RTAI Linux
- February 2009 - March 2009
- Research and design of deferrable servers, implementation in RTAI Linux
- April 2009 - June 2009
- Analysis of implementation, optimization. T.B.D.
- July 2009
- Finalization of thesis
Results
We implemented FPDS in RTAI/Linux; the patch to the source code of version 3.6-cv is available here. libfpds is a small library containing supportive routines for use by real-time programs.
A paper describing the process and our results has been accepted for the OSPERT workshop. It can be downloaded here, and the older version of our FPDS implementation, on which the paper is based, is here.
Abstract
- Fixed-Priority Scheduling with Deferred Preemption (FPDS) is a middle ground between Fixed-Priority Preemptive Scheduling and Fixed-Priority Non-preemptive Scheduling, and offers advantages with respect to context switch overhead and resource access control. In this paper we present our work on extending the real-time operating system RTAI/Linux with support for FPDS. We give an overview of possible alternatives, describe our design choices and implementation, and verify through a series of measurements that indicate that a FPDS implementation in a real-world RTOS is feasible with minimal overhead.
Contact
Any comments/questions/suggestions about this work are welcome; please direct them at mark at nedworks dot org.
