Jakob Jenkov 2014-06-23
如果一个线程因为其他线程总是抢占 CPU 时间而始终得不到执行机会，这种情况就称为“饥饿（Starvation）”。该线程被“饿死”，因为 CPU 时间总是被分配给其他线程。解决饥饿问题的方法被称为“公平性（Fairness）”——即所有线程都应被公平地给予执行机会。
Java 中导致线程饥饿的常见原因
以下三种常见情况可能导致 Java 中的线程发生饥饿：
- 高优先级线程吞噬了所有 CPU 时间，低优先级线程无法获得执行机会。
- 线程无限期地阻塞在等待进入
synchronized代码块的过程中，因为其他线程总是被优先允许进入。 - 调用了某个对象的
wait()方法的线程一直等待下去，因为每次调用notify()时总是唤醒其他线程，而不是它。
高优先级线程吞噬低优先级线程的 CPU 时间
你可以为每个线程单独设置优先级。优先级越高，获得的 CPU 时间通常也越多。线程优先级范围是 1 到 10。但具体如何解释这些优先级，取决于运行应用程序的操作系统。对于大多数应用程序来说，最好保持默认优先级不变。
线程无限期阻塞在 synchronized 代码块之外
Java 的 synchronized 代码块也可能导致线程饥饿。synchronized 并不保证等待进入同步块的线程的执行顺序。这意味着理论上存在一种风险：某个线程可能永远无法进入同步块，因为其他线程总是被优先授予访问权限。这种问题就叫做“饥饿”——线程因始终无法获得 CPU 时间而被“饿死”。
调用 wait() 的线程无限期等待
当多个线程对同一个对象调用了 wait()，而此时调用 notify() 时，并不保证会唤醒哪一个线程——可能是任意一个等待中的线程。因此，存在一种风险：某个特定线程可能永远无法被唤醒，因为每次 notify() 都选择了其他线程。
在 Java 中实现公平性
虽然在 Java 中无法实现 100% 的公平性，但我们仍可以设计自己的同步机制，以提高线程之间的公平性。
首先，我们来看一个简单的 synchronized 代码块：
public class Synchronizer {
public synchronized void doSynchronized() {
// 执行大量耗时操作
}
}
如果有多个线程调用 doSynchronized() 方法，其中一些线程将被阻塞，直到第一个获得访问权的线程退出该方法。如果有多个线程在等待，Java 并不保证下一个被允许进入的是哪一个线程。
使用 Lock 替代 synchronized 块
为了提高等待线程的公平性，我们首先将上述代码改为使用显式锁（Lock）而不是 synchronized 块：
public class Synchronizer {
Lock lock = new Lock();
public void doSynchronized() throws InterruptedException {
this.lock.lock();
// 临界区：执行大量耗时操作
this.lock.unlock();
}
}
注意，doSynchronized() 方法不再声明为 synchronized，而是通过 lock.lock() 和 lock.unlock() 来保护临界区。
一个简单的 Lock 实现可能如下所示：
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() 时，它们会被阻塞在 lock() 方法内部；如果锁已被占用，线程将在 while(isLocked) 循环中的 wait() 调用处阻塞。
需要注意的是，调用 wait() 会释放 Lock 实例上的同步锁，因此其他线程现在可以进入 lock() 方法。结果是，多个线程最终都会在 lock() 方法内部调用 wait()。
再回顾 doSynchronized() 方法中的注释：“临界区代码执行时间很长”。假设这段代码的执行时间远长于进入 lock() 方法和调用 wait() 所需的时间，那么线程等待获取锁的大部分时间实际上是在 wait() 中度过的，而不是在尝试进入 lock() 方法时被阻塞。
如前所述，synchronized 块在多个线程等待时并不保证谁先获得锁；同样，wait()/notify() 机制也不保证哪个线程会被唤醒。因此，当前这个 Lock 实现与 synchronized 版本在公平性上并无本质区别。
但我们可以通过修改来改善这一点。
当前版本中，所有线程都在同一个 Lock 对象上调用 wait()。如果我们让每个线程在各自独立的对象上调用 wait()，那么 Lock 就可以选择具体唤醒哪一个线程，从而实现更公平的调度。
公平锁（Fair Lock）
下面我们将前面的 Lock 类改造为一个名为 FairLock 的公平锁。你会注意到，相对于之前的 Lock，其同步和 wait()/notify() 的实现方式已有显著变化。
注：从原始
Lock到FairLock的设计过程涉及多个中间步骤，包括解决嵌套监视器锁死、条件错失 等问题。为保持本文简洁，这些中间步骤在此省略，但相关链接已提供供深入阅读。
关键点在于：每个调用 lock() 的线程都会被加入一个队列，只有队列中的第一个线程才被允许获取锁（前提是锁未被占用）。其他线程则等待，直到轮到自己位于队首。
public class FairLock {
private boolean isLocked = false;
private Thread lockingThread = null;
private List<QueueObject> waitingThreads = new ArrayList<>();
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块。- 每个调用
lock()的线程都会创建一个QueueObject实例并加入等待队列。 - 调用
unlock()的线程会唤醒队列中的第一个QueueObject，从而只唤醒一个等待线程，而不是全部。这正是实现公平性的关键。 - 锁的状态检查和修改仍在同一个
synchronized块中完成，以避免“条件错失”（slipped conditions）。 QueueObject本质上是一个信号量（semaphore），其doWait()和doNotify()方法将信号存储在对象内部，以防止因线程调度导致的“信号丢失”（missed signals）。queueObject.doWait()被放在synchronized(this)块之外调用，以避免“嵌套监视器锁死”（nested monitor lockout），确保其他线程能正常调用unlock()。doWait()被包裹在try-catch中，以便在线程被中断时能从队列中移除对应的QueueObject。
关于性能的说明
对比 Lock 和 FairLock 可以发现，FairLock 的 lock() 和 unlock() 方法中包含更多操作。这些额外代码会使 FairLock 的同步开销略高于普通 Lock。
这种性能影响的程度取决于临界区代码的执行时间：
- 如果临界区代码执行时间很长，那么同步器本身的开销就相对较小；
- 如果临界区非常短且频繁调用，则公平锁的额外开销可能变得显著。
因此，在实际应用中需要根据具体场景权衡公平性与性能。