Ecrire un programme qui ira sûrement dans une impasse [fermé]

J'ai récemment reçu cette question posée lors d'une interview.

J'ai répondu qu'une impasse se produit si l'entrelacement tourne mal, mais l'intervieweur a insisté sur le fait qu'un programme qui ira toujours dans l'impasse indépendamment de l'entrelacement peut être écrit.

Pouvons-nous écrire un tel programme? Pouvez-vous m'indiquer un exemple de programme comme celui-là?

MISE À JOUR: Cette question a fait l'objet de mon blog en janvier 2013 . Merci pour la bonne question!

Comment pouvons-nous écrire un programme qui ira toujours dans une impasse quelle que soit la planification des threads?

Voici un exemple en C #. Notez que le programme semble ne contenir aucun verrou et aucune donnée partagée. Il n'a qu'une seule variable locale et trois déclarations, et pourtant il se bloque avec une certitude à 100%. On aurait du mal à proposer un programme plus simple qui bloque avec certitude.

Exercice au lecteur n ° 1: expliquez comment cette impasse. (Une réponse est dans les commentaires.)

Exercice au lecteur n ° 2: démontrez le même blocage en Java. (Une réponse est ici: 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() 
  { }
}

Le verrou ici garantit que les deux verrous sont maintenus lorsque chaque thread tente de verrouiller l'autre:

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

   }

}

Intéressant d'exécuter jconsole, qui vous montrera correctement le blocage dans l'onglet Threads.

Le blocage se produit lorsque les threads (ou tout ce que votre plate-forme appelle ses unités d'exécution) acquièrent des ressources, où chaque ressource ne peut être détenue que par un thread à la fois, et conserve ces ressources de telle sorte que les réservations ne peuvent pas être anticipées, et il existe une relation "circulaire" entre les threads de telle sorte que chaque thread dans le blocage attend d'acquérir une ressource détenue par un autre thread.

Ainsi, un moyen simple d'éviter les blocages est de donner un ordre total aux ressources et d'imposer une règle selon laquelle les ressources ne sont acquises que par les threads dans l'ordre . Inversement, un blocage peut être intentionnellement créé en exécutant des threads qui acquièrent des ressources, mais ne les acquièrent pas dans l'ordre. Par exemple:

Deux fils, deux verrous. Le premier thread exécute une boucle qui tente d'acquérir les verrous dans un certain ordre, le second thread exécute une boucle qui tente d'acquérir les verrous dans l'ordre opposé. Chaque thread libère les deux verrous après avoir réussi l'acquisition des verrous.

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

Maintenant, il y a eu quelques commentaires dans cette question qui soulignent la différence entre la vraisemblance et la certitude d'une impasse. Dans un certain sens, la distinction est une question académique. D'un point de vue pratique, j'aimerais certainement voir un système en cours d'exécution qui ne se bloque pas avec le code que j'ai écrit ci-dessus :)

Cependant, les questions d'entrevue peuvent parfois être théoriques, et cette question SO a le mot «sûrement» dans le titre, donc ce qui suit est un programme qui bloque certainement . Deux Lockerobjets sont créés, chacun reçoit deux verrous et un CountDownLatchutilisé pour se synchroniser entre les threads. Chacun Lockerverrouille le premier verrou, puis compte à rebours le verrou une fois. Lorsque les deux fils ont acquis un verrou et ont décompté le verrou, ils passent devant la barrière de verrou et tentent d'acquérir un second verrou, mais dans chaque cas, l'autre fil détient déjà le verrou souhaité. Cette situation entraîne une certaine 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();
    }
}

Voici un exemple Java en suivant celui d'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();      
    }

}

Voici un exemple de la documentation:

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

J'ai réécrit la version Java de Yuriy Zubarev de l'exemple de blocage posté par Eric Lippert: https://stackoverflow.com/a/9286697/2098232 pour ressembler plus étroitement à la version C #. Si le bloc d'initialisation de Java fonctionne de la même manière que le constructeur statique C # et acquiert d'abord le verrou, nous n'avons pas besoin d'un autre thread pour invoquer également la méthode de jointure pour obtenir un blocage, il suffit d'appeler une méthode statique de la classe Lock, comme le C # d'origine exemple. L'impasse qui en résulte semble le confirmer.

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

}

Ce n'est pas une tâche d'entrevue la plus simple que vous puissiez obtenir: dans mon projet, cela a paralysé le travail d'une équipe pendant une journée entière. Il est très facile d'arrêter votre programme, mais il est très difficile de l'amener à l'état où thread dump écrit quelque chose comme,

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)

Le but serait donc d'obtenir un blocage que JVM considérera comme un blocage. Evidemment, aucune solution comme

synchronized (this) {
    wait();
}

fonctionnera dans ce sens, même s’ils s’arrêteront pour toujours. Se fier à une condition de race n'est pas non plus une bonne idée, car pendant l'entretien, vous voulez généralement montrer quelque chose qui fonctionne de manière prouvée, pas quelque chose qui devrait fonctionner la plupart du temps.

Maintenant, la sleep()solution est correcte dans un sens, il est difficile d'imaginer une situation où cela ne fonctionne pas, mais pas juste (nous sommes dans un sport équitable, n'est-ce pas?). La solution de @artbristol (la mienne est la même, juste des objets différents comme moniteurs) est agréable, mais longue et utilise les nouvelles primitives de concurrence pour obtenir les threads dans le bon état, ce qui n'est pas très amusant:

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

Je me souviens que la synchronizedsolution -only correspond à 11..13 lignes de code (à l'exclusion des commentaires et des importations), mais je n'ai pas encore rappelé l'astuce réelle. Mettra à jour si je le fais.

Mise à jour: voici une solution moche sur 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) {
            }
        }
    }
}

Notez que nous remplaçons un verrou par un moniteur d'objet (en utilisant "a"comme objet).

Cette version C #, je suppose que java devrait être assez similaire.

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

Le programme se bloque toujours parce que chaque thread attend à la barrière pour les autres threads, mais pour attendre la barrière, le thread doit maintenir le moniteur sous tension BadRunnable.class.

Il y a un exemple en Java ici

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

Où un kidnappeur se retrouve dans une impasse quand il refuse d'abandonner la victime jusqu'à ce qu'il reçoive l'argent mais le négociateur refuse de donner l'argent jusqu'à ce qu'il ait la victime.

Une simple recherche m'a donné le code suivant:

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

Source: impasse

Voici un exemple où un thread tenant un verrou démarre un autre thread qui veut le même verrou, puis le démarreur attend que le démarrage se termine ... pour toujours:

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

Voici un exemple:

deux threads sont en cours d'exécution, chacun attendant que l'autre libère le verrou

La classe publique ThreadClass étend 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();
            }
        }

    }


}

}

L'exécution de ceci conduirait à une impasse:

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


}

}