Guido Krüger's Web Service

Programming Asssignments 7 - 10

(This page is available in German only. )

Aufgaben zu den Kapiteln 7 bis 10

1. [A] (Definition der Vererbung). Definieren Sie den Begriff der Vererbung. Unterscheiden Sie anschließend zwischen Einfachvererbung und Mehrfachvererbung und geben Sie jeweils ein Beispiel für ihre Anwendung. Positionieren Sie das Konzept der Interfaces zwischen Einfach- und Mehrfachvererbung.

2. [A] (Definition Polymorphismus und Late Binding). Definieren Sie die Begriffe Polymorphismus und Late Binding.
Aufg0702.java

3. [A] (Typkompatibilität von Klassen). Beschreiben Sie die Typkompatibilät verschiedener Klassen und erläutern Sie, welche Konvertierungen zwischen ihnen anwendbar sind. Beschreiben Sie, warum diese Typkonvertierungen der Schlüssel zur Anwendung des Polymorphismus sind.

4. [A] (Laufzeitfehler). Geben Sie ein Beispiel für ein Programm, das einen Laufzeiterfehler auslösen kann (und wird), das aber auch ohne explizite Ausnahmebehandlung vom Compiler übersetzt wird. Erweitern Sie das Programm um eine geeignete Ausnahmebehandlung und demonstrieren Sie an einem Beispiel das Auftreten des Fehlers.

5. [A] (Statische Methoden). Beschreiben Sie die Analogie zwischen statischen Methoden in Java und globalen Funktionen in konventionellen Programmiersprachen. Wo liegen die Gemeinsamkeiten, wo die Unterschiede?

6. [A] (Ein häufig auftretender Fehler). Das nachfolgende Listing zeigt die Datei "Hello.java", die das weiter oben vorgestellte "Hello, world"-Programm enthält. Leider enthält das Programm einen gravierenden (und sehr häufig gemachten) Fehler, der es unkompilierbar macht. Worin besteht dieser Fehler? 

public class hello
{
   public static void main(String args[])
   {
      System.out.println("Hello, world");
   }
}

7. [A] (Potenz berechnen). Schreiben Sie eine nicht-rekursive Methode power, die zwei Ganzzahlen x und y akzeptiert und die Potenz xy berechnet.
Aufg0707.java

8. [A] (Potenz berechnen, rekursive Version). Schreiben Sie eine rekursive Variante der Methode power analog der vorigen. Diese Methode soll keine expliziten Schleifen verwenden, sondern das Ergebnis durch rekursiven Aufruf von sich selbst ermitteln.
Aufg0708.java

9. [A] (Exceptions). Schreiben Sie ein Programm, das ein vorgegebenes Array in einer while-Schleife durchläuft. Anstatt die Länge des Arrays als Abbruchbedingung der Schleife zu verwenden, soll die Schleife solange laufen, bis eine Ausnahme des Typs ArrayIndexOutOfBoundsException erzeugt wird. Beschreiben Sie, ob Sie die hier praktizierte Verwendung des Ausnahmemechanismus für sinnvoll halten.

10. [B] (Objekt-Tracking). Angenommen, Sie wollen ein sehr großes Programm schreiben und interessieren sich aus Performancegründen für die konkrete Objektstruktur ihres Programmes zu einem beliebigen Zeitpunkt zur Laufzeit des Programms. Überlegen Sie sich ein einfaches Verfahren, mit dem Ihr Programm zur Laufzeit den Namen und die Anzahl von Objekten anwendungsspezifischer Klassen ermitteln kann. Funktioniert Ihr Verfahren auch für Objekte, die aus vordefinierten Klassen des JDK oder aus davon abgeleiteten Klassen instanziert wurden?

