OS

发表于 2026-05-31 分类于课程笔记

第二章：进程与线程

2.1 处理器概述

2.1.1 单处理器和多处理器系统

计算机系统的核心是CPU

CPU的基本任务是：

1	取指令 -> 译码 -> 取操作数 -> 执行指令

处理器可以分为：

1 2	- 单处理器系统 - 多处理器系统

单处理器系统

一个计算机系统只包括一个运算处理器。

注意：单处理器也可以有多个程序“看起来同时允许”。

这叫：

**并发**

从微观上来看，一个时刻CPU只能执行一个程序片段。

多处理器系统

一个计算机系统有多个运算处理器。

多个处理器真的可以同时执行不同任务。

这叫：

**并行**

计算机系统结构分类

PPT讲了四类：

1. SISD
2. SIMD
3. MISD
4. MIMD

1. SISD：单指令流单数据流

1	Single Instruction Single Data

意思是：

1	一个处理器在一个存储器中的数据上执行单条指令流

可以理解为最传统的单核执行机器：

一条指令 -> 执行一个数据流

2. SIMD：单指令流多数据流

1	Single Instruction Multiple Data

意思是：

1	一条指令控制多个数据单元，同时对不同数据做相同操作

例如：

1
2
3

向量机
阵列机
GPU中很多并行数据处理思想

3. MISD：多指令流单数据流

Multiple Instruction Single Data

意思是：
一个数据流被送给一组处理器，不同处理器执行不同指令。

这个现实中不常见，考试一般知道定义就够。

4. MIMD：多指令流多数据流

Multiple Instruction Multiple Data

意思是：

1	多个处理器对各自不同的数据集，同时执行不同的指令流。

现代多核、多处理器系统大多更接近这个模型。

多处理器和多核处理器

多处理器：

在一个体系结构上放置多个单核CPU芯片。

多核处理器：

在同一块CPU芯片上放置多个核core。

也就是一个CPU芯片里面有多个执行核心。

多核比多CPU更紧凑，成本更低，功耗更小

2.1.2 寄存器

构成一级存储，容量小，访问速度快
x86 寄存器分类：
- 通用寄存器：EAX, EBX, ECX, EDX
- 指针及变址寄存器：ESP, EBP, ESI, EDI
- 段选择符寄存器：CS, DS, SS, ES, FS, GS
- 指令指针和标志寄存器：EIP, EFLAGS
- 控制寄存器：CR0, CR1, CR2, CR3

2.1.3 特权指令和非特权指令

特权指令：仅供OS核心使用（设置定时器、读取时钟、清除内存、发起陷入、关中断、修改设备状态、访问I/O等）
非特权指令：普通功能指令（数据处理、转移、数据传送、移位、字符串、I/O类）

2.1.4 处理器状态

管理状态（内核态/管态/Ring 0）：可执行全部的指令，使用所有资源
用户状态（用户态/目态/Ring 3）：只能执行非特权指令
状态切换途径：
- 程序请求OS服务（系统调用）
- 程序运行过程中产生中断或异常事件
Intel保护级别：Ring 0（内核） -> Ring 1/2（设备驱动）-> Ring 3（应用程序）

2.1.5 程序状态字寄存器（PSW）

用于区别不同的处理器的工作状态
包含内容：
- 程序基本状态
- 中断码（保存当前发生的中断事件）
- 中断屏蔽位（指明是否响应中断）

2.1.6 x86总体架构

工作模式：实模式、保护模式、SMM模式
- 实模式：没有任何保护机制，最原始的8086兼容模式
- 保护模式：现代OS运行的机制，通过硬件机制实现了内核态/用户态的隔离。
- SMM模式：主板/固件的后门模式，执行一些比操作系统更底层、更紧急的硬件管理任务。
关键控制寄存器：
- CR0：PE（保护模式）、PG（分页）
- CR3：页目录基址
内存管理寄存器：GDTR（全局描述符）、IDTR（中断描述符）、TR（任务寄存器）

2.2 计算机的启动

传统启动流程（BIOS）

1	系统加电 -> BIOS 初始化硬件 -> BIOS读取主引导扇区(MBR)-> 读取活动分区引导扇区 -> 加载OS内核 -> 跳转执行内核

启动时内存布局
- CS: 0xF000, IP: 0xFFF0，指向 BIOS ROM 最后的 16 字节
- 主引导扇区（512 字节，以 0x55AA 结尾）被加载到 0x7C00
Bootloader：完成系统初始化和OS内核加载，提供启动菜单

2.3 OS中的中断处理

2.3.1 中断的概念

中断：程序执行的过程中，因为发生某个事件而中止CPU现行程序，转去处理该事件的过程
本质：能够改变CPU执行指令序列的事件；OS是由中断驱动的

2.3.2 中断分类

分类	名称	特征
同步中断	异常	由CPU控制单元产生，指令执行终止后才发出
异步中断	中断	由其他硬件设备依据CPU时钟信号随机产生

2.3.3 中断、异常和系统调用

类型	产生原因	同步/异步	服务对象
中断	硬件设备请求	异步	不一定是当前进程
异常	程序错误、内核必须处理的异常条件	同步	当前进程
系统调用	应用程序主动请求OS服务	同步（特殊的异常）	当前进程

Fault：保存触发异常的那条指令地址，返回重新执行执行
Trap：保护触发异常指令的下一条地址，返回时不重新执行

2.3.4 中断处理机制

定时器：OS回收控制的重要方式，避免死循环和恶意独占CPU
中断装置：
- 发现中断源
- 保护现场
- 启动中断处理程序
CPU响应中断的过程（略看）：
- 自动保存CPU状态
- 根据TR定位当前进程内存空间
- 根据IDTR定位IDT，检索中断向量号对应处理程序
- 跳转执行
中断处理程序工作：
- 保护未被硬件保存的必需状态
- 识别中断源，分析原因
- 处理中断事件
- 恢复正常操作

同步性和原子性

中断随时发生，OS必须保证现场保护的原子性
方法：关中断、原子指令

2.4 进程的定义和描述

2.4.1 程序的顺序执行

特征：
1. 顺序性：严格按照程序规定顺序执行
2. 封闭性：执行结果不受外界因素影响
3. 可再现性：初始条件相同，重复执行结果相同

2.4.2 程序的并发执行

定义：若干个程序（段）同时在系统中运行，执行时间重叠
特征：
1. 间断性：执行—暂停—执行
2. 失去封闭性：资源共享，相互影响
3. 不可再现性：结果依赖于执行次序
与时间有关的错误：并发读写共享变量导致结果不确定

2.4.3 程序并发执行的条件（Bernstein 条件）

设 R(S) 为读集，W(S) 为写集，两程序段 Si 与 Sj 可并发执行当且仅当：

R(Si)∩W(Sj)=∅
R(Sj)∩W(Si)=∅
W(Si)∩W(Sj)=∅

2.4.4 进程的引入

定义：进程是可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，是 OS 进行资源分配和保护的基本单位
引入原因：
- 刻画系统动态性，发挥并发性，提高资源利用率
- 解决共享性，正确描述程序执行状态

2.4.5 进程的特征

动态性：因创建而生，因调度而执行，因撤销而消亡
并发性：多个进程实体同时存在于内存中
独立性：独立运行的基本单位，系统分配资源和调度的基本单位
异步性（制约性）：各自以不可预知的速度推进
结构性：程序段 + 数据段 + PCB
共享性：同一程序运行于不同数据集合构成不同进程

