操作系统的引入

之所以在计算机中加入操作系统来实现多个程序的同时执行，主要是基于以下原因：

• 资源利用率
  • 在某些情况下，程序必须等待某个外部操作执行完成，例如输入操作或输出操作等，而在等待时程序无法执行其他任何工作。因此，如果在等待的同时可以运行另一个程序，那么无疑将提高资源的利用率。
• 公平性
  • 不同的用户和程序对于计算机上的资源有着同等的使用权。一种高效的运行方式是通过粗粒度的时间分片（Time Slicing）使这些用户和程序能共享计算机资源，而不是由一个程序从头运行到尾，然后再启动下一个程序。
• 便利性
  • 通常来说，在计算多个任务时，应该编写多个程序，每个程序执行一个任务并在必要时相互通信，这比只编写一个程序来计算所有任务更容易实现。

线程

• 进程：
  • 正在运行的程序，是系统进行资源分配和调用的独立（基本）单位。
  • 每一个进程都有它自己的内存空间和系统资源。
• 线程：
  • 是进程中的单个顺序控制流，是一条执行路径，程序使用CPU的基本单位
  • 一个进程如果只有一条执行路径，则称为单线程程序。
  • 一个进程如果有多条执行路径，则称为多线程程序。

对于单核计算机来讲，游戏进程和音乐进程是同时运行吗

不是。

因为CPU在某个时间点上只能做一件事情，计算机是在游戏进程和音乐进程间做着频繁切换，且切换速度很快，所以，我们感觉游戏和音乐在同时进行，其实并不是同时执行的。
多进程的作用不是提高执行速度，而是提高CPU的使用率。

多进程有什么意义

能在同一个时间段内执行多个任务。提高CPU的使用率。

多线程有什么意义

多线程的作用不是提高执行速度，而是为了提高应用程序的使用率。(程序抢占CPU时间片几率更大)
而多线程却给了我们一个错觉：让我们认为多个线程是并发执行的。其实不是。
因为多个线程共享同一个进程的资源(堆内存和方法区)，但是栈内存是独立的，一个线程一个栈。所以他们仍然是在抢CPU的资源执行。一个时间点上只有能有一个线程执行。而且谁抢到，这个不一定，所以，造成了线程运行的随机性。

什么是并发

大家注意两个词汇的区别：并行和并发。

前者是逻辑上同时发生，指在某一个时间内同时运行多个程序。
后者是物理上同时发生，指在某一个时间点同时运行多个程序。
那么，我们能不能实现真正意义上的并发呢，是可以的，多个CPU就可以实现，不过你得知道如何调度和控制它们。

JVM虚拟机的启动是单线程的还是多线程的？

JVM启动至少启动了垃圾回收线程和主线程，所以是多线程的。

多线程的实现方案

继承Thread类

步骤

1. 自定义类MyThread继承Thread类。
2. MyThread类里面重写run()
3. 创建对象
4. 启动线程

public class MyThread extends Thread {
	@Override
	public void run() {
		System.out.println("thread running");
	}
}

线程能不能多次启动

// MyThread my = new MyThread();
// my.start();
// // IllegalThreadStateException:非法的线程状态异常
// // 为什么呢?因为这个相当于是my线程被调用了两次。而不是两个线程启动。
// my.start();

// 创建两个线程对象
MyThread my1 = new MyThread();
MyThread my2 = new MyThread();

my1.start();
my2.start();

实现Runnable接口

步骤

1. 自定义类MyRunnable实现Runnable接口
2. 重写run()方法
3. 创建MyRunnable类的对象
4. 创建Thread类的对象，并把C步骤的对象作为构造参数传递

public class MyRunnable implements Runnable {

	@Override
	public void run() {
		for (int x = 0; x < 100; x++) {
			// 由于实现接口的方式就不能直接使用Thread类的方法了,但是可以间接的使用
			System.out.println(Thread.currentThread().getName() + ":" + x);
		}
	}

}


MyRunnable my = new MyRunnable();

// 创建Thread类的对象，并把C步骤的对象作为构造参数传递
// Thread(Runnable target)
// Thread t1 = new Thread(my);
// Thread t2 = new Thread(my);
// t1.setName("林青霞");
// t2.setName("刘意");

// Thread(Runnable target, String name)
Thread t1 = new Thread(my, "林青霞");
Thread t2 = new Thread(my, "刘意");

t1.start();
t2.start()

如何获取和设置线程名称

通过Thread.currentThread()获取当前线程后获取或设置线程名

实现接口方式的好处

• 可以避免由于Java单继承带来的局限性。
• 适合多个相同程序的代码去处理同一个资源的情况，把线程同程序的代码，数据有效分离，较好的体现了面向对象的设计思想。

多线程两种方式比较及区别

查看Thread类的run()方法的源代码，可以看到其实这两种方式都是在调用Thread对象的run方法，如果Thread类的run方法没有被覆盖，并且为该Thread对象设置了一个Runnable对象，该run方法会调用Runnable对象的run方法。

// Thread.java
private Runnable target;
public void run() {
	if (target != null) {
	    target.run();
	}
}

如果在Thread子类覆盖的run方法中编写了运行代码，也为Thread子类对象传递了一个Runnable对象，那么，线程运行时的执行代码是子类的run方法的代码？还是Runnable对象的run方法的代码？

子类的

实现Callable接口或者Runable接口（和线程池结合）

• 好处：
  • 可以有返回值
  • 可以抛出异常

线程调度

• 分时调度模型
  • 所有线程轮流使用 CPU 的使用权，平均分配每个线程占用 CPU 的时间片
• 抢占式调度模型
  • 优先让优先级高的线程使用 CPU，如果线程的优先级相同，那么会随机选择一个，优先级高的线程获取的 CPU 时间片相对多一些。

Java使用的是抢占式调度模型。

// 设置getPriority()和获取setPriority()线程优先级 默认是5 范围是1-10
// 线程优先级高仅仅表示线程获取的 CPU时间片的几率高
// 但是要在次数比较多，或者多次运行的时候才能看到比较好的效果。
Thread thread = Thread.currentThread();
System.out.println(thread.getPriority());// 5

线程操作

• 线程休眠
  • public static void sleep(long millis)
• 线程加入(等待某线程执行结束后才继续执行)
  • public final void join()

ThreadJoin tj1 = new ThreadJoin();
ThreadJoin tj2 = new ThreadJoin();
ThreadJoin tj3 = new ThreadJoin();

tj1.setName("李渊");
tj2.setName("李世民");
tj3.setName("李元霸");

tj1.start();
try {
	tj1.join();//tj1执行结束后继续执行下面的start()语句
} catch (InterruptedException e) {
	e.printStackTrace();
}

tj2.start();
tj3.start();

• 线程礼让(暂停当前正在执行的线程对象，并执行其他线程，让多个线程的执行更和谐，但是不能靠它保证一人一次。)
  • public static void yield()
• 后台线程(守护线程，主进程结束后守护进程也结束)
  • public final void setDaemon(boolean on)
• 中断线程
  • public final void stop() 强制中断
  • public void interrupt() 中断线程。 把线程的状态终止，并抛出一个InterruptedException。
• 获取线程名

Thread myThread = Thread.currentThread();
String name = myThread.getName();//通过setName()方法设置线程名
System.out.println(name);//main

sleep()和wait()的区别

• sleep() 必须指时间;不释放锁。
• wait() 可以不指定时间，也可以指定时间;释放锁。

线程生命周期

新建 – 就绪 – 运行 – 死亡
新建 – 就绪 – 运行 – 阻塞 – 就绪 – 运行 – 死亡

线程安全性

安全性

当多个线程访问某个类时，这个类始终都能表现出正确的行为，那么就称这个类是线程安全的。

当多个线程访问某个类时，不管运行时环境采用何种调度方式或者这些线程将如何交替执行，并且在主调代码中不需要任何额外的同步或协同，这个类都能表现出正确的行为，那么就称这个类是线程安全的。

• 在线程安全类中封装了必要的同步机制，因此客户端无须进一步采取同步措施。
• 无状态对象一定是线程安全的。

原子性

竞态条件

在并发编程中，由于不恰当的执行时序而出现不正确的结果是一种非常重要的情况，它有一个正式的名字：竞态条件（Race Condition）。

最常见的竞态条件类型就是“先检查后执行（Check-Then-Act）”操作，即通过一个可能失效的观测结果来决定下一步的动作。

“先检查后执行”：首先观察到某个条件为真（例如文件X不存在），然后根据这个观察结果采用相应的动作（创建文件X），但事实上，在你观察到这个结果以及开始创建文件之间，观察结果可能变得无效（另一个线程在这期间创建了文件X），从而导致各种问题（未预期的异常、数据被覆盖、文件被破坏等）。

使用“先检查后执行”的一种常见情况就是延迟初始化。

复合操作

复合操作：包含了一组必须以原子方式执行的操作以确保线程安全性。

在实际情况中，应尽可能地使用现有的线程安全对象（例如AcomicLong）来管理类的状态。 与非线程安全的对象相比，判断线程安全对象的可能状态及其状态转换情况要更为容易，从而也更容易维护和验证线程安全性。

或者使用下面的加锁机制

加锁机制

要保持状态的一致性，就需要在单个原子操作中更新所有相关的状态变量。

内置锁

Java提供了一种内置的锁机制来支持原子性：同步代码块（Synchronized Block）。

每个Java对象都可以用做一个实现同步的锁，这些锁被称为内置锁（Intrinsic Lock）或监视器锁（Monitor Lock）。
线程在进入同步代码块之前会自动获得锁，并且在退出同步代码块时自动释放锁，而无论是通过正常的控制路径退出，还是通过从代码块中抛出异常退出。
获得内置锁的唯一途径就是进入由这个锁保护的同步代码块或方法。

重入

当某个线程请求一个由其他线程持有的锁时，发出请求的线程就会阻塞。然而，由于内置锁是可重入的，因此如果某个线程试图获得一个已经由它自己持有的锁，那么这个请求就会成功。

“重入”意味着获取锁的操作的粒度是“线程”，而不是“调用”

重入的一种实现方法是，为每个锁关联一个获取计数值和一个所有者线程。当计数值为0时，这个锁就被认为是没有被任何线程持有。当线程请求一个未被持有的锁时，JVM将记下锁的持有者，并且将获取计数值置为1。如果同一个线程再次获取这个锁，计数值将递增，而当线程退出同步代码块时，计数器会相应地递减。当计数值为0时，这个锁将被释放。

用锁来保护状态

对于可能被多个线程同时访问的可变状态变量，在访问它时都需要持有同一个锁，在这种情况下，我们称状态变量是由这个锁保护的。

• 每个共享的和可变的变量都应该只由一个锁来保护，从而使维护人员知道是哪一个锁。
• 对于每个包含多个变量的不变性条件，其中涉及的所有变量都需要由同一个锁来保护。

一种常见的加锁约定是，将所有的可变状态都封装在对象内部，并通过对象的内置锁对所有访问可变状态的代码路径进行同步，使得在该对象上不会发生并发访问。

活跃性与性能

• 我们使用加锁机制来确保线程安全，但如果过度地使用加锁，则可能导致锁顺序死锁。
• 同样，我们使用线程池和信号量来限制对资源的使用，但这些被限制的行为可能会导致资源的死锁。

在安全性和活跃性之间通常存在着某种制衡。

• 当实现某个同步策略时，一定不要盲目地为了性能而牺牲简单性（这可能会破坏安全性）。
• 当执行时间较长的计算或者可能无法快速完成的操作时（例如，网络I/O或控制台I/O），一定不要持有锁。

死锁

多个线程由于存在环路的锁依赖关系而永远等待下去。

在数据库系统的设中考虑了检测死锁以及从死锁中恢复。检测到死锁时，将选择一个牺牲者并放弃这个任务

锁顺序死锁

两个线程试图以不同的顺序来获得相同的锁。

如果所有线程以固定的顺序来获得锁，那么在程序中就不会出现锁顺序死锁问题。

动态的锁顺序死锁

所有的线程似乎都是按照相同的顺序来获得锁，但事实上锁的顺序取决于传递给transferMoney的参数顺序，而这些参数顺序又取决于外部输入。

如何检查这种死锁——查看是否存在嵌套的锁获取操作。由于我们无法控制参数的顺序，因此要解决这个问题，必须定义锁的顺序，并在整个应用程序中按照这个顺序来获取锁。

在极少数情况下，两个对象可能拥有相同的散列值，此时必须通过某种任意的方法来决定锁的顺序，而这可能又会引入死锁。为了避免这种情况，可以使用“加时赛”锁。

如果在Account中包含一个唯一的，不可变的并且具备可比性的键值，例如账号，那么要制定锁的顺序就更加容易了，通过键值对对象进行排序，因而不需要使用“加时赛”锁。

public class InduceLockOrder {
    private static final Object tieLock = new Object();
    public void transferMoney(final Account fromAcct,
                              final Account toAcct,
                              final DollarAmount amount)
            throws InsufficientFundsException {
        class Helper {
            public void transfer() throws InsufficientFundsException {
                if (fromAcct.getBalance().compareTo(amount) < 0) {
                    throw new InsufficientFundsException();
                } else {
                    fromAcct.debit(amount);
                    toAcct.credit(amount);
                }
            }
        }
        int fromHash = System.identityHashCode(fromAcct);
        int toHash = System.identityHashCode(toAcct);
        if (fromHash < toHash) {
            synchronized (fromAcct) {
                synchronized (toAcct) {
                    new Helper().transfer();
                }
            }
        } else if (fromHash > toHash) {
            synchronized (toAcct) {
                synchronized (fromAcct) {
                    new Helper().transfer();
                }
            }
        } else {
            synchronized (tieLock) {
                synchronized (fromAcct) {
                    synchronized (toAcct) {
                        new Helper().transfer();
                    }
                }
            }
        }
    }
    interface DollarAmount extends Comparable<DollarAmount> {}
    interface Account {
        void debit(DollarAmount d);
        void credit(DollarAmount d);
        DollarAmount getBalance();
        int getAcctNo();
    }
    class InsufficientFundsException extends Exception {}
}

在协作对象之间发生的死锁

如果在持有锁的情况下调用某个外部方法，那么就需要警惕死锁。

如果在持有锁时调用某个外部方法，那么将出现活跃性问题。 在这个外部方法中可能会获取其他锁（这可能会产生死锁），或者阻塞时间过长，导致其他线程无法及时获得当前被持有的锁。

因为setLocation和notifyAvailable都是同步方法，因此调用setLocation的线程将首先获取Taxi的锁，然后获取Dispatcher的锁。 同样，调用getImage的线程将首先获取Dispatcher的锁，然后再获取每一个Taxi的锁（每次获取一个）。 这与LeftRightDeadlock中的情况相同，两个线程按照不同的顺序来获取两个锁，因此就可能产生死锁。

public class CooperatingDeadlock {
    // Warning: deadlock-prone!
    class Taxi {
        private final Dispatcher dispatcher;
        @GuardedBy("this")
        private Point location, destination;
        public Taxi(Dispatcher dispatcher) {
            this.dispatcher = dispatcher;
        }
        public synchronized Point getLocation() {
            return location;
        }
        public synchronized void setLocation(Point location) {
            this.location = location;
            if (location.equals(destination)) {
                dispatcher.notifyAvailable(this);
            }
        }
        public synchronized Point getDestination() {
            return destination;
        }
        public synchronized void setDestination(Point destination) {
            this.destination = destination;
        }
    }
    class Dispatcher {
        @GuardedBy("this")
        private final Set<Taxi> taxis;
        @GuardedBy("this")
        private final Set<Taxi> availableTaxis;
        public Dispatcher() {
            taxis = new HashSet<Taxi>();
            availableTaxis = new HashSet<Taxi>();
        }
        public synchronized void notifyAvailable(Taxi taxi) {
            availableTaxis.add(taxi);
        }
        public synchronized Image getImage() {
            Image image = new Image();
            for (Taxi t : taxis) {
                image.drawMarker(t.getLocation());
            }
            return image;
        }
    }
    class Image {
        public void drawMarker(Point p) {
        }
    }
}

开放调用

如果在调用某个方法时不需要持有锁，那么这种调用被称为开放调用（Open Call）。

依赖于开放调用的类通常能表现出更好的行为，并且在与那些在调用方法时需要持有锁的类相比，也更易于编写。通过尽可能地使用开放调用，将更易于找出那些需要获取多个锁的代码路径，因此也就更容易确保采用一致的顺序来获得锁。

这种通过开放调用来避免死锁的方法，类似于采用封装机制来提供线程安全的方法：

虽然在没有封装的情况下也能确保构建线程安全的程序，但对一个使用了封装的程序进行线程安全分析，要比分析没有使用封装的程序容易地多。
同理，分析一个完全依赖于开发调用的活跃性，要比分析那些不依赖开放调用的程序的活跃性简单。通过尽可能地使用开放调用，将更需要于找出那些需要获得多个锁的代码路径，因此也就更容易确保采用一致的顺序来获得锁。

在程序中应尽量使用开放调用。与那些在持有锁时调用外部方法的程序相比，更易于对依赖于开放调用的程序进行死锁分析。

// 开放调用需要使代码块仅被用于保护那些涉及共享状态的操作
class CooperatingNoDeadlock {
    @ThreadSafe
    class Taxi {
        private final Dispatcher dispatcher;
        @GuardedBy("this")
        private Point location, destination;
        public Taxi(Dispatcher dispatcher) {
            this.dispatcher = dispatcher;
        }
        public synchronized Point getLocation() {
            return location;
        }
        public synchronized void setLocation(Point location) {
            boolean reachedDestination;
            synchronized (this) {
                this.location = location;
                reachedDestination = location.equals(destination);
            }
            if (reachedDestination) {
                dispatcher.notifyAvailable(this);
            }
        }
        public synchronized Point getDestination() {
            return destination;
        }
        public synchronized void setDestination(Point destination) {
            this.destination = destination;
        }
    }
    @ThreadSafe
    class Dispatcher {
        @GuardedBy("this")
        private final Set<Taxi> taxis;
        @GuardedBy("this")
        private final Set<Taxi> availableTaxis;
        public Dispatcher() {
            taxis = new HashSet<Taxi>();
            availableTaxis = new HashSet<Taxi>();
        }
        public synchronized void notifyAvailable(Taxi taxi) {
            availableTaxis.add(taxi);
        }
        public Image getImage() {
            Set<Taxi> copy;
            synchronized (this) {
                copy = new HashSet<Taxi>(taxis);
            }
            Image image = new Image();
            for (Taxi t : copy) {
                image.drawMarker(t.getLocation());
            }
            return image;
        }
    }
    class Image {
        public void drawMarker(Point p) {
        }
    }
}

