《存储管理动态分区分配算法的模拟.docx》由会员分享，可在线阅读，更多相关《存储管理动态分区分配算法的模拟.docx（19页珍藏版）》请在三一文库上搜索。
1、存储管理动态分区分配算法的模拟一(题目：存储管理一动态分区分配算法的模拟二(任务:设计主界面以灵活选择某算法，且以下算法都要实现：首次适应算 法、 循环首次适应算法、最佳适应算法；。三(思想:对任务进行构思和设想。(1)首次适应算法：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺 巡查找，直到找到一个大小能够满足要求的空闲分区为止；然后再按照作业的大小， 从该分区中划出一块内存空间分配给请求者，余下的空闲区间仍留在空闲链中。若从 链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算 法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空
2、闲区。这 给为以后到达的大作业分配大的内存空间创造了条件。(2)循环首次适应算法该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都 从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至 找到 一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。 为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采 用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则返回 到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。(3)最佳适应算法是将最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找
3、，该算法要 求将所有的空闲分区按照某容量以从小到大的顺序形成一空闲分区链。这样，第一次 找到的能满足要求的空闲区，必然是最佳的。(4)内存回收:将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断 该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一 个空闲块，同时修改分区大小及起始地址。四(目的:在构思中提出要达到的目的。(1)按照首次适应算法对内存进行分配，得到(2)按照循环首次适应算法对内存(3)按照最佳适应算法对内存进行分配(4)在作业完成时，释放作业所在内存块，使其能够再次被利用五(方案:对构思的细化，提出粗略的方案。(1)首次适应算法：设立头
4、指针，每次从头指针开始查找，进行内存分配(2)最佳适应算法：设立一个指针纪录最佳位置，然后根据内存大小，对最佳位 置进行分配(3)循环首次适应算法：设立查找指针，查找指针初始为链首指针，最后位置为 查找指针，返回查找指针，第二次运行时从查找指针开始查找。(4)内存回收：将释放的空间与前后空闲状态区间合并，改写空闲区间地址和大 小六(框图:根据方案画出框图并审核框图。七(程序:是实施框图的主体并运行和修改。1 .有大小恰好合适的空闲块if(p-data.state=Free & p-data.size=request) p-data.state=Busy;p-data,ID=ID;return
5、OK;break; )2 .有空闲块能满足需求且有剩余”if(p-data.state=Free & p-data.sizerequest) (temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address; p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;)3 .回收内存if(p-data.lD=ID)p-data.state=Free;p-data.lD=F
6、ree;if(p-prior-data.state=Free)/ 与前面的空闲块相连 prior-data.size+=p-data.size; p-prior-next=p-next;p-next-prior=p-prior; if(p-next-data.state=Free)/ 与后面的空闲块相连(p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;八（文档：运行环境，输入条件，输出结果，整理成文。1 .运行环境：操作系统 WINDOWS XP编译软件 Microsoft Visual C+电脑配置：主
7、频3.0GHz内存512MB2 .输入条件作业1申请130KB作业1申请60KB作业1申请100KB作业1释放130KB作业1申请100KB作业1释放60KB九（总结：谈心得体会，特别是开发一个软件的体会。开发一个软件需要有软件需求分析，软件流程图，根据流程进行软件的编写。在编写软件时需要很好的结构感，编写的程序需要有框架，编写的程序需要补语句说明，让观看着更好的了解程序，使用程序十(附件:完整程序#include #include# define Free 0 / 空闲状态# define Busy 1 / 已用状态# define OK 1 / 完成# define ERROR 0 / 出
8、错# define MAXJength 640 / 最大内存空间为 640KB typedef int Status; typedef struct freearea/定义一个空闲区说明表结构int ID; 分区号long size; /分区大小long address; / 分区地址int state; / 状态ElemType;/线性表的双向链表存储结构typedef structDuLNode 双向链表 (ElemType data;struct DuLNode *prior; / 前趋指针struct DuLNode *next; /后继指针DuLNode,*DuLinkList;Du
9、LinkList block_first; / 头结点DuLinkList blockjast; / 尾结点Status alloc(int);/内存分配Status free(int); /内存回收首次适应算法最佳适应算法循环首次适应算法Status First_fit(int,int);/Status Best_fit(int,int); /Status Next_fit(int,int); / void show();/ 查看分配Status lnitblock();/ 开创空间表Status lnitblock()/开创带头结点的内存空间链表block_first=(DuLinkLis
10、t)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_last-prior=block_first;block_last-next=NULL;block_last-data.address=0;block_last-data.size=MAX_length;block_last-data.lD=0;block_last-data.state=Free;return OK;/分配主存Status
11、alloc(int ch) int ID,request;coutvv”请输入作业(分区号)cinID;coutw”请输入需要分配的主存大小(单位:KB):;cinrequest;if(requestdata.lD=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)(if(p-data.state=Free & p-data.size=request)有大小恰好合适的空闲块p-data.state=Busy;p-data.lD=ID;return OK;break;)if(p-d
12、ata.state=Free & p-data.sizerequest)有空闲块能满足需求且有剩余“temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break; )p=p-next; )return ERROR; )/最佳适应算法 StatusBest_fit(int IDJnt request)/
13、传入作业名及申请量 (int ch; 记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp-data.lD=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; 记录最佳插入位置while(p) /初始化最小空间和最佳位置 (if(p-data.state=Free &(p-data.sizerequest | p- data.size=request) q=p;ch=p-data.size-
14、request;break; )p=p-next;while(p)if(p-data.state=Free & p-data.size=request)空闲块大小恰好合适p-data.lD=ID;p-data.state=Busy;return OK;break;)if(p-data.state=Free & p-data.sizerequest)空闲块大于分配需求if(p-data.size-requestdata.size-request;/ 更新剩余最小值q=P； 更新最佳位置指向)p=p-next;)if(q=NULL) return ERROR;没有找到空闲块else/找到了最佳位置
15、并实现分配temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address; q-prior-next=temp;q-prior=temp;q-data.address+=request; q-data.size=ch;return OK;/循环首次适应算法Status Next_fit(int IDJnt request)/传入作业名及申请量/为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.lD=ID;temp-data.siz
16、e=request;temp-data.state=Busy;static DuLNode *p=block_first-next;/ 定义静态指针变量if(p-data.sizenext;while(p)if(p-data.state=Free & p-data.size=request)有大小恰好合适的空闲块p-data.state=Busy;p-data.lD=ID;return OK;break;)if(p-data.state=Free & p-data.sizerequest)/有空闲块能满足需求且有剩余“ temp-prior=p-prior;temp-next=p;temp-d
17、ata.address=p-data.address; p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size; p-data.size- =request;return OK;break;p=p-next;)return ERROR;)/主存回收Statusfree(int ID)DuLNode *p=block_first;while(p)if(p-data.lD=ID)p-data.state=Free;p-data.lD=Free;if(p-prior-data.state=Free)
18、/ 与前面的空闲块相连prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;)if(p-next-data.state=Free)/ 与后面的空闲块相连 p-data.size+=p-next-data.size;p-next-next-prior=p-prior;p-prior-next=p-next;心 reak;)p=p-next;)return OK;)/显示主存分配情况void show()Coutvv”+rT; coutvv+ 主存分配情况+n”；coutvv+rT; DuLNode*p=bloc
19、k_first-next;while(p)(cout分区号:；if(p-data.ID=Free) coutFree,endl;else coutp-data.lDendl;coutn 起文台地址 :,p-data.addressendl; coutM 分区大小:np-data.size KBHendl;coutH 状 态:;if(p-data.state=Free) cout空闲vvendl;else cout已分配 nendl;coutn“vvendl;p=p-next; /主函数voidmain()(loop: int ch;算法选择标记cout*动态分区分配方式的模拟优cout*n;c
20、outn*n;cout-* 1)首次适应算法2)最佳适应算法3)循环首次适应算法当n”;coutn*n;* coutn*n;coutvv”请选择分配算法:；cinch;lnitblock(); /开创空间表int choice; 操作选择标记while(1)(*coutfl*nH;coukl* 1:分配内存2:回收内存*n”;coutH* 3:查看分配0:退出*nn;*文* coutncoutvv”请输入您的操作: cinchoice;if(choice=1) alloc(ch); 分配内存 elseif(choice=2) / 内存回收(int ID;coutvv”请输入您要释放的分区号：“；cinID;free(ID);)else if(choice=3) show();/显示主存else if(choice=0) goto loop; / 退出 else /输入操作有误cout输入有误，请重试vvendl;continue;)