第四章：存储器管理

type

slug

status

summary

icon

4.1 存储器达到层次结构

存储器分为三级:

CPU寄存器

主存:高速缓存、主存、磁盘缓存

辅存:磁盘、可移动存储介质

三个评估方面:

速度(由高到低)、容量(由小到大)、价格(由高到低)

主存储器（内存，主存，可执行存储器）

用于保存进程运行时的程序和数据。CPU的控制部件只能从主存中取得指令和数据到CPU寄存器，同样，CPU寄存器中的数据可存入主存。CPU与外设交换数据必须依托于主存。

寄存器

寄存器访问速度最快，与CPU协调工作。

高速缓存

CPU对高速缓存的访问，其速度比访问主存快，比访问寄存器慢。
根据程序执行的局部性原理，将主存中一些经常访问的数据存放在高速缓存中，减少访问主存的次数，提高程序的执行速度。
有些计算机系统设置了两级高速缓存，即，一级高速缓存与二级高速缓存。

磁盘缓存

内存中一块存储区，对应于某固定磁盘，临时存储磁盘数据（如，数据预取）。

4.1.2 存储器管理的目的和功能

主存储器的分配和管理

按用户要求把适当的存储空间分配给相应的作业。一个有效的存储分配机制，应在用户请求时能作出快速的响应，分配相应的存储空间；在用户不再使用它时，应立即回收，以供其他用户使用。
功能

记住每个存储区域的状态：哪些是已分配的，哪些是可以用作分配的。
实施分配：在系统程序或用户提出申请时，按所需的量给予分配；修改相应的分配记录表。
接受系统或用户释放的存储区域：并相应地修改分配记录表。

目的：

提高主存储器的利用率：多道程序能动态地共享主存。
“扩充”主存容量：提供虚拟存储器，为用户提供比主存的存储空间还大的地址空间。
存储保护：确保各道用户作业都在所分配的存储区内操作，互不干扰

4.1.3 存储分配的三种方式

存储分配：解决多道作业之间共享主存的问题。

解决的问题：确定什么时候，以什么方式，把一个作业的全部信息或作业运行时首先需要的信息分配到主存中，并使这些问题对用户来说尽可能是“透明”的。

直接指定方式

由编程人员在编写程序时，或由编译程序编译源程序时，对一个作业的所有信息确定在主存存储空间中的位置。在多道程序环境下，应保证各作业所用的地址互不重叠。
缺点：不仅用户感到不便，而且存储空间的利用也不那么有效。

静态分配方式(Static Allocation)

用户在编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址开始；当装配程序对其进行连接装入时才确定它们在主存中的相应位置，从而生成可执行程序。也就是说，存储分配是在装入时实现的。
特点：

在一个作业装入时必须分配其要求的全部存储量；
如果没有足够的存储空间，就不能装入该作业；
一旦一个作业进入内存后，在其退出系统之前，它一直占用着分配给它的全部存储空间；
作业在整个运行过程中不能在内存中“搬家”、也不能再申请存储量。

缺点：多道程序系统中不能有效地共享存储器资源。（前面说到的退出系统之前一直占用）

动态分配方式(Dynamic Allocation)

特点：

作业在存储空间中的位置，也是在其装入时确定的；
在其执行过程中可根据需要申请附加的存储空间
一个作业已占用的部分存储区域不再需要时，可以要求归还给系统。（即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收；）
存储区域的大小是可变的；
允许作业在内存中“搬家”

4.1.4 地址空间的基本概念

逻辑地址（相对地址，虚地址）

用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。
不能用逻辑地址在内存中读取信息

物理地址（绝对地址，实地址）

内存中存储单元的地址，可直接寻址

名空间

一个用高级语言编制的源程序，我们说它存在于由程序员建立的符号名字空间（简称名空间）。

地址空间

程序用来访问信息所用地址单元的集合，是逻辑（相对）地址的集合，由编译程序生成。

存储空间：主存中物理单元的集合。这些单元的编号称物理地址或绝对地址。存储空间的大小是由主存的实际容量决定的。

地址空间是逻辑地址的集合；存储空间是物理地址的集合。一个是“虚”的概念，一个是“实”的物体。

一个编译好的目标程序存在于它自己的地址空间中，当要它在计算机上运行时，才把它装入存储空间。

一个作业在编译、装入前后存在于不同的空间。

4.2 程序的装入和链接

程序的运行步骤

编译

源程序模块是用高级语言或汇编语言写的一组程序语句。计算机不能直接执行源语句，它们要首先被编译程序或解释程序翻译成机器级代码。
编译程序(Compiler)接受完整的源一级的程序，并以类似于成批的方式生成完整的目标一级的模块。

链接

目标模块是纯二进制的机器级代码。计算机可以执行目标级代码，但是典型的目标模块是不完备的，它包含对其它目标模块（诸如存取方法或子例程）或库函数的引用。因此，目标模块通常是不能装入计算机并执行的。
大部份目标模块必须首先链接成一个装入模块，它是能被装入并执行的完备的机器级程序。这个使目标模块链接成装入模块的过程，是由链接程序（Linker）实现的。

装入

由装入程序（Loder）将装入模块装入内存并执行。

4.2.1 程序的装入

装入程序将装入模块装入内存时，可采用三种方式：

4.2.1.1 绝对装入方式