11. [B] (Pakete). Kapitel 8 erklärt die Verwendung von Paketen und weist auf die Konventionen bei der Vergabe von Paketnamen hin. Überlegen Sie sich ein Verfahren, alle ihre zukünftigen Klassen und Pakete abzulegen, das an dieses Schema angelehnt ist. Beschreiben Sie die Struktur ihrer Paketnamen, die zugehörige Verzeichnisstruktur und Veränderungen an Umgebungsvariablen (wie beispielsweise der CLASSPATH-Variablen). Sorgen Sie dafür, daß Ihre Struktur das Aufrufen und Einbinden Ihrer .class-Files aus jedem anderen Verzeichnis erlaubt.

12. [B] (Oktalzahlen ausgeben). Schreiben Sie eine Methode toOctalString, die eine als Argument übergebene Ganzzahl in einen Oktalwert verwandelt und als String zurückgibt.

13. [B] (Sortieren eines Arrays). Schreiben Sie eine Methode sort, die ein als Argument übergebenenes Array von Fließkommazahlen aufsteigend sortiert.

14. [B] (Polymorphismus). Polymorphismus ist eines der wichtigsten, aber auch der am meisten verwirrenden Konzepte beim Erlernen der objektorientierten Programmierung. Zusammen mit abstrakten Klassen ergibt sich ein mächtiges Instrumentarium für eine Vielzahl von Anwendungen. Ihre Aufgabe besteht nun darin, ein Programm gemäß der nachfolgenden Spezifikation zu erstellen:


Aufg0714.java

15. [B] (Producer/Consumer). Verändern Sie das Producer-/Consumer-Beispiel aus Kapitel 10 so, daß einem schnellen Produzenten drei relativ langsame Konsumenten gegenüber stehen. Sorgen Sie auch hier für eine korrekte Synchronisierung und beobachten und interpretieren Sie das Verhalten des Programms.

16. [B] (Time). Realisieren Sie eine Klasse Time, die in der Lage ist, eine Uhrzeit, bestehend aus Stunde, Minute und Sekunde, darzustellen. Intern soll die Uhrzeit durch einen einzigen Wert vom Typ int dargestellt werden, der die Uhrzeit in Sekunden speichert. Die Klasse soll folgende Methoden zur Verfügung stellen:

17. [B] (Lineare Liste). In Java werden Objekte als Referenzen gespeichert. Indem innerhalb des Objekts ein Objekt desselben Typs als Verweis auf ein Nachfolger- oder Vorgängerelement gespeichert wird, können verkettete Listen und andere dynamische Datenstrukturen angelegt werden. Die folgenden Klassendefinitionen können beispielsweise dazu verwendet werden, eine lineare Liste beliebiger Objekttypen anzulegen: 

class LinkedListNode
{
   Object element;
   LinkedListNode next;
}

class LinkedList
{
   private LinkedListNode root;
}
Erweitern Sie die Klasse LinkedList um die folgenden Features: Testen Sie Ihre Implementierung, indem Sie eine leere Liste erzeugen und eine Reihe von Ganzzahlen in aufsteigender Reihenfolge einfügen. Geben Sie nun zunächst das erste, dann das zweite und alle weiteren Elemente der Liste aus. Wenn das Programm korrekt arbeitet, werden die Elemente in umgekehrter Reihenfolge erscheinen.
Aufg0717.java

18. [B] (Enumeration). Im Buch wird das Interface Enumeration zur Aufzählung der Elemente einer Kollektion erwähnt. Während die Verwendung der beiden Methoden dieses Interfaces sehr einfach ist (s. auch Kapitel 12), erfordert die Implementierung eines Enumeration-Interfaces einige Überlegeung. Ihre Aufgabe ist es nun, eine einfache Kollektion-Klasse SimpleSet zu entwickeln, die in der Lage ist, beliebige Ganzzahlen zu speichern und folgende Methoden zu implementieren:

Schreiben Sie auch hier ein Testprogramm, an dem Sie die Funktionsfähigkeit Ihres Ansatzes demonstrieren.
Aufg0718.java

