张蒙用首次适应算法模拟内存的分配和回收

《张蒙用首次适应算法模拟内存的分配和回收》由会员分享，可在线阅读，更多相关《张蒙用首次适应算法模拟内存的分配和回收（18页珍藏版）》请在装配图网上搜索。

1、采用首次适应算法实现主存的分配和回收一、目的在电脑系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实 验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。在熟练掌握电脑 分区存储管理方式的原理的基础上，编程模拟实现操作系统的可变分区存储管理的功能， 一方面加深对原理的理解，另一方面提高根据已有原理通过编程解决实际问题的能力，为 进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。二、实验内容与数据结构：(1) 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区的个数是可以调整的。当需要装入一个作业时，根据作业需要的贮存量，

2、查看是否有足够的空闲空间，假设有，则按需求量分割一部分给作业；假设无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被分配作业占用，有的分区空闲，例如，某时刻主存空间占用情况如下图：0K操作系统(10KB)10K作业1 (10KB )45K作业4 (25KB )65K空闲区1(20KB)110K作业2 (45KB )256K空闲区2 (146KB)为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如 下列图所示。起始地址长度状态45K20KB未分配110K146KB未分配空表目空表目空表目(2) 当有一个新作业要求装入贮存时，必须查空闲区说

3、明表，从中找出一个足够大的空闲 区。有时找到的空闲区可能大于作业的需求量，这时应将空闲区一分为二。一个分给 作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽 可能分配地地址部分的空闲区，将较大的空闲区留在高地址端，以利于大作业的装 入。为此在空闲区表中，按空闲区首地址从低到高进行登记。(3) 当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时，要考虑相邻空 间区合并问题。作业的释放区与空闲区的邻接分以下4种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D、释放区上邻空闲区不邻接一、 实验要求1. 内存大小初始化2. 可以

4、对内存区进行动态分配，采用首次适应算法来实现3. 可以对已分配的内存块进行回收，并合并相邻的空闲内存块。二、 实验内容 把一个作业装入内存，按照首次适应算法对内存区进行分配，作业结束，回收已分配 给该作业的内存块，并合并相邻的空闲内存块。三、实验结果运行效果：1初始化内存区大小，并添加作业，选择1添加作业2.当作业大小超过存储块大小时，分配失败。3选择3,可查看内存分配情况4. 选择2回收内存5. 选择1添加新作业6. 回收C作业，相邻的空闲内存块合并。五、程序流程图：等于置状态为“空表目将空表目向后移开始长度=XK ？NJ为空闲区说明表的最 后一个表 目？大于长度=长度-XK始址=始址+XK

5、登记已分配区表和空闲区表, 输出系统中各数据结构的值, 返回分配给作业的主存始址。Y作业 等待回 返六、实验源代码：/ FirstFit.cpp : 可变分区用首次适应算法来模拟内存回收#include #include int MAX_SEGMENT=10;最大碎片值struct Partition/分区表目int Par_Size;/分区大小int Par_No;/分区序号或者名字int Addr;/分区地址/分区使用情况,0表示空闲，1 表示使用int IsUse;Partition *pri;/前向指针Partition *next;/后向指针;Partition * Int()函数，

6、返回 Partition 类型指针/初始化空闲分区表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)；H1-Addr=0； H1-

7、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;F-pri=H; H=H-next;return

8、FP;Partition * New_Process( Partition *list， Partition *FP) /为新的进程分配资源Partition *H，*P，*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; else要分配的大小if(H-IsUse=0)/if(H-Par_Size=Size)if(H-Par_

9、Size=Size)/空表目/大小满足，空闲分区大小/大小满足，bool temp=false;if(H-Par_Size-Size)v=MAX_SEGMENT) 空闲分区大小-要分配的大小Par_Size;分配的大小为整块内存 temp=true;会 产生碎片 /其他情况就分配大小为请求大小，不会产生碎 片，L=H-Addr;保存空闲分地址 if(temp)printf(”该次内存分配会产生碎片,将整块内 存大小d分配出去!,Size);elseprintf(”该次内存分配不会产生碎片”)； break;H=H-next;/否则，继续往下查找if(H)if(H-Par_SizeSize)/大

10、小满足,空闲分区大小要分配的大小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所指区块地址加SizeelseH-IsUse=1;/大小相等的，把当前表项设

