ProcessCommunication第三章-2

操作系统原理PrinciplesofOperatingSystem第3章进程同步与死锁“如果我们只做能力范围以内的事，则永远没有进步。”－爱迪生3本章概要进程同步信号量机制经典进程同步算法进程同步实例研究---linux、windows2003管程进程通信--linux、windows2003死锁§3.3经典同步问题3.3.1生产者——消费者问题问题描述：一组消费者进程一组生产者进程具有n个单元的环型缓冲池生产者-消费者问题是对相互合作的进程之间同步问题的一种抽象，例如，在输入和计算进程间，计算进程是消费者；而在计算和打印进程间，计算进程是生产者。§3.3经典同步问题问题分析：①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。§3.3经典同步问题问题解答：所用信号量设置如下：1）同步信号量empty，可用缓冲区的数目，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用。2）同步信号量full，缓冲区中可用的产品数，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用。3）互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问缓冲池。voidproducer()voidconsumer(){{do{do{……wait(full);produceaproduct;wait(mutex);…………wait(empty);removeanitemfrombuffer;wait(mutex);……;……signal(mutex);addnextptobuffer;signal(empty);…………signal(mutex);consumetheiteminnextc;signal(full);……}while（1）；}while(1);}}§3.3经典同步问题问题思考：（1）如果某进程中的wait操作顺序颠倒了，会怎么样？——如果将生产者进程中的两个wait操作交换次序。（2）如果某程序员漏写了一个signal操作，会怎么样？——如果将生产者进程中的signal(full）去掉。9利用AND信号量解决生产者-消费者问题semaphoremutex=1,empty=n,full=0;itembuffer[n];intin=out=0;voidproducer(){while(1){…produceaniteminnextp;...Swait(empty,mutex);buffer[in]=nextp;in=(in+1)modn;Ssignal(mutex,full);}}10voidconsumer(){while(1){...Swait(full,mutex);nextc=buffer[out];out=(out+1)modn;Ssignal(mutex,empty);...consumetheiteminnextc;…}}main(){cobegin{producer();consumer();}}11考研集锦生产者-消费者问题------应用设有两个生产者进程A、B和一个销售进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库，而且要求生产A产品和B产品的件数满足以下关系：-n≤A的件数-B的件数≤m其中n、m是正整数，但对仓库中A产品和B产品的件数无上述要求，请用信号量机制写出A、B、C三个进程的工作流程。12分析：（1）生产者A、B和消费者C之间，不能同时将产品入库和出库，故仓库是一个临界资源。（2）两个生产者之间必须进行同步。当生产者的A、B产品的件数之差大于等于m时，生产者A必须等待；小于等于-n时，生产者B必须等待。这种关系可想象成有两种令牌，分别跟允许A和B生产的产品数量相关，A和B必须取得对应的令牌后才能生产产品，故这两类令牌也就是两种临界资源。（3）生产者和销售者之间也必有进行同步，只有当生产者生产出产品并入库后，销售者才能进行销售。解：为了互斥地入库和出库，需为仓库设置一初值为1的互斥信号量mutex；为了使生产的产品件数满足：-n≤A的件数－B的件数≤m，需设置两个信号量，其中SAB表示当前允许A生产的产品数量，其初值为m,SBA表示当前允许B生产的产品数量，其初值为n;还需设置一个初值为0的资源信号量S，对应于仓库的产品量。SAB,SBA,S,mutex:semaphore:=m,n,0,1;Main(){A();B();C();}voidA(){repeat{wait(SAB);produceaproductA;signal(SBA);wait(mutex);addtheproductAtothestorehouse;signal(mutex);signal(S);}untilfalse}voidB(){repeat{wait(SBA);produceaproductB;signal(SAB);wait(mutex);addtheproductBtothestorehouse;signal(mutex);signal(S);}untilfalse}VoidC(){repeat{wait(S);wait(mutex);takeaproductAorBfromstorehouse;signal(mutex);selltheproduct;}untilfalse}§3.3经典同步问题3.3.2读者—写者问题问题描述一组读者与一组写者循环访问共享的同一个数据对象。规定：多个读者可以同时读这个数据对象，但决不允许多个写者同时对它进行写操作，也不允许读者、写者同时访问它。如何对读者、写者编程？RRW§3.3经典同步问题问题分析：①读者—写者之间的互斥关系：由于共享的数据对象是临界资源，故可设一个公用的初值为1的互斥信号量wmutex，以保证同时只有1个读者或者写者进程进入临界区访问该数据对象。但是，这样做不仅实现了写者与写者的互斥、写者与读者的互斥，而且也实现了读者与读者的互斥。其实，只有第1个到来的读者和最后1个离开的读者需要与写者进行互斥通信。为此，引入一个读者计数器变量ReadCount。②读者—读者之间新增的互斥关系：读者需互斥地访问RC，故需再设一个初值为1的互斥信号量rmutex。18问题：读者在读过程中：后续读者和写者如何解决：读者优先如果读者来：无读者、写者，新读者可以读有写者等，但有其它读者正在读，则新读者也可以读有写者写，新读者等如果写者来：无读者，新写者可以写有读者，新写者等待有其它写者，新写者等待该算法称为读者优先算法§3.3经典同步问题问题解答：所用信号量和其他变量设置如下：1）互斥信号量wmutex，初值为1，用于实现写者与其他写者或读者互斥地访问共享的数据对象。2）互斥信号量rmutex，初值为1，用于实现诸读者互斥地访问读者计数器变量ReadCount。3）整型变量ReadCount，初值为0，用于对读者进行计数。§3.3经典同步问题读者Readers:while(TRUE){wait(rmutex);Readcount=ReadCount+1;if(ReadCount==1)wait(wmutex);signal(rmutex);执行读操作wait(rmutex);ReadCount=ReadCount-1;if(ReadCount==0)singal(wmutex);singal(rmutex);使用读取的数据}写者Writers：while(TRUE){wait(wmutex);执行写操作singal(wmutex);}main(){reader(1);…reader(n);writer();}21写者优先条件：多个读者可以同时进行读写者必须互斥（只允许一个写者写，也不能读者写者同时进行）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）分析：增加初值为1的信号量s,当至少有一个写者准备访问共享对象时它使后续的读者进程等待；增加初值为0的信号量writecount用于对写者计数;增加初值为1的互斥信号量mutex用来实现多个写者对writecount进行互斥访问22Semaphores=rmutex=wmutex=mutex=1;intreadcount=writecount=0;voidreader(inti){while(1){wait(s);wait(rmutex);readcount++;if(readcount==1)wait(wmutex);signal(rmutex);signal(s);...performreadoperation;...wait(rmutex);readcount--;if(readcount==0)signal(wmutex);signal(rmutex);}}23voidwriter(){while(1){wait(mutex);writecount++;if(writecount==1)wait(s);signal(mutex);wait(wmutex);...performreadoperation;...signal(wmutex);wait(mutex);readcount--;if(readcount==0)signal(s);signal(mutex);}}main(){reader(1);…reader(n);writer();}§3.3经典同步问题考研集锦：设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，管理规则如下：当AB间有车辆在行驶时，同方向的车可以同时驶入AB段，但另一方向的车必须在AB段外等待；当AB段之间无车辆行驶时，到达AB段的任一方向的车都可进入AB段，但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在AB段行驶的车辆驶出了AB段且暂无车辆进入AB段时，应让另一方向等待的车辆进入AB段行驶。试用信号量和wait、signal操作管理AB路段车辆的行驶。BA§3.3经典同步问题问题分析：本题属于读者写者问题的变形，相当于两组读者（即两个方向的车辆）使用同一个共享文件（即AB路段）的互斥问题。因此，可参考读者写者问题的解法。一个方向的车辆中只有第1辆驶入AB路段的和最后1辆驶出AB路段的需要与另一方向的车竞争和释放对AB路段的互斥使用权，为此需引入两个计数器变量，分别用来对驶入AB路段的两个方向的车辆进行计数，以确定哪辆车是第1辆驶入的，哪辆是该方向最后1辆驶出的。故共需3个互斥信号量。§3.3经典同步问题问题解答：所用信号量和其他变量设置如下：整型变量Car_A，初值为0，用于对从A点（东）驶入AB段的车辆进行记数。整型变量Car_B，初值为0，用于对从B点（西）驶入AB段的车辆进行记数。互斥信号量mutex，初值为1，用于实现不同方向的第一辆车互斥驶入AB路段。互斥信号量ma，初值为1，用于实现东西向的车互斥地访问计数器变量Car_A。互斥信号量mb，初值为1，用于实现西东向的车互斥地访问计数器变量Car_B。§3.3经典同步问题wait（mb）；Car_B加1；若Car_B==1则wait（mutex）；signal（mb）；车辆从B点通过AB路段到达A点；wait（mb）；Car_B减1；Car_B==0则signal（mutex）；signal（mb）；wait（ma）；Car_A加1；若（Car_A==1）则wait（mutex）；signal（ma）；车辆从A点通过AB路段到达B点；Wait（ma）；Car_A减1；若Car_A==0则signal（mutex）；signal（