Java并发编程（九）-- 进程饥饿和公平锁

上一章已经提到“如果一个进程被多次回滚，迟迟不能占用必需的系统资源，可能会导致进程饥饿”，本文我们详细的介绍一下“饥饿”和“公平”。

Java中导致饥饿的原因

在Java中，下面三个常见的原因会导致线程饥饿：

1. 高优先级线程吞噬所有的低优先级线程的CPU时间。
2. 线程被永久堵塞在一个等待进入同步块的状态，因为其他线程总是能在它之前持续地对该同步块进行访问。
3. 线程在等待一个本身(在其上调用wait())也处于永久等待完成的对象，因为其他线程总是被持续地获得唤醒。

高优先级线程吞噬所有的低优先级线程的CPU时间

你能为每个线程设置独自的线程优先级，优先级越高的线程获得的CPU时间越多，线程优先级值设置在1到10之间，而这些优先级值所表示行为的准确解释则依赖于你的应用运行平台。对大多数应用来说，你最好是不要改变其优先级值。

线程被永久堵塞在一个等待进入同步块的状态

Java的同步代码区也是一个导致饥饿的因素。Java的同步代码区对哪个线程允许进入的次序没有任何保障。这就意味着理论上存在一个试图进入该同步区的线程处于被永久堵塞的风险，因为其他线程总是能持续地先于它获得访问，这即是“饥饿”问题，而一个线程被“饥饿致死”正是因为它得不到CPU运行时间的机会。

线程在等待一个本身(在其上调用wait())也处于永久等待完成的对象

如果多个线程处在wait()方法执行上，而对其调用notify()不会保证哪一个线程会获得唤醒，任何线程都有可能处于继续等待的状态。因此存在这样一个风险：一个等待线程从来得不到唤醒，因为其他等待线程总是能被获得唤醒。

在Java中实现公平性

虽Java不可能实现100%的公平性，我们依然可以通过同步结构在线程间实现公平性的提高。

首先来学习一段简单的同步态代码：

public class Synchronizer{

    public synchronized void doSynchronized(){

      //Todo
         .....
    }
}

如果有一个以上的线程调用doSynchronized()方法，在第一个获得访问的线程未完成前，其他线程将一直处于阻塞状态，而且在这种多线程被阻塞的场景下，接下来将是哪个线程获得访问是没有保障的。

使用锁方式替代同步块

为了提高等待线程的公平性，我们使用锁方式来替代同步块。

public class Synchronizer{
    Lock lock = new Lock();
    public void doSynchronized() throws InterruptedException{
        this.lock.lock();
        //Todo
       ....
        this.lock.unlock();
    }
}

注意到doSynchronized()不再声明为synchronized，而是用lock.lock()和lock.unlock()来替代。

一个简单的锁类看起来像这样：

public class Lock{

    private boolean isLocked = false;
    private Thread lockingThread = null;

    public synchronized void lock() throws InterruptedException {
        while (isLocked) {
            wait();
        }
        isLocked = true;
        lockingThread = Thread.currentThread();
    }

    public synchronized void unlock() {
        if (this.lockingThread != Thread.currentThread()) {
            throw new IllegalMonitorStateException("Calling thread has not locked this lock");
        }
        isLocked = false;

        lockingThread = null;

        notify();
    }
}

如果注意到你上面的Synchronizer类和Lock的实现，你将注意到线程现在在尝试调用lock()方法时被阻塞，如果多个线程同时调用了wait()方法。第二，如果锁被锁定，这些线程将在lock()方法的while循环中的wait()方法的调用中。请记住，线程调用wait()会释放锁实例上的同步锁，因此等待进入lock()的线程现在可以这样做。结果是多个线程最终会在lock()中调用wait()。 
如果你回顾doSynchronized()方法，你将注意到在lock()和unlock()方法之间的注释，在这两个方法调用之间执行了很长时间。让我们进一步假设，与调用lock()和wait()方法相比，这两个方法之间的代码执行时间更长，因为锁已经被锁定。就是说，等待锁定锁和进入关键区域的大部分等待时间是耗费咋了wait()调用，而不是lock()方法，在试着进入lock()方法时没有被阻塞。 
如上所书，同步块无法保证在多个线程的情况下一个线程获取访问权。wait()方法无法保证当notify()方法被调用是线程被唤醒。因此，当前这个Lock类版本与doSynchronized()的同步版本相比，对线程公平也没有任何作用。但是我们可以改变这种情况。 
当前的Lock类调用了它自己的wait()方法。如果每个线程都调用独立的对象的wait()方法，就每个线程就只有一个线程调用wait()方法，那么Lock类就可以知道调用notify()方法是在哪个对象上了，从而可以快速精确地选择哪个线程可以被唤醒。

公平锁

下面来讲述将上面Lock类转变为公平锁FairLock。你会注意到新的实现和之前的Lock类中的同步和wait()/notify()稍有不同。

