Objektorientierte Programmiertechniken
LVA 185.A01, VU, 3 ECTS, 2016/2017 W

8. Übungsaufgabe

Themen:

Exceptions, nebenläufige Programmierung

Termine:

Ausgabe:	14.12.2016
Abgabe:	11.01.2017, 12:00 Uhr

Abgabeverzeichnis:

Aufgabe8

Programmaufruf:

java Test

Grundlage:

Skriptum, Schwerpunkt auf den Abschnitten 4.1 und 4.2

Aufgabe

Welche Aufgabe zu lösen ist:

Nachdem es immer kälter wird, fressen die Eichhörnchen die letzten Nüsse von den Bäumen. Da die leicht erreichbaren Nüsse schon vertilgt sind, wagen sich die Eichhörnchen auf Äste, die so dünn sind, dass sie immer auf zwei Ästen gleichzeitig sitzen müssen, damit diese nicht brechen.

Simulieren Sie das Fressen der letzten Nüsse mittels eines nebenläufigen Java-Programms. Stellen Sie dabei jedes Eichhörnchen durch einen eigenen Thread dar. Zur Vereinfachung der Simulation werden nur die Äste in einer Ebene simuliert. Dazu wird schachbrettartig ein Gitter über die Äste gelegt und angenommen, dass sich jeweils ein Aststück auf jedem Feld befindet. Ein Eichhörnchen muss sich immer gleichzeitig auf zwei benachbarten Ästen (zwei senkrecht oder waagrecht benachbarten Feldern) befinden. Es darf sich immer maximal ein Eichhörnchen auf einem Astpaar befinden. Ein Eichhörnchen kann auf ein freies benachbartes Astpaar springen. Ein Astpaar ist benachbart, wenn ein Feld des Astpaares zu einem Feld des anderen Astpaares benachbart ist. Nach dem Sprung wartet das Eichhörnchen eine kurze Zeit bevor es weiterspringt. Bestimmen Sie durch eine einfache Strategie wohin gesprungen wird. Wenn kein freies Astpaar vorhanden ist, wartet das Eichhörnchen kurze Zeit. Damit die Simulation sehr viel schneller als in Wirklichkeit abläuft, lassen Sie die Eichhörnchen zufallsgesteuert wenige Millisekunden (5-50) warten. Zählen Sie die Anzahl der Warteschritte mit. Simulieren Sie Wartezeiten mittels der Methode Thread.sleep(n). Achtung: sleep behält alle Monitore (= Locks); Sie sollten sleep daher nicht innerhalb einer synchronized-Methode oder -Anweisung aufrufen, wenn während der Wartezeit von anderen Threads aus auf dasselbe Objekt zugegriffen werden soll.

Wenn ein Eichhörnchen die maximalen Warteschritte (32) erreicht hat, oder alle Nüsse gefressen sind, geben Sie von allen Eichhörnchen den Zählerstand der Warteschritte und die Anzahl der gefressenen Nüsse und das Astpaar (auf welchen Feldern es sich befindet) aus und beenden alle Threads. Verwenden Sie Thread.interrupt() um einen Thread zu unterbrechen. Geben Sie die Positionen als X- und Y-Koordinaten der Felder sowie die Zählerstände aus, und beenden Sie den Thread. Die Äste dürfen in jeder Dimension (waagrecht und senkrecht) nicht mehr als 80 Felder haben.

Wählen Sie ein Eichhörnchen als Leiteichhörnchen aus und geben sie immer, nachdem es gewartet hat, die Astfelder zeilenweise am Bildschirm aus. Verwenden Sie den Buchstaben "o" für ein Feld, auf dem eine Nuss ist, die Buchstaben "e" und "h" für die Felder eines Astpaares, auf dem sich ein Eichhörnchen befindet und den Buchstaben "+" für die restlichen Astfelder, zum Beispiel so:

+ o + + e h + + +
+ + o + o + e + o
+ o + + + + h + +
+ + + o + + e h +
o + o + + + o + +

Die Klasse Test soll (nicht interaktiv) Testläufe des Nüsse-Fressens 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). Bitte achten Sie darauf, dass die Testläufe keine Systemlimits wie maximale Anzahl an gleichzeitig aktiven Threads auf dem Abgaberechner (g0) überschreiten. Führen Sie mindestens drei Testläufe mit unterschiedlichen Einstellungen durch:

Jeder Testlauf soll Eichhörnchen und Nüsse an unterschiedlichen Feldern positionieren. Für die Länge des Wartens sollen unterschiedliche Werte verwendet werden.
Stellen Sie die Parameter so ein, dass irgendwann Nüsse gefressen werden und Eichhörnchen manchmal warten müssen.

Daneben soll die Datei Test.java wie gewohnt als Kommentar eine kurze, aber verständliche Beschreibung der Aufteilung der Arbeiten auf die einzelnen Gruppenmitglieder enthalten – wer was gemacht hat.

Warum die Aufgabe diese Form hat:

Die Simulation soll die nötige Synchronisation bildlich veranschaulichen und ein Gefühl für eventuell auftretende Sonderfälle geben. Beispielsweise müssen Eichhörnchen erkennen, wenn sie die maximale Anzahl an Warteschritten erreicht haben. Einen speziellen Sonderfall stellt das Simulationsende dar, das (aus Sicht eines Eichhörnchens) 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.

Was im Hinblick auf die Beurteilung zu beachten ist:

Die insgesamt 100 für diese Aufgabe erreichbaren Punkte sind folgendermaßen auf die zu erreichenden Ziele aufgeteilt:

Synchronisation richtig verwendet, auf Vermeidung von Deadlocks geachted, sinnvolle Synchronisationsobjekte gewählt, kleine Synchronisationsbereiche	45 Punkte
Lösung wie vorgeschrieben und sinnvoll getestet	20 Punkte
Zusicherungen richtig und sinnvoll eingesetzt	15 Punkte
Geforderte Funktionalität vorhanden (so wie in Aufgabenstellung beschrieben)	15 Punkte
Sichtbarkeit auf so kleine Bereiche wie möglich beschränkt	5 Punkte

Der Schwerpunkt bei der Beurteilung liegt auf korrekter nebenläufiger Programmierung 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. dürfen nicht alle Astfelder gleichzeitig als ein einzelnes Synchronisationsobjekt blockiert werden, ausgenommen davon ist nur die Ausgabe der Astfelder am Bildschirm),
nicht richtig abgefangene Exceptions im Zusammenhang mit nebenläufiger Programmierung,
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.

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 (Eichhörnchen sollen gleichzeitig umherspringen können). 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 -Anweisung 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. Stellen Sie sicher, dass die maximale Anzahl an Threads und der maximale Speicher nicht überschritten werden. Dazu ist es sinnvoll, dass Sie im Threadkonstruktor explizit die Stackgröße mit einem kleinen Wert angeben (z.B. 16k).

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.

Was im Hinblick auf die Abgabe zu beachten ist:

Gerade für diese Aufgabe ist es besonders wichtig, dass Sie (abgesehen von geschachtelten Klassen) nicht mehr als eine Klasse in jede Datei geben und auf aussagekräftige Namen (ohne Umlaute) achten. Sonst ist es schwierig, sich einen Überblick über Ihre Klassen und Interfaces zu verschaffen. Achten Sie darauf, dass Sie keine Java-Dateien abgeben, die nicht zu Ihrer Lösung gehören (alte Versionen, Reste aus früheren Versuchen, etc.).