《2014广西科技大学操作系统复习要点》由会员分享,可在线阅读,更多相关《2014广西科技大学操作系统复习要点(7页珍藏版)》请在金锄头文库上搜索。
1、2014年操作系统考核说明期末考试范围:教材第1-7章,其中4.4死锁不考。以各章习题为重点。考试形式:闭卷。题型:1. 名称解释(3个,每个5分 ,共15分)2. 简答题(5题,每题5分,共25分)3. 计算题(5题,共60分)复习要点一、 基本概念(20个)用户界面、系统调用、多道程序设计、进程、线程、原子性、临界区、工作集、互斥、同步、死锁、地址空间、虚拟内存、地址翻译或地址重定位、TLB、文件、目录、文件的逻辑结构、文件的物理结构、块设备、字符设备、设备的独立性、假脱机(spool),RAID二、 核心技术1. 进程状态转换2. 信号量的PV操作解决进程的互斥和同步问题3. 内存空间分
2、配技术4. 分页管理、分段管理和段页式管理中的地址翻译的方法5. 文件的物理实现三、 算法1. 进程调度,不同算法如:先来先服务、短任务优先、最短剩余时间优先、时间片轮转、优先级、多级队列等情况,系统平均周转时间和等待时间的计算2. 引入快表TLB后页式管理中的访存时间计算3. 页面置换算法:先进先出,最优置换、最近最少使用LRU4. 磁盘调度算法:先来先服务FCFS、最短寻道优先SSTF、电梯算法SCAN、提前查看电梯算法LOOK、单向电梯调度C-LOOK. 简答题重点题型1. 为什么要有操作系统?2. 多道程序是否总能提高CPU利用率?为什么?3. 进程的产生与消亡与人的出生与死亡有类似之
3、处,你能否予以阐述。4. 引发进程调度的原因有哪些?5. 从某种程度上人类社会中的一个家庭可以看作一个进程,而家庭成员则是线程。请根据对家庭的体验论述线程之间资源共享有可能存在的竞争。6. 页表存放在内存还是磁盘上,为什么?7. 分页存储管理存在的局限性是什么?8. 什么是“忙等待”,如何克服“忙等待”?9. 为什么要引入线程,解释一下线程与进程之间的相互关系。10. 简述各种不同的I/O控制方式。11. 假脱机技术是什么?14. 引入缓冲的目的是什么?15. 设备驱动程序的主要任务是什么?16. 简述I/O系统的层次结构。17. 简述“打开文件”所做的工作。综合题案例1.考虑下列进程集,进程
4、占用的CPU区间长度以毫秒来计算:进程 区间时间 优先级P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2假设在时刻0以进程P1,P2,P3,P4,P5的顺序到达。a.画出4个运行进度表分别演示用FCFS、SJF、非抢占优先级(数字小代表优先级高)和RR(时间片1)算法调度时进程的执行过程。b.在a里每个进程在每种调度算法下的周转时间是多少?c.在a里每个进程在每种调度算法下的等待时间是多少?d.在a里哪一种调度算法的平均等待时间对所有进程而言最小?答:a.进程运行进度表FCFS:P1P2P3P4P5 0 10 11 13 14 19SJF:P2P4P3P5P1 0 1 2 4 9
5、 19非抢占优先级:P2P5P1P3P4 0 1 6 16 18 19 RR: P1P2P3P4P5P1P3P5P1P5P1P5P1P5P1P1P1P1P10 19 b.周转时间FCFSRRSJF非抢占优先级P110191916P211211P3137418P4144219P5191496c.等待时间FCFSRRSJF非抢占优先级P10996P210100P3115216P4133118P514942d. SJF2.考虑一个运行十个I/O限制任务和一个CPU限制任务的系统。假设,I/O限制任务一次分配给一个I/O操作1毫秒的CPU计算,但每个I/O操作的完成需要 10毫秒。同时,假设间接的上下
6、文切换要0.1毫秒,所有的进程都是长进程。对一个RR调度来说,以下情况时CPU的利用率是多少: a.时间片是1毫秒 b.时间片是10毫秒答:a.时间片是1毫秒:不论是哪个进程被调度,这个调度都会为每一次的上下文切换花费一个0.1毫秒的上下文切换。CPU的利用率是1/1.1*100=92%。b.时间片是10毫秒:这I/O限制任务会在使用完1毫秒时间片后进行一次上下文切换。这个时间片要求在所有的进程间都走一遍,因此,10*1.1+10.1(因为每个I / O限定任务执行为1毫秒,然后承担上下文切换的任务,而CPU限制任务的执行10毫秒在承担一个上下文切换之前) 。因此,CPU的利用率是20/21.
7、1*100=94%。4. 考虑一个分页系统在内存中存储着一张页表。a.如果内存的查询需要200毫秒,那么一个分页内存的查询需要多长时间?b.如果我们加上相关联的寄存器,75%的页表查询可以在相关联的寄存器中找到,那么有效的查询时间是多少?(假设如果入口存在的话,在相关的寄存器中找到页表入口不花费时间)答:a.400毫秒:200毫秒进入页表,200毫秒进入内存中的字 b.有效进入时间=0.75*200毫秒+0.25*400毫秒=250毫秒5. 假设有一个请求调页存储器,页表放在寄存器中:处理一个页错误,当有空的帧或被置换的页没有被修改过时要用8ms,当被置换的页被修改过时用20ms,存储器访问时
8、间为100ns。 假设被置换的页中有70被修改过,有效访问时间不超过200ns时最大可接受的页错误率是多少?(提示:1ms=1000us 1us=1000ns)答:0.2 us = (1 P) 0.1 us + (0.3P) 8 ms + (0.7P) 20 ms0.1 = 0.1P + 2400 P + 14000 P0.1= 16,400 PP = 0.6. 假设一个请求调页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换是通过在主存中的页表来进行的,每次内存访问时间为1s。这样,每个通过页表进行的内存引用都要访问内存两次。为了提高性能,加入一个相关内存,当页表项在相关内存中时
9、,可以减少内存引用的访问次数。 假设80%的访问发生在相关内存中,而且剩下中的10%(总量的2%)会导致页错误。内存的有效访问时间是多少?答: 有效访问时间= (0.8) (1 sec)+ (0.18) (2 sec) + (0.02) (20000+2 sec)7. 某虚拟存储器的用户空间共有32个页面,每页1KB,主存16KB。试问:(1)逻辑地址的有效位是多少?(2)物理地址需要多少位?(3)假定某时刻系统用户的第0,1,2,3页分别分配的物理块号为5,10,4,7,试将虚地址0A5C和093C变换为物理地址。解 (1)程序空间的大小为32KB,因此逻辑地址的有效位数是15位。(2)内存
10、空间的大小是16KB,因此物理地址至少需要14位。(3)当页面为1KB时,虚地址0A5C表示页号为00010,页内地址是。该页在内存的第4块,即块号为0100,因此0A5C的物理地址是100,即125CH。(4)用同样的方法可以求得,093C的物理地址是113CH。8. 若在一分页存储管理系统中,某作业的页表如下所示。已知页面大小为1024字节,试将逻辑地址1011,2148,3000,5012转化为相应的物理地址(注:此处块号即为页面号)。页号块号01232316解 本题中,为了描述方便,设页号为P,页内位移为W,逻辑地址为A,内存地址为M,页面大小为L,则P=int(A/L)W=A mod
11、 L对于逻辑地址1011P=int(1011/1024)=0W=1011 mod 1024=1011A=1101=(0,1101)查页表第0页在第2块,所以物理地址为M=1024*2+1101= 3059。对于逻辑地址为2148P=2148/1024=2W=2148 mod 1024=100A=2148=(2,100)查页表第2页在第1块,所以物理地址为M=1024*1+100=1124。对于逻辑地址为3000P=3000/1024=2W=3000 mod 1024=952A=3000=(2,952)查页表第2页在第1块,所以物理地址为M=1024*1+952=1976对于逻辑地址5012P=
12、5012/1024=4W=5012 mod 1024=916因页号超过页表长度,该逻辑地址非法。9. 某段式存储管理系统中,有一作业的段表(SMT)如下表所示,求逻辑地址0,65,1,55,2,90,3,20对应的主存地址(按十进制)。(其中方括号中的第一个元素为段号,第二个元素为段内地址)段号段长(容量)主存起始地址状态01232005010015060085010001110解 逻辑地址0,65:对应的主存地址为60065665。逻辑地址1,55:因段内地址超过段长,所以产生段地址越界中断。逻辑地址2,90:对应的主存地址为1000901090。逻辑地址3,20:因为状态位为0,即该段在辅存中,所以产生缺段中断。10对页面访问串:1,2,3,4,1,2,5,1,2,3,4,5,指出在驻留集大为3时,使用FIFO、OPT和LRU替换算法的缺页次数。(OPT和LRU如果出现多选项时使用FIFO)答: FIFO: 缺页11次页面号123412512345111444442225222111113333332555544 OPT: 缺页7次页面号