Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
images
README.adoc

README.adoc

Praktikum Concurrency 2

1. Producer-Consumer Problem

1.1. Producer- und Consumer-Thread

Vorgegeben ist eine Implementation eines zirkulären Buffers (CircularBuffer.java, Buffer.java) mit folgendem Design:

CircularBuffer

Als erstes soll ein "Producer" und ein "Consumer" implementiert werden. Unten ist das Gerüst für beide abgebildet (CircBufferTest.java):

class Producer extends Thread {
    public Producer(String name, Buffer buffer, int prodTime) {
        ...
    }
    public void run() {
        ...
    }
}

class Consumer extends Thread
{
    public Consumer(String name, Buffer buffer, int consTime) {
        ...
    }
    public void run() {
        ...
    }
}

Der Producer soll Daten in den Buffer einfüllen, und der Consumer soll Daten herausholen. Auf den Buffer soll nur über das Interface zugegriffen werden. Das Zeitintervall, in dem ein Producer Daten einfüllen kann, ist mit sleep((int)(Math.random()*prodTime)) zu definieren. Die Zeit fürs konsumieren können Sie entsprechend mit sleep((int)(Math.random() * consTime)) bestimmen.

Für Producer und Consumer wurde bereits ein Testprogramm (class CircBufferTest) geschrieben. Testen Sie damit ihre Consumer- und Producer-Klassen. Versuchen sie den generierten Output auf der Console richtig zu interpretieren! Spielen sie mit den Zeitintervallbereichen von Producer (maxProdTime) und Consumer (maxConsTime) und ziehen sie Schlüsse. Erstellen sie über die Modifikation von prodCount und consCount mehrere Producer bzw. Consumer.

Note

Generieren sie in den selber implementierten Klassen keine eigene Ausgabe. Ändern sie den bestehenden Code nicht. Es stehen zwei Ausgabefunktionen zur Auswahl: print() und print2().

1.2. Thread-Safe Circular Buffer

In der vorangehenden Übung griffen mehrere Threads auf den gleichen Buffer zu. Die Klasse CircularBuffer ist aber nicht thread-safe. Was wir gemacht haben, ist daher nicht tragbar. Deshalb soll jetzt eine Wrapper Klasse geschrieben werden, welche die CircularBuffer-Klasse "thread-safe" macht. Das führt zu folgendem Design:

GuardedCircularBuffer

Aufrufe von put blockieren, solange der Puffer voll ist, d.h., bis also mindestens ein leeres Puffer-Element vorhanden ist. Analog dazu blockieren Aufrufe von get, solange der Puffer leer ist, d.h, bis also mindestens ein Element im Puffer vorhanden ist.

Tip

Verwenden Sie den Java Monitor des GuardedCircularBuffer-Objektes! Wenn die Klasse fertig implementiert ist, soll sie in der CircBufferTest Klasse verwendet werden.

Beantworten Sie entweder (a) oder (b) (nicht beide):

  1. Falls Sie bei der Implementierung der Klasse GuardedCircularBuffer die Methode notifyAll benutzt haben: Hätten Sie statt notifyAll auch die Methode notify verwenden können oder haben Sie notifyAll unbedingt gebraucht? Begründen Sie Ihre Antwort!

  2. Falls Sie bei der Implementierung der Klasse GuardedCircularBuffer die Methode notify benutzt haben: Begründen Sie, warum Sie notifyAll nicht unbedingt gebraucht haben!

2. Single-Lane Bridge

Die Brücke über einen Fluss ist so schmal dass Fahrzeuge nicht kreuzen können. Sie soll jedoch von beiden Seiten überquert werden können. Es braucht somit eine Synchronisation, damit die Fahrzeuge nicht kollidieren. Um das Problem zu illustrieren wird eine fehlerhaft funktionierende Anwendung, in welcher keine Synchronisierung vorgenommen wird, zur Verfügung gestellt. Ihre Aufgabe ist es die Synchronisation der Fahrzeuge einzubauen.

Die Anwendung finden Sie im Ordner handout/Bridge. Nach dem Kompilieren (z.B. mit mvn compile) können Sie diese starten, in dem Sie die Klasse Main ausführen (z.B. mit mvn exec:exec). Das GUI sollte selbsterklärend sein. Mit den zwei Buttons können sie Autos links bzw. rechts hinzufügen. Sie werden feststellen, dass die Autos auf der Brücke kollidieren.

