操作系统实验 实验4 页面置换算法
1.实验目的
了解请求分页管理的基本思想，掌握调页策略，掌握常用的页面置换算法。
2.实验要求
采用先进先出或最近最久未使用（LRU）算法，实现分页管理的缺页调度。
- 实验内容：
- 实验内容
采用先进先出或最近最久未使用（LRU）算法，实现分页管理的缺页调度。要求用C语言编写模拟程序并进行调试。
（1）相关知识及其分析
每当程序所要访问的页面未在内存时， 便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存原物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。常见置换算法有：最佳置换算法(Optimal)、 先进先出(FIFO)页面置换算法、最近最久未使用（LRU）置换算法、时钟（CLOCK）置换算法、最少使用(LFU)置换算法、页面缓冲算法(PBA)等。本实验重点实现LRU置换算法。
最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：① 寄存器 ②栈。
实现流程如图3所示。
实验代码如下：
#include <stdio.h> #include <stdlib.h> // 提供标准库函数，如内存分配函数等 #include <conio.h> // 提供控制台输入输出函数，如getche() #include <iostream> #define M 4 // 内存块数量，即可以同时存放的页面数 #define N 17 // 页面引用序列长度，即模拟过程中访问的页面总数 // 表格输出格式宏定义，用于打印内存状态表格的分隔线 #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-+|\n") using namespace std; // 页面结构体定义，用于表示内存中的一个页面 typedef struct page {int num; // 页面号，标识具体的页面int time; // 时间戳：记录上次使用时间，用于LRU算法判断最近最少使用的页面 } Page;Page b[M]; // 内存单元数组，最多可存放M个页面 int c[M][N]; // 记录内存状态的缓冲区，c[i][j]表示时间点j时内存块i中的页面号 int queue[100]; // 记录调入队列，保存所有发生页面调入的页面号 int K; // 调入队列计数器，记录调入操作的次数// 初始化内存和缓冲区 void Init(Page *b, int c[M][N]) {int i, j;// 只初始化M个内存块，将每个内存块标记为空闲状态for (i = 0; i < M; i++) {b[i].num = -1; // -1表示该内存块当前空闲，未存放任何页面b[i].time = N - i; // 初始时间戳，确保各页面时间戳不同且不会冲突}// 初始化缓冲区，将所有位置标记为-1（表示初始时无页面）for (i = 0; i < M; i++)for (j = 0; j < N; j++)c[i][j] = -1; }// 查找最久未使用的页面，返回其在内存块数组中的索引 int GetMax(Page *b) {int i;int max = -1; // 记录最大时间戳值int tag = 0; // 记录具有最大时间戳的页面索引for (i = 0; i < M; i++) {if (b[i].time > max) {max = b[i].time;tag = i;}}return tag; // 返回最久未使用的页面索引 }// 检查页面是否已在内存中，若存在返回其索引，否则返回-1 int Equation(int fold, Page *b) {int i;for (i = 0; i < M; i++) {if (fold == b[i].num)return i; // 找到匹配页面，返回其在内存块数组中的索引}return -1; // 未找到匹配页面 }// LRU算法核心：处理页面访问请求 void Lru(int fold, Page *b) {int i;int val;val = Equation(fold, b); // 检查请求的页面是否已在内存中if (val >= 0) {// 页面已在内存中，更新时间戳：将当前页面时间戳设为0（最新），其他页面时间戳加1b[val].time = 0;for (i = 0; i < M; i++)if (i != val)b[i].time++;} else {// 页面不在内存中，需要置换queue[++K] = fold; // 记录调入的页面号，K加1val = GetMax(b); // 找到最久未使用的页面索引b[val].num = fold; // 将该内存块置换为新页面b[val].time = 0; // 新页面的时间戳设为0（最新）// 其他页面时间戳加1，表示它们的未使用时间增加for (i = 0; i < M; i++)if (i != val)b[i].time++;} }int main() {// 页面引用序列：模拟程序运行过程中访问的页面顺序int a[N] = {1, 0, 1, 0, 2, 4, 1, 0, 0, 8, 7, 5, 4, 3, 2, 3, 4};int i, j;do {K = -1; // 初始化调入队列计数器Init(b, c); // 初始化内存和缓冲区// 模拟页面访问过程for (i = 0; i < N; i++) {Lru(a[i], b); // 处理页面访问请求// 记录当前时间点的内存状态，用于后续输出for (j = 0; j < M; j++)c[j][i] = b[j].num;}// 输出模拟结果printf("内存状态为：\n");Myprintf;// 输出引用序列printf("|引用序列 ");for (j = 0; j < N; j++)printf(" |%2d", a[j]);printf(" |\n");Myprintf;// 输出每个内存块在各个时间点的状态for (i = 0; i < M; i++) {printf("|内存块 %d ", i+1);for (j = 0; j < N; j++) {if (c[i][j] == -1)printf("|%2c ", ' '); // 空闲块用空格表示elseprintf("|%2d ", c[i][j]); // 已占用块显示页面号}printf("|\n");}Myprintf;// 输出调入队列和统计信息printf("\n调入队列为:");for (i = 0; i <= K; i++)printf("%3d", queue[i]);// 计算并输出缺页次数和缺页率printf("\n缺页次数为：%6d\n缺页率：%16.6f%%\n", K+1, (float)(K+1)/N * 100);printf("是否继续? y:");} while ((getche()) == 'y'); // 按y键可重新运行模拟return 0; }二、实验过程及结果记录
实验过程：
初始状态：
程序自动加载预设的页面引用序列：
a[N] = {1, 0, 1, 0, 2, 4, 1, 0, 0, 8, 7, 5, 4, 3, 2, 3, 4}输出结果为：
关键步骤解释：
页面访问过程：
时间点 0：访问页面 1 → 内存块 1 装入页面 1（缺页）。
时间点 1：访问页面 0 → 内存块 2 装入页面 0（缺页）。
时间点 2：访问页面 1 → 页面 1 已在内存中（命中）。
时间点 4：访问页面 2 → 内存块 2 置换为页面 2（缺页）。
时间点 5：访问页面 4 → 内存块 3 装入页面 4（缺页）。
时间点 9：访问页面 8 → 内存块 2 置换为页面 8（缺页）。
时间点 11：访问页面 5 → 内存块 4 装入页面 5（缺页）。
时间点 13：访问页面 3 → 内存块 3 置换为页面 3（缺页）。
LRU 算法机制：
每次命中页面时，该页面的时间戳置为 0，其他页面时间戳 + 1。
缺页时，选择时间戳最大（最久未使用）的页面置换。
例如，时间点 9 访问页面 8 时，内存块 2 的页面 0 是最久未使用的，因此被置换为页面 8。
按y则重新进行模拟输出
修改部分：
1. 内存块初始化范围修改
原来的代码是这样的：
for(i=0;i<N;i++)
{
b[i].num=-1;
b[i].time=N-i-1;
}
修改后变成：
for(i=0;i<M;i++)
{
b[i].num=-1;
b[i].time=N-i;
}
修改原因：
原代码把循环写成了i<N，但实际上我们只需要初始化M个内存块（M是内存块总数，N是页面引用序列长度）。比如说，如果内存只能放 4 个页面（M=4），但引用序列有 17 个页面（N=17），原来的代码会尝试初始化 17 个内存块，这就会导致数组越界。现在改成i<M就对了，只初始化实际需要的内存块数量。
2. 时间戳初始化值修改
原来的时间戳初始化是：
b[i].time=N-i-1;
现在改成：
b[i].time=N-i;
修改原因：
之前的初始化方式会导致时间戳重复。比如说，当N=17，M=4时，初始化的时间戳会是 16、15、14、13（N-i-1），这样第一个内存块（i=0）和第 17 个内存块（如果初始化到那么多的话）的时间戳就会冲突（都是 16）。现在改成N-i后，时间戳变成 17、16、15、14，每个内存块的初始时间戳都不一样，避免了冲突。
3. 缺页率计算修改
原来的输出是：
printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/N);
现在改成：
printf("\n缺页次数为：%6d\n缺页率：%16.6f%%\n",K+1, (float)(K+1)/N * 100);
修改原因：
原来的代码虽然计算了缺页率，但有两个问题：一是没有乘以 100，导致显示的是小数（比如 0.588），而不是百分比（58.8%）；二是没有在输出里加百分号%。现在改了之后，先把缺页率乘以 100，再在输出格式里加上%%（在 C 语言里%%表示输出一个%符号），这样输出就正确显示为百分比了，比如58.8235%。
三、实 验 小 结
心得体会：
通过本次实验，我对请求分页管理和页面置换算法有了更深入的理解与掌握。
我初步理解了 LRU 算法原理。LRU 算法基于 “最近的过去” 作为 “最近的将来” 的近似，选择最近最久未使用的页面淘汰，这一理念在实际代码实现中得到了充分验证。通过代码中对时间戳的维护和更新，清晰地展现了如何根据页面使用情况进行决策。
我对操作系统内存管理机制有了更直观认识。从缺页中断处理流程，到页面置换时内存状态的改变，再到页表的相关操作等，都让我明白操作系统在内存管理上的复杂性和精妙之处。
通过本次实验，我锻炼了 C 语言编程能力。在编写代码过程中，涉及到结构体的定义与使用、数组的操作、函数的编写与调用等，对 C 语言的语法和编程规范更加熟悉。例如，对页面结构体中时间戳和页面号等成员的管理，以及内存块数组、记录内存状态缓冲区数组的操作等。
此外，我还提高了算法实现与调试能力。将理论的 LRU 算法转化为可运行的代码并非易事，期间遇到了诸如时间戳更新逻辑错误、页面置换时机判断不准确等问题。通过不断调试，仔细检查代码逻辑，逐步解决这些问题，让我在算法实现和调试方面积累了宝贵经验。
目前代码在功能实现上虽然达到要求，但在性能和代码结构上还有优化空间。比如，在查找最久未使用页面和检查页面是否在内存等操作中，时间复杂度较高，后续可以研究更高效的数据结构或算法来优化。
LRU 算法实际应用中需要寄存器或栈等硬件支持，实验中仅从软件模拟角度实现算法，对硬件如何配合实现该算法理解不够透彻，后续需要查阅更多资料加深这方面认识。
总体而言，这次实验不仅让我巩固了课堂所学的操作系统知识，还通过实践提升了编程和解决问题的能力，为今后深入学习操作系统及相关领域知识奠定了良好基础。
