Deadlock finden?

Hey, ich gehe grad ein paar Übungen zum Thema Paralleles Rechnen etc durch. In folgendem Abschnitt ist wohl ein potentieller Deadlock vorhanden:

Ich weiß die Objekte sind nicht initialisiert, aber nehmen wir mal an es wäre so:

public class ResourcePool<T> {
	private List<T> pool;
	private Semaphore semaphore;

	public synchronized void release(T resource) {
		pool.add(resource);
		semaphore.release();
	}

	public synchronized T require() throws InterruptedException {
		semaphore.acquire();
		return pool.remove(0);
	}

}```

und 

public class Semaphore {
private volatile int free;

public Semaphore(int size) {
	free = size;
}

public synchronized void release() {
	free++;
	notify();
}

public synchronized void acquire() {
	while (free <= 0) {
		try {
			wait();
		} catch (InterruptedException e) { /* ignore */
			e.printStackTrace();
		}
	}
	free--;
}

}```

Sooo, ich sehe, dass man jetzt praktisch 2 Locks hat, wobei man wahrscheinlich nur einen bräuchte.
Ein Deadlock könnte ja jetzt dadurch passieren, dass sich ein Thread am Semaphore locked, und ein anderer am ResourcePool und die sich irgendwie gegenseitig verklemmen.
Allerdings sehe ich nicht wirklich, wie das passieren kann, da sich ein Thread ja nur am Semaphore locken kann, wenn er schon den ResourcePool-Lock hat.

Hab da gestern länger drangesessen und es nicht wirklich gefunden. Vllt kann mir jemand sagen, wo da ein potentieller Deadlock ist?

Meine Vermutung wäre jetzt gewesen, dass sich ein Thread den ResourcePool-Lock “holt”, dann den Semaphore-Lock, und sich dann in der acquire-Methode des Semaphores “schlafen legt”.
Dann gibt er den Lock auf den Semaphore praktisch ab, hat aber immer noch den Lock auf den ResourcePool. Somit kann ein anderer Thread garnicht erst den Lock des Semaphores “bekommen” und die notify-Methode aufrufen.

Das wäre jetzt meine Vermutung, allerdings weiß ich nicht ganz genau, wie das mit den Locks läuft bei wait() etc.

Vllt kann mir da jemand helfen.

Grüße

Die Semaphore ist unsinnig implementiert. Die Semaphore sollte nicht auf sich selbst synchronisieren, sondern ein internes Lock-Objekt haben, auf dem synchronisiert wird. Ansonsten kann nicht garantiert werden, dass nicht ein Benutzer notify auf der Semaphore aufruft.
Der Deadlock wird dann auftreten, wenn alle Semaphoren akquiriert sind. Denn dann wird auf dem Semaphorenobjekt synchronisiert und release kann nicht mehr aufgerufen werden, weil es ebenfalls auf diesem Objekt synchronisiert. Folglich wird sich die Anzahl verfügbarer Semaphoren niemals wieder erhöhen und es ist zum Deadlock gekommen.

Die Umsetzung des Pools ist im übrigen auch etwas merkwürdig… Ein Pool sollte beim “Release” nicht einfach die übergebene Ressource wieder zum Pool hinzufügen, sondern die Ressourcen markieren, die vergeben wurden, und dann beim Release prüfen, ob die Ressource überhaupt Teil des Pools ist. Die Ressourcen selbst sollten über eine separate Methode hinzugefügt werden können.

Hey, danke für die Antwort.

Ja das mit dem Pool/Semaphore war nur ein Negativ-Übungsbeispiel. Die “korrekte” Implementierung sieht anders aus.

[QUOTE=cmrudolph]
Der Deadlock wird dann auftreten, wenn alle Semaphoren akquiriert sind. Denn dann wird auf dem Semaphorenobjekt synchronisiert und release kann nicht mehr aufgerufen werden, weil es ebenfalls auf diesem Objekt synchronisiert. [/QUOTE]

Kannst du das näher ausführen? (Habe nur kurz drübergeschaut, und bin gerade etwas Braindead, deswegen hab ich das “Nachdenken” jetzt mal abgekürzt, aber) wenn ein Thread ins “acquire” geht, und dann im “wait” landet, wird der Lock auf das Semaphore-Objekt ja freigegeben. D.h. ein anderer Thread KANN dann ins “release” reingehen…

Schande über mich. Du hast Recht. :o Das passiert, wenn man nur noch mit High-Level-Synchronisierung arbeitet…

Abgesehen davon, dass einige Best-Practices ignoriert werden*, sehe ich keine Fehler in der Semaphore, die den Deadlock verursachen könnten. Man könnte einen Deadlock nur provozieren, indem man als Aufrufer einfach auf der Semaphore synchronisiert und dann wait aufruft. Dann kann es vorkommen, dass nicht der richtige Thread aufwacht und das Ereignis verloren geht.

  • notify statt notifyAll, Lock-Objekt nicht gekapselt, Interrupt ignoriert statt Thread.currentThread().interrupt()

