操作系统原理 知识总结

---

前言

  关于 操作系统原理 知识体系的总结。

大纲

• 硬件结构
  • 图灵机
  • 冯诺依曼模型
  • 存储器
  • CPU 缓存
  • 软中断
• 内存管理
  • 虚拟内存
  • 内存分段
  • 内存分页
  • 段页式内存管理
  • Linux 内存管理

硬件结构

图灵机

• 有⼀条「纸带」，纸带由⼀个个连续的格子组成，每个格子可以写入字符，纸带就好比内存，而纸带上的格子的字符就好比内存中的数据或程序。
• 有⼀个「读写头」，读写头可以读取纸带上任意格子的字符，也可以把字符写⼊到纸带的格子。
• 读写头上有⼀些部件，比如存储单元、控制单元以及运算单元：
  • 储单元用于存放数据。
  • 控制单元用于识别字符是数据还是指令，以及控制程序的流程等。
  • 运算单元用于执行运算指令。

冯诺依曼模型

  遵循图灵机的设计，提出用电子元件构造计算机，并约定了用⼆进制进行计算和存储，还定义计算机基本结构为 5 个部分，分别是中央处理器（CPU）、内存、输⼊设备、输出设备、总线。

中央处理器

• 32 位和 64 位 CPU 最主要区别在于⼀次能计算多少字节数据。
  • 32 位 CPU ⼀次可以计算 4 个字节。
  • 64 位 CPU ⼀次可以计算 8 个字节。
• 这里的 32 位和 64 位，通常称为 CPU 的位宽。
• CPU 内部还有⼀些组件，常见的有寄存器、控制单元和逻辑运算单元等。
• 控制单元：负责控制 CPU ⼯作。
• 逻辑运算单元：负责计算。
• 寄存器：存储计算时的数据。
  • 通用寄存器，用来存放需要进行运算的数据，⽐如需要进行加和运算的两个数据。
  • 程序计数器，用来存储 CPU 要执行下⼀条指令「所在的内存地址」，注意不是存储了下⼀条要执行的指令，此时指令还在内存中，程序计数器只是存储了下⼀条指令的地址。
  • 指令寄存器，用来存放程序计数器指向的指令，也就是指令本身，指令被执行完成之前，指令都存储在这⾥。

内存

• 数据存储的单位是⼀个⼆进制位（bit），即 0 或 1。
• 最⼩的存储单位是字节（byte），1 字节等于 8 位。
• 内存存储区域是线性的，类似数组，所以内存的读写任何⼀个数据的速度都是⼀样的。

输入输出设备

• 输入设备向计算机输入数据。
• 计算机经过计算后，将数据输出给输出设备。

总线

• 总线用于 CPU 和内存以及其他设备之间的通讯。
  • 地址总线：用于指定 CPU 将要操作的内存地址。
  • 数据总线：用于读写内存的数据。
  • 控制总线：用于发送和接收信号，如中断、设备复位信号等。

存储器

• CPU 寄存器
  • 数量在几十到几百之间
  • 存储一定字节的数据（32 位 4 字节，64 位 8 字节）
  • 一般要求在半个 CPU 时钟周期内完成读写
• CPU Cache（SRAM，静态随机存储器）
  • 通电才能存储数据
  • L1-Cache
    • 每个 CPU 核心都有一个
    • 访问时间通常需要 2~4 个时钟周期
    • 大小在几十 KB 到几百 KB
    • 指令与数据分开存放
  • L2-Cache
    • 每个 CPU 核心都有一个
    • 访问时间通常需要 10~20 个时钟周期
    • 大小在几百 KB 到几 MB
  • L3-Cache
    • 通常是多个 CPU 核心共用
    • 访问时间通常需要 20~60 个时钟周期
    • 大小在几 MB 到几十 MB
• 内存（DRAM，动态随机存储器）
  • 密度更高，功耗更低，容量更大，造价更便宜
  • 访问时间大概在 200~300 个时钟周期之间
  • 定时刷新电容才能存储数据
• SSD/HDD 硬盘
  • 断电后数据依然存在
  • SSD 访问时间是内存的 10~1000 倍
  • HDD 访问时间是内存的 10w 倍左右
• 从上到下访问速度由快到慢，单位存储能耗由高到低、成本价格由高到低。

CPU 缓存

缓存一致性

• 数据不止有读操作还有写操作，如何将 Cache 中的数据同步到内存中呢？
  • 写直达：同时写入 Cache 和内存中
  • 写回：发生写操作时只写入到 Cache Block 中，整块替换时才写入内存
• 缓存一致性问题：多核心的 CPU 拥有自己的 L1/L2 Cache，需要保持一致性
  • 写传播：某个核心更新数据时需要传播给其他核心
  • 事务的串行化：某个核心里对数据的操作顺序，需要在其他核心看来是一样的
• MESI 协议
  • 基于总线嗅探，需监听总线，修改数据需在总线上广播
  • Modified：已修改，可以直接自己改
  • Exclusive：独占，可以直接自己改，变共享的时候需要同步给别人
  • Shared：共享，要改需广播，让别人变成 I，自己变成 M
  • Invalid：已失效，不能改

伪共享问题

• CPU Cache 缓存数据的时候并不是一个一个读取的，而是一次读取一小块，称为 Cache Line。
• 多个线程同时读写同一个 Cache Line 的不同变量，原本没有关联，缺因为处于同一个 Cache 而导致 CPU Cache 失效。这个现象称为伪共享。
• 解决这个问题的思路就是对于多个线程共享的热点数据（经常会修改的数据），应该避免这些数据刚好在同一个 Cache Line 中。
• 在 Linux 内核中，存在着一个宏定义，使得变量在 Cache Line 中对齐。其实就是用空间换时间的思路，浪费一定的 Cache 空间，让变量处于不同的 Cache Line 中。
• 在应用层面中，也有使用「字节填充 + 继承」的方式来避免伪共享问题。

软中断

• 硬中断：打断 CPU 正在执行的任务，处理硬件请求，主要负责耗时短的工作。
• 软中断：由内核触发，完成硬中断未完成的工作，通常是耗时较长的任务，特点是延迟执行，一般是以内核线程的方式执行，例如网络收发、定时事件。另外，一些内核自定义事件也属于软中断，例如内核调度、RCU 锁等等。

内核

• 内核是应用和硬件设备连接的桥梁，应用程序只需关心与内核的交互，不用关心硬件的细节。
• 内核的基本能力
  • 管理进程、线程，决定哪个进程、线程使用 CPU，也就是进程调度的能力。
  • 管理内存，决定内存的分配和回收，也就是内存管理的能力。
  • 管理硬件设备，为进程与硬件设备之间提供通信能力，也就是硬件通信能力。
  • 提供系统调用，如果应用程序需要更高权限运行的服务，那么就需要系统调用，它是用户程序与操作系统之间的接口。
• 操作系统的内存分区
  • 内核空间，这个内存空间只有内核程序可以访问。
  • 用户空间，这个内存空间专门给应用程序使用。
• 宏内核
  • 内核的所有模块，比如进程调度、内存管理、文件系统、设备驱动等，都运行在内核态。
  • 整个内核就是一个完整的可执行程序，且拥有最高的权限。
