系统架构设计笔记（2）—— 操作系统进程管理

深藏阁楼爱情的钟 2023-07-12 09:21 36阅读 0赞

操作系统基本原理包含以下 5 大管理。

![format_png][]

我们先来说说进程管理。

因为处理机是计算机系统的核心资源，所以整个操作系统的重心是处理机管理。

处理机管理中最基本的、最重要的概念是进程。进程是系统并发执行的体现。

<table> 
 <thead> 
  <tr> 
   <th align="center">不同观点</th> 
   <th align="left">操作系统</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">静态</td> 
   <td align="left">是一组程序和表格集合的操作系统。</td> 
  </tr> 
  <tr> 
   <td align="center">动态</td> 
   <td align="left">是进程动态和并发执行的操作系统。</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th align="center">不同观点</th> 
   <th align="left">进程</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">静态</td> 
   <td align="left">进程是由程序 、 数据和进程控制块 ( ProcessControlBlock ， PCB ) 组成的。</td> 
  </tr> 
  <tr> 
   <td align="center">动态</td> 
   <td align="left">进程是计算机状态的一个有序集合。</td> 
  </tr> 
 </tbody> 
</table>

进程控制块 PCB 是进程存在的唯一标志， PCB 描述了进程的基本情况，具体内容可分为调度信息和执行信息两大部分。调度信息供进程调度使用，包括进程当前的一些基本属性 ; 执行信息即现场，描述了进程的执行情况 。 PCB 随着进程的建立而产生，随着进程的完成而消亡。

顺序程序是指程序中若干操作必须按照某种先后次序来执行，并且每次操作前后的数据、状态之间都有一定的关系。早期的程序设计一般都是按顺序执行的。

多道程序系统，有以下特点：

1.  资源共享。这样可以提高资源利用率，是由多道程序共用。
2.  并发执行。允许一个用户程序内部完成不同操作的程序段之间并行运行；允许操作系统内部不同的程序之间并行运行。物理上讲：内存中保存多个程序，I/O 设备被多个程序交替地共享使用；在多处理机系统的情形下，表现为多个程序在各自的处理机上运行，执行时间是重叠的。单处  
    理机系统时，程序的执行表现为多道程序交替地在处理机上相互空插运行。

程序的并行执行和资源共享之间是相辅相成的：

1.  只有允许程序并行执行，才可能存在资源共享的问题；
2.  只有有效地实现资源共享，才可能使得程序并行执行。

实际情况是：大多数程序段要求操作在时间上是有序的，也就是说有些操作必须在其他操作之前，但其中有些操作却可以同时进行，这时就可以采用并发操作。

## 1 进程状态转换 ##

由于进程运行的间断性，决定了进程至少具有以下三种状态：

1.  就绪状态。当进程已分配了除 CPU 以外的所有必要的资源后，只要能再获得处理机，便能立即执行，这时的进程状态就称为就绪状态。在一个系统中，可以有多个进程同时处于就绪状态，通常把它们排成一列，称为就绪队列。
2.  执行状态。是指进程已获得处理机，正在执行。在单处理机系统中，只能有一个进程处于执行状态。如果是多处理机，就可以多个进程处于执行状态。
3.  阻塞状态指进程因发生某事件（如请求 I/O、申请缓冲空间等）而暂停执行时的状态，也就是说，进程的执行受到了阻塞，也可以称其为“等待”状态或“睡眠”状态。通常把它们排成一列，称为阻塞队列。

进程的状态会随着自身的推进或外界条件的变化而变化。

![format_png 1][]

<table> 
 <thead> 
  <tr> 
   <th align="center">状态变化</th> 
   <th align="left">示例条件</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">运行态→阻塞态</td> 
   <td align="left">运行中启动了外围设备； 运行中申请资源（主存储空间及外围设备得不到满足）；运行中出现了故障（程序出错或主存储器读写错误等）</td> 
  </tr> 
  <tr> 
   <td align="center">阻塞态→就绪态</td> 
   <td align="left">外围设备工作结束；等待的资源能得到满足；</td> 
  </tr> 
  <tr> 
   <td align="center">运行态→就绪态</td> 
   <td align="left">进程用完了一个使用处理器的时间后；有更高优先权的进程要运行时；由于自身或外界原因成为等待状态的进程让出处理器时；</td> 
  </tr> 
  <tr> 
   <td align="center">就绪态→运行态</td> 
   <td align="left">系统按一种选定的策略从处于就绪状态的进程中选择一个进程。</td> 
  </tr> 
 </tbody> 
