Kritischer Abschnitt

 

Im sehr einfachen Beispiel A soll in der gemeinsamen Variablen zaehler die Häufigkeit des Betretens des Programmabschnitts gezählt werden. Dabei sei angenommen, dass der Zugriff zu zaehler nur mittels einer Lese- oder einer Schreiboperation möglich ist, nicht jedoch durch eine von Haus aus unteilbare Inkrementieroperation (inkrementieren: um eins erhöhen).

Der Programmabschnitt lautet:

zaehler in lokale Variable lesen

lokale Variable um 1 erhöhen

lokale Variable in zaehler schreiben

Nun werde dieser Programmabschnitt von zwei Threads zeitlich verschränkt ausgeführt. Die zeitliche Verschränkung wird vom Betriebssystem vorgenommen. Die Threads haben standardmäßig darauf keinen Einfluss. Beide Threads greifen unabhängig voneinander auf die Variable zaehler zu, verarbeiten und verändern sie:

Vor dem Schritt 5 wird von beiden Threads der gleiche ursprüngliche Wert der Variablen zaehler gelesen. Die Threads haben diesen Wert als private Kopie. In den Schritten 3 und 4 addieren beide Threads jeweils 1 zu ihrer privaten Kopie. In den Schritten 5 und 6 speichern die Threads dann den neuen Wert aus ihren privaten Kopien zurück in die Variable zaehler. Im geschilderten Szenario ist es Thread Y, dessen Schreibaktion als letzte ausgeführt wird. Sie erzeugt das falsche Endergebnis 1, das nicht der Aufgabenstellung entspricht.

Beispiel B: Das Beispiel A sei erweitert um einen zweiten kritischen Abschnitt, der dieselbe Variable zaehler nun dekrementiert und damit in Relation zum ersten kritischen Abschnitt steht. Aus Konsistenzgründen darf sich dann zu einer Zeit maximal ein Thread in beiden kritischen Abschnitten aufhalten.

In Programmier- und Modellierungssprachen finden sich gelegentlich die Direktiven:

• Begin_CriticalSection
• End_CriticalSection

oder auch

• EnterCriticalSection()
• LeaveCriticalSection()

Werden Prozesse oder Threads parallel oder zeitlich verzahnt ausgeführt und benutzen sie Daten (Speicherbereiche) oder allgemein Betriebsmittel (z. B. Verbindungen, Geräte) gemeinsam, so gibt es Betriebsmittel, die ihrer Natur nach nur exklusiv benutzt werden dürfen: während der Ausführung eines Programmabschnitts von einem Thread, in dem das Betriebsmittel verändernd verwendet wird, darf das Betriebsmittel für andere Threads nicht zugreifbar sein. Ein Programmabschnitt im Programm eines Threads, in dem auf ein gemeinsam genutztes, aber exklusiv zu nutzendes Betriebsmittel zugegriffen wird, ist ein kritischer Abschnitt.

Es gilt, eine zeitlich verschränkte Ausführung kritischer Abschnitte paralleler Threads zu verhindern, da diese zu unvorhersagbaren Ergebnissen oder inkonsistenten Zuständen der Betriebsmittel führt. Es ist aber nicht erforderlich, eine strenge Reihenfolge der Nutzung des Betriebsmittels festzulegen. Es ist ausreichend, für einen wechselseitigen Ausschluss der Zugriffe zu sorgen. Wenn sich ein Thread in einem kritischen Abschnitt bezüglich eines Betriebsmittels befindet, darf kein anderer Thread in einen kritischen Abschnitt bezüglich des gleichen Betriebsmittels gelangen. Dies wird durch eine beliebige Sequentialisierung der Ausführung kritischer Abschnitte der zugreifenden Threads erreicht. Dies ist eine schwächere Anforderung als die Anforderung nach Ununterbrechbarkeit der Ausführung eines kritischen Abschnitts, die oftmals im Zusammenhang mit kritischen Abschnitten erwähnt wird. Wird ein kritischer Abschnitt bezüglich eines Betriebsmittels ausgeführt, so darf dieser nur nicht zugunsten der Ausführung eines kritischen Abschnitts (bezüglich des gleichen, gemeinsam genutzten Betriebsmittels) eines anderen Prozesses unterbrochen werden.

An eine Lösung für das Problem des Kritischen Abschnitts werden folgende Anforderungen gestellt:^[1]

• Wechselseitiger Ausschluss: Bezüglich eines Betriebsmittels darf sich zu jedem Zeitpunkt höchstens ein Thread in einem kritischen Abschnitt befinden.
• Fortschritt: Eine Beendigung oder ein Anhalten eines Prozesses außerhalb eines kritischen Abschnitts darf keinen Einfluss auf den Fortschritt der verbleibenden Prozesse haben.
• Begrenzte Wartezeit: Kein Thread darf beliebig lange vom Betreten eines kritischen Abschnitts ausgeschlossen werden.
• Die Lösung darf keine Annahme über die Ausführungsgeschwindigkeit der Threads machen.

Mit der Erfüllung dieser Anforderungen kann die Konsistenz der Betriebsmittel gewährleistet werden. Ferner kommt jeder Thread in endlicher Zeit in seinen kritischen Abschnitt und wird nicht grundsätzlich am Eintritt in seinen kritischen Abschnitt gehindert.

• Prozesssynchronisation
• Time-Of-Check-to-Time-Of-Use-Problem
• Race Condition
• Lösungskonzepte für das Problem des Kritischen Abschnitts:
  • Semaphor
  • Mutex
  • Lock
  • Monitor

• Anderson, James H. and Kim, Yong-Jik and Herman, Ted: 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. 
• Raynal, M. and Beeson, D.: Algorithms for mutual exclusion. MIT Press, Cambridge, MA, USA 1986, ISBN 0-262-18119-3. 

1. ↑ Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating system concepts. 7. Auflage. John Wiley & Sons, Hoboken (New Jersey) 2005, ISBN 0-471-69466-5, 6.2 The Critical-Section Problem, S. 194 (englisch).