计算机操作系统之PV原语分析及计算

《计算机操作系统之PV原语分析及计算》由会员分享，可在线阅读，更多相关《计算机操作系统之PV原语分析及计算（10页珍藏版）》请在装配图网上搜索。

1、操作系统课程之 PV 原语PV 原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不 可分割不可中断的程序。信号量的概念 1965 年由著名的荷兰计算机科学家 Dijkstra 提出，其基本思路是 用一种新的变量类型( semaphore )来记录当前可用资源的数量。有两种实现方式：1) semaphore 的取值必须大于或等于 0。0 表示当前已没有空闲资源，而正数表示 当前空闲资源的数量； 2) semaphore 的取值可正可负，负数的绝对值表示正在等 待进入临界区的进程个数。信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语( P V 原语)来访问。初始化可

2、指定一个非负整数，即空闲资源总数。P原语：P是荷兰语Proberen (测试)的首字母。为阻塞原语，负责把当前进程 由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源 (把信号量减 1) ，若成功，则退出；若失败，则该进程被阻塞；V原语：V是荷兰语Verhogen (增加)的首字母。为唤醒原语，负责把一个被 阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一 个被占用的资源(把信号量加 1)，如果发现有被阻塞的进程，则选择一个唤醒之。具体 PV 原语对信号量的操作可以分为三种情况：1) 把信号量视为一个加锁标志位，实现对一个共享变量的互斥访问。实

3、现过程：P(mutex); / mutex 的初始值为 1 访问该共享数据 ;V(mutex);非临界区2) 把信号量视为是某种类型的共享资源的剩余个数，实现对一类共享资源的访 问。实现过程：P(resource); / resource 的初始值为该资源的个数 N 使用该资源；V(resource); 非临界区3) 把信号量作为进程间的同步工具实现过程：临界区 C1；P(S);V(S);临界区 C2；哲学家问题PV原语程序2009年03月10日 星期二 21:29 设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。但是，桌 子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在

4、肚子饥饿时才试 图分两次从两边拾起筷子就餐。条件：(1) 只有拿到两支筷子时，哲学家才能吃饭。(2) 如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷 子。(3) 任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。试：(1) 描述一个保证不会出现两个邻座同时要求吃饭的通信算法。(2) 描述一个既没有两邻座同时吃饭，又没有人饿死(永远拿不到筷子)的算 法。(3) 在什么情况下，5个哲学家全部吃不上饭？解答：(1) 、设信号量c0c4,初始值均为1,分别表示i号筷子被拿(i=0,1,2,3,4), send(i):第i个哲学家要吃饭beginP(ci);P(ci+1

5、mod 5);eat;V(ci+1 mod 5);V(ci);End;该过程能保证两邻座不同时吃饭，但会出现5个哲学家一人拿一只筷子,谁也吃 不上饭的死锁情况.(2) 、解决的思路如下:让奇数号的哲学家先取右手边的筷子，让偶数号的哲学 家先取左手边的筷子这样，任何一个哲学家拿到一只筷子之后，就已经阻止了他 邻座的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人会饿 死.send(i):第i个哲学家要吃饭BeginIf i mod 2=0 thenP(ci),P(ci+1 mod 5)eat;V(ci,ci+1 mod 5)ElseP(ci+1 mod 5)P(ci)EatV(ci+

6、1 mod 5)V(ci)EndPV原语实现互斥与同步2008年09月19日 星期五 17:28PV原语的含义P操作和V操作是不可中断的程序段，称为原语。PV原语及信号量的概念都 是由荷兰科学家E.W.Dijkstra提出的。信号量sem是一整数，sem大于等于零时 代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界 区的进程数。P原语操作的动作是：(1) sem 减 1；(2) 若sem减1后仍大于或等于零，则进程继续执行；(3) 若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中, 然后转进程调度。V原语操作的动作是：(1) sem 加 1；(2) 若相

