实验四 页式虚拟存储管理中地址转换和页式中断 FIFO LRU OPT C 版本

操作系统实验报告-页式虚拟存储管理中地址转换和缺页中断实验四页式虚拟存储管理中地址转换和缺页中断一．实验目的（1）深入了解存储管理如何实现地址转换。

（2）进一步认识页式虚拟存储管理中如何处理缺页中断。

二．实验内容编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。

三．实验原理页式存储管理把内存分割成大小相等位置固定的若干区域，叫内存页面，内存的分配以“页”为单位，一个程序可以占用不连续的页面，逻辑页面的大小和内存页面的大小相同，内外存的交换也以页为单位进行，页面交换时，先查询快表，若快表中找不到所需页面再去查询页表，若页表中仍未找到说明发生了缺页中断，需先将所需页面调入内存再进行存取。

四．实验部分源程序#define size 1024//定义块的大小，本次模拟设为1024个字节。

#include "stdio.h"#include "string.h"#includestruct plist{int number; //页号int flag; //标志，如为1表示该页已调入主存，如为0则还没调入。

int block; //主存块号，表示该页在主存中的位置。

int modify; //修改标志，如在主存中修改过该页的内容则设为1，反之设为0int location; //在磁盘上的位置};//模拟之前初始化一个页表。

struct plist p1[7]={{0,1,5,0,010},{1,1,8,0,012},{2,1,9,0,013},{3,1,1,0,021},{4,0,-1,0,022},{5,0,-1,0,023},{6, 0,-1,0,125}};//命令结构，包括操作符，页号，页内偏移地址。

struct ilist{char operation[10];int pagenumber;int address;};//在模拟之前初始化一个命令表，通过程序可以让其顺序执行。

一．实验内容模拟请求页式存储管理中硬件的地址转换和缺页中断处理 二．实验原理装入新页置换旧页时，若旧页在执行中没有被修改过，则不必将该页重写磁盘。

因此，页表中增加是否修改过的标志，执行“存”指令和“写”指令时将对应的修改标志置成“1”三．要求及方法：① 设计一个地址转换程序来模拟硬件的地址转换和缺页中断。

当访问的页在主存时则形成绝对地址，但不去模拟指令的执行，可以输出转换后的绝对地址来表示一条指令已执行完成。

当访问的页不在主存中时，则输出“*页号”来表示硬件产生了一次缺页中断。

模拟地址转换流程见图1。

② 编制一个FIFO 页面调度程序；FIFO 页面调度算法总是先调出作业中最先进入主存中的哪一页。

因此可以用一个数组来表示（或构成）页号队列。

数组中每个元素是该作业已在主存中的页面号，假定分配给作业的页架数为m ，且该作业开始的m 页已装入主存，则数组可由m 个元素构成。

P[0]，P[1]，P[2]，…，P[m-1]它们的初值为P[0]：=0，P[1]：=1，P[2]：=2，…，P[m-1]：=m-1用一指针K 指示当要调入新页时应调出的页在数组中的位置，K 的初值为“0”，当产生缺页中断后，操作系统总是选择P[K]所指出的页面调出，然后执行：P[K]：=要装入的新页页号 K ：=(k+1)mod m在实验中不必实际地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT 调出的页号”和“IN 要装入的新页页号”来模拟一次调出和装入过程，模拟程序的流程图见附图1。

按流程控制过程如下：提示：输入指令的页号和页内偏移和是否存指令⎩⎨⎧ 0 1非存指令存指令，若d 为-1则结束，否则进入流程控制过程，得P1和d，查表在主存时，绝对地址=P1×1024+d③假定主存中页架大小为1024个字节，现有一个共7页的作业，其副本已在磁盘上。

系统为该作业分配了4个页架，且该作业的第0页至第3页已装入内存，其余3页未装入主四．主要代码及其说明#include <stdio.h>#include <string.h>#include <stdlib.h>#define M 1024#define R 4typedef struct _PTable{int Number; //页号int Flag; //标志int Fnum; //页架号int Mflag; //修改标志int Position; //该页存放在磁盘上的位置}PTable;//初始化PTable ptable[]={{0, 1, 5, 0, 11},{1, 1, 8, 0, 12},{2, 1, 9, 0, 13},{3, 1, 1, 0, 21},{4, 0, -1, 0, 22},{5, 0, -1, 0, 23},{6, 0, -1, 0, 121},};void menu();int change(char op,int number,int add);void display();int p[]={0,1,2,3},k=0;void main(void){int number,add,n;char op;while(n){display();fflush( stdin );printf("输入:操作页号页内地址(存指令用\"c\"代表)\n");scanf("%c %d %d",&op,&number,&add);change(op,number,add);printf("\"是否继续! (按1 继续按任意键结束)\"\n");scanf("%d",&n);system( "cls ");if(n==1)continue;elsebreak;}}void menu(){printf("操作码\t页号\t页内地址页架标志修改标志出入状态绝对地址(L)\n");}int change(char op,int number,int add){bool flag1=false;bool flag2=false;int i,address,cout,temp;;for(i=0;i<7;i++){if(op=='c'){ptable[number].Mflag=1;}if(ptable[i].Number==number && ptable[i].Flag==1){address=ptable[i].Fnum*M+add;flag1=true;}if(ptable[i].Number==number && ptable[i].Flag==0){cout=i;temp = p[k]; //将要出的页if(ptable[temp].Mflag==1){flag2=true;}//修改页表ptable[number].Flag=1; //修改新页标志ptable[number].Fnum=ptable[temp].Fnum; //修改新页页架address=ptable[number].Fnum*M+add;ptable[temp].Flag=0; //修改旧页ptable[temp].Fnum=-1; //修改页架ptable[temp].Mflag=0; //修改修改标志p[k]=number; //新页k=(k+1)%R;}}menu();if(flag1)printf("%c\t %d\t %d\t %d\t %d\t %d\t 无出入\t%d\n",op,number,add,ptable[number].Fnum,ptable[number].Flag,ptable[number].Mflag,address);else if(flag2)printf("%c\t *%d\t %d\t %d\t %d\t%d OUT:%d,IN:%d %d\n",op,number,add,number,ptable[number].Fnum,ptable[number].Flag,ptable[number].Mflag,temp,number,address);elseprintf("%c\t *%d\t %d\t %d\t %d\t %d\t IN%d\t %d\n",op,number,add,ptable[number].Fnum,ptable[number].Flag,ptable[number].Mflag,number,address);return 0;}void display(){int i;printf("********当前页表中的状态*********\n");printf("页号标志页架修标志\n");for(i=0;i<7;i++){printf("%d\t%d\t%d\t%d\n",ptable[i].Number,ptable[i].Flag,ptable[i].Fnum,ptable[i]. Mflag);}printf("当前主存中的页号为: ");for(i=0;i<4;i++){printf("%d ",p[i]);}printf("\n*********************************\n");}五,实验截图。

实验四页式虚拟存储管理中地址转换和页式中断FIFO一、实验目的深入了解页式存储管理如何实现地址转换；进一步认识页式虚拟存储管理中如何处理缺页中断以及页面置换算法。

二、实验主要内容编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。

实验具体内容包括：首先对给定的地址进行转换工作，若发现缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所做工作进行测试。

假定主存64KB，每个主存块1024字节，作业最大支持到64KB，系统中每个作业分得主存块4块。

三、实验原理1）地址转换过程：首先从逻辑地址中的高位取得页号，然后根据页号查页表，得到块号；然后从逻辑地址中的低位取得页内地址，将块号和页内地址合并即得到物理地址。

2）缺页中断处理根据页号查找页表，判断该页是否在主存储器中，若该页标志位“0”，形成缺页中断。

操作系统让调出中断处理程序处理中断。

四、实验方法与步骤实现地址转换与缺页中断处理，主要考虑三个问题：第一，设计页式虚拟存储管理方式中页表的数据结构；第二，地址转换算法的实现；第三，缺页中断处理算法的实现。

1)设计页表的数据结构页式虚拟存储管理方式中页表除了页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。

