蒲晓蓉_操作系统原理第3_3章_存储管理)

1、3.5 虚拟存储管理技术虚拟存储管理技术 简单存储：要求将一个进程所需的程序和数据简单存储：要求将一个进程所需的程序和数据全部装入内存方可执行。全部装入内存方可执行。 这样的系统存在两个很严重的问题。这样的系统存在两个很严重的问题。 其一，对于大进程，如果其所需内存空间超过了内存其一，对于大进程，如果其所需内存空间超过了内存的最大容量，则无法运行。的最大容量，则无法运行。 其二，对于多道程序系统，由于每一个进程需要全部其二，对于多道程序系统，由于每一个进程需要全部装入内存，使同时驻留内存的进程数量受到限制。虽装入内存，使同时驻留内存的进程数量受到限制。虽然也可以通过提高内存容量来解决，但是代价

2、太高。然也可以通过提高内存容量来解决，但是代价太高。 如果能将一部分价格较低的外存空间当作内存如果能将一部分价格较低的外存空间当作内存使用，从逻辑上扩充内存容量。那么，将获得使用，从逻辑上扩充内存容量。那么，将获得更高的性价比。更高的性价比。虚拟存储技术的理论依据虚拟存储技术的理论依据 程序执行的局部性原理：程序的执行总是呈现程序执行的局部性原理：程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。储空间也局限于某个区域。 因此，只要保证进程执行

3、所需的部分程序和数因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。据驻留在内存，一段时间内进程都能顺利执行。实现虚拟存储的一般过程实现虚拟存储的一般过程 进程运行之前，仅需要将一部分页面或段装入进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁内存，便可启动运行，其余部分暂时保留在磁盘上。盘上。 进程运行时，如果它所需要访问的页面（段）进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；已经装入内存，则可以继续执行下去； 如果其所需要访问的页面（段）尚未装入内存，如果其所需要访问的页面（段）尚未装入内存，则发

4、生缺页（段）中断，进程阻塞。则发生缺页（段）中断，进程阻塞。 此时，系统将启动请求调页（段）功能，将进此时，系统将启动请求调页（段）功能，将进程所需的页（段）装入内存。程所需的页（段）装入内存。实现虚拟存储的一般过程实现虚拟存储的一般过程 如果当前内存已满，无法装入新的页如果当前内存已满，无法装入新的页（段），则还需要利用页（段）置换功（段），则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。到磁盘上，以腾出足够的内存空间。 再将进程所需的页（段）装入内存，唤再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与

5、调度执行。醒阻塞的进程，使之重新参与调度执行。 从外存装入页从外存装入页/段段更新页更新页/段表段表交换页交换页/段段内存满内存满？是是否否缺页缺页/段中断段中断页页/段段在内存在内存是是否否进程执行进程执行图图3.28 实现虚拟存储的典型过程实现虚拟存储的典型过程什么是虚拟存储什么是虚拟存储 通过系统提供的缺页通过系统提供的缺页/段中断功能和交换技术，段中断功能和交换技术，动态装入进程的程序代码和数据，使得一个大动态装入进程的程序代码和数据，使得一个大的用户程序能在一个相对较小的内存空间中运的用户程序能在一个相对较小的内存空间中运行，也使得有限的内存能同时容纳更多的进程。行，也使得有限的内存

6、能同时容纳更多的进程。 习惯上，人们把这种用户感觉上的、由实际内习惯上，人们把这种用户感觉上的、由实际内存和部分外存共同构成的存储空间称为存和部分外存共同构成的存储空间称为虚拟存虚拟存储器储器虚拟存储技术的技术支持虚拟存储技术的技术支持 首先，必须有相应的硬件支持，用以实首先，必须有相应的硬件支持，用以实现虚拟分页或虚拟分段存储管理。现虚拟分页或虚拟分段存储管理。 其次，操作系统必须提供相应的软件支其次，操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移持，管理页或段在内存和外存之间的移动。动。虚拟存储的基本数据结构虚拟存储的基本数据结构 由于虚拟存储系统中，进程的程序代码和数据由

7、于虚拟存储系统中，进程的程序代码和数据只有一部分在内存，另一部分保存在外存。只有一部分在内存，另一部分保存在外存。 在页在页/段表项中增加一个段表项中增加一个“存在存在”字段，其值字段，其值为为0或或1。 增加一个增加一个“修改修改”字段，表明对应页字段，表明对应页/段自进段自进入内存以来是否被修改过。只有被修改过的页入内存以来是否被修改过。只有被修改过的页/段才需要保存到外存，若需要将未修改过的段才需要保存到外存，若需要将未修改过的页页/段换出内存，只需要将新装入的页段换出内存，只需要将新装入的页/段直接段直接覆盖其存储区域，而不必将其内容保存到外存。覆盖其存储区域，而不必将其内容保存到外存

