详情
本书介绍如何编写或者设计、调试、维护、研究多线程C++程序，并提供了技术模式和工具，可以用来分析并发编程以及降低封装并发交互的复杂性。书中还提供了大量的实例、练习、可重用的代码以及用于网络通信程序的简化库。
书名：C++并发编程实战
ISBN：978-7-115-38732-5
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
• 著 [美] Anthony Williams
译 周 全 梁娟娟 宋真真 许 敏
责任编辑 陈冀康
• 人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
• 读者服务热线：(010)81055410
反盗版热线：(010)81055315
Original English language edition, entitled C++ Concurrency in Action by Anthony Williams, published by Manning Publications Co., 209 Bruce Park Avenue, Greenwich, CT 06830. Copyright ©2012 by Manning Publications Co.
Simplified Chinese-language edition copyright ©2015 by Posts & Telecom Press. All rights reserved.
本书中文简体字版由Manning Publications Co.授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。
版权所有，侵权必究。
本书是一本基于C++11新标准的并发和多线程编程深度指南。内容包括std::thread、std::mutex、std::future和std::async等基础类的使用，内存模型和原子操作、基于锁和无锁数据结构的构建，以及并行算法和线程管理，最后还介绍了多线程代码的测试。本书的附录部分还对C++11新语言特性中与多线程相关的项目进行了简要的介绍，并提供了C++11线程库的完整参考。
本书适合于需要深入了解C++多线程开发的读者，以及使用C++进行各类软件开发的开发人员、测试人员阅读。使用第三方线程库的读者，也可以从本书后面的章节中了解到相关的指引和技巧。同时，本书还可以作为C++11线程库的参考工具书。
我是在离开大学后的第一份工作中遇到多线程编程的概念的。我们当时在编写一个数据处理应用程序，它需要用传入的数据记录来填充数据库。虽然数据很多，但每个数据都是独立的，并且在它被插入数据库前需要大量的处理。为了充分利用10-CPU UltraSPARC的能力，我们在多线程中运行代码，让每个线程处理它们自己的一组输入数据。在这个过程中，我们用C++编写代码，使用POSIX线程，并且犯了相当多的错误。尽管多线程对我们而言都是全新的，但我们最终还是完成了。正是在这个项目中的工作，我第一次了解了C++标准委员会和全新发布的C++标准。
我对多线程和并发有前所未有的兴趣。虽然别人认为它困难、复杂，是问题之源，但我却视它为强大的工具，因为它可以允许你利用现有的硬件让代码运行得更快。随后我了解到它即便是在单核硬件上也能提高应用程序的响应和性能，通过使用多线程来隐藏诸如I/O这样耗费时间的操作延迟。我还了解了它怎样在OS级别工作以及Intel CPU如何处理任务切换。
同时，我对C++的兴趣给我带来了与ACCU以及BSI的C++标准专家组以及Boost接触的机会。我凭兴趣跟进了Boost线程库的初期开发，当它被最初的开发者抛弃时，我便趁机介入了。我从此成为了Boost线程库最主要的开发者和维护者。
当C++标准委员会的工作从修正现有标准的缺陷转移到编写下一代标准（希望在2009年之前完成故命名为C++0x，现在正式为C++11，因为最终发布于2011年）的提案后，我更多地参与到BSI并且开始起草我自己的提案。多线程刚被明确地提上议事日程，我就全力以赴地投入进去，并且撰写或共同撰写了许多与多线程和并发相关的提案，它们组成了新标准的一部分。我感到很荣幸，可以有这个机会用这种方式组合我的计算机相关的两大兴趣——C++和多线程。
这本书借鉴了我在C++和多线程上的全部经验，其目标是教会其他C++开发者如何安全并有效地使用C++11线程库。我也希望能顺带传授一些我在这方面的热情。
周全，软件工程师，毕业于中国科学技术大学信息学院，现就职于中国人民银行合肥中心支行科技处。有着丰富的系统集成和运维经验，对虚拟化也有较深入的研究，曾从事.NET开发和培训工作。读者可以通过Email:zhouquan.pbc@foxmail.com与他联系。
梁娟娟，2010年毕业于中国科学技术大学信息技术学院，现就职于中国人民银行合肥中心支行。
宋真真，网络工程师，2008年毕业于合肥工业大学计算机与信息学院，现就职于中国人民银行合肥中心支行科技处，参与软件开发、项目管理等工作，爱好数据库、编程等研究。读者可以通过Email:hfut_szz@sina.com与她联系。
许敏，软件工程师，2005年获得软件测试工程师证书。现就职于中国人民银行合肥中心支行科技处，负责项目管理工作。读者可以通过Email:xu_min@sina.com与她联系。
我要首先对我的妻子Kim说一声“谢谢”，感谢在我写这本书的时候她给我的爱和支持。写书占用了我最近4年很多的空闲时间，没有她的耐心、支持和理解，我不可能做到。
其次，我想感谢Manning的团队，包括总编Marjan Bace、副总编Michael Stephens、开发编辑Cynthia Kane、编审Karen Tegtmeyer、文字编辑Linda Recktenwald、校对Katie Tennant和制作经理Mary Piergies。他们使得这本书成功面世，没有他们的努力，你现在就读不到这本书了。
我还想感谢C++标准委员会的其他成员，他们为多线程工具上撰写了文件。正是Andrei Alexandrescu、Pete Becker、Bob Blainer、Hans Boehm、Beman Dawes、Lawrence Crowl、Peter Dimov、Jeff Garland、Kevlin Henney、Howard Hinnant、Ben Hutchings、Jan Kristofferson、Doug Lea、Paul McKenney、Nick McLaren、Clark Nelson、Bill Pugh、Raul Silvera、Herb Sutter、Detlef Vollmann和Michael Wong，以及所有在文件上批注的人们，他们在委员会会议上进行了讨论，还有其他人的帮助才形成了C++11中的多线程和并发支持。
最后，我还想感谢下面的人：Dr. Jamie Allsop、Peter Dimov、Howard Hinnant、Rick Molloy、Jonathan Wakely和Dr. Russel Winder，他们的建议极大地改进了这本书。另外特别感谢Russel的详细审阅，还有技术校对Jonathan，在编辑出版过程中极其用心地检查了终稿中所有内容中的错误（当然所有的错误都是由我造成的）。此外我想感谢我的审稿专家组：Ryan Stephens、Neil Horlock、John Taylor Jr.、Ezra Jivan、Joshua Heyer、Keith S. Kim、Michele Galli、Mike Tian-Jian Jiang、David Strong、Roger Orr、Wagner Rick、Mike Buksas和Bas Vodde。还要谢谢MEAP版的读者，他们花费时间来指出错误或是强调了需要阐明的部分。
这本书是对新C++标准中的并发和多线程工具的深度指南，内容包括从std::thread、std::mutex和std::async的基本用法，到复杂的原子操作与内存模型。
前4章介绍了由类库提供的各种类库工具以及他们如何使用。
第5章涵盖了内存模型和原子操作的低阶基础，包括原子操作怎样在其他代码上强制实行排序约束，并标志着导言章节的结束。
第6章和第7章开始涵盖高阶的论题，包括一些如何使用基础工具来构造更复杂的数据结构的示例——第6章中基于锁的数据结构，以及第7章中无锁的数据结构。
第8章继续高阶论题，包括如何设计多线程代码的指南，涵盖了影响性能的论点，以及各种并行算法的示范实现。
第9章涵盖了线程管理——线程池、工作队列和中断操作。
第10章包括了测试和调试——bug的类型，定位它们的技巧，如何测试它们，等等。
附件包含了对由新标准引入的与多线程相关的一些新语言工具的简要介绍，第4章中提到的消息传递库的具体实现，以及C++11线程库的完整参考。
如果你打算用C++编写多线程代码，你就应该阅读本书。如果你正要使用C++标准库中新的多线程工具，这本书是必备的指南。如果你正使用替代的线程库，后面几章中的指引和技巧应该也是有用的。
假设你对C++已经有了很好的了解，但对新的语言特性却不甚熟悉，这些在附录A中也能找到答案。假定你之前没有多线程编程的知识和经验，那就更应该阅读本书。
如果你以前从未写过多线程代码，我建议你按顺序从头到尾阅读本书，可以跳过第5章中的细节部分，但第7章大量依赖第5章中的材料，所以如果你跳过了第5章，你一定要阅览第7章，除非你曾读过。
如果你之前未曾使用过C++11语言工具，在你开始确定准备快速开始书中例子之前最好浏览一下附录A。新语言工具的使用凸显在文字之中，然而，当你遇到了之前没有见过的东西时，总是可以翻看附录的。
如果你在其他环境中拥有大量编写多线程代码的经验，开始的几章可能让你值得浏览一遍，以便你可以看看你了解的工具怎样映射到新C++标准中。如果你打算用原子变量做一些低阶的工作，第5章就是必需的。为了确认你熟悉多线程C++中类似异常安全的东西，值得阅览一下第8章。如果你在脑海中有特定的任务，索引和目录可以帮助你快速找到相关的章节。
一旦你打算促进C++线程库的使用，附录D应该仍然有用，比如查询每个类和函数调用的细节。你可能会想一次又一次地翻回主章节，来刷新你对某一概念的使用或者看一看示例代码。
所有代码清单和正文中的源代码，出现等宽字体（like this），是为了便于从常规文本中区分出来。代码注解伴随着很多清单，指出重要的概念。在有些情况下，数字符号往往指向清单后面的注释。
本书中所有的工作示例源代码可以在出版社网址下载，www.manning.com/CPlusPlusConcurrencyinAction。
为了直截了当地使用本书中的代码，你需要一个最新的C++编译器，它支持示例中使用的新的C++11语言特性（参见附录A），并且你需要C++标准线程库的副本。
在撰写本书的时候，g++是我所知道的唯一带有标准线程库实现的编译器，尽管Microsoft Visual Studio 2011预览版也包括了实现。线程库的g++实现最早是在g++ 4.3中引入了基本形式，并且在后来的版本中进行了扩展。g++ 4.3也引入了一些新C++11语言特性的初次支持；对新语言特性更多的支持在各个后续版本中。详情参见g++ C++11状态页面[1]。
Microsoft Visual Studio 2010提供了一些新C++11语言特性，例如右值引用和lambda函数，但并不带有线程库的实现。
作者的公司Just Soft Solutions Ltd，出售为Microsoft Visual Studio 2005、Microsoft Visual Studio 2008、Microsoft Visual Studio 2010和g++的各种版本[2]设计的C++11标准线程库的完整实现。这些实现已被用来测试本书中的示例。
Boost线程库[3]提供了基于C++标准线程库提案的API，可以移植到许多平台。本书中的大部分示例可以通过审慎地将std::替换成boost::进行修改，并使用适当的#include指令，来与Boost线程库一起工作。在Boost线程库中有少数工具不受支持（比如std::async）或者拥有不同的名称（比如boost::unique_future）。
购买C++ Concurrency in Action包括了免费访问由Manning出版社运营的私有网络论坛，在这里你可以对本书做出评论，提问技术问题，并且从作者和其他用户那里得到帮助。如果要访问此论坛并订阅它，可以访问网址www.manning.com/CPlusPlusConcurrencyinAction。该页面提供了论坛的使用指南以及论坛上的行为规则。
Manning对我们读者的承诺是提供一个场所，在这里每个读者之间以及读者和作者之间可以进行有意义的对话。就作者而言并没有承诺任何规定的参与量，作者对本书论坛的贡献只是义务的（且无偿的）。我们建议你试着向作者提问一些有挑战性的问题，以免他失去兴趣！
作者在线论坛以及过往讨论的归档，在本书在印期间都可以从出版社网站进行访问。
[1] GNU Compiler Collection C++0x/C++11状态页面，http://gcc.gnu.org/projects/cxx0x.html。
[2] C++标准线程库的just::thread实现，http://www.stdthread.co.uk。
[3] Boost C++库集合，http://www.boost.org。
Cargill, Tom, “Exception Handling: A False Sense of Security,”in C++ Report 6, no. 9, (November-December 1994). Also available at http://www.informit.com/content/images/ 020163371x/supplements/Exception_Handling_Article.html.
Hoare, C.A.R., Communicating Sequential Processes (Prentice Hall International, 1985), ISBN 0131532898. Also available at http://www.usingcsp.com/cspbook.pdf.
Michael, Maged M., “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes”in PODC’02: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing (2002), ISBN 1-58113-485-1.
———. U.S. Patent and Trademark Office application 20040107227, “Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation.”
Sutter, Herb, Exceptional C++: 47 Engineering Puzzles, Programming Problems, and Solutions (Addison Wesley Professional, 1999), ISBN 0-201-61562-2.
———. “The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software,”in Dr. Dobb’s Journal 30, no. 3 (March 2005). Also available at http://www.gotw.ca/publications/ concurrency-ddj.htm.
Atomic Ptr Plus Project Home, http://atomic-ptr-plus.sourceforge.net/.
Boost C++ library collection, http://www.boost.org.
C++0x/C++11 Support in GCC, http://gcc.gnu.org/projects/cxx0x.html.
C++11—The Recently Approved New ISO C++ Standard, http://www.research.att. com/～bs/C++0xFAQ.html.
Erlang Programming Language, http://www.erlang.org/.
GNU General Public License, http://www.gnu.org/licenses/gpl.html.
Haskell Programming Language, http://www.haskell.org/.
IBM Statement of Non-Assertion of Named Patents Against OSS, http://www.ibm.com/ ibm/licensing/patents/pledgedpatents.pdf.
Intel Building Blocks for Open Source, http://threadingbuildingblocks.org/.
The just::thread Implementation of the C++ Standard Thread Library, http://www. stdthread.co.uk.
Message Passing Interface Forum, http://www.mpi-forum.org/.
Multithreading API for C++0X—A Layered Approach, C++ Standards Committee Paper N2094, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2094.html.
OpenMP, http://www.openmp.org/.
SETI@Home, http://setiathome.ssl.berkeley.edu/.
第1章 你好，C++并发世界 1
第2章 管理线程 13
第3章 在线程间共享数据 31
第4章 同步并发操作 63
第5章 C++内存模型和原子类型操作 97
第6章 设计基于锁的并发数据结构 140
第7章 设计无锁的并发数据结构 170
第8章 设计并发代码 213
第9章 高级线程管理 258
第10章 多线程应用的测试与调试 285
附录A C++11部分语言特性简明参考 299
附录B 并发类库简要对比 324
附录C 消息传递框架与完整的ATM示例 326
附录D C++线程类库参考 344
本章主要内容
这是令C++用户振奋的时刻。距1998年初始的C++标准发布13年后，C++标准委员会给予程序语言和它的支持库一次重大的变革。新的C++标准（也被称为C++11或C++0x）于2011年发布并带来了很多的改变，使得C++的应用更加容易并富有成效。
在C++11标准中一个最重要的新特性就是支持多线程程序。这是C++标准第一次在语言中承认多线程应用的存在，并在库中为编写多线程应用程序提供组件。这将使得在不依赖平台相关扩展下编写多线程C++程序成为可能，从而允许以有保证的行为来编写可移植的多线程代码。这也恰逢程序员寻求更多普遍的并发，特别是多线程程序，来提高应用程序的性能。
这本书讲述的就是C++编程中对多线程并发的使用，以及相关的C++语言特性和库工具。我会以解释并发和多线程的含义以及为什么要在应用程序中使用并发开始。在快速全方位地阐述为什么在应用程序中会不使用并发之后，我会对C++中并发支持进行概述，并以一个简单的C++并发实例结束这一章。具有开发多线程应用程序经验的读者可以跳过前面的小节。在随后几章将会涵盖更多广泛的例子，并且更深入地了解库工具。本书最后附有对多线程与并发全部的C++标准库工具的深入参考。
那么，什么是并发（concurrency）和多线程（multithreading）？
在最简单和最基本的层面，并发是指两个或更多独立的活动同时发生。并发在生活中随处可见。我们可以一边走路一边说话，也可以两只手同时做不同的动作，还有我们每个人都相互独立地过我们的生活——我在游泳的时候你可以看球赛，等等。
当我们提到计算机术语的“并发”，指的是在单个系统里同时执行多个独立的活动，而不是顺序地或是一个接一个地。这并不是一种新的现象，多任务操作系统通过任务切换允许一台计算机在同一时间运行多个应用程序已司空见惯多年，一些高端的多任务处理服务器实现并发控制的历史更久远。真正有新意的是增加计算机真正并行运行多任务的普遍性，而不只是给人这种错觉。
以前，大多数计算机都有一个处理器，具有单个处理单元或核心，至今许多台式机器仍是这样。这种计算机在某一时刻只可以真正执行一个任务，但它可以每秒切换任务许多次。通过做一点这个任务然后再做一点别的任务，看起来像是任务在并行发生。这就是任务切换（taskswitching）。我们仍然将这样的系统称为并发（concurrency），因为任务切换得太快，以至于无法分辨任务在何时会被暂挂而切换到另一个任务。任务切换给用户和应用程序本身造成了一种并发的假象。由于这只是并发的假象，当应用程序执行在单处理器任务切换环境下，与在真正的并发环境下执行相比，其行为还是有着微妙的不同。特别地，对内存模型不正确的假设（参见第5章）在这样的环境中可能不会出现。这将在第10章中作深入讨论。
包含多个处理器的计算机用于服务器和高性能计算任务已有多年，现在基于单个芯片上具有多于一个核心的处理器（多核心处理器）的计算机也成为越来越常见的台式机器。无论它们拥有多个处理器或一个多核处理器（或两者兼具），这些计算机能够真正的并行运行超过一个任务。我们才称之为硬件并发（hardwareconcurrency）。
图1.1显示了一个计算机处理恰好两个任务时的理想情景，每个任务被分为10个相等大小的块。在一个双核机器（具有两个处理核心）中，每个任务可以在各自的核心执行。在单核机器上做任务切换时，每个任务的块交织进行。但它们也隔开了一位（图中所示灰色分隔条的厚度大于双核机器的分隔条）。为了实现交替进行，该系统每次从一个任务切换到另一个时都得执行一次上下文切换（contextswitch），而这是需要时间的。为了执行上下文切换，操作系统必须为当前运行的任务保存CPU的状态和指令指针，算出要切换到哪个任务，并为要切换到的任务重新加载处理器状态。然后CPU可能要将新任务的指令和数据的内存载入到缓存中，这可能会阻止CPU执行任何指令，造成进一步的延迟。
图1.1 并发的两种方式：双核机器的并行执行对比单核机器的任务切换
尽管硬件并发的可用性在多处理器或多核系统上更显著，有些处理器却可以在一个核心上执行多个线程。要考虑的最重要的因素是硬件线程（hardwarethreads）的数量：即硬件可以真正并发运行多少独立的任务。即便是具有真正硬件并发的系统，也很容易有超过硬件可并行运行的任务要执行，所以在这些情况下任务切换仍将被使用。例如，在一个典型的台式计算机上可能会有几百个的任务在运行，执行后台操作，即使计算机在名义上是空闲的。正是任务切换使得这些后台任务可以运行，并使得你可以同时运行文字处理器、编译器、编辑器和web浏览器（或任何应用的组合）。图1.2显示了四个任务在一台双核机器上的任务切换，仍然是将任务整齐地划分为同等大小块的理想情况。实际上，许多因素造成了分割不均和调度不规则。这些因素中的一部分将涵盖在第8章中，那时我们再来看一看影响并行代码性能的因素。
图1.2 四个任务在两个核心之间的切换
所有的技术、功能和本书所涉及的类都可以使用，无论你的应用程序是在单核处理器还是多核处理器上运行，也不管是任务切换或是真正的硬件并发。但你可以想象，如何在你的应用程序中使用并发很大程度上取决于可用的硬件并发。这将在第8章中涵盖，在第8章我们具体研究C++代码并行设计问题。
想象一下两个程序员一起做一个软件项目。如果你的开发人员在独立的办公室，它们可以各自平静地工作，而不会互相干扰，并且他们各有自己的一套参考手册。然而，沟通起来就不那么直接了；不能转身然后互相交谈，他们必须用电话、电子邮件或走到对方的办公室。同时，你需要掌控两个办公室的开销，还要购买多份参考手册。
现在想象一下把开发人员移到同一间办公室。他们现在可以地相互交谈来讨论应用程序的设计，他们也可以很容易地用纸或白板来绘制图表，辅助阐释设计思路。你现在只有一个办公室要管理，只要一组资源就可以满足。消极的一面是，他们可能会发现难以集中注意力，并且还可能存在资源共享的问题（“参考手册跑哪去了？”）。
组织开发人员的这两种方法代表着并发的两种基本途径。每个开发人员代表一个线程，每个办公室代表一个处理器。第一种途径是有多个单线程的进程，这就类似让每个开发人员在他们自己的办公室，而第二种途径是在单一进程里有多个线程，这就类似在同一个办公室里有两个开发人员。你可以随意进行组合，并且拥有多个进程，其中一些是多线程的，一些是单线程的，但原理是一样的。让我们在一个应用程序中简要地看一看这两种途径。
在一个应用程序中使用并发的第一种方法，是将应用程序分为多个、独立的、单线程的进程，它们运行在同一时刻，就像你可以同时进行网页浏览和文字处理。这些独立的进程可以通过所有常规的进程间通信渠道互相传递信息（信号、套接字、文件、管道等），如图1.3所示。有一个缺点是这种进程之间的通信通常设置复杂，或是速度较慢，或两者兼备，因为操作系统通常在进程间提供了大量的保护，以避免一个进程不小心修改了属于另一个进程的数据。另一个缺点是运行多个进程所需的固有的开销：启动进程需要时间，操作系统必须投入内部资源来管理进程，等等。
图1.3 一对并发运行的进程之间的通信
当然，也并不全是缺点：操作系统在线程间提供的附加保护操作和更高级别的通信机制，意味着可以比线程更容易地编写安全的并发代码。事实上，类似于为Erlang编程语言提供的环境，可使用进程作为重大作用并发的基本构造块。
使用独立的进程实现并发还有一个额外的优势——你可以通过网络连接的不同的机器上运行独立的进程。虽然这增加了通信成本，但在一个精心设计的系统上，它可能是一个提高并行可用行和提高性能的低成本方法。
并发的另一个途径是在单个进程中运行多个线程。线程很像轻量级的进程：每个线程相互独立运行，且每个线程可以运行不同的指令序列。但进程中的所有线程都共享相同的地址空间，并且从所有线程中访问到大部分数据——全局变量仍然是全局的，指针、对象的引用或数据可以在线程之间传递。虽然通常可以在进程之间共享内存，但这难以建立并且通常难以管理，因为同一数据的内存地址在不同的进程中也不尽相同。图1.4显示了一个进程中的两个线程通过共享内存进行通信。
图1.4 同一进程中的一对并发运行的线程之间的通信
共享的地址空间，以及缺少线程间的数据保护，使得使用多线程相关的开销远小于使用多进程，因为操作系统有更少的簿记要做。但是，共享内存的灵活性是有代价的：如果数据要被多个线程访问，那么程序员必须确保当每个线程访问时所看到的数据是一致的。线程间数据共享可能会遇到的问题、所使用的工具以及为了避免问题而要遵循的准则在本书中都有涉及，特别是在第3、4、5和8章中。这些问题并非不能克服，只要在编写代码时适当地注意即可，但这却意味着必须对线程之间的通信作大量的思考。
相比于启动多个单线程进程并在其间进行通信，启动单一进程中的多线程并在其间进行通信的开销更低，这意味着若不考虑共享内存可能会带来的潜在问题，它是包括C++在内的主流语言更青睐的并发途径。此外，C++标准没有为进程间通信提供任何原生支持，所以使用多进程的应用程序将不得不依赖平台相关的API来实现。因此，本书专门关注使用多线程的并发，并且之后提到并发均是假定通过使用多线程来实现的。
明确了什么是并发后，现在让我们来看看为什么要在应用程序中使用并发。
在应用程序中使用并发的原因主要有两个：关注点分离和性能。事实上，我甚至可以说它们差不多是使用并发的唯一原因；当你观察得足够仔细时，一切其他因素都可以归结到这两者之一（或者可能是二者兼有，当然，除了像“我愿意”这样的原因之外）。
在编写软件时，划分关注点总是个好主意。通过将相关的代码放在一起并将无关的代码分开，这种方法可以使你的程序更容易理解和测试，从而减少出错的可能性。你可以使用并发来分隔不同的功能区域，即使在这些不同功能区域的操作需要在同一时刻发生的情况下。如果不显式地使用并发，你要么被迫编写任务切换框架，要么在操作中主动地调用不相关的一段代码。
考虑一类带有用户界面的密集处理型应用程序，例如为台式计算机提供的DVD播放程序。这样一个应用程序基本上具备两套职能：它不仅要从光盘中读取数据，解码图像和声音，并把它们及时输出至视频和音频硬件，从而实现DVD的无错播放；它还要接受来自用户的输入，例如当用户单击暂停或返回菜单甚至退出按键的情况。在单个线程中，应用程序须在回放期间定期检查用户的输入，于是将DVD回放代码和用户界面代码合在一起。通过使用多线程来分隔这些关注点，用户界面代码和DVD回放代码不再需要如此紧密地交织在一起。一个线程可以处理用户界面，另一个处理DVD回放，它们之间会有交互，例如用户点击暂停，但现在这些交互直接与眼前的任务有关。
这会带来响应性的错觉，因为用户界面线程通常可以立即响应用户的请求，即使在请求被传达给工作的线程，响应为简单地显示正忙的光标或请等待的消息的情况。类似地，独立的线程常被用于运行必须在后台连续运行的任务，例如在桌面搜索程序中监视文件系统的变化。以这种方式使用线程一般会使每个线程的逻辑更加简单，因为它们之间的交互可以被限制为清晰可辨的点，而不是到处散播不同任务的逻辑。
在这种情况下，线程的数量与CPU可用内核的数量无关，因为对线程的划分是基于概念上的设计而不是试图增加吞吐量。
多处理器系统已经存在了几十年，但直到最近，他们几乎只能在超级计算机、大型机和大型服务器系统中才能看到。然而芯片制造商越来越倾向于多核芯片的设计，即在单个芯片上集成2、4、16或更多的处理器，从而达到比单核心更好的性能。因此，多核台式计算机，甚至多核嵌入式设备，现在越来越普遍。这些计算机的计算能力的提高不是源自使单一任务运行的更快，而是源自并行运行多个任务。在过去，程序员曾坐等他们的程序随着处理器的更新换代而变得更快，无需他们这边做出任何努力。但是现在，就像Herb Sutter所说的，“免费的午餐结束了[1]”。如果软件想要利用日益增长的计算能力，它必须设计为并发运行多个任务。程序员因此必须留意，而且那些迄今都忽略并发的人们必须注意它并将其加入他们的工具箱中。
有两种方式为了性能使用并发。首先，也是最明显的，是将一个单个任务分成几部分且各自并行运行，从而降低总运行时间，这就是任务并行（taskparallelism）。虽然这听起来很直观，但它可以是一个相当复杂的过程，因为在各个部分之间可能存在很多的依赖。区别可能是在过程方面——一个线程执行算法的一部分而另一个线程执行算法的另一部分——或是在数据方面——每个线程在不同的数据部分上执行相同的操作。后一种方法被称为数据并行（dataparallelism）。
容易受这种并行影响的算法常被称为易并行（embarrassinglyparallel）。抛开你可能会尴尬地面对的很容易并行化的代码这一含义，这是一件好事情。我曾遇到过的关于此算法的别的术语是自然并行（naturallyparallel）和便利并发（convenientlyconcurrent）。易并行算法具有良好的可扩展特性——随着可用硬件线程数量的提升，算法的并行性可以随之增加与之匹配。这样的一个算法是谚语“人多力量大”的完美体现。对于非易并行算法的那一部分，你可以将算法划分为一个固定（因而不可扩展）数量的并行任务。在线程之间划分任务的技巧涵盖在第8章中。
使用并发来提升性能的第二种方法是使用可用的并行方式来解决更大的问题。与其同时处理一个文件，不如酌情处理2个或10个或20个。虽然这实际上只是数据并行的一种应用，通过对多组数据同时执行相同的操作，但还是有不同的重点。处理一个数据块仍然需要同样的时间，但在相同的时间内却可以处理更多的数据。当然，这种方法也存在限制，且并非在所有情况下都是有益的，但是这种方法所带来的吞吐量提升可以让一些新玩意变得可能。例如，如果图片的各部分可以并行处理，就能提高视频处理的分辨率。
知道何时不使用并发与知道何时要使用它同等重要。基本上，不使用并发的唯一原因就是在收益比不上成本的时候。使用并发的代码在很多情况下难以理解，因此编写和维护的多线程代码就有直接的脑力成本，同时额外的复杂性也可能导致更多的错误。除非潜在的性能增益足够大或关注点分离得足够清晰，能抵消确保其正确所需的额外的开发时间以及与维护多线程代码相关的额外成本，否则不要使用并发。
同样地，性能增益可能不会如预期的那么大。在启动线程时存在固有的开销，因为操作系统必须分配相关的内核资源和堆栈空间，然后将新线程加入调度器中，所有这一切都要占用时间。如果在线程上运行的任务完成得很快，那么任务实际上占据的时间与启动线程的开销时间相比就显得微不足道，可能会导致应用程序的整体性能还不如通过产生线程直接执行该任务。
此外，线程是有限的资源。如果让太多的线程同时运行，则会消耗操作系统资源，并且使得操作系统整体上运行得更缓慢。不仅如此，运行太多的线程会耗尽进程的可用内存或地址空间，因为每个线程都需要一个独立的堆栈空间。对于一个可用地址空间限制为4GB的扁平架构的32位进程来说，这尤其是个问题。如果每个线程都有一个1MB的堆栈（对于很多系统来说是典型的），那么4096个线程将会用尽所有地址空间，不再为代码、静态数据或者堆数据留有空间。虽然64位（或者更大）的系统不存在这种直接的地址空间限制，它们仍然只具备有限的资源：如果你运行太多的线程，最终会导致问题。尽管线程池（参见第9章）可以用来限制线程的数量，但这并不是灵丹妙药，它们也有自己的问题。
如果客户端/服务器应用程序的服务器端为每一个链接启动一个独立的线程，对于少量的链接是可以正常工作的，但当同样的技术用于需要处理大量链接的高需求服务器时，就会因为启动太多线程而迅速耗尽系统资源。在这种场景下，谨慎地使用线程池可以提供优化的性能（参见第9章）。
最后，运行越多的线程，操作系统就需要做越多的上下文切换。每个上下文切换都需要耗费本可以花在有价值工作上的时间，所以在某些时候，增加一个额外的线程实际上会降低而不是提高应用程序的整体性能。为此，如果你试图得到系统的最佳性能，考虑可用的硬件并发（或缺乏之）并调整运行线程的数量是必需的。
为了性能优化而使用并发就像所有其他优化策略一样，它拥有极大提高应用程序性能的潜力，但它也可能使代码复杂化，使其更难理解和更容易出错。因此，只有对应用程序中的那些具有显著增益潜力的性能关键部分才值得这样做。当然，如果性能收益的潜力仅次于设计清晰或关注点分离，可能也值得使用多线程设计。
假设你已经决定确实要在应用程序中使用并发，无论是为了性能、关注点分离，或是因为“多线程星期一”，对于C++程序员来说意味着什么？
通过多线程为并发提供标准化的支持对C++来说是新鲜事物。只有在即将到来的C++11标准中，你才能不依赖平台相关的扩展来编写多线程代码。为了理解新版本C++线程库中众多规则背后的基本原理，了解其历史是很重要的。
1998C++标准版不承认线程的存在，并且各种语言要素的操作效果都以顺序抽象机的形式编写。不仅如此，内存模型也没有被正式定义，所以对于1998 C++标准，你没办法在缺少编译器相关扩展的情况下编写多线程应用程序。
当然，编译器供应商可以自由地向语言添加扩展，并且针对多线程的C API的流行——例如在POSIX C和Microsoft Windows API中的那些——导致很多C++编译器供应商通过各种平台相关的扩展来支持多线程。这种编译器支持普遍地受限于只允许使用该平台相应的C API以及确保该C++运行时库（例如异常处理机制的代码）在多线程存在的情况下运行。尽管极少有编译器供应商提供了一个正式的多线程感知内存模型，但编译器和处理器的实际表现也已经足够好，以至于大量的多线程的C++程序已被编写出来。
由于不满足于使用平台相关的C API来处理多线程，C++程序员曾期望他们的类库提供面向对象的多线程工具。像MFC这样的应用程序框架，以及像Boost和ACE这样的C++通用类库曾积累了多套C++类，封装了下层的平台相关API并提供高级的多线程工具以简化任务。各类库的具体细节，特别是在启动新线程的方面，存在很大差异，但是这些类的总体构造存在很多共通之处。有一个为许多C++类库共有的，同时也是为程序员提供很大便利的特别重要的设计，就是带锁的资源获得即初始化（RAII, ResourceAcquisitionIsInitialization）的习惯用法，来确保当退出相关作用域的时候互斥元被解锁。
许多情况下，现有的C++编译器所提供的多线程支持，例如Boost和ACE，综合了平台相关API以及平台无关类库的可用性，为编写多线程C++代码提供一个坚实的基础，也因此大约有数百万行C++代码作为多线程应用程序的一部分而被编写出来。但缺乏标准的支持，意味着存在缺少线程感知内存模型从而导致问题的场合，特别是对于那些试图通过使用处理器硬件能力来获取更高性能，或是编写跨平台代码，但是在不同平台之间编译器的实际表现存在差异。
所有这些都随着新的C++11标准的发布而改变了。不仅有了一个全新的线程感知内存模型，C++标准库也被扩展了，包含了用于管理线程（参见第2章）、保护共享数据（参见第3章）、线程间同步操作（参见第4章）以及低级原子操作（参见第5章）的各个类。
新的C++线程库很大程度上基于之前通过使用上文提到的C++类库而积累的经验。特别地，Boost线程库被用作新类库所基于的主要模型，很多类与Boost中的对应者共享命名和结构。在新标准演进的过程中，这是个双向流动，Boost线程库也改变了自己，以便在多个方面匹配C++标准，因此从Boost迁移过来的用户将会发现自己非常适应。
正如本章开篇提到的那样，对并发的支持仅仅是新C++标准的变化之一，此外还存在很多对于编程语言自身的改善，可以使得程序员们的工作更便捷。这些内容虽然不在本书的论述范围之内，但是其中的一些变化对于线程库本身及其使用方式已经形成了直接的冲击。附录A对这些语言特性做了简要的介绍。
C++中对原子操作的直接支持，允许程序员编写具有确定语义的高效代码，而无需平台相关的汇编语言。这对于那些试图编写高效的、可移植代码的程序员们来说是一个真正的福利。不仅有编译器可以搞定平台的具体内容，还可以编写优化器来考虑操作的语义，从而让程序作为一个整体得到更好的优化。
对于C++整体以及包含低级工具的C++类——特别是在新版C++线程库里的那些，参与高性能计算的开发者常常关注的一点就是效率。如果你正寻求极致的性能，那么理解与直接使用底层的低级工具相比，使用高级工具所带来的实现成本，是很重要的。这个成本就是抽象惩罚（abstractionpenalty）。
C++标准委员会在整体设计C++标准库以及专门设计标准C++线程库的时候，就已经十分注重这一点了。其设计的目标之一就是在提供相同的工具时，通过直接使用低级API就几乎或完全得不到任何好处。因此该类库被设计为在大部分平台上都能高效实现（带有非常低的抽象惩罚）。
C++标准委员会的另一个目标，是确保C++能提供足够的低级工具给那些希望与硬件工作得更紧密的程序员，以获取终极性能。为了达到这个目的，伴随着新的内存模型，出现了一个全面的原子操作库，用于直接控制单个位、字节、线程间同步以及所有变化的可见性。这些原子类型和相应的操作现在可以在很多地方加以使用，而这些地方以前通常被开发者选择下放到平台相关的汇编语言中。使用了新的标准类型和操作的代码因而具有更佳的可移植性，并且更易于维护。
C++标准库也提供了更高级别的抽象和工具，它们使得编写多线程代码更简单和不易出错。有时候运用这些工具确实会带来性能成本，因为必须执行额外的代码。但是这种性能成本并不一定意味着更高的抽象惩罚；总体来看，这种性能成本并不比通过手工编写等效的函数而招致的成本更高，同时编译器可能会很好地内联大部分额外的代码。
在某些情况下，高级工具提供超出特定使用需求的额外功能。在大部分情况下这都不是问题，你没有为你不使用的那部分买单。在罕见的情况下，这些未使用的功能会影响其他代码的性能。如果你更看重程序的性能，且代价过高，你可能最好是通过较低级别的工具来手工实现需要的功能。在绝大多数情况下，额外增加的复杂性和出错的几率远大于小小的性能提升所带来的潜在收益。即使有证据确实表明瓶颈出现在C++标准库的工具中，这也可能归咎于低劣的应用程序设计而非低劣的类库实现。例如，如果过多的线程竞争一个互斥元，这将会显著影响性能。与其试图在互斥操作上花掉一点点的时间，还不如重新构造应用程序以减少互斥元上的竞争来得划算。设计应用程序以减少竞争会在第8章中加以阐述。
在非常罕见的情况下，C++标准库不提供所需的性能或行为，这时则有必要运用特定的平台相关的工具。
虽然C++线程库为多线程和并发处理提供了颇为全面的工具，但是在所有的平台上，都会有些额外的平台相关工具。为了能方便地访问那些工具而又不用放弃使用标准C++线程库带来的好处，C++线程库中的类型可以提供一个native_handle()成员函数，允许通过使用平台相关API直接操作底层实现。就其本质而言，任何使用native_handle()执行的操作是完全依赖于平台的，这也超出了本书（同时也是标准C++库本身）的范围。
当然，在考虑使用平台相关的工具之前，明白标准库能够提供什么是很重要的，那么让我们通过一个例子来开始。
好，现在你有一个很棒的与C++11兼容的编译器。接下来呢？一个多线程C++程序是什么样子的？它看上去和其他所有C++程序一样，通常是变量、类以及函数的组合。唯一真正的区别在于某些函数可以并发运行，所以你需要确保共享数据的并发访问是安全的，详见第3章。当然，为了并发地运行函数，必须使用特定的函数以及对象来管理各个线程。
让我们从一个经典的例子开始：一个打印“Hello World.”的程序。一个非常简单的在单线程中运行的Hello, World程序如下所示，当我们谈到多线程时，它可以作为一个基准。
清单1.1这个程序所做的一切就是将“Hello World”写进标准输出流。让我们将它与下面清单所示的简单的Hello, Concurrent World程序做个比较，它启动了一个独立的线程来显示这个信息。
清单1.1 一个简单的Hello,Concurrent World程序
第一个区别是增加了#include<thread>❶。在标准C++库中对多线程支持的声明在新的头文件中，用于管理线程的函数和类在<thread>中声明，而那些保护共享数据的函数和类在其他头文件中声明。
其次，写信息的代码被移动到了一个独立的函数中❷。这是因为每个线程都必须具有一个初始函数（initialfunction），新线程的执行在这里开始。对于应用程序来说，初始线程是main()，但是对于所有其他线程，这在std::thread对象的构造函数中指定——在本例中，被命名为t❸的std::thread对象拥有新函数hello()作为其初始函数。
下一个区别，与直接写入标准输出或是从main()调用hello()不同，该程序启动了一个全新的线程来实现，将线程数量一分为二——初始线程始于main()而新线程始于hello()。
在新的线程启动之后❸，初始线程继续执行。如果它不等待新线程结束，它就将自顾自地继续运行到main()的结束，从而结束程序——有可能发生在新线程有机会运行之前。❹这里调用join()的原因——详见第2章，这会导致调用线程（在main()中）等待与std::thread对象相关联的线程，即这个例子中的t。
如果这看起来像是仅仅为了将一条信息写入标准输出而做了大量的工作，那么它确实如此——正如上文1.2.3节所描述的，一般来说并不值得为了如此简单的任务而使用多线程，尤其是如果在这期间初始线程无所事事。在本书后面的内容中，我们将通过实例来展示在哪些情景下使用多线程可以获得明确的收益。
在本章中，我提及了并发与多线程的含义以及在你的应用程序中为什么会选择使用（或不使用）它。我还提及了多线程在C++中的发展历程，从1998标准中完全缺乏支持，经历了各种平台相关的扩展，再到新的C++11标准中具有合适的多线程支持。该支持到来的正是时候，它使得程序员们可以利用伴随新的CPU而带来的更加强大的硬件并发，因为芯片制造商选择了以多核心的形式使得更多任务可以同时执行的方式来增加处理能力，而不是增加单个核心的执行速度。
在1.4节中的示例中展示了C++标准库中的类和函数有多么的简单。在C++中，使用多线程本身并不复杂，复杂的是如何设计代码以实现其预期的行为。
在尝试了1.4节的示例之后，是时候看看更多实质性的内容了。在第2章中，我们将看一看用于管理线程的类和函数。
[1] The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Herb Sutter, Dr. Dobb’s Journal, 30(3), March 2005. http://www.gotw.ca/publications/concurrency-ddj.htm
本章主要内容
前面的章节主要是讨论新的C++11工具箱里用来写并行代码的工具。在第6章和第7章中，我们观察了如何使用这些工具来设计多个线程可以并发存取的安全的基础数据结构。作为木匠，为了制作柜橱或者桌子，不仅仅需要知道如何铰链或者接缝处。同样，需要设计并行代码而不仅仅是设计和使用基础数据结构。你需要了解更广泛的背景，这样就可以构造进行有用工作的更大的结构。我将使用一些C++标准库算法的多线程实现作为例子，但是同样的原则适用于应用的所有方面。
正如所有编程项目一样，仔细考虑并行代码是很重要的。尽管如此，使用多线程代码比使用顺序代码需要考虑更多的因素。你不仅需要考虑常见的因素，例如封装，耦合和内聚（在很多软件设计书中有详细的描述），而且需要考虑共享哪些数据，如何同步那些数据的存取，哪个线程需要等待哪些别的线程完成特定操作，等等。
本章，我们将致力于这些问题，从高层次考虑使用多少个线程，各个线程执行哪些代码，以及这些是如何影响代码的透明度。到低层次考虑如何构造共享数据来获得最佳性能。
让我们从在线程间划分工作的技术开始。
设想你被安排建造一所房子。为了完成这项工作，你需要挖地基、筑墙、布线等。理论上说，你可以在足够的训练下全部自己完成，但是将耗费很多时间，并且会一直切换任务。或者，你可以雇佣别人来帮助你。你只需要选择雇佣多少人并且决定他们需要哪些技能。例如，你可以雇佣一些具有一般技能的人，并且让每个人做所有事。你仍然需要切换任务，但是因为人数更多所以能够更快地完成。
或者，你可以雇佣一些专家。例如，砖匠，木匠，电工和管道工。这些专家只做他们专长的事情，因此如果没有管道工程的时候，管道工就不需要做任何事情。事情会比之前完成得更快，因为有更多的人，并且当电工给厨房布线的时候，管道工可以安装卫生间。但是当专家没有工作的时候就会处于等待状态。即使有空闲时间，你也会发现雇佣专家比雇佣一般技能的人工作进展得更快。专家不需要改变工具，并且他们完成任务比一般人要快。无论这种情况是否取决于特殊情况——你都需要尝试一下。
即使你雇佣专家，你仍然可以选择每种专家的数量。例如，雇佣比电工数量更多的砖匠就很合理。如果你要建造不止一座房子的话，你的队伍的构成以及总体效率都会发生改变。即使管道工在给定的房子上不会有太多的工作，你也可以一次建造很多房子，这样他就会始终有工作了。并且，如果当他们没有工作的时候不需要付钱的话，那么就可以负担更大的团队了，即使同一时间只有相同数量的人在工作。
那么线程需要做哪些呢？同样的问题也适用于线程。你需要决定使用多少线程以及它们需要完成什么任务。你需要决定是使用“通用型”线程来在需要的时候执行操作，还是使用“专家型”线程来做好一件事或一些合作的事。你需要决定无论是为了使用并发性而划分的原因，还是如何去做都会对代码的性能和清晰度产生很大影响。因此理解这些选择是很重要的，这样当设计你的应用中的数据结构的时候，就可以做出合适的决定。在这部分，我们将会看到一些划分任务的方法。在我们做别的工作前先来看看如何在线程间划分数据。
最早并行化的算法是简单的算法，如std::for_each在数据集合中对每个元素进行操作。为了并行化这样的算法，就需要将每个元素划分到一个处理线程中。如何划分元素来得到最优性能在很大程度上决定于数据结构的细节，稍后我们分析性能问题的时候就可以看到了。
划分数据最简单的方法就是将第一个N元素分配给一个线程，将下一个N元素分配给另一个线程，以此类推，正如图8.1所示，但是也可以使用别的模式。无论如何划分数据，每个线程只能处理分配给它的元素，并且直到它完成任务的时候才能与别的线程通信。
图8.1 在线程间划分连续数据块
这种结构与使用消息传递接口（Message Passing Interface, MPI）[1]或者OpenMP[2]框架编程的结构是类似的。一个任务被分成一个并行任务集，工作的线程独立运行这些任务，并且在最后的化简步骤中合并这些结果。这是2.4节中accumulate例子使用的方法；在这种情况下，并行任务和最后的步骤都是累加。对一个简单的for_each来说，最后的步骤是不需要的，因为不需要化简结果。
确定将最后的步骤作为化简步骤是很重要的，清单2.8中的简单实现将执行此化简作为最后的线性步骤。尽管如此，这个步骤也可以并行化。累加过程本身就是化简操作，因此可以修改清单2.8，当线程的数量比线程处理的的最少数据的数量还要多，就可以递归地调用它本身。或者，当每个线程完成它的任务后，工作线程可以执行一些化简操作步骤，而不是每次产一些新线程。
尽管这种方法是很有效的，但是并不适用于所有情况。有时数据不能被事先划分，因为只有当处理数据的时候才知道如何划分。在化简算法例如快速排序中，这种情况更明显。因此需要一个不同的方法。
快速排序算法有两个基本步骤，基于其中一个元素（关键值）将数据划分为两部分，一部分在关键值之前，一部分在关键值之后。然后递归地排序这两部分。你无法通过预先划分数据来实行并行，因为只有当处理元素的时候才知道他们属于哪一个“部分”。如果你打算并行这个算法，就需要把握递归的本质。每次递归的时候，会调用更多的quick_sort函数来排序关键点之前和关键点之后的元素。这些递归调用是完全相互独立的，因为它们读取完全不同的元素集合。这种划分可以作为我们初步的候选方案。此递归划分如图8.2所示。
图8.2 连续划分数据
在第4章中，有这样一个实现。不仅只是为这两部分执行两个递归调用，你还在每一步都在前一部分使用std::async()来生成异步任务。通过使用std::async()，你让C++线程库来决定何时在一个新线程上运行这个任务，以及何时同步运行它们。
当你对很大规模的数据进行排序的时候这是很重要的。为每一个递归调用生成一个新线程会很快产生大量线程。当我们考虑性能的时候，你就会发现如果线程太多的时候，就可能降低了应用。如果数据集很大的时候也可能会用完所有的线程。像这样用递归来划分总体任务的方法是很好的，只需要严格控制线程数量就可以了。在简单情况下，std::async( )就可以处理它，但是这并不是唯一选择。
或者使用std::thread::hardware_concurrency()函数来选择线程数量，正如清单2.8中accumulate()的并行版本所做的一样。然后，你只是将此块存储到第6章和第7章描述线程安全栈中，而不是为递归调用创建一个新线程。如果线程不在工作，就说明它已经处理完所有块，或者等待存储在栈中的块。此时可以从栈中得到一个块并将它排序。
清单8.1列出了使用这种方法的简单实现。
清单8.1 使用待排序块栈的并行快速排序
这里，parallel_quick_sort函数⓳代表了sorter类➊的大部分功能，提供了一种简单的方法将未排序块➋所在的栈进行分组，以及将线程集➌分组。主要的工作是在do_sort成员函数➒中完成的，它是用来完成通常的数据排序➓。这次，它将块压入栈中⓫，而不是为一个块产生一个新的线程，并且当你仍然有处理器可以分配的时候就产生一个新进程⓬。因为后一部分可能是被另一个线程处理，你就必须等待它处理完成⓭。为了处理这种情况（即只有一个线程或者别的线程都在工作），你就试图在等待的时候，让这个线程处理栈中的块⓮。try_sort_chunk只是将一个块出栈➐并且将它排序➑，将结果存储在promise中，此结果可以被将此块放入栈中的线程取得⓯。
当未设置end_of_data标志的时候⓱，可以在循环中产生线程将栈中的块先出栈然后排序⓰。在检查的时候，它们让别的线程先对栈进行操作。这段代码依靠sorter类析构函数➍来结束这些线程。当所有数据都被排序了，就会返回do_sort（即使线程仍然在运行），因此主线程将从parallel_quici_sort⓴中返回，并且销毁你的sorter对象。这就设置了end_of_data标志位➎并且等待线程结束➏。设置标志位结束了线程函数中的循环⓰。
使用这种方法就不会和使用spawn_task来产生一个新线程一样导致无穷多个线程这样的问题了，并且不再和std::async()一样依赖C++线程库来选择线程数量。现在我们将线程数量限制到std::thread::hardware_concurrency()来避免过多的任务切换。尽管如此，你有另一个潜在的问题，处理这些线程和线程间通信给代码增加了很多复杂性。同时，尽管这些线程在处理不相关的数据元素，它们都访问栈来移入和移出所操作的块。即使使用无锁（因此是无阻塞的）栈，这种竞争会降低性能。你稍后会看到原因。
这种方法是一种特殊版本的线程池——有一个线程集，每个线程处理等待列表中的工作，然后回到线程池。线程池存在的问题（包括列表上的竞争），第9章中有解决这些问题的方法。本章稍后将讨论如何将程序扩展到多处理器上执行（参见8.2.1节）。
在处理开始前划分数据和递归划分数据都是假设数据是固定不变的，然后你寻找划分它的方法，但是情况并不总是这样。如果数据是动态生成的或者是外部输入的，那么这种方法就不行了。在这种情况下，通过任务类型来划分工作比基于数据划分更合适。
通过给每个线程分配不同数据块在线程间划分工作（无论是事先划分还是处理过程中递归划分）仍然是基于这样的假设，即线程将会基于每个数据块做同样的工作。划分工作的另一种方法是使得线程变得专业化，即每个线程执行不同的任务，就如同建造房子的时候管道工和电工执行不同的任务一样。线程可以基于也可以不基于同样的数据来工作，但是如果基于同样的数据，那也是有不同的目的。
这种划分工作的方式源自于将并发中的关注点分离。每个线程都有不同的任务，并且独立于别的线程来工作。偶尔别的线程可能给它数据或者有触发事件需要处理，但是通常每个线程只做一件事情。这本质上是一个好设计，每块任务都应该只负责一个单一的任务。
当在一段时间内需要持续运行多个任务的时候，或者需要此应用能够及时处理有输入的事件（例如用户键盘输入或者输入网络数据）而不影响别的线程继续执行的时候，单线程应用需要处理与单一任务原则间的矛盾。在单线程环境中，你手工写代码来执行任务A的一部分，执行任务B的一部分，检查键盘输入，检查输入的网络包，然后继续循环执行A的另一部分。这就意味着任务A代码的结束部分会变复杂，因为需要保留它的状态以及周期性地返回控制给主循环。如果你给循环增加了太多任务，运行就会变得很慢，并且使用者会发现键盘输入的响应时间太长。你肯定见过一些应用采取过极端的方式。你设置它处理一些任务，然后接口保持不变直到它完成任务。
这就是线程发生作用的地方。如果你在独立的线程里运行每个任务，操作系统就可以帮你处理这种问题。在任务A的代码中，你可以致力于执行任务，并且不需要担心保留状态以及返回到主循环或者在此之前你花费了多长时间。操作系统将自动地保留状态，然后在适当的时候切换到任务B或C，并且如果系统有多个核或者处理器，任务A和B就可以真正地并行运行。处理键盘输入或者网络包的代码将会运行得很及时，并且皆大欢喜。使用者获得及时响应，你作为开发者可以写更简单的代码，因为每个线程都致力于做与任务直接相关的操作，而不是与控制流和用户互动混合在一起。
看上去这是一个很好的版本。它真的如此吗？如同任何事情一样，它取决于细节。如果每件事情都是独立的，并且线程不需要与另一个线程通信，那么它就确实很简单了。可是，事实却并不是如此。这些后台任务经常做一些用户需要的事情，并且它们需要更新用户接口让用户知道是何时完成这些任务的。或者，用户可能要取消任务，这就会要求用户接口以某种方式给后台任务发送一个消息通知它停止此任务。这两种情况都需要仔细的思考，设计以及适当的同步。但是这些关注点都是分离的。用户接口线程仍然只是处理用户接口，但是当别的线程要求时，它需要更新它的接口。同样，运行后台任务的线程仍然致力于那个任务要求的操作，只有当它的操作是“允许另一个线程停止此任务”。在这两个例子中，线程都不关心该要求是从哪里产生的，只关心它是否是为它们准备的以及与它们的任务是否直接相关。
多个线程关键点分离有两个危害。首先就是你将分离错误的关键点。征兆就是线程间有很多共享数据，或者不同的线程都以等待彼此作为结束。这两种情况都可以归结为线程间有太多的通信。如果发生这种情况，就值得查找产生通信原因。如果所有的通信都与同一件事相关，那么可能那就是单线程的关键任务，并且从所有引用它的线程中获得。或者，如果两个线程彼此之间需要很多通信但是与别的线程通信很少，那么它们就应该联合为一个线程。
当根据任务类型在线程间划分工作的时候，你就不需要局限于完全独立的任务。如果多个数据集合需要应用同样的操作序列，那么就可以划分工作使每个线程执行整个序列中一个步骤。
如果你的任务是由在很多独立数据项上运行同样的操作序列组成的话，就可以使用管道来开发系统可能的并发性。可以将它类比为管道，数据通过一系列操作（管子）从一端流入，并且从另一端流出。
为了用这种方式划分工作，你在管道的每一个步骤都创造一个独立的线程——序列中的每个操作都有一个线程。当操作完成时，数据元素被放入队列中供下一个线程获得。这就允许当管道中第二个线程在操作第一个元素的时候，第一个线程执行序列中的第一个操作来开始下一个数据元素。
这是仅仅在线程间划分数据的一种替代方法，正如8.1.1节中描述的一样，并且在操作开始时并不知道所有输入数据的情况下是适用的。例如，数据可能是通过网络输入的，或者序列的第一个操作就是扫描一个文件系统来识别要处理的文件。
当序列中的每个操作都消耗时间的时候，管道也可以很好地工作。通过在线程间划分任务而不是数据，你改变了性能概况。假设你要在四核上处理20个数据项，并且每个数据项需要四个步骤，每个步骤需要3秒。如果你在四个线程中划分数据，那么每个线程要处理5个数据项。假设没有别的影响时间的处理，12秒后将处理完4个数据项，24秒后将处理完8个数据项，以此类推。1分钟后将处理完所有的20个数据项。如果使用管道，事情就会不一样了。可以将四个步骤中的每个步骤分配到一个处理核上。现在每个核心都要处理第一个元素，因此需要12秒。实际上，12秒后你只处理完一个数据项，这就没有比数据划分的方法好。但是，一旦管道被使用，处理事情就会变得不一样了。在第一个核心处理完的第一项以后，它接着处理第二项。因此一旦最后一个核处理完第一项，它就可以在第二项上执行它的步骤。现在每3秒都可以处理完一个数据项，而不是在每12秒能处理完一批四个数据项。
处理整个分批会花费更长的时间，因为在最后一个核开始处理第一个数据项之前你需要等待9秒。但是更平滑，更有规律的处理在某些环境下可能会很有效。例如，考虑用来收看高清数字电视的系统。为了使电视是可看的，你至少需要每秒25帧并且更多的帧得到更理想的效果。同样，观看者需要它们被均匀地分开来得到持续活动的印象；一个可以每秒解码100帧的应用是没用的，如果它暂停一秒，然后显示100帧，然后再停一秒，然后显示另一个100帧；另一方面，观看者可能很高兴接受当他们开始观看电视的时候有几秒的延迟。在这种情况下，使用管道以一个更好、更稳定的速度并行输出帧可能会更好。
已经看过在线程间划分工作的一些方法，我们来看看影响多线程系统性能的因素以及它是如何影响你选择的方法的。
如果要用并发来提高程序在多处理器环境下的性能，我们需要了解哪些因素会影响。哪怕你只是用多线程来进行关注点分离，你需要确保这不会对性能有负面影响。如果你的程序在16核的机器上跑得比在一台老的单核机器上还更慢，客户可是不会买账的。
接下来，我们会看到有非常多的因素影响多线程程序的性能——哪怕只是改变下每个线程处理的哪部分数据（其他都保持不变）都会对性能有巨大的影响。我们先不进一步展开，从看其中一些明显的因素看起，如你的目标机器有多少个处理器？
处理器的数量和结构是多线程程序的性能的首要和关键的因素。有时你在开发时是知道目标硬件，有目标硬件的规格甚至在一样的硬件上开发。有这种条件你算得上是幸运儿了，但是一般情况我们没这种待遇。也许你是在相似的硬件环境下开发，但是其中的差异会很致命。例如，你在2核或4核的系统下开发，而你的客户可能有多核处理器或者多个单核处理器，乃至多个多核处理器。并发程序的行为和性能在这样不同的环境下会有很大的差异。因此你需要仔细考量会有哪些影响并尽可能地进行测试。
简单近似的话，一个16核处理器等价于4个4核处理器或16个单核处理器，因为它们都可以并发执行16个线程。你的程序至少要有16个线程来利用好这些硬件。如果少于16，就会有处理器性能闲置（除非这个机器还在运行其他程序，我们现在忽略这个情形）；另一方面，如果你有多于16个线程要运行（没有阻塞或等待），会浪费处理器的运算力在切换这些线程上（参见第1章）。这种情况一般被称为过度订阅（oversubscription）。
为了让程序中的线程数量随着硬件能同时运行的线程数量扩展，C++11的标准库提供了std::thread::hardware_concurrency()。我们已经看过使用它的例子。
直接调用std::thread::hardware_concurrency()时需要注意，你的程序并没有考虑机器上运行的其他线程，除非你显式地共享这些信息。最坏的情况是，多个线程同时调用std::thread::hardware_concurrency()会造成严重的过度订阅。而std::async()会在被调用时，由标准库处理所有这些调用并适当地调度，从而避免这个问题。精心设计的线程池也能避免这个问题。
即使你已经考虑了程序中所有运行的线程，你仍然会被其他同时运行的程序影响。尽管在单用户环境下很少有多个CPU密集型任务同时运行，在某些场景下这种情况会更普遍。为这种应用场景设计的系统一般会提供某种机制来让程序选择合适的线程数，当然这已经不在C++标准内了。一种方法是提供类似std::async()的调用，在选择线程数量时考量所有程序异步执行的任务数量。另一种是限制给定程序使用的核的数量。我希望在这样的平台上可以用std::thread::hardware_concurrency()来返回这个数量，不过这取决于具体的系统。如果你需要处理这样的情形，可以去查阅文档了解目标系统提供了哪种方案。
这种情况下随之而来的麻烦是：一个问题的理想算法取决于问题大小和处理单元的数量。如果你在有大量处理单元的大规模并行处理机上运行，耗费操作多的算法可能会比操作少的算法快得多，因为每个处理器只需要处理少量的操作。
随着处理器数量增加，另一个影响性能的问题也出现了，多个处理器访问相同的数据。
如果两个线程同时在不同的处理器上运行，它们同时读取同样的数据通常不会有问题，数据会被复制到各自的缓存，两个处理器都可以继续执行。但是，如果其中一个线程修改了数据，这个修改需要花费时间传播到另一个处理器的缓存。取决于两个线程的操作和这些操作的内存顺序，这样的修改可能导致第二个处理器停下来等待内存硬件传播对数据的修改。从CPU指令来说，这是个相当于数百条指令的显著缓慢的操作，具体的时间主要与硬件的物理结构相关。
考虑下面这段简单代码。
这里的counter是全局的，每个调用processing_loop()的线程都在修改同一个变量。因此，每次在增加时，处理器必须保证它的缓存中有counter的最新拷贝、修改，然后发布到其他处理器。即使你用std::memory_order_relaxed来让编译器不同步其他数据，fetch_add是一个“读-修改-写”操作，因此需要获取变量最新的值。如果其他处理器上的其他线程在运行同样的代码，counter的数据就必须在两个处理器之间来回传递来保证每个处理器在增加时都有最新的counter值。如果do_something()耗时很少，或者有太多的处理器在运行这段代码，处理器可能会处于互相等待的状态。一个处理器已经准备好更新这个值，但是另一个处理器已经在做了，这就要等待另一个处理器更新，并且这个改动已经传播完成，这种情况被称为高竞争（highcontention）。如果处理器很少需要互相等待，则称为低竞争（lowcontention）。
在这样的循环中，counter的数据在各处理器的缓存间来回传递。这被称为乒乓缓存（cacheping-pong），而且会严重影响程序的性能。如果处理器因为需要等待缓存而被挂起，在这个时间里处理器无法进行任何工作，即使有其他线程等待被执行，这对整个程序来说不是个好消息。
也许你会觉得这不会在自己身上发生，因为不会写这样的循环。但是你能确定吗？如互斥锁，如果你在一个循环中获得一个互斥元，你的代码从数据访问的角度看和上面的代码会非常相像。为了锁住互斥元，另一个线程必须从它所在的处理器获得互斥元并修改。当操作完成后，它又修改互斥元来释放，相关的数据必须传递到下一个需要互斥元的线程所在的处理器。这个传递所需的时间是第二个线程等待第一个线程释放互斥元的额外时间。
现在是最棘手的部分：如果数据和互斥元被不止一个线程访问，当你添加更多的核和处理器时，你就越可能面临高竞争，处理器需要等待另一个处理器。如果你更快地用多线程来处理同样的数据，这些线程会竞争这些数据，并竞争同一个互斥元。线程数量越多，就越可能同时试图获取互斥元或者访问某个原子变量。
竞争互斥元的影响通常和竞争原子操作不同，因为使用互斥元在操作系统层面将线程串行化，而不是在处理器层面。如果你有足够的线程等待运行，操作系统会在一个线程等待互斥元时调度另一个线程运行。与之相对的是，处理器的挂起会阻止其他线程在这个处理器上运行。但是，这仍然会影响其他竞争这个互斥元的线程的性能，因为它们每次只有一个会被运行。
在第3章，我们看过如何用一个单写入者，多读取者的互斥元保护很少更新的数据结构的例子（参见3.3.2节）。乒乓缓存会使得只用一个互斥元的好处不明显，特别是工作量大的时候。因为所有访问数据的线程（甚至是读取者仍然需要自己去修改互斥元。随着访问数据的处理器数量上升，互斥元本身的竞争也在增加，包含互斥元的缓存线必须在各个核之间传递，导致获取和释放锁的时间不可接受。你可以用一些方法来改善，主要是通过将互斥元分布在多个缓存线，但这就意味着你要自己去实现这样的互斥元，而不能使用系统本身提供的。
如果乒乓缓存效应有害，我们如何避免呢？本章稍后会揭示，解决方法依赖于提高并发度，尽可能地避免两个线程竞争从一个内存位置。不过这并不容易做到，即使一个特定内存区域只有一个线程会去访问，你仍然会遇到乒乓缓存，因为存在假共享（falsesharing）的问题。
处理器缓存的最小单位通常不是一个内存地址，而是一小块称为缓存线（cacheline）的内存。这些内存块一般大小为32～64字节，取决于具体的处理器。缓存只能处理缓存线大小的内存块，相邻地址的数据会被载入同一个缓存线。有时这是好事，线程访问的数据在同一个缓存线比分布在多个缓存线更好。但是如果缓存线内有不相关但需要被别的线程访问的数据，会导致严重的性能问题。
假设你有一个int型的数组以及一组线程，每个线程都不停访问和改写数组中彼此正交的部分。因为整型的大小通常小于缓存线，数组中的多个元素会出现在同一个缓存线。这样即使线程只访问自己相关的数据，仍然会有乒乓缓存。一个线程在更改其访问的数据时，缓存线的所有权需要转移到其所在的处理器，而另一个线程所需的数据可能也在这个缓存线上，当它访问时缓存线又要再次转移。这个缓存线是两者共享的，然而其中的数据并不共享，因此被称为假共享（falsesharing）。这里的解决方案是构造好数据的结构，使得被同一个线程访问的数据在内存中也是相邻的，这样就更可能出现在同一个缓存线，而不同线程访问的数据则分散在内存中，使之更可能地出现在不同的缓存线。本章稍后会介绍如何根据这个要求设计数据和代码。
如果说多个线程访问同一个缓存线有害，那么单个线程访问的数据的内存布局又有什么影响呢？
假共享是由于一个线程访问的数据与另一个线程的靠得太近，而另一个与数据布局直接相关的性能隐患则来自一个线程本身。根源是数据的相邻度。如果线程访问的数据分散在内存中，意味着这些数据分布在各个缓存线上。因此，更多的缓存线需要加载到处理器的缓存中，这会增加内存访问延迟，性能要低于数据分布紧密的情况。
同时，这也会增加线程需要的某个缓存线同时含有其他线程访问的数据的可能性。极端情况下，缓存中无关的数据会多于你关心的数据。这会浪费宝贵的缓存空间，迫使处理器将需要的数据移出缓存来腾出空间，这样更容易缓存未命中而不得不从内存中获取数据。
这对单线程代码的性能很重要，而我们在这里考虑它的原因是任务切换（taskswitching）。如果有多余CPU核数量的线程，每个核都将运行多个线程。这会增加缓存的压力，因为你要保证不同线程访问不同的缓存线以避免假共享。因此，当处理器切换线程时，数据分散在多个缓存线比每个线程的数据都紧靠在同一个缓存线，更可能需要重载这些缓存线。
如果线程数多于核或者处理器处理，操作系统可能也会选择在一个核上给某个线程分配一个时间片，之后又到另一个核上给这个线程分配时间片。这就需要将这个线程所需的缓存线从第一个核转移到第二个核。需要转移的缓存线越多，消耗的时间也越多。尽管操作系统通常会尽可能避免这种情况，这种现象仍然存在并且一旦发生就会严重影响性能。
任务切换导致的问题在大量线程处于就绪而不是等待状态时特别突出。这是我们已经接触过的问题：过度订阅。
在多线程的系统中，线程数量通常会多于处理器数量，除非你使用的是大规模并行处理机。然而，线程经常花时间等待外部I/O操作完成或者因为互斥元而阻塞，又或者在等待一个条件变量等，因此数量多于处理器并不会带来问题。多出的线程可以让程序进行有用的工作而不是使处理器空闲等待。
但是这不总是好事。当你有太多的线程时，你会有多余可用处理器的就绪线程，操作系统将会开始频繁的任务切换以保证所有线程享有适当的时间片。我们在第1章看到过，这会增加任务切换的额外开销，并且由于数据没有相邻导致的一系列缓存问题。过度订阅会在以下情况产生：你有任务无限制地生成新的线程，如第4章递归调用的快速排序；或者你根据任务类型分配的线程数量大于处理器的数量，而任务更依赖于CPU而不是I/O。
如果你只是因为划分数据产生了太多的线程，你可以简单的限制工作线程的数量，就像我们在8.1.2节见过的一样。如果过度订阅来自于对任务类型的划分，你就没有什么改进的余地了，这时选择合适的划分也许超出了你对目标平台的知识储备，除非性能无法接受而且能证明对划分的改变确实可以提高性能才值得去做。
其他因素也能影响多线程代码的性能。乒乓缓存的代价在两个单核处理器和一个双核处理器上会有很大的差异，哪怕两个平台的CPU类型和时钟频率都一样。以上都是重要的因素，对性能有显著的影响。现在，让我们了解一下这会如何影响我们代码和数据结构的设计。
在8.1节中我们看到了在线程间划分工作的一些方法，在8.2节中我们看到了影响代码性能的一些因素。当设计多线程性能的数据结构的时候如何使用这些信息呢？这是在第6章和第7章中处理的很困难的问题，是关于设计可以安全并行读取的数据结构。正如你在8.2节中看到的一样，即使没有别的线程共享此数据，单个线程使用的数据布局也会对它产生影响。
当为多线程性能设计你的数据结构时需要考虑的关键问题是竞争、假共享以及数据接近。这三个方面都会对性能产生很大影响，并且通常你可以通过改变数据布局或者改变分配给某线程的数据元素来提高性能。首先，我们来看一个简单的例子，在线程间划分数组元素。
假设你正在做一些复杂的数学计算，你需要将两个大矩阵想乘。为了实现矩阵相乘，你将第一个矩阵的第一行每个元素与第二个矩阵的第一列相对应的每个元素相乘，并将结果相加得到结果矩阵左上角第一个元素。然后你继续将第二行与第一列相乘得到结果矩阵第一列的第二个元素，以此类推。正如图8.3所示，突出显示的部分表明了第一个矩阵的第二行与第二个矩阵的第三列配对，得到结果矩阵的第三列第二行的值。
图8.3 矩阵相乘
为了值得使用多线程来优化该乘法运算，现在我们假设这些都有几千行和几千列的大矩阵。通常，非稀疏矩阵在内存中是用一个大数组表示的，第一行的所有元素后面是第二行的所有元素，以此类推。为了实现矩阵相乘，现在就有三个大数组了。为了获得更优的性能，你就需要注意数据存取部分，特别是第三个数组。
有很多在线程间划分工作的方法。假设你有比处理器更多的行/列，那么你就可以让每个线程计算结果矩阵中某些列的值，或者让每个线程计算结果矩阵中某些行的值，或者甚至让每个线程计算结果矩阵中规则矩形子集的值。
回顾8.2.3节和8.2.4节，你就会发现读取数组中的相邻元素比到处读取数组中的值要好，因为这样减少了缓存使用以及假共享。如果你使每个线程处理一些列，那么就需要读取第一个矩阵中的所有元素以及第二个矩阵中相对应的列中元素，但是你只会得到列元素的值。假设矩阵是用行顺序存储的，这就意味着你从第一行中读取N个元素，从第二行中读取N个元素，以此类推（N的值是你处理的列的数目）。别的线程会读取每一行中别的元素，这就很清楚你应该读取相邻的的列，因此每行的N个元素就是相邻的，并且最小化了假共享。当然，如果这N个元素使用的空间与缓存线的数量相等的话，就不会有假共享，因为每个线程都会工作在独立的缓存线上。
另一方面，如果每个线程处理一些行元素，那么就需要读取第二个矩阵中的所有元素，以及第一个矩阵中相关的行元素，但是它只会得到行元素。因为矩阵是用行顺序存储的，因此你现在读取从N行开始的所有元素。如果你选择相邻的行，那么就意味着此线程是现在唯一对这N行写入的线程；它拥有内存中连续的块，并且不会被别的线程访问。这就比让每个线程处理一些列元素更好，因为唯一可能产生假共享的地方就是一块的最后一些元素与下一个块的开始一些元素。但是值得花时间确认目标结构。
第三种选择—划分为矩形块如何呢？这可以被看做是先划分为列，然后划分为行。它与根据列元素划分一样存在假共享问题。如果你可以选择块的列数目来避免这种问题，那么从读这方面来说，划分为矩形块有这样的优点：你不需要读取任何一个完整的源矩阵。你只需要读取相关的目标矩阵的行与列的值。从具体方面来看，考虑两个1000行和1000列的矩阵相乘。就有一百万个元素。如果你有100个处理器，那么每个线程可以处理10行元素。尽管如此，为了计算这10000个元素，需要读取第二个矩阵的所有元素（一百万个元素）加上第一个矩阵相关行的10000个元素，总计1010000个元素；另一方面，如果每个线程处理100行100列的矩阵块（总计10000个元素），那么它们需要读取第一个矩阵的100行元素（100 x 1000=100000个元素）和第二个矩阵的100列元素（另一个100000个元素）。这就只有200000个元素，将读取的元素数量降低到五分之一。如果你读取更少的元素，那么发生缓存未命中和更好性能的潜力的机会就更少了。
因此将结果矩阵划分为小的方块或者类似方块的矩阵比每个线程完全处理好几行更好。当然，你可以调整运行时每个块的大小，取决于矩阵的大小以及处理器的数量。如果性能很重要，基于目标结构分析各种选择是很重要的。
你也有可能不进行矩阵乘法，那么它是否适用呢？当你在线程间划分大块数据的时候，同样的原则也适用于这种情况。仔细观察数据读取方式，并且识别影响性能的潜在原因。在你遇到的问题也可能有相似的环境，就是只要改变工作划分方式可以提高性能而不需要改变基本算法。
好了，我们已经看到数组读取方式是如何影响性能的。其他数据结构类型呢？
从根本上说，当试图优化别的数据结构的数据访问模式时也是适用的。
当然，运用到别的数据结构上是不容易的。例如，二叉树本来就很难用任何方式来再分，有用还是没用，取决于树是如何平衡的以及你需要将它划分为多少个部分。同样，树的本质意味着结点是动态分配的，并且最后在堆上不同地方。
现在，使数据最后在堆上不同地方本身不是一个特别的问题，但是这意味着处理器需要在缓存中保持更多东西。实际上这可以很有利。如果多个线程需要遍历树，那么它们都需要读取树的结点，但是如果树的结点至包含指向该结点持有数据的指针，那么当需要的时候，处理器就必须从内存中载入数据。如果线程正在修改需要的数据，这就可以避免结点数据与提供树结构的数据间的假共享带来的性能损失。
使用互斥元保护数据的时候也有同样的问题。假设你有一个简单的类，它包含一些数据项和一个互斥元来保护多线程读取。如果互斥元和数据项在内存中离得很近，对于使用此互斥元的线程来说就很好；它需要的数据已经在处理器缓存中了，因为为了修改互斥元已经将它载入了。但是它也有一个缺点：当第一个线程持有互斥元的时候，如果别的线程试图锁住互斥元，它们就需要读取内存。互斥元的锁通常作为一个在互斥元内的存储单元上试图获取互斥元的读—修改—写原子操作来实现的，如果互斥元已经被锁的话，就接着调用操作系统内核。这个读—修改—写操作可能导致拥有互斥元的线程持有的缓存中的数据变得无效。只要使用互斥元，这就不是问题。尽管如此，如果互斥元和线程使用的数据共享同一个缓冲线，那么拥有此互斥元的线程的性能就会因为另一个线程试图锁住该互斥元而受到影响。
测试这种假共享是否是一个问题的方法就是在数据元素间增加可以被不同的线程并发读取的大块填充数据。例如，你可以使用：
来测试互斥元竞争问题或者使用：
来测试数组数据是否假共享。如果这样做提高了性能，就可以得知假共享确实是一个问题，并且你可以保留填充数据或者通过重新安排数据读取的方式来消除假共享。
当然，当设计并发性的时候，不仅需要考虑数据读取模式，因此让我们来看看别的需要考虑的方面。
本章我们看了一些在线程间划分工作的方法，影响性能的因素，以及这些因素是如何影响你选择哪种数据读取模式和数据结构的。但是，设计并发代码需要考虑更多。你需要考虑的事情例如异常安全以及可扩展性。如果当系统中处理核心增加时性能（无论是从减少执行时间还是从增加吞吐量方面来说）也增加的话，那么代码就是可扩展的。从理论上说，性能增加是线性的。因此一个有100个处理器的系统的性能比只有一个处理器的系统好100倍。
即使代码不是可扩展的，它也可以工作。例如，单线程应用不是可扩展的，异常安全是与正确性有关的。如果你的代码不是异常安全的，就可能会以破碎的不变量或者竞争条件结束，或者你的应用可能因为一个操作抛出异常而突然终止。考虑到这些，我们将首先考虑异常安全。
异常安全是好的C++代码的一个基本方面，使用并发性的代码也不例外。实际上，并行算法通常比普通线性算法需要你考虑更多关于异常方面的问题。如果线性算法中的操作抛出异常，该算法只要考虑确保它能够处理好以避免资源泄漏和破碎的不变量。它可以允许扩大异常给调用者来处理。相比之下，在并行算法中，很多操作在不同的线程上运行。在这种情况下，就不允许扩大异常了，因为它在错误的调用栈中。如果一个函数大量产生以异常结束的新线程，那么该应用就会被终止。
作为一个具体的例子，我们来回顾清单2.8中的parallel_accumulate函数，清单8.2中会做一些修改。
清单8.2 std::accumulate的并行版本（来自清单2.8）
现在我们检查并且确定抛出异常的位置：总的说来，任何调用函数的地方或者在用户定义的类型上执行操作的地方都可能抛出异常。
首先，你调用distance❷，它在用户定义的迭代器类型上执行操作。因为你还没有进行任何工作，并且这是在调用线程上，所以这是没问题的。下一步，你分配了results迭代器❸和threads迭代器❹。同样，这是在调用线程上，并且你没有做任何工作或者生产任何线程，因此这是没问题的。当然，如果threads构造函数抛出异常，那么就必须清楚为results分配的内存，析构函数将为你完成它。
跳过block_start的初始化❺因为这是安全的，就到了产生线程的循环中的操作❻、❼、❽。一旦在❼中创造了第一个线程，如果抛出异常的话就会很麻烦，你的新std::thread对象的析构函数会调用std::terminate然后中止程序。
调用accumulate_block❾也可能会抛出异常，你的线程对象将被销毁并且调用std::terminate；另一方面，最后调用std::accumulate❿的时候也可能抛出异常并且不导致任何困难，因为所有线程将在此处汇合。
这不是对于主线程来说的，但是也可能抛出异常，在新线程上调用accumulate_block可能抛出异常❶。这里没有任何catch块，因此该异常将被稍后处理并且导致库调用std::terminate()来中止程序。
即使不是显而易见的，这段代码也不是异常安全的。
好了，我们识别出了所有可能抛出异常的地方以及异常所造成的不好影响。那么如何处理它呢？我们先来解决在新线程上抛出异常的问题。
在第4章中介绍了完成此工作的工具。如果你仔细考虑在新线程中想获得什么，那么很明显当允许代码抛出异常的时候，你试图计算结果来返回。std::packaged_task和std::future的组合设计是恰好的。如果你重新设计代码来使用std::packaged_task，就以清单8.3中的代码结束。
清单8.3 使用std::packaged_task的std::accumulate的并行版本
第一个改变就是，函数调用accumulate_block操作直接返回结果，而不是返回存储地址的引用❶。你使用std::packaged_task和std::future来保证异常安全，因此你也可以使用它来转移结果。这就需要你调用std::accumulate❷明确使用默认构造函数T而不是重新使用提供的result值，不过这只是一个小小的改变。
下一个改变就是你用futures向量❸，而不是用结果为每个生成的线程存储一个std::future<T>。在生成线程的循环中，你首先为accumulate_block创造一个任务❹。std::packaged_task<T(Iterator,Iterator)>声明了有两个Iterator并且返回一个T的任务，这就是你的函数所做的。然后你将得到任务的future❺，并且在一个新的线程上运行这个任务，输入要处理的块的起点和终点❻。当运行任务的时候，将在future中捕捉结果，也会捕捉任何抛出的异常。
既然你已经使用了future，就不再有结果数组了，因此必须将最后一块的结果存储在一个变量中❼而不是存储在数组的一个位置中。同样，因为你将从future中得到值，使用基本的for循环比使用std::accumulate要简单，以提供的初始值开始❽，并且将每个future的结果累加起来❾。如果相应的任务抛出异常，就会在future中捕捉到并且调用get()时会再次抛出异常。最后，在返回总的结果给调用者之前要加上最后一个块的结果❿。
因此，这就去除了一个可能的问题，工作线程中抛出的异常会在主线程中再次被抛出。如果多于一个工作线程抛出异常，只有一个异常会被传播，但是这也不是一个大问题。如果确实有关的话，可以使用类似std::nested_exception来捕捉所有的异常然后抛出它。
如果在你产生第一个线程和你加入它们之间抛出异常的话，那么剩下的问题就是线程泄漏。最简单的方法就是捕获所有异常，并且将它们融合到调用joinable()的线程中，然后再次抛出异常。
现在它起作用了。所有线程将被联合起来，无论代码是如何离开块的。尽管如此，try-catch块是令人讨厌的，并且你有复制代码。你将加入正常的控制流以及捕获块的线程中。复制代码不是一个好事情，因为这意味着需要改变更多的地方。我们在一个对象的析构函数中检查它，毕竟，这是C++中惯用的清除资源的方法。下面是你的类。
这与清单2.3中的thread_guard类是相似的，除了它扩展为适合所有线程。你可以如清单8.4所示简化代码。
清单8.4 std::accumulate的异常安全并行版本
一旦你创建了你的线程容器，也就创建了一个新类的实例❶来加入所有在退出的线程。你可以去除你的联合循环，只要你知道无论函数是否退出，这些线程都将被联合起来。注意调用futures[i].get()❷将被阻塞直到结果出来，因此在这一点并不需要明确地与线程融合起来。这与清单8.2中的原型不一样，在清单8.2中你必须与线程联合起来确保正确复制了结果向量。你不仅得到了异常安全代码，而且你的函数也更短了，因为将联合代码提取到你的新（可再用的）类中了。
你已经知道了当处理线程时需要什么来实现异常安全，我们来看看使用std::async()时需要做的同样的事情。你已经看到了，在这种情况下库为你处理这些线程，并且当future是就绪的时候，产生的任何线程都完成了。需要注意到关键事情就是异常安全，如果销毁future的时候没有等待它，析构函数将等待线程完成。这就避免了仍然在执行以及持有数据引用的泄漏线程的问题。清单8.5所示就是使用std::async()的异常安全实现。
清单8.5 使用std::async的std::accumulate的异常安全并行版本
这个版本使用递归将数据划分为块而不是重新计算将数据划分为块，但是它比之前的版本要简单一些，并且是异常安全的。如以前一样，你以计算序列长度开始❶，如果它比最大的块尺寸小的话，就直接调用std::accumulate❷。如果它的元素比块尺寸大的话，就找到中点❸然后产生一个异步任务来处理前半部分![序号❹。范围内的第二部分就用一个直接的递归调用来处理❺，然后将这两个块的结果累加❻。库确保了std::async调用使用了可获得的硬件线程，并且没有创造很多线程。一些“异步”调用将在调用get()的时候被异步执行❻。
这种做法的好处在于它不仅可以利用硬件并发，而且它也是异常安全的。如果递归调用抛出异常❺，当异常传播时，调用std::async❹创造的future就会被销毁。它会轮流等待异步线程结束，因此避免了悬挂线程。另一方面，如果异步调用抛出异常，就会被future捕捉，并且调用get()❻将再次抛出异常。
当设计并发代码的时候还需要考虑哪些方面呢？让我们来看看可扩展性。如果将你的代码迁移到更多处理器系统中会提高多少性能呢？
可扩展性是关于确保你的应用可以利用系统中增加的处理器。一种极端情况就是你有一个完全不能扩展的单线程应用，即使你在系统中增加100个处理器也不会改变性能。另一种极端情况是你有类似SETI@Home[3]的项目，被设计用来利用成千上万的附加的处理器（以用户将个人计算机增加到网络中的形式）。
对于任何给定的多线程程序，当程序运行时，执行有用工作的线程的数量会发生变化。即使每个线程都在做有用的操作，初始化应用的时候可能只有一个线程，然后就有一个任务生成其他的线程。但是即使那样也是一个不太可能发生的方案。线程经常花时间等待彼此或者等待I/O操作完成。
除非每次线程等待事情（无论是什么事情）的时候都有另一个线程在处理器上代替它，否则就有一个可以进行有用工作的处理器处于闲置状态。
一种简单的方法就是将程序划分为只有一个线程在做有用的工作“串行的”部分和所有可以获得的处理器都在做有用工作的“并行的”部分。如果你在有更多处理器的系统上运行你的应用，理论上就可以更快地完成“并行”部分，因为可以在更多的处理器间划分工作，但是“串行的”部分仍然是串行的。在这样一种简单假设下，你可以通过增加处理器数量来估计可以获得的性能。如果“连续的”部分组成程序的一个部分
，那么使用N个处理器获得的性能P就可以估计为
这就是阿姆达尔定律（Amdahl’slaw），当谈论并发代码性能的时候经常被引用。如果所有事情都能被并行，那么串行部分就为0，加速就是N。或者，如果串行部分是三分之一，即使有无限多的处理器，你也不会得到超过3的加速。
尽管如此，这是一种很理想的情况。因为任务很少可以像方程式所需要的那样被无穷划分，并且所有事情都达到它所假设的CPU界限是很少出现的。正如你看到的，线程执行的时候会等待很多事情。
阿姆达尔定律中有一点是明确的，那就是当你为性能使用并发的时候，值得考虑总体应用的设计来最大化并发的可能性，并且确保处理器始终有有用的工作来完成。如果你可以减少“串行”部分或者减少线程等待的可能性，你就可以提高在有更多处理器的系统上的性能。或者，如果你可以为系统提供更多的数据，并且保持并行部分准备工作，就可以减少串行部分，增加性能P的值。
从根本上说，可扩展性就是当增加更多的处理器的时候，可以减少它执行操作的时间或者增加在一段时间内处理的数据数量。有时这两点是相同的（如果每个元素可以处理得更快，那么你就可以处理更多数据），但是并不总是一样的。在选择在线程间划分工作的方法之前，识别出可扩展性的哪些方面对你很重要是很必要的。
在这部分的开始我就提到过线程并不是总有有用的工作来做。有时它们必须等待别的线程，或者等待I/O操作完成，或者别的事情。如果在等待中你给系统一些有用的事情，你就可以有效的“隐藏”等待。
在很多关于多线程代码性能的讨论中，我们都假设当它们真正在处理器上运行时，线程在“全力以赴”的运行并且总是有有用的工作来做。这当然不是正确的，在应用代码中，线程在等待的时候总是频繁地被阻塞。例如，它们可能在等待一些I/O操作的完成，等待获得互斥元，等待另一个线程完成一些操作并且通知一个条件变量，或者只是休眠一段时间。
无论等待的原因是什么，如果你只有和系统中物理处理单元一样多的线程，那么有阻塞的线程就意味着你在浪费CPU时间。运行一个被阻塞的线程的处理器不做任何事情。因此，如果你知道一个线程将会有相当一部分时间在等待，那么你就可以通过运行一个或多个附加线程来使用那个空闲的CPU时间。
考虑一个病毒扫描应用，它使用管道在线程间划分工作。第一个线程搜索文件系统来检查文件并且将它们放到队列中。同时，另一个线程获得队列中的文件名，载入文件，并且扫描它们的病毒。你知道搜索文件系统的文件来扫描的线程肯定会达到I/O界限，因此你就可以通过运行一个附加的扫描线程来使用“空闲的”CPU时间。那么你就有一个搜索文件线程，以及与系统中的物理核或者处理器相同数量的扫描线程。因为扫描线程可能也不得不从磁盘读取文件的重要部分来扫描它们，拥有更多扫描线程也是很有意义的。但是在某个时刻会有太多线程，系统会再次慢下来因为它花了更多时间切换程序，正如8.2.5节所描述的。
仍然，这是一个最优化问题，因此测量线程数量改变前后的性能时很重要的；最有的线程数量将很大程度上取决于工作的性质和线程等待的时间所占的比例。
取决于应用，它也可能用完空闲的CPU时间而没有运行附加的线程。例如，如果一个线程因为等待I/O操作的完成而被阻塞，那么使用可获得的异步I/O操作就很有意义了。那么当在背后执行I/O操作的时候，线程就可以执行别的有用的工作了。在别的情况下，如果一个线程在等待另一个线程执行一个操作，那么等待的线程就可以自己执行那个操作而不是被阻塞，正如第7章中的无锁队列。在一个极端的情况下，如果线程等待完成一个任务并且该任务没有被其他线程执行，等待的线程可以在它内部或者另一个未完成的任务中执行这个任务。清单8.1中你看到了这个例子，在排序程序中只要它需要的块没有排好序就不停地排序它。
有时它增加线程来确保外部事件及时被处理来增加系统响应性，而不是增加线程来确保所有可得到的处理器都被应用了。
很多现代图形用户接口框架是事件驱动的，使用者通过键盘输入或者移动鼠标在用户接口上执行操作，这会产生一系列的事件或者消息，稍后应用就会处理它。系统自己也会产生消息或者事件。为了确保所有事件和消息都能被正确处理，通常应用都有下面所示的一个事件循环。
显然，API的细节是不同的，但是结构通常是一样的，等待一个事件，做需要的操作来处理它，然后等待下一个事件。如果你有单线程应用，就会导致长时间运行的任务很难被写入，如8.1.3节描述的。为了确保用户输入能被及时处理，get_event()和process()必须以合理的频率被调用，无论应用在做什么操作。这就意味着要么任务必须定期暂停并且将控制交给事件循环，要么方便的时候在代码中调用get_event()/process()代码。每一种选择都将任务的实现变得复杂了。
通过用并发分离关注点，你就可以将长任务在一个新线程上执行，并且用一个专用的GUI线程来处理事件。线程可以通过简单的方法互相访问，而不是必须以某种方式将事件处理代码放到任务代码中。清单8.6列出了这种分离的简单概括。
清单8.6 从任务线程中分离GUI线程
通过这种方式分离障碍，用户线程能够及时地响应事件，即使任务要执行很长时间。这种响应性通常是使用应用时用户体验的关键。无论何时执行一个特定操作（无论该操作是什么），应用都会被完全锁住，这样使用起来就不方便了。通过提供一个专用的事件处理线程，GUI可以处理GUI特有的消息（例如调整窗口大小或者重画窗口）而不会中断耗时处理的执行，并且当它们确实影响长任务时会传递相关的消息。
本章你看到了设计并发代码的时候需要考虑的问题。就整体而言，这些问题是很大的，但是当你习惯了“多线程编程”，它们就会变得得心应手了。如果这些考虑对你来说很新，那么希望当你看到它们是如何影响多线程代码的具体例子的时候，可以变得更清晰。
当为一个特别的任务设计并发代码的时候，你需要事先考虑每个描述的问题的程度将取决于任务。为了演示它们是如何应用的，我们将看看C++标准库中三个函数并行版本的实现。这将给你一个类似的构造基础，提供了考虑问题的平台。作为奖励，我们也有可用的函数实现，可用来帮助并行一个更大的任务。
我选择这些实现主要是用来演示特别的方法而不是成为最高水平的实现。在并行算法学术文献或者在多线程库例如Inter’s Threading Building Blocks[4]中可以找到更高程度的实现，它们更好地利用了可获得的硬件并发性。
概念上最简单的并行算法是std::for_each的并行版本，我们就先从它 开始。
std::for_each在概念上很简单，它轮流在范围内的每个元素上调用用户提供的函数。std::for_each的并行实现和串行实现的最大区别就是函数调用的顺序。std::for_each用范围内的第一个元素调用函数，然后是第二个，以此类推。然而使用并行实现就不能保证元素被处理的顺序，它们可能（实际上我们希望）被并发处理。
为了实现并行版本，你只需要将这个范围划分为元素集合在每个线程上处理。你事先知道了元素数量，因此你可以在处理开始前划分数据（参见8.1.1节）。我们假设这是唯一在运行的并行任务，那么就可以使用std::thread::hardware_ concurrency()来决定线程的数量。你也知道元素可以被独立地处理，因此你可以使用临近的块来避免假共享（参见8.2.3节）。
这个算法与8.4.1节中描述的std::accumulate的并行版本在概念上是类似的，但是不计算每个元素的和，你只要应用具体函数。尽管你可能推测这会大大简化代码，因为它不返回结果。如果你想传递异常给调用者，你仍然需要使用std::packaged_task和std::future方法在线程间传递异常。一个简单的实现如清单8.7所示。
清单8.7 std::for_each的并行版本
这段代码的基础结构与清单8.4中的代码是一样的。关键的不同之处在于futures向量存储了std::future<void>❶，因为工作线程不返回值，并且在这个任务上使用一个简单lambda函数激活了从block_start到block_end范围上的函数f❷。这就避免了将范围传递给线程构造函数❸。因为工作线程不返回值，调用future[i].get()❹只提供取回工作线程抛出的异常的方法，如果你不希望传递异常，那么你就可以省略它。
正如你的std::accumulate的并行实现可以通过使用std::async被简化，因此你的parallel_for_each也可以被简化。它的实现如清单8.8所示。
清单8.8 使用std::async的std::for_each的并行版本
如同清单8.5中基于std::async的parallel_accumulate一样，你递归地划分数据而不是在执行前划分数据，因为你不知道库会使用多少线程。如以前一样，每一步都将数据划分为两部分，异步运行前半部分❷并且直接运行后半部分❸直到剩下的数据太小而不值得划分，在这种情况下会调用std::for_each❶。使用std::async和get()成员函数std::future❹提供了异常传播语义。
让我们从必须在每个元素上执行相同操作的算法转移到稍微复杂的例子std::find。
std::find是下一个考虑的有用的算法，因为它是不用处理完所有元素就可以完成的几个算法之一。例如，如果范围内的第一个元素符合搜索准则，那么就不需要检查别的元素。稍后你将看到，这是性能的一个重要属性，并且对设计并行实现有直接影响。这是数据读取部分可能影响代码设计的一个特殊例子（参见8.3.2节）。这类别的算法包括std::equal和std::any_of。
如果你和你的妻子或者搭档在阁楼的两箱纪念品中寻找一张旧相片，如果你找到了相片就应该让他们也停止寻找。你要让他们知道你已经找到了相片（可以通过呼喊，“找到了”），这样他们就可以停止寻找并且做别的事情。很多算法的天性是处理每个元素，因此它们没有呼喊“找到了”。对于算法例如std::find，早日完成的能力是一个重要的特性并且不浪费任何事情。因此你需要设计你的代码来使用这个特性——当知道结果的时候用一些方式中断别的任务，因此代码不需要等待别的工作线程处理剩下的元素。
如果你不中断别的线程，串行版本比并行版本的性能更好，因为串行算法一旦找到匹配项就停止搜索并且返回。例如，如果系统可以支持四个并发线程，每个线程将检查范围内四分之一的元素，并且我们的并行算法大约花费单个线程四分之一的时间来检查每个元素。如果匹配的元素位于范围内的前四分之一，串行算法会首先返回，因为它不需要检查剩下的元素。
你可以中断别的线程，一种方法是通过使用一个原子变量作为一个标志，并且在处理完每个元素后检查这个标志。如果设置了标志，就代表有一个线程发现了匹配项，因此就可以终止执行并且返回了。用这种方法中断别的线程，你保持了你不需要处理每个值的特性，因此在更多的情况下与串行版本相比提高了性能。这种方法的缺点是原子载入变成慢动作，这就会妨碍每个线程的前进。
关于如何返回值和如何传递异常你有两个选择。你可以使用future数组，使用std::packaged_task来转移值和异常，然后在主线程中处理返回的结果；或者你使用std::promise来从工作线程中直接设置最终结果。如果你希望在第一个异常处停止（即使你没有处理完所有元素），你可以使用std::promise来设置值和异常。另一方面，如果你希望允许别的工作线程继续搜索，你可以使用std::packaged_task，存储所有的异常，那么没有发现匹配项的时候就重新抛出其中之一。
在这种情况下，我选择使用std::promise，因为行为更匹配std::find。这里要注意的一件事情就是要搜索的元素不在提供的范围内。因此在从future得到结果之前你需要等待所有线程结束。如果你在future上阻塞了并且没有这个值的话，你就会永远等待。结果如清单8.9所示。
清单8.9 并行find算法的一种实现
清单8.9的主函数与之前的例子很相似。这次，在本地find_element类的函数调用操作上完成工作➊。这个循环访问给定的块的每个元素，每一步都检查标志➋。如果找到匹配项，就在promise中设置最后的结果➌并且在返回前设置done_flag➍。
如果抛出异常，就可以被捕获➎，并且在设置done_flag前在promise中存储异常➏。如果promise已经被设置了，再设置值就有可能抛出异常，因此你捕获并且抛弃发生在这里的异常➐。
这就意味着如果一个线程调用find_element，要么找到匹配项要么抛出异常，此时所有别的线程都会看到done_flag被设置了并且停止执行。如果多个线程同时找到匹配项或者抛出异常，它们就会在设置promise值的时候产生竞争。但是这是一个没有危害的竞争条件，无论哪一个线程成功都会成为名义上的“第一个”并且是一个可接受的结果。
回顾主函数parallel_find本身，你用promise➑和flag➒来停止搜索，这两者都传递给在这个范围内搜索的新线程⓫。主线程也使用find_element来搜索剩下的元素⓬。我们已经说过，你在检查结果之前需要等待所有线程结束，因为可能没有匹配的元素。你通过在块中附入线程连接的代码来完成➓，因此当你检查标志来看看是否发现匹配项的时候，所有线程都被联合起来了⓭。如果发现匹配项，你就可以通过在std::future<iterator>中调用get()得到结果或者抛出存储的异常⓮。
同样，这个实现假设你将使用所有可获得的硬件线程或者你有别的方法来决定线程数量，用来提前在线程间划分工作。跟以前一样，在使用C++标准库的自动扩展功能的时候，你可以使用std::async和递归数据划分来简化你的实现。使用std::async的parallel_find实现如清单8.10所示。
清单8.10 使用std::async的并行查找算法的实现
如果你找到匹配项就结束查找，意味着你需要引入一个在线程间共享的标志，用来表示已经找到该匹配项。因此这就需要传递给所有递归调用。实现它最简单的方法就是通过在实现函数上➊附加参数——引用done标志，这是从主入口点传递进来的⓬。
核心实现在类似的代码行里继续执行。与很多实现相同，你在单线程上设置处理项的最小值➋。如果你不能将它划分为都至少达到设置的大小的两部分，就在当前线程上运行所有的事情➌。实际算法是处理具体范围的简单循环，一直循环直到范围结束或者设置了done标志➍。如果你查找到匹配项，就在返回前设置done标志➎。如果你停止查找，要么因为你已经到达范围的末端，要么因为另一个线程设置了done标志。你返回last用来表示在这里没有匹配项➏。
如果范围可以被划分，你在使用std::async前首先发现中点➐，以便在范围的后半部分进行查找➑，小心使用std::ref来传递done标志的引用。同时，你可以通过直接递归调用在范围的前半部分进行查找➒。如果原来的范围太大的话，这个异步调用和直接递归可能导致进一步的划分。
如果直接搜索返回mid_point，那么就没有找到匹配项，你就需要得到异步搜索的结果。如果那部分没有发现结果，结果就将是last，这是正确的返回值表明没有查找到这个值➓。如果“异步的”调用被延迟而不是真正的异步，它在调用get()的时候才真正运行，在这种情况下，如果在后半部分查找到了就跳过搜索范围的前半部分。如果异步搜索已经在另一个线程上运行了，async_result变量的析构函数将等待线程完成。这样就不会有任何泄露线程。
如同以前一样，使用std::async提供了异常安全和异常传递特性。如果直接递归抛出异常，future的析构函数将确保运行异步调用的线程在函数返回前就结束了。并且如果异步调用抛出异常，这个异常就通过get()调用传递➓。使用一个try/catch块是为了在异常上设置done标志并且确保如果抛出异常的话所有线程很快终止⓫。没有它，实现仍然是正确的，但是会继续检查元素直到每个线程都结束了。
这个算法的两种实现与另一种并行算法共享的主要特点就是不再保证项目按照从std::find得到的顺序来处理。如果你想并行算法这一点是很基础的。如果顺序很重要的话，你就不能并发处理元素。如果元素是独立的，就可以使用parallel_for_each。但是这意味着你的parallel_find可能返回范围尾部的元素，即使它与范围头部的元素匹配。
好了，你已经处理了并行化std::find。正如我在这一节开头说的那样，存在别的类似算法可以在不处理每个数据元素的情况下完成，并且可以使用同样的方法。我们将在第9章中进一步讨论中断线程的问题。
为了完成我们的例子，我们将从不同的方面来考虑并且看看std::partial_sum。这个算法是一个很有趣的并行算法并且强调了一些附加的设计选择。
std::partial_sum计算了一个范围内的总和，因此每个元素都被这个元素与它之前的所有元素的和所代替。所以序列1、2、3、4、5就变成1、(1+2)=3、(1+2+3)=6、(1+2+3+4)=10、(1+2+3+4+5)=15。它的并行化是很有趣的，因为你不能将范围划分为块然后单独计算每个块。例如，第一个元素的原始值需要加到每一个别的元素上。
一种用来决定范围内部分和的方法就是计算独立块的部分和，然后将第一个块中计算得到的最后一个元素的值加到下一个块的元素中，并以此类推。如果你有元素1,2,3,4,5,6,7,8,9并且你将它分成三个块，首先你得到{1,3,6}、{4,9,15}、{7,15,24}。如果你将6加到第二个块的所有元素上，你就得到{1,3,6}、{10,15,21}、{7,15,24}。然后你将第二个块的最后一个元素{21}加到第三个块的元素上，这样最后一个块得到最后的值：{1,3,6}、{10,15,21}、{28,36,55}。
同原始划分成块一样，也可以并行加上前一个块的部分和。如果每个块的最后一个元素首先被更新，那么当第二个线程更新下一个块的时候，第一个线程可以更新这个块中剩下的元素，并且以此类推。当列表中的元素多于处理核的时候，这种方法很有效，因为每个核每一步都要处理大量元素。
如果你有很多处理核（同元素数量一样，或者多于元素数量），这种方法就不是很有效了。如果你在处理器间划分工作，第一步以元素对结束工作。这这种条件下，这种进一步传递结果意味着很多处理器会等待，因此你需要给它们分配工作。你可以采用另一种方法对待这个问题。你做部分传递，而不是从一个块到下一个块做全部和的传递。首先像之前一样求和相邻的元素，然后将这些和加到与它相隔两个的元素上，然后再将得到的值加到与它相隔四个的元素上，以此类推。如果你以同样的九个元素开始，第一轮后你得到1,3,5,7,9,11,13,15,17，这就得到前两个元素最后的值。第二轮后你得到1,3,6,10,14,18,22,26,30，它的前四个元素是正确的。第三轮后你得到1,3,6,10,15,21,18,36,44，它的前八个元素是正确的。第四轮后你得到1,3,6,10,15,21,18,36,45，这就是最终答案。尽管它比第一种方法的总步骤数要多，但是如果你有很多线程的话，它有更大的余地来并行化，每个处理器每一步都能更新一个入口。
总的说来，第二种方法执行log2(N)个步骤，每一个步骤执行大约N个操作（每个线程处理一个），其中N是表中的元素数量。第一种算法中，每个线程为分配给它的块的最初分段求和执行
个操作，然后为进一步的传递执行个操作，k是线程数量。因此从总的操作数来说，第一种方法是O(N)，第二种方法是O(N log (N))。尽管如此，如果你的处理器与列表中的元素一样多，那么第二种方法中每个处理器只需要log(N)个操作。而当k很大时，第一种方法本质上是串行操作，因为需要进一步传递值。对于拥有很少处理单元的系统，第一种方法可以更快结束，而对于大规模并行系统，第二种方法可以更快结束。8.2.1节讨论了这个问题的一个极端的例子。
无论如何，先不考虑效率问题，我们来看一些代码。清单8.11所示的是第一种方法。
清单8.11 通过划分问题来并行计算分段的和
在这个例子中，总体结构与之前的代码是一样的，划分问题为块，每个线程拥有最小化的块尺寸⓬。在这种情况下，与线程向量一样⓭，你有一个promise向量⓮用来存储块中最后一个元素的值，并且还有一个future向量⓯，用来得到前一个块的最后一个值。你可以保留future的空间⓰来避免在生成线程的时候再分配，因为你知道将有多少线程。
主循环与以前的一样，只是这次你希望迭代器指向每个块中的最后一个元素本身，而不是通常情况下那样指向最后元素的后继⓱，因此在每个范围你都可以传递最后一个元素。真正的处理是在process_chunk函数对象中完成的，我们稍后再分析。需要给的参数包括这个块的开始和结束的迭代器，先前范围的终值（如果存在的话），这个范围的终值存放的位置⓲。
产生线程后，你就可以更新这个块的起点，记住将它的值加一使它位于最后一个元素之后⓳，并且将当前块的最后一个值的future存储到future向量中，这样下一次循环的时候就可以得到它⓴。
在你处理最后一个块之前，你需要得到最后一个元素的迭代器
，这样你就可以传递到process_chunk中
。std::partial_sum不返回值，因此一旦最后一个块被处理了，你不需要做任何操作。当所有线程结束的时候这个操作就完成了。
现在我们来看看process_chunk函数对象在整个工作中所起的作用➊。首先在整个块上调用std::partial_sum，包括最后一个元素➋，但是然后就需要知道这是否为第一个块➌。如果这不是第一个块，那么在先前块中就有previous_end_value，因此你就需要等待这个值![序号➍。为了最大化算法的并发性，你就需要首先更新最后一个元素➎，因此你将值传递给下一个块（如果存在的话）➏。一旦完成了这些操作，你就可以使用std::for_each和一个简单的lambda函数➐来更新这个范围内剩下的元素。
如果没有previous_end_value，那么这就是第一个块，因此你可以只更新下一个块的end_value()（同样，如果存在下一个块的话——这可能是仅有的块）➑。
最后，如果任何操作抛出异常，你捕捉到它➒并且将它存储在promise中➓。这样当它试图得到先前的最后一个值的时候就会传递给下一个块了➍。这会将所有的异常都传递给最后一个块，然后被重新抛出⓫，因为你知道这是运行在主线程上。
因为线程间的同步，这段代码就不容易控制与std::async一起重写。等待结果的任务中途通过别的任务的执行，因此所有任务都必须同时运行。
使用基于块，向前传输的方法是很少见的，让我们来看看计算范围内部分和的第二种方法。
当你的处理器可以按部就班地执行加法，通过累加越来越远的元素来计算部分和的方法可以工作得很好。在这种情况下，不需要进一步的同步，因为所有中间结果都会直接传递给下一个需要它们的处理器。但是实际上，你很少可以在这样的系统上工作，除非你的系统支持少量数据元素上同时执行操作的指令，即所谓的单指令/多数据（Single-Instruction/Multiple-Data，SIMD)指令。因此，你必须为通常情况设计代码并且每一步都明确地同步线程。
一种方法是使用屏障（barrier）——一种同步方法使得线程等待直到要求的线程已经到达了屏障。一旦所有线程到达屏障，它们就可以继续执行而不阻塞了。C++11线程库没有直接提供这样的工具，因此你需要自己设计。
想象一下游乐园里的过山车。如果有合适数量的人在等待，游乐园职员就会确保在过山车离开平台之前每个座位都有人。屏障的工作原理也是一样的，你提前指定“座位”的数量，并且线程必须等待直到所有“座位”都是满的。一旦有足够的等待线程，就可以继续执行；屏障被重置并且开始等待下一批线程。通常，在循环中使用此构造，在那里同一线程再次出现并且等待下一次。这个想法是为了使线程按部就班地工作，因此一个线程不会在别的线程前面离开以及掉队。对于这个算法，这就会造成灾难，因为离开的线程可能会修改别的线程正在使用的数据，或者使用还没有被正确更新的数据。
无论如何，清单8.12给出了屏障的一个简单实现。
清单8.12 一个简单的屏障类
在这个实现中，你构造了一个barrier，它具有一定数量“座位”❶，存储在count变量中。最初，屏障中spaces的数量与count相等。当每个线程等待的时候，spaces的数量就会减 1❸。当它的值为零的时候，spaces的值就会重置为count❹，并且generation的值增一来给别的线程发信号表示它们可以继续执行❺。如果空闲spaces的数量没有达到零，你就必须等待。这个实现使用一种简单旋转锁❻，检查在wait()开始的时候得到的值。因为当所有线程到达屏障的时候才会更新generation的值❺，等待的时候调用yield()❼，因此在一个繁忙的等待中，等待的线程不会独占CPU。
当我说这个实现是简单的，我的意思是它使用一个旋转锁，因此它不适合线程可能等待很长时间的情况。并且如果在任何一个时间有多于count数量的线程可能调用wait()，那么它就不起作用了。如果你想处理这些情况中的任何一种，你就必须使用一个更健壮性（但是更复杂）的实现来代替。我遵循了在原子变量上的顺序连续操作，因为这使得事情更容易解释，但是你可以放松一些顺序约束。在大规模并发结构上，这样的全局同步是代价很高的，因为缓存线持有屏障的状态必须在所有涉及到的线程间穿梭（参见8.2.2节），因此你必须注意确保在这里这是最好的选择。
无论如何，在这里这就是你所需要的，你有固定数量的线程在循规蹈矩的循环中运行。当然，这只是几乎固定数量的线程。你可能记得，在一些步骤后，列表开始的项获得它的最终值。这就意味着要么你保持这些线程循环直到处理完整个范围，要么你需要允许屏障处理线程退出并且减少count。我倾向于后面一种选择，因为它避免了使线程只是循环而不做任何有用的工作直到最后一步完成。
这就意味着你需要将count变成一个原子变量，因此你可以从多个线程更新它而不需要额外的同步。
它的初始化是一样的，但是现在当你重置spaces的值的时候就必须明确在count中load()。
这些都是在wait()上所做的改变；现在你需要一个新的成员函数来减少count。我们称之为done_waiting()，因为一个线程声称在等待的时候完成它。
你做的第一件事是递减count的值❶，这样下一次重置spaces就反映新的等待线程的数量。然后你需要将空闲spaces的数目递减❷。如果不这么做，别的线程就会永远等待，因为spaces被初始化为旧的，更大的值。如果这是分支上的最后一个线程，你就需要重置counter并且增加generation❸，就如你在wait()中所做的那样。在完成所有的等待后就结束了。
现在你准备好写部分和的第二种实现了。在每一步，每个线程在屏障上调用wait()来保证线程步骤一起，并且一旦每个线程都完成了，就在屏障上调用done_waiting()来减少count。如果你在初始范围内使用第二个缓冲器，屏障提供你所需要的所有同步。在每一步中，线程从原先的范围或者缓冲器中读取，并且将新值写入相关元素中。如果线程在一个步骤中读取了原先的范围，它们在下一个步骤中读取缓冲器，反之亦然。这就确保了在不同线程的读取和写操作中没有竞争条件。一旦一个线程结束循环，它必须确保正确的最终值被写入最初的范围中。清单8.13给出了所有的操作。
清单8.13 通过成对更新的partial_sum的并行实现
现在你已经很熟悉这段代码的总体结构了。你用一个拥有函数调用操作的类（process_element）来做这个工作❶，你在存储在向量中❽的一些线程❾上运行它并且在主线程调用它❿。这次的主要不同之处在于线程数量取决于列表中项的数量而不是取决于std::thread::hardware_concurrency。正如我所说，除非你是在一个线程很便宜的大量并行机器上运行，这不是一个好方法，但是它显示了总体结构。也可以用较少的线程，每个线程处理源范围的多个值。但是这也会出现一个问题，那就是有足够少的线程使得它比向前传输算法的效率还要低。
无论如何，在process_element函数调用操作中完成了关键工作。每一步你要么从原先的范围得到第i个元素要么从缓冲器得到第i个元素❷，并且将它添加到stride元素的值中❸，如果从原先的范围开始就将它存储在缓冲器中，或者如果从缓冲器开始就存储在原先的范围中❹。然后在开始下一步之前你在屏障上等待❺。当stride使你离开范围的起点时你就完成操作了。在这种情况下，如果你的最终结果存储在缓冲器中的话，就更新原先范围里的元素❻。最后，你告诉屏障你正在done_waiting()❼。
注意这种情况不是异常安全的。如果一个工作线程在process_element上抛出异常，就会终止此引用。你可以使用std::promise存储异常来处理这种情况，正如你在清单8.9的parallel_find实现中所做的一样，或者使用互斥元保护的std::exception_ptr。
这总结了我们的三个例子，希望它们有助于具体化8.1，8.2和8.3中强调的设计考虑，并且证明在真实代码中可以使用这些方法。
本章我们涉及很多基础知识。我们从在线程间划分工作的多种方法开始，如提前划分数据或者使用许多线程来形成管道。然后我们从低水平角度考虑与多线程代码的性能紧密相关的问题，在转移到数据读取是如何影响代码性能之前考虑了假共享和数据竞争问题。然后我们考虑了设计并发代码时候要考虑的问题，如异常安全和可扩展性。最后，我们以一些并发算法实现的例子作为结束，每一个例子都强调了当设计多线程代码时可能出现的具体问题。
本章出现几次的一个事情就是线程池的想法——一组事先配置的线程运行分配给线程池的任务。很多想法被用在设计一个好的线程池上，因此下一章我们将考虑一些问题，以及高级线程管理的别的方面。
[3] http://setiathome.ssl.berkeley.edu/
[4] http://threadingbuildingblocks.org/
