Как предотвратить взаимоблокировки в Java с помощью алгоритма Bakery?

Вот код, который в основном реализует алгоритм Bakery (в классе Bakery) для защиты критического раздела счетчика классов (из этого класса я буду создавать свои потоки). Проблема, с которой я столкнулся, заключается в том, что программа иногда зависает (а иногда работает идеально, например, переменная счетчика равна 20000, потому что в моем коде 4 потока). Кстати, решение — это просто интерфейс, содержащий входную секцию и выходную секцию.

public class Main {
 public static void main(String[] args) throws InterruptedException {
     int threadNumbers = 4;
     
     Bakery solution = new Bakery(threadNumbers);

     ArrayList<Counter> threads = new ArrayList<Counter>();

     for(int i =0; i<threadNumbers;i++){
         threads.add(new Counter(i,solution));
     }
     for(int i =0; i<threadNumbers;i++){
         threads.get(i).start();
     }
     for(int i =0; i<threadNumbers;i++){
         
         threads.get(i).join();
     }
     System.out.println(Counter.counter);
 }
}
public class Counter extends Thread{
    static int counter;
    int id;
    private final Bakery solution;
    int count = 0;

    public Counter(int id,Bakery solution) {
        this.id= id;
        this.solution = solution;
    }
    @Override
    public void run(){
        for (int i=0;i<5000;i++){
            this.solution.entrySection(this);
             counter++;
             System.out.println(counter);
            this.solution.exitSection(this);

        }

    }
}
public class Bakery implements Solution{
    boolean[] Choosing;
    int[] Numbers;
    Bakery(int n){
        Choosing = new boolean[n];
        Numbers = new int[n];
        for(int i=0;i<n; i++) {
            Choosing[i] = false;
            Numbers[i] = 0;
        }
    }
    @Override
    public void entrySection(Counter c) {
        Choosing[c.id] = true;
        int max = Numbers[0];
        for (int i = 1; i < Numbers.length; i++) {
            int currentNumber = Numbers[i];
            if (currentNumber > max) {
                max = currentNumber;
            }
        }
        Numbers[c.id] = max + 1;
        Choosing[c.id] = false;
        for(int i=0;i<Numbers.length; i++) {
            while(Choosing[i]){}
            while ((Numbers[i] != 0) && ((Numbers[i] < Numbers[c.id]) || ((Numbers[i] == Numbers[c.id]) && (i < c.id)))) {}
        }
    }
    @Override
    public void exitSection(Counter c) {
        Numbers[c.id] = 0;
    }
}

Я попытался реализовать алгоритм пекарни и ожидал, что переменная счетчика будет равна 20000.

Проблема в том, что изменения в переменных, записанные в одном потоке, не сразу видны другим потокам. Вам понадобится что-то вроде volatile, но для массивов.

dan1st 05.03.2024 18:02

Как правило, Модель памяти Java позволяет записывать переменную в одном потоке без ее распространения на другие потоки до тех пор, пока не нарушаются отношения «до того, как произойдет», и однопоточная семантика, как если бы они выполнялись последовательно (например, кэширование ЦП). ). Если вы измените boolean в одной теме, это изменение может быть не видно в других темах. Если вы хотите, чтобы изменение распространялось на другие потоки, вам нужно установить отношение «происходит до»/использовать что-то вроде volatile (которое не работает с элементами массива).

dan1st 05.03.2024 18:12

Я применил то, что вы сказали, а именно добавление летучих значений перед логическим значением и перед int, но могу ли я узнать, почему это не видно другим тредам?

Oualid Laib 05.03.2024 18:33

Добавление volatile в массив приводит к эффекту при переназначении всего массива. Это не влияет на элементы массива.

dan1st 05.03.2024 18:35

но когда я не добавляю переменную в массив int, программа зависает

Oualid Laib 05.03.2024 18:38

но после многократного выполнения возникла еще одна проблема. Я получил ответы типа 19999 и 19998. В чем проблема?

Oualid Laib 05.03.2024 18:49

Это может быть та же проблема: записанные переменные не рассматриваются как обновленные.

dan1st 05.03.2024 20:20

Re: «...Я получил ответы типа 19999 и 19998». То же самое. Разные потоки обращаются к одной и той же переменной counter, без установленной связи «происходит раньше» между ними. Один поток может заблокировать ваш самодельный мьютекс Bakery, увеличить переменную, а затем разблокировать мьютекс. Тогда другой поток сможет заблокировать ваш Bakery, прочитать переменную и увидеть счетчик, как если бы первый поток никогда не увеличивал его. Этого не могло бы произойти, если бы вы изменили программу, чтобы использовать ReentrantLock вместо вашего Bakery объекта, потому что блокировка и разблокировка ReentrantLock действительно устанавливает «происходит раньше».

Solomon Slow 05.03.2024 22:08

Никаких признаков тупика здесь нет.

user207421 05.03.2024 22:23

Вы имели в виду en.wikipedia.org/wiki/Lamport's_bakery_algorithm ?

Basil Bourque 06.03.2024 07:56
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
10
73
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Как и многие подходы к взаимному исключению и связанным формам синхронизации потоков, алгоритм Bakery зависит от особенно сильной семантики памяти — более сильной, чем вы можете безопасно полагаться в большинстве сред с несколькими одновременно работающими исполнительными блоками. Или даже в некоторых, которые этого не делают.

В частности, как описано в Википедии, Алгоритм Лампорта Bakery содержит несколько потенциальных гонок данных, и, если их не предотвратить, его поведение в Java не определено. Чтобы ваша реализация работала на Java надежно, вам необходимо исправить гонки данных, включающие

  • элементы Bakery.Choosing
  • элементы Bakery.Number
  • Counter.count

Вам необходимо убедиться, что разные потоки действительно будут наблюдать за записью друг друга, и что операции чтения и записи любого из них не будут переупорядочены относительно других из них. Предположительно, цель состоит в том, чтобы сам алгоритм Bakery по своей сути обеспечивал необходимую синхронизацию для доступа к Counter.count внутри критической секции, и если все сделано правильно, так и будет. Но это зависит от обеспечения правильной семантики памяти для всех этих элементов массива.

Использование блоков или методов synchronized или явных блокировок лишило бы смысла использование алгоритма Bakery, поэтому я полагаю, что они не обсуждаются. volatile был поднят в комментариях к вопросу, но здесь он не подходит, потому что volatile могут быть только поля и переменные, тогда как вам нужен безопасный способ доступа к элементам массива (или List).

Достаточно естественное решение, которое не слишком сильно отклоняется от традиционного описания алгоритма, будет включать использование массивов или Listатомарных объектов:

public class Bakery implements Solution{
    AtomicBoolean[] choosing;
    AtomicInteger[] numbers;

    Bakery(int n){
        choosing = new AtomicBoolean[n];
        numbers = new AtomicInteger[n];
        for(int i = 0; i < n; i++) {
            choosing[i] = new AtomicBoolean();  // defaults to false
            numbers[i] = new AtomicInteger();   // defaults to 0
        }
    }

    // ...

Существует множество методов доступа и изменения значения, содержащегося в каждом атомарном объекте, но их простые методы get() и set() должны делать то, что вам нужно. Они обеспечивают ту же семантику памяти, что и чтение и запись volatile соответственно. (Некоторые другие методы доступа не обеспечивают достаточно строгой семантики.)

Другие вопросы по теме