Liveness

A concurrent application's ability to execute in a timely manner is known as its liveness. This section describes the most common kind of liveness problem, deadlock, and goes on to briefly describe two other liveness problems, starvation and livelock.

一个并发应用程序在时间上的执行的能力被称为活动性。这一节主要描述了活动性的问题，死锁，并简要的介绍两个其他的活动性问题，饥饿和活锁。

Deadlock

Deadlock describes a situation where two or more threads are blocked forever, waiting for each other. Here's an example. 死锁是这样一种状态：2个活多个线程被永久性阻塞，互相等待。如下例： Alphonse and Gaston are friends, and great believers in courtesy. A strict rule of courtesy is that when you bow to a friend, you must remain bowed until your friend has a chance to return the bow. Unfortunately, this rule does not account for the possibility that two friends might bow to each other at the same time. This example application, Deadlock, models this possibility: Alphone（简称A）和Gaston（简称G）是朋友，而且都是虔诚的信徒。信徒的一个严格的规定是：当你向朋友鞠躬，你必须保持鞠躬状态直到你的朋友有机会像你鞠躬。然而，不幸的是，这个规则并没有考虑两个人同时向对方鞠躬的可能性。，下面的程序 Deadlock，描述了这总可能性。

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s"
                + "  has bowed to me!%n", 
                this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                + " has bowed back to me!%n",
                this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); }
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); }
        }).start();
    }
}

When Deadlock runs, it's extremely likely that both threads will block when they attempt to invoke bowBack. Neither block will ever end, because each thread is waiting for the other to exit bow. 当Deadlock程序运行时，两个线程极有可能在试图调用bowBack时发生阻塞。两个线程都不会结束，因为他们都在等待另一个Bow方法退出。

Starvation and Livelock 饥饿和活锁 Starvation and livelock are much less common a problem than deadlock, but are still problems that every designer of concurrent software is likely to encounter. 饥饿和活锁并没有死锁普遍，但是也是设计并发程序的程序员很有可能遇到的问题。

Starvation 饥饿

Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by "greedy" threads. For example, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.

饥饿描述了这样一种状态：线程无法通过一般途径获取共享资源从而无法继续运行。 当贪婪的线程长期霸占共享资源时，有些线程就会产生饥饿。例如，一个对象的同步方法需要运行很长时间。如果一个线程进场调用该对象的同步方法，其他线程在调用该对象的同步方法时就会产生阻塞。

Livelock 活锁 A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left. They're still blocking each other, so... 一个线程经常会对另外的线程做出回应。如果一个线程的动作同时也是另外一个线程的响应，就可能导致活锁。就像死锁一样，活锁也会让程序不再继续运行，然而他们并没有发生阻塞，他们只是忙于互相响应而不能继续运行。这就像两个人在走廊里互相传递东西一样：Alpthose 把他左手的东西传递给Gaston,而Gaston把他右手的东西又传递给Alpthose.实际上他们也是在互相阻塞对方，Alphone移到他的右边，而Gaston移到他的左边。他们依旧在互相阻塞，因此……。

Guarded Blocks 保护块 Threads often have to coordinate their actions. The most common coordination idiom is the guarded block. Such a block begins by polling a condition that must be true before the block can proceed. There are a number of steps to follow in order to do this correctly. 线程之间经常需要协同工作，最普遍的协同工作方法就是保护块。 Suppose, for example guardedJoy is a method that must not proceed until a shared variable joy has been set by another thread. Such a method could, in theory, simply loop until the condition is satisfied, but that loop is wasteful, since it executes continuously while waiting.