</table>

**注意：** 任何一个结束阻塞的进程必须先变成就绪状态，待分配到处理器后才能运行。

## 2 挂起状态 ##

引入挂起状态的原因：

1.  对换的需要。为了缓解内存紧张，而将内存中处于阻塞状态的进程换至外存上，使进程又处于一种有别于阻塞状态的新状态。
2.  终端用户的请求。当终端用户在自己的程序运行期间，发现有可疑问题时，往往希望使自己的进程暂停下来。
3.  父进程的请求。父进程常常希望能挂起自己的子进程，以便考查和修改子进程，或者协调各子进程间的活动。
4.  负荷调节的需要。当实时系统中的工作负荷较重时，有可能影响到对实时任务的控制，可由系统把一些不重要的进程挂起，以保证系统正常运行。
5.  操作系统的需要。操作系统希望挂起某些进程，以便检查运行中资源的使用情况及进行记账。

挂起状态有以下这些特性：

1.  原来处于就绪状态的进程，被挂起后，就进入“静止就绪” 状态；原来处于阻塞状态的进程，被挂起后，就进入“静止阻塞” 状态。
2.  “静止阻塞” 状态的进程，恢复后，进入“活跃阻塞” 状态。
3.  进程可以由其自身挂起，也可由用户或操作系统等对象将该进程挂起。其目的都在于阻止进程继续运行，被挂起的进程只能用显式方式来激活，以便从挂起状态中解脱出来。
4.  静止就绪态表明进程具备运行条件但目前在二级存储器 ( 辅存 ) 中，只有当它被对换到内存时才能被调度执行。
5.  静止阻塞态则表明进程正在等待某一个事件且在二级存储器中。

![format_png 2][]

--------------------

新的模型是把三态模型中的等待态改名为活跃阻塞态，就绪态改名为活跃就绪态，然后新增了与挂起相关的两种状态（静止就绪态和静止阻塞态）。

## 3 进程互斥与同步 ##

进程互斥指的是：一组并发进程中一个或多个程序段，因共享某一共有资源而导致必须以互斥的方式访问。也就是说，互斥指的是要保证临界资源在某一时刻只被一个进程访问。**互斥即资源竞争关系。**

进程同步指的是：各进程异步执行，但必须按一定的制约顺序和速度执行。**同步是进程间协作关系。**

临界资源指的是：一次仅允许一个进程使用的资源。比如，物理设备如打印机、磁带机等，某些软件的变量、数据、表格等。

临界区指的是：一个进程访问临界资源的那段程序代码。  
进程互斥加入临界区概念之后，可以这样描述：禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。因此必须有专门的同步机制来协调它们。

协调准则如下：

1.  空闲让进 - 无进程处于临界区时，这时，有进程要求进入临界区，则立即准其进入；
2.  忙则等待 - 当已有进程进入其临界区时，其他试图进入该临界区的进程必须等待，确保各进程必须互斥地进入临界区；
3.  有限等待 - 有有多个进程要求进入临界区时，应该在有限的时间内使某一进程进入临界区，而不是它们相互等待导致谁也进不了临界区；
4.  让权等待 - 信号量可以有效地实现进程的同步和互斥。

在操作系统中，信号量是一个整数。当信号量大于等于 0 时，代表可供并发进程使用的资源实体数；当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建的信号量所代表的意义和设置初始值，以及建立相应的数据结构，以便指向那些等待使用该临界区的进程。

信号量操作： P 操作和 V 操作。它们都是不可分割的原子操作，也称为原语。原语操作指的是，在执行期间不允许发生中断。

P(sem) 操作会将信号量 sem 值减 1，如果操作前 sem 值为负数，那么调用 P 操作的进程将暂停执行，直到另一个进程对同一信号量做 V 操作。 V(sem) 操作会是将信号量 sem 值加 1，若 sem 的值<=0，操作系统会从与 sem 有关的队列中选一个进程，唤醒它。

--------------------

总结如下：

