操作系统串讲

前言

文章内容来源：东北大学的操作系统MOOC视频
在操作系统的不同阶段，计算机的工作形式也不同，不要在一开始就将操作系统在心里预设成现代的 windows 或 linux 操作系统，以及将计算机预设成个人电脑等，防止代错对象、误导理解
在操作系统的学习过程中，会出现：作业、任务、程序之类的词，它们是类似的概念，只是在不同的操作系统阶段对计算机需要处理的问题的代称。以及计算机、处理机、主机之类的词，都是指的具有计算能力的硬件。希望大家不要被术语所误导
在学习操作系统的过程中，本文会从简单的算法/解决方案逐步引申出复杂成熟的算法/解决方案，这样的过程可以体现出思维的发散性，方便大家理解记忆，不建议各位同学在初次学习时直接去看成熟的算法/解决方案，否则可能理解较浅，过时则忘

操作系统概述

操作系统的概念

操作系统在计算机系统中的位置：

操作系统本身属于系统软件，在硬件之上、应用软件之下，是应用软件使用硬件能力的接口。可以说硬件这块儿“硬骨头”都让操作系统啃了，使得普通用户、程序员能够方便、高效、安全的使用计算机
操作系统的定义：操作系统是计算机系统中的一个系统软件，它是一些程序模块的集合，它们能以尽量有效、合理的方式组织和管理计算机的软硬件资源、组织计算机的工作流程，控制程序的执行，并向用户提供各种服务功能

操作系统的发展历史

先要概念介绍

联机：I/O设备直接与主机连接，即：输入设备 -> 主机 -> 输出设备。在这种模式下，当作业输入时，主机就必须接收输入，不能再进行其他操作; 当作业结果输出时，主机就必须控制输出，不能再进行其他操作。在输入、输出时，可能I/O设备执行速度较慢，则主机执行速度也要受制于I/O设备
脱机：I/O设备不直接与主机连接，而是通过卫星机间接与主机相连，即：输入设备 -> 卫星机 -> 主机 -> 卫星机 -> 输出设备。卫星机类似于缓冲区，在输入设备将作业输入到卫星机的过程，主机仍可以执行已经录入到内存中的作业，当作业完全输入到卫星机后，主机再一次性将作业录入到内存; 当作业执行完成后，主机将作业结果一次性输出到卫星机，再由卫星机输出到输出设备。在这种模式下，作业的输入、作业结果的输出与主机的执行可以并行发生，提高了主机的利用率，主机的执行速度虽受制于卫星机的读写速度但也比受制于I/O设备要快。
批处理：批则就是指多个，用户将一批(多个)作业输入到输入设备，主机处理后，作业结果再成批输出到输出设备。反之，非批处理，则是将一个作业输入到输入设备，主机处理后，再将一个作业结果输出到输出设备。
单道：主机一次只从输入设备调入一个作业到内存进行处理，处理完成后将结果输出到输出设备后，再从输入设备调入另一个作业到内存进行处理

如上图，在单道系统下，当单个作业请求输入时，须在等待输入的完成后才可以继续进行计算，在中间的等待过程中主机处于空闲状态，主机利用率不高
多道：主机根据内存情况一次从输入设备尽可能多的调入多个作业到内存中，多个作业交替调度执行，执行完成后输出结果到输出设备，如果内存允许，则继续从输入设备调入作业执行

如上图，在多道系统下，多个作业被交替调度执行，当程序A需要等待I/O时，由程序B执行，反之程序B需要等待I/O时，由程序A执行，这样使得主机尽可能一直都在被使用，提高了主机的利用率

对单/多道批处理对比如下：

以上，批处理强调的是作业输入过程是不是有多个作业进行输入，单/多道强调的是主机处理作业过程中是不是有单/多个作业进行执行。如果作业一次输入多个，而主机仅调度一个作业到内存执行，则为单道批处理; 如果作业一次输入多个，主机也调度多个作业到内存执行，则为多道批处理。对上述更优的概念进行整合，可以得到脱机多道批处理是我们主要的研究对象

发展历史

无操作系统阶段：普通用户使用不了计算机，计算机用户都是操作员，是计算机专业人员，通过纸带将机器语言输入到计算机执行，即：从输入设备输入单个作业 -> 在处理机执行 -> 输出结果到输出设备 -> 从输入设备输入单个作业 -> ... 这样的串行工作流。在这一阶段，计算机利用率低，用户独占全机所有资源
批处理阶段：相比于上一阶段，作业可以一次输入多个，主机也可以一次调入多个作业到内存执行，解决了主机利用率低、用户独占全机所有资源的问题。其中监督程序对作业使用I/O时的调度、作业之间交替执行的调度等行为也开始体现出操作系统的特性，因此监督程序是操作系统的早期雏形。

批处理作业调度示意图：

以上，对用户独占进行解释：假如用户A将自己的问题描述给计算机操作员，操作员将作业录入到计算机执行后，用户B又来了，计算机操作员同样需要将用户B的问题转为作业后录入到计算机，如果用户B的作业需要等用户A的作业执行完才能进行执行，那么此时相当于全机所有资源是被用户A独占的; 如果用户B的作业可以跟用户A的作业在主机交替执行，则全机所有资源是被用户A、用户B共用的，则没有被独占

