操作系统2存储器管理简介2

前面所介绍的各种存储器管理方式有一个共同的特点&＃xff0c;即它们都要求将一个作业全部装入内存后方能运行&＃xff0c;于是&＃xff0c;出现了下面这样两种情况&＃xff1a;
(1) 有的作业很大&＃xff0c;其所要求的内存空间超过了内存总容量&＃xff0c;作业不能全部被装入内存&＃xff0c;致使该作业无法运行。
(2) 有大量作业要求运行&＃xff0c;但由于内存容量不足以容纳所有这些作业&＃xff0c;只能将少数作业装入内存让它们先运行&＃xff0c;而将其它大量的作业留在外存上等待。
出现上述两种情况的原因&＃xff0c;都是由于内存容量不够大。一个显而易见的解决方法&＃xff0c;是从物理上增加内存容量&＃xff0c;但这往往会受到机器自身的限制&＃xff0c;而且无疑要增加系统成本&＃xff0c;因此这种方法是受到一定限制的。另一种方法是从逻辑上扩充内存容量&＃xff0c;这正是虚拟存储技术所要解决的主要问题。

1&＃xff0e;常规存储器管理方式的特征

(1) 一次性。在前面所介绍的几种存储管理方式中&＃xff0c;都要求作业在运行前需一次性地全部装入内存&＃xff0c;而正是这一特征导致了上述两种情况的发生。此外&＃xff0c;还有许多作业在每次运行时&＃xff0c;并非其全部程序和数据都要用到。如果一次性地装入其全部程序&＃xff0c;也是一种对内存空间的浪费。
(2) 驻留性。作业装入内存后&＃xff0c;便一直驻留在内存中&＃xff0c;直至作业运行结束。尽管运行中的进程会因 I/O 而长期等待&＃xff0c;或有的程序模块在运行过一次后就不再需要(运行)了&＃xff0c;但它们都仍将继续占用宝贵的内存资源。
上述一次性及驻留性在程序运行时是必需的吗&＃xff1f;

2&＃xff0e;局部性原理

程序在执行时将呈现出局部性规律&＃xff0c;即在一较短的时间内&＃xff0c;程序的执行仅局限于某个部分&＃xff1b;相应地&＃xff0c;它所访问的存储空间也局限于某个区域。
局限性还表现在下述两个方面&＃xff1a;
(1) 时间局限性。如果程序中的某条指令一旦执行&＃xff0c;则不久以后该指令可能再次执行&＃xff1b;如果某数据被访问过&＃xff0c;则不久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。
(2) 空间局限性。一旦程序访问了某个存储单元&＃xff0c;在不久之后&＃xff0c;其附近的存储单元也将被访问&＃xff0c;即程序在一段时间内所访问的地址&＃xff0c;可能集中在一定的范围之内&＃xff0c;其典型情况便是程序的顺序执行。

3&＃xff0e;虚拟存储器的定义

基于局部性原理&＃xff0c;应用程序在运行之前&＃xff0c;没有必要全部装入内存&＃xff0c;仅须将那些当前要运行的少数页面或段先装入内存便可运行&＃xff0c;其余部分暂留在盘上。程序在运行时&＃xff0c;如果它所要访问的页(段)已调入内存&＃xff0c;便可继续执行下去&＃xff1b;但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)&＃xff0c;此时程序应利用 OS 所提供的请求调页(段)功能&＃xff0c;将它们调入内存&＃xff0c;以使进程能继续执行下去。如果此时内存已满&＃xff0c;无法再装入新的页(段)&＃xff0c;则还须再利用页(段)的置换功能&＃xff0c;将内存中暂时不用的页(段)调至盘上&＃xff0c;腾出足够的内存空间后&＃xff0c;再将要访问的页(段)调入内存&＃xff0c;使程序继续执行下去。这样&＃xff0c;便可使一个大的用户程序能在较小的内存空间中运行&＃xff1b;也可在内存中同时装入更多的进程使它们并发执行。从用户角度看&＃xff0c;该系统所具有的内存容量&＃xff0c;将比实际内存容量大得多。但须说明&＃xff0c;用户所看到的大容量只是一种感觉&＃xff0c;是虚的&＃xff0c;故人们把这样的存储器称为虚拟存储器。
由上所述可以得知&＃xff0c;所谓虚拟存储器&＃xff0c;是指具有请求调入功能和置换功能&＃xff0c;能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定&＃xff0c;其运行速度接近于内存速度&＃xff0c;而每位的成本却又接近于外存。