绝对装入方式(Absolute Loading Mode) ：在编译时，如果知道程序将驻留在内存的具体位置，那么编译程序将产生实际存储地址（绝对地址）的目标代码。（逻辑地址和物理地址一样）

装入程序按照装入模块中的地址，将程序和数据装入内存。

装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对程序和数据的地址进行修改。

通常在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。

4.2.1.2 可重定位装入方式(Relocation Loading Mode)

重定位（地址映射/地址变换）

经编译得到的目标模块中为相对地址（通常从0开始），即地址都是相对于0开始的。
装入模块中的逻辑地址与实际装入内存的物理地址不同。
装入内存时，相对地址（数据、指令地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为重定位。

重定位的分类

静态重定位

地址变换是在装入内存时一次完成的，且以后不能移动。
物理地址=相对地址+内存中的起始地址
优点：不需硬件支持，可以装入有限多道程序。
缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享。

动态重定位

动态运行时装入方式(Denamle Run-time Loading) ：装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行。在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为动态重定位。
最简单的办法是利用一个重定位寄存器(RR)。该寄存器的值是由进程调度程序根据作业分配到的存储空间起始地址来设定的。
在具有这种地址变换机构的计算机系统中，当执行作业时，不是根据CPU给出的有效地址去访问主存，而是将有效地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。

采用动态重定位技术后，程序中所有指令和数据的实际地址是在运行过程中最后访问的时刻确定的。也就是说，在作业运行过程中临时申请分配附加的存储区域或释放已占用的部分存储空间是允许的。

4.2.2 程序的链接

链接程序的功能，是将经过编译后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。根据链接时间的不同，可把链接分成如下三种：

4.2.2.1 静态链接

(Static Linking)：在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开。

说明：将几个目标链接装配成一个装入模块时，需解决以下两个问题：

将相对地址进行修改。即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址。
变换外部调用符号。即将每个模块中所用的外部调用符号，都变换为相对地址。 这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。

4.2.2.2 装入时动态链接(Load-Time Dynamic Linking)

用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。

即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将其装入内存。

优点：

便于软件版本的修改和更新。只需修改各个目标模块，不必将装入模块拆开，非常方便。 便于实现目标模块共享。即可以将一个目标模块链接到几个应用模块中，从而实现多个应用程序对该模块的共享。

4.2.2.3 运行时动态链接(Run-Time Dynamic Linking)

采用装入时动态链接方式，虽然可将一个装入模块装入到内存的任何地方，但装入模块的结构是静态的，

表现在：进程（程序）在整个执行期间，装入模块是不改变的；
每次运行时的装入模块是相同的。并且事先无法知道本次要运行哪些模块，只能将所有可能要运行的模块在装入时全部链接在一起，而实际上往往有些目标模块根本不会运行。

采用运行时动态链接可将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并链接到调用模块上。

凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

运行时动态链接是目前最常使用的链接方式。

4.3 连续分配存储管理方式

连续分配指为用户程序分配一个连续的内存空间。

程序空间本来就是连续的。

用连续的内存装入连续的程序，减少管理工作的难度。

内存分为两个区域：系统区，用户区。

连续分配的三种方式

单一连续分配方式
分区式分配方式

固定分区/动态（可变）分区/可重定位分区分配

可重定位分区分配

4.3.1 单一连续分配方式

单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用。应用程序装入到用户区，可使用用户区全部空间。

4.3.2 固定分区分配

将内存用户空间划分为若干个固定大小的区域，每个区域称为一个分区（region），在每个分区中只装入一道作业 ，从而支持多道程序并发设计。

由于这些存储区域是在系统启动时划定的，在用户作业装入及运行过程中，其区域的大小和边界是不能改变的。

固定式分区的两种划分方式

分区大小相等
分区大小不等

分区说明表

为了实现这种固定分区的分配，系统需要建立一张分区说明表。这个分区说明表指出可用于分配的分区数以及每个区的大小、起始地址及状态。

内存分配过程当有作业要装入内存时，内存分配程序检索分区说明表，从中找出一个尚未使用的满足大小要求的分区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。

内存中已分配给用户但未被利用的区域称为 “内零头”（内碎片）。固定分区分配有内零头产生。

优点：易于实现，开销小。

缺点：内碎片造成浪费/分区总数固定，限制了并发执行的程序数目。/存储空间的利用率太低。

采用的数据结构：分区表－记录分区的大小和使用情况

4.3.3 动态分区分配

动态分区分配是指根据进程的实际需要，动态地为之分配连续的内存空间。即分区的边界可以移动，分区的大小是可变的。 动态分区又有两种不同选择，一种是分区的数目固定大小是可变的，而另一种则允许分区的数目和大小都是可变的。 为了说明它们之间的重要差异，我们考虑一个具有256K字节存储器的系统。

注意：在每个分区中只能装入一个作业

4.3.3.1 分区分配中的数据结构

4.3.3.2 分区分配算法

系统运行一段时间后，在整个存储空间内将出现许多大小不等的区域，有的仍被作业进程占用，有的则因作业已退出系统而成为可用于再分配的区域。

现在假设有一个新的作业需调入主存，如何为其选择一个合适的区域？

4.3.3.3 最佳适应算法（BF:Best Fit）

空闲分区按容量递增的方式形成分区链，找到一个最接近目标大小的满足要求的空闲分区。（外部碎片过多）

就是为一作业选择分区时总是寻找其大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的零头最小。

优点：如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。

