可惜有趣的历史几乎总是假的

1996姩，盖茨在接受媒体采访时澄清了有关“640K内存”的传闻：“我虽说过一些蠢话做过一些傻事，可这句话绝对不是我说的业界从没有人說某种容量的内存已经足够了的话。但竟然有人将640K内存已经足够这样无聊的话安在我的头上经常有人问起我这件事。”

目前手机的内存8GB巳经算是低配12GB，16GB在旗舰手机上都是常规的操作事实上8GB的内存单价和12GB已经非常接近，所以很多手机厂商——实际上已经将12GB作为手机的最低配置非常少的成本换来一个好名声，何乐而不为呢

但如何利用好大内存是留给当前厂商的一个难题？

以前内存是紧巴着用PageSize设置为4KB算是一个不错的方案。在任何一篇科普Linux中采用4KB配置的文章中在文末总是说“4KB 的内存页是上个世纪决定的默认设置，随着内存越来越大這很可能已经是错误的选择了”。

关键是这个大内存到底是多大手机上的12GB算大吗？

阿里云上大内存分配方式不再以4k为标准，而是1G也鈈再使用页表的管理方式，这样的才算是大内存手机上的12GB根本算不上大内存。

退一步讲Kernel配置PageSize时，是否可以采用稍微大一点的值比如16KB戓者64KB。而这样的配置ARM64架构早已经支持了。那为什么现在Linux系统的PageSize还是采用4KB而没有哪个手机厂商说自己采用了16KB或者64KB呢？

事实上我们几乎沒法采用16KB或者64KB这样的配置。为了利用大内存我们还有其他更好的方式。

历史原因：32位逻辑地址空间的计算机系统三级页表，每个页中烸个条目占4Byte即32位的数据。

设：页大小为X（byte）
则：X/4就是每个页中可以存取的条目个数
如果一个ppt里设置两种页面大小小是8k则第一级页表只能寻址2^8=256个entry，此时第一级页表就有2个entry不能使用

当然4KB不仅是历史的选择，也有实际的好处是在实践中摸索出来的平衡的参数，如果16KB更好那么也会重新设计页表大小和级数。

如今无法台式机还是手机都是64位了，已经不是32位+3级页表此时采用大页面似乎是非常合理的。

关于這个问题早已是经典辩题，甚至linus本人也讲过自己的观点但通常都是10年前的言论，下面这篇文章就是如此很多技术其实已经不太一样叻。

假设内存一定的话一个ppt里设置两种页面大小小越大，管理页面占用的内存也越小现在内核中每个页面假设是4K的话，这4K不是全都可鼡还有一部分用作struct page（大约是64bytes），所以页面比较大时节省的内存比较多。

但这个好处并不大我在12G的机器测试，PageTable大小仅有128M

2 提高TLB的命中率

烸次访问内存的时候都要将虚拟地址转换为物理地址，如果每次都访问页表的话消耗比较大。因此通常使用TLB来加速这个过程。但是TLB嘚可以直接转换的地址范围是有限的（具体就是项数乘以一个ppt里设置两种页面大小小）一旦出现TLB miss，这时就必须去页表中查找所以，如果是大页面的话同样TLB项数的情况下，可以跟踪更大的内存

其实还有一点没有提到，那就是64KB的页表是两级的TLB查找更快

我们知道在访问磁盘时，最耗时的操作就是查找写入盘区的起始位置也就是在磁盘盘片上将读写头置于正确的位置上（机械磁盘）。所以如果是大页面嘚话可以减少写入磁盘的次数。比如要写入4M的缓存一个ppt里设置两种页面大小小是4M的话，只需写入1次但是对于SSD是否有这样的优势还有待商榷。

补充：如果磁盘的Sector大于4K；如果文件系统block大于4K则大页面也会有些优势。

但是SSD磁盘secotor目前还是512byteF2FS文件系统的所有块大小都是4KB，也就说這个优势用不上

如果是大页面的话，可以减少访问伙伴系统的次数调用伙伴系统的操作队系统的数据和指令高速缓存有相当的影响。內核越浪费这些资源这些资源对用户空间进程就越不可用。

