操作系统大题

《操作系统大题》由会员分享，可在线阅读，更多相关《操作系统大题（19页珍藏版）》请在装配图网上搜索。

1、1. 这是一个从键盘输入到打印机输出的数据处理流图，其中键盘输入进程通 过缓冲区 buf1 把输入数据传送给计算进程，计算进程把处理结果通过缓冲 buf2传送给打印进程。bufl和buf2为临界资源，试写出键盘输入进程，计 算进程及打印进程间的同步算法。(10分)输入进程f bufl f计算进程f buf2 f打印进程 解答：从键盘输入到打印机输出的数据传送过程，可以看作是由键盘输入进程到计算进程， 以及由计算进程到打印输出进程这两个数据传送进程所组成。其中，对键盘输入进程而言， 计算进程是消费者进程；而对打印输出进程而言，计算进程又是生产者进程。据此可将它 们之间的同步问题描述如下：var：

2、mutexl， mutex2， emptyl， empty2， fulll， full2：=l， l， l， l， 0， 0； IP:beginrepeatP(empty);P(mutexl);input a charcter from keyboard;Add to buffer;V(mutexl);V(full);until falseendCP:beginrepeatP(full);P(mutexl);Take a charactor form bufferl;Add to chl;V(mutexl);V(emptyl);P(empty2);P(mutex2);Take a charac

3、tor form chl;Add to buffer2;V(mutex2);V(full2);until falseendOP:beginrepeatp(full2);P(mutex2);Take a charactor from buffer2;Add to printer controler;start printer;V(mutex2);V(empty2);until false end 2设在一个页面大小为 1K 的系统中，正在处理器上执行的一个进程的页表如图所示：页号状态位 访问位 修改位 物理块号01104111172000-310024000-51010起始页号和块号均为0。1详

4、述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程2下列虚地址（十进制）对应与什么物理地址：5449，2221。解： （10分）HhiiarD tnPu辭 19ia1Figure 8.S Operation of PagingTraits la If un Ijookasicle BuIEf ITLB； FljRH875449 的物理地址为： 3292221 的物理地址为： 22213设系统有三种类型的资源，数量为（4，2，2），系统中有进程 A，B，C 按如 下顺序请求资源：进程A申请（3, 2, 1）进程B申请(1, 0, 1)进程A申请(0, 1, 0)进程C申请(

5、2, 0, 0)请你给出一和防止死锁的资源剥夺分配策略,完成上述请求序列,并列出 资源分配过程,指明哪些进程需要等待,哪些资源被剥夺。(10分) 解：(10分) 分配策略为：当进程pi申请r类资源时，检査r中有无可分配的资源：有则分配给与 否则将气占有的资源全部释放而进入等待状态。i等待原占有的所有资源和新申请的资源)资源分配过程：剩余资源进程 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可完成

6、。4设公共汽车上,司机和售票员的活动分别是司机： 启动车辆正常行车到站停车售票员： 上乘客关车门 售票开车门、下乘客在汽车不断地到站，停车，行使过程中，这两个活动有什么同步关系？并用wait和signal原语操作实现它们的同步。Stop:=0;Run:=0;解： BEGIN integer stop,run;COBEGINDriver: BEGINL1: wait(run); 启动车辆；正常行车 到站停车signal(stop);Goto L1;ENDConductor: BEGINL2： 上乘客；关车门；signal(run); 售票； wait(stop);开车门；下乘客；Goto L2;

7、ENDCOENDEND5、某虚拟存储器的用户编程空间共321KB,内存为16KB。假定某时刻一用户页表中已调入内存 的页面的页号和物理块号的对照表如下：页号物理块号152103447则逻辑地址0A5C （H）所对应的物理地址是什么？答：逻辑地址0A5CH）所对应的二进制表示形式是：0000 1010 0101 1100由于1K=21Q 下划线部分前的编码为000010，表示该逻辑地址对应的页号为3査页表，得到物理块号是4 （十进制），即物理块地址为：0001 0010 0000 0000，拼接块内地址0000 0000 0101 1100， 得 0001 0010 0101 1100,即 12

