06 | 用“等待-通知”机制优化循环等待

由上文可知：在破坏占用且等待条件的时候，如果转出账本和转入账本不满足同时在文件架上这个条件，就用死循环的方式来循环等待，核心代码如下：

1
2
3

// 一次性申请转出账户和转入账户，直到成功
while(!actr.apply(this, target))
  ；

这种循环等待的方式极其浪费CPU，如果并发冲突大，可能要循环上万次才能取到锁。

其实在这种场景下，最好的方案应该是：如果线程要求的条件（转出账本和转入账本同在文件架上）不满足，则线程阻塞自己，进入等待状态，当线程要求的条件满足后，通知等待的线程重新执行。其中，使用线程阻塞的方式就能避免循环等待消耗CPU的问题。

下面我们看看Java语言是如何支持等待——通知机制的。

就医流程

我们先看一个现实世界里面的就医流程，它有着完善的等待——通知机制，所以对比就医流程，我们可以更好地理解等待——通知机制。

就医流程基本上是这样：

患者先去挂号，然后到就诊门口分诊，等待叫号；
当叫到自己的号时，患者就可以找大夫就诊了；
就诊过程中，大夫可能会让患者去做检查，同时叫下一位患者；
当患者做完检查后，拿检测报告重新分诊，等待叫号；
当大夫再次叫到自己的号时，患者再去找大夫就诊。

这个就诊流程能保证同一时刻大夫只为一个患者服务，而且还能保证大夫和患者的效率，不会让患者在大夫诊室门口傻等。下面我们把Java的等待——通知机制和就诊流程对比起来，并关注一下上面忽视的细节：

患者到就诊室门口分诊，类似于线程要去获取互斥锁；当患者被叫到时，类似线程已经获取到锁了；
大夫让患者去做检查（缺少检测报告不能诊断病因），类似于线程要求的条件没有被满足；
患者去做检查，类似于线程进入等待状态；然后大夫叫下一个患者，这个步骤对应到程序里，本质是线程释放持有的互斥锁；
患者做完检查，类似于线程要求的条件已经满足；患者拿检测报告重新分诊，类似于线程需要重新获取互斥锁。

所以加上这些至关重要的细节，综合一下，就可以得出一个完整的等待——通知机制：线程首先获取互斥锁，当线程要求的条件不满足时，释放互斥锁，进入等待状态；单线程要求的条件满足时，通知等待的线程，重新获取互斥锁。

用 synchronized 实现等待——通知机制

在 Java 中，等待——通知机制可以有多种实现方式，比如内置的 synchronized 配合 wait()、notify()、notifyAll() 这三个方法就能轻松实现。

在下面这个图里，左边有一个等待队列，同一时刻，只允许一个线程进入 synchronized 保护的临界区（这个临界区可以看作大夫的诊室），当有一个线程进入临界区后，其他线程就只能进入图中左边的等待队列里等待（相当于患者分诊等待）。这个等待队列和互斥锁是一对一的关系，每个互斥锁都有自己独立的等待队列。

在并发程序中，当一个线程进入临界区后，由于某些条件不满足，需要进入等待状态，Java 对象的 wait() 方法就能够满足这种需求。如上图所示，当调用 wait() 方法后，当前线程就会被阻塞，并且进入到右边的等待队列中，这个等待队列也是互斥锁的等待队列。线程在进入等待队列的同时，会释放持有的互斥锁，线程释放锁后，其他线程就有机会获得锁，并进入临界区了。

那线程要求的条件满足时，该怎么通知这个等待的线程呢？很简单，就是 Java 对象的 notify() 和 notifyAll() 方法。当条件满足时调用 notify()，会通知等待队列（互斥锁的等待队列）中的线程，告诉它条件曾经满足过。

为什么说是曾经满足过呢？因为 notify() 只能保证在通知时间点，条件是满足的。而被通知线程的执行时间点和通知的时间点基本上不会重合，所以当线程执行的时候，很可能条件已经不满足了（保不齐有其他线程插队）。这一点需要格外注意。

除此之外，还有一个需要注意的点，被通知的线程要想重新执行，仍然需要获取到互斥锁（因为曾经获取的锁在调用 wait() 时已经释放了）。

上面我们一直强调 wait()、notify()、notifyAll() 方法操作的等待队列是互斥锁的等待队列，所以如果 synchronized 锁定的是 this，那么对应的一定是 this.wait()、this.notify()、this.notifyAll()；如果 synchronized 锁定的是 target，那么对应的一定是 target.wait()、target.notify()、target.notifyAll()。而且 wait()、notify()、notifyAll() 这三个方法能够被调用的前提是已经获取了相应的互斥锁，所以我们会发现 wait()、notify()、notifyAll() 都是在 synchronized{}内部被调用的。如果在 synchronized{} 外部调用，或者锁定的 this，而用 target.wait() 调用的话，JVM 会抛出一个运行时异常：java.lang.IllegalMonitorStateException。

小试牛刀：一个更好地资源分配器

等待 - 通知机制的基本原理搞清楚后，我们就来看看它如何解决一次性申请转出账户和转入账户的问题吧。在这个等待 - 通知机制中，我们需要考虑以下四个要素。

互斥锁：上一篇文章我们提到 Allocator 需要是单例的，所以我们可以用 this 作为互斥锁。
线程要求的条件：转出账户和转入账户都没有被分配过。
何时等待：线程要求的条件不满足就等待。
何时通知：当有线程释放账户时就通知。

将上面几个问题考虑清楚，可以快速完成下面的代码。需要注意的是我们使用了：

1
2
3

while(条件不满足) {
    wait();
}

利用这种范式可以解决上面提到的条件曾经满足过这个问题。因为当wait() 返回时，有可能条件已经发生变化了，曾经条件满足，但是现在已经不满足了，所以要重新检验条件是否满足。范式，意味着是经典做法，所以没有特殊理由不要尝试换个写法。

class Allocator {
  private List<Object> als;
  // 一次性申请所有资源
  synchronized void apply(Object from, Object to){
    // 经典写法
    while(als.contains(from) || als.contains(to)){
      try{
        wait();
      }catch(Exception e){
      }   
    } 
    als.add(from);
    als.add(to);  
  }
  // 归还资源
  synchronized void free(Object from, Object to){
    als.remove(from);
    als.remove(to);
    notifyAll();
  }
}

注意：尽量使用 notifyAll()，notify() 是会随机地通知等待队列中的一个线程，而 notifyAll() 会通知等待队列中的所有线程。使用 notify() 也很有风险，它的风险在于可能导致某些线程永远不会被通知到。

课后思考

很多面试都会问到，wait() 方法和 sleep() 方法都能让当前线程挂起一段时间，那它们的区别是什么？

wait与sleep区别在于：

wait会释放所有锁而sleep不会释放锁资源；
wait只能在同步方法和同步块中使用，而sleep任何地方都可以；
wait无需捕捉异常，而sleep需要；

两者相同点：都会让渡CPU执行时间，等待再次调度！