• 微内核
  • 内核只保留最基本的能力，比如进程调度、虚拟机内存、中断等，把一些应用放到了用户空间，比如驱动程序、文件系统等。
  • 这样服务于服务之间是隔离的，单个服务出现故障或者遭受攻击也不会导致整个操作系统挂掉，提高了操作系统的稳定性和可靠性。
  • 功能少，可移植性高，相比宏内核的缺点在于不在内核中的驱动程序却需要频繁调用底层能力，因此需要频繁地在用户态和内核态之间进行切换，增加了系统开销。
• 混合类型内核
  • 架构比较像微内核，内核里面会有一个最小版本的内核，然后其他模块在这个基础上搭建。
  • 实现的时候与宏内核类似，把整个内核做成一个完整的程序，大部分服务都在内核中，就像一个宏内核包裹着一个微内核。

Linux 内核

• 设计理念
  • MutiTask，多任务
    • 任务可以并发（单核 CPU）或并行（多核 CPU）
  • SMP，对称多处理
    • 每个 CPU 的地位相同，对资源的使用权限相同，共享内存
  • ELF，可执行文件链接格式
    • 编译 → 汇编 → 链接 → ELF 文件 → 转载 → 运行
  • Monolithic Kernel，宏内核
    • 系统内核的所有模块都运行在内核态

Windows 内核

• 采用混合型内核。
• 可执行文件格式与 Linux 不同，称为可移植执行文件（PE）。

内存管理

虚拟内存

  我们把进程所使用的地址隔离开，让操作系统为每个进程分配独立的一套虚拟地址，而操作系统会提供一种机制（CPU 芯片中的内存管理单元（MMU）），将不同进程的虚拟地址和不同内存的物理地址映射起来，这个过程对于进程来说是不可见的。这样做的好处是不同的进程同时运行的时候，操作的是不同的物理地址，不会产生冲突。

• 我们程序所使用的内存地址叫做虚拟内存地址。
• 实际存在硬件里面的空间地址叫物理内存地址。

内存分段

概述

  分段是较早提出的内存管理方式。
  程序是由若干个逻辑分段组成的，例如代码分段、数据分段、栈段、堆段。不同的段具有不同的属性，可以利用分段的形式将它们分离出来。
  分段机制下，虚拟地址由两部分组成，段选择子和段内偏移量。

• 段选择子：保存在段寄存器里。
  • 段号：段表的索引。
  • 特权等标志位。
• 段内偏移量：位于 0 与段界限之间。
• 段基地址加上段内偏移量得到物理内存地址。
• 段表：保存段的基地址、段的界限和特权等级等。

缺点

• 内存碎片
  • 外部内存碎片：产生了多个不连续的小物理内存，新的程序无法被转载。
    • 内存交换：写到硬盘上，再写回内存，将不连续的小内存合并。
  • 内部内存碎片：程序所有的内存都转载到了物理内存，但有些并不常用。
• 内存交换效率低
  • 硬盘的访问速度很慢，频繁的内存交换效率低。

内存分页

概述

  内存分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小，这样一个连续并且尺寸固定的内存空间就称为页。（Linux 中一个页大小 4KB）
  虚拟地址与物理地址之间通过页表来映射。当进程要访问的虚拟地址在页表中找不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存，更新进程页表，再返回用户空间，恢复进程运行。
  分页机制下，虚拟地址由两部分组成，页号和页内偏移。

• 页号：页表的索引。
• 页内偏移：位于 0 与页大小之间。
• 页表：保存物理页每页所在的物理内存的基地址。
• 基地址和页内偏移组成物理内存地址。

优点

• 解决内存碎片问题
  • 内存空间是预先划分的，不会产生间隙非常小的内存。内存释放也是以页为单位。
• 解决内存交换效率低问题
  • 内存空间不够时，利用 LRU 将其他进程中内存页面释放掉（写入硬盘），称为换出，而需要的时候再加载进来，称为换入。这样一次磁盘 IO 只有几页，不会花费大量时间。
• 加载程序时无需一次性全部加载
  • 在程序运行中需要用到对应的虚拟内存的指令和数据时再装载页。

多级页表

• 简单分页（单页表）中存在缺陷
  • 操作系统中可以同时运行非常多的进程，这意味着页表非常的庞大。
  • 32 位操作系统，4GB 虚拟内存空间需要 4MB 大小的页表。
  • 每个进程都有自己的页表，总和就非常庞大了。
• 多级页表
  • 例如分二级，一级页表 4KB，二级页表 4MB，但一个进程通常无需这么多内存。
  • 一级页表 4KB 已经覆盖所有内存，如果某一个页表项没有被用到，可以不用创建对应的二级页表，这样二级页表总和就远小于 4MB 了。
  • 64 位系统分成了四级目录
    • 全局页目录项 PGD
    • 上层页目录项 PUD
    • 中间页目录项 PMD
    • 页表项 PTE

TLB

• 多级页表解决空间的问题，但带来了时间的开销。
• 程序是有局部性的，某段时间内执行所访问的存储空间通常只局限于某个内存区域。
• 我们可以将最常访问的几个页表项存储到访问速度更快的硬件，也就是 CPU 中专门用于存放最常访问页表项的 Cache，也就是 TLB。
• TLB 也称为页表缓存、转址旁路缓存、快表。

段页式内存管理

• 分段和分页机制是可以结合起来的，也就是段页式内存管理。
• 先将程序划分为多个有逻辑意义的段（先分段）。
• 再把每个段划分为多个页（再分页）。
• 地址结构由段号、段内页号、页内偏移三部分组成。
• 每一个程序一张段表，每个段一张页表，段表中的地址是页表的起始地址。

Linux 内存管理

Intel 处理器

• 早期的 Intel 处理器使用段式内存管理。
• 不久后实现页式内存管理，但是这个页式内存管理是建立在段式内存管理的基础上，页式内存管理的作用是在由段式内存管理所映射而成的地址上再加上一层地址映射。
• 这时由段式内存管理映射而成的地址称为线性地址（虚拟地址）。
• 逻辑地址通过段式内存管理映射为线性地址，线性地址再通过页式内存管理映射为物理地址。

Linux 的内存管理

• 主要采用页式内存管理，但同时也不可避免地涉及段机制。
• 每个段是从 0 地址开始的整个 4GB 虚拟空间（32 位），也就是说所有的段起始地址都是一样的，这意味着 Linux 系统中的代码，包括操作系统本身和应用程序代码，所面对的都是线性地址，这种做法相当于屏蔽了逻辑地址的概念。
• 段只被用于访问控制和内存保护。
• 虚拟地址空间内部又分为内核空间和用户空间。
  • 32 位系统内核空间占 1G，位于最高处，用户空间占剩下的 3G。
  • 64 位系统内核空间和用户空间都是 128T，分别占据内存空间的最高处和最低处，剩下的中间部分是未定义的。
  • 进程在用户态时，只能访问用户内存空间。
  • 只有进入内核态后，才能访问内核空间的内存。
  • 每个虚拟内存中的内核地址，关联的是相同的物理内存。
  • 用户内存空间的分布（从低到高）
    • 程序文件段，包括二进制可执行文件。
    • 已初始化的数据段，包括静态常量。
    • 未初始化的数据段，包括未初始化的静态变量。
    • 堆段，包括动态分配的内存，从低地址开始向上增长。
    • 文件映射段，包括动态库、共享内存等。
    • 栈段，包括局部变量和函数调用上下文等。大小是固定的，从高地址开始。

进程与线程

进程

