操作系统生产与消费者问题

一、生产者和消费者问题1、有n个缓冲区，一个生产者和一个消费者情况：main(){intS=1;//可否进入缓冲区intfull=0;//产品数目intempty=n//可用缓冲区数intbuffer[n];intin=0;//指向下一个可放产品的缓冲区intout=0;//指向下一个可取产品的缓冲区producer();consumer();}producer(){While(生产未结束){produceaproductP(empty);P(S);Buffer[in]=product;in=(in+1)modn;V(S);V(full);}}consumer(){While(消费未结束){P(full);P(S);TakeaproductfromBuffer[out]Out=(out+1)modn;V(S);V(empty);}Consumetheproduct}2、m个生产者和k个消费者共享n个缓冲区的情况：main(){intB[n];//缓冲区intp=r=0;//p表示生产者指针，r表示消费者指针intS=1;//可否进入缓冲区intfull=0;//产品数目intempty=n;//可用缓冲区数producer-i(i=1,2,…,m);consumer-j(j=1,2,…,k);}Producer-i(i=1,2,…,m){while(producingdoesnotend){produceaproductP(empty);P(S);B[p]=product;p=(p+1)modn;//每放入一个产品，位置指针后移一位V(S);V(full);}}Consumer-j(j=1,2,…,k){while(continuetoconsume){P(full);P(S);TakeaproductfromB[r]r=(r+1)modn;//从第一个开始，消费一个后，指向下一个V(S);V(empty);Consume}}二、读者与写者问题1、读者与写者有相同的优先级的情况：main(){intS=1;//读者与写者，写者与写者间的互斥，即可否修改文件intSr=1;//可否修改读者个数intrc=0;//读者个数reader();writer();}reader(){While(读过程未结束){P(Sr);if(rc==0){P(S);rc=rc+1;V(Sr);readfileF}else{rc=rc+1;V(Sr);readfileF}P(Sr);rc=rc-1;if(rc==0)V(S);V(Sr);}}writer(){While(写过程未结束){P(S);WritefileFV(S);}}2、写者优先问题：main(){intS=1;//读者与写者，写者与写者间的互斥，即可否修改文件intSn=n;//最多有n个进程可以同时进行读操作reader();writer()}reader(i){P(S);P(Sn);V(S);ReadfileFV(Sn);}writer(j){P(S)WritefileFV(S);}例题1、有一个阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括座号、姓名。读者离开时要撤消登记信息。阅览室有100个座位，试问：（1）为描述读者的动作，应编写几个程序？，应该设置几个进程？进程和程序之间的关系如何？（2）试用P、V操作描述这些进程之间的同步算法。2、若系统有某类资源m*n+1个，允许作业执行过程中动态申请该类资源，但在该系统上运行的每一个作业对该类资源的占有量在任一时刻都不会超过m+1个。当作业申请资源时，只要资源尚未分配完，则总能满足它的要求。但用限制系统中可同时执行的作业个数来防止死锁。你认为作业调度允许同时执行的最大作业数应为多少？证明之。3、若系统有同类资源m个，被n个进程共享，试问：当mn和mn，每个进程最多可申请多少个这类资源而使系统一定不会发生死锁？4、设Pa,Pb,Pc为一组合作进程，其进程流程图如下所示。试用信号灯的P、V操作实现这三个进程的同步。SFPaPbPc5、医生给病人看病，需要化验，于是医生开出化验单，病人到化验室化验，化验结果送回医生处供医生诊断。医生看病为一个进程，化验室化验为一个进程，二者需要交换信息，试用信号灯的P、V操作实现这两个进程的同步关系。6、设有两个优先级相同的进程P1、P2如下：令信号量S1,S2的初值为0，试问P1、P2并发运行结束后X=?y=?z=?进程P1进程P2y=1;x=1;y=y+2;x=x+1;V(S1);P(S1);Z=y+1;x=x+y;P(S2);V(S2);Y=z+y;z=x+z;7、在一个盒子里，混装了数量相等的围棋白子和黑子。现在要用自动分拣系统把白子和黑子分开。该系统设有两个进程P1、P2，其中P1将拣白子，P2将拣黑子。规定每个进程每次只拣一子。当一进程正在拣子时，不允许另一进程去拣，当一进程拣了一子时，必须让另一进程去拣。试写出两个并发进程能正确执行的程序。8、桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的橘子。试用P、V操作写出他们能同步的程序。Main(){IntSp=1;//是否有空盘子IntSa=0;//盘中是否有苹果IntSo=0;//盘中是否有橘子Pf();Pm();Pd();Ps();}Pf(){P(Sp);向盘中放苹果;V(Sa);}Pm(){P(Sp);向盘中放橘子;V(So);}Pd(){P(Sa);取盘中的苹果;V(Sp);}Ps(){P(So);取盘中的橘子;V(Sp);}9、桌上有一只盘子，最多可容纳两个水果。每次只能放入一个或取出一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，两个女儿专等吃盘中的苹果，两个儿子专等吃盘中的橘子。试用P、V操作写出他们能同步与互斥的程序。（南京大学）Main(){IntS=1;//是否可以更改盘子内的空间数Intempty=2;//盘子内的初始空间数IntSa=0;//盘中是否有苹果IntSo=0;//盘中是否有橘子Pf();Pm();Pd_i();Ps_j();}Pf(){P(empty);P(S);向盘中放苹果;V(S);V(Sa);}Pm(){P(empty);P(S);向盘中放橘子;V(S);V(So);}Pd_i(){P(Sa);P(S);取盘中的苹果;V(S);V(empty);}Ps_j(){P(So);P(S);取盘中的橘子;V(S);V(empty);}10、某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚提水入缸，老和尚从缸中取水饮用。水缸可容纳10桶水，水取自同一水井中，水井径窄，每次只能容一个水桶取水。水桶总数为3个，每次入、取缸水仅为1桶，且不可同时进行。试给出取水、入水的算法描述。（北京邮电大学）Main(){Intmutex1=1;//是否可以使用水井Intmutex2=1;//是否可以使用水缸Intempty=10;//水缸初始空间数Intfull=0;//水缸满否Intcount=3;//水桶初始个数Pin_i();//入水进程Pout_j();//取水进程}Pin_i(){P(empty);//水缸满否？满则阻塞入水进程P(count);//申请打水的桶P(mutex1);//互斥使用水井从井中取水V(mutex1);P(mutex2);//互斥使用水缸向缸中入水V(mutex2);V(full);//水缸多了一桶水V(count);//归还水桶}Pout_j(){P(full);水缸是否有水？无则阻塞取水进程P(count);//申请取水的桶P(mutex2);//互斥使用水缸从缸中取水V(mutex2);V(empty);//水缸少了一桶水V(count);//归还水桶}11、有一个理发师，有n张可供顾客等待理发的椅子，如果没有顾客，则理发师睡觉；如果有一顾客进入理发店发现理发师在睡觉，则把他叫醒进行理发，如果理发师正在理发时又有顾客来到，若有空椅子，就在空椅子上等待，若没有空椅子就离开理发店。写一个算法描述理发师和顾客之间的关系。要求不能带有竞争条件。（西安电子科技大学）Main(){Intmutex=1;//可否修改顾客数Intwakeup=0;//理发师等唤醒的信号Intwait=0;//顾客是否可以等待Intrc=0;//初始顾客数P1();//顾客进程P2();//理发师进程}P1(){P(mutex);//可否修改顾客数rc=rc+1;if(rc==1)//如果是第一个顾客就唤醒理发师V(wakeup);else{if(rc=n)//当顾客人数少于n时，在椅子上等待P(wait);else{rc=rc-1;该顾客离开理发店}}V(mutex);}P2(){P(wakeup);//理发师睡觉，等待被唤醒While(rc!=0){理发P(mutex);rc=rc-1;if(rc!=0)V(wait);//让等待中的一个顾客理发V(mutex);}}12、如何让五个哲学家吃通心面问题满足同步机制。解：改变5个哲学家申请叉子的顺序。规定奇数号的哲学家先拿起他左边的叉子，然后再去拿右边的叉子；偶数号的哲学家则正好相反。即：拿到一个叉子的哲学家才有权拿另一个叉子，而没有拿到叉子的哲学家则退出竞争。Pi(i=0,1,2,3,4)(){Thinkforawhileif(odd(i))//若为奇数号{P(fork(i+1)MOD5);P(fork(i));}else{P(fork(i));P(fork(i+1)MOD5);}EatforawhileV(fork(i));V(fork(i+1)MOD5);}