操作系统解答题练习

操作系统解答题练习平均周转时间T=156.67min平均带权周转时间 W=3.68最高响应比优先调度算法：作业提交时运行时开始时完成时周转时间带权周转时刻刻刻刻/min间110:002:0010:0012:001201210:101:0012:2513:251953.25310:250:2512:0012:251204.8平均周转时间T=145min平均带权周转时间 W=3.02综上所述，最高响应比调度算法性能较好。如果限制为两道的多道程序系统中，有4个作业进入系统，其进入系统时刻、估计运行时间为下图所示。系统采用SJF作业调度算法，采用SRTF进程调度算法，请填充下面表格。作业进入系估计运行开始运行结束运行周转时间统时刻时间/min时刻时刻/min110:0030210:0520310:105410:2010平均周转时间T=平均带权周转时间 W=参考答案：作业进入系估计运行进入内开始运结束运周转时统时刻时间/min存时刻行时刻行时刻间/min110:003010:0010:0011:0565210:052010:0510:0510:2520310:10510:2510:2510:3020410:201010:3010:3010:4020平均周转时间T=31.25min平均带权周转时间 W=2.3有一个4道作业的操作系统，若在一段时间内先后到达6个作业，其提交时刻和估计运行时间为下表所示：作业提交时刻估计运行时间/min18:006028:203538:252048:302558:35568:4010系统采用剩余SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短的作业所抢占。1）分别给出6个作业的执行时间序列，即开始执行时间、作业完成时间、作业周转时间。2）计算平均作业周转时间。参考答案：提交时估计运进入剩余开始完成周转作业行时间内存时间时间时间时间刻/min时刻/min/min18:00608:00408:0010:3515528:20358:20308:209:559538:25208:25158:258:452048:30258:30259:009:255558:3558:4558:458:501568:40108:50108:509:0020平均周转时间T=60min有一个具有三道作业的多道批处理系统，作业调度采用短作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列中，作业优先数即为进程优先数，数越小则优先级越高。作业到达时刻估计运行时间/min优先数A10:00405B10:20303C10:30604D10:50206E11:00204F11:10104试填充下表：作业进入内存时刻运行结束时刻作业周转时间/minABCDEF平均作业周转时间 T=参考答案：作业进入内存开始运行运行结束时刻作业周转时时刻时刻间/minA10:0010:0012:40160B10:2010:2010:5030C10:3010:5011:5080D10:5012:4013:00130E12:0012:0012:2080F11:5011:5012:0050平均作业周转时间 T=88.3min1、（2分）生产者消费者的互斥同步问题叙述如下：生产者生产产品，放入有 n个缓冲区的缓冲池中，每个缓冲区只能放一个产品。消费者从缓冲池中取产品消费， 不允许从空缓冲区中取产品。有多个生产者进程与多个消费者进程并发进行，任何时刻只允许一个进程访问缓冲池。生产者进程和消费者进程分别从缓冲池中的同一位置开始，顺序循环地使用缓冲池，放产品或取产品。当缓冲池的n个缓冲区都满时，生产者进程必须在缓冲池外等待。当缓冲池的n个缓冲区都空时，消费者进程必须在缓冲池外等待。使用记录型信号量对生产者消费者问题的解答如下：设置整型量n，设定缓冲池（临界资源）中的缓冲区总数设置互斥信号量mutex，初值1，记录对缓冲池的互斥访问设置信号量empty，初值n，记录缓冲池中空缓冲区数设置信号量full，初值0，记录缓冲池中满缓冲区数生产者和消费者的并发程序如上面的流程图所示。请回答下面的问题（1）、（1分）如果将生产者进程中的两个 P操作语句（S2和S3）的执行次序反过来，可能会造成死锁。试分析其原因，发生死锁时缓冲池中的缓冲区有几个是满的？参考答案：n个（2）、（1分）如果将消费者进程中的两个P操作语句（X1和X2）的执行次序反过来，可能会造成死锁。试分析其原因，发生死锁时缓冲池中的缓冲区有几个是满的？参考答案：0个（或n个全是空的）2、（5分）设两个进程并发访问一个打印机分配表， A进程申请打印机，从打印机分配表读入状态字，进程 B向打印机分配表写入状态字。这两个进程对打印机分配表的操作是互斥的，用 P/V操作表示进程A和B的操作过程。参考答案：设互斥信号量S=1进程A：进程B：⋯⋯⋯⋯P(S);P(S);读入打印机分配表；修改打印机分配表；V（S）；V（S）；⋯⋯⋯⋯1、（8分）设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A资源的数量17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表所示。系统采用银行家算法来避免死锁。请回答下列问题：1）T0时刻是否为安全状态？若是，请给出安全序列。2）若进程P4请求资源（2，0，1），能否实现资源分配？为什么？3）在（2）的基础上，若进程P1请求资源（0，2，0），能否实现资源分配？参考答案：（1）T0时刻为安全状态。其中的一个安全序列为（ P4，P5，P3，P2，P1）（其他可能的安全序列有：（P4，P5，X，X，X），（P4，P2，X，X，X），（P4，P3，X，X，X），（P5，X，X，X，X））（2）可以为 P4分配资源，因为分配后的状态还是安全的，其安全序列的分析如下表：|Work|Need|Allocation|Work+Allocation|Finish|ABC|ABC|ABC|ABCP4|032|020|405|437|TrueP5|437|110|314|7411|TrueP1|7411|347|212|9513|TrueP2|9513|134|402|13515|TrueP3|13515|006|405|17520|True（3）进程P1再请求资源（0，2，0），则不能为之分配资源。2、（15分）考虑一个系统在某个时刻的状态如表所示。应用银行家算法回答下列问题：1）填写Need矩阵的内容2）系统是否处于安全状态？3）如果进程P1发出请求（0，4，2，0），这个请求能否被满足？参考答案：（1）根据银行家算法，可列出 Need矩阵如下表：进程|Need|Allocation|Max|Available|ABCD|ABCD|ABCD|ABCDP0|0000|0012|0012|1520P1|0750|1000|1750|P2|1002|1354|2356|P3|0020|0632|0652|P4|0646|0014|0656|（2）利用安全性算法，列出下表：进程|Work|Need|Allocation|Work+Allocation|Finish|ABCD|ABCD|ABCD|ABCD|P0|1520|0000|0012|1532|trueP1|1532|1002|1750|21282|trueP2|21282|0020|0632|218114|trueP3|218114|0646|0014|218128|trueP4|218128|0750|1000|318128|true存在安全序列（P0,P2,P3,P4,P1）系统处于安全状态。3）进程P1发出请求（0，4，2，0），可进行分配，结果得到如下表：进程|Need|Allocation|Max|Available|ABCD|ABCD|ABCD|ABCDP0|0000|0012|0012|1100P1|0330|1420|1750|P2|1002|1354|2356|P3|0020|0632|0652|P4|0646|0014|0656|用安全性算法检查，列出进程|Work|Need|Allocation|Work+Allocation|Finish|ABCD|ABCD|ABCD|ABCD|P0|1100|0000|0012|1112|trueP1|1102|1002|1750|2862|trueP2|2862|0020|0632|21494|trueP3|21494|0646|0014|214104|trueP4|214108|0330|1420|38128|true存在安全系列（P0,P2,P3,P4,P1），因此可满足需求，可分配所需要资源。1、（1分）给定段表如下：段号 | 段基地址 | 段长0 | 210 | 5001 | 2350 | 202 | 100 | 903 | 1350 | 5904 | 1938 | 95试求分段地址(3,500)所对应的物理地址？参考答案：18502、（1分）在分页式存储管理中，快表被用来提高访问内存中的数据的存取速度。假定查找快表需要10ns，访问内存一次需要100ns，如果采用二级页表结构，而快表的命中率是60%，问对于内存数据的平均存取时间是多少?参考答案：0.6*(10+100)+0.4*(10+300)=1904、（1分）设有一分页管理系统，管理总共 16个存储块，每个页面大小为1024，问物理地址至少应有多少位？参考答案：16个存储块的块号最多需要4位，每块有1024个存储单元，即所需的地址数需要10位，所以物理地址总长为14位。5、（1分）设有一分页管理系统，能够管理的逻辑地址空间最多可有16个页面，每个页面大小为 1024，问逻辑地址至少应有多少位？参考答案：页号占 4位，页面占10位，逻辑地址至少要有 14位。6、（1分）假定地址长度为 16位，页面大小为 1024。问二进制分页地址(100010,10001000)的二进制逻辑地址的表示参考答案：1000 10100010007、（1分）假定地址长度为 16位，页面大小为 1024。问二进制逻辑地址(0001000100010001)的二进制分页地址的表示参考答案：0100 01000100018、（1分）在一个段式存储管理系统中，其段表为：段号

