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

说明

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

synchronized 中同步队列有两个 _cxqEntryList,基于不同的 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 协议》,转载必须注明作者和本文链接
讨论数量: 2

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!