第十二章 并发编程

csapp
loading...

并发编程

12.1 基于进程的并发编程

构造并发程序最简单的方法就是用进程，使用那些大家都很熟悉的函数，像 fork,exec 和 waitpid例如，一个构造并发服务器的自然方法就是，在父进程中接受客户端连接请求，然后创建一个新的子进程来为每个新客户端提供服务。

12.1.1 基于进程的并发服务器

图 12-5 展示了一个基于进程的并发 echo 服务器的代码。

  • 首先，通常服务器会运行很长的时间，所以我们必须要包括一个 SIGCHLD 处理程序，来回收僵死(zombie)子进程的资源（第 4~9 行）。 因为当 SIGCHLD 处理程序执行时，SIGCHLD 信号是阻塞的，而 Linux 信号是不排队的，所以 SIGCHLD 处理程序必须准备好回收多个僵死子进程的资源。
  • 其次，父子进程必须关闭它们各自的 fd（分别为第 33 行和第 30 行）副本。就像我们已经提到过的，这对父进程而言尤为重要，它必须关闭它的已连接描述符，以避免内存泄漏。
  • 最后，因为套接字的文件表表项中的引用计数，直到父子进程的 cormfd都关闭了，到客户端的连接才会终止。


图 12-5 基于进程的并发 echo 服务器。父进程派生一个子进程来处理每个新的连接请求

12.1.2 进程的优劣

对于在父、子进程间共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来，一个进程不可能不小心覆盖另一个进程的虚拟内存，这就消除了许多令人迷惑的错误来， 这是一个明显的优点。

另一方面，独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，它们必须使用显式的 IPC(进程间通信）机制。（参见下面的旁注。）基于进程的设计的另一个缺点是，它们往往比较慢，因为进程控制和 IPC 的开销很高。

12.2 基于 I/O 多路复用的并发编程

假设要求你编写一个 echo 服务器，它也能对用户从标准输人键入的交互命令做出响应。在这种情况下，服务器必须响应两个互相独立的 I/O 事件：1)网络客户端发起连接请求，2）用户在键盘上键人命令行。我们先等待哪个事件呢？没有哪个选择是理想的。如果在 accept 中等待一个连接请求，我们就不能响应输人的命令。类似地，如果在 read 中等待一个输入命令，我们就不能响应任何连接请求。

针对这种困境的一个解决办法就是 I/O 多 路复用（I/O multiplexing）技术。基本的思路就是使用 select 函数，要求内核挂起进程，只有在一个或多个 I/O 事件发生后，才将控制返回给应用程序，就像在下面的示例中一样：

  • 当集合{0, 4}中任意描述符准备好读时返回。
  • 当集合{1，2, 7}中任意描述符准备好写时返回。
  • 如果在等待一个 I/O 事件发生时过了 152.13 秒，就超时。

select 是一个复杂的函数，有许多不同的使用场景。我们将只讨论第一种场景：等待一组描述符准备好读。

1
2
3
4
5
6
7
8
9
10
#include <sys/select,h>
int select(int n, fd_set *fdset, NULL, NULL, NULL);
// 返回已准备好的描述符的非零的个数，若出错则为 一1,

FD_ZERO(fd_set *fdset);  /* Clear all bits in fdset */
FD_CLR(int fd, fd.set *fdset); /* Clear bit fd in fdset */
FD_SET(int fd, fd_set *fdset); /*Turn on bit fd in fdset */
FD_ISSET(int fd, fd_set *fdset)j /* Is bit fd in fdset on? */

// 处理描述符集合的宏。

select 函数处理类型为 fd_set 的集合，也叫做描述符集合。逻辑上，我们将描述符
集合看成一个大小为n的位向量（在 2.1 节中介绍过）：

bn-1 … b1 b0

每个位bk对应于描述符k。当且仅当 bk = 1，描述符k才表明是描述符集合的一个元素。只允许你对描述符集合做三件事：1）分配它们，2）将一个此种类型的变量赋值给另一个变量，3）用 FD_ZERO、FD_SET、FD_CLR 和 FD_ISSET 宏来修改和检査它们。

