操作系统

发表于 2025-06-07 分类于课程笔记本文字数： 4.2k

#前言

还没写完！进度：往年题整理（0/7）

往年题整理的部分可能会往后拖，原因如下：

Xi’En: 06-10 21:51:36
感觉我没做往年题是不是赢了

本文分为以下两部分：

课程复习笔记
- 考虑篇幅和效率原因，我们不使用本课程的教学资料进行复习
  
  PPT 总字数约为 $10^5$ 量级……
- 复习部分采用蜂考《〈操作系统〉17小时系统学习》课程讲义
  - 此处只保留笔记部分，阅读时请参考讲义进行（密码 velkhana）
  - 个人实践，仅供参考。若希望获得更贴切的复习思路，可以阅读课程复习 PPT
往年题整理
- 在这一部分，我们会按照课程 PPT 的目录结构整理所有往年题目
  注意：一定要自己做一遍慕课题目！其实很重要，这里不放只是博主有点懒
  往年题目来源如下：
  - 2013年 (2013.pdf)
  - 2014年 (2014样卷.pdf)
  - 2016年 (2016卷A（空白）.pdf)
  - 2019年 (2019操作系统试卷回忆.pdf)
  - 2020年 (2020年期末卷回忆.pdf)
  - 2021年 (2021考试回忆.md)
  - 2022年 (2022回忆 (1).pdf)

致谢：

感谢好哥哥电报提供的复习资料！
感谢好兄弟CuWO4提供的往年题！

#第一部分课程预习

#课时一操作系统引论

#1.1 操作系统的概念及特征

区分并发和并行：

并发是快速交替地进行了操作
并行是同时进行了操作

#1.2 操作系统的功能和接口

区分命令接口和程序接口的关系：

命令接口是用户直接与操作系统交互的方式；
- 包含 CLI/GUI 等。对应地举两个例子：在终端输入指令、使用资源管理器的图形界面拖放文件
- 需要注意：操作系统提供的图形化界面也是操作系统的一部分（即上一条第二个例子）
程序接口是程序与操作系统交互的形式
- 是一批系统调用的统称

假如用户写了一段 C 代码，代码中调用 getchar() 时：

getchar() 是 glibc 提供的函数，底层使用含缓冲的 read() 实现
read() 在缓冲区为空时会触发系统调用，触发时先设置调用号等参数，再 int 0x80 或 syscall
此时（对应调用号的）系统调用是一段程序，从寄存器中获取参数并进行 IO 操作

前两点都属于用户程序，第三点才是系统调用，才属于程序接口

#1.3 操作系统的发展过程

按同时运行的任务数量分：单道程序系统/多道程序系统
多道程序系统需要使用中断，会带来进程切换的开销

按时间分：

批处理系统：批处理，不能交互
分时系统：一台主机通过采用时间片轮转方式允许多个用户同时使用
实时系统：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理

#1.4 操作系统的运行环境

关于“管态”“目态”的神秘命名可以看 https://www.zhihu.com/question/395146934

用户态通过中断进入内核态，内核态通过执行一个特权指令将程序状态字 PSW 的标志位设为“用户态”来进入用户态

内中断的信号来源与当前执行的指令有关（trap、缺页、整数除零），外中断反之（IO设备中断，kill）

#1.ex 练习题

计算机开机后如何加载操作系统：

开机后执行存储在 ROM/EPROM 中的 BIOS 程序
- BIOS：Basic In/Out System，一个程序，负责遍历并检查是否有可引导的设备
如果找到引导设备，则把引导程序（Boot Loader）加载到 RAM 中并执行
引导程序将内核及必要的系统文件加载到 RAM 中
引导程序将控制权交给操作系统，操作系统启动

DOS：Disk Operating System，单用户单任务

进程调度可以不需要（专用的）硬件支持，始终管理、地址映射、中断都需要

#课时二进程的描述与控制

#2.1 进程的概念

无

#2.2 进程的状态与转换

重点关注进程的状态转换图，后面会有新的内容

#2.3 进程通信

无

#2.4 线程的概念

分配资源的单位是进程，运行的单位是线程

线程有 KLT ULT 两种，贴一个 gemini 整理的表：

特性	用户级线程 (ULT)	系统级线程 (KLT)
管理方	用户空间线程库	操作系统内核
内核可见性	不可见（内核只看到进程）	可见（内核知道每个线程）
创建/销毁/切换	快（用户态操作）	慢（需要陷入内核）
阻塞问题	单个线程阻塞导致整个进程阻塞	单个线程阻塞不影响其他线程
多核利用	无法并行利用多核CPU	可以并行利用多核CPU
开销	小	大
典型示例	Old versions of Pthreads, Java’s green threads	Linux Pthreads (NPTL), Windows threads

#2.ex 练习题

线程之间只共享进程共有的资源和变量，可以拥有自己的资源和变量

#课时三处理机调度（一）

#3.1 处理机调度的基本概念

系统调用返回时可以进行调度：返回之前在内核态，适合评估；返回前评估一下是否有抢占之类

用户登录会产生新进程、阻塞的进程变为就绪，都可能导致进程调度

#3.2 三种简单的调度算法