在实验中页表用数组模拟，其数据结构定义如下：struct{int lnumber; //页号int flag; //表示页是否在主存中，“1”表示在，“0”表示不在int pnumber; // 该页所在主存块的块号int write; //该页是否被修改过，“1”表示修改过，“0“表示没有修改过int dnumber; //该页存放在磁盘上的位置，即磁盘块号}page[n]; //页表定义2）地址转换算法的实现地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程。

在实验中，每个主存块1024字节，则块内地址占10位；主存64KB，则主存共64块，即块号占6位；物理地址共占16位；作业最大64KB，则作业最大占64块，即页号占6位，逻辑地址共占16位。

目录1 需求分析 (2)1.1 目的和要求 (2)1.2 研究内容 (2)2 概要设计 (2)2．1 FIFO算法 (3)2．2 LRU算法 (3)2．3 OPT算法 (3)2．4 输入新的页面引用串 (3)3 详细设计 (4)3．1 FIFO（先进先出）页面置换算法： (4)3．2 LRU（最近最久未使用）置换算法： (4)3．3 OPT（最优页）置换算法 (4)4 测试 (5)5 运行结果 (5)6 课程设计总结 (9)7 参考文献 (10)8 附录：源程序清单 (10)1 需求分析1.1 目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

1.2 研究内容模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU （最近最久未使用）和OPT（最长时间不使用）），并通过比较性能得出结论。

前提：（1）页面分配采用固定分配局部置换。

（2）作业的页面走向和分得的物理块数预先指定。

可以从键盘输入也可以从文件读入。

（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。

2 概要设计本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、应用OPT算法和页面引用串的插入。

1.1各模块之间的结构图2．1 FIFO 算法该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO 算法处理之后的结果。

2．2 LRU 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU 算法处理之后的结果。

2．3 OPT 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT 算法处理之后的结果。

2．4 输入新的页面引用串该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0，用户可以自定义全新的20个数字页面引用串。

一、实验目的1. 理解操作系统存储管理的基本概念和原理。

2. 掌握分页式存储管理中地址转换和缺页中断的产生。

3. 学习并分析常见的页面调度算法，如先进先出（FIFO）算法、最近最少使用（LRU）算法等。

4. 比较不同页面调度算法的性能，提高对虚拟存储技术特点的理解。

二、实验环境1. 操作系统：Linux2. 编程语言：C语言3. 实验工具：gdb、gcc三、实验内容1. 模拟分页式存储管理中硬件的地址转换和产生缺页中断。

2. 使用先进先出（FIFO）页面调度算法处理缺页中断。

3. 使用最近最少使用（LRU）页面调度算法处理缺页中断。

4. 比较FIFO和LRU算法的性能。

四、实验步骤1. 定义虚拟页和实页的结构体，包括页号、物理页号、时间戳等。

2. 模拟地址转换过程，当访问的虚拟页不在内存时，产生缺页中断。

3. 使用FIFO算法处理缺页中断，将最早的页面替换出内存。

4. 使用LRU算法处理缺页中断，将最近最少使用的页面替换出内存。

5. 比较FIFO和LRU算法的性能，包括页面命中率、页面置换次数等。

五、实验结果与分析1. 实验结果（1）地址转换过程在模拟实验中，我们使用了一个简单的地址转换过程。

当访问一个虚拟页时，系统会检查该页是否在内存中。

如果在内存中，则直接返回对应的物理地址；如果不在内存中，则产生缺页中断。

（2）FIFO算法在FIFO算法中，当产生缺页中断时，系统会将最早进入内存的页面替换出内存。

实验结果显示，FIFO算法在页面访问序列较长时，页面命中率较低。

（3）LRU算法在LRU算法中，当产生缺页中断时，系统会将最近最少使用的页面替换出内存。

实验结果显示，LRU算法在页面访问序列较长时，页面命中率较高。

2. 实验分析（1）FIFO算法的缺点FIFO算法简单，但性能较差。

当页面访问序列较长时，FIFO算法可能会频繁地发生页面置换，导致页面命中率较低。

（2）LRU算法的优点LRU算法可以较好地适应页面访问模式，提高页面命中率。

在四页虚拟存储管理中使用先进先出版本的地址转换和页面中断进行实验四页虚拟存储管理中的地址转换和页中断先进先出实验首先，实验的目的是深入理解基于页面的存储管理如何实现地址转换。

进一步了解在页面虚拟存储管理中如何处理分页和页面替换算法。

其次，实验的主要内容是编写一个程序来完成地址转换过程，并模拟基于页面的虚拟存储管理中缺页中断的处理。

实验的具体内容包括:首先，给定的地址被转换。

如果发现缺页，首先中断该页，然后转换地址。

最后，编写主要函数来测试所做的工作。

假设主内存为64KB，每个主内存块为1024字节，支持的最大作业数为64KB，系统中的每个作业分为4个主内存块。

3.实验原则1)地址翻译过程:首先，从逻辑地址中的高位获得页号，然后根据页号搜索页表以获得块号。

然后，从逻辑地址的低位获得页内地址，并且通过组合块号和页内地址获得物理地址。

2)缺页中断处理根据页码查找页表，以确定该页是否在主存储器中。

如果页面标志位为“0”，则形成缺页中断。

操作系统让调用中断处理程序处理中断。

四、实现地址翻译和分页处理的实验方法和步骤，主要考虑三个问题:首先，设计了页面虚拟存储管理模式下页面表的数据结构。

二是地址转换算法的实现；第三，缺页中断处理算法的实现。

1)设计页表的数据结构。

在页型虚拟存储管理模式中，除了对应于该页的页号和主存储器块号之外，页表还应至少包括存在标志(该页是否在主存储器中)、磁盘位置(该页在磁盘上的副本的位置)和修改标志(该页是否已被修改)。

在实验中，页表由数组模拟，其数据结构定义如下:结构{ int lnumber//页码int标志；//表示页面是否在主存中，“1”表示“0”表示不在整数中；//页面所在的主内存块的块号为int write//页面是否已被修改，“1”表示已被修改，“0”表示未被修改为数字；//页面在磁盘上存储的位置，即磁盘块号}页面[n]；//页表定义2)地址转换算法由硬件实现。

在实验中，使用软件程序来模拟地址转换过程。

实验三
课程名称：操作系统
课程类型：必修
实验项目名称：存储器管理
实验题目：模拟分页式存储管理中硬件的地址转换和产生缺页中断。

一、实验目的
在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。

用这种办法扩充的主存储器称为虚拟存储器。

通过本实验帮助同学理解在分页式存储管理中怎样实现虚拟存储器。

二、实验要求
模拟分页式存储管理中硬件的地址转换。

需要为作业建立页表，应说明哪些页已在主存，哪些页尚未装入主存。

作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式“绝对地址=块号×块长+单元号”计算出欲访问的主存单元地址。

若产生缺页中断，引出操作系统来处理这个中断事件。

如果主存中已经没有空闲块，则可用FIFO 页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。

调出和装入后都要修改页表页表中对应页的标志。

三、设计思想
1、物理设计
全局变量定义如下：
struct info//页表
{
int block;//物理页架号
int disk;//在磁盘上的物理块号
int flag; //内外标志
}pagelist[10];
int po;//队列标记
int t[4];
2、程序流程图
（见下图）
图1-1主程序的流程图
图1-2 init( )的流程图。

操作系统实验报告四【实验题目】虚拟内存页面置换算法【实验目的】通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。

【实验内容】问题描述：设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。

假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, …,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。

程序要求如下：1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。

2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。

3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。

4）输出：每种算法的缺页次数和缺页率。

【实验要求】1) 上机前认真复习页面置换算法，熟悉FIFO，OPI，LRU三种页面分配和置换算法的过程；2) 上机时独立编程、调试程序；3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。

