📘 第1章操作系统引论

1.1 定义与目标必考重点

操作系统是管理计算机硬件与软件资源，并为应用程序提供公共服务的系统软件。

A：资源管理者
分配/调度 CPU、内存、磁盘、网络
目标：效率、公平、隔离、可靠性

B：服务提供者
把复杂硬件包装成简单接口
进程：独占CPU；虚拟内存：独占内存
文件：永久存储；套接字：可读写网络

操作系统的四大目标

方便性

让用户/开发者更容易使用计算机，如 shell、GUI、包管理器。

有效性

提高资源利用率与系统吞吐量。

可扩充性

方便增加新的功能和服务。

开放性

遵循标准，便于互联互操作。

1.2 操作系统的发展过程常考掌握

操作系统的发展是"需求推动机制"的过程：

💡 多道程序设计：把"CPU等待I/O"的空档利用起来。内存中同时存放多道程序，CPU在等待某程序I/O时，切换执行另一道程序，提高CPU利用率。

1.3 基本特征与功能必考重点

四大基本特征

特征	含义	举例
并发	多个活动"同时"推进（时间上复用）	浏览器多标签、多进程DataLoader
共享	资源被多个程序共同使用	共享文件、共享GPU、共享带宽
虚拟	将物理实体映射为多个逻辑对应物	虚拟内存、虚拟CPU
异步	进程以不可预知的速度向前推进	进程交替执行，速度不确定

五大管理功能

处理机管理 → 存储器管理 → 设备管理 → 文件管理 → 接口管理

1.4 运行环境与系统调用必考重点

硬件给OS的"特权与开关"：双模式 + 中断/异常 + 定时器 + MMU

用户态（目态）
应用代码运行状态
不能执行特权指令

内核态（管态）
OS内核运行状态
可执行全部特权指令

用户态→内核态的三种触发方式

系统调用

用户程序主动请求OS服务（如open、fork、read）

中断

外部设备发出的信号（如键盘输入、磁盘I/O完成）

异常

指令执行过程中的错误（如除零、缺页、非法指令）

📝 系统调用示例（strace）

系统调用是用户程序请求内核完成特定功能的"过程调用"，可用 strace 命令观察：

$ strace -c ls

该命令统计 ls 程序执行过程中触发了哪些系统调用。
常见系统调用类型：进程控制（fork/exec/wait）、文件操作（open/read/write）、设备管理（ioctl）、信息维护（getpid/time）。

📗 第2章进程与控制

2.1 进程概念与PCB 必考重点

进程是程序的一次执行过程，是系统进行资源分配和调度的一个独立单位。

💡 程序 vs 进程：程序是静态的指令集合（存在磁盘上），进程是动态的执行过程（在内存中运行）。一个程序可以对应多个进程。

PCB（进程控制块）

PCB是进程存在的唯一标识，OS通过PCB来管理和控制进程。PCB包含：

进程标识符

每个进程有唯一的PID

处理机状态

通用寄存器、程序计数器PC、程序状态字PSW

进程调度信息

状态、优先级、时间片、等待时间

资源信息

内存地址空间、打开的文件、I/O设备

🎯 对比记忆：PCB≈进程的"身份证"，TCB≈线程的"身份证"。

2.2 进程状态与控制必考重点

三种基本状态

进程控制原语

创建：分配PCB→分配资源→置为就绪→插入就绪队列

终止：回收资源→撤销PCB

阻塞：保存现场→置阻塞→转进程调度

唤醒：置就绪→插入就绪队列

2.3 进程通信常考掌握

通信方式	特点	适用场景
共享存储器系统	进程共享一段内存区域，速度快	同机大量数据交换
消息传递系统	通过消息队列发送/接收，分布式友好	异机通信、微内核
管道通信	单向字节流，半双工，自然同步	父子进程shell管道

2.4 线程必考重点

进程
拥有资源的基本单位（重型）
进程切换开销大
地址空间独立

线程
调度和分派的基本单位（轻型）
线程切换开销小
共享进程地址空间

线程实现方式

模型	描述	特点
多对一（ULT→KLT）	多个用户级线程映射到1个内核线程	管理高效但一个阻塞系统调用导致整个进程阻塞
一对一	每个用户线程对应1个内核线程	并发性强，但创建开销大
多对多	多用户线程映射到多内核线程	兼顾效率与并发，最灵活

📙 第3章处理机调度