public void guardedJoy() { // Simple loop guard. Wastes // processor time. Don't do this! while(!joy) {} System.out.println("Joy has been achieved!"); }

A more efficient guard invokes Object.wait to suspend the current thread. The invocation of wait does not return until another thread has issued a notification that some special event may have occurred — though not necessarily the event this thread is waiting for:

public synchronized void guardedJoy() { // This guard only loops once for each special event, which may not // be the event we're waiting for. while(!joy) { try { wait(); } catch (InterruptedException e) {} } System.out.println("Joy and efficiency have been achieved!"); }

Note: Always invoke wait inside a loop that tests for the condition being waited for. Don't assume that the interrupt was for the particular condition you were waiting for, or that the condition is still true.

Like many methods that suspend execution, wait can throw InterruptedException. In this example, we can just ignore that exception — we only care about the value of joy.

Why is this version of guardedJoy synchronized? Suppose d is the object we're using to invoke wait. When a thread invokes d.wait, it must own the intrinsic lock for d — otherwise an error is thrown. Invoking wait inside a synchronized method is a simple way to acquire the intrinsic lock.

When wait is invoked, the thread releases the lock and suspends execution. At some future time, another thread will acquire the same lock and invoke Object.notifyAll, informing all threads waiting on that lock that something important has happened:

public synchronized notifyJoy() { joy = true; notifyAll(); }

Some time after the second thread has released the lock, the first thread reacquires the lock and resumes by returning from the invocation of wait. Note: There is a second notification method, notify, which wakes up a single thread. Because notify doesn't allow you to specify the thread that is woken up, it is useful only in massively parallel applications — that is, programs with a large number of threads, all doing similar chores. In such an application, you don't care which thread gets woken up.

Let's use guarded blocks to create a Producer-Consumer application. This kind of application shares data between two threads: the producer, that creates the data, and the consumer, that does something with it. The two threads communicate using a shared object. Coordination is essential: the consumer thread must not attempt to retrieve the data before the producer thread has delivered it, and the producer thread must not attempt to deliver new data if the consumer hasn't retrieved the old data.

In this example, the data is a series of text messages, which are shared through an object of type Drop:

public class Drop { // Message sent from producer // to consumer. private String message; // True if consumer should wait // for producer to send message, // false if producer should wait for // consumer to retrieve message. private boolean empty = true;

public synchronized String take() {
    // Wait until message is
    // available.
    while (empty) {
        try {
            wait();
        } catch (InterruptedException e) {}
    }
    // Toggle status.
    empty = true;
    // Notify producer that
    // status has changed.
    notifyAll();
    return message;
}

public synchronized void put(String message) {
    // Wait until message has
    // been retrieved.
    while (!empty) {
        try { 
            wait();
        } catch (InterruptedException e) {}
    }
    // Toggle status.
    empty = false;
    // Store message.
    this.message = message;
    // Notify consumer that status
    // has changed.
    notifyAll();
}

}

The producer thread, defined in Producer, sends a series of familiar messages. The string "DONE" indicates that all messages have been sent. To simulate the unpredictable nature of real-world applications, the producer thread pauses for random intervals between messages.

import java.util.Random;

public class Producer implements Runnable { private Drop drop;

public Producer(Drop drop) {
    this.drop = drop;
}

public void run() {
    String importantInfo[] = {
        "Mares eat oats",
        "Does eat oats",
        "Little lambs eat ivy",
        "A kid will eat ivy too"
    };
    Random random = new Random();

    for (int i = 0;
         i < importantInfo.length;
         i++) {
        drop.put(importantInfo[i]);
        try {
            Thread.sleep(random.nextInt(5000));
        } catch (InterruptedException e) {}
    }
    drop.put("DONE");
}

}

The consumer thread, defined in Consumer, simply retrieves the messages and prints them out, until it retrieves the "DONE" string. This thread also pauses for random intervals.

import java.util.Random;

public class Consumer implements Runnable { private Drop drop;

public Consumer(Drop drop) {
    this.drop = drop;
}

public void run() {
    Random random = new Random();
    for (String message = drop.take();
         ! message.equals("DONE");
         message = drop.take()) {
        System.out.format("MESSAGE RECEIVED: %s%n", message);
        try {
            Thread.sleep(random.nextInt(5000));
        } catch (InterruptedException e) {}
    }
}

}

Finally, here is the main thread, defined in ProducerConsumerExample, that launches the producer and consumer threads.

public class ProducerConsumerExample { public static void main(String[] args) { Drop drop = new Drop(); (new Thread(new Producer(drop))).start(); (new Thread(new Consumer(drop))).start(); } }

Note: The Drop class was written in order to demonstrate guarded blocks. To avoid re-inventing the wheel, examine the existing data structures in the Java Collections Framework before trying to code your own data-sharing objects. For more information, refer to the Questions and Exercises section.