注意事项：有时候，在重新编写同步代码块以使用开放调用时会产生意想不到的结果，因为这会使得某个原子操作变为非原子操作。在许多情况下，使某个操作失去原子性是可以接受的。
Tips：解决原子性引发的错误，可以在将服务的状态更新为”关闭“之前一直持有锁，依赖于构造的一些协议（而不是通过加锁）来防止其他线程进入代码的临界区。

资源死锁

正如当多个线程相互持有彼此正在等待的锁而又不释放自己已持有的锁时会发生死锁，当它们在相同的资源集合上等待时，也会发生死锁。
另一种基于资源的死锁形式就是线程饥饿死锁，参考《饥饿死锁》部分。

死锁的避免与诊断

尽量减少潜在的加锁交互数量，将获取锁时需要遵循的协议写入正式文档并始终遵循这些文档。

在使用细粒度锁的程序中，可以通过使用一种两阶段策略来检查代码中的死锁：
首先，找出在什么地方将获取多个锁（使这个集合尽量小），然后对所有这些实例进行全局分析，从而确保它们在整个程序中获取锁的顺序都保持一致。

尽可能地使用开放调用，这能极大地简化分析过程。如果所有的调用都是开放调用，那么要发现获取多个锁的实例是非常简单的，可以通过代码审查，或者借助自动化的源代码分析工具。

支持定时的锁

显式使用Lock类中的定时tryLock功能来代替内置锁机制。当使用内置锁时，只要没有获得锁，就会永远等待下去，而显式锁则可以指定一个超时时限，在等待超过该时间后tryLock会返回一个失败信息。如果超时时限比获取锁的时间要长很多，那么就可以在发生某个意外情况后重新获得控制权。

其他活跃性危险

饥饿

当线程无法访问它所需要的资源而不能继续执行时，就会发生。引发饥饿的最常见资源就是CPU时钟周期。如果在Java应用程序中对线程的优先级使用不当，或者持有锁时执行一些无法结束的结构，那么也可能导致饥饿，因为其他需要这个锁的线程将无法得到它。

要避免使用线程优先级，因为这会增加平台依赖性，并可能导致活跃性问题。在大多数并发应用程序中，都可以使用默认的线程优先级。

糟糕的响应性

CPU密集型的后台任务仍然可能对响应性造成影响，因为它们会与事件线程共同竞争CPU的时钟周期。

不良的锁管理也可能导致糟糕的相应性。如果某个线程长时间占有一个锁，而其他想要访问这个容器的线程就必须等待很长时间。

活锁

活锁是另一种形式的活跃性问题，该问题尽管不会阻塞线程，但也不能继续执行，因为线程将不断执行相同的操作，而且总会失败。

活锁通常发生在处理事务消息的应用程序中：

• 如果不能成功地处理某个消息，那么消息处理机制将会回滚整个事务，并将它重新放到队列的开头。
• 如果消息处理器在处理某种特定类型的消息时存在错误并导致它失败，那么每当这个消息从队列中取出并传递到错误的处理器时，都会发生事务回滚。
• 由于这条消息又被放到队列开头，因此处理器将被反复调用，并返回相同的结果。

虽然处理消息的线程并没有阻塞，但也无法继续执行下去。这种形式的活锁通常是由过度的错误恢复代码导致，因为它错误地将不可修复的错误作为可修复的错误。

当多个相互协作的线程都对彼此进行响应从而修改各自的状态，并使得任何一个线程都无法继续执行时，就发生了活锁。

要解决这种活锁问题，需要在重试机制中引入随机性。在并发应用程序中，通过等待随机长度的时间和回退可以有效地避免活锁的发生。

对性能的思考

性能与可伸缩性

可伸缩性指的是：当增加计算资源时（例如CPU、内存、存储容量或I/O带宽），程序的吞吐量或者处理能力响应地增加。

当进行性能调优时，其目的通常是用更小的代价完成相同的工作，在进行可伸缩性调优时，其目的是设法将问题的计算并行化，从而能利用更多地计算资源来完成更多的工作。

评估各种性能权衡因素

避免不成熟的优化。首先使程序正确，然后再提高运行速度——如果它还运行得不够快。
以测试为基准，不要猜测。

• “更快”的含义是什么？
• 该方法在什么条件下运行得更快？在低负载还是高负载的情况下？大数据集还是小数据集？能否通过测试结果来验证你的答案？
• 这些条件在运行环境中的发生频率？能否通过测试结果来验证你的答案？
• 在其他不同条件的环境中能否使用这里的代码？
• 在实现这种性能提升时需要付出哪些隐含地代价，例如增加开发风险或维护开销？这种权衡是否合适？

Amdahl定律

Amdahl定律描述的是：

在增加计算资源的情况下，程序在理论上能够实现最高加速比，这个值取决与程序中可并行组件与串行组件所占的比重。 假定F时必须被串行执行的部分，那么根据Amdahl定律，在包含N个处理器的机器中，最高的加速比为：

在串行部分所占不同比例下的最高利用率：

在所有并发程序中都包含一些串行部分。

多个线程反复地从一个共享Queue中取出元素进行处理，处理步骤只需执行线程本地的计算。 如果某个线程发现队列为空，那么它将把一组新元素放入队列，因而其他线程在下一次访问时不会没有元素可供处理。

降低锁粒度的两种技术：

锁分解（将一个锁分解为两个锁）和锁分段（把一个锁分解为多个锁）。

当通过Amdahl定律来分析这两项技术时，我们会发现，如果将一个锁分解为两个锁，似乎并不能充分利用多处理器的能力。 锁分段技术似乎更有前途，因为分段的数量可随着处理器数量的增加而增加。 当然，性能优化应该考虑实际的性能需求，在某些情况下，将一个锁分解为两个就够了。

线程引入的开销

单线程程序既不存在线程调度，也不存在同步开销，而且不需要使用锁来保护数据结构的一致性。在多个线程的调度和协调过程总都需要一定的性能开销：
对于为了提升性能而引入的线程来说，并行带来的性能提升必须超过并发导致的开销。

上下文切换

如果主线程是唯一的线程，那么它基本上不会被调度出去。 另一方面，如果可运行的线程数大于CPU的数量，那么操作系统最终会将某个正在运行的线程调度出来，从而使其他线程能够使用CPU。
这将导致一次上下文切换，在这个过程中将保存当前运行线程的执行上下文，并将新调度进来的线程的上下文设置为当前上下文。

当上下文切换的开销并不只是包含JVM和操作系统的开销，当一个新的线程被切换进来时，它所需要的数据可能不在当前处理器的本地缓存中，因此上下文切换将导致一些缓存缺失，因而线程在首次调度运行时会更加缓慢。
这就是为什么调度器会为每个可运行的线程分配一个最小执行时间，即使有许多其他的线程正在等待执行：它将上下文切换的开销分摊到更多不会中断的执行时间上，从而提高整体的吞吐量（以损失响应性为代价）。

上下文切换的实际开销会随着平台的不同而变化，然而按照经验来看：

在大多数通用的处理器中，上下文切换的开销相当于5000~10000个时钟周期，也就是几微秒。

当线程由于等待某个发生竞争的锁而被阻塞时，JVM通常会将这个线程挂起，并允许它被交换出去。 如果线程频繁发生阻塞，那么它们将无法使用完整的调度时间片。 在程序中发生越多的阻塞（包括阻塞I/O，等待获取发生竞争的锁，或者在条件变量上等待），与CPU密集型的程序就会发生越多的上下文交换，从而增加调度开销，并因此而降低吞吐量。
UNIX系统的vmstat命令和Windows系统的perfmon工具都能报告上下文切换次数以及在内核中执行时间所占比例等信息。 如果内核占用率较高（超过10%），那么通常表示调度活动发生得很频繁，这很可能是由I/O或竞争锁导致的阻塞引起的。

内存同步

同步操作的性能开销包括多个方面。 在synchronized和volatile提供的可见性保证中可能会使用一些特殊指令，即内存栅栏（Memory Barrier）。 内存栅栏可以刷新缓存，使缓存无效，刷新硬件的写缓存，以及停止执行管道。 内存栅栏可能同样会对性能带来间接的影响，因为它们将抑制一些编译器优化操作。在内存栅栏中，大多数操作都是不能被重排序的。

评估同步操作带来的性能影响时，区分有竞争的同步和无竞争的同步非常重要。synchronized机制针对无竞争的同步进行了优化（volatile通常是非竞争的）。

一个“快速通道”的非竞争同步将消耗20~250个时钟周期。虽然无竞争同步的开销不为零，但它对应用程序整体性能的影响微乎其微。

现代的JVM能够通过优化去掉一些不会发生竞争的锁，从而减少不必要的同步开销。如果一个锁对象只能由当前线程访问，那么JVM就可以通过优化来去掉这个锁获取操作，因为另一个线程无法与当前线程在这个锁上发生同步。

synchronized (new Object()) {
    // 执行一些操作...
}

一些更完备的JVM能通过逸出分析来找出不会发布到堆的本地变量引用（因此这个引用是线程本地的）。
即使不进行逸出分析，编译器也可以执行锁粒度粗化，操作，即将邻近的同步代码块用同一个锁合并起来。这不仅减少了同步的开销，同时还能使优化器处理更大的代码块，从而可能实现进一步的优化。

public String getStoogeNames() {
	// JVM通常会分析这些调用，从而使stooges及其内部状态不会逸出，因此可以去掉这4次锁获取操作。
    List<String> stooges = new Vector<String>();//Vector是线程安全的
    stooges.add("Moe");
    stooges.add("Larry");
    stooges.add("Curly");
    return stooges.toString();
}

不要过度担心非竞争同步带来的开销。这个基本的机制已经非常快了，并且JVM还能进行额外的优化以进一步降低或消除开销。 因此，我们应该将优化重点放在那些发生锁竞争的地方。

某个线程的同步可能会影响其他线程的性能。同步会增加共享总线上的通信量，总线的带宽是有限的，并且所有的处理器都将共享这条总线。如果有多个线程竞争同步带宽，那么所有使用了同步的线程都会受到影响。

阻塞

非竞争的同步可以完全在JVM中进行处理，而竞争的同步可能需要操作系统的介入，从而增加开销。当在锁上发生竞争时，竞争失败的线程肯定会阻塞。

JVM在实现阻塞行为时，可以采用自旋等待（Spin-Waiting，指通过循环不断地尝试获取锁，直到成功）或者通过操作系统挂起被阻塞的线程。
这两种方式的效率高低，要取决于上下文切换的开销以及在成功获取锁之前需要等待的时间。

• 如果等待的时间较短，则适合采用自旋等待方式
• 而如果等待的时间较长，则适合采用线程挂起方式

有些JVM将根据对历史等待时间的分析数据在这两者之间进行选择，但是大多数JVM在等待锁时都只是将线程挂起。

减少锁的竞争

在并发程序中，对可伸缩性的最主要威胁就是独占方式的资源锁。

有两个因素将影响在锁上发生竞争的可能性：锁的请求频率，以及每次持有该锁的时间。
如果二者的乘积很小，那么大多数获取锁的操作都不会发生竞争，因此在该锁上的竞争不会对可伸缩性造成严重的影响。 然而，如果在锁上的请求量很高，那么需要获取该锁的线程被阻塞并等待。 在极端的情况下，即使仍有大量工作等待完成，处理器也会被闲置。

有3种方式可以降低锁的竞争程度：

• 减少锁的持有时间
• 降低锁的请求频率
• 使用带有协调机制的独占锁，这些机制允许更高的并发性

缩小锁的范围（“快进快出“）

降低发生竞争可能性的一种有效方式就是尽可能缩短锁的持有时间。
例如，可以将一些与锁无关的代码移除同步代码块，尤其是那些开销比较大的曹组，以及可能被阻塞的操作，例如I/O操作。

根据Amdahl定律，这样消除了限制可伸缩性的一个因素，因为串行代码的总量减少

public synchronized boolean userLocationMatches(String name, String regexp) {
    String key = "users." + name + ".location";
    String location = attributes.get(key);
    if (location == null) {
        return false;
    } else {
        return Pattern.matches(regexp, location);
    }
}
public boolean userLocationMatches(String name, String regexp) {
    String key = "users." + name + ".location";
    String location;
    // 降低锁的范围，可以通过线程安全性委托给并发库中的类进一步提升性能
    synchronized (this) {
        location = attributes.get(key);
    }
    if (location == null) {
        return false;
    } else {
        return Pattern.matches(regexp, location);
    }
}

尽管缩小同步代码块能提高可伸缩性，但同步代码快也不能过小——一些需要采用原子方式执行的操作（例如对某个不变性条件中的多个变量进行更新）必须包含在一个同步块中。
此外，同步需要一定的开销，当把一个同步代码块分解为多个同步代码块时（在确保正确性的情况下），反而会对性能提升产生负面影响。
在分解同步代码块时，理想的平衡点将与平台相关（虚拟机执行锁力度粗化操作，可能将分解的同步块重新合并起来），在实际情况中，仅当可以将一些“大量”的计算或阻塞操作从同步代码块中移出时，才应该考虑同步代码块的大小。

减小锁的粒度

另一种减小锁的持有时间的方式是降低线程请求锁的频率（从而减小发生竞争的可能性）。
这可以通过锁分解和锁分段技术来实现，在这些技术中将采用多个相互独立的锁来保护独立的状态变量，从而改变这些变量在之前由单个锁来保护的情况。
这些技术能减小锁操作的粒度，并能实现更高的可伸缩性，然而，使用的锁越多，那么发生死锁的风险也越高。

锁分解

如果一个锁需要保护多个相互独立的状态变量，那么可以将这个锁分解为多个锁，并且每个锁只保护一个变量，从而提高可伸缩性，并最终降低每个锁被请求的频率。

• 如果在锁上存在适中而不是激烈的竞争，通过将一个锁分解为两个锁，能最大限度地提升性能。
  • 对竞争适中的锁进行分解时，实际上是把这些锁转变为非竞争的锁，从而有效地提高性能和可伸缩性。
• 如果对竞争并不激烈的锁进行分解，那么在性能和吞吐量等方面带来的提升将非常有限，但是也会提高性能随着竞争提高而下降的拐点值。

@ThreadSafe
public class ServerStatusBeforeSplit {
    @GuardedBy("this")
    public final Set<String> users;
    @GuardedBy("this")
    public final Set<String> queries;
    public ServerStatusBeforeSplit() {
        users = new HashSet<String>();
        queries = new HashSet<String>();
    }
    public synchronized void addUser(String u) {
        users.add(u);
    }
    public synchronized void addQuery(String q) {
        queries.add(q);
    }
    public synchronized void removeUser(String u) {
        users.remove(u);
    }
    public synchronized void removeQuery(String q) {
        queries.remove(q);
    }
}

// 每个状态由自己的锁保护
// 还可以将Set委托给线程安全的Set，继续分解锁粒度
@ThreadSafe
public class ServerStatusAfterSplit {
    @GuardedBy("users")
    public final Set<String> users;
    @GuardedBy("queries")
    public final Set<String> queries;
    public ServerStatusAfterSplit() {
        users = new HashSet<String>();
        queries = new HashSet<String>();
    }
    public void addUser(String u) {
        synchronized (users) {
            users.add(u);
        }
    }
    public void addQuery(String q) {
        synchronized (queries) {
            queries.add(q);
        }
    }
    public void removeUser(String u) {
        synchronized (users) {
            users.remove(u);
        }
    }
    public void removeQuery(String q) {
        synchronized (users) {
            queries.remove(q);
        }
    }
}

锁分段

在某些情况下，可以将锁分解技术进一步扩展为对一组独立对象上的锁进行分解，这种情况被称为锁分段。

在ConcurrentHashMap的实现中使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16，其中第N个散列桶由第（N mod 16）个锁来保护。
假设散列函数具有合理的分布性，并且关键字能够均匀分布，那么这大约能把对于锁的请求减少到原来的1/16，正是这项技术使得ConcurrentHashMap能够支持多达16个并发的写入器。
要使得拥有大量处理器的系统在高访问量的情况下实现更高的并发性，还可以进一步增加锁的数量，但仅当你能证明并发写入线程的竞争足够激烈并需要突破这个限制时，才能将锁分段的数量超过默认的16个。

锁分段的一个劣势在于：

与采用单个锁来实现独占访问相比，要获取多个锁来实现独占访问将更加困难并且开销更高。 通常，在执行一个操作时最多只需获取一个锁，但在某些情况下需要加锁整个容器。

当ConcurrentHashMap需要扩展映射范围，以及重新计算键值的散列值要分布到更大的桶集合中时，就需要获取分段锁集合中的所有锁（要获取内置锁的一个集合，唯一的方式是递归）。

如果程序采用锁分段或分解技术，那么一定要表现出在锁上的竞争频率高于在锁保护的数据上发生竞争的频率。

@ThreadSafe
public class StripedMap {
    // Synchronization policy: buckets[n] guarded by locks[n%N_LOCKS]
    private static final int N_LOCKS = 16;
    private final Node[] buckets;
    private final Object[] locks;
    public StripedMap(int numBuckets) {
        buckets = new Node[numBuckets];
        locks = new Object[N_LOCKS];
        for (int i = 0; i < N_LOCKS; i++) {
            locks[i] = new Object();
        }
    }
    private final int hash(Object key) {
        return Math.abs(key.hashCode() % buckets.length);
    }
    public Object get(Object key) {
        int hash = hash(key);
        synchronized (locks[hash % N_LOCKS]) {
            for (Node m = buckets[hash]; m != null; m = m.next) {
                if (m.key.equals(key)) {
                    return m.value;
                }
            }
        }
        return null;
    }
    public void clear() {
    	// 非原子操作
        for (int i = 0; i < buckets.length; i++) {
            synchronized (locks[i % N_LOCKS]) {
                buckets[i] = null;
            }
        }
    }
    private static class Node {
        Node next;
        Object key;
        Object value;
    }
}

线程安全的Map性能比较

在ConcurrentHashMap的实现中假设，大多数常用的操作都是获取某个已经存在的值，因此它对各种get操作进行了优化从而提供了最高的性能和并发性。

• 在同步Map的实现中，可伸缩性的最主要阻碍在于整个Map中只有一个锁，因此每次只有一个线程能够访问这个Map。
• 不同的是，ConcurrentHashMap对于大多数读操作并不会加锁，并且在写入操作以及其他一些需要锁的读取操作中使用了锁分段技术。因此，多个线程能并发地访问这个Map而不会发生阻塞。

不同Map实现的可伸缩性比较：