3.1 调度层次与指标必考重点

调度层次	对象	频率	作用
高级调度（长程/作业调度）	作业	低（秒~分钟级）	决定哪些作业进入内存
中级调度（中程/内存调度）	进程	中等	进程在内外存之间对换
低级调度（短程/进程调度）	进程	高（毫秒级）	从就绪队列选一个进程分配CPU

评价指标

周转时间

从作业提交到完成的时间间隔。
T = 完成时间 − 提交时间

等待时间

进程在就绪队列中等待的总时间。

响应时间

从用户提交请求到首次产生响应的时间。

带权周转时间

W = 周转时间/运行时间，≥1

3.2 经典调度算法必考重点

FCFS（先来先服务）

按照作业到达的先后次序调度。非抢占式。实现最简单，但长作业会使短作业等待时间过长。

必考重点 FCFS & SJF Gantt图计算

题目：P1(0,8), P2(1,4), P3(2,2), P4(4,1)，求FCFS和抢占式SJF的各项指标。

FCFS调度：

Gantt图：P1[0-8] → P2[8-12] → P3[12-14] → P4[14-15]

等待时间：P1=0, P2=7, P3=10, P4=10 → 平均等待 = (0+7+10+10)/4 = 6.75

周转时间：P1=8, P2=11, P3=12, P4=11 → 平均周转 = (8+11+12+11)/4 = 10.5

抢占式SJF（最短剩余时间优先）：

Gantt图：P1[0-1] → P2[1-5] → P3[5-7] → P4[7-8] → P1[8-15]

等待时间：P1=7, P2=0, P3=3, P4=3 → 平均等待 = (7+0+3+3)/4 = 3.25

周转时间：P1=15, P2=4, P3=5, P4=4 → 平均周转 = (15+4+5+4)/4 = 7.0

RR（时间片轮转）

就绪队列每个进程依次获得一个时间片 q，时间片用完还没结束就被抢占并放回队尾。特别适合分时系统。

💡 时间片大小的确定：时间片太小→频繁切换，开销大；时间片太大→退化为FCFS，响应变慢。

优先级调度（PSA）

每个进程有一个优先数，小的优先数具有高优先级。分静态优先级（创建时确定，不变）和动态优先级（可随等待时间增加而提升——老化，防止饥饿）。

MLFQ（多级反馈队列）

3.3 多核与实时调度常考掌握

多处理机调度

SMP（对称多处理）：每个处理器独立调度自己，主流方案。ASMP（非对称）：仅一个处理器处理系统数据结构。亲和性：进程尽量在同一个CPU上运行，避免缓存失效。

实时调度

EDF（最早截止时间优先）
截止时间越早，优先级越高。优先级动态变化。

LLF（最低松弛度优先）
松弛度=必须完成时间−运行时间−当前时间。松弛度越小越紧急。

调度算法对比总结必考重点

算法	抢占	平均等待	响应速度	饥饿风险	适用
FCFS	非抢占	长	慢	无	批处理
SJF	两种	最短	中等	有	作业调度
PSA	两种	依优先级	快(高优)	有	实时/分时
RR	抢占	中等	快	无	分时系统
HRRN	非抢占	较短	中等	无	批处理
MLFQ	抢占	短	快	可控	通用

📕 第4章进程同步与死锁

4.1 同步互斥概念必考重点

同步（同步关系）
进程间相互合作。一个进程的推进依赖另一个进程先产生某个结果。
如：生产者→消费者（先生产才能消费）

互斥（互斥关系）
进程互斥使用临界资源。一次只允许一个进程进入临界区。
如：打印机、共享变量

临界区管理四准则

空闲让进

临界区空闲时，想进入的进程应能进入。

忙则等待

临界区已被占用时，其他进程必须等待。

有限等待

进程不能无限期等待进入临界区。

让权等待

不能进入临界区时应释放CPU，避免忙等。

4.2 同步机制必考重点

Peterson算法

解决两个进程的临界区问题，满足三个准则：

// 进程 Pi
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j) ;
// 临界区
flag[i] = FALSE;
// 剩余区

信号量机制

信号量 S 是一个受保护的计数器。wait(P)申请资源，signal(V)释放资源。

整型信号量
wait(S) { while(S≤0); S--; }
signal(S) { S++; }
缺点：忙等，浪费CPU

