再谈阻塞(3)：cxq、EntryList与WaitSet

发表于 | 分类于 | 阅读次数:
字数统计: 2,722 | 阅读时长 ≈ 11

通过上一篇的分析，我们知道当一个线程尝试获取monitor锁失败后，最终会被封装成一个ObjectWaiter对象，放入一个以_cxq为头节点的队列中，这个队列通过一个简单链表实现。每当有新来的节点入队，它的next指针总是指向之前队列的头节点，而_cxq指针会指向该新入队的节点，这就是后来者当头。实际上synchronized锁机制内维护了三个队列，除了cxq，还包括EntryList与WaitSet，本篇将以此为研究对象，弄清内置锁队列的运作机制。

并发示例

这里提供一个新的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class SynchronizedDemo02 {
    public static void main(String[] args) throws InterruptedException {
        byte[] lock = new byte[0];
        Runnable task01 = () -> {
            synchronized (lock) {
                System.out.println(Thread.currentThread().getName() + ": begin");
                try {
                    Thread.sleep(3000);
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName() + ": finish");
            }
        };
        Runnable taskOpen = () -> {
            synchronized (lock) {
                System.out.println(Thread.currentThread().getName() + ": begin");
                lock.notify();
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName() + ": finish");
            }
        };
        Thread t1 = new Thread(task01, "t1");
        Thread t2 = new Thread(taskOpen, "t2");
        Thread t3 = new Thread(taskOpen, "t3");
        t1.start();
        Thread.sleep(1000);
        t2.start();
        Thread.sleep(2000); // 设置不同的睡眠时间，可能会产生不同的打印效果；
        System.out.println("t1: " + t1.getState());
        t3.start();
    }
}

本示例包括三个线程和两个任务，线程t1先开启并获得锁，t2、t3后续开启。t1睡眠三秒后挂起，t2拿到锁，执行过程中调用notify，并睡眠三秒。先看看输出是怎样的：

1
2
3
4
5
6
7
t1: begin
t2: begin
t1: WAITING
t2: finish
t1: finish
t3: begin
t3: finish

观察这个输出结果可以发现两个表象：

  • 表象1： t1: finish出现在t2: finish后，哪怕t2调用notify方法后三秒才执行t2: finish的打印语句；
  • 表象2： t3在t1后拿到锁；

现在将源代码稍稍更改一下，把带有注释的语句Thread.sleep(2000);更改为Thread.sleep(1500);，再次运行，输出变更为：

1
2
3
4
5
6
7
t1: begin
t1: TIMED_WAITING
t3: begin
t3: finish
t2: begin
t2: finish
t1: finish

从输出结果可以看出：

  • 表象3：t3的打印出现在t2的打印之前；
  • 表象4：t1: finish在最后打印；

仅仅将代码稍作改动就出现了不同的打印结果，下面将深入代码探寻其原因。

线程调用wait()进入WaitSet

前一篇文章探索了一个线程从尝试获取重量级锁到失败的过程，线程随即进入到了cxq队列并将自己挂起。挂起的线程还可能存在于WaitSet中，t1是通过调用lock.wait();来实现的。在objectMonitor.cpp下，查看void ObjectMonitor::wait(jlong millis, bool interruptible, TRAPS)函数，一开始有：

1
2
3
4
ObjectWaiter node(Self);
node.TState = ObjectWaiter::TS_WAIT ;
Self->_ParkEvent->reset() ;
OrderAccess::fence();

底层的wait函数仍然是先将当前线程封装成一个ObjectWaiter，设置其TState状态为TS_WAIT，接下里执行最重要的入队代码：

1
2
3
Thread::SpinAcquire (&_WaitSetLock, "WaitSet - add") ;
AddWaiter (&node) ;
Thread::SpinRelease (&_WaitSetLock) ;

这段代码的背景注释给出了很清晰的介绍：

  • WaitSet是一个双向环形链表实现的等待队列，但它可以是优先级队列或任何数据结构；
  • _WaitSetLock用来保护该等待队列。通常只有monitor owner能访问等待队列，除非有一个超时中断将其唤醒；
  • 竞争并不激烈，所以我们使用简单的旋转锁而不是更重的阻塞锁来保障同步；