内存起始地址

段长0

210

5001235020210090313505904193895试求表中逻辑地址（0,430）（2,120）对应的物理地址是什么？参考答案：逻辑地址（0，430）表示段号为2，即段首地址为210，对应的物理地址为：210+430=640逻辑地址（2，120）因为段内地址120>段长90，所为该段为非法段，越界。10、（5分）请求分页存储管理中，假定系统为某进程分配了

3个物理块，开始时3个物理块都为空，进程运行时的页面走向为：

7,0,1,0,3,0,7,0,1,4,6,3,6,0,1,3,6,1,3,。2如果使用先进先出置换算法，请问缺页率是多少？参考答案：75%11、（5分）在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面访问顺序为4，3，2，1，4，3，5，4，3，2，1，5，当分配给该作业的物理块数 M为4时，试写出页面访问的过程，并计算访问中所发生的缺页次数和缺页率？参考答案：产生缺页次数 8次，缺页率为8/12≈66.7%12、（20分）对于如下的页面访问序列：1，2，3，4，1，2，5，1，2，3，4，5当内存块数量分别为3和4时，试问：使用FIFO和LRU置换算法产生的缺页中断次数和缺页中断率分别是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）参考答案：FIFO淘汰算法：页面123412512345块1111444555块222211133块33332224缺缺缺缺缺缺缺缺缺内存块为3时，缺页中断（或称缺页次数、页面故障）为9缺页中断率为75%；页面123412512345块11111555544块2222211115块333332222块44444333缺缺缺缺缺缺缺缺缺缺内存块为4时，缺页中断为10，缺页中断率为83%。LRU淘汰算法：页面123412512345块11114445333块2222111144块333322225缺缺缺缺缺缺缺缺缺缺内存块