2.4.6 进程的描述

进程映像：某时刻进程的内容及其状态的集合
- 组成：PCB + 程序块 + 核心栈 + 数据块
进程上下文：进程物理实体 + 支持进程运行的环境
- 用户级上下文：正文、数据、共享存储区、用户栈
- 寄存器级上下文：PSW、指令计数器、栈指针、控制/通用寄存器
- 系统级上下文：PCB、主存管理信息、核心栈
进程控制块（PCB）：进程存在的唯一标志
- 标识信息：进程标识符、家族关系、用户标识符
- 现场信息：通用寄存器、控制寄存器、栈指针等
- 控制信息：进程状态、队列指针、优先级、通信信息、程序/数据地址、资源清单
Linux 进程表示：task_struct

2.5 进程的状态及转换

2.5.1 三态模型

状态	说明
就绪（Ready）	有资源，一旦分配CPU就可以执行
执行（Running）	正在CPU上执行
阻塞（Blocked）	因等待某事件，如I/O而暂停，即使分配CPU也无法运行

状态转换：

就绪 -> 执行：进程调度
执行 -> 就绪：时间片用完了
执行 -> 阻塞：等待事件（主动请求I/O等）
阻塞 -> 就绪：事件发生

思考题：1个处理器，N个进程 -> 运行态最多1个；就绪态最多N - 1个；阻塞态最多N个

2.5.3 五态模型

在三态模型的基础上新增：

新建（New）：进程刚建立，未进入就绪队列
终止（Terminated）：进程结束，资源已释放但是尚未撤销

Java线程与隐蔽通道侧信道攻击

以下是根据 PPT 整理的 进程与线程 完整学习笔记，采用 Markdown 格式，方便你直接复制到笔记软件（如 Typora、Obsidian、Notion）中使用。

第2章进程与线程

2.1 处理器概述

2.1.1 单处理器与多处理器系统

CPU 核心任务：取指 → 译码 → 取操作数 → 执行指令
单处理器系统：仅包含一个运算处理器
多处理器系统：包含多个运算处理器

计算机系统结构分类（Flynn 分类法）

表格

类型	名称	特征
SISD	单指令流单数据流	一个处理器在一个存储器的数据上执行单条指令流
SIMD	单指令流多数据流	单条指令控制多个处理单元同时对不同数据操作（向量机、阵列机）
MISD	多指令流单数据流	一个数据流传送给一组处理器，通过不同指令操作得到结果
MIMD	多指令流多数据流	多个处理器对各自不同的数据集同时执行不同的指令流；分为共享内存紧密耦合与内存分布松散耦合

多处理器 vs 多核处理器

多处理器：一个体系结构上放置多个（单核）CPU 芯片
多核处理器：同一块 CPU 芯片上放置多个核（Core/执行单元）
区别：多核更加紧凑、成本更低、功耗更小
结构演进：多处理器 → 超线程 → 多核 → 多核超线程

2.1.2 寄存器

构成一级存储，容量小、访问速度快
x86 寄存器分类：
- 通用寄存器：EAX, EBX, ECX, EDX
- 指针及变址寄存器：ESP, EBP, ESI, EDI
- 段选择符寄存器：CS, DS, SS, ES, FS, GS
- 指令指针和标志寄存器：EIP, EFLAGS
- 控制寄存器：CR0, CR1, CR2, CR3

2.1.3 特权指令与非特权指令

特权指令：仅供 OS 核心使用（设置定时器、读取时钟、清除内存、发起陷入、关中断、修改设备状态、访问 I/O 等）
非特权指令：普通功能指令（数据处理、转移、数据传送、移位、字符串、I/O 类）

2.1.4 处理器状态

管理状态（内核态/管态/Ring 0）：可执行全部指令，使用所有资源
用户状态（用户态/目态/Ring 3）：只能执行非特权指令
状态切换途径：
1. 程序请求 OS 服务（系统调用）
2. 程序运行产生中断或异常事件
Intel 保护级别：Ring 0（内核）→ Ring 1/2（设备驱动）→ Ring 3（应用程序）

2.1.5 程序状态字寄存器（PSW）

用于区别不同的处理器工作状态
包含内容：
- 程序基本状态（程序计数器、条件码、处理器状态位）
- 中断码（保存当前发生的中断事件）
- 中断屏蔽位（指明是否响应中断）

2.1.6 x86 总体架构

工作模式：实模式、保护模式、SMM 模式
关键控制寄存器：
- CR0：PE（保护模式）、PG（分页）
- CR3：页目录基址（PDBR）
内存管理寄存器：GDTR（全局描述符）、IDTR（中断描述符）、TR（任务寄存器）

2.2 计算机的启动

传统启动流程（BIOS 方式）

plain

复制
系统加电 → BIOS 初始化硬件 → BIOS 读取主引导扇区(MBR)
→ 读取活动分区引导扇区 → 加载 OS 内核 → 跳转执行内核

启动时内存布局（实模式，20 位地址空间，1MB）：
- CS: 0xF000, IP: 0xFFF0，指向 BIOS ROM 最后的 16 字节
- 主引导扇区（512 字节，以 0x55AA 结尾）被加载到 0x7C00
Bootloader：完成系统初始化与 OS 内核加载，提供启动菜单

现行启动规范

表格

规范	特点
Legacy BIOS	固化到主板，支持传统 MBR，不支持 2TB 以上硬盘
UEFI	统一可扩展固件接口，提供一致的启动服务，支持大硬盘

可信计算启动信任链

从 BIOS boot block 开始建立信任根
逐级度量：BIOS → OS loader → OS → Application
TPM：可信平台模块，负责存储度量值与报告

2.3 OS 中的中断处理

2.3.1 中断的概念

中断：程序执行过程中，因发生某个事件而中止 CPU 现行程序，转去处理该事件的过程
本质：能够改变 CPU 执行指令序列的事件；OS 是由中断（事件）驱动的

2.3.2 中断分类

表格

分类	名称	特征
同步中断	异常（Exception）	由 CPU 控制单元产生，指令执行终止后才发出
异步中断	中断（Interrupt）	由其他硬件设备依据 CPU 时钟信号随机产生

2.3.3 中断、异常与系统调用

表格

类型	产生原因	同步/异步	服务对象
中断	硬件设备请求	异步	不一定是当前进程
异常	程序错误、内核必须处理的异常条件	同步	当前进程
系统调用	应用程序主动请求 OS 服务	同步（特殊异常）	当前进程

Fault（出错）：保存触发异常的那条指令地址，返回时重新执行
Trap（陷入）：保存触发异常指令的下一条地址，返回时不重新执行（用于调试）

2.3.4 中断处理机制

定时器：OS 回收控制的重要方式，避免死循环与恶意独占 CPU
中断装置（如 8259A）：
1. 发现中断源（按优先级响应）
2. 保护现场（PSW 保存至核心栈）
3. 启动中断处理程序
CPU 响应中断过程：
1. 自动保存 CPU 状态（EIP, EFLAGS, ESP, SS, CS）
2. 依据 TR 定位当前进程内存空间
3. 依据 IDTR 定位 IDT，检索中断向量号对应处理程序
4. 跳转执行
中断处理程序工作：
1. 保护未被硬件保存的必需状态
2. 识别中断源，分析原因
3. 处理中断事件
4. 恢复正常操作