8、5C （H）。6、某段表内容如下：段号段首地址段长度0120K40K1760K30K2480K20K3370K20K一逻辑地址为（ 2， 154）的实际物理地址为多少？答：逻辑地址（2154）表示段号为 2，即段首地址为 480K， 154为单元号，则实际物理地址 为 480K+154。7、设系统中有三种类型的资源（A, B，C）和五个进程（P1, P2, P3, P4, P5），A资 源的数量为17, B资源的数量为5, C资源的数量为20。在T0时刻系统状态如表1和表2 所示。（共10 分）系统采用银行家算法实施死锁避免策略。 T0 时刻是否为安全状态？若是,请给出安全序列。 在 T0 时

9、刻若进程 P2 请求资源（0, 3, 4）,是否能实施资源分配？为什么？ 在的基础上，若进程P4请求资源（2, 0, 1）,是否能实施资源分配？为什么？ 在的基础上，若进程P1请求资源（0, 2, 0）,是否能实施资源分配？为什么？最大资源需求量已分配资源数量ABCABCP1559212P2536402P34011405P4425204P5424314表 2 T0 时刻系统状态ABC剩余资源数2338系统中有五个进程P、P2、P3、P4、P5,有三种类型的资源：R1、R2、和R3。在T0 时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：（共9 分， 每小题 3分）1 T0

10、 时刻是否为安全状态？为什么？2. 若这时P4请求资源（1, 2, 0）,是否能实施资源分配？为什么？3. 在上面的基础上，若进程P3请求资源（0, 1, 0），是否能实施资源分配？为什么？T0时刻系统状态已分配资源数量最大资源需求量R1R2R3R1R2R3Pl001001P2200275P3003665P4115435P5033065R1R2R3剩余资源数330解：（共 9 分，每小题 3 分）1. T0时刻是安全的，安全序列为：P1, P4, P5, P2, P32. P4 请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全 序列为： P1，P4，P5，P2，P33. P3

11、 请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不 能实施资源分配。9一个进程的大小占5个页面，每页的大小为1K,系统为它分配了 3个物理块。当前进程的页表如图所示：（共 8 分）块号 存在位 P访问位 R修改位 M0x1C1100x3F1110000x5D1000001有那些页面不在内存？（2 分）2.请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址 （用十六进制表示），并说明理由。（6分）解：（共 8 分）不在内存的是第 2 和 4 页（按页号），或第 3和 5页（按序号）。（2 分）Ox3B7的物理地址=0x 73 B7 （2分）0x12 A

12、5的物理地址=0x176 A5,缺页，换出第三页。（2分）0x1432地址越界，出错。（2分）10.系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工 作。输入进程和计算进程之间共用缓冲区bufferl,计算进程和打印进程之间共 用缓冲区buffer2。输入进程接收外部数据放入bufferl中;计算进程从bufferl 中取出数据进行计算，然后将结果放入buffer2；打印进程从buffer2取出数据 打印输出。用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。 （共 8分）解：（共 8 分） 解答：输入进程、计算进程和打印进程之间的同步问题描述如下：

13、 var：mutex1 ， mutex2， empty1 ， empty2， full1 ， full2：=1 ， 1 ， 1 ， 1 ， 0， 0； InP:beginrepeatwait（empty1）;wait（mutex1）;input a data from keyboard;Add to buffer1;signal（mutex1）; signal（full1）;until falseendCalP:beginrepeatwait（full1）; wait（mutex1）;Take a data form buffer1;Add to ch1;signal（mutex1）;sign

14、al（empty1）;calculate ch1; wait (empty2); wait(mutex2);Take a data form ch1; Add to buffer2;signal (mutex2); signal (full2);until falseendOutP:beginrepeat wait(full2); wait(mutex2);Take a data from buffer2; Add to printer controler; signal(mutex2); signal(empty2);start printer;until false end（评分标准：信号

