Proste przykłady impasu

92

Chciałbym wyjaśnić początkującym wątki zakleszczeń. Widziałem w przeszłości wiele przykładów zakleszczeń, niektóre wykorzystujące kod, a niektóre wykorzystujące ilustracje (jak słynne 4 samochody ). Istnieją również klasyczne problemy , które można łatwo zablokować, takie jak The Dining Philosophers , ale mogą one być zbyt złożone, aby prawdziwy nowicjusz mógł je w pełni zrozumieć.

Szukam najprostszego przykładu kodu, aby zilustrować, czym są zakleszczenia. Przykład powinien:

  1. Odnoszą się do „prawdziwego” scenariusza programowania, który ma jakiś sens
  2. Pisz bardzo krótko, prosto i prosto do przodu

Co polecasz?

Roee Adler
źródło
dlaczego nie skorzystać ze słynnych 4 samochodów, ponieważ wydaje mi się to całkiem proste.
Vehomzzz
2
Cztery samochody nie są scenariuszem programowania, a dla początkującego nie jest rzeczą trywialną abstrakcję problemu w postaci czterech samochodów. Używam ich, ale chcę pokazać scenariusz programowania, w którym występuje zakleszczenie.
Roee Adler

Odpowiedzi:

139

Może prosta sytuacja w banku.

class Account {
  double balance;

  void withdraw(double amount){
     balance -= amount;
  } 

  void deposit(double amount){
     balance += amount;
  } 

   void transfer(Account from, Account to, double amount){
        sync(from);
        sync(to);

        from.withdraw(amount);
        to.deposit(amount);

        release(to);
        release(from);
    }

}

Oczywiście, gdyby istniały dwa wątki, które będą próbowały uruchomić transfer ( a, b ) i transfer ( b, a ) w tym samym czasie, nastąpi impas, ponieważ będą próbowały pozyskać zasoby w odwrotnej kolejności.

Ten kod jest również świetny do szukania rozwiązań dla zakleszczenia. Mam nadzieję że to pomoże!

AAA
źródło
1
Byłoby idealnie, gdybyś ty lub ktoś inny mógł znaleźć rozwiązanie tego problemu.
Jacky,
2
@Jacky Rozwiązanie tego problemu zostało opublikowane przez Willa Hartunga tutaj: stackoverflow.com/questions/13326861/avoid-deadlock-example/…
Piotr Chojnacki
2
Jestem zdezorientowany twoją składnią. Co to jest metoda sync ()? Zrozumiałbym, gdybyś zsynchronizował (z); ... zwolnij (z); zostały zastąpione synchronizowanymi (z) {...}
Ellen Spertus
1
@espertus syncmoże być coś takiego: sync(Account & a) { a.mutex.lock(); }.
vladon
1
javaworld.com/article/2075692/java-concurrency/… (Brian Goetz) wyjaśnia rozwiązanie tego problemu.
lingareddyk
59

Niech natura wyjaśni impas,

Deadlock: Frog vs. Snake

„Bardzo chciałbym zobaczyć, jak się rozeszli, ale byłem wykończony” - powiedział fotograf. „Żaba cały czas próbowała odciągnąć węża, ale wąż po prostu nie chciał puścić” .

wprowadź opis obrazu tutaj

Nick Dandoulakis
źródło
59
Ładny, ale nie wyjaśnia, w jaki sposób zakleszczenia występują w kontekście programowania.
jalf,
ok, jalf, przynajmniej uzasadniłeś głos przeciw. W każdym razie jest podobny do przykładu „4 samochody”. Słodkie reprezentacja jak zakleszczenie wygląda.
Nick Dandoulakis
@Nick Dandoulakis: Doskonała prezentacja graficzna. Zdjęcie wyjaśnia koncepcję impasu
Rasmi Ranjan Nayak
@NickDandoulakis - Nie jest to dobry przykład obrazka imho. Przydałby się tutaj prosty kod.
Erran Morad
13
Jak to ma być słodkie? Jadowite węże i żaby zjadają się nawzajem i to przerażające !!!
Vikkyhacks
54

Oto przykład kodu z wydziału informatyki uniwersytetu na Tajwanie, przedstawiający prosty przykład w języku Java z blokowaniem zasobów. To jest dla mnie bardzo istotne w „prawdziwym życiu”. Kod poniżej:

/**
 * Adapted from The Java Tutorial
 * Second Edition by Campione, M. and
 * Walrath, K.Addison-Wesley 1998
 */

/**
 * This is a demonstration of how NOT to write multi-threaded programs.
 * It is a program that purposely causes deadlock between two threads that
 * are both trying to acquire locks for the same two resources.
 * To avoid this sort of deadlock when locking multiple resources, all threads
 * should always acquire their locks in the same order.
 **/