• 我们编写的代码只是一个存储在硬盘中的静态文件，通过编译后生成二进制可执行文件，当运行这个可执行文件时，它会被装载到内存中，然后 CPU 执行程序中的每一条指令，而这个运行中的程序，就称为进程。
• CPU 执行指令的速度是非常快的，而需要读取文件等等指令时，硬盘的读写速度却非常慢，这个时候如果 CPU 停转等待硬盘会导致利用率非常低，因此我们需要一个进程管理方法，在某个进程阻塞时，CPU 可以执行别的进程。
• CPU 可以从一个进程切换到另一个进程，在切换前必须要记录当前进程中运行的状态信息，以备切换回来的时候可以恢复运行。

进程的状态

• 运行状态：该时刻进程占用 CPU。
• 就绪状态：可运行，由于其他进程处于运行状态而暂时停止运行。
• 阻塞状态：该进程正在等待某一事件发生（如等待输入/输出）而暂时停止运行。
• 创建状态：进程正在被创建时的状态。
• 结束状态：进程正在从系统中移除的状态。
• 阻塞挂起状态：进程在外存（硬盘）并等待某个时间的出现。
• 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即可立即运行。

进程的控制结构

• 进程控制块（PCB）是进程存在的唯一标识。
  • 进程描述信息
    • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符。
    • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务。
  • 进程控制和管理信息
    • 进程当前状态，如运行状态、就绪状态、阻塞状态等等。
    • 进程优先级：进程抢占 CPU 时的优先级。
  • 资源分配清单
    • 有关内存地址空间或虚拟地址空间的信息。
    • 所打开的文件列表和所使用的的 I/O 设备信息。
  • CPU 相关信息：CPU 中各个寄存器的值
• PCB 通常通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。除了链接，也有索引的组织方式，同一状态的进程在同一个索引表中。

进程的控制

• 创建进程
  • 为新进程分配一个唯一的进程标识号，并申请一个空白的 PCB，申请失败则创建失败。
  • 为进程分配资源，如果资源不足，则进入等待状态，等待资源分配。
  • 初始化 PCB。
  • 如果进程的调度队列可以接纳新进程，则进程进入就绪队列，等待运行。
• 终止进程
  • 查找需要终止的进程 PCB。
  • 如果处于执行状态，则立即终止运行，并将 CPU 资源分配给其他进程。
  • 如果该进程有子进程，则应将其所有子进程终止。
  • 将该进程所拥有的全部资源归还给父进程或者操作系统。
  • 将其从 PCB 所在队列中删除。
• 阻塞进程
  • 查找将要被阻塞进程标识号对应的 PCB。
  • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞态，停止运行。
  • 将该 PCB 插入到阻塞队列中去。
• 唤醒进程
  • 处于阻塞状态的进程需要由其他进程进行唤醒。
  • 在该事件的阻塞队列中找到相应进程的 PCB。
  • 将其从阻塞队列中移出，并置其状态为就绪状态。
  • 把该 PCB 插入到就绪队列中，等待调度程序调度。

进程的上下文切换

• 各个进程之间是共享 CPU 资源的，一个进程切换到另一个进程运行，称为进程的上下文切换。
• 操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器，这些信息称为 CPU 上下文。
• CPU 上下文切换分为：进程上下文切换、线程上下文切换、中断上下文切换。
• 进程的上下文切换发生在内核，不仅包含了虚拟内存、栈、全局变量等用户空间资源，还包括了内核堆栈、寄存器等内核空间的资源。
• 发生进程上下文切换的场景
  • 为了保证所有进程可以得到公平调度，CPU 时间被划分为时间片，轮流分配给各个进程。某个进程的时间片耗尽了就需要切换为就绪状态，让另外一个进程运行。
  • 进程在系统资源不足时，要等到资源满足后才可以运行，这个时候进程需要挂起，并由系统调度其他进程运行。
  • 当进程通过睡眠函数等方法将自己主动挂起时，也需要进行进程切换。
  • 当有优先级更高的进程运行时，低优先级的进程需要挂起。
  • 发生硬件中断时，CPU 上的进程会被中断挂起，然后运行内核中的中断服务程序。

线程

• 线程是进程中的一条执行流程。
• 同一个进程内的多个线程之间可以共享代码段、数据段、打开的文件等资源。
• 每个线程各自拥有一套独立的寄存器和栈，可以确保线程的控制流是相对独立的。
• 优点
  • 一个进程中可以同时存在多个线程。
  • 各个线程之间可以并发执行。
  • 各个线程之间可以共享地址空间和文件等资源。
• 缺点
  • 当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃。

线程的上下文切换

• 当进程只有一个线程时，可以认为进程就等于线程。
• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的。
• 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样。
• 当两个线程是属于同一个进程，则只需要切换线程的私有数据、寄存器等不共享的数据。

线程的实现

• 线程由线程控制块（TCB）进行控制。
• 用户线程：在用户空间实现的线程，由用户态的线程库来完成线程的管理。
  • 用户线程的 TCB 是在线程管理库中实现的，对于操作系统而言是不可见的。
  • 用户线程的整个线程管理和调度，操作系统均不参与，由用户级线程库函数完成。
  • 优点
    • 每个进程拥有它私有的 TCB 列表，可用于不支持线程技术的操作系统。
    • 用户线程的切换也是由线程库函数完成，无需切换内核态，速度快。
  • 缺点
    • 由于操作系统不参与用户线程调度，当一个线程发起系统调用而被阻塞，则该进程所包含的所有用户线程都不能执行了。
    • 当一个线程开始运行时，除非它主动地交出 CPU 的使用权，否则它所在进程中的其他线程均无法运行，因为用户态线程没有权限打断运行中的线程。
    • 由于时间片是分配给进程的，与其他进程相比，多线程中每个线程得到的时间片较少，执行会比较慢。
• 内核线程：在内核中实现的线程，是由内核管理的线程。
  • 内核线程的 TCB 放在操作系统里，由操作系统负责创建、终止和管理。
  • 优点
    • 在一个进程中，某个内核线程发起系统调用而阻塞，不会影响其他内核线程运行。
    • 时间片分配给线程，多线程的进程可以获得更多的 CPU 运行时间。
  • 缺点
    • 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息。
    • 线程的创建、终止和切换都是通过系统调用的方式来进行，系统开销较大。
• 轻量级进程（LWP）：在内核中来支持用户线程。
  • 与普通进程的区别在于它只有一个最小执行上下文和调度程序所需要的统计信息。
  • 一个进程代表程序的一个实例，而 LWP 代表程序的执行线程。

进程与线程的异同

• 进程是操作系统资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位。
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源（寄存器和栈）。
• 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转移关系。
• 线程能够减少并发执行的时间和空间开销。
  • 线程的创建和终止更快，因为所拥有的资源少，申请和释放更简单。
  • 同一进程里的线程切换比进程切换快，因为线程具有相同的地址空间，这意味着同一个进程里的线程具有同一个页表，在切换的时候无需切换页表。
  • 线程之间进行数据传递的时候不需要经过内核，数据交换效率更高。

进程间通信

管道

• 管道传输数据是单向的，并且遵循 FIFO。如果想相互通信，需要创建两个管道。
• 管道其实就是内核里面的一串缓存，从一端写入数据，从另一端读取。
• 管道传输的数据是无格式的流并且大小受限。
• 匿名管道是特殊的文件，只存在于内存而不存在于文件系统中。
• 匿名管道的通信范围是存在父子关系的进程。
• 匿名管道的生命周期跟随进程，随进程的创建建立，随进程的结束销毁。
• 命名管道拥有文件实体，可以在不相关的进程间相互通信。
• 管道的通信方式效率低，不适合进程间频繁地交换数据。