8、。 图图3.29 虚拟分页、分段及段页式存储系统的数据结构虚拟分页、分段及段页式存储系统的数据结构页号页号页框号页框号存在存在修改修改其他控制其他控制(a) 虚拟存储页表项虚拟存储页表项段号段号段长段长存在存在修改修改其他控制其他控制(b) 虚拟存储段表项虚拟存储段表项段基址长段基址长(c) 虚拟存储段页式系统的段表项和页表项虚拟存储段页式系统的段表项和页表项段号段号其他控制其他控制页表长度页表长度页表基址页表基址段表项段表项页号页号页框号页框号存在存在修改修改其他控制其他控制页表项页表项虚拟存储的好处虚拟存储的好处 第一，可以运行大程序，包括超过内存第一，可以运行大程序，包括超过内存实际容量

9、的大程序。实际容量的大程序。 第二，可以在有限的物理内存中运行更第二，可以在有限的物理内存中运行更多的程序。多道程序系统的度不再受到多的程序。多道程序系统的度不再受到物理内存空间的限制。物理内存空间的限制。虚拟存储的典型问题虚拟存储的典型问题抖动（抖动（thrashing） 当进程要求装入新的页面或程序段时，如果当当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。被进程使用，则又需要将其换入内存。 如果系统花费大

10、量的时间把程序和数据频繁地如果系统花费大量的时间把程序和数据频繁地装入和移出内存而不是执行用户指令，那么，装入和移出内存而不是执行用户指令，那么，称系统出现了称系统出现了抖动抖动。出现抖动现象时，系统显。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。得非常繁忙，但是吞吐量很低，甚至产出为零。 根本原因：选择的页面或段不恰当。根本原因：选择的页面或段不恰当。虚拟存储分页技术虚拟存储分页技术 建立在简单分页存储管理系统之上，是建立在简单分页存储管理系统之上，是目前常用的一种虚拟存储管理技术。目前常用的一种虚拟存储管理技术。地址变换地址变换 基于简单存储分页系统增加了某些功能，如产

11、基于简单存储分页系统增加了某些功能，如产生和处理缺页中断，以及从内存中换出页面等。生和处理缺页中断，以及从内存中换出页面等。 进程执行时，首先通过根据逻辑地址中的页号，进程执行时，首先通过根据逻辑地址中的页号，查找查找快表快表中是否存在对应的页表项。若快表中中是否存在对应的页表项。若快表中不存在该页表项，则再查找不存在该页表项，则再查找页表页表。检查对应的。检查对应的页面是否在内存中存在。若该页面页面是否在内存中存在。若该页面不在内存不在内存，启动启动缺页中断处理缺页中断处理例程，装入需要的页面，并例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将更新页表和快表。若该页面已经在内

12、存中，将对应的页表项插入快表中，对应的页表项插入快表中，更新快表更新快表。若快表。若快表中存在该表项，则直接取出其中的中存在该表项，则直接取出其中的页框号，加页框号，加上页内偏移量，计算出物理地址上页内偏移量，计算出物理地址。 访问页表访问页表图图3.30 虚拟存储分页系统地址变换过程虚拟存储分页系统地址变换过程物理地址物理地址页框号页框号 偏移量偏移量更新快表更新快表页号页号 偏移量偏移量逻辑地址逻辑地址检索快表检索快表是是否否是是否否换出页面换出页面处理机处理中断处理机处理中断是是否否处理机从外存取该页处理机从外存取该页将该页装入内存将该页装入内存更新页表更新页表缺页中断处理缺页中断处理？

13、命中？命中？内存满？内存满？页在内存？页在内存缺页中断处理过程缺页中断处理过程（1）操作系统接收到进程产生的缺页中断信号，启动中）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；断处理例程，保留处理机现场；（2）操作系统通知处理机从外存读取指定的页面；）操作系统通知处理机从外存读取指定的页面；（3）处理机激活）处理机激活I/O设备；设备；（4） 检查内存有无足够的空闲空间装入该页面？若有，检查内存有无足够的空闲空间装入该页面？若有，转（转（6），否则，执行（），否则，执行（5）；）；（5） 利用页面置换算法，选择内存中的某个页面，换利用页面置换算法，选择内存中的某个页面

14、，换出内存；出内存；（6） 将指定页面从外存装入内存；将指定页面从外存装入内存；（7） 更新该进程的页表；更新该进程的页表；（8） 更新快表；更新快表；（9）计算物理地址。）计算物理地址。 虚拟存储分段技术虚拟存储分段技术 建立在简单存储分段系统基础上，利用动态分建立在简单存储分段系统基础上，利用动态分区技术分配存储空间，并以段作为交换的单位。区技术分配存储空间，并以段作为交换的单位。 进程执行之前，系统为之分配几个必要的内存进程执行之前，系统为之分配几个必要的内存分区，每一个分区中装入一段。分区，每一个分区中装入一段。 当进程执行过程中，出现缺段中断时，操作系当进程执行过程中，出现缺段中断时

