内存管理(操作系统)操作系统课程设计

1、附件2：封面（打印时清除本行内容。只许填空，不许变动结构）河南城建学院操作系统课程设计说明书设计题目： 存储管理 专 业： 计算机科学与技术 指导教师： 邵国金 班 级： 0814121 学 号： 081412112 姓 名： 同 组 人： 计算机科学与工程学院2015 年 1 月 9日前言本课程设计是编制页面置换算法FIFO、LRU、LFU、NUR和OPT的模拟程序,并模拟其在内存的分配过程。同时根据页面走向，分别采用FIFO、LRU、LFU、NUR和OPT算法进行页面置换，统计命中率；同时系统可以随意设置当前分配给作业的物理块数。 系统运行时，任意输入一个页面访问序列，可以设定不同的页面置

2、换算法和物理块数，输出其页面淘汰的情况，计算其缺页次数和缺页率。系统结束后，比较同一个页面访问序列，可以得出在不同的页面置换算法和物理块数的情况下，其产生的缺页次数和缺页率。 使用FIFO算法，由于测试数据相同的页面比较少，所以采用FIFO算法时，需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。使用LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU算法介于FIFO和OPT之间。通过系统模拟得出，OPT算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于OPT算法在实际上难于实现，所以实际应用一般用LRU

3、算法。 本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。该程序能按要求随机确定内存大小，随机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。 目录一系统环境11.1硬件环境11.2软件环境1二设计目的2三总体设计33.1程序设计组成框图33.2流程图4四详细设计74.1模块功能说明74.11数据结构74.12函数定义84.13变量定义84.2算法分析8五

4、调试与测试105.1调试方法105.11使用Vi编译程序105.12运行程序125.2结果分析与讨论135.3测试问题及采取措施13六源程序14七心得体会23八参考文献24一系统环境1.1硬件环境PC机一台，0.99G内存，2.0GHZ主频1.2软件环境设计和实验将Windows环境下，gcc和虚拟机软件VMWare2 设计目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。要求：(1)通过随机数产生一个指令序列，共320条指令。指令的地址按下

5、述原则生成：50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分。具体的实施方法是：在0，319的指令地址之间随机选取一起点m；顺序执行一条指令，即执行地址为m+l的指令；在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m；顺序执行一条指令，其地址为m+1；在后地址m+2，319中随机选取一条指令并执行；重复上述步骤，直到执行320次指令。(2)将指令序列变换成为页地址流。设:页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令

6、为第0页(对应虚存地址为0，9)；第10条第19条指令为第1页(对应虚存地址为10，19)； 第310条第319条指令为第31页(对应虚存地址为310，319)。按以上方式，用户指令可组成32页。(3)计算并输出下述各种算法在不同内存容量下的命中率（要为以下各种算法定义数据结构）。先进先出的算法(FIFO)；最近最少使用算法(LRU)；最近最不经常使用算法(NUR/NRU/CLOCK)。命中率=1-页面失效次数/页地址流长度在本设计中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。(4)关于随机数产生办法，Linux/UNIX系统提供函数srand（）

7、和rand（），分别进行初始化和产生随机数。例如:srand()语句可初始化一个随机数：a0=10*rand()/32767*319+1，a1=10*rand()/32767*a0； 语句可用来产生a0、a1、中的随机数。三总体设计3.1程序设计组成框图系统分为4个子模块：初始化模块，FIFO、LRU、LFU、NUR和OPT的五个算法模块。初始化模块：initialize( )初始化函数，给每个相关的页面赋值。FIFO算法模块：计算使用FIFO算法时的命中率。LRU算法模块：计算使用LRU算法时的命中率。LFU算法模块：计算使用OPT算法时的命中率。NUR算法模块：计算使用LFU算法时的命中率

8、。OPT算法模块：计算使用NUR算法时的命中率。Main()FIFO算法模块LFU算法模块NUR算法模块OPT算法模块LRU算法模块Initialize()初始化函数3.2流程图LFU NUR OPT四详细设计本实验的程序设计基本上按照实验内容进行。即首先用srand()和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的命中率。相关定义如下:4.1模块功能说明4.11数据结构(l)页面类型typedef structintpn,pfn,count,time; pl_type;其中pn为页号,pfn为面号,count为个周期内访问该页面次数ti

9、me为访问时间。(2)页面控制结构pfc_structintpn,pfn;struct pfc_struct*next;typedefstruct pfc_struct pfc_type;pfc_typepfcxy,*free_head,*busy_head;pfc_type*busy_tail;其中：pfcxy定义用户进程虚页控制结构,*free_head为空页面头的指针,*busy_head为忙页面头的指针,*busy_tail为忙页面尾的指针。4.12函数定义(1)void initialize():初始化函数,给每个相关的页面赋值。(2)void FIFO():计算使用FIFO算法时的

