资源描述
动态连续内存分配算法模拟实险报告实验目的与内容理解内存管理的相关理论，掌握连续动态分区内存管理的理论；通过对实际问题的编程实现，获得实际应用和编程能力。 编写程序实现连续动态分区内存管理方式，该程序管理一块虚拟内存，实现内存分配和回收功能。 通过设计流程并编写代码实现四种内存分配算法，最先适应算法，下次最先适应算法，最优适应算法，最坏适应算法。内存分配算法和回收算法的实现。概要设计本程序采用使用C+开发，共分为四大核心算法组成。1) 首次适应算法实现 从空闲分区表的第一个首地址查找，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。2) 循环首次适应分配算法实现 该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头(链首)开始查找，而就是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。3) 最佳适应算法实现 该算法从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区.自链头开始查找到第一个满足要求的自由分区分配。4) 最坏算法实现 该算法要扫描整个空闲分区或链表，挑选一个最大的空闲分区分割给作业使用。为了快速响应分配过程及较为明显的观察分配结果，程序设计中通过选择对应算法，通过Alloc函数中，指定了分配与回收过程，并打印出每一步的内存排列结果.每一步分配或回收失败，则给出提示或退出程序.设计思想与流程图首次适应算法在分配内存时，循环从链首开始顺序查找，直到找到能满足要求的分区为止；再按申请的大小，从该分区中划出一块内存空间分配，剩下的空闲分区仍留在空闲链中。若从首地址直到末尾都不能找到一个能满足要求的大小分区，则内存分配失败。循环首次适应算法此算法是对首次适应算法的一个变种. 在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。最佳适应算法它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。最坏适应算法也称最差适配算法，从全部空闲区中找出能满足作业要求的分区、且大小最大的空闲分区，使链表中的结点大小趋于均匀。回收内存空间流程加收分区内存空间时，如前面有空闲空间则合并至前面的空闲空间，再检则后面是否有空闲空间，如果有后面的空闲空间合并至当前分区空闲空间,合并为一个大的空闲空间源程序分析内存管理设计MemArea 内存区域,链表中的data, 标识分区名,分区大小,分区状态typedef struct FreeArea /定义一个空闲区说明表结构 long size; /分区大小 long address; /分区地址 int state; /状态 ElemType;线性表的双向链表存储结构,模拟连续内存空间typedef struct DLNode ElemType data; struct LNode *prior; /前趋指针 struct LNode *next; /后继指针 LNode, *DLinkList;算法函数,详细实现在源代码中/首次适应算法status FirstFit(int); /循环首次适用status NextFit(int); /最佳适应算法 status BestFit(int); /最坏适应算法 status WorstFit(int); 源代码/* * 连续动态内存分配模拟实现 * author 名字（写自己名字） * date 2021-05-02 */#include#includeusing namespace std;#define FREE 0 /空闲状态#define USED 1 /已用状态#define OK 1 /完成标识#define ERR 0 /错误标识#define MAX_LEN 640 /定义最大主存信息640KBtypedef int status;int flag;/标志位 0为空闲区 1为已分配 typedef struct MemArea /定义一个空闲区说明表结构 long size; /分区大小 long addr; /分区地址 int state; /状态EleType; typedef struct DLNode/ 线性表的双向链表存储结构 EleType data; struct DLNode *prior; /前趋指针 struct DLNode *next; /后继指针 DLNode, *DLinkList;DLinkList lastfind;DLinkList link_first; /头结点DLinkList link_last; /尾结点void Run(int);/内存分配status free(int); /内存回收status FirstFit(int); /首次适应算法status NextFit(int); /循环首次适用法status BestFit(int); /最佳适应算法status WorstFit(int); /最差适应算法void showMem(); /显示分配status initMem(); /创建空间表 void Sim_First(int); /模拟首次适应算法status free_by_size(int); /按分配大小释放,根据作业模拟status ChooseFit(int, int); /模拟中选择算法/开创带头结点的内存空间链表status initMem() link_first = (DLinkList)malloc(sizeof(DLNode); link_last = (DLinkList)malloc(sizeof(DLNode); link_first-prior = NULL; link_first-next = link_last; link_last-prior = link_first; link_last-next = NULL; link_last-data.addr = 0; link_last-data.size = MAX_LEN; link_last-data.state = FREE; return OK;void Run(int ch)/分配主存 return Sim_First(ch);status ChooseFit(int ch, int size) switch (ch) case 0: return FirstFit(size); break; case 1: return NextFit(size); break; case 2: return BestFit(size); break; case 3: return WorstFit(size); break; default: return ERR; void Sim_First(int ch) int size = 130; if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; showMem(); else cout 内存不足,分配失败. endl; exit(1); size = 60; if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; showMem(); else cout 内存不足,分配失败. endl; exit(1); size = 100; if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; showMem(); else cout 内存不足,分配失败. endl; exit(1); if (free_by_size(60) = OK) cout free(60K) 释放成功. endl; showMem(); else cout 内存释放失败; exit(1); size = 200; /p3 if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; else cout 内存不足,分配失败. endl; showMem(); if (free_by_size(100) = OK) cout free(100K) 释放成功. endl; else cout 内存释放失败; showMem(); if (free_by_size(130) = OK) cout free(130K) 释放成功. endl; else cout 内存释放失败; showMem(); size = 140; /p4 if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; else cout 内存不足,分配失败. endl; showMem(); size = 60; /p5 if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; else cout 内存不足,分配失败. endl; showMem(); size = 50; /p6 if (ChooseFit(ch, size) = OK) cout malloc( size K)分配成功. endl; else cout 内存不足,分配失败. endl; showMem(); if (free_by_size(60) = OK) cout free(60K) 释放成功. endl; else cout data.size = request; temp-data.state = USED; DLNode *p = link_first-next; while (p) if (p-data.state = FREE & p-data.size = request) /有大小恰好合适的空闲块 p-data.state = USED; return OK; break; if (p-data.state = FREE & p-data.sizerequest) /有空闲块能满足需求且有剩余 temp-prior = p-prior; temp-next = p; temp-data.addr = p-data.addr; p-prior-next = temp; p-prior = temp; p-data.addr = temp-data.addr + temp-data.size; p-data.size -= request; return OK; break; p = p-next; return ERR;/*循环首次适应算法*request为用户输入的进程请求空闲块的大小*/status NextFit(int request) DLinkList temp = (DLinkList)malloc(sizeof(DLNode); temp-data.size=request; temp-data.state=USED; /lastfind为上次分配空闲的位置，如果是首次分配就不存在lastfind /首次分配不存在空闲位置lastfind if(lastfind) while(lastfind) if(lastfind-data.state=FREE&lastfind-data.size=request) /等于则直接修改该状态 lastfind-data.state=USED; lastfind=lastfind-next; return OK; break; if(lastfind-data.state=FREE&lastfind-data.sizerequest) /寻找内存中空闲块大于等于请求的空闲块 temp-prior=lastfind-prior; temp-next=lastfind; temp-data.addr=lastfind-data.addr; /大于则分配response大小后把剩余的存为空闲块 lastfind-prior-next=temp; lastfind-prior=temp; lastfind-data.addr=temp-data.addr+temp-data.size; lastfind-data.size=lastfind-data.size-request; lastfind=lastfind-next; return OK; break; /找到则标记为lastfind lastfind=lastfind-next; else DLNode *p = link_first-next; while(p) if(p-data.state=FREE&p-data.size=request) p-data.state=USED; lastfind=p-next; return OK; break; if(p-data.state=FREE&p-data.sizerequest) temp-prior=p-prior; temp-next=p; temp-data.addr=p-data.addr; p-prior-next=temp; p-prior=temp; p-data.addr=temp-data.addr+temp-data.size; p-data.size=p-data.size-request; lastfind=p-next; return OK; break; p=p-next; return OK;/* * 最佳适应算法 */status BestFit(int request) int ch; /记录最小剩余空间 DLinkList temp = (DLinkList)malloc(sizeof(DLNode); temp-data.size = request; temp-data.state = USED; DLNode *p = link_first-next; DLNode *q = NULL; /记录最佳插入位置 while (p) /循环查找初始化最小空间和最佳插入点 if (p-data.state = FREE & (p-data.size = request) if (q = NULL) q = p; ch = p-data.size - request; else if (q-data.size p-data.size) q = p; ch = p-data.size - request; p = p-next; if (q = NULL) return ERR;/没有找到空闲块 else if (q-data.size = request) q-data.state = USED; return OK; else temp-prior = q-prior; temp-next = q; temp-data.addr = q-data.addr; q-prior-next = temp; q-prior = temp; q-data.addr += request; q-data.size = ch; return OK; return OK;/* * 最差适应算法 */status WorstFit(int request) int ch; /记录最大剩余空间 DLinkList temp = (DLinkList)malloc(sizeof(DLNode); temp-data.size = request; temp-data.state = USED; DLNode *p = link_first-next; DLNode *q = NULL; /记录最佳插入位置 while (p) /初始化最大空间和最佳位置 if (p-data.state = FREE & (p-data.size = request) if (q = NULL) q = p; ch = p-data.size - request; else if (q-data.size data.size) q = p; ch = p-data.size - request; p = p-next; if (q = NULL) return ERR; /没有找到空闲块 else if (q-data.size = request) q-data.state = USED; return OK; else temp-prior = q-prior; temp-next = q; temp-data.addr = q-data.addr; q-prior-next = temp; q-prior = temp; q-data.addr += request; q-data.size = ch; return OK; return OK;/* * 按照大小回收内存 */status free_by_size(int size) int flag = 0; DLNode *p = link_first-next; while (p) if(p-data.size=size & p-data.state != FREE) free(flag); return OK; break; else p = p-next; flag+; return ERR;/* * 主存回收 */status free(int flag) DLNode *p = link_first; for (int i = 0; i next; else return ERR; p-data.state = FREE; if (p-prior != link_first & p-prior-data.state = FREE)/与前面的空闲块相连 p-prior-data.size += p-data.size;/空间扩充,合并为一个 p-prior-next = p-next;/去掉原来被合并的p p-next-prior = p-prior; p = p-prior; if (p-next != link_last & p-next-data.state = FREE)/与后面的空闲块相连 p-data.size += p-next-data.size;/空间扩充,合并为一个 p-next-next-prior = p; p-next = p-next-next; if (p-next = link_last & p-next-data.state = FREE)/与最后的空闲块相连 p-data.size += p-next-data.size; p-next = NULL; return OK;/* * 显示主存分配情况 */void showMem() int flag = 0; cout 内存分配情况:n; cout next; cout 分区号t起始地址t分区大小t状态n; while (p) cout flag+ t; cout data.addr tt; cout data.size data.state = FREE) cout 03332m 空闲 0330mn; else cout next; cout +nn;int main() /主函数 int fit;/算法选择标记 cout 内存分配算法：n; cout fit; while (fit3) cout fit; switch (fit) case 0: cout 0.首次适应算法n; break; case 1: cout 1.循环首次适应算法n; break; case 2: cout 2.最佳适应算法n; break; case 3: cout 3.最坏适应算法n; break; default: exit(1); initMem(); /开创空间表 showMem(); Run(fit);运行截图首次适应算法循环首次适应算法最佳适应算法最坏适应算法总结与体会通过对本次连续动态分区分配算法实现，理解了连续内存分配和内存回收的机制，通过对首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的设计,在不懂的地方,在网上搜索相应的资料查找及摸索算法过程,不断去试错,去理解实现过程,不仅提高了C+的编程能力, 同时加深了各算法的实现细节. 从而敬佩前辈在对内存的分配的算法上的精益求精,
展开阅读全文