Обновление энергозависимого логического массива с использованием потоков

Question

Я учусь на CS и в настоящее время изучаю параллельное программирование, поэтому мои знания о потоках все еще носят предварительный характер.

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

class Viewer extends Thread{
    private String name;
    private int index;
    volatile boolean[] seats;


    Viewer(boolean[] st, String n){
        seats = st;
        name = n;
    }

    public void run() {
        ViewingStand vs = new ViewingStand(seats);
        this.index = vs.findSeat(name, seats);
            try {
                Thread.sleep((long)(Math.random() * 1000));
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            seats = vs.leaveSeat(name, seats, index);

    }
}

class ViewingStand{
    private volatile boolean[] area; //the array used by threads
    private int seatNo; //index of whatever area is being taken or left.
    Random rand = new Random();
    boolean found = false;

    public ViewingStand(boolean st[]){
    this.area = st;
    }

    public int findSeat(String s, boolean[] seats){
        this.area = seats;
        while(found == false) {
            for(int i=0; i < area.length; i++) {
                if(area[i] == true) {
                    found = true;
                    this.seatNo = i; 
                    area[seatNo] = false;
                    System.out.println(s + " has found a seat.");
                    return this.seatNo;
                }
            }
            System.out.println(s + " has started searching again.");
        }
        return -1; //should never reach this
    }

    public boolean[] leaveSeat(String s, boolean[] area, int n){
        this.area = area;
        this.area[n] = false;
        System.out.println(s + " has left their seat.");
        return this.area;
    }

Результатом этой программы является массив, изначально заполненный 10 элементами (размер массива, который я передал из основной программы), затем эти потоки покидают массив 'an'но явно не то же самое, что я передаю взад-вперед между обоими методами PreviewStand, поскольку каждый последующий поток после 10-го застревает в поисках места.Хотелось бы некоторый вклад, чтобы указать мне в правильном направлении.Спасибо!

Answer 1

На стороне параллелизма ...

1. A volatile boolean[] вряд ли будет поточно-ориентированным.Семантика volatile применяется только к ссылке на массив, но не к доступу и обновлению элементов массива.

2. Вы выполняете отдельное чтение и запись для элемента массива,Изменчивый означает, что одно чтение гарантированно увидит мгновенно правильное значение;т.е. значение последней записи из любого потока.Но это не мешает условиям гонки.

   Ваш код, поток выполняет чтение, чтобы проверить, свободно ли место, затем запись, чтобы зарезервировать его.Эта последовательность не атомарна.Ничто не мешает другому потоку «захватить место» между чтением и записью этого потока.

К сожалению, единственный способ гарантировать, что ваш код не имеет такой проблемы, состоит в том, чтобывыполнить формальный анализ (т.е. построить математически обоснованное звуковое доказательство), начиная с указанной семантики модели памяти Java ¹ .Это сложно.Следовательно, обычно рекомендуется использовать стандартные строительные блоки, предоставляемые пакетами java.util.concurrent, java.util.concurrent.atomic и java.util.concurrent.locks.

---

^{1 - Если вы понимаете JMM, неформальный анализ может быть приемлемым ...}

Answer 2

Сначала о стиле кода.Viewer s предоставляется необработанный доступ к массиву.Это противоречит философии ОО дизайна.Логический массив должен быть инкапсулирован ViewingStand, обработанным только его методами.

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

---

Доступ к фактическим данным, содержимому boolean[], не является энергозависимым.То, как вы используете ключевое слово, делает ссылку на данные непостоянной.Так как ссылка вообще не изменяется, добавленный volatile ничего не делает, за исключением, может быть, замедления доступа.

Даже если вам удалось выполнить энергозависимые операции чтения и записи в содержимое массива, существуетпо-прежнему возникают проблемы с параллелизмом, поскольку проверка свободного места и его получение не являются атомарными.

Один из способов сделать доступ атомарным - добавить блокировки (сделать методы synchronized), по сути, форсируя доступ к ViewingStand случиться один за другим.С порядком «происходит до», навязанным блокировкой, вам даже не нужно volatile.

Однако, если вы добавите блокировку к findSeat, n + 1 ^th Viewer будет удерживать замок, продолжайте искать свободное место, пока первые n Viewer ждут блокировки, чтобы они могли запустить leaveSeat.ТупикКлючевое слово synchronized должно быть добавлено к методу, который циклически перебирает массив, но не к методу findSeat.

---

Другой способ и мощная идея, которую можно применять даже в базе данных.Доступ Сравнение и замена .Это одна инструкция, которая изменяет данные, только если предыдущее значение соответствует ожидаемому.Вместо boolArray[i] = true вы можете использовать массив AtomicBoolean s и сделать atomicBoolArray[i].compareAndSet(false, true).Если compareAndSet возвращает false, это означает, что другой Viewer получил место ранее.

Answer 3

Сначала я проигнорирую проблемы параллелизма и пойду прямо к тому, что похоже на логическую ошибку, о которой вы спрашиваете - leaveSeat устанавливает this.area[n] = false - что, кажется, указывает на то, что место занято (ваше findSeat метод предполагает, что место пусто, если значение true).

По вопросам параллелизма: у вас, скорее всего, возникнут проблемы с циклом проверки мест - для нескольких потоков возможно определить, что место пусто (и перейти в блок if), и все «забрать»то же местоВы должны создать один экземпляр ViewingStand и управлять им доступом к местам - используя элементы управления параллелизмом, такие как synchronized или блокировку, чтобы несколько потоков не изменяли состояние мест одновременно.