消息队列

• 消息队列是保存在内核中的消息链表，拥有独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，消息发送方和接收方要约定消息体的数据类型。
• 如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。
• 消息队列的生命周期跟随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在。
• 消息队列的不足是通信不及时，并且有大小限制。
• 消息队列不适合比较大数据的传输，因为消息体的大小有限制，队列的长度也有限制。
• 消息队列通信过程中，存在用户态和内核态之间的数据拷贝开销。

共享内存

• 两个进程拿出一块虚拟地址空间，映射到相同的物理内存。
• 这样的方法减少了拷贝的开销，可以提高通信的速度，但是同时也引入了冲突问题。
• 防止多进程竞争共享资源的问题，使用信号量进行保护。
• 信号量其实是一个整型计数器，主要用于实现进程间互斥与同步，不用于缓存通信数据。
  • P 操作：把信号量减 1，相减后小于 0 表示资源已被占用，其他进程需阻塞；大于等于 0 则表示还有资源可以使用。P 操作用于进入共享资源之前。
  • V 操作：把信号量加 1，相加后小于等于 0 表示有阻塞中的进程需唤醒；大于 0 则表明当前没有阻塞中的进程。V 操作用于离开共享资源后。
  • 如果要使得进程互斥访问共享内存，则初始化信号量为 1，称为互斥信号量。
  • 如果要使得进程顺序访问共享内存，则初始化信号量为 0，称为同步信号量。

信号

• 以上的几种进程间通信方式都是常规状态下的工作模式。而异常情况下的工作模式，则需要使用信号来通知进程。（信号与信号量是完全不同的东西）
• 信号是进程间通信机制中唯一的异步通信机制，可以在任何时候发送信号给某一进程。
• 用户进程对信号的处理方式
  • 执行默认操作。Linux 中的每种信号都有默认操作，例如终止进程等等。
  • 捕捉信号。为信号定义一个处理函数，当信号发生时执行相应的处理函数。
  • 忽略信号。当我们不希望处理某些信号的时候，可以设置忽略该信号不做处理。

套接字

• 以上的几种进程间通信方式都是在同一台主机上进行的，而跨网络与不同主机上的进程之间通信就用到了 Socket 通信，也就是套接字。当然 Socket 也可以用于本机通信。
• Socket 的系统调用中有三个参数，分别表示协议簇（IPv4、IPv6、本机）、通信特性（字节流、数据报）、通信协议。
• 不同主机间的通信需要绑定（bind）主机 IP 地址和端口号。
• TCP 协议需要建立和维护连接（使用 listen 监听，使用 connect 请求连接，使用 accept 接受连接），使用 sendto 和 recvfrom 发送和接收数据。使用 close 关闭连接。
• UDP 协议无需建立连接，但是仍然需要绑定主机 IP 地址和端口号。
• 本地 Socket 也分为字节流和数据报，实现效率大大高于 IPv4 和 IPv6 的实现。
• 本地 Socket 与 TCP、UDP 的区别是绑定的是一个本地文件，而不是 IP 和端口。

多线程同步

竞争与协作

• 互斥
  • 由于多线程执行操作共享变量的代码可能会导致竞争状态，因此我们将此段代码称为临界区，它是访问共享资源的代码片段，一定不能让多线程同时执行。
  • 我们希望临界区的代码是互斥的，也就是保证一个线程在临界区执行时，其他线程会被阻止进入临界区。
• 同步
  • 并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程/线程同步。
• 实现进程/线程间正确的协作的主要方法有两种
  • 锁：加锁、解锁
  • 信号量：P、V 操作

信号量

• 信号量是操作系统提供的一种协调共享资源访问的方法。
• 通常信号量表示资源的数量，对应的变量是一个整型变量。
• 信号量不仅可以实现临界区的互斥访问控制，还可以实现线程间的事件同步。

生产者-消费者模型

• 问题描述
  • 生产者在生成数据后，放在一个缓冲区中。
  • 消费者从缓冲区取出数据处理。
  • 任何时刻，只能有一个生产者或消费者可以访问缓冲区。
• 问题分析
  • 任何时刻只能有一个线程操作缓冲区。说明缓冲区是临界区，需要互斥。
  • 缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者需要同步。
• 信号量
  • 互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1。
  • 资源信号量 full：用于表示满槽的个数，用于消费者询问缓冲区是否有数据，有数据则可以读取数据，初始化为 0。
  • 资源信号量 empty：用于表示空槽的个数，用于生产者询问缓冲区是否有空位，有空位则可以生产数据，初始为 n（缓冲区大小）。

哲学家就餐问题

• 哲学家围成一圈吃面，每个哲学家之间有一把叉子，每个哲学家需要拿到左右两边的叉子才可以进餐。这个问题使用普通的调度可能会导致死锁（所有哲学家都拿了同一边的叉子，构成了循环等待）
• 方案一：直接使用互斥量，缺点是同一时间只能有一个哲学家进餐。
• 方案二：奇数编号和偶数编号的哲学家获取叉子的顺序不同，保证不会发生死锁。
• 方案三：使用信号量数组，当左右两边的哲学家都不是进餐状态时才可以进餐。

读者-写者问题

• 问题描述
  • 「读-读」允许：同一时刻，允许多个读者同时读
  • 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
  • 「写-写」互斥：没有其他写者时，写者才能写
• 方案一：读者优先
  • 读者计数为 0 时写者才能操作，否则会被阻塞。
  • wMutex：控制写者进入的互斥信号量，初始值为 1。
  • rCount：读者计数器，初始化为 0。
  • rCountMutex：控制对 rCount 读者计数器的互斥修改，初始值为 1。
  • 若持续不断有读者，则写者会处于饥饿状态。
• 方案二：写者优先
  • 只要有写者准备写入，写者应尽快执行写操作，后来的读者则阻塞。
  • rMutex：控制读者进入的互斥信号量，初始值为 1。
  • WDataMutex：控制写者写操作的互斥信号量，初始值为 1。
  • wCount：写者计数器，初始值为 0。
  • wCountMutex：控制对 wCount 写者计数器的互斥修改，初始值为 1。
  • 若持续不断有写者，则读者会处于饥饿状态。
• 方案三：公平策略
  • 读者和写者的优先级相同。
  • 读者、写者互斥访问。
  • 只能一个写者访问临界区。
  • 可以有多个读者同时访问临界资源。

各种锁

• 使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。
• 任何想进入临界区的线程，必须先执行加锁操作，若操作顺利通过，则线程可以进入临界区。
• 在完成对临界资源的访问后需要执行解锁操作，以释放该临界资源。

互斥锁与自旋锁

• 互斥锁加锁失败后，线程会释放 CPU，给其他线程。
  • 独占锁，一旦一个线程加锁成功就独占，其他线程会因为加锁失败而阻塞。
  • 阻塞的线程会将 CPU 让给其他线程执行。
  • 对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。
  • 开销成本主要来源于两次线程上下文切换。
  • 如果被锁住的代码执行时间很短，可能上下文切换时间比锁住的代码执行时间更长。
• 自旋锁加锁失败后，线程会忙等待，直到它拿到锁。
  • 自旋锁通过 CPU 提供的 CAS 函数，在用户态完成加锁和解锁操作。
  • 加锁过程分为两步：查看锁的状态，若空闲则设置为当前线程拥有。
  • 上面的操作被 CAS 函数合并成一条硬件级指令，是具有原子性的。
  • 在单核 CPU 中，需要抢占式调度器（不断通过时钟中断一个线程，运行其他线程）。这是因为自旋的线程永远不会放弃 CPU。