同步与原子性

中断随时发生，OS 必须保证现场保护的原子性
方法：关中断、原子指令

2.4 进程的定义与描述

2.4.1 程序的顺序执行

特征：
1. 顺序性：严格按照程序规定顺序执行
2. 封闭性：执行结果不受外界因素影响
3. 可再现性：初始条件相同，重复执行结果相同

2.4.2 程序的并发执行

定义：若干个程序（段）同时在系统中运行，执行时间重叠
特征：
1. 间断性：执行—暂停—执行
2. 失去封闭性：资源共享，相互影响
3. 不可再现性：结果依赖于执行次序
与时间有关的错误：并发读写共享变量导致结果不确定

2.4.3 程序并发执行的条件（Bernstein 条件）

设 R(S) 为读集，W(S) 为写集，两程序段 Si 与 Sj 可并发执行当且仅当：

R(Si)∩W(Sj)=∅
R(Sj)∩W(Si)=∅
W(Si)∩W(Sj)=∅

2.4.4 进程的引入

定义：进程是可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，是 OS 进行资源分配和保护的基本单位
引入原因：
- 刻画系统动态性，发挥并发性，提高资源利用率
- 解决共享性，正确描述程序执行状态

2.4.5 进程的特征

动态性：因创建而生，因调度而执行，因撤销而消亡
并发性：多个进程实体同时存在于内存中
独立性：独立运行的基本单位，系统分配资源和调度的基本单位
异步性（制约性）：各自以不可预知的速度推进
结构性：程序段 + 数据段 + PCB
共享性：同一程序运行于不同数据集合构成不同进程

2.4.6 进程的描述

进程映像：某时刻进程的内容及其状态的集合
- 组成：PCB + 程序块 + 核心栈 + 数据块
进程上下文：进程物理实体 + 支持进程运行的环境
- 用户级上下文：正文、数据、共享存储区、用户栈
- 寄存器级上下文：PSW、指令计数器、栈指针、控制/通用寄存器
- 系统级上下文：PCB、主存管理信息、核心栈
进程控制块（PCB）：进程存在的唯一标志
- 标识信息：进程标识符、家族关系、用户标识符
- 现场信息：通用寄存器、控制寄存器、栈指针等
- 控制信息：进程状态、队列指针、优先级、通信信息、程序/数据地址、资源清单
Linux 进程表示：task_struct

2.5 进程的状态及转换

2.5.1 三态模型

表格

状态	说明
就绪（Ready）	有资源，一旦分配 CPU 即可执行
执行（Running）	正在 CPU 上执行
阻塞（Blocked）	因等待某事件（如 I/O）而暂停，即使分配 CPU 也无法运行

状态转换：

就绪 → 执行：进程调度
执行 → 就绪：时间片用完
执行 → 阻塞：等待事件（主动请求 I/O 等）
阻塞 → 就绪：事件发生（被动唤醒）

思考题：1 个处理器，N 个进程 → 运行态最多 1 个；就绪态最多 N-1 个；阻塞态最多 N 个。

2.5.2 五态模型

在三态基础上增加：

新建（New）：进程刚建立，未进入就绪队列
终止（Terminated）：进程结束，资源已释放但尚未撤销

2.5.3 七态模型（含挂起状态）

引入挂起Suspend状态，将进程对换到磁盘镜像区，暂时不参与调度：

表格

状态	说明
活动就绪	在内存中，可被调度
挂起就绪	在外存中，需激活后才能调度
活动阻塞	在内存中等待事件
挂起阻塞	在外存中等待事件

挂起原因：内存不足、调试、父进程要求、系统故障排除、定期进程对换等

2.6 进程控制管理和组织

2.6.1 进程创建

进程树：描述进程家族关系的有向树（如Linux中的init为根，pid = 1）
创建事件：用户登录、作业调度、OS服务等
创建原语流程：
- 申请空闲PCB
- 分配内存空间等资源
- 初始化PCB
- 插入就绪队列
Linux相关系统调用：
- fork()：创建子进程，复制父进程全部资源
- exec()：用新程序填充进程空间
- vfork()：子进程与父进程共享数据段，子进程先运行
- clone()：有选择地共享父进程资源

`POSIX`共享内存

进程通过系统调用shm_open()创建共享内存

shm_fd = shm_open(name, O_CREAT | O_RDRW, 0666);
//name: 共享内存对象的名称, 
//当name 不存在时，创建共享内存(O_CREAT)  对象需要打开以便读写(O_RDRW),
//0666设定共享内存对象的目录权限

shm_open 返回共享内存对象的一个文件描述符

ftruncate()函数配置对象的大小

1 2	ftruncate(shm_fd, 4096); //将对象的大小分配为4096字节

最后mmap()函数创建内存映射文件，以便包含共享内存对象，返回一个指向内存映射文件的指针，以便用于访问共享内存对象
1
mmap(0, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0)

第三章：调度

调度是多道程序操作系统的基础

多道程序的目标：无论何时都有进程在运行，从而最大化操作系统的利用率。
分时系统的目的：在进程之间快速切换CPU，以方便多个用户在程序运行时能与其进行交互。
进程调度器：(可能从多个可用进程中)选择一个可用进程，装入到CPU上执行。

3.1 调度的基本概念
1. 调度队列
操作系统中维护了一组进程调度队列
作业队列：系统中所有进程的集合
作业Job：针对批处理系统的CPU活动而言
用户程序/任务Task：针对分时系统的CPU而言

就绪队列：所有驻留在内存，处于就绪状态，等待调度执行的进程集合。
设备队列：等待某个I/O设备的进程集合

进程在整个生命周期中，会在各种调度队列之间迁移

2.调度的层次

调度程序：负责挑选就绪进程的内核模块

一个作业从提交到完成通常要经历多级调度

处理机的三层调度：

高级调度：

作业级别的调度

低级调度：

进程级别的调度

中级调度：

交换调度

高级调度：

主要任务：按照一定的规则，从外存中处于后备状态的作业中，选择一个或多个作业，决定哪些进程可以进入就绪队列。
同时为这些选中的作业，I/O设备提供必要资源，并建立相应地进程使该作业拥有获得竞争处理机的权利。

低级调度：
按照某种原则，决定就绪队列里的哪个进程能够获得处理器，并且将处理机出让给它进行工作
存在剥夺，抢占懂机制
进程可以分为：
- I/O密集型和 CPU密集型为了资源重复利用，这两类经常应该混合搭配
  
  中级调度：
将内存中不用的信息移到外存，为内存中进程腾出空间
将需要的信息从外存读入内存
决定主存中能容纳的进程数，提高内存利用率和系统吞吐量

3. 调度的性能评价指标：

资源利用率
- CPU利用率 = CPU有效工作时间 / CPU总运行时间真实系统介于40% - 90%
响应时间
- 交互式进程，从提交一个请求到接收到第一个响应之间的时间间隔
周转时间
- 从作业提交到作业完成的时间间隔
- 包括：等待进入内存，在就绪队列里等待，在CPU上执行和I/O执行的时间
- 带权周转时间：作业周转时间与作业实际运行时间的比值，这里的作业实际运行时间指的是在CPU中的时间，不包括阻塞和挂起等时间
系统吞吐率
- 单位时间CPU完成作业的数量
公平性：
- 确保每个进程获得合理的CPU份额，不会出现饿死现象

