Rechnernetze

Erhaltungssätze

Eine wichtige Frage in einem technischen System ist es, welche Veränderungen Auswirkungen auf das Systemverhalten haben bzw. welche Veränderungen keine Auswirkungen auf das Systemverhalten zeitigen. Eine Invariante ist eine Größe, die sich trotz Änderungen nicht selbst verändert. In der Wartetheorie spielen die Erhaltungssätze (conversation laws) eine wichtige Rolle.

In dem obigen Diagramm ist die restliche Bedienzeit sämtlicher in einem Wartesystem wartender Aufträge dargestellt. Die Kurve der restlichen Bedienzeit ist ausschließlich charakterisiert durch

Damit ist die Kurve der restlichen Bedienzeit unabhängig von der Bedienstrategie! Die Kurve und die Fläche unter dieser Kurve sind somit invariant bzgl. der tatsächlich angewendeten Bedienstrategie. Ihre Fläche, deren numerischer Wert im folgenden nicht interessiert, sei C.

Die Fläche unter dieser Kurve läßt sich u.a. auch durch folgenden Ausdruck berechnen wie dem vorstehenden Diagramm entnommen werden kann.

Mit der Definition der Kovarianz zweier Zählgrößen

erhalten wir also die Beziehung

Dieses läßt sich nach W auflösen, so daß folgt

Die Größen auf der rechten Seite hängen bis auf die Kovarianz nicht von der Wartezeit ab. Sind Kovarianz und Bedienzeit unabhängig, was bei FIFO-, LIFO- und Random-Strategien der Fall ist, dann hängt auch die Wartezeit nicht von den jeweiligen Bedienstrategien ab. Also ist die Wartezeit invariant unter diesen Bedienstrategien.

Werden kurze Aufträge bevorzugt, so ist deren Wartezeit in der Regel auch kürzer als die längerer Aufträge. In diesem Fall ist die Kovarianz positiv, da kurze Aufträge kurze, lange Aufträge lange Wartezeiten haben, die Größen also positiv korreliert sind. In diesem Fall hat man einen negativen Einfluß auf die mittlere Wartezeit, so daß diese in solchen Fällen kürzer ist als FIFO usw. Die Strategie SJN (Shortes Job Next) verkürzt also die mittlere Wartezeit zu Lasten von Aufträgen mit langer Bedienzeit.

Werden hingegen lange Aufträge bevorzugt, so ist deren Wartezeit in der Regel auch kürzer, die Wartezeit kurzer Aufträge jedoch länger. Aus der negativen Korrelation folgt, daß die Kovarianz cov(w,s) negativ ist, also die mittlere Wartezeit insgesamt ansteigt. Die Strategie LJN (Longest Job Next) verlängert also die mittlere Wartezeit zu Lasten von Aufträgen mit kurzer Bedienzeit.