操作系统实验之请求页式管理（页面置换算法）

一、实验目的

理解内存的虚拟分配存储管理技术；理解请求分页存储管理的思想；.掌握常用的页面置换算法的思想

二、实验环境概述

C语言或其它高级语言

三、实验内容

对教材中所讲述的几种页面调度算法进行深入的分析，设计一个程序模拟实现一个作业在内存中执行的页面置换，并计算缺页中断次数。编程实现三种页面置换算法：
1）FIFO页面置换算法；2）LRU页面置换算法：3）OPT最佳页面置换算法

四、实验原理

1）FIFO页面置换算法；

初始化内存帧：

'frames[MAX_FRAME
'框架
'pageFaults
页面访问循环：

通过循环遍历页面访问顺序（pages数组）。
对于每个访问的页面，检查它是否已经在内存中（页面命中）。
页面是否在内存中的判断：

通过遍历内存中的页面帧，检查当前访问的页面是否已经在内存中。
页面置换：

如果页面不在内存中（页面未命中），则将该页面放入内存中的某个页面帧中。
使用FIFO算法的特性，即将页面放入队列的尾部，如果内存已满，则替换队列的头部页面。
更新内存状态：

在每次页面访问后，打印当前内存状态，以显示哪些页面帧被占用。
统计页面缺页中断次数：

统计页面缺页中断的次数，即发生页面置换的次数。
打印总的页面缺页中断次数：

在算法执行完毕后，打印总的页面缺页中断次数。

2）LRU页面置换算法：

LRU 页面置换算法原理解释
LRU（Least Recently Used）页面置换算法是一种基于最近使用过的页面的思想来进行页面置换的算法。其基本原理如下：

维护页面访问顺序：

对于每个页面的访问，记录或维护一个页面访问顺序的数据结构，通常是一个队列或链表。
最近访问的页面排在队列的前面，而最早访问的页面排在队列的末尾。
页面访问时的更新：

当一个页面被访问时，将该页面移动到访问顺序的队列或链表的最前面，表示这个页面是最近使用过的。
页面替换时的策略：

当需要进行页面替换时，选择访问顺序队列或链表中最后一个位置的页面进行替换。
这样即替换了最久未使用的页面，保持了最近使用过的页面在内存中。
在上述代码中，实现了以下关键点：

使用 pageOrder 数组来记录页面的访问顺序，每次访问页面都更新这个数组。
在发生页面缺页中断时，选择 pageOrder 数组中最后一个位置的页面进行替换。
这样，LRU 页面置换算法就能够在页面替换时选择最近最少使用的页面，以尽量减少缺页中断的发生。

3）OPT最佳页面置换算法

未来最长时间不被访问的页面：

对于每个页面访问，找到未来最长时间不会被访问的页面。
这样的页面最理想地被替换，因为它在未来最长的时间内都不会再被使用。
实现方法：

使用一个函数 findOptimal 来找到未来最长时间不会被访问的页面。
该函数在当前页面访问后的未来访问序列中查找最远的下一个访问位置。
页面访问循环：

针对每个页面访问，检查页面是否已在内存中。
页面是否在内存中的判断：

如果页面已在内存中，无需操作。
页面置换：

如果页面未在内存中，调用 findOptimal 找到未来最长时间不会被访问的页面，进行页面置换。
统计页面缺页中断次数：

统计每次页面未命中时发生的页面缺页中断次数。
打印总的页面缺页中断次数：

在整个算法执行完毕后，打印总的页面缺页中断次数。

五、实验步骤

1）FIFO页面置换算法；

#include <stdio.h>

#define MAX_FRAMES 3 // 页面帧数

#define MAX_PAGES 10 // 页面总数