A braucht B, B braucht A, und das gleichzeitig, A ist (für B) exklusiv gesperrt, B ist (für A) exklusiv gesperrt, egal welcher Programmteil momentan ausgeführt wird,- er kann nicht auf den anderen Programmteil zugreifen — vereinfacht gesagt. A B brauchen gemeinsamen Lock.

synchronized, reentrant lock, semaphore…, zuerst muss das zu verwendende Konzept klar sein, reentrantL ist “feiner” und schneller, aber nicht eleganter.

Ja, eigentlich ist das Muster für einen “Klassischen Deadlock” recht einfach, so wie es CB beschrieben hat:

void foo()
{
    synchronized(A) {
        synchronized(B) {
            doSomething();
        }
    }
}

void bar()
{
    synchronized(B) {
        synchronized(A) {
            doSomething();
        }
    }
}

Wenn diese Methoden von zwei Threads betreten werden, und sie sich jeweils den ersten Lock schnappen, ist der Deadlock da. In der Praxis kann es aber IMHO schon SEHR schwer sein, diesen Fall “durch Draufschauen” zu erkennen, je nach Verschachtelungstiefe, Größe der synchronized-Blöcke und dem Einfluß von wait()s.

Deswegen vielleicht nochmal ganz konkret, in bezug auf diesen Fall: Soll der Deadlock da schon bei “der vorgesehenen Verwendung” auftreten können, oder ging es darum, dass man (“böswillig”) einen Deadlock provozieren könnte? Im Fall von letzterem sollte da vielleicht was zu machen sein. Das von cmrudolph schon angedeutete “synchronized(semaphore)” wäre ein heißer Kandidat, aber die ist ja erstmal private. Ansonsten wäre die Frage, WIE “böswillig” man sein dürfte - d.h. von Semaphore oder ResourcePool erben? Oder sowas irgendwelche Konstrukte wie resourcePool.release(resourcePool) oder so? (nur spontane Gedanken, wie gesagt, im Moment bin ich nicht der disziplinierteste Denker…)

Hallo Marco, ich hätte nicht gedacht, dass meine "Um"schreibung mit A und B richtig ist… das angewandte abstrakte Konzept… :S

Du hast tatsächlich A und B verwendet. Auf Klassenebene bräuchte man aber zwei Klassen mit 2 synchronisierten Methoden, 2 Objekten und Methodenaufrufen darauf.

class A [b = B;]
syn void a() {
b.b.();
}

class B [a = A;]
syn void b() {
a.a();
}

a ist gesperrt, a will b() aufrufen; gleichzeitig ist b gesperrt [und will a() aufrufen]. Fortgesetzt werden kann das Programm nicht. Jede CPU 100%.

Also muss ich zitieren, “gegenseitige Abhängigkeit”, “exklusiv gesperrt” (was immer das heißen mag,= für alle außer A a gesperrt?), “gegenseitiger Exclusion”,…

Angenommen, a() würde direkt aufgerufen werden, dann kann die Methode schon fertig sein, bevor der Thread mit b()-Aufruf aufgerufen/gestartet wird.

Summa summarum, ‘sehr schwer (“böswillig”) zu provozieren’.

Wie vermeidet man das ganze? Z. B. U. a. statische Synchronisation, darüber wurde noch ger nicht gesprochen,… Das Thema gibt es schon sehr lange.

Danke nochmal für die Antworten.
Ich glaube der potentielle Deadlock war nur unter der Voraussetzung zu “finden”, dass nur der ResourcePool zur Verfügung steht, also das man keinen direkten Zugriff auf die Semaphore Klasse hat ,)

Hey, ich push das nochmal.

Habe mir einige Resource-Pool Implementierungen angeguckt.
Eine davon, sah so ähnlich aus wie aus meinem ersten Post, nur das die release und acquire Methoden aus dem Pool nicht synchronized sind (um den Deadlock zu verhindern).

Sah also so aus:

