操作系统|操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF）） c++|算法|操作系统|c语言

算法介绍一、动态分区分配算法
为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的研究，于是产生了许多动态分区分配算法。传统的四种分配算法，它们都属于顺序式搜索算法。
二、分区分配操作
在动态分区存储管理方式中，主要的操作是分配内存和回收内存。
1)分配内存
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size,表中每个空闲分区的大小可表示为m.size. 若m.size-u.size≤size(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者。否则(即多余部分超过size),便从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图示出了分配流程。

文章图片

2)回收内存
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
(1)回收区与插入点的前一个空闲分区F1 相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F的大小。如图（a）。
(2)回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。如图（b）
(3)回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F的表项和F的首址，取消F2的表项，大小为三者之和。如图（c）。
(4)回收区既不与F邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

文章图片

内存回收时流程图：

文章图片

三、基于顺序搜索的动态分区分配算法
为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。所谓顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。基于顺序搜索的动态分区分配算法有如下四种:首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法，下面分别进行介绍。
1.首次适应(first fit, FF)算法
我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区,从而保留了高址部分的大空闲区。这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会
留下许多难以利用的、很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。
2.循环首次适应(next fit，NF)算法
为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。
3.最佳适应(best fit，BF)算法
所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成——空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的碎片。
4.最坏适应(worst fit, WF)算法
由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反:它在扫描整个空闲分区表或链表时，总是挑选-一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。实际上，这样的算法未必是最坏的，它的优点是可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。同时，最坏适应分配算法查找效率很高，该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成——空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。
【操作系统|操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））】直接代码（实验原因封装在一块）
.h文件（头文件）

#pragma once #include using namespace std; typedef struct Node { int pid; //分区号 long size; //分区大小 long start_locat; //分区起始地址 int status; //分区状态 struct Node* next; struct Node* perior; }Node, *PNode; void Init_list(PNode list); //初始化头结点 void Creat_list(PNode list); //初始化链表 PNode Insert_Node(); //新插入链表 long* _Sort_min(long* p); //小到大因为实验量小采用冒泡排序 long* _Sort_max(long* p); //大到小因为实验量小采用冒泡排序 void First_fit(PNode list); //FF首次适应算法 void Next_fit(PNode list); //循环首次适应 void Best_fit(PNode list); //BF 最佳适应算法 void Worst_fit(PNode list); //最欢适应算法 void Release_Mem(PNode list); //回收内存 void Show(PNode list);

.cpp文件

