操作系统之-页面置换算法（java代码模拟）

一：页面置换算法简介

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无

空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘

的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的

算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏，将直接影响到系统

的性能。

一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不

再会访问的页面换出，或把那些在较长时间内不会再访问的页面调出。目前存在着许多种

置换算法，它们都试图更接近于理论上的目标。

二:常用到的页面置换算法

1、最佳置换算法(Optimal)) （该算法主要是用来度量其他算法）

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，

将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，

通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面

中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用

该算法去评价其它算法。

2、先进先出置换算法(FIFO)

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻

留时间最久的页面予以淘汰。先进先出这个特性会想到的是队列，算法思想就是先写入到同一个队列

里面，然后设置一个指针（替换指针），让它指向最老的页面。

下面就是Java代码模拟FIFO置换算法：

使用队列记录对应内存空间位置以及页面数据：

PrintUtils这个工具类主要输出的是过程数据

/** * 没有用计数方法，使用的队列记录对应位置 * @param numbers * @param memorySize */public static void FIFOPages(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    String[] ways = new String[memorySize];    Queue queue = new LinkedList<>();    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        int number = numbers[i];        long count = queue.stream().filter(page -> page.getData().equals(number)).count();        if (count <= 0) {            int size = queue.size();            if (size >= memorySize) {                size = queue.poll().getMemoryPosition();            }            queue.add(new Page(number, size));            pages[size] = numbers[i];            sum++;            sums[i] = true;        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}@Setter@Getter@AllArgsConstructor@ToStringpublic class Page {    private Integer data;    private Integer memoryPosition;}

3、最近最久未使用置换算法（LRU：Least Recently Used）

LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一

个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最

近最久未使用的页面

模拟代码：

public static void URLPage(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    // 页面计数    int[] counts = new int[memorySize];    String[] ways = new String[memorySize];    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        if (!havePage(pages, numbers[i], counts)) {            int maxCount = getMaxCount(counts);            pages[maxCount] = numbers[i];            counts[maxCount] = 1;            sum++;            sums[i] = true;        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}/** * 获取最先进入的数据，如果计数最大说明是最先进来的，并且每一个对应计数+1 * * @param counts * @return */private static int getMaxCount(int[] counts) {    int index = 0;    int max = 0;    for (int i = 0; i < counts.length; i++) {        if (counts[i] == -1) {            index = i;            break;        }        if (counts[i] > max) {            max = counts[i];            index = i;        }        counts[i]++;    }    return index;}
/** * 查看当前内存块中是否有当前页，如果没有就是要置换掉最先进入的页，并且计数+1,有就计数变为1，因为已经被访问了 * * @param pages * @param page * @param counts * @return */private static boolean havePage(int[] pages, int page, int[] counts) {    boolean isHave = false;    for (int i = 0; i < pages.length; i++) {        counts[i]++;        if (pages[i] == page) {            isHave = true;            counts[i] = 1;        }    }    return isHave;}

4、Clock置换算法

  （1）简单的Clock置换算法

当采用简单 Clock 算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过

链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。置换算法在选择一页淘

汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不

换出，而给该页第二次驻留内存的机会，再按照 FIFO 算法检查下一个页面。当检查到队列

中的最后一个页面时，若其访问位仍为 1，则再返回到队首去检查第一个页面。图 4-31 示

出了该算法的流程和示例。由于该算法是循环地检查各页面的使用情况，故称为 Clock 算法。

但因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过

的页面换出去，故又把该算法称为最近未用算法 NRU(Not Recently Used)

模拟代码如下：

public static void ClocksPage(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    // 页面计数    int[] counts = new int[memorySize];    int index = 0;    String[] ways = new String[memorySize];    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        int number = numbers[i];        if (havePage(pages, number, counts)) {            index = (index + 1) % memorySize;        } else {            while (true) {                int indexs = (index + 1) % memorySize;                if (pages[index] == -1 || (counts[index] == 0 && pages[index] != number)) {                    pages[index] = number;                    counts[index] = 1;                    sum++;                    sums[i] = true;                    index = indexs;                    break;                }                if (pages[index] != number) {                    counts[index] = 0;                    index = indexs;                }            }        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}
/** * 查看当前内存块中是否有当前页 * * @param pages * @param page * @param counts * @return */private static boolean havePage(int[] pages, int page, int[] counts) {    boolean isHave = false;    for (int i = 0; i < pages.length; i++) {        if (pages[i] == page) {            isHave = true;            counts[i] = 1;        }    }    return isHave;}

   （2）改进型Clock置换算法

简单时钟只有一个标记位，但是改进型是多加了一个标记位，简单时钟最多遍历2遍，改进型的最多比遍历4遍。

算法书里面是这样描述的：

假设 search标识访问标记位，update表示修改标记位，下面就有这样的一个规则

•  

• 1 类( search  =0， update  =0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。

• 2 类( search  =0， update  =1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。

• 3 类( search  =1， update  =0)：表示该页最近已被访问，但未被修改，该页有可能再被访问。

• 4 类( search  =1， update  =1)：表示该页最近已被访问且被修改，该页可能再被访问。 

(1) 从指针所指示的当前位置开始，扫描循环队列，寻找 search  =0 且  update  =0 的第一类页面，

将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位  search  。

(2) 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找  search  =0

且  update  =1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所

有扫描过的页面的访问位都置 0。

(3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所

有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到

被淘汰的页。

该算法与简单 Clock 算法比较，可减少磁盘的 I/O 操作次数。但为了找到一个可置换的

页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。

模拟代码如下：

public static void ClocksPage(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    // 记录访问状态    int[] search = new int[memorySize];    // 记录修改状态    int[] update = new int[memorySize];    int index = 0;    String[] ways = new String[memorySize];    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        int number = numbers[i];        boolean isHave = false;        for (int page : pages) {            if (page == number) {                isHave = true;                break;            }        }        if (!isHave) {            sums[i] = true;            sum++;            int count = 0;            int start = index;            while (true) {                int j = (index + 1) % memorySize;                if (j == start) {                    ++count;                }
                if (count == 0 || count == 2) {                    if (search[index] == 0 && update[index] == 0) {                        pages[index] = number;                        search[index] = 1;                        update[index] = 1;                        index = j;                        break;                    }                } else {                    if (search[index] == 0 && update[index] == 1) {                        pages[index] = number;                        search[index] = 1;                        update[index] = 1;                        index = j;                        break;                    }                }                if (count != 0) {                    search[index] = 0;                }                index = j;            }        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}

5、最少使用置换算法（LFU：Least Frequently Used）

在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记

录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。由于存

储器具有较高的访问速度，例如 100 ns，在 1 ms 时间内可能对某页面连续访问成千上万次，

因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每

次访问某页时，便将该移位寄存器的最高位置 1，再每隔一定时间(例如 100 ms)右移一次。

这样，在最近一段时间使用最少的页面将是∑Ri 最小的页。

LFU 置换算法的页面访问图与 LRU 置换算法的访问图完全相同；或者说，利用这样一

套硬件既可实现 LRU 算法，又可实现 LFU 算法。应该指出，LFU 算法并不能真正反映出

页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因

此，访问一次和访问 10 000 次是等效的。

6、页面缓冲算法（PBA：Page Buffering Algorithm）

虽然 LRU 和 Clock 置换算法都比 FIFO 算法好，但它们都需要一定的硬件支持，并需

付出较多的开销，而且，置换一个已修改的页比置换未修改页的开销要大。而页面缓冲算

法(PBA)则既可改善分页系统的性能，又可采用一种较简单的置换策略。VAX/VMS 操作系

统便是使用页面缓冲算法。它采用了前述的可变分配和局部置换方式，置换算法采用的是

FIFO。该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将

它直接放入空闲链表中；否则，便放入已修改页面的链表中。须注意的是，这时页面在内

存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。

空闲页面链表，实际上是一个空闲物理块链表，其中的每个物理块都是空闲的，因此，

可在其中装入程序或数据。当需要读入一个页面时，便可利用空闲物理块链表中的第一个

物理块来装入该页。当有一个未被修改的页要换出时，实际上并不将它换出内存，而是把

该未被修改的页所在的物理块挂在自由页链表的末尾。类似地，在置换一个已修改的页面

时，也将其所在的物理块挂在修改页面链表的末尾。利用这种方式可使已被修改的页面和

未被修改的页面都仍然保留在内存中。当该进程以后再次访问这些页面时，只需花费较小

的开销，使这些页面又返回到该进程的驻留集中。当被修改的页面数目达到一定值时，例

如 64 个页面，再将它们一起写回到磁盘上，从而显著地减少了磁盘 I/O 的操作次数。一个

较简单的页面缓冲算法已在 MACH 操作系统中实现了，只是它没有区分已修改页面和未修

改页面。

参考书籍：《计算机操作系统第三版》汤小丹等著

完整代码地址：

https://gitee.com/yh128/SpringDemoProject/tree/master/blog-code

                                            文章同时会更新到公众号，觉得对你有帮助或者有用的可以关注一下哦 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！