public class Deadlock {
  public static void main(String[] args){
    //These are the two resource objects 
    //we'll try to get locks for
    final Object resource1 = "resource1";
    final Object resource2 = "resource2";
    //Here's the first thread.
    //It tries to lock resource1 then resource2
    Thread t1 = new Thread() {
      public void run() {
        //Lock resource 1
        synchronized(resource1){
          System.out.println("Thread 1: locked resource 1");
          //Pause for a bit, simulating some file I/O or 
          //something. Basically, we just want to give the 
          //other thread a chance to run. Threads and deadlock
          //are asynchronous things, but we're trying to force 
          //deadlock to happen here...
          try{ 
            Thread.sleep(50); 
          } catch (InterruptedException e) {}

          //Now wait 'till we can get a lock on resource 2
          synchronized(resource2){
            System.out.println("Thread 1: locked resource 2");
          }
        }
      }
    };

    //Here's the second thread.  
    //It tries to lock resource2 then resource1
    Thread t2 = new Thread(){
      public void run(){
        //This thread locks resource 2 right away
        synchronized(resource2){
          System.out.println("Thread 2: locked resource 2");
          //Then it pauses, for the same reason as the first 
          //thread does
          try{
            Thread.sleep(50); 
          } catch (InterruptedException e){}

          //Then it tries to lock resource1.  
          //But wait!  Thread 1 locked resource1, and 
          //won't release it till it gets a lock on resource2.  
          //This thread holds the lock on resource2, and won't
          //release it till it gets resource1.  
          //We're at an impasse. Neither thread can run, 
          //and the program freezes up.
          synchronized(resource1){
            System.out.println("Thread 2: locked resource 1");
          }
        }
      }
    };

    //Start the two threads. 
    //If all goes as planned, deadlock will occur, 
    //and the program will never exit.
    t1.start(); 
    t2.start();
  }
}
Kyle Rosendo
źródło
1
Problem w tym, że nie jest to przykład z „prawdziwego życia”. Chodzi o „zasób 1” i „zasób 2” i byłoby miło powiązać to z rzeczywistym problemem programistycznym (mam na myśli, bezpośrednio użyteczne w praktyce, w odniesieniu do domeny problemowej itp.)
Jay
7
Moim zdaniem dobry przykład. Dzięki.
James Raitsev,
Ten kod wydaje się być opublikowany w kilku różnych książkach ... stackoverflow.com/a/11338853/112705
Dan J
15

Jeśli method1 () i method2 () zostaną wywołane przez dwa lub wiele wątków, istnieje duża szansa na zakleszczenie, ponieważ jeśli wątek 1 uzyska blokadę na obiekcie String podczas wykonywania metody method1 (), a wątek 2 uzyska blokadę na obiekcie Integer podczas wykonywania metody Method2 () oba będą czekać na siebie, aby zwolnić blokadę na Integer i String, aby przejść dalej, co nigdy się nie stanie.

public void method1() {
    synchronized (String.class) {
        System.out.println("Acquired lock on String.class object");

        synchronized (Integer.class) {
            System.out.println("Acquired lock on Integer.class object");
        }
    }
}

public void method2() {
    synchronized (Integer.class) {
        System.out.println("Acquired lock on Integer.class object");

        synchronized (String.class) {
            System.out.println("Acquired lock on String.class object");
        }
    }
}
Ashish Chaurasia
źródło
Szybko i prosto. Ładny.
user1068352
13

Jeden z prostych przykładów impasu, z jakim się spotkałem.

public class SimpleDeadLock {
   public static Object l1 = new Object();
   public static Object l2 = new Object();
   private int index;
   public static void main(String[] a) {
      Thread t1 = new Thread1();
      Thread t2 = new Thread2();
      t1.start();
      t2.start();
   }
   private static class Thread1 extends Thread {
      public void run() {
         synchronized (l1) {
            System.out.println("Thread 1: Holding lock 1...");
            try { Thread.sleep(10); }
            catch (InterruptedException e) {}
            System.out.println("Thread 1: Waiting for lock 2...");
            synchronized (l2) {
               System.out.println("Thread 2: Holding lock 1 & 2...");
            }
         }
      }
   }
   private static class Thread2 extends Thread {
      public void run() {
         synchronized (l2) {
            System.out.println("Thread 2: Holding lock 2...");
            try { Thread.sleep(10); }
            catch (InterruptedException e) {}
            System.out.println("Thread 2: Waiting for lock 1...");
            synchronized (l1) {
               System.out.println("Thread 2: Holding lock 2 & 1...");
            }
         }
      }
   }
}
Hemanth
źródło
Podoba mi się ten przykład. Ale dlaczego klasa SimpleDeadLock wykracza poza Thread? To nie jest konieczne.
Charmin
1
To prawie to samo, co ta odpowiedź: stackoverflow.com/a/1385868/1310566 . A co private int indexto tam robi?
Simon Forsberg
6

Oto prosty przykład w C ++ 11.

#include <mutex>    // mutex
#include <iostream> // cout 
#include <cstdio>   // getchar
#include <thread>   // this_thread, yield
#include <future>   // async
#include <chrono>   // seconds

using namespace std;
mutex _m1;
mutex _m2;

// Deadlock will occur because func12 and func21 acquires the two locks in reverse order

void func12()
{
    unique_lock<mutex> l1(_m1);
    this_thread::yield(); // hint to reschedule
    this_thread::sleep_for( chrono::seconds(1) );
    unique_lock<mutex> l2(_m2 );
}

void func21()
{
    unique_lock<mutex> l2(_m2);
    this_thread::yield(); // hint to reschedule
    this_thread::sleep_for( chrono::seconds(1) );
    unique_lock<mutex> l1(_m1);
}

int main( int argc, char* argv[] )
{
    async(func12);
    func21();
    cout << "All done!"; // this won't be executed because of deadlock
    getchar();
}
Phillip Ngan
źródło
5

Zobacz moją odpowiedź na to pytanie . Podsumowując, ilekroć dwa wątki muszą zdobyć dwa różne zasoby i robią to w różnych kolejności, możesz uzyskać zakleszczenie.

djna
źródło
2
Naprawdę nie widzę sensu w powielaniu informacji z innej odpowiedzi tutaj. Zakładam, że jeśli uważasz, że tę odpowiedź można poprawić, możesz ją samodzielnie edytować.
djna
Myślę, że ta sytuacja nazywa się „blokowaniem inwersji”. Cóż, wiem, że to się nazywa inwersja blokująca, bo tak to nazywam, ale myślę, że jest to również termin artystyczny :-)
Steve Jessop,
4

Jednym z przykładów, które przychodzą mi do głowy, jest scenariusz Stół, latarka i baterie. Wyobraź sobie latarkę i parę baterii umieszczoną na stole. Jeśli podejdziesz do tego stołu i złapiesz baterie, podczas gdy inna osoba będzie miała latarkę, oboje będziecie zmuszeni do niezręcznego wpatrywania się w siebie, czekając, kto pierwszy położy przedmiot z powrotem na stole. To jest przykład impasu. Ty i ta osoba czekacie na zasoby, ale nikt z was nie rezygnuje z ich zasobów.

