Écrire un programme qui va sûrement aller dans l'impasse

Question

J'ai récemment eu ce questions posées lors d'une entrevue.

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

Peut-on écrire un tel programme ? Pouvez-vous m'indiquer un exemple de programme de ce genre ?

Answer 1

Mise à JOUR: Cette question a été l'objet de mon blog en janvier 2013. Merci pour la grande question!

---

Comment peut-on écrire un programme qui ira toujours dans l'impasse, peu importe comment les fils sont-ils planifiés?

Voici un exemple en C#. Notez que le programme semble pas contenir de serrures et sans partage de données. Il n'a qu'une seule variable locale et de trois états, et pourtant il blocages avec 100% de certitude. On aurait du mal à venir avec un programme plus simple que les blocages avec certitude.

Exercice pour le lecteur n ° 1: expliquer comment cette blocages. (La réponse est dans les commentaires.)

Exercice pour le lecteur #2: faire preuve de la même impasse en Java. (La réponse est ici: http://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() 
  { }
}

Answer 2

Le loquet ici de s'assurer que les deux verrous de la tenue de 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 sera bien vous montrer l'impasse dans les discussions de l'onglet.

Answer 3

Blocage se produit lorsque les threads (ou quel que soit votre plate-forme d'appels de ses unités d'exécution) acquérir des ressources, où chaque ressource ne peut être détenu que par un seul thread à la fois, et tient à ces ressources d'une manière qui la détient ne peut pas être éliminée, et il existe la "circulaire" de la relation entre les fils de telle sorte que chaque fil dans le blocage est en attente pour acquérir une ressource détenue par un autre thread.

Donc, un moyen facile d'éviter un blocage est de donner quelques total de la commande de ressources et d'imposer une règle que les ressources ne sont jamais acquises par les fils dans l'ordre. À l'inverse, un blocage peut être créé intentionnellement par les threads en cours d'exécution que l'acquisition des ressources, mais n'acquièrent pas dans l'ordre. Par exemple:

Deux fils, deux serrures. Le premier thread exécute une boucle qui tente d'acquérir les verrous dans un certain ordre, le deuxième thread exécute une boucle qui tente d'acquérir les verrous dans l'ordre inverse. Chaque thread libère les deux serrures après la réussite de l'acquisition d'une écluse.

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 à cette question que souligner la différence entre la probabilité et la certitude de blocage. Dans un certain sens, la distinction est une question théorique. À partir d'un point de vue pratique, j'aimerais voir l'exécution d'un système qui ne fait pas l'impasse avec le code que j'ai écrit ci-dessus :)

Cependant, des questions d'entrevue peut être académique, à la fois, et ce DONC, la question n'ont que le mot "certainement" dans le titre, ce qui suit est un programme qui certainement les blocages. Deux Locker des objets sont créés, chacun est donné deux écluses et un CountDownLatch utilisé pour la synchronisation entre les threads. Chaque Locker les verrous de la première écluse, puis le compte à rebours une fois le loquet. Lorsque les deux fils ont acquis un verrou et compté le loquet, ils passent devant le loquet de la barrière et de tenter d'acquérir un deuxième verrou, mais dans chaque cas, le thread est déjà titulaire de la serrure 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();
    }
}

Answer 4

Voici un exemple Java en suivant 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() {
        try {
            Thread t = new Thread(new Lock());
            t.start();
            t.join();
        } catch (InterruptedException ex) {
            System.out.println("won't see me");
        }
    }

}

Answer 5

Voici un Exemple à partir 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();
    }
}