suanfa.rar_fifo_页面置换算法 ；LRU ；LFU；OPT

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<time.h> #define Bsize 4 using namespace std; int PAGES; /*页面引用页数*/ #define M 3 /*当前分配给改作业的物理块数*/ /*页面引用串*/ int pagee[100]; int rel[M][100]; /*存储结果数组*/ /*内存物理块结构体*/ int Process[100];//页面队列 int Memory[100];//块数 int OPTQueue[100];//OPT算法的队列 int ProcessNum;//页面数 int ii; //OPT算法找到最长未使用的 ; typedef struct{ int pnum; /*该块中所存的页面号*/ int tm; /*从最近一次调入所经历的时间*/ }PBlock; struct BLOCK//声明物理块类型 { int pagenum;//页号 int use;//最近使用次数 int time; }; int num = 0; //记录指令的序号 int n = 0;//记录缺页的次数 static int temp[100];//用来存储320条指令 struct BLOCK block[4];//大小为4的物理块数组 /****************************************************************************** ***********/ int findExist(int curpage); //查找物理块中是否有该页面 int findSpace();//查找是否有空闲物理块 int findReplace();//查找应予置换的页面 void display();//显示置换过程 void zhiling();//产生320条指令,显示并存储到temp[320],并调度页号队列 void LFU();//LFU算法 /****************************************************************************** ***********/ int findExist(int curpage)//查找物理块中是否有该页面 { int i; for (i = 0; i < Bsize; i++) { if (block[i].pagenum == curpage) return i;//检测到内存中有该页面，返回block中的位置 } return -1; } /****************************************************************************** ***********/ int findSpace()//查找是否有空闲物理块 { int i; for (i = 0; i < Bsize; i++) { if (block[i].pagenum == -1) return i;//找到空闲的block，返回block中的位置 } return -1; } /****************************************************************************** ***********/ int findReplace()//查找应予置换的页面 { int i, min = 0; for (i = 0; i < Bsize; i++){ if (block[i].use < block[min].use) min = i;//找到应予置换页面，返回BLOCK中位置 } return min; } /****************************************************************************** ***********/ void display()//显示置换过程 { int i,min=0; for (i = 0; i < Bsize; i++) { if (block[i].pagenum != -1&&i!=3) { for (int j = i,int m=0; j < Bsize; j++) { if (block[j+1].pagenum!=-1) { for (m=j+1; m < Bsize; m++) { if (block[m].time<block[j]) } } } } } printf("\n"); } /****************************************************************************** ***********/ void zhiling()//产生320条指令,显示并存储到temp[320],并调度页号队列 { int j = 0; /*srand((int)time(NULL)); num = rand() % 320; printf("%d", num); for (i = 0; i < 320; i = i + 5) { temp[i] = num; temp[i + 1] = num + 1; temp[i + 2] = rand() % (num + 1); temp[i + 3] = temp[i + 2] + 1; temp[i + 4] = temp[i + 3] + 1 + rand() % (320 - temp[i + 3] - 1); num = rand() % 320; } for (i = 0; i < 320; i++){ printf(" %03d", temp[i]); if ((i + 1) % 10 == 0) printf("\n"); }*/ printf("页面个数："); scanf("%d", &ii); printf("i:%d", ii); printf("\n"); printf("输入页面序列\n"); for (int j = 0; j < ii; j++) { scanf("%d", &num); temp[j] = num; } for (j = 0; j < ii; j++) { printf(" %d", temp[j]); } } /****************************************************************************** ***********/ void LFU(){ int exist, space, position; int page, i, j, k; double pr; for (i = 0; i < ii; i++) { num = temp[i];//指令记录号 //page = num / 10;//页号 exist = findExist(num);//是否有记录 if (exist == -1) { //没有 space = findSpace();//判断是否为空的标记 if (space != -1) {//有空盘块 block[space].pagenum = num; block[space].time++; printf("输入页面号：%d", temp[i]); printf("发生缺页:"); display(); printf("\n"); n = n + 1; } else { printf("输入页面号：%d", temp[i]); position = findReplace(); block[position].pagenum = num; printf("发生缺页"); display(); printf("\n"); n++; } } else { printf("输入页面号：%d", temp[i]); block[exist].use++; block[exist].time++; printf("不发生缺页"); display(); printf("\n"); } } pr = n / double(ii); printf("缺页次数:%d \n", n); printf("缺页率:%.3lf\n", pr); printf("命中率:%.3lf\n", 1 - pr); } /****************************************************************************** ***********/ void Input1() { cout << "请输入页面数：" << endl; cin >> PAGES; cout << "请输入页面序列号：" << endl; for (int i = 0; i < PAGES; i++) cin >> pagee[i]; } /*初始化物理块数组*/ void init(PBlock *pb) { int i, j; //pb = (PBlock*)malloc(sizeof(PBlock)*M); for (i = 0; i < M; i++){ pb[i].pnum = -1; pb[i].tm = -1; for (j = 0; j < PAGES; j++){ rel[i][j] = -1; } } } /*打印结果数组*/ void printRelArr(int rel[M][100]) { int i, j; for (i = 0; i < M; i++){ for (j = 0; j < PAGES; j++){ if (rel[i][j] == -1) cout << "- "; else cout << rel[i][j] << " "; } cout << endl; } } /*打印一维数组*/ void printArr1(int *arr, int n) { int i; for (i = 0; i < n; i++){ cout << arr[i]<<" "; } cout << endl; } /*查看页面号为num的页面是否在内存块中,存在返回1*/ int in_mem(int num, PBlock *pb, int m) { int i; int b = 0; for (i = 0; i < m; i++){ if (pb[i].pnum == num){ b = 1; break; } } return b; } /*获得最近最久的块*/ int getP(PBlock *pb, int p) { int i; bool out = true; // for (i = 0; i < M; i++){ if (pb[i].tm == -1){ p = i; out = false; break; } } if (out){ for (i = 0; i < M; i++){ if (pb[i].tm > pb[p].tm) p = i; } } return p; } int getEQnum(int num, PBlock *pb) { int i; int in = -1; for (i = 0; i < M; i++){ if (pb[i].pnum == num){ in = i; break; } } return in; } /*LRU算法*/ void lru(PBlock *pb, int m) { int lps = 0; /*缺页次数*/ double lpp; /*缺页率*/ int p = 0; /*替换指针*/ int index = 0; /*页面号索引*/ while (index < PAGES){ if (!in_mem(pagee[index], pb, m)){ /*如果页面不在物理块中*/ p = getP(pb, p); pb[p].pnum = pagee[index]; pb[p].tm = 0; lps++; for (int i = 0; i < M; i++){ rel[i][index] = pb[i].pnum; } } else{ /*如果页面在物理块中*/ int in = getEQnum(pagee[index], pb); /*获取该页面在物理块中的索引*/ pb[in].tm = 0; } int i; for (i = 0; i < M; i++){ if (i != p&&pb[i].tm != -1){ pb[i].tm++; } } index++; } cout << "LRU算法所得缺页次数为 " << endl << lps<<endl; lpp = 1.0*lps / PAGES; cout << "LRU算法缺页率为: " << endl << lpp<<endl; cout << "页面号序列为:" << endl; printArr1(pagee, PAGES); cout << "LRU结果数组为:" << endl; printArr1(pagee, PAGES); cout << endl; printRelArr(rel); } //读入页面流 class page { public: int num; page() { num = 0; } }; void FIFO() { cout << "------FIFO-----------" << endl; int error = 0; page frame[3];//页帧 int num = 3; for (int i = 0; i < 3; i++)//处理前三个引用 { frame[i].num = Process[i]; error++; cout << frame[i].num << " | "; for (int j = 0; j <= i; j++) cout << frame[j].num << ' '; cout << endl; } for (int i = 3; i < 20; i++) { int j; for (j = 0; j < 3; j++) if (Process[i] == frame[j].num) { cout << Process[i] << endl; break; } if (j == 3) { error++; frame[((error - 1) % 3)].num = Process[i];//换掉最旧的页 cout << Process[i] << " | "; for (int k = 0; k < 3; k++) cout << frame[k].num << ' '; cout << endl; } } cout << "缺页次数：" << error << endl << endl; float str; str = (float)error / ProcessNum;