内存原理

基本内存原理

内存管理的环境

程序要运行，必须先加载到内存。

程序员面临的物理现实却是一个由缓存、主存、磁盘、磁带等组成的内存架构。在这个内存的现实架构中，缓存的特点是低容量（相对主存来说）、高速度、高价格；主存的特点则是中容量、中速度和中价格；磁盘则属于大容量、低速度、低成本的存储媒介；磁带则通常更持久但速度更慢。

很显然，这样一个存储架构与程序员或用户对内存的要求相差甚远。要以这个存储架构为基础来提供程序员所需的内存抽象，我们需要一个巧妙有效的内存管理机制。内存管理机制负责对内存架构进行管理，使程序在内存架构的任何一个层次上的存放对于用户来说都是一样的。用户无须担心自己的程序是存储在缓存、主存、磁盘还是磁带上，反正运行、计算、输出的结果都一样。而内存管理实现这种媒介透明的手段就是虚拟内存。

内存管理的目标

地址保护：一个程序不能访问另一个程序的地址空间
地址独立：程序发出的地址应与物理主存地址无关

虚拟内存的概念

一个程序如果要运行，必须加载到物理主存中。但是，物理主存的容量非常有限。因此，如果要把一个程序全部加载到物理主存，则我们所能编写的程序将是很小的程序。它的最大容量受制于主存容量（还要减去操作系统所占的空间和一些临时缓存空间）。另外，即使我们编写的每个程序的尺寸都小于物理主存容量，但还是存在一个问题：主存能够存放的程序数量将是很有限的，而这将极大地限制多道编程的发展。

那有没有办法在不增加成本的情况下扩大内存容量呢？有，这就是虚拟内存。虚拟内存的中心思想是将物理主存扩大到便宜、大容量的磁盘上，即将磁盘空间看做主存空间的一部分。用户程序存放在磁盘上就相当于存放在主存内。用户程序既可以完全存放在主存，也可以完全存放在磁盘上，当然也可以部分存放在主存、部分存放在磁盘。而在程序执行时，程序发出的地址到底是在主存还是在磁盘则由操作系统的内存管理模块负责判断，并到相应的地方进行读写操作。事实上，我们可以更进一步，将缓存和磁带也包括进来，构成一个效率、价格、容量错落有致的存储架构。即虚拟内存要提供的就是一个空间像磁盘那样大、速度像缓存那样高的主存储系统。如图11-3所示。而对程序地址所在位置（缓存、主存和磁盘）的判断则是内存管理系统的一个中心功能。

虚拟内存除了让程序员感觉到内存容量大大增加之外，还让程序员感觉到内存速度也加快了。这是因为虚拟内存将尽可能从缓存满足用户访问请求，从而给人以速度提升了的感觉。

操作系统在内存中的位置

内存管理的第一个问题是操作系统本身在内存中的存放位置。应该将哪一部分的内存空间用来存放操作系统呢？或者说，我们如何将内存空间在操作系统和用户程序之间进行分配呢？

最简单的方式就是将内存划分为上下两个区域，操作系统和用户程序各占用一个区域，如图11-4所示。

图 11-4 仅有RAM时操作系统与用户程序的内存分配

比较起来图11-4a的构造最容易理解。因为操作系统是为用户提供服务的，在逻辑上处于用户程序之下。将其置于地址空间的下面，符合人们的惯性思维。另外，操作系统处于地址空间下面还有一个实际好处：就是在复位、中断、陷入等操作时，控制移交给操作系统更方便，因为操纵系统的起始地址为0，无须另行记录
操作系统所处的位置，程序计数器清零就可以了。清零操作对于硬件来说非常简单，无须从总线或寄存器读取任何数据；而图11-4b的布置虽然也可以工作，但显然与人们习惯中操作系统在下的惯性思维不符。

由于现代的计算机内存除了RAM之外，可能还备有ROM。而操作系统既可以全部存放在ROM里，也可以部分存放在ROM里，这样又多出了两种分配方式，如图11-5所示。

图 11-5 备有ROM时操作系统和用户程序之内存分配

图11-5a模式下操作系统放在ROM里面的好处是不容易被破坏，缺点就是ROM要做得大，能够容纳整个操作系统。由于ROM比较贵，通常情况下是备有少量的ROM，只将操作系统的一部分放在ROM里，其余部分放在RAM里。因此，这两种分配模式以图11-5b为佳。

图11-5b分配模式还有另外一个好处：可以将输入输出和内存访问统一起来。即将输入输出设备里面的寄存器或其他存储媒介编入内存地址（在用户程序地址之上），使得访问输入输出设备如同访问内存一样。这种输入输出称为内存映射的输入输出。如果要访问的地址高于RAM的最高地址，则属于I/O操作，否则属于正
常内存操作。

这样，根据操作系统是否占用ROM或我们是否采用内存映射的输入输出来分，存在两种模式：

操作系统占用RAM的底层，用户程序占用RAM的上层。
操作系统占用RAM的底层和位于用户程序地址空间上面的ROM，用户程序位于中间。
- 没有使用内存映射的输入输出，ROM里面全部是操作系统。
- 使用了内存映射的输入输出，ROM的一部分是操作系统，另一部分属于I/O设备。
- 使用了内存映射的输入输出，ROM全部属于I/O设备。

单道编程的内存管理

固定地址的内存管理单元非常简单，实际上并不需要任何内存管理单元。因为程序发出的地址已经是物理地址，在执行过程中无须进行任何地址翻译。而这种情况的直接结果就是程序运行速度快，因为越过了地址翻译这个步骤。

当然，固定地址的内存管理其缺点也明显：第1个缺点是整个程序要加载到内存空间中去。这样将导致比物理内存大的程序无法运行。第2个缺点是，只运行一个程序造成资源浪费。如果一个程序很小，虽然所用内存空间小，但剩下的内存空间也无法使用。第3个缺点是可能无法在不同的操作系统下运行，因为不同操作系统占用的内存空间大小可能不一样，使得用户程序的起始地址可能不一样。这样在一个系统环境下编译出来的程序很可能无法在另一个系统环境下执行。

多道编程的内存管理

虽然多道编程可以极大地改善CPU和内存的效率，改善用户响应时间，但是天下没有免费的午餐，这种效率和响应时间的改善是需要付出代价的。

这个代价是什么呢？当然是操作系统的复杂性。因为多道编程的情况下，无法将程序总是加到固定的内存地址上，也就是无法使用静态地址翻译。这样我们就必须在程序加载完毕后才能计算物理地址，也就是在程序运行时进行地址翻译，这种翻译称为动态地址翻译。

固定分区的多道编程内存管理

固定分区的管理就是将内存分为固定的几个区域，每个区域的大小固定。最下面的分区为操作系统占用，其他分区由用户程序使用。这些分区大小可以一样，也可以不一样。考虑到程序大小不一的实际情况，分区的大小通常也各不相同。当需要加载程序时，选择一个当前闲置且容量够大的分区进行加载。

在这种模式下，当一个新的程序想要运行，必须排在一个共同的队列里等待。当有空闲分区时，才能进行加载。由于程序大小和分区大小不一定匹配，有可能形成一个小程序占用一个大分区的情况，从而造成内存里虽然有小分区闲置，但无法加载大程序的情况。如果在前面加载小程序时考虑到这一点，可以将小程序加载到小分区里，就不会出现这种情况（或者说至少降低这种情况发生的概率）。这样，我们就想到也许可以采用多个队列，即给每个分区一个队列。程序按照大小排在相应的队列里。

这样不同的程序有不同的对，就像在社会中不同的社会阶层有不同的待遇一样。当然，这种方式也有缺点，就是如果还有空闲分区，但等待的程序不在该分区的等待队列上，就将造成有空间而不能运行程序的尴尬处境。

地址翻译的方法

物理地址 = 虚拟地址 + 基址（程序所在区域的起始地址）

另外，由于有多个程序在内存空间中，我们需要进行地址保护。由于每个程序占用连续的一片内存空间，因此只要其访问的地址不超出该片连续空间，则为合法访问。因此，地址保护也变得非常简单，只要访问的地址满足下列条件即为合法访问：

