操作系统

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

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

操作系统分类

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

操作系统的基本特征

并发性：两个或多个时间在同一时间间隔内发生
活动的协调、资源共享
共享性：对多个并发执行进程
虚拟性：例如：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

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

中断是由CPU 外部事件引起的，比如时钟到期、键盘输入、磁盘完成，用来通知处理机及时处理外设或异步事件；异常是由CPU 执行当前指令时在内部发现的异常情况引起的，比如除零、缺页、非法指令、越界等，属于同步事件；系统调用是用户程序主动发出的特殊请求，本质上是用户态通过陷入机制进入内核态，请求操作系统提供服务，如文件读写、进程创建、内存申请等。

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 读者写者问题

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

约束是：

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

int readcount = 0;
semaphore rmutex = 1;
semaphore wmutex = 1;

reader() {
    while (true) {
        P(rmutex);
        if(readcount == 0) {
            P(wmutex);
        }
        readcount++;
        V(rmutex);
        
        read_data();
        
        P(rmutex);
        readcount--;
        if(readcount == 0) {
            V(wmutex);
        }
        V(rmutex);
    }
}

write(){
    while (true) {
        P(wmutex);
        
        write_data();
        
        V(wmutex);
    }
}

读者优先

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

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()：
文件 → 映射到虚拟地址空间
访问时通过缺页机制把文件页调入内存

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

第八章文件管理

8.1 文件的概念

文件 = 存放在外存上 + 有名字 + 一组相关信息的集合

文件是记录在外部存储上、具有名字的一组相关记录的集合；记录有相关数据项组成，数据项是可命名的最小逻辑单位

从用户角度：文件就是能操作的最小外存单位

从操作系统：文件时它管理磁盘数据的基本单位


文件 file.txt
 └── 记录 BOB 2024 99
      └── 数据项 name grade score

文件分类

.c 文件：源文件
.o 文件：目标文件
.exe 文件：可执行文件
.txt 文件：普通用户文件

文件属性

文件属性包括名称、标识符、类型、位置、大小、保护信息、时间日期和用户标识等，这些信息通常保存在目录结构中，并长期存储在外存上

文件操作

Create：创建文件
Read：读文件
Write：写文件
Seek：移动文件读写位置
Delete：删除文件
Truncate：清空文件内容但保留属性
Open：打开文件
Close：关闭文件

Open ：把磁盘上的文件目录信息读入内存，建立打开文件表项

Close ：关闭文件，减少打开计数，必要时把修改后的文件信息写回磁盘

8.2文件访问方法

文件已经存在磁盘上了，用户/程序要怎样读取它？

顺序访问
rptr = rptr + L
直接访问：记录长度固定，有额外索引支持

要访问第i条数据rptr = addr + i × L
索引访问：先查目录/索引，再根据索引找到真正的数据位置

访问方法	核心思想	适合场景
顺序访问	从前到后依次访问	日志文件、文本文件、批量处理
直接访问	根据记录号直接定位	定长记录、数据库文件
索引访问	先查索引再访问数据	按关键字查询的文件

8.3 磁盘和文件目录结构

目录：文件名到文件信息的映射表，所以目录通常会保存文件名以及指向文件控制块FCB或inode的信息（通过文件名找到文件信息，大小，权限，磁盘位置，类型等）

目录上的基本操作：搜索文件、创建文件、删除文件、查看目录、重命名文件、遍历文件系统

目录结构：

单级目录：所有文件公用一个目录
二级目录：分主文件目录和用户文件目录两层
多级目录（树形）：非叶子节点为目录名，叶子节点为文件（同一个文件或目录不能自然地被多个目录共享）
无环图目录：支持文件共享，节省磁盘空间（管理比较复杂：悬挂指针，删除和引用计数复杂）
通用图目录：可以出现环（管理更加复杂）

8.4 文件系统的安装、保护和共享

文件系统的安装 mount

一个文件系统在被访问之前，需要先被安装/挂载 mount，就是把磁盘分区或外部存储设备，接到已有目录树的某个子目录上，例如：

mount /dev/sdb1 /mnt/usb

就是把前者设备上的文件系统挂载到后者目录下

文件共享

在 Linux 中，一个文件通常有：

1
2
3

所有者 owner
所属组 group
其他用户 others

比如：

1	-rw-r--r-- user group test.txt

意思大致是：

1
2
3

文件所有者：可读可写
同组用户：只读
其他用户：只读

远程文件系统

远程文件系统可以通过 Client-Server 模型让客户端挂在远程文件系统，NFS是UNIX标准的CS文件共享协议，CIFS是Windows的标准协议

本地文件系统：文件在自己电脑磁盘上
远程文件系统：文件在服务器上，但你像访问本地目录一样访问它

共享一致性

UFS 中写操作对其他打开同一文件的用户立即可见；AFS 是会话语义，即关闭文件后，后来打开的会话才能看到变化

文件保护：给用户权限，文件权限

