Напишите программу, которая наверняка зайдет в тупик [закрыто]

86

Недавно мне задали этот вопрос в интервью.

Я ответил, что тупиковая ситуация возникает, если чередование идет не так, но интервьюер настаивал на том, что можно написать программу, которая всегда будет заходить в тупик независимо от чередования.

Можем ли мы написать такую ​​программу? Вы можете указать мне на какой-нибудь пример такой программы?

user2434
источник
3
Интервьюер определенно глупый парень.
Lion
23
Интервьюер определенно не дурак. Полное понимание предмета означает, что вы должны уметь объяснять крайние случаи: заставить программу никогда не блокироваться и всегда блокироваться.
Юрий Зубарев

Ответы:

100

ОБНОВЛЕНИЕ: этот вопрос был темой моего блога в январе 2013 года . Спасибо за отличный вопрос!


Как мы можем написать программу, которая всегда будет заходить в тупик независимо от того, как запланированы потоки?

Вот пример на C #. Обратите внимание, что программа, похоже, не содержит блокировок и общих данных. У него есть только одна локальная переменная и три оператора, и все же он заходит в тупик со 100% уверенностью. Было бы сложно придумать более простую программу, которая гарантированно зайдет в тупик.

Упражнение для читателя №1: объясните, как это заходит в тупик. (Ответ в комментариях.)

Упражнение читателю №2: продемонстрируйте тот же тупик в Java. (Ответ здесь: 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() 
  { }
}
Эрик Липперт
источник
4
Мои знания теоретического C # ограничены, но я предполагаю, что загрузчик классов гарантирует, что код будет выполняться в однопоточном режиме, как в Java. Я почти уверен, что в Java Puzzlers есть похожий пример.
Voo
11
@Voo: У тебя хорошая память. Нил Гафтер - соавтор «Java Puzzlers» - и я представили более запутанную версию этого кода в нашем выступлении «C # Puzzlers» на конференции разработчиков в Осло несколько лет назад.
Эрик Липперт
41
@Lieven: статический конструктор должен запускаться не более одного раза, и он должен запускаться перед первым вызовом любого статического метода в классе. Main - это статический метод, поэтому основной поток вызывает статический ctor. Чтобы гарантировать, что он выполняется только один раз, среда CLR снимает блокировку, которая не снимается до завершения статического ctor. Когда ctor запускает новый поток, этот поток также вызывает статический метод, поэтому CLR пытается взять блокировку, чтобы узнать, нужно ли запускать ctor. Тем временем основной поток «присоединяется» к заблокированному потоку, и теперь у нас есть тупик.
Эрик Липперт
33
@artbristol: Я никогда не писал даже строчки кода Java; Не вижу причин начинать сейчас.
Эрик Липперт
4
О, я предполагал, что у вас есть ответ на свое упражнение №2. Поздравляем, вы получили столько голосов за ответ на вопрос Java.
artbristol
27

Защелка здесь гарантирует, что обе блокировки удерживаются, когда каждый поток пытается заблокировать другой:

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, которая правильно покажет вам тупик на вкладке Threads.

artbristol
источник
3
На данный момент это лучший вариант, но я бы заменил его sleepна подходящую защелку: теоретически здесь есть состояние гонки. Хотя мы можем быть почти уверены, что 0,5 секунды достаточно, это не слишком хорошо для задания на собеседовании.
alf
25

Взаимоблокировка возникает, когда потоки (или что-то другое ваша платформа называет своими исполнительными модулями) получают ресурсы, при этом каждый ресурс может удерживаться только одним потоком за раз, и удерживает эти ресурсы таким образом, что удержания не могут быть вытеснены, и между потоками существует некоторая «круговая» взаимосвязь, так что каждый поток в тупике ожидает получения некоторого ресурса, удерживаемого другим потоком.

Таким образом, простой способ избежать взаимоблокировки - это упорядочить ресурсы и ввести правило, согласно которому ресурсы всегда будут получать только потоки по порядку . И наоборот, тупиковая ситуация может быть создана намеренно путем запуска потоков, которые получают ресурсы, но не получают их по порядку. Например:

Две нити, два замка. Первый поток запускает цикл, который пытается получить блокировки в определенном порядке, второй поток запускает цикл, который пытается получить блокировки в обратном порядке. Каждый поток снимает обе блокировки после успешного получения блокировок.

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();
    }
}
Грег Мэттес
источник
3
Извините за цитату Линуса: «Говорить дешево. Покажи мне код» - это хорошая задача, и она на удивление сложнее, чем кажется.
alf
2
Этот код можно запустить без тупика
Владимир Жиляев
1
Хорошо, ребята, вы жестокие, но я думаю, что это полный ответ.
Грег Мэттес
@GregMattes, спасибо :) Ничего не могу добавить, кроме +1, и надеюсь, вам было весело :)
alf
15

Вот пример 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();      
    }

}
Юрий Зубарев
источник
4
Я думаю, что использование метода join in run немного вводит в заблуждение. Это предполагает, что это другое соединение, помимо соединения в статическом блоке, необходимо для получения тупиковой ситуации, в то время как тупиковая ситуация вызвана оператором «new Lock ()». Моя переписывание с использованием статического метода, как в примере C #: stackoverflow.com/a/16203272/2098232
luke657
Не могли бы вы объяснить свой пример?
gstackoverflow
согласно моим экспериментам t.join (); метод внутри run () избыточен
gstackoverflow
Я удалил
лишний
11

