操作系统

操作系统是一个系统软件，是用户与计算机硬件之间的接口，计算机系统资源的管理（资源复用、虚化、抽象）

多道程序运行：把多个作业一起放在主存，交替运行共享处理器

操作系统分类

分时操作系统
分成很短的时间片，让用户交替使用
批处理操作系统
单道多道批处理
实时操作系统
嵌入式系统：比如一些电气设备

操作系统的基本特征

并发性：两个或多个时间在同一时间间隔内发生
活动的协调、资源共享
共享性：对多个并发执行进程
虚拟性：例如：VM虚拟机
异步性：程序执行的时间和顺序时行时停

过程调用和系统调用

调用方\被调用方	过程调用	系统调用
过程调用	可以，函数嵌套函数	可以，写入打印等就是过程调用请求系统调用
系统调用	可以，系统调用调用自己的内核函数	不可以，系统调用不能嵌套

系统调用：用操作系统的户程序向内核发请求的唯一合法入口

操作系统的运行环境

系统初启动程序：时钟中断，外部中断驱动
服务程序：用户态，中断驱动
系统内部模块：管态运行，内核态，中断驱动

//内核程序
SYSCALL_DEFINE1(mysyscall, int, num) {
    return num + 100;   // 这是内核程序！
}

//系统调用
#define __NR_mysyscall 548

//用户程序
syscall(548, 20);

内核程序：在内核里，真正做事。

系统调用：是接口、门，连接用户和内核。

关系：一个系统调用，背后一定对应一段内核程序。

openeuler自定义系统调用

第二章进程与线程

计算机最底层只有一个或多个 CPU，CPU 本质上只会不断做一件事：

取指令 → 译码 → 取操作数 → 执行指令

CPU 怎么让这么多程序“同时”运行？

这一章就是围绕这个问题展开的：

硬件基础
  ↓
中断机制
  ↓
进程
  ↓
进程状态与调度
  ↓
进程切换
  ↓
进程间通信
  ↓
线程
  ↓
安全问题：隐蔽通道

1.处理器与多核

单处理器系统只有一运算处理器；多处理器有多个。后来出现了多核处理器（在一块CPU芯片上放多个执行核心）。多核比多CPU更紧凑、成本更低、功耗更小。

初学者可以这样理解：

1
2
3

单核 CPU：一个厨师
多核 CPU：一个厨房里多个厨师
多处理器：多个厨房各有厨师

概念	含义	例子
并发	看起来同时做，其实可能轮流做	单核 CPU 快速切换多个任务
并行	真的同时做	多核 CPU 同时运行多个线程

2.用户态和内核态

用户态权限低，内核态权限高

用户程序权限低，那它怎么请求操作系统帮它做事？

答案就是后面的系统调用。

2.1 特权指令

关中断、访问 I/O 设备、设置定时器等列为特权操作，并且用户态程序只能执行非特权指令

特权指令只能在内核态由操作系统执行

3.中断：唤醒操作系统的方式

操作系统不是一直主动盯着所有事情，而是很多时候由事件触发

名称	谁触发	是否主动	例子
中断	外部硬件	被动	键盘输入、磁盘完成 I/O、定时器
异常	当前程序出错	被动	除 0、非法访问内存、缺页
系统调用	用户程序主动请求	主动	read、write、fork

三者的关联：最终都可能通过中断机制进入内核态

3.1 Fault 和 Trap 的区别

Fault：保存的是触发异常的那条指令地址，处理完后可能重新执行这条指令，例如：缺页异常

Trap：保存的是下一条指令的地址，处理完成之后不再重新执行原指令，例如：断点调试、系统调用

3.2 定时器中断

定时器是 OS 回收控制的重要方式，可以用于分时 OS 调度，避免死循环或恶意程序非法独占 CPU。

PSW 程序状态字

它用来记录：

当前 CPU 工作状态
能否执行特权指令
程序执行顺序
中断屏蔽信息
条件码

可以把 PSW 理解成 CPU 当前状态的“控制面板”。

它告诉 CPU：

现在是用户态还是内核态？
中断能不能响应？
下一条指令在哪里？
上一次运算结果有没有溢出？

这和进程切换也有关：
每个进程运行时都有自己的状态，切换进程时也要保存和恢复这些状态。

4.进程

程序本身只是静态文件，比如硬盘上的 qq.exe、chrome.exe。进程是程序真正运行起来后的动态实例。

进程是程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。

进程和程序：

对比点	程序	进程
性质	静态	动态
是否运行	不一定运行	正在运行或等待运行
生命周期	可长期保存	创建、运行、阻塞、终止
组成	指令集合	程序段、数据段、PCB 等
管理者	文件系统	操作系统

5. PCB

PCB 是描述和管理进程的数据结构，是进程存在的唯一标志；操作系统通过 PCB 了解进程状态、断点信息，并进行调度、控制和管理。

可以把 PCB 理解为进程档案：

PCB =
  进程 ID
  当前状态
  程序运行到哪里了
  寄存器现场
  优先级
  使用了哪些资源
  父子进程关系

所以：

程序能不能运行，靠 CPU；

进程能不能被管理，靠 PCB。

6. 进程状态

最基本的三态模型：

1	就绪态 -> 运行态 -> 阻塞态

就绪态：除了CPU，其他资源都准备好了
运行态：正在CPU上执行
阻塞态：等待某件事，比如等待 I/O 完成

状态之间的联系

就绪 → 运行：调度程序分配 CPU
运行 → 就绪：时间片用完
运行 → 阻塞：等待 I/O 或事件
阻塞 → 就绪：等待的事件发生

注意：
阻塞态不能直接变运行态。

7. 进程控制：创建、终止、阻塞、唤醒

进程控制包括进程创建、终止、阻塞与唤醒等，一般由操作系统内核原语实现。原语是在执行期间不可分割的一段程序

进程创建的大致过程：

申请空闲 PCB
  ↓
分配资源
  ↓
初始化 PCB
  ↓
放入就绪队列

阻塞和唤醒的区别

操作	谁发起	状态变化
阻塞	当前进程自己	运行态 → 阻塞态
唤醒	其他进程或中断处理程序	阻塞态 → 就绪态

7.1 五态模型

三态模型只描述运行过程，不够完整，所以加入：

1 2	新建态 New 终止态 Terminated

五态模型：

1
2
3

新建 → 就绪 → 运行 → 终止
          ↑      ↓
        阻塞 ← 等待事件

新建态

进程刚刚被创建，但还没进入就绪队列。
比如 PCB 正在初始化，资源还没完全分配。

终止态

进程已经结束，OS 正在或即将回收资源。
比如程序执行完、异常退出、被父进程终止。

7.2 七态模型

当系统资源紧张，内存不够，OS 可能会把某些进程暂时换出到磁盘。

PPT 里说，挂起是把某些进程切换到静止状态，对换到磁盘镜像区中，暂时不参与进程调度，以平滑系统负荷。

也就是说：

1	挂起 = 暂时移出内存/不参与调度

这不是普通阻塞。

状态	原因	是否主要和内存/调度有关
阻塞	等事件	等待 I/O、锁、信号等
挂起	被 OS/用户暂时移出活动集合	常和内存不足、系统负载、调试有关

七态模型里会出现：

活动就绪
活动阻塞
挂起就绪
挂起阻塞

理解方式：

1 2	就绪/阻塞：它等不等事件活动/挂起：它在不在内存、参不参与调度

8. 进程切换

多个进程共享 CPU，必须切换。

进程切换就是中断处于运行态的进程，让出处理器，并完成上下文切换：保存老进程状态，装入新进程状态。

所谓上下文，就是“进程运行到一半所需的全部环境”。

保存旧进程寄存器、PC、栈等
  ↓
修改旧进程 PCB
  ↓
选择新进程
  ↓
恢复新进程上下文
  ↓
新进程继续运行

9. 进程间通信

进程之间通常是隔离的。隔离保证安全，那么如何进行通信呢？