分时系统阶段：在上一阶段，通过对多道程序的调度解决了主机利用率低的问题，但没有解决公平性问题：如果作业A进入内存执行后，一直不进行I/O请求让出执行权，那么作业A后面的作业就都没有机会得到执行。为了解决这一问题，操作系统将处理机的运行时间分成很短的时间片，按时间片轮流把处理机分配给各作业使用，如图：
实时系统阶段：在上一阶段，通过分时机制解决了公平性问题，但没有考虑到作业的紧迫程度，比如在工业过程控制、军事实时控制等领域，某些作业必须在一定时间范围之内完成，如果同上一阶段一样，将它们的执行时间分散到其他不紧迫作业的多个时间片中，可能会因执行时间过长导致作业失败。为了解决这一问题，操作系统将作业进行优先级分类，优先级高的先执行，甚至可以抢占正在执行的低优先级作业的执行权; 优先级相同的作业之间再进行分时执行。

下图为对操作系统发展的各个阶段的对比：
在这里插入图片描述
在现代的操作系统中，通常兼具批处理、分时、实时系统的功能，被称作通用操作系统。

操作系统的功能

在上述操作系统的历史中，将操作系统分为了：批处理、分时、实时系统。这其实是按操作系统对处理机的调度策略进行分类的。操作系统除了对处理机进行管理之外，还包括：存储管理、设备管理、文件管理、用户接口。

处理机管理

完成处理机资源的分配、调度、回收等功能

存储管理

存储器的分配与回收
地址映射：逻辑地址到内存物理地址的映射
存储保护：保证进程间相互隔离
利用覆盖、交换、虚拟存储等技术提高内存利用率，扩大进程的内存空间

设备管理

设备的分配与回收
利用设备驱动程序完成对设备的操作
提供统一的设备接口，提高可适应性
利用缓冲区技术匹配CPU与外设的速度，提高两者的利用率

文件管理

用户接口

命令接口：例如 cd、ls、echo 等在命令行/终端窗口使用的命令，或者在具有UI界面的操作系统中(如: windows)，对命令接口进一步封装，通过图形操作间接使用命令接口，例如双击打开文件夹，相当于使用了 cd 命令

另一种使用命令接口的方式是将其编写成 shell脚本(linux上) 或 bat 脚本(windows上)，作为批处理运行。之所以将其称作批处理，是因为将每一个命令看成一个程序，脚本通常包含多个命令，则就是一次录入多个程序，执行时从上向下按顺序逐个执行每个程序，即单道批处理

shell 脚本示意如下，截图来自菜鸟教程。

同时应该注意到，为了方便编程，除了命令接口之外，还引入了程序控制语句、赋值等特性使得命令接口编程更加灵活
编程接口：为程序调用操作系统功能所提供的接口，包括系统调用和库函数，例如在编程时使用的：open、fork、printf 等接口

对系统调用进行说明：
系统调用包含：中断指令调用号，其中，中断指令由机器指令提供，如 int; 调用号则是指操作系统提供的功能的编号。int 0x21H，即是指调用 0x21H号系统调用
从上一条描述可以看出，系统调用的具体功能是由操作系统实现的，而操作系统运行在内核态，用户程序运行在用户态，所以在执行系统调用时，会有 用户态 -> 进入内核态 -> 返回用户态 的状态变化
从上一条描述可以看出，在系统调用时CPU执行权会有执行用户程序 -> 执行操作系统的系统调用 -> 返回执行用户程序的变化，因此在进入系统调用时，需要将当前用户程序的执行现场保存，在系统调用执行完成后，再将执行现场恢复，使得用户程序从断点处继续执行

作业管理

操作系统对处理机的管理，即对处理机的分配、调度、回收，是围绕作业进行的，因此我们应该先学习作业的建立

作业的基本概念

学习作业的建立之前，先了解下什么是作业：

作业 = 程序 + 数据 + 作业说明书。其中，程序+数据被称为作业体，也就是执行需要的部分; 而作业说明书里包含了作业的基本情况、控制描述、资源要求描述等信息，之后会通过作业说明书在内存建立作业控制块(JCB)，是作业管理需要的部分

作业的建立

作业的建立过程：包括作业的输入和作业控制块的建立
- 作业控制块是系统管理作业的必要信息，主要包括：作业名、优先级、估计执行时间、资源要求、作业状态等

进程管理

先要概念介绍

进程：前面不管我们说的是作业还是程序，都是指的静态的代码+数据，而进程指的是程序的一次执行活动，比作：正在进行的程序。进程体现的是程序的动态特性。如果把程序当成菜谱，进程则是照着菜谱烧菜的过程
并行：多个进程在同一时刻同时向前推进执行，常见于多核处理器中
并发：多个进程交替执行，在一段时间内共同向前推进，但在同一时刻仅有最多一个进程在CPU上执行
异步：由于多个进程在CPU上交替执行，进程走走停停，虽然在同一个进程内代码的执行顺序是确定的，但在不同进程之间代码执行的时序是不可确定的。
可再现性：在初始条件相同的情况下，程序的反复执行应该得到相同的结果