继续追踪AddWaiter：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline void ObjectMonitor::AddWaiter(ObjectWaiter* node) {
  assert(node != NULL, "should not dequeue NULL node");
  assert(node->_prev == NULL, "node already in list");
  assert(node->_next == NULL, "node already in list");
  // put node at end of queue (circular doubly linked list)
  if (_WaitSet == NULL) {
    _WaitSet = node;
    node->_prev = node;
    node->_next = node;
  } else {
    ObjectWaiter* head = _WaitSet ;
    ObjectWaiter* tail = head->_prev;
    assert(tail->_next == head, "invariant check");
    tail->_next = node;
    head->_prev = node;
    node->_next = head;
    node->_prev = tail;
  }
}

以上是将node入队一个双向环形链表末尾(这里的末尾参照物是head指针)的简单操作。

当一个线程调用了wait()后，不仅会挂起自己，还会释放锁，涉及到如下代码：

1
2
3
4
5
6
7
    ...
exit (true, Self) ;                    // exit the monitor
guarantee (_owner != Self, "invariant") ;
    ...

exit()的解析后续会展开。

顺便也将出队操作列出：

1
2
3
4
5
6
7
8
inline ObjectWaiter* ObjectMonitor::DequeueWaiter() {
  // dequeue the very first waiter
  ObjectWaiter* waiter = _WaitSet;
  if (waiter) {
    DequeueSpecificWaiter(waiter);
  }
  return waiter;
}

可见每次出队都是单个头节点，而非倾倒(drain)。DequeueSpecificWaiter函数完全从链表中删除了waiter节点，这里就不贴码了。

notify()的底层实现

为了解释本文开篇列举的并发示例的输出现象，我们还需要先了解notify()的底层实现。这个底层实现通过objectMonitor.cpp下的void ObjectMonitor::notify(TRAPS)来完成。

浏览代码会发现，存在不同的策略可供选择，而int Policy = Knob_MoveNotifyee ;，查询相关字段有static int Knob_MoveNotifyee = 2;，所以默认为Policy = 2时的策略。这里仅为说明原理，所以暂时只分析默认策略，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ObjectWaiter * iterator = DequeueWaiter() ;
    ...
ObjectWaiter * List = _EntryList ;
    ...
if (Policy == 2) {      // prepend to cxq
   // prepend to cxq
   if (List == NULL) {
       iterator->_next = iterator->_prev = NULL ;
       _EntryList = iterator ;
   } else {
      iterator->TState = ObjectWaiter::TS_CXQ ;
      for (;;) {
          ObjectWaiter * Front = _cxq ;
          iterator->_next = Front ;
          if (Atomic::cmpxchg_ptr (iterator, &_cxq, Front) == Front) {
              break ;
          }
      }
   }
}

Policy == 2在这段代码中表达的策略：

  1. 如果EntryList是空队列，则iterator单个节点构成一个双向环形链表，然后_EntryList指向该节点；
  2. 如果EntryList不为空，通过CAS将iterator入队cxq，并将_cxq指针指向iterator；

现在可以解释表象1：

由于notify()在默认策略下只是将代表线程的节点由WaitSet转移到其它队列，并没有唤醒线程，所以即便调用了notify方法后继续执行三秒，线程t2也只有等待被唤醒后才能打印语句，所以t1: finish出现在t2: finish后。

那究竟什么时候才唤醒线程？

ObjectMonitor::exit函数解析

在虚拟机层线程的唤醒是通过ObjectMonitor::ExitEpilog函数完成的，该函数同时还完成释放锁的操作。把核心代码抽离出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ObjectMonitor::ExitEpilog (Thread * Self, ObjectWaiter * Wakee) {
  // 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 ;
   Wakee  = NULL ;
   // 释放锁；
  OrderAccess::release_store_ptr (&_owner, NULL) ;
  OrderAccess::fence() ;
  // 线程唤醒；
  Trigger->unpark() ;
}

ExitEpilog又封装在ObjectMonitor::exit函数中，当Java虚拟机执行代表退出monitor锁的字节码指令时，会调用ObjectMonitor::exit函数。为了保证鲁棒性，该函数还会考虑轻量级锁的情况，轻量级锁在这里用一个BasicLock指针代表，会被当成重量级锁来处理，所以会有一些设定。

