ch3-3.3信号量与PV操作

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同步和同步机制•著名的生产者--消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。•在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。•解决好生产者--消费者问题就解决好了一类并发进程的同步问题。生产者--消费者问题表述有界缓冲问题•有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。生产者-消费者问题算法描述(1)•intk;•typedefanyitemitem;//item类型•itembuffer[k];•intin=0,out=0,counter=0;生产者-消费者问题算法描述(2)•processproducer(void){•while(true){//无限循环•{produceaniteminnextp};//生产一个产品•if(counter==k)//缓冲满时，生产者睡眠•sleep(producer);•buffer[in]=nextp;//将一个产品放入缓冲区•in=(in+1)%k;//指针推进•counter++;//缓冲内产品数加1•if(counter==1)//缓冲为空，加进一件产品•wakeup(consumer);//并唤醒消费者•}•}生产者-消费者问题算法描述(3)•processconsumer(void){•while(true){//无限循环•if(counter==0)//缓冲区空，消费者睡眠•sleep(consumer);•nextc=buffer[out];//取一个产品到nextc•out=(out+1)%k;//指针推进•counter--;//取走一个产品，计数减1•if(counter==k-1)//缓冲满了，取走一件产品并唤•wakeup(producer);//醒生产者•{consumetheiteminnextc};//消耗产品•}•}生产者-消费者问题的算法描述(4)•生产者和消费者进程对counter的交替执行会使其结果不唯一•生产者和消费者进程的交替执行会导致进程永远等待RaceCondition•counter++couldbeimplementedasregister1=counterregister1=register1+1count=register1•counter--couldbeimplementedasregister2=counterregister2=register2-1counter=register2•Considerthisexecutioninterleavingwith“counter=5”initially:S0:producerexecuteregister1=counter{register1=5}S1:producerexecuteregister1=register1+1{register1=6}S2:consumerexecuteregister2=counter{register2=5}S3:consumerexecuteregister2=register2-1{register2=4}S4:producerexecutecounter=register1{counter=6}S5:consumerexecutecounter=register2{counter=4}生产者-消费者问题算法描述(3)•processconsumer(void){•while(true){//无限循环•if(counter==0)//缓冲区空，消费者睡眠•sleep(consumer);•nextc=buffer[out];//取一个产品到nextc•out=(out+1)%k;//指针推进•counter--;//取走一个产品，计数减1•if(counter==k-1)//缓冲满了，取走一件产品并唤•wakeup(producer);//醒生产者•{consumetheiteminnextc};//消耗产品•}•}生产者-消费者问题算法描述(2)•processproducer(void){•while(true){//无限循环•{produceaniteminnextp};//生产一个产品•if(counter==k)//缓冲满时，生产者睡眠•sleep(producer);•buffer[in]=nextp;//将一个产品放入缓冲区•in=(in+1)%k;//指针推进•counter++;//缓冲内产品数加1•if(counter==1)//缓冲为空，加进一件产品•wakeup(consumer);//并唤醒消费者•}•}3.3.2信号量与PV操作(1)•前节种种方法解决临界区调度问题的缺点:1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。•1965年E.W.Dijkstra提出了新的同步工具--信号量和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)•typedefstructsemaphore{•intvalue;//信号量值•structpcb*list;//信号量队列指针•};•voidP(semaphore&s){•s.value--;•if(s.value0)•W(s.list);•}•voidV(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)•typedefstructbinary_semaphore{•intvalue;//value取值0or1•structpcb*list;};•voidBP(binary_semaphore&s){•if(s.value==1)•s.value=0;•else•W(s.list);•}•voidBV(binary_semaphore&s){•if(s.listisempty())•s.value=1;•else•R(s.list);•}3.3.3信号量实现互斥•semaphoremutex;•mutex=1;•cobegin•processPi(){//i=1,…,n•P(mutex);•{临界区};•V(mutex);•}•coend信号量解决五个哲学家吃通心面问题(1)有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子信号量解决五个哲学家吃通心面问题(2)哲学家吃通心面问题(3)semaphorefork[5];for(inti=0;i5;i++)fork[i]=1;cobeginprocessphilosopher_i(){//i=0,1,2,3,4while(true){think();P(fork[i]);P(fork[(i+1)%5]);eat();V(fork[i]);V(fork[(i+1)%5]);}}coend有若干种办法可避免这类死锁上述解法可能出现永远等待，有若干种办法可避免死锁：•至多允许四个哲学家同时吃；•奇数号先取左手边的叉子，偶数号先取右手边的叉子；•每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。哲学家吃通心面问题的一种正确解semaphorefork[5];for(inti=0;i5;i++)fork[i]=1;cobeginprocessphilosopher_i(){/*i=0,1,2,3*/while(true){think()；P(fork[i]；/*i=4,P(fork[0])*/P(fork[(i+1)%5])；/*i=4,P(fork[4])*/eat()；V(fork[i])；V(fork([i+1]%5)；}}coend3.3.5信号量解决生产者消费者问题①一个生产者、一个消费者共享一个缓冲区②一个生产者、一个消费者共享多个缓冲区③多个生产者、多个消费者共享多个缓冲区一个生产者、一个消费者共享一个缓冲区的解•intB;•semaphoreempty;//可以使用的空缓冲区数•semaphorefull;//缓冲区内可以使用的产品数•empty=1;//缓冲区内允许放入一件产品•full=0;//缓冲区内没有产品•cobegin•processproducer(){processconsumer(){•while(true){while(true){•produce();P(full);•P(empty);take()fromB;•append()toB;V(empty);•V(full);consume();•}}•}}coend多个生产者/消费者、共享多个缓冲区的解•itemB[k];•semaphoreempty;empty=k;//可以使用的空缓冲区数•semaphorefull;full=0;//缓冲区内可以使用的产品数•semaphoremutex;mutex=1;//互斥信号量•intin=0;//放入缓冲区指针•intout=0;//取出缓冲区指针•cobegin•processproducer_i(){processconsumer_j(){•while(true){while(true){•produce();P(full);•P(empty);P(mutex);•P(mutex);take()fromB[out];•appendtoB[in];out=(out+1)%k;•in=(in+1)%k;V(mutex);•V(mutex);V(empty);•V(full);consume();•}}•}}•coe