《操作系统》人大网校考前练习题.doc

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

一、综合应用题
1. 设某页式存管理系统允许用户编程空间为32个页面（每页1KB），主存为16KB，如有一用户程序有10页长，且某时刻该用户程序页表见下表，如果分别遇有逻辑地址0AC5H、1AC5H、3AC5H处的操作，试计算并说明存管理系统将如何处理。
2. 面包师有很多面包，由n个销售人员推销，每个顾客进店后先取一个号，并且等待叫号，当一个销售人员空闲下来时，就叫下一个号，试设计一个使销售人员和顾客同步的算法。
3. 目录可以实现为只能以受限方式访问的特别文件，也可以实现为普通数据文件，两种方法各有什么优缺点？
4. 设某系统中既有就绪进程也有就绪/挂起进程，且至少有一个就绪/挂起进程的优先级比所有就绪进程都高，有两种极端的调度策略：（1）为减少交换，总是选择就绪进程运行；（2）总是选择最高优先级的进程运行，哪怕引起不必要的交换。请你给出一种既考虑优先级也考虑性能的折中策略。
5. 什么是多道程序设计技术？多道程序设计技术的特点是什么？
6. 设某系统的状态如下表所示，使用银行家算法回答下面的问题：
（1）系统是否处于安全状态？如安全，请给出一个安全序列。
（2）如果从进程P1发来一个请求（0，4，2，0），这个请求能否立刻被满足？如可以，请给出一个安全序列。
7. 将一组进程分为四类，如下图所示，各类进程之间采用优先级调度算法，而各类进程的部采用时间片轮转算法，请简述P1、P2、P3、P4、P5、P6、P7、P8进程的调度过程。

8. 系统中的I/O软件通常可分为四个层次：用户层、与设备无关的软件层、设备驱动程序和中断处理程序。请说明以下工作是在哪一层完成的：
（1）为磁盘读操作计算磁道、扇区和磁头；
（2）向设备寄存器写命令；
（3）检查用户是否有权限使用设备；
（4）将二进制证书转换成ASCII码以便打印。
9. 某页式虚拟存系统，用于页面交换的磁盘的平均访问及传输时间是20ms，页表保存在存，访问时间为1μs，即每引用一次指令或数据，需要访问两次存，为改善性能，可以增设一个关联寄存器，如果页表项在关联寄存器中，则只要访问一次存就可以，假设80%的访问其页表项在关联寄存器中，剩下的20%中，10%的访问（即总数的2%）会产生缺页，请计算有效访问时间。
10. 在一个段式存管理系统中，某段表见下面的表一，试求下面的表二中的逻辑地址所对应的物理地址。
11. 系统有同类资源m个，供n个进程共享，如果每个进程对资源的最大需求为k，试问：当m、n、k的值如下表所示时，是否会发生死锁？
12. 忽略目录和文件描述符的开销，设某文件系统存储块的大小为16KB，针对以下文件大小，计算由于最后一个存储块的不完全利用所造成的文件存储空间浪费的百分比：41,600B、640000B、4,064,000B。

附：参考答案