以上，由于进程的并发执行所产生的异步性破坏了程序的可再现性，示意如下：

// 共用变量
let a = 1;// 程序 A
a++;			//（1）
console.log(a);	//（2）// 程序 B 
a--;			//（3）
console.log(a);	//（4）// 如果执行顺序为 1、2、3、4，则输出 2、1
// 如果执行顺序为 1、3、2、4，则输出 1、1
// ...

为了解决进程的异步，还需要继续学习后续的进程互斥与同步

进程的描述

进程的组成

进程 = 程序 + 数据 + 进程控制块(PCB)，其中，程序是进程执行的部分，如代码段; 数据是进程处理的对象; PCB是进程的控制结构

进程控制块

PCB 是操作系统维护的、用来记录进程相关信息和管理进程而设置的数据结构
PCB 与进程一一对应
PCB 是操作系统感知进程存在的唯一结构
PCB 的内容包括：

进程上下文

进程是运行在用户态的，因此具有用户级上下文，包括：用户代码段、用户数据段、用户栈
进程某些时候也会进入内核执行，例如在执行系统调用时，因此也具有系统级上下文，包括核心栈，另外，操作系统对进程进行管理时用到的PCB结构和各种资源表格，也是保存在内核空间的，都属于是系统级上下文的内容
最后，进程是运行在CPU上的，因此也具有寄存器上下文，包括：程序寄存器、状态寄存器、栈指针、通用寄存器的值

以上，即进程上下文包括：用户级上下文、系统级上下文、寄存器上下文，如图：
在这里插入图片描述

进程控制块的组织方式

系统把所有PCB组织在一起，形成PCB表
PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度
PCB可以采用链表、索引表等组织方式：
链表：
索引表：

进程状态及转换

在这里插入图片描述

在进程创建时，一般被提交到就续挂起状态，如果内存充足或进程优先级较高，也可以直接被提交到就绪状态
在就绪状态，则有机会得到时间片运行，调度到CPU上转为运行状态
在运行状态，如果时间片用完，则转到就绪状态; 如果需要等待事件的发生则进行到阻塞状态; 如果执行完成则转到终止状态
在阻塞状态，如果事件发生则转到就绪状态，如果内存不足则可能转为阻塞挂起状态，在外存等待事件的发生
在阻塞挂起状态，如果事件发生则转到就绪挂起状态
在就绪挂起状态，如果优先级高则转到就绪状态，等待被调度运行

进程控制原语

原语是指，由若干条指令构成的原子操作过程，作为一个整体而不可分割，要么全都完成，要么全都不做
原语控制示意图：

创建与撤消

创建原语：
撤消原语：

阻塞与唤醒

阻塞原语：
唤醒原语：

挂起与激活

挂起原语：
激活原语：

线程

在传统操作系统中，进程是资源分配、调度运行的基本单位，其中，作为前者进程有自己的地址空间，包括程序、数据、PCB 及其他资源; 作为后者进程在执行过程中与其他进程并发执行，操作系统根据进程状态和调度优先级对进程实施调度。
由于进程的创建、删除和切换过程中时空代价大，限制了系统中的进程数目和并发活动的程度。因此在现代操作系统中，进程作为资源分配的基本单位，调度运行的基本单位被赋予了新的实体——线程

线程的特点

进程与线程的关系：

如上图，一个进程中至少存在一个线程，被称为主线程
多线程模型：

如上图，进程内的线程共享进程内的代码、数据、地址空间和资源，线程间可直接利用共同的地址空间等进行通信
每个进程拥有的地址空间、全局变量、资源等等可以被线程共用，每个线程都拥有自己的程序计数器、堆栈等等，如下图：
线程的创建、调度、终止开销比进程小
进程的终止会导致其所有线程的终止

线程类别

内核线程

线程在核心空间实现，线程切换由内核完成，操作系统知道线程存在，可以按线程分配时间片，多线程的进程可以获得更多的CPU时间，如图：

用户线程

将进程在用户态通过用户线程库改造成多个用户线程，操作系统对用户线程无感知，如图：

优点：

不依赖于核心，可以在不支持内核线程的操作系统上实现线程特性
线程调度在用户态进行，无需用户态/内核态切换，所以相对较快

缺点

时间片按进程分配，线程越多每个线程的执行就越慢
一个线程被阻塞时，整个进程都会被阻塞

轻权进程

将内核态实现的线程，在用户态再通过用户线程库实现多个用户线程，其本身为内核线程不单独拥有资源，但在用户态被当作进程来使用，因此称作轻权进程。如图：

混合线程

即对上述三种线程类型的综合利用，如图：

进程互斥与同步

先要概念介绍

