论多线程中的活性风险(liveness hazard)—死锁,活锁,饥饿

 在java多线程编程中，一不小心就会引起活性危险(liveness hazard)，需要非常谨慎。
liveness可以翻译成活性，如果线程的活性好，说明运行状态不错，能得到CPU的有效处理；反之则线程可能处于死锁、饥饿、活锁等危险状态。
-----------------------------------------------------------------------------------------------------------------------------------------
什么是死锁，举个简单的例子：两只山羊过独木桥，它们同时走到桥中间，结果都堵在中间动弹不得。在这个例子中，可以把一只山羊在桥上走过的路比喻成资源，两只山羊同时在请求对方占有的资源。在java中，这种资源可以理解为对象的监视锁。

以下四个条件若同时满足，则可能会引起死锁：
相互排斥（Mutual exclusion）：资源不能被共享，只能由一个线程使用。
请求与保持（Hold and wait）：已经得到资源的线程可以再次申请新的资源。例如，线程A和B都需要访问一个文件，同时需要用到打印机，线程A得到了文件资源，线程B得到了打印机资源，但两个进程都不能获得全部的资源。
不可剥夺（No pre-emption）：已经分配的资源不能从相应的线程中被强制地剥夺，即使该线程处于阻塞状态。
循环等待（Circular wait）：系统中若干进程组成环路，该环路中每个线程都在等待相邻进程正占用的资源。例如，线程A在等待线程B，线程B在等待线程C，而线程C又在等待线程A。

死锁的解决办法有：加锁顺序、加锁时限、死锁检测，具体可参考：
http://ifeve.com/deadlock-prevention/
-----------------------------------------------------------------------------------------------------------------------------------------
什么是活锁，处于活锁状态中的线程对任务的处理丝毫取不到任何进展，其实活锁只是一种形象的比喻，和锁没有太大的关系。举个简单的例子：JMS中的死信问题，即消息监听器监听到消息后进行处理，但由于程序的bug，异常导致事务回滚，消息又回到了消息队列中，消息监听器再次监听到此消息后，又接着处理，又失败回滚，如此循环下去，此消息始终无法得到正确处理。
以下java代码也会引起活锁：
在a线程里：b.join(); 然后在b线程里：a.join()。两个线程都处于等待状态，如下图所示：

 

 
活锁的解决办法有：设置最大重试次数，超过该阈值后，监听自动停止；消息监听器监听到消息后，若不成功，则存表，不作回滚处理，事后再进行定时异步补偿处理；编程时避免两个线程互相join的情况，实际很少会出现这种情况。
-----------------------------------------------------------------------------------------------------------------------------------------

什么是饥饿，也举个简单的例子：从前有个贪婪自私的人进入镇上唯一的一家饭馆后，把门锁上，在里面吃饱了就睡，也不解锁开门，就是不让外面其他的顾客进门，外面的顾客只能活活挨饿。在这个例子中，可以把米饭比喻成CPU资源。
以下java代码会引起这种类型的饥饿：
synchronized(obj) {
while (true) {
  // .... infinite loop
}
}

关于饥饿，再举一个例子：从前有个被勾结的高官，总是把粮食优先分配给谄媚者，其他百姓很少有机会被分配到，总是处于挨饿的状态。
在java中，会引起这种类型的饥饿是给线程设置了优先级，优先级低的线程始终得不到执行的机会，虽然java线程的优先级对于不同操作系统的实现方式不一样，即便设置了优先级也不一定会有效果，但还是有可能会出现这种情况。

饥饿的解决办法有：在synchronized方法或者块中避免无限循环、采用线程默认的优先级。
-----------------------------------------------------------------------------------------------------------------------------------------
总结：
死锁是两个线程同时在请求对方占有的资源；
活锁是线程对任务的处理没有取得任何进展；
饥饿是一个线程在无限地等待其他线程占有的但是不会往外释放的资源。

可参考《Java Concurrency in Practice》PartIII -> Chapter10 -> Avoiding Liveness Hazards

Starvation
Starvation occurs when a thread is perpetually denied access to resources it needs in order to make progress; the most commonly starved resource is CPU cycles. Starvation in Java applications can be caused by inappropriate use of thread priorities. It can also be caused by executing nonterminating constructs (infinite loops or resource waits that do not terminate) with a lock held, since other threads that need that lock will never be able to acquire it.

The thread priorities defined in the Thread API are merely scheduling hints. The Thread API defines ten priority levels that the JVM can map to operating system scheduling priorities as it sees fit. This mapping is platform-specific, so two Java priorities can map to the same OS priority on one system and different OS priorities on another. Some operating systems have fewer than ten priority levels, in which case multiple Java priorities map to the same OS priority.

Avoid the temptation to use thread priorities, since they increase platform dependence and can cause liveness problems. Most concurrent applications can use the default priority for all threads.

Livelock
Livelock is a form of liveness failure in which a thread, while not blocked, still cannot make progress because it keeps retrying an operation that will always fail. Livelock often occurs in transactional messaging applications, where the messaging infrastructure rolls back a transaction if a message cannot be processed successfully, and puts it back at the head of the queue. If a bug in the message handler for a particular type of message causes it to fail, every time the message is dequeued and passed to the buggy handler, the transaction is rolled back. Since the message is now back at the head of the queue, the handler is called over and over with the same result. (This is sometimes called the poison message problem.) The message handling thread is not blocked, but it will never make progress either. This form of livelock often comes from overeager error-recovery code that mistakenly treats an unrecoverable error as a recoverable one.
Livelock can also occur when multiple cooperating threads change their state in response to the others in such a way that no thread can ever make progress. This is similar to what happens when two overly polite people are walking in opposite directions in a hallway: each steps out of the other's way, and now they are again in each other's way. So they both step aside again, and again, and again. . .
The solution for this variety of livelock is to introduce some randomness into the retry mechanism. For example, when two stations in an ethernet network try to send a packet on the shared carrier at the same time, the packets collide. The stations detect the collision, and each tries to send their packet again later. If they each retry exactly one second later, they collide over and over, and neither packet ever goes out, even if there is plenty of available bandwidth. To avoid this, we make each wait an amount of time that includes a random component. (The ethernet protocol also includes exponential backoff after repeated collisions, reducing both congestion and the risk of repeated failure with multiple colliding stations.) Retrying with random waits and backoffs can be equally effective for avoiding livelock in concurrent applications.