针对我们的目的，select 函数有两个输入：一个称为读集合的描述符集合（fdset）和该读集合的基数（n）(实际上是任何描述符集合的最大基数）。 select 函数会一直阻塞，直到读集合中至少有一个描述符准备好可以读。当且仅当一个从该描述符读取一个字节的请求不会阻塞时，描述符々就表示准备好可以读了。select 有一个副作用，它修改参数fdset 指向的 fd_set，指明读集合的一个子集，称为准备好集合（ready set), 这个集合是由读集合中准 好可以读了的描述符组成的。该函数返回的值指明了准备好集合的基数。注意，由于这个副作用，我们必须在每次调用 select 时都更新读集合。

12.2.1 基于 I/O 多路复用的并发事件驱动服务器

I/O 多路复用可以用做并发事件驱动（event-driven）程序的基础，在事件驱动程序中，某些事件会导致流向前推进。一般的思路是将逻辑流模型化为状态机。不严格地说，一个状态机(state machine)就是一组状态(state)、输入事件(input event)和转移(transition)，其中转移是将状态和输人事件映射到状态。每个转移是将一个（输人状态，输人事件）对映射到一个输出状态。自循环(self-loop)是同一输人和输出状态之间的转移。通常把状态机画成有向图，其中节点表示状态，有向弧表示转移，而弧上的标号表示输人事件。一个状态机从某种初始状态开始执行。每个输入事件都会引发一个从当前状态到下一状态的转移。

对于每个新的客户端 I 基于 I/O 多路复用的并发服务器会创建一个新的状态机sk并将它和已连接描述dk符义联系起来。如图 12-7 所示，每个状态机 都有一个状态（“等待描述符 A准备好可读”）、 一个输入事件(“描述符 A准备好可以读了”)和一个转移（“从描述符 A读一个文本行”）。


图 12-7 并发事件驱动 echo 服务器中逻辑流的状态机

服务器使用 I/O 多路复用，借助 select 函数检测输入事件的发生。当每个已连接描述符准备好可读时，服务器就为相应的状态机执行转移，在这里就是从描述符读和写回一个文本行。

12.2.2 I/O 多路复用技术的优劣

事件驱动设计的一个优点是，它比基于进程的设计给了程序员更多的对程序行为的控制。例如，我们可以设想编写一个事件驱动的并发服务器，为某些客户端提供它们需要的服务，而这对于基于进程的并发服务器来说，是很困难的。

另一个优点是，一个基于 I/O 多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都能访问该进程的全部地址空间。这使得在流之间共享数据变得很容易。一个与作为单个进程运行相关的优点是，你可以利用熟悉的调试工具，例如 GDB,来调试你的并发服务器，就像对顺序程序那样。最后，事件驱动设计常常比基于进程的设计要高效得多，因为它们不需要进程上下文切换来调度新的流。

事件驱动设计一个明显的缺点就是编码复杂。我们的事件驱动的并发 echo 服务器需要的代码比基于进程的服务器多三倍，并且很不幸，随着并发粒度的减小，复杂性还会上升。这里的粒度是指每个逻辑流每个时间片执行的指令数量。

12.3 基于线程的并发编程

到目前为止，我们已经看到了两种创建并发逻辑流的方法。在第一种方法中，我们为每个流使用了单独的进程。内核会自动调度每个进程，而每个进程有它自己的私有地址空间，这使得流共享数据很困难。在第二种方法中，我们创建自己的逻辑流，并利用 I/O 多路复用来显式地调度流。因为只有一个进程，所有的流共享整个地址空间。本节介绍第三种方法棗 基于线程，它是这两种方法的混合。

线程（thread）就是运行在进程上下文中的逻辑流。在本书里迄今为止，程序都是由每个进程中一个线程组成的。但是现代系统也允许我们编写一个进程里同时运行多个线程的程序。线程由内核自动调度。每个线程都有它自己的线程上下文（thread context）, 包括一个唯一的整数线程 HXThreadlD，TID）、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。

基于线程的逻辑流结合了基于进程和基于 I/O 多路复用的流的特性。同进程一样，线程由内核自动调度，并且内核通过一个整数 ID 来识别线程。同基于 I/O 多路复用的流一样，多个线程运行在单一进程的上下文中，因此共享这个进程虚拟地址空间的所有内容，包括它的代码、数据、堆、共享库和打开的文件。

12.3.1 线程执行模型

