计算机操作系统（OS）——P2进程（满满3万字干货）什么？你一电气的想学OS？直接甩给你

1、进程的概念、组成、特征

学习目标：

1.1、进程的概念

__进程（Process）：是__动态的，是程序的一此执行过程。同一个程序多次执行会对应多个进程。

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

思考：操作系统是这些进程的管理者，它要怎么区分各个进程呢？

可以这样：当进程被创建时，操作系统会为该进程分配一个__唯一的、不重复__的“身份证号”——PID（Process ID，进程ID）。

当然操作系统除了记录PID，还记录进程所属用户ID（UID）。

还要记录给进程分配了那些资源（如：分配了多少内存，正在使用那些I/O设备，正在使用那些文件）。

还要记录进程的运行情况（如：CPU使用时间、磁盘使用情况、网络流量使用情况等）。

这些信息都被保存在一个数据结构__PCD（Process Control Block）中，即__进程控制块。

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中。

1.2、进程的组成PCB

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。

1.2.1、进程的组成——程序段、数据段

首先我们先来看一下，程序是如何运行的：

一个__进程实体（进程映像）__由__PCB、程序段、数据段__组成。

进程时动态的，进程实体（进程映像）时静态的。

进程实体可以理解为是进程在动态执行过程当中某一时刻的快照/照片。

进程实体反应了进程在某一时刻的状态（如：x++后，x=2）。

所以进程的组成如下：

PCB、程序段、数据段__三部分组成了“进程实体（进程映像）”__。

引入进程实体的概念后，可把进程定义为：进程__是进程实体的__运行过程，是系统进行__资源分配__和__调度__的一个独立单位。

一个进程被“调度”，就是指操作系统决定让这个进程上CPU运行。

【注】PCB是进程存在的唯一标志！

1.3、进程的特征

程序是静态的，进程是动态的，相比于程序，进程拥有以下特征：

1.4、知识回顾

2、进程的状态与转换、进程的组织

学习目标：

2.1、进程的状态——创建态、就绪态

一个系统中会有多个就绪态的进程，当CPU空闲时，操作系统就会选择一个就绪进程，让该进程上CPU运行。

如果一个进程此时在CPU上运行，那么这个进程处于“运行态”，CPU会执行该进程对应的程序（执行指令序列）。

在进程运行的过程中，可能会__请求等待某个事件的发生。（如等待某种系统资源的分配，或者等待其它进程的相应）。__

在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进行下CPU，并让它进入__“阻塞态”__。

当CPU空闲时，又会选择另一个“就绪态”进程上CPU进行

此时程序运行结束时，一个进程可以执行exit系统调用，请求操作系统终止该进程。

此时该进程会进入__“终止态”__，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。

当终止进程的工作完成之后，这个进程就彻底消失了。

下面再将所有的进程状态串起来看：

进程的状态可以分为三种基本状态和另外两种状态：

进程PCB中，会有一个变量state来表示进程的当前状态。如：1表示创建态、2表示就绪态、3表示运行态…

为了对同一个状态下的各个进程进行统一管理，操作系统会将各个进程的PCB组织起来。

2.2、进程的组织

进程的组织方式有两种：

• 链接方式
• 索引方式

大多数操作系统用的是链接方式。

2.2.1、链接方式

链式方式是指，操作系统会管理一系列的队列，每个队列会指向响应状态的PCB。

2.2.2、索引方式

进程组织总结：

2.3、知识回顾

3、进程控制

学习目标：

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

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

3.1、如何实现进程控制？

实现进程控制，需要“原语”。

原语__是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行__必须一气呵成，不可中断。

思考：为何进程控制（状态转化）的过程要一气呵成？

假设PCB中的变量state表示进程当前所处的状态，1表示就绪态，2表示阻塞态。

现有如下，就绪队列指针和阻塞队列指针：

假设此时进程2等待的事件发生，则操作系统中，负责进程控制的内核程序至少需要做这样两件事：

• 将PCB2的state设为1。
• 将PCB2从阻塞队列放到就绪队列。

但是现在假如完成了第一步将PCB2的state设为1后，收到中断信号，那么PCB2的state=1，但是它却被放在阻塞队列里面了。

所以这就导致了PCB2中变量state所表示的状态和PCB2它所处的队列这两个信息对不上了。

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

3.2、如何实现原语的“原子性”

原语__的执行具有__原子性，即执行过程只能一气呵成，期间__不允许被中断__。

可以用“关中断”指令和“开中断”指令，这两个__特权指令__是实现__原子性__。

我们来看看关中断指令和开中断指令的作用。

比如现在有一段指令：

CPU执行了__关中断指令__之后，就不再例行检查中断信号，直到执行__开中断指令__之后才会恢复检查。

假如现在指令a处有个中断指令，在正常情况下，CPU处理完指令a会自动检查是否有中断指令，检查到有中断指令后，会先执行此特权指令，等特区按指令执行完毕之后再回到原来的指令中继续执行其它指令。

而现在提前执行了关中断指令后，指令a执行完毕后，检查到有中断指令了，但这时不会执行这个特区按指令，而是继续执行指令b…，之后遇见开中断命令，才会执行上面的特权指令。

显然关中断指令和开中断指令都是特权指令。

3.3、进程控制相关的原语

3.3.1、进程创建原语

3.3.2、撤消原语

3.3.3、阻塞原语和唤醒原语

阻塞原语和唤醒原语需要成对使用。

3.3.4、切换原语

3.4、知识回顾

无论那个进程控制原语，要做的无非三类事情：

• 更新PCB中的信息（修改进程状态（state）保存/恢复运行环境）。
• 将PCB插入合适的队列。
• 分配/回收资源。

4、进程通信（IPC）

学习目标：

1、什么是进程间通信？

进程通信（Inter-Process Communication，IPC）是指两个进程之间产生数据交互。

进程间通信需要操作系统的支持！！！

2、为什么进程通信需要操作系统的支持？

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

正是因为进程之间相互独立，因此需要借助操作系统的支持才可以完成进程之间的通信。

下面介绍三种进程间的通信方式，分别是：

• 共享存储。
• 消息传递。
• 管道通信。

4.1、共享存储

共享存储的机制：

各个进程只能访问自己的空间，如果操作系统支持共享存储功能，发起通信的进程可以申请一片__共享存储区__而这个共享存储区也可以被其它进程所共享。

如下图，进程P想要给进程Q传数据，进程P可以先将数据写入到共享存储区里面，接下来进程Q再从此共享存储区读出数据。

【注意】如果多个进程都往这片区域写数据，有可能会导致写冲突和数据覆盖的问题。

所以各个进程之间使用共享存储的方式进行通信的话，那么需要保证各个进程对这个共享存储是__互斥的__。

比如上图，当进程P访问此共享存储时，要求进程Q不能访问此共享存储。

那怎么实现__互斥功能呢？__

答：各个进程可使用操作系统内核提供的同步互斥工具（如P、V操作）。

例如：Linux中，实现共享存储：

第一步：
int shm_open(...);      //发起通信的进程调用shm_open系统调用，申请一片共享内存区。

第二步：
void * mmap(...);       //通过mmap系统调用，将共享内存区映射到进程自己的地址空间。

__基于存储区的共享：操作系统只负责在内存中划出一块共享存储区。数据的形式，存放位置由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种__高级通信。

还有一种__基于存储区的共享：__比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种__低级通信__方式。

4.2、消息传递

__进程间的数据交换以格式化的消息（Message）为单位。__进程通过操作系统提供的“发送消息/接收消息”两个__原语__进行数据交换。

什么叫做格式化的消息？格式化消息由两部分组成：

• 消息头：包含发送进程ID、接收进程ID、消息长度等格式化的信息。
• 消息体：包含具体的一个进程要传送给另一个进程的数据等。

消息传递又分为两类：

• 直接通信方式：消息发送进程要指明接收进程的ID。
• 间接通信方式：通过“信箱”间接地通信。因此又称“信箱通信方式”。

4.2.1、直接通信方式

现在有进程P和进程Q进行通信。

在操作系统内核区域管理着各个进程的PCB，在各个PCB中包含一个消息队列。

