多线程杂谈

进程与线程

进程

我们编写的代码只是一个存储在硬盘的静态文件，通过编译后就会生成二进制可执行文件，当我们运行这个可执行文件后，它会被装载到内存中，接着 CPU 会执行程序中的每一条指令，那么这个运行中的程序，就被称为「进程」（Process）。

多个程序、交替执行的思想，就是 CPU 管理多个进程的初步想法。例如当进程要从硬盘读取数据时，CPU 不需要阻塞等待数据的返回，而是去执行另外的进程。当硬盘数据返回时，CPU 会收到个中断，于是 CPU 再继续运行这个进程。

虽然单核的 CPU 在某一个瞬间，只能运行一个进程。但在 1 秒钟期间，它可能会运行多个进程，这样就产生并行的错觉，实际上这是并发。

并发与并行

• 并发（Concurrency）：

  并发是指在同一时间段内，多个任务交替执行。并发并不要求多个任务同时执行，而是任务之间可以交替进行。在单核 CPU 上，通过快速切换任务，使得多个任务看起来像是同时进行的，这就是并发。并发的关键在于任务的交替执行和管理。

  如在一个 Web 服务器上，多个客户端请求可以并发处理，即使服务器只有一个 CPU 核心，它也可以通过快速切换处理不同的请求。

• 并行（Parallelism）：

  并行是指在同一时刻，多个任务同时执行。并行需要多个处理器或多核处理器来实现真正的同时执行。并行的关键在于任务的同时执行。

  如在一个多核 CPU 上，多个计算任务可以分配到不同的核心上同时执行，这就是并行。

进程的状态

进程有五种状态：创建、就绪、执行、阻塞、终止：

• 创建：一个进程启动，首先进入创建状态，需要获取系统资源创建进程管理块（PCB：Process Control Block）完成资源分配。

• 就绪状态：在创建状态完成之后，进程已经准备好，处于就绪状态，但是还未获得处理器资源，无法运行。

• 运行状态：获取处理器资源，被系统调度，当具有时间片开始进入运行状态。如果进程的时间片用完了就进入就绪状态。

• 阻塞状态：在运行状态期间，如果进行了阻塞的操作，此时进程暂时无法操作就进入到了阻塞状态，在这些操作完成后就进入就绪状态。等待再次获取处理器资源，被系统调度，当具有时间片就进入运行状态。

• 终止状态：进程结束或者被系统终止，进入终止状态。

进程的控制结构

在操作系统中，是用 进程控制块（process control block，PCB） 数据结构来描述进程的。PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

PCB 包含的信息：

1. 进程描述信息：

• 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
• 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

2. 进程控制和管理信息：

• 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
• 进程优先级：进程抢占 CPU 时的优先级；

3. 资源分配清单：

• 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

4. CPU 相关信息：

• CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

PCB 通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

• 将所有处于就绪状态的进程链在一起，称为就绪队列；
• 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；

另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

进程的上下文切换

进程的上下文切换是指操作系统在多任务处理中，将 CPU 从一个进程切换到另一个进程的过程。上下文切换的主要目的是使多个进程能够共享 CPU 资源，从而实现并发执行。

上下文切换的主要流程

1. 保存当前进程的上下文：

当操作系统决定暂停当前正在运行的进程时，它需要保存该进程的上下文信息。这些信息包括：

• CPU 寄存器的值（如程序计数器、堆栈指针等）
• 进程状态
• 内存管理信息
• 打开的文件描述符等

这些信息通常保存在进程控制块（PCB）中。

2. 更新进程状态：

将当前进程的状态更新为“等待”或“就绪”，以便操作系统知道该进程当前不在运行。

3. 选择下一个进程：

操作系统的调度器选择下一个要运行的进程。这个选择可以基于多种调度算法，如先来先服务（FCFS）、最短作业优先（SJF）、轮转调度（RR）等。

4. 恢复下一个进程的上下文：

