操作系统（二）——进程与线程

1. 进程与线程

1.1 进程的概念

在多道程序环境下，允许多个程序并发执行，此时他们将失去封闭性，并具有间断性及不可再现性的特征。为此引入进程(Process)的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性（最基本的两个特性，这两个特性在第一章里已经讲过，有遗忘可以去第一章回顾一下）。

所以，我们可以提出进程的概念：进程是程序的一次执行过程。

这里我们提到一个容易被混淆的概念：程序与进程。在此，对两者进行一个区分。

程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。

进程：是动态的，是程序的一次执行过程，同一个程序多次执行会对应多个进程，例如QQ程序被多次执行，就会显示多个QQ登录界面。

为了使参与并发执行的每个程序都能独立运行，必须为之配置一个专门的数据结构，称为进程控制块(PCB)。所谓创建进行，就是创建进程的PCB；撤销进程，就是撤销进程的PCB。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。

由程序段、相关数据和PCB三部分构成了进程实体(又称进程映像)。注意，进程实体状态反应了进程在某一时刻的状态，是静态的。

在引入进程实体的概念后，我们可以将传统操作系统中的进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度（一个进程被调度，就是指操作系统决定让这个进程上CPU执行）的一个独立单位。

注意，在传统定义里所说的系统资源指CPU、存储器和其他设备服务某个进程的”时间”，例如将CPU资源理解为CPU的时间片才准确。又因为进程是这些资源分配和调度的独立单位，即“时间片”分配的独立单位，这就决定了进程一定是一个动态的、过程性的概念。

1.2 进程的组成

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位。它由三部分组成：进程控制块、程序段、数据段。其中最核心的是进程控制块（PCB）。

1.2.1 进程控制块

进程控制块是进程实体的一部分，也是进程存在的唯一标志。

当进程创建时，操作系统为它创建一个PCB，该结构之后便常驻于内存，任意时刻都可以存取，并在进程结束时删除。当进程执行期间，操作系统要记录各种相关信息，而这些信息都会被保存在PCB中，如下图所示。

需要注意，当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的身份证号——PID（进程ID）。

PCB中主要包括进程描述信息、进程控制和管理信息、资源分配清单和CPU相关信息。各部分具体描述如下展示：

1.2.2 程序段

程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意，程序可被多个进程共享，即多个进程可以运行同一个程序。

1.2.3 数据段

一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

1.2.4 进程组成小结

1.2.5 补充拓展——程序的运行过程

程序员将写好的程序经过编译等一系列步骤，最后形成一个可执行文件，存放在硬盘里。若要执行这个程序，需要先将可执行文件从硬盘读到内存当中，并且操作系统会建立一个与之对应的进程。操作系统会建立PCB，并将可执行文件里的指令序列（程序段）读到内存当中，同时程序运行过程中产生的各种数据（数据段）也会保存到内存中。

1.3 进程的特征

进程是由多道程序的并发执行而引出的，它和程序是两个截然不同的概念。程序是静态的，进程是动态的，进程的基本特征是对比单个程序的循序执行提出的。

1.4 进程的概念、组成和特征总结

1.5 进程的状态与转换

1.5.1 进程的状态与转换

进程在其生命周期内，由于系统中各个进程之间的相互制约及系统的运行环境的变化，使得进程的状态也在不断地发生变化。通常进程有以下5种状态：

创建态。进程正在被创建，尚未转到就绪态。
就绪态。进程获得了除CPU外的一切资源，一旦得到CPU，便可立即运行。系统中处于就绪态的进程可能有多个，通常将他们排成一个队列，称为就绪队列。
运行态。进程正在CPU上运行。
阻塞态。又称等待态，进程正在等待某一事件而暂停运行。系统通常将阻塞态的进程也排成一个队列，甚至根据阻塞原因不同，设置多个阻塞队列。
终止态。进程从系统中消失，可能是进程正常结束或其他原因退出运行。

注意区分就绪态和阻塞态：就绪态说明进程已经准备好，只差CPU资源就可以运行。而阻塞态是进程在运行过程中，因缺少相关资源，而暂时无法运行。

接下来，我们以一个实例来对五态进行具体介绍：

首先，我们在运行可执行文件时，系统会为其建立一个PCB，并对其进行资源分配以及PCB初始化，这个阶段称为进程的创建态。当进程被创建以后，便进入就绪态，处于就绪态的进程已经可以运行，至于能不能运行，还需要看CPU有没有处于空闲态，如果CPU一直处于忙碌状态，则进程就停留在就绪态。

当CPU处于空闲状态时，操作系统就会选择一个处于就绪态的进程，让它进CPU进行处理。此时进程就会从就绪态转变为运行态。处于运行态的进行就会执行程序指令。当进程的指令里存在系统调用指令时，例如请求打印机操作，系统会处理该指令，当打印机处于繁忙状态，这个时候进程就无法进行该系统调用指令，于是进程就进入阻塞态。

进入阻塞态的进程由于无法继续往下运行，于是操作系统就当前的进程放回内存中，并从内存中再次调取一个处于就绪态的进程上CPU进行处理。当一段时间以后，打印机完成当前操作处于空闲状态时，这个时候处于阻塞态的进程等待的事件发生了，于是该进程从阻塞态转为就绪态，拥有了再次上CPU运行的权利。

一个进程在运行完以后或执行系统终止以后，就会从运行态转变为终止态，操作系统就会让该进程下CPU，并回收内存空间等资源，最后还会回收该进程的PCB。

通过实例的演示讲解，我们接下来对进程的五态进行一个总结：

创建态 -> 就绪态：系统完成创建进程的一些列工作，包括PCB建立，资源分配等。

就绪态 -> 运行态：处于就绪态的进程被CPU调用以后，获得CPU资源，于是进程由就绪态转变为运行态。

运行态 -> 就绪态：当进程在CPU上运行了很长时间，系统发现CPU分给其的时间片使用完以后，会迫使进程让出CPU，从运行态转变为就绪态，等待下次运行。如果在可剥夺的OS中，有更高优先级的进程就绪时（比如中断），也会迫使当前进程从运行态转变为就绪态。

运行态 -> 阻塞态：进程请求某一事件发生时，该事件无法发生，于是就从运行态转变为阻塞态。

阻塞态 -> 就绪态：当请求的事件发生以后，OS会让进程从阻塞态转变为就绪态。

运行态 -> 终止态：当进程运行结束，或运行过程中遇到不可修复的错误以后，会从运行态转变为终止态。

