操作系统考点总结

覆盖章节：Chp1 操作系统引论 | Chp2 进程的描述与控制 | Chp3 处理机调度与死锁

📗 第一章操作系统引论

1. 操作系统的目标与作用 ⭐

目标	说明
有效性	提高资源利用率和系统吞吐量
方便性	使计算机系统更易使用
可扩充性	采用新结构，易于增删改功能
开放性	统一开放环境，跨平台互通

OS的三重作用：

用户与硬件之间的接口（命令方式、系统调用方式、图形窗口方式）
计算机系统的资源管理者（处理机、存储器、I/O设备、文件）
对计算机资源的抽象（裸机 → 虚机器/扩充机器）

2. OS的发展过程 ⭐⭐

阶段	特征	缺点/优点
人工操作	单用户单任务，CPU等人	人机矛盾，浪费CPU
单道批处理	监督程序，自动顺序处理	CPU仍等待I/O
多道批处理	多道并发，引入进程调度	平均周转时间长，交互性差
分时系统	时间片轮转，多终端交互	响应及时，交互性强
实时系统	任务在截止时间内完成	可靠性高，实时性强

多道批处理特征： 多道性、无序性、调度性
分时系统特征： 多路性、交互性、独立性、及时性
实时系统分类： 硬实时任务(HRT)、软实时任务(SRT)
实时 vs 分时： 实时可靠性>分时；交互性：分时>实时

3. OS的四大基本特征 ⭐⭐⭐

特征	说明	关键点
并发性	多事件在同一时间间隔内发生（宏观并行，微观交替）	是最基本特征，其他特征以并发为前提
共享性	互斥共享（临界资源）+ 同时访问（磁盘等）	并发与共享互为存在条件
虚拟性	时分复用技术（虚拟处理机）；空分复用技术	提高资源利用率
异步性	进程以不可预知的速度推进	每次执行结果应可再现

⚠️ 并行 vs 并发：并行 = 同一时刻；并发 = 同一时间间隔

4. OS的主要功能 ⭐⭐

功能	主要内容
处理机管理	进程控制、进程调度、进程同步、进程通信
存储管理	存储分配与回收、存储保护、地址映射、内存扩充
设备管理	缓冲管理、设备分配、设备处理
文件管理	存储空间管理、目录管理、文件读写管理与保护
用户接口	联机接口（命令行）、脱机接口（JCL）、图形接口

程序接口（系统调用） = 用户程序取得OS服务的唯一途径

5. OS的结构设计 ⭐

结构类型	特点
无结构OS	编码紧凑，维护难
模块化OS	模块-接口法，可并行开发；接口难确定，依赖关系复杂
分层式OS	单向依赖，易正确性保证；通信开销大，效率降低
微内核OS	内核只保留最基本功能；客户-服务器模式；可扩充性、可靠性、可移植性强；但多次上下文切换，运行效率降低

微内核基本功能： 进程/线程管理、低级存储器管理、中断和陷入处理

📘 第二章进程的描述与控制

1. 前趋图 ⭐

前趋图(DAG，有向无环图)，描述进程执行的先后顺序
结点 = 进程/程序段；有向边 = 前趋关系
前趋图中不允许有循环！

程序顺序执行特征： 顺序性、封闭性、可再现性
程序并发执行特征： 间断性、失去封闭性、不可再现性

2. 进程的定义与特征 ⭐⭐⭐

进程的定义：

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立基本单位。

进程实体 = 程序段 + 数据段 + PCB

进程的四大特征：

特征	说明
动态性	进程有生命期（创建→调度→撤销），最基本特征
并发性	多进程同时驻留内存，并发执行
独立性	独立运行、获得资源、接受调度的基本单位
异步性	各进程以不可预知速度推进

程序 vs 进程：

程序是静态的，进程是动态的
程序可长期保存；进程有生命周期
一个程序可对应多个进程；一个进程可包含多个程序

3. 进程的状态与转换 ⭐⭐⭐

三种基本状态：

就绪态：已分配除CPU外所有资源，等待CPU
执行态：正在CPU上运行（单处理机只有一个）
阻塞态：因等待事件无法继续执行，让出CPU

五状态模型（加入创建态和终止态）：

1
2
3

新建 → 就绪 ←→ 执行 → 终止
              ↓↑
            阻塞

状态转换：

就绪→执行：调度程序分配CPU
执行→就绪：时间片到，被抢占
执行→阻塞：等待事件（I/O等）
阻塞→就绪：等待事件完成

4. 进程控制块 PCB ⭐⭐

PCB是进程在系统中存在的唯一标志，包含：

进程标识符（PID）
处理机状态（寄存器内容）
进程调度信息（优先级、状态）
进程控制信息（程序地址、资源清单）

进程控制的原语：

进程创建原语：申请空白PCB → 填写信息 → 分配资源 → 插入就绪队列
进程终止原语：清空PCB → 回收资源
进程阻塞原语(block)：执行态 → 阻塞态
进程唤醒原语(wakeup)：阻塞态 → 就绪态

5. 进程同步 ⭐⭐⭐

核心概念：

