Java 线程 — ConcurrentLinkedQueue

duanjian01 5年前
   <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>