操作系统课程设计 伙伴系统

1、北京理工大学珠海学院课程设计说明书20122013学年第1学期题目: 伙伴系统 学 院： 专业班级： 学 号： 学生姓名： 指导教师： 成 绩： 时 间： 2013-1-7 年 月 日北京理工大学珠海学院课程设计任务书 2012 2013 学年第 1 学期学生姓名： 专业班级： 指导教师： 工作部门：计算机学院 一、课程设计题目 伙伴系统二、课程设计内容（含技术指标）1. 动态内存管理之伙伴系统算法2. 递归算法3. 使用Visual Studio2008开发平台三、进度安排1第1至2学时，程序分析；2第3至6学时，程序设计；3第7至8学时，程序测试与完善。四、基本要求1 初始内存的大小（必须

2、是2的幂）、申请内存的进程大小及次序等数据放在文本文件中。对于给定的输入文件，输出进程申请与退出每步的内存分配状态。 课程负责人签名： 年 月 日课程设计分工安排姓名课程设计负责工作备注程序设计软件测试书写报告线程同步与互斥摘 要固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统是操作系统中用到的一种动态存储管理方法。它与分类搜索法类似，在用户提出申请内存时，分配一块大小“合适”的内存区给用户；当

3、用户释放内存时即回收。所不同的是，伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，1km，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常是整个可分配内存的大小。结合之前学过的C程序设计和数据结构，对伙伴系统进行模拟。关键词：同步 互斥 信号量 互斥体目 录1.需求分析12.1设计任务22.1.1伙伴系统的功能概述22.1.2分配内存22.1.3回收内存33.1 外部定义变量43.2 函数说明44.调试与测试54.1 测试结果与分析5参考文献10心得体会11教师评语12计算机学院课程设计答辩记录表13 1.需求分析假设系统的可利用空间容量为2m个字

4、，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k（0km）个空闲分区链表。当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1n2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i+1的空闲分区链表中寻找。若存在2i+1的一个空闲分区，则把该空闲分区分为相等的连个分区，这两

5、个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i+1的空闲分区不存在，则需要查找大小为2i+2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i+1的两个分区，一个用于分配，一个加入到大小为2i+1空闲分区链表中；第二次，将第一次用于分配的空闲分区分割为2i的两个分区，一个用于分配，一个加入到大小为2i空闲分区链表中。若仍然找不到，则继续查找大小为2i+3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收

6、大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i+1的空闲分区，若事先已存在2i+1的空闲分区时，又应继续与其伙伴分区合并为大小为2i+2的空闲分区，依此类推。 2.总体设计2.1设计任务2.1.1伙伴系统的功能概述利用数组来实现伙伴系统算法的3种功能，定义一个空闲分区数组和已分配分区数组，这2个数组都为2维数组，分别记录空闲分区块和已分配分区块的大小和内存地址。这样，在实现伙伴系统算法的3种功能就转化为对数组的操作。 分配内存：修改空闲分区数组，模拟按照伙伴系统算法思想划分合适分区进行分配，然后添加到已分配分区数组。 回收内存：修改空闲分区数组，模拟按

7、照伙伴系统算法思想回收内存，然后从已分配分区数组中删除该内存块。 输出内存使用情况：输出空闲分区数组和已分配分区数组。2.1.2分配内存输入信息：内存大小输出信息：错误信息根据你输入的内存大小，程序寻找一个合适的空闲分区大小，如果没有找到，说明当前内存空间不足，则提示错误信息后重新输入；如果找到则按伙伴系统算法分配内存，如图2-1-2所示。图2-1-2 分配内存2.1.3回收内存输入信息：已分配内存首地址输出信息：错误信息根据输入的已分配内存首地址，程序进行查询，如果没有找到该已分配内存块，则提示错误信息后重新输入；如果找到则按伙伴系统算法回收内存，如图3-2所示。图2-1-3Main()函数

8、是程序的入口，输出提示和接受用户的收入，导入文件。READFILE（）函数根据导入的文件里的数据产生多个子线程（男生线程和女生线程）。等到所有的子线程都执行结束后才结束。Man()函数是男生线程执行的函数，Woman()函数是女生线程执行的函数，这两个函数的结构大致相同，都是用来控制线程之间的同步与互斥，相同性别线程之间是同步的关系，异性线程之间是互斥关系。 3.详细设计3.1 外部定义变量int buddy10=2,4,8,16,32,64,128,256,512,1024; /分区大小 2的k次幂int free110=0,0,0,0,0,0,0,0,0,1; /空闲分区的个数 初始内存大

