操作系统第五章同步互斥作业.ppt

Chapter5:ProcessSynchronization进程同步习题课,最简单的情况如何进行分析呢？本章作业2,经典的生产者和消费者问题一个生产者V.S.一个消费者,Producerwhile(1)produce；wait(empty);putinbuffer;signal(full);,semaphoreempty=1,full=0;,Consumerwhile(1)wait(full);takeoutfrombuffer;signal(empty);consume,一个生产者V.S.一个消费者但缓冲区有n个,复杂一些的情况如何进行分析呢？本章作业3,Producerwhile(1)produce;wait(empty);put;signal(full);in=(in+1)%n;,semaphoreempty=n,full=0;,Consumerwhile(1)wait(full);take;signal(empty);consume；out=（out+1)%n;,Bufferbufn；intin=0,out=0;%使用循环缓冲级数,多个生产者V.S.多个消费者n个缓冲区,更为复杂的情况如何进行分析呢？本章作业3,Producerwhile(1)produce;wait(empty);wait（mutex1）put;in=(in+1)%n;signal（mutex1）signal(full);,semaphoreempty=n,full=0，mutex1=1，mutex2=1;,Consumerwhile(1)wait(full);wait（mutex2）take;out=（out+1)%n;signal（mutex2）signal(empty);consume；,Bufferbufn；intin=0,out=0;%使用循环缓冲级数,ProcessSynchronizationExample进程同步例子作业4,同步要求：先关门，后开车,先停车，后开门,解：,Semaphoreclose=0，open=0；driver()/*司机*/while(True)P(close);启动车辆;正常行车;到站停车;V(open);,Conductor()/*售票员*/while(True)关车门；V(close);售票;P(open);开车门;上下乘客;,作业5,设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？,进程P1y=1；y=y+2;V(S1);z=y+1;P(S2);y=z+y;,进程P2x=1;x=x+1;P(S1);x=x+y;V(S2);z=x+z;,作业5,设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？,进程P1y=1；y=y+2;V(S1);z=y+1;P(S2);y=z+y;,进程P2x=1;x=x+1;P(S1);x=x+y;V(S2);z=x+z;,y=3,X=2,X=5,Z=4,X的最终值是5;Z的最终值是：9,Y的最终值取决于P1和P2最后一行的执行顺序：如果P2先执行完，则Y=12；如果P1先执行完，则Y=7；,作业6,假定系统有3个并发进程get、copy和put共享缓冲器B1和B2。进程get负责从输入设备上读信息，每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务，使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。（北大1990年试题）,解题思路：这是同步还是互斥呢？2个资源；每个资源对应两个事件（空、满）；,设置4个信号量，其中empty1对应空闲的缓冲区1，其初值为1；full1对应缓冲区1中的记录，其初值为0；empty2对应空闲的缓冲区2，其初值为1；full2对应缓冲区2中的记录，其初值为0。相应进程描述为：,get()while(1)从输入设备读入一条记录;P(empty1);将记录存入缓冲区1；V(full1);,copy()while(1)P(full1);从缓冲区1中取出一条记录;V(empty1);P(empty2);将取出的记录存入缓冲区2；V(full2);,put()while(1)P(full2);从缓冲区2中取出一条记录;V(empty2);将取出的记录打印出来；,公平的读写问题（作业7）,读者优先的读写问题中，当有读者不断到来时，写者可能会饥饿。修改：进程的执行顺序按照到达顺序进行操作即一个读者试图进行读操作时，如果有写者正在等待进行写操作，后续读者需要等待先到达的写者完成写操作后才能开始读操作。思路：读者和写者的排队模型排队模型是：读者和写者竞争在排队过程中所有的进程都不可以加塞；只能按顺序排队；但是队列中两个写者进程之间的读者进程可以一起进入到临界区,初始值：semaphorermutex=1,wrt=1;intreadcount=0,ReaderProcesswait(rmutex);readcount+;if(readcount=1)wait(wrt);signal(rmutex);readingisperformedwait(rmutex);readcount-;if(readcount=0)signal(wrt);signal(rmutex):,WriterProcesswait(wrt);writingisperformedsignal(wrt);,TheReaders-WritersProblem读者写者问题-读者优先,WhatistheReaders-Writersproblem?AdatasetissharedamonganumberofconcurrentprocessesReadersonlyreadthedataset;theydonotperformanyupdates;Writerscanbothreadandwrite.Problemallowmultiplereaderstoreadatthesametime.Onlyonesinglewritercanaccesstheshareddataatthesametime.Shareddatasemaphoremutex,wrt;Initiallymutex=1,wrt=1,readcount=0,初始值：mutex=1,wrt=1,readcount=0,ReaderProcesswait(mutex);readcount+;if(readcount=1)wait(wrt);signal(mutex);readingisperformedwait(mutex);readcount-;if(readcount=0)signal(wrt);signal(mutex):,WriterProcesswait(wrt);writingisperformedsignal(wrt);,更为复杂的读者写者问题,写者优先的读者写者问题课后作业8：写者优先的读者写者问题的同步机制实现。,初始值：semaphorewrt=1,S=1;semaphorewmutex=1,rmutex=1;intreadcount=0,writecount=0;,Writer()while(1)P(wmutex);writecount+;If(writecount=1)P(S);V(wmutex);P(wrt);写文件；V(wrt);P(wmutex);writecount-;i