1.  信号量 : 是一种特殊的变量，表现形式是一个整型 S 和一个队列；
2.  P操作 : S = S -1，若 S <0，进程暂停执行，进入等待队列；
3.  V操作 : S = S +1，若 S <=0，则唤醒等待队列中的一个进程 。

> P 是减 1，消耗资源；V 是加 1，释放资源。

P(sem) 操作定义：

P(sem)  {
      sem = sem - 1;
      if ( sem < 0 )
        进程进入等待状态;
      else 
        继续进行;
     }

V(sem) 操作定义：

V(sem) {
      sem = sem + 1;
      if（ sem ≤ 0）
        唤醒队列中的一个等待进程;
      else 
        继续进行;
    }

### 3.1 互斥控制 ###

利用 P、 V 原语和信号量可以方便地解决并发进程在临界区的互斥问题。

假设信号量 mutex 是用于互斥的信号量，初值为 1，表示没有并发进程使用该临界区。  
于是各并发进程的临界区可改写成下列形式的代码段：

P(信号量 S)；
      临界区
    V(信号量 S)；

1.  由于只允许一个进程进入，因此信号量 S 的初值应该为 1。 信号量 S 的初值表示可以允许多少个进程进入；
2.  当 S < 0 时，其绝对值就是等待使用临界资源的进程总数，也就是等待队列中的进程数。而当一个进程从临界区出来时（即释放临界资源），执行 V 操作 ( S = S +1 ) ，如果等待队列中还有进程需要进入临界区 ( S<=0 ) ，则调入 ( 唤醒 )一个新的进程进入该临界区。

### 3.2 同步控制 ###

要用 P， V 操作实现进程同步，需要引入私有信号量。注意：私有信号量只与制约进程和被制约进程有关，而不是与整组并发进程。与此相对，进程互斥使用的信号量为公用信号量。

首先为各并发进程设置私用信号量，然后为私有信号量赋初值，最后利用 P， V 原语和私用信号量定义各进程的执行顺序。

最简单的同步控制是进程 A 在另一个进程 B 到达 L2 以前，不应前进到超过点 L1。

![format_png 3][]

要确保进程 B 执行 V 操作之前，不让进程 A 的运行超过 L1 ，就要设置信号量 S 的初值为 0 。 这样，如果进程 A 先执行到 L1 ，那么执行 P 操作 ( S = S - 1 ) 后，则 S < 0 ，就停止执行，让其进入阻塞状态。直到进程 B 执行到 L2 时，再执行 V 操作 ( S = S +1 ) ，唤醒进程 A 让其继续执行 。

### 3.3 生产者－消费者问题 ###

“生产者－消费者” 是经典的同步问题。要求存后再取，取后再存，即存在两个制约关系（缓存区如果满了，就停止生产；而缓存区如果空了，则停止消费）。

生产者 - 消费者问题不仅要解决生产者进程与消费者进程的同步关系，还要处理缓冲区的互斥关系，因此需要 3 个信号量来实现：

<table> 
 <thead> 
  <tr> 
   <th align="center">信号量</th> 
   <th align="center">类别</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">empty</td> 
   <td align="center">同步</td> 
   <td align="left">空闲的缓冲区数量。程序刚开始时，缓冲区全部为空。所以，其初始值应为缓冲区的总个数。</td> 
  </tr> 
  <tr> 
   <td align="center">full</td> 
   <td align="center">同步</td> 
   <td align="left">已填充的缓冲区数量。程序刚开始时，所有缓冲区都为空 ，所以，其初始值为 0。</td> 
  </tr> 
  <tr> 
   <td align="center">mutex</td> 
   <td align="center">互斥</td> 
   <td align="left">确保同时只有一个进程正在写缓冲区，因此，其初始值为1。</td> 
  </tr> 
 </tbody> 
</table>

如果对缓冲区的读写无须进行互斥控制的话，那么就不需要 mutex 的互斥信号量了。

假设我们只对生产者与消费者进行同步控制，那么程序如下。

生产者程序 ：

loop
      生产一个物品;
      P(empty); //空闲的缓冲区数量 - 1
      物品存入缓冲区;
      V(full);//填充的缓冲区数量 + 1
    endloop

消费者程序 ：

loop
      P(full);//填充的缓冲区数量 - 1
      从缓冲区中取出物品;
      V(empty);//空闲的缓冲区数量 +1
      使用它;
    endloop

