操作系统(OS, Operating System)对于内存(Memory)管理的方式有许多种,这篇文章将会说明当使用分页(Paging)的方法管理内存时,若发生了分页错误(Page fault),操作系统要如何找到一个适当的分页(Page),并将其取代成新的内容,尽量让未来发生分页错误的机会降到最低。

分页(Paging)

许多操作系统,如 Linux、Windows、macOS,都使用分页的方式来管理内存。分页技术应用在虚拟内存(Virtual Memory)上,将一块物理内存(Physical Memory)切成数个固定大小的页框(Frame),再将一块虚拟内存切成数个固定大小的分页(Page),页框和分页的大小必须一样,接着再借由分页表(Page Table)将各个分页去对应物理内存的页框(Frame)。这样的作法可以带来多种好处,好比连续的虚拟内存空间在物理内存空间上也不一定需要连续,使得内存更容易配置(Allocate),因为不需要在杂乱物理内存空间上寻找可用的连续空间。另外,虚拟内存空间可以大于等于物理内存空间,超出的空间可以使用辅助内存(Secondary Memory),如硬盘、记忆卡等保存设备来保存,等到有需要访问的时候,再替换(Replacement)至物理内存空间。

在 Linux 系统中,虚拟内存的大小等于物理内存空间的大小加上所有在辅助内存上可用的 SWAP 空间。Linux 的 SWAP 空间可以直接用磁盘分割的方式来配置出 SWAP 分割区,分割区的大小就是 SWAP 空间的大小;也可以在现有的文件系统下创建一个专门用来进行 SWAP 的文件,文件的大小就是 SWAP 空间的大小。

在 Windows 系统中,虚拟内存的大小等于物理内存空间的大小加上所有硬盘分割区下的分页文件大小。

分页错误(Page fault)

当操作系统要访问某个分页时,会先去分页表中搜索该分页的分页项目(PTE, Page Table Entry),这个分页项目会保存分页对应的页框,以及其他关于这个分页一些信息,例如这个分页目前是不是正存在于物理内存中(是不是有页框可以使用)。若要访问的分页不存在于物理内存中,就会发生分页错误(Page fault),此时就需要替这个分页寻找一个页框来使用。这个在发生分页错误后,寻找页框并使用的动作就称为分页替换(Page Replacement)。

分页替换(Page Replacement)

如果物理内存中还有没使用到的页框,可以直接将分页的内容从辅助内存移进(swap in)这个物理内存的页框中;如果物理内存中所有的页框都已经被分页使用,那么只好想办法找出一个未来可能要很久才会再被用到的页框中其他分页的内容,将其移出(swap out)至辅助内存中保存,接着再将辅助内存中要使用的分页内容移进(swap in)这个物理内存的页框中。由于这个移出移入(swap in/out)的动作需要许多时间来完成,因此我们会希望分页替换的次数愈少愈好。也就是说,我们要让分页被替换后,再次发生分页错误的机会降低。分页错误的次数愈少,操作系统的运作性能就能愈好,同时也能减少对辅助内存的读写次数,延长硬件寿命。

分页替换算法(Page Replacement Algorithm)

以下将分别使用不同算法来实际模拟当要在三个页框的物理内存情况下,连续访问「E F A B F C F D B C F C B A B」以字母代号表示的分页时的流程。

First in First out Page Replacement (FIFO)

将存在于物理内存页框中最久的分页给取代掉,实作起来最为容易。流程如下表,表格填色的部份表示下一次分页错误发生时要拿来进行替换的页框。

FIFO 分页替换的流程表

分页错误的次数为 12 次。

Least Recently Used Page Replacement (LRU)

将存在于物理内存页框中最久没用到的分页给取代掉,实作起来比起 FIFO 稍微困难,需使用计数变量(Counter)去保存每个在页框内的分页使用后闲置的时间,或是如 Linked List 等额外的数据结构来保存过去页框中的分页使用的顺序,但实行起来成效显著。流程如下表,分页后数字的部份为最近使用的排序,数字愈小表示愈久之前使用过。

LRU 分页替换的流程表

分页错误的次数为 10 次。

The Clock Page Replacement (Second Chance)

基于 FIFO,但是会重新给予被使用到的分页第二次机会,使其可以跳过一次页框被别的分页选择取代的命运。概念上类似 LRU,能保留最近使用过的页框,但比 LRU 还要容易实作得多。流程如下表,分页后数字的部份为剩余可跳过被选择取代的次数。

Clock 分页替换的流程表

分页错误的次数为 11 次。

Random Page Replacement

基于 FIFO,只是当没有可用的页框时,会随机选取一个页框来替换。流程如下表:

Random 分页替换的流程表

分页错误的次数为 10 次(随机)。

Optimal Page Replacement

基于 FIFO,将于物理内存页框中,不会再次被使用或是最久才会再次被使用的分页给取代掉,实作起来非常困难,因为要预知未来可能会访问的分页,但是这个将会是理想最佳解。流程如下表:

Optimal 分页替换的流程表

分页错误的次数仅为 8 次(最佳)。

实作与模拟分页替换

如果想要更了解不同分页替换算法的运作流程,可以查看以下这支程序的源代码,也可以使用这支程序来进行简单的模拟:

使用 PageFaultAlgorithm

本程序只提供命令行界面,使用方式很简单,可以使用以下指令来运行:

java -jar PageFaultAlgorithm.jar

运行后可以选择要使用的算法,以及页框数量和要依序参考的分页。

运行 PageFaultAlgorithm.jar 并选择算法

也可以直接在命令行参数传入要使用的算法,以及页框数量和要依序参考的分页,指令格式如下:

java -jar PageFaultAlgorithm.jar ALGORITHM NUMBER_OF_FRAMES REFERENCES...

以命令行参数运行 PageFaultAlgorithm.jar

以命令行参数模拟的分页替换结果