基址 ≤ 有效地址 ≤ 基址+程序长度

由此可见，我们只需要设置两个端值：基址和极限，即可达到地址翻译和地址保护的目的。这两个端值可以由两个寄存器来存放，分别称为基址寄存器和极限寄存器。

那么我们怎么知道一个程序有多大呢？编译过后，我们就可以得到这个程序的大小。基址和极限是很重要的两个参数，只有内核能够改变它们。如果要切换程序，只需将保存基址和极限的寄存器的值按照新程序的情况重新设置即可。

动态地址翻译的优点

动态地址翻译虽然增加了系统消耗，不如静态地址翻译效率高，但其带来的优点远远超过静态地址翻译。

第1个优点是灵活。因为实施了动态地址翻译，我们就无须依赖编译器或加载器来进
行静态地址翻译，可以将程序随便加载到任何地方，极大地提高操作系统操作的灵活性。
第2个优点是，它是实施地址保护的“不二法门”。要想进行地址保护，就必须对每个访问地址进行检查，而动态地址翻译恰恰就能做到这一点。
第3个优点则更为重要，它使虚拟内存的概念得以实现。虚拟内存就是子虚乌有的内存，这个内存的空间可以非常大，比物理空间大很多。那么虚拟内存的根本是将内存扩展到磁盘上，就是将磁盘也当成内存的一部分。从这里我们可以获得一个重要的推论，就是一个程序可以一半放在磁盘上，一半放在内存上。这样，从物理上讲，一个程序发出的访问地址有可能在内存，也有可能在磁盘。

但是计算机怎么能知道这个地址所指向的数据在内存上还是在磁盘上呢？这无法在静态地址编译时就知道的。唯一的方法就是动态地址翻译。在每次内存访问的时候，虚拟地址就是用户每次看到的地址，这个地址只是一个抽象，它需要由内存管理单元进行翻译，变成物理内存地址才能使用。由于这个翻译是在程序执行
过程中发生，因此称为动态地址翻译。有了动态地址翻译，编译器和用户进程就再也不用考虑物理地址了。

在动态地址翻译环境下，一个虚拟地址仅在被访问的时候才需要放在内存里，在其他时候并不需要占用内存。由于动态地址翻译可以动态地改变翻译参数或过程，因此可以在程序加载到不同的物理位置时，或不同虚拟地址占用同一物理地址时，做出正确翻译。在使用基址和极限管理模式下，不同程序进入物理内存时，我们只需要变更基址和极限寄存器的内容即可。

非固定分区的内存管理

固定分区的缺点：

一是程序大小和分区大小的匹配不容易令人满意
二是很僵硬，如果有个程序比最大的分区大怎么办呢？
三是地址空间无法增长，如果程序在运行时内存需求增长怎么办？很容易想到固定分区为什么有这个缺陷，因为分区是固定大小。

非固定分区的思想很简单：除了划分给操作系统的空间外，其余的内存空间是作为一个整体存在的。当一个程序需要占用内存空间时，就在该片空间里面分出一个大小刚刚满足程序所需的空间；再来一个程序，则在剩下的空间里面再这样分出一块来。在这种模式下，一个程序可以加载到任何地方，也可以和物理内存一样
大。

非固定分区这种管理方式存在一个重大问题：如果程序在执行过程中需要更多空间，怎么办？解决的办法当然是在一开始给程序分配空间时就分配足够大的空间，留有一片闲置空间供程序增长用。

不过，在分配增长空间后需要考虑一个问题。一个程序的空间增长通常有两个来源：数据和栈。如何处理这两种空间增长的关系会对整个程序的扩展性产生影响。

最简单的方式是数据和栈往一个方向增长。这种模式下，我们事先给数据部分和栈部分分别留下增长空间。这样的优点是两者独立性高，缺点是空间利用率可能较低。
当然，我们可以通过移动栈底来解决上述问题。但这样成本就高了，而且十分复杂，容易出错。一个更简单的办法是让数据和栈往相反方向增长。这样，只要本程序的自由空间还有多余，不仅可以进行函数调用，又可以增加新的数据，可以最大限度地利用这片自由空间。

不过，这里还有个问题：操作系统怎么知道应该分配多少空间给一个程序呢？怎么知道该程序会进行多少层嵌套调用，产生多少新的数据呢？如果为保险起见分配一个很大的空间，就有可能造成浪费；而分配小了，则可能造成程序无法继续运行。那还有没有别的办法呢？有，给该程序换一个空间。就是当一个程序所占空间不够时，我们将其倒到磁盘上，再加载到一片更大的内存空间。这种将程序倒到磁盘上，再加载进内存的管理方式称为交换（swap）。

交换

交换就是将一个进程从内存倒到磁盘上，再将其从磁盘上加载到内存中的过程。这种交换的主要目的是为程序找到一片更大的空间，从而防止一个程序因空间不够而崩溃。交换的另一目的，是实现进程切换，也就是将一个程序暂停一会儿，让另一个程序运行。不过使用交换进行进程切换的成本颇高，一般不这样做。

交换和非固定分区一样，每个程序占用一片连续的空间，操作系统使用基址和极限来进行管理。但由于一个程序在执行过程中可能发生交换，其基址和极限均有可能发生变化。但这种变化对于内存管理来说，并不增加多少难度。只要每次加载程序的时候将基址和极限寄存器的内容进行重载即可

重叠

如果一个程序超过了物理内存，还能运行吗？答案也许出乎意料。能。这个办法就是所谓重叠（overlay）。重叠就是将程序按照功能分成一段一段功能相对完整的单元。一个单元执行完后，再执行下一个单元，而一旦执行到下一个单元，就不会再执行前面的单元。所以我们可以把后面的程序单元覆盖到当前程序单元上。这样就可以执行一个比物理内存还要大的程序。

但是这相当于把内存管理的部分功能交给了用户，是个很拙劣的方法。况且也不是每个人都能够将程序分成边界清晰的一个个执行单元的。而且，从根本上说，这不能算是操作系统提供的解决方案。

双基址

如果我们运行两个一样的程序，只是数据不同，我们自然想到能否让两个程序共享部分内存空间。但在基址极限这种管理模式下，这种共享无法实现。

那么有什么办法共享这段代码又不容易出错呢？答案就是设定两组基址和极限。数据和代码分别用一组基址和极限表示，这就解决了问题。

闲置空间管理

在管理内存的时候，操作系统需要知道内存空间有多少空闲。如何才能知道有哪些空闲呢？这就必须跟踪内存的使用。跟踪的办法有两种：

第1种办法是给每个分配单元赋予一个字位，用来记录该分配单元是否闲置。例如，字位取值0表示分配单元闲置，字位取值1则表示该分配单元已被占用。这种表示法就是所谓的位图表示法。

位图表示法的优点是直观、简单。在搜索需要的闲置空间时只需要找到一片连续0个数大于等于所需分配单元数即可。
另外一种办法是将分配单元按是否闲置链接起来，这种办法称为链表表示法。

图中的P代表程序，即当前这片空间由程序占用。后面的数字是本片空间的起始分配单元号和大小。而H代表的是空洞，即这是一片闲置空间。

在链表表示下，寻找一个给定大小的闲置空间意味着找到一个类型为H的链表项，其大小大于或等于给定的目标值。不过，扫描链表速度通常较慢。为提高查找闲置单元的速度，有人提出了将闲置空间和被占空间分开设置链表，这样就形成了两个链表的管理模式。

位图表示和链表表示各有优缺点：

如果程序数量很少，那么链表比较好，因为链表的表项数量少。
位图表示法的空间成本是固定的，它不依赖于内存中程序的数量。因此，从空间成本上分析，到底使用哪种表示法得看链表表示后的空间成本是大于位图表示还是小于位图表示而定。
从可靠性上看，位图表示法没有容错能力。如果一个分配单元为1，你并不能肯定它应该为1，还是因为错误变成1的。因为链表有被占空间和闲置空间的表项，可以相互验证，具有一定的容错能力。
从时间成本上，位图表示法在修改分配单元状态时，操作很简单，直接修改其位图值即可，而链表表示法则需要对前后空间进行检查以便做出相应的合并。

