资源描述
目录一、课程设计的目的与要求 .11.1设计目的.11.2设计要求.1二、内容、主要功能和实现环境 .22.1设计内容.22.2主要功能.22.3实现环境.2三、实现过程 .33.1课设任务的分析 .33.2程序流程图 .33.3程序关键代码 .63.3.1FIFO算法主要代码 .63.3.2LRU算法主要代码 .73.4增加算法与比较 .93.4.1增加 FIFO 算法 .93.4.2分析比较 .9四、程序测试 .104.1运行结果及截图 .104.2思考题解答 .144.2.1思考题（ 1） .144.2.2思考题（ 2） .14五、课程设计小结 .17六、参考文献 .18一、课程设计的目的与要求1.1 设计目的近年来，由于大规模集成电路（ LSI）和超大规模集成电路（ VLSI ）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。 所以，提高存储器的效率始终是操作系统研究的重要课题之一。 虚拟存储技术是用来扩大内存容量的一种重要方法。 学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。1.2 设计要求任务四采用最近最少使用页淘汰算法 ( LRU) 实现。为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。 然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。1二、内容、主要功能和实现环境2.1 设计内容最近最少使用页淘汰算法 ( LRU) ，这是一种经常使用的方法。 有各种不同的实施方案，本次课程设计采用的是不断调整物理块数组的方法， 即总是淘汰首个物理块数组里面的页， 而把新访问的页插入末物理块， 然后更新存放页面的二维字符数组。如果当前调用页已在物理块内， 则把它再次调整到末物理块。 这样就能保证最近使用的页，总是处于末物理块中，而不常使用的页就移到首物理块，逐个被淘汰，页面访问序列长度太长时， 调整物理块空间花费的代价也是不小的。2.2 主要功能本程序先进入主菜单界面， 由用户选择所需功能模块， 之后由用户自定义输入访问串的长度（页数） ，再输入页面访问序列，最后输入分配给进程的物理块数，用户进入菜单自定义选择淘汰算法FIFO（先进先进先出算法）或LRU （最近最少使用算法），用户此时也可以修改分配给进程的物理块数。选择算法以后输出淘汰页的二维数组， 并计算出缺页次数、缺页率和该算法的页面访问命中率。2.3 实现环境本次课程设计结合算法的特点，采用 Windows 操作系统平台。开发工具为 Microsoft Visual C+6.0 。2三、实现过程3.1 课设任务的分析本示例是采用页式分配存储管理方案， 并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。 另外也考虑到改变页面大小和实际存储器容量对计算结果的影响， 从而可为算则好的算法、 合适的页面尺寸和实存容量提供依据。本程序是按下述原则生成指令序列的：（1） 50%的指令是顺序执行的。（2） 25%的指令均匀散布在前地址部分。（3） 25%的指令均匀散布在后地址部分。示例中选用最佳淘汰算法（ OPT）和最近最少使用页面淘汰算法（ LRU ）计算页面命中率。公式为页面失效次数命中率1页地址流长度假定虚存容量为32K，页面尺寸从 1K 至 8K ，实存容量从 4 页至 32 页。3.2 程序流程图整个程序流程图：3开始显示主菜单界面选择输入菜单选项是菜单 1已执行？结束否是否是否选择 1？是否选择 1？是是 是否选择 0？否否输入访问串的长度否是否选择 2？是否选择 3？是输入访问序列生成方式调用 FIFO是算法调用 LRU算否法输出结果是否选择 4？是否修改物理块数是否选择 0？否是结束输入 0？否否是输入 1？手动输入序列是随机生成序列输入物理块数图 3-1主函数流程图FIFO 算法流程图：4开始当前访问页在物理块？否是标记为 * 发生缺页标记为内存中有空物理块？是否得到空物理块下标low当前页插入到空物理块淘汰物理块数组中第一个元素其余元素下标减一，当前页插入末物理块物理块数组各元素不变更新二维数组否页访问结束？是输出页面淘汰过程结束图 3-2 FIFO算法LRU 算法流程图：5开始当前访问页在物理块？是否标记为 * 发生缺页内存中有空物理块？得到物理块中与当前页相同的元素下标 q标记为否是内存中有空物理块？淘汰物理块数组中第一个元素其余元素下标减一，当前页插入末物理块否得到空物理是得到空物理块下标 low块下标 low物理块中下标大于q的元素下标减一当前页插当前页插入入到该空到 memlow-物理块1 物理块更新二维数组页访问结束？是输出页面淘汰过程否物理块中下标大于 q的元素下标减一当前页插入末物理块结束图 3-3 LRU 算法3.3 程序关键代码算法主要代码for(i=0;in;i+)/查看当前物理块， 看是否缺页并更新二维数组int low=-1;/非空物理块标志for(j=0;jm;j+)/ 判断当前物理块是否装满页面if(memj= )6low=j;/ 得到第一个空物理块的下标break;losei= ;/ 初始化当前页面有效q=0;while(pagei!=memq)&(q!=m)/查询物理块中与当前访问页相同的页面下标q+;if(q=m)flag=*;/ 缺页，则置标志flag 为 *elseflag= ;/ 不缺页if(flag=*)/ 物理块中没有当前访问页(如果有缺页 )if(low!=-1)/存在一个物理块为空memlow=pagei;/ 当前访问页直接插入到该物理块中else/当前物理块装满页面losei=mem0;/ 淘汰最先访问的页面for(j=0;jm-1;j+)memj=memj+1;/淘汰第一个物理块中的页面，其余页面下标减一memm-1=pagei;/ 最后一个物理块保存当前访问页面for(j=0;jm;j+)Listji=memj;/用当前物理块里的内容更新二维数组fi=flag;/更新标记当前访问页是否缺页的字符数组算法主要代码for(i=0;in;i+)/查页表，看是否缺页int low=-1;/ 物理块是否为空的标志for(j=0;jm;j+)if(memj= )/ 判断当前物理块是否有空的物理块low=j;/ 得到第一个空物理块的下标7break;losei= ;/ 初始化当前页面有效q=0;while(pagei!=memq)&(q!=m)q+;if(q=m)flag=*;/ 缺页，则置标志flag 为 *elseflag= ;if(flag=*)if(low!=-1)/物理块中有空位memlow=pagei;elselosei=mem0;/ 淘汰最近最久未使用的页面for(j=0;jm-1;j+)/ 淘汰最先调入的页面调入当前访问的memj=memj+1;memm-1=pagei;elseif(low!=-1)for(j=q;jlow-1;j+)memj=memj+1;memlow-1=pagei;elsefor(j=q;jm-1;j+)memj=memj+1;memm-1=pagei;for(j=0;jm;j+)Listji=memj;fi=flag;83.4 增加算法与比较增加 FIFO 算法该算法总是淘汰最先进入内存的页面，即选择内存中驻留时间最久的页面予以淘汰。该算法实现简单， 在本次课程设计中， 只需要将要访问的页面排成一个序列，然后判断当前访问页在物理块中是否存在，若在则标记为“* ”, 否则标记为“ ”，如果发生缺页，则先判断内存中是否有空旳物理块，有则得到空物理块的下标，将当前访问页插入到该物理块；没有则移除首物理块中的页面，即淘汰最先进入内存中的页面， 其余物理块中的页面元素下标减一，当前访问页插入到末物理块。如果标记为“”，则当前物理块中页面元素下标不变。分析比较FIFO 算法是先进先出，当当前内存中没有正要访问的页面时，置换出最先进来的页面。LRU 算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。先进先出 ( FIFO) 算法较易实现，比较适用于具有线性顺序特性的程序，而对其他特性的程序则效率不高。 缺页中断率为最佳算法的 23 倍；增加可用主存块的数量会导致更多的缺页，此算法还可能出现抖动现象异常。最近最久未被使用 ( LRU ) 算法的实现需要硬件支持，基于程序的局部性原理，所以适用用大多数程序， 此算实现必须维护一个特殊的队列页面淘汰队列。关键是确定页面最后访问以来所经历的时间。9四、程序测试4.1 运行结果及截图按 1 进入自定义进程数和物理块数。图 4-1用户自定义输入调用 FIFO 算法输出淘汰过程，计算页面访问命中率。图 4-2调用 FIFO 算法调用 LRU 算法输出淘汰过程，计算页面访问命中率。10图 4-3调用 LRU算法按 4 修改当前物理块的个数。图 4-4修改物理块数修改物理块数后，调用FIFO 算法输出。11图 4-5修改物理块数调用FIFO 算法修改物理块数后，调用LRU 算法输出。图 4-6修改物理块数调用LRU算法选择随机生成页面访问序列的方式。图 4-7随机生成页面访问序列12随机生成页面访问序列后，调用FIFO 算法输出。图 4-8调用 FIFO 算法随机生成页面访问序列后，调用LRU 算法输出。图 4-9调用 LRU算法修改物理块数后，调用LRU 算法输出淘汰过程。13图 4-10修改物理块数调用LRU算法4.2 思考题解答思考题（ 1）题目：设计一个界地址存储管理的模拟系统， 模拟界地址方式下存储区的分配和回收过程。提示：必须设置一个内存分配表， 按照分配表中有关信息实施存储区的分配，并不断根据存储区的分配和回收修改该表。 算法有首次匹配法， 循环首次匹配法和最佳匹配法等。 可用各种方法的比较来充实实习内容。 可使用碎片收集和复盖等技术。答：分配时，根据用户提供的作业大小，从第一个空闲块开始查找，将找到的第一个足够大的空闲块块分配给该作业，返回给用户该块始地址。 如果该块剩余部分小于特定阈值（本程序为2k), 将该块整体分配给此作业，将该块直接加入分配区链表， 若剩余块大于或等于阈值， 将分配块加入分配区链表，剩余部分作为新的空闲块 . 另：程序开始时已将0 到 20k 分配给操作系统。回收时，根据用户提供的作业的始地址，在分配区表查找，若找到该块，将其加入空闲区链表， 提示用户释放成功。 若新形成的空闲块与其前后的空闲块相连，合并空闲块形成更大的空闲块。显示，用户可随时选择查看内存分配状态图以及空闲区表与分配区表， 在分配或回收成功时，程序自动显示内存分配状态图、空闲区表与分配区表。思考题（ 2）题目：自行设计或选用一种较为完善的内存管理方法，并加以实现。提示：设计一个段页式管理的模拟程序或通过一个实际系统的消化和分析，编制一个程序来模拟该系统。14答：选择 1 分配内存， 输入内存名和占用空间大小即可分配内存， 显示的项目有进程名、起始地址和长度，已分配的内存分配情况会显示出来， ；空间分配满则显示“无空闲区” ；选择 2 回收内存，输入已分配的内存名称即可回收该内存；分配总空间大小为 128，若输入的进程大于该数，则显示“占用空间过大，分配失败”。具体如下所示：图 4-11 按键选择 1图 4-12内存分配情况15图 4-13 回收内存图 4-14分配内存失败16五、课程设计小结在本次操作系统课程设计中， 我们小组抽中的课设任务是请求页式存储管理中 LRU 算法的实现，由我担任小组长。在熟悉了课设任务和课设要求后，我为各个组员分配了任务， 思考题部分交给了组员， 而我则负责课设主要程序代码的编写，画程序流程图，以及协助完成课设所需的所有资料。在课堂上，我已经了解到， LRU 算法是发生在缺页中断时，由于内存中没有空的物理块存放当前访问的页面， 需要淘汰一个已在内存中的页面而采用的算法之一。 LRU 算法即最近最久未使用算法，每次淘汰的页面是相对于现在最久没有被访问的页面。参考关于 LRU 算法的题目，结合考试复习资料，我决定采用老师上课所讲的填表方式来输出 LRU 算法淘汰页面的过程。在设计程序时，我另外增加了 FIFO 算法，用以比较页面淘汰过程。为了提高代码的可重用性， 我把程序设计成菜单选择的样式， 总共五个菜单选项，分别是“ 1- 用户自定义输入”、“2- 先进先出算法 FIFO”、“3- 最近最少使用算法 LRU”、“4- 仅修改物理块数” 、“0- 退出程序”。需要说明的是，程序运行一开始，首先得执行一次菜单选项 1，用以初始化物理块数组中的页号，否则提示请选择菜单 1，并返回主菜单重新输入菜单选项。在设计输出页面淘汰过程时，我用一个页面序列数组， 用于存放产生的页面访问序列； 用缺页标记字符数组，用于输出当前访问页面是否缺页；一个二位字符数组，用于显示LRU 算法或 FIFO 算法淘汰页面的过程；一个存放被淘汰页面的字符数组，用于输出被淘汰的页面。在每种算法淘汰页面后， 输出采用该算法计算出的缺页率和页面访问命中率。在物理块数组中的页号初始化后，选择菜单4 修改内存中物理块数，然后可以选择调用哪种算法输出页面淘汰过程， 可以反复循环。在测试淘汰页面过程的代码时， 选择输入页面序列， 调用算法输出结果， 我对照事先填好的淘汰过程表，发现有的序列结果正确，有的不对，后来发现一个关键点，即空物理块的下标，修改了部分代码，终于使每种算法的淘汰过程输出正确。通过本次课程设计， 我重新复习了很多 C语言的知识，对于想要实现的功能可以很好的用代码来完成， 而且提高了自己的编程能力， 加强了自己的团队合作能力，同时，我对 LRU算法的了解也更加清晰明白了。17六、参考文献1 苏庆刚. 操作系统原理与应用教程.上海：上海交通大学出版社2 胡志刚 . 谭长庚等 . 计算机操作系统 . 中南大学出版社 . 20053 谭浩强 . C 程序设计（第四版） . 北京：清华大学出版社4 王旭阳，李睿 . 操作系统原理 . 北京：机械工业出版社， 20095 汤子瀛等 . 计算机操作系统 . 西安电子科技大学出版社181、请求页式存储管理中LRU 算法的实现#include #include #include #define p 30#define w 10int i,j,q,m,n,sum;char flag,fp,losep,pagep,memw,Listwp;void Init()/ 初始化函数sum=0;/计算缺页次数的变量，初始值为0for(int i=0;im;i+)memi= ;/ 初始时，内存中物理块为空for(i=0;im;i+)for(j=0;jn;j+)Listij= ;/初始时，用于显示页面淘汰过程的二维数组为空void FIFO()for(i=0;in;i+)/查看当前物理块， 看是否缺页并更新二维数组int low=-1;/ 非空物理块标志for(j=0;jm;j+)/ 判断当前物理块是否装满页面if(memj= )low=j;/ 得到第一个空物理块的下标break;losei= ;/初始化当前页面有效q=0;while(pagei!=memq)&(q!=m)/ 查询物理块中与当前访问页相同的页面下标q+;if(q=m)1flag=*;/ 缺页，则置标志flag 为 *elseflag= ;/不缺页if(flag=*)/物理块中没有当前访问页(如果有缺页 )if(low!=-1)/ 存在一个物理块为空memlow=pagei;/当前访问页直接插入到该物理块中else/当前物理块装满页面losei=mem0;/淘汰最先访问的页面for(j=0;jm-1;j+)memj=memj+1;/ 淘汰第一个物理块中的页面，其余页面下标减一memm-1=pagei;/ 最后一个物理块保存当前访问页面for(j=0;jm;j+)Listji=memj;/ 用当前物理块里的内容更新二维数组fi=flag;/ 更新标记当前访问页是否缺页的字符数组printf(nt-FIFO算法页面淘汰过程-nt);for(i=0;in;i+)printf(%c,pagei);printf(nt-nt);for(i=0;in;i+)if(fi=*)sum+;/累加缺页次数printf(%c,fi);printf(nt-nt);for(i=0;im;i+)for(j=0;jn;j+)printf(%c,Listij);/ 输出二维数组printf(nt);printf(-nt);for(i=0;in;i+)printf(%c,losei);printf(nt-n);2printf(nt其中* 代表缺页n);printf(nt被淘汰的页面依次为：);for(i=0;in;i+)if(losei!= )printf(%c,losei);printf(nt缺页次数是 : %d缺页率是 : %fn,sum,(double)sum/n);printf(ntFIFO算法的页面访问命中率是:%fn,1-(double)sum/n);void LRU()for(i=0;in;i+)/查页表，看是否缺页int low=-1;/物理块是否为空的标志for(j=0;jm;j+)if(memj= )/判断当前物理块是否有空的物理块low=j;/ 得到第一个空物理块的下标break;losei= ;/初始化当前页面有效q=0;while(pagei!=memq)&(q!=m)q+;if(q=m)flag=*;/ 缺页，则置标志flag 为 *elseflag= ;if(flag=*)if(low!=-1)/ 物理块中有空位memlow=pagei;elselosei=mem0;/淘汰最近最久未使用的页面for(j=0;jm-1;j+)/淘汰最先调入的页面调入当前访问的memj=memj+1;memm-1=pagei;else3if(low!=-1)for(j=q;jlow-1;j+)memj=memj+1;memlow-1=pagei;elsefor(j=q;jm-1;j+)memj=memj+1;memm-1=pagei;for(j=0;jm;j+)Listji=memj;fi=flag;printf(nt-LRU算法页面淘汰过程-nt);for(i=0;in;i+)printf(%c,pagei);printf(nt-nt);for(i=0;in;i+)if(fi=*)sum+;printf(%c,fi);printf(nt-nt);for(i=0;im;i+)for(j=0;jn;j+)printf(%c,Listij);printf(nt);printf(-nt);for(i=0;in;i+)printf(%c,losei);printf(nt-n);printf(nt其中* 代表缺页n);printf(nt被淘汰的页面依次为：);for(i=0;in;i+)4if(losei!= )printf(%c,losei);printf(nt缺页次数是 : %d缺页率是 : %fn,sum,(double)sum/n);printf(ntLRU算法的页面访问命中率是:%fn,1-(double)sum/n);void memu()printf(nnt*页面置换算法的模拟实现 *n);printf(tn);printf(t1-用户自定义输入 n);printf(tn);printf(t2-先进先出算法 FIFO n);printf(tn);printf(t3-最近最少使用算法 LRU n);printf(tn);printf(t4-仅修改物理块数 n);printf(tn);printf(t0-退出程序 n);printf(tn);printf(t请输入菜单项： );void main()system(color f0);int choice;/ 菜单选择int way;/ 选择页面序列产生方式int isexc=0;/菜单“ 1”未执行char pageno;/ 页号int flength,porder,store;while(1)memu();scanf(%d, &choice);switch(choice)case 1:flength=0;porder=0;store=0;printf(nt请输入访问串的长度（页数=30 ）： );5while(flength=0)scanf(%d,&n);if(n30)printf(nt 你输入的是 %d ,请确保访问串的长度 =30 ！nt 请再次输入访问串的长度： t,n);elseflength=1;printf(nt请选择页面访问序列生成方式（数字0- 手动输入 |数字1-随机生成） :t);while(porder=0)scanf(%d,&way);if(way=0)printf(nt请输入页面访问序列（数字0-9）:nt);for(i=0;i=0&pageno=9)pagei=pageno;continue;elsei-;continue;porder=1;else if(way=1)printf(nt随机产生的页面访问序列为:nt);srand(unsigned)time(NULL);for(i=0;in;i+)pagei=rand()%10+48;/数字字符转成字符型printf(%c,pagei);printf(n);porder=1;6elseprintf(nt请确保选择的数字为“0”或“ 1”！ nt 再次输入序列生成方式： t);porder=0;printf(nt请输入分配给进程的物理块数（=10 ）： t);while(store=0)scanf(%d,&m);if(m10)printf(nt你输入的是%d ,请确保物理块数=10 ！nt 再次输入物理块数： t,m);elsestore=1;isexc=1;/菜单“ 1”执行完成break;case 2:if(isexc=0)printf(nt请先选择菜单“1”创建页面访问序列和物理块数！n);break;Init();FIFO();break;case 3:if(isexc=0)printf(nt请先选择菜单“1”创建页面访问序列和物理块数！n);break;Init();LRU();break;case 4:if(isexc=0)7printf(nt请先选择菜单“1”创建页面访问序列和物理块数！n);break;store=0;printf(nt请输入要修改的物理块数：t);while(store=0)scanf(%d,&m);if(m10)printf(nt你输入的是%d ,请确保物理块数=10 ！nt 再次输入物理块数： t,m);elseprintf(nt内存中的物理块数修改成功！);store=1;break;case 0:exit(0);break;default:printf(nt选择菜单项输入错误，请重新输入!n);8
展开阅读全文