19. [B] (Einfaches Matherätsel). Versuchen Sie herauszufinden, welche einfache mathematische Aufgabe durch folgende Methode berechnet wird: 

static long mathPuzzle(int a, int b)
{
    if (b > 0) {
        return mathPuzzle(a, b - 1) + 1;
    } else {
        return a;
    }
}

20. [B] (Maximum bestimmen). Schreiben Sie eine rekursive Methode max, die das größte Element eines vorgegebenen int-Arrays liefert. Sehen Sie den rekursiven Ansatz darin, daß das größte Element eines Arrays entweder dessen erstes Element oder das größte der verbleibenden Elemente ist.
Aufg0720.java

21. [B] (Sortierung eines Arrays ermitteln). Schreiben Sie eine Methode, die herausfindet, ob ein vorgegebenes Array aufsteigend, absteigend, alternierend oder auf keine dieser Arten geordnet ist. Zur Erklärung: ein Array soll dann aufsteigend sortiert sein, wenn keines seiner Elemente kleiner als sein Vorgänger ist. Absteigend sortiert soll es sein, wenn keines seiner Elemente größer als sein Vorgänger ist. Wird die Folge der Elemente abwechselnd größer und kleiner, ist es alternierend sortiert.

22. [B] (Ziffern vertauschen). Schreiben Sie eine Methode swapDigits die drei Argumente long n, int i and int j erwartet. Die Methode soll das i-te und j-te Element innerhalb der Dezimaldarstellung von n vertauschen. Ist beispielsweise n = 1734256, i = 2 and j = 4, dann sollte die Methode den Wert 1437256 zurückgeben. Falls entweder i oder j oder beide außerhalb des Bereichs gültiger Ziffern liegen, sollte die Methde den Wert von n unverändert zurückgeben.
Aufg0722.java

23. [B] (Der universelle NAND-Operator). Java verfügt über die drei logischen Operatoren UND, ODER und NICHT. Damit können alle zusammengesetzten logischen Ausdrücke realisiert werden. Aus der digitalen Schaltungstechnik ist bekannt, daß beliebige logische Ausdrücke auch bereits mit einem einzigen logischen Operator realisiert werden können, beispielsweise dem NAND. Das NAND ist die Negation des UND-Operators, und kann durch folgende Methode nand realisiert werden: 

boolean nand(boolean a, boolean b)
{
  return !(a && b);
}
Schreiben Sie drei Methoden and, or und not, die die entsprechenden logischen Funktionen nachbilden, ohne die eingebauten Operatoren zu benutzen. Statt dessen sollen sie die Aufgabe lediglich durch geschickten Aufruf der Methode nand erledigen.

24. [B] (Fibonacci-Zahlen). Im 19. Jahrhundert untersuchte der italienische Mathematiker Leonardo Fibonacci die Vermehrungsrate bei Kaninchenpopulationen und entdeckte dabei die später nach ihm benannte Fibonacci-Folge, die den Verlauf des Wachstums der Kaninchenpopulation wiederspiegelt. Die Fibonacci-Folge gehorcht einem sehr einfachen Bildungsgesetz. Die ersten beiden Glieder der Folge sind 0 und 1 und alle weiteren Glieder ergeben sich als Summe der beiden vorhergehenden. Damit ergibt sich folgende Zahlenfolge:

F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
usw.

Schreiben Sie eine Methode fibonacci, die die n-te Fibonacci-Zahl berechnet. Wählen Sie dabei anstelle eines iterativen einen rekursiven Lösungsansatz, bei dem für n > 1 ein Aufruf von fibonacci(n) zwei Aufrufe von fibonacci(n-1) und fibonacci(n-2) nach sich zieht. Testen Sie Ihre Lösung für große n. Ist sie effizient? Versuchen Sie abzuschätzen, wie Speicher- und rechenintensiv die rekursive Lösung ist und vergleichen Sie Ihre Beobachtungen mit einer einfachen iterativen Lösung.

