《经典进程同步问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《经典进程同步问题ppt课件.ppt（41页珍藏版）》请在三一办公上搜索。
1、1,2.4 经典进程同步问题,在多道程序环境下，进程同步问题是十分重要的，也是相当有趣的问题，因而吸引了不少学者对它进行研究。 其中较有代表性的是“生产者消费者问题”、“读者写者问题”、“哲学家进餐问题”等。,2,2.4.1 生产者消费者问题,问题的描述： 有一群生产者进程生产消息，并将此消息提供给消费者进程消费。为使生产者进程和消费者进程并发执行，在它们之间设置一个具有n个缓冲区的公共缓冲池。生产者进程将它所生产的消息放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个消息消费。 不允许消息费者进程到一个空缓冲区中去取消息，也不允许生产者进程向一个已装有消息且尚未被取走消息的缓冲区中投放消
2、息。,3,需要解决的问题：1、对缓冲池的互斥访问，即只有一个进程访问缓冲区。2、对生产、消费进程的同步，即：有产品时才能消费，无产品时，必须先生产后消费；有空间时才能生产，空间满时，必须先消费再生产。,4,信号量的设置：1、一个互斥信号量mutex，用于实现对共享缓冲区的互斥访问，初始值为1。2、两个同步信号量，分别表示可用资源数：Empty：表示空缓冲区的个数，初始值为nFull：表示装有消息的缓冲区的个数，初始值为0，（一个缓冲区中放一条消息）,5,一、利用记录型信号量解决生产者消费者问题,数据结构：Var mutex, empty, full：semaphore=1，n，0； /定义信号
3、量并赋初值 buffer：array0, , n-1 of item; /定义缓冲区 in, out: integer=0, 0; /定义存取指针的初始位置,6,Proceduer： /生产者进程begin repeat 生产一件产品; wait(empty); wait(mutex); bufferin:=nextp; in=(in+1) mod n; signal(mutex); signal(full); until false;end,empty:=empty-1;if empty 0 then block;,mutex:=mutex-1;if mutex 0 then block;,
4、full:=full + 1;if full =0 then wakeup;,mutex:=mutex+1;if mutex =0 then wakeup;,7,consumer：/消费者进程begin repeat wait(full); wait(mutex); nextc:=bufferout; out=(out+1) mod n; signal(mutex); signal(empty); 消费这件产品; until false;end,full:=full - 1;if full 0 then block;,mutex:=mutex-1;if mutex0 then block;,e
5、mpty:=empty+1;if empty=0 then wakeup;,mutex:=mutex+1;if mutex=0 then wakeup;,8,例：有生产者P1、P2和消费者C1，利用3个信号量和对它们的wait和signal操作实现同步与互斥。,初始条件： 记录型信号量 mutex.value=1,empty=2,full=0,执行序列 mutex empty full empty队列 full队列P1:wait(empty),wait(m),CS 0 1 signal(m),signal(f) 1 1P1:wait(empty),wait(m),CS 0 0 signal(m
6、),signal(f) 1 2P2:wait(empty) 1 p2P1:wait(empty) 2 p1C1:wait(full),wait(m),CS 0 1 signal(m),signal(empty) 1 1 （唤醒p2）P2:wait(m) 0 CS C1:wait(full),wait(m) 1 0 C1P2:signal(m),signal(full) 0 1 (唤醒C1)C1:CS,signal(m),signal(e) 1 0 （唤醒p1)P1: wait(m) 0,9,在生产者消费者问题中应注意：,()在每个程序中用于实现互斥的wait(mutex)和signal(mut
7、ex)必须成对地出现。()对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的进程中，这样保证生产者进程和消费者进程的同步及交替执行。()在每个进程中，多个wait操作顺序不能颠倒，而signal操作的次序是无关紧要的 。,10,Wait操作不能颠倒！,P：wait(empty) wait(mutex),C：wait(full) wait(mutex),如果颠倒,P：wait(mutex) mutexl.value=0 wait(empty) 如果此时缓冲池满empty=1，P阻塞,C：wait(mutex) mutex.value=1， C阻
8、塞 wait(full),P阻塞在empty队列中，等待一个空缓冲,C阻塞在mutex队列中，等待公共缓冲池访问权,由于wait操作顺序不当，会造成死锁，因此wait操作顺序不能颠倒。,11,二、利用AND信号量解决生产者消费者问题,数据结构：Var mutex, empty, full：semaphore=1，n，0； /定义信号量并赋初值 buffer：array0, , n-1 of item; /定义缓冲区 in, out: integer=0, 0; /定义存取指针的初始位置,12,Proceduer： /生产者进程begin repeat 生产一件产品; Swait( empty，
9、mutex ); bufferin:=nextp; in=(in+1) mod n; Ssignal(mutex，full); until false;end,if empty=1 and mutex=1 then empty:=empty-1;mutex:=mutex-1;,mutex:=mutex+1;full:=full + 1;,13,consumer：/消费者进程begin repeat Swait(full，mutex); nextc:=bufferout; out=(out+1) mod n; Ssignal(mutex，empty); 消费这件产品; until false;e
10、nd,if full =1 and mutex=1 then full:=full - 1; mutex:=mutex-1;,mutex:=mutex+1;empty:=empty+1;,14,3利用管程解决生产者消费者问题 在利用管程方法来解决生产者消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer，或简称为PC。其中包括两个过程：(1) put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。(2) get(item)过程。消费者利用该过程
11、从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，消费者应等待。,15,PC管程可描述如下：type producer-consumer=monitorVar in,out,count: integer；buffer: array0, , n-1 of item；notfull，notempty: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 the
12、n notempty.signal；end,16,procedure entry get(item)beginif count=0 then notempty.wait；nextc:=buffer(out)；out:=(out+1) mod n；count:=count-1；if notfull.quene then notfull.signal；endbegin in:=out:=0； count:=0 end,17,在利用管程解决生产者消费者问题时，其中的生产者和消费者可描述为：producer: beginrepeatproduce an item in nextp；PC.put(ite
13、m)；until false；endconsumer: beginrepeatPC.get(item)；consume the item in nextc；until false；end,18,2.4.2 哲学家进餐问题,1、问题描述： 设有5个哲学家围坐在一张圆桌前吃饭。桌上有5支筷子和5个碗。哲学家要吃饭时，只有从左、右两边都拿到筷子时，才能吃饭。 如果筷子已在他人手上，则该哲学家必须等待到他人吃完后才能拿到筷子；任何一个哲学家在自己未拿到两只筷子吃饭之前，决不放下自己手里的筷子。,19,2、问题分析： 放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用
14、，可以为每一只筷子设置一个信号量，由这五个信号量构成信号量数组：Var chopstick: array0, , 4 of semaphore; 设初始条件下，所有哲学家都未吃，故所有信号量均被初始化为1。,20,假设每一位哲学家拿筷子的方法都是：先拿起左边的筷子，再拿起右边的筷子，则第i位哲学家的活动可描述为：,一、利用记录型信号量解决哲学家进餐问题,21,第i位哲学家的活动可描述为：repeat wait(chopsticki); wait(chopsticki+1 mod 5); . eat; . signal(chopsticki); signal(chopsticki+1 mod 5
15、); . think;until false;,22,以上算法存在一个问题： 假设5个哲学家同时拿起左边的筷子，就会使五个信号量chopstick均为0；那么当他们再去拿右边的筷子时，就会因无机筷子而无限期地等待，这就会产生死锁。,23,下面给出几种解决方法：（1）至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。（2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。最后总会有一位哲学家能获得两只筷子而进餐。,
16、24,二、利用AND信号量机制解决哲学家进餐问题,即要求每个哲学家先获得两个临界资源（筷子）后，才能进餐。,Var chopstick: array0,4 of semaphore :=（1,1,1,1,1）;Process irepeat think Swait（chopsticki+1 mod 5，chopsticki）； eat; Ssignal（chopsticki+1 mod 5，chopsticki）；until false;,25,2.4.3 读者写者问题,1问题的提出 一个数据文件可以被多个并发进程共享，将这些访问该文件的进程按访问方式分为两类： 一类只能读共享对象的内容，把这
17、类进程称为读进程或读者； 另一类进程则要更新（写）共享对象文件F，将这些进程称为写进程或写者。 试用Wait、Signal操作解决各进程间的同步问题。,26,2问题的分析 显然，多个读者同时读一个共享对象是可以的，然而一个写者不能与其它任何读者或写者同时共享该文件。 亦即：在使用共享文件时，一个写进程与其它所有进程都是互斥的。但多个读进程之间不存在互斥的现象。,27,一、利用记录型信号量解决读者写者问题,信号量的设置：Wmutex：互斥使用该共享文件信号量。如：写进程write与读进程reader在使用文件时是互斥的；共享文件只有一个，设初始情况未被使用，则初值为1。readcount：整型变
18、量，表示正在读的进程个数，初值为0。该变量属临界资源。rmutex：计数器readcount的信号量。因为readcount是一个可被多个reader进程访问的临界资源，为此设一信号量。设初始状态下无进程读和写，故rmutex的初值设为1。,28,由于多个进程可以同时读，因此只要有一个reader进程在读，其它reader进程便不必申请该共享文件，直接读即可；若无文件在读，则第一个读文件的进程必须做申请该文件的操作。只要有read进程在执行，则不允许writer进程去写。 因此，仅当readcount=0, 即无reader进程在读时，reader进程才需要执行wait(wmutex)操作。若
19、wait(wmutex)操作成功，reader进程便可去读，相应地，做readcount+1操作。同理，仅当reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让writer进程写。,29,数据结构： Var rmutex, wmutex：semaphore：=1，1; readcount：integer：=0;,30,reader: repeat wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); readfil
20、e; wait(rmutex); readcount :=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false,第一个读者要检查文件的访问权是否空闲,最后一个读进程要负责释放对文件的访问权,申请对readcount的访问权,释放对readcount的访问权,读操作完毕，要修改readcount的值,31,writer: begin repeat wait(wmutex); writing operation; signal(wmutex); until false ; end,申请对文件的访问权
21、,释放文件的访问权,32,举例： 文件F r1, r2, w1 三个进程并发执行,初始： readcount=0, rmutex=1, wmutex=1,执行过程 readcount rmutex wmutex 0 1 1,r1:,wait(rmutex);,if readcount=0 then wait(wmutex),0,0,readcount+1,1,signal(rmutex),1,开始读,r2:,wait(rmutex);,0,readcount+1,2,signal(rmutex),1,w1:,wait(wmutex);,1,r1:,wait(rmutex);,readcount
22、1,0,1,signal(rmutex),1,r2:,wait(rmutex);,readcount1,0,0,signal(rmutex),1,if readcount0,被阻塞,if readcount0,if readcount=0 then signal(wmutex),0,w1:,开始写,signal(wmutex),1,读结束,读结束,33,二、利用信号量集机制解决读者写者问题,问题描述： 这里的读者写者问题，增加了一条限制，即最多只允许RN个读者同时读。为此，引入一个信号量L，初始值为RN，通过执行wait（L，1，1）操作来控制读者的数目。Var RN:integer;L,mx
23、:semaphore:Rn,1;,34,reader: repeat Swait（L，1，1）; Swait（mx，1，0）； readfile; Ssignal（L，1）； until false,if L =1 then L :=L - 1;,if mx =1 then mx :=mx - 0; /即mx值不变,L :=L + 1;,35,writer: repeatSwait(mx,1,1;L,RN,0);writing operation; Ssignal(mx,1); until false ;,if mx =1 and L =RN then mx:=mx - 1; L:=L-0;/
24、即在读进程数不变,mx :=mx + 1;,36,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进程才能进入临界区写。,37,有一座桥，桥上不允许两车交会，但允许同方向（南/北方向）多辆车依次通行（即桥上可以有多台同方向的车）。请用wait、signal操作实现交通管理以防止桥上堵塞。,38,分
25、析：桥上不允许两车相会，因此，桥应该被互斥访问；同一方向上允许多辆车依次通过，即临界区允许多个进程访问，可以用一个信号量mutex来互斥访问临界区。并且保证最多某一方向上连续通过一定数量的（m台）车后，必须让另一方向上的车通过。,39,数据结构： Var mutex, avail-n, avail-s：semaphore：= 0, m, m;/mutex是互斥信号量，用于实现对共享缓冲区的互斥访问，初始值为1 /avail-n表示允许向北行的车辆数，初始值为m/avail-s表示允许向南行的车辆数，初始值为m,40,South:Begin wait(avail-s); wait(mutex); cross the bridge; signal(mutex); signal(avail-n);End,North:Begin wait(avail-n); wait(mutex); cross the bridge; signal(mutex); signal(avail-s);End,41,第二章习题：P81-83 2、24、26、27、28,
