Prof. Dr. R. Laue                                                                                                                   WS9900
Informatik I
Übungsblatt 12
Abgabe: 15.2.00 vor der Vorlesung

URL:        /axel/informatik1_ws9900_blatt12.html
Dieses Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt bitte den Übungsgruppentag angeben. Um den Übungsschein zu erhalten, muß man 50% der Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.

Aufgabe 32 -  Benes (3+3+4 Punkte)

a) Man berechne für das Benes Permutationsnetz mit 2n Eingängen die Anzahl der möglichen Kombinationen von Schalterstellungen.
b) Zeigen Sie, daß diese Anzahl für Netze mit mehr als zwei Eingängen größer ist als die Anzahl der möglichen Permutationen der Eingabedaten.
c) Wieviele Schritte sind beim Benes Netz mit m = 2n Prozessoren höchstens nötig um eine Information vom Prozessor i zu einem Prozessor j zu senden. Die vorherige Berechnung der Schalterstellung bleibt dabei unberücksichtigt.

Aufgabe 33 - Buddy System  (6 Punkte)


Sie haben ein leeres Buddy-System mit einer Gesamtspeicherplatzgröße 29   gegeben. Damit werden folgende Operationen durchgeführt:

a- Anforderung von Speicherplatz der Größe 15
b- Anforderung von Speicherplatz der Größe 40
c- Anforderung von Speicherplatz der Größe 5
d- Anforderung von Speicherplatz der Größe 201
e- Anforderung von Speicherplatz der Größe 8
f - Anforderung von Speicherplatz der Größe 9
g - Freigabe des Speichers aus c
h - Freigabe des Speichers aus e
i -  Freigabe des Speichers aus f
j -  Freigabe des Speichers aus a

Geben Sie die Einträge in den Listen L9 bis L2 nach jedem der Schritte an.  Die Liste Li enthält die Startadressen der freien Blöcke der Größe 2i. Am Anfang steht in Liste L9 also 000000000, die anderen Listen sind leer.