操作系统总复习题纲(整理版)资料(DOC 21页).doc

1、考试题型：选择题（20分），20个选择，每个选择1分填空题（20分），20个空，每空1分简答题（25分），5道题，每题5分综合题（35分），3道题，第二章：用信号量解决进程同步、互斥问题（生产者消费者问题）第三章：处理机调度（通用/实时）/银行家算法第四章：分页系统地址变换/页面置换算法/动态分区分配算法总分：100分（闭卷，考试允许带计算器，所有计算结果精确至小数点后2位）考试范围第一章 操作系统引论第二章 进程管理第三章 处理机调度与死锁第四章 存储器管理第五章 设备管理 第六章 文件管理第一章 操作系统引论1、操作系统的作用： 1)OS作为用户与计算机硬件系统之间接口(用户观点)：OS处

2、于用户与计算机硬件系统之间，用户通过OS来使用计算机系统； 2)OS作为计算机系统资源的管理者(资源管理者观点)； 3)OS实现了对计算机资源的抽象(虚拟机观点)。2、操作系统的发展过程 1)批处理系统是如何提高资源的利用率 用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。 2)多道与单道的周转时间计算单道：顺序执行的总时间多道抢占式/非抢占式 3)分时系统（为什么引入，实现中的关键问题）引入目的：为了改进响应时间和性能，提供交互式操作环境，导致了分时系统的出现。实现中的关

3、键问题： 及时接收 多路卡：使主机能同时接收各用户从终端上输入的数据。 缓冲区：暂存用户键入的命令。 及时处理 作业直接进入内存 不允许一个作业长时间占用处理机 4)实时系统（为什么引入，更注重什么特征）引入原因：为了满足实时控制和实时信息处理的应用需求 更注重什么特征：多路性、独立性、及时性、交互性、可靠性3、操作系统四大特征并发性、共享性、虚拟性、异步性 1) 并发：在一段时间内宏观上有多个程序在同时运行； 共享：系统中的资源可供内存中多个并发执行的进程(线程)共同使用； 虚拟：通过某种技术把一个物理实体变为若干个逻辑上的对应物； 异步：进程以人们不可预知的速度向前推进2) 并发与并行概念

4、 并行性是指两个或多个事件在同一时刻发生； 并发性是指两个或多个事件在同一时间间隔内发生。4、五大功能处理机管理、存储器管理、设备管理、文件管理、提供接口 五大功能：1)处理机管理：创建和撤销进程(线程)，撤销已结束的进程，以及控制进程在运行过程中的状态转换；2)存储器管理：为多道程序的运行提供良好的环境，方便用户使用存储器；3)设备管理：完成用户进程提出的I/O请求；为用户进程分配其所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；方便用户使用I/O设备。4)文件管理：对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性；5)提供接口：操作系统向用户提供用户与操作

5、系统的接口 -用户接口：是提供给用户使用的接口,用户可通过接口取得操作系统的服务。-程序接口：以系统调用的形式供用户编程时使用。几乎各种操作系统都提供了系统调用，供程序设计。 接口类型：1) 用户接口（CLI、GUI） CLI(Command Line Interface)：命令行接口 GUI(Graphics User Interface)：图形用户接口2) 程序员接口（API,Application Programming Interface,应用程序接口）5、OS结构：微内核结构 1)所采用的技术：采用面向对象技术，基于“抽象”和“隐蔽”原则控制系统的复杂性，再进一步利用“对象”、“封装

6、”和“继承”等概念来确保操作系统地“正确性”、“可靠性”。2) 微内核中包括的内容： 基本概念： 足够小的内核； 基于客户/服务器模式； 应用“机制与策略分离”原理； 采用面向对象技术。 基本功能：进程(线程)管理；低级存储器管理；中断和陷入处理； 优点： 提供了系统的可扩展性；增强了系统的可靠性；可移植性；提供了分布式系统地支持；融入了面向对象技术。 存在的问题：运行效率有所降低；引起更多的上下文切换。第二章 进程管理1、前趋图（要求会画，会用相应的程序来描述） 概念：是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。2、 程序并

7、发执行时的特征（间断、失去封闭、不可再现）1)间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。2)失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。(封闭性：程序运行时独占全机资源，资源的状态除初始状态外只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响)。3)不可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，