进程的整个生命周期中，大部分时间处于运行态、就绪态和阻塞态，所以这三种状态也被称为进程三种基本状态。

在进程PCB中，还会有一个变量来表示进程的当前状态，为了方便对同一个状态下的进程进行统一管理，OS会将各个进程的PCB组织起来。

1.5.2 进程的组织方式

1.5.2.1 链接方式

OS使用链接方式进行进程的组织。会使用不同指针指向不同状态的进程，并把同状态的进程链接起来。通常还会把优先级高的进程放在队头。

1.5.2.2 索引方式

采用索引的组织方式，OS会给不同状态的进程建立索引表，然后索引表又会指向相同状态的PCB，具体模型如下图

1.5.2.3 组织方式思维图

1.5.3 进程的状态与转换小结

1.6 进程的控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

简化理解：进程控制就是要实现进程状态转换。

进程控制的实现是通过原语实现的，在第一章里我们说过，原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须一气呵成，不可中断。

为什么进程控制的程序需要一气呵成呢？具体的原因可以参考下图，假设state=2表示阻塞态，这时候PCB2等待的事件发生，则操作系统会将PCB2转变成就绪态，并将他放入就绪队列指针。这个时候会经历两步骤，第一步将PCB2的state设为1；第二步将PCB2从阻塞队列放到就绪队列。如果进程控制程序不一气呵成的话，在第一步后收到中断信号，那么PCB2的state=1，但是它却被放在阻塞队列里，这个时候就出现错误堆放的问题。

所以，如果进程控制程序不能一气呵成，就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作。

原语程序刚好能满足进程控制程序一气呵成的特点，所以进程控制程序采用原语设计。

那原语的原子性究竟是怎么实现的呢？这就牵扯到了关中断指令以及开中断指令。具体如下。

如图是一段内核程序，在前面我们学过，每执行完一条指令时，程序都要判断有没有中断信号。如果在这里使用了关中断指令，这个时候内核程序执行时，就不会去判断有没有中断信号，而是会一直往下运行，直到运行完开中断指令以后，才会再次去判断中断信号。这就是原语的实现。

需要注意的是，关中断和开中断指令是特权指令，只能内核程序使用，而不能让每个用户都使用，如果每个人都能调用的话，会导致CPU运行一个的程序，直到运行完才会运行别人的程序，如果运行过程中出现等待事件等问题，则会出现CPU一直被占用的情况。

对于原语以及进程控制相关知识了解完以后，接下来我们就可以讨论进程控制相关的原语了。

1.6.1 进程的创建相关原语

1.6.2 进程的终止相关原语

1.6.2 进程的阻塞和唤醒原语

1.6.3 进程的切换原语

这里稍微讲解一下进程的运行环境。运行环境，顾名思义，就是进程在运行时，当前计算机所处的一种状态，包括当前寄存器的数值，数据的位置等等。在我们运行一个进程时，这个进程在运行过程中所产生的数据等信息都会存到相应的寄存器里，但是这些寄存器并不是只为这一个进程服务。如果这个时候需要执行另一个进程时，系统会将当前正在运行的进程的寄存器、数据等环境信息存入到当前进程的PCB里。然后清空当前环境，为另一个进程的运行提供资源。如果另一个进程运行结束以后，想切回原来的进程，这时候OS会从原进程的PCB里读取环境信息，并复原到该进程停止运行时所处的环境状态。

注意，保存环境信息和复原环境信息是保证进程并发执行的一个很关键的技术。

1.6.4 进程控制的小结

这部分有关进程控制的相关原语，我写的很简陋。这里大部分都是理解的东西，参考1.5.1走一遍进程的运行过程，不仅完全可以理解，还会绝对这里很简单，所以我就不多说了。毕竟别人塞到嘴里的不一定好吃，但自己吃到嘴里的一定是自己想吃的。

1.7 进程的通信

进程通信（IPC），指进程之间的信息交换。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

如果想实现两个进程间的通信，主要有以下三种方法：共享存储、消息传递、管道通信。

1.7.1 共享存储

进程可以创建一个可直接访问的共享存储空间，通过对这片共享空间进行读/写操作可以实现进程之间的信息交换。

需要注意的是，一个存储空间可以被多个进程读写，如果多个进程同时读写会出现错误，所以在对共享空间进行读/写操作时，需要使用同步互斥工具（如P操作、V操作，我们会在互斥一节介绍），避免同时读写的情况。

共享存储分为两种存储方式，一种基于数据结构的共享，一种基于存储区的共享，具体如下图：

另外，操作系统只提供进行共享存储的存储空间和同步互斥工具，而数据交换是由用户自己安排读/写指令完成的。

还有，进程空间一般是独立的，进程运行期间一般不能访问其他进程的空间，想让两个进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。

1.7.2 消息传递

在消息传递系统中，进程间的数据以格式化的消息为单位，进程通过操作系统提供的发送消息和接收消息两个原语进行数据交换。

消息传递有两种方式，一种是直接通信。发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。

第二种是间接通信方式，发送进程将消息发送到某个中间实体，接收进程从中间实体取得消息。这种中间实体一般称为信箱。该通信方式广泛应用于计算机网络中。

1.7.3 管道通信

管道是一个特殊的共享文件，又称pipe文件，数据在管道中是先进先出的。（管道其实就是一个循环队列）

使用管道通信，只要管道不满，写进程就能向管道的一端写入数据；只要管道非空，读进程就能从管道的一端读出数据。

为了协调双方的通信，管道机制必须提供三方面的协调能力：

互斥：指当一个进程对管道进行读/写操作时，其他进程必须等待。
同步：管道写满以后，写进程会被阻塞，直到读进程读取数据以后才能将其唤醒；同理，管道读空，读进程会被阻塞，直到写进程写入数据以后才能读取。
双方要确定彼此的存在。

1.7.4 进程小结

注意，不论是哪一种进程通信方式，数据在被读进程读取以后，都会从中转空间里消失，不会被保留。

1.8 线程和多线程模型

1.8.1 线程的基本概念

引入进程的目的是更好地使用多道程序并发执行，提高资源利用率和系统吞吐量；而引入线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

线程最直接的理解就是轻量级进程，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。

线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。

引入线程以后，进程只作为除CPU之外的系统资源的分配单元。例如，打印架等外接设备，都是按照进程分配使用的。

1.8.2 线程与进程的比较

1.8.3 线程的属性

1.8.4 线程的状态与转换

