操作系统存储管理实验报告

1、下载可编辑北京邮电大学操作系统实验实验报告实验日期 ： 2010-12-20实验名称 ：存储管理一、实验目的2二、实验内容3三、实验分析3对于伙伴算法3对于虚拟存储区和内存工作区的不同算法3四、编程实现4伙伴算法4 原理4 伙伴的概念4 内存的释放4 位图法4 伪代码5 运行结果演示6最佳置换算法6 基本思想7 伪代码实现7 运行结果演示7先进先出法（ Fisrt In First Out）7.专业 .整理 .下载可编辑 基本思想7 伪代码实现8 运行结果演示8 最近最久未使用（ Least Recently Used）8 基本思想8 伪代码实现9 运行结果演示9最不经常使用法（ Least

2、Frequently Used）9 基本思想9 伪代码实现9 运行结果演示10 最近未使用法（ No Used Recently）10 基本思想10 伪代码实现10 运行结果演示11五、各种算法运行综合比较11六、实验心得12七、程序源代码13伙伴算法14最佳置换算法23先进先出法27 最近最久未使用30最不经常使用法34最近未使用法37一、实验目的.专业 .整理 .下载可编辑通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程 ，并比较它们的效率。二、实验内容实现一个内存管理的伙伴算

3、法，实现内存块申请时的分配和释放后的回收。设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1) 最佳置换算法 （Optimal ）2) 先进先出法 （ Fisrt In First Out）3) 最近最久未使用（ Least Recently Used）4) 最不经常使用法（ Least Frequently Used）5) 最近未使用法（No Used Recently）其中 ，命中率 页面失效次数页地址流长度 。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。三、实验分析对于伙伴算法，用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。

4、对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。对于虚拟存储区和内存工作区的不同算法，其中主要的流程：首先用 srand( ) 和 rand( )函数定义和产生指令序列 ，然后将指令序列变换成相应的页地址流 ，并针对不同的算法计算出相应的命中率 。实验可先从一个具体的例子出发。（ 1）通过随机数产生一个指令序列，共 320 条指令 。 指令的地址按下述原则生成：A： 50% 的指令是顺序执行的B： 25% 的指令是均匀分布在前地址部分C： 25% 的指令是均匀分布在后地址部分具体的实施方法是：A：在 0， 319 的指令地址之间随机选取一起点mB：顺序执行一条指令，

5、即执行地址为m+1的指令C：在前地址 0,m+1 中随机选取一条指令并执行，该指令的地址为mD：顺序执行一条指令，其地址为m +1E：在后地址 m +2 319，中随机选取一条指令并执行.专业 .整理 .下载可编辑F：重复步骤A-E，直到 320 次指令（ 2 ）将指令序列变换为页地址流设：页面大小为 1K；用户内存容量4页到 32页；用户虚存容量为32K 。在用户虚存中 ，按每 K 存放 10 条指令排列虚存地址 ，即 320 条指令在虚存中的存放方式为 ：第 0 条 -第 9 条指令为第 0 页（对应虚存地址为 0 ，9 ）第 10 条 -第 19 条指令为第 1 页（对应虚存地址为 10

6、 ， 19 ）第 310 条 - 第 319 条指令为第 31 页（对应虚存地址为 310 ， 319 ）按以上方式 ，用户指令可组成 32 页 。四、编程实现伙伴算法原理 ：伙伴算法把所有的空闲页面分为10 个块组 ，每组中块的大小是2 的幂次方个页面，例如 ，第 0 组中块的大小都为 2 0（ 1 个页面 ）， 第 1 组中块的大小为都为21（ 2 个页面）， 第 9 组中块的大小都为29（ 512 个页面）。 也就是说 ，每一组中块的大小是相同的，且这同样大小的块形成一个链表。 伙伴的概念 ， 满足以下三个条件的称为伙伴：(1) 两个块大小相同(2) 两个块地址连续(3) 两个块必须是从

7、同一个大块中分离出来的。内存的释放 ，是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块 ，就直接把要释放的块挂入链表头；如果有 ，则从链表中摘下伙伴，合并成一个大块 ，然后继续考查合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2 个页面 )。位图法 ，通常我们用位图来实现整个过程中，位图的某一位对应两个互为伙伴的块，为 l 表示其中一块分配出去了，为 0 表示两块都空闲。伙伴算法中无论是分配还是释放内存块都只对相应的位图位.专业 .整理 .下载可编辑进行异或操作 。 分配内存时对位图的操作是为释放