3.2作业，进程和线程的调度

1.作业和进程的关系：

作业是一个Job集合，是一个任务的实体
进程是完成这个任务的执行实体

没有作业，进程无事可做
没有进程，作业无法完成

2.作业从提交到完成经过四个状态：

提交状态：用户作业由输入设备，向系统外存输入作业所处的状态
后备状态：系统为作业建立作业控制块，你并把它插入到后备作业队列里面等待调度
执行状态：作业在内存中，包含占有CPU和没占有CPU
完成状态：作业正常完成或者异常结束，但是作业占有的资源还没有被系统全部回收

3.作业进程调度：

记录进入系统的各作业情况
从后备作业中挑一些投入执行
为被选中的作业做好执行前的准备工作
为执行完或异常结束的作业作收尾工作

4.资源控制块：
包括：资源要求，资源使用情况，作业的控制方式（联机作业控制or脱机作业控制），类型（终端型，批量型），优先级等

5.进程调度的方式：

抢占方式
非抢占方式：一旦将处理机分配给某进程，便让该进程一直执行知道执行完or发生某事件进入阻塞。

抢占方式：
运行调度程序根据某种原则去停止正在执行的进程，将其重新分配给其他进程

抢占原则由：
优先权：高优先级进程剥夺/抢占低优先级
时间片：时间片用完，剥夺CPU使用权

引起进程调度的原因：
从运行态切换到等待状态：I/O请求，调用wait等
从运行态切换到等待态：如中断
从等待态切换到就绪态：系统调用或中断返回等
进程终止

分派器：将CPU分派给调度器选定的进程

6. 线程调度：

分为用户级线程和内核级线程
当OS内核支持线程时，内核级线程由OS调度
对于多对一和多对多模型，系统库负责调度用户级线程

3.3 调度算法

3.3.1 先来先服务算法（`FCFS`）：

额，很容易理解，就是字面意思，不过多解释。

3.3.2 短作业有线调度算法：

也很容易理解的字面意思，不过多解释。

3.3.3 优先级调度算法：

也比较好理解，注意抢占

静态优先级，在创建进程的时候就确定的
动态优先级，优先数在进程运行过程中进行调整，如：
1
优先数 = CPU使用时间 / 2 + 基本优先数
3.3.4 时间片轮转调度（RR）

时间片轮转法（Round-robin）：

核心思想：大家轮流来，每人一次只干一会

所有就绪的进程按FIFO的顺序拍成一个队列，CPU每次都把执行权交给队首进程，但是这个进程最多执行一个固定时长（称为时间片）。

时间片用完但是进程还没执行完，将CPU让给队首进程，自己排到队尾。
如果提前执行完了，直接让出CPU。
举个例子：

进程	执行时间（ms）
P1	5
P2	3
P3	8

调度过程：

时刻	执行进程	剩余时间	说明
0-4	P1	P1剩1	P1时间片用完，未做完，排队尾
4-7	P2	P2完成	P2执行3ms后完成，主动释放CPU
7-11	P3	P3剩4	P3时间片用完，排队尾
11-12	P1	P1完成	P1只剩1ms，做完
12-16	P3	P3完成	P3做完

时间片大小的选择：

若时间片时间过大，所有进程都能在一个时间片内完成，则时间片轮转算法退化成先来先服务。
若时间片太小，则进程调度频繁，会有大量时间用于上下文切换，系统开销增加。

3.3.5最高响应比优先调度算法(HRRN)

1. 核心思想

每次调度时，计算所有就绪程序的响应比，选最高的那个投入运行。

2. 响应比的计算

$$
响应比 = 1 + 等待时间/要求服务时间
$$

3.算法的优点

同时照顾了长作业和短作业。

场景	响应比变化	意义
等待时间越长	响应比越大	长作业等待久了，也能有调度的机会（防止饥饿）
要求服务的时间越短	响应比越大	短作业有天然优势
刚到达的短作业	响应比 ≈ 1	刚来的短作业，等待时间为0

主要用于作业调度。

3.3.6多级队列调度算法

“人以群分，队以类聚”

1. 核心思想：

先把进程按照类型固定分进不同的队列，然后：

队列的内部：各自用适合自己的调度算法
队列之间：按照固定的优先级或者时间片比例进行调度

2. 队列之间的两种调度的策略
策略A：固定优先级调度
高优先级的队列只要有进程，低优先级的队列永远轮不到
优点：重点任务响应快
缺点：低优先级队列可能会饿死

策略B：时间片比例分配
给每个队列分配固定比例的CPU时间
例如：系统队列20%，交互队列50%，批处理30%
优点：避免饿死，每个队列都有保底时间
缺点：高优先级响应没那么极致

3.3.7 多级反馈队列调度算法（MLFQ）

1. 和多级队列的区别

特性	多级队列	多级反馈队列
队列间移动	固定不动	可以升降级
优先级变化	一成不变	动态调整
灵活性	低	高
饥饿问题	可能饿死	通过反馈机制避免

2. 算法核心

系统设置多个就绪队列，优先级由高到低，时间片由小到大：

Q0: 优先级最高,时间片最短（如8ms）  I/O密集型
Q1: 优先级最高,时间片中等（如16ms）
Q2: 优先级最高,时间片最长（如32ms）
...
Qn: 优先级最低,时间片最长      计算密集型

3. 调度规则（重点！！！）

MLFQ 依靠几条简单的规则实现智能调度：

规则1：新进程->最高优先级队列

规则2：时间片用完，任务还没完成->降级

规则3：主动放弃CPU->保持/升级

如果进程在时间片用完之前主动放弃CPU（I/O请求，调用wait），说明是I/O密集型

规则4：高优先级队列有进程，低优先级队列永远轮不到
规则5：低优先级队列的进程等太久，全部重新提升到最高优先级队列

4.一个例子

假设有两个进程：

P1：I/O密集型
P2：CPU密集型

时间	发生的事情	P1所在队列	P2所在队列
0	两个进程都到达，进入Q0	Q0	Q0
0-2	P1用了2msCPU收到I/O请求，主动放弃，留在Q0	Q0	-(不变)
2-8	P2狂算了8ms还没算完，降级	-	Q1
8-10	P1又是用了2ms后收到I/O请求，主动放弃，留着Q0	Q0	-
10-16	P2依旧狂算6ms，仍然没算完，降级	-	Q2
…	P1每次都只用2ms，主动放弃留在Q0	Q0	-
…	P2一直算一直算，一直降级	-	Qn

3.3.8 公平分享调度算法

公平不是进程之间的公平，而是用户/组之间的公平

1. 核心思想：

传统调度算法：只考虑进程本身；公平分享调度算法：不管用户开多少个进程，每个用户获得相等的CPU份额。

2.核心机制

两层调度：
外层：按照权重，给每个用户分配CPU份额
内层：在用户内部，用传统算法调度用户进程
关键指标：CPU利用率
系统记录每个用户/组的CPU使用时间，优先调度用的少的用户
用户用的越多，优先级越低

3.具体例子

用户进程数传统 RR 占比公平分享占比

用户 A 1 个进程 10% 50%

用户 B 9 个进程 90% 50%

用户	进程数	传统 RR 占比	公平分享占比
用户 A	1 个进程	10%	50%
用户 B	9 个进程	90%	50%

公平分享调度算法的做法：