比如进程Q中就包含进程Q的消息队列。其它进程要发送给进程Q消息，这些消息都会放在进程Q的消息队列中。

那好，假如现在进程P要给进程Q发消息。

• 首先进程P会在自己的内存空间里面，来完善要发送的信息-msg（消息头，信息体），接下来进程P要使用__发送原语，send(Q,msg)__ ，那这个发送原语会导致操作系统内核接收到这个消息，并且会把刚才的这个消息放在__进程Q__的消息队列中。
• 接下来进程Q运行，进程Q使用__接收原语，receive(P,&msg)__之后，操作系统内核会检查进程Q的PCB中消息队列，并找到相应的消息，然后由操作系统将此消息赋值到进程Q地址中。

总结：直接通信方式，就是点名道姓的信息传递。

4.2.2、间接通信方式

间接通信方式，以“信箱”作为中间实体进行消息传递。

假如现在进程P要和进程Q通信：

• 进程P可以通过系统调用在操作系统中申请一个“信箱”。
• 进程P在自己的内存空间，完善要发送的信息-msg（消息头，信息体），接下来进程P要使用__发送原语，send(A,msg)__ ，往信箱A发送消息msg。
• 接下来进程Q使用__接收原语，receive(A,&msg)__，从信箱A接收消息。那信箱A的消息就会被操作系统复制到进程Q内存空间中。

通常来说操作系统允许多个进程往同一个信箱send消息，也可以多个进程从同一个信箱中reveice消息。

4.3、管道通信

“管道”是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区。

遵循__先进先出（FIFO）。__

管道通信特点：

• 管道只能采用__半双工通信__，某一时间内只能实现单向的传输。如果要实现__双向同时通信（两个进程互相通信）__，则需要设置两个管道。

• 各个进程要__互斥__地访问管道（由操作系统实现）。

• 由于管道是固定大小的，所以当管道读满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。

• 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。

• 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：

  • 第一种解决方案：一个管道只允许多个写进程，一个读进程。（408真题答案）
  • 第二种解决方案：允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据。（Linux方案）

  考试以第一种解决方案为答案。

也许有同学会有疑惑？这个“管道”方式，和共享存储的方式不一样吗？都是由操作系统内核开辟一个共享存储空间。

那二者之间有什么区别呢？

我们说共享存储的方式，是直接一个空间，写入数据时，进程P写数据想写在此空间哪里就写在那里，然后进程Q想在那个位置访问就那个位置访问。

但管道中数据强调的是一个__先进先出__，假如进程P写入数据为a，b，c，那进程读出的数据应该为：a，b，c。

4.4、知识回顾

5、线程概念

学习目标：

5.1、什么是线程？为什么要要引入线程？

引入：我们知道QQ可以视频、文字聊天、传送文件。

进程是程序的一次执行。但是以上QQ功能显然不可能是由一个程序顺序处理就能实现的。

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。

有了线程CPU服务对象就不再是进程了，而是线程。

引入了线程后，线程成为了程序执行流的最小单位。

可以把线程理解为“轻量级进程”。

线程__是一个__基本的CPU执行单元，也是__程序执行流的最小单位__。

引入线程之后，不仅是进程之间可以并发，进程内的__各线程之间__也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频，文字聊天，传文件）。

引入线程后，进程只作为除CPU之外的系统资源的分配单元。

那引入线程机制后，有什么变化呢？

5.2、线程属性

1、线程是处理机调度的单位。

2、多CPU计算机中，各个线程可占用不同的CPU。

3、每个线程都有一个线程ID、线程控制块（TCB）。

4、线程也有就绪、阻塞、运行三种基本状态。

5、线程几乎不拥有系统资源。

6、由于共享内存地址空间，同一进程中的线程间通信甚至无需操作系统干预。

7、同一进程中的线程切换，不会引起进程切换。

8、不同进程中的线程切换，会引起进程切换。

9、切换同进程内的线程，系统开销很小。

10、切换进程，系统开销较大。

6、线程的实现方式和多线程模型

学习目标：

6.1、用户级线程（User-Level Thread，ULT）

用户级线程（User-Level Thread，ULT），历史背景：早期的操作系统（如：早期Unix）只支持进程，不支持线程。当时的“线程”是由线程库实现的。

由于“线程”是由线程库实现的。所以以操作系统的角度来看操作系统直接操作的还是进程。

而程序员写的应用程序当中是使用线程库实现的。

很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能。

由于操作系统只能看见进程，而进程上处理机运行的时候，使用程序员写的线程库，创建了逻辑线程（用户级线程）。

那问题来了：

• 线程的管理工作由谁来完成？

  答：用户级线程的工作是由应用程序通过线程库来完成的，并不是操作系统负责的。

• 线程切换是否需要CPU变态？

  答：线程切换在用户态来完成的。

• 操作系统是否能意识到用户级线程的存在？

  答：操作系统只能看到进程的存在，并不知道线程。

• 这种线程的实现方式有什么优点和缺点？

  • 优点：用户级线程的切换在用户空间即可完成，不需要切换到和心态，线程管理的系统开销小，效率高。
  • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

在这种用户级线程的情况下，CPU的调度基本单位依然是__进程__，操作系统是给进程分配时间的。因此即便我么电脑是多核处理机，但是由于进程才是CPU的调度单位，因此这个进程只能被分配一个核心，所以这些线程并不能并行的运行。

以上是早期的操作系统中实现线程的方式。

这个阶段操作系统还只支持进程，不支持线程。

所以内核级线程诞生。

6.2、内核级线程（Kernel-Level Thread）

“内核级线程”又称“由操作系统支持的线程”。

那内核级线程，就是在操作系统的角度上也能看到此线程。

（大多数现代操作系统都实现了内核级线程，如：Windows，Linux）

同样的也需要思考几个问题：

• 线程的管理工作由谁来完成？

  答：由于此内核级线程是在操作系统层面实现的，因此内核级线程的管理工作需要由操作系统来完成。

• 线程的转换是否需要CPU变态？

  答：既然内核级线程是由操作系统负责管理，那它们的切换肯定需要操作系统接入，因此在进行线程切换的时候，当然需要变态。

• 操作系统是否能意识到内核级线程的存在？

  答：会的。

• 这种线程的实现方式有什么优点和缺点：

  • 优点：如果操作系统支持内核级线程，那在这种操作系统中内核级线程是处理机调度的基本单位。而进程只作为分配资源的基本单位。因此在多核CPU的环境下，这几个内核级线程可以被分别分配到不同的核心下。所以当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
  • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

以上两种进程各有各的优缺点。

那有没有两者结合的线程模型呢？

有，下面介绍。

6.3、多线程模型

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型。

6.3.1、一对一模型

6.3.2、多对一模型

6.3.3、多对多模型

6.4、知识回顾

7、线程的状态与转换

线程的状态我们只关心三个核心状态：就绪、运行、阻塞。

__线程__的组织与转换和__进程__的组织与转换很相似的：

在组织与控制进程的时候，操作系统会对进程的PCB进行管理。

那对于线程来说，想要管理线程，就需要给各个线程建立与之对应的数据结构——TCB（线程控制块）。

线程控制块包含的内容：

线程表：

8、调度

8.1、调度概念、层次

学习目标：

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定__某种规则__来__决定__处理这些任务的__顺序__，这就是“调度”研究的问题。

8.2、调度的三个层次

1、高级调度（作业调度）：

作业：一个具体的任务。

用户向系统提交一个作业__就约等于__用户当操作系统启动一个程序

__高级调度（作业调度）：__按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

2、__低级调度（进程调度/处理机调度）：__按照某种策略从就绪队列中选取一个进程，将处理机分配给他。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。

进程调度的频率很高，一般几十毫秒一次。

3、当内存不够时，可将某些进程的数据调出外存。等内存空间空闲或者进程需要运行时在重新调入内存。

暂时调到外存等待的进程状态为__挂起状态__。被挂起的进程PCB会被组织成__挂起队列__。

__中级调度（内存调度）：__按照某种策略决定将那些处于挂起状态的进程重新调入内存。

8.3、进程的挂起态与七状态模型

暂时调到外存等待的进程状态为__挂起状态__（挂起态，suspend）