临界资源：一次仅允许一个进程访问的资源（互斥共享）
临界区：访问临界资源的代码段
同步机制四准则： 空闲让进、忙则等待、有限等待、让权等待

整型信号量 vs 记录型信号量：

	整型信号量	记录型信号量
特点	P操作忙等	不满足”让权等待”
P(S)	while(S≤0); S–	S–; if(S<0) block(S.list)
V(S)	S++	S++; if(S≤0) wakeup(S.list)

信号量含义：

S > 0：有 S 个可用资源
S = 0：无可用资源，无等待进程
S < 0：|S| 个进程在阻塞队列中等待

6. 信号量的应用 ⭐⭐⭐

互斥： mutex 初值通常为 1，P在临界区前，V在临界区后，成对出现
同步： 同步信号量初值通常为 0，一进程V（发信号），另一进程P（等信号）

⚠️ 关键规则：当P操作中既有同步P又有互斥P时，同步P必须在互斥P前面！

AND型信号量： 一次性申请所有资源，要么全分配要么全不分配，避免死锁

7. 经典同步问题 ⭐⭐⭐

生产者-消费者问题

信号量：
  Buffers = N    // 缓冲区空闲容量（同步）
  Products = 0   // 产品数量（同步）
  mutex = 1      // 互斥访问缓冲区

生产者：P(Buffers) → P(mutex) → 放产品 → V(mutex) → V(Products)
消费者：P(Products) → P(mutex) → 取产品 → V(mutex) → V(Buffers)

⚠️ P(Buffers)和P(mutex)不能交换顺序（会死锁）

读者-写者问题（读者优先）

int count = 0           // 正在读的读者数
semCount = 1            // 互斥访问count
semWrite = 1            // 互斥访问共享数据区

读者：P(semCount) → (count==0?P(semWrite)) → ++count → V(semCount) → 读 → P(semCount) → --count → (count==0?V(semWrite)) → V(semCount)
写者：P(semWrite) → 写 → V(semWrite)

哲学家就餐问题

死锁成因： 5人同时各拿左边筷子，均等右边筷子 → 循环等待死锁
解决方案：

最多允许4人同时吃（至少1人能拿到两根筷子）
奇数号先取左边，偶数号先取右边
AND型信号量（推荐）：一次性申请两根筷子

8. 管程 ⭐

管程：共享资源的数据结构 + 对其操作的一组过程构成的资源管理模块
特征： 模块化、抽象数据类型、信息封装、互斥性（任一时刻只有一个进程进入管程）
条件变量： x.wait()（阻塞调用进程并释放管程）；x.signal()（唤醒阻塞在x上的进程）
优点： 将同步机制集中在管程内，不分散；正确性更易验证

9. 进程通信 ⭐⭐

类型	方式	特点
低级通信	信号量机制	速度快，传送量小，不透明
共享存储器（高级）	申请共享内存区	高效，速度快
管道通信	pipe文件	单向，读写互斥，需同步
消息传递	直接通信/信箱通信	最广泛，透明，格式化消息
客户-服务器	套接字、RPC	网络环境主流

10. 线程 ⭐⭐

引入线程的原因： 将进程的”拥有资源”和”调度执行”两个属性分开，减少并发执行的时空开销

对比项	进程	线程
调度单位	无线程时是调度基本单位	引入线程后是调度基本单位
资源	拥有资源的独立单位	几乎不拥有资源，共享进程资源
独立性	进程间独立性高	同进程内线程独立性低
系统开销	创建/撤销/切换开销大	开销远小于进程

线程实现方式：

用户级线程(ULT)： 管理在用户空间，内核不知道其存在；切换无需内核；一个线程阻塞导致整个进程阻塞
内核支持线程(KST)： 内核管理；一个线程阻塞不影响其他线程；用户态-内核态切换开销大
组合方式： 多对一、一对一、多对多（推荐，兼顾两者优点）

📙 第三章处理机调度与死锁

1. 调度层次 ⭐⭐

层次	别名	对象	频率	应用
高级调度	作业调度/长程调度	作业（外存→内存）	几分钟一次	多道批处理
中级调度	内存调度/中程调度	进程（换入/换出）	取决于内存	存储器管理
低级调度	进程调度/短程调度	进程（就绪队列→CPU）	10~100ms	所有OS

进程调度是最基本的调度，运行频率最高，算法不宜复杂

2. 调度算法 ⭐⭐⭐

先来先服务 FCFS

按到达顺序调度
有利于长作业/CPU繁忙型，不利于短作业
简单，效率不高

短作业优先 SJF/SPF

选CPU时间最短的作业/进程
比FCFS改善了平均周转时间和吞吐量
缺点：长作业可能饥饿；需预知执行时间

高响应比优先 HRRN ⭐⭐

$$
R_p = \frac{等待时间 + 服务时间}{服务时间} = 1 + \frac{等待时间}{服务时间}
$$

折中算法：既照顾短作业又不让长作业无限等待
每次调度前计算响应比，增加系统开销

优先级调度 PSA

静态优先级：进程创建时确定，不变；简单，低优先级进程可能饥饿
动态优先级：随运行动态调整（如占用CPU越长降优先级）