读写锁

• 读写锁适用于能明确区分读操作和写操作的场景。
• 读锁是共享锁，而写锁是独占锁。
• 读写锁可以根据场景选择使用互斥锁还是自旋锁实现。

乐观锁与悲观锁

• 悲观锁对多线程竞争持悲观态度，认为多线程同时修改共享资源的概率比较高，于是很容易发生冲突，所以访问共享资源前都需要先上锁。
• 乐观锁对多线程竞争持乐观态度，认为冲突的概率较低，工作时先修改共享资源，再检验这段时间内有没有发生冲突，如果没有其他线程在修改资源则操作完成，如果发现有其他线程已经修改过这个资源则放弃操作。
• 一般来说，乐观锁一旦发生冲突，处理成本是比较高的，但是如果冲突概率足够低就可行。并且实际上它并没有真正上锁，所以也称为无锁编程。

死锁

• 死锁发生的条件
  • 互斥条件：多个线程不能同时使用用一个资源。
  • 持有并等待条件：线程已经持有一定资源，并在等待其它线程持有的资源。
  • 不可剥夺条件：线程拥有的资源在使用完之前不能被其他线程获取。
  • 环路等待条件：线程正在等待的资源顺序刚好构成了环形链。
• 避免死锁的方法就是破坏以上任意一个条件。
• 最常见的解决方法是使用资源有序分配法来破坏环路等待条件。

调度算法

进程调度

• 非抢占式调度算法
  • 当进程正在运行时，它会一直运行，直到该进程完成，或者发生某个事件而被阻塞，才会把 CPU 让给其他进程。
• 抢占式调度算法
  • 当进程正在运行时，可以被打断，使其把 CPU 让给其他进程。

先来先服务调度算法

• 先来先服务（FCFS）算法是非抢占式调度算法。
• 每次从就绪队列选择最先进入队列的进程。
• 一直运行进程，直到进程退出或者被阻塞，才选择下一个进程运行。
• 对短作业不利，如果前面有长作业先运行，那么短作业等待的时间会很长。
• 对长作业有利，适用于 CPU 繁忙型作业的系统，不适用于 I/O 繁忙型作业的系统。

最短作业优先调度算法

• 最短作业优先（SJF）算法也是非抢占式调度算法。
• 优先选择运行时间最短的进程来运行，有助于提高系统吞吐量。
• 对长作业不利，极端情况下长作业永远也不会被运行。

高响应比优先调度算法

• 高响应比优先（HRRN）算法权衡了短作业和长作业。
• 每次进行进程调度时先计算响应比优先级，最高的进程投入运行。
• 优先权 = ( 等待时间 + 要求服务时间 ) / 要求服务时间。
• 等待时间相同时，短作业优先权更高，更容易被选中运行。
• 而随着等待时间增长，优先权会逐渐变高，这样就兼顾了长作业。

时间片轮转调度算法

• 时间片轮转（RR）算法是抢占式调度算法。
• 每个进程被分配一个时间段，称为时间片，允许该进程在该时间段中运行。
• 如果时间片用完，进程还在运行，则此进程会从 CPU 中释放出来，分配给另外一个进程。
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。
• 如果时间片设置得太短会导致频繁的进程上下文切换，降低了 CPU 效率。
• 如果时间片设置得太长会导致短作业进程的响应时间变长。
• 一个时间片大小通常设置为 20ms ~ 50ms

最高优先级调度算法

• 最高优先级（HPF）算法从就绪队列中选择最高优先级的进程运行。
• 静态优先级：创建进程的时候确定优先级，并且整个运行时间都不会变化。
• 动态优先级：根据进程的动态变化调整优先级，例如随着运行时间增加降低优先级，随着等待时间增加升高优先级。
• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
• 低优先级的进程可能永远不会运行。

多级反馈队列调度算法

• 多级反馈队列（MFQ）算法是时间片轮转算法和最高优先级算法的综合和发展。
• 多级表示有多个队列，每个队列优先级从高到低，优先级越高时间片越短。
• 反馈表示如果有新的进程加入优先级高的队列，立即停止当前正在运行的进程并将其移入原队列队尾，转而去运行优先级高的队列。
• 新的进程会被放入第一级队列的末尾，按先来先服务的原则排队等待调度。如果在第一级队列规定的时间片没运行完成，则将其转入第二级队列的末尾，以此类推，直完成。
• 短作业可以在第一级队列很快处理完。而长作业在第一级队列处理不完，可以移入下一队列，下次运行的时间片更长。这样就很好地兼顾了长短作业，并且响应时间也比较理想。

页面置换

• 缺页异常（缺页中断）指 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入物理内存。
• 缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完成之后检查和处理中断信号。缺页中断返回到该指令的开始重新执行，而一般中断返回到该指令的下一个指令执行。
• 页面换入的时候需要寻找空闲页进行替换，若没有空闲页就需要使用页面置换算法选择一个页面换出到磁盘中。
• 页表项字段
  • 页号、物理页号
  • 状态位：表示该页是否有效，也即是否在物理内存中。
  • 访问字段：记录该页在一段时间被访问的次数，用于页面置换算法作参考。
  • 修改位：表示该页在调入内存后是否有被修改过，如果有则称为脏页，在置换该页时需要写回磁盘；若没有则置换时无需写回磁盘，可以减少系统开销。
  • 硬盘地址：表示该页在硬盘上的地址，通常是物理块号，供调入该页时使用。

最佳页面置换算法

• 最佳页面置换算法（OPT）基本思路是置换在“未来”最长时间不访问的页面。
• 该算法实现需要计算内存中每个逻辑页面的下一次访问时间，通过比较选择换出的页。
• 这种算法是理想算法，实际系统中无法实现，因为程序访问页面是动态的，我们无法预知每个页面下一次访问的时间。
• 最佳页面置换算法的作用是衡量其他页面置换算法的效率，越接近这个效率表明算法越高效。

先进先出置换算法

• 先进先出置换算法（FIFO）选择在内存驻留时间最长的页面进行置换。
• FIFO 算法通常来说并不高效，优点是简单。

最近最久未使用置换算法

• 最近最久未使用置换算法（LRU）选择最长时间没有被访问的页面进行置换。
• 该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内也不会被使用。
• 最佳页面置换算法通过“未来”的使用情况淘汰页面，而 LRU 使用“历史”的使用情况来推测需要淘汰的页面，效果是较优的。
• LRU 的缺点是实现代价比较高，因为我们需要在内存中维护一个所有页面的链表，最近使用的页面在表头，而最近最久未使用的页面在表尾。每次访问都需要更新链表。
• 所以 LRU 虽然效果不错，但是因为开销比较大，在实际应用中较少使用。

时钟页面置换算法

• 时钟页面置换算法（Clock）与 LRU 近似，又是对 FIFO 的一种改进，比较容易实现。
• 该算法把所有的页面保存在一个类似钟面的环形链表中，一个表针指向最老的页面。
• 发生缺页中断时，检查表针指向的页面。
  • 如果访问位是 0，淘汰该页面，把新的页面插入到这个位置，表针前移一个位置。
  • 如果访问位是 1，清除访问位，表针前移一个位置，继续寻找访问位为 0 的页面。