void fifoPageReplacement(int pages[], int n) {

int frames[MAX_FRAMES];

int frameIndex = 0;

int pageFaults = 0;

for (int i = 0; i < MAX_FRAMES; i++) {

frames[i] = -1; // 初始化页面帧

}

for (int i = 0; i < n; i++) {

int currentPage = pages[i];

int pageHit = 0;

// 检查页面是否已在内存中

for (int j = 0; j < MAX_FRAMES; j++) {

if (frames[j] == currentPage) {

pageHit = 1;

break;

}

// 页面不在内存中，进行页面置换

if (!pageHit) {

frames[frameIndex] = currentPage;

frameIndex = (frameIndex + 1) % MAX_FRAMES;

pageFaults++;

}

// 打印当前内存状态

printf("Step %d: ", i + 1);

for (int j = 0; j < MAX_FRAMES; j++) {

printf("%d ", frames[j]);

}

printf("
");

}

printf("
Total Page Faults: %d
", pageFaults);

}

int main() {

int pages[MAX_PAGES] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1};

int n = sizeof(pages) / sizeof(pages[0]);

printf("FIFO Page Replacement Algorithm
");

fifoPageReplacement(pages, n);

return 0;

}

2）LRU页面置换算法：

#include <stdio.h>

#define MAX_FRAMES 3 // 页面帧数

#define MAX_PAGES 10 // 页面总数

void lruPageReplacement(int pages[], int n) {

int frames[MAX_FRAMES];

int pageOrder[MAX_PAGES]; // 用于记录页面的访问顺序

int pageFaults = 0;

for (int i = 0; i < MAX_FRAMES; i++) {

frames[i] = -1; // 初始化页面帧

}

for (int i = 0; i < n; i++) {

int currentPage = pages[i];

int pageHit = 0;

// 检查页面是否已在内存中

for (int j = 0; j < MAX_FRAMES; j++) {

if (frames[j] == currentPage) {

pageHit = 1;

// 更新页面访问顺序

for (int k = 0; k < MAX_PAGES; k++) {

if (pageOrder[k] == currentPage) {

// 移动当前页面到最近使用的位置

for (int l = k; l > 0; l--) {

pageOrder[l] = pageOrder[l - 1];

}

pageOrder[0] = currentPage;

break;

}

break;

}

// 页面不在内存中，进行页面置换

if (!pageHit) {

int replacedPage = frames[MAX_FRAMES - 1];

// 将最近最少使用的页面替换出去

for (int j = 0; j < MAX_FRAMES; j++) {

if (frames[j] == replacedPage) {

frames[j] = currentPage;

break;

}

// 更新页面访问顺序

for (int j = MAX_PAGES - 1; j > 0; j--) {

pageOrder[j] = pageOrder[j - 1];

}

pageOrder[0] = currentPage;

pageFaults++;

}

// 打印当前内存状态

printf("Step %d: ", i + 1);

for (int j = 0; j < MAX_FRAMES; j++) {

printf("%d ", frames[j]);

}

printf("
");

}

printf("
Total Page Faults: %d
", pageFaults);

}

int main() {

int pages[MAX_PAGES] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1};

int n = sizeof(pages) / sizeof(pages[0]);

printf("LRU Page Replacement Algorithm
");

lruPageReplacement(pages, n);

return 0;

}

3）OPT最佳页面置换算法

#include <stdio.h>

#include <limits.h>

#define MAX_FRAMES 3 // 页面帧数

#define MAX_PAGES 10 // 页面总数

int findOptimal(int frames[], int pages[], int start, int end) {

int index = -1, farthest = start;

for (int i = 0; i < MAX_FRAMES; i++) {

int j;

for (j = start; j < end; j++) {

if (frames[i] == pages[j]) {

if (j > farthest) {

farthest = j;

index = i;

}

break;

}

if (j == end)

return i;

}

return (index == -1) ? 0 : index;

}

void optPageReplacement(int pages[], int n) {

int frames[MAX_FRAMES];

int pageFaults = 0;

for (int i = 0; i < MAX_FRAMES; i++) {

frames[i] = -1; // 初始化页面帧

}

for (int i = 0; i < n; i++) {

int currentPage = pages[i];

int pageHit = 0;

// 检查页面是否已在内存中

for (int j = 0; j < MAX_FRAMES; j++) {

if (frames[j] == currentPage) {

pageHit = 1;

break;

}

// 页面不在内存中，进行页面置换

if (!pageHit) {

int index = findOptimal(frames, pages, i + 1, n);

frames[index] = currentPage;

pageFaults++;

}

// 打印当前内存状态

printf("Step %d: ", i + 1);

for (int j = 0; j < MAX_FRAMES; j++) {

printf("%d ", frames[j]);

}

printf("
");

}

printf("
Total Page Faults: %d
", pageFaults);

}

int main() {

int pages[MAX_PAGES] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1};

int n = sizeof(pages) / sizeof(pages[0]);

printf("OPT Page Replacement Algorithm
");

optPageReplacement(pages, n);

return 0;

}

六、实验结论及感悟

1）FIFO页面置换算法；

2）LRU页面置换算法：

3）OPT最佳页面置换算法

FIFO 页面置换算法：

FIFO 在实现方面表现出简单性，但在某些情况下可能会导致性能欠佳。
在最旧的页面不一定是将来最不可能使用的情况下，该算法往往会受到影响。
LRU 页面置换算法：

与FIFO相比，LRU表现出更好的性能，通过考虑页面的最近访问历史。
但是，LRU 的实现涉及维护和更新页面访问历史记录，这可能会增加开销。
OPT 页面置换算法：

从理论上讲，OPT通过替换时间最长的页面来表示最佳的页面替换策略。
在实际场景中，实施 OPT 具有挑战性，因为未来需要了解页面访问，而这通常是不可用的。

算法复杂度：

反思实现每种算法的复杂性，以及在简单性与最佳性方面所涉及的权衡。
实际挑战：

讨论实施过程中面临的任何挑战，例如对 OPT 未来知识的需求或在 LRU 中维护访问历史记录的潜在开销。
性能比较：

比较这三种算法在页面错误总数和管理页面替换效率方面的性能。
教育价值：

反思实验如何增强了您对虚拟内存管理概念的理解，以及不同页面替换策略的实际意义。