与进程一样，线程之间也存在着状态转换，而在考研中，通常比较关心就绪态、运行态和阻塞态三态之间的转换。

运行态 -> 就绪态：线程被分配的时间用完了，就会下处理机进入就绪态。

就绪态 -> 运行态：一个就绪态的线程如果被处理机选中，就会从就绪态进入运行态开始运行。

运行态 -> 阻塞态：如果一个运行态的线程发出了请求，等待某事件完成，就会从运行态进入阻塞态。

阻塞态 -> 就绪态：当等待的事件发生以后，就会从阻塞态回到就绪态。

1.8.5 线程的组织与控制

同进程的控制管理一样，线程也有自己的控制管理块——TCB。TCB块里包含的内容在上图显示，这部分的东西和进程PCB的内容大相径庭，所以我就不多说，有问题可以看看往上翻看看进程的相关知识，也可以看看这个视频，不多，就6分钟：线程的状态转换和组织控制

1.8.6 线程的实现方式

线程的实现可以分为两类：用户级线程（ULT）和内核级线程（KLT）。内核级线程又称为内核支持的线程。

1.8.6.1 用户级线程

早期的操作系统只支持进程，不支持线程。当时的“线程”是由线程库实现的。所以用户级线程其实就是在应用程序里，使用线程库，将进程设计成多线程程序。如下图：

用户级线程的相关操作（创建、管理等）都是在用户态完成，无需操作系统干预，在这种模式下，线程只能从用户视角观察到，而内核意识不到线程的存在，所以系统的调度仍然以进程为单位。

1.8.6.2 内核级线程

随着技术发展，越来越多的操作系统开始支持线程的开发。而在内核下执行的线程，就是内核级线程。内核级线程内容如下：

内核级线程在内核的支持下运行，线程管理的所有工作也是在内核空间内实现的。操作系统为每个内核级线程设置一个线程控制块TCB，内核根据该控制块感知某线程的存在。

在内核级线程中，线程可以从操作系统观察到，所以系统的调度以线程为单位。

1.8.7 多线程模型

用户级线程和内核级线程各有各的优缺点，所以为了综合两种模式，有的系统可以同时支持用户级线程和内核级线程，进而产生了三种不同的多线程模型——一对一模型、多对一模型、多对多模型。

1.8.7.1 一对一模型

1.8.7.2 多对一模型

1.8.7.3 多对多模型

2. CPU调度

2.1 调度的基本概念

2.2 调度的层次

一个作业从提交开始直到完成，往往要经历三级调度：高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）。

2.2.1 高级调度（作业调度）

2.2.2 中级调度（内存调度）

2.2.3 低级调度（进程调度）

2.2.4 三级调度的联系与对比

2.2.5 小结

2.2.6 补充——进程的挂起态与七状态模型

在进程一块有介绍过进行的五状态模型，但是通过这一节对调度层次的学习，我们可以将五状态模型拓展到七状态模型，即加上就绪挂起态和阻塞挂起态。

一个处于就绪态的进程，如果此时系统负载比较高，内存空间不够用，那系统就会将就绪态的进程调到外存里，此时处于就绪态的进程就是就绪挂起态。直到内存空间有空闲或进程需要被执行，这时处于就绪挂起态的进程才会被激活，相应的数据也会被移入内存中，这样处于就绪挂起的进程就回到了就绪态。

同理，处于阻塞态的进程也会因为负责问题进入阻塞挂起态，同样被激活以后回到阻塞态。但注意，有的系统处于阻塞挂起态的进程，等待的事件触发后，会进入就绪挂起态，之后被调入内存时，直接进入就绪态。

此外，处于运行态的进程，在下处理机时，有可能会直接进入就绪挂起态。而进程在创建态完成以后，也可能会直接进入就绪挂起态。

上图就是我们所说的七状态模型。

2.3 调度的实现

2.3.1 调度的时机

进程的调度与切换时间如上图所述，大部分的知识，我们都可以理解，但在不能进行进程调度与切换的部分，第二种情况稍微难理解一点，所我们详细说一下。

首先说一下临界资源的概念，临界资源就是一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。而临界区，就是访问临界资源的那段代码。

而操作系统内核程序临界区，就是访问某种内核数据结构，比如进程的就绪队列（这里不解释，我们应该也知道，内核的东西多牵扯到硬件电路，一般都会禁止进程切换与中断实行）。在1.6进程的控制部分，我们说过，就绪队列里的进程指令段在执行时，是不能被打断的，否则会导致操作系统中的某些关键数据结构信息不统一，会影响操作系统的管理。

所以，在进程访问就绪队列前，会先将就绪队列上锁，只有等待进程访问结束以后，才会将就绪队列解锁。如果未解锁就进行了进程调度，那其他的进程也需要访问就绪队列，此时就绪队列上锁，导致其他进程也访问失败，这就会使调度无法进行。而内核程序临界区的临界资源不尽快释放会影响到OS的其它管理工作。所以在访问内核程序临界区期间不能进行调度与切换。

但是，如果访问的是普通临界区能不能进行调度与切换呢？如我们上图中12年的考题，进程处于临界区不能进行调度与切换是错误的。原因在于，访问普通临界区时是可以进行调度与切换的。

例如，打印机也是一种临界资源，在使用进程访问时，进程一直处于临界区内，临界资源上锁。但打印机是慢速设备，这个时候不进行调度的话，会导致CPU一直处于空闲状态，所以需要通过进程调度使CPU忙起来，由此可以看出，在访问普通临界资源时，要尽可能的使用调度与切换。

2.3.2 调度的方式

有的系统，只允许进程主动放弃处理机；而有的系统，进程可以主动放弃处理机，当有更紧急的任务要处理时，也会强行剥夺处理机。基于这两种进程放弃的方式，衍生出了两种进程调度的方式，如下：

2.3.3 进程切换的过程

2.3.4 调度程序（调度器）

用于调度和分派CPU的组件称为调度程序。

调度程序主要负责执行让谁运行，运行多长时间的功能。

一般在创建新进程、进程退出、运行进程阻塞、I/O中断发生这四个情况下会触发”调度程序。”

注意，在不支持内核级线程的操作系统里，调度的单位是进程。但是在支持内核级线程的操作系统里，调度程序的处理对象是内核线程，而非进程。

2.3.5 闲逛进程

在没有其他就绪进程时，系统会让闲逛进程上CPU运行，所以CPU每时每刻都是处于运行中的。

2.4 调度算法

2.4.1 调度算法的评价指标（调度的目标）

2.4.1.1 CPU利用率

