操作系统大题(共12页).docx

《操作系统大题(共12页).docx》由会员分享，可在线阅读，更多相关《操作系统大题(共12页).docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上四、计算题1. 这是一个从键盘输入到打印机输出的数据处理流图，其中键盘输入进程通过缓冲区 buf1 把输入数据传送给计算进程，计算进程把处理结果通过缓冲 buf2 传送给打印进程。buf1 和 buf2 为临界资源，试写出键盘输入进程，计算进程及打印进程间的同步算法。（10分） 输入进程 buf1 计算进程 buf2 打印进程解答：从键盘输入到打印机输出的数据传送过程，可以看作是由键盘输入进程到计算进程，以及由计算进程到打印输出进程这两个数据传送进程所组成。其中，对键盘输入进程而言，计算进程是消费者进程；而对打印输出进程而言，计算进程又是生产者进程。据此可将它们之间的

2、同步问题描述如下： var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0；IP:begin repeat P(empty); P(mutex1); input a charcter from keyboard;Add to buffer;V(mutex1);V(full);until false endCP:begin repeatP(full);P(mutex1);Take a charactor form buffer1;Add to ch1;V(mutex1);V(empty1);P(empty2);P(mutex2);Take

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

4、号均为0。1详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。2下列虚地址（十进制）对应与什么物理地址：5449，2221。解：（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)请你给出一和防止死锁的资源剥夺分配策略，完成上述请求序列，并列出资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。(10分)解：(10分) 分配策略为：当进程Pi申请ri类资源时，检

5、查ri中有无可分配的资源：有则分配给Pi；否则将Pi占有的资源全部释放而进入等待状态。(Pi等待原占有的所有资源和新申请的资源) 资源分配过程：剩余资源进程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 原语操作实现它们的同步。解：BEG

6、IN integer stop,run;Stop:=0;Run:=0;COBEGINDriver: BEGIN L1: wait(run);启动车辆；正常行车；到站停车； signal(stop); Goto L1;ENDConductor:BEGINL2：上乘客；关车门；signal(run);售票；wait(stop);开车门；下乘客；Goto L2;ENDCOENDEND5、某虚拟存储器的用户编程空间共321KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号152103447则逻辑地址0A5C（H）所对应的物理地址是什么？答：逻辑地址0

7、A5CH）所对应的二进制表示形式是：0000 1010 0101 1100 ，由于1K=210，下划线部分前的编码为，表示该逻辑地址对应的页号为3查页表，得到物理块号是4（十进制），即物理块地址为：0001 0010 0000 0000 ，拼接块内地址0000 0000 0101 1100，得0001 0010 0101 1100，即125C（H）。6、某段表内容如下：段号段首地址段长度0120K40K1760K30K2480K20K3370K20K 一逻辑地址为（2，154）的实际物理地址为多少？答：逻辑地址（2154）表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为48

8、0K+154。7、设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表1和表2所示。（共10分） 系统采用银行家算法实施死锁避免策略。 T0时刻是否为安全状态？若是，请给出安全序列。 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ 在的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？ 在的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？ 表1 T0时刻系统状态 最大资源需求量已分配资源数量ABCABCP1559212

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

10、P4115435P5033065 R1R2R3剩余资源数330解：（共9分，每小题3分）1 T0时刻是安全的，安全序列为：P1，P4，P5，P2，P32 P4请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P33 P3请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不能实施资源分配。 9一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：（共8分）块号存在位P访问位R修改位M0x1C1100x3F111-0000x5D100-0001 有那些页面不在内存？（2分）2 请分别计算进程中虚地

11、址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。 （6分）解：（共8分）不在内存的是第2和4页（按页号），或第3和5页（按序号）。 （2分）0x3B7的物理地址=0x 73 B7 （2分）0x12 A5的物理地址=0x 176 A5，缺页，换出第三页。 （2分）0x1432地址越界，出错。 （2分）10系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工作。输入进程和计算进程之间共用缓冲区buffer1,计算进程和打印进程之间共用缓冲区buffer2。输入进程接收外部数据放入buffer1中；计算进程从buffer1中取出数据进行计算，然后将

