管理学院*12.4 经典进程的同步问题管理学院*2生产者─消费者问题消费者生产者管理学院*3管理学院*4问题分析： v ①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区 v ②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行 管理学院*5问题解答： v①所用信号量设置如下： Ⅰ）同步信号量empty，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用Ⅱ）同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用 Ⅲ）互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问缓冲池 管理学院*6用信号量机制解决的算法描述如下：v 生产者i 消费者jv 生产出一产品； P（full）；v P（empty）； P（mutex）； v P（mutex）； 从缓冲区取出一产品； v 将该产品放入缓冲区； V（mutex）； v V（mutex）； V（empty）； v V（full）； 消费该产品； 管理学院*7P操作的顺序可换吗？管理学院*8若两个wait操作互换——死锁v 将生产者的两个P操作对调。
wait(mutex); wait(empty);v 考虑系统中缓冲区全满时，若一生产者进程先执行了 wait(mutex)操作并获得成功，当再执行wait(empty)操作时，它将因失败而进入阻塞状态，期待着消费者执行 signal(empty)来唤醒自己，在此之前，不可能执行 signal(mutex)操作，从而使企图通过wait(mutex)进入自己的临界区的其他生产者和所有的消费者进程全部进入 阻塞状态，从而引起死锁v 消费者进程的两个P操作对调，同样可能造成死锁管理学院*9若两个V操作互换？v 生产者进程的两个V操作互换，或消费者进程呢的两个V操作，不会引起死锁，只是使临界资源的释放略为推迟一些管理学院*102.4 经典进程的同步问题2.4.1 生产者——消费者问题相互合作的进程关系的一种抽象1. 利用记录型信号量解决生产者——消费者问题假定在生产者和消费者之间的公用缓冲池具有n个缓冲 区，可利用互斥信号量mutex实现诸进程对缓冲池的互斥 使用，利用信号量empty和full分别表示缓冲池中空缓冲 区和满缓冲区的数量Var mutex, empty, full: semaphore :=1, n, 0;buffer: array [ 0, …, n-1] of item;in, out: integer :=0, 0;beginparbeginproducer : beginrepeat…produce an item in nexp;…wait(empty);wait(mutex);buffer(in):=nexp;in:=(in+1) mod n;signal(mutex);signal(full);until false; endconsumer : beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty);consume the item in nexc; until false; endparendend注意： 1。
每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成 对地出现对资源信号量empty和full的wait和signal操作，同样需要成对地 出现，但处于不同的程序中在每个程序中的多个wait操作顺序不能颠倒应先执行对资源信 号量的wait操作，再执行对互斥信号量的wait操作，否则可能引起进 程死锁管理学院*112.4 经典进程的同步问题2. 利用AND信号量解决生产者——消费者问题wait(empty)和wait(mutex) →Swait(empty, mutex)； signal(mutex)和signa1(empty) → Ssignal(mutex, empty)； wait(full)和wait(mutex) → Swait(full, mutex)； signal(mutex)和signal(full) → Ssignal(mutex, full)Var mutex, empty, full: semaphore :=1, n, 0;buffer: array [ 0, …, n-1] of item;in, out: integer :=0, 0;beginparbeginproducer : beginrepeat…produce an item in nexp;…Swait(empty, mutex);buffer(in):=nexp;in:=(in+1) mod n;Ssignal(mutex, full);until false; endconsumer : beginrepeatSwait(full, mutex);nextc:=buffer(out);out:=(out+1) mod n;Ssignal(mutex, empty);consume the item in nexc; until false; endparendend管理学院*122.4 经典进程的同步问题2.4.2 哲学家进餐问题 w 五个哲学家共用一张圆桌，分别坐 在周围的五张椅子上，在桌子上有五 只碗和五只筷子，他们的生活方式是 交替地进行思考和进餐。
平时，一个 哲学家进行思考，饥饿时便试图取用 其左右最靠近他的筷子，只有在他拿 到两只筷子时才能进餐进餐毕，放 下筷子继续思考5143215432管理学院*132.4 经典进程的同步问题1. 利用记录型信号量解决哲学家进餐问题放在桌子上的筷子是临界资源，在一段时间内只允 许一个哲学家使用为实现对筷子的互斥使用，用一个 信号量表示一只筷子，五个信号量构成信号量数组Var chopstick: array [0, …, 4] of semaphore;所有信号量均被初始化为1第i 位哲学家的活动可描述为：repeatwait(chopstick[ i ]);wait(chopstick[ ( i +1) mod 5] );…eat;…signal(chopstick[ i ]);signal(chopstick[ ( i +1) mod 5] );…think;until false;当哲学家饥饿时，总 是先拿左边的筷子， 再拿右边的筷子当哲学家进餐毕，先 放下左边的筷子，再 放下右边的筷子管理学院*142.4 经典进程的同步问题• 算法虽能保证相邻两位哲学家不 会同时进餐，但有可能引起死锁。
假如五位哲学家同时饥饿而各自拿 起左边的筷子时，就会使五个信号 量chopstick均为0，当他们再试图 去拿右边的筷子时，都将因无筷子 可拿而无限等待解决方法： Ë 至多只允许有四位哲学家同时去拿左边的筷子 ，最终能保证至少有一位哲学家能够进餐，并在 用毕后释放出他用过的两只筷子，从而使更多的 哲学家能够进餐 Ë 仅当哲学家的左右两只筷子均可用时，才允许 他拿起筷子进餐 Ë 规定奇数号哲学家先拿他左边的筷子，然后再 去拿右边的筷子；偶数号哲学家则相反5143215432管理学院*15课堂练习v 请写出上述哲学家进餐问题的解法3的算法伪代码： ٭规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反这样，任何一个哲学家拿到一只筷子以后，就已经阻止了他邻座的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人饿死管理学院*16processiRepeatthink；if I mod 2 ==0 then {P(c[I+1 mod 5]); P(c[I]); eat;V(c[I]); V(c[I+1 mod 5]); }else {P(c[I]); P(c[I+1 mod 5]); eat;V(c[I+1 mod 5]); V(c[I]); }Until false；管理学院*172.4 经典进程的同步问题2. 利用AND信号量机制解决哲学家进餐问题• 在哲学家进餐问题中，要求每个哲学家先获得两个临界 资源(筷子)后方能进餐。
本质上是AND同步问题Var chopstick: array [0, …, 4] of semaphore:=(1, 1, 1, 1, 1); Process irepeatthink;Swait(chopstick[ ( i +1) mod 5] , chopstick[ i ] );eat;Ssignal(chopstick[ ( i +1) mod 5] , chopstick[ i ] ); until false;管理学院*182.4 经典进程的同步问题2.4.3 读者——写者问题v 一个数据文件或记录可被多个进程共享v 只要求读文件的进程称为“Reader进程”，其它进程则称 为“Writer进程”v 允许多个进程同时读一个共享对象，但不允许一个Writer 进程和其他Reader进程或Writer进程同时访问共享对象读者——写者问题”是指保证一个Writer进程必须与其他 进程互斥地访问共享对象的同步问题管理学院*19问题分析： v①读者—写者之间的互斥关系： 写者与写者的互斥、写者与读者的互斥设 一个公用的初值为1的互斥信号量Wmutexv②读者—读者之间又有了互斥关系：再设一个读者公用的初值为1的互斥信号量 rmutex，实现各个读者间互斥的访问Readcount 。
管理学院*20问题解答： v所用信号量和其他变量设置如下：٭Ⅰ）互斥信号量Wmutex，初值为1，用于实现写者与其他写者或读者互斥地访问共享的数据对象٭Ⅱ）互斥信号量rmutex，初值为1，用于实现诸读者互斥地访问读者计数器变量٭Ⅲ）整型变量Readcount，初值为0，用于对读者进行记数 管理学院*21用信号量机制解决读者—写者问题v 读者 写者 v P（rmutex）； P（Wmutex）；v 若Readcount=0则 P（Wmutex）； 对数据对象进行写操作；v Readcount加1； V（Wmutex）； v V（rmutex）；v 读数据对象； vP（rmutex）；v Readcount减1； v 若Readcount =0则 V（Wmutex）； v V（rmutex）； 管理学院*222.4 经典进程的同步问题1. 利用记录型信号量解决读者——写者问题• 为实现Reader与Writer进程间在读或写时的互斥而设 置了一个互斥信号量Wmutex。
设置整型变量 Readcount表示正在读的进程数目• 由于只要有一个Reader进程在读，便不允许Writer进程 去写因此，仅当Readcount=0，表示。