Podobnie w programie, zakleszczenie występuje, gdy dwa lub więcej wątków (Ty i druga osoba) czekają na zwolnienie dwóch lub więcej blokad (latarki i baterii), a okoliczności w programie są takie, że blokady nigdy nie są zwalniane ( oboje macie jeden element układanki).

Jeśli znasz Javę, możesz przedstawić ten problem w następujący sposób:

import java.util.concurrent.locks.*;

public class Deadlock1 {

    public static class Table {

        private static Lock Flashlight = new ReentrantLock();
        private static Lock Batteries = new ReentrantLock();        

        public static void giveFlashLightAndBatteries() {
            try {
                Flashlight.lock();
                Batteries.lock();
                System.out.println("Lights on");
            } finally {
                Batteries.unlock();
                Flashlight.unlock();
            }
        }

        public static void giveBatteriesAndFlashLight() {
            try {
                Batteries.lock();
                Flashlight.lock();
                System.out.println("Lights on");
            } finally {
                Flashlight.unlock();
                Batteries.unlock();
            }
        }
    }

    public static void main(String[] args) {
        // This thread represents person one
        new Thread(new Runnable() {
            public void run() { Table.giveFlashLightAndBatteries(); }
        }).start();

        // This thread represents person two
        new Thread(new Runnable() {
            public void run() { Table.giveBatteriesAndFlashLight(); }
        }).start();
    }
}

Jeśli uruchomisz ten przykład, zauważysz, że czasami rzeczy działają dobrze i poprawnie. Ale czasami twój program po prostu niczego nie drukuje. Dzieje się tak, ponieważ jedna osoba ma baterie, a druga ma latarkę, która zapobiega włączeniu latarki, powodując impas.

Ten przykład jest podobny do przykładu podanego w samouczkach Java: http://docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html

Innym przykładem jest przykład pętli:

public class Deadlock2 {

    public static class Loop {
        private static boolean done = false;

        public static synchronized void startLoop() throws InterruptedException {
            while(!done) {
                Thread.sleep(1000);
                System.out.println("Not done");
            }
        }

        public static synchronized void stopLoop() {
            done = true;
        }

    }

    public static void main(String[] args) {
        // This thread starts the loop
        new Thread(new Runnable() {
            public void run() {
                try {
                    Loop.startLoop();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();

        // This thread stops the loop
        new Thread(new Runnable() {
            public void run() {
                Loop.stopLoop();
            }
        }).start();
    }
}

Ten przykład może albo drukować w kółko „Nieskończone”, albo w ogóle nie może drukować „Nieukończone”. Pierwsza ma miejsce, ponieważ pierwszy wątek uzyskuje blokadę klasy i nigdy jej nie zwalnia, uniemożliwiając dostęp do „stopLoop” przez drugi wątek. A ostatnia ma miejsce, ponieważ drugi wątek rozpoczął się przed pierwszym wątkiem, powodując, że zmienna „done” ma wartość true przed wykonaniem pierwszego wątku.

Y_Y
źródło
4
public class DeadLock {
    public static void main(String[] args) throws InterruptedException {
        Thread mainThread = Thread.currentThread();
        Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    mainThread.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });
        thread1.start();
        thread1.join();
    }
}
gstackoverflow
źródło
3

Uważam jednak, że problem filozofów kulinarnych jest jednym z prostszych przykładów pokazania impasu, ponieważ 4 wymagania dotyczące impasu można łatwo zilustrować na rysunku (zwłaszcza cykliczne oczekiwanie).

Uważam, że przykłady ze świata rzeczywistego są znacznie bardziej zagmatwane dla początkującego, chociaż nie mogę teraz wymyślić dobrego scenariusza ze świata rzeczywistego na szczycie mojej głowy (jestem stosunkowo niedoświadczony w zakresie współbieżności w świecie rzeczywistym).

Julson Lim
źródło
3

Niedawno zdałem sobie sprawę, że kłótnie między parami to nic innego jak impas ... gdzie zwykle jeden z procesów musi się zawiesić, aby go rozwiązać, oczywiście jest to mniej priorytetowy (Boy;)).

Oto analogia ...

Proces1: Dziewczyna (G) Proces2: Chłopiec (B)
Zasób 1: Przepraszam Zasób2 : Akceptowanie własnego błędu

Niezbędne warunki:
1. Wzajemne wykluczenie: Tylko jeden z G lub B może powiedzieć przepraszam lub zaakceptować swój błąd w danej chwili.
2. Wstrzymaj i czekaj: W jednej chwili jeden trzyma Przepraszam, a drugi Akceptując swój błąd, jeden czeka, aż Zaakceptowanie własnego błędu uwolni przepraszam, a drugi czeka, aż przepraszam, aby się uwolnić, akceptując swój błąd.
3. Brak uprzedzeń: nawet Bóg nie może zmusić B lub G do uwolnienia Przepraszam lub Akceptując własny błąd. I dobrowolnie? Czy ty żartujesz??
4. Oczekiwanie cykliczne: Ponownie, ten, kto trzyma przepraszam, czeka, aż inny zaakceptuje własne błędy, a jeden z nich akceptuje własne błędy, aby inny najpierw przeprosił. Więc to jest okrągłe.

Tak więc impas ma miejsce, gdy wszystkie te warunki obowiązują w tym samym czasie, i tak jest zawsze w walce par;)

Źródło: http://www.quora.com/Saurabh-Pandey-3/Posts/Never-ending-couple-fights-a-deadlock

i_am_saurabh
źródło
3