8、过程服务，释放过程根据位图判断伙伴是否存在 ，如果对相应位的异或操作得1 ，则没有伙伴可以合并，如果异或操作得0，就进行合并 ，并且继续按这种方式合并伙伴，直到不能合并为止。如上所述 ，伙伴算法综合利用了位图和链表的方式，较为高效地实现了内存的分配和释放，而且在释放过程中尽可能的合并小块内存，有效的消除了内存碎片。伪代码struct node/*建立结构数组，定义链表链接 */int much;int flag,flag_left,flag_right;struct node *leftchild,*rightchild,*father;/左右儿子父亲指针;struct IN_Tint num

9、;int space;struct node *temp;void search_tree(struct node *head,int space,int really_need)/处理内存请求内存节点的最大可用空间比应该分配内存小时分配失败否则 如果内存节点的大小正好等于应该分配内存分配成功否则如果该内存节点尚未分配子女节点分配左右子女递归处理该请求，依照做子女先分配否则若左右子女最小的可用空间比需要的内存还大取小者分配内存否则取可用空间比需要的内存大者分配内存修改节点可用空间与碎片大小void back_to_space(int i).专业 .整理 .下载可编辑从释放节点依次向上经过每一个

10、父节点，都要做释放内存的操作。运行结果演示随机生成的20 组内存分配请求这是内存分配结果，其中 ，对于内存不够时会有显示，提示最佳置换算法.专业 .整理 .下载可编辑基本思想 ：发生缺页时 ，有些页面在内存中，其中有一页见很快被访问（也包含紧接着的下一条指令的那页）， 而其他页面则可能要到10、 100 或者 1000 条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。伪代码实现void OPT()for(i=0;i<LEN;i+)如果帧已经填满若在帧中找到该页命中，退出否则找到最远使用的页面置换若帧未填满命中，则退出否则 ，加入空闲帧中运行结果演示先进先

11、出法 （ Fisrt In First Out）基本思想 ： FIFO 最简单的页置换算法， FIFO 的页置换的算法为每个页记录着该页调入内存的时间 。 当必须置换一页时，将选择最旧的页。注意并不需要记录调入一页的确切时间，可以创建一个FIFO 队列来管理内存中的所有页。队列中的首页将被置换。当需要调入页时 ，将它加入到队列的尾部。FIFO 的页置换算法很好理解和实现 ，但是，其性能并不是很好 。 所替代的页可能是很久以前使用的 、现已不再使用的初始化模块 ，另一方面 ，所替代的页可能包含一个以前初始化的并且不断使用的常用变量 。.专业 .整理 .下载可编辑伪代码实现void FIFO()f

12、or(i=0;i<LEN;i+)如果帧已经填满若在帧中找到该页命中，退出否则找到最先进入的页面置换若帧未填满命中 ，则退出否则 ，加入空闲帧中运行结果演示 最近最久未使用（ Least Recently Used）基本思想 ： LRU 置换为每个页关联该页上次使用的时间。当必须置换一次的时候，LRU选择最长时间没有使用的页，这种策略为向后看最优页置换算法。 LRU 置换算法被认为相当不错 ，其主要问题是如何实现LRU 置换 ，页帧的排序序列按页帧上次使用时间来定，有两种可行方法 ：计算器为每个页表项关联一个使用时间域，并为 CPU 增加一个逻辑时钟或者计数器。对每次内存引用，计算器都会增

13、加，每次内存引用的时候时钟寄存器的内容会被复制到相应页所对应的页表项的使用时间域内。用这种方式就得到每页的最近使用时间。置换具有最小时间的页 。 这种方案需要搜索页表已经查找LRU 也，且每次内存访问都要写入内存。在改变页表时 ，因 CPU 调度 ，也必须保持时间。必须考虑时钟溢出。栈 每当引用一个页，该页就从栈中删除并放在顶部。这样 ，栈顶部总是最近使用的页，栈底部总是LRU 页。由于必须是从栈中删除项，所以 ，该栈可实现为具有头部指针和尾指.专业 .整理 .下载可编辑针的双向链表 。 虽然每个更新有点费事，但是置换不需要搜索；尾部指针指向栈底部，就是 LRU 页。伪代码实现void LRU

14、()for(i=0;i<LEN;i+)如果帧已经填满若在帧中找到该页命中，并将该页放到帧的最后，标志最近使用退出否则找到最近最不常用的页面置换若帧未填满命中，则退出否则 ，加入空闲帧中运行结果演示最不经常使用法 （ Least Frequently Used）基本思想 ：即 LFU 算法 （Least Frequently Used algorithm）。 这种算法选择近期最少访问的页面作为被替换的页面。显然 ，这是一种非常合理的算法，因为到目前为止最少使用的页面 ，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息 ，又正确反映了程序的局部性。该算法在需要淘汰