2.4.1.2 系统吞吐量

2.4.1.3 周转时间及带权周转时间

周转时间这里对思考部分介绍说一下，如果两个作业周转时间相同，但是其中一个运行时间短，一个运行时间长，会给用户带来不同的感受。比如两个程序的周转时间都是11分钟，而其中一个程序只需运行1分钟，但需要等待10分钟，这对用户来说肯定是不乐意的；相反另一个程序运行需要10分钟，等待只要1分钟，这种情况下用户还是比较乐意的。所以，调度算法的实施，其实就是对等待时间的调度。

2.4.1.4 等待时间

这里注意一点，等待时间是等进程建立后等待被服务的时间之和，但是等待I/O完成的期间是被I/O服务的，所以等待I/O完成的时间不能算作等待被服务的时间。

2.4.1.5 响应时间

响应时间：指从用户提交请求到系统首次产生响应所用的时间。

从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。

2.4.1.6 调度目标的小结

2.4.2 调度的算法

2.4.2.1 先来先服务（FCFS）

先来先服务算法就是按照作业/进程到达的先后顺序进行服务，先来的进程先服务，后到的进程要等待前一个进程的结束，才可以被服务。

以下是FCFS的相关知识点：

接下里我们举个例子来演示一下FCFS的调度实现过程：

如上图，是有关FCFS的调度实现及相关指标的求解，从求解的数据可以看到，P3的带权周转时间很大，这意味着P3有大部分时间都处在等待之中，所以我们可以验证出前一张有关FCFS基础知识的图里，对其缺点的描述，对短作业的运行是非常不利的。但是这种执行算法非常简单，且每个作业/进程都会执行到，所以它不存在饥饿问题。

这里还有一点要注意，就是等待时间的求解，这里使用周转时间-运行时间，对于这题是可以这么写的，但这个公式并不是一成不变的，对于有I/O操作的进程，因为I/O操作过程也是在服务进程，所以还要减去I/O操作的时间。这时，等待时间=周转时间-运行时间-I/O操作时间。

2.4.2.2 短作业优先（SJF）

短作业优先算法：最短的作业/进程优先得到服务。

在短作业优先算法里，一般是非抢占式的算法（考研一般默认非抢占），但也有抢占的版本，接下来以实例的方式分别介绍两个版本。

首先，非抢占式：

如上图，是非抢占式的短作业优先算法，可以看到，相比于FCFS来说，SJF算法的各项指标都降低了许多，这对用户来说，体验效果好了许多。

接下来看一下抢占式算法：

抢占式短作业优先算法的过程如上，通过对各项指标的计算，我们可以发现，对比非抢占式的短作业优先算法来说，抢占式的指标更低。

通过以上对抢占式和非抢占式的探究，可以发现一点，不论是哪一种，如果有源源不断的短进程进来，那长进程就永远不会处理，这就导致长进程会出现饥饿甚至饿死的情况。

另外，基于这两种情况，为了应对考试，需要对短作业优先算法做一个如下细节补充：

2.4.2.3 高响应比优先调度算法

首先，我们对之前说的FCFS和SJF算法进行一个思考。

FCFS算法是在每次调度的时候，它的工作本质是选择一个等待时间最长的作业（进程）为其服务（这里可会有人不懂为什么是选择等待时间最长的作业，因为作业分先来后来，而先来的作业已经处于等待，后来的作业此时可能还未创建，即使创建了，他由于来的时间比较晚，相较于先来的作用，他的等待时间也没有前面的长，这里的等待时间是从作业开始被创建计算的）。但是没有考虑到作用的运行时间，导致了对短作业不友好的问题。

SIF算是选择一个执行时间最短的作业为其服务。但是又不完全考虑各个作用的等待时间，因此导致了对长作业不友好的问题。

为此，有人设计了一个综合两种算法的全新调度算法——高响比优先算法。

高响应比优先算法在每次调度时先计算各个作业的响应比，选择响应比最高的作业/进程为其服务。

高响应比优先算法没有抢占式的算法，因此只有当前运行的作用/进程主动放弃处理机时，才需要调度，才需要计算响应比。

接下来，仍以一个例子加深理解：

2.4.2.4 对FCFS/SJF/高响应比优先的小结

这三种调度算法主要关心对用户的公平性、平均周转、评价等待时间等评价系统整体性能的指标，忽略了响应时间，也不区分紧急程度，交互性很糟，因此这三种算法一般适合用于早期的批处理系统。接下来，我们要介绍适合用于交互式系统的调度算法。

2.4.2.5 时间片轮转调度算法（RR）

时间片轮转调度算法就是按照各进程到就绪队列的顺序，让各个进程执行一个时间片，若进程未在一个时间片内执行结束，则剥夺执行，将进程重新放到就绪队列队尾重新排队。

这里仍然举例演示，但是我们取两个时间片大小来演示，在演示过程中可以思考一下，时间片大小有什么影响。

时间片为2时：

时间片为5时：

通过两种演示，我们可以比较一下，得出下图的结论：

一般来说，设计时间片时，要让切换进程的开销占比不超过1%。

2.4.2.6 优先级调度算法

优先级调度算法就是在调度时，选择优先级最高的作业/进程。

同样，以例子演示过程，再从例子里进行总结归纳。

优先级调度算法知识补充：

2.4.2.7 多级反馈队列算法

从前面的学习可以知道：

FCFS算法的优点是公平。

SJF算法的优点是能尽快处理完短作业。

时间片轮转调度算法可以让各个进程得到及时响应。

优先级调度算法可以灵活地调整各种进程被服务的机会。

这里，我们对各个算法进行折中权衡，可以综合出一个新的集合各种算法优点的全新算法——多级反馈队列调度算法。

多级反馈队列的算法规则如上图，如果没有理解的话可以参考下面的示例，不过这个算法我更推荐看下视频动态过程，我把讲解链接贴出来（大概30~35分钟）：调度算法。

2.4.2.8 交互式调度总结

这里对几种适合交互式的调度算法进行一下总结。

2.4.2.9 多级队列调度算法

多级队列调度就是系统根据进程类型设置队列，一个队列里的进程全是同一类型的。队列之间会采取调度算法，队列内部也会采取调度算法。

队列间的调度算法可以采用固定优先级或时间片划分。但是固定优先级会出现高优先级的队列一直有进程，导致低优先级的队列无法执行。

队列里面可以采用不同的调度策略，如RR、FCFS等。

3. 同步与互斥

3.1 同步与互斥的基本概念