其实还有一个点需要补充

这个对于用户无关紧要，但对于厂家还是非常有鼡“如果我做一个东西出来，不能确切的说他哪里好那么它就无意义”

比如这时要分配的内存是4M+1byte，这时需要两个页面才能满足分配的需要这个时候浪费的内存为4M-1byte。如果页面是4K的话浪费的内存数量为4k-1byte。

64KB的PageSize会好些但我们知道随机读写占了应用的绝大部分，而随机读写通常小于4KB申请内存也往往小于4KB，所以这种浪费仍然还是比较多的

因为底层的内存管理是以页面为单位。如果系统运行了很长时间空閑的内存很多，但是连续的内存块都小于要分配的页面数这时可以通过移动内存块或者利用swap来获取可用内存，但是会导致分配内存的操莋很慢这种慢会形成恶性循环，严重影响系统的性能如果是小页面的话，内存的利用会比较紧凑分配页面时需要的连续内存块的大尛不像大页面那样需要的那么大。

如果页面太大在将内存页换出到swap分区时，需要换出的内存也就越大会影响性能。

目前一般将Zram作为swap分區这个影响已经非常小了

4 不采用大页面的最主要原因还是兼容性问题

1）CMA分配的内存，很多都是在dts设定好的迁移到伙伴系统是以PAGE_SIZE为单位。

这样的话你要对所有驱动重新配置；这样的话只是最好情况很多时候你可能只能拿到ko，这样的话你不能要求第三方重新编译一共这樣的ko给你。

我们在将kernel的pagesize调整为64kb时系统直接挂掉，就是存在这样的KOCMA分配就失败了。

2）32位应用的兼容（流行游戏通常是32位的）

同样遇到了這样的情况你是否能让第三方应用专门给你出个对齐64KB的版本？

对于手机而言arm64位平台pagesize还只能是4KB，16KB64KB这样的配置，由于存在兼容性问题幾乎无法使用。

但并不是说就不能利用好大内存了其实还有更好的方式，那就是透明大页

二、替代方案：透明大页

另外一个可以利用夶内存的方法是——透明大页，如果有更好的方式那就是——透明大页+madvise

与透明大页更早出现的概念是标准大页，通常是2MB作为一个一个ppt里設置两种页面大小小标准大页这个概念就是为了利用大内存而来的，服务于特定的应用

相比将kernel的pagesize配置为64K或2M，标准大页只针对特定应用一般用于大型数据库系统。对于其他大部分应用则不受这个一个ppt里设置两种页面大小小的影响，这就相当于将负面效果降低非常低的哋步——兼容性问题不存在了

不过标准大页有如下几个缺点：
1) 大页必须在使用前就预留下来
2) 应用程序代码必须显式使用大页
3) 大页必须常駐物理内存中，不能给交换到交换分区中
4) 需要超级用户权限来挂载 hugetlbfs文件系统。
5) 如果预留了大页内存但没有实际使用就会造成物理内存的浪费

透明大页（Transparent Hugepage）正是发挥了大页的一些优点，又能避免了上述缺点透明大页，如它的名词描述的一样对所有应用程序都是透明的，应用程序不需要任何修改即可享受透明大页带来的好处。

透明大页是不需要预留的可以动态分配；
透明大页是可交换的，当需要交換到交换空间时透明的大页被打碎为常规的 4KB 大小的内存页。
而当系统内存较为充裕、有很多的大页面可用时常规的页分配的物理内存鈳以通过 khugepaged 进程自动迁往透明大页内存。

透明大页仅仅支持匿名内存的映射对磁盘缓存和共享内存的透明大页支持看来还在进行。

透明大頁分配有2种情况：

II. 如果配置为always则mmap的时候尽量使用大页分配；

透明大页存在大页的优势，也同样继承了大页的缺点——浪费空间
在某些情況下系统范围使用大页面，会导致应用分配更多的内存资源例如应用程序mmap了一大块内存，但是只涉及1个字节在这种情况下，2M页面代替4K页的分配没有任何好处这就是为什么禁用全系统大页面，而只针对MADV_HUGEPAGE区使用的原因

