操作系统复习.pdf

《操作系统复习.pdf》由会员分享，可在线阅读，更多相关《操作系统复习.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统的主要功能操作系统的主要功能从资源管理观点看，操作系统具有五大功能：从资源管理观点看，操作系统具有五大功能：处理机管理处理机管理存储器管理存储器管理设备管理设备管理文件管理文件管理作业管理作业管理1.1.处理机管理处理机管理主要任务：是对处理机的分配和运行实施有效管理。对处理机管理，可归结为对进主要任务：是对处理机的分配和运行实施有效管理。对处理机管理，可归结为对进程的管理。程的管理。进程管理的主要功能进程管理的主要功能进程控制：当用户作业要运行时，应为之建立一个或多个进程，并为它分配除处理进程控制：当用户作业要运行时，应为之建立一个或多个进程，并为它分配除处理机以外的所有资源，机以外

2、的所有资源，将它放入进程就绪队列。将它放入进程就绪队列。当进程运行完成时，当进程运行完成时，立即撤消该进程，立即撤消该进程，以便及时释放其所占有的资源。进程控制的基本功能就是创建和撤消进程以及控制以便及时释放其所占有的资源。进程控制的基本功能就是创建和撤消进程以及控制进程的状态转换。进程的状态转换。进程同步：所谓进程同步是指系统对并发执行的进程进行协调。最基本的进程同步进程同步：所谓进程同步是指系统对并发执行的进程进行协调。最基本的进程同步方式是使诸进程以互斥方式访问临界资源。方式是使诸进程以互斥方式访问临界资源。此外，对于彼此相互合作、去完成共同任务的诸进程，则应由系统对它们的运行速此外，对

3、于彼此相互合作、去完成共同任务的诸进程，则应由系统对它们的运行速度加以协调。度加以协调。进程通信：进程通信：对于相互合作的进程，对于相互合作的进程，在它们运行时，在它们运行时，相互之间往往要交换一定的信息，相互之间往往要交换一定的信息，这种进程间所进行的信息交换称为进程通信。这种进程间所进行的信息交换称为进程通信。进程调度：当一个正在执行的进程已经完成，或因某事件而无法继续执行时，系统进程调度：当一个正在执行的进程已经完成，或因某事件而无法继续执行时，系统应进行进程调度，重新分配处理机。进程调度是指按一定算法，如最高优先算法，应进行进程调度，重新分配处理机。进程调度是指按一定算法，如最高优先算

4、法，从进程就绪队列中选出一进程，把处理机分配给它，为该进程设置运行现场，并使从进程就绪队列中选出一进程，把处理机分配给它，为该进程设置运行现场，并使之投入运行。之投入运行。2.2.存储器管理存储器管理存储器管理的主要任务存储器管理的主要任务:为多道程序的并发运行提供良好环境；为多道程序的并发运行提供良好环境；便于用户使用存储器；便于用户使用存储器；提高存储器的利用率；提高存储器的利用率；为尽量多的用户提供足够大的存储空间。为尽量多的用户提供足够大的存储空间。存储器管理的功能存储器管理的功能内存分配：多道程序能并发执行的首要条件是，各道程序都有自己的内存空间，因内存分配：多道程序能并发执行的首要

5、条件是，各道程序都有自己的内存空间，因此，为每道程序分配内存是存储器管理的最基本功能。此，为每道程序分配内存是存储器管理的最基本功能。内存保护：为保证各道程序都能在自己的内存空间运行而互不干扰，要求每道程序内存保护：为保证各道程序都能在自己的内存空间运行而互不干扰，要求每道程序在执行时能随时检查对内存的所有访问是否合法。必须防止因一道程序的错误而扰在执行时能随时检查对内存的所有访问是否合法。必须防止因一道程序的错误而扰乱了其它程序，尤其应防止用户程序侵犯操作系统的内存区。乱了其它程序，尤其应防止用户程序侵犯操作系统的内存区。地址映射：在多道程序的系统中，操作系统必须提供把程序地址空间中的逻辑地