3.1.1 同步的基本概念

3.1.2 互斥的基本概念

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可将临界资源的访问过程分成4个部分，如下图：

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）。
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

下面小结一下：

3.2 进程互斥的软件实现方法

首先设想一下，如果没有互斥会怎么样，假设A、B两人打印报告，A的申请打印进程先上打印机运行，B的申请在等待中。如果A的进程未结束，但因时间片到了，会切换B进程，而没有互斥的存在，打印机会开始打印B的报告，待B的进程时间片到了以后，又会切换回A。这样会导致两人的报告混合在一起，这显然不是我们想要的。所以，就需要设置互斥，只允许一个进程占用打印机，若未完成任务，即使时间片到了，另一个进程也无法访问临界资源。

进程互斥软件实现思想：要在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

进程互斥软件实现的方法有四种：单标志法、双标志先检查法、双标志后检查法、Peterson算法。

3.2.1 单标志法

单标志法设置了一个公用整型变量turn用来指示允许进入临界区的进程编号。如上图，turn初始化为0，此时若P1先上处理机运行，则会一直卡在while循环处，直到P1时间片用完，发生调度，此时P0上进程，不满足while循环条件，可以跳过while卡死循环，从而访问临界区资源。当P0时间片到了，即使切换为P1，因为P0未执行完，此时P1还会卡在while循环处，无法进入临界区。当P0的访问完临界区，会把turn设置为1，此时P1就可以上临界区了。

这个算法可以实现各个进程对临界区的互斥访问，但也存在一个致命的问题，就是每个进程只能轮流进入临界区。如果在进程的最后，表示了谦让的动作，即让对方访问临界区，但是对方没有访问临界区的话，下次即使自己想使用临界区资源，也无法使用。因此，单标志法存在的主要问题是，违背了“空闲让进”原则。

3.2.2 双标志先检查法

双标志检查法设置了布尔型数组，用来表示各个进程想进入临界区的意愿。如上图，设置了一个flag[2]数组来分别表示P0，P1想进入临界区的意愿。在每个进程想访问临界区资源前，先检查一下别的进程想不想访问，如果别的进程想访问，自己就先等待。

但是这样设计的算法也存在问题，如上图，在并发环境的运行下，若P0先执行1，发现flag[1]是false，于是P0就会进入下一步，但是在进入下一步前，受调度影响，切换到P1进程，P1执行5，发现flag[0]是false，于是P1也会进入下一步，此时切换到P0，P0将flag[0]改为true，再次切换到P1，P1将flag[1]也改为true，此时我们会发现，flag[0]=flag[1]=1，两边在接下来的调度中都会进入临界区，访问临界区资源。

所以，双标志先检查法存在的主要问题是，违反“忙则等待”的原则。原因是由于检查和上锁不是一气呵成的（即检查对面意愿和表达自己意愿不是一步到位的）。

3.2.3 双标志后检查法

双标志后检查法是双标志先检查法的改变，这里先进行自己的意愿表达，然后才去检查别人的意愿。如上图，一个进程若想访问临界资源，会先将自己的意愿数组改为1，然后才去检查别的进程是否想访问临界资源。

在这算法之后，可以解决忙则等待的问题，但也产生了别的问题。假设一下，在并行的环境中，P0先执行1，然后P1执行5，紧接着切换到P0执行2时发现P1是true，此时P0卡在while循环等待P1。而切换到P1时，P1也发现P0是true，此时P1也卡在while循环等待P0。出现了每一个进程都进不了临界区的情况，所以，双标志后检查法违背了空闲让进和有限等待的原则。

3.2.4 Peterson算法

由于上面三种算法都有自己的问题，但也有自己优点，所以结合三种算法设计出了Peterson算法。Peterson算法结合双标志法和单标志法，设计了意愿变量和谦让变量。在每个进程开始前，先表达自己想要进入临界区的意愿，然后再表示如果别的进程也想访问临界资源，则自己谦让给别的进程。在这种算法下，最后一个谦让的进程会进入等待状态，先执行谦让的进程会进入临界区。

这种算法不论进程如何调度切换，都遵循了空闲让进、忙则等待、有限等待三个原则。但仍没有遵循让权等待的原则。

3.2.5 进程互斥的软件实现方法小结

3.3 进程互斥的硬件实现方法

进程互斥硬件实现方法有三种，分别是中断屏蔽方法、TestAndSet（TS指令/TSL指令）指令和Swap指令（XCHG指令）。

3.3.1 中断屏蔽指令

中断屏蔽指令和前面在1.6进程的控制里的进程的原语实现一样，采用关中断指令杜绝了进程被中断调度的情况，因此，进程一旦进入临界区除了执行结束，否则无法被中断踢出临界区。

这种方法很简单，但也存在问题，首先，这种方法并不适合用于多处理机，因为关中断指令只能在设置本机的进程无法被中断，而无法更改别的主机，当一个主机访问临界资源时，开始了关中断指令，而另一台主机没有关中断，它也可能来访问临界资源，这样就出现了同时访问临界资源的情况，违背了忙则等待的原则。

另外，关中断和开中断指令要求的权限等级很高，只适合用于操作系统内核进程，不适合用于用户进程。

3.3.2 TestAndSet（TS指令/TSL指令）

实现互斥还可以借助硬件指令——TestAndSet指令，这条指令是原子操作。其功能是读出指定标志后将该标志设置为真。指令的C语言描述的逻辑如上图，注意，虽然上图是C语言描述，但这条指令是由硬件操作的，不是软件，上面描述的只是硬件操作的过程。

根据上面的逻辑描述，可以看到设置了一共享变量lock，TestAndSet指令就是将该变量的值赋值给old变量，然后返还old变量的值。这里可能不大好理解，可以联系右边互斥逻辑一起看。可以看到，while循环里不停的判断TestAndSet指令返回的值，当某个进程要访问临界资源却发现临界资源被上锁时，lock==1，然后把lock值赋值给old，old变量的值也为1，这时候返回的值也是1，while就会陷入死循环中，直到临界资源被释放。若lock==0时，可以跳出while循环，这时候，该进程可以进入临界区，但是别忘了，进入临界区要把临界区上锁，而上锁这一步就是*lock=true，这里我们就可以发现不论当前lock值是多少，都要把lock值赋true的原因，如果原来lock值为true，再赋值为true并没有影响，但是若lock=0，先把lock给old，然后赋值为true，就是先判断出临界区没有处于忙状态，自己可以访问，所以对临界区上锁，表明自己要进入临界区。这里可以自己体会一下逻辑。

