操作系统课程设计报告--页面置换算法模拟程序设计.docx

操作系统课程设计报告题目：页面置换算法模拟程序设计专 业：院系：目录第一部分概述第二部分设计的基本概念和原理第三部分总体设计3.1算法流程图3.2算法的简要实现方法3.2.1 OPT页面置换算法3.2.2 FIFO页面置换算法3.2.3 LRU页面置换算法3.2.4 LFU页面置换算法第四部分详细设计4.1 main 函数4.2 OPT函数4.2 FIFO 函数4.3 LRU函数4.5 LFU函数4.6辅助函数4.6.1 Designer 函数4.6.2 mDelay 函数4.6.3 Download 函数4.6.4 Compute 函数4.6.5 showTable 函数第五部分实现源代码第六部分简要的使用说明及主要运行界面第七部分总结第八部分参考文献第一部分概述设计任务：页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面 调度的机制，在模拟实现OPT、FIFO、LRU和LFU几种经典页面置换算法的基 础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。第二部分设计的基本概念和原理(1) .页面淘汰机制页面淘汰又称为页面置换。若请求调页程序要调进一个页面，而此时该作业 所分得的主存块已全部用完，则必须淘汰该作业已在主存中的一个页。这时，就 产生了在诸页面中淘汰哪个页面的问题，这就是淘汰算法(或称为置换算法)。置换算法可描述为，当要索取一个页面并送入主存时，必须将该作业已在主存中 的某一页面淘汰掉，用来选择淘汰哪一页的规则就叫做置换算法。(2) .各种页面置换算法的实现思想OPT算法是当要调入一新页而必须先淘汰一旧业时，所淘汰的那一页应是以 后不要再用的或是以后很长时间才会用到的页。FIFO算法的实质是，总是选择在主存中居留时间最长(即最老)的一页淘 汰。其理由是最先调入主存的页面，其不再被使用的可能性比最近调入主存的页 的可能性大。LRU算法的实质是，当需要置换一页时，选择最长时间未被使用的那一页淘 汰。如果某一页被访问了，它很可能马上还要被访问；相反，如果它很长时间未 曾用过，看起来在最近的未来是不大需要的。LFU即最不经常使用页置换算法，要求在页置换时置换在一定时期内引用计 数最小的页，因为经常使用的页应该有一个较大的引用次数。本次设计取整个页 面访问时期为计算周期，实际问题中应根据页面数量多少来确定周期。第三部分总体设计3.1算法流程图输入页面访问序列是否是否缺页按算法不同淘汰一页面置缺页标志flag为*调入所访问的页面> 取访问的页号<查页表3.2算法的简要实现方法选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：最佳置换算法（OPT）：是用一维数组pagePSIZE存储页面号序列，memeryMSIZE是存储装入物理块中的页面，用pflagPSIZE数组标记缺页中断处。数组nextMSIZE记录物 理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问 时间最大的页面，调出该页，换入所缺的页面，然后初始化nextMSIZE，便于 下次使用。【特别声明】若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。先进先出置换算法（FIFO）：是用一维数组pagePSIZE存储页面号序列，memeryMSIZE是存储装入物 理块中的页面，用pflagPSIZE数组标记缺页中断处。采用队列的思想，总是把 最先进入物理块中的页面放在第一个位置，当发生缺页时，就从队头删除一页， 而从队尾加入缺页。最久未使用置换算法（LRU）：是用一维数组pagePSIZE存储页面号序列，memerymSIZE是存储装入物 理块中的页面，用pflagPSIZE数组标记缺页中断处。总是把最长时间内未被使 用的页放在最后一块，当发生缺页时，就删掉最后一页，将当前所缺页面放入第 一块。最不经常使用淘汰算法（LFU）：是用一维数组pagePSIZE存储页面号序列，memerymSIZE是存储装入物 理块中的页面，用pflagPSIZE数组标记缺页中断处。用useMSIZE数组记录当 前各页已使用次数，其中use0中存放使用次数最少的页的次数，当发生缺页 时，就在已放入物理块的页中查找当前使用次数最少的页，将之删掉，并引入当 前缺页页面。第四部分详细设计main函数：void main()(int i, k, code;int mSize, pSize, pagePSIZE;system("color 0A");Designer();printf(" |请按任意键继续.In");printf( 11n");printf( >>> )；getchar();system(cls)；/DOS命令，清除屏幕上的所有文字system(color 0B)； /改变控制台的前景和背景色printf(请输入物理块的个数mSize <= 10：)；scanf(d， &mSize);printf( 请输入页面数pSize <= 50：)；scanf(d， &pSize);printf(请输入页面序列110之间：n)；for (i = 0; i < pSize; i +)scanf(d，&pagei);Download(pSize, mSize);system(cls);system(color 0E);do(printf(即将进入物理块的页面序列为：n)；for (i = 0; i < pSize; i +)printf(3d，pagei);printf(n);printf(* * * * * * * * * * * * * * * * * * * * * * * * * * * * *n)；printf(* 请选择页面置换算法： *n);printf(* _*n)；printf(* 1.最佳(OPT) 2.先进先出(FIFO) 3.最近最久未使用 (LRU)*n");printf(* 4.最不经常使用(LFU,当前使用次数最少)5.退出*n);printf("* * * * * * * * * * * * * * * * * * * * * * * * * * * * *n");printf("请选择操作：bb");scanf(d,&code);switch (code)(case 1:OPT(page, pSize, mSize);break;case 2:FIFO(page, pSize, mSize);break;case 3:LRU(page, pSize, mSize);break;case 4:LFU(page, pSize, mSize);break;case 5:system("cls");system("color 0A");Designer(); 显示设计者信息后退出printf (- |谢谢使用页面置换算法演示器！正版授权®| n");printf( 11 n)；exit(0);default:printf(输入错误，请重新输入：)；/printf(按任意键重新选择置换算法：>>>)；getchar();system(pause)； /冻结屏幕system(cls); while (code != 5);getchar ();OPT函数：void OPT(int page, int pSize, int mSize) (int i, j, k;int count = 0; /计数器int memeryMSIZE = 0;/存储装入物理块中的页面int nextMSIZE = 0;/记录物理块中对应页面的最后访问时间sum = 0;for (i = 0; i < pSize; i +)j = 0;while (j < mSize) && (pagei != memeryj) /查页表，看是否 缺页j +;if (j = mSize)flag = '*'缺页，则置标志flag为'*'sum += 1;/记录缺页次数if (sum <= mSize)/如果物理块中有空余，则将当前页面直接放入for (j = 0; j < mSize; j +)if (memeryj = 0)memeryj = pagei;break;else/物理块已满的情况下for (j = i + 1; j < pSize; j +) /查找以后不再使用或在 最长时间以后才会用到的页for (k = 0; k < mSize; k +)if (pagej = memeryk)nextk += 1;/记录将被使用的次数，可以不用累加count +;记录物理块中以后将即被使用的页面个数break;if (count = mSize - 1) break; /如果已有 mSize-1 个页面即将被使用，则剩下最后一个页面一定是最长时间后才会用到的页if (count = 0)memery0 = pagei;else(count = 0;for (k = 0; k < mSize; k +)(if (nextk = 0)总是置换出第一个可以换出的页memeryk = pagei;nextk = 0;/初始化 next 口数组else flag =''pflagi = flag;/记录当前页的缺页情况for (k = 0; k < mSize; k +) /记录每一次的置换情况 tableki = memeryk;Compute();showTable(page, pSize, mSize);FIFO函数：void FIFO(int page, int pSize, int mSize)int i, j;int memeryMSIZE = 0;存储装入物理块中的页面sum = 0;for(i = 0; i < pSize; i+) 查页表，看是否缺页j = 0;while (j < mSize) && (pagei != memeryj) j+;if (j = mSize)flag = '*'缺页，则置标志flag为'*'sum += 1;for (j = mSize-1; j > 0; j -) 淘汰最先调入的页面，并调入当前页面 memeryj = memeryj-1;memery0 = pagei;else flag =''pflagi = flag;for (j = 0; j < mSize; j+) tableji = memeryj;Compute();showTable(page, pSize, mSize);LRU函数：void LRU(int page, int pSize, int mSize)int i, j, k;int memeryMSIZE = 0;存储装入物理块中的页面sum = 0;for (i = 0; i < pSize; i +)j = 0;while (j < mSize) && (pagei != memeryj)查页表，看是否缺页j +;if (j = mSize)flag = '*' 缺页，则置标志flag为'*'sum += 1;k = j - 1;elseflag =''k = j;pflagi = flag;记录当前页的缺页情况while (k > 0) 总是把最长时间内未被使用的页放在最后一页memeryk = memeryk-1;k -;memery0 = pagei; 调入当前页面for (k = 0; k < mSize; k +) 记录每一次的置换情况 tableki = memeryk;Compute();showTable(page, pSize, mSize);LFU函数：void LFU(int page, int pSize, int mSize)一int i, j, replace; /replace标记使用次数最少的页int useMSIZE = 0; /记录当前各页已使用次数，其中use0中存放使用次 数最少的页的次数int memeryMSIZE = 0;存储装入物理块中的页面sum = 0;for (i = 0; i < pSize; i +)usepagei += 1; /下标即为页号j = 0;while (j < mSize) && (pagei != memeryj)查页表，看是否缺页j +;if (j = mSize)flag = '*' 缺页，则置标志flag为'*'sum += 1;if (sum <= mSize)如果物理块中有空余，则将当前页面直接放入for (j = 0; j < mSize; j +)if (memeryj = 0)memeryj = pagei;break;else物理块已满的情况下use0 = 100;for (j = 0; j < mSize; j +)在已放入物理块的页中查找当前使用次数最少的页if (usememeryj < use0)use0 = usememeryj;replace = j;标记页号memeryreplace = pagei;elseflag =''pflagi = flag;记录当前页的缺页情况for (j = 0; j < mSize; j +) 记录每一次的置换情况 tableji = memeryj;Compute();showTable(page, pSize, mSize);辅助函数Designer 函数: void Designer() printf(" |1 n");printf("课题：页面置换算法 | n");printf(" !学号：11150038 | n");printf(" !姓名：李艳平 | n");printf(" !<Visual C+ 6.0> | n");printf(" 11 n");mDelay 函数：void mDelay(unsigned int Delay)unsigned int i;while (Delay > 0)for (i = 0; i < 125; i+)printf(" b");Delay-;Download 函数：void Download(int pSize, int mSize)int i;system("color 0D");printf(" |1 n");printf(":正在载入数据，请稍后.：n");printf(" 11 n");printf("Loading.n");printf("0n");for (i = 0; i < 51; i+)printf("b");for (i = 0; i < 50; i+)mDelay(pSize+mSize)/2);printf(">");printf("nFinish.n载入成功，按任意键进入置换算法选择界面：>>>");getchar();Compute 函数：void Compute()int i;printf("正在进行相关计算，请稍候.n");for(i=1;i<20;i+)mDelay(15);if(i%4=0)printf("bbbbbb bbbbbb");elseprintf(">>>");for(i=0;i+<30;printf("b");for(i=0;i+<30;printf(" ");for(i=0;i+<30;printf("b");showTable 函数：void showTable(int page, int pSize, int mSize)(int i, j;/*printf("即将进入物理块的页面序列为:n");for (i = 0; i < pSize; i +)printf("%3d", pagei);printf (-n输出置换过程，“*”标记缺页中断处n)；*/for (i = 0; i < mSize; i +)(for (j = 0; j < pSize; j +) printf("%3d", tableij);printf("n");for (i = 0; i < pSize; i +)printf("%3c", pflagi);printf(nn)；printf(总的缺页次数为：dn，sum);printf(缺页中断率为：.2lf%n，100.0 * sum / pSize);printf( n);第五部分实现源代码#include <stdio.h>#include <stdlib.h>/*宏定义*/#define MSIZE 10最大物理块数#define PSIZE 50最大页面数/*全局变量*/char flag, pflagPSIZE; 缺页标志int tableMSIZEPSIZE; 存放置换记录int sum = 0;记录每个算法的缺页次数/*置换算法函数*/void OPT(int page, int pSize, int mSize); 最佳置换算法void FIFO(int page, int pSize, int mSize); / 先进先出置换算法void LRU(int page, int pSize, int mSize); 最久未使用置换算法void LFU(int page, int pSize, int mSize);最不经常使用淘汰算法(当前使用次数最少)/*辅助函数*/void Designer(); 显示设计者信息void mDelay(unsigned int Delay); 设置延迟void Download(int pSize, int mSize); 载入数据void Compute();计算过程延迟void showTable(int page, int pSize, int mSize); 输出置换过程【主函数及其他函数详见第四部分】第六部分 简要的使用说明及主要运行界面主要运行界面：【运行环境Visual C+ 6.0】课题：页面置换算法学号；1115003S姓名；李艳平<llisuial C* g.0>（1）按任意键继续:EmSize <= 103- 3iae <= 503： 13上菸物理心隔挽入页面敦*仕输入页面序列间L23421562123 4（2）载入数据:if输八物理携的个数 mSize <= 101 ： 3 请揄入页面加<= 50： 13 请输入页面序列E110Z间:1234215G21234江隹葺X魏i"备房二Loading _.»»»>>>»»»»请搅入物理摇的个数加= 土皿m请辄入页面gtpSize <= 501： 13请输入页面序歹|J UT 0ZI®：1234215621234正备瓦成据，请备房Loading.»»»»>»>»»>»>»>»»»»>»>»>»»»»»>>Fin isli-载人成功，按任意键进入置换算法选择界面：请按任意键继续-（3）进入置换算法选择界面:即将讲入物理块的页面序列为；1234215621234*XX4G*XX4G* 共 XXW*请选择页面置换算法；* 1遢佳3PT> 2 .先进光出<FIFO 3.最近最久未使用LRU* 共虬矗不经常使用LFU档前使用次数最少,§傀出 *请选择操作=(4) 运算中延迟操作:即将讲入物理块的页面序列为=123421542*驰* XX* 洼* 夫*1-最佳<opt>2 .先进先出<fifo> 3 最近最久未使用amjw4 -最不经常使用LFU渚前使用次数最少或虑出，请选择页面置换算法；其M拿籍蜀胃,请稍候»»»>>>(5) 四种算法演示结果:即将进入物理块的页面序列为=1234215621234* 荒 *6t6t 蜀*请选择页面置换算怯；*2 先避先出如I F0> 3 最近最久丞使用<LBU>* CLFU苴前使用次.数最少)5-盘出 «4- 2 G W 3 2 6 M 1 2 G 12 6 -1 2 G .g-1 2 6 *肖SI 1 2 5 W请12 4ffi- * w 1 2 4 >使*1计PT常：关1:我 oXX tri< <NA * 7 12 3*佳不*操行曰兽取* 0$ 1 2 8 M 1.4.电选在 1G «即将讲入物理块的页面序列为=1234215621234* 滞羟邦*»»*请选择页面置换算法：共l-ftl±<OPT>4 最不经常使用* 选母操作m E21 在Jl行相关计算 12 3 4 40 12 3 3 0 0 12 2用*¥2 .先谜先出<FIFO> 3 .最近最久本使用CLHU>*（LFU档前使用次数最少）S痕出 *4 3 1*3 12*1 2 G1 2 & W -2 G 5 M6 5 1 V肖* s 1 4 共 请1 4 3 W请按任意键继续.即将进入物理块的页面序列为；1234215621234* 好* * 丑* 在 游丑* *请选择页面置换算法：*<-用 * 使出* 久5-* 最 * 近 . 曰笋*b * 3 J-最* 揪* 0>滩拜 Iffl;* <吏*先FU*2.任*用*>使*FT常 * co经科霜3 佳不*操行 s *s l.d括选在1算3 f.-L4 .4-即将进入物理块的页面序列为：1234215621234*蜀藤* 藤* *虽*注*请选择页面置换算法；*M-汪* 1 最佳<OPT>2先进先出<FIFO>3最近最久未使用<L«U>* 4置不经常使用<LFU,雪前使用次数最少5傀出选择操作=4】在曲行相关计算，请稍候1110 2 2 0 0 3M M K44112 22 23 33 5123*L点的缺页次数为：9q 69.23z 青按任意键继续. - .kJ(6)退出界面:课题：页面置换算法学号=11150938姓名：李艳平<Uisual C+ 6.0> 甄主理点曳理旦理邑还理玉美*r-ess 乱nyto continue_第七部分总结（特色、经验、教训和感受）两周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识， 也培养了我如何去把握一件事情，如何去做一件事情，如何去坚持一件事情，又 如何完成一件事情。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能 力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的 不足和薄弱环节，从而加以弥补，同时对页面置换算法有了更深入的了解。虽然 在写算法的过程中遇到了一些麻烦，但经过我的坚持不懈最终解决了问题。同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同 学的友谊。由于本人的设计能力有限，在设计过程中难免出现错误，恳请老师们 多多指教,我十分乐意接受你们的批评与指正，本人将万分感谢。第八部分参考文献C语言程序设计中国水利水电出版社计算机操作系统庞丽萍编著 人民邮电出版社