跳转至

操作系统

研究生入学考试，全国统考计算机学科基础，其之三，操作系统。

第一章 操作系统概述

系统调用

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) 饥饿现象：某些进程长时间得不到调度。

(5) 对称多处理器（SMP）中的线程调度问题：我们希望一个线程始终在同一个处理器核心上工作，以最大化利用处理器提供的高速缓存等特性，这被称作处理器亲和性。同时我们希望能够让各个处理器核心的工作负载均衡。因此线程就绪队列有以下实现：

公共就绪队列：所有空闲的核心从一个公共的队列中取出进程，能够实现负载均衡，但不能实现处理器亲和性。

私有就绪队列：每个核心有自己的就绪队列，能够实现处理器亲和性，但不能实现负载均衡，这种情况下，引入推拉迁移，即使用某个程序定期检查各个核心的负载，调整各个核心的就绪队列。

进程同步

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

同步：时序上的约束关系，例如 A 必须要等待 B 完成后才能开始。

互斥：空间上的约束关系，资源 R 同时只能被一人访问。

(2) 互斥锁的软件实现：Peterson 算法，其核心思想是，用全局变量 flags[] 表示各个进程对使用临界资源的意愿，用全局变量 turn 表示当前有权使用临界资源的进程。每个进程在使用临界资源之前，先标记自己的意愿，然后再将 turn 让与对方，如果此时对方仍然不使用临界资源，则自己占用临界资源。

互斥锁的硬件实现：关闭中断；使用原子指令 TestAndSet 设置互斥锁的值。

(3) 信号量 Semephore。进程间通信使用信号量。每个信号量都有一个值和一个等待队列。信号量拥有 P() 操作请求资源（消费），V() 操作释放资源（生产）。

信号量的值 S 代表某一资源的剩余数量，P() 操作使得如果 --S < 0 则将请求者挂起到等待队列中（代表没有资源可以分配了）；V() 操作使得如果 ++S <= 0 则从等待队列中唤醒一个请求者（S 值为负的时候，代表当前等待队列中的请求者数量）。

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

(4) 信号量的应用

a. 用于实现互斥锁

如果设置信号量的初始值为 1，那么此时这个信号量等价于一个互斥锁。

b. 用于实现同步

如果将同步关系画成一张有向图，每个节点代表一个操作，每条边代表操作的先后顺序，那么可以用信号量实现同步：每条边代表一个初始值为 0 的信号量，出边生产，入边消费。

c. 用于实现生产-消费问题

假设 A 向 buffer 生产数据，B 向 buffer 消费数据。

A 和 B 对 buffer 的访问是互斥的，需要一个互斥锁进行保护。

A 能够生产数据的前提条件是 buffer 中有空余的位置，需要用信号量 empty 记录这个同步关系，初始为 buffer.size()。

B 能够消费数据的前提条件是 buffer 中有东西可以取，需要用信号量 full 记录这个同步关系，初始值为 0。

每次生产 V(empty); P(full)，每次消费 V(full); P(empty)。

问题：先加互斥锁再判断生产/消费条件还是先判断条件再加锁？应该是先判断条件再加锁，以防止死锁的产生。

d. 用于实现读者-写者问题

要求实现读写、写写互斥，而读读不互斥。

使用互斥锁保护 buffer，对读者进行计数，当且仅当目前没有读者，这是第一个读者时，才申请互斥锁。计数器需要用一个额外的互斥锁保护。

升级：上面的方法会出现问题，如果有源源不断的读者，那么写者将无法进行写操作。解决方案在上面判断第一个读者并申请互斥锁的逻辑外再套一层互斥锁，只有当写者完成写后才能够进行读者可读判断，即对控制读写的互斥锁来说，写有更高的申请优先级。

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（可能会导致大进程无法分配）

(4) 动态分配中的索引分配：如何组织动态分配中的可分配内存链表。包括按长度为界限分成多个链表、、Buddy System（规定所有的可供分配的内存大小为 \(2^k\)。分配时，在对应大小的分配链表中查找，如果没有，则拆分一个大一级的块。回收时，按条件合并）

分页、分段

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

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

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

(3) 段页式：逻辑地址分段，逻辑地址到物理地址的转换分页。每个进程有自己的段表。

虚拟内存管理

(1) 页面分配策略：

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

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

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

(2) 页面置换算法：

a. 理想型：OPT，选择在将来最长时间内不会被访问的页换出，作为评价标准

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

c. 最近最少使用：LRU

d. 时钟置换：CLOCK，丐版 LRU，只使用 1 位作为访问位 A。将所有页面使用循环链表链接，使用指针指向下一个换出的页。当页面被访问或换入时，置 A = 1。换出页面时，检查当前页是否满足 A == 0，若是，则换出，并令指针指向链表的下一个元素；若否，则置 A = 0，并令指针指向链表的下一个元素。

如果将循环链表画成一个圆圈，把指针放在圆圈的内部，改算法的执行过程就像是时钟的指针转动，故此得名。

e. 改进型时钟置换算法：添加一位修改位 M，希望优先换出未被访问的页，同时也希望优先换出未被修改的页（这样不需要写回外部存储器）。将所有页面使用循环链表链接，使用指针指向下一个换出的页。当页面被访问或换入时，置 A = 1，当页面被修改时，置 M = 1。换出页面时，执行以下两轮检定和一个递归条件：(i) 检查当前页是否满足 A == 0 && M == 0，若是，则换出，并令指针指向链表的下一个元素；若否，令指针指向链表的下一个元素，直至该检定对每个页面都执行过。(ii) 检查当前页是否满足 A == 0 && M == 1，若是，则换出，并令指针指向链表的下一个元素；若否，则置 A = 0，并令指针指向链表的下一个元素，直至该检定对每个页面都执行过。(iii) 回到 (i)。

