操作系统

本篇文章系统梳理了研究生招生考试《计算机学科基础》科目中操作系统部分的核心知识点。首先介绍了操作系统概念和RISC-V环境下的系统调用机制，分析了硬件异常处理和用户态与内核态的切换流程。接着，阐述了操作系统引导过程，以及微内核和宏内核模型的差异与适用场景。随后，详细讨论了进程和线程的概念，进程调度算法、线程同步与互斥、信号量及死锁预防与检测的原理，并通过银行家算法等典型案例说明死锁避免方法。内存管理部分重点介绍了分页与分段、虚拟内存、页面置换算法以及工作集等概念。文件系统方面，则围绕文件结构、目录管理、磁盘空间分配策略等内容展开。最后讲解了I/O系统及磁盘调度算法，为研究生招生考试《计算机学科基础》科目中的操作系统部分提供了全面、系统的复习思路。

（摘要由 OpenAI o1-preview 生成）

第一章 操作系统概述

系统调用

RISC-V ISA 中的系统调用过程（省略了一些细节）：

1. 系统调用参数使用寄存器 a0 - a5，系统调用号使用 a7， 系统调用的返回值会被保存到 a0 与 a1 中。
2. ecall 后，硬件将触发 ecall-from-u-mode-exception（如果符合其他条件），在这个过程中，硬件所实现的部分是：将 pc 存入 sepc，将 scause 赋值为与 ecall 对应的异常号，然后跳转到 stvec 中对应的异常处理程序地址（Direct 模式中）。
3. 该异常被操作系统的 trap_handler() 捕获，保存 usp 及其他寄存器，根据 scause 的值判断是哪种异常，然后调用对应的处理函数（此处是系统调用处理函数）。
4. 根据保存在栈上的 a7 的值，调用对应的系统调用处理函数。
5. 系统调用处理完成后，恢复寄存器，并将系统调用的返回值保存到 a0 与 a1 中，sepc +=4，sret，回到 U-Mode 继续执行用户态程序。

操作系统的引导

1. CPU 上电
2. 执行 BIOS 或者 UEFI 固件
3. 硬件自检
4. 读取 boot sequence，找到 MBR（BIOS） 或者 GUID 分区表（UEFI）
5. 由 MBR 找到可引导扇区，加载可引导扇区中的 PBR，由 PBR 找到启动管理器，加载操作系统（BIOS）
6. 由 GUID 分区表找到 EFI 系统分区，加载 EFI 引导程序，加载操作系统（UEFI）

微内核、宏内核

微内核：只有必要的功能模块（进程调度、低级存储器管理、中断处理、...）运行在内核态，其他功能模块运行在用户态，通过消息传递进行通信。

宏内核：几乎所有功能模块都作为一个整体运行在内核态，通过函数调用进行通信。

第二章 进程、线程

线程 \(\approx\) 微型的进程，同一个进程中的线程共享地址空间。其调度开销更小，但是需要考虑线程间的同步问题。

线程模型：用户级线程到内核级线程的多对一、一对一、多对多映射关系。

进程调度

(1) 类型：抢占式、非抢占式。

(2) 调度算法：先来先服务、短作业优先、高响应比优先（(等待时间 + 要求服务时间)/要求服务时间）、优先级调度、时间片轮转、多级反馈队列。

(3) 性能指标

CPU 利用率 = CPU 有效工作时间 / (CPU 有效工作时间 + CPU 空闲时间)

周转时间 = 完成时间 - 到达时间

带权周转时间 = 单个任务的周转时间 / 单个任务的服务时间

平均周转时间 = 所有任务的周转时间之和 / 任务数

平均带权周转时间 = 所有任务的带权周转时间之和 / 任务数

(4) 饥饿现象：某些进程长时间得不到调度。

进程同步

(1) 临界资源：一次只允许一个进程访问的资源。

(2) 信号量 S、P() 操作、V() 操作：信号量 S 代表某一资源的剩余数量，进程使用 P() 操作申请资源，V() 操作释放资源。

S > 0 代表仍有资源可用，S = 0 代表资源已被完全使用，S < 0 代表存在等待资源的进程。

对 S < 0 进行 P(S) 操作的进程将被阻塞并加入等待队列中，等待某一个进程执行 V(S) 操作，并使得 S > 0，从而被按等待顺序唤醒。

P()、V() 操作必须是原子操作，不可被打断。

(3) 互斥锁：同时只允许一个线程访问的资源。使用信号量描述的话，其初始值为 1。

(4) 信号量相关套路题

a. 有 n 个格子可以用来放置物品：使用信号量 full = 0（对应取操作）、empty = n（对应放操作）。

b. 按顺序从 n 个格子中取：使用信号量 S1 = 1、S2 = ... = Sn = 0。对第 i 个格子取：P(Si)、V(Si+1)。（推广：前后依赖关系，画依赖有向图，入边请求 P()，出边释放 V()）

