偶然学习到多线程，看到多线程的饥饿和公平，觉得可以写点什么。
什么是饥饿什么是公平呢？如果一个线程因为CPU运行时间全部被其他线程抢走而得不到CPU运行时间，这种状态被称之为“饥饿”。而该线程被“饥饿致死”正是因为它得不到CPU运行时间的机会。解决饥饿的方案被称之为“公平性”，即所有线程均能公平地获得运行机会。
首先我们要知道，什么原因导致了“饥饿”？在Java方面我觉的分为了三种情况:
①.线程中高优先级的吞噬所有的低优先级的CPU时间。
你能为每个线程设置独自的线程优先级，优先级越高的线程获得的CPU时间越多，线程优先级值设置在1到10之间，而这些优先级值所表示行为的准确解释则依赖于你的应用运行平台。所以对大多数应用来说，你最好是不要改变其优先级值。
②线程被永久堵塞在一个等待进入同步块的状态
Java的同步代码区也是一个导致饥饿的因素。Java的同步代码区对哪个线程允许进入的次序没有任何保障。这就意味着理论上存在一个试图进入该同步区的线程处于被永久堵塞的风险，因为其他线程总是能持续地先于它获得访问，这即是“饥饿”问题，而一个线程被“饥饿致死”正是因为它得不到CPU运行时间的机会。
③.线程被永久堵塞在一个等待进入同步块的状态
如果多个线程处在wait()方法执行上，而对其调用notify()不会保证哪一个线程会获得唤醒，任何线程都有可能处于继续等待的状态。因此存在这样一个风险：一个等待线程从来得不到唤醒，因为其他等待线程总是能被获得唤醒。
如何在Java中实现公平？
无论哪里都不可能实现100%公平，所以我们只能提出比较好的方案来达到目的，首先可以通过同步结构来实现公平性的提高。
先来一段简单的代码：1
2
3
4
5public class Synchronizer{
public synchronized void doSynchronized(){
//需要运行很长时间的某些代码
}
}
如果有多个线程调用了doSynchronized()方法，在第一个获得访问的线程未完成前，其他线程将一直处于阻塞状态，而且在这种多线程被阻塞的场景下，接下来将是哪个线程获得访问是没有保障的。
现在我们使用锁方式替代同步块来试试:1
2
3
4
5
6
7
8public class Synchronizer{
Lock lock = new Lock();
public void doSynchronized() throws InterruptedException{
this.lock.lock(); //当前线程锁住lock对象
//时间临界区
this.lock.unlock(); //当前线程释放lock对象上的锁
}
}
我们可以注意到doSynchronized()不再声明为synchronized，而是用lock.lock()和lock.unlock()来替代。
下面是用Lock类做的一个实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public class Lock{
private boolean isLocked = false; //是否加过锁的信号
private Thread lockingThread = null; //进行加锁的线程
public synchronized void lock() throws InterruptedException{
while(isLocked){ //如果lock对象已被其他线程加锁了（线程已经退出了本lock()方法）
wait(); //当前线程阻塞，它释放锁对象上的锁，其他线程可以再进入本lock()
}
isLocked = true; //如果没加锁，则当前线程对锁对象加锁
lockingThread = Thread.currentThread();
}
public synchronized void unlock(){
if(this.lockingThread != Thread.currentThread()){ //如果调用lock()加锁的不是当前线程
throw new IllegalMonitorStateException(
"所调用线程尚未锁定");
}
isLocked = false; //释放锁，标记为未加锁
lockingThread = null;
notify(); //通知阻塞在锁对象上的线程队列，唤醒其中某一个线程
}
}
注意到上面对Lock的实现，如果存在多线程并发访问lock()，这些线程将阻塞在对lock()方法的访问上。另外，如果isLocked=true时，表示锁已被锁上，这些线程将阻塞在while(isLocked)循环的wait()调用里面。要注意的是，当线程正在等待进入lock() 时，可以调用wait()释放其锁实例对应的同步锁，使得其他多个线程可以进入lock()方法，并调用wait()方法。
我们回头看doSynchronized()方法，可以看到在lock()和unlock()之间：一段代码将长时间运行，和进入lock()并调用wait()来比较的话。这意味着大部分时间用在等待进入锁和进入临界区的过程是用在wait()的等待中，而不是被阻塞在试图进入lock()方法中。
由于同步块不会对等待进入的多个线程谁能获得访问做任何保障，同样当调用notify()时，wait()也不会做保障一定能唤醒线程。因此这个版本的Lock类和doSynchronized()那个版本就保障公平性而言，没有任何区别。
但我们能改变这种情况。当前的Lock类版本调用自己的wait()方法，如果每个线程在不同的对象上调用wait()，那么只有一个线程会在该对象上调用wait()，Lock类可以决定哪个对象能对其调用notify()，因此能做到有效的选择唤醒哪个线程。
下面看看如何把Lock类转变为公平锁FairLock。
新的实现和之前的Lock类中的同步和wait()/notify()将会稍有不同。
每一个调用lock()的线程都会进入一个队列，当解锁后，只有队列里的第一个线程被允许锁住FairLock实例，所有其它的线程都将处于等待状态，直到他们处于队列头部。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
43public 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{ //放在同步块之外，避免monitor嵌套锁死
queueObject.doWait(); //监视器对象（持有信号量isNotified）等待
}catch(InterruptedException e){
synchronized(this) { waitingThreads.remove(queueObject); }
throw e;
}
}
}
public synchronized void unlock(){
if(this.lockingThread != Thread.currentThread()){ //加锁的不是当前线程
throw new IllegalMonitorStateException( "该线程尚未锁");
}
isLocked = false; //解锁
lockingThread = null;
if(waitingThreads.size() > 0){ //唤醒第一个线程
waitingThreads.get(0).doNotify();
}
}
}
1 | public class QueueObject { |
首先注意到lock()方法不再声明为synchronized，取而代之的是对必需同步的代码，在synchronized中进行嵌套。
FairLock新创建了一个QueueObject的实例，并对每个调用lock()的线程都将其QueueObject实例推入队列。调用unlock()的线程将从队列头部获取QueueObject，并对其调用doNotify()，以唤醒在该对象上等待的线程。通过这种方式，在同一时间仅有一个等待线程获得唤醒，而不是所有的等待线程。这也是实现FairLock公平性的核心所在。
请注意，在同一个同步块中，锁状态依然被检查和设置，以避免出现滑漏条件。
还需注意到，QueueObject实际是一个semaphore。doWait()和doNotify()方法在QueueObject中保存着信号。这样做以避免一个线程在调用queueObject.doWait()之前被另一个调用unlock()并随之调用queueObject.doNotify()的线程重入，从而导致信号丢失。queueObject.doWait()调用放置在synchronized(this)块之外，以避免被monitor嵌套锁死，所以另外的线程可以进入unlock()来解锁，只要当没有线程在lock方法的synchronized(this)块中执行即可。
最后，注意到queueObject.doWait()在try – catch块中是怎样调用的。在InterruptedException抛出的情况下，线程得以离开lock()，并需让它从队列中移除。
性能考虑
如果比较Lock和FairLock类，你会注意到在FairLock类中lock()和unlock()还有更多需要深入的地方。这些额外的代码会导致FairLock的同步机制实现比Lock要稍微慢些。究竟存在多少影响，还依赖于应用在FairLock临界区执行的时长。执行时长越大，FairLock带来的负担影响就越小，当然这也和代码执行的频繁度相关。