【源代码】//--------------- YeMianZhiHuan.cpp -----------------#include "iostream.h"const int DataMax=100;const int BlockNum = 10;int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示//int Data[DataMax]={4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1}; // 测试数据//int N = 20; // 输入页面个数int Data[DataMax]; // 保存数据int Block[BlockNum]; // 物理块int count[BlockNum]; // 计数器int N ; // 页面个数int M;//最小物理块数int ChangeTimes;void DataInput(); // 输入数据的函数void DataOutput();void FIFO(); // FIFO 函数void Optimal(); // Optimal函数void LRU(); // LRU函数///*int main(int argc, char* argv[]){DataInput();// DataInput();// FIFO();// Optimal();// LRU();// return 0;int menu;while(true){cout<<endl;cout<<"* 菜单选择*"<<endl;cout<<"*******************************************************"<<endl;cout<<"* 1-FIFO *"<<endl;cout<<"* 2-Optimal *"<<endl;cout<<"* 3-LRU *"<<endl;cout<<"* 0-EXIT *"<<endl;cout<<"*******************************************************"<<endl;cin>>menu;switch(menu){case 1: FIFO();break;case 2: Optimal();break;case 3: LRU();break;default: break;}if(menu!=1&&menu!=2&&menu!=3) break;}}//*/void DataInput(){cout<<"请输入最小物理块数：";cin>>M;while(M > BlockNum) // 大于数据个数{cout<<"物理块数超过预定值，请重新输入："; cin>>M;}cout<<"请输入页面的个数：";cin>>N;while(N > DataMax) // 大于数据个数{cout<<"页面个数超过预定值，请重新输入："; cin>>N;}cout<<"请输入页面访问序列："<<endl;for(int i=0;i<N;i++)cin>>Data[i];}void DataOutput(){int i,j;for(i=0;i<N;i++) // 对所有数据操作{cout<<Data[i]<<" ";}cout<<endl;for(j=0;j<M;j++){cout<<" ";for(i=0;i<N;i++) // 对所有数据操作{if( DataShowEnable[j][i] )cout<<DataShow[j][i]<<" ";elsecout<<" ";}cout<<endl;}cout<<"缺页次数: "<<ChangeTimes<<endl;cout<<"缺页率: "<<ChangeTimes*100/N<<"%"<<endl; }void FIFO(){int i,j;bool find;int point;int temp; // 临时变量ChangeTimes = 0;for(j=0;j<M;j++)for(i=0;i<N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据for(i=0;i<M;i++){count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段}for(i=0;i<N;i++) // 对有所数据操作{// 增加countfor(j=0;j<M;j++)count[j]++;find = false; // 表示块中有没有该数据for(j=0;j<M;j++){if( Block[j] == Data[i] ){find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据ChangeTimes++; // 缺页次数++if( (i+1) > M ) // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1 {//获得要替换的块指针temp = 0;for(j=0;j<M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0; // 更新计数值// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"FIFO => "<< endl;DataOutput();}void Optimal(){int i,j,k;bool find;int point;int temp; // 临时变量，比较离的最远的时候用ChangeTimes = 0;for(j=0;j<M;j++)for(i=0;i<N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据// for(i=0;i<M;i++)// {// count[i] = 0 ; //// }for(i=0;i<N;i++) // 对有所数据操作{find = false; // 表示块中有没有该数据for(j=0;j<M;j++){if( Block[j] == Data[i] )find = true;}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据，最优算法ChangeTimes++; // 缺页次数++for(j=0;j<M;j++){// 找到下一个值的位置find = false;for( k =i;k<N;k++){if( Block[j] == Data[k] ){find = true;count[j] = k;break;}}if( !find ) count[j] = N;}if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 {//获得要替换的块指针temp = 0;for(j=0;j<M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"Optimal => "<< endl;DataOutput();}void LRU(){int i,j;bool find;int point;int temp; // 临时变量ChangeTimes = 0;for(j=0;j<M;j++)for(i=0;i<N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据for(i=0;i<M;i++){count[i] = 0 ;}for(i=0;i<N;i++) // 对有所数据操作{// 增加countfor(j=0;j<M;j++)count[j]++;find = false; // 表示块中有没有该数据for(j=0;j<M;j++){if( Block[j] == Data[i] ){count[j] = 0;find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据ChangeTimes++; // 缺页次数++if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 {//获得要替换的块指针temp = 0;for(j=0;j<M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0;// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"LRU => "<< endl;DataOutput();}【效果截图】以作业为测试数据：。

操作系统实验二〔第一题〕一．实验内容模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二．实验目的在电脑系统总，为了提高主存利用率，往往把辅助存储器作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间综合可以超出主存的绝对地址空间。

用这种方法扩充的主存储区成为虚拟存储器。

三．实验题目模拟分页式存储管理中硬件的地址转换和产生缺页中断。

四．程序清单//// 操作实验二.cpp : 定义控制台应用程序的入口点。

//#include "stdafx.h"#include<iostream>#include<string>#include<fstream>using namespace std;class ins{private:string ope;long int page;long int unit;public:ins(){ }ins(string o,long int p,long int u):ope(o),page(p),unit(u){}void setope(string o){ ope=o;}void setpage(long int p){ page=p;}void setunit(long int u){ unit=u;}string getope(){return ope;}long int getpage(){return page;}long int getunit(){return unit;}};class work{private:long int Page;int sym;long int inum;long int onum;public:work(){}work(long int P, int s,long int i,long int o):Page(P),sym(s),inum(i),onum(o){} void setPage(long int P){ Page=P;}void setsym( int s){ sym=s;}void setinum(long int i){ inum=i;}void setonum(long int o){ onum=o;}long int getPage(){return Page;}int getsym(){return sym;}long int getinum(){return inum;}long int getonum(){return onum;}};void diaodu(work *w,ins * i,int numofins){ for(int j=0;j<numofins;j++){long int tempofk;long int a =i[j].getpage();for(int k=0;k<7;k++) //7是页表的页数if(w[k].getPage()!=a)continue;else{tempofk=k;break;}if(w[tempofk].getsym()==1)cout<<"绝对地址："<<w[tempofk].getinum()*128+i[j].getunit()<<" "<<"磁盘地址为："<<w[tempofk].getonum()<<" "<<"操作为："<<i[j].getope()<<endl;else cout<<"*"<<"发生缺页中断"<<endl;}}int main(){ins*INS=new ins[12];INS[0].setope ("+");INS[0].setpage(0);INS[0].setunit(70);INS[1].setope ("+");INS[1].setpage(1);INS[1].setunit(50);INS[2].setope ("×");INS[2].setpage(2);INS[2].setunit(15);INS[3].setope ("存"); INS[3].setpage(3);INS[3].setunit(21);INS[4].setope ("取"); INS[4].setpage(0);INS[4].setunit(56);INS[5].setope ("-");INS[5].setpage(6);INS[5].setunit(40);INS[6].setope ("移位"); INS[6].setpage(4);INS[6].setunit(53);INS[7].setope ("+");INS[7].setpage(5);INS[7].setunit(23);INS[8].setope ("存"); INS[8].setpage(1);INS[8].setunit(37);INS[9].setope ("取"); INS[9].setpage(2);INS[9].setunit(78);INS[10].setope ("+"); INS[10].setpage(4);INS[10].setunit(1);INS[11].setope ("存"); INS[11].setpage(6);INS[11].setunit(84);work*W =new work[7]; ifstream in("g://operate1.txt");long int p;int s;long int i;long int o;for(int jj=0;jj<7 ;jj++){in>>p;in>>s;in>>i;in>>o ;W[jj].setPage(p);W[jj].setsym(s);W[jj].setinum(i);W[jj].setonum(o);}diaodu(W,INS,12);}五．结果显示操作系统实验二〔第二题〕一．用先进先出〔FIFO〕九．程序清单/ 操作系统实验二.cpp : 定义控制台应用程序的入口点。

一、实验目的1. 理解虚拟存储管理的基本概念和原理。

2. 掌握分页式虚拟存储管理的地址转换和缺页中断处理过程。

3. 学习并分析几种常见的页面置换算法，如FIFO、LRU、OPT等。

4. 比较不同页面置换算法的性能，提高对虚拟存储管理的认识。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3. 虚拟存储器模拟工具：虚拟机（VirtualBox）三、实验内容1. 模拟分页式虚拟存储器（1）定义分页式虚拟存储器的参数，如页大小、内存大小、虚拟地址空间大小等。

（2）创建页表，记录每个页在内存中的位置和是否已加载。

（3）模拟进程的指令序列，生成虚拟地址。

（4）根据虚拟地址进行地址转换，得到物理地址。

（5）处理缺页中断，选择合适的页面置换算法。

2. 页面置换算法模拟（1）实现FIFO（先进先出）页面置换算法。

（2）实现LRU（最近最少使用）页面置换算法。

（3）实现OPT（最优页面置换）算法。

3. 比较不同页面置换算法的性能（1）设置不同的页面置换算法，模拟进程运行。

（2）记录每次缺页中断时的页面命中率。

（3）比较不同页面置换算法的页面命中率，分析其性能。

四、实验结果与分析1. 分页式虚拟存储器模拟（1）通过模拟，成功实现了分页式虚拟存储器的地址转换和缺页中断处理过程。

（2）实验结果表明，分页式虚拟存储器能够有效地提高内存利用率，减少内存碎片。

2. 页面置换算法模拟（1）实现了FIFO、LRU和OPT三种页面置换算法。

（2）通过模拟，比较了三种算法在不同进程下的页面命中率。

3. 页面置换算法性能比较（1）FIFO算法的页面命中率较低，适用于进程较稳定的情况。

