操作系统总结

现代操作系统总结

书写规范

1. 定义与定理的格式如下：

   【定义】操作系统：……

   【定理】操作系统定理：……

   若需要在下面写注释，则用引用的形式：

   注：……

2. 列表一律用有序表，而不是无序表，并且每一项若有标题，则标题粗体

3. 凡是有一定”步骤“的算法，均使用类 c 写：

   【方法】：

   1 2 3 4 5 6

   if(){ } //如果 while(){ }//循环

课程结构

资源管理的角度：

1. 硬件资源
   1. 处理器
   2. 存储器
   3. I/O 设备
2. 软件资源
   1. 文件

软件工程的角度：

1. 进程管理子系统
2. 存储管理子系统
3. I/O 设备管理子系统
4. 文件管理子系统

对每个子系统：

1. 基本功能
2. 高效运行

一些常识

单位换算

B, Byte 字节

KB, Kilobyte 千字节 = $2^{10}$ B（ $1024$ B）

MB, Megabyte 兆字节 = $2^{10}$ KB

GB, Gigabyte 千兆字节 = $2^{10}$ MB

TB, Terabyte 太兆字节 = $2^{10}$ GB

系统启动的过程

1. 加电或复位
2. BIOS（Basic I/O System）
3. Boot Loader
4. 操作系统初始化

第一章 引论

一些概念：

计算机的两种运行模式：

1. 内核态、管态 —— 操作系统 —— 对所有硬件具有完全访问权
2. 用户态 —— 软件 —— 只能使用机器指令中的一个子集

操作系统的功能/作用/目的：

1. 从用户的观点：作为用户与计算机之间的硬件接口
2. 从系统管理员的观点：作为资源管理者，实现资源在时间和空间上的共用
3. 从发展的观点：作为扩展机器，给计算机的功能扩展提供支持平台

操作系统的历史4

1. 1945~1955：真空管和穿孔卡片
2. 1955~1965：晶体管和批处理系统
   1. 新技术：
      1. I/O 与计算并行：中断技术
      2. 多道程序设计：存储保护技术
   2. 特点：
      1. 用户脱机使用计算机
      2. 成批处理作业
      3. 多道程序运行
3. 1965~1980：集成电路和多道程序设计 分时操作系统
   1. 新技术：时间片轮转技术（抢占式、剥夺式）
   2. 特点：
      1. 交互性
      2. 多用户
      3. 独立性
4. 1980~至今：个人计算机 实时操作系统（嵌入式计算）
   1. 新技术：？
   2. 特点：
      1. 即时响应
      2. 高可靠性

   下面说几个重要的操作系统：

5. MULTICS：分时操作系统，幻想用一台机器满足整个波士顿地区用户的需求，虽然失败，但对后续的操作系统影响深远
6. UNIX：由参与 MULTICS 研制的贝尔实验室科学家 Ken Thompson 开发，它有两个重要的分支：
   1. BSD（Berkelet Software Distribution）：由加州大学伯克利分校开发，它有一个重要的分支：MACH，是第一个微内核的 OS，也是第一个用软件工程开发的 OS。MACH 又有一个重要的分支：苹果的 NeXT，也就是 Mac OS 的前身
   2. Linux：由芬兰学生 Linux Torvalds 开发，目前使用最广的系统

7. Windows：微软的操作系统，最古老的是 MS-DOS，但我们现在使用的 Windows10 起源于 Windows NT，而不是 MS-DOS，因为它俩的内核完全不同

   

第二章 进程和线程

一个非常重要的概念：

1. 并行： 指两个或两个以上进程在 同一时刻 运行

   

2. 并发：指两个或两个以上进程共享一个 CPU，在 同一时间段 运行，但在同一时刻只有一个进程运行

   

进程的基本概念

进程的状态

三状态：

1. 运行态：实际占用 CPU
2. 就绪态：可运行，但不在 CPU 上
3. 阻塞态：因等待某个事件（比如用户输入）而睡眠

如果算上初始和终止，则为五状态：

在实际中，为七状态，多了两种状态：

1. 挂起阻塞状态
2. 挂起就绪状态

挂起指的是：在资源不足的情况下，操作系统对在内存中的程序进行合理的安排，其中有的进程被暂时调离出内存，当条件允许的时候，会被操作系统再次调回内存，重新进入等待被执行的状态即就绪态。

