常见内存分配算法
一、首次适应算法
使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。
然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。
该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。
显然为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。
二、循环首次适应法
该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再每次从链首开始查找， 而是从上次找到的空闲分区开始查找，直至找到一个能满足要求的空闲分区，并从中划出一块来分给作业。 该算法能使空闲中的内存分区分布得更加均匀，但将会缺乏大的空闲分区。
三、最佳适应算法
该算法总是把既能满足要求，又是最小的空闲分区分配给作业。 为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。 这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的， 但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。 同时每次分配后必须重新排序，这也带来了一定的开销
四、最差适应算法
最差适应算法中，该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中分配（不能满足需要则不分配）。
很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观吸引力：
在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。 最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。 该算法克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。
1 // 常见内存分配算法.cpp : 定义控制台应用程序的入口点。
2 //
3
4
5
6
7 #include "stdafx.h"
8 #include
9 #include
10 #include
11
12
13 #define N 100
14 /*
15 * freelist为空闲区链表的头，它的下一个节点才指向空闲缓冲区
16 * freelist是按首地址来排序的，而不是按size来排序。
17 * 按首地址排序便于相邻空闲内存合并；按size大小来排序，便于分配内存
18 */
19
20 typedef struct _LIST_NODE
21 {
22 CHAR* StartAddress; //start addr 指向mem处开始的地址
23 INT BlockSize; //size of the free block
24 struct _LIST_NODE *NextNode; //next free block
25 }LIST_NODE,*PLIST_NODE;
26
27
28 CHAR MemoryPool[N]; //total memory pool
29 LIST_NODE FreeListHead; //head of free list, no value
30 /* init freelist to contain the whole mem */
31 VOID Init()
32 {
33 PLIST_NODE TempNode = (PLIST_NODE)malloc(sizeof(LIST_NODE));
34 TempNode->StartAddress = MemoryPool;
35 TempNode->BlockSize = N;
36 TempNode->NextNode = NULL;
37 FreeListHead.NextNode = TempNode;
38 }
39 /* remove a node ptr from the list whose previous node is prev */
40 void RemoveNode(PLIST_NODE CurrentNode, PLIST_NODE PrevNode)
41 {
42 PrevNode->NextNode = CurrentNode->NextNode;
43
44 //delete CurrentNode;
45 int a = 0;
46
47 }
48
49
50 /*
51 * 首次适配法：从自由空闲区中选取第一个合适空闲区来分配
52 * 返回分配内存区首地址
53 */
54
55 CHAR* FirstFit(int BlockSize)
56 {
57 PLIST_NODE CurrentNode, PrevNode;
58 CHAR* MemoryAddress;
59
60 for (PrevNode = &FreeListHead, CurrentNode = PrevNode->NextNode; CurrentNode; PrevNode = CurrentNode, CurrentNode = CurrentNode->NextNode)
61 if (CurrentNode->BlockSize > BlockSize)
62 {
63 MemoryAddress = CurrentNode->StartAddress;
64 CurrentNode->BlockSize -= BlockSize; //从空闲区去掉size空间
65 CurrentNode->StartAddress += BlockSize; //空闲区首地址往后移size个单位
66 return MemoryAddress; //返回申请到的空闲区 首地址
67 }
68 else if (CurrentNode->BlockSize == BlockSize)
69 {
70 MemoryAddress = CurrentNode->StartAddress;
71 RemoveNode(CurrentNode, PrevNode);
72 return MemoryAddress;
73 }
74 return NULL; //没有足够长的空闲内存
75 }
76
77 /* 最佳适配法：找到大小与size最接近的空闲区来分配 */
78 CHAR* BestFit(int BlockSize)
79 {
80 PLIST_NODE CurrentNode, PrevNode;
81 CHAR* MemoryAddress;
82 int v1 = N + 1;
83 PLIST_NODE minptr = NULL, minprev = NULL;
84
85 for (PrevNode = &FreeListHead, CurrentNode = PrevNode->NextNode; CurrentNode; PrevNode = CurrentNode, CurrentNode = CurrentNode->NextNode) {
86 if (CurrentNode->BlockSize >= BlockSize && CurrentNode->BlockSize - BlockSize < v1)
87 {
88 v1 = CurrentNode->BlockSize - BlockSize;
89 minptr = CurrentNode;
90 minprev = PrevNode;
91 }
92 }
93
94 if (minptr == NULL)//没有找到
95 return NULL;
96 CurrentNode = minptr;
97 PrevNode = minptr;
98 if (CurrentNode->BlockSize > BlockSize)
99 {
100 MemoryAddress = CurrentNode->StartAddress;
101 CurrentNode->BlockSize -= BlockSize;
102 CurrentNode->StartAddress += BlockSize;
103 return MemoryAddress;
104 }
105 else if (CurrentNode->BlockSize == BlockSize)
106 {
107 MemoryAddress = CurrentNode->StartAddress;
108 RemoveNode(CurrentNode, PrevNode);
109 return MemoryAddress;
110 }
111 return NULL;
112 }
113
114
115
116 /* prt: sizeof(int) contains size of the pool allocated
117 * 返回分配的空间首地址(不包括最前面的长度的4个字节)
118 */
119 CHAR* Memalloc(int size)
120 {
121 CHAR *v1 = BestFit(size + sizeof(int)); //此处选择分配算法
122 printf("allocating %d using firstfit...\n", size);
123 if (v1 == NULL)
124 return NULL;
125 *(int *)v1 = size; //分配的空闲内存区前面几个字节用于存放分配数
126 return v1 + sizeof(int);
127 }
128
129 /* add memptr of size to freelist, remember that block ptrs are stored on mem addr */
130 VOID AddToFreeList(CHAR *MemoryAddress, int BlockSize)
131 {
132 PLIST_NODE PrevNode, CurrentNode, v1;
133
134 for (PrevNode = &FreeListHead, CurrentNode = PrevNode->NextNode; CurrentNode && CurrentNode->StartAddress < MemoryAddress; PrevNode = CurrentNode, CurrentNode = CurrentNode->NextNode)
135 ;
136 v1 = (PLIST_NODE)malloc(sizeof(LIST_NODE));
137 v1->StartAddress = MemoryAddress;
138 v1->BlockSize = BlockSize;
139 v1->NextNode = CurrentNode;
140 PrevNode->NextNode = v1;
141 }
142
143 VOID PrintFreeList()
144 {
145 PLIST_NODE CurrentNode;
146 for (CurrentNode = FreeListHead.NextNode; CurrentNode; CurrentNode = CurrentNode->NextNode) {
147 printf("{%u %d}", CurrentNode->StartAddress, CurrentNode->BlockSize);
148 }
149 putchar('\n');
150 }
151 /* combine adj blocks of list if necessary */
152 VOID Coalesce()
153 {
154 PLIST_NODE PrevNode, CurrentNode;
155
156 for (PrevNode = &FreeListHead, CurrentNode = PrevNode->NextNode; CurrentNode; PrevNode = CurrentNode, CurrentNode = CurrentNode->NextNode) {
157 if (PrevNode != &FreeListHead && PrevNode->StartAddress + PrevNode->BlockSize == CurrentNode->StartAddress)
158 {
159 PrevNode->NextNode = CurrentNode->NextNode;
160 free(CurrentNode);
161 CurrentNode = PrevNode;
162 }
163 }
164
165 }
166 VOID MemFree(CHAR* CurrentNode)
167 {
168 int BlockSize = *(int *)(CurrentNode - sizeof(int));//找到已分配的空闲区大小(空闲区的前4个字节)
169 printf("freeing %d...\n", BlockSize);
170 AddToFreeList(CurrentNode - sizeof(int), BlockSize + sizeof(int));
171 Coalesce();
172 }
173
174
175
176 int main()
177 {
178 /*
179 CHAR *p1, *p2, *p3, *p4, *p5;
180 Init();
181 PrintFreeList();
182
183 p1 = Memalloc(10);//note：分配10个字节，但其前面还有4个字节用于指示长度的，所以共用了14字节
184 PrintFreeList();
185 p2 = Memalloc(15);
186 PrintFreeList();
187 p3 = Memalloc(23);
188 PrintFreeList();
189 p4 = Memalloc(3);
190 PrintFreeList();
191 p5 = Memalloc(8);
192 PrintFreeList();
193 MemFree(p1);
194 PrintFreeList();
195 MemFree(p5);
196 PrintFreeList();
197 MemFree(p3);
198 PrintFreeList();
199 p1 = Memalloc(23);
200 PrintFreeList();
201 p1 = Memalloc(23);
202 PrintFreeList();
203 MemFree(p2);
204 PrintFreeList();
205 p1 = Memalloc(3);
206 PrintFreeList();
207 MemFree(p4);
208 PrintFreeList();
209 p2 = Memalloc(1);
210 PrintFreeList();
211 MemFree(p1);
212 PrintFreeList();
213 MemFree(p2);
214 PrintFreeList();
215 return 0;
216 */
217
218
219 CHAR* v1 = (CHAR*)malloc(100);
220
221 int a = 0;
222 free(v1);
223 }