15、，操作系统将为进程装入需要的程序段。统将为进程装入需要的程序段。虚拟存储分段：数据结构虚拟存储分段：数据结构 因此，需要修改段表，增加因此，需要修改段表，增加“存在存在”字字段和段和“修改修改”字段，分别标明对应段是字段，分别标明对应段是否存在于内存，以及内存中的段自装入否存在于内存，以及内存中的段自装入以来是否被修改过。以来是否被修改过。地址变换与存储保护地址变换与存储保护 在简单分段系统的地址变换机构基础上形成的。在简单分段系统的地址变换机构基础上形成的。 越界检查越界检查：可能产生一个地址越界中断，进入：可能产生一个地址越界中断，进入相应的中断处理例程执行。一般地，当地址越相应的中断处理

16、例程执行。一般地，当地址越界中断处理完毕，该进程将异常结束。界中断处理完毕，该进程将异常结束。 操作合法性检查操作合法性检查：如果属于非法操作，产生非：如果属于非法操作，产生非法访问中断，这时也会让进程异常终止。法访问中断，这时也会让进程异常终止。 缺段处理缺段处理：执行进程被阻塞。并产生一个中断：执行进程被阻塞。并产生一个中断信号，处理机执行缺段中断处理例程。信号，处理机执行缺段中断处理例程。图图3.31 虚拟存储分段系统地址变换过程虚拟存储分段系统地址变换过程物理地址物理地址段基址段基址 偏移量偏移量更新快表更新快表否否非法访问中断非法访问中断是是是是否否是是越界中断处理越界中断处理访问段

17、表访问段表段号段号 偏移量偏移量逻辑地址逻辑地址检索快表检索快表否否是是缺段中断处理缺段中断处理否否更新段表更新段表？命中？命中？段在内存？段在内存？地址越界？地址越界？合法访问？合法访问图图3.31 虚拟存储分段系统中的缺段中断的处理过程虚拟存储分段系统中的缺段中断的处理过程换出一个或几个段换出一个或几个段形成一个合适空闲区形成一个合适空闲区返回返回修改段表、空闲分区表修改段表、空闲分区表从外存读入段从外存读入段s唤醒进程唤醒进程是是拼接外零头，形成拼接外零头，形成一个合适的空闲区一个合适的空闲区是是段段s不在内存不在内存阻塞执行进程阻塞执行进程内存中有合内存中有合适的空闲区适的空闲区吗？吗

18、？否否空闲区容量空闲区容量总和能否满总和能否满足？足？否否虚拟存储段页式技术虚拟存储段页式技术 虚拟存储段页式系统中，程序和数据通常以页虚拟存储段页式系统中，程序和数据通常以页面为单位被系统装入和移出内存。面为单位被系统装入和移出内存。 因此，一般不需要在段表项中增加因此，一般不需要在段表项中增加“存在存在”字字段和段和“修改修改”字段，而将它们放在页表中。字段，而将它们放在页表中。 段表中需要保留基于段的保护与存储共享等目段表中需要保留基于段的保护与存储共享等目的的存取控制信息，页表中设置基于页的控制的的存取控制信息，页表中设置基于页的控制信息。信息。 地址变换地址变换 首先，通过根据段号和

19、页号，查找首先，通过根据段号和页号，查找快表快表中是否中是否存在对应的页表项。存在对应的页表项。 若快表中不存在该页表项，则再查找若快表中不存在该页表项，则再查找段表段表。然。然后，检索段号对应的段表项，找到对应段的页后，检索段号对应的段表项，找到对应段的页表起始地址。表起始地址。 再根据页号检索该再根据页号检索该页表页表，检查对应页面是否在，检查对应页面是否在内存。若该页面内存。若该页面不在内存不在内存，启动，启动缺页中断缺页中断处理处理例程，装入需要的页面，并例程，装入需要的页面，并更新页表和快表更新页表和快表。若该页面已经在内存中，将对应的页表项插入若该页面已经在内存中，将对应的页表项插

20、入快表中，快表中，更新快表更新快表。 若快表中存在该表项，则直接取出其中的若快表中存在该表项，则直接取出其中的页框页框号，加上页内偏移量，计算出物理地址号，加上页内偏移量，计算出物理地址。 图图3.32 虚拟存储分页系统地址变换过程虚拟存储分页系统地址变换过程更新页表更新页表缺页中断处理缺页中断处理物理地址物理地址页框号页框号偏移量偏移量更新快表更新快表是是否否访问段表访问段表访问页表访问页表检索快表检索快表段号段号页内偏移量页内偏移量逻辑地址逻辑地址段内页号段内页号否否是是？命中？命中？页在内存？页在内存虚拟存储系统的软件策略虚拟存储系统的软件策略 现代操作系统几乎都采用虚拟存储管理系统现代

