Kritische Regionen

Zunächst führt man in einer höheren Programmiersprache^5.3 ein zusätzliches Schlüsselwort shared ein, mit dessen Hilfe man Variablen deklariert, auf die verschiedene Prozesse zugreifen dürfen:

Hier wird eine Variable v von Typ T deklariert, auf die mehrere Prozesse zugreifen können.

Auf Variablen, die als shared deklariert sind, darf man nur innerhalb von Region-Umgebungen zugreifen:

Die Semantik der Region-Umgebungen ist so festgelegt, dass solange das Programmstück S ausgeführt wird, kein anderer Prozess auf die Variable v zugreifen darf. B ist ein boole'scher Ausdruck, der erfüllt sein muss, damit der Prozess mit S beginnt.

Als ein Beispiel für die Region-Umgebungen wollen wir nun das Erzeuger-Verbraucher-Problem implementieren (Abbildung ).

Figure: Erzeuger-Verbraucher-Problem in der Region-Umgebung

Betrachten wir nun eine mögliche Übersetzung der Region-Umgebungen:

In Abbildung ist in C mit Semaphoren eine Übersetzung angegeben.

Figure: Implementierung der Region-Umgebung

Die Übersetzung implementiert eine Warteschleife die jeweils alle Prozesse die zum Start der Region-Umgebungen kommen zunächst durch eine zweistufige Warteschleife schickt, wenn die Bedingung B (noch) nicht erfüllt ist. Schritt für Schritt wird für die wartenden Prozesse die Bedingung wieder geprüft. Drei binäre Semaphoren sind wie folgt vorinitialisiert: mutex = 1, first = 0, second = 0. Zunächst wird der Prozess bezüglich first schlafen gelegt. Wenn nun ein anderer Prozess S verlässt, wird dieser Prozess durch up aufgeweckt. Der so aufgeweckte Prozess weckt dann in der zweiten Stufen alle Prozesse auf, die sich bezüglich first schlafen gelegt haben. Diese so aufgeweckten Prozesse legen sich nun bezüglich second schlafen. Der letzte Prozess der bezüglich first aufgeweckt wurde, weckt seinerseits einen Prozess auf, der sich bezüglich second schlafen gelegt hat. Für diesen aufgeweckten Prozess wird die Bedingung B erneut überprüft. Wenn B erfüllt ist, durchläuft der betrachtete Prozess das Programmstück S. Die Variablen first-count und second-count beinhalten die Anzahl der im Moment bezüglich des jeweiligen Semaphors schlafen gelegten Prozesse.

Man muss die Warteschleife zweistufig programmieren, weil sich sonst mehrere wartende Prozesse ständig gegenseitig aufwecken würden, ohne dass ein anderer Prozess seinen kritischen Bereich verlassen hätte. Damit wäre die Implementierung falsch.