多线程的执行模型在某些方面和多进程的执行模型是相似的。思考图 12-12 中的示例。每个进程开始生命周期时都是单一线程，这个线程称为主线程（main thread）在某 一时刻，主线 程创建一个对 等线程(peer thread), 从这个时间点开始，两个线程就并发地运行。最后，因为主线程执行一个 慢速系 统调用，例如 read 或者sleep。或者因为被系统的间隔计时器中断，控制就会通过上下文切换传递到对等线程。对等线程会执行一段间，然后控制传递回主线程，依次类推。

在一些重要的方面，线程执行是不同于进程的。因为一个线程的上下文要比一个进程的上下文小得多，线程的上下文切换要比进程的上下文切换快得多。另一个不同就是线程不像进程那样，不是按照严格的父子层次来组织的。和一个进程相关的线程组成一个对等（线程）池，独立于其他线程创建的线程。主线程和其他线程的区别仅在于它总是进程中第一个运行的线程。对等（线程）池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。另外，每个对等线程都能读写相同的共享数据。


图 12-12 并发线程执行

12.3.2 Posix 线程

Posix 线程(Pthreads)是在 C 程序中处理线程的一个标准接口。它最早出现在 1995年，而且在所有的 Linux 系统上都可用。Pthreads 定义了大约 60 个函数，允许程序创建、杀死和回收线程，与对等线程安全地共享数据，还可以通知对等线程系统状态的变化。

12.3.3 创建线程

线程通过调用 pthread_create 函数来创建其他线程。

1
2
3
4
5
#include <pthread.h>
typedef void *(func)(void *);
int pthread_create(pthread_t *tid, pthread_attr_t *attr,
func *f, void *arg);
// 若成功则返回 0，若出错则为 非零。

pthread_create 函数创建一个新的线程，并带着一个输入变量 arg 在新线程的上下文中运行线程例程 f。 能用 attr 参数来改变新创建线程的默认属性。改变这些属性已超出我们学习的范围，在我 们的示 例中，总是用一个为 NULL 的 attr 参数来调用pthread_create 函数。

当 pthread_create 返回时，参数 tid 包含新创建线程的 ID。新线程可以通过调用pthread_self 函数来获得它自己的线程 ID。

1
2
3
#include <pthread.h>
pthread_t pthread_self(void);
// 返回调用者的线程 ID

12.3.4 终止线程

一个线程是以下列方式之一来终止的

  • 当顶层的线程例程返回时，线程会隐式地终止。
  • 通过调用 pthread_exit 函数，线程会显式地终止，如果主线程调用 pthread_exit，它会等待所有其他对等线程终止，然后再终止主线程和整个进程，返回值为thread return。
1
2
3
#include <pthread.h>
void pthread_exit(void *thread_return);
// 从不返回。
  • 某个对等线程调用 Linux 的 exit 函数，该函数终止进程以及所有与该进程相关的线程。
  • 另一个对等线程通过以当前线程 ID 作为参数调用 pthread_cancel 函数来终止当前线程。
1
2
3
#include <pthread.h>
int pthread_cancel(pthread_t tid);
// 若成功则返回 0，若出错则为 非零。

12.3.5 回收已终止线程的资源

线程通过调用 pthread_join 函数等待其他线程终止。

1
2
3
#include <pthread.h>
int pthread_join(pthread_t tid, void **thread_return);
// 若成功则返回 0，若出错则为非零。

pthreadjoin 函数会阻塞，直到线程 tid 终止，将线程例程返回的通用（void*）针赋值为 thread_return 指向的位置，然后回收已终止线程占用的所有内存资源。

注意，和 Linux 的 wait 函数不词，pthread_join 函数只能等待一个指定的线程终止。没有办法让 pthread_wait 等待任意一个线程终止。这使得代码更加复杂，因为它迫使我们去使用其他一些不那么直观的机制来检测进程的终止。

12.3.6 分离线程

在任何一个时间点上，线程是可结合的（joinable）或者是分离的（detached)。一个可结合的线程能够被其他线程收回和杀死。在被其他线程回收之前，它的内存资源（例如栈）是不释放的。相反，一个分离的线程是不能被其他线程回收或杀死的。它的内存资源在它终止时由系统自动释放。

