Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2010 W

8. Laborübungsaufgabe

Themen:

Exceptions, nebenläufige Programmierung

Termine:

Ausgabe:	15.12.2010
reguläre Abgabe:	22.12.2010, 13:45 Uhr
nachträgliche Abgabe:	12.01.2011, 13:45 Uhr

Abgabeverzeichnis:

Gruppe/Aufgabe8

Programmaufruf:

java Test

Grundlage:

Skriptum bis Seite 151, Schwerpunkt auf den Abschnitten 3.5 und 3.6

Aufgabe

Welche Aufgabe zu lösen ist:

In einem Computerspiel versuchen Schatzsucher (jeder Schatzsucher hat einen Namen) in einem Labyrinth möglichst viele Schätze einzusammeln und dann einen Ausgang zu erreichen. Geister versuchen das zu verhindern und töten jeden Schatzsucher, den sie treffen. Das Labyrinth ist rechteckig und besteht ähnlich einem Schachbrett aus einer Anzahl an quadratischen Feldern. Das Labyrinth ist im Süden und Westen von einer Mauer begrenzt, jedes Feld kann im Norden und/oder Osten von einer Mauer begrenzt sein. Auf jedem Feld könen sich beliebig viele Schatzsucher oder Geister aufhalten. Sowohl Schatzsucher als auch Geister bewegen sich von Feld zu Feld. Befinden sich Schatzsucher und mindestens ein Geist gleichzeitig auf einem Feld, werden alle Schatzsucher getötet, die sich auf diesem Feld befinden. Auf einem Feld befindet sich maximal ein Schatz, dessen Wert durch eine ganze Zahl dargestellt wird. Der erste Schatzsucher, der ein Schatzfeld betritt, erhät diesen Schatz. Das Spiel ist beendet, wenn

• alle Schatzsucher getötet wurden (dann haben die Geister gewonnen)
• oder ein Schatzsucher einen Ausgang (ein Feld am Nord- oder Ostrand des Labyriths, das keine Mauer am Rand besitzt) erreicht hat,
• oder ein Schatzsucher eine Maximalzahl an Schritten (= Wechseln des Feldes) durchgeführt hat.

In den letzten beiden Fällen haben die Schatzsucher gewonnen und es wird der Wert aller Schätze der überlebenden Schatzsucher angezeigt.

Simulieren sie das Spiel mittels eines nebenläufigen Java-Programms. Stellen sie dabei jeden Schatzsucher und jeden Geist durch einen eigenen Thread dar. Jeder Schatzsucher bzw. Geist bewegt sich nach einer gewissen Zeit (wenige Millisekunden) von einem Feld des Labyrinths zu einem beliebigen, nicht durch eine Mauer getrennten Nachbarfeld in den vier Himmelsrichtungen. Simulieren Sie Wartezeiten zwischen einzelnen Schritten mittels der Methode Thread.sleep(n). Achtung: sleep behält alle Monitore (= Locks); Sie sollten sleep daher nicht innerhalb einer synchronized-Methode oder eines synchronized-Blocks aufrufen, wenn während der Wartezeit von anderen Threads aus auf dasselbe Objekt zugegriffen werden soll. Wenn der letzte Schatzsucher gestorben ist, ein Schatzsucher einen Ausgang erreicht hat, oder ein Schatzsucher die Maximalzahl an Schritten ausgeführt hat, geben Sie aus, welche Schatzsucher noch leben und beenden alle Threads (Schatzsucher und Geister). Verwenden Sie Thread.interrupt() um einen Thread zu unterbrechen, geben Sie, falls es sich um einen Schatzsucher handelt, seinen Namen und den aufsummierten Wert seiner Schätze aus, und beenden Sie den Thread. Wenn ein Schatzsucher den auf einem Feld liegenden Schatz aufnimmt, wird der Wert des Schatzes für diesen Schatzsucher aufsummiert und der Schatz aus dem Labyrinth enfernt.

Die Klasse Test soll (nicht interaktiv) Testläufe des Spiels durchführen und die Ergebnisse in allgemein verständlicher Form in der Standardausgabe darstellen. Bitte achten Sie darauf, dass die Testläufe nach kurzer Zeit terminieren (maximal 10 Sekunden für alle zusammen). Führen Sie mindestens drei Testläufe mit unterschiedlichen Einstellungen durch:

