南昌大学实验报告
---（5）存储管理的模拟实现
学生姓名：张皓然学号：5501215001专业班级：本硕151 实验类型：□ 验证 □ 综合 ■ 设计□ 创新 实验日期：实验成绩：
一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
二、实验内容
1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； #具体的实施方法是：
A. B. C. D. E. F.
在[0，319]的指令地址之间随机选区一起点M; 顺序执行一条指令，即执行地址为M+1的指令；
在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’; 顺序执行一条指令，其地址为M’+1；
在后地址[M’+2，319]中随机选取一条指令并执行； 重复A—E，直到执行320次指令。
2．指令序列变换成页地址流 设：（1）页面大小为1K；
（2） 用户内存容量为4页到32页； （3） 用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条—第9条指令为第0页（对应虚存地址为[0，9]）； 第10条—第19条指令为第1页（对应虚存地址为[10，19]）； 。。。。。。。。。。。。。。。。。。。。。
第310条—第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。
3. 计算并输出下述各种算法在不同内存容量下的命中率。
A. FIFO先进先出的算法 B. LRU最近最少使用算法 C．LFU最少访问页面算法
三、实验要求
1、需写出设计说明； 2、设计实现代码及说明 3、运行结果；
四、主要实验步骤
代码如下：
#include
#include
#define TRUE 1 #define FALSE 0 #define INVALID -1
#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; //缺页计数器 int a[total_instruction]; //指令流数组
int page[total_instruction]; //指令对应的页面号 int offset[total_instruction]; //指令所在页面的偏移量 //初始化页面结构数组和页面控制结构数组 int initialize(int); int FIFO(int); //先进先出 int LRU(int); //最近最久未使用 int OPT(int); //最佳置换算法 int CLOCK(int); //clock置换算法
int main( ) {
int s; int i;
srand(10*getpid());
s = (int)((float)(total_instruction-1)*(rand()/(RAND_MAX+1.0))); printf(\随机产生指令流------------\\n\ for (i=0; i a[i]=s; //任选一指令访问点m a[i+1]=a[i]+1; //顺序执行一条指令 a[i+2]=(int)((float)a[i]*(rand()/(RAND_MAX+1.0))); //执行前地址指令m' a[i+3]=a[i+2]+1; //顺序执行一条指令 printf(\ s = (int)((float)((total_instruction-1)-a[i+2])*(rand()/(RAND_MAX+1.0))) a[i+2]; } printf(\ for (i=0;i page[i]=a[i]/10; offset[i]=a[i]; } printf(\不同页面工作区各种替换策略的命中率表--\\n\ printf(\ for(i=4;i<=32;i++) //用户内存工作区从个页面到个页面 { printf(\ FIFO(i); LRU(i); OPT(i); CLOCK(i); printf(\ } return 0; + } //初始化页面结构数组和页面控制结构数组 //total_pf; 用户进程的内存页面数 int initialize(int total_pf) { int i; diseffect=0; for(i=0;i //主存区页面控制结构的空闲页面头指针指向pfc[0] return 0; } //最久最近未使用算法形参为用户进程的内存页面数目 int LRU (int total_pf) { int MinT; //最小的访问时间 int MinPn; //拥有最小访问时间的页的页号 int i,j; int CurrentTime; initialize(total_pf); //初始化 CurrentTime=0; diseffect=0; for(i=0;i diseffect++; //缺页次数+1 if(freepf_head==NULL) //无空闲的页面 { MinT=100000; for(j=0;j MinT=pl[j].time; MinPn=j; } } //释放最久未访问的页面 freepf_head=&pfc[pl[MinPn].pfn]; //最久未访问页面被换出主存 pl[MinPn].pfn=INVALID; //最久未访问页面的访问时间设置为无效 pl[MinPn].time=-1; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].time=CurrentTime; freepf_head=freepf_head->next; } else pl[page[i]].time=CurrentTime; CurrentTime++; } printf(\ return 0; } //最佳置换算法 int OPT(int total_pf) { int i,j; int MaxD; //将来最近一次访问距离的最大值 int MaxPn; //对应的页号 int dis; //距离计数器 int dist[total_vp]; initialize(total_pf); diseffect=0; for(i=0;i