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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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个单位缓冲区的有界缓冲上。其中，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();/*,缓冲满时，生产者睡眠,*/,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;/*指针推进*/,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),信号量：一种软资源,原语：内核中执行时不可被中断的过程,P操作原语和V操作原语,记录型信号量与,PV操作(3),信号量和P、V操作，将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。,一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,记录型信号量与,PV操作(4),通过信号量传送信号，进程使用P、V两个特殊操作来发送和接收信号，如果进程相应的信号仍然没有送到，进程被挂起直到信号到达为止。,操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。,实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,记录型信号量与,PV操作(7),信号量的值(-2),信号量队列指针,信号量分类,信号量按其用途分为,公用信号量：,私有信号量：,信号量按其取值分为,二元信号量：,一般信号量：,整型信号量,设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)的进程被置成等待信号量s的状态。,V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,记录型信号量(2),type semaphore=record,value:integer;,queue:list of process;,End,procedure 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);,begin,s:=s+1;,/*把信号量加1*/,if s=1,then begin,Xi:=Xi-1;Aj:=Xi;,V(mutex);输出一张票；,end;,else begin,V(mutex);输出票已售完；,end;,goto L1;,end;,Var A:ARRAY1.m OF integer;,s:ARRAY1.m OF semaphore;,sj:=1;,cobegin,process Pi,var Xi,:integer;,begin,L1:,按旅客定票要求找到,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),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子,哲学家吃通心面,问题(2),哲学家吃通心面,问题(3),var fork,i,:array0.4 of semaphore;,fork,i,:=1;,cobegin,process Pi /i=0,1,2,3,4,begin,L1:,思考；,P(forki)；,P(fork(i+1)mod 5)；,吃通心面；,V(forki)；,V(fork(i+1)mod 5)；,goto L1;,end;,coend;,有若干种办法可避免这类死锁,上述解法可能出现永远等待，有若,干种办法可避免死锁：,至多允许四个哲学家同时吃；,奇数号先取左手边的叉子，偶数号先取右手边的叉子；,每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,哲学家吃通心面,问题的一种正确解,var fork,i,:array0.4 of semaphore;,fork,i,:=1;,cobegin,process Pi,/*i=0,1,2,3*/,begin,L1:,思考；,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;,生产者消费者问题,一个生产者、一个消费者共享一个缓冲区,一个生产者、一个消费者共享多个缓冲区,多个生产者、多个消费者共享多个缓冲区,多个生产者、多个消费者共享一个缓冲区,多个生产者、一个消费者共享多个缓冲区,一个生产者、多个消费者共享多个缓冲区,一个生产者、一个消费者共享一个缓冲区的,解,var B:integer;,empty:semaphore;/*,可以使用的空缓冲区数,*/,full:semaphore;/*,缓冲区内可以使用的产品数,*/,empty:=1;/*,缓冲区内允许放入一件产品,*/,full:=0;/*,缓冲区内没有产品*,/,cobegin,Process producer process consumer,begin begin,L1: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;/*,放入/取出缓冲区指针*/,c,obegin,process producer_i process consumer_j,Begin begin,L1: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)，妈妈专向盘子中放桔于(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果,记录型信号量解决苹果桔子问题,plate:integer;,sp:semaphore；,/*盘子里可以放几个水果*/,sg1:semaphore;/*盘子里有桔子*/,sg2:semaphore;/*盘子里有苹果*/,sp:=1;/*盘子里允许放一个水果*/,Sg1,:=0;/*盘子里没有桔子*/,sg2:=0;/*盘子里没有苹果*/,cobegin,process father,begin,L1:,削一个苹果,；,P(sp);,把苹果放入,plate；,V(sg2);,goto L1;,end;,process mother,begin,L2:,剥一个桔子,；,P(sp);,把桔子放入,plate；,V(sg1);,goto L2;,end;,process son,begin,L3:P(sg1);,从plate中取桔子；,V(sp);,吃桔子；,goto L3;,end;,process daughter,begin,L4:P(sg2);,从plate中取苹果；,V(sp);,吃苹果；,goto L4;,end;,coend,读者写者问题,有两组并发进程：读者和写者，共享一个文件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);