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

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)