操作系统课程设计LRU算法的实现

1、上孝甩SHANGHAI DIANJI UNIVERSITY操作系统原理课程设计报告姓名：黄崧岳班级：BX1010学号：5扌旨导老师：苏庆冈I二一二年十二月十四日一、操作系统原理课程设计的目的与要求 11目的12要求1二、简述课程设计内容、主要功能和实现环境 11课程设计内容12主要功能13实现环境2三、任务的分析、设计、实现和讨论 21任务的分析22任务的设计与实现 34思考题的解答和讨论 10四、操作系统课程设计小结 14五、参考文献14附录14操作系统原理课程设计的目的与要求1目的近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI ）技术的发展，使存 储器的容量不断扩大，价格

2、大幅度下降。但从使用角度看，存储器的容量和成本总受到一定 的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法， 并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。2要求任务四采用最近最少使用页淘汰算法 （LRU）实现。为了比较真实地模拟存储管理，可预 先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。二、简述课程设计内容、主要功能和实现环境1课程设计内容最近最少使用页淘汰算法（LRU），这

3、是一种经常使用的方法。有各种不同的实施方案， 这里采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使用的页，总 是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。2主要功能（1）菜单函数int menu_select（）:用于显示主菜单，可在其中选择1.自定义进程数和块数；2显示显示用户自定义的进程数和块数；3.进行LRU算法4.退出程序。（2）最近最久未使用算法函数 void LRU（）:此函数是将随机产生的页面进行最近未使用 便置换的函数，也是本

4、程序的主要部分。（3）自定义进程数和块数函数 void Zidingyi（）:此函数是主菜单中的第一个选项，即用户可以自定义所需的进程数和块数。（4）显示用户自定义的进程数和块数函数void ShowCustomer（）:此函数是用于显示用户自定义的进程数和块数的情况。（5）修改块数函数void Xiugaikuaishu（）:此函数是在进行 LRU算法后，可以在原来的进程数的基础上，修改块数并重新生成一组LRU算法的过程。（6）显示每次换页后的结果函数void ShowResult（）:此函数是显示在LRU算法的执行过程中每次换页的情况。（7）显示一定不用换页的函数 void ShowNot

5、（）:此函数是显示最近使用过的页面，即不用换页的结果。3实现环境本次课程设计结合算法的特点，采用Windows操作系统平台。开发工具为MicrosoftVisual C+6.0。三、任务的分析、设计、实现和讨论1任务的分析本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。 另外也考虑到改变页面大小和实际存储器容量对计算结果的 影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。本程序是按下述原则生成指令序列的：（1）50%的指令是顺序执行的。（2）25%的指令均匀散布在前地址部分。（3）25%的指令均匀散布在后地址部分。示例中选用

6、最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU ）计算页面命中 率。公式为命中率=1 -页面失效次数 页地址流长度3#假定虚存容量为32K，页面尺寸从1K至8K，实存容量从4页至32页。#2任务的设计与实现2.1 ma in()函数流程图:42.2主菜单流程图:inm;11printfl入 你0renrrnlji),2.3 LRU函数流程图:62.4 Zidingyi()函数流程图:inti;i-0piiges:100;岸 whim);2.5 ShowCustomer(函数流程图:o("cm；i-0printtVtd *bpagesi汁十72.6 ShowNot()函数流程

7、图:82.7 ShowResult()函数流程图:9#pr'Tlttr1 %d",Fu7hui；i+pTinttrn"：#3操作过程和结果分析按1进入自定义进程数和块数请求页式存储管理中LRU譚法的实现12 3 4利义 矍 程自法 进UMTT 义用RUEX 定一凭 自显#输入你的选择#按2显示进程数，块数和随机分配页号10覽 JOCKXHHBEXX JOCKKJOC” KUH WBHHHHOCJtK ICX)0000( JOC)1 W lOOCK 100(童 Wit JCK见不:进程斂为：20页号分别为： 4167 34 B 6924 ?B 5862 B4 

8、3;45 Bl 27 G1 VI 95422736町用物理块数为，1曲任意键 可返回 主菜.单按3实现LRU算法，输出命中率11#LRU算法结果显示;9-454259-420 52 80:414141078781 188:27换为：为为：一 書备詈一 总罢一 s页面页一 页置4叩缺一#按1修改块数，按2遞回主菜单Wes1, No2#按1修改物理块数，重新实现 LRU算法并输出命中率27&191958178显示:34417ZT别为27町用物理块数为:按任意键可返回王菜单UW算袪结果显黃:454S4561616161424241412.b81813i12EZ2l2l0B 0 0 17fhj