常见访问模式有：

1
2
3

read：读
write：写
execute：执行

Linux 常用三类用户权限：

1
2
3

owner：文件所有者
group：同组用户
others/public：其他用户

每一类都有：

1
2
3

r：read，读
w：write，写
x：execute，执行

8.5 文件系统分层结构

从“用户怎么用文件”转到“操作系统内部怎么实现文件”，文件系统有两个任务：一是定义用户接口，二是创建算法和数据结构，实现逻辑单元到物理单元的映射

用户视图：

文件名
目录
文件内容
read/write/open/close

操作系统视图：

数据块集合
目录项
FCB / inode
磁盘块号
缓冲区
设备驱动

用户通过系统调用访问文件，不关心磁盘存储方式；而操作系统视图中，文件是数据块集合

文件控制块FCB：FCB是包含文件属性信息的数据结构，文件内容在数据块里文件属性和位置在FCB中

文件系统的层次结构

用户程序
↓
逻辑文件系统
↓
文件组织模块
↓
基本文件系统
↓
I/O 控制层
↓
硬件设备

第一层逻辑文件系统

逻辑文件系统负责根据路径找到对应的inode 和 FCB，负责处理：文件名、目录结构、文件保护、FCB / inode

1
2
3

用户要访问的文件是谁？
有没有权限？
文件的元数据在哪里？

第二层文件组织模块

逻辑块号->物理块号

1	这个文件的第 i 块，实际放在磁盘哪里？

第三层基本文件系统

负责向设备驱动发送通用读写命令：

1 2	读第 x 个物理块写第 y 个物理块

它不太关心文件名，只关心块读写。

第四层 IO控制层

负责启动磁盘IO，包括：设备驱动程序、中断处理程序、磁盘控制器交互

I/O 控制层通过设备驱动和中断处理实现对 I/O 设备的管理

read一个文件的基本流程

read(fd, buf, 100)

逻辑文件系统：根据fd找到已打开文件表项和 inode/FCB
文件组织模块：确定要读的文件是哪个逻辑块
文件组织模块：把逻辑块号转换成物理磁盘号
基本文件系统：发出读物理块请求
I/O控制层：设备驱动控制磁盘读取
数据库进入缓冲区
拷贝到用户缓冲区buf

8.6 文件系统实现

8.6.1 文件系统实现分两类结构

盘上结构说明如何启动OS、总块数、空闲数、目录结构和具体文件

内存结构用于管理文件系统并通过缓存提高性能

盘上结构

存放磁盘里的管理信息

①引导控制块 Boot Control Block：保存从该卷启动操作系统所需的信息，如果这个分区可以启动系统，那么它里面会有引导信息

② 卷控制块 Volume Control Block：记录整个卷/分区的总体信息

③ 目录结构 Directory Structure：组织文件名和文件控制信息之间的关系

④ 文件控制块 FCB：每个文件对应一个 FCB

内存结构

内存结构是系统运行时为了加快文件访问而维护的，主要有：

安装表 Mount Table
目录结构缓存
系统打开文件表
进程打开文件表

① 安装表 Mount Table:记录已经挂载的文件系统

② 目录结构缓存：系统会缓存最近访问过的目录信息，加快查找速度

③ 系统打开文件表：整个系统共享的一张表，记录当前系统那些文件被打开、对应的FCB/inode，打开计数，文件状态

④ 进程打开文件表：每个进程有自己有一张打开文件表，记录：该进程打开了哪些文件、当前读写位置、访问模式、指向系统打开文件表的指针

open() 的内部过程

open("a.txt")

系统调用进入逻辑文件系统
查系统打开文件表，看文件是否已被其他进程打开
如果已打开：在本进程打开文件表中建立条目，指向系统打开文件表
如果未打开：根据文件名搜索目录
找到文件后：把FCB/inode复制到系统打开文件表
在进程打开文件表中建立条目
返回文件描述符 fd

避免每次 read/write 都重新查目录、读FCB

close() 的内部过程

close(fd)

删除该进程打开文件表中对应的条目
系统打开文件表中的打开计数器减1
如果打开计数器变成0：
- 把删除过的元数据写回磁盘
- 删除系统打开文件表中的条目

一个进程close不一定真正关闭整个文件，只有最后一个进程close，系统才真正清理公共打开文件信息

8.7 文件存储空间的管理

8.7.1 文件分配磁盘块

如何为文件分配磁盘块，以及如何记录空闲空间

连续分配：记录起始位置和块长度，空间连续但会产生外部碎片

链接分配：文件的磁盘块可以分散存放，每一块中保存指向下一块的指针

不适合随机访问
必须沿链表一个块一个块找
指针占用空间
指针损坏会影响后续块

FAT文件分配表

普通链接分配的指针放在数据块里，每找下一块可能都要读磁盘，FAT把所有块的“下一块指针”集中存放在一张表里

目录项：文件首块 = 5