9、小1024int use1002=0; /已分配分区表/最多为100个进程分配 记录已分配分区大小，内存地址int free_addr1050=0; /空闲分区的首地址/free_addrij表示2的i次方大小的空闲分区的第j个分区的首地址int maxsize=9; /最大空闲分区 初始为1024int usenum=0; /进程数 初始为03.2 函数说明void menu(); / 多级菜单函数void showMemory(); /输出内存使用情况void showFreeMemory(); /输出空闲分区情况void showUseMemory(); /输出已分配区情况void al

10、locBuddy(); /分配内存void reclaimBuddy(); /回收内存4.调试与测试4.1 测试结果与分析用户运行程序首先出现的是一个选择菜单，如图4-1所示。图4-1 菜单界面只能输入0-3进行选择，如果输入其他数据则提示出错后重新输入，如图4-2所示图4-2 选择出错选择3查看内存占用情况，观察当前内存的的使用情况。由于程序刚运行，未分配过内存，当前内存为初始大小1024，如图4-3所示。图4-3 初始内存按任意键返回到菜单，输入1申请内存，进入到申请内存界面。该界面输出内存空闲区的的情况，方便用户模拟申请内存，用户只要输入申请内存大小即可申请内存，如图4-4所示。图4-4

11、 申请内存界面申请内存的大小在11024之间，如果输入超过范围或者输入其他字符，提示出错后重新输入。如果申请内存的大小超过当前系统的内存，则提示内存不足后重新输入，如图4-5所示。图4-5 申请内存出错输入合法的申请内存的大小后，系统按伙伴系统算法分配内存，如图4-5所示。图4-5申请内存成功按任意键返回到菜单，输入3查看当前内存的使用情况，如图4-6所示。图4-6 查看内存使用情况按任意键返回到菜单，输入2模拟释放内存，进入释放内存界面。该界面输出内存已分配区的情况，方便用户模拟释放内存，用户输入已分配内存的首地址即可释放内存，如图4-7所示。图4-7 释放内存界面只能输入已分配内存的首地址

12、，如果输入其他则提示出错后重新输入，如图4-8所示。图4-8 释放内存出错输入已分配内存的首地址后，系统按伙伴系统算法回收内存，如图4-9所示。图4-10 释放内存成功 将已分配的内存块全部释放后，内存又恢复初始状态，如图4-11所示。图4-11 恢复初始状态 参考文献1(荷兰)AnderwS.Tanenbaum ：现代操作系统M，机械工业出版社2009年版。2作者：MicrosoftMSDNOL3作者：（美）William StallingsOperating Systems Internal and Design Principles,Sixth EditionM,北京：机械工业出版社,2

13、010.9,进程与线程部分。心得体会根据伙伴系统算法的思想我们组划分了3个模块模拟了伙伴系统的3个操作。第一个模块是内存分配模块，通过该模块的功能可以实现按伙伴系统算法分配内存的操作。第二个模块是内存回收模块，通过该模块的功能可以实现按伙伴系统算法回收内存的操作。第三个模块是输出模块，通过该模块的功能可以实时输出系统内存使用的情况。通过编码调试，表明该程序模块是有效可行的。教师评语 计算机学院课程设计答辩记录表专业学院计算机 专业软件工程姓名学号课程设计题目伙伴系统答辩日期答辩时间答辩提问及其回答记录 计算机学院课程设计答辩记录表专业学院计算机 专业软件工程姓名学号课程设计题目伙伴系统答辩日期

14、答辩时间答辩提问及其回答记录程序代码#include #include #include int buddy10=2,4,8,16,32,64,128,256,512,1024; /分区大小 2的k次幂int free110=0,0,0,0,0,0,0,0,0,1; /空闲分区的个数 初始内存大小1024int use1002=0; /已分配分区表 最多为100个进程分配 记录已分配分区大小，内存地址int free_addr1050=0; /空闲分区的首地址 ij表示2的i次方大小的空闲分区的第j个分区的首地址int maxsize=9; /最大空闲分区 初始为1024int usenum=