页式内存管理

交换的问题

空间浪费问题

随着程序在内存与磁盘间的交换，内存将变得越来越碎片化，即内存将被不同程序分割成尺寸大小无法使用的小片空间。

随着进程的进进出出，外部碎片将浪费大量的内存空间。我们可以采取一些措施来降低外部碎片的危害，例如，在寻找空间容纳新的进程时，可以按照某种算法，如最先适用（first fit）或者最佳适用（best fit）来进行。

但不管是最佳适用还是最先适用，这些算法都不能消除外部碎片。当然，如果实在不行，我们可以进行碎片整理，即通过移动进程在内存里面的位置将空闲空间连成一片。但是这种操作需要将进程导出到磁盘上，再重新加载，效率十分低下。在进行碎片整理的过程中，系统的响应延迟将显著增加。

程序受限问题

除了外部碎片外，交换的内存管理模式还存在几个重大问题：地址空间增长困难。这有两层意思：一是指空间增长效率低下；二是空间增长存在天花板限制。

由于磁盘操作耗时，这种交换出去，再找一片更大的空间来增长程序空间的做法效率非常低。
交换所能带来的空间增长有限。这个限制就是单一程序不能超过物理内存空间（减去操作系统所占部分），尽管多个程序的总空间可以超过物理内存空间。

解决之道

空间碎片化的根源是每个程序的大小不一样，这样在空间分配时不存在一致性。解决的办法自然是将空间按照某种规定的大小进行分配。只要将虚拟内存与物理内存都分成大小一样的部分，我们称为页，然后按页进行内存分配，就可以克服外部碎片的问题。

程序增长有限则是因为一个程序需要全部加载到内存才能运行。而解决的办法就是使一个程序无须全部加载就可以运行。用分页也可以解决这个问题：只将当前需要的页面放在内存里，其他暂时不用的页面放在磁盘上，这样一个程序同时占用内存和磁盘，其增长空间就大大增加了。而且，分页后，如果一个程序需要更多
的空间，给其分配一个新页即可（而无须像之前介绍的那样将程序倒出倒进，从而大大提高空间增长效率）。

因此，分页似乎就是我们解决交换缺陷的不二法门。

分页内存管理

分页系统的核心就是将虚拟内存空间和物理内存空间皆划分为大小相同的页面，如4KB、8KB或16KB等，并以页面作为内存空间的最小分配单位，一个程序的一个
页面可以存放在任意一个物理页面里。这样，由于物理空间是页面的整数倍，并且空间分配以页面为单位，将不会再产生外部碎片。同时，由于一个虚拟页面可以存放在任何一个物理页面里，空间增长也容易解决：只需要分配额外的虚拟页面，并找到一个闲置的物理页面存放即可。

在分页系统下，一个程序发出的虚拟地址由两部分组成：页面号和页内偏移值。

地址翻译

页面管理系统要能够将虚拟地址转换为物理地址。

因此，分页系统的核心是页面的翻译，即从虚拟页面到物理页面的映射。而这个翻译过程由内存管理单元（MMU）完成。MMU接收CPU发出的虚拟地址，将其翻译为物理地址后发送给内存。内存单元按照该物理地址进行相应访问后读出或写入相关数据。

内存管理单元对虚拟地址的翻译只是对页面号的翻译，即将虚拟页面号翻译成物理页面号。而对于偏移值，则不进行任何操作。这是因为虚拟页表和物理页表大小完全一样，虚拟页面里的偏移值和物理页面里的偏移值完全一样，因此无须翻译。

那么内存管理单元是通过什么手段完成这种翻译的呢？当然是查页表。对于每个程序，内存管理单元都为其保存一个页表，该页表中存放的是虚拟页面到物理页面的映射。每当为一个虚拟页面寻找到一个物理页面后，就在页表里面增加一个记录来保留该虚拟页面到物理页面的映射关系。随着虚拟页面进出物理内存，页表的内容页不断发生变化。

在程序发出一个虚拟地址给内存管理单元后，内存管理单元首先将地址里面页号部分的字位分离出来，然后判断该虚拟页面是否有效，是否存放在内存，是否受到保护。如果页面无效，即该虚拟页面不存在或没有在内存，也就是说该虚拟页面在物理内存里面没有对应。如果该页面受到保护，即对该页面的访问被禁止，则
产生一个系统中断来处理这些特殊情况。对于无效页面访问，需要终止发出该无效访问的进程。对于合法但不在物理内存中的页面，我们通过缺页中断将该虚拟页面放进物理内存。对于受保护的页面，同样终止该进程。

这里有一点要解释的就是非法虚拟页面。什么叫做虚拟页面非法呢？程序在加载前所使用的一切地址均是虚拟地址，即程序存在于虚拟空间。而虚拟空间的大小与系统的寻址长度有关。例如，32位寻址的系统虚拟地址空间为232-1，即一个程序最多可以有232-1条指令。但是一个程序可能没有这么多条指令。事实上，大部
分程序都不会占满整个虚拟空间。这样，就有一部分虚拟空间是空的，即程序没有使用的部分。这部分空间就是非法虚拟空间。如果一个程序访问了这片空间，即判定为非法，而无须再判断该虚拟页面是否在物理内存。

如果页面有效且在物理内存，又没有受保护，则使用该虚拟页面号作为索引，找到页表中对应该虚拟页面的记录，读取其对应的物理页面号。

那么内存管理单元是怎么知道一个页面是否有效，是否被保护，是否在物理内存呢？这个简单，将这些信息储存在页表里面即可。这样，页表不只是用来进行翻译，还用来进行页面的各种状态判断，因此，页表在分页系统里面的地位举足轻重。

页表

页表的根本功能是提供从虚拟页面到物理页面的映射。因此，页表的记录条数与虚拟页面数相同。

内存管理单元依赖页表来进行一切与页面有关的管理活动。这些活动包括判断某一页面号是否在内存里，页面是否受到保护，页面是否非法空间等。因此，页表除了提供虚拟页面到物理页面的映射外，还记录这些相关信息：

缓存禁止位用来指示该页面是否允许存放在缓存里。
访问位记录该页面是否被访问过（被读过或者被写过）。
修改位记录该页面自从加载到物理内存后是否被修改过。
保护标识位记录该页的受保护情况，如是否允许读、写、执行等。
在内存否则记录该虚拟页面是否已经在物理内存里。
物理页面号则是该虚拟页面对应的物理页面（如果该虚拟页面在物理内存的话）。

访问位和修改位是内存管理单元进行页面置换时依赖的信息。

当然，一个记录条通常还会有一个保留区（reserve area），设置保留区的目的是为以后有需要时增加信息用的。如果没有保留区，万一想对分页系统进行某种改善，而该种改善又需要在页表中记录额外的信息，则就没有办法实施了。除非重新设计页表记录内容。但这样一来成本就太高了。因此，设计任何数据结构时应该留有余地，这样才有改善的空间。

由于页表的特殊地位决定了它由硬件直接提供支持，即页表是一个硬件数据结构。

如果访问的页面不在内存，那么将产生缺页中断。缺页中断服务程序将负责在磁盘上找到需要的虚拟页面，并在物理内存里面寻找一个闲置的页面来存放该虚拟页面，然后更新页表。之后，对该虚拟页面的访问就可以正常进行了。

页面翻译过程

在该图中，CPU发出虚拟地址0010000000000100。由于页面大小为4KB，后面的12位为页内偏移值。前面的4位则为页面号。按此分解后，我们得出该地址在虚拟页面2，页内偏移值4的地址上。将这两部分地址分开，以2作为索引到找到页表的第2个记录，发现该记录所对应的页面在物理内存，其物理页面号是110，即6。这样，我们再将物理页面号与页内偏移值合并，获得物理地址为：110000000000100。

分页系统的优缺点

优点：