每次运行时，将有N个线程并发地执行一个紧凑的循环：选择一个随机的键值，并尝试获取这个键值相对应的值。 如果不存在对应的值，那么将这个值增加到Map的概率为p=0.6； 如果存在对应的值，那么将这个值删除的概率为p=0.02。

避免热点域

当每个操作都请求多个变量时，锁的粒度将很难降低。这是在性能与可伸缩性之间相互制衡的另一个方面
一些常见的优化措施，例如将一些反复计算的结果缓存起来，都会引入一些”热点域“，而这些热点域往往会限制可伸缩性。

当实现HashMap时，你需要考虑如何在size方法中计算Map中的元素数量。最简单的方法就是，在每次调用时都统计一次元素的数量。
一种常见的优化措施是，在插入和移除元素时更新一个计数器，虽然这在put和remove等方法中略微增加了一些开销，以确保计数器是最新的值，但这把size方法的开销从O(n)降低到O(1)。

使用一个独立的计算器能很好地提高类似size和isEmpty这些方法的执行速度，但却导致更难以提升实现的可伸缩性，因为每个修改map的操作都需要更新这个共享的计数器。
即使使用锁分段技术来实现散列链，那么在对计数器的访问进行同步时，也会重新导致在使用独占锁时存在的可伸缩性问题。
一个看似性能优化的措施——缓存size操作的结果，已经变成了一个可伸缩性问题。在这种情况下，计数器也被称为热点域，因为每个导致元素数量发生变化的操作都需要访问它。
为了避免这个问题，ConcurrentHashMap中的size将对每个分段进行枚举并将每个分段中的元素数量相加，而不是维护一个全局计数。 为了避免枚举每个元素，ConcurrentHashMap为每个分段都维护一个独立的计数，并通过每个分段的锁来维护这个值。

一些替代独占锁的方法

第三种降低竞争锁的影响的技术就是放弃使用独占锁，从而有助于使用一种友好并发的方式来管理共享状态。例如，使用并发容器、读-写锁、不可变对象以及原子变量。

ReadWriteLock实现了一种在多个读取操作以及单个写入操作情况下的加锁规则：

• 如果多个读取操作都不会修改共享资源，那么这些读取操作可以同时访问该共享资源
• 但在执行写入操作时必须以独占方式来获取锁

对于读取操作占多数的数据结构，ReadWriteLock能够提供比独占锁更高的并发性。而对于只读的数据结构，其中包含的不变性可以完全不需要加锁操作。

原子变量提供了一种方式来降低更新“热点域”时的开销，例如竞态计数器、序列发生器、或者对链表数据结构中头节点的引用。

原子变量类提供了在整数或者对象引用上的细粒度原子操作（因此可伸缩性更高），并使用了现代处理器中提供的底层并发原语（例如比较并交换）。
如果在类中只包含少量的热点域，并且这些域不会与其他变量参与到不变性条件中，那么用原子变量来替代他们能提高可伸缩性。
通过减少算法中的热点域，可以提高可伸缩性——虽然原子变量能降低热点域的更新开销，但并不能完全消除。

监测CPU的利用率

当测试可伸缩性时，通常要确保处理器得到充分利用。一些工具，例如UNIX系统上的vmstat和mpstat，或者Windows系统上的perfmon，都能给出处理器的“忙碌“状态。

如果所有CPU的利用率并不均匀（有些CPU在忙碌地运行，而其他CPU却并非如此），那么你的首要目标就是进一步找出程序中的并行性。 不均匀的利用率表明大多数计算都是由一小组线程完成的，并且应用程序没有利用其他的处理器。

如果CPU没有得到充分利用，那么需要找出其中的原因。通常由以下几种原因：

• 负载不充足
  • 测试的程序中可能没有足够多的负载，因而还可以在测试时增加负载，并检查利用率、响应时间和服务时间等指标的变化。如果产生足够多的负载使应用程序达到饱和，那么可能需要大量的计算机能耗，并且问题可能在于客户端系统是否具有足够的能力，而不是被测试系统。
• I/O密集
  • 可以通过iostat或perfmon来判断某个应用程序是否是磁盘I/O密集型的，或者通过监测网络的通信流量级别来判断它是否需要高带宽。
• 外部限制
  • 如果应用程序依赖于外部服务，例如数据库或Web服务，那么性能瓶颈可能并不在你自己的代码中。可以使用某个分析工具或数据库管理工具来判断在等待外部服务的结果时需要多少时间。
• 锁竞争
  • 使用分析工具可以知道在程序中存在何种程度的锁竞争，以及在哪些锁上存在”激烈的竞争“。然而，也可以通过其他一些方式来获得相同的信息，例如随机取样，触发一些线程转储并在其中查找在锁上发生竞争的线程。如果线程由于等待某个锁而被阻塞，那么在线程转储信息中将存在相应的栈帧，其中包含的信息形如”waiting to lock monitor…“。非竞争的锁很少会出现在线程转储中，而对于竞争激烈的锁，通常至少会有一个线程在等待获取它，因此在线程转储中频繁出现。

如果应用程序正在使CPU保持忙碌状态，那么可以使用监视工具来判断是否能通过增加额外的CPU来提升程序的性能。
如果一个程序只有4个线程，那么可以充分利用一个4路系统的计算能力，但当移植到8路系统上时，却未必能获得性能提升，因为可能需要更多的线程才会有效利用剩余的剩余的处理器。（可以通过重新配置程序将工作负载分配给更多的线程，例如调整线程池的大小。）
在vmstat命令的输出中，有一栏信息是当前处于可运行状态但并没有运行（由于没有足够的CPU）的线程数量。
如果CPU的利用率很高，并且总会有可运行的线程在等待CPU，那么当增加更多地处理器时，程序的性能可能会得到提升。

向对象池说“不”

通常，对象分配操作的开销比同步的开销更低。

如果线程从对象池中请求一个对象，那么就需要通过某种同步来协调对象池数据结构的访问，从而使某个线程被阻塞。 如果某个线程由于锁竞争而被阻塞，那么这种阻塞的开销将是内存分配操作开销的数百倍，因此即使对象池带来的竞争很小，也可能形成一个可伸缩性瓶颈。 （即使是一个非竞争的同步，所导致的开销也会比分配一个对象的开销大。）

减少上下文切换的开销

在许多任务中都包含一些可能被阻塞的操作。当任务在运行和阻塞这两个状态之间转换时，就相当于一次上下文切换。

在服务器应用程序中，发生阻塞的原因之一就是在处理请求时产生各种日志消息。

通过将I/O操作从处理请求的线程分离出来，可以缩短处理请求的平均服务时间。

对象共享

可见性

在没有同步的情况下，编译器、处理器以及运行时等都可能对操作的执行顺序进行一些意想不到的调整。在缺乏足够同步的多线程程序中，要想对内存操作的执行顺序进行判断，几乎无法得出正确的结论。

有一种简单的方法能避免这些复杂的问题：只要有数据在多个线程之间共享，就使用正确的同步。

失效数据

由于内存可见性问题导致线程获取到数据是失效数据

仅对set方法进行同步是不够的，调用get的线程仍然会看见失效值。

非原子的64位操作

非volatile类型的64位数值变量（double和long）。

Java内存模型要求，变量的读取操作和写入操作都必须是原子操作，但对于非volatile类型的long和double变量，JVM允许将64位的读操作或写操作分解为两个32位的操作。
当读取一个非volatile类型的long变量时，如果对该变量的读操作和写操作在不同的线程中执行，那么很可能会读取到某个值的高32位和另一个值的低32位。
因此，即使不考虑失效数据问题，在多线程程序中使用共享且可变的long和double等类型的变量也是不安全的，除非用关键字volatile来声明它们，或者用锁保护起来。

参考虚拟机部分的，现代虚拟机对这部分的实现做了优化（处理器支持了64位数值的原子操作），所以可以保证操作原子性

加锁与可见性

加锁的含义不仅仅局限于互斥行为，还包括内存可见性。为了确保所有线程都能看到共享变量的最新值，所有执行读操作或者写操作的线程都必须在同一个锁上同步。

同步的可见性保证：

Volatile变量

volatile变量是一种比sychronized关键字更轻量级的同步机制。（在当前大多数处理器架构上，读取volatile变量的开销只比读取非volatile变量的开销略高一些。）

并不建议过度依赖volatile变量提供的可见性。如果在代码中依赖volatile变量来控制状态的可见性，通常比使用锁的代码更脆弱，也更难以理解。

仅当volatile变量能简化代码的实现以及对同步策略的验证时，才应该使用它们。 如果在验证正确性时需要对可见性进行复杂的判断，那么就不要使用volatile变量。

volatile变量的正确使用方式包括：

确保它们自身状态的可见性，确保它们所引用对象的状态的可见性，以及标识一些重要的程序生命周期事件的发生（例如，初始化或关闭）。

加锁机制既可以确保可见性又可以确保原子性，而volatile变量只能确保可见性。

当且仅当满足以下所有条件时，才应该使用volatile变量：

• 对变量的写入操作不依赖变量的当前值，或者你能确保只有单个线程更新变量的值。
• 该变量不会与其他状态变量一起纳入不变性条件中。
• 在访问变量时不需要加锁。

Tips：对于服务器应用程序，无论在开发阶段还是在测试阶段，当启动JVM时一定都要指定-server命令行选项。server模式的JVM将比client模式的JVM进行更多的优化，

发布与逸出

“发布（Publish）”一个对象的意思是指，使对象能够在当前作用域之外的代码中使用
当某个不应该发布的对象被发布时，这种情况就被称为逸出（Escape）

封装能够使得对程序的正确性进行分析变得可可能，并使得无意中破坏设计约束条件变得更难。

• 不要在构造过程中使this引用逸出。this引用都会被新创建的线程共享。在对象尚未完全构造之前，新的线程就可以看见它。
• 在构造函数中创建线程并没有错误，但最好不要立即启动它，而是通过一个start或initialize方法来启动。
• 在构造函数中调用一个可改写的实例方法时（既不是私有方法，也不是终结方法），同样会导致this引用在构造过程中逸出。

public class ThisEscape {
	public ThisEscape(EventSource source) {
	    source.registerListener(new EventListener() {
	        public void onEvent(Event e) {
	        	// unsafe this escape
	            doSomething(e);
	        }
	    });
	}
	void doSomething(Event e) {}
	interface EventSource {
	    void registerListener(EventListener e);
	}
	interface EventListener {
	    void onEvent(Event e);
	}
	interface Event {}
}

上述代码是一个构造方法，构造方法是用来创建对象的，但是构造方法里面有内部类，内部类有隐式引用，也就是说外部类在构造过程中被其构造方法里的内部类引用了，本身构造过程还没完就引用了自己肯定是有问题的。

与此类似的还有，在构造方法中新启线程，使用线程可以，注意不要执行start()方法，否则会逸出。

使用一个私有的构造函数和一个公共的工厂方法（Factory Method），从而避免不正确的构造过程

public class SafeListener {
    private final EventListener listener;
    private SafeListener() {
        listener = new EventListener() {
            public void onEvent(Event e) {
                doSomething(e);
            }
        };
    }
    public static SafeListener newInstance(EventSource source) {
        SafeListener safe = new SafeListener();
        source.registerListener(safe.listener);
        return safe;
    }
    void doSomething(Event e) {}
    interface EventSource {
        void registerListener(EventListener e);
    }
    interface EventListener {
        void onEvent(Event e);
    }
    interface Event {}
}

线程封闭

当访问共享的可变数据时，通常需要使用同步。一种避免使用同步的方式就是不共享数据。如果仅在单线程内访问数据，就不需要同步。 这种技术被称为线程封闭（Thread Confinement），它是实现线程安全性的最简单方式之一。当某个对象封闭在一个线程中时，这种用法将自动实现线程安全性，即使被封闭的对象本身不是线程安全的。

Ad-hoc线程封闭

Ad-hoc线程封闭是指，维护线程封闭性的职责完全由程序实现来承担。

Ad-hoc线程封闭是非常脆弱的，因为没有任何一种语言特性，例如可见性修饰符或局部变量，能将对象封闭到目标线程上。事实上，对线程封闭对象的引用通常保存在公有变量中。

当决定使用线程封闭技术时，通常是因为要将某个特定的子系统实现为一个单线程子系统。 在某些情况下，单线程子系统提供的简便性要胜过Ad-hoc线程封闭技术的脆弱性。

在volatile变量上存在一种特殊的线程封闭。只要你能确保只有单个线程对共享的volatile变量执行写入操作，那么就可以安全地在这些共享的volatile变量上执行“读取-修改-写入”的操作。 在这种情况下，相当于将修改操作封闭在单个线程中以防止发生竞态条件，并且volatile变量的可见性保证还确保了其他线程能看到最新的值。

由于Ad-hoc线程封闭技术的脆弱性，因此在程序中尽量少用它，在可能的情况下，应该使用更强的线程封闭技术（例如，栈封闭或ThreadLocal类）。

栈封闭

栈封闭是线程封闭的一种特例，在栈封闭中，只能通过局部变量才能访问对象。

正如封装能使得代码更容易维持不变性条件那样，同步变量也能使对象更易于封闭在线程中。 局部变量的固有属性之一就是封闭在执行线程中。它们位于执行线程的栈中，其他线程无法访问这个栈。 栈封闭（也被称为线程内部使用或者线程局部使用）比Ad-hoc线程封闭更易于维护，也更加健壮。

public int loadTheArk(Collection<Animal> candidates) {
    SortedSet<Animal> animals;
    int numPairs = 0;
    Animal candidate = null;
    // 只有一个引用指向集合animals，这个引用被封闭在局部变量中，因此也被封闭在执行线程中
    animals = new TreeSet<Animal>(new SpeciesGenderComparator());
    animals.addAll(candidates);
    for (Animal a : animals) {
        if (candidate == null || !candidate.isPotentialMate(a))
            candidate = a;
        else {
            ark.load(new AnimalPair(candidate, a));
            ++numPairs;
            candidate = null;
        }
    }
    return numPairs;
}

ThreadLocal类

维持线程封闭性的一种更规范方法是使用ThreadLocal，这个类能使线程中的某个值与保存值的对象关联起来

ThreadLocal对象通常用于防止对可变的单实例变量（Singleton）或全局变量进行共享，这些特定于线程的值保存在Thread对象中，当线程终止后，这些值会作为垃圾回收。

ThreadLocal变量类似于全局变量，它能降低代码的可重用性，并在类之间引入隐含的耦合性，因此在使用时要格外小心。

不可变性

满足同步需求的另一种方法是使用不可变对象（Immutable Object）

当满足以下条件时，对象才是不可变的：

• 对象创建以后其状态就不能修改
• 对象的所有域都是final类型（引用的对象也要保证不逸出）
• 对象是正确创建的（在对象的创建期间，this引用没有逸出）

final域

final类型的域是不能修改的（但如果final域所引用的对象是可变的，那么这些被引用的对象是可以修改的）。 然而，在Java内存模型中，final域还有着特殊的语义。final域能确保初始化过程的安全性，从而可以不受限制地访问不可变对象，并在共享这些对象时无须同步。

即使对象是可变的，通过将对象的某些域声明为final类型，仍然可以简化对状态的判断，因此限制对象的可变性也就相当于限制了该对象可能的状态集合。仅包含一个或两个可变状态的“基本不可变”对象仍然比包含多个可变状态的对象简单。通过将域声明为final类型，也相当于告诉维护人员这些域是不会变化的。

正如“除非需要更高的可见性，否则应将所有的域都声明为私有域”是一个良好的编程习惯，“除非需要某个域是可变的，否则应将其声明为final域”也是一个良好的编程习惯。

使用Volatile类型来发布不可变对象:

public class OneValueCache {
    private final BigInteger lastNumber;
    private final BigInteger[] lastFactors;
    public OneValueCache(BigInteger i, BigInteger[] factors) {
        lastNumber = i;
        lastFactors = Arrays.copyOf(factors, factors.length);
    }
    public BigInteger[] getFactors(BigInteger i) {
        if (lastNumber == null || !lastNumber.equals(i)) {
            return null;
        } else {
            return Arrays.copyOf(lastFactors, lastFactors.length);
        }
    }
}

public class VolatileCachedFactorizer extends GenericServlet implements Servlet {
    private volatile OneValueCache cache = new OneValueCache(null, null);
    public void service(ServletRequest req, ServletResponse resp) {
        BigInteger i = extractFromRequest(req);
        BigInteger[] factors = cache.getFactors(i);
        if (factors == null) {
            factors = factor(i);
            cache = new OneValueCache(i, factors);
        }
        encodeIntoResponse(resp, factors);
    }
    void encodeIntoResponse(ServletResponse resp, BigInteger[] factors) {}
    BigInteger extractFromRequest(ServletRequest req) {
        return new BigInteger("7");
    }
    BigInteger[] factor(BigInteger i) {
        // Doesn't really factor
        return new BigInteger[]{i};
    }
}

安全发布

不安全的发布

参考《发布与逸出》部分

各种安全技术，它们的安全性都来自于JMM提供的保证，而造成不正确发布的真正原因，就是在”发布一个共享对象“与”另一个线程访问该对象“之前缺少一种Happens-Before排序。

当缺少Happens-Before关系时，就可能出现重排序问题，这就解释了为什么在没有充分同步的情况下发布一个对象会导致另一个线程看到一个只被部分构造的对象。
在初始化一个新的对象时需要写入多个变量，即新对象中的各个域。 同样，在发布一个引用时也需要写入一个变量，即新对象的引用。 如果无法确保发布共享引用的操作在另一个线程加载该共享引用之前执行，那么对新对象引用的写入操作将与对象中各个域的写入操作重排序（从使用该对象的线程的角度来看）。
在这种情况下，另一个线程可能看到对象引用的最新值，但同时也将看到对象的某些或全部状态中包含的是无效值，即一个被部分构造对象。

除了不可变对象之外，使用被另一个线程初始化的对象通常是不安全的，除非对象的发布操作是在使用该对象的线程开始使用之前执行。

安全的发布

安全发布常用模式可以确保被发布对象对于其他线程是可见的，因为它们保证发布对象的操作将在使用对象的线程开始使用该对象的引用之前执行。
借助于类库中现在的同步容器、使用锁保护共享变量、或都使用共享的volatile类型变量，都可以保证对该变量的读取和写入是按照happens-before排序的。

happens-before事实上可以比安全发布承诺更强的可见性与顺序保证。 如果X对象从A线程到B线程是安全发布的，安全发布可以保证X本身的状态是可见的，但是不包括A所依赖的其他对象（即A中还包含了其他对象，不只是基本类型变量）的状态； 但是如果X对象是在同步的情况下由线程A生产，然后由线程B消费，B不仅仅能看到A中所有直接状态域，而且还能看见A所依赖的甚至是更深一层的状态域所做的更改。

