Hausübungsblatt 3 - Universität Paderborn

Sommersemester 2011
Konzepte und Methoden der Systemsoftware
Hausübung 03
Universität Paderborn
vom 13.05.2011 bis 27.05.2011
Fachgebiet Rechnernetze
3 + 2 = 5 Punkte
Aufgabe 1: Fairness
1. Es werde ein Mehrprogrammsystem mit drei Nutzern und einer einzigen Ressource mit Kapazität
C betrachtet.
(a) Bestimmen Sie für jeden Benutzer die Rate (r1 , r2 , r3 ), bei der die Ressource fair an alle drei
Nutzer verteilt wird. Nutzer sind nicht unterscheidbar und es gibt keinen maximalen Bedarf.
2
(b) Der maximale Bedarf mi der drei Benutzer sei gegeben als m1 = 13 x, m2 = 15
x und m3 = 15 x.
Bestimmen Sie das größtmögliche x, für das der Bedarf jedes Benutzers erfüllt werden kann.
(c) Es seien m1 , m2 und m3 gegeben wie oben und x = 2C. Bestimmen Sie für jeden Benutzer
eine faire Rate ri und geben Sie den Rechenweg an. Ergebnisse ohne vollständige Angabe
des Rechenweges werden nicht gewertet.
2. Es werde jetzt ein Mehrprogrammsystem mit drei Nutzern ohne maximalen Bedarf und zwei Ressourcen mit den Kapazitäten C1 = 980 und C2 = 420 betrachtet. Die Ressourcen-Verbrauchsverhältnisse
der Benutzer seien durch die Vektoren v1 = (1; 2), v2 = (3; 1) und v3 = (a; 0) gegeben.
Bestimmen Sie jetzt die max-min-faire Ratenallokation R in Abhängigkeit des Parameters a. Eine
Ratenallokation ohne vollständige Angabe des Rechenweges wird nicht gewertet.
Hinweis: Fallunterscheidung in a.
Aufgabe 2: Verteilte Berechnung von Fairness
5 + 2 + 2 = 9 Punkte
Sie wollen die Fairness für einige Ressourcen in einem verteilten System verwalten, ohne dieses an einer
zentralen Stelle zu tun.
Für diese Übung werden wir den Algorithmus von Low und Lapsley [LL99] verwenden:
Algorithm A1: Synchronous Gradient Projection
Link l’s algorithm: At times t = 1, 2, . . . link l:
1. Receives rates xs(t) from all sources s ∈ S(l) that go through link l.
2. Computes a new price
h
i+
pl (t + 1) = pl (t) + γ(xl (t) − cl )
where xl (t) = ∑s∈S(l) xs (t)
3. Communicates new price pl (t + 1) to all sources s ∈ S(l) that use link l.
KMS Sommersemester 2011
Hausübung 03
1
Source s’s algorithm:
At times t = 1, 2, . . . link l:
1. Receives from the network the sum ps (t) = ∑l∈L(s) pl (t) of link prices in its path.
2. Chooses a new transmission rate xs(t + 1) for the next period of price given by 1.
xs (t + 1) = xs (ps (t))
where xs (·) is given by 1.
3. Communicates new rate xs (t + 1) to links l ∈ L(s) in itspath.
Hierbei ist [x]+ = max(x, 0), γ > 0 ist die Schrittweite, cl die Kapazität eines Links, xs (·) ist definiert als:
0
s
xs (p) = [Us −1 (p)]M
ms
(1)
Us (p) ist die utility Funktion der Quelle s, [x]ba = min(max(x, a), b).
Für die Verwendung dieses Algorithmusses zur Berechnung von Fairness identifizieren wir die Ressourcen mit den Links l ∈ L, die Nutzer mit den Quellen s ∈ s.
Implementieren Sie den Algorithmus in einer Programmiersprache Ihrer Wahl (z.B. Matlab/Octave,
Python, C, . . . ). Die Abgabe des Quelltextes ist erforderlich. Nehmen Sie als Schrittgröße 0, 0001.
a) Gegeben sind drei Nutzer mit Us (x) = 0.01 log(1+xs ). Es sind zwei Ressourcen R1 und R2 vorhanden.
V1 = [1, 1], V2 = [1, 1], V3 = [0, 1]. Nutzer 1 ist in t ∈ [0, 240] aktiv, Nutzer 2 in t ∈ [80, 320] und Nutzer
3 in t ∈ [160, 400]. Plotten Sie die Auslastung der Ressourcen über die Zeit in einem geeigneten
Programm wie z.B. gnuplot. Nehmen Sie weiterhin für die beiden Ressourcen eine Kapazität von 5
an. Als Minimum und Maximum Werte für die Nutzer (ms , Ms ) ist 0 und 10 gegeben. Die Variablen
xs und pl sind am Anfang mit 0 initialisiert.
Plotten Sie den Verlauf von xs für die drei Nutzer über die Zeit t = [0 . . . 400].
b) Interpretieren Sie das Ergebnis aus Aufgabenteil a. Beschreiben und erklären Sie die wesentlichen
Merkmale des Graphen.
c) Behalten Sie die Parameter wie in Aufgabe a bei. Ändern sie nun die Schrittweite γ auf 0.0003 und
0.00001. Plotten Sie auch die Graphen zu den xs über die Zeit. Wie verändert sich das Verhalten
gegenüber Aufgabe a. Erklären Sie kurz das Verhalten der Graphen.
KMS Sommersemester 2011
Hausübung 03
2
1 + 1, 5 + 1, 5 + 1 + 3 + 1 = 9 Punkte
Aufgabe 3: Semaphoren
Sie werden von der Jurassic Park AG angestellt, um die Zugangskontrolle der Besucher zu den vollautomatischen Tourwagen zu programmieren. Die Wagen fahren nacheinander auf eine Einstiegsplattform
(im Bild grau dargestellt), warten bis zwei Besucher eingestiegen sind und fahren anschließend los.
Betrachten Sie für diese Aufgabe die Besucher und die Wagen als Threads, die die entsprechende “Arrive”-Methode aufrufen, sobald sie für eine Rundfahrt bereit sind. Es existiert bereits der unten
angegebene Algorithmus.
Reparieren sie den Algorithmus, bevor ein Unglück geschieht!
Hinweis: In dieser Aufgabe betrachten wir nur das Einsteigen.
Algorithm 1 carArrive
1: while (carsOnPlatform > 0) {}
2: carsOnPlatform = 1
3: enterLoadingPlatform()
4: openDoors()
5: freeSeats = 2
6: while (freeSeats > 0) {}
7: closeDoors()
8: leaveLoadingPlatform()
9: carsOnPlatform = 0
Algorithm 2 passengerArrive
1: while (freeSeats < 1) {}
2: enterCar()
3: freeSeats = freeSeats - 1
1. Welche zwei Fälle sollten anscheinend vermieden werden? Geben Sie für jeden dieser zwei Fälle
ein Beispiel an, wie er trotzdem eintreten kann.
Verwenden Sie Sempahoren, um den Algorithmus zu reparieren. Der Algorithmus muss danach fehlerfrei
funktionieren und darf kein busy-waiting mehr durchführen.
2. Benennen Sie die benötigten Semaphoren und erläutern sie kurz deren jeweilige Aufgabe. Auf
welche Werte müssen Ihre Semaphoren initialisiert werden? (Leere Platform, keine Passagiere/Wagen vor Ort)
3. Schreiben Sie eine fehlerfreie carArrive und passengerArrive Methode.
KMS Sommersemester 2011
Hausübung 03
3
4. Welches Problem kann auftreten, wenn Sie in Ihrem Algorithmus mehrere Wagen auf der Platform
zulassen? Hinweis: Die Wagen würden nebeneinander auf der Platform stehen. Was müssen Sie
tun, um dieses Problem zu beseitigen?
5. Betrachten Sie wieder die Situation mit nur einem Tourwagen auf der Platform. Die Tourwagen
sollen nun mit Audiokommentaren unterlegt werden in Deutsch und in Englisch. Dabei sollen
in einem Wagen immer nur Personen mit der gleichen Sprache einsteigen. Anstatt einer Warteschlange gibt es nun für jede Sprache eine eigene Schlange. Geben Sie die benötigten Methoden
carArrive, passengerArriveGerman und passengerArriveEnlgish an.
6. Anstatt zwei verschiedenen Sprachen sollen Sie nun eine “VIP” Warteschlange und eine normale
Warteschlange implementieren. Die VIP Warteschlange soll immer bevorzugt behandelt. Erklären
Sie mit welcher Technik Sie dieses Problem lösen können oder ob das Problem mit Semphoren
nicht lösbar ist.
Literatur
[LL99] Steven H. Low and David E. Lapsley. Optimization flow control, i: basic algorithm and convergence. IEEE/ACM Trans. Netw., 7:861–874, December 1999.
KMS Sommersemester 2011
Hausübung 03
4