25. [C] (Rationale Zahlen). Als rationale Zahlen werden diejenigen Zahlen bezeichnet, die sich als Quotient zweier Ganzzahlen darstellen lassen. So ist beispielsweise 2,5 eine rationale Zahl, denn 2,5 ist gleich 5 / 2. Schreiben Sie eine Klasse RationalNumber, die eine rationale Zahl implementiert. Zähler und Nenner sollen dabei als getrennte Instanzmerkmale vom Typ long gespeichert werden. Implementieren Sie folgende Methoden:

Weiterhin sollen Sie einige Methoden zur Arithmetik rationaler Zahlen implementieren. Schreiben Sie Methoden zur Addition, Subtraktion, Multiplikation, Invertierung und Division von rationalen Zahlen. Die Resultate der Operationen sollten jeweils soweit wie möglich gekürzt werden. Implementieren Sie die Methoden als statische Methoden, übergeben Sie die rationalen Zahlen als Argumente und liefern Sie ein neues Objekt vom Typ RationalNumber als Ergebnis.

26. [C] (Komplexe Zahlen). Realisieren Sie analog zur Klasse RationalNumber eine Klasse ComplexNumber, die sich mit der Darstellung und Arithmetik komplexer Zahlen beschäftigt.

27. [C] (BigInteger). Schreiben Sie eine Klasse BigInteger, die in der Lage ist, große Ganzzahlen in einem 50-elementigen Array von Ziffern zu speichern. Die Klasse sollte sowohl positive als auch negative Zahlen speichern können. Stellen Sie folgende Methoden zur Verfügung:

Schreiben Sie weiterhin eine statische Methode testStub, mit der die korrekte Implementierung der Klasse BigInteger getestet werden kann. Diese Methode sollte eine Reihe von Ganzzahlen erzeugen und darauf verschiedene Additionen und Subtraktionen ausführen. Die Ergebnisse jeder Operation sollten gegen eine analoge, parallel ausgeführte Operation auf den entsprechenden long-Werten getestet werden. Bei Auftreten einer Diskrepanz sollte eine Fehlermeldung ausgegeben werden. Mit diesem Verfahren können zwar nur Werte getestet werden, die klein genug sind, um mit einem long dargestellt zu werden, dies dürfte für unsere Zwecke jedoch genügend Sicherheit geben.
Aufg0727.java

28. [C] (Permutationen). Schreiben Sie eine Methode, die alle n! Permutationen eines n Zeichen langen int-Arrays ausgibt. Zur Erinnerung: als Permutationen bezeichnet man die unterschiedlichen Möglichkeiten, die einzelnen Elemente eines Arrays anzuordnen. Die Permutationen des dreielementigen Arrays (1, 2, 3) sind beispielsweise (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) und (3, 2, 1). Versuchen Sie auch hier einen rekursiven Lösungsansatz.

29. [C] (Interfaces für Funktionszeiger). Einer der Unterschiede zwischen C/C++ und Java ist das Fehlen von expliziten Zeigern. Mit Hilfe von Zeigern auf Funktionen konnten in C/C++ sehr leicht allgemein verwendbare Routinen geschrieben werden, die durch Übergabe eines Zeigers auf eine Callback-Funktion vom Anwender weitreichend konfiguriert werden. Glücklicherweise gibt es in Java eine einfache und typsichere Möglichkeit, die Übergabe von Funktionen an ein Objekt mit Hilfe von Interfaces nachzubilden.

Schreiben Sie dazu ein Programm, das eine Liste von Funktionsargumenten und ihre Anwendung auf eine beliebige Funktion in tabellarischer Form ausgibt. Die Funktionen sollen einen einzelnen Fließkommawert als Argument akzeptieren, eine wohldefinierte Berechnng darauf ausführen und als Ergebnis einen Fließkommawert zurückgeben. Ihr Programm soll für eine beliebige Funktion die Ergebnisse für die Argumente 1.0, 2.0, 3.0, ... 10.0 berechnen und zusammen mit dem Argument in einer Tabelle ausgeben.