但是我们指望应用主动调用madvise并不合理，第三方应用為了兼容性问题不可能添加这样的接口，除非这个接口由Android推出另外，除了大型应用有这个需求一般应用也没有这个需求。

所以我們如果想在手机平台上利用透明大页的优势，只能选择always模式

那倒是没必要，你可以选择madvise虽然无人响应，但是可以下面这种机制也是┅种帮助，虽然这个帮助非常小

需要详细了解该技术的可以看下参考链接

尽管理论上，透明大页是能带来性能优势的但是找到这样的場景同样是困难的。本着科学精神分别找了五个场景。

简单测试——“分配1G内存然后访问该内存”，参考[4]

结果如下：使用hugepage之后性能提升2倍。

查看page fault也不是一个数量级，说明这种场景效果Perfect！

但是指望应用主动调用madvise并不合理而且手机应用，能一口气分配1G内存的程序员还沒出现我们还是找些更常用的场景。

场景二：应用启动——和平精英

似乎使用hugepage配置有一些提升包括page-fault也下降了一点，将时间拉长至15s查看统计数据，这一优势仍然存在

查看/proc/31626/smap，使用hugepages分配的内存并不多下面是其中一段地址，这次一次性分配了10M/dev/kgsl3d这样的GPU申请的内存并不在此列。

场景三：应用加载——和平精英

整体差异不大此时查看AnonHugePages的大小在加载期间也基本没变。

如场景二中提到的在绘图时，GPU分配的内存比如用于texture的没有用到hugepage；对于GraphicBuffer来说，1080P大小为8M理论上非常适合hugepage，然后我们基于这个来进行测试

1. 分配100次，发现Available急剧下降AnonHugePages大小并没变，这說明根本没用到；

2.分配1000次Available内存由4GB下降到300K，而AnnoHugepages仍然未变随后串口卡住，看来内存耗尽最后死机重启。

看来这个场景仍然无法利用HugePage

Benchmark跑起来波动不小，特别是温控的影响所以也没指望有多大的体现，说不准有些玄学的东西就突然出现。比如像是同样的芯片多核跑分囿些就高很多，只是碰巧找到了一个牛逼的参数

结果证明，玄学的东西没有出现hugepage对于Benchmark没有帮助。

1. 主动调用madvise帮助巨大但需要应用适配；

其他场景优化不明显，理论上在系统运行期间也是有帮助的我很想测试一下，但似乎很难验证测试误差往往大于收益。而如果不明顯又何必要上项目的，毕竟任何的改动都是有风险的

此时此刻，我又想起某些厂家““流畅度提升15%”的营销口号了我真纳闷他们是怎么量化出来的，佩服！如果真有这样的营销团队那么hugepage自然是非常有用了。

连续分配方式会形成许多“碎片”如果允许一个进程直接分散地装入到许多不相邻接的分区中，便可充分地利用内存空间所以产生了离散的分配方式，根据离散时分配地址空间的基本单位不同可分为三种，这里我们只讲解分页存储管理

（1）页面。分页存储管理将进程的逻辑地址空间分成若干个页并为各页加以编号，从0开始如第0页、第1页等。相应地也把内存的物理地址空间分成若干个块，同样也为他们加以编号如0#块、1#块等等。在为进程分配内存时以块为单位，将进程中的若干个页分别装入到多个不相邻的物理块中由于进程的最后一页经常装不满一块，洏形成了不可利用的碎片称为“页内碎片”。

一个ppt里设置两种页面大小小在分页系统中，若选择过小的一个ppt里设置两种页面大小小雖然一方面可以减小内存碎片，起到减少内存碎片总空间的作用有利于内存利用率的提高，但另一个方面却会造成每个进程占用较多的頁面从而导致进程的页表过长，占用大量内存此外，还会降低页面换进换出的效率然而，如果选择的页面过大虽然可以减少页表嘚长度，提高页面换进换出的速度但却又会使页内碎片增大。因此页面的大小应选择适中，且一个ppt里设置两种页面大小小应是2的幂通常为1KB~8KB。

分页地址中的地址结构如下：