6、址地址映射：在多道程序的系统中，操作系统必须提供把程序地址空间中的逻辑地址转换为内存空间对应的物理地址的功能。地址映射功能可使用户不必过问物理存储转换为内存空间对应的物理地址的功能。地址映射功能可使用户不必过问物理存储空间的分配细节，从而为用户编程提供了方便。空间的分配细节，从而为用户编程提供了方便。内存扩充：由于物理内存的大小可能限制了大型作业或多个作业的并发执行，为了内存扩充：由于物理内存的大小可能限制了大型作业或多个作业的并发执行，为了满足用户的要求并改善系统性能，必须对内存加以扩充。但我们无须去真正地增加满足用户的要求并改善系统性能，必须对内存加以扩充。但我们无须去真正地增加内存空间，

7、而只须借助于虚拟存贮技术，便可获得这样地效果，使系统能运行内存内存空间，而只须借助于虚拟存贮技术，便可获得这样地效果，使系统能运行内存要求量远比物理内存大得多得作业，或让更多得作业并发执行。要求量远比物理内存大得多得作业，或让更多得作业并发执行。3.3.设备管理设备管理1)1)设备管理的主要任务设备管理的主要任务:为用户程序分配为用户程序分配 I/OI/O 设备；设备；完成用户程序请求的完成用户程序请求的 I/OI/O 操作；操作；提高提高 CPUCPU 和和 I/OI/O 设备的利用率；设备的利用率；改善人机界面。改善人机界面。2)2)设备管理程序应具有的功能设备管理程序应具有的功能缓冲管理

8、：几乎所有的外围设备于处理机交换信息时，都要利用缓冲来缓和缓冲管理：几乎所有的外围设备于处理机交换信息时，都要利用缓冲来缓和CPUCPU 和和I/OI/O 设备间速度不匹配的矛盾，设备间速度不匹配的矛盾，和提高和提高 CPUCPU 与设备、与设备、设备与设备间操作的并行程度，设备与设备间操作的并行程度，以提高以提高 CPUCPU 和和 I/OI/O 设备的利用率。设备的利用率。设备分配：系统根据用户所请求的设备类型和所采用的分配算法对设备进行分配，设备分配：系统根据用户所请求的设备类型和所采用的分配算法对设备进行分配，并将未获得所需设备的进程放进相应设备的等待队列。并将未获得所需设备的进程放进

9、相应设备的等待队列。设备处理：启动指定的设备处理：启动指定的 I/OI/O 设备，完成用户规定的设备，完成用户规定的 I/OI/O 操作，并对由设备发来的中操作，并对由设备发来的中断请求进行及时响应，根据中断类型进行相应的处理。断请求进行及时响应，根据中断类型进行相应的处理。虚拟设备功能：通常，把一次仅允许一个进程使用的设备称为独占设备。系统可通虚拟设备功能：通常，把一次仅允许一个进程使用的设备称为独占设备。系统可通过某种技术使该设备成为能被多个用户共享的设备，以提高设备利用率及加速程序过某种技术使该设备成为能被多个用户共享的设备，以提高设备利用率及加速程序的执行过程。可使每个用户都感觉到自己

10、在独占该设备。的执行过程。可使每个用户都感觉到自己在独占该设备。4.4.文件管理文件管理文件存储空间的管理文件存储空间的管理目录管理目录管理文件读、写管理文件读、写管理文件保护文件保护向用户提供接口向用户提供接口5.5.作业管理作业管理1 1作业管理的主要任务作业管理的主要任务:是根据系统条件和用户需要，对作业的运行进行合理的组织、调是根据系统条件和用户需要，对作业的运行进行合理的组织、调度及相应的控制。度及相应的控制。2 2作业调度：作业调度是指根据系统的能力和当前作业的运行情况，按一定策略，从后备作业调度：作业调度是指根据系统的能力和当前作业的运行情况，按一定策略，从后备作业队列中选出一批