--------------------

1.  信号量与 PV 操作是用来解决并发问题中的互斥与同步两个关系。因此，在并发分析时，应该先从寻找互斥与同步关系开始。这个分析过程可以参考简单互斥 、 简单同步以及生产者 - 消费者问题 。
2.  通常来说，一个互斥或一个同步关系可以使用一个信号量来解决，但要注意一些经常会被忽略的隐藏同步关系。例如，在生产者 - 消费者问题中，就存在两个同步关系，一个是判断是否还有足够的空间给生产者存放产物，另一个是判断是否有足够的产物让消费者使用。
3.  信号量的初值通常就是表示可用的资源数。而且通常对于初始为 0 的信号量，会先做 V 操作，比如生产者 - 消费者问题中的 full 信号量（表示已填充的缓冲区数量）。
4.  在资源使用之前，会使用 P 操作，表示占用资源；在资源使用完之后，会使用 V 操作，表示释放资源。在互斥关系中， PV 操作是在一个进程中成对出现的；而在同步关系中，则 PV 操作是在两个进程甚至是多个进程中成对出现的。

### 3.4 实际应用 ###

假设，在某并发系统中，有一个发送进程 A 、 一个接收进程 B 、 一个环形缓冲区 BUFFER 、 信号量 S1 和 S2。 发送进程不断地产生消息并写入缓冲区 BUFFER ，接收进程不断地从缓冲区 BUFFER 中取消息。假设发送进程和接收进程可以并发地执行，那么，当缓冲区的容量为 N 时，如何使用 PV 操作才能保证系统能够正常工作。发送进程 A 和接收进程 B 的工作流程如图 8 所示。请在图 8 中的 ①~④ 处填写正确的操作。

![format_png 4][]

显然，这是一个 “ 生产者 - 消费者 ” 问题，这个问题通常需要 3 个信号量来实现 : 两个用来管理缓冲区同步，信号量 empy 表示空闲缓冲区数量，初值为缓冲区最大数 N ，信号量 full 表示已填充缓冲区数量，初值为 0； 第三个信号量用于管理互斥，由信号量 mutex 保证只有一个进程在写缓冲区，初值为 1。 但在本系统中，进程 A 和进程 B 允许并发地访问缓冲区，因此无须管理互斥，因此只需定义两个信号量 : S 1和 S2 ，初值为 N 的 S1 在此承担的是信号量 empty 的功能，初值为 0 的 S2 则承担了信号量 full 的功能。

![format_png 5][]

在这套并发系统的基础上，如果系统中有多个发送进程和接收进程，进程间的工作流程如图 10 所示。发送进程产生消息并顺序地写入环形缓冲区 BUFFER，接收者进程顺序地从 BUFFER中取消息，且每条消息只能读取一次为了保证进程间的正确通信，增加了信息量 SA 和 SB 。请说明信息量 SA 和 SB 的物理意义，并把信息量 SA 和 SB 正确应用到流程中。

这里的关键点是系统中允许有多个发送进程和接收进程，推断系统需要完成的控制是： 发送进程顺序写入，接收进程顺序读取，而且每条消息都只能够读取一次。这显然是两个互斥的问题，即多个发送进程在写缓冲区时是互斥关系，多个接收进程读缓冲区也是互斥关系。因此，信号量 SA 和 SB 用于分别实现这两个互斥控制。

![format_png 6][]

1.  发送进程 : 在进程产生消息之后准备写入缓冲区时，这时就需要进行互斥判断，而直到完成 “ i=(i+1)modN ” 操作后，才完成缓冲区操作。
2.  接收进程 : 由于接收进程是负责读数据的，如果数据区是空的则应该等待，因此必须先完成 P(S2) 操作，来决定其是否需要阻塞。如果没有阻塞时，再进入临界区；而 “ 对读取的消息进行处理 ” 已显然在临界区之外，因此在这之前插入V(SB)。

## 4 前趋图 ##

前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺  
序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程，结点间的有  
向边表示两个结点之间存在的前趋关系。

比例：在计算机中，经常采用流水线方式执行指令，每一条指令都可以分解为取指（取出指令）、分析和执行三步。取指操作为 Ai，分析操作为 Bi 和执行操作为 Ci(i=1,2,3)。图 6 所示即为三个任务各程序段并发执行的前驱图。

