Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur 09.08.2011
Hallo Leute,
ich habe mich gestern an die Klausur vom versucht 11.08.2011 und bin an folgenden Aufgaben deutlich gescheitert:
-Aufgabe 4) n-Damen-Problem
-Aufgabe 6) Levenshtein-Distanz
bei Aufgabe 4)
habe ich versucht das in scala umzusetzen, jedoch ist mir nicht ganz klar was bei der b) gefordert ist .
also addQueen(ss)(n) soll man so aufrufen können, wobei ss eine Liste ist mit Damen-besetzungen und n gibt die Groesse der Spalten (somit die groesse des Bretts) vor, habe ich das soweit richtig verstanden?
jetzt frage ich mich, von wo komm das „m“ her?? und wie schaut die Umsetzung in Kombination der Funktion „safe“ aus?
c) wäre wahrscheinlich nur der aufruf von addQueen(ss)(n) mit ss == eine leere liste ?!
bei Aufgabe 6)
bin ich mir nicht wirklich sicher wie die Implementierung ausschaut.
zum Feld 1 steht folgendes
zuerst wollte ich die spalten aufteilen auf die anzahl der threads also : table.length/threads und der letzte Thread bekommt den Rest table.length%threads noch aufaddiert.
aber ich denke das ist hier nicht erwünscht weil das dann überhaupt nicht mehr gleichmaessig verteilt wäre wenn es z.b. 7 Spalten gibt und 8 Threads … dann hätten thread[0] bis thread[6] keine spalten und Thread[7] alle restlichen 7, stimmts?
Kann mir jemand einen trick verraten wie ich so etwas umgehe?
Feld 2 :
Jeder Thread muesste sozusagen aus einer input-queue ein READY auslesen um anfangen zu dürfen und nach vollbrachter arbeit ein READY in die output-queue hineinlegen. wobei input queues[threadID] ist und output queues[threadID+1] … letzter Thread dürfte an output nichts übergeben da es so IndexOutOfBoundsException wäre…
ist das der richtige gedanke?
Feld 3:
da bin ich eigentlich Ideenlos… ich hätte jetzt einfach nur geraten dass man t.join(); aufrufen sollte.
Ich wäre dankbar wenn man mir hier weiterhilft und eine scala Implementierung zu Aufgabe 4 wäre sehr hilfreich zum nachvollziehen! 
Die Levenshtein Distanz würde mich auch interessieren…
Meine Synchronisation an der Queue:
if( threadId != 0) {
queue[threadId - 1].take();
}// blabla
if(threadId != threads - 1){
queue[threadId].put(READY);
}Warum ist die Anzahl der Queues gleich der Anzahl der Threads? Wenn ich z.B zwei Threads habe, dann reicht doch eine Queue ?
hallo zusammen…hier mal ein lösungvorschlag für die lev-distanz (Kasten 1)
falls jemand einen fehler sieht freue ich mich über feedback
for(int i = 0 ; i < threads; i++){
final int threadId = i;
queues[threadId] = new LinkedBlockingQueue<Object>();
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;
}[quote=[hedgehogs dilemma = 42]]
hallo zusammen…hier mal ein lösungvorschlag für die lev-distanz (Kasten 1)
falls jemand einen fehler sieht freue ich mich über feedback
for(int i = 0 ; i < threads; i++){
final int threadId = i;
queues[threadId] = new LinkedBlockingQueue<Object>();
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;
}[/quote]
So ohne es mit eclipse überprüft zu haben:
Wenn threads > columns gilt, dann sind inc 0. Also von start 1 bis ende 0. Inc müsste, wenn ich mich nicht täusche,1 sein.
Der Letzte Thread arbeitet von columns bis columns. Da fehlt der Rest noch, falls columns%threads != 0 ist.
Ich finde die Aufgabe nicht gerade leicht.
stimmt, so?
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 == 0) ? 1: i*inc;
final int end = (i == threads - 1) ? columns: (i+1)*inc;
}
Hat denn jemand die Fehlersuche gemacht?
Sehe ich es richtig, dass bei c) die Verklemmung auftreten kann,
weil paid ein Boolean-Array und kein AtomicBoolean-Array ist?
Das wäre die einzige Möglichkeit, die mir einfällt, aber ich find es merkwürdig,
weil ja nicht die Variable im Thread verändert wird, sondern der Thread die
Methode der Klasse aufruft, was nach meinem Verständnis dasselbe ist, wie,
wenn in der main einfach 10 mal die methode aufgerufen wird.
Liege ich da falsch?
Mich würde auch eine Lösung für die b) interessieren. Dafür müsste doch eigentlich die Philosopher-Klasse modifziert werden? Eine andere Lösung fällt mir nicht ein.
Ich denke, da kann man einfach einen synchronized-Block (z.B. auf Dinner.lock) um die Zeile 97 machen.
ich hab da auch noch keine lösung, von der ich glaube, dass sie richtig ist, aber normal müsstest du doch prüfen, ob row != 0 ist und row != rows-1 , oder?
in der aufgabenstellung steht, dass nach jeder zeile ein READY-Object eingestellt werden muss.
zur b)
Hier kann man doch einfach durch die reihenfolge der Forks die Verklemmung lösen:
Z28: if(i == 9){ guests[i] = new Philosopher(i,forks[0], forks[9]);
Z:29 }else{ guests[i] = new Philoshopher(i, forks[i], forsk[(i+1)%10]);}@ lemur:
das sollte meiner Meinung nach eigentlich passen,
weil die for schleife ja erst bei row = 1 anfängt => 0 ist ausgelassen
und das mit rows-1 braucht man nicht, da ja die queues zwischen den columns und nicht den rows geschaltet sind
=> das von trigger sollte eigentlich stimmen …(glaub ich)
EDIT:
das nach jeder Zeile ein Ready objekt eingefügt wird ist dadurch gewährleistet das der aufruf in der schleife ist und somit pro row automatisch gemacht wird
[quote=[hedgehogs dilemma = 42]]
das nach jeder Zeile ein Ready objekt eingefügt wird ist dadurch gewährleistet das der aufruf in der schleife ist und somit pro row automatisch gemacht wird
[/quote]
achso, das müsste ja tatsächlich passen, weil ja mit take() immer die liste geleert wird und erst wieder was drin ist, wenn der thread eben eine zeile fertig bearbeitet hat, sehe ich das richtig?
also ich stell mir das ungefähr so vor
angenommen wir hätten nur zwei Spalten mit beliebig vielen Reihen und nur 1 Queue zum synchen.
Dann haben wir zwei threads A und B
A arbeitet jetzt jede Zeile ab und nach jeder Zeile packt er ein Ready Objekt in die Queue und signalisiert somit Thread B das Thread B die Zeile bearbeiten kann.
Thread B nimmt ja vor beginn jeder Zeile ein Ready Objekt aus der Queue, bzw. wartet solange bis dort eins auftaucht (Take wartet automatisch).
Der Vorteil an der Queue (im Gegensatz zu einem Exchanger) ist das Thread A beliebig schnell arbeiten kann.
Es kann also passieren angenommen wir haben 8 Zeilen, dass Thread A 5 bearbeitet und dann Thread B dran kommt und Thread B dann 2 bearbeitet, dann Thread A wieder 1 und dann Thread B 4
wenn Thread B dann bei Zeile 7 ankommt und versucht was aus der Queue zu nehmen ist diese leer, da ja thread A Zeile 7 noch nicht bearbeitet hat
=> Thread B blockiert …irgendwann kommt dann wieder Thread A dran bearbeitet Zeile 7 und packt ein Ready Objekt in die Queue
=> wenn dann wieder B dran kommt ist er immernoch dabei zu versuchen ein Ready-Objekt aus der Queue zu nehmen - diesmal mit Erfolg, da thread A ja grade ein neues reingepackt hat
=> Thread B bearbeitet dann Zeile 7
hoffe dir Erklärung macht halbwegs Sinn ^^
EDIT: aber take leert die Liste eigentlich nicht sondern nimmt immer genau 1 Objekt raus
cool, dann hab ich’s verstanden. ich habe “leeren” geschrieben, weil ich vom idealfall ausgegangen bin, dass thread A ein ready-objekt reinpackt und thread b das wieder rausnimmt, bevor thread A das nächste reinpackt.
Gibt’s Lösungsvorschläge für die c) ?
Eigentlich sind die ja die parallelisireungsaufgaben immer straight forward, aber die macht mir ganz schön schwierigkeiten
bei der c) fällt mir auch nichts besseres ein als t.join
t.join bewirkt ja das auf den thread gewartet wird (also bzw. bis er mit seiner Arbeit fertig ist)
[quote=[hedgehogs dilemma = 42]]
bei der c) fällt mir auch nichts besseres ein als t.join
t.join bewirkt ja das auf den thread gewartet wird (also bzw. bis er mit seiner Arbeit fertig ist)
[/quote]
aber die Variable t existiert ja nur in der for-schleife #1 und die ist ja da schon beendet.
EDIT: Vielleicht könnte man ja einfach innerhalb der for-schleife am ende jeder zeile ein ready-objekt speichern (also ohne die if-abfrage).
Dann könnte man wieder ein take auf das letzte array-element aufrufen.
stimmt, das hab ich nicht bedacht.
in dem fall könnte ja sowas hier klappen.
in 2.b
queue[threadId].put(READY);
in 3
for(int i = 1; i < rows; i++){
queue[threads-1].take();
}
ja, auf was besseres bin ich auch nicht gekommen.
Ja, klar. Allerdings steht in der Angabe „Sie dürfen die Klasse Philosopher NICHT ändern.“
Zur Levenshtein-2b) noch eine Ergänzung:
if(i == rows.length-1) {} else {queues[threadid+1].put(READY);}, da der letzte Thread sein Objekt ja nicht weitergeben kann.