Вот пример из документации:

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();
    }
}
ОблачноМрамор
источник
2
+1 За линковку java-туториала.
mre
4
«очень вероятно» недостаточно для «наверняка зайдет в тупик»
alf
1
@alf О, но фундаментальная проблема здесь довольно хорошо продемонстрирована. Можно написать планировщик циклического перебора, который предоставляет Object invokeAndWait(Callable task)метод. Тогда все, Callable t1что нужно сделать, это invokeAndWait()в Callable t2течение его жизни до возвращения, и наоборот.
user268396
2
@ user268396 ну, фундаментальная проблема тривиальна и скучна :) Вся суть задачи состоит в том, чтобы выяснить - или доказать, что вы понимаете, - что на удивление сложно получить гарантированный тупик (а также гарантировать что-либо в асинхронном мире ).
alf
4
@bezz sleep- это скучно. Хотя я верю, что ни один поток не будет запускаться в течение 5 секунд, в любом случае это состояние гонки. Вы же не хотите нанимать программиста, который будет полагаться на sleep()решение условий гонки :)
alf
9

Я переписал Java-версию примера тупика Юрия Зубарева, опубликованную Эриком Липпертом: https://stackoverflow.com/a/9286697/2098232, чтобы он больше напоминал версию C #. Если блок инициализации Java работает аналогично статическому конструктору C # и сначала получает блокировку, нам не нужен другой поток, чтобы также вызвать метод соединения для получения тупиковой ситуации, ему нужно только вызвать некоторый статический метод из класса Lock, как в исходном C # пример. Возникший тупик, кажется, подтверждает это.

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");
    }

}
luke657
источник
почему, когда я комментирую Lock.initialize () в методе выполнения, он не блокируется? хотя метод инициализации ничего не делает ??
Aequitas
@Aequitas - это всего лишь предположение, но метод может быть оптимизирован; не уверен, как это будет работать с потоками
Дэйв Кузино,
5

Это непростое задание на собеседование: в моем проекте оно парализовало работу команды на целый день. Очень легко остановить вашу программу, но очень сложно привести ее в состояние, когда дамп потока записывает что-то вроде,

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 (у меня такое же, только разные объекты в качестве мониторов) хорошее, но длинное и использует новые примитивы параллелизма, чтобы привести потоки в правильное состояние, что не так уж и весело:

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. Я не думаю, что общая идея такая сложная (убедитесь, что оба потока могут продолжаться только после того, как оба заблокируют свой первый ресурс), вам просто нужно помнить CountdownLatch - но как интервьюер я бы помог интервьюируемому в этой части если бы он мог объяснить, что именно ему нужно (это не тот курс, который когда-либо нужен большинству разработчиков, и вы не можете найти его в Google на интервью). Я бы хотел получить такие интересные вопросы для интервью!
Voo
@Voo в то время, когда мы играли с ним, в JDK не было защелок, поэтому все это было вручную. И разница между LOCKEDи waiting to lockтонкая, это не то, что вы читаете во время завтрака. Но что ж, вы, наверное, правы. Позвольте перефразировать.
alf
4

Думаю, эта версия C # должна быть похожей на Java.

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

    Console.WriteLine("Press Any key");
    Console.ReadKey();
}
gemasp
источник
2
Хороший! Поистине самая короткая программа на C # для создания тупиковой ситуации при удалении consoleоператоров. Вы можете просто написать всю Mainфункцию как Thread.CurrentThread.Join();.
RBT
3
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.

Даниэль Треббиен
источник
3
} catch (InterruptedException ex) { continue; }... красиво
artbristol
2

Здесь есть пример на Java

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

Когда похититель попадает в тупик, когда он отказывается отдать жертву до тех пор, пока он не получит деньги, но переговорщик отказывается отдать деньги, пока он не получит жертву.

Тоби
источник
Эта реализация не подходит как дано. Некоторые фрагменты кода отсутствуют. Однако общая идея, которую вы выражаете, верна в том, что касается конфликта ресурсов, ведущего к тупиковой ситуации.
Master Chief
пример носит педагогический характер, поэтому мне любопытно, почему вы интерпретируете его как неуместное ... отсутствующий код - это пустые методы, в которых имена методов должны быть полезными (но не показаны для краткости)
Тоби,
1

Простой поиск дал мне следующий код:

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

bchetty
источник
3
«очень вероятно» недостаточно для «наверняка зайдет в тупик»
alf
1

Вот пример, в котором один поток, удерживающий блокировку, запускает другой поток, которому нужна такая же блокировка, а затем стартер ждет, пока запуск не завершится ... навсегда:

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();
    }
}
Виктор Сорокин
источник
0

Вот пример:

два потока работают, каждый ожидает, пока другой снимет блокировку

открытый класс 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();
            }
        }

    }


}

}

Выполнение этого приведет к тупику:

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);


}

}

Правин Кумар
источник