在这里本人重点关心的是各队列中节点的变化。实际上，在一个线程释放锁之后，关于如何唤醒后继线程，Java虚拟机也提供了几种模式，前面分析notify采用的是默认策略，这里也只单讲默认模式，代码中的设定是int QMode = Knob_QMode ;，查询相关字段有static int Knob_QMode = 0 ;，所以默认模式是QMode == 0;，抽离出关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void ObjectMonitor::exit(bool not_suspended, TRAPS) {
    ...
  for(;;) {
    ObjectWaiter * w = NULL ;
    w = _EntryList  ;
    if (w != NULL) {
      assert (w->TState == ObjectWaiter::TS_ENTER, "invariant") ;
      ExitEpilog (Self, w) ;
      return ;
    }
    w = _cxq ;
    if (w == NULL) continue ;
    for (;;) {
      assert (w != NULL, "Invariant") ;
      ObjectWaiter * u = (ObjectWaiter *) Atomic::cmpxchg_ptr (NULL, &_cxq, w) ;
      if (u == w) break ;
      w = u ;
    }
    assert (w != NULL              , "invariant") ;
    assert (_EntryList  == NULL    , "invariant") ;
    // 抽离出来的QMode == 0 or QMode == 2情况下代码；
    _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 ;
    }
    // _succ表示已经存在唤醒的线程；
    if (_succ != NULL) continue;
    w = _EntryList  ;
    if (w != NULL) {
      guarantee (w->TState == ObjectWaiter::TS_ENTER, "invariant") ;
      ExitEpilog (Self, w) ;
      return ;
    }
  }
    ...
}

这段代码的含义：

  1. 若EntryList队列的头节点_EntryList不为null，那么直接唤醒该头节点封装的线程，然后返回；
  2. 1的条件不满足，程序继续向下执行，若cxq队列的头节点_cxq为null，则跳过当次循环；
  3. 若程序继续向下执行说明cxq队列不为空，EntryList队列为空。接下来是一个内嵌的for循环，目的是取出cxq队列中的所有元素，方法是通过一个临时变量指针获得构成队列的整个链表，然后将_cxq指针置为NULL；
  4. 第二个内嵌for循环是QMode == 0策略的内容，目的在于将第三步得到的单向链表倾倒(drain)进EntryList队列，具体方法是将_EntryList指针指向单向链表的头节点，然后通过for循环将单向链表构造成双向环形链表；
  5. 通过ExitEpilog函数释放monitor锁并唤醒EntryList队列的头节点；

解释开篇并发示例输出表象

首先解释未改动之前的代码输出结果。

表象1已经在之前解析notify方法的时候解释过了，notify并不唤醒线程；

接着解释表象2(即：t3在t1后拿到锁)：

首先要了解t3启动的时机，当t3启动，此时的t1已经睡眠了1+2秒(这里是近似值，实际上线程启动挂起会有时间消耗，后文出现时间常量亦是近似处理)，并通过调用wait()将自己挂起在WaitSet并释放锁；

而t2已经被挂起多时，它之前在cxq队列中，t3释放锁后它被drain入EntryList队列，并被ExitEpilog函数唤醒；

t2运行3秒后释放锁，现在的情况是，t3在cxq中，t1在WaitSet中，而EntryList此时为空，根据notify()的默认策略，处于WaitSet中封装了t1线程的节点会从WaitSet出队，转而进入EntryList，构成一个双向环形链表；

根据exit()的默认模式，EntryList队列的头节点_EntryList不为null，直接唤醒该头节点封装的线程t1，所以t3在t2后拿到锁；

接下来解释表象3和表象4，这里再将它们列出方便查看：

  • 表象3：t3的打印出现在t2的打印之前；
  • 表象4：t1: finish在最后打印；

首先解释表象3：

改动代码后，t3启动时，t1已经sleep()了2.5秒，还处在TIMED_WAITING状态，t3在尝试获取锁失败后会和t2一样，进入cxq，但由于cxq特殊的入队规则，t3后来者当头，构成t3 -> t2的单链表形式；

t1调用wait()后将自己挂起，并调用exit()，此时EntryList为空而cxq不为空，cxq中的链表整条drain入EntryList，并通过for循环将其构成双向环形链表；

通过ExitEpilog函数释放monitor锁并唤醒EntryList队列的头节点，也就是t3了，所以t3的打印在t2之前；

承接前面的内容，再来解释表象4：

t3调用notify()，此时t2处在EntryList，所以按照notify默认策略，EntryList不为空，通过CAS将t1入队cxq，并将_cxq指针指向t1；

当t3执行exit()，t1处在cxq，t2处在EntryList，按照策略，t2先行执行，所以t1的finish打印出现在最后；

小结

本篇通过对源码进行分析，解释了开篇运行示例后出现的四个表象。经此一役，本人对内置锁队列的运作机制有了一个比较清晰的认识。

参考

ObjectMonitor日文源码注释