从下一个进程的 PCB 中恢复其上下文信息，包括 CPU 寄存器的值、内存管理信息等。

5. 更新进程状态：

将下一个进程的状态更新为“运行”，表示该进程正在运行。

6. 切换到下一个进程：

最后，操作系统将控制权交给下一个进程，开始执行该进程的代码。

线程

线程是操作系统中最小的执行单元，它是进程的一部分。一个进程可以包含一个或多个线程，这些线程共享进程的资源（如内存、文件描述符等），但每个线程有自己的栈、程序计数器和寄存器。

线程与进程的比较

线程与进程的比较如下：

• 进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位；
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
• 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
• 线程能减少并发执行的时间和空间开销；

对于线程相比进程能减少开销，体现在：

• 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
• 线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
• 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
• 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

所以，不管是时间效率，还是空间效率线程比进程都要高。

线程的上下文切换

在前面我们知道了，线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。

所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

对于线程和进程，我们可以这么理解：

• 当进程只有一个线程时，可以认为进程就等于线程；
• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

在线程进行上下文切换时：

• 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
• 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；

所以，线程的上下文切换相比进程，开销要小很多。

进程间通信方式

由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，管道分为「匿名管道」和「命名管道」。

1. 匿名管道: 顾名思义，它没有名字标识，匿名管道是特殊文件, 只存在于内存，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。

2. 命名管道: 突破了匿名管道只能在亲缘关系进程间的通信限制，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信。另外，不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持 lseek 之类的文件定位操作。

管道这种通信方式效率低，不适合进程间频繁地交换数据。当然，它的好处，自然就是简单

3. 消息队列: 克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

消息队列通信不及时，且消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销

3. 共享内存: 可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

共享内存会使得多进程竞争同个共享资源从而造成数据的错乱

4. 信号量: 那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

信号量虽然可以实现互斥访问，但无法在进程间传递数据，因此信号量通常与共享内存结合使用，共享内存用于传递数据，信号量用于同步和互斥。

5. 信号：与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SIGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。

6. Socket：前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

以上，就是进程间通信的主要机制了。你可能会问了，那线程通信间的方式呢？

同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步：

• 互斥的方式，可保证任意时刻只有一个线程访问共享资源；
• 同步的方式，可保证线程 A 应在线程 B 之前执行；

实现线程间同步与互斥的主要方式有：锁（自旋锁、互斥锁、读写锁）、条件变量、信号量等。

进程调度

进程调度是操作系统管理多任务处理的关键机制之一。它决定了在任何给定时间哪个进程或线程应该获得 CPU 资源进行执行。进程调度的主要目标是提高系统性能和资源利用率，同时确保所有进程公平地获得执行机会。

先来先服务（First Come First Serve, FCFS）算法

顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。

FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

最短作业优先（Shortest Job First, SJF）调度算法

顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

高响应比优先 （Highest Response Ratio Next, HRRN）调度算法

每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：

$$优先度 = \frac{等待时间 + 要求服务时间}{要求服务时间}$$

高响应比优先调度算法是「理想型」的调度算法，现实中是实现不了的。

时间片轮转（Round Robin, RR）调度算法

时间片轮转调度算法是一种抢占式调度算法，每个进程被分配一个时间片，当进程用完时间片后，操作系统会将进程从 CPU 中移除，然后放到就绪队列的末尾，然后选择下一个进程运行。

时间片轮转调度算法是一种公平的调度算法，每个进程都有相同的机会获得 CPU 时间，但是当时间片设置的太大时，会导致响应时间变长，当时间片设置的太小时，会导致进程切换过于频繁，降低系统的效率。

最高优先级优先（Highest Priority First, HPF）调度算法

每次从就绪队列中选择优先级最高的进程运行，如果有多个进程的优先级相同，那么就采用 FCFS 算法。

这种调度算法的问题在于，可能会导致低优先级的进程饥饿，因为高优先级的进程总是会被优先调度。

多级反馈队列（Multilevel Feedback Queue, MFQ）调度算法

