synchronized 中的同步队列与等待队列

说明

• 同步队列：排队取锁的线程所在的队列
• 等待队列：调用 wait 方法后，线程会从同步队列转移到等待队列

synchronized 中同步队列有两个 _cxq 与 EntryList，基于不同的 QMode 来调整线程的出队策略

• _cxq(竞争队列):抢锁失败后，线程会进入此队列，此队列大部分情况时单向链表，入队策略是 后来者当头

• EntryList:默认情况下（根据 Knob_MoveNotifyee 判断，源码默认为 2 ，当 EntryList 不为空，Policy == 2 时，参阅 源码 1720-1735行)，线程被唤醒时，会从等待队列转移到此队列，此队列是一个双向链表

• WaitSet:等待队列，调用 wait 方法后，线程会进入此队列

出队策略

QMode 一共有5种值，0、1、2、3、4，不同的 QMode ，会影响 _cxq 和 EntryList 的优先级，默认情况下，QMode 为 0

      // 当 _cxq 不为空，且 QMode 为 2 时，会直接使用 _cxq 的顺序进行唤醒（后来者当头）
      if (QMode == 2 && _cxq != NULL) {
          w = _cxq ;
          assert (w != NULL, "invariant") ;
          assert (w->TState == ObjectWaiter::TS_CXQ, "Invariant") ;
          ExitEpilog (Self, w) ;
          return ;
      }

      // 当 _cxq 不为空，且 QMode 为 3 时，将 _cqx 链接到 EntyList 后面
      if (QMode == 3 && _cxq != NULL) {
          w = _cxq ;

          ObjectWaiter * q = NULL ;
          ObjectWaiter * p ;
          // 将 _cqx 变成双向链表
          for (p = w ; p != NULL ; p = p->_next) {
              guarantee (p->TState == ObjectWaiter::TS_CXQ, "Invariant") ;
              p->TState = ObjectWaiter::TS_ENTER ;
              p->_prev = q ;
              q = p ;
          }
          // 将 _cqx 拼在 EntryList 后面
          // Append the RATs to the EntryList
          // TODO: organize EntryList as a CDLL so we can locate the tail in constant-time.
          ObjectWaiter * Tail ;
          for (Tail = _EntryList ; Tail != NULL && Tail->_next != NULL ; Tail = Tail->_next) ;
          if (Tail == NULL) {
              _EntryList = w ;
          } else {
              Tail->_next = w ;
              w->_prev = Tail ;
          }

          // Fall thru into code that tries to wake a successor from EntryList
      }

      // 当 _cxq 不为空，且 QMode 为 4 时，将 EntyList 链接到 _cqx 后面
      if (QMode == 4 && _cxq != NULL) {

          w = _cxq ;
          ...
          // 将 cqx 变为双向链表
          ObjectWaiter * q = NULL ;
          ObjectWaiter * p ;
          for (p = w ; p != NULL ; p = p->_next) {
              guarantee (p->TState == ObjectWaiter::TS_CXQ, "Invariant") ;
              p->TState = ObjectWaiter::TS_ENTER ;
              p->_prev = q ;
              q = p ;
          }

          // 将 EntryList 的头设为 _cqx
          if (_EntryList != NULL) {
              q->_next = _EntryList ;
              _EntryList->_prev = q ;
          }
          _EntryList = w ;
      }

      w = _EntryList  ;
      // 除了 (Qmode == 2 && _cqx != null) 的情况，按照 EntryList 的顺序出队
      if (w != NULL) {
          assert (w->TState == ObjectWaiter::TS_ENTER, "invariant") ;
          ExitEpilog (Self, w) ;
          return ;
      }


      w = _cxq ;
      if (w == NULL) continue ;

     // EntryList 为空，QMode 为 1 ，翻转 _cqx ，然后出队 
      if (QMode == 1) {
         ...
         ObjectWaiter * t = w ;
         ...
         // 翻转 _cqx
         while (t != NULL) {
             guarantee (t->TState == ObjectWaiter::TS_CXQ, "invariant") ;
             t->TState = ObjectWaiter::TS_ENTER ;
             u = t->_next ;
             t->_prev = u ;
             t->_next = s ;
             s = t;
             t = u ;
         }
         // 赋值给 _EntryList
         _EntryList  = s ;
         assert (s != NULL, "invariant") ;
      } else {
         // EntryList 为空，QMode 为 0，直接将 _cqx 赋值给 EntryList，同时变成双向链表 
         _EntryList = w ;
         ObjectWaiter * q = NULL ;
         ObjectWaiter * p ;
         for (p = w ; p != NULL ; p = p->_next) {
             guarantee (p->TState == ObjectWaiter::TS_CXQ, "Invariant") ;
             p->TState = ObjectWaiter::TS_ENTER ;
             p->_prev = q ;
             q = p ;
         }
      }

      // 出队
      w = _EntryList  ;
      if (w != NULL) {
          guarantee (w->TState == ObjectWaiter::TS_ENTER, "invariant") ;
          ExitEpilog (Self, w) ;
          return ;
      }

void ObjectMonitor::ExitEpilog (Thread * Self, ObjectWaiter * Wakee) {
   assert (_owner == Self, "invariant") ;

   // Exit protocol:
   // 1. ST _succ = wakee
   // 2. membar #loadstore|#storestore;
   // 2. ST _owner = NULL
   // 3. unpark(wakee)

   _succ = Knob_SuccEnabled ? Wakee->_thread : NULL ;
   ParkEvent * Trigger = Wakee->_event ;

   // Hygiene -- once we've set _owner = NULL we can't safely dereference Wakee again.
   // The thread associated with Wakee may have grabbed the lock and "Wakee" may be
   // out-of-scope (non-extant).
   Wakee  = NULL ;

   // Drop the lock
   OrderAccess::release_store_ptr (&_owner, NULL) ;
   OrderAccess::fence() ;                               // ST _owner vs LD in unpark()

   if (SafepointSynchronize::do_call_back()) {
      TEVENT (unpark before SAFEPOINT) ;
   }

   DTRACE_MONITOR_PROBE(contended__exit, this, object(), Self);
   Trigger->unpark() ;

   // Maintain stats and report events to JVMTI
   if (ObjectMonitor::_sync_Parks != NULL) {
      ObjectMonitor::_sync_Parks->inc() ;
   }
}

参考资料

1. Java 并发——基石篇（中）
2. 再谈阻塞(3)：cxq、EntryList与WaitSet
3. OpenJDK / jdk8 / jdk8 / hotspot

本作品采用《CC 协议》，转载必须注明作者和本文链接