Tutorium 5

Tutorium #510.5. bzw. 17.5.

Bei dieser Ausarbeitung handelt es sich um keine offizielle Lösung des Lehrstuhls. Dies sind nur Lösungsansätze, welche keinen

Anspruch auf Korrektheit oder Vollständigkeit erheben.

c.deckert@me.com

Monday, May 10, 2010

tr.im/wifotut

Monday, May 10, 2010

Agenda

• Aufgabe 1: Mutexe und Sempaphore

• 2. Aufgabe (Deadlocks)

Monday, May 10, 2010

Aufgabe 1• Java bot ursprünglich nur folgende Möglichkeiten

zur Synchronisation an:

• Das Attribut synchronized für Methoden. Damit wird im Methodenrumpf gegenseitiger Ausschluss realisiert.

• Die Monitor-Methoden wait() und notify(). Diese Methoden können für jedes Java-Objekt aufgerufen werden. Die Methode notify() hebt eine durch wait() hervorgerufene Blockierung im Objekt auf.

Monday, May 10, 2010

public class Semaphore { int s; public Semaphore(int initial) { s = initial; }

synchronized public void P() throws InterruptedException { s--; if (s < 0) wait(); }

synchronized public void V() { s++; if (s <= 0) notify(); }

Monday, May 10, 2010

Aufgabe 1b• Nehmen wir an, dass wir ein Betriebssystem

haben, das nur Mutexe unterstützt, wir aber trotzdem Semaphore verwenden möchten. Überlegen Sie sich, wie Sie einen Semaphor mit Mutexen implementieren können. Diese Lösung sollte kein busy waiting verwenden. Da das System nur Mutexe unterstützt, dürfen auch keine Interrupts abgeschaltet werden, etc. Schreiben Sie Ihre Lösung in Pseudo-code auf.

Monday, May 10, 2010

Monday, May 10, 2010

Monday, May 10, 2010

class Semaphore { Mutex wait = new Mutex(0); int value;

public Semaphore(int initalValue) { value = initalValue; }

public void Down() { if (value == 0) { wait.Lock(); } else { value = value--; } }

public void Up() { if (wait.ProcessesWaiting())

{ wait.Unlock(); } else { value = value++; } } }

Monday, May 10, 2010

2 Probleme:• Änderungen von value sind nicht geschützt, wenn

mehrer Prozesse Up() bzw. Down() gleichzeitig ausführen. Dieses Problem lässt sich mit einem weiteren Mutex protect lösen, so dass Up() und Down() mutually exclusive sind.

• Wie sieht die Methode „ProcessesWaiting()“ aus? Mit anderen Worten: Wie finden wir heraus, ob auf wait gerade Prozesse warten? Eine Möglichkeit ist, die Anzahl der wartenden Prozesse in einer Variable count zu speichern. Dabei muss natürlich auch count geschützt werden.

Monday, May 10, 2010

class Semaphore { Mutex wait = new Mutex(0); Mutex protect = new Mutex(1); int value; int count = 0;

public Semaphore(int initalValue) { value = initalValue; }

public void Down() { protect.Lock(); if (value == 0) { count = count++; protect.Unlock(); wait.Lock(); } else { value = value--; protect.Unlock(); } }

public void Up() { protect.Lock();

if (count > 0) { count = count--; wait.Unlock(); protect.Unlock(); } else { value = value++; protect.Unlock(); } } }

Monday, May 10, 2010

Aufgabe 2

• Ist es möglich einen Deadlock zu geraten, an dem nur ein Prozess beteiligt ist? Begründen Sie Ihre Antwort.

Monday, May 10, 2010

Antwort

• Nein. Das folgt direct aus der Hold-and-Wait Bedingung. (Folie 16)

Monday, May 10, 2010

Aufgabe 2b

• Deadlock Detection: Betrachten Sie den folgenden Resourcen-Graphen. Befindet sich das System in einem Deadlock?

Monday, May 10, 2010

Antwort

• Ja, es ist in einem Deadlock, da es einen Zyklus im Graphen gibt (S -> C -> F).

Monday, May 10, 2010