首次适应算法 内存分配.doc

操作系统实验报告课程名称： 操作系统 实验题目： 首次适应算法 姓 名： * 专业班级： * 学 号： * 指导老师： * 一、 实验目的在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。二、 实验要求1. 内存大小初始化2. 可以对内存区进行动态分配，采用首次适应算法来实现3. 可以对已分配的内存块进行回收，并合并相邻的空闲内存块。三、 实验内容把一个作业装入内存，按照首次适应算法对内存区进行分配，作业结束，回收已分配给该作业的内存块，并合并相邻的空闲内存块。四、 实验结果运行效果：1.初始化内存区大小，并添加作业，选择1添加作业2.当作业大小超过存储块大小时，分配失败。3.选择3，可查看内存分配情况4. 选择2回收内存5. 添加新作业6. 回收C作业，相邻的空闲内存块合并。五、 实验总结首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始查找，直到找到一个大小能满足要求的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区仍留在空闲链中。若从链首到链尾都不能找到一个能满足要求的分区，则此次分配失败。这里，我采用数组的方式，模拟内存分配首次适应算法，动态的为作业分配内存块。可以根据作业名称回收已分配的内存块，当空闲内存块相邻时，则合并。通过此次的实验，让我对内存分配中首次适应算法更加熟悉，在此基础上，我也测试最佳适应算法（best_fit）和最坏适应算法（worst_fit），并对其进行了比较分析，从比较中我发现，针对同一个问题，解决的方法不止一种，而且不同的方法所要消耗的资源和时间也不相同，根据不同的要求，方法的优劣也不同，可以说方法是解决问题的一种模式，随环境不同而体现出优越性。六、 实验附录程序源代码：#include #include #include int neicun=200;/内存块默认大小int fqNum=1;/已使用分区数目，进程数目=fqNum-1#define number 100/进程数量struct fqinfo/分区信息 int start;/开始位置 int end;/结束位置 char name;/进程名称int capactity;/进程大小或者分区块大小int flag;/分区使用标记，0：未使用 1：已使用 2:回收或者合并的分区 3:尾部fqlistnumber;int init_neicun();/初始化内存大小int first_fit(char name,int size);/首次适应算法int fenpei();/为进程存储区int showit();/显示进程int menu();/功能菜单int Memory_recovery();/内存回收int exit();/退出系统int main()init_neicun();/初始化内存大小menu();return 0;int menu()int select;printf(n-n);printf( 1: 添加进程 2: 回收内存n);printf( 3: 查看内存分配 4: 退出n);printf(-n);printf(please input you choice:);scanf(%d,&select);switch(select)case 1:fenpei();break;case 2:Memory_recovery();break;case 3:showit();break;case 4:exit();break;menu();return 0;int init_neicun()for(int i=0;inumber;i+)=$;fqlisti.start=0;fqlisti.end=0;fqlisti.capactity=0;fqlisti.flag=0;printf(请输入内存大小:);scanf(%d,&neicun);printf(内存大小neicun=%dn,neicun);fqlist0.capactity=neicun;fqlist0.start=0;fqlist0.end=neicun-1;fqlist0.flag=3;return 0;int fenpei()getchar();char m;int n;printf(请输入进程的名称和大小（空格分隔）：);scanf(%c %d,&m,&n);first_fit(m,n);return 0;int first_fit(char jname,int size)/printf(name=%c,size=%d,number=%dn,jname,size,number);/int count=0;int flag=0;/默认情况分配失败 1时分配成功int sum=0;for(int i=0;isize)/printf(fenpei name=%c,size=%dn,jname,size);if(ii;j-)fqlistj=fqlistj-1;fqlisti+1.name=$;fqlisti+1.start=sum+size;fqlisti+1.end=fqlisti.end;fqlisti+1.capactity=fqlisti.capactity-size;fqlisti+1.flag=fqlisti.flag;=jname;fqlisti.start=sum;fqlisti.end=sum+size-1;fqlisti.capactity=size;fqlisti.flag=1;fqNum+;/进程数目增1/需要把以后的分区块往后一个位置flag=1;else/当未使用的分区块大小不足时sum=sum+fqlisti.capactity;else/当该分区块在使用时sum=sum+fqlisti.capactity;/count+;/记录已查询出的分区块个数if(flag=1)printf(已为进程%c分配内存区！n,jname);elseprintf(为进程%c分配内存区失败！n,jname);return 0;int Memory_recovery()int flag=0;/标记回收是否成功 0：失败 1：成功int sflag=0;/int tflag=0;/char jname=z;getchar();/吸收空白键printf(请输入进程名称:);scanf(%c,&jname);for(int i=0;inumber;i+)if(=jname)=$;fqlisti.flag=2;/表示为回收的内存区flag=1;fqNum-;if(flag=1)printf(进程%c结束，内存回收成功！n,jname);elseprintf(进程%c无法结束，内存回收失败！n,jname);/将连续的已回收的内存区合并while(flag3)for(i=0;inumber-1;i+)if(fqlisti.flag=0|fqlisti.flag=2)if(fqlisti+1.flag!=1)if(fqlisti+1.flag=3)fqlisti.end=fqlisti+1.end;fqlisti.capactity=fqlisti.capactity+fqlisti+1.capactity;fqlisti.flag=fqlisti+1.flag;for(int j=i+1;jnumber-1;j+)fqlistj=fqlistj+1;i=number;flag+;elsefqlisti.end=fqlisti+1.end;fqlisti.capactity=fqlisti.capactity+fqlisti+1.capactity;fqlisti.flag=fqlisti+1.flag;for(int j=i+1;jnumber-1;j+)fqlistj=fqlistj+1;flag+;return 0;int showit()/显示进程情况int count=0;printf(进程名称 开始位置 结束位置 进程大小 状态n);for(int i=0;inumber-1&countfqNum;i+)printf(%5c%10d%12d%10d,,fqlisti.start,fqlisti.end,fqlisti.capactity);if(fqlisti.flag=1)prin