15、0; /进程数 初始为0void menu(); / 多级菜单函数void showMemory(); /输出内存占用情况void showFreeMemory(); /输出空闲分区情况void showUseMemory(); /输出已分配区情况void allocBuddy(); /分配内存void reclaimBuddy(); /回收内存void menu()printf( * 欢迎使用伙伴系统模拟程序 *n); printf( *n); printf( *n); printf( * 1.申请内存 *n); printf( * 2.释放内存 *n); printf( * 3.查看内存占

16、用情况 *n);printf( * 0.退出 *n); printf( *n); printf( *n); printf( *n);int n; lab1:fflush(stdin); /刷新缓冲区printf(请输入(0-3)选择：);scanf(%d,&n);switch(n) case 1:system(cls); showFreeMemory(); allocBuddy(); printf(分配成功，按任意键返回！); getch(); system(cls); menu(); break;case 2:system(cls); if(usenum!=0) showUseMemory(

17、); reclaimBuddy(); printf(回收成功，按任意键返回！); else printf(未分配内存，请先申请内存！按任意键返回！); getch(); system(cls); menu(); break;case 3:system(cls); showMemory(); printf(按任意键返回！); getch(); system(cls); menu(); break;case 0:printf(按任意键退出！); getch(); break; default:printf(输入错误，请重新输入！n); goto lab1;void showMemory() /输出

18、内存使用情况 int i,j;printf(空闲分区剩余情况：n);for(i=0;i10;i+)printf(空闲区大小%4d：有%d个空闲块，内存起始地址分别为：,buddyi,free1i);for(j=0;jfree1i;j+)printf(%4d%4d ,free_addrij,free_addrij+buddyi-1);printf(n);printf(内存已分配区情况：n);for(i=0;iusenum;i+)printf(%2d：分区大小：%4d 内存起始地址为：%4d%4dn,i+1,buddyusei0,usei1,usei1+buddyusei0-1);void sho

19、wFreeMemory() /输出空闲分区情况 int i,j;printf(空闲分区剩余情况：n);for(i=0;i10;i+)printf(空闲区大小%4d：有%d个空闲块，内存起始地址分别为：,buddyi,free1i);for(j=0;jfree1i;j+)printf(%4d%4d ,free_addrij,free_addrij+buddyi-1);printf(n);void showUseMemory() /输出已分配区情况 int i;printf(内存已分配区情况：n);for(i=0;iusenum;i+)printf(%2d：分区大小：%4d 内存起始地址为：%4d

20、%4dn,i+1,buddyusei0,usei1,usei1+buddyusei0-1);void allocBuddy() /分配内存 int i,j,size,usepage,remain,start;lab2:fflush(stdin); printf(请输入申请内存的大小(11024)：); scanf(%d,&size);if(size1024) printf(请输入11024之间的数字！);goto lab2; else if(sizebuddymaxsize)printf(没有足够的内存空间，请先释放！n) ;goto lab2;else for(i=0;i=size)brea

21、k;usepage=i; free1i-;for(i=0;i=size) break; useusenum0=i; /记录分配给该进程的空闲区大小 2的i次方 useusenum1=free_addrusepagefree1usepage; / 内存起始地址 remain=buddyusepage-buddyuseusenum0; /剩余大小start=free_addrusepagefree1usepage+buddyusepage-buddyusepage-1; /空闲区首地址usenum+; for(i=usepage-1;i=0;i-) /确定其他空闲分区的首地址 if(remain=

22、buddyi)free1i+; free_addrifree1i-1=start;remain-=buddyi; /剩余大小start-=buddyi-1; /首地址if(remain=0)break;if(free1maxsize=0) /确定最大空闲分区maxsize=0;for(i=9;i=0;i-)if(free1i!=0)maxsize=i;break; void reclaimBuddy() /回收内存 int i,j,k,free_start,flag,f=0;lab3:fflush(stdin); printf(请输入要回收内存的首地址：);scanf(%d,&free_start);for(i=0,flag=0;iusenum;i+) /匹配已分配首地址if(free_start=usei1)free_start=i;flag=1;break; if(flag=0)printf(输入的首地址不存在，请重新输入！n);goto lab3;else for(i=usefree_start0;i9