Sudoku oder doch lieber Ada?

Nein, kein Sudoku-Rätsel zum Zeit­ver­treib! Fürs Geo-Caching habe ich zwei selbst ge­löst, für das dritte, das schwie­ri­ge, hatte ich zu­fäl­lig ein Forth-Pro­gramm und da­mit die Lösung in der Hand ...

Meine kleine, selbstgestellte Aufgabe: Ein Software-System hat sich über die Jah­re mun­ter wei­ter entwickelt, etliche Mel­dungen sind hin­zu­ge­kom­men. Nun stel­len die An­wen­der fest, dass unter Um­ständen die wich­ti­gen Mel­dun­gen zu spät beim Empfänger ankommen oder et­wa auch in der Mel­dungs­flut un­ter­ge­hen.

Die Meldungen sollen daher (vielleicht nur in be­stimm­ten Be­triebs­mod­i) prio­ri­täts­ge­steu­ert ge­sen­det werden.

Was soll der Baustein tun?

Nun denn, liegt eine 'wichtige' Meldung vor, so soll diese vor al­len an­der­en ge­sen­det wer­den, zudem sollen 'un­wich­ti­ge' Meldungen unterdrückt werden.

Wie gestalte ich den Baustein?

Ich möchte den Baustein gerne un­ab­hän­gig von der vorhandenen Soft­ware ent­wickeln und testen. Ein generisches Pa­ket liegt also nahe:

Die Zeilen 2 bis 10 umfassen die ge­ne­ri­sche Schnittstelle, hier sind das 2 ge­ne­ri­sche Typen und eine generische Pro­ze­dur - diese müssen alle bei der Aus­prä­gung (oder Instantiierung) des ge­ne­ri­schen Pakets durch kon­kret Ty­pen und Pro­ze­du­ren ersetzt werden.

Data_Priority_Type (Zeile 4) ist ein Auf­zäh­lungstyp, er stellt den Satz der Prio­ri­tä­ten bereit. Data_Type (Zeile 8) steht für den Meldungstyp, des­sen Struk­tur nicht offen gelegt ist (daher private), tagged bedeutet, dass der Typ klas­sen­ar­tig hierachisch aufgebaut ist. Handler (Zeile 10) ist die ge­ne­ri­sche Pro­ze­dur für die prioritätsgesteuerte Verarbeitung der Meldungen, von ihr ist nur die Pro­ze­dur­schnitt­stel­le bekannt.

Die Zeilen 13-15 stellen die eigentliche Schnittstelle des Paketes (Pa­ket­spe­zi­fi­ka­tion) dar, hier sind das 2 Prozeduren. Mittels Start wird ei­ne pa­ket­in­ter­ne Task gestartet und mittels Get kann das Pa­ket mit Meldungen versorgt werden.

Wie sieht die Algorithmik aus?

In etwa so, in Pseudo-Code formuliert:

Was leistet Ada für die Kodierung?

Zwei Sprachkonstrukte bieten sich als Vehikel der Im­ple­men­tie­rung an: (ne­ben­läu­fi­ge) Tasks oder geschützte Typen (protected types). Ich wäh­le das Task-Kon­strukt und den requeue-Me­cha­nis­mus.

Hinweis: Da, wo im Ada-Quelltext ein '+' rechts ne­ben der Zei­len­num­mer steht, ist der Code zu­sam­menge­faltet.

Die Task Controller im Rumpf des Pa­ke­tes Ge­ne­ric_Prio­ri­ty_Con­trol­ler weist 2 öffentliche Eingänge Start und Get (Zeilen 12-13) auf und eine private Ein­gangs­familie Request­(Data­_Priority­_Type) (Zei­len 18-21); für je­den Wert des Auf­zäh­lungs­ypes Data­_Priority­_Type gibt es einen ei­ge­nen Ein­gang. Je­der einzelne Task-Eingang ist mit ei­nem FIFO-Puffer verknüpft.

Im Rumpf (body) der Task wird das Ab­lauf­verhalten der Task im­ple­men­tiert, hier wartet die Task nach der Ak­ti­vie­rung an der accept-Anweisung Start (Zei­le 29) bis ein externer Programmteil (mittelbar) den Task-Eingang Start (Zei­le 12) aufruft und damit ein Rendezvous eingeht. Danach durchläuft die Task die Schleife Outer (Zeilen 31-85).

Der Zähler Total gibt an, wieviele Meldungen die Task aktuell verwaltet. Ist kei­ne interne Meldung da, wartet die Task an der accept-Anweisung Get (Zei­le 39) auf eine eingehende Meldung; geht eine sol­che ein, wird sie dem Ein­gangs­puf­fer ent­nom­men und innerhalb des Ren­dez­vous' in einem der re­queue-Eingänge ent­spre­chend der Prio­rität ab­ge­legt.

Nun wird die innere Schleife More­_En­try­_Calls (Zeilen 50-63) so­lan­ge durch­lau­fen, bis der Ein­gangs­puffer mittels der accept-Anweisung Get (Zeile 54) ge­leert ist; ist der Puffer leer, wird die else-Anweisung Zeile 59 an­ge­sprun­gen, wonach mit der exit-Anweisung Zeile 60 die in­ne­re Schlei­fe verlassen wird.