安全初始化模式

参看《设计模式》的单例模式

使用静态域来初始化，会有的额外的线程安全性保证。 静态初始化是JVM完成的，发生在类的初始化阶段（加载、链接、类的初始化），即类被加载后到类被任意线程使用之前。 JVM会在初始化期间获得一个锁，这个锁每个线程都至少会获取一次，来确保类是否已被加载； 这个锁也保证了静态初始化期间，内存写入的结果自动地对照所有线程都是可见的。 所以静态初始化的对象，无论是构造期间还是被引用的时候，都不需要显试地进行同步。 然而，这仅仅适用于构造当时的状态——如果对象是可变的，为了保证后续修改的可见性，仍然需要同步。

@ThreadSafe
public class SafeLazyInitialization {
    private static Resource resource;
    public synchronized static Resource getInstance() {
        if (resource == null)
            resource = new Resource();
        return resource;
    }
    static class Resource {
    }
}

通过使用提前初始化（Eager Initialization），避免了在每次调用SafeLazyInitialization中的getInstance时所产生的同步开销。 通过将这项技术和JVM的延迟加载机制结合起来，可以形成一种延迟初始化技术，从而在常见的代码路径中不需要同步。

@ThreadSafe//主动初始化
public class EagerInitialization {
    private static Resource resource  = new Resource();
    public static Resource getResource() { return resource; }
}

“延迟初始化占位类（Static Holder）模式”中使用了一个专门的类来初始化Resource。 JVM将推迟ResourceHolder的初始化操作，知道开始使用这个类时才初始化，并且由于通过一个静态初始化来初始化Resource，因此不需要额外的同步。 当任何一个线程第一次调用getResource时，都会使ResourceHolder被加载和被初始化，此时静态初始化器执行Resource的初始化操作。

@ThreadSafe
public class ResourceFactory {
     private static class ResourceHolder {
         public static Resource resource = new Resource();
     }
     public static Resource getResource() {
         return  ResourceHolder.resource ;
     }
}

双重检查加锁

在常见的代码路径中——获取一个已构造好的Resource引用，并没有使用同步。这就是问题所在，线程可能看到一个仅被部分构造的Resource。

DCL的真正问题在于：当在没有同步的情况下读取一个共享对象时，可能发生的最糟糕事情只是看到一个失效值（在这种情况下是一个空值），此时DCL方法将通过在持有锁的情况下再次尝试避免这种风险。 然而，实际情况远比这种情况糟糕——线程可能看到引用的当前值，但对象的状态值却是失效的，这意味着线程可以看到对象处于无效或错误的状态。

@NotThreadSafe
public class DoubleCheckedLocking {
    private static Resource resource;
    public static Resource getInstance() {
        if (resource == null) {
            synchronized (DoubleCheckedLocking.class) {
                if (resource == null)
                    resource = new Resource();
            }
        }
        return resource;
    }
    static class Resource {}
}

在JMM的后续版本（Java5.0以及更高的版本）中，如果把resource声明为volatile类型，那么就能启用DCL，并且这种方式对性能影响很小，因为volatile变量读取操作的性能通常只是略高于非volatile变量的读取操作的性能。
然而，DCL的这种使用方法已经被广泛地废弃了——促使该模式出现的驱动力（无竞争同步的执行速度很慢，以及JVM启动时很慢）已经不复存在，因而它不是一种高效地优化措施。延迟初始化占位类模式能带来同样的优势，并且更容易理解。

初始化过程中的安全性

如果能确保初始化过程的安全性，那么就可以使得被正确构造的不可变对象在没有同步的情况下也能安全地在多个线程之间共享，而不管它们是如何发布的，甚至通过某种数据竞争来发布。

如果不能确保初始化的安全性，那么当在发布或线程中没有使用同步时，一些本应为不可变对象（例如String）的值将会发生改变。（为了确保初始化的安全，所以在1.5中String中的域都已修改成了final了）

初始化安全性将确保，对于被正确构造的对象，所有线程都能看到由构造函数为对象给各个final域设置的正确值，而不管采用何种方式来发布对象。 而且对于可以通过被正确构造对象中某个final域到达的任意变量（例如某个final数组中的元素，或者由一个final域引用的HashMap的内容）将同样对于其他线程是可见的。 （这仅仅适用于那些在构造过程中从对象的final域出发可以到达的对象）

对于含有final域的对象，初始化安全性可以防止对对象的初始引用被重排序到构造过程之前。 当构造函数完成时，构造函数对final域的所有写入操作，以及对通过这些域可以到达的任何变量的写入操作，都将被“冻结”，并且人设获得该对象的引用的线程都至少能确保看到被冻结的值。 对通过final域可到达的初始变量的写入操作，将不会域构造过程后的操作一起被重排序。

初始化安全性意味着，下面的SafeStates可以安全地发布，即便通过不安全的延迟初始化，或者在没有同步的情况下将SafeStates的引用放到一个公有的静态域，或者没有使用同步以及依赖于非线程安全的HashSet。

@ThreadSafe
public class SafeStates {
    private final Map<String, String> states;
    public SafeStates() {
        states = new HashMap<String, String>();
        states.put("alaska", "AK");
        states.put("alabama", "AL");
        /*...*/
        states.put("wyoming", "WY");
    }
    public String getAbbreviation(String s) {
        return states.get(s);
    }
}

然而，许多对SafeStates的细微修改都可能破坏它的线程安全性。

• 如果states不是final类型，或者存在除构造函数以外的其他方法能修改states，那么初始化安全性将无法确保在缺少同步的情况下安全地访问SafeStates。
• 如果在SafeStates中还有其他的非final域，那么其他线程仍然可能看到这些域上的不正确的值。

这也导致了对象在构造函数中逸出，从而使初始化安全性的保证无效。

初始化安全性只能保证通过final域可达的值从构造过程完成时可见性。对于通过非final域可达的值，或者在构成过程完成后可能改变的值，必须采用同步来确保可见性。

不可变对象与初始化安全性

任何线程都可以在不需要额外同步的情况下安全地访问不可变对象，即使在发布这些对象时没有使用同步。

这种保证还将延伸到被正确创建对象中所有final类型的域。在没有额外同步的情况下，也可以安全地访问final类型的域。然而，如果final类型的域所指向的是可变对象，那么在访问这些域所指向的对象的状态时仍然需要同步。

安全发布的常用模式

可变对象必须通过安全的方式来发布，这通常意味着在发布和使用该对象的线程时都必须使用同步。

要安全地发布一个对象，对象的引用以及对象的状态必须同时对其他线程可见。一个正确构造的对象可以通过以下方式来安全地发布：

• 在静态初始化函数中初始化一个对象引用
• 将对象的引用保存到volatile类型的域或者AtomicReferance对象中
• 将对象的引用保存到某个正确构造对象的final类型域中
• 将对象的引用保存到一个由锁保护的域中

• 线程安全库中的容器类提供了以下的安全发布保证：
  • 通过将一个键或者值放入Hashtable、synchronizedMap或者ConcurrentMap中，可以安全地将它发布给任何从这些容器中访问它的线程（无论是直接访问还是通过迭代器访问）。
  • 通过将某个元素放入Vector、CopyOnWriteArrayList、CopyOnWriteArraySet、synchronizedList或synchronizedSet中，可以将该元素安全地发布到任何从这些容器中访问该元素的线程。
  • 通过将某个元素放入BlockingQueue或者ConcurrentLinkedQueue中，可以将该元素安全地发布到任何从这些队列中访问该元素的线程。
• 类库中的其他数据传递机制（例如Future和Exchanger）同样能实现安全发布，在介绍这些机制时将讨论它们的安全发布功能。
• 静态初始化器由JVM在类的初始化阶段执行。由于在JVM内部存在着同步机制，因此通过这种方式初始化的任何对象都可以被安全地发布

事实不可变对象

如果对象从技术上来看是可变的，但其状态在发布后不会再改变，那么把这种对象称为“事实不可变对象（Effectively Immutable Object）”。

在没有额外的同步的情况下，任何线程都可以安全地使用被安全发布的事实不可变对象。

可变对象

对象的发布需求取决于它的可变性：

• 不可变对象可以通过任意机制来发布。
• 事实不可变对象必须通过安全方式来发布。
• 可变对象必须通过安全方式来发布，并且必须是线程安全的或者由某个锁保护起来。

安全地共享对象

在并发程序中使用和共享对象时，可以使用一些实用的策略，包括：

• 线程封闭
  • 线程封闭的对象只能由一个线程拥有，对象被封闭在该线程中，并且只能由这个线程修改。
• 只读共享
  • 在没有额外同步的情况下，共享的只读对象可以由多个线程并发访问，但任何线程都不能修改它。共享的只读对象包括不可变对象和事实不可变对象。
• 线程安全共享
  • 线程安全的对象在其内部实现同步，因此多个线程可以通过对象的公有接口来进行访问而不需要进一步的同步。
• 保护对象
  • 被保护的对象只能通过持有特定的锁来访问。保护对象包括封装在其他线程安全对象中的对象，以及已发布的并且由某个特定锁保护的对象。

如果一个数据模型必须被多个线程共享，而且由于阻塞、一致性或复杂度等原因而无法实现一个线程安全的模型时，可以考虑使用分解模型设计（DTO）。

对象的组合

设计线程安全的类

通过使用封装技术，可以使得在不对整个程序进行分析的情况下就可以判断一个类是否是线程安全的。

在设计线程安全类的过程中，需要包含以下三个基本要素：

• 找出构成对象状态的所有变量
• 找出约束状态变量的不变性条件
• 建立对象状态的并发访问管理策略

同步策略（Synchronization Policy）定义了如何在不违背对象不变条件或后验条件的情况下对其状态的访问操作进行协同。 同步策略规定了如何将不可变性、线程封闭与加锁机制等结合起来以维护线程的安全性，并且还规定了哪些变量由哪些锁来保护。 要确保开发人员可以对这个类进行分析与维护，就必须将同步策略写为正式文档。

收集同步需求

这些相关的变量必须在单个原子操作中进行读取或更新。不能首先更新一个变量，然后释放锁并再次获得锁，然后再更新其他的变量。 因为释放锁后，可能会使对象处于无效状态。如果在一个不变性条件中包含多个变量，那么在执行任何访问相关变量的操作时，都必须持有保护这些变量的锁。

如果不了解对象的不变性条件与后验条件，那么就不能确保线程安全性。要满足在状态变量的有效值或状态转换上的各种约束条件，就需要借助于原子性与封装性。

依赖状态的操作

• 在单线程程序中，如果某个操作无法满足先验条件，那么就只能失败。
• 但在并发程序中，先验条件可能会由于其他线程执行的操作而变成真。在并发程序中要一直等到先验条件为真，然后再执行该操作。

在Java中，等待某个条件为真的各种内置机制（包括等待和通知等机制）都与内置加锁机制紧密关联，要想正确地使用它们并不容易。 要想实现某个等待先验条件为真时才执行的操作，一种更简单的方法是通过现有库中的类（例如阻塞队列[Blocking Queue]或信号量[Semaphore]）来实现依赖状态的行为。

状态的所有权

许多情况下，所有权与封装性总是相互关联的：对象封装它拥有的状态，反之也成立，即对它封装的状态拥有所有权。状态变量的所有者将决定采用何种加锁协议来维持变量状态的完整性。所有权意味着控制权。然而，如果发布了某个可变对象的引用，那么就不再拥有独占的控制权，最多是“共享控制权”。对于从构造函数或者从方法中传递进来的对象，类通常并不拥有这些对象，除非这些方法是被专门设计为转移传递进来的对象的所有权（例如，同步容器封装器的工厂方法）。

实例封闭

将数据封装在对象内部，可以将数据的访问限制在对象的方法上，从而更容易确保线程在访问数据时总能持有正确的锁。

在Java平台的类库中还有很多线程封闭的示例，其中有些类的唯一用途就是将非线程安全的类转化为线程安全的类。
一些基本的容器类并非线程安全的，例如ArrayList和HashMap，但类库提供了包装器工厂方法（例如Collections.synchronizedList及其类似方法），使得这些非线程安全的类可以在多线程环境中安全地使用。 这些工厂方法通过“装饰器（Decorator）”模式（Gamma et al.，1995）将容器类封装在一个同步的包装器对象中，而包装器能将接口中的每个方法都实现为同步方法，并将调用请求转发到底层的容器对象上。 只要包装器对象拥有对底层容器对象的唯一引用（即把底层容器对象封闭在包装器中），那么它就是线程安全的。在这些方法的Javadoc中指出，对底层容器对象的所有访问必须通过包装器来进行。

封闭机制更易于构造线程安全的类，因为当封闭类的状态时，在分析类的线程安全性时就无须检查整个程序。

Java监视器模式

从线程封闭原则及其逻辑推论可以得出Java监视器模式。遵循Java监视器模式的对象会把对象的所有可变状态都封装起来，并由对象自己的内置锁来保护。

在许多类中都使用了Java监视器模式，例如Vector和Hashtable。Java监视器模式的主要优势就在于它的简单性。

@ThreadSafe
public class MonitorVehicleTracker {
    @GuardedBy("this") private final Map<String, MutablePoint> locations;
    public MonitorVehicleTracker(Map<String, MutablePoint> locations) {
        this.locations = deepCopy(locations);
    }
    public synchronized Map<String, MutablePoint> getLocations() {
    	// 占用锁时间长，效率低的做法
        return deepCopy(locations);
    }
    public synchronized MutablePoint getLocation(String id) {
        MutablePoint loc = locations.get(id);
        return loc == null ? null : new MutablePoint(loc);
    }
    public synchronized void setLocation(String id, int x, int y) {
        MutablePoint loc = locations.get(id);
        if (loc == null)
            throw new IllegalArgumentException("No such ID: " + id);
        loc.x = x;
        loc.y = y;
    }
    private static Map<String, MutablePoint> deepCopy(Map<String, MutablePoint> m) {
        Map<String, MutablePoint> result = new HashMap<String, MutablePoint>();
        for (String id : m.keySet()) {
            result.put(id, new MutablePoint(m.get(id)));
        }
        return Collections.unmodifiableMap(result);
    }
}

@NotThreadSafe
public class MutablePoint {
    public int x, y;
    public MutablePoint() {
        x = 0;
        y = 0;
    }
    public MutablePoint(MutablePoint p) {
        this.x = p.x;
        this.y = p.y;
    }
}

线程安全性的委托

大多数对象都是组合对象。当从头开始构建一个类，或者将多个非线程安全的类组合为一个类时，Java监视器模式是非常有用的。
但是，如果类中的各个组件都已经是线程安全的，是否需要再增加一个额外的线程安全层？答案是“视情况而定”。

// 将线程安全委托给ConcurrentHashMap

