CSAPP-并发编程

当逻辑控制流在时间上是重叠的，那么我们就可以说它们是并发的（concurrent）。这种常见的现象称为并发（concurrency），出现在计算机系统的许多不同的层面上。硬件异常处理程序、进程和Linux信号处理程序都是大家熟悉的例子。

并发可以在应用程序中扮演重要的角色。例如，处理异常响应事件，访问慢速的I/O设备，与人交互，通过推迟工作以降低延迟，服务多个网络客户端，在多核机器上进行并行计算。

使用应用级并发的应用程序称为*并发程序(concurrent program)*。现代操作系统提供了三种基本的构造并发程序的方法：

  • 进程
  • I/O多路复用
  • 线程

1. 基于进程的并发编程

构建并发程序最简单的方式就是进程，使用哪些大家都很熟悉的函数，如fork, exec和waitpid。

对于在父子进程中共享状态信息，进程有一个非常清晰的模型；共享文件表，但是不共享用户地址空间。

进程拥有独立的地址空间可以避免进程污染另一个进程的虚拟内存，但是会导致进程间共享状态信息变得更加困难。为了共享信息通常需要使用显示的IPC（进程间通信）机制（如waitpid）。

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

I/O多路复用的基本思想就是使用select函数，要求内核挂起进程名，只有在一个或者多个I/O事件发生后，才将控制返回给应用程序。

Linux中，Ctrl+D表示EOF。

事件驱动设计的一个优点是，它比基于进程的设计给程序员更多的对程序行为的控制，同时一个基于I/O多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都能访问改进程的全部地址空间。但是事件驱动设计的缺点是会导致编码复杂。

3. 基于线程的并发编程

线程（thread）就是运行在进程上下文中的逻辑流。线程由内核自动调度。每个线程都有它自己的线程上下文（thread context），包括一个唯一的整数线程ID（thread ID， TID）、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有运行在一个进程里面线程共享该进程的整个虚拟地址空间。

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

线程在进程的上下文中。

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

POSIX线程(Pthreads)是在C程序中处理线程的一个标准接口，POSIX提供下面的和线程相关的方法：

  1. 创建线程。线程通过调用pthread_create函数来创建其他线程。
  2. 线程可以通过pthread_self函数来获取它自己的线程ID。
  3. 终止线程。1）当顶层线程返回时，线程会隐式的终止；2）通过调用pthread_exit函数显式的终止，主线程调用的话，会等待所有其他对等线程终止；3）某个对等线程调用Linux exit函数，该函数终止进程以及所有与该进程相关的线程；4）另一个对等线程可以以当前线程ID作为参数调用pthread_cancel函数来终止当前线程。
  4. 回收已终止线程的资源。线程可以通过调用pthread_join函数等待其他线程终止。
  5. 分离线程。线程是可以被结合（joinable）或者分离的（detached）。一个可结合的线程能够被其他线程回收和杀死。一个可结合的线程能够被其他线程杀死和回收。在被其他线程回收之前，它的内存资源（如栈）是不会被释放的。相反，一个分离的线程是不能被其他线程回收或者杀死的。它的内存资源在它终止时由系统自动释放。默认线程被创建成可结合的。可以通过pthread_detach函数分离。
  6. 初始化线程。pthread_once函数允许你初始化与线程例程相关的状态。

4. 多线程中的共享变量

线程有一个很有吸引力的地方就是多个线程很容易共享相同的程序变量。为了理解C程序中的一个变量是否是共享的，需要理解下面三个问题：

  1. 线程的基础内存模型是什么？
  2. 根据这个模型，变量实例是如何被映射到内存的？
  3. 最后，有多少线程引用到这些实例？一个变量我们说是共享的，当且仅当多个线程引用到这个变量的某个实例。

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

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

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

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

5. 用信号量同步线程

共享变量十分方便，但是也引入了*同步错误(synchronization error)*的可能性。如下面代码，创建了两个线程，每个线程堆共享计数变量cnt加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "mylab.h"

void *thread(void *vargp);  /*Thread routine prototype */

/* Global  shared variable */
volatile long cnt = 0;

int main(int argc, char **argv)
{
    long niters;
    pthread_t tid1, tid2;

    /* Chech input argument */
    if (argc != 2) {
        printf("usage: %s <niters>\n", argv[0]);
        exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    Pthread_create(&tid1, NULL, thread, &niters);
    Pthread_create(&tid2, NULL, thread, &niters);
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);

    /* Check result */
    if(cnt != (2*niters))
        printf("BOOM ! cnt = %ld\n", cnt);
    else
        printf("OK cnt = %ld\n", cnt);
    
    exit(0);
}

/*Thread routine */
void *thread(void *vargp)
{
    long i, niters = *((long *) vargp);

    for(i = 0; i < niters; i++)
        cnt++;

    return NULL;
}

运行上面这段程序可以看到每次得到的答案十分随机。这里关键的地方是，一般而言，我们没法预测操作系统是否将为你的线程选择一个正确的顺序。这里我们将借助一种叫做进度图（progress graph）的方法来阐明这些正确和不正确的概念。

进度图（progress graph）将n个并发线程的执行模型转化为一条n维笛卡尔空间的轨迹线。每条轴k对应于线程k的进度。每个点代表线程k已经完成指令I这一状态。图的原点对应于没有任何线程完成一条指令的初始状态。

进度图将指令执行模型化为从一种状态到另一种状态的转换（transition）. 转换被表示为一条从一点到相邻点的有向边。合法的转换是向右或者向上的。两条指令不能在同一时刻完成。程序不能反向运行。

这里我们通常想要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问（mutually exclusive access）。通常这种现象称为*互斥(mutual exclusion)*。