15、某一页时，首先淘汰到当前时间为止 ，被访问次数最少的那一页 。 该算法只要在页表中给每一页增设一个访问计数器即可实现 。 每当该页被访问时，访问计数器加1 ，而发生一次缺页中断时 ，则淘汰计数值最小的那一页 ，并将所有的计数器清零。伪代码实现void LFU()/最不经常使用法.专业 .整理 .下载可编辑for(i=0;i<LEN;i+)如果帧已经填满若在帧中找到该页命中，该页面标志计数器加1，退出否则找到计数值最小的页面置换若帧未填满 ，命中该页面标志计数器加1，退出否则 ，加入空闲帧中运行结果演示 最近未使用法 （ No Used Recently）基本思想 ：该算法在需要淘汰某一页

16、时，从那些最近一个时期内未被访问的页中任选一页淘汰 。 NRU 为操作系统请求分页存储管理中的页面淘汰算法，又名近似的LRU 置换算法。当一存储块中的页面访问时 ，其相应的 “页面访问 ”位由硬件自动置 “”，而由页面管理体制软件周期性地 （设周期为 ， 其值通常为几百毫秒 ），把所有的页面访问位重新置为“”。这样 ，在时间 内，某些被访问的页面 ，其对应的访问位为 “而”未访问的页面 ，其对应的访问位为 “”。查寻页面访问位为 “的”页面 。 在查找过程中 ，那些被访问的页所对应的访问位被重新置为“”。由此可见 ，实际上这种近似LRU 算法 ，已经退化成一种“最近不用 ”的算法 NRU （

17、Not Recently Used）。伪代码实现void NUR()/最近未使用法void NRU()/最近未使用法.专业 .整理 .下载可编辑for(i=0;i<LEN;i+)模拟周期性将每一页的计数器清0如果帧已经填满若在帧中找到该页命中，该页面标志计数器置1 退出否则找到计数值为0 的页面置换 ，并将新页面计数器置1若所有计数值为1，则选首页置换若帧未填满 ，命中 ，该页面标志计数器置1 ，退出否则 ，加入空闲帧中，并将新页面计数器置1运行结果演示五、各种算法运行综合比较因为每个算法在运行时请求是随机分配的 ，所以要比较不同算法的优劣 ，需要将不同的算法放在一个程序中 ，并行执行

18、，打印在一块 ，方便观察.专业 .整理 .下载可编辑综上比较 ，帧较少时 ， OPT 算法命中率较高。其次是 LRU。六、实验心得.专业 .整理 .下载可编辑1：要编程的第一件事情是先把这个算法的思想弄明白，开始编伙伴算法时 ，没有考虑合并状况 ，没有设置对于相同伙伴的合并的判断位，以至于到了后来只能重新修改结构2：没搞清楚伙伴的定义，未考虑到伙伴的地址必须块地址连续，强行将两个大小相同 ，但地址不知道连不连续的块合并在一起，最后发现这样会导致程序停止运行，这个问题一直到写报告时 ，将书上相关知识写入文档时才发现，然后豁然开朗 ，改变了合并方式 ，程序就可以正常运行了 。这个经历也让我发现了边

19、写实验报告，边编程的重要性 ，比一味的编程更重要的是 ，在发现错误时 ，首先要考虑的是自己的编程思想是否正确，其次才是语法问题 。3：合并是一个链式问题，不是合并一次就可以的 ，而是每一次合并都要一直检测，在更大一级的链表中是否有伙伴存在，直到不能合并或者已经合并到了最大块为止。4：位图法是一种很好的标志位方法。有了它可以很方便的寻找空闲块，并进行相关的合并分配操作 。用二进制的思想考虑问题，有时候可以事半功倍 。5：很久以前是老师强制我们在编程前先画流程图，做为作业的一部分，现在，我发现先画个流程图或者先写个伪代码能让人先对程序的整体框架有一个把握，就像树的主干一样 。如果流程图画对了的话，

20、接下来把程序的具体实现填充进去，就可以很方便的实现程序功能了 。 在伙伴算法实现中 ，因为没有从全局出发，导致的反复的修改程序，让我体会到了一定要画出正确的流程图，或是先写对伪代码再进行编程的重要性。在实验报告中 ，为了简洁 ，我没有附加流程图 ，但是将相应的伪代码写入报告，来表明编程思想 。6：下面对于五种页面的置换算法进行了编程实验。这部分实现起来就比较简单了，因为老师给出了实现的分析 ，对于如何入手写出了详细的方法。“对于虚拟存储区和内存工作区的不同算法 ，其中主要的流程 ：首先用 srand( ) 和 rand( ) 函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不