FAT[5] = 9
FAT[9] = 20
FAT[20] = 31
FAT[31] = EOF

比普通链式结构更方便管理
如果 FAT 缓存在内存中，查找速度更快

FAT 表本身占空间
大磁盘时 FAT 很大
如果不缓存，会频繁访问 FAT

索引分配
为每个文件建立一个索引块，索引块中保存该文件所有数据块的物理块号

逻辑块 0 → 物理块 8
逻辑块 1 → 物理块 21
逻辑块 2 → 物理块 5
逻辑块 3 → 物理块 30

支持随机访问
不产生外部碎片
文件块可以离散存放

索引块占额外空间
访问数据前可能要先读索引块
小文件也可能浪费一个索引块

多级索引：文件很大，一个索引块放不下所有块号

二级索引
一级索引块
 ├── 二级索引块 1 → 数据块
 ├── 二级索引块 2 → 数据块
 └── 二级索引块 3 → 数据块
 
 如果盘块大小 1KB，每个盘块号 4B，则一个索引块可放 256 个盘块号，两级索引最多表示：
 256 × 256 = 64K 个盘块
 最大文件长度：
 64K × 1KB = 64MB

混合索引

直接索引
一次间接索引
二次间接索引
三次间接索引

UNIX 中有 15 个地址项，包括 12 个直接地址项、1 个一次间接地址项、1 个二次间接地址项和 1 个三次间接地址项

假设：

1 2	块大小 = 4KB 块号大小 = 4B

那么一个索引块能放：

1	4KB / 4B = 1024 = 1K 个块号

所以：

12 个直接地址项：12 × 4KB = 48KB
一次间接：1K × 4KB = 4MB
二次间接：1K × 1K × 4KB = 4GB
三次间接：1K × 1K × 1K × 4KB = 4TB

这就是为什么混合索引对小文件和大文件都比较友好：

1 2	小文件：直接索引，访问快大文件：间接索引，容量大

8.7.2 空闲存储空间管理

操作系统怎么知道哪些磁盘块是空闲的？

位图法

磁盘块号：0 1 2 3 4 5 6 7
位图：    1 0 0 1 1 0 1 0

查找连续空闲块比较方便
结构简单
适合连续分配

链接法
把所有空闲块串成链表
- 不需要额外的大位图空间
- 空闲块可以分散存在
- 查找效率低
分组法
分组法是链接法的改进，在一个空闲块中存放一组空闲块号
- 遍历次数少
- 适合一次分配多个空闲块
UNIX 使用的是一种成组链接法，把若干空闲盘块划分为一组，每组中的盘块号记录在前一组的第一个空闲块中
计数法
计数法适合空闲块连续的情况，记录：起始空闲块号 + 连续空闲块数量
- 表项少
空间图法 Space Maps
空间图法把空间申请和释放操作按日志形式记录下来之后再在内存中重放、合并、整理

方法	核心思想	优点	缺点
位图法	每个块用 1 位表示状态	简单，适合找连续空闲块	大磁盘下位图占空间
链接法	空闲块串成链表	不浪费大表空间	不易找连续块
分组法	一块记录一组空闲块号	分配多个块更快	管理稍复杂
计数法	起始块号 + 连续块数	表项少，适合连续空间	空间零散时效果差
空间图法	记录空间变化日志	适合大规模文件系统	实现复杂

8.8 文件系统实现中的其他问题

文件系统怎样提高效率和性能？
文件共享在系统内部怎样实现？
文件系统怎样备份、恢复和保证一致性？

文件系统的效率和性能

① 数据和元数据尽量靠近

文件系统访问文件时，还需要读取inode、目录项、数据块和空闲块管理信息，如果inode和数据块距离很远，磁头移动多，性能就差

② 缓冲区缓存

把最近访问过的磁盘块放到内存中
下次再访问时，直接从内存读，不用再读磁盘

③ 同步写和异步写

同步写：write() 必须等数据真正写入磁盘后才返回

异步写：write() 先把数据写入缓存就返回，之后由系统找到合适的时机写回磁盘

但是如果突然断电，缓存中的数据可能丢失

④ 预读

读取当前块时，顺便把后面的块也读入缓存

文件共享的实现

用户合作
减少磁盘空间开销
减少文件不一致性

硬链接：多个文件名指向同一个inode，文件名不同但是inode相同数据块相同，基于inode的共享就是不同目录共享已存在的文件的inode，让inode的链接计数+1
符号链接软链接：软链接是一种只有问文件名、不直接指向inode的文件，它包含被链接文件的路径名而不是inode号

项目	硬链接	软链接
本质	多个文件名指向同一 inode	一个特殊文件，保存目标路径
是否有独立 inode	没有独立目标文件 inode；共享原 inode	有自己的 inode
是否增加原文件引用计数	增加	不增加
删除原文件影响	不影响其他硬链接	软链接失效
能否跨文件系统	通常不能	可以
类比	同一个人有多个名字	快捷方式

文件备份和恢复

