操作系统基本原理——原创通过三种前驱图类型详细总结计算进程管理之 PV 操作
操作系统基本原理——原创通过三种前驱图类型详细总结计算进程管理之 PV 操作
文章目录
- 前言
- 一、PV 操作定义
- 1.1、P 操作定义
- 1.2、V 操作定义
- 二、串联进程（单线前驱图）
- 2.1、什么是单线前驱图？
- 2.2、如何计算单线前驱图的 PV？
- 2.2.1、计算前驱节点 PV
- 2.2.2、计算中间节点 PV
- 2.2.3、计算尾节点 PV
- 三、并联进程（多线前驱图）
- 3.1、什么是多线前驱图？
- 3.2、并联进程趋于合并
- 3.2.1、计算前驱节点 PV
- 3.2.2、计算中间节点 PV
- 3.2.3、计算尾节点 PV
- 3.3、并联进程趋于展开
- 3.3.1、计算前驱节点 PV
- 3.3.2、计算中间节点 PV
- 3.3.3、计算尾节点 PV
- 总结
前言
关于 PV 操作基本都是结合进程管理的前驱图来进行考察，历年以来，无论是软考还是操作系统的单独考试，占有很大的比重。今天我们总结两种在考试中常考的类型。一种是单线前驱图，即串联进程，另一种是多线前驱图，即并联进程。并联进程下又细分为两类：一种逐渐向后合并（进程趋于合并），另一种是前驱图逐渐向后展开。两种类型你都掌握了应试也就毫无问题了。
一、PV 操作定义
本文中的 S 为信号量。关于前驱图以及信号量的基础知识本篇不作详细介绍。
1.1、P 操作定义
S:=S-1，若 S≥0，则执行 P 操作的进程继续执行；若 S<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
定义这么长，我们只需要谨记：执行 P 操作的进程将进入等待队列。
1.2、V 操作定义
S:=S+1，若 S>0，则执行 V 操作的进程继续执行；若 S≤0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行 V 操作的进程继续。
定义这么长，我们只需要谨记：执行 V 操作的进程将从阻塞队列中唤醒一个进程。
二、串联进程（单线前驱图）
2.1、什么是单线前驱图？
串联进程（单线前驱图）是计算 PV 操作中最为简单的。那什么是单线前驱图呢？举例前驱图如下：
题干信息：使用 PV 操作控制进程 P1、P2、P3 执行的过程，设置 2 个信号量分别为 S1、S2 且初值均为零。分别列出 3 个进程的进程执行图来计算每个进程的 PV 操作。
我们可以看到 P1、P2、P3 三个进程是串联关系，一一执行，只有前面的进程执行了后面的才可以执行，我们将这类前驱图归类为单线前驱图。
2.2、如何计算单线前驱图的 PV？
那我们计算该进程的 PV 操作呢？我们将节点分为前驱节点（即首节点），中间节点，尾节点分别计算 PV。
2.2.1、计算前驱节点 PV
对于前驱的首结点 P1 进程，进程 P1 从初始状态执行操作的结果就是从阻塞队列中唤醒一个进程，即唤醒 P2，故其只有 V 操作，占用一个信号量 S1，进程 P1 执行 V（S1）操作。P1 进程执行图如下图所示：
2.2.2、计算中间节点 PV
对于中间节点 P2 进程，只有在前驱进程 P1 完成之后才可以执行，如果进程 P1 阻塞 P2 就无法正常执行，处于等待状态，故 P2 进程是从等待 S1 的信号量，运行本进程，结果就是唤醒另一个进程即 P3 进程，并占用一个信号量 S2。P2 进程执行图如下图所示：
2.2.3、计算尾节点 PV
对于 P3 进程，同理，只有在前驱节点 P2 执行完成将信号量 S2 传过来之后才可以执行，然后进程结束。P3 进程执行图如下图所示：
三、并联进程（多线前驱图）
3.1、什么是多线前驱图？
多线前驱图即并联进程，多个进程趋于合并或者单个进程展开为多个进程，类似于初中我们所学的串并联电路知识。下面我们分别从并联进程趋于合并与并联进程趋于展开两个方向来讨论不同情况如何计算 PV 操作。
3.2、并联进程趋于合并
并联进程趋于合并是并联进程中较为简单的，我在这里举一例较为经典的例题。进程前驱图如下：
题干信息：使用 PV 操作控制进程 P1、P2、P3、P4 并发执行的过程，设置 4 个信号量分别为 S1、S2、S3、S4 且初值均为零。分别列出 5 个进程的进程执行图来计算每个进程的 PV 操作。
3.2.1、计算前驱节点 PV
对于前驱的首结点，以 P1 进程为例，进程 P1 从初始状态执行操作的结果就是从阻塞队列中唤醒一个进程，即唤醒 P4，故其只有 V 操作，并占用一个信号量 S1，故进程 P1 执行 V（S1）操作。P1 进程执行图如下图所示：
同理，P2、P3 进程与 P1 相同，三个进程分别各占三个信号量S1、S2、S3，进程执行图如下图所示：
3.2.2、计算中间节点 PV
对于中间节点进程 P4，只有在前驱进程 P1、P2、P3 都已经完成之后才可以执行，而进程 P1、P2、P3 均有可能在阻塞队列中，故进程 P4 需要先等待 P1、P2、P3 进程的执行（即 P 操作）接收信号量，然后执行 P4 自身进程唤醒 P5 操作（即 V 操作）占用一条信号量 S4。P4 进程执行图如下图所示：
3.2.3、计算尾节点 PV
对于 P5 进程，同理，需要接收到 P4 进程的信号量才可以运行，然后进程结束。P5 进程执行图如下图所示：
3.3、并联进程趋于展开
并联进程趋于展开是并联进程中较为难的一种，但是理清了思绪还是得心应手的。举例题如下：
题干信息：使用 PV 操作控制进程 P1、P2、P3、P4、P5 执行的过程，设置 5 个信号量分别为 S1、S2、S3、S4、S5 且初值均为零。分别列出 5 个进程的进程执行图来计算每个进程的 PV 操作。
分析：对于本前驱图，我们应该注意 P2、P3、P4 进程，信号量的判别根据进程标识顺序走。
3.3.1、计算前驱节点 PV
前驱节点进程 P1跟之前我们讲到的一样，这里不再赘述。P1 进程执行图如下图所示：
3.3.2、计算中间节点 PV
对于进程 P2，需要等到 P1 的信号量 S1，并唤醒 P3、P4 进程分别占用信号量 S1、S2。P2 进程执行图如下图所示：
对于进程 P3，需要等到进程 P2 的信号量 S2 才可以执行，然后激活进行 P4，占用一个信号量 S4。P3 进程执行图如下图所示：
对于进程 P4，需要等到进程 P2、P3 的信号量 S3、S4 才可以执行，然后激活进程 P5，并占用一个信号量 S5。P4 进程执行图如下图所示：
3.3.3、计算尾节点 PV
对于尾节点进程 P5，需要等到进程 P4 的信号量 S5 才可以执行，直到进程结束。P5 进程执行图如下图所示：
总结
本文给大家介绍了操作系统基本原理中的一个重要知识点，进程管理之 PV 操作。我们通过对不同的前驱图进行分类，总结了两大类最为常见的前驱图类型，在不同的情境下设置不同的处理思路。循序渐进，从单进程到多进程，处理思路跟着题目给出的前驱图表示顺序走（跟着顺序走你会发现都是单进程的计算方式）。相信本篇文章更能让你在计算过程中起到事半功倍的效果。
我是白鹿，一个不懈奋斗的程序猿。望本文能对你有所裨益，欢迎大家的一键三连！若有其他问题、建议或者补充可以留言在文章下方，感谢大家的支持！