12、结果放入buffer2；打印进程从buffer2取出数据打印输出。用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。（共8分）解：（共8分）解答：输入进程、计算进程和打印进程之间的同步问题描述如下：var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0；InP:begin repeat wait(empty1); wait(mutex1); input a data from keyboard;Add to buffer1;signal(mutex1);signal(full1);until falseend

13、CalP:begin repeatwait(full1);wait(mutex1);Take a data form buffer1;Add to ch1;signal(mutex1);signal(empty1);calculate ch1;wait (empty2);wait(mutex2);Take a data form ch1;Add to buffer2;signal (mutex2);signal (full2); until falseendOutP:begin repeat wait(full2);wait(mutex2);Take a data from buffer2;A

14、dd to printer controler;signal(mutex2);signal(empty2);start printer; until falseend（评分标准：信号量设置2分，输入进程、计算进程、打印进程各2分）11在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配 3 个物理块 ，并且此进程的页面走向为 2，3，2，1，5，2，4，5，3，2，5，2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。（10分）解：FIFO： 2 3 2 1 5 2 4 5 3 2 5 2第1页 2 2 2 5 5 5 3 3 3第2页 3 3 3

15、 2 2 2 5 5第3页 1 1 1 4 4 4 2缺页中断次数 = 6LUR： 2 3 2 1 5 2 4 5 3 2 5 2第1页 2 2 2 2 5 5 5 3第2页 3 3 5 2 3 3 5第3页 1 1 4 4 2 2缺页中断次数 = 512. 进程 A1，A2，An 通过 K 个缓冲区向进程 B1，B2，Bm 不断地发送消息。发送和接收工作遵循如下规则：1 每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度一致；2 对每个消息，B1，B2，Bm 都需接收一次，读入各自的数据区内；3 K 个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。试用 wait 和

16、 signal 原语操作组织正确的发送和接收操作。（10分）解：BEGIN Integer Mutex, Availn, Fullm; Integer I;Mutex:=1;FOR i:=1 TO m DOBEGIN AvailI := k; FullI := 0;ENDPROCEDURE Send(K)Integer I;BEGIN13一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因（10分）页号块号加载时间访问时间访问位R修改位M206016101111

17、3016000022616210332016311 IFO算法 LRU算法 CLOCK算法 当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法解：1换出第3号虚页，因为它加载的时间最早；2换出第1号虚页，因为它最近最久没被访问；3换出第1号虚页，因为它最近既没被访问，又没被修改；4换出第3号虚页，因为它离访问点最远。14. 用整型信号量描述在哲学家进餐问题中，至多允许4个哲学家同时进餐的算法。（10分）解：public class diningphilosophers semaphore fork = new semaphore 5 (1);semaphore roo

18、m = new 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);15考虑一个有150个存储器单元

19、的系统，如下分配给三个进程：进程最大占有170452604036015使用银行家算法，以确定下面的任何一个请求是否安全：a第4个进程到达，最多需要60个存储单元，最初需要25个单元；b第4个进程到达，最多需要60个存储单元，最初需要35个单元；如果安全给出安全序列；若不安全给出结果分配简表。（10分）解：进程最大占有尚需可用170452525260402036015454602535安全序列为：1、2、3、4所以系统是安全的，可以进行分配。b进程最大占有尚需可用170452515260402036015454603525当前可用的资源不够任何一个进程运行完毕，所以不安全。16、（8分）在某采用

20、页式存储管理的系统中，所有作业执行时依次访问的页号是：1,2，3,4，3,1，5,4,6，2，1,2,5，7,3，2,4 假定开始时先把前4页装入内存。要求完成： （1）先进先出调度算法，作业执行过程中会产生_次缺页中断。依次淘汰的页号是_。 （2）最近最少使用算法时，作业执行过程中会产生_次缺页中断。依次淘汰的页号是_。 解：1）先进先出调度算法，作业执行过程中会产生_7_次缺页中断。依次淘汰的页号是_1、2、3、4、5、6、2。（4分） （2）最近最少使用算法时，作业执行过程中会产生_8_次缺页中断。依次淘汰的页号是2、3、1、5、4、6、1、5。17、（8分）假定某移动磁盘上，处理了访问