• 这个算法结合了 LRU 和 FIFO 的部分优点，采取了较容易实现的方式，是不错的改进。

最不常用置换算法

• 最不常用置换算法（LFU）选择访问次数最少的页面进行置换。
• 该算法对每个页面设置一个访问计数器，每当一个页面被访问，访问计数器累加 1。
• 虽然算法非常简单，但是需要增加一个计数器，这对操作系统来说是不小的硬件成本。并且查找计数器值最小的页面也是比较耗时的操作。
• 另一个缺点是 LFU 只考虑了频率而没有考虑时间，一个非常常见的情况是某些页面在过去的一段时间内访问频率很高，但是现在已经不常访问甚至是不访问了，而目前频繁访问的页面没有这些页面访问次数高，可能会在刚开始频繁访问的时候不断换进换出，因此效果不佳。
• 上面的这个缺点也有一些应对办法：定期减少所有页面的访问次数，这样随着时间的流逝，以前的高访问页面的访问计数器会不断减少，增加被置换的几率。

磁盘调度

• 常见的机械磁盘是由多个盘片组成的，每个盘片有磁头，每一层有多个磁道，每个磁道分为多个扇区，每个扇区大小是 512 字节。每个相同编号的磁道形成的圆柱称为磁盘的柱面。
• 磁盘调度算法的目的就是提高磁盘的访问性能，一般通过优化磁盘的访问请求顺序做到。
• 寻道的时间是磁盘访问最耗时的部分，因此优化的方向可以是尽量减少寻道次数。

先来先服务算法

• 先来先服务（FCFS）算法就是先到的请求先服务。
• 这种算法是最简单粗暴的做法，如果请求访问的磁道比较分散则会导致性能特别差。

最短寻道时间优先算法

• 最短寻道优先（SSF）算法是优先选择从当前磁头位置所需寻道时间较短的请求。
• 这个算法相比 FCFS 服务性能提升很多，但是可能存在的问题是饥饿。
• 产生饥饿的情况就是动态的请求使得磁头在一小块区域来回移动，而没有服务远端的请求。

扫描算法

• 扫描（Scan）算法可以防止 SSF 算法造成的饥饿。
• 该算法规定磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上最后的磁道，再调换方向，如此在磁道来回移动。
• 扫描算法的性能较好，不会产生饥饿，不过存在的问题是中间部分的磁道的响应效率会高一些，磁道的响应频率存在差异。

循环扫描算法

• 循环扫描算法（C-Scan）用于解决磁道访问频率差异的问题。
• 该算法规定只有磁头朝某个特定方向移动时才处理访问请求；而返回时则直接快速移动到最靠边缘的起始磁道，不处理任何请求，也即是复位，这个过程是很快的。

Look 与 C-Look 算法

• 上面说到的扫描算法和循环扫描算法都是磁头移动到磁盘的最始端和最末端才调换方向，而 Look 算法优化的思路就是在移动到最远的请求之后就调换方向。
• Scan 算法对应的就是 Look 算法，C-Scan 算法对应的就是 C-Look 算法。

文件系统

文件系统的基本组成

• 文件系统是操作系统中负责管理持久数据的子系统。
• 文件系统的基本数据单位是文件，它的目的是对磁盘上的文件进行组织管理。
• Linux 最经典的一句话：「一切皆文件」，不仅普通文件和目录，就连块设备、管道、Socket 等，都是统一交给文件系统管理的。
  • 索引节点。记录文件的元信息，比如索引编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘中的位置等等。它是文件的唯一标识，它们之间一一对应，而索引节点同样也存储在磁盘中，占用磁盘空间。
  • 目录项。记录文件的名字、索引节点指针以及其他目录项的层级关联关系。多个目录项关联起来就形成目录结构。与索引不同的是，目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存中。
• 注意目录和目录项并不是一个东西。目录也是文件，也是用索引节点唯一标识，和普通文件不同的是，普通文件在磁盘里保存的是文件数据，而目录文件保存的是子目录或文件。目录项则是内核里的一个数据结构，缓存在内存，目的是加快文件系统效率。
• 磁盘读写的最小单位是扇区，大小 512B，多个扇区组成一个逻辑块，文件系统每次读写的最小单位就是逻辑块，Linux 中的逻辑块大小为 4KB（8 个扇区）。
• 磁盘的存储区域
  • 超级块，用来存储文件系统的详细信息，如块个数、块大小、空闲块等等。
  • 索引节点区，用来存储索引节点。
  • 数据块区，用来存储文件或目录数据。
• 虚拟文件系统
  • 文件系统种类众多，而操作系统希望读用户提供一个统一的接口。
  • 我们在用户层与文件系统层引入了中间层，就是虚拟文件系统（VFS）。
  • VFS 定义了一组所有文件系统都支持的数据结构和标准接口。

文件的存储

连续空间存放方式

• 文件存放在磁盘连续的物理空间中。读写效率高。
• 文件头里需要指定起始块的位置和长度。
• 缺陷是存在磁盘空间碎片、文件长度不易扩展。

非连续空间存放方式

• 链表方式
  • 存放方式是离散的，不连续的。
  • 可以消除磁盘碎片，文件长度可以动态扩展。
  • 隐式链表
    • 文件头包含第一块和最后一块的位置。
    • 每个数据块里面留出一个指针空间，存放下一个数据块的位置。
    • 缺点是无法直接访问数据块，需要通过指针顺序访问，指针也消耗一定空间。
    • 稳定性较差，如果数据块指针丢失或损坏，文件数据会丢失。
  • 显式链表
    • 每个磁盘块的指针都放在内存的一个表中。
    • 每个表项中存放链接指针，指向下一个数据块号。
    • 这个表格称为文件分配表（FAT）。
    • 查找记录的过程是在内存中进行的。
    • 提高了检索速度，大大减少了磁盘访问次数，但不适用于大磁盘。
• 索引方式
  • 为每个文件创建一个索引数据块，存放了指向文件数据块的指针列表。
  • 文件头需要包含指向索引数据块的指针。
  • 优点
    • 文件的创建、增大、缩小很方便。
    • 不会有磁盘碎片的问题。
    • 支持顺序读写和随机读写。
  • 缺点
    • 索引数据块带来的开销。
  • 当文件很大，一个索引块放不下的时候
    • 链式索引块。同样的，这个处理方式也会存在文件损坏的问题。
    • 多级索引块。利用索引套索引的方式。

Unix 文件的实现方式

• 结合了前面几种存放方式，根据文件的大小进行变化。
  • 如果数据块小于 10 块，采用直接查找的方式。
  • 如果数据块多于 10 块，采用一级间接索引方式。
  • 如果前面两种方式不够存大文件，采用二级间接索引方式。
  • 如果二级间接索引也不够存放大文件，采用三级间接索引方式。
• 对于小文件使用直接查找的方式可以减少索引数据块的开销。
• 对于大文件采用多级索引的方式支持，所以大文件访问数据块的时候需要大量查询。

空闲空间管理

• 存储管理是针对已经被占用的数据块的组织和管理。
• 而新的数据块保存在哪里，就需要用到空闲空间管理来进行分配。

空闲表法

• 为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数。
• 这个方式是连续分配的，空闲块个数符合要求才会进行分配。
• 这种方法适用于仅有少量空闲块，如果存储空间有大量小空闲块，则空闲表很大。

空闲链表法