• Jeder Testlauf soll eine unterschiedliche Menge an Schätzen, Mauern, Schatzsuchern und Geistern verwenden und diese vor dem Start auf unterschiedliche Felder des Labyrinths positionieren. Auch innerhalb eines Testlaufs sollen Schatzsucher und Geister unterschiedliche Geschwindigkeiten haben.
• Stellen Sie die Parameter so ein, dass sich irgendwann auch mehrere Schatzsucher oder Geister gleichzeitig auf einem Feld befinden.

Warum die Aufgabe diese Form hat:

Das Spiel soll die nötige Synchronisation bildlich veranschaulichen und ein Gefühl für eventuell auftretende Sonderfälle geben. Beispielsweise müssen Schatzsucher erkennen, wenn sie getötet werden. Einen speziellen Sonderfall stellt das Spielende dar, das (aus Sicht eines Schatzsuchers oder eines Geistes) jederzeit in jedem beliebigen Zustand auftreten kann. Dabei wird auch geübt, nach einer an einer beliebigen Programmstelle aufgetretenen Exception den Objektzustand so weit wie nötig zu rekonstruieren, um ein sinnvolles Ergebnis zurückliefern zu können.

Wie die Aufgabe zu lösen ist:

Überlegen Sie sich genau, wie und wo Sie Synchronisation verwenden. Halten Sie die Granularität der Synchronisation möglichst klein, um unnötige Beeinflussungen anderer Threads zu reduzieren. Vermeiden Sie aktives Warten, indem Sie immer sleep aufrufen, wenn Sie eine bestimmte Zeit warten müssen. Beachten Sie, dass ein Aufruf von sleep innerhalb einer synchronized-Methode oder eines synchronized-Blocks den entsprechenden Lock nicht freigibt.

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. Ein Programm, das auf einem Rechner problemlos funktioniert, kann auf einem anderen Rechner (durch winzige Unterschiede im zeitlichen Ablauf) plötzlich nicht mehr funktionieren.

Nebenläufigkeit kann die Komplexität eines Programms gewaltig erhöhen. Achten Sie daher besonders darauf, dass Sie den Programm-Code so klein und einfach wie möglich halten. Jede unnötige Anweisung kann durch zusätzliche Synchronisation (oder auch fehlende Synchronisation) eine versteckte Fehlerquelle darstellen und den Aufwand für die Fehlersuche um vieles stärker beeinflussen als in einem sequentiellen Programm.

In dieser Aufgabe geht es nicht darum, geschickte Spielstrategien für Schatzsucher und Geister zu finden. Halten Sie daher die Auswahl der Richtung, in die sich ein Schatzsucher oder Geist bewegt, möglichst einfach.

Was im Hinblick auf die Beurteilung zu beachten ist:

Der Schwerpunkt bei der Beurteilung liegt auf korrekter nebenläufiger Programmerierung und der richtigen Verwendung von Synchronisation sowie dem damit in Zusammenhang stehenden korrekten Umgang mit Exceptions. Punkteabzüge gibt es für

• fehlende oder fehlerhafte Synchronisation,
• zu große Synchronisationsbereiche, durch die sich Threads gegenseitig unnötig behindern (z.B. das gesamte Labyrinth als Synchronisationsobjekt),
• nicht richtig abgefangene Exceptions im Zusammenhang mit nebenläufiger Programmerierung,
• Nichttermination von java Test innerhalb von 10 Sekunden,
• unnötigen Code und mehrfache Vorkommen gleicher oder ähnlicher Code-Stücke,
• vermeidbare Warnungen des Compilers, die mit Generizität in Zusammenhang stehen,
• Verletzungen des Ersetzbarkeitsprinzips bei Verwendung von Vererbungsbeziehungen,
• mangelhafte Zusicherungen,
• schlecht gewählte Sichtbarkeit,
• unzureichendes Testen,
• und mangelhafte Funktionalität des Programms.

Was im Hinblick auf die Abgabe zu beachten ist:

Verzichten Sie wie üblich auf die Verwendung von packages und Verzeichnissen innerhalb des Abgabeverzeichnisses. Geben Sie (abgesehen von geschachtelten Klassen) nicht mehr als eine Klasse in jede Datei, und verwenden Sie aussagekräftige Namen. Achten Sie darauf, dass Sie keine Java-Dateien abgeben, die nicht zu Ihrer Lösung gehören.