Berechnet die Funktion beispielsweise das Quadrat einer Zahl, so könnte die Ausgabe wie folgt aussehen: 

    x        f(x)
-----------------
  1.0       1.0
  2.0       4.0
  3.0       9.0
  4.0       16.0
  5.0       25.0
  6.0       36.0
  7.0       49.0
  8.0       64.0
  9.0       81.0
 10.0       100.0
Realisieren Sie das Programm entsprechend den folgenden Vorgaben:

30. [C] (Geschachtelte Schleifen durch Rekursion ersetzen). Eine etwas umständliche Variante, von 0 bis 999 zu zählen, besteht darin, drei ineinander geschachtelte for-Schleifen zu verwenden, in der die Einer-, Zehner- und Hunderterstellen der maximal dreistelligen Zahl getrennt hochgezählt werden: 

class Counter
{
  public static void main(String[] args)
  {
    int zahl;

    for (x = 0; x <= 9; ++x) {
      for (y = 0; y <= 9; ++y) {
        for (z = 0; z <= 9; ++z) {
          zahl = 100 * x + 10 * y + z;
          System.out.println(""+zahl);
        }
      }
    }
  }
}
Rein funktionale Programmiersprachen (wie beispielsweise frühe LISP-Dialekte) bieten gar keine expliziten Schleifenkonstrukte an. Jede Art von Schleife muß stattdessen mit Hilfe von rekursiven Funktionsaufrufen nachgebildet werden. Schreiben Sie das obige Programm so um, daß es völlig ohne explizite Schleifen auskommt und stattdessen die drei Zählervariablen durch rekursive Methodenaufrufe verändert.

31. [C] (Türme von Hanoi). "Türme von Hanoi" ist das klassische Problem für die Anwendung rekursiver Lösungsansätze. Um ein gutes Gefühl für rekursive Problemlösungen zu bekommen, sollten Sie sich mit dieser Aufgabe beschäftigen. Die Lösung ist sehr verblüffend und elegant.

Bei diesem Problem sind drei Stäbe auf einem Brett montiert, so daß Scheiben unterschiedlicher Größe darauf gesteckt werden können. Zu Beginn befinden sich n Scheiben nach absteigender Größe sortiert auf Stab A. Die Aufgabe besteht nun darin, unter Beachtung der folgenden Regeln alle n Scheiben Zug für Zug in der gleichen Ordnung auf Stab C zu plazieren:

  1. Ein Zug besteht darin, daß die oberste Scheibe eines beliebigen Turmes auf einen anderen Stab gesteckt wird.
  2. Niemals darf eine größere auf einer kleineren Scheibe liegen.
  3. Stab B darf als Zwischenablage verwendet werden.
Interpretieren Sie zur Lösung der Aufgabe den aus n Scheiben bestehenden Turm rekursiv als Zusammensetzung einer ganz unten liegenden großen Scheibe mit einem darauf befindlichen Turm-von-Hanoi aus n-1 Scheiben.

32. [C] (Türme von Hanoi, iterativ). Eine nicht minder interessante Aufgabe besteht darin, eine iterative Lösung für "Türme von Hanoi" zu finden. Üblicherweise wird die Schwierigkeit, eine solche zu finden und zu implementieren als Argument für die Eleganz und Einfachheit rekursiver Lösungsansätze gebraucht. Überraschenderweise gibt es aber einen weithin unbekannten Algorithmus (Buneman und Levy, 1980), der noch einfacher ist als die rekursive Lösung. Er basiert auf der Idee, die Stäbe "im Kreis" anzuordnen und die Scheiben in geschickter Weise im Uhrzeigersinn zu bewegen.