21、操作系统几乎都采用虚拟存储管理系统 一些特殊的操作系统和一些较老的操作系统没一些特殊的操作系统和一些较老的操作系统没有采用虚拟存储技术。例如，有采用虚拟存储技术。例如，MS DOS和早期和早期的的UNIX操作系统等。操作系统等。 大多采用分段与分页相结合的段页式管理系统。大多采用分段与分页相结合的段页式管理系统。 下面以分页存储管理为例，介绍虚拟存储系统下面以分页存储管理为例，介绍虚拟存储系统采用的软件策略。采用的软件策略。虚拟存储系统的软件策略虚拟存储系统的软件策略 驻 留 集 管 理驻 留 集 管 理 ( R e s i d e n t S e t Management) 放置策略放置策略

22、(Placement Policy) 获取策略获取策略(Fetch Policy) 置换策略置换策略(Replacement Policy) 清除策略清除策略(Cleaning Policy) 负载控制负载控制(Load Control)驻留集管理驻留集管理 进程的进程的驻留集驻留集指，虚拟存储系统中，每指，虚拟存储系统中，每个进程驻留在内存的页面集合，或进程个进程驻留在内存的页面集合，或进程分到的物理页框集合。分到的物理页框集合。 驻留集管理主要解决的问题是，系统应驻留集管理主要解决的问题是，系统应当为每个活跃进程分配当为每个活跃进程分配多少个页框多少个页框。影响页框分配的主要因素影响页框分

23、配的主要因素 分配给每个活跃进程的页框数分配给每个活跃进程的页框数越少越少，同，同时驻留内存的活跃进程数就时驻留内存的活跃进程数就越多越多，进程，进程调度程序能调度就绪进程的调度程序能调度就绪进程的概率就越大。概率就越大。然而，这将导致然而，这将导致进程发生缺页中断的进程发生缺页中断的概概率较大率较大； 为进程分配过多的页框，并不能显著地为进程分配过多的页框，并不能显著地降低其缺页中断率。降低其缺页中断率。 基本的驻留集管理策略基本的驻留集管理策略 固定分配策略固定分配策略(Fixed-Allocation Policy) 可变分配策略可变分配策略(Variable-Allocation Po

24、licy) 固定分配策略固定分配策略 为每个进程分配为每个进程分配固定数量固定数量的页框。即，的页框。即，每个活跃进程的驻留集尺寸在运行期间每个活跃进程的驻留集尺寸在运行期间固定不变固定不变。 为进程分配为进程分配多少个多少个页框是合理的呢？页框是合理的呢？ 可以由系统根据进程的类型确定，也可可以由系统根据进程的类型确定，也可以由编程人员或系统管理员指定。以由编程人员或系统管理员指定。可变分配策略可变分配策略 为每个活跃进程分配的页框数在进程的生命周为每个活跃进程分配的页框数在进程的生命周期内是期内是可变的可变的。即，系统可以首先给进程分配。即，系统可以首先给进程分配一定数量的页框。进程运行期

25、间，可以一定数量的页框。进程运行期间，可以增加或增加或减少减少页框。页框。 系统可以根据进程的系统可以根据进程的缺页率缺页率调整进程的驻留集调整进程的驻留集。 当进程的缺页率很高时，驻留集太小，需要当进程的缺页率很高时，驻留集太小，需要增加增加页框；页框； 当缺页率一段时间内都保持很低时，可以在不会当缺页率一段时间内都保持很低时，可以在不会明显增加进程缺页率的前提下，明显增加进程缺页率的前提下，回收回收其一部分页框，其一部分页框，减小进程的驻留集。减小进程的驻留集。可变分配可变分配 vs.固定分配固定分配 可变分配策略比固定分配策略更灵活，既可以可变分配策略比固定分配策略更灵活，既可以提高系统

26、的吞吐量，又能保证内存的有效利用。提高系统的吞吐量，又能保证内存的有效利用。 可变分配要求统计进程的缺页率，增加系统额可变分配要求统计进程的缺页率，增加系统额外开销。而准确判断进程缺页率的高低，确定外开销。而准确判断进程缺页率的高低，确定缺页率的阈值是非常困难的。缺页率的阈值是非常困难的。 可变分配策略不仅需要操作系统软件专门的支可变分配策略不仅需要操作系统软件专门的支持，而且，还需要处理机平台提供的硬件支持持，而且，还需要处理机平台提供的硬件支持页面放置策略页面放置策略 解决的问题：系统应当在内存的解决的问题：系统应当在内存的什么位置什么位置为活为活跃进程分配页框？跃进程分配页框？ 一般地，