默认情况下，线程被创建成可结合的。为了避免内存泄漏，每个可结合线程都应该要么被其他线程显式地收回，要么通过调用 pthread_detach 函数被分离。

1
2
3
#include <pthread.h>
int pthread_detach(pthread_t tid);
// 若成功则返回 0，若出错则为非零

pthread_detach 函数分离可结合线程 tid。线程能够通过以 pthread_self()为参数的 pthread_detach 调用来分离它们自己。

尽管我们的一些例子会使用可结合线程，但是在现实程序中，有很好的理由要使用分离的线程。例如，一个高性能 Web 服务器可能在每次收到 Web 浏览器的连接请求时都创建一个新的对等线程。因为每个连接都是由一个单独的线程独立处理的，所以对于服务器而會S 就很没有必要（实际上也不愿意）显式地等待每个对等线程终止。在这种情况T,每个对等线程都应该在它开始处理请求之前分离它自身，这样就能在它终止后回收它的内存资源了。

12.3.7 初始化线程

pthread_once 函数允许你初始化与线程例程相关的状态。

1
2
3
4
5
#include <pthread.h>
pthread_once_t once_control = PTHREAD_ONCE_INIT;
int pthread_once(pthread_once_t *once_control,
void (*init_routine)(void));
// 总是返回 0。

once_control 变量是一个全局或者静态变量,总是被初始化为 PTHREAD_ONCE_INIT。当你第一次用参数once_control调用 pthread_once 时它调用 init_routine ,这是一个没有输人参数、也不返回什么的函数。接下来的以once_control为参数的 pthread_once调用不做任何事情。无论何时，当你需要动态初始化多个线程共享的全局变量时， pthread_once函数是很有用的。

12.4 多线程程序中的共享变量

从程序员的角度来看，线程很有吸引力的一个方面是多个线程很容易共享相同的程_序变量。然而，这种共享也是很棘手的。为了编写正确的多线程程序，我们必须对所谓的共享以及它是如何工作的有很清楚的了解。

为了理解 C 程序中的一个变量是否是共享的，有一些基本的问题要解答？I) 线程的基础内存模型是什么？2): 根据这个模型，变量实例是如何映射到内存的？3)最后，有多少线程引用这些实例？一个变量是共享的，当且仅当多个线程引用这个竣量的某个实例。

为了让我们对共享的讨论具体化，我们将使用图 12-15 中的程序作为运籽示例。尽管有些人为的痕迹，但是它仍然值得研究，因为它说明了关于共享的许多细微之处。示例程序由一个创建了两个对等线程的主线程组成。主线程传递一个唯一的 ID 给每个对等线程，每个对等线程利用这个 ID 输出一条个性化的信息，以及调用该线程例程的总次数。

12.4.1 线程内存模型

一组并发线程运行在一个进程的上下文中。每个线程都有它自己独立的线程上下文，包括线程 ID、栈、栈指针、程序计数器、条件码和通用目的寄存器值。每个线程和其他线程一起共享进程上下文的剩余部分。这包括整个用户虚拟地址空间，它是由只读文本（代码）、 读/写数据、堆以及所有的共享库代码和数据区域组成的。线程也共享相同的打开文件的集合。

从实际操作的角度来说，让一个线程去读或写另一个线程的寄存器值是不可能的。另一方面，任何线程都可以访问共享虚拟内存的任意位置。如果某个线程修改了一个内存位置，那么其他每个线程最终都能在它读这个位置时发现这个变化。因此，寄存器是从不共享的，而虚拟内存总是共享的。

各自独立的线程栈的内存模型不是那么整齐清楚的。这些栈被保存在虚拟地址空间的栈区域中，并且通常是被相应的线程独立地访问的。我们说通常而不是总是，是因为不同的线程栈是不对其他线程设防的。所以，如果一个线程以某种方式得到一个指向其他线程栈的指针，那么它就可以读写这个栈的任何部分。示例程序在第 26 行展示了这一点，其中对等线程直接通过全局变量 ptr 间接引用主线程的栈的内容。


图 12-15 说明共享不同方面的示例程序

12.4.2 将变量映射到内存