在此引入三级调度的概念：

1. 高级调度（作业调度）：程序从硬盘上变为进程（创建到就绪）
2. 中级调度（内存调度）：进程从内存上转移到硬盘swap space上（挂起/释放）
3. 低级调度（进程调度）：内存内的进程轮流上下 CPU（就绪/执行）

进程的描述

进程的静态描述由 3 部分组成：

1. 进程控制块（PCB，process control block）：PCB是系统感知进程的唯一实体，PCB的全部或部分常驻内存。PCB 包含以下信息：
   1. 描述信息：
      1. 进程名/进程标识号 PID
      2. 用户名/用户标识号
      3. 进程间的家族关系
   2. 控制信息
      1. 当前状态（初始、就绪、执行、等待、终止）
      2. 进程优先级
   3. 资源信息
      1. 占用内存大小及数据结构指针
      2. 对换或覆盖的相关信息
2. 程序段
3. 数据集

进程上下文：

1. 用户级上下文：
   1. 用户正文段（程序编译而成）
   2. 用户数据
   3. 用户栈
2. 寄存器级上下文
   1. PC 指针
   2. PSW 寄存器
   3. 栈指针
   4. 通用寄存器
3. 系统级上下文
   1. 静态部分：PCB 结构、虚地址空间映射的相关表格、核心栈
   2. 动态部分：

进程间通信67

进程间通信问题，又称 IPC问题（Inter Process Communication），包括以下三个：

1. 进程间的消息传递
2. 进程间互斥
3. 进程间同步

下面间逐一分析。

进程间互斥

生产者-消费者问题

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#define N 10 //缓冲区中槽的数目 typedef int semaphore; //信号量是一种特殊的整数类型 semaphore mutex = 1; //控制对临界区的控制 semaphore empty = N; //空槽数目 semaphore full = 0; //满槽数目 void producer(void) { char item; while(1){ char = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); } } void consumer(void) { int item; while(1){ down(&full); down(&mutex); item=remove_item(); up(&mutex); up(&empty); consum_item(item); } }

第三章 死锁

资源

资源分为：

1. 共享资源：资源可同时使用
2. 互斥资源：资源只允许一个进程使用
   1. 可抢占式资源：可以从拥有它的进程中抢占而不会产生副作用
   2. 不可抢占式资源：在不引起进程失败的情况下，无法从拥有它的进程中抢占过来

死锁的简介249

死锁产生的必要条件：

1. 互斥条件：资源要么分配给一个进程，要么可用
2. 占有和等待条件：已占有资源的进程可以再请求新的资源
3. 不可抢占条件：已占有的资源不能被抢占
4. 环路等待条件：有两个或以上进程组成一个环路，每个进程都在等待下一个进程所占有的资源

处理死锁的方法：

1. 忽略它（干脆不处理了）
2. 检测死锁并恢复（监测发送并处理）
3. 仔细分配资源（避免产生）
4. 破坏死锁产生的四个条件（从源头预防）

下面将说说四种情况

忽略它（鸵鸟算法）251

虽然听起来很扯淡，但 Linux 和 Windows 都采用这种方法

原因：

1. 死锁发生的概率很小
2. 处理死锁的开销太大

优点：

1. 方便
2. 正确

检测并恢复251

检测

假设每种资源只有一个：（基于图的检测算法）

1. 构造一个资源分配图
2. 对资源分配图进行深度优先搜索
3. 若形成了环，则形成了死锁
4. 将所有路径都遍历一次

假设每种资源有多个：（基于矩阵的检测算法）

1. 构造下面四种数据结构：
   1. 假设有 m 种资源，则现有资源向量（existing resource vector）为：$\vec{E}=(E_1， E_2, \cdots , E_m)$，代表每种资源总的数量
   2. 可用资源向量（available resource vector)为：$\vec{A}=(A_1, A_2, \cdots, A_m)$，代表每种资源可用（未分配）的数量
   3. 当前分配矩阵（current allocation matrix)： $\begin{bmatrix} C_{11} & C_{12} & \cdots & C_{1m} \\ C_{21} & C_{22} & \cdots & C_{2m} \\ \vdots & \vdots & & \vdots \\ C_{n1} & C_{n2} & \cdots & C_{nm} \end{bmatrix}$ 第 $n$ 行代表进程 $n$ 已分配的资源
   4. 请求矩阵（request matrix）： $\begin{bmatrix} R_{11} & R_{12} & \cdots & R_{1m} \\ R_{21} & R_{22} & \cdots & R_{2m} \\ \vdots & \vdots & & \vdots \\ R_{n1} & R_{n2} & \cdots & R_{nm} \end{bmatrix}$ 第 $n$ 行代表进程 $n$ 请求的资源
