Schreiben Sie ein Programm, das sicherlich in einen Deadlock geraten wird [geschlossen]

Diese Fragen wurden mir kürzlich in einem Interview gestellt.

Ich antwortete, dass ein Deadlock auftritt, wenn das Interleaving schief geht, aber der Interviewer bestand darauf, dass ein Programm geschrieben werden kann, das unabhängig vom Interleaving immer in einen Deadlock gerät.

Können wir ein solches Programm schreiben? Können Sie mich auf ein solches Beispielprogramm verweisen?

UPDATE: Diese Frage war das Thema meines Blogs im Januar 2013 . Danke für die tolle Frage!

Wie können wir ein Programm schreiben, das immer in einen Deadlock gerät, unabhängig davon, wie die Threads geplant sind?

Hier ist ein Beispiel in C #. Beachten Sie, dass das Programm anscheinend keine Sperren und keine gemeinsam genutzten Daten enthält. Es hat nur eine einzige lokale Variable und drei Anweisungen und blockiert dennoch mit 100% iger Sicherheit. Es würde schwer fallen, ein einfacheres Programm zu entwickeln, das mit Sicherheit blockiert.

Übung für den Leser Nr. 1: Erklären Sie, wie dies blockiert. (Eine Antwort finden Sie in den Kommentaren.)