多级反馈队列调度算法是一种综合性的调度算法，它结合了时间片轮转和最高优先级优先调度算法。

多级反馈队列调度算法的基本思想是：将就绪队列分成多个队列，每个队列有不同的优先级，优先级高的队列的时间片短，优先级低的队列的时间片长。

当一个进程进入就绪队列时，首先进入优先级最高的队列，如果在时间片内没有运行完，那么就会被移到下一个优先级的队列，直到运行完为止。

多级反馈队列调度算法的优点是：能够兼顾短作业和长作业，提高系统的吞吐量。

完全公平调度（Completely Fair Scheduler, CFS） 调度算法

CFS 是 Linux 内核中的一种调度算法，它是一种基于红黑树的调度算法，CFS 通过维护每个进程的虚拟运行时间来实现公平性。虚拟运行时间是进程实际运行时间的一个加权值，权重由进程的优先级决定。优先级越高，虚拟运行时间增加得越慢。调度器总是选择虚拟运行时间最小的进程进行调度，从而确保所有进程都能公平地获得 CPU 时间。

CFS 使用红黑树（红黑树是一种自平衡二叉搜索树）来存储所有的可运行进程。红黑树的性质使得插入、删除和查找操作的时间复杂度为 O(log N)，其中 N 是树中的节点数。
红黑树的中序遍历可以得到所有进程按虚拟运行时间排序的列表，这使得调度器可以快速找到虚拟运行时间最小的进程。

CFS 调度算法的优点是：能够保证每个进程都能获得公平的 CPU 时间。

总结

• FCFS：适用于 CPU 繁忙型作业的系统，不适用于 I/O 繁忙型作业的系统；
• SJF：适用于短作业优先的系统，不适用于长作业优先的系统；
• HRRN：是一种理想型的调度算法，现实中是实现不了的；
• RR：是一种公平的调度算法，但是时间片设置的太大时，会导致响应时间变长，时间片设置的太小时，会导致进程切换过于频繁；
• HPF：可能会导致低优先级的进程饥饿；
• MFQ：能够兼顾短作业和长作业，提高系统的吞吐量。
• CFS：能够保证每个进程都能获得公平的 CPU 时间。

线程间的同步与互斥

竞争条件（race condition）: 当多线程相互竞争操作共享变量时，由于不可控的调度，在执行过程中可能会发生上下文切换，因此会得到错误的结果，事实上，每次运行都可能得到不同的结果，因此输出的结果存在不确定性（indeterminate）。

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。

我们希望这段代码是**互斥（mutualexclusion）**的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程。

另外，说一下互斥也并不是只针对多线程。在多进程竞争共享资源的时候，也同样是可以使用互斥的方式来避免资源竞争造成的资源混乱。

互斥解决了并发进程/线程对临界区的使用问题。这种基于临界区控制的交互作用是比较简单的，只要一个进程/线程进入了临界区，其他试图想进入临界区的进程/线程都会被阻塞着，直到第一个进程/线程离开了临界区。

我们都知道在多线程里，每个线程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个线程能密切合作，以实现一个共同的任务。

例子：线程 1 是负责读入数据的，而线程 2 是负责处理数据的，这两个线程是相互合作、相互依赖的。线程 2 在没有收到线程 1 的唤醒通知时，就会一直阻塞等待，当线程 1 读完数据需要把数据传给线程 2 时，线程 1 会唤醒线程 2，并把数据交给线程 2 处理。

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

原子操作

由于锁以及信号量都是基于原子操作实现的，因此这里先介绍一下原子操作

原子操作(atomic operation)是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。保证访问共享资源是唯一的。

一般原子操作需要 CPU 等硬件支持，使用硬件同步原语来实现原子操作。常用的原语有 CAS（compare-and-swap）、TAS（test-and-set）、TTAS (Test and test-and-set ) 以及 FAA（fetch-and-add）。

CAS

