操作系统 第3章 进程管理 PV操作专题

本课程内容•第1章绪论•第2章操作系统用户界面•第3章进程管理•第4章处理机调度•第5章存储管理•第8章文件系统•第9章设备管理例1：有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名，读者离开时，要删掉登记的信息，阅览室共有100个座位，试问：（1）为描写读者动作，应编写几个程序，应设置几个进程？进程与程序间关系如何？（2）试问P、V操作写出这些进程间的同步算法。解法1：（1）因阅览室有100个座位可容纳100个读者同时阅读，基于这种并行性，因此可为每一个读者设立一个进程。因为任何读者进出阅览室都做相同的工作（登记阅读和取消登记）。所以对于100个读者进程可以共同对应一个程序。此程序功能是入室时查表登记，入室阅读和离室时查表取消登记。（2）设置信号量（S位）来表示空座位个数，初值为100，用来控制进入阅览室的读者进程个数不超过100。设置信号量（S表）来表示被共享的登记表这一临界资源。初值为1，用来防止两个以上读者进程同时查表。每个进程和其他进程之间的同步关系如下：解法2：（1）将读者入室查表登记和离室查表取消登记各编一个程序，这样每个读者需设两个进程，分别执行入室和离室程序。（2）原设信号量S位为座位入室进程私有信号量，增设离室进程私有信号量S人---入室读者数，初值为0，这时进程间的同步关系如下：例2.设有一个作业流自动处理系统，其处理过程是：（1）只要卡片机上有作业，作业输入进程就把卡片机上的作业信息逐个地输入到后缓存储器，并建立后备作业队列。（2）当内存无作业运行时，作业调度进程从后备作业队列中挑选一个作业，把该作业信息从后缓存储器调入内存。（3）作业处理进程负责处理已调入内存的作业。请写出输入进程、作业调度进程、作业处理进程之间的同步算法。提示：（1）输入进程与作业调度进程的同步算法用P、V原语写出。（2）作业调度进程与作业处理进程的同步算法用消息缓冲通讯原语写出。解答：（1）输入进程和调度进程要共享作业后备队列（临界资源），因此设置一个后备队列公有信号量S队，用于保证两个进程对队列的互斥存取。其初值为1。另外，输入进程与调度进程必须同步，因此设置一个调度进程私有信号量S计，用于表示队列中JCB的个数，其初值为0。（2）调度就能成先向处理进程“发信”，请求处理作业，然后等待处理进程处理完毕的回答。“等待回答”（“接收”）保证了处理进程未处理完一个作业之前，调度进程不再调度新作业。处理进程首先要等待调度进程的处理要求，（收信）才能进行作业处理。当作业处理完毕后，处理进程应“发信”回答调度进程，使之再调度下一作业。它们之间的关系如下所示：例3.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。COBEGINPROCESSPI(I=1，2，……)begin；进入售票厅；购票；退出；end；COEND(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。解答：(1)定义一信号量S，初始值为20。意义：S0S的值表示可继续进入售票厅的人数S=0表示售票厅中已有20名顾客(购票者)S0|S|的值为等待进入售票厅的人数(2)上框为P(S),框为V(S)(3)S的最大值为20,S的最小值为20－n注：信号量的符号可不同(如写成t)，但使用时应一致(即上述的s全应改成t)。例4：桌上有一只盘子，最多可以容纳M只水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果（Apple），妈妈专向盘子中放桔子（Orange），两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。解答：设信号量place、apple、orange和mutex分别表示盘子里能放水果的数目、盘子里已放入的苹果数目和盘子里已放入的桔子的数目和对盘子的互斥访问，其初值分别为m、0、0和1，其同步与互斥关系描述如下：intplace=m;intapple=0;intorange=0;intmutex=1;main(){father();mother();son();daughter();}father(){while(1){p(place);p(mutex)placeapple;v(mutex);v(apple);}}mother(){while(1){p(place);p(mutex)placeorange;v(mutex);v(orange);}}son(){while(1){p(apple);p(mutex)takeapple;v(mutex);v(place);}}daughter(){while(1){p(orange);p(mutex)takeorange;v(mutex);v(place);}}例5：三个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容读出并读入到缓冲区2，每执行一次读出并读入一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区1的大小和m个记录大小一样，缓冲区2的大小和n个记录大小一样。请用P、V操作来保证文件的正确打印。解答：设置四个信号量empty1、empty2、full1、full2、mutex1和mutex2，信号量empty1和empty2分别表示缓冲池1和缓冲池2是否为空，其初值为m和n；信号量full1和full2分别表示缓冲池1和缓冲池2是否有记录供读出，其初值均为0；信号量mutex1和mutex2分别表示对缓冲池1和缓冲池2的访问互斥，其初值为1。其进程间的同步与互斥关系如下：intempty1=m;intempty2=n;intfull1=0;intfull2=0;intmutex1=1;intmutex2=1;main(){PA();PB();PC();}PA(){while(1){从磁盘读出一个文件记录；p(empty1);p(mutex1);将一个文件记录读入缓冲池1；v(mutex1);v(full1);}}PB(){while(1){p(full1);p(mutex1);从缓冲区1中读出一个文件记录；v(mutex1);v(empty1);p(empty2);p(mutex2);将一个记录读入缓冲区2；v(mutex2)；v(full2);}}PC(){while(1){p(full2);p(mutex2);从缓冲池2读出一个文件记录打印；v(mutex2);v(empty2);}}例6：有三个进程A、B、C，其中A与B构成一对生产者和消费者，共享一个由n个缓冲区块组成的缓冲池1；B与C也构成一对生产者与消费者，共享另一个由m个缓冲块组成的缓冲池2。用P、V操作描述它们之间的同步关系。解答：设置四个信号量empty1、empty2、full1和full2，其同步关系描述如下：intempty1=n;/*表示缓冲池1中的空缓冲区数*/intempty2=m;/*表示缓冲池2中的空缓冲区数*/intfull1=0;/*表示缓冲池1中装满产品的缓冲区数*/intfull2=0;/*表示缓冲池2中装满产品的缓冲区数*/main(){cobeginPA();PB();PC();Coend}PA(){while(1){生产一件产品；P(empty1);将一件产品放入缓冲池1；V(full1);}}PB(){while(1){P(full1);从缓冲池1中取出一件产品；V(empty1);P(empty2);将一件产品放入缓冲池2；V(full2);}}PC(){while(1){P(full2);从缓冲池2中取出一件产品；V(empty2);}}例7：两个山崖间有一根铁索，山崖两边各有一群猴子，任何时候同时只能有一个方向的猴子通过铁索。使用P、V操作写出山崖两边的猴子过铁索的算法。解答：一个山上的猴子就是一群读者，第二个山上的猴子为另一群读者，两群读者互斥使用铁索。设信号量waymutex表示山两边的猴子对铁索的互斥共享，初值为1；设m1count和m2count表示对两边猴子的记数，其初值为0；设m1mutex和m2mutex表示两群猴子中各猴子互斥访问记数变量的信号量，初值都为1，其同步与互斥的算法如下：intwaymutex=1;intm1mutex=1,m2mutex=1;intm1count=0,m2count=0;main(){cobeginmonkeygroup1();monkeygroup2();coend}monkeygroup1(){while(1){P(m1mutex);ifm1count=0thenP(waymutex);m1count=m1count+1;V(m1mutex)……P(m1mutex);m1count=m1count-1;ifm1count=0thenV(waymutex);V(m1mutex)}}monkeygroup2(){while(1){P(m2mutex);ifm2count=0thenP(waymutex);m2count=m2count+1;V(m2mutex)……P(m2mutex);m2count=m2count-1;ifm2count=0thenV(waymutex);V(m2mutex)}}例2：思考题东西★☆☆☆过隧道的问题思想：每边的第一个进程抢互斥信号灯，后边的进程跟进;每边的最后一个进程释放互斥信号灯。问题：要计数，而且计数时应互斥；SBmutexBASA程序描述:main(){mutex=1/*互斥信号灯SB=1；/*B边计数互斥信号灯SA=1；/*A边计数互斥信号灯countA=0；countB=0；cobeginwhile(A边还有人){A进程()}；while(B边还有人){B进程()}；coend}A边进程()｛到隧道口P(SA)countA=countA+1if(countA==1)P(mutex)V(SA)进隧道．．．．．．出隧道P(SA)countA=countA－1if(countA==0)V(mutex)V(SA)}B边进程()｛到隧道口P(SB)countB=countB+1if(countB==1)P(mutex)V(SB)进隧道．．．．．．出隧道P(SB)countB=countB－1if(countB==0)V(mutex)V(SB)}更进一步的考虑：当令一边有人等待时，能否规定每边能跟进的最多人数？例8：考虑过河的例子，用P、V操作设计一个算法要求该算法能确保若干人从同一岸同时过河而不死锁。解答如下：intwait[2]={1,0};ints=1,mutex[2]={1,1},rc[2]={0,0};p(s);//与河对面争夺过河权p(wait[i]);//互斥过桥p(mutex[i]);rc[i]++;if(rc[i]==1)p(wait[(i+1)mod2]);//如果是第一个则控制对方过河权v(mutex[i]);passriver;v(wait[i]);v(s);p(mutex[i]);rc[i]--;if(rc[i]==0)v(wait[(i+1)mod2]);//如果是最后一个则释放对方过河权v(mutex[i])例9：进程A通过一个缓冲区不断地向进程B、C、D发送信息，A每向缓冲区送入一个信息后，必须等进程B、C、D都取走后才可以发送下一个信息，B、C、D对A送入的每一信息各取一次，试用P、V操作实现它们之间的正确通讯。解答：解答：设置信号量intRab=1；/*表示进程B对进程A送入的信息取了一次*/intRac=1；/*表示进程C对进程A送入的信息取了一次*/i