IPC，进程间通信，IPC是进程之间的信息交换，是一种协作机制。原因包括信息共享、提高运算速度、模块化和方便性

两大基本模块

1
2

消息传递
共享内存

消息传递安全、清晰，但可能慢一些；共享内存速度快，但容易产生同步问题。

比如两个进程同时改同一个变量，就可能出现“时间有关的错误”。这就需要信号量、锁、互斥等同步机制。

10. 线程

线程是比进程更轻量的执行单位，由于进程的创建和切换成本较高，于是引入线程来减少程序并发执行所付出的时空开销，使操作系统具有更好的并发性。

进程和线程核心区别

对比点	进程	线程
资源	拥有独立资源	基本不拥有资源
地址空间	进程间通常隔离	同一进程内线程共享
调度	传统 OS 中进程可调度	现代 OS 中线程是调度基本单位
开销	创建、切换开销大	创建、切换开销小
通信	IPC 较复杂	同进程线程共享数据，通信方便

11.线程模型：用户级线程和内核级线程

11.1 用户级线程

用户级线程有用户态线程库管理，操作系统看不见

优点：快，不需要频繁进入内核

缺点：一个线程阻塞，可能导致整个进程阻塞

11.2 内核级线程

内核级线程由操作系统管理

优点：一个线程阻塞，不影响同进程其他线程；可以更好利用多核

缺点：创建和切换需要内核参与，开销较大

11.3 多线程映射模型

课件中讲了三种：

1
2
3

多对一：多个用户线程 → 一个内核线程
一对一：一个用户线程 → 一个内核线程
多对多：多个用户线程 → 多个内核线程

Linux、Windows 常见的是一对一模型。
一个用户线程对应一个内核线程，能利用多核，但线程太多会增加系统开销

第三章调度

这一章可以按这条主线理解：

为什么需要调度
  ↓
调度队列
  ↓
三级调度
  ↓
调度性能指标
  ↓
作业/进程/线程调度
  ↓
具体调度算法
  ↓
实时、多处理器调度
  ↓
UNIX / Solaris / openEuler / Windows 实例
  ↓
算法评估

一句话总结：

调度就是操作系统在多个可运行任务中，按照某种策略选择“下一个使用 CPU 的任务”。

3.1 调度的基本概念

为什么需要调度
  ↓
调度队列
  ↓
三级调度
  ↓
调度性能指标
  ↓
作业/进程/线程调度
  ↓
具体调度算法
  ↓
实时、多处理器调度
  ↓
UNIX / Solaris / openEuler / Windows 实例
  ↓
算法评估

3.1.1 调度队列

操作系统维护一组进程调度队列，包括作业队列、就绪队列、设备队列

1
2
3

作业队列：系统中所有作业/进程的集合
就绪队列：已经在内存中，等待 CPU 的进程
设备队列：等待某个 I/O 设备的进程

3.1.2 调度的三个层次

高级调度是长期调度，低级调度是短期/CPU调度，中级调度是交换调度

高级调度、作业调度、长程调度、Job Schedule
从外存后备队列里面选择作业进入内存成为进程，主要影响：系统中允许同时多少个作业、多道程序的道数
1
2
3
4
5
6
7
8
外存后备队列：J1 J2 J3 J4
高级调度选择 J1 J3
↓
为它们分配内存和资源
↓
创建进程
↓
进入就绪队列
低级调度、进程调度、短程调度、CPU Schedule
从绪队列里面选择进程，将CPU使用权交给该进程
1
2
3
4
就绪队列：P1 P2 P3
CPU 空闲
低级调度选择 P2
P2 进入运行态
中级调度、交换调度、中程调度、Middle-term Schedule
内存不够时，哪些进程暂时换出到磁盘，哪些进程再回到内存
1
2
3
4
5
6
7
内存紧张
↓
中级调度把某些阻塞/就绪进程换出
↓
变成挂起阻塞或挂起就绪
↓
需要时再换入内存

3.1.3 三种调度和进程状态的关系

高级调度：
创建态/后备作业 → 就绪态

低级调度：
就绪态 → 运行态

中级调度：
就绪态 ↔ 挂起就绪态
阻塞态 ↔ 挂起阻塞态

3.1.4 调度性能评价指标

CPU利用率
响应时间
周转时间 = 等待时间 + 运行时间
带权周转时间（= 周转时间 / 实际需要运行的时间）
吞吐率（单位时间内完成的作业数量）
公平性（避免饥饿和老化aging）

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

3.2.1 作业

作业是用户在一次解题或事务处理中要求计算机系统所做工作的集合，包括用户程序、数据和命令等

作业是任务实体
进程是完成任务的执行实体

作业：我要系统完成什么任务
进程：系统真正派出去干活的执行单位

作业 = 订单
进程 = 负责执行订单的员工

没有作业，进程不知道干什么
没有进程，作业没法真正执行

作业的四种状态：提交（输入系统）-后备（已经进入外存，等待作业调度）-运行（进入内存，参与CPU的竞争（也包含就绪-运行-阻塞））-完成

JCB：作业控制块（类似PCB是进程存在的唯一标志）

3.2.2 进程调度

主要工作内容：
记录所有进程状态、优先数、资源情况
从就绪队列中选择一个进程
分配或回收处理机

抢占式和非抢占式 （进程运行时能否抢占其CPU）

进程调度发生的时机

运行态 → 等待态 	I/O请求：运行->等待
运行态 → 就绪态	时间片用完：运行 -> 就绪
等待态 → 就绪态	I/O完成：等待-> 就绪
进程终止		 程序结束：运行->终止

分派器 Dispatcher

调度器负责“选谁”，分派器负责“真正交接 CPU”

调度器说：

下一个运行 P2

分派器就做：

保存 P1 上下文
恢复 P2 上下文
切回用户态
跳到 P2 上次停下的位置继续执行

这里会产生一个概念：

1	分派延迟 = 停止一个进程到启动另一个进程所花的时间

3.2.3 线程调度

线程是CPU调度的基本单位，用户级线程由线程库调度OS看不见，内核级线程由内核调度OS可操控

PCS:同一个进程内部的用户级线程竞争CPU

SCS:系统中内核级线程竞争CPU

3.3 调度算法

1.FCFS：先来先服务

2.SJF：短作业优先

3.SRTF：最短剩余时间优先(抢占式SJF)
如果新来的进程比当前进程剩余时间更短，就抢占当前进程。

4.优先级调度：将处理机分配给就绪队列中优先级最高的进程；相同优先级按 FCFS
分静态优先级和动态优先级

5.RR(抢占)：时间片轮转

6.HRRF(非抢占)：高响应比优先 (响应比 = 1 + 等待时间 / 估计运行时间)
综合 FCFS 和 SJF

7.多级队列调度
多级反馈队列调度(抢占)

8.公平分享调度

实时调度
多处理器调度

RR(时间片轮转)

每次调度把 CPU 分配给队首进程，并让它执行一个时间片，时间片用完就放到就绪队列末尾

假设时间片q = 2

进程	到达时间	运行时间
A	0	5
B	0	3
C	0	1

调度：

A 运行 2，剩 3
B 运行 2，剩 1
C 运行 1，完成
A 运行 2，剩 1
B 运行 1，完成
A 运行 1，完成

时间轴：
0  2  4 5  7 8 9
|A |B |C|A |B|A|

时间片太大则退化为先来先服务；时间片太小则调度频繁，产生大量上下文切换

公平分享调度算法

采用 RR 时，如果多个用户拥有的进程数不同，那么用户获得 CPU 的比率不同，这会造成某些用户响应比过低；公平分享调度就是基于进程组分配 CPU 时间。

1 2	不是让每个进程公平而是让每个用户/进程组公平

计算公式

CPUj(i) = CPUj(i-1) / 2

GCPUk(i) = GCPUk(i-1) / 2

Pj(i) = Basej + CPUj(i)/2 + GCPUk(i)/(4Wk)

假设用户1拥有进程 A 用户2拥有进程B C

