CH11-性能与伸缩
线程主要的目的是提高程序的运行性能。线程可以使程序更加充分的发挥系统的可处理能力，从而提高系统的资源利用率。此外，线程还可以使程序在运行现有任务的情况下立即开始处理新的任务，从而提高系统的响应性。
本章将开始介绍各种分析、监测以及提升并发程序性能的技术。然而，许多提升性能的技术同样会增加复杂性，因此也就增加了在安全性和活跃性上发生失败的风险。更糟糕的是，虽然某些技术的初衷是提升性能，但事实上却与最初的目标背道而驰，或者又带来了其他新的性能问题。虽然我们希望获得更好的性能——提升性能总会令人满意，但始终要把安全性放在第一位。首先要保证程序能正确运行，然后仅当程序的性能需求和测试结果要求程序执行的更快时，才应该设法提高它的运行速度。在设计并发的应用程序时，最重要的考虑因素通常并不是将程序的性能提升至极限。
11.1 对性能的思考
提升性能意味着用更少的资源做更多的事。“资源”的含义很广。对于一个给定的操作，通常会缺乏某种特定的资源，例如 CPU 时钟周期、内存、网络带宽、IO 带宽、数据库请求、磁盘空间等其他资源。当操作性能由于某种特定的资源而受到限制时，我们通常将该操作称为资源密集型的操作，例如，CPU 密集型、数据库密集型等。
尽管使用线程的目标是提升整体性能，但与单线程的方法相比，使用多个线程总会引入一些额外的性能开销。造成这些开销的操作包括：线程之间的协调(例如加锁、触发信号以及内存同步等)，增加的上下文切换，线程的创建和销毁，以及线程的调度等。如果过度的使用线程，那么这些开销甚至会超过由于提升吞吐量、响应性或计算能力带来的性能提升。另一方面，一个并发设计很糟糕的应用程序，其性能甚至比实现相同功能的串行程序的性能还要差。
要想通过并发来获得更好的性能，需要努力做好两件事情：更有效的利用现有处理资源，以及在出现新的处理资源时使程序尽可能的利用这些新资源。从性能监视的视角来看，CPU 需要尽可能保持忙碌状态。(当然，这并不意味着将 CPU 时钟周期浪费在一些无用的计算上，而是执行一些有用的工作)。如果程序是计算密集型的，那么可以通过增加处理器来提升性能。因为如果程序无法使现有的处理器处于忙碌的状态，那么增加再多的处理器也无济于事。通过将应用程序分解到多个线程上执行，使得每个处理器都执行一些工作，从而使所有 CPU 都保持忙碌状态。
11.1.1 性能与可伸缩性
应用的性能可以通过多个指标来衡量，例如服务时间、延迟时间、吞吐率、效率、可伸缩性以及容量等。其中一些指标(服务时间、等待时间)用于衡量程序的“运行速度”，即某个指定的任务单元需要“多快”才能处理完成。另一些指标(生产量、吞吐量)用于程序的“处理能力”，即在计算资源一定的情况下，能完成多少工作。
可伸缩性指的是：当增加计算资源时(如 CPU、内存、存储容量或 IO 带宽)，程序的吞吐量或者处理能力能获得相应的提升。
在并发应用程序中针对可伸缩性进行设计和调整时所采用的方法与传统的性能调优方法截然不同。当进行性能调优时，其目的通常是用更小的代价完成相同的工作，例如通过缓存来重用之前计算的结果，或者采用事件复杂度 O(n^2) 算法来代替复杂度为 O(n log n) 的算法。在进行可伸缩性调优时，其目的是设法将问题进行并行化，从而能利用更多的计算资源来完成更多的任务。
我们熟悉的三层程序模型，即在模型中的表现层、业务逻辑层、持久化层都是彼此独立的，并且可能由不同的系统来处理，这很好的说明了提高可伸缩性通常会造成性能损失的原因。如果把表现层、业务逻辑层和持久化层都融合到单个应用程序汇总，那么在处理第一个工作单元时，其性能肯定要高出将应用分为多个层次并将不同层次划分到多个系统时的性能。这种单一的应用程序避免了在不同层次之间传递任务时存在的网络延迟，同时也不需要将计算过程分解到不同的抽象层次，因此能减少很多开销(如任务排队、线程协调、数据复制)。
然而，当这种单一的系统到达自身处理能力的极限时，会遇到一个严重的问题：要进一步提升它的处理能力将非常困难。因此，我们通常会接受每个工作单元执行更长的时间或消耗更多的计算资源，以换取应用程序在增加更多资源的情况下处理更高的负载。
对于服务器应用程序来说，“多少”这个方面——可伸缩性、吞吐量、生产量，往往比“多快”这个方面更受重视。(在交互式应用程序中，延迟或许更加重要，这样用户就不用等待进度条，并奇怪程序究竟在执行哪些操作)。本章将重点介绍可伸缩性而不是单线程程序的性能。
11.1.2 评估各种性能权衡因素
在几乎所有的工程决策中都会涉及某些形式的权衡。在建设桥梁时，使用更粗的钢筋可以提高桥的负载能力和安全性，但同时也会提高建造成本。尽管在软件工程的决策中通常不会涉及资金以及人身安全，但在做出正确的权衡时通常会缺少相应的信息。例如，“快速排序”算法在大规模数据集上的执行效率非常高，但对于小规模的数据集来说，“冒泡排序”实际上更搞笑。如果要实现一个高效的排序算法，那么就需要知道被处理的数据集的大小，还有衡量优化的指标，包括：平均计算时间、最差时间、可预知性。然而，编写某个库中的排序算法的开发人员通常无法知道这些需求信息。这就是大多数优化措施都不成熟的原因之一：它们通常无法获得一组明确的需求。
避免不成熟的优化。首先使程序正确，然后再提高运行速度——如果它运行的还不够快。
当进行决策时，有时候会通过增加某种形式的成本来降低另一种形式的开销(例如，增加内存使用量以降低服务时间)，也会通过增加开销来换取安全性。安全性并不一定就是指对人身安全的威胁，例如桥梁设计的示例。很多性能优化措施都是以牺牲可读性或可维护性为代价——代码越聪明越晦涩，它们又会带来更高的错误风险，因为通常越快的算法就越复杂。(如果你无法找出其中的代价或风险，那么或许还没有对这些优化措施进行彻底的思考和分析)。
在大多数性能决策中都包含多个变量，并且非常依赖于运行环境。在使某个方案比其他方案更快之前，首先问自己一些问题：
- “更快”的含义是什么？
- 该方法在什么条件写运行的更快？在低负载还是高负载的情况下？多数据集还是小数据集？能否通过测试结果来验证你的答案？
- 这些条件在运行环境中的发生概率？能否通过测试结果来验证你的答案？
- 在其他不同条件的环境中是否能使用这里的代码？
- 在实现这种性能提升时需要付出哪些隐含的代价，例如增加开发风险或维护开销？这种权衡是否合适？
在进行任何与性能相关的决策时，都应该考虑哪些问题，本书只介绍并发性方面的内容。我们为什么要推荐这种保守的方法？对性能的提升可能是并发错误的最大来源。有人认为同步机制太慢，因而采用一些看似聪明实则危险的方法来减少同步的使用(比如 16.2.4 节中讨论的双重检查锁)，这也通常作为不遵守同步规则的一个常见借口。然而，由于并发错误是最难追踪和消除的错误，因此对于任何可能会引入这类错误的措施，都需要谨慎实施。
更糟糕的是，虽然你的初衷可能是用安全性来换取性能，但最终可能什么也得不到。特别是，当提到并发时，许多开发人员对于哪些地方存在性能问题，哪种方法的运行速度更快，以及哪种方法的可伸缩性更好，往往会存在错误的直觉。因此，在对性能进行调优时，一定要有明确的性能需求(这样才能知道什么时候需要调优，以及什么时候应该停止)，此外还需要一个测试程序以及真实的配置和负载均衡等环境。在对性能调优后，你需要再次测量以验证是否达到了预期的性能提升目标。在许多优化措施中带来的安全性和可维护性等风险非常高。如果不是必须的话，你通常不想付出这样的代价，如果无法从这些措施中获得性能提升，那么你肯定不希望付出这种代价。
以测试为基准，不要猜测。
市场上有一些成熟的分析工具可以用于评估性能以及找出性能瓶颈，但你不需要花费太多的资金来找出程序的功能。比如免费的 perfbar 应用可以给出 CPU 的忙碌程度信息，而我们通常的目标是使 CPU 保持忙碌状态，因此这个功能可以有效的评估是否需要进行性能调优或者已经实现的调优效果如何。
11.2 Amdahl 定律
在有些问题中，如果可用资源越多，那么问题的解决速度就越快。例如，如果参与收割庄稼工人越多，那么就能越快的完成收割工作。而有些任务本质上是串行的，例如，即使增加再多的工人也无法增加作物的生长速度。如果使用线程主要是为了发挥多个处理器的处理能力，那么就必须对问题进行合理的并行分解，并使得程序能有效的使用这种潜在的并行能力。
大多数并发程序都与农业耕作有着形似之处，它们都是由一系列的并行工作和串行工作组成的。Amdahl 定律描述的是：在增加计算资源的情况下，程序在理论上就能够实现最高加速比，这个取值取决于程序中可并行组件与串行组件所占的比重。假定 F 是必须被串行的部分，那么根据 Amdahl 定律，在包含 N 个处理器的机器中，最高的加速比为：
当 N 趋近于无穷大时，最大的加速比趋近于 1/F。因此，如果程序有 50% 的计算需要串行执行，那么最高的加速比只能是 2(而无论有多少个线程可用)；如果程序中有 10% 的计算需要串行执行，那么最高的加速比接近于 10。Amdahl 定律还量化了串行化的效率开销。在拥有 10 个处理器的系统中，如果程序中有 10% 的部分需要串行执行，那么最高加速比为 5.3(53%的使用率)，在拥有 100 个处理器的系统中，加速比可以达到 9.2(9%的使用率)。即使拥有无限多个 CPU，加速比也不可能为 10。
图 11-1 给出了处理器利用率在不同串行比例以及处理器数量的情况下的变化曲率。(利用率定义为：加速比除以处理器的数量)。随着处理器数量的增加，可以明显的看到，即使串行部分所占的比例很小，也会极大的限制当增加计算资源时能够提升的吞吐率。
第六章介绍了如何识别任务的逻辑边界并将应用程序分解为多个子任务。然而，要预测应用程序在某个多处理器系统中将实现多大的加速比，还需要找出任务的串行部分。
假设应用程序中 N 个线程正在执行程序清单 11-1 中的 doWork，这些线程从一个共享的工作队列中取出任务并进行处理，而且这里的任务都不依赖于任何其他的执行结果或影响。暂时先不考虑任务是如何进入这个队列的，如果增加处理器，那么应用程序的性能是否会相应的发生变化？初看上去，这个程序似乎能完全并行化：各个任务之间不会互相等待，因此处理器越多，能够并发处理的任务也就越多。然而，在这个过程中包含了一个串行的部分——从队列中获取任务。所有工作者线程都共享同一个工作队列，因此在对该队列进行并发访问时需要采用某种同步机制来维持队列的完整性。如果通过加锁来保护队列的状态，那么当一个线程从队列中取出一个任务时，其他需要获取下一个任务的线程就必须等待，这就是任务处理过程中的串行部分。
public class WorkerThread extends Thread {
private final BlockingQueue<Runnable> queue;
public WorkerThread(BlockingQueue<Runnable> queue) { this.queue = queue;
}
public void run() {
while (true) {
try {
Runnable task = queue.take();
task.run();
} catch (InterruptedException e) {
break; /* Allow thread to exit */
}
}
}
}
单个任务的处理时间不仅包括执行任务 Runnable 的时间，还包括从共享队列中取出任务的时间。如果使用 LinkedBlockingQueue 作为工作队列，那么出列操作被阻塞的可能性将小于使用同步 LinkedList 发生阻塞的可能性，因为 BlockingQueue 使用了一种可伸缩性更高的算法。然而，无论访问何种共享数据结构，基本上都会为程序引入一个串行的部分。
这个示例还忽略了另一种常见的串行操作：对结果进行处理。所有有用的计算都会生成某种结果或产生某种副作用——如果不会，那么可以将它们作为无用代码删除掉。由于 Runnable 没有提供明确的结果处理过程，因此这些任务一定会产生某种副作用，例如将它们的结果写入日志或保存到某个数据结构。通常，日志文件和结果容器都会由多个工作者线程共享，因此这也是串行的一部分。如果所有线程都将各自的计算结果保存到自行维护的数据结构中，并且在所有任务都执行完成后在合并所有结果，那么这种合并操作也是一个串行部分。
在所有并发程序中都包含一些串行部分。
11.2.1 示例：在各种框架中隐藏的串行部分
要想知道串行部分是如何隐藏在应用程序的框架中的，可以比较当增加线程时吞吐量的变化，并根据观察到的可伸缩线变化来推断串行部分中的差异。图 11-2 给出了一个简单的应用程序，其中多个线程反复从一个共享 Queue 中取出元素进行处理，这与程序清单 11-1 很相似。处理步骤只需执行线程本地的计算。如果某个线程发现队列为空，那么他将一个新元素放入队列，因而其他线程在下一次访问时不会出现没有元素可供处理。在访问共享队列的过程中显然存在着一定程度的串行操作，但处理步骤完全可以并行执行，因为它不会访问共享数据。
图 11-2 的曲线对两个线程安全的 Queue 的吞吐率进行了对比：其中一个是采用 synchronizedList 封装的 LinkedList，另一个是 ConcurrentLinkedQueue。这些测试在 8 路 Sparc V880 系统上运行，操作系统为 Solaris。尽管每次运行都表示相同的“工作量”，但我们可以看到，只需要改变队列的实现方式，就能对伸缩性产生明显的影响。
ConcurrentLinkedQueue 的吞吐量不断提升，直到达到处理器的数量上限，之后将基本保持不变。另一方面，当线程数量小于 3 时，同步 LinkedList 的吞吐量也会有某种程度的提升，但是之后会由于同步开销而骤然下跌。当线程数量达到 4 个或 5 个时，竞争将非常激烈，甚至每次访问队列都会在锁上发生竞争，此时的吞吐量主要受到上下文切换的限制。
吞吐量的差异主要来源于两个队列中不同比例的串行部分。同步 LinkedList 采用单个锁来保护整个队列的状态，并且在 offer 和 remover 等方法的调用期间都将持有该锁。ConcurrentLinkedQueue 使用了一种更加复杂的非阻塞队列算法，该算法使用原子引用来更新各个链接指针。在第一个队列中，整个的插入和删除操作都将串行执行，而在第二个队列中，只有对指针的更新操作才需要串行执行。
11.2.2 Amdahl 定律的应用
如果能准确估算出串行部分所占的比例，那么 Amdahl 定律就能量化增加计算资源时的加锁比。虽然要直接测量串行部分的比例非常困难，但即使在不进行测试的情况下该定律仍然是有用的。
因为我们的思维通常会受周围环境的影响，因此很多人都习惯的认为在多处理器系统中会包含 2 个或 4 个处理器，甚至更多，因为这种技术在近年来被广泛使用。但随着多个 CPU 逐渐成为主流，系统可能拥有数百个或者数千个处理器。一些在 4 路系统中看似具有可伸缩性的算法，却可能含有一个隐藏的可伸缩性瓶颈，只是还没有遇到而已。
在评估一个算法时，要考虑算法在数百个或数千个处理器的情况下的性能表现，从而对可能出现的可伸缩性局限有一定程度的认识。例如，在 11.4.2 节或 11.4.3 节中介绍了两种降低所粒度的技术：锁分解(将一个锁分解为两个锁)和锁分段(将一个锁分解为多个锁)。当通过 Amdahl 定律来分析这两项技术时，我们会发现，如果将一个锁分解为两个锁，似乎并不能充分利用多处理器的能力。锁分段技术似乎更有前途，因为分段的数量可随着处理器数量的增加而增加。(当然，性能优化应该考虑实际的性能需求，在某些情况下，应用锁分解就够了)。
11.3 线程引入的开销
单线程程序即不存在线程调度、也不存在同步开销、而且也不需要使用锁来保证数据结构的一致性。在多个线程的调度和协调过程中都需要一定的性能开销：对于为了提升性能而引入的线程来说，并行带来的性能提升必须超过引入线程的开销。
11.3.1 上下文切换
如果主线程是唯一的线程，那么它基本上不会被调度出去。另一方面，如果可运行的线程数大于 CPU 的数量，那么操作系统最终会将某个正在运行的线程调度出来，从而使得其他线程能够使用 CPU。这将导致一次上下文切换，在这个过程中将保存当前运行线程的执行上下文，并将新调度进来的线程的上下文设置为当前上下文。
切换上下文需要一定的开销，而在线程调度过程中需要访问由操作系统和 JVM 共享的数据结构。应用程序、操作系统以及 JVM 都使用一组相同的 CPU。在 JVM 和操作系统的代码中消耗越多的 CPU 时钟周期，应用程序的可用 CPU 时钟周期就越少。但上下文切换的开销并不只是包含 JVM 和操作系统的开销。当一个新的线程被切换进来时，它所需要的数据可能不再当前处理器的本地缓存中，因此上下文切换将导致一些缓存缺失，因而线程在首次调度运行时会更加缓慢。这就是为什么调度器会为每个可运行的线程分配一个最小执行时间，即使有许多其他的线程正在等待执行：它将上下文切换的开销分摊到更多不会中断的执行时间上，从而提高整体的吞吐量(以损失响应性为代价)。
当线程由于等待某个发生竞争的锁而被阻塞时，JVM 通常会将这个线程挂起，并允许它被交换出去。如果线程频繁发生阻塞，那么它们将无法使用完整的调度时间片。在程序中发生越多的阻塞(包括阻塞 IO、等待获取发生竞争的锁、在条件变量上等待)，与 CPU 密集型的程序就会发生越多的上下文切换，从而增加调度开销，并因此而降低吞吐量。(无阻塞算法同样有助于减少上下文切换，详见第 15 章)。
上下文切换的开销会随着平台的不同而变化，然而按照经验来看：在大多数同样的处理器中，上下文切换的开销相当于 5000~10000 个时钟周期，也就是几微秒。
UNIX 系统中的 vmstat 命令和 Windows 系统的 perfmon 工具都能包括上下文切换的次数以及在内核中执行时间所占比例等信息。如果内核占用率较高(超过 10%)，那么通常表示调度活动发生得很频繁，这很可能是由 IO 或竞争锁导致的阻塞引起的。
11.3.2 内存同步
同步操作的性能开销包括多个方面。在 synchronized 和 volatile 提供的可见性保证中可能会使用一些特殊指令，即内存屏障。内存屏障可以刷新缓存，使缓存无效，刷新硬件的写缓冲，以及停止执行管道。内存屏障可能同样会对性能带来间接的影响，因为它们将抑制一些编译器优化操作。在内存屏障中，大多数操作都不能被重排序。
在评估同步操作带来的性能影响时，区分有竞争的同步和无竞争的同步非常重要。synchronized 机制针对无竞争的同步进行了优化(volatile 通常是非竞争的)，而在编写本书时，一个快速通道(Fast-Path)的非竞争同步将消耗 20~250 个时钟周期。虽然非竞争同步的开销不为零，但它对应用程序整体性能的影响微乎其微，而另一种方法不仅会破坏安全性，而且会使你(或后续开发人员)经历非常痛苦的除错过程。
现代的 JVM 能通过优化来去掉一些不会发生竞争的锁，从而减少不必要的同步开销。如果一个锁的对象只能由当前线程访问，那么 JVM 就可以通过优化来去掉这个加锁操作，因为另一个线程无法与当前线程在这个锁上发生同步。比如，JVM 通常都会去掉程序清单 11-2 中的加锁操作。
synchronized (new Object()) {
// some operations
}
一些更加完备的 JVM 会通过逃逸分析来找出不会被发布到堆的对象引用(因此这个对象是线程本地的)。在程序清单 11-3 的 getStoogeNames 中，对 List 的唯一引用就是局部变量 stooges，并且所有封闭在栈中的变量都会自动称为线程本地变量。在 getStoogeNames 的执行过程中，至少会将 Vector 上的锁获取、释放 4 次，每次调用 add 或 toString 时都会执行一次。然而，一个智能的运行时编译器通常会分析这些调用，从而使 stooges 及其内部状态不会益处，因此可以去掉这 4 次对锁的获取操作。
public String getStoogeNames() {
List<String> stooges = new Vector<String>();
stooges.add("Moe");
stooges.add("Larry");
stooges.add("Curly");
return stooges.toString();
}
即使不进行逃逸分析，编译器也可以执行锁粒度粗化操作，即将临近的同步代码块用同一个锁合并起来。在 getStoogeNames 中，如果 JVM 进行锁粗粒度化，那么可能会把 3 个 add 操作和 1 个 toString 调用合并为单个加解锁操作，并采用启发式方法来评估同步代码块中采用同步操作以及指令之间的相对开销。这不仅减少了同步的开销，同时还能使优化器处理更大的代码块，从而实现更进一步的优化。
不要过度担心非竞争同步带来的开销。这个基本的机制已经非常快了，并且 JVM 还能进行额外的优化进一步降低或消除开销。因此，我们应该将优化重点放到那些发生锁竞争的地方。
某个线程中的同步可能会影响其他线程的性能。同步会增加共享内存总线上的通信量，总线的带宽是有限的，并且所有的处理器都将共享这条总线。如果有多个线程竞争同步带宽，那么所有使用了同步的线程都会受到影响。
11.3.3 阻塞
非竞争同步可以完全在 JVM 中进行处理(而不涉及操作系统)，而竞争的同步可能需要操作系统的介入，从而增加开销。当在锁上发生竞争时，竞争失败的线程肯定会阻塞。JVM 在实现阻塞的行为时，可以采用自旋等待(Spin-Waiting，指通过循环不断的尝试获取锁，直到成功)或者通过操作系统挂起被阻塞的线程。这两种方式的效率高低，要取决于上下文切换的开销以及在成功获取锁之前需要等待的时间。如果等待的时间很短，则适合采用自旋等待的方式，而如果等待时间很长，则适合采用线程挂起的方式。有些 JVM 将根据对历史等待时间的分析数据在这两者之间进行选择，但是大多数 JVM 在等待锁时都只是将线程挂起。
当线程无法获取某个锁或者由于在某个条件等待或在 IO 操作上阻塞时，需要被挂起，在这个过程中将包含两次额外的上下文切换，以及所有必要的操作系统操作和缓存操作：被阻塞的线程在其执行时间片还未用完之前就被交换出去，而在随后当要获取的锁或者其他资源可用时，又再次被切换回来。(由于锁竞争而导致锁阻塞时，线程在持有锁时将存在一定的开销：当它释放锁时，必须告诉操作系统恢复运行阻塞的线程)。
11.4 减少锁的竞争
我们已经看到，串行操作会降低可伸缩线，并且上下文切换也会降低性能。在锁上发生竞争时将同时导致这两种问题，因此减少锁的竞争能够提高性能和可伸缩性。
在对由某个独占锁保护的资源进行访问时，将采用串行方式——每次只有一个线程能访问它。当然，我们有很好的理由来使用锁，例如避免数据被破坏，但获得这种安全性是需要付出代价的。如果在锁上持续发生竞争，那么将限制代码的可伸缩性。
在并发程序中，对可伸缩性的最主要威胁就是独占方式的资源锁。
有两个因素将影响在锁上发生竞争的可能性：锁的请求频率，以及每次持有该锁的时间。如果二者的乘积很小，那么大多数获取锁的操作都不会发生竞争，因此在该锁上的竞争不会对可伸缩性造成严重影响。然而，如果在锁上的请求量很高，那么需要获取该锁的线程将被阻塞并等待。在极端情况下，即使仍有大量工作等待完成，处理器也会被闲置。
有三种方式可以降低锁的竞争程度：
- 减少持有锁的时间。
- 降低对锁的请求频率。
- 使用带有协调机制的独占锁，这些机制支持更高的并发性。
11.4.1 缩小锁的范围——“快进快出”
降低发生竞争可能性的一种有效方式就是尽可能缩短锁的持有时间。例如，可以将一些与锁无关的代码移出同步代码块，尤其是那些开销较大的操作，以及可能被阻塞的操作，例如 IO 操作。
我们都知道，如果将一个“高度竞争”的锁持有过长的时间，那么会限制可伸缩性，例如在第二章中介绍的 SynchronizedFactorizer 的示例。如果某个操作持有锁的时间超过 2 毫秒并且所有操作都需要这个锁，那么无论拥有多个个空闲的处理器，吞吐量也不会超过每秒 500 个操作。如果将这个锁的持有时间降低为 1 毫秒，那么能够将这个锁对应的吞吐量提高到每秒 1000 个操作。
程序清单 11-4 给出了一个示例，其中锁被持有过长的时间。userLocationMatches 方法在一个 Map 对象中查找用户的位置，并使用正则表达式进行匹配以判断结果值是否匹配所提供的模式。整个 userLocationMatches 方法都是用了 synchronized 来修饰，但只有 Map.get 这个调用才真正需要锁。
@ThreadSafe public class AttributeStore {
@GuardedBy("this")
private final Map<String, String> attributes =
new HashMap<String, String>();
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);
}
}
在程序清单 11-5 的 BetterAttributeStore 中重新编写了 AttributeStore，从而大大降低了锁的持有时间。第一个步骤是构建 Map 中与用户位置相关联的键值，这是一个字符串，形式为 user.name.location。这个步骤还包括实例化一个 StringBuilder 对象，向其添加几个字符串，并将结果转化为一个 String 对象。在获得了位置之后，就可以将正则表达式与位置字符串进行匹配。由于在构建键值字符串以及处理正则表达式等过程中不需要访问共享状态，因此在执行时不需要持有锁。通过 BetterAttributeStore 中将这些步骤提取出来并放到同步代码块之外，从而减少了锁被持有的时间。
@ThreadSafe public class BetterAttributeStore {
@GuardedBy("this")
private final Map<String, String> attributes =
new HashMap<String, String>();
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);
}
}
通过缩小 userLocationMatches 方法中所的作用范围，能极大的减少在持有锁时需要执行的指令数量。根据 Amdahl 定律，这样消除了限制可伸缩性的一个因素，因为串行代码的总量减少了。
由于 AttributeStore 中只有一个状态变量 attributes，因此可以通过将线程安全性委托给其他的类来进一步提升它的性能。通过使用线程安全的 Map 来代替 attributes，AttributeStore 可以将确保线程安全性为任务委托给顶层的线程安全容器来实现，这样就无需在 AttributeStore 中采用显式锁的同步，缩小在访问 Map 期间锁的范围，并降低了将来的代码维护者无意破坏线程安全性的风险(比如在访问 attributes 之前忘记获得对应的锁)。
尽管缩小同步代码块能够提高可伸缩性，但同步代码块也不能过小——一些采用原子方式执行的操作(如对某个不变性条件中的多个变量进行更新)必须包含在一个同步块中。此外，同步需要获得一定的开销，当把一个同步块分解为多个同步块代码块时(在确保正确性的情况下)，反而会对性能提升产生负面的影响。在分解同步代码时，理想的平衡点将与平台相关，但在实际情况中，仅当可以将一些“大量”的计算或阻塞操作作为同步代码块中移出时，才应该考虑同步代码块的大小。
11.4.2 减小锁的粒度
另一种减少锁持有时间的方式是降低线程请求锁的频率(从而减少发生竞争的可能性)。这可以通过锁分解和锁分段技术来实现，在这些技术中将采用多个互相独立的锁来保护独立的状态变量，从而改变这些变量在之前由单个变量来保护的情况。这些技术能减少锁操作的粒度，并能实现更高的可伸缩性，然而，使用的锁越多，发生死锁的风险也越高。
设想一下，如果在整个应用中只有一个锁，而不是为每个对象分配一个独立的锁，那么，所有同步代码块的执行就会变成串行化执行，而不考虑各个同步块中的锁。由于很多线程将竞争同一个全局锁，因此两个线程同时请求这个锁的概率将剧增，从而导致更严重的竞争。所以如果将这些锁请求分布到更多的锁上，那么能有效的降低竞争程度。由于等待锁而被阻塞的线程将更少，因此可伸缩性将提高。
如果一个锁需要保护多个相互独立的状态变量，那么可以将这个锁分解为多个锁，并且每个锁仅保护一个变量，从而提高可伸缩性，并最终降低每个锁被请求的频率。
在程序清单 11-6 的 ServerStatus 中给出了某个数据库服务器的部分监视接口，该数据库维护了当前已登录的用户以及正在执行的请求。当一个用户登录、注销、开始查询或结束查询时，都会调用对应的 add 和 remove 方法来更新 ServerStatus 对象。这两种类型的信息是完全独立的，ServerStatus 甚至可以被分解为两个类，同时确保不会丢失功能。
@ThreadSafe public class ServerStatus {
@GuardedBy("this")
public final Set<String> users;
@GuardedBy("this")
public final Set<String> queries;
...
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);
}
}
在代码中不是用 ServerStatus 锁来保护用户状态和查询状态，而是每个状态都通过一个锁来保护，如程序清单 11-7 所示。在对锁进行分解后，每个新的粒度锁上的访问量将比最初的访问量少。(通过将用户状态和查询状态委托给一个线程安全的 Set，而不是使用显式的同步，能隐含的对锁进行分解，因为每个 Set 都会使用一个不同的锁来保护其状态。)
@ThreadSafe public class ServerStatus {
@GuardedBy("users") public final Set<String> users;
@GuardedBy("queries") public final Set<String> queries;
...
public void addUser(String u) {
synchronized (users) {
users.add(u);
}
}
public void addQuery(String q) {
synchronized (queries) {
queries.add(q);
}
}
// remove methods similarly refactored to use split locks
}
如果在锁上存在适中而非激烈的竞争时，通过将一个锁分解为两个锁，能最大限度的提升性能。如果对竞争并不激烈的锁进行分解，那么在性能和吞吐量等方面带来的提升将非常有限，但是也会提高性能随着竞争提高而下降的拐点。对竞争适中的锁进行分解时，实际上是把这些锁转变为非竞争的锁，从而有效的提高性能和可伸缩性。
11.4.3 锁分段
把一个竞争激烈的锁分解为两个锁时，这两个锁可能都存在激烈的竞争。虽然采用两个线程并发执行能提高一部分性能，但是在一个拥有多个处理器的系统中，仍然无法给可伸缩性带来极大的提高。在 ServerStatus 类的锁分解实例中，并不能进一步多锁进行分解。
在某些情况下，可以将锁分解技术进一步扩展为对一组独立对象上的锁进行分解，这种情况被称为锁分段。例如，在 ConcurrentHashMap 的实现中使用了一个包含 16 的锁的数组，每个锁保护所有散列通的 1/16，其中第 N 个散列桶由第 (N mod 16) 个锁来保护。假设散列函数具有合理的分布性，并且关键字能够实现均匀分布，那么这大约能把对于锁的请求减少到原来的 1/16。这是这项技术使得 ConcurrentHashMap 能够支持多达 16 个并发的写入器。(要使得拥有大量处理器的系统在高访问量的情况下实现更高的并发性，还可以进一步增加锁的数量，但仅当你能证明并发写入线程的竞争足够激烈并需要突破这个限制时，才能将锁分段的数量超过默认的 16 个。)
锁分段的一个劣势在于：与采用单个锁来实现的独占性相比，要获取多个锁来实现独占访问将更加困难并且开销更高。通常，在执行一个操作时最多只需获取一个锁，但在某些情况下需要对整个容器加锁，例如当 ConcurrentHashMap 需要扩展容器映射范围时，以及重新计算键值的散列值要分布到更大的桶集合中时，就需要获取分段分段锁集合中所有的锁。
在程序清单 11-8 的 StripedMap 中给出了基于散列的 Map 实现，其中使用了锁分段技术。它拥有 N_LOCKS 个锁，并且每个锁保护散列桶的一个子集。大多数方法，例如 get，都只需要获得一个锁，而有些方法则需要获得所有的锁，但并不要求同时获得，例如 clear 方法的实现。
@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;
private static class Node { ... }
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;
}
}
}
...
}
11.4.4 避免热点域
锁分解和锁分段技术都能提高可伸缩性，因为它们都能使不同的线程在不同的数据(或者同一个数据的不同部分)上操作，而不会互相干扰。如果程序采用锁分段技术，那么一定要表现出在锁上的竞争频率高于在锁保护的数据上发生竞争的频率。如果一个锁保护两个独立变量 X 和 Y，并且线程 A 想要访问 X，而线程 B 想要访问 Y(这类似于在 ServerStatus 中，一个线程调用 addUser，而另一个线程调用 addQuery)，那么这两个线程不会在任何数据上发生竞争，即使它们会在同一个锁上发生竞争。
当每个操作都访问多个变量时，锁的粒度将很难降低。这是在性能和可伸缩性之间相互制衡的另一个方面，一些常见的优化措施，例如将一些反复计算的结果缓存起来，都会引入一些“热点域(Hot Field)”，而这些热点域往往会限制可伸缩性。
当实现 HashMap 时，你需要考虑如何在 size 方法中计算 Map 中的元素数量。最简单的方法就是，在每次调用时都统计一次元素的数量。一种常见的优化措施是，在插入和移除元素时更新一个计数器，虽然这在 put 和 remove 等方法中略微增加了一些开销，以确保计数器是最新的值，但这将 size 方法的开销从 O(n) 降低到了 O(1)。
在单线程或采用完全同步的实现中，使用一个独立的就计数能很好的提高类似 size 和 isEmpty 这些方法的执行速度，但却导致更加难以提升实现的可伸缩性，因为每个修改 Map 的操作都需要跟新这个计数器。即使使用锁分段即使来实现散列链，那么在对计数器的访问进行同步时，也会重新导致在使用独占锁时存在的可伸缩性问题。一个看似性能优化的措施——缓存 size 操作的结果，已经变成了一个可伸缩性问题。在这种情况下，计数器也被称为热点域，因为每个导致元素数量发生变化的操作都需要访问它。
为了避免该问题，ConcurrentHashMap 中的 size 将对每个分段进行枚举并将每个分段中的元素数量增加，而不是维护一个全局计数。为了避免枚举每个元素，ConcurrentHashMap 为每个分段都维护了一个独立的计数，并通过每个分段的锁来维护这个值。
11.4.5 一些替代独占锁的方法
第三种降低竞争锁的影响的技术就是放弃独占所，从而有助于使用一种友好并发的方式来管理共享状态。例如，使用并发容器、读-写锁、不可变对象以及原子变量。
ReadWriteLock 实现了一种在多个读取操作以及单个写入操作情况下的加锁规则：如果有多个读取操作都不会修改共享资源，那么这些读操作可以同时访问该共享资源，但在执行写入操作时必须以独占的方式来获取锁，对于读取操作占多数的数据结构，ReadWriteLock 能够提供比独占锁更高的并发性。而对于只读的数据结构，其中包含的不可变性可以完全不需要加锁操作。
源自变量提供了一种方式来降低更新“热点域”时的开销，例如静态计数器、序列生成器、或者对链表数据结构中头节点的引用。原子变量类提供了在整数或对象引用上的细粒度原子操作(因此可伸缩性更高)，并使用了现代处理器中提供的底层并发原语(比如 CAS)。如果在类中只包含少量的热点域，并且这些域不会与其他变量参与到不变性条件中，那么用原子变量来代替它们提高可伸缩性。(通过减少算法中的热点域，可以提高可伸缩性——虽然原子变量能降低热点域的更新开销，但并不能完全消除。)
11.4.6 检测 CPU 的利用率
当测试可伸缩性时，通常要确保处理器得到充分利用。一些工具，例如 UNIX 系统上的 vastat 和 mpstat，或者 Windows 系统的 perfmon，都能给出处理器的忙碌状态。
如果所有 CPU 的利用率并不均匀(有些 CPU 在忙碌的运行，而其他 CPU 却并非如此)。那么你的首要目标就是进一步找出程序中的并行性。不均匀的利用率表名大多数计算都是由一小组线程完成的，并且应用程序没有利用上其他的处理器。
如果 CPU 没有得到充分的利用，那么需要找出其中的原因，通常有以下几种原因：
负载不充足。测试的程序中可能没有足够的负载，因而可以在测试时增加负载，并检查利用率、响应时间和服务时间等指标的变化。如果产生足够多的负载使应用程序达到饱和，那么可能需要大量的计算机能耗，并且问题可能在于客户端系统是否具有足够的能力，而不是被测试的系统。
IO 密集。可以通过 iostat 或 perfmon 来判断某个应用程序是否是磁盘 IO 密集型的，或者通过监控网络的通信流量级别来判断它是否需要高带宽。
外部限制。如果应用程序依赖于外部服务，例如数据库或者 Web 服务，那么性能瓶颈可能并不在你自己的代码中。可以使用某个分析工具或数据库管理工具来判断在等待外部的结果时需要的时间。
锁竞争。使用分析工具可以知道在程序中存在何种程度的锁竞争，以及在哪些锁上存在“激烈的竞争”。然而，也可以通过其他一些方式来获得相同的信息，例如随机取样，触发一些线程转储并在其中查找在锁上发生竞争的线程。如果线程由于等待某个锁而被阻塞，那么在线程转储信息中将存在相应的栈帧，其中包含的信息形如“waiting to lock monitor…”。非竞争的锁很少会出现在线程转储中，而对于竞争激烈的锁，通常至少会有一个线程正在等待获取它，因此将在线程转储中频繁的出现。
如果应用程序正在使 CPU 保持忙碌的状态，那么可以使用检测工具来判断是否能通过增加额外的 CPU 来提升程序的性能。如果一个程序只有 4 个线程，那么可以充分利用一个 4 路系统的计算能力，但当移植到 8 路系统上时，却未必能获得性能提升，因为可能需要更多的线程才会有效利用剩余的处理器。(可以通过重新配置程序将负载分配给更多的线程，例如调整线程池的大小)。在 vmstat 命令的输出中，有一栏信息是当前处于可运行状态但并没有运行(由于没有足够的 CPU)的线程数量。如果 CPU 的利用率很高，并且总会有可运行的线程在等待 CPU，那么当增加更多的处理器时，程序的性能可能会得到提升。
11.4.7 向对象池说“不”
在 JVM 早期的版本中，对象分配和垃圾回收等操作的执行速度非常慢，但在后续的版本中，这些操作的性能得到了很大的提升。事实上，现在 Java 的分配操作已经比 C 语言的 malloc 调用更快：在 HotSpot 1.4.x 和 5.0 中，“new Object”的代码大约包含 10 条机器指令。
为了解决“缓慢的”对象生命周期问题，许多开发人员都选择使用对象池技术，在对象池中，对象能够被循环使用，而不是由垃圾收集器回收并在需要时再重新分配。在单线程程序中，尽管对象池技术能降低垃圾收集器的开销，但对于高开销对象以外的其他对象来说，仍然存在性能缺失(对于轻量级和中量级的对象来说，这种损失更为严重)。
在并发应用程序中，对象池的表现更加糟糕。当线程分配新的对象时，基本上不需要在线程之间进行协调，因为对象分配器通常会使用线程本地的内存块，所以不需要在堆数据结构上进行同步。然而，如果这些线程从对象池中请求一个对象，那么久需要通过某种同步来协调对对象池数据结构的访问，从而可能使某个线程被阻塞。如果某个线程由于锁竞争而被阻塞，那么这种阻塞的开销将是内存分配操作开销的数百倍，因此即使对象池带来的竞争很小，也可能形成一个可伸缩的性能瓶颈。(即使是一个非竞争同步，所导致的开销也会被分配一个对象的开销大)。虽然这看上去是一种性能优化技术，但实际上却会导致可伸缩性问题。对象池有其特定的用途，但对于性能优化来说，用途是有限的。
通常，对象分配操作的开销比同步的开销更低。
11.5 示例：比较 Map 的性能
在单线程环境下，ConcurrentHashMap 的性能比同步的 HashMap 的性能略好一些，但在并发环境中则要好的多。在 ConcurrentHashMap 的实现中假设，大多数常用的操作都是获取某个已经存在的值，因此它对各种 get 操作进行了优化从而提高性能和并发性。
在同步 Map 的实现中，可伸缩性的最主要阻碍在于整个 Map 中只有一个锁，因此每次只有一个线程能能够访问这个 Map。不同的是，ConcurrentHashMap 对于大多数读操作都不会加锁，并且在写入操作以及其他一些需要锁的读操作中使用了锁分段技术。因此，多个线程能并发的访问这个 Map 而不会发生阻塞。
图 11-3 给出了几种 Map 实现在可伸缩性上的差异：ConcurrentHashMap、ConcurrentSkipListMap，以及通过 synchronizedMap 来包装的 HashMap 和 TreeMap。前两种 Map 是线程安全的，而后两个 Map 则通过同步封装器来确保线程安全性。每次运行时，将有 N 个线程并发的执行一个紧凑的循环：选择一个随机的键值，并尝试获取与这个键值相对应的值。如果不存在相应的值，那么将这个值增加到 Map 的概率为 p=0.6，如果存在相应的值，那么删除这个值的概率为 p=0.02。这个测试在 8路 Sparc V880 系统上运行，基于 Java 6 环境，并且在图中给出了将 ConcurrentHashMap 归一化为单个线程时的吞吐量。(并发容器与同步容器在可伸缩性上的差异比在 Java 5.0 中更明显)。
ConcurrentHashMap 和 ConcurrentSkipListMap 的数据显示，它们在线程数量增加时能表现出更好的可伸缩性，并且吞吐量会随着线程的增加而增加。虽然图 11-3 中的线程数量并不大，但与普通的应用程序相比，这个测试程序在每个线程上生成更多的竞争，因为它除了向 Map 施加压力以外几乎没有执行任何其他操作，而实际的应用程序通常会在每次迭代中进行一些线程本地工作。
同步容器的数量并非越多越好。单线程情况下的性能与 ConcurrentHashMap 的性能基本相当，但当负载情况由于非竞争性转变为竞争性时——这里是两个线程，同步容器的性能将变得非常糟糕。在伸缩性收到锁竞争限制的代码中，这种情况很常见。只要竞争程度不高，那么每个操作消耗的时间基本上即使实执行工作的时间，并且吞吐量会因为线程数的增加而增加。当竞争变得激烈时，每个操作消耗的时间大部分都用于上下文切换和调度延迟，而再加入更多的线程也不会提高太多的吞吐量。
11.6 减少上下文切换的开销
在许多人物中都包含一些可能被阻塞的操作。当任务在运行和阻塞这连个状态之间转换时，就相当于一次上下文切换。在服务器应用中，发生阻塞的原因之一就是在处理请求时产生各种日志消息。为了说明如何通过减少上下文切换的次数来提高吞吐量，我们将对两种日志方法的调度行为进行分析。
在大多数日志框架中都是简单的对 println 进行包装，但需要记录某个消息时，只需要将其写入日志文件。在第七章中的 LogWriter 中给出了另一种方法：记录日志的工作由一个专门的后台线程完成，而不是由发出请求的线程。从开发人员的角度来看，这两种方法基本上是相同的。但二者在性能上可能存在一些差异，这取决于日志操作的工作量，即有多少线程正在记录日志，以及其他一些因素，例如上下文切换的开销等。
日志操作的服务时间包括与 IO 流类相关的计算时间，如果 IO 操作被阻塞，那么还会包括线程被阻塞的时间。操作系统将这个被阻塞的线程从调度队列中移出并直到 IO 操作结束，这将比实际阻塞的时间更长。当 IO 操作结束时，可能有其他线程正在执行它们的带哦度时间片，并且在调度队列中有些线程位于被阻塞线程之前，从而进一步增加服务时间。如果有多个线程在同时记录日志，那么还可能在输出流上的锁上发生竞争，这种情况的结果与阻塞 IO 的情况一样——线程被阻塞并等待锁，然后被线程调度器调度出去。在这种日志操作中包含了 IO 操作和加锁操作，从而导致上下文切换次数的增多，以及服务时间的增加。
请求服务的时间不应该过长，主要有以下原因。首先，服务时间将影响服务质量：服务时间越长，就意味着有程序在获得结果时需要等待更多的时间。但更重要的是，服务是将越长，也就意味着存在越多的锁竞争。11.4.1 节中的“快进快出”原则告诉我们，锁被持有的时间应该尽可能的短，因为锁的持有时间越长，那么在这个锁上发生竞争的可能性就越大。如果一个线程由于等待 IO 操作完成而被阻塞，同时它还持有一个锁，那么在这期间很可能会有另一个线程想要获得这个锁。如果在大多数的锁获取操作上不存在竞争，那么并发系统就能执行得更好，因为在锁获取操作上发生竞争时将导致更多的上下文切换。在代码中造成的上下文切换次数越多，吞吐量就越低。
通过将 IO 操作从处理请求的线程分离出来，可以缩短处理请求的平均服务时间。调用 log 方法的线程将不会再因为等待输出流的锁或者 IO 完成而被阻塞，它们只需要将消息放入队列，然后就返回到各自的任务中。另一方面，虽然在消息队列上可能发生竞争，但 put 操作相对于记录日志的 IO 操作(可能需要执行系统调用)是一种更为轻量级的操作，因此在实际使用中发生阻塞的概率更小(只要队列未满)。由于发出日志请求的线程现在被阻塞的概率降低，因此该线程在处理请求时被交换出去的概率也会降低。我们所做的工作就是把一条包含 IO 操作和锁竞争的复杂且不确定的代码路径变成一条简单的代码路径。
从某种意义上讲，我们只是将工作分散开来，并将 IO 操作移到了另一个用户感知不到开销的线程上(这本身就已经获得了成功)。通过把所有记录日志的 IO 转移到一个线程，还消除了输出流上的竞争，因去掉了一个竞争来源。这将提升整体的吞吐量，因为在调度中消耗的资源更少，上下文切换次数更少，并且锁的管理也更简单。
通过把 IO 操作从处理请求的线程转移到一个专门的线程，类似于两种不同救火方案之间的差异：第一种方案是所有人排成一队，通过传递水桶来救火；第二种方案是每个人都拿着一个水桶去救火。在第二种方案中，每个人都可能在水源点和着火点上存在很大的竞争(结果导致了只能将更少的水传递到着火点)，此外救火的效率也更低，因为每个人都在不停的切换模式(装水、跑步、倒水、跑步…)。在第一种方案中，水不断的从水源传递到燃烧的建筑物，人么付出更少的体力却传递了更多的水，并且每个人从头到尾只需要做一项工作。正如中断会干扰人们的工作并降低效率一样，阻塞和上下文切换同样会干扰线程的正常执行。
小结
由于使用线程常常是为了充分利用多个处理器的计算能力，因此在并发程序性能的讨论中，通常更多的将侧重点放在吞吐量和可伸缩性上，而不是服务时间。Amdahl 定律告诉我们，程序的可伸缩性取决于在所有代码中必须被串行执行的代码的比例。因为 Java 程序中串行执行的主要来源是独占方式的资源锁，因此通常可以通过以下方式来提升伸缩性：减少锁的持有时间、降低锁的粒度、以及采用非独占的锁或者非阻塞锁来代替独占锁。
Feedback
Was this page helpful?
Glad to hear it! Please tell us how we can improve.
Sorry to hear that. Please tell us how we can improve.