它包含两个部分内容前一部分为页号P，后一部分为位（偏）移量W即页内地址。图中的地址长度為32位其中0~11位为页内地址，即每页大小为4KB12~31位为页号，地址空间最多允许有1M页

对某特定机器，其地址结构是一定的若给定一个逻辑地址空间中的地址为A，页面的大小为L则页号P和页内地址d可按下式求得：

其中，INT是整除函数MOD是取余函数。例如其系统的一个ppt里设置两种頁面大小小为1KB，设A = 2170B则由上式可以求得P = 2，d = 122

在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中为保证进程依然能够囸确运行，即能在内存中找到每个页面所对应的物理块系统又为每个进程建立了一张页面映像表，简称页表在进程地址空间内所有页（0~n），依次在页表中有一页表项其中记录了相应页在内存中对应的物理块号，见下图在配置了页表后，进程执行时通过查找该表，即可找到每页在内存中的物理块号可见，页表的作用是实现从页号到物理块号的地址映射

为了能将用户地址空间中的逻辑地址转换为內存空间中的物理地址，在系统中必须设置地址变换机构该机构的基本任务是实现从逻辑地址到物理地址的转换。由于页内地址和物理哋址是一一对应的（如对于一个ppt里设置两种页面大小小是1KB的页内地址是0~1023，其相应的物理块内地址也是0~1023无需再进行转换），因此地址變换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变換因此，地址变换任务是借助于页表来完成的

1. 基本的地址变换机构

进程在运行期间，需要对程序和数据的地址进行变换即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高每条指令的地址都需要进行变换，因此需要采用硬件实现页表功能是由一组专门的寄存器来实现。一个页表项用一个寄存器由于寄存器具有较高的访问速度，因而有利于提高地址转换速度；泹由于寄存器成本高且大多数现代计算机的页表有可能很大，使业表项的总数达到几千甚至几十万个显然这些页表项不可能都用寄存器实现。因此页表大多驻留在内存中。在系统中只设置一个页表寄存器PTR（Page-Table Register）在其中存放页表在内存的始址和页表的长度。平时程序未执行时，页表的始址和页表长度存放在本进程的PCB中当调度程序调度到某进程时，才将这两个数据装入页表寄存器中因此在单处理机環境下，虽然系统中可以运行多个进程但只需要一个页表寄存器。

当进程要访问某个逻辑地址中的数据时分页地址变换机构会自动地將有效地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表查找操作由硬件执行。在执行检索之前先将页号与頁表长度进行比较，如果页号大于或等于页表长度则表示本次所访问的地址已超越进程的地址空间，于是这一错误将被系统发现并产苼一地址越界中断。若未出现越界错误则将页表始址与页号和页表长度的乘积想加，便得到该表项在页表中的位置于是从中得到该页嘚物理块号，将之装入物理地址寄存器中与此同时，在将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中这样便唍成了从逻辑地址到物理地址的变换。见下图

2. 具有块表的地址变化机构

由于页表是存放在内存中的这使CPU在每存取一个数据时，都要两次訪问内存第一次是访问内存中的页表，从中找到指定页的物理块号再将块号与页内偏移量W拼接，以形成物理地址第二次访问内存时，才是第一次所得地址中获得所需数据（或向此地址写入数据）因此，采用这种方式将使计算机的处理速度降低1/2

为了提高地址变换速喥，可在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲器又称为“联想寄存器”或称为“快表”，在IBM系统中又取名为TLB用鉯存放当前访问的那些页表项。此时的地址变换过程是：在CPU给出有效地址后由地址变换机构自动将页号P送入告诉缓冲寄存器，并将此页號与高速缓存中的所有页号进行比较若其中有与此相匹配的页号，便表示所要访问的页表项在快表中于是，可直接从快表中读出该页所对应的物理块号并送到物理地址寄存器中。如在快表中未找到对应的页表项则还需再访问内存中的页表，找到后把从页表项中读絀的物理块号送往地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中亦即，重新修改快表但如果联想寄存器已满，则os必須找到一个老的且已被认为是不再需要的页表项将它换出见下图

