操作系统总复习

1、 总复习 2015-11 2013级软件3-4 考试时间与题型 考试时间：12.3，第14周周四上午10：10-12：00 考试题型： 选择题（20分），20个选择，每个选择1分 填空题（20分），20个空，每空1分 简答题（30分），6道题，每题5分，每章1题 综合题（30分），3道题， 第二章：用信号量解决进程同步、互斥问题 第三章：处理机调度/银行家算法 第四章/第五章：地址 变换/页面置换算法 总分：100分（闭卷，考试允许带计算器，所有计算结果精确至小数点后2位） 考试范围 第一章 操作系统引论 第二章 进程的描述与控制 第三章 处理机调度与死锁 第四章 存储器管理 第五章 虚拟存储

2、器 第六章 输入输出系统 第七章 文件管理 第八章 磁盘存储器的管理 第1章 操作系统引论 操作系统的目标 有效性、方便性、可扩展性、开放性 操作系统的作用 用户观点、资源管理者、虚拟机 操作系统的发展过程 脱机/联机输入输出技术 多道程序设计技术，解决了哪 二对矛盾 为什么引入分时系统 为什么引入实时系统 操作系统四大特征 并发、共享、虚拟、异步 并发与并行概念 五大功能 处理机管理、存储器管理、设备管理、文件管理、提供接口 接口类型：用户接口（CLI、GUI）、程序员接口（API/系统调用） OS结构 微内核结构：所采用的技术，微内核中包括什么内容 第2章 进程的描述与控制 程序并发执行时

3、的特征（间断、失去封闭、不可再现） 并发与并行的概念 进程相关的概念 为什么要引入进程 进程由什么组成的（程序段+数据段+PCB） 为什么说PCB是进程存在的唯一标志 进程的三种基本状态，它们之间如何进行转换 进程的同步与互斥 临界资源、临界区的概念 忙等的概念 信号量：记录型信号量的含义、信号量集 应用信号量机制解决进程的同步与互斥问题（前趋图、生产者与消费者、哲学家进餐、读者-写者） 进程通信（4种高级通信） 管程 管程的组成（4部分） 线程 线程的特点 第3章 处理机调度与死锁 调度层次 低级调度：进程调度 高级调度：作业调度 中级高度：内存调度 处理机调度算法 FCFS、SJF、高响应

4、比优先调度、RR，要求知道每种算法的调度规则、调度方式与偏好性，会计算周转时间与带权周转时间 实时调度算法 实时系统调度能力 最低松弛度优先算法（调度规则、松弛度） 死锁的相关概念 死锁的定义与产生死锁的原因 产生死锁的4个必要条件 预防死锁的方法 静态资源分配法、资源剥夺法、有序资源分配法 避免死锁 银行家算法 并非所有不安全状态都是死锁状态，但只要系统处于安全状态便可避免死锁状态。 检测并解除死锁 检测死锁：资源分配图完全简化法 解除死锁：剥夺资源与撤消进程 第45章（虚拟）存储器管理 程序的装入与链接 装入：绝对、可重定位、动态运行 链接：静态、装入时动态、运行时动态 重定位：重定位、静

5、态重定位、动态重定位 地址空间：作业地址空间与物理地址空间 动态分区分配算法 首次适应 循环首次 最佳 最坏 空闲分区的分配与回收算法 基本分页存储管理 页面、页框、页表的概念 逻辑地址结构 地址变换机构 快表 基本分段存储管理 为什么要引入分段存储管理方式 逻辑地址结构 地址变换机构 虚拟存储器基本概念 引入虚拟存储器的目的 虚拟存储器的特征 整体对换VS虚拟存储器 请求分页存储管理 系统需要的硬件支持 系统需要的软件支持 物理块分配与置换的策略 缺页中断与一般中断的不同 抖动 页面置换算法（OPT、FIFO、LRU、CLOCK） 第6章 输入输出系统 I/O系统 设备控制器 设备控制器是C