9、 为为；为为.24总忌率 95换页面页 置畳命缺-按1修改块数按2返回主菜单Wes1, No2 2_请求页式存储管理中LRU算法的实现按4退出程序12 3 4数 块和义 墊疋 程自法 进fin 义用RUEK 定不L 自显12#输入你的选择= 4 谢谢使用算迭？Bye ByeA-APress any keu to continueFIFO算法该算法总是淘汰最先进入内存的页面，既选择内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需要把一个进程已调入内存的页面，按照先后测序链接成一个队列，并设置一个指针，使他总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被

10、访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。这里，我们用下面的例子，采用FIFO算法进行页面置换。当进程第一次访问页面 2时，将把第七页换出，因为它是最先被调入内存的；在第一次范文页面3时，又将把第零页换出，因为他在现有的2，0，1三个页面中是最老的页。由下图可以看出，利用 FIFO算法时进行了十二次页面置换，比最佳置换算法正好多一倍。结果分析一一两种算法的比较：先进先出（FIFO）算法较易实现，比较适用于具有线性顺序特性的程序，而对其他特性的程序 则效率不高。缺页中断率为最佳算法的23倍；增加可用主存块的数量会导致更多的缺页，此算法还可能出现抖动

11、现象异常。最近最久未被使用（LRU）算法的实现需要硬件支持，基于程序的局部性原理，所以适用用大 多数程序，此算实现必须维护一个特殊的队列一一页面淘汰队列。关键是确定页面最后访问以来 所经历的时间。4思考题的解答和讨论（1 ）设计一个界地址存储管理的模拟系统，模拟界地址方式下存储区的分配和回收过程。提示：必须设置一个内存分配表， 按照分配表中有关信息实施存储区的分配，并不断根据存储区的分配和回收修改该表。算法有首次匹配法，循环首次匹配法和最佳匹配法等。可用各种方法的比较来充实实习内容。可使用碎片收集和复盖等技术。答：开始（1 ）数据结构及说明本程序为可变分区管理方式主存分配回收模拟程序，采用首次

12、适应策略。主要数据结构：空闲区链表FBC，分配区链表ABC :表中记录块的起始地址和大小，块按照始地址大小从小到大排列。（2）功能实现 分配时，根据用户提供的作业大小，从第一个空闲块开始查找，将找到的第一个足够大的空闲块块分配给该作业，返回给用户该块始地址。如果该块剩余部分小于特定阈值（本程序为2k）,将该块整体分配给此作业，将该块直接加入分配区链表，若剩余块大于或等于阈值，将分配块加入分配区链表，剩余部分作为新的空闲块另：程序开始时已将0到20k分配给操作系统。 回收时，根据用户提供的作业的始地址，在分配区表查找，若找到该块，将其加入空闲区链表，提示用户释放成功。 若新形成的空闲块与其前后的

13、空闲块相连，合并空闲块形成更大的空闲块。 显示，用户可随时选择查看内存分配状态图以及空闲区表与分配区表，在分配或回收成功时，程序自动显示内存分配状态图、空闲区表与分配区表。编制一个程(2)自行设计或选用一种较为完善的内存管理方法，并加以实现。 提示：设计一个段页式管理的模拟程序或通过一个实际系统的消化和分析, 序来模拟该系统。答：分配总空间大小为128,若输入的进程大于该数，则显示“占用空间过大，分配失败”若分配的进程大小为 0,则显示“进程空间大小错误”1603070b闲区情况： 无空闲区了.长.g *C: Docu*ent s and Sett ingsAdB.in.ist rat orB

14、y DocuAent sDebugCppl. exe Sb-内名名名Jt:a=缠粗 长鼎始 己己-己- - 0 tSI - -Ir:! -!r 况:7分； 第存:a:b 区地问名名 空起进进进：30（：40：58睛按键选搖：1牺输入进翟名和占用空I可大小:CC58:址址址 乩也也也 壇始始 己己己己 酉_已一已_已 分a b C 存:a:b:c选择1分配内存，输入内存名和占用空间大小即可分配内存，显示的项目有进程名、起始地址和长度，已分配的内存分配情况会显示出来，如上图。空间分配满则显示“无空闲区” *C: Docu>ent s and Sett ingsAdB.inist rat or

15、By DocuAent sDebugCppl. exe*CC58空闲区情况: 氏空闲区了.內名名名进进进进：0aa起.：30 f ：40bb起始地址：30起始地址:西长度汚&cc熒黯爲和程名: 迸翟内存回收完毕.ccg=5a=缠粗 彼鼎始 卡 己己-己一 - 酉走 况:0分；择 舟存:a:b选 区地内名名 键 i K 按 空起逬进逬 请选择2回收内存，输入已分配的内存名称即可回收该内存，并显示剩余的已分配内存17四、操作系统课程设计小结页面置换算法理解比较容易，这次根据学号要求实现的是 LRU算法的实现。分配到我的是两道思考题，其实这两道思考题的算法是差不多的，所以第一 题我没有去编写

