Read-Write-Lock

Unter Locking (engl. für Sperren) versteht man in der Informatik das Sperren des Zugriffs auf eine Ressource. Eine solche Sperre ermöglicht den exklusiven Zugriff eines Prozesses auf eine Ressource d.h. mit der Garantie dass kein anderer Prozess diese Ressource liest oder verändert solange die Sperre besteht.

Locking wird häufig bei Prozesssynchronisation sowie in Datei- und Datenbanksystemen verwendet um atomare und konsistente Lese- und Schreibanforderungen zu gewährleisten.

Locking-Arten

Möchte ein Prozess exklusiven Zugriff auf eine Ressource, muss er eine Sperre bei einem Verwaltungsprozess (z.B. einem Locking-Manager) anfordern. Um die angeforderte Ressource nicht komplett zu sperren gibt es zwei grundlegende Arten von Sperren:

• Read-Lock: Besitzt eine Ressource einen Read-Lock so möchte der Prozess, der diese Sperre gesetzt hat, von der Ressource nur lesen. Somit können auch andere Prozesse auf diese Ressource lesend zugreifen, diese aber nicht verändern.
• Write-Lock: Eine Ressource mit Write-Lock verhindert, dass die Ressource von anderen Prozessen gelesen oder geschrieben wird, da der Prozess, der den Lock gesetzt hat, die Ressource verändern möchte.

Lock-Freigabe

Ist der Prozess, der eine Sperre angefordert hat, fertig, muss er die Sperre wieder aufheben. Prozesse, die aufgrund einer Sperre auf eine Ressource nicht zugreifen konnten, müssen warten und reihen sich in eine Warteschlange ein. Es existieren mehrere Möglichkeiten wie diese Warteschlange ausgelegt ist, z.B. prioritätsgesteuert, FIFO-gesteuert, usw.

Verhungern/Starving

Hebt ein Prozess eine Sperre nicht wieder auf, so warten ggf. andere Prozesse unendlich lange auf diese Freigabe. Diese Prozesse „verhungern“ (engl. starve) somit.

Deadlock

Das Setzen einer Sperre kann Deadlocks verursachen, nämlich dann, wenn zwei Prozesse gegenseitig auf die Freigabe der von ihnen gesperrten Ressourcen warten.

Hierarchisches Locking

Beim hierarchischen Locking werden Ressourcen zu größeren logischen Einheiten zusammengefasst. Es ist nun möglich die gesamte logische Einheit zu sperren. Dies bringt einen Performancegewinn, da so nicht alle Elemente der Einheit separat gesperrt und überwacht werden müssen. Die richtige Wahl der Granularität der logischen Einheiten ist dabei von großer Bedeutung.

Hierarchisches Locking findet vor allem in Datenbanksystemen Anwendung. Es kann z.B. ein Datenfeld, ein Datensatz, eine Datei, oder die ganze Datenbank gesperrt werden. Das 'optimale' Verfahren ergibt sich, abhängig von der Art der Datenbank, der Häufigkeit von Änderungen und der Anzahl der gleichzeitigen Nutzer.

Implementierung

Der zentrale Aspekt von Locks ist die Fähigkeit, einen Prozess, der gerade nicht "bedient" werden kann, so lange warten zu lassen, bis das Lock frei ist – das entspricht der Funktion warte_bis, die im Pseudocode weiter unten zur Anwendung kommen wird. Das Warten auf eine Bedingung ist grundsätzlich auf zwei Arten möglich:

• Die erste Möglichkeit ist die Umsetzung mit Hilfe des Prozess-Schedulers (also des Betriebssystems bzw. der Laufzeitumgebung, siehe Time Sharing): Der Scheduler kennt das Lock und weist dem Prozess solange keine Rechenzeit zu, bis das Lock frei ist. Das ist im Allgemeinen nur dann möglich, wenn der Lock-Mechanismus vom Betriebssystem (bzw. der Laufzeitumgebung) bereitgestellt wird, denn nur dann kann der Scheduler das Lock und seinen aktuellen Zustand kennen. Alternativ kann die Laufzeitumgebung auch ein Monitor-Konzept unterstützen, in dem dies durch die Funktionen wait (auf eine Bedingungsvariable) und notify (beendet wait auf die Bedingungsvariable) umgesetzt wird – die Bedingung wird dann in einem kritischen Abschnitt des Monitors geprüft. Die Umsetzung von warte_bis wäre dann folgendermaßen möglich:

   Funktion warte_bis( Parameter bedingung ) {
       solange ( nicht bedingung ) wait(); // bei jedem notify wird die Bedingung erneut geprüft
   }

