[ Institut fuer Informationstechnische Systeme ]

Mutex Patch for the 'Preemptible Linux Kernel'

The kernel patches presented hereafter can be downloaded (under the license GPL 2) and can be added to a Linux 2.4 Kernel, that has already been patched with the Preemptible Kernel Patch, in order to be able to serve time-critical processes with less latency and a higher predictability.

We developed this patch for Linux 2.4.18. The new kernel mutexes shall replace spinlocks in the Linux kernel, which don't lock interrupts at the same time. The mutexes offer a protocoll that avoids priority inversion.

We have presented the following papers with recent research results concerning this topic:

Arnd C. Heursch; Witold Jaworski; Romesch Duee und Helmut Rzehak:
Konzepte zur Steigerung der Preemptivitaet des Linux Kernels 2.6, hier Ersatz der Read Write Locks durch Mutexe;
paper for the Linux Automation Konferenz 2005, University of Hannover, Germany, March 31, 2005
Patch under GPL2 license for the MontaVista Open Source Realtime Linux Project Linux Kernel 2.6.9 to replace also Read Write Locks by Mutexes;
Arnd C. Heursch; Dirk Grambow; Dirk Roedel and Helmut Rzehak:
Time-critical tasks in Linux 2.6 - Concepts to increase the preemptability of the Linux kernel;
paper for the Linux Automation Konferenz 2004, University of Hannover, Germany, March 4-5, 2004
Arnd C. Heursch; Dirk Grambow; Alexander Horstkotte; Helmut Rzehak:
Steps towards a fully preemptable Linux kernel;
paper for 27th IFAC/IFIP/IEEE Workshop on Real-Time Programming, WRTP '03, Lagow, Poland, May 14-17, 2003,
proceedings, p.159-164, Editors: COLNARIC, ADAMSKI,& WEGRZYN, title: Real-Time Programming 2003,
publication date: mid November 2003 ?, ISBN: 008044203 X

In the following we present 2 different kernel patches for Linux 2.4.X already patched with the Preemptible Kernel Patch

1.) Mutex Kernel Patch for Linux 2.4.18 with the protocol EVP2
2.) Mutex Kernel Patch for Linux 2.4.18 implemented following the ideas in "The dangers of priority inheritance" by Victor Yodaiken (2001)
The same Mutex Kernel Patch like in 2.) for Linux 2.4.20

EVP2 is a mutex implementation with a priority inversion protocol which works fine, if every process holds not more than one mutex at the same time. Victor Yodaiken instead proposed a more general protocol that can also cope with priority inversion, if there are processes which hold several mutexes at the same time. Both mutex protocol implementations are described in detail in the following extract of Dirk Grambow's diploma thesis (ID 17/2002) (pdf), (zipped Postscript), 2002, in German. If you patched your kernel with one of the patches above, please load down the following file mutex_in_userspace.tgz and unpack it using tar xvzf mutex_in_userspace.tgz. This file contains the source code for a kernel module for Linux which you can compile with make and for a library, that you can build executing the makefile. The header 'pmutex.h' has to be copied into /usr/include/ on your computer, while the library has to be copied in /lib/.

When you write an application that includes

#include pmutex.h

you will be able to use the following 4 easy API functions in your programs:

int p_mutex_create();
int p_mutex_destroy(int m_id);
int p_mutex_down(int m_id);
int p_mutex_up(int m_id);

Please bind your application with the linker switch

-l libpmutex.so

When you run your application please make sure that your kernel has been patched with the Preemptible and the mutex patch, that you turned on Priority Inheritance before compiling the kernel on your computer, that the kernel module is loaded and that the device /dev/pmutex exists.

If all these conditions are fulfilled, your application should use mutexes with priority inheritance. You can test, whether the inheritance protocol works fine using our priority inversion test program for Linux 2.4 and Linux 2.6.

We ported the EVP2 patch to Linux 2.6.

In July 2004 we have joined our forces with a group of MontaVista Inc..

MontaVista (project leader: Sven Dietrich) initialized a new Open Source Real-Time Linux Project and released patches to form a "Linux 2.6 Real Time Kernel", for Linux-2.6.9-rc3, which incorporates the EVP2 patch for Linux 2.6. This kernel replaces a lot of spinlocks/preemption locks of the standard Linux 2.6 kernel with configured 'Preemptible kernel' by mutexes. As mutex implementation PMutexes of EVP2 (see above) can be used. Furthermore interrupts are executed by kernel threads in this Real Time Kernel, in order to be able to replace also spinlocks/preemption locks in interrupt handlers by mutexes.

For further details regarding the mutex implementation please refer to the diploma thesis, that can be downloaded above, and please also refer to MontaVista's WhitePaper .

We will continue our cooperation with MontaVista Inc. " on the course towards configurable responsiveness in the 2.6 Linux kernel."

This project is executed on the guidance of Prof.Dr. Helmut Rzehak and Prof.Dr.G.Teege, Institut fuer Informationstechnische Systeme, Fakultaet fuer Informatik, Universitaet der Bundeswehr Muenchen .

In case of any questions, please mailto: Arnd C. Heursch