文章目录
一、概述
（1）置换算法
进程运行时，若其访问的页面不在内存中而需要将其调入，但内存已经无空闲空间时，就需要从内存中调出一页程序或者数据，送入磁盘的对换区。
选择调出页面的算法就称为页面置换算法。常见的页面置换算法有以下四种：
- 最佳置换算法（OPT）
- 先进先出页面置换算法（FIFO）
- 最近最久未使用置换算法（LRU）
- 时钟置换算法（CLOCL）
（2）缺页率与命中率
当前访问的页面不在内存中时，此时发生缺页中断，选择合适的页面置换算法来从内存中调出一页程序或者数据，送入磁盘的对换区，与当前要访问的页面进行置换，从而满足当前的访问需求。这种情况就叫缺页，相反，如果当前访问的页面在内存中时，即为命中。二者有如下关系：
- 缺页率+命中率=1
- 缺页率=缺页次数/总页面访问次数
- 命中率=命中次数/总页面访问次数
本次实验重点是模拟先进先出和最近最久未使用算法的执行过程。
二、先进先出置换算法（FIFO）
(1)定义
优先淘汰那些最早进入内存的页面，即淘汰在内存中驻留时间最久的页面。该算法实现简单，只需把已调入内存的页面根据先后次序链接成队列，设置一个指针总是指向最老的页面。
(2)示例
假定系统为某个进程分配了3个物理块,访问页面依次如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
按照FIFO算法， 当依次访问页面7,0,1时，由于都不在内存中发生缺页中断，因为有3个物理块且内存空闲，所以可以不用置换页面直接将这三个页面依次放入内存中；当访问页面2时，由于不在内存中，发生缺页中断，此时按照FIFO置换算法将内存中最早进入内存的页面7与2置换，让2进入内存，后面以此类推。
（3）Belady异常
分配给进程的物理块增多，但是缺页率却不减反增的现象被称之为Belady异常。如图：
当进程有3个物理块时，缺页次数为9，缺页率为75%
当进程有4个物理块时，缺页次数为10，缺页率为83.33%
另外，只有FIFO算法会出现Belady异常，其它算法不会出现这种情况！
三、最近最久未使用置换算法（LRU）
（1）定义
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
（2）示例
再对上面的例子采用LRU算法进行页面置换，如图3.25所示。进程第一次对页面 2访问时，将最近最久未被访问的页面7置换出去。然后在访问页面3时，将最近最久未使用的页面1换出。
LRU算法的性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO 算法基于队列实现，不是堆栈类算法。
四、FIFO&LRU置换算法的模拟
(1)流程图
（2）完整代码
/*
虚拟存储器之页面置换算法的模拟
测试数据1：20个访问的页面 3个物理块:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
测试数据2:10个访问页面 2个物理块
4 2 3 0 3 2 1 2 0 1
*/
#include <stdio.h>
#define phy 100
#define page 100//页面最大数
#define phyBlock 100//物理块最大数
int phyBlockNum;//物理块的数量
int pageNum;//页面数量
int pageNumStrList[page];//保存页面号引用串
//初始化队列
void initializeList(int list[], int number)
{
for (int i = 0; i < number; i++)
{
list[i] = -1;
}
}
//展示当前队列状态
void showList(int list[], int number)
{
for (int i = 0; i < number; i++)
{
printf("%2d", list[i]);
}
printf("\n");
}
//展示当前系统内存状态
void showMemoryList(int list[], int phyBlockNum)
{
for (int i = 0; i < phyBlockNum; i++)
{
if (list[i] == -1)
{
break;
}
printf(" |%d|\t", list[i]);
}
printf("\n");
}
//页面置换结果分析统计
void informationCount(int missingCount, int replaceCount, int pageNum)
{
printf("---------------------------结果分析--------------------------\n");
printf("缺页次数:%d\n", missingCount);
double a=(double)missingCount/pageNum;//计算缺页率以百分号形式表示
printf("缺页率:%.2f%%\n", a*100);
double result = (double)(pageNum - missingCount) / (double)pageNum;
printf("置换次数:%d\n", replaceCount);
printf("------------------------------------------------------------\n");
}
//寻找该页面下次要访问的位置
int getNextPosition(int currentPage, int currentPosition, int strList[], int pageNum)
{
for (int i = currentPosition + 1; i < pageNum; i++)
{
if (strList[i] == currentPage)
{
return i;
}
}
return 100;
}
//FIFO:先进先出置换算法
void replacePageByFIFO(int memoryList[], int phyNum, int strList[], int pageNum) {
int replaceCount = 0; //置换次数
int missingCount = 0; //缺页次数
int pointer = 0; //记录当前最早进入内存的下标
int isVisited = 0;//记录当前页面的访问情况: 0表示未访问，1表示已访问
for (int i = 0; i < pageNum; i++) {
isVisited = 0;
//判断是否需要置换，内存已满且需要访问的页面不在内存中
for (int j = 0; j < phyNum; j++) {
if (memoryList[j] == strList[i]) {
//1.该页面已经存在内存中
//修改访问情况
isVisited = 1;
//修改访问时间
printf("%d\t", strList[i]);
printf("\n");
break;
}
if (memoryList[j] == -1) {
//2.页面不在内存中且内存未满则直接存入即可
memoryList[j] = strList[i];
//修改访问情况
isVisited = 1;
missingCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
break;
}
}
//当前页面还未被访问过，需要进行页面置换
if (!isVisited) {
//直接把这个页面存到所记录的下标中
memoryList[pointer] = strList[i];
pointer++; //下标指向下一个
//如果到了最后一个，将下标归零
if (pointer > phyNum - 1) {
pointer = 0;
}
missingCount++;
replaceCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
}
}
informationCount(missingCount, replaceCount, pageNum);
}
//LRU:最近最久未使用置换算法
void replacePageByLRU(int memoryList[], int phyNum, int strList[], int pageNum) {
int replaceCount = 0;//置换次数
int missingCount = 0; //缺页次数
int timeRecord[phy]; //记录内存中最近一次访问至今的时间
initializeList(timeRecord, phyNum);
int isVisited = 0;
//记录已经在内存中的页面数量
int pageCount = 0;
for (int i = 0; i < pageNum; i++) {
isVisited = 0;
//时间加一
for (int p = 0; p < pageCount; p++) {
if (memoryList[p] != -1) {
timeRecord[p] ++;
}
}
//是否需要置换
for (int j = 0; j < phyNum; j++) {
if (memoryList[j] != -1) {
timeRecord[j] ++;
}
if (memoryList[j] == strList[i]) {
//该页面已经存在内存中
//修改访问情况
isVisited = 1;
//重置访问时间
timeRecord[j] = -1;
printf("%d\t", strList[i]);
printf("\n");
break;
}
if (memoryList[j] == -1) {
//页面不在内存中且内存未满，直接存入
memoryList[j] = strList[i];
pageCount++;
//修改访问情况
isVisited = 1;
//修改访问时间
timeRecord[j]++;
missingCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
break;
}
}
//不在内存中，则需要进行页面置换
if (!isVisited) {
//1.遍历时间记录表，寻找最久未访问的页面所在的内存下标
int max = 0;
for (int k = 0; k < phyNum; k++) {
if (timeRecord[max] < timeRecord[k]) {
max = k;
}
}
//2.将该位置的页面换出
memoryList[max] = strList[i];
timeRecord[max] = -1;
missingCount++;
replaceCount++;
printf("%d\t", strList[i]);
showMemoryList(memoryList, phyNum);
}
}
informationCount(missingCount, replaceCount, pageNum);
}
//测试
int main(int argc, const char* argv[])
{
printf("------------------虚拟存储器之页面置换算法------------------\n");
printf("请输入内存的物理块数量:");
scanf("%d", &phyBlockNum);
//生成内存队列
int memoryList[phyBlock];
//初始化内存状态
initializeList(memoryList, phyBlockNum);
//showMemoryList(memoryList,phyBlockNum);
printf("请输入要访问的页面总数:");
scanf("%d", &pageNum);
printf("请输入要访问的页面号:");
for (int i = 0; i < pageNum; i++) {
scanf("%d", &pageNumStrList[i]);
}
printf("------------------------------------------------------------\n");
int chose;
while (1)
{
printf("★请选择你要执行的操作：(1.FIFO算法 2.LRU算法 3.退出):");
scanf("%d", &chose);
switch (chose)
{
case 1:
printf("------------------------------------------------------------\n");
printf("页面号\t");
for(int i=0;i<phyBlockNum;i++){
printf("物理块%d\t",i+1);
}
printf("\n");
replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
//重新初始化内存
initializeList(memoryList, phyBlockNum);
break;
case 2:
printf("------------------------------------------------------------\n");
printf("页面号\t");
for(int i=0;i<phyBlockNum;i++){
printf("物理块%d\t",i+1);
}
printf("\n");
replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
//重新初始化内存
initializeList(memoryList, phyBlockNum);
break;
default:
printf("退出成功");
return 0;
break;
}
}
return 0;
}
（3）实验结果
最后， 如果本文内容对你有所帮助，记得点赞收藏哈。
本文含有隐藏内容，请 开通VIP 后查看