随着多核处理器的普及，如果你还希望成为一名有雇佣价值的程序员，那么除了学习和掌握并发编程技术外，你将别无选择。
实现并发编程的途径不止一种，也有特别为并发编程特别设计的语言，如 Erlang。不过，在可以预见的将来，线程仍然会是一种主流的并发编程方法。
并发编程入门
并发编程的核心内容是指计算机能够以任何顺序来执行的独立计算（Independent Computation）。例如，在代码中可独立执行的循环迭代和函数调用都属于独立计算。要想将并发工作分配到多个线程上，需要调用一些实现了线程化机制的库函数。这些额外的函数调用将增加并发执行的开销（overhead），因为在最初的串行代码中并不包含这些函数调用。任何为了控制和协调线程而增加的额外代码，尤其是调用线程化库函数的代码，同样是一种开销。。
此外，还需要增加一部分代码来判断计算是应该继续执行，还是应该获取更多的工作或者在满足指定的条件时触发其他线程，这也是需要考虑的开销。
采用线程化方法的4个步骤
不建议一开始就编写并发的代码，因为可能会同时存在两种类型的问题：在算法或者实现中的逻辑错误，以及在代码中与线程相关的问题。建议编写一个能正确使用的串行代码，然后分析如何将其转换为并发代码。
第 1 步 找出并发性
找出哪些代码可以通过线程模型来实现；也就是找出应用程序中包含了独立计算的代码。
试着找出时间消耗最多的位置后，就可以开始执行这些位置的代码，并判断它们是否可以并发执行。然而，消耗最多执行时间并不一定就意味着代码可以被修改为并发执行。你必须通过对代码的算法进行分析来判断这段代码是否足够高的独立性以支持并发执行。尽管如此，查找程序中执行时间消耗最多的代码部分，还是可以达到事半功倍的效果的。
第 2 步 设计与实现：采用线程来实现算法
考虑将串行代码修改为并发代码。
第 3 步 测试正确性：检测并修复在线程化时引入的错误
多线程的程序可能正确运行了数百次，但在另一个系统上运行该程序时，仍然有可能出现错误。有时候，代码正常运行出现错误，但在调试器（甚至是一个能够感知线程的调试器）下运行代码，单步执行的特性可能会掩盖正在分析的错误。通过 print 语句输出变量的值则可能修改线程交替执行的时间，同样可能隐藏错误。
通过缜密的措施防止线程化常见的错误（如数据竞争和死锁等），就可以彻底避免这些错误。但如果在编程语言中使用了指针和间接引用，那么问题是无法预见的。有可能会遇到某个错误显现取决于输入的数据。
即使消除了由于修改代码引入的错误后，代码仍然有可能无法获得和单线程代码一样的结果。如果只是细微的误差，那么可能是舍入造成的。因为在多线程的环境下合并的顺序和串行合并结果的顺序可能并不相同。如果偏差的很大，那么有可能是引入了某个逻辑错误。
第 4 步 性能调优：消除性能瓶颈
最后一步是确保代码能够以最高的性能运行。在改写成线程化代码之前，首先要确保串行程序的代码已经调整为最优性能。如果在对代码进行线程化之后再对其串行执行进行调优，可能会改变代码的整体行为，并使得增加的线程化代码反而降低了程序的性能。
并行算法的背景知识
理论模型
研究算法的基本处理器架构之一：随机访问机（Random Access Machine，RAM）。这是冯诺伊曼架构的简化模型，在这种模型中包含了所有的基本组件：CPU、输入设备、输出设备以及随机访问内存。为了更加符合实际机器，还可以将缓存（Cache）层次结构加入到内存中，将一个随机访问磁盘作为输入和输出的单个设备。然而，无论怎么修改，这个模型的基本架构仍然是保持不变的。
RAM 模型图
在设计并行算法时，有的研究人员使用了 RAM 模型的一种变化形式，称为并行随机访问机（Parallel Random Access Machine，PRAM）。简单来说，PRAM 就是多个 CPU 连接到无限大的内存，并且这个内存在所有CPU之间是共享的。
PRAM 模型图
假设在这些 CPU 上执行的多个线程是步调一致的，即所有的线程都同时执行同一条指令，然后再同时执行下一条指令，以此类推。无论处理器的数量多少，对于内存位置的访问时间都是相同的。通常不考虑这些 CPU 与内存之间的连接方式，除非某种特殊的配置方式有可能对算法的设计会造成影响。
分布式内存编程
20世纪80年代末期90年代早期，由于共享总线的连接问题，基于共享内存模型的并行计算机在处理器的使用数量上达到了一个上限，即最多不超过32个处理器。于是，研究人员提出了分布式内存（Distributed-Memory）模型以进一步提高处理器的数量。
并行算法需要对数据进行一定程度的共享，然而分布式内存各个节点是相互独立的，没有直接的共享机制，开发人员需要通过各种函数库在各个节点之间传递消息。
例如：在分布式内存编程中，假定处理器1（P1）需要获得来自处理器0（P0）的一组值。在 P0 上运行的程序需要将这组值封装到一个缓冲区中，并且调用函数将缓冲区从 P0 所在的节点发送到网络上，然后将缓冲区的内容传入到 P1 所在节点的内存中。
在 P1 所在的节点上，程序必须调用接收函数以接收传入到节点内存的数据，并且将数据复制到内存中某个指定的缓冲区由 P1 访问。
随着时间的推移，有了可以移植的库，例如：PVM（Parallel Virtual Machine，并行虚拟机）以及 MPI（Message-Passing Interface，消息传递接口）。PVM 能够将一组互连的计算机改造成一个虚拟并行机，并且这个虚拟并行机的开销要小于专门并行平台的开销。MPI 是一个实现消息传递功能的标准库，这些功能在并行机或者一组互连的计算机上都被支持。
共享内存编程与分布式内存编程的比较
共有功能
冗余工作
无论一个算法的并发程度如何，在程序中仍然存在一部分代码必须串行执行。需要用到串行执行计算的结果时，可以在其中一个进程中执行串行计算，然后将计算结果广播传递到其他需要该结果的进程。在发送消息的过程中需要一定的开销。
另一种方式：每个线程都执行相同的串行计算并生成结果，这样就无需发送任何信息。尽管在多个线程中执行冗余的工作会使得处理资源保持忙碌的状态，并且极大地减少同步操作的数量，但却需要消耗更多的内存来保存同一个值的多个副本。
共享数据
在某些情况下，应用程序需要共享数据。例如，某个计数器的值，或者一组浮点数，或者一组图顶点（Graph vetex）。无论是哪种情况，线程／进程都需要在计算过程中访问到这些数据。
在共享内存模型中，程序只需要访问内存中指定的位置，而在分布式内存中，程序必须通过发送和接收消息来共享数据。
工作的静态／动态分配
静态分配：一次性分配完所有工作（通常在计算开始的时候）
动态分配：随着代码的执行逐渐分配工作。（需要时才会分配工作）
通常，如果可以工作分解的数量等于线程／进程的数量，并且总的执行时间就大致等于每一部分工作的执行时间之和，那么静态分配就是最优的分配方式。采用静态分配方法的代码通常是最容易实现和维护的。
当工作的数量远远多于线程的数量，并且每部分工作的执行时间都不相同或者无法在计算开始时知道，那么就应该采用动态分配的方式。动态分配会有开销，但是带来的好处是执行过程中的负载更加均匀。
共享内存模型特有功能
在共享内存中所有东西都是共享的，然而在某些情况下需要使用私有的或者局部的变量，并且这个变量只能由一个线程访问。Windows 线程和 POSIX 线程中都定义了线程局部存储（Thread-Local Storage，TLS）API。虽然在不同的线程化库中有着不同的实现方式，但这些 API 的作用都是为了线程分配私有内存，并且允许线程存储和提取一个只能由该线程访问的值。
TLS 与局部变量的不同之处在于，TLS 中的值在不同的函数调用之间将保持不变。这种行为非常像静态变量的行为，只不过在 TLS 中，每个线程都将获得一个单独的值。
内存效应
由于处理器核上的内存对于所有在该核上执行的线程来说都是共享的，因此会出现由于共享而带来的性能问题。我在前面已经提到了写入冲突和数据竞争。处理器架构将决定着线程是否共享缓存还是各自访问独立的缓存。如果在两个处理器核之间共享缓存，那么线程可用的缓存数量将减半，而如果各自使用独立的缓存，那么在共享数据时将变得低效。对于一些需要经常访问的只读数据来说，共享缓存是非常高效的，因为只需要一个副本。
伪共享是指，虽然线程并没有访问同一个变量，但它们各自访问的不同变量都被包含在同一条缓存线（Cache Line）中。根据缓存一致性协议，当某个线程更新缓存线中的一个变量时，如果另一个线程希望访问该缓存线中的其他内容时，需要首先将该缓存线写回到内存中。当两个或者多个线程不断更新同一条缓存线时，那么这条缓存线将在内存与缓存之间反复地移动。
内存中的通信
在基于分布式内存的程序中，共享数据是通过在进程之间发送和接收消息来实现的。而在共享内存模型中共享数据时，一个线程只需将值写入到某个内存位置，而其他线程从这个内存位置上读取这个值。当然，要确保数据被正确地读取，写入数据的线程必须在读取数据的线程访问该共享内存位置之前首先将值写入。因此，我们必须对写入线程和读取线程进行同步。发送/接收消息的模式其实是分布式进程之间一种隐式的同步形式。
互斥
在某些情况下，当多个线程需要在内存中相互通信时，必须保护对共享内存位置的访问。实现这种保护的方法就是，每次只允许一个线程访问这些共享变量。这也被称之为互斥（Mutual Exclusion）。有几种不同的同步机制可以用来实现互斥（具体采用何种机制通常取决于你所使用的线程化方法）。
读取数据的操作和写入数据的操作都必须被保护。如果多个线程读取同一个数据，那么这种行为不会导致任何问题。当有多个线程写入同一个内存位置时，写入操作的执行顺序将决定着最终写入到这个内存位置的值，以及其他线程从这个内存位置读出的值（如航空订票系统中两个乘客得到同一个座位的情况）。当有一个线程读取某个内存位置而另一个线程写入这个内存位置时，如果没有正确地同步，那么可能读取到两个不同的值（旧值或者新值）。在这两个值中，很可能只有一个值是我们预期的值，因为在最初的串行代码中认为只会出现一个值。如果并发算法的正确执行需要依赖某个变量的特定值，而这个变量由多个线程更新，那么你必须确保在正确的时间写入正确的值；这就需要使用互斥以及其他同步机制。
生产者/消费者
在分布式内存程序中，一种用来将数据或者分配任务到不同进程的方法就是老板/工人（boss/worker）方法。“工人”进程向“老板”进程发送消息以请求新任务；在收到请求后，“老板”进程将回送消息/任务/数据给“工人”进程。你可以编写一种在多个线程中分配任务的“老板/工人”机制，但需要非常多的同步。
要采用共享内存模型，那么你需要对“老板/工人”方式做一些变化，使用一个共享队列来分配任务。这种模型被称之为“生产者/消费者”模型。生产者线程将创建任务并将它们存储到共享队列中。当消费者线程需要执行工作时，它们将从共享队列中提取任务。你必须通过某种形式的互斥来保护对共享队列的访问，从而确保任务被正确地插入到队列中，并且从队列中取出的任务也只能被分配给一个线程。
读/写锁
由于多个线程在同时读取共享变量时不会产生问题，因此在多个读取线程上使用互斥就会不必要地产生性能瓶颈。不过，如果有任何线程试图更新共享变量，那么就必须使用互斥。但当共享变量的更新操作远少于读取操作时，可以使用读/写锁（Reader/Writer Lock）来作为同步对象。
读/写锁允许多个读取线程进入访问共享变量的代码保护区。当有线程试图更新（写入）共享变量的值时，这个锁将确保之前的读线程首先全部执行完成，然后再允许写入线程执行更新操作。当读/写锁允许某个写入线程访问共享变量时，新的读取线程或者其他写入线程都将不能执行，直到当前的写入线程执行完成。
网友评论