互斥：进程间因使用共同的资源而产生的间接制约关系，例如：进程A在使用打印机时，另一个进程B也请求使用，这时进程B只能被阻塞，等待进程A释放打印机资源后才可以继续执行
同步：进程间因互相协作而产生的直接制约关系，例如：进程A负责生产内容、进程B负责使用内容，则需要让进程A先执行，生产完内容后，再由进程B执行去使用内容，如图：
互斥资源：一次只允许被一个进程使用的资源，也称作临界资源，例如：打印机
互斥区：进程中访问临界资源的一段代码，也称作临界区

进程互斥的实现

实现进程的互斥，其实就是合理的使用临界资源，而使用临界资源的代码称为临界区，对临界区的访问过程如下：
使用互斥区的准则，如图：

软件方法

即，通过代码设计来实现进程互斥

算法一：单标志

设立一个共用整型变量 turn，描述允许进入临界区的进程标识，如下：
在这里插入图片描述

缺点

忙等待，即在进入区被挡住时，cpu也会调度程序执行，在cpu上执行循环操作，占用cpu资源
进程间必须严格交替执行，即程序 Pi执行完成，一定需要 Pj执行，否则Pi不可以再执行

算法二：双标志、先检查

设置一个标志数组flag[]，描述进程是否在临界区，初值均为 false，表示进程不在临界区。且执行时，先检查、后修改，如图：

优点

进程间可以不严格交替执行，即程序Pi执行完成，不需要Pj执行，Pi可以再次执行

缺点

忙等待
进程可能同时进入临界区，即并发执行的顺序为 Pi<a> 、Pj<a>… 时

算法三：双标志、后检查

同上，但执行时，先修改，后检查，如图：

优点

进程间可以不严格交替执行，即程序Pi执行完成，不需要Pj执行，Pi可以再次执行

缺点

忙等待
进程可能同时不能进入临界区，即并发执行的顺序为 Pi<a> 、Pj<a>… 时

算法四：先修改、后检查、后修改者等待

该算法结合前面三种算法。如图：

优点：前面三种算法优点的结合

进程间可以不严格交替执行
临界区可以被正确使用：不存在同时进入或都不能进入临界区的情况

缺点：前面三种算法共同的缺点

忙等待

以上，所有软件方法还有另一个缺点：应用范围通常局限于两个进程间的互斥，在更多的进程下，修改、检查的代码会越来越复杂，正确性不好判断

硬件方法

利用某些硬件指令的原子性，即读写操作由一条指令完成且不会被打断

Test-and-Set 指令 (TS指令)

指令代码如下：
互斥实现如下：

Swap指令

指令代码如下：
互斥实现如下：

开关中断指令

互斥实现如下：

以上，对上述所有硬件方法从本质上看跟软件方法的二、三没有区别，只是利用了代码执行的原子特性，使得修改、检查不会被打断。从代码逻辑上看相比软件方法更加简单，适用于任意数目的进程，且具有软件方法四的全部优点，但也仍然存在忙等待的缺点

信号量与P、V原语

前面的软件、硬件方法都是进程间的协商机制，无法避免忙等待的问题，在此处介绍的方法中由操作系统介入，通过对共享资源的管理，将被拦在进入区外的进程阻塞或挂起，而不是无差别的在CPU上进行循环操作，从而做到让权等待

信号量

结构如下：

其中，count，为非负值时表示信号量代表的资源数目，为负值时表示当前等待临界区的进程数目，即Queue的队列长度;
Queue，表示因为申请该信号量失败而被阻塞的进程的PCB构成的队列。
从以上描述可以看到，被阻塞的进程的PCB是排队的，当资源被释放时会从队首选择一个PCB进行资源分配，每个进程都有机会按次序获得资源，从而做到了有限等待，而不是同之前软件、硬件方法一样，进程获得资源的概率是不可预知的，进而导致某些进程一直获取不到资源，无法得到运行，产生饥饿现象

P、V原语

对信息量进行操作，需要通过 P、V 原语进行

P原语，或称 wait原语，申请使用临界资源时调用 P原语，伪代码如下：
V原语，或称 signal原语，释放临界资源时调用 V原语，伪代码如下：
使用信号量和 P、V原语实现互斥与同步示意：
死锁问题，示意如下

// 假设有两类资源 s1、s2，数量都为1，则// 进程A
P(s1)		// 1
P(s2)		// 2
...
V(s2)
V(s1)// 进程B
P(s2)		// 3
P(s1)		// 4
...
V(s1)
V(s2)/* 
** 以上，如果执行顺序为 1、3、2、4，在前两步中，进程A占用了s1、进程B占用了s2，
** 之后，进程A再申请s2被阻塞，进程B再申请s1被阻塞，两者互相请求对方拥有的资源，
** 且不肯释放自己已经拥有的资源，将导致两个进程都陷入无限等待，进行造成死锁
**//* 
** 有同学可能注意到，只要把进程B获取资源的顺序修改，即先申请s1，再申请s2，就可以避免死锁问题。
** 仅从以上示例分析，确实如此，但如果进程B的业务逻辑要求，必须先使用 s2、后使用 s1呢，另外，
** 在实际的应用过程中，涉及的信号量会更多，很容易写出不易察觉的死锁代码，因此后面还需要学习避免死锁的方法
**/

