经典的PV问题

EditedByRunningwulf1PV问题：.................................................................................................................................................................11生产-消费模型，推广到多个生产者，多个消费者的生产消费模型；............................................11.1一个生产者、一个消费者、一个缓冲区的模型：信号量empty=0full=0.......................11.2一个生产者、一个消费者、一个缓冲区的第二种解法：信号量empty=1full=0............11.3一个生产者、一个消费者、n个缓冲区的模型：(不需要考虑互斥).................................21.4m个生产者、k个消费者、n个缓冲区的模型：（需要考虑互斥）.....................................22读者-写者模型，分两种：读者优先，写着优先；............................................................................22.1第一类读者-写者问题：读者优先..........................................................................................32.2第二类读者-写者问题：写者优先..........................................................................................33哲学家就餐模型，共3种解法；.......................................................................................................肆3.1改进解法1..............................................................................................................................肆3.2改进解法2..............................................................................................................................伍3.3改进解法3..............................................................................................................................陆4吸烟者问题，1种解法；....................................................................................................................柒5面包师问题，1种解法；....................................................................................................................未银行问题...............................................................................................................................................未6类似面包师的理发师问题，可以推广到多个理发师问题；............................................................酉爱睡觉的理发师问题[Dijkstra，1968]...........................................................................................酉7狒狒过河问题；...................................................................................................................................12巴拿马运河问题...................................................................................................................................128另类P，V问题。.................................................................................................................................13红客黑客过河问题...............................................................................................................................13某系统如此定义p,v操作：...............................................................................................................16PV问题：1生产-消费模型，推广到多个生产者，多个消费者的生产消费模型；设一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来，缓冲区只能容纳一个产品，生产者不断的生产产品，然后往空缓冲区送产品；消费者不断的从缓冲区中取出产品，并消费。1.1一个生产者、一个消费者、一个缓冲区的模型：信号量empty=0full=0P：Repeat生产一个产品送产品到缓冲区V(full);P(empty);Untilfalse;Q：Repeat：P(full);从缓冲区拿走一个产品V(empty);消费产品Untilfalse;1.2一个生产者、一个消费者、一个缓冲区的第二种解法：信号量empty=1full=0P:RepeatEditedByRunningwulf2P(empty);生产一个产品送产品到缓冲区V(full);Untilfalse;Q:RepeatP(full);从缓冲区取产品V(empty);消费产品Untilfalse;1.3一个生产者、一个消费者、n个缓冲区的模型：(不需要考虑互斥)信号量empty=n——空缓冲区的数目full=0——满缓冲区的数目P:i:=0Repeat生产产品P(empty);送产品到缓冲池buffer[i]V(full);i:=(i+1)modn;Untilfalse;Q:j:=0RepeatP(full);从缓冲池buffer[i]中取产品V(empty);消费产品j:=(j+1)modn;Untilfalse;1.4m个生产者、k个消费者、n个缓冲区的模型：（需要考虑互斥）信号量：empty=n——空缓冲区的数目full=0——满缓冲区的数目mutex1(P进程互斥),mutex2(Q进程互斥)=1——互斥信号量，实现临界区（缓冲池）的互斥P:i:=0Repeat生产产品P(empty);P(mutex1);添加产品到缓冲区buffer[i]i:=(i+1)modn;V(mutex1);V(full);Untilfalse;Q:j:=0RepeatP(full);P(mutex2);从缓冲区buffer[j]中取产品j:=(j+1)modn;V(mutex2);V(empty);消费产品Untilfalse;2读者-写者模型，分两种：读者优先，写着优先；某个共享文件F，系统允许若干进程对文件F读或写，但规定：1、多个进程可以同时读文件F；2、任一个进程在对文件F进行写时不允许其他进程对文件进行读或写；3、当有进程在读文件是不允许任何进程去写文件。EditedByRunningwulf32.1第一类读者-写者问题：读者优先除非有写者在写文件，否则没有一个读者需要等待。分析思想：读者到：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等写者到：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待信息量：readcount=0——记录当前正在读的读者进程数，这是一个共享变量，需要互斥使用mutex=1——互斥信息量write=1——用于写者互斥，或第一个读者和最后一个读者与写者互斥READ：Repeat;P(mutex);readcount:=readcount+1;if(readcount=1)P(write);V(mutex);读文件P(mutex);readcount:=readcount-1;if(readcount=0)V(write);V(mutex);UntilfalseWRITE:RepeatP(write);写文件V(write);Untilfalse;2.2第二类读者-写者问题：写者优先一旦一个写者到来，它应该尽快对文件进行写操作。则新来到的读者不允许进行读操作。分析思想：读者到：1）无读者且无写者，新读者读2）有读者但无写者等待，新读者读3）有读者但有写着等待，读者等待4）有写者在写，新读者等待写者到：1）无读者且无写者，新写者写2）有读者在读，新写者等待3）有写者写，新写者等待信息量：read:=1——读者信息量，用于第一个写者与读者互斥readcount:=0——记录当前读者的进程数mutex:=1——互斥信息量writecount:=0——记录当前写者排队的进程数write:=1——写者信息量，用于写者互斥，第一个读者与写者互斥EditedByRunningwulf-4-mutex2:=1——互斥信息量P:RepeatP(read)P(mutex)V(read)readcount:=readcount+1;if(readcount=1)P(write)V(mutex)读文件P(mutex)readcount:=readcount-1if(readcount=0)V(write)V(mutex)UntilfalseQ:RepeatP(mutex2)writecount:=writecount+1if(writecount=1)P(read)V(mutex2)P(write)写文件V(write)P(mutex2)writecount:=writecount-1if(writecount=0)V(read)V(mutex2)Untilfalse;3哲学家就餐模型，共3种解法；哲学家就餐问题[Dijkstra，1965]问题描述：有五个哲学家以思考、用餐交替进行的方式生活，他们坐在一张圆桌边，桌子上有5个盘子和5只筷子。当一个哲学家思考时，他不与邻座的哲学家发生联系，当一个哲学家感觉到饿了，他就试图拿起他左右两边的筷子用餐。如果该哲学家的邻座已经拿到筷子，则他可能只能拿到一只