private volatile ArrayList<T> pool;
@SuppressWarnings("deprecation")
private final Semaphore semaphore;
 
    public void release(T resource) {
        pool.add(resource);
        semaphore.release();
    }
 
    public T require() throws InterruptedException {
        semaphore.acquire();
        return pool.remove(0);
    }
 
}```
, mit der Semaphore Klasse aus dem ersten Post. In einem anderen Beispiel wurde die Semaphore Klasse aus dem Java concurrent Package genommen, aber ich denke mal, die sieht so ähnlich aus. 

Jedenfalls ist das aus meiner Sicht nicht Thread-safe. Das wait() bzw notify(), falls die Liste leer ist bzw was eingefügt wird passiert jetzt in der Semaphore-Klasse, okay.
Aber die Operationen ```pool.add(resource)``` und ```pool.remove(0)``` können ja immer noch von mehreren Threads gleichzeitig ausgeführt werden. 
Und soweit ich weiß ist die normale ArrayList nicht thread-safe. Also könnte ich mir vorstellen, dass da irgendwas schief geht, wenn zwei Threads versuchen die gleiche Resource zu nehmen bzw Resourcen gleichzeitig einzufügen. 

Hab ich da irgendwas übersehen?

du dürftest richtig liegen, also nicht mit der letzten Frage sondern all dem davor :wink:


‚resource pool java Semaphore‘
liefert als ersten Link
The Java Semaphore class: controlling a resource pool

mit passend

Note that Semaphore controls purely the number of accesses to the pool and waiting for/interrupting access to the pool; it doesn’t control how we manage synchronization when actually taking a resource from the list or putting it back. In this example, we use a ConcurrentLinkedQueue, which allows us to concurrently add to the end of the queue and take from the beginning.

Um SlaterB’s Antwort zu untermauern, schaue in die API-Doc von Semaphore: Semaphore (Java Platform SE 8 )
Dort ist ein Codebeispiel, dass Deinem Anwendungsfall sehr nahe kommt. Der Semaphor wird nicht für die Synchronisation verwendet. Die Methoden sind dort selbst synchronized.

Danke nochmal an alle. Hatte Donnerstag die Klausur und ist alles gut gelaufen :slight_smile:

Was mir grad so nebenbei eingefallen ist (total Off Topic eig):

Wenn ein Thread jetzt wait(1000); macht oder Thread.sleep(1000), wird dann eine Sekunde in „Echtzeit“ gewartet oder wird die Zeit praktisch nur runtergezählt, wenn das Java Programm auch tatsächlich ausgeführt wird, also vom OS Rechenzeit bekommt? ;o

Wenn das Programm (auf einem Single-Core, unter MS-DOS (wenn’s dafür eine VM gibt)) wirklich GAR keine Rechenzeit abbekommt, kann er weder feststellen, dass eine Sekunde rum ist, noch kann er das machen, was er nach dieser Sekunde machen soll. Ein bißchen Händewedeln: Er sollte, wie du es nanntest, eine Sekunde “Echtzeit” warten. Ob es dann 1001 oder 1002 ms sind, hängt vom Betriebssysteminternen Scheduler ab, aber wenn nicht irgendwas ganz im Argen liegt, sollte der das schon ziemlich genau hinkriegen. Wenn eine “fundiertere” (mehr mit Argumenten untermauerte) Aussage wichtig ist, würde ich da nochmal Websuchen, könnte ganz interessant sein (wenn man keine Angst vor Assemblercode hat ;))

Ich untermauere mal. Gezählt wird nicht, nur etwas gerechnet. Garantiert wird 1 sek gewartet. Es kann auch mehr sein. CPU auslastung gar nicht. Es kann aber sein, alle Kerne sind mit 'was anderen beschäftigt, aktiv gewartet und Programmstellencode fortgesetzt wird dann nicht.

Also ein Thread soll nicht fertig sein, bevor ein anderer startet, dann schreibt man sleep#, um den DLo zu ‘provozieren’.

Über den Timer baustein kannst du wirklich viel nachlesen, in der Klausur hilft aber nicht.

Heißt das Ding Timer baustein?

Summa summarum, es sollte keine konstante Zeit gewartet werden, sondern ein berechneter Wert, um genau zu sein.

Viele grüße, Cyborg

Edit: Ich möchte natürlich auch 'was nachtragen:
Timerbaustein NE555 und NE556 (Schaltungen)

wenn man die verballerte Rechenzeit für den Kontextwechsel vernachlässig, dann ja

Der Task wird für mind. 1000ms aus dem aktiven Scheduling rausgenommen, verbraucht also keine bis gar keine Rechenzeit. Dann wird er dem aktiven Scheduling wieder hinzugefügt. Nach wieviel Millisekunden der Task wieder rechnen darf, ist vom verwendete Scheduler und der eigentlichen Prozessorauslastung abhängig.

Beim Kunden ist auf dem embedded Gerät ein Scheduling programmiert, wo ein Task mit einer niedrigeren Priorität nur abgearbeitet wird, wenn es keinen aktiven Task mit einer höheren Priorität gibt. Sie also alle entweder im Sleep sind oder auf I/O einer externen Hardware warten.

Also hat der Timer baustein auf dieser Ebene gar nix damit zu tun. Mit nicht Zählen meinte ich, auf Ebene Java wird schon mal gar nicht gezählt, zählen verbinde ich für mich noch mit aktiv Warten.

@Tarrew : sleep# verbraucht jedenfalls keine Rechenzeit, das wäre genau das Gegenteil, was angestrebt wird.