27、对于一个分页系统或段页式系统，将一般地，对于一个分页系统或段页式系统，将进程的一个页面装入哪一个页框进程的一个页面装入哪一个页框无关紧要无关紧要。 对于分段系统，对于分段系统，需要考虑需要考虑将一个程序段装入哪将一个程序段装入哪一个合适的分区中，可采用的分配算法包括首一个合适的分区中，可采用的分配算法包括首次适应法、下次适应法、最佳适应法或最差适次适应法、下次适应法、最佳适应法或最差适应法等。应法等。页面获取策略页面获取策略 解决的问题：系统应当在解决的问题：系统应当在何时何时把一个页把一个页面装入内存？面装入内存？ 请求调页请求调页 (Demand Paging) 预调页预调页 (Prepa

28、ging)请求调页请求调页 仅当进程执行过程中，通过检查页表发现相应仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。页面不在内存时，才装入该页面。 当进程刚开始执行时，由于预先未装入进程的当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。时间以后，进程的缺页率将下降。 采用请求调页方式，一次装入请求的一个页面，采用请求调页方式，一次装入请求的一个页面，磁盘磁盘I/O的启动频率较高，系统的开销较大。的启动频率较高，系统的开销较大。预调页方式预调页方式 当进程创建时，预先为进程

29、装入多个页面。当进程创建时，预先为进程装入多个页面。 缺页中断时，系统为进程装入指定的页面以及缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。与之相临的多个页面。 若局部性很差，预先装入的很多页面不会很快若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低被引用，并会占用大量的内存空间，反而降低系统的效率系统的效率页面置换策略页面置换策略 当发生缺页中断且无足够的内存空间时，需要当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。置换已有的某些（个）页面。 应该解决的基本问题：应该解决的基本问题： 当系统欲把一个页面装入内存时，应当在当系统

30、欲把一个页面装入内存时，应当在什么范围什么范围内判断已经没有空闲页框供分配？内判断已经没有空闲页框供分配？ 当指定的范围内没有空闲页框时，应当从当指定的范围内没有空闲页框时，应当从指定的范围内选择指定的范围内选择哪个页面哪个页面移出内存？移出内存？ 局部置换策略局部置换策略 可以采用可以采用局部置换局部置换或或全局置换全局置换策略。策略。 局部置换局部置换：系统在进程：系统在进程自身的驻留集中自身的驻留集中判断当前是否存在空闲页框，并在其中判断当前是否存在空闲页框，并在其中进行置换。进行置换。全局置换策略全局置换策略 在在整个内存空间内整个内存空间内判断有无空闲页框，判断有无空闲页框，并允许从

31、其它进程的驻留集中选择一个并允许从其它进程的驻留集中选择一个页面换出内存。页面换出内存。分配模式分配模式 vs. 置换模式置换模式 固定分配策略固定分配策略 局部置换策略局部置换策略 全局置换策略全局置换策略 可变分配策略可变分配策略 可变分配策略可变分配策略+局部置换策略局部置换策略 即可增加或减少分配给每个活跃进程的页即可增加或减少分配给每个活跃进程的页框数；当进程的页框全部用完，而需要装入一框数；当进程的页框全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集个新的页面时，系统将在该进程的当前驻留集中选择一个页面换出内存。中选择一个页面换出内存。 页面置换策略页面置换策略 页面

32、置换算法：在指定的置换范围内，页面置换算法：在指定的置换范围内，决定将哪一个页面换出内存。决定将哪一个页面换出内存。 置换算法的好坏将直接影响系统的性能，置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现不适当的置换算法可能导致系统出现“抖动抖动”现象。现象。 常用的页面置换算法：最佳置换算法、常用的页面置换算法：最佳置换算法、最近最少使用算法、先进先出算法和时最近最少使用算法、先进先出算法和时钟算法等钟算法等最佳置换算法最佳置换算法(Optimal Algorithm，OPT) 基本思想：被置换的页面是将来不再访问，或基本思想：被置换的页面是将来不再访问，或在最远的将来才被

33、访问的页面。在最远的将来才被访问的页面。 若采用若采用固定分配策略，最佳置换算法可以保证固定分配策略，最佳置换算法可以保证系统的缺页率最低。系统的缺页率最低。 但是，无法预知一个进程在内存的若干页面中，但是，无法预知一个进程在内存的若干页面中，哪一个页面是将来不再访问的，甚至最长时间哪一个页面是将来不再访问的，甚至最长时间内将不再被访问的，因而该算法是无法实现的。内将不再被访问的，因而该算法是无法实现的。 该算法可以用于该算法可以用于评价其它置换算法评价其它置换算法的性能。的性能。示例示例 假设假设系统分配给某进程系统分配给某进程3个页框，且进个页框，且进程开始运行时，这程开始运行时，这3个页

