Institut für Rechnerentwurf und Fehlertoleranz - Universität Karlsruhe
Forschungsschwerpunkt Informationslogistik

(Erweiterte) Warteschlangennetze

Überblick   MM1-System   WS-Netz   Simulation eines MM1-Systems   Software-Voraussetzungen
Zurück zur Modellierungsseite

Überblick

Warteschlangennetze stellen heute eine häufig verwendete und weit verbreitete Modellierungstechnik dar. Mit den vorliegenden Computeranimationen soll die grundlegende Funktionsweise von Warteschlangennetzen verdeutlicht werden. Die wesentlichen Lernziele sind:
  • Erste Erfahrungen beim Umgang mit Warteschlangennetzen sammeln;
  • Darstellung der grundlegenden Gesetzmäßigkeiten in Wartesystemen;
  • Visualisierung von Einschwingphase und stationärem Zustand.
    •

    MM1-Wartesystem

    Bei einem MM1-System handelt es sich um ein elementares Wartesystem (Bedienstation) bestehend aus einer Warteschlange und einer Bedieneinheit. In einer externen Quelle werden Aufträge erzeugt, in die Warteschlange eingereiht, von der Bedieneinheit abgearbeitet und schließlich in einer Senke wieder vernichtet. Ein solches elementares Wartesystem wird charakterisiert durch die Ankunftsrate (lambda) der nacheinander ankommenden Aufträge und die Bedienrate (mue), mit der die einzelnen Aufträge von der Bedieneinheit abgearbeitet werden. Diese beiden Größen werden beim MM1-System durch Zufallsvariablen mit negativ exponentieller Verteilung beschrieben, wobei jeweils der Mittelwert als Eingabeparameter anzugeben ist. Als Ausgabegrößen werden u.a. die mittlere Wartezeit der Aufträge in der Warteschlange sowie die mittlere Warteschlangenlänge berechnet.
     
    Bild einer MM1-Warteschlange

    Um die Abläufe in elementaren Wartesystemen besser verstehen zu können, wurde eine Computeranimation realisiert, die über den unten dargestellten Verweis aufgerufen werden kann. Die Animation verdeutlicht, wie Aufträge dynamisch erzeugt, in der Bedienstation abgearbeitet und schließlich wieder vernichtet werden. Zusätzlich wird die Entwicklung der beiden Ausgabegrößen mittlere und absolute Warteschlangenlänge in Kurvenform aufgetragen. Man beachte, daß sich die Werte der Ausgabegröße mittlere Warteschlangenlänge nach Durchlaufen einer gewissen Einschwingphase zunehmend stabilisieren.

    Animation eines MM1-Wartesystems

    Erweitertes Warteschlangennetz

    Das bei den erweiterten Petrinetzen besprochene speichergekoppelte Multiprozessor-System mit Mehrfachbus wurde auch auf Basis von erweiterten Warteschlangennetzen modelliert. Dazu wurden mehrere Bedienstationen miteinander verbunden, aber auch sogenannte "passive" Knoten zur Ressourcenmodellierung verwendet. Um zum Beispiel den begrenzten Zugriff auf den Kommunikationskanal (Bus) zu realisieren, wurde eine Kombination aus Anforderungs- und Freigabeknoten mit dem dazugehörenden Token-Pool eingesetzt. GB bedeutet hier "Global Bus", GM "Global Memory" und QS steht für ein einzelnes "Queueing System", also eine Bedienstation. In der angebotenen Computeranimation kann man u.a. beobachten, wie Aufträge (Prozessoren) warten müssen, bis ein Bus frei wird (ein GB-Token ist verfügbar) und bis auf den gewünschten Speicher zugegriffen werden kann (ein GM-Token ist verfügbar).

    Animation eines erweiterten Warteschlangennetzes

    Simulation eines MM1-Systems

    Zum oben beschriebenen MM1-System wurde ein einfacher Simulator realisiert, um das Verhalten der Ausgabegrößen in Abhängigkeit unterschiedlicher Eingabegrößen beobachten zu können. Dazu muß der Benutzer für die Eingabeparameter jeweils einen Wert festlegen. Zudem läßt sich über den Parameter "Anzahl Aufträge" (AA) bestimmen, wieviele Aufträge insgesamt von der Quelle erzeugt werden sollen, bis die Simulation beendet und die berechneten Ausgabegrößen schließlich ausgegeben werden können. Durch diesen Parameter wird also explizit die Simulationsdauer beeinflußt.

    Zu Beginn der Simulation müssen die Werte der Eingabeparameter festgelegt werden, zum Beispiel:

    Danach ist der Button "Starte einen Simulationslauf" zu drücken. Nach der Beendigung der Simulation werden folgende Ausgabegrößen ausgegeben: Anschließend kann der Benutzer die Eingabeparameter verändern und den Simulator erneut starten. Die berechneten Ausgabewerte lassen sich durch Cut-and-Paste in ein Tabellenkalkulations-Programm (beispielsweise Excel) übertragen, um deren Verlauf zu visualisieren.

    Simulation eines MM1-Wartesystems (Java 1.1 - Applet)

    Software-Voraussetzungen zur Betrachtung der Animationen

    Zur Betrachtung der Animationen wird die Multimediaerweiterung QuickTime 3 der Firma Apple Computer benötigt. Diese kann im WWW unter der Adresse "http://www.apple.com/quicktime/download/index.html" heruntergeladen werden. Falls nicht vorhanden, werden Sie beim Aufruf der Animation aufgefordert, dieses Plugin zu installieren.