2. 对进程 $i$ 运行如下算法：
   1. 考察 R矩阵的第 $i$ 行，若其所有列都小于 A向量，则说明它的请求可以被满足，将这行标记
   2. 若它的请求可以被满足，则它的资源会在使用完后释放出来，故将 C矩阵的第 $i$ 行加到 A向量上
3. 对其他未标记的行重复以上算法，直到没有进程可被标记为止，没有被标记的进程即为死锁进程

恢复

1. 利用抢占恢复：将资源从一个进程中强行取走给另一个资源使用，然后再送回。
2. 利用回滚恢复：周期性对进程进行检查点检查（checkpointed），储存一系列的检查点文件，一旦检测到死锁，将进程回滚到获取资源前，然后将资源分配给一个死锁进程，而其他进程要等到死锁进程结束后才能获取资源。
3. 通过杀死进程恢复：杀死环内的进程，打破死锁；或杀死环外的进程，为环内进程提供资源。最好杀死可以从头开始运行而且不会发生副作用的进程

死锁避免 255

找到一种分配顺序，使得死锁不会发生，有如下两类算法：

资源轨迹图

1. 横轴代表程序A，纵轴代表程序B
2. “$\leftarrow!\rightarrow$ ” 代表程序需要资源的阶段
3. 浅阴影代表两个程序同时需要打印机或绘图仪
4. 深阴影代表两个程序出现死锁
5. 虚线代表程序运行时分配资源的轨迹，只能从下到上，从左到右
6. 目标就是使轨迹不要进入深阴影

银行家算法

【定义】安全状态：对于某个时刻的资源状态，存在一种调度次序能使每一个进程运行完毕，则称该状态为安全状态，反之为不安全状态

注：不安全状态并不代表一定会发生死锁，因为可能在运行过程中，有其他程序释放资源

银行家算法（banker’s algorithm）：

1. os 分配资源 = 银行家给客户贷款
2. 在某个时刻，如果银行家无法满足任何一个客户的需求，则为不安全状态；能满足客户其中之一的要求，则为安全状态

运用银行家算法检测状态是否安全的步骤同上面 检测并恢复：基于矩阵的检测算法 一模一样

死锁预防258

破坏死锁产生的四个条件：

1. 破坏互斥条件：令资源可以被多个程序独占，采用 假脱机打印机（spooling printer），由打印机守护进程占有打印机，而其他进程向其传递打印信息。（有可能因为磁盘空间耗尽导致死锁）
2. 破坏占有并等待条件：
   1. 方法一（破坏等待）：规定所有进程在开始执行前请求所需的全部资源，这样它就不会等待（要求进程在开始时明确所需的全部资源，否则无法实现）。
   2. 方法二（破坏占有）：当进程请求资源时，要先释放所有占有的资源，再尝试一次获取所需的全部资源
3. 破坏不可抢占条件：允许抢占，但可能会出现混乱（比如打印机只打印一半）
4. 破环环路等待条件：
   1. 对资源编号，进程必须先请求编号小的资源（考虑只有两个进程，两种资源的死锁即可理解）；
   2. 另一种变种是进程不允许请求编号比当前所占有资源编号小的资源（道理同上）

活锁（不考）261

两个进程出现了死锁，于是它们都释放了自己的资源，然后又同步的获取资源，于是又出现了死锁。最终它俩步调一致地同时给对方让路，导致谁也无法前进。

活锁与死锁的区别是：进程发生死锁后，会进入阻塞状态；但发生活锁，不会发生阻塞，只会空耗 CPU 直到时间片用完。

饥饿262

进程有不同的优先级，优先级高的能先分配到资源，会导致优先级低的一直分配不到资源（一直被插队）

第四章 内存管理

程序在内存中的安排方法可以分为：

1. 连续：一个程序占据连续的一段内存空间
   1. 分区技术：简单/虚拟
