Queuing – Warteschlangentheorie für Embedded-Software

Wann kann der nächste Burst starten? Was ist die maximale Queuing-Verzögerung?

Die eben vorgenommene Berechnung der Queue-Länge ist nur gültig, wenn die Queue vor einem neuen Burst vollständig geleert wurde. In dem Beispiel mit den Gehirnströmen bedeutet das:

D = L/Cr = 450 Messages / 200 Messages pro Sekunde = 2,25 Sekunden.

Ein neuer Burst darf also frühestens 2,25 Sekunden nach Ende des vorherigen Bursts beginnen.

Diese Einschränkung kann erhebliche Auswirkungen auf ein System haben. In unserem Gehirnstrom-Messgerät darf demnach die maximale Frequenz, mit der eine neue Farbe oder ein neues Bild gezeigt wird, einmal pro 3,75 Sekunden betragen. [Burstzeit + Erholzeit]. Bleibt zu hoffen, dass die Versuchspersonen im Gehirnstrom-Experiment dabei nicht die Geduld verlieren.

Was ist nun in diesem Beispiel die längste Wartezeit einer Message in der Queue? Dies entspricht auch dem Wert, den wir für D errechnet haben. Demnach kann eine Message in dieser Queue bis zu 2,25 Sekunden verzögert werden. Und tatsächlich muss die letzte Message jedes Bursts genau für diese Dauer in der Queue warten, ehe sie verarbeitet wird.

Formel zur Berechnung der Queue-Länge mit variabler Rate

Die Formeln zur Berechnung von Queues werden komplexer, wenn die Production und Consumption Rate einer Message nicht mehr konstant sind. Definieren wir zunächst neue Symbole, ehe wir mit einer komplexeren Gleichung arbeiten:

Die Burstperiode T beginnt zum Zeitpunkt t1 und endet zum Zeitpunkt t2. Ein Zeitpunkt innerhalb dieses Burstintervalls wird als Tx bezeichnet.

Die Production Rate Pr(t) für Messages der Queue ist nun über die Zeit veränderlich, ebenso wie die Consumption Rate Cr(t) für Messages der Queue.

Dieser Fall ist typischer, und er ist nicht linear. Somit können wir nicht mehr davon ausgehen, dass die Queue am Ende eines Bursts am längsten ist. Es sind also zwei Schritte erforderlich. Im ersten Schritt müssen wir die Länge der Queue zu jedem Zeitpunkt innerhalb eines Bursts ermitteln. Im zweiten Schritt müssen wir ermitteln, an welchem Punkt innerhalb des Bursts die Queue am längsten war. Das wäre dann die Länge der Queue, die wir für unsere Software vorsehen müssen. In diesem typischen Fall könnte die Queue etwa in der Mitte oder nach zwei Dritteln des Bursts am längsten sein.

Zu Schritt 1 sehen Sie nachfolgend eine Gleichung, mit der sich die tatsächliche Länge L(Tx) der Message Queue zu jedem Zeitpunkt Tx während des Bursts T ermitteln lässt:

L(Tx) zeigt an, wie die Länge der Message Queue während des Bursts über die Zeit variiert. Achtung: Diese Formel nimmt an, dass die Queue-Länge L(Tx) während des Bursts keinen Negativwert annimmt. Wenn das bei Ihnen so ist, belegen Sie am besten sofort einen Kurs in Warteschlangentheorie!

Nun zu Schritt 2: Ausschlaggebend ist hier die Worst-Case-Länge der Message Queue. Wir können nicht davon ausgehen, dass diese Worst-Case-Länge am Ende des Bursts vorliegt; sie könnte jederzeit während des Bursts vorliegen, wenn Pr(t) und Cr(t) stark schwanken. Man kann also nur sagen, dass die Worst-Case-Länge einer Message Queue wie folgt ist:

Lqueue = MAXIMUM[L(Tx)] für jeden Tx innerhalb T

Dies ist die erforderliche Gesamtlänge der Message Queue.

(ID:44833511)