Queuing – Warteschlangentheorie für Embedded-Software

Berechnen von Bursts mit konstanter Rate

Beginnen wir mit einem einfachen Szenario und nehmen an, dass die Consumption Rate ‘Cr’ und die Production Rate ‘Pr’ konstant sind. Die Konstante ‚Production Rate‘ ist natürlich auf die Burst-Zeit T zu begrenzen. Nehmen wir vorerst an, dass sie zu anderen Zeiten Null ist.

Zu Beginn eines Bursts sollte die Message Queue leer sein. Während des Bursts werden Messages erzeugt und der Queue hinzugefügt. Gleichzeitig werden einige Messages aus der Queue entfernt und verarbeitet. In dieser vereinfachten Situation läuft alles linear ab, also steigt die Anzahl der Messages in der Queue mit fortschreitendem Burst allmählich an. Am Ende des Bursts sieht es so aus:

Pr*T Messages wurden erzeugt und der Queue hinzugefügt.

Und … Cr*T Messages wurden aus der Queue entfernt und verarbeitet.

Damit ist am Ende des Bursts die Anzahl der in der Queue verbleibenden Messages L = (Pr-Cr)*T.

Da die Queue über die Dauer des Bursts immer länger wird, ist die Länge der Queue am Ende des Bursts die maximale Länge der Queue während des Bursts. Damit ist L = (Pr-Cr)*T die maximale Queue-Länge – so groß muss die Queue sein.

Aber aufgepasst! Wir sind noch nicht ganz fertig mit unserem „konstanten“ Szenario. Wenn kurz nach Ende des ersten Bursts ein weiterer eintritt, läuft der Trichter über bzw. hat die Message Queue keine Kapazität für diesen weiteren Burst. Die oben genannte Formel gilt also nur, wenn ein neuer Burst erst dann eintritt, wenn die Inhalte aus dem vorherigen Burst vollständig aus dem Trichter/der Queue entfernt wurden. Dieser Vorgang nimmt Zeit in Anspruch – die sog. Entleerdauer D bzw. erforderliche Deadtime (Wartezeit). Sie lässt sich wie folgt berechnen:

Am Ende des Bursts geht die Production Rate ‘Pr’ auf Null, die Consumption Rate ‘Cr’ behält jedoch ihren konstanten Wert. Zu diesem Zeitpunkt sind L = (Pr-Cr)*T Messages in der Queue.

Demnach beträgt die Entleerdauer D = L/Cr bzw. D = (Pr/Cr – 1)*T.

Die Entleerdauer D könnte sogar viel länger sein als die Burst-Zeit, wenn das Pr/Cr-Verhältnis hoch ist. Es ist sozusagen eine „Ruhezeit“, in der die Message Queue sich auf einen neuen Burst vorbereiten kann.

Sie werden schnell selbst erkennen, dass die Entleerdauer D auch die längste Zeit ist, in der eine Message in der Queue verweilt und darauf wartet, dass sie abgeholt wird. So lange muss die Message, die der Queue am Ende des Bursts als letztes hinzugefügt wurde, darauf warten, dass die anderen Messages vor ihr abgeholt und verarbeitet werden. D ist also die maximale Wartezeit in unserer einfachen „linearen“ Queue. (Die Variablen-Bezeichnung „D“ kann also auch für die maximale Delay-Zeit stehen). Dieser Wert spielt beim Entwurf zeitkritischer Systeme eine wichtige Rolle.

Beispiel: Berechnung von Bursts mit konstanter Rate in einem Psychologie-Experiment

In diesem Beispiel ist die Applikation ein Gerät, das Veränderungen in den Gehirnströmen eines Menschen als Reaktion auf Farben und Bilder erkennt, die der Versuchsperson gezeigt werden. Gehirnströme, auch elektroenzephalographische (EEG) Signale genannt, sind schwache elektrische Signale. Sie werden mithilfe von Elektroden erfasst, die ringförmig auf dem Kopf der Versuchsperson angebracht sind.

Sobald der Versuchsperson eine neue Farbe oder ein neues Bild gezeigt wird, tastet die Hardware die EEG-Signale mit 2 Millisekunden Abtastgeschwindigkeit ab. Dieser Sampling-Vorgang dauert insgesamt 1,5 Sekunden. In der Software besteht jedes Sample aus einem Byte-Array, ein Byte per Elektrode. Das gesamte Array für ein Sample wird als eine einzige Message gespeichert, die dann einer Message Queue hinzugefügt wird, siehe Abbildung 1.

Die Weiterverarbeitung der EEG-Signale dauert 5 Millisekunden je Sample. Wenn die EEG-Signal-Messages in einer Message Queue gespeichert werden, eine Message je Datensample, wird die erforderliche Länge der Message Queue wie folgt berechnet:

Pr = 500 Samples pro Sekunde während eines Bursts
Cr = 200 Samples pro Sekunde während und nach einem Burst
T = 1,5 Sekunden Burst-Dauer

Ergibt: L = (500-200)*1,5 = 450 Messages sind in der Warteschlange aufzureihen.

Die erforderliche Länge der Message Queue beträgt dann genau 450 Messages.

(ID:44833511)