2. 离散：一个程序占据离散的内存空间
   1. 分页技术：简单/虚拟
   2. 分段技术

简单指的是：进程要运行时，全部装入内存才能运行；虚拟指的是：进程只装入需要的部分

一些术语：

多级存储体系

三级层次：

1. 高速缓冲存储器 cache
2. 主存储器 memory
3. 辅助存储器 I/O

为什么：① 为了解决对存储器要求容量大，速度快，成本低三者之间的矛盾 ② 为了缓解主存储器读写速度慢，不能满足CPU运行速度需要的矛盾

交换技术106

【定义】交换（swap）技术：将内存中处于等待的进程换出内存，放到硬盘中，要运行时再调入内存

地址转换（重定位）

【定义】重定位：把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程

【定义】基址寄存器（BR，base register）：当前进程的起始地址。基址寄存器在每个CPU中只有一个。其他进程的起始地址在 PCB 里

【定义】界限寄存器（Bounds register）：当前进程的终止地址

地址转换：MA（memory address）=（BR）+（VR），然后将 MA 与 界限寄存器比较，若超出，则发生中断。

地址转换是多道程序并发运行的基础，避免了使用绝对地址造成的进程间干扰。

静态地址重定位

思想：在程序执行前，由装配程序将所有指令的虚拟地址 VA加上首地址 BA

评价：

1. 优点：无需硬件支持
2. 缺点：无法实现虚拟内存，因为要求

动态地址重定位

思想：在程序执行过程中，在 CPU 访问内存前，依靠硬件完成重定位

程序寻找某一地址的过程：程序 —-> 虚拟地址（virtual address） —-> 内存管理单元（Memory Management Unit，MMU） —-> 物理内存地址

虚拟内存109

【定义】虚拟内存 的基本思想：每个程序拥有自己的地址空间（即内存中的一部分），这个空间被分为多个块，每个块称为页面（page），页内的地址连续。页被映射到物理内存，但不一定所有的页都在内存中才能运行程序，当一个页不在内存中时，由操作系统将缺失的部分从硬盘装入内存中。

程序寻找某一地址的过程：程序 —-> 虚拟地址（virtual address） —-> 内存管理单元（Memory Management Unit，MMU） —-> 物理内存地址

分区技术

比较好的总结：操作系统——分区存储管理 （同时也推荐这个人的其他总结）

总的来说，分区技术就是指将内存划分为

固定分区技术（静态分区）

【定义】固定分区：操作系统将内存固定地划分为多个大区域（大小可相等可不等），并且在系统运行的过程中，分区的长度和个数都保持不变。

进程进入内存的过程：进程先查找空闲的分区，然后比较空间的大小和进程的大小，直到找到合适的分区放进去。若无空闲分区，操作系统则 swap 一个分区出去

优势：实现简单，系统开销小

缺点：

1. 存在内部碎片（小进程放入大分区），内存的利用率较低
2. 分区尺寸固定，无法运行大程序
3. 分区数目固定，使活动进程的数目受限

动态分区技术

【定义】动态分区：在作业要求装入内存时，根据用户作业的大小和当时内存空间使用情况决定是否为该作业分配一个分区。分区的大小、个数、位置都不是预先确定的。

缺点：

1. 存在外部碎片（离散的空闲分区导致总空间足够，但大进程无法装入，如图）

【定义】内存紧凑（memory comaction）：为了使外部碎片得到充分利用，将所有内存向下移动，使小的空闲区合并为大的空闲区。系统开销较大，并且要求系统有动态重定位功能。

为了减小外部碎片，需要考虑分区的放置（分配）算法：有下面三种：

首次适配算法（first fit）

思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

评价：简单，性能最好，一是因为它搜索的分区较少，二是因为只从一端开始找，那么另一端就很可能有适合大进程的分区，紧凑的频率就较低

下次适配算法（next fit）

思想：和首次适配算法差不多，不同的是每次都从上次结束的地方开始找

评价：比首次适配算法稍差，因为可能将大块的内存切了

最佳适配算法（best fit）

思想：从所有空闲区中挑选一个能满足要求的最小空闲区，需要先对所有空闲分区排序

评价：出乎意料的是，性能最差，浪费也较多，因为用了最新的空间后，剩下的碎片会更小，更难找到一个合适的进程放入，导致常常需要紧凑。

最差适应算法（worst fit）