分页系统不会产生外部碎片，一个进程占用的内存空间可以不是连续的，并且一个进程的虚拟页面在不需要的时候可以放在磁盘上。这样，在分页系统下，进程空间的增长和虚拟内存的实现都解决了。
可以共享小的地址，即页面共享。我们只需要在对应给定页面的页表项里做一个相关的记录即可。

缺点：

页表很大，占用了大量的内存空间。那么有没有办法减少页表的尺寸呢？可以选择多级页表的方式。既然一个程序可以分解为一个个页面，并将部分页面存放在磁盘上而降低其内存占用空间，页表也可以采用同样的方式处理，即将页表分为一个个页面，不需要的页面也放在磁盘上。内存里只存放需要的页面。

多级页表

在多级页表结构下，页表根据存放的内容可分为：顶级页表、一级页表、二级页表、三级页表等。顶级页表里面存放的是一级页表的信息，一级页表里面存放的是二级页表的信息，以此类推，到最后一级页表存放的才是虚拟页面到物理页面的映射。一个程序在运行时其顶级页表常驻内存，而次级页表则按需要决定是否存放在物理内存。

多级页表为什么占用的内存空间少呢？因为大部分次级页表会放到磁盘上，而放在内存里面的页表较少。因此，内存占用少。

多级页表有什么缺点呢？它降低了系统的速度。因此每次内存访问都变成多次内存访问。对于二级页表，一次内存访问变成了三次内存访问。如果次级页表不在内存，还需要加上一次磁盘访问。这样，系统的速度将大为下降。对于级数更多的页表来说，内存访问速度额下降将更加明显。

反转页表

那有没有可能在不增加页表级数的情况下降低页表所占的空间呢？有，使用反转页表。正常的页表存放的是从虚拟页面到物理页面的映射；而反转页表存放的是物理页面到虚拟页面的映射。这样，由于物理内存比虚拟内存小很多，页表的尺寸将大为减少。

由于反转页表存放的是物理地址到虚拟地址的映射，而CPU发出的地址却是虚拟地址，这就造成页表查找困难。不过，这个问题可以通过散列来解决，即将虚拟页号散列到物理页号，然后以这个散列出来的物理页号作为索引在反转页表里面查找。但由于虚拟页面远多于物理页面的缘故，多个虚拟页号将很可能散列到同一个物理页号对应的记录里。这样，在散列后，仍然需要检查该虚拟页面是否在物理内存内，而这种检查需要进行多次内存访问。如果使用开放式散列，则散列表的尺寸将随着程序使用的虚拟页面数的增加而增加。

翻译速度

地址翻译因增加了内存访问次数而降低了系统效率。如果只使用单级页表，则每次内存访问变为两次内存访问，速度的下降还尚可以忍受。但如果使用多级页表或反转页表，则每次内存访问将变为多于两次的内存访问，这样效率的下降将非常明显。由于内存访问是每条指令都需要执行的操作，这样将造成整个系统效率的下降。那有没有什么办法改善翻译的速度呢？有。因为程序的运行呈现所谓的时空局域性，即在一段时间内，程序所要访问的地址空间有一定的空间局域性。如果一个页面被访问，则该页面的其他地址可能也将被随后访问。这样，我们可以将该页面的翻译结果存放在缓存里，而无须在访问该页面的每个地址时再翻译一次。这样就可以大大提高系统的执行效率。

这种存放翻译结果的缓存称为翻译快表（Translation Look-Aside Buffer, TLB）。TLB里面存放的是从虚拟页面到物理页面的映射，其记录的格式与内容和正常页表的记录格式与内容一样。这样，在进行地址翻译时，如果TLB里有该虚拟地址记录，即“命中”，就从TLB获得其对应的物理页面号，而无须经过多级页表或反转页表查找，从而大大提高翻译速度。如果TLB里面没有该虚拟页面号，即“未命中”，则需要按正常方式读取页表内容。

由于TLB里面不能按虚拟页面号进行索引，唯一的办法是一个记录一个记录地按顺序查找，以确认我们所需的虚拟页面是否在TLB里面。但这样的话，我们使用TLB的意义就不复存在了。因为搜索TLB所花费的时间可能已经远远超过查找多级页表所花的时间了。解决方案就是使用硬件。我们在TLB里面进行的比较不是一个个地顺序比较，而是同时比较，即将所有的TLB记录与目的虚拟地址同时比较，因此只需要一次查找就能确定一个虚拟页面号是否在TLB里。这种设计需要同时配备多套比较电路，比较电路的套数需与TLB的大小一样。这也就是为什么TLB非常昂贵。

当然，在TLB未命中的情况下，我们既可以将页表相应记录存入TLB，然后再由TLB来满足地址翻译需求（即重新启动指令），也可以直接由页表来满足翻译请求，同时将翻译结果存入TLB。这两种方式提供的抽象是不一样的。前者提供的抽象是所有翻译皆由TLB完成，而后者提供的抽象则是翻译过程既看到TLB，又看到正常页表。方式的差异将影响模块化的设计思路。

显然，采用多级页表的分页系统的效率将取决于TLB的命中率。如果命中率很高，则系统效率高；如果命中率低，则系统效率低。

缺页中断处理

在分页系统里，一个虚拟页面既有可能在物理内存，也有可能保存在磁盘上。如果CPU发出的虚拟地址对应的页面不在物理内存，就将产生一个缺页中断。而缺页中断服务程序负责将需要的虚拟页面找到并加载到内存。那么缺页中断程序是如何知道虚拟页面在磁盘的什么地方呢？它当然不知道。但它知道产生缺页中断进程所对应的源程序文件名和产生缺页中断的虚拟地址。这样，缺页中断服务程序首先根据虚拟地址计算出该地址在相应程序文件里面的位移量或偏移量（off-set），然后要求文件系统在这个偏移量的地方进行文件读操作。那么知道读多少内容吗？当然知道了，读一个页面的数据！而文件系统当然知道如何根据程序的文件名和偏移值来读取数据。

下面是缺页中断的处理步骤：

硬件陷入内核。
保护通用寄存器。
操作系统判断所需的虚拟页面号。
操作系统检查地址的合法性。
操作系统选择一个物理页面来存放将要调入的页面。
如果选择的物理页面包含有未写磁盘的内容，则首先进行写盘操作。
操作系统将新的虚拟页面调入内存。
更新页表。
发生缺页中断的程序进入就绪状态。
恢复寄存器。
程序继续。

锁住页面

如果发生缺页中断，就需要从磁盘上将需要的页面调入内存。如果内存没有多余的空间，就需要在现有的页面里选择一个页面进行替换。使用不同的更换算法，页面更换的顺序将各不相同。但不管使用何种算法，每个页面都存在被替换的可能。

这听上去像是一个很公平的事情。问题是有时我们需要把页面锁在内存，不想被交换出去。比如包含用于存放输入数据缓冲区的页面。如果这个页面被替换了，输入数据来的时候就没有地方写，将造成系统效率下降。此外，如果一个页面非常重要，我们知道它将被经常访问，也可以把它锁住，从而防止不必要的页面替换。

如何把页面锁在内存里呢？很简单，只需要对该页面做出特殊标记即可。即我们在页表的相应记录项里增加一项标志。如果该标志被设置，缺页中断服务程序在选择被替换的页面时将跳过该页面。

页面尺寸

分页系统的一个考虑因素就是页面应该设计为多大？如果太大，可能造成浪费。因为一个程序的最后一个页面很有可能是不满的。最好的情况是一个程序的大小正好是页面大小的整数倍；最坏的情况则是页面的整数倍多1条指令，多出来的这条指令就要占用一个页面，造成一个页面的绝大部分空间浪费。在平均情况下，最后一个页面有半个页面被浪费。这种浪费称为内部碎片，即一个进程内部的碎片空间。这样，页面越大，内部碎片就越大，浪费就越多。

