Computerorientierte Mathematik

Im Internet gibt es hunderte von Datenbanken, auf die wiederum tausende von Nutzern gleichzeitig zugreiffen. Diese Zugriffe k&oe;nnen dabei sowohl lesender als auch schreibender Natur sein. Stellt euch z.B. vor, ihr wollt einen Internet-Dienst einrichten, in dem sich Benutzer registrieren ("Einfügen"), anmelden ("Suchen") bzw. ihren Zugang auflösen ("Löschen") k&oennen. Zur Verwaltung dieser Benutzer-Accounts eignet sich ein AVL-Baum, da die Benutzer-Daten nach dem eindeutigen Schl&ue;ssel "Benutzerkennung" sortiert sind, und der Zugriff auf diese Daten schnell erfolgen soll.

Das Problem dabei ist, dass nun ständig mehrere Nutzer gleichzeitig auf den AVL-Baum zugreifen, wobei einige lesen und andere schreiben wollen. Dies führt i.A. zu Konflikten, die dazuführen, dass die AVL-Baum-Eigenschaften nachhaltig zerstört werden, kann aber mit dem bereits vorgestellten Monitor-Konzept verhindert werden.

Ihr sollt nun diesen multiplen Zugriff auf einen AVL-Baum mittels Threads simulieren und den Umgang daraus resultierender Schwierigkeiten üben. Dazu wird jeder Nutzer wird durch einen eigenen Thread repräsentiert.

Eine Beschreiung von Threads findet Ihr auch nochmal im Java Tutorial von Sun.

Oberfläche

Das Hauptprogramm soll auf Anforderung einen neuen Nutzer erstellen können, das heißt ein neuer Thread wird gestartet. Um die Aktivitäten des imaginären Nutzers simulieren zu können soll er auch ein Fenster (Frame) zugeordnet bekommen, in welches die Aktivitäten eingetragen werden. Alle Nutzer (Threads), die das Hauptprogramm erzeugt, und nur diese, sollen in einer gemeinsamen ThreadGroup enthalten sein. Durch diese Gruppe hat das Hauptprogramm immer einen Überblick über alle aktiven Nutzer, diese sollen auch regelmäßig aktualisiert vom Hauptprogramm angezeigt werden. Dazu eignet sich idealerweise ein weiterer, eigener Thread.

Das Hauptprogramm soll sich nicht um die Einzelheiten der Threadorganisation eines Nutzers kümmern. Das muss alles in gekapselter Form Aufgabe einer eigenen Klasse sein.

Ein Nutzer, also insbesondere sein Thread, soll sowohl vom Hauptprogramm als auch über sein Fenster ordentlich beendet werden können. Beachtet dazu die Hinweise in der Dokumentation zum Beenden von Threads.

Funktionalität

Das Hauptprogramm soll einen AVL-Baum besitzen, auf den die verschiedenen Nutzer (Threads) Zugriff haben. Es soll sowohl nur lesender als auch schreibender/löschender Zugriff möglich sein. Ihr müsst also ein Konzept entsprechend der Übung bzw. der Aufgabe 48 vom 10. Übungsblatt entwickeln, mit dem die Zugriffe auf den Baum konsistent organisiert werden. Dazu sollt Ihr Eure AVL-Baum Klasse aus der letzten Programmieraufgabe verwenden. Diese Klasse darf nicht mehr verändert werden! Alle Veränderungen daran müsst Ihr am besten mittels einer Wrapper-Klasse oder über Vererbung realisieren. Alle öffentlich sichtbaren Methoden und Attribute müssen bezüglich parallelen Zugriffs in Eurer neuen Klasse sicher sein. (Einzige Ausnahme ist die nachträgliche Korrektur der Sichtbarkeiten von internen Methoden der alten AVL-Baum Klasse, falls Ihr vergessen habt, diese als private zu deklarieren.)

Genauso wie ihr Wrapper-Iteratoren bereits kennengelernt habt, kann man auch Container-Wrapper schreiben, die einen anderen Container (hier: einen AVL-Baum) enthalten und den Zugriff auf die einzelnen Methoden neu regeln. Eine geeignete Wrapper-Klasse sollte das Interface AssociativeContainer implementieren und neben eurem AVL-Baum auch einen Monitor besitzen, der die Zugriffe auf den AVL-Baum regelt. Dieser Monitor könnte von dieser Monitor-Klasse abgeleitet sein. Die einzelnen Methoden eures synchronisierten Containers könnten den Monitor dann etwa so verwenden:

    public Iterator find( Object someData ) throws ContainerException {
	monitor.readLogOn();
	Iterator it=null;

	try{
	    it = container.find(someData);
	}
	catch(ContainerException e){
	    throw e;
	}
	finally{
	    monitor.readLogOff();
	}

	if (it==null)
	    return null;
	return new SynchronizedIterator(it, monitor);
    }
    

Zu beachten ist, dass auch das Anwenden von Iterator-Methoden ein (meist lesender) Zugriff auf den Baum ist, und deshalb ebenfalls synchronisiert werden muss!!! Deshalb ist es sinnvoll, eine Wrapper-Klasse auch für die Iteratoren zu schreiben, die dann wieder neben dem eigentlichen Iterator auch den Monitor kennt.

Parallelität

Da die unterschiedlichen Nutzer nur über verschiedene Fenster und somit nur durch einen Nutzer (Euch) realisiert sind, würden direkte Anfragen nicht parallel sondern nur seriell erfolgen. Um Euren neuen AVL-Baum trotzdem testen zu können, soll für jeden Nutzer über sein Fenster eine Liste von Aktionen eingeben werden können (zum Beispiel in einer TextArea), die zu einem vorgegebenen Zeitpunkt abgearbeitet wird. Die Abwicklung der Abarbeitung dieser Aufgaben muss dann der zum Nutzer gehörende Thread übernehmen. Der Startzeitpunkt soll natürlich für alle Nutzer (Threads) der gleiche sein. So beginnen doch alle Nutzer gleichzeitig, Anfragen zu stellen.

Euer Hauptprogramm soll alle Zugriffe auf den Baum protokollieren. Die Ausgaben sollen mittels einer gabl.util.trace.TracePolicy in Eurer neuen AVL-Baum Klasse erzeugt und dann vom Hauptprogramm an entsprechender Stelle ausgegeben werden. Dazu solltet ihr eine neue TracePolicy schreiben, die die mittels println zu druckenden Texte in eine ihr übergebene TextArea schreibt.

Die Fenster zu den Nutzern sollen natürlich ebenfalls Protokoll über die erfolgreichen oder nicht erfolgreichen Anfragen führen.

Zur Erinnerung

Überlegt Euch wieder als erstes eine saubere Zerlegung des Problems in Klassen und ordnet diesen Aufgaben und die notwendigen Informationen zu. Dazu eignet sich bekanntlich UML (ein white paper dazu). Beim Programmieren überprüft immer wieder an Hand Eures Bildes ob Euer Konzept noch richtig ist oder verändert werden muss. Verändert immer erst dass Konzept, bevor Ihr das Programm dazu schreibt.

Bekanntlich kann man in einem kurzen Programm (Methode) weniger Fehler machen als in einem langen. Ersetzt nicht einen Fehler durch ständiges hinzufügen von weiten Zeilen durch zehn Fehler.

Vergesst die javadoc-Dokumentierung nicht!