Tag Archiv für ExecutorService

Erzeuger-Verbraucher-Problem

Concurrency Utilities

Das folgende Beispiel habe ich für ein Seminar in der Fachhochschule angefertigt, da ich es ganz gelungen finde, möchte ich es hier veröffentlichen.

Thema waren die Concurrency Utilities in Java und die Bearbeitung des Erzeuger-Verbraucher-Problems.

Erzeuger-Verbraucher-Problem

Das Erzeuger-Verbraucher-Problem ist eine Problemstellung aus der Prozesssynchronisation. Es gilt dabei die Problematik der Zugriffsreihenfolge auf eine gemeinsame Datenstruktur von erzeugenden Prozessen und verbrauchenden Prozessen zu lösen. Dabei muss zum Beispiel verhindert werden, dass ein verbrauchender Prozess Zugriff auf eine Datenstruktur erhält, wenn diese keine Elemente zum Entnehmen beinhaltet. Das kann zum einen der Fall sein, wenn die Datenstruktur leer ist, zum anderen aber auch wenn eine Mindestanzahl an Restelementen (Puffer) gefordert ist. Auch gilt es zu verhindern, dass ein erzeugender Prozess Elemente in eine Datenstruktur ablegt, die schon voll ist.

Lösung

Gelöst wird das Problem durch die Benutzung von drei Semaphoren. Ein binärer Semaphor dient zum Schutz der Datenstruktur (mutex). Zwei zählende Semaphoren stellen die Kapazität (sem_write) und die vorhandenen Elemente (sem_read) der Struktur dar. Versucht nun ein erzeugender Prozess Daten in die Struktur abzulegen, muss er zuerst den Semaphor sem_write mit der gewünschten Anzahl an Elementen passieren. Wenn dies erfolgreich war, muss sichergestellt werden, dass nicht gerade ein anderer Prozess auf die Datenstruktur zugreift. Dafür ist der Semaphor mutex zuständig. Erst nach erfolgreichem Passieren von mutex, darf die angeforderte Anzahl an Elementen in die Datenstruktur abgelegt werden. Nach diesem Vorgang wird der durch mutex gesicherte Bereich wieder freigegeben. Am Ende werden für den Semaphor sem_read die Anzahl der hinzugefügten Elemente freigegeben. Im Falle des verbrauchenden Prozesses sähe dieser Vorgang in einer Kurzschreibweise, bei der P() für passieren und V() für freigegeben steht, wie folgt aus:

P (sem_read, Anz);   // Anfordern von Anz Elementen zum Verbrauchen
P (mutex);           // geschützen Bereich betreten
verbrauchen(Anz);    // Verbrauchen von Anz Elementen
V (mutex);           // geschützen Bereich verlassen
V (sem_write, Anz);  // Anz Elemente zum Hinzufügen wieder freigeben

Beispiel

Ein Wassertank soll die gemeinsame Datenstruktur darstellen. Zwei Wasserwerke stellen die erzeugenden Prozesse dar. Vier Häuser die verbrauchenden Prozesse. Der Tank soll einen Puffer von 100 Liter Wasser haben und ein Fassungsvermögen von 1000 Liter.

Die Lösung für dieses Beispiel sieht wie folgt aus:
Der zu schützende Bereich erhält den binären Semaphor
sem_tank = new Semaphore(1);, der zählende Semaphor für die Kapazität sem_hinzufuegen = new Semaphore(1000); und der zählende Semaphore für die vorhandenen Elemente sem_entnehmen = new Semaphore(-100);. Im letzten Fall wird ein Semaphor mit einer negativen Anzahl von Erlaubnissen (engl. permits) erzeugt, um so das Problem des Puffers von 100 Liter zu lösen. Ein verbrauchender Prozess kann erst Wasser entnehmen, wenn der Semaphor über 100 steigt.

In Java sieht die hinzufügende Methode folgendermaßen aus:

public void hinzufuegen(Wasserwerk ww) {
	try {
		sem_hinzufuegen.acquire(ww.getLieferMenge());
		sem_tank.acquire();
	} catch (InterruptedException e) {	}

	fuellstand+=ww.getLieferMenge();

	sem_tank.release();
	sem_entnehmen.release(ww.getLieferMenge());
}

 Und die entnehmende Methode so:

public void entnehmen(Haushalt hh,int wassermenge) {
	try {
		sem_entnehmen.acquire(wassermenge);
		sem_tank.acquire();
	} catch (InterruptedException e1) {	}

	fuellstand-=wassermenge;

	sem_tank.release();
	sem_hinzufuegen.release(wassermenge);
}

Der vollständige Sourcecode kann als Eclipse-Projekt hier heruntergeladen werden:  ErzeugerVerbraucherProblemEclipseProjekt.zip

Oder wer das ganze nur mal laufen sehen möchte, der kann das auch direkt von der Seite erledigen und zwar über den Webstart.  Falls der Browser mit dem Dateityp nichts anfangen kann: Rechtsklick auf „Webstart“ und „speichern unter“ wählen. Danach dann manuell starten.

Webstart: 

Vielleicht kurz zur „Bedienung“ noch ein paar Worte:


In der Oberfläche existieren neun verschiedene Klickzonen. Ich habe diese in dem Screenshot neben diesen Text eingezeichnet und mit Nummern versehen.

Nr.1-4 sind die Haushalte (HH). Ein klick darauf deaktiviert bzw. aktiviert diese. Der aktuelle Auftrag, also die Wassermenge die von ihnen schon angefordert wurde, wird aber noch bearbeitet.

Nr. 5 blendet im Himmel ein paar Debugmeldungen ein.
Nr. 6-7 sind die Wasserwerke (WW), die wie die HH mit einem Klick deaktiviert und aktiviert werden können.
Nr. 8 und 9 sind „böse“, denn sie greifen in den über Semaphoren gesicherten Ablauf ein.  Sie sind zum einen dafür gedacht, um zu zeigen was ein manueller Eingriff bewirken würde und zum anderen für Debugzwecke und zum Spaß Grimace

Nr. 8 füllt den Tank komplett. Schlecht, wenn ein WW gerade damit beschäftigt ist Wasser rein zu pumpen –> boom!
Nr. 9  leert den Tank komplett bis auf den Pufferinhalt. Schlecht, wenn zu viele HH in der Warteschlange zum abpumpen stehen –> flupp! (ok, eigentlich würde dann halt nur kein Wasser kommen, aber das wäre ja langweilig und man hätte nichts zum visualisieren)