信号量与PV操作ppt课件

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.7记录型信号量处理理发师问题3.3.1 同步和同步机制v著名的消费者-消费者问题是计算机操作系统中并发进程内在关系的一种笼统，是典型的进程同步问题。v在操作系统中，消费者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接纳进程等等。v处理好消费者-消费者问题就处理好了一类并发进程的同步问题。消费者-消费者问题表述 有界缓冲问题有n个消费者和m个消费者，衔接在一个

2、有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只需缓冲区未满，消费者pi消费的产品就可投入缓冲区；只需缓冲区不空，消费者进程cj就可从缓冲区取走并耗费产品。消费者-消费者问题算法描画(1)vint k;vtypedef anyitem item; /item类型vitem bufferk;vint in=0,out=0,counter=0;消费者-消费者问题算法描画(2)vprocess producer(void) vwhile (true) /无限循环vproduce an item in nextp;/消费一个产品vif (counter=k) /缓冲满时，消费者睡眠v s

3、leep(producer);vbufferin=nextp;/将一个产品放入缓冲区vin=(in+1)%k; /指针推进vcounter+; /缓冲内产品数加1vif(counter=1) /缓冲为空，加进一件产品v wakeup(consumer);/并唤醒消费者vv 消费者-消费者问题算法描画(3)vprocess consumer(void) vwhile (true) /无限循环vif (counter=0) /缓冲区空，消费者睡眠v sleep(consumer);v nextc=bufferout;/取一个产品到nextcv out=(out+1)%k; /指针推进v count

4、er-; /取走一个产品，计数减1vif(counter=k-1) /缓冲满了，取走一件产品并唤v wakeup(producer); /醒消费者vconsume the item in nextc;/耗费产品vv 消费者-消费者问题的算法描画(4)v消费者和消费者进程对counter的交替执行会使其结果不独一 v消费者和消费者进程的交替执行会导致进程永远等待竞争条件(Race Condition)vcounter+ could be implemented as register1 = counter register1 = register1 + 1 count = register1vc

5、ounter- could be implemented as register2 = counter register2 = register2 - 1 counter = register2vConsider this execution interleaving with “counter = 5 initially:vS0: producer execute register1 = counter register1 = 5vS1: producer execute register1 = register1 + 1 register1 = 6vS2: consumer execute

6、 register2 = counter register2 = 5 vS3: consumer execute register2 = register2 - 1 register2 = 4vS4: producer execute counter = register1 counter = 6 vS5: consumer execute counter = register2 counter = 4消费者-消费者问题算法描画(3)vprocess consumer(void) vwhile (true) /无限循环vif (counter=0) /缓冲区空，消费者睡眠v sleep(con

7、sumer);v nextc=bufferout;/取一个产品到nextcv out=(out+1)%k; /指针推进v counter-; /取走一个产品，计数减1vif(counter=k-1) /缓冲满了，取走一件产品并唤醒消费者v wakeup(producer); vconsume the item in nextc;/耗费产品vv 消费者-消费者问题算法描画(2)vprocess producer(void) vwhile (true) /无限循环vproduce an item in nextp;/消费一个产品vif (counter=k) /缓冲满时，消费者睡眠v sleep(

8、producer);vbufferin=nextp; /将一个产品放入缓冲区vin=(in+1)%k; /指针推进vcounter+; /缓冲内产品数加1vif(counter=1) /缓冲为空，加进一件产品v wakeup(consumer); /并唤醒消费者vv 3.3.2信号量与PV操作(1)v前节种种方法处理临界区调度问题的缺陷:v 1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。v 2)将测试能否进入临界区的责任推给各个竞争的进程会减弱系统的可靠性，加重了用户编程负担。v1965年E.W.Dijkstra提出新的同步工具-信号量和P、V操作。v 信号量与PV操作(2)

