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

在破话占用且等待条件的时候，如果转出账本和转入账本不满足同时在文件架上这个调教，就用死循环的方式来循环等待：while(!actr.apply(this,target))。

如果apply()操作耗时非常短，而且并发冲突量也不大时，这个方案可行，这种场景下，循环上几次或者几十次就能一次性获取转出账户和转入账户了。但是如果apply()操作耗时长，或者并发冲突量大的时候，循环等待这种方案就不适用了，这种场景下，可能要循环上万次才能获取到锁，太消耗CPU了。

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

完美的就医流程

现实世界中的就医流程，有着完善的等待-通知机制：

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

这个等待-通知机制的就医流程，不仅能够保证同一时刻大夫只为一个患者服务，而且还能够保证大夫和患者的效率。

等待-通知机制中的细节：

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

一个完整的等待-通知机制：线程首先获取互斥锁，当线程要求的条件不满足时，释放互斥锁，进入等待状态；当要求的条件满足时，通知等待的线程，重新获取互斥锁。

用synchronized实现等待-通知机制

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

左边有一个等待队列，同一时刻，只允许一个线程进入synchronized保护的临界区，当有一个线程进入临界区后，其他线程就只能进入图中左边的等待队列里等待。这个等待队列和互斥锁是一对一的关系，每个互斥锁都有自己独立的等待队列。

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

当条件满足时叼你公用notify()，会通知等待队列(互斥锁的等待队列)中的线程，告诉它条件曾经满足过。因为notify()只能保证在通知的时间点，条件是满足的。而被通知线程的执行时间点和通知的时间点基本上不会重合，所以当线程执行的时候，很可能条件已经不满足了(保不齐又其他线程插队)。

被通知的线程要想重新执行，仍然需要获取到互斥锁(因为曾经获取的锁在调用wait()时已经释放了)。

wait释放资源，sleep不释放资源。
wait是Object顶级父类的方法，sleep则是Thread的方法。
wait只能在同步方法和同步块中使用，sleep在任何地方都可以。
wait无须捕捉异常，sleep需要。

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作为互斥锁。
线程要求的条件：转出账户和转入账户都没有被分配过。
何时等待：线程要求的条件不满足就等待。
何时通知：当有线程释放账户时就通知。

利用while(条件不满足) { wait() }这种范式可以解决条件曾经满足过这个问题。当wait()返回时，有可能条件已经发生变化了，曾经条件满足，但是现在已经不满足了，所以要重新检验条件是否满足。

class Allocator {
    //静态内部类单例
    private Allocator() {}
    public static Allocator getInstance() {
        return AllocatorSingle.install;
    }
    private static class AllocatorSingle {
        private static Allocator install = new 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()是会随机的通知等待队列中的一个线程，而notify()会通知等待队列中的所有线程。即便通知所有线程，也只有一个线程能够进入临界区。但是仅通知一个线程，可能导致某些线程永远不会被通知到。

假设有资源A、B、C、D，线程1申请到了AB，线程2申请到了CD，此时线程3申请AB，会进入等待队列(AB分配给了线程1，线程3要求的条件不满足)，线程4申请CD也会进入等待队列。
之后线程1归还了资源AB，如果使用notify()来通知等待队列中的线程，有可能被通知的是线程4，但是线程4申请的是CD，所以此时线程4不满足条件还是会等待，而真正该唤醒的线程3就再也没有机会被唤醒了。

总结

等待-通知机制是一种非常普遍的线程间协作的方式。工作中使用轮询的方式来等待某个状态的很多情况，都可以使用等待-通知来优化。Java语言内置的synchronized配合wait()、notify()、notifyAll()这三个方法可以快速实现这种机制。

Java语言的这种实现，背后的理论模型是管程。