《操作系统 计算题》由会员分享,可在线阅读,更多相关《操作系统 计算题(5页珍藏版)》请在金锄头文库上搜索。
1、1. 这是一个从键盘输入到打印机输出的数据处理流图,其中键盘输入进程通过缓冲区 buf1 把输入数据传送给计算进程,计算进程把 处理结果通过缓冲buf2传送给打印进程.bufl和buf2为临界资源,试写出键盘输入进程,计算进程及打印进程间的同步算 法.(10分)输入进程一 bufl 计算进程一 buf2 一打印进程从键盘输入到打印机输出的数据传送过程,可以看作是由键盘输入进程到计算进程,以及由计算进程到打印输出进程这两个数据 传送进程所组成.其中,对键盘输入进程而言,计算进程是消费者进程;而对打印输出进程而言,计算进程又是生产者进程.据此可将它 们之间的同步问题描述如下:var:mutex1,
2、mutex2,empty1,empty2,full1,full2:=1,1,1,1,0,0;IP:beginrepeatP(full);P(mutex1);until falseendOP:beginrepeatP(empty);P(mutex1);Take a charactor form buffer1;Add to ch1;input a charcter from keyboard;Add to buffer;V(mutex1);V(mutex1);V(empty1);P(empty2);P(mutex2);repeatp(full2);P(mutex2);Take a charact
3、or from buffer2;Add to printer controler;V(full);Take a charactor form ch1;until falseAdd to buffer2;start printer;V(mutex2);V(empty2);endV(mutex2);V(full2);until falseCP:begin2. 设在一个页面大小为1K的系统中,正在处理器上执行的一个进程的页表如图所示:起始页号和 块号均为0.1.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过 程.2.下列虚地址(十进制)对应与什么物理地址:5449,2221
4、.解: (10分)5449的物理地址为:3292221的物理地址为:22213. 设系统有三种类型的资源,数量为(4,2,2),系统中有进程A,B,C按如下顺序请求资源:进程A申请(3,2,1)进程B申请(1,0,1)进程A申请(0,1,0)进程C申请(2,0,0)请你给出一和防止end死锁的资源剥夺分配策略,完成上述请求序列,并列出资源分配过程,指明哪些进程需要等待,哪些资源被剥夺.(10分) 分配策略为:当进程Pi申请ri类资源时,检查ri中有无可分配的资源:有则分配给Pi;否则将Pi占有的资源全部释放而进入等 待状态.(Pi等待原占有的所有资源和新申请的资源) 资源分配过程:剩余资源 进
5、程A:(3,2,1) (1,0,1)进程B:(1,0,1) (0,0,0)进程A:(0,1,0)(不满足)(3,2,1)A的所有资源被剥夺,A处于等待 进程C:(2,0,0) (1,2,1) C,B完成之后,A可完成.4. 设公共汽车上,司机和售票员的活动分别是:司机: 启动车辆 售票员: 上乘客 正常行车 关车门 到站停车 售票 开车门 下乘客 在汽车不断地到站,停车,行使过程中,这两个活动有什么同步关系 并用wait和signal原语操作实现它们的同步.解:BEGIN integer stop,run;到站停车;售票;Stop:=0;signal(stop);wait(stop)Run:=
6、0;Goto L1;开车门;COBEGINEND下乘客;Driver: BEGINConductor: BEGINGoto L2;L1: wait(run);L2: 上乘客;END启动车辆;关车门;COEND正常行车;signal(run);END5, 某虚拟存储器的用户编程空间共321KB,内存为16KB假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下:则逻辑地址0A5C(H)所对应的物理地址是什么贡导物理块导力1 3+J54+J2 44107+J逻辑地址0A5CH)所对应的二进制表示形式是:0000 1010 0101 1100,由于1K=210,下划线部分前的编码为00
7、0010, 表示该逻辑地址对应的页号为3查页表,得到物理块号是4(十进制),即物理块地址为:0001 0010 0000 0000 ,拼接块 内地址 0000 0000 0101 1100,得 0001 0010 0101 1100,即 125C(H).6, 某段表内容如下: 段号0123段首地址 120K 760K 480K 370K段长度 40K30K 20K 20K 一逻辑地址为(2,154)的实际物理地址为多少答:逻辑地址(2154)表示段号为2,即段首地址为480K,154为单元号,则实际物理地址为480K+154.10.系统运行有三个进程:输入进程,计算进程和打印进程,它们协同完成
8、工作输入进程和计算进程之间共用缓冲区bufferl,计算进程 和打印进程之间共用缓冲区buffer2.输入进程接收外部数据放入bufferl中;计算进程从bufferl中取出数据进行计算,然后将结 果放入buffer2;打印进程从buffer2取出数据打印输出.用算法描述这三个进程的工作情况,并用wait和signal原语实现其同步操作(共8分) 解:(共8分)解答:输入进程, 计算进程和打印进程之间的同步问题描述如下:var:mutex1,mutex2,empty1,empty2, full1,full2:=1,1,1,1,0,0;wait(full1); wait(mutex1);endO
9、utP:beginInP:beginTake a data form buffer1;repeatrepeatAdd to ch1;wait(full2);wait(empty1);signal(mutex1);wait(mutex2);wait(mutex1);signal(empty1);Take a data from buffer2input a data from keyboard;calculate ch1;Add to printer controlerAdd to buffer1;wait (empty2);signal(mutex2);signal(mutex1);wait(
10、mutex2);signal(empty2);signal(full1);Take a data form ch1;start printer;until falseAdd to buffer2;until falseendsignal (mutex2);endCalP:beginsignal (full2);repeatuntil false11. 在一个请求分页系统中, 有一个长度为5 页的进程,假如系统为它分配 3 个物理块, 并且此进程的页面走向为2,3,2,1,5,2,4,5,3,2,5,2. 试用 FIFO 和LRU 两种算法分别计算出程序访问过程中所发生的缺页次数. (10分)解
11、:FIFO:LUR:2 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 53 2 5 2第 1页22255533 3第1页2222555 3第2页33322255第2页3352335第3页lll4442第3页ll4422缺页中断次数=6缺页中断次数=512.进程A1,A2,An通过K个缓冲区向进程B1,B2,Bm不断地发送消息发送和接收工作遵循如下规则:每个发送进程一次发 送一个消息,写入缓冲区,缓冲区大小与消息长度一致;对每个消息,B1,B2,Bm都需接收一次,读入各自的数据区内;K个缓冲区 都满时,发送进程等待,没有可读的消息时,接收进程等待.试用 wait 和 si
12、gnal 原语操作组织正确的发送和接收操作.(10分)解:BEGINFOR i:=1 TO m DOENDInteger Mutex, Avai ln, Ful lm ;BEGINInteger I;AvailI := k;PROCEDURE Send(K)Integer I;Mutex:=1;FullI := 0;BEGIN14. 用整型信号量描述在哲学家进餐问题中,至多允许4个哲学家同时进餐的算法.(10分)解:public class diningphilosophers semaphore fork = new semaphore 5 (1); semaphore room = new
13、 semaphore (4);int i;void philosopher (int i) while (true) think();wait (room);wait (forki);wait (fork (i+1) % 5);eat();signal (fork (i+1) % 5);signal (forki);signal (room); void main() parbegin (philosopher (0),philosopher (1),philosopher (2) philosopher (3), philosopher (4); 16. Jruassic公园有一个恐龙博物馆
14、和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客.旅客在博物馆逛了一会儿,然后排队 乘坐旅行车.当一辆车可用时,它载入一个旅客,然后绕公园行驶任意长的时间.如果n辆车都已被旅客乘坐游玩,则想坐车的旅客需 要等待;如果一辆车已经就绪,但没有旅客等待,那么这辆车等待使用信号量同步m个旅客和n辆车的进程.(10分)解:visitors二m; cars二n; mutex=l;Pvi() Pci() repeat repeat wait(cars); wait(visitors); wait(mutex); wait(mutex);travell; run; get off; stop;signa
15、l(cars); signal(visitors); wait(mutex); wait(mutex); until false; until false;get on; start; 17. 读者与写者问题 (reader - writer problems ) (10分)在计算机体系中,对一个共享文件进行操作的进程可分为两类:读操作和 写操作,它们分别被称为读者和写者.访问该文件时读者和写者,写者和写者间必须实现互斥.只有在没有读者访问文件时,写者才允 许修改文件.或者写者在修改文件时不允许读者去读,否则会造成读出的文件内容不正确.试写出算法描述读者和写者的问题.解:为了实现读者与写者的同步和互斥,我们设置一个信号量s,用于读