为了加快查找速度，应将存储空间中所有的空白区按其大小递增的顺序链接起来，组成一空白区链(Free List)。

缺点：采用最佳适应算法，在每次分配时，总是产生最小的空白区。因此，经过一段时期后，存储空间中可能留许多这样的空白区，由于其太小而无法使用。为了改善这种情况，在该算法中设置一参数G，用它来确定最小分区的大小。当选择一个分区时，如果选中的空白区与要求的大小之差小于G，则不再对它划分，而把整个这个空白区分配给申请的作业。（即当零头小于标准值时，即划分后无法使用，那么就将整个空白区分配给作业，这样会产生内零头）

最佳适应算法的另一缺点是：在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。所以，这种算法乍看起来是最佳的，其实则不然。

4.3.3.4 最坏适应算法（WF:Worst Fit）

空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，即挑选出最大的分区。（对大进程不利）

4.3.3.5 首次适应算法（First Fit：FF)

每个空白区按其在存储空间中地址递增的顺序链在一起，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大。

和上述算法一样，这个选择的空白区被分成两部分。一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。显然，这个算法倾向于优先利用存储空间中低址部分的空白区。

主要优点：算法简单，查找速度快；留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。

主要缺点：这种算法常常利用一个大的空白区适应小作业的请求，从而留下一些较小的无法用的空白区，存储空间利用率不高；而且，由于所有的请求都是从空白区链的始端开始查找，因而这些小而无用的空白区集中在这个链的前端，相应地，一些较大空白区在链的尾端才能发现，这种情况将使找到合适空白区的速度降低。

4.3.3.6 内零头和外零头

内存分配性能评价的一类重要指标

内零头(Internal Fragment)

已分配给用户但用户没有使用的空间
“多分配的空间”

外零头(External Fragment )

没有分配但无法分配的空间
太小而无法分配，“分不出去的空间”

单一连续分配有较大的内零头

分区分配有小于一个分区的内零头

4.3.3.7 下次适应算法(NF:Next Fit)

由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找。

也被称为带旋转指针的首次适应算法(Next Fit with Roving Pointer)。为此，我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。显然，采用这一策略后，存储空间的利用更加均衡，而不至于使小的空白区集中于存储器的一端。但是，在存储器的另一端也不可能保留大的空白块，因此，当需要获得相当大的空白区时，能满足的可能性减少了。

4.3.3.8 快速适应算法（QF:Quik Fit）

将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。这样，系统中存在多个空闲分区链表；

同时，在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。

分配过程：根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可

优点：

查找效率高。

该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。

缺点：

在分区归还主存时算法复杂，系统开销较大。

该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重。

4.3.4 分区分配操作

涉及动态分区的主要操作有分配内存和回收内存。这些操作是在程序接口中通过系统调用发出的。

4.3.4.1 分配内存

分配内存：向操作系统提出一特定存储量的请求。通常，它并不要求这个分配的存储区域限于特定的位置，但是，这个区域必须是连续的。

系统利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。

请求的分区大小为u.size
表中每个空闲分区的大小为m.size
size是事先规定的不再切割的剩余分区的大小

4.3.4.2 回收内存

进程用于归还一个不再需用的存储区域。

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点。

在回收一个分区时，一个回收的分区与空白区邻接的情况有四种，对这四种情况分别作如下处理：

4.3.5 伙伴系统

4.3.6 哈希算法

利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张哈希表，以空闲分区大小为关键字，每一个表项记录了一个对应的空闲分区链表表头指针。

当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

4.3.7 可重定位分区分配

4.3.7.1 紧凑

可变式分区分配策略是在装入作业时根据其要求量为其划定相应的区域。这种分配策略，消除了固定式分区分配造成的“内零头”，但不可避免地在存储空间中造成“外零头”，为了进一步提高存储器的利用率，必须设法减少由于外零头造成的浪费。一个最简单而直观的解决零头问题的办法是，定时地或者在内存紧张时，把存储空间中的空白区合并为一个大的连续区。

实现方法：将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区。这种技术称为存储器的“紧凑”

一个较实用且可行的办法是采用动态重定位技术。一个作业在主存中移动后，只要改变重定位寄存器中的内容即可。

4.3.7.2 动态重定位

在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。

程序在执行时，真正访问的内存地址=相对地址+重定位寄存器中的地址。

（这里应该是1500访问吧？）

4.3.7.3 动态重定位分区分配算法

4.4 基本分页存储管理方式

离散分配方式的引入

连续分配方式会产生内/外零头
为解决零头问题又要进行紧凑等高开销活动

什么是离散分配

程序在内存中不一定连续存放

根据离散时的基本单位不同，可分为三种：

分页存储管理
分段存储管理
段页式存储管理

4.4.1 分页存储管理基本思想

离散的基础

分页(Pages)：将程序地址空间分页
分块(Frames)：将内存空间分块

离散分配的体现

内存一块可以装入程序一页
连续的多个页不一定装入连续的多个块中
注：系统中页块的大小是不变的。

离散分配的优点

没有外零头 不受连续空间限制，每块都能分出去
仅有小于一个页面的内零头

程序大小一般不是页大小的整数倍。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头”。

4.4.2 分页存储管理的基本方法

程序空间逻辑空间相对地址转到内存空间物理空间绝对地址

如何建立程序空间与主存空间的映射

如何进行地址变换：从程序逻辑地址到内存物理地址

