操作系统课程设计 页面置换算法C语言0001

1、页面置换算法一题目要求：通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。要求设计主界面以灵活选择某算法，且以下算法都要实现1)最佳置换算法(OPT):将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。2)先进先出算法(FIFO):淘汰最先进入内存的页面，即选择在内存中驻留时间最久的 页面予以淘汰。3)4)二实验目的：1、用C语言编写OPT、FIFO、LRU , LFU四种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的

2、运用能力和实践能力。三、设计要求最近最久未使用算法(LRU):淘汰最近最久未被使用的页面。 最不经常使用算法(LFU)1、 编写算法，实现页面置换算法FIFO、LRU2、针对内存地址引用串，运行页面置换算法进行页面置换;3、算法所需的各种参数由输入产生(手工输入或者随机数产生)； 4、输出内存驻留的页面集合，页错误次数以及页错误率;四. 相关知识：1虚拟存储器的引入：局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储 空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。2. 虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内

3、存容量进行扩充的一种 存储器系统。3. 虚拟存储器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成 的页面形式虚拟存储系统。请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成 的段式虚拟存储系统。4. 页面分配：平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法，根据进程的大小按比例分配物理块。考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分 配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。5. 页面置换算法：常用的页面置换算法有 OPT、

4、FIFO、LRU、Clock、LFU、PBA等。五、设计说明1、采用数组页面的页号-16 -2、3、FIFO算法，选择在内存中驻留时间最久的页面予以淘汰;分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。LRU算法，根据页面调入内存后的使用情况进行决策;同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：六. 设计思想：OPT基本思想：是用一维数组PagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页 面。数组nextm

5、SIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理 块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。FIFO基本思想：是用队列存储内存中的页面， 队列的特点是先进先出， 与该算法是一致的， 所以每当发 生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组timemSIZE记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。LRU基本思想：是用一维数组PagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页 面。数组flag10标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就 从物理块中页面标记最小的一

6、页，调出该页，换入所缺的页面。七. 流程图：如下页所示:3P： 20 串 用空格隔开書六.运行结果：1. 按任意键进行初始化:请揃入物理块旳个数5 ：请龟入更面号弓俑串的1数二请履次龜入页面号引用戟用空格隔开:$01203042303212017012. 载入数据:M= 3个数tPd盹：20请撞A物理块旳人塑人h i辜输入贝亦号舟用第的士宀S 请廉次i入页面号引用串调空格隔开儿70120304230321201701正在载入数据，请稍候tT!Loading.Fin ish.载入咸功，按任意键进入置换算法选择界面 3. 进入置换算法选择界面:输鼻的页面号引用串如70120304230请选贝面置换

7、算法*32120170*e用 S:使 切未 出久氏 先最e 进近佳岀 12 3 4W * * *ft4. 运算中延迟操作:32120170输入的页面号弓串为: 7*4E-0120304230请选择页面萱换算法：7U rrr=-O Rn 疔使 Fte.t讨 岀久s: 酋阪w 进近 先蕙顋12 3 4算 计 关 乍用*操行*选在*请正5. 三种算法演示结果:3输 2的页面号引用串為.70120304230:备甜N备轟鼻：* *先意惫 12 3 4进先岀 近最久未使用5RU f*请选择操作；701：7： 17!:! ：Bi2 0 !7! i2i iei !0! !1! !1 !3：2 I!3：11B

8、 42：2 : !3： !Q：4： !3!0：3!4：!2：!0：i4i 12! !3 !eie !2 !321i0i ili J3 !i&i ：1! ：2 :17!iliL2 !7! i0i !2 !：7!i0i：1 !缺页率：15/20 谊I可命中率：5k脓任意键重新选择换算法，-輸入的页面号引用串节;0120304230谙选睪页面置换算法：1.先进先岀佳 4退岀选择操作：1? 0 1 !7! *7! !7! !2!:! ：0! !0! !0： t ! t ! tl! Hi2 2 03 Q!Q !；3t4230!4t !4t !4t iQt ：0： ：0： ：3: !3! i3t 2t 2

9、t !2t1!1! !3 !E2i1 !1! ：0! 12!7tl!：0!tVi赵更矜12/20 说同命中率：40X捋任意键重新选择H换算法：输AS顶面号引用串知70120304230请选择页面置换算法：12 3 4进近佳岀先岀最久未使用a刖PT*操*择0 陥71i2i：0!El；!71：0：Hi鶴加麟4技意破重新八. 结论通过这次课程设计，不仅让我了解了页面置换算法，开始我一味的进行调试，急切的想侥幸调试出来，但由于没有进行深入的考虑，我调试了很久都没没有成功，我仔细的分析题目分析材料,在原由的基础上我进亍了改正，我最后还是调试成功了，还是经过了一翻努力， 这 次操作系统实习，不仅让我对操作