11、作业，为它们分配所需的作业队列中选出一批作业，为它们分配所需的 I/OI/O 设备和存储空间，将它们调入内存并为设备和存储空间，将它们调入内存并为之建立相应的进程，使之成为具有获得处理机资格的侯选进程。之建立相应的进程，使之成为具有获得处理机资格的侯选进程。3 3作业控制：作业控制是指作业从进入系统开始，直到运行完成的整个过程中，用户可通作业控制：作业控制是指作业从进入系统开始，直到运行完成的整个过程中，用户可通过某种形式向系统发出各种命令，以对自己的作业进行控制和管理。过某种形式向系统发出各种命令，以对自己的作业进行控制和管理。进程状态转换条件进程状态转换条件在进程运行过程中，由于自身进展情

12、况及外界环境的变化，这三种基本状态可以依据一定在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：的条件相互转换：就绪就绪-运行运行 调度程序选择一个新的进程运行调度程序选择一个新的进程运行运行运行-就绪就绪 运行进程用完了时间片运行进程用完了时间片 运行进程被中断，因为一高优先级进程处于就绪状态运行进程被中断，因为一高优先级进程处于就绪状态运行运行-等待等待 当一进程必须等待时当一进程必须等待时OSOS 尚未完成服务尚未完成服务对一资源的访问尚不能进行对一资源的访问尚不能进行初始化初始化 I/OI/O 且必须等待结果且必须等待结果等待某一进程提供输入

13、等待某一进程提供输入(IPC)(IPC)等待等待-就绪就绪 当所等待的事件发生时当所等待的事件发生时其他状态其他状态创建状态创建状态终止状态终止状态挂起状态挂起状态调节负载，对换，父进程，操作系统，终端用户调节负载，对换，父进程，操作系统，终端用户创建创建(新新 new)new)状态状态 OSOS 已完成为创建一进程所必要的工作已完成为创建一进程所必要的工作已构造了进程标识符已构造了进程标识符已创建了管理进程所需的表格已创建了管理进程所需的表格 但还没有允许执行该进程但还没有允许执行该进程(尚未同意尚未同意)因为资源有限因为资源有限终止退出终止退出 exit)exit)状态状态 中止后进程移入

14、该状态中止后进程移入该状态 它不再有执行资格它不再有执行资格 表格和其它信息暂时由辅助程序保留表格和其它信息暂时由辅助程序保留例子例子:为处理用户帐单而累计资源使用情况的财务程序为处理用户帐单而累计资源使用情况的财务程序当数据不再需要后，进程当数据不再需要后，进程(和它的表格和它的表格)被删除被删除五状态进程模型五状态进程模型七状态进程模型七状态进程模型阻塞阻塞-阻塞挂起阻塞挂起 当所有进程都阻塞，当所有进程都阻塞，OSOS 会安排空间让一就绪进程进入内存会安排空间让一就绪进程进入内存阻塞挂起阻塞挂起-就绪挂起就绪挂起 当等待的事件发生时当等待的事件发生时(状态信息已在状态信息已在 OSOS

15、中中)就绪挂起就绪挂起-就绪就绪 当内存中没有就绪进程时当内存中没有就绪进程时就绪就绪-就绪挂起就绪挂起(较少见较少见)当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时进程控制块进程控制块PCBPCB系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。进程运行所需的全部信息。系统利用系统利用 PCBPCB 来控制和管理进程，所以来控制和管理进程，所以 PCBPCB 是系统感知进程存在的唯一标志是系统感知进程存在的

16、唯一标志进程与进程与 PCBPCB 是一一对应的是一一对应的进程控制块的内容进程控制块的内容进程标识符：标识一个进程的编号，也称为进程的内部名；进程标识符：标识一个进程的编号，也称为进程的内部名；现性状态：说明进程的当前状态；现性状态：说明进程的当前状态；现场保留区：保存进程由执行状态变为其它状态时的现场保留区：保存进程由执行状态变为其它状态时的 CPUCPU 现场信息；现场信息；程序与数据地址：该进程的程序和数据所在位置信息；程序与数据地址：该进程的程序和数据所在位置信息；互斥与同步机构：实现进程间互斥与同步时所必须的机构；互斥与同步机构：实现进程间互斥与同步时所必须的机构；进程通信机制：用

