第1章　操作系统概述 链接到标题

操作系统有两个职责：对硬件进行管理和抽象，为应用提供服务并进行管理。
从硬件的角度来看，操作系统核心功能是将优先的，离散的资源高效的抽象为无限的、连续的资源。
从应用的角度来看，操作系统提供了不同层次，不同功能的接口，还提供了不同类型的访问控制。还负责对应用生命周期的管理，包括应用的加载、启动、切换、调度、销毁等。

API vs ABI
API 是指应用编程接口，它定义了两层软件之间的源码层面的交互接口。
ABI 是指应用二进制接口，即在某个特定体系结构下两层软件之间二进制层面的交互接口，包括如何定义二进制文件格式、应用之间的调用约定、数据模式等。

第2章　硬件结构 链接到标题

冯诺依曼结构包括三个主要部分：

  • 中央处理单元（CPU）：主要负责运算和逻辑控制，按照程序中的指令进行计算，并且根据条件执行程序中的不同部分
  • 存储器（memory unit）：负责存储程序指令和数据，以及保存程序执行的中间结果和最终结构。在现代计算机中，存储器通常包括寄存器、cpu 缓存、内存等存储层次。
  • 输入输出（I/O）：负责与外界进行交互，从外界获得输入，将结果向外界输出。

指令集架构（ISA）是 CPU 和软件之间的桥梁。ISA 包含指令集、特权级、寄存器、执行模式、安全扩展、性能加速扩展等方面。

指令集是 ISA 的重要组成部分，通常包含一系列不同功能的指令，用于数据搬移、计算、内存访问、过程调用等。

AArch64 属于精简指令集计算机（RISC）。AArch64 每跳指令的长度固定为 4 字节，指令类型包括：

  • 数据搬移指定（mov）；
  • 寄存器计算指令（add，sub）；
  • 内存读写指令（ldr，str）；
  • 跳转指令（b）；
  • 过程调用指令（bl，ret）；
  • 特权指令（msr，mrs）。

特权级也是 ISA 的重要组成部分。AArch64 中的特权级被称为异常级别（Exception Level，EL），共有四种特权级：

  • EL0：最低的特权级，应用程序通常运行在该特权级，也成为用户态
  • EL1：操作系统通常运行在该特权级，也成为内核态
  • EL2：在虚拟化场景下需要，虚拟机监控器（VMM，也称为 Hypervisor）通常运行在该特权级
  • EL3：和安全特性 TrustZone 相关，负责普通世界（normal word）和安全世界（secure world）之间的切换

一般来说，EL0 切换到 EL1 的可能场景有三种：

  1. 应用程序需要调用操作系统提供的系统调用，此时应用程序会通过执行 svc（特权调用 supervisor call）指令将 CPU 特权级从 EL0 切换到 EL1
  2. 应用程序执行了一条指令，而该指令触发了异常（exception），该异常导致 CPU 特权级从 EL0 切换到了 EL1。例如，应用在执行一条访存指令时，触发了缺页异常（page fault），从而切换到操作系统内核进行处理
  3. 应用程序在执行的过程中，CPU 收到了一个来自外设的中断（interrupt），该中断也会导致 CPU 特权级从 EL0 切换到 EL1 前两种成为同步的 CPU 特权级切换，因为都是由于 CPU 正在执行的指令所导致的，第三种 CPU 发生的切换并不是由于指令导致的，属于异步的 CPU 特权级切换。

在发生特权级切换时，CPU 负责保存当前执行状态，以便操作系统内核在处理异常是使用并在处理结束后能够恢复应用程序的执行，CPU 保存的主要状态包括：

  • 触发异常的指令地址（即当前的程序计数器（Program Counter,PC）），保存在 ELR_EL1（异常链接寄存器）中；
  • 异常原因（即异常是由于执行 svc 指令还是由于访存缺页导致的），保存在 ESR_EL1（异常症状寄存器）中；
  • CPU 将栈指针（SP）从 SP_EL0 切换到 SP_EL1 ；
  • CPU 还会保存一些其他状态，例如将 CPU 的相关状态保存在 SPSR_EL1（以保存的程序状态寄存器）中，将引发缺页异常的地址保存在 FAR_EL1 （错误地址寄存器）中。

寄存器是 ISA 的另一个重要组成部分，在 aarch64 中，有 31 个 64 位通用寄存器，被命名为 X0~X30，其中 X29 用作帧指针（FP）寄存器，按照惯例，一般用于保存函数调用过程中栈顶的地址；X30 用作链接指针（LP）寄存器，因为 CPU 在执行函数调用指令 b1 时会自动把返回地址保存在其中。