8、还是“停停走走”地执行，将获得不同的结果。进程相关的概念3、为什么要引入进程：为了使程序能并发执行，且为了对并发执行的程序加以描述和控制。4、 进程由什么组成的（程序段+数据段+PCB）5、 进程的三种基本状态就绪、执行、阻塞 它们之间如何进行转换：处于就绪状态的进程，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它就由就绪状态转变为执行状态。正在执行的程序也称为当前进程，如果因分配给它的时间片已完而被暂停执行时，该进程便由执行状态又回复到就绪状态；如果因发生某事件而使进程的执行受阻(例如，进程请求访问某临界资源，而该资源正被其它进程访问时)，使之无法继续执行，该进程将由执行状态转变

9、为阻塞状态。 6、进程的同步与互斥 1)临界资源的概念：在一段时间内只允许一个进程访问的资源。临界资源的访问要求互斥的访问。2)临界区的概念：每个进程中访问临界资源的代码3)原语的概念：系统提供的一组通信命令4)如何写原语具体情况具体分析5)记录型信号量的物理含义： wait(S)：当S.value0时，表示目前系统中这类资源还有可用的。执行一次wait 操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源减少一个，因此描述为S.value:=S.value-1；当S.value0时，表示该类资源已分配完毕，进程应调用block原语自我阻塞，放弃处理机，并插入到信号量链表S.L中

10、。 signal(S)：执行一次signal操作，意味着释放一个单位的可用资源，使系统中可供分配的该类资源数增加一个，故执行S.value:=S.value+1 操作。若加1后S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，因此应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。6) 如何解决忙等问题(？有待进一步解答) 7)应用信号量机制解决进程的同步与互斥问题（生产者与消费者(可能会出综合题)、哲学家进餐、读者-写者）7、管程代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了的操作系统地资源管理模块 1)管程的组成

11、(4部分)管程的名称；局部于管程内部的共享数据结构说明；对该数据结构进行操作的一组过程；对局部于管程内部的共享数据设置初始值的语句。2) 为什么引入条件变量：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其他进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量。8、进程的通信1)高级通信的类型（共享存储器系统、消息传递系统、管道通信） 共享存储器系统：相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。 消息传递系统：进程间的数据交换以格式化的消息为单位。程序员直接利用操作系统提供的一组通信

12、命令(原语)，不仅实现大量数据的传递，还隐藏了通信的实现细节，使通信过程对用户是透明的，从而大大减化了通信程序编制的复杂性。 管道通信：发送进程和接受进程利用管道(用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件)进行通信。2) 消息传递通信 直接通信方式：发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显示方式提供对方的标识符。 间接通信方式：进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体称为信箱。9、线程轻量级的(线程中的实体

13、基本上不拥有系统资源，只是有一点必不可少 的、能保证其独立运行的资源)。第三章 处理机调度与死锁1、处理机调度算法1)SJF(Shortest Job First)，短作业(进程)优先调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。(抢占和非抢占)2)高响应比优先调度(非抢占) 等待时间+要求服务时间 响应时间 (响应比)= 要求服务时间 = 要求服务时间 =1 3) 时间片轮转(RR)(抢占)4) 要求会计算周转时间与带权周转时间 周转时间=完成时间到达时间； 带权周转时间=周转时间/服务时间 2、实时调度算法1)系统处理能力与可调度性： 假定系统中有m个周

14、期性的硬实时任务，它们的处理时间可表示为 ，周期时间表示为，则在单处理机情况下，必须满足下面的限制条件： 系统才是可调度的；同理，多处理机情况下，则 2) 最早截止时间优先算法(EDF，Earliest Deadline Firtst)：根据任务的开始截止时间来确定任务的优先级。(抢占和非抢占) 3) 最低松弛度优先算法(LLD，Least Laxity First)：根据任务紧急(或松弛)的程度，来确定任务的优先级。(抢占) 松弛度=必须完成时间其本身的运行时间当前时间3、掌握各种算法的调度方式(见上述算法括号中内容)4、死锁的相关概念1)死锁的定义：多个进程同时竞争多个临界资源所产生的僵持

15、状态(多个进程竞争一个资源不会产生死锁)；进程推进次序不等当。(？有待进一步更正)2)产生死锁的原因： 竞争资源引起进程死锁 可剥夺和非剥夺性资源 竞争非剥夺性资源 竞争临时性资源 进程推进顺序不当引起死锁 进程推进顺序合法 进程推进顺序非法3) 产生死锁的必要条件: 互斥条件：指进程对所分配到的资源进行排它性使用，即要求在一段 时间内某资源仅被一进程占用。如果此时还有其它进程请求该资源，则请求者 只能等待，直至占有该资源的进程用毕释放。 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占用，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。 不剥