4&＃xff0e;虚拟存储器的实现

虚拟存储器的实现&＃xff0c;都建立在离散分配的存储管理方式的基础上。

4.1 分页请求系统

这是在分页系统的基础上&＃xff0c;增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入少数页面的程序(及数据)&＃xff0c;便启动运行。以后&＃xff0c;再通过调页功能及页面置换功能&＃xff0c;陆续地把即将要运行的页面调入内存&＃xff0c;同时把暂不运行的页面换出到外存上。置换时以页面为单位。

4.2 请求分段系统

这是在分段系统的基础上&＃xff0c;增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用户程序和数据&＃xff0c;即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出&＃xff0c;同时调入即将运行的段。置换是以段为单位进行的。

5.虚拟存储器的特征

1&＃xff0e;多次性
多次性是指一个作业被分成多次调入内存运行&＃xff0c;亦即在作业运行时没有必要将其全部装入&＃xff0c;只需将当前要运行的那部分程序和数据装入内存即可&＃xff1b;以后每当要运行到尚未调入的那部分程序时&＃xff0c;再将它调入。多次性是虚拟存储器最重要的特征&＃xff0c;任何其它的存储管理方式都不具有这一特征。因此&＃xff0c;我们也可以认为虚拟存储器是具有多次性特征的存储器系统。
2&＃xff0e;对换性
对换性是指允许在作业的运行过程中进行换进、换出&＃xff0c;亦即&＃xff0c;在进程运行期间&＃xff0c;允许将那些暂不使用的程序和数据&＃xff0c;从内存调至外存的对换区(换出)&＃xff0c;待以后需要时再将它们从外存调至内存(换进)&＃xff1b;甚至还允许将暂时不运行的进程调至外存&＃xff0c;待它们具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。
3&＃xff0e;虚拟性
虚拟性是指能够从逻辑上扩充内存容量&＃xff0c;使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征&＃xff0c;也是实现虚拟存储器的最重要的目标。
值得说明的是&＃xff0c;虚拟性是以多次性和对换性为基础的&＃xff0c;或者说&＃xff0c;仅当系统允许将作业分多次调入内存&＃xff0c;并能将内存中暂时不运行的程序和数据换至盘上时&＃xff0c;才有可能实现虚拟存储器&＃xff1b;而多次性和对换性又必须建立在离散分配的基础上。

请求分页系统是建立在基本分页基础上的&＃xff0c;为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。相应地&＃xff0c;每次调入和换出的基本单位都是长度固定的页面&＃xff0c;这使得请求分页系统在实现上要比请求分段系统简单(后者在换进和换出时是可变长度的段)。因此&＃xff0c;请求分页成为目前最常用的一种实现虚拟存储器的方式。

1.请求分页中的硬件支持

1.1页表机制

在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将应用程序的一部分调入内存&＃xff0c;还有一部分仍在盘上&＃xff0c;故须在页表中再增加若干项&＃xff0c;供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如下所示&＃xff1a;
(1) 状态位 P&＃xff1a;用于指示该页是否已调入内存&＃xff0c;供程序访问时参考。
(2) 访问字段 A&＃xff1a;用于记录本页在一段时间内被访问的次数&＃xff0c;或记录本页最近已有多长时间未被访问&＃xff0c;供选择换出页面时参考。
(3) 修改位 M&＃xff1a;表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本&＃xff0c;因此&＃xff0c;若未被修改&＃xff0c;在置换该页时就不需再将该页写回到外存上&＃xff0c;以减少系统的开销和启动磁盘的次数&＃xff1b;若已被修改&＃xff0c;则必须将该页重写到外存上&＃xff0c;以保证外存中所保留的始终是最新副本。简言之&＃xff0c;M 位供置换页面时参考。
(4) 外存地址&＃xff1a;用于指出该页在外存上的地址&＃xff0c;通常是物理块号&＃xff0c;供调入该页时参考。

