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!.

Anwender von Echtzeit-Betriebssystemen sind in der Regel mit drei Semaphor-Typen vertraut: je nach RTOS Zähl-, binäre oder Mutex-Semaphore. In vielen multicorefähigen Betriebssystemen kommt ein weiterer hinzu — der Multiple-Readers-Writers-Lock. Dieser Artikel beschreibt, wie er funktioniert und welche Anwendungsprobleme sich damit adressieren lassen.

Entwickler von Software für Multicore-Prozessoranwendungen stoßen immer häufiger auf das so genannte „Multiple-Readers-Writers“-Problem. Es tritt auf, wenn mehrere Tasks einen großen Datenbereich gemeinsam nutzen sollen. Solange eine Task in den Datenbereich schreibt, darf keine andere Task zur selben Zeit darin schreiben bzw. lesen. Diese Regelung ließe sich auch mit einem herkömmlichen Semaphor einfach umsetzen.

Im „Multiple-Readers-Writers“-Fall jedoch soll es mehreren Tasks möglich sein, gleichzeitig Daten zu lesen – vorausgesetzt, es findet aktuell kein Schreibvorgang im Datenbereich statt. Herkömmliche Semaphore bieten diese Flexibilität nicht, denn sie gewähren immer nur einem Leseprozess (Reader) Zugriff zum Datenbereich, wenn gerade keine Task schreibt. Mit diesem Ansatz lässt sich also dem Problem der Multiple-Readers-Writers nicht effizient begegnen.

Ein einfaches Anwendungsbeispiel für Multiple-Readers-Writers-Lock

Das Problem lässt sich am Beispiel einer Datenbankverwaltung für die Sitzplatzreservierung verdeutlichen: Mehrere Kunden interessieren sich für einen bestimmten Sitzplatz auf einem bestimmten Flug und wollen zur selben Zeit den Plan für die angrenzenden Sitze ansehen. Es kann also vorkommen, dass sich beispielsweise Kunden in San Francisco, Berlin und Tel Aviv alle gleichzeitig nach Sitzplätzen in der Nähe von Sitz 18D erkundigen.

Bild 1: Illustration des Beispiels Buchungssystem für Fluggesellschaft. Ein klassisches Problem von „Multiple-Readers-Writers“
Bild 1: Illustration des Beispiels Buchungssystem für Fluggesellschaft. Ein klassisches Problem von „Multiple-Readers-Writers“

Alle Kunden, die den Sitzplan sehen möchten, sollen diese Information natürlich schnellstmöglich erhalten – und zwar gleichzeitig und nicht nacheinander. Reserviert jedoch einer dieser Kunden dann tatsächlich einen oder zwei Sitzplätze, dann soll es auch nur diesem Kunden möglich sein, diese Sitze auszuwählen. Es muss verhindert werden, dass verschiedene Kunden gleichzeitig den gleichen Platz bzw. die gleichen Plätze auswählen können.

Ebenso wenig darf es möglich sein, den Sitzplan zu lesen, während die Sitzplatzreservierung gerade aktualisiert wird. Dieser Ablauf lässt sich mit einem Multiple-Readers-Writers-Lock umsetzen: Ist kein Schreibvorgang aktiv, sind mehrere Lesevorgänge gleichzeitig möglich. Während eines Schreibvorgangs dagegen ist kein gleichzeitiger Zugriff gestattet.

Multiple-Readers-Writers-Lock in Echtzeitbetriebssystemen

Der Multiple-Readers-Writers-Lock steht in immer mehr embedded Multicore-Betriebssystemen zur Verfügung - besonders in symmetrischen Multiprozessor-Betriebssystemen (SMP), deren Ursprung entweder im Bereich der herkömmlichen Single-CPU-RTOS oder in der SMP-Linux-Welt liegt. Beim Einsatz dieser Betriebssysteme können Tasks (bzw. Threads oder Prozesse) dynamisch von Core zu Core wechseln.

In bestimmten Anwendungen müssen diese Tasks gleichzeitig in gemeinsam genutzten Datentabellen oder Datenbanken lesen. Oder mehrere Tasks haben eine Producer-Consumer-Beziehung für gemeinsam genutzte Daten, und es sollen gleichzeitig mehrere Consumer Informationen erhalten.

Auf einem Multicore-Chip können verschiedene Tasks auf verschiedenen Cores mit echtem Parallelismus ablaufen (anders als beim Pseudo-Parallelismus für das Multitasking mit Single-CPU). Erhalten die Tasks die erforderlichen Daten basierend auf echtem Parallelismus, verbessert dies die Performance gegenüber dem sequentialisierten Lesen über einen „herkömmlichen“ Semaphor.

Überblick herkömmlicher Semaphor-Varianten: Zählsemaphor

Echtzeit-Betriebssysteme für Single-CPU-Systeme unterstützen für gewöhnlich die folgenden drei Semaphor-Varianten: Zählsemaphore, binäre Semaphore und Mutex-Semaphore. In unserem Multitasking-Softwaredesign erfüllt jedes seinen eigenen Zweck.

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.

Der Grund dafür ist, dass alle Writer-Tasks nacheinander ausgeführt werden müssen - und das nur, solange keine Reader-Task aktiv ist. Hier können herkömmliche Semaphore durchaus zu einer Leistungssteigerung führen. In einer Single-CPU-Umgebung käme als Alternative ein Mutex infrage; in einer Multicore-Umgebung ein „Spinlock“.