1. 设某页式存管理系统允许用户编程空间为32个页面（每页1KB），主存为16KB，如有一用户程序有10页长，且某时刻该用户程序页表见下表，如果分别遇有逻辑地址0AC5H、1AC5H、3AC5H处的操作，试计算并说明存管理系统将如何处理。
解答:
页面大小为1KB，所以低10位为页偏移地址；用户编程空间为32个页面，即逻辑地址高5位为虚页号；主存为16kB，即物理地址高4位为物理块号。
逻辑地址0AC5H转换为二进制为000 1010 1100 0101B，虚页号为2(00010B)，映射至物理块号4，故系统访问物理地址12C5H(01 0010 1100 0101B)。
逻辑地址1AC5H转换为二进制为001 1010 1100 0101B，虚页号为6(00110B)，不在页面映射表中，会产生缺页中断，系统进行缺页中断处理。
逻辑地址3AC5H转换为二进制为011 1010 1100 0101B，页号为14，而该用户程序只有10页，故系统产生越界中断。
注意：题中在对十六进制地址转换为二进制时，我们可能会习惯性地写为16位，这是容易犯错的细节。如题中逻辑地址是15位，物理地址为14位。逻辑地址0AC5H的二进制表示为000 1010 1100 0101B，对应物理地址12C5H的二进制表示为01 0010 1100 0101B。这一点应该注意。
2. 面包师有很多面包，由n个销售人员推销，每个顾客进店后先取一个号，并且等待叫号，当一个销售人员空闲下来时，就叫下一个号，试设计一个使销售人员和顾客同步的算法。
解答:
顾客进店后按序取号，并等待叫号；销售人员空闲之后也是按序叫号，并销售面包。因此同步算法只要对顾客取号和销售人员叫号进行合理同步即可。我们使用两个变量i和j分别记录当前的取号值和叫号值，并各自使用一个互斥信号量用于对i和j进行访问和修改。
int i=0,j=0;
semaphore mutex_i=1,mutex_j=1;
Consumer(){ //顾客
进入面包店;
p(mutex_i); //互斥访问i
取号i;
i++;
V(mutex_i); //释放对i的访问
等待叫号i并购买面包;
}
Seller(){ //销售人员
while(1){
p(mutex_j); //互斥访问j
if(j取走并等待
叫号j;
j++;
V(mutex_j); //释放对j的访问
销售面包；
}
else{ //暂时没有顾客在等待
V(mutex_j); //释放对j的访问
休息片刻;
}
}
}
3. 目录可以实现为只能以受限方式访问的特别文件，也可以实现为普通数据文件，两种方法各有什么优缺点？
解答:
实现为特别文件，便于操作系统对目录的识别，使得安全性更容易实施。
实现为普通文件，便于操作系统以统一的方式对系统中的对象进行管理，以便更易于创建和管理属于用户的目录。
4. 设某系统中既有就绪进程也有就绪/挂起进程，且至少有一个就绪/挂起进程的优先级比所有就绪进程都高，有两种极端的调度策略：（1）为减少交换，总是选择就绪进程运行；（2）总是选择最高优先级的进程运行，哪怕引起不必要的交换。请你给出一种既考虑优先级也考虑性能的折中策略。
解答:
以降低N个优先级（如N=2或3）的方式看待就绪/挂起进程，只有当就绪/挂起进程的优先级比最高优先级的就绪进程高出N个优先级时，才选择就绪/挂起的进程。
5. 什么是多道程序设计技术？多道程序设计技术的特点是什么？
解答:
多道程序设计是指同时把多个作业（程序）放入存，使它们交替执行共享处理器时间、外设及系统中的其他资源；当一道程序因某种原因（如I/O请求）而暂停执行时，CPU立即转去执行另一道程序。多道程序设计技术减少了CPU等待时间，增加了系统吞吐量，提高了系统的效率。
多道程序设计技术的主要特点：多道、宏观上并行、微观上串行。多道是指计算机存中同时存放多道相互独立的程序。宏观上并行是指同时进入系统中的多道程序都处于运行状态。微观上串行是指在单处理器环境中，存中的多道程序轮流占用CPU，交替执行。
6. 设某系统的状态如下表所示，使用银行家算法回答下面的问题：
（1）系统是否处于安全状态？如安全，请给出一个安全序列。
（2）如果从进程P1发来一个请求（0，42，0），这个请求能否立刻被满足？如可以，请给出一个安全序列。
解答:
（1）Work矢量初始化值=Available(1,5,2,0)
系统安全性分析：
因为存在一个安全序列，所以系统处于安全状态。
（2）
Requset1(0,4,2,0)，所以系统仍处于安全状态。所以进程P1的这个请求应该马上被满足。
7. 将一组进程分为四类，如下图所示，各类进程之间采用优先级调度算法，而各类进程的部采用时间片轮转算法，请简述P1、P2、P3、P4、P5、P6、P7、P8进程的调度过程。