1. 2 缺页中断机构

在请求分页系统中&＃xff0c;每当所要访问的页面不在内存时&＃xff0c;便产生一缺页中断&＃xff0c;请求 OS 将所缺之页调入内存。缺页中断作为中断&＃xff0c;它们同样需要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序进行处理、恢复 CPU 环境等几个步骤。但缺页中断又是一种特殊的中断&＃xff0c;它与一般的中断相比&＃xff0c;有着明显的区别&＃xff0c;主要表现在下面两个方面&＃xff1a;
(1) 在指令执行期间产生和处理中断信号。通常&＃xff0c;CPU 都是在一条指令执行完后&＃xff0c;才检查是否有中断请求到达。若有&＃xff0c;便去响应&＃xff0c;否则&＃xff0c;继续执行下一条指令。然而&＃xff0c;缺页中断是在指令执行期间&＃xff0c;发现所要访问的指令或数据不在内存时所产生和处理的。
(2) 一条指令在执行期间&＃xff0c;可能产生多次缺页中断。基于这些特征&＃xff0c;系统中的硬件机构应能保存多次中断时的状态&＃xff0c;并保证最后能返回到中断前产生缺页中断的指令处继续执行

1.3 地址变换机构

请求分页系统中的地址变换机构&＃xff0c;是在分页系统地址变换机构的基础上&＃xff0c;再为实现虚拟存储器而增加了某些功能而形成的&＃xff0c;如产生和处理缺页中断&＃xff0c;以及从内存中换出一页的功能等等。图 4-25 示出了请求分页系统中的地址变换过程。在进行地址变换时&＃xff0c;首先去检索快表&＃xff0c;试图从中找出所要访问的页。若找到&＃xff0c;便修改页表项中的访问位。对于写指令&＃xff0c;还须将修改位置成“1”&＃xff0c;然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束.

如果在快表中未找到该页的页表项时&＃xff0c;应到内存中去查找页表&＃xff0c;再从找到的页表项中的状态位 P&＃xff0c;来了解该页是否已调入内存。若该页已调入内存&＃xff0c;这时应将此页的页表项写入快表&＃xff0c;当快表已满时&＃xff0c;应先调出按某种算法所确定的页的页表项&＃xff0c;然后再写入该页的页表项&＃xff1b;若该页尚未调入内存&＃xff0c;这时应产生缺页中断&＃xff0c;请求 OS 从外存把该页调入内存。

1.4 内存分配策略和分配算法

最小物理块数的确定:
最小物理块数&＃xff0c;是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时&＃xff0c;进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关&＃xff0c;取决于指令的格式、功能和寻址方式。
物理块的分配策略:
在请求分页系统中&＃xff0c;可采取两种内存分配策略&＃xff0c;即固定和可变分配策略。在进行置换时&＃xff0c;也可采取两种策略&＃xff0c;即全局置换和局部置换。于是可组合出以下三种适用的策略。

1. 固定分配局部置换(Fixed Allocation&＃xff0c;Local Replacement)
   为每个进程分配一定数目的物理块&＃xff0c;在整个运行期间都不再改变。采用该策略时&＃xff0c;如果进程在运行中发现缺页&＃xff0c;则只能从该进程在内存的 n 个页面中选出一个页换出&＃xff0c;然后再调入一页&＃xff0c;以保证分配给该进程的内存空间不变。