FCFS 对 IO 密集型任务不友好，因为经常被踢到队尾

SJF 有最短的平均周转时间

#3.ex 练习题

无

#课时四处理机调度（二）

#4.1 时间片轮转算法 RR（Round-Robin）

无

#4.2 高相应比优先算法 HRRN（Highest Response Ratio Next）

也就是说：求一下如果现在执行，执行结束时这个程序一共等了几倍于它自己的时间，选比例最大的

#4.3 多级反馈队列调度算法 MLFQ（Multi-Level Feedback Queue）

注意葛季栋的多级反馈队列不太相同：程序被抢占时会执行完当前时间片再被剥夺

#4.ex 练习题

优先级有抢占和不抢占的两种不同实现

#课时五死锁（一）

#5.1 死锁的概念

无

#5.2 死锁预防

区分预防和避免：

预防：破坏四个必要条件之一
避免：状态转移时，防止进入可能发生死锁的状态

#5.ex 练习题

死锁定理：检测方法，先找到所有进程及其需要的资源（包括已占有的），然后尝试获得资源并消除，如果消完了就没有死锁，否则没消掉的部分会发生死锁

#课时六死锁（二）

#6.1 死锁的避免

快速了解银行家算法：

先定义“安全序列”：按照这个序列让每个进程依次进行 a.获取最大资源量 b.运行 c.释放资源，可以让全部进程运行完成
（为什么要记录最大资源量？因为我们希望确保某个进程可以被完成，才能得到安全序列。如果没有最大值限制，任何一个进程都可能一直请求资源，于是不能保证任何进程可以被执行完成。）
每次分配资源时，先尝试分配，并检查是否存在“安全序列”，如果不存在则把这个分配请求扔到队列里等着

#6.2 死锁的检测与消除

关注资源分配图的画法及对应的意义，死锁定理的内容在上一课时提到了

#6.ex 练习题

资源分配图成（有向）环不一定是死锁，但如果每种资源只有一个就是（想一想为什么）

发生死锁时一定有循环等待，但是发生循环等待时未必死锁。从必要条件的角度分析并举例：

不可剥夺：抢占
持有并等待：某个进程一段时间后释放自己所持有资源

#课时七进程同步（一）

#7.1 同步与互斥的基本概念

注意区分临界资源和临界区，以及同步机制的准则。

#7.2 软件同步机制

快速了解 Peterson 算法：

解决两个进程希望访问同一个临界资源的问题，避免无限等待
公有变量 int turn 表示现在轮到谁进入，bool flag[2] 表示第 i 个进程是否想要访问临界资源
执行时，先设置自己的 flag 为 true 宣称自己想要访问，再将 turn 设为对方
然后，如果轮到对方访问且对方想要访问，则等待
等待结束后进行访问，访问结束后将自己的 flag 设为 false

保证了有限等待，不会出现饥饿现象，因为比自己晚来的进程会把资源让给自己。

#7.3 硬件同步机制

无

#7.ex 练习题

正在访问临界资源的进程在被中断时，仍然不允许其他进程进入它占有的临界区。

#课时八进程同步（二）

#8.1 信号量

记录型信号量除了能避免忙等待，还可以保证 wait 的一致性

#8.2 信号量的基本应用

无

#8.3 管程

讲义上没有所以写一下：

管程与 PV 操作相比，管程是把临界资源、信号量、处理方法等封装成了一个统一的模型，只暴露一些外部接口用于业务操作

管程是一套完备的接口和具体实现的封装，它是一段代码，可以被单独编译（需要连接）

一个业务线程在调用管程方法时，如果不满足条件则会阻塞。当另一线程执行管程方法完毕并归还信号量时，信号量会通知这个阻塞的线程恢复执行

管程的信号量除了业务需要的，还有一个避免竞态的（即同时只能有一个线程正在执行管程部分的代码）

需要关注一下管程的写法（格式），因为会考

#8.ex 练习题

互斥使用缓冲区，即使容量很大，一次也只能有一个读/写

#课时九进程同步（三）

#9.1 生产者消费者问题

一个有上下界的、支持一次性放入或取出若干个元素的容器（为什么这么设计？）

semaphore mutex_put = 1;
semaphore mutex_get = 1;
semaphore empty = SIZE;
semaphore count = 0;

semaphore mutex_buf = 1;
int buf[SIZE];

put(int c) {
  P(mutex_put);
  for (int i = 0; i < c; i++) {
    P(empty);
    P(mutex_buf);
    // put an element
    V(mutex_buf);
    V(count);
  }
  V(mutex_put);
}

get(int c) {
  P(mutex_get);
  for (int i = 0; i < c; i++) {
    P(count);
    P(mutex_buf);
    // get an element
    V(mutex_buf);
    V(empty);
  }
  V(mutex_get);
}

#9.2 读者写者问题

使用信号量互斥读写一个共享的变量是一个很有用的 trick

#9.3 哲学家进餐问题

举了一个会出现死锁的情景。三种解决办法：

至多四个人拿筷子
将整个拿筷子过程变为原子的
按奇偶确定先拿哪个方向的筷子

#9.ex 练习题

