Deadlock verstehen der Ausgabe!

[BodyLAB]

Hallo zusammen,

irgendwie verstehe ich nicht wieso mir bei folgendem Code das hier ausgegeben wird:

Alf : Karl has bowed to me!
Karl : Alf has bowed to me!

public class Deadlock {
    static class Friend {
        private final String name;

        public Friend(String name) {
            this.name = name;
        }

        public String getName() {
            return this.name;
        }

        public synchronized void bow(Friend bower) {
            System.out.println(this.name + " : " + bower.getName() + " has bowed to me!");
            bower.bowBack(this);
        }

        public synchronized void bowBack(Friend bower) {
            System.out.println(this.name + " : " + bower.getName() + " has bowed back to me!");
        }
    }

    public static void main(String[] args) {
        final Friend alf = new Friend("Alf");
        final Friend karl = new Friend("Karl");

        new Thread(new Runnable() {
            public void run() {
                alf.bow(karl);
            }
        }).start();

        new Thread(new Runnable() {
            public void run() {
                karl.bow(alf);
            }
        }).start();
    }

}

Ich bin sogar davon ausgegangen das es gar kein Deadlock ist.
Alf führt z. B. als erstes die synchronized Methode bow aus. Nun würde Friend gesperrt werden. In der Methode bow würde nun bower als Karl die nächste synchronized Methode aufrufen und als übergabe- Parameter Alf. Da diese Methoden aber reentrant sind ging ich davon aus das es im ersten Fall durchlaufen würde und somit zu keinem Deadlock kommen.

