Синхронизация очереди

Question

Я читал книгу Дуга Ли «Параллельное программирование на Java». Как вы, возможно, знаете, Даг изначально написал API параллелизма Java. Однако что-то вызвало у меня некоторую путаницу, и я надеялся получить несколько своих мнений об этой маленькой головоломке!

Возьмите следующий код из примера очереди Дуга Ли ...

class LinkedQueue {
  protected Node head = new Node(null); 
  protected Node last = head; 

  protected final Object pollLock = new Object();
  protected final Object putLock = new Object();

  public void put(Object x) {
    Node node = new Node(x);
    synchronized (putLock) {     // insert at end of list
      synchronized (last) {
        last.next = node;        // extend list   
        last = node;
      }
    }
  }

  public Object poll() {         // returns null if empty
    synchronized (pollLock) {
      synchronized (head) {
        Object x = null;
        Node first = head.next;  // get to first real node
        if (first != null) {
          x = first.object;
          first.object = null;   // forget old object
          head = first;            // first becomes new head
        }
        return x;
      }
    }
  }

  static class Node {            // local node class for queue
    Object object;
    Node next = null;

    Node(Object x) { object = x; }
  }
}

Это довольно хорошая очередь. Он использует два монитора, так что Производитель и Потребитель могут одновременно получить доступ к Очереди. Ницца! Тем не менее, синхронизация на «last» и «head» смущает меня здесь. В книге говорится, что это необходимо для ситуации, в которой очередь в настоящее время или собирается иметь 0 записей. Хорошо, достаточно справедливо, и этот вид имеет смысл.

Однако затем я посмотрел на Java Concurrency LinkedBlockingQueue. оригинальная версия очереди не синхронизируется по голове или хвосту (я также хотел опубликовать другую ссылку на современную версию, которая также страдает от той же проблемы, но я не мог сделать это, потому что я новичок). Интересно почему нет? Я что-то здесь упускаю? Есть ли какая-то особенная природа модели памяти Java, которую я пропускаю? Я бы подумал для наглядности, что нужна эта синхронизация? Буду признателен за мнение экспертов!

Answer 1

В версии, к которой вы добавили ссылку, а также версию в последней JRE, элемент внутри класса Node является изменчивым, который обеспечивает чтение и запись, чтобы быть видимыми для всех других потоков, вот более подробное объяснение 1001 *http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile

Answer 2

Тонкость здесь в том, что synchronized (null) генерирует исключение NullPointerException, поэтому ни head, ни last не могут становиться null. Они оба инициализируются значением того же фиктивного узла, который никогда не возвращается и не удаляется ни из одного списка.

put () и poll () синхронизируются на двух разных блокировках. Методы должны были бы синхронизироваться с одной и той же блокировкой, чтобы быть потокобезопасными по отношению друг к другу, если бы они могли изменять одно и то же значение из разных потоков. Единственная ситуация, в которой это проблема, - это когда head == last (т.е. это один и тот же объект, на который ссылаются различные переменные-члены). Вот почему код синхронизируется с головой и последним - в большинстве случаев это будут быстрые, необоснованные блокировки, но иногда заголовок и последний будут одним и тем же экземпляром, и один из потоков должен будет блокировать другой.

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