@ThreadSafe
public class DelegatingVehicleTracker {
    private final ConcurrentMap<String, Point> locations;
    private final Map<String, Point> unmodifiableMap;
    public DelegatingVehicleTracker(Map<String, Point> points) {
        locations = new ConcurrentHashMap<String, Point>(points);
        unmodifiableMap = Collections.unmodifiableMap(locations);
    }
    public Map<String, Point> getLocations() {
        return unmodifiableMap;
    }
    public Point getLocation(String id) {
        return locations.get(id);
    }
    public void setLocation(String id, int x, int y) {
        if (locations.replace(id, new Point(x, y)) == null){
            throw new IllegalArgumentException("invalid vehicle name: " + id);
        }
    }
    public Map<String, Point> getLocationsAsStatic() {
        return Collections.unmodifiableMap(
                new HashMap<String, Point>(locations));
    }
}
// 使用不可修改的Point对象防止封装性被破坏
@Immutable
public class Point {
    public final int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
// 如果需要返回一个不发生变化的车辆视图，可以返回一个浅拷贝
public Map<String, Point> getLocations() {
    return Collections.unmodifiableMap(new HashMap<String,Point>(locations));
}

独立的状态变量

还可以将线程安全性委托给多个状态变量，只要这些变量是彼此独立的，即组合而成的类并不会在其包含的多个状态变量上增加任何不变性条件。

// CopyOnWriteArrayList来保存各个监听器列表。它是一个线程安全的链表，特别适用于管理监听器列表。
// 每个链表都是线程安全的，此外，由于各个状态之间不存在耦合关系，因此VisualComponent可以将它的线程安全性委托给mouseListeners和keyListeners等对象。
public class VisualComponent {
    private final List<KeyListener> keyListeners = new CopyOnWriteArrayList<KeyListener>();
    private final List<MouseListener> mouseListeners = new CopyOnWriteArrayList<MouseListener>();
    public void addKeyListener(KeyListener listener) {
        keyListeners.add(listener);
    }
    public void addMouseListener(MouseListener listener) {
        mouseListeners.add(listener);
    }
    public void removeKeyListener(KeyListener listener) {
        keyListeners.remove(listener);
    }
    public void removeMouseListener(MouseListener listener) {
        mouseListeners.remove(listener);
    }
}

委托失效

如果某个类含有复合操作，那么仅靠委托并不足以实现线程安全性。在这种情况下，这个类必须提供自己的加锁机制以保证这些复合操作都是原子操作，除非整个复合操作都可以委托给状态变量。

如果一个类是由多个独立且线程安全的状态变量组成，并且在所有的操作中都不包含无效状态转换，那么可以将线程安全性委托给底层的状态变量。

发布底层的状态变量

如果一个状态变量是线程安全的，并且没有任何不变性条件来约束它的值，在变量的操作上也不存在任何不允许的状态转换，那么就可以安全地发布这个变量。

@ThreadSafe
public class SafePoint {
    @GuardedBy("this")
    private int x, y;
    // 这是私有构造函数捕获模式（Private Constructor Capture Idiom）的一个实例。
    private SafePoint(int[] a) {
        this(a[0], a[1]);
    }
    // 如果将拷贝构造函数实现为this（p.x, p.y），那么会产生竞态条件，而私有构造函数则可以避免这种竞态条件。
    public SafePoint(SafePoint p) {
        this(p.get());
    }
    // get方法同时获得x和y的值，并将二者放在一个数组中返回
    // 如果为x和y分别提供get方法，那么在获得这两个不同坐标的操作之间，x和y的值发生变化，从而导致调用者看到不一致的值
    public SafePoint(int x, int y) {
        this.set(x, y);
    }
    public synchronized int[] get() {
        return new int[]{x, y};
    }
    public synchronized void set(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

// 将其线程安全性委托给底层的ConcurrentHashMap，只是Map中的元素是线程安全的且可变的Point，而并非不可变的。
@ThreadSafe
public class PublishingVehicleTracker {
    private final Map<String, SafePoint> locations;
    private final Map<String, SafePoint> unmodifiableMap;
    public PublishingVehicleTracker(Map<String, SafePoint> locations) {
        this.locations = new ConcurrentHashMap<String, SafePoint>(locations);
        this.unmodifiableMap = Collections.unmodifiableMap(this.locations);
    }
    // getLocation方法返回底层Map对象的一个不可变副本
    // 调用者不能增加或删除车辆，但却可以通过修改返回Map中的SafePoint值来改变车辆的位置
    public Map<String, SafePoint> getLocations() {
        return unmodifiableMap;
    }
    public SafePoint getLocation(String id) {
        return locations.get(id);
    }
    public void setLocation(String id, int x, int y) {
        if (!locations.containsKey(id))
            throw new IllegalArgumentException("invalid vehicle name: " + id);
        locations.get(id).set(x, y);
    }
}

在现有的线程安全类中添加功能

添加代码或者扩展类

• 要添加一个新的原子操作，最安全的方法是修改原始的类，但这通常无法做到，因为你可能无法访问或修改类的源代码。
  • 要想修改原始的类，就需要理解代码中的同步策略，这样增加的功能才能与原有的设计保持一致。如果直接将新方法添加到类中，那么意味着实现同步策略的所有代码仍然处于一个源代码文件中，从而更容易理解与维护。
• 另一种方法是扩展这个类，假定在设计这个类时考虑了可扩展性。
  • “扩展”方法比直接将代码添加到类中更加脆弱，因为现在的同步策略实现被分布到多个单独维护的源代码文件中。
  • 如果底层的类改变了同步策略并选择了不同的锁来保护它的状态变量，那么子类会被破坏，因为在同步策略改变后它无法再使用正确的锁来控制对基类状态的并发访问。

在Vector的规范中定义了它的同步策略，因此BetterVector遵循这个规范就不存在被破坏问题。

@ThreadSafe
public class BetterVector <E> extends Vector<E> {
    static final long serialVersionUID = -3963416950630760754L;
    public synchronized boolean putIfAbsent(E x) {
        boolean absent = !contains(x);
        if (absent) {
            add(x);
        }
        return absent;
    }
}

客户端加锁机制

对于由Collections.synchronizedList封装的ArrayList，这两种方法在原始类中添加一个方法或者对类进行扩展都行不通， 因为客户代码并不知道在同步封装器工厂方法中返回的List对象的类型。
第三种策略是扩展类的功能，但并不是扩展类本身，而是将扩展代码放入一个“辅助类”中。

要想使这个方法能正确执行，必须使实现客户端加锁或外部加锁时使用同一个锁。客户端加锁是指，对于使用某个对象X的客户端代码，使用X本身用于保护其状态的锁来保护这段客户代码。要使用客户端加锁，你必须知道对象X使用的是哪一个锁。

@ThreadSafe
class GoodListHelper<E> {
    public List<E> list = Collections.synchronizedList(new ArrayList<E>());
    public boolean putIfAbsent(E x) {
    	// 使用内部锁对应的this对象，而不是在方法上使用synchronized而使用不同的锁对象
        synchronized (list) {
            boolean absent = !list.contains(x);
            if (absent) {
                list.add(x);
            }
            return absent;
        }
    }
}

• 通过添加一个原子操作来扩展类是脆弱的，因为它将类的加锁代码分布到多个类中。
• 然而，客户端加锁却更加脆弱，因为它将类C的加锁代码放到与C完全无关的其他类中。当在那些并不承诺遵循加锁策略的类上使用客户端加锁时，要特别小心。

客户端加锁机制与扩展类机制有许多共同点，二者都是将派生类的行为与基类的实现耦合在一起。正如扩展会破坏实现的封装性，客户端加锁同样会破坏同步策略的封装性。

组合

当为现有的类添加一个原子操作时，有一种更好的方法：组合（Composition）。ImprovedList通过自身的内置锁增加了一层额外的加锁。

它并不关心底层的List是否是线程安全的，即使List不是线程安全的或者修改了它的加锁实现，ImprovedList也会提供一致的加锁机制来实现线程安全性。虽然额外的同步层可能导致轻微的性能损失（性能损失很小，因为在底层List上的同步不存在竞争，所以速度很快），但与模拟另一个对象的加锁策略相比，ImprovedList更为健壮。
事实上，我们使用了Java监视器模式来封装现有的List，并且只要在类中拥有指向底层List的唯一外部引用，就能确保线程安全性。

public class ImprovedList<T> implements List<T> {
    private final List<T> list;
    // PRE: list argument is thread-safe.
    public ImprovedList(List<T> list) {
        this.list = list;
    }
    public synchronized boolean putIfAbsent(T x) {
        boolean contains = list.contains(x);
        if (contains) {
            list.add(x);
        }
        return !contains;
    }
    //……按照类似的方式委托List的其他方法
}

将同步策略文档化

在文档中说明客户代码需要了解的线程安全性保证，以及代码维护人员需要了解的同步策略。

synchronized、volatile或者任何一个线程安全类都对应于某种同步策略，用于在并发访问时确保数据的完整性。 这种策略是程序设计的要素之一，因此应该将其文档化。当然，设计阶段是编写设计决策文档的最佳时间。

在设计同步策略时需要考虑多个方面：

• 将哪些变量声明为volatile类型
• 哪些变量用锁来保护
• 哪些锁保护哪些变量
• 哪些变量必须是不可变的或者被封闭在线程中的
• 哪些操作必须是原子操作等。

其中某些方面是严格的实现细节，应该将它们文档化以便于日后的维护。还有一些方面会影响类中加锁行为的外在表现，也应该将其作为规范的一部分写入文档。

最起码，应该保证将类中的线程安全性文档化。

• 它是否是线程安全的
• 在执行回调时是否持有一个锁
• 是否有某些特定的锁会影响其行为

不要让客户冒着风险去猜测。如果你不想支持客户端加锁也是可以的，但一定要明确地指出来。

基础构建模块

同步容器类

• 同步容器类包括Vector和Hashtable，二者是早期JDK的一部分
• 此外还包括在JDK l.2中添加的一些功能相似的类，这些同步的封装器类是由Collections.synchronizedXxx等工厂方法创建的
  • 这些类实现线程安全的方式是：将它们的状态封装起来，并对每个公有方法都进行同步，使得每次只有一个线程能访问容器的状态

同步容器类的问题

// 在使用客户端加锁的Vector上的复合操作，使用同一个锁对象
public static Object getLast(Vector list) {
    synchronized (list) {
        int lastIndex = list.size() - 1;
        return list.get(lastIndex);
    }
}

// 带有客户端加锁的迭代
// 这同样会导致其他线程在迭代期间无法访问它，因此降低了并发性。
synchronized (list) {
    for (int i = 0; i < list.size(); i++) {
        doSomething(list.get(i));
    }
}

迭代器与ConcurrentModificationException

如果在迭代期间计数器被修改，那么hasNext或next将抛出ConcurrentModificationException（在单线程代码中也可能抛出ConcurrentModificationException异常。当对象直接从容器中删除而不是通过Iterator.remove来删除时，就会抛出这个异常）。
然而，这种检查是在没有同步的情况下进行的，因此可能会看到失效的计数值，而迭代器可能并没有意识到已经发生了修改。 这是一种设计上的权衡，从而降低并发修改操作的检测代码对程序性能带来的影响。

要想避免出现ConcurrentModificationException，就必须在迭代过程持有容器的锁。

如果容器的规模很大，或者在每个元素上执行操作的时间很长，那么这些线程将长时间等待。 即使不存在饥饿或者死锁等风险，长时间地对容器加锁也会降低程序的可伸缩性。持有锁的时间越长，那么在锁上的竞争就可能越激烈，如果许多线程都在等待锁被释放，那么将极大地降低吞吐量和CPU的利用率

如果不希望在迭代期间对容器加锁，那么一种替代方法就是“克隆”容器，并在副本上进行迭代。 由于副本被封闭在线程内，因此其他线程不会在选代期间对其进行修改，这样就避免了抛出ConcurrentModificationException（在克隆过程中仍然需要对容器加锁）。 在克隆容器时存在显著的性能开销。这种方式的好坏取决于多个因素，包括容器的大小，在每个元素上执行的工作，迭代操作相对于容器其他操作的调用频率，以及在响应时间和吞吐量等方面的需求。

隐藏迭代器

所有这些间接的迭代操作都可能抛出ConcurrentModificationException：

• 容器的toString、hashCode和equals等方法会间接地执行迭代操作，当容器作为另一个容器的元素或键值时，就会出现这种情况。
• 同样，containsAll、removeAll和retainAll等方法，以及把容器作为参数的构造函数，都会对容器进行迭代。

正如封装对象的状态有助于维持不变性条件一样，封装对象的同步机制同样有助于确保实施同步策略。

public class HiddenIterator {
    @GuardedBy("this")
    private final Set<Integer> set = new HashSet<Integer>();
    public synchronized void add(Integer i) {
        set.add(i);
    }
    public synchronized void remove(Integer i) {
        set.remove(i);
    }
    public void addTenThings() {
        Random r = new Random();
        for (int i = 0; i < 10; i++) {
            add(r.nextInt());
        }
        // 这里必须使用同步synchronized(this)，因为会toString会调用Iterator
        System.out.println("DEBUG: added ten elements to " + set);
    }
}

并发容器

通过并发容器来代替同步容器，可以极大地提高伸缩性并降低风险。

同步容器将所有对容器状态的访问都串行化，以实现它们的线程安全性。这种方法的代价是严重降低并发性，当多个线程竞争容器的锁时，吞吐量将严重减低。

Java 5.0提供了多种并发容器类来改进同步容器的性能。

并发容器是针对多个线程并发访问设计的。 在Java 5.0中增加了ConcurrentHashMap，用来替代同步且基于散列的Map，以及CopyOnWriteArrayList，用于在遍历操作为主要操作的情况下代替同步的List。 在新的ConcurrentMap接口中增加了对一些常见复合操作的支持，例如“若没有则添加”、替换以及有条件删除等。

Java 5. 0增加了两种新的容器类型：Queue和BlockingQueue。

Queue用来临时保存一组等待处理的元素。

它提供了几种实现，包括：ConcurrentLinkedQueue，这是一个传统的先进先出队列，以及PriorityQueue，这是一个（非并发的）优先队列。 Queue上的操作不会阻塞，如果队列为空，那么获取元素的操作将返回空值。虽然可以用List来模拟Queue的行为——事实上，正是通过LinkedList来实现Queue的，但还需要一个Queue的类，因为它能去掉List的随机访问需求，从而实现更高效的并发。

BlockingQueue扩展了Queue，增加了可阻塞的插入和获取等操作。 如果队列为空，那么获取元素的操作将一直阻塞，直到队列中出现一个可用的元素。 如果队列已满（对于有界队列来说），那么插入元素的操作将一直阻塞，直到队列中出现可用的空间。在“生产者-消费者”这种设计模式中，阻塞队列是非常有用的。

正如ConcurrentHashMap用于代替基于散列的同步Map, Java 6也引入了ConcurrentSkipListMap和ConcurrentSkipListSet，分别作为同步的SortedMap和SortedSet的并发替代品（例如用synchronizedMap包装的TreeMap或TreeSet）。

ConcurrentHashMap

同步容器类在执行每个操作期间都持有一个锁。

与HashMap一样，ConcurrentHashMap也是一个基于散列的Map，但它使用了一种完全不同的加锁策略来提供更高的并发性和伸缩性。
ConcurrentHashMap并不是将每个方法都在同一个锁上同步并使得每次只能有一个线程访问容器，而是使用一种粒度更细的加锁机制来实现更大程度的共享，这种机制称为分段锁（Lock Striping）。
在这种机制中，任意数量的读取线程可以并发地访问Map，执行读取操作的线程和执行写入操作的线程可以并发地访问Map，并且一定数量的写入线程可以并发地修改Map。 ConcurrentHashMap带来的结果是，在并发访问环境下将实现更高的吞吐量，而在单线程环境中只损失非常小的性能。

ConcurrentHashMap与其他并发容器一起增强了同步容器类：它们提供的迭代器不会抛出ConcurrentModificationException，因此不需要在迭代过程中对容器加锁。
ConcurrentHashMap返回的迭代器具有弱一致性（Weakly Consistent），而并非“及时失败”。 弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有的元素，并可以（但是不保证）在迭代器被构造后将修改操作反映给容器。

尽管有这些改进，但仍然有一些需要权衡的因素。对于一些需要在整个Map上进行计算的方法，例如size和isEmpty，这些方法的语义被略微减弱了以反映容器的并发特性。
由于size返回的结果在计算时可能已经过期了，它实际上只是一个估计值，因此允许size返回一个近似值而不是一个精确值。 虽然这看上去有些令人不安，但事实上size和isEmpty这样的方法在并发环境下的用处很小，因为它们的返回值总在不断变化。 因此，这些操作的需求被弱化了，以换取对其他更重要操作的性能优化，包括get、put、containsKey和remove等。

• 在ConcurrentHashMap中没有实现对Map加锁以提供独占访问。
• 在Hashtable和synchronizedMap中，获得Map的锁能防止其他线程访问这个Map。

在一些不常见的情况中需要这种功能，例如通过原子方式添加一些映射，或者对Map迭代若干次并在此期间保持元素顺序相同。然而，总体来说这种权衡还是合理的，因为并发容器的内容会持续变化。

与Hashtable和synchronizedMap相比，ConcurrentHashMap有着更多的优势以及更少的劣势，因此在大多数情况下，用ConcurrentHashMap来代替同步Map能进一步提高代码的可伸缩性。
只有当应用程序需要加锁Map以进行独占访问(或者需要依赖于同步Map带来的一些其他作用)时，才应该放弃使用ConcurrentHashMap。

额外的原子Map操作

由于ConcurrentHashMap不能被加锁来执行独占访问，因此我们无法使用客户端加锁来创建新的原子操作， 但是，一些常见的复合操作都已经实现为原子操作并且在ConcurrentMap的接口中声明

public interface ConcurrentMap＜K, V＞extends Map＜K, V＞{
	//仅当K没有相应的映射值时才插入
	V putIfAbsent（K key, V value）；
	//仅当K被映射到V时才移除
	boolean remove（K key, V value）；
	//仅当K被映射到oldValue时才替换为newValue
	boolean replace（K key, V oldValue, V newValue）；
	//仅当K被映射到某个值时才替换为newValue
	V replace（K key, V newValue）；
}

CopyOnWriteArrayList

CopyOnWriteArrayList用于替代同步List，在某些情况下它提供了更好的并发性能，并且在迭代期间不需要对容器进行加锁或复制。（类似地，CopyOnWriteArraySet的作用是替代同步Set。）

“写入时复制（Copy-On-Write）”容器的线程安全性在于，只要正确地发布一个事实不可变的对象，那么在访问该对象时就不再需要进一步的同步。在每次修改时，都会创建并重新发布一个新的容器副本，从而实现可变性。
“写入时复制”容器的迭代器保留一个指向底层基础数组的引用，这个数组当前位于迭代器的起始位置，由于它不会被修改，因此在对其进行同步时只需确保数组内容的可见性。 因此，多个线程可以同时对这个容器进行迭代，而不会彼此干扰或者与修改容器的线程相互干扰。
“写入时复制”容器返回的迭代器不会抛出ConcurrentModificationException，并且返回的元素与迭代器创建时的元素完全一致，而不必考虑之后修改操作所带来的影响。

显然，每当修改容器时都会复制底层数组，这需要一定的开销，特别是当容器的规模较大时。仅当迭代操作远远多于修改操作时，才应该使用“写入时复制”容器。
这个准则很好地描述了许多事件通知系统：在分发通知时需要迭代已注册监听器链表，并调用每一个监听器，在大多数情况下，注册和注销事件监听器的操作远少于接收事件通知的操作。

阻塞队列和生产者-消费者模式

在类库中包含了BlockingQueue的多种实现：

• 其中，LinkedBlockingQueue和ArrayBlockingQueue是FIFO队列
  • 二者分别与LinkedList和ArrayList类似，但比同步List拥有更好的并发性能。
• PriorityBlockingQueue是一个按优先级排序的队列，当你希望按照某种顺序而不是FIFO来处理元素时，这个队列将非常有用。
  • 正如其他有序的容器一样，PriorityBlockingQueue既可以根据元素的自然顺序来比较元素（如果它们实现了Comparable方法），也可以使用Comparator来比较。
• 最后一个BlockingQueue实现是SynchronousQueue，实际上它不是一个真正的队列，因为它不会为队列中元素维护存储空间。与其他队列不同的是，它维护一组线程，这些线程在等待着把元素加入或移出队列。
  • 因为SynchronousQueue没有存储功能，因此put和take会一直阻塞，直到有另一个线程已经准备好参与到交付过程中。仅当有足够多的消费者，并且总是有一个消费者准备好获取交付的工作时，才适合使用同步队列。

阻塞队列提供了可阻塞的put和take方法，以及支持定时的offer和poll方法。
如果队列已经满了，那么put方法将阻塞直到有空间可用； 如果队列为空，那么take方法将会阻塞直到有元素可用。
队列可以是有界的也可以是无界的，无界队列永远都不会充满，因此无界队列上的put方法也永远不会阻塞。

生产者-消费者模式能简化开发过程，因为它消除了生产者类和消费者类之间的代码依赖性， 此外，该模式还将生产数据的过程与使用数据的过程解耦开来以简化工作负载的管理，因为这两个过程在处理数据的速率上有所不同。

BlockingQueue简化了生产者-消费者设计的实现过程，它支持任意数量的生产者和消费者。 一种最常见的生产者-消费者设计模式就是线程池与工作队列的组合，在Executor任务执行框架中就体现了这种模式

阻塞队列同样提供了一个offer方法，如果数据项不能被添加到队列中，那么将返回一个失败状态。这样你就能够创建更多灵活的策略来处理负荷过载的情况， 例如减轻负载，将多余的工作项序列化并写入磁盘，减少生产者线程的数量，或者通过某种方式来抑制生产者线程。

在构建高可靠的应用程序时，有界队列是一种强大的资源管理工具：它们能抑制并防止产生过多的工作项，使应用程序在负荷过载的情况下变得更加健壮。

开发人员总会假设消费者处理工作的速率能赶上生产者生成工作项的速率，因此通常不会为工作队列的大小设置边界，但这将导致在之后需要重新设计系统架构。 因此，应该尽早地通过阻塞队列在设计中构建资源管理机制—这件事情做得越早，就越容易。
在许多情况下，阻塞队列能使这项工作更加简单，如果阻塞队列并不完全符合设计需求，那么还可以通过信号量（Semaphore）来创建其他的阻塞数据结构。

生产者-消费者模式同样能带来许多性能优势。生产者和消费者可以并发地执行。如果一个是I/O密集型，另一个是CPU密集型，那么并发执行的吞吐率要高于串行执行的吞吐率。

public class IndexingService {
    private static final int CAPACITY = 1000;
    private static final File POISON = new File("");
    private final IndexerThread consumer = new IndexerThread();
    private final CrawlerThread producer = new CrawlerThread();
    private final BlockingQueue<File> queue;
    private final FileFilter fileFilter;
    private final File root;
    public IndexingService(File root, final FileFilter fileFilter) {
        this.root = root;
        this.queue = new LinkedBlockingQueue<File>(CAPACITY);
        this.fileFilter = new FileFilter() {
            public boolean accept(File f) {
                return f.isDirectory() || fileFilter.accept(f);
            }
        };
    }
    private boolean alreadyIndexed(File f) {
        return false;
    }
    class CrawlerThread extends Thread {
        @Override
        public void run() {
            try {
                crawl(root);
            } catch (InterruptedException e) { /* fall through */
            } finally {
                while (true) {
                    try {
                        queue.put(POISON);
                        break;
                    } catch (InterruptedException e1) { /* retry */
                    }
                }
            }
        }
        private void crawl(File root) throws InterruptedException {
            File[] entries = root.listFiles(fileFilter);
            if (entries != null) {
                for (File entry : entries) {
                    if (entry.isDirectory()) {
                        crawl(entry);
                    } else if (!alreadyIndexed(entry)) {
                        queue.put(entry);
                    }
                }
            }
        }
    }
    class IndexerThread extends Thread {
        @Override
        public void run() {
            try {
                while (true) {
                    File file = queue.take();
                    if (file == POISON) {
                        break;
                    } else {
                        indexFile(file);
                    }
                }
            } catch (InterruptedException ignored) {
            }
        }
        public void indexFile(File file) {
            /*...*/
        }
    }
    public void start() {
        producer.start();
        consumer.start();
    }
    public void stop() {
        producer.interrupt();
    }
    public void awaitTermination() throws InterruptedException {
        consumer.join();
    }
}

串行线程封闭

对于可变对象，生产者-消费者这种设计与阻塞队列一起，促进了串行线程封闭，从而将对象所有权从生产者交付给消费者。 线程封闭对象只能由单个线程拥有，但可以通过安全地发布该对象来“转移”所有权。
在转移所有权后，也只有另一个线程能获得这个对象的访问权限，并且发布对象的线程不会再访问它。 这种安全的发布确保了对象状态对于新的所有者来说是可见的，并且由于最初的所有者不会再访问它，因此对象将被封闭在新的线程中。 新的所有者线程可以对该对象做任意修改，因为它具有独占的访问权。

对象池利用了串行线程封闭，将对象“借给”一个请求线程。只要对象池包含足够的内部同步来安全地发布池中的对象，并且只要客户代码本身不会发布池中的对象，或者在将对象返回给对象池后就不再使用它，那么就可以安全地在线程之间传递所有权。

我们也可以使用其他发布机制来传递可变对象的所有权，但必须确保只有一个线程能接受被转移的对象。阻塞队列简化了这项工作。 除此之外，还可以通过ConcurrentMap的原子方法remove或者AtomicReference的原子方法compareAndSet来完成这项工作。

双端队列与工作密取

Java 6增加了两种容器类型，Deque（发音为“deck”）和BlockingDeque，它们分别对Queue和BlockingQueue进行了扩展。 Deque是一个双端队列，实现了在队列头和队列尾的高效插入和移除。具体实现包括ArrayDeque和LinkedBlockingDeque。

正如阻塞队列适用于生产者-消费者模式，双端队列同样适用于另一种相关模式，即工作密取（Work Stealing）。

• 在生产者-消费者设计中，所有消费者有一个共享的工作队列
• 而在工作密取设计中，每个消费者都有各自的双端队列。

如果一个消费者完成了自己双端队列中的全部工作，那么它可以从其他消费者双端队列末尾秘密地获取工作。 密取工作模式比传统的生产者-消费者模式具有更高的可伸缩性，这是因为工作者线程不会在单个共享的任务队列上发生竞争。 在大多数时候，它们都只是访问自己的双端队列，从而极大地减少了竞争。 当工作者线程需要访问另一个队列时，它会从队列的尾部而不是从头部获取工作，因此进一步降低了队列上的竞争程度。

工作密取非常适用于既是消费者也是生产者问题——当执行某个工作时可能导致出现更多的工作。
当一个工作线程找到新的任务单元时，它会将其放到自己队列的末尾（或者在工作共享设计模式中，放入其他工作者线程的队列中）。当双端队列为空时，它会在另一个线程的队列队尾查找新的任务，从而确保每个线程都保持忙碌状态。
例如，在网页爬虫程序中处理一个页面时，通常会发现有更多的页面需要处理。类似的还有许多搜索图的算法，例如在垃圾回收阶段对堆进行标记，都可以通过工作密取机制来实现高效并行。

阻塞方法与中断方法

线程可能会阻塞或暂停执行，原因有多种：等待I/O操作结束，等待获得一个锁，等待从Thread.sleep方法中醒来，或是等待另一个线程的计算结果。
当线程阻塞时，它通常被挂起，并处于某种阻塞状态（BLOCKED、WAITING或TIMED_WAITING）。
当某个外部事件发生时，线程被置回RUNNABLE状态，并可以再次被调度执行。

中断是一种协作机制。一个线程不能强制其他线程停止正在执行的操作而去执行其他的操作。 当线程A中断B时，A仅仅是要求B在执行到某个可以暂停的地方停止正在执行的操作—前提是如果线程B愿意停止下来。
虽然在API或者语言规范中并没有为中断定义任何特定应用级别的语义，但最常使用中断的情况就是取消某个操作。 方法对中断请求的响应度越高，就越容易及时取消那些执行时间很长的操作。

当在代码中调用了一个将抛出InterruptedException异常的方法时，你自己的方法也就变成了一个阻塞方法，并且必须要处理对中断的响应。对于库代码来说，有两种基本选择：

• 传递InterruptedException
  • 避开这个异常通常是最明智的策略——只需把InterruptedException传递给方法的调用者。传递InterruptedException的方法包括，根本不捕获该异常，或者捕获该异常，然后在执行某种简单的清理工作后再次抛出这个异常。
• 恢复中断
  • 有时候不能抛出InterruptedException，例如当代码是Runnable的一部分时。在这些情况下，必须捕获InterruptedException，并通过调用当前线程上的interrupt方法恢复中断状态，这样在调用栈中更高层的代码将看到引发了一个中断

public class TaskRunnable implements Runnable {
    BlockingQueue<Task> queue;
    public void run() {
        try {
            processTask(queue.take());
        } catch (InterruptedException e) {
            // restore interrupted status
            Thread.currentThread().interrupt();
        }
    }
    void processTask(Task task) {
        // Handle the task
    }
    interface Task {
    }
}

还可以采用一些更复杂的中断处理方法，但上述两种方法已经可以应付大多数情况了。 然而在出现InterruptedException时不应该做的事情是，捕获它但不做出任何响应。 这将使调用栈上更高层的代码无法对中断采取处理措施，因为线程被中断的证据已经丢失。 只有在一种特殊的情况中才能屏蔽中断，即对Thread进行扩展，并且能控制调用栈上所有更高层的代码。

同步工具类

所有的同步工具类都包含一些特定的结构化属性：

它们封装了一些状态，这些状态将决定执行同步工具类的线程是继续执行还是等待，此外还提供了一些方法对状态进行操作，以及另一些方法用于高效地等待同步工具类进入到预期状态。

闭锁和CountDownLatch

闭锁是一种同步工具类，可以延迟线程的进度直到其到达终止状态。

闭锁可以用来确保某些活动直到其他活动都完成后才继续执行，如：

• 确保某个计算在其需要的所有资源都被初始化之后才继续执行
• 确保某个服务在其依赖的所有其他服务都已经启动之后才启动
• 等待直到某个操作的所有参与者都就绪再继续执行

CountDownLatch是一种灵活的闭锁实现，可以在上述各种情况中使用，它可以使一个或多个线程等待一组事件发生。

public class TestHarness {
    public long timeTasks(int nThreads, final Runnable task) throws InterruptedException {
        final CountDownLatch startGate = new CountDownLatch(1);
        final CountDownLatch endGate = new CountDownLatch(nThreads);
        for (int i = 0; i < nThreads; i++) {
            Thread t = new Thread() {
                @Override
                public void run() {
                    try {
                        startGate.await();
                        try {
                            task.run();
                        } finally {
                            endGate.countDown();
                        }
                    } catch (InterruptedException ignored) {
                    }
                }
            };
            t.start();
        }
        long start = System.nanoTime();
        startGate.countDown();
        endGate.await();
        long end = System.nanoTime();
        return end - start;
    }
}

FutureTask

FutureTask也可以做闭锁，它实现了Future语义，表示一种抽象的可生成结果的计算。

FutureTask表示的计算是通过Callable来实现的，相当于一种可生成结果的Runnable，并且可以处于以下3种状态：等待运行（Waiting to run)、正在运行（Running）和运行完成（Completed）。
“执行完成”表示计算的所有可能结束方式，包括正常结束、由于取消而结束和由于异常而结束等。当FutureTask进入完成状态后，它会停止在这个状态上。

Future.get的行为取决于任务的状态，如果任务已经完成，那么get会立即返回结果，否则get将阻塞直到任务进入完成状态，然后返回结果或者抛出异常。
FutureTask将计算结果从执行计算的线程到获取这个结果的线程，而FutureTask的规范确保了这种传递过程能实现结果的安全发布。

FutureTask在Executor框架中表示异步任务，此外还可以用来表示一些时间较长的计算，这些计算可以在使用计算结果之前启动。

// 提前加载稍后要使用的数据
public class Preloader {
    ProductInfo loadProductInfo() throws DataLoadException {
        return null;
    }
    private final FutureTask<ProductInfo> future =
            new FutureTask<ProductInfo>(new Callable<ProductInfo>() {
                public ProductInfo call() throws DataLoadException {
                    return loadProductInfo();
                }
            });
    private final Thread thread = new Thread(future);
    public void start() {
        thread.start();
    }
    public ProductInfo get() throws DataLoadException, InterruptedException {
        try {
            return future.get();
        } catch (ExecutionException e) {
            Throwable cause = e.getCause();
            if (cause instanceof DataLoadException) {
                throw (DataLoadException) cause;
            } else {
                throw LaunderThrowable.launderThrowable(cause);
            }
        }
    }
    interface ProductInfo {}
}
class DataLoadException extends Exception {}

Callable表示的任务可以抛出受检查的或未受检查的异常，并且任何代码都可能抛出一个Error。无论任务代码抛出什么异常，都会被封装到一个ExecutionException中，并在Future.get中被重新抛出。
这将使调用get的代码变得复杂，因为它不仅需要处理可能出现的ExecutionException（以及未检查的CancellationException），而且还由于ExecutionException是作为一个Throwable类返回的，因此处理起来并不容易。

public class LaunderThrowable {
    public static RuntimeException launderThrowable(Throwable t) {
        if (t instanceof RuntimeException) {
        	// 直接抛出给调用者
            return (RuntimeException) t;
        } else if (t instanceof Error) {
        	// 如果是错误直接抛出错误
            throw (Error) t;
        } else {
        	// 非RuntimeException表示这是一个逻辑错误
            throw new IllegalStateException("Not unchecked", t);
        }
    }
}

信号量

计数信号量（Counting Semaphore）用来控制同时访问某个特定资源的操作数量，或者同时执行某个指定操作的数量。计数信号量还可以用来实现某种资源池，或者对容器施加边界。

Semaphore中管理着一组虚拟的许可（permit），许可的初始数量可通过构造函数来指定。在执行操作时可以首先获得许可（只要还有剩余的许可），并在使用以后释放即可。 如果没有许可，那么aquire将阻塞直到有许可（或者直到被中断或者操作超时）。release方法将返回一个许可给信号量。 （在这种实现中不包含真正的许可对象，并且Semaphore也不会将许可与线程关联起来，因此在一个线程中获得的许可可以在另一个线程中释放。可以将acquire操作视为是消费一个许可，而release操作是创建一个许可，Semaphore并不受限于它在创建时的初始许可数量。）

计算信号量的一种简化形式是二值信号量，即初始值为1的Semaphore。二值信号量可以用作互斥体（mutex），并具备不可重入的加锁语义：谁拥有这个唯一的许可，谁就拥有了互斥锁。

// 设置容器边界
public class BoundedHashSet<T> {
    private final Set<T> set;
    private final Semaphore sem;
    public BoundedHashSet(int bound) {
        this.set = Collections.synchronizedSet(new HashSet<T>());
        sem = new Semaphore(bound);
    }
    public boolean add(T o) throws InterruptedException {
        sem.acquire();
        boolean wasAdded = false;
        try {
            wasAdded = set.add(o);
            return wasAdded;
        } finally {
            if (!wasAdded) {
                sem.release();
            }
        }
    }
    public boolean remove(Object o) {
        boolean wasRemoved = set.remove(o);
        if (wasRemoved) {
            sem.release();
        }
        return wasRemoved;
    }
}

栅栏CyclicBarrier和Exchanger

栅栏类似于闭锁，它能阻塞一组线程直到某个事件发生。

栅栏与闭锁的关键区别在于：

所有线程必须同时到达栅栏位置，才能继续执行。闭锁用于等待事件，而栅栏用于等待其他线程。

CyclicBarrier可以使一定数量的参与方反复地在栅栏位置汇集，它在并行迭代算法中非常有用：

这种算法通常将一个问题拆分成为一系列相互独立的自问题。

• 当线程到达栅栏位置时将调用await方法，这个方法将阻塞直到所有的线程到达栅栏位置。
• 如果所有的线程都到达栅栏位置，那么栅栏将打开，此时所有的线程都被释放，而栅栏将被重置一遍下次使用。
• 如果对await方法的调用超时，或者await阻塞的线程被中断，那么栅栏就认为是被打破了，所有阻塞的await都将终止并且抛出BorkenBarrierException。
• 如果成功的通过栅栏，那么await将会为每个线程都返回一个唯一的索引号，我们可以利用这些索引来“选举”产生一个“领导线程”,并在下一次迭代中由该领导线程执行一些特殊的工作。

CycleBarrier还可以使你将一个栅栏操作传递给构造函数，这是一个Runnable，当成功通过栅栏会（在一个子任务线程中）执行它，但在阻塞线程被释放之前是不能执行的。

// 通过CyclicBarrier协调细胞自动衍生系统中的计算
// 将问题分解成一定数量的子问题，为每个子问题分配一个线程来求解，之后再将所有的结果合并起来
public class CellularAutomata {
    private final Board mainBoard;
    private final CyclicBarrier barrier;
    private final Worker[] workers;
    public CellularAutomata(Board board) {
        this.mainBoard = board;
        int count = Runtime.getRuntime().availableProcessors();
        this.barrier = new CyclicBarrier(count,
                new Runnable() {
                    public void run() {
                        mainBoard.commitNewValues();
                    }
                });
        this.workers = new Worker[count];
        for (int i = 0; i < count; i++) {
            workers[i] = new Worker(mainBoard.getSubBoard(count, i));
        }
    }
    private class Worker implements Runnable {
        private final Board board;
        public Worker(Board board) {
            this.board = board;
        }
        public void run() {
            while (!board.hasConverged()) {
                for (int x = 0; x < board.getMaxX(); x++) {
                    for (int y = 0; y < board.getMaxY(); y++) {
                        board.setNewValue(x, y, computeValue(x, y));
                    }
                }
                try {
                    barrier.await();
                } catch (InterruptedException ex) {
                    return;
                } catch (BrokenBarrierException ex) {
                    return;
                }
            }
        }
        private int computeValue(int x, int y) {
            // Compute the new value that goes in (x,y)
            return 0;
        }
    }
    public void start() {
        for (Worker worker : workers) {
            new Thread(worker).start();
        }
        mainBoard.waitForConvergence();
    }
    interface Board {
        int getMaxX();
        int getMaxY();
        int getValue(int x, int y);
        int setNewValue(int x, int y, int value);
        void commitNewValues();
        boolean hasConverged();
        void waitForConvergence();
        Board getSubBoard(int numPartitions, int index);
    }
}

另一种形式的栅栏是Exchanger，它是一种两方（Two-Party）栅栏，各方在栅栏位置上交换数据。当两方执行不对称的操作时，Exchanger会非常有用

当两个线程通过Exchanger交换对象时，这种交换就把这两个对象安全的发布给另一方。

使用同步工具类构造高效且可伸缩的缓存

看上去简单的缓存，可能会将性能瓶颈转变成伸缩性瓶颈，即使缓存是用来提高单线程性能的。

public class Memoizer<A, V> implements Computable<A, V> {
    private final ConcurrentMap<A, Future<V>> cache = new ConcurrentHashMap<A, Future<V>>();
    private final Computable<A, V> c;
    public Memoizer(Computable<A, V> c) {
        this.c = c;
    }
    public V compute(final A arg) throws InterruptedException {
        while (true) {
            Future<V> f = cache.get(arg);
            if (f == null) {
                Callable<V> eval = new Callable<V>() {
                    public V call() throws InterruptedException {
                        return c.compute(arg);
                    }
                };
                FutureTask<V> ft = new FutureTask<V>(eval);
                f = cache.putIfAbsent(arg, ft);
                if (f == null) {
                    f = ft;
                    ft.run();
                }
            }
            try {
                return f.get();
            } catch (CancellationException e) {
                cache.remove(arg, f);
            } catch (ExecutionException e) {
                throw LaunderThrowable.launderThrowable(e.getCause());
            }
        }
    }
}

并发技巧清单

• 可变状态是至关重要的(It’s the mutable state stupid)。
  • 所有问题都可以归结为如何协调对并发状态的访问。可变状态越少就越容易确保线程安全性。
• 尽量将域声明为final类型，除非需要他们是可变的。
• 不可变对象一定是线程安全的
  • 不可变对象能极大的降低并发编程的复杂性。它们更为简单而且安全，可以任意共享而无须使用加锁或者保护性复杂等机制。
• 封装有助于管理复杂性
  • 在编写线程安全的程序时，虽然可以将所有数据都保存在全局变量中，但是不建议这么做？将数据封装在对象中，更易于维护不变性条件：将同步机制封装在对象中，更易于遵循同步策略。
• 用锁来保护每个可变变量
• 当保护同一个不变性条件中所有变量时，要使用同一个锁。
• 在执行复合操作期间，要持有锁。
• 如果从多个线程中访问同一个可变变量时没有同步机制，那么程序会出现问题。
• 不要故作聪明地推断出不需要使用同步。
• 再设计过程中考虑线程安全，或者在文档中明确指出它不是线程安全的。
• 将同步策略文档化。

任务执行

在线程中执行任务

当围绕“任务执行”来设计应用程序结构时，第一步就是要找出清晰的任务边界。
独立有利于实现并发，因为如果存在足够多的处理资源，那么这些独立的任务都可以并行执行。为了在调度与负载均衡等过程中实现更高的灵活性，每项任务还应该表示应用程序的一小部分处理能力。

在理想情况下，各个任务之间是相互独立的：任务不依赖于其他任务的状态、结果或边界效应。

• 在正常的负载下，服务器应用程序应该同时表现出良好的吞吐量和快速的响应性。
• 应用程序提供商希望程序支持尽可能多的用户，从而降低每个每个用户的服务成本，而用户则希望获得尽快的响应。
• 而且，当负荷过载时，应用程序的性能应该是逐渐降低，而不是直接失败。

要实现上述目标，应该选择清晰的任务边界以及明确的任务执行策略。

大多数服务器应用程序都提供了一种自然的任务边界选择方式：以独立的客户请求为边界。
Web服务器、邮件服务器、文件服务器、EJB容器以及数据库服务器等，这些服务器都能通过网络接受远程客户的连接请求。将独立的请求作为任务边界，既可以实现任务的独立性，又可以实现合理的任务规模。

显示地为任务创建线程

主循环都将创建一个新线程来处理请求，而不是在主循环中进行处理。由此可得出3个主要结论：

• 任务处理程序从主线程中分离出来，使得主循环能够更快地重新等待下一个到来的请求。
  • 这使得程序在完成前面的请求之前可以接受新的请求，从而提高响应性。
• 任务可以并行处理，从而能同时服务多个请求。
  • 如果有多个处理器，或者任务由于某种原因被阻塞，例如等待I/O完成，获取锁或者资源可用性等，程序的吞吐量将得到提高。
• 任务处理代码必须是线程安全的，因为当有多个任务时会并发地调用这段代码。

在正常的负载情况下，“为每个任务分配一个线程”的方法能提升串行执行的性能。只要请求的到达率不超出服务器的请求处理能力，那么这种方法可以同时带来更快地响应性和更高的吞吐率。

无限制创建线程的不足

在生产环境中，“为每个任务分配一个线程”这种方法存在一些缺陷，尤其是当需要创建大量的线程时：

• 线程生命周期的开销非常高
  • 线程的创建与销毁并不是没有代价的。根据平台的不同，实际的开销也有所不同，但线程的创建过程都会需要时间，延迟处理的请求，并且需要JVM和操作系统提供一些辅助操作。如果请求的到达率非常高且请求的处理过程是轻量级的，例如大多数服务器应用程序就是这种情况，那么为每个请求创建一个新线程将消耗大量的计算资源。
• 资源消耗
  • 活跃的线程会消耗系统资源，尤其是内存。如果可运行的线程数量多于可用处理器的数量，那么有些线程会消耗系统资源，尤其是内存。如果可运行的线程数量多于可用处理器的数量，那么有些线程将闲置。大量空闲的线程会占用许多内存，给垃圾回收期带来压力，而且大量线程在竞争CPU资源时还将产生其他的性能开销。如果你已经拥有足够多的线程使CPU保持忙碌状态，那么再创建更多地线程反而会降低性能。
• 稳定性
  • 在可创建线程的数量上存在一个限制。这个限制值将随着平台的不同而不同，并且受多个因素制约，包括JVM的启动参数、Thread构造函数中请求的栈大小，以及底层操作系统对线程的限制等。如果破坏了这些限制，那么很可能抛出OutOfMemoryError异常，要想从这种错误中恢复过来是非常危险的，更简单的办法是通过构造程序来避免超出这些限制。

Executor框架

• 串行执行的问题在于其糟糕的响应性和吞吐量
• “为每个任务分配一个线程”的问题在于资源管理的复杂性

java.util.concurrent提供了一种灵活的线程池实现作为Executor框架的一部分

public interface Executor {
    void execute(Runnable command);
}

Executor接口为灵活且强大的异步任务执行框架提供了基础，该框架能支持多重不同类型的任务执行策略。 它提供了一种标准的方法将任务的提交过程与执行过程解耦开来，并用Runnable来表示任务。
Executor的实现还提供了对生命周期的支持，以及统计信息收集、应用程序管理机制和性能监视等机制。

Executor基于生产者—消费者模式，提交任务的操作相当于生产者（生成待完成的工作单元），执行任务的线程则相当于消费者（执行完成这些工作单元）。 如果要在程序中实现一个生产者—消费者的设计，那么最简单的方式通常就是使用Executor。

执行策略

通过将任务的提交与执行解耦开来，从而无须太大的困难就可以为某种类型的任务指定和修改执行策略。在执行策略中定义了任务执行的“What、Where、When、How“等方面，包括：

• 在什么（What）线程中执行任务？
• 任务按照什么（What）顺序执行（FIFO、LIFO、优先级）？
• 有多少个（How Many）任务能并发执行？
• 在队列中有多少个（How Many）任务在等待执行？
• 如果系统由于过载而需要拒绝一个任务，那么应该选择哪一个（Which）任务？另外，如何（How）通知应用程序有任务被拒绝？
• 在执行一个任务之前或之后，应该进行哪些（What）动作？

每当看到下面这种形式的代码时： new Thread(runnable).start() 并且你希望获得一种更灵活的执行策略时，请考虑使用Executor来代替Thread。

线程池Executor

线程池是与工作队列密切相关的，其中在工作队列中保存了所有等待执行的任务。
工作者线程的任务很简单：从工作队列中获取一个任务，执行任务，然后返回线程池并等待下一个任务。

优势：

• 通过重用现有的线程而不是创建新线程，可以在处理多个请求时分摊在线程创建和销毁过程中产生的巨大开销。
• 另一个额外的好处是，当请求到达时，工作线程通常已经存在，因此不会由于等待创建线程而延迟任务的执行，从而延迟任务的执行，从而提高了响应性。
• 通过适当调整线程池的大小，可以创建足够多得线程以便使处理器保持忙碌状态，同时还可以防止过多线程相互竞争资源而使应用程序耗尽内存或失败。

可以通过调用Executors中的静态工厂方法之一来创建一个线程池：

• newFixedThreadPool
  • newFixedThreadPool将创建一个固定长度的线程池，每当提交一个任务时就创建一个线程，直到达到线程池的最大数量，这时线程池的规模将不再变化（如果某个线程由于发生了未预期的Exception而结束，那么线程池会补充一个新的线程）。
• newCachedThreadPool
  • newCachedThreadPool将创建一个可缓存的线程池，如果线程池的当前规模超过了处理需求时，那么将回收空闲的线程，而当需求增加时，则可以添加新的线程，线程池的规模不存在任何限制。
• newSingleThreadExecutor
  • newSingleThreadExecutor是一个单线程的Executor，它创建单个工作者线程来执行任务，如果这个线程异常结束，会创建另一个线程来替代。newSingleThreadExecutor能够确保依照任务在队列中的顺序来串行执行（例如FIFO、LIFO、优先级）。
  • 单线程的Executor还提供了大量的内部同步机制，从而确保了任务执行的任何内存写入操作对于后续任务来说都是可见的，这意味着，即使这个线程会不时地被另一个线程替代，单对象总是可以安全的封闭在“任务线程”中
• newScheduledThreadPool
  • newScheduledThreadPool创建一个固定长度的线程池，而且以延迟或定时的方式来执行任务，类似于Timer。

newFixedThreadPool与newCachedThreadPool两个工厂方法返回通用的ThreadPoolExecutor实例。

通过使用Executor，可以实现各种调优、管理、监视、记录日志、错误报告和其他功能。

参看《Jdk1.5 Executors工厂类来产生线程池》部分

Executor的生命周期

Executor的实现通常会创建线程来执行任务。但JVM只有在所有非守护线程全部终止后才会退出。因此，如果无法正确的关闭Executor，那么JVM将无法结束。

为了解决执行服务的声明周期问题，Executor扩展了ExecutorService接口，添加了一些用于声明周期管理的方法。

public interface ExecutorService extends Executor {
    void shutdown();
    List<Runnable> shutdownNow();
    boolean isShutdown();
    boolean isTerminated();
    boolean awaitTermination(long timeout, TimeUnit unit) throws InterruptedException;
    <T> Future<T> submit(Callable<T> task);
    <T> Future<T> submit(Runnable task, T result);
    Future<?> submit(Runnable task);
    <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks) throws InterruptedException;
    <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks, long timeout, TimeUnit unit) throws InterruptedException;
    <T> T invokeAny(Collection<? extends Callable<T>> tasks) throws InterruptedException, ExecutionException;
    <T> T invokeAny(Collection<? extends Callable<T>> tasks, long timeout, TimeUnit unit) throws InterruptedException, ExecutionException, TimeoutException;
}