进程互斥与同步经典问题

包括：生产者-消费者问题、读者-写者问题、哲学家进餐问题，在这里不再赘述，有兴趣的同学可以通过文章首部的视频链接到MOOC慕课学习该课程的 4.8、4.9、4.10 节，来提升对信号量、PV原语的理解及熟练程度

信号量集

我们在前面的信号量小节中，引入了死锁问题，从之前的示例看，死锁是由于对资源的申请顺序不当而产生的，这节的信号量集，用来解决资源的申请顺序问题。

AND型信号量集

将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，伪代码如下：

在这里插入图片描述
以上，大家应该还记得，P原语也叫wait原语，V原语也叫signal原语，而上述伪代码中还分别在这些原语前加了S，大家可以将它看成是 Set 即集合的缩写，表示对信号量集的P、V操作

使用示例，如下：

一般信号量集

主要用于同时需要多种资源、每种占用的数目不同，且可分配的资源还存在一个临界值时的处理
调用形式如下：

其中，Swait(s1, t1, d1) 表示，对于资源 s1，如果资源剩余数目不小于t1，则申请 d1 个资源;
Ssignal(s1, d1) 表示，对于资源 s1，释放资源 d1 个

以上，对于AND型信号量集可以看作是一般信号量集的特殊形式，例如 Swait(s1, s2)，可以看作是一般型信号量集的 Swait(s1, 1, 1, s2, 1, 1)

使用示例，如下：

管程

前面我们通过信号量集，已经可以实现进程的同步与互斥，并在一定程度上避免死锁问题，但仍存在开发体验上的问题：对信号量集的使用是面向过程的编程模式，这意味着，我们会将控制进程同步与互斥的P、V原语写的到处都是，混杂在我们的业务逻辑代码里面，且不阅读整体代码，难以缕清进程间的同步与互斥关系。为了解决该问题，我们接下来要学习的管程，利用面向对象的思想，将控制代码同步的P、V操作，封装在管程对象里，使得代码结构清晰明了、易于复用

管程定义：是关于共享资源的数据结构及一组操作该资源的过程所构成的软件模块
管程的组成：
管程的特点：
管程队列：分别为入口等待队列、紧急等待队列、条件等待队列，条件等待队列因进程等待的条件不同可以有多个。如图：
管程使用示例：可前往文章首部MOOC视频 4.13 小节进行学习

进程间通信

我们知道，为了进程的独立性以及数据和资源保护，操作系统刻意将进程之间互相隔离，即进程A无法访问进程B的地址空间，反之亦然，但有时候进程之间因为某种原因需要进行信息交换，就需要用到本章所学习的进程通信机制
进程间通信分为低级通信与高级通信，低级通信只能传递状态和控制信息，也就是我们前面学习进程互斥与同步所使用的信号量和管程机制。在这一章中，我们主要学习高级通信，可以传递任意数量的数据，包括：共享存储区、管道、消息队列等

共享存储区

进程在通信之前通过关键字key值，向操作系统申请一块共享存储区，然后将这块地址空间映射连接到进程自己的地址空间中，多个进程通过同一个关键字key申请到相同的共享存储区，即可利用对该区域的读写实现信息交换
UNIX 操作系统中，共享存储区使用过程如下：

管道

基于文件系统形成的一种通信方式，利用共享文件实现进程间通信，如图：
无名管道：打开的文件描述符只可以被父子进程访问到，所以只能进行父子进程、或各子进程之间通信，使用示例如下：
命名管道：因为使用时会先创建文件，即任何进程都可以通过文件名打开该文件作为管道进行使用，所以可以用于非父子关系之间的进程通信。

消息队列

在上述两种进程间通信的方式中，都存在这个问题：进程通信时遇到的同步与互斥问题，需要程序员自己编程解决，而下面这种方式中，将同步与互斥的管理封装到了原语中，因此不需要程序员处理

操作系统在内存中维护一组消息缓冲区，发送消息的进程申请消息缓冲区，装满消息后将该缓冲区链接到接收进程的消息队列，当进程从消息队列上取出缓冲区并读出消息后，操作系统再将缓冲区回收以便后续使用，如下：
消息缓冲区结构如下：
为了使用消息队列通信，PCB中需要增加：
用于发送、接收消息的 send、receive 原语，伪码如下：

在这里插入图片描述

死锁

在前面的章节中，我们已经提到过死锁的概念，在这一章中，我们将对死锁问题进行专门的研究，以及学习如何预防、避免、检测死锁的发生。

死锁概念及发生条件

概念：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，这种现象称为进程死锁，这一组进程就称为死锁进程
发生条件，以下四个条件均满足，才会出现死锁：

处理死锁的基本方法

如图：
在这里插入图片描述

预防——破坏死锁发生的条件

预先静态分配法（破坏请求与保持）：预先分配进程所需的全部资源，保证进程不会拥有一部分资源，而等待另一部分资源的情况发生

