Недавно я задал эти вопросы в интервью.
Я ответил, что тупик возникает, если чередование идет не так, но интервьюер настаивал на том, что программа, которая всегда будет заходить в тупик, независимо от перемежения, может быть написана.
Можем ли мы написать такую программу? Можете ли вы указать мне пример такой программы?
UPDATE: Этот вопрос был предметом моего блога в январе 2013 года. Спасибо за отличный вопрос!
Как мы можем написать программу, которая всегда будет заходить в тупик независимо от того, как запланированы потоки?
Вот пример в С#. Обратите внимание, что программа не содержит блокировок и общих данных. У нее есть только одна локальная переменная и три оператора, и все же она блокируется со 100% уверенностью. Было бы трудно придумать более простую программу, которая с уверенностью блокирует.
Упражнение для читателя # 1: объясните, как эти взаимоблокировки. (Ответ в комментариях.)
Упражнение читателю # 2: продемонстрируйте ту же тупик в Java. (Ответ здесь: fooobar.com/questions/53288/...)
class MyClass
{
static MyClass()
{
// Let 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()
{ }
}
Защелка здесь гарантирует, что обе блокировки удерживаются, когда каждый поток пытается заблокировать другое:
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();
}
}
Интересно запустить jconsole, который правильно покажет вам тупик на вкладке "Темы".
"Тупик" происходит, когда потоки (или независимо от того, какая ваша платформа вызывает свои исполнительные блоки) приобретают ресурсы, где каждый ресурс может удерживаться только одним потоком в время и удерживается на этих ресурсах таким образом, что трюмы не могут быть выгружены, и существует определенное "круговое" отношение между потоками, так что каждый поток в тупике ожидает получения некоторого ресурса, удерживаемого другим потоком.
Таким образом, простой способ избежать тупиковой ситуации - дать некоторый общий порядок ресурсов и наложить правило, что ресурсы только когда-либо приобретаются потоками в порядке. И наоборот, тупик может быть намеренно создан путем запуска потоков, которые приобретают ресурсы, но не приобретают их по порядку. Например:
Два потока, два замка. Первый поток запускает цикл, который пытается получить блокировки в определенном порядке, второй поток выполняет цикл, который пытается получить блокировки в обратном порядке. Каждый поток освобождает оба замка после успешного приобретения замков.
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();
}
}
Теперь в этом вопросе было несколько комментариев, указывающих на разницу между вероятностью и уверенностью в тупике. В каком-то смысле это различие является академическим вопросом. С практической точки зрения, мне бы очень хотелось увидеть запущенную систему, которая не зашла в тупик с кодом, который я написал выше:)
Тем не менее, вопросы интервью могут быть академическими порой, и этот вопрос SO действительно имеет слово "наверняка" в названии, так что следующее - это программа, которая, безусловно, тупиковая. Создаются два объекта Locker, каждый из которых имеет две блокировки и CountDownLatch, используемые для синхронизации между потоками. Каждый Locker блокирует первую блокировку, затем подсчитывает защелку один раз. Когда оба потока приобрели блокировку и подсчитали защелку, они проходят мимо защелки и пытаются приобрести вторую блокировку, но в любом случае другая нить уже удерживает требуемую блокировку. Эта ситуация приводит к определенному тупику.
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();
}
}
Вот пример Java, следуя примеру Эрика Липперта:
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();
}
}
Вот пример из документации:
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();
}
}
Я переписал Юрий Зубарев в Java-версии примера тупика, размещенного Эриком Липпертом: fooobar.com/questions/53288/... чтобы более близко походить на версию С#. Если блок инициализации Java работает аналогично статическому конструктору С# и сначала получает блокировку, нам не нужен другой поток, чтобы также вызывать метод join, чтобы получить взаимоблокировку, ему нужно всего лишь вызвать некоторый статический метод из класса Lock, такой как исходный С# пример. Возникающий тупик, кажется, подтверждает это.
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");
}
}
Это не самая простая задача интервью, которую вы можете получить: в моем проекте она парализовала работу команды целый день. Очень легко заставить вашу программу остановиться, но очень сложно получить ее в состоянии, где dump dump пишет что-то вроде
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)
Таким образом, целью было бы получить тупик, который JVM будет рассматривать как тупик. Очевидно, что никакое решение вроде
synchronized (this) {
wait();
}
будут работать в этом смысле, даже если они действительно прекратятся навсегда. Опираясь на состояние гонки, это тоже не очень хорошая идея, так как во время интервью вы обычно хотите показать что-то доказуемо работающее, а не то, что должно работать большую часть времени.
Теперь решение sleep() в порядке, в каком-то смысле, трудно представить себе ситуацию, когда это не сработает, но не справедливо (мы в спортивном спорте, не так ли?). Решение @artbristol (мой же, просто разные объекты в качестве мониторов) хорош, но длинный и использует новые примитивы concurrency, чтобы получить потоки в правильное состояние, что не так весело:
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) {
}
}
}
}
Напомню, что решение synchronized -only подходит для 11..13 строк кода (исключая комментарии и импорт), но еще не вспомнить об этом. Будет обновлен, если я это сделаю.
Обновление: здесь уродливое решение на 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) {
}
}
}
}
Примечание: мы заменяем защелку монитором объекта (используя "a" как объект).
Эта версия С#, я думаю, java должна быть очень похожей.
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();
}
}
}
Программа всегда тупик, потому что каждый поток ждет у барьера для других потоков, но для ожидания барьера нить должна удерживать монитор на BadRunnable.class.
Вот пример в Java здесь
http://baddotrobot.com/blog/2009/12/24/deadlock/
Если похититель попадает в тупик, когда он отказывается отказаться от жертвы, пока он не получит наличные деньги, но переговорщик отказывается сдавать деньги, пока не получит жертву.
Простой поиск дал мне следующий код:
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();
}
}
Источник: Deadlock
Здесь образец, где один фиксатор потока запускает другой поток, который хочет иметь тот же замок, а затем стартер ждет, пока он не закончится... навсегда:
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();
}
}
Вот пример:
работают два потока, каждый из которых ожидает, что другие блокируют блокировку
public class ThreadClass расширяет 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();
}
}
}
}
}
Запуск этого приведет к тупику:
открытый класс 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);
}
}