3.3.3 Swap指令

Swap指令看上去和TestAndSet指令不一样，实际上两者算法设计思路都是一样的，Swap指令先在一开始给old赋值为true，这一步是为了保证临界区是空闲时，自己要去访问时，要先给临界区上锁。然后通过不断交换lock与old的值，判断lock什么时候变为false，若lock是fasle，则可以跳出循环，进入临界区。在访问完以后，再进行解锁操作。稍加理解一下可以发现和TestAndSet指令是一样的。

但这里也要注意一下，Swap指令和TestAndSet一样，也是用硬件实现的，执行过程是不可打断的，上面描述的是硬件执行的逻辑结构。

3.3.4 进程互斥的硬件实现方法小结

这里补充一点，TestAndSet指令和Swap指令实现互斥的方法都违反了让权等待的原则。

3.4 互斥锁

锁是用于实现互斥的一种方法，可以简单理解为锁就是一个bool型变量，只有0或1（false或true）分别表示当前已上锁或没有上锁。上锁与释放锁可以通过acquire()和release()函数来实现。

用锁实现互斥的缺点就是忙等，如果进不了临界区就会不断while循环，这就会导致CPU资源浪费，违反了让权等待的原则。由于忙等过程中需要不断循环检查，因此这类锁也称为自旋锁。

特别注意一下，进程忙等，并不意味着该进程就会一直占用CPU，当进程时间片到了以后，进程依然会下CPU。

另外，忙等这种特性也有优点，在等待期间时不用切换进程上下文的（毕竟切换上下文的代价也很大），如果在多处理器系统中，若临界区上锁时间很短，则自旋等待代价很低。

举个例子，在一个4核系统里，某进程陷入自旋等待要独占一个核的运算资源，但其余的核可以接着运行，此时，若另一个核很快速的运行完占用临界资源的进程，临界资源就会被释放，此时这个在自旋等待中的进程就可以快速进入临界区。这也是忙等在多核系统里的优越性。

但是注意，如果是在单核系统里，若临界资源被上锁，此时该进程时间片到了，但临界资源没有访问完，待他下了处理机后，又上了一个进程，这时候临界资源被锁，该进程进入自旋状态，在这个进程等待的过程中，临界资源是不可能被释放的，所以该进程必须等待时间片到了以后，切换回上一个访问临界资源的进程。所以，这种忙等的性能，并不适合单处理机系统。

3.5 信号量

3.5.1 信号量基本概念

在之前所学的所有进程互斥方案里，都无法实现让权等待的原则，为了解决这个问题，于是又提出了信号量的概念。

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语wait()和signal()访问，也可简写为P()和V()，或者简称P操作和V操作。

这里wait()和signal()是原语指令，是一气呵成的，无法被中断的。

信号量分为整形信号量和记录型信号量。

3.5.2 整形信号量

所谓整形信号量，就是用一个整形的变量作为信号量，用来表示系统中某种资源的数量。与普通整形变量相比，整形信号量只能进行三种操作，即初始化、P操作、V操作。

可以通过P(S)和V(S)（即wait(S)和signal(S)，这两个太长，我就简写为P、V），来对一个进程进行操作。一个进程使用P指令申请临界资源；若申请成功，则可访问临界资源；访问完资源以后，通过V指令，释放资源。

在上图左，展示了使用整型信号量定义的P、V操作执行过程的C语言表示。

以一个例子讲解一下进程基于整形信号量工作的过程：假设某计算机系统中有一台打印机，就可以初始化一个整形信号量S=1，S表示当前系统中可用的打印机资源，1说明有一个资源可用，一般情况下，系统中有几个资源，初始值就等于几，例如有两台打印机，则S=2。此时进程P0访问临界资源，先调佣P指令，令S-1，得S=0，然后P访问临界资源，此时若进程P1也想访问临界资源，也会调用P指令，此时调用P指令，因为S=0，进而进程P1会被卡在P指令里的while循环处，所以P1无法进入临界区。当P0访问完临界区以后，会将临界资源释放，即S+1，此时S=1，P1可跳出P循环，进而访问临界资源。

从这里可以看出，使用整型信号量仍没有满足让权等待的原则，所以人们对整型信号量进一步修改，得到了下面的记录型信号量。

3.5.3 记录型信号量

记录型信号量在整型信号量的基础上，添加了等待队列。如上图的记录型信号量的结构描述，仍然定义一个value用来表示资源剩余数，但在此基础上添加了一个等待队列用来表示还有几个进程要访问资源。

基于结构型信号量的定义，可以设计上面的P(S)和V(S)，当某进程要访问临界资源时，就让value值减一，表示该临界资源若被本进程占用，则临界资源还有多少剩余的数量，进而对value值判断，若此时value值小于0，说明无资源可被本进程占用，要让本进程堵塞并排进等待队列。当进程释放资源时，先让value加1，表示有一个进程被释放，然后根据value值判断此时等待进程在等待队列里，若有则从等待队列里，唤醒一个进程访问临界资源。

结合上面对P指令和V指令的描述，下面举一个记录型信号量应用的例子：

如上图，假设有两台打印机，则value=2，表示资源剩余数量为2。现在有四个进程要访问打印机，P0先使用P指令访问一台打印机，此时value变为1，P1也要访问打印机，value变为0。此时P2突然也想访问打印机，value变成-1，满足P里判断条件，要让P2堵塞，并进入等待队列，同理P3想访问打印机，也要被堵塞。

当P0访问完以后，要释放临界资源，同时根据value，判断队列里还有两个进程要访问资源，便会唤醒队头进程，因为P2比P3先进入队列，所以P2被唤醒，可以访问打印机。当P1访问完以后，也可以唤醒P3进程访问打印机。

这里不难看出，被唤醒的进程不需要从头运行P指令，而是会直接进入临界资源进行访问。

3.5.4 信号量小结

(1) 记录型信号量小结

(2) 信号量知识点框架小结

3.6 用信号量实现进程互斥、同步、前驱

3.6.1 用信号量机制实现进程互斥

互斥的这部分在3.5的记录型信号量里已经介绍的很详细，这部分提出几个重点说一下。

要注意，对不同的临界资源要设置不同的互斥信号量，如上图，对打印机设置mutex1信号量，而对摄像头则设置mutex2信号量。而不能把打印机资源和摄像头资源都定义为mutex1信号量。