全量转储：把文件系统中的所有文件都备份一次
增量转储：只备份上次转储后修改过或新增加的文件

文件日志系统

日志文件系统解决的是：

1	如果系统更新文件系统元数据时突然崩溃，怎么办？

它的做法类似数据库事务：

1 2	先把操作记录到日志再真正修改文件系统结构

如果系统崩溃：

1 2	已经提交的事务：重新执行没有提交完整的事务：撤销

第九章大容量存储系统

9.1 大容量存储结构概述

磁带
磁盘HDD：容量大、支持直接访问、但存在机械移动开销
磁盘访问时间包括寻道时间、旋转延迟和传输时间；寻道时间是磁臂移动到目标磁道的时间，旋转延迟是目标扇区转到磁头下方的时间

SSD 固态硬盘：

没有磁头
没有盘片旋转
没有寻道时间
没有旋转延迟
随机访问快

磁盘访问时间计算

平均 I/O 时间
= 平均寻道时间 + 平均旋转延迟 + 传输时间 + 控制器开销

平均访问时间 = 平均寻道时间 + 平均旋转延迟

平均延迟是转半圈的时间

9.2 磁盘特性

磁盘驱动器被视为逻辑块的一维数组，逻辑块是最小传输单元

机械磁盘常见结构：

盘片
盘面
磁道
扇区
柱面
磁头
磁臂

简单理解：

1
2
3

磁道：盘面上一圈一圈的圆形轨道
扇区：磁道被切分成的小区域
柱面：多个盘面上半径相同的磁道集合

数据最终存放在：

1	某个盘面、某个磁道、某个扇区

但是操作系统通常先看到的是逻辑块号。

就有了逻辑块到物理扇区的映射

逻辑块一维数组会顺序映射到磁盘扇区，扇区 0 通常是最外面柱面的第一个磁道的第一个扇区。映射顺序一般是：先磁道内扇区顺序，再柱面内磁道顺序，最后从外到内的柱面顺序

逻辑块号
↓
磁盘控制器映射
↓
盘面号 + 磁道号 + 扇区号

LBA:逻辑块地址：把复杂的磁盘物理位置编号成连续的逻辑块号

主机连接存储、NAS、SAN

主机连接存储

就是磁盘直接接到本机：

SATA 硬盘
USB 硬盘
SCSI 磁盘
NVMe SSD

特点：

1 2	本机直接访问速度通常较快

ANS

NAS 是网络连接存储。

1	NAS = Network Attached Storage

它通过网络提供文件访问，比如：

1 2	NFS CIFS / SMB

你可以理解为：

1	一台专门提供文件共享的存储服务器

SAN

SAN 是存储区域网络。

1	SAN = Storage Area Network

它更偏企业级，用高速专用网络把服务器和存储阵列连接起来。

简单区别：

1 2	NAS：通过网络共享“文件” SAN：通过专用存储网络共享“块设备”

9.3 磁盘调度

磁盘调度的目标是提高磁盘访问速度和磁盘带宽，而最主要的优化目标就是 最小化寻道时间

算法	核心思想	优点	缺点
FCFS 先来先服务	按请求到达顺序依次访问	简单、公平、不会饥饿	不考虑磁头位置，移动距离可能很大
SSTF 最短寻道时间优先	每次选择离当前磁头最近的请求	平均寻道距离较短，效率比 FCFS 高	远处请求可能长期得不到服务，可能饥饿
SCAN 扫描算法	磁头像电梯一样沿一个方向移动，服务沿途请求，到尽头后反向	避免饥饿，性能较稳定	对两端磁道不太公平
C-SCAN 循环扫描	磁头只沿一个方向服务，到一端后快速回到另一端继续同方向扫描	等待时间更均匀，公平性比 SCAN 好	回绕过程会增加移动距离
LOOK 算法	SCAN 的改进，只移动到当前方向最远请求处就返回，不走到磁盘边界	减少无效移动，比 SCAN 更高效	仍需要判断当前方向
C-LOOK 算法	C-SCAN 的改进，只到当前方向最远请求，再跳到另一端最远请求继续	比 C-SCAN 少走无效路，等待较均匀	实现比 FCFS、SSTF 复杂

FCFS：按顺序
SSTF：找最近
SCAN：电梯来回走
C-SCAN：单向循环走
LOOK：电梯只走到最远请求
C-LOOK：单向循环，只到最远请求

9.4 磁盘存储优化分布

机械磁盘读数据时，不只是找到磁道就行，还要等目标扇区转到磁头下面。

如果记录简单按顺序放：

1	A B C D E F G H I J

程序读完 A 后还要处理 A。处理期间，磁盘已经转过了 B 的位置。

等程序想读 B 时，B 可能刚刚错过，只能等磁盘再转一圈。

这就浪费了大量旋转时间。

根据磁盘旋转和 CPU 处理时间，合理安排记录的物理位置，减少旋转等待，提高连续处理效率。