![image.png][]

图中 A1 没有前趋结点，称为**开始结点**，它不受任何制约，可以直接执行；而 B1 与 A2 只能在 A1 执行完成之后才能开始，而 B2 必须在 B1 与 A2 完成之后才能开始； C3 没有后继结点，称为**终止结点**。

在前趋图中，执行先后顺序的制约关系可分为两种：

1.  直接制约 - 一个操作中，多个步骤之间的制约关系，也可以说是“同步的进程之间的制约关系”。如图 6 所示， A1、 B1、 C1 是一条指令的取指、分析、执行的三个步骤，  
    所以它们之间是直接制约关系。
2.  间接制约 - 多个操作之间相同步骤的制约关系，也可以说是“互斥的进程之间的制约关系”。如图 6 所示， A1、 A2、 A3 之间就存在间接制约的关系。

--------------------

以下是 PV 操作与前趋图结合的示例。假设进程 P1、P2、P3、P4 和 P5 的前趋图如图 7 所示：

![format_png 7][]

若用 PV 操作控制进程 P1~P5 并发执行的过程，则需要设置5个信号量 S1、S2、S3、S4 和 S5 ，进程间同步所使用的信号量标注在图 7 中的边上，且信号量 S1~S5 的初值都等于零，初始状态下进程 P1 开始执行。则该如何设置信号量来控制这些进程？

![format_png 8][]

根据前趋图，得知进程之间的约束关系为：

1.  P1 执行后，才能开始执行 P2 与 P3；
2.  P2 执行后，才能开始执行 P4；
3.  P2、P3 执行后，才能开始执行 P5。

这里的信号量用于进程同步。前趋图的进行信号量使用规则如下：

1.  进程开始执行前，必须对前趋图中指向自己的信号量执行 P 操作，等待前一个进程完成。比如进程 P2，指向自己的信号量为 S1，那么就必须先执行 P(S1) 操作；
2.  进程结束后，必须执行对前趋图中的出口信号量，执行 V 操作，给后一个进程的执行创建条件。比如进程 P1 执行后，它的出口有两条线，信号量分别为 S1 与 S2，那么就需要对这两个信号量都执行 V 操作。

![format_png 9][]

## 5 进程调度 ##

进程调度即处理器调度（又称上下文转换），它的主要功能是确定在什么时候分配处理器，并确定分给哪一个进程，即让正在执行的进程改变状态转入就绪队列的队尾，再由调度原语取出就绪队列的队首进程，并执行它。

引起进程调度的原因有以下几类：

1.  正在执行的进程执行完毕。
2.  执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态。
3.  执行中的进程调用了 P 原语操作，然后因资源不足而被阻塞；或调用 V 原语操作激活了等待资源的进程队列。
4.  在分时系统中，当一个进程用完了一个 CPU 时间片。
5.  就绪队列中某个进程的优先级变得高于当前执行进程的优先级，也将引起进程调度。

对于不同的系统与目标，会采取不同的进程调度算法：

1.  先来先服务（ First Come and First Serverd， FCFS）调度算法，又称先进先出（ First In and First Out， FIFO）。比如就绪队列，会按照先来后到原则排队。
2.  优先数调度。优先数反映了进程优先级，就绪队列按优先数排队。有两种确定优先级的方法，即静态优先级和动态优先级。静态优先级是指进程的优先级在进程开始执行前确定，执行过程中不变；而动态优先级则可以在进程执行过程中改变优先级。
3.  轮转法（ Round Robin）。就绪队列按 FCFS 方式排队。每个进程执行一次占有处理器时间都不能超过规定的时间单位（时间片）；如果超过，则自行释放自己所占有的 CPU 资源，然后排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去取当前就绪队列中的第一个进程，放入处理器执行。

在进程管理的实现中，如果设计不当，就会出现**死锁**。

## 6 死锁 ##

当若干个进程互相争用对方已占有的资源，导致无限期地等待，不能向前推进的情况，就会造成“死锁”。例如， P1 进程占有资源 R1， P2 进程占有资源 R2，这时， P1 又需要资源 R2， P2 也需要资源 R1，它们在互相等待对方占有的资源时，又无法释放自己占有的资源，从而使双方都进入了无限等待状态。