6、PU与I/O设备之间的接口 功能：完成设备与主机间的连接和通信 分类：字符设备与块设备，典型的设备是什么 通道 概念，作用：实现内存与外设之间的信息传输 I/O控制方式：程序、中断、DMA、通道 中断、DMA控制方式适用于何种类型的设备 缓冲管理 引入缓冲区的目的 设备独立性的概念 什么是设备独立性，如何实现 设备驱动 设备的分配 数据结构 独占设备的分配 SPOOLing技术及组成 磁盘存储器的调度 磁盘调度算法（FCFS；SSTF；SCAN；CSCAN） 第7章 文件管理 文件系统的目标 文件的逻辑结构 逻辑结构：概念及分类（顺序文件、索引文件、索引顺序文件） 目录管理 对目录管理的要求

7、第8章 磁盘存储器的管理 文件的物理结构 物理结构：概念及分类（连续分配方式、链接分配、索引分配） 文件存储空间的管理 位示图法 磁盘容错技术 第一、二级容错技术第1章 作业一、选择题1. 操作系统中采用多道程序设计技术提高了CPU和外部设备的 A. 利用率B. 可靠性C. 稳定性D. 兼容性2. 在操作系统中，并发性是指若干事件 发生。A. 在同一时刻B. 一定在不同时刻C. 在某一时间间隔内D. 依次在不同时间间隔内3. 订购机票系统处理各个终端的服务请求，处理后通过终端回答用户，所以它是一个 。A. 分时系统B. 多道批处理系统C. 计算机网络D. 实时信息处理系统4. 下列选择中， 不

8、是操作系统关心的主要问题。A. 管理计算机裸机B. 设计、提供用户程序与计算机硬件系统的界面C. 管理计算机系统资源D. 高级程序设计语言的编译器5. 在操作系统中，处理机负责对进程进行管理和调度，对系统中的信息进行管理的部分通常称为 。A. 数据库系统B. 软件系统C. 文件系统D. 检索系统二、简答题1、设计现代OS的主要目标是什么？2、何谓脱机I/O和联机I/O？3、实现分时系统的关键问题是什么？应如何解决？4、OS有哪几大特征？其最基本的特征是什么？5、是什么原因使操作系统具有异步性特征？6、何谓微内核技术？在微内核中通常提供了哪些功能？三、综合题1、设内存中有三道程序A、B、C，它们

9、按A、B、C的优先次序执行。它们的计算和I/O操作时间如表所示（单位：ms）。三道程序的操作时间 程序操作ABC计算306020I/O403040计算101020假设三道程序使用相同设备I/O操作，即程序是以串行方式使用设备，调度程序的执行时间忽略不计，试计算出在单道和多道两种情况下，完成这三道程序各要花多少时间？要求画出多道运行的时序图。（假定在多道方式下采用的是基于优先级的非抢占调度程序）第2章作业1、进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？（1）若干同学去图书馆借书；（2）两队举行篮球比赛；（3）流水线生产的各道工序；（4）商品生产和社会消费。2、

10、已知一个求值公式(A23B)/(B+5A)，若A、B已赋值，试画出该公式求值过程的前趋图，并使用信号量描述这些前趋关系。3、试用信号量实现课件中司机与售票员进程的同步关系课后作业一、简答题：1、什么是前趋图？为什么要引入前趋图？2、程序并发执行时为什么会失去封闭性和可再现性？3、试说明PCB的作用，为什么说PCB是进程存在的唯一标志？4、同步机构应遵循哪些基本准则？5、何谓“忙等”？它有什么缺点？6、试从物理概念上说明记录型信号量wait和signal。7、在生产者消费者问题中，分别分析如果缺少了signal(full)或signal(empty)，对执行结果将会有何影响？8、我们为某临界资源

11、设置一把锁W，当W=1时表示关锁；当W=0时表示锁已经打开，试写出开锁和关锁原语，并利用它们去实现互斥。9、试说明管程由哪几部分组成，为什么要引入条件变量？10、为什么要引入信号量集? 信号量集中有哪两种操作？11、当前有哪几种高级通信机制？12、为什么引入进程？为什么引入线程？ 13、试说明线程具有哪些属性？14、何谓用户级线程和内核支持线程？打印进程单缓冲区计算进程综合题：1、如图所示，有一计算进程和一打印进程，它们共享一个单缓冲区，计算进程不断地计算出结果并将它放入单缓冲区中，打印进程则负责从单缓冲区中取出每一个结果进行打印。请用信号量来实现它们的同步关系。2、试用信号量解决读者写者问题