9.5 磁盘管理

磁盘在真正存放文件之前，需要经过哪些管理步骤？

低级格式化
分区
逻辑格式化
引导块
坏块管理

低级格式化

低级格式化是把磁盘物理介质划分成一个个扇区。

每个扇区通常包含：

1
2
3

头信息
数据区
纠错码 ECC

低级格式化的作用是将磁盘分成多个扇区，以满足磁盘控制器的读写要求。

简单理解：

1	低级格式化 = 让磁盘具备最基本的物理读写结构

分区

分区就是把一个磁盘划分成多个逻辑区域。

例如一块硬盘可以分成：

1
2
3

C盘
D盘
E盘

在操作系统中，一个分区可以被看成一个独立的逻辑磁盘。

逻辑格式化

逻辑格式化就是创建文件系统。

比如把某个分区格式化为：

Ext4
NTFS
FAT32
XFS

逻辑格式化会在磁盘上建立文件系统需要的数据结构，例如：

超级块
空闲空间管理结构
目录结构
inode 表

低级格式化：划分扇区
分区：划分逻辑磁盘
逻辑格式化：创建文件系统

Raw Disk

Raw disk 是没有普通文件系统管理的磁盘区域。

它可以理解为：

一个大的逻辑块数组

有些数据库系统可能会直接使用 Raw Disk，因为它们希望自己管理数据布局和缓存，而不是完全交给文件系统。

引导块

ROM 中的启动程序负责找到磁盘引导块，磁盘引导块继续加载操作系统

坏块管理

磁盘可能出现坏扇区或坏块。

坏块就是：

1	不能可靠读写的磁盘块

常见处理方式：

1
2
3

格式化时检查坏块
建立坏块链表
使用备用块替代坏块

9.6 空间交换管理

内存不够时，被换出的页面或进程放到磁盘哪里？

这个磁盘区域就叫：

1	交换空间 swap space

交换空间可以理解为：

1	磁盘上专门配合虚拟内存使用的一块区域

当内存紧张时，操作系统可以把暂时不用的页面换出到交换空间：

1	内存页面 → 交换空间

等以后又需要访问时，再换回来：

交换空间 → 内存

所以它的作用是：

1	用磁盘空间临时扩充内存

但要注意：

1 2	交换空间不是内存它在磁盘上，速度远慢于内存

交换空间的两种实现方式

交换文件

在普通文件系统中创建一个大文件作为 swap

优点：

1
2
3

创建简单
大小调整相对方便
不需要单独分区

缺点：

1
2
3

访问要经过文件系统的数据结构
可能产生外部碎片
效率相对较低

交换分区

单独划出一个磁盘分区作为 swap

优点：

1
2
3

不经过普通文件系统
管理更直接
访问效率通常更高

缺点：

1 2	需要提前分区调整大小不如交换文件灵活

交换文件位于普通文件系统中，访问时可能要经过文件系统的块映射结构，还可能受到文件碎片影响；
交换分区直接作为连续或专门管理的交换区域使用，开销更小。

和虚拟内存的关系

1	虚拟内存 = 请求调页 + 页面置换 + 外存支持

这里的“外存支持”常常就是交换空间。

当页面被换出时：

1 2	如果页面来自普通文件且未修改：可以直接丢弃，需要时从原文件重新读

但如果是匿名页，例如：

1
2
3

堆
栈
进程运行时数据

这些页面没有对应的普通文件，就需要写到交换空间。

9.7 磁盘容错技术 / RAID

磁盘可能损坏，系统怎样减少数据丢失，提高可靠性？

通过增加冗余磁盘驱动器、磁盘控制器等方法来提高磁盘系统可靠性。

磁盘容错的核心是：

用冗余换可靠性

也就是说，系统会额外保存一些信息，例如：

备份目录
备份文件分配表
镜像磁盘
校验信息
冗余磁盘

当某个磁盘块、磁盘驱动器或服务器出问题时，可以利用这些冗余信息恢复数据。

第一级容错技术

磁盘表面局部缺陷导致数据丢失

写后读校验

热修复重定向

坏块不能用
↓
改用备用块
↓
记录映射关系

第二级容错技术

磁盘驱动器或磁盘控制器故障

磁盘镜像：两份盘保存一份数据
磁盘双工：还有两个磁盘控制器

1 2	磁盘镜像：两块盘，一个控制器磁盘双工：两块盘，两个控制器

第三级容错技术

服务器级容错

主服务器工作
↓
数据同步到从服务器
↓
主服务器故障
↓
从服务器接管

第三级系统容错是在一、二级容错基础上提供文件服务器镜像功能，主服务器故障时，从服务器成为主服务器继续提供服务

RAID 独立磁盘冗余整列

利用磁盘阵列控制器统一管理一组磁盘驱动器，组成高速、可靠、大容量的磁盘系统；数据会被分拆并均匀写到每个驱动器上