7、加结果大于零，则进程继续执行；(3) 若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程， 然后再返回原进程继续执行或转进程调度。PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。在PV 原语执行期间不允许有中断的发生。用PV原语实现进程的互斥由于用于互斥的信号量sem与所有的并发进程有关，所以称之为公有信号量。 公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem)和V(sem)之 间，即可实现进程间的互斥。就象火车中的每节车厢只有一个卫生间，该车厢的 所有旅客共享这个公有资源：卫生间，所以旅客间必须互斥进入卫生间，只要把 卫生间放在P(sem用叮(sem)之

8、间，就可以到达互斥的效果。以下例子说明进程的 互斥实现。例1生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用 自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：(1) 进程A专门拣黑子，进程B专门拣白子；(2) 每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣 子；分析： 第一步：确定进程间的关系。由功能(2)可知进程之间是互斥的关系。第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子, 箱子是两个进程的公有资源，所以设置一个信号量s，其值取决于公有资源的数 目，由于箱子只有一个，s的初值就设为1。实现：begins:sem

9、aphore;s:=1;cobeginprocess AbeginL1: P(s);拣黑子；V(s);goto L1;end;process BbeginL2:P(s);拣白子；V(s);goto L2;end;coend;end;判断进程间是否互斥，关键是看进程间是否共享某一公有资源，一个公有资 源与一个信号量相对应。确定信号量的值是一个关键点，它代表了可用资源实体 数。如下实例：例2某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20 名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看 成一个进程。分析：第一步：确定进程间的关系。售票厅是各进程共享的公有

10、资源，当售 票厅中多于20名购票者时，厅外的购票者需要在外面等待。所以进程间是互斥的 关系。第二步：确定信号量及其值。只有一个公有资源：售票厅，所以设置一个 信号量S。售票厅最多容纳20个进程，即可用资源实体数为20, s的初值就设为 20。实现：begins:semaphore;s:=20;cobeginprocess PI(I=1,2,)begin P(s);进入售票厅；购票；退出；V(s);end;coend当购票者进入售票厅前要执行P(s)操作，执行后若s大于或等 于零，说明售票厅的人数还未满可进入。执行后若s小于零，则说明售票厅的人 数已满不能进入。这个实现中同时最多允许20个进程进

11、入售票厅购票，其余进程 只能等待。用PV原语实现进程的同步与进程互斥不同，进程同步时的信号量只与制约进程及被制约进程有关而不 是与整组并发进程有关，所以称该信号量为私有信号量。利用PV原语实现进程同 步的方法是：首先判断进程间的关系为同步的，且为各并发进程设置私有信号量， 然后为私有信号量赋初值，最后利用PV原语和私有信号量规定各进程的执行顺 序。下面我们将例1增添一个条件，使其成为进程间是同步的。例3在例1的基础之上再添加一个功能：（3）当一个进程拣了一个棋子（黑子或白子）以后，必让另一个进程拣一个 棋子（黑子或白子）。分析： 第一步：确定进程间的关系。由功能（1）（2）（3）可知，进程间的

12、关系为 同步关系。第二步：确定信号量及其值。进程A和B共享箱子这个公有资源，但 规定两个进程必须轮流去取不同色的棋子，因而相互间要互通消息。对于进程A 可设置一个私有信号量si，该私有信号量用于判断进程A是否能去拣黑子，初值 为1。对于进程B同样设置一个私有信号量s2,该私有信号量用于判断进程B是 否能去拣白子，初值为0。当然你也可以设置si初值为0, s2初值为1。实现:begins1,s2:semaphore;s1:=1;s2:=0;cobeginprocess AbeginL1: P（s1）;拣黑子；V（s2）;goto L1;end;process BbeginL2:P（s2）;拣白子

13、；V（s1）;goto L2;end;coend;end;另外一个问题就是P原语是不是一定在V原语的前面？回答是否定的。下面 看一个例子。例4设在公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车， 到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。用PV操作对其控 制。分析：第一步：确定进程间的关系。司机到站停车后，售票员方可工作。同样，售 票员关车门后，司机才能工作。所以司机与售票员之间是一种同步关系。第二步：确定信号量及其值。由于司机与售票员之间要互通消息，司机进程 设置一个私有信号量run，用于判断司机能否进行工作，初值为0。售票员进程设 置一个私有信号量st op,

14、用于判断是否停车，售票员是否能够开车门，初值为0。实现：begin stop ,run:semaphorestop:=0;run:=0;cobegindriver: beginL1: P(run);启动车辆；正常行车；到站停车；V(stop);goto L1;end;conductor:beginL2:上乘客；关车门；V(run);售票；P(stop);开车门；下乘客；goto L2;end;coend;end;用PV操作还可以实现进程同步与互斥的混合问题，典型的如：多个生产者和 多个消费者共享容量为n的缓存区。这个例子在很多书中都有介绍，在这里就不 说了。用信号量机制来解决进程的同步与互斥：

15、PV操作 首先确定进程间的关系，然后确定信号量及其值。判断进程间是否互斥的关键：看进程间是否共享某一公有资源，一个公有资源与一个信 号量相对应。确定信号量的值是一个关键点，它代表了可用资源实体数。举例：票大厅容纳的人数限制为20人，少于20人时购票者可以进入，否则要在厅外等 候。进程间是同步时：是否存在合作关系，是否需要互通消息 首先判断进程间的关系为同步的，且为各并发进程设置私有信号量，然后为私有信号量 赋初值，最后利用PV原语和私有信号量规定各进程的执行顺序。举例：公交车上司机与售票员的行为，司机到站停车后，售票员方可开门，售票员关门 后，司机方可开车。进程同步应用示例讲解：1 桌上有一个

16、盘子，可以存放一个水果。父亲总是把苹果放在盘子中，母亲总是把香蕉放在盘子中；一个儿 子专等吃盘中的香蕉，一个女儿专等吃盘中的苹果。1) 系统要设几个进程来完成这个任务？各自的工作是什么？2) 这些进程间有什么样的相互制约关系?3) 用P, V操作写出这些进程的同步算法(注：标明信号量的含义)。1) 需要四个进程进程描述：Father :父亲放置苹果的进程；Mother :母亲放置香蕉的进程；Son:儿子吃香蕉的进程；Daughter:女儿吃苹果的进程。分析:四人公用一个盘子； 盘子每次只能放一个水果，当盘子为空时，父母均可尝试放水果，但一次只能有一人成功；盘中是香蕉，儿子吃，女儿等；盘中是苹果

