操作系统的任务调度机制（四）通信、同步和死锁
2月 21, 2021
操作系统进程间通信、以及并发的处理方式，是调度器能够高效运行的基础，上篇说了调度器的策略，本篇继续深入调度器的背后，看看进程间通信、同步和并发控制如何支撑着这套现代操作系统的调度机制。内容上是按照进程间通信引出了并发控制方法：同步原语，并发又进而引出了死锁问题。
进程间通信（IPC） #
进程间通信（Inter-Process Communication，IPC）是多进程协作的基础，进程间通信的很多内容对线程同样适用。
管道（Pipe） #
管道是 Unix 系统上出现的第一种 IPC 方法，和其名字一样，类似一个管道，其中一端负责发送，另一端负责接收，它和 FIFO（先进先出）队列非常像，是单向的 IPC，可以由两个进程参与。管道在内核中通常有一定的缓冲区来缓冲消息，而通信的数据是字节流，需要应用自己去对数据进行解析。管道可以分为命名管道和匿名管道，它们的区别主要在于创建方式。
匿名管道 #
Linux 中的命令行还有管道操作符 |，比如经常会通过 ps axu | grep python 这个命令查找一个进程，这里就是利用一个管道将 ps aux 的输出作为 grep python 的输入。
这里的管道操作符的使用就是一个匿名管道，因为它没有名字。匿名管道底层是通过 pipe 的系统调用实现的，在创建的同时进程会拿到读写的端口（两个文件描述符）。这种没有名字的管道一般结合 fork 使用，由于子进程可以继承文件描述符，因此父子进程相当于通过 fork 完成了一次 IPC 权限的分发，进而通过管道进行父子进程间通信。
int pipe(int fd[2])
其中，f[0] 是读取端描述符，f[1] 是写入端描述符。虽然是文件类型，但是匿名管道只存在于内存中。
命名管道 #
命名管道是由 mkfifo 命令创建的，在创建过程中会指定一个全局的文件名，在 Linux 的实现中，管道也会被当做一个文件。这样，两个进程通过相同的管道名进程创建，就可以实现在任意两个进程间建立管道的通信连接。在一些资料中，命名管道也被直接称为 FIFO 以区别于管道（匿名管道）。
创建管道：
mkfifo pipeName
写入管道：
echo "info" > pipeName # 没有读取的时候会被阻塞
读取管道里的数据：
cat < pipeName
#hello
实际应用中，除了命令，一般通过文件相关的系统调用进行读写消息。相比匿名管道一般的父子进程通信的场景，命名管道通常用在两个不相关的进程间通信。
消息队列（MQ） #
消息队列（Message Queue）和管道也有些类似，首先都是“发送者”和“接收者”模型，其次都有一段“管道”，但是消息队列更高级一些。相比管道，消息队列有以下几个特点：
- 支持多个发送者和多个接收者，因此通信效率更高。
- 消息在发送后不会阻塞以等待接收，而是可以直接返回。
- 队列中的消息是一块一块排队等等消费的，不是字节流。
- 不同的消息可以有不同的类型，消息由类型和数据组成。
System V 接口 #
消息队列的操作一般被抽象为四个基本操作，以 System V 为例。
msgget 系统调用创建一个新消息队列或取得一个既有队列的标识符。
int msgget(key_t key, int msgflg);
key是一个整数，会被转换成一个 IPC 标识符，即一个消息队列。msgflg是一个标志位，用于指定新队列的权限或者检查既有队列的权限。
msgsnd 系统调用向消息队列写入一个消息。
int msgsnd(int msqid, cost void *msgp, size_t msgsz, int msgflg);
msqid消息队列标识符。msgp是一个又程序员定义的指针，该结构用于存放发送或接收的消息结构体，这个结构体的常规形式如下：
struct mymsg {
long mtype;
char mtext[];
}
msgrcv 系统调用从消息队列中读取（并删除）一条消息，并将内容复制进 msgp 指向的缓冲区。
ssize_t msgrcv(int msgid, void *msgp, size_t maxmsgsz, long msgtyp, int msgflg);
msgctl 可以控制和管理一个消息队列，如修改消息队列的权限信息或删除消息队列。
int msgctl(int msqid, int cmd, struct msqid_ds *buf);
cmd指定了集中操作类型：- IPC_RMID 立即删除消息队列对象及其关联的
msqid_ds数据结构。 - IPC_STAT 将于这个消息队列关联的
msqid_ds数据结构的副本放到buf指向的缓冲区中。 - IPC_SET 使用
buf指向的缓冲区提供的值更新与这个消息队列关联的msgid_ds数据结构中被选中的字段。
- IPC_RMID 立即删除消息队列对象及其关联的
POSIX 接口 #
mq_open创建或打开一个既有队列。mq_send向队列写入一个消息。mq_receive从队列读取一个消息。mq_close关闭一个消息队列。mq_unlink删除一个消息队列。mq_notify允许一个进程向队列注册接收消息通知。
消息队列的缺点 #
消息队列仍然存在几个明显的问题。
- 消息队列的生命周期的比较不受控制：除非内核重新启动或者主动删除队列，否则数据都是会被保留的。
- 如何安全地删除一个消息队列（后续不会再有读写且没有数据丢失）。
- 消息队列的单条消息大小、队列消息总量、队列数据总量都受系统限制。
- 消息队列存在于内核态，消息会通过系统调用在内核态和用户态频繁拷贝。
- 消息队列不一定按照先进先出的顺序读取。
信号量（Semaphore） #
在有些场景下，多个进程需要依赖于进程间通信来同步彼此的状态，如执行的顺序等。此时，管道、消息队列这些能够传递数据但是不提供强制同步机制的方案是不太满足的。
信号量是由 Dijkstra 在 1965 年提出的一种方法，它更加强调“同步”，而不是“消息传递”。它本身传递的数据很少，一般来说只有一个共享的整型计数器，该计数器由内核维护，而对信号量的操作需要经过内核系统调用。
信号量的主要操作是两个原语：P 和 V（源自荷兰语），就是 Down 和 Up 的意思。在内核的信号量结构中，会封装一个计数器，P 将计数器减 1，V 将计数器加 1。P 操作的失败会将当前进程切换到阻塞状态，直到其他进程执行了 V 操作。
一个简单设计是使计数器只在 0 和 1 之间变化（二元信号量），当减小信号量时，内核会将所有试图将信号量降低到 0 以下的操作阻塞，类似的，将信号量累加到 1 以上的操作也会阻塞，这样就可以支持简单的进程间同步的需求。比如对于两个进程 A 和 B，希望在 A 执行后 B 再执行，那么它们可以共享一个信号量，A 在执行完成后，对共享信号量进行 V 操作，B 再执行代码前，对信号量执行 P 操作，如此就可以保证执行顺序。
System V 接口 #
System V 系统中针对信号量有 semget、semctl、semop 等操作。
semget 用于创建一个新的信号量集或获取一个既有集合的标识符。
int semget(key_t key, int nsems, int semflg);
- 如果是创建新的信号量
nsems会指定集合中的信号量的数量。
一个信号量集关联的数据结构如下：
struct semid_ds{
struct ipc_perm sem_perm;
time_t sem_otime;
time_t sem_ctime;
unsigned log sem_nsems;
}
semctl 用来删除、更新、初始化信号量集 semid 中的第 semnum 个信号量的值。
int semctl(int semid, int semnum, int cmd);
semop() 系统调用在 semid 标识的信号量集中的信号量上执行一个或多个操作。
int semop(int semid, struct sembuf *sops, unsigned int nsops);
struct sembuf{
unsigned short sem_num;
short sem_op;
short sem_flg;
}
sem_num标识了在集合中的第几个信号量上执行操作。sem_op标识了需执行的 P/V 操作
System V 信号量的缺点 #
- 接口过于复杂，通常情况下，一个程序只会操作一个信号量，同时操作集合中的多个信号量的能力是多余的，增加了编程复杂度。
- 内核不会维护引用信号量集的进程数量，这就给何时删除信号量的操作增加了难度。
- 信号量操作存在诸多限制，比如集合数量、操作数量、信号量最大值等。
- 创建和初始化是分开的接口，意味着需要为防止同一个信号量被竞争做额外工作。
- System V 的信号量是处于内核状态的，这也意味着更多的切换成本。
POSIX 接口 #
POSIX 信号量有两种，命名的和未命名的。命名信号量是通过一个名字标识的，它可以被所有拥有打开这个信号量的权限的进程共享。未命名信号量没有名字，但可以将它放在一块由进程或线程共享的内存区域中，使得这些进程或线程能够共享同一个信号量。
sem_open打开或创建一个信号量sem_close关闭一个信号量。sem_unlink删除一个信号量。sem_wait会递减一个 sem 引用的信号量的值。sem_post递增。sem_getvalue获取当前信号量的值。sem_init初始化一个未命名信号量。sem_destroy销毁一个未命名信号量。
共享内存（Shared Memory） #
前面已经介绍了管道、消息队列和信号量，它们都有一个共同的问题就是都在内核态处理数据，性能不太好，尤其是高并发情况下的资源竞争，会带来更多的并发同步问题要处理（下面会说有哪些机制）。于是 System V 和 POSIX 也都提供了基于共享内存的进程间通信方式，这是最快的一种 IPC，因为它所有的数据操作都是在用户态下完成的。
共享内存允许两个或多个进程共享物理内存的同一块区域（也称为段或页），两个不同进程的逻辑地址通过页表映射到物理空间的统一区域，它们共同指向的这块区域就是共享内存。当进程不再希望共享内存时，可以取消共享内存和虚拟内存之间的映射。
System V 接口 #
shmget用来创建一个新共享内存段或取得一个既有内存段的标识符。shmat用来附上共享内存段，即使该段成为调用进程的虚拟内存的一部分。同时返回一个指向进程的虚拟地址空间中该共享段的起点的指针。
POSIX 接口 #
shm_open创建共享内存对象。shm_unlink删除共享内存对象。
信号（Signal） #
管道、消息队列、共享内存等方式主要关注在数据传输的设计上，而信号是对事件发生时对进程的通知机制，虽然信号量也有通知能力，但是需要进程主动去查询计数器状态。通过信号，一个进程可以随时发送一个事件到特定的进程、线程或进程组等，并且接受信号不需要阻塞等待事件，内核会帮助进程切换到对应的处理函数中响应信号事件，并在处理完成后恢复之前的上下文，故信号机制有时也称为软件中断。
一个进程能够向另一个进程发送信号，也可以向自己发送信号，然而更多时候是内核向进程发送信号，引发内核为进程产生信号的各类事件如下：
- 硬件发生异常，比如执行了一条异常指令，或者引用了无法访问的内存空间等。
- 用户键入了能够产生信号的终端特殊字符，比如中断字符（Ctrl-C）。
- 发生了软件事件，比如调整了窗口大小、定时器到期等。
针对每一个信号，都定义了一个唯一的整数，由于每个信号的实际编号随系统不同而不同，所以在程序中总是使用 SIGINT 这些符号名。信号分为两大类，第一组用于向内核向进程通知事件，构成所谓传统信号或标准信号，编号为 1 ~ 31 号。后来 POSIX 又引入了实时信号，主要用于实时场景，编号为 32 ~ 64 号。
信号的发送 #
内核提供了接口用来发送信号，例如 kill 函数，与 shell 的 kill 命令类似。
信号的响应和处理 #
内核对信号的处理一般有下面三种情况：
- 忽略：直接忽略对应的信号。
- 用户处理函数：调用用户注册的信号处理函数。
- 内核默认处理函数：调用默认的内核处理函数（如果用户没有注册处理函数）。
Linux 提供了 signal、sigaction 等系统调用，允许用户为特定的信号注册一个用户态处理函数。
套接字（Socket） #
Socket 与上面几种进程间通信方式都不一样，它是一种既可用于本地，又可跨网络使用的通信机制。应用程序可以用相同的套接字接口来实现本地进程间通信和跨机器的网络通信。Socket 离我们好像很远，但其实也很近，它提供了非常丰富的底层 API，而且可以指定通信协议，比如是使用 TCP 协议还是 UDP 协议。
与其它的几个进程间通信相比，套接字强调的是“客户端/服务端”的模型，客户端通过一个特定的“地址”，套接字支持多种不同的地址类型，在进程间通信中，这里可以使用基于 IP 地址和端口的组合的地址，通信双方通常使用本地回环地址（127.0.0.1），然后各自绑定上不同的端口号，就可以通过网络协议进行通信。
此外，也可以使用本地文件系统中的一个路径作为地址，这通常叫做 Unix Domain Socket，又叫 IPC Socket，它不会经过操作系统网络协议栈，不需要打包拆包、计算校验和，只是将应用程序从一个进程拷贝到另一个进程。
socket API #
下面列一些常见的接口，你或许已经耳熟能详。
socket() 方法用来创建一个 socket。
int socket(int domain, int type, int protocol);
domain指定了 socket 的通信 domain（协议域），枚举有：- AF_UNIX，就是上面说的只能在本地应用程序之间通信的 Unix Domain Socket。
- AF_INET，通过 IPv4 的 domain 类型进行通信。
- AF_INET6，通过 IPv6 进行通信。
type指定了 Socket 的类型，枚举有：- 创建流 socket 时会被指定为
SOCK_STREAM，比如使用 TCP 时。 - 创建数据报 socket 会被指定为
SOCK_DGRAM，比如使用 UDP 时。
- 创建流 socket 时会被指定为
protocol一般为 0，会根据type自动选择。
bind() 系统调用将一个 socket 绑定到一个地址上。
listen() 系统调用允许一个 socket 接受来自其他 socket 的接入连接。
connect() 系统调用用来建立与另一个 socket 的连接。
accept() 系统调用会创建一个新的 socket，它在已经 listen 过的 socket 上接受来自一个客户端应用程序执行 connect 的连接，并返回这个新的 socket 的文件描述符。然后就可以通过传统的 read() 和 write() 来对新的 socket 的文件描述符进行读写操作。
close() 用来终止连接。
小结 #
同步原语 #
随着多核处理器以及其带来的并行技术的发展，操作系统通过多进程（线程）的任务调度提高处理能力的同时，也带来了一系列的并发问题。并行处理同一任务意味着对共享资源的并发访问，为了保证共享资源状态的正确性，需要正确地在这些子任务之间进行同步信息。
很多时候，我们说进程间通常是通信，因为他们往往是不同的任务，没有同步任务进度的必要，而同步一般是指进程和其线程、线程和线程之间的信息同步，但现在也不排除进程和进程之间对同一任务的信息同步，比如共享内存就需要同步机制来对资源的更新进行并发控制，而同步机制很多时候也需要通信工具来实现信息同步，可以说通信只是一种手段，实现同步才是目的，而同步最终的目标就是实现线程安全。
为了实现这些并发控制，逐渐抽象出了一系列同步原语（Synchronization Primitive），供开发者使用，下面开始展开介绍。
原语：一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。
互斥量（Mutex） #
临界区（Critical Section） #
线程的主要优势在于，能够通过全局变量来共享信息，不过这种便捷的共享是有代价的：必须确保多个线程不会同时修改同一变量，或者某一线程不会读取正由其他线程修改的变量。
临界区是指访问某一共享资源的代码片段，并且这段代码的执行应为原子（Atomic）操作。在同一时刻，最多只能有一个线程可以执行临界区的代码。而如何通过设计协议来保证互斥访问临界区的问题就成为临界区问题。
不管是多核还是单核，临界区问题都同样存在。单核中，由于调度器允许多个线程在一个核心交错执行，正在临界区内执行的线程可能会被打断，然后另一个线程又被调度进临界区，从而造成两个线程同时处于临界区的现象，导致竞争条件（race condition，也叫竞争冒险，race hazard）的出现。
互斥访问 #
一个有效解决临界区问题的方式是互斥（mutual exclusion，mutex）访问。互斥量有两种状态：已锁定和未锁定，同时提供了 lock 和 unlock 操作。任何时候，至多只有一个线程可以锁定该互斥量，试图对已锁定的某一互斥量再次加锁，将可能阻塞线程或者报错失败，具体取决于加锁使用的方法。一旦线程锁定了互斥量，随即成为互斥量的所有者，只有所有者才能给互斥量解锁，一般情况下，对每一共享资源会使用不同的互斥量。
为了保证临界区的互斥访问，我们可以在申请进入临界区时尝试获取一个共享的锁，只有拥有锁的代码才能被允许执行临界区的代码，在退出临界区时，线程将释放锁，从而允许其他线程拥有锁并进入临界区，以此来保证对共享资源的原子访问。
POSIX 接口 #
POSIX 线程提供了pthread_mutex_init 函数来初始化一个互斥量， pthread_mutex_lock 函数用来锁定一个互斥量，而 pthread_mutex_unlock 则可以将一个互斥量解锁。
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
自旋锁 #
自旋锁（Spin lock）也是一种互斥锁的实现，相比一般的互斥锁会将线程阻塞并释放 CPU 给其他线程，在自旋锁的实现中，它会一直占用 CPU，相当于在做 while 轮询，直到目标锁被释放为止。
可以使用 pthread_mutex_trylock 函数来尝试对共享变量加自旋锁，当目标锁被占用时，与 pthread_mutex_lock 会阻塞等待不同，trylock 会返回一个 EBUSY 错误，从而可以让开发者决定是否继续 while 循环（不释放当前线程的 CPU）。
互斥量的死锁 #
互斥量如果使用不当会造成死锁问题。有时，一个线程需要同时访问两个或更多的共享资源，而每个资源又都由不同的互斥量管理，当超过一个线程加锁同一组互斥量时，其中每个线程都成功地锁定住一个互斥量，并视图对另一个线程锁定的互斥量加锁，这时两个线程将无限期等待下去。要避免此类问题的最简单办法就是应该总是以相同的顺序对一组互斥量进行锁定。
条件变量（Condition Variable） #
考虑一个“生产者-消费者”的例子，当队列中的空位为 0 时，生产者会陷入循环等待（busy looping），而在消费者释放空位之前，这种循环等待是毫无意义的，这些无畏的循环不仅浪费 CPU 资源，还增加了系统的能耗，此时我们需要一个睡眠/唤醒的机制来解决问题，条件变量就是为了满足这样的需求设计的。
通过使用条件变量提供的接口，一个线程可以停止使用 CPU 并将自己挂起，当等待的条件满足时，其他线程会唤醒该挂起的线程让其继续执行。使用条件变量能够有效得避免无畏的循环等待。
条件变量要和互斥量一起使用，这种模式用于让一个线程锁住一个互斥量，然后当它不能获得它期待的结果时等待一个条件变量。最后另一个线程会向它发现信号，使它可以执行。
pthread_cond_wait 原子性地调用并解锁它持有的互斥量。
信号量（Semaphore） #
没错信号量除了可以实现 IPC 通信，也可以用于同步，在同步原语里也称为 PV 原语。借助互斥量、条件变量和一个计数器，信号量能实现的功能也要比互斥量和条件变量更强大，从而实现了更高层级的抽象。
读写锁（Reader Writer Lock） #
读写锁分为读锁和写锁。使用起来与互斥锁类似，但是如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。所以，读写锁适用于能明确区分读操作和写操作的场景，而互斥锁不能实现共享资源的“共读”。
RCU（Read-Copy Update） #
RCU，是 Linux 中比较重要的一种同步机制。顾名思义就是“读，拷贝更新”，再直白点是“随意读，但更新数据的时候，需要先复制一份副本，在副本上完成修改，再一次性地替换旧数据”。这是 Linux 内核实现的一种针对“读多写少”的共享数据的同步机制。与读写锁不用，RCU 的写者不会阻塞读者，且读者不需要额外的同步原语来保护读临界区。
管程（Monitor） #
前面介绍了互斥量、条件变量、信号量、读写锁这些同步原语来帮助开发者实现线程安全的应用程序，但是这些工具仍然相对底层和多样化，开发者在实际应用中稍有不慎就有可能出现死锁问题。因此为了减轻上层开发者的负担，更易于编写正确的程序，最早在 1974 年提出了管程的概念，它是一种高级的同步原语。
管程一般由编程语言来支持，编译器会对其进行实现。进入管程时的互斥由编译器负责，通常的做法是用一个互斥量或二元信号量，当一个进程调用管程过程时，该过程的前几条指令将检查管程中是否有其他的活跃进程，如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进入。
由于是编译器而非程序员来安排互斥，所以出错的可能性要小很多，程序员只需要通过关键字将临界区包装起来就可以，比如 Java 就是通过关键字 synchronized 实现的。
屏障（Barrier） #
还有一种同步机制，它不是为了共享资源的并发控制，而是为了能让一组进程/线程在一段时间后能够到达相同的阶段，即没有人领先也没有人落后。除非所有的进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段，一般通过在每个阶段的结尾安置屏障来实现这种行为。
比如 Go 语言的 sync.WaitGroup 就实现了并发 Goroutine 的执行屏障的效果，等待多个 Goroutine 执行完毕，这里有一个例子。
死锁（Deadlock） #
死锁是并发同步机制带来的一个最主要的问题，所以还是专门总结一下死锁。什么是死锁就不介绍了，上面已经提过了。
饥饿问题 #
上一篇已经提到了由于一些调度策略的优先级问题，一些任务可能由于无法得到 CPU 资源而陷入饥饿状态，现在我们也发现，线程也会因为死锁进入饥饿状态。
哲学家就餐问题 #
1965 年，Dijkstra 提出并解决了一个他称为 哲学家就餐 的同步问题。问题是这样的：五个哲学家围坐在一张圆桌前，而哲学家的生活就是思考和吃饭。就餐的安排很简单，每个哲学家前面都有一盘意大利面，如图所示，每个盘子旁边都有一把叉子，而每个哲学家都需要两把叉子吃面。
要求来了：设计一套哲学家吃饭的算法，算法必须保证互斥，即两位相邻的哲学家不能同时使用同一把叉子，而且还要避免死锁和饥饿。如果五位哲学家同时拿起左边的叉子，就没人能够拿到他们右面的叉子，于是发生死锁。
从那时起，每个发明新的同步原语的人都希望通过解决哲学家就餐问题来展示其同步原语的精妙之处。而 Dijkstra 的解法就是上面提到的信号量。
产生死锁的条件 #
产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程/线程使用。
（2） 持有并等待条件：线程持有一些资源，同时也在等待一些资源。
（3） 非抢占条件：进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。
死锁预防 #
死锁预防是通过设计合理的资源分配算法，从源头上预防死锁。为了实现这个目标，只需要保证产生死锁的四个必要条件不被同时满足：
（1）避免互斥访问
（2）不允许持有并等待。
（3）允许资源被抢占。
（4）避免循环等待。
死锁避免 #
除了死锁预防，死锁避免是解决死锁的另一种思路。死锁避免是通过在系统运行时跟踪资源分配过程来避免出现死锁。主要有两个方法：
（1）进程启动拒绝：如果一个进程的请求会导致死锁，这不启动该进程。
（2）资源分配拒绝：如果一个进程增加的资源请求会导致死锁，则不允许这一资源分配。
资源拒绝分配策略，又称银行家算法（banker algorithm），还是由 Dijkstra 在 1965 年提出的。
死锁检测和恢复 #
死锁检测是在死锁发生后，通过检测以尽早发现死锁。检测到死锁后，就需要一些策略来恢复死锁。
鸵鸟策略 #
还有一种对死锁的处理方式，就是像鸵鸟把头埋到沙子里一样，假装根本没有问题发生。如果一个场景的死锁发生的概率非常低（比如一年一次），而处理办法仅仅是重启程序就可以。死锁问题理论上确实存在，但是现实中也不是一定要处理，那么成本非常低的鸵鸟策略显然就是优先选择了。
活锁（live lock） #
除了死锁，还有活锁。活锁类似死锁，出现活锁时，锁的竞争者很长一段时间都无法获取锁进入临界区，但是锁并没有发生阻塞，听起来好像感觉“活死人”比“死人”更可怕。
产生这种现象的大概场景是，在试图满足“不允许持有并等待”的死锁预防方法时，会要求一次性申请所有资源（A 锁和 B 锁），一旦任意需要获取的资源不可用，则需要放弃所有已经占有的资源并尝试重新获取。这样便可能有一种特殊情况出现：一个线程获取了锁 A 并尝试获取锁 B，同时另一个线程获取了锁 B 并尝试获取锁 A，那两个线程就会各自释放已经获取的锁并重试，然后失败再次重试，如此往复。
一个简单有效的办法是，让线程在重试前等待一个随机的时间，从而使两个线程的执行顺序分开，以减少活锁出现的概率。
结束语 #
从全局角度看这四篇内容可能只是操作系统的进程/线程调度相关的学习笔记，在查阅资料的时候也能体会到几乎每一个概念其实都可以更详细的展开，这里只能算是一个总览/大纲，以后详细的内容可能会在新的文章里继续讨论。如果你现在就需要继续深入的话，可以看看下面的一些书，这些里面有更多的实现细节。
以下三本是同一个作者！！
其他在线链接：