RAID 级别	核心思想	优点	缺点
RAID 0	条带化，无冗余	性能高，利用率高	无容错
RAID 1	镜像	可靠性高，恢复简单	利用率 50%
RAID 3	专用奇偶校验盘	有容错	校验盘可能瓶颈
RAID 4	块级条带 + 专用校验盘	支持块访问	校验盘瓶颈
RAID 5	分布式奇偶校验	性能与可靠性较均衡	写入校验有开销

第十章设备管理

CPU 和内存之外，还有键盘、鼠标、显示器、磁盘、打印机、网卡等设备。
这些设备速度不同、工作方式不同，操作系统怎样统一管理它们？

10.1 I/O 硬件
10.2 I/O 控制方式
10.3 I/O 软件原理
10.4 缓冲技术管理
10.5 设备分配
10.6 SPOOLING 系统

10.1 I/O 硬件

使用特性分类
1. 存储设备：磁盘、磁带、光盘
2. 传输设备：网卡、modem
3. 人机交互设备：键盘、鼠标、显示器、打印机
共享属性分类
1. 独占设备：打印机
2. 共享设备：磁盘
3. 虚拟设备：通过虚拟技术，把一台独占设备改造成多台逻辑设备
  1
  SPOOLING 把打印机改造成可共享设备
  用户感觉自己“独占”了一台打印机，但实际上输出先进入磁盘缓冲区，最后由打印进程统一打印。
信息交换单位分类
1. 块设备：磁盘、磁带
2. 字符设备：键盘、鼠标、显示器、打印机
设备控制器：联系CPU和IO设备
1. CPU与控制器接口
2. 控制器与设备接口
3. IO控制逻辑
IO端口和内存端口的映射
1. 独立IO端口
2. 内存映射IO
  把设备寄存器映射到内存地址空间CPU 像访问内存一样访问设备寄存器

10.2 IO控制方式

CPU、内存和外设之间怎样完成数据传输？

I/O 控制方式的发展过程始终贯穿这个宗旨：减少主机对 I/O 控制的干预。常见方式包括轮询方式、中断方式、DMA 方式和通道方式。

10.2.1 轮询方式 Polling

轮询方式也叫程序直接控制方式。

核心思想：

1 2	CPU 不断检查设备状态设备准备好后，CPU 再进行数据传输

类似你一直刷新快递页面：

1
2
3

到了吗？
到了吗？
到了吗？

轮询过程大致是：

1. CPU 读取设备状态寄存器
2. 判断设备是否忙
3. 如果忙，继续等待
4. 如果不忙，就传输数据

优点：

1 2	实现简单适合很简单、很快的设备

缺点：

1 2	CPU 一直等待，浪费处理器时间设备慢时效率很低

所以轮询方式最大问题是：

1	忙等待 busy-wait

10.2.2 中断方式

中断方式改进了轮询方式。

核心思想：

1 2	CPU 启动 I/O 后，不再一直等待；设备完成后，通过中断通知 CPU。

类似你点外卖后不用一直刷新页面，外卖到了会通知你。

过程：

1. CPU 启动 I/O 操作
2. CPU 去执行其他程序
3. 设备完成 I/O 后发出中断
4. CPU 暂停当前程序，转去执行中断处理程序
5. 处理完后恢复原程序

优点：

1 2	CPU 不必一直等待设备比轮询方式效率高

缺点：

1 2	每传输一部分数据就可能中断 CPU 中断次数多时，开销仍然较大

10.2.3 DMA方式

DMA 全称：

1 2	Direct Memory Access 直接存储器存取

核心思想：

1 2	让 DMA 控制器直接在设备和内存之间传输数据 CPU 只负责开始和结束时参与

过程：

1. CPU 告诉 DMA 控制器：从哪里读、写到哪里、传多少
2. DMA 控制器接管总线
3. 设备和内存之间直接传输一批数据
4. 传输完成后，DMA 控制器中断 CPU

PPT 中说明，DMA 是在外设与内存之间开辟直接的数据交换通路，在控制器控制下成批交换数据。

优点：

1 2	CPU 干预更少适合高速、大批量数据传输

缺点：

1 2	需要 DMA 控制器 DMA 占用总线时，CPU 访问内存可能受影响

对比	中断方式	DMA 方式
数据传输控制者	CPU	DMA 控制器
CPU 参与程度	较多	较少
中断时机	每次或每小段数据传完后中断	一批数据传完后中断
适合场景	少量、低速 I/O	大批量、高速 I/O

10.2.4 通道方式

是DMA进一步发展，用专门的IO处理机来管理IO操作，通道可以执行简单的通道程序

CPU只要发出启动指令，说明要执行什么IO操作

优点：

1 2	CPU 干预最少适合大型机、多设备、大量 I/O 场景

控制方式	CPU 干预程度	特点
轮询方式	最高	CPU 一直检查设备状态
中断方式	较高	设备完成后中断 CPU
DMA 方式	较低	设备和内存直接成批传输
通道方式	最低	专门 I/O 处理机控制 I/O

