《各章例题集2011[1].6》由会员分享，可在线阅读，更多相关《各章例题集2011[1].6（115页珍藏版）》请在金锄头文库上搜索。
1、操 作 系 统各章例题集操作系统1操 作 系 统第二章 进程管理2操 作 系 统1. 利用记录型信号量解决生产者消费者问题 l简单情况（只有同步）：一个buffer，一个生产者，一个 消费者，生产者不断地生产，消费者不断地消费。只有 buffer为空时生产者才能进行putdata操作，只有buffer有数 据时消费者才能进行getdata操作。设置2个信号量full和empty。full表示buffer是否有数据， 初值为0；empty表示buffer是否为空，初值为1;取值范围 都是-1，1。 buffer生产者消费者3操 作 系 统 Var empty, full: semaphore :
2、=1, 0; buffer: array1 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，多个生产者，多个消费者，
3、生产者不断地生产，消费者 不断地消费。只有buffer为空时生产者才能进行putdata操作，只有buffer有数 据时消费者才能进行getdata操作。buffer变成了临界资源，不允许多个进程同时操作 buffer。即不允许多个生产者同时进行putdata操作，也不 允许多个消费者同时进行getdata操作。 与简单情况相比，需要增加一个信号量mutex来实现对 buffer的互斥访问，其初始值为1。 信号量full和empty的变化范围与简单情况有所不同。 full初值仍然为0，变化范围：-n，1，n是消费者进程总 数量；empty初值仍然为1，变化范围：-m，1，m是生产 者进程总数量
4、。 buffer生 产 者消 费 者5操 作 系 统Var mutex, empty, full: semaphore :=1, 1, 0; buffer: array1 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 fals
5、e; end parend end说明： （1）在生产者进程和消费者进程中，V操作的次序无关紧要，但两个P操作 的次序却不能颠倒，否则可能导致死锁，即，应先执行对资源信号量的wait操 作，再执行对互斥信号量的wait操作。 （2）由于buffer只有一个，full和empty就可以保证对buffer的互斥操作，故 mutex也可以省略，但如果buffer有多个，则mutex不能省略。6操 作 系 统l一般意义的“生产者消费者”问题：N个buffer，多个生产者，多个消费者，循环存取buffer。 l(教材上的)buffer生 产 者消 费 者bufferbufferbufferbuffer7
6、操 作 系 统1. 利用记录型信号量解决生产者消费者问题假定：在P-C之间的公用缓冲池中，具有n个缓冲区；利用互斥信号量mutex实现各进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓 冲区的数量。这些生产者和消费者相互等效，只要缓冲池未满，生产者 便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓 冲池中取走一个消息。full是“满”数目，初值为0，empty是 “空”数目，初值为N。 实际上，full和empty是同一个含义 ：full + empty = N初值为18操 作 系 统每个进程中各个P操作的次序很重要：先检查资源数目，再检查是否互斥否则可
7、能死锁9操 作 系 统Var mutex, empty, full:semaphore = 1,n,0;buffer:array0, , n-1 of item;in, out: integer = 0, 0;beginparbeginproceducer:beginrepeat 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:beginrepeatwa
8、it(full);wait(mutex);nextc = buffer(out);out = (out+1) mod n;signal(mutex);signal(empty);consumer the item in nextc;until false;endparendend 11操 作 系 统 练 习桌上有一只盘子，每次只能放入一个水果 。爸爸专向盘中放苹果，妈妈专向盘中放桔 子，一个女儿专等吃盘中的苹果，一个儿子 专等吃盘中的桔子。试用P,V操作写出他们能 同步的程序。桌上有1空盘，允许存放1个水果。爸爸向盘中 放苹果，也可以向盘中放桔子。儿子专等吃盘中的 桔子，女儿专等吃盘中的苹果。
9、规定当盘空时一次 只能放1个水果供吃者取用。请用Wait()、Signal() 原语实现爸爸、儿子、女儿三个并发进程的同步。 12操 作 系 统semaphore chopstick5=1，1，1，1，1; semaphore count=4; void philosopher(int i) while(true) think(); wait(count); /请求进入房间进餐 wait(chopsticki); /请求左手边的筷子 wait(chopstick(i+1)%5); /请求右手边的筷子 eat(); signal(chopstick(i+1)%5); /释放右手边的筷子 sign
10、al(chopsticki); /释放左手边的筷子 signal(count); /退出房间释放信号量room 解法一：哲学家进餐问题13操 作 系 统14操 作 系 统利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界 资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND 同步问题，故用AND信号量机制可获得最简洁的解法。Var chopsiick array 0, , 4 of semaphore = (1,1,1,1,1);processirepeatthink;Sswait(chopstick(i+1) mod 5, chopstick i);e
11、at;Ssignat(chopstick (i+1) mod 5, chopstick i);until false; 15操 作 系 统ar mutex, empty, full:semaphore = 1, n, 0;buffer:array0, , n-1 of item;in out:integer = 0, 0;beginparbeginproducer:beginrepeat produce an item in nextp; Swait(empty, mutex);buffer(in) = nextp;in = (in+1)mod n;Ssignal(mutex, full);u
12、ntil false;end consumer:beginrepeatSwait(full, mutex);nextc = buffer(out);out = (out+1) mod n;Ssignal(mutex, empty);consumer the item in nextc;until false;endparendend 利用AND信号量解决生产者消费者问题 16操 作 系 统读者-写者问题可描述如下： Var rmutex, wmutex:semaphore =1,1;Readcount:integer = 0;beginparbeginReader:begin /读者repea
13、twait(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;endwriter:begin /写者repeatwait(wmutex);perform write operation;signal(wmutex);until false;
14、endparendend 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 - 读互斥信号
15、量，初值为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操 作 系 统理发师问题