16、只是写出了大概的思路和算法框图。其实这两种算法的程序编写 比较容易，虽然不全是自己编写的，一部分是参考的网上的例题，但是通过对每 一语句的理解，自己弄懂了整个程序的执行原理。 但是，在编写过程中自己还是 遇到了一些问题。最大的一个问题就是两个算法的正确实现，在程序的编写时，两个程序是分 开进行编写的，分别执行起来没有什么问题，但是把两个程序融合在一起后，却 出现了问题，即在执行完成一个算法后再执行另外一个算法时， 开始的数据是紧 接着上次算法结果的数据进行实验的。 这个问题困扰了我好长时间，直到现在还 没有很好的解决掉，程序只能分别执行一次，如果再进行执行的话，就会出现问 题。自己的编程技术不

17、好，程序编的也很繁琐，但是基本的要求已经实现了，希 望这次的实验是自己动手的一个开始，自己应该更加努力，再接再厉。五、参考文献【1】 计算机操作系统 【2】 计算机操作系统 【3】 操作系统教程孙雅如等编著西安电子科技大学2003（第2版）吴企渊 等编著清华大学出版社 2003 徐甲同编著西安电子科技大学出版社.2001附录LRU算法实现#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <time.h>#defi ne Maxsize 300 void Xiugaikuaishu(); void In itio