10.3 IO 软件原理

从“硬件怎么传输”转到“操作系统软件怎么组织 I/O”

应用程序调用 read/write 之后，
操作系统内部经过哪些层次，最后才真正访问设备？

IO软件的设计目标：高效性，尽量减少CPU等待和无效IO开销；通用性，不同设备尽量使用统一接口

IO软件层次结构

用户层 I/O 软件
↓
与设备无关的操作系统 I/O 软件
↓
设备驱动程序
↓
I/O 中断处理程序
↓
硬件

用户层IO软件

典型例子：
1
2
3
4
printf()
scanf()
fread()
fwrite()
比如：
1
printf("hello");
它不是直接操作显示器，而是先在用户层完成格式化，然后再通过系统调用进入内核。

所以用户层 I/O 软件主要负责：
1
2
3
格式化 I/O
调用系统调用
提供更方便的库函数接口
与设备无关的IO软件它的作用是：
1
屏蔽具体设备差异，提供统一接口
它负责的功能包括：
1
2
3
4
5
6
设备命名
设备保护
缓冲管理
错误处理
独占设备的分配和释放
提供统一逻辑块大小
例如用户访问：
1
/dev/print
操作系统要把这个逻辑设备名转换成真正的物理设备和驱动程序。

与设备无关软件负责设备命名、保护、逻辑块、缓冲、空间管理、独占设备分配释放和错误处理等功能
设备驱动程序
设备驱动程序是和具体设备强相关的一层。

它负责：
1
把上层的抽象 I/O 请求转换成设备控制器能识别的具体命令
比如上层说：
1
读磁盘第 100 块
磁盘驱动程序要转换成：
1
2
3
4
5
控制器命令
磁道号
扇区号
读写方向
数据缓冲区地址
设备驱动程序是 I/O 进程与设备控制器之间的通信程序，负责把抽象 I/O 请求转换为设备控制器可接收的具体命令

简单来说就是：操作系统和硬件之间的指令翻译

IO中断处理程序设备完成 I/O 后，会通过中断通知 CPU。

中断处理程序负责：

响应设备中断
判断 I/O 是否完成
检查是否出错
唤醒等待 I/O 的进程
调用后续处理

比如磁盘读完数据后：

磁盘控制器发中断
↓
CPU 进入中断处理程序
↓
中断处理程序通知驱动程序
↓
驱动程序唤醒等待的进程

read()的完整路径

read(fd, buf, 100);

用户层调用read()
通过系统调用进入内核
与设备无关IO层检查fd、权限、缓冲区等
找到对应设备驱动程序
驱动程序向设备控制器发送具体命令
设备执行IO
IO 完成之后发出中断
中断完成程序处理完成事件
数据返回给用户进程

10.4 缓冲技术管理

CPU 和外设速度差很多，怎么减少等待、提高 I/O 效率？

使用缓冲区 buffer

主要作用

缓和 CPU 与设备速度不匹配
减少 I/O 次数
提高 CPU 和设备的并行性

缓冲方式	特点	效率
单缓冲	一个缓冲区	一般
双缓冲	两个缓冲区交替使用	较高（CPU处理和设备IO并行进行）
循环缓冲	多个缓冲区首尾相接	更适合连续数据
缓冲池	系统统一管理多个缓冲区	利用率最高、最灵活

10.5 设备分配

多个进程都要使用 I/O 设备时，操作系统应该把设备分配给谁？

分配什么设备？
分配给哪个进程？
怎样避免冲突和死锁？

分配中的数据结构

DCT：设备控制表，记录某一台设备的信息（类别、标识、状态、等待队列指针，指向控制器的指针）
COCT：控制器控制表，记录设备控制器的信息
CHCT：记录通道信息（通道方式下，I/O 通道相当于专门的 I/O 处理机）
SDT：系统设备表，系统范围内所有设备的总表，全系统设备总目录

分配策略

先来先服务
优先级

设备分配方式

静态分配：进程运行前一次性分配所需设备，运行结束后再释放
动态分配：进程运行过程中需要设备时再申请，用完后释放

安全分配：进程申请到设备后，在 I/O 完成前阻塞自己
不安全分配：进程申请到设备后继续运行，运行中还可以继续申请其他设备

设备独立性

设备独立性也叫：

设备无关性

意思是：

1	应用程序使用逻辑设备名，而不直接指定具体物理设备。

例如程序只写：

输出到打印机

而不是写死：

1	输出到 HP-LaserJet-3020 这台打印机

这样做的好处是：

1
2
3

程序和具体设备解耦
更换设备时程序不用修改
系统可以灵活选择空闲设备

一句话：

1	用户面对逻辑设备，系统负责映射到物理设备。

10.6 SPOOLING 系统

用磁盘模拟外设，把慢速独占设备改造成可共享的虚拟设备。

进程不直接使用打印机，
而是先把打印数据写入磁盘上的输出井；
打印进程再从输出井中取数据，按顺序真正打印。