4.4.2.1 页面与物理块

页面或页(Page)：把每个进程的逻辑地址空间分成一些大小相等的片。

物理块或页框(Page Frame)：内存空间也分成与页相同大小的若干存储块。在为进程分配存储空间时，总是以页框为单位。

例如：一个作业的地址空间有m页。那么，只要分配给它m个页框，每一页分别装入一个页框内即可。这里，并不要求这些页框是连续的。
说明： ⑴从0开始编制页号，页内地址是相对于0编址； ⑵在进程调度时，必须把它的所有页一次装入到主存的页框内；如果当时页框数不足，则该进程必须等待，系统再调度另外的进程。（纯分页方式）

页面大小的选择

页面大小由机器的地址结构决定。某一机器只能采用一种大小的页面。

小页面
大页面
页面的大小通常在1KB~8KB之间。

4.4.2.2 实现分页存储管理的数据结构

页表：每个进程对应 1 个页表，描述该进程的各页面在内存中对应的物理块号。

页表中包括页号、物理块号（还可有存取控制字段，对存储块中的内容进行保护）。
注意：全部页表集中存放在主存的系统专用区中，只有系统有权访问页表，保证安全。（系统调度）

作业表：整个系统1张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。

空闲块表：整个系统1张，记录主存当前空闲块。

4.4.2.3 地址结构

地址空间为程序限定的空间。

物理空间为内存限定空间。

在页式管理系统中将地址空间分成大小相同页面。将内存空间分成与页面相同大小的存储块（页框）。

在分页存储管理方式中，任何一个逻辑地址都可转变为：页号+页内位移量。页号、位移量的划分是由系统自动完成的，对用户是透明的。

页内位移量即代表了页面大小（因为是逻辑地址，都是相对于0来写的）

页号的数目可以代表页面的数目

4.4.2.4 分页存储管理的逻辑地址表示

设有一逻辑地址A，页面大小为L，则在分页存储管理方式中，它的地址被转换：

如有逻辑地址为：2170，页面大小为1KB，则P=INT[2170/1024]=2；W=2170 MOD 1024=122

这个地址的变换通常由系统中的某些硬件完成。

任何一个逻辑地址都可转变为：页号+页内位移量。（地址为2进制，首先是8进制→2进制，如何又因为每一块是1KB，所以10位为页内位移量，剩下为页号）

如果需要做的话，按照上面的先换算成十进制。页号就是地址/页面大小

4.4.3 地址变换机构

地址变换机构的功能：是将用户的逻辑地址转变为内存中的物理地址

逻辑地址由页号和页内位移量组成。

页的大小和内存物理块的大小是相同的，所以页内位移量即为物理块内位移量。

关键是页号到物理块号的转换，由页表完成。

4.4.3.1 基本的地址变换机构

使用寄存器存放页表

速度快，成本高。特别对于大的系统，页表很长，不可能都用寄存器实现。

一般系统，将页表存储在内存中

设置一个页表寄存器（PTR），记录当前运行的进程的页表在内存中的始址和页表长度。（平时存于PCB中，要运行时才装入PTR中）

分页系统中的地址变换过程如下

根据逻辑地址,计算出页号和页内偏移量；（页内偏移量=物理偏移量）
从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；（物理块号）
用页框号乘以页面大小获得其对应的起始地址（页面大小=页框大小），并将其送入物理地址的高端。
将页内偏移量送入物理地址低端，形成完整的物理地址。

分析：

内存空间大小就是物理地址可以表示的范围，物理地址占20位，那么内存空间大小就是2^20=1MB

(10位地址，可以访问2^10=1KB内存；20位地址，可以访问2^20=1MB内存；30位地址可以访问2^30=1GB内存)

页面大小位1KB(10根地址线来寻找，即10位)，所以逻辑地址一共16位。每个作业的最大长度，~~2^20/2^6=2^14=16KB~~ 每个作业的最大长度即逻辑地址可以访问的地址区间，就是2^16=64KB

全部化成十进制，H代表地址是十六进制的。0420H=1056,1024≤1056<2048,或者说页号=1056/1024=1，页内偏移量=1056 mod 1024=32.一号页面对应7号存储块，页框号*页面的大小放在物理地址的高端，偏移量放在低端。7*1KB+32=7*1024+32

先判断逻辑地址在第几页面。因为一个页面大小为1KB，所以0~999为第0页面，1K~2K-1是第一页面。2K~3K-1是第二页面。在第一页面，页内偏移量是32.对应第7物理块，物理地址为物理号*物理块大小+偏移量。

作业空间：8K，页面大小2K，所以一共有4页。又因为已知页框号，所以可以得出页表。

相对地址=逻辑地址=（4000），就要算一下这个是在哪一页。（2K≤4000<4k-1）,所以在页面1，对应的页框号为3.偏移量为4000-2K=1952（字节）所以地址=3*2K+1952=8096

同理数据存放的逻辑地址为2500，属于页面1，偏移量为2500-2K=452，对应的物理块号为3.所以物理地址为3*2K+452=6596

每页2K，作业空间为8K.~~从逻辑地址4865=0100100001100101，2K就是11位地址，~~这里注意是给出了地址（地址的单位默认为B）所以这里计算页号=4865/2048=2，偏移量是4865 mod 2048=769，对应的物理块号为6.所以物理地址=6*2048+769=13057

4.4.3.2 具有快表的地址变换机构