16、夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时自行释放。 环路等待条件：在发生死锁时，必然存在一个进程资源的环行链。即进程集合 P0，P1，Pn 对资源的请求成环状：P0 P1 P2 Pn P0(P0正在等待一个P1占用的资源；P1正在等待P2占用的资源.)5、 预防死锁的方法：1) 摒弃“请求和保持”条件(静态资源分配法)：系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。2) 摒弃“不剥夺”条件(资源剥夺法)：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请

17、。3) 摒弃“环路等待”条件(有序资源使用法)：系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出。6、避免死锁1)银行家算法(可能会出综合题)银行家算法中的数据结构 系统中进程总数 n 资源类总数 m 可利用资源向量Available：是一个含有m个元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其值随资源的分配和回收而动态地改变。 最大需求矩阵Max：是一个nm的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。 分配矩阵Allocation：是一个nm的矩阵，定义了系统中

18、每一类资源当前已分配给每一进程的资源数。 需求矩阵Need：是一个nm的矩阵,表示每一个进程尚需的该类资源数。 上述三个矩阵间存在下述关系：Need i, j = Max i , j Allocation i , j 银行家算法： 设是进程的请求向量，如果j=k，表示进程需要K个类型的资源。当发出资源请求后，系统按下述步骤进行检查： 1如果jNeedi,j，便转向步骤(2)；否则认为出错，因为它所需 要的资源数已超过它所宣布的最大值。 2如果jAvailablej，便转向步骤(3)；否则，表示尚无足够资源， 须等待。 3系统试探着把资源分配给进程，并修改下面数据结构中的数值： Availabl

19、ej：=Availablejj； Allocationi,j：= Allocationi,j+j； Needi,j：=Needi,jj；4系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若 安全，才正式将资源分配给进程，以完成本次分配；否则，将本次的试探 分配作废，恢复原来的资源分配状态，让进程等待。安全性算法： 系统所执行的安全性算法可描述如下：1设置两个向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数 目，它含有m个元素，在执行安全算法时，Work：=Available； Finish，它表示系统是否有足够的资源分配给进程,使之运行完成。开始 时先做Fi

20、nishi:=false；当有足够资源分配给进程时，再令Finishi:=true Work:=Available; Finishi:=false;2从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj; 若找到，执行步骤(3)；否则，执行步骤(4)。3当进程获得资源后，可顺利执行，直至完成，并释放处分配给它的资源，故应执行：Worki:=Worki+Allocationi,j; Finishi:=true; go to step 2;4若对所有进程的Finishi=true都满足，则表示系统处于安全状态，否则，系统处于不安全状态。 (2)并非所有

21、不安全状态都是死锁状态，但只要系统处于安全状态便可避免死锁状态。7、检测并解除死锁 1)检测死锁：资源图完全简化法 2)解除死锁： 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。 撤消进程：最简单的撤销进程的方法是使全部死锁都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤销进程，直至有足够的资源可用，使死锁状态消除为之。第四章 存储器管理1、程序的装入与链接 1)装入：绝对、可重定位、动态运行 绝对装入方式：绝对装入程序按照装入模块中的地址，将程序和数据装 入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地 址完全相同，故不须对程序和数据的地址进行修改。 可重

22、定位装入方式：根据内存的当前情况，将装入模块装入到内存的适 当位置。 动态运行时装入方式：允许程序运行时在内存移动位置。 2)链接：静态、装入时动态、运行时动态 静态链接方式： 对相对地址进行修改 变换外部调用符号 装入时动态链接：用户源程序经编译后所得的目标模块，是在装入内 存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块 调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存。 运行时动态链接：对某些模块的链接推迟到程序执行时才进行链接， 亦即，在执行过程中，当发现一个被调用模块尚未装入内存，立即由 OS去找到该模块并将它装入内存，并把它链接到调用者模块上。凡在 执

23、行过程中未被调用到的目标模块，都不会被调入内存和被链接到装入 模块上。 3)重定位：静态重定位、动态重定位 静态重定位：地址变换只是在装入时一次完成，以后不再改变。 动态重定位：动态分区分配方式的基础上增加紧凑功能。2、动态分区分配算法1)首次适应(first fit，FF)：从链首开始顺序搜索，直至找到一个大小能满足要求的空闲分区，从该分区中划出一块能放下作业的空间给请求者，剩下的空闲分区仍留在空闲链中。若未找到大小大于作业要求的大小，则分配失败。2)循环首次(next fit)：不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一空闲分区开始查找，直至找到一个能满足要求的空闲分区，从

24、中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查询指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小扔不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查询指针。3)最佳适应算法(best fit)：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。4)最坏适应算法(worst fit)：扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用。该算法要求将所有的空闲分区按其容量以从

25、大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。5)空闲分区的分配与回收算法 分配内存：利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.sizeu.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。 回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲

26、区链(表)中找到相应的插入点，此时可能出现一些四种情况之一： 1回收区与插入点的前一个空闲分区F1相邻接。此时应将回收区与插入点 的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1的大小。 2回收分区与插入点的后一空闲分区F2相邻接。此时也可将两分区合并， 形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者 之和。 3回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并， 使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 4回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表 项，填写回收区的首址和大小，并根据其首址插入到空闲链中

27、的适当位 置。 3、可重定位分区分配1)动态重定位的引入连续式分配中，内存总量大于作业大小的多个小分区不能容纳作业。 2)动态重定位的实现程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。对内存进行“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。3)动态重定位分区分配算法：可重定位分区分配算法就是在动态分区分配方式(根据进程的实际需要，动态地为之分配内存空间)的基础上增加紧凑功能。4、基本分页存储管理1)页面、页框、页表的概念 页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页

28、面(page)或页。 页框：把内存空间分成与页面相同大小的若干个存储块，称为(物理)块 或页框( frame)。 页表：系统为每个进程建立的一张页面映像表，以实现从页号到物理 块号的地址映射。2) 逻辑地址(用户程序中使用的地址)结构 页号P+页内地址d(页内的偏移量) P=INTA/L；(给定一个逻辑地址空间中的地址)/L页面大小) d=A MOD (L ) ;3) 物理地址与逻辑地址的转换 设给定的逻辑地址为A，页面大小为L，则先求出页号P=A/L和页内地址 d=a MOD L ； 查页表找到对应得物理块为n； 则物理地址= n*L + d；5、基本分段存储管理1)为什么要引入分段存储管理

29、方式引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要：方便编程信息共享 信息保护 动态增长 动态链接 2) 逻辑地址结构段号+段内地址3) 物理地址与逻辑地址的转换 查找段表寄存器(用于存放段表始地址和段表长度TL) 若段号S 段表长度TL 访问越界 否则，从段表项中读出该段在内存的起始地址 段内地址d 段长SL 越界中断 否则，基址 + 段内地址d = 内存物理地址6、段页式存储管理3次访问内存(访段表、访页表、取指令/数据)1)作业地址空间的管理： 段号(S) 段内页号(P)页内地址(W)2)物理地址空间的管理：在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，

30、其中存放段表始址和段表长TL。进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若STL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。7、虚拟存储器基本概念1)局部性原理 时间局部性：一个数据结构被访问，不久以后可能再次被访问。典型 原因：由于在程序中存在着大量的循环操作。 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的 存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定 的范围之内

31、。其典型情况便是程序的顺序执行。2) 虚拟存储器的特征 多次性：指一个作业被分成多次调入内存运行，这是虚拟存储器最重要的特征。 对换性：指允许在作业的运行过程中换入、换出。 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器表现出的最重要特征，是实现虚拟存储器的最重要的目标。 虚拟性是以多次性和对换性为基础，多次性和对换性是建立在离散分 配的基础上。8、请求分页存储管理 1)系统需要的硬件支持（3个） 页表机制:将用户地址空间中的逻辑地址变换为内存空间中的物理地址。页号物理块号状态位P访问字段A修改位M外存地址 1状态位P：用于指示该页是否已调入内存，

32、供程序访问时参考； 2访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考； 3修改位M：表示该页在调入内存后是否被修改过，供置换页面时参 考。由于内存中的每一页都在外存上保留一份副本，因此，若未被 修改，在置换该页时就不需再将该页重写到外存上，以减少系统地 开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上， 以保证外存中所保留的始终是最新副本。 4外存地址：用于指出该页在外存上的地址，通常是物理块号，供调 入该页时参考。缺页中断机构 1缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条 指令执行完后检查和处理中断信号；

33、2缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到 该指令的下一条指令执行 ； 3一条指令在执行期间，可能产生多次缺页中断。地址变换机构 1首先去检索快表，试图从中找到访问的页； 2如果从快表中找到所要访问的页，则修改页表项中的访问位；如果 是写操作，则应将修改位置“1”。然后利用页表项中给出的物理块 号和页内地址，形成物理地址。地址变换到此结束。 3如果在快表中未找到该页的页表项，则应再到内存中去查找页表， 再从找到的页表项中的状态位P，来了解该页是否已调入内存。其结 果可能是： 该页已调入内存：将页表项写入快表。 该页尚未调入内存。产生缺页中断，请求OS调页。2) 系统需要的软件