挂起态又可以进一步细分为__就绪状态、阻塞状态__两种状态。

五状态模型：

七状态模型：

【注意】：“挂起”和“阻塞”的区别，两种状态都是暂时不能获得CPU的服务，但挂起状态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

有的操作系统会把就绪挂起，阻塞挂起分为两个挂起队列，甚至会把根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

三层调度的联系、对比：

8.4、知识回顾

8.5、进程调度的时机、切换、过程和方式

下面来对__进程调度__进行具体的展开学习。

8.5.1、进程调度的时机

__进程调度（低级调度）：__就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

那什么时候能进行进程调度呢？

进程调度时机分为两大类：

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

什么时候不能进行进程调度与切换的情况？

• 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到中断处理过程中进行进程切换。
• 进程在__操作系统内核临界区__中。（但进程在普通临界区中是可以进行调度、切换的）
  • 《进程在操作系统内核程序临界区中不能进行调度和切换》这种表述方式是对的。
  • 《进程处于临界区时不能进行处理机调度》这种表述方式是错的。
• 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如，之前学习到的修改PCB中进程状态标志，并把PCB放到相应队列）。

什么是临界资源呢？

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

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

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

当一个进程处于内核临界区，并且进程是来访问就绪队列的，那这个进程需要独占式访问，必须给该就绪队列加锁，以防止其他进程入内。

但如果现在该进程还没退出临界区（相当于还没给此就绪队列解锁），那在一些进程调度相关的程序需要使用该就绪队列时，由于其还没解锁的缘故，因此无法顺利的进行进程调度。

所以内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其它管理工作。因此在访问内核程序临界区期间不能进行调度和切换。

那我们再来看看__普通临界区：__

所以说：进程在__操作系统内核临界区__中不可进行调度和切换，但进程在__普通临界区__是可以进行调度、切换的。

8.5.2、进程调度的方式

有的系统中，只允许进程主动放弃处理机。

但在有的系统中，进程可以主动放弃处理机，当有更紧急的任务处理时，也会强行剥夺处理机（被动放弃）。

进程调度的方式分为两种：

• 非剥夺调度方式：

  

• 剥夺调度方式：

  

8.5.3、进程的切换与过程

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

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

__进程切换__是指一个进程让出处理机，由另一个进程占用处理机的过程。

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

进程切换的过程主要完成了：

• 对原来运行进程各种数据的保存。
• 对新的进程各种数据的恢复。（如：程序计数器、程序状态字、各种数据寄存器等处理机现场处理，这些信息一般保存在进程控制块）

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

8.6、调度器、闲逛进程

8.6.1、调度器/调度程序（scheduler）

调度器是操作系统内核重要的程序模块。

②、③由调度器引起，调度程序决定：

• 当谁运行？——调度算法实现。
• 运行多长时间？——时间片大小。

调度时机——什么事件会触发“调度程序”？

• 创建新进程。
• 进程退出。
• 运行进程阻塞。
• I/O中断发生。

8.6.2、闲逛进程

调度程序永远的备胎，没有其它就绪进程时，运行闲逛进程（idle）。

闲逛进程的特性：

• 优先级最低
• 可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）。
• 能耗低

9、调度算法

9.1、调度算法的评价指标

学习目标：

9.1.1、CPU利用率

CPU利用率：指CPU“忙碌”的时间占总时间的比例。

Eg：某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？

9.1.2、系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业。

__系统吞吐量：__单位时间内完成作业的数量。

Eg：某计算机系统处理完10道作业，共花费1000秒，则系统吞吐量为？

9.1.3、周转时间

对于计算机的用户来说，它很关心自己的作业从提交到完成花了多少时间。

__周转时间：是指从__作业被提交给系统开始，到作业完成为止的这段时间间隔。

它包括四个部分：

• 作业在外存后备队列上等待作业调度（高级调度）的时间
• 进程在就绪队列上等待进程调度（低级调度）的时间
• 进程在CPU上执行的时间
• 进程等待I/O操作完成的时间

后三项在一个作业的整个处理过程中，可能发生多次。

思考：有的作业运行时间短，有的作业运行时间长，因此在周转时间相同的情况下，运行时间不同的作业，给用户的感觉肯定是不一样的。

比如，A、B做同一件事总时间为12分钟，A需要等待10分钟，然后2分钟做完事情，而B需要等待2分钟，然后0分钟做完事情。

因此提出另一个指标：

对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。

对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。

带权周转时间和周转时间都是越小越好。

9.1.4、等待时间

计算机用户希望自己的作业尽可能少的等待处理机。

__等待时间：__指进程/作业等待处理机状态时间之和，等待时间越长，用户满意度越低。

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

对于__作业__来说，不仅要考虑__建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。__

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

9.1.5、响应时间

对于计算机用户来说，会希望自己提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。

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

9.1.6、知识回顾

9.2、调度算法（一）

学习目标：

学习各中调度算法的学习思路：

• 算法思想
• 算法规则
• 这种调度算法是用于__作业调度__还是__进程调度__。
• 抢占式？还是非抢占式？
• 优点和缺点
• 是否会导致__饥饿__（饥饿：某进程/作业长期得不到的服务）。

9.2.1、先来先服务（FCFS，First Come First Serve）

先来先服务算法特性：

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

下面来看个例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用__先来先服务__调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。

因此根据到达时间可以得出，调度顺序：P1—>P2—>P3—>P4。

各个指标的计算结果：

9.2.2、短作业优先（SJF，Shortest Job First）

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

例题一（非抢占式）：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用__非抢占式__的__短作业优先__调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

短作业/进程优先调度算法：每次调度时选择__当前已到达__且__运行时间最短__的作业/进程。

因此，调度顺序为：P1—>P3—>P2—>P4。

分析：只有P1的到达时间为0，所以P1先到达，因此P1先调度。当P1运行了7秒后，P2、P3、P4全部都已经达到了，但是P3的运行时间最短，所以P3调度，那P2、P4的运行时间一样，但P2的达到时间短，所以在调度P2，最后调度P4。

各个指标的计算结果：

__例题二（抢占式）：__将上面的题修改为，使用__抢占式__的__短作业优先调度__算法。

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

需要注意的是，当有新进程到达时就绪队列就会改变，就要按照上述规则进行检查。以下Pn(m)表时当前Pn进程剩余时间为m。各个时刻的情况如下：

• 0时刻（P1到达）：P1(7)，此时运行P1进程。
• 2时刻（P2到达）：P1(5)、P2(4)。P2进程到达就绪队列，就绪队列改变，并且此时P1进程还需要运行5个时间，而P2进程需要4个时间，所以P2会抢占P1，所以现在P2上处理机进程运行。
• 4时刻（P3到达）：P1(5)、P2(2)、P3(1)，P3进程又会抢占处理机，所以4时刻，P3进程上处理机运行。
• 5时刻（P3完成且P4刚好到达）：P1(5)、P2(2)、P4(4)，P2进程上处理机运行。

在抢占式的算法中，各个进程的执行时断断续续的。如下图：

所以各个指标的计算结果：

在最短作业优先中，关于抢占式和非抢占式的几个细节：

• 如果题目中为特别说明，所提到的“短作业/进程优先算法”默认是__非抢占式__的。

• 好多书上都会说“SJF（非抢占式）调度算法的平均等待时间、平均周转时间最少”，严格的来说，这个表述是错误的，不严谨的。上面的例子表明，最短剩余时间优先算法（SPF抢占式）得到的平均等待时间、平均周转时间还要更少

  应该加上一个条件：“在所有进程同时可运行时”，采用SJF调度算法的平均等待时间、平均周转时间最少。

  或者说：“在所有进程都几乎同时到达时”，采用SJF调度算法的平均等待时间、平均周转时间最少。

  如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最断剩余时间优先，SRNT算法）的平均等待时间、平均周转时间最少”。

• 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其它算法（如FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间。

• 如果选择题中遇见“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其它选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项。

对FCFS和SJF两种算法的思考

FCFS算法是在每次调度的时候选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。

SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。

既然这样，能不能设计一个算法，即考虑到各个作业的等待时间，也能兼顾运行时间呢？

有：高响应比优先算法（HRRN）。