34、框是空的。个页框是空的。 考虑下列页面号引用序列：考虑下列页面号引用序列： 2、3、2、1、5、2、4、5、3、2、5、222323231235235435435435235235235页面引用序列页面引用序列 2 3 2 1 5 2 4 5 3 2 5 2 F F F F F F 12次页面引用次页面引用 6次缺页中断（次缺页中断（F和和F） 3次页面置换（次页面置换（F）图图3.33 采用采用OPT置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程 据局部性原理，如果一个页面最近被访问过，据局部性原理，如果一个页面最近被访问过，那么，它将在不久的将来再次被访问。那么，它将在不

35、久的将来再次被访问。 如果一个页面已经很长时间未被访问过，则在如果一个页面已经很长时间未被访问过，则在很久的将来，它将不会被访问。很久的将来，它将不会被访问。 因此，可以根据页面的使用历史，判断其将来因此，可以根据页面的使用历史，判断其将来的行为。的行为。最近最少使用置换算法最近最少使用置换算法(Least Recently Used Algorithm，LRU) LRU根据页面装入内存以后的使用情况，选择根据页面装入内存以后的使用情况，选择淘汰最近最久未被使用的一个页面。淘汰最近最久未被使用的一个页面。 该算法的性能接近该算法的性能接近OPT算法，但实现较困难。算法，但实现较困难。 一种方法

36、：为每一个页面增加一个访问字段，一种方法：为每一个页面增加一个访问字段，用以标注该页最后一次被访问的时间。需要选用以标注该页最后一次被访问的时间。需要选择淘汰页面时，比较置换范围内的所有页面的择淘汰页面时，比较置换范围内的所有页面的最后访问时间，选择访问时间最远的哪个页面。最后访问时间，选择访问时间最远的哪个页面。 实现该方法的开销非常大，不易实现。实现该方法的开销非常大，不易实现。LRU置换算法的实现置换算法的实现 另一种方法：将访问页面组织在一个堆另一种方法：将访问页面组织在一个堆栈中，最近访问的页面位于栈顶，栈底栈中，最近访问的页面位于栈顶，栈底的页面即是最久未被访问的。的页面即是最久未

37、被访问的。 实践证明，该方法的实现仍然很困难，实践证明，该方法的实现仍然很困难，系统付出的代价也非常大。系统付出的代价也非常大。 22323231251251254254354352352352页面引用序列页面引用序列 2 3 2 1 5 2 4 5 3 2 5 2 F F F F F F F 12次页面引用次页面引用 7次缺页中断（次缺页中断（F和和F） 4次页面置换（次页面置换（F）图图3.34 采用采用LRU置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程先进先出置换算法先进先出置换算法(First-in First-out Algorithm，FIFO) 淘汰最先进入内

38、存的页面，即选择在内淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。存中驻留时间最久的页面予以淘汰。 实现时，只需把一个进程已调入内存的实现时，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设页面按先后次序链接成一个队列，并设置一个指针，使它总是指向最老的页面。置一个指针，使它总是指向最老的页面。22323231531521524524324324354352页面引用序列页面引用序列 2 3 2 1 5 2 4 5 3 2 5 2 F F F F F F F F F12次页面引用次页面引用 9次缺页中断（次缺页中断（F和和F） 6次页面置换（次页面置换（F）图图3

39、.35 采用采用FIFO置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程先进先出置换算法先进先出置换算法(First-in First-out Algorithm，FIFO) 该算法与进程实际的运行规律不相适应，该算法与进程实际的运行规律不相适应，进程中的某些程序代码或数据可能需要进程中的某些程序代码或数据可能需要高频使用，该算法将导致这种类型的页高频使用，该算法将导致这种类型的页面被反复地换进换出，从而降低系统性面被反复地换进换出，从而降低系统性能。能。Clock时钟置换算法时钟置换算法 内存中的每个页面配置一个内存中的每个页面配置一个使用位使用位（U位）；位）； 当页面装入

40、内存时，或被引用时，其当页面装入内存时，或被引用时，其U位将被设位将被设置为置为1； 系统将置换范围内的所有页面组成一系统将置换范围内的所有页面组成一 个循环队个循环队列，并为其设置一个列，并为其设置一个扫描指针扫描指针； 未进行页面置换时，扫描指针总是指向上一次进未进行页面置换时，扫描指针总是指向上一次进行页面置换时被置换页面所在位置的下一个位置。行页面置换时被置换页面所在位置的下一个位置。时钟置换算法（续）时钟置换算法（续） 当需要进行页面置换时，系统将移动扫描指针，搜索置换当需要进行页面置换时，系统将移动扫描指针，搜索置换范围内的各个页面，以便找到一个范围内的各个页面，以便找到一个U位为

