《信号量与PV操作》PPT课件.ppt

《《信号量与PV操作》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《信号量与PV操作》PPT课件.ppt（37页珍藏版）》请在三一办公上搜索。

1、3.3 信号量与PV操作,3.3.1同步与同步机制3.3.2记录型信号量与PV操作3.3.3用记录型信号量实现互斥3.3.4记录型信号量解决生产者-消费者问题3.3.5记录型信号量解决读者-写者问题3.3.6记录型信号量解决理发师问题,3.3.1 同步和同步机制,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,生产者-消费者问题表述,有界缓冲问题有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有

2、界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,生产者-消费者问题算法描述(1),var k:integer;type item:any;buffer:array0.k-1 of item;in,out:integer:=0;coumter:integer:=0;,生产者-消费者问题算法描述(2),process producer begin while(TRUE)/*无限循环*/produce an item in nextp;/*生产一个产品*/if(counter=k)sleep();

3、/*缓冲满时，生产者睡眠*/bufferin:=nextp;/*将一个产品放入缓冲区*/in:=(in+1)mod k;/*指针推进*/counter:=counter+1;/*缓冲内产品数加1*/if(counter=1)wakeup(consumer);/*缓冲空了，加进一件产品并唤醒消费者*/end,生产者-消费者问题算法描述(3),process consumer begin while(TRUE)/*无限循环*/if(counter=0)sleep();/*缓冲区空消费者睡眠*/nextc:=bufferout;/*取一个产品到nextc*/out:=(out+1)mod k;/*指

4、针推进*/counter:=counter-1;/*取走一个产品，计数减1*/if(counter=k-1)wakeup(producer);/*缓冲满了，取走一件产品并唤醒生产者*/consume thr item in nextc;/*消耗产品*/end,记录型信号量与PV操作(1),前节种种方法解决临界区调度问题的缺点:1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。1965年E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。,记录型信号量与PV操作(2),信号量：一种软

5、资源原语：内核中执行时不可被中断的过程P操作原语和V操作原语,记录型信号量与PV操作(3),信号量和P、V操作，将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,记录型信号量与PV操作(4),通过信号量传送信号，进程使用P、V两个特殊操作来发送和接收信号，如果进程相应的信号仍然没有送到，进程被挂起直到信号到达为止。操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。实现时

6、，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,记录型信号量与PV操作(7),信号量分类,信号量按其用途分为 公用信号量：私有信号量：信号量按其取值分为 二元信号量：一般信号量：,整型信号量,设s为一个整形量，除初始化外，仅能通过P、V操作访问，P和V操作原语定义：P(s)：while s0 do null operation s：=s-1；V(s)：s：=s+1；,记录型信号量(1),设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue,P和V操作原语定义：P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程

7、被置成等待信号量s的状态。V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,记录型信号量(2),type semaphore=record value:integer;queue:list of process;Endprocedure P(var s:semaphore);begin s:=s 1;/*把信号量减去1*/if s 0 then W(s);/*若信号量小于0，则调用P(s)的进 程被置成等待信号量s的状态*/end;procedure V(var s:semaphore);begins:=s+1;/*把信号量加1*/if s=0 then R(s);/*

8、若信号量小于等于0，则释放 一个等待信号量s的进程*/end;,记录型信号量(3),推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数,记录型信号量(4),推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数,记录型信号量(5),推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作,二元信号量(1),设s为一个记录型数据结构,一个分量为val