17、于实现进程间的通信所需的数据结构；进程通信机制：用于实现进程间的通信所需的数据结构；优先级：表示进程使用优先级：表示进程使用 CPUCPU 时优先级别的一个整数；时优先级别的一个整数；资源清单：列出进程拥有的资源的记录；资源清单：列出进程拥有的资源的记录；连接字：给出本进程所在队列中的下一个进程的连接字：给出本进程所在队列中的下一个进程的 PCBPCB 首址；首址；家族联系：用于说明本进程与其它家族成员间的关系。家族联系：用于说明本进程与其它家族成员间的关系。进程映象进程映象(进程要素进程要素)用户程序用户程序用户数据用户数据栈栈 用于过程调用和参数传递用于过程调用和参数传递进程控制块进程控制

18、块 PCB(PCB(执行上下文执行上下文)控制进程所需的数据控制进程所需的数据(进程属性进程属性)，包括，包括:进程标识符信息进程标识符信息处理器状态信息处理器状态信息进程控制信息进程控制信息进程控制块的组织方式进程控制块的组织方式为了有效地对进程控制块进行管理，应该采用适当的方式把它们组织起来。为了有效地对进程控制块进行管理，应该采用适当的方式把它们组织起来。目前常用的组织方式有以下两种：目前常用的组织方式有以下两种：按链接方式组织按链接方式组织 PCB(PCB(队列队列)不同状态进程分别组成队列不同状态进程分别组成队列运行队列、就绪队列、等待队列运行队列、就绪队列、等待队列按索引方式组织按

19、索引方式组织 PCB(PCB(表表)对具有相同状态的进程，分别设置各自的对具有相同状态的进程，分别设置各自的 PCBPCB 索引表，说明索引表，说明 PCBPCB 在在 PCBPCB 表中的地址表中的地址其他方式：线性表或链表其他方式：线性表或链表为什么要线程的引入为什么要线程的引入在操作系统中，进程的引入提高了电脑资源的利用效率。但在进一步提高进程的并在操作系统中，进程的引入提高了电脑资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制限制线程的引入正是为了简

20、化进程间的通信，以小的开销来提高进程内的并发程度线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度信号量的物理含义：信号量的物理含义：信号量信号量 S S0 0 时，时，S S 的数值表示某类可用资源的数目，的数值表示某类可用资源的数目，执行执行 P P 操作意味着申请分配一个单操作意味着申请分配一个单位的资源；当位的资源；当 S S0 0 时，表示无资源可用，此时时，表示无资源可用，此时S S 的绝对值表示信号量的绝对值表示信号量 S S 的阻塞队列中的进的阻塞队列中的进程数。执行程数。执行 V V 操作意味着释放一个单位的资源。操作意味着释放一个单位的资源。S0 S0 表

21、示有表示有 S S 个资源可用个资源可用 S=0 S=0 表示无资源可用表示无资源可用 S0 S0 则则|S|S|表示表示 S S 等待队列中的进程个数等待队列中的进程个数 P(S):P(S):表示申请一个资源表示申请一个资源 V(S)V(S)表示释放一个资源。信号量的初值应该大于等于表示释放一个资源。信号量的初值应该大于等于 0 0处理机调度的基本概念处理机调度的基本概念在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配

22、处理机的任按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。务是由进程调度程序完成的。它是操作系统设计的中心问题之一。分时系统和实时系统的区别。各有什么特点？各自采用什么调度算法？分时系统和实时系统的区别。各有什么特点？各自采用什么调度算法？分时系统分时系统:时间片轮转调度算法时间片轮转调度算法实时系统实时系统:在实时系统中在实时系统中,硬实时任务和軟实時任務都聯系着一個截止時間硬实时任务和軟实時任務都聯系着一個截止時間.1)1)非抢占式调度算法非抢占式调度算法:非抢占式轮转调度算法非抢占式轮转调度算法非抢占

23、式优先调度算法非抢占式优先调度算法2)2)抢占式调度算法抢占式调度算法:基于时钟中断的抢占优先调度算法基于时钟中断的抢占优先调度算法立即抢占优先权调度算法。立即抢占优先权调度算法。周转时间：作业从提交到完成得到结果所经历的时间。包括：在收容队列中等待，周转时间：作业从提交到完成得到结果所经历的时间。包括：在收容队列中等待，CPUCPU上执行，就绪队列和阻塞队列中等待，结果输出等待上执行，就绪队列和阻塞队列中等待，结果输出等待响应比响应比:(:(等待時間等待時間+要求服務時間要求服務時間)/)/要求服務時間要求服務時間产生死锁的原因产生死锁的原因1.1.竞争系统资源竞争系统资源2.2.进程的推进

