Queuing – Warteschlangentheorie für Embedded-Software

Poisson-Verteilung der Message-Ankunftsraten

Oft wird folgendes angenommen: Ist die Ankunftszeit „memoryless“, lässt sich nicht sagen, wann die nächste Message ankommen wird. Wenn die letzten 25 Messages in einem Abstand von etwa 10 Millisekunden in der Queue angekommen sind, kann die nächste Message genauso gut erst nach 10.000 Jahren ankommen oder auch nach 10 Millisekunden.

Das wäre völlig chaotisch und unrealistisch, daher sprechen wir über eine geordnetere Art von Zufallsverhalten: Die Zwischenankunftszeiten sind willkürlich verteilt, aber die mittlere Anzahl von Ankünften je Zeiteinheit ist bekannt.

Dies bezeichnet man als Poisson-Verteilung (benannt nach einem französischen Mathematiker, nicht nach dem französischen Wort für Fisch). Die Poisson-Verteilung wird häufig zur Beschreibung diskreter, aber seltener Events mit willkürlich verteilten Zwischenankunftszeiten verwendet. Damit lassen sich beispielsweise Verkehrsunfallraten, die Häufigkeit von Krebserkrankungen innerhalb einer Bevölkerungszahl, radioaktiver Zerfall oder eben Interrupt-Ankunftsraten in Embedded-Systemen beschreiben.

Ein hohes Maß an Systematik wird erkennbar, wenn man diese Daten aus einer bestimmten Perspektive betrachtet: Fragen Sie, wie viele dieser zufälligen Events Sie innerhalb eines bestimmten Zeitintervalls erwarten, wenn Sie die mittlere Anzahl solcher Events je Zeitintervall kennen. Manchmal sind es weniger als die mittlere Event-Anzahl und manchmal mehr. Die Poisson-Verteilung drückt dies mathematisch aus. Wenn ‘E’ die mittlere Anzahl an Events pro Zeitintervall ist, dann steht ‘P(N)’ für die Wahrscheinlichkeit von ‘N’ Events in einem Zeitintervall, in dem:

-E N

P(N) = (e) * ( (E) / N! ) , für N = 0, 1, 2, 3, …

Keine Sorge, wir werden diese Formel nicht herleiten; wir werden nicht einmal damit arbeiten. Aber wir müssen verstehen, was sie bedeutet. Das wird in dem grafischen Beispiel in Abbildung 3 (Bildergalerie) veranschaulicht.

In diesem Beispiel ist E=1. Das heißt, wir haben durchschnittlich ein “Event” (bzw. eine Message-Ankunft in unserer Queue) je Zeitintervall. Wie im Diagramm dargestellt, beträgt die Wahrscheinlichkeit 1/3, dass es in jedem vorgegebenen Zeitintervall null Events geben wird. Die Wahrscheinlichkeit, dass es in jedem vorgegebenen Zeitintervall genau ein Event gibt, beträgt ebenfalls 1/3. Die Wahrscheinlichkeiten einer höheren Anzahl an Events in jedem vorgegebenen Zeitintervall ist geringer. Ähnliche Diagramme lassen sich für andere Werte von E erzeugen, die typischerweise auf beiden Seiten eines Peaks in der Nähe des Wertes E abfallen. Bei N>E fällt der Wert graduell ab, je höher N, also die Anzahl an Events je Intervall, steigt. Bei N<E fällt der Wert jedoch steil ab, da N keinen negativen Wert annehmen kann.

Wir gehen davon aus, dass Messages entsprechend solcher Poisson-Verteilungen in unserer Queue ankommen. Im weiteren Verlauf verwenden wir den Kehrwehrt von ‘E’ und bezeichnen diesen als ‘M’ – die mittlere Zwischenankunftszeit. M = 1/E

(ID:44833511)