每个用户获得相同的CPU份额，50%
A的一个进程独占A的百分之50
B的9个进程平分百分之50

3.3.9单速率调度算法RM
1. 核心思想
优先级与周期成反比：周期越短的任务，优先级越高
任务每T毫秒到来一次，每次需要C毫秒CPU时间
周期越短 -> 频率越高 -> 优先级越高

2. 例子：

任务	周期T	执行时间C	优先级
P1	50ms	20ms	高
P2	100ms	35ms	低

3. 调度过程

0ms：P1和P2同时到达，P1优先级高，先执行20ms
20ms：P1完成，P2开始执行
50ms：P1第二次到达，抢占P2，执行20ms
70ms：P1完成，P2执行剩余的5s
100ms：P1，P2再次到达….

3.3.10 最早截止时间优先EDF

核心思想

每次调度的时候，看谁的截止时间最先到，就先执行谁

不固定优先级，每个周期同时算
截止时间越接近，优先级越高

还是上面的例子，调度过程如下

0ms：P1截止时间50，P2截止时间1000，先执行P1 20ms
20ms：P1执行完了，只剩P2，开始执行（20ms - 55ms）
50ms：P1第二次到达（截止100），此时P2还剩5ms，截止时间也是20ms
50ms-70ms：P1和P2截止时间相同，后续规则看具体实现

EDF的利用率可能达到很高，但是系统可能会超载

第四章：进程同步

核心问题

多个并发进程共享资源时，如何保证执行顺序正确，避免资源状态不一致？
进程之间制约关系分为两种：

同步：合作进程的直接制约（协作）
互斥：共享资源产生的间接制约（竞争）

4.1 同步和互斥的概念

4.1.1 两个经典案例

案例1：结果不唯一

进程A:
R1 = x;
if(R1>=1){
  R1--;
  x = R1;
}

进程B：
R2 = x;
if(R2>=1){
R2–;
x = R2;
}

假设 x=1：
- 如果先执行完A再执行B，x最终减少2 -- 正确
- 如果A读到R1 = x，在进程1对x修改之前，B读到R2 = x, 最后的结果是x减少1
原因：没有互斥使用共享变量

案例2：永远等待：

进程A(alloc):
while(B>x)
等待;
x=x-B;

进程B(free):
x=x+B;

如果在A执行完while(B>x)之后，还没有进入等待队列之前，B恰好进行了free，则A进入等待队列后再没人将他幻想–永远等待

4.1.2 临界资源和临界区

概念	定义
临界资源	一段时间内仅允许一个进程使用的资源
临界区	进程中访问临界资源的那段代码
同类临界区	所有与同一临界资源相关联的临界区

临界区访问的四条部分：

进入区：检查是否可以访问，若可以则设置访问状态
临界区：实际访问临界资源的代码
退出区：清除访问状态
剩余区：其余代码

临界区访问的四条原则

空闲让进：无人在临界区时，允许一个进程进入
忙则等待：有人在临界区内，其他人等待
有限等待：保证有限实际内能够进入，不会饥饿
让权等待：进不去的时候应该释放CPU

4.2 互斥的实现方法

4.2.1 软件方法

算法1：轮转法（turn变量）

int turn = 0;
P0() {
    do{
        while (turn != 0);//turn = 1循环等待
        //临界区CS0
        turn = 1;
    }while (true);
}
P1() {
    do{
        while (turn != 1);//turn = 0循环等待
        //临界区CS0
        turn = 0;
    }while (true);
}

问题：必须严格交替执行；不满足空闲让进

算法2：flag数组法

enum bool {false, true};
bool flag[2] = {false, false};

P0(){               P1(){
  do {               do {
    while (flag[1]);    while (flag[0]);
    flag[0] = true;     flag[1] = true;
    // 临界区 CS0        // 临界区 CS1
    flag[0] = false;    flag[1] = false;
    // 其他代码          // 其他代码
  } while(true);     } while(true);
}

算法3：先上锁后检查

enum bool {false, true};
bool flag[2] = {false, false};

P0(){               P1(){
  do {               do {
    flag[0] = true;     flag[1] = true;
    while (flag[1]);    while (flag[0]);
    // 临界区 CS0        // 临界区 CS1
    flag[0] = false;    flag[1] = false;
    // 其他代码          // 其他代码
  } while(true);     } while(true);
}

算法4：Dekker算法

enum bool {false, true};
bool flag[2] = {false, false};
int turn = 0;  // 或 1

P0 {                          P1 {
  do {                          do {
    flag[0] = true;               flag[1] = true;
    while (flag[1]) {             while (flag[0]) {
      if (turn != 0) {              if (turn != 1) {
        flag[0] = false;              flag[1] = false;
        while (turn != 0);            while (turn != 1);
        flag[0] = true;               flag[1] = true;
      }                             }
    }                             }
    // 临界区 CS0                   // 临界区 CS1
    turn = 1;                     turn = 0;
    flag[0] = false;              flag[1] = false;
    // 其他代码                     // 其他代码
  } while(true);                } while(true);
}

关键机制：当P0和P1遇到算法2，3的，同时想要进入缓冲区的问题的时候，turn的值决定P0和P1的优先级，决定谁先进入

算法5：Peterson算法

enum bool {false, true};
bool flag[2] = {false, false};
int turn;

P0 {                          P1 {
  do {                          do {
    flag[0] = true;               flag[1] = true;
    turn = 1;                     turn = 0;
    while (flag[1] && turn == 1); while (flag[0] && turn == 0);
    // 临界区 CS0                   // 临界区 CS1
    flag[0] = false;              flag[1] = false;
    // 其他代码                     // 其他代码
  } while(true);                } while(true);
}

关键代码：

flag[me] = true;//如果我想进入缓冲区
turn = other;//谦让给对面优先;
while(flag[other] && turn = other);//如果对面也想进入，则让对方进入
//否则我自己进入

4.2.2 硬件方法

核心思想：把“检测+设置”封装成一条硬件指令，保证原子性。

方法1：关中断

原理：进程进入到临界区的时候，禁止中断的发生。
因为进程之间的切换是通过中断引起的。

1
2
3

关中断;
临界区;
开中断;

缺点：

如果临界区很长，系统收到的其他I/O请求无法响应；
多处理器无效：一个CPU上关中断，其他CPU不受影响，其他CPU的进程仍可进入临界区；
安全问题

方法2：原子指令-TS

原理：硬件提供一条原子指令，在一条指令内完成“读取旧值＋设置新值”

boolean TS(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}
//使用方式
boolean lock = false; //共享变量，false表示空闲
// 每个进程:
while (TS(&lock));
//临界区
lock = false;

方法3：原子指令Swap

void swap(boolean* a, boolean* b){
    boolean temp = *a;
    *a = *b;
    *b = temp;
}
//使用方式
boolean lock = false;  // 共享锁变量

// 每个进程：
boolean key = true;
while (key != false)   // 只要key还是true，就说明没拿到锁
    Swap(&lock, &key);  // 把lock和key交换
// 临界区
lock = false;          // 释放

4.2.3 互斥锁机制

基本互斥锁

// 上锁
void lock(int w) {
    while (w == 1);  // 等待锁被释放（忙等）
    w = 1;           // 加锁
}

// 开锁
void unlock(int w) {
    w = 0;           // 释放锁
}
//使用
// 进程P1          // 进程P2
lock(w);          lock(w);
临界区;           临界区;
unlock(w);        unlock(w);

自旋锁

void spinlock(lock) {
    while (test_and_set(lock) == 1);  // 忙等
    // 获得锁，进入临界区
}

void spinunlock(lock) {
    lock = 0;
}

4.3 信号量

4.3.1 信号量的定义

信号量是一个二元组：S = (s, q)

s：整型变量，表示系统中某类资源的可用数量
- s ≥ 0时：表示还有s个资源可用
- s < 0时：表示|s|个进程正在等待
q：等待队列，存放因等待该资源而阻塞的进程
重要规则：信号量的值只能提供P操作和V操作来改变，不能直接s++或者s–

4.3.2 P 操作（wait/等待/请求资源）

P(S) {
    s = s - 1; //先减1，表示请求一个资源
    if (s < 0) { //如果减完小于0表示没资源了
        设置进程状态为等待；
        讲进程放入信号量等待队列q；
        转调度程序；//阻塞自己，让出cpu
    }
}

4.3.3 V操作（signal/信号/释放资源）

V(S) {
    s = s + 1; //释放一个进程
    if (s <= 0){ //如果加完后仍<=0，说明有进程在等待
        取队列q的队首进程；
        设置状态为就绪；
        插入就绪队列；
    }
}

4.3.4 标准教材版本

typedef struct {
    int value;              // 资源计数
    struct process *list;   // 等待队列
} semaphore;

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        将当前进程加入 S->list;
        block();            // 阻塞自己
    }
}

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        从 S->list 取出一个进程 P;
        wakeup(P);          // 唤醒进程P
    }
}