（2）LRU算法的页面命中率较高，适用于进程频繁访问同一页面的情况。

（3）OPT算法的页面命中率最高，但实现复杂度较高，适用于进程访问序列可预测的情况。

五、实验结论1. 通过本次实验，加深了对虚拟存储管理的基本概念和原理的理解。

操作系统——模拟页⾯置换算法（FIFO——先⼊先出、LRU——最近最少使⽤、LFU——最近。

操作系统——模拟页⾯置换算法（FIFO——先⼊先出、LRU——最近最少使⽤、LFU——最近最不常使⽤），计算置换率（包含程序框图）导语：1. FIFO页⾯置换算法：最简单的页⾯置换算法。

这种算法的基本思想是：当需要淘汰⼀个页⾯时，总是选择驻留主存时间最长的页⾯进⾏淘汰，即先进⼊主存的页⾯先淘汰。

(看时间)2. LRU页⾯置换算法：最近最少使⽤，简单来说就是将数据块中，每次使⽤过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据置换掉。

(看时间)3. LFU页⾯置换算法：近期最少使⽤算法，选择近期最少访问的页⾯作为被替换的页⾯，如果⼀个数据在最近⼀段时间内使⽤次数很少，那么在将来⼀段时间内被使⽤的可能性也很⼩。

(看次数)4. 置换率与与缺页率不同。

置换率⽤置换次数算，缺页率⽤缺页中断次数算。

FIFO页⾯置换算法：Linux效果图（采⽤UOS + VScode + g++）程序框图C++代码(FIFO)：#include<iostream>using namespace std;static int mnum;//物理块数static int pnum;//页⾯⾛向static int count=0;//页⾯置换次数static int *analogblock;//模拟物理块static int *block;//物理块static int *process;//随机页⾯访问序列int judge(int a[],int n,int x) //判断数组中是否已有x，若有返回其下标值，没有则返回-1 {int i;for (i=0;i<n;i++)if(x==a[i])return i;return -1;}void replace(int y,int mnum,int x)//⽤于物理块页⾯置换，y是⽤来置换的页⾯，x是被置换的页⾯ {int i;for (i=0;i<mnum;i++)if(x==block[i])block[i]=y;}int main() {int i;int maxanalogblock=-1;//模仿队列的定义int x;cout<<"请输⼊页框⼤⼩物理块数：\n";cin>>mnum;if(mnum>999999) {cout<<"输⼊超出控制⼤⼩！"<<endl;return 0;}cout<<"⾃动⽣成的内存块需求序列个数：\n";cin>>pnum;if(pnum>999999) {cout<<"输⼊超出控制⼤⼩！"<<endl;return 0;}analogblock=new int[mnum];block=new int[mnum];process=new int[pnum];for (i=0;i<mnum;i++) analogblock[i]=-1;for (i=0;i<mnum;i++) block[i]=-1;///////////////////////随机产⽣页⾯⾛向序列cout<<"产⽣随机序列如下：\n";srand( (unsigned)time( NULL ) );//以time函数值（即当前时间）作为种⼦数，保证两次产⽣序列的随机性for (i=0; i<pnum; i++) {process[i] = rand()%10;cout<<process[i]<<" ";}cout<<endl;//////////////////////cout<<"先进先出(FIFO)页⾯置换算法，结果： \n\n";//////////////////////for (x=0;x<pnum;x++) //⾃动读数 {//读⼀个序列号，输出当前数组元素cout<<"真实物理块情况：";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况：";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}//////////////////////////maxanalogblock++;//读数后maxanalogblock⾃动+1if(maxanalogblock<mnum) //若在物理块范围内 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {analogblock[maxanalogblock]=process[x];//新元素从尾部插⼊block[maxanalogblock]=process[x];//新元素从尾部插⼊cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断调⼊页⾯"<<process[x]<<endl;} else //若数组中存在待插⼊元素 {maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock值cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在直接访问"<<endl;}} else //超过物理块数的元素 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {//队列法插⼊(尾部元素出，新元素从头部⼊)cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0]<<endl; replace(process[x],mnum,analogblock[0]);//置换物理块中页⾯for (i=0;i<mnum-1;i++)LRU 页⾯置换算法：Linux 效果图（采⽤UOS + VScode + g++）程序框图C++代码(LRU)： analogblock[i]=analogblock[i+1];analogblock[mnum-1]=process[x];//////////////////maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock 值count++;} else //若数组中存在待插⼊元素 {maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock 值cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在 直接访问"<<endl;}}}//读⼀个序列号，输出当前数组元素cout<<"真实物理块情况：";for (i=0;i<mnum;i++) {if(block[i]!=-1) cout<<block[i]<<" ";}cout<<"模拟物理块情况：";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}cout<<endl<<"页⾯换算次数为："<<count<<endl;cout<<"置换率为："<<(float)count/pnum<<endl;return 0;}//g++ test71.cpp -o test71 -lpthread&&./test71#include<iostream>using namespace std;static int mnum;//物理块数static int pnum;//页⾯⾛向static int count=0;//页⾯置换次数static int *analogblock;//模拟物理块static int *block;//物理块static int *process;//随机页⾯访问序列int judge(int a[],int n,int x) //判断数组中是否已有x ，若有返回其下标值，没有则返回-1 {int i;for (i=0;i<n;i++)if(x==a[i])return i;return -1;}void replace(int y,int mnum,int x)//⽤于物理块页⾯置换，y是⽤来置换的页⾯，x是被置换的页⾯ { int i;for (i=0;i<mnum;i++)if(x==block[i])block[i]=y;}void move(int a[],int n,int i) //移动下标为i的元素到尾部 {int j;int m=a[i];for (j=i;j<n-1;j++)a[j]=a[j+1];a[n-1]=m;}int main() {int i;int maxanalogblock=-1;//模仿栈的定义int x;cout<<"请输⼊页框⼤⼩物理块数：\n";cin>>mnum;if(mnum>999999) {cout<<"输⼊超出控制⼤⼩！"<<endl;return 0;}cout<<"⾃动⽣成的内存块需求序列个数：\n";cin>>pnum;if(pnum>999999) {cout<<"输⼊超出控制⼤⼩！"<<endl;return 0;}analogblock=new int[mnum];block=new int[mnum];process=new int[pnum];for (i=0;i<mnum;i++) analogblock[i]=-1;///////////////////////随机产⽣页⾯⾛向序列cout<<"产⽣随机序列如下：\n";srand( (unsigned)time( NULL ) );//以time函数值（即当前时间）作为种⼦数，保证两次产⽣序列的随机性for (i=0; i<pnum; i++) {process[i] = rand()%10;cout<<process[i]<<" ";}cout<<endl;//////////////////////cout<<"最近最少使⽤(LRU)页⾯置换算法，结果： \n\n";//////////////////////for (x=0;x<pnum;x++) //⾃动读数 {//读⼀个序列号，输出当前数组元素cout<<"真实物理块情况：";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况：";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}//////////////////////////maxanalogblock++;//读数后maxanalogblock⾃动+1LFU 页⾯置换算法：Linux 效果图（采⽤UOS + VScode + g++）程序框图 if(maxanalogblock<mnum) //若在物理块范围内 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {analogblock[maxanalogblock]=process[x];//新元素从尾部插⼊block[maxanalogblock]=process[x];//新元素从尾部插⼊cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断 调⼊页⾯"<<process[x]<<endl;} else //若数组中存在待插⼊元素 {move(analogblock,maxanalogblock,judge(analogblock,mnum,process[x]));//移动下标为i 的元素到尾部maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock 值cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在 直接访问"<<endl;}} else //超过物理块数的元素 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {//栈法插⼊(第⼀个元素出，后⾯元素前移，新元素从尾部⼊)cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断 页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0]<<endl; replace(process[x],mnum,analogblock[0]);//物理块中页⾯置换for (i=0;i<mnum-1;i++)analogblock[i]=analogblock[i+1];analogblock[mnum-1]=process[x];//////////////////maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock 值count++;} else //若数组中存在待插⼊元素 {move(analogblock,mnum,judge(analogblock,mnum,process[x]));//移动下标为i 的元素到尾部maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock 值cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在 直接访问"<<endl;}}}//读⼀个序列号，输出当前数组元素cout<<"真实物理块情况：";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况：";for (i=0;i<mnum;i++) {if(analogblock[i]!=-1)cout<<analogblock[i]<<" ";}cout<<endl<<"页⾯换算次数为："<<count<<endl;cout<<"置换率为："<<(float)count/pnum<<endl;return 0;}//g++ test72.cpp -o test72 -lpthread&&./test72C++代码(LFU)：#include<iostream>using namespace std;static int mnum;//物理块数static int pnum;//页⾯⾛向static int count=0;//页⾯置换次数static int **analogblock;//模拟物理块static int *block;//物理块static int *process;//随机页⾯访问序列int judge(int *a[],int n,int x) //判断数组中是否已有x，若有返回其下标值，没有则返回-1 {int i;for (i=0;i<n;i++)if(x==a[i][0])return i;return -1;}void replace(int y,int mnum,int x)//⽤于物理块页⾯置换，y是⽤来置换的页⾯，x是被置换的页⾯ { int i;for (i=0;i<mnum;i++)if(x==block[i])block[i]=y;}void move(int *a[],int n,int i) //移动下标为i的元素，⽐较访问次数次多少进⾏前进 {int j;int m=a[i][0];int m2=a[i][1];for (j=i;j<n-1;j++) {if(m2>=a[j+1][1]) {a[j][0]=a[j+1][0];a[j][1]=a[j+1][1];a[j+1][0]=m;a[j+1][1]=m2;}}}int main() {int i;int maxanalogblock=-1;//模仿栈的定义int x;//动态数组初始化cout<<"请输⼊页框⼤⼩物理块数：\n";cin>>mnum;if(mnum>999999) {cout<<"输⼊超出控制⼤⼩！"<<endl;return 0;}cout<<"⾃动⽣成的内存块需求序列个数：\n";cin>>pnum;if(pnum>999999) {cout<<"输⼊超出控制⼤⼩！"<<endl;return 0;}analogblock=(int**) (new int[mnum]);block=new int[mnum];process=new int[pnum];for (i=0;i<mnum;i++) analogblock[i]=(int*) new int[2];//⽤于保存页⾯号和访问次数for (i = 0; i < mnum; i++) {analogblock[i][0]=-1;analogblock[i][1]=0;}///////////////////////随机产⽣页⾯⾛向序列cout<<"产⽣随机序列如下：\n";srand( (unsigned)time( NULL ) );//以time函数值（即当前时间）作为种⼦数，保证两次产⽣序列的随机性for (i=0; i<pnum; i++) {process[i] = rand()%10;cout<<process[i]<<" ";}cout<<endl;//////////////////////cout<<"最近最不常使⽤(LFU)页⾯置换算法，结果： \n\n";//////////////////////for (x=0;x<pnum;x++) //⾃动读数 {//读⼀个序列号，输出当前数组元素cout<<"真实物理块情况：";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况：";for (i=0;i<mnum;i++) {if(analogblock[i][0]!=-1)cout<<analogblock[i][0]<<" ";//<<"访问次数"<<analogblock[i][1]<<" "}//////////////////////////maxanalogblock++;//读数后maxanalogblock⾃动+1if(maxanalogblock<mnum) //若在物理块范围内 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {analogblock[0][0]=process[x];//新元素从头部插⼊analogblock[0][1]=1;block[maxanalogblock]=process[x];//新元素从尾部插⼊move(analogblock,mnum,0);//移动下标为i的元素到相同访问次数页⾯的顶部cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断调⼊页⾯"<<process[x]<<endl;} else //若数组中存在待插⼊元素 {// move(analogblock,maxanalogblock,judge(analogblock,mnum,process[x]));//移动下标为i的元素到尾部analogblock[judge(analogblock,mnum,process[x])][1]++;move(analogblock,mnum,judge(analogblock,mnum,process[x]));//移动下标为i的元素到相同访问次数页⾯的顶部maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock值cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在直接访问"<<endl;}} else //超过物理块数的元素 {if(judge(analogblock,mnum,process[x])==-1)//若数组中不存在待插⼊元素 {//栈法插⼊(新元素从头部⼊，替换掉头部)cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 缺页中断页⾯"<<process[x]<<"置换出页⾯"<<analogblock[0][0]<<endl; replace(process[x],mnum,analogblock[0][0]);//物理块中页⾯置换analogblock[0][0]=process[x];analogblock[0][1]=1;move(analogblock,mnum,0);//移动下标为i的元素相同访问次数页⾯的顶部//////////////////maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock值count++;} else //若数组中存在待插⼊元素 {analogblock[judge(analogblock,mnum,process[x])][1]++;move(analogblock,mnum,judge(analogblock,mnum,process[x]));//移动下标为i的元素到相同访问次数页⾯的顶部maxanalogblock--;//因为没有插⼊新元素，回滚maxanalogblock值cout<<" 第"<<x+1<<"次访问，页⾯"<<process[x]<<" 已存在直接访问"<<endl; }}}//读⼀个序列号，输出当前数组元素cout<<"真实物理块情况：";for (i=0;i<mnum;i++) {if(block[i]!=-1)cout<<block[i]<<" ";}cout<<"模拟物理块情况：";for (i=0;i<mnum;i++) {if(analogblock[i][0]!=-1)cout<<analogblock[i][0]<<" ";}cout<<endl<<"页⾯换算次数为："<<count<<endl;cout<<"置换率为："<<(float)count/pnum<<endl;return 0;}//g++ test73.cpp -o test73 -lpthread&&./test73。

