常见并发问题
多年来，钻研人员花了大量的工夫和精力钻研并发编程的缺点。并发缺点有很多常见的模式，从大的方面来说能够分为两类：非死锁缺点和死锁缺点。理解这些模式是写出强壮、正确程序的第一步。
非死锁缺点
钻研表明，非死锁问题占了并发问题的大多数。它们是怎么产生的？以及如何修复？咱们次要探讨其中两种：违反原子性（atomicity violation）缺点和违反程序（order violation）缺点。
违反原子性缺点
这是一个 MySQL 中呈现的例子。
1 Thread 1::
2 if (thd->proc_info) {
3 ...
4 fputs(thd->proc_info, ...);
5 ...
6 }
7
8 Thread 2::
9 thd->proc_info = NULL;这个例子中，两个线程都要拜访 thd 构造中的成员 proc_info。第一个线程查看 proc_info 非空，而后打印出值；第二个线程设置其为空。显然，如果当第一个线程查看之后，在 fputs() 调用之前被中断，第二个线程把指针置为空；当第一个线程复原执行时，因为援用空指针，会导致程序解体。
正式的违反原子性的定义是：“违反了屡次内存拜访中预期的可串行性（即代码段本意是原子的，但在执行中并没有强制实现原子性）”。
这种问题的修复通常很简略。咱们只有给共享变量的拜访加锁，确保每个线程拜访 proc_info 字段时，都持有锁。当然，拜访这个构造的所有其余代码，也应该先获取锁。
1 pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;
2
3 Thread 1::
4 pthread_mutex_lock(&proc_info_lock);
5 if (thd->proc_info) {
6 ...
7 fputs(thd->proc_info, ...);
8 ...
9 }
10 pthread_mutex_unlock(&proc_info_lock);
11
12 Thread 2::
13 pthread_mutex_lock(&proc_info_lock);
14 thd->proc_info = NULL;
15 pthread_mutex_unlock(&proc_info_lock);违反程序缺点
上面是一个简略的例子。
1 Thread 1::
2 void init() {
3 ...
4 mThread = PR_CreateThread(mMain, ...);
5 ...
6 }
7
8 Thread 2::
9 void mMain(...) {
10 ...
11 mState = mThread->State;
12 ...
13 }你可能曾经发现，线程 2 的代码中仿佛假设变量 mThread 曾经被初始化了。然而，如果线程 1 并没有率先执行，线程 2 就可能因为援用空指针解体（假如 mThread 初始值为空，否则可能会产生更加奇怪的问题，因为线程 2 中会读到任意的内存地位并援用）。
违反程序更正式的定义是：“两个内存拜访的预期程序被突破了（即 A 应该在 B 之前执行，然而理论运行中却不是这个程序）”。
咱们能够通过强制程序来修复这种缺点，条件变量（condition variables）就是一种简略牢靠的形式。在下面的例子中，咱们能够把代码批改成这样：
1 pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
2 pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
3 int mtInit = 0;
4
5 Thread 1::
6 void init() {
7 ...
8 mThread = PR_CreateThread(mMain, ...);
9
10 // signal that the thread has been created...
11 pthread_mutex_lock(&mtLock);
12 mtInit = 1;
13 pthread_cond_signal(&mtCond);
14 pthread_mutex_unlock(&mtLock);
15 ...
16 }
17
18 Thread 2::
19 void mMain(...) {
20 ...
21 // wait for the thread to be initialized...
22 pthread_mutex_lock(&mtLock);
23 while (mtInit == 0)
24 pthread_cond_wait(&mtCond, &mtLock);
25 pthread_mutex_unlock(&mtLock);
26
27 mState = mThread->State;
28 ...
29 }死锁缺点
除了下面提到的并发缺点，死锁（deadlock）是一种在许多简单并发零碎中呈现的经典问题。例如，当线程 1 持有锁 L1，正在期待另外一个锁 L2，而线程 2 持有锁 L2，却在期待锁 L1 开释时，死锁就产生了。以下的代码片段就可能呈现这种死锁：
Thread 1: Thread 2:
lock(L1); lock(L2);
lock(L2); lock(L1);这段代码运行时，不是肯定会呈现死锁的。当线程 1 占有锁 L1，上下文切换到线程 2。线程 2 锁住 L2，试图锁住 L1。这时才会产生死锁，两个线程相互期待。如图所示，其中的圈（cycle）表明了死锁。
产生死锁的条件
死锁的产生须要如下 4 个条件：
- 互斥：线程对于须要的资源进行互斥的拜访。
- 持有并期待：线程持有了资源，同时又在期待其余资源。
- 非抢占：线程取得的资源，不能被抢占。
- 循环期待：线程之间存在一个环路，环路上每个线程都额定持有一个资源，而这个资源又是下一个线程要申请的。
如果这 4 个条件的任何一个没有满足，死锁就不会产生。因而，解决死锁的办法也不言而喻：只有设法阻止其中某一个条件即可。
死锁预防
循环期待
兴许最实用的预防技术，就是让代码不会产生循环期待。 最间接的办法就是获取锁时提供一个全序（total ordering）。 如果零碎共有两个锁（L1 和 L2），那么咱们每次都先申请 L1 而后申请 L2，这样严格的程序防止了循环期待，也就不会产生死锁。
当然，更简单的零碎中不会只有两个锁，锁的全序可能很难做到。因而， 偏序（partial ordering）可能是一种有用的办法，安顿锁的获取程序并防止死锁 。Linux 中的内存映射代码就是一个偏序锁的优良范例。代码结尾的正文表明了 10 组不同的加锁程序，包含简略的关系，比方 i_mutex 早于 i_mmap_mutex，也包含简单的关系，比方 i_mmap_mutex 早于 private_lock，早于 swap_lock，早于 mapping->tree_lock。
不过， 全序和偏序都须要粗疏的锁策略的设计和实现。另外，程序只是一种约定，大意的程序员很容易疏忽，导致死锁 。最初，有序加锁须要深刻了解代码库，理解各种函数的调用关系，即便一个谬误，也会导致重大的结果。
注：能够依据锁的地址作为获取锁的程序，依照地址从高到低，或者从低到高的程序加锁。
持有并期待
死锁的持有并期待条件，能够通过原子地抢锁来防止。 实际中，能够通过如下代码来实现：
lock(prevention);
lock(L1);
lock(L2);
...
unlock(prevention);代码保障了某个线程先抢到 prevention 这个锁之后，即便有不合时宜的线程切换，其余线程也抢不到任何锁。
不过，这个计划的问题也不言而喻。 首先它不适用于封装，因为这个计划须要咱们精确地晓得要抢哪些锁，并且提前抢到这些锁。并且因为要提前抢到所有锁，而不是在真正须要的时候，所以可能升高了并发。
非抢占
在调用 unlock 之前，都认为锁是被占有的。多个抢锁操作通常会带来麻烦，因为咱们期待一个锁时，可能会同时持有另一个锁。很多线程库提供更为灵便的接口来防止这种状况。具体来说，trylock() 函数会尝试取得锁，返回−1 则示意锁曾经被占有，线程并不会挂起。
能够用这一接口来实现无死锁的加锁办法：
top:
lock(L1);
if (trylock(L2) == -1) {unlock(L1);
goto top;
}留神，当另一个线程应用雷同的加锁形式，然而不同的加锁程序（L2 而后 L1），程序依然不会产生死锁。然而会引来一个新的问题：活锁（livelock）。 两个线程有可能始终反复这一序列，又同时都抢锁失败。这种状况下，零碎始终在运行这段代码，因而名为活锁。也有活锁的解决办法：例如，能够在循环完结的时候，先随机期待一个工夫，而后再反复整个动作，这样能够升高线程之间的反复相互烦扰。
应用 trylock 办法可能还会有其余一些艰难。 第一个问题依然是封装：如果其中的某一个锁是封装在函数外部的，那么这个跳回开始处就很难实现。还有如果代码在中途获取了某些资源，必须要确保也能开释这些资源。例如，在抢到 L1 后，咱们的代码调配了一些内存，当抢 L2 失败时，在 goto 之前，须要开释这些内存。 当然，在某些场景下，这种办法很无效。
互斥
最初的预防办法是完全避免互斥。通常来说，代码都会存在临界区，因而很难防止互斥。那么咱们应该怎么做呢？想法很简略： 通过弱小的硬件指令，咱们能够结构出不须要锁的数据结构 。
比方，咱们能够应用比拟并替换（compare-and-swap）指令来实现一个无锁同步的链表插入操作。
这是在链表头部插入元素的代码：
void insert(int value) {node_t *n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
n->next = head;
head = n;
}一种可能的实现是：
void insert(int value) {node_t *n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
do {n->next = head;} while (CompareAndSwap(&head, n->next, n) == 0);
}这段代码，首先把 next 指针指向以后的链表头 head，而后试着把新节点替换到链表头。如果此时其余的线程胜利地批改了 head 的值，这里的替换就会失败，线程会始终重试。
死锁防止
除了死锁预防，某些场景更适宜死锁防止（avoidance）。 咱们须要理解全局的信息，包含不同线程在运行中对锁的需要状况，从而使得后续的调度可能防止产生死锁。
例如，假如咱们须要在两个处理器上调度 4 个线程，进一步假如咱们晓得线程 1（T1）须要用锁 L1 和 L2，T2 也须要抢 L1 和 L2，T3 只须要 L2，T4 不须要锁。咱们用下表来示意线程对锁的需要。
一种可行的调度形式是，只有 T1 和 T2 不同时运行，就不会产生死锁。上面就是这种形式：
Dijkstra 提出的银行家算法也是一种相似的解决方案。 不过这些计划的实用场景很局限。例如，在嵌入式零碎中，你晓得所有工作以及它们须要的锁。另外这种办法会限度并发。因而，通过调度来防止死锁不是宽泛应用的通用计划。
死锁检查和复原
最初一种罕用的策略就是容许死锁偶然产生，查看到死锁时再采取行动。如果死锁很少见，这种不是方法的方法也很实用。
很多数据库系统应用了死锁检测和复原技术。死锁检测器会定期运行，通过构建资源图来查看循环。当循环（死锁）产生时，零碎会依据既定的策略进行回滚甚至重启。如果还须要更简单的数据结构相干的修复，那么须要人工参加。
注：兴许最好的解决方案是开发一种新的并发编程模型：在相似 MapReduce 这样的零碎中，程序能够实现一些类型的并行计算，毋庸任何锁。锁必然带来各种艰难，咱们应该尽可能地防止应用锁，除非确信必须应用。
基于事件的并发
目前为止，咱们提到的并发，仿佛只能用线程来实现。这不齐全对，一些基于图形用户界面（GUI）的利用，或某些类型的网络服务器，经常采纳另一种并发形式。这种形式称为基于事件的并发（event-based concurrency），在一些古代零碎中较为风行。
基于事件的并发针对两方面的问题。一方面是多线程利用中，正确处理并发很有难度。另一方面，开发者无法控制多线程在某一时刻的调度。程序员只是创立了线程，而后就依赖操作系统可能正当地调度线程，然而某些时候操作系统的调度并不是最优的。
根本想法：事件循环
咱们的想法很简略： 咱们期待某些事件的产生，当它产生时，查看事件类型，而后做大量的相应工作（可能是 I / O 申请，或者调度其余事件筹备后续解决）。
咱们看一个典型的基于事件的服务器。这种利用都是基于一个简略的构造，称为事件循环（event loop）。事件循环的伪代码如下：
while (1) {events = getEvents();
for (e in events)
processEvent(e);
}主循环期待某些事件产生，而后顺次解决这些产生的事件。处理事件的代码叫作事件处理程序（event handler）。处理程序在解决一个事件时，它是零碎中产生的惟一流动。因而，调度就是决定接下来解决哪个事件。这种对调度的显式管制，是基于事件办法的一个重要长处。
但这也带来一个更大的问题：基于事件的服务器如何晓得哪个事件产生，尤其是对于网络和磁盘 I /O？
重要 API：select()/poll()
晓得了根本的事件循环，咱们接下来必须解决如何接管事件的问题。大多数零碎提供了根本的 API，即通过 select() 或 poll() 零碎调用。这些接口对程序的反对很简略：查看是否接管到任何应该关注的 I /O。例如，假设网络应用程序（如 Web 服务器）心愿查看是否有网络数据包已达到，以便为它们提供服务。
上面以 select() 为例，它的定义如下：
int select(int nfds,
fd_set *restrict readfds,
fd_set *restrict writefds,
fd_set *restrict errorfds,
struct timeval *restrict timeout);select() 查看 I / O 描述符汇合，它们的地址通过 readfds、writefds 和 errorfds 传入，别离查看它们中的某些描述符是否已筹备好读取，是否筹备好写入，或有异常情况待处理。在每个汇合中查看前 nfds 个描述符，返回时用给定操作曾经筹备好的描述符组成的子集替换给定的描述符汇合。select() 返回所有汇合中就绪描述符的总数。
这里的一个常见用法是将超时设置为 NULL，这会导致 select() 无限期地阻塞，直到某个描述符准备就绪。然而，更强壮的服务器通常会指定某个超时工夫。一种常见的做法是将超时设置为零，让调用 select() 立刻返回。
应用 select()
咱们来看看如何应用 select() 来查看哪些描述符有接管到网络音讯，上面是一个简略示例：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <sys/time.h>
4 #include <sys/types.h>
5 #include <unistd.h>
6
7 int main(void) {8 // open and set up a bunch of sockets (not shown)
9 // main loop
10 while (1) {
11 // initialize the fd_set to all zero
12 fd_set readFDs;
13 FD_ZERO(&readFDs);
14
15 // now set the bits for the descriptors
16 // this server is interested in
17 // (for simplicity, all of them from min to max)
18 int fd;
19 for (fd = minFD; fd < maxFD; fd++)
20 FD_SET(fd, &readFDs);
21
22 // do the select
23 int rc = select(maxFD+1, &readFDs, NULL, NULL, NULL);
24
25 // check which actually have data using FD_ISSET()
26 int fd;
27 for (fd = minFD; fd < maxFD; fd++)
28 if (FD_ISSET(fd, &readFDs))
29 processFD(fd);
30 }
31 }这段代码很容易了解。初始化实现后，服务器进入有限循环。在循环外部，它应用 FD_ZERO() 宏首先革除文件描述符汇合，而后应用 FD_SET() 将所有从 minFD 到 maxFD 的文件描述符蕴含到汇合中。最初，服务器调用 select() 来查看哪些连贯有可用的数据。而后，通过在循环中应用 FD_ISSET()，事件服务器能够查看哪些描述符已筹备好数据并解决传入的数据。
应用单个 CPU 和基于事件的应用程序，并发程序中常见的问题不再存在。因为一次只解决一个事件，所以不须要获取或开释锁。基于事件的服务器是单线程的，因而也不能被另一个线程中断。
问题：阻塞零碎调用
不过，这里存在一个问题：如果某个事件要求你收回可能会阻塞的零碎调用，该怎么办？
例如，假设一个申请从客户端进入服务器，要从磁盘读取文件并将其内容返回给发出请求的客户端。为了解决这样的申请，某些事件处理程序会收回 open() 零碎调用来关上文件，而后通过 read() 调用来读取文件。当文件被读入内存时，服务器可能会开始将后果发送到客户端。
open() 和 read() 调用都可能向存储系统收回 I / O 申请，因而可能须要很长时间能力提供服务。应用基于线程的服务器时，这不是问题：在收回 I / O 申请的线程挂起时，其余线程能够运行。然而，应用基于事件的办法时，没有其余线程能够运行。这意味着如果一个事件处理程序收回一个阻塞的调用，整个服务器就会阻塞直到调用实现。当事件循环阻塞时，零碎处于闲置状态，因而是潜在的微小资源节约。因而， 咱们在基于事件的零碎中必须恪守一条规定：不容许阻塞调用 。
解决方案：异步 I /O
为了克服这个限度，许多古代操作系统引入了新的办法来向磁盘零碎收回 I / O 申请，个别称为异步 I /O（asynchronous I/O）。 这些接口使应用程序可能收回 I / O 申请，在 I / O 实现之前能够立刻将控制权返回给调用者，并能够让应用程序可能确定各种 I / O 是否已实现。
当程序须要读取文件时，能够调用异步 I / O 的相干接口。如果胜利，它会立刻返回，应用程序能够持续其工作。 对于每个未实现的异步 I /O，应用程序能够通过调用接口来周期性地轮询（poll）零碎，以确定所述 I / O 是否曾经实现。
如果一个程序在某个特定工夫点收回数十或数百个 I /O，反复查看它们中的每一个是否实现是很低效的。为了解决这个问题， 一些零碎提供了基于中断（interrupt）的办法。此办法应用 UNIX 信号（signal）在异步 I / O 实现时告诉应用程序，从而打消了反复询问零碎的须要 。
信号提供了一种与过程进行通信的形式。具体来说，能够将信号传递给应用程序。这样做会让应用程序进行以后的任何工作，开始运行信号处理程序（signal handler），即应用程序中某些解决该信号的代码。实现后，该过程就复原其先前的行为。
另一个问题：状态治理
基于事件的办法的另一个问题是，当事件处理程序收回异步 I / O 时，它必须打包一些程序状态，以便下一个事件处理程序在 I / O 最终实现时应用。
咱们来看一个简略的例子，在这个例子中，一个基于线程的服务器须要从文件描述符（fd）中读取数据，一旦实现，将从文件中读取的数据写入网络套接字描述符 sd。
在一个多线程程序中，做这种工作很容易。当 read() 最终返回时，程序立刻晓得要写入哪个套接字，因为该信息位于线程堆栈中。在基于事件的零碎中，为了执行雷同的工作，咱们应用 AIO 调用异步地收回读取，而后定期检查读取的实现状况。当读取实现时，基于事件的服务器如何晓得该怎么做？也即该向哪个套接字写入数据？
解决方案很简略： 在某些数据结构中，记录实现解决该事件须要的信息。当事件产生时（即磁盘 I / O 实现时），查找所需信息并处理事件。
在这个特定例子中，解决方案是将套接字描述符（sd）记录在由文件描述符（fd）索引的某种数据结构（例如，散列表）中。当磁盘 I / O 实现时，事件处理程序将应用文件描述符来查找该数据结构，这会将套接字描述符的值返回给调用者。而后，服务器能够实现最初的工作将数据写入套接字。