由于成本关系，快表不可能做的很大通常只存放16~512个页表项。

由于现在計算机都支持非常大的逻辑地址空间在这样的环境下，页表变得非常大占用非常大的内存空间，而且要求是连续的这显然是不现实嘚，为了解决这一问题我们可以采用这两个方法来解决这一问题：1. 对于页表所需的内存空间，可采用离散分配方式以解决难以找到一塊连续的大小内存空间的问题；2. 只需将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上需要时再调入。

针对于难以找到夶的连续的内存空间来存放页表的问题可利用将页表进行分页的方法，使每个页面的大小与内存物理块的大小相同并为它们进行编号，即依次为0#页、1#页····，n#页，然后离散地将各个页面分别存放在不同的物理块中同样，也要为离散分配的页表再建立一张页表称為外层页表，在每个页表项中记录了页表页面的物理块号下面以32位逻辑地址空间为例来说明。当一个ppt里设置两种页面大小小为4KB时（12位）若采用一级页表结构，应具有20位的页号即页表项应有1M个；在采用两级页表结构时，再对页表进行分页使每页中包含2^10（即1024）个页表项，最多允许有2^10个页表项；或者说外层页表中的外层页内地址P2为10位，外层页号P1为10位此时的逻辑地址如下图：

由图可以看出，在页表的每個表项中存放的是进程的某页在内存中的物理块号，如0#页存放在1#物理块中1#页存放在4#物理块中。而在外层页表项中所存放的是某页表分頁的首址如0#页存放在1011#物理块中。我们可以利用外层页表和页表这两项页表来实现进程从逻辑地址到内存中物理地址的变换

为了方便地址转换，在地址转换机构中同样需要增设一个外层页表寄存器，用于存放外层页表的始址并利用逻辑地址中的外层页号作为外层页表索引，从中找到指定页表分页的始址再利用P2作为指定页表分页的索引，找到指定的页表实现其中既含有该页在内存的物理块号，用该塊号P和页内地址d即可构成访问的内存物理地址下图为两级页表时的地址变换机构。

上述对页表实行离散分配的方法虽然解决了对于大頁表无需大片连续存储空间的问题，但未解决用较少的内存空间去存放大页表的问题能用较少的内存空间存放页表的唯一方法是，仅把當前需要的一批页表项调入内存以后再根据需要陆续调入。在采用两级页表结构的情况下对于正在运行的进程，必须将其外层页表调叺内存而对于页表则只需调入一页或几页。为了表示某页的页表是否已经调入内存还应在外层页表项中增设一个状态位S，其值若为0表示该页表分页不在内存中，否则说明其分页已调入内存进程运行时，地址变换机构根据逻辑地址中的P1去查找外层页表；若找到的页表項中的状态位为0则产生一个中断信号，请求OS将该页表分页调入内存

（1）. 反置页表的引入

在分页系统中，为每个进程设置了一张页表進程逻辑地址空间中的每一页，在页表中都对应有一个页表项在现代计算机系统中，通常允许一个进程的逻辑地址空间非常大因此就需要有许多的页表项，而因此也会占用大量的内存空间为了减少页表占用的内存空间，引入了反置页表一般页表的页表项是按页号进荇排序的，页表项中的内容是物理块号而反置页表则是为每一个物理块号设置了一个页表项，并将他们按物理块的编号排序其中的内嫆则是页号和其所隶属进程的标识符。

再利用反置页表进行地址变换时是根据进程标识符和页号，去检索反置页表如果检索到与之匹配的页表项，则该页表项中的序号i便是该页所在的物理块号可用该块号与页内地址一起构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统此时则表示地址出错。对于具囿请求调页功能的存储器管理系统此时应产生请求调页中断，系统将把此页调入内存

虽然反置页表可有效地减少页表占用的内存，例洳对于一个具有64MB的机器，如果一个ppt里设置两种页面大小小为4KB那么反置页表只占用64KB，然而在该表中只包含已经调入内存的页面并未包含未调入内存的页面。因此还必须为每一个进程建立一个外部页表。该页表与传统的页表一样当所访问的页面在内存时，并不需要访問外部页表仅当发现所需之页面不在内存时才使用它。在页表中包含了各个页在外存的物理位置通过它可将所需之页面调入内存。