ExecutorService的生命周期有3种状态：运行、关闭、已终止。初始创建时处于运行状态。

• shutdown方法将执行平缓的关闭过程
  • 不再接受新的任务，同时等待已经提交的任务执行完成——包括那些还未开始执行的任务
• shutdownNow方法将执行粗暴的关闭过程
  • 它将尝试取消所有运行中的任务，并且不再启动队列中尚未开始的任务

在ExecutorService关闭后提交的任务由拒绝执行处理器RejectedExecutionHandler处理，它会抛弃任务，或者使得execute方法抛出一个未受检的RejectedExecutionException。
等所有任务都完成后，ExecutorService将转入终止状态。可以调用awaitTermination来等待ExecutorService到达终止状态，或者通过调用isTerminated来轮询ExecutorService是否已经终止。
通常在调用awaitTermination后立即调用shutdown，从而产生同步关闭ExecutorService的效果。

public class LifecycleWebServer {
	// guava包ThreadFactoryBuilder
    private ThreadFactory namedThreadFactory = new ThreadFactoryBuilder()
            .setNameFormat("demo-pool-%d").build();
    private ExecutorService exec = new ThreadPoolExecutor(
            5,
            200,
            0L,
            TimeUnit.MILLISECONDS,
            new LinkedBlockingQueue<Runnable>(1024),
            namedThreadFactory,
            new ThreadPoolExecutor.AbortPolicy());
    public void start() throws IOException {
        try (ServerSocket socket = new ServerSocket(80)) {
            while (!exec.isShutdown()) {
                try {
                    final Socket conn = socket.accept();
                    exec.execute(new Runnable() {
                        @Override
                        public void run() {
                            handleRequest(conn);
                        }
                    });
                } catch (RejectedExecutionException e) {
                    if (!exec.isShutdown()) {
                        log("task submission rejected", e);
                    }
                }
            }
        }
    }
    public void stop() {
        exec.shutdown();
    }
    private void log(String msg, Exception e) {
        Logger.getAnonymousLogger().log(Level.WARNING, msg, e);
    }
    void handleRequest(Socket connection) {
        Request req = readRequest(connection);
        if (isShutdownRequest(req)) {
            stop();
        } else {
            dispatchRequest(req);
        }
    }
    private Request readRequest(Socket s) {
        return null;
    }
    private void dispatchRequest(Request r) {}
    private boolean isShutdownRequest(Request r) {
        return false;
    }
    interface Request {}
}

