计算机操作系统教程.ppt

1、计算机操作系统教程,P、V操作,P、V操作的引入,为禁止两个进程同时进入临界区，使用了锁操作方法。 但这带来两个问题： 1.当临界资源被占用，不停的测试会造成错误。 2.无法实现同步 为此E.W.Dijkstra提出了一种解决同步，互斥问题的更一般的方法，这就是信号量以及有关的P、V操作,信号量,信号量是表示资源的实体，是一个与队列有关的整型变量，其值只能由P、V操作来改变。 操作系统利用信号量对进程和资源进行控制和管理。 根据用途的不同，分为公用信号量和私用信号量。公用信号量通常用于实现进程之间的互斥，初值为1，他所联系的一组并发进程均可对其实施P,V操作；私用信号量一般用于实现进程间的同步

2、，初值为0或为某个正整数n，仅允许拥有它的进程对其实施P、V操作。,P、V操作的定义,P、V操作是定义在信号量S上的两个操作。 P(S): (1）S:=S-1; (2) 若S=0，则调用P(S)的进程继续运行。 (3)若S0,则调用P(S)的进程被阻塞，并把它插入到等待信号量S的阻塞队列中,V(S): (1)S:=S+1; (2)若S0,则调用V(S)的进程继续运行； (3)若S=0，从等待信号量S的阻塞队列中唤醒头一个进程，然后调用V(S)的进程继续运行,对P、V操作的分析： 当信号量的初值为1时，如果有若干个进程都要求进入临界区时，由于每个进程都要调用P(S)过程，则只有第一个调用P(S)

3、的进程，执行P操作而使S为0，立即进入临界区；而其余进程在执行完P操作后，由于S变为负值而进入阻塞，被插入到等待信号量S的阻塞队列中。由于信号量的初值为1，P操作起到限制一次只有一个进程进入临界区的作用。任何一个进程，在执行完临界区操作后，在退出临界区前必须调用V操作，从而保证了进程在临界区内逗留有限时间，当一个进程进退出临界区时，如有进程在等待进入临界区，V操作将唤醒位于阻塞队列中的头一个进程，使其可以进入临界区，因而不会出现进程无限等待进入临界区的情况这完全符合对临界区管理的三条原则。,对P、V操作的分析：（续） 信号量S0时的数值表示某类可用资源的数量，执行P操作意味着申请分配一个单位的

4、资源。因此可描述为S:=S-1，当S0时，表示已无资源可用，此时S的绝对值表示信号量S的阻塞队列中的进程数；而执行一次V操作意味着释放一个单位的资源，描述为S:=S+1,若此时S=0，表明信号量地阻塞队列中仍有被阻塞额进程，因此在执行V操作时应唤醒该队列的第一个进程,互斥模式,S:=1 进程P1 进程P2 P(S) P(S) S1 S2 V(S) V(S) 分析：由于信号量的初值为1，故第一个进程P1执行P操作后信号量减为0,表明临界资源空闲，可分配给该进程，使之进入临界区。若此时又有第二个进程P2欲进入临界区，也应先执行P操作。结果使S=-1，表示临界资源已被占用，因此第二进程变为阻塞状态，

5、当第一个进程在临界区内将S1执行完后再执行V操作，释放该资源而使信号量恢复到0，有唤醒了第二个进程P2。待第二个进程P2完成对临界资源的使用（S2）后，有执行V操作，最后信号量恢复到初值1.,同步模式,进程P1 进程P2 L1：P(S) L2：V(S) 分析：设进程P1先到达L1点，当它执行P(S)时，使S=-1； 于是P1进入阻塞状态并进入信号量S的阻塞队列； 然后进程P2到达L2点，当它执行到V(S)时，将S值变为0，于是唤醒P1,使其转变为就绪状态，当再次调度到进程P1时，则P1可在L1点后继续运行下去，由此可见，当进程P1到达L1时，除非进程P2已过了L2点，否则进程P1就要暂停执行，

6、这就是说，P1在L1点必须与进程P2进行同步。在这种同步操作中，进出那个P1受到进程P2的制约，而进程P2却不受进程P1的制约，所以是非对称的。,P、V操作举例,例1：假定某一时刻，观察者已记录了N辆车，又在记录下一辆车，此时，报告者也开始工作。 观察者 begin L：observe a lorry； count := count +1； goto L end；,执行顺序1： （观察者）count := count + 1; （报告者）report; （报告者）count := 0; 这是正确的结果。,报告者 begin print count； count := 0； end；,执行顺序2

7、： （报告者）report count; （观察者）count := count +1; （报告者）count := 0; 观察者刚刚记录的一辆车的信息丢失了 造成不正确的因素是与进程占用处理器的时间、 执行的速度以及外界的影响有关。这些因素都与时间 有关，所以，称它们为“与时间有关的错误”,例2：飞机航班有N个售票处，每个售票处通过终端访问系统的公共数据区。,售票处1 begin 从数据单元中取出现 有余票； 做减1操作； 把结果送回到数据单元 end;,售票处2 begin 从数据单元中取出现 有余票； 做减1操作； 把结果送回到数据单元 end;,假定现有余票为1 执行顺序： （售票处1

8、）从数据单元中取出现有余票； （售票处2）从数据单元中取出现有余票； （售票处1）做减1操作； （售票处1）把结果送回到数据单元； （售票处2）做减1操作； （售票处2）把结果送回到数据单元； 结果是把一张票卖给了两个顾客。 与时间有关的错误产生的原因：多个进程不受限制的对同一数据对象进行存取操作。,用P、V操作实现售票系统的互斥 将S定义为信号量，初值为1，余票的数量值放在整型变量A中。,PROCESS Pi r : integer; begin P(S); r := A; if r = 1 then begin r := r 1; A := r; V(S); 售出一张票; end else

9、 售出票已售完; end；,PROCESS Pi r : integer; begin P(S); r := A; if r = 1 then begin r := r 1; A := r; V(S); 售出一张票; end else begin V(S); 售出票已售完 end end；,例3：有m个生产者和r个消费者共享容量为n的缓冲器（m、r、n均大于1）。每个生产者把自己生产的物品存入缓冲区，每个消费者从缓冲区中取出物品去消费。要求用P、V操作对这些生产者和消费者进行正确管理。 定义：整型数组：B0n-1 整型变量：k，t 初值均为0 信号量：S1：初值1 用于生产者放入物品 S2：初

10、值1 用于消费者取出物品 SP：初值n 缓冲区是否可用 SG：初值0 缓冲区里是否有物品,PROCESS Pi begin L1: produce a product; P(SP); P(S1); Bk := product; k := (k + 1) mod n; V(S1); V(SG); goto L1 end,PROCESS Cj begin L2: P(SG); P(S2); take a product from Bt; t := (t + 1) mod n; V(S2); V(SP); consume; goto L1 end,生产者分别向缓冲区送产品，由S1控制互斥访问。 消费

11、者分别从缓冲区中取出产品，由S2控制互斥访问,例4：读者写者问题： 规定：允许多个进程同时读；只允许一个进程写；当有进程读时不允许其它进程写。 第一种方案：定义信号量：S: semaphore；初值1；定义一个整数：rs ，初值0；,读者： PROCESS Readeri begin rs := rs + 1; if rs = 1 then P(S); read file F; rs := rs 1; if rs = 0 then V(S); end;,写者： PROCESS Writerj begin P(S); write file F; V(S); end; 问题：对共享变量rs访问的程

12、序段也是临界区。,课后练习,24有一阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一作为列出了一个表目，包括座号，姓名。读者离开时要撤销登记信息。阅览室有100个作为，试问： (1)为描述读者的动作，应编写几个程序，应该设置几个进程？进程和程序之间的对应关系如何？ （2)试用P,V操作描述这些进程之间的同步算法。 分析：设读者有任意多个，但能同时阅览的只能100人，所以，设一个信号量S代表空座位数目，初值为100，用它来控制进入阅览室的读者进程不超过100。另设信号量m，用于控制对登记表这一共享资源的互斥使用，其初值为1。,(1)需编写一个程序，100个进程，进程之间通过登记表之间存

13、在同步关系,（2）Process 第i个读者进程 begin P(S); P(m); 填写登记表； V(m); 坐下阅览; P(m); 在登记表上去掉登记； V(m); V(S); goto L1; end,25设有两个优先级相同的进程P1，P2如下所示。令信号量S1，S2的初值为0，试问P1，P2并发运行结束后，x=? ,y=? ,z=? 进程P1 进程P2 y:=1; x:=1; y:=y+2; x:=x+1; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=x+y z:=x+z X=5, y8， Z 9.,28.桌上有一只盘子，每次只能放一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中方桔子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的桔子，试用P、V操作写出他们能同步的程序。,semaphore S_Plate=1, S_Apple=0, S_Orange=0;,void father( ) / 父亲进程 while(1) P(S_Plate); 往盘子中放入一个苹果； V(S_Apple); ,void mother( ) / 母亲进程 while(1) P(S_Plate); 往盘子中放入一个桔子； V(S_Orange