在计算机科学中，比较与交换(CAS)是多线程中用来实现同步的原子指令。它将内存位置的内容与给定值进行比较，只有当它们相同时，才将该内存位置的内容修改为新的给定值。这是作为单个原子操作完成的。

bool CAS(int* p, int oldVal, int newVal) {
  if (*p != oldVal) {
    return false;
  }
  *p = newVal;
  return true;
}

CAS 存在的问题

CAS操作无法检测到变量值在预期值和新值之间发生了变化。例如，变量值从A变为B，然后又变回A，CAS操作会认为变量值没有变化，从而导致错误的更新，这就是经典的ABA问题。

ABA问题的根本在于CAS 在修改变量的时候，无法记录变量的状态，比如修改的次数，否修改过这个变量。这样就很容易在一个线程将A修改成B时，另一个线程又会把B修改成A,造成 CAS 多次执行的问题。

解决ABA问题的一种方法是使用版本号或标记位，如 JAVA 中的 AtomicStampedReference，AtomicStampedReference 是 Java 中的一种原子类，用于解决 CAS 操作中的 ABA 问题。它不仅维护一个引用值，还维护一个整数标记（stamp），以确保在进行 CAS 操作时，能够检测到引用值是否经历了多次变化。

AtomicStampedReference 通过维护一个引用和一个整数标记来实现原子操作。每次更新引用时，都会同时更新标记。这样，即使引用值在预期值和新值之间发生了变化，只要标记也发生了变化，CAS 操作就会失败，从而避免 ABA 问题。

TAS

在计算机科学中，test-and-set指令是一种用来将 1 (set)写入一个内存位置，并以单个原子的形式返回其旧值的指令。这些代码是原子执行。因为既可以测试旧值，又可以设置新值，所以我们把这条指令叫作「测试并设置」。

int TAS(int* p, int newVal) {
  int oldVal = *p;
  *p = newVal;
  return oldVal;
}

TAS特点是自旋，也就是循环，每次尝试去设置值，如果设置成功则会返回，如果没有返回就会一直自旋，直到设置成功。此时进入临界区，执行完临界区数据，再设置bool变量为false。从而让其他线程拿到锁。

TTAS

TTAS 是 Test and Test-and-Set 的缩写，它是对 TAS 的一种优化。TTAS的特点也是自旋，主要是为了降低性能开销，主要思路是减少回写（CAS导致的不断修改共享变量的值）。第一步先去检测 lock是否空闲；不可用就让出CPU，可用就执行TAS进行CAS操作，只有一个线程先观测到lock是空闲的，该线程才会尝试的去获取它，从而消除一部分回写操作。

bool lock = false;
bool TTAS() {
  while (true) {
    while (lock) {
      // do nothing
    }
    if (!TAS(&lock, true)) {
      return true;
    }
  }
}

FAA

在计算机科学中，fetch-and-add是一种原子操作，它将一个值添加到一个内存位置，并返回该位置的旧值。这是作为单个原子操作完成的。

int FAA(int* p, int addVal) {
  int oldVal = *p;
  *p += addVal;
  return oldVal;
}

锁

使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。

任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

自旋锁

自旋锁是一种锁的实现方式，它的特点是：当一个线程尝试获取锁时，如果锁已经被其他线程获取，那么该线程会一直循环等待，直到获取到锁为止。

我们可以用 CAS 原子操作来实现自旋锁，代码如下：

typedef struct lock_t {
  int flag;
} lock_t;

void init(lock_t* lock) {
  lock->flag = 0;
}

void lock(lock_t* lock) {
  while (TAS(&lock->flag, 1)) {
    // do nothing
  }
}

void unlock(lock_t* lock) {
  lock->flag = 0;
}

我们来确保理解为什么这个锁能工作：

• 第一个场景是，首先假设一个线程在运行，调用 lock()，没有其他线程持有锁，所以 flag 是 0。当调用 TestAndSet(flag, 1) 方法，返回 0，线程会跳出 while 循环，获取锁。同时也会原子的设置 flag 为1，标志锁已经被持有。当线程离开临界区，调用 unlock() 将 flag 清理为 0。

