操作系统历年真题讲义

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Page,*,Operating System,*,Page,1,2024/9/28,操作系统,刘 刚,samuel2005,Page,2,2024/9/28,2009,年真题,2010,年大纲,2010,年大纲解析,考点分析,2009,年真题解析,2010,年大纲例题解析,操作系统,Page,3,2024/9/28,1.,为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出 的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是,A.,栈,B.,队列,C.,树,D.,图,2009,年真题一瞥,Page,4,2024/9/28,21.,假设某计算机的存储系统由,Cache,和主存组成，某程序执行过程中访存,1000,次，其中访问,Cache,缺失（未命中）,50,次，则,Cache,的命中率是,A,5% B.9.5% C.50% D.95%,22.,下列选项中，能引起外部中断的事件是,A,键盘输入,B.,除数为,0,C.,浮点运算下溢,D.,访存缺页,2009,年真题一瞥,Page,5,2024/9/28,23.,单处理机系统中，可并行的是,I,进程与进程,II,处理机与设备,III,处理机与通道,IV,设备与设备,A,I,、,II,和,III B. I,、,II,和,IV,C. I,、,III,和,IV D. II,、,III,和,IV,24.,下列进程调度算法中，综合考虑进程等待时间和执行时间的是,A,时间片轮转调度算法,B.,短进程优先调度算法,C.,先来先服务调度算法,D.,高响应比优先调度算法,2009,年真题一瞥,Page,6,2024/9/28,25.,某计算机系统中有,8,台打印机，有,K,个进程竞争使用，每个进程最多需要,3,台打印机。该系统可 能会发生死锁的,K,的最小值是,A. 2 B. 3 C. 4 D. 5,26,分区分配内存管理方式的主要保护措施是,A,界地址保护,B.,程序代码保护,C.,数据保护,D.,栈保护,2009,年真题一瞥,Page,7,2024/9/28,27.,一个分段存储管理系统中，地址长度为,32,位，其中段号占,8,位，则最大段长是,A,2,8,字节,B.2,16,字节,C. 2,21,字节,D.2,32,字节,28.,下列文件物理结构中，适合随机访问且易于文件扩展的是,A,连续结构,B.,索引结构,C.,链式结构且磁盘块定长,D.,链式结构且磁盘块变长,2009,年真题一瞥,Page,8,2024/9/28,29.,假设磁头当前位于第,105,道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为,35,，,45,，,12,，,68,，,110,，,180,，,170,，,195,，采用,SCAN,调度（电梯调度）算法得到的磁道访问序列是,A,110,，,170,，,180,，,195,，,68,，,45,，,35,，,12,B. 110,，,68,，,45,，,35,，,12,，,170,，,180,，,195,C. 110,，,170,，,180,，,195,，,12,，,35,，,45,，,68,D. 12,，,35,，,45,，,68,，,110,，,170,，,180,，,195,2009,年真题一瞥,Page,9,2024/9/28,30.,文件系统中，文件访问控制信息存储的合理位置是,A,文件控制块,B.,文件分配表,C.,用户口令表,D.,系统注册表,31,设文件,F1,的当前引用计数值为,1,，先建立,F1,的符号链接（软链接）文件,F2,，再建立,F1,的硬链接 文件,F3,，然后删除,F1,。此时，,F2,和,F3,的引用计数值分别是,A,0,、,1 B. 1,、,1 C. 1,、,2 D. 2,、,1,2009,年真题一瞥,Page,10,2024/9/28,32,程序员利用系统调用打开,I/O,设备时，通常使用的设备标识是,A,逻辑设备名,B.,物理设备名,C.,主设备号,D.,从设备号,2009,年真题一瞥,Page,11,2024/9/28,45.,（,7,分）三个进程,P1,、,P2,、,P3,互斥使用一个包含,N,（,N0,）个单元的缓冲区。,P1,每次用,produce,（）生成一个正整数并用,put,（）送入缓冲区某一空单元中；,P2,每次用,getodd,（）从该缓冲区中取 出一个奇数并用,countodd,（）统计奇数个数；,P3,每次用,geteven,（）从该缓冲区中取出一个偶数并 用,counteven,（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定 义的信号量的含义。要求用伪代码描述。,2009,年真题一瞥,Page,12,2024/9/28,2009,年真题一瞥,页号,页框（,Page Frame,）号,有效位（存在位）,0,101H,1,1,0,2,254H,1,46.,（,8,分）请求分页管理系统中，假设某进程的页表内容如下表所示。,Page,13,2024/9/28,页面大小为,4KB,，一次内存的访问时间是,100ns,，一次快表（,TLB,）的访问时间是,10ns,，处理一次 缺页的平均时间为,10,8,ns,（已含更新,TLB,和页表的时间），进程的驻留集大小固定为,2,，采用最近最 少使用置换算法（,LRU,）和局部淘汰策略。假设,TLB,初始为空；,地址转换时先访问,TLB,，若,TLB,未命中，再访问页表（忽略访问页表之后的,TLB,更新时间）；,有效位为,0,表示页面不在内存，产 生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。,设有虚地址访问序列,2362H,、,1565H,、,25A5H,，请问：,（,1,） 依次访问上述三个虚地址，各需多少时间？给出计算过程。,（,2,） 基于上述访问序列，虚地址,1565H,的物理地址是多少？请说明理由。,2009,年真题一瞥,Page,14,2024/9/28,（,1,）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大 小为,4KB,，即,2,12,，则得到页内位移占虚地址的低,12,位，页号占剩余高位。可得三个虚地址的页号,P :,十六进制的一位数字转换成,4,位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号,2362H,：,P=2,，访问快表,10ns,，因初始为空，访问页表,100ns,得到页框号，合成物理地址后访问主 存,100ns,，共计,10ns+100ns+100ns=210ns,。,2009,年真题一瞥,Page,15,2024/9/28,页面大小为,4KB,，一次内存的访问时间是,100ns,，一次快表（,TLB,）的访问时间是,10ns,，处理一次 缺页的平均时间为,10,8,ns,（已含更新,TLB,和页表的时间），进程的驻留集大小固定为,2,，采用最近最 少使用置换算法（,LRU,）和局部淘汰策略。假设,TLB,初始为空；,地址转换时先访问,TLB,，若,TLB,未命中，再访问页表（忽略访问页表之后的,TLB,更新时间）；,有效位为,0,表示页面不在内存，产 生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。,设有虚地址访问序列,2362H,、,1565H,、,25A5H,，请问：,（,1,） 依次访问上述三个虚地址，各需多少时间？给出计算过程。,2009,年真题一瞥,Page,16,2024/9/28,2009,年真题一瞥,页号,页框（,Page Frame,）号,有效位（存在位）,0,101H,1,1,0,2,254H,1,1565H,：,P=1,访问快表,10ns,，落空，,访问页表,100ns,，落空，,进行缺页中断处理,10,8,ns,，,合成物理地 址后访问主存,100ns,，共计,10ns+100ns+10,8,ns+100ns10,8,ns,Page,17,2024/9/28,页面大小为,4KB,，一次内存的访问时间是,100ns,，一次快表（,TLB,）的访问时间是,10ns,，处理一次 缺页的平均时间为,10,8,ns,（已含更新,TLB,和页表的时间），进程的驻留集大小固定为,2,，采用最近最 少使用置换算法（,LRU,）和局部淘汰策略。假设,TLB,初始为空；,地址转换时先访问,TLB,，若,TLB,未命中，再访问页表（忽略访问页表之后的,TLB,更新时间）；,有效位为,0,表示页面不在内存，产 生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。,设有虚地址访问序列,2362H,、,1565H,、,25A5H,，请问：,（,1,） 依次访问上述三个虚地址，各需多少时间？给出计算过程。,2009,年真题一瞥,Page,18,2024/9/28,25A5H,：,P=2,，,访问快表，,因第一次访问已将该页号放入快表，,因此花费,10ns,便可合成物理地址，,访问主存,100ns,，共计,10ns+100ns=110ns,。,2009,年真题一瞥,Page,19,2024/9/28,页面大小为,4KB,，一次内存的访问时间是,100ns,，一次快表（,TLB,）的访问时间是,10ns,，处理一次 缺页的平均时间为,10,8,ns,（已含更新,TLB,和页表的时间），进程的驻留集大小固定为,2,，采用最近最 少使用置换算法（,LRU,）和局部淘汰策略。假设,TLB,初始为空；,地址转换时先访问,TLB,，若,TLB,未命中，再访问页表（忽略访问页表之后的,TLB,更新时间）；,有效位为,0,表示页面不在内存，产 生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。,设有虚地址访问序列,2362H,、,1565H,、,25A5H,，请问：,（,2,） 基于上述访问序列，虚地址,1565H,的物理地址是多少？请说明理由。,2009,年真题一瞥,Page,20,2024/9/28,2009,年真题一瞥,页号,页框（,Page Frame,）号,有效位（存在位）,0,101H,1,1,0,2,254H,1,（,2,）当访问虚地址,1565H,时，产生缺页中断，,合法驻留集为,2,，必须从页表中淘汰一个页面,根据题目的置换算法，应淘汰,0,号页面，因此,1565H,的对应页框号为,101H,。,由此可得,1565H,的物理地址 为,101565H,。,Page,21,2024/9/28,2009,年真题,2010,年大纲,2010,年大纲解析,考点分析,2009,年真题解析,2010,年大纲例题解析,操作系统,Page,22,2024/9/28,考查目标：,计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。,要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。,2010,年新大纲,Page,23,2024/9/28,考试形式和试卷结构,一、 试卷满分及考试时间,本试卷满分为,150,分，考试时间为,180,分钟,二、 答题方式,答题方式为闭卷、笔试,2010,年新大纲,Page,24,2024/9/28,考试形式和试卷结构,三、 试卷内容结构,数据结构,45,分,计算机组成原理,45,分,操作系统,35,分,计算机网络,25,分,四、 试卷题型结构,单项选择题,80,分,(40,小题，每小题,2,分,),综合应用题,70,分,2010,年新大纲,Page,25,2024/9/28,考查范围与考查目标,1.,了解操作系统在计算机系统中的作用、地位、发展和特点。,2.,理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。,3.,能够运用所学的操作系统原理、方法与技术分析问题和解决问题。,2010,年新大纲,Page,26,2024/9/28,考查范围与考查目标,一、 操作系统概述,(,一,),操作系统的概念、特征、功能和提供的服务,(,二,),操作系统的发展与分类,(,三,),操作系统的运行环境,2010,年新大纲,Page,27,2024/9/28,考查范围与考查目标,二、 进程管理,(,一,),进程与线程,1.,进程概念,2.,进程的状态与转换,3.,进程控制,4.,进程组织,5.,进程通信,共享存储系统,;,消息传递系统,;,管道通信。,6.,线程概念与多线程模型,2010,年新大纲,Page,28,2024/9/28,考查范围与考查目标,二、 进程管理,(,二,),处理机调度,1.,调度的基本概念,2.,调度时机、切换与过程,3.,调度的基本准则,4.,调度方式,5.,典型调度算法,先来先服务调度算法,;,短作业,(,短进程、短线程,),优先调度算法,;,时间片轮转调度算法,;,优先级调度算法,;,高响应比优先调度算法,;,多级反馈队列调度算法。,2010,年新大纲,Page,29,2024/9/28,考查范围与考查目标,二、 进程管理,(,三,),进程同步,1.,进程同步的基本概念,2.,实现临界区互斥的基本方法,软件实现方法,;,硬件实现方法。,3.,信号量,4.,管程,5.,经典同步问题,生产者,-,消费者问题,;,读者,-,写者问题,;,哲学家进餐问题。,2010,年新大纲,Page,30,2024/9/28,考查范围与考查目标,二、 进程管理,(,四,),死锁,1.,死锁的概念,2.,死锁处理策略,3.,死锁预防,4.,死锁避免,系统安全状态：银行家算法。,5.,死锁检测和解除,2010,年新大纲,Page,31,2024/9/28,考查范围与考查目标,三、 内存管理,(,一,),内存管理基础,1.,内存管理概念,程序装入与链接,;,逻辑地址与物理地址空间,;,内存保护,2.,交换与覆盖,3.,连续分配管理方式,4.,非连续分配管理方式,分页管理方式,;,分段管理方式,;,段页式管理方式。,2010,年新大纲,Page,32,2024/9/28,考查范围与考查目标,三、 内存管理,(,二,),虚拟内存管理,1.,虚拟内存基本概念,2.,请求分页管理方式,3.,页面置换算法,最佳置换算法,(OPT);,先进先出置换算法,(FIFO);,最近最少使用置换算法,(LRU);,时钟置换算法,(CLOCK),。,4.,页面分配策略,5.,抖动,抖动现象,;,工作集。,6.,请求分段管理方式,7.,请求段页式管理方式,2010,年新大纲,Page,33,2024/9/28,考查范围与考查目标,四、 文件管理,(,一,),文件系统基础,1.,文件概念,2.,文件结构,顺序文件,;,索引文件,;,索引顺序文件。,3.,目录结构,文件控制块和索引节点,;,单级目录结构和两级目录结构,;,树形目录结构,;,图形目录结构。,4.,文件共享,5.,文件保护,访问类型,;,访问控制。,2010,年新大纲,Page,34,2024/9/28,考查范围与考查目标,四、 文件管理,(,二,),文件系统实现,1.,文件系统层次结构,2.,目录实现,3.,文件实现,(,三,),磁盘组织与管理,1.,磁盘的结构,2.,磁盘调度算法,3.,磁盘的管理,2010,年新大纲,Page,35,2024/9/28,考查范围与考查目标,五、 输入输出,(I/O),管理,(,一,) I/O,管理概述,1. I/O,设备,2. I/O,管理目标,3. I/O,管理功能,4. I/O,应用接口,5. I/O,控制方式,2010,年新大纲,Page,36,2024/9/28,考查范围与考查目标,五、 输入输出,(I/O),管理,(,二,) I/O,核心子系统,1. I/O,调度概念,2.,高速缓存与缓冲区,3.,设备分配与回收,4.,假脱机技术,(SPOOLing),5.,出错处理,2010,年新大纲,Page,37,2024/9/28,试题示例,一、单项选择题：,1,40,小题，每小题,2,分，共,80,分。在每小题给出的四个选项中，请选出一项最符合题目要求的。,5,下列进程状态转换中，不可能发生的转换是,A,运行一就绪,B,运行一等待,C,等待一运行,D,等待一就绪,6,设某系统中有,3,个并发进程都需要,4,个同类资源，该系统不会发生死锁的最少资源数是,A,9 B,10 C,1 D. 12,2010,年新大纲,Page,38,2024/9/28,试题示例,二、综合应用题：,41,47,小题，共,70,分。,45,(6,分,),设页引用序列：,(1,，,2,，,3,，,4,，,2,，,1,，,5,，,6,，,2,，,1,，,2,，,3,，,7,，,6,，,3,，,2,，,1,，,2,，,3,，,6),，物理块,(Page frame),数为,3,，且所有的块初始时为空。当分别采用最近最少使用置换,(LRU),、先进先出置换,(FIFO),和最佳置换,(OPT),的页面置换算法时，各会发生多少次缺页,?,要求给出求解过程。,2010,年新大纲,Page,39,2024/9/28,试题示例,二、综合应用题：,41,47,小题，共,70,分。,46,(9,分,),理发师问题描述如下：理发店包含一间接待室和一间工作室，接待室内有,n(n1),把椅子，而工作室只有,1,把椅子。如果没有顾客，理发师就去睡觉；如果顾客来时所有的椅子都有人，那么顾客离去；如果理发师在忙且接待室有空闲的椅子，那么此顾客会坐在其中,1,把空闲的椅子上等待；如果理发师在睡觉，则顾客会唤醒他。请采用信号量机制解决该理发师问题,(,可用伪代码描述,),。,2010,年新大纲,Page,40,2024/9/28,2009,年真题,2010,年大纲,2010,年大纲解析,考点分析,2009,年真题解析,2010,年大纲例题解析,操作系统,Page,41,2024/9/28,新大纲与去年相比变化的地方,考查内容方面：,试卷考核内容仍然是,4,个部分：数据结构、计算机组成原理、操作系统和计算机网络。,分值方面：,数据结构,45,分、计算机组成原理,45,分、操作系统,35,分以及计算机网络,25,分。,题型方面：,仍然延续了单项选择题占,80,分，综合应用题,70,分的试卷结构。,2010,年新大纲解析,Page,42,2024/9/28,考核的知识点变化情况及其分析,1,、,进程管理,一点中，去掉了对,短任务优先,这一调度算法的要求。这样就进一步明确了对短进程，短线程优先算法的要求。,2,、去掉了连续分配内存管理方式一点所属的,单一连续分配,和,分区分配,两个小点，降低了对内存连续分配这一知识点的要求。,3,、去掉了文件共享一点所属的,共享动机,、,共享方式,和,共享语义,三个小点。考生事实上还是可以依据这三小点进行复习。,2010,年新大纲解析,Page,43,2024/9/28,考试预测与备考建议,2010,年将是计算机专业研究生入学考试第二次采取统考的形式，相比第一年来说，命题人对考试难度的把握将好于第一次命题时的情况，将会针对去年考生在考试中的表现作相应调整。,可以预见的是，今年的试题难度将不会有重大的，跳跃性的变化。,另一方面，各校的计算机研究生录取考试也已经存在了很多年，考研命题的重难点也相当明确，今年计算机考研命题重难点的设计也将不会出现大的变化。这一点从今年的大纲就可以看出来。,2010,年新大纲解析,Page,44,2024/9/28,考试预测与备考建议,（一）强调基础,计算机统考的这几门课，都是计算机专业核心的基础原理课程。从考试科目的选择上就可以看出计算机专业研究生入学考试对考生专业基础的要求。而这几门课程可以考核的基础知识点都相当多，如果想要拿高分，在考试中脱颖而出，必须把基础打扎实，全面性地进行学习。,2010,年新大纲解析,Page,45,2024/9/28,考试预测与备考建议,（一）强调基础,要掌握这么多的知识点，一要多看，二要多记，三要多练。多看课本，把参考教材里的知识点吃透；多记概念，重复理解各种原理与其实现；多练解题，这样既可以提高对解题方法的敏感度，又可以促进相关知识点的记忆，是快速提高知识掌握程度的一种好方法。,2010,年新大纲解析,Page,46,2024/9/28,考试预测与备考建议,（二）重点突出,从,09,年考试的命题与往年各校单独命题对比的情况来看，数据结构、组成原理、操作系统、计算机网络这四门课受各校选拔考试的重视程度是依次递减的，体现到大纲上，就是数据结构和组成原理两门课试题所占分值比重比较高，操作系统次之，而网络所占比例最小。从各科学习的难度来说，也有类似关系。因此，考生可以以此安排各科不同的复习强度。,2010,年新大纲解析,Page,47,2024/9/28,考试预测与备考建议,（二）重点突出,同样，在每一门课当中，考试的重要知识点也是比较明确，这从各校单独命题而考核的知识点相同或至少相互间有重合可以看出来，同样，,09,年的命题情况也与此相符合，因此我们可以预期,2010,年考试的重点仍是历年计算机专业课考核的重点。,2010,年新大纲解析,Page,48,2024/9/28,2009,年真题,2010,年大纲,2010,年大纲解析,考点分析,2009,年真题解析,2010,年大纲例题解析,操作系统,Page,49,2024/9/28,END,操作系统,人有了知识，就会具备各种分析能力，,明辨是非的能力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”通过阅读科技书籍，我们能丰富知识，,培养逻辑思维能力；,通过阅读文学作品，我们能提高文学鉴赏水平，,培养文学情趣；,通过阅读报刊，我们能增长见识，扩大自己的知识面。,有许多书籍还能培养我们的道德情操，,给我们巨大的精神力量，,鼓舞我们前进,。,