在 EL1 特权级下由两个“页表基地址寄存器（TTBR）“，即 TTBR0_EL1 和 TTBR1_EL1 ，它们负责翻译虚拟地址空间中不同的地址段，负责的地址范围由另一个控制寄存器 TCR_EL1（翻译控制寄存器）决定。操作系统中一种常见的配置是 TTBR0_EL1 负责[0，2^48）的地址映射（作为用户地址空间），TTBR1_EL1 负责[2^48 ,2^64）地址映射（作为操作系统内核地址空间）。

CPU 使用物理内存的方式：通过总线向物理内存发送一个读写请求，其中包括目标地址，物理内存在收到请求后进行读写操作。因此从 CPU 的角度，可以把物理内存看做由字节组成的大数组：其中每一个字节拥有一个地址（物理地址），CPU 可以在这个数组中存取数据。

内存访问速度太慢，引入缓存（cache）。 CPU 缓存是由若干个缓存行（cache line）组成的。每个缓存行包括：
一个有效位，用户表示其是否有效；
一个标记地址，用于标识其对应的物理地址；
一些其他的状态信息。

内存映射输入输出（MMIO）是一种常见的 CPU 控制和访问设备的方式。MMIO 的原理是：把输入输出设备和物理内存放到同一个地址空间，为设备内部的内存和寄存器也分配对应的地址。

CPU 通过访问 MMIO 配置的地址可以获取输入，但是 CPU 如何才能知道有输入事件发生了？

一种方法是轮询。但是轮询会使 CPU 长时间处于等待输入的状态，造成 CPU 浪费，一种更高效的做法是：让设备在获得输入后主动告知 CPU，然后 CPU 再去获取输入。

中断，设备通过向 CPU 发出中断来打断 CPU 的执行，使得 CPU 去处理这个中断。操作系统可以为不同的设备中断配置不同的中断函数。

中断机制除了使得设备能够主动通知 CPU 之外，还包括让一个 CPU 核心去通知另一个 CPU 核心等用途。

MMIO 使得 CPU 可以主动访问设备，中断使得设备能够主动通知 CPU。 从应用程序的视角来看，异常和中断的区别是什么？

在发生特权级切换时，如果不保存程序计数器和栈指针，会出现什么问题？

第3章　操作系统结构 链接到标题

策略表示要”做什么，机制表示该“如何做”。

对于操作系统的调度系统而言，策略包括先到先得（FCFS），时间片轮转（RR）等，机制包括调度队列的设计，调度实体（线程）的表示与调度的中断处理等。

模块化划分要充分考虑“高内聚”和“低耦合”。

分层 vs 层级

分层和层级这两个概念有点像，简而言之，分层是指不同类模块之间的层级，而层级则是指同类模块之间的分层。

第4章　内存管理 链接到标题

应用程序能够既高效又安全的功能使用物理内存资源的方案：虚拟内存。

虚拟内存的设计有如下三个方面的目标：

  • 高效性，一方面，虚拟内存抽象不能在应用程序运行过程中造成明显的性能开销；另一方面，虚拟内存抽象不能占用过多的物理内存资源
  • 安全性，虚拟内存抽象需要使不同的应用程序的内存互相隔离，即一个应用程序只能访问属于自己的物理内存区域
  • 透明性，虚拟内存抽象需要考虑对应用程序的透明性，使得应用程序开发者在编程时无需考虑虚拟内存抽象

应用程序使用虚拟地址访问存储在内存中的数据和代码，在程序执行过程中，CPU 会把虚拟地址转换为物理地址，然后通过后者访问物理内存，虚拟地址转换成物理地址的过程，通常称为地址翻译。

内存管理单元（MMU），负责虚拟地址到物理地址的转换。程序在 CPU 核心上运行期间，它使用的虚拟地址都会由 MMU 进行翻译，当需要访问物理内存设备的时候，MMU 翻译出的物理地址将会通过总线传到相应的物理内存设备，从而完成相应的物理内存读写请求。为了加速地址翻译的过程，现代 CPU 引入了转址旁路缓存（TLB），TLB 是 MMU 内部的单元。

MMU 将虚拟地址翻译为物理地址的主要机制有两种：分段机制和分页机制。

分段：应用程序的虚拟地址空间由若干个不同大小的段组成，比如代码段、数据段等。
分页：将应用程序的虚拟地址空间划分成连续的、等长的物理页（显著区分于分段机制下不同长度的段），同时物理内存也被划分成连续的、等长的物理页。虚拟也和物理页的页长固定且想等，从而使得操作系统能够很方便的为每个应用构造页表，即虚拟页到物理页的映射关系表。

在分页机制下，应用程序虚拟地址空间中的任意虚拟页可以被映射到物理内存中的任意物理页上，因此可以实现物理内存资源的离散分配。分页机制按照固定页大小分配物理内存，可有效避免分段机制中外部碎片的问题。

为什么需要多级页表？
因为如果是单级页表，那么页表所占用的空间很大，为了压缩页表大小，引入了多级结构的页表。多级页表允许在整个页表结构中出现空洞，而单级页表需要每一项都实际存在。

为什么单级页表中每一项都需要存在？
单级页表可以看成以虚拟地址的虚拟页号作为索引的数组，整个数组的起始地址（物理地址）存储在页表基地址寄存器中。翻译某个虚拟地址即根据其虚拟页号找到对应的数组项，因此整个页表必须在物理内存中连续，其中没有被用到的数组项也需要预留（不能出现空洞）。

在 4 级页表结构中允许页表内存在“空洞”，假设整个应用程序的内存地址空间中只有两个虚拟页被使用，分别对应最低和最高的两个虚拟地址。在使用 4 级页表后，整个页表实际上只需要 1 个 0 级页表，2 个 1 级页表，2 个 2 级页表，2 个 3 级页表，合计 7 个页表页，仅仅占用 28KB 的物理内存空间，远小于单级页表。

多级页表会导致地址翻译实践增加，一次地址翻译可能会导致多次物理内存访问。为了减少地址翻译的访存次数，MMU 引入了转址旁路缓存（TLB）部件来加速地址翻译的过程。TLB 缓存了虚拟页号到物理页号的映射关系，若找到则可直接获得对应的物理页号而无须查询页表。

为什么硬件仅仅采用简单的 TLB 管理方式，就能在大多数情况下获得较高的 TLB 命中率？
因为局部性起了重要作用，应用程序在运行过程中访问内存的模式具有时间局部性和空间局部性，TLB 中的一条缓存项对应着一个内存页，由于内存访问的时空局部性，TLB 缓存项在将来很可能被多次查询。

如何保证 TLB 中的内容与当前页表内容的一致性？
由于TLB 是使用虚拟地址进行查询的，所以操作系统在进行页表切换（应用程序切换）的时候，需要主动刷新 TLB。若操作系统在切换应用的过程中刷新 TLB，那么应用程序开始执行（被切换到）的时候总会发生 TLB 未命中的情况，进而不可避免的造成性能损失。那么是否能够避免应用程序切换过程中 TLB 刷新的开销呢？
一种为 TLB 缓存打上“标签”的设计正是为了避免这样的开销。AArch64 体系结构为例，它提供了 ASID 功能（x86 64 上对应的功能为 PCID），具体来说，操作系统可以为不同的应用程序分配不同的 ASID 作为应用程序的标签，再将这个标签写入应用程序的页表基地址寄存器的空闲位，同时 TLB 中的缓存项也会包含 ASID 这个标签，从而使得 TLB 中属于不同应用程序的缓存项可以被区分开。因此，在切换页表的过程中，操作系统不再需要清空 TLB 缓存项。

ASID 最多有 16 位，即同时最多可以有 65536 个标签，操作系统需要合理的为应用程序分配标签。

当一个虚拟页处于未分配状态或者已分配但未映射至物理内存状态的时候，应用程序访问虚拟页都会触发缺页异常，操作系统时如何区分的呢？操作系统时如何记录虚拟页分配状态的呢？
Linux 实现方法：由于应用程序通常使用虚拟地址空间的一些区域（比如数据和代码，栈，堆分别对应于三个互不连续的虚拟内存区域），所以在 linux 中，应用程序的虚拟地址空间被实现成由多个虚拟内存区域（VMA）组成的数据结构，每个 VMA 中包含该区域的起始虚拟地址，结束虚拟地址，访问权限等信息，当发生缺页异常时，操作系统判断该虚拟页是否属于该应用程序的某 VMA 来区分该页所处的分配状态。 页替换策略：

  • MIN/OPT 策略
  • FIFO 策略
  • Second Chance 策略
  • LRU 策略
  • MRU 策略
  • 时钟算法策略

虚拟内存的功能

  • 共享内存，允许同一个物理页在不同的应用程序间共享，共享内存到的一个基本用途是可以让不同的应用程序之间互相通信、传递数据。基于共享内存的思想，操作系统又从中衍生出诸如写时拷贝、内存去重等功能
  • 写时拷贝，页表中每个页表项除了记录物理页号，还记录了其他信息（属性位），用于标识虚拟页的权限（该页是否可写，可执行）的权限位，写时拷贝正式利用标识“是否可写”的权限位来实现的。写时拷贝允许应用 A 和应用 B 以只读的方式共享同一段物理内存，一单某个应用对该内存区域进行修改，就会触发缺页异常（这是由于违反权限导致的，不同于之前所说的换页机制下的未映射导致的）。在触发了缺页异常后，CPU 同样会将控制流传递给操作系统预先设置的缺页异常处理函数，在该函数中，操作系统会发现当前的缺页异常是由于应用程序写了只读内存，而且相应的内存区域又是被操作系统标记成写时拷贝的，于是操作系统会在物理内存中将缺页异常对应的物理页重新拷贝一份，并且将新拷贝的物理页以可读可写的方式重新映射给触发异常的应用程序，此后再恢复应用程序的执行。
  • 内存去重，操作系统定期扫描具有相同内容的物理页，并找到映射到这些物理页的虚拟页，然后只保留其中一个物理页，将具有相同内容的其他虚拟页都用写时拷贝的方式映射到这个物理页，释放其他的物理页。Linux 中的 KSM 实现该功能。但是该功能会对性能产生影响。
  • 内存压缩，当内存资源不足时，操作系统选择一些“最近不太会使用”的内存页，压缩其中的数据，从而释放更多空闲内存。如 Linux zswap。

第5章　进程与线程 链接到标题

进程的状态

  • 新生状态（new）：该状态表示一个进程刚刚被创建出来，还未完成初始化，不能被调度执行。在经过初始化过程之后，进程迁移至预备状态
  • 预备状态（ready）：该状态表示进程可以被调度执行，但还未被调度器选择。由于 CPU 数量可能少于进程数量，在某一时刻只有部分进程能被调度到 CPU 上执行。此时，系统中其他的可被调度的进程都处于预备状态。在被调度器选择执行后，进程迁移至运行状态
  • 运行状态（running）：该状态表示进程正在 CPU 上运行。当一个进程执行一段时间后，调度器可以选择中断它的执行并重新将其放回调度队列，它就迁移至预备状态。当进程运行结束，它会迁移至终止状态。如果一个进程需要等待某些外部事件，它可以放弃 CPU 并迁移至阻塞状态
  • 阻塞状态（blocked）：该状态表示进程需要等待外部事件（如某个 I/O 请求的完成），暂时无法被调度。当进程等待的外部事件完成后，它会迁移至预备状态
  • 终止状态（terminated）：该状态表示进程已经完成了执行，且不会再被调度

进程的（虚拟内存）空间布局

  • 用户栈：栈保存了进程需要使用的各种临时数据（如临时变量的值）。栈是一种可以伸缩的数据结构，其扩展方向是自顶向下，栈底在高地址上，栈顶在低地址上。当临时数据被压入栈内时，栈顶会像低地址扩展。
  • 代码库：进程的执行有时需要依赖共享的代码库（比如 libc），这些代码库会被映射到用户栈下方的虚拟地址处，并标记为只读。
  • 用户堆：堆管理的是进程动态分配的内存。与栈相反，堆的扩展方向是自底向上，堆顶在高地址上，当进程需要更多内存时，堆顶会向高地址扩展。
  • 数据与代码段：处于较低地址的是数据段与代码段，它们原本都保存在进程需要执行的二进制文件中，在进程执行前，操作系统会将它们载入虚拟地址空间。其中，数据段保存的是全局变量的值，代码段保存的是进程执行所需的代码。
  • 内核部分：处于进程地址空间最顶端的是内核内存。每个进程的虚拟地址空间里都映射了相同的内核内存。当进程在用户态运行时，内核内存对其不可见；只有当进程进入内核态时，才能访问内核内存。与用户态相似，内核部分也有内核需要的代码和数据段，当进程由于中断或系统调用进入内核后，会使用内核的栈。

每个进程都通过一个数据结构来保存它的相关状态，如进程标识符（PID）、进程状态、虚拟内存状态、打开的文件等。这个数据结构成为进程控制块（PCB）。在进行上下文切换时，会将前一个进程的寄存器状态保存到 PCB 中，然后将下一个进程先前保存的状态写入寄存器，从而切换到该进程执行。

进程的创建：fork，进程的执行：exec。

进程间监控：wait，wait 可以用来等待子进程，来回收已经运行结束的子进程和释放资源。如果父进程没有调用 wait 操作，或者还没来得及调用 wait 操作，就算子进程已经终止了，它所占用的资源也不会完全释放，这种进程成为“僵尸进程”。内核会为僵尸进程保留其进程描述符 PID 和终止时的信息，以便父进程在调用 wait 时可以监控子进程的状态。由于管理 PID 也需要一定的内存开销，内核会设定最大可用 PID 的限制，如果一个进程创建了大量子进程却不调用 wait，那么僵尸进程会迅速占据可用 PID，使得后续的 fork 因为内核资源不足而失败。不过如果父进程退出了，那么子进程的信息就不再会被父进程使用，也就没有必要继续保留它们了。这时，所有父进程创建的僵尸进程都会被内核的第一个进程 init 通过 wait 的方式回收。

进程组是进程的集合，进程组的一大作用体现在对信号的处理，应用程序可以调用 killpg 向一个进程组发送信号，这个信号会被发送给这个进程组的每个进程。

会话是进程组的集合，可以由一个或多个进程组构成。会话将进程组根据执行状态分为前台进程组和后台进程组，控制终端进程是会话与外界进行交互的“窗口”，它负责接收从用户发来的输入。

fork 的优点：
简洁，fork 和 exec 的组合可以认为是将进程的创建过程进一步的解耦：fork 为进程搭建了“骨架”，而 exec 则为进程添加了“血肉”，两者的分工非常清晰，由于 fork 和 exec 的解耦，程序可以在 fork 调用后，exec 调用前，对子进程进行各种设定，比如对文件进行重定向。另外，fork 还强调了进程与进程之间的联系，由于 fork 具有创建原有进程的拷贝的语义，原进程与 fork 创建的进程之间存在较强的联系（父进程与子进程），这种联系为进程的管理提供了便利，比如在 Shell 中，虽然同一个 shell 创建的进程的功能不同，但是它们都来自同一个用户，因此可以共享很多状态。又如，web 服务场景中，服务器为每个请求单独创建一个进程，由于这些进程的逻辑相似，因此可以通过 fork 一次创建多个进程来应对用户的请求。

fork 的局限性：

  • fork 过于复杂，由于 fork 到的默认语义是构造与父进程一样的拷贝，因此它会使得子进程与父进程共享大量状态，可能会使进程表现出看似违反直觉的行为。每当操作系统为进程的结构添加功能时，就必须考虑到对 fork 的实现和修改，fork 在实现过程中需要考虑的特殊情况越来越多，代码越来越复杂。另外由于 fork 的实现与进程、内存管理等模块的耦合程度越高，因此不利于内核的代码维护。
  • fork 的性能太差，由于 fork需要创建出原进程的一份拷贝，原进程的状态越多，fork 的性能就越差。尽管写时拷贝已经大大减少了内存拷贝，但对于这类应用来说，就连建立内存映射都需要耗费大量时间，fork 的效率已经满足不了它们的需要。
  • fork 存在潜在的安全漏洞，fork 建立的父进程与子进程之间的联系可能会成为攻击者的重要切入点。

除了以上三点，还有扩展性差、与异质硬件不兼容、线程不安全等。

Linux 针对 fork 提出了多种替代方案：

  • posix_spawn：灵活度不如fork & exec，但是性能要好于 fork&exec
  • vfork：vfork 是 fork 的裁剪版，从父进程中创建出子进程，但是不会为子进程单独创建地址空间，只适合用在进程创建后立即使用 exec 的场景，vfork & exec 相比 fork&exec 省去了一次地址空间的拷贝。
  • rfork/clone：fork 的精密控制版本，允许应用程序通过参数对创建过程进行更多的控制

进程抽象过于笨重：

  1. 创建进程的开销较大，需要完成创建独立的地址空间、载入数据和代码段、初始化堆等步骤，即使使用 fork 接口创建进程，也需要对父进程的状态进行大量拷贝
  2. 由于进程拥有独立的虚拟地址空间，在进程间进行数据共享和同步比较麻烦，一般只能基于共享虚拟内存页（粒度较粗）或者基于进程间通信（开销较高）。

因此提出在进程内部添加可独立执行的单元，它们共享进程的地址空间，但又各自保存运行时所需的状态（上下文），这就是线程。线程取代进程成为操作系统调度和管理程序的最小单位。

多线程的地址空间主要有两个重要特征：

  • 分离的内核栈和用户栈：由于每个线程的执行相对独立，进程为每个线程都准备了不同的栈，供它们存放临时数据。在内核中，每个线程也有对应的内核栈，当线程切换到内核中执行时，它的栈指针会切换到对应的内核栈
  • 共享的其他区域：进程除栈以外的其他区域由该进程的所有线程共享，包括堆、数据段、代码段等。当一个进程的多个线程需要动态分配更多的内存时（在 C 语言中可通过调用 malloc 函数实现），它们的内存分配操作都是在同一个堆上完成的。因此 malloc 的实现需要使用“同步原语”，使每个线程能正确的获取可用的内存空间

线程分为：用户态线程和内核态线程。有三种多线程模型：

  • 多对一模型
  • 一对一模型（Linux & Windows 默认）
  • 多对多模型（macOS 和 iOS）

与进程类似，线程也有自己的线程控制块（TCB），用于保存与自身相关的信息。在目前主流的一对一线程模型中，内核态线程和用户态线程都会各自保存自己的 TCB。内核态 TCB 结构与 PCB 相似，会存储现成的运行状态、内存映射、标识符等信息。用户态 TCB 的结构则主要由线程库决定，对于 Linux 平台上使用 pthread 线程库的应用来说，pthread 结构体就是用户态的 TCB。用户态的 TCB 可以认为是内核态的扩展，可以用来存储更多与用户态相关的信息，其中一项重要的功能就是线程本地存储（TLS）。

sleep vs yield ：

sleep 操作与 yield 有相似之处，他们都会让当前线程放弃 CPU 资源，交给其他线程执行。它们最重要的区别是调用后线程的状态。当线程调用 yield 后，它会处于预备状态，并可能很快就会被调度；在某些极端情况下，如果没有其他可调度线程，该线程甚至会继续执行。而当调用 sleep 之后，它会进入阻塞状态，只有满足条件后才会重新恢复到预备状态。可以把 yield 看做类似于 sleep（0），即挂起时间无限趋近于 0 的调用。

线程的上下文是上下文切换的基础，在实际硬件中，上下文主要指的是当前处理器中大部分寄存器的值，这其中包括：

  • 程序计数器（PC）存储 CPU 当前所执行指令的地址；
  • 通用寄存器，存储 CPU 当前正在处理的一些数据；
  • 特殊寄存器，存储 CPU 当前的一些硬件状态和配置，如页表地址等。

第6章　操作系统调度 链接到标题

一般来说，一个系统会同时处理多个请求，但是其资源是优先的，调度就是用来协调每个请求对资源的使用的方法。调度中存在：优先级，时间片，截止时间等概念。

任务调度（task scheduling 也称 CPU 调度）负责调度可执行的任务对 CPU 的使用；I/O 调度负责对应该以何种顺序想存储设备发起 I/O 请求进行调度；内存管理也是一种调度，内存管理将虚拟内存映射到物理内存，物理内存是有限的资源，当需要使用的虚拟内存超过物理内存容量时，换页机制就是在对哪部分物理内页的内容可以留在内存中进行调度，并将剩余物理页上到的内容写回磁盘，进而复用那些剩余的物理页。

一般调度器会通过维护运行队列（run queue）的方式来管理任务，Linux 调度器会用红黑树来实现运行队列，任务在执行时若触发一定条件，则会停止执行，这些条件可以是：

  • 该任务执行了指定的时间片后，应让其他任务在当前 CPU 核心上执行
  • 该任务发起了 I/O 请求，在 I/O 返回前，它不会继续执行
  • 该任务主动停止执行或进入睡眠
  • 该任务被系统中断打断，系统优先处理中断而暂缓该任务的执行

调度器主要作用是做出调度决策，整个系统通过该决策进而决定如何调度，这些调度决策包括：

  • 从运行队列中选择下一个运行任务
  • 决定执行该任务的 CPU 核心
  • 决定该任务被允许执行的时间，即时间片

调度器的设计问题主要可以归纳为两类：

  • 调度器应该做出什么样的调度决策（what）？
  • 调度器应该如何做出符合预期的调度决策（how）？

常用的调度指标包括：

  • 性能
    • 吞吐量、周转时间、响应时间、调度开销
  • 非性能
    • 公平性、资源利用率
  • 特殊
    • 实时性、能耗

调度器面临的挑战：

  • 调度指标多样性
  • 调度可参考的信息有限
  • 任务间的复杂交互
  • 许多方便存在权衡

调度器权衡包括但不限于一下几点：

  • 调度开销与调度效果
  • 优先级与公平性
  • 性能与能耗

在任务调度中，长期、中期和短期调度相互协作，分别以不同的目标对进程进行调度。
长期任务的触发间隔较长，它粗粒度的决定是否应该将一个新的进程纳入调度管理，负责增加系统中可被调度的进程的数量；
中期调度的触发相对频繁，它辅助换页机制，负责限制系统中可被调度的进程的数量；
短期调度的触发最为频发，它负责细粒度的调度进程的执行，做出相应的调度决策。

调度流程：

  1. 在传统操作系统中，批处理任务被发起后，其信息会被存入磁盘中的批处理队列，等待被长期调度允许进入系统；
  2. 长期调度负责从批处理队列中选取下一个可被调度的批处理任务，为其创建对应的进程，将进程设为预备状态并放入运行队列；
  3. 由于交互任务和实时任务一般都有比较高的时延要求，需要在一定时间内返回结果。所以这两类任务一般不会被长期调度管理。系统会直接为他们创建对应的进程，将进程设为预备状态并放入运行队列；
  4. 通过短期调度的决策，运行队列中的进程会被调度到 CPU 上执行，此时进程为运行状态；
  5. 当进程运行完一个时间片后，短期调度会将其重新置为预备状态，并放回运行队列；
  6. 当运行中的进程发起 I/O 请求，等待用户输入或进入睡眠，因而需要被阻塞时，会被放入阻塞队列，短期调度会选择其他进程进行调度；
  7. 当进程等待的事件被触发后，操作系统直接将对应的进程移出阻塞队列，并将其置为预备状态，重新放入运行队列；
  8. 如果系统中的内存使用量偏大，就会触发换页机制，中期调度会挂起处于预备状态、阻塞状态的进程，将其置为挂起预备状态/挂起阻塞状态并放入挂起运行队列/挂起阻塞队列中；
  9. 处于挂起阻塞状态的进程，如果其等待的时间被处罚，会被置为挂起预备状态并被放入挂起运行队列中；
  10. 当系统的内存使用不再紧张时，中期调度会激活挂起运行队列/挂起阻塞队列中的进程，将其置为预备状态/阻塞状态并放回运行队列/阻塞队列中；
  11. 当进程结束后，会进入终止状态并最终被回收

单核调度策略 链接到标题

经典调度 链接到标题

先到先得（FCFS），
弊端：

  • 在长短任务混合的场景下对短任务不友好
  • 对 I/O 密集型任务不友好

最短任务优先（SJF）

弊端：

  • 必须预知任务的运行时间
  • 其表现严重依赖与任务到达时间点

弊端：

  • 必须预知任务的运行时间
  • 长任务饥饿

时间片轮转（RR）

对于 RR 策略，一个关键点是它的时间片该如何选取。

弊端：

  • 在任务运行时间相似的场景下平均周转时间高，RR 一定程度上保证了每个任务之间的公平性，同时也可获得良好的响应时间，但是在特定场景下，任务的平均周转时间可能较差。

优先级调度 链接到标题

多级队列（MLQ），每个任务会被分配预先设置好的优先级，每个优先级对应一个队列，任务会被存储在对应的优先级队列中。如果优先级不同的任务同时处于预备状态，那么调度器应该倾向于调度优先级较高的任务，因此一个任务必须等到所有优先级比它高的任务调度完成才可以被调度。处于相同优先级队列的任务，它们内部的调度方式没有统一标准，可以针对性的为不同队列采用不同的调度策略，如 FCFS 或 RR。

在设置 MLQ 策略的任务优先级时，需要注意将 I/O 密集型任务的优先级提高，保证 I/O 资源利用率。

弊端：

  • 低优先级任务饥饿，如果调度器需要保证一定的公平性，需要引入额外的机制监控任务等待时间，为等待时间过长（如超过一定的阈值）的任务提升优先级
  • 优先级反转，在程序执行时，多个任务可能会对同一份数据产生竞争，因此任务会使用锁来保护共享数据。假设存在 3 个任务A，B，C，他们的优先级是 ABC，任务 C 在运行时持有一把锁，然后被高优先级的 A 抢占了，A 也想申请任务 C 持有的锁，但是申请失败，因此进入阻塞状态等待 C 释放锁，此时 BC 都处于可以运行状态，B 优先级高，因此 B 先运行，观察该情况，会发现 B 的优先级好像高于 A，这一问题称为优先级反转。一个可行的解决方案是优先级继承。

多级反馈队列（MLFQ），在 MLQ 基础上，增加了动态设置任务优先级的策略，MLFQ 策略也会维护多个优先级队列，处于相同优先级的任务则采用 RR 策略执行，优先级的动态设置策略如下：

  • 短任务拥有更高的优先级，好处：1. 可以有更好的平均周转时间；2. I/O 密集型任务一般在 CPU 中执行的时间很短，给短任务提高优先级也相当于提高 I/O 密集型任务的优先级，提高系统的 I/O 资源利用率；3. 交互式任务一般是短任务，降低响应时间。根据每个任务（多次）执行时间来判断是短任务还是长任务。当任务进入系统中，假设任务是短任务，MLFQ 会为每个任务队列设置任务的最大运行时间，如果超过了最大时间，就会将该任务的优先级减一。
  • 低优先级的任务采用更长的时间片，为了减少任务的调度次数，优先级月底的任务，其时间片越长，由于 MLFQ 策略支持抢占式调度，无须担心低优先级的任务阻塞新进入系统的任务。
  • 定时将所有任务的优先级提升至最高，避免出现低优先级任务饥饿。

公平共享调度

  • “公平”是指任务对资源的使用符合用户预期

公平共享调度会量化任务对系统资源的占有比例，从而实现对资源的公平调度。用份额（share）来量化每个任务对 CPU 时间的使用。份额支持曾计划的分配方式，可以将任务分组，以组为单位分配份额，任务组会在组内进一步分摊该组所拥有的份额。

优先级和份额都表示了任务在系统中的重要程度，但是目的是不同的。优先级调度是为了优化任务的周转时间、响应时间和资源利用率而设计的。不同任务的优先级只能用于相互比较，表明任务执行的先后。而基于份额的公平共享调度是为了让每个任务都能使用它应该获得的系统资源。分隔的值明确对应了任务应使用的系统资源比例。

彩票调度，彩票转让，彩票货币，彩票通胀。
弊端：

  • 随机数所带来的问题，彩票调度通过使用随机的方式实现了一个简单并且近似于公平共享的调度器，然而，随机数会导致某一任务占用 CPU 时间的比例，需要在该任务经历多次调度后，才能趋近于该任务的份额在所有任务总份额的比例。只有调度次数足够多，彩票调度效果才接近公平。 步幅调度，采用确定性的方式调度任务，核心概念是步幅。引入虚拟时间的概念。为了让虚拟时间短的任务能够“追赶”虚拟时间长的任务，使用虚拟时间的调度策略一般会选择调度所有任务中虚拟时间最少的任务。步幅调度通过设置虚拟时间的方式，让任务在每次调度时增加一定的虚拟时间，即步幅。经历虚拟时间相同的任务，它们使用的 CPU 时间之比就是步幅的倒数之比，换句话说，任务的份额之比正对应了任务的步幅的倒数之比。在真实的系统中，由于任务可能在任意时间进入系统，因此任务经历的虚拟时间不能为 0，而应该设置为当前所有任务的最小虚拟时间值，放置新进入的任务长时间占有 CPU。

实时调度

根据任务超过截止时间所造成的后果分类：

  • 硬实时任务，该类任务必须在截止时间前完成
  • 软实时任务，该类任务可以偶尔超过截止时间完成

根据被触发的时间分类：

  • 周期任务，指到达系统时间遵循一定周期的任务
  • 偶发任务，指不会周期性的到达系统的任务，且还要满足连续两个相同偶发任务到达系统的时间间隔有最小值，即系统不会在同一时刻处理两个相同的偶发任务。偶发任务通常是硬实时任务。
  • 非周期性任务，指到达系统时间随机的任务，通常是软实时任务。

多核调度策略 链接到标题

在多核上进行调度时，需要回答以下三个问题：

  • 当前应该调度哪个/哪些任务？
  • 每个调度的任务应该在哪个 CPU 核心上执行？
  • 每个调度的任务应该执行多久？

负载分担

设想多核共享一个全局运行队列，当一个 CPU 核心需要调度任务时，根据给定的调度策略，决定全局运行队列中下一个由它执行的任务。给定的调度策略可以是任一一种单核调度策略，这种方法称为负载分担，因为系统的负载是被所有的 CPU 核心分担的。

优点：

  • 设计实现简单，通过使用负载分担，可以将多核调度问题规约为单核调度问题，使用已有的单核调度策略和单核调度器，就可以实现一个多核的全局调度器
  • 每个 CPU 核心都会分担系统的负载，不会出现 CPU 资源浪费的情况，一个 CPU 核心执行完当前任务后，它会从全局任务队列中再选取一个任务执行，只要当前系统还有可以执行的任务，每个 CPU 核心都能获取到任务执行

问题：

  • 多核共享一个全局运行队列的同步开销
  • 任务在多个 CPU 核心间来回切换的开销，包括重新载入缓存，TLB 刷新等

协同调度

为了满足对蚁族任务进行调度的需求，协同调度的概念应运而生。协同调度的目的是尽可能让一组任务并行执行，避免调度器同时调度有依赖关系的两组任务，同时避免关联任务执行效率降低的问题。

协同调度的经典策略是群组调度。

两级调度

为了减少任务在不同 CPU 核心上切换执行的开销，每个任务应尽可能只在一个 CPU 核心上进行调度。因此，新的调度策略改为每个 CPU 核心都引入一个本地调度器，并用它管理对应核心上执行的任务。这种调度策略使用全局调度器和本地调度器，构成了层级化结构，一般称为两级调度。

当一个任务进入系统时，全局调度器根据系统的当前信息，诸如每个 CPU 核心的负载情况，决定该任务应该被哪个 CPU 核心执行，当一个任务被分配给定的核心时，它将一直被该核心的本地调度器管理，不会迁移到其他 CPU 核心上执行。同时，每个本地调度器可以使用任意单核调度策略来调度任务。在避免线程在 CPU 核心间来回切换，提高了缓存局部性，较少了数据竞争的冲突的同时，这种曾计划的设计将设计单核调度策略与支持多核调度进行了解耦，使得调度器的设计实现更加灵活。以 Linux 为代表的一系列操作系统会为每个 CPU 核心分配一个本地运行队列，即可理解为每个 CPU 核心有一个本地调度器。

负载追踪与负载均衡

两级调度策略避免了任务在多核间切换，但是由于在任务开始时就指定了它在哪个 CPU 上运行，且没有任务在 CPU 核心间切换的机制，可能会导致多核间的负载不均衡，为了解决这个问题，引入了负载均衡的策略，负载均衡的思想是：通过追踪每个 CPU 核心当前的负载情况，将处于高负载的 CPU 核心管理的任务迁移至低负载的 CPU 核心上，尽可能的保证每个核心的负载大致相同。

负载均衡面临的挑战是：如何确定当前任务的负载情况，一个任务的执行负载是动态变化的，因此系统必须动态追踪当前的负载情况，这会造成一定的性能开销，如何保持低开销的同时对负载进行精确追踪是调度器设计实现的一大挑战，Linux 目前使用的是调度实体粒度负载追踪（PELT）。

运行队列粒度的负载追踪，在 Linux 3.8 以前，内核以每个 CPU 核心的运行队列为粒度计算负载，认为运行队列长的负载就高，导致负载追踪不够精确。

调度实体粒度的负载追踪，在 Linux 3.8 以后，Linux 使用了以调度实体（单个任务）为粒度的负载计算方式，做到了更细粒度的负载追踪。PELT通过记录每个任务的历史执行状况来表示任务的当前负载。具体的，调度器会以 1024 微妙作为一个周期，记录任务处于可运行状态（包括正在运行的以及等待被运行的）的时间，记为 x 微妙。该任务在第 i 个周期内对当前 CPU 的利用率为 x/1024，而对应的负载 Li 为 scale_cpu_capacity * x/1024 ，其中 scale_cpu_capacity 是 CPU 容量，可以理解为对应 CPU 核心的处理能力。在手机到任务每个周期内的负载后，PELT 需要计算一段时间内任务所有周期的累计负载，随着距离当前时间越远，数据参考意义越小，采用衰减系数 y 来计算： L = L0 + L0 * y + L1 * y^2 + L2 * y ^3…. 通过计算每个任务的负载 L，PELT 就可以进而统计出每个运行队列的负载，便于调度器做出有效的迁移决策。

随着 CPU 核心数量越来越多，系统架构越来越复杂，负载均衡策略应该让任务尽量在迁移开销较小的 CPU核心间迁移，以 NUMA 架构为例，当任务从一个 NUMA 节点迁移到另一个 NUMA 节点，会严重影响任务的执行效率，又以超线程为例，一个物理核会被逻辑上分为两个逻辑核，任务在同属于一个五里河的两个逻辑核间切换的开销，会比在不同五里河的两个逻辑核间的开销小很多。

Linux 为了解决上述问题，采用层级化的方法，引入两个数据结构：调度与是有用相同特性的 CPU 核心的集合，这些核心间可以进行负载均衡。一个调度与保存一个或多个调度组，调度组是一个调度与内进行负载均衡的整体单位。通过自下而上的方式层级式的进行负载均衡，并且为了设计简单，只允许触发负载均衡的 CPU 核心拉取其他 CPU 核心的任务到本地。如果当前 CPU 核心触发负载均衡逻辑，首先在最底层调度域内的调度组间进行均衡，然后依次进入更高一级的调度域，并对其管理的调度组进行负载均衡。由于越高层级的调度域间进行负载均衡的开销越大，所以 Linux 为不同层级的调度域设置了不同的负载均衡触发频率与阈值。

对于非实时任务，Linux 使用 CFS 调度器进行调度，CFS 采用了累死公平共享调度的策略，因此其主要关心每个任务占用 CPU 时间的份额。sched_nice 为[-20,19] 的 Niceness ，越不友善的任务越倾向于使用更多的资源或抢占其他友善的任务。

Linux 调度器设计

O(n) 调度器

在 Linux 2.4 版本以前，Linux 调度器是一个机遇 RR 策略的运行队列，没有考虑很多因素（诸如任务的实时性要求）。从 Linux 2.4 版本开始，采用 O(n) 调度器，O(n) 调度器指定调度决策的时间复杂度是 O(n) ，n 代表的是调度器运行队列中的任务数量。

O(n) 调度器采用了负载分担的思想，所有任务被存储于一个全局运行队列中，被选择调度的任务会从运行队列中移除，当该任务执行完并且需要再次被调度时，会被重新放入运行队列的队尾。当调度器选择下一个被调度的任务时，需要遍历运行队列中的所有任务，并重新计算他们的动态优先级，然后选取动态优先级最高的任务。

存在问题：

  • 调度开销过大
  • 多核扩展性差

O(1) 调度器

由于O(n) 调度器存在上述问题，Linux 在 2.6.0 版本使用心得 O(1) 调度器替换 O(n) 调度器。 O(1) 调度器采用了两级调度的思想，每个 CPU 核心单独维护一个本地运行队列，让任务仅在同一个核心上调度。每个本地运行队列实际上是由两个多级队列：激活队列和过期队列组成的，分别用于管理仍有时间片剩余的任务和时间片耗尽的任务。当一个任务的时间片耗尽后，它会被加入到过期队列中。如果当前激活队列中没没有可调度的任务， O(1) 调度器会将两个队列的角色互换，开始新一轮调度。 每个多级队列都有 140 个优先级，其中高优先级 [0,100) 对应于实时任务，剩下的优先级 [100, 140) 对应于不同 Niceness 的非实时任务。每个多级队列都维护了一个位图，位图中的比特位用于判断对应的优先级队列是否有任务等待调度，在制定调度决策时， O(1) 调度器会根据位图找到激活队列中第一个不为空的队列，并调度该队列的第一个任务，其时间复杂度是 O(1) ，与运行队列中的任务数量无关。

用户可能不希望交互式任务在时间片用完后就需要等待所有其他任务的时间片用完才能再次执行，因此该类任务在时间片用完后，仍然会被加入激活队列中。同时，为了防止交互式任务过于激进而导致当前过期队列中的任务无法执行，当过期队列中的任务等待过长时间后， O(1) 调度器会把交互式任务加入过期多列中。

存在问题：

  • 交互式任务的判定算法过于复杂
  • 静态时间片带来的问题， O(1) 调度器的非实时任务的运行时间片是根据其 Niceness 静态确定的，问题是，随着系统中任务数量的上升，任务的调度时延也会上升，对应的，响应时间也会受到影响。

完全公平调度器

为了解决 O(1)调度器的问题，Linux 从 2.6.23 版本开始使用完全公平调度器。公平共享调度策略保证每个任务可以根据自己所占的份额共享 CPU 时间，这是 CFS 调度器的基本思想，O(1)调度器需要繁琐的通过启发式方法确定交互式任务，再给与交互式任务更多的执行机会。而 CFS 调度器只关心非实时任务对 CPU 时间的公平共享，避免了复杂的调度算法实现与调参。同时通过动态的设定任务时间片，确保了任务的调度时延不会过高。

CFS 调度器所使用的调度策略类似于步幅调度，vruntime 代表人物经过的虚拟时间，在调度是 CFS 会调度 vruntime 值最低的任务，Linux 静态的设置了 Niceness 与任务权重的对应关系，Niceness 越低则任务的权重越高，可被分配的 CPU 时间越多。

CFS 调度器的动态时间片，为了避免静态设置任务时间片所带来的问题，CFS 调度使用了调度周期的概念，并保证每经过一个调度周期，运行队列中所有任务都会被调度一次。因而在最坏的情况下，任务的调度时延即为一个调度周期。同时间片一样，调度周期会带来权衡问题。如果调度周期过长，则一系列任务必须在很长时间的运行后才能体现公平性，且任务的调度时延可能过长；如果调度周期过短，则调度开销会变大。

确定了 CFS 的调度周期后，调度器就可以开始计算在当前运行队列中，第 i 个任务的动态时间片 time_slice_i = sched_period * weight_i / weight_rq ，其中 weight_i 是第 i 个任务的权重，weight_rq 代表当前运行队列中的任务权重之和。

由于每个任务的动态时间片是不同的，都根据任务权重进行了缩放，所以任务每次执行后对 vruntime 的更新也要进行对应的缩放： vruntime_i = vruntime_i + weight_nice0 / weight_i * real_runtime ，其中 weight_nice0 表示一个 Niceness 为 0 的任务的权重，该权重与 weight_i 的比值是一个系数，用于将任务的实际运行时间映射为虚拟时间。通过该系数，CFS 保证了不同动态时间片的任务执行完自己的时间片后，他们虚拟时间的增幅是一致的。

第7章　进程间通信 链接到标题

共享内存 vs 基于共享内存的消息传递：基于共享内存的消息传递以共享内存为媒介进行消息的传输，其核心的通信抽象仍然是消息。共享内存的另一种使用方法是，直接在两个（多个）进程间建立共享区域，然后再共享区域上建立数据结构。进程可以直接使用该共享区域上的数据，而不存在”消息“的抽象。

宏内核下的典型的进程间通信机制：管道，消息队列，信号量，共享内存，信号，套接字。

第8章　同步原语 链接到标题

实际应用程序中有很多需要同步的场景，为了正确，搞笑的解决这些同步问题，抽象出了一系列同步原语。

互斥锁 链接到标题

当程序的正确性依赖于特定执行顺序的情况时，被称为竞争冒险。避免竞争冒险最直接的办法就是：确保同一时刻只有生产者中的一个能够对共享缓冲区进行操作。任意时刻只允许至多一个线程访问的方式被称为互斥访问，而保证互斥访问共享资源的代码区域被称为临界区。

需要满足以下条件：

  • 互斥访问：在同一时刻，最多只能有一个线程可以执行临界区
  • 有限等待：当一个线程申请进入临界区后，必须在有限的时间内获得许可并进入临界区，不能无限等待
  • 空闲让进：当没有线程在执行临界区代码时，必须在申请进入临界区的线程中选择一个线程，允许其执行临界区代码，保证程序执行的进展。

硬件实现：关闭中断。

关闭中断可以防止执行临界区的线程被抢占，避免多个线程同时执行临界区，保证了互斥访问。而有限等待依赖于内核的调度器，如果能保证有限时间内调度到该线程，则该线程可以再有限时间内进入临界区，达成有限等待的要求。最后，每个线程离开临界区时都开启了中断，允许调度器调度其他线程执行，达成了空闲让进的要求。但是多核环境中，即使关闭了所有核心的中断，也不能阻塞其他核心上正在运行的线程继续执行。

软件实现：皮特森算法https://zh.wikipedia.org/wiki/Peterson%E7%AE%97%E6%B3%95。

软硬件协同：使用原子操作实现互斥锁。原子操作指的是不可被打断的一个或一系列操作。即要么这一系列指令都执行完成，要么都没有执行，最常见的是比较与置换 （CAS）拿取并累加（FAA）。

互斥锁的实现种类多，不同的互斥锁被用于不同的场景，比如利用原子 CAS 实现的自旋锁，利用原子 FAA 实现的排号自旋锁。

自旋锁：利用一个变量 lock 表示锁的状态，lock 为 1 表示已经有人拿锁，为 0 表示空闲。在加锁时，线程会通过 CAS 判断 lock 是否为空闲，如果空闲则上锁，否则将一遍一遍重试。放锁时，直接将 lock 设置为 0 表示其空闲。自旋锁不能保证有限等待，即不具有公平性。自旋锁并非按照申请的顺序决定下一个获取锁的竞争者，而是让所有的竞争者均同时尝试完成原子操作。

排号自旋锁：排号自旋锁按照锁竞争者申请锁的顺序传递锁，锁的竞争者组成了一个 FIFO 的等待队列。排号锁的结构体有两个成员，owner 表示当前锁持有者序号，next 表示下一个需要分发的序号。获取排号所需要先通过原子的 FAA 操作拿到最新的序号并同时增加锁的分发序号，来避免其他竞争者拿到相同的序号。拿到序号后，竞争者通过判断 owner 的值，等待排到自己的序号，一旦两者想等，竞争者拥有该锁并被允许进入临界区。释放锁时，持有者更新 owner 的值将锁传递给下一个竞争者，保证了公平性。

条件变量 链接到标题

使用条件变量提供的借口，一个线程可以停止使用 CPU 并将自己挂起，当等待的条件满足时，其他的线程会唤醒该挂起的线程让其继续执行，使用条件变量能够有效的避免无谓的循环等待。

互斥锁 vs 条件变量：

互斥锁与条件变量解决的不是同一个问题，互斥锁用于解决临界区的问题，保证互斥访问共享资源。而条件变量通过提供挂起/唤醒机制来避免循环等待，节省 CPU 资源。条件变量需要和互斥锁搭配使用。

信号量 链接到标题

信号量在不同的线程之间充当信号灯，根据剩余资源数量控制不同线程的执行或等待。信号量又被成为 PV 原语，P 为校验，V 为自增。

互斥锁 vs 信号量：
互斥锁与信号量有相似之处。当信号量的初始值为 1，且只允许其值在 0 和 1 之间变化时，wait 和 signal 操作分别于互斥锁的 lock 和 unlock 操作类似，称这种信号量为二院信号量。二元信号量与互斥锁的差别在于：互斥锁有拥有者概念，二元信号量没有。互斥锁往往由同一个线程加锁和放锁，信号量允许不同线程执行 wait 与 signal 操作。互斥锁与计数信号量（非二元信号量）区别较大，计数信号量允许多个线程通过，其数量等于剩余可用资源数量；而互斥锁同一时刻只允许一个线程获取。互斥锁用于保证多个线程对一个共享资源的互斥访问，而信号量用于协调多个线程对一系列共享资源的有序操作。

条件变量 vs 信号量：
信号量是由条件变量、互斥锁以及计数器实现的。而这个计数器就是信号量的核心，用于表示当前可用资源的数量。可以理解为：信号量利用条件变量实现了更高层级的抽象。

同步带来的问题

死锁

死锁产生的必要条件：

  • 互斥访问
  • 持有并等待
  • 资源非抢占
  • 循环等待

优先级反转：由于同步导致线程执行顺序违反预设优先级的问题。

解决方法：

  • 不可抢占临界区协议，核心时避免线程在临界区中被抢占，当线程获取锁，编不允许任何其他线程抢占。
  • 优先级继承协议，在高优先级线程等待锁时，会使锁的持有者继承其优先级，从而避免该锁的临界区被低优先级的任务打断。
  • 优先级置顶协议，将获取锁的线程的优先级置为可能竞争该锁的最高优先级。