例如，如果虚拟地址空间比较稀疏，大多数地址都是非法的。这样，用大页面造成的浪费将更为明显。当然，对一般的用户程序来讲，其地址空间一般是连贯的，不大可能出现断开的空间。而中间出现断开的程序，最典型的例子是编译器。编译器程序的虚拟地址空间里面有许多不连续的空间。如果被编译的程序尺寸小，则中间的很多空间都将是非法空间。如果页面尺寸很小，则浪费减少了，可以较好地容纳各种数据结构。但页表尺寸将增大，或者多级页表的层次增多。由此可见，页面大小并不能随意确定，必须考虑各种参数的折中。如何找到一个合适的尺寸呢？具体来说，就是要在页表大小和内部碎片之间进行平衡。

我们既不希望太大的内部碎片，又不想页表太大。那就先算一下因页表和内部碎片造成的系统消耗。假定p表示页面大小，e表示页表一个记录的大小，s表示程序的平均尺寸，则整个系统浪费的空间可由下面的表达式计算：(s·e/p+p/2)

其中(s·e/p)是一个程序页表所占的内存空间，而(p/2)则是一个程序平均浪费的页面空间（半个页面）。对上述表达式求极小值就可以得出页面尺寸p的最优大小为：(p=sqrt{2se})

可变页面尺寸

当然，如果需要，我们也可以使用可变尺寸的页面。例如，如果我们服务的环境既有许多很大的程序，也有许多很小的程序，则使用一种固定尺寸的页面不一定是最有效率的。这时，我们可以考虑使用可变尺寸，即不同的程序可以使用不同的页面大小，尽可能地降低系统的空间浪费。

但是可变页面页面策略的缺点也十分明显，首先是操作系统对内存的管理将更为复杂。其次，我们也很难正确地判断每个程序使用何种页面尺寸最为合适。最后，可变页面尺寸也不是一定就能消除内部碎片的。因此，可变页面尺寸策略听上去动听，实际上并不中用

内存抖动

在更换页面时，如果更换的页面是一个很快就会被再次访问的页面，则在此次缺页中断后很快又会发生新的缺页中断。在最坏情况下，每次新的访问都是对一个不在内存的页面进行访问，即每次内存访问都产生一次缺页中断，这样每次内存访问皆变成一次磁盘访问，而由于磁盘访问速度比内存可以慢一百万倍，因此整个系统的效率急剧下降。这种现象就称为内存抖动。

当然，我们可以通过仔细设计页面更换算法来降低内存抖动的概率，但却不能完全避免

发生内存抖动时，系统的效率将与停滞差不多，几乎看不到任何进展的迹象。如果页面不断地换出去调进来，CPU的资源将完全耗费在缺页中断上，无法进行任何有效工作。用户体验到的就是计算机停止了工作，而硬盘灯一直亮着。

那么我们有什么办法解决内存抖动呢？这要看是什么原因造成的抖动了。

如果是因为页面替换策略失误，当然可以修改替换算法来解决这个问题。
如果不是页面替换策略的问题，而是因为运行的程序太多，造成至少一个程序无法同时将所有频繁访问的页面调入内存，则需要降低多道编程的度数。通过减少同时运行的程序个数而使得每个程序都有足够的资源来运行而不产生抖动。这种降低多道编程度数的做法也称为负载平衡。
当然，有时候即使进行负载平衡也不一定能够消除内存抖动。例如，如果是一个进程的频繁访问页面就超过物理内存的页面数，即使降低多道编程度数，系统仍将抖动。这个时候解决的办法只有两个：一是终止该进程，永远不许其运行；二是增加物理内存的容量，就是开疆拓土。

比莱迪异常

增加物理页面数反而导致缺页次数增加的现象称为比莱迪异常（Beladys anomaly）。

这里需要注意的是，比莱迪异常并不能说明我们就不能给进程增加物理页面数，或者增加物理页面数就一定会导致缺页中断次数增加。事实上，比莱迪现象不是一种常见现象，而是一种异常现象。因此，只要需要，我们仍然给进程增加物理页面数，而且也期望着其缺页次数随着物理页面数的增加而降低。只不过是在我们这样做的时候要注意比莱迪异常。如果我们发现在增加物理页面数后程序的效率不升反降，则有可能发生了比莱迪异常。这个时候的应对策略是继续增加物理页面数，直到该现象消失为止。

当然，我们也可以改变页面替换算法来避免比莱迪异常。例如，改先进先出算法为LRU或工作集算法即可避免比莱迪异常。

页面更换算法

页面需要更换

分页系统克服了交换系统的各种缺点：外部碎片、难以增长、程序不能大于物理内存等。但是天下没有免费的午餐，虽然优点很多，但那也是需要付出代价的。这个代价就是页面的更换。在交换系统下，一个程序作为一个整体加载到内存。因此，在运行时，无须再从磁盘上加载任何东西。而在分页系统下，一个程序的所有页面并不一定都在内存中，因此，在执行的过程中就有可能发生页面不在内存的情况。

如果访问的页面不在内存中，则系统将产生缺页中断。缺页中断服务程序将负责把位于磁盘上的数据加载到物理内存来。如果物理内存还有空闲页面，那就直接使用空闲的页面。但如果物理内存已满，则需要挑选某个已经使用过的页面进行替换。那么挑选哪个页面合适呢？

页面更换的目标

显然，如果挑选的页面是之后很快又要被访问的页面，那么系统将很快再次产生缺页中断。因为磁盘访问速度远远慢于内存访问速度，缺页中断的代价是非常大的。因此，挑选哪个页面进行更换不是随随便便的事情，而是有要求的。

页面更换时挑选替换页面的目标是什么呢？当然是降低随后发生缺页中断的次数或者概率。因此，我们选择的页面应当是在随后相当长时间内不会被访问的页面。最好是再也不会被访问的页面。同时，如果可能，我们应该选择一个没有修改过的页面。这样，替换时就无须将被替换页面的内容写回磁盘，从而进一步加快缺页中断的响应速度。

随机更换算法

最简单的算法当然就是随机算法，或者说没有算法。在需要替换页面的时候，产生一个随机页面号，而替换与该页面号对应的物理页面。
显然，这种算法计算需替换页面号时速度很快。但是效果如何呢？事实上，这种算法的效果相当差。

先进先出算法

该算法的核心是更换最早进入内存的页面。FIFO的优点是简单且容易实现。但这个绝对的公平方式容易降低效率。

第二次机会算法

由于FIFO只考虑进入内存的时间，不关心一个页面被访问的频率，从而有可能造成替换掉一个被经常访问的页面而造成效率低下。那么我们对FIFO改进的方向就是考虑一个页面是否是经常被访问的因素。改进的手段就是在使用FIFO更换一个页面时，需要看一下该页面是否在最近被访问过。如果没有被访问过，则替换该页面。如果该页面在最近被访问过（通过检查其访问位的取值），则不替换该页面，而是将该页面挂到链表末端，并将该页面进入内存的时间设置为当前时间，并将其访问位清零。

时钟算法

第二次机会算法既简单、公平，又容易实现。只不过，每次给予一个页面第二次机会时，将其移到链表末端需要耗费时间。另外，页面的访问位只在页面替换进行扫描时才可能清零，所以其时间局域性体现得不好，访问位为1的页面可能是很久以前访问的，时间上的分辨粒度太粗，从而影响页面替换的效果。为了改善这些缺点，人们想出了时钟算法。

在时钟算法里，我们把页面排成一个时钟的形状。该时钟有一个针臂。每次需要更换页面时，我们从针臂所指的页面开始检查。如果当前页面的访问位为0，即从上次检查到这次，该页面没有被访问过，将该页面替换。如果当前页面被访问过，那就将其访问位清零，并顺时针移动指针到下一个页面。我们重复这些步骤直到找到一个访问位为0的页面。

时钟算法可以直接使用页表。使用页表的好处是无需额外的空间。更大的好处是页面的访问位会定期自动清零。这样将使得时钟算法的时间分辨粒度较第二次
机会算法高，从而取得更好的页面替换效果。

时钟算法的精髓就是第二次机会算法，只不过使用的是不同的数据结构，从而造成效率不同。既然时钟算法的精髓就是第二次机会算法，其缺点就和第二次机会算法一样：过于公平，没有考虑到不同页面调用频率的不同，有可能换出不应该或不能换出的页面，还有可能造成无限循环。