Übung für den Leser Nr. 2: Demonstrieren Sie den gleichen Deadlock in Java. (Eine Antwort finden Sie hier: https://stackoverflow.com/a/9286697/88656 )

class MyClass
{
  static MyClass() 
  {
    // Let's run the initialization on another thread!
    var thread = new System.Threading.Thread(Initialize);
    thread.Start();
    thread.Join();
  }

  static void Initialize() 
  { /* TODO: Add initialization code */ }

  static void Main() 
  { }
}

Die Verriegelung hier stellt sicher, dass beide Verriegelungen gehalten werden, wenn jeder Thread versucht, den anderen zu verriegeln:

import java.util.concurrent.CountDownLatch;

public class Locker extends Thread {

   private final CountDownLatch latch;
   private final Object         obj1;
   private final Object         obj2;

   Locker(Object obj1, Object obj2, CountDownLatch latch) {
      this.obj1 = obj1;
      this.obj2 = obj2;
      this.latch = latch;
   }

   @Override
   public void run() {
      synchronized (obj1) {

         latch.countDown();
         try {
            latch.await();
         } catch (InterruptedException e) {
            throw new RuntimeException();
         }
         synchronized (obj2) {
            System.out.println("Thread finished");
         }
      }

   }

   public static void main(String[] args) {
      final Object obj1 = new Object();
      final Object obj2 = new Object();
      final CountDownLatch latch = new CountDownLatch(2);

      new Locker(obj1, obj2, latch).start();
      new Locker(obj2, obj1, latch).start();

   }

}

Interessant, jconsole auszuführen, wodurch der Deadlock auf der Registerkarte "Threads" korrekt angezeigt wird.

Ein Deadlock tritt auf, wenn Threads (oder wie auch immer Ihre Plattform ihre Ausführungseinheiten nennt) Ressourcen erwerben, wobei jede Ressource jeweils nur von einem Thread gehalten werden kann und diese Ressourcen so hält, dass die Holds nicht vorweggenommen werden können Zwischen den Threads besteht eine "kreisförmige" Beziehung, sodass jeder Thread im Deadlock darauf wartet, eine Ressource zu erhalten, die von einem anderen Thread gehalten wird.

Eine einfache Möglichkeit, einen Deadlock zu vermeiden, besteht darin, den Ressourcen eine vollständige Reihenfolge zu geben und die Regel festzulegen, dass Ressourcen immer nur von Threads in der richtigen Reihenfolge erfasst werden . Umgekehrt kann ein Deadlock absichtlich erstellt werden, indem Threads ausgeführt werden, die Ressourcen erfassen, diese jedoch nicht in der richtigen Reihenfolge abrufen. Beispielsweise:

Zwei Fäden, zwei Schlösser. Der erste Thread führt eine Schleife aus, die versucht, die Sperren in einer bestimmten Reihenfolge abzurufen, der zweite Thread führt eine Schleife aus, die versucht, die Sperren in der entgegengesetzten Reihenfolge abzurufen. Jeder Thread gibt beide Sperren frei, nachdem die Sperren erfolgreich erworben wurden.

public class HighlyLikelyDeadlock {
    static class Locker implements Runnable {
        private Object first, second;

        Locker(Object first, Object second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public void run() {
            while (true) {
                synchronized (first) {
                    synchronized (second) {
                        System.out.println(Thread.currentThread().getName());
                    }
                }
            }
        }
    }

    public static void main(final String... args) {
        Object lock1 = new Object(), lock2 = new Object();
        new Thread(new Locker(lock1, lock2), "Thread 1").start();
        new Thread(new Locker(lock2, lock1), "Thread 2").start();
    }
}

Nun gab es einige Kommentare in dieser Frage, die auf den Unterschied zwischen der Wahrscheinlichkeit und der Gewissheit eines Deadlocks hinweisen . In gewissem Sinne ist die Unterscheidung ein akademisches Problem. Aus praktischer Sicht würde ich mir sicherlich ein laufendes System wünschen, das nicht mit dem oben geschriebenen Code blockiert ist :)

Interviewfragen können jedoch manchmal akademisch sein, und diese SO-Frage enthält das Wort "sicher" im Titel. Was folgt, ist also ein Programm, das mit Sicherheit ins Stocken gerät. Es Lockerwerden zwei Objekte erstellt, von denen jedes zwei Sperren erhält und eine CountDownLatchzum Synchronisieren zwischen den Threads verwendet wird. Jedes LockerSchloss sperrt das erste Schloss und zählt dann den Riegel einmal herunter. Wenn beide Fäden eine Verriegelung erhalten und die Verriegelung heruntergezählt haben, gehen sie an der Verriegelungsbarriere vorbei und versuchen, eine zweite Verriegelung zu erlangen, aber in jedem Fall hält der andere Faden bereits die gewünschte Verriegelung. Diese Situation führt zu einem gewissen Deadlock.

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class CertainDeadlock {
    static class Locker implements Runnable {
        private CountDownLatch latch;
        private Lock first, second;

        Locker(CountDownLatch latch, Lock first, Lock second) {
            this.latch = latch;
            this.first = first;
            this.second = second;
        }

        @Override
        public void run() {
            String threadName = Thread.currentThread().getName();
            try {
                first.lock();
                latch.countDown();
                System.out.println(threadName + ": locked first lock");
                latch.await();
                System.out.println(threadName + ": attempting to lock second lock");
                second.lock();
                System.out.println(threadName + ": never reached");
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
    }

    public static void main(final String... args) {
        CountDownLatch latch = new CountDownLatch(2);
        Lock lock1 = new ReentrantLock(), lock2 = new ReentrantLock();
        new Thread(new Locker(latch, lock1, lock2), "Thread 1").start();
        new Thread(new Locker(latch, lock2, lock1), "Thread 2").start();
    }
}

Hier ist ein Java-Beispiel, indem Sie Eric Lipperts folgen:

public class Lock implements Runnable {

    static {
        System.out.println("Getting ready to greet the world");
        try {
            Thread t = new Thread(new Lock());
            t.start();
            t.join();
        } catch (InterruptedException ex) {
            System.out.println("won't see me");
        }
    }

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }

    public void run() {           
        Lock lock = new Lock();      
    }

}

Hier ist ein Beispiel aus der Dokumentation:

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.format("%s: %s"
                + "  has bowed to me!%n", 
                this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                + " has bowed back to me!%n",
                this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); }
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); }
        }).start();
    }
}

Ich habe Yuriy Zubarevs Java-Version des von Eric Lippert veröffentlichten Deadlock-Beispiels umgeschrieben: https://stackoverflow.com/a/9286697/2098232 , um der C # -Version ähnlicher zu werden . Wenn der Initialisierungsblock von Java ähnlich wie der statische C # -Konstruktor funktioniert und zuerst die Sperre abruft, benötigen wir keinen weiteren Thread, um auch die Join-Methode aufzurufen, um einen Deadlock zu erhalten. Es muss nur eine statische Methode aus der Lock-Klasse aufgerufen werden, wie die ursprüngliche C # Beispiel. Der resultierende Deadlock scheint dies zu bestätigen.

public class Lock {