18、 n();void Zidi ngyi(); void ShowCustomer();void ShowResult();void ShowNot();void LRU();int menu _select();int pageNum = 0;/ 页面数int pagesMaxsize; 存储页号int FuzhuMaxsize; 辅助数组int TimeMaxsize;记录页在内存中的时间int block;/记录物理块数int Fz;辅助变量int mai n()for(;) /*循环无限次*/switch(me nu _select()case 1: Zidi ngyi();break;

19、case 2: ShowCustomer();break;case 3: LRU();break;case 4:printf(”谢谢使用LRU算法!n");printf(” Bye ByeA-An");exit(0);/*如菜单返回值为13则程序结束*/return 0; int menu _select()int n;printf(”i1n");prin tf("|请求页式存储管理中 LRU算法的实现| n ”);prin tf("| n ”);prin tf("|1.自定义进程数和块数| n");prin tf(&quo

20、t;|2.显示用户自定义| n");prin tf("|3.LRU算法| n");19prin tf("|4.EXIT1 n ”);prin tf("|1 n ”);prin tf("|1 n ”);printf(”|1n");doprintf("nttt 输入你的选择(14):");scan f("%d", &n);while(n< 1|n>4); /*如果选择项不在13之间则重输*/ |如果一个以上为真,真，二者都为假时，结果为假return(n); /*返回选

21、择项，主函数根据该数调用相应的函数*/则结果为void Zidi ngyi()II自定义进程数和块数int i;system("cls");printf(” *n");printf(”页式储存管理一LRU算法printf(” *n");printf(” 自定义进程数和块数 n");prin tf("n");printf("请输入进程数：”)；scan f("%d",&pageNum);for(i = 0 ; i < pageNum ; i+)pagesi = rand()%100;

22、 II初始化页号，初始值在0-100之内 getchar();printf("请输入块数：”)；scan f("%d",&block );getchar();自定义进程数和块数n");void LRU()II最近最久未使用算法 int i,j;int WithOutPages = 0;II 记录缺页数printf(" *printf(”LRU 算法结果显示：n");prin tf("n");ShowNot();for(i = Fz ; i < pageNum; i+)21int key = 0;for

23、(j = 0 ; j < block ; j+)判断该页是否在物理块中 if(Fuzhuj = pagesi)key = 1;Timej = i;更新时间break; if(key = 0)/若该页不在内存中WithOutPages+;int min = Time0;int flag = 0;for(j = 1 ; j < block ; j+)if(min > Timej)min = Timej;/找到最久的页面 flag = j;Timeflag = i;/ 记录时间Fuzhuflag = pagesi;ShowResult();printf("置换次数为：d

24、n”,WithOutPages);printf("页面总数为：%d n”,pageNum);double re = (double)WithOutPages)/(double)pageNum); printf("置换率为：%.2lfn",re);printf("命中率为：.2lfn",1-re);printf("缺页次数为：%d n”,WithOutPages+block);printf("页面总数为：%d n”,pageNum);re = (double)(WithOutPages+block)/(double)pageN

25、um); printf("缺页率为：%.2lfn",re);22printf("*printf(”按1修改块数，按2返回主菜单n");#prin tf("n");printf(”Yes-1，No-2 n");in t la;sea nf("%d",&la);if(la=1)Xiugaikuaishu();elseprintf(” *n “);printf("system("cls");void ShowResult()显示每次换页后的结果int i;for(i = 0

26、 ; i < block ; i+)printf(" %d",Fuzhui);prin tf("n"); void Xiugaikuaishu()system("cls");printf(" *printf(”请输入需要修改块的数目 ：n ”);prin tf("");int a;scan f("%d", &a);block = a;ShowCustomer();显示自定义页面信息LRU();void ShowCustomer()显示用户自定义的进程数和块数 system

27、("cls");int i;printf(" *printf("显示:n");printf("进程数为：%dn",pageNum); printf("页号分别为：”)；for(i = 0 ; i < pageNum ; i+)prin tf("%d”,pagesi);prin tf("n");printf("可用物理块数为：%dn",block);printf(" *printf(” 按任意键可返回主菜单 n");getchar();voi

28、d ShowNot()显示一定不用换页的部分 Fz = block;int i,j,k=O,key = 0;for(i = 0 ; i < Fz ; i+)int flag = 0;for(j = 0 ; j <= i-1 ; j+)if(Fuzhuj = pagesi) Timej = i;flag = 1;Fz = Fz+1; key+; if(flag = 0) Timek = i;Fuzhuk = pagesi;k+;for(j = 0 ; j <= i-key ; j+)prin tf("%d",Fuzhuj); prin tf("n&

29、quot;);思考题2:内存管理小程序#in clude <iostream.h>#in clude <stdio.h>#in elude <stri ng.h> struct programchar n ame30;long start;long len gth;struct program *n ext;struct spacelong start;long len gth;struct space *n ext;void creat();void allot();void back();void callback(program *r);void so

30、rt(space *L);void sort(program *S);void display(space *L);void display(program *S);space *L; program *S;void creat()L=new space;space *p=new space; p->start=0;p->le ngth=128;p-> next=NULL;L_>n ext=p;S=new program;S-> next=NULL;void allot()program *q;q=new program;cout<<"请输入

31、进程名和占用空间大小:"<<endl;cin»q_>n ame»q->le ngth;if(q->le ngth<=0)cout<<"进程空间大小错误."<<endl;delete q;return;space *p,*r;P=L;r=p;while(p-> next!=NULL&&p-> next->le ngth<q->le ngth)r=p;p=p->n ext;if(p-> next=NULL)cout<<&

32、quot;占用空间过大，分配失败"<<endl;delete q;return;elseq->start=p->n ext->start;q->n ext=S->n ext;S_>n ext=q;p-> next->le ngth-=q->le ngth;if(p->n ext->le ngth!=O)p_>n ext->start+=q->le ngth;elseif(p-> next-next!=NULL)p->n ext=p->n ext- >n ext;el

33、ser->n ext=NULL;delete p->n ext;display(L);display(S);void back()char n ame30;cout<<"输入要回收的进程名："cin»n ame;program *p;p=S;while(p-> next!=NULL)if(strcmp(p->n ext- >n ame, n ame)=0)callback(p);return;p=p->n ext;if(p-> next=NULL)cout<<"此进程不存在，内存回收失败&

34、quot;<<endl;void callback(program *t)program *r;r=t- >n ext;space *p,*q;long n;n=r->le ngth;if(L-> next=NULL)space *w=new space;w->start=0;w->le ngth=n;w-> next=NULL;L->n ext=w;t->n ext=r- >n ext;delete r;cout<<"此进程内存回收完毕."<<endl;27display(L);di

35、splay(S);return;p=L->n ext;while(p!=NULL&&p->start<r->start)q=p;p=p->n ext;上下均空if(q->start+q->le ngth=r->start )&&( r->start+ n=p->start) /q_>n ext=p->n ext;q->le ngth=q_>le ngth+p_>le ngth+n;t->n ext=r- >n ext;delete r;else if(r->

36、;start+ n=p->start) / 下邻空p->start-=n;p->le ngth+=n;t->n ext=r- >n ext;delete r;else if(q->start+q->le ngth=r->start)q->le ngth+=n;t->n ext=r- >n ext;delete r;elsespace *sp=new space;sp->start=r->start;sp->le ngth=n;sp->n ext=L->n ext;L->n ext=sp;t-&

37、gt;n ext=r- >n ext;delete r;cout<<"此进程内存回收完毕."<<endl;display(L);display(S);void display(space *L)sort(L);space *p=L->n ext;cout<<e ndl<<"空闲区情况："<<e ndl;if(p=NULL) cout<<"无空闲区了 ."<<endl; return;while(p!=NULL)cout<<"起始地址:"<<p->start<<"长度:"<<p->length<<endl;p=p->n ext;void display(program *S)sort(S);program *p=S->n ext;cout<<e ndl<