Lock

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Lock (Begriffsklärung) aufgeführt.

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[Bearbeiten]

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[Bearbeiten]

Besitzt eine Ressource einen Read-Lock (oder auch „Shared 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, dürfen diese aber nicht verändern.

Write-Lock[Bearbeiten]

Eine Ressource mit Write-Lock (oder auch „Exclusive 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. 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 existiert.

Lock-Freigabe[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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 (bis in alle Ewigkeit).

Hierarchisches Locking[Bearbeiten]

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.

Multi-Locking[Bearbeiten]

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

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[Bearbeiten]

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
   }

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[Bearbeiten]

Ohne Locking (sog. Race Condition)
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 implementierter 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[Bearbeiten]

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]