17、，女儿吃，儿子等。2) 进程之间既有互斥又有同步关系。Father进程和Mother进程要互斥的向盘中放水果，应设置一互斥信号量dish，初值为1,表示盘子为空；Father进程要设置同步信号量apple，用于给Daughter进程传送消息，初值为0表示还没有消息产生， 即没有放苹果；相应Daughter进程也要向父、母进程传送盘子为空的消息。Mother进程要设置同步信号量banana，用于给Son进程传送消息，初值为0表示还没有消息产生，即 没有放香蕉。相应Son进程也要向父、母进程传送盘子为空的消息。3) 信号量设置:dish :表示盘子是否为空，初值=1；apple:表示盘中是否有苹果

18、，初值=0；banana:表示盘中是否有香蕉，初值=0。Father: while( true)P ( dish );/判断盘子是否空将苹果放入盘中；V ( apple );/传消息给女儿进程Mather: while( true)P ( dish );/判断盘子是否空将香蕉放入盘中；V ( banana );/传消息给儿子进程Son: while( true)P ( banana );/判断是否有香蕉从盘中取出香蕉；V ( dish );/传送盘空消息吃香蕉；Daughter: while（ true）P （ apple ）;/判断是否有苹果从盘中取出苹果；V （ dish ）;/ 传送盘空

19、消息吃苹果；进程同步应用示例讲解：2生产者与消费者共用一个有 n 个缓冲单元的缓冲区，生产者向缓冲区中放产品，消费者从缓冲区中取产品 消费。1）系统要设几个进程来完成这个任务？各自的工作是什么？2）这些进程间有什么样的相互制约关系?3）用P, V操作写出这些进程的同步算法（注：标明信号量的含义）。1）系统需设两个进程producer 进程 ：生产产品并向缓冲区中放；consumer 进程 ：从缓冲区取产品并消费；分析：生产者与消费者共用一个缓冲区，但有n个缓冲单元;对于缓冲区同一时刻只能有一个进程使用； 有空缓冲单元时，生产者可以放，否则等待； 有满缓冲单元时，消费者可以取，否则等待。2）两进