延迟任务与周期任务

Timer类负责管理延迟任务和周期任务。然后，Timer类存在一些缺陷（Timer支持基于绝对时间而不是相对时间的调度机制，因此任务的执行对系统时钟变化很敏感，而ScheduledThreadPoolExecutor只支持基于相对时间的调度），因此应该考虑使用ScheduledThreadPoolExecutor来代替。
可以通过ScheduledThreadPoolExecutor的构造函数或newScheduledThreadPool工厂方法来创建该类对象。

Timer在执行所有定时任务时只会创建一个线程。如果某个任务的执行事件过长，那么将破坏其他TimerTask的定时精确性。
线程池能弥补这个缺陷，它可以提供多个线程来执行延时任务和周期任务。

Timer线程并不捕获异常，如果TimerTask抛出了一个未受检的异常，那么将终止定时线程。 这种情况下，Timer不会恢复线程的运行，而是会错误的认为整个Timer都被取消了。 因此，已经被调度但尚未执行的TimerTask将不会执行，新的任务也不能被调度。（这个问题被称之为“线程泄漏”）

因此在Java5.0之后的版本，将很少使用Timer。

如果要构建自己的调度服务，可以使用DelayQueue，它实现了BlockingQueue，并为ScheduledThreadPoolExecutor提供调度功能。 DelayQueue管理一组Delayed对象。每个Delayed对象都有一个相应的延迟时间：
在DelayQueue中，只有某个元素与气候，才能从DelayQueue中执行take操作。从DelayQueue中返回的对象将根据它们的延迟时间进行排序。

任务执行策略之间的隐性耦合

有些类型的任务需要明确地执行执行策略，包括：

• 依赖性任务：
  • 当线程池中运行任务都是独立的时，我们可以随意地修改池的长度与配置，这不会影响到性能以外的任何事情。
  • 但如果你提交到线程池中的任务依赖于其他的任务，这就会隐式地给执行策略带来了约束。
• 使用线程封闭机制的任务：
  • 与线程池相比，单线程的Executor能够对并发性作出更强的承诺。它们能够确保任务不会并发的执行，使你能够放宽代码对线程安全的要求。
  • 如果将Executor从单线程环境改为线程池环境，那么将失去线程安全性。
• 对响应时间敏感的任务：
  • 如果将一个运行时间长的任务提交给单线程的Executor中，或者将多个运行时间较长的任务提交给一个只包含少量线程的线程池中，那么将降低由该excutor管理的服务响应性。
• 使用ThreadLocal的任务：
  • Threadlocal使每个线程都可以拥有某个变量的一个私有“版本”。然而，只要条件允许，Executor可以自由的重用这些线程。
  • 在标准的Executor实现中，当执行需求较低时将回收空闲线程，而当需求增加时将添加新的线程。
  • 只有当线程本地值得生命周期受限于任务的生命周期时，在线程池的线程中使用Threadlocal才有意义，而在线程池中不应该使用Threadlocal在任务之间传递值。

只有当任务都是同类型并且相互独立时，线程池的性能才能达到最佳。如果将运行时间较长的任务与运行时间较短的任务混合在一起，那么除非线程池很大，否则将可能造成“拥塞”。如果提交的任务依赖于其他任务，那么除非线程池无限大，否则将可能造成死锁。

在一些任务中，需要拥有或排除某种特定的执行策略。
如果某些任务依赖于其它的任务，那么会要求线程池足够大，从而确保它们依赖任务不会被放入等待队列中或被拒绝，而采用线程封闭机制的任务需要串行执行。
通过将这些需求写入文档，将来的代码维护人员就不会由于使用了某种不合适的执行策略而破坏安全性或活跃性。

线程饥饿死锁

在一个线程池中，如果一个任务依赖于其他任务的执行，就可能产生死锁。

• 对应一个单线程话的Executor,一个任务将另一个任务提交到相同的Executor中，并等待新提交的任务的结果，这总会引发死锁。第二个任务滞留在工作队列中，直到第一个任务完成，但是第一个任务不会完成，因为它在等待第二个任务的完成。
• 同样在一个大的线程池中，如果所有线程执行的任务都阻塞在线程池中，等待着仍然处于同一个工作队列中的其他任务，那么会发生同样的问题。

这就是线程饥饿死锁。

public class ThreadDeadlock {
    public static ExecutorService exec = Executors.newSingleThreadExecutor();
    public static class LoadFileTask implements Callable<String> {
        private final String fileName;
        public LoadFileTask(String fileName) {
            this.fileName = fileName;
        }
        @Override
        public String call() throws Exception {
            // Here's where we would actually read the file
            System.out.println("execute");
            return fileName;
        }
    }
    public static class RenderPageTask implements Callable<String> {
        @Override
        public String call() throws Exception {
            Future<String> header, footer;
            header = exec.submit(new LoadFileTask("header.html"));
            footer = exec.submit(new LoadFileTask("footer.html"));
            String page = renderBody();
            // Will deadlock -- task waiting for result of subtask

            return header.get() + page + footer.get();
        }
        private String renderBody() {
            // Here's where we would actually render the page
            return "";
        }
    }
    public static void main(String[] args) throws Exception {
    	// 主任务依赖次要任务，但是没有足够的线程执行次要任务造成饥饿死锁
        Future<String> submit = ThreadDeadlock.exec.submit(new RenderPageTask());
        System.out.println(submit.get());// 一直阻塞
        ThreadDeadlock.exec.shutdown();
        ThreadDeadlock.exec.awaitTermination(10, TimeUnit.SECONDS);
    }
}

运行时间较长的任务

如果任务阻塞时间过长，那么即使不出现死锁，线程池的响应性也会变得糟糕。 执行时间较长的任务不仅会造成线程池堵塞，甚至会增加执行时间较短任务的服务时间。 如果线程池中的数量远小于在稳定状态下执行时间较长任务的数量，那么到最后可能所有线程都会运行这些执行时间较长的任务，从而影响整体的响应性。

缓解这个问题的技术就是限定等待资源的时间，而不是无限制等待。

例如Thraed.join(),BlockingQueue.put()、CountDownLatch.await()等，如果等待超时，可以把任务标识为失败，然后终止任务或将任务重新放回队列以便随后执行。

设值线程池的大小

线程池的理想大小取决于被提交任务的类型以及所部属系统的特性。在系统中一般不固定线程池的大小，而是通过某种配置机制来提供。或者根据Runtime.getRuntime().availableProcessors()来决定。

对于设置线程池的大小我们需要考虑的问题有：

• 机器有多少个CPU？
• 多大内存？
• 任务是计算密集型还是IO密集型？
• 是否需要像JDBC这种稀缺资源？

计算密集型的任务，在拥有N个处理器的系统上，当线程池的大小为N+1时通常能实现最优利用率。

对于IO密集型的任务，由于包括IO和阻塞操作的任务，线程不会一直执行即不会一直用到CPU，所以需要更多的线程，具体的多少得根据一些资源需求和计算公式得到。

线程池大小=CPU个数 CPU期望利用率 (1 + 任务等待时间 / 任务处理时间)

