SAI || Sommersemester 1997 || Systemnahe Software II || Übungen

Übungen zu Systemnahe Software II
Blatt 2 (28. 04. - 12. 05. 1997)

Aufgabe 2 (20 Punkte)

Ein Geheimagent erhält während eines Spezialauftrags von Zeit zu Zeit eine Codenummer (eine positive ganze Zahl), von der er sehr schnell feststellen muß, ob sie eine bestimmte Eigenschaft hat. Diese Eigenschaft läßt sich wie folgt charakterisieren: Kann man aus einer bestimmten (fest vorgegebenen) Menge von Zahlen eine Teilmenge in der Weise auswählen, daß die Summe der Elemente gleich der Codenummer ist, dann ist sie erfüllt. Man nennt diese Fragestellung übrigens ein Knapsack-Problem. Glücklicherweise hat der Agent auch mal in einer Universität spioniert und besitzt ein Modula-2-Programm, das dieses Problem lösen kann. Sie finden dieses Programm im folgenden Verzeichnis: 
/www/thales/ftp/pub/vorlesungen/ss97/soft/blatt/2
Ihre Aufgabe besteht nun darin, dem Agenten mit einer verbesserten Lösung unter die Arme zu greifen.

Auf Computern mit mehreren Prozessoren kann man unter Umständen viel Zeit sparen, wenn man langwierige Berechnungen auf mehrere parallele Prozesse verteilt.

Schreiben Sie also eine C-Funktion, die folgende Definition implementiert: 

void multisearch(
        Code code,                      /* code to search for */
        Key min, Key max,               /* search interval */
        Searchfunc search,              /* search function */
        unsigned nproc,                 /* number of subprocesses */
        unsigned timeout);              /* timeout in realtime seconds */
Diese Funktion soll ein gegebenes Suchintervall in mehrere etwa gleich große Teile teilen und für jedes Teilintervall die mitgegebene Funktion search in einem separaten Kindprozeß ausführen. Das Ergebnis wird einfach auf die Standardausgabe ausgegeben. Sobald eine Suche in einem Teilbereich erfolgreich ist, sollen alle anderen Prozesse abgebrochen werden. Wenn kein Aufruf der Suchfunktion ein Ergebnis erbringt, soll der Vaterprozess einfach auf das Ende der Kinder warten. Zur Sicherheit sollen nach einer in Sekunden angegebenen Zeitspanne auf jeden Fall ebenso alle Prozesse abgebrochen werden.

Koppeln Sie diese Funktion mit einer geeigneten Fassung des Knapsack-Problems (mit derselben Zahlenmenge wie im Modula-Programm) in C und einem Hauptprogramm, das folgendermaßen aufzurufen ist: 

Usage: a.out code processes timeout
Modularisieren Sie das Programm zu verschiedenen Quelldateien (insbesondere sollte multisearch separat implementiert werden) und schreiben Sie ein Makefile für Übersetzung und Zusammenbau des Programms.

Testen Sie Ihr Programm mit folgenden Codenummern: 

59946459
81761365
38886333
Im angegebenen Katalog befindet sich auch eine Demo-Version des Programms.
SAI || Sommersemester 1997 || Systemnahe Software II || Übungen
Martin Hasch, April 1997