处理机调度

调度概念

调度的基本概念

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题。

调度的层次

一个作业从提交开始直到完成，往往要经历以下三级调度：

作业调度。又称高级调度，其主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程（建立PCB），以使它（们）获得竞争处理机的权利。简言之，作业调度就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。作业调度的执行频率较低，通常为几分钟一次。

高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的 PCB，作业调出时才撤销 PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。
中级调度。又称内存调度，其作用是提高内存利用率和系统吞吐量。为此，应将那些暂时不能运行的进程调至外存等待（虚拟内存），把此时的进程状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程，再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。

暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

暂时调到外存等待的进程状态为挂起状态（挂起态，suspend），挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。五状态模型 → 七状态模型
进程调度。又称低级调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

	要做什么	调度发生在	发生频率	对进程状态的影响
高级调度（作业调度）	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存 → 内存（面向作业）	最低	无 → 创建态 → 就绪态
中级调度（内存调度）	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存 → 内存（面向进程）	中等	挂起态 → 就绪态（阻塞挂起 → 阻塞态）
低级调度（进程调度）	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存 → CPU	最高	就绪态 → 运行态

三级调度的联系

作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。

中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒。

作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
作业调度次数少，中级调度次数略多，进程调度频率最高。
进程调度是最基本的，不可或缺。

调度的时机、切换与过程

调度的时机

进程调度和切换程序是操作系统内核程序。

需要进行进程调度与切换的情况：

当前运行的进程主动放弃处理机：进程正常终止；运行过程中发生异常而终止；进程主动请求阻塞（如等待I/O）
当前运行的进程被动放弃处理机：分给进程的时间片用完；有更紧急的事需要处理（如I/O中断）；有更高优先级的进程进入就绪队列

请求调度的事件发生后，才可能运行进程调度程序，调度了新的就绪进程后，才会进行进程间的切换。理论上这三件事情应该顺序执行，但在实际设计中，操作系统内核程序运行时，若某时发生了引起进程调度的因素，则不一定能够马上进行调度与切换。

现代操作系统中，不能进行进程的调度与切换的情况有以下几种：

在处理中断的过程中。中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。
进程在操作系统内核程序临界区中。进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放。

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源

临界区：访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 PCB 组成）

如果还没退出内核程序临界区（还没解锁）就进行进程调度，但是进程调度相关的程序也需要访问就绪队列，但此时就绪队列被锁住了，因此又无法顺利进行进程调度，内核程序临界区访问的临界资源如果不尽快释放的话，极有可能
影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。

在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致 CPU 一直空闲，普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。
其他需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。

若在上述过程中发生了引起调度的条件，则不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。应该进行进程调度与切换的情况如下：

发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度。
中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度。

调度的切换与过程

进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。

对原来运行进程各种数据的保存
对新的进程各种数据的恢复

现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

“狭义的进程调度”与“进程切换"的区别：

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程调度方式

所谓进程调度方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。通常有以下两种进程调度方式:

非剥夺调度方式，又称非抢占方式。非剥夺调度方式是指当-一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程。

在非剥夺调度方式下，一旦把CPU分配给-一个进程，该进程就会保持CPU直到终止或转换到等待态。这种方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。
剥夺调度方式，又称抢占方式。剥夺调度方式是指当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。

采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处。但“剥夺”不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。

调度的基本准则

不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较处理机调度算法的性能，人们提出了很多评价准则，下面介绍其中主要的几种:

CPU 利用率。CPU 是计算机系统中最重要和昂贵的资源之一，所以应尽可能使 CPU 保持“忙”状态，使这一资源利用率最高。利用率=忙碌的时间/总时间。
系统吞吐量。表示单位时间内CPU完成作业的数量。长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量。而对于短作业，它们所需要消耗的处理机时间较短，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。系统的吞吐量=总共完成了多少道作业/总共花了多少时间。
周转时间。周转时间是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及进行输入/输出操作所花费时间的总和。
- 周转时间＝作业完成时间-作业提交时问；
- 平均周转时间＝各作业周转时间之和/作业数；
- 带权周转时间=作业周转时间/作业实际运行时间；
- 平均带权周转时间=各作业周转时间之和/作业数；
等待时间。等待时间指进程处于等处理机状态的时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
响应时间。响应时间指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。

典型的调度算法

操作系统中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。下面介绍几种常用的调度算法。

先来先服务（FCFS）调度算法

知识点	相关内容
算法思想	主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）
算法规则	按照作业/进程到达的先后顺序进行服务
用于作业/进程调度	用于作业调度时，考虑的是哪个作业先到达后备队列用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占	非抢占式的算法
优点	公平、算法实现简单
缺点	排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。FCFS算法对长作业有利，对短作业不利
是否会导致饥饿	不会