分页系统中处理机每次存取指令或数据至少需要访问两次物理内存：

第一次访问页表，以得到物理地址(页号→页框号，页内偏移→块内偏移，物理地址=页框号*页面大小+偏移量)
第二次访问物理地址，以得到数据。

为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表TLB(Translation Lookaside Buffer)，或联想存储器（Associative Memory）。

工作原理：快表的工作原理类似于系统中的数据高速缓存(cache)，其中专门保存当前进程最近访问过的一组页表项。

地址转换过程

根据逻辑地址中的页号，查找快表中是否存在对应的页表项。
若快表中存在该表项，称为命中（hit），取出其中的页框号，加上页内偏移量，计算出物理地址。
若快表中不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号。同时，更新快表，将该表项插入快表中。并计算物理地址.

4.4.3.3 访问内存的有效时间(EAT)

定义：从进程发出指定逻辑地址的访问请求，经过地址变换，再到内存中找到对应的物理单元并取出数据，所花费的总时间。

如检索快表时间为20 ns，访问内存为100 ns。

若能在快表中检索到CPU给出的页号，则CPU存取一个数据共需120 ns。（计算物理地址后的取数据的一次访存100+20）
否则（在快表中不能检索到页号），需要220 ns的时间(20+100*2（两次访存，访问页表，取数据）)。
当访问联想存储器时的命中率分别为0%，50%，80%，90%，98%（这个命中率可以理解为使用快表的概率）时，其有效访问时间如下表所示：

选用8～12项组成的联想存储器，并采用适当的替换策略，在联想存储器中匹配成功的可能性可达80%～90%。可见，由于增设了联想存储器，访问内存的有效时间减少（不设联想存储器EAT=220ns。）

4.4.4 两级和多级页表

处理大页表的存储与检索

采用离散分配方式来解决难以找到一块连续的大内存空间的问题，（即引入两级页表）；
只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

4.4.4.1 两级页表

对于要求连续的内存空间来存放页表的问题：

可将页表进行分页，并离散地将各个页面分别存放在不同的物理块中

同样也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表分页的物理块号。

对于4GB(2^32)的进程，页面大小为4KB(2^12) ,若采用二级页表，则对应的二级页表结构如下：

把页表本身按固定大小分成为一个个页面(页表大小为 2^12)，每页有2^10=1K个页表项(每个页表项4Byte)，最多允许有2^10=1K个页表分页。（页面→页表分页）

为了对1K个页表分页进行管理和索引查找，设置一个页表目录，又称之为外层(顶级)页表，该页表包含有1K个页表项，分别指出每个页表分页所在物理块号和其他有关状态信息。（每个页表项为4B，所以外层页表为4KB）

每个进程有一个外层页表，它的每个页表项映射一个页表，存放某页表分页的首址。逻辑地址结构如下：

说明：利用离散分配方法实现的两级页表只是解决了大页表无需大片连续存储空间问题，但并未减少用较少内存去存放大页表问题，有关此类问题的成功解决方案放在虚拟存储器管理中。

4.4.4.2 多级页表结构

64位的机器，采用的是多级（4级以上）页表结构。

对于大地址空间问题：多级页表变得繁琐。逻辑 (虚拟) 地址空间增长速度快于物理地址空间

4.4.4.3 反置页表（IPT）

不让页表与逻辑地址空间的大小相对应

让页表与物理地址空间的大小相对应

IPT要解决的问题

逻辑空间越来越大，页表占内存也越来越大，为了解决大页表问题占内存多现象，减少内存开销，避免一个进程一个页表。

IPT的思想

IPT是为主存中的每一个物理块建立一个页表项并按照块号排序；
该表每个表项包含正在访问该物理块的进程标识、页号及特征位,用来完成主存物理块到访问进程的页号的转换。

反置页表地址转换过程如下

给出进程标识和页号,用它们去比较IPT,若整个反置页表中未能找到匹配的页表项,说明该页不在主存,产生请求调页中断,请求操作系统调入;否则，该表项的序号便是物理块号块号加上位移,便形成物理地址。

4.5 基本分段存储管理方式

4.5.1 分段式存储管理方式的引入

方便编程

分段共享：段是信息的逻辑单位，可以为共享过程建立一个独立的段，更便于实现程序和数据的共享。
分段保护：对内存中的信息的保护，同样也是对信息的逻辑单位进行保护。
动态链接：程序运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段调入内存并进行链接。
动态增长

4.5.2 分段式存储管理的基本原理

4.5.2.1 分段

作业地址空间按逻辑信息的完整性被划分为若干个段

每段有段名（或段号），每段从0开始编址；

段内的地址空间是连续的。

许多编译程序支持分段方式，自动根据源程序的情况产生若干个段。

这些符号程序经汇编和装配后，指令和数据的单元地址均由两部分构成：一是表示段名的段号S；一是位移量W，即段内地址。所以，在分段系统中的地址结构有如下形式：

最大段长为64KB=2^16，所以段内地址为0~15位

一旦段号字段和位移量字段的长度确定后，一个作业地址空间中允许的最多段数及段的长度也就限定了。

分段管理

管理由若干分段组成的作业，且按分段来进行存储分配。
实现分段管理的关键在于，如何保证分段(二维)地址空间中的一个作业在线性(一维)的存储空间中正确运行。也就是说，如何把分段地址结构变换成线性的地址结构，和分页管理一样，可采用动态重定位技术，即通过地址变换机构来实现。