10、系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。通过努力，三个页面置换算法程序都已经完成，此时此刻，我心里多了些成就感。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。 主要有以下几点收获：1.通过对上网和看书查阅相关资料，使自己对C语言的基本框架有新的了解，加深了对可视化程序的认识。2.在使用C语言来实现功能时，不像以往用的其他语言，它比较简练，更容易 理解，实用性很强。3. 先进先出页面置换和 LRU以及OPT算法各有特点，但是实践起来却很大， 使自己 对页面置换算法有了新的认识。一周半的课程设计就要结束了，不但对专业知识有了更深的理解，更使的自己认识到实践的重要性，理论

11、、实践相结合才能达到很好的学习效果，特别是程序语言的学习。六.源代码：如下页所示【使用 C语言】#in clude #i nclude /*全局变量*/int mSIZE; /* 物理块数 */int PSIZE; /*页面号引用串个数*/static int memery10=0; /* 物理块中的页号 */ static int Page100=0; /* 页面号引用串 */ static int temp10010=0; /*辅助数组 */*置换算法函数*/void FIFO();void LRU();void OP T();/*辅助函数*/void pnnt(un sig ned in

12、t t);void desig nBy();void downl oad();void mDelay (un sig ned int Delay);/*主函数*/void mai n()int i,k,code;printf(” Iprintf(丨请按任意键进行初始化操作printf(” printf(” );getch();system(cls);printf(”请输入物理块的个数 (M=10):);scan f(%d,&mSIZE);printf(”请输入页面号引用串的个数(P=100):);scan f(%d,&p SIZE);puts(请依次输入页面号引用串(用空格隔开):);for(

13、i=0;i pSIZE;i+)scan f(%1d,&p agei);dow nl oad();system(cls);dopu ts(输入的页面号引用串为：”)；for(k=0;k=( pSIZE-1)/20;k+)for(i=20*k;(i pSIZE )&(i”printf(”输入错误，请重新输入:printf(按任意键重新选择置换算法：getch();system(cls);while (code!=4);getch();/*载入数据*/void downl oad()int i;printf(”printf(”printf(”prin tf(Loadi ng.n);printf(”

14、for(i=0;i51;i+)prin tf(b);for(i=0;i);”printf(nFinish.n载入成功，按任意键进入置换算法选择界面: getch();/*设置延迟*/void mDelay (un sig ned int Delay) un sig ned int i;for(;Delay0;Delay-)for(i=0;i124;i+) printf(” b); void pnnt(un sig ned int t)int i,j,k,l;int flag;for(k=0;k=( pSIZE-1)/20;k+)for(i=20*k;(i pSIZE) &(i20*(k+1);

15、i+)if(i+1)%20=0)|(i+1)%20)&( i=pSIZE-1) prin tf(%dn, pagei);elseprin tf(%d”,p agei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k )&(i=j)prin tf( |%d|,tem p ij);elseprin tf( | |);for(i=mSIZE+20*k;(i pSIZE) &(i20*(k+1);i+) for(flag=0,l=0;lmSIZE;l+)if(tem p il=tem pi-1l)flag+;if(flag=mSIZE)/*页面在物理块中*/ pri

16、ntf(”);elseprin tf( |%d|,tem p ij);/*每行显示20个*/if(i%20=0)con ti nue;prin tf(n);printf(”n);printf(” 缺页次数：%dtt,t+mSIZE); printf(缺页率：d/%drTt+mSIZE,pSIZE);printf(” 置换次数：%dtt,t);printf(” 访问命中率：%d%n,pSIZE-(t+mSIZE)*100/pSIZE); printf(”n);/*计算过程延迟*/void compu te()int i;printf(”正在进行相关计算，请稍候 )；for(i=1;i20;i+)

17、mDelay(15);if(i%4=0)bbbbbb);prin tf(bbbbbbelseprintf( );for(i=0;i+30; prin tf(b);for(i=0;i+30; printf(” );for(i=0;i+30; prin tf(b);/*先进先出页面置换算法*/void FIFO()int memery10=0;int time10=0; /* 记录进入物理块的时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/for(i=0;imSIZE;i+)memeryi=p ag

18、ei;timei=i;for(j=0;jmSIZE;j+)temp ij=memeryj;for(i=mSIZE;i pSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei) k+;if(k=mSIZE) /*如果不在物理块中*/coun t+;/*计算换出页*/max=time0time1?0:1;for(m=2;mmSIZE;m+) if(timemtimemax) max=m; memerymax=p agei;timemax=i; /*记录该页进入物理块的时间*/for(j=0;jmSIZE;j+)temp i

19、j=memeryj;elsefor(j=0;jmSIZE;j+)tem p ij=memeryj;comp ute();prin t(co un t);/*最近最久未使用置换算法*/void LRU()int memery10=0;int flag10=0; /* 记录页面的访问时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/for(i=0;imSIZE;i+)memeryi=p agei; flagi=i;for(j=0;jmSIZE;j+)tem p ij=memeryj;for(i=mSIZE;i pSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memery|j!=pagei)k+;elseflagj=i; /*刷新该页的访问时间*/if(k=mSIZE) /*如果不在物理块中*/coun t+;/*计算换出页*/max=flag0flag1?0:1;for(m=2;mmSIZE;m+) if(flagmflagmax) max=m;memerymax=p agei;flagmax=i; /*记录