    static {
        System.out.println("Getting ready to greet the world");
        try {
            Thread t = new Thread(new Runnable(){

                @Override
                public void run() {
                    Lock.initialize();
                }

            });
            t.start();
            t.join();
        } catch (InterruptedException ex) {
            System.out.println("won't see me");
        }
    }

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }

    public static void initialize(){
        System.out.println("Initializing");
    }

}

Es ist keine einfachste Interviewaufgabe, die Sie bekommen können: In meinem Projekt hat es die Arbeit eines Teams für einen ganzen Tag gelähmt. Es ist sehr einfach, Ihr Programm zum Stoppen zu bringen, aber es ist sehr schwierig, es in den Zustand zu bringen, in dem der Thread-Dump so etwas schreibt wie:

Found one Java-level deadlock:
=============================
"Thread-2":
  waiting to lock monitor 7f91c5802b58 (object 7fb291380, a java.lang.String),
  which is held by "Thread-1"
"Thread-1":
  waiting to lock monitor 7f91c6075308 (object 7fb2914a0, a java.lang.String),
  which is held by "Thread-2"

Java stack information for the threads listed above:
===================================================
"Thread-2":
    at uk.ac.ebi.Deadlock.run(Deadlock.java:54)
    - waiting to lock <7fb291380> (a java.lang.String)
    - locked <7fb2914a0> (a java.lang.String)
    - locked <7f32a0760> (a uk.ac.ebi.Deadlock)
    at java.lang.Thread.run(Thread.java:680)
"Thread-1":
    at uk.ac.ebi.Deadlock.run(Deadlock.java:54)
    - waiting to lock <7fb2914a0> (a java.lang.String)
    - locked <7fb291380> (a java.lang.String)
    - locked <7f32a0580> (a uk.ac.ebi.Deadlock)
    at java.lang.Thread.run(Thread.java:680)

Das Ziel wäre also, einen Deadlock zu erreichen, den JVM als Deadlock betrachtet. Offensichtlich keine Lösung wie

synchronized (this) {
    wait();
}

wird in diesem Sinne funktionieren, obwohl sie in der Tat für immer aufhören werden. Sich auf eine Rennbedingung zu verlassen, ist ebenfalls keine gute Idee, da Sie während des Interviews normalerweise etwas zeigen möchten, das nachweislich funktioniert, und nicht etwas, das die meiste Zeit funktionieren sollte.

Nun, die sleep()Lösung ist in gewissem Sinne in Ordnung. Es ist schwer vorstellbar, dass es nicht funktioniert, aber nicht fair ist (wir sind in einem fairen Sport, nicht wahr?). Die Lösung von @artbristol (meine ist die gleiche, nur verschiedene Objekte als Monitore) ist nett, aber lang und verwendet die neuen Parallelitätsprimitive, um die Threads in den richtigen Zustand zu bringen, was nicht so viel Spaß macht:

public class Deadlock implements Runnable {
    private final Object a;
    private final Object b;
    private final static CountDownLatch latch = new CountDownLatch(2);

    public Deadlock(Object a, Object b) {
        this.a = a;
        this.b = b;
    }

    public synchronized static void main(String[] args) throws InterruptedException {
        new Thread(new Deadlock("a", "b")).start();
        new Thread(new Deadlock("b", "a")).start();
    }

    @Override
    public void run() {
        synchronized (a) {
            latch.countDown();
            try {
                latch.await();
            } catch (InterruptedException ignored) {
            }
            synchronized (b) {
            }
        }
    }
}

Ich erinnere mich, dass die synchronized-only-Lösung für 11..13 Codezeilen (ohne Kommentare und Importe) passt, muss mich aber noch an den eigentlichen Trick erinnern. Wird aktualisiert, wenn ich es tue.

Update: Hier ist eine hässliche Lösung für synchronized:

public class Deadlock implements Runnable {
    public synchronized static void main(String[] args) throws InterruptedException {
        synchronized ("a") {
            new Thread(new Deadlock()).start();
            "a".wait();
        }
        synchronized ("") {
        }
    }

    @Override
    public void run() {
        synchronized ("") {
            synchronized ("a") {
                "a".notifyAll();
            }
            synchronized (Deadlock.class) {
            }
        }
    }
}

Beachten Sie, dass wir einen Latch durch einen Objektmonitor ersetzen ( "a"als Objekt verwenden).

