进程同步经典问题

题目: 进程同步模拟设计——司机和售票员问题⑴需求分析；本程序的功能是模拟公车的司机和售票员的开门以及行车的过程，其实也就是一个典型的进程同步互斥问题，其中主要的两点是1：司机开车的时候，售票员不能开门，（这里体现的是进程的互斥问题）车停之后，由司机通知售票员开门（这里体现的是进程的同步问题）；2：车门开着的时候，司机不能开车，等售票员把车门关上之后，由售票员通知司机开车。

⑵功能设计（数据结构及模块说明）；本程序的设计原理比较简单，就是两大部分，一是司机的行车操作过程，另一个是售票员的开车门和关车门（以及售票，本程序不讨论售票过程）的过程。

现在来说明如何具体实现司机开车和售票员售票的相关过程。

首先，设置2个私有信号量，分别是司机和售票员的。

其中，司机的私有信号量设置为sj，其初始值为0；售票员的私有信号量为spy，其初始值为1；以上的初值表示的是司机和售票员的行车和开关车门的一个具体初始状态，具体的说也就是当车子停着，车门开着的时候的状态，此时，司机不能开车，只有当售票员售完票之后，通知司机才可以。

用操作系统书上的方法写出的流程图如下：司机售票员这样一来的话，仿照书上的P，V操作，实现司机和售票员之间的同步的过程如下：beginsj,spy;semaphore //设置司机和售票员的私有信号量；sj=0;spy=1; //设置初始值；cobeginprocess 司机 //司机的操作过程；beginL1:P(sj);启动车辆；正常行驶；到站停车；V(spy);goto L1;end;process 售票员 //售票员的操作过程；beginL2:P(spy);开车门；关车门；V(sj);售票；goto L2;end;coend;end;⑶开发平台及源程序的主要部分；根据以上的原理，再结合自己所学的程序开发语言，最后得出：本程序的开发平台是c++平台，其中源程序的代码如下：#include<iostream>using namespace std;int spy=1, sj=0; //信号量的定义，spy是售票员的私有信号量，sj 是司机的私有信号量。

例题1（北京大学1999年）有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：(1)一次只能存人一种产品（(A或B);(2)一N< A产品数量一B产品数量＜M其中，N和M是正整数。

试用“存放A’和‘存放B’以及P操作和V操作描述产品A和产品B的人库过程。

解答：应先将表达式转换成制约条件，不可在程序中直接使用该表达式将表达式分解为：B产品数量—A产品数量<NA产品数量—B产品数量＜M可这样理解：(1)若只放人A产品，而不放入B产品，则A产品最多可放M—1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为M—1），当计数器值为0时，进程程A被阻塞；每当放入一个B产品，则可令A产品的计数器增加1，表明A产品可以多一次放入产品的机会；同理，(2)若只放人B产品，而不放入A产品，则B产品最多可；放N一1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为N—1）。

当计数器值为0时，进程B被阻塞；每当放人一个A产品，则可令B产品的计数器增加1，表明B产品可以多一次放入产品的机会。

由此可见，该问题是一个同步控制问题。

又因为一次仅允许一种产品人库，设置信号量mutex控制粮进程互斥访问临界资源（仓库）。

过程如下：beginmutex:＝1;Sa := M-1;Sb := N-1；ParbeginA产品beginrepeatP (Sa)；P (mutex)；A人库；V (mutex)；V (Sb)；Until false;End;B产品beginrepeatP (Sb)；P (mutex)；B人库；V (mutex)；V (Sa)；Until false;End;rend;例题2（华中理工大学1999年试题）设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客在汽车不断地到站，停车，行驶过程中，这两个活动有什么同步关系？并用信号灯的P, V操作实现它们的同步。

课程设计题目进程同步模拟设计—哲学家就餐学院计算机科学与技术专业计算机科学与技术班级计算机姓名指导教师20011 年 1 月19 日需求分析1.1问题描述有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，即共5只筷子。

每个哲学家的行为是思考和进餐。

为了进餐，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。