41、位为0的页面：的页面： 如果当前扫描指针所指向的页面的如果当前扫描指针所指向的页面的U位为位为1，那么系统将把该页面，那么系统将把该页面的的U位设置为位设置为0，同时把扫描指针移到下一个位置，继续搜索；，同时把扫描指针移到下一个位置，继续搜索； 如果当前扫描指针所指向的页面的如果当前扫描指针所指向的页面的U位为位为0，那么系统将把该页面，那么系统将把该页面作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。页页6U = 1页页123U = 1页页30U = 0页页616U = 0页页77U = 1页页24U = 1页页110U = 1

42、页页16U = 0页页76U = 0.01234567n-1(b) 用用77号页面替换号页面替换23号页面以后的情况号页面以后的情况页页6U = 1页页123U = 1页页30U = 1页页616U = 1页页23U = 0页页24U = 1页页110U = 1页页16U = 0页页76U = 0.01234567n-1(a) 当前页面循环队列情况当前页面循环队列情况2*2*3*2*3*2*3*1*5*315*2*15*2*4*5*2*4*3*243*2*43*25*3*2*5*页面引用序列页面引用序列 2 3 2 1 5 2 4 5 3 2 5 2F F F F F F F F 12次页面引

43、用次页面引用 8次缺页中断（次缺页中断（F和和F） 5次页面置换次页面置换（F）图图3.37 采用采用Clock置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程时钟置换算法的改进时钟置换算法的改进 系统把一个页面移出内存时，如果该页面驻留内存期间没有系统把一个页面移出内存时，如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则系统必须把它写回被修改过，那么不必把它写回辅存，否则系统必须把它写回辅存。这表明，换出未修改过的页面比换出被修改过的页面辅存。这表明，换出未修改过的页面比换出被修改过的页面开销小。开销小。 显然，我们可以依据上述结论改进显然，我们可以依据上述结论

44、改进CLOCK算法。改进后的算法。改进后的CLOCK算法将在置换范围内算法将在置换范围内首选首选在最近没有被使用过、在在最近没有被使用过、在驻留内存期间没有被修改过的页面作为被置换页面。驻留内存期间没有被修改过的页面作为被置换页面。时钟置换算法的改进时钟置换算法的改进(续续1) 为了改进为了改进CLOCK算法，系统将为内存的每个页面配置一个算法，系统将为内存的每个页面配置一个修改位修改位（简称为（简称为M位）。位）。 改进后的改进后的CLOCK算法在置换范围内选择被置换页面时将同算法在置换范围内选择被置换页面时将同时考虑时考虑U位和位和M位。位。 一个页面的一个页面的U位与位与M位共有四种组合

45、：位共有四种组合： U=0，M=0：最近没有被使用过，驻留内存期间也没有被修改过；：最近没有被使用过，驻留内存期间也没有被修改过； U=1，M=0：最近被使用过，但驻留内存期间没有被修改过；：最近被使用过，但驻留内存期间没有被修改过； U=0，M=1：最近没有被使用过，但驻留内存期间被修改过；：最近没有被使用过，但驻留内存期间被修改过； U=1，M=1：最近被使用过，驻留内存期间也被修改过；：最近被使用过，驻留内存期间也被修改过；时钟置换算法的改进时钟置换算法的改进(续续2) 改进后的改进后的 CLOCK 算法将按下列步骤选择被置换页面：算法将按下列步骤选择被置换页面：1、从扫描指针的当前位置

46、开始，搜索、从扫描指针的当前位置开始，搜索 U=0且且 M=0 的页的页面。此次搜索不会修改置换范围内的任何一个页面的面。此次搜索不会修改置换范围内的任何一个页面的U位。位。若找到第一个若找到第一个U=0且且M=0的页面，则把该页面选作被置的页面，则把该页面选作被置换页面，终止算法。换页面，终止算法。2、如果第一步没有成功，、如果第一步没有成功， 那么扫描指针将回到原位。那么扫描指针将回到原位。 再再次搜索次搜索U=0但但M=1的页面。如果遇到的页面。如果遇到U位为位为1的页面，将的页面，将其其U位修改为位修改为0。倘若找到第一个。倘若找到第一个U=0但但M=1的页面，将的页面，将该页面选作被

47、置换页面，终止算法。该页面选作被置换页面，终止算法。3、如果第二步也没有成功，、如果第二步也没有成功， 那么扫描指针将再次回到原那么扫描指针将再次回到原位，且置换范围内的所有页面的位，且置换范围内的所有页面的U位均为位均为0。此时，算法。此时，算法将返回第一步继续执行。将返回第一步继续执行。页页10U=1 M=0页页565U=1 M=1页页20U=1 M=0页页16U=1 M=1页页19U=0 M=0页页566U=1 M=0 页页110 U=1 M=1页页111U=0 M=1页页112U=0 M=1.01234567n-1图图3.38 改进型改进型clock算法：页面置换之前的情形算法：页面置