最优更换算法

最理想的页面替换算法是选择一个再也不会被访问的页面进行替换。如果不存在这样的页面，那至少选择一个在随后最长时间内不会被访问的页面进行替换。这样，我们就可以保证在随后发生缺页中断的次数最小或者概率最低，这种替换算法就是最优的替换算法。

那我们怎么知道一个页面随后多长时间不会被访问呢？当然不知道。既然如此，最优更换算法就是一种无法实际实现的算法。那么我们为什么要介绍最优算法呢？那是为了定义一个标杆，以此来评判其他算法的优劣。

NRU算法

改进的办法就是选择一个最近没有被访问的页面来替换，但在所有的最近没有使用的页面里，不是按照最先进入来划分，而是按照各个页面的修改位和访问位的组合来进行划分。这种算法称为最近未使用算法（Not Recently Used, NRU）。

顾名思义NRU就是选择一个在最近一段时间没有被访问过的页面进行替换，做出这种选择是基于程序访问的时空局域性。因为根据时空局域性原理，一个最近没有被访问的页面，在随后的时间里也不太可能被访问，而NRU的实现方式就是利用页面的访问和修改位。

我们知道每个页面都有一个访问位和一个修改位。凡是对页面进行读写操作时，访问位设置为1。当进程对页面进行写操作时，修改位设置为1。根据这两个位的状态来对页面进行分类的话，可以分成4种页面类型：

页面类型	访问位状态	修改位状态
1	没有被访问	没有被修改
2	没有被访问	修改过
3	被访问过	没有修改过
4	访问过	修改过

第2种状态是完全可能的。当然，修改需要访问。那什么情况下会出现页面没有被访问但是又被修改的状态呢？只有一种可能性，就是系统对访问位会定期清零，对修改位却不能清零。访问位定期清零是保证这个访问位不失去意义的手段。如果不定期清零，则一段时间后所有的页面都是被访问的。这样，这个访问位就没有任何意义了。与此同时，修改位却不能清零，因为操作系统在页面换出时要用它判断页面是否需要写回磁盘，清零后就会出错。这样，一个被访问和修改的页面在访问位定期清零后就会变成没有被访问但被修改的状态。

由此可以看出，我们在考虑一个页面的状态时有一个时间概念，即我们只考虑一段时间内的访问情况。因为所谓访问和未访问都需要局限在一段时间内讨论才有意义，如果考虑无限长的时间段，页面都是被访问状态。那我们就无法判断了。这个时候就得看谁是最近被访问的，以前很久被访问的就可以忽略了。这个可以通过定期清零访问位实现。

那么有了这个分类后，NRU算法就是按照这4类页面的顺序寻找可以替换的页面。如果所有页面皆被访问和修改过，那也只能从中替换掉一个页面。因此，NRU算法总是会终结。

当然，这种分类比较笼统，在同一类页面里，我们没有办法分辨出哪一类被访问时间更最近一些。即在某些情况下，我们替换的可能并不是最近没有使用的页面。换言之，在最差情况下，时间的分辨粒度粗到一个访问位清零的周期

LRU算法

LRU算法是最近使用最少算法（LeastRecently Used）。我们不仅考虑最近是否用过，还要考虑最近使用的频率。此处我们使用的哲学理念仍是拿过去的数据来预测将来：如果一个页面被访问的频率低，那么以后很可能也用不到。

由LRU算法的定义可以看出，LRU算法的实现必须以某种方式记录每个页面被访问的次数，而这是个相当大的工作量。最简单的办法就是在页表的记录项里增加一个计数域，一个页面被访问一次，这个计数器的值就增加1。这样，当需要更换页面时，只需找到计数域取值最小的页面替换即可，该页面即是最近最少使用的页面。

当然，这种实现存在很多疑问。首先，它不一定保证是最近最少使用的页面被选中。最少被使用可以肯定，但“最近”则不一定。因为计数器记录的时间段不一定是最近。这要看我们的最近定义的是多长时间。另外，由于物理计数域的长度总是有限的，值到最大后将发生溢出，而回到0。这样值最小的不一定是最少使用的，反而可能是最多使用的。

不过，我们何必一定要精确地实现LRU算法呢？研究计算机的人又不像研究数学的人那么精确，而且上述的实现还真是差不多。由于计数域长度有限，我们可以采取定期清零的操作来将时间段限制在我们所喜欢的“最近”。在这个人为确定的最近里面，计数器最小值的页面当然就是最近最少使用的页面了。事实证明，这种近似方法和真实最优情形很接近。

LRU算法的另一种简单实现方式是用一个链表将所有页面链接起来，最近被使用的页面在链表头，最近未被使用的放在链表尾。在每次页面访问时对这个链表进行更新，使其保持最近被使用的页面在链表头。

这两种简单的LRU算法实现方法都存在明显的缺点。每次内存访问都对链表进行更新效率十分低下，因为这种更新需要考虑不同页面之间的关系。使用计数器虽然在每次内存访问时只需修改一个页面的数据即可，但却需要使用的计数器个数与虚拟页面数一样多，空间成本巨大。另外，在遴选页面来替换时，需要比较所有页面的计数器的取值，时间成本也很大。

那么LRU算法实现还有没有比较现实的方式呢？

使用矩阵实现LRU算法

比起链表或页表来实现，使用矩阵实现LRU算法就要好不少。顾名思义，矩阵法，就是使用一个矩阵来记录页面的使用频率和时间。该矩阵为n×n维，n是相关程序当前驻内存的页面数。在一开始矩阵的初值为0。每次一个页面被访问时，例如第k个虚拟页面被访问时，我们进行如下操作：

将第k行的值全部设置为1。
将第k列的值全部设置为0。

在每次需要更换一个页面时，选择矩阵里对应行值最小的页面更换即可。此处的行值是指把该行所有的0和1连起来看做一个二进制数时的取值。

那么这种实现方式为什么正确呢？或者说这样做为什么能达到LRU算法的效果呢？我们来看，在一个页面被访问时，我们将该页面所对应的行设置为1，在第1步操作后，我们已经保证该页面对应的行值为最大之一。而第2个操作将该页面对应的列置为0，则保证了该页面对应的行值为唯一的最大。由于每个页面访问都会将某一列置为0，这样，越长时间没有被访问的页面，其对应的行元素里面被置为0的列个数就越多，即它对应的行值将越小。

使用矩阵法相对于链表法和页表法的优点是我们可以使用矩阵的许多理论来迅速判断哪个矩阵行值最小。而且，使用矩阵来实现LRU算法的成本比使用计数域要低，因为这个矩阵的行列数并不需要是虚拟页面数，而是在内存中的实际页面数，因此要小多了。

但该矩阵仍然太大，因为总的存储位是页面数的平方。矩阵法不能体现长时间访问次数的累积。

使用移位寄存器实现LRU算法

我们给每个存放在内存的页面配备一个移位寄存器。该寄存器用来记录该页面被访问频率和最近的属性。所有移位寄存器的初值皆为0。然后在每个规定长度的周期内，将移位寄存器的值往右移动一位，并将对应页面的访问位的值加到该移位寄存器的最左位。

这样，当需要寻找一个页面进行更换时，只需要找到对应移位寄存器值最小的页面即可。该页面即是最近最少使用的页面。

那么这个实现和矩阵法相比有什么优势？

首先，在硬件上节省了空间。因为移位寄存器个数虽然与内存页面数一样，但每个寄存器的长度却没有页面数多。矩阵法需要n×n维的空间，而这里是n×L维。这里的L是移位寄存器的长度。因此，只要移位寄存器的长度少于进程在内存的页面数，这种实现方式就有空间上的优势。而通常情况下，移位寄存器的长度确实远远少于内存里面的页面数。不难理解，移位寄存器的长度的意义就是决定“最近”这个时间段的长度。至于溢出的位，都属于超时的信息，不再纳入考虑。
其次，这种实现也节省时间。在矩阵法里，每次页面访问均需要更新矩阵，而移位寄存器法却不需要每次访问都进行更新。我们只在规定长度的时间内统计更新一次。因此更新的粒度（周期）是非常灵活的。而正因为这个灵活性，使得我们的时间成本大大降低。

