Queuing – Warteschlangentheorie für Embedded-Software

Hilfreiche Formeln

Nachweislich (auch wenn wir uns an dieser Stelle einen mathematischen Beweis sparen) ist die durchschnittliche Queue-Länge wie folgt:

Lavg = R / (1-R) , oder Lavg = A / (M-A).

Die mittlere Verweilzeit einer Message in der Queue ist dann:

Tavg = A / (1-R) , oder Tavg = A*M / (M-A).

Wenn man die Tavg-Formel durch die Lavg-Formel teilt, erhält man: Tavg / Lavg = M oder:

Lavg = Tavg / M oder Lavg = E* Tavg .

Dies wird auch als Little-Theorem bezeichnet und ähnelt ein wenig der bekannten Formel „Geschwindigkeit x Zeit = Strecke“ aus der Physik, nur eben auf Queues angewendet. Es besagt folgendes: Wenn für alle Werte Mittelwerte verwendet werden, ist die Länge einer Queue das Produkt der Ankunftsrate von Messages multipliziert mit deren Verweilzeiten in der Queue.

Warum beinhaltet das Little-Theorem nicht A, also die Dauer, die durchschnittlich für die Verarbeitung einer Message erforderlich ist? Das wäre doch intuitiver? Antwort: Das Little-Theorem beinhaltet sehr wohl A, denn A spielt eine wichtige Rolle bei der Bestimmung von Tavg, also der mittleren Verweilzeit einer Message in der Queue.

Eine letzte hilfreiche Formel: Die Wahrscheinlichkeit P, dass sich mindestens K Messages in der Queue befinden werden („enqueued“), beträgt:

P [ > K enqueued ] = (R) .

Das heißt, die Wahrscheinlichkeit, dass eine Queue länger wird, sinkt exponentiell zu deren Länge (da R kleiner als 1 ist).

Nachfolgend zeigen wir Ihnen, wie Sie mit diesen vier Formeln hilfreiche Schlüsse für den Entwurf Ihrer Embedded-Systeme und -Software ziehen können.

(ID:44833511)