Deadlock Prevention

[eQuest]

grüße Community,
ich habe vor, ein multithreaded java prog zu schreiben, welches deadlock safe ist, indem es geordnet anfordern soll. Diese Lösung ist ja weitgehend bekannt, nur mir ist sie nicht ganz klar. Habe schon etwas gegoogelt, habe aber keine zufriedenstellende und verständliche Antowort gefunden.

Ich würde euch bitten, mir dies zu erklären. Nehmen wir einfach ein Bsp.: 3 Threads, Thread 1 fordert Komponente 1 an, danach Thread 2 Komponente 2 und Thread 3 Komponente 4. Wie funktioniert zyklisches Anfordern in diesem Fall?

danke im Vorraus,

 

[Ark]

Wenn die Komponenten nicht irgendwie voneinander abhängen, könnten doch alle Threads gleichzeitig arbeiten, oder verstehe ich da gerade etwas falsch?

Ark

 

[eQuest]

ne des geht nicht, es könnte ja immer eine deadlock situation geben, (Thread 1 hat Komp 1 und will Komp 2, Thread 2 hat Komp 2 und will Komp 1 --> Deadlock )

 

[ice-breaker]

bau doch ne simple Deadlock-Detection ein

Alle Prozesse über mehrere Objekte laufen in einer "Transaktion" (hier versimpelt: ganz oder gar nicht).
Mit dem ReentrantReadWriteLock synchronisierst du dann den Zugriff, mittels tryLock immer den Lock anfordern und nem Timeout, kommt der Timeout vor dem Bekommen des Locks, weißt du, dass es einen potentiellen Deadlock gibt.
Sollte dies geschehen, dann rollst du die Transaktion zurück, wartest einen kurzen Moment (Zufallswert, macht so CSMA/CD) und beginnst die Transaktion von vorne.

 

[tfa]

Such mal nach "Dining Philisophers".
Dining Philosophers
Dining Philosophers

 

[eQuest]

@ice-breaker: ja könnte man auch mit rollbacks machen, aber ich will keine deadlock detection, sondern avoidance ich will, dass es erst garnicht dazu kommt und dies will ich auf basis zyklischen anfordern machen, (bzw wurde verlangt) und da ich dies noch nicht ganz im detail durchschaue, hätte ich gerne eine detaillierte erklärung dazu, da ich im web leider nichts passendes gefunden habe.

@tfa: Ja, bei den Philosophen geht es ja darum, dass sich 5 gleichberechtigte ausmachen, wer wann die gabeln bekommt. In meinem Fall habe ich ja mehrere Threads, die um eine Komponente bei einem "Verteiler" anfragen. Wie man diesen Verteiler im Detail so programmiert, dass er die Komponenten in einer geordneten Reihenfolge (zyklisch) verwaltet, ist mir nicht ganz klar, deshalb dieser Thread ;D

 

[eQuest]

so für leute, die sich vl. schon das selbe gefragt haben oder noch fragen werden, hier die Antwort:

Bei Deadlock Prevention per geordneter Rückgabe, wird ein "Manager" zwischengeschalten (auf java, ne klasse), der die Komponenten an die Anfragenden verteilt und zwar mit folgender Technik: Die Komponenten sind sozusagen durchnummeriert und der Manager gibt die Komponente, die gebraucht wird, zurück UND alle, die eine niedrigere Nummerierung haben, auch.
BSP.: Thread 1 fordert Komponente 3 an, Thread 2 Komp 5 und Thread 3 Komp 6 (auch in dieser Reihenfolge wird angefordert). Dann wird der Manager Thread 1 die Komponenten 1-3 zurückgeben (das können Drucker, Scanner, etc sein), Thread 2 die Komponenten 4 und 5 (vorrausgesetzt, 1,2&3 sind noch in Benutzung) und Thread 3 Komponente 6.
Diese Methodik ist Deadlock safe, aber leider nicht sehr performant, da mit einer Anforderung mehrere Komponenten möglicherweiße besetzt werden, obwohl diese garnicht benötigt werden.

Hoffe ich konnte den suchenden helfen, bei weiteren fragen zu diesem Thema oder einfach generell Deadlocks, einfach hier posten

 

[hdi]

Versteh ich nicht.

Was ist wenn Thread 1 jetzt Komponente 5 will und Thread 2 Komponente 2?
Ist doch noch immer Deadlock.

 

[eQuest]

wenn Thread 1 vor Thread 2 seine Komponente anfordert, also die 5., sind alle Komponenten bis 5 besetzt. Wenn nun Thread 2 anfordert, muss er einfach warten, bis die Komponente frei wird. In java ist das einfach ein Semaphore, der 0 ist und Thread 2 macht praktisch .aquire();. Das ist kein Deadlock ;D

 

[hdi]

Nein, nochmal:

Thread 1 will Komponente 3, der Manager weist ihm Komponenten 1-3 zu.
Thread 2 will Komponente 4, das geht ja auch.

Aber jetzt will Thread 1 Komponente 4, und Thread 2 will Komponente 2. Was macht der Manager jetzt? Ich verstehe halt nicht was an diesem System mit den Komponenten deadlock-safe sein soll.