文章目录

一、概述

 （1）置换算法

 （2）缺页率与命中率

二、先进先出置换算法（FIFO）

   (1)定义

   (2)示例

 （3）Belady异常

 三、最近最久未使用置换算法（LRU）

（1）定义

（2）示例

四、FIFO&LRU置换算法的模拟

   (1)流程图

 （2）完整代码

 （3）实验结果

一、概述

（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 
#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