计算机操作系统（第二版）课件：经典进程同步问题

经典进程同步问题生产者-消费者问题哲学家进餐问题读者-写者问题理发师问题3.4.3经典进程同步问题1.生产者－消费者问题(theproducer-consumerproblem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有K个；任何时刻只能有一个进程可对共享缓冲区进行操作。0123…4K-13.4进程同步inout3.4.3经典进程同步问题这个问题中有哪些进程？进程间有需要互斥使用的临界资源吗？是什么？哪些进程间有互斥关系？哪些进程间有前驱后继（同步）关系？1.生产者－消费者问题分析：确定进程：进程数量及工作内容；确定进程间的关系：

互斥：多个进程间互斥使用同一个缓冲池；

同步：当缓冲池空时，消费者必须阻塞等待；当缓冲池满时，生产者必须阻塞等待。设置信号量：Mutex：用于访问缓冲池时的互斥，初值是1Full：“满缓冲”数目，初值为0；Empty：“空缓冲"数目，初值为K。full+empty=K3.4.3经典进程同步问题＃defineK100

＃defineMAXLEN80typedefstruct{intnum;chararray[MAXLEN];}Message;semaphoremutex;semaphoreempty;

semaphorefull;Messagebuffers[K];

intin,out;

1.生产者－消费者问题算法描述：3.4.3.经典进程同步问题

voidmain(){mutex={1,NULL};empty={K,NULL};

full={0,NULL};Messagebuffers[K];in=0;out=0;

parbegin(produceri,consumerj)}

生产者－消费者问题programproduceri{Messagep_puf;while(1){produceamessageinp_buf;wait(empty)；

wait(mutex)；buffers[in]=p_bufin=(in+1)%K;signal(mutex)；

signal(full)；}}3.4.3经典进程同步问题programconsumerj{Messagec_buf;while(1){wait(full)；

wait(mutex)；

c_buf=buffers[out]；out=(out+1)%K;signal(mutex)；

signal(empty)；

consumethemessageinc_buf;}}1.生产者－消费者问题生产者i

消费者j生产出一产品；

wait（full）；wait（empty

）；

wait（mutex）；wait（mutex

）

；从缓冲区取出一产品；将该产品放入缓冲区；

signal（mutex）；signal（mutex

）；

signal（empty）；

signal（full

）

；消费该产品；如果交换消费者代码中的两个wait（）操作的顺序，进程的执行会怎么样？假设状态：mutex=1,full=0,empty=k，先执行消费者进程wait（mutex）;wait（full）；系统可能会死锁！生产者i

消费者j生产出一产品；wait（full）；wait（empty）；wait（mutex）；wait（mutex）；从缓冲区取出一产品；将该产品放入缓冲区；signal（mutex）；signal（mutex）；signal（empty）；

signal（full）；消费该产品；signal(empty);Signal(mutex);1.生产者－消费者问题如果交换消费者代码中的两个signal（）操作的顺序，进程的执行会怎么样？思考：请举出一个计算机系统中可以用生产者-消费者问题描述的实际例子在解决生产者-消费者问题的算法中，如果生产者算法中的两个wait()操作（wait(empty）和wait(mutex)）不小心互换了位置，消费者的算法是正确的，则以下说法中正确的是（

）。生产者可能会把两个或多个消息放到同一个缓冲区中

消费者可能取到空消息生产者可能会占着缓冲池，但因为没有空缓冲区而不能放消息

消费者可能占着缓冲池，但因为缓冲池为空而不能取到消息ABCD提交单选题10分2.哲学家进餐问题

解决多个进程同时需要多个资源的问题有5个进程制约关系哲学家只有拿到两只筷子才能吃饭筷子必须互斥使用这个问题中有几个进程？进程间有哪些制约关系？3.4.3经典进程同步问题筷0筷3筷4筷2筷1我是谁？宇宙是否有尽头？时间是否有长短？

programphilosopher（i）{thinking…wait(chopstick[i])；wait(chopstick[(i+4)mod5]);eating;

signal(chopstick[i])；

signal(chopstick[(i+4)mod5]);}哲学家进餐问题voidmain(){chopstick[0…4]={1,NULL};parbegin(philosopher(i));}

算法描述1semaphorechopstick[0…4];如果5个哲学家几乎同时饿了，要求同时吃饭，系统会怎么样？5个哲学家可能会被饿死！programphilosopher(i){wait(sm)；

wait(chopstick[i])；wait(chopstick[(i+4)mod5]);eating;signal(chopstick[i])；

signal(chopstick[(i+4)mod5]);

signal(sm)；}semaphorechopstick[0…4];

semaphoresm;voidmain(){chopstick[0…4]={1,NULL};

sm={4,NULL};parbegin(philosopher(i));}哲学家进餐问题思考1：在这个问题中，是否可以只设置一个互斥信号量chopstick，其初始值为5？思考2：请举出一个计算机系统中可以用哲学家进程问题描述的实际例子算法描述2课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出前期知识回顾1、说明记录型信号量的PV操作的定义2、说明如何应用记录型信号量解决进程互斥问题？3、说明如何应用记录型信号量解决进程同步问题？3.读者-写者问题(thereaders-writersproblem)问题描述：3.4进程同步3.4.3经典进程同步问题共享数据读者1读者2读者m写者1写者2写者n访问要求：

写者与其他进程互斥访问共享数据；

允许多个读者同时读；这个问题中有哪些进程？进程间有哪些同步互斥关系呢？3.读者－写者问题(thereaders-writersproblem)问题分析及信号量设置：信号量wmutex表示“允许写”，写者与其他进程互斥使用数据公共整形变量Readcount表示“正在读”的读者数信号量Rmutex：实现多个读者对Readcount的互斥操作

wmutex:semaphore=1//读者与写者之间、写者与写者之间互斥使用共享数据readcount:int=0;//当前正在读的读者数量rmutex:semaphore=1//多个读者互斥使用readcount3.4.3经典进程同步问题3.读者－写者问题算法描述：semaphorewmutex,rmutex;intreadcount;voidmain(){wmutex=1;rmutex=1;readcount=0;

parbegin(writeri,readerj);}voidwriteri{while(1){

writing…

}}wait(wmutex);signal(wmutex);voidreaderj{while(1){

wait(rmutex)ifreadcount==0thenwait

(wmutex);readcount++;signal(rmutex);

reading…

wait

(rmutex);readcount--;ifreadcount==0thensignal(wmutex);signal(rmutex);}}3.读者－写者问题读者优先的读者-写者算法：3.读者－写者问题共享数据R1W1R2R3写者优先的读者-写者算法：写进程与其他所有进程互斥允许多个读者同时读

写者优先于读者（一旦有写者，则后续读者必须等待；若同时有读者和写者在等待，唤醒时优先考虑写者）

此时W1能去写共享数据吗？此时R2能去读共享数据吗？

semaphore

wmutex=1//读者与写者之间、写者与写者之间互斥使用共享数据SemaphoreS=1//当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成SemaphoreS2＝1//阻塞第二个以后的等待读者intReadcount,writecount=0,0;//当前读者数量、写者数量Semaphoremutex1=1//多个读者互斥使用readcountSemaphoremutex2=1//多个写者互斥使用writecount算法描述：写者优先的读者－写者问题算法Reader(){while(1){wait(S2);

wait(S);wait(mutex1)ifreadcount==0thenwait(wmutex);readcount++;signal(mutex1);signal(S);signal(S2);

reading…wait(mutex1);readcount--;ifreadcount==0thensignal(wmutex);signal(mutex1);}}写者优先的读者－写者问题算法算法描述：voidwriter(){while(1)wait(mutex2);ifwritecount==0thenwait(S);writecount++;signal（mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);writecount--;ifwritecount==0thensignal(S);signal（mutex2）;}}写者优先的读者－写者问题算法4.理发师问题问题描述：

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子（等候椅）。如果没有顾客，理发师便在理发椅上睡觉；第一个顾客到来时，他必须叫醒理发师；理发结束后离开理发店；若顾客到达时理发师正在理发时，则如果有空等候椅，顾客就坐下来等待，如果满座了就离开理发店。

