《操作系统》2016年11月考试考前练习题

一、综合应用题

1. 设某页式内存管理系统允许用户编程空间为32个页面（每页1KB），主存为16KB，如有一用户程序有10页长，且某时刻该用户程序页表见下表，如果分别遇有逻辑地址0AC5H、1AC5H、3AC5H处的操作，试计算并说明内存管理系统将如何处理。

逻辑页号 0 1 2 3 物理块号 8 7 4 10 2. 面包师有很多面包，由n个销售人员推销，每个顾客进店后先取一个号，并且等待叫号，当一个销售人员空闲下来时，就叫下一个号，试设计一个使销售人员和顾客同步的算法。 3. 目录可以实现为只能以受限方式访问的特别文件，也可以实现为普通数据文件，两种方法各有什么优缺点？

4. 设某系统中既有就绪进程也有就绪/挂起进程，且至少有一个就绪/挂起进程的优先级比所有就绪进程都高，有两种极端的调度策略：（1）为减少交换，总是选择就绪进程运行；（2）总是选择最高优先级的进程运行，哪怕引起不必要的交换。请你给出一种既考虑优先级也考虑性能的折中策略。

5. 什么是多道程序设计技术？多道程序设计技术的特点是什么？ 6. 设某系统的状态如下表所示，使用银行家算法回答下面的问题：

（1）系统是否处于安全状态？如安全，请给出一个安全序列。

（2）如果从进程P1发来一个请求（0，4，2，0），这个请求能否立刻被满足？如可以，请给出一个安全序列。

A P0 P1 P2 P3 0 1 1 0 Allocation B 0 0 3 0 C 1 0 5 1 D 2 0 4 4 A 0 1 2 0 B 0 7 3 6 Max C 1 5 5 5 D 2 0 6 6 A 1 Available B 5 C 2 D 0 7. 将一组进程分为四类，如下图所示，各类进程之间采用优先级调度算法，而各类进程的内部采用时间片轮转算法，请简述P1、P2、P3、P4、P5、P6、P7、P8进程的调度过程。

优先级4（最高）P1P4P6P2P5P7P8P3优先级3优先级2优先级1（最低） 8. 系统中的I/O软件通常可分为四个层次：用户层、与设备无关的软件层、设备驱动程序和中断处理程序。请说明以下工作是在哪一层完成的：

（1）为磁盘读操作计算磁道、扇区和磁头； （2）向设备寄存器写命令；

（3）检查用户是否有权限使用设备；

（4）将二进制证书转换成ASCII码以便打印。

9. 某页式虚拟内存系统，用于页面交换的磁盘的平均访问及传输时间是20ms，页表保存在内存，访问时间为1μs，即每引用一次指令或数据，需要访问两次内存，为改善性能，可以增设一个关联寄存器，如果页表项在关联寄存器中，则只要访问一次内存就可以，假设80%的访问其页表项在关联寄存器中，剩下的20%中，10%的访问（即总数的2%）会产生缺页，请计算有效访问时间。

10. 在一个段式内存管理系统中，某段表见下面的表一，试求下面的表二中的逻辑地址所对应的物理地址。

表一 段号 0 1 2 3 4 内存起始地址 210 2350 100 1350 1938 段长 500 20 90 590 95 表二 段号 0 1 2 3 4 5 段内地址 430 10 500 400 112 32 11. 系统有同类资源m个，供n个进程共享，如果每个进程对资源的最大需求为k，试问：当m、n、k的值如下表所示时，是否会发生死锁？

序号 1 2 3 m 6 9 13 n 3 3 6 k 3 3 3 是否会死锁 说明 12. 忽略目录和文件描述符的开销，设某文件系统存储块的大小为16KB，针对以下文件大小，计算由于最后一个存储块的不完全利用所造成的文件存储空间浪费的百分比：41,600B、640,000B、4,064,000B。

1

附：参考答案

1. 设某页式内存管理系统允许用户编程空间为32个页面（每页1KB），主存为16KB，如有一用户程序有10页长，且某时刻该用户程序页表见下表，如果分别遇有逻辑地址0AC5H、1AC5H、3AC5H处的操作，试计算并说明内存管理系统将如何处理。

逻辑页号 0 1 2 3 物理块号 8 7 4 10 解答:

页面大小为1KB，所以低10位为页内偏移地址；用户编程空间为32个页面，即逻辑地址高5位为虚页号；主存为16kB，即物理地址高4位为物理块号。

…… 此处隐藏1468字 ……

资源情况 进程 P0 P2 P1 P3 A 1 1 2 3 Work B 5 5 8 8 C 2 3 8 8 D 0 2 6 6 A 0 1 0 0 Need B 0 0 7 6 C 0 0 5 4 D 0 2 0 2 A 0 1 1 0 Allocation B 0 3 0 0 C 1 5 0 1 D 2 4 0 4 Work＋Allocation A 1 2 3 3 B 5 8 8 8 C 3 8 8 9 D 2 6 6 10 True True True True Finish 因为存在一个安全序列，所以系统处于安全状态。

（2）

Requset1(0,4,2,0)假设先试着满足进程P1的这个请求，则Available变为（1,1,0,0） 系统状态变化见下表：

资源情况 进程 P0 P1 P2 P3 A 0 1 2 0 Max B 0 7 3 6 C 1 5 5 5 D 2 0 6 6 A 0 1 1 0 Allocation B 0 4 3 0 C 1 2 5 1 D 2 0 4 4 A 0 0 1 0 Need B 0 3 0 6 C 0 3 0 4 D 0 0 2 2 1 1 0 0 A Available B C D 再对系统进行安全性分析，见下表：

资源情况 进程 P0 P2 P1 P3 A 1 1 2 3 Work B 1 1 4 8 C 0 1 6 8 D 0 2 6 6 A 0 1 0 0 Need B 0 0 3 6 C 0 0 3 4 D 0 2 0 2 A 0 1 1 0 Allocation B 0 3 4 0 C 1 5 2 1 D 2 4 0 4 A 1 2 3 3 Work＋Allocation B 1 4 8 8 C 1 6 8 9 D 2 6 6 10 True True True True Finish 因为存在一个安全序列，所以系统仍处于安全状态。所以进程P1的这个请求应该马上被满足。

7. 将一组进程分为四类，如下图所示，各类进程之间采用优先级调度算法，而各类进程的内部采用时间片轮转算法，请简述P1、P2、P3、P4、P5、P6、P7、P8进程的调度过程。

4