存储器管理
首先得声明，在引入虚拟存储器之前，存储器通常是将整个进程所有资源引入内存的。
存储器的层次结构
程序的装入和链接
装入
绝对装入方式
编译程序将产生绝对地址的目标代码根据地址将程序和数据存入内存。
- 编程人员要熟悉内存。
- 程序在内存中不能移动。
- 不适用于多道程序设计环境。
可重定位装入方式（静态）
编译程序将产生相对地址的目标代码，装入时需要地址映射，地址变换只在装入时一次性完成，以后不再改变。
- 适用于多道程序环境。
- 程序在内存中不能移动。
动态运行时装入方式
编译程序将产生相对地址的目标代码，装入时并不立即把相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时才运行。
- 程序装入内存后可移动。
链接
静态链接方式
程序运行前将各目标模块及所需库装配成一个完整模块且不再分开。
装入时动态链接
边装入边链接。（假如没有用到某一模块，也会装入内存，所有才有了方法3）
运行时动态链接
将链接推迟到程序运行时，如果链接到哪一模块，则再将该模块装入内存。（加快装入过程，节省空间）
连续分配存储管理方式
方式
- 单一连续分配
- 固定分区分配
- 动态分区分配
基于顺序搜索的动态分区分配算法
首次适应算法(First Fit):
从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
特点
该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。
缺点
低址部分不断被划分，会留下许多难以利用的，很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销
下次适应（next fit）算法
也称“临近适应”算法，其工作方式和最先适应算法相同（最先适应也称首次适应算法。它总是最先找到的、满足存储要求的那个空闲分区作为分配对象。），不同的是每次找到合适的空闲的分区时就记住它的位置，以便下次就从该位置开始往下查找，而不是每次都像最先适应算法那样从头开始查找。这种算法的总体结果通常要比最先适应算法差。由于它经常会在内存的末尾分配存储分区，使位于存储空间末尾的最大分区被撕裂称小的外部碎片，因此必须经常不断地进行存储紧凑。在该算法中应采取循环查找方式，即最后上个空闲区的大小仍不能满足要求时，应再从第一个空闲区开始查找，故又称为循环造就算法。
最佳适应算法（Best Fit）：
它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。
Best fit算法等价于装箱问题，举例如下：
装箱问题：有体积为V的箱子N个，体积为Vi的物品M个，求使得物品全部能够装入箱子，箱子数量的最小值。
假设 V=6 N=10，V1，V2，…,V10分别为：3 4 4 3 5 1 2 5 3 1。计算过程如下：
第一步按物品体积降序排序：5 5 4 4 3 3 3 2 1 1
第二步：取未装箱的最大值5装入第一个箱子。
第三步：判断第一个箱子是否已满，不满且剩余空间为1，搜寻剩下体积小于等于1的物品填入箱子1，箱子1填满。
第四步：重复第二，第三步，直到所有物品装入箱子为止，得到箱子数量为6.
6即时本例N的最小值。
最坏适应算法（worst fit）
最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。
优点：可使剩下的空闲分区不至于太小，产生碎片的几率最小，对中、小作业有利，同时该算法查找效率很高。
缺点：会使存储器中缺乏大的空闲分区。
最坏适应算法与首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。
基于索引搜索的动态分区分配算法
快速适应算法（分类搜索法）
该算法就是将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样的系统中存在多个空闲分区链表。同时，在内存总设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分的。
该算法在搜索可分配的空闲分区时分为两步：第一步是根据进程的长度，从索引表中寻找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配即可。另外，该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。优点是查找效率高。缺点是在分区归还时的算法复杂，系统开销大。此外，该算法在分配空闲分区时，是以进程为单位的，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少的存在一定的浪费。这是典型的以空间换时间的做法。
伙伴系统
该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂，通常2的m次方是整个可分配内存的大小。假设系统的的可利用空间容量为2的m次方，则当系统开始运行时，整个内存区是一个大小为2的m次方的空闲分区。在系统运行过程中，由于不断地划分，将会形成若个个不连续的空闲分区，将这些分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了k个空闲分区链表。
当需要为进程分配一个长度大小为n的存储空间时，首先计算一个i值，使2的i-1次方小于n小于等于2的i次方，然后再空闲分区大小为2的i次方的空闲分区链表中查找。
在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差，但由于它采用了索引搜索算法，比顺序搜索算法号。而其空间性能，由于对空闲分区进行合并，减少了空闲分区，提高了空间分区的可使用率，故由于快速适应算法，比顺序搜索法略差。
总结：虽然在当前的操作系统中，主要还是采用离散分配方式的分页和分段机制的虚拟内存机制，因为该机制较伙伴算法更为合理和高效，但在多处理机系统中，伙伴系统仍不失为一种有效的内存分配和释放的方法，目前仍然被广泛使用。
哈希算法
由于分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在每一张管理索引表中查找到所需要的空间大小所对应的表项，从中得到对应的空间内分区链表表头指针，从而通过查找一个空闲分区。如果对空闲分区分类比较细，则相应索引表的表项也就较多，因此会显著的增加搜索索引表的表项的时间开销。
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲分区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需要的空闲 分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
动态可重定位分区分配
- 紧凑
- 动态重定位
- 动态重定位分区分配算法
离散式存储管理方式
分页存储管理方式
连续分配存储管理方式产生的问题
在分区存储管理中，要求把进程放在一个连续的存储区中，因而会产生许多碎片。
碎片问题的解决方法
（1）拼接/紧凑技术—-代价较高。
（2）离散分配方式—允许将作业/进程离散放到多个不相邻接的分区中，就可以避免拼接。
离散分配方式
分页式存储管理：离散分配的基本单位是页
分段式存储管理：离散分配的基本单位是段
段页式存储管理：离散分配的基本单位是段、页
什么是页
将一个用户进程的地址空间（逻辑）划分成若干个大小相等的区域，称为页或页面,页面大小由地址结构（逻辑）决定 ，并为各页从0开始编号。
什么是块
内存空间也分成若干个与页大小相等的区域，称为（存储、物理）块或页框（frame），同样从0开始编号。
内存分配
在为进程分配内存时,以块为单位,将进程中若干页装入到多个不相邻的块中,最后一页常装不满一块而出现页内碎片。
页表的出现
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。一个页表中包含若干个表目，1.表目的自然序号对应于用户程序中的页号。2.表目中的块号是该页对应的物理块号。
内存地址的获取
以页号查页表，得到对应页装入内存的块号。即可求出：内存地址＝物理块号×页大小＋页内地址。
例:在采用页式存储管理的系统中,某作业J的逻辑地址空间为4页(每页2048字节),且已知该作业的页面映像表如下:
| 页号 | 块号 |
|---|---|
| 0 | 2 |
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
试借助地址变换图求出有效逻辑地址4865所对应的物理地址.
解:页号 4865/2048=2 页内位移 4865%2048=769，过程如下：
从上面我们可以看出：CPU要想获取一个数据时，必须两次访问内存：
1、从内存中的页表中，寻找对应的物理块号，将物理块号与页内地址组合成物理地址。
2、根据组合成的物理地址，来获取数据。
为了提高效率呢，就引进了块表，什么是快表呢？
在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想存储器”或“快表”。
在引入快表的分页存储管理方式中，通过快表查询，可以直接得到逻辑页所对应的物理块号，由此拼接形成实际物理地址，减少了一次内存访问，缩短了进程访问内存的有效时间。但是，由于快表的容量限制，不可能将一个进程的整个页表全部装入快表，所以在快表中查找到所需表项存在着命中率的问题，。总体上来说，还是减少了访问内存的时间。
分段存储管理方式
分段存储管理方式的引入
引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：
1）方便编程
通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并有自己的名字和长度。
因此，希望要访问的逻辑地址是由段名（段号）和段内偏移量（段内地址）决定的。
2）信息共享
在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。比如共享某个例程和函数，分页系统中的“页”只是存放信息的物理单位（块），
并无完整的意义，不便于实现共享，然而段却是信息的逻辑单位。
3）信息保护
信息保护同样是对信息的逻辑单位进行保护，因此，分段管理方式能更有效和方便的实现信息保护功能。
4）动态增长
在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切地知道数据段会增长到多大。前面的几种存储
管理方式都难以应付这种动态增长的情况，分段存储管理方式能较好的解决这一问题。
5）动态链接
动态链接是指在作业运行之前，并不把几个目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程
中又需要调用某段时，才将该段（目标程序）调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。
分段和段表
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段 定义了一组逻辑信息。每个段都有自己的名字，通常可用一个段号来
代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的
地址空间分成多个段，是二维的。
在动态分区（可变分区）分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个
连续的分区，而进程中的各个段可以离散地装入内存中不同的分区中。为使程序能正常运行，即能从物理内存中找出每个逻辑段所对应的位置，
应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。
每个段在表中占有一个表项，其中记录了该段在内存中的起始地址（“基址”）和段长（字节）。段表一般放在内存中。在配置了段表后，
执行中的进程可通过查找段表找到每个段所对应的内存区。可见，段表是用于实现从逻辑段到物理内存区的映射。
地址变换机构
为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址 和段表长度TL。在进行地址变换时，
系统将逻辑地址中的段号S（0～TL-1）与段表长度TL进行比较。– 若S>=TL，表示段号太大，是访问越界，于是产生越界中断信号；
若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置（段表的始址+段号x段表项的长度），从中读出该段在内存的
起始地址，然后再检查段内地址d是否超过该段的段长SL。若超过，即d>SL,同样发出越界中断信号；若未越界，则将该段的基址与段内地址d
相加，即可得到要访问的内存物理地址。
像分页系统一样，当段表放在内存中时，每当要访问一个数据，都需访问两次内存（第一次是得到物理地址，第二次是从地址中取数据），
从而极大地降低了计算机的速率。解决方法是再增设一个联想存储器（TLB），用于保存最近常用的段表项。一般情况下是段比页大，因而
段表项的数目比页表项的数目少，需要的TLB也相对较小，可以显著的减少存取数据的时间。
分页和分段的主要区别
分页和分段系统都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，主要表现在3个方面：
– 1）页是信息的物理**单位，分页是为实现离散分配方式，消减外部碎片，提高内存的利用率。分页仅仅是由于系统管理的需要而不是用户的需要。**
段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好的满足用户的需要。
– 2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；
而段的长度不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
– 3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间是二维的，
程序员在标识一个地址时，既需给出段名，又需给出段内地址。
信息共享
段的共享：即允许若干个进程共享一个或多个分段。
可重入代码（Reentrant Code）又称为“纯代码”（Pure Code），是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，
绝对不允许可重入代码在执行中有任何改变。因此，可重入代码是一种不允许任何进程对它进行修改的代码。
—- 但事实上，大多数代码在执行时都可能有些改变，例如，用于控制程序执行次数的变量以及指针、信号量及数组等。为此，在每个进程中，都必
须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区，这样，程序在执行时，只需对该数据区（属于该进程私有）中的内容进行修改，并
不去改变共享的代码，这时的可共享代码即成为可重入码。
段页式存储管理方式
用户程序先分段，每个段内部再分页（内部原理同基本的分页、分段相同）
地址结构
分三部分：段号、段内页号、页内地址
地址映射（逻辑地址—>物理地址）
³ 逻辑地址—– >段号、段内页号、业内地址
³ 段表寄存器— >段表始址
³ 段号+段表始址—- >页表始址
³ 页表始址+段内页号—–>存储块号
³ 块号+页内地址——>物理地址
地址变换原理及步骤
请看上图，给出逻辑地址的段号、页号、页内地址，开始进行地址变换：
1) 在被调进程的PCB中取出段表始址和段表长度，装入段表寄存器
2) 段号与控制寄存器的页表长度比较，若页号大于等于段表长度，发生地址越界中断，停止调用，否则继续
3) 由段号结合段表始址求出页表始址和页表大小
4) 页号与段表的页表大小比较，若页号大于等于页表大小，发生地址越界中断，停止调用，否则继续
5) 由页表始址结合段内页号求出存储块号
6) 存储块号&页内地址，即得物理地址
总结
在页式、段式存储管理中，为获得一条指令或数据，须两次访问内存；而段页式则须三次访问内存。
虚拟存储器
常规存储器要求将一个作业全部装入内存方能执行。而虚拟存储器允许将一个作业分多次调入内存。如果采用连续分配方式，则需将作业装入一个连续的内存区域中。所以，虚拟存储器抖毫无例外建立在离散分配管理方式之上。
- 请求分页存储管理方式。
- 请求分段存储管理方式。
请求分页存储管理方式
定义：
请求分页系统是建立在基本分页系统的基础上，为了能支持虚拟存储器功能而
添加了请求调页功能和页面置换功能。
页表机制
在请求分页系统中所须要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。因为仅仅将应用程序的一部分调入内存，另一部分仍在盘上，故须在页表中再添加若干项，供程序(数据)在换进、换出时參考。在请求分页系统中的每个页表项例如以下所看到的：
状态位 P：指示该页是否已调入内存。 供程序访问时参考
访问字段 A：记录本页在一段时间内被访问的次数或最近未被访问的时间。 供选择页面换出时参考
修改位 M：表示该页在调入内存后是否被修改过。若修改过，则置换该页时需重写该页至外存。 供置换页面时参考
外存地址：指出该页在外存上的地址。供调入该页时参考
缺页中断机构
在请求分页系统中，每当所要訪问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，它们相同须要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的差别，主要表如今以下两个方面：
(1) 在指令运行期间产生和处理中断信号。通常，CPU都是在一条指令运行完后，才检查是否有中断请求到达。若有，便去响应，否则，继续运行下一条指令。然而，缺页中断是在指令运行期间，发现所要訪问的指令或数据不在内存时所产生和处理的。
(2) 一条指令在运行期间，可能产生多次缺页中断。在下图中示出了一个样例。如在运行一条指令COPY A TO B时，可能要产生6次缺页中断，当中指令本身跨了两个页面，A和B又分别各是一个数据块，也都跨了两个页面。基于这些特征，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续运行。
地址变换机构
请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，再为实现虚拟存储器而添加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。下图表示出了请求分页系统中的地址变换过程。在进行地址变换时，首先去检索快表，试图从中找出所要訪问的页。若找到，便改动页表项中的訪问位。对于写指令，还须将改动位置成“1”，然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
请求分页存储管理
例：一个采用请求分页存储管理的计算机系统，其内存（实存）容量为 256M 字节，虚拟内存容量（给用户的最大地址空间）为 4G 字节，页面大小为 4K 字节，试问：
实存物理地址应设为多少位？
256M = 2^28，所以为28位
实存中有多少物理块？
256M/4K = 64K
实存中最大块号是多少？
64K-1
虚存地址应设多少位？
4G = 2^32，所以为32位
虚拟地址空间最多可以有多少页？
4G/4K = 1M
页内最大偏移量是多少？
4k-1 = 4*1024-1 = 4095
请求分页中的内存分配
最小物理块数的确定
最小物理块数指能保证进程正常运行所需的最小的物理块数，最小物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
采用直接寻址方式，所需的最少物理块数为 2。一块是用于存放指令，另一块用于存放数据。
间接寻址时，至少要求有三个物理块。 （间接寻址中一些物理块放的是其它物理块的块号）
物理块的分配策略
固定分配局部置换
为每个进程分配固定数目 n 的物理块，在整个运行中都不改变。如出现缺页则从该进程的页面中置换一页。
每个进程分配多少个物理块难以确定.
若太少，会频繁地出现缺页中断，降低了系统的吞吐量。
若太多，内存中驻留的进程数目减少，可能造成 CPU空闲或其它资源空闲的情况。
可变分配全局置换
为每个进程分配一定数目的物理块，但 OS 自留一空闲块队列，若发现缺页，则从空闲块队列中分配一空闲块与该进程，并调入缺页于其中。当空闲块队列用完时，OS 才从内存中任选择一页置换。
可变分配局部置换
为每个进程分配一定数目的物理块，若发现缺页，则从该进程的页面中置换一页，不会影响其它进程的运行。根据进程缺页率高低，则可增加或减少分配给该进程的物理块。
页面调入策略
何时调入页面
预调页策略
预调页：将预计在不久之后便会被访问的页面预先调入内存。
进程的页一般存放在外存的一个连续区域中。一次调入若干个相邻的页会比一次调入一页更高效。
但如果调入的一批页面中的大多数都未被访问，则浪费了内存。
请求调页策略
当进程在运行中发生缺页时，就立即提出请求，由系统将缺页调入内存。但这种策略每次仅调入一页，须花费较大的系统开销，增加了启动磁盘 I/O 的频率。
从何处调入页面
在请求分页系统中，外存分成了按离散分配方式存放文件的文件区和按连续分配方式存放对换页的对换区。进程发出缺页请求时，从何处将缺页调入内存呢？
对换区：如果系统有足够的对换区空间，运行前可将与进程相关的文件从文件区复制至对换区，以后缺页时全部从对换区调页。
文件区：如果系统没有足够的对换区空间，凡是不会被修改的文件，直接从文件区调页，不必回写（换出） 。对可能会修改的文件第一次直接从文件区调页，换出时换至对换区，以后从对换区调页。
UNIX 方式：凡未运行过的页面均从文件区调页，运行过的页面和换出的页面均从对换区调页。
页面置换算法
最佳置换算法（OPT）（理想置换算法）
从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
进程运行时，先将7, 0, 1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推，如图3-26所示。从图中可以看出釆用最佳置换算法时的情况。
可以看到，发生缺页中断的次数为9，页面置换的次数为6。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | |||||||||||
| 物理块2 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | ||||||||||||
| 物理块3 | 1 | 1 | 3 | 3 | 3 | 1 | 1 | |||||||||||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ |
先进先出置换算法（FIFO）
是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||
| 物理块2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||
| 物理块3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
这里仍用上面的实例，釆用FIFO算法进行页面置换。进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由图 3-27可以看出，利用FIFO算法时进行了 12次页面置换，比最佳置换算法正好多一倍。
FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常，如图3-28所示。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。
| 访问页面 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | ,5’ | 5 | |||
| 物理块2 | 2 | 2 | 2 | 1 | 1 | 1 | 3 | 3 | ||||
| 物理块3 | 3 | 3 | 3 | 2 | 2 | 2 | 4 | |||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | |||
| 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 | ||||
| 物理块2* | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |||
| 物理块3* | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||||
| 物理块4* | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ |
注意：内存的页面中“最老“的页面，会被新的网页直接覆盖，而不是“最老“的页面先出队，然后新的网页从队尾入队。
最近最久未使用（LRU）算法
这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。
再对上面的实例釆用LRU算法进行页面置换，如图3-29所示。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||
| 物理块2 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||
| 物理块3 | 1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。
***LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。
时钟(CLOCK)置换算法
LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。
简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。
CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：
- 最近未被访问，也未被修改(u=0, m=0)。
- 最近被访问，但未被修改(u=1, m=0)。
- 最近未被访问，但被修改(u=0, m=1)。
- 最近被访问，被修改(u=1, m=1)。
算法执行如下操作步骤：
- 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。
- 如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。
- 如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。
改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。
例题：
在5个页框上使用LRU页面替换算法，当页框初始为空时，引用序列为0、1、7、8、6、2、3、7、2、9、8、1、0、2，系统将发生（C）次缺页
A、13 B、12 C、11 D、8
解析：内存中驻留5个页框：
| 访问页面 | 0 | 1 | 7 | 8 | 6 | 2 | 3 | 7 | 2 | 9 | 8 | 1 | 0 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 页框1 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 页框2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | |
| 页框3 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 0 | 0 | ||
| 页框4 | 8 | 8 | 8 | 8 | 8 | 8 | 9 | 9 | 9 | 9 | 9 | |||
| 页框5 | 6 | 6 | 6 | 6 | 6 | 6 | 8 | 8 | 8 | 8 | ||||
| 是否缺页 | Y | Y | Y | Y | Y | Y(换页) | Y(换页) | N | N | Y(换页) | Y(换页) | Y(换页) | Y(换页) | N |
LRU是堆栈类的算法，最后访问的页面放在栈顶，可以得到答案为C。
编程思路：
1,用结构体成员记录访问的顺序，换页时选取times最大的那个替换掉。
struct LRU { int data;
int times;};记录访问次序
struct queue{ LRU *p; int front; int rear
}Qe;
(1)队列未满时，依次添加新访问的页面，并Qe.p[i++].times++
(2)队列满了 a, 新访问的页面在队列中，times设为0，之前在它前面的LRU.times++
b, 新访问的页面不在队列中，需替换掉times最大的页面，并设新页面times=0，对列中其它页面times++
2,用队列中存放的位置表示最后访问时间（用线性表涉及大量元素移动，用链表好些）
队列未满时，依次压入；队列满，则查看对列中是否存在，若存在，将其移动到队尾，若不存在，删除队首页面，并在队尾加入新页面。
抖动与工作集
页面抖动（颠簸）
在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。
频繁的发生缺页中断（抖动），其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提髙系统效率。在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。但如果管理不当，处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，这就会大大降低系统效率。
工作集（驻留集）
工作集（或驻留集）是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。
工作集模型的原理是：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。
正确选择工作集的大小，对存储器的利用率和系统吞吐量的提嵩，都将产生重要影响。
