经典进程同步问题

2.4经典进程同步问题

在多道程序环境下，进程同步问题是十分重要的，也是相当有趣的问题，因而吸引了不少学者对它进行研究。

其中较有代表性的是“生产者——消费者问题”、“读者——写者问题”、“哲学家进餐问题”等。12.4.1生产者——消费者问题问题的描述：有一群生产者进程生产消息，并将此消息提供给消费者进程消费。为使生产者进程和消费者进程并发执行，在它们之间设置一个具有n个缓冲区的公共缓冲池。生产者进程将它所生产的消息放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个消息消费。不允许消息费者进程到一个空缓冲区中去取消息，也不允许生产者进程向一个已装有消息且尚未被取走消息的缓冲区中投放消息。2需要解决的问题：1、对缓冲池的互斥访问，即只有一个进程访问缓冲区。2、对生产、消费进程的同步，即：有产品时才能消费，无产品时，必须先生产后消费；有空间时才能生产，空间满时，必须先消费再生产。3信号量的设置：1、一个互斥信号量mutex，用于实现对共享缓冲区的互斥访问，初始值为1。2、两个同步信号量，分别表示可用资源数：Empty：表示空缓冲区的个数，初始值为nFull：表示装有消息的缓冲区的个数，初始值为0，（一个缓冲区中放一条消息）4一、利用记录型信号量 解决生产者——消费者问题数据结构：Varmutex,empty,full：semaphore∶=1，n，0；//定义信号量并赋初值

buffer：array［0,…,n-1］ofitem;//定义缓冲区in,out:integer∶=0,0;//定义存取指针的初始位置5Proceduer：//生产者进程beginrepeat…生产一件产品;…

wait(empty);wait(mutex);buffer[in]:=nextp;in∶=(in+1)modn;

signal(mutex);

signal(full);untilfalse;endempty:=empty-1;ifempty<0thenblock;mutex:=mutex-1;ifmutex<0thenblock;full:=full+1;iffull<=0thenwakeup;mutex:=mutex+1;ifmutex<=0thenwakeup;6consumer：//消费者进程beginrepeat

wait(full);wait(mutex);nextc:=buffer[out];out∶=(out+1)modn;

signal(mutex);signal(empty);消费这件产品;untilfalse;endfull:=full-1;iffull<0thenblock;mutex:=mutex-1;ifmutex<0thenblock;empty:=empty+1;ifempty<=0thenwakeup;mutex:=mutex+1;ifmutex<=0thenwakeup;7例：有生产者P1、P2和消费者C1，利用3个信号量和对它们的wait和signal操作实现同步与互斥。初始条件：记录型信号量mutex.value=1,empty=2,full=0执行序列mutexemptyfullempty队列full队列P1:wait(empty),wait(m),CS01signal(m),signal(f)11P1:wait(empty),wait(m),CS00signal(m),signal(f)12P2:wait(empty)－1p2P1:wait(empty)－2p1C1:wait(full),wait(m),CS01signal(m),signal(empty)1－1（唤醒p2）P2:wait(m)0CSC1:wait(full),wait(m)－10C1P2:signal(m),signal(full)01(唤醒C1)C1:CS,signal(m),signal(e)10（唤醒p1)P1:wait(m)08在生产者—消费者问题中应注意：

(１)在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。(２)对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的进程中，这样保证生产者进程和消费者进程的同步及交替执行。(３)在每个进程中，多个wait操作顺序不能颠倒，而signal操作的次序是无关紧要的。9Wait操作不能颠倒！！P：wait(empty)wait(mutex)C：wait(full)wait(mutex)如果颠倒P：wait(mutex)mutexl.value=0wait(empty)如果此时缓冲池满empty=－1，P阻塞C：wait(mutex)mutex.value=－1，C阻塞

wait(full)P阻塞在empty队列中，等待一个空缓冲C阻塞在mutex队列中，等待公共缓冲池访问权由于wait操作顺序不当，会造成死锁，因此wait操作顺序不能颠倒。10二、利用AND信号量 解决生产者——消费者问题数据结构：Varmutex,empty,full：semaphore∶=1，n，0；//定义信号量并赋初值

buffer：array［0,…,n-1］ofitem;//定义缓冲区in,out:integer∶=0,0;//定义存取指针的初始位置11Proceduer：//生产者进程beginrepeat…生产一件产品;…

Swait(empty，mutex);buffer[in]:=nextp;in∶=(in+1)modn;

Ssignal(mutex，full);untilfalse;endifempty>=1

andmutex>=1thenempty:=empty-1;mutex:=mutex-1;mutex:=mutex+1;full:=full+1;12consumer：//消费者进程beginrepeat

Swait(full，mutex);nextc:=buffer[out];out∶=(out+1)modn;