多线程的 C 程序中变量根据它们的存储类型被映射到虚拟内存：

  • 全局变量。全局变量是定义在函数之外的变量。在运行时，虚拟内存的读/写区域只包含每个全局变量的一个实例，任何线程都可以引用。
  • 本地自动变量。本地自动变量就是定义在函数内部但是没有 static 属性的变量。在运行时，每个线程的栈都包含它自己的所有本地自动变量的实例。即使多个线程执行同一个线程例程时也是如此。
  • 本地静态变量。本地静态变量是定义在函数内部并有 static 属性的变量。和全局变量一样，虚拟内存的读/写区域只包含在程序中声明的每个本地静态变量的一个实例。

12.5 用信号量同步线程

共享变量是十分方便，但是它们也引入了同 步错误(synchronization error)的可能性。

12.5.1 进度图

进度图(progress graph)将 n 个并发线程的执行模型化为一条 n 维笛卡儿空间中的轨迹线。每条轴 k 对应于线程 k 的进度。每个点(I1,I2,…,In)代表线程k(k=1,…,n)已经完成了指令 h这一状态。图的原点对应于没有任何线程完成一条指令的初始状态。

进度图将指令执行模型化为从一种状态到另一种状态的转换(transition)。转换被表示为一条从一点到相邻点的有向边。合法的转换是向右（线程 1 中的一条指令完成）或者向上（线程 2 中的一条指令完成）的。两条指令不能在同一时刻完成–对角线转换是不允许的。程序决不会反向运行，所以向下或者向左移动的转换也是不合法的。

在进度图中，两个临界区的交集形成的状态空间区域称为不安全区(unsafe region)。

绕开不安全区的轨迹线叫做安全轨迹线（safe trajectory） 相反，接触到任何不安全区的轨迹线就叫做不安全轨迹线（unsafe trajectory）。


图 12-21 安全和不安全轨迹线。临界区的交集形成了不安全区。绕开不安全区的轨迹线能够正确更新计数器变量

12.5.2 信号量

EdsgerDijkstra, 并发编程领域的先锋人物，提出了一种经典的解决同步不同执行线
程问题的方法，这种方法是基于一种叫做信号量(semaphore)的特殊类型变量的信号量 s
是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为 P 和 V:

  • P(s): 如果 s 是非零的，那么 P 将 s 减 1，并且立即返回。如果 s 为零，那么就挂起这个线程，直到 s 变为非零，而一个 V 操作会重启这个线程。在重启之后，P 操作将 s 减 1，并将控制返回给调用者。
  • V(s): V 操作将 s 加 1。如果有任何线程阻塞在 P 操作等待 s 变成非零，那么 V 操作会重启这些线程中的一个，然后该线程将 s 减 1，完成它的 P 操作。

P 中的测试和减 1 操作是不可分割的，也就是说，一旦预测信号量 s 变为非零，就会将 减s 1，不能有中断。V 中的加 1 操作也是不可分割的，也就是加载、加 1 和存储信号量的过程中没有中断。注意，V 的定义中没有定义等待线程被重启动的顺序。唯一的要求是 V 必须只能重启一个正在等待的线程。因此，当有多个线程在等待同一个信号量时，你不能预测 V 操作要重启哪一个线程。

P 和 V 的定义确保了一个正在运行的程序绝不可能进人这样一种状态，也就是一个正确初始化了的信号量有一个负值。这个属性称为信号量不变性(semaphore invariant)为控制并发程序的轨迹线提供了强有力的工具，

Posix 标准定义了许多操作信号量的函数。

1
2
3
4
5
#include <semaphore.h>
int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */
// 返回：若成功则为 0, 若出错则为 一1。

sem _init 函数将信号量 sem 初始化为 value。每个信号量在使用前必须初始化。针对我们的目的，中间的参数总是零。程序分别通过调用 sem_wait 和 sem_Post函数来执行 P 和 V 操作。为了简明，我们更喜欢使用下面这些等价的 P 和 V的包装函数：

1
2
3
4
#include "csapp.h"
void P(sem_t *s); /* Wrapper function for sem_wait */
void V(sem_t *s); /* Wrapper function for sem_post */
// 返回：无。

12.5.3 使用信号量来实现互斥