9.2.3、高响应比优先算法（HRRN）

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

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用__高响应比优先__调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

高响应比优先算法：非抢占式的调度算法，只有当前运行地进程__主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时__计算所有就绪进程的响应比，选响应比最高的进程上处理机。

0时刻：只有P1到达就绪队列，P1上处理机（因为在0时刻，P1就到达，所以不用计算P1的响应比，直接将P1上处理机）。

7时刻（P1主动放弃CPU）：就绪队列中有P2(响应比=(5+4)/4=2.25)，P3(响应比=(3+1)/1=4)，

P4(响应比=(2+4)/4=1.5)。P3的响应比大，所以执行P3进程。

8时刻（P3完成）：P2(2.5)，P4(1.75)。

12时刻（P2完成）：就绪队列只剩下P4，那就不用在计算P4的响应比，直接将P4上处理机执行。

9.2.4、知识回顾

9.3、调度算法（二）

学习目标：

学习各中调度算法的学习思路：

• 算法思想
• 算法规则
• 这种调度算法是用于__作业调度__还是__进程调度__。
• 抢占式？还是非抢占式？
• 优点和缺点
• 是否会导致__饥饿__（饥饿：某进程/作业长期得不到的服务）。

9.3.1、时间片轮转调度算法（RR，Round-Robin）

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

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用__时间片轮转__调度算法，分析时间片大小分别是2、5时的进程运行情况。

时间片轮转法常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间。

时间片大小为2：

0时刻(P1(5))：0时刻只有P1到达就绪队列，让P1上处理机运行一个时间片。

2时刻(P2(4)—>P1(3))：2时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾，此时P2排在对头，因此让P2上处理机。（注意：2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列）。

4时刻(P1(3)—>P3(1)—>P2(2))：4时刻，P3到达，先插到就绪队尾，紧接着，P2下处理机也能插到队尾。

5时刻(P3(1)—>P2(2)—>P4(6))：5时刻，P4到达，插到就绪队尾（注意：由于P1的时间片还没用完，因此暂时不调度。另外，此时P1处于运行态，并不在就绪队列中）。

6时刻(P3(1)—>P2(2)—>P4(6)—>P1(1))：6时刻，P1时间片用完，下处理机，重新放回就绪队尾，发生调度。

7时刻(P2(2)—>P4(6)—>P1(1))：虽然P3的时间片还没用完，但是由于P3只需要运行1个单位的时间，运行完了会主动放弃处理机，因此也会发生调度。对头进程P2上处理机。

9时刻(P4(6)—>P1(1))：进程P2时间片用完，并刚好运行完，发生调度，P4上处理机。

11时刻(P1(1)—>P4(4))：进程P4时间片用完，重新回到就绪队列。P1上处理机。

12时刻(P4(4))：P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机。

14时刻()：就绪队列为空，因此让P4接着运行一个时间片。

16时刻()：所有进程运行结束。

时间片大小为5：

如果我们使用先来先服务(FCFS)调度算法，得到各进程的运行情况：

会发现，使用FCFS和时间片轮换算法基本一样（唯一区别：时间片轮换算法在15个时间处会在检查一下，二FCFS没有）。

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

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

9.3.2、优先级调度算法

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

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用__非抢占式__的__优先级调度算法__，分析进程运行情况。（注：优先数越大，优先级越高）

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

• 0时刻（P1）：只有P1到达，P1上处理机。
• 7时刻（P2、P3、P4）：P1运行完成主动放弃处理机，其余进程都已到达，P3优先级最高，P3上处理机。
• 8时刻（P2、P4）：P3完成，P2、P4优先级相同，由于P2先到达，因此P2优先上处理机
• 12时刻（P4）：P2完成，就绪队列只剩P4，P4上处理机。
• 16时刻（）：P4完成，所有进程都结束。

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用__抢占式__的__优先级调度算法__，分析进程运行情况。（注：优先数越大，优先级越高）

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

• 0时刻（P1）：只有P1到达，P1上处理机。
• 2时刻（P2）：P2到达就绪队列，优先级比P1更高，发生抢占。P1回到就绪队列，P2上处理机。
• 4时刻（P1、P3）：P3到达，优先级比P3更高，P2回到就绪队列，P3抢占处理机。
• 5时刻（P1、P2、P4）：P3完成，主动释放处理机，同时，P4也到达，由于P2比P4更先进入就绪队列，因此选择P2上处理机。
• 7时刻（P1、P4）：P2完成，就绪队列只剩下P1、P4，P4上处理机。
• 11时刻（P1）：P4完成。P1上处理机。

【补充】：

• 就绪队列未必只有一个，可以把按照不同的优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。
• 根据优先级是否可以动态改变，可将优先级分为__静态优先级__和__动态优先级__两种。
  • 静态优先级：创建进程时确定，之后一直不变。
  • 动态优先级：创建进程时有一个初始值，之后会很据情况动态的调整优先级。

【思考一】：如何合理地设置各类进程地优先级？通常：

• 系统进程优先级__高于__用户进程。
• 前台进程优先级__高于__后台进程。
• 操作系统更__偏好I/O型进程（或称I/O繁忙型进程）__。

注：与I/O型进程相对地是计算型进程（或称CPU繁忙型进程）。

为什么操作系统更偏好于__偏好I/O型进程__而不是__CPU繁忙型进程__？

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

【思考二】：如果采用是动态优先级，什么时候应该调整？

? 答：可以从追求公平，提升资源利用率等角度考虑：

• 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级。
• 如果某进程占用处理机运行了很长时间，则可适当降低其优先级。

9.3.3、思考

FCFS算法的优点是公平

SJF算法的特点是能尽快处理完短作业，平均等待/周转时间等参数很优秀。

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

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

那能否对其它算法做个折中权衡？得到一个综合表现优秀平衡地算法呢？

有——多级反馈队列调度算法。

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

例题：各进程到达就绪队列的时间、需要地运行时间如下表所示。使用__多级反馈队列__调度算法，分析进程运行地过程。

队列和时间片如下：

解题步骤：

• 时刻0：P1到达时间为0，所以P1先被放入第1级队列，然后分配时间片，由于第1级队列的时间片为1，P1用完时间片进程还未结束，则P1进入下一级队列队尾。

• 时刻1：P2到达，此时P2调到到第1级队列，由于P2在高级的队列中，所以暂不考虑P1的处理。因此P2上处理机运行，同样的P2的时间片大小也是1，此时间片用完后，P2进入到下一队列中。如下：

  

• 此时第1级队列没有进程了，只有第2级有进程，并且P3没到达，所以处理第2级队列的进程。现在第2队列的时间片大小为2，所以P1运行此时间片，并且运行完此时间片后，P1还没运行完，则P1到第3级队列。然后P2分配时间片2，但这里由于P2还没运行完，P3就到达了，并且P3在第1级队列中，由于第1级的队列优先级高，会出现抢占时间片，所以需要先给P3分配时间片。

• P3所处的时间片为1，正好P3进程执行结束。

• 然后接下来运行P2，由于前面已经运行了P2的2个时间片，现在P2处于时间片为2的第二队列中，所以P2执行完毕。

• 现在只有P1进程，然后分配P1时间片，直到P1执行结束。

9.3.4、知识回顾

