Zweitgutachter:
Danksagung
An dieser Stelle mochte ich Prof. Dr. Friedhelm Meyer auf der Heide und Olaf Bonorden fur die hervorragende Betreuung und Ulrich Ahlers fur das Bereitstellen der Testrechner danken.
Erklarung
Hiermit versichere ich, dass ich die vorliegende Arbeit sowie die zugehorige Software selb- standig angefertigt und keine weiteren als die angegebenen Quellen und Hilfsmittel benutzt habe.
Paderborn, im Februar 2005
4.2.1 Durchfuhrung der initialen Verteilung . . . . . . . . . . . . . . . . . 26
4.2.2 Der Lebenszyklus eines BSP-Programms . . . . . . . . . . . . . . . 29
4.2.3 Implementierung von PON . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.4 Implementierung von PMN . . . . . . . . . . . . . . . . . . . . . . 31
4.2.5 Implementierung von SOJ . . . . . . . . . . . . . . . . . . . . . . . 33
4.2.6 Implementierung von SMJ . . . . . . . . . . . . . . . . . . . . . . . 34
5 Analyse 37
5.3 Lastmessungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.3.5 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4.1 Die Testbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6 Zusammenfassung und Ausblick 97
6.1 Die Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
A.1 Der Quelltext von PUBWCL v2.0 . . . . . . . . . . . . . . . . . . . . . . . 101
B Quellcode 109
B.2 Das BSP-Programm fur die Benchmarks . . . . . . . . . . . . . . . . . . . 110
B.3 Der Algorithmus IVT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
B.4 Der Algorithmus MZA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
B.5 Der Algorithmus OVT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
iv
Zusammenfassung
1
ZUSAMMENFASSUNG
2
Wenn man bedenkt, wie viele Millionen Rechner uber die ganze Welt verteilt existieren, kann man sich leicht vorstellen, dass deren Idle-Zeit zusammengenommen eine riesige unge- nutzte Rechenkapazitat darstellt. Daher beschaftigen sich seit einiger Zeit Wissenschafter damit, wie man diese ungenutzte Rechenkapazitat fur rechenintensive Aufgaben nutzen kann.
In den meisten Fallen werden Programme, im Folgenden als Clients bezeichnet, zum Down- load angeboten, mit denen die Besitzer bzw. Administratoren der Rechner ihre ungenutzte Rechenkapazitat auf freiwilliger Basis1 einem Großprojekt zufuhren konnen.
distributed.net [dis05], Great Internet Mersenne Prime Search (GIMPS) [GIM05], Search for Extraterrestrial Intelligence (SETI@home) [set05] oder Folding@home Distributed Com- puting [fol05] sind z.B. bekannte derartige Projekte.
Eine gemeinsame Eigenschaft der genannten Projekte ist, dass das zu untersuchende Pro- blem von einem zentralen Server in viele kleine Teilprobleme zerlegt wird; die Clients, die – oftmals in Form von Bildschirmschonern – im Hintergrund die Berechnungen durchfuhren, laden sich ein Teilproblem herunter, losen es, schicken das Ergebnis zuruck zum Server und fahren mit dem nachsten Teilproblem fort.
Bei dieser Herangehensweise finden die Berechnungen zwar parallel statt, jedoch konnen zeitgleich nur von einander unabhangige Teilprobleme gelost werden, da zwischen den Clients keinerlei Kommunikation stattfindet.
Um diese Einschrankung aufzuheben, wurde in [Geh03] das System Paderborn Univer- sity BSP-based Web Computing Library (PUBWCL) entwickelt. PUBWCL fuhrt massiv parallele Algorithmen auf uber das Internet verteilten Rechnern aus, die nach dem Bulk- Synchronous Parallel (BSP)-Modell miteinander kommunizieren und sich synchronisieren. Nahere Informationen zum BSP-Modell und PUBWCL folgen in den Kapiteln 2.1 und 2.4.
1Bei einigen Projekten wird eine Belohnung ausgesetzt fur denjenigen, auf dessen Recher eine Losung gefunden wurde.
3
Da die PUBWCL zugeteilten Rechenkapazitaten auf den einzelnen Rechnern standig schwan- ken und ein BSP-Programm bereits durch einen langsamen Prozess
’ ausgebremst‘ werden
kann, unterstutzt PUBWCL Migrationen (Details in den Kapiteln 2.2 und 2.4), um die Rechenlast zur Laufzeit geeignet umverteilen zu konnen.
Um die Rechenlast nun sinnvoll zu verteilen, bedarf es intelligenter Lastbalancierungsstra- tegien, die fur jeden BSP-Prozess entscheiden, ob eine Migration nutzlich ist, und welcher Rechner ggf. das Migrationsziel sein sollte. In dieser Diplomarbeit werden deshalb verschie- dene Lastbalancierungsstrategien fur PUBWCL implementiert und analysiert.
Im Folgenden werden zunachst wichtige Grundlagen vorgestellt (Kapitel 2). Die Konzeption der Arbeit wird in Kapitel 3 dargelegt. Den Schwerpunkt bilden die Kapitel 4 und 5 uber die Implementierung und Analyse. Eine abschließende Zusammenfassung wird in Kapitel 6 gegeben.
Verwandte Arbeiten
In [LMSadH04] stellen Stefano Leonardi, Alberto Marchetti-Spaccamela und Friedhelm Meyer auf der Heide ein Modell vor, in dem Computer mit gleich schnellen Prozessoren zu jedem Zeitpunkt entweder vollstandig oder gar nicht ausgelastet sind; jeder Computer bietet also eine Sequenz disjunkter Zeitintervalle an, in denen er verfugbar ist. Die Intervall- großen und die Joblangen (die Berechnungsphase eines Superstep in einem BSP-Programm laßt sich offensichtlich in einzelne Jobs zerlegen) sind Zweierpotenzen. In dem vorgestellten Modell ist keine Preemption moglich, d.h. die Prozesse konnen nicht an einem Intervallende angehalten und im nachsten Intervall fortgesetzt werden, sondern sie werden am Interval- lende abgebrochen und mussen spater neu gestartet werden. Die Autoren nehmen weiter an, dass sich die verfugbare Rechenkapazitat eines Netzwerks von n Computern P1, . . . , Pn
zwischen zwei auf einander folgenden Zeitabschnitten, I1 und I2, nicht dramatisch andert, und formulieren zwei Einschrankungen, von denen die schwachere wie folgt lautet:∑
i∈J
q (r) i ∀J ⊆ {1, . . . , n} : |J | ≥ α · n
wobei 0 < ε, α < 1 und q (r) i bzw. q′
(r) i die Anzahl der freien Intervalle der Lange 2r in I1
bzw. I2 fur Prozessor Pi sind. Darauf aufbauend prasentieren die Autoren u.a. einen Online- Algorithmus, der einen Superstep bestehend aus m gleich schweren Jobs mit competitive ratio O(log∗(m)) ausfuhrt.
Maria Calzarossa und Giuseppe Serazzi beschrieben in [CS93] Charakteristiken der Aus- lastung fur bestimmte Typen von Systemen, z.B. Recher im Batchbetrieb, Rechner im interaktiven Betrieb, Datenbank-Server oder Parallelrechner. Die in dieser Arbeit betrach- teten Rechner werden jedoch typischerweise universell genutzt und lassen sich daher nicht ohne weiteres einer dieser Klassen zuordnen.
In [Kun91] wird untersucht, wie gut ein gegebenes Lastbalancierungsverfahren arbeitet,
4
wenn es seine Entscheidungen anhand bestimmter Kenngroßen zur Beschreibung der Aus- lastung eines Systems (u.a. die Idle-Zeit, die Anzahl der Prozesse in der Run-Queue und der Load-Average-Wert) trifft. Da es sich dabei jedoch um ein
’ binares‘ Lastbalancierungs-
verfahren handelt (d.h. es gibt kein Maß dafur, wie viel Kapazitat auf einem Rechner noch frei ist, sondern es wird pro Rechner nur zwischen den Zustanden
” unterbelastet“ und
5
In diesem Kapitel werden wichtige Modelle, Konzepte und Projekte vorgestellt, auf die spater noch mehrfach Bezug genommen wird.
2.1 Das BSP-Modell
Um die Entwicklung paralleler Algorithmen zu vereinfachen, entwarf Leslie G. Valiant das Bulk-Synchronous Parallel (BSP)-Modell (s. [Val90]), das eine Verbindung zwischen der zu verwendenden Hardware und der zu entwickelnden Software darstellt; es ermoglicht dem Software-Entwickler eine abstrahierende Sicht auf die technische Struktur und die Kommunikationsmoglichkeiten der einzusetzenden Hardware (z.B. einen Parallelrechner, ein Cluster von Workstations oder eine Menge uber das Internet verbundener PCs).
In diesem Modell besteht ein Computer – von Valiant als BSP-Computer bezeichnet – aus
• einer Menge von Prozessor/Speicher-Paaren, zwischen denen uber einen zugrunde liegenden Kommunikationsmechanismus (z.B. ein Netzwerk oder Shared Memory) Punkt-zu-Punkt-Kommunikation moglich ist (vgl. Abbildung 2.1), und
• einem Mechanismus zur effizienten Barriere-Synchronisation.
Ein BSP-Algorithmus besteht aus einer Reihe von zeitlich durch die Barriere-Synchronisa- tion getrennten Abschnitten, den sog. Supersteps. Innerhalb eines Supersteps fuhrt jeder Prozessor lokale Berechnungen durch und verschickt ggf. Nachrichten an andere Prozes- soren; anschließend signalisiert er durch Aufruf der Synchronisationsfunktion, dass er fur die Barriere-Synchronisation bereit ist. Haben alle Prozessoren die Synchronisationsfunk- tion aufgerufen, wird noch solange gewartet, bis alle Nachrichten an ihrem Ziel angekom- men sind. Dann beginnt der nachste Superstep und erst dann stehen den Prozessoren die wahrend des letzten Supersteps versandten Nachrichten zur Verfugung. Abbildung 2.2 veranschaulicht diesen Vorgang.
7
PID 0 PID 1 PID 2 PID p-2 PID p-1
Kommunikationsmedium
Prozessor 0 ...Prozessor 1 Prozessor 2 Prozessor p-2 Prozessor p-1
ein Superstep
lokale Berechnungen
Nachricht verschicken
8
Prozessor 0 ...Prozessor 1 Prozessor 2 Prozessor p-2 Prozessor p-1
Barriere-Synchronisation
Barriere-Synchronisation
Abbildung 2.3: ’ Ausbremsen‘ eines BSP-Programms
Es existieren verschiedene Bibliotheken zur Entwicklung von Programmen nach dem BSP- Modell, z.B. die BSPlib (s. [HMS+98]), die Paderborn University BSP Library (PUB) (s. [BJvOR03], [pub05b]) oder die Paderborn University BSP-based Web Computing Library (PUBWCL) (s.u.).
2.2 Migration
Komplexe Berechnungen erfordern oft viel Rechenzeit und die Ausfuhrung eines BSP- Programms kann somit relativ lange andauern. Daher ergibt sich in einer Web-Computing- Umgebung folgendes Problem: Mochte der Besitzer des Rechners, auf dem ein BSP-Prozess lauft, seinen Rechner vorubergehend wieder selbst stark beanspruchen, sinkt die Rechen- zeit, die dem BSP-Prozess zur Verfugung steht, stark ab; dadurch wird jedoch nicht nur dieser eine Prozess des BSP-Programms aufgehalten, sondern es wird auch die nachste Syn- chronisation (und somit die Ausfuhrung des gesamten BSP-Programms) hinausgezogert. Abbildung 2.3 veranschaulicht dies.
Um auf Schwankungen der zur Verfugung stehenden Rechenleistung wahrend der Laufzeit
9
KAPITEL 2. GRUNDLAGEN
reagieren zu konnen, ist ein Mechanismus vonnoten, der es erlaubt, einzelne BSP-Prozesse wahrend der Ausfuhrung des BSP-Programms zu migrieren und dabei die Kommunikation der BSP-Prozesse untereinander aufrecht zu erhalten.
2.3 Fehlertoleranz
Durch die aufgrund komplexer Berechnungen oftmals relativ lange Laufzeit eines BSP- Programms steigt die Wahrscheinlichkeit stark an, dass irgendeiner der Rechner, auf dem gerade ein BSP-Prozess ausgefuhrt wird, vor der Vollendung des BSP-Programms absturzt oder das Peer-to-Peer-System verlasst.
Web-Computing-Umgebungen fur BSP-Programme sollten daher unbedingt resistent sein gegen den Ausfall einiger Rechner.
2.4 PUBWCL
Die Paderborn University BSP-based Web Computing Library (PUBWCL) (s. [Geh03], [pub05a]) ist eine Bibliothek zur Entwicklung paralleler Algorithmen nach dem BSP- Modell, konzipiert fur den Einsatz auf uber das Internet verteilten Rechnern. PUBWCL nutzt auf diesen Rechnern jeweils nur die ansonsten ungenutzte Rechenleistung.
Die eingesetzte Programmiersprache ist Java, woraus sich Vorteile in puncto Sicherheit1, Plattformunabhangigkeit und Objekt-Orientierung ergeben.
Als Teilnehmer am System PUBWCL muss man sich wie in den in der Einleitung zitier- ten Projekten einen Client2 herunterladen und installieren. Im Gegensatz zu den ande- ren Projekten, die nur dann eine Internetverbindung benotigen, wenn sie die Ergebnis- se hochladen und sich neue Arbeit zuteilen lassen, setzt PUBWCL wegen der standigen Kommunikation eine permanente Internetverbindung voraus; neben direkten Anschlussen kommen aber auch Einwahlzugange (z.B. DSL-Verbindungen) in Frage, da PUBWCL kurz- fristige Netzwerkfehler (z.B. Unterbrechung der Verbindung durch Neueinwahl) und sogar IP-Adressanderungen toleriert.
Die Architektur von PUBWCL ist hybrid: Die Ausfuhrung der BSP-Programme geschieht auf Peer-to-Peer-Basis, d.h. die mit der Ausfuhrung eines BSP-Programms betrauten Cli- ents wickeln diese Aufgabe eigenstandig unter sich ab. Die organisatorischen Aufgaben (z.B. Zuteilung von Clients an ein BSP-Programm) dagegen geschehen auf Client-Server-Basis. Abbildung 2.4 veranschaulicht dies.
1Die sog. Java Sandbox gesteht anhand einer Sicherheitsrichtlinie Java-Programmen (abhangig von deren Herkunft) nur bestimmte, konfigurierbare Rechte zu; beispielsweise konnen Festplattenzugriffe un- terbunden werden.
2Bei PUBWCL handelt es sich jedoch nicht um einen Bildschirmschoner, sondern um einen Hinter- grundprozess mit niedriger Prioritat.
10
Abbildung 2.4: Die Architektur von PUBWCL
Der Proxy dient zur Anbindung von Clients in Subnetzen mit privaten IP-Adressen oder hinter einer Firewall.
Die in Kapitel 2.2 angesprochenen Migrationen fuhrt PUBWCL fur den BSP-Programmie- rer unsichtbar durch, d.h. die Programmausfuhrung wird nach einer Migration so fortge- setzt, als hatte die Migration gar nicht stattgefunden.
Die technische Unterstutzung fur Migrationen kann in PUBWCL auch zur Realisierung von Mechanismen zur Steigerung der Fehlertoleranz verwendet werden, wie in Kapitel 4.1 dargelegt wird.
2.5 JavaGO
Um die oben angesprochenen Migrationen technisch umzusetzen, gibt es verschiedene Ansatze, von denen JavaGO (s. [SMY99], [jgo05a]) fur PUBWCL der am besten geeig- nete ist (Details hierzu finden sich in [Geh03]).
JavaGO ist eine Erweiterung der Sprache Java um drei Schlusselworter:
• Mit go wird eine Migration durchgefuhrt (gibt man als Migrationsziel eine Datei an, kann man auf diese Weise eine Sicherungskopie des Ausfuhrungszustands anlegen).
• Funktionen, in denen eine Migration stattfinden kann, mussen als migratory dekla- riert werden.
• Mit dem undock-Statement kann die Tiefe, bis zu der der Stack migriert wird, be- grenzt werden.
11
Mithilfe des JavaGO-Compilers jgoc wird diese erweiterte Sprache in Java-Quellcode uber- setzt, der die fur die Migration notigen Modifikationen enthalt. Die Ausfuhrung des kom- pilierten Programms geschieht mithilfe eines Wrappers (javago.Run); zur Fortsetzung der Ausfuhrung ist auf Seiten des Migrationsziels ein Server (javago.BasicServer) erforder- lich.
Da die ursprungliche Implementierung von JavaGO nicht vollstandig kompatibel ist zum Java-Standard RMI (Remote Method Invocation), wird in PUBWCL eine vom Autor dieser Arbeit modifizierte Version, JavaGO RMI (s. [jgo05b]), verwendet, die zwar nicht mehr zur ursprunglichen Version von JavaGO, dafur aber zu RMI vollstandig kompatibel ist.
12
In diesem Kapitel werden zunachst die Rahmenbedingungen dargelegt und die Art der Lastmessung erlautert; abschließend werden die zu vergleichenden Lastbalancierungsalgo- rithmen vorgestellt.
3.1 Rahmenbedingungen
Aus den Eigenschaften des BSP-Modells ergibt sich folgende Vorgabe: Am Ende eines jeden Supersteps werden alle BSP-Prozesse synchronisiert; folglich lasst sich das Scheduling- Problem fur einen BSP-Algorithmus mit n Supersteps auf n unabhangige Teilprobleme, namlich das Scheduling innerhalb eines Supersteps, reduzieren.
Da in einem idealen BSP-Programm in allen Supersteps auf jeden der p BSP-Prozesse ein gleicher Anteil der Arbeit entfallt, erzeugen die BSP-Prozesse pro Superstep jeweils dieselbe Last. Der Scheduler hat also p gleich schwere Aufgaben zu verteilen.
Neben den genannten impliziten Rahmenbedingungen gibt es auch eine einschrankende Anforderung: Aus Grunden des Datenschutzes ist auf keinem Rechner eine Aufschlusselung der CPU-Nutzung verfugbar, d.h. es ist insbesondere unklar, ob bzw. wie viel Idle-Zeit zur Verfugung steht, und wie viel Prozent der Rechenkapazitat den BSP-Prozessen zugeteilt wird.
3.2 Lastmessung
13
Definition 3.1 Ein Rechner sei zu einem bestimmten Teil vom Benutzer ausgelastet. Die verbleibende Idle-Zeit kann dann von Idle-Time-Computing (ITC)-Prozessen (z.B. von BSP-Prozessen) genutzt werden.
Die Rest-Rechenkapazitat ist nun definiert als die Rechenleistung, die einem neuen (d.h. zusatzlich auf dem Rechner gestarteten) ITC-Prozess zugeteilt wurde.
Dieser Wert lasst sich relativ einfach bestimmen, indem man in regelmaßigen Zeitabstanden fur ein kurzes Zeitintervall1 einen Messprozess2 startet, der typische Rechenoperationen in einer Schleife ausfuhrt; die Anzahl der in dem zugeteilten Zeitintervall ausgefuhrten Opera- tionen liefert dabei den Messwert fur die Rest-Rechenkapazitat. Aus diesem Messwert kann man zwar nicht auf die CPU-Nutzung zuruckschließen, dafur ist der Wert aber architek- turunabhangig und daher systemweit (d.h. zwischen allen PUBWCL-Clients) vergleichbar, was fur die Lastbalancierung von großem Vorteil ist.
Die Rest-Rechenkapazitat ist folglich gut geeignet fur die initiale Verteilung der BSP- Prozesse auf PUBWCL-Clients sowie fur die Auswahl von geeigneten Migrationszielen.
Wieso kann man aber aus der Rest-Rechenkapazitat nicht auf die CPU-Nutzung zuruck- schließen? Dazu stelle man zunachst folgende Voruberlegungen an: PUBWCL hat eine niedrige Prozessprioritat, um nur die Rechenleistung zu konsumieren, die der Besitzer des Rechners ubrig hat. Die von PUBWCL gestartenen Subprozesse sind untereinander gleich- berechtigt; das bedeutet insbesondere, dass der Messprozess dieselbe Prioritat hat wie die BSP-Prozesse, woraus folgt, dass auf einem voll ausgelasteten Rechner die vorhande- nen n BSP-Prozesse jeweils 1
n+1 der ihnen zugeteilten Rechenleistung an den Messprozess
abgeben. Die Rest-Rechenkapazitat also kann bei einem voll ausgelasteten Rechner im Extremfall bis zu 50% der Rechenleistung betragen.
Zur Veranschaulichung ein paar Beispiele: Abbildung 3.1 zeigt, welchen Anteil an der Re- chenleistung der Messprozess bekommt, wenn das System Leerlauf hat (Fall a) bzw. wenn bereits ein (Fall b) oder drei (Fall c) BSP-Prozesse die Idle-Zeit konsumieren. t0 stellt dabei einen Zeitpunkt vor dem Starten des Messprozesses und t1 einen Zeitpunkt wahrend der Messung dar.
Die Folgerung, dass jedem BSP-Prozess nun gegenwartig das n+1 n
-fache der Rest-Rechenka- pazitat an Rechenleistung zugeteilt sei, weil die BSP-Prozesse dieselbe Prioritat haben und daher untereinander gleichberechtigt sind, ist ein Trugschluss, denn es ist moglich, dass ge- rade einige BSP-Prozesse blockiert sind (z.B. durch einen blockierenden entfernten Metho- denaufruf) oder sich im Wartezustand befinden (z.B. weil sie zur Barriere-Synchronisation bereit sind, aber noch auf andere BSP-Prozesse warten mussen). In einem solchen Fall verbrauchen sie kaum Rechenleistung, was dazu fuhrt, dass dem Messprozess weit mehr als
1 n+1
1Bei der Implementierung wurde hierfur ein Zeitintervall der Lange von einer Sekunde gewahlt. 2Aus Effizienzgrunden wurde bei der Implementierung dafur ein Thread anstatt eines Prozesses ver-
wendet.
14
t t 10
Abbildung 3.2: Anomalie bei der Messung der Rest-Rechenkapazitat
tuation dar, wo diese Anomalie auftritt. Man kann leicht erkennen, dass alle BSP-Prozesse zusammen weit mehr Rechenleistung verbrauchen wurden als der Prozessor uberhaupt hat, wenn jedem der 7 BSP-Prozesse das 8
7 -fache der Rest-Rechenkapazitat zugeteilt ware.
Zusatzlich gilt es noch zu berucksichtigen, dass die ITC-Prozesse nicht ausschließlich BSP- Prozesse sein mussen, sondern dass auch noch andere unbekannte ITC-Prozesse laufen konnen, die PUBWCL nicht erkennen kann. Es ist folglich also nicht moglich, mithilfe der Rest-Rechenkapazitat festzustellen, wie viel Rechenleistung ein bestimmter BSP-Prozess gegenwartig zugeteilt bekommt. Daher werden die Entscheidungen, ob eine Migration durchgefuhrt werden sollte, in den im Folgenden vorgestellten Lastbalancierungsverfah- ren auf Zeitmessungen beruhen: Anhand der bislang benotigten Rechenzeit lasst sich fur jeden BSP-Prozess feststellen, ob ihm (durchschnittlich) tatsachlich so viel Rechenleistung zur Verfugung gestellt wurde wie angenommen.
15
Algorithmus 3.2 (PON) Sei r ∈ R, r > 1.
Das Lastbalancierungsverfahren ” Parallele Ausfuhrung ohne Neuzuweisung“, PON(r), ar-
beitet wie folgt:
1. Zu Beginn des BSP-Programms werden die BSP-Prozesse auf die im System verfugba- ren Rechner anhand der Rest-Rechenkapazitat derart verteilt, dass jeder BSP-Prozess nach Moglichkeit dieselbe Rechenleistung erhalt.
2. Jeder Rechner fuhrt nebenlaufig den nachsten Superstep der ihm zugewiesenen BSP- Prozesse aus.
3. Der Scheduler wartet solange, bis alle BSP-Prozesse die Rechnungen des aktuellen Supersteps vollendet und die Barriere-Synchronisation durchgefuhrt haben.
4. Von allen Rechnern, auf denen die BSP-Prozesse fur den zuletzt ausgefuhrten Su- perstep mehr Zeit als das r-fache des Durchschnittswertes benotigt haben, wird ein geeigneter Teil der BSP-Prozesse auf andere Rechner migriert, wenn dadurch ein Laufzeitgewinn zu erwarten ist.
5. Falls der zuletzt ausgefuhrte Superstep nicht der letzte war, gehe zu Schritt 2.
Fur den Lastbalancierungsalgorithmus PON(r) zeigt Abbildung 3.3 ein UML-Aktivitats- diagramm fur den Scheduler.
Initiale Verteilung anhand Rest-Rechenkapazität
Nebenläufige Prozess- ausführung starten mit nächstem Superstep
Warten bis alle Prozesse mit Superstep fertig
[letzter Superstep]
Abbildung 3.3: Aktivitatsdiagramm fur PON(r)
3d.h. die Anzahl der BSP-Prozesse ist deutlich großer als die Anzahl der PUBWCL-Clients
16
3.3. DIE LASTBALANCIERUNGSVERFAHREN
Wahrend PON(r) zu langsame Prozesse migriert, nachdem der aktuelle Superstep abge- schlossen ist, bricht folgender Algorithmus zu langsame Prozesse mitten im Superstep ab und startet sie auf einem anderen Rechner neu (es handelt sich dabei nicht mehr um eine Migration, sondern um ein Reset auf den Status zu Beginn des aktuellen Supersteps).
Der Zeitraum vom (Neu-) Starten der (verbliebenen) Prozesse bis zum Abbruch der zu langsamen Prozesse wird als Phase bezeichnet. Dieser Vorgang wird ggf. mehrmals wieder- holt; ein Superstep besteht folglich aus einer oder mehreren Phasen.
Algorithmus 3.3 (PMN) Seien r, s ∈ R, r > 1, 0 < s < 1 und sei p ∈ N die Anzahl der BSP-Prozesse. Weiter bezeichne rnd(x) das Ergebnis der Rundung von x auf eine ganze Zahl.
Das Lastbalancierungsverfahren ” Parallele Ausfuhrung mit Neuzuweisung“, PMN(r, s), ar-
beitet wie folgt:
1. Wie in PON(r) werden zu Beginn des BSP-Programms die BSP-Prozesse auf die im System verfugbaren Rechner anhand der Rest-Rechenkapazitat derart verteilt, dass jeder BSP-Prozess nach Moglichkeit dieselbe Rechenleistung erhalt.
2. Jeder Rechner fuhrt nebenlaufig wie in PON(r) den aktuellen Superstep der ihm zugewiesenen BSP-Prozesse aus.
3. Nachdem in der aktuellen Phase x := max{1, rnd(s · p)} BSP-Prozesse die Rech- nungen des aktuellen Supersteps vollendet haben und zur Barriere-Synchronisation bereit sind, wartet der Scheduler auf alle ubrigen BSP-Prozesse maximal die r-fache Zeitdauer4, die der langsamste unter den ersten x BSP-Prozessen der aktuellen Phase benotigt hat. Diejenigen BSP-Prozesse, die in diesem Zeitrahmen nicht fertig wurden, werden abgebrochen und einem Rechner mit moglichst viel Rest-Rechenkapazitat zu- gewiesen. Eine neue Phase beginnt.
4. Die Schritte 2 und 3 werden solange wiederholt, bis alle BSP-Prozesse die Rechnungen des aktuellen Supersteps vollendet und die Barriere-Synchronisation durchgefuhrt haben.
5. Falls der zuletzt ausgefuhrte Superstep nicht der letzte war, optimiere die Verteilung und gehe zu Schritt 2. Zur Optimierung wird dabei fur jeden beteiligten Rechner der Durchsatz errechnet und anhand dieser Kenngroße werden ggf. BSP-Prozesse derart migriert, dass im nachsten Superstep alle BSP-Prozesse annahernd gleichzeitig fertig werden, falls sich der Durchsatz der Rechner bis dahin nicht andert. Die Anzahl der dazu benotigten Migrationen wird so klein wie moglich gehalten.
Fur den Lastbalancierungsalgorithmus PMN(r, s) zeigt Abbildung 3.4 ein UML-Aktivitats- diagramm fur den Scheduler.
4gemessen ab dem Beginn der Berechnungen
17
Warten, bis x Prozesse der Phase mit Rechnen fertig
[letzter Superstep]
d := Rechendauer von x-schnellstem
Superstepzähler erhöhen
[sonst]
[sonst]
Abbildung 3.4: Aktivitatsdiagramm fur PMN(r, s)
Die beiden Verfahren PON(r) und PMN(r, s) fuhren die einem Rechner zugewiesenen Pro- zesse parallel aus; die im Folgenden vorgestellten Strategien hingegen arbeiten auf einem jeden Rechner jeweils sequentiell, d.h. es werden insgesamt nur noch so viele Prozesse parallel ausgefuhrt, wie es Rechner gibt (die ubrigen Prozesse werden in Warteschlangen verwaltet).
Wie Algorithmus PMN(r, s) arbeitet auch der folgende Algorithmus in Phasen:
Algorithmus 3.4 (SOJ) Seien r, s ∈ R, r > 1, 0 < s < 1 und sei n ∈ N die Anzahl der aktuell beteiligten Clients. Weiter bezeichne rnd(x) das Ergebnis der Rundung von x auf eine ganze Zahl.
Das Lastbalancierungsverfahren ” Sequentielle Ausfuhrung ohne Just-in-Time-Zuweisung“,
SOJ(r, s), arbeitet wie folgt:
1. Wie in PMN(r, s) werden zu Beginn des BSP-Programms die BSP-Prozesse auf die im System verfugbaren Clients anhand der Rest-Rechenkapazitat derart verteilt, dass jeder BSP-Prozess nach Moglichkeit dieselbe Rechenleistung erhalt.
2. Jeder Client fuhrt sequentiell fur jeden der ihm zugewiesenen BSP-Prozesse den ak- tuellen Superstep aus.
3. Nachdem in der aktuellen Phase x := max{1, rnd(s ·n)} Clients fur alle zugewiesenen BSP-Prozesse die Rechnungen des aktuellen Supersteps vollendet haben, wartet der Scheduler auf alle ubrigen Clients maximal die r-fache Zeitdauer5, die der langsamste der ersten x Clients der aktuellen Phase benotigt hat. Diejenigen BSP-Prozesse, die
5gemessen ab dem Beginn der Berechnungen
18
Warten, bis x Clients der Phase mit zugewiese-
nen Prozessen fertig
d := Rechendauer von x-schnellstem
Superstepzähler erhöhen
[sonst]
[sonst]
in diesem Zeitrahmen nicht fertiggestellt wurden (BSP-Prozesse mit angefangener Berechnung und BSP-Prozesse in Warteschlangen), werden abgebrochen und einem Client mit moglichst viel Rest-Rechenkapazitat zugewiesen. Eine neue Phase beginnt.
4. Die Schritte 2 und 3 werden solange wiederholt, bis alle BSP-Prozesse die Rechnungen des aktuellen Supersteps vollendet und die Barriere-Synchronisation durchgefuhrt haben.
5. Falls der zuletzt ausgefuhrte Superstep nicht der letzte war, optimiere die Verteilung und gehe zu Schritt 2. Die Optimierung lauft dabei genauso ab wie in PMN(r, s).
Fur den Lastbalancierungsalgorithmus SOJ(r,s) zeigt Abbildung 3.5 ein UML-Aktivitats- diagramm fur den Scheduler.
Wie SOJ(r, s) plant der vierte Algorithmus zwar fur einen Superstep im Voraus, setzt diese Planung zunachst aber nur fur so viele Prozesse um, wie gleichzeitig bearbeitet wer- den konnen. Wahrend der Ausfuhrung des Supersteps wird der Plan fur die noch nicht zugewiesenen Prozesse ggf. optimiert.
Algorithmus 3.5 (SMJ) Seien r, s ∈ R, r > 1, 0 < s < 1 und sei n ∈ N die Anzahl der aktuell beteiligten Clients. Weiter bezeichne rnd(x) das Ergebnis der Rundung von x auf eine ganze Zahl.
Das Lastbalancierungsverfahren ” Sequentielle Ausfuhrung mit Just-in-Time-Zuweisung“,
SMJ(r, s), arbeitet wie folgt:
1. Wie in SOJ(r, s) werden zu Beginn des BSP-Programms die BSP-Prozesse auf die im
19
System verfugbaren Clients anhand der Rest-Rechenkapazitat derart verteilt, dass jeder BSP-Prozess nach Moglichkeit dieselbe Rechenleistung erhalt.
2. Jeder Client fuhrt sequentiell fur jeden der ihm zugewiesenen BSP-Prozesse den nachsten Superstep aus. Im Gegensatz zu SOJ(r, s) konnen aus der Warteschlange jedoch noch nicht bearbeitete BSP-Prozesse wieder entfernt oder hinzugefugt werden.
3. Fuhre folgendes solange parallel aus, bis alle BSP-Prozesse den aktuellen Superstep vollendet haben:
(a) Sobald ein Client alle ihm zugewiesenen BSP-Prozesse abgearbeitet hat und es auf anderen Clients noch nicht begonnene Prozesse gibt, weist ihm der Sche- duler einen weiteren Prozess zu, den er aus der Warteschlange des am meisten uberlasteten Clients entnimmt.
(b) Sobald kein BSP-Prozess mehr in einer Warteschlange steht, gesteht der Sche- duler jedem noch in Berechnung befindlichen BSP-Prozess maximal das r-fache der fur ihn vorgesehenen Zeitdauer (s.u.) zu. Wird einer dieser BSP-Prozesse in diesem Zeitrahmen nicht fertig, wird er abgebrochen und auf einem Client mit moglichst viel Rest-Rechenkapazitat neu gestartet.
Die fur einen BSP-Prozess vorgesehene Zeitdauer hangt dabei von der Anzahl der dem jeweiligen Client zugewiesenen Prozesse (und damit indirekt von der freien Rechenkapazitat des Clients) ab: Die BSP-Prozesse sind – nach Moglich- keit – stets derart auf die Clients verteilt, dass alle Clients moglichst gleichzeitig mit der ihnen zugewiesenen Arbeit fertig werden; da die freie Rechenkapazitat der Clients Schwankungen unterliegt, kann sich dieser anvisierte gemeinsame Endzeitpunkt zur Laufzeit verschieben. Als Schatzwert wird deshalb der hoch- gerechte Endzeitpunkt des x := max{1, rnd(s·n)}-schnellsten Clients verwendet. Die fur einen BSP-Prozess vorgesehene Zeitdauer ergibt sich dann aus diesem Schatzwert geteilt durch die Anzahl der dem Client zugewiesenen Prozesse.
4. Falls der zuletzt ausgefuhrte Superstep nicht der letzte war, gehe zu Schritt 2.
Fur den Lastbalancierungsalgorithmus SMJ(r, s) zeigt Abbildung 3.6 ein UML-Aktivitats- diagramm fur den Scheduler.
20
Prozess fertig
[letzter Superstep]
Rechenkapazität neu starten
Warten, bis 1 Client mit zugewiesenen Prozessen fertig
1 Prozess aus Warte- schlange des am mei-
sten überlasteten Clients migrieren
anderen Clients]
Abbildung 3.6: Aktivitatsdiagramm fur SMJ(r, s)
21
Grundlegende Informationen zur Architektur und Implementierung von PUBWCL finden sich in [pub05a].
4.1 Restauration von BSP-Prozessen
Sicherungskopien und Restaurationsverfahren erhohen einerseits die Fehlertoleranz fur den Fall, dass der eine oder andere Client wahrend der Berechnungen ausfallt, und ermoglichen andererseits erst Schedulingverfahren, die zu langsame BSP-Prozesse abbrechen und auf einem anderen Client neu starten.
Deshalb wurde PUBWCL folgendermaßen erweitert: Mithilfe der Mechanismen fur die Migration wird in regelmaßigen Abstanden (wie bei einer Migration) ein Abbild der BSP- Prozesse angelegt; dieses Abbild wird jedoch nicht (wie bei einer Migration) an einen anderen Client verschickt, sondern als Sicherungskopie in einer Datei gespeichert, die so- wohl lokal gehalten als auch auf einem anderen Client hinterlegt wird. Wenn der Client nun plotzlich ausfallt oder ein BSP-Prozess vom Scheduler absichtlich beendet wird, kann auf einem Ersatz-Client das Prozess-Abbild aus der Sicherungskopie eingespielt werden, so dass die Berechnungen nicht von vorne beginnen mussen, sondern ab dem letzten Siche- rungspunkt wieder aufgenommen werden konnen.
Die Sicherungskopien werden von PUBWCL jeweils zu Beginn eines Supersteps angelegt, noch ehe die BSP-Prozesse die Kontrolle uber die CPU (zuruck-) erhalten. Hinterlegt wer- den die Sicherungskopien jeweils auf dem Client des BSP-Prozesses mit der nachsthoheren PID (modulo n), der nicht auf demselben Client lauft wie der gesicherte BSP-Prozess.
Die Restauration von BSP-Prozessen wird von den Clients hauptsachlich auf Peer-to-Peer-
23
Abbildung 4.1: Doppelte Restauration bei fehlendem zweiten Check
Basis abgewickelt. Die verbliebenen BSP-Prozesse stellen entweder selbstandig fest, dass ein BSP-Prozess nicht mehr erreichbar ist, oder werden vom Scheduler darauf hingewiesen, wenn er einen BSP-Prozess absichtlich beendet. Wenn ein BSP-Prozess nicht mehr erreich- bar ist, kommen – da davon ausgegangen wird, dass alle BSP-Prozesse gutartig sind – nur folgende Grunde in Betracht:
1. Der BSP-Prozess, der Client oder der gesamte Rechner ist abgesturzt.
2. Der BSP-Prozess wurde vom Scheduler absichtlich beendet.
3. Der Benutzer hat das BSP-Programm absichtlich beendet.
4. Ein Netzwerkfehler hat den Rechner vom Internet abgeschnitten.
In den ersten beiden Fallen muss der betroffene BSP-Prozess offensichtlich neu gestar- tet werden. Im dritten Fall ist es unerheblich, ob eine Restauration begonnen wird oder nicht, da i.d.R. binnen weniger Sekunden alle noch verbliebenen (und evtl. neu gestarteten) BSP-Prozesse beendet werden. Im vierten Fall wird der vom Internet abgeschnittene BSP- Prozess1 feststellen, dass er den Server nicht mehr erreichen kann, und wird sich beenden.
Damit nun genau einer der verbliebenen BSP-Prozesse die Restauration durchfuhrt, ist eine Leader Election erforderlich. Realisiert wurde dies durch Aufruf einer atomaren Funktion des Servers, die die Leader Election nach dem First-Come-First-Serve-Prinzip durchfuhrt, denn ein verteilter Leader-Election-Algorithmus wurde i.d.R. einen deutlich hoheren Kom- munikationsaufwand bedeuten, da je nach Nachrichtenaufkommen des BSP-Programms nur wenige der verbliebenen BSP-Prozesse feststellen, dass ein BSP-Prozess neu gestar- tet werden muss, und die ubrigen BSP-Prozesse somit gar nicht in das Leader-Election- Verfahren involviert werden.
Weil sich die verbliebenen BSP-Prozesse bei dieser Herangehensweise nicht untereinander uber ihr Vorgehen verstandigen, ist es erforderlich, dass jeder BSP-Prozess, der das Leader- Election-Verfahren gewonnen hat, danach uberpruft, ob der tote BSP-Prozess inzwischen moglicherweise schon neu gestartet wurde. Fehlt dieser zweite Test, kann es bei ungunstig verzahnter Ausfuhrung passieren, dass der tote BSP-Prozess von mehreren BSP-Prozessen wiederhergestellt wird, wie Abbildung 4.1 zeigt.
Die Wiederherstellungsprodezur an sich lauft schließlich wie folgt ab:
1Dies gilt auch fur mehrere vom Internet abgeschnittene BSP-Prozesse.
24
4.1. RESTAURATION VON BSP-PROZESSEN
1. Suche lokal eine Sicherungskopie. Im Erfolgsfall fahre mit Schritt 5 fort.
2. Suche eine Sicherungskopie auf dem Client, wo der Prozess zuletzt lief, falls dieser Client noch lebendig ist. Im Erfolgsfall fahre mit Schritt 5 fort.
3. Suche eine Sicherungskopie auf den Clients der ubrigen BSP-Prozesse, wobei die Clients nach demselben System durchsucht werden, nach dem der Client fur die Sicherungskopie ausgewahlt wurde. Im Erfolgsfall fahre mit Schritt 5 fort.
4. Suche eine Sicherungskopie auf Clients, deren BSP-Prozesse kurzlich weggezogen sind.2 Bei Misserfolg wird das BSP-Programm abgebrochen.
5. Fordere vom Server einen Ersatz-Client an und starte den toten BSP-Prozess dort neu. Falls kein Ersatz-Client verfugbar ist, wird das BSP-Programm abgebrochen. Wenn die Wiederherstellung misslingt, wiederhole diesen Schritt.
Wahrend der ersten vier Schritte wird eine Liste mit den schon besuchten Clients gefuhrt, um bei keinem Client doppelt anzufragen.
Da eine Prozess-Restauration nur in bestimmten Prozess-Zustanden erlaubt ist (vgl. Kapi- tel 4.2.2), ist das beschriebene Vorgehen ausreichend. Wurde man Prozess-Restaurationen auch in der Phase des Nachrichtenversands erlauben, ware es erforderlich,
• vor dem Neustarten des toten BSP-Prozesses alle verbliebenen BSP-Prozesse per Broadcast aufzufordern, samtliche bereits vom toten BSP-Prozess empfangene Nach- richten zu verwerfen, und
• nach dem Neustarten des toten BSP-Prozesses alle verbliebenen BSP-Prozesse per Broadcast aufzufordern, die moglicherweise schon an diesen BSP-Prozess vor dem Neustart versandten Nachrichten erneut zu senden.
Die Komplexitat des Problems erhoht sich nochmals, wenn mehrere BSP-Prozesse ausfal- len und von verschiedenen verbliebenen BSP-Prozessen nahezu zeitgleich restauriert wer- den. Weil sich der Nachrichtenverkehr dadurch stark erhohen kann, wurde keine Prozess- Restaurationen in der Phase des Nachrichtenversands vorgesehen. Da aufgrund einer vor- geschalteten Zwischen-Synchronisation (vgl. Kapitel 4.2.2) die Phasen des Nachrichtenver- sands und der Barriere-Synchronisation im Vergleich zu den ubrigen Phasen sehr kurz sind, ist die Wahrscheinlichkeit, dass ein BSP-Prozess in den genannten Phasen absturzt, sehr gering. Tritt dieser Fall aber einmal ein, mussen alle BSP-Prozesse auf den Anfang des Supersteps zuruckgesetzt werden.3
Die entscheidenden Teile der Implementierung der Prozess-Restauration finden sich in die- sen Klassen:
2Beim Server konnen Listen solcher Clients angefordert werden. 3Dieser Vorgang wurde nicht implementiert (das BSP-Programm wird stattdessen abgebrochen), weil
dieses Szenario in der Praxis fast nie auftritt.
25
Allen vier zu untersuchenden Lastbalancierungsverfahren ist gemeinsam, dass sie die in- itiale Verteilung der BSP-Prozesse auf die Clients anhand der Rest-Rechenkapazitat (vgl. Definition 3.1) durchfuhren. Daher wird in den folgenden Abschnitten zunachst diese ge- meinsame Komponente beschrieben, ehe die Implementierung der vier Lastbalancierungs- verfahren erlautert wird.
4.2.1 Durchfuhrung der initialen Verteilung
Da gemaß Voraussetzung (vgl. Kapitel 3.1) ein BSP-Programm aus m ca. gleich schweren Prozessen besteht, sollten die Prozesse derart auf die n verfugbaren Clients verteilt werden, dass jedem Prozess ungefahr dieselbe Rechenkapazitat zur Verfugung steht.
Algorithmus 4.1 (IVT) Seien m, n ∈ N wie oben beschrieben gewahlt. Fur einen Client j, 0 ≤ j < n, bezeichne rj ∈ R+
0 die Rest-Rechenkapazitat. Dann arbeitet der Algorithmus zur initialen Verteilung der BSP-Prozesse, IVT(m, n, r0, . . . , rn−1), wie folgt:
1. Sei π : N 7→ N eine Permutation auf [0; n− 1], die die Clients nach absteigender Rest-Rechenkapazitat sortiert:
∀ j, 0 ≤ j < n− 2 : rπ(j) ≥ rπ(j+1)
2. Sei n′ ∈ N. Setze n′ := min{n, m}.
3. ρ ∈ R+ 0 bezeichne die Rest-Rechenkapazitat, die einem jeden BSP-Prozess nach
Moglichkeit zugeteilt werden soll:
4. Jedem Client π(j), 0 ≤ j < n′, weise b rπ(j)
ρ c BSP-Prozesse zu.
4.2. IMPLEMENTIERUNG DER LASTBALANCIERUNGSVERFAHREN
5. Fur einen Client j bezeichne zj(i) die Anzahl der zugewiesenen BSP-Prozesse nach Ausfuhrung des i-ten Schrittes4. Solange noch nicht alle BSP-Prozesse zugewiesen sind, weise in Schritt k den nachsten unzugewiesenen BSP-Prozess einem Client x zu, fur den gerade gilt:
rπ(x)
zπ(j)(k − 1) + 1 (4.1)
Satz 4.2 Der Algorithmus IVT(m, n, r0, . . . , rn−1) ist optimal.
Beweis: Zunachst kann man sich leicht verdeutlichen, dass es genugt, die n′ (d.h. maximal m) Clients mit den großten Rest-Rechenkapazitaten zu betrachten: Da es nur m BSP- Prozesse gibt und diese nicht gesplittet werden konnen, konnen maximal m Clients genutzt werden.
Weil alle m BSP-Prozesse ca. gleich schwer sind, wurde im Optimalfall jedem BSP-Prozess eine Rest-Rechenkapazitat von ρ zugewiesen; dies ist aber praktisch unmoglich, da dazu jeder Client eine Rest-Rechenkapazitat haben musste, die ein ganzzahlig-Vielfaches von ρ ist.
Der Algorithmus arbeitet nun in zwei Phasen:
1. Zunachst werden jedem Client so viele BSP-Prozesse zugewiesen, wie viele Einheiten der Große ρ vollstandig in seiner Rest-Rechenkapazitat Platz finden5 (vgl. Schritt 4 des Algorithmus).
2. Danach werden die noch nicht zugewiesenen BSP-Prozesse verteilt (vgl. Schritt 5 des Algorithmus). Weshalb das Auswahlkriterium (4.1) dabei zu einer optimalen Verteilung fuhrt, wird im Folgenden erlautert.
In Phase 1 werden BSP-Prozesse auf Clients verteilt mit der Intention, dass jeder BSP- Prozess eine Rechenkapazitat von ρ erhalt. In der Praxis lauft die Verteilung aber so ab, dass alle BSP-Prozesse gleichberechtigt sind, und jeder von ihnen so viel Rechenka- pazitat wie moglich beansprucht; die verfugbare Rest-Rechenkapazitat eines Clients wird also gleichmaßig auf alle ihm zugewiesenen BSP-Prozesse verteilt6.
4Gemeint ist die Anzahl der wahrend der Ausfuhrung des Algorithmus IVT bislang zugewiesenen BSP- Prozesse, nicht die Anzahl der insgesamt (von samtlichen aktiven BSP-Programmen) zugewiesenen BSP- Prozesse
5Dass die Zahl der insgesamt zugewiesenen BSP-Prozesse nicht großer als m werden kann, folgt unmit- telbar aus der Wahl von ρ.
6Falls einem Client mehrere BSP-Prozesse zugewiesen werden, ist die Rechenkapazitat, die den zugewie- senen BSP-Prozessen insgesamt zur Verfugung steht, etwas großer als die Rest-Rechenkapazitat, da vor- handenen BSP-Prozessen anderer BSP-Programme etwas Rechenkapazitat entzogen wird. Da jedoch von stark ausgelasteten Systemen ausgegangen wird, d.h. da die Anzahl der neu zu startenden BSP-Prozesse deutlich kleiner ist als die Anzahl der vorhandenen BSP-Prozesse, ist diese Abweichung vernachlassigbar.
27
x
ri
Abbildung 4.2: Beispiel zu Phase 2 von Algorithmus IVT(m, n, r0, . . . , rn−1)
Dies bedeutet, dass die einem Client zugewiesen BSP-Prozesse eine Rechenkapazitat großer als ρ erhalten, falls dem Client in Phase 2 kein weiterer BSP-Prozess zugeteilt wird. Analog ist die Rechenkapazitat kleiner als ρ, falls weitere BSP-Prozesse zugeteilt werden.
Zur Veranschaulichung zeigt Abbildung 4.2 ein bewußt etwas extrem gewahltes Beispiel, da die Problematik bei einem ausgeglichenen System nicht auftritt: Angenommen, Client 0 habe eine Rest-Rechenkapazitat von r0 = 10 und Client 1 eine von r1 = 1, 25; bei 5 Prozessen ergibt sich ρ = 2, 25. In Phase 1 werden 4 Prozesse Client 0 zugewiesen und in 1 Prozess bleibt ubrig (vgl. Situation a). Wurde man in Phase 2 nun den funften Prozess Client 1 zuteilen, ware die Rest-Rechenkapazitat aller Clients voll ausgeschofpt, wobei 4 Prozesse eine Rechenkapazitat von 2, 5 erhielten und ein Prozess eine Rechenkapazitat von 1, 25 (vgl. Fall b). Wurde man den funften Prozess hingegen ebenfalls Client 0 zuweisen (vgl. Fall c), ergabe sich fur alle Prozesse eine Rechenkapazitat von 2.
Da die Laufzeit eines BSP-Programms von seinem langsamsten Prozess bestimmt wird, ist der Algorithmus IVT(m, n, r0, . . . , rn−1) dann optimal, wenn er die kleinste Rechenkapa- zitat, die einem BSP-Prozess zugeteilt wird, maximiert.
Angenommen, IVT(m,n, r0, . . . , rn−1) ware nicht optimal: dann gabe es einen Client a, dessen zugewiesene BSP-Prozesse mehr Rechenkapazitat erhielten, wenn der letzte dem Client a zugewiesene BSP-Prozess y einem anderen Client zugewiesen worden ware.
Dass dann, wenn der BSP-Prozess y einem anderen Client zugewiesen worden ware, die ubrigen dem Client a zugewiesenen BSP-Prozesse mehr Rechenkapazitat erhielten, ist of- fensichtlich. Damit der BSP-Prozess y auf einem anderen Client b mehr Rechenkapazitat erhielte, musste fur den letzten Schritt, l, gelten:
rb
4.2. IMPLEMENTIERUNG DER LASTBALANCIERUNGSVERFAHREN
Sei k der Schritt, in dem der BSP-Prozess y dem Client a zugewiesen wurde; dann galt vor der Zuweisung aber wegen des Kriteriums (4.1):
rb
rb
za(k) (4.3)
Weil dem Client a danach kein weiterer BSP-Prozess mehr zugewiesen wurde, kann sich der Wert von za bis zum letzten Schritt des Algorithmus nicht mehr verandert haben. Da ferner die Parameter ra und rb konstant sind, und der Wert von zb niemals kleiner werden kann, konnte die Bedingung (4.3) in allen folgenden Schritten des Algorithmus nicht mehr verletzt werden. Dies liefert einen Widerspruch zur aus der Annahme resultierenden Ungleichung (4.2), womit die Behauptung folgt. q.e.d.
Implementiert wurde IVT(m, n, r0, . . . , rn−1) hauptsachlich mithilfe von MySQL-Anwei- sungen auf einer temporaren Tabelle vom Typ HEAP7; Details findet man in Anhang B.3.
4.2.2 Der Lebenszyklus eines BSP-Programms
Startet ein Benutzer ein BSP-Programm, lasst sich der Client des Benutzers vom Server zuerst die initiale Verteilung berechnen (vgl. Kapitel 4.2.1) und startet dann die einzelnen BSP-Prozesse auf den jeweiligen Clients.
Bei der Ausfuhrung eines Supersteps durchlauft die Runtime Environment von PUBWCL fur einen BSP-Prozess der Reihe nach folgende Stadien: Zuerst fordert sie vom Client die CPU an und wartet, bis ihr die CPU zugeteilt wird. Dann wird eine Status-Nachricht an den Server verschickt, damit der Scheduler weiß, dass der zugehorige BSP-Prozess nun mit seinen Berechnungen beginnt. Jetzt wird der Code des aktuellen Supersteps ausgefuhrt.
Sobald der BSP-Prozess mit den Berechnungen fur den aktuellen Superstep fertig ist, erhalt die Runtime Environment durch Aufruf der bsp.sync() Methode die Kontrolle zuruck. Als erstes wird nun eine weitere Status-Nachricht an den Server verschickt, um das Ende der Berechnungen zu melden. Ehe die BSP-Nachrichten des BSP-Prozesses versendet werden und die Barriere-Synchronisation durchgefuhrt wird, wird zunachst mittels einer weiteren Synchronisation darauf gewartet, dass alle BSP-Prozesse die Berechnungsphase abgeschlossen haben. Dies erlaubt eine effizientere und erheblich weniger komplexe Prozess- Restauration (vgl. Kapitel 4.1).
Bevor nach der Barriere-Synchronisation ein neuer Superstep angefangen wird, kann der BSP-Prozess auf einen anderen Client migrieren; jedes BSP-Programm kann außerdem
7d.h. die Tabelle wird nur im RAM angelegt (und nicht auf der Festplatte)
29
Nachrichten verschicken
Barriere- Synchronisation
auch wahrend der Rechenphase weitere Migrationen zulassen.8
Falls die Berechnungen zulange andauern, hat der Scheduler die Moglichkeit, den BSP- Prozess abzubrechen und auf einem anderen Client neu zu starten. Wenn der BSP-Prozess nach Beginn des Supersteps und bevor alle BSP-Prozesse mit ihren Berechnungen fertig sind, absturzt, kann er restauriert und auf einem anderen Client neu gestartet werden; wenn er in einem anderen Zustand absturzt, z.B. wahrend der Barriere-Synchronisation, wird das BSP-Proramm abgebrochen.9
Abbildung 4.3 zeigt den Lebenszyklus eines BSP-Programms als UML-Zustandsdiagramm.
4.2.3 Implementierung von PON
• Jeder BSP-Prozess, der den Prozessor anfordert, erhalt ihn sofort zugeteilt (parallele Ausfuhrung).
• Der Scheduler bricht keinen BSP-Prozess ab, egal wie lange die Berechnung andauert (ohne Neuzuweisungen).
Jedesmal wenn ein BSP-Prozess die Status-Nachricht ” superstep end“ an den Server sendet,
wird der Scheduler aktiv. Sind dann alle BSP-Prozesse fertig, errechnet der Scheduler die
8Migrationen wahrend der Rechenphase finden beim Aufruf von bsp.mayMigrate() statt, falls der Scheduler eine Migration zu diesem Zeitpunkt fur sinnvoll erachtet. Die in dieser Arbeit untersuchten Lastbalancierungsverfahren PON, PMN, SOJ und SMJ lassen jedoch keine Migrationen wahrend der Rechenphase zu, d.h. ein Aufruf von bsp.mayMigrate() bleibt wirkungslos.
9Man konnte in diesem Fall alternativ auch die verbliebenen BSP-Prozesse abbrechen und danach samtliche BSP-Prozesse neu starten, d.h. den Superstep wiederholen.
30
durchschnittlich benotigte Zeit, die die BSP-Prozesse fur die Rechenphase benotigt haben. Fur alle BSP-Prozesse, die mehr als das r-fache dieser Durchschnittsdauer benotigt haben, wird eine Migration vorgesehen.10
Die Migrationsziele werden auf folgende Weise bestimmt: Wie bei der initialen Verteilung (vgl. Kapitel 4.2.1) sind m (ca. gleich schwere) BSP-Prozesse derart auf n verfugbare Clients zu verteilen, dass jedem dieser Prozesse ungefahr dieselbe Rechenkapazitat zur Verfugung steht. Dies geschieht mithilfe von Algorithmus 4.3.11 Der entscheidende Unterschied zum Algorithmus IVT(m,n, r0, . . . , rn−1) ist, dass als Basis nicht die Rest-Rechenkapazitat dient, sondern ein Erfahrungswert, der aus der Ausfuhrungsdauer der BSP-Prozesse auf den einzelnen Clients im am nachsten zuruckliegenden Superstep gewonnen wird; folglich kommen als verfugbare Clients nicht mehr alle Clients in Frage, sondern nur die, auf denen das BSP-Programm gegenwartig lauft.12
Algorithmus 4.3 (MZA) Seien m, n ∈ N wie eben beschrieben gewahlt. Dann arbeitet der Algorithmus zur Auswahl der Migrationsziele, MZA(m, n), wie folgt:
Fur einen Client j, 0 ≤ j < n, bezeichne rj ∈ R+ 0 die Rechenkapazitat, die durch den
Durchsatz des Clients bestimmt ist:
rj := Anzahl BSP-Prozesse auf Client j
Summe der Berechnungsdauer der Proz. auf Client j
wobei nur die BSP-Prozesse des betroffenen BSP-Programms betrachtet werden.
Alle weiteren Schritte verlaufen analog zum Algorithmus IVT (vgl. Algorithmus 4.1, Schritt 1 bis 5).
Wie IVT(m,n, r0, . . . , rn−1) wurde auch MZA(m, n) hauptsachlich mithilfe von MySQL- Anweisungen auf einer temporaren Tabelle vom Typ HEAP implementiert; Details findet man in Anhang B.4.
4.2.4 Implementierung von PMN
Zum Lebenszyklus eines BSP-Programms (vgl. Kapitel 4.2.2) bei Verwendung des Lastba- lancierungsverfahrens PMN ist – wie bei PON – zu bemerken, dass jeder BSP-Prozess, der den Prozessor anfordert, ihn sofort zugeteilt bekommt (parallele Ausfuhrung).
Sei p die Anzahl der Prozesse des BSP-Programms.
10Dies geschieht im letzten Superstep nicht mehr. 11Ursprunglich sollte hierfur ebenfalls den Algorithmus IVT(m,n, r0, . . . , rn−1) genutzt werden, jedoch
erwies sich hierfur der Wert der Rest-Rechenkapazitat in der Praxis als zu ungenau. 12Dies hat zur Konsequenz, dass das Lastbalancierungsverfahren PON nicht fur Umgebungen geeignet
ist, in denen die Menge der Clients erhohter Fluktuation unterliegt. Die anderen Lastbalancierungsverfah- ren werden diese Einschrankung nicht mehr aufweisen.
31
KAPITEL 4. IMPLEMENTIERUNG
Jedesmal wenn ein BSP-Prozess die Status-Nachricht ” superstep end“ an den Server sendet,
uberpruft der Scheduler,
1. ob alle BSP-Prozesse mit dem aktuellen Superstep fertig sind oder
2. ob max{1, rnd(s · p)} BSP-Prozesse in der aktuellen Phase fertig geworden sind.
Im zweiten Fall startet der Scheduler einen Wachter-Prozess, der nach Verstreichen der (r−1)-fachen Zeit, die der max{1, rnd(s·p)}-schnellste BSP-Prozess in der aktuellen Phase benotigt hat, alle unvollendeten Berechnungen abbricht und neu startet; die Auswahl der Clients fur die Neuzuweisungen geschieht dabei mithilfe des Algorithmus IVT (vgl. Kapitel 4.2.1) und die Neuzuweisungen an sich laufen wie in Kapitel 4.1 beschrieben ab. Das Kernstuck des Wachter-Prozesses ist die Klasse de.upb.sfb376.a1.server.ProcessKil- ler.
Im ersten Fall beendet der Scheduler den Wachter-Prozess und optimiert die Verteilung der BSP-Prozesse. Der Optimierungsvorgang wird im folgenden Algorithmus naher beschrie- ben:
Algorithmus 4.4 (OVT) Sei n ∈ N die Anzahl der Clients, die an der Ausfuhrung des BSP-Programms beteiligt sind, und sei p ∈ N weiterhin die Anzahl der Prozesse des BSP-Programms. Dann lauft der Al- gorithmus zur Optimierung der Verteilung der BSP-Prozesse, OVT(n, p), folgendermaßen in zwei Schritten ab:
1. Berechnung des Soll-Zustands
2. Uberfuhrung des Ist-Zustands in den Soll-Zustand mit moglichst wenig Migrationen
Die Berechnung des Soll-Zustands verlauft ahnlich wie die Algorithmen IVT und MZA:
1. Sei a : N 7→ N eine Abbildung von [0; n− 1] auf die Indizes der Clients, die an der Ausfuhrung des BSP-Programms beteiligt sind.
2. Fur einen Client a(j), 0 ≤ j < n, bezeichne ra(j) ∈ R+ 0 die Rechenkapazitat. Dieser
Wert wird wie beim Algorithmus MZA bestimmt, d.h.
ra(j) := Anzahl BSP-Prozesse auf Client a(j)
Summe der Berechnungsdauer der Proz. auf Client a(j)
3. ρ ∈ R+ 0 bezeichne die Rechenkapazitat, die einem jeden BSP-Prozess nach Moglich-
keit zugeteilt werden soll:
4. Jedem Client a(j), 0 ≤ j < n, weise b ra(j)
ρ c BSP-Prozesse zu.
5. Fur einen Client j bezeichne zj(i) die Anzahl der zugewiesenen BSP-Prozesse nach Ausfuhrung des i-ten Schrittes. Solange noch nicht alle BSP-Prozesse zugewiesen sind, weise in Schritt k den nachsten unzugewiesenen BSP-Prozess einem Client a(x) zu, fur den gilt:
ra(x)
za(j)(k − 1) + 1
Der Ist-Zustand wird nun wie folgt in den Soll-Zustand uberfuhrt: Auf jedem Client, auf dem gegenuber dem Soll-Zustand zu viele BSP-Prozesse liegen, wird fur die uberzahli- gen BSP-Prozesse eine Migration vorgesehen.13 Als Migrationsziel wird jeweils ein Client ausgewahlt, fur den noch zu wenige ankommende Migrationen vorgesehen sind.
Satz 4.5 Der von Algorithmus OVT(n, p) berechnete Soll-Zustand ist optimal.
Der Beweis von Satz 4.5 verlauft analog zu dem von Satz 4.2.
Satz 4.6 Die Anzahl der Migrationen, die Algorithmus OVT(n, p) zur Uberfuhrung des Ist-Zustands in den Soll-Zustand benotigt, ist minimal.
Beweis: Die Anzahl der Migrationen ist gleich der Summe der uberzahligen BSP-Prozesse auf den Clients, auf denen gegenuber dem Soll-Zustand zu viele BSP-Prozesse liegen. Wurden weniger Migrationen ausgefuhrt, hatte wenigstens ein Client gegenuber dem Soll- Zustand immer noch zu viele BSP-Prozesse. Folglich ist die Anzahl der Migrationen mini- mal. q.e.d.
Implementiert wurde OVT(n, p) fur PMN hauptsachlich mithilfe von MySQL-Anweisungen auf einer temporaren Tabelle vom Typ HEAP; Details findet man in Anhang B.5.
4.2.5 Implementierung von SOJ
Zum Lebenszyklus eines BSP-Programms (vgl. Kapitel 4.2.2) bei Verwendung des Lastba- lancierungsverfahrens SOJ ist zu bemerken, dass – im Gegesatz zu PON und PMN – nur einer der BSP-Prozesse, die den Prozessor anfordern, ihn sofort zugeteilt bekommt – die ubrigen BSP-Prozesse mussen warten, bis sie an der Reihe sind (sequentielle Ausfuhrung).
Sei n die Anzahl der Clients, die in der jeweils aktuellen Phase mit der Ausfuhrung des BSP-Programms beschaftigt sind.
Jedesmal wenn ein BSP-Prozess die Status-Nachricht ” superstep end“ an den Server sendet,
uberpruft der Scheduler,
13Die Auswahl der BSP-Prozesse, die migriert werden, geschieht dabei zufallig.
33
KAPITEL 4. IMPLEMENTIERUNG
1. ob alle BSP-Prozesse mit dem aktuellen Superstep fertig sind oder
2. ob max{1, rnd(s · n)} Clients mit den in der aktuellen Phase zugewiesenen BSP- Prozessen fertig geworden sind.
Im ersten Fall beendet der Scheduler den Wachter-Prozess, sofern er gestartet wurde, und optimiert die Verteilung des BSP-Prozesse. Der Optimierungsvorgang lauft dabei fast genauso ab wie beim Lastbalancierungsverfahren PMN (vgl. Algorithmus 4.4) und wird daher nicht naher beschrieben.
Im zweiten Fall startet der Scheduler einen Wachter-Prozess, der nach Verstreichen der (r − 1)-fachen Zeit, die der max{1, rnd(s · n)}-schnellste Client fur die in der aktuellen Phase zugewiesenen BSP-Prozesse benotigt hat, alle unvollendeten Berechnungen abbricht und neu startet; die Auswahl der Clients fur die Neuzuweisungen und die Neuzuweisungen an sich laufen dabei genauso ab wie beim Lastbalancierungsverfahren PMN.
Die Implementierung des Schedulers des Lastbalancierungsverfahrens SOJ ist in der Klasse de.upb.sfb376.a1.server.SchedulerSOJ zu finden.
4.2.6 Implementierung von SMJ
Als Besonderheiten beim Lebenszyklus eines BSP-Programms (vgl. Kapitel 4.2.2) bei Ver- wendung des Lastbalancierungsverfahrens SMJ sind zu erwahnen:
• Nur einer der BSP-Prozesse, die den Prozessor anfordern, bekommt ihn sofort zuge- teilt – die ubrigen BSP-Prozesse mussen warten, bis sie an der Reihe sind (sequentielle Ausfuhrung).
• Die Migrationen finden nicht unmittelbar nach Ende eines Supersteps statt, son- dern wahrend der Wartephase auf den Prozessor (d.h. die BSP-Prozesse konnen von der Warteschlange auf einem Client in die Warteschlange auf einem anderen Client umziehen).
Sei n die Anzahl der Clients, die im jeweils aktuellen Superstep mit der Ausfuhrung des BSP-Programms beschaftigt sind.
Jedesmal wenn ein BSP-Prozess die Status-Nachricht ” superstep end“ an den Server sendet,
uberpruft der Scheduler,
1. ob alle BSP-Prozesse mit dem aktuellen Superstep fertig sind oder
2. (a) ob der betroffene Client keine weiteren BSP-Prozesse mehr in der Warteschlange hat und
(b) ob wenigstens max{1, rnd(s · n)} Clients mit mindestens einem zugewiesenen BSP-Prozess fertig sind.
34
4.2. IMPLEMENTIERUNG DER LASTBALANCIERUNGSVERFAHREN
Im ersten Fall wird der Wachter-Prozess beendet, sofern er gestartet wurde. Eine Optimie- rung ist bei diesem Lastbalancierungsverfahren an dieser Stelle nicht mehr erforderlich, da die Warteschlangen wahrend der Ausfuhrung des Supersteps ausgeglichen werden.
Im zweiten Fall wird dem betroffenen Client, falls er alle ihm zugewiesenen BSP-Prozesse abgearbeitet hat, ein weiterer BSP-Prozess zugewiesen, der der Warteschlange des am meisten uberlasteten Clients14 entnommen wird. Falls außerdem ein Mindestanteil der beteiligten Clients mit wenigstens einem zugewiesenen BSP-Prozess fertig ist, wird ein Wachter-Prozess gestartet (falls schon ein Wachter-Prozess lauft, werden nur seine Para- meter aktualisiert). Dieser Wachter-Prozess bricht genau dann alle laufenden BSP-Prozesse ab, wenn keine BSP-Prozesse mehr in Warteschlangen stehen und alle noch laufenden BSP- Prozesse eine bestimmte Hochstdauer uberschritten haben; die Hochstdauer ist dabei das r-fache der durchschnittlichen Bearbeitungsdauer auf dem max{1, rnd(s ·n)}-langsamsten Client. Durch die Verknupfung der beiden Bedingungen im Abbruchkriterium wird erreicht, dass die Prozessausfuhrung auf zu langsamen Clients erst dann abgebrochen wird, wenn schnellere Clients Leerlauf haben; dadurch wird die Anzahl der Neustarts minimiert und die Rechenleistung zu langsamer Clients maximal ausgenutzt.
Die Implementierung des Schedulers und des Wachter-Prozesses des Lastbalancierungsver- fahrens SMJ ist in der Klasse de.upb.sfb376.a1.server.SchedulerSMJ zu finden.
14Der am meisten uberlastete Client ist dabei definiert als derjenige Client, beim dem das Verhaltnis der nicht bearbeiteten BSP-Prozesse zu den zugewiesenen BSP-Prozessen am hochsten ist.
35
In diesem Kapitel wird zunachst ein Modell zur Beschreibung der CPU-Auslastung ent- wickelt; anschließend werden die in Kapitel 3.3 vorgestellten Lastbalancierungsverfahren anhand dieses Modells analysiert.
5.1 Das Modell
Zur Analyse der Lastbalancierungsalgorithmen ist ein Modell erforderlich, das einerseits fur die Analyse hinreichend prazise ist und andererseits flexibel genug fur die in der Realitat typischerweise auftretenden Lastschwankungen.
Im Modell wird dabei von folgender Beobachtung ausgegangen: Viele PC-Nutzer fuhren an ihren Rechnern oft keine Tatigkeit aus (z.B. nachts oder in der Mittagspause) oder gleichformige Tatigkeiten (z.B. Textverarbeitung, Programmieren, etc.), wobei diese Tatig- keiten ein regelmaßiges Muster aufweisen (z.B. Editieren, Kompilieren, Testen) oder sogar an sich gleichformig sind (z.B. Tippen). Daher weist die CPU-Auslastung eines Rechners typischerweise fur eine bestimmte Zeitdauer ein relativ regelmaßiges Muster auf, andert sich dann meist abrupt (wenn der PC-Nutzer eine andere Tatigkeit beginnt) und weist wieder eine Zeit lang ein ziemlich gleichformiges Muster auf usw. Dies wird sich spater noch in zahlreichen Messungen zeigen.
Eine gegebene CPU-Auslastungskurve (z.B. von der Lange einer Woche), wird im Modell deshalb in Blocke unterteilt, in denen die CPU-Auslastung einigermaßen gleichbleibend ist oder ein regelmaßiges Muster aufzeigt; solche Blocke sind typischerweise einige Stunden lang, jedoch treten auch Langen von einer halben Stunde (z.B. Mittagspause) bis hin zu ein paar Tagen (z.B. langes Wochenende) auf. Diese Blocke werden im Folgenden mit Lastsequenz bezeichnet.
Die CPU-Auslastung in einer Lastsequenz wird dabei durch ein relativ enges Intervall um einen mittleren Lastwert und ein Maß fur die
’ Ausreißer‘ (d.h. Spitzen in der CPU-
37
Abbildung 5.1: Beispielhafte Anwendung des Modells auf eine CPU-Auslastungskurve
Auslastung, die außerhalb des engen Intervalls liegen) beschrieben. Zur Veranschaulichung betrachte man Abbildung 5.1; die Ausreißer nach oben (unten) sind rot (grun) hinterlegt.
Um die Haufigkeit und Dauer der Ausreißer zu beschreiben, wird eine Lastsequenz in eine Folge vieler kurzer, gleichartiger Unterabschnitte, im Folgenden Lastperioden genannt, unterteilt. Die Lange dieser Lastperioden ist pro Lastsequenz einheitlich und betragt z.B. funf Minuten. Der in Abbildung 5.1 gezeigte Ausschnitt einer Lastsequenz dauert drei Lastperioden.
Die Ausreißerquote ist der Anteil der Ausreißer bezogen auf eine Lastperiode, wobei der Wert eine obere Schranke fur jeden beliebigen Startzeitpunkt einer Lastperiode innerhalb der Lastsequenz sein muss. Fur die Lastkurve aus Abbildung 5.1 ist in Abbildung 5.2 eine Wahl des Startzeitpunkts zu sehen, die ungunstig ist im Sinne, dass die Ausreißerquote im dem gezeigten Ausschnitt maximal wird.
Es folgt nun eine formale Beschreibung des Modells:
Definition 5.1 Fur einen Rechner i ∈ N0 ist seine CPU-Auslastung zum Zeitpunkt t definiert durch:
`i(t) : R+ 0 7→ [ 0; 1 ]
Definition 5.2 Fur einen Rechner i ∈ N0 seien λi, αi, β
+ i , β−i ∈ R gewahlt mit:
• 0 ≤ λi < 1 (die Intervallmitte)
• 0 ≤ λi − αi und λi + αi < 1 (der Intervallradius)
• 0 ≤ β+ i , β−i < 1
2 (die Ausreißerquoten)
5.2. EINGRENZUNG DER SCHWANKUNGEN
Weiterhin seien Ti ∈ R+, Ii eine Zeitspanne der Lange Ti sowie Ii,j, I + i,k, I
− i,k ⊆ Ii disjunkte
Zeitintervalle mit: j
und ∀t ∈ Ii,j : |λi − `i(t)| ≤ αi
∀t ∈ I+ i,k : λi − `i(t) < −αi
∀t ∈ I−i,l : λi − `i(t) > αi
Wenn die Variablen λi, αi, β + i , β−i derart gewahlt sind, dass∑
k
I−i,l ≤ β−i · Ti (5.1)
gilt, dann ist die Zeitspanne Ii auf dem Rechner i eine (i, λi, αi, β + i , β−i , Ti)-Lastperiode.
Zur Veranschaulichung betrachte man nochmals Abbildung 5.1, in der eine Sequenz von drei Lastperioden dargestellt ist. Die rot hinterlegten Zeitintervalle einer Lastperiode ent- sprechen dabei den Zeitintervallen I+
i,j, die grun hinterlegten den Zeitintervallen I−i,j und die nicht hinterlegten den Zeitintervallen Ii,j aus Definition 5.2. Bedingung (5.1) besagt, dass die rot hinterlegten Zeitintervalle pro Lastperiode zusammengenommen maximal einen Faktor β+
i und die grun hinterlegten maximal einen Faktor β−i der Dauer der Lastperiode ausmachen.
Bei der Einteilung einer gegebenen CPU-Auslastungskurve in Lastperioden wird man die Parameter αi, β
+ i , β−i einerseits moglichst klein halten, andererseits aber nicht zu eng
wahlen, um eine moglichst lange Folge gleicher Lastperioden zu erhalten.
Definition 5.3 Seien i, λi, αi, β
+ i , β−i , Ti wie in Definition 5.2 gewahlt; weiter seien t0, t1 ∈ R+
0 mit t0 < t1.
Dann ist auf dem Zeitintervall [ t0; t1) eine (i, λi, αi, β + i , β−i , Ti, t0, t1)-Lastsequenz auf einem
Rechner i definiert als eine Folge von b t1−t0 Ti c (i, λi, αi, β
+ i , β−i , Ti)-Lastperioden.
Die Parameter αi, β + i , β−i mussen dabei so gewahlt sein, dass fur einen beliebigen Zeitpunkt
t ∈ [ t0; t1 − Ti ) als Startzeitpunkt einer Lastperiode Definition 5.2 erfullt ist.
In dem Beispiel aus Abbildung 5.1 mussen β+ i und β−i also fur die ungunstigste (s.o.) Wahl
von t0 ausreichend groß gewahlt werden. Abbildung 5.2 zeigt einen solchen Fall.
5.2 Eingrenzung der Schwankungen
Angenommen, einem Rechner wurde ein BSP-Prozess zugewiesen, dann stellt sich die Fra- ge, wie viel Zeit der Rechner zur Ausfuhrung eines Supersteps im besten bzw. schlechtesten Fall benotigt.
39
+t 0t 0 Ti Ti
Abbildung 5.2: Ungunstige Wahl von t0 fur das Beispiel aus Abbildung 5.1
Dazu benotigt man folgende Definition:
Definition 5.4 Die Normdauer eines Supersteps, Di,j ∈ R+, ist definiert als die Dauer, die die Ausfuhrung des Supersteps j auf dem Rechner i erfordert in dem Fall, dass der Rechner 100% seiner Rechenleistung zur Verfugung stellen wurde.
Die Ausfuhrungsdauer eines Supersteps, di,j(t) : R+ 0 7→ R+, ist die tatsachlich zur Aus-
fuhrung des Supersteps j auf dem Rechner i benotigte Zeit, wenn die Ausfuhrung des Supersteps zum Zeitpunkt t ∈ R+
0 beginnt.
Es ist davon auszugehen, dass nur einige Male pro Tag eine neue Lastsequenz beginnt, was bedeutet, dass die Lastsequenzen typischerweise relativ lang sind im Vergleich zur Dauer eines Supersteps.
Die Dauer der Lastperioden dagegen sei relativ kurz gewahlt1 im Vergleich zur Dauer eines Supersteps, d.h. Ti Di,j.
Unter diesen Voraussetzungen konnen nun zwei Falle auftreten:
1. Die Ausfuhrung eines Supersteps geschieht innerhalb einer Lastsequenz. Dieser Fall wird im Folgenden genauer untersucht.
2. Eine neue Lastsequenz beginnt wahrend der Ausfuhrung eines Supersteps. Da sich die Parameter der neuen Lastsequenz von denen der alten vollig unterscheiden konnen, ist fur diesen Fall keine Aussage uber die tatsachlich benotigte Zeit di,j(t) moglich: Di,j ≤ di,j(t) ≤ ∞
1Im Gegensatz zur Dauer der Lastsequenzen, auf die man keinen Einfluss hat, kann man die Dauer der Lastperioden geeignet wahlen.
40
Fur Fall 1 kann man folgendes zeigen:
Lemma 5.5 Seien Di,j und di,j(t) wie oben definiert. Dann gilt fur die Ausfuhrung des Supersteps j auf dem Rechner i innerhalb einer (i, λi, αi, β
+ i , β−i , Ti, t0, t1)-Lastsequenz:
Di,j
Di,j
mit:
i Ti
wobei der Parameter Ti der Lastsequenz derart zu wahlen ist, dass Ti Di,j.
Beweis: Die minimale bzw. maximale Ausfuhrungsdauer wird offensichtlich von den durch die (i, λi, αi, β
+ i , β−i , Ti)-Lastperioden gegebenen Grenzen bestimmt. In Abbildung 5.3 sind
fur λi = 1 2 , αi = 1
12 , β+
und β−i = 1 12
die obere Grenze in rot und die untere in grun eingezeichnet.
Ware die CPU-Auslastung stets mit der oberen Grenze identisch, ergabe sich im Mittel eine Auslastung von:
`max,i := β+ i · 1 + (1− β+
i )(λi + αi) (5.3)
`min,i := β−i · 0 + (1− β−i )(λi − αi) (5.4)
Teilt man nun die Normdauer Di,j durch die Rechenleistung, die bei minimal bzw. maximal moglicher CPU-Auslastung in der Lastseqzenz verfugbar ist, erhalt man Ungleichung (5.2).
41
a)
0
1
t
b)
+ε2
Abbildung 5.4: Speziallfall: letzte Lastperiode (obere Schranke)
Zu zeigen bleiben noch die Abschatzungen fur die Korrekturwerte ε1 und ε2, die deshalb erforderlich sind, weil die Ausfuhrungsdauer di,j(t) kein ganzzahlig-Vielfaches von Ti sein muss.
Weil eine Lastperiode innerhalb einer Lastsequenz zu einem beliebigen Zeitpunkt beginnen darf (vgl. Definition 5.3), kann man annehmen, dass der Startzeitpunkt der Ausfuhrung des Supersteps mit dem Beginn einer Lastperiode zusammenfallt. Dies bedeutet, dass man nur am Ende der Ausfuhrung des Supersteps
’ Verschnitt‘ hat, d.h. eine zu einem Bruchteil
x ∈ R, 0 < x < 1, angebrochene Lastperiode.
Ohne die Korrekturwerte ε1 und ε2 wurde das bedeuten, dass auf diesen angebrochenen Teil der Lastperiode maximal ein Anteil von x der insgesamt β+
i Ti (β−i Ti) langen Abweichungen der CPU-Auslastungskurve nach oben (unten) entfiele. Dies kann aber nicht garantiert werden. Daher sind die Korrekturwerte ε1 und ε2 so zu wahlen, dass im Fall der oberen (unteren) Schranke die gesamte Abweichung nach oben (unten) auf den angebrochenen Teil entfallen kann.
Abbildung 5.4 zeigt den Einfluss, den die β+ i Ti langen Abweichungen der CPU-Ausla-
stungskurve nach oben haben konnen (grau dargestellt ist die Rechenkapazitat, die der BSP-Prozess nutzen kann): In Fall b) verlangert sich die Ausfuhrungsdauer um ε2 = β+
i Ti
gegenuber Fall a)2.
Der Einfluss, den die β−i Ti langen Abweichungen der CPU-Auslastungskurve nach unten haben konnen, ist nicht ganz so einfach zu berechnen. Man betrachte dazu Abbildung 5.5: Die hell- bzw. dunkelgrau hinterlegte Flache stellt die Rechenkapazitat dar, die der BSP-Prozess nutzen kann. Das dunkelgraue Rechteck in Fall a) ist in Fall b) abgeschnitten und durch ein flachengleiches in der Abweichung der CPU-Auslastungskurve nach unten
2Die Abschatzung fur ε2 ist dabei etwas zu grob, da ein Bruchteil von x der β+ i Ti langen Abweichungen
der CPU-Auslastungskurve nach oben in der ursprunglichen Ausfuhrungsdauer schon eingerechnet ist.
42
a)
0
1
t
b)
-ε1
Abbildung 5.5: Speziallfall: letzte Lastperiode (untere Schranke)
ersetzt worden3. Dadurch verkurzt sich in Fall b) die Ausfuhrungsdauer um die Breite des dunkengrauen Rechtecks aus Fall a), die sich aus der Flache des dunkelgrauen Rechtecks aus Fall b) geteilt durch die Hohe des dunkelgrauen Rechtecks aus Fall a) ergibt, d.h. ε1 = β−i Ti
λi−αi
1−(λi−αi) .
Folglich erhalt man mit Ungleichung (5.2) eine untere und eine obere Schranke, womit das Lemma folgt. q.e.d.
Nun stellt sich die Frage, welche Werte fur die Parameter λi, αi, β + i , β−i der Lastsequenz
moglich sind, damit minimale und maximale Ausfuhrungsdauer nur um einen Faktor q ∈ R+, q > 1, auseinander liegen.
Satz 5.6 Wenn ein Superstep mit Normdauer Di,j komplett innerhalb einer (i, λi, αi, β
+ i , β−i , Ti, t0, t1)-
Lastsequenz ausgefuhrt wird, dann liegen die minimale und maximale Ausfuhrungsdauer des Supersteps um maximal einen Faktor q ∈ R+, q > 1, auseinander, falls Ti derart gewahlt ist, dass Ti Di,j, und falls fur die Parameter λi, αi, β
+ i , β−i gilt:
(q (β+ i − 1)− β−i + 1) λi + (q (β+
i − 1) + β−i − 1) αi + q (1− β+ i ) ≤ 1 (5.5)
3Die Abschatzung ist auch in diesem Fall etwas etwas zu grob, da ein Bruchteil von x der β−i Ti
langen Abweichungen der CPU-Auslastungskurve nach unten in der ursprunglichen Ausfuhrungsdauer schon eingerechnet ist.
43
Beweis: Ausgehend von Ungleichung (5.2) aus Lemma 5.5 erhalt man:
Di,j
Di,j
⇒ Di,j
1− (1− β−i )(λi − αi)
⇒ 1− (1− β−i )(λi − αi) ≤ q (1− (β+ i + (1− β+
i )(λi + αi)))
i )(λi + αi))) + (1− β−i )(λi − αi) ≤ 1
⇒ q − qβ+ i − qλi − qαi + qβ+
i λi + qβ+ i αi + λi − αi − β−i λi + β−i αi ≤ 1
⇒ (q (β+ i − 1)− β−i + 1) λi + (q (β+
i − 1) + β−i − 1) αi + q (1− β+ i ) ≤ 1
q.e.d.
Ungleichung (5.5) aus Satz 5.6 beschreibt nun eine Teilmenge des funfdimensionalen Raums. Ihr Rand ist bestimmt durch die zugehorige Gleichung:
(q (β+ i − 1)− β−i + 1) λi + (q (β+
i − 1) + β−i − 1) αi + q (1− β+ i ) = 1 (5.6)
Zur geometrischen Interpretation wird der Parameter q festgehalten und den Parameter β−i schrittweise verandert, um eine dreidimensionale Darstellung zu ermoglichen.
Dabei sind zusatzlich die Einschrankungen an die Parameter (vgl. Definition 5.2 bzw. Satz 5.6) zu berucksichtigen:
• 0 ≤ λi < 1
• 0 ≤ β+ i , β−i < 1
2
(q (β+ i − 1)− β−i + 1) λi + (q (β+
i − 1) + β−i − 1) αi + q (1− β+ i ) = 1
⇒ αi = 1− (q (β+
i − 1)− β−i + 1) λi − q (1− β+ i )
q (β+ i − 1) + β−i − 1
Eine Division durch null kann dabei nicht auftreten aufgrund der genannten Einschrankun- gen an die Parameter:
∀ q, β+ i , β−i : q (β+
i − 1) <0
Abbildung 5.6: Plot fur q = 2, β−i = 0
Abbildung 5.6 zeigt den Plot fur q = 2 und β−i = 0. Die Plots fur q = 2 und in 0,1-er Schritten von 0 auf 0,5 erhohtes β−i sind in Abbildung 5.7 und die Plots fur q = 1,5 bzw. q = 2 bzw. q = 3 und β−i = 0 in Abbildung 5.8 zu sehen. Um die Plots aus verschiedenen Perspektiven betrachten zu konnen, moge sich der Leser die Plots selber erzeugen; die noti- gen Befehle fur MuPAD (oder alternativ auch fur Maple) findet man auf der beiliegenden CD.
Beispiel 5.7 Angenommen, ein Benutzer fuhrt wahrend seiner Login Session folgendes durch:
• Verfassen eines Aufsatzes o.a.
• Lesen / Schreiben von e-Mails
• Recherchieren im Internet
Dann erfordern die von ihm benutzten Anwendungen i.d.R. die meiste Zeit uber nur eine geringe Rechenleistung, und nur gelegentlich wird z.B. durch das Starten von Anwendungen oder durch Multimedia-Objekte kurzzeitig erhohte oder volle Rechenleistung benotigt.
45
λi
Abbildung 5.7: Plot fur q = 2, β−i = [0,0; 0,1; 0,2; . . . ; 0,5]
Liegt die Rechenleistung beispielsweise hauptsachlich unter 20% und pro funf Minuten fur nur maximal eine Minute daruber, dann lasst sich der Lastverlauf wahrend der Login Session durch eine Lastsequenz mit λi = 10%, αi = 10%, β+
i = 20%, β−i = 0% und Ti = 300s beschreiben; die zugehorige Koordinate (0,1; 0,2; 0,1) liegt unterhalb der Flache fur q = 2 aus Abbildung 5.6; zwischen der minimal und maximal verfugbaren Rechenkapazitat wahrend der Login Session liegt also ein Faktor von weniger als 2.
Lost man Gleichung 5.5 nach q auf, erhalt man:
1− (1− β−i )(λi − αi)
1− (β+ i + (1− β+
i )(λi + αi)) ≤ q (5.7)
Eine Division durch null kann dabei nicht auftreten aufgrund der Einschrankungen an die Parameter.
Dies fuhrt zu folgender Definition:
Definition 5.8 Eine (i, λi, αi, β
+ i , β−i , Ti, t0, t1)-Lastsequenz heißt q-beschrankt, falls sie die Gleichung 5.7
erfullt.
46
λi
Abbildung 5.8: Plot fur q = [1,5; 2,0; 3,0], β−i = 0
Beispiel 5.9 Die Lastsequenz aus Beispiel 5.7 ist wegen 1−(1−0)(0,1−0,1)
1−(0,2+(1−0,2)(0,1+0,1)) = 1,5625 also z.B. 1,6-
beschrankt.
5.3 Lastmessungen
In diesem Abschnitt geht es darum zu untersuchen, wie sich die Lastkurven in der Realitat verhalten und welche Werte fur die Parameter im Modell gewahlt werden mussen.
Dazu wurden an drei verschiedenen Hochschulen in insgesamt vier verschiedenen Rechner- netzen uber einen Zeitraum von 21 bzw. 28 Tagen (beginnend an einem Freitag um 00:00 Uhr) alle 30 Sekunden die Auslastung der CPU gemessen.
Die Taktfrequenz der insgesamt uber 100 untersuchten Rechner reichte von 233 MHz bis hin zu 2,8 GHz. Neben wenigen Mehr-Prozessor-Maschinen handelte es sich hauptsachlich um Ein-Prozessor-Maschinen. Als Betriebsysteme kamen Debian Linux, RedHat Enterprise Linux und SuSE Linux zum Einsatz.
47
KAPITEL 5. ANALYSE
Die Lastmessungen erfolgten durch ein Perlskript (vgl. Listing B.1 in Anhang B.1), welches aus den Werten aus /proc/stat die (gemittelte) CPU-Nutzung der letzten 30 Sekunden errechnet, diesen Wert an eine Datei anhangt und dann 30 Sekunden schlaft usw.
Samtliche Rohdaten (uber 2300 Dateien mit insgesamt uber 6,8 Mio. Messwerten) sowie deren Aufbereitung und Auswertung in uber 400 Diagrammen befinden sich auf der bei- liegenden CD.
Da aufgrund der riesigen Datenflut eine Bearbeitung per Hand ausscheidet, wurden die Lastkurven mit einem Perlskript (auf der beiliegenden CD enthalten) geeignet in Lastse- quenzen zerlegt. Das Ziel bei der Wahl der Parameter ist dabei nicht nur, Lastsequenzen mit moglichst geringer q-Beschranktheit und moglichst langer Dauer zu erhalten, sondern auch, den Anteil nicht nutzbarer Intervalle moglichst gering zu halten.
Offensichtlich hangen diese drei Kenngroßen von einander ab: wenn man eine sehr niedrige q-Beschranktheit und gleichzeitig eine lange Dauer fordert, steigt die Ausschussquote stark an. Es handelt sich also um ein nicht-triviales Optimierungsproblem, fur das Perlskript nur eine Naherungslosung liefert.
Bemerkung 5.10 Um das Optimum zu finden, brauchte man eine Aufschlusselung der CPU-Auslastung, die so fein ist wie die kleinste Schwankung; aber bereits bei einer Auflosung im Sekundenbereich wurde die Last fur das Messen der Last die Ergebnisse stark verfalschen.
Das folgende Beispiel illustriert, welchen Einfluss das Abgreifen gemittelter Lastwerte im 30-Sekunden-Rhythmus haben kann.
Beispiel 5.11 Angenommen, ein Benutzer surft im Internet und verursacht dadurch hauptsachlich eine CPU-Last zwischen 0% und 2% (die Werte seien gleichmaßig zwischen 0% und 2% verteilt). Gelegentlich verursachen aufwendig gestaltete Webseiten kurzzeitig Vollast; angenommen, dies passiert dreimal in einer Lastperiode von 5 Minuten Dauer, dauert jeweils 2 Sekunden und dazwischen liegen jeweils mindestens 30 Sekunden.
Dann betragt die tatsachliche durchschnittliche Last:
294s0,02−0 2
≈ 0,03
Man wahlt also λi = αi = 1%, β+ i = 2% und β−i = 0%. Damit ist die Lastperiode
q-beschrankt fur:
1− (0,02 + (1− 0,02)(0,01 + 0,01)) ≈ 1, 04
Man kennt nun aber nicht die tatsachliche Last, sondern hat nur 10 Messwerte vorliegen, die jeweils die gemittelte Last eines 30-Sekunden-Intervalls darstellen. Da drei der 10 In- tervalle je eine 2-Sekunde-Spitze enthalten, hat man 7 Messwerte von 0,02−0
2 = 0,01 und
2 + 2s · 1
30s = 0,076
Man kann nun beispielsweise β+ i = 30%, β−i = 0% und λi = αi = 1% wahlen, woraus sich
folgende q-Beschranktheit ergibt:
1− (0,3 + (1− 0,3)(0,01 + 0,01)) ≈ 1, 46
Oder man kann β+ i = 0%, β−i = 0% und λi = αi = 3, 8% wahlen, woraus sich diese
q-Beschranktheit ergibt:
1− (0 + (1− 0)(0,038 + 0,038)) ≈ 1, 08
Das Perlskript zur Zerlegung einer Lastkurve in Lastsequenzen arbeitet nun wie folgt: Zu gegebenem β+
i , β−i und Ti sowie einer Obergrenze fur αi zerlegt es eine gegebene Lastkurve derart in Lastsequenzen, dass diese moglichst lang sind und nebenbei αi pro Lastsequenz moglichst klein bleibt. Intervalle, in denen die CPU fast vollstandig ausgelastet ist (z.B. uber 90%) oder die kurzer als eine bestimmte Mindestdauer (z.B. 30 min.) sind, sind von keinem Nutzen und werden daher nicht als Lastsequenzen ausgegeben.
Fur Ti wurden funf Minuten gewahlt, da einerseits bei einer zu kurzen Dauer ein zu großer Wert fur β+
i bzw. β−i folgt, und andererseits die Dauer deutlich kurzer als die einer Berech- nungsphase sein muss (vgl. Kapitel 5.2). Fur β+
i bzw. β−i sowie als Obergrenze fur αi muss man die am besten geeigneten Werte durch systematisches Variieren der moglichen Werte ermitteln (da pro 5 Minuten nur 10 Messwerte vorliegen, sind fur β+
i bzw. β−i nur Werte in 10%-Schritten eine sinnvolle Wahl, was die Zahl der infrage kommenden Kombinationen deutlich verkleinert). Als Obergrenze fur αi wurde in einigen Fallen auch eine Funktion in λi verwendet.
Nebenher sammelt das Perlskript außerdem noch statistische Daten wie z.B. die Ausschuss- quote, die durchschnittliche Dauer einer Lastsequenz usw.
Es folgen nun ausgewahlte Messergebnisse aus den vier Rechnernetzen, im Folgenden als
” Netz A“ bis
” Netz D“ bezeichnet.
5.3.1 Ergebnisse aus Netz A
Beim Betrachten von Abbildung 5.9, in der jeder Messpunkt der (gemittelten) CPU- Nutzung in einem 30-Sekunden-Intervall entspricht, fallt sofort auf, dass die CPU-Last nachts (von 20:00 Uhr bis 08:00 Uhr) praktisch durchgehend bei ca. 100% liegt; an eini- gen Tagen betragt die CPU-Last auch tagsuber ca. 100%, an den ubrigen Tagen liegt sie tagsuber hauptsachlich bei knapp uber 0% mit vielen Streuungen von teilweise bis uber
49
Uhrzeit
Tag 01 Tag 02 Tag 03 Tag 04 Tag 05 Tag 06 Tag 07 Tag 08 Tag 09 Tag 10 Tag 11 Tag 12 Tag 13 Tag 14 Tag 15 Tag 16 Tag 17 Tag 18 Tag 19 Tag 20 Tag 21
Abbildung 5.9: Auslastung von host07 aus Netz A (24h-Ansicht)
40%, wobei die Werte dabei tatsachlich hauptsachlich bei ca. 0% konzentriert sind und die Wertedichte nach oben schnell abnimmt (vgl. Abbildung 5.12).
Reiht man die Messergebnisse der 21 Tage hintereinander auf (vgl. Abbildung 5.10), er- kennt man folgende Regelmaßigkeit: Diejenigen Tage, an denen die CPU-Last tagsuber hauptsachlich bei knapp uber 0% mit vielen Streuungen von teilweise bis uber 40% liegt, sind Werktage. An Wochenenden betragt die CPU-Last auch tagsuber ca. 100%. Die grun gestrichelte Kurve beschreibt eine Glattung, die man erhalt, indem man ein zehn Messwerte breites Fenster uber die Daten schiebt und an jeder Stelle jeweils den Mittelwert bildet.
Da fast alle Rechner aus Netz A ein derartiges Muster aufweisen4, liegt die Vermutung nahe, dass rechenintensive Aufgaben in diesem Rechnernetz nachts und am Wochenende skriptgesteuert durchgefuhrt werden.5 Die interaktiv genutzten Anwendungen verursachen erwartungsgemaß nur eine geringe CPU-Last mit vereinzelten Spitzen; einige wenige Male pro Tag treten jedoch starke Ausreißer oder langer anhaltende Veranderungen auf.
Die Zerlegung der gegebenen Lastkurven in Lastsequenzen wurde mit dem eingangs be- schriebenen Perlskript durchgefuhrt. Dabei wurden β+
i = 20%, β−i = 10% sowie 15% als Obergrenze fur αi verwendet. Die errechneten Lastsequenzen sind in Abbildung 5.11 zu
4Die Diagramme von samtlichen Messungen befinden sich auf der beiliegenden CD. 5Stichprobenartige Nachforschungen bestatigen diese Vermutung.
50
A us
la st
un g
Abbildung 5.10: Auslastung von host07 aus Netz A (aneinandergereihte Ansicht)
sehen: Jedes (rot-grune) Saulenpaar6 entspricht dabei einer Lastsequenz; die Breite der Saulen gibt die Dauer der Lastsequenz an. Die Hohe der roten Saulen entspricht λi + αi
und die der grunen Saulen λi − αi. Fur die Mehrzahl der Lastsequenzen betragen λi und αi also weniger als 15%.
Dass alle 53 untersuchten Rechner aus Netz A eine sehr ahnliche Verteilung der Ausla- stungswerte haben, und dass insbesondere die Auslastung mit hoher Wahrscheinlich ent- weder nahe 0% oder nahe 100% liegt, ist aus Abbildung 5.12 (logarithmische Skala!) er- sichtlich.
Das Verhaltnis der Lange der ausgegebenen Lastsequenzen zu der der nicht nutzbaren Zeitintervalle betragt auf den meisten der 53 Rechner ca. 2:1 (vgl. Abbildung 5.13). Zu den nicht nutzbaren Zeitintervallen zahlen dabei diejenigen Zeitintervalle, in denen die CPU ausgelastet ist, sowie solche, die kurzer als die Mindestdauer sind oder in denen die CPU- Auslastung zu stark schwankt; der Anteil der Idle-Zeit der nicht nutzbaren Zeitintervalle (aus den beiden zuletzt genannten Fallen) an der gesamten Rechenzeit ist in Abbildung 5.14 dargestellt.
Die durchschnittliche Dauer einer Lastsequenz liegt bei der Mehrzahl der Rechner zwischen 2 und 12 Stunden (vgl. Abbildung 5.15).
6Die meisten grunen Saulen haben eine Hohe von null und sind daher nicht zu erkennen.
51
A us
la st
un g
0.0016
0.008
0.04
0.2
1
W ah
rs ch
ei nl
ic hk
ei t
Auslastung
host00 host01 host02 host03 host04 host05 host06 host07 host08 host09 host10 host11 host12 host13 host14 host15 host16 host17 host18 host19 host20 host21 host22 host23 host24 host25 host26
host27 host28 host29 host30 host31 host32 host33 host34 host35 host36 host37 host38 host39 host40 host41 host42 host43 host44 host45 host46 host47 host48 host49 host50 host51 host52
Abbildung 5.12: Verteilung der Auslastungswerte in Netz A
52
Abbildung 5.13: Anteil der nutzbaren Lastsequenzen in Netz A
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
host50host45host40host35host30host25host20host15host10host05host00
Abbildung 5.14: Anteil der nicht nutzbaren Rechenzeit in Netz A
53
Abbildung 5.15: Durchschnittliche Dauer der Lastsequenzen in Netz A
Grenzen zwei auf einander folgende Lastsequenzen nicht direkt aneinander an (weil ein nicht nutzbares Intervall dazwischen liegt), entsteht eine Lucke. Fur die Rechner aus Netz A kann man die Anzahl der Lucken aus Abbildung 5.16 entnehmen: auf den meisten Rechnern gibt es zwischen 15 und 35 Lucken, was bei einer Dauer von 21 Tagen im Schnitt weniger als 2 Lucken pro Tag entspricht.
Schließlich stellt sich noch die Frage, fur welche Werte von q die Lastsequenzen jeweils q-beschrankt sind. Fur den eben betrachteten Rechner host07 aus Netz A sind alle Last- sequenzen ca. 1,8-beschrankt, einige sogar ca. 1,25-beschrankt, wie aus Abbildung 5.17 ersichtlich ist.
Abbildung 5.18 zeigt, dass die minimale und die maximale q-Beschranktheit der Lastse- quenzen auf den meisten Rechnern in Netz A i.W. dieselbe ist wie auf host07; die durch- schnittliche q-Beschranktheit der Lastsequenzen liegt auf vielen Rechnern sogar niedriger als auf host07.
5.3.2 Ergebnisse aus Netz B
Netz B weist im Gegensatz zu Netz A kein signifikantes Muster in der Last tags bzw. nachts sowie am Wochenende auf. Stattdessen ist ein permanentes Hintergrundrauschen feststellbar (vgl. Abbildung 5.19).
54
Abbildung 5.16: Anzahl der Lucken zwischen Lastsequenzen in Netz A
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
q− B
es ch
rä nk
th ei
Abbildung 5.17: q-Beschranktheit der Lastsequenzen auf host07 aus Netz A
55
Abbildung 5.18: Minimale, durchschnittliche und maximale q-Beschranktheit
0
0.2
0.4
0.6
0.8
1
A us
la st
un g
Abbildung 5.19: Auslastung von host01 aus Netz B (aneinandergereihte Ansicht)
56
W ah
rs ch
ei nl
ic hk
ei t
Auslastung
host00 host01 host02 host03 host04 host05 host06 host07 host08 host09 host10 host11 host12 host13 host14 host15 host16 host17 host18 host19 host20 host21 host22 host23
Abbildung 5.20: Verteilung der Auslastungswerte in Netz B
Auch in Netz B haben die insgesamt 24 untersuchten Rechner eine untereinander sehr ahnliche Verteilung der Auslastungswerte, wie Abbildung 5.20 zeigt. Auffallig ist das Hin- tergrundrauschen auf der Mehrzahl der Rechner sowie die Spitzen bei ca. 25%, 50% und 75%, die durch Dual- und Quadro-Prozes