Echtzeit- und Multicore-Programmierung

Der vierte Semaphor: Multiple-Readers-Writers-Lock

08.06.2010 | Autor / Redakteur: David Kalinsky* / Martina Hafner

*David Kalinsky ist Leiter für Kundentraining bei D. Kalinsky Associates – Technical Training, einem Anbieter von Intensivseminaren für professionelle Embedded System- und Softwareentwickler. Als Dozent und Seminarleiter für Embedded-Softwarethemen hat er sich in Nordamerika, Europa und Israel einen Namen gemacht. In Deutschland ist er regelmäßiger Gastreferent beim Münchner Anbieter von technischen Trainings HILF!.
*David Kalinsky ist Leiter für Kundentraining bei D. Kalinsky Associates – Technical Training, einem Anbieter von Intensivseminaren für professionelle Embedded System- und Softwareentwickler. Als Dozent und Seminarleiter für Embedded-Softwarethemen hat er sich in Nordamerika, Europa und Israel einen Namen gemacht. In Deutschland ist er regelmäßiger Gastreferent beim Münchner Anbieter von technischen Trainings HILF!.

Der Zählsemaphor ist äußerst komplex. Er lässt sich mit einem Becher vergleichen, in dem sich identische „Token“ befinden. Tasks können dem Becher einzelne Token hinzufügen bzw. Token aus dem Becher entnehmen. Zählsemaphore werden häufig verwendet, um den Zugriff von Tasks auf mehrere äquivalente, gemeinsam nacheinander genutzte Ressourcen zu regulieren.

Beispiel: 17 Tasks teilen sich 4 identische Drucker. Hier lässt sich ein Zählsemaphor mit 4 Token erzeugen und initialisieren (siehe Abbildung). Die Tasks werden so programmiert, dass sie vor dem Drucken einen Token entnehmen und diesen nach dem Druckvorgang wieder in den Becher zurückgeben.

Doch dabei gibt es ein Problem: Wenn ein oder mehrere Token entnommen wurden, kann die Task nicht mehr erkennen, welcher Drucker noch verfügbar ist. Demnach bieten Zählsemaphore keine umfassende Lösung für die gemeinsame Nutzung mehrerer äquivalenter Ressourcen (siehe Quelle 1).

Zählsemaphore eignen sich eher für die Signalisierung zwischen einzelnen Tasks. Beispiel: 2 Tasks mit unterschiedlicher Priorität sind langfristig über die gleiche Gesamtzeit auszuführen. Ein Zählsemaphor mit Initialwert 0 wird erzeugt (d.h. keine Token enthalten). Wenn die höherpriore Task läuft, erzeugt sie ein Token, fügt dieses dem Semaphor hinzu und erhöht so den Semaphor-Zählwert. Die niederpriore Task wartet darauf, dass im Semaphore Token erscheinen und wird einmal je neuem Token ausgeführt. Damit braucht sie den Token auf und verringert den Semaphor-Zählwert.

Läuft die höherpriore Task mit einer mäßigen Wiederholrate, holt die niederpriore Task mit der Zeit auf und wird ebenso oft ausgeführt.

Der klassische binäre Semaphore

Klassische binäre Semaphore kann man sich als Zählsemaphore vorstellen, die auf den Maximalwert eins beschränkt sind (1 einziger Token). Auch sie eignen sich zum Signalisieren zwischen einzelnen Tasks, wenn Signale (Zählungen, Token) nicht akkumuliert werden oder nicht gezählt werden müssen.

Sie sollten z.B. nicht verwendet werden, um die gemeinsame Nutzung eines einzigen Druckers oder einer Datenstruktur durch mehrere Tasks zu regeln. Der Grund dafür ist ein berühmter (bzw. eher berüchtigter) Fehler – die so genannte unbegrenzte Prioritätsinversion, die typisch für klassische binäre Semaphore ist (siehe Quelle 2).

Der Mutex-Semaphore

Mutex-Semaphore kann man sich als binäre Semaphore vorstellen, bei denen der Fehler der „unbegrenzten Prioritätsinversion“ behoben wurde. Ein Mutex-Mechanismus dient also dem wechselseitigen Ausschluss (mutual exclusion). Er wird eingesetzt, um die gemeinsame Nutzung eines Druckers oder einer Datenstruktur durch mehrere Tasks zu regeln.

Die meisten Mutexe lösen den Fehler der „unbegrenzten Prioritätsinversion“, indem die Priorität einer Task manipuliert wird, die den Mutex hält. Dies erfolgt mit Methoden wie z.B. Prioritätsvererbungs-Protokoll oder Prioritäts-Obergrenzen-Protokoll.

Multiple-Readers-Writers-Lock unterscheidet Lese- und Schreibe-Task

Alle drei klassischen Semaphor-Varianten behandeln alle Arten von Tasks gleich, wenn sie den Zugriff auf eine einzelne, gemeinsam genutzte Ressource regeln. Sie unterscheiden nicht, ob Tasks in einer gemeinsam genutzten Ressource lesen oder schreiben sollen.

Bild 2: Multiple-Readers-Writers-Lock und zugehörige Task-Queues
Bild 2: Multiple-Readers-Writers-Lock und zugehörige Task-Queues

Nur die vierte Semaphor-Variante, der Multiple-Readers-Writers-Lock, unterscheidet zwischen Reader-Task und Writer-Task und stellt damit sicher, dass nur Reader-Tasks gleichzeitig auf die gemeinsam genutzte Ressource zugreifen können. Multiple-Readers-Writers-Locks sind meist hochkomplex. In Betriebssystemen, die diese Locks unterstützen, sind jedem Lock je eine Lese- und eine Schreib-Task-Waiting-Queue zugeordnet, wie in Abbildung 2 dargestellt.

Bei der Task-Queue rechts im Bild kann das Betriebssystem Writer-Tasks so lange halten, bis die Reader-Tasks den Lesevorgang beendet haben. In der zweiten Task-Queue links im Bild kann das Betriebssystem Reader-Tasks so lange halten, bis eine oder mehrere Writer-Tasks den Schreibvorgang beenden.

Das Verwalten und Regeln dieser Task-Queues ist komplex und beinhaltet in vielen Fällen weitere interne Semaphore in der eigentlichen Betriebssystemlogik. Oft beeinträchtigt diese Komplexität die Leistungsfähigkeit, deshalb sind diese Locks mit Sorgfalt zu verwenden.

Wann der vierte Semaphore etwas für die Performance bringt

Multiple-Readers-Writers-Locks bieten normalerweise eine höhere Performance als andere Semaphore oder Locks, besonders in Sequenzen mit vielen nebenläufigen Reader-Tasks und unregelmäßigen Schreibvorgängen - häufig anzutreffen in Multicore-Softwaredesigns. In der Regel führen Multiple-Readers-Writers-Locks jedoch zu keiner Performancesteigerung bei Anwendungen, in denen Writer-Tasks sehr viele Schreibvorgänge ausführen.

Inhalt des Artikels:

Kommentar zu diesem Artikel abgeben

Schreiben Sie uns hier Ihre Meinung ...
(nicht registrierter User)

Kommentar abschicken
copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 349652 / Software-Implementierung)