4.5.2.2 段表

为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。

应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。（对比页表；页号，页框号）

通常将段表放在内存中，执行中的进程可通过查找段表找到每个段所对应的内存区。

实现从逻辑段到物理内存区的映射。

分段制造了二维空间，而内存是一维的

作业分段地址空间和主存存储空间之间通过段表映射的情况

4.5.2.3 地址变换机构

根据段表寄存器的内容找到该作业的段表地址；

利用有效地址中的段号2作为检索段表的索引，得到该段在主存的起始地址；(10K=10240)

将段的主存起始地址和位移量W相加，即得访问主存的物理地址。(10240+100=10340)

Q:若段表放在内存中，每访问一个数据需要访问内存几次？

A：2次。可设置联想存储器（快表），以提高访问速度。

优点：没有内碎片，外碎片可以通过内存紧凑来消除。便于改变进程占用空间的大小。

缺点：进程全部装入内存。

4.5.3 段的共享和保护

分页系统实现程序段的共享较为困难。

分段易于实现段的共享和段的保护。

可重入代码（Reentrant Code, 纯代码）

是一种允许多个进程同时访问的代码（可共享），且是一种不允许任何进程对其进行修改的代码。

4.5.4 段页式存储管理

原理：分段和分页相结合

先将用户程序分段，每段内再划分成若干页，每段有段名（段号），每段内部的页有一连续的页号。

内存划分：按页式存储管理方案。

内存分配：以页为单位进行离散分配。

逻辑地址结构

地址变换

控制寄存器、段表、页表与主存空间的关系

4.5.4.1 地址变换

首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。

然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。

再根据逻辑地址中指定的页号检索该页表，找到对应页所在的物理块号。

最后，用物理块号加上逻辑地址中指定的页内偏移量，形成物理地址。

段页式系统的地址变换机构

在段页式存储管理方式中，每访问一次数据，需访问3次内存。

第一次：访问内存中的段表
第二次：访问内存中的页表
第三次：访问相应数据。

解决方式:可以设置快表，表项应包括段号、页号、物理块号。

评价：综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进行程序设计。但是，实现段页式存储管理系统需要增加硬件成本，系统的复杂度和管理开销也大大增加。因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统。

4.5.5 对换（Swapping）

对换指把内存中暂不能运行的进程或暂时不用和程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。

对换是系统行为，是提高内存的利用率的有效措施。

常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。

实现：可在系统中设一对换进程，以执行换进内存、换出至外存操作。

分类

整体对换（进程对换）：对换以整个进程为单位，用于分时系统，以解决内存紧张的问题；
“页面对换/分段对换”：对换以“页”或“段”为单位进行“部分对换”，该方法是实现请求分页及请求分段存储器的基础，支持虚存系统。

OS需要的功能

对换空间的管理、进程的换入、进程的换出

4.5.5.1 对换空间的管理

外存可以分为文件区和对换区：

文件区存放文件，管理侧重于提高存储空间利用率，应用离散分配方式；

即一个文件可根据当前外存的使用情况，被分成多块，分别存储到不邻接的多个存储区域中，用指针相连。

对换区存放从内存中进进出出的文件，交换较频繁，侧重于对换这个操作，应用连续分配方式

即把一个换出的进程存放到一个连续的存储空间中。
对换区空闲盘块的管理：空闲分区表或空闲分区链。在空闲分区表中的每个表目应包含两项，即对换分区首址和对换区长度，它们的基本单位都是盘块。
分配：连续分配，算法：可以是首次适应算法、循环首次适应算法和最佳适应算法。
回收：四种情况

4.5.5.2 进程的换出与换入(由对换进程完成)

换出（swap out）

选择：首先选择阻塞或睡眠状态的进程，若有多个，按优先级由低到高进行选择。若没有此状态进程，则选择就绪状态的，仍然按优先级由低到高进行选择。
为避免某进程被频繁的换入换出，还应考虑进程在内存中的驻留时间，优先选择驻留时间长的进程。

换入（swap in）

从PCB集合中查找“就绪且换出”的进程，有多个，则选择换出时间最长的。
根据进程大小申请内存，成功则读入，否则要先执行换出，再换入。
若还有可换入进程，则转向①。直至无“就绪且换出”进程或无法获得足够内存空间为止。

4.6 虚拟存储器的基本概念

4.6.1 虚拟存储器的引入

4.6.2 局部性原理

程序执行的局部性原理：程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分（执行局部有限）；相应的，它所访问的存储空间也局限于某个区域。（访问局部有限）

因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。

4.6.3 虚拟存储器的定义

当进程运行时，先将当前要运行的部分程序装入内存，其他部分暂留外存；

当要执行的指令不在内存时，处理器发生中断，通知操作系统将所缺部分从外存调入内存，保证程序继续执行；

当内存不足时，允许程序部分换入、换出。

虚存实现的理论依据：程序执行的局部性原理

如何将程序划分成部分：分页/分段

4.6.3.1 虚拟存储器的基本工作情况

基于局部性原理。一个作业运行前，仅将那些当前要运行的页面（段）装入内存启动运行，其余暂在外存。

若运行所需页面（段）不在内存，则利用请求调页（段）功能将其调入内存。

若此时内存满，则利用置换功能，将内存中暂时不用的部分页面（段）调至外存，再将所需页面（段）调入。