21、同的算法计算出相应的命中率。”并给出了具体的例子来帮我们分析实验。这部分的难点就在于区分不同的算法，并对各种算法的排序问题和取代给出自己的方法。7：最佳置换算法使用的是最远使用的页面置换，又叫向前看最优置换算法。而 LRU 选择最长时间没有使用的页，这种策略为向后看最优页置换算法。8： LRU 置换算法关于页帧的排序序列按页帧上次使用时间来定，有两种可行方法 ：计算器和栈 。 在这次实验中我选用了计算法方法，这只需要加标志位即可，用栈的话还得另外再加操作 ，比较复杂 。9：在打印各种算法的命中率时，我想按照制表法来打印，结果发现总是有错位现象 ，因为每次请求是随机分配 ，所以无法限定打印方式，

22、总是有错位现象 。10 ：这次实现 ，通过编程的实验 ，让我对各种算法的原理了解的更为深刻，同时也熟悉了一下编程的方法 ，将 C 编程方法温习了一下。温故而知新 ，学到了很多 。七、程序源代码.专业 .整理 .下载可编辑伙伴算法#include<windows.h>#include<stdio.h>#include<stdlib.h>#include<time.h>struct nodeint much;int flag,flag_left,flag_right;struct node *leftchild,*rightchild,*father

23、;struct IN_Tint num;int space;struct node *temp;struct IN_T str20;struct node *root,*temp_root,*temp;struct node *temp_l,*temp_r;int total_space=1024,space_num1025;int apply_num=0,release_num=0,find_space=0,str_lock20;void produce_num()int i;for(i=0;i<20;i+)stri.num=rand()%512+1;.专业 .整理 .下载可编辑pri

24、ntf("%d ",stri.num);if(i=9) printf("n");printf("n");int search(int t)if(space_numt>0)space_numt-;total_space=total_space-t;return t;elseint temp=t;t=t*2;while(t<=1024)if(space_numt>0)space_numt-;int temp_2=t/2;while(temp_2>=temp)space_numtemp_2+;temp_2=temp_