页式虚拟存储管理中地址转换和缺页中断一、实验目的模拟请求页式存储管理中硬件的地址转换和缺页中断，并用先进先出调度算法（FIFO）处理缺页中断。

二、实验内容1.内容：模拟请求页式存储管理中硬件的地址转换和缺页中断处理2.思想：装入新页置换旧页时，若旧页在执行中没有被修改过，则不必将该页重写磁盘。

因此，页表中增加是否修改过的标志，执行“存”指令和“写”指令时将对应的三、程序及截图程序主要代码:#include<iostream>#include<iomanip>#include<list>using namespace std;char useSign[12][5]={{'+'},{'-'},{'*'},{"存"},{"取"},{'-'},{"移位"},{'+'},{"存"},{"取"},{'+'},{"存"}};int PageAddress[12]={70,50,15,21,56,40,53,23,37,78,01,84};int PageNum[12]={0,1,2,3,0,6,4,5,1,2,4,6};int S_Station;int pPageNum[7];//页号pPageint pSign[7];int pStool[7];//页架号int pModify[7];//修改标志int pStation[7];//磁盘位置static int z=0;void Store(){for(int i=0;i<7;i++){if(i<4){pSign[i]=1;}elsepSign[i]=0;pPageNum[i]=i;pModify[i]=0;}int p1=1,p2=2,p3=3;for(i=0;i<7;i++){if(i<3){pStation[i]=p1;p1++;}elseif(i<6){pStation[i]=p2;p2++;}elsepStation[i]=p3;}pStool[0]=5;pStool[1]=8;pStool[2]=9;pStool[3]=1;}void CShow(){cout<<"操作";cout<<"页号";cout<<"页内地址";cout<<"标志";cout<<"绝对地址";cout<<"修改页号";cout<<"页架号";cout<<"绝对地址";cout<<endl;}void Find(){int m_Pagenum;int m_Station;int Y_Station;//绝对地址int m_Stool;cout<<"输入页号及页内地址查询操作：";cin>>m_Pagenum>>m_Station;CShow();int i,j=0;//string m_Modify;for(i=0;i<12;i++){if(PageAddress[i]==m_Station){break;}}Y_Station=pStool[m_Pagenum]*1024+m_Station;if(pSign[m_Pagenum]==1){if(strcpy(useSign[i],"存")!=0){pModify[m_Pagenum]=1;}}cout<<useSign[i]<<" ";cout<<m_Pagenum<<" ";cout<<m_Station<<" ";cout<<pSign[m_Pagenum]<<" ";if(Y_Station!=m_Station){cout<<Y_Station<<" ";cout<<" ";cout<<pStool[m_Pagenum]<<" ";cout<<Y_Station<<endl;}else{cout<<"*"<<m_Pagenum<<" ";for(j=z;j<7;j++){if(pSign[j]==1){z++;break;}}cout<<m_Pagenum<<"->"<<j<<" ";pStool[m_Pagenum]=pStool[j];pSign[j]=0;pStool[j]=0;cout<<pStool[m_Pagenum]<<" ";cout<<pStool[m_Pagenum]*1024+m_Station<<endl;}}int main(void){Store();char judge='Y';while(judge=='Y'){Find();cout<<"是否继续输入？Y = 是N=否"<<endl;cin>>judge;}return 0;}运行结果截图:五．心得体会在实验过程中，在调试的过程中遇到了一些问题，导致出现很多错误，在同学的帮助下，基本都解决了所有问题。