归纳来说，就是多个进程之间互相等待对方的资源，而在得到对方资源之前又不释放自己的资源，这样，就会造成循环等待，这就是死锁。如果一个进程在等待一个永远不可能发生的事件，就会造成死锁。

死锁是系统的一种出错状态，它不仅会浪费大量的系统资源，甚至还会导致整个系统的崩溃，所以死锁是应该尽量预防和避免的。

产生死锁的主要原因是共享资源不足，资源分配策略和进程的推进顺序不当造成的。系统资源既可能是可重复使用的永久性资源，也可能是消耗性的临时资源。

### 6.1 产生死锁的必要条件 ###

产生死锁的必要条件是：互斥条件、保持和等待条件、不剥夺条件和环路等待条件。

1.  互斥条件 : 即一个资源每次只能被一个进程使用；
2.  保持与等待条件 : 有一个进程已获得了某些资源，但因请求其他资源而被阻塞时，又对所获得的资源保持不放；
3.  不可抢占条件 : 有些系统资源是不可抢占的，当某个进程已获得这种资源后系统不能强行收回，只能由进程使用完资源后自己释放；
4.  循环等待条件 : 若干个进程形成环形链，每个都占用对方要申请的下一个资源。

### 6.2 银行家算法 ###

银行家算法指的是，当进程请求资源时，系统将按照如下原则分配资源 :

1.  当一个进程对资源的最大需求量不超过系统中的可用资源数时，就接纳该进程；
2.  进程可以分期请求资源，但请求的总数不能超过该进程对资源的最大需求量；
3.  当系统现有的资源不能满足进程所需要的资源数时，会推迟分配该进程的请求，但总能使进程在有限的时间内得到相应资源；
4.  当系统现有的资源能满足进程所需要的资源数时，必须测试系统现存的资源能否真的能满足该进程所需的最大资源数，若能满足则按当前的申请量分配资源，否则也要推迟分配；

假设系统中有三类互斥资源 R1、R2 和 R3 ，可用资源数分别是 9、8 和 5。 在 T0 时刻系统中有 P1、P2、P3、P4 和 P5 五个进程，这些进程对资源的最大需求量和已分配资源数如表 1 所示。进程按照 P1→P2→P4→P5→P3 序列执行，系统状态安全吗 ? 如果按P2→P4→ P5→P1→P3 的序列呢 ?

![format_png 10][]

从表 1 中可以看出，还有 2 个 R1 （9-1-2-2-1-1=2）未分配，1个 R2 （8-2-1-1-2-1=1）未分配，而 R3 全部分配完毕（5-1-1-3=0）。

按照 P1 → P2 → P4 →P5→P3 的顺序执行时，首先执行 P1 ，这时由于其R1、 R2 和 R3 的资源数都未分配够，因而开始申请资源，得到还未分配的 2 个 R1 ，1个 R2 。但其资源仍不足 ( 因为没有可用的 R3 资源 ) ，从而进入阻塞状态，并且这时所有资源都已经分配完毕。因此，后续的进程都无法得到能够完成任务的资源，全部进入阻塞，这时死锁就发生了。

而如果按照 P2 → P4 →P5→ P1 →P3 的序列执行时：

1.  首先执行 P2 ，它还差1个 R2 资源，系统中刚好还有 1 个未分配的 R2 ，因此满足其要求，进程能够顺利结束，并释放出所占用的资源：2个 R1 、2个 R2、1 个 R3 。这时，未分配的资源为 4 个 R1（2+2） 、2 个 R2 、1 个 R3 。
2.  然后执行 P4 ，它还差一个 R3 ，而这时系统中刚好有一个未分配的 R3 ，因此满足其要求，也能够顺利结束，并释放出所占用的资源。这时，未分配的资源为 5个 R1（4+1） 、4个 R2（2+2） 、1个 R3 。
3.  接着执行 P5，它需要 2 个 R1、3 个 R2 以及 1 个 R3，这些资源都满足，所以也会顺利结束，并释放出所占用的资源。这时，未分配的资源为 8个 R1（5+3） 、8个 R2（4+4） 、5个 R3（4+1） 。  
    根据这样的方式推下去，会发现按这种序列可以顺利地完成所有的进程，而不会出现死锁现象。

### 6.3 解决死锁的策略 ###