12、，使得写者与读者优先级根据到达顺序确定（读写平等）。在该解决方案中，请加入阅览室最多只许多N位读者的限制条件。然后用到达序列：R1, R2, W1, R3, R4, W2进行测试列出类似如下测试结果进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者3、请给出一个写者优先的“读者写者”问题的算法描述，实现比较温和的写者优先策略。然后用到达序列：R1, R2, W1, R3, R4, W2进行测试列出类似如下测试结果进程行为rmutex=1wmutex=1Readcount=0状态

13、备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者4、桌上有一只能容纳一个水果的盘子；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果，1）试用信号量实现他们的同步关系；2）如果有两个家庭的爸爸、妈妈、儿子、女儿和二只盘子呢？会需要专门的实现吗？ 5、请用counter作为临界资源的方案解决生产者消费者问题？这种解决方案与书本上的解决方案相比，有何缺点第三章1、某进程被唤醒后立即投入运行，我们就说这个系统采用的是剥夺调度方法，对吗？为什么？10”2、什么是高响应比

14、优先调度算法，它采用何种调度方式？10”3、假设一个系统中有4个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（MFQ，第i级队列的时间片=2i-1）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，填入下表中（抢占式算法要求画出调度时序图，HRRN算法要求列出调度时的响应比）。30”进程到达时间服务时间A05B12C39D67算法时间进程平均时间ABCDFCFS完成时间周转时间带权

15、周转时间SPF（非抢占）完成时间周转时间带权周转时间SPF（抢占）完成时间周转时间带权周转时间RR（q=1）完成时间周转时间带权周转时间MFQ（q=2i-1）完成时间周转时间带权周转时间作业号到达时间运行时间开始时间完成时间周转时间带权周转时间调度依据平均周转时间为：平均带权周转时间为：4、在一个软实时系统中有四个周期性任务，任务A、B、C、D分别要求每50ms、100ms、200ms、250ms执行一次，假定A、B、C、D的执行时间分别为35ms、20ms、10ms与x ms，那么要使得这个实时系统为可调度的，x的最大值为多少？（要求列出计算公式）10”5、什么是最低松弛度优先调度算法？它采

16、用何种调度方式？抢占时机是什么？10”6、若有4个周期性任务，任务A要求每30ms执行一次，执行时间为15ms；任务B要求每50ms执行一次，执行时间为5ms；任务C要求每50ms执行一次，执行时间为15ms；任务D要求每100ms执行一次，执行时间为10ms，应如何按最低松弛度优先算法对它们进行CPU调试？ （要求画出0-150ms时段的调度时序图，并列出每次切换时每个任务的松弛度）20”7、何谓死锁？产生死锁的原因和必要条件是什么？10”8、3个进程共享4个同类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？10”9、不安全状态是否必然导致系统进入死锁状态？举例说

17、明。10”10、在银行家算法中，若出现下面的资源分配情况： 30”ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 5 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 1 3 20 5 5 2P40 0 1 40 6 5 8试问：1）该状态是否安全（要求列出安全性算法检查表）？ 2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它（要求根据分配算法列出检查过程）？ 3）如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态，请说明原因？11、进程资源的使用情况和可用情况如表所示，请画

18、出资源分配图，并对资源图进行简化，这种情况下系统会发生死锁吗？20”进程当前分配数待分配的请求可用资源R1R2R3R1R2R3R1R2R3P1P2P3P423100131000110001001001000012、要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目，而不是存在的资源数）。10”进程当前分配数最大分配数R1R1P1P2P3P41132329713、在时间片轮转法中，应如何确定时间片的大小？10”14、在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法能使资源利用率最高？10”第4-5章作业1、“整体对换从逻辑上也扩充了内存，因此也实现了虚