15、量设置 2 分，输入进程、计算进程、打印进程各 2 分） 11在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配 3 个物 理块，并且此进程的页面走向为 2，3，2，1，5，2，4，5，3，2，5，2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。（10分）解：FIFO：232152453252第1页222555333第2页33322255第3页1114442缺页中断次数= 6LUR：232152453252第1页22225553第2页3352335第3页114422缺页中断次数 = 512. 进程 A1，A2，An 通过 K 个缓冲区向进程 B

16、1，B2，Bm 不断地发送 消息。发送和接收工作遵循如下规则：1 每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度一致；2.对每个消息，B1, B2,，Bm都需接收一次，读入各自的数据区内；3 K 个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。试用wait和signal原语操作组织正确的发送和接收操作。（10分）解：BEGINInteger Mutex, Availn, Fullm;Integer I;Mutex:=1;FOR i:=1 TO m DOBEGINAvailI := k;FullI := 0;ENDPROCEDURE Send(K) Integer

17、I;BEGIN 13一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所 示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算 法，哪一个物理块将被换出？并解释原因（ 10分）页号块号加载时间访问时间访问位R修改位M20601610111130160000226162103320163111. IFO算法2. LRU算法3. CLOCK 算法4. 当页面的访问串为：“4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2”的OPT算法解： 1.换出第3 号虚页，因为它加载的时间最早；2. 换出第1号虚页,因为它最近最久没被访问；3. 换出第

18、1号虚页,因为它最近既没被访问,又没被修改；4. 换出第3号虚页,因为它离访问点最远。14. 用整型信号量描述在哲学家进餐问题中,至多允许4个哲学家同时进餐的算法（。 10分） 解： public class diningphilosophers semaphore fork = new semaphore 5 （1）;semaphore room = new semaphore （4）;int i;void philosopher (int i) while (true) think();wait (room);wait (forki);wait (fork (i+1) % 5);eat()

19、;signal (fork (i+1) % 5);signal (forki);signal (room); void main() parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4); 15考虑一个有 150个存储器单元的系统，如下分配给三个进程： 进程 最大 占有1 70452 60403 6015使用银行家算法，以确定下面的任何一个请求是否安全：a. 第4个进程到达，最多需要60个存储单元，最初需要25个单元;b. 第4个进程到达，最多需要60个存储单元

20、，最初需要35个单元;如果安全给出安全序列；若不安全给出结果分配简表。（10分） 解：进程最大占有尚需可用170452525260402036015454602535安全序列为：1、2、3、4所以系统是安全的，可以进行分配。b进程最大占有尚需可用170452515260402036015454603525当前可用的资源不够任何一个进程运行完毕，所以不安全。16. Jruassic公园有一个恐龙博物馆和一个公园有m个旅客和n辆车，每辆车只能容纳一 个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入 一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐

21、车 的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信 号量同步m个旅客和n辆车的进程。（10分）解：visitors=m;cars=n;mutex=1;Pvi()Pci() repeat repeatwait(cars);wait(visitors);wait(mutex);wait(mutex);get on;start;travell;run;get off;stop;signal(cars);signal(visitors);wait(mutex);wait(mutex);until false;until false;17.读者与写者问题 （reader -

22、writer problems ）（ 10 分）在计算机体系中，对一个共享文件进行操作的进程可分为两类：读操作和写操作，它们分 别被称为读者和写者。访问该文件时读者和写者，写者和写者间必须实现互斥。只有在没 有读者访问文件时，写者才允许修改文件。或者写者在修改文件时不允许读者去读，否则 会造成读出的文件内容不正确。试写出算法描述读者和写者的问题。解：为了实现读者与写者的同步和互斥，我们设置一个信号量S，用于读者与写者之间或写 者与读者之间的互斥，初值为“1”用一个变量rc表示当前正在读的读者个数，当进程可 以去读或读结束后都要改变rc的值，因此rc又成为若干读进程的共享变量，它们必须互 斥地修