9、ue,它仅能取值0和1,另一个分量为信号量队列queue,把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：,二元信号量(2),type binary semaphore=record value(0,1);queue:list of process end;procedure BP(var s:semaphore);procedure BV(var s:semaphore);begin begin if s.value=1;if s.queue is empty;then s.value=0;then s.value=1;else begin else begin W(

10、s.queue);R(s.queue);end;end;end end,3.3.3记录型信号量解决进程互斥问题,s:semaphore;s:=1;cobegin process Pi begin P(s);临界区；V(s);end;coend;,记录型信号量和PV操作解决机票问题,Var A:ARRAY1.m OF integer;mutex:semaphore;mutex:=1;cobeginprocess Pivar Xi:integer;beginL1:按旅客定票要求找到Aj；P(mutex)Xi:=Aj;if Xi=1 then begin Xi:=Xi-1;Aj:=Xi;V(mute

11、x);输出一张票；end;else begin V(mutex);输出票已售完；end;goto L1;end;,Var A:ARRAY1.m OF integer;s:ARRAY1.m OF semaphore;sj:=1;cobeginprocess Pivar Xi:integer;beginL1:按旅客定票要求找到Aj；P(sj)Xi:=Aj;if Xi=1 then begin Xi:=Xi-1;Aj:=Xi;V(sj);输出一张票；end;else begin V(sj);输出票已售完；end;goto L1;end;coend;,哲学家吃通心面问题(1),有五个哲学家围坐在一圆桌

12、旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子,哲学家吃通心面问题(2),哲学家吃通心面问题(3),var forki:array0.4 of semaphore;forki:=1;cobeginprocess Pi/i=0,1,2,3,4,beginL1:思考；P(forki)；P(fork(i+1)mod 5)；吃通心面；V(forki)；V(fork(i+1)mod 5)；goto L1;end;coend;,有若干种办法可避免这类死锁,上述解法可能出现永

13、远等待，有若 干种办法可避免死锁：至多允许四个哲学家同时吃；奇数号先取左手边的叉子，偶数号先取右手边的叉子；每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,哲学家吃通心面问题的一种正确解,var forki:array0.4 of semaphore;forki:=1;cobeginprocess Pi/*i=0,1,2,3*/beginL1:思考；P(forki)；/*i=4,P(fork0)*/P(forki+1 mod5)/*i=4,P(fork4)*/吃通心面；V(forki)；V(fork(i+1 mod 5)；goto L1;end;coend;,生产者消费者问题,一个生产

14、者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享一个缓冲区多个生产者、一个消费者共享多个缓冲区一个生产者、多个消费者共享多个缓冲区,一个生产者、一个消费者共享一个缓冲区的解,var B:integer;empty:semaphore;/*可以使用的空缓冲区数*/full:semaphore;/*缓冲区内可以使用的产品数*/empty:=1;/*缓冲区内允许放入一件产品*/full:=0;/*缓冲区内没有产品*/cobeginProcess producer process consumer begin begin L

15、1:L2:Produce a product;P(full);P(empty);Product:=B;B:=product;V(empty);V(full);Consume a product;Goto L1;Goto L2;end;end;coend,多个生产者、多个消费者、共享多个缓冲区的解,var B:array0.k-1 of item;empty:semaphore:=k;/*可以使用的空缓冲区数*/full:semaphore:=0;/*缓冲区内可以使用的产品数*/mutex:semaphore:=1;in,out:integer:=0;/*放入/取出缓冲区指针*/cobeginp

16、rocess producer_i process consumer_j Begin beginL1:produce a product;L2:P(full);P(empty);P(mutex);P(mutex);Product:=Bout;Bputptr:=product;out:=(out+1)mod k;In:=(in+1)mod k;V(mutex);V(mutex);V(empty);V(full);Consume a product;Goto L1;Goto L2;end;end;coend,苹果桔子问题,桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈

17、妈专向盘子中放桔于(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果,记录型信号量解决苹果桔子问题,读者写者问题,有两组并发进程：读者和写者，共享一个文件F，要求：允许多个读者同时执行读操作任一写者在完成写操作之前不允许其它读者或写者工作写者执行写操作前，应让已有的写者和读者全部退出,记录型信号量解决读者写者问题(1),var rc,wc:integer:=0;W，R:semaphore;Rc:=0;/*读进程计数*/W:=1;R:=1;,记录型信号量解决读者写者问题(2),procedure read;procedure write;begin begin P(R);P(W);rc:=rc+1;写文件;if rc=1 then P(W)；V(W);V(R);end;读文件；P(R);rc:=rc-1;if rc=0 then V(W)；V(R);end;,理发师问题,理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开,记录型信号量解决理发师问题,