当然，这种实现方法也有缺点。

更新周期灵活所付出的代价就是记录的精确性不如矩阵法。在某些特定情况下，这样选出的页面有可能不是最近最少使用的页面。
这是一个常见的“衰老算法”的思想，越是发生时间久远的事件，它对决策的影响越小。
大家知道，这个是用移位寄存器实现的，造价高。即使是单价降低了，成本仍然很大，因为需要的寄存器数量较大。

工作集算法

LRU算法虽然很好，但实现成本高，并且时间代价大。因此，一般的商用操作系统并没有采纳LRU页面更新算法。

那么LRU算法为什么会成本高呢？仔细分析可以发现，其成本之所以高，是因为我们想要分辨出不同页面中哪个页面是最近最少使用的。即需要对每个页面保持某种记录，并在每次页面访问发生时或者周期性地对这些记录进行更新，从而造成空间和时间成本居高不下。

工作集概念来源于程序访问的时空局域性。即在一段时间内，程序访问的页面将局限在一组页面集合上。例如，最近k次访问均发生在某m个页面上，那么m就是参数为k时的工作集。我们用w（k, t）来表示在时间t时k次访问所涉及的页面数量。

显然，随着k的增长，w（k, t）的值也随着增长；但在k增长到某个数值后，w（k, t）的值将增长极其缓慢甚至接近停滞，并维持一段时间的稳定。

由此可以看出，如果一个程序在内存里面的页面数与其工作集大小相等或超过工作集，则该程序可在一段时间内不会发生缺页中断。如果其在内存的页面数小于工作集，则发生缺页中断的频率将增加，甚至发生内存抖动。

因此，我们的目标就是维持当前的工作集的页面在物理内存里面。每次页面更换时，寻找一个不属于当前工作集的页面替换即可。而在这些不属于工作集的页面中间，无须顾虑哪个页面访问次数多或少，或者最后一次访问离当前时间谁近谁远，因为它们被替换出去都不会造成什么不良后果，从而大大降低页面替换算法的实现复杂性。这样，我们在寻找页面时只需将页面分离为两大类即可：当前工作集内页面和当前工作集外页面。这样，只要找到一个非当前工作集的页面，即可将其替换。

工作集算法的实现如下：

为页表的每个记录增加一项信息用来记录该页面最后一次被访问的时间。这个时间不必是真实时间，只要是按规律递增的一个虚拟时间即可。同时我们设置一个时间值T，如果一个页面的最后一次访问在当前时间减去T之前，则视为在工作集外，否则视为在工作集内。

这样，在每次需要替换页面时，扫描所有的页面记录，并进行如下操作：

如果一个页面的访问位是1，则将该页面的最后一次访问时间设为当前时间，并将访问位清零。
如果页面的访问位为0，则查看其访问时间是否在当前时间减去T之前。
- 如果在，则该页面将是被替换页面，算法结束。
- 如果不在，记录当前所有被扫描过页面的最后访问时间里面的最小值。

扫描下一个页面并重复1、2两个步骤。

如果在所有页面扫描后没有找到一个被替换的页面，则所有页面中最后一次访问时间最早的页面将被替换。这也是第b步记录当前最小值的原因。

该算法选择的是否是一个工作集外的页面呢？如果一个页面的访问位为0，表示自从上次扫描以来，该页面没有被访问过。如果该页面最后一次访问的时间在T时间以前，那么就说明该页面不在工作集内。这里需要注意的是，工作集既可以用访问次数表示，也可以用时间来表示，它们之间可以相互转换。因此，该算法选择的的确是一个工作集外的页面。当然，如果不存在一个最后一次访问时间在T之前的页面，则该算法选择的就有可能不是工作集外的页面，但选择的也是工作集里的最早页面。

这里需要注意的是，该算法只扫描页表一次。如果所有页面的访问位都为1的话，则表示分配给该程序的内存不够。最好的解决办法不是替换页面，而是给该程序增加一个物理页面。

那么该算法的T设置为多少呢？或者说我们怎么知道每个进程的工作集有多大呢？工作集有时空局域性，如果时刻都发生变化，那么就没有工作集了。所以它必须在某段时间是比较固定的。即随着访问次数的增多，访问的页面数也在增多，但是到了后面，你会发现，访问了100次的页面，你的页面始终集合在某个集合里。当然，如果你的程序是顺序的，也可能打破这个规则。但在正常情况下，你有50次访问，都是这10个页面，100次也是这10个页面。通过测试，我们可以求出这个临界的次数。在得到这个次数后，就可以将时间T算出来。只有算一下访问这么多次，需要多长时间即可。

工作集算法的优点是实现简单，只需在页表的每个记录增加一个虚拟时间域即可。因此，其空间成本不大。而且，这个时间域不是每次发生访问时都需要修改，而是在需要更换页面时，页面更换算法对其进行修改，因此其时间成本也不大。

工作集时钟算法

工作集算法的缺点就是每次扫描页面进行替换时，有可能需要扫描整个页表。而我们知道，并不是所有页面都在内存里，因此扫描过程中的一大部分时间将是无用功。另外，由于其数据结构是线性的，造成每次都按同样的顺序进行扫描，这样就对某些页面不太公平。

我们可不可以在保留其优点的同时对其进行改进呢？答案是肯定的。方法就是将工作集算法与时钟算法结合起来，设计出工作集时钟算法，即使用工作集算法的原理，但是将页面的扫描顺序按照时钟的形式组织起来。这样每次需要替换页面时，从指针指向的页面开始扫描，从而达到更加公平的状态。而且，按时钟组织的页面只是在内存里的页面，在内存外的页面不放在时钟圈里，从而提高实现效率。

鉴于其时间和空间上的优势，工作集时钟算法被大多数商业操作系统所采纳。

页面替换策略

在全局策略下，算法应用的对象是物理内存里面的所有页面，即我们是从所有的页里面按照选定的算法选出替换页面。这个被选出的页面既可以是当前发生缺页中断的进程的页面，也可以是另外一个进程的页面。这种策略可能影响其他进程的内存使用。

在局部策略下，算法应用的对象是当前进程的所有页面，即我们是从当前进程中物理页面按照我们选定的算法选出替换页面。这种策略不会影响其他进程的内存使用。

全局策略的优点是系统的总页面缺失率低，但程序运行不稳定。因为程序无法控制自己的缺页率。一个进程在内存中的页面使用不仅取决于该进程的页面走向，也取决于其他进程的页面走向。因此，相同程序由于外界环境不同会造成执行上的很大差别。

局部替换策略的优点是更加公平，程序运行更加稳定。因为一个进程的内存使用情况不会干扰其他进程的内存使用，但缺点是不能充分利用系统的整体资源，可能造成不同进程之间在页面使用上的不平衡：即有的进程有页面富余，而有的进程却频繁缺页。

固定与可变驻留集

使用何种页面替换策略决定了一个进程在内存所占页面的数量是否固定。局部策略由于只选择本进程的页面进行替换，所以一个进程所占的物理页面数将保持不变，即进程驻留内存的页面数是固定的。全局页面替换策略由于动态地改变一个进程所占物理页面数，进程驻留内存的页面数是可变的。从另一方面说，凡是支持
固定驻留集的页面替换算法只能使用局部替换策略，凡是支持可变驻留集的页面替换算法只能使用全局页面替换策略。

初始页面数确定

为每个进程分配内存块的算法主要有3种：均分法、比例法、优先权法。

均分法将内存空间在多个进程间平均分配。若有m块内存页面和n个进程，则每个进程分m/n块。每次增加一个进程，就需要重新分配一次。
比例法则根据程序大小按比例给每个程序分配内存空间。例如，分给进程的页面数=（进程地址空间大小/全部进程的总地址空间）×可用页面总数
这种分配方法考虑了程序的个体特性，比均分法更恰当。但同样，每次增加一个进程时需要重新计算和分配内存页面。
优先权法则将一个进程的优先级考虑进来，从而加速高优先级进程的执行。例如，在使用比例分配法时，分给进程的页面数不仅取决于程序的相对大小，而且取决于该程序优先级的高低。在请求分页的策略下，一个进程在初始化时不分配任何页面，而是在需要使用页面的时候一个页面一个页面地增加。当进程的缺页频率降低到一定程度后，页面数将不再增加。

