各章例题集2011[1].6.ppt

操 作 系 统各章例题集——操作系统1操 作 系 统第二章 进程管理2操 作 系 统1. 利用记录型信号量解决生产者—消费者问题 l简单情况（只有同步）：一个buffer，一个生产者，一个 消费者，生产者不断地生产，消费者不断地消费只有 buffer为空时生产者才能进行putdata操作，只有buffer有数 据时消费者才能进行getdata操作设置2个信号量full和emptyfull表示buffer是否有数据， 初值为0；empty表示buffer是否为空，初值为1;取值范围 都是[-1，1] buffer生产者消费者3操 作 系 统 Var empty, full: semaphore :=1, 0; buffer: array[1] of item; beginparbegin producer : beginrepeatwait(empty);putdata;signal(full);until false; endconsumer : beginrepeatwait(full);getdata;signal(empty);until false; end parend end 说明：对资源信号量empty和full的wait和signal操作， 同样需要成对地出现，但处于不同的程序中。

4操 作 系 统l复杂情况（既有同步，又有互斥）：一个buffer，多个生产者，多个消费者，生产者不断地生产，消费者 不断地消费只有buffer为空时生产者才能进行putdata操作，只有buffer有数 据时消费者才能进行getdata操作buffer变成了临界资源，不允许多个进程同时操作 buffer即不允许多个生产者同时进行putdata操作，也不 允许多个消费者同时进行getdata操作 与简单情况相比，需要增加一个信号量mutex来实现对 buffer的互斥访问，其初始值为1 信号量full和empty的变化范围与简单情况有所不同 full初值仍然为0，变化范围：[-n，1]，n是消费者进程总 数量；empty初值仍然为1，变化范围：[-m，1]，m是生产 者进程总数量 buffer生 产 者消 费 者5操 作 系 统Var mutex, empty, full: semaphore :=1, 1, 0; buffer: array[1] of item; beginparbegin producer : beginrepeatwait(empty);wait(mutex);putdata;signal (mutex);signal(full);until false; endconsumer : beginrepeatwait(full);wait(mutex);getdata;signal (mutex); signal(empty);until false; end parend end说明： （1）在生产者进程和消费者进程中，V操作的次序无关紧要，但两个P操作 的次序却不能颠倒，否则可能导致死锁，即，应先执行对资源信号量的wait操 作，再执行对互斥信号量的wait操作。

（2）由于buffer只有一个，full和empty就可以保证对buffer的互斥操作，故 mutex也可以省略，但如果buffer有多个，则mutex不能省略6操 作 系 统l一般意义的“生产者—消费者”问题：N个buffer，多个生产者，多个消费者，循环存取buffer l(教材上的)buffer生 产 者消 费 者bufferbufferbufferbuffer……7操 作 系 统1. 利用记录型信号量解决生产者—消费者问题假定：ü在P-C之间的公用缓冲池中，具有n个缓冲区；ü利用互斥信号量mutex实现各进程对缓冲池的互斥使用；ü利用信号量empty和full分别表示缓冲池中空缓冲区和满缓 冲区的数量ü这些生产者和消费者相互等效，只要缓冲池未满，生产者 便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓 冲池中取走一个消息full是“满”数目，初值为0，empty是 “空”数目，初值为N 实际上，full和empty是同一个含义 ：full + empty == N初值为18操 作 系 统每个进程中各个P操作的次序很重要：先检查资源数目，再检查是否互斥――否则可能死锁9操 作 系 统Var mutex, empty, full:semaphore￿￿ ∶=￿￿ 1,n,0;￿￿buffer:array［0, …, n-1］ of item;￿￿in, out: integer￿￿ ∶=￿￿ 0, 0;￿￿begin￿￿parbegin￿￿proceducer:begin￿￿repeat￿￿￿￿ …￿￿producer an item nextp;￿￿￿￿ …￿￿wait(empty);￿￿wait(mutex);￿￿buffer(in)￿￿ ∶=￿￿ nextp;￿￿in￿￿ ∶=￿￿ (in+1) mod n;￿￿signal(mutex);￿￿signal(full);￿￿until false;￿￿end￿￿ 10操 作 系 统consumer:begin￿￿repeat￿￿wait(full);￿￿wait(mutex);￿￿nextc￿￿ ∶ =￿￿ buffer(out);￿￿out￿￿ ∶ =￿￿ (out+1) mod n;￿￿signal(mutex);￿￿signal(empty);￿￿consumer the item in nextc;￿￿until false;￿￿end￿￿parend￿￿end 11操 作 系 统 练 习•桌上有一只盘子，每次只能放入一个水果 。

