PV练习及参考解答.doc

PV原语操作详解 ?　　PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出，其基本思路是用一种新的变量类型(semaphore)来记录当前可用资源的数量。 ???? semaphore有两种实现方式： ???? 1) semaphore的取值必须大于或等于0。0表示当前已没有空闲资源，而正数表示当前空闲资源的数量； ??? 2) semaphore的取值可正可负，负数的绝对值表示正在等待进入临界区的进程个数。 ???? 信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语(P、V原语)来访问。初始化可指定一个非负整数，即空闲资源总数。 ???? P原语：P是荷兰语Proberen(测试)的首字母。为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源(把信号量减1)，若成功，则退出；若失败，则该进程被阻塞； ???? V原语：V是荷兰语Verhogen(增加)的首字母。为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一个被占用的资源(把信号量加1)，如果发现有被阻塞的进程，则选择一个唤醒之。 ???? P原语操作的动作是：??? (1)sem减1；??? (2)若sem减1后仍大于或等于零，则进程继续执行；??? (3)若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。 ??? V原语操作的动作是：??? (1)sem加1；??? (2)若相加结果大于零，则进程继续执行；??? (3)若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。 ??? PV操作必须成对使用。在PV原语执行期间不允许有中断的发生。 例1： ??? 生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：????(1)进程A专门拣黑子，进程B专门拣白子；????(2)每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子； ???? 分析：??? 第一步：确定进程间的关系。由功能(2)可知进程之间是互斥的关系。???? 实现：确定信号量及其值semaphore? s;? // 箱子个数，初值为1 ?　　????? 例：某超市门口为顾客准备了100辆手推车，每位顾客在进去买东西时取一辆推车，在买完东西结完帐以后再把推车还回去。试用P、V操作正确实现顾客进程的同步互斥关系。 ???? 分析：把手推车视为某种资源，每个顾客为一个要互斥访问该资源的进程。因此这个例子为PV原语的第二种应用类型。 ???? 解： ?semaphore?S_CartNum;????//：空闲的手推车数量，初值为100 void? consumer(void)????// 顾客进程{??? P(S_CartNum); ???买东西; ???结帐; ???V(S_CartNum); } ??? 例：桌子上有一个水果盘，每一次可以往里面放入一个水果。爸爸专向盘子中放苹果，儿子专等吃盘子中的苹果。把爸爸、儿子看作二个进程，试用P、V操作使这两个进程能正确地并发执行。 ???? 分析：爸爸和儿子两个进程相互制约，爸爸进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。因此该问题为进程间的同步问题。 解： semaphore? S_PlateNum;? // 盘子容量，初值为1 semaphore? S_AppleNum;??// 苹果数量，初值为0 void? father( )??// 父亲进程{ ??? while(1) ??? {??????? P(S_PlateNum); ??????? 往盘子中放入一个苹果; ??????? V(S_AppleNum); ??? } } void? son( )???// 儿子进程{ ??? while(1) ??? {??????? P(S_AppleNum); ??????? 从盘中取出苹果; ??????? V(S_PlateNum); ??????? 吃苹果； ??? } } ???? 例：两个进程PA、PB通过两个FIFO(先进先出)缓冲区队列连接(如图) ??? PA从Q2取消息，处理后往Q1发消息；PB从Q1取消息，处理后往Q2发消息，每个缓冲区长度等于传送消息长度。 Q1队列长度为n，Q2队列长度为m. 假设开始时Q1中装满了消息，试用