bridge overview
Figure 1. Single-Lane Bridge GUI

Um das Problem zu lösen müssen Sie die den GUI Teil der Anwendung nicht verstehen. Sie müssen nur wissen, dass Fahrzeuge die von links nach rechts fahren die Methode controller.enterLeft() aufrufen bevor sie auf die Brücke fahren (um Erlaubnis fragen) und die Methode controller.leaveRight() aufrufen sobald sie die Brücke verlassen. Fahrzeuge in die andere Richtung rufen entsprechend die Methoden enterRight() und leaveLeft() auf. Dabei ist controller eine Instanz der Klasse TrafficController welche für die Synchronisation zuständig ist. In der mitgelieferte Klasse sind die vier Methoden nicht implementiert (Dummy-Methoden).

  1. Bauen sie die Klasse TrafficController in einen Monitor um der sicherstellt, dass die Autos nicht mehr kollidieren. Verwenden Sie dazu den Lock und Conditions Mechanismus.

    Tip
    Verwenden Sie eine Statusvariable um den Zustand der Brücke zu repräsentieren (e.g. boolean bridgeOccupied).
  2. Erweitern Sie die Klasse TrafficController so, dass jeweils abwechslungsweise ein Fahrzeug von links und rechts die Brücke passieren kann. Unter Umständen wird ein Auto blockiert, wenn auf der anderen Seite keines mehr wartet. Verwenden Sie für die Lösung mehrere Condition Objekte.

  3. Bauen Sie die Klasse TrafficController um, so dass jeweils alle wartenden Fahrzeuge aus einer Richtung passieren können und erst wenn keines mehr wartet die Gegenrichtung fahren kann.

    Tip
    Mit ReentrentLock.hasWaiters(Condition c) können Sie abfragen ob Threads auf eine bestimmte Condition warten.

3. The Dining Philosophers (optional)

Beschreibung des Philosophen-Problems:

Fünf Philosophen sitzen an einem Tisch mit einer Schüssel, die immer genügend Spaghetti enthält. Ein Philosoph ist entweder am Denken oder am Essen. Um zu essen braucht er zwei Gabeln. Es hat aber nur fünf Gabeln. Ein Philosoph kann zum Essen nur die neben ihm liegenden Gabeln gebrauchen. Aus diesen Gründen muss ein Philosoph warten und hungern, solange einer seiner Nachbarn am Essen ist.

philosopher table numbered
Figure 2. Philosopher Table
philosopher ui
Figure 3. Philosopher UI

Das zweite Bild zeigt die Ausgabe des Systems, das wir in dieser Aufgabe verwenden. Die schwarzen Kreise stellen denkende Philosophen dar, die gelben essende und die roten hungernde. Bitte beachten Sie, dass eine Gabel, die im Besitz eines Philosophen ist, zu dessen Teller hin verschoben dargestellt ist.

  1. Analysieren Sie die bestehende Lösung (PhilosopherGui, PhilosopherTable), die bekanntlich nicht Deadlock-frei ist. Erzeugen Sie ein Projekt in ihrer IDE und starten Sie anschliessend die Applikation. Nach einiger Zeit geraten die Philosophen in eine Deadlock-Situation und verhungern. Überlegen Sie sich, wo im Code der Deadlock entsteht und versuchen Sie, dessen Auftreten schneller herbeizuführen.

  2. Passen Sie die bestehende Lösung so an, dass keine Deadlocks mehr möglich sind. Sie müssen im Wesentlichen den ForkManager so anpassen, dass sich Gabelpaare in einer atomaren Operation belegen bzw. freigegeben lassen. Die Ausgabe müssen Sie nicht anpassen. Die Änderungen an der Klasse Philosoph sind minimal, da sie nur den Methodenaufruf für die Freigabe bzw. Belegung der Gabeln ändern müssen.

    Note
    Verwenden Sie für die Synchronisation Locks und Conditions!
    Testen Sie ihre Lösung auf Deadlock-Freiheit!
  3. (optional) In der Vorlesung haben Sie mehrere Lösungsansätze kennen gelernt. Implementieren Sie einmal einen alternativen Ansatz, wie zum Beispiel die Nummerierung der Betriebsmittel.

You can’t perform that action at this time.