23、改rc。故必须定义另一个用于互斥的信号量Sr,初值也是“1”读者-写者问题可描述如下：S, Sr：semaphore； int rc = 0;process Reader I (i=1,2,.,m)S=Sr=1;process Writer j (j=1,2,.,k)beginP(S);Write file F; V(S);endbeginP(Sr); rc = rc+1; if (rc=1) P(S);V(Sr);read file F;P(Sr);rc = tc-1;if (rc=0) V(S);V(Sr);end 18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，1

24、2，76，假设每移动 一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并 计算为完成上述各次访问总共花费的寻道时间。（1）先来先服务算法；（2）最短寻道时间优先算法。（3）扫描算法（当前磁头移动的方向为磁道递增）（10分） 解：（1）磁道访问顺序为：20，44，40，4，80，12，76 寻道时间=（20+24+4+36+76+68+64）*3=292*3=876 （2）磁道访问顺序为：40，44，20，12，4，76，80 寻道时间=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道访问顺序为：40，44，76，80，20，12，4 寻道时间=

25、（0+4+32+4+60+8+8）*3=116*3=34819、生产者和消费者问题（10分）有一组生产者P1, P2,PM和一组消费者C1, C2,CK,他们通过由n个环形缓冲区构成的缓冲池进行通信，生产者把产品放入缓冲区，消费 者从缓冲区取产品来消费。请用wait和signal原语实现他们的同步操作。 解：生产者和消费者问题beginVar mutex,empty,full:semaphore:=1,n,0;buffer:arrayO,-m of item; in,out:integer := 0,0;parbeginproducer: beginrepeatproduce next pro

26、duct ; wait (empty);wait (mutex); buffer(in):=nextp ;in := (in+1) mod n ;signal (full);signal (mutex);until false ;endconsumer: beginrepeatwait (full);wait (mutex);nextc := buffer(out);out := (out+1) mod n;signal (empty);signal (mutex);consume the item in nextc;until false ;endparend end20、请用信号量描述哲学

27、家进餐问题。(15分) 解：哲学家进餐问题(15 分)public void philosopher (int i) while (true) think();wait (forki);wait (fork (i+1) % 5);eat();signal(fork (i+1) % 5);signal(forki);21. 今有三个并发进程R, M, P,它们共享了一个可循环使用的缓冲区B,缓冲区B共有 N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个 单元中；进程 M 负责处理读入的字符,若发现读入的字符中有空格符,则把它改成“,”； 进程P负责把处理后的字符取出

28、并打印输出。当缓冲区单元中的字符被进程P取出后，则 又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。 (10 分)解：(10 分)beginVar mutex,input,calculate,output:semaphore:=1,n,0,0;buffer:arrayO,-in of item;in,mid,out:integer := 0,0,0;proR() do wait (input);wait (mutex);buffer(in):=input data;in := (in+1) mod n ;signal (calculate);signal (m

29、utex);while true ; proM() do wait (calculate);wait (mutex);buffer(middle):=calculate data ;mid := (mid+1) mod n ;signal (output);signal (mutex); while true ;proP() do wait (output);wait (mutex);buffer(out):=calculate data ;out := (out+1) mod n ;signal (input);signal (mutex); while true ; 22. 理发店里有一位

30、理发师、一把理发椅子和五把供等候理发的顾客坐的椅子。如果没有顾 客，理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正 在理发时又有顾客来到，而如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就 离开。这里的问题是为理发师和顾客各编写一段程序来描述他们行为，并用wat和signal 原语操作实现其同步。(10分)解：理发师问题#define CHAIRS 5 typedef int semaphore; semphore customers=0; semaphore barbers=0 semaphore mutex=1;int waiting=0;void bar