线程等待时间所占比例越高，需要越多线程。
线程CPU时间所占比例越高，需要越少线程。

当然，CPU周期并不是唯一影响线程池大小的资源，还包括内存、文件句柄、套接字句柄和数据库连接等。计算这些资源对线程池的约束条件是更容易的：

计算每个任务对该资源的需求量，然后用该资源的可用总量除以每个任务的需求量，所得结果就是线程池大小的上限。

当任务需要某种通过资源池来管理的资源时，例如数据库连接，那么线程池和资源池的大小将会互相影响。

如果每个任务都需要一个数据库连接，那么连接池的大小就限制了线程池的大小
同样，当线程池中的任务是数据库连接的唯一使用者时，那么线程池的大小又将限制连接池的大小

配置ThreadPoolExecutor

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler)

线程的创建与销毁

线程池的基本大小corePoolSize（池中所保留的线程数量，即使是空闲线程）、最大大小maximumPoolSize（池中允许最大的线程数量）、存活时间keepAliveTime（当线程数大于corePoolSize时，允许多余的空闲线程所等待新任务的最长时间，如果超过个时间将会被停止掉）等因素共同负责线程的创建与销毁。

• 基本大小也就是线程池的目标大小，即在没有任务执行时线程池的大小（在创建ThreadPoolExecutor初期，线程并不会立即启动，而是等到有任务提交时才会启动，除非调用prestartAllCoreThreads），并且只有在工作队列满了的情况下才会创建超出这个数量的线程。
  • 如果线程池中的线程数量等于线程池的基本大小，那么仅当在工作队列已满的情况下ThreadPoolExecutor才会创建新的线程。因此，如果线程池的基本大小为零并且其工作队列有一定的容量，那么当把任务提交给该线程池时，只有当线程池的工作队列被填满后，才会开始执行任务，而这种行为通常不是我们所希望的。
  • 在Java6中，可以通过allowCoreThreadTimeOut来使线程池中的所有线程超时。对于一个大小有限的线程池并且在该线程池中包含了一个工作队列，如果希望和这个线程池在没有任务的情况下能销毁所有的线程，那么可以启用这个特性并将基本大小设置为零。
• 线程池的最大大小表示可同时活动的线程数量的上限。如果某个线程的空闲时间超过了存活时间，那么将被标记为可回收的，并且当线程池的当前大小超过了基本大小时，这个线程将被终止。

ThreadPoolExecutor中的策略：

• newFixedThreadPool工厂方法将线程池的基本大小和最大大小设置为参数中指定的值，而且创建的线程池不会超时。
• newCachedThreadPool工厂方法将线程池的最大大小设置为Integer.MAX_VALUE，而将基本大小设置为零，并将超时时间设置为1分钟，这种方法创建出来的线程池可以被无限扩展，并且当需求降低时会自动收缩。其他形式的线程池可以通过显式地ThreadPoolExecutor构造函数来构造。

管理队列任务

通过一个Runnable和一个链表节点来表现一个等待中的任务，当然比使用线程来表示的开销低很多，但如果客户提交给服务器请求的速率超过了服务器的处理速率，那么仍可能会耗尽资源。
即使请求的平均到达速率很稳定，也仍然会出现请求突增的情况。尽管队列有助于缓解任务的突增问题，但如果任务持续高速地到来，那么最终还是会抑制请求的到达率以避免耗尽内存。甚至在耗尽内存之前，响应性也将随着任务队列的增长而变得越来越糟。

ThreadPoolExecutor允许提供一个BlockingQueue来保存等待执行的任务。基本的任务排队方法由3种：无界队列、有界队列和同步移交。队列的选择与其他的配置参数有关，例如线程池的大小等。

newFixedThreadPool和newSingleThreadPool在默认情况下将使用一个无界的LinkedBlockingQueue。如果所有工作者线程都处于忙碌状态，那么任务将在队列中等候。如果任务持续快速地到达，并且超过了线程池处理它们的速度，那么队列将无限制地增加。

一种更稳妥的资源管理策略是使用有界队列，例如ArrayBlockingQueue、有界的LinkedBlockingQueue、PriorityBlockingQueue。

有界队列有助于避免资源耗尽的情况发生，但它又带来了新的问题：当队列填满后，新的任务该怎么办？

对于非常大的或者无界的线程池，可以通过使用SynchronousQueue来避免任务排队，以及直接将任务从生产者移交给工作者线程。 在newCachedThreadPool工厂方法中就使用了SynchronousQueue。

SynchronousQueue不是一个真正的队列，而是一种在线程之间进行移交的机制。要将一个元素放入SynchronousQueue中，必须有另一个线程正在等待接受这个元素。 如果没有线程正在等待，并且线程池的当前大小小于最大值，那么ThreadPoolExecutor将创建一个新的线程，否则根据饱和策略，这个任务将被拒绝。 使用直接移交将更高效，因为任务会直接移交给执行它的线程，而不是被首先放在队列中，然后由工作者线程从队列中提取该任务。 只有当线程池是无界的活着可以拒绝任务时，SynchronousQueue才有实际价值。

当使用像LinkedBlockingQueue或ArrayBlockingQueue这样的FIFO（先进先出）队列时，任务的执行顺序与它们的到达顺序相同。
如果想进一步控制任务执行顺序，还可以使用PriorityBlockingQueue，这个队列将根据优先级来安排任务。任务的优先级是通过自然顺序或Comparator（如果任务实现了Comparable）来定义的。

对于Executor，newCachedThreadPool工厂方法是一种很好的默认选择，它能提供比固定大小的线程池更好的排队性能（由于SynchronousQueue的高性能）。 当需要限制当前任务的数量以满足资源管理需求时，那么可以选择固定大小的线程池，就像在接受网络客户请求的服务器应用和程序中，如果不进行限制，那么很容易发生过载问题。

只有当任务相互独立时，为线程池或工作队列设置界限才是合理的。

• 如果任务之间存在依赖性，那么有界的线程池或队列就可能导致线程“饥饿”死锁问题。此时应该使用无界的线程池，例如newCachedThreadPool。
• 还有一种可选的配置策略：使用一个受限的线程池，工作队列选用SynchronousQueue，饱和策略选择“调用者运行（Caller-Runs）”策略。

饱和策略

当有界队列被填满后，饱和策略开始发挥作用。（如果某个任务被提交到一个已被关闭的Executor时，也会用到饱和策略。）

ThreadPoolExecutor的饱和策略可以通过调用setRectedExecutionHandler来修改。JDK提供了几种不同的RejectedExecutionHandler实现，每种实现都包含有不同的饱和策略：
AbortPolicy、CallerRunsPolicy、DiscardPolicy和DiscardOldestPolicy。

“中止（Abort）“策略是默认的饱和策略，该策略将抛出未检查的RejectedExecutionException。调用者可以捕获这个异常，然后根据需求编写自己的处理代码。
当新提交的任务无法保存到队列中等待执行时，“抛弃”策略会悄悄抛弃该任务。“抛弃最旧的”策略则会抛弃下一个将被执行的任务，然后尝试重新提交新的任务。
如果工作队列是一个优先队列，那么“抛弃最旧的”策略将导致抛弃优先级最高的任务，因此最好不要将“抛弃最旧的”饱和策略和优先队列放在一起使用。

“调用者运行”策略实现了一种调节机制，该策略既不会抛弃任务，也不会抛出异常，而是将某些任务回退到调用者，从而降低新任务的流量。
它不会在线程池的某个线程中执行新提交的任务，而是在一个调用了execute的线程中执行该任务。
由于执行任务需要一定的时间，因此主线程至少在一段时间内不能提交任何任务，从而使得工作者线程有时间来处理完正在执行的任务。 在这期间，主线程不会调用accept，因此到达的请求将被保存在TCP层的队列中而不是在应用程序的队列中。 如果持续过载，那么TCP层将最终发现它的请求队列被填满，因此同样会开始抛弃请求。 当服务器过载时，这种过载情况会逐渐向外蔓延开来——从线程池到工作队列到应用程序再到TCP层，最终到达客户端，导致服务器在高负载下实现一种平缓的性能降低。

使用Semaphore（信号量）来限制任务的到达率，来阻塞execute。

@ThreadSafe
public class BoundedExecutor {
    private final Executor exec;
    private final Semaphore semaphore;
    public BoundedExecutor(Executor exec, int bound) {
        this.exec = exec;
        this.semaphore = new Semaphore(bound);
    }
    public void submitTask(final Runnable command) throws InterruptedException {
        semaphore.acquire();
        try {
            exec.execute(new Runnable() {
                @Override
                public void run() {
                    try {
                        command.run();
                    } finally {
                        semaphore.release();
                    }
                }
            });
        } catch (RejectedExecutionException e) {
            semaphore.release();
        }
    }
}

线程工厂

默认的线程工厂方法将创建一个新的、非守护的线程，并且不包含特殊的配置信息。通过指定一个线程工厂方法，可以定制线程池的配置信息。

可以使用guava库提供的ThreadFactoryBuilder或者自定义ThreadFactory

private ThreadFactory namedThreadFactory = new ThreadFactoryBuilder()
            .setNameFormat("demo-pool-%d").build();

public class MyThreadFactory implements ThreadFactory {
    private final String poolName;
    public MyThreadFactory(String poolName) {
        this.poolName = poolName;
    }
    @Override
    public Thread newThread(Runnable runnable) {
        return new MyAppThread(runnable, poolName);
    }
}

// 定制了线程名字，设置了UncaughtExceptionHandler，维护了一些统计信息及日志记录
public class MyAppThread extends Thread {
    public static final String DEFAULT_NAME = "MyAppThread";
    private static final AtomicInteger created = new AtomicInteger();
    private static final AtomicInteger alive = new AtomicInteger();
    private static final Logger log = Logger.getAnonymousLogger();
    private static volatile boolean debugLifecycle = false;
    public MyAppThread(Runnable r) {
        this(r, DEFAULT_NAME);
    }
    public MyAppThread(Runnable runnable, String name) {
        super(runnable, name + "-" + created.incrementAndGet());
        setUncaughtExceptionHandler(new Thread.UncaughtExceptionHandler() {
            @Override
            public void uncaughtException(Thread t,
                                          Throwable e) {
                log.log(Level.SEVERE,"UNCAUGHT in thread " + t.getName(), e);
            }
        });
    }
    public static int getThreadsCreated() {
        return created.get();
    }
    public static int getThreadsAlive() {
        return alive.get();
    }
    public static boolean getDebug() {
        return debugLifecycle;
    }
    public static void setDebug(boolean b) {
        debugLifecycle = b;
    }
    @Override
    public void run() {
        // Copy debug flag to ensure consistent value throughout.
        boolean debug = debugLifecycle;
        if (debug) {
            log.log(Level.FINE, "Created " + getName());
        }
        try {
            alive.incrementAndGet();
            super.run();
        } finally {
            alive.decrementAndGet();
            if (debug) {
                log.log(Level.FINE, "Exiting " + getName());
            }
        }
    }
}

如果在应用和程序中需要利用安全策略来控制对某些特殊代码库的访问权限，那么可以通过Executors中的privilegedThreadFactory工厂来定制自己的线程工厂。 通过这种方式创建出来的线程，将与创建privilegedThreadFactory的线程拥有相同的访问权限、AccessControlContext和contextClassLoader。
如果不使用privilegedThreadFactory，线程池创建的线程将从在需要新线程时调用execute或submit的客户端代码中继承访问权限，从而导致令人困惑的安全性异常。

在构造后再定制ThreadPoolExecutor

在Executors中包含一个unconfigurableExecutorService工厂方法，该方法对一个现有的ExecutorService进行包装，使其只暴露出ExecutorService的方法，因此不能对它进行配置。 如果将ExecutorService暴露给不信任的代码，又不希望对其进行修改，就可以通过unconfigurableExecutorService来包装它。

newSingleThreadExecutor返回按这种方式封装的ExecutorService，而不是最初的ThreadPoolExecutor。虽然单线程的Executor实际上被实现为一个只包含唯一线程的线程池，但它同样确保了不会并发地执行任务。如果在代码中增加单线程Executor的线程池大小，那么将破坏它的执行语义。

扩展ThreadPoolExecutor

ThreadPoolExecutor是可扩展的，它提供了几个“钩子”方法可以在子类化中改写：beforeExecute、afterExecute和terminated，这些方法可以用于扩展ThreadPoolExecutor的行为。

在执行任务的线程中将调用beforeExecute和afterExecute等方法，在这些方法中还可以添加日志、计时、监视或统计信息收集的功能。
无论任务是从run中正常返回，还是抛出一个异常而返回，afterExecute都会被调用。（如果任务在完成后带有一个Error，那么就不会调用afterExecute。）
如果beforeExecute抛出了一个RuntimeException，那么任务将不会被执行，并且afterExecute也不会被调用。

在线程池完成关闭操作时地暗涌terminated，也就是所有任务都已经完成并且所有工作者线程也已经关闭后。
terminated可以用来释放Executor在其生命周期里分配的各种资源，此外，还可以执行发送通知、记录日志、或者收集finalize统计信息等操作

public class TimingThreadPool extends ThreadPoolExecutor {
    private final ThreadLocal<Long> startTime = new ThreadLocal<Long>();
    private final Logger logger = Logger.getLogger("TimingThreadPool");
    private final AtomicLong numTasks = new AtomicLong();
    private final AtomicLong totalTime = new AtomicLong();
    public TimingThreadPool() {
        super(1, 1, 0L, TimeUnit.SECONDS, null);
    }
    @Override
    protected void beforeExecute(Thread t, Runnable r) {
        super.beforeExecute(t, r);
        logger.fine(String.format("Thread %s: start %s", t, r));
        startTime.set(System.nanoTime());
    }
    @Override
    protected void afterExecute(Runnable r, Throwable t) {
        try {
            long endTime = System.nanoTime();
            long taskTime = endTime - startTime.get();
            numTasks.incrementAndGet();
            totalTime.addAndGet(taskTime);
            logger.fine(String.format("Thread %s: end %s, time=%dns", t, r, taskTime));
        } finally {
            super.afterExecute(r, t);
        }
    }
    @Override
    protected void terminated() {
        try {
            logger.info(String.format("Terminated: avg time=%dns", totalTime.get() / numTasks.get()));
        } finally {
            super.terminated();
        }
    }
}

递归算法的并行化

当串行循环中的各个迭代操作彼此独立时，并行每个迭代操作执行的工作亮比管理一个新任务带来的开销更多，那么这个串行循环就适合并行化。

public <T> void sequentialRecursive(List<Node<T>> nodes, Collection<T> results) {
    for (Node<T> n : nodes) {
        results.add(n.compute());
        sequentialRecursive(n.getChildren(), results);
    }
}
// 在每个迭代操作中都不需要来自于后续递归迭代的结果
public <T> void parallelRecursive(final Executor exec, List<Node<T>> nodes,
                                  final Collection<T> results) {
    for (final Node<T> n : nodes) {
        exec.execute(new Runnable() {
            @Override
            public void run() {
                results.add(n.compute());
            }
        });
        parallelRecursive(exec, n.getChildren(), results);
    }
}

// 创建一个特定于遍历过程的Executor，并使用shutdown和awaitTermination等方法，等待上面并行运行的结果
public <T> Collection<T> getParallelResults(List<Node<T>> nodes) throws InterruptedException {
    ExecutorService exec = Executors.newCachedThreadPool();
    Queue<T> resultQueue = new ConcurrentLinkedQueue<T>();
    parallelRecursive(exec, nodes, resultQueue);
    exec.shutdown();
    exec.awaitTermination(Long.MAX_VALUE, TimeUnit.SECONDS);
    return resultQueue;
}

谜题框架

谜题定义：包含了一个初始位置，一个目标位置，以及用户判断是否有效移动的规则集
规则集包含两部分：计算从指定位置开始的所有合法移动，以及每次移动的结果位置

// P和M代表位置类和移动类
public interface Puzzle<P, M> {
    P initialPosition();
    boolean isGoal(P position);
    Set<M> legalMoves(P position);
    P move(P position, M move);
}

@Immutable
public class PuzzleNode<P, M> {
    final P pos;
    final M move;
    final PuzzleNode<P, M> prev;
    public PuzzleNode(P pos, M move, PuzzleNode<P, M> prev) {
        this.pos = pos;
        this.move = move;
        this.prev = prev;
    }
    List<M> asMoveList() {
        List<M> solution = new LinkedList<M>();
        for (PuzzleNode<P, M> n = this; n.move != null; n = n.prev) {
            solution.add(0, n.move);
        }
        return solution;
    }
}

// 串行版本的程序执行深度优先搜索，搜索过程受限于栈的大小
// 并发版本执行广度优先搜索，因此不会受栈大小限制
public class ConcurrentPuzzleSolver<P, M> {
    protected final ValueLatch<PuzzleNode<P, M>> solution = new ValueLatch<PuzzleNode<P, M>>();
    private final Puzzle<P, M> puzzle;
    private final ExecutorService exec;
    private final ConcurrentMap<P, Boolean> seen;
    public ConcurrentPuzzleSolver(Puzzle<P, M> puzzle) {
        this.puzzle = puzzle;
        this.exec = initThreadPool();
        this.seen = new ConcurrentHashMap<P, Boolean>();
        if (exec instanceof ThreadPoolExecutor) {
            ThreadPoolExecutor tpe = (ThreadPoolExecutor) exec;
            tpe.setRejectedExecutionHandler(new ThreadPoolExecutor.DiscardPolicy());
        }
    }
    private ExecutorService initThreadPool() {
        return Executors.newCachedThreadPool();
    }
    public List<M> solve() throws InterruptedException {
        try {
            P p = puzzle.initialPosition();
            exec.execute(newTask(p, null, null));
            // block until solution found
            PuzzleNode<P, M> solnPuzzleNode = solution.getValue();
            return (solnPuzzleNode == null) ? null : solnPuzzleNode.asMoveList();
        } finally {
            exec.shutdown();
        }
    }
    protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) {
        return new SolverTask(p, m, n);
    }
    protected class SolverTask extends PuzzleNode<P, M> implements Runnable {
        SolverTask(P pos, M move, PuzzleNode<P, M> prev) {
            super(pos, move, prev);
        }
        @Override
        public void run() {
            if (solution.isSet() || seen.putIfAbsent(pos, true) != null) {
                return; // already solved or seen this position
            }
            if (puzzle.isGoal(pos)) {
                solution.setValue(this);
            } else {
                for (M m : puzzle.legalMoves(pos)) {
                    exec.execute(newTask(puzzle.move(pos, m), m, this));
                }
            }
        }
    }
}