思考时则同时将两支筷子放回原处（此图中以叉子代表筷子）规则：只有拿到两只筷子时，哲学家才能吃饭；如果筷子已经在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子；任何一个哲学家在自己没有拿到两只筷子吃饭之前，决不放下自己手中的筷子。

由此出现的问题：可能出现死锁问题，因为当五个哲学家都饥饿时，都拿着一支筷子，这样就可能五个哲学家都用不上餐1.2问题分析该问题可用记录型信号量或者是AND型信号量解决。

记录型信号量解决：经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量组成信号量数组。

当哲学家饥饿时总是先拿其左边的筷子，成功后，再去拿右边的筷子，又成功后方可就餐。

进餐完，又先放下他左边的筷子，再放下右边筷子。

这个算法可以保证不会有两个相邻的哲学家同时就餐，但有可能引起死锁。

AND型信号量解决：在哲学家就餐过程中，要求每个哲学家先获得两个临界资源后方能就餐，这在本质上就是AND同步问题，故用AND信号量机制可获得最简洁的解法。

1.3解决方法对于死锁问题可采取这样的几种解决方法：(1)至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终总会释放出他所用过的两只筷子，从而可使更多的哲学家进餐；(2)仅当左右两只筷子均可用时，才允许哲学家拿起筷子就餐(3)规定奇数号哲学家先拿起右边筷子，然后再去拿左边筷子，而偶数号哲学家则相反。

(4)把筷子顺序编号 fk0, fk1, fk2, fk3, fk4，给每个哲学家分配筷子时，必须依从小号到大号（或者相反顺序）进行。

第三章一.选择题（50题）1.以下_B__操作系统中的技术是用来解决进程同步的。

A.管道B.管程C.通道2.以下_B__不是操作系统的进程通信手段。

A.管道B.原语C.套接字D.文件映射3.如果有3个进程共享同一程序段，而且每次最多允许两个进程进入该程序段，则信号量的初值应设置为_B__。

4.设有4个进程共享一个资源，如果每次只允许一个进程使用该资源，则用P、V 操作管理时信号量S的可能取值是_C_。

,2,1,0,-1,1,0,-1,-2C.1,0,-1,-2,-3,3,2,1,05.下面有关进程的描述，是正确的__A__oA.进程执行的相对速度不能由进程自己来控制B.进程利用信号量的P、V操作可以交换大量的信息C.并发进程在访问共享资源时，不可能出现与时间有关的错误、V操作不是原语操作6.信号灯可以用来实现进程之间的_B_。

A.调度B.同步与互斥C.同步D.互斥7.对于两个并发进程都想进入临界区，设互斥信号量为S,若某时S=0,表示_B__0A.没有进程进入临界区8.有1个进程进入了临界区C.有2个进程进入了临界区D.有1个进程进入了临界区并且另一个进程正等待进入8.信箱通信是一种_B__方式A.直接通信B.间接通信C.低级通信D.信号量9.以下关于临界区的说法，是正确的_CA.对于临界区，最重要的是判断哪个进程先进入B.若进程A已进入临界区，而进程B的优先级高于进程A,则进程B可以打断进程A而自己进入临界区C.信号量的初值非负，在其上只能做PV操作D.两个互斥进程在临界区内，对共享变量的操作是相同的10.并发是指_C__。

A.可平行执行的进程B.可先后执行的进程C.可同时执行的进程D.不可中断的进程11.临界区是_C__。

A.一个缓冲区B.一段数据区C.一段程序D.栈12.进程在处理机上执行，它们的关系是_C_。

A.进程之间无关，系统是封闭的B.进程之间相互依赖相互制约C.进程之间可能有关，也可能无关D.以上都不对13.在消息缓冲通信中，消息队列是一种__A_资源。

例题：选择题1、当一个进程独占处理器执行时，具有两个特性，即（）。

A、封闭性和可再现性B、独立性和可再现性C、开放性和可再现性D、顺序性和独立性2、对于两个并发进程，设互斥信号量为A，若A=0，则（）。

A、表示有一个进程进入临界区，另一个进程等待进入B、表示有两个进程进入临界区C、表示有一个进程进入临界区D、表示没有进程进入临界区3、进程并发执行时，执行结果与其执行的（）有关。