33. [C] (Das 8-Damen-Problem). Schreiben Sie ein Programm, das das 8-Damen-Problem löst. Bei diesem Problem geht es darum, 8 Damen so auf einem Schachfeld zu plazieren, daß keine die andere schlagen kann. Das 8-Damen-Problem ist seit langer Zeit bekannt (und gelöst) und hat bereits im 19. Jahrhundert den berühmten Mathematiker C. F. Gauß beschäftigt. Im Gegensatz zu uns hatte er jedoch noch keinen Computer und konnte daher Zeit seines Lebens keine Lösung finden.
Aufg0733.java

34. [C] (Game of Life). Eine interessante Anwendung zweidimensionaler Arrays ist die Implementierung zellulärer Automaten. Eine der ältesten und bekanntesten Simulationen solcher Automaten nennt sich "Game of Life" und wurde von dem Mathematiker J. H. Conway vorgeschlagen.

Die Regeln sind sehr einfach zu verstehen. Game of Life ist ein zellulärer Automat, der auf einem rechteckigen Spielfeld mit einer festen Anzahl Zellen gespielt wird. Jedes Element des Spielfeldes enthält eine Zelle, die entweder tot ist oder lebt. Der Anfangszustand des Spielfelds wird per Zufallszahlengenerator ermittelt oder vom Anwender vorgegeben. Ein Folgezustand wird für die komplette Population auf der Basis der folgenden Regeln bestimmt:

Das Berechnen der nächsten Generation erfolgt simultan für alle Zellen. Das bedeutet, daß das Programm zunächst aus der aktuellen Population für jede Zelle den Folgezustand berechnet. Erst nachdem die komplette Nachfolgegeneration berechnet ist, wird sie auf das Spielfeld übertragen.

Trotz dieser einfachen Regeln ist das Verhalten der Zellpopulation komplex und es macht Spaß, die Veränderungen zu beobachten. Es gibt eine Reihe interessanter Muster, die während der Generationswechsel ein vorhersagbares Verhalten zeigen. So wechseln beispielsweise drei benachbarte Zellen, die keine weiteren Nachbarn haben, zyklisch zwischen einer horizontalen und vertikalen Darstellung. Daneben gibt es Muster, die vollkommen unverändert bleiben und solche, die sich nach kurzer Zeit vollständig auflösen. Außerdem gibt es Muster, die sich in zyklischen Wiederholungen über das Brett bewegen. Die folgende Abbildung zeigt einige von ihnen: 

........ ........ ........ ........
........ ........ ...XX... ....X...
..XXX... ...XX... ..X..X.. .....X..
........ ...XX... ...XX... ...XXX..
........ ........ ........ ........
Ihre Aufgabe besteht nun darin, eine textorientierte Implementierung von Game of Life zu entwickeln. Der Anwender soll die Möglichkeit haben, einen initialen Zustand vorzugeben und nacheinander Folgegenerationen abzurufen. Die Ausgabe des Programm soll in einer Form ähnlich der obigen Abbildung erfolgen.
Aufg0734.java

35. [C] (Semaphoren). Wie Kapitel 10 deutlich macht, gibt es beim konkurrierenden Zugriff auf gemeinsame Daten eine Reihe von Synchronisationsproblemen. Wird von mehreren Threads gleichzeitig auf dieselben Daten zugegriffen, und ist mindestens einer der Zugriffe schreibender Art, so können Situationen auftreten, bei denen die Daten inkonsistent werden. Dies liegt in vielen Fällen daran, daß bestimmte Operationen nicht mehr unteilbar ablaufen, sondern vom Thread-Scheduler unterbrochen werden können.