这样，可实现大程序在小内存中运行，也可实现内存中同时装入更多的进程并发执行。

4.6.3.2 虚拟存储器定义

虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

其逻辑容量由内存容量和外存容量之和所决定

其运行速度接近于内存速度，而成本却又接近于外存。

4.6.4 虚拟存储器的实现方法

请求分页系统

它是在纯分页系统的基础上增加了请求调页、页面置换两大功能所形成的页式虚拟存储系统。
系统提供的硬件支持：

请求分页的页表机制
缺页中断机构
地址变换机构
（软件支持）OS支持

请求分段系统

它是在纯分段系统的基础上增加了请求调段、分段置换两大功能所形成的段式虚拟存储系统。
系统提供的硬件支持

请求分段的段表机制
缺段中断机构
地址变换机构
（软件支持）OS支持

段页式虚拟系统

目前，许多虚拟存储管理系统是建立在段页式系统的基础上的，通过增加了请求调页、页面置换两大功能所形成的段页式虚拟存储系统。

4.6.5 虚拟存储器的特征

虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上。

多次性

多次性是指一个作业被分成多次调入内存运行。

对换性

对换性是指作业的运行过程中进行换进、换出。换进和换出能有效地提高内存利用率。

虚拟性

虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

4.6.6 虚拟存储的典型问题：抖动（thrashing）

当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。

抖动的定义：如果系统花费大量的时间把程序和数据频繁地换入和换出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。

根本原因：选择的页面或段不恰当。

4.7 请求分页存储管理方式

工作原理

作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由OS将其从辅存调入主存，如果内存无空闲块，则根据某种算法选择一个页淘汰以便装入新的页面。

优点

利用这种方法，可使更多的作业处于就绪状态，且能支持比主存容量大的作业在系统中运行。从而提高存储空间利用率。

硬件支持

请求分页的页表机制
缺页中断机构
地址变换机构

4.7.1 请求分页中的硬件支持

4.7.1.1 请求分页的页表机制

在虚拟存储系统中的所有的页表，其页描述子有了新的扩充，这是进行地址变换机构所必须的，增加四个信息标识位。

状态位（存在位）D:用于说明该页是否已调入内存，供程序访问时参考；

D=0，该页不在内存
D=1，该页在内存

访问位A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。

A=0，该页未被访问
A=1，该页被访问

修改位M：用于表示该页在调入内存后是否被修改过，也是提供给置换算法在换出页面时是否将该页面写回外存作参考。

M=0，该页在内存中未被修改
M=1，该页在内存中已经被修改

外存地址：用于指出该页在外存上的地址，供调入该页时使用。

4.7.1.2 缺页中断机构

由上述页表机制知道，状态位记录了访问页面是否在内存。在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断，也称为缺页故障。OS接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。

缺页中断是一种特殊的中断，与一般中断相比

在指令执行期间产生和处理中断信号。通常，CPU只能在指令之间接受中断；然而，一个缺页中断要求在指令执行中间得到服务，即发现所要访问的指令或数据不在内存时产生缺页中断并处理。
再则，一条指令可能引起多次不同的页面故障。下图是一个十分极端的例子，这条指令的执行需要访问六个不同的页面，对它们的访问都可能引起缺页中断

由于缺页中断的独特性，系统中需要提供硬件寄存器或其它机构，在出现页面故障时，保存部分完成的指令的状态。此外，还需要使用一条特殊的返回指令，确保在出现缺页中断处恢复该指令的处理。

4.7.1.3 缺页中断处理过程

4.7.1.4 地址变换机构

该缺页如果修改过，就需要将该页写回辅存后再在内存里该页。如果没有被修改过，那么直接将该页装入内存。

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

4.7.2.1 最小物理块数的确定

给每个进程所分配物理块数目越少，则进程执行中的缺页率越高，进程的执行速度也减慢。

最小物理块数：是指能保证进程正常运行所需的最少物理块数。若系统为某进程所分配的物理块数少于此值时，进程将无法运行。

进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。

对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。
如果该机器允许间接寻址时，则至少要求有物理块数为3。
对于前面所介绍的在缺页中断机构中要发生6次中断的情况，至少要为每个进程分配6个物理块，以装入6个页面。

物理块的分配策略

固定分配局部置换（Fixed Allocation，Local Replacement）

为每个进程分配一定数目的物理块，在整个运行期间都不再改变。
实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。若太少，会频繁地出现缺页中断，降低了系统的吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而可能造成CPU空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。

可变分配全局置换（Variable Allocation，Global Replacement）(常用方式)

在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。
当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。
这样，凡产生缺页（中断）的进程，都将获得新的物理块；
仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。

可变分配局部置换（Variable Allocation， Local Replacement ）

为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。
在进程运行过程中统计进程的缺页率，如果缺页率高，则为其增加一定的内存页，否则适当减少其内存的页面数。
当需要置换时只从本进程的内存页中选择，但此方式实现复杂，对进程的缺页情况的统计需要额外的开销。

物理块的分配算法：采用固定分配策略时，可采用下面的几种方法

平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。
按比例分配算法：根据进程的大小按比例分配物理块的算法。

考虑优先权的分配算法：通常采取的方法是把内存中可供分配的所有物理块分成两部分：

一部分按比例地分配给各进程；
另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。
在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配物理块。

4.7.3 调页策略

4.7.3.1 系统应当在何时把一个页面装入内存？