• 使用链表的方式来管理空闲空间，每个空闲块有一个指针指向下一个空闲块。
• 这种方法很方便把空闲块连接起来一起分配。
• 回收空间时就把空闲块依次连接到链头上，主存中只保存指向第一个空闲块的指针。
• 特点是简单，但不能随机访问，工作效率低，不适用于大型文件系统。

位图法

• 利用二进制的一位来表示磁盘中的一个盘块的使用情况。
• 当值为 0 时表示对应的盘块空闲，值为 1 时表示对应的盘块已分配。

文件系统的结构

• 上面提到的位图法，一个块的位图+这个位图表示的所有块，假设一个块大小为 4 KB，则这样一个数据结构最多只能表示 128 MB 的空间。
• 上面的数据结构成为块组，而一个文件系统有大量的块组。
• 块组的内容
  • 超级块，包含文件系统的重要信息。比如 inode 总个数、块总个数。
  • 块组描述符，包含文件系统中各个块组的状态。比如空闲块和 inode 数目。
  • 数据位图和 inode 位图，用于表示对应的数据块或者 inode 是否空闲。
  • inode 列表，inode 用于保存文件系统中各个文件和目录相关的所有元数据。
  • 数据块，包含文件的有用数据。
• 上面提到的超级块和块组描述符所包含的信息是冗余的。
  • 它们保存的是全局消息，并且非常重要，冗余是为了提高可靠性。
  • 文件和管理数据尽可能靠近，可以减少磁头寻道和旋转，提高性能。（空间换时间）
  • Ext2 后续版本使用了稀疏技术，它们不再存储到每个块组中，而是只写入到块组 0、块组 1 和其他可以表示为 3、5、7 的幂的块组中。

软链接和硬链接

• Linux 中可以通过硬链接和软链接的方式来给某个文件取别名。
• 硬链接
  • 多个目录项中的索引节点指向一个文件，也即指向同一个 inode。
  • 硬链接不可用于跨文件系统。
  • 只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。
• 软链接
  • 软链接相当于重新创建一个文件，这个文件的内容是另外一个文件的路径。
  • 所以软链接的文件有独立的 inode，并且是可以跨文件系统的。
  • 目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了。

文件 I/O

缓冲与非缓冲 I/O

• 文件操作的标准库可以实现数据的缓存，根据是否利用标准库缓冲，可将文件 I/O 分为缓冲 I/O 和非缓冲 I/O。
• 缓冲 I/O，利用标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件。
• 非缓冲 I/O，直接通过系统调用访问文件，不经过标准库缓存。
• 例子：很多程序在换行的时候再进行输出，而换行前的内容就是由标准库暂时缓存。

直接与非直接 I/O

• 根据是否利用操作系统的缓存，可以把文件 I/O 分为直接 I/O 与非直接 I/O。
• 直接 I/O，不会发生内核缓存和用户程序之间的数据复制，直接经过文件系统访问磁盘。
• 非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序；写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。
• 非直接 I/O，内核什么情况下会把缓存数据写入磁盘？
  • 在调用 write 的最后，发现内核缓存的数据太多的时候，内核会把数据写入磁盘。
  • 用户主动调用 sync，内核缓存会刷到磁盘上。
  • 当内存十分紧张，无法再分配页面时，会把内核缓存的数据刷到磁盘上。
  • 内核缓存的数据的缓存时间超过某个时间时，会把数据刷到磁盘上。

阻塞与非阻塞 I/O

• 阻塞 I/O，当用户程序执行 read，线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷贝到应用程序的缓冲区中，当拷贝过程完成，read 才会返回。
• 非阻塞 I/O，read 请求在数据未准备好的情况下会立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷贝到应用程序缓冲区，read 调用才可以获取到结果。
• I/O 多路复用，也是一种非阻塞 I/O，通过 I/O 事件分发，当内核数据准备好时，再以事件的方式通知应用程序进行操作。这个做法大大改善了应用程序对 CPU 的利用率，应用程序无需一直轮询而没有做其他事情。

同步与异步 I/O

• 同步 I/O，上面的阻塞与非阻塞 I/O 都是同步调用，它们在 read 调用时，内核将数据从内核空间拷贝到应用程序空间，过程都是需要等待的，也就是同步的。如果内核实现的拷贝效率不高，那么 read 调用在这个过程中就需要等待较长时间。
• 异步 I/O，内核数据准备好和数据从内核态拷贝到用户态，都不需要等待。

设备管理

设备控制器

• 电脑的输入输出设备非常多样，比如键盘、鼠标、显示器、网卡、硬盘、打印机、音响等。
• 为了屏蔽设备之间的差异，每个设备都使用设备控制器进行管理。
• 控制器一般有三类寄存器
  • 状态寄存器，存储设备的工作状态。
  • 命令寄存器，存储 CPU 向设备发送的命令。
  • 数据寄存器，存储 CPU 向 I/O 设备写入的需要传输的数据。
• 输入输出设备也可以分为两大类
  • 块设备，把数据存储在固定大小的块中，每个块有自己的地址，例如硬盘、USB。
  • 字符设备，以字符为单位发送或接收字符流，不可寻址，没有寻道，例如鼠标。

I/O 控制方式

• 硬件一般拥有中断控制器，当设备完成任务后就触发中断，通知 CPU 处理。
• 中断的方式对于读写频繁的磁盘并不友好，这样的 CPU 经常会被打断而影响效率。解决方法是使用 DMA 控制器，使得设备在 CPU 不参与的情况下，自行完成把设备 I/O 数据与内存交互，而 CPU 只需要在传送开始和结束的时候进行干预。

设备驱动程序

• 虽然设备控制器屏蔽了设备的众多细节，但是每种设备控制器的寄存器、缓冲区等使用模式也是不同的，为了屏蔽这种差异，我们还需要设备驱动程序。
• 设备控制器是硬件的一部分，而设备驱动程序是操作系统的一部分。
• 中断处理程序就位于设备驱动程序里，中断处理程序的处理流程如下
  • 设备控制器如果已经准备好数据，则会通过中断控制器向 CPU 发送中断请求。
  • 保护被中断进程的 CPU 上下文。
  • 转入相应的设备中断处理函数。
  • 进行中断处理。
  • 恢复被中断进程的上下文。

通用块层

• 对于块设备，为了减少不同块设备的差异带来的影响，Linux 使用一个通用块层进行管理。
• 通用块层是处于文件系统和磁盘驱动中间的一个块设备抽象层。
• 第一个功能，向上为文件系统和应用程序，提供访问块设备的标准接口，向下把各种不同的磁盘设备抽象为统一的块设备，并在内核层面，提供一个框架来管理这些设备的驱动程序。
• 第二个功能，通用块层还会给文件系统和应用程序发来的 I/O 请求排队，并对队列进行重新排序、请求合并，也就是 I/O 调度，主要目的是提高磁盘读写的效率。

网络系统

网络模型

• 开放式系统互联参考模型（OSI）（7 层）
• TCP/IP 网络模型（4 层）
• 具体可以参考 计算机网络 知识总结 这篇文章。
• Linux 网络协议栈
  • 应用程序需要通过系统调用，跟 Socket 层进行数据交互。
  • Socket 层的下面就是传输层、网络层和网络接口层。
  • 最下面的一层，则是网卡驱动程序和硬件网卡设备。

Linux 收发网络包的流程