抖动、驻留集、工作集

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

(2) 驻留集：操作系统能够分配给某个进程的页面数。

(3) 工作集：某一时刻 \(t\)，在时间区域 \([t - \Delta, t]\) 内进程需要访问的页面。

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

第四章 文件系统

文件

文件的构成：数据项构成记录，记录和元数据构成文件。操作系统通过文件控制块 FCB 管理文件。

将 FCB 组成的集合称为文件目录，文件目录中的每一项即 FCB 也被称为文件目录项。文件目录本身也是一个文件，即目录文件，打开文件时需要先将目录文件调入内存，然后再从中查找对应的 FCB。

即：FCB = 文件目录项；目录文件 = 文件目录 = FCB 的集合。

文件系统需要按名查找，而 FCB 中包含许多在查找时用不到的信息，它们让目录文件变得更大，从而降低了从目录文件中查找特定文件，因此，产生了分离 FCB 中的文件名和其他元数据的实现，将其他元数据包装为 inode，此时每个文件目录项的形式为 [file_name, inode_ptr]，这个时候，文件目录项就不再等于 FCB 了。

操作系统维护文件打开表，记录打开的文件的 FCB，打开表分为用户表和系统表。

(1) 文件的逻辑结构：指文件如何由若干记录组织起来。分为无结构文件（即流文件）、有结构文件。

有结构文件又可以根据记录是否定长划分。问题关注如何通过记录的下标 i 找到数据项的下标 index。定长划分时，直接乘积即可；不定长划分时，需要通过索引表等手段实现。此外还有使用哈希表的有结构文件。

(2) 文件的物理结构

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

b. 链接分配：使用链表连接文件在物理上占据的盘块。根据链表如何实现，可以进一步划分为隐式和显式链接分配。

隐式：FCB 只维护链表的首尾指针，每个盘块中包含指向下一个盘块的指针。

显示：操作系统维护文件分配表 FAT，表中有各个盘块的 next 指针数据，这样就不需要从盘块中找它的下一个盘块了，增加了鲁棒性。

c. 索引分配：用若干个盘块保存索引，每个索引指向文件占用的一个盘块。分为单级索引（FCB 中直接包含索引）、多级索引（FCB 中包含指向索引块的索引）、混合索引（UNIX 文件系统，10 个直接块，一、二、三级间接索引各一个块）。由于要求每一个索引块只能占用一个盘块，因此可以计算出某种索引分配方案中的最大文件大小限制。

(3) 文件共享

a. 硬链接：用多个不同的 FCB 指向同一个 inode，并在 inode 中维护引用计数，

b. 软链接（符号链接）：用多个不同的 FCB 指向多个不同的 FCB。共享出来的项（通过软链接创建的 FCB）指向另一个文件的 inode，这个文件作为链接文件，包含被共享文件的路径。通过间接访问来访问被共享文件。

目录

如何组织 FCB。分为单级目录结构（所有 FCB 在一个列表中，这个列表不允许重名）、两级目录结构（每个用户有自己的列表）、树形目录结构（例如 UNIX 系统）

磁盘空间管理

(1) 空闲表法

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

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

(2) 空闲链表法

将空闲的盘块串成链表，在每一个盘块中，存放下一个空闲盘块的指针。

或者以若干个盘块组成一个链表项，这种情况下需要实现分配算法（First Fit）、回收算法（合并可以合并的块）。

(3) 位示图法

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

(4) 成组链接法

将若干个空闲盘块合并为一组，每个组的第一个块用于指示组中可供使用的空闲盘块数，第二个块用于指示下一个组的位置。

分配和回收操作都是在第一个组上做的，将第一个组内的空闲盘块按栈的方式进行管理。此时这个组也可以称为空闲盘块栈。

分配时从栈中 pop，如果不够，则全部分配之后，删掉第一组，此时原先第二组成为第一组，在它的空闲盘块中 pop。

回收时向栈中 push，如果超出了组的容量，则新建一个组作为第一组，指向原先的第一组，向新建的组 push。

第五章 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：将低速 I/O 设备上的输入输出缓存到磁盘上。实现方式是在存储器中划出一部分区域作为 I/O 的输入/输出井，将不同进程对同一 I/O 设备的操作链接为一个输入或输出队列，使用专门的程序管理输入/输出井和 I/O 设备之间的数据交换。不同的进程只需要向输入/输出井进行读写操作即可，为了进一步加速，在内存中引入专用的缓冲区缓冲这个读写操作。

SPOOLing 实现了共享独占设备，并一定程度上能够向上层的进程屏蔽下层的 I/O 的低速，缓和 CPU 和 I/O 设备之间的速度差异。

磁盘调度

(1) 机械硬盘地址结构

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

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

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

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

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

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

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

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

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

(3) 提升磁盘 I/O：寻道算法、延迟写提前读、高速缓存、物理分布优化（对于机械硬盘，读写后需要一段时间处理，而这段时间内盘面仍然会旋转，这就导致逻辑上连续的数据如果物理上也连续，反而会带来更长的延迟）

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

(5) 机械硬盘读写耗时 = 寻道时间（找到柱面，磁头跨越磁道的耗时加上启动耗时）+ 旋转时间（找到扇区，盘面的平均旋转时间认为是旋转一周所需耗时的一半）+ 数据传输时间（与每个扇区能够保存的字节数、转速有关）