页式存储管理页面置换算法

1、 实验三 页面置换算法1 实验目的 在虚拟页式存储管理中，当每次发生缺页时，尽管可以随机选择一个页面置换，但是选择不常使用的页面会使系统性能好得多，如果一个经常使用的页面被置换出去，很有可能他很快又要被调入内存，带来不必要的额外开销。通过本实验加深对几种页面置换算法的理解，了解各种置换算法的执行方法。2 实验内容 分别模拟理想页面置换算法（OPT），先进先出页面置换算法（FIFO），最近最少使用页面置换算法（LRU），输出如P202页的表格。3 实验环境VC6.0，C，Windows4 数据结构/内存页面结构体struct PAGEint cp;/内存页面所存的当前页面 struct PAGE

2、 *next;/指向后续页面的指针;程序中采用链结构五实验结果截屏六实验源代码# include # include # define MAX1 15/输入的页面最多为15页# define MAX2 10/所分配的内存页面数做多为5页int cpageMAX1;/存放输入的页面int ctotal;/用户输入的页面总数int stotal;/内存分配的页面数int recordMAX1MAX2;/记录每页的历史存放情况int length;/链表当前长度char chMAX2;/记录缺页情况/内存页面结构体struct PAGEint cp;/内存页面所存的当前页面 struct PAGE

3、*next;/指向后续页面的指针;typedef struct PAGE PG;PG *s;/链表头指针PG *e;/链表尾指针/遍历链表，判断该页是否在内存int isInlink(int page)PG *q = s-next; while(q != NULL)if(q-cp = page)return 0;/在，返回0elseq = q-next;return 1;/不在，返回1/在LRU算法中，若当前页在内存，则调整链表，将当前页放到表头void transt(int page) PG *q = s-next,*r; while(q-cp != page) r = q;q = q-ne

4、xt;if(q = e)e = r;r-next = q-next;q-next = s-next;s-next = q;/将新页插到表头void insertHead(PG *p)if(s-next = NULL)e = p;p-next = s-next;s-next = p;/删表尾void deletetail()PG *q,*r;q = s-next;while(q-next != e)q = q-next;q-next = NULL;r = e;e = q;delete r;/判断在后stotal - 1页中是否出现int isInnext(int page1,int page2

5、) for(int i = 1;i stotal;i+)if(page1 next;if(page = ctotal-1) deletetail(); return; for(q;q != NULL;q = q-next) if(isInnext(page,q-cp) = 0)/如果该页在后几页中未出现r-next = q-next;if(q = e)e = r;delete q;return;else r = q;/先进先出置换算法void FIFO() int i; for(i = 0;i cp = cpagei; p-next = NULL; if(length next; for(c

6、= 0;c cp; q = q-next; /最近最少使用置换算法void LRU() int i; for(i = 0;i cp = cpagei; p-next = NULL; if(length next; for(c = 0;c cp; q = q-next; /OPT置换算法void OPT() int i; for(i = 0;i cp = cpagei; p-next = NULL; if(length next; for(c = 0;c cp; q = q-next; void main()while(1)int choice;printf(选项：n);printf( 1.FI

7、FO算法n);printf( 2.LRU算法n);printf( 3.OPT算法n);printf( 4.退出 );printf( 请选择：);scanf(%d,&choice);if(choice = 4) exit(-1);s = (PG*)malloc(sizeof(PG);s-next = NULL;e = s;length = 0;printf(nn请输入所要运行的页面总数，应小于%d:,MAX1);scanf(%d,&ctotal);while(ctotal MAX1) printf(输入的页面数大于%d,请重新输入:,MAX1); scanf(%d,&ctotal);int i,

8、j; printf(请输入页面走向:);for(i = 0;i MAX2) printf(输入的页面数大于%d,请重新输入:,MAX2); scanf(%d,&stotal); /初始化记录组for(i = 0;i ctotal;i+)for(j = 0;j stotal;j+) recordij = -1; for(j = 0;j ctotal;j+) chj = v;/默认不缺页 printf(n );for(i = 0;i ctotal;i+)printf( %d,cpagei); if(choice = 1)FIFO(); else if(choice =2)LRU();else OPT(); for(i = 0;i stotal;i+)printf(n页%d: ,i+1);for(j = 0;j