Могут ли многоуровневые блокировки вызвать тупики в многопоточных программах?

Question

У меня есть программа с писателями и читателями, и их право доступа контролируется монитором.

Итак, это должно было голодать, но я получил тупик. Мне было интересно, почему, а потом я вспомнил, что я положил еще один замок, который, я думаю, был ненужным внутри моего метода чтения внутри читателей, чтобы защитить мою глобальную переменную от несоответствий. Я думал, что это не приведет к тупику, потому что я мог бы запустить Threads 10000 раз без какого -либо тупика, но когда мне пришлось сделать демонстрацию своей лаборатории, я думаю, что он зашел в тупик в 10010 -й ветке. Я не понимаю, почему это сделает это, хотя. Кроме того, я не ожидал, что это голодает, но, видимо, это должно было.

Мой вопрос: ответственность за эти многоуровневые замки за тупик? Если нет, то что вызывает это?!

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

    }


}

Это класс писателей.

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

    }



        }

Это класс читателей.

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


            }






        }

}

Это основной класс.

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

    }


}

Это монитор.

псевдокод для монитора

Answer 1

Всякий раз, когда у вас есть несколько замков A, B и C, у вас может быть тупик, если вы не гарантируете, что ваш код пытается приобрести указанные блокировки в том же заказе.

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

A, b, c или c, b, a или a, c, b - это не имеет значения, пока порядок является последовательным.

Проблема возникает, когда у вас есть один путь кода, попробуйте: A, B, C, а другой пытается для C, B, A.

Как вы, вероятно, можете догадаться, так как оба удерживаются A и C, один из них получит B, а затем оба будут тупиться. (AKA у вас есть цикл на графике блокировки ресурсов)

Формально говорящий тупик может возникнуть только если Все следующие условия удерживаются:

1. Без предположения: система не будет свободным ресурсами после распределения; Они могут быть освобождены только процессом удержания.
2. Круговое ожидание: обсуждается выше.
3. Взаимное исключение: только один процесс может использовать ресурс в любой момент времени.
4. Удержание ресурсов: в настоящее время процесс имеет как минимум один ресурс и запрашивает/ожидает дополнительных ресурсов, которые удерживаются другим процессом.

Лучшее решение - убедиться, что порядок является согласованным или блокировал на более высоком (одиночном) уровне. Другой вариант - использовать записную библиотеку, которая будет тайм -аутом при попытке блокировать (или использовать условия и написать свою собственную обертку, которая делает это). Но этот подход не для слабонервных. Некоторая реализация этого будет ждать случайное количество времени и повторить попытку, но это может быть очень неэффективным, поскольку количество замков увеличивается.

Ресурсы:

• Вот практическая статья об анализе тупика в Яве, которую вам может быть интересно:http://www.journaldev.com/1058/java-deadlock-example-and-how-to-analyze-deadlock-situcation
• Вы также можете использовать инструменты с открытым исходным кодом, такие как JCarder, чтобы найти тупик:http://www.jcarder.org/ Что для программ с большими дампами может быть проще, а затем попытаться запустить файлы дампы Grok.

PS Я на самом деле не читал большую часть вашего кода, так как его плохо отформатировано и не является минимальным примером (т.е. слишком условно для наших целей здесь). Но этот совет должен ответить вам на вопрос с теоретической точки зрения.

Answer 2

Это, безусловно, возможно. Вы также можете проверить во время выполнения!

Первый шаг - получить свалку потока. Вот три метода:

• Если вы откроете процесс в VisualVM и перейдите на вкладку «Тема», он скажет вам, если он обнаружит такой тупик. Затем вы можете сделать дамп потока (есть кнопка прямо здесь), которая расскажет вам, что делает каждый поток, а также любые блокировки, которой она владеет, и любые блокировки (если таковые имеются), он пытается приобрести.
• На Linux или Mac вы можете получить стек, выпустив kill -3 <pid>, куда <pid> Ваш Java Process 'ID. Это сбросит тот же свалки резьбы в Stderr. Внизу этого дампа резьбы также будет содержать резюме тупиков, которые он обнаруживает. Я не знаю, как это сделать в Windows.
• Вы также можете вызвать jstack <pid>, который будет печатать свалку потока в Stdout ( jstackSTDOUT, а не оригинальный процесс Java ').

Я написал образец программы, которая запустила ее (см. моя суть) Соответствующий раздел дампа потока:

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"

И соответствующие состояния потока:

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

Это не будет работать на все тупики. Например, тупики из -за ожидания внешних ресурсов не будут пойманы. Но это поймает Lock-основанные тупики, а также synchronized-Са основаны.