在考试时，如果题目没有特别说明，可以简写semaphore mutex=1来表示记录型信号量初始化，而不需要把记录型信号量的结构再C描述一遍。

3.6.2 用信号量机制实现进程同步

可以先回3.1.1里看一下同步的概念，知道了同步的概念以后，就知道，所谓用信号量机制实现同步就是通过P/V指令来控制程序代码执行的先后顺序。如上图，是控制代码2在代码4之前执行的例子，通过初始化S=0，来阻塞P2进程，进而让P1进行先执行，当代码2执行完以后，使用V释放资源，此时P2进程才可以执行，开始运行代码4，更详细的描述可以参考上图右。

在这里，可以将信号量实现进程同步总结为四字——前V后P。解释一下就是在前操作后执行V(S)，在后操作前执行P(S)。可以结合下面的用信号量机制实现进程前驱理解。

3.6.3 用信号量机制实现进程前驱

用信号量机制实现进程前驱其实就是用信号量机制实现多个进程的同步，这里我们牢记前V后P四字口诀可轻松解题。如上图，进程P1有代码S1，P2有代码S2，根据图例可以看出，S1是S2的前驱，即S1先执行，执行完以后才可以执行S2，根据口诀，只需要在S1后加V(a)，S2前加P(a)，就可以轻松设计出P1进程和P2进程的同步。具体设计结果如上图，可以根据这个思路自己先把右图推一编，再与左边的结果对一下。

3.6.4 小结

计算机操作系统（二）——进程与线程——用信号量机制实现同步、互斥、前驱小结.png

3.7 生产者与消费者问题

写在开头：3.7~3.11是经典的PV操作问题，这部分重点靠练题，所以我只记了题目和代码实现，最多记一些易错和重点。题目的具体分析以及如何做可以看书或跳转视频听讲解。老实说，这部分题做多了自然就会了，听得再多，不做，遇到也不会。

视频链接：生产者-消费者问题

问题描述：

问题分析：

问题实现：

下面思考一个问题，上面都是先对同步信号量执行P操作，再对互斥信号量执行P操作，能不能颠倒，先对互斥信号量执行P操作，再对同步信号量执行P操作呢？

从上图的分析可以发现，不可以颠换同步信号量与互斥信号量的P操作，也就是说实现互斥的P操作一定要在实现同步的P操作之后。

现在再思考一下，可不可以把生产一个产品和使用产品的操作放在临界区的P、V操作之间呢？逻辑上看是可以放到里面的，但是如果放到P、V操作之间，会导致临界区代码很长，也就是说一个进程对临界区上锁的时间会很长，这样就不利于各个进程交替使用临界区，所以要让临界区资源尽可能的短。所以，逻辑上把这两个操作放进去没有问题，但实际上会对系统效能产生影响，因而并不建议把这两个操作放到P、V操作里。

下面对生产者-消费者问题进行回顾：

3.8 多生产者-多消费者问题

问题描述：

问题分析：

问题实现：

上图对该问题进行了解答，现在考虑一下，可不可以不用互斥信号量呢？

结论是可以的，如下图：

这里可以不设置互斥信号量的原因在于，本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。

但是，如果缓冲区改为2，就需要设置互斥信号量，原因如下图：

计算机操作系统（二）——进程与线程——多生产者与多消费者问题实现改进缓冲区设置.png

经过对缓冲区的讨论，可以得到以下结论：

下面，对多生产者-多消费者问题进行总结：

3.9 吸烟者问题

问题描述：

问题分析：

信号量设置：

问题实现：

吸烟者问题总结：

3.10 读者写者问题

问题描述：

问题分析：

问题实现：

注意，这里mutex变量是用来保证各读进程之间的互斥访问，如果没有P(mutex)，在并发条件下，可能会出现两个进程同时进行count判断从而进入P(rw)，第一个进入的可以顺利执行，第二个会被阻塞。出现这种情况的原因是由于对count变量的检查和赋值操作不是一气呵成的，所以设置mutex来实现读进程的互斥，保证了检查和赋值的操作可以一气完成。

注意，上面的实现还有问题，当利用count变量来记录当前有几个读进程在访问文件时，可以看到，文件被第一个读进程加锁，被最后一个读进程解锁。不难发现，当第一个读进程执行时，如果执行了写进程，则写进程会被堵塞，此时如果再执行读进程，读进程会使count数量增加，此时上一个读进程运行完，不会执行先来的写进程，而是会执行再写进程后的读进程。所以，这种实现方式暗含着读进程优先。

下面对此实现进行修改，提高了写进程的权值，暗含写优先思想，即当在执行一个读进程时，如果写进程先来，可以先执行，而不是在比其来的晚的读进程后执行。

下面对读写者问题进行总结：

3.11 哲学家进餐问题

问题描述：

问题分析：

经过分析，我们可以先写出上图的程序，即让一个哲学家想吃饭就拿起自己左右两个筷子，吃完再放下。但不难发现，这样执行存在一个问题，如果5个哲学家并发拿起了自己左手边的筷子，则每一个哲学家都会堵塞在拿右边筷子处，这就产生了死锁现象。

如何避免这种现象？下面提供了几种方法：

除了上图提供的两种方法，还可以有下面这种方法，即仅当一个哲学家的左右两支筷子都可用时才允许他抓起筷子。对于这种方法的代码实现如下图：

如上图，这段代码虽然说是仅当一个哲学家的左右两支筷子都可用时才允许他抓起筷子，但实际并非如此。根据程序可以看出，0号哲学家先拿起筷子吃饭，此时1号哲学家若想吃饭，发现左边筷子被占，则会堵塞在拿左的程序处，此时若2号哲学家想吃饭，虽然2号哲学家两侧筷子都可拿，但因为1号哲学家堵塞在拿左处，他已经使用P(mutex)上锁，所以此时2号也无法拿筷子。再重新看，如果0号哲学家拿起筷子吃饭，此时4号哲学家想吃饭，他会拿起左边筷子，被堵塞在拿右边筷子处，直到0号吃完，放回筷子0，4号哲学家才会拿起右边筷子吃饭。

经过上面的描述，不难发现，用仅当一个哲学家的左右两支筷子都可用时才允许他抓起筷子来描述并不准确，因为这种方法并不能保证只有两边的筷子都可用时才允许哲学家拿起筷子。

对于上述程序更准确的描述应该是，各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放在筷子后，被阻塞的哲学家就可以获得等待的筷子了。

下面对哲学家问题进行总结：

3.12 管程

