I blocchi multilivello possono causare deadlocks nei programmi multithread?

Question

Ho un programma con scrittori e lettori e il loro diritto di accesso è controllato da un monitor.

Quindi, questo doveva morire di fame, ma ho avuto una situazione di stallo. Mi chiedevo perché e poi mi sono ricordato di aver messo un altro blocco, che penso non fosse necessario all'interno del mio metodo di lettura all'interno dei lettori per proteggere la mia variabile globale dalle incoerenze. Ho pensato che non avrebbe causato alcun deadlock, perché potevo eseguire i thread 10000 tempo senza che si verificasse alcun deadlock, ma quando ho dovuto fare la mia demo di laboratorio, credo, credo. Non capisco perché lo farebbe però. Inoltre, non mi aspettavo che fame di fame, ma a quanto pare avrebbe dovuto.

La mia domanda è: quelle serrature multilivello sono responsabili del deadlock? In caso contrario, cosa sta causando questo?!

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

    }


}

Questa è la classe Writer.

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

    }



        }

Questa è la classe Reader.

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


            }






        }

}

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

    }


}

Questo è il monitor.

pseudocodi per il monitor

Answer 1

Ogni volta che hai più serrature A, B e C puoi avere Deadlock se non garantisci che il tuo codice tenta di acquisire tali serrature nello stesso ordine.

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

A, B, C o C, B, A o A, C, B - Non importa fintanto che l'ordine è coerente.

Un problema sorge quando hai un percorso di codice per: A, B, C e un altro che prova per C, B, A.

Come puoi probabilmente indovinare poiché A e C vengono detenuti entrambi, uno dei due otterrà B e poi entrambi saranno deadlock. (Aka hai un ciclo nel grafico di bloccaggio delle risorse)

Può sorgere la stallo formalmente parlando solo se Tutte le seguenti condizioni contengono:

1. Nessuna precettazione: il sistema non libererà risorse dopo l'allocazione; Possono essere rilasciati solo dal processo di detenzione.
2. Aspetta circolare: discusso sopra.
3. Esclusione reciproca: solo un processo può utilizzare una risorsa in qualsiasi momento.
4. Holding delle risorse: un processo ha attualmente almeno una risorsa e richiede/attendendo risorse aggiuntive che sono detenute da un altro processo.

La soluzione migliore è assicurarsi che l'ordine sia coerente o blocca a un livello più alto (singolo). Un'altra opzione è quella di utilizzare una libreria di bloccaggio che si time mentre si tenta di bloccare (o utilizzare le condizioni e scrivere il proprio wrapper che lo fa). Ma quell'approccio non è per i deboli di cuore. Una certa implementazione di questo aspetterà un periodo di tempo casuale e riproverà, ma questo può essere altamente inefficiente all'aumentare del numero di blocchi.

Risorse:

• Ecco un articolo pratico sull'analisi del deadlock in Java a cui potresti essere interessato:http://www.journaldev.com/1058/java-deadlock-example-and-how-to-analyze-deadlock-situation
• Puoi anche usare strumenti open source come JCarder per trovare Deadlock:http://www.jcarder.org/ Che per programmi con dump di grandi dimensioni può essere più semplice, quindi provare a far sfuggire i file di dump.

PS in realtà non ho letto gran parte del tuo codice poiché è scarsamente formattato e non è un esempio minimo (cioè troppo verboso per i nostri scopi qui). Ma questo consiglio dovrebbe rispondere alla tua domanda dal punto di vista teorico.

Answer 2

È certamente possibile. È anche possibile per te controllare in fase di esecuzione!

Il primo passo è ottenere il dump del thread. Ecco tre metodi:

• Se apri il processo in VisualVM e vai alla scheda "Threads", ti dirà se rileva questo tipo di deadlock. Puoi quindi fare un dump di thread (c'è un pulsante proprio lì), che ti dirà cosa sta facendo ogni thread, oltre a qualsiasi serratura che possiede e qualsiasi chiusura (se presente) sta cercando di acquisire.
• Su Linux o Mac, puoi ottenere lo stack emettendo kill -3 <pid>, dove <pid> è l'ID del tuo processo Java. Scaricherà lo stesso thread dump su Stderr. Il fondo di quel dump thread conterrà anche un riepilogo dei deadlock che rileva. Non so come farlo su Windows.
• Puoi anche invocare jstack <pid>, che stamperà il thread dump su stdout (il jstack's stdout, non il processo Java originale').

Ho scritto un programma di esempio che i deadlocks e lo hanno eseguito (vedi la mia sostanza). La sezione pertinente del dump del thread è:

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"

E gli stati del thread pertinenti sono:

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

Questo non funzionerà tutto Deadlocks. Ad esempio, i deadlock a causa dell'attesa di risorse esterne non verranno catturati. Ma catturerà Lock-IlDlocks basati, oltre che synchronized-Il base.