实验目地通过模拟实现请求页式存储管理地几种基本页面置换算法，了解虚拟存储技术地特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法地基本思想和实现过程，并比较它们地效率.文档收集自网络，仅用于个人学习实验内容设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率.1、最佳淘汰算法（OPT）2、先进先出地算法（FIFO ）3、最近最久未使用算法（LRU ）4、最不经常使用算法（LFU ）5、最近未使用算法（NUR ）命中率＝１－页面失效次数／页地址流长度实验准备本实验地程序设计基本上按照实验内容进行.即首先用srand（）和rand（）函数定义和产生指令序列，然后将指令序列变换成相应地页地址流，并针对不同地算法计算出相应地命中率.文档收集自网络，仅用于个人学习（1）通过随机数产生一个指令序列，共320 条指令.指令地地址按下述原则生成：A：50%地指令是顺序执行地B：25%地指令是均匀分布在前地址部分C：25%地指令是均匀分布在后地址部分具体地实施方法是：A：在[0，319]地指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1 地指令C：在前地址[0,m+1] 中随机选取一条指令并执行，该指令地地址为m'D：顺序执行一条指令，其地址为m'+1E：在后地址[m'+2，319]中随机选取一条指令并执行F：重复步骤A-E ，直到320 次指令（2）将指令序列变换为页地址流设：页面大小为1K ；用户内存容量 4 页到32 页；用户虚存容量为32K.在用户虚存中，按每K 存放10 条指令排列虚存地址，即320 条指令在虚存中地存放方式为：第0 条-第9 条指令为第0 页（对应虚存地址为[0，9]）第10 条-第19 条指令为第1页（对应虚存地址为[10，19]）第310 条-第319条指令为第31 页（对应虚存地址为[310，319]）按以上方式，用户指令可组成32 页.实验指导一、虚拟存储系统UNIX 中，为了提高内存利用率，提供了内外存进程对换机制；内存空间地分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页地存储管理方式.文档收集自网络，仅用于个人学习当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU 发出缺中断），由系统将其所需页面调入内存.这种页面调入方式叫请求调页.文档收集自网络，仅用于个人学习为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保 护位等 .二、页面置换算法当 CPU 接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处 理程序 .该程序通过查找页表，得到该页所在外存地物理块号 .如果此时内存未满，能容纳新 页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表 .如果内存已满，则须按某种置换 算法从内存中选出一页准备换出， 是否重新写盘由页表地修改位决定， 然后将缺页调入， 修 改页表 .利用修改后地页表，去形成所要访问数据地物理地址，再去访问内存数据 .整个页面地调入过程对用户是透明地 .文档收集自网络，仅用于个人学习 常用地页面置换算法有1、最佳置换算法( Optimal )2、先进先出法( Fisrt In First Out )3、最近最久未使用( Least Recently Used )4、最不经常使用法( Least Frequently Used )5、最近未使用法( No Used Recently )三、参考程序：view plaincopy to clipboardprint?50 ··60·· ··70·····80· ··90 ·100····110 ·· ·120·130 ···140 ····150 文档收集自网络，仅用于个人学习#define TRUE 1 #define FALSE 0 #define INV ALID -1#define NULL 0 #define total_instruction 320 #define total_vp 32 #define clear_period 50 typedef struct{int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp]; struct pfc_struct{int pn,pfn;struct pfc_struct *next; };typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail; int diseffect, a[total_instruction];int page[total_instruction], offset[total_instruction]; 文档收集自网络，仅用于个人学习int initialize(int);int FIFO(int); int LRU(int); int LFU(int);10· ····20·· ·30··· ·40/* 指令流长 */ /* 虚页长 */ /*清 0周期*/ /* 页面结构 *//* 页面结构数组 */ /* 页面控制结构 */文档收集自网络，仅用于个人学习int NUR(int);int OPT(int);int main( ){int s,i,j;srand(10*getpid()); /* 由于每次运行时进程号不同，故可用来作为初始化随机数队列地“种子” */ 文档收集自网络，仅用于个人学习s=(float)319*rand( )/32767/32767/2+1; // for(i=0;i<total_instruction;i+=4) /* 产生指令队列*/ { if(s<0||s>319){ printf("When i==%d,Error,s==%d\n",i,s); exit(0);}a[i]=s; /* 任选一指令访问点m*/a[i+1]=a[i]+1; /* 顺序执行一条指令*/ a[i+2]=(float)a[i]*rand( )/32767/32767/2; /* 执行前地址指令m' */ 文档收集自网络，仅用于个人学习a[i+3]=a[i+2]+1; /* 顺序执行一条指令*/s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; 文档收集自网络，仅用于个人学习if((a[i+2]>318)||(s>319)) printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s); 文档收集自网络，仅用于个人学习}for (i=0;i<total_instruction;i++) /* 将指令序列变换成页地址流*/{page[i]=a[i]/10; offset[i]=a[i]%10;for(i=4;i<=32;i++) /*用户内存工作区从 4 个页面到32 个页面*/{printf("---%2d page frames---\n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);} return 0;}int initialize(total_pf) int total_pf;人学习/* 初始化相关数据结构*/ 文档收集自网络，仅用于个人学习/* 用户进程地内存页面数*/ 文档收集自网络，仅用于个for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INV ALID){diseffect+=1; if(freepf_head==NULL){p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID;freepf_head=busypf_head; /* 释放忙页面队列地第一个页面 */ freepf_head->next=NULL; busypf_head=p;}p=freepf_head->next;/* 按 FIFO 方式调新页面入内存页面 */freepf_head->next=NULL; freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL){int i; diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INV ALID; pl[i].counter=0; pl[i].time=-1;}/* 置页面控制结构中地页号，页面为空 */ /* 页面控制结构中地访问次数为 0，时间为 -1*/for(i=0;i<total_pf-1;i++){pfc[i].next=&pfc[i+1]; pfc[i].pfn=i; } /* 建立 pfc[i-1] 和 pfc[i] 之间地链接 */pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; return 0;}int FIFO(total_pf) int total_pf;{int i,j; pfc_type *p; initialize(total_pf);/* 空页面队列地头指针为 pfc[0]*//* 先进先出算法 *//* 用户进程地内存页面数 *//* 初始化相关页面控制用数据结构 */busypf_head=busypf_tail=NULL; /* 忙页面队列头，队列尾链接 */ /* 页面失效 *//* 失效次数 */ /* 无空闲页面*/busypf_head=busypf_tail=freepf_head; else {busypf_tail->next=freepf_head; busypf_tail=freepf_head;}freepf_head=p;}elsepl[page[i]].time=present_time;收集自网络，仅用于个人学习}}printf("FIFO:%6.4f\n",1-(float)diseffect/320); return 0;}int LRU (total_pf) int total_pf;{int min,minj,i,j,present_time; initialize(total_pf); present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INV ALID){diseffect++;if(freepf_head==NULL){/*最近最久未使用算法*//* 页面失效 *//* 无空闲页面 */min=32767;for(j=0;j<total_vp;j++) if(min>pl[j].time&&pl[j].pfn!=INV {/* 找出 time 地最小值 */ALID) min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INV ALID; pl[minj].time=-1;freepf_head->next=NULL;//腾出一个单元}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time; freepf_head=freepf_head->next;//有空闲页面 ,改为有效//减少一个 free 页面/*free 页面减少一个 *///命中则增加该单元地访问次数文档present_time++;}printf("LRU:%6.4f\n",1-(float)diseffect/320); return 0;}int NUR(total_pf) int total_pf;{ int i,j,dp,cont_flag,old_dp; pfc_type *t;initialize(total_pf); dp=0;for(i=0;i<total_instruction;i++) { if (pl[page[i]].pfn==INV ALID) {diseffect++;if(freepf_head==NULL) { cont_flag=TRUE; old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INV cont_flag=FALSE; else{dp++;if(dp==total_vp)dp=0; if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn]; pl[dp].pfn=INV ALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next;}else pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;j<total_vp;j++) pl[j].counter=0;}printf("NUR:%6.4f\n",1-(float)diseffect/320); return 0;/* 最近未使用算法 *//* 页面失效 */ /* 无空闲页面 */ALID)}int OPT(total_pf) /* 最佳置换算法*/ int total_pf;{int i,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i++){ //printf("In OPT for//i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278; 学习if(pl[page[i]].pfn==INV ALID) /* 页面失效*/{diseffect++;if(freepf_head==NULL) /* 无空闲页面*/{for(j=0;j<total_vp;j++)if(pl[j].pfn!=INV ALID) dist[j]=32767; /* 最大"距离" */ 习else dist[j]=0;d=1;for(j=i+1;j<total_instruction;j++){if(pl[page[j]].pfn!=INV ALID)dist[page[j]]=d;d++;}max=-1;for(j=0;j<total_vp;j++)if(max<dist[j]){max=dist[j];maxpage=j;}freepf_head=&pfc[pl[maxpage].pfn];freepf_head->next=NULL;pl[maxpage].pfn=INV ALID;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}}printf("OPT:%6.4f\n",1-(float)diseffect/320);return 0;}int LFU(total_pf) /* 最不经常使用置换法*/1,i=%d\n",i);文档收集自网络，仅用于个人文档收集自网络，仅用于个人学int total_pf;{int i,j,min,minpage; pfc_type *t;initialize(total_pf); for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INV ALID)/* 页面失效 */{ diseffect++; if(freepf_head==NULL) /* 无空闲页面 */ { min=32767; for(j=0;j<total_vp;j++) {if(min>pl[j].counter&&pl[j].pfn!=INV ALID){min=pl[j].counter; minpage=j; }pl[j].counter=0;}freepf_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INV ALID; freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn; //有空闲页面 , 改为有效 pl[page[i]].counter++;freepf_head=freepf_head->next;// 减少一个 free 页面}else pl[page[i]].counter++;}printf("LFU:%6.4f\n",1-(float)diseffect/320); return 0;}#define TRUE 1#define FALSE 0 #define INV ALID -1#define NULL 0 #define total_instruction 320 #define total_vp 32 #define clear_period 50typedef struct { int pn,pfn,counter,time; }pl_type;pl_type pl[total_vp]; struct pfc_struct{/* 页面控制结构 */int pn,pfn;struct pfc_struct *next; };typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail; 文档收集自网络，仅用于个人学习int diseffect,a[total_instruction];int page[total_instruction], offset[total_instruction]; 文档收集自网络，仅用于个人学习int initialize(int); int FIFO(int); int LRU(int);/* 指令流长 */ /* 虚页长 */ /*清0周期*/ /* 页面结构 *//* 页面结构数组 */int LFU(int);int NUR(int);int OPT(int);int main( ){int s,i,j;srand(10*getpid()); /* 由于每次运行时进程号不同，故可用来作为初始化随机数队列地“种子” */ 文档收集自网络，仅用于个人学习s=(float)319*rand( )/32767/32767/2+1; // for(i=0;i<total_instruction;i+=4) /* 产生指令队列*/ {if(s<0||s>319){ printf("When i==%d,Error,s==%d\n",i,s); exit(0);}a[i]=s; /* 任选一指令访问点m*/a[i+1]=a[i]+1; /* 顺序执行一条指令*/ a[i+2]=(float)a[i]*rand( )/32767/32767/2; /* 执行前地址指令m' */ 文档收集自网络，仅用于个人学习a[i+3]=a[i+2]+1; /* 顺序执行一条指令*/s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; 文档收集自网络，仅用于个人学习if((a[i+2]>318)||(s>319))printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s); 文档收集自网络，仅用于个人学习}for (i=0;i<total_instruction;i++) /* 将指令序列变换成页地址流*/ {page[i]=a[i]/10; offset[i]=a[i]%10;for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/ { printf("---%2d page frames---\n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);}return 0;int initialize(total_pf) int total_pf; /*初始化相关数据结构*/ 文档收集自网络，仅用于个人学习/*用户进程地内存页面数*/ 文档收集自网络，仅用于个人学}习{int i;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INV ALID; /* 置页面控制结构中地页号，页面为空*/ pl[i].counter=0;pl[i].time=-1; /* 页面控制结构中地访问次数为0，时间为-1*/ }for(i=0;i<total_pf-1;i++){pfc[i].next=&pfc[i+1];pfc[i].pfn=i;} /* 建立pfc[i-1] 和pfc[i] 之间地链接*/pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0]; return 0;}int FIFO(total_pf)int total_pf;{int i,j;pfc_type *p;initialize(total_pf); /* 空页面队列地头指针为pfc[0]*//* 先进先出算法*//* 用户进程地内存页面数*//* 初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NULL; /* 忙页面队列头，队列尾链接*/ for(i=0;i<total_instruction;i++){/* 页面失效*/if(pl[page[i]].pfn==INV ALID){diseffect+=1; /* 失效次数*/if(freepf_head==NULL) /* 无空闲页面*/{p=busypf_head->next;pl[busypf_head->pn].pfn=INV ALID;freepf_head=busypf_head; /* 释放忙页面队列地第一个页面*/freepf_head->next=NULL;busypf_head=p;}p=freepf_head->next; /* 按FIFO 方式调新页面入内存页面*/freepf_head->next=NULL;freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NULL)busypf_head=busypf_tail=freepf_head;else{ busypf_tail->next=freepf_head; /*free 页面减少一个*/ busypf_tail=freepf_head;} freepf_head=p;}} printf("FIFO:%6.4f\n",1-(float)diseffect/320);return 0;}int LRU (total_pf) /*最近最久未使用算法*/int total_pf;{int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INV ALID) {diseffect++;min=32767;/* 页面失效*/if(freepf_head==NULL){/* 无空闲页面*/for(j=0;j<total_vp;j++) /* 找出time 地最小值*/ if(min>pl[j].time&&pl[j].pfn!=INV ALID){min=pl[j].time;minj=j;} freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元pl[minj].pfn=INV ALID;pl[minj].time=-1;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next; }else //有空闲页面,改为有效//减少一个free 页面pl[page[i]].time=present_time; 自网络，仅用于个人学习//命中则增加该单元地访问次数文档收集present_time++;}printf("LRU:%6.4f\n",1-(float)diseffect/320);return 0;}int NUR(total_pf)int total_pf;{ int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i++){ if (pl[page[i]].pfn==INV ALID) {diseffect++;if(freepf_head==NULL){ cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INV cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0; /* 最近未使用算法*//* 页面失效*//* 无空闲页面*/ ALID)if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INV ALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;j<total_vp;j++)pl[j].counter=0;}printf("NUR:%6.4f\n",1-(float)diseffect/320);return 0;}int OPT(total_pf) /* 最佳置换算法*/int total_pf;{int i,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i++){ //printf("In OPT for 1,i=%d\n",i);//i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278; 文档收集自网络，仅用于个人学习if(pl[page[i]].pfn==INV ALID) /* 页面失效*/{diseffect++;if(freepf_head==NULL) /* 无空闲页面*/{for(j=0;j<total_vp;j++)if(pl[j].pfn!=INV ALID) dist[j]=32767; /* 最大"距离" */ 文档收集自网络，仅用于个人学习elsedist[j]=0;d=1;for(j=i+1;j<total_instruction;j++){if(pl[page[j]].pfn!=INV ALID)dist[page[j]]=d;d++;}max=-1;for(j=0;j<total_vp;j++)if(max<dist[j]){max=dist[j];maxpage=j;}freepf_head=&pfc[pl[maxpage].pfn];freepf_head->next=NULL; pl[maxpage].pfn=INVALID;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}}printf("OPT:%6.4f\n",1-(float)diseffect/320);return 0;}int LFU(total_pf) /* 最不经常使用置换法 */int total_pf;{int i,j,min,minpage;pfc_type *t;initialize(total_pf); for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INV ALID) /* 页面失效 */{ diseffect++;if(freepf_head==NULL) /* 无空闲页面 */{ min=32767; for(j=0;j<total_vp;j++){if(min>pl[j].counter&&pl[j].pfn!=INVALID){min=pl[j].counter;minpage=j;}pl[j].counter=0;}freepf_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INV ALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].counter++; freepf_head=freepf_head->next;}else pl[page[i]].counter++;} printf("LFU:%6.4f\n",1-(float)diseffect/320);return 0;}五、分析1、从几种算法地命中率看， OPT 最高，其次为 NUR 相对较高，而 FIFO 与LRU 相差无几， 最低地是 LFU. 但每个页面执行结果会有所不同 .文档收集自网络，仅用于个人学习//有空闲页面 , 改为有效// 减少一个 free 页面2、OPT 算法在执行过程中可能会发生错误五、思考1、为什么OPT 在执行时会有错误产生？本文来自CSDN 博客，转载请标明出处：/followingturing/archive/2010/12/22/6091196.aspx 文档收集自网络，仅用于个人学习版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理。

虚拟存储器实验报告一、实验目的本次虚拟存储器实验的目的在于深入理解虚拟存储器的工作原理，掌握其基本概念和关键技术，通过实际操作和观察，分析虚拟存储器对系统性能的影响，并能够运用所学知识解决在实验过程中遇到的问题。

二、实验环境本次实验使用的操作系统为 Windows 10，开发工具为 Visual Studio 2019，编程语言为 C+＋。

实验所使用的计算机配置为：Intel Core i7 处理器，16GB 内存，512GB 固态硬盘。

三、实验原理虚拟存储器是一种利用硬盘等辅助存储器来扩充主存容量的技术。

它将程序的逻辑地址空间与物理地址空间分开，使得程序可以使用比实际物理内存更大的地址空间。

当程序访问的地址不在物理内存中时，系统会通过页面置换算法将暂时不用的页面换出到硬盘，将需要的页面换入到物理内存中。

虚拟存储器的实现主要依赖于页式存储管理和地址转换机制。

页式存储管理将逻辑地址空间划分为固定大小的页面，物理地址空间也划分为相同大小的页框。

地址转换通过页表来完成，页表记录了逻辑页面与物理页框的对应关系。

四、实验内容1、页面置换算法的实现首先实现了先进先出（FIFO）页面置换算法。

创建一个固定大小的物理内存页框数组，模拟物理内存。

当需要装入新页面时，如果物理内存已满，按照先进入的页面先被置换的原则选择置换页面。

接着实现了最近最少使用（LRU）页面置换算法。

为每个页面设置一个访问时间戳，当需要置换页面时，选择访问时间最久远的页面进行置换。

2、虚拟地址到物理地址的转换设计了一个简单的页表结构，包括逻辑页号、物理页框号和有效位等字段。

输入一个虚拟地址，通过查找页表将其转换为物理地址。

如果页面不在物理内存中，触发页面置换算法进行页面调入。

3、性能分析对不同大小的程序和不同的页面置换算法，测量其页面缺失率和执行时间。

分析页面大小、物理内存大小等因素对虚拟存储器性能的影响。

五、实验步骤1、初始化实验环境设定物理内存大小、页面大小等参数。

页面置换算法实践报告页面置换算法（Page Replacement Algorithm）是操作系统中用于管理虚拟内存的重要算法之一。

其目的是在有限的物理内存空间中，将进程所需的页面加载到内存中，并根据一定的策略替换掉不再被使用的页面，以提高内存利用率和系统性能。

在本次实践报告中，我将重点介绍三种常见的页面置换算法：先进先出（FIFO）、最近最久未使用（LRU）和最不经常使用（LFU）。

先进先出（FIFO）算法是最简单的页面置换算法之一。

它根据页面进入内存的先后顺序进行页面置换。

当一个页面需要被替换时，选择最早进入内存的页面进行替换。

虽然FIFO算法的实现简单，但它无法很好地反映页面的使用频率和重要性，容易发生“缺页率抖动”的问题。

缺页率抖动指的是在某些场景下，缺页率会频繁地快速上升，然后又快速下降。

最近最久未使用（LRU）算法是一种基于页面历史访问记录的页面置换算法。

它认为最近被访问过的页面是最有可能在未来被访问的，因此选择最近最久未使用的页面进行替换。

LRU算法可以较为准确地反映页面的使用频率，避免了FIFO算法的缺点。

但由于需要记录页面的访问历史，因此实现相对复杂，需要额外的开销。

最不经常使用（LFU）算法是一种基于页面使用频率的页面置换算法。

它认为使用频率最低的页面是最不重要的，因此选择最不经常使用的页面进行替换。

LFU算法可以较好地反映页面的使用频率，对于一些热点页面和冷门页面的处理较为准确。

但由于需要记录页面的使用次数，因此实现相对复杂，需要额外的开销。

根据实际情况选择合适的页面置换算法对于系统的性能影响非常重要。

一般来说，FIFO算法比较适用于缺页率较低的情况，而LRU算法则适用于需要较高精确度的场景，而LFU算法则适用于需要特别关注页面使用频率的场景。

在实践中，我们可以使用模拟算法来进行页面置换算法的实验。

通过构造不同的页面访问序列，我们可以测试不同算法的效果并进行比较。

在实验过程中，我们可以观察不同算法的缺页率、替换次数、访问延迟等指标，以评估算法的性能。

操作系统实验二：虚构储存器管理时间： 2013-12-06地址：计算机实验机房2实验人：朱蓉蓉学号： E01114336题目一：采纳先进先出算法实现分页管理的缺页调动。

实验代码：#include "stdio.h"#define N 20#define m 4void main(){int n;printf(" 请输入引用串页面个数 :\n");scanf("%d",&n);int ym[N],i,j,q,mem[m]={0},table[m][N];char flag,f[N];printf(" 请输入页面接见序列 :\n");for(i=0;i<n;i++){printf(" 输入页面号 :");scanf("%d",&ym[i]);}for(i=0;i<n;i++)//查页表，看能否缺页{q=0;while((ym[i]!=mem[q])&&(q!=m)) q++;if(q==m)flag='*';//缺页，则置标记flag为'*'else flag=' ';if(flag=='*'){for(j=m-1;j>0;j--)//裁减最初调入的页面调入目前访问的mem[j]=mem[j-1];mem[0]=ym[i];}for(j=0;j<m;j++)table[j][i]=mem[j];f[i]=flag;}printf(" 输出结果为下表 (0 代表为空， * 代表出缺页 )\n"); for(i=0;i<m;i++){for(j=0;j<n;j++)printf("%3d",table[i][j]);printf("\n");}for(i=0;i<n;i++)printf("%3c",f[i]);printf("\n");}实验二：采纳 LRU算法实现分页管理的缺页调动.实验代码：#include <stdio.h>#define P 20#define m 5void main(){int n;printf("--------------LRU算法缺页调动---------------\n"); printf(" 请输入引用串页面个数 :\n");scanf("%d",&n);int ym[P],i,j,q,mem[m]={0},table[m][P];char flag,f[P];printf(" 请输入页面接见序列 :\n");for(i=0;i<n;i++){:");printf(" 输入页面号scanf("%d",&ym[i]); }//查页表，看能否缺页for(i=0;i<n;i++){q=0;while((ym[i]!=mem[q])&&(q!=m)) q++;if(q==m)flag='*';//缺页，则置标记flag为'*'else flag=' ';for(j=q;j>0;j--)mem[j]=mem[j-1];mem[0]=ym[i];for(j=0;j<m;j++)table[j][i]=mem[j];f[i]=flag;}printf(" 输出结果为下表（ 0 代表为空， * 代表出缺页） \n"); for(i=0;i<m;i++){for(j=0;j<n;j++)printf("%3d",table[i][j]);printf("\n");}for(i=0;i<n;i++)printf("%3c",f[i]);printf("\n");}。

实验4 页式存储管理的页面置换算法模拟1.实验目的通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

2.实验环境装有操作系统Windows XP和开发工具VC++，内存在256M以上的微机；或者：装有Linux(Fedora 7)操作系统和gcc编译器，内存在256M以上的微机。

3.实验内容（1）通过随机数产生一个指令序列，共320条指令。

指令的地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分；具体的实施方法是：①在[0，319]的指令地址之间随机选取一起点m；②顺序执行一条指令，即执行地址为m+1的指令；③在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；④顺序执行一条指令，其地址为m’+1的指令；⑤在后地址[m’+2，319]中随机选取一条指令并执行；⑥重复上述步骤①～⑤，直到执行320次指令。

（2）将指令序列变换为页地址流①设页面大小为1K；②分配内存容量为4K到32K；③用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条～第9条指令为第0页（对应虚存地址为[0，9]）；第10条～第19条指令为第1页（对应虚存地址为[10，19]）；…………第310条～第319条指令为第31页（对应虚存地址为[310，319]）。

按以上方式，用户指令可组成32页。

（3）计算先进先出（FIFO）算法或最近最少使用（LRU）算法在不同内存容量下的命中率。

其中，命中率=1-页面失效次数/页地址流长度4.实验要求(1)将FIFO或者LRU算法的源程序及程序执行结果写入实验报告；(2)将FIFO和LRU算法的工作机理写入实验报告。