11、置空表目while(H1) if(H1-IsUse=0) H1-Par_No=Name; H1-Par_Size=Size;Hl-Addr=L;保存已分配地址 Hl-IsUse=l;在已分配表中设置为已分配 break;Hl=Hl-next;elseprintf(所申请资源已大过系统所拥有的，请重新输入!n); return list;Partition *Reclaim( Partition *list， Partition *FP)结束作业，资源回收,No为作业名，回收内存Partition * H1,*H2,*H3,*HF;/H1为释放区，H2为后分区，H3为前分区 int No;/作业

12、名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(Hl)/对空闲表进行操作if(Hl-Par_No=No)Hl-IsUse=0;/标志为空表目printf(”内存回收成功”)； break;Hl

13、=Hl-next；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)

14、;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-Par_Size); return list;void Print( Partition *list, Partition *FP)/输出已分配分区和空闲分区Partition *H1,*H2;H1=list-next;H2=FP;H2=H2-next;printf(*printf(分区序号while

15、(H2)已分配分区表*n)； 大小始址状态5);printf(%dif(H2-IsUse=1)printf(已分配5);%d %d,H2-Par_No,H2-Par_Size,H2-Addr);elseprintf(” 空表目 n);H2=H2-next;printf(printf(*n); *总的空闲分区表* n)大小始址状态5);printf(分区序号while(H1)printf(%dif(H1-IsUse=1)printf(已分配5);%d %d,H1-Par_No,H1-Par_Size,H1-Addr);elseprintf( 空表目 n);H1=H1-next;*J / 11 1

16、* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* f f -*% 1-1- f 1 1 Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx

17、Tx Tx Tx Tx Tx Tx -*% 1 1 1 void Main_Print( Partition *list, Partition *FP)/ 主入口函数，进行菜单项选择择int op;while(1)printf(n主菜单 n);printf( 1.申请新的作业，分配内存5); printf(2 结束作业,回收内存5);printf(3.查看内存表5);printf(4.退出系统5); printf(n 请选择:”)； scanf(%d,&op);switch(op)/根据输入,选择分支方向 case 1:New_Process(list,FP);break;case 2:Rec

18、laim(list,FP);break;case 3:Print(list,FP);break;case 4:break;default:printf(n选择错误，请重新选择!)；break;if(op=4)break;/退出循环void main()/主函数入口struct Partition *list,*FP;list=Int();FP=InitFP();Main_Print(list,FP);七、实验结果图示：了页先输入分区总大小 以KB/勺单位:200三12 3 4存亜匕收 、耳一 FHT 七箱卫表 、王的亚集 请暑岀 申第退 青迭择-请输人新作业的名称和犬1X整数:1150该次內存

19、分配丕会产生碎片已内存王采单4退岀请选择M请输入新作业的名称和大小 整数S3M该次內存配丕会产生碎片i己内存4JJ戌存新r 配汞R表 分春业更存內请页看出 i次申蕾_退 土 B20该2.3.4.00 0 0000212 3 4请煎择请输入新作业的名称和大小整数820该次內存分配会产生碎片将整块內存大1吟讯己岀去?2*总的空 床分区麦 分区序号大小 始址15003U15M218R三配00 0 U00000 0 U000030508S区始0 分己b2:3牛号 序1区I藝II回请页看K rrnnniiiiaiiErnnn 十*有-*攵请选择：33Q00Q分区序号32分区序号418配配3=二-二三-=

20、二卄0 U3 2氐0 S *5 8*配配rm配配卄八务卄己已空己已卄5 0 卄区址15184(102100021* 分始U4070廿闲心空卄的小 yon X 去女 000 3220M000M、-|74 3 812 3 4新 宣12 30分 己亜匕收 垂舉 主的业$ 请頁看出 申聖退 1请 业正 作 的称攵 朿蚤业刖 结业七盘表 想作畫业匱:2奮 10 择入入请页看出 临聾申蕾_退 閒常 頃兄看1.1 申氢退 :Program FilesMicrosoft Visual StudioMlyPrqjectsFirstFitDbugFirstFit.exe作业的名称和大小理数=6所*请资源已文叫系就所漲有的，请重新轴八!書欷:抚站朿的作业汨L-疗内配亍分冋 旦1.收 叹糸 凹请豆看匕3 - 坏4八 业70 的可Ml申翟_退 -12 3 4:2哪飯斯咅忝 SA.0请豆看 选零申-W旦退 .fw H四、实验总结通过此次的实验，让我对内存分配中首次适应算法更加熟悉，通过编程模拟实现操作 系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高根据已有原理 通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决 方案打下基础。