In der inneren Schleife Se­rvi­cing­_Re­quests (Zeilen 67-83) wird nun in der Pri­o­ri­tät absteigend über die Puffer der Request­-Eingänge (Zeile 71) ite­riert - wird bei einem Schlei­fen­durch­lauf eine Meldung ge­funden, wird die Hand­ler-Pro­ze­dur aufgerufen und anschließend die innere Schleife ver­las­sen, um nach neuen Meldungen zu schauen; wird im Puffer kei­ne Mel­dung ge­fun­den, wird auch nichts un­ter­nommen (Zeilen 79-80).

Was für eine lästige Angelegenheit!

Ich wollte eigentlich Zusicherungen (as­ser­tions) und viel­leicht neue Sprach­mit­tel von Ada 2015 (Vor­be­din­gungen, Nach­bedin­gungen, etc) ver­wen­den, um den Test etwas Formaler zu gestalten. Doch bei den ersten wei­ter­ge­hen­den Test­läufen, die schon mehr einen Nachweis-Charakter ha­ben soll­ten, gab es Irritationen: Die innere Schleife Mo­re­_Entry_Calls wur­de an­fänglich nie durch­laufen, es gab immer nur einen Eintrag im Ein­gangs­puf­fer, obwohl ich in der Test­prozedur sequen­tiell Mel­dungen bereit­gestellt hatte. Ich habe also doch Text­ausgaben einge­streut, um das Ver­hal­ten zu verstehen ...

Und ich habe ein Feld von Tasks im­ple­mentiert, um den Ein­gangs­puf­fer hin­rei­chend zu füllen. Aber zu­nächst zu den Test­meldungen ...

Die Prozeduren Send (Zeilen 12, 18) machen hier einfach Text­aus­ga­ben, im­ple­mentiert im Rumpf des Paketes.

Zum Testprogramm! Um das generische Paket Ge­ne­ric_Prio­ri­ty_Con­trol­ler aus­prä­gen zu können, be­nö­tige ich noch Prio­ritäten und eine kon­kre­te Han­dler-Prozedur. Die Pri­o­ri­täten werden durch Mes­sage_Prio­rity_Type (Zei­le 12) und die Pro­zedur durch Send_With_Priority (Zeilen 16-23) be­reit­ge­stellt. Ei­ne In­stanz Pctr des gene­rischen Paktes wird durch die Zeilen 25-28 be­reit­ge­stellt.

Ich möchte einen Satz von (ne­ben­läu­fi­gen) Tasks ha­ben, die je­weils se­quen­tiell Mel­dungen be­reit­stel­len. Dazu de­fi­nie­re ich zunächst eine Zu­griffs­typ (Zei­ger) Send­_Pro­ce­du­re­_Access­_Type (Zei­le 37) auf ei­ne pa­ra­me­ter­lo­se Pro­ze­dur.

Der Task-Typ Sender_Task_Type (Zei­len 41-67) hat einen Taskeingang Start (Zeilen 42-44, Im­ple­men­tievrung 54-59); mit dem Ein­gangs­aufruf wird auch ein 'Zeiger' (Zugriff) auf die Prozedur, etwa Send1_Procedure über­geben, die das Task­objekt aus­führen (Zeile 63) soll.

Nun braucht es nur noch 3 Felder und schon kann es mit dem Testen los­ge­hen.

Im Feld Send_Procedure_Access_Array (Zeilen 135-139) sind die Zeiger auf die aus­zu­füh­ren­den Pro­ze­duren zu­sam­men­ge­fasst, im Feld Sen­der­_Task­_Id­_Array (Zeilen 145-146) die Kennzeichen für die Tasks und schließlich im Feld Sen­der­_Task­_Array die Task­objekte selbst. Sobald das Haupt­programm das begin (Zeile 150) ihres Aus­füh­rungs­teils er­reicht hat, laufen diese Tasks los und war­ten jeweils auf den Start­aufruf (Zei­len 155-159) mit dem ja auch kund getan wird, was die Task abarbeiten soll.

Soll ich nun zufrieden sein?

Die Sender-Tasks A und B werden sofort ge­star­tet, die Sender-Task C wird in­te­res­san­ter­wei­se erst ge­star­tet, nachdem 18 Meldungen ver­schickt wur­den. Die Pri­oritäten der drei Sender-Tasks sind (etwas zufällig) nie­dri­ger ge­wählt als die Priorität der Task, die die Meldungen pri­o­risiert weiter schickt.

Es sind anfänglich 2 Meldungen in den War­te­schlan­gen, es wird zuerst die UR­GEND-Meldung ge­sen­det und dann die NORMAL-Meldung:

Die eingehende NORMAL-Meldung wird gesendet, da die UR­GEND-War­te­schlan­ge leer ist:

Ich behandele eine DROP-Meldung wie die anderen Mel­dun­gen, die wei­ter ge­schickt werden. Eine ein­ge­hen­de DROP-Meldung wird daher erst dann ver­ar­bei­tet (un­ter­drückt), wenn die URGEND- und NOR­MAL-War­te­schlan­gen leer sind:

Hinweise: Wenige Anweisungen sind dem Stan­dard Ada 2005 entlehnt, der Rest ist Ada 1995. Die Zei­len­num­mern stimmen nicht mit denen in den obi­gen Code-Ausschnitten überein.

•  Der Quellcode, gezippt     Mein GNAT-Projekt zum Weiter­machen

•  GNAT-Ada-Compiler        von AdaCore

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