A、绝对速度B、时间C、速度D、相对速度4、造成进程结果不正确的因素与进程占用处理器的时间、执行的速度及外界的影响有关。

而这些因素都与时间有关，所以称为（）。

A、时间因素B、与时间有关的错误C、时间错误D、时间问题5、P、V操作是对（）进行操作。

A、信号量B、执行速度C、执行时间D、执行结果5、两个进程合作完成一个任务，在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的（）。

A、调度B、执行C、同步D、互斥6、信号量被定义为一个整型变量，其初始值是（）。

A、0B、无任何限制C、负整数D、非负数填空题：1、并发进程间的关系可以是（）的，也可以是有（）的。

2、在用P、V操作实现同步时，一定要根据具体的问题来定义（）和调用（）。

3、每执行一次P原语操作，信号量s的数值减1，如果s>=0，该进程（）；若s<0，则（）该进程，并把它插入该（）对应的（）队列中，重新进行进程调度。

综合应用题1、假定有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。

当缓冲器中无数时，进程R可将M输入设备上读入的数存放到缓冲器B中；若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。

同时规定：进程R必须等缓冲器中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器中的数只能打印一次；W1和W2都不能从空的缓冲器中取数。

经典进程的同步问题之——⽣产者消费者1 、利⽤记录型信号量解决⽣产者——消费者问题假定在⽣产者和消费者之间的公⽤缓冲池，具有n个缓冲区，这时可利⽤互斥信号量mutex实现诸进程对缓冲池的互斥使⽤。

利⽤信号量empty和full分别表⽰缓冲池中空缓冲区和满缓冲区的数量。

只要缓冲区未满⽣产者便可将消息送⼊缓冲区，只要缓冲区未空消费者便可从缓冲区取⾛⼀个消息。

1 Var mutex,empty,full:semapthore:=1,n,0; // 声明互斥信号量mutex=1,n个空缓冲区,满缓冲区个数为02 buffer:array[0,1,...,n-1] of item;3in,out:integer:=0,0; // 输⼊、输出指针4 begin5 parbegin6 proceducer:begin7 repeat8 ...9 proceducer an item nextp; // ⽣产⼀个产品10 ...11 wait(empty); // 申请⼀个空缓冲区12 wait(mutex); // 申请⼀个临界资源使⽤权13 buffer(in):=nextp;// 将产品放⼊缓冲池中14in:=(in+1) mod n; // 输⼊指针向前移⼀个位置15 signal(mutex); // 释放临界资源16 signal(full); // 释放⼀个满缓冲区17 until false;18 end19 consumer:begin20 repeat21 wait(full); // 申请⼀个满缓冲区22 wait(mutex); // 申请⼀个临界资源使⽤权23 nextc:=buffer(out); // 从缓冲池取⾛⼀个产品24out:=(out+1) mod n; // 输出指针向前移⼀个位置25 signal(mutex); // 释放临界资源26 signal(empty); // 释放⼀个空缓冲区27 consumer the item in nextc;28 until false29 end30 parend31 end2、利⽤AND信号量解决⽣产者——消费者问题（看懂了上⾯的详细分析，下⾯的伪代码就容易理解多了）1 Var mutex,empty,full:semapthore:=1,n,0;2 buffer:array[0,...,n-1] of item;3in out:integer:=0,0;4 begin5 parbegin6 proceducer:begin7 repeat8 ...9 proceduce an item in nextp;10 ...11 Swait(empty,mutex); // 同时申请⼀个空缓冲区和临界资源使⽤权12 buffer(in):=nextp;13in:=(in+1)mod n;14 Ssignal(mutex,full); // 同时释放⼀个临界资源和满缓冲区15 until false16 end17 consumer:begin18 repeat19 Swait(full,mutex);20 Nextc:=buffer(out);21 Out:=(out+1)mod n;22 Ssignal(mutex,empty);23 consumer the item in nextc;24 until false;25 end26 parend27 end。

【转】进程同步之信号量机制（pv操作）及三个经典同步问题上篇博客中（），我们对临界区，临界资源，锁机制详细解读了下，留下了⼀个问题，就是锁机制只能判断临界资源是否被占⽤，所以他解决了互斥问题，但是他不能确定前⾯的进程是否完成，所以他不能⽤于同步问题中。

