操作系统-内存分配与回收模拟-实验06.doc

操 作 系 统 课 程 实 验 报 告姓名学号系任课教师指导教师评阅教师实验地点综合楼B104 励耘楼A206 综合楼B102 丽泽楼C304-1 (请勾选实际实验地点)实验时间实验课表现出勤和个人表现Q1(15+15（组长评分）=30分)得分：实验总分(Q1+Q2+Q3+Q4)实验完成情况Q2(45分(组长与教师评分的加权平均)得分：实验编号与实验名称：第六次实验 内存分配与回收模拟实验目的：通过使用位图跟踪内存使用情况，模拟和评价不同的内存分配算法；熟悉内存分配和回收。实验内容及要求（详见实验讲义与实验指导书）：实验要求： 1）要求用你熟悉的程序设计语言编写和调试一个内存分配和回收模拟程序；要求在主函数中测试。2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。3）必须模拟该4种内存分配算法：first fit，next fit，best fit和worst fit中的至少2种。4） 需显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图，并统计各种算法产生的碎片空闲区（小于3个单元（unit）的空闲区）数。5）计算2个性能参数：碎片数、平均搜索空闲区次数实验内容： 假设内存容量为256KB，并且划分成2KB大小的块，也即每个内存单元为2KB。一个进程所需要的内存为3到10个单元。同时假设一个作业在运行过程中所需内存的大小不变。 模拟包括3部分：1）实现特定的内存分配算法2）实现内存回收模拟3）每种内存分配策略对应的碎片数统计实验用到的软件（：）C-FREE实验内容及关键步骤（代码）Q3（15分）得分：（1）首次适应算法实现 从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。（2）最佳适应算法实现它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。数据结构体分析（3）内存回收将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。首次适配算法流程图：最佳适配算法流程图：内存回收：#include #include #include #define M 20#define N 101#define max_size 128int i = 0,choose;int id= 0,size = 0,countOfEmpty = 1,countOfNotEmpty = 0,num = 1;int TimeN=1;/进程分配搜索空闲区次数 struct Emptyint start;int size;int yesornot;emptyM;struct not_Emptyint id;int size;int start;int yesornot;not_emptyN;int cmp(const void *p,const void *q) int c = (*(struct Empty*)p).start - (*(struct Empty*)q).start;int a = (*(struct Empty*)p).yesornot - (*(struct Empty*)q).yesornot; if(a 0) return -1; else if(a = 0)if(c 0) return 1; else return -1;else return 1;int cmp1(const void *p,const void *q) int c = (*(struct not_Empty*)p).start - (*(struct not_Empty*)q).start;int a = (*(struct not_Empty*)p).yesornot - (*(struct not_Empty*)q).yesornot; if(a 0) return -1; else if(a = 0)if(c 0) return 1; else return -1;else return 1;int cmp2(const void *p,const void *q) int c = (*(struct Empty*)p).size - (*(struct Empty*)q).size;int a = (*(struct Empty*)p).yesornot - (*(struct Empty*)q).yesornot; if(a 0) return -1; else if(a = 0)if(c 0) return 1; else return -1;else return 1;void state()int j = 0,f = 0,k = 0,x = 0, t = 0,a,flog =0,debris = 0;qsort(not_empty, countOfNotEmpty, sizeof(struct not_Empty), cmp1);qsort(empty, countOfEmpty, sizeof(struct Empty), cmp);for(i = 0; i countOfEmpty; i+)if(emptyi.yesornot = 0)j+;countOfEmpty-=j;for(i = 0; i countOfNotEmpty; i+)if(not_emptyi.yesornot = 0)f+;countOfNotEmpty-=f;if(not_empty0.start = 0)flog = 1;while(1)if(flog = 1)for(f = t; f countOfNotEmpty; f+)if(not_emptyf.start%11 = 0)printf(n);printf(%2d,not_emptyf.id);for(j = not_emptyf.start+1; j not_emptyf.size + not_emptyf.start; j+)if(j%11 = 0&j!=0)printf(n+ );elseprintf(+ );if(not_emptyf.start + not_emptyf.size = max_size|not_emptyf.start + not_emptyf.size = max_size -2)break;if(not_emptyf.start + not_emptyf.size = emptyx.start)t = f+1;break;for(j = emptyx.start; j emptyx.size + emptyx.start; j+)if(j%11 = 0&j!=0)printf(n);elseprintf();flog = 1;if(emptyx.size + emptyx.start = max_size)break;x+;printf(n空闲分区列表：n);for(a = 0; a countOfEmpty; a+)if(emptya.size 3)debris+;printf(起始位置：%d 大小：%dn,emptya.start,emptya.size);printf(非空闲分区列表：n);for(a = 0; a countOfNotEmpty; a+)if(not_emptya.yesornot = 1)printf(id：%d 起始位置：%d 大小：%dn,not_emptya.id,not_emptya.start,not_emptya.size);printf(碎片空闲分区数：%dn,debris);void distribute()int temp = 0;printf(请输入进程ID(0-255),占用空间大小(3-10)n);scanf(%d%d,&id,&size);for(i = 0; i 30; i+)printf(-);printf( 内存占用情况图 );for(i = 0; i 30; i+)printf(-);printf(n); if(choose = 1)qsort(empty, countOfEmpty, sizeof(struct Empty), cmp2);for(temp = 0; temp countOfEmpty; temp+)Timenum+;if(size = emptytemp.size)not_emptycountOfNotEmpty.yesornot = 1;not_emptycountOfNotEmpty.id = id;not_emptycountOfNotEmpty.start = emptytemp.start;not_emptycountOfNotEmpty.size = size;emptytemp.start += size;emptytemp.size -= not_emptycountOfNotEmpty.size;if(emptytemp.size = 0)emptytemp.yesornot = 0;countOfNotEmpty+;break;if(temp-1 = countOfEmpty)printf(内存空闲不足，无法分配n);elsestate();printf(第%d次搜索空闲区次数为:%dn,num,Timenum);void recover()int p;printf(请输入进程ID(0-255)n);scanf(%d,&id);for(i = 0; i 30; i+)printf(-);printf( 内存占用情况图 );for(i = 0; i 30; i+)printf(-);printf(n); for(i = 0; i countOfNotEmpty; i+)if(not_emptyi.id = id)not_emptyi.yesornot = 0;p = i;break;countOfEmpty+;for(i = 1; i countOfEmpty; i+)if(not_emptyp.start = emptyi-1.start + emptyi-1.size)/新生成的空闲区可以和左边的空闲区可以合并 emptyi-1.size += not_emptyp.size;emptyi-1.yesornot = 1;countOfEmpty-;if(emptyi.start = not_emptyp.start + not_emptyp.size)/右边可以合并 emptyi-1.size += emptyi.size;emptyi.yesornot = 0;break;else if(emptyi-1.start = not_emptyp.start + not_emptyp.size)/右边可以合并 emptyi-1.start = not_emptyp.start;emptyi-1.size += not_emptyp.size;emptyi-1.yesornot = 1;countOfEmpty-;break;if(i = countOfEmpty - 1)emptycountOfEmpty-1.size = not_emptyp.size;emptycountOfEmpty-1.yesornot = 1;emptycountOfEmpty-1.start = not_emptyp.start;break;state();void first_fit()int chose = 0;for(i = 0; i 80; i+)printf(-);printf(ttt 首次适应算法n);for(i = 0; i 80; i+)printf(-);printf(n);printf(1 分配;ttt2 回收n3 内存占用情况图tt4 退出n请输入你的选择(1-4)n);scanf(%d,&chose);choose = 0;switch(chose)case 1:distribute();num+;break;case 2:recover();break;case 3:state();break;case 4:exit(0);break;void best_fit()int chose;for(i = 0; i 80; i+)printf(-);printf(ttt 最佳适应算法n);for(i = 0; i 80; i+)printf(-);printf(n);printf(1 分配;ttt2 回收n3 内存占用情况图tt4 退出n请输入你的选择(1-4)n);scanf(%d,&chose);choose = 1;switch(chose)case 1:distribute();num+;break;case 2:recover();break;case 3:state();break;case 4:exit(0);break;int main()empty0.size = max_size;empty0.start = 0;empty0.yesornot = 1;char algorithm20;printf(n);printf(选择算法：F/B（首次适应算法/最佳适应算法）n);while(1) scanf(%s,algorithm); if(strcmp(algorithm,F) = 0|strcmp(algorithm,B) = 0) break; else printf(输入出错，请重新输入n);if(strcmp(algorithm,F) = 0)while(1)first_fit();elsewhile(1)best_fit();system(pause);return 0;实验过程中遇到的问题解决办法与实验体会Q4（需手写，10分）得分：本次做的课题是内存分配算法实现，此次课程设计成功实现了内存分配和内存回收，内存分配中包