Jeszcze jeden prosty przykład zakleszczenia z dwoma różnymi zasobami i dwoma wątkami oczekującymi na nawzajem zwolnienie zasobu. Bezpośrednio z examples.oreilly.com/jenut/Deadlock.java

 public class Deadlock {
  public static void main(String[] args) {
    // These are the two resource objects we'll try to get locks for
    final Object resource1 = "resource1";
    final Object resource2 = "resource2";
    // Here's the first thread.  It tries to lock resource1 then resource2
    Thread t1 = new Thread() {
      public void run() {
        // Lock resource 1
        synchronized(resource1) {
          System.out.println("Thread 1: locked resource 1");

          // Pause for a bit, simulating some file I/O or something.  
          // Basically, we just want to give the other thread a chance to
          // run.  Threads and deadlock are asynchronous things, but we're
          // trying to force deadlock to happen here...
          try { Thread.sleep(50); } catch (InterruptedException e) {}

          // Now wait 'till we can get a lock on resource 2
          synchronized(resource2) {
            System.out.println("Thread 1: locked resource 2");
          }
        }
      }
    };

    // Here's the second thread.  It tries to lock resource2 then resource1
    Thread t2 = new Thread() {
      public void run() {
        // This thread locks resource 2 right away
        synchronized(resource2) {
          System.out.println("Thread 2: locked resource 2");

          // Then it pauses, for the same reason as the first thread does
          try { Thread.sleep(50); } catch (InterruptedException e) {}

          // Then it tries to lock resource1.  But wait!  Thread 1 locked
          // resource1, and won't release it 'till it gets a lock on
          // resource2.  This thread holds the lock on resource2, and won't
          // release it 'till it gets resource1.  We're at an impasse. Neither
          // thread can run, and the program freezes up.
          synchronized(resource1) {
            System.out.println("Thread 2: locked resource 1");
          }
        }
      }
    };

    // Start the two threads. If all goes as planned, deadlock will occur, 
    // and the program will never exit.
    t1.start(); 
    t2.start();
  }
}
Bhavin Shah
źródło
If all goes as planned, deadlock will occur, and the program will never exit.Czy możemy zrobić ten przykład guaranteeimpasu?
Erran Morad
To jest ten sam kod, który opublikował Kyle , po co dodawać zduplikowaną odpowiedź trzy lata po kolejnej odpowiedzi? (i dlaczego to komentuję, kolejne trzy lata później?)
Simon Forsberg,
2

Impas może nastąpić w sytuacji, gdy ktoś Girl1chce flirtować Guy2, zostaje złapany przez innego Girl2i Girl2chce flirtować z Guy1złapanym Girl1. Ponieważ obie dziewczyny czekają na siebie, stan ten nazywa się impasem.

class OuchTheGirls
{
    public static void main(String[] args)
    {
        final String resource1 = "Guy1";
        final String resource2 = "Guy2";

        // Girl1 tries to lock resource1 then resource2
        Thread Girl1 = new Thread(() ->
                                  {
                                      synchronized (resource1)
                                      {
                                          System.out.println("Thread 1: locked Guy1");

                                          try { Thread.sleep(100);} catch (Exception e) {}

                                          synchronized (resource2)
                                          {
                                              System.out.println("Thread 1: locked Guy2");
                                          }
                                      }
                                  });

        // Girl2 tries to lock Guy2 then Guy1
        Thread Girl2 = new Thread(() ->
                                  {
                                      synchronized (resource2)
                                      {
                                          System.out.println("Thread 2: locked Guy2");

                                          try { Thread.sleep(100);} catch (Exception e) {}

                                          synchronized (resource1)
                                          {
                                              System.out.println("Thread 2: locked Guy1");
                                          }
                                      }
                                  });


        Girl1.start();
        Girl2.start();
    }
}
snr
źródło
blokowanie klas typu String lub wrapper nie jest dobrą praktyką ze względu na sposób, w jaki wewnętrzne obiekty typu string i wrapper są obsługiwane w java. Wiele odniesień będzie wskazywać wewnętrznie ten sam obiekt. Lepiej jest użyć klasy Object, jeśli nie masz żadnego obiektu niestandardowego.
Lokesh
1

Problem producentów-konsumentów wraz z problemem filozofów kulinarnych jest prawdopodobnie tak prosty, jak się da. Ma też pseudokod, który to ilustruje. Jeśli są one zbyt skomplikowane dla nowicjusza, lepiej postaraj się je zrozumieć.

Michael Foukarakis
źródło
1

Wybierz najprostszy możliwy scenariusz, w którym może dojść do impasu podczas wprowadzania koncepcji do uczniów. Wymagałoby to co najmniej dwóch wątków i co najmniej dwóch zasobów (tak mi się wydaje). Celem jest zaprojektowanie scenariusza, w którym pierwszy wątek ma blokadę zasobu 1 i czeka na zwolnienie blokady zasobu 2, podczas gdy w tym samym czasie wątek drugi blokuje zasób 2 i czeka na blokada zasobu jeden do zwolnienia.

Nie ma znaczenia, jakie są podstawowe zasoby; dla uproszczenia możesz po prostu utworzyć z nich parę plików, w których oba wątki będą mogły zapisywać.

EDYCJA: Zakłada brak komunikacji między procesami poza posiadanymi blokadami.

Jon
źródło
1

Uważam, że nieco trudny do zrozumienia, czytając problem filozofów kulinarnych, impas IMHO jest w rzeczywistości związany z alokacją zasobów. Chciałbym podzielić się prostszym przykładem, w którym 2 pielęgniarki muszą walczyć o 3 elementy wyposażenia, aby wykonać zadanie. Chociaż jest napisane w Javie. Prosta metoda lock () jest tworzona w celu symulacji zachodzenia zakleszczenia, dzięki czemu można ją zastosować również w innym języku programowania. http://www.justexample.com/wp/example-of-deadlock/

Tylko przykład
źródło
1

Prosty przykład z https://docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html

public class Deadlock {

public static void printMessage(String message) {

    System.out.println(String.format("%s %s ", Thread.currentThread().getName(), message));

}

private static class Friend {

    private String name;

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

    public void bow(Friend friend) {

        printMessage("Acquiring lock on " + this.name);

        synchronized(this) {
            printMessage("Acquired lock on " + this.name);
            printMessage(name + " bows " + friend.name);
            friend.bowBack(this);
        }

    }

