Eine einfache Warteschlange in PDQ

Die Beziehung zwischen dem Szenario im Lebensmittelmarkt und den PDQ-Funktionen fasst Tabelle 2 zusammen. Nach diesem Schema kann man leicht ein einfaches Modell der Kasse in einem Lebensmittelmarkt nachbilden, wie das folgende Listing für die Perl-Variante von PDQ zeigt (Listing 2). Im PDQ-Code (unten) befinden sich die Input-Werte für die Ankunftsrate (λ) und die Bedienzeit (S):

(4)

(5)

Wendet man nun die metrische Beziehung (2) an, ergibt sich die Auslastung der Kasse wie folgt:

(6)

Analog dazu ergibt sich für die Verweildauer durch Anwenden der metrischen Beziehungen (1) und (2):

(7)

So erfährt man, dass die Verweildauer an der Kasse gleich vier durchschnittliche Bedienzeiten ist, wenn der Kassierer zu 75 Prozent ausgelastet ist. Die sich daraus ergebende durchschnittliche Warteschlangenlänge ist:

(8)

Aus Platzgründen kann hier lediglich die Ausgabeseite des generischen PDQ-Reports für dieses Modell gezeigt werden (Listing 1a).

Die berechneten PDQ-Werte stimmen genau mit den theoretischen Vorhersagen für den Durchsatz (X=λ), die Auslastung (r), die Warteschlangenlänge (Q) und die Verweildauer (R) überein.

Nachdem die fundamentalen Begriffe bekannt sind und PDQ als Tool für die Berechnungen eingeführt ist, lassen sich diese Werkzeuge auch auf Computerprobleme anwenden, etwa auf die Vorhersage der Leistung individueller Hardware-Ressourcen wie der Ausführungswarteschlange der CPU (siehe Kapitel 4 in [5]) oder eines Festplattengerätetreibers.

Die meisten Lehrwerke zur Warteschlangentheorie bieten Beispiele auf diesem Niveau. Wichtiger für die Vorhersage der Leistung von echten Computersystemen ist allerdings die Fähigkeit, den Workflow zwischen mehreren Warteschlangen-Ressourcen abbilden zu können, also die Interaktion zwischen Anforderungen, die gleichzeitig an Prozessoren, Festplatten und das Netzwerk gestellt werden. Die nächsten Abschnitte zeigen, wie man diese Aufgabe mithilfe von PDQ erfüllt.

Warteschlangensysteme

Anforderungen, die aus einer Warteschlange in eine andere fließen, entsprechen einer Warteschlangenkette oder einem Warteschlangennetz. Erfasst man anstelle der Anzahl der Anforderungen lediglich die Ankunftsrate (λ), spricht man von einem offenen System oder Kreis (Abbildung 6). Ein Beispiel für eine Situation dieser Art, die nicht aus der Welt der Computer stammt und sich durch das offene Modell in Abbildung 6 abbilden ließe, wäre das Boarding am Flughafen. Die drei Phasen sind: Warten am Gate, Schlangestehen auf der Fluggastbrücke, um ins Flugzeug zu gelangen, und zum Schluss Schlangestehen im Gang des Flugzeugs beim Boarding, während Passagiere weiter vorn Platz nehmen. Die durchschnittliche Antwortzeit (R) ergibt sich aus den in jeder Warteschlangenphase verbrachten Zeiten, also der Summe der drei Verweildauern. Im Computerkontext ließe sich das auf eine dreistufige Webapplikation anwenden, von der lediglich die Rate der HTTP-Requests bekannt ist.

Abbildung 6: Ein offenes System mit drei Queueing-Phasen.

Eine weitere Art von Warteschlangensystemen wird durch eine finite Menge (N) von Kunden oder Anforderungen charakterisiert. Genau diese Situation ergibt sich bei einem Lasttest. Eine finite Menge von Client-Lastgeneratoren sendet Anforderungen an das Testsystem, wobei keine weiteren Anforderungen von außerhalb in das isolierte System eintreten können. (Open-Source Last- und Stresstesttools finden Sie unter [7].)

Darüber hinaus wirkt eine Art Rückkopplungsmechanismus, weil zu jeder Zeit nicht mehr als eine Anforderung unbearbeitet bleiben darf. Mit anderen Worten: Jeder Lastgenerator sendet erst dann eine weitere Anforderung, wenn die vorherige abgearbeitet worden ist. In der Sprache der Warteschlangentheorie geht es hier um einen geschlossenen Warteschlangenkreis.