Kritischer Abschnitt

In der Informatik dient ein kritischer Abschnitt (engl. ‚critical section’) zur Kennzeichnung einer Ansammlung von Programmanweisungen zum Zwecke der Ablaufsteuerung. In ihm darf sich zu einer Zeit nur ein einziger Prozess/Thread aufhalten, ähnlich einem Bahnübergang, der nur vom Schienenfahrzeug oder nur von Straßenfahrzeugen befahren werden darf, aber nicht von beiden Fahrzeugarten gleichzeitig.

Kritische Abschnitte bestehen aus mehreren Einzelanweisungen, deren Zwischenergebnisse inkonsistente Zustände darstellen, auf die die anderen Threads keinen Zugriff erhalten dürfen. Das Ergebnis eines kritischen Abschnitts darf nur als eine unteilbare Einheit nach außen sichtbar werden.

Dieses Konzept wird zur Sicherstellung der Konsistenz der Zustände von Betriebsmitteln, bspw. Datenstrukturen, Verbindungen, Geräte usw., aber auch Datenbankinhalten, benötigt. Im letzteren Fall gehen die Konzepte auf in der Transaktionsverarbeitung.

Beispiele

Je zwei Threads sollen die gemeinsame Variable s inkrementieren:
Links wird ein kritischer Abschnitt (orange umrandet) unterbrochen, und das Ergebnis ist nicht korrekt.
Rechts ist das Ergebnis korrekt, da sich zu einer Zeit maximal ein Thread im kritischen Abschnitt befindet.

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:

		Thread X	Thread Y
1:		zaehler lesen
2:			zaehler lesen
3:		um 1 erhöhen
4:			um 1 erhöhen
5:		zaehler schreiben
6:			zaehler schreiben

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.

Notation

In Programmier- und Modellierungssprachen finden sich gelegentlich die Direktiven:

• Begin_CriticalSection
• End_CriticalSection

oder auch

• EnterCriticalSection()
• LeaveCriticalSection()

Merkmal und Behandlung kritischer Abschnitte

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:

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

Siehe auch

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

Literatur

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