    public void bowBack(Friend friend) {

        printMessage("Acquiring lock on " + this.name);

        synchronized (this) {
            printMessage("Acquired lock on " + this.name);
            printMessage(friend.name + " bows back");
        }

    }

}

public static void main(String[] args) throws InterruptedException {

    Friend one = new Friend("one");
    Friend two = new Friend("two");

    new Thread(new Runnable() {
        @Override
        public void run() {
            one.bow(two);
        }
    }).start();

    new Thread(new Runnable() {
        @Override
        public void run() {
            two.bow(one);
        }
    }).start();
}

}

Wynik:

Thread-0 Acquiring lock on one 
Thread-1 Acquiring lock on two 
Thread-0 Acquired lock on one 
Thread-1 Acquired lock on two 
Thread-1 two bows one 
Thread-0 one bows two 
Thread-1 Acquiring lock on one 
Thread-0 Acquiring lock on two 

Zrzut wątku:

2016-03-14 12:20:09
Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.74-b02 mixed mode):

"DestroyJavaVM" #13 prio=5 os_prio=0 tid=0x00007f472400a000 nid=0x3783 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"Thread-1" #12 prio=5 os_prio=0 tid=0x00007f472420d800 nid=0x37a3 waiting for monitor entry [0x00007f46e89a5000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at com.anantha.algorithms.ThreadJoin$Friend.bowBack(ThreadJoin.java:102)
    - waiting to lock <0x000000076d0583a0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$Friend.bow(ThreadJoin.java:92)
    - locked <0x000000076d0583e0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$2.run(ThreadJoin.java:141)
    at java.lang.Thread.run(Thread.java:745)

"Thread-0" #11 prio=5 os_prio=0 tid=0x00007f472420b800 nid=0x37a2 waiting for monitor entry [0x00007f46e8aa6000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at com.anantha.algorithms.ThreadJoin$Friend.bowBack(ThreadJoin.java:102)
    - waiting to lock <0x000000076d0583e0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$Friend.bow(ThreadJoin.java:92)
    - locked <0x000000076d0583a0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$1.run(ThreadJoin.java:134)
    at java.lang.Thread.run(Thread.java:745)

"Monitor Ctrl-Break" #10 daemon prio=5 os_prio=0 tid=0x00007f4724211000 nid=0x37a1 runnable [0x00007f46e8def000]
   java.lang.Thread.State: RUNNABLE
    at java.net.SocketInputStream.socketRead0(Native Method)
    at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
    at java.net.SocketInputStream.read(SocketInputStream.java:170)
    at java.net.SocketInputStream.read(SocketInputStream.java:141)
    at sun.nio.cs.StreamDecoder.readBytes(StreamDecoder.java:284)
    at sun.nio.cs.StreamDecoder.implRead(StreamDecoder.java:326)
    at sun.nio.cs.StreamDecoder.read(StreamDecoder.java:178)
    - locked <0x000000076d20afb8> (a java.io.InputStreamReader)
    at java.io.InputStreamReader.read(InputStreamReader.java:184)
    at java.io.BufferedReader.fill(BufferedReader.java:161)
    at java.io.BufferedReader.readLine(BufferedReader.java:324)
    - locked <0x000000076d20afb8> (a java.io.InputStreamReader)
    at java.io.BufferedReader.readLine(BufferedReader.java:389)
    at com.intellij.rt.execution.application.AppMain$1.run(AppMain.java:93)
    at java.lang.Thread.run(Thread.java:745)

"Service Thread" #9 daemon prio=9 os_prio=0 tid=0x00007f47240c9800 nid=0x3794 runnable [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"C1 CompilerThread3" #8 daemon prio=9 os_prio=0 tid=0x00007f47240c6800 nid=0x3793 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"C2 CompilerThread2" #7 daemon prio=9 os_prio=0 tid=0x00007f47240c4000 nid=0x3792 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"C2 CompilerThread1" #6 daemon prio=9 os_prio=0 tid=0x00007f47240c2800 nid=0x3791 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"C2 CompilerThread0" #5 daemon prio=9 os_prio=0 tid=0x00007f47240bf800 nid=0x3790 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"Signal Dispatcher" #4 daemon prio=9 os_prio=0 tid=0x00007f47240be000 nid=0x378f waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"Finalizer" #3 daemon prio=8 os_prio=0 tid=0x00007f472408c000 nid=0x378e in Object.wait() [0x00007f46e98c5000]
   java.lang.Thread.State: WAITING (on object monitor)
    at java.lang.Object.wait(Native Method)
    - waiting on <0x000000076cf88ee0> (a java.lang.ref.ReferenceQueue$Lock)
    at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:143)
    - locked <0x000000076cf88ee0> (a java.lang.ref.ReferenceQueue$Lock)
    at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:164)
    at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:209)

"Reference Handler" #2 daemon prio=10 os_prio=0 tid=0x00007f4724087800 nid=0x378d in Object.wait() [0x00007f46e99c6000]
   java.lang.Thread.State: WAITING (on object monitor)
    at java.lang.Object.wait(Native Method)
    - waiting on <0x000000076cf86b50> (a java.lang.ref.Reference$Lock)
    at java.lang.Object.wait(Object.java:502)
    at java.lang.ref.Reference.tryHandlePending(Reference.java:191)
    - locked <0x000000076cf86b50> (a java.lang.ref.Reference$Lock)
    at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:153)

"VM Thread" os_prio=0 tid=0x00007f4724080000 nid=0x378c runnable 

"GC task thread#0 (ParallelGC)" os_prio=0 tid=0x00007f472401f000 nid=0x3784 runnable 

"GC task thread#1 (ParallelGC)" os_prio=0 tid=0x00007f4724021000 nid=0x3785 runnable 

"GC task thread#2 (ParallelGC)" os_prio=0 tid=0x00007f4724022800 nid=0x3786 runnable 