2. 可变分配全局置换(Variable Allocation&＃xff0c;Global Replacement)
   在采用这种策略时&＃xff0c;先为系统中的每个进程分配一定数目的物理块&＃xff0c;而 OS 自身也保持一个空闲物理块队列。当某进程发现缺页时&＃xff0c;由系统从空闲物理块队列中取出一个物理块分配给该进程&＃xff0c;并将欲调入的(缺)页装入其中。这样&＃xff0c;凡产生缺页(中断)的进程&＃xff0c;都将获得新的物理块。仅当空闲物理块队列中的物理块用完时&＃xff0c;OS 才能从内存中选择一页调出&＃xff0c;该页可能是系统中任一进程的页&＃xff0c;这样&＃xff0c;自然又会使那个进程的物理块减少&＃xff0c;进而使其缺页率增加。
3. 可变分配局部置换(Variable Allocation&＃xff0c;Local Replacement)
   为每个进程分配一定数目的物理块&＃xff0c;但当某进程发现缺页时&＃xff0c;只允许从该进程在内存的页面中选出一页换出&＃xff0c;这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断&＃xff0c;则系统须再为该进程分配若干附加的物理块&＃xff0c;直至该进程的缺页率减少到适当程度为止&＃xff1b;反之&＃xff0c;若一个进程在运行过程中的缺页率特别低&＃xff0c;则此时可适当减少分配给该进程的物理块数&＃xff0c;但不应引起其缺页率明显增加。

物理块分配算法
在采用固定分配策略时&＃xff0c;如何将系统中可供分配的所有物理块分配给各个进程&＃xff0c;可采用平均分配算法、按比例分配算法、考虑优先权的分配算法。

1.5 调页策略

调入页面的时机
为了确定系统将进程运行时所缺的页面调入内存的时机&＃xff0c;可采取预调页策略或请求调页策略。

1. 预调页策略
   如果进程的许多页是存放在外存的一个连续区域中&＃xff0c;则一次调入若干个相邻的页&＃xff0c;会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问&＃xff0c;则又是低效的。可采用一种以预测为基础的预调页策略&＃xff0c;将那些预计在不久之后便会被访问的页面预先调入内存。如果预测较准确&＃xff0c;那么&＃xff0c;这种策略显然是很有吸引力的。
2. 请求调页策略
   当进程在运行中需要访问某部分程序和数据时&＃xff0c;若发现其所在的页面不在内存&＃xff0c;便立即提出请求&＃xff0c;由 OS 将其所需页面调入内存。由请求调页策略所确定调入的页&＃xff0c;是一定会被访问的&＃xff0c;再加之请求调页策略比较易于实现&＃xff0c;故在目前的虚拟存储器中大多采用此策略。但这种策略每次仅调入一页&＃xff0c;故须花费较大的系统开销&＃xff0c;增加了磁盘 I/O 的启动频率。

确定从何处调入页面
在请求分页系统中的外存分为两部分&＃xff1a;用于存放文件的文件区和用于存放对换页面的对换区。通常&＃xff0c;由于对换区是采用连续分配方式&＃xff0c;而文件区是采用离散分配方式&＃xff0c;故对换区的磁盘 I/O 速度比文件区的高。这样&＃xff0c;每当发生缺页请求时&＃xff0c;系统应从何处将缺页调入内存&＃xff0c;可分成如下三种情况&＃xff1a;