思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时，优先使用最大的连续空闲区，这样分配后的空闲区就不会太小，更方便使用。

分区管理

无论是固定分区还是动态分区，都需要对空闲内存进行管理。有两种管理方法：

1. 使用位图：每一位代表一个分配单元（0为空闲，1为占用，或相反），多个分配单元构成一个分区。分配单元越小，位图越大。简单，但查找空闲分区时需要找出连续的0，比较费时。
2. 使用链表：每个节点表示一个分区，包含以下域：空闲or占用、起始地址、长度、下一节点。当内存终止时可以非常方便地更新链表

分页技术110

基本原理

1. 将整个系统的内存空间划分成一系列大小相等的块，每一块称为一个 物理块、物理页 或 实页，页架 或 页帧、页框（frame），可简称为 块（block）。所有的页框按物理地址递增顺序连续编号为0、1、2……
2. 每个作业的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个 逻辑页 或 虚页，也有人叫 页面，可简称为 页（page）。所有的页按照逻辑地址递增顺序连续编号为0、1、2……
3. 一个作业，只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。系统装入作业时，以页为单位分配内存，一页分配一个页框，作业所有的页所占的页框可以不连续。系统同时为每个作业建立一个页号与页框号的对照表，称为页表（page table），页表放在内存中。最基本的页表包括：
   1. 页号
   2. 对应页框号
4. CPU 并不直接去计算物理地址，而是交给 MMU 处理。MMU 先通过 页表寄存器（记录页表起始地址）找到页表在内存的位置，然后再通过页表计算地址。

考试：计算页式存储的虚地址对应物理地址的方法：

1. 页号 = 逻辑地址/页面长度，然后通过查页表找到对应页框
2. 页内偏移量 = 逻辑地址%页面长度
3. 物理地址 = 页框号 * 页面长度 + 页内偏移量

页表

页表

分段技术134

第五章 I/O

硬件原理

I/O设备的分类

按设备功能分类：

1. 存储型设备
2. 输入输出型设备
3. 数据通信型设备

按数据的组织分类：

1. 块设备：以数据块为单位存储、传输数据
2. 字符设备：以字节为单位存储、传输数据

按资源分配分类：

1. 独占式设备
2. 共享式设备
3. 虚拟式设备（SPOOLing技术）：用高速设备模拟低速设备，用共享设备模拟虚拟设备

设备控制器

I/O 设备的控制方式

程序控制 I/O（忙等待模式）

CPU 直接与 I/O 设备通信，CPU 需要不断查询 I/O 设备的端口状态， 导致CPU的利用率相当低。唯一的优点是简单。

中断控制 I/O

CPU发出读命令，然后保存当前运行程序的上下文（现场，包括程序计数器及处理机寄存器），当前程序阻塞，转去执行其他程序； 当有来自I/O控制器的中断时，CPU保存当前正在运行程序的上下文，转去执行中断处理程序处理该中断。

由于中断依然会浪费时间，所以 CPU 的效率也不高。

DMA 控制 I/O（飞跃模式，越过CPU）

DMA 代替 CPU 与设备通信，DMA 传输完一个数据缓冲区后再向 CPU 发出中断，减少了中断次数。

DMA 控制方式与中断驱动方式的主要区别是中断驱动方式在每个数据需要传输时中断 CPU，而 DMA控制方式则是在所要求传送的一批数据全部传送结束时才中断CPU；此外，中断驱动方式数据传送是在中断处理时由CPU控制完成的，而 DMA 控制方式则是在 DMA 控制器的控制下完成的。

I/O 通道机制

I/O通道是指专门负责输入/输出的处理机，它相当于一个小型的处理机，可以从 CPU 接受复杂的 I/O 指令。

当 CPU 要完成一组相关的读（或写）操作及有关控制时，只需向 I/O 通道发送一条 I/O 指令，以给出其所要执行的通道程序的首地址和要访问的 I/O 设备，通道接到该指令后，通过执行通道程序便可完成 CPU 指定的I/O任务，数据传送结束时向 CPU 发中断请求。

I/O 通道与 DMA 方式的区别是：DMA 方式需要CPU来控制传输的数据块大小、传输的内存位置，而通道方式中这些信息是由通道控制的。另外，每个 DMA 控制器对应一台设备与内存传递数据，而一个通道可以控制多台设备与内存的数据交换。