最终结论：执行顺序A-B-A-C-A-B-A-C用户对CPU使用是公平的

多级反馈队列调度

仅当第 1 个队列为空时，才调度第 2 个队列；仅当前面所有更高优先级队列都为空时，才调度第 i 个队列。并且如果低优先级队列正在运行时，有新进程进入更高优先级队列，那么高优先级进程会抢占当前进程。

3.4 调度实例

UNIX：多级反馈队列思想
Solaris：多类别 + 优先级 + RR
openEuler/Linux：CFS + 调度类 + 红黑树
Windows：线程调度 + 抢占式优先级

3.4.1 UNIX调度实例

UNIX 采用的是类似多级反馈队列的思想，调度时先从最高优先级队列中选择进程；如果同一优先级有多个进程，就选择就绪状态最久的那个。

多个优先级队列
  ↓
先看高优先级
  ↓
同级别按等待时间/FCFS
  ↓
运行一个时间片
  ↓
可能被剥夺

UNIX优先级大致分三层
实时优先级 > 内核优先级 > 分时优先级

3.4.2 Solaris调度

Solaris 是基于优先级的线程调度

每个类别有自己的调度算法，调度器会把类别优先级转换成全局线程优先级，然后选择全局优先级最高的线程执行

先判断线程属于哪一类
  ↓
计算它的全局优先级
  ↓
选择最高优先级线程
  ↓
同优先级用 RR

3.4.3 openEuler / Linux 调度

现代 Linux 类系统常用 CFS。

CFS核心思想：每个进程按权重公平地获得CPU时间

核心指标 vruntime:虚拟运行时间 调度时选择该指标最小的进程

参数 nice 值越低优先级越高分到的CPU比例更多

CFS 使用红黑树，自平衡二叉树；vruntime 小的放左边，vruntime 大的放右边，最左边节点就是下一个要运行的任务

3.4.4 多核调度问题

openEuler/Linux 还要考虑多核 CPU。

多核下有几个问题：

缓存一致性
缓存亲和性
核间数据共享
负载均衡

其中最重要的是两个：

CPU 亲和性

如果一个进程一直在同一个 CPU 核上运行，它的缓存数据可能还在这个核附近，继续运行会更快。

1
2
3

同一个 CPU 上继续跑
→ cache 命中率高
→ 性能好

负载均衡

如果 CPU0 很闲，CPU1 很忙，就需要迁移进程。

1
2
3

CPU1 上进程太多
CPU0 空闲
→ 把部分进程迁移到 CPU0

但这和亲和性有矛盾：

1 2	迁移有利于负载均衡不迁移有利于缓存亲和性

所以多核调度要在二者之间平衡。

3.4.5 Windows 调度

Windows 调度对象主要是线程，不是进程。实现了基于优先级的抢占式多处理器调度系统，总是运行最高优先级的就绪线程

第四章同步

并发访问会出错
  ↓
引出同步与互斥
  ↓
提出临界资源和临界区
  ↓
尝试软件方法实现互斥
  ↓
再用硬件方法和锁实现互斥
  ↓
引入信号量 PV 操作
  ↓
解决经典同步问题
  ↓
引入管程
  ↓
拓展到现代同步：内存屏障

进程同步研究的是：多个进程/线程并发访问共享资源时，如何保证结果正确

4.1 同步与互斥

同步：多个进程并发访问共享变量，如果没有控制执行顺序，就可能出现资源状态不一致。

直接制约（同步）和间接制约（互斥）

概念	关注点	例子
同步	执行顺序	先生产，后消费
互斥	不能同时访问	同一时刻只能一个进程改共享变量

4.1.1 临界资源与临界区

临界资源：一段时间内仅允许一个进程使用的资源，称为临界资源。例子有打印机、共享变量。

临界区：进程中访问临界资源的那段代码，称为临界区。

进入区：申请进入临界区
临界区：访问共享资源
退出区：释放临界资源
剩余区：做其他事情

临界区访问原则：

空闲让进：不能出现资源空闲，但需要该资源的进程不进去
忙则等待：如果已经有进程进入临界区，其他进程必须等待
有限等待：一个进程请求进入临界区之后不能让其一直等待
让权等待：如果进程暂时进不了临界区，最好让其释放CPU而不是一直占用浪费资源

4.2 互斥的实现方法

互斥实现分成三类：

1
2
3

软件方法
硬件方法
更高级的抽象方法

4.2.1 turn 轮流进入

思想：

1
2
3

设置一个 turn 变量
turn = 0 表示允许 p0 进入
turn = 1 表示允许 p1 进入

P0:
while (turn != 0);
临界区;
turn = 1;
剩余区;

它能保证：

1	同一时刻不会两个进程都进入临界区

但问题是：必须严格轮流。

比如 P0 用完后把 turn 改成 1，但 P1 此时根本不想进临界区。
这时 P0 想再次进入，却发现：

turn = 1

于是 P0 只能等 P1。
这就违反了：

空闲让进

因为临界区明明空着，但 P0 进不去。

4.2.2 先检查对方 flag ，在设置自己flag

思想：

1	flag[i] 表示 Pi 是否在临界区

P0：
while (flag[1]);
flag[0] = true;
临界区;
flag[0] = false;

4.2.3

改进思路：

1 2	我先声明：我要进临界区再看对方是不是也要进

P0：

flag[0] = true;
while (flag[1]);
临界区;
flag[0] = false;

P1：

flag[1] = true;
while (flag[0]);
临界区;
flag[1] = false;

这次不会两个同时进入了。

但可能出现：

P0 设置 flag[0] = true
P1 设置 flag[1] = true
P0 看到 flag[1] = true，等待
P1 看到 flag[0] = true，等待

于是双方都等对方，谁也进不去。

这违反了：

1	空闲让进 / 推进原则

4.2.4

Dekker 算法把前面的两个思想结合起来：

1 2	flag：表示是否想进入临界区 turn：表示冲突时该让谁进入

它解决的是：

1
2
3

既不能同时进
也不能双方都卡住
还不能强制无意义轮流

大致思想：

我想进：flag[i] = true
如果对方也想进：
    看 turn
    如果轮不到我：
        我先撤回 flag[i]
        等 turn 变成我
        再重新声明想进
进入临界区
退出时把 turn 给对方，并撤回 flag

你可以把它理解成：

1 2	flag 管“意愿” turn 管“冲突时谁优先”

4.2.5

Peterson 算法更简洁，也是经典两个进程互斥软件算法。

P0：

flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
临界区;
flag[0] = false;

P1：

flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
临界区;
flag[1] = false;

核心意思是：

1	我想进临界区，但如果对方也想进，我愿意让对方先

如果两边同时想进，最后写入的 turn 会决定谁等待，另一个进入。

PPT三个错误版本分别破坏了不同点：

PPT 问题代码	错在哪里	后果
去掉 `if(turn != i)`	不管是不是自己优先，都退让	破坏 turn 的裁决作用，可能推进异常
等 `flag[j]` 而不是等 `turn`	退让后等对方“不想进”，不是等“轮到我”	可能等待过久，削弱公平推进
外层用 `while(turn != i)`	主要靠 turn 决定能否进入	退化成强制轮流，违反空闲让进

4.3 硬件方法实现互斥

关中断

因为在单核 CPU 上：

没有中断
  ↓
OS 很难抢回 CPU
  ↓
当前进程不会被切走
  ↓
其他进程无法同时进入临界区

问题：

效率低
不适合多处理器
安全性差

4.3.1 原子指令方法

TS 指令：Test-and-Set

TS 指令的功能可以理解成：

boolean TS(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}

它做了两件事：

1 2	读取 lock 原来的值把 lock 设置为 true

关键是：

这两个动作由硬件保证不可分割。

共享变量：

1	boolean lock = false;

含义：

1 2	lock == false：资源空闲 lock == true：资源被占用

进入临界区：

while (TS(&lock));

临界区;

lock = false;

Swap / Exchange 指令