爸爸专向盘中放苹果，妈妈专向盘中放桔 子，一个女儿专等吃盘中的苹果，一个儿子 专等吃盘中的桔子试用P,V操作写出他们能 同步的程序桌上有1空盘，允许存放1个水果爸爸向盘中 放苹果，也可以向盘中放桔子儿子专等吃盘中的 桔子，女儿专等吃盘中的苹果规定当盘空时一次 只能放1个水果供吃者取用请用Wait()、Signal() 原语实现爸爸、儿子、女儿三个并发进程的同步 12操 作 系 统semaphore chopstick[5]={1，1，1，1，1}; semaphore count=4; void philosopher(int i) {while(true) {think(); wait(count); //请求进入房间进餐 wait(chopstick[i]); //请求左手边的筷子 wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat(); signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(chopstick[i]); //释放左手边的筷子 signal(count); //退出房间释放信号量room } } 解法一：哲学家进餐问题13操 作 系 统14操 作 系 统利用AND信号量机制解决哲学家进餐问题￿￿在哲学家进餐问题中，要求每个哲学家先获得两个临界 资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND 同步问题，故用AND信号量机制可获得最简洁的解法。

Var chopsiick array ［0, …, 4］ of semaphore￿ ∶ =￿ (1,1,1,1,1);￿processi￿repeat￿think;￿Sswait(chopstick［(i+1) mod 5］, chopstick ［i］);￿eat;￿Ssignat(chopstick ［(i+1) mod 5］, chopstick ［i］);￿until false;￿ 15操 作 系 统ar mutex, empty, full:semaphore￿￿ ∶ =￿￿ 1, n, 0;￿￿buffer:array［0, …, n-1］ of item;￿￿in out:integer￿￿ ∶ =￿￿ 0, 0;￿￿begin￿￿parbegin￿￿producer:begin￿￿repeat￿￿￿￿ …￿￿produce an item in nextp;￿￿￿￿ …￿￿Swait(empty, mutex);￿￿buffer(in)￿￿ ∶ =￿￿ nextp;￿￿in￿￿ ∶ =￿￿ (in+1)mod n;￿￿Ssignal(mutex, full);￿￿until false;￿￿end￿￿ consumer:begin￿￿repeat￿￿Swait(full, mutex);￿￿nextc￿￿ ∶ =￿￿ buffer(out);￿￿out￿￿ ∶ =￿￿ (out+1) mod n;￿￿Ssignal(mutex, empty);￿￿consumer the item in nextc;￿￿until false;￿￿end￿￿parend￿￿end 利用AND信号量解决生产者—消费者问题 16操 作 系 统读者-写者问题可描述如下：￿￿ Var rmutex, wmutex:semaphore∶ =1,1;￿￿Readcount:integer￿￿ ∶ =￿￿ 0;￿￿begin￿￿parbegin￿￿Reader:begin //读者repeat￿￿wait(rmutex);￿￿if readcount=0 then wait(wmutex);￿￿Readcount￿￿ ∶ =￿￿ Readcount+1;￿￿signal(rmutex);￿￿￿￿ …￿￿perform read operation;￿￿￿￿ …￿￿wait(rmutex);￿￿readcount￿￿ ∶ =￿￿ readcount-1;￿￿if readcount=0 then signal(wmutex); ￿￿ signal(rmutex);￿￿until false;￿￿end￿￿writer:begin￿￿ //写者repeat￿￿wait(wmutex);￿￿perform write operation;￿￿signal(wmutex);￿￿until false;￿￿end￿￿parend￿￿end￿￿ 17操 作 系 统Reader() {While(1) { P(s); P(rmutex); If (count==0) P(wmutex); /*当第1 个读者读文件时，阻止写者写*/ count++ V(rmutex); V(s); 读文件； P(rmutex); count--;} If (count==0) V(wmutex); /*当最后1个读 者读完文件时，允许写者写*/V(rmutex); }writer() {While(1) { P(s); P(wmutex); 写文件； V(wmutex); V(s);} }第二类读者写者问题——写优先设3个信号量： •rmutex --- 读互斥信号量，初值为1； •wmutex --- 写互斥信号量，初值为1； •s --- 用于在写进程到达后封锁后续的读者，初值为1； •count --- 共享变量，用于记录当前正在读文件的读者数目，初值为 0；18操 作 系 统读者：while (true) {P(w);P (readcount);V(w);读V(readcount);};写者：while (true) {P(w);for i:=1 to n do P(readcount);写for i:=1 to n do V(readcount);V(w);};第二类读写问题（解法2）设2个信号量：lW是读者和写者公用的互斥变量，用来互斥读写或者写写同时进 行，初值为1lReadcount用来记录当前有多少个读者在访问数据，初值n19操 作 系 统理发师问题。