构造并发程序的方法

gaunthan Posted on Mar 29 2017

? Concurrent Programming ? ? Server Development ?

> **并发**(concurrency)出现在计算机系统的许多不同层面上——硬件异常处理程序、进程，以及Unix信号处理程序都是广为人知的例子。并发虽然可能带来竞争条件等[并发问题](http://leanote.com/blog/post/5783b869ab644133ed0088db)，但它使得系统有同时执行多个任务的能力，以此大大提高系统的工作效率。本文将介绍几种构建并发程序的主流方法。

## 概述
通常我们将并发看做是一种操作系统内核用来执行多个应用程序的机制（多道程序）。但是，并发并不仅仅局限于内核。它也可以在应用程序中扮演重要角色：

- 访问慢速I/O设备。当一个应用正在等待来自慢速I/O设备（例如磁盘）的数据到来时，内核会运行其他进程，使CPU保持繁忙。每个应用都可以按照类似的方式，通过交替执行I/O请求和其他有用的工作来使用并发。
- 与人交互。和计算机交互的人要求计算机有同时执行多个任务的能力。
- 通过推迟工作以降低延迟。某些应用程序可以推迟操作，待它们累积到一定量后再执行。
- 服务多个网络客户端。简单的迭代服务器根本就不能满足需求，一个慢速的客户端就会导致服务器拒绝为其他客户端提供服务。一种更好的方法是创建一个并发服务器，为每个客户端创建一个单独的逻辑流。这就允许服务器同时为多个客户端服务，并且也避免了慢速客户端独占服务器。
- 在多核机器上进行并行计算。被划分成并发流的应用程序通常在多核机器上都比单处理器机器上运行得快，因为这些流可以并行执行，而不是交错执行。

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

方法|说明
--|--
进程|每个逻辑控制流都是一个进程，由内核来调度和维护。因为进程有独立的虚拟地址空间，想要和其他流通信，控制流必须使用某种显式的[**进程间通信**](http://gaunthan.leanote.com/post/%E8%BF%9B%E7%A8%8B%E9%97%B4%E9%80%9A%E4%BF%A1-IPC)(interprocess communication, IPC)机制。
I/O多路复用|应用程序在一个进程的上下文中显式地调度它们自己的逻辑流。逻辑流被模型化为**状态机**，数据到达文件描述符后，主程序显式地从一个状态切换到另一个状态。因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。
线程|线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。可以把线程看成是上面两种方式的混合体，像进程流一样由内核进行调度，而像I/O多路复用一样共享一虚拟地址空间。

## 基于进程的并发编程
构造并发程序最简单的方式就是用进程，使用`fork`、`exec`和`waitpid`这样的函数。例如，一个构造并发服务器的自然方法就是：在父进程中接受客户端连接请求，然后创建一个新的子进程来为每个新客户端提供服务。

假设我们有两个客户端和一个服务器，服务器正在监听一个监听描述符（假设该描述符为3）上的连接请求。现在假设服务器接受了客户端1的连接请求，并返回一个已连接描述符（假设为4），如下图所示：
![](https://leanote.com/api/file/getImage?fileId=58db27eeab644174dd0034b3)

在接受连接请求之后，服务器派生一个子进程，这个子进程获得服务器描述符表的完整拷贝。子进程关闭它的拷贝中的监听描述符3，而父进程关闭它的已连接描述符4的拷贝，这样就得到下图的状态，其中子进程正忙于为客户端提供服务：
![](https://leanote.com/api/file/getImage?fileId=58db27eeab644174dd0034b4)

**因为父、子进程中的已连接描述符都指向同一个文件表表项，所以父进程关闭它的已连接描述符的拷贝是至关重要的。否则，将永远不会释放已连接描述符4的文件表条目，由此引起资源泄漏。**

接着，假设父进程又接受一个新的客户端2的连接请求，并返回一个新的已连接描述符（假设为5）。那么，父进程会执行前面提到的步骤：创建子进程，然后关闭已连接描述符5。当然，子进程也要关闭监听描述符3。父进程会接着等待下一个连接请求，而两个子进程正在并发地为它们各自的客户端提供服务。

### 基于进程的并发服务器
这种模型下有几点需要注意：

- 通常服务器会运行很长时间，所以必须包括一个 SIGCHLD 处理程序，来回收僵死子进程的资源。因为当 SIGCHLD 信号是阻塞的，而Unix信号是不排队的，所以它的信号处理程序必须准备好回收多个僵死子进程的资源：
```c
void sigchld_handler(int sig)
{
    // 等待任意子进程（不阻塞），因此如果没有子进程状态发生变化
    // 则waitpid返回0，退出循环
    while(waitpid(-1, NULL, WNOHANG) > 0) {}
}
```
- 父子进程必须关闭它们各自的已连接描述符拷贝。

下面是该服务器实现伪代码，忽略了错误处理等非主要信息：
```c
int main()
{
    ...
    signal(SIGCHLD, sigchld_hanler);    // 安装回收僵死子进程的信号处理程序
    listenfd = open_listenfd(server_port);  // 创建监听描述符
    while(1) {
        connfd = accept(listenfd, (SA *)&client_addr, &client_len);   // 等待连接
        if(fork() == 0) {   // 在子进程中
            close(listenfd);
            offer_service(connfd);  // 向客户端提供服务
            close(connfd);
            exit(0);
        }
        close(connd);
    }
```

### 关于进程的优劣
对于在父、子进程间共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来，一个进程不可能不小心覆盖另一个进程的内存空间，这就消除了许多令人迷惑的错误。而且，假如业务代码有缺陷，可能使进程在服务客户的时候崩溃，使用多进程使得服务器进程不需要关注这些异常情况。

另一方面，独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，它们必须使用显式的[**进程间通信**](http://gaunthan.leanote.com/post/%E8%BF%9B%E7%A8%8B%E9%97%B4%E9%80%9A%E4%BF%A1-IPC)机制。基于进程的设计的另一个缺点是，它们往往比较慢，因为进程控制和IPC的开销很高。

## 基于I/O多路复用的并发编程
假设我们的服务器现在不仅需要服务远程客户端，还需要服务本地的终端客户，那么使用进程的方式将无法满足需求——无论是等待套接字还是终端输入，都可能会导致阻塞，使得另一方等待过长的时间。再者，进程的创建代价是很高的，如果系统不允许我们创建太多进程，那么服务器的并发度就会很低。

针对这些困境的一个解决方法是使用**I/O多路复用**(I/O multiplexing)技术。基本的思路就是使用`select`函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。

实际使用I/O多路复用的产品有很多，如 Redis——基于I/O多路复用的单进程、单线程内存数据库。

### select
`select`函数的接口如下：

#include <sys/select.h>
    // 成功，返回就绪的描述符数量。如果超时，则为0
    // 错误，返回-1，设置 errno
    int select(int nfds, fd_set *readfds, fd_set *writefds,
                  fd_set *exceptfds, struct timeval *timeout);

它处理类型为 fd_set 的集合，也叫做描述符集合。逻辑上我们将它看成一个大小为 n 的位向量，我们通过使用`FD_SET`接口将其中的某些位置位，以表明这些是我们想要监听的描述符。相关的接口还有`FD_ZERO`、`FD_CLR`和`FD_ISSET`。这些接口可以实现为宏或函数。调用 FD_ZERO 将一个 fd_set 变量的所有位设置为0。要开启描述符集中的一位，可以调用 FD_SET。调用 FD_CLR 可以清除一位。最后，可以调用 FD_ISSET 测试描述符集中的一个指定位是否已打开。

select 可以监听读、写、异常描述符事件，分别通过 readfds、writefds 以及 exceptfds 变量指定。三个指向描述符集的指针中的任意一个（或全部）可以是空指针，这表示对相应条件并不关心。如果所有3个指针都是 NULL，则 select 提供了比 `sleep` 更精确的定时器。（sleep 等待整数秒，而 select 的等待时间则可以小于1秒，其实际精度取决于系统时钟。

nfds 指出监听的描述符的最大值加一，select 的轮询将到这里止步，然后重来（即范围$[0, nfds)$）。可以将 nfds 设置为 **FD_SETSIZE**，这是 sys/select.h 中的一个常量，它指定最大描述符数（通常是1024）。但是对大多数应用程序而言，此值太大了。通过指定我们所关注的最大描述符，内核就只需在此范围内寻找打开的位，而不必在3个描述符集的数百个没有使用的位内搜索。

timeout 参数指定等待的时间。如果在该时间后还没有描述符就绪，则 select 返回0。

当一个错误发生时，select 返回-1。例如，在所指定的描述符一个都没准备好时捕捉到一个信号。在这种情况下，一个描述符集都不修改。

一旦 select 返回正数，我们就用`FD_ISSET`宏判断哪个描述符就绪。一个正返回值说明了已经就绪的描述符数，该值是3个描述符集中已准备好的描述符数量之和，所以如果同一描述符已准备好读和写，那么在返回值中会对其计两次数。在这种情况下，3个描述符集中仍旧打开的位对应于已准备好的描述符。

**”就绪“的含义如下：**

- 如果对读集(readfds)中的一个描述符进程的 `read` 操作不会阻塞，则认为此描述符是就绪的。有数据到来，或描述符关闭（这时候 `read `会返回0表示 EOF）都会导致其就绪。
- 如果对写集(writefds)中的一个描述符进行的 `write` 操作不会阻塞，则认为此描述符是就绪的。
- 如果对异常条件集(exceptfds)中的一个描述符有一个未决异常条件，则认为此描述符是就绪的。异常条件包括：在网络连接上到达带外(out-of-band)的数据，或者在处于数据包模式的伪终端上发生了某些条件。
- 对于读、写和异常条件，普通文件的文件描述符总是返回就绪。

一个描述符阻塞与否不会影响 select 是否阻塞。如果希望读一个非阻塞描述符，并且以超时值为3秒调用 select，则它最多阻塞3s。相类似，如果指定一个无限的超时值（通过将 timeout 指定为 NULL），则在有描述符就绪，或捕捉到一个信号之前，select 都会一直阻塞。

由于 select 返回后，传入的描述符集可能被修改，因此我们每一次调用它之前都需要重新初始化描述符集。

**select 有几个缺点：**

- 每次调用 select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大。
- 每次调用 select 都需要在内核态遍历传递进来的所有 fd，这个开销在 fd 很多时也很大。
- select 支持的文件描述符数量比较少，最大为 FD_SETSIZE（默认是 1024，可以通过修改其值，但需要重新编译内核）。

### pselect
POSIX.1 也定义了一个 select 的变体，称为 `pselect`：

#include <sys/select.h>
    // 返回值的定义与 select 相同  
    int pselect(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, const struct timespec *timeout,
           const sigset_t *sigmask);

除以下几点，pselect 与 select 相同：

- select 的超时值用 timeval 结构指定，但 pselect 使用 timespec 结构。timespec 结构以秒和纳秒表示超时值，而非秒和微秒。如果平台支持这样的时间精度，那么 timespec 就能提供更精准的超时时间。
- pselect 的超时值被声明为 `const`，这保证了调用 pselect 不会改变此值。
- pselect 可使用可选信号屏蔽字。若 sigmask 为 NULL，那么在与信号有关的方面，pselect 的运行状况和 select 相同。否则，sigmask 指向一信号屏蔽字，在调用 pselect时，以原子操作的方式安装该信号屏蔽字。在返回时，恢复以前的信号屏蔽字。

### poll
`poll` 函数类似于 select，但接口有所不同。select 可以监听的描述符数量受到 FD_SETSIZE 的限制，而poll 则没有这一限制：
    
    #include <poll.h>
    // 返回值的定义与 select 相同
    int poll(struct pollfd *fds, nfds_t nfds, int timeout);

与 select 不同，poll 不是为每种条件（可读、可写和异常条件）构造一个描述符集，而是构造一个 pollfd 结构的数组，每个数组元素指定一个描述符编号以及我们对该描述符感兴趣的条件。数组中的元素数量由参数 nfds 指定。

数组元素类型 pollfd 的定义如下：

struct pollfd {
        int   fd;         /* file descriptor */
        short events;     /* requested events */
        short revents;    /* returned events */
    };

poll 返回时，revents 成员由内核设置，用于说明每个描述符发生了哪些事件。注意，poll 没有更改 events 成员。这与 select 不同，select 修改其参数以指示哪一个描述符是就绪的。

poll 的 events 和 revents 标志如下：
![](https://leanote.com/api/file/getImage?fileId=58db6f95ab644178dc0040d2)

当一个描述符被挂断(POLLHUP)后，就不能再写该描述符，但是有可能仍然可以从该描述符读到数据。

poll 的最后一个参数指定的是等待时间，有三种不同的情形：

poll 会在所指定的描述符中的一个已准备好，或者捕捉到一个信号时返回。如果在等待期间捕捉到一个信号，则 poll 返回 -1，errno 设置为 EINTR。如果等待超时，则返回0。

与 select 一样，一个描述符是否阻塞不会影响 poll 是否阻塞。

虽然 poll 没有 select 使用 fd_set 所带来的那些问题，但从移植性来看，使用 select 也不失为一个选择，因为支持 select 的系统比支持 poll 的系统要多。

### epoll

`epoll` 是对 select 和 poll 的改进。前面提到 select 有三个缺点，下面看 epoll 是怎么解决这些问题的：

- fd 拷贝代价
epoll 利用 `epoll_create`接口，每次注册新事件时都会将其拷贝进内核，而不是在 `epoll_wait` 的时候重复拷贝。epoll 保证每个 fd 只会被拷贝一次。
- 轮询 fds 代价
epoll 不像 select 和 poll 一样，每次都把查询的描述符加入到对应的设备等待队列中，并为它们指定一个回调函数。而是只在调用 `epoll_ctl`时加入一次。当设备就绪唤醒其等待队列上的等待者时，就会调用回调函数，将该描述符加入一个就绪链表。`epoll_wait` 的工作实际上就是时不时检查下这个链表是不是非空。
- fd 数量受限
epoll 所支持的 fd 上限是最大可以打开的文件数目，这个数字与机器的内存有很大关系。可以使用 `cat /proc/sys/fs/file-max` 命令查看：
![](https://leanote.com/api/file/getImage?fileId=58db7735ab644174dd004036)
这个值一般都大于2048。

### 基于I/O多路复用的事件驱动
I/O多路复用可以用作并发**事件驱动**(event-driven)程序的基础。在事件驱动程序中，执行流是因为某种事件而前进的。一般概念是将逻辑流模型化为状态机。select监听的某一个描述符就绪，就相当于特定事件的发生。

### 关于I/O多路复用的优劣
I/O多路复用解决了单进程单线程模型中，连接阻塞导致不能服务其他客户端的问题。此外，它不需要进行频繁的进程/线程上下文切换，因此效率很高。但是，也正因为这一点，它不能充分利用多核处理器的优势——它是串行地处理请求的。因此，现实中使用I/O多路复用的产品往往还会混合线程或进程，以进一步提高工作效率。例如使用I/O多路复用处理连接，然后用一组工作者线程来服务客户端。

## 基于线程的并发编程
**线程**(thread)是运行在进程上下文中的逻辑流。程序都是由每个进程中的一个线程（主线程）组成的。但是现代操作系统允许我们编写一个进程里同时运行着多个线程的程序。

线程由内核自动调度，每个线程都有自己的**线程上下文**(thread context)，包括一个唯一的整数类型的**线程ID**(thread ID, TID)、运行时栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。

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

因为一个线程的上下文比一个进程的上下文小得多，因此它的上下文切换速度比进程的上下文切换速度快得多。另外，线程不像进程那样按照严格的父子层次来组织——和一个进程相关的线程组成一个对等（线程）**池**(pool)。

主线程和其他线程的区别仅在于它总是进程中第一个运行的线程，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。另外，每个对等线程都能读写相同的共享数据。

由于线程之间共享内存，对同样数据的访问如果不加锁，就会引入竞争条件等[并发问题](http://leanote.com/blog/post/5783b869ab644133ed0088db)。

### POSIX线程
POSIX线程(Pthreads)是在C程序中处理线程的一个标准接口，它定义了大约60个函数，允许程序创建、杀死和回收线程，与对等线程安全地共享数据，还可以通知对等线程系统状态的变化。

## References

- RandalE.Bryant, DavidR.O’Hallaron, 布赖恩特,等. 深入理解计算机系统[M]. 机械工业出版社, 2011.
- W.RichardStevens, StephenA.Rago, 史蒂文斯, 等. UNIX 环境高级编程 [M]. 人民邮电出版社, 2014.
- [select、poll、epoll 之间的区别总结 [整理]](http://www.cnblogs.com/Anker/p/3265058.html)