"GC task thread#3 (ParallelGC)" os_prio=0 tid=0x00007f4724024800 nid=0x3787 runnable 

"GC task thread#4 (ParallelGC)" os_prio=0 tid=0x00007f4724026000 nid=0x3788 runnable 

"GC task thread#5 (ParallelGC)" os_prio=0 tid=0x00007f4724028000 nid=0x3789 runnable 

"GC task thread#6 (ParallelGC)" os_prio=0 tid=0x00007f4724029800 nid=0x378a runnable 

"GC task thread#7 (ParallelGC)" os_prio=0 tid=0x00007f472402b800 nid=0x378b runnable 

"VM Periodic Task Thread" os_prio=0 tid=0x00007f47240cc800 nid=0x3795 waiting on condition 

JNI global references: 16


Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x00007f46dc003f08 (object 0x000000076d0583a0, a com.anantha.algorithms.ThreadJoin$Friend),
  which is held by "Thread-0"
"Thread-0":
  waiting to lock monitor 0x00007f46dc006008 (object 0x000000076d0583e0, a com.anantha.algorithms.ThreadJoin$Friend),
  which is held by "Thread-1"

Java stack information for the threads listed above:
===================================================
"Thread-1":
    at com.anantha.algorithms.ThreadJoin$Friend.bowBack(ThreadJoin.java:102)
    - waiting to lock <0x000000076d0583a0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$Friend.bow(ThreadJoin.java:92)
    - locked <0x000000076d0583e0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$2.run(ThreadJoin.java:141)
    at java.lang.Thread.run(Thread.java:745)
"Thread-0":
    at com.anantha.algorithms.ThreadJoin$Friend.bowBack(ThreadJoin.java:102)
    - waiting to lock <0x000000076d0583e0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$Friend.bow(ThreadJoin.java:92)
    - locked <0x000000076d0583a0> (a com.anantha.algorithms.ThreadJoin$Friend)
    at com.anantha.algorithms.ThreadJoin$1.run(ThreadJoin.java:134)
    at java.lang.Thread.run(Thread.java:745)

Found 1 deadlock.

Heap
 PSYoungGen      total 74752K, used 9032K [0x000000076cf80000, 0x0000000772280000, 0x00000007c0000000)
  eden space 64512K, 14% used [0x000000076cf80000,0x000000076d8520e8,0x0000000770e80000)
  from space 10240K, 0% used [0x0000000771880000,0x0000000771880000,0x0000000772280000)
  to   space 10240K, 0% used [0x0000000770e80000,0x0000000770e80000,0x0000000771880000)
 ParOldGen       total 171008K, used 0K [0x00000006c6e00000, 0x00000006d1500000, 0x000000076cf80000)
  object space 171008K, 0% used [0x00000006c6e00000,0x00000006c6e00000,0x00000006d1500000)
 Metaspace       used 3183K, capacity 4500K, committed 4864K, reserved 1056768K
  class space    used 352K, capacity 388K, committed 512K, reserved 1048576K
Anantha Krishnan
źródło
1

Oto jeden prosty impas w Javie. Potrzebujemy dwóch zasobów do zademonstrowania impasu. W poniższym przykładzie jeden zasób to blokada klasy (za pomocą metody synchronizacji), a drugi to liczba całkowita „i”

public class DeadLock {

    static int i;
    static int k;

    public static synchronized void m1(){
        System.out.println(Thread.currentThread().getName()+" executing m1. Value of i="+i);

        if(k>0){i++;}

        while(i==0){
            System.out.println(Thread.currentThread().getName()+" waiting in m1 for i to be > 0. Value of i="+i);
            try { Thread.sleep(10000);} catch (InterruptedException e) { e.printStackTrace(); }
        }
    }

    public static void main(String[] args) {

        Thread t1 = new Thread("t1") {
            public void run() {
                m1();
            }
        };

        Thread t2 = new Thread("t2") {
            public void run() {
                try { Thread.sleep(100);} catch (InterruptedException e) { e.printStackTrace(); }
                k++;
                m1();
            }
        };

        t1.start();
        t2.start();
    }
}
ernesto
źródło
1
public class DeadLock {

    public static void main(String[] args) {
        Object resource1 = new Object();
        Object resource2 = new Object();
        SharedObject s = new SharedObject(resource1, resource2);
        TestThread11 t1 = new TestThread11(s);
        TestThread22 t2 = new TestThread22(s);
        t1.start();
        t2.start();
    }

}

class SharedObject {
    Object o1, o2;
    SharedObject(Object o1, Object o2) {
        this.o1 = o1;
        this.o2 = o2;
    }
    void m1() {
        synchronized(o1) {
            System.out.println("locked on o1 from m1()");
            synchronized(o2) { 
                System.out.println("locked on o2 from m1()");
            }
        }
    }
    void m2() {
        synchronized(o2) {
            System.out.println("locked on o2 from m2()");
            synchronized(o1) { 
                System.out.println("locked on o1 from m2()");
            }
        }
    }
}

class TestThread11 extends Thread {
    SharedObject s;
    TestThread11(SharedObject s) {
        this.s = s;
    }
    public void run() {
        s.m1();
    }
}

class TestThread22 extends Thread {
    SharedObject s;
    TestThread22(SharedObject s) {
        this.s = s;
    }
    public void run() {
        s.m2();
    }
}
user3515327
źródło
1
Czy mógłbyś dodać jakiś tekst, aby wyjaśnić swoją odpowiedź?
Kmeixner
1

Oto prosty impas w C #.

void UpdateLabel(string text) {
   lock(this) {
      if(MyLabel.InvokeNeeded) {
        IAsyncResult res =  MyLable.BeginInvoke(delegate() {
             MyLable.Text = text;
            });
         MyLabel.EndInvoke(res);
        } else {
             MyLable.Text = text;
        }
    }
}