预调页 (Prepaging)

可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。
处理过程

当进程创建时，预先为进程装入多个页面。
缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。

评价:若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。预调页的成功率仅约50％。

请求调页 (Demand Paging)

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

4.7.3.2 从何处调入页面？

在请求分页系统中的外存分为两部分

用于存放文件的文件区
用于存放对换页面的对换区。

通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘I/O 速度比文件区的高

当缺页请求发生时，系统从何处将缺页调入内存有三种情况

系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页的速度。
系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；

而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。
但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。

UNIX方式。由于与进程有关的文件都放在文件区，应从文件区调入。故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。

4.7.3.3 页面调入过程？

每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断。

中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。

如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果此页已被修改，则必须将它写回磁盘。

然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。

形成所要访问数据的物理地址，再去访问内存数据。

4.7.3.4 页面置换算法？

页面置换算法的选择，是虚拟存储器管理系统的核心问题。

它的实质是，为系统提供一种方法，当从主存中需要换出页面时，应避免选择那些不久再次要求访问的页面。

置换算法的选择在一定程度上取决于可用的硬件设施。

4.7.4 最佳(优)置换算法(OPT:Optimal)

最理想的页面置换策略是：从主存中移出永远不再需要的页面；如无这样的页面存在，则应选择最长时间不需要访问的页面。

根据后面的请求来置换相对来说最近用不到的页面，如无这样的页面存在，则应选择最长时间不需要访问的页面。

6次页面置换+3次（最初存储块里面没有页面的”页面置换”）=9次缺页中断

访存次数：也就是上面的页面请求次序的数字的个数

4.7.5 先进先出（FIFO）页面置换算法

该算法的实质是：总是选择作业中驻留时间最长(即最老)的一页淘汰。即：先进入主存的页面先退出主存。

算法实现：算法实现比较容易，如分配给一个作业的存储块数为m，只需建立一个m个元素的队列表Q(0)、Q(1)、…、Q(m-1)和一个替换指针。该队列是按页面调入主存的先后顺序排列的，而指针始终指向最早调入主存的一页。

缺页中断数=12+3=15，访存次数=20

4.7.6 最近最久未使用（LRU）置换算法

LRU:Least Recently Used

基本思想:利用局部性原理，根据一个作业在执行过程中过去的页面访问踪迹来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。

实质是：当需要置换一页面时，选择在最近一段时间内最久不用的页面予以淘汰。

实现这种技术，是通过周期性地对“页面访问”位进行检查，并利用它来记录一个页面自上次访问以来所经历的时间 t ，并选择 t 为最大的页予以淘汰。

这里怎么看呢？看两个竖条的间隔。

当2请求时，判断t。t为一个页面自上次访问以来所经历的时间。页面7距离2就是3，页面0距离2就是2，页面1距离2就是1.所以淘汰7.
3请求时，2距离3为2.0距离3为1，1距离3为3。所以置换1.4距离2为4，4距离0为1，4距离3为2，所以置换2.2距离4为1，2距离0为2，2距离3为3，所以距离3……
缺页中断数=9次页面置换+3次空白填充=12，访问次数20，所以缺页率为12/20=0.6

OPT这里给的答案：在2需要置换的时候，选择的是置换3；1需要置换的时候选择的是置换2，根据我们的法则根据后面的请求来置换相对来说最近用不到的页面，如无这样的页面存在，则应选择最长时间不需要访问的页面。这里应该是默认使用之后，后面就不再用到，所以选择的是最近使用的。

LRU算法的硬件支持

寄存器。用于记录某进程在内存中各页使用情况。

第六个页面是最小数值，为最近最久未使用的页面

栈。用于保存当前进程使用的各个页面的页面号。

每当进程访问时某页面时，便将该页面号从栈中移出，压入栈顶。这样栈底则是最近最久未使用页面的页面号。例如:假定一进程访问某页面的时页面号如下(5个存储块）：

最少使用置换算法LFU(Least Frequently Used（最少使用置换）)

选择到当前时间为止被访问次数最少的页面被置换（即寄存器中含1的数目最少）。
基本方法

记录每个页面的访问次数，最少访问的页面首先考虑淘汰
实际采取方法(LRU:最近最久未使用，即寄存器数更小的；LFU即1最少的)

4.7.7 Clock置换算法

4.7.7.1 简单的Clock置换算法（NRU）

当采用简单clock算法时，为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。

置换程序从上次停止位置开始检查页面的访问位，如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会。

由于该算法是循环地检查各页面的使用情况，故称为clock算法。置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法NRU(Not Recently Used（最近未使用）)。

通过指针链接成环，此时2，3，1页面的A都为1.5页面请求置换的时候，所有A=1,所有无法置换，第二轮扫描将所有A都变成0。然后回到原位，5置换2（A置1），2置换3（A置1）

4.7.8 改进型Clock置换算法

系统把一个页面移出内存时，如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则(驻存期间被修改)系统必须把它写回辅存。这表明，换出未修改过的页面比换出被修改过的页面开销小。

显然，我们可以依据上述结论改进CLOCK算法。改进后的CLOCK算法将在置换范围内首选满足下面条件的页面作为置换页面：

在最近没有被使用过；
在驻留内存期间没有被修改过的页面

执行步骤

从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M＝1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位A都置0。
（3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，~~并将所有的访问位复0~~。（根据第二步可以知道，此时所有A均为0）然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。