操作系统 LRU页面置换算法

写这个算法，就是一步一步调试出来的，花点功夫，其实原理比较简单，我使用的是链表。
中间有一些循环控制变量和条件需要琢磨以下，其他还好。

#define vpNum 10	//虚页块数
#define rpNum 3		//实页块数
ElemType arr[N] = { 7,0,1,2,0,3,4,2,3,0,3,2,1,2,0,1,7,0,1 };//页面引用串

完成这个分了三种情况：

第一种情况，虚页号和页面号引用串值相等且此时不在内存中
第二种情况，如果实页满了，进行页面置换
第三种情况，此时刻的页面号在内存中

完整代码：

#include 
#include 
typedef int ElemType;
#define vpNum 10	//虚页块数
#define rpNum 3		//实页块数
#define N 20		//页面引用串数目
#define MAX 100		//用于找最小访问时间的对比量，初值设置大一点
ElemType arr[N] = { 7,0,1,2,0,3,4,2,3,0,3,2,1,2,0,1,7,0,1 };//页面引用串
int count = 0;		//记录一共多少次缺页
int sum = 1;		//记录时刻
// 虚页数据结构
typedef struct VirtualPage {ElemType virtualPage;	//虚页号ElemType realPage;		//实页号ElemType state;			//状态ElemType enterTime;		//进入时间ElemType accessTime;	//访问时间struct VirtualPage* next;int len;
}VirtualPage, * VP;
// 实页数据结构
typedef struct RealPage {ElemType realPage;		//实页号ElemType virtualPage;	//虚页号ElemType state;			//状态struct RealPage* next;int len;
}RealPage, * RP;
//初始化虚页数据结构，尾插法
void init_VP(VP& vp) {vp = (VP)malloc(sizeof(VirtualPage));VP q, r = vp;vp->len = vpNum;for (int i = 0; i < vp->len; i++) {q = (VP)malloc(sizeof(VirtualPage));q->virtualPage = i;q->realPage = -1;q->state = 0;q->enterTime = 0;q->accessTime = 0;r->next = q;r = q;}r->next = NULL;
}
//初始化虚页数据结构，尾插法
void init_RP(RP& rp) {rp = (RP)malloc(sizeof(RealPage));RP q, r = rp;rp->len = rpNum;for (int i = 0; i < rp->len; i++) {q = (RP)malloc(sizeof(RealPage));q->realPage = i;q->virtualPage = -1;q->state = 0;r->next = q;r = q;}r->next = NULL;
}
//记录每个时刻为哪个页面上内存
void print(VP vp) {printf("***************************************************\n");printf("\n时刻%d:\n", sum++);printf("页面%d装入内存\n", vp->virtualPage);printf("%3d", vp->virtualPage);printf("\t%3d", vp->realPage);printf("\t%3d", vp->state);printf("\t%3d", vp->enterTime);printf("\t\t%3d\n", vp->accessTime);
}
//打印虚页 实页当前时刻状态
void showAns(VP vp, RP rp) {vp = vp->next;rp = rp->next;printf("\n虚页号\t实页号\t状态\t加入时间\t访问时间\n");while (vp != NULL) {printf("%3d", vp->virtualPage);printf("\t%3d", vp->realPage);printf("\t%3d", vp->state);printf("\t%3d", vp->enterTime);printf("\t\t%3d\n", vp->accessTime);vp = vp->next;}printf("\n实页号\t虚页号\t状态\n");while (rp != NULL) {printf("%3d", rp->realPage);printf("\t%3d", rp->virtualPage);printf("\t%3d\n", rp->state);rp = rp->next;}printf("\n");
}
//LRU页面置换算法
void function(VP vp, RP rp, ElemType arr[]) {//创建的是带头结点的链表，所以指向头结点的下一个节点为 0号 节点的值VP v = vp->next;RP r = rp->next;bool flag = false;//控制缺页置换操作完成后 跳出循环for (int i = 0; i < N; i++) {while (v != NULL) {flag = false;//每次循环都要重置flag//第一种情况，虚页号和页面号引用串值相等且此时不在内存中if (v->virtualPage == arr[i] && v->state == 0) {//如果实页没满，直接装入内存if (count < rpNum) {v->state = 1;//状态置为1while (r != NULL) {if (r->state == 0) {//找一个实页中的空块r->state = 1;	//状态置为1//修改虚页，实页中相关属性，与之对应r->virtualPage = v->virtualPage;v->realPage = r->realPage;v->enterTime = i + 1;v->accessTime = i + 1;flag = true;//标志找到一个空块print(v);showAns(vp, rp);count++;	//缺页次数加一break;}r = r->next;//没找到符合要求的节点，继续向下找}}//第二种情况，如果实页满了，进行页面置换else {VP temp = vp->next;VP t = (VP)malloc(sizeof(VirtualPage));//临时节点，用来找到访问时间最小的节点t->accessTime = MAX;while (temp != NULL) {//比大小if (temp->accessTime < t->accessTime && temp->state == 1) {t = temp;}temp = temp->next;}v->state = 1;//置换的页面状态改为1t->state = 0;//被置换的页面状态改回0while (r != NULL) {//通过虚页的实页号找到实页中对应的实页块，并修改对应参数if (t->realPage == r->realPage && r->state == 1) {v->realPage = t->realPage;t->realPage = -2;//表示装入过内存v->enterTime = i + 1;v->accessTime = i + 1;r->virtualPage = v->virtualPage;flag = true;//标志替换成功print(v);showAns(vp, rp);count++;break;}r = r->next;}}}//第三种情况，此时刻的页面号在内存中else if (v->virtualPage == arr[i] && v->state == 1) {v->accessTime = i + 1;//修改访问时间flag = true;//标志操作完成print(v);showAns(vp, rp);break;}if (flag) break;//三种情况中，任一种成功就直接判断下一个页面号，不成功再判断下一个虚页块是否满足要求v = v->next;}//用于回到链表头。进行重新比对v = vp->next;r = rp->next;}
}
int main() {VP vp;init_VP(vp);RP rp;init_RP(rp);function(vp, rp, arr);showAns(vp, rp);int s = count + 1;printf("\n该访问序列的缺页率为：%.2f%c\n\n\n\n",(s*1.0/N)*100,'%');return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！