信号量与PV操作

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.3 信号量与,PV操作,同步与同步机制,信号量与PV操作,信号量实现互斥,信号量解决五个哲学家吃通心面问题,信号量解决生产者-消费者问题,记录型信号量解决读者-写者问题,记录型信号量解决理发师问题,3.3.1 同步和同步机制,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。,在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。,解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,生产者-消费者问题表述,有界缓冲问题,有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,生产者-消费者问题算法描述(1),int k;,typedef anyitem item; /item类型,item bufferk;,int in=0,out=0,counter=0;,生产者-消费者问题算法描述(2),process producer(void) ,while (true) /无限循环,produce an item in nextp;/生产一个产品,if (counter=k) /缓冲满时，生产者睡眠,sleep(producer);,bufferin=nextp;/将一个产品放入缓冲区,in=(in+1)%k; /指针推进,counter+; /缓冲内产品数加1,if(counter=1) /缓冲为空，加进一件产品,wakeup(consumer);/并唤醒消费者,生产者-消费者问题算法描述(3),process consumer(void) ,while (true) /无限循环,if (counter=0) /缓冲区空，消费者睡眠,sleep(consumer);,nextc=bufferout;/取一个产品到nextc,out=(out+1)%k; /指针推进,counter-; /取走一个产品，计数减1,if(counter=k-1) /缓冲满了，取走一件产品并唤,wakeup(producer); /醒生产者,consume the item in nextc;/消耗产品,生产者-消费者问题的算法描述(4),生产者和消费者进程对counter的交替执行会使其结果不唯一,生产者和消费者进程的交替执行会导致进程永远等待,竞争条件(Race Condition),counter+,could be implemented as,register1 = counter register1 = register1 + 1 count = register1,counter-,could be implemented as,register2 = counter register2 = register2 - 1 counter = register2,Consider this execution interleaving with “counter = 5” initially:,S0: producer execute,register1 = counter,register1 = 5,S1: producer execute,register1 = register1 + 1,register1 = 6,S2: consumer execute,register2 = counter,register2 = 5,S3: consumer execute,register2 = register2 - 1,register2 = 4,S4: producer execute,counter = register1,counter = 6 ,S5: consumer execute,counter = register2,counter = 4,生产者-消费者问题算法描述(3),process consumer(void) ,while (true) /无限循环,if (counter=0) /缓冲区空，消费者睡眠,sleep(consumer);,nextc=bufferout;/取一个产品到nextc,out=(out+1)%k; /指针推进,counter-; /取走一个产品，计数减1,if(counter=k-1) /缓冲满了，取走一件产品并唤醒生产者,wakeup(producer);,consume the item in nextc;/消耗产品,生产者-消费者问题算法描述(2),process producer(void) ,while (true) /无限循环,produce an item in nextp;/生产一个产品,if (counter=k) /缓冲满时，生产者睡眠,sleep(producer);,bufferin=nextp; /将一个产品放入缓冲区,in=(in+1)%k; /指针推进,counter+; /缓冲内产品数加1,if(counter=1) /缓冲为空，加进一件产品,wakeup(consumer); /并唤醒消费者,信号量与,PV操作(1),前节种种方法解决临界区调度问题的缺点:,1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。,2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。,1965年提出新的同步工具-信号量和P、V操作。,信号量与,PV操作(2),信号量：一种软件资源,原语：内核中执行时不可被中断的过程,P操作原语和V操作原语,一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,信号量与,PV操作(3),操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。,实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,信号量的值(-2),信号量队列指针,信号量分类,信号量按其用途分为,公用信号量：,私有信号量：,信号量按其取值分为,二元信号量：,一般信号量：,一般信号量(1),设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue, P和V操作原语定义：,P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。,V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,一般信号量(2),typedef struct semaphore ,int value; /信号量值,struct pcb *list; /信号量队列指针,;,void P(semaphore &s) ,s.value-;,if(s.value0),W(s.list);,void V(semaphore &s) ,s.value+;,if(s.value=0),R(s.list);,一般信号量(3),推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数,推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数,推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作,二元信号量(1),设s为一个记录型数据结构,一个分量为value,它仅能取值0和1,另一个分量为信号量队列queue, 把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：,二元信号量(2),typedef struct binary_semaphore ,int value; /value取值0 or 1,struct pcb *list; ;,void BP(binary_semaphore &s) ,if(s.value=1),s.value=0;,else,W(s.list);,void BV(binary_semaphore &s) ,if(s.list is empty( ),s.value=1;,else,R(s.list);,信号量实现互斥,semaphore mutex;,mutex=1;,cobegin,process Pi( ) /i=1,n,P(mutex);,临界区;,V(mutex);,coend,信号量解决五个哲学家吃通心面问题(1),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子,信号量解决五个哲学家吃通心面问题(2),哲学家吃通心面,问题(3),semaphore fork5;,for (int i=0;i5;i+),forki=1;,cobegin,process philosopher_i( ) ,/i= 0,1,2,3,4,while(true) ,think( );,P(forki);,P(fork(i+1)%5);,eat( );,V(forki);,V(fork(i+1)%5);,coend,有若干种办法可避免这类死锁,上述解法可能出现永远等待，有若,干种办法可避免死锁：,至多允许四个哲学家同时吃；,奇数号先取左手边的叉子，偶数号先取右手边的叉子；,每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,哲学家吃通心面,问题的一种正确解,semaphore fork5;,for (int i=0;i5;i+),forki= 1;,cobegin,process,philosopher_i( ),/*i=0,1,2,3 */,while(true) ,think( )；,P(forki；,/*i=4,P(fork0)*/,P(fork,(i+1)%5,),；,/*i=4,P(fork4)*/,eat( )；,V(forki)；,V(fork(i+ 1 % 5)；,coend,信号量解决生产者消费者问题,一个生产者、一个消费者共享一个缓冲区,一个生产者、一个消费者共享多个缓冲区,多个生产者、多个消费者共享多个缓冲区,一个生产者、一个消费者共享一个缓冲区的,解,int B;,semaphore empty; /可以使用的空缓冲区数,semaphore full; /缓冲区内可以使用的产品数,empty=1; /缓冲区内允许放入一件产品,full=0; /缓冲区内没有产品,cobegin,process producer() process consumer(),while(true) while(true) ,produce( ); P(full);,P(empty); take( ) from B;,append( ) to B; V(empty);,V(full); consume( );, , ,coend,多个生产者/消费者、共享多个缓冲区的,解,item Bk;,semaphore empty;empty=k; /可以使用的空缓冲区数,semaphore full; full=0; /缓冲区内可以使用的产品数,semaphore mutex;mutex=1; /互斥信号量,int in=0; /放入缓冲区指针,int out=0; /取出缓冲区指针,cobegin,process producer_i ( ) process consumer_j ( ),while(true) while(true) ,produce( ); P(full);,P(empty); P(mutex);,P(mutex); take( ) from Bout;,append to Bin; out=(out+1)%k;,in=(in+1)%k; V(mutex);,V(mutex); V(empty);,V(full); consume( );, , ,coend,3.3.6 信号量解决读者-写者问题(1),有两组并发进程：读者和写者，共享一个文件F，要求：,允许多个读者同时执行读操作,任一写者在完成写操作之前不允许其它读者或写者工作,写者执行写操作前，应让已有的写者和读者全部退出,信号量解决读者写者问题(2),int readcount=0,;/读进程计数,semaphore writeblock,mutex;,writeblock=1;mutex=1;,信号量解决读者写者问题(3),cobegin,process reader_i( ) process writer_j( ),P(mutex); P(writeblock);,readcount+; 写文件;,if(readcount=1) V(writeblock);,P(writeblock);,V(mutex);,读文件;,P(mutex);,readcount-;,if(readcount=0),V(writeblock);,V(mutex);,Coend,信号量解决读者写者问题(3),cobegin,process reader_i( ) process writer_j( ),P(mutex); P(writeblock);,readcount+; 写文件;,if(readcount=1) V(writeblock);,P(writeblock); ,V(mutex);,读文件;,P(mutex);,readcount-;,if(readcount=0),V(writeblock);,V(mutex);,coend,信号量解决读者写者问题(3),cobegin,process reader_i( ) process writer_j( ),P(mutex); P(writeblock);,readcount+; 写文件;,if(readcount=1) V(writeblock);,P(writeblock); ,V(mutex);,读文件;,P(mutex);,readcount-;,if(readcount=0),V(writeblock);,V(mutex);,coend,信号量解决理发师问题(1),理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子,如果没有顾客，理发师便在理发椅上睡觉,一个顾客到来时，它必须叫醒理发师,如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开,信号量解决理发师问题(2),int waiting=0;/,等候理发顾客坐的椅子数,int CHAIRS=N; /,为顾客准备的椅子数,semaphore customers,barbers,mutex;,customers=0;barbers=0;mutex=1;,信号量解决理发师问题(3),cobegin,process barber( ) ,while(true) ,P(customers); /有顾客吗？若无顾客，理发师睡眠,P(mutex); /若有顾客时，进入临界区,waiting-; /等候顾客数少一个,V(barbers); /理发师准备为顾客理发,V(mutex); /退出临界区,cut_hair(); /理发师正在理发(非临界区),process customer_i( ) ,P(mutex); /进入临界区,if(waitingCHAIRS) /有空椅子吗,waiting+; /等候顾客数加1,V(customers); /唤醒理发师,V(mutex); /退出临界区,P(barbers); /理发师忙，顾客坐下等待,get_haircut(); /否则顾客坐下理发,else,V(mutex); /人满了，走吧！,Coend,信号量解决理发师问题(3),cobegin,process barber( ) ,while(true) ,P(customers);/有顾客吗？若无顾客，理发师睡眠,P(mutex); /若有顾客时，进入临界区,waiting-; /等候顾客数少一个,V(barbers); /理发师准备为顾客理发,V(mutex); /退出临界区,cut_hair(); /理发师正在理发(非临界区),信号量解决理发师问题(3),process customer_i( ) ,P(mutex); /进入临界区,if(waitingCHAIRS) /有空椅子吗,waiting+; /等候顾客数加1,V(customers); /唤醒理发师,V(mutex); /退出临界区,P(barbers); /理发师忙，顾客坐下等待,get_haircut(); /否则顾客坐下理发,else,V(mutex); /人满了，走吧！,coend,