Swap 指令的功能是交换两个变量的值：

Swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

这个交换动作也是原子的。

用法大致是：

boolean lock = false;
boolean key;

do {
    key = true;
    while (key != false)
        Swap(&lock, &key);

    临界区;

    lock = false;

    剩余区;
} while (true);

理解方式：

1
2
3

key 是本进程想拿锁的意愿
lock 是共享锁状态
Swap 把 key 和 lock 原子交换

4.3.2 互斥锁

互斥锁通常用一个变量表示资源状态：

1 2	0：资源可用，开锁 1：资源已占用，关锁

使用形式：

lock(w);

临界区;

unlock(w);

lock(w) {
    while (w == 1);
    w = 1;
}

unlock(w) {
    w = 0;
}

不过要注意：
真正实现时，while(w == 1); w = 1; 这两步也必须通过原子操作保护，否则又会出现两个进程同时拿锁的问题。

4.3.3 自旋锁

自旋锁的意思是：

1	如果锁被占用，不睡眠，而是在原地循环等待

也就是：

1
2
3

while (拿不到锁) {
    不断尝试;
}

若预计等待时间很短，短到小于两次上下文切换时间，使用自旋锁是划算的，自旋锁适合多核处理器不适合单核处理器

4.4 信号量

前面软件方法的缺点是忙式等待浪费 CPU，并且把同步责任推给各个进程会增加编程负担；因此 Dijkstra 提出了信号量和 P、V 操作

4.4.1 信号量的定义

信号量可以先理解成：

1	一个整数值 + 一个等待队列

PPT 中定义信号量由两个成员组成：

1	S = (s, q)

其中：

1 2	s：整数变量，表示资源数量或等待情况 q：等待队列，存放被阻塞的进程

并且信号量的值只能通过两个操作改变：

P 操作，也叫 wait
申请一个资源

P(S) {
    S.s = S.s - 1;

    if (S.s < 0) {
        将当前进程设置为等待状态;
        将当前进程放入 S.q 队列;
        转调度程序;
    }
}
先把资源数减 1
如果减完后仍然 >= 0，说明申请成功
如果减完后 < 0，说明资源不够，当前进程阻塞等待


V 操作，也叫 signal
释放一个资源

V(S) {
    S.s = S.s + 1;

    if (S.s <= 0) {
        从 S.q 等待队列中移出一个进程;
        将它设置为就绪状态;
        插入就绪队列;
    }
}
先把资源数加 1
如果加完后 <= 0，说明之前有人在等
于是唤醒一个等待进程

将s初值设为1就可以实现互斥

4.4.2 用信号量实现前驱关系

某个操作必须在另一个操作之前完成P1 完成后，P2 才能执行

P1() {
    执行 P1;
    V(S);
}

P2() {
    P(S);
    执行 P2;
}

多个前驱,就把都放在前，用不同信号量表示

P(S3);
P(S4);
P(S5);
执行 P6;
//改变前面三个P的顺序不影响结果，只影响阻塞在哪一步

类型	初值	作用	常见位置
互斥信号量	1	保证临界区一次只进一个	临界区前 P，临界区后 V
同步信号量	0 或资源数	保证先后顺序或资源数量	前驱等待处 P，前驱完成处 V

4.5 进程同步问题

4.5.1 生产者消费者问题（有界缓冲区问题）

有若干生产者和消费者，共享一个大小为 n 的缓冲区：

1 2	生产者：生产产品 → 放入缓冲区消费者：从缓冲区取产品 → 消费产品

限制条件：

1
2
3

缓冲区满：生产者不能再放，必须等待
缓冲区空：消费者不能再取，必须等待
缓冲区本身：同一时刻只能一个进程操作

所需信号量

1
2
3

semaphore empty = n; 	//空缓冲区数量，初值为n
semaphore full = 0;		//满缓冲区数量，初值为0
semaphore mutex = 1;	//互斥信号量，初值为1

生产者代码

Producer() {
    while (true) {
        produce_item();

        P(empty);
        P(mutex);

        put_item_into_buffer();

        V(mutex);
        V(full);
    }
}

消费者代码

Consumer() {
    while (true) {
        P(full);
        P(mutex);

        get_item_from_buffer();

        V(mutex);
        V(empty);

        consume_item();
    }
}

P操作的顺序不能颠倒，先判断资源条件是否满足，在进入临界区

假如颠倒：

生产者先 P(mutex)，拿到锁，mutex = 0
然后 P(empty)，发现 empty = 0，于是阻塞

生产者阻塞时还占着 mutex
消费者想取产品，也需要 P(mutex)
但 mutex 被生产者占着
消费者进不去
生产者等消费者取走产品释放 empty
消费者等生产者释放 mutex

发生死锁

同步 P 要放在互斥 P 前面；否则可能拿着锁去等待条件，导致别人无法改变条件。

4.5.2 读者写者问题

多个进程共享一个数据对象，有两类进程写者（只读数据），读者（修改数据）

约束是：

1
2
3

多个读者可以同时读
写者必须独占
写者写时，不能有读者或其他写者

读者优先

只要已经有读者在读，后续读者可以继续进入，写者需要等所有读者退出

int readcount = 0; // 当前正在读的读者数量
semaphore rmutex = 1; //保护readcount的互斥锁
semaphore wmutex = 1; //控制读写互斥

Reader() {
	p(rmutex);
    if (readcount == 0)
        p(wmutex);
    readcount++;
    V(rmutex);
    
    read_data();
    
    p(rmutex);
    readcount--;
    if (readcount == 0)
        V(wmutex);
    V(rmutex);
}
第一个读者进入时：P(wmutex)，阻止写者
后续读者进入时：不用再 P(wmutex)，可以一起读
最后一个读者离开时：V(wmutex)，允许写者进入
    
Write(){
    P(wmutex);
    
    write_data();
    
    V(wmutex);
}

rmutex 不是表示读者数量，它只是用来互斥访问共享变量 readcount；真正表示读者数量的是 readcount

4.5.3 哲学家进餐问题

5 个哲学家围桌而坐
每两个哲学家之间有一支筷子
哲学家要吃饭必须拿到左右两支筷子
吃完后放下筷子

如果每个哲学家都这样写

P(chopstick[i]);
P(chopstick[(i + 1) % 5]);

eat();

V(chopstick[i]);
V(chopstick[(i + 1) % 5]);

可能出现死锁，所有人同时拿起左筷子全部等待右筷子

解决方法1：最多允许四个人同时尝试拿起筷子

1 2	semaphore room = 4;//允许拿筷子的名额 semaphore chopstick[5] = {1,1,1,1,1};

Philosopher(i) {
    while (true) {
        think();
        
        P(room);
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5]);

        eat();

        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        V(room);
    }
}

最多 4 个人拿筷子
至少有 1 个人没参与竞争
因此不可能形成 5 人环形等待

解决方法2：资源分级法

给筷子编号0到4，规定每个哲学家只能先拿编号小的筷子，再拿编号大的筷子，释放的时候相反。这样可以破坏循环等待

4.5.4 睡眠的理发师问题

一个理发师
一把理发椅
N 把等待椅
没有顾客时理发师睡觉
顾客来时，如果有空位就等；没空位就离开

semaphore customers = 0: 等待理发的顾客数，初值为0
semaphore barbers = 0：等待理发师服务的顾客数/理发师准备好，初值 0
semaphore mutex = 1：保护 count，初值 1
int count = 0：等待顾客数

Barber(){
    while(true){
        P(customers);
        
        P(mutex);
        count--;
        V(barbers);
        V(mutex);
        
        cut_hair();
    }
}
P(customers)：没有顾客就睡眠
count--：叫一个等待顾客来理发
V(barbers)：通知顾客，理发师准备好了
cut_hair：理发

Customer(){
    P(mutex);
    
    if(count < N){
        count++;
        V(customers);
        V(mutex);
        
        P(barbers);
        get_haircut();
    } else {
        V(mutex);
        leave();
    }
}
先检查等待椅是否有空位
有空位：count++，通知理发师有顾客
没空位：释放 mutex 后离开