24、顺序不当进程的推进顺序不当产生死锁的必要条件产生死锁的必要条件互斥条件资源独占互斥条件资源独占请求和保持条件部分分配，占有申请请求和保持条件部分分配，占有申请不剥夺条件不可强占不剥夺条件不可强占环路等待条件。环路等待条件。预防死锁的方法预防死锁的方法破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一 1)1)资源一次性分配；资源一次性分配；(破坏请求和保持条件破坏请求和保持条件)2)2)可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源(破坏不可剥夺条件破坏不可剥夺条件)3)3)资源有序分配法；做法：系统给每类资源赋予一个

25、编号，每一个进程按编号递增的顺资源有序分配法；做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反序请求资源，释放则相反(破坏环路等待条件破坏环路等待条件)死锁防止死锁防止死锁防止定义死锁防止定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，进行动态检查，并根据检查结果断定是否分配资源，并根据检查结果断定是否分配资源，假设分配后系统可能发生死锁，假设分配后系统可能发生死锁，则不予分配，否则予以分配。则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱

26、的限制，从而获预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来防止死锁。得较满意得系统性能来防止死锁。由于在防止死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配由于在防止死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。假设此次分配不会导致系统进入不安全状态，则之前预先计算资源分配的安全性。假设此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的防止死锁算法是银行家将资源分配给进程；否则，进程等待。其中最具有代表性的防止死锁算法是银行家算法。算法。死锁的解除

27、死锁的解除重要的是以最小的代价恢复系统的运行。方法如下：重要的是以最小的代价恢复系统的运行。方法如下：1 1重新启动重新启动 2 2撤消进程撤消进程 3 3剥夺资源剥夺资源 4 4进程回退进程回退虚拟存储器的基本思想是：虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换.虚拟存储器支持虚拟存储器支持多道程序设计技术多道程序设计技术虚拟存储器

28、虚拟存储器具有请求调入功能和自换功能具有请求调入功能和自换功能,能从逻辑上对内存容量进行扩充的存储器系统。虚能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储器就是一个地址空间，且具有比实存大得多的容量。拟存储器就是一个地址空间，且具有比实存大得多的容量。对用户：指令地址部分所限定的比实存大得多的地址实间。对用户：指令地址部分所限定的比实存大得多的地址实间。对系统：借助于各种表格机构，表达虚拟实间。对系统：借助于各种表格机构，表达虚拟实间。虚拟存储器的容量虚拟存储器的容量一个虚拟存储器的最大容量是由电脑的地址结构确定的。如：假设一个虚拟存储器的最大容量是由电脑的地址结构确定的。如：假设CPUC

29、PU 的有效地址的有效地址长度为长度为 3232 位，则程序可以寻址范围是位，则程序可以寻址范围是 0 0(232)-1(232)-1，即虚存容量为，即虚存容量为 4GB 4GB。虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。和所确定。页面置换算法页面置换算法当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。置换算法。最正确置换算法最正确置换算法先进先出置换算法先进先出置换算法最近

30、最久未用置换算法最近最久未用置换算法近似的近似的 LRULRU 算法算法NRUNRU 算法算法最正确置换算法最正确置换算法最正确置换算法是由最正确置换算法是由 BeladyBelady 于于 19661966 年提出的一种理论上的算法。年提出的一种理论上的算法。其所选择的被淘汰其所选择的被淘汰页面，将是以后永不使用的，页面，将是以后永不使用的，或许是在最长或许是在最长(未来未来)时间内不再被访问的页面。采用最正确时间内不再被访问的页面。采用最正确置换算法，通常可保证获得最低的缺页率。置换算法，通常可保证获得最低的缺页率。先进先出先进先出(FIFO)(FIFO)页面置换算法页面置换算法置换时置换