困死了，没有做

#课时十内存管理（一）

#10.1 内存管理的基本原理和要求

无

#10.2 覆盖与交换

关注进程状态转换图

PCB 不会被换出外存

#10.ex 练习题

无

#课时十一内存管理（二）

#11.1 连续分配管理

关注内部碎片和外部碎片的定义，以及分配方式是否会导致这两种碎片

#11.2 动态分区管理

同上

#11.ex 练习题

动态可重定位：例如虚拟内存。物理上的一个块的虚拟地址可以改变

#课时十二内存管理（三）

#12.1 分页存储管理方式

快表就是个副本而已

#12.2 分段存储管理方式

分段式：程序分成不定长的几个段，在内存里分配完整的段

#12.3 段页式管理方式

段页式：分段后，把段用页面形式分配。每个段有自己的页表

#12.ex 练习题

没有做

#课时十三虚拟内存管理

#13.1 虚拟内存的基本概念

关注若干性质、特征等

多次性：分多次装入
对换性：不用的可以换下来
虚拟性：分配的地址空间大于物理地址空间
离散性：在物理上不连续

页面是虚拟内存上的概念，页框是物理内存上的概念，页表是页面到页框的对应

和上一章一样都有分段、分页、段页。需要硬件支持。

#13.2 页面置换算法

FIFO 算法会出现 Belady 异常：分配给进程的物理块增多，但缺页次数不减反增

举一个例子：3 2 1 0 3 2 4 3 2 1 0 4 在四个块的时候缺页 10 次，三个块的时候缺页 9 次

TODO：研究一下如何构造一个例子

#13.3 页面分配策略

有很多概念需要看一看

#13.ex 练习题

无

#课时十四文件管理（一）

#14.1 文件逻辑结构

注意逻辑结构和实际存储方式是独立的

#14.2 文件目录

无

#14.3 文件共享

硬链接与软链接

#14.4 文件保护

无

#14.ex 练习题

read 系统调用需要的是文件描述符，需要通过 open 系统调用打开文件得到

#课时十五文件管理（二）

#15.1 文件的物理结构

注意不同点：

显式链接分配：文件系统管理所有文件的所有块，包括已经在用的和空闲的。一个磁盘会建立一个文件分配表（FAT）
索引分配：文件系统管理所有文件，文件自行管理自己的块。一个文件建立一个索引表

#15.2 文件存储空间管理

空闲表法：类似分段式内存分配
空闲链表法：以盘块为单位的分配
位示图法：直接维护所有块是否空闲，每次顺序寻找。存储的时候把若干个 bool 压到一个 byte 里面
成组链接法：没看

#15.ex 练习题

链式结构+磁盘块定长可以支持文件的扩展。一般来说磁盘块都是一样长（定长）的

文件索引节点分配块的时候，类似于 {直接: 1} {直接: 1} {直接: 1} {直接: 1} {一级: 2^10} {一级: 2^10} {二级: 2^20}，前面不够用了就启用后面的。启用的是一个前缀，所以容量为总和

需要注意是否考虑间接块的大小；需要关注索引节点是否已经读入内存

#课时十六文件管理（三）

#16.1 文件的基本操作

关注这里的“打开”操作，之前提到过

#16.2 文件系统的层次结构

无

#16.ex 练习题

区分“文件目录”（目录项，inode/FCB）和“目录文件”（directory）

#课时十七磁盘的组织与管理

#17.1 磁盘

无

#17.2 磁盘调度算法

无（计组学过了）

#17.3 磁盘的管理

关注这里的一些概念

#17.ex 练习题

没有做！

#课时十八 I/O 设备管理（一）

#18.1 I/O 设备的基本概念和分类

无

#18.2 I/O 控制方式

中断和 DMA 的区别：

中断：
- I/O Device：INT …
DMA：
- I/O Device：DMA
- CPU：控制权交给 DMA 控制器
- DMA 控制器：处理整块数据（例如写入内存）后发出中断归还控制权

DMA 控制器里面的寄存器：

CR 命令/状态
MAR 内存地址
DR 数据
DC 数据计数（长度）

还要注意一下通道这种更高级的方式

#18.ex 练习题

无

#课时十九 I/O 设备管理（二）

#19.1 I/O 软件层次结构

往年考过，需要仔细了解

#19.2 I/O 子系统概述

需要注意高速缓存和缓冲区的区别

#19.ex 练习题

无

#课时二十 I/O 设备管理（三）

#20.1 设备分配与回收

DCT（Device Control Table）设备控制表
CHCT（CHannel Control Table）通道控制表
COCT（Controller Control Table）控制器控制表
SDT（System Device Table）系统设备表

DCT 管理具体设备，CHCT 管理通道

对设备的访问需要经过通道。控制器即为具体设备寻求通道为其服务的抽象，所以 DCT COCT 一对一，COCT CHCT 多对一

#20.2 SPOOLing 技术

需要关注 SPOOLing 系统的原理图

注意缓冲区只是用来联通内存与硬盘、硬盘与设备的

#20.ex 练习题

无

#第二部分往年题整理

TODO

#前言

#第一部分 课程预习

#课时一 操作系统引论