19、拟存储器的功能”这种说法是否正确？请说明理由。2、什么叫静态重定位，什么叫动态重定位，它们分别与何种装入方式相对应？3、虚拟存储器有哪些特征？其中最本质的特征是什么？4、某系统采用页式存储管理策略，拥有逻辑空间32页，每页为2KB，拥有物理空间1MB。1）写出逻辑地址的格式。2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？3）如果物理空间减少一半，页表结构应相应作怎样的改变？5、对于下表所示的段表，请将逻辑地址（0，137）、（1，4000）、（2，3600）、（5，230）转换成物理地址。段 表段号内存地址段长050K10KB160K3KB270K5KB3120K8KB4150

20、K4KB6、在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？7、在一个请求分页系统中，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时，访问过程中所发生的缺页次数和缺页率，并比较所得结果。 （选做括号内的内容：根据本题的结果，请查找资料，说明什么是Belady现象，在哪种置换算法中会产生Belady现象，为什么？）8、现有一请求调页系统，页表保存在寄存器中。若一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，

21、则处理一个缺页中断需要20ms。内存存取时间为1us，访问页表的时间可忽略不计。假定70%被替换的页被修改过，为保证有效存取时间不超过2us，可接受的最大缺页率是什么？ 第6章习题1、有哪几种I/O控制方式？哪种I/O控制方式适用于字符设备？哪种I/O控制方式适用于块设备？答：有四种：使用轮询的可编程I/O方式；使用中断的可编程I/O方式；直接存储器访问（DMA） 方式；I/O通道控制方式。其中使用中断的可编程I/O方式适用于字符设备，直接存储器访问（DMA） 方式适用于块设备。2、在设备管理中，为什么要引入缓冲区？答：在设备管理中，引入缓冲区的主要原因有以下四点：1）缓和CPU与I/O设备速

22、度不匹配的矛盾；2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制；3）解决数据粒度不匹配的问题；4）提高CPU和I/O设备之间的并行性。3、什么是设备的独立性？引入设备的独立性有什么优点？如何实现设备的独立性？答：设备的独立性是指应用程序独立于具体使用的物理设备。引入设备独立性可提高设备分配的灵活性和设备的利用率，使I/O重定向更易于实现。为实现设备的独立性引入了逻辑设备和物理设备的概念，在应用程序中使用的是逻辑名，而系统中还配备了一张将逻辑设备名转换为物理设备名的数据结构逻辑设备表（LUT），从而实现了应用程序所使用的设备与具体的设备无关的设备独立性。4、什么是SPOOLing技术

23、，它由哪几部分组成？答：SPOOLing也称为假脱机技术，是指在多道程序的环境下，利用多道程序中的一道或两道来模拟外围控制机，从而在联机的条件下实现同时外围操作的技术。它由输入/输出井、输入/输出缓冲区、输入/输出进程和井管理程序四部分组成。5、什么是SCAN算法，它是为了解决什么问题而引入的？答：SCAN算法是一种磁盘调度算法，它选择在磁头当前移动方向上，与当前磁头所在磁道距离最近的，要求访问的磁道进行访问，直至在当前移动方向上再无需要访问的磁道时，才反转磁臂移动方向，并执行与前面相同的调度策略。SCAN算法的引入是为了避免出现进程“饥饿”现象。6、为什么引入NStepSCAN算法，它是如何

24、解决上述问题的？答：在SSTF、SCAN、CSCAN几种磁盘调度算法中，都可能出现“磁臂粘着”现象，即有一个进程或几个进程对某一磁道有较高的访问频率，从而导致磁臂停留在某处不动，垄断了整个磁盘设备。NStepScan算法将磁盘请求队列分成若干个长度为N的子队列，磁盘调度按FCFS算法依次处理这些子队列。而每处理一个子队列时又是按照SCAN算法。当处理某子队列时，又有新的磁盘I/O请求，便将新请求进程放入其他队列中，从而避免了粘臂现象。7、假定一磁盘有200个柱面，编号为0-199，在完成了磁道125处的请求后，当前正在磁道143处为一个请求服务。若请求队列的先后顺序为86，147，91，177，94，150，102，175，130，试分别采用FCFS、SSTF、SCAN算法完成上述请求，写出磁头移动的顺序，并计算存取臂移动总量。 （PPT最后一页的课堂练习）FCFS算法SSTF算法SCAN算法CSCAN算法8657147414741474147611503150315039156130201752