31、时 选择在内存中驻留时间最长的页并淘汰之选择在内存中驻留时间最长的页并淘汰之最近最久未使用最近最久未使用(LRU)(LRU)置换算法置换算法选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高时间戳或硬件方法长的页。实现代价很高时间戳或硬件方法LRULRU 置换算法的硬件支持置换算法的硬件支持 1)1)寄存器寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为位寄存器，

32、可表示为:R=R:R=Rn-1n-1R Rn-2n-2R Rn-3n-3 R R2 2R R1 1R R0 02)2)栈栈改良型改良型 ClockClock 置换算法置换算法由访问位由访问位 A A 和修改位和修改位 M M 可以组合成下面四种类型的页面：可以组合成下面四种类型的页面：1 1 类类(A=0,M=0):(A=0,M=0):表示该页最近既未被访问，表示该页最近既未被访问，又未被修改，又未被修改，是最正确淘汰页。是最正确淘汰页。2 2 类类(A=0,M=1)(A=0,M=1)：表示该页最近未被访问，表示该页最近未被访问，但已被修改，但已被修改，并不是很好的淘汰页。并不是很好的淘汰页。

33、3 3 类类(A=1,M=0)(A=1,M=0)：最近已被访问，最近已被访问，但未被修改，但未被修改，该页有可能再被访问。该页有可能再被访问。4 4 类类(A=1,M=1):(A=1,M=1):最近已被访问且被修改，最近已被访问且被修改，该页可能再被访问。该页可能再被访问。其执行过程可分成以下三步：其执行过程可分成以下三步：(1)(1)从指针所指示的当前位置开始，从指针所指示的当前位置开始，扫描循环队列，扫描循环队列，寻找寻找 A=0A=0 且且 M=0M=0 的第一类页的第一类页面，面，将所遇到的第一个页面作为所选中的淘汰页。将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问

