Lock
Unter einem Lock oder Locking (englisch für Sperre oder Sperren) versteht man in der Informatik das Sperren des Zugriffs auf ein Betriebsmittel. 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 ganz zu sperren, gibt es zwei grundlegende Arten von Sperren:
Read-Lock
Besitzt eine Ressource einen Read-Lock („Lesesperre“, oder auch Shared Lock, „geteilte Sperre“), 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, dürfen diese aber nicht verändern.
Write-Lock
Eine Ressource mit Write-Lock („Schreibsperre“, oder auch Exclusive Lock, „exklusive Sperre“) 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. Das Verfahren wird auch als pessimistisches Locking bezeichnet, da es von der Annahme ausgeht, dass in der Regel eine Aktualisierung der Daten erfolgen wird. Beim optimistischen Locking wird davon ausgegangen, dass in der Regel keine Aktualisierung erfolgt oder eine gleichzeitige Aktualisierung durch zwei Nutzer nicht wahrscheinlich ist. Es wird erst beim Aktualisieren geprüft, ob der Status quo noch gilt.
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 gibt 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“ (englisch starve) somit.
Deadlock
Das Setzen einer Sperre kann Deadlocks verursachen, nämlich dann, wenn zwei Prozesse gegenseitig auf die Freigabe der vom jeweils anderen gesperrten Ressource warten.
Beispiel: Es gebe (als Ressourcen) ein Fahrrad und einen Stadtplan. Zwei Fahrradkuriere sollen jeweils ein Paket ausliefern und benötigen dazu (jeweils) Fahrrad und Stadtplan. Der Kurier A kann das Fahrrad reservieren, der Kurier B den Stadtplan. Sie befinden sich nun im Deadlock, da beide auf die Ressource des jeweils anderen warten (endlos).
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 Leistungsgewinn, da so nicht alle Elemente der Einheit separat gesperrt und überwacht zu werden brauchen. 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 jeweils beste Verfahren ist abhängig von der Art der Datenbank, der Häufigkeit von Änderungen und der Anzahl der gleichzeitigen Nutzer.
Multi-Locking
Multi-Locking gehört zum pessimistischen Locking und ermöglicht ein Deadlock-freies Programmieren. Beim MultiLock werden die Locks gleich am Anfang des Synchronisierungsblocks reserviert und bilden einen MultiLock. Bei MultiLocks können keine Deadlocks entstehen, weil ein MultiLock nur dann gestartet wird, wenn alle benötigten Locks verfügbar sind. Während der Ausführung von MultiLock können keine neuen Locks verwendet werden. Die einzelnen zum MultiLock gehörenden Locks können jedoch freigegeben und in anderen MultiLocks verwendet werden.
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 meist 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) undnotify(beendet wait auf die Bedingungsvariable) umgesetzt wird – die Bedingung wird dann in einem kritischen Abschnitt des Monitors geprüft. Die Umsetzung vonwarte_biswä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
notifyaufgerufen 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 ungünstig, 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 vonwarte_biswä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
}
Locking ist einfach zu implementieren, wenn zum Ablauf „Setze die Blockierung, wenn sie im Moment frei ist“ eine atomare Anweisung existiert. Wenn hingegen zwischen der Prüfung, ob der Lock gerade frei ist, und dessen Belegung ein zweiter Prozess ebenfalls prüfen kann, so beschließen beide, dass der Lock zu setzen ist und jetzt „ihnen gehört“. Das Gleiche gilt insbesondere auch für mehrere Threads eines Prozesses.
Beispiel
| 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.
| Prozess 1 | Prozess 2 |
|---|---|
| Ressource wird reserviert; liest von Ressource |
|
| versucht von Ressource zu lesen; muss warten („Lock greift“) | |
| verändert Daten; schreibt auf Ressource; Ressource wird freigegeben |
|
| Ressource wird reserviert; 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 implementierter Bankautomat sein:
| 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!
| Person 1 | Person 2 |
|---|---|
| Zugriff auf Bankkonto wird reserviert; 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 reserviert; liest Kontostand (150 €); hebt 100 € ab; schreibt neuen Kontostand (150 €-100 € = 50 €); Zugriff auf Bankkonto wird freigegeben |
Neuer Stand: 50 € richtig!
Siehe auch
Literatur
- James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986. In: Distrib. Comput. Band 16, Nr. 2–3. Springer-Verlag, September 2003, ISSN 0178-2770, S. 75–110, doi:10.1007/s00446-003-0088-6.
- M. Raynal, D. Beeson: Algorithms for mutual exclusion. MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3.