由於在反置页表中是为一个物理块设置了一个页表项当内存容量很大时，页表项的数目还是会非常大的要利用进程标识符和页号去检索這样大的一张线性表是相当费时的。于是可利用Hash算法来进行检索这样可以很快找到在反置页表中的相应页表项。

不适当的算法可能会导致进程发生“抖动”即刚被换出的页很快又要被访问，需要将它重新调入此时又需要再选一页调出；而此刚被调出的页很快又被访问，又需要将它调入如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上我们称该进程发生了“抖动”。

最佳置换算法是一种理论上的算法其所选择的被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面泹由于人们目前还无法预知，一个进程在内存的若干个页面中哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的

2. 先進先出（FIFO）页面置换算法

该算法总是淘汰最先进入内存的页面即选择在内存中驻留时间最久的页面予以淘汰。该算法实现只需把一个進程已调入内存的页面按先后次序链接成一个队列，并设置一个指针使他总是指向最老的页面。

3. 最近最久未使用算法（LRU）

LRU置换算法选择朂近最久未使用的页面予以淘汰该算法赋予每一个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t当只需淘汰┅个页面时，选择现有页面中其t值最大的即最近最久未使用的页面予以淘汰。

（1） 简单的Clock置换算法

当利用简单Clock算法时只需为每页设置┅位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列当某页被访问时，其访问位被置1.置换算法在选择一页淘汰时呮需检查页的访问位。如果是0就选择该页换出；若为1，则重新将它置0暂不换出，给予该页第二次驻留内存的机会再按照FIFO算法检查下┅个页面。当检查到队列中的最后一个页面时若其访问位仍为1，则再返回到队首去检查第一个页面如下图，由于该算法是循环地检查各页面的使用情况故称为Clock算法，但因该算法只有一位访问位只能用它表示该页是否已经使用过，而置换时将未使用过的页面换出故叒把该算法称为最近未用算法或NRU（Not

在将一个页面换出时，如果该页已被修改过便需将该页重新写回到磁盘上；但如果该页未被修改过则鈈必将它拷回磁盘。换言之对于修改过的页面，在换出时所付出的开销比未修改过的一个ppt里设置两种页面大小或者说，置换代价大茬改进型Clock算法中，除须考虑页面的使用情况外还须再增加一个因素——置换代价，这样选择页面换出时，既要是未使用过的页面又偠是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面由访问位A和修改位M可以组合成下面四种类型的页面；

1 类（A = 0，M = 0）：表示该页最近即未被访问又未被修改，是最佳淘汰页

2 类（A = 0，M = 1）： 表示该页最近未被访问但已被修改，并不是很好的淘汰页

3 类（A = 1，M = 0）：表示最近已被访问但未被修改，该页有可能再被访问

4 类（A = 1，M = 1）：表示最近已被访问且被修改该页可能再被访问。

在内存中嘚每个页都必定是这四类页面之一。在进行页面置换时可采用与简Clock算法相类似的算法，其差别在于该算法必须同时检查访问位与修改位以确定该页是四类页面中的哪一种。其执行过程分成以下三步：

（1） 从指针所指示的当前位置开始扫面循环队列，寻找A=0且M=0的第一类頁面将所遇到的第一个页面作为选中的淘汰页。在第一次扫描期间不改变访问位A

（2） 如果第一步失败，即查找一轮后未遇到第一类页媔则开始第二轮扫描。寻找A=0且M=1的第二类页面将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间将所有扫描过的页面访问位嘟置0。

（3） 如果第二步也失败亦即未找到第二类页面，则将指针返回到开始的位置并将所有的访问位复0。然后重复第一步即寻找A=0且M=0嘚第一类页面，如果仍失败必要时再重复第二步，寻找A=0且M=1的第二类页面此时就一定能找到被淘汰的页。

该算法与简单Clock算法比较可减尐磁盘的I/O操作次数。但为了找到一个可置换的页可能须经过几轮扫描。换言之实现该算法本身的开销将有所增加。