c. 互斥锁：使用信号量 mutex = 1。

d. 计数：使用 mutex 保护计数器。

e. 读者写者问题：读写互斥、写写互斥、读读不互斥。

f. 哲学家吃饭问题：当两手筷子都可用时，才能拿起筷子。

g. 使得共享全局变量的多个线程运行效率最高：画出全局变量-线程对的表格。不共享、读读不互斥，读写、写写互斥。（2017）

死锁

死锁的四个必要条件：

(1) 互斥条件：资源只能被一个进程占用。

(2) 不可抢占条件：资源只能由进程自愿释放。

(3) 请求并保持条件：进程可以请求资源并保持已有资源不释放。

(4) 循环等待条件：进程之间形成一种循环等待资源的关系。

直接针对以上任意一点的算法被称为死锁预防算法。

死锁避免：银行家算法

尝试找到一个安全的资源分配序列。

资源分配表：

使用列表描述系统中的资源分配情况，包括进程的最大需求 Max、已分配资源 Allocation、还需要的资源 Need、系统中剩余的资源 Available，工作列表 Work（初始值为 Available）。

Available	[3, 3, 2]

进程	Max	Allocation	Need = Max - Allocation
P0	[7, 5, 3]	[0, 1, 0]	[7, 4, 3]
P1	[3, 2, 2]	[2, 0, 0]	[1, 2, 2]
P2	[9, 0, 2]	[3, 0, 2]	[6, 0, 0]
P3	[2, 2, 2]	[2, 1, 1]	[0, 1, 1]
P4	[4, 3, 3]	[0, 0, 2]	[4, 3, 1]

在资源分配表中，划去能够满足的进程，将其添加到安全序列中，然后释放其资源，更新 Work（其实就是代表了下一个状态的 Available），迭代直到所有进程都被划去。若某一状态下无法找到任何一个进程能够被满足，则回溯。

死锁检测：简化资源分配图

资源分配图：用顶点表示进程和资源，用从进程到资源的有向边表示当前资源请求，用从资源到进程的有向边表示当前资源分配。

对资源分配图进行简化：找到能够满足的进程，满足其需求，然后释放其占有的资源，将其请求边和分配边删除，迭代直到所有的边都被删除。若某一状态下无法找到任何一个进程能够被满足，则说明存在死锁。（死锁定理）

第三章 内存管理

未引入虚拟内存前

(1) 单一连续分配：一个程序独享全部的内存空间

(2) 固定分区分配：将内存分为若干固定大小的区域，每个区域只能分配给一个进程

(3) 动态分配：分配算法包括 First Fit（最佳）、Next Fit、Best Fit（最多的外部碎片）、Worst Fit（可能会导致大进程无法分配）、Buddy System（索引分配算法，规定分配的内存大小为 \(2^k\)。分配时，在对应大小的分配链表中查找，如果没有，则拆分一个大一级的块。回收时，按条件合并）

分页、分段

(1) 分页：将内存按固定大小划分为若干页。进程需要的每一页被映射到一块内存中，映射关系由页表维护。

三段页表的地址转换、TLB。

(2) 分段：将内存按逻辑划分为若干段。每个段有自己的段表，段表中的每一项描述了一个段的起始地址和长度（段长是不固定的）

(3) 混合型

虚拟内存管理

(1) 页面分配策略：

a. 固定分配局部置换：为每一个进程分配一定数目的物理块，每个进程只能在自己的物理块中置换

b. 可变分配全局置换：每个进程可以置换的物理块数量可变

c. 可变分配局部置换：为每一个进程分配一定数目的物理块，每个进程只能在自己的物理块中置换，除非其一直触发缺页中断，则将分配给它的物理块数量增加

(2) 页面置换算法：

a. 理想型：OPT，作为评价标准

b. 先进先出：FIFO，可能导致 Belady 异常（页面数增加时，缺页次数反而增加）

c. 最近最少使用：LRU

d. 时钟置换：LRU + 每一个页面存在一个访问位（复活卡），当访问位为 1，将其置为 0，当访问位为 0 时，将其替换。如果扫描到最后一个帧时，仍然没有找到可替换的页面，则从头开始扫描。当每一帧被装入内存或被访问时，将其访问位置为 1。

e. 改进型时钟置换：添加访问位和修改位，按下表进行替换：

访问位	修改位	描述
0	0	最近未访问，未修改，优先替换
0	1	最近未访问，已修改，次优先替换
1	0	最近访问，未修改，次次优先替换
1	1	最近访问，已修改，最后替换

抖动、驻留集、工作集

(1) 抖动：当内存不足时，频繁地进行页面置换，导致性能下降。

