Queuing – Warteschlangentheorie für Embedded-Software

Beispiel: Queue mit variabler Rate

Die Formeln sind alle ziemlich angsteinflößend für diejenigen, die inzwischen vergessen haben (oder gern vergessen würden), was sie über Höhere Mathematik gelernt haben. Die Integralberechnung lässt sich aber umgehen. Verwenden Sie Diagramme für die Funktionen und berechnen Sie die Flächen unterhalb der Kurven, anstatt die Gleichung zu integrieren.

Abbildung 2 zeigt Diagramme der Message Production Rate und Consumption Rate in Abhängigkeit von der Zeit. Um die Länge der Queue zum Zeitpunkt Tx zu ermitteln, müssen Sie lediglich die Fläche unter der Kurve Pr(t) bis zum Zeitpunkt Tx und die Fläche der Kurve Cr(t) bis zum Zeitpunkt Tx bestimmen. Die Differenz zwischen den beiden Flächen bildet dann L(Tx), also die Länge der Queue zum Zeitpunkt Tx. (Eine ganz simple Methode besteht darin, ein Lineal vertikal auf die 2 Graphen zum Zeitpunkt Tx zu legen und dann die Fläche links vom Lineal und unter jeder der 2 Kurven zu ermitteln).

Wenn Sie dies für mehrere verschiedene Werte von Tx durchführen, erhalten Sie eine graphische Darstellung von L(Tx) in Abhängigkeit der Zeit Tx. Dies entspricht der untersten Kurve in Abbildung 2. Die Kurve zeigt, wie sich die Anzahl der Messages in der Queue zeitabhängig ändert. Sie können die Kurve nach dem Ende des Message Production Burst weiterführen und sehen, wie sich die Queue leert. (Im typischeren „variablen“ Szenario lässt sich die Einschränkung auf definierte Bursts etwas lockern).

Nun gilt es also nur noch, den höchsten Punkt der Kurve von L(Tx) zu ermitteln. Dieser höchste Punkt steht für die maximale Länge der Message Queue an jedem beliebigen Zeitpunkt innerhalb des Bursts. Es ist die Gesamtlänge, die für Ihre Message Queue erforderlich ist.

Und wenn man keine präzise Formel hat?

Der Beitrag hat bisher einen grundlegen Überblick über die Warteschlangentheorie für Embedded-Systementwickler vermittelt. Einige sehr einfache algebraische Formeln wurden vorgestellt, die von vereinfachten Annahmen ausgehen, etwa konstante oder bekannte Ankunfts- und Ausgangsraten. Aber solche Annahmen sind oft eine Übervereinfachung. Der eine oder andere Embedded-Entwickler hat inzwischen bestimmt schon Einspruch eingelegt: „Es ist gar nicht möglich, an eine präzische algebraische Formel für die Rate zu kommen, mit der meine Messages verschickt oder verarbeitet werden. Die bisher gezeigten Formeln nützen mir deshalb nichts. Gibt es keine andere Möglichkeit, die Queue-Länge und Queue-Verzögerungen für eine echte Applikation herauszufinden?“

Um das zu beantworten, müssen wir etwas tiefer in die Warteschlangentheorie einsteigen, insbesondere in die „klassische“ Warteschlangentheorie. Bisher haben wir uns auf deterministische, harte Echtzeitsysteme konzentriert. Ab jetzt richten wir unser Augenmerk auf Systeme mit einem Zeitverhalten, das sich mithilfe statistischer Methoden beschreiben lässt. Sie werden oft auch als „weiche“ Echtzeitsysteme bezeichnet.

Wir werden mit der sogenannten M/M/1-Queue arbeiten; dies ist die mathematische Bezeichnung für die einfachste Art eines statistischen Queuing-Systems. Das erste M steht für „Memoryless arrival time probability function“ und besagt, dass die Ankunftszeiten nachfolgender Messages in einer Queue nicht von der Ankunftszeit vorheriger Messages abhängen. Das zweite M steht für “Memoryless service time probability function”. Das heißt, die Verarbeitungszeiten nachfolgender Messages hängen nicht von den Verarbeitungszeiten vorheriger Messages ab. Das 1 schließlich bedeutet, es geht um eine einzelne Queue, die ihre Messages zur Verarbeitung an einen Prozessor weiterleitet.

(ID:44833511)