10、命中率。(3)void LRU():计算使用LRU算法时的命中率。(4)void OPT():计算使用OPT算法时的命中率。(5)void LFU():计算使用LFU算法时的命中率。(6)void NUR():计算使用NUR算法时的命中率。4.13变量定义(1)int azllc;指令流数据组。(2)int pagezllc;每条指令所属页号。(3)int offsetzllc;每页装入10条指令后取模运算页号偏移值。(4)int pf:用户进程的内存页面数。(5)int zhihuan:页面失效次数。4.2算法分析先进先出算法，即FIFO算法（First-In First-Out algor

11、ithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主储存器中页面调度情况的历史信息，但是没有反应程序的局部性。因为最先调入主存的页面，很有可能是经常使用的页面。最近最少使用算法，即LFU（Least Frequently used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然这是一种非常合理的算法，因为到目前为止最少使用的页面，和可能也是将来最少访问的页面。该算法即充分利用了主存中吗调度的历史信息，又正确反映了程序的局部性。但是这种算法实现起来非常的困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每

12、个计数器定时计数。在选择被替换页面时，要从所有的计数器中选择一个计数值最大的计数器。因此，通常使用如下一种简单的方法。最久没有使用算法。即LRU(Least Recently Used Algorithm)。这种算法把近期最久没有被访问的页面作为被替换的页面。它把LFU算法中要记录数量上的多与少简化成判断有于无，因此实现起来比较容易。NUR算法在需要淘汰一页时，从哪些最近一个时期内未被访问的页面中任选一页淘汰。只要在页面中增加一个访问位即可实现。当某页被访问时，访问位置1.否则，访问位置0.系统周期性第对所有的引用位清零。当须淘汰一页时从那些访问位为0 的页中选择一页进行淘汰。如果引用位全为1

13、或0，NRU算法退化为FIFO算法。最优替换算法，即OPT(Optimal Replacement Algorithm).s上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。当然这种假设不总是正确的。最好的算法是选择将来醉酒不被访问的页面作为被替换的页面，这种算法的命中率是最高的，它就是最有替换算法。要实现OPT算法，唯一的办法就是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找到药被替换的页面。显然这样做是不现实的。 因此OPT算法只是一种理想化的算法，然而它也是一

14、种很用的算法。实际上，经常把这种算法作为评价其他页面替换算法好坏的标准。在其他条件相同的情况下，哪一种算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。五调试与测试5.1调试方法5.11使用Vi编译程序（1） 打开VMware、选中Red Hat Enterprise Linux、查看属性、选项、共享文件夹添加（2） 查看root的主目录mnthgfszhengzhengjingjing使用vi打开5.12运行程序5.2结果分析与讨论 从上述结果可知,在内存页面数较少(45页面)时,5种算法的命中率差别不大,都是50%左右。在内存页面为725个页面之间时,5种算法的访内命中

15、率大致在52%至87%之间变化。但是,FIFO算法与0PT算法之间的差别一般在610个百分点左右。在内存页面为2532个页面时,由于用户进程的所有指令基本上都已装入内存,从而命中率已较大。从而算法之间的差别不大。 比较上述5种算法,以OPT算法的命中率最高,NUR算法次之,再就是LFU算LRU算法,其次是FIF0算法。5.3测试问题及采取措施 本次课程设计中我们遇到的问题是，一开始没有弄清楚rand和sand函数的使用方法，以至于运行时的到的结果与实际算起来的不相符，后来查阅资料，上网浏览搜索相关信息后，终于弄明白了是怎么回事。 函数rand()是真正的随机数生成器，而srand()会设置供r

16、and()使用的随机数种子。如果你在第一次调用rand()之前没有调用srand()，那么系统会为你自动调用srand()。而使用同种子相同的数调用 srand()会导致相同的随机数序列被生成。 srand(unsigned)time(NULL)则使用系统定时/计数器的值做为随机种子。每个种子对应一组根据算法预先生成的随机数，所以，在相同的平台环境下，不同时间产生的随机数会是不同的，相应的，若将srand（unsigned）time(NULL)改为srand(TP)（TP为任一常量），则无论何时运行、运行多少次得到的“随机数”都会是一组固定的序列，因此srand生成的随机数是伪随机数。六源程序

17、#include<stdlib.h>#include<stdio.h>#include<time.h>#define TRUE 1#define FALSE 0#define INVALID -1#define zllc 320 /指令流长#define xy 32 /虚页长#define clear 50 /清零周期typedef struct /页面结构int pn;/页号int pfn;/页面框架号int count; /计数器int time;/时间pc;pc plxy;/页面线性结构typedef struct pfc_struct/页面控制结构，

18、调度算法的控制结构int pn;int pfn;struct pfc_struct *next;pfc_type;pfc_type pfcxy,*free_head,*busy_head,*busy_tail;int zhihuan,azllc;/a 为指令序列int pagezllc,offsetzllc;/地址信息int initialize(int);/初始化模块int FIFO(int);/FIFO调度算法int LRU(int);/LRU调度算法int LFU(int);/LFU调度算法int NUR(int);/NUR调度算法int OPT(int);/OPT调度算法/*主函数*/