4.3.4 使用信号量实现互斥

为临界资源设置一个互斥信号量，初始值为1（表示资源可用数为1)。

semaphore mutex = 1;   // 互斥信号量

进程P1 {              进程P2 {
    P(mutex);           P(mutex);
    临界区;             临界区;
    V(mutex);           V(mutex);
}

互斥信号量的取值范围：N个进程共享一个资源

最大：1（无人在临界区）
最小：-（N-1)（1人在临界区，N-1人在等待）

4.3.5 利用信号量实现前驱关系

前驱关系：P1必须在P2之前执行完成。
方法：设置一个同步信号量，初值为0

semaphore a = 0;   // 同步信号量

P1() {             P2() {
    ...               P(a);      // 等待P1完成
    ...               ...
    V(a);             // 通知P1已完成
}                 }

4.4 生产者-消费者问题

生产者-消费者问题是一个很经典的”仓库协作”问题

有两类线程：

生产者：生产数据，送入缓冲区

消费者：负责从缓冲区中获取数据，进行处理

中间有一个共享的缓冲区：

生产者线程 -> 缓冲区 -> 消费者线程

1. 问题出现在哪

缓冲区是共享资源，多个线程可能同时访问它。

假设缓冲区只能放5个产品，会出现以下这几个问题：

情况1：缓冲区满了，生产者还想放：

缓冲区：[A, B, C, D, E]

这个时候生产者不能继续放，否则会溢出。

所有生产者应该：

1
2
3

if buffer full：
    wait
util 消费者 get

情况2：缓冲区空了，消费者还想取

缓冲区：[]

这时候消费者不能继续取，否则取不到东西。

所以消费者应该：

1
2
3

if buffer empty:
    wait
util 生产者 input

情况3：多个线程同时操作缓冲区

比如：两个生产者同时判断：

缓冲区内容是否小于等于4个

然后两个生产者同时往缓冲区放一个产品，缓冲区就超出容量了

消费者同理…

所以必须保证：同一时刻只能有一个线程真正的修改缓冲区。

这就需要互斥

2. 解决问题的核心：

第一，互斥

也就是说：取产品，放产品这些操作，在进入缓冲区的时候，需要对缓冲区上锁。

有锁，其他取/放操作就无法真正的访问缓冲区

第二，同步

生产者和消费者之间需要配合：

缓冲区满了，生产者等待
缓冲区空了，消费者等待

等条件满足了之后，再取唤醒对方

3. 怎么用信号量解决？

经典解发会使用三个信号量：

1
2
3

nutex = 1 //互斥信号量，保护缓冲区
empty = n //空位的数量，初始的缓冲区的大小为n
full = 0  //产品的数量，初始为0

mutex 是表示缓冲区的锁，1表示没上锁，0表示上锁了

1 2	进入缓冲区之前：P(mutex) 离开缓冲区之后：V(mutex)

4. 生产者的代码逻辑

伪代码如下：

while true:
    生产一个产品


    P(empty)     // 申请一个空位，如果没有空位就wait
    P(mutex)     // 有空位的话（走过了上一步），锁住缓冲区
    
    把产品放入缓冲区


    V(mutex)      // 离开临界区，解锁
    V(full)      // V(full) 产品数量加1，通知消费者可以

顺序很重要，一定会要先申请空位，再进入缓冲区

5. 消费者的代码逻辑

伪代码如下：

while true:
    P(full)      // 申请一个产品，如果没有产品就等待
    P(mutex)     // 进入临界区，锁住缓冲区

    从缓冲区取出产品

    V(mutex)     // 离开临界区，释放锁
    V(empty)     // 空位数量 +1，通知生产者可以放

    消费这个产品

先确认有产品，再进入缓冲区取

6. 如果顺序错误：

以生产者为例：先P(mutex)再P(empty)

假设缓冲区已经满了：

生产者拿到mutex，进入临界区，然后执行：P(empty)

因为此时empty = 0所以生产者阻塞了

但是生产者阻塞的时候，还拿着mutex，于是消费者要取产品，就要等待mutex

消费者取不走产品，empty永远不会增加，生产者等待empty增加，永远无法醒来

这就死锁了！！！

消费者在缓冲区为空的时候，同理

一句话总结：

先申请资源数量，再申请互斥锁；操作完共享缓冲区后，先释放互斥锁，再通知对方

4.5 读者-写者问题:

1. 问题的背景

假设有一个共享的文件

共享数据区

有两类进程/线程：

读者：只读取数据，不修改数据
写者：会修改数据

2. 核心规则：

第一、读者与读者可以同时读

第二、写者和写者不能同时写

第三、读者和写者不能同时访问

3. 第一类读者-写者问题：读者优先

它的思想是：

只要有读者在读，后来的读者也可以继续进入。

写者必须等所有读者全部离开后才能写。

读者优先，写者可能饿死

4. 需要哪些变量？

经典读者优先解法优先使用：

int readcount = 0; //当前正在访问的读者数量

semaphore mutex = 1; // 保护readcount
semaphore rw = 1; //保护共享数据区的访问

mutex

保护readcount

因为多个读者可能同时修改readcount

1 2	readcount++ readcount--

这些操作也要互斥

rw

控制共享数据区

1 2	读者整体和写者之间互斥写者和写者之间互斥

谁拿到rw谁就能访问共享数据区

5. 读者优先：读者代码

reader:
    P(mutex)            //有读者到来，锁住readcount
    readcount++
    if readcount == 1:       //第一个读者，帮其他读者锁住数据共享区
        P(rw)
    V(mutex)                //readcount的验证结束，解锁mutex

    reading the data

    P(mutex)
    readcount--
    if readcount == 0        //直到最后一个读者离开，才释放共享数据区
        V(rw)
    V(mutex)

6. 读者优先：写者代码

writer:
    P(rw)
    
    写数据

    V(rw)

