《内蒙古大学计算机操作系统课件02-4经典进程的同步问题》由会员分享，可在线阅读，更多相关《内蒙古大学计算机操作系统课件02-4经典进程的同步问题（26页珍藏版）》请在金锄头文库上搜索。
1、2.4经典进程的同步问题 2.4.1生产者消费者问题1利用记录型信号量解决生产者消费者问题假定在缓冲池中具有n个缓冲区，利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用资源信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。Var mutex，empty，full: semaphore:=1,n,0；buffer:array0，n-1 of item；in，out: integer:=0，0；beginparbegin利用记录型信号量的生产者消
2、费者算法proceducer: beginrepeatproducer an item nextp；wait(empty)； wait(mutex)；buffer(in):=nextp；in:=(in+1) mod n；signal(mutex)；signal(full)；until false； endconsumer: begin repeatwait(full)；wait(mutex)；nextc:=buffer(out)； out:=(out+1) mod n；signal(mutex)；signal(empty)；consumer the item in nextc； until f
3、alse；endparendend n 在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对出现；n 对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。p例如，wait(empty)在计算进程中，而signal(empty)则在打印进程中，计算进程若因执行wait(empty)而阻塞，则以后将由打印进程将它唤醒；n 在每个程序中的多个wait操作顺序不能颠倒，应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。 生产者消费者算法中应注意用Swait(empty
4、，mutex)来代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)来代替signal(mutex)和signal(full)；用Swait(full，mutex)来代替wait(full)和wait(mutex)用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。 2利用AND信号量解决生产者消费者问题Var mutex，empty，full: semaphore:=1，n，0；buffer:array0，n-1 of item；in out: integer:=0，0；beginparbeginpro
5、ducer: beginrepeatproduce an item in nextp；Swait(empty，mutex)；buffer(in):=nextp；in:=(in+1)mod n；Ssignal(mutex，full)；until false；end consumer:beginrepeatSwait(full，mutex)；Nextc:=buffer(out)；Out:=(out+1) mod n；Ssignal(mutex，empty)；consumer the item in nextc；until false；endparendend 首先建立一个管程，并命名为Proclu
6、cerConsumer，简称PC。其中包括两个过程：(1) put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。(2) get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，消费者应等待。 3利用管程解决生产者消费者问题type producer-consumer=monitorVar in, out, count: integer；buffer: array0, , n-1 of item；notfull，notem
7、pty : condition；procedure entry put(item)beginif count=n then notfull.wait；buffer(in):=nextp；in:=(in+1) mod n；count:=count+1；if notempty.queue then notempty.signal；end PC管程procedure entry get(item)beginif count=0 then notempty.wait；nextc:=buffer(out)；out:=(out+1) mod n；count:=count-1；if notfull.quen
8、e then notfull.signal；endbegin in:=out:=0； count:=0 end producer: beginrepeatproduce an item in nextp；PC.put(item)；until false；endconsumer: beginrepeatPC.get(item)；consume the item in nextc；until false；end 利用管程的生产者和消费者2.4.2哲学家进餐问题n五位哲学家围坐在一张圆形餐桌旁，交替进行吃饭或者思考n桌上有五个碗和五只筷子n每个哲学家饥饿时试图用其左右最近的筷子，只有拿到两只筷子才能
9、进餐 经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下： Var chopstick: array0，4 of semaphore； 1利用记录型信号量解决哲学家进餐问题所有信号量均被初始化为1，第i位哲学家的活动可描述为：repeatwait(chopsticki)；wait(chopstick(i+1)mod 5)；eat；signal(chopsticki)；signal(chopstick(i+1)mod 5)；think；until false； 虽然，上述解法可
10、保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0； 当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法： (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。要求每个哲学家先获得两个临界资源(筷子)后方能
11、进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Var chopstick array of semaphore:=(1,1,1,1,1)；processirepeatthink；Swait(chopstick(i+1)mod 5，chopsticki)；eat；Ssignat(chopstick(i+1)mod 5，chopsticki)；until false； 2利用AND信号量机制解决哲学家进餐问题2.4.3读者写者问题n一个数据文件被多个读者进程（ Reader）和写者进程（ Writer ）访问n允许多个进程同时读n但不允许写者进程和其他写者
12、或者读者进程同时访问为实现Reader与Writer的互斥，设置互斥信号量 wmutex。整型变量readcount表示正在读的进程数。因为它是一个可被多个Reader访问的临界资源，为它设置互斥信号量 rmutex。 由于只要有一个Reader在读，便不允许Writer去写。因此，仅当readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行wait(wmutex)操作。若wait(wmutex)操作成功，Reader进程便可去读，相应地，做readcount+1操作。仅当Reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmute
13、x)操作，以便让Writer进程写。1利用记录型信号量解决读者写者问题Var rmutex，wmutex: semaphore:=1,1；readcount: integer:=0；beginparbeginReader: beginrepeatwait(rmutex)；if readcount=0 then wait(wmutex)；readcount:=readcount+1；signal(rmutex)； 利用记录型信号量的读者写者perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 then
14、signal(wmutex)；signal(rmutex)；until false； endWriter: beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false； endparendend 读者写者问题增加限制：最多只允许RN个读者同时读。引入信号量L，并赋予其初值为RN，通过执行wait(L，1，1)操作，来控制读者的数目。p每当有一个读者进入时，就要先执行wait(L，1，1)操作，使L的值减1。p当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait(L，1，1)操作
15、失败而阻塞。利用信号量集来解决读者写者的描述如下2利用信号量集机制解决读者写者问题 Var RN integer；L，mx: semaphore:=RN,1；beginparbegin Reader: beginrepeatSwait(L,1,1)；Swait(mx,1,0)；perform read operation；Ssignal(L,1)；until false；end Writer: beginrepeatSwait(mx,1,1；L,RN,0)；perform write operation；Ssignal(mx,1)；until false；endparendend Swait(mx，1，0)语句起着开关的作用。只要无Writer进程进入写，mx=1，Reader进程就都可以进入读；但只要一旦有Writer进程进入写时，其mx=0，则任何Reader进程就都无法进入读。Swait(mx，1，1；L，RN，0)语句表示仅当既无Writer进程在写(mx=1)，又无Reader进程在读(L=RN)时，writer进程才能进入临界区写。
