Les verrous à plusieurs niveaux peuvent-ils provoquer des impasses dans les programmes Multithread?

Question

J'ai un programme avec des écrivains et des lecteurs et leur droit d'accès est contrôlé par un moniteur.

Donc, c'était censé mourir de faim, mais j'ai eu une impasse. Je me demandais pourquoi et puis je me suis souvenu que j'avais mis une autre serrure, ce qui, je pense, n'était pas nécessaire à l'intérieur de ma méthode de lecture à l'intérieur des lecteurs pour protéger ma variable globale contre les incohérences. Je pensais que cela ne provoquerait aucune impasse, car je pouvais exécuter la fois les threads 10000 sans aucune impasse, mais quand j'ai dû faire ma démo de laboratoire, il est en vertu de l'impasse au 10010e fil, je pense. Je ne comprends pas pourquoi cela ferait cela. De plus, je ne m'attendais pas à ce qu'il meure de faim, mais apparemment, c'était censé le faire.

Ma question est: ces serrures à plusieurs niveaux sont-elles responsables de l'impasse? Sinon, qu'est-ce qui cause cela ?!

    import java.io.*;
    import java.io.IOException;
    import java.util.*;

    public class Writer extends Thread{

    private int number;

    public Writer(int number)
    {
        this.number = number;
    }

    public int getNumber()
    {
        return number;
    }

        public static void Write(String filename){

        try {

            String content = RandomString();


            File f = new File(filename);

            if (!f.exists())
            {
                f.createNewFile();
            }


            PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("Task1out.txt", true)));
            out.println(content);
            out.close();


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static String RandomString(){

        String chars = new String("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
        int n = chars.length();

        String randomString = new String();
        Random r = new Random();

            for (int i=0; i<100; i++)
            {
                randomString = randomString + chars.charAt(r.nextInt(n));
            }

        System.out.println("RandomString() generated: " + randomString);

        return randomString;

    }



    public void run(){

        try{

        //FileControl fc = new FileControl();

            int number = this.getNumber();


            for(int i = 0; i <1000; i++) //CHANGE IT TO 1000
            {
                main.fc.WriterEntry(number);

                //write file random characters (must append)

                Write("Task1out.txt");

                main.fc.WriterExit(number);

            }
        } catch(InterruptedException e)
        {
            System.out.println("Interrupted Exception caught");
        }

    }


}

Ceci est la classe d'écrivain.

    import java.io.BufferedWriter;
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileWriter;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.*;
    import java.util.concurrent.locks.Condition;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;



public class Reader extends Thread{


    private int number;

    public Reader(int number)
    {
        this.number = number;
    }


    public int getNumber()
    {
        return number;
    }

        public static synchronized void Read(String filename)throws InterruptedException{

        BufferedReader br = null;





            main.lock.lock(); //lock
        try{




        try {


            String line;
            char[] chars = new char[100];
            int readIndex2 = 0;
            int addToIndex = 0;



            br = new BufferedReader(new FileReader(filename));


            int initialReadIndex = main.getIndex();




            System.out.println("initial read index: " + initialReadIndex);

            while ((line = br.readLine()) != null && readIndex2 < initialReadIndex+100 && addToIndex < 100) {

                for(int i = 0; i< 100; i++)
                {
                    if (initialReadIndex == readIndex2 || initialReadIndex < readIndex2)
                    {

                        if(line.length() > addToIndex)
                        {




                        chars[i] = line.charAt(i);
                        addToIndex++;
                        }


                    }
                    else
                    {
                        readIndex2++;
                    }
                }
                System.out.println(chars);
            }

            if(line == null)
            {
                System.out.println("nothing to read");
            }



            main.incrementIndex(addToIndex);


            System.out.println("current read index: " + (initialReadIndex + addToIndex));





        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("buffered reader exception");
        } finally {


            try {


                if (br != null)
                    {

                    br.close();
                    }
            } catch (IOException ex) {
                ex.printStackTrace();
                System.out.println("exception during closing");
            }
        }
        }finally{
            main.lock.unlock(); //lock

        }

        }


    public void run(){

        try{


        //FileControl fc = new FileControl();


        int number = this.getNumber();


            for(int i = 0; i <1000; i++) //CHANGE IT TO 1000
            {
                main.fc.ReaderEntry(number);

                //read file

                Read("Task1out.txt");

                main.fc.ReaderExit(number);
            }
        } catch(InterruptedException e)
        {
            System.out.println("Interrupted Exception caught");
        }

    }



        }

Ceci est la classe des lecteurs.

 import java.io.BufferedWriter;
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileWriter;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.concurrent.locks.Condition;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;

    public class main{

    public static FileControl fc = new FileControl();

    final static Lock lock = new ReentrantLock();

    public static int readIndex;

    public static void incrementIndex(int increment) {


                readIndex = readIndex + increment;

    }

    public static int getIndex()
    {
        return readIndex;
    }



    public static void main(String[] args) throws InterruptedException {



            Writer [] writer = new Writer[10];
            Reader [] reader = new Reader[10];

            for(int i = 0; i < 10; i++)
            {
                reader[i] = new Reader(i);
                writer[i] = new Writer(i);
                //creating readers and writers

            }

            for(int i = 0; i < 10; i++)
            {
                //anonymous threads
                //(new Thread(new Writer())).start();
                //(new Thread(new Reader())).start();

                reader[i].start();
                writer[i].start();

            }




            for(int i = 0; i < 10; i++)
            {
                try{
                    reader[i].join();
                    writer[i].join();
                } catch(InterruptedException e){
                    e.printStackTrace();
                }


            }






        }

}

C'est la classe principale.

    import java.util.concurrent.locks.Condition;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;


    public class FileControl {
    final Lock lock = new ReentrantLock();
    final Condition writers = lock.newCondition();
    final Condition readers = lock.newCondition();
    int activereaders = 0;
    int waitingwriters = 0;
    boolean writing = false;

    public void WriterEntry(int number)throws InterruptedException{
        lock.lock();
        try{
                if(writing == true || activereaders > 0){
                    waitingwriters++;
                    System.out.println("Writer thread " + number + " : waiting to write");
                    writers.await();
                    waitingwriters--;
                }
                System.out.println("Writer thread " + number + " : ready to write");

                writing = true;
           }
        finally{
            lock.unlock();
        }


    }



    public void WriterExit(int number)throws InterruptedException{
        lock.lock();
        try{
            System.out.println("Writer thread " + number + " : finished to write");

            System.out.println("writers " + waitingwriters + "readers " + activereaders); //test

            if(waitingwriters > 0)
                writers.signal();
            else{
                writing = false;
                readers.signal();
            }
        }
        finally{
            lock.unlock();
        }

    }


    public void ReaderEntry(int number)throws InterruptedException{
        lock.lock();
        try{

            if(writing == true || waitingwriters > 0){ //remove activereaders > 0
                System.out.println("Reader thread " + number + " : waiting to read");
                readers.await();
                activereaders++;
            }


            System.out.println("Reader thread " + number + " : ready to read");
        }
        finally{
            lock.unlock();
        }

    }

    public void ReaderExit(int number)throws InterruptedException{
        lock.lock();
        try{



        activereaders--;



        System.out.println("Reader thread " + number + " : finished to read");

        System.out.println("writers " + waitingwriters + "readers " + activereaders); //test

            if(activereaders == 0)
            {
                if(waitingwriters > 0)
                {
                    writers.signal();
                }
                else
                {
                    readers.signal();
                }
            }
        }
        finally{
            lock.unlock();
        }

    }


}

Ceci est le moniteur.

pseudocode pour le moniteur

Answer 1

Chaque fois que vous avez plusieurs verrous A, B et C, vous pouvez avoir une impasse si vous ne garantissez pas que votre code tente d'acquérir lesdits verrous dans le même ordre.

final Lock A = new ReentrantLock();
final Lock B = new ReentrantLock();
final Lock C = new ReentrantLock();

A, B, C ou C, B, A ou A, C, B - Peu importe tant que l'ordre est cohérent.

Un problème se pose lorsque vous avez un chemin de code essayant: a, b, c et un autre essayant pour c, b, a.

Comme vous pouvez probablement le deviner, car A et C sont tous deux détenus, l'un des deux obtiendra B, puis les deux seront imprégnés. (AKA vous avez un cycle dans le graphique de verrouillage des ressources)

L'impasse formellement parlant peut surgir seulement si Toutes les conditions suivantes soutiennent:

1. Pas de préemption: le système ne sera pas gratuit après l'allocation; Ils ne peuvent être libérés que par le processus de maintien.
2. Attente circulaire: discuté ci-dessus.
3. Exclusion mutuelle: un seul processus peut utiliser une ressource à tout moment.
4. Tenue de ressources: un processus détient actuellement au moins une ressource et demande / attend des ressources supplémentaires qui sont détenues par un autre processus.

La meilleure solution consiste à s'assurer que la commande est cohérente ou à verrouiller à un niveau plus élevé (unique). Une autre option consiste à utiliser une bibliothèque de verrouillage qui sera dénoncée tout en essayant de verrouiller (ou d'utiliser des conditions et d'écrire votre propre wrapper qui le fait). Mais cette approche n'est pas pour les faibles de cœur. Une certaine mise en œuvre de cela attendra un temps aléatoire et réessayera, mais cela peut être très inefficace à mesure que le nombre de verrous augmente.

Ressources:

• Voici un article pratique sur l'analyse de l'impasse en Java qui pourrait vous intéresser:http://www.journaldev.com/1058/java-deadlock-example-and-how-to-analyze-deadlock-situation
• Vous pouvez également utiliser des outils open source comme JCarder pour trouver une impasse:http://www.jcarder.org/ Ce qui pour les programmes avec de grands vidages peut être plus facile que d'essayer d'obtenir des fichiers de vidage.

PS Je n'ai pas vraiment lu beaucoup de votre code car il est mal formaté et n'est pas un exemple minimal (c'est-à-dire trop verbeux pour nos fins ici). Mais ce conseil devrait vous répondre à un point de vue théorique.

Answer 2

C'est certainement possible. Il est également possible pour vous de vérifier au moment de l'exécution!

La première étape consiste à obtenir le vidage de thread. Voici trois méthodes:

• Si vous ouvrez le processus dans VisualVM et accédez à l'onglet "Threads", il vous dira s'il détecte ce type de blocage. Vous pouvez ensuite faire un vidage (il y a un bouton juste là), qui vous dira ce que fait chaque fil, ainsi que tous les verrous qu'il possède et ceux qui serrent (le cas échéant) qu'il essaie d'acquérir.
• Sur Linux ou Mac, vous pouvez obtenir la pile en émettant kill -3 <pid>, où <pid> est votre id de processus Java. Il videra ce même vidage de thread à stderr. Le bas de ce vidage contiendra également un résumé des impasses qu'il détecte. Je ne sais pas comment faire cela sous Windows.
• Vous pouvez également invoquer jstack <pid>, qui imprimera le vidage de thread à stdout (le jstack«S stdout, pas le processus Java original»).

J'ai rédigé un exemple de programme qui se compose des impasses et je l'ai exécuté (voir mon gist). La section pertinente de la vidage de thread est:

Found one Java-level deadlock:
=============================
"Thread-2":
  waiting for ownable synchronizer 7f42b0f38, (a java.util.concurrent.locks.ReentrantLock$NonfairSync),
  which is held by "Thread-1"
"Thread-1":
  waiting for ownable synchronizer 7f42ba170, (a java.util.concurrent.locks.ReentrantLock$NonfairSync),
  which is held by "Thread-2"

Et les états de threads pertinents sont:

"Thread-2" prio=5 tid=7fc01c911000 nid=0x113d18000 waiting on condition [113d17000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <7f30c3528> (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:156)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:811)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:842)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1178)
    at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLock.java:186)
    at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:262)
    at Locky$Boomer.run(Locky.java:22)
    at java.lang.Thread.run(Thread.java:680)

   Locked ownable synchronizers:
    - <7f30c3558> (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

"Thread-1" prio=5 tid=7fc01d06c800 nid=0x113c15000 waiting on condition [113c14000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <7f30c3558> (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:156)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:811)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:842)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1178)
    at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLock.java:186)
    at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:262)
    at Locky$Boomer.run(Locky.java:22)
    at java.lang.Thread.run(Thread.java:680)

   Locked ownable synchronizers:
    - <7f30c3528> (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

Cela ne fonctionnera pas sur tout des impasses. Par exemple, les impasses en raison de l'attente des ressources externes ne seront pas prises. Mais ça va attraper Lock-Laques de blocages basés, ainsi que synchronized-Us basés.