• 第二种场景是，当某一个线程已经持有锁（即 flag 为1）。本线程调用 lock()，然后调用 TestAndSet(flag, 1)，这一次返回 1。只要另一个线程一直持有锁，TestAndSet() 会重复返回 1，本线程会一直忙等。当 flag 终于被改为 0，本线程会调用 TestAndSet()，返回 0 并且原子地设置为 1，从而获得锁，进入临界区。

很明显，当获取不到锁时，线程就会一直 while 循环，不做任何事情，所以就被称为「忙等待锁」，也被称为自旋锁（spin lock）。

这是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

互斥锁

互斥锁是一种更高级的锁，它允许线程在无法获取锁时进入睡眠状态，而不是忙等待。这样可以让 CPU 用于其他任务，而不是浪费在自旋上。

type struct lock_t{
    int flag;
    queue_t *q;    // 等待队列
} lock_t;

void init(lock_t *lock)
{
    lock->flag = 0;
    queue_init(lock->q);
}

void lock(lock_t *lock)
{
    while(TestAndSet(&lock->flag, 1) == 1)
    {
        // 保存现在运行线程 TCB;
        // 将现在运行的线程 TCB 插入到等待队列;
        // 设置该线程为等待状态;
        // 调度程序;
    }
}

void unlock(lock_t *lock)
{
    if(lock->q != NULL)
    {
        // 移出等待队列的队头元素;
        // 将该线程的 TCB 插入到就绪队列;
        // 设置该线程为就绪状态;
    }
    lock->flag = 0;
}

互斥锁是一种「独占锁」，比如当线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放手中的锁，线程 B 加锁就会失败，于是就会释放 CPU 让给其他线程，既然线程 B 释放掉了 CPU，自然线程 B 加锁的代码就会被阻塞。

对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。当加锁失败时，内核会将线程置为「睡眠」状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，于是就可以继续执行。如下图：

所以，互斥锁加锁失败时，会从用户态陷入到内核态，让内核帮我们切换线程，虽然简化了使用锁的难度，但是存在一定的性能开销成本。

那这个开销成本是什么呢？会有两次线程上下文切换的成本：

当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
接着，当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。
线程的上下文切换的是什么？当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

上下切换的耗时有大佬统计过，大概在几十纳秒到几微秒之间，如果你锁住的代码执行时间比较短，那可能上下文切换的时间都比你锁住的代码执行时间还要长。

所以，如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

条件变量用于线程间的等待和通知机制，通常与互斥锁一起使用。它允许线程在某个条件不满足时进入等待状态，并在条件满足时被唤醒。

递归锁

递归锁是一种特殊的锁，用于解决线程在多次获取同一个锁时产生死锁的问题。在递归锁中，同一个线程可以多次获取同一个锁，而不会造成死锁。

递归锁具有两个主要操作：上锁（lock）和解锁（unlock）。线程可以多次上锁，但必须相应地多次解锁才能完全释放该锁。只有当线程解锁次数与上锁次数相等时，其他线程才能获取该锁。

递归锁的工作原理如下：

• 当一个线程请求上锁时，如果锁是未上锁状态，则线程获取锁并将其状态设置为已上锁，并将上锁次数设置为1。

• 如果同一个线程再次请求上锁，递归锁会检查当前线程是否已经持有该锁。如果是，则上锁次数加1，锁继续保持上锁状态。

• 当线程解锁时，上锁次数减1。只有当上锁次数减到0时，锁才会完全释放，其他线程才能获取该锁。

递归锁通常应用于以下情况：

• 递归函数或方法：当一个递归函数或方法需要在每一次递归调用时获取同一个锁时，递归锁可以保证线程不会因为获取同一个锁而产生死锁。

• 嵌套的临界区：当一个线程在一个临界区内部再次进入同一个临界区时，递归锁可以确保线程不会因为自己已经持有锁而被阻塞。