先来先服务（FCFS，First Come First Serve）调度算法是一种最简单的调度算法，它既可用于作业调度，又可用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

在进程调度中，FCFS 调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。

下面通过一个实例来说明FCFS调度算法的性能。假设系统中有 4 个作业，它们的提交时间分别是 8、8.4、8.8、9，运行时间依次是 2、1、0.5、0.2，系统采用 FCFS 调度算法，这组作业的平均等待时间、平均周转时间和平均带权周转时间见下表。

周转时间 = 完成时间 - 提交时间
带权周转时间 = 周转时间 / 运行时间
等待时间 = 周转时间 - 运行时间 ( - I/O 操作时间）如果有 I/O 操作的进程

FCFS 调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按 FCFS 原则处理。

FCFS 调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对 SJF 和高响应比）；有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。

短作业优先算法（SJF）

知识点	相关内容
算法思想	追求最少的平均等待时间、最少的平均周转时间、最少的平均平均带权周转时间
算法规则	最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）
用于作业/进程调度	即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF，Shortest Process First）算法”
是否可抢占	SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）
优点	“ 最短的”平均等待时间、平均周转时间
缺点	不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
是否会导致饥饿	会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死

最短剩余时间优先算法（SRTN）：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

注意几个小细节：

如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的。
很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少”

严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”；或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”；如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先，SRNT算法）的平均等待时间、平均周转时间最少”。
虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 FCFS），SJF 依然可以获得较少的平均等待时间、平均周转时间
如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

FCFS 算法是在每次调度的时候选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。
SJF 算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。

高响应比优先调度算法（HRRN）

知识点	相关内容
算法思想	要综合考虑作业/进程的等待时间和要求服务的时间
算法规则	在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。响应比=（等待时间 + 要求服务时间）/ 要求服务时间
用于作业/进程调度	即可用于作业调度，也可用于进程调度
是否可抢占	非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
优点	综合考虑了等待时间和运行时间（要求服务时间）等待时间相同时，要求服务时间短的优先（SJF 的优点）要求服务时间相同时，等待时间长的优先（FCFS 的优点）对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
是否会导致饥饿	不会

根据响应比公式可知：

作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业
要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。

注：以上三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的角色。

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

知识点	相关内容
算法思想	公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则	按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度	用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
是否可抢占	若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到
优点	公平；响应快，适用于分时操作系统;
缺点	由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
是否会导致饥饿	不会

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

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

优先级调度算法

知识点	相关内容
算法思想	随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则	每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
用于作业/进程调度	既可用于作业调度，也可用于进程调度。甚至，还会用于I/O调度
是否可抢占	抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
优点	用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
缺点	若源源不断地有高优先级进程到来，则可能导致饥饿
是否会导致饥饿	会

非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。

抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种：

静态优先级：创建进程时确定，之后一直不变。
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

如何合理地设置各类进程的优先级? 通常：

系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好 I/O 型进程（或称 I/O 繁忙型进程），与 I/O 型进程相对的是计算型进程（或称 CPU 繁忙型进程）

I/O 设备和 CPU 可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让 I/O 设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

如果采用的是动态优先级，什么时候应该调整? 可以从追求公平、提升资源利用率等角度考虑。

如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
如果某进程占用处理机运行了很长时间，则可适当降低其优先级
如果发现一个进程频繁地进行 I/O 操作，则可适当提升其优先级

Linux 中每个进程都有一个优先数，进程能否占用处理器的优先权取决于进程的优先数，优先数越小则优先权越高。Windows 中每一个线程在内核中有一个优先级顺序，这个顺序的取值范围是 0 ~ 31，数字越大优先级越高。

多级反馈队列调度算法（融合了前几种算法的优点）

知识点	相关内容
算法思想	对其他调度算法的折中权衡
算法规则	设置多级就绪队列，各级队列优先级从高到低，时间片从小到大新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾只有第k级队列为空时，才会为k+1级队头的进程分配时间片
用于作业/进程调度	用于进程调度
是否可抢占	抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
优点	对各类型进程相对公平（FCFS的优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（可以将因I/O而阻塞的进程重新放回原队列，这样I/O型讲程就可以保持较高优先级
是否会导致饥饿	会

进程同步、互斥

为什么要引入进程同步的概念？
不同的进程之间会存在什么关系？
当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗？

进程同步的基本概念

在多道程序环境下，进程是井发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

互斥

互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

例如，在仅有一台打印机的系统中，有两个进程A和进程B，若进程A需要打印时，系统已将打印机分配给进程B，则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞态变为就绪态。

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

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

临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所用，我们将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

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

进入区。为了进入临界区使用临界资源，在进入区要检查是否可以进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。（“上锁”）
临界区。进程中访问临界资源的那段代码，又称临界段。
退出区。将正在访问临界区的标志清除。（“解锁”）
剩余区。代码中的其余部分。

do {
    entry section;     // 进入区
    critical section;  // 临界区
    exit section;      // 退出区
    remainder section; // 剩余区
} while(true)

临界区互斥的软件实现方法

理解各个算法的思想、原理
结合上小节学习的“实现互斥的四个逻辑部分”，重点理解各算法在进入区、退出区都做了什么
分析各算法存在的缺陷（结合“实现互斥要遵循的四个原则”进行分析）

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

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

该算法设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号，即若 turn=0，则允许 P₀ 进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区（违背“空闲让进”）。这样很容易造成资源利用不充分。

若 P₀ 顺利进入临界区并从临界区离开，则此时临界区是空闲的，但 P₁ 并没有进入临界区的打算，turn=1 一直成立， P₀ 就无法再次进入临界区（一直被while死循环困住）。

1	int turn = 0; // turn表示当前允许进入临界区的进程号

// P0 进程
while(trun != 0);  // 进入区
critical section;  // 临界区
turn = 1;          // 退出区
remainder section; // 剩余区

// P1 进程
while(trun != 1);  // 进入区
critical section;  // 临界区
turn = 0;          // 退出区
remainder section; // 剩余区

双标志法先检查

算法思想：设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 flag[0] =true 意味着 0 号进程 P₀ 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。

1
2
3

bool flag[2];    // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置两个进程都不想进入临界区

// P0 进程
while(flag[1]);   // ①
flag[0] = true;   // ③
critical section;  
flag[0] = false;          
remainder section;

// P1 进程
while(flag[0]);    // ② 如果此时P0想进入临界区，P1就一直循环等待
flag[1] = true;    // ④
critical section;  
flag[1] = false;          
remainder section;

优点：不用交替进入，可连续使用

缺点： P₀ 和 P₁ 可能同时进入临界区。按序列①②③④执行时，执行时，会同时进入临界区（违背“忙则等待”）。即在检查对方的 flag 后和切换自己的 flag 前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行（不是原子性操作）。

双标志法后检查

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

1
2
3

bool flag[2];    // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置两个进程都不想进入临界区

// P0 进程
flag[0] = true; 
while(flag[1]);
critical section;  
flag[0] = false;          
remainder section;

// P1 进程
flag[1] = true;
while(flag[0]);    // 如果此时P0想进入临界区，P1就一直循环等待
critical section;  
flag[1] = false;          
remainder section;

两个进程几乎同时都想进入临界区时，它们分别将自己的标志值 flag 设置为 true，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区时，双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

Peterson’s Algorithm

算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L. Peterson 想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“谦让”，主动让对方先使用临界区。

bool flag[2];    // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置两个进程都不想进入临界区
int turn = 0;

// Pi 进程
flag[0] = true; 
turn = 1;
while(flag[1] && turn==1);
critical section;  
flag[0] = false;          
remainder section;

// Pj 进程
flag[1] = true                // 表示自己想进入临界区
turn = 0;                     // 可以优先让对方进入临界区
while(flag[0] && turn==0);    // 对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section;  
flag[1] = false;          
remainder section;

具体如下：

考虑进程 P₀ ，一旦设置 flag[0] = true，就表示它想要进入临界区，同时 turn = 1，此时若进程 P₁ ，已在临界区中，符合进程 P₀ 中的 while 循环条件，则 P₀ 不能进入临界区。
若 P₁ 不想要进入临界区，即 flag[1] = false，循环条件不符合，则 P₀ 可以顺利进入，反之亦然。

本算法的基本思想是算法一和算法三的结合。利用 flag 解决临界资源的互斥访问，而利用 turn 解决“饥饿”现象。

临界区互斥的硬件实现方法

理解本节介绍的硬件实现，对学习后面的信号量很有帮助。计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换等。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。

中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）

当一个进程正在使用处理机执行它的临界区代码时，防止其他进程进入其临界区进行访问的最简方法是，禁止一切中断发生，或称之为屏蔽中断、关中断。

因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，进而保证互斥的正确实现，然后执行开中断。其典型模式为

...
关中断;  // 关中断后即不允许当前进程被中断，也必然不会发生进程切换
临界区;
开中断;  // 直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区
...

优点：简单、高效

缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

这种方法限制了处理机交替执行程序的能力，因此执行的效率会明显降低。对内核来说，在它执行更新变量或列表的几条指令期间，关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。

TestAndSet 指令

简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令。这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的逻辑功能描述如下：

// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true表示已加锁，false 表示未加锁
bool TestAndSet (bool *lock){
    bool old;
    old = *lock;  // old用来存放 lock 原来的值
    *lock = true; // 无论之前是否已加锁，都将 lock 设为 true
    return old;   // 返回 lock 原来的值
}

// TSL 指令实现互斥的算法逻辑
while (TestAndSet (&lock)); // 上锁并检查
// 临界区代码
// ...
lock  false; // 解锁
// 剩余区代码
// ...

若刚开始 lock 是 false ，则 TSL 返回的 old 值为 false ，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行 TSL 指令，从而导致“忙等”。

Swap 指令

有的地方也叫 Exchange 指令，或简称 XCHG 指令。

Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑

// Swap 指令：该指令的功能是交换两个字（字节）的内容
Swap(bool *a, bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 使用 Swap 指令实现互斥的算法逻辑
// lock 表示当前临界区是否被加锁
bool old = true;
while (old == true){
    Swap(&lock, &old);
}
// 临界区代码
// ...
lock  false; // 解锁
// 剩余区代码
// ...

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

⭐信号量机制（高频考点）

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语 wait(S) 和 signal(S) 访问，也可记为“P操作”和“V操作”。（来自荷兰语 proberen 检测和 verhogen 释放）

原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现（关中断/开中断指令实现）。例如，前述的 Test-and-Set 和 Swap 指令就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现。

原语之所以不能被中断执行，是因为原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。若能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示，系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作

int S = 1; // 初始化整形信号量S,表示当前系统中可用的某资源数

void wait (int S) {     // wait 原语,相当于“进入区”
    while (S <= 0);    // 如果资源数不够，就一直循环等待
    S = S - 1;         // 如果资源数够，则占用一个资源
}

void signal (int S) {  // signal 原语，相当于“退出区”
    S = S + 1;         // 使用完资源后，在退出区释放资源
}

优点：“检查”和“上锁”一气呵成，避免了并发、异步导致的问题

缺点：不满足“让权等待”原则，会发生“忙等”

记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

记录型信号量是不存在“忙等”现象的进程同步机制。除需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程。记录型信号量得名于采用了记录型的数据结构。记录型信号量可描述为

/*记录型信号量*/
typedef struct {
    int value;         // 剩余资源数
    struct process *L; // 等待队列
} semaphore;

// 某进程需要使用资源时，通过wait 原语申请
void wait (semaphore S) {
    S.value--;
    if (S.value < 0){
        // 如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态
        // 并把挂到信号量S的等待队列(即阻塞队列)中
        add this process to S.L; 
        block(S.L); 
    }
}

wait 操作，S.value--表示进程请求一个该类资源，当S.value < 0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列S.L，可见该机制遵循了“让权等待”的准则。

// 进程使用完资源后，通过signal原语释放
void signal (semaphore S) {
    S.value++;
    if (S.value <= 0){
        remove a process P from S.L; 
        wakeup(P);
    }
}

signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，因此有S.value++。若加1后仍是S.value≤0，则表示在S.L中仍有等待该资源的进程被阻塞，因此还应调用 wakeup 原语，将S.L中的第一个等待进程唤醒。

信号量机制实现进程互斥

分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
设置互斥信号量 mutex ，初值为1

/*信号量机制实现互斥*/
semaphore mutex = 1;  // 初始化信号量

P1(){
    //...
    P(mutex);  // 准备开始访问临界资源，加锁
    // P1临界区代码段...
    V(mutex);  // 使用临界资源后需要解锁
    //...
}

P2(){
    //...
    P(mutex);  // 准备开始访问临界资源，加锁
    // P2临界区代码段...
    V(mutex);  // 使用临界资源后需要解锁
    //...
}

当没有进程在临界区时，任意一个进程要进入临界区，就要执行P操作，把 mutex 的值减为0，然后进入临界区；
当有进程存在于临界区时，mutex 的值为0，再有进程要进入临界区，执行P操作时将会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。

互斥是不同进程对同一信号量进行P，V操作实现的，一个进程成功对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行 V 操作，表示当前没有进程进入临界区，可以让其他进程进入。

下面简单总结一下PV操作在同步互斥中的应用：在同步问题中，若某个行为要用到某种资源，则在这个行为前面P这种资源一下；若某个行为会提供某种资源，则在这个行为后面V这种资源一下。在互斥问题中, P，V操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

注意：对不同的临界资源需要设置不同的互斥信号量。

P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

信号量机制实现进程同步

进程同步：要让各并发进程按要求有序地推进。让本来异步并发的进程互相配合，有序推进。

分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
设置同步信号量S，初始为0
在“前操作”之后执行V(S)
在“后操作”之前执行P(S)

/*信号量机制实现进程同步*/
semaphore S = 0;  // 初始化信号量

P1(){
    // ...
    x;    // 语句x
    V(S); // 告诉进程P2，语句己经完成
    // ...
}

P2(){
    //...
    P(S); // 检查语句x是否运行完成
    y;    // 检查无误，运行 语句
    // ...
}

若先执行到 V(S) 操作，则 S++ 后 S=1 。之后当执行到 P(S) 操作时，由于S=1，表示有可用资源，会执行 S-- , S的值变回0，P2进程不会执行block原语，而是继续往下执行代码；
若先执行到 P(S) 操作，由于S=0，S-- 后S=-1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码x，继而执行 V(S) 操作，S++，使S变回0，由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码y了

信号量机制实现前驱关系

信号量也可用来描述程序之间或语句之间的前驱关系。下图给出了一个前驱图，其中S1、S2、S3…S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干初始值为“ 0” 的信号量。例如，为保证S1 → S2，S1 → S3 的前驱关系，应分别设置信号量a1，a2。同样，为保证S2 → S4，S2 → S5，S3 → S6，S4 → S6，S5 → S6，应设置信号量b1，b2，c，d，e。

要为每一对前驱关系各设置一个同步变量
在“前操作”之后对相应的同步变量执行 V 操作
在“后操作”之前对相应的同步变量执行 P 操作

实现算法如下：

semaphore a1=a2=b1=b2=c=d=e=0;

P1(){
    // ...
    S1;
    V(a1);
    V(a2);
    // ...
}

P2(){
    // ...
    P(a1);
    S2;
    V(b1);
    V(b2);
    // ...
}

P3(){
    // ...
    P(a2);
    S3;
    V(e);
    // ...
}

P4(){
    // ...
    P(b1);
    S4;
    V(c);
    // ...
}

P5(){
    // ...
    P(b2);
    S5;
    V(d);
    // ...
}

P6(){
    // ...
    P(c);
    P(d);
    P(e);
    S6;
    // ...
}

分析进程同步和互斥问题的方法步骤

关系分析。找出问题中的进程数，并分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。
整理思路。找出解决问题的关键点，并根据做过的题目找出求解的思路。根据进程的操作流程确定P操作、V操作的大致顺序。
设置信号量。根据上面的两步，设置需要的信号量，确定初值，完善整理。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注: 这里的“产品”理解为某种数据）

生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（同步关系。缓冲区满时，生产者要等待消费者取走产品）
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。（同步关系。缓冲区空时，消费者要等待生产者放入产品）
缓冲区是临界资源，各进程必须互斥地访问。（互斥关系）

如何用信号量机制（P、V操作）实现生产者、消费者进程的这些功能呢？

思路：

生产者每次要消耗（P）一个空闲缓冲区，并生产（V）一个产品。
消费者每次要消耗（P）一个产品，并释放一个空闲缓冲区（V）。
往缓冲区放入/取走产品需要互斥。

semaphore mutex = 1;  // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;  // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0;   // 同步信号量，表示产品的数量，也即非空缓冲区的数量

producer(){
    while(1){
        // 生产产品...
        P(empty); // 消耗一个空闲缓冲区
        P(mutex);
        // 把产品放入缓冲区...
        V(mutex);
        V(full);  // 增加一个产品
    }
}

consumer(){
    while(1){
        P(full); // 消耗一个产品(非空缓冲区)
        P(mutex);
        // 从缓冲区取走一个产品...
        V(mutex);
        V(empty); // 增加一个空闲缓冲区
        // 使用产品...        
    }
}

实现互斥是在同一进程中进行一对 PV 操作；
实现两进程的同步关系，是在其中一个进程中执行 P，另进程中执行 V
实现互斥的 P 操作一定要在实现同步的 P 操作之后。否则可能会产生“死锁”
V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换。

多生产者多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。

多指多类，而不是多个

互斥关系：对缓冲区（盘子）的访问要互斥地进行

同步关系：

父亲将苹果放入盘子后，女儿才能取苹果
母亲将橘子放入盘子后，儿子才能取橘子
只有盘子为空时，父亲或母亲才能放入水果，“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果

semaphore mutex = 1;
semaphore apple = 0;  // 盘中中有几个苹果
semaphore orange = 0; // 盘中有几个橘子
semaphore plate = 1;  // 盘中还可以放多少个水果

dad(){
    while(1){
        // 准备苹果...
        P(plate);  // 检查盘子还可以放多少水果
        P(mutex);
        // 把苹果放入盘子...
        V(mutex);
        V(apple);  // 告诉女儿苹果数量+1
    }
}
mom(){
    while(1){
        // 准备橘子...
        P(plate);  // 检查盘子还可以放多少水果
        P(mutex);
        // 把橘子放入盘子...
        V(mutex);
        V(orange);  // 告诉儿子橘子数量+1
        
    }
}
daughter(){
    while(1){
        P(apple);  // 检查是否有苹果
        P(mutex);
        // 从盘中取出苹果...
        V(mutex);
        V(plate);  // 盘子水果数-1
        // 吃掉苹果...
    }
}
son(){
    while(1){
        P(orange);  // 检查是否有橘子
        P(mutex);
        // 从盘中取出橘子...
        V(mutex);
        V(plate);  // 盘子水果数-1
        // 吃掉橘子...
    }
}

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

总结：在生产者消费者问题中，如果缓冲区大小为 1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）

本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者——多消费者”。

桌子可以抽象为容量为 1 的缓冲区，要互斥访问。

同步关系（从事件的角度来分析）：

桌上有组合一 → 第一个抽烟者取走东西
桌上有组合二 → 第二个抽烟者取走东西
桌上有组合三 → 第三个抽烟者取走东西
发出完成信号 → 供应者将下一个组合放到桌上

semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 0;
int i = 0; // 用于实现"三个抽烟者轮流抽烟"

provider(){
    while(1){
        if(i==0){
            // offer1
            V(offer1);
        } else if(i==1){
            // offer2
             V(offer2);
        }else if(i==2){
            // offer3
             V(offer3);
        }
        i = (i+1)%3; 
        P(finish);
    }
}

smoker1(){
    while(1){
        P(offer1);
        // 拿offer1并处理...
        V(finish);
    }
}
smoker2(){
    while(1){
        P(offer2);
        // 拿offer2并处理...
        V(finish);
    }
}
smoker3(){
    while(1){
        P(offer3);
        // 拿offer3并处理...
        V(finish);
    }
}

读者写者问题

问题描述：有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：

允许多个读者可以同时对文件执行读操作；
只允许一个写者往文件中写信息；
任一写者在完成写操作之前不允许其他读者或写者工作；
写者执行写操作前，应让已有的读者和写者全部退出。

问题分析：

关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。
整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的 P 操作、V 操作即可解决。读者的问题比较复杂，它必须在实现与写者互斥的同时，实现与其他读者的同步，因此简单的一对 P 操作、V 操作是无法解决问题的。这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，此时读者会一直占用文件，当没有读者时，写者才可以写文件。同时，这里不同读者对计数器的访问也应该是互斥的。
信号量设置。首先设置信号量 count 为计数器，用于记录当前读者的数量，初值为 0；设置 mutex 为互斥信号量，用于保护更新 count 变量时的互斥；设置互斥信号量 rw，用于保证读者和写者的互斥访问。

代码如下：

semaphore rw = 1; // 用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;    // 记录当前有几个读进程在访问文件
semaphore mutex = 1;

writer(){
    while(1){
        P(rw);
        // 写文件...
        V(rw);
    }
}

reader(){
    while(1){ 
        P(mutex);  // 各读进程互斥访问count
        if(count==0){ 
            P(rw); // 第一个读进程负责“加锁”
        }
        count++;   // 访问文件的读进程数+1
        V(mutex);
        
        // 读文件...
        
        P(mutex);  // 各读进程互斥访问count
        count--;   // 访问文件的读进程数+1
        if(count==0){
            V(rw); // 最后一个读进程负责“解锁”
        }
        V(mutex);
    }
}

潜在的问题：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的

semaphore rw = 1; // 用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;    // 记录当前有几个读进程在访问文件
semaphore mutex = 1;
semaphore w= 1; // 用于实现"写优先"

writer(){
    while(1){
        P(w);
        P(rw);
        // 写文件...
        V(rw);
        V(w);
    }
}

reader(){
    while(1){ 
        P(w);
        P(mutex);  // 各读进程互斥访问count
        if(count==0){ 
            P(rw); // 第一个读进程负责“加锁”
        }
        count++;   // 访问文件的读进程数+1
        V(mutex);
        V(w);
        
        // 读文件...
        
        P(mutex);  // 各读进程互斥访问count
        count--;   // 访问文件的读进程数+1
        if(count==0){
            V(rw); // 最后一个读进程负责“解锁”
        }
        V(mutex);
    }
}

结论：在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不
是真正的“写优先"，而是相对公平的先来先服务原则。有些书上把这个算法称为读写公平法，即读写程具有样的优先级。

其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。

另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。

哲学家进餐问题

问题描述：一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析：

关系分析。5 名哲学家与左右邻居对其中间筷子的访问是互斥关系。
整理思路。显然，这里有 5 个进程。本题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。解决方法有两个：一是让他们同时拿两根筷子；二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。
信号量设置。定义互斥信号量数组 chopstick[5]= {1,1,1,1,1}，用于对5个筷子的互斥访问。哲学家按顺序编号为 0 ~ 4，哲学家 i 左边筷子的编号为 i，哲学家右边筷子的编号为 (i + 1)%5。

semaphore chopstick[5] = {1,1,1,1,1};

Pi(){
    while(1){
        P(chopstick[i]);       // 拿左
        P(chopstick[(i+1)%5]); // 拿右
        eat;
        V(chopstick[i]);       // 放左
        V(chopstick[(i+1)%5]); // 放右
        think;
    }
}

该算法存在以下问题：当 5 名哲学家都想要进餐并分别拿起左边的筷子时（都恰好执行完 wait(chopstick[i]);）筷子已被拿光，等到他们再想拿右边的筷子时（执行 wait(chopstick[(i + 1)%5]);）就全被阻塞，因此出现了死锁。

为防止死锁发生，可对哲学家进程施加一些限制条件，比如：

至多允许 4 名哲学家同时进餐；这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。设置初始值为 4 的信号量。
对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。判断序号奇偶
仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子；

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;
Pi(){
    while(1){
        P(mutex);
        P(chopstick[i]);       // 拿左
        P(chopstick[(i+1)%5]); // 拿右
        V(mutex);
        eat;
        V(chopstick[i]);       // 放左
        V(chopstick[(i+1)%5]); // 放右
        think;
    }
}

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁"问题的隐患。

管程

在信号量机制中，每个要访问临界资源的进程都必须自备同步的 PV 操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁。于是，便产生了一种新的进程同步工具——管程。管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。

管程的定义和基本特征

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。

利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。

这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程（monitor）。

管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程是一种特殊的软件模块，有这些部分组成：

局部于管程的共享数据结构说明；
对该数据结构进行操作的一组过程；
对局部于管程的共享数据设置初始值的语句；
管程有一个名字。

熟悉面向对象程序设计的读者看到管程的组成后，会立即联想到管程很像一个类（class）。

管程的基本特征：

局部于管程的数据只能被局部于管程的过程所访问；
一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
每次仅允许一个进程在管程内执行某个内部过程。

/*管程伪代码*/
monitor ProducerConsumer
    condition full, empty;  // 条件变量用来实现同步(排队)
    int count = 0;  // 缓冲区中的产品数
    void insert(Item item){  // 把产品item 放入缓冲区 
        if(count==N){
            wait(full);
        }
        count++;
        insert_item(item);
        if(count==1){
            signal(empty)
        }
    }
    Item remove(){  // 从缓冲区中取走一个产品
        if(count==0){
            wait(empty);
        }
        count--;
        if(count==N-1){
            signal(full);
        }
        return remove_item();
    }
end monitor;

// 生产者进程
producer(){
    while(1){
        item = producer_item();
        ProducerConsumer.insert(item);
    }
}

// 消费者进程
consumer(){
    while(1){
        item = ProducerConsumer.remove();
        consumer_item(item);
    }
}

由编译器负责实现各进程互斥地进入管程中的过程

引入管程的目的无非就是要更方便地实现进程互斥和同步。

需要在管程中定义共享数据（如生产者消费者问题的缓冲区）
需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）
只有通过这些特定的“入口”才能访问共享数据
管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心）
可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

Java 中，如果用关键字 synchronized 来描述一个函数，那么这个函数同一时间段内只能被一个线程调用

死锁

死锁的概念

死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题——死锁。所谓死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

下面通过一些实例来说明死锁现象。

先看生活中的一个实例。在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。若有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述冲突情况：此时，左边的汽车占有桥面左边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段；右边的汽车占有桥面右边的一段，要想过桥还需等待左边的汽车让出桥面左边的段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如，某计算机系统中只有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2所占用，而P2在未释放打印机之前，又提出请求使用正被P1占用的输入设备。这样，两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

死锁、饥饿、死循环的区别

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

共同点：都是进程无法顺利向前推进的现象，（故意设计的死循环除外）

区别：

死锁一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态。
可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态（如长期得不到需要的I/O设备），也可能是就绪态（长期得不到处理机）
可能只有一个进程发生死循环。死循环的进程可以上处理机运行（可以是运行态），只不过无法像期待的那样顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥
饿是管理者（操作系统）的问题，死循环是被管理者的问题。

死锁产生的原因

系统资源的竞争

通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。

进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁。例如，并发进程P1，P2分别保持了资源R1，R2，而进程P1申请资源R2、进程P2申请资源R1时，两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息，也会使得这些进程间无法继续向前推进。例如，进程A等待进程B发的消息，进程B又在等待进程A发的消息，可以看出进程A和B不是因为竞争同一资源，而是在等待对方的资源导致死锁。

死锁产生的必要条件

产生死锁必须同时满足以下4个条件，只要其中任意一个条件不成立，死锁就不会发生。

互斥条件：进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）。
请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

注意❗ 发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

总之，对不可剥夺资源的不合理分配，可能导致死锁。

死锁的处理策略

为使系统不发生死锁，必须设法破坏产生死锁的4个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。

死锁预防。设置某些限制条件，破坏产生死锁的4个必要条件中的一个或几个，以防止发生死锁。
避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。
死锁的检测及解除。无须采取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检
测出死锁的发生，然后采取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低：避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

处理策略	资源分配策略	各种可能模式	主要优点	主要缺点
死锁预防	保守，宁可资源闲置	一次请求所有资源，资源剥夺，资源按序分配	适用于突发式处理的进程，不必进行剥夺	效率低，进程初始化时间延长；剥夺次数过多；不便灵活申请新资源
死锁避免	是“预防”和“检测”的折中（在运行时判断是否可能死锁）	寻找可能的安全允许顺序	不必进行剥夺	必须知道将来的资源需求；进程不能被长时间阻塞
死锁检测	宽松，只要允许就分配资源	定期检查死锁是否已经发生	不延长进程初始化时间，允许对死锁进行现场处理	通过剥夺解除死锁，造成损失

死锁预防

防止死锁的发生只需破坏死锁产生的4个必要条件之一即可。

1.破坏互斥条件

若允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。

比如: SPOOLing 技术。操作系统可以采用 SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如，用 SPOOLing 技术将打印机改造为共享设备。

2.破坏不剥夺条件

当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺，或从而破坏了不剥夺条件。

该策略实现起来比较复杂；
释放已获得的资源可能造成前一阶段工作的失效；
反复地申请和释放资源会增加系统开销，降低系统吞吐量。

这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

3.破坏请求并保持条件

采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行，这些资源就一直归它所有，不再提出其他资源请求，这样就可以保证系统不会发生死锁。

这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

4.破坏循环等待条件

为了破坏循环等待条件，可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时己考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

死锁避免

避免死锁同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。

系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。

所谓安全状态，是指系统能按某种进程推进顺序（P1，P2，…，Pn）为每个进程 Pi 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称 P1，P2，…，Pn 为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

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

银行家算法

银行家算法是最著名的死锁避免算法，其思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

假设系统中有n个进程，m种资源。每个进程在运行前先声明对各种资源的最大需求数，则可用一个n*m的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i, j]=K表示进程 P_i 最多需要K个资源R_j。同理，系统可以用一个n*m的分配矩阵 Allocation表示对所有进程的资源分配情况。Max - Allocation = Need矩阵，表示各进程最多还需要多少各类资源。另外，还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源。

某进程Pi向系统申请资源，可用一个长度为m的一维数组Request；表示本次申请的各种资源量。

数据结构：

长度为m的一维数组Available表示还有多少可用资源；
n*m矩阵Max表示各进程对资源的最大需求数；
n*m矩阵Allocation表示已经给各进程分配了多少资源；
Max-Allocation=Need 矩阵表示各进程最多还需要多少资源；
用长度为m的一位数组Request表示进程此次申请的各种资源数

可用银行家算法预判本次分配是否会导致系统进入不安全状态：

如果 Request_i[j] ≤ Need[i, j] （0≤j≤m）便转向第2步，否则认为出错。【检查此次申请是否超过了之前声明的最大需求数】
如果 Request_i[j] ≤ Available[j] （0≤j≤m）便转向第3步，否则表示尚无足够资源，Pi必须等待。【检查此时系统剩余的可用资源是否还能满足这次请求】
系统试探着把资源分配给进程Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判）Available = Available - Request_i;、Allocation[i, j] = Allocation[i, j] + Request_i[j];【试探着分配，更改各数据结构】
操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。【用安全性算法检查此次分配是否会导致系统进入不安全状态】

安全性算法步骤：检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程看是否能将所有进程都加入安全序列。

死锁检测和解除

死锁检测

为了能对系统是否已发生了死锁进行检测，必须：

用某种数据结构来保存资源的请求和分配信息；
提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

资源分配图

系统死锁可利用资源分配图来描述。

资源分配图两种结点：

进程节点：对应一个进程
资源节点：对应一类资源，一类资源可能有多个

资源分配图两种边：

进程节点 → 资源节点：表示进程申请几个资源（每条边代表一个）
资源节点 → 进程节点：表示已经为进程分配了几个资源（每条边代表一个）

死锁定理

简化资源分配图可检测系统状态是否为死锁状态。简化方法如下：

在资源分配图中，找出既不阻塞又不孤点的进程P_i （即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量，如上图在，R1没有空闲资源，R2 有一个空闲资源。若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图中，P1 是满足这一条件的进程结点，将P1的所有边消去。

进程 P_i 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。进程P2就满足这样的条件。根据上面方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）。

S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的，该条件为死锁定理。

死锁解除

一旦检测出死锁，就应立即采取相应的措施来解除死锁。死锁解除的主要方法有：

资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
撤销进程法。强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撒销的原则可以按进程优先级和撤销进程代价的高低进行。
进程回退法。让一（或多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点。

如何决定“对谁动手”？

进程优先级
已执行多长时间
还要多久能完成
进程已经使用了多少资源
进程是交互式的还是批处理式的