count 是普通变量，用来判断等待椅有没有满；
customers 是信号量，用来让理发师“没顾客就睡，有顾客就醒”。

4.6 管程

管程就是把共享资源和访问共享资源的操作封装在一起，并自动保证同一时刻只有一个进程进入

它解决的是信号量编程容易出错的问题。

信号量方式像这样：

1 2	每个进程自己写 P/V 程序员自己保证顺序正确

管程方式像这样：

1
2
3

把共享数据放进一个“受保护的房间”
进程只能通过管程提供的函数访问它
一次只允许一个进程进房间

管程不是单纯一个变量，也不是单纯一个函数，而是一种封装结构。

//管程 = 共享数据 + 操作共享数据的函数 + 同步机制
monitor Buffer {
    共享缓冲区;
    条件变量;

    put() { ... }
    get() { ... }
}  
//生产者只能调用Buffer.put();
//消费者只能调用Buffer.get();

同一时刻最多只有一个进程在管程内执行。

所以进入管程函数时，不需要程序员手动写：

1
2
3

P(mutex);
...
V(mutex);

管程机制会自动保证互斥。

4.6.1 条件变量 condition

调用管程的进程无法进行用于阻塞的机制，配合 wait 和 signal 使用

condition notFull;
condition notEmpty;

C.wait();
//当前进程因为条件不满足，阻塞自己
//并释放管程，让其他进程可以进入管程

C.signal();
//唤醒一个等待在条件变量 C 上的进程

条件变量和信号量的区别

对比点	信号量	条件变量
是否有计数值	有	没有累计计数
signal/V 没人等时	值会增加	信号丢失
用途	资源计数、同步、互斥	管程内部等待某条件
是否自带互斥	不自带，要配合使用	管程本身保证互斥

举个区别：

V(S);

如果没人等，S 的值会 +1，以后有人 P(S) 可以直接通过。

但：

1	notEmpty.signal();

如果此时没有消费者在等，这个 signal 就没了，不会保存给未来的消费者。

signal 会带来“谁留在管程里继续执行”的问题，Hoare 方法让被唤醒者立即执行。Hansen 方法规定 signal 必须是过程体最后一个操作

管程解决生产者消费者问题

monitor BoundedBuffer {
    item buffer[N];
    int count = 0;
    condition notFull, notEmpty;

    void put(item x) {
        if (count == N)
            notFull.wait();

        放入产品;
        count++;

        notEmpty.signal();
    }

    item get() {
        if (count == 0)
            notEmpty.wait();

        取出产品;
        count--;

        notFull.signal();

        return 产品;
    }
}

//没有显式写
//P(mutex);
//V(mutex);

4.7作业题

4.7.1 多个表格读写者问题

有P1、P2、P3三类进程（每类进程都有K个）共享一组表格F（F有N个），P1对F只读不写，P2对F只写不读，P3对F先读后写。进程可同时读同一个Fi（0≤i≤ N）；但有进程写时，其他进程不能读和写。

用信号量和P、V操作给出方案
对方案的正确性进行分析说明
对访问的公平性进行分析

semaphore rwmutex[N];//读写互斥
semaphore rmutex[N];//保护readcount
semaphore queue[N];//在统一入口处公平竞争（排队）
int readcount[N];//读者计数

for (int i = 0; i < N; i++) {
    rwmutex[i] = 1;
    rmutex[i] = 1;
    queue[i] = 1;
    readcount[i] = 0;
}

readlock(i){
    P(queue[i]);
    P(rmutex[i]);
    
    readcount++;
    if (readcount[i] == 1){
        P(rwmutex[i]);
    }
    
    V(rwmutex[i]);
    V(queue[i]);
    
}

readunlock(i){
    P(rmutex[i]);
    
    readcount[i]--;
    if(readcount[i] == 0){
        V(rwmutex[i]);
    }
    
    P(rmutex);
}

writelock(i){
    P(queue[i]);
    P(rwmutex[i]);
    V(queue[i]);
}

writeunlock(i){
    V(rwmutex[i]);
}

P1(i){
    while(true) {
        readlock(i);
        
        readFi(i);
        
        readunlock(i);
    }
}

P2(i){
    while(true){
        writelock(i);
        
        writeFi(i);
        
        writeunlock(i);
    }
}

P3(i){
    while(true){
        readlock(i);
        readFi(i);
        readunlock(i);
        
        writelock(i);
        writeFi(i);
        writeunlock(i);
    }
}

4.7.2 生产者消费者

三组进程P1（K个，K>1）、P2（1个）、P3（1个）、互斥使用一个包含N(N>1)个单元的缓冲区buf1，P2-1、P3-1、P4（各有1个）执行定期统计

P1每次用produce()，生成一个正整数并用put()送入缓冲区
buf1某一空单元中，循环访问缓冲区
P2每次用getodd()从buf1缓冲区取出一个奇数，放到自己私
有缓冲区buf2中（缓冲区长度为M>1），然后由P2-1（1个
）进程读取P2的私有缓冲区，使用countodd()统计奇数个数
P3每次用geteven()从buf1缓冲区中取出一个偶数，，放到
自己私有缓冲区buf3中（缓冲区长度为M>1），然后由P3-1
（1个）进程读取P3的私有缓冲区，使用counteven()统计偶
数个数
P4在P2-1、P3-1产生一个统计值后，就输出一个包含统计时
间的结果
请用信号量机制实现这几个进程的同步与互斥活动，并说明
所定义的信号量含义。

semaphore empty1 = N;//剩余产生位
semaphore full_odd = 0;//剩余奇数读取位
semaphore full_even = 0;//剩余偶数读取位
semaphore mutex1 = 1;//生产消费互斥信号
semaphore empty2 = M;
semaphore full2 = 0;
semaphore mutex2 = 1;
semaphore empty3 = M;
semaphore full3 = 0;
semaphore mutex3 = 1;
//P4信号量
semaphore odd = 0;
semaphore even = 0;

P1() {
    while (true) {
        int a = produce();

        P(empty1);
        P(mutex1);

        put_buf1(a);

        V(mutex1);

        if (is_odd(a))
            V(full_odd);
        else
            V(full_even);
    }
}

P2(){
    while(true){
        //先取一个奇数
        P(full_odd);
        P(mutex1);
        
        int x = getodd();
        
        V(mutex1);
        V(empty1);
        
        //再放入自己的缓冲区
        P(empty2);
        P(mutex2);
        
        put_into_buf2(x);
        
        V(mutex2);
        V(full2); 
    }
}

P3() {
    while (true) {
        P(full_even);
        P(mutex1);

        int x = geteven_buf1();

        V(mutex1);
        V(empty1);

        P(empty3);
        P(mutex3);

        put_buf3(x);

        V(mutex3);
        V(full3);
    }
}

P2-1(){
    while(true){
        P(full2);
        P(mutex2);
        
        int x = get_buf2();
        
        V(mutex2);
        V(empty2);
        
        countodd();
        
        V(odd);
    }
}

P3-1(){
    while(true){
        P(full3);
        P(mutex3);
        
        int x = get_buf3();
        
        V(mutex3);
        V(empty3);
        
        counteven();
        
        V(even);
    }
}

P4(){
    while(true){
        P(odd);
        P(even);
        
        output();
    }
}

4.7.3 独木桥问题

独木桥问题

独木桥只允许一台汽车过河，当车到达桥头时，如果桥上无
车，则可上桥，否则车在桥头等待，直到桥上无车。使用
PV操作解决该问题。
如果独木桥允许多台车同方向过河，当车到达桥头时，如果
桥上只有同方向车且不超过N台，或者桥上无车，则可上桥
通过，否则等待，直到满足上桥条件。使用PV操作解决该
问题。

//1.
semaphore mutex = 1;//桥是否被占用

Car(){
    P(mutex);
    
    cross_bridge();
    
    V(mutex)
}