缺点

预先分配的资源，进程可能不会立即使用，使得资源实际处于闲置状态，降低了资源的利用率
进程在未分配到全部资源之前，无法得到运行，延长了进程的整体执行时间
操作系统难以预知进程在运行过程中所需要哪些资源

有序资源使用法（破坏环路等待）：把资源分类，按顺序排列，进程只能申请已有资源顺序之后的资源，保证请求不形成环路，如下图，进程P4已经获取了R4，就不允许再申请资源R1:

缺点

限制了进程对资源的请求，降低了资源的利用率
对资源的排序工作增加了系统的开销

资源剥夺（破坏非剥夺）：进程申请资源时，可直接剥夺其他进程所拥有的资源。

缺点

只适用于状态可以保存和恢复的资源
进程资源被剥夺的次数过多，对资源的反复分配增加了系统的开销

最后，死锁的发生还剩下最后一种条件：互斥，而这是资源所固有的属性，因此无法从破坏该条件入手来预防死锁

避免

每次在资源分配时都进行判断：如果允许资源分配，是否会造成死锁，若会则不予以分配，反之，则予以分配

银行家算法

背景引入：一个银行家把他的固定资金贷给若干顾客，顾客贷款分若干次进行，并且会告知银行家自己总共要借多少，以及每次需要借多少。若银行家可以按顾客要求借出，则可以安全收回贷款。银行家算法则就是用来判断每次贷款是否是安全的
问题引入，如下：

如上图，可以使资源顺利完成分配的序列被称为安全序列
安全状态：存在安全序列的系统称为安全状态，在安全状态下一定没有死锁发生
多资源类型举例：上面的例子中，进程仅需要磁带机这一类资源，在实际过程中，进程可能会需要多种资源，如下：
算法伪代码，如下：
解释：
1. A[m] = x 表示，资源m还剩下x个
2. U[n][m] = x 表示，进程n占用资源m x个
3. N[n][m] = x 表示，进程n还需要资源m x个
4. R[n][m] = x 表示，进程n申请资源m x 个
检查系统目前状态是否安全，如下：

优点

尽可能不限制对资源的申请，允许互斥、请求与保持、非剥夺条件的出现，资源利用率相对前面的预防方案更高

缺点

系统难以预知进程所需的资源情况
进程之间必须是无关的，不存在同步关系，即只用考虑资源对进程造成的死锁

检测

操作系统不阻止死锁的发生，只是不断的检测系统中是否产生了死锁，一旦产生，就采用某种措施，例如剥夺某进程的资源，来打破死锁，恢复系统的运行

检测时机：进程被阻塞时检测、定时检测、系统资源利用率下降时检测
资源分配图，如下：
死锁定理：可以通过资源分配，使进程变为即不拥有资源也不请求其他资源的孤立结点，从而对资源分配图进行简化，若简化过程中消去了所有的边，所有的进程都成为孤立的结点，则称为完全简化，而死锁状态的资源分配图，是不可完全简化的
死锁恢复：以最小代价恢复系统的运行，如：重启进程、撤消进程、剥夺资源、进程回退

处理机调度

对处理机的调度研究，即研究如何分配处理机资源使其得到充分利用，而利用处理机资源的是进程，因此，对处理机的调度管理，实质上是研究：在多个就绪进程中，选择哪个进程获得处理机资源得到运行（调度算法）、在什么时机触发进程调度（调度时机）、以及在进程调度时需要做哪些工作（进程切换）

我们先对后两者进行介绍

调度时机

正在执行的程序执行完毕时
分时系统中，正在执行的程序时间片用完时
正在执行的程序被因调用阻塞原语、资源不足、被I/O阻塞变为等待状态时
睡眠的程序被唤醒，被加入到就绪队列后（例如优先级较高的进程，会优先被调度获得执行权）
系统调用执行完毕，从系统程序返回到用户程序时

进程切换

决定是否切换
保存当前执行进程的上下文
恢复调度算法选择的进程的上下文
将执行权交给所选进程

调度算法

先要概念介绍

周转时间 = 执行时间 + 等待时间，周转时间越短越好
响应比 = ( 执行时间 + 等待时间) / 执行时间，响应比越小越好

先来先服务 FCFS

按照作业提交或进程加入就绪队列的先后次序分配CPU

特点：

最简单的调度算法
有利于长作业，而不利用短作业
有利于CPU繁忙的作业，而不利用I/O繁忙的作业

解释：第二三点，短作业、I/O繁忙型作业响应比高。即如果作业执行时间较短，那么排队等待的时间就显的长; 如果作业I/O繁忙，每次进入就绪队列时又要重新排队，则将大量的时间浪费在了排队上。反观前者，即长作业或CPU繁忙型作业，在排到CPU后可能一直执行到进程执行完毕，响应比更低

短作业优先 SJF

对预计执行时间短的作业优先分派处理机，但后来的短作业不抢占正在执行的作业

优点

相比 FCFS 缩短了短作业的等待时间，提高了系统的吞吐量