理发店问题经常被用来模拟各种排队情形。3.4.3经典进程同步问题这个问题中进程间有哪些同步互斥关系呢？

理发师与顾客之间？

顾客与顾客之间？理发师与顾客之间：有顾客到了，理发师才工作；理发师理完发，顾客才能离开。

顾客与顾客之间：

有等候椅顾客才能坐下等待，否则离开；互斥使用理发椅4.理发师问题算法描述：intwaiting;semaphorecust_ready,finished,mutex,chair;voidmain(){waiting=0;cust_ready=finished=0;mutex=chair=1;

parbegin(barber,customer-i);}

3.4.3经典进程同步问题Cust_ready:理发师等待顾客到达Finished:顾客是否已完成理发mutex:互斥访问waitingchair:理发椅的互斥使用表示坐在等候椅上的顾客数voidbarber(){do{wait(cust_ready);cut_hair;signal（finished);}while(1);}voidcustomer-i(){wait(mutex)；if(waiting<n){waiting=waiting+1;signal(mutex);}}else{signal(mutex)；

离开理发店；return;}wait(chair);sit_in_chair;wait(mutex)；waiting=waiting-1;signal(mutex);signal(cust_ready);get-haircut;wait(finished);stand_from_chair;signal(chair);}4、理发师问题3.4经典进程同步问题例1：

桌上有个只能盛得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量的PV操作实现爸爸、儿子和女儿这三个循环进程之间的同步。

这个问题中有哪些进程？进程间有哪些同步互斥关系呢？

所用信号量设置如下：

Ⅰ）同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。

Ⅱ）同步信号量orange，初值为0，表示爸爸尚未把桔子放入盘中。

Ⅲ）同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。

算法同步描述：爸爸进程（P）：

儿子进程（C1）：

女儿进程（C2）：P（empty）；

P（orange）；

P（apple）；将水果放入盘中；

从盘中取出桔子；

从盘中取出苹果；若放入的是桔子，

V（empty）；

V（empty）；则V（orange）；吃桔子；

吃苹果；否则，V（apple）；3.4经典进程同步问题这个问题中有如果盘子中可以放3个水果，代码应该如何修改？2018-2019-2期末试题（本小题13分）医院中的就医流程通常是：某个医生若没有病人，则医生休息，当有病人挂号就诊且分配到该医生时则叫号看病；病人到医院后首先到自助挂号终端挂号，自助挂号终端一段时间只能一个人操作；病人挂号成功后拿着挂号凭证到门诊大厅里等待就医叫号；当叫到自己的号码时，病人到诊疗室看病，医生开出药方并提交后系统自动完成缴费操作；医生叫下一个号码的病人就诊；已完成缴费的病人到取药柜台将已缴费的药方交给发药员，取药柜台一次只能一个病人取药，发药员根据药方把药交给病人，病人离开医院。请用信号量实现医院的就诊流程的管理（即医生、病人、发药员之间的协调处理）。3.4经典进程同步问题：小组讨论12分钟完成小组讨