Что произойдет, если положить и взять одновременно, когда Java LinkedBlocking Queue имеет только один элемент?

Question

LinkedBlocking Queue имеет две блокировки, одну для сдачи, одну для взятия.Когда размер очереди равен 1, я думаю, что два потока могут одновременно блокировать и манипулировать очередью, что приведет к неопределенному поведению.Я не прав?

// method put:                             // method take:             
// put lock                                // take lock
 putLocK.lockInterruptibly();              takeLock.lockInterruptibly();                      
 ...                                       ...

 while(count.get() == capacity){           while(count.get() == 0){
   notFull.await();                          notEmpty.await();
 }                                         }
 enqueue(node);                            x = dequeue();

// method enqueue:                         // method dequeue:
  last = last.next = node;                 Node<E> h = head;    
 ...                                       Node<E> first = h.next;
                                           h.next = h;        
                                           head = first;     
                                           E x = first.item;     
                                           first.item = null;   
                                           return x;

Ясно, что поток и прием потока могут блокировать, когда в очереди только один элемент, поэтому они будут выполнять коды в методах enqueue и dequeue соответственно.Я имею в виду, если take thread входит в метод dequeue, после того, как эта модификация указателя не вступит в конфликт с кодами в enqueue?

Ссылки здесь говорят: «Однако, когда очередь пуста, тогда нельзя избежать конфликта, и поэтомудополнительный код требуется для обработки этого общего «крайнего» случая »

Является ли BlockingQueue полностью поточно-ориентированным в Java

Answer 1

javadoc для BlockingQueue (суперкласс LinkedBlockingQueue) гласит:

BlockingQueue реализации являются поточно-ориентированными. Все методы очередей достигают своих эффектов атомарно , используя внутренние блокировки или другие формы управления параллелизмом.

Слово «атомарно» означает, что если две операции (например, put и take) происходят одновременно, то реализация обеспечит их поведение в соответствии с контрактом. Эффект будет , как если бы put происходил до get или наоборот. Это относится и к крайним случаям, таким как ваш пример очереди с одним элементом.

Фактически, поскольку put и get являются блокирующими операциями, относительный порядок этих двух операций не имеет значения. С offer / poll или add / remove заказ имеет значение , но вы не можете его контролировать.

---

Обратите внимание, что вышесказанное основано исключительно на том, что говорит Javadoc. Если предположить, что я правильно интерпретировал Javadoc, то он применяется ко всем реализациям ¹ BlockingQueue, независимо от того, используют ли они одну или две блокировки ... или вообще ни одной. Если реализация BlockingQueue ведет себя не так, как описано выше, это ошибка!

^{1 - Все реализации, которые правильно реализуют API. Это должно охватывать все классы Java SE.}

Answer 2

put реализация LinkedBlockingQueue

public void put(E e) throws InterruptedException {
    // some lock and node code

    // the part that matters here
    try {

        while (count.get() == capacity) {
            notFull.await();
        }

        // put the item in the queue.
    } finally {
        // not important here
    }
}

В основном, в put, вызывающий поток wait s для емкости будет меньше, чем максимальное продолжающееся.

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

take имеет аналогичныйреализация в отношении notEmpty вместо notFull.

Answer 3

После 2 дней поиска я наконец-то понял ... Когда в очереди есть только один элемент, в соответствии с дизайном очереди LinkedBlocking, на самом деле есть два узла: фиктивная голова и действительно элемент (между тем последний указывает на него). Это правда, что put thread и take thread могут оба получить свою блокировку, но они изменяют различные части очереди.

Поставь ветку, назову

last = last.next = node; // last points to the only item in queue

Возьми ветку, позвоню

Node<E> h = head;
Node<E> first = h.next;  // first also points to the only item in queue
h.next = h; 
head = first;
E x = first.item;
first.item = null;
return x;

Пересечение этих двух потоков - это то, на что последний указывает на поток ввода и на что первый указывает на поток потока. Обратите внимание, что поток потока только изменяет last.item, а поток потока только изменяет first.next. Хотя эти два потока модифицируют один и тот же экземпляр объекта, они изменяют другой его элемент, и это не приведет к конфликтам потоков.