读写锁

读写锁从字面意思我们也可以知道，它由「读锁」和「写锁」两部分构成，如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。

所以，读写锁适用于能明确区分读操作和写操作的场景。

读写锁的工作原理是：

当「写锁」没有被线程持有时，多个线程能够并发地持有读锁，这大大提高了共享资源的访问效率，因为「读锁」是用于读取共享资源的场景，所以多个线程同时持有读锁也不会破坏共享资源的数据。但是，一旦「写锁」被线程持有后，读线程的获取读锁的操作会被阻塞，而且其他写线程的获取写锁的操作也会被阻塞。

所以说，写锁是独占锁，因为任何时刻只能有一个线程持有写锁，类似互斥锁和自旋锁，而读锁是共享锁，因为读锁可以被多个线程同时持有。

知道了读写锁的工作原理后，我们可以发现，读写锁在读多写少的场景，能发挥出优势。

另外，根据实现的不同，读写锁可以分为「读优先锁」和「写优先锁」。

• 读优先锁期望的是，读锁能被更多的线程持有，以便提高读线程的并发性，它的工作方式是：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁。

• 而「写优先锁」是优先服务写线程，其工作方式是：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取写锁。

乐观锁与悲观锁

乐观锁和悲观锁是两种不同的并发控制机制，用于解决多线程或多进程环境下的数据一致性问题。它们的主要区别在于对数据冲突的处理方式。

• 悲观锁

  悲观锁假设数据冲突是常见的，因此在访问数据时会先加锁，以防止其他线程或进程同时访问该数据。悲观锁通常用于写操作较多的场景。前文提到的自旋锁、互斥锁、读写锁都属于悲观锁。

• 乐观锁

  乐观锁假设数据冲突是罕见的，因此在访问数据时不会加锁，而是在提交更新时检查数据是否发生冲突。乐观锁通常用于读操作较多的场景。乐观锁的实现方式有很多，比如 CAS 操作、版本号、时间戳等。由于乐观锁全程不加锁，因此又被称为无锁编程。

  乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

死锁

死锁是指在多线程或多进程环境中，两个或多个线程或进程相互等待对方释放资源，从而导致所有线程或进程都无法继续执行的情况。死锁会导致系统资源被无限期地占用，程序无法继续运行。

死锁的四个必要条件：

• 互斥条件：一个资源每次只能被一个线程或进程使用。

• 请求与保持条件：一个线程或进程因请求资源而阻塞时，对已获得的资源保持不放。

• 不剥夺条件：线程或进程已获得的资源，在未使用完之前，不能被其他线程或进程强行剥夺。

• 循环等待条件：若干线程或进程之间形成一种头尾相接的循环等待资源关系。

死锁的预防方法：

• 破坏互斥条件：将互斥资源改为非互斥资源。

• 破坏请求与保持条件：一次性申请所有资源。

• 破坏不剥夺条件：当一个线程获取资源失败时，释放已经获取的资源，等待一段时间后再次尝试。

• 破坏循环等待条件：对资源进行排序，按照顺序申请资源。

信号量

信号量实际上是一个非负的整数计数器，用来实现对公共资源的控制。在公共资源增加的时候，信号量就增加；公共资源减少的时候，信号量就减少；只有当信号量的值大于0的时候，才能访问信号量所代表的公共资源。

信号量是操作系统提供的一种协调共享资源访问的方法。

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。

另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：

P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

P 操作是用在进入临界区之前，V 操作是用在离开临界区之后，这两个操作是必须成对出现的。

信号量数据结构与PV 操作的算法描述如下图：

// 信号量数据结构
type struct sem_t {
    int sem;        // 资源个数
    queue_t *q;     // 等待队列
} sem_t;

// 初始化信号量
void init(sem_t *s, int sem)
{
    s->sem = sem;
    queue_init(s->q);
}

