Java 线程 — ConcurrentLinkedQueue

   <h2><strong>ConcurrentLinkedQueue</strong></h2>    <p>在考虑并发的时候可以先考虑单线程的情况，然后再将并发的情况考虑进来。</p>    <p>比如ConcurrentLinkedQueue：</p>    <ol>     <li>先考虑单线的offer</li>     <li>再考虑多线程时候的offer：      <ul>       <li>多个线程offer</li>       <li>部分线程offer，部分线程poll        <ul>         <li>offer比poll快</li>         <li>poll比offer快</li>        </ul> </li>      </ul> </li>    </ol>    <h2><strong>offer</strong></h2>    <pre>  <code class="language-java">public boolean offer(E e) {      checkNotNull(e);      // 新建一个node      final Node<E> newNode = new Node<E>(e);            // 不断重试（for只有初始化条件，没有判断条件），直到将node加入队列      // 初始化p、t都是指向tail      // 循环过程中一直让p指向最后一个节点。让t指向tail      for (Node<E> t = tail, p = t;;) {          // q一直指向p的下一个          Node<E> q = p.next;          if (q == null) {              // p is last node              // 如果q为null表示p是最后一个元素，尝试加入队列              // 如果失败，表示其他线程已经修改了p指向的节点              if (p.casNext(null, newNode)) {                  // Successful CAS is the linearization point                  // for e to become an element of this queue,                  // and for newNode to become "live".                  // node加入队列之后，tail距离最后一个节点已经相差大于一个了，需要更新tail                  if (p != t) // hop two nodes at a time                      // 这儿允许设置tail为最新节点的时候失败，因为添加node的时候是根据p.next是不是为null判断的，                      casTail(t, newNode);  // Failure is OK.                  return true;              }              // Lost CAS race to another thread; re-read next          }          else if (p == q)              // 虽然q是p.next，但是因为是多线程，在offer的同时也在poll，如offer的时候正好p被poll了，那么在poll方法中的updateHead方法会将head指向当前的q，而把p.next指向自己，即：p.next == p              // 这个时候就会造成tail在head的前面，需要重新设置p              // 如果tail已经改变，将p指向tail，但这个时候tail依然可能在head前面              // 如果tail没有改变，直接将p指向head              // We have fallen off list.  If tail is unchanged, it              // will also be off-list, in which case we need to              // jump to head, from which all live nodes are always              // reachable.  Else the new tail is a better bet.              p = (t != (t = tail)) ? t : head;          else              // Check for tail updates after two hops.              // tail已经不是最后一个节点，将p指向最后一个节点              p = (p != t && t != (t = tail)) ? t : q;      }  }</code></pre>    <h2><strong>poll</strong></h2>    <pre>  <code class="language-java">public E poll() {      // 如果出现p被删除的情况需要从head重新开始      restartFromHead:      for (;;) {          for (Node<E> h = head, p = h, q;;) {              E item = p.item;                if (item != null && p.casItem(item, null)) {                  // Successful CAS is the linearization point                  // for item to be removed from this queue.                  if (p != h) // hop two nodes at a time                      updateHead(h, ((q = p.next) != null) ? q : p);                  return item;              }              else if ((q = p.next) == null) {                  // 队列为空                  updateHead(h, p);                  return null;              }              else if (p == q)                  // 当一个线程在poll的时候，另一个线程已经把当前的p从队列中删除——将p.next = p，p已经被移除不能继续，需要重新开始                  continue restartFromHead;              else                  p = q;          }      }  }    final void updateHead(Node<E> h, Node<E> p) {      if (h != p && casHead(h, p))          h.lazySetNext(h);  }</code></pre>    <h3><strong>为什么会出现p == q</strong></h3>    <p>假设下面这种情况：</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/59a127eb08d4f8a2d14ef31f6394e1a7.png"></p>    <p>在第一种情况下，线程A执行offer操作：</p>    <p>第一次循环的时候</p>    <ol>     <li>tail = node0, p = t = node0</li>     <li>执行 Node<E> q = p.next; 之后q = p.next，也就是node0.next</li>     <li>执行 if (q == null) ，不满足，继续往下</li>     <li>到了 else if (p == q) 这一步的时候线程A暂停</li>    </ol>    <p>线程A现在的结果是：</p>    <pre>  <code class="language-java">head = node0  tail = node0  t = node0  p = node0  q = node0.next</code></pre>    <p>因为程序时多线程的，我们假设线程A暂定在了第4步，接下来看线程B，线程B执行poll操作：</p>    <p>第一次循环：</p>    <ol>     <li>head = node0, p = h = node0;</li>     <li>执行 E item = p.item; ，item = null</li>     <li>if (item != null && p.casItem(item, null)) 不满足</li>     <li>执行 else if ((q = p.next) == null) ，q = node1，条件不满足</li>     <li>执行 else if (p == q) ，条件不满足</li>     <li>执行 p = q; ，p = node1</li>    </ol>    <p>第二次循环：</p>    <ol>     <li>head = node0, h = node0, p = node1;</li>     <li>执行 E item = p.item; ，item = node2</li>     <li>if (item != null && p.casItem(item, null)) ， item != null 满足,如果CAS操作成功      <ol>       <li>p != h 成立，调用updateHead</li>       <li>执行 updateHead(h, ((q = p.next) != null) ? q : p); 之后，q = node2</li>       <li>在updateHead里面        <ol>         <li>h != p 成立，如果CAS操作成功（将head设置为node2）</li>         <li>执行 h.lazySetNext(h); ，这个时候 h = node0 ，这个方法执行完之后，node0.next = node0</li>        </ol> </li>      </ol> </li>     <li>将item返回</li>    </ol>    <p>这个时候队列就是图中第二种情况，线程A结果为：</p>    <pre>  <code class="language-java">head = node2  tail = node0  t = node0  p = node0  q = node0.next = node0</code></pre>    <p>看到结果了吧，这个时候 p = q = node0 ！ 其实主要原因是在 updateHead方法的 h.lazySetNext(h) 操作里面，将旧的head.next设置成为了自己即 head.next = head。但是要注意：是旧的head</p>    <p>从上面分析的过程要注意：</p>    <ol>     <li>多线程执行环境，单线程下一定不会出现这种情况</li>     <li>注意引用赋值比如 Node<E> q = p.next ，q指向的是p.next，虽然目前 p.next = node1 ，但是当p.next指向变了之后，q也就跟着变了</li>     <li>再就是阅读源码的时候一定要弄清楚调用的每个方法的作用，这样才能对整个方法有一个准确的理解，比如这里的 h.lazySetNext(h);</li>    </ol>    <p><strong>参考</strong></p>    <p><a href="/misc/goto?guid=4959725300515504184" rel="nofollow,noindex">http://www.jianshu.com/p/7816c1361439</a></p>    <p>Java并发编程的艺术</p>    <p> </p>    <p>来自：http://www.cnblogs.com/sunshine-2015/p/6067709.html</p>    <p> </p>