34、位在第一次扫描期间不改变访问位 A A。(2)(2)如果第一步失败，即查找一周后未遇到第一类页面，如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻则开始第二轮扫描，寻找找 A=0A=0 且且 M=1M=1 的第二类页面，的第二类页面，将所遇到的第一个这类页面作为淘汰页。将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，在第二轮扫描期间，将所有扫描过的页面的访问位都置将所有扫描过的页面的访问位都置 0 0。(3)(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复将所有

35、的访问位复 0 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。能找到被淘汰的页。其它置换算法其它置换算法1.1.最少使用最少使用(LFU(LFU：Least Frequently Used)Least Frequently Used)置换算法置换算法2.2.页面缓冲算法页面缓冲算法(PBA(PBA：Page Buffering Algorithm)Page Buffering Algorithm)与设备无关性设备独立性与设备无关性设备独立性用户在编制程序时，使用逻辑设备名，由系统实现从逻辑设备到物理设备

36、的转换用户在编制程序时，使用逻辑设备名，由系统实现从逻辑设备到物理设备的转换用户能独立于具体物理设备而方便的使用设备用户能独立于具体物理设备而方便的使用设备用户申请使用设备时，只需要指定设备类型，而无须指定具体物理设备，系统根据用户申请使用设备时，只需要指定设备类型，而无须指定具体物理设备，系统根据当前的请求，及设备分配的情况，在相同类别设备中，选择一个空闲设备，并将其当前的请求，及设备分配的情况，在相同类别设备中，选择一个空闲设备，并将其分配给一个申请进程分配给一个申请进程引入缓冲技术引入缓冲技术1.1.緩和緩和 CPUCPU 與與 I/OI/O 設備間速度不匹配的矛盾設備間速度不匹配的矛盾

37、.2.2.减少對减少對 CPUCPU 的中斷頻率的中斷頻率,放寬對放寬對 CPUCPU 中斷响應時間的限制中斷响應時間的限制.3.3.提高提高 CPUCPU 和和 I/OI/O 設備之間并行性設備之間并行性.磁盘查找算法磁盘查找算法1.(First-Come,First Served)1.(First-Come,First Served)FCFSFCFS 调度算法调度算法2.2.最短寻道时间优先最短寻道时间优先 SSTF(Shortest Seek Time First)SSTF(Shortest Seek Time First)3.3.扫描扫描(SCAN)(SCAN)算法算法优先考虑磁頭當前

38、的移動方向优先考虑磁頭當前的移動方向,在移動方向上沒有更外的的磁道需要訪問時在移動方向上沒有更外的的磁道需要訪問時,才輚換磁才輚換磁臂的移動方向臂的移動方向4.4.循环扫描循环扫描(CSCAN)(CSCAN)算法算法磁頭單向移動磁頭單向移動,當磁頭到最外的磁首并訪問後當磁頭到最外的磁首并訪問後,磁頭立即返回到最里的欲訪問的磁道磁頭立即返回到最里的欲訪問的磁道.5.N-Step-SCAN5.N-Step-SCAN 和和 FSCANFSCAN 调度算法调度算法N N 步步 SCANSCAN 算法是将磁盘请求队列分成假设干个长度为算法是将磁盘请求队列分成假设干个长度为 N N 的子队列的子队列,磁盘

39、调度将按磁盘调度将按 FCFSFCFS算法依次处理这些子队列。而每处理一个队列时又是按算法依次处理这些子队列。而每处理一个队列时又是按 SCANSCAN 算法，对一个队列处理完后，算法，对一个队列处理完后，再处理其他队列再处理其他队列6.6.FSCANFSCAN 算法算法FSCANFSCAN 只将磁盘请求队列分成两个子队列。只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘一个是由当前所有请求磁盘 I/OI/O 的进程形成的进程形成的队列，由磁盘调度按的队列，由磁盘调度按 SCANSCAN 算法进行处理。算法进行处理。虚拟设备概念虚拟设备概念虚拟设备技术：虚拟设备技术：把一台慢速的以独占

40、方式工作的物理设备，通过快速的以共享方式把一台慢速的以独占方式工作的物理设备，通过快速的以共享方式工作的设备改造成假设干台虚拟的同类设备的技术。即通过高速共享设备来模拟独占型设工作的设备改造成假设干台虚拟的同类设备的技术。即通过高速共享设备来模拟独占型设备的动作，将其改造为共享设备提高设备利用率和系统的效率的技术。备的动作，将其改造为共享设备提高设备利用率和系统的效率的技术。实现虚拟设备的必要条件实现虚拟设备的必要条件:SpoolingSpooling 系统系统加快目录检索的方法加快目录检索的方法1 1指定当前目录，使查找操作从当前目录开始往下进行，缩小了搜索范围。指定当前目录，使查找操作从当

41、前目录开始往下进行，缩小了搜索范围。2 2建立活动或打开文件表，使查找操作不必在磁盘上进行，而是在内存中进行。建立活动或打开文件表，使查找操作不必在磁盘上进行，而是在内存中进行。位示图位示图用来反映磁盘文件存储器存储块的使用情况，故又称盘图。它由假设干字节组成，每位对用来反映磁盘文件存储器存储块的使用情况，故又称盘图。它由假设干字节组成，每位对应一个物理块。当其值为应一个物理块。当其值为 1 1 时，表示已分配；为时，表示已分配；为 0 0 时表示空闲时表示空闲分配分配:b=n(i-1)+jb=n(i-1)+jn n 為每行的位數為每行的位數回收回收i=(b-1)DIV n+1i=(b-1)DIV n+1j=(b-1)mod n+1j=(b-1)mod n+1UNIXUNIX 的混合索引方式的混合索引方式所謂混合索引文件結构所謂混合索引文件結构,提指文件的物理結构可能包括多種索引文件結构形式提指文件的物理結构可能包括多種索引文件結构形式,如單級如單級索引文件結构索引文件結构,兩級索引文件結构和多級索引文件結构形式兩級索引文件結构和多級索引文件結构形式.這種物理結构既可提高對文件這種物理結构既可提高對文件的查詢速度的查詢速度,又能節省存放文件地址所需的空間又能節省存放文件地址所需的空間.