Nun zeigt mir aber die Ausgabe oben etwas ganz anderes und ich verstehe überhaupt nicht wie es zu einem Deadlock in diesem Beispiel kommen kann :-( Wieso schaffen es beide Thread Aufrufe einmal in die synchroinzed "Umgebun"? Hängen müssten diese ja dann nach System.out.println(this.name + " : " + bower.getName() + " has bowed to me!");? Falls JA aber wieso? Ich komme da nicht mehr mit :-(

 

[BodyLAB]

Nach einer Pause, denke ich habe ich es nun verstanden.
alf und karl sind unterschiedliche Objekte. Wenn nun alf erzeugt wird und der Thread startet, sperrt dieser ja nur das Objekt alf. Bei karl genau das selbe.
Betreten wir bei beiden Objekten dann die Methode bow was ja eben wie oben geschrieben funktioniert. Dort geben wir dann etwas auf der Konsole aus. Danach aber versuchen wir mit dem immer gegensätzlichen Objekt als bei alf wäre das eben karl die Methode bowBack aufzurufen. Was natürlich auch funktioniert, doch diese Funktion ist in beiden Fällen ja durch synchronized gelockt also nicht betretbar! Somit warten beide ewig (Deadlock)

 

[Robert Zenz]

Also das erste Problem hierbei ist dass es vermutlich nie zu einem Deadlock kommen wird, weil der erste Thread lange fertig ist bevor der zweite ueberhaupt erst gestartet wird. Um die Wahrscheinlichkeit zu erhoehen dass beide wirklich gleichzeitig loslaufen muesstest du diese weiter synchronisieren mit einem zusaetzlichen Objekt.

Ich habe es gerade nicht im Kopf, aber in etwa so (vereinfacht):

public synchronized bow() {
    SYNCHRONIZATION_OBJECT.wait();
}

// ---

startThread1();
startThread2();

SYNCHRONIZATION_OBJECT.notifyAll();

Ansonsten muesste der Code eigentlich ein Deadlock ergeben koennen. Aber die Wahrscheinlichkeit dass sich die beiden Aktionen einfach verpassen ist sehr, sehr, sehr, sehr, sehr gut. Idealerweise synchronisierst du die beiden Zugriffe nachdem diese die erste Sperre haben um sicher zu gehen dass nicht der eine Thread einfach zu frueh fertig wird.

 

[mihe7]

alf und karl sind unterschiedliche Objekte. Wenn nun alf erzeugt wird und der Thread startet, sperrt dieser ja nur das Objekt alf. Bei karl genau das selbe.

Ja. Wenn ein Thread T eine synchronized Methode eines Objekt O aufruft, wird T zum Besitzer des Monitors von O, falls der Monitor nicht bereits einen von T verschiedenen Besitzer hat. Ansonsten muss T warten, bis der Monitor wieder verfügbar ist.

Wenn T1 eine synchronized Methode von alf und T2 eine synchronized Methode von karl aufruft, erhält T1 den Monitor von alf und T2 den Monitor von karl. Soweit alles gut.

Versucht nun T1 eine synchronized Methode von karl aufzurufen, muss T1 warten, bis der Monitor von karl wieder zur Verfügung steht.

Wenn jetzt aber T2 eine synchronized Methode von alf aufruft, muss T2 warten, bis der Monitor von alf wieder zur Verfügung steht.

Beide Threads warten nun darauf, den jeweils anderen Monitor zu erhalten, bevor sie ihren Monitor zurückgeben -> Deadlock.

 

[BodyLAB]

Beide Threads warten nun darauf, den jeweils anderen Monitor zu erhalten, bevor sie ihren Monitor zurückgeben -> Deadlock.

Danke für die schöne ausführliche Antwort. Jetzt verstehe ich das ganze sogar noch besser.

Was ich mich frage ist wie man solche Deadlocks verhindern kann.

Anderes Code Beispiel:

public class Test {
    private String[] s1 = {"foo"};
    private String[] s2 = {"bar"};
    
    public void copy_s1_to_s2() {
        synchronized(s1) {
            synchronized(s2) {
                s2[0] = s1[0];
            }
        }
    }
    
        public void copy_s2_to_s1() {
        synchronized(s2) {
            synchronized(s1) {
                s1[0] = s2[0];
            }
        }
    }
//hier sei ein Hauptprogramm welches parallel die beiden oben angegebenen Methoden in jeweils einem Thread ausführt
}

Denn ich zerbreche mir seit Sonntag den Kopf über diese Aufgabenstellung doch dort wird verlangt

Ist die Synchronisation ausreichend, um Schreib/Schreibe- und Schreib/Lese-Konflikte auszuschließen?

Hier könnte man ja so Argumentieren, dass gehen wir davon aus es trifft nicht der Fall ein es kommt zu einem Deadlock, sämltiche Schreib-Schreib oder Schreib-Lese Konflikte beseitigt wären. Es werden immer beide Objekte gesperrt auf die geschrieben werden soll, somit kann kein weiterer Thread unserem Schreib oder Lese Vorgang in die Quere kommen und es zu keinerlei Konflikt kommt.

Warum kann es bei Ausführung des Programms zu einem Deadlock kommen? Was müsste man abändern, um dieses Problem zu vermeiden?

So gesehen ist es ja wie oben, doch so schön wie @mihe7 erklären kann ich es wohl nicht.
Was mir darüber hinaus Kopfzerbrechen macht, ist wie verbessere ich die Situation das es nicht mehr zu einem Deadlock kommen kann / kommt. Ich verstehe ja das hier über Kreuz in Synchronized Blöcken Objekte gesperrt werden. Im ersten durchlauf copy_s1_to_s2 sperrt Objekt s1 kommt direkt dahinter der zweite Thread mit dem Methode copy_s2_to_s1 und sperrt das Objekt s2 sind beide Objekte gesperrt und naja Problem.

Meine Idee wäre das "einfach" im synchronized Block steht.

  public void copy_s2_to_s1() {

        synchronized(Test.class) {

                s1[0] = s2[0];
        }
  }

Würde man dann aber die Parallelität nicht zu stark einschränken?
Meines derzeitigen Wissensstandes würde es dann wenigstens korrekt laufen ohne einen Deadlock.
Wenn man beide Methoden synchronized Kennzeichnet also so:

public class Test {
    private String[] s1 = {"foo"};
    private String[] s2 = {"bar"};
    
    public synchronized void copy_s1_to_s2() {
                s2[0] = s1[0];
    }
    
        public synchronized void copy_s2_to_s1() {
                s1[0] = s2[0];
    }
}

würde es dann auch noch laufen?
Da bin ich mir unsicher, denn ich kann mir nicht so ganz vorstellen wie das gemeint ist:

//hier sei ein Hauptprogramm welches parallel die beiden oben angegebenen Methoden in jeweils einem Thread ausführt

 

[KonradN]

Generell kommt es zu einem Deadlock, wenn mehrere Locks benötigt werden und es dabei zu "verdrehten" Reihenfolgen kommt.

Du hast jetzt einmal Locks auf A und dann zusätzlich auf B
Und einmal erst auf B und dann auf A

Und das führt zu einem Deadlock, da ein Prozess A haben kann und auf B wartet und der andere B hat und auf A wartet.

Das zeigt auch eine Bedingung für Deadlocks: Ich brauche Threads die Locks auf mehrere Monitore halten! Also hier Monitor von Objekt A und Monitor von Objekt B.

Hier könnte ein Entwickler darauf achten und z.B. immer, wenn man einen Lock auf B braucht, vorher auch A anzufordern.

Das ist aber in der Praxis so meist schlicht nicht möglich, denn wenn man dein Beispiel mit vielen Instanzen und Threads betrachtet, dann geht das so einfach nicht. Aber es kann durchaus denkbar sein, dass man hier zwei Monitore hat und man muss immer erst den ersten locken, wenn man den zweiten braucht. (der zweite enthält dann sozusagen auch den ersten. Wenn Du die Tabelle lockst, dann sind auch alle Zeilen der Tabelle gelockt. So in der Art.) Daher ist hier aus meiner Sicht die praktikable Lösung wirklich, dass man auf einem übergeordneter Elemente blockiert.

Evtl. kann man aber auch schauen, ob wirklich der gelockte Bereich so gross sein muss, wie er gewählt wurde. Evtl. wurde einfach eine Methode als synchronized markiert aber nicht alles benötigt den Lock:

        public synchronized void bow(Friend bower) {
            System.out.println(this.name + " : " + bower.getName() + " has bowed to me!");
            bower.bowBack(this);
        }

Wenn der Lock eigentlich nur für Zeile 2 gebraucht wird, dann könnte man z.B. etwas bauen wie:

        public void bow(Friend bower) {
            synchronized(this) {
                System.out.println(this.name + " : " + bower.getName() + " has bowed to me!");
            }
            bower.bowBack(this);
        }

Damit wäre so ein Deadlock auch verhindert, denn man hat nie zwei Locks auf zwei Instanzen sondern immer nur einen Lock auf eine Instanz.

 

[BodyLAB]

public void bow(Friend bower) { synchronized(this) { System.out.println(this.name + " : " + bower.getName() + " has bowed to me!"); } bower.bowBack(this); }

🥲 Solch ein Code habe ich ja schon einmal gesehen doch auf die Idee wäre ich jetzt wahrlich so schnell nicht gekommen.

Wenn ich mich als nicht ganz täusche, wäre der Deadlock mit diesem Programmcode beseitigt:

public  void bow(Friend bower) {
            System.out.println(this.name + " : " + bower.getName() + " has bowed to me!");
            synchronized(bower) {
                bower.bowBack(this);
            }
        }

        public  void bowBack(Friend bower) {
            System.out.println(this.name + " : " + bower.getName() + " has bowed back to me!");
        }

Wenn beide Threads los laufen, können sie beide die Methode bow aufrufen. Danach gewinnt aber der erste der es Schafft den Freund zu Blockieren. Dieser läuft dann zu ende und verlässt den Synchronized Bereich gibt den Lock frei und der zweite Thread könnte nun auch zu Ende laufen ;-) Problem gelöst.

Könntet Ihr vielleicht noch auf meinen Post #5 Bezug nehmen? Dort habe ich noch einen weiteren Code gepostet und verstehe nicht wie das aufgerufen werden soll. Erkennen tut man diesen Kreuzaufruf ja sofort, doch wie könnte ein solches Programm-Schnippsel aufgerufen werden. Denn anders komme ich gerade auch auf keine andere Lösung als entweder wie oben mit synchronized(Test.clss) zu synchronisieren oder man erstellt ein static Object lock; mit dem selben Effekt (synchronized(lock)).

Kann das vielleicht mir jemand noch erklären?

Außerdem habe ich eine Nachricht erhalten es sollen Vier Bedingungen um wechselseitigen Ausschluss zu ermöglichen genannt werden?
Was um alles in der Welt ist denn damit gemeint?
Ich kenne 3 Konzepte um das Problem wechselseitigen Ausschluss zu lösen: Mutex, Monitore und Semaphore
Oder ist mit Bedingung Anforderung gemeint? Dort fallen mir jetzt aber auch nur diese drei ein:
1. mutual exclusion: zu jedem Zeitpunkt darf sich höchstens ein Prozess im kritischen Bereich
2. progress – no deadlock: wechselseitiges Aufeinanderwarten muss verhindert werden
3: bounded waiting – no starvatio: bei 3 Prozessen A, B, C könnten sich z.B. A und B in der Nutzung einer kritischen Ressource immer abwechseln

 

[mihe7]

würde es dann auch noch laufen?

Ja, das ist in dem Fall praktisch das gleiche wie die Synchronisation via synchronized(this) { ... }, da die Methode ja nur diese eine Zeile enthält.

Da bin ich mir unsicher, denn ich kann mir nicht so ganz vorstellen wie das gemeint ist:

Damit dürfte einfach gemeint sein, dass es mehrere Threads gibt, die parallel laufen und eben diese Methode aufrufen.

 

[BodyLAB]

Damit dürfte einfach gemeint sein, dass es mehrere Threads gibt, die parallel laufen und eben diese Methode aufrufen.

Dann müsste ja synchronized(this) {...} oder eben die Methoden Synchronized machen ausreichend sein um das Problem zu lösen und keinen Deadlock mehr zu bekommen.

Vier Bedingungen um wechselseitigen Ausschluss zu ermöglichen

Versteht jemand noch das hier?

 

[mihe7]

Dann müsste ja synchronized(this) {...} oder eben die Methoden Synchronized machen ausreichend sein um das Problem zu lösen und keinen Deadlock mehr zu bekommen.

Selbstverständlich. Es gilt das gleiche wie vorhin: ein Thread erhält den Monitor, die anderen müssen warten, bis er wieder zurückgegeben wurde. In dem Fall gibt es aber keinen Deadlock, weil der laufende Thread auf keinen anderen wartet. Er läuft einfach durch die Methode, der Monitor wird frei und ein (womöglich) anderer Thread bekommt ihn.

 

[BodyLAB]

Ist gar nicht leicht das Thema. Danke nochmals an euch alle

Eine letzte Frage hätte ich noch steht ja schon oben, kann jemand etwas damit anfangen:
Vier Bedingungen um wechselseitigen Ausschluss zu ermöglichen
Welche Bedingungen sollen das bitte sein? Oder soll man sich vorstellen wie man so etwas teschnich angehen würde (sprich nach Programmiert)

 

[mihe7]

Ist gar nicht leicht das Thema.

Parallele Verarbeitung ist brutal schwer. Irgendwie hat man sofort einen Knopf im Hirn.

Vier Bedingungen um wechselseitigen Ausschluss zu ermöglichen

Hm... Keine Ahnung worauf man hier hinaus will, evtl:

1. Mehrere Threads,
2. die einen kritischen Abschnitt durchlaufen,
3. der mit einer Sperre versehen wird,
4. die ihrerseits atomar gesetzt/aufgehoben werden kann.

 

[BodyLAB]

Parallele Verarbeitung ist brutal schwer. Irgendwie hat man sofort einen Knopf im Hirn.

Ja, so geht es mir auch im falle von C mit Pointern :-D

1. Mehrere Threads,
2. die einen kritischen Abschnitt durchlaufen,
3. der mit einer Sperre versehen wird,
4. die ihrerseits atomar gesetzt/aufgehoben werden kann.

Danke trotzdem ich verstehe es auch nicht hehe