Programmierschnittstelle für Multiple-Readers-Writers-Locks

Für Multiple-Readers-Writers-Locks gibt es keine Standard-Programmierschnittstelle (API) in den jeweiligen Betriebssystemen. Deshalb wird nachfolgend eine „universelle“ API gezeigt, die die typisch angebotenen Dienste darstellt, mit der API des eigentlichen Betriebssystems jedoch nicht identisch ist.

  • RWLockCreate() Neuen Multiple-Readers-Writers-Lock erzeugen
  • RWLockDelete() Bestehenden Multiple-Readers-Writers-Lock löschen
  • RWLockRead() Lock zum Lesen sperren (gemeinsam genutzt)
  • RWLockEndRead() Nach dem Lesen entsperren
  • RWLockWrite() Lock zum Schreiben sperren (nicht gemeinsam nutzbar)
  • RWLockEndWrite() Nach dem Schreiben entsperren

Wird ein solcher Lock zum Schutz einer gemeinsam genutzten Datenressource erzeugt, müssen Tasks vor dem Lesen erst RWLockCreate() aufrufen und nach dem Lesevorgang RWLockEndRead(). Mehrere Tasks dürfen gleichzeitig lesen. Vor dem Schreiben müssen Tasks RWLockWrite()und nach dem Lesevorgang RWLockEndWrite()aufrufen. Jeweils nur eine Task darf schreiben, vorausgesetzt, es darf gerade keine Task lesen.

Unterschiedliche Multiple-Readers-Writers-Locks: Lock mit Reader Praeferenz

Nicht alle Multiple-Readers-Writers-Locks weisen genau das gleiche Verhalten auf. Die Betriebssysteme, die diese Locks unterstützen, implementieren sie mit unterschiedlicher interner Logik zum Ausdruck der verschiedenen Applikationssoftware-Designpräferenzen. Betrachten wir drei mögliche Ansätze:

Bild 3: Multiple Reader–Writer-Lock mit Readers Preference
Bild 3: Multiple Reader–Writer-Lock mit Readers Preference

Der Lock mit Reader-Präferenz ist ein Multiple-Readers-Writers-Lock, der maximale potentielle Nebenläufigkeit schaffen soll, indem Reader-Tasks klar bevorzugt werden. Wenn Tasks bereits einen Lesevorgang ausführen, können jederzeit weitere Reader dazukommen. Eine neue Reader-Task wird nur dann zurückgehalten (in der Reader-Task-Queue links in Abb. 2 und 3), wenn die Writer-Task die Erlaubnis zum Schreiben bereits erhalten hat.

Writer-Tasks werden zurückgehalten (in der Writer-Task-Queue rechts in Abb. 2 und 3), solange die Reader-Task einen Lesevorgang ausführt. Unter Umständen werden Writer-Tasks also sehr lange verzögert, im schlimmsten Fall „verhungern“ sie in der Writer-Task-Queue.

Lock mit Writer-Präferenz

Bild 4: Multiple Reader Writer Lock mit Writers Preference
Bild 4: Multiple Reader Writer Lock mit Writers Preference

Dieser Multiple-Readers-Writers-Lock soll es Writer-Tasks erlauben, die geschützten Daten schnellstmöglich zu aktualisieren. Dabei sorgt er aber auch dafür, dass Reader-Tasks, einschließlich möglicher paralleler Reader, erst den bereits begonnenen Lesevorgang beenden, ehe eine Writer-Task auf die Daten zugreifen darf.

Neue Reader-Tasks werden zurückgehalten (in der Reader-Task-Queue links in Abb. 2 und 4), sobald eine Writer-Task um Schreiberlaubnis bittet. Neue Reader-Tasks werden unter Umständen also lange verzögert oder „verhungern“ schlimmstenfalls. Dazu kommt es ist jedoch nur sehr selten, wenn häufig gelesen und nur selten geschrieben wird, was bei Multiple-Readers-Writers-Lock normalerweise der Fall ist.

„Fairer“ Lock

Dieser Multiple-Readers-Writers-Lock sorgt dafür, dass weder eine Reader-Task noch eine Writer-Task verhungert. Er behandelt Reader und Writer gleich. Unter Umständen muss dabei jedoch eine Reader- oder Writer-Task gelegentlich länger als die minimal mögliche Wartezeit warten.

Um „Fairness“ zu schaffen, kann der Lock beispielsweise Tasks innerhalb der Einschränkungen des Multiple-Readers-Writers-Locks auf „first come, first serve“ Basis bedienen. Anders ausgedrückt: Neue Reader-Tasks werden zurückgehalten, solange eine Writer-Task wartet, und neue Writer-Tasks werden zurückgehalten, solange eine Reader-Task wartet.

Von diesen drei Varianten des Multiple-Readers-Writers-Locks kommt vermutlich der Lock mit Writer-Präferenz in Betriebssystemen am häufigsten zum Einsatz. Er leistet gute Dienste, wenn Writer-Tasks einen Lock selten und nur kurzzeitig sperren.

Quellen:

1. COUNTING SEMAPHORES:

“Mutexes and Semaphores Demystified”, Michael Barr

URL: http://www.embedded.com/design/210605040

2. UNBOUNDED PRIORITY INVERSIONS:

“Mutexes Battle Priority Inversions”, David Kalinsky.

URL: http://kalinskyassociates.com/Wpaper2.html

Kommentar zu diesem Artikel abgeben

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

Kommentar abschicken

 

Copyright © 2017 - Vogel Business Media