Jeśli pewnego dnia wywołasz to z wątku GUI, a inny wątek również to wywoła - możesz się zakleszczyć. Drugi wątek dostaje się do EndInvoke, czeka, aż wątek GUI wykona delegata podczas przytrzymywania blokady. Wątek GUI blokuje się na tym samym zamku, czekając, aż inny wątek go zwolni - czego nie zrobi, ponieważ wątek GUI nigdy nie będzie dostępny do wykonania delegata, na który czeka inny wątek. (oczywiście blokada tutaj nie jest ściśle potrzebna - podobnie jak EndInvoke, ale w nieco bardziej złożonym scenariuszu blokada może zostać nałożona przez dzwoniącego z innych powodów, powodując ten sam zakleszczenie).

nr
źródło
0
package test.concurrent;
public class DeadLockTest {
   private static long sleepMillis;
   private final Object lock1 = new Object();
   private final Object lock2 = new Object();

   public static void main(String[] args) {
       sleepMillis = Long.parseLong(args[0]);
       DeadLockTest test = new DeadLockTest();
       test.doTest();
   }

   private void doTest() {
       Thread t1 = new Thread(new Runnable() {
           public void run() {
               lock12();
           }
       });
       Thread t2 = new Thread(new Runnable() {
           public void run() {
               lock21();
           }
       });
       t1.start();
       t2.start();
   }

   private void lock12() {
       synchronized (lock1) {
           sleep();
           synchronized (lock2) {
               sleep();
           }
       }
   }

   private void lock21() {
       synchronized (lock2) {
           sleep();
           synchronized (lock1) {
               sleep();
           }
       }
   }

   private void sleep() {
       try {
           Thread.sleep(sleepMillis);
       } catch (InterruptedException e) {
           e.printStackTrace();
       }
   }
}
To run the deadlock test with sleep time 1 millisecond:
java -cp . test.concurrent.DeadLockTest 1
sun007
źródło
0
public class DeadlockProg {