#include #include"list.h"#define MAX_ALLOC_SIZE 600000 long start_add, end_add, memory_size; // 起始地址，终止地址，内存大小 int free_num = 0; Node* Flag_Node = NULL; void Init_list(PNode list) { assert(NULL != list); list->next =list; list->perior = list; list->start_locat = start_add; list->size = 0; list->status = 1; } void Creat_list(PNode list) { assert(NULL != list); int _id = -1, _num = 0; long _size = -1; long _locat = list->start_locat; cout << "请输入申请资源的进程个数：" << endl; cin >> _num; for (int i = 0; i <= _num; i++) { Node* newnode = (Node*)malloc(sizeof(Node)); assert(NULL != newnode); if (i < _num) { cout << "请输入第" << i + 1 << "个进程调入的分区号及其大小:" << endl; cin >> _id >> _size; newnode->pid = _id; newnode->size = _size; newnode->start_locat = _locat; newnode->status = 1; _locat += _size; } else { newnode->pid = -1; newnode->size = memory_size - _locat; newnode->start_locat = _locat; newnode->status = 0; free_num++; } PNode ptr = list; for (ptr; ptr->next != list; ptr = ptr->next); newnode->next = list; newnode->perior = ptr; ptr->next = newnode; list->perior = newnode; } } PNode Insert_Node() { Node* newnode = (Node*)malloc(sizeof(Node)); assert(NULL != newnode); int _id = 0; long _size = 0; cout << "请输入进程调入的分区号及其大小:" << endl; cin >> _id >> _size; newnode->next = NULL; newnode->perior = NULL; newnode->pid = _id; newnode->size = _size; newnode->start_locat = 0; newnode->status = 0; return newnode; } void First_fit(PNode list) { assert(NULL != list); PNode _head = Insert_Node(); PNode ptr = list; while (ptr->next != list) { PNode cur = ptr->next; if (cur->status==0&&cur->size > _head->size) { _head->next = cur; _head->perior = ptr; cur->perior = _head; ptr->next = _head; _head->status = 1; _head->start_locat = ptr->start_locat + ptr->size; cur->start_locat = _head->start_locat + _head->size; cur->size = cur->size - _head->size; break; } else if (cur->status == 0&&cur->size == _head->size) { cur->pid = _head->pid; cur->status = 1; free_num--; break; } ptr = ptr->next; } if (ptr->next->status == 0) { cout << "没有适合的申请位置" << endl; } } void Next_fit(PNode list) { assert(NULL != list); PNode _head = Insert_Node(); PNode p = list; if (Flag_Node != NULL) { p = Flag_Node; } PNode ptr = p; while (ptr->next != p) { PNode cur = ptr->next; if (cur->status == 0 && cur->size > _head->size) { _head->next = cur; _head->perior = ptr; cur->perior = _head; ptr->next = _head; _head->status = 1; _head->start_locat = ptr->start_locat + ptr->size; cur->start_locat = _head->start_locat + _head->size; cur->size = cur->size - _head->size; Flag_Node = _head; break; } else if (cur->status == 0 && cur->size == _head->size) { cur->pid = _head->pid; cur->status = 1; Flag_Node = cur; free_num--; break; } ptr = ptr->next; } if (ptr->next->status == 0) { cout << "没有适合的申请位置" << endl; } } long* _Sort_min(long* p) { assert(NULL != p); for (int i = 0; i < free_num-1; i++) { for (int j = 0; j < free_num - 1 - i; j++) { if (p[j] > p[j + 1]) { long tmp = p[j]; p[j] = p[j + 1]; p[j + 1] = tmp; } } } return p; } void Best_fit(PNode list) { assert(NULL != list); PNode _head = Insert_Node(); long* p = (long*)malloc(sizeof(long)*(free_num)); assert(NULL!=p); PNode ptr = list->next; long i = 0, j = 0; while (ptr!= list) { if (ptr->status == 0) { *(p+i) = ptr->size; i++; } ptr = ptr->next; } long* q = _Sort_min(p); while (j < free_num) { if (_head->size < q[j]) { break; } j++; } PNode cur = list; while (cur->next != list) { PNode tr = cur->next; if (tr->status==0&&tr->size == q[j]) { if (_head->size < tr->size) { _head->next = tr; _head->perior = cur; tr->perior = _head; cur->next = _head; _head->status = 1; _head->start_locat = cur->start_locat + cur->size; tr->start_locat = _head->start_locat + _head->size; tr->size = tr->size - _head->size; break; } else if(_head->size==tr->size) { tr->pid = _head->pid; tr->status = 1; break; } } cur = cur->next; } } long* _Sort_max(long* p) { assert(NULL != p); for (int i = 0; i < free_num - 1; i++) { for (int j = 0; j < free_num - 1 - i; j++) { if (p[j] <= p[j + 1]) { long tmp = p[j]; p[j] = p[j + 1]; p[j + 1] = tmp; } } } return p; } void Worst_fit(PNode list) { assert(NULL != list); PNode _head = Insert_Node(); long* p = (long*)malloc(sizeof(long) * (free_num)); assert(NULL != p); PNode ptr = list->next; long i = 0, j = 0; while (ptr != list) { if (ptr->status == 0) { *(p + i) = ptr->size; i++; } ptr = ptr->next; } long* q = _Sort_max(p); PNode cur = list; while (cur->next != list) { PNode tr = cur->next; if (tr->status == 0 && tr->size == q[j]) { if (_head->size < tr->size) { _head->next = tr; _head->perior = cur; tr->perior = _head; cur->next = _head; _head->status = 1; _head->start_locat = cur->start_locat + cur->size; tr->start_locat = _head->start_locat + _head->size; tr->size = tr->size - _head->size; break; } else if (_head->size == tr->size) { tr->pid = _head->pid; tr->status = 1; break; } } cur = cur->next; } } void Release_Mem(PNode list) { assert(NULL != list); int delet_id = 0; cout << "请输入需要回收的进程号：" << endl; cin >> delet_id; PNode ptr = list; while (ptr->next != list) { PNode cur = ptr->next; if (cur->pid == delet_id) { if (cur->status == 0) { cout << "回收错误请输入正确进程号" << endl; break; } else { if (ptr->status == 0&&cur->next->status==1)//1 { ptr->size = ptr->size + cur->size; cur->next->perior = ptr; ptr->next = cur->next; free(cur); cur = NULL; break; } else if (ptr->status == 1 && cur->next->status == 0)//2 { PNode p = cur->next; cur->size = cur->size + p->size; p->next->perior = cur; cur->next = p->next; cur->status = 0; free(p); p = NULL; break; } else if (ptr->status == 0 && cur->next->status == 0)//3 { PNode p = cur->next; ptr->size = cur->size + ptr->size + p->size; p->perior = ptr; ptr->next = p; free(cur); cur = NULL; p->next->perior = ptr; ptr->next = p->next; free(p); p = NULL; free_num--; break; } else//4 { cur->status = 0; free_num++; break; }}} ptr = ptr->next; } } void Show(PNode list) { assert(NULL != list); printf("分区号码分区大小分区始址分区状态\n"); PNode ptr = list; while (ptr->next!=list) { ptr = ptr->next; if (ptr->status == 0) { printf("%6d%6dk%6dk空闲\n",ptr->pid, ptr->size,ptr->start_locat); } else { printf("%6d%6dk%6dk占用\n",ptr->pid, ptr->size, ptr->start_locat); } } }

.cpp文件（主函数）

int main() { struct Node head; int select = 1; cout << "请输入请初始化内存块的首地址及内存大小：" << endl; cin >> start_add >> memory_size; if (memory_size > MAX_ALLOC_SIZE) { cout << "申请内存超过内存大小阈值！" << endl; return -1; } Init_list(&head); Creat_list(&head); Show(&head); while (1) { cout << "******************************************\n"; cout << "*****1.******* 首次适应算法 ************\n"; cout << "*****2.******循环首次适应算法 ************\n"; cout << "*****3.******最佳适应算法************\n"; cout << "*****4.******最坏适应算法************\n"; cout << "*****5.*******回收内存*********\n"; cout << "*****0.**********退出*********************\n"; cout << "请选择:> "; cin >> select; switch (select) { case 1: First_fit(&head); Show(&head); break; case 2: Next_fit(&head); Show(&head); break; case 3: Best_fit(&head); Show(&head); break; case 4: Worst_fit(&head); Show(&head); break; case 5: Release_Mem(&head); Show(&head); break; default: break; } } return 0; }

第一次写不太好见谅
（1）以首地址为0内存大小1024对链表初始化