信号量提供了一种很方便的方法来确保对共享变量的互斥访问。基本思想是将每个共享变量(或者一组相关的共享变量）与一个信号量 K初始为 1)联系起来，然后用 P(s)和 V(s)操作将相应的临界区包围起来。

以这种方式来保护共享变量的信号量叫做二元信号量(binary semaphore), 因为它的值总是 0 或者 1。以提供互斥为目的的二元信号量常常也称为互斥锁(mutex)。在一个互斥锁上执行 P 操作称为对互斥锁加锁。类似地，执行 V 操作称为对互斥锁解锁。对一个互斥锁加了锁但是还没有解锁的线程称为占 用这个互斥锁。一个被用作一组可用资源的计数器的信号量被称为计数信号量。

图 12-22 中的进度图展示了我们如何利用二元信号量来正确地同步计数器程序示例。每个状态都标出了该状态中信号量 s 的值。关键思想是这种 P 和 V 操作的结合创建了组状态，叫做禁止区(forbidden region), 其中 s<0。因为信号量的不变性，没有实际可行的轨迹线能够包含禁止区中的状态。而且，因为禁止区完全包括了不安全区，所以没有实际可行的轨迹线能够接触不安全区的任何部分。因此，每条实际可行的轨迹线都是安全的，而且不管运行时指令顺序是怎样的，程序都会正确地增加计数器值。

从可操作的意义上来说，由 P 和 V 操作创建的禁止区使得在任何时间点上，在被包围的临界区中，不可能有多个线程在执行指令。换句话说，信号量操作确保了对临界区的互斥访问。

总的来说，为了用信号量正确同步图 12-16 中的计数器程序示例，我们首先声明一个信号量 mutex:

1
2
volatile long cnt = 0; /* Counter */
sem_t mutex; /* Semaphore that protects counter */

然后在主例程中将 mutex 初始化为 1:

Sem_init(toutex, 0, 1); /* mutex = 1 */

最后，我们通过把在线程例程中对共享变量 cnt 的更新包围 P 和 V 操作，从而保护它们:

1
2
3
4
5
for (i = 0; i < niters; i++) {
    P(&mutex);
    cnt++;
    V(&emutex);
}

当我们运行这个正确同步的程序时，现在它每次都能产生正确的结果了。

1
2
3
4
linux> ,/goodcnt 1000000
OK cnt=2000000
linux> ,/goodcnt 1000000
OK cnt=2000000

12.5.4 利用信号量来调度共享资源

除了提供互斥之外，信号量的另一个重要作用是调度对共享资源的访问。在这种场景中，一个线程用信号量操作来通知另一个线程，程序状态中的某个条件已经为真了。两个经典而有用的例子是生产者-消费者和读者-写者问题。

12.5.5 综合：基于预线程化的并发服务器

我们已经知道了如何使用信号量来访问共享变量和调度对共享资源的访问。为了帮助你更清晰地理解这些思想，让我们把它们应用到一个基于称为预线程化(prethreading)妨术的并发服务器上。

在图 12-14 所示的并发服务器中，我们为每一个新客户端创建了一个新线程。这种方法的缺点是我们为每一个新客户端创建一个新线程，导致不小的代价。一个基于预线程化的服务器试图通过使用如图 12-27 所示的生产者-消费者模型来降低这种开销。服务器是由一个主线程和一组工作者线程构成的。生线程不断地接受来自客户端的连接请求，并将得到的连接描述符放在一个有限缓冲区中。每一个工作者线程反复地从共享缓冲区中取出描述符，为客户端服务，然后等待下一个描述符。


图 12-27 预线程化的并发服务器的组织结构。一组现有的线程不断地取出和处理来自有限缓冲区的已连接描述符

12.6 使用线程提高并行性

到目前为止，在对并发的研究中，我们都假设并发线程是在单处理器系统上执行的。然而，大多数现代机器具有多核处理器。并发程序通常在这样的机器上运行得更快，因为操作系统内核在多个核上并行地调度这些并发线程，而不是在单个核上顺序地调度。在像繁忙的 Web 服务器、数据库服务器和大型科学计算代码这样的应用中利用这样的并行性是至关重要的，而且在像 Web 浏览器、电子表格处理程序和文档处理程序这样的主流应用中，并行性也变得越来越有用。