写者必须独享数据共享数据区

如果读者正在读，rw已经被拿走了，写者就等

如果有写者在写，写者也等

7. 读者优先有什么问题？

最大的问题是：

写者可能饥饿

只要读者不断的来，readcount就一直不变成0。

写者一直拿不到rw

8. 第二类：写者优先

写者优先的思想是：

一旦有写者等待，后面的读者就不能再插队

已经在读的读者可以读完，但新的读者要等写者写完。

9. 第三类：公平读写

公平读写的思想是：

按照请求到达的顺序排队

谁先来谁访问

10. 重点代码：

读者优先上面有了

写者优先：

通常要用这些变量

int readcount = 0;     //正在读的读者数量
int writecount = 0;    //正在写或者正在等待的写者数量

semaphore readmutex = 1;   //protect readcount
semaphore writemutex = 1;    //protect writecount


semaphore rw = 1;        //控制共享数据区，读者群体和写者互斥
semaphore r = 1;         //控制读者入口，写者优先的关键

完整代码：

reader:
    P(r);    //关门，堵上后面来的读者
    P(readmutex);
    readcount++;
    if (readcount == 1)
       P(rw);              
    V(readmutex);
    V(r);

    reading the data

    P(readmutex);
    readmutex--;
    if (readmutex == 0)
        V(rw);
    V(readmutex);

写者：

P(writemutex);
writecount++;
if (writecount == 1){
    P(r);
}
V(writemutex);
P(rw);

写数据;

V(rw);
P(writemutex);
writecount--;
if (writecount == 0){
    V(r);
}
V(writemutex);

写者优先：第一个写者关读者入口，最后一个写者开读者入口。

公平读写：读者和写者都先过同一个queue，谁先到谁先排。

int readcount = 0;

semaphore mutex = 1;
semaphore rw = 1;
semaphore queue = 1;

读者：

P(queue);
P(mutex);
readcount++;
if (readcount == 1){
    P(rw);
}
V(mutexl);
V(queue);

读数据;

P(mutex);
readcount--;
if (readcount == 0){
    V(rw);
}
V(mutex);

写者：

P(queue);
P(rw);
V(queue);

write data;

V(rw);

4.6 睡眠理发师问题

一. 睡眠理发师问题是什么？

想象一个理发店：

1个理发师
1把理发椅
n把等待椅
若干顾客

二. 问题的核心

它要解决三个问题：

1.客户来了要不要等？

如果有空等待椅，客户坐下等待。

如果没空等待椅，顾客离开。

2.理发师没顾客时怎么办？

不能一直空转检查：

1 2	while ture: 看看有没有顾客

这样是浪费CPU，所以应该：

1	没有顾客时，理发师阻塞/睡眠

3.多个顾客同时进店怎么办？

等待椅数量是共享变量，比如：

waiting

多个顾客可能同时修改它，所以必须加锁。

三.需要的变量

int waiting = 0;    //当前等待的顾客数量
int chairs = n;    //等待椅数量

semaphore mutex = 1;    //保护waiting
semaphore customers = 0;    //等待顾客的数量
semaphore barber = 0;    //理发师是否准备好

四.理发师代码

while (true) {
    P(customers); // 没有顾客就睡觉

    P(mutex);
    waiting--;    //在等待队列中叫一个顾客
    V(barber);    //通知某个顾客：理发师准备好了
    V(mutex);

    理发;
}

五.顾客代码

P(mutex);
if (waiting < chairs) {
    waiting++;        //坐到等待椅上
    V(customers);    //通知理发师:来了一个顾客
    V(mutex);

    P(barber);        //等待理发师叫自己

    接受理发;
} else {
    V(mutex);
    离开;
}

第五章死锁

5.1 死锁的引出

什么是死锁？

定义：一个进程集合中，每个进程都在等待只能由该集合中其他一个进程才能引发的事件

死锁的常见场景：

进程推荐顺序不当： P、Q共享打印机、读卡机。P先申请打卡机再申请打印机，Q先申请打印机再申请打卡机。当执行到P、Q一人持有其中一种等待另一种的时候，发生死锁
PV操作不当： 不同进程执行到各自持有一个信号量，等另一个，死锁。
资源分配不当： m个资源被n个进程共享，每个进程需要K个，m < n * K
临时性资源(信箱)： P1等P3的信件S3，然后发S1给P2；P2等S1，发S2给P3；P3等S2，发S3给P1。循环等待，死锁

5.2 死锁产生原因和特征

5.2.1 按照资源分类

1. 按照剥夺类型分类

类型	特点	例子
可剥夺资源	获取后可被系统/其他进程强行剥夺	CPU/内存
非剥夺资源	分配后只能又进程主动释放	打印机、读卡机

注意： CPU不会死锁，CPU可以强行收回CPU，而进程不会霸占CPU

2. 按照使用期限分类

类型	特点	例子
永久性资源	可顺序重复使用	打印机、文件
消耗性资源（临时性资源）	由一个进程产生，被另一个使用短暂时间	信息、信号、I/O缓冲区数据

注意： 竞争永久性资源和临时性资源都可能导致死锁。

5.2.2 死锁产生的原因

根本原因两条：

资源竞争：多个进程竞争有限资源，资源数量不能满足所有进程同时需求。
进程推进顺序不当：进程申请和释放资源的顺序不合适。

5.2.3 死锁产生的四个必要条件（Coffman条件，1971）

死锁产生必须同时满足以下四个条件，缺一不可：

表格

条件	含义	破坏策略
① 互斥条件	资源在某段时间内仅能被一个进程占用	使资源可共享（如只读文件）
② 请求和保持条件（占有并等待）	进程因请求新资源被阻塞时，已占有的资源保持不放	一次性申请所有资源；或申请新资源前释放已有资源
③ 不剥夺条件（非抢占）	进程获得的资源在未使用完前不能被强行夺走	允许抢占（如CPU、内存）
④ 循环等待条件	存在进程-资源的循环等待链	按序分配资源（层次分配）

重要：这四个条件是必要条件（必须同时满足才会死锁），不是充分条件。即使四个条件都满足，也不一定立即死锁（还要看推进顺序）。

5.2.4 字体分配图 RAG

图的组成：

进程节点：圆圈；
资源节点：方框，方框中的黑点表示该资源的实例数量；
分配边：资源 -> 进程（实线）；
请求边：进程 -> 资源（虚线）。

死锁结论相关结论：

情况	结论
资源分配图无环	一定没有死锁
有环，且每个资源类只有1个实例	一定死锁（环是充要条件）
有环，但某些资源类有多个实例	可能死锁，也可能不死锁（环只是必要条件）

5.3 处理死锁的基本方法

方法	思想	特点
忽略死锁（鸵鸟算法）	对死锁视而不见	大多数OS采用，死锁概率低，处理代价小
预防死锁	破坏四个必要条件之一	限制严格，并发性低，资源利用率低
避免死锁	动态分配时防止进入不安全状态	限制较弱，并发现好，实现复杂
检测和解除	定时检测，发现后解除	利用率高，但是检测和解除有开销

5.3.1 预防死锁

通过破坏四个必要条件来预防：

（1）破坏互斥条件：

思路：使资源可同时访问
可行情况：只读文件、可重入代码、时钟
不可行情况：打印机、互斥锁等固有互斥资源
很多时候不可行

（2）破坏请求和保持条件

两种方法：