缺点

对长作业不利，可能出现饥饿现象

SJF 变形 —— 最短剩余时间优先 SRT

SJF 算法的抢占式版本，当新就绪进程比当前运行进程具有更短的剩余运行时间时，系统抢占当前运行进程

SJF 变形 —— 最高响应比优先 HRRN (Highest Response Ratio Next)

在进程调度过程中，不断计算进程的响应比，并调度最高响应比的进程执行
对上面的响应比公式化简：响应比 = 1 + 等待时间 / 执行时间
从响应比公式可以看出，影响响应比的两个因素为：等待时间、执行时间，其中等待时间体现的是 FCFS 中的排队时间，执行时间体现的是 SJF 中的执行时间或者剩余执行时间，因此该算法是对 FCFS、SJF 算法的一种结合

优点：

解决了 SJF 算法中的饥饿问题

缺点：

增加了系统的执行开销

时间片轮转算法 (RoundRobin)

在 FCFS 原则基础上，引入时间片机制，即每次从就绪队列队首取出一个进程，让其执行一个时间片，然后通过时钟中断，再调度下一个进程执行

优点：

公平
响应时间快，有利于交互

缺点：

上下文切换需要时空代价

优先级算法

对不同进程分配不同的优先级，优先调度高优先级的进程执行。优先级分配的依据可以是：进程类型，如系统进程优先级较高、对资源的需求，如对资源需求低的进程优先级较高、用户要求，如用户紧迫程度高和付费多的优先级较高。
按优先级确定的时间，可以分为静态优先级、动态优先级;按是否能够被抢占，可以分为抢占式和非抢占式;

动态优先级

在创建进程时赋予优先级，在运行过程中不断调整，从而使调度更灵活。如：等待时间长的优先级调高、持续执行的优先级调低

线性优先级调度 (Selfish Round Robin)

引入两种就绪队列：新创建进程就绪队列、享受服务进程就绪队列
新创建进程就绪队列以速率a增长优先级
享受服务进程就绪队列以速率b增长优先级
当新创建进程就绪队列中的进程优先级大于享受服务进程就绪队列中最低优先级时进入享受服务进程就绪队列
其中：当 b > a > 0 时，享受服务队列中永远只有一个进程，该算法退化为 FCFS 算法; 当 a > b = 0 时，该算法退化成时间片轮转算法

多级队列 (Multiple-level Queue)

该算法引入多个就绪队列，将不同类型的进程划分到不同的队列中，不同的队列可以有不同的优先级、时间片长度、调度策略等

解释：该算法的目的是将不同的进程区别对待，以便实现更合理的调度，但难点在于如何对进程进行区分，进而确定进程该进入哪种队列

多级反馈队列 (Multiple-level Feedback Queue)

该算法引入多个就绪队列，通过反馈调节将不同类型的进程分配到不同的就绪队列中进行区别对待，从而达到一个综合的调度目标
要达到反馈调节的效果，需要进行规则设定，让不同类型的进程在规则影响下自然的被分配到不同的队列中，规则如下：

进程在初始时，都在最高优先级队列，若被调度执行时，执行完时间片，则下一次进入次一级优先级队列中等待; 若被调度执行时，因各种原因未能执行完时间片，则下一次进入同一级优先级队列中等待
调度时优先选择高优先级队列中的进程，高优先级队列中为空时，才调度次一级优先级的队列中的进程执行
在多个就绪队列中，优先级高的队列中的进程所执行的时间片短，反之优先级低的队列中的进程所执行的时间片长（这条规则是为了让等待更长时间的进程获得更长的执行时间，体现公平性）
如果执行时有新进程进入较高优先级队列，则抢先执行新进程（体现该算法是抢占式调度）

解释：
在上述规则的影响下：

若为CPU密集型进程，则在执行过程中，有更大概率执行完时间片，逐渐进入低优先级队列，反之，若为I/O密集型进程，则在执行过程中，有更大概率执行不完时间片，逐渐滞留在高优先级队列
若为短作业，有更大概率在高优先级队列时就已经执行完毕，反之，若为长作业，则有更大概率不断进入低优先级队列
经过上述两条的作用，对占有CPU具有优势的CPU密集型作业、长作业，及对占有CPU具有劣势的I/O密集型作业、短作业进行了分类，并区别对待，实现了综合调度的目的

优点：

进程是CPU密集型、I/O密集型、短作业、长作业哪种类型，不需要操作系统提前预知，它们会在执行过程中自行分类
对不同类型的进程进行了综合调度，解决了前面调度算法出现的饥饿、不公平的现象
该算法结合了时间片轮转、动态优先级、抢占式调度、多级队列等优秀算法思想，是集大成者，也是伯克利 UNIX 操作系统中采用的调度算法

存储管理

存储体系结构

对存储的管理，主要指的是进程运行所需的内存空间的管理，即指的是内存条上的空间，而不是硬盘上外存空间的管理。管理目标是使得尽可能多的程序驻留在内存中，提高CPU利用率。需要做到：逻辑地址到物理地址的映射、存储共享和保护、虚拟存储器管理