48、换之前的情形页面清除策略页面清除策略 页面清除是指，将由页面置换算法选择页面清除是指，将由页面置换算法选择的被修改的置换页面的被修改的置换页面保存到外存保存到外存。 页面清除策略需要决定系统页面清除策略需要决定系统何时何时把一个把一个被置换页面写回外存。被置换页面写回外存。 最直接的页面清除时机是，只有当一个最直接的页面清除时机是，只有当一个页被选中作为置换页时，才被写回外存，页被选中作为置换页时，才被写回外存，称之为称之为请求清除策略请求清除策略。 若被选中的置换页面自进入内存以来被修改过，若被选中的置换页面自进入内存以来被修改过，则需要首先将该页面内容写回外存保存起来，则需要首先将该页面内

49、容写回外存保存起来，然后，装入进程需要的新页内容。然后，装入进程需要的新页内容。 可见，采用请求清除策略时，写出一个被修改可见，采用请求清除策略时，写出一个被修改过的页面与读入一个新页的操作是过的页面与读入一个新页的操作是成对出现成对出现的，的，而且，写出操作先于读入操作。而且，写出操作先于读入操作。 所以，当正在执行的进程发生缺页中断时，需所以，当正在执行的进程发生缺页中断时，需要阻塞等待一个页面的写出和另一个页面的读要阻塞等待一个页面的写出和另一个页面的读入，这可能降低处理机的使用效率。入，这可能降低处理机的使用效率。 一种有效的页面清除策略是结合一种有效的页面清除策略是结合页缓冲页缓冲（

50、Page Buffering）技术。）技术。 当发生缺页中断时，不必首先写出置换当发生缺页中断时，不必首先写出置换页，然后读入新页。而是，将被选中的页，然后读入新页。而是，将被选中的置换页置换页暂时保留暂时保留在内存的一个缓冲区，在内存的一个缓冲区，在以后某个合适的时候将这些被置换页在以后某个合适的时候将这些被置换页批量写出批量写出到外存。到外存。 减少磁盘减少磁盘I/O的次数，提高处理机的效率。的次数，提高处理机的效率。页缓冲技术的实现页缓冲技术的实现 需要两个链表：需要两个链表：未修改页链表未修改页链表和和修改页链表修改页链表。 当选中一个被修改过的页作为置换页时，不需当选中一个被修改过的

51、页作为置换页时，不需要立即、真正地将其写出到外存，而是首先将要立即、真正地将其写出到外存，而是首先将其插入到其插入到修改链表修改链表中缓冲存储。修改链表中的中缓冲存储。修改链表中的页可以周期性地批量写出到外存，并移到未修页可以周期性地批量写出到外存，并移到未修改表中。改表中。 未修改表未修改表链接被选中的未修改置换页，当其中链接被选中的未修改置换页，当其中某页所占用的页框被新页占用时，新页的内容某页所占用的页框被新页占用时，新页的内容覆盖置换页的内容，置换页被真正从内存清除。覆盖置换页的内容，置换页被真正从内存清除。 采用页缓冲技术，当需要读入一个新页时，首采用页缓冲技术，当需要读入一个新页时

52、，首先检查先检查未修改页链表未修改页链表，若该表非空，便可按照，若该表非空，便可按照FIFO方法，将该链表头指向的第一个页面占方法，将该链表头指向的第一个页面占用的页框分配给新页。用的页框分配给新页。 如果未修改表为空，检查修改页链表，将该表如果未修改表为空，检查修改页链表，将该表中的页面内容批量写出到外存，并将这些页移中的页面内容批量写出到外存，并将这些页移到未修改表中，按照上述方法重新分配其占用到未修改表中，按照上述方法重新分配其占用的页框。的页框。 显然，采用页缓冲技术不仅可以减少写出页面显然，采用页缓冲技术不仅可以减少写出页面的系统开销，而且可以减少读入页面的开销。的系统开销，而且可以

53、减少读入页面的开销。因为，当进程再次访问页面缓冲区的页面时，因为，当进程再次访问页面缓冲区的页面时，只需要将对应页面从缓冲区返回到该进程的驻只需要将对应页面从缓冲区返回到该进程的驻留集中，而无须从外存读入。留集中，而无须从外存读入。负载控制负载控制 多道程序系统允许多个进程同时驻留内多道程序系统允许多个进程同时驻留内存，以提高系统吞吐量和资源利用率。存，以提高系统吞吐量和资源利用率。 然而，如果同时驻留内存的进程数量然而，如果同时驻留内存的进程数量太太多多，每个进程都竞争各自需要的资源，每个进程都竞争各自需要的资源，反而会反而会降低系统效率降低系统效率。负载控制负载控制 如果内存中如果内存中进程太多，进程太多，将导致每个进程的驻留将导致每个进程的驻留集