一道关于P、V操作的操作系统经典题目的正确算法

一道关于Ｐ、Ｖ操作的操作系统经典题目的正确算法

作者：徐 健 张 雷 朱向彩

来源：《中国校外教育·理论》2008年第09期

[摘要]本文介绍了操作系统中P、V操作的有关概念，分析了应用PV操作的一道经典题目并给出了正确的解法。

[关键词]操作系统 P、V操作 算法

1操作系统中的P、V操作简介

现代操作系统基本上都是多进程的操作系统，系统中有多个进程并发执行，这些并发执行的进程之间存在着不同的相互制约关系，为了协调进程之间的这种相互制约关系，需要实现进程的同步与互斥。

在操作系统中存在着各种资源供进程使用，如果某个资源一次只能供一个进程使用，则称其为临界资源。计算机中许多物理设备如打印机、扫描仪等都属于临界资源，除物理设备外，许多变量、数据等都可以被若干进程共享，但不允许多个进程同时进行修改操作，它们也可视为临界资源。

在每个进程中，访问临界资源的那段程序称为临界区，在操作系统中，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源，这种进程间的相互制约关系称为互斥。

一般说来，在操作系统中，一个进程相对于另一进程的运行速度是不确定的，但是相互合作的几个进程需要在某些确定点上协调它们的工作。所谓进程同步是指多个相互合作的进程，在一些关键点上可能需要相互等待或相互交换信息，这种相互制约关系称为进程同步。 在操作系统中解决进程同步和互斥问题的一种重要方法是信号量机制和P、V操作。信号量是一个确定的二元组（S，Q），其中S是一个具有非负初值的整形变量，Q是一个初始状态为空的队列。整形变量S表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因其请求该类资源而被阻塞的进程数目。除信号量的初值外，信号量的值仅能由P操作和V操作改变。

龙源期刊网 http://www.qikan.com.cn

P、V操作在1965年由荷兰计算机大师Dijkstra引入，他用荷兰语中的单词passeren（通过）、vrijgeven（释放）的首字母来为这两种操作命名。

P、V操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

P（S）：①将信号量S的值减1，即S=S-1；

②如果S30，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1；

②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。 利用信号量和P、V操作可以有效的解决进程的同步和互斥问题。 2 一道考察PV操作的经典操作系统试题

P、V操作是操作系统课程中的重点内容，其考察形式并不仅限于计算机中进程的互斥和同步，而更多的将现实中的某些事务纳入，要求使用P、V操作来处理这些事务。许多操作系统教材中都有诸如哲学家进餐问题、理发师问题、生产者－消费者问题等经典例题，就是这种情况的体现。本文所要讲述的这道题目也是这种类型的。

在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但其中有一个小的安全岛M(同时允许两辆自行车停留)，可供两辆自行车已从两端进人小路情况下错车使用，如图1所示。试设计一个算法使来往的自行车均可顺利通过。 该题目是南开大学1997年研究生入学考试的操作系统科目的一道试题，在很多操作系统的参考书和习题集中都有收录，其解法一般如下：

分析及相关知识：在本题中，需要控制路段T到L，路段S到K及安全岛M的使用。路段T到L及路段S到K同时只允许一辆自行车通过。而安全岛M允许两辆自行车使用，因此可以用三个信号量来管理它们、另一方面，同一方向上的自行车最多只能有一辆通过这段路(两个方向上有两辆)，因此还应该用两个信号量来控制。

解：在本题中，应设置5个信号量ST，TS K，L，M，信号量ST表示是否允许自行车从南开大学去天津大学，其初值为1;信号量TS表示是否允许自行车从天津大学去南开大学，其初值为1;信号量K表示是否允许自行车通过路段S到K，其初值为1;信号量L表示是否允许自行车通过路段T到L，其初值为1;信号量M表示安全岛上还可停放自行车的数目;其初值为2。其控制过程描述如下：

龙源期刊网 http://www.qikan.com.cn

