《计算机操作系统》由会员分享，可在线阅读，更多相关《计算机操作系统（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 mo
5、d 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+1
6、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:semap
9、hore;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）;拣白子；V
13、（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的缓存区。这个例子在很多书中都有介绍，在这里就不 说了。用信号量机制来解决进程的同步与互斥：PV
15、操作 首先确定进程间的关系，然后确定信号量及其值。判断进程间是否互斥的关键：看进程间是否共享某一公有资源，一个公有资源与一个信 号量相对应。确定信号量的值是一个关键点，它代表了可用资源实体数。举例：票大厅容纳的人数限制为20人，少于20人时购票者可以进入，否则要在厅外等 候。进程间是同步时：是否存在合作关系，是否需要互通消息 首先判断进程间的关系为同步的，且为各并发进程设置私有信号量，然后为私有信号量 赋初值，最后利用PV原语和私有信号量规定各进程的执行顺序。举例：公交车上司机与售票员的行为，司机到站停车后，售票员方可开门，售票员关门 后，司机方可开车。进程同步应用示例讲解：1 桌上有一个盘子，可以存放一个水果。父亲总是把苹果放在盘子中，母亲总是把香蕉放在盘子中；一个儿 子专等吃盘中的香蕉，一个女儿专等吃盘中的苹果。1) 系统要设几个进程来完成这个任务？各自的工作是什么？2