在信号量机制中，每个要访问的临界资源的进程必须自备同步的PV操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当导致系统死锁。于是，便产生了一种新的进程同步工具——管程。

管程的定义和基本特征如下：

利用共享数据结构抽象地表示系统中的共享资源，而将对该数据结构实施的操作定义为一组过程。

这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程。有了管程以后，程序员就不需要考虑同步PV操作，仅调用管程的过程（函数）即可。

局部于管程的数据只能被局部于管程的过程所访问，用大白话来说就是管程中定义的共享数据结构，只能被管程里的函数所修改。所以一个进程想修改管程里的数据，只能通过调用管程里的函数来实行。另外，每次仅允许一个进程在管程内调用某个函数，如果别的进程也想访问管程，就需要等待当前进程访问结束以后，才能访问。

为了加深理解，下面看一下用管程实现的生产者与消费者问题：

上图左边，封装在monitor内的就是管程函数（这里给的是用C实现的伪代码），右边是实现生产者与消费者进程的方式，仅需调用管程内的函数即可。编译器会负责实现个进程互斥地进入管程中的过程。

这里补充说一点，上图左边伪代码里，通过定义两个条件变量full与empty，用来解决同步问题。如果缓冲区产品满了，则生产者进程要被堵塞掉，仅当有消费者进程产生以后，取走了一个产品，才会通过full变量来唤醒被堵塞的生产者进程。消费者进程同理，当缓冲区为空以后，消费者进程也要被堵塞，仅当有生产者进程产生以后，生产了一个产品，才会通过empty变量来唤醒被堵塞的消费者进程。

经过用管程实现生产者与消费者问题，可以总结出管程的以下特点：

在JAVA里也有类似实现管程的机制，可以参考了解一下：

下面对管程一节进行小结：

4. 死锁

4.1 死锁的概念

死锁的定义：指多个进程因竞争资源而造成的一种僵局（互相等待对方手里的资源），使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。

死锁易与饥饿和死循环产生混淆，下面看一下死锁、饥饿与死循环的区别：

了解完死锁定义以后，下面看一下有哪些条件会导致死锁的产生：

接下来看一下，在什么情况下会满足这些条件，导致死锁的产生：

既然存在死锁问题，就要想办法处理死锁，死锁的处理策略如下：

下面对死锁的概念部分进行一个小结：

4.2 死锁的处理策略

在上面标注了死锁的三种处理策略，接下来分别对其进行介绍。

4.2.1 死锁的处理策略——预防死锁。

预防死锁就是破坏会导致死锁产生的几个必要条件，接下来分别看一下怎么破坏这些条件。

4.2.1.1 破坏互斥条件

破坏互斥条件，就是将只能互斥使用的资源改造为允许共享使用的资源，则系统就不会进入死锁状态。比如使用SPOOLing技术，如上图。

在使用SPOOLing技术以后，会有一个输出进程（类似缓冲区）用来存储每个进程的请求，比如进程1先申请使用打印机，此时进程2也发出申请，就会放到输出进程里，若有别的进程也想使用，则会依次放到输出进程的进程2的申请之后。通过这种方式，各个进程的申请被放到输出进程里依次输出，在各个进程看来，自己对打印机资源的使用请求是立即被接受处理的，不需要阻塞，但实际上会通过输出进程的安排来依次使用打印机。

该策略也存在缺点，如上图下。

4.2.1.2 破坏不可剥夺条件

4.2.1.3 破坏请求和保持条件

使用静态分配方法破坏请求和保持条件，需要在进程运行前一次申请完它所需要的全部资源，若有的资源已被占用，要释放掉当前已申请的资源。如果进程一直申请不到全部的资源，则会导致进程饥饿。

此外，进程一旦申请资源成功，就会一直保持所有资源，这其中的一些资源，可能仅需使用很短的时间，但是会一直被占用，这样资源利用率就会很低，造成很严重的资源浪费。

4.2.1.4 破坏循环等待条件

采用顺序资源分配法，会对系统中的资源进行编号，每个进程必须按编号递增的顺序请求资源，而大编号的资源进程不可能逆向地回来申请小编号的资源，这也就不会产生循环等待的现象。

但这种策略也有缺点，如果进程想先使用一个大编号的资源再使用一个小编号的资源，就必须先占用小编号资源，否则系统使用大编号资源以后，无法再回来申请小编号资源，这就导致资源浪费。

另外，通过这种策略，如果要添加新的设备，可能会导致重新分配编号。因为必须按规定次序申请资源，用户编程需要考虑的逻辑等东西也会很多，用户编程变得很麻烦。

下面对预防死锁进行总结：

4.2.2 死锁的处理策略——避免死锁

避免死锁同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在每次分配资源的过程中，都要分析此次分配是否会带来死锁风险，只有在不产生死锁的情况下，系统才会为其分配资源。实现避免死锁最经典的方法便是银行家算法。

首先，用一个例子来了解一下什么是安全序列。

在上面这个借钱例子里，有一个限制条件，如果借给企业的钱总数达不到企业提出的最大要求，那么不管之前借给企业多少钱，这些钱最终都拿不回来。

如果，BAT的最大需求是70亿，40亿，50亿，但是一开始BAT三个企业分别借走20亿，10亿，30亿，此时银行家手里只剩40亿。如果这时B又想借30亿，那么银行家借出去的话，就只剩10亿，此时无论再借给BAT中的谁，都无法达到企业最大需求，也就意味着银行家的钱都拿不回来了。可以说，再借给B30亿是不安全的操作。

如果，银行家还剩40亿，但是A向银行家借20亿，银行家就会剩20亿，此时这20亿不论借给A还是T都可以收回，然后把收回的钱再借给B，就可以把所有的钱都收回，即通过T->B->A或A->T->B的序列可以安全收回所有的钱。所以，银行家再借20亿给A是安全的操作。而T->B->A或A->T->B就是安全序列。

由此，可以引出下面对安全序列的定义：

在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这也是银行家算法的核心思想。

下面看一下如何把银行家算法应用到操作系统上。

在BAT例子里，只有一种类型的资源——钱，但是在计算机系统中会有多种多样的资源，可以把单维的数字拓展为多维的向量，实现银行家算法在操作系统中的应用。具体如上图下的例子，把3种资源的剩余数量当成一个3维向量，根据其剩余数量进行银行家算法分配。此时可以思考一下，这个系统是否处于安全状态，也就是说能不能找到一个安全序列完成各个进程的运行。

我们可以通过从需求资源较小的进程开始每一轮检查，分析过程如下图：