20、程间有互斥和同步的关系producer进程和consumer进程要互斥的访问缓冲区，应设置一互斥信号量mutex，初值为1。producer进程和consumer进程有同步的关系，当没有满缓冲单元时，consumer进程不能消费，当没有 空缓冲单元时，producer进程不能向缓冲区放。应为他们设置同步信号量empty=n和full=0，用于互传消息。当 empty=0 时不能生产，当 full=0 时不能消费。3）信号量设置mutex :保证对缓冲区的互斥访问，初值=1；empty :表示缓冲区中是否有空缓冲单元，初值=n full： 表示缓冲区中是否有满缓冲单元，初值=0。producer

21、： while（1）生产一个成品；P（empty）；P（mutex）；将产品存入缓冲区；V（mutex）；V（full）；进程同步应用示例讲解：3设有进程 A、B、C 分别对单缓冲区 S 和 T 进行consumer： while（1）P（full）；P（mutex）； 将产品从缓冲区取出；V（mutex）；V（empty）； 消费成品；作，其中 A 进程负责从卡片上读取数据并把数据块输入到缓冲区S，B进程负责从缓冲区S中提出数据块并将数据块送到缓冲区T中，C进程负责从缓冲区T 中取出信息打印。问题：1）这些进程间有什么样的相互制约关系?2）用P, V操作写出这些进程的同步算法（注：标明信号量

22、的含义）。 分析：两个阶段的生产者和消费者问题。只有S为空时，A进程才能向S中放数据； 只有S中有数据时，B进程才能取数据; 只有T为空时，B进程才能向T中放数据； 只有T中有数据时，C进程才能取数据。1）三进程间有互斥和同步的关系A进程和B进程要互斥的访问缓冲区S，B进程和C进程要互斥的访问缓冲区T。A进程和B进程有同步的关系，当缓冲区S空时，A进程才能向S中放数据，只有S中有数据时，B 进程才能取数据。应为他们设置同步信号量emptyS=l和fullS=O，用于互传消息。B进程和C进程有同步的关系，只有当缓冲区T空时，B进程才能向T中放数据，只有T中有数据时,C进程才能取数据。应为他们设置

23、同步信号量emptyT=1和fullT=0，用于互传消息。 3）信号量设置emptyS :表示单缓冲区S是否为空，初值为1；emptyT ：表示单缓冲区 T 是否为空，初值为1；fullS ：表示单缓冲区 S 是否有数据可处理，其初值0fullT :表示单缓冲区T是否有数据可处理，其初值0A: while(1)读卡片P(emptyS );将数据送入S; V(fullS ) ;B: while(1)P(fullS )； 从S中取数据;V(emptyS) ；P(emptyT); 将数据送入T; V(fullT ) ;C: while（1）P（fullT）;从T中取数据；V（emptyT） ;打印数

24、据； 进程同步应用示例讲解：4 分析： 确定进程间的关系:司机到站停车后，售票员方可工作。同样，售票员关车门后，司 机才能工作。所以司机与售票员之间是一种同步关系。司机进程 While（True） 启动公车； 驾驶公车； 停止公车；售票员进程While（True） 关车门； 卖车票； 开车门；售票员优先正确运行过程While（True）（售票员）关车门（司机）启动公车；（司机）驾驶公车；（售票员）卖车票（司机）停止公车; （售票员）开车门;信号量设置： 确定信号量及其值：由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run,用于判断司机能否进行工作，初值为0。售票员进程设置一个私有信号量stop, 用于判断是否停车，售票员是否能够开车门，初值为0。售票员进程司机进程: while(1) p(run);启动车辆正常行车 到站停车 v(stop); 售票员进程: while(1) 关车门； v(run);p(stop);开车门分享知识分享快乐-