以打印为例。

如果没有 SPOOLING：

1	进程 A 使用打印机时，进程 B、C 都必须等待

这样设备利用率低，进程也容易阻塞。

有了 SPOOLING：

1
2
3

进程 A、B、C 都可以先把打印任务提交到磁盘
然后继续执行自己的程序
打印机由系统后台慢慢打印这些任务

所以它解决的是：

1
2
3

独占设备共享化
慢速设备与快速 CPU 速度不匹配
进程长时间等待外设

SPOOLING 一般包括四个部分：

输入井
输出井
输入缓冲区
输出缓冲区
输入进程和输出进程

输入井

1	磁盘上的一块区域，用来暂存输入数据

比如读卡机、输入设备传来的数据先放入输入井。

输出井

1	磁盘上的一块区域，用来暂存输出数据

打印任务通常先放入输出井。

输入缓冲区

1	内存中的缓冲区，用来暂存从输入设备送来的数据

输出缓冲区

1	内存中的缓冲区，用来暂存即将送往输出设备的数据

输入进程和输出进程

1 2	输入进程：负责把输入设备的数据送入输入井输出进程：负责把输出井中的数据送到输出设备

假设三个进程都要打印：

1
2
3

进程 A
进程 B
进程 C

它们不是直接抢打印机，而是：

1. 每个进程把打印内容提交给 SPOOLING 系统
2. 系统把打印内容保存到磁盘输出井
3. 每个打印任务形成一个队列
4. 后台打印进程按顺序取出任务
5. 打印机真正打印

所以用户感觉：

1	我已经提交打印任务了

但实际上：

1	打印机可能还在慢慢打印前面的任务

SPOOLING本质：用磁盘空间换取设备共享和并行性

2018.操作系统卷

B实时操作系统
D内核态可以执行CPU中的所有指令
A进程是资源分配的基本单位，线程是调度的基本单位
D需要磁盘读取的资源处于阻塞态，得到资源之后变为就绪态等待CPU的控制权
A临界资源是非共享资源
A
D（RR）时间片轮转调度算法是非抢占
B银行家算法是避免死锁的方法
C循环首次适应算法
C段页式存储管理系统每个作业有一张段表，每个段有一张页表
A页面置换会考虑页表中的修改位
C系统抖动是因为分配的页面太少了（内存不够）
A**？**Spooling
D 通道控制IO方式是CPU干预最少的方式
？
D？
B
D对文件的操作不是文件系统提供？
A
C

填空

操作系统的用户接口包含
管程由
短作业，优先级，时间比
4kb，页框号*物理块大小+页内偏移
？
1MB，20，20MB
？

判断

操作系统

openeuler自定义系统调用

第二章 进程与线程

1.处理器与多核

2.用户态和内核态

2.1 特权指令

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

3.1 Fault 和 Trap 的区别

3.2 定时器中断

PSW 程序状态字

4.进程

5. PCB

6. 进程状态

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

进程创建的大致过程：

阻塞和唤醒的区别

7.1 五态模型

7.2 七态模型

8. 进程切换

9. 进程间通信

两大基本模块

10. 线程

进程和线程核心区别

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

11.1 用户级线程

11.2 内核级线程

11.3 多线程映射模型

第三章 调度

3.1 调度的基本概念

3.1.1 调度队列

3.1.2 调度的三个层次

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

3.1.4 调度性能评价指标

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

3.2.1 作业

3.2.2 进程调度

3.2.3 线程调度

3.3 调度算法

RR(时间片轮转)

多级反馈队列调度

3.4 调度实例

3.4.1 UNIX调度实例

3.4.2 Solaris调度

3.4.3 openEuler / Linux 调度

3.4.4 多核调度问题

3.4.5 Windows 调度

第四章 同步

4.1 同步与互斥

4.1.1 临界资源与临界区

4.2 互斥的实现方法

4.2.1 turn 轮流进入

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

4.2.3

4.2.4

4.2.5

4.3 硬件方法实现互斥

4.3.1 原子指令方法

4.3.2 互斥锁

4.3.3 自旋锁

4.4 信号量

4.4.1 信号量的定义

4.4.2 用信号量实现前驱关系

4.5 进程同步问题

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

4.5.2 读者写者问题

4.5.3 哲学家进餐问题

4.5.4 睡眠的理发师问题

4.6 管程

4.6.1 条件变量 condition

4.7作业题

4.7.1 多个表格读写者问题

4.7.2 生产者消费者

4.7.3 独木桥问题

4.7.4 红黑客过河问题

第五章 死锁

5.1 死锁产生的原因和特征

第六章 主存储器管理

6.1 主存储器的主要功能

6.1.1 内存

6.1.2 功能

第二章进程与线程

第三章调度

第四章同步

第五章死锁

第六章主存储器管理

第七章虚拟内存管理

第九章大容量存储系统

第十章设备管理