Diese C # -Version sollte Java wohl ziemlich ähnlich sein.

static void Main(string[] args)
{
    var mainThread = Thread.CurrentThread;
    mainThread.Join();

    Console.WriteLine("Press Any key");
    Console.ReadKey();
}

import java.util.concurrent.CountDownLatch;

public class SO8880286 {
    public static class BadRunnable implements Runnable {
        private CountDownLatch latch;

        public BadRunnable(CountDownLatch latch) {
            this.latch = latch;
        }

        public void run() {
            System.out.println("Thread " + Thread.currentThread().getId() + " starting");
            synchronized (BadRunnable.class) {
                System.out.println("Thread " + Thread.currentThread().getId() + " acquired the monitor on BadRunnable.class");
                latch.countDown();
                while (true) {
                    try {
                        latch.await();
                    } catch (InterruptedException ex) {
                        continue;
                    }
                    break;
                }
            }
            System.out.println("Thread " + Thread.currentThread().getId() + " released the monitor on BadRunnable.class");
            System.out.println("Thread " + Thread.currentThread().getId() + " ending");
        }
    }

    public static void main(String[] args) {
        Thread[] threads = new Thread[2];
        CountDownLatch latch = new CountDownLatch(threads.length);
        for (int i = 0; i < threads.length; ++i) {
            threads[i] = new Thread(new BadRunnable(latch));
            threads[i].start();
        }
    }
}

Das Programm blockiert immer, da jeder Thread an der Barriere auf die anderen Threads wartet. Um jedoch auf die Barriere zu warten, muss der Thread den Monitor eingeschaltet halten BadRunnable.class.

Hier gibt es ein Beispiel in Java

http://baddotrobot.com/blog/2009/12/24/deadlock/

Wenn ein Entführer in eine Sackgasse gerät, wenn er sich weigert, das Opfer aufzugeben, bis er das Geld erhält, der Verhandlungsführer sich jedoch weigert, das Geld aufzugeben, bis er das Opfer erhält.

Eine einfache Suche ergab den folgenden Code:

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.format("%s: %s"
                + "  has bowed to me!%n", 
                this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                + " has bowed back to me!%n",
                this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); }
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); }
        }).start();
    }
}

Quelle: Deadlock

Hier ist ein Beispiel, in dem eine Thread-Haltesperre einen anderen Thread startet, der dieselbe Sperre wünscht, und der Starter dann wartet, bis der Start beendet ist ... für immer:

class OuterTask implements Runnable {
    private final Object lock;

    public OuterTask(Object lock) {
        this.lock = lock;
    }

    public void run() {
        System.out.println("Outer launched");
        System.out.println("Obtaining lock");
        synchronized (lock) {
            Thread inner = new Thread(new InnerTask(lock), "inner");
            inner.start();
            try {
                inner.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

class InnerTask implements Runnable {
    private final Object lock;

    public InnerTask(Object lock) {
        this.lock = lock;
    }

    public void run() {
        System.out.println("Inner launched");
        System.out.println("Obtaining lock");
        synchronized (lock) {
            System.out.println("Obtained");
        }
    }
}

class Sample {
    public static void main(String[] args) throws InterruptedException {
        final Object outerLock = new Object();
        OuterTask outerTask = new OuterTask(outerLock);
        Thread outer = new Thread(outerTask, "outer");
        outer.start();
        outer.join();
    }
}

Hier ist ein Beispiel:

Es werden zwei Threads ausgeführt, von denen jeder darauf wartet, dass der andere die Sperre aufhebt

öffentliche Klasse ThreadClass erweitert Thread {

String obj1,obj2;
ThreadClass(String obj1,String obj2){
    this.obj1=obj1;
    this.obj2=obj2;
    start();
}

public void run(){
    synchronized (obj1) {
        System.out.println("lock on "+obj1+" acquired");

        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("waiting for "+obj2);
        synchronized (obj2) {
            System.out.println("lock on"+ obj2+" acquired");
            try {
                Thread.sleep(3000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

    }


}

}}

Das Ausführen würde zu einem Deadlock führen:

öffentliche Klasse SureDeadlock {

public static void main(String[] args) {
    String obj1= new String("obj1");
    String obj2= new String("obj2");

    new ThreadClass(obj1,obj2);
    new ThreadClass(obj2,obj1);


}

}}