地址映射

为了我们编程的方便，每个进程都拥有自己的相对地址空间，例如：0 ~ 4GB，但在内存条这个物理硬件，上面的每一个地址空间，都不能在同一时刻被多个进程使用。如果我们把进程的 0 ~ 4GB 空间直接装在内存条的 0 ~ 4GB 空间，多个进程的地址空间肯定是会冲突的，因此我们只能将进程装在内存条的不同位置，同时建立进程的0~4GB地址空间跟实际装载在内存条物理地址空间的映射，这样我们在编程时，可以使用逻辑地址，然后操作系统再通过映射关系找到真实的物理地址进行访问

静态地址重定位

即在程序装配到内存空间时完成地址映射，如下：
在这里插入图片描述

优点：

简单，无需硬件支持

缺点：

一旦装入内存，无法再移动
程序占用连续的空间，不易共享
只能装入有限数量的程序

动态地址重定位

程序运行过程中，访问地址空间时再临时进行地址变换

硬件上需要一对寄存器，记录装载到的物理空间的起始地址，即基址，以及访问的地址空间的偏移

优点：

可以移动程序，只需要修改BR寄存器中的值即可定位到新的内存空间
可以动态地分配内存

缺点：

为了满足临时地址变换的效率需求，一般需要硬件支持

存储保护和共享

即进程只能在自己所属区域运行，不破坏其他程序和不被其他程序破坏、代码和数据共享、访问控制（读、写、执行）

存储保护

界限保护

所有访问地址必须在上下界之间，如下：

若访问越界则产生越界中断，交由操作系统进行相应处理
补充：用户态进程才受限于上下界范围的内存，核心态进程，即执行操作系统代码时，可以访问整个内存地址空间

访问方式保护

对有权访问内存区域的进程以及访问方式进行记录，如下：

程序链接

为了更好的管理内存，我们需要了解程序是按什么方式加载到内存的

静态链接

在程序执行前，使用链接程序将程序的各模块链接成一个可运行的目标程序，并在程序运行前都装入内存，如下：

装入时动态链接

边装入边链接，在装入一个模块时，发现该模块调用了外部模块，则去寻找相应模块并链接装入，如下：

运行时动态链接

边执行边链接，在执行过程中，若发现被调用模块尚未装入内在，则寻找该模块并链接装入

优点：

节省内存，不需要全部装入即可运行
加快程序的启动速度

虚拟存储器管理

分区管理

先要概念介绍

内碎片：占用分区之内未被利用的空间
外碎片：占用分区之间难以利用的空闲分区

固定分区

把内存区固定地划分为若干个大小相等或不等的连续分区，每个进程能且仅能占用一个分区，如下：
分区一旦划分，在运行过程中每个分区的长度和内存中分区总数不变
将每个进程分配到适应它的最小分区

优点：

易于实现，开销小

缺点：

内碎片造成浪费
分区总数是固定的，限制了系统的并发度

动态分区

内存不预先划分好，而是当进程装入时，根据进程的需求和内存空间使用情况来决定分配

优点：

没有外碎片

缺点：

有外碎片

动态分区分配算法

分配：寻找某个大小大于等于程序要求的空闲分区，若大于，则将该分区分割成两个分区，分配的分区标记为占用，余下的部分标记为空闲
释放：需将相邻的分区合并成一个空闲分区

最先匹配法

由内存地址从低到高开始查找，找到符合要求的第一个分区

优点：

简单、快速

缺点：

随着分配过程推进，低地址不断划分产生较多小分区，每次查找时开销会增大

下次匹配法 (Next-Fit)

从上次分配的分区位置开始向后查找（到最后的分区时再回到开头），找到符合要求的第一个分区

优点：

空闲分区分布均匀

缺点：

较大空闲分区不易保留

最佳匹配法（Best-Fit）

找到大小与要求相差最小的空闲分区

优点：

较大的空闲分区可以被保留

缺点：

外碎片较多

最坏匹配法（Worst-Fit）

找到最大的空闲分区

优点：

外碎片少

缺点：

较大空闲分区无法被保留

覆盖和交换技术

覆盖技术

把程序划分为若干功能上相对独立的程序段，不会同时执行的程序段共享同一块内存区域，如下：
在这里插入图片描述
执行栈先后为：
A、B、F
A、C、D
A、C、E
因此，BF不会与CDE同一时间执行，D不会与E同一时间执行，所以：
就用 100K 运行了 190K 大小的程序

交换技术

将暂时不能执行的程序移出到外存，从而获得空闲内存来装入新程序

简单页式存储管理

将内存条的物理内存空间、程序的逻辑地址空间都划分为同样大小的页，程序加载时，分配所需的全部页，并记录逻辑页到物理页的映射关系，这些页在物理内存中不必连续，如下：
在这里插入图片描述
以及记录映射关系的页表，如下：

系统需要维护一个物理页面表，描述页面占用和空闲信息
系统需要维护一个请求表，记录哪些进程请求了哪些页面，如下：