(2) 驻留集：进程当前正在使用的页面集合。

(3) 工作集：进程在 \(t_0\) 到 \(t_0 + \Delta t\) 时间段访问的页面集合。

驻留集小于工作集，发生缺页异常。

第四章 文件系统

文件索引

概念：目录项（即 FCB，文件控制块，与文件一一对应）、索引节点（UNIX 文件系统，将文件的元数据与文件名分开存储，索引节点存放文件的元数据，而文件目录项存放文件名和索引节点的指针）

(1) 文件的物理结构分配

a. 连续分配：每一个文件在物理上占据连续的块

b. 链接分配：显式（在 FAT 表中查询每一个盘块的下一块，文件目录只含有指向第一个物理块的链接）、隐式（在硬盘块中索引下一个块，文件目录只含有指向第一个物理块的链接）

c. 索引分配：单级索引（文件目录中含有索引块的链接，索引块中存放文件所在盘号）、多级索引（索引表的索引表）、混合索引（UNIX 文件系统，10 个直接块，一、二、三级间接索引各一个块）。计算最大文件大小。

文件目录

本质是为了实现按名存取，FCB 之间的组织问题。要区别于平时所讲的目录。

(1) 文件目录的实现：文件名与 FCB 之间的映射。文件名和索引节点的指针组成一个文件目录项。

每一个目录对应着一个目录文件，每一个目录文件维护了该目录下的文件目录项（其中包括文件名和用于索引的成员，例如索引节点的指针）。

(2) 文件共享

a. 软链接（符号链接）：本质是一个文件目录项，指向一个新的索引节点，这个索引节点指向 link 文件，这个文件中包含目标文件的路径。

b. 硬链接：本质是一个文件目录项，直接指向目标文件的索引节点，使得其中的引用计数加一。

磁盘空间管理

(1) 空闲表法

序号	第一个空闲块号	空闲块数
0	3	2
1	7	3
2	12	4

分配：类似于内存的动态分配，首次适应、最佳适应、最坏适应、...

(2) 空闲链表法

在每一个盘块中，存放下一个空闲盘块的指针。

(3) 位示图法

用二进制的 0 和 1 表示空闲和占用。一个 \(n\times m\) 的位示图可以表示 \(n\times m\) 个盘块。

(3) 成组链接法

将盘块分组。每组的第一个盘块记录下一个组的空闲盘块总数和空闲盘块号。每一组之间链接起来。

操作系统维护空闲盘号栈，用于维护第一组的空闲盘块总数和空闲盘块号。

第五章 I/O 系统

• 操作系统
• 通道 1
  • 控制器 1
    • 设备 1
    • 设备 2
  • 控制器 2
    • ...
• 通道 2
  • ...

为进程分配设备：从叶节点到根节点，访问设备控制表（DCT）、控制器控制表（COCT）、通道控制表（CHCT），确认可以分配后，添加到系统设备表（SDT）中。

I/O 控制方式

(1) 程序直接控制：CPU 对 I/O 设备轮询

(2) 中断驱动

(3) DMA：通过 DMA 控制器，按块传送数据，直接送入内存，仅在开始和结束时使用中断通知 CPU。用 DMA 控制器内部的寄存器控制传送状态。

I/O Hierachy

以下列表自高到低：

(1) 用户程序：通过系统调用访问 I/O 设备

(2) 设备无关程序：缓冲、设备分配、操作翻译

(3) 设备驱动程序：控制设备

(4) 中断处理程序：保存断点、上下文切换、获取 I/O 给出的数据、中断返回

(5) 硬件控制器：控制设备

逻辑设备

(1) SPOOLing：共享独占设备，同时能够实现缓和 CPU 和 I/O 设备之间的速度差异，在存储器中划出一部份区域作为输入/输出井，作为预输入和预输出的缓冲区。

磁盘调度

(1) 机械磁盘地址结构

磁道号	磁头号	扇区号
第几柱面	第几盘面	第几扇区

主要耗时：定位柱面（寻道过程）

(2) 磁盘调度算法：目标是减少寻道时间

a. 先来先服务 FCFS：按照请求的顺序进行调度

b. 最短寻道时间优先 SSTF：选择离当前磁头最近的请求

c. 电梯算法 SCAN：电梯，双向，每次必须到最大/最小磁道号

d. 循环扫描算法 C-SCAN：电梯，单向，每次必须到最大/最小磁道号

e. LOOK 算法：电梯，双向，每次只会扫到请求中的最大/最小磁道号，然后返回

f. C-LOOK 算法：电梯，单向，每次只会扫到请求中的最大/最小磁道号，然后返回

(3) 提升磁盘 I/O：寻道算法、延迟写提前读、高速缓存、物理分布优化

(4) 磁盘格式化：低级格式化（磁道、扇区标记）、高级格式化（文件系统）