图 12-30 给出了顺序、并发和并行程序之间的集合关系。所有程序的集合能够被划分成不相交的顺序程序集合和并发程序的集合。写顺序程序只有一条逻辑流。写并发程序有多条并发流。并行程序是一个运行在多个处理器上的并发程序。因此，并行程序的集合是并发程序集合的真子集。


图 12-30 顺序、并发和并行程序集合之间的关系

12.7 其他并发问题

你可能已经注意到了，一旦我们要求同步对共享数据的访问，那么事情就变得复杂得多了。迄今为止，我们已经看到了用于互斥和生产者-消费者同步的技术，但这仅仅是冰山一角。同步从根本上说是很难的问题，它引出了在普通的顺序程序中不会出现的问题。这一小节是关于你在写并发程序时需要注意的一些问题的（非常不完整的）综述。为了让事情具体化，我们将以线程为例描述讨论。不过要记住，这些典型问题是任何类型的并发流操作共享资源时都会出现的。

12.7.1 线程安全

当用线程编写程序时，必须小心地编写那些具有称为线程安全性(thread safety)属性的函数。一个函数被称为线程安全的(thread-safe), 当且仅当被多个并发线程反复地调用时，它会一直产生正确的结果。如果一个函数不是线程安全的，我们就说它是线程不安全的(thread-unsafe)。

12.7.2 可重入性

有一类重要的线程安全函数，叫做可重入函数(reentrant function), 其特点在于它们具有这 样一种属性：当它们被多个线程调用时，不会引用任何共享数据。尽管线程安全和可重入有时会（不正确地）被用于同义词，但是它们之间还是有清晰的技术差别，值得留意。

12.7.3 在线程化的程序中使用已存在的库函数

大多数 Linux 函数，包括定义在标准 C 库中的函数(例如 malloc、free、realloc、printf和 scanf)都是线程安全的，只有一小部分是例外。

12.7.4 竞争

当一个程序的正确性依赖于一个线程要在另一个线程到达 点之前到达它的控制流中的 x 点时，就会发生竞争(race)通常发生竞争是因为程序员假定线程将按照某种特殊的轨迹线穿过执行状态空间，而忘记了另一条准则规定：多线程的程序必须对任何可行的轨迹线都正确工作。

12.7.5 死锁

信号量引入了一种潜在的令人厌恶的运行时错误，叫做死锁(deadlock), 它指的是一组线程被阻塞了，等待一个永远也不会为真的条件。进度图对于理解死锁是一个无价的工具。

12.8 小结

一个并发程序是由在时间上重叠的一组逻辑流组成的。在这一章中，我们学习了三种不同的构建并发程序的机制：进程、I/O 多路复用和线程。我们以一个并发网络服务器作为贯穿全章的应用程序。

进程是由内核自动调度的，而且因为它们有各自独立的虚拟地址空间，所以要实现共享数据，必须要有显式的 IPC 机制。事件驱动程序创建它们自己的并发逻辑流，这些逻辑流被模型化为状态机，用I/O多路复用来显式地调度这些流。因为程序运行在一个单一进程中，所以在流之间共享数据速度很快而且很容易。线程是这些方法的混合。同基于进程的流一样，线程也是由内核自动调度的。同基于 I/O 多路复用的流一样，线程是运行在一个单一进程的上下文中的，因此可以快速而方便地共享数据。

无论哪种并发机制，同步对共享数据的并发访问都是一个困难的问题。提出对信号量的 P 和 V 操作就是为了帮助解决这个问题。信号量操作可以用来提供对共享数据的互斥访问，也对诸如生产者-消费者程序中有限缓冲区和读者-写者系统中的共享对象这样的资源访问进行调度。一个并发预线程化的 echo服务器提供了信号量使用场景的很好的例子。

并发也引人了其他一些困难的问题。被线程调用的函数必须具有一种称为线程安全的属性。我们定义了四类线程不安全的函数，以及一些将它们变为线程安全的建议。可重人函数是线程安全函数的一个真子集，它不访问任何共享数据。可重入函数通常比不可重入函数更为有效，因为它们不需要任何同步原语。竞争和死锁是并发程序中出现的另一些困难的问题。当程序员错误地假设逻辑流该如何调度时，就会发生竞争。当一个流等待一个永远不会发生的事件时，就会产生死锁。