Informatik 4 (StuPO90)/Semaphoren

A Pattern Language for the usage of Semaphores

(Nach http://c2.com/cgi/wiki?PatternLanguage)

Dafür zu sorgen, dass mehrere nebenläufige Prozesse korrekt miteinander arbeiten, ist erstaunlich schwierig. Speziell Mehrseitige Synchronisation bereitete mir beim Verstehen und Erklären besondere Probleme. Um die dabei auftretenden Probleme übersichtlicher zu erklären habe ich diese "Pattern Language" formuliert.

Ich würde mich sehr über Feedback (mhaecker@cs.tu-berlin.de) zu den Beispielen und Formulierungen freuen.

Folgende Probleme werden behandelt:

• Locking für kritische Sektionen
• Locking für beschränkten Zugriff (n clients)
• Locking zum gegenseitigen Ausschluss von zwei Gruppen
• Locking für Priorisierung einer von mehreren Gruppen

1. "Critical Section"

Eine kritische Sektionen ist ein Stück Code, in dem nur ein Prozess gleichzeitig sein darf. Diese Bereiche kann man schützen, indem man sie in Semaphoren "verpackt".

Beispiel:

criticalSection = Semaphore(1)

criticalSection.P()
	.. etwas in der kritischen Sektion tun ..
criticalSection.V()

2. "Restricted Section"

Will man einer bestimmten Anzahl von Prozessen den Aufenthalt in einem Bereich gestatten, nennt man das eine beschränkte Sektion. Dies setzt man um, indem man diese Sektion in die P()- und V()-Operationen einer Semaphore fasst, die mit dem gewünschten Wert initialisiert ist. Streng genommen ist dies also eine Erweiterung der "Critical Section".

Beispiel:

restrictedSection = Semaphore(n)

restrictedSection.P()
	... etwas tun in der kritischen Sektion
restrictedSection.V()

Jetzt können maximal n Prozesse den kritischen Abschnitt gleichzeitig betreten.

3. "Mutual Exclusion"

Wenn ein Stück Code nur von jeweils einer Art von Prozessen betreten werden darf, dann verwendet man eine Semaphore um gegenseitigen Ausschluss zu realisieren.

Beispiel:

wenn ich der erste Prozess meiner Art bin der den kritischen Abschnitt betreten will:
	hole ich mir die Semaphore

.. etwas im kritischen Abschnitt tun ..

wenn ich der letzte Prozess meiner Art bin der den kritischen Abschnitt verlässt:
	gebe ich die semaphore frei

Sowohl der erste als auch der zweite Test, ob man der erste bzw. letzte ist, ist natürlich /*TODO: ist das echt so natürlich?Wenn man den Zähler dazu erwähnt schon*/ ein kritischer Abschnitt und muss entsprechend gelockt werden. Etwas formaler:

criticalSection = Semaphore(1), mutualExclusion = Semaphore(1)

criticalSection.P()
	howManyInCriticalSection++
	if 1 == howManyInCriticalSection:
		mutualExclusion.P()
criticalSection.V()

.. etwas in dem kritischen Abschnitt erledigen,
	 in dem jetzt diese Prozesse unter sich sind ...

criticalSection.P()
	howManyInCriticalSection--
	if 0 == howManyInCriticalSection:
		mutualExclusion.V()
criticalSection.V()

Hier wird das Muster "Critical Section" zusätzlich gebraucht, damit der Zähler zwischen seiner Veränderung und dem Test welchen Wert er hat nicht von einem anderen Prozess verändert werden kann.

Kombiniert man "Critical Section" mit "Mutual Exclusion" dann kann man entweder die "Critical Section" direkt um den kritischen Abschnitt legen, oder sie um das gesamte außen herum "wickeln".

4. "Priority"

Zwei ineinander verschachtelte Semaphoren können genutzt werden, um eine Art von Prozessen gegen andere zu priorisieren. Dies ist eine Ergänzung des vorhergehenden Musters.

Beispiel:

äusserer kritischer Abschnitt <- An dieser Semaphore bleiben alle Prozesse 
				 "hängen" bis auf einen
	innerer Kritischer Abschnitt <- an dieser Semaphore ist also immer 
					nur maximal ein Prozess gleichzeitig

		.. kritischer Bereich ..

	innerer Kritischer Abschnitt
äusserer kritischer Abschnitt

/*TODO: und die andere Prozessart?*/

Die Semaphore, die den inneren kritischen Abschnitt schützt, kann jetzt von einem anderen Prozess aus einer anderen Prozessgruppe gelockt werden. Wenn das passiert, dann muss er maximal so lange warten, bis sie der Prozess der sie gerade besitzt freigibt, da nur einer aus dieser Gruppe daran "hängen" kann. Er hat also alle anderen Prozesse die an der äusseren Semaphore warten überholt.

Etwas Formaler:

outerCriticalSection = Semaphore(1), innerCriticalSection = Semaphore(1)

outerCriticalSection.P()
	innerCriticalSection.P()
		
		.. kritischer Bereich ..
	
	innerCriticalSection.V()
outerCriticalSection.V()

Um dieses Muster anzuwenden muss man es mit dem Muster "Mutual Exclusion" kombinieren, indem der erste einer anderen Gruppe sich die Semaphore des inneren kritischen Abschnitts "sichert". /* TODO: klarer machen, das die andere Gruppe die innere semaphore als "mutex" verwendet. */

Will man "Priority" mit "Restricted Section" kombinieren, ist zu beachten, das die begrenzte kritische Sektion der Gruppe die überholt werden soll natürlich den gesamten Code mit einschließt, der die Priorität sichert. Tut man das nicht, kann das Überholen nicht garantiert werden. Auf der anderen Seite, bei den Prozessen, die überholen sollen, muss die begrenzte kritische Sektion innerhalb des Codes liegen, der die Priorität garantiert, da andernfalls in dem Spezialfall, in dem die Begrenzung auf eins liegt, das Überholen nicht funktioniert.

/* TODO: klar machen, das die beiden restrictions verschiedene semaphoren sind! */

/*TODO: hier einen Punkt einfügen, der einseitige Synchronisationabdeckt*/

5. "Reduction"

Die Lösungen, die man aus der Kombination dieser Muster erhält, verwenden in Spezialfällen mehr Semaphoren als unbedingt nötig. Man kann daher manchmal einige der Semaphoren weglassen, da ihre Funktion schon von einer der anderen Semaphoren erfüllt werden.