b) zur b) habe ich ja einen Lösungsvorschlag gemacht
zur Levenstein 2b)
das mit den rows musst du nicht machen
es wird ja nicht nach rows gebarriert sondern nach columns und auch in der letzten zeile muss der thread sachen in die barrier packen
Beispiel: (wieder Thread A und Thread B)
wenn TA in der letzten Zeile ist und keine Ready in die Barrier Packen würde würde TB nie die letzte Zeile bearbeiten
Noch einmal zur A3 c,
Ein Vorschlag war bekanntlich, dass man das Boolean-Array Atomic setzt.
Ich verstehe aber ehrlich gesagt nicht ganz, was das bringen soll, da ja alle Threads
unterschiedliche IDs haben und somit alle unterschiedliche Einträge bearbeiten und zweitens
sowieso immer nur true in das Array geschrieben wird.
Zur Sichtbarkeitsproblemen sollte es durch den Aufruf der static-Methode der Klasse eigentlich auch nicht kommen, wie schon in einen früheren Post angemerkt wurde.
Mir ist hier wirklich nicht klar, weshalb eine Verklemmung auftreten kann.
Hat da jemand noch eine gute Idee gehabt?
Ich verstehe nicht ganz, was das static an der Sichtbarkeit aendert? Ich haette hier naemlich auch auf ein Sichtbarkeitsproblem getippt und gesagt, dass die while()-Schleife unter Umstaenden nie sieht, dass pay() true in die Array-Felder geschrieben hat.
Nun ich hatte es so wie Lemur verstanden und gedacht, dass durch die zwei getrennten Klassen jeder Philosopher-Thread mit dem Aufruf der statischen Methode der Klasse Dinner auch die Ausführung im Datenbereich der Klasse-Dinner startet.
Dem wird wohl nicht so sein, da es ansonsten nicht als Klausur-Aufgabe gestellt worden wäre. Andere Fehlerquellen sind mir ja nicht offensichtlich, weshalb mein Verständnis der static-Ausführung einfach falsch ist.
Ich habe das ganze zwar getestet und keine Veklemmung bei mehreren Ausführungen feststellen können, aber das ist sowieso ein Fehler den man nur auf manchen JVMs beobachten kann und der deshalb schwer zu detektieren ist, wenn man nicht tiefes Verständnis der Java-Ausführung besitzt.
Und trotzdem müssen alle Threads wissen, dass jetzt true an einer bestimmten Stelle im Array steht und genau das garantiert dir ein einfaches Boolean-Array eben nicht. Deshalb kann es passieren, dass alle Threads darauf warten, dass die Werte im Array true werden, da diese ihren Cache aber nicht aktualisieren, werden sie Änderungen nicht erkennen. Durch eine Atomic-Datenstruktur könnte man dieses Problem eben beheben.
Static hat mit Sichtbarkeitsproblemen nichts zu tun. Static deklariert in diesem Fall eine Klassen-Methode, die ausgeführt werden kann, ohne dass eine Instanz dieser Klasse existieren musst (Klassenname.methodenName()). Dabei kann es aber genauso zu Sichtbarkeitsproblemen kommen, wie bei non-static Methoden. Static hat mit Paralleler Programmierung nichts zu tun ;).
Alle Threads? Ich denke, der einzige der davon Wind bekommen sollte, ist der main Thread, damit er aus der While Schleife kommt.
Ich habe es selber noch nicht getestet, aber wenn Fertu schreibt, dass es zu keiner Verklemmung kommt, vermute ich, dass der main-Thread mitbekommen hat, dass die Werte in paid sich geändert haben.
Natürlich wissen die einzelnen Philosophen(Threads) nix davon, was in dem paid steht, aber das braucht die doch nicht zu interessieren. Also SIchtbarkeitsprobleme scheinen mir nicht der Grund zu sein.
Hat jemand eine Erklärung?
Ja in dieser Aufgabe ist es nur der Main-Thread, der das mitbekommen sollte. Es aber nicht mitbekommen muss, weil der Cache evtl. nie aktualisiert wird.
Wenn es bei ein paar Mal ausprobieren nicht zu einer Verklemmung kommt, dann muss das wohl unmöglich sein. Wahrscheinlich hast du Recht und die Aufgabe war damals einfach fehlerhaft gestellt. Ignoriere die Teilaufgabe einfach ;).
Sie sind es aber ;). Natürlich kann der Main-Thread trotzdem über Änderungen informiert werden. Es kann aber eben auch nicht passieren und wenn es 1000 Mal gut geht und ein einziges Mal schief läuft, dann kann es immer noch an Sichtbarkeitsproblemen liegen ;). Es kann eben dazu kommen, weil die Werte des Arrays nicht aktualisiert werden.
Außerdem darf der Compiler natürlich optmieren. Und eine Schleife, die die Variablen-Bedingung nicht verändert und deren Variablenbedingung einmal ausgeführt wird, lässt sich leicht zu einer while(true)-Schleife verbessern. Deshalb muss man dem Compiler eben auch mitteilen, dass eine Variable von einem anderen Thread verändert werden kann und Optmierungen daher nicht so klug sind. Das Schlüsselwort [m]volatile[/m] bewirkt genau das. Allerdings funktionier volatile in diesem Fall nicht, weil nur die Referenz auf das Array als volatile definiert werden würde. Jede einzelne Array-Element kann ggf. immer noch veraltet im Cache stehen. Daher braucht man hier eben ein Atomic-Array, das auch für Sichtbarkeit in den einzelnen Elementen sorgt.
Dieser Code stellt das Problem nach und bei mir kommt es zu einer Verklemmung. So verkehrt war die Aufgabe wohl doch nicht ;).
public class MyThreads {
public static int threads = 10;
public static CyclicBarrier barrier;
public static boolean[] paid;
public static class MyRunnable implements Runnable
{
private int id;
MyRunnable( int id )
{
this.id = id;
}
public void run()
{
paid[id] = true;
try {
barrier.await();
} catch (InterruptedException | BrokenBarrierException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
public static void main( String[] args )
{
barrier = new CyclicBarrier(threads+1);
paid = new boolean[threads];
Thread[] t = new Thread[threads];
for( int i = 0; i < t.length; ++i )
new Thread( new MyRunnable(i) ).start();
for( int i = 0; i <t.length; ++i)
while( !paid[i] );
System.out.println("WAIT FOR OTHER THREADS");
try {
barrier.await();
} catch (InterruptedException | BrokenBarrierException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("DONE");
}
}Ich versuch mal das Zusammenzufassen 
Hier mal meine Loesung der Klausur vom 09.08.2011
Zusammenfassung der Loesung (Korrektur stark erwuenscht):
A1
a) falsch (sie koennen an verschiedenen Objekten synchronisiert werden)
b) MISD (bin mir nicht sicher)
c) Entzug, Zirkulaere Abhaengigkeit
d) Speedup: ¼, Effizienz: 1/12
e),f) weggelassen, da nicht relevant
A2
a) t1 t2 t3 t4
A 0 0 0 -1
B 0 -1 2 0
C 0 1 -1 0
D 1 0 0 0
E -1 0 -2 1
b) nein.
Kommt man in den Zustand [0,0,2,5,0], so kann keine Transition mehr schalten.
c) ja
Der Erreichbarkeitsgraph ist beschraenkt
A3
a)
Zeile 10: synchronized(Dinner.class) {
Zeile 16: }
b)
Zeile 29: for[Math.max(i, (i+1)%10], forks[Math.min(i,(i+1)%10]);
// Gedanke dazu: Globale Ordnung herstellen. Klappt das so?
c)
Z 10: static Object locker = new Object();
Z 55: synchronised(locker) {
Z 58: }
A6
1: (Danke hedgehogs, fand deine Loesung gut)
for(int i = 0 ; i < threads; i++){
final int threadId = i;
queues[threadId] = new LinkedBlockingQueue();
if(threads > columns) threads = columns;
int inc = columns / threads;
final int start = (i == threads - 1) ? columns: 1 + (i*inc);
final int end = (i == threads - 1) ? columns: (i+1)*inc;
}
2.1:
if(i > 0) queues[threadId-1].take();
2.2: //
queues[threadId].put(READY);
3:
for (int i = 1; i < colums; i++)
{
queues[threads-1].take();
}
Es geht um nicht-statische Methoden, die mit dem Schlüsselwort [m]synchronized[/m] versehen werden. Wie kannst du diese an verschiedenen Marken synchronisieren?
Es ist eher SIMD, weil Grafikkarten in der Regel eine Instruktion auf möglichst vielen Daten ausführen.
Hierzu nochmal die Vorlesungsfolien 05-14 bis 05-16 lesen.
Formel für Speedup ist [m]sequenzielle Laufzeit/parallele Laufzeit[/m]
Die restlichen Aufgaben habe ich mir jetzt nicht näher angesehen.
Vielen Dank