Nachdem Sie nun schon mal einen Prozess via fork() erzeugt haben,
können Sie bestimmt auch mehrere Prozesse erzeugen. Bei elektronischen
Schaltkreisen, wie sie z.B. im Computer vorkommen, findet
wenn möglich Parallelverarbeitung statt, um die Geschwindigkeit zu erhöhen.
Voneinander unabhängige (Teil-)Ergebnisse können hierbei gleichzeitig
berechnet werden. Damit es interessanter wird, befassen wir uns nicht
mit Binärschaltkreisen (d.h. in den Leitungen ,,fließen`` 0en und 1en),
sondern mit Integer-Schaltkreisen (d.h. die Leitungen führen Integer-Werte).
Hierbei verwenden wir nur zwei verschiedene Gatter-Typen, nämlich
Minimum-
und
Maximum-Gatter. (Ein Minimum-Gatter berechnet das Minimum seiner beiden
Eingaben und liefert dieses auf der Ausgabeleitung. Analog dazu funktioniert
ein Maximum-Gatter.) Mit diesen beiden Gattern kann man ein
Vergleichs-Gatter
(,,compare``) wie folgt simulieren (Vergleichs-Gatter links und Simulation
des Gatters rechts):
Ein Schaltkreis besitzt Eingaben, Ausgaben und Gatter. Jedes Gatter (wir betrachten nur min- und max-Gatter) besitzt genau zwei Eingänge und genau einen Ausgang. Die Eingaben und die Gatter werden eindeutig durch jeweils eine ganze Zahl beschrieben (die Zahlen für die Eingaben und für die Gatter sind voneinander verschieden). Die Eingaben sind mit einem (oder mehreren) Eingängen eines Gatters verbunden. Die Ausgabe eines Gatters kann mit dem Eingang eines (oder mehrerer) Gatter verbunden werden. Die Ausgaben sind schließlich Ausgängen von Gattern oder Eingaben. Eine wesentliche Eigenschaft von Schaltkreisen ist, dass keine Zyklen vorkommen. (Man kann z.B. nicht den Ausgang eines Gatters mit dessen Eingang verbinden.)
Ihre Aufgabe ist es, ein C-Programm zu schreiben, das einen gegebenen Schaltkreis auswertet. Hierzu erhält das Programm als einziges Kommandozeilen-Argument den Namen einer Datei. Aus dieser Datei liest es die Beschreibung des Schaltkreises (deren Aufbau folgt noch). Nun erzeugt es für jede Eingabe eine Datei, deren Name der Nummer dieser Eingabe entspricht1 und die den Wert dieser Eingabe enthält. Dieser Wert soll für jede Eingabe zuvor von der Standardeingabe gelesen werden. Danach erzeugt es für jedes Gatter einen Prozess, der wartet bis alle Eingabedateien existieren und danach eine Ausgabedatei mit der Nummer des Gatters2erzeugt, die den berechneten Wert enthält, und terminiert. Zum Schluss (d.h. wenn die Dateien für alle Ausgaben existieren und etwas enthalten) soll noch für jede Ausgabe deren Wert auf die Standardausgabe geschrieben werden. Außerdem sollen noch alle erzeugten Dateien gelöscht werden.
In der Eingabedatei steht zunächst eine ganze Zahl 
, die die Anzahl der
Eingaben des Schaltkreises angibt. Danach
folgen3 ganze Zahlen, die
die eindeutigen Nummern der Eingaben angeben. Dann kommt die Zahl 
der
Ausgaben des Schaltkreises gefolgt von ganzen Zahlen, die die Nummern
dieser Ausgaben
repräsentieren (dabei handelt es sich jeweils um die Nummer eines Gatters
oder die Nummer einer Eingabe). Dann folgt eine ganze Zahl 
, die der
Anzahl der Gatter des Schaltkreises entspricht. Für jeden der Schaltkreise
folgt dann eine ganze Zahl (die eindeutige Nummer des Gatters),
ein String (der Gattertyp, d.h. ,,min`` oder ,,max``) und zwei ganze
Zahlen (die Nummern der Eingaben; das sind Nummern von Eingaben des
Schaltkreises oder anderen Gattern).
Beispiel:
Im folgenden ist ein Schaltkreis dargestellt, der die vier Zahlen aus der
Eingabe in sortierter Reihenfolge ausgibt. (Die Nummer eines Gatters steht
in folgendem Bild jeweils an der Ausgabeleitung.)
4 1 2 3 4 4 11 12 13 14 10 5 min 1 2 6 max 1 2 7 min 3 4 8 max 3 4 11 min 5 7 9 max 5 7 10 min 6 8 14 max 6 8 12 min 9 10 13 max 9 10
Zum Üben erhalten Sie Schaltkreisbeschreibungen für das Sortieren von 2 Zahlen, das Sortieren von 3 Zahlen, das Sortieren von 4 Zahlen, die Bestimmung des Medians von 3 Zahlen und die Berechnung des Maximums von 8 Zahlen.
Wichtiger Hinweis: Damit Sie Turing, Thales, etc. nicht durch
eine Prozesslawine bedrohen, sollten sie ihr Programm nur auf der lokalen
Workstation laufen lassen und nicht via ssh auf Turing, ...! Wenn
Sie Ihr Programm testen, sollten Sie auch mit ps -u<loginname> überwachen,
ob Sie evtl. ungewollt Prozesse erzeugen. Eine Prozesslawine auf einem
Rechner kann über das neue Kommando killflood cmd beendet werden
(man killflood).
Dazu sollten Sie immer ein zweites Terminal-Fenster auf diesem
Rechner offen haben.
Lösung:
/* Systemnahe Software (Teil 2)
* Sommersemester 2001
* Blatt 2
* Beispielloesung
* Johannes Mayer, 26.4.2001
*/
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/stat.h>
#include <errno.h>
#include <stdio.h>
/* alle moeglichen Gattertypen */
#define F_MIN 0
#define F_MAX 1
/* Praefix fuer alle Dateinamen zur IPC */
#define IPC_PREFIX "gates_ipc"
#define MAXIN 10
#define MAXOUT 10
#define MAXGATE 20
#define MAXGIN 2
int main(int argc, char **argv) {
FILE *fp, *fp1;
int i, j, k = 0;
struct stat statbuf;
char s[80];
int inputCount, outputCount, gateCount;
int inputNum[MAXIN], outputNum[MAXOUT];
int inputValue, outputValue;
int gateNum, gateFun, gateInputCount, gateInputNum[MAXGIN];
int gates[MAXGATE];
if (argc != 2) {
printf("Usage: %s <input file>\n", argv[0]);
exit(1);
}
if (! (fp = fopen(argv[1], "r"))) {
perror(argv[1]);
exit(1);
}
/* aus der Beschreibungsdatei die Anzahl der Eingaben
* und deren Nummern einlesen
*/
fscanf(fp, " %d ", &inputCount);
for (i = 0; i < inputCount; i++)
fscanf(fp, " %d ", &inputNum[i]);
/* Eingaben von der Standardeingabe lesen und in
* die jeweiligen Dateien schreiben (damit sie von den Kindprozessen
* gelesen werden koennen)
*/
for (i = 0; i < inputCount; i++) {
printf("Eingabe %d: ", inputNum[i]);
fgets(s, sizeof(s), stdin);
sscanf(s, " %d ", &inputValue);
sprintf(s, "%s%d", IPC_PREFIX, inputNum[i]);
if (! (fp1 = fopen(s, "w"))) {
perror(s);
exit(1);
}
fprintf(fp1, "%d", inputValue);
fclose(fp1);
}
/* aus der Beschreibungsdatei die Anzahl der Ausgaben
* und deren Nummern einlesen
*/
fscanf(fp, " %d ", &outputCount);
for (i = 0; i < outputCount; i++)
fscanf(fp, " %d ", &outputNum[i]);
/* aus der Beschreibungsdatei zunaechst die Anzahl der
* Gatter und danach die Beschreibung fuer jedes einzelne
* Gatter einlesen und pro Gatter einen Prozess erzeugen,
* der das Ergebnis dieses Gatters berechnet und in eine
* eigene Datei schreibt
*/
fscanf(fp, " %d ", &gateCount);
for (i = 0; i < gateCount; i++) {
/* Nummer des Gatters einlesen */
fscanf(fp, " %d %s ", &gateNum, s);
gates[k++] = gateNum;
/* Typ des Gatters einlesen und Anzahl der
* notwendigen Eingaben berechnen
*/
if (! strcmp(s, "min")) gateFun = F_MIN, gateInputCount = 2;
else if (! strcmp(s, "max")) gateFun = F_MAX, gateInputCount = 2;
else {
printf("Unknown gate type: %s\n", s);
exit(1);
}
/* Nummern der Eingabegatter einlesen */
for (j = 0; j < gateInputCount; j++)
fscanf(fp, " %d ", &gateInputNum[j]);
/* Puffer vor dem Forken noch mal leeren ...
* (tueckische Fehlerquelle!!!)
*/
fflush(stdout);
switch (fork()) {
case 0:
/* Kindprozess */
fclose(fp);
{
int in[MAXGIN], out;
/* die Ergebnisse der Eingabegatter
* von den jeweiligen Dateien
* einlesen
*/
for (i = 0; i < gateInputCount; i++) {
sprintf(s, "%s%d", IPC_PREFIX, gateInputNum[i]);
/* solange warten, bis die
* Datei existiert und mindestens
* ein Zeichen enthaelt
*/
while (stat(s, &statbuf) < 0
|| statbuf.st_size == 0
|| ! (fp = fopen(s, "r")));
fscanf(fp, " %d ", &in[i]);
fclose(fp);
}
/* Gatterfunktion berechnen */
switch (gateFun) {
case F_MAX:
out = in[0] >= in[1] ? in[0] : in[1];
break;
case F_MIN:
out = in[0] <= in[1] ? in[0] : in[1];
break;
default:
puts("Unknown gate type");
exit(1);
}
/* Ergebnis des Gatters in
* die zugehoerige Datei schreiben
*/
sprintf(s, "%s%d", IPC_PREFIX, gateNum);
if (! (fp = fopen(s, "w"))) {
perror(s);
exit(1);
}
fprintf(fp, "%d", out);
fclose(fp);
}
exit(0);
break;
case -1:
perror("fork()");
exit(1);
default:
/* Elternprozess */
/* => macht einfach weiter in der
* for-Schleife mit der naechsten
* Gatterbeschreibung
*/
}
}
fclose(fp);
/* warten bis alle erzeugten Prozesse terminiert sind
* koennte man mit wait jetzt wie folgt:
* while (wait(&i) >= 0 || errno == EINTR);
* (war aber in der Vorlesung noch nicht dran - faellt also weg)
*/
puts("----------------------------------");
/* Ausgaben aus den (von den Kindprozessen erzeugten)
* Dateien lesen und auf die Standardausgabe schreiben
*/
for (i = 0; i < outputCount; i++) {
printf("Ausgabe %d: ", outputNum[i]);
sprintf(s, "%s%d", IPC_PREFIX, outputNum[i]);
/* solange warten, bis die Datei geoeffnet werden
* kann und auch etwas enthaelt
*/
while (stat(s, &statbuf)
|| statbuf.st_size == 0
|| ! (fp = fopen(s, "r")));
fscanf(fp, " %d ", &outputValue);
printf("%d\n", outputValue);
fclose(fp);
}
/* alle erzeugten Dateien wieder entfernen */
for (i = 0; i < inputCount; i++) {
sprintf(s, "%s%d", IPC_PREFIX, inputNum[i]);
unlink(s);
}
for (i = 0; i < k; i++) {
sprintf(s, "%s%d", IPC_PREFIX, gates[i]);
unlink(s);
}
exit(0);
}