处于死锁状态的进程不能继续执行但又占用了系统资源，从而阻碍其他作业的执行。因此必须解决死锁。解决死锁的策略为：

1.  死锁预防 : 破坏导致死锁必要条件中的任意一个就可以预防死锁。例如，采用资源静态分配法，要求用户申请资源时一次性申请所需要的全部资源，这就破坏了保持和等待条件 ;采用资源有序分配法将资源分层，得到上一层资源后， オ 能够申请下一层资源，它破坏了环路等待条件。预防通常会降低系统的效率 。
2.  死锁避免 : 避免是指进程在每次申请资源时判断这些操作是否安全，例如，使用银行家算法。死锁避免算法的执行会增加系统的开销 。
3.  死锁检测 : 死锁预防和避免都是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略 。
4.  死锁解除 : 这是与死锁检测结合使用的，它使用的方式是剥夺。即将某进程所拥有的资源强行收回，分配给其他的进程 。

> 实际上，系统出现死锁的概率很小，故从系统所花的代价上来看，采用死锁发生后的检测与解除策略要比采用死锁发生前的预防与避免策略代价要小一些。所以，推荐采用死锁发生后的检测与恢复策略。

## 7 管程与线程 ##

**管程**由管程名 、 局部子管程的变量说明 、 使用共享资源并在数据集上进行操作的若干过程，以及对变量赋初值的语句等4个基本部分组成。

每一个管程管理一个临界资源。当有多个进程调用某管程时，仅允许一个进程进入管程，其他调用者必须等待，也就是申请进程必须互斥地进入管程。方法是通过调用特定的管程入口进入管程，然后通过管程中的一个过程使用临界资源。当某进程通过调用请求访问某临界资源而未能满足时，管程调用相应同步原语使该进程进入等待状态，并将它放入等待队列。当使用临界资源的进程访问完该临界资源并释放之后，管程又调用相应的同步原语唤醒等待队列中的队首进程。为了表示不同的等待原因，设置条件变量，条件变量是与普通变量不同的变量，条件变量不能取任何值，只是一个排队栈。

**线程**是进程的活动成分，是处理器分配资源的最小单位，它可以共享进程的资源与地址空间，通过线程的活动，进程可以提供多种服务 ( 对服务器进程而言 ) 或实行子任务并行 ( 对用户进程而言 ) 。每个进程创建时只有一个线程（主线程），根据需要在运行过程中创建更多的线程。显然，只有主线程的进程才是传统意义下的进程内核负责线程的调度，线程的优先级可以动态地改变。

采用线程机制的最大优点是节省开销，传统的进程创建子进程的办法内存开销大，而且创建时间也长。

在多线程系统中，一个进程可以由一个或多个线程构成，每一个线程可以独立运行，每个进程的线程共享这个进程的地址空间。有多种方法可以实现多线程系统，一种方法是核心级线程，另一种方法是用户级线程，也可以把两者组合起来。

多线程实现的并行避兔了进程间并行的缺点 : 创建线程的开销比创建进程要小，同一进程的线程共享进程的地址空间，所以线程切换 ( 处理器调度 ) 比进程切换快。例如， WindowsServer 内核采用基于优先级的方案选定线程执行的次序。高优先级的线程会比低优先级的线程先执行，内核周期性地改变线程的优先级，以确保所有线程均能执行。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LTEzMDE2YmFlOTQwNDZjZjEucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LTI0OWFiOWYyY2ViZTQ5NjIucG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LWIyNzZmMjUwZWM2NTM3YTUucG5n?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LWZhYzJlOWFhODFkYjliYjIucG5n?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LWU4NGY0Yjg5MjdlOTc5ZDMucG5n?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LWI3NzdlMGMyYTU0YjY0YzQucG5n?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LTcxY2M1Y2FiNmU1ODMyNzUucG5n?x-oss-process=image/format,png
[image.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LWQwN2NkNDgwYmFhZmU5MDQucG5n?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LTc5MzM2NDc0NzlhZTRkZGQucG5n?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LTU3MGJhZTQ2MzZiNGEzZjIucG5n?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LTIwNzNiNjQ2YTJhY2UwODIucG5n?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMzg2MTA4LWNiYjliNTIwODgxZGMwODcucG5n?x-oss-process=image/format,png