在进度图中，两个临界区的交集形成的状态空间称为不安全区（unsafe region）。绕开不安全区的轨迹线就叫做不安全轨迹线（unsafe trajectory）。

有一种经典的解决同步不同执行线程的方法是通过采用*信号量(semaphore)*的特殊类型变量。信号量s是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作叫做P和V。

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

当有多个线程在等待同一个信号的时候，你不能预测V操作要重启哪一个线程。

P和V的名字来自于荷兰语的单词Proberen（测试）和Verhogen（增加）

POSIX标准定义了许多操作信号量的函数：

1
2
3
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) */

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

以这种方式保护起来的共享变量的信号量叫做二元信号量（binary semaphore）。因为它的值总是0或者1.以提供互斥目的的二元信号量常常被称为互斥锁(mutex)。在一个互斥锁上执行P操作称为互斥锁加锁，执行V操作称为互斥锁解锁。一个被用作一组可用资源的计数器的信号量被称为计数信号量。

对于进度图来说PV定义了一个禁止区，禁止区完全包含了不安全区，阻止了实际可行的轨迹线接触到不安全区。

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

生产者-消费者模型中，生产者产生新的项目并将它们插入到一个有限的缓冲区中。消费者从缓冲区中取出这些项目，然后消费它们。

1
生产者线程 --> 有限的缓冲区 --> 消费者线程

读者-写者问题是互斥问题的一个概括。一组并发的线程要访问一个共享对象，例如一个主存中的数据结构，或者一个磁盘数据。有的线程只读对象，而其他的线程只修改对象，修改对象的线程叫做写者。只读对象的线程叫做读者。写者必须拥有对对象的独占访问，而读者可以和无限多个其他的读者共享对象。（一般如抢购系统）

6. 使用线程提高并行性

到目前为止，在对并发的研究中，我们都假设并发线程是在单处理器上执行的。然而，大多数现代机器具有多核处理器。并发程序通常在这样的机器上运行得更快，因为操作系统内核在多个核上并行地调度这些并发线程，而不是在单个核上顺序地调度。

并发程序的对立是顺序程序；并发程序包含并行程序。并行程序是一个运行在多个处理器上的并发程序。

将任务分配到不同线程的最直接的方法是将序列划分成t个不相交的区域，然后给t个不同的线程每个分配一个区域。

程序单线程顺序运行时非常慢，几乎比多线程并行运行时慢了一个数量级。造成性能差的原因是相对于内存更新操作的开销，同步操作（P和V）代价太大。这里突显出了并行编程的一个重要原则：同步操作开销巨大，要尽可能避免。如果无可避免，必须要用尽可能多的有用计算来弥补这个开销。

根据线程运行时间图我们可以看出，对于一个4核系统，并行代码的运行时间在线程数少于4的时候，线程每增加一个，运行时间就下降一半。单当大于4时，4个核中的每个都至少忙于一个线程，这时线程数增加会使实际运行时间变长。

运行程序的加速比通常被定义为： $S_p = T_1/T_p$ 这里P是处理器的核心数量，T_k是在k个核心上的运行时间。T_1是程序顺序执行版本的执行时间时，S_p称为绝对加速比；T_1是程序顺序并行版本在一个核上的执行时间时时，S_p称为相对加速比。

另一种相关测量称为效率，定义为： $E_p = S_p/p = T_1/p*T_p$

7. 其他并发问题

一旦我们要求同步对共享数据的访问，那么事情就变得复杂的多。

7.1 线程安全

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

我们定义四个线程不安全的函数类型：

  1. 不保护共享变量的函数；
  2. 保持跨越多个调用的状态函数；
  3. 函数返回指向静态变量的指针；
  4. 函数中调用了线程不安全的函数。

7.2 可重入性

有一类重要的线程安全函数，叫做可重入函数（reentrant function），其特点在于它们具有这样的一种属性：当它们被多个函数调用的时候，不会引用任何共享数据。

如果所有的函数参数都是值传递的，并且所有的数据引用都是本地的自动栈变量，那么函数就是显示可重入的（explicitly reentrant），也就是说，无论它是如何被调用的，都可以断言它是可重入的。

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

大多数Linux函数，包括定义在标准C库中的函数（例如malloc, free, realloc, printf和 scanf）都是线程安全的，只有一小部分是例外的。同时Linux对这些函数提供了线程安全的版本。

线程不安全函数 线程不安全类 Linux线程安全版本
rand 2 rand_r
strtok 2 strtok_r
asctime 3 asctime_r
ctime 3 ctime_r
gethostbyaddr 3 gethostbyaddr_r
gethostbyname 3 gethostbyname_r
inet_ntoa 3 无
localtime 3 rand_r

7.4 竞争

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

7.5 死锁

信号量引入可一种潜在的令人厌恶的运行时错误，叫做死锁（deadlock），它指的是一组线程被阻塞了，等待一个永远不会为真的条件。

  • 程序员使用P和V操作顺序不当，以至于两个信号量的禁止区域重叠。如果某个执行轨迹线恰巧到达死锁状态d，那么就不可能有进一步的进展了，因为重叠的禁止区域阻塞了每个合法方向上的进展。换句话说，程序死锁是因为每个线程都在等待其他线程执行一个不可能的V操作；
  • 重叠的禁止区域引起了一组称为死锁区域（deadlock region）的状态。如果一个轨迹线碰巧到达了一个死锁区域中的状态，那么死锁就是不可避免的了。轨迹线可以进入死锁区域，但是它们不能离开。
  • 死锁是不可预测的。

当使用二元信号量来实现互斥的时候，可以通过下面规则来避免死锁：

互斥锁加锁规则：给定所有的互斥操作一个全序，如果每个线程都是以一种顺序获得互斥锁并以相反的顺序释放，那么这个程序就是无死锁的。