• 接收网络包的流程
  • 网卡是计算机里的一个硬件，专门负责接收和发送网络包。
  • 当网卡接收到一个网络包时，会通过 DMA 技术，将网络包放入 Ring Buffer 中，这是一个环形的缓冲区。然后触发中断，告诉操作系统。
  • 操作系统中有一个 NAPI 机制来处理网络包。它是混合了中断和轮询的方式来接收网络包，核心概念就是不采用中断的方式读取数据，而是首先采用中断唤醒数据接收服务程序（软中断），然后通过 poll 方法轮训数据。
  • 软中断处理网络包会从 Ring Buffer 拷贝数据到内核缓冲区，交给协议栈逐层处理。
  • 在网络接口层会判读报文合法性，不合法则丢弃，然后找出上层协议类型（IP 协议 IPv4、IPv6），去掉帧头和帧尾，交给网络层。
  • 取出 IP 包，判断 IP 包的走向，是发给本机的（需要交给上层处理）还是需要进行转发的。如果是发给本机的，从 IP 头查看上层网络协议类型（传输层协议 TCP、UDP），然后去掉 IP 头，交给传输层。
  • 取出 TCP 头或者 UDP 头，根据四元组找到对应的 Socket，并将数据拷贝给 Socket 的接收缓冲区。
  • 应用层程序调用 Socket 接口，从内核的 Socket 接收缓冲区取出数据。
• 发送网络包的流程
  • 发送网络包的流程刚好和接收流程相反。
  • 应用程序调用 Socket 发送数据包，这是系统调用，会从用户态进入内核态。
  • Socket 层从发送缓冲区中取出数据包，通过协议栈逐层封装。
  • 最后达到网络接口层，添加了帧头帧尾后，放到发包队列中。
  • 触发软中断告诉网卡驱动程序，然后通过 DMA，读取网络包，加入硬件网卡的队列中，然后通过物理网卡将其发送出去。

零拷贝

• 磁盘是计算机系统最慢的硬件之一，读写速度相比其他硬件来说慢了非常非常多，因此针对磁盘优化很有必要，可以大幅提高系统的吞吐量。
• DMA 技术也即直接内存访问技术，在进行 I/O 设备和内存的数据传输时，交给 DMA 控制器，而 CPU 不参与这个数据搬运的工作，可以去处理别的事务。
• 传统的网络文件传输中，需要将磁盘上的文件读取出来，然后通过网络协议发送出去，这个过程需要两个系统调用，read 和 write，期间发送了 4 次用户态与内核态的上下文切换，因为每次系统调用会从用户态切换到内核态，完成任务后又从内核态切换回用户态。
• 这期间还发生了 4 次数据拷贝，从磁盘中拷贝到内核缓冲区（通过 DMA 搬运），从内核缓冲区拷贝到用户缓冲区，从用户缓冲区拷贝到内核的 Socket 缓冲区，从 Socket 缓冲区拷贝到网卡的缓冲区（通过 DMA 搬运）。
• 可以看到，想要提升网络文件传输的性能，就需要减少用户态与内核态的上下文切换和内存拷贝的次数，也就是零拷贝技术。
• 减少上下文切换次数的思路是减少系统调用，因为系统调用必然会导致两次上下文切换。
• 减少内存拷贝次数的思路是减少其中不必要的拷贝，比如通过用户缓冲区的这个过程，如果用户程序并没有对数据进行修改，这个过程是不必要的。
• mmap + write 技术
  • 通过 mmap() 系统调用函数直接把内核缓冲区的数据映射到用户空间，而没有进行实际的数据拷贝操作。这个技术可以减少一次拷贝操作。
• sendfile 函数
  • ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);
  • 参数分别是目的端文件描述符、源端文件描述符、源端偏移量、复制数据长度。返回值是实际复制数据的长度。
  • 这个函数只有一次系统调用，因此只有 2 次上下文切换开销。
  • 这个函数的数据拷贝次数也是 3 次，数据没有到用户缓冲区。
• SG-DMA 技术
  • 如果网卡支持 SG-DMA 技术，还可以再减少一次数据拷贝，无需通过 Socket 缓冲区。
  • 具体过程是只有缓冲区描述符和数据长度传送到了 Socket 缓冲区，然后网卡的 SG-DMA 控制器直接从内核缓冲区将数据拷贝到网卡的缓冲区里。
  • 这个技术就是真正的零拷贝技术，两次数据拷贝都是 DMA 完成的，无需使用 CPU 进行数据搬运，没有从内存层面拷贝数据。

大文件传输

• PageCache 也即磁盘高速缓存，它是内存中存放的磁盘的部分缓存。
  • 缓存最近被访问的数据。
  • 预读功能。
• 在传输大文件（GB 以上级别）时，PageCache 会失效。
  • PageCache 被大文件占据，其他热点小文件无法充分利用 PageCache 提高读写性能。
  • PageCache 无法一次性装入大文件，换进后又换出，并且其中一些文件再次被访问的概率也非常低，无法享受缓存带来的好处，还耗费了 DMA 的一次拷贝。
• 因此大文件传输不应该使用 PageCache 零拷贝技术。一般是采用异步 I/O + 直接 I/O 的方式，绕开 PageCache。

I/O 多路复用

• Socket 模型中，一个客户端请求对应一个连接。
• 多进程模型中，一个连接对应一个子进程，复制了父进程的文件描述符，就可以维护一个已连接 Socket，不过进程上下文切换的开销非常大，100 以上连接就开始扛不住。
• 多线程模型中，一个连接对应一个线程，比起多进程开销小了一些，但是频繁的创建和销毁线程也会带来不小的系统开销。这个时候可以采用线程池进行避免，也就是提前创建若干个线程，用于处理已连接的 Socket。不过需要注意的是，已连接 Socket 队列是全局的，为了避免多线程竞争，操作这个队列时需要加锁。
• 有没有只使用一个进程来维护多个 Socket 呢？其实就是 I/O 多路复用技术。
• select/poll
  • select 是将已连接的 Socket 都放到一个文件描述符集合，调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生，将此 Socket 标记为可读/可写，再把文件描述符拷贝回用户态，遍历找到可读/可写的 Socket 并处理。
  • select 这种方式，需要 2 次遍历文件描述符集合，2 次拷贝文件描述符集合。
  • select 采用固定长度的 BitsMap，表示文件描述符集合。默认最大值 1024。
  • poll 则是使用动态数组，以链表的方式组织，突破了文件描述符个数限制。
  • 它们并没有本质区别，都是使用线性结构存储，都需要使用遍历的方式检查。
• epoll
  • epoll 在内核中是使用红黑树来跟踪进程所有待检测的文件描述符。每次操作只传入需要检测的 Socket，可以在对数时间内得到结果。并且是在内核中完成，减少了大量的内存分配和数据拷贝的工作。
  • epoll 使用了事件驱动的机制，内核里维护了一个链表来记录就绪事件，当某个 Socket 有事件发生时，通过回调函数将其加入这个链表中，当用户调用 epoll_wait() 函数时，只会返回有事件发生的文件描述符个数，而无需进行轮询。
  • 边缘触发（ET），当被监控的 Socket 描述符上有可读事件发生时，服务器端只会从 epoll_wait 中苏醒一次，即使进程没有调用 read 函数从内核中读取数据。因此我们要保证一次性将内核缓冲区的数据读取完。边缘触发模式一般和非阻塞 I/O 搭配使用，程序会一直执行 I/O 操作直到返回错误。
  • 水平触发（LT），当被监控的 Socket 上有可读事件发生时，服务器端不断地从 epoll_wait 苏醒，直到内核缓冲区的数据被 read 函数读完才结束。