Queuing – Warteschlangentheorie für Embedded-Software

Exponentialverteilung der Message-Verarbeitungszeiten

Nach Ankunft in einer Queue verbleibt eine Message dort, bis alle Messages vor ihr aus der Queue entfernt und verarbeitet wurden. Es ist nicht schwierig, die Message-Verarbeitungszeit auch als zufällig verteilt, jedoch mit einer bekannten mittleren Verarbeitungszeit, darzustellen – also machen wir das so.

Die Annahmen sind tatsächlich dieselben wie für eine Poisson-Verteilung; die von Herrn Poisson entwickelten Berechnungen lassen sich also auch auf Message-Verarbeitungszeiten anwenden. Wenn es um Message-Verarbeitungszeiten geht, formulieren wir die Formeln aber anders: Wenn A die mittlere Message-Verarbeitungszeit ist, dann ist die Wahrscheinlichkeit P(T), dass eine beliebige vorgegebene Message reale Verarbeitungszeit verbraucht, wie folgt:

-T/A

P(T) = (e) / A , für Verarbeitungszeiten T von 0 bis A und höher.

Bei überdurchschnittlichen Message-Verarbeitungszeiten (rechts von A) erstreckt sich die Kurve ins Unendliche ---. Dies besagt, dass manche Messages extrem lange Verarbeitungszeiten haben können, auch wenn die Wahrscheinlichkeit, dass dies bei einer vorgegebenen Message eintritt, sehr gering ist. Bei unterdurchschnittlichen Message-Verarbeitungszeiten (links von A) beschränkt sich die Kurve jedoch auf positive Zeitwerte. In diesem kleinen Bereich läuft also eine hohe Anzahl an Messages auf, und diese Anzahl steigt, je mehr die Verarbeitungslast gegen Null geht.

Die Realität in unseren Embedded-Systemen entspricht häufig diesem Muster. Es gibt oft viele Nachrichten, die einfach zu verarbeiten sind, und einige, die zeitaufwändiger sind. Deshalb verwenden wir eine Exponentialverteilung zur Beschreibung der Message-Verarbeitungszeit. Die mittlere Message-Verarbeitungszeit A wird uns im weiteren Verlauf nochmal begegnen.

Wann entsteht eine Queue?

Wenn sowohl die Ankunftszeiten als auch die Verarbeitungszeiten willkürlich sind, wie entsteht dann überhaupt eine längere Queue? Wenn die Ankunfts- mit den Verarbeitungszeiten korrelieren würden, würde unter Umständen keine entstehen, oder sie wäre im schlimmsten Fall sehr kurz. Die Message-Ankunftszeiten korrelieren aber in der Redgel nicht mit den Message-Verarbeitungszeiten, weder in der Warteschlangentheorie noch in Embedded-Systemen und -Software. Das heißt, ein Message-Cluster mit sehr kurzen Zwischenankunftszeiten könnte viele Messages mit sehr langen Verarbeitungszeiten enthalten. Und dann würde eine Queue mit signifikanter Länge entstehen.

Wenn die mittlere Zwischenankunftszeit ‘M’ kürzer ist als die mittlere Verarbeitungszeit ‘A’, also M<A, dann wächst die Queue ungebremst weiter, läuft über und wird nutzlos. Somit ist in unserem Szenario folgendes erforderlich:

M > A , nur dann ist eine Queue sinnvoll.

Dies lässt sich anders darstellen, indem man einen neuen Parameter R hinzufügt, der wie folgt definiert ist:

R == A / M Dies entspricht R=A*E.

R ist das Verhältnis der mittleren Verarbeitungszeit zur mittleren Zwischenankunftszeit. R muss kleiner als 1 sein, damit eine Queue nicht überläuft. Das heißt, Messages müssen mit einer langsameren mittleren Geschwindigkeit ankommen als sie verarbeitet werden können, damit eine Queue sinnvoll ist.

(ID:44833511)