《用首次适应算法模拟内存的分配和回收》由会员分享，可在线阅读，更多相关《用首次适应算法模拟内存的分配和回收（16页珍藏版）》请在金锄头文库上搜索。
1、操作系统实验报告完成日期：2011-12-5用首次适应算法模拟内存的分配和回收一、实验目的在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本 实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。在熟练掌握计 算机分区存储管理方式的原理的基础上，编程模拟实现操作系统的可变分区存储管理的功 能，一方面加深对原理的理解，另一方面提高根据已有原理通过编程解决实际问题的能 力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。二、实验内容与数据结构：(1) 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区的个数是可以调
2、整的。当需要装入一个作业时，根据作业需要的贮存量，查 看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等 待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被分 配作业占用，有的分区空闲，例如，某时刻主存空间占用情况如图所示：0K操作系统(10KB)10K作业 1(10KB )45K作业4(25KB )65K空闲区 1(20KB)110K作业 2(45KB )256K空闲区 2(146KB)为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如 下图所示。起始地址长度状态45K20KB未分配110K146KB未分配空表目空表目空表目
3、.(2) 当有一个新作业要求装入贮存时，必须查空闲区说明表，从中找出一个足够大的空闲 区。有时找到的空闲区可能大于作业的需求量，这时应将空闲区一分为二。一个分给 作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽 可能分配地地址部分的空闲区，将较大的空闲区留在高地址端，以利于大作业的装 入。为此在空闲区表中，按空闲区首地址从低到高进行登记。(3) 当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时，要考虑相邻空 间区合并问题。作业的释放区与空闲区的邻接分以下4种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D、释放区上邻空
4、闲区不邻接；二、实验要求1. 内存大小初始化2. 可以对内存区进行动态分配，采用首次适应算法来实现3. 可以对已分配的内存块进行回收，并合并相邻的空闲内存块。三、实验内容把一个作业装入内存，按照首次适应算法对内存区进行分配，作业结束，回收已分配给该作业的内存块，并合并相邻的空闲内存块。四、实验结果运行效果:1. 初始化内存区大小，并添加作业，选择1添加作业2. 当作业大小超过存储块大小时，分配失败。3. 选择3,可查看内存分配情况4. 选择2回收内存5. 选择1添加新作业6. 回收C作业，相邻的空闲内存块合并。五、程序流程图:开始NY长度=XK ?状态为“未分配”吗？J为空闲区 说明表的最 后
5、一个表 目？Y返回N大于小于等于登记已分配区表和空闲区表， 输出系统中各数据结构的值， 返回分配给作业的主存始址。长度=长度-XK始址=始址+XK查看第J个表目的登记项置状态为“空表目”申请XK主存将空表目向后移J=J+1J=0作业等待六、实验源代码：/ FirstFit.cpp :可变分区用首次适应算法来模拟内存回收#include #include int MAX_SEGMENT=10;/ 最大碎片值struct Partition分区表目int Par_Size;分区大小int Par_No;分区序号或者名字int Addr;分区地址int IsUse;分区使用情况,0表示空闲，1表示使
6、用Partition *pri;前向指针Partition *next;后向指针;Partition *list,*H,*H1;list=(struct Partition *)malloc(sizeof(struct Partition); list-next=NULL; H=list; if(!list) printf(n错误，内存初始化分配失败！程序结束， exit(1); H1=(struct Partition *)malloc(sizeof(struct Partition); printf(请预先输入分区总大小(以KB为单位)：”)； scanf(%d”,&H1-Par_Size
7、); H1-Addr=0; H1-Par_No=0; H1-IsUse=0; H1-pri=H; H1-next=NULL; H-next=H1;/list-H1 return list; Partition * InitFP() 初始化已分配分区表Partition *FP,*F,*H; int i; FP=(struct Partition *)malloc(sizeof(struct Partition); FP-next=NULL; H=FP; for(i=0;iPar_Size=0; F-Addr=0;F-Par_No=0;F-IsUse=0;F-next=NULL;H-next=F
8、;F-pri=H;H=H-next;return FP;Partition * New_Process( Partition *list, Partition *FP)(为新的进程分配资源Partition *H,*R*H1;int Size,Name,L;H=list;H1=FP-next;H=H-next;printf(请输入新作业的名称和大小(整数):， scanf(%d %d”,&Name,&Size);while(H)if(!H)表目已查完，无法分配printf(n已无空闲分区，本次无法分配!”);return list; elseif(H-IsUse=0)/if(H-Par_Siz
9、e=Size)空表目大小满足，空闲分区大小要分配的大小if(H-Par_Size=Size) 大小满足,bool temp=false;if(H-Par_Size-Size)=MAX_SEGMENT)/ 空闲分区大小-要分配的大小 Par_Size;/分配的大小为整块内存 temp=true;/会产生碎片/其他情况就分配大小为请求大小，不会产生碎片，L=H-Addr;/保存空闲分地址if(temp)(printf(该次内存分配会产生碎片，将整块内 存大小d分配出去也Size);else(printf(该次内存分配不会产生碎片， break; H=H-next;否则，继续往下查找if(H)if(
10、H-Par_SizeSize)大小满足，空闲分区大小要分配的大小P=(struct Partition *)malloc(sizeof(struct Partition);分配新的表目，处理一条数据，分配一次内存P-IsUse=1;P-Addr=L;/指向空闲分区地址P-next=H;修改指针H-pri-next=P;P-pri=H-pri;H-pri=P;P-Par_Size=Size;/分配大小为要请求分配的大小P-Par_No=Name;/ 名称H-Par_Size-=Size;修改空闲分区,H所指区块大小减SizeH-Addr+=Size;/H所指区块地址加Sizeelse H-IsU
11、se=1;大小相等的，把当前表项设置空表目while(H1)if(H1-IsUse=0)H1-Par_No=Name;H1-Par_Size=Size;H1-Addr=L;/保存已分配地址H1-IsUse=1;/在已分配表中设置为已分配 break;H1=H1-next;elseprintf(-所申请资源已大过系统所拥有的，请重新输入!n);return list;Partition *Reclaim( Partition *list, Partition *FP)(结束作业，资源回收,No为作业名，回收内存Partition * H1,*H2,*H3,*HF;/H1为释放区，H2为后分区，H
12、3为前分区 int No;/作业名H1=list;HF=FP;/可有可无？H1=H1-next;HF=FP-next;printf(请输入您想结束的作业名:)； scanf(%D”,&No);while(HF)/对已分配表进行操作if(HF-Par_No=No)HF-IsUse=0;标志为空表目break;/这时保存着HF所指分区的信息 HF=HF-next;if(!HF)如果找不到该作业，则提示出错printf(-所输入的作业名称不正确,请重新输入!);elsewhile(H1)/对空闲表进行操作if(H1-Par_No=No)printf(内存回收成功)； break; H1=H1-nex
13、t; H2=H1-next;/后 分区 H3=H1-pri;/前 分区 if(H2&H2-IsUse=0) /后接分区为空闲 if(H2-next=NULL)判断后接分区是否为尾结点 H1-Par_Size+=H2-Par_Size;把 H2 合并到 H1H1-next=NULL; free(H2); printf(已回收d 大小内存,H1-Par_Size); else 后分区不为空闲，表示已经被使用 H1-Par_Size+=H2-Par_Size; H1-next=H2-next; H2-next-pri=H1; free(H2); printf(已回收d 大小内存,H1-Par_Size); if(H3&H3-IsUse=0)前分区为空闲分区，则合并去前分区 H3-Par_Size+=H1-Par_Size; H3-next=H1-next; if(H1-next!=NULL)若 H1 为尾结点H1-next-pri=H3; free(H1); printf(已回收d 大小内存,H1-