25、2/2;total_space=total_space-temp;.专业 .整理 .下载可编辑break;elset=t*2;if(t<=1024)return t;elsereturn 0;void search_tree(struct node *head,int space,int really_need)if(head!=NULL)if(head->much=space&&(head->flag=0)if(space=really_need)head->flag=1;temp=head;elseint x=space/really_need;x=

26、x/2;while(x)temp_l=(struct node*)malloc(sizeof(struct node);.专业 .整理 .下载可编辑temp_r=(struct node*)malloc(sizeof(struct node);head->flag=1;head->leftchild=temp_l;head->rightchild=temp_r;temp_l->father=head;temp_l->much=(head->much)/2;temp_l->flag=1;temp_l->leftchild=NULL;temp_l-&

27、gt;rightchild=NULL;temp_r->father=head;temp_r->much=(head->much)/2;temp_r->flag=0;temp_r->leftchild=NULL;temp_r->rightchild=NULL;x=x/2;head=head->leftchild;temp=head;search_tree(head->leftchild,space,really_need);search_tree(head->rightchild,space,really_need);void back_to

28、_space(int i).专业 .整理 .下载可编辑struct node *tempx=(struct node*)malloc(sizeof(struct node);int or_not=0;total_space=total_space+stri.space;tempx=stri.temp;printf("already release the %d of %dn",stri.space,stri.num);tempx->flag=0;space_numtempx->much+;tempx=tempx->father;if(tempx)if(te

29、mpx->leftchild->flag=0)tempx->flag_left=0;elsetempx->flag_left=1;if(tempx->rightchild->flag=0)tempx->flag_right=0;elsetempx->flag_right=1;while(tempx!=NULL)&&(tempx->flag+(tempx->flag_left)+(tempx->flag_right)=1)tempx->flag=0;tempx->flag_left=tempx->

30、flag_right=0;space_num(tempx->leftchild)->much=space_num(tempx->leftchild)->much-2;space_numtempx->much+;.专业 .整理 .下载可编辑tempx->leftchild=tempx->rightchild=NULL;tempx=tempx->father;if(tempx)if(tempx->leftchild->flag=0)tempx->flag_left=0;elsetempx->flag_left=1;if(tem

31、px->rightchild->flag=0)tempx->flag_right=0;elsetempx->flag_right=1;int how_much_space(int a)if(a>512) return 1024;if(a>256) return 512;if(a>128) return 256;if(a>64) return 128;if(a>32) return 64;if(a>16) return 32;if(a>8)return 16;if(a>4)return 8;if(a>2)return

32、4;if(a>1)return 2;.专业 .整理 .下载可编辑elsereturn 1;DWORD WINAPI release()while(1)Sleep(rand()%3);if(apply_num)int c=rand()%apply_num;if(str_lockc=0)back_to_space(c);str_lockc=1;release_num+;if(release_num=20) break;DWORD WINAPI apply()while(1)Sleep(rand()%3);int t=how_much_space(strapply_num.num); /nee

33、d how big spaceif(total_space>=t).专业 .整理 .下载可编辑int have_space=search(t);if(have_space)temp_root=root;search_tree(temp_root,have_space,t);strapply_num.space=t;strapply_num.temp=(struct node*)malloc(sizeof(struct node);strapply_num.temp=temp;printf("already give %d the %dn",strapply_num.n

34、um,t);apply_num+;if(apply_num=20) break;elseprintf("There is no space to apply %d because of fragment.n",strapply_num.num);Sleep(2000);elseprintf("There is no much space to apply %d!n",strapply_num.num);Sleep(2000);int main().专业 .整理 .下载可编辑DWORD ThreadId1,ThreadId2;HANDLE ThreadHa

35、ndle1,ThreadHandle2;/ 根节点的初始化 ，貌似方法比较 2。root=(struct node*)malloc(sizeof(struct node);temp_root=(struct node*)malloc(sizeof(struct node);temp=(struct node*)malloc(sizeof(struct node);root->father=NULL;root->leftchild=NULL;root->rightchild=NULL;root->much=1024;root->flag=0;root->fla

36、g_left=root->flag_right=0;temp_root=root;/srand (time(NULL);produce_num();int i;for(i=0;i<1025;i+)space_numi=0;space_num1024=1;for(i=0;i<20;i+)str_locki=0;ThreadHandle1=CreateThread(NULL,0,release,NULL,0,&ThreadId1);ThreadHandle2=CreateThread(NULL,0,apply,NULL,0,&ThreadId2);if(Threa

37、dHandle1!=NULL).专业 .整理 .下载可编辑WaitForSingleObject(ThreadHandle1,INFINITE);CloseHandle(ThreadHandle1);if(ThreadHandle2!=NULL)WaitForSingleObject(ThreadHandle2,INFINITE);CloseHandle(ThreadHandle2);system("pause");最佳置换算法#include<windows.h>#include<stdio.h>#include<stdlib.h>#i

38、nclude<time.h>int str320;/320条指令int page32;/物理内存页int page_lock32;int count_num32;int error=0;int already_given=0;int find_page(int i)return (i/10);int page_schelduing_opt(int num).专业 .整理 .下载可编辑int i,j,m,n,count,find;for(i=0;i<num;i+) pagei=-1;page_locki=0; for(i=0;i<320;i+)find=0;count=0

39、;for(j=0;j<already_given;j+)if(pagej=stri)find=1;break;if(!find)error+;for(n=0;n<num;n+)page_lockn=0;if(already_given<num)pagealready_given=stri;already_given+;elsefor(m=i;m<320&&(count<num);m+).专业 .整理 .下载可编辑for(n=0;n<num;n+)if(strm=pagen)page_lockn=1;count+;for(n=0;n<nu

40、m;n+)if(page_lockn=0)pagen=stri;break;main()int i,j,m,n,upper,least,x=0;for(i=0;i<320;i+)stri=i;i=0;upper=319;least=0;srand (time(NULL);.专业 .整理 .下载可编辑while(i<80)/every time 4 ordersm=least+rand()%(upper+1); /m/ 执行 m+1 strx+=find_page(m+1); n=least+rand()%(m+2);/ m'/ 执行 n 和 n+1strx+=find_pa

41、ge(n);strx+=find_page(n+1);n=n+2+rand()%(320-n-2);/ 执行 n strx+=find_page(n); upper=n;least=0;i+;printf("当前运行的算法是OPT 算法 n");for(j=4;j<33;j+)printf("%d:t",j);error=0;for(i=0;i<32;i+)pagei=0;page_locki=0;i=0;error=0;already_given=0;.专业 .整理 .下载可编辑page_schelduing_opt(j);printf("%.2f,%dt",1-(float)error/320,error);if(j-3)%3=0&&j!=4)printf("n");printf("n");system("pause");先进先出法#include<windows.h>#include<stdio.h>#include<stdlib.h>#include<time.h>in