9、v信号量：一种软件资源v原语：内核中执行时不可被中断的过程vP操作原语和V操作原语v一个进程在某一特殊点上被迫停顿执行直到接纳到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程协作需求都可以经过适当的信号构造得到满足。信号量与PV操作(3)v操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。v实现时，信号量是一种记录型数据构造，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。信号量的值(-2) 信号量队列指针信号量分类信号量按其用途分为 公用信号量： 私有信号量：信号量按其取值分为 二元信号量： 普通讯号量：普通讯号量(1) 设s为一

10、个记录型数据构造,一个分量为整形量value,另一个为信号量队列queue, P和V操作原语定义： P(s)；将信号量s减去l，假设结果小于0，那么调用P(s)的进程被置成等待信号量s的形状。 V(s)：将信号量s加1，假设结果不大于0，那么释放一个等待信号量s的进程。普通讯号量(2)vtypedef struct semaphore vint value; /信号量值vstruct pcb *list; /信号量队列指针v ; vvoid P(semaphore &s) v s.value-; v if(s.value0) v W(s.list); v vvoid V(semapho

11、re &s) vs.value+; v if(s.value=0) v R(s.list); v 普通讯号量(3)v推论1：假设信号量s为正值，那么该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实践还可以运用的物理资源数v推论2：假设信号量s为负值，那么其绝对值等于登记陈列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数v推论3：通常，P操作意味着恳求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作二元信号量(1)v设s为一个记录型数据构造,一个分量为