下⾯就为你讲解信号量机制是如何解决这⼀问题的。

1.信号量机制信号量机制即利⽤pv操作来对信号量进⾏处理。

什么是信号量？信号量（semaphore）的数据结构为⼀个值和⼀个指针，指针指向等待该信号量的下⼀个进程。

信号量的值与相应资源的使⽤情况有关。

当它的值⼤于0时，表⽰当前可⽤资源的数量；当它的值⼩于0时，其绝对值表⽰等待使⽤该资源的进程个数。

注意，信号量的值仅能由PV操作来改变。

⼀般来说，信号量S³0时，S表⽰可⽤资源的数量。

执⾏⼀次P操作意味着请求分配⼀个单位资源，因此S的值减1；当S<0时，表⽰已经没有可⽤资源，请求者必须等待别的进程释放该类资源，它才能运⾏下去。

⽽执⾏⼀个V操作意味着释放⼀个单位资源，因此S的值加1；若S£0，表⽰有某些进程正在等待该资源，因此要唤醒⼀个等待状态的进程，使之运⾏下去。

2.PV操作什么是PV操作？p操作（wait）：申请⼀个单位资源，进程进⼊经典伪代码wait(S){while(s<=0)<span style="white-space:pre"> </span>//如果没有资源则会循环等待；;S-- ;}v操作（signal）：释放⼀个单位资源，进程出来signal(S){S++ ;}p操作（wait）：申请⼀个单位资源，进程进⼊v操作（signal）：释放⼀个单位资源，进程出来PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进⾏操作，具体定义如下：P（S）：①将信号量S的值减1，即S=S-1；②如果S<=0，则该进程继续执⾏；否则该进程置为等待状态，排⼊等待队列。

1、测量控制系统中的数据采集任务把所采集的数据送一单缓冲区；计算任务则从该缓冲区中取出数据并进行计算。

试写出利用信号量机制实现两者共享单缓冲区的同步算法。

Var Sempty，Sfull: semaphore:= 1,0BeginParbeginCollection:beginrepeat采集一个数据；wait(Sempty);数据放入缓冲区；signal(Sfull);untill false;end;Compute:beginrepeatwait(Sfull);从缓冲区取出数据;signal(Sempty);计算;` until false;end;ParendEnd2、有一阅览室，共有100个座位。

读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。

读者离开时要注销掉登记内容。

试用wait和signal原语描述读者进程的同步问题。

var mutex, readcount :semaphore := 1,100; BeginParbeginProcess Reader:beginrepeatwait(readcount);wait(mutex);<填入座号和姓名完成登记>；signal(mutex);<阅读>wait(mutex)<删除登记表中的相关表项，完成注销>signal(mutex);signal(readcount);until false;end;parend;End;1）、桌上有一空盘，只允许放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子；女儿专吃盘中的苹果，儿子专吃盘中的桔子；试用wait 和signal原语实现爸爸、妈妈、女儿、儿子之间的同步问题。

var Sempty, Sapple, Sorange,: semaphore:= 1,0,0; beginparbeginFather: beginrepeatwait(Sempty);<put apple in tray>;signal(Sapple);until false;end;Mother: beginrepeatwait(Sempty);<put orange in tray>;signal(Sorange);until false;end;Son: beginrepeatwait(Sorange);<take orange>;signal(Sempty);until false;end;Daughter: beginrepeatwait(Sapple);<take apple>;signal(Sempty);until false;end;parend;end;1、在4×100米接力赛中，4个运动员之间存在如下关系，运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交给运动员3，运动员3也只有在接到运动员2传来的棒后才能跑，他跑完100米后交给运动员4，运动员4接到棒后跑完全程。

4.10经典进程互斥同步问题：哲学家进餐问题（the dining philosophers problem）问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支，哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。

要考虑的问题是如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子。

在这里，哲学家的生活规律是：Repeat思考；取fork[i];取fork[(i+1) mod 5]；进食；放fork[i];放fork[(i+1) mod 5]；Until false;实现方法：一个信号量表示一根筷子，五个信号量构成信号量数组chop[5]，所有信号量初始值为1。

第i个哲学家的进餐过程为：思考问题P(chop[i]);P(chop(i+1) mod 5]);进餐V(chop[i]);V(chop[(i+1) mod 5]);该算法可保证两个相邻的哲学家不能同时进餐，但不能防止五位哲学家同时拿起各自左边的筷子、又试图拿起右边的筷子，这会引起死锁。

这里给出可以防止死锁发生的一种解决方案：Semaphore fork[5] = {1};Semaphore room = 4;Void philospher (int i) {while (true) {thinking();P( room );P(fork[i]);P(fork[(i+1) mod 5])eating();V(fork[i]);V(fork[(i+1) mod 5])V(room); }。

【例1】有三个进程PA 、PB 和PC 协作解决文件打印问题：PA 将文件记录从磁盘读入内存的缓冲区1中，每执行一次读一个记录；PB 将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC 将缓冲区2中的内容打印出来，每执行一次打印一个记录。

缓冲区的大小与记录大小一样。

请用信号量来保证文件的正确打印。

答：该文件打印过程的同步算法可描述如下：【例2】进程A1、A2、…An1通过m 个缓冲区向进程B1、B2、…Bn2不断地发送消息。

发送和接收工作遵循如下规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。

（2）对于每一个消息，B1、B2、…Bn2都需各接收一次，读入自己的数据区内。

（3）m 个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。

试用wait,signal 操作描述它们的同步关系。

分析：本题是生产者－消费者问题的一个变形。

由于每个缓冲区都只写一次，但要读n2次，故我们可将每个缓冲区看成是由n2格组成的。

只有当某个缓冲区的n2格都空闲时，才允许写入，而且写一次缓冲区相当于将该缓冲区的n2格全部写一遍。

Bj 进程从缓冲中取消息时，它只取相应缓冲的第j 格。

由于每个Bj 取消息的速度不同，故需为它们分别设置指针outj ，用来指示从哪个缓冲区的第j 格中取消息。

答：我们将每个缓冲区看成是由n2格组成的，可为本题设置下列信号量：mutex,初值为1，用来实现对缓冲区的互斥访问；empty[i](i=1,…,n2)，初值均为m ，每个empty[i]对应于缓冲池的第i 格中的所有空闲缓冲区；full[i](i=1,…,n2)，初值均为0，对应缓冲池第i 格中装有消息的缓冲区。

另外还需要提供整型变量in 用来指示将消息放入哪个缓冲区，outj(j=1,…,n2)用来指示Bj 从哪个缓冲区中取消息，这些变量的初值均为0。

Ai,Bj 的算法描述如下：【例3】设有两个生产者进程A 、B 和一个销售进程C ，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。

第二章进程管理（三）进程同步5、经典同步问题1、生产者—消费者问题生产者消费者问题是一种同步问题的抽象描述。

计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。

这些资源可以是硬件资源，也可以是软件资源。

当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。

而当某一进程释放某一资源时，它就相当于生产者。

问题1：设某计算进程CP和打印进程IOP共用一个单缓冲区，CP进程负责不断地计算数据并送入缓冲区T中，IOP进程负责不断地从缓冲区T中取出数据去打印。

通过分析可知，ＣＰ、ＩＯＰ必须遵守以下同步规则：(1)当ＣＰ进程把计算结果送入缓冲区时，IOP进程才能从缓冲区中取出结果去打印;(2)当IOP进程把缓冲区中的数据取出打印后，ＣＰ进程才能把下一个计算结果送入缓冲区.(3)为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。

两个进程的同步可以描述如下：问题2：一组生产者通过具有N个缓冲区的共享缓冲池向一组消费者提供数据。

问题分析”：为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用empty表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用full表示，初值为０。

由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。

由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为１。

问题的解：注意：在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对的出现对资源信号量empty和full的P和V操作，同样需要成对地出现，但它们分别处于不同的程序中。

在每个程序中的多个P操作顺序不能颠倒。

先同步后互斥。

生产者进程缓冲池消费者进程1┇┇i┇┇2、哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。