Neue Ansätze und Entwicklungen zur Steigerung der Preemptivität des Linux Kernels 2.6

Themenschwerpunkte & Stichpunkte: Linux Kernel 2.6, weiche Echtzeit, Unterbrechbarkeit, kritische Abschnitte, Preemptionsperre, Mutex, Prioritätsinversion, Prioritätsvererbung, Scheduler, Zeitauflösung

Linux 2.6 ist für Soft-Realtime Aufgaben geeigneter als frühere Kernel. In Linux 2.4 hängt die Scheduler-Laufzeit von der Anzahl rechenbereiter Prozesse ab, in 2.6 ist sie konstant wie unsere Messung belegt. Der Timerinterrupt kommt in 2.6 jede Millisekunde, dies führt - bei entsprechendem Overhead - zu einer 10 mal besseren Zeitauflösung als in Linux 2.4. Der in 2.6 integrierte einschaltbare Preemptible Kernel erlaubt es, Kernel-Systemdienste falls nötig zu unterbrechen, um einen hochprioren Prozess auszuführen. Aber auch der Linux 2.6 Preemptible Kernel enthält längere kritische Abschnitte mit Preemptionsperren, die immer noch zu Verzögerungen für zeitkritische Prozesse führen wie unsere Messungen zeigen. Die Häufigkeit solcher Latenzzeiten kann durch die Wandlung der Preemptionsperren in Mutexe reduziert werden wie es der Linux-GPL-Kernel der Firma Timesys es tut oder neuerdings das MontaVista Open Source Linux Realtime Project auch. In diesem Projekt ist meine Arbeitsgruppe an der UniBwM "Early Contributor"

Greifen 2 Prozesse auf denselben Mutex zu, treten dennoch wieder Latenzen auf, so daß dieser Ansatz zwar den Kernel für Soft-Realtime Aufgaben wesentlich preemptiver macht, allerdings die Worst Case Latenz nicht senkt, d.h. der Linux Kernel wird durch diesen Ansatz nicht hard-realtime fähig.

Ein belegter Mutex legt den Aufrufer schlafen, Interrupt Handler dürfen dies jedoch nicht. Um auch Preemptionsperren in Interrupt Handlern in Mutexe wandeln zu können, müssen die Interrupt Handler durch hochpriore Kernel-Threads ausgeführt werden, dies erledigen die sog. IRQ-Thread Patches.

Mutexe können Prioritätsinversion verursachen. Der kommerzielle Timesys-Kernel begegnet dem durch ein nicht offengelegtes Prioritätsvererbungsprotokoll. Unser GPL Kernel Patch implementiert Mutexe mit Prioritätsvererbung nach einem Vorschlag von Victor Yodaiken (2001). MontaVista hat sich für einen unserer einfacheren Protokollimplementationen entschieden, das EVP2 (Einfaches PrioritätsVererbungs-Protokoll2), mit dem die Mutexe im MV Open Source RT Projekt ausgestattet sind. Dieses Protokoll ist dem ähnlich, das auch in VxWorks verwandt wird, es beruht auf einem recht bekannten Paper von Sha, Rjakumar and Sathaye und verhindert effizient Prioritätsiversion, wenn jeder Prozess nur ein Mutex hält.

Die Voluntary Preemption Patches, die als Nachfolger der Spinlock Breaking Patches Preemption Points in kritische Bereiche einführen, oder bedingte Schleifenabbrüche ermöglichen, können daher tatsächlich auch Worst Case Latenzzeiten senken, da sie lange kritische Bereiche in mehrere kleinere unterteilen.

Außerdem sollte natürlich auch ein High Timing Resolution Patch, also einer der Nachfolger des UTIME Patches, ins MontaVista Projekt Eingang finden.

In einer weiteren, eigenen Forschungsarbeit haben wir auch Mutexe entwickelt, die die Read-Write Locks des Standard LinuxKernels ersetzen im MontaVista Open Source RT Kernel, der ja z.B. auf den 2.6.7 mm-rc4 Kerneln von Andrew Morton basiert. Diese Implementation würden wir dann auf unserer Webseite unter GPL zum Download anbieten und im Paper auf die Webseite verweisen.

Noch einige Links: Am 12.10.2004 hat die Firma MontaVista ihr Open Source Linux Realtime Project gelaunched, http://source.mvista.com/linux_2_6_RT.html http://inf3-www.informatik.unibw-muenchen.de/research/linux/mutex/mutex.html

Referent:

Arnd Christian Heursch, Witold Jaworski and Helmut Rzehak
Universität der Bundeswehr München
Institut für informationstechnische Systeme
Fakultät Informatik
Werner-Heisenberg-Weg 39
85577 Neubiberg