操作系统中P、V操作实现进程的同步与互斥

2012-04-29 00:44常静
电脑知识与技术 2012年30期
关键词:信号量

常静

摘要:操作系统是计算机科学与技术的专业基础课程,进程的同步与互斥问题是操作系统中的重要内容。如何正确使用P、V操作实现进程的同步与互斥是防止死锁的重要手段,怎样判断进程是同步还是互斥问题,以及如何正确使用P、V操作防止进程死锁,该文通过具体的实例给出一种通用的解决模式。

关键词:进程同步;进程互斥;信号量;P、V操作

中图分类号:TP393 文献标识码:A文章编号:1009-3044(2012)30-7144-04

操作系统中,可以使用软件和硬件方法解决临界区的问题,虽然它们都可以解决互斥问题,但是存在一定的缺陷。于是计算机科学家们努力寻找其他更有效地方法。荷兰著名的计算机科学家E.W.Dijkstra提出了一个信号量和P、V操作同步机构。其基本原则是在多个相互合作的进程之间使用简单的信号来协调控制。

1 信号量的含义

信号量被定义为含有整型数据项的结构变量,其整型值大于等于零代表可供并发进程使用的资源个数,小于零时其绝对值表示正在等待使用临界资源的进程数。其数据结构表示为:

2 P、V原语的含义

信号量的值可以修改,但只能由P和V操作来访问,对信号量的操作由P、V操作原语来实现。P操作和V操作在执行时是不可中断的过程。

P操作P(s)

表示申请一个资源,将信号量s的整型值减去1,若结果小于0,则将调用P(s)的进程插入等待该资源的阻塞队列。

V操作V(s)

表示释放一个资源,将信号量s的整型值加上1,若结果不大于0,则从该资源的阻塞队列首部唤醒一个进程插入到就绪队列中。

P、V操作原语是一种阻塞等待的同步原语,若进程通过该原语的调用而不允许继续执行时,它将被阻塞或挂起,在此期间就没有机会获得CPU执行,直到它被唤醒为止。故可使得进程在等待进入临界区时,将CPU让给了其他就绪进程执行。而忙等待的临界区管理法,使得进程在等待进入临界区时,也和其他就绪进程一起分享CPU的服务。

3 P、V操作在进程同步中的意义

进程同步包括进程互斥和进程同步两个方面,进程互斥是同步的一种特例。用P、V操作解决进程同步问题时首先要分清哪些是互斥问题(互斥访问临界资源的),哪些是同步问题(具有前后执行顺序要求的)。

在互斥问题中,P操作的意义是申请资源,是否能进入临界区;V操作的意义是退出临界区,从而释放资源;通常只设置一个互斥信号量,且初值为1,代表一次只允许一个进程对临界资源进行访问。在同步问题中,P操作的意义是接受发来的信息、通知,表示可以执行;V操作的意义是发送消息、通知,告知对方。在设置同步信号量时,通常同步信号量的个数与参与同步的进程种类有关,即同步关系涉及几类进程,就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。

在每个进程中用于实现互斥的P、V操作必须成对出现;用于实现同步的P、V操作也必须成对出现,但可以分别出现在不同的进程中;在某个进程中如果同时存在互斥与同步的操作,则其顺序不能颠倒,必须先执行对同步信号量的P操作,再执行对互斥信号量的P操作,但V操作的顺序没有严格要求。

4 实现P、V操作的具体做法

1)确定进程间的关系以及进程的个数。这一环节非常重要,如果理解不准确,则之后的操作都将是错误的。进程间的关系主要指是进程同步还是进程互斥,它决定了P、V操作在进程中存在的意义。进程的个数主要看题目中需要P、V控制的事件有多少个,则进程个数就是几个。

2)信号量个数的设置,并给信号量赋初值。一般情况下,在进程互斥中,信号量都为一个;在同步中,要根据进程间的同步关系来设置信号量的个数, 有一个也可能是多个。

3)画出进程的工作流程图。流程图时最好反映题意的一种方法,工作流程图越准确,最后的算法就越容易实现。

4)根据流程图使用一门语言来描述进程之间的关系。这步主要是看个人的编程基础,用不同的语言实现都可以,最好是用自己掌握较好的一门语言。

下面就一些典型例子做分析,在分析中理解P、V操作在进程同步中的实际运用:

4.1 用PV原语实现进程的互斥

为了正确地解决一组并行进程对临界资源的竞争使用,可以引入一个互斥信号量,对于互斥使用的资源,其信号量的初值就是系统中这个资源的数量。以哲学家进餐问题为例:

有四位哲学家围着一个圆桌在思考和进餐,每人思考时手中什么都不拿,当需要进餐时,每人需要用刀和叉各一把,餐桌上的布置如图1所示,共有两把刀和两把叉,每把刀或叉供相邻的两个人使用。请用信号量及PV操作说明四位哲学家的同步过程。

1)确定进程的个数及其工作内容。本例子涉及四个进程,每个哲学家为一个进程。因相邻的两个哲学家要竞争刀或叉,刀或叉就成为了临界资源,所以属于互斥关系。

2)第二步确定互斥信号量的个数、含义及PV操作。设置4个互斥信号量fork1,fork2,knife1,knife2,其初值均为“1”,分别表示叉1,叉2,刀1,刀2是可用的。

3)画工作流程图。一般情况下,进程互斥问题的工作流程基本相同,所以只要画出其中一个进程的流程图即可。

4)根据流程图写出相应算法。用类C语言描述互斥关系,互斥描述如下:

4.3用P、V原语实现进程的同步和互斥

有了上面的分析后,下面来考虑进程同步与互斥的混合问题就不难了。混合问题当中关键就是协调同步操作和互斥操作的先后。通过下面的例子来说明此问题:

设有一个具有N个信息元素的环形缓冲区,A进程顺序地把信息写进缓冲区,B进程依次地从缓冲区中读出信息,请用P、V操作表示A和B进程的同步算法。

1)确定进程间的关系。A和B两个进程对缓冲区的访问必须互斥,并且当缓冲区满时,A进程不能写入,必须等待;当缓冲区空时,B进程不能读,必须等待。所以这是一个同步加互斥的问题。

2)确定信号量及其值。可以设置3个信号量:互斥信号量S=1(表示对缓冲区的互斥使用);同步信号量Sw(代表缓冲区是否有空闲,即写进程能否写)、Sr(代表缓冲区是否有数据,即读进程能否读),假设初始时缓冲区没有任何数据,则Sw=N,Sr=0。

3)画出工作流程图,如图3所示。

4)根据流程图写出相应算法。在此就不再详述。

5 总结

本文通过实例,对利用P、V操作实现进程互斥与同步给出了一个一般模型。在具体实现时,只需要在模型中的P 操作和V操作间填入适当的实现代码,就可以很方便地实现进程的同步与互斥了,希望对学习者理解和解决这一难点问题有一定的帮助。

参考文献:

[1] 马海波,王德广.计算机操作系统教程[M].北京:清华大学出版社,2009.

[2] 连卫民,徐保民.操作系统原理教程[M].北京:中国水利水电出版社,2004.

猜你喜欢
信号量
基于STM32的mbedOS信号量调度机制剖析
互斥信号量初值不同情况分析
能源控制器信号量死锁问题分析及解决方案
Nucleus PLUS操作系统信号量机制的研究与测试
操作系统进程同步和互斥教学方法研究
linux下多值信号量的操作探讨
硬件信号量在多核处理器核间通信中的应用
学生在理解信号量实现进程同步与互斥时常见问题
μC/OS- -III对信号量的改进
Linux操作系统信号量机制的实时化改造