19、int main()int s,i;srand(unsigned)time(NULL);s = rand()%320;for(i=0;i<zllc;i += 4)if(s<0|s>319)printf("When i = %d,Error,s=%d",i,s);exit(0);ai = s;ai+1 = ai+1;ai+2 = rand()%(ai+1+1);ai+3 = ai+2 + 1;s = rand()%(319-ai+3) +ai+3+1;if(ai+2>318|s>319)printf("a%d+2,a number wh

20、ich is:%d and s = %dn",i,ai+2,s);for(i=0;i<zllc;i+)/将指令序列变换为页地址流pagei = ai/10;offseti = ai%10;for(i=4;i<=32;i+)printf("%2d page frames:t",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return 0;/*初始化相关的数据结构，pf表示内存的块数*/int initialize(int pf)int i;zhihuan = 0;for(i=0;i<xy;i+)pli.pn = i

21、;pli.pfn = INVALID;/质页面控制结构中的页号，页面为空pli.count = 0;/页面控制结构中访问次数pli.time = -1;/访问时间for(i=0;i<pf-1;i+)/建立pfci-1与pfci之间的联系pfci.next = &pfci+1;pfci.pfn = i;pfcpf-1.next = NULL;pfcpf-1.pfn = pf-1;free_head = &pfc0;/空页面队列的头指针为pfc0return 0;/*先进先出算法，pf为用户进程的内存页面数*/int FIFO(int pf)int i;pfc_type *p

22、;/中间变量initialize(pf);/初始化数据结构busy_head = busy_tail = NULL;/忙页面头队列，为队列链接for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/页面失效zhihuan+;/失效次数if(free_head = NULL)/无空闲页面p = busy_head->next;/保存忙页面的下一个页面plbusy_head->pn.pfn = INVALID;/把这个页面换出，更新它的数据成员free_head = busy_head;/释放忙页面队列的第一个页面free_head->nex

23、t = NULL;/表明此页面是空的组后一面busy_head = p;/更新页面的头队列指针p = free_head->next;free_head->pn = pagei;plpagei.pfn = free_head->pfn;free_head->next = NULL;/使busy的尾为空if(busy_tail = NULL)busy_tail = busy_head = free_head;else/把刚刚换进来的接在busy_tail的后面busy_tail->next = free_head;busy_tail = free_head;free

24、_head = p;/下一个空页面printf("FIFO:%6.4f|",1-(float)zhihuan/320);return 0;/*最近最久未使用算法*/int LRU(int pf)int min,minj,i,j,present_time;/minj为最小值下标initialize(pf);present_time=0;for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/页面失效zhihuan+;if(free_head = NULL)/无空闲页面min = 32767;/设置最大值for(j=0;j<xy;j+

25、)/找出time最下值if(min>plj.time&&plj.pfn!=INVALID)min = plj.time;minj = j;free_head = &pfcplminj.pfn;/腾出一个单元plminj.pfn = INVALID;plminj.time = 0;free_head->next= NULL;plpagei.pfn = free_head->pfn;/有空闲页面改为有效plpagei.time =present_time;free_head = free_head->next;/减少一个free页面elseplpag

26、ei.time = present_time;/命中则增加该页面的访问次数present_time+;printf("LRU:%6.4f|",1-(float)zhihuan/320);return 0;/*最近未使用算法*/int NUR(int pf)int i,j,dp,cont_flag,old_dp;/这个算法用count用于访问位initialize(pf);dp = 0;for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/页面失效zhihuan+;if(free_head = NULL)/无空闲页cont_flag =

27、 TRUE;old_dp = dp;while(cont_flag)/找到一访问位count为0的页面if(pldp.count = 0 && pldp.pfn != INVALID)cont_flag = FALSE;else/下一个页面pldp.count = 0;dp+;if(dp=xy)/32个页面找一遍，开始新的循环dp=0;free_head = &pfcpldp.pfn;pldp.pfn = INVALID;free_head->next = NULL;plpagei.pfn = free_head->pfn;plpagei.count = 1

28、;free_head->pn = pagei;free_head = free_head->next;elseplpagei.count = 1;if(i%clear = 0)for(j=0;j<xy;j+)plj.count = 0;printf("NUR:%6.4f|",1-(float)zhihuan/320);return 0;/*最少访问页面算法*/int LFU(int pf)int i,j,min,minpage;initialize(pf);for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/页面失

29、效zhihuan+;if(free_head = NULL)/无空闲页面min = 32767;/获取count的使用频率最小的内存for(j=0;j<xy;j+)if(min>plj.count&&plj.pfn!=INVALID)min = plj.count;minpage=j;free_head = &pfcplminpage.pfn;plminpage.pfn = INVALID;plminpage.count=0;free_head->next=NULL;plpagei.pfn = free_head->pfn;plpagei.cou

30、nt+;free_head = free_head->next;/减少一个free页面elseplpagei.count = plpagei.count+1;printf("LFU:%6.4f",1-(float)zhihuan/320);return 0;/*最佳置换算法*/int OPT(int pf)int i,j,k,l,max,maxpage;initialize(pf);for(i = 0; i < zllc; i+)if(plpagei.pfn = INVALID)/页面失效 zhihuan+;max = maxpage = 0;if(free_head = NULL)/无页面空闲for(j = 0; j < pf; j+)l = 1;for(k = i + 1; k <