//2.
semaphore mutex = 1;       // 保护共享变量
semaphore wait[2] = {0, 0}; // 两个方向的等待队列

int count = 0;             // 当前桥上车辆数
int dir = -1;              // 当前桥上方向，-1 表示桥空
int waiting[2] = {0, 0};   // 两个方向等待车辆数

arrive(int x) {
    P(mutex);
    
    if (count == 0) {
        dir = x;
        count++;
        V(mutex);
    } else if (dir == x && count < N){
        count++;
        V(mutex);
    } else {
        waiting[x]++;
        V(mutex);
        
        P(wait[x]);
    }
}

leave(int x){
    P(mutex);
    
    count--;
    
    if (count == 0) {
        if (waiting[1-x] > 0){
            dir = 1 - x;
            
            int num = min(N, waiting[1-x]);
            count = num;
            waiting[1-x] -= num;
            
            for (int i = -; i < num; i++){
                V(wait[1-x]);
            }
        }
        else if (waiting[x] > 0){
            dir = x;
            
            int num = min(N, waiting[x]);
            count - num;
            waiting[x] -= num;
            
            for (int i = 0; i < num; i++){
                V(wait[x]);
            }
        }
        else {
            dir = -1;
        }
    }
    
    V(mutex);
}

Car(int x) {
    Arrive(x);

    cross_bridge();

    Leave(x);
}

4.7.4 红黑客过河问题

红黑客过河问题

有红客和黑客两组人员需要过河。河上有船，但是每次只能乘坐4人，且每次乘客满员时才能开船，到河对岸后空船返回。
但船上乘客不能同时有3个红客、1个黑客或者 1个红客、 3个黑客的组合。（其他组合安全）。请编写程序，用PV操作解决红客、黑客过河的问题

#define RED 0
#define BLACK 1

semaphore mutex = 1;          // 保护 red、black 等等待人数变量
semaphore redq = 0;           // 红客等待队列
semaphore blackq = 0;         // 黑客等待队列

semaphore boat_mutex = 1;     // 保护 boarded
semaphore boat_ready = 0;     // 前3个上船者等待第4个人开船返回

int red = 0;                  // 当前等待的红客数
int black = 0;                // 当前等待的黑客数
int boarded = 0;              // 当前这一船已经上船的人数

Red() {
    P(mutex);

    red++;

    if (red >= 4) {
        red -= 4;

        V(redq);
        V(redq);
        V(redq);
        V(redq);
    }
    else if (red >= 2 && black >= 2) {
        red -= 2;
        black -= 2;

        V(redq);
        V(redq);
        V(blackq);
        V(blackq);
    }

    V(mutex);

    P(redq);

    BoardAndRow();
}

Black() {
    P(mutex);

    black++;

    if (black >= 4) {
        black -= 4;

        V(blackq);
        V(blackq);
        V(blackq);
        V(blackq);
    }
    else if (red >= 2 && black >= 2) {
        red -= 2;
        black -= 2;

        V(redq);
        V(redq);
        V(blackq);
        V(blackq);
    }

    V(mutex);

    P(blackq);

    BoardAndRow();
}

BoardAndRow() {
    board();

    P(boat_mutex);

    boarded++;

    if (boarded == 4) {
        row_boat();          // 第4个人负责开船过河
        return_boat();       // 空船返回

        boarded = 0;

        V(boat_ready);
        V(boat_ready);
        V(boat_ready);

        V(boat_mutex);
    }
    else {
        V(boat_mutex);

        P(boat_ready);       // 前3个人等待第4个人开船返回
    }
}

第五章死锁

5.1 死锁产生的原因和特征

资源分类：
可剥夺资源和不可剥夺资源
竞争可剥夺资源一般不会产生死锁，竞争不可剥夺资源容易产生死锁可剥

1 2	可夺资源：CPU、主存不可剥夺资源：打印机、读卡机、互斥锁

永久性资源和消耗性资源

1 2	永久性资源：打印机、磁盘、文件消耗性资源：消息、信件、信号

死锁产生的四个必要条件

死锁发生时，四个条件一定同时成立，只要破坏其中一个，就能预防死锁

互斥条件
资源一次只能给一个进程使用
请求和保持条件
进程已经占有一些资源，同时又请求新的资源
不剥夺条件
进程已经获得得资源，在它主动释放之前，系统不能强行夺走
循环等待条件
存在一个进程等待环

资源分配图

处理死锁的方法

忽略、预防、避免、检测和解除

忽略：鸵鸟算法
预防死锁：破坏四个必要条件之一

破坏互斥条件：资源共享
破坏请求和保持条件：一次性申请所有资源或者申请新的资源之前先释放已有的资源
破坏不可剥夺条件：如果一个进程申请新的资源失败，就强行剥夺它已经占有的资源
破坏循环等待条件：给所有资源编号，进程只能按编号递增顺序申请资源

死锁避免

如果系统能找到一个进程执行顺序，使所有进程都能顺利完成，则系统处于安全状态，这个顺序叫安全序列。反之为不安全状态：让系统始终不进入不安全状态

银行家算法

资源分配图的化简

第六章主存储器管理

6.1 主存储器的主要功能

主存储器是程序与数据执行和处理的必经载体，但主存存取速度远远跟不上处理器处理速度，因此必须要有一套管理机制

6.1.1 内存

系统区：这部分主要给操作系统自身使用，普通用户程序不能随便访问，包括操作系统内核程序和数据结构
用户去：分区分页分段主要是讨论用户区怎么分配给各个进程，包括应用程序和用户进程的数据

6.1.2 功能

存储空间的分配和回收
抽象与映射
地址映射、地址变换和重定位
隔离和共享，进程之间默认隔离，授权之后可以共享，一旦共享就要考虑互斥和同步
存储扩充：用户希望程序拥有很大的地址空间，但物理内存有限。

所以 OS 要在逻辑上提供：
1
比实际物理内存更大的存储空间
后面的分页、交换、虚拟存储，都是为了解决这个问题。

逻辑地址：程序看到的地址
物理地址：内存中的真实地址

地址空间：逻辑地址的集合
主存空间：物理地址的集合

连续分配：一个进程必须放在一整块连续内存中
离散分配：一个进程可以分散放在多个内存块中

分页：按固定大小切，主要是系统管理需要
分段：按程序逻辑功能切，主要是用户/程序需要

6.2 程序的装入和链接

源程序
  ↓ 编译
目标模块
  ↓ 链接
装入模块 / 可执行文件
  ↓ 装入
内存中的进程

6.2.1 装入

绝对装入方式：在编译的时候就知道程序将来要放在内存的那个位置，生成代码中使用绝对地址
可重定位装入方式（静态重定位）：编译时后生成的是相对地址，装入程序根据内存当前空闲情况，把程序放到合适的位置
动态运行时装入（动态重定位）：装入内存时不修改程序里面的逻辑地址，而是在程序运行过程中，每次访问内存时再进行地址变换，需要 重定位寄存器，起始地址修改时（程序被移动到另一块内存）不用修改逻辑地址，直接修改重定位寄存器里面的值（目标地址 = 重定位寄存器 + 逻辑地址）

PCB不只是记录进程状态，也保存进程运行所需的地址映射信息

装入方式	地址确定时间	是否需要硬件支持	特点
绝对装入	编译时	不需要	简单，但位置固定
可重定位装入	装入时	不需要	装入时统一改地址
动态运行时装入	运行时	需要	最灵活，可支持移动

6.2.2 链接

静态链接：静态链接是在程序运行之前，把所有目标模块和库函数都合并成一个完整可执行文件
装入时动态链接：一边装入，一边链接需要的外部模块，如果装入目标模块时遇到外部模块调用，装入程序会寻找相应外部目标模块，将其装入内存，并修改目标模块中的相对地址
运行时动态链接：运行时动态链接把某些目标模块的链接推迟到执行时才进行；如果被调用模块还没装入，由 OS 找到它、装入并链接；如果没被调用，就不会加载