34、支持（2个）?(有待进一步探讨)3)页面置换算法（OPT、FIFO、LRU、CLOCK） 1OPT(Optimal)，最佳置换算法：所选择额被淘汰的页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。向右看，置换最远的。 2FIFO先进先出页面置换算法：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。向左看，置换连续块数最多的。 3LRU(Least Recently Used)最近最久未使用置换算法：根据页面调入内存后的使用情况进行决策的。向左看，置换距离最远的 4CLOCK 简单的Clock置换算法：为每页设置一个访问位(使用标志位use bit)，再

35、将内存总的所有页面都通过链接指针链接成一个循环队列。若某页被访问，则其访问位被置1(use bit=1)。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首区检查第一个页面。 改进型Clock置换算法 在改进型Clock算法中，它既考虑到页面的使用情况，又考虑页面是否被修改过。即选择换出页面时，既要是未使用过的页面，又要是未修改过的页面，把同时满足两条件的页面作为首选淘汰页。 访问位 A 和修改位 M 的四种组合

36、情况： 1类(A=0，M=0)：表示该页最近既未被访问，又未被修改，是最 佳淘汰页 2类(A=0，M=1)：表示该页最近未被访问，但已被修改，并不是 很好的淘汰页 3类(A=1，M=0)：最近已被访问，但未被修改，该页有可能再被 访问 4类(A=1，M=1)：最近已被访问且被修改，该页可能再被访问 执行过程：第一步：从指针所指示的当前位置开始，扫描循环队列，寻找第一类页 面，将所遇到的第一个页面作为选中的淘汰页。【不修改A】第二步：如果第一步失败，即查找一周后未遇到第一类页面，则开始第 二轮扫描，寻找第二类页面，将所遇到的第一个页面作为选中 的淘汰页。在第二轮扫描期间，将所有扫描过的页面的的访

37、问 位都置0。【A=0】第三步：重复第一步或第二步，此时必能找到被淘汰的页。第五章 设备管理1、设备控制器设备控制器是CPU与I/O设备之间的接口分类：字符设备与块设备2、 I/O控制方式：程序、中断、DMA、通道1) 程序I/O方式(忙等待方式)：在处理机向控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy置为1，然后便不断地循环测试busy。2) 中断驱动I/O控制方式：当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。3) DMA(Direct Memory Access)，直接存储器

38、访问I/O控制方式： 1数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至 少一个数据块； 2所传送的数据是从设备直接送入内存的，或者相反； 3仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据 的传送是在控制器的控制下完成的。4)I/O通道控制方式：把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。5)采用中断方式的典型设备适合于字符设备(屏幕、键盘)6)DMA方式的典型设备适合于块设备(磁盘、打印机)3、缓冲管理1)为什么引入缓冲区 缓和CPU和I/O设备间速度不匹配的矛盾。 减少对CPU的中断频率，放宽对CP

39、U中断响应时间的限制。 提高CPU和I/O设备之间的并行性 2) 单/双缓冲 单缓冲：每当用户进程发出一I/O请求时，操作系统便在主存中为之分 配一缓冲区。 双缓冲： 1若采用行输入方式，则采用双缓冲通常能消除用户的等待时间， 即用户在输入完第一行之后，在CPU执行第一行中的命令时，用户 可继续向第二缓冲区输入下一行数据。 2在双机通信时，为了实现双向数据传输，必须在两台机器中都设 置两个缓冲区，一个用作发送缓冲区，另一个用作接收缓冲区。3)缓冲池：在池中设置了多个可供若干个进程共享的缓冲区。4、 设备驱动程序的作用：接收上层软件发来的抽象I/O要求，如read或write命令，在把它转换为具

40、体要求后，发送给设备控制器，启动设备去执行；此外，它也将由设备控制器发来的信号传送给上层软件。5、设备的分配1)数据结构SDT-DCT-COCT-CHCT 设备控制表(DCT)：用于记录本设备的情况； 控制器控制表(DCT)：用于记录本控制器情况； 通道控制表(CHCT)：用于记录本通道情况； 系统设备表(SDT)：记录系统中全部设备的情况。2) SPOOLing技术，即所谓假脱机输入/输出技术。把这种技术用于对设备的使用实质就是对输入输出操作成批处理。(SPOOLing也称为假脱机操作，是指在多道程序的环境下，利用多道程序中的一道或两道来模拟外围控制机，从而在联机的条件下实现脱机I/O功能。)3) SPOOLing技术的组成 输入井和输出井：这是在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据；输出井是模拟脱机输出时的磁盘，用于暂存用户程序的输出数据。 输入缓冲区和输出缓冲区：为了换和CPU和磁盘之间速度不匹配的矛盾，在内存中要开辟两个缓冲区；输入缓冲区和输出缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用于暂存从