解答:从题意可知，各类进程之间采用优先级调度算法，而同类进程部采用时间片轮转调度算法，因此，系统首先对优先级为4的进程P1、P2、P3采用时间片轮转调度算法运行；当P1、P2、P3均运行结束或没有可运行的进程（即P1、P2、P3都处于等待状态；或其中部分进程已运行结束，其余进程处于等待状态）时，则对优先级为3的进程P4、P5采用时间片轮转调度算法运行。在此期间，如果未结束的P1、P2、P3有一个转为就绪状态，则当前时间片用完后又回到优先级4进行调度。类似地，当P1～P5均运行结束或没有可运行进程（即P1～P5都处于等待状态；或其中部分进程已运行结束，其余进程处于等待状态）时，则对优先级为2的进程P6、P7、P8采用时间片轮转调度算法运行，一旦P1～P5中有一个转为就绪状态，则当前时间片用完后立即回到相应的优先级进行时间片轮转调度。
8. 系统中的I/O软件通常可分为四个层次：用户层、与设备无关的软件层、设备驱动程序和中断处理程序。请说明以下工作是在哪一层完成的：
（1）为磁盘读操作计算磁道、扇区和磁头；
（2）向设备寄存器写命令；
（3）检查用户是否有权限使用设备；
（4）将二进制证书转换成ASCII码以便打印。
解答:
首先，我们来看这些功能是不是应该由操作系统来完成。操作系统是一个代码相对稳定的软件，它很少发生代码的变化。如果1）由操作系统完成，那么操作系统就必须记录逻辑块和磁盘细节的映射，操作系统的代码会急剧膨胀，而且对新型介质的支持也会引起代码的变动。如果2）也由操作系统完成，那么操作系统需要记录不同生产厂商的不同数据，而且后续新厂商和新产品也无法得到支持。因为1）和2）都与具体的磁盘类型有关，因此为了能够让操作系统尽可能多的支持各种不同型号的设备，1）和2）应该由厂商所编写的设备驱动程序完成。3）涉及到安全与权限问题，应由与设备无关的操作系统完成。4）应该由用户层来完成，因为只有用户知道将二进制整数转换为ASCII码的格式（使用二进制还是十进制，有没有特别的分隔符等）。
9. 某页式虚拟存系统，用于页面交换的磁盘的平均访问及传输时间是20ms，页表保存在存，访问时间为1μs，即每引用一次指令或数据，需要访问两次存，为改善性能，可以增设一个关联寄存器，如果页表项在关联寄存器中，则只要访问一次存就可以，假设80%的访问其页表项在关联寄存器中，剩下的20%中，10%的访问（即总数的2%）会产生缺页，请计算有效访问时间。
解答:
有效访问时间为80%×1+（1－80%）×（（1－10%）×1×2）+2%×（1×320×1000）=401.22（μs）
10. 在一个段式存管理系统中，某段表见下面的表一，试求下面的表二中的逻辑地址所对应的物理地址。
解答:
1）由段表知，第0段存始址为210，段长为500，故逻辑地址(0,430)是合法地址，对应的物理地址为210+430=640。
2）由段表知，第1段存始址为2350，段长为20，故逻辑地址(1,10)是合法地址，对应的物理地址为2350+10=2360。
3）由段表知，第2段存始址为100，段长为90，故逻辑地址(2,500)的段位移500已经超过了段长，故为非法地址。
4）由段表知，第3段存始址为1350，段长为590，故逻辑地址(3400)是合法地址，对应的物理地址为1350+400=1750。
5）由段表知，第4段存始址为1938，段长为95，故逻辑地址(4,112)的段位移112已经超过了段长，故为非法地址。
6）由段表知，不存在第5段，故逻辑地址(5,32)为非法地址。
11. 系统有同类资源m个，供n个进程共享，如果每个进程对资源的最大需求为k，试问：当m、n、k的值如下表所示时，是否会发生死锁？
解答:
不发生死锁要求必须保证至少有一个进程可以得到所需的全部资源并执行完毕，当m>=n(k－1)＋1则一定不会发生死锁。
12. 忽略目录和文件描述符的开销，设某文件系统存储块的大小为16KB，针对以下文件大小，计算由于最后一个存储块的不完全利用所造成的文件存储空间浪费的百分比：41,600B、640,000B、4,064,000B。
解答:

11 / 12