Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2007 W

8. Übungsaufgabe

Themen:

Generizität, nebenläufige Programmierung

Termine:

Ausgabe:	13.12.2007
reguläre Abgabe:	10.01.2008, 12:45 Uhr
nachträgliche Abgabe:	17.01.2008, 12:45 Uhr

Abgabeverzeichnis:

Aufgabe8

Programmaufruf:

java Test

Grundlage:

Skriptum bis Seite 131 und die Seiten 139 bis 145

Aufgabe

Welche Aufgabe zu lösen ist:

Eine häufig genutzte Datenstruktur zum Speichern und Auffinden von Daten ist ein binärer Suchbaum. Dabei werden in den Knoten des Baums der Schlüssel und die Daten gespeichert. Daten mit kleinerem Schlüssel werden im linken Teilbaum, Daten mit größerem Schlüssel im rechten Teilbaum gespeichert. Schlüssel können beliebige Datentypen sein, die einen Vergleich unterstützen, wie z.B. ganze Zahlen oder Zeichenketten.

        7
      /   \
     4     8
   /   \     \
  2     5     11

Definieren Sie ein Interface KeyType, das die Methoden less and equal unterstützt.

Entwickeln Sie eine generische Klasse BinTree für einen binäreren Suchbaum mit einem Schlüssel eines Untertyps von KeyType, die in einem Knoten den Schlüssel und (nicht als Teil des Schlüssels) einen Zähler speichert. Die Klasse BinTree bzw. die Knoten müssen den gleichzeitigen Zugriff mehrerer Threads sicher ermöglichen. Methoden für folgende Aufgaben werden benötigt:

eine Methode insert, die einen Knoten in den Baum einfügt und den Zähler auf 1 setzt, falls der Knoten mit dem Schlüssel noch nicht existiert, und andernfalls den Zähler um 1 erhöht.
eine Methode delete, die den Zähler um 1 erniedrigt (falls der Knoten mit dem Schlüssel existiert und der Zähler größer als 1 ist), die den Knoten entfernt (falls der Knoten mit dem Schlüssel existiert und der Zähler gleich 1 ist) und anderfalls keine Aktion durchführt.

Die Klasse Test soll die wichtigsten Normal- und Grenzfälle (nicht interaktiv) überprüfen und die Ergebnisse in allgemein verständlicher Form in der Standardausgabe darstellen. Bitte achten Sie darauf, dass der Test nach kurzer Zeit terminiert. Zumindest die folgenden Überprüfungen sind durchzuführen:

Testen Sie die Klasse BinTree mit mindestens zwei selbstdefinierten Klassen, die ganze Zahlen und Zeichenketten (Strings) darstellen.
Testen Sie die Klasse BinTree mit vier Threads, die Knoten in den Baum einfügen, und gleichzeitig zwei Threads, die Knoten vom Baum entfernen. Jeder Thread soll zumindest 10.000 Einfüge- oder Löschoperationen mit 100 unterschiedlichen Schlüsseln durchführen. Geben Sie für jeden Einfügethread getrennt aus, wie viele Einfügeoperationen ausgeführt wurden und wie oft dabei nur der Zähler erhöht wurde. Geben Sie für jeden Löschthread getrennt aus, wie viele Löschoperationen ausgeführt wurden, wie oft dabei Knoten nicht im Baum enthalten waren und wie oft nur der Zähler erniedrigt wurde.

Wie die Aufgabe zu lösen ist:

Der Schwerpunkt dieser Aufgabe liegt auf korrekter nebenläufiger Programmerierung und der richtigen Verwendung von Synchronisation. Überlegen Sie sich genau, wie und wo Sie Synchronisation verwenden. Halten Sie die Granularität der Synchronisation möglichst klein und achten Sie auf eine effiziente Ausführung. Teilen Sie die Funktionalität für die Zählung der Ereignisse für die Testausgabe sinnvoll auf die einzelnen Klassen auf. Achten Sie weiters auf die richtige Verwendung von gebundener Generizität. Testen Sie Ihre Lösung bitte rechtzeitig auf der g0, da es im Zusammenhang mit Nebenläufigkeit große Unterschiede zwischen den einzelnen Plattformen geben kann.

Hinweise zur Beurteilung:

Der Schwerpunkt bei der Beurteilung liegt auf korrekter nebenläufiger Programmerierung und der richtigen Verwendung von Synchronisation. Kräftige Punkteabzüge gibt es für

fehlende Synchronisation
zu große Synchronisationsbereiche
vermeidbare Warnungen des Compilers, die mit (der falschen Verwendung von) Generizität in Zusammenhang stehen
Verletzungen des Ersetzbarkeitsprinzips bei Verwendung von Vererbungsbeziehungen
Nichttermination nach 10 Sekunden
und mangelhafte Funktionalität des Programms.

Punkteabzüge gibt es, wie bereits üblich, auch für unnötigen (oder unnötig komplexen) Code, mangelhafte Zusicherungen und falsche Sichtbarkeit.

Was im Hinblick auf die Abgabe zu beachten ist:

Schreiben Sie Ihre Lösung in das bereits existierende Verzeichnis Gruppe/Aufgabe8. Das Programm soll von diesem Verzeichnis aus durch java Test aufrufbar sein. Schreiben Sie (abgesehen von geschachtelten Klassen) nicht mehr als eine Klasse in jede Datei. Das Verzeichnis soll zu den Abgabezeitpunkten alle .java-Dateien enthalten, die Sie für Ihre Lösung benötigen. Bitte entfernen Sie alle .java-Dateien, die nicht zur Abgabe gehören. Dateien mit anderen Endungen werden bei der Beurteilung nicht berücksichtigt. Verzichten Sie auf die Verwendung von Verzeichnissen innerhalb von Gruppe/Aufgabe8.