// P 操作
void P(sem_t *s)
{
    s->sem--;
    if(s->sem < 0)
    {
        // 1. 保留调用线程 CPU 现场;
        // 2. 将该线程的 TCB 插入到 s 的等待队列;
        // 3. 设置该线程为“等待”状态;
        // 4. 执行调度程序;
    }
}

// V 操作
void V(sem_t *s)
{
    s->sem++;
    if(s->sem <= 0)
    {
        // 1. 移出 S 等待队列首元素;
        // 2. 将该线程的 TCB 插入就绪队列;
        // 3. 设置该线程为“就绪”状态;
    }
}

PV 操作的函数是由操作系统管理和实现的，所以操作系统已经使得执行 PV 函数时是具有原子性的。

信号量的应用

临界区的互斥访问控制

为每类共享资源设置一个信号量 s，其初值为 1，表示该临界资源未被占用。

只要把进入临界区的操作置于 P(s) 和 V(s) 之间，即可实现进程/线程互斥：

此时，任何想进入临界区的线程，必先在互斥信号量上执行 P 操作，在完成对临界资源的访问后再执行 V 操作。由于互斥信号量的初始值为 1，故在第一个线程执行 P 操作后 s 值变为 0，表示临界资源为空闲，可分配给该线程，使之进入临界区。

若此时又有第二个线程想进入临界区，也应先执行 P 操作，结果使 s 变为负值，这就意味着临界资源已被占用，因此，第二个线程被阻塞。

并且，直到第一个线程执行 V 操作，释放临界资源而恢复 s 值为 0 后，才唤醒第二个线程，使之进入临界区，待它完成临界资源的访问后，又执行 V 操作，使 s 恢复到初始值 1。

对于两个并发线程，互斥信号量的值仅取 1、0 和 -1 三个值，分别表示：

1. 如果互斥信号量为 1，表示没有线程进入临界区；
2. 如果互斥信号量为 0，表示有一个线程进入临界区；
3. 如果互斥信号量为 -1，表示一个线程进入临界区，另一个线程等待进入。

通过互斥信号量的方式，就能保证临界区任何时刻只有一个线程在执行，就达到了互斥的效果。

事件同步

举个生活的同步例子，你肚子饿了想要吃饭，你叫妈妈早点做菜，妈妈听到后就开始做菜，但是在妈妈没有做完饭之前，你必须阻塞等待，等妈妈做完饭后，自然会通知你，接着你吃饭的事情就可以进行了。

使用信号量实现上述的线程间同步，代码如下：

semaphore s1 = 0;    // 表示不需要吃饭
semaphore s2 = 0;    // 表示饭还没做好

// 儿子线程函数
void son()
{
    while(TRUE)
    {
        // 肚子饿;
        V(s1);    // 叫妈妈做饭
        P(s2);    // 等待妈妈做完饭
        // 吃饭;
    }
}

// 妈妈线程函数
void mon()
{
    while(TRUE)
    {
        P(s1);    // 询问需不需要做饭
        // 做饭;
        V(s2);    // 做完饭，通知儿子吃饭
    }
}

妈妈一开始询问儿子要不要做饭时，执行的是 P(s1) ，相当于询问儿子需不需要吃饭，由于 s1 初始值为 0，此时 s1 变成 -1，表明儿子不需要吃饭，所以妈妈线程就进入等待状态。

当儿子肚子饿时，执行了 V(s1)，使得 s1 信号量从 -1 变成 0，表明此时儿子需要吃饭了，于是就唤醒了阻塞中的妈妈线程，妈妈线程就开始做饭。

接着，儿子线程执行了 P(s2)，相当于询问妈妈饭做完了吗，由于 s2 初始值是 0，则此时 s2 变成 -1，说明妈妈还没做完饭，儿子线程就等待状态。

最后，妈妈终于做完饭了，于是执行 V(s2)，s2 信号量从 -1 变回了 0，于是就唤醒等待中的儿子线程，唤醒后，儿子线程就可以进行吃饭了。