1. 系统拥有足够的对换区空间&＃xff0c;这时可以全部从对换区调入所需页面&＃xff0c;以提高调页速度。为此&＃xff0c;在进程运行前&＃xff0c;便须将与该进程有关的文件从文件区拷贝到对换区。
2. 系统缺少足够的对换区空间&＃xff0c;这时凡是不会被修改的文件都直接从文件区调入&＃xff1b;而当换出这些页面时&＃xff0c;由于它们未被修改而不必再将它们换出&＃xff0c;以后再调入时&＃xff0c;仍从文件区直接调入。但对于那些可能被修改的部分&＃xff0c;在将它们换出时&＃xff0c;便须调到对换区&＃xff0c;以后需要时&＃xff0c;再从对换区调入。
3. UNIX 方式。由于与进程有关的文件都放在文件区&＃xff0c;故凡是未运行过的页面&＃xff0c;都从文件区调入。而对于曾经运行过但又被换出的页面&＃xff0c;由于是被放在对换区&＃xff0c;因此在下次调入时&＃xff0c;应从对换区调入。由于 UNIX 系统允许页面共享&＃xff0c;因此&＃xff0c;某进程所请求的页面有可能已被其它进程调入内存&＃xff0c;此时也就无须再从对换区调入。

页面调入过程
每当程序所要访问的页面未在内存时&＃xff0c;便向 CPU 发出一缺页中断&＃xff0c;中断处理程序首先保留 CPU 环境&＃xff0c;分析中断原因后转入缺页中断处理程序。该程序通过查找页表&＃xff0c;得到该页在外存的物理块后&＃xff0c;如果此时内存能容纳新页&＃xff0c;则启动磁盘 I/O 将所缺之页调入内存&＃xff0c;然后修改页表。如果内存已满&＃xff0c;则须先按照某种置换算法从内存中选出一页准备换出&＃xff1b;如果该页未被修改过&＃xff0c;可不必将该页写回磁盘&＃xff1b;但如果此页已被修改&＃xff0c;则必须将它写回磁盘&＃xff0c;然后再把所缺的页调入内存&＃xff0c;并修改页表中的相应表项&＃xff0c;置其存在位为“1”&＃xff0c;并将此页表项写入快表中。在缺页调入内存后&＃xff0c;利用修改后的页表&＃xff0c;去形成所要访问数据的物理地址&＃xff0c;再去访问内存数据。整个页面的调入过程对用户是透明的。

在进程运行过程中&＃xff0c;若其所要访问的页面不在内存而需把它们调入内存&＃xff0c;但内存已无空闲空间时&＃xff0c;为了保证该进程能正常运行&＃xff0c;系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出&＃xff0c;须根据一定的算法来确定。通常&＃xff0c;把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏&＃xff0c;将直接影响到系统的性能。
一个好的页面置换算法&＃xff0c;应具有较低的页面更换频率。从理论上讲&＃xff0c;应将那些以后不再会访问的页面换出&＃xff0c;或把那些在较长时间内不会再访问的页面调出。

8.1 最佳置换算法和先进先出置换算法

最佳置换算法是一种理想化的算法&＃xff0c;它具有最好的性能&＃xff0c;但实际上却难于实现。先进先出置换算法是最直观的算法&＃xff0c;由于它可能是性能最差的算法&＃xff0c;故实际应用极少。

1&＃xff0e;最佳(Optimal)置换算法

最佳置换算法所选择的被淘汰页面&＃xff0c;将是以后永不使用的&＃xff0c;或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法&＃xff0c;通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中&＃xff0c;哪一个页面是未来最长时间内不再被访问的&＃xff0c;因而该算法是无法实现的&＃xff0c;但可以利用该算法去评价其它算法。&＃xff08;最佳置换算法“向后看”&＃xff09;

2&＃xff0e;先进先出(FIFO)页面置换算法

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面&＃xff0c;即选择在内存中驻留时间最久的页面予以淘汰。

8.2 最近最久未使用(LRU)置换算法

1. LRU置换算法的概念

FIFO 置换算法性能之所以较差&＃xff0c;是因为它所依据的条件是各个页面调入内存的时间&＃xff0c;而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法&＃xff0c;是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况&＃xff0c;只能利用“最近的过去”作为“最近的将来”的近似&＃xff0c;因此&＃xff0c;LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段&＃xff0c;用来记录一个页面自上次被访问以来所经历的时间 t&＃xff0c;当须淘汰一个页面时&＃xff0c;选择现有页面中其 t 值最大的&＃xff0c;即最近最久未使用的页面予以淘汰。&＃xff08;LRU算法“向前看”&＃xff09;