    /**
     * @Gowtham Chitimi Reddy IIT(BHU);
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        final Object ob1 = new Object();
        final Object ob2 = new Object();
        Thread t1 = new Thread(){
            public void run(){
                synchronized(ob1){
                    try{
                        Thread.sleep(100);
                    }
                    catch(InterruptedException e){
                        System.out.println("Error catched");
                    }
                    synchronized(ob2){

                    }
                }

            }
        };
        Thread t2 = new Thread(){
            public void run(){
                synchronized(ob2){
                    try{
                        Thread.sleep(100);
                    }
                    catch(InterruptedException e){
                        System.out.println("Error catched");
                    }
                    synchronized(ob1){                      
                    }
                }               
            }
        };
        t1.start();
        t2.start();
    }

}
Chitimi Reddy Gowtham
źródło
0
package ForkBlur;

public class DeadLockTest {
  public static void main(String args[]) {

    final DeadLockTest t1 = new DeadLockTest();
    final DeadLockTest t2 = new DeadLockTest();

    Runnable r1 = new Runnable() {

        @Override
        public void run() {
            try {

                synchronized (t1) {
                    System.out
                            .println("r1 has locked t1, now going to sleep");
                    Thread.sleep(100);
                    System.out
                            .println("r1 has awake , now going to aquire lock for t2");
                    synchronized (t2) {
                        Thread.sleep(100);
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }

        }
    };

    Runnable r2 = new Runnable() {

        @Override
        public void run() {
            try {

                synchronized (t2) {
                    System.out
                            .println("r2 has aquire the lock of t2 now going to sleep");
                    Thread.sleep(100);
                    System.out
                            .println("r2 is awake , now going to aquire the lock from t1");
                    synchronized (t1) {
                        Thread.sleep(100);
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }

        }
    };

    new Thread(r1).start();
    new Thread(r2).start();
  }
}
user3669507
źródło
0

Stworzyłem ultra prosty przykład roboczy DeadLock: -

package com.thread.deadlock;

public class ThreadDeadLockClient {

    public static void main(String[] args) {
        ThreadDeadLockObject1 threadDeadLockA = new ThreadDeadLockObject1("threadDeadLockA");
        ThreadDeadLockObject2 threadDeadLockB = new ThreadDeadLockObject2("threadDeadLockB");

        new Thread(new Runnable() {

            @Override
            public void run() {
                threadDeadLockA.methodA(threadDeadLockB);

            }
        }).start();

        new Thread(new Runnable() {

            @Override
            public void run() {
                threadDeadLockB.methodB(threadDeadLockA);

            }
        }).start();
    }
}

package com.thread.deadlock;

public class ThreadDeadLockObject1 {

    private String name;

    ThreadDeadLockObject1(String name){
        this.name = name;
    }

    public  synchronized void methodA(ThreadDeadLockObject2 threadDeadLockObject2) {
        System.out.println("In MethodA "+" Current Object--> "+this.getName()+" Object passed as parameter--> "+threadDeadLockObject2.getName());
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        threadDeadLockObject2.methodB(this);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }   
}

package com.thread.deadlock;

public class ThreadDeadLockObject2 {

    private String name;

    ThreadDeadLockObject2(String name){
        this.name = name;
    }

    public  synchronized void methodB(ThreadDeadLockObject1 threadDeadLockObject1) {
        System.out.println("In MethodB "+" Current Object--> "+this.getName()+" Object passed as parameter--> "+threadDeadLockObject1.getName());
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        threadDeadLockObject1.methodA(this);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

W powyższym przykładzie 2 wątki wykonują zsynchronizowane metody dwóch różnych obiektów. Zsynchronizowana metoda A jest wywoływana przez obiekt threadDeadLockA, a zsynchronizowana metodaB jest wywoływana przez obiekt threadDeadLockB. W metodzie A przekazywana jest referencja do threadDeadLockB, aw metodzieB - do threadDeadLockA. Teraz każdy wątek próbuje zablokować inny obiekt. W metodzie A wątek, który trzyma blokadę na threadDeadLockA, próbuje uzyskać blokadę na obiekcie threadDeadLockB i podobnie w metodzieB wątek, który trzyma blokadę na threadDeadLockB, próbuje uzyskać blokadę na threadDeadLockA. W ten sposób oba wątki będą czekać wiecznie, tworząc impas.

Goyal Vicky
źródło
0

Pozwólcie, że wyjaśnię to jaśniej na przykładzie mającym więcej niż 2 wątki.

Powiedzmy, że masz n wątków, z których każdy posiada odpowiednio zamki L1, L2, ..., Ln. Teraz powiedzmy, zaczynając od wątku 1, każdy wątek próbuje uzyskać blokadę wątku sąsiedniego. Tak więc, wątek 1 zostaje zablokowany przy próbie uzyskania L2 (ponieważ właścicielem L2 jest wątek 2), wątek 2 zostaje zablokowany dla L3 i tak dalej. Wątek n zostaje zablokowany dla L1. Jest to teraz impas, ponieważ żaden wątek nie jest w stanie wykonać.

class ImportantWork{
   synchronized void callAnother(){     
   }
   synchronized void call(ImportantWork work) throws InterruptedException{
     Thread.sleep(100);
     work.callAnother();
   }
}
class Task implements Runnable{
  ImportantWork myWork, otherWork;
  public void run(){
    try {
      myWork.call(otherWork);
    } catch (InterruptedException e) {      
    }
  }
}
class DeadlockTest{
  public static void main(String args[]){
    ImportantWork work1=new ImportantWork();
    ImportantWork work2=new ImportantWork();
    ImportantWork work3=new ImportantWork();
    Task task1=new Task(); 
    task1.myWork=work1;
    task1.otherWork=work2;

    Task task2=new Task(); 
    task2.myWork=work2;
    task2.otherWork=work3;

    Task task3=new Task(); 
    task3.myWork=work3;
    task3.otherWork=work1;

    new Thread(task1).start();
    new Thread(task2).start();
    new Thread(task3).start();
  }
}

W powyższym przykładzie widać, że istnieją trzy wątki zawierające Runnablezadania task1, task2 i task3. Przed instrukcją sleep(100)wątki uzyskują blokady trzech obiektów roboczych, gdy wchodzą do call()metody (ze względu na obecność synchronized). Ale gdy tylko próbują callAnother()złapać obiekt swojego sąsiada, zostają zablokowani, co prowadzi do impasu, ponieważ zamki tych obiektów zostały już zajęte.

zafar142003
źródło
0
CountDownLatch countDownLatch = new CountDownLatch(1);
ExecutorService executorService = ExecutorService executorService = Executors.newSingleThreadExecutor();
executorService.execute(() -> {
    Future<?> future = executorService.submit(() -> {
        System.out.println("generated task");
    });
    countDownLatch.countDown();
    try {
        future.get();
    } catch (InterruptedException e) {
        e.printStackTrace();
    } catch (ExecutionException e) {
         e.printStackTrace();
    }
});


countDownLatch.await();
executorService.shutdown();
gstackoverflow
źródło
0

Podstępnym sposobem na zakleszczenie za pomocą tylko jednego wątku jest dwukrotna próba zablokowania tego samego (nierekurencyjnego) muteksu. Może to nie jest prosty przykład, którego szukałeś, ale z pewnością już napotkałem takie przypadki.

#include <mutex>
#include <iostream>

int main()
{
  std::mutex m;
  m.lock();
  m.lock();
  std::cout << "Expect never to get here because of a deadlock!";
}
rknuus
źródło
0

Oto mój szczegółowy przykład impasu po spędzeniu dużej ilości czasu. Mam nadzieję, że to pomoże :)

package deadlock;

public class DeadlockApp {

    String s1 = "hello";
    String s2 = "world";

    Thread th1 = new Thread() {
        public void run() {
            System.out.println("Thread th1 has started");
            synchronized (s1) { //A lock is created internally (holds access of s1), lock will be released or unlocked for s1, only when it exits the block Line #23
                System.out.println("Executing first synchronized block of th1!");
                try {
                    Thread.sleep(1000);
                } catch(InterruptedException ex) {
                    System.out.println("Exception is caught in th1");
                }
                System.out.println("Waiting for the lock to be released from parrallel thread th1");
                synchronized (s2) { //As another has runned parallely Line #32, lock has been created for s2
                    System.out.println(s1 + s2);
                }

            }
            System.out.println("Thread th1 has executed");
        }
    };


    Thread th2 = new Thread() {
        public void run() {
            System.out.println("Thread th2 has started");
            synchronized (s2) { //A lock is created internally (holds access of s2), lock will be released or unlocked for s2, only when it exits the block Line #44
                System.out.println("Executing first synchronized block of th2!");
                try {
                    Thread.sleep(1000);
                } catch(InterruptedException ex) {
                    System.out.println("Exception is caught in th2");
                }
                System.out.println("Waiting for the lock to be released from parrallel thread th2");
                synchronized (s1) { //As another has runned parallely Line #11, lock has been created for s1
                    System.out.println(s1 + s2);
                }

            }
            System.out.println("Thread th2 has executed");
        }
    };

    public static void main(String[] args) {
        DeadlockApp deadLock = new DeadlockApp();
        deadLock.th1.start();
        deadLock.th2.start();
        //Line #51 and #52 runs parallely on executing the program, a lock is created inside synchronized method
        //A lock is nothing but, something like a blocker or wall, which holds access of the variable from being used by others.
        //Locked object is accessible, only when it is unlocked (i.e exiting  the synchronized block)
        //Lock cannot be created for primitive types (ex: int, float, double)
        //Dont forget to add thread.sleep(time) because if not added, then object access will not be at same time for both threads to create Deadlock (not actual runtime with lots of threads) 
        //This is a simple program, so we added sleep90 to create Deadlock, it will execute successfully, if it is removed. 
    }

    //Happy coding -- Parthasarathy S
}
Parthasarathy S.
źródło