时间片轮转 RR ⭐⭐

所有就绪进程按FCFS排队，逐个分配时间片
时间片太小：切换频繁，开销大
时间片太大：退化为FCFS
时间片选取：略大于一次典型交互所需的时间

多级反馈队列 MFQ ⭐⭐

设多个优先级依次降低的就绪队列，优先级越高时间片越小
新进程进第1队列（FCFS），时间片内未完成降入下一队列
最低级队列采用RR
高优先级队列有进程时，立即抢占低优先级队列的运行进程
优点： 不需预知执行时间，满足多种类型进程需要

3. 调度算法性能指标 ⭐⭐

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

$$
带权周转时间 = \frac{周转时间}{服务时间}
$$

$$
平均周转时间 = \frac{\sum 周转时间}{n}
$$

4. 进程调度方式 ⭐

方式	说明	适用
非抢占方式	进程运行直到完成或阻塞才放弃CPU	批处理系统
抢占方式	根据某种原则强行剥夺CPU分配给其他进程	分时、实时系统

5. 死锁概述 ⭐⭐⭐

死锁定义：

若一组进程中的每一个进程都在等待仅由该组内的其他进程才能引发的事件，则称该组进程是死锁的。

产生死锁的原因：

竞争不可抢占性资源（数量不足）
竞争可消耗性资源（通信消息）
进程推进顺序不当

产生死锁的四个必要条件 ⭐⭐⭐：

条件	说明
互斥条件	资源被排他性使用
请求和保持条件	占有资源的同时请求被其他进程占有的资源
不可抢占条件	资源只能由进程自主释放，不可被强行夺走
循环等待条件	存在进程-资源的循环等待链

四个条件同时成立才会产生死锁

6. 预防死锁 ⭐⭐

通过破坏必要条件中的一个或多个（互斥条件是固有属性，不能破坏）：

破坏的条件	方法	优缺点
破坏请求和保持	①全部资源一次分配；②获得部分后，需新资源时先释放已有资源	简单安全但资源浪费，易饥饿
破坏不可抢占	申请资源未满足时，释放已占资源	实现复杂，代价大，可能使前段工作失效
破坏循环等待	有序资源分配法（按序号递增申请）	利用率有改善；新增资源不便，编程不自由

7. 避免死锁——银行家算法 ⭐⭐⭐

核心思想： 动态分配资源时，先判断分配后系统是否仍处于安全状态，若安全则分配，否则等待。

安全状态： 系统能找到某种进程推进顺序（安全序列），使每个进程都能顺利完成。

数据结构（设n个进程，m类资源）：

数据结构	含义
`Available[m]`	各类可用资源数
`Max[n][m]`	各进程的最大需求
`Allocation[n][m]`	各进程已分配量
`Need[n][m]`	各进程还需要量

关系： Need[i][j] = Max[i][j] - Allocation[i][j]

银行家算法流程（进程Pi请求Request[i]）：

Request[i] ≤ Need[i]，否则出错
Request[i] ≤ Available，否则等待
假设分配（修改Available、Allocation、Need）
运行安全性算法检查是否安全
安全则真正分配；否则撤销假设，Pi等待

安全性算法：

Work = Available，Finish[i] = false
找满足 Finish[i]=false 且 Need[i]≤Work 的进程i
令 Work = Work + Allocation[i]，Finish[i] = true
重复直到所有进程 Finish[i]=true（安全）或找不到（不安全）

8. 死锁的检测与解除 ⭐⭐

死锁检测工具： 资源分配图

死锁定理： 系统处于死锁状态 ⟺ 资源分配图不可完全简化

简化步骤：

找到一个既非阻塞（能获得所需资源）又非孤立的进程结点
模拟其获得资源运行完毕，消去其请求边和分配边（成为孤立结点）
重复以上步骤，若能消去所有边则可完全简化（无死锁）

死锁解除方法：

结束所有进程，重启OS（简单但损失大）
抢占足够资源给死锁进程
终止所有死锁进程
逐个终止死锁进程，逐步回收资源（最常用）

9. 处理死锁方法对比 ⭐

方法	防范程度	资源利用率	进程阻塞频度
预防	最强	最低	高
避免（银行家）	较强	较高	较低
检测与解除	最弱	最高	最低

📝 重点题型总结

计算题：调度算法（作业周转时间）

步骤： 列表 → 按算法排调度顺序 → 计算开始/完成时间 → 计算周转时间 → 计算带权周转时间

计算题：银行家算法

步骤： 写出Available/Max/Allocation → 计算Need → 检查请求合法性 → 假设分配 → 安全性算法找安全序列

问答题：死锁四个必要条件

记忆：互请不循（互斥、请求与保持、不可抢占、循环等待）

问答题：P/V操作实现同步互斥

互斥信号量初值1；同步信号量初值0；同步P在互斥P前面

💡 考试提示：

银行家算法为重难点，必考计算

进程状态转换图需掌握五种状态

信号量P/V应用（生产者消费者、读写者、哲学家）需会用代码描述

调度算法（FCFS/SJF/HRRN/RR/MFQ）需理解适用场景和优缺点