semaphore ST=1; semaphore TS=1; semaphoreK=1; semaphore L=1; semaphore M=2;

totianjin() /*从南开大学去天津大学 */ { p(ST); p(K); 从S走到K; p(M); 进入安全岛; v(K); p(L); 从L走到T; v(M); v(L); v(ST); }

tonankai() /*从无津大学去南开大学 */ { p(TS);

龙源期刊网 http://www.qikan.com.cn

p(L); 从T走到L; p(M); 进入安全岛; v(L); P(K); 从K走到S; v(M); v(K); v(TS); }

以上是一般参考书中给出的解法。后来笔者又在网上找到了安徽理工大学操作系统课程网站上给出的另一种解法，如下所示：

由于小路中间的安全岛M仅允许两辆自行车停留，本应该作为临界资源而设置信号量， 但仔细分析可以发现：在任何时刻进入小路的自行车最多不会超过两辆(南开和天大方向各一辆)，因此，无需为安全岛M设置信号量。在路口S处，南开出发的若干自行车应进行进入小路权的争夺，以决定谁能够进入小路SK段，为此，设置信号量S(初值为1)来控制南开路口资源的争夺。同理，设置信号量T(初值为1)来控制天大路口资源的争夺。此外，小路SK段仅允许一辆自行车通过，所以设置信号量SK(初值为1)来进行控制，而对于LT 段则设置信号量LT(初值为1)进行控制。(控制过程描述略) 3 该题目正确的算法

下面我们抛弃掉这个错误的前提，看一下真实情况下的小路，能够容许什么样的交通。当对面没有来车的情况下，小路应该允许多辆自行车单向行驶；若一个方向有多辆自行车进入，另一方向仅有一辆自行车，则可以在安全岛错车，单独的自行车要在安全岛里等待对面自行车全部通过安全岛后方可进入第二路段；若两个方向都有超过一辆的自行车进入，则双方都无法通过，出现死锁。另外，两个路段中都只允许单个方向的自行车进入，不能有两个方向的自行车同时存在；两个路段可以分别有不同方向的自行车。

龙源期刊网 http://www.qikan.com.cn

由P、V操作的定义可知，这种方法是对资源进行封锁，当下一个进程进行P操作时会因为没有可用的资源而被阻塞。因此，现在问题转化为在什么情况下应该对后来的自行车进行阻塞的问题。

为方便说明，引入两个变量i、j。i表示本方向已进入小路的自行车数量，j表示对面方向进入小路的自行车数量。分情况讨论，当i>0,j=0时，本方可以任意进入，对方可以进一辆车，无需封锁；当i=1,j=1时本方或对方都可以进一辆车，双方在安全岛错车，因此也无需封锁；当i>1，j=1时，本方可以进车，而对方不能进入，因此要封锁对方后续自行车进入；i=0,j>0时，本方可以进一辆车，对方也可以进入，无需封锁；i=1,j>1时，本方不能再进，对方可以进入，因此需要封锁己方后续进入；i>1,j>1,这种情况不可能出现，如果出现意味着算法失败。

再考虑解锁，由于在封锁时可以封锁对方，也可以封锁本方，因此，解锁时也要考虑，解锁的时机应该放在本方向最后一辆自行车离开小路时。是否解锁要根据是否封锁来确定，由于信号量只能由P、V操作访问，因此，应该设置一个共享变量来表示当前加锁情况。

以上是对于整个路径的封锁情况，由于每个路段都只能单向行驶，因此，当一辆自行车进入后，应当阻塞对面方向的自行车进入该路段，本方向的自行车可以依次进入，在最后一辆自行车离开时，进行解锁。

安全岛可以容纳两辆自行车，因此资源M＝2，但是在i>1，j=1的情况下，有可能出现，本向两辆自行车进入安全岛，等待进入第二路段，而对方自行车却在第二路段中等待进入安全岛的情况，这样就发生了死锁。由于安全岛的作用就是错车（这里我们不考虑同方向自行车利用安全岛超车的可能），因此，同时进入安全岛的自行车一个方向只能有一辆，我们可以把临界资源M分成

