| 内存分配算法（FF、BF、MF） | 您所在的位置：网站首页 › 内存分配图怎么画 › 内存分配算法（FF、BF、MF） |
内存分配算法（FF、BF、MF）
|
动态分区分配
最近在学习操作系统内存分配方面的知识点，小小的总结一下知识点。 根据进程的实际需要，动态的为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用到的数据结构、分区分配算法和分区的分配与回收操作三方面的问题。 我的理解是，动态分区分配是按照作业需要的主存空间大小来分配的，当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表。
意思就是，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小、分区始址等数据项。 为了实现对分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部设置一些后向指针。通过这些就可以把所有的空闲分区链接成一个双向链。 分区分配操作 分配内存和回收内存 分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size, 表中每个空闲分区的大小可表示为m.size.若m.size-u.size≤size(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者。否则(即多余部分超过size)，便从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。 回收内存当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一: (1)回收区与插入点的前一个空闲分区F1相邻接。 此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 (2)回收分区与插入点的后一空闲分区F2相邻接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。 (3)回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F的表项和F1的首址，取消F2的表项，大小为三者之和。 (4)回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。 内存分配算法
首次适应算法（FirstFit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。 最佳适应算法（BestFit)：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。 最差适应算法（WorstFit)：从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。为适应此算法，空闲分区表（空闲区链）中的空闲分区按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。 伙伴算法（buddy）：使用二进制优化的思想，将内存以2的幂为单位进行分配，合并时只能合并是伙伴的内存块，两个内存块是伙伴的三个条件是： 1.大小相等 2.地址连续 3.两个内存块分裂自同一个父块（其实只要判断低地址的内存块首地址是否是与父块地址对齐，即合并后的首地址为父块大小的整数倍）使用lowbit等位运算可以o(1)判断。 内存分配算法实现（无伙伴算法）： #include #include using namespace std; #define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1 //完成 #define ERROR 0 //出错 #define MAX_length 640 //最大内存空间为640KB typedef int Status; int flag; typedef struct freearea//定义一个空闲区说明表结构 { long size; //分区大小 long address; //分区地址 int state; //状态 }ElemType; // 线性表的双向链表存储结构 typedef struct DuLNode { ElemType data; struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 } DuLNode,*DuLinkList; DuLinkList block_first; //头结点 DuLinkList block_last; //尾结点 Status alloc(int);//内存分配 Status free(int); //内存回收 Status First_fit(int);//首次适应算法 Status Best_fit(int); //最佳适应算法 Status Worst_fit(int); //最差适应算法 void show();//查看分配 Status Initblock();//开创空间表 Status Initblock()//开创带头结点的内存空间链表 { block_first=(DuLinkList)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.state=Free; return OK; } //分配主存 Status alloc(int ch) { int request = 0; coutrequest; if(requestdata.size-request; } else if(q->data.size > p->data.size) { q=p; ch=p->data.size-request; } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else if(q->data.size==request) { q->data.state=Busy; return OK; } else { 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; } return OK; } //最差适应算法 Status Worst_fit(int request) { int ch; //记录最大剩余空间 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); 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.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 ERROR;//没有找到空闲块 else if(q->data.size==request) { q->data.state=Busy; return OK; } else { 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; } return OK; } //主存回收 Status free(int flag) { DuLNode *p=block_first; for(int i= 0; i next; else return ERROR; p->data.state=Free; if(p->prior!=block_first && p->prior->data.state==Free)//与前面的空闲块相连 { p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; p=p->prior; } if(p->next!=block_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==block_last && p->next->data.state==Free)//与最后的空闲块相连 { p->data.size+=p->next->data.size; p->next=NULL; } return OK; } //显示主存分配情况 void show() { int flag = 0; cout |
由此也引入了空闲分区表和空闲分区链的概念
【本文地址】