Das setzt voraus, dass beim Ändern der Variablen, auf die sich die Bedingung bezieht, stets notify aufgerufen wird, so dass die Bedingung erneut geprüft wird.

• Die zweite Möglichkeit ist die Umsetzung als Spinlock: der Prozess prüft in einer Schleife ständig, ob das Lock frei ist, und fährt erst dann fort. Dies ist auch ohne Unterstützung des Schedulers möglich, hat aber den Nachteil, dass der Prozess Rechenzeit verbraucht, während er wartet („aktives Warten“ bzw. „Busy Waiting“). Wenn das Betriebssystem (bzw. die Laufzeitumgebung) eine Möglichkeit bietet, einen Prozess für eine vorgegebene Zeit „schlafen“ zu lassen (sleep), so ist das nicht ganz so schlimm, da nur in regelmäßigen Abständen etwas Rechenzeit gebraucht wird, um das Lock zu prüfen (man spricht auch von slow busy waiting oder lazy polling). Bietet das Betriebssystem diese Möglichkeit aber nicht, so beansprucht der Prozess während des Wartens die volle Rechenleistung des Systems und bremst dadurch andere laufende Prozesse aus. Die Umsetzung von warte_bis wäre mit der Möglichkeit zu schlafen ähnlich wie oben, nur mit dem Unterschied, dass die Bedingung in regelmäßigen Abständen geprüft wird, und nicht (nur) wenn sich die betreffenden Variablen ändern:

   Funktion warte_bis( Parameter bedingung ) {
       solange ( nicht bedingung ) sleep( 1 Sekunde ); // die Bedingung wird einmal pro Sekunde geprüft
   }

Beispiel

Ohne Locking

Prozess 1	Prozess 2
liest von Ressource
	liest von Ressource verändert Daten schreibt auf Ressource
verändert Daten schreibt auf Ressource

Die Veränderungen von Prozess 2 werden somit von Prozess 1 überschrieben und sind verloren. Solche Fehler sind manchmal schwer zu reproduzieren, da sie zufällig auftreten.

Mit Locking

Prozess 1	Prozess 2
Ressource wird gesperrt liest von Ressource
	versucht von Ressource zu lesen Lock greift
verändert Daten schreibt auf Ressource Ressource wird freigegeben
	Ressource wird gesperrt liest von Ressource verändert Daten schreibt auf Ressource Ressource wird freigegeben

Beide Änderungen sind in der Ressource enthalten.

Ein anschaulicheres Beispiel könnte ein falsch implentierter Bankautomat sein:

Ohne Locking
(Guthaben Konto: 100€)

Person 1	Person 2
liest Kontostand (100€)
	liest Kontostand (100€) Hebt 100€ ab schreibt neuen Kontostand (100€-100€ = 0€)
zahlt 50€ ein schreibt neuen Kontostand (100€+50€ = 150€)

Neuer Stand: 150€ falsch!

Mit Locking
(Guthaben Konto: 100€)

Person 1	Person 2
Zugriff auf Bankkonto wird gesperrt liest Kontostand (100€)
	versucht Kontostand zu lesen Lock greift, Person 2 muss warten.
zahlt 50€ ein schreibt neuen Kontostand (100€+50€ = 150€) Zugriff auf Bankkonto wird freigegeben
	Lock frei Zugriff auf Bankkonto wird gesperrt liest Kontostand (150€) hebt 100€ ab schreibt neuen Kontostand (150€-100€ = 50€) Zugriff auf Bankkonto wird freigegeben

Neuer Stand: 50€ richtig!

Siehe auch

• Sperrverfahren
• Sperreskalation
• Deadlock