21、56号柱面的请求后，现在正在70号柱面上读信息，目前有下面的请求访问磁盘柱面的序列：73,68,100,120,60,108,8，50。请写出： （1）用最短查找时间优先算法，列出响应的次序。 （2）用电梯调度算法，列出响应的次序。 解：（1）用最短查找时间优先算法，响应的次序为68、73、60、50、8、100、108、120。 （2）用电梯调度算法，响应的次序为73、100、108、120、68、60、50、8。18.设某程序大小为460字，并且它有下面的存储访问序列：10，11，104，170，73，309，185，245，246，434，458，364设页面大小是100字，请给出该访问

22、序列的页面走向又设该程序基本可用内存是200字，采用先进先出置换算法(FIFO)，求出其缺页率如果采用最佳置换算法(OPT)，其缺页率又是多少?(注：缺页率=缺页次数/访问页面总数)解：(共10分)根据已知条件页面大小是100字，将页面访问序列简化为：0，0，1，1，0，3，1，2，2，4，4，3(2分)又因为该程序基本可用内存是200字，可知内存块数为2采用先进先出置换算法(FIFO)，总共有6次缺页，缺页率为6/12=50%，具体算法如下：(4分)页面走向0 0 1 1 0 3 1 2 2 4 4 3 块1 0 0 3 3 4 4块2 1 1 2 2 3 缺页缺 缺 缺 缺 缺 缺采用最佳

23、置换算法(OPT)，总共有5次缺页，缺页率为5/12=41.6%，具体算法如下：(4分)页面走向0 0 1 1 0 3 1 2 2 4 4 3块1 0 0 3 3 3块2 1 1 24缺页缺缺缺缺缺19、(10分)在一个批处理单道系统中，假设有四道作业，它们的提交时间及运行时间在下表中所列，当第一个作业进入系统后开始调度，假定作业都是仅作计算，采用计算时间短的作业优先调度算法，忽略调度花费时间。 作业 进入系统时间 运行时间 开始时间 完成时间 周转时间 1 8：00 2小时 2 8：50 30分钟 3 9：00 6分钟 4 9：30 12分钟 （1） 求出每个作业开始时间、完成时间及周转时间

24、并填入表中。 （2）计算四个作业的平均周转时间应为_. 解：（1）每空0.5分，6分。 作业 进入系统时间 运行时间 开始时间 完成时间 周转时间 1 8：00 2小时 8:00 10:00 120分钟 2 8：50 30分钟 10:18 10:48 118分钟 3 9：00 6分钟 10:00 10:06 66分钟 4 9：30 12分钟 10:06 10:18 48分钟 （2）四个作业的平均周转时间应为88分钟.（20(4分)一个由3个页面(页号为0、1、2)，每页有2048个字节组成的程序，假定在某时刻调入8个物理块的内存，其页面的页号和物理块号的对照表如下：逻辑页号 主存块号0 41

25、72 1请根据页表，计算下列给出的逻辑地址对应的绝对地址。(1)100 (2)2617 (3)5196答：（4分）首先根据逻辑地址查页表，得到主存的块号，再根据公式绝对地址=块号块长+页内地址进行计算。（1）100的页号为0（100/2048=2），页内地址为100mod2048=100；查表得主存块号为4，于是绝对地址=42048+100=8292；（2）2617的页号为1（2617/2048=1），页内地址为2617mod2048=569；查表得主存块号为7，于是绝对地址=72048+569=14905；（3）5196的页号为2（5196/2048=2），页内地址为5196mod2048=1100；查表得主存块号为1，于是绝对地址=12048+1100=3148；（注：mod为取模运算，即求余数）专心-专注-专业