31、ber (void) while(TRUE) wait(customers); wait(mutex);waiting=waiting-1; signal(barbers);signal(mutex); cut_hair();void customers (void) wait(mutex);if (waiting0 S的值表示可继续进入售票厅的人数S=0 表示售票厅中已有20名顾客(购票者)S0 |S|的值为等待进入售票厅的人数(2) int S=20;COBEGIN PROCESS PI(I=1, 2,)begin进入售票厅；wait(S) ；购票；signal(S);退出；end；COE

32、ND(3) S的最大值为20S 的最小值为 20n27. 设正在处理器上执行的一个进程的页表如下表所示,表中的虚页号和物理块号是十进制 数,起始页号(块号)均为0。所有的地址均是存储器字节地址。页的大小为1024字节。 (10 分) 详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。 下列虚地址对应于什么物理地址： 5499, 2221。进程的页表解：4逻辑地 址J44联想存储器P-7号*0r5499 的物理地址为：3792221 的物理地址为：3*1024+173=324528、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。进程read

33、负 责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓 冲器B1中取出一记录，加工后存入缓冲器B2。进程print将B2中的记录取出打印输 出。缓冲器B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出 来的与读入的记录的个数，次序完全一样。请用wait和signal原语写出它们的并发程 序。(10分)解：begin SR,SM1,SM2,SP:semaphore;B1,B2:record;SR:=1;SM1:=0;SM2:=1;SP:=0Cobeginprocess readX:record;begin R: (接收来自输入设备上一个记录)X:=接收

34、的一个记录；waiut(SR)；B1:=X;signal(SM1);goto R;end;Process moveY:record;BeginM:wait(SM1);Y:=B1;signal(SR)加工 Ywait(SM2)；B2:=Y;signal(SP);goto M;end;Process printZ:record;BeginP:wait(SP);Z:=B2;signal(SM2)打印Zgoto P;end;coend;end;29、考虑下述页面走向：12，3，42，1，56，2，12，3，76，3，21，2，36 当内存块数量分别为 3 时，试问 FIFO、LRU、OPT 答：所有内

35、存块最初都是空的，所以第一次用到的页面都产生一次缺页 3 时：FIFO 1， 23，4， 21， 5，6, 2,12，3，76，3， 21，2，3611 144 466633322262 221 1122277711133355 511166 63 3发生缺页中断的次数为16在FIF064、1、56之前调入的页面，分别为5、1、24,可见4 为最先进入内存的，本次应换出，然后把页 6LRU 1，23, 4，21，5，6，2，12，3，76，3，21，2，361 1 1 4455511 7 72 222 2 22 2 6 6 63333 333 31112 2发生缺页中断的次数为15在LRU65

36、、2、16之前调入的页面，分别为5、1、22为最近一段 时间内使用最少的，本次应换出，然后把页6调入内存。OPT 1， 23，4, 21, 5, 6, 2,12， 3， 76， 3， 21， 2， 361 1 11113 33 36222222722234566 6 611发生缺页中断的次数为11在OPT61、2、56后面要调入的页面，分别为2、1、2，可见5为最近一段时间内使用最少的，本次应换出，然后把页64、答：引入缓冲技术 的主要目的是：（123）使得一次输入的信息能多次使用。30若干个等待访问磁盘的进程依次要访问的磁道为27， 63， 57， 24， 107， 35， 106当前 磁头

37、的位置为57号磁道，根据下面的磁盘调度算法，请给出调度的顺序，并计算平均寻道 长度。（10 分）1. 先来先服务算法2. 最短寻道时间优先3. 扫描算法（当前磁头移动的方向为磁道递增）4. 循环扫描算法（当前磁头移动的方向为磁道递增）解：一系统中具有S类资源150个，在T0时刻按下表所示分配给3个进程：进程Maximum demandCurrent allocationP17025P26040P36045对下列请求应用银行家算法逐步分别分析判定是否安全, 如果是安全的，请给出一个可能的进程安全执行序列；如果不是安全的，请说明原因。（10分）1第4个进程P4到达，对资源S的最大需求为60个，当前请求分配25个；2.第4个进程P4到达，对资源S的最大需求50个，当前请求分配35个。31. 个采用请求式存储管理的计算机系统，其主存（实存）容量为256M字节，虚存容量（给用户的最大地址空间）为4G字节，页面大小为4K字节，试问：（10分）1. 主存物理地址应设为多少位？2. 主存中有多少物理块？3. 虚拟地址应该设多少位？4.虚拟地址空间最多可以有多少页？5. 页内最大和最小偏移量是多少？