Eine von E. Dijkstra im Jahre 1968 entwickelte Methode der Synchronisation paralleler Prozesse ist die Verwendung von Semaphoren. Ein Semaphor ist eine Variable, auf die von mehreren Prozessen mit Hilfe zweier unteilbarer Operationen passeer (holl. betreten) und verlaat (holl. verlassen) zugegriffen werden kann. Bei einem binären Semaphor, auf dessen Betrachtung wir uns hier beschränken wollen, kann die Variable die Werte 0 und 1 annehmen. Die Wirkungsweise der beiden Operationen ist dabei wie folgt:

Da beide Operationen per Definition unteilbar ablaufen, können mit ihrer Hilfe nahezu alle gängigen Synchronisationsprobleme gelöst werden. Dazu werden die Programmteile identifiziert, die nur von einem Prozess zur Zeit ausgeführt werden dürfen. Diese kritischen Abschnitte werden mit Hilfe von Semaphoren nun so geschützt, daß am Anfang ein Aufruf von passeer und am Ende ein Aufruf von verlaat steht.

Die Semaphore sorgen auf diese Weise dafür, daß der kritische Abschnitt nur von einem einzigen Prozess zur Zeit passiert werden kann. Mit ihrer Hilfe lassen sich die meisten Synchronisationsprobleme lösen. Nachteilig ist allerdings, daß der Programmierer selbst für die ordnungsgemäße Klammerung der kritischen Abschnitte zu sorgen hat. Auch ist es leicht möglich, versehentlich Deadlocks zu erzeugen, also Verklemmungen, bei denen mehrere Prozesse auf die vom jeweils anderen Prozess belegten Semaphoren warten.

Implementieren Sie mit Hilfe der in Java verfügbaren Synchronisationsprimitive binäre Semaphoren. Versuchen Sie dabei, den Wartezustand ohne Verwendung einer Rechenzeit verbrauchenden expliziten Warteschleife zu implementieren. Zeigen Sie die Funktionsfähigkeit Ihrer Implementierung am Beispiel eines Programmes, bei dem mehrere Threads lesend und schreibend auf eine gemeinsame Zählervariable zugreifen. Demonstrieren Sie das typische Fehlverhalten des Programmes bei Verzicht auf die Synchronisation durch Semaphoren und zeigen Sie, wie das Problem mit Hilfe von Semaphoren gelöst werden kann.

36. [C] (Die dinierenden Philosophen). Das Philosophenproblem ist ein klassisches Problem zur Erläuterung konkurrierender Prozesse und damit zusammenhängender Synchronisationsprobleme. Dabei sitzen 5 Philosophen um einen runden Tisch und durchlaufen zyklisch (aber in unterschiedlichen, zufälligen Zeitabständen) die drei Zustände "nachdenken", "hungrig sein" und "essen". Jeder Philosoph hat einen Teller Nudeln vor sich und zwischen je zwei Tellern liegt eine Gabel. Zum Essen werden beide Gabeln benoetigt, so das höchstens zwei Philosophen zur Zeit essen können, und das auch nur, wenn sie nicht nebeneinander sitzen. Nach dem Essen werden die Gabeln wieder an ihren Platz gelegt und stehen den Nachbarn zur Verfügung. Der Philosoph wechselt dann wieder in den Zustand "nachdenken".

Ihre Aufgabe besteht nun darin, das Problem mit Hilfe geeigneter Synchronisationsverfahren (die typischerweise, aber nicht zwangsläufig, durch Semaphoren realisiert werden) zu lösen. Dabei dürfen weder Verklemmungen entstehen, noch sollen einzelne Philosophen auf Dauer vom Essen ausgeschlossen werden. Schreiben Sie ein Programm, bei dem die einzelnen Philosophen durch separat ablaufende Threads repräsentiert werden, deren aktueller Zustand durch eine interne Variable zyklisch verändert wird. Synchronisieren Sie den Zugriff auf die Gabeln durch gemeinsame Variablen, auf die mit Hilfe von Synchronisationsprimitiven in geeigneter Weise zugegriffen wird.

© 1995-2004 Guido Krüger - Last updated 31 Dec 2003 - Back to top-level page