【注】：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统( 包括
分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也
能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。( 比如UNIX使用的就是多级反馈
队列调度算法)

9.4、调度算法（三）多级队列调度

系统中按进程类型设置多个队列，进程创建成功后插入某个队列。

队列之间可采取固定优先级，或时间片划分：

• 固定优先级：高优先级空时低优先级进程才能被调度。

• 时间片划分：如三个队列分配时间50%，40%，10%。

各队列可采用不同的调度策略，如：

• 系统进程对列采用优先级调度。
• 交互式队列采用RR。
• 批处理队列采用FCFS。

10、进程同步、互斥

10.1、什么是进程同步？

知识点回顾：进程具有__异步性__的特性。异步性是指，各并发执行的进程已各自独立的、不可预知的速度向前推进。

我们先来看个例子：上面学习到的，进程通信——管道通信

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据”—>“读数据”的顺序来执行的。

如何解决这种__异步__问题，就是”进程同步“所讨论的内容。

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

10.2、什么是互斥？

进程的”并发“需要”共享“的支持。各个并发执行的进程不可避免的需要共享一些系统资源（比如内存，又比如打印机，摄像头这样的I/O设备）。

在前面我们也学习到两种资源共享方式：

我们把__一个时间段内只允许一个进程使用__的资源称为__临界资源__。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区都属于临界资源。

对临界资源的访问，必须__互斥__地进行。互斥，亦称__间接制约关系__。

__进程互斥__指当一个进程访问某临界资源时，另一个想要访问该临界资源地进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

注意：

• 临界区是进程中访问临界资源的代码段。
• 进入区和退出区是负责实现互斥的代码段。
• 临界区也可称为”临界段“。

如果一个进程暂时不能进入临界区，那么该进程是否应该一直占着处理机？该进程有没有可能一直进不了临界区？

以上问题都是要实现进程互斥要解决的问题。

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

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

知识回顾：

10.3、进程互斥的软件实现方法

学习目标：

学习提示：

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

10.3.1、如果没有进程互斥？

先调度A上处理机运行

当A在使用打印机的过程中，分配给它的时间片用完了，接下来操作系统B让它上处理机运行进程B也在使用打印机。

结局：A、B的打印内容混在一起。

如何实现进程互斥？

10.3.2、单标志法

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

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

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

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

代码分析：

? turn的初始值为0，即刚开始只允许0号进程进入临界区。

? 若P1先上处理机运行，则会一直卡在⑤。知道P1的时间片用完，发生调度，切换P0上处理机运行。

? 代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即使切换回P1，P1依然会卡在⑤。

? 只有P0在退出区将turn改为1后，P1才能进入临界区。

因此，该算法可以实现__同一时刻最多只允许一个进程访问临界区。__

单标志法，只能按P0—>P1—>P0—>P1…这样轮流访问。这种必须”轮流访问“带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问（因为无法执行turn = 1这步操作）。

因此，__单标志法__存在的问题是：违背“空闲让进”原则。

10.3.3、双标志先检查法

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

进入临界区代码：

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

//P0进程：
while (flag[1]);         ①
flag[0] = ture;          ②
critical section;        ③  
flag[0] = flase;         ④         
remainder section;


//P1进程：
while (flag[0]);       ⑤ //如果此时P0想进入临界区，P1就一直循环等待
flag[1] = ture;        ⑥ //标记为P1进程想要进入临界区
critical section;      ⑦ //访问临界区
flag[1] = flase;       ⑧ //访问完临界区，修改标记为P1不想使用临界区       
remainder section;

此算法在进程P0和P1并发执行时，会出现错误，如下分析：

首先P0执行①，跳出while循环，然后执行②，表明P0想要访问临界资源，执行②后，发生进程切换，P1开始执行⑤，跳出while循环，然后执行⑥，表明P1想要访问临界资源，然后在执行⑦，P1开始访问临界区。此时在发生进程切换，执行P0中的③，P0开始访问临界区。可以看到P0，P1都要访问临界区。所以问题出现。

因此，双标志检查法的主要问题是：违反“忙则等待”原则。

原因在于，__进入去__的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

10.3.4、双标志后检查法

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

代码实现：

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

//P0进程：
flag[0] = ture;          ①
while (flag[1]);         ②
critical section;        ③  
flag[0] = flase;         ④         
remainder section;


//P1进程：
flag[1] = ture;        ⑤ //标记为P1进程想要进入临界区
while (flag[0]);       ⑥ //如果此时P0想进入临界区，P1就一直循环等待
critical section;      ⑦ //访问临界区
flag[1] = flase;       ⑧ //访问完临界区，修改标记为P1不想使用临界区       
remainder section;

但双标志后检查法依然有问题：

若按照①⑤②⑥…的顺序执行，P0和P1将都无法进入临界区。

因此，双标志后检查法虽然__解决了”忙则等待“的问题，但是又__违背了”空闲让进“和”有限等待“原则，会因各进程都长期无法访问临界资源而__产生”饥饿“__现象。

两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

10.3.5、Peterson算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试”孔融让梨“。做一个有礼貌的进程。

代码实现：

bool flag[2];       //表示进入临界区意愿的数组，初始值都是false
int turn = 0;

//P0进程：
flag[0] = ture;                  ①
turn = 1;                        ②
while (flag[1] && turn == 1);    ③
critical section;                ④
flag[0] = false;                 ⑤
remainder section;

//P1进程：
flag[1] = ture;                  ⑥//表示自己想进入临界区
turn = 0;                        ⑦//可以优先让对方进入临界区
while (flag[0] && turn == 0);    ⑧//对方想进，且最后一次是自己”让梨“，那自己就循环等待
critical section;                ⑨
flag[1] = false;                 ⑩//访问完临界区，表示自己已经不想访问临界区了
remainder section;

按照这种方法，可以动手推导，按照不同的顺序穿插执行会发生什么？

• ①②③⑥⑦⑧
• ①⑥②③
• ①③⑥⑦⑧
• ①⑥②⑦⑧

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然__未遵循让权等待__的原则。

Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

10.3.6、知识回顾

10.4、进程互斥的硬件实现方法

学习目标：

学习提示：

• 理解各方法的原理。
• 了解各方法的优缺点。

10.4.1、中断屏蔽方法

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

优点：简单、高效。

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

10.4.2、TestAndSet指令

简称TS指令、也有地方称为TestAndSetLock指令，或TSL指令。

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

代码分析：

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

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

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

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

10.4.3、Swap指令

也叫Exchange指令，或简称XCHG指令。

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

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

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

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

10.4.4、知识回顾

10.5、锁🔒

1、互斥锁

解决临界区最简单的工具就是__互斥锁（mutex lock）__。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。

每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁时可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，直到锁被释放。

如下代码：

acquire()
{
    while(!available);          //忙等待
	available = false;          //获得锁
}

realses()
{
    available = ture;           //释放锁
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是”忙等待“，当有一个进程在临界区中，任何其它进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其它线程的执行。

需要连续循环忙等的互斥锁，都可称为__自旋锁（spin lock）__，如TSL指令，Swap指令，单标志法。

互斥锁特性：

• 需要忙等但不会一直忙等，进程时间片用完才下处理机，违反“让权等待”。
• 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低。
• 常用于多处理器系统，一个核忙等，其它核照常工作，并快速释放临界区。
• 不太适用于单处理即系统，忙等的过程中不可能解锁。

10.6、信号量机制

学习目标：

复习回顾+思考：之前学习的这些进程互斥的解决方案分别存在哪些问题？
进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）

进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）

1、在双标志发先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题。

2、以上所有解决方案都无法实现__让权等待__。

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制。

10.6.1、信号量机制实现

用户进程可以通过使用操作系统提供的__一对原语（关中断/开中断指令）__来对__信号量__进行操作，从而很方便的实现进程互斥、进程同步。

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

为什么使用原语呢？因为软件解决方案的主要问题是由“进入区的检查和上锁操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，是这些操作能“一气呵成”就能避免问题。

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

wait和signal原语常__简称为P、V操作__（来自荷兰语proberen和verhogen）。因此，做题的时候常把wait(S)，signal(S)两个操作分别为P(S)、V(S)。这对原语可用于__实现系统资源的“申请”和“释放”。__

上面提到过一句话可以是一个整数，也可以是更复杂的记录型变量。

因此信号量分为两类：

• 整数信号量。
• 记录型变量。

10.6.2、整型信号量

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

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

Eg：某计算机系统中有一台打印机。

wait和signal原语代码如下：

int S = 1;        //初始化整型信号量S，表示当前系统中可用的打印机资源数

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

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

上面wait原语中解决了“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。

存在的问题：不满足“让权等待”原则，会发生“忙等”。

信号量代码如下：

//进程P0

...
wait(S);            //进入区，申请资源
使用打印机资源...     //临界区，访问资源
signal(S);         //退出区，释放资源
...

10.6.3、记录型信号量

上面的整型信号量，有个缺点：不满足“让权等待”原则，会发生“忙等”。因此人们又提出__记录型信号量__，即用记录型数据结构表示的信号量。

记录型信号量的定义：

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

wait和signal原语的定义：

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


//进程使用完资源后，通过signal原语释放
void signal(semaphore S)
{
    S.value++;
    if (S.value <= 0)
    {
//释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态（因为当前的进程释放了一个资源，所以使用wakeup唤醒一个进程并将此进程使用刚释放的资源。）
        wakeup(S.L);
    }
}

我们来看个具体的例子：

Eg：某计算机系统中有2台打印机…，则可在初始化信号量S时将S.value的值设为2，队列S.L设置为空。

• 先将资源数设置为2：

  

• 然后各个进程调用原语：

  

【重点总结】

• 一个信号量对应一种资源，value值代表资源个数。

• 信号量的值=这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）。

• P(S)——申请一个资源S，如果__资源不够就阻塞等待__。

• V(S)——释放一个资源S，如果有进程在等待该资源，则__唤醒一个进程__。

10.6.4、知识回顾

【注】若考试中出现P(S)，V(S)的操作，除非特别说明，否则默认S为记录型信号量。

10.7、用信号量机制实现进程互斥、同步、前驱关系

学习目标：

10.7.1、信号量机制实现进程互斥

系统当中的某一些资源是必须互斥访问的，而访问这种系统资源的那段代码叫做临界区。

信号量机制实现进程互斥步骤：

• 分析并发进程的关键活动，划定临界区（如：队临界区资源打印机的访问就应放在临界区）。
• 设置__互斥信号量__mutex，初值为1。我们可以将信号量mutex表示“进入临界区的名额”。
• 在进入区P(mutex)——申请资源。
• 在退出区V(mutex)——释放资源。

代码如下：

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

//进程1
P1()
{
    ...
    P(mutex);                   //执行P操作，使用临界资源前需要枷锁
    临界区代码
    V(mutex);                  //执行V操作，使用临界资源后需要解锁
    ...
}

//进程2
P2()
{
    ...
    P(mutex);                   //执行P操作，使用临界资源前需要枷锁
    临界区代码
    V(mutex);                  //执行V操作，使用临界资源后需要解锁
    ...
}

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

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

10.7.2、信号量机制实现进程同步

进程同步：要让各并发进程按要求有序地推进。

比如，有如下两段代码：

比如，P1、 P2并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。
若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”-定是在“代码2”之后才会执行。

这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

用信号量实现进程同步：

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

【技巧】前V后P。

我们就以前面的问题：若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行。

来实现信号量机制实现同步：

//信号量S代表“某种资源”，刚开始是没有这种资源的（所以初始值为0）。P2需要使用这种资源，而又只能由P1产生这种资源。
semaphore S = 0;


P1()
{
    代码1;
    代码2;
    V(S);        
    代码3;
}
//若先执行到V(S)操作，则S++后S=1。之后当执行到P(S)操作时，由于S=1，表示有可用资源，会执行S--，S的值变回0，P2进程不会执行block原语（代表解锁），而是继续往下执行代码4。

//由V(S)--->P(S)是资源释放的过程

P2()
{
    P(S);
    代码4;
    代码5;
    代码6;
}

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

10.7.3、信号量机制实现前驱关系

__前V后P__的详细说明。

进场P1中有句代码S1，P2中有句代码S2，P3中有句代码S3，…，P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行：

其实每一对前驱关系都是一个进程同步问题（需保证一前一后的操作）。

因此：

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

10.7.4、知识回顾

10.8、经典同步、互斥原理

10.8.1、生产者—消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）生产者、消费者共享一个初始化为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须阻塞等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须阻塞等待。

缓冲区是临界资源，各进程必须互斥的访问。

为什么必须互斥的访问缓冲区？如下图分析：

PV操作题目分析步骤：

• tip1：关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

• tip2：整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

  

  full和empty是同步信号量，是用来解决同步问题的。当然我们还需要一个互斥信号量mutex，用来实现互斥。

• tip3：设置信号量。并根据题目条件确定信号量初值。（互斥信号量mutex初始值一般为1，同步信号量的初始值要看对应资源的初始值是多少）。

  设置的信号量如下：

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

那如何实现同步、互斥呢？如下代码：

semaphore mutex = 1;           //互斥信号量，实现对缓冲区的互斥访问。

semaphore full = 0;           //同步信号量，表示产品的数量，也即非空缓冲区的数量。

semaphore empty = n;          //同步信号量，表示空闲缓冲区的数量。

//生产
product()
{
    while(1)
    {
        生产一个产品;
        P(empty);     //生产一个产品，就消耗一个空闲缓冲区
        P(mutex);     //实现互斥功能，对临界区上锁
        把产品放入缓冲区;
        V(mutex);     //实现互斥功能，对临界区解锁        并且实现互斥是在同一进程中进行一对PV操作
        V(full);     //把产品放入缓冲区，就增加一个产品
    }
}

//消费
consumer()
{
    while(1)
    {
        P(full);         //消耗一个产品（非空缓冲区）
        P(mutex);       //互斥访问
        从缓冲区取出一个产品;
        V(mutex);       //互斥访问
        V(empty);       //增加一个空闲缓冲区
        使用产品;
    }
}

实现同步的重要步骤就是：product()里面的 V(full);执行完毕和consumer()里面的P(full);对接。

【思考一】能否改变相邻P、V操作的顺序呢？

答案：P操作不能！而V操作可以。

改变P操作的顺序导致的问题

若此时缓冲区已经放满产品，则empty=0，full=n。

则生产者进程执行①使mutex变为0，在执行②（消耗一个空闲缓冲区），因此生产者被阻塞。由于生产者被阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没解锁临界资源，因此消费者也被阻塞。

这就造成了生产者等待消费者释放空闲资源(V(empty))，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。

同样的，若缓冲区中没有产品，即full=0，empty=n。按③④①的顺序执行就会发生死锁。因此，实现互斥的操作一定要在实现同步的P操作之后。

而V操作不会导致进程阻塞，因此__两个V操作顺序可以交换__。

总结：

• 生产者消费者问题是一个互斥、同步的综合问题。
• 难点是如何发现题目中隐含的两对同步关系：
  • 有时候是消费者需要等待生产者生产。
  • 有时候是生产者要等待消费者消费。
  • 以上两个是不同“一前一后”的问题，因此也需要设置两个同步信号量。但对这两个信号量的操作都是__前V后P__。

【易错点】实现互斥和实现同步的两个P操作的先后顺序（死锁问题）。

10.8.2、多生产者—多消费者

问题描述：桌子上有一只盘子，每次只能向其中放入- -个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放
橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才
可向盘子中放-一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
用PV操作实现上述过程。

1、关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

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

• 同步关系（一前一后）：

  • 父亲将苹果放入盘子后，女儿才能取苹果。
  • 母亲将橘子放入盘子后，儿子才能取出橘子。
  • 只有__盘子为空__时，__父亲和母亲__才能放入水果。

  “盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果。

2、整理思路。根据各进程地操作流程确定P，V操作的大致顺序。

遵循前V后P的操作

3、设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。

具体的代码实现：

semaphore mutex = 1;         //实现互斥访问盘子（缓冲区）
semaphore apple = 0;         //盘子中有几个苹果
semaphore orange = 0;        //盘子中由几个橘子
semaphore plate = 1;         //盘子中还可以放多少个水果

实现同步的过程：

实现互斥的过程：

【思考一】不要互斥信号量可以吗？（也就是只有同步的情况）

分析：刚开始，儿子，女儿进程即使上处理机运行也是被阻塞（因为刚开始apple/orange都为0）。如果刚开始是父进程线上处理机运行，则：父亲P(plate)是可以访问盘子的（因为plate初始值为1），而在父亲访问盘子之后，母亲在访问盘子P(plate)，由于plate=0了，所以母亲进程被阻塞。之后父亲进程放入苹果V(apple)，女儿进程被唤醒，其它进程即使运行也会阻塞，暂时不可能访问临界资源（盘子）。之后女儿进程访问盘子V(plate)，那plate会+1，所以此时等待盘子的母亲进程被唤醒，之后母亲进程访问盘子，但其它进程暂时无法访问临界资源（盘子）…

__结论：__即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问临界资源（盘子）的现象

__原因：__本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞（意思就是最多只有一个进程可以执行操作，其它进程都在阻塞，所以不存在第二个进程和这个进程抢临界资源），所以可以顺利的进入临界区。

但如果盘子的容量为2呢？

分析：女儿和儿子进程都先阻塞。父亲进程可以访问盘子（临界资源）P(plate)，这个时候母亲进程也可以P(plate)，可以访问盘子（临界资源），父亲往盘子里面放苹果，同时母亲也可以往盘子里面放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。

__结论：__如果缓冲区大小大于1，就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。

知识回顾：

• 解决“多生产者—多消费者问题”的关键在于理清复杂的同步关系。
• 在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。

比如，如果__从单个进程行为的角度来考虑的话__，我们会有以下结论：

• 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果。
• 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果。

这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？如下图：

其实不然，正确的分析方法应该__从“事件”的角度来考虑__，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”。

盘子变空事件—>放入水果事件。“盘子变空事件”即可由儿子引发，也可由女儿引发。“放水果事件”即可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。如下图：

10.8.3、吸烟者问题

问题描述：

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷
起并抽掉一支烟， 抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第

二个拥有纸、第三个拥有胶水（所以每个抽烟者都缺少两种材料）。供应者进程无限地提供三种材

料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它， 并给

供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复

(让三个抽烟者轮流地抽烟)

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

1、关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

明明桌子上放两种材料，为什么说桌子可以抽象为__容量为1__的缓冲区呢？其实这里的容量为1，不是是一种材料，而是一组材料：

• 组合一：纸+胶水
• 组合二：烟草+胶水
• 组合三：烟草+纸

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

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

2、整理思路并设置信号量。根据各进程的操作流程确定P、V操作的大致顺序

• 同步操作：前V后P。

  四种同步关系的信号量如下设置：

  

• 互斥操作：由于缓冲区的大小为1，所以即使不设置互斥变量也无关紧要

具体代码如下：

知识回顾：

• 吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。
• 值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，注意体会我们是如何用一个整型变量i实现这个“轮流”过程的。
• 若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的“事件”发生之后的位置。

10.8.4、读者—写者问题

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

因此要求：

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

1、关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

• 两类进程：写进程、读进程
• 互斥关系：写进程—写进程，写进程—读进程。读进程与读进程不存在互斥问题。

2、整理思路。根据各进程的操作流程确定P、V操作的大致顺序

3、设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

具体代码实现：

以上代码可以实现多个读者同时读数据，一个写者写数据。

但以上程序也存在问题。

【思考】：若两个读进程并发执行，则count=0时两个进程也许都能满足if条件，都会执行P(rw)，从而使第二个读进程阻塞的情况。

如何解决：出现上述问题的__原因在于对count变量的检查和赋值无法一气呵成__，因此可以设置另一个互斥信号量来保证各读进程对count的访问互斥的。

算法改进（在添加一对互斥信号量mutex）：

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

算法改进（在添加一对互斥信号量w）：

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

知识回顾：

• 读者—写者问题为我们解决复杂的互斥问题提供了一个参考思路。
• __核心思想__在于设置一个__计数器count__用来记录当前正在访问共享文件的读进程数。我们可以使用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
• 另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果__需要实现“一气呵成”，自然而然地想到互斥信号量__。
• 最后，还要认真体会是如何解决“写进程饥饿”问题的。

10.8.5、哲学家进餐问题

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

1、关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中中间筷子的访问是互斥的。

2、整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能吃饭。如何避免临界资源分配不当造成的__死锁现象__，是哲学家问题的精髓。

3、信号量设置。定义互斥信号量数组chopstick={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

具体代码实现：

以上代码看似可以实现哲学家吃饭问题，但实际不对。

分析：5个哲学家是可以正常拿起左筷子的（也就是说可以正常执行P(chopstick[i])），但是5个哲学家都不能拿起它们的右筷子，因为相邻哲学家的右筷子就是相邻哲学家的左筷子，而左筷子依然被申请使用了，所以P(chopstick[(i+1)%5])不能正确执行。

由于每位哲学家循环等待右边的人放下筷子（阻塞）。发生“死锁”。

那如何防止死锁的发生呢？

tip1：可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。

tip2：要求奇数号哲学家先拿左边筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿到第一只筷子，另一个会直接阻塞。这就避免了占有一支后在等待另一只的情况。

tip3：仅当一个哲学家左右两只筷子都可用时才允许它抓起筷子。

我们对tip3来实现个代码：

我们来分析一下过程：

首先哲学家0先拿其左右筷子，然后执行V(mutex)和吃饭过程，之后哲学家4开始拿筷子，首先可以顺利通过P(mutex)然后由于哲学家4是可以拿左筷子的，但是哲学家4的右筷子被哲学家0所拿了，因此哲学家4发生阻塞。

【注意】：此时哲学家4是可以拿到一根筷子的，所以说我们在说tip3（仅当一个哲学家左右两只筷子都可用时才允许它抓起筷子）是不准确的，哲学家也可被允许拿到一根筷子。

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

知识回顾：

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

如果在题中遇见一个进程需要同时持有对各临界资源的情况，应该参考哲学家问题的思想。分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

可以参考哲学家就餐问题解决死锁的三种思路。

11、管程

学习目标：

为什么要引入管程？

信号量机制存在的问题：编写程序困难，易出错。

那能不能设计一种机制，让程序员写程序时不需要再关注复杂的P、V操作，当写代码更轻松呢？
1973年，Brinch Hansen首次在程序设计语言（Pascal）中引入了“管程”成分——一种高级同步机制。

11.1、管程的定义和基本特征

管程和之前学习过的P、V操作一样是用来实现进程的互斥和同步的。

管程是一种特殊的软件模块、有以下部分组成：

• 局部于管理的__共享数据结构__（生产者和消费者之间共享访问的缓冲区）说明；
• 对该数据结构进行操作的__一组过程/一组函数__；（过程就是函数）
• 对局部于管程的共享数据设置初始值的语句；（简而言之就是而缓冲区的一些初始化）
• 管程有一个名字。

管程的特征：

• 局部于管程的数据只能被局部于管程的过程所访问。
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。（简而言之就是管程中的数据结构只能被管程中的函数所修改）。
• 每次仅允许一个进程在管程内执行某个内部过程。（保证了某个时刻只能一个进程访问共享资源。不存在多个进程同时访问此共享资源）。

11.2、用管程解决生产者消费者问题

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

1、需要在管程中定义共享数据（如生产者消费者问题的缓冲区）。

2、需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者—消费者问题中，可以定义一个函数（上图中的insert函数）用于将产品放入缓冲区，再定义一个函数（上图中的remove函数）用于从缓冲区取出产品）。

3、只能__通过这些特定的“入口”才能访问共享数据__。

4、管程中有很多“入口”，但是__每次只能开放其中一个“入口”，并且__只能让一个进程或线程进入（如生产者和消费者问题中，各进程需要互斥的访问共享缓冲区。管程的这种特性即可保证一个时间段最多只会有一个进程在访问缓冲区。注意：这种互斥性是由编译器负责实现的，程序员无需关心）。

5、可在管程中设置__条件变量及等待/唤醒操作__以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

11.3、Java中类似于管程的机制

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

11.4、知识回顾

12、死锁

学习目标：

__死锁：__在并发环境下，各进程因竞争资源而造成的一种__互相等待对方手里的资源，导致个进程都阻塞，都无法向前推进__的现象，就是“死锁”，发生死锁后若无外力干涉，这些进程都将无法向前推进。

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

• 死锁：各个进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推荐的现象。
• 饥饿：由于长期得不到想要的资源，某进程无法向前推进的想象。比如：在短进程优先（SPF）算法中，若有渊源不断的段进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
• 死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

总结为表格，如下：

死锁产生的必要条件：

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

• __互斥条件：__只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
• __不可剥夺条件：__进程所获得的资源在未使用之前，__不能有其他进程强行夺走，__只能主动释放。
• __请求和保持条件：__进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其它进程占有，此时请求被阻塞，但又对自己已有的资源__保持__不放。
• __循环等待条件：存在一种进程__资源的循环等待链，链中的每一个进程以获得的资源同时被下一个进程所请求。

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

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

什么时候发生死锁呢？

• 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
• 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发性执行的进程P1、P2分别申请并占有了资源的R1、R2，之后进程P1有紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有阻塞，从而发生死锁。
• 信号量使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（也可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）。

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

死锁的处理策略：

• 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
• 避免死锁。用某种算法防止系统进入不安全状态，从而避免死锁（银行家算法）。
• 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

知识回顾：

12.1、死锁的处理策略——预防死锁

学习目标：

预防死锁的主要思想是：想办法破坏死锁产生的四个条件。

下面我们就来逐个分析以上四个死锁产生的条件，那个适合破坏。

12.1.1、破快互斥条件

__互斥条件：__只有对必须互斥使用的资源的争抢才会导致死锁。

破坏互斥条件：如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备…

该策略的__缺点__：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

12.1.2、破坏不剥夺条件

__不剥夺条件：__进程所获得的资源在未使用完之前，不能由其它进程强行夺走，只能主动释放。

破坏不剥夺条件：

• 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
• 方案二：当某个进程需要的资源被其它进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑个进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）。

该策略的缺点：

• 实现起来比较复杂。
• 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
• 反复的申请和释放资源会增加系统开销，降低系统吞吐量。
• 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

12.1.3、破坏请求和保持条件

__请求和保持条件：进程__已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其它进程占有，此时请求进程被阻塞，但又对自己有的资源保持不放。

破坏请求和保持条件：可以采用__静态分配方法__，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会在请求别的任何资源了。

该策略实现起来简单，但也有明显的__缺点__：

• 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率低。另外，该策略也有可能__导致某些进程饥饿__。

  

12.1.4、破坏循环等待条件

__循环等待条件：存在一种进程__资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

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

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

假设系统中共有10个资源，编号1，2，3…10

如果P3进程要申请的资源是8，9，10那P3肯定不会阻塞。

该策略的缺点：

• 不方便增加新的设备，因为可能需要重新分配所有的编号。
• 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费。
• 必须按规定次序申请资源，用户编程麻烦。

12.1.5、知识回顾

12.2、死锁的处理策略——避免死锁

学习目标：

12.2.1、什么是安全序列？

__安全序列：就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是__安全状态。当然，安全序列可能有多个。

但如果分配了资源之后，系统中找不出任何一个安全序列，系统就会进入了__不安全状态__。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那__系统也有可能重新回到安全状态，__不过我们在分配资源之前总是要考虑到最坏的情况。

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

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

12.2.2、银行家算法

银行家算法是荷兰学者Dijkstra为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用来在操作系统中，用于__避免死锁__。

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

【思考】计算机系统中会有各种各样的资源，应该怎么把算法拓展为多种资源的情况呢？
可以把单维的数字拓展为多维的向量。比如：系统中有5个进程P0_{P4，3种资源R0}R2，初始数量为(10,5,7)，则某一时刻的情况可表示如下：

此时系统是否处于安全状态？

思路：尝试找出一个安全状态…

以此检查剩余可用资源(3,3,2)是否能满足个进程的需求。

__第一轮检查：__可满足P1需求，将P1加入安全序列，并更新剩余可用资源值为(5,3,2)。

__第二轮检查（P1不检查）：__可满足P3需求，将P3加入安全序列，并更新剩余可用资源值为(7,4,3)

…

以此类推，共5次循环检查即可将5个进程都加入安全序列中，最终可得一个安全序列。该算法称为__安全性算法__。可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查。

实际做题时可以更快速的得到安全序列：

经过对比发现（3,2,2）可满足P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次被满足的，因此P1、P3一定可以顺利的执行完，并归还资源，可把P1、P3先加入安全序列。

并且此时剩余资源：(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)。

然后可以发现剩余的P0、P2、P4都可被满足。同理，这些进程都可以加入安全序列。

于是，5个进程全部加入安全序列，说明此时系统__处于安全状态__，暂__不可能发生死锁__。

银行家代码实现

假设系统中有n个进程，m种资源。

每个进程在运行前先声明对各种资源的最大需求数，则可用一个n*m的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不访问称为__最大需求矩阵Max__，Max[i,j]=k表示进程Pi最多需要K个资源Rj（最大需求）。同理，系统可以用一个n*m的__分配矩阵Allocation__表示对所有进程的资源分配情况。

Max-Allocation=Need矩阵，表示各进程最多还需要多少各类资源。另外，还需要用一个__长度为m的一维数组Available__表示当前系统中还有多少可用资源。

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

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

• ①如果Request[j] <= Need[i,j]（0<=j<m） 便转向②；否则认为出错。
• ②如果Request[j]<=Available[j]（0<=j<m），便转向③；否则表示尚无足够资源，Pi必须等待。
• 系统试探着把资源分配给进程Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判）：
  • Available = Available - Request；
  • Allocation[i,j] = Allocation[i,j] + Request[j];
  • Need[i,j] = Need[i,j] - Request[j];
• 操作系统执行__安全性算法__，检查此次资源分配后，系统__是否处于安全状态__。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。④、⑤、⑥，

银行家算法总结：

• 数据结构：
  • 长度为m的一-维数组Available表示还有多少可用资源
  • n*m矩阵Max表示各进程对资源的最大需求数*
  • n*m矩阵Allocation表示已经给各进程分配了多少资源
  • Max-Allocation=Need矩阵表示各进程最多还需要多少资源
  • 用长度为m的–位数组Request表示进程此次申请的各种资源数
• 银行家算法步骤: .
  ①检查此次申请是否超过了之前声明的最大需求数
  ②检查此时系统剩余的可用资源是否还能满足这次请求
  ③试探着分配，更改各数据结构
  ④用安全性算法检查此次分配是否会导致系统进入不安全状态
• 安全性算法步骤:
  • 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
  • 不断重复上述过程，看最终是否能让所有进程都加入安全序列。

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

12.3、死锁的处理策略——检测和解除

如果系统中即不采取预防死锁的措施，也不采取避免死锁的措施，系统就很__可能发生死锁__。在这种情况下：系统应当提供两个算法：

• 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
• 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态冲解脱出来。

12.3.1、死锁的检测

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

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

如果系统中剩余的可用资源数足够进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。

如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程激活，并顺利的执行下去。

相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另一些阻塞的进程…

如果按照上述过程分析，最终__能消除所有边__，就称这个图使__可完全简化的__。此时一定__没有发生死锁__（相当于能找到一个安全序列）。

如果最终__不能消除所有边__，那么此时就是__发生了死锁__。

最终还连着边的那些进程就是处于死锁状态的进程。

检查死锁的算法：

• 在资源分配图中，找出既不阻塞又不是孤点的进程Pi ( 即找出一条有向边与它相连，且该有
  向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有
  一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然
  后释放它所占有的所有资源)。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中
  P1是满足这- - 条件的进程结点，于是将P1的所有边消去。
• 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变
  为非阻塞进程。在下图中，P2 就满足这样的条件。根据1)中的方法进行一系列简化后，若能消
  去途中所有的边，则称该图是__可完全简化__的。

__死锁定理：如果某时刻系统的资源分配图是__不可完全简化__的，那么此时系统__死锁。

到此为止我们已经可以__检测到死锁，那如何解除死锁呢？__

12.3.2、死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。

【补充】并不是系统中所有的进程都是死锁状态，用死锁检测算法__化简资源分配图后，还连着边的哪些进程就是死锁进程。__

解除死锁的主要方法：

• 资源剥夺法。挂起（暂时放到外存上）某些死进程，并抢占它的资源，将这些资源分配给其它的死锁进程，但是应防止被挂起的进程长时间得不到资源而饥饿。
• 撤销进程法（终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓是功亏一篑，以后还得从头再来。
• 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统记录进程的历史信息，设置还原点。

那对那些进程执行死锁的解除呢？

• 进程优先级：进程优先级低的进程。
• 已执行多长时间：已经执行时间少的进程。
• 还要多久能完成：让马上就执行结束的进程。
• 进程已经使用了多少资源：使用较多的资源的进程。
• 进程是交互式还是批处理式的：优先解除批处理式的进程。

12.3.3、知识回顾