准确地说如何从之前的Lock类做到公平锁的设计是一个渐进设计的过程，每一步都是在解决上一步的问题而前进的：Nested Monitor Lockout, Slipped Conditions和Missed Signals。这些本身的讨论虽已超出本文的范围，但其中每一步的内容都将会专题进行讨论。重要的是，每一个调用lock()的线程都会进入一个队列，当解锁后，只有队列里的第一个线程被允许锁住Farlock实例，所有其它的线程都将处于等待状态，直到他们处于队列头部。

public class FairLock {
    private boolean isLocked = false;
    private Thread lockingThread = null;
    private List<QueueObject> waitingThreads = new ArrayList<QueueObject>();

    public void lock() throws InterruptedException {
        QueueObject queueObject = new QueueObject();
        boolean isLockedForThisThread = true;
        synchronized (this) {
            waitingThreads.add(queueObject);
        }
        while (isLockedForThisThread) {
            synchronized (this) {
                isLockedForThisThread = isLocked || waitingThreads.get(0) != queueObject;
                if (!isLockedForThisThread) {
                    isLocked = true;
                    waitingThreads.remove(queueObject);
                    lockingThread = Thread.currentThread();
                    return;
                }
            }
            try {
                queueObject.doWait();
            } catch (InterruptedException e) {
                synchronized (this) {
                    waitingThreads.remove(queueObject);
                }
                throw e;
            }
        }
    }

    public synchronized void unlock() {
        if (this.lockingThread != Thread.currentThread()) {
            throw new IllegalMonitorStateException("Calling thread has not locked this lock");
        }
        isLocked = false;
        lockingThread = null;
        if (waitingThreads.size() > 0) {
            waitingThreads.get(0).doNotify();
        }
    }
}

 

public class QueueObject {
    private boolean isNotified = false;

    public synchronized void doWait() throws InterruptedException {
        while (!isNotified) {
            this.wait();
        }
        this.isNotified = false;
    }

    public synchronized void doNotify() {
        this.isNotified = true;
        this.notify();
    }

    public boolean equals(Object o) {
        return this == o;
    }
}

首先注意到lock()方法不在声明为synchronized，取而代之的是对必需同步的代码，在synchronized中进行嵌套。

FairLock新创建了一个QueueObject的实例，并对每个调用lock()的线程进行入队列。调用unlock()的线程将从队列头部获取QueueObject，并对其调用doNotify()，以唤醒在该对象上等待的线程。通过这种方式，在同一时间仅有一个等待线程获得唤醒，而不是所有的等待线程。这也是实现FairLock公平性的核心所在。

请注意，在同一个同步块中，锁状态依然被检查和设置，以避免出现滑漏条件。

还需注意到，QueueObject实际是一个semaphore。doWait()和doNotify()方法在QueueObject中保存着信号。这样做以避免一个线程在调用queueObject.doWait()之前被另一个调用unlock()并随之调用queueObject.doNotify()的线程重入，从而导致信号丢失。queueObject.doWait()调用放置在synchronized(this)块之外，以避免被monitor嵌套锁死，所以另外的线程可以解锁，只要当没有线程在lock方法的synchronized(this)块中执行即可。

最后，注意到queueObject.doWait()在try – catch块中是怎样调用的。在InterruptedException抛出的情况下，线程得以离开lock()，并需让它从队列中移除。

性能考虑

如果比较Lock和FairLock类，你会注意到在FairLock类中lock()和unlock()还有更多需要深入的地方。这些额外的代码会导致FairLock的同步机制实现比Lock要稍微慢些。究竟存在多少影响，还依赖于应用在FairLock临界区执行的时长。执行时长越大，FairLock带来的负担影响就越小，当然这也和代码执行的频繁度相关。

补充几点

• 条件队列（信号处理）的使用范式

synchronized(lock){
    while ( !conditionPredicate() )
        lock.wait();
}

• 公平/非公平几点对比

  • 非公平
    • 默认
    • 吞吐量好
    • 各线程表现差异大
    • 闯入锁
      • 让闯入者获得锁继续运行，比唤醒等待线程，再让等待线程开始工作要快的多
  • 公平
    • 伸缩性好
    • 因挂起/重新开始线程的代价带了巨大的性能开销
      • 为了维护等待线程的公平调度

• 显式锁使用时的注意事项

  • Lock 的实现必须提供具有与内部加锁（monitor）相同的内存可见性的语义
  • 需要确保显式的释放锁
    • finally
  • Java 6 引入偏向锁，平均来说和内部锁的优势不再那么的大了，但在极端情况下仍然占有一定的优势
  • 在Java 5 中，线程转储无法体现
  • 难以被JIT优化
    • 锁省略
    • 粗化锁

参考资料：

　　https://juejin.im/post/5ae755736fb9a07acd4d829c

　　https://hk.saowen.com/a/aadedea0c56eced784e4dbb52f0a4bde6252185ae779b95c7d2fb52c6d1bc2d4