和

两部分，数量都为1，来表示S→T和T→S两个方向的

安全岛资源。通过这种方法，可以避免前述的死锁问题。 设置信号量如下：

wait：控制两个方向的自行车只能依次进入小路，不能有两辆自行车同时由小路两端进入。

s-entry,t-entry：表示是否允许两个方向的自行车进入小路。

sk,lt,tl,ks：表示是否允许自行车按方向进入该路段，比如sk＝1表示允许自行车由s端进入sk路段。

variety：用来封锁共享变量，避免两个进程同时访问共享变量，为避免复杂性，程序中只提供一个这样的信号量，它对所有共享变量提供保护。

龙源期刊网 http://www.qikan.com.cn

设置共享变量countSK,countKS,countTL,countLT表示路段内某方向的自行车数量；block记录当前对s-entry和t-entry的封锁情况，block=0表示两个方向都没有封锁，block=1表示封锁S→T方向，block=2表示封锁T→S方向。 算法描述如下： semaphore wait=1; semaphore s-entry=1; semaphore t-entry=1; semaphore sk=1; semaphore lt=1; semaphore tl=1; semaphore ks=1; semaphore Ms=1; semaphore Mt=1; semaphore variety=1; int countSk=0; int countKS=0; int countTL=0; int countLT=0; int countMs=0; int countMt=0; int block=0; main() { cobegin;

龙源期刊网 http://www.qikan.com.cn

StoT(); TtoS(); coend }

StoT()/*从南开大学去天津大学*/ { p(wait); p(s-entry); p(sk); p(variety);

if (countSK==0) p(ks); countSK++; if(countTL+countMt

else if (countSK+countMs=1 and countTL+countMt>1) block=1; if (countSK+countMs>1) {p(t-entry);block=2;} V(variety); V(sk); V(wait); 从S走到K； p(Ms); 进入安全岛; p(variety); countMs=1;

龙源期刊网 http://www.qikan.com.cn

countSK--;

if (countSK==0) V(ks); V(variety); P(lt); V(Ms); P(variety); CountMs=0; If (countLT==0) p(tl); CountLT++; V(variety); 从L走到T; p(variety); countLT--;

if (countLT==0) V(tl);

if(countSK+countMs+countLT==0 and block==2) {V(t-entry);block=0;} V(variety); }

TtoS()/*从天津大学去南开大学*/ { p(wait); p(t-entry); p(tl);

龙源期刊网 http://www.qikan.com.cn

p(variety);

if (countTL==0) p(lt); countTL++; if(countSK+countMs

else if (countTL+countMt=1 and countSK+countMs>1) block=2; if (countTL+countMt>1) {p(s-entry);block=1;} V(variety); V(tl); V(wait); 从T走到L； p(Mt); 进入安全岛; p(variety); countMt=1; countTL--;

if (countTL==0) V(lt); V(variety); P(ks); V(Mt); P(variety); CountMt=0;

If (countKS==0) p(ks); CountKS++;

龙源期刊网 http://www.qikan.com.cn

V(variety); 从K走到S; p(variety); countKS--;

if (countKS==0) V(sk);

if(countTL+countMt+countKS==0 and block==1) {V(s-entry);block=0;} V(variety); }

该算法通过增加对于本方向和对面方向的进入封锁，保证了在小路中在反方向没有或只有一辆自行车的情况下，本方向可以有多辆自行车依次进入，提高了运行效率，更好地模拟了真实的交通情况，作为操作系统的经典题目，该算法应该是较为正确的解法。

参考文献：

[1]曾平，曾林.操作系统习题与解析（第二版）[M].北京:清华大学出版社，2004.3. [2]安徽理工大学网站的解法 star.aust.edu.cn/~ypsheng/os/ch0604-c12.htm. (作者单位：山东泰山学院)