链接方式	链接时间	特点
静态链接	程序运行前	全部提前打包
装入时动态链接	装入内存时	边装入边链接
运行时动态链接	程序运行过程中	用到谁再加载谁

6.3 内存保护

防止进程有意或无意破坏操作系统或其他进程

os需要保证：

进程只能访问自己被允许访问的内存
用户程序不能随便访问内核区
读权限、写权限、执行权限要区分

6.3.1 界限寄存器法

给每个进程规定一个合法地址范围，访问前先检查是否越界

上下界寄存器：使用上下界寄存器保存进程内存开始和结束地址
基址限长寄存器：基址保存起始地址，限长存长度

6.3.2 存储保护键

存储保护键可以类比成：

1
2
3

内存块有锁
进程有钥匙
钥匙和锁匹配，才能访问

为每个存储块分配一个保护键，相当于锁；给进入系统的每个作业赋予保护键，相当于钥匙；访问时检查是否匹配，不匹配就产生保护性中断。

这个方法适合按内存块进行保护。

6.3.3 环保护机制

处理器状态可分为多个环，编号越小，特权级越高

程序可以访问相同环或较低特权环的数据
程序可以调用相同环或较高特权环的服务

6.3.4 访问权限保护

除了地址范围和特权级，还可以给内存区域设置访问权限。

常见权限有：

禁止访问
只执行
只读
读/写

比如：

代码段：通常可执行、只读
数据段：可读写
只读常量区：只读
内核区：用户态不可访问

这很重要。比如代码段如果可写，攻击者可能修改程序指令；栈如果可执行，可能引发安全问题。

方法	保护思路	重点
界限寄存器	检查地址是否越界	防止访问范围外内存
存储保护键	锁钥匙匹配	按内存块控制访问
环保护机制	按特权级访问	区分内核和用户
访问权限	控制读/写/执行	防止非法操作类型

6.4 内存分配

6.4.1 单一连续分配

1
2
3

单一连续分配：内存分为系统区和用户区
用户区一次只装入一道用户作业
实现简单，但内存利用率低，不适合多道程序

6.4.2 固定分区分配

系统启动或初始化时，把内存用户区划分成若干个固定大小的分区，每个分区最多装入一个作业

等长分区
不等放分区

系统一般会维护一张分区说明表，记录每个分区的信息，当一个作业进入时，系统查表，找一个能容纳它的空闲分区。

6.4.3 动态分区分配

作业装入时，按大小为其划分一块内存区，缺点：外部碎片

1 2	内部碎片：分配进去以后，分区里面浪费外部碎片：分区外面零散空闲，拼不成大块

动态分区算法

First Fit：从空闲分区表开头开始找找到第一个能满足大小要求的空闲分区就分配
Next Fit：从上次查找结束的位置继续往后找
Best Fit：选择能满足要求的最小空闲分区
Worst Fit：选择最大的空闲分区进行分配

动态分区的回收：回收时要检查相邻空闲区，能合并就合并

紧凑技术：如果外部碎片太多，可以把已经分配的进程移动到一起，使空闲区合并成一整块，需要动态重定位支持

6.4.4 伙伴系统

分配过程

假设系统有一个 64KB 空闲块。

现在有进程申请：

10KB

系统要分配能容纳 10KB 的最小 2 的幂：

16KB

于是从 64KB 开始分裂：

64KB
 ↓
32KB + 32KB
 ↓
16KB + 16KB + 32KB

分配其中一个 16KB 给进程。

剩余空闲块是：

1
2

16KB
32KB

注意：虽然进程只要 10KB，但系统给了 16KB，所以会有：

1	16KB - 10KB = 6KB

这 6KB 是内部碎片。

回收过程

假设刚才分配出去的 16KB 后来释放了。

系统会检查它的伙伴块是否空闲。

如果它的伙伴 16KB 也空闲，则合并：

1
2
3

16KB + 16KB
 ↓
32KB

再继续检查这个 32KB 的伙伴是否空闲。

如果另一个 32KB 也空闲，则继续合并：

1
2
3

32KB + 32KB
 ↓
64KB

伙伴系统回收时的优势： 可以快速把相邻的伙伴空闲块合并成大块，减少外部碎片。

6.4.5 覆盖和交换

覆盖的核心思想是：

1
2
3

一个程序不需要所有模块同时在内存中
只把当前需要的模块装入内存
用完后可以被其他模块覆盖

交换的核心思想是：

把暂时不能运行的进程从内存换出到外存
需要运行时再换入内存

进程 P1 阻塞等待 I/O
↓
OS 把 P1 换出到磁盘
↓
腾出内存给 P2
↓
P1 需要运行时再换入

就绪 ↔ 挂起就绪
阻塞 ↔ 挂起阻塞

6.4.6 分页存储管理

分页存储管理就是为了解决进程必须占用一整块连续的内存从而产生的外部的碎片

页和页框

页：把进程的逻辑地址空间分为大小相等的块

页框：把物理内存也切成同样大小相等的块

将物理地址连续转化成逻辑地址连续减少外部碎片

页表：查询逻辑页号对应的物理块号

地址结构：逻辑地址 = 页号 + 页内偏移
程序的访问逻辑地址，通过逻辑地址求得页号和页内偏移->查询页表组成物理地址

分页基本消除外部碎片，但是可能产生内部碎片

分页的关键改进是：

进程被切成页
内存被切成页框
页可以离散装入页框
页表负责地址映射

快表TLB与多级页表

上一种方法的问题是：每次访问内存都要先查页表，在访问真正的数据会变慢

TLB再cpu附近速度很快，其中保存最近用过的页表项

先查 TLB
  ↓
如果命中：直接得到物理块号
  ↓
形成物理地址，访问内存

如果未命中：
  ↓
访问内存中的页表
  ↓
找到物理块号
  ↓
把该页表项放入 TLB
  ↓
再访问真正数据

TLB的作用是减少查页表带来的额外内存访问

所以TLB的命中率是评价分页系统性能的重要标准

由于页表过大，需要引进多级页表表，即在页表在进行分页，例如：

1	一级页号 p1 + 二级页号 p2 + 页内偏移 d

6.4.7 分段存储管理

分段：按照程序的逻辑结构，把程序分为若干个段

分段地址结构 ：段号 s + 段内偏移 w （逻辑地址 = 段号 + 段内地址）

段表：记录段号、段长和段基址

分段地址变化过程：

逻辑地址：段号 S + 段内偏移 W
        ↓
查段表，找到该段的段基址和段长
        ↓
判断 W 是否小于段长
        ↓
如果 W >= 段长，越界中断
        ↓
如果合法，物理地址 = 段基址 + W

对比	分页	分段
划分依据	固定大小	程序逻辑单位
大小	每页大小相同	每段大小可不同
地址结构	页号 + 页内偏移	段号 + 段内偏移
表结构	页表记录块号	段表记录基址和段长
碎片	可能有内部碎片	可能有外部碎片
用户是否可见	通常用户不可见	通常用户可见
适合	内存管理	共享、保护、逻辑组织

分段的优点：

第一，符合程序逻辑结构。
程序本来就有代码段、数据段、栈段等，按段管理更自然。

第二，方便共享。
比如多个进程可以共享同一个代码段或库函数段。

第三，方便保护。
不同段可以设置不同权限：

1
2
3

代码段：只读、可执行
数据段：可读写
栈段：可读写

缺点：容易产生外部碎片

6.4.8 段页式存储管理

先按逻辑结构分段，再把每个段分页

段页式逻辑地址组成：段号S + 段内页号 P + 页内偏移 W

需要：段表和页表

缺点也很明显：

地址变换更复杂
需要先查段表，再查页表
表占用空间更多
访问速度可能下降

所以实际系统中通常要配合快表 TLB 来提高地址转换速度。

第七章虚拟内存管理

7.1 虚拟内存

程序不必全部装入内存，缺哪一页再调哪一页

