Inhalt
|
Anlass
Sudoku oder doch lieber Ada?
Nein, kein Sudoku-Rätsel zum Zeitvertreib! Fürs Geo-Caching habe ich zwei selbst gelöst, für das dritte, das schwierige, hatte ich zufällig ein Forth-Programm und damit die Lösung in der Hand ...
Meine kleine, selbstgestellte Aufgabe: Ein Software-System hat sich über die Jahre munter weiter entwickelt, etliche Meldungen sind hinzugekommen. Nun stellen die Anwender fest, dass unter Umständen die wichtigen Meldungen zu spät beim Empfänger ankommen oder etwa auch in der Meldungsflut untergehen.
Die Meldungen sollen daher (vielleicht nur in bestimmten Betriebsmodi) prioritätsgesteuert gesendet werden.
Anforderung
Was soll der Baustein tun?
Nun denn, liegt eine 'wichtige' Meldung vor, so soll diese vor allen anderen gesendet werden, zudem sollen 'unwichtige' Meldungen unterdrückt werden.
Entwurf
Wie gestalte ich den Baustein?
Ich möchte den Baustein gerne unabhängig von der vorhandenen Software entwickeln und testen. Ein generisches Paket liegt also nahe:
Generic_Priority_Controller
(Schnittstelle)
Die Zeilen 2 bis 10 umfassen die generische Schnittstelle, hier sind das 2 generische Typen und eine generische Prozedur - diese müssen alle bei der Ausprägung (oder Instantiierung) des generischen Pakets durch konkret Typen und Prozeduren ersetzt werden.
Data_Priority_Type (Zeile 4) ist ein Aufzählungstyp, er stellt den Satz der Prioritäten bereit. Data_Type (Zeile 8) steht für den Meldungstyp, dessen Struktur nicht offen gelegt ist (daher private), tagged bedeutet, dass der Typ klassenartig hierachisch aufgebaut ist. Handler (Zeile 10) ist die generische Prozedur für die prioritätsgesteuerte Verarbeitung der Meldungen, von ihr ist nur die Prozedurschnittstelle bekannt.
Die Zeilen 13-15 stellen die eigentliche Schnittstelle des Paketes (Paketspezifikation) dar, hier sind das 2 Prozeduren. Mittels Start wird eine paketinterne Task gestartet und mittels Get kann das Paket mit Meldungen versorgt werden.
Feinentwurf
Wie sieht die Algorithmik aus?
In etwa so, in Pseudo-Code formuliert:
loop
Schaue nach, ob neue Meldungen vorliegen.
Sortiere alle neuen und alten gepufferten Meldungen.
nach Eingang und Priorität.
Verarbeite die älteste Meldung der höchten Priorität.
end loop
Implementierung
Was leistet Ada für die Kodierung?
Zwei Sprachkonstrukte bieten sich als Vehikel der Implementierung an: (nebenläufige) Tasks oder geschützte Typen (protected types). Ich wähle das Task-Konstrukt und den requeue-Mechanismus.
Controller-Task
(Spezifikation und Rumpf-Ausschnitt)
Hinweis: Da, wo im Ada-Quelltext ein '+' rechts neben der Zeilennummer steht, ist der Code zusammengefaltet.
Die Task Controller im Rumpf des Paketes Generic_Priority_Controller weist 2 öffentliche Eingänge Start und Get (Zeilen 12-13) auf und eine private Eingangsfamilie Request(Data_Priority_Type) (Zeilen 18-21); für jeden Wert des Aufzählungsypes Data_Priority_Type gibt es einen eigenen Eingang. Jeder einzelne Task-Eingang ist mit einem FIFO-Puffer verknüpft.
Im Rumpf (body) der Task wird das Ablaufverhalten der Task implementiert, hier wartet die Task nach der Aktivierung an der accept-Anweisung Start (Zeile 29) bis ein externer Programmteil (mittelbar) den Task-Eingang Start (Zeile 12) aufruft und damit ein Rendezvous eingeht. Danach durchläuft die Task die Schleife Outer (Zeilen 31-85).
Controller-Task
Abholen von neuen Meldungen
Der Zähler Total gibt an, wieviele Meldungen die Task aktuell verwaltet. Ist keine interne Meldung da, wartet die Task an der accept-Anweisung Get (Zeile 39) auf eine eingehende Meldung; geht eine solche ein, wird sie dem Eingangspuffer entnommen und innerhalb des Rendezvous' in einem der requeue-Eingänge entsprechend der Priorität abgelegt.
Nun wird die innere Schleife More_Entry_Calls (Zeilen 50-63) solange durchlaufen, bis der Eingangspuffer mittels der accept-Anweisung Get (Zeile 54) geleert ist; ist der Puffer leer, wird die else-Anweisung Zeile 59 angesprungen, wonach mit der exit-Anweisung Zeile 60 die innere Schleife verlassen wird.
Controller-Task
Verarbeiten einer Meldung
In der inneren Schleife Servicing_Requests (Zeilen 67-83) wird nun in der Priorität absteigend über die Puffer der Request-Eingänge (Zeile 71) iteriert - wird bei einem Schleifendurchlauf eine Meldung gefunden, wird die Handler-Prozedur aufgerufen und anschließend die innere Schleife verlassen, um nach neuen Meldungen zu schauen; wird im Puffer keine Meldung gefunden, wird auch nichts unternommen (Zeilen 79-80).
Test
Was für eine lästige Angelegenheit!
Ich wollte eigentlich Zusicherungen (assertions) und vielleicht neue Sprachmittel von Ada 2015 (Vorbedingungen, Nachbedingungen, etc) verwenden, um den Test etwas Formaler zu gestalten. Doch bei den ersten weitergehenden Testläufen, die schon mehr einen Nachweis-Charakter haben sollten, gab es Irritationen: Die innere Schleife More_Entry_Calls wurde anfänglich nie durchlaufen, es gab immer nur einen Eintrag im Eingangspuffer, obwohl ich in der Testprozedur sequentiell Meldungen bereitgestellt hatte. Ich habe also doch Textausgaben eingestreut, um das Verhalten zu verstehen ...
Und ich habe ein Feld von Tasks implementiert, um den Eingangspuffer hinreichend zu füllen. Aber zunächst zu den Testmeldungen ...
Zwei armselige Testmeldungen
im Paket Test_Data
Die Prozeduren Send (Zeilen 12, 18) machen hier einfach Textausgaben, implementiert im Rumpf des Paketes.
Testprogramm Test_Priority_Controller (Anfang)
Zum Testprogramm! Um das generische Paket Generic_Priority_Controller ausprägen zu können, benötige ich noch Prioritäten und eine konkrete Handler-Prozedur. Die Prioritäten werden durch Message_Priority_Type (Zeile 12) und die Prozedur durch Send_With_Priority (Zeilen 16-23) bereitgestellt. Eine Instanz Pctr des generischen Paktes wird durch die Zeilen 25-28 bereitgestellt.
Testprogramm Task-Typ
Ich möchte einen Satz von (nebenläufigen) Tasks haben, die jeweils sequentiell Meldungen bereitstellen. Dazu definiere ich zunächst eine Zugriffstyp (Zeiger) Send_Procedure_Access_Type (Zeile 37) auf eine parameterlose Prozedur.
Der Task-Typ Sender_Task_Type (Zeilen 41-67) hat einen Taskeingang Start (Zeilen 42-44, Implementievrung 54-59); mit dem Eingangsaufruf wird auch ein 'Zeiger' (Zugriff) auf die Prozedur, etwa Send1_Procedure übergeben, die das Taskobjekt ausführen (Zeile 63) soll.
Vielfalt:
Ein Taskobjekt - eine Prozedur
Nun braucht es nur noch 3 Felder und schon kann es mit dem Testen losgehen.
Testprogramm
Taskobjekte und Rumpf
Im Feld Send_Procedure_Access_Array (Zeilen 135-139) sind die Zeiger auf die auszuführenden Prozeduren zusammengefasst, im Feld Sender_Task_Id_Array (Zeilen 145-146) die Kennzeichen für die Tasks und schließlich im Feld Sender_Task_Array die Taskobjekte selbst. Sobald das Hauptprogramm das begin (Zeile 150) ihres Ausführungsteils erreicht hat, laufen diese Tasks los und warten jeweils auf den Startaufruf (Zeilen 155-159) mit dem ja auch kund getan wird, was die Task abarbeiten soll.
Testergebnis
Soll ich nun zufrieden sein?
Die Sender-Tasks A und B werden sofort gestartet, die Sender-Task C wird interessanterweise erst gestartet, nachdem 18 Meldungen verschickt wurden. Die Prioritäten der drei Sender-Tasks sind (etwas zufällig) niedriger gewählt als die Priorität der Task, die die Meldungen priorisiert weiter schickt.
Es sind anfänglich 2 Meldungen in den Warteschlangen, es wird zuerst die URGEND-Meldung gesendet und dann die NORMAL-Meldung:
## Test_Priority_Controller ...
#> Controller starting ...
## Sender starting A
## Sender starting B
#> Receiving first NORMAL
#> Receiving all URGEND
#> Get queue in all is empty
#> Servicing queue URGEND
#> Servicing data URGEND
## Sending URGEND
**********
#> Get queue in all is empty
#> Servicing queue URGEND
#> Request queue is empty URGEND
#> Servicing queue NORMAL
#> Servicing data NORMAL
## Sending NORMAL
**********
Die eingehende NORMAL-Meldung wird gesendet, da die URGEND-Warteschlange leer ist:
#> Receiving first NORMAL
#> Get queue in all is empty
#> Servicing queue URGEND
#> Request queue is empty URGEND
#> Servicing queue NORMAL
#> Servicing data NORMAL
## Sending NORMAL
123 |
Ich behandele eine DROP-Meldung wie die anderen Meldungen, die weiter geschickt werden. Eine eingehende DROP-Meldung wird daher erst dann verarbeitet (unterdrückt), wenn die URGEND- und NORMAL-Warteschlangen leer sind:
#> Receiving first DROP
#> Get queue in all is empty
#> Servicing queue URGEND
#> Request queue is empty URGEND
#> Servicing queue NORMAL
#> Request queue is empty NORMAL
#> Servicing queue DROP
#> Servicing data DROP
## NOT Sending DROP
Quellcode
Hinweise: Wenige Anweisungen sind dem Standard Ada 2005 entlehnt, der Rest ist Ada 1995. Die Zeilennummern stimmen nicht mit denen in den obigen Code-Ausschnitten überein.
• Der Quellcode, gezippt Mein GNAT-Projekt zum Weitermachen
Ada-Compiler
• GNAT-Ada-Compiler von AdaCore
Literatur
Das gute, alte Buch
John Barnes
Programming in Ada 2005
Addison-Wesley, 2006
Alan Burns, Andy Wellings
Concurrent and Real-Time Programming in Ada 2005
Cambridge University Press, 2007
Norman H. Cohen
Ada as a second language
- based on Ada 95
The McGraw-Hill Companies, 1996