Ssignal(mutex，empty); 消费这件产品;untilfalse;endiffull>=1andmutex>=1thenfull:=full-1;mutex:=mutex-1;mutex:=mutex+1;empty:=empty+1;133．利用管程解决生产者—消费者问题在利用管程方法来解决生产者—消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer，或简称为PC。其中包括两个过程：(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待。14PC管程可描述如下：typeproducer-consumer=monitorVarin,out,count:integer；buffer:array[0,…,n-1]ofitem；notfull，notempty:condition；procedureentryput(item)beginifcount>=nthennotfull.wait；buffer(in):=nextp；in:=(in+1)modn；count:=count+1；ifnotempty.queuethennotempty.signal；end15procedureentryget(item)beginifcount<=0thennotempty.wait；nextc:=buffer(out)；out:=(out+1)modn；count:=count-1；ifnotfull.quenethennotfull.signal；endbeginin:=out:=0；count:=0end16在利用管程解决生产者—消费者问题时，其中的生产者和消费者可描述为：producer:beginrepeatproduceaniteminnextp；PC.put(item)；untilfalse；endconsumer:beginrepeatPC.get(item)；consumetheiteminnextc；untilfalse；end172.4.2哲学家进餐问题1、问题描述：设有5个哲学家围坐在一张圆桌前吃饭。桌上有5支筷子和5个碗。哲学家要吃饭时，只有从左、右两边都拿到筷子时，才能吃饭。如果筷子已在他人手上，则该哲学家必须等待到他人吃完后才能拿到筷子；任何一个哲学家在自己未拿到两只筷子吃饭之前，决不放下自己手里的筷子。182、问题分析：放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以为每一只筷子设置一个信号量，由这五个信号量构成信号量数组：Varchopstick:array［0,…,4］ofsemaphore;设初始条件下，所有哲学家都未吃，故所有信号量均被初始化为1。19假设每一位哲学家拿筷子的方法都是：先拿起左边的筷子，再拿起右边的筷子，则第i位哲学家的活动可描述为：一、利用记录型信号量 解决哲学家进餐问题20第i位哲学家的活动可描述为：repeatwait(chopstick[i]);wait(chopstick[i+1]mod5);….eat;….signal(chopstick[i]);signal(chopstick[i+1]mod5);….think;untilfalse;21以上算法存在一个问题：假设5个哲学家同时拿起左边的筷子，就会使五个信号量chopstick均为0；那么当他们再去拿右边的筷子时，就会因无机筷子而无限期地等待，这就会产生死锁。22下面给出几种解决方法：（1）至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。（2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。最后总会有一位哲学家能获得两只筷子而进餐。23二、利用AND信号量机制 解决哲学家进餐问题即要求每个哲学家先获得两个临界资源（筷子）后，才能进餐。Varchopstick:array[0,…,4]ofsemaphore:=（1,1,1,1,1）;ProcessirepeatthinkSwait（chopstick[i+1]mod5，chopstick[i]）；eat;Ssignal（chopstick[i+1]mod5，chopstick[i]）；untilfalse;242.4.3读者—写者问题1．问题的提出一个数据文件Ｆ可以被多个并发进程共享，将这些访问该文件的进程按访问方式分为两类：一类只能读共享对象的内容，把这类进程称为读进程或读者；另一类进程则要更新（写）共享对象文件F，将这些进程称为写进程或写者。试用Wait、Signal操作解决各进程间的同步问题。252．问题的分析显然，多个读者同时读一个共享对象是可以的，然而一个写者不能与其它任何读者或写者同时共享该文件。亦即：在使用共享文件时，一个写进程与其它所有进程都是互斥的。但多个读进程之间不存在互斥的现象。26一、利用记录型信号量 解决读者——写者问题信号量的设置：Wmutex：互斥使用该共享文件信号量。如：写进程write与读进程reader在使用文件时是互斥的；共享文件只有一个，设初始情况未被使用，则初值为1。readcount：整型变量，表示正在读的进程个数，初值为0。该变量属临界资源。rmutex：计数器readcount的信号量。因为readcount是一个可被多个reader进程访问的临界资源，为此设一信号量。设初始状态下无进程读和写，故rmutex的初值设为1。27由于多个进程可以同时读，因此只要有一个reader进程在读，其它reader进程便不必申请该共享文件，直接读即可；若无文件在读，则第一个读文件的进程必须做申请该文件的操作。只要有read进程在执行，则不允许writer进程去写。因此，仅当readcount=0,即无reader进程在读时，reader进程才需要执行wait(wmutex)操作。若wait(wmutex)操作成功，reader进程便可去读，相应地，做readcount+1操作。同理，仅当reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让writer进程写。28数据结构：Varrmutex,wmutex：semaphore：=1，1;readcount：integer：=0;29reader:repeat

wait(rmutex);

ifreadcount=0thenwait(wmutex);readcount:=readcount+1;

signal(rmutex);……readfile;……

wait(rmutex);readcount:=readcount-1;

ifreadcount=0thensignal(wmutex);

signal(rmutex);untilfalse第一个读者要检查文件的访问权是否空闲最后一个读进程要负责释放对文件的访问权申请对readcount的访问权释放对readcount的访问权读操作完毕，要修改readcount的值30writer:beginrepeat

wait(wmutex);……writingoperation;……

signal(wmutex);

untilfalse;end申请对文件的访问权释放文件的访问权31举例：文件Fr1,r2,w1三个进程并发执行初始：readcount=0,rmutex=1,wmutex=1执行过程readcountrmutexwmutex011r1:wait(rmutex);ifreadcount=0thenwait(wmutex)00readcount+11signal(rmutex)1开始读r2:wait(rmutex);0readcount+12signal(rmutex)1w1:wait(wmutex);－1r1:wait(rmutex);readcount－101signal(rmutex)1r2:wait(rmutex);readcount－100signal(rmutex)1ifreadcount≠0被阻塞ifreadcount≠0ifreadcount=0thensignal(wmutex)0w1:开始写signal(wmutex)1读结束读结束32二、利用信号量集机制 解决读者——写者问题问题描述：这里的读者—写者问题，增加了一条限制，即最多只允许RN个读者同时读。为此，引入一个信号量L，初始值为RN，通过执行wait（L，1，1）操作来控制读者的数目。VarRN:integer;L,mx:semaphore:Rn,1;33reader:repeat

Swait（L，1，1）;Swait（mx，1，0）；……readfile;……

Ssignal（L，1）；untilfalseifL>=1thenL:=L-1;ifmx>=1thenmx:=mx-0;//即mx值不变L:=L+1;34writer:repeatSwait(mx,1