2&＃xff0e;LRU 置换算法的硬件支持

LRU 置换算法虽然是一种比较好的算法&＃xff0c;但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问&＃xff0c;以及如何快速地知道哪一页是最近最久未使用的页面&＃xff0c;须有两类硬件之一的支持&＃xff1a;寄存器或栈。
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时&＃xff0c;便将该页面的页面号从栈中移出&＃xff0c;将它压入栈顶。因此&＃xff0c;栈顶始终是最新被访问页面的编号&＃xff0c;而栈底则是最近最久未使用页面的页面号。

8.3 Clock 置换算法

LRU 算法是较好的一种算法&＃xff0c;但由于它要求有较多的硬件支持&＃xff0c;故在实际应用中&＃xff0c;大多采用 LRU 的近似算法。Clock 算法就是用得较多的一种 LRU 近似算法。

1&＃xff0e;简单的 Clock 置换算法

当采用简单 Clock 算法时&＃xff0c;只需为每页设置一位访问位&＃xff0c;再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时&＃xff0c;其访问位被置 1。置换算法在选择一页淘汰时&＃xff0c;只需检查页的访问位。如果是 0&＃xff0c;就选择该页换出&＃xff1b;若为 1&＃xff0c;则重新将它置 0&＃xff0c;暂不换出&＃xff0c;而给该页第二次驻留内存的机会&＃xff0c;再按照 FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时&＃xff0c;若其访问位仍为 1&＃xff0c;则再返回到队首去检查第一个页面。图 4-31 示出了该算法的流程和示例。由于该算法是循环地检查各页面的使用情况&＃xff0c;故称为 Clock 算法。但因该算法只有一位访问位&＃xff0c;只能用它表示该页是否已经使用过&＃xff0c;而置换时是将未使用过的页面换出去&＃xff0c;故又把该算法称为最近未用算法 NRU(Not Recently Used)。

2&＃xff0e;改进型 Clock 置换算法

在将一个页面换出时&＃xff0c;如果该页已被修改过&＃xff0c;便须将该页重新写回到磁盘上&＃xff1b;但如果该页未被修改过&＃xff0c;则不必将它拷回磁盘。在改进型 Clock 算法中&＃xff0c;除须考虑页面的使用情况外&＃xff0c;还须再增加一个因素&＃xff0c;即置换代价&＃xff0c;这样&＃xff0c;选择页面换出时&＃xff0c;既要是未使用过的页面&＃xff0c;又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位 A和修改位 M 可以组合成下面四种类型的页面&＃xff1a;
1 类(A&＃61;0&＃xff0c;M&＃61;0)&＃xff1a;表示该页最近既未被访问&＃xff0c;又未被修改&＃xff0c;是最佳淘汰页。
2 类(A&＃61;0&＃xff0c;M&＃61;1)&＃xff1a;表示该页最近未被访问&＃xff0c;但已被修改&＃xff0c;并不是很好的淘汰页。
3 类(A&＃61;1&＃xff0c;M&＃61;0)&＃xff1a;表示该页最近已被访问&＃xff0c;但未被修改&＃xff0c;该页有可能再被访问。
4 类(A&＃61;1&＃xff0c;M&＃61;1)&＃xff1a;表示该页最近已被访问且被修改&＃xff0c;该页可能再被访问。
在内存中的每个页必定是这四类页面之一&＃xff0c;在进行页面置换时&＃xff0c;可采用与简单 Clock算法相类似的算法&＃xff0c;其差别在于该算法须同时检查访问位与修改位&＃xff0c;以确定该页是四类页面中的哪一种。其执行过程可分成以下三步&＃xff1a;
(1) 从指针所指示的当前位置开始&＃xff0c;扫描循环队列&＃xff0c;寻找 A&＃61;0 且 M&＃61;0 的第一类页面&＃xff0c;将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
(2) 如果第一步失败&＃xff0c;即查找一周后未遇到第一类页面&＃xff0c;则开始第二轮扫描&＃xff0c;寻找 A&＃61;0且 M&＃61;1 的第二类页面&＃xff0c;将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间&＃xff0c;将所有扫描过的页面的访问位都置 0。
(3) 如果第二步也失败&＃xff0c;亦即未找到第二类页面&＃xff0c;则将指针返回到开始的位置&＃xff0c;并将所有的访问位复 0。然后重复第一步&＃xff0c;如果仍失败&＃xff0c;必要时再重复第二步&＃xff0c;此时就一定能找到被淘汰的页。该算法与简单 Clock 算法比较&＃xff0c;可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页&＃xff0c;可能须经过几轮扫描。换言之&＃xff0c;实现该算法本身的开销将有所增加。