程序运行有明显局部性，某一小段时间内真正用到的部分不多，可以在程序运行前直把一部分放入内存；运行过程中访问的信息不在内存中的时候，再由os将所需要的部分调入内存；同时还可以把不用的部分换出到外存

也就是节省了内存空间，但增加了调页和磁盘 I/O 的时间开销

实现方法：请求分页存储管理和请求分段存储管理

与前面一张的区别是：按需调入，请求到哪一页再调入那一页，普通分页是程序页面一次性调入

7.2 请求分页存储管理

请求分页是在分页存储管理的基础上增加请求调页和页面替换的功能，运行中的页面不存在内存中时硬件产生缺页中断，请求OS将缺页调入内存，如果内存没有空闲空间，就根据替换算法淘汰某个页面

请求分页的支持机构

硬件支持：

MMU：内存管理单元，接受虚拟地址作为输入，输出物理地址，并送到总线上对内存单元寻址

CPU 发出逻辑地址
↓
MMU 查页表 / 快表
↓
如果页在内存，得到物理地址
↓
如果页不在内存，触发缺页中断

页表、缺页中断机构、地址变换机构

软件支持：

请求调页程序
页面替换算法

请求分页的页表项

页号、物理块号
存在位：该页是否存在主存中
访问字段：记录该页最近是否访问、访问次数、多久没访问等，主要用于替换算法
修改位（脏位）：该页被调入内存之后是否被修改，用于判断淘汰时直接丢弃还是写回内存
外存地址：该页在外存中的地址

缺页中断：

MMU 检查页表
发现存在位 = 0
↓
产生缺页中断
↓
OS 介入，把缺页从外存调入内存
↓
修改页表
↓
重新执行刚才那条指令

1. CPU 发起地址访问，MMU 查页表
2. 如果页面不在内存，产生缺页中断
3. OS 在外存中找到该页
4. 找空闲页框
5. 如果没有空闲页框，选择一个页面淘汰
6. 如果淘汰页被修改过，先写回外存
7. 把缺页调入内存
8. 修改页表和相关表项
9. 重新执行产生缺页的指令

缺页中断和普通中断的区别：

产生时间不同：普通中断发生在指令执行之后，缺页中断发生在指令执行过程当中
返回位置：前者返回下一条指令的位置，后者重新执行该条指令
一条指令可能产生多个缺页中断比如：
1
copy A to B
可能访问源地址 A 时缺页，处理完后重新执行；又访问目标地址 B 时缺页，再处理一次

总体流程：

逻辑地址
↓
拆成页号 + 页内偏移
↓
查 TLB
↓
TLB 命中：形成物理地址，访问内存
↓
TLB 未命中：查页表
↓
页在内存：更新 TLB，形成物理地址
↓
页不在内存：缺页中断
↓
OS 调页，修改页表
↓
重新执行指令

7.3 Copy-on-Write

父进程创建子进程时，先不复制整份内存，而是让父子进程共享同一批物理页面；只有当其中一方要修改页面时，才真正复制该页面。

父子进程的页表都指向同一批物理页面

P1 页表 → Page A
P2 页表 → Page A

P1 页表 → Page B
P2 页表 → Page B

P1 页表 → Page C
P2 页表 → Page C

假设 P1 要修改 Page C。

因为 Page C 被标记为只读，所以写操作会触发异常。

操作系统发现：

1 2	这不是普通非法写入而是 COW 页面写入

于是 OS 会：

1. 分配一个新的物理页
2. 把原 Page C 的内容复制到新页
3. 让 P1 的页表指向新页
4. 恢复 P1 对新页的写权限
5. P2 仍然指向原来的 Page C

PPT 第 40、41 页的图正是这个过程：修改 Page C 前，两个进程都映射到同一个 Page C；修改 Page C 后，Process 1 获得 Copy of Page C，而 Process 2 仍然使用原 Page C

vfork()：子进程直接用父进程地址空间，父进程挂起，子进程应尽快 exec。

7.4 页面替换算法

FIFO：先进先出页面替换算法
OPT：淘汰将来最长时间不会被访问的页面
LRU：淘汰最近最长时间没有被访问的页面

Clock：简单时钟算法

1
2
3

看指针指向的页面
如果访问位 = 0：淘汰它
如果访问位 = 1：把访问位置 0，指针后移，继续找

增强型 Clock 算法

R=0, M=0：最近没访问，没修改，最好淘汰
R=0, M=1：最近没访问，但修改过，淘汰要写回
R=1, M=0：最近访问过，没修改
R=1, M=1：最近访问过，且修改过，最不优先淘汰

7.5 页面管理的策略问题

页面什么时候装入？什么时候写回？每个进程分多少页框？替换范围是本进程还是全系统？

页面装入与清除策略、页面分配与替换策略。

页面装入：什么时候把页面调入主存？

请求调页：用一页调一页
预调页：根据局部性原理，提前把可能调入的页面调入内存

清除策略：什么时候把写过的页面写回外存

请求清除
预约清除：提前把修改过的页面成批写回外存

页面分配：每个进程分配多少页框

固定分配
可变分配：
如果某进程缺页率很高，说明需要更多页面，可以增加页框，反之可以减少

页面替换：发生缺页时，从哪里选牺牲页

局部替换：从自己的页框中选择一页替换
全局替换：可以从整个系统所有进程的页框中选择牺牲页

抖动问题：如果运行进程的大部分时间都用于页面换入/换出，而几乎不能完成有效工作，则称该进程处于抖动状态，高缺页率，分配的页框数过少

7.7 局部页面替换算法

抖动的根本原因之一：
进程当前真正需要的页面没有全部留在内存中

所以能不能根据进程最近的访问情况，判断它当前真正需要哪些页面

局部最佳页面替换算法、工作集模型和工作集替换算法、模拟工作集替换算法、缺页频率替换算法。

局部最佳页面替换算法：类似OPT，如果某页在未来 Δ 时间内不会再被访问，就可以把它移出驻留集

工作集模型 working set：基于局部性原理，通过考察最近时间内内的主存需求，估计不久将来的内存页框需求，工作集定义 W(t,Δ ) t时刻之前的Δ 时间窗口内，进程访问过的页面集合

页面访问序列：

1	1, 2, 3, 2, 4, 2, 5

假设当前时刻访问到最后一个 5，窗口 Δ = 4，看最近 4 次访问：

1	2, 4, 2, 5

那么工作集是：

{2, 4, 5}

注意，集合不重复计数。

所以工作集大小是：

至少分配页框大小3

模拟工作集替换算法

例如时间戳算法：给每个页面记录最近一次被访问的时间，如果某页很久没被访问，超过阈值，就认为他不在工作集中

缺页频率替换算法 PFF：PFF 根据连续缺页之间的时间间隔测量缺页频率，并利用测量时间调整进程工作集尺寸；另一种实现是设置上下阈值，缺页率达到上限时增加物理块，达到下限时减少物理块

7.8 页面大小选择

页面小：页内碎片小，但页表大、TLB覆盖范围小

页面大：页表小、I/O效率可能高，但页内碎片大

设：

1
2
3

s = 每个进程平均长度
p = 页面大小
e = 每个页表项大小

则：

1 2	每个进程页表空间 = se / p 每个进程平均页内碎片 = p / 2

所以每个进程平均浪费空间：

1	se / p + p / 2

对这个式子求最小值，可得到：

1	p = √(2es)

7.9 内存映射文件

内存映射文件就是用虚拟内存机制来访问文件。把文件内容映射成虚拟内存地址，再通过分页方式进行读取修改和写回，也就是虚拟页对应文件某一块的内容，写回方式也类似（脏位）

访问映射区
↓
对应文件页不在内存
↓
缺页中断
↓
OS 从文件中把对应页调入内存
↓
继续访问

read()：
文件 → 内核缓冲区 → 用户缓冲区

mmap()：
文件 → 映射到虚拟地址空间
访问时通过缺页机制把文件页调入内存

访问方式简单，减少数据复制，方便进程共享