本文共 4552 字，大约阅读时间需要 15 分钟。
实验：虚拟存储
一、实验目的
1 、加深对虚拟存储器的理解。
2 、熟练掌握常用页面置换算法的实现原理。
二、实验设备
微型计算机
三、实验说明
1、在FIFO置换算法的基础上，编写实现LRU页面置换算法；
按如下的访问序列：12560365365604270435，
2、在物理块数分别为3和4时，分别调用FIFO和LRU算法，计算并输出相应的命中率。
1、 数据结构
（1） 页面结构
typedef struct{ int pn, pfn, counter, time; } pl_type ;
pl_type pl[total_vp];
其中pn为页面号（页号），pfn为页帧号（物理块号），counter为一个周期内访问该页面的次数，time为访问时间；pl[total_vp]为页面结构数组，由于共有320条指令，每页可装入10条指令，因此虚页长total_vp的值为32。
（2）页帧控制结构
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;
其中pfc[total_vp]定义用户进程的页帧控制结构数组，在该实验中，用户内存工作区是动态变化的，最多可达到用户进程的虚页数目，即32个物理块。
*freepf_head为空闲页帧头的指针
*busypf_head为忙页帧头的指针
*busypf_tail忙页帧尾的指针
2、 变量定义
(1) int a[total_instruction]: 指令流数组
(2) int diseffect: 页面失效次数
(3) int page[total_instruction]: 每条指令所属页面号
(4) int offset[total_instruction]: 每页装入10条指令后取模运算得出的页内偏移地址
(5) int total_pf: 用户进程的内存页帧数
3、 主要函数
(1) void initialize(int): 初始化函数
该函数主要对页面结构数组pl和页帧结构数组pfc进行初始化，如置页面结构中的页面号pn，初始化页帧号pfn为空，访问次数counter为0，访问时间time为-1；同样对页帧数组进行初始化，形成一个空闲页帧队列。
(2) void FIFO(int): 计算使用先进先出页面置换算法时的命中率
(3) void LRU(int): 计算使用最近最久未使用页面置换算法时的命中率
#include #include #include typedef struct{ int pn, pfn, counter, time;} pl_type ;struct pfc_struct{ int pn, pfn; struct pfc_struct *next;};typedef struct pfc_struct pfc_type;#define INVALID -1//total_vp页面个数//pfc[total_vp]定义用户进程的页帧控制结构数组static int a[320]; //指令流数组int diseffect=0; //页面失效次数int page[320]={ 1,2,5,6,0,3,6,5,3,6,5,6,0,4,2,7,0,4,3,5}; // 每条指令所属页面号int offset[320]={ -1}; //每页装入10条指令后取模运算得出的页内偏移地址int total_pf=0; //用户进程的内存页帧数=块数int total_vp=32;int total_instruction;pl_type pl[32];pfc_type *freepf_head, *busypf_head, *busypf_tail;//pfc[total_vp],int initialize(int total_pf){ int i; pfc_type *pf; for(i=0;i pfn=0; freepf_head->next=NULL; pf=freepf_head; for(i=1;i next=(pfc_type *) malloc(sizeof(pfc_type)); pf=pf->next; pf->pfn=i; pf->next=NULL; } } busypf_head=busypf_tail=NULL; return 0;}void LRU(int total_pf){ int i,farthest,j; pfc_type *p,*q,*a; initialize(total_pf); for(i=0;i pn; while(p!=NULL) { if(pl[p->pn].time pn; p=p->next; } p=busypf_head; q=p; while(p->pn!=farthest&&p!=NULL) { q=p; p=p->next; } if(p==busypf_head) { busypf_head=busypf_head->next; pl[p->pn].pfn=INVALID; //将忙页帧队首原来页面作为换出页面 freepf_head=p; freepf_head->next=NULL; } else if(p!=busypf_tail) { q->next=p->next; pl[p->pn].pfn=INVALID; //将忙页帧上次被调用时间最早的页面作为换出页面 freepf_head=p; freepf_head->next=NULL; } else { busypf_tail=q; pl[p->pn].pfn=INVALID; //将忙页帧队尾的页面作为换出页面 freepf_head=p; freepf_head->next=NULL; } } p=freepf_head->next; //有空闲页帧 freepf_head->next=NULL; //将这个将被征用的空闲页帧和后面的断开 freepf_head->pn=page[i]; /* 将所需页面调入空闲页帧 */ pl[page[i]].pfn=freepf_head->pfn;//标注页表中此页对应的块号 pl[page[i]].time=time(NULL)+i; if(busypf_head==NULL) /* 若忙页帧队列为空，则将其头尾指针都指向刚调入页面所在的页帧 */ { busypf_head=busypf_tail=freepf_head; busypf_tail->next=NULL; } else { //否则，将刚调入页面所在的页帧挂在忙页帧队列尾部 busypf_tail->next=freepf_head; busypf_tail=busypf_tail->next; busypf_tail->next=NULL; } freepf_head=p; //空闲页帧头指针后移 } else { pl[page[i]].time=time(NULL)+i; } } printf("未命中数：%d\n\n",diseffect); printf("LRU命中率:%6.4f \n",1-(float)diseffect/20);}void FIFO(int total_pf) /*先进先出页面置换算法*/{ int i; pfc_type *p; initialize(total_pf); busypf_head=busypf_tail=NULL; for(i=0;i next; pl[busypf_head->pn].pfn=INVALID; //将忙页帧队首原来页面作为换出页面 freepf_head=busypf_head; freepf_head->next=NULL; busypf_head=p; //忙页帧头指针后移 } p=freepf_head->next; //有空闲页帧 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; busypf_tail=freepf_head; } freepf_head=p; //空闲页帧头指针后移 } } printf("未命中数：%d\n",diseffect); printf("FIFO命中率:%6.4f \n",1-(float)diseffect/20);}int main(){ int i,ch; printf("请输入指令个数：\n"); scanf("%d",&total_instruction); printf("指令序列所在页面号如下\n"); for(i=0;i %d",page[i]); printf("\n请输入内存块数：\n"); scanf("%d",&total_pf); printf("************Page replacement algorithm************\n\n"); printf("\t\t\t1.FIFO\n\n"); printf("\t\t\t2.LRU\n\n"); printf("choose the algorithm:\n"); scanf("%10d",&ch); switch(ch) { case 1: FIFO(total_pf); break; case 2: LRU(total_pf); break; default:printf("enter error data!\n"); }}
对于FIFO页面置换算法，每次置换时只需换出忙队列对手的页面，新加入的页面放到队尾；对于LRU页面置换算法，每次都要找到忙队列中上次调用距今最久的页面，因此要被换出的页面在队头、队尾和队中的操作不同。
转载地址：http://nnxzi.baihongyu.com/