Escreva um programa que certamente entrará em um impasse [fechado]

Recentemente, recebi essas perguntas em uma entrevista.

Respondi que o impasse ocorre se a intercalação der errado, mas o entrevistador insistiu que um programa que sempre entrará em impasse, independentemente da intercalação, pode ser escrito.

Podemos escrever esse programa? Você pode me indicar algum programa de exemplo como esse?

ATUALIZAÇÃO: Esta questão foi o assunto do meu blog em janeiro de 2013 . Obrigado pela ótima pergunta!

Como podemos escrever um programa que sempre entrará em impasse, não importa como os threads estão agendados?

Aqui está um exemplo em C #. Observe que o programa parece não conter bloqueios e dados compartilhados. Ele tem apenas uma única variável local e três instruções e, ainda assim, bloqueia com 100% de certeza. Seria difícil chegar a um programa mais simples que travasse com certeza.

Exercício para o leitor # 1: explique como isso bloqueia. (Uma resposta está nos comentários.)

Exercício para o leitor 2: demonstrar o mesmo impasse em Java. (Uma resposta está aqui: 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() 
  { }
}

A trava aqui garante que ambos os bloqueios sejam mantidos quando cada thread tenta bloquear o outro:

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

   }

}

Interessante executar o jconsole, que mostrará corretamente o impasse na guia Threads.

O deadlock acontece quando os threads (ou o que quer que sua plataforma chame de unidades de execução) adquirem recursos, onde cada recurso só pode ser mantido por um thread de cada vez e retém esses recursos de tal forma que as suspensões não podem ser impedidas, e existe algum relacionamento "circular" entre os threads de modo que cada thread no conflito está esperando para adquirir algum recurso mantido por outro thread.

Portanto, uma maneira fácil de evitar o conflito é dar uma ordem total aos recursos e impor uma regra de que os recursos só são adquiridos por threads em ordem . Por outro lado, um deadlock pode ser criado intencionalmente executando threads que adquirem recursos, mas não os adquirem em ordem. Por exemplo:

Dois fios, duas fechaduras. O primeiro thread executa um loop que tenta adquirir os bloqueios em uma determinada ordem, o segundo thread executa um loop que tenta adquirir os bloqueios na ordem oposta. Cada thread libera ambos os bloqueios após adquiri-los com sucesso.

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

Agora, houve alguns comentários nesta questão que apontam a diferença entre o probabilidade e a certeza de um impasse. Em certo sentido, a distinção é uma questão acadêmica. Do ponto de vista prático, certamente gostaria de ver um sistema em execução que não bloqueie com o código que escrevi acima :)

No entanto, as perguntas da entrevista podem ser acadêmicas às vezes, e essa pergunta do SO tem a palavra "certamente" no título, então o que se segue é um programa que certamente bloqueia. Dois Lockerobjetos são criados, cada um recebe dois bloqueios e um CountDownLatchusado para sincronizar entre os threads. Cada Lockertrava a primeira fechadura e, em seguida, conta uma vez. Quando os dois fios adquirem um bloqueio e fazem a contagem regressiva do trinco, passam pela barreira do trinco e tentam obter um segundo bloqueio, mas em cada caso o outro segmento já contém o bloqueio desejado. Essa situação resulta em um certo impasse.

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

Aqui está um exemplo de Java seguindo o de Eric Lippert:

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

}

Aqui está um exemplo da documentação:

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

Reescrevi a versão Java de Yuriy Zubarev do exemplo de deadlock postado por Eric Lippert: https://stackoverflow.com/a/9286697/2098232 para se parecer mais com a versão C #. Se o bloco de inicialização do Java funciona de forma semelhante ao construtor estático C # e primeiro adquire o bloqueio, não precisamos de outro thread para também invocar o método de junção para obter um deadlock, ele só precisa invocar algum método estático da classe Lock, como o C # original exemplo. O impasse resultante parece confirmar isso.

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

}

Não é a tarefa de entrevista mais simples que você pode conseguir: no meu projeto, paralisou o trabalho de uma equipe por um dia inteiro. É muito fácil fazer seu programa parar, mas é muito difícil levá-lo ao estado em que o despejo de thread grava algo como,

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)

Portanto, o objetivo seria obter um conflito que a JVM considerará um conflito. Obviamente, nenhuma solução como

synchronized (this) {
    wait();
}

funcionarão nesse sentido, embora realmente parem para sempre. Depender de uma condição de corrida também não é uma boa ideia, já que durante a entrevista você geralmente quer mostrar algo que provavelmente está funcionando, não algo que deveria funcionar na maior parte do tempo.

Agora, a sleep()solução está bem em um sentido, é difícil imaginar uma situação em que não funcione, mas não é justo (estamos em um esporte justo, não é?). A solução de @artbristol (a minha é a mesma, apenas objetos diferentes como monitores) é boa, mas longa e usa as novas primitivas de simultaneidade para colocar os threads no estado certo, o que não é muito divertido:

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) {
            }
        }
    }
}

Eu me lembro que o synchronized solução -only se encaixa 11..13 linhas de código (excluindo comentários e importações), mas ainda não me lembrei do truque real. Atualizará se eu fizer.

Atualização: aqui está uma solução feia em 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) {
            }
        }
    }
}

Observe que substituímos uma trava por um monitor de objeto (usando "a"como um objeto).

Esta versão C #, acho que o java deve ser bastante semelhante.

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

O programa sempre bloqueia porque cada thread está esperando na barreira pelos outros threads, mas para esperar a barreira, a thread deve estar segurando o monitor BadRunnable.class.

Há um exemplo em Java aqui

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

Onde um sequestrador entra em um impasse quando se recusa a entregar a vítima até conseguir o dinheiro, mas o negociador se recusa a entregar o dinheiro até pegar a vítima.

Uma simples pesquisa me deu o seguinte código:

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

Fonte: Deadlock

Aqui está um exemplo em que um thread segurando o bloqueio inicia outro thread que deseja o mesmo bloqueio e, em seguida, o iniciador espera até que o início termine ... para sempre:

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

Aqui está um exemplo:

dois threads estão em execução, cada um esperando que o outro libere o bloqueio

public class ThreadClass extends 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();
            }
        }

    }


}

}

Executar isso levaria a um impasse:

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


}

}