Niedawno zadawano mi te pytania w wywiadzie.
Odpowiedziałem, że zakleszczenie występuje, gdy przeplatanie przebiega nieprawidłowo, ale prowadzący wywiad nalegał, aby można było napisać program, który zawsze będzie wpadał w impas, niezależnie od przeplatania.
Czy możemy napisać taki program? Czy możesz wskazać mi jakiś przykładowy program?
Odpowiedzi:
AKTUALIZACJA: To pytanie było tematem mojego bloga w styczniu 2013 roku . Dzięki za świetne pytanie!
Jak możemy napisać program, który zawsze będzie wpadał w zakleszczenie, niezależnie od tego, jak zaplanowano wątki?
Oto przykład w C #. Zwróć uwagę, że program wydaje się nie zawierać żadnych blokad ani udostępnionych danych. Ma tylko jedną zmienną lokalną i trzy instrukcje, a mimo to blokuje się ze 100% pewnością. Trudno byłoby wymyślić prostszy program, który z pewnością jest zakleszczony.
Ćwiczenie dla czytelnika nr 1: wyjaśnij, w jaki sposób dochodzi do impasu. (Odpowiedź jest w komentarzach).
Ćwiczenie dla czytelnika nr 2: zademonstruj ten sam impas w Javie. (Odpowiedź jest tutaj: 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()
{ }
}
Zatrzask tutaj zapewnia, że oba zamki są trzymane, gdy każdy wątek próbuje zablokować się nawzajem:
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();
}
}
Ciekawe jest uruchomienie jconsole, które poprawnie pokaże ci zakleszczenie w zakładce Wątki.
sleepodpowiednim zatrzaskiem: teoretycznie mamy tutaj stan wyścigu. Chociaż możemy być prawie pewni, że 0,5 sekundy wystarczy, to nie jest zbyt dobre na rozmowę kwalifikacyjną.
Zakleszczenie ma miejsce, gdy wątki (lub cokolwiek twoja platforma nazywa swoimi jednostkami wykonawczymi) pozyskują zasoby, gdzie każdy zasób może być utrzymywany tylko przez jeden wątek naraz i zatrzymuje te zasoby w taki sposób, że blokady nie mogą być wywłaszczone, oraz istnieje pewna „cykliczna” relacja między wątkami, tak że każdy wątek w zakleszczeniu oczekuje na pobranie zasobów przechowywanych przez inny wątek.
Tak więc prostym sposobem uniknięcia impasu jest nadanie pewnego całkowitego uporządkowania zasobów i narzucenie reguły, że zasoby są pozyskiwane tylko przez wątki w kolejności . I odwrotnie, zakleszczenie można celowo utworzyć, uruchamiając wątki, które pobierają zasoby, ale nie pozyskują ich po kolei. Na przykład:
Dwie nitki, dwa zamki. Pierwszy wątek uruchamia pętlę, która próbuje uzyskać zamki w określonej kolejności, drugi wątek uruchamia pętlę, która próbuje uzyskać zamki w odwrotnej kolejności. Każdy wątek zwalnia obie blokady po pomyślnym uzyskaniu blokad.
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();
}
}
W tym pytaniu pojawiło się kilka komentarzy, które wskazują na różnicę między prawdopodobieństwem a pewnością impasu. W pewnym sensie to rozróżnienie jest kwestią akademicką. Z praktycznego punktu widzenia z pewnością chciałbym zobaczyć działający system, który nie blokuje się z kodem, który napisałem powyżej :)
Jednak pytania podczas rozmowy kwalifikacyjnej mogą czasami mieć charakter akademicki, a to pytanie SO ma w tytule słowo „na pewno”, więc poniżej znajduje się program, który z pewnością utknął w martwym punkcie. LockerTworzone są dwa obiekty, każdy ma dwie blokady i CountDownLatchsłuży do synchronizacji między wątkami. Każdy Lockerblokuje pierwszy zamek, a następnie odlicza raz zapadkę. Kiedy obie nitki osiągną blokadę i odliczą zatrzask, przechodzą przez barierę zatrzasku i próbują uzyskać drugi zamek, ale w każdym przypadku drugi gwint już utrzymuje pożądany zamek. Ta sytuacja powoduje pewien impas.
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();
}
}
Oto przykład Java, naśladując przykład Erica Lipperta:
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();
}
}
Oto przykład z dokumentacji:
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();
}
}
Object invokeAndWait(Callable task)metodę. Wtedy wszystko Callable t1musi być zrobione invokeAndWait()przez cały Callable t2okres jego życia przed powrotem i odwrotnie.
sleepjest nudne. Chociaż wierzę, że żaden wątek nie rozpocznie się przez 5 sekund, i tak jest to stan wyścigu. Nie chcesz zatrudniać programisty, który polegałby na sleep()rozwiązywaniu warunków wyścigu :)
Przepisałem wersję Java Yuriya Zubareva przykładu zakleszczenia opublikowanego przez Erica Lipperta: https://stackoverflow.com/a/9286697/2098232, aby bardziej przypominał wersję C #. Jeśli blok inicjalizacji Java działa podobnie do konstruktora statycznego C # i najpierw uzyskuje blokadę, nie potrzebujemy innego wątku, aby również wywołać metodę join w celu uzyskania zakleszczenia, wystarczy wywołać pewną metodę statyczną z klasy Lock, taką jak oryginalny C # przykład. Wynikający z tego impas wydaje się to potwierdzać.
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");
}
}
Nie jest to najprostsze zadanie na rozmowę kwalifikacyjną, jakie można dostać: w moim projekcie sparaliżowało pracę zespołu na cały dzień. Zatrzymanie programu jest bardzo łatwe, ale bardzo trudno jest doprowadzić go do stanu, w którym zrzut wątku zapisuje coś w rodzaju:
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)
Tak więc celem byłoby uzyskanie impasu, który JVM uzna za impas. Oczywiście nie ma takiego rozwiązania
synchronized (this) {
wait();
}
będą działać w tym sensie, chociaż rzeczywiście zatrzymają się na zawsze. Poleganie na warunkach wyścigu również nie jest dobrym pomysłem, ponieważ podczas rozmowy kwalifikacyjnej zwykle chcesz pokazać coś, co działa, a nie coś, co powinno działać przez większość czasu.
Teraz sleep()rozwiązanie jest w porządku, w pewnym sensie trudno sobie wyobrazić sytuację, w której to nie działa, ale nie jest sprawiedliwe (jesteśmy w uczciwym sporcie, prawda?). Rozwiązanie @artbristol (moje jest takie samo, tylko różne obiekty jako monitory) jest fajne, ale długie i wykorzystuje nowe prymitywy współbieżności, aby uzyskać wątki we właściwym stanie, co nie jest zbyt zabawne:
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) {
}
}
}
}
Pamiętam, że synchronizedrozwiązanie -only pasuje do 11..13 linii kodu (bez komentarzy i importu), ale jeszcze nie przypomniałem sobie właściwej sztuczki. Zaktualizuję, jeśli to zrobię.
Aktualizacja: oto brzydkie rozwiązanie na 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) {
}
}
}
}
Zauważ, że zamieniamy zatrzask na monitor obiektu (używając "a"jako obiektu).
LOCKEDi waiting to lockjest subtelna, a nie coś, co czytasz podczas śniadania. Ale cóż, prawdopodobnie masz rację. Pozwólcie, że przeredaguję.
Ta wersja C #, myślę, że java powinna być całkiem podobna.
static void Main(string[] args)
{
var mainThread = Thread.CurrentThread;
mainThread.Join();
Console.WriteLine("Press Any key");
Console.ReadKey();
}
consoleinstrukcje. Możesz po prostu napisać całą Mainfunkcję jako Thread.CurrentThread.Join();.
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();
}
}
}
Program zawsze zakleszcza się, ponieważ każdy wątek czeka przy barierze na inne wątki, ale aby poczekać na barierę, wątek musi utrzymywać monitor BadRunnable.class.
} catch (InterruptedException ex) { continue; }... piękny
Tutaj jest przykład w Javie
http://baddotrobot.com/blog/2009/12/24/deadlock/
Kiedy porywacz wpada w impas, gdy odmawia oddania ofiary, dopóki nie otrzyma gotówki, ale negocjator odmawia oddania gotówki, dopóki nie dostanie ofiary.
Proste wyszukiwanie dało mi następujący kod:
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();
}
}
Źródło: Deadlock
Oto przykład, w którym jeden wątek przytrzymujący blokadę uruchamia inny wątek, który chce tej samej blokady, a następnie starter czeka, aż rozpoczęty zakończy się ... na zawsze:
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();
}
}
Oto przykład:
działają dwa wątki, każdy czeka, aż drugi zwolni blokadę
public class ThreadClass rozszerza 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();
}
}
}
}
}
Uruchomienie tego doprowadziłoby do impasu:
public class 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);
}
}