Inhalt
Sieben | Das Sieb des Eratosthenes |
Konzept | Wie könnte man das angehen? |
Ada (1) | Vom Hirn in die Hand |
Ada (2) | Noch einmal nachgedacht |
Ergebnis | Es funktioniert, im Prinzip |
Wettrennen | Es funktioniert? Aber ... |
Quellcode | Zum Weiter machen |
Compiler | Das perfekte Werkzeug |
Literatur | Das gute, alte Buch |
Sieben
Das Sieb des Eratosthenes
Eine ungerade ganze Zahl N ist eine Primzahl, wenn sie nicht durch ihre ungeraden Vorgänger {3,5,..,N-2} teilbar ist. Dazu eine Ada-Spielerei als schierer Selbstzweck.
Es soll hier nicht etwa ein neuer Primzahlzwilling gefunden werden - nein, es soll schlicht der obige Algorithmus mit Sprachmitteln der Programmiersprache Ada modelliert werden - wie gesagt, der schiere, aber schöne Selbstzweck.
Konzept
Wie könnte man das Problem elegant angehen?
Eleganz schließt hier aber auch die praktische Nutzlosigkeit ein, denn für wenig Rechnerei wäre der Verwaltungsaufwand doch erheblich - nichts destotrotz!
Eine zu überprüfende Zahl N wird durch eine Ketvte von Tasks geschickt, je eine Task für je eine Primzahl, wobei jede Task überprüft, ob die eingegangene Zahl ein Vielfaches der eigenen Primzahl ist; ist sie das, wird die eingegangene Zahl verworfen und die nächste Zahl entgegen genommen; ist sie kein Vielfaches, wird sie an die nächste Task weitergereicht. Die Tasks filtern oder eben sieben also den eingehenden Strom an Zahlen.
Die Kette wird aufgebaut, indem mit den Zahlen 3,5,7,9,.. begonnen wird. Die Task am jeweiligen Ende der Kette erzeugt dynamisch eine weitere Task für die nächste Primzahl mit einem zugehörigen Puffer. Als letzte zu überprüfende Zahl wird schließlich die Zahl N in die Rohrleitung ('pipeline') geschickt.
Damit sich das Task-System anständig verabschieden kann, wird eine 0 als Kennzeichen durch die Task-Kette geschickt als Botschaft, dass die Arbeit getan ist und sich die einzelnen Tasks nun verabschieden können.
Ada (1)
Vom Hirn in die Hand
Für die siebenden Tasks wird ein Task-Typ Sieve_Task_Type definiert: Jede Task wird ein Eingangspuffer, der CPU-Kern, auf dem sie ablaufen soll, und die Priorität übergeben.
Sieb-Task-Typ mit Fabrik
Neue Taskobjekte werden mittels einer task-externen Funktion (Zeilen 58-59) erzeugt ('Taskfabrik'). Im Taskrumpf selbst können neue Taskinstanzen nicht direkt mittels eines 'new Sieve_Task_Type' dynamisch erzeugt werden ("task type cannot be used as type mark within its own spec or body").
Im Rumpf des Task-Typen wird gleich ein Ausgangspuffer bereitgestellt, der auch Eingangspuffer für das nächste, noch zu erzeugende Taskobjekt sein wird.
Die allererste Zahl, die eine Sieb-Task dann aus dem Input_Buffer (Zeile 15) erhält, ist ihre 'eigene' Primzahl.
Rumpfteil (1) der Sieb-Task
Wird nun die nächste Primzahl gefunden, so wird sogleich eine neue Task erzeugt (Zeile 56) und dabei der neuen Task der Eingangspuffer mit übergeben - der Ausgangspuffer der aktuellen Taskinstanz ist der Eingangspuffer der nächsten Task in der Task-Kette.
Die neue Task erhält auch sogleich ihre eigene Primzahl (Zeile 58) über den Ausgangspuffer mitgeteilt.
Rumpfteil (2) der Sieb-Task
Anschließend werden neue Zahlen zur Überprüfung entgegen genommen (Zeile 63). Falls eine 0 dabei ist, wird aus der Schleife ausgestiegen (Zeile 65). Die Überprüfung findet in Zeile 67 statt. Primzahl-Kandidaten werden in der Zeile 70 weitergereicht.
Ada (2)
Noch einmal nachgedacht
Eine spannende Geschichte - viel besser als Sudoku. Solch eine siebende Task und der ihr zugeordnete Ausgangspuffer gehören eigentlich zusammen - könnte man meinen. Ich habe die beiden zu einem Kettenglied ('chain member') zusammengefasst. Die Kettenglieder werden dann mittels Zeiger (in Ada-Sprache: über Zugriffstypen) zu einer Kette verbunden:
Der Behälter für die Task und den Puffer
Die Task und der Puffer werden zu einem Verbund-Typen, zu einem Record, namens Sieve_Chain_Member_Type zusammengefasst. Die Datenstruktur referenziert sich selbst, da der Task ein Zeiger auf den Behälter mittels einer Diskriminante übergeben wird. Ein nützliches Konstrukt!
Auf die Puffer kann auf zweierlei Weise zugegriffen werden: Die aktuelle Task greift über den Zeiger Chain_Member auf ihren Eingangspuffer zu, die Task, die diesen Behälter erzeugt, verwendet einen Zeiger auf diesen Behälter, um Zugriff auf den Ausgangspuffer zu erhalten.
In der Anwendung sieht das dann mit den Zeile 61 und 67 so aus:
Der innere (Zeile 61) und der äußere Zugriff (Zeile 67)
Ergebnis
Es funktioniert, ja im Prinzip
Für N=2*6400 klappte das Programm auf meinem Vier-Kern-Rechner noch, bei N=3*6400 stieg es aus. Ich habe nur die Primzahlzwillinge auf die Konsole ausgegeben:
Primzahlzwillinge (Ausschnitt)
Wettrennen
Es funktioniert? Ja, aber ...
Eine neue Erfahrung für mich: Während der Entwicklung stieg das Programm des öfteren gleich nach dem Starten aus - offensichtlich kann es leicht zu 'Wettrennbedingungen' (race condition) kommen, dann steht eine Ressource noch nicht zur Verfügung, wenn sie benutzt werden soll. Solche Wettrennen traten etwa auf, wenn man ein Sieb-Taskobjekt gleich im Deklarationsteil erzeugte.
Oder: Am Ende aller Konsolenausgaben sollten die Sieb-Tasks einmal die Meldung ausgegeben, der Benutzer möge bitte den Wagenrücklauf auslösen. Dazu habe ich eine globale atomare Variable Done spendiert, die nach der ersten Meldungsausgabe auf False wird, womit weitere Ausgaben unterbleiben sollten. Nun denn: Anfänglich gab es genau 2 Ausgaben.
Quellcode
Hinweis: Die Zeilennummern stimmen nicht unbedingt mit denen in den obigen Code-Ausschnitten überein.
• Der Quellcode, gezippt Mein GNAT-Projekt (1)
• Der Quellcode, gezippt Mein GNAT-Projekt (2)
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
Dank an die drei Herren!