段式内存管理

分页系统的缺点

分页系统还有其他缺陷吗？有。其中的一个是共享困难。虽然在理论上可以按页进行共享，似乎粒度很细，但实际上这根本就是不现实的。原因是一个页面的内容很可能既包括代码又包括数据，即很难使一个页面只包含需要共享的内容或不需要共享的内容。只要一个页面里面有一行地址是不能共享的，这个页面就不能共享。而一个页面里面存在至少一行不能共享的地址是完全可能的。这样，想自由地共享任何内容几乎就变得不可能了。

如果说上述缺点尚可以容忍，但有一个缺点却是无法容忍的，同时也是分页系统无法解决的。这个缺点就是一个进程只能占有一个虚拟地址空间。在此种限制下，一个程序的大小至多只能和虚拟空间一样大，其所有内容都必须从这个共同的虚拟空间内分配。

我们知道编译器在工作时需要保持多个数据结构：词法分析树、常数表、代码段、符合表、调用栈。保持多个数据结构本身并无任何问题。问题出在这些数据结构可以独立增长和收缩。即在编译器扫描过程中，这些数据结构里面数据可以增多或减少，从而造成该数据结构所需内存空间的变化。

如果编译器只在一个虚拟空间活动，则所有的数据结构或表格均在一个虚拟空间分配，这样就必然发生不同的数据结构占据虚拟空间的不同部分的情况。这样，当一个数据结构空间需要增长时，就会碰到处于其上的其他数据结构而造成无法增长。那么如果某个数据结构无法增长，例如词法树所占空间无法增长，则编译过程将失败。

那么怎么解决这个问题呢？记住，这里的碰撞可是在虚拟空间中的碰撞，而不是物理空间的碰撞。解决的办法自然是增加虚拟空间的容量。但是虚拟空间的大小受寻址宽度的限制而无法增长。剩下的办法就只能让一个程序使用多个虚拟空间！

分段管理系统

分段管理就是将一个程序按照逻辑单元分成多个程序段，每一个段使用自己单独的虚地址空间。

这样，一个段占用一个虚地址空间，就不会再发生空间增长时碰撞到另一个段的问题。从而避免因空间不够而造成编译失败的情况。

一个程序占据多个虚拟地址空间，那么不同的段有可能有同样的虚拟地址空间。如果要区分一个虚拟地址所在的段，我们必须在虚拟地址前面冠以一个前缀，即该地址所在的段号。也就是说，在分段情况下，一个虚拟地址将由段号和段内偏差两个部分构成。

在逻辑分段下，每一个虚拟地址段可以加载到物理内存的任何空间。我们只需要在加载后将对应的基址寄存器与极限寄存器的值进行相应调整即可。

分段管理的一个重要数据结构就是段表。和页表类似，该表存放的是虚拟段号到该段所在内存基址的映射。如果一个段不在内存中，则该段号对应的基址将不存在。这里需要注意的是，由于段的数量很少，通常为3～5段，段表的尺寸非常小。

这里我们要问的一个问题是，段号是否占用寻址位数。如果是，则每个逻辑段实际上不能占用一个完整的虚拟地址空间。但由于段数很小，通常为3～5段，段号所占的位数不会超过3位，因此，每一个逻辑段可以使用的虚地址空间仍然非常大。

如果我们想分配给逻辑段完整的虚地址空间，则可以将虚拟段号存放到一个特殊的寄存器里，即不占用寻址字位。或者将其隐含在指令的操作码里面。这样只要看到操作码，我们就知道其所属段号。

分段的优缺点

逻辑分段的优点十分明显。

首先，每个逻辑单元可单独占一个虚拟地址空间，这样使得编写程序的空间大为增长，几乎可以编写出没有尺寸限制的程序来。
其次，由于段是按逻辑关系而分，共享起来就非常方便。不会出现分页系统下一个页面里面可能同时包含数据和代码而造成共享不便的问题。由于不同的逻辑段使用不同的基址与极限对，我们可以对不同的段采用不同的保护措施。
最后，对于空间稀疏的程序来说，分段管理将节省大量的空间。因为空余的部分不用分配任何虚拟空间；而在分页下，空余的空间仍然需要分配虚拟页面，只不过该页面非法而已。而在上下文切换时要更换的内容很简单：段表。因为段表很小，这种切换非常容易。

分段管理的缺点也十分明显。既然是分段，就存在前面基本内存管理时介绍过的缺点：外部碎片和一个段必须全部加载到内存。

一般来说，一个程序的所有逻辑段是同时需要的。如果实行分段管理，则由于每个段必须全部加载到内存，这就造成了我们在基本内存管理时已经遇到过的一个问题：一个程序必须同时全部加载到内存才能执行。当然，解决这个问题可以使用重叠（overlay）。但我们已经尝过分页系统好处后再使用overlay显然有“优汰劣
胜”的味道。

那么我们的解决办法是什么呢？分页。但这次的分页不是前面的直接对程序进程分页，而是对程序里面的段进行分页。这就形成了所谓的段页式内存管理模式。这种段内分页是前面讲过的页式内存管理的否定之否定。

段页式内存管理

段页式管理就是将程序分为多个逻辑段，在每个段里面又进行分页，即将分段和分页组合起来使用。这样做的目的就是想同时获得分段和分页的好处，但又避免了单独分段或单独分页的缺陷。如果我们将每个段看做一个单独的程序，则逻辑分段就相当于同时加载多个程序。

那么段页式内存管理是如何实现的呢？

由于段页式管理模式是在段里面分页，而每个段占据一个虚地址空间，这就意味着一个程序将对应多个页表。那么一个程序如何管理多个页表呢？简单！在分页系统里已经介绍过多级页表。在这里我们只需要将这些页表作为次级页表，而在次级页表上面增加一层段表（相当于多级页表里面的顶级页表）。由段号在段表里面获得所应该使用的页表，然后在该页表里面查找物理页面号。

如果需要，次级页表又可以再分为两个或多个层次，形成层次更为丰富的段页式层次结构。当然，随后层次的增加，内存访问的效率将下降。但我们前面已经讨论过了，可以使用快表TLB来绕过段表和页表的查找，从而加快速度。不过，这里的快表必须将段号也包括进来。

那么段表里面的每个记录包含哪些内容呢？这个答案显然随着系统的不同而不同。不过，一般来说，包括的内容至少有段长、对应页表在内存的地址、页面大小、保护标志等。

段号是否占用寻址字位

本章前面介绍过，分段管理就是将一个程序分为多个逻辑上有一定独立性的段，每个段占一个完整的虚拟地址空间。这样的话，每个段里面的指令所使用的虚地址将与寻址位数相等，即段内偏差与寻址位数一样。但是我们又知道，在分段模式下，一条指令的虚地址包括段号和段内偏差。那么段号将不占用虚地址空间的字位。

那么段号不占虚地址空间位数是如何实现的呢？这个简单：使用单独的寄存器来存放段号，或者将段号隐含在指令操作码里，即每条指令都隐含了自己到底属于哪一个逻辑段。

分段管理时每个段的虚地址空间是独立的，它们之间没有任何距离上的关系。如果将段号放在虚地址空间内，则每个段之间将存在距离上的关系，即某个段在另一个段前面或者后面。这样段之间的关系就有了限制，且每个段的大小就会比虚地址空间小。

有一个段表，而每个段有个页表。我们从段号里面找到应该使用哪个页表，然后从页表里面找到逻辑页面对应的物理页面。再将物理页面号和页内偏差合并形成物理地址。所有段页式的系统使用的都是这种方式。

如果我们的地址完全是以页号和页内偏差构成的，那么我们的段就可以放在任何地方。从这一点说，段的唯一目的就是区分不同的页表。