在请求分段系统中&＃xff0c;程序运行之前&＃xff0c;只需先调入若干个分段(不必调入所有的分段)&＃xff0c;便可启动运行。当所访问的段不在内存中时&＃xff0c;可请求 OS 将所缺的段调入内存。像请求分页系统一样&＃xff0c;为实现请求分段存储管理方式&＃xff0c;同样需要一定的硬件支持和相应的软件。

9.1 请求分段中的硬件支持

1&＃xff0e;段表机制

在请求分段式管理中所需的主要数据结构是段表。由于在应用程序的许多段中&＃xff0c;只有一部分段装入内存&＃xff0c;其余的一些段仍留在外存上&＃xff0c;故须在段表中增加若干项&＃xff0c;以供程序在调进、调出时参考。下面给出请求分段的段表项。

在段表项中&＃xff0c;除了段名(号)、段长、段在内存中的起始地址外&＃xff0c;还增加了以下诸项。
(1) 存取方式&＃xff1a;用于标识本分段的存取属性是只执行、只读&＃xff0c;还是允许读/写。
(2) 访问字段 A&＃xff1a;其含义与请求分页的相应字段相同&＃xff0c;用于记录该段被访问的频繁程度。
(3) 修改位 M&＃xff1a;用于表示该页在进入内存后是否已被修改过&＃xff0c;供置换页面时参考。
(4) 存在位 P&＃xff1a;指示本段是否已调入内存&＃xff0c;供程序访问时参考。
(5) 增补位&＃xff1a;这是请求分段式管理中所特有的字段&＃xff0c;用于表示本段在运行过程中是否做过动态增长。
(6) 外存始址&＃xff1a;指示本段在外存中的起始地址&＃xff0c;即起始盘块号。

2. 缺段中断机构

**在请求分段系统中&＃xff0c;每当发现运行进程所要访问的段尚未调入内存时&＃xff0c;便由缺段中断机构产生一缺段中断信号&＃xff0c;进入 OS 后由缺段中断处理程序将所需的段调入内存。**缺段中断机构与缺页中断机构类似&＃xff0c;它同样需要在一条指令的执行期间&＃xff0c;产生和处理中断&＃xff0c;以及在一条指令执行期间&＃xff0c;可能产生多次缺段中断。但由于分段是信息的逻辑单位&＃xff0c;因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。缺段中断的处理过程如图 4-32 所示。由于段不是定长的&＃xff0c;这使对缺段中断的处理要比对缺页中断的处理复杂。

3. 地址变换机构

请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存&＃xff0c;所以在地址变换时&＃xff0c;若发现所要访问的段不在内存&＃xff0c;必须先将所缺的段调入内存&＃xff0c;并修改段表&＃xff0c;然后才能再利用段表进行地址变换。为此&＃xff0c;在地址变换机构中又增加了某些功能&＃xff0c;如缺段中断的请求及处理等。图 4-33 示出了请求分段系统的地址变换过程。

《操作系统》汤子瀛&＃xff0c;第三版