方法一：静态资源分配（一次性申请）

进程运行前一次性申请需要的全部资源
缺点： 资源利用率低，前面的进程不用某些资源，一直占着，后面的进程申请不到资源，饥饿。

方法二：申请新资源前释放已有资源

进程申请更多资源时，必须先释放已占有的全部资源，然后再重新申请。
缺点：反复申请释放开销大。

（3）破坏不剥夺条件

思路：若进程申请新资源失败，则其已占有的资源可以强行剥夺。
例子：CPU、内存可以被抢占
缺点：
- 已做的（已做一部分）的工作失效
- 剥夺资源有系统开销
适用于状态易于恢复和保存的资源（CPU寄存器、内存），部不适用于打印机信号量等。

（4）破坏循环等待条件

层次分配策略/有序资源分配法

给所有资源编号
进程在占有ri后，只能申请比编号i更大的资源
释放资源的时候先释放编号大的，再释放小的

为什么能防止死锁？（反证法）

假设死锁发生，则存在循环等待链：P1等P2的资源，P2等P3的资源…Pn等P1的资源。
按有序分配，若P1等的是rk1，则P1一定占有编号更小的资源；P2占有rk1，等待rk2，则 k1 < k2。
推下去：k1 < k2 < k3 < ... < kn。
但Pn占有rkn等待P1的资源，则必须有 kn < k1，矛盾！
所以不可能形成循环等待。

5.3.2 避免死锁

核心思想

不破坏四个必要条件，在资源动态分配的过程中，用算法判断这次分配是否会让系统进入不安全状态。
若安全则分配；若不安全则拒绝

关键概念

安全状态 ：系统能按照某顺序为每个进程分配其所需的最大需求资源，使每个进程可以顺利完成。这样的顺序称为安全序列。

不安全状态：

系统中不存在任何一个安全序列

不安全状态可能导致死锁，但不是必然（进程可能不会真的申请到最大需求）
避免死锁的本质：让系统始终保持在安全状态

安全序列可能不唯一，但是只要存在一个，系统就是安全的。

避免死锁的算法

（1）资源分配图机制（单实例资源）

需求边（Claim Edge）

进程 Pi → Rj 的虚线，表示进程将来可能申请该资源。
需求边在进程创建时就声明（系统需要事先知道进程可能需要的所有资源）。

算法规则

当进程 Pi 请求资源 Rj 时：

将请求边转换为分配边。
检查转换后的资源分配图是否存在环。
若不存在环，则分配是安全的，允许分配。
若存在环，则分配会导致死锁，拒绝分配。

（2）银行家算法（多实例资源）

由Dijkstra提出，类比银行放贷：银行资金有限，客户有信用额度，银行要确保放贷后还能满足其他客户的提款需求，避免资金链断裂。

数据结构

数据结构	维度	含义
`Available`	向量，m个元素	每类资源的可用数量
`Max`	n×m 矩阵	每个进程对每类资源的最大需求
`Allocation`	n×m 矩阵	每个进程当前已分配的资源数
`Need`	n×m 矩阵	每个进程还需要的资源数

核心公式：
Need[i][j] = Max[i][j] - Allocation[i][j]

资源请求算法（Request_i）

当进程 Pi 发出请求向量 Request_i：

步骤1：检查 Request_i ≤ Need_i

若否，出错（进程请求超出其声明的最大需求）。

步骤2：检查 Request_i ≤ Available

若否，Pi 必须等待（资源不够）。

步骤3：试分配（假设分配，修改数据结构）：

1	Available = Available - Request_i Allocation_i = Allocation_i + Request_i Need_i = Need_i - Request_i

步骤4：执行安全性算法检查新状态是否安全。

若安全：正式分配。
若不安全：试分配作废，恢复原来的数据，Pi 等待。

安全性算法

初始化：

1	Work = Available Finish[i] = false （对于所有进程） // 注意：如果 Allocation_i = 0（进程未分配任何资源），可设 Finish[i] = true

循环：

寻找进程 i，满足：
- Finish[i] == false
- Need_i ≤ Work（该进程所需资源系统当前能满足）

若找到这样的 i：

1 2	Work = Work + Allocation_i // 进程完成，释放资源 Finish[i] = true 回到步骤1继续找

若找不到这样的 i，则检查：
- 若所有 Finish[i] == true：系统安全。
- 若存在 Finish[i] == false：系统不安全。

重要结论 ：安全路径可能有多条。但只要存在一个安全序列，算法过程中无论怎么选分叉点，都能找到安全序列；若不存在安全序列，则任何路径都找不到。

第二章：进程与线程

2.1 处理器概述

2.1.1 单处理器和多处理器系统

单处理器系统

多处理器系统

计算机系统结构分类

1. SISD：单指令流单数据流

2. SIMD：单指令流多数据流

3. MISD：多指令流单数据流

4. MIMD：多指令流多数据流

多处理器和多核处理器

多处理器：

多核处理器：

2.1.2 寄存器

2.1.3 特权指令和非特权指令

2.1.4 处理器状态

2.1.5 程序状态字寄存器（PSW）

2.1.6 x86总体架构

2.2 计算机的启动

传统启动流程（BIOS）

2.3 OS中的中断处理

2.3.1 中断的概念

2.3.2 中断分类

2.3.3 中断、异常和系统调用

2.3.4 中断处理机制

同步性和原子性

2.4 进程的定义和描述

2.4.1 程序的顺序执行

2.4.2 程序的并发执行

2.4.3 程序并发执行的条件（Bernstein 条件）

2.4.4 进程的引入

2.4.5 进程的特征

2.4.6 进程的描述

2.5 进程的状态及转换

2.5.1 三态模型

2.5.3 五态模型

第2章 进程与线程

2.1 处理器概述

2.1.1 单处理器与多处理器系统

计算机系统结构分类（Flynn 分类法）

多处理器 vs 多核处理器

2.1.2 寄存器

2.1.3 特权指令与非特权指令

2.1.4 处理器状态

2.1.5 程序状态字寄存器（PSW）

2.1.6 x86 总体架构

2.2 计算机的启动

传统启动流程（BIOS 方式）

现行启动规范

可信计算启动信任链

2.3 OS 中的中断处理

2.3.1 中断的概念

2.3.2 中断分类

2.3.3 中断、异常与系统调用

2.3.4 中断处理机制

同步与原子性

2.4 进程的定义与描述

2.4.1 程序的顺序执行

2.4.2 程序的并发执行

2.4.3 程序并发执行的条件（Bernstein 条件）

2.4.4 进程的引入

2.4.5 进程的特征

2.4.6 进程的描述

2.5 进程的状态及转换

2.5.1 三态模型

2.5.2 五态模型

2.5.3 七态模型（含挂起状态）

2.6 进程控制管理和组织

2.6.1 进程创建

POSIX共享内存

第三章：调度

调度是多道程序操作系统的基础

3.1 调度的基本概念

1. 调度队列

操作系统中维护了一组进程调度队列

作业队列：系统中所有进程的集合

就绪队列：所有驻留在内存，处于就绪状态，等待调度执行的进程集合。

设备队列：等待某个I/O设备的进程集合

2.调度的层次

调度程序：负责挑选就绪进程的 内核 模块

第2章进程与线程

`POSIX`共享内存

调度程序：负责挑选就绪进程的内核模块

3.3.1 先来先服务算法（`FCFS`）：