Вот код, который в основном реализует алгоритм 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.
Как правило, Модель памяти Java позволяет записывать переменную в одном потоке без ее распространения на другие потоки до тех пор, пока не нарушаются отношения «до того, как произойдет», и однопоточная семантика, как если бы они выполнялись последовательно (например, кэширование ЦП). ). Если вы измените boolean в одной теме, это изменение может быть не видно в других темах. Если вы хотите, чтобы изменение распространялось на другие потоки, вам нужно установить отношение «происходит до»/использовать что-то вроде volatile (которое не работает с элементами массива).
Я применил то, что вы сказали, а именно добавление летучих значений перед логическим значением и перед int, но могу ли я узнать, почему это не видно другим тредам?
Добавление volatile в массив приводит к эффекту при переназначении всего массива. Это не влияет на элементы массива.
но когда я не добавляю переменную в массив int, программа зависает
но после многократного выполнения возникла еще одна проблема. Я получил ответы типа 19999 и 19998. В чем проблема?
Это может быть та же проблема: записанные переменные не рассматриваются как обновленные.
Re: «...Я получил ответы типа 19999 и 19998». То же самое. Разные потоки обращаются к одной и той же переменной counter, без установленной связи «происходит раньше» между ними. Один поток может заблокировать ваш самодельный мьютекс Bakery, увеличить переменную, а затем разблокировать мьютекс. Тогда другой поток сможет заблокировать ваш Bakery, прочитать переменную и увидеть счетчик, как если бы первый поток никогда не увеличивал его. Этого не могло бы произойти, если бы вы изменили программу, чтобы использовать ReentrantLock вместо вашего Bakery объекта, потому что блокировка и разблокировка ReentrantLock действительно устанавливает «происходит раньше».
Никаких признаков тупика здесь нет.
Вы имели в виду en.wikipedia.org/wiki/Lamport's_bakery_algorithm ?




Как и многие подходы к взаимному исключению и связанным формам синхронизации потоков, алгоритм Bakery зависит от особенно сильной семантики памяти — более сильной, чем вы можете безопасно полагаться в большинстве сред с несколькими одновременно работающими исполнительными блоками. Или даже в некоторых, которые этого не делают.
В частности, как описано в Википедии, Алгоритм Лампорта Bakery содержит несколько потенциальных гонок данных, и, если их не предотвратить, его поведение в Java не определено. Чтобы ваша реализация работала на Java надежно, вам необходимо исправить гонки данных, включающие
Bakery.ChoosingBakery.NumberCounter.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 соответственно. (Некоторые другие методы доступа не обеспечивают достаточно строгой семантики.)
Проблема в том, что изменения в переменных, записанные в одном потоке, не сразу видны другим потокам. Вам понадобится что-то вроде
volatile, но для массивов.