PV练习及参考解答.doc

PV原语通过操作信号量来处理进程间的同步与互斥的问题(如:经典的生产者-消费者问题)。其核心就是一段不可分割不可中断的程序,从而实现进程同步。信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一种新的变量类型(semaphore)来记录当前可用资源的数量(如:生产者进程中的资源和消费者中的资源信号量:空位置数empty和产品数full)。    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//注意以下表示方法,cobegin和coend之间的是并发进程main() { cobegin A(); B(); coend}A(){ while(1){ wait(S); 拣黑子; signal(S);}}B(){ while(1){ wait(S); 拣白子; signal(S);}}       例2:某超市门口为顾客准备了100辆手推车,每位顾客在进去买东西时取一辆推车,在买完东西结完帐以后再把推车还回去。试用P、V操作正确实现顾客进程的同步互斥关系。    分析进程及关系:把手推车视为某种资源,每个顾客为一个要互斥访问该资源的进程。因此这个例子为PV原语的第二种应用类型。    解:信号量定义 semaphore S_CartNum;    //: