undefinedfix
Sign in

Why can't the tail in transferqueue be deleted under the fair mode of synchronous queue

somutesting edited in Fri, 25 Nov 2022

For example, in the implementation of synchronous queue fair mode, in the clean method of transferqueue, when the cleared node is tail, why can't CAS be changed to pred directly? Instead, it's necessary to set PRED to clean me???

void clean(QNode pred, QNode s) {  
    s.waiter \= null; // forget thread  
 /\* \* At any given time, exactly one node on list cannot be \* deleted -- the last inserted node. To accommodate this, \* if we cannot delete s, we save its predecessor as \* "cleanMe", deleting the previously saved version \* first. At least one of node s or the node previously \* saved can always be deleted, so this always terminates. \*/  while (pred.next \== s) { // Return early if already unlinked  
  QNode h = head;  
  QNode hn = h.next; // Absorb cancelled first node as head  
  if (hn != null && hn.isCancelled()) {  
            advanceHead(h, hn);  
 continue;  }  
        QNode t = tail; // Ensure consistent read for tail  
  if (t == h)  
            return;  
  QNode tn = t.next;  
 if (t != tail)  
            continue;  
 if (tn != null) {  
            advanceTail(t, tn);  
 continue;  }  
        if (s != t) {        // If not tail, try to unsplice  
  QNode sn = s.next;  
 if (sn == s || pred.casNext(s, sn))  
                return;  
  }  
  //对于s == t 时的情况,为什么需要这么复杂的操作?
        QNode dp = cleanMe;  
 if (dp != null) {    // Try unlinking previous cancelled node  
  QNode d = dp.next;  
  QNode dn;  
 if (d == null ||               // d is gone or  
  d == dp ||                 // d is off list or  
  !d.isCancelled() ||        // d not cancelled or  
  (d != t &&                 // d not tail and  
  (dn = d.next) != null &&  //   has successor  
  dn != d &&                //   that is on list  
  dp.casNext(d, dn)))       // d unspliced  
  casCleanMe(dp, null);  
 if (dp == pred)  
                return; // s is already saved node  
  } else if (casCleanMe(null, pred))  
            return; // Postpone cleaning s  
  }  
}
0 Replies