Queuing – Warteschlangentheorie für Embedded-Software

Entwickler von Embedded-Systemen müssen beim Systementwurf oft die maximale Anzahl an Messages ermitteln, die in einer Message Queue auflaufen können. Viele RTOS benötigen diese Information, um eine Queue zu erzeugen. Besonders wenn es um „harte“ Echtzeitsysteme geht, gilt es, sich auch mit Queuing-Verzögerungen auseinanderzusetzen,

Anbieter zum Thema

MicroConsult Microelectronics Consulting & Training GmbH

Wenn man mich auf diese Themen anspricht, erwidere ich gern: „Ist alles Warteschlangentheorie“. Fast immer reagieren die Embedded-Entwickler dann mit einem etwas nervösen Lachen und denken sich vermutlich so etwas in der Art: „Klar - ich lege mein Projekt erst mal auf Eis und mache einen Kurs über die Warteschlangentheorie, und das alles nur wegen der Message Queue in diesem Programm. Was hat der Mann geraucht?“

Bildergalerie

Bildergalerie mit 7 Bildern

Ähnliche Fragen stellen sich zu der Kapazität von verketteten Listen und Ringpuffern, der Anzahl von Puffern in einem Pufferpool oder auch der Zuweisung von Dual-Port-RAM zu Puffer-Deskriptoren in modernen Kommunikationsprozessoren. Diese Faktoren haben einen direkten Einfluss auf das Speichervolumen, das der entsprechenden Ressource zuzuweisen ist, sowie auf die Kapazität eines Embedded-Systems, das immer unterschiedlich große Datenmengen verarbeiten muss.

Um die erforderliche Kapazität zu ermitteln, greifen Entwickler häufig auf empirische Methoden zurück. Bei einer Methode teilen sie z.B. den gesamt vorhandenen RAM in ihrem Entwicklungstarget-Board auf und weisen ihn den Stacks, Queues, verketteten Listen und Pufferpools zu. Bleibt zu hoffen, dass das Hardwareteam genügend RAM vorgesehen hat, damit diese Strukturen alle ausreichend versorgt sind.

Vor dem Ausführen der Applikationssoftware „bemalt“ (das heißt füllt) eine Testsoftware diese Strukturen mit Inhalt, der unwahrscheinlich ist, z.B. Muster aus 0xAAAAAAAA , 0x55555555 oder 0xDEADDEAD. Dann wird die Applikation eine Zeitlang ausgeführt. Anschließend werden die Strukturen daraufhin untersucht, wie viel von der Standard-„Farbe“ übrig ist. Ist in einem Bereich noch „Farbe“ vorhanden, hat die Applikation diesen vermutlich nicht verwendet, also kann ein Großteil davon wohl eliminiert werden.

Bei einer anderen empirischen Methode lässt sich mithilfe RTOS-kompatibler Debugger/Profiler und ‚Object Browser‘ die maximale Anzahl von Messages in einer Queue zu jeder Zeit während des Versuchslaufs der Applikationssoftware erfassen. Manche liefern sogar ein Diagramm der Queue-Befüllung in Abhängigkeit der Zeit. Ähnliche Diagramme können für Stacks und Pufferpools erzeugt werden. Der höchste Punkt des Diagramms zeigt an, wie viel Kapazität Ihre Software tatsächlich benötigt hat.

Ist dieser Wert aber wirklich ein zuverlässiger Indikator für die erforderliche Kapazität einer bestimmten Message Queue, eines Stacks oder eines Pufferpools? Leider nicht, denn nur wenige Sekunden oder Minuten nach Ende des Versuchslaufs könnte der Speicherbedarf der Software erheblich ansteigen, hätte man sie weiterlaufen lassen. Und diese Information ließe sich dann mit keiner empirischen Methode erfassen.

Auf empirische Methoden ist also nicht immer Verlass, selbst wenn nachgebessert und beispielsweise 30 Prozent zusätzliche Kapazität hinzugefügt wird.

Ein dritter Ansatz, der eher auf Mathematik basiert und nicht auf empirischen Tests, bringt uns der Antwort auf unsere Frage nach der Kapazität vielleicht näher. Dieser Beitrag stellt Queuing-Berechnungen vor, zwar vereinfacht, aber dennoch mit genügend Tiefe, um einige unserer Fragen zum Softwareentwurf beantworten zu können. Auch werden wir erfahren, ob mehr Warteschlangentheorie auch mehr Antworten bedeutet.

Als Beispiel dienen uns hier Software Message Queues; ähnliche Betrachtungen ließen sich aber auch für verkettete Listen, Pufferpools, Ringpuffer und Stacks anstellen.

(ID:44833511)