12、value,它仅能取值0和1,另一个分量为信号量队列queue, 把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：二元信号量(2)v typedef struct binary_semaphore v int value; /value取值0 or 1v struct pcb *list; ;vvoid BP(binary_semaphore &s) vif(s.value=1)v s.value=0;velsev W(s.list);vvvoid BV(binary_semaphore &s) vif(s.list is empty( )v s.val

13、ue=1;velsev R(s.list);v3.3.3信号量实现互斥v semaphore mutex;v mutex=1;v cobeginv process Pi( ) /i=1,nv P(mutex);v 临界区;v V(mutex);v v coend信号量处理五个哲学家吃通心面问题(1) 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思索、饥饿、然后吃通心面。为了吃面，每个哲学家必需获得两把叉子，且每人只能直接从本人左边或右边去取叉子 信号量处理五个哲学家吃通心面问题(2)哲学家吃通心面问题(3)semaphore fork5

14、;for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(forki); P(fork(i+1)%5);eat( ); V(forki); V(fork(i+1)%5); coend有假设干种方法可防止这类死锁 上述解法能够出现永远等待，有假设 干种方法可防止死锁：至多允许四个哲学家同时吃；奇数号先取左手边的叉子，偶数号先取右手边的叉子；每个哲学家取到手边的两把叉子才吃，否那么一把叉子也不取。哲学家吃通心面问题的一种正确解 semaphore fork5; s

15、emaphore fork5; for (int i=0;i5;i+) for (int i=0;i5;i+) forki= 1; forki= 1;cobegincobeginprocess philosopher_i( )/process philosopher_i( )/* *i=0,1,2,3 i=0,1,2,3 * */ /while(true) while(true) think( )think( )；P(forkiP(forki； / /* *i=4,P(fork0)i=4,P(fork0)* */ /P(fork(i+1)%5 )P(fork(i+1)%5 )；/ /* *i=

16、4,P(fork4)i=4,P(fork4)* */ /eat( )eat( )；V(forki)V(forki)；V(fork(i+ 1 % 5)V(fork(i+ 1 % 5)； coendcoend3.3.5信号量处理消费者消费者问题一个消费者、一个消费者共享一个缓冲区一个消费者、一个消费者共享多个缓冲区多个消费者、多个消费者共享多个缓冲区一个消费者、一个消费者共享一个缓冲区的解vint B;vsemaphore empty; /可以运用的空缓冲区数vsemaphore full; /缓冲区内可以运用的产品数vempty=1; /缓冲区内允许放入一件产品vfull=0; /缓冲区内没有产

17、品vcobeginvprocess producer() process consumer()v while(true) while(true) vproduce( ); P(full);vP(empty); take( ) from B;vappend( ) to B; V(empty);vV(full); consume( );v v v coendv多个消费者/消费者、共享多个缓冲区的解vitem Bk;item Bk;vsemaphore empty;semaphore empty;empty=k; /empty=k; /可以运用的空缓冲区数可以运用的空缓冲区数vsemaphore f

18、ull; full=0; /semaphore full; full=0; /缓冲区内可以运用的产品数缓冲区内可以运用的产品数vsemaphore mutex;semaphore mutex;mutex=1; /mutex=1; /互斥信号量互斥信号量vint in=0;int in=0; / /放入缓冲区指针放入缓冲区指针vint out=0; /int out=0; /取出缓冲区指针取出缓冲区指针 vcobegincobeginvprocess producer_i ( ) process consumer_j ( ) process producer_i ( ) process cons

19、umer_j ( ) v while(true) while(true) while(true) while(true) v produce( ); P(full); produce( ); P(full);v P(empty); P(mutex); P(empty); P(mutex);v P(mutex); take( ) from Bout; P(mutex); take( ) from Bout;v append to Bin; out=(out+1)%k; append to Bin; out=(out+1)%k;v in=(in+1)%k; V(mutex); in=(in+1)%

20、k; V(mutex);v V(mutex); V(empty); V(mutex); V(empty);v V(full); consume( ); V(full); consume( );v v vcoendcoendv 3.3.6 信号量处理读者-写者问题(1) 有两组并发进程：读者和写者，共享一个文件F，要求：允许多个读者同时执行读操作任一写者在完成写操作之前不允许其它读者或写者任务写者执行写操作前，应让已有的写者和读者全部退出信号量处理读者写者问题(2)vint readcount=0;/读进程计数vsemaphore writeblock,mutex;vwriteblock=1;m

21、utex=1;信号量处理读者写者问题(3)vcobegincobeginvprocess reader_i( ) process writer_j( )process reader_i( ) process writer_j( )v P(mutex); P(writeblock); P(mutex); P(writeblock);v readcount+; readcount+; 写文件写文件; ;v if(readcount=1) V(writeblock); if(readcount=1) V(writeblock);v P(writeblock); P(writeblock);v v V

22、(mutex); V(mutex);v 读文件读文件; ;v P(mutex); P(mutex);vreadcount-;readcount-;vif(readcount=0)if(readcount=0)v V(writeblock); V(writeblock);vV(mutex);V(mutex);v vCoendCoend信号量处理读者写者问题(3)vcobeginvprocess reader_i( ) process writer_j( )v P(mutex); P(writeblock);v readcount+; 写文件;v if(readcount=1) V(writebl

23、ock);v P(writeblock); v V(mutex);v读文件;v P(mutex);v readcount-;v if(readcount=0)v V(writeblock);v V(mutex);vvcoend信号量处理读者写者问题(3)vcobeginvprocess reader_i( ) process writer_j( )v P(mutex); P(writeblock);v readcount+; 写文件;v if(readcount=1) V(writeblock);v P(writeblock); v V(mutex);v读文件;v P(mutex);v rea

24、dcount-;v if(readcount=0)v V(writeblock);v V(mutex);vvcoend3.3.7信号量处理理发师问题(1)v理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子v假设没有顾客，理发师便在理发椅上睡觉v一个顾客到来时，它必需叫醒理发师v假设理发师正在理发时又有顾客来到，那么假设有空椅子可坐，就坐下来等待，否那么就分开信号量处理理发师问题(2)vint waiting=0;/等候理发顾客坐的椅子数vint CHAIRS=N; /为顾客预备的椅子数vsemaphore customers,barbers,mutex;vcustomers=0;barbers=0;mutex=1;信号量处理理发师问题(3)vcobeginvprocess barbe