记录型信号量
typedef struct { int value; PCB* queue; } semaphore;
wait(S) { S.value--; if(S.value<0) block(); }
signal(S) { S.value++; if(S.value≤0) wakeup(); }
优点：让权等待，不会忙等

💡 信号量应用模板：
互斥：mutex=1 → wait(mutex) / 临界区 / signal(mutex)
同步：S=0 → 前驱操作 / signal(S) → wait(S) / 后驱操作

管程

管程把共享数据与同步操作封装在一个"管理室"中，任何时刻只允许一个进程在管程中操作，天然互斥。

4.3 经典同步问题必考重点

生产者—消费者问题

M个生产者、N个消费者共享n个缓冲区的缓冲池。

必考重点 PV操作解题

semaphore mutex = 1;  // 互斥访问缓冲区
semaphore empty = n;   // 空缓冲区数量
semaphore full = 0;    // 满缓冲区数量

// 生产者
void producer() {
  while(TRUE) {
    produce an item;
    wait(empty);     // 先检查空缓冲区
    wait(mutex);     // 再获取互斥锁
    buffer[in] = item; in = (in+1)%n;
    signal(mutex);
    signal(full);
  }
}

// 消费者
void consumer() {
  while(TRUE) {
    wait(full);      // 先检查满缓冲区
    wait(mutex);
    item = buffer[out]; out = (out+1)%n;
    signal(mutex);
    signal(empty);
    consume the item;
  }
}

⚠️ 注意：

wait(empty/full) 必须在 wait(mutex) 之前！ 否则若缓冲区满，生产者先锁住mutex再等待empty，消费者无法进入取数据，导致死锁。

哲学家进餐问题

5个哲学家共用5支筷子，每人需同时拿左右两支才能进餐。朴素解法可能产生死锁（每人拿左边筷子，一起等右边）。

解法1：最多4人同时用餐

限制并发数，打破循环等待

解法2：AND型信号量

Swait(左筷, 右筷) 同时申请两支

解法3：奇偶编号

奇数号先左后右，偶数号先右后左

读者—写者问题

多个读者可以同时读；写者必须独占。读者优先：读可并发，写者可能饥饿。写者优先：一旦有写者等待，后续读者必须等待。

4.4 死锁必考重点

死锁的四个必要条件

① 互斥

资源一次只允许一个进程使用

② 请求和保持

进程已至少有一个资源，又申请新资源

③ 非抢占

资源不能被强制抢占

④ 循环等待

存在进程-资源的循环等待链

死锁处理方法

方法	策略	示例
预防	破坏四个必要条件之一	一次性申请全部资源（破坏"请求和保持"）
避免	分配前判断安全性	银行家算法（Banker's Algorithm）
检测与解除	允许死锁发生，检测到后解除	资源分配图化简，终止/回滚进程
忽略	假装不存在	鸵鸟算法（大多数PC使用）

银行家算法必考重点

像银行贷款一样做资源分配。基本数据结构：

Available（可用资源）\to Max（最大需求）\to Allocation（已分配）\to Need（还需要）

Need = Max − Allocation。分配前先"试分配"，运行安全性算法检查是否安全。

必考重点银行家算法例题（课件原题）

系统有5个进程P0~P4，3类资源A(10个)、B(5个)、C(7个)。T0时刻：

进程	Allocation	Max	Need
P0	(0,1,0)	(7,5,3)	(7,4,3)
P1	(2,0,0)	(3,2,2)	(1,2,2)
P2	(3,0,2)	(9,0,2)	(6,0,0)
P3	(2,1,1)	(2,2,2)	(0,1,1)
P4	(0,0,2)	(4,3,3)	(4,3,1)

Available = (3,3,2)。

找安全序列：

P1: Need(1,2,2) ≤ Work(3,3,2) → 满足 → P1释放 → Work=(5,3,2)

P3: Need(0,1,1) ≤ Work(5,3,2) → 满足 → P3释放 → Work=(7,4,3)

P4: Need(4,3,1) ≤ Work(7,4,3) → 满足 → P4释放 → Work=(7,4,5)

P2: Need(6,0,0) ≤ Work(7,4,5) → 满足 → P2释放 → Work=(10,4,7)

P0: Need(7,4,3) ≤ Work(10,4,7) → 满足 → 完成

✅ 安全序列：<P1, P3, P4, P2, P0>

📘 第1章 操作系统引论

1.1 定义与目标 必考重点