操作系统——存储管理大作业
实验要求
用malloc申请一块1M字节的内存空间作为自己的空闲内存
实现自己的void *myalloc(int size) 和int myfree(void *ptr)函数，用于分配和回收内存，替代malloc和free函数
采用最先适应、最优适应或最差适应分配算法对空闲内存进行管理
注意：实现之前一定要理解malloc和free的底层实现原理
实现
定义BlockNode存储内存块信息
先通过_aligned_malloc申请一块8字节对齐的内存(也可以采用VirtualAlloc分配)，然后实现malloc和free函数对这块内存进行管理。
这里将内存以块(Block)的方式进行管理，每块内存分为标记区(Header)和数据区(Data)，块的定义如下：
1
2
3
4
5
6
7
|
struct BlockNode{
BlockNode* m_next;
size_t m_size;
};
|
Header中记录了指向下一块内存的指针和一个size_t类型的m_size记录这块内存数据的大小
构造MemAllocator类管理内存
定义一个MemAllocator类，类中维持一个指向所有空闲内存块的m_freeList。在类的构造函数中通过_aligned_malloc申请一块8字节对齐的内存，除了申请内存外，构造构造函数还负责初始化m_freeList(直接在申请的内存上构建一个空闲块并将其添加到freelist中)，并在析构函数中释放了这块内存。
m_numAllocations记录了申请和释放内存的次数(每次申请内存时加一，释放时减一)，m_remainSize记录了空闲块数据区的总大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class MemAllocator
{
public:
MemAllocator(size_t pSize, SEARCH_MODE pMode) {
m_size = pSize * 8;
m_data = _aligned_malloc(m_size, 8);
m_mode = pMode;
memset(m_data, 0, m_size);
InitFreeList(m_data, m_size);
cout << "申请内存空间大小为：" << m_size << "B" << endl;
cout << "内存空间实际剩余为：" << m_remainSize << "B" << endl;
cout << "内存空间首地址为：0x" << m_data << endl;
}
void InitFreeList(void* pStart, size_t pSize){
assert(pStart != nullptr);
m_numAllocations = 0;
m_remainSize = pSize - sizeof(BlockNode);
m_freeList = static_cast<BlockNode*>(pStart);
m_freeList->m_next = nullptr;
m_freeList->m_size = m_remainSize;
}
~MemAllocator() {
if (m_data != nullptr) {
_aligned_free(m_data);
}
}
private:
BlockNode* m_freeList;
void* m_data;
size_t m_size;
size_t m_numAllocations;
size_t m_remainSize;
SEARCH_MODE m_mode;
};
|
每次申请内存时需要在FreeList中找到合适大小的空闲内存块，这是可以采用两种不同的查找方法：
- First fit，返回第一个数据区大小大于等于所申请内存的空闲块。
- Best fit，检查所有块，返回数据区和所申请内存大小差距最小且大于等于所需内存的空闲块。
- Worst fit，和Best类似，返回数据区和所申请内存大小差距最大且大于等于所需内存的空闲块（代码略）。
1
2
3
4
5
6
7
8
9
10
11
| enum class SEARCH_MODE{
FIRST_FIT,
BEST_FIT,
WORST_FIT
};
bool GetProperBlock(size_t pSize, SEARCH_MODE pMode, BlockNode** pPrevNode, BlockNode** pFoundNode) {
if (pMode == SEARCH_MODE::FIRST_FIT) {
return GetFirstFitBlock(pSize, pPrevNode, pFoundNode);
}
return GetBestFitBlock(pSize, pPrevNode, pFoundNode);
}
|
First fit的查找实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool GetFirstFitBlock(size_t pSize, BlockNode** pPrevNode, BlockNode** pFoundNode) {
BlockNode* prev = nullptr;
BlockNode* curr = m_freeList;
bool success = false;
while (curr != nullptr){
if (curr->m_size >= pSize){
success = true;
break;
}
prev = curr;
curr = curr->m_next;
}
*pPrevNode = prev;
*pFoundNode = curr;
return success;
}
|
Best fit的查找实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| bool GetBestFitBlock(size_t pSize, BlockNode** pPrevNode, BlockNode** pFoundNode){
BlockNode* prev = nullptr;
BlockNode* curr = m_freeList;
bool success = false;
BlockNode* best = nullptr;
BlockNode* bestPrev = nullptr;
size_t bestSize = m_size;
while (curr != nullptr){
size_t currSize = curr->m_size;
if (currSize >= pSize){
success = true;
if (currSize < bestSize){
bestSize = currSize;
best = curr;
bestPrev = prev;
}
}
prev = curr;
curr = curr->m_next;
}
*pPrevNode = bestPrev;
*pFoundNode = best;
return success;
}
|
SplitBlock
若找到的空闲内存块的大小size > 所需内存大小+sizeof(BlockNode)，则可以将该空闲块分裂为两个新的块，并将新分出的块插入到m_freeList中：
1
2
3
4
5
6
7
8
9
10
| void SplitBlock(BlockNode* pOld, size_t pSize){
assert(pOld != nullptr);
size_t oldBlockSize = pOld->m_size;
assert(oldBlockSize > pSize);
BlockNode* newBlock = pOld + (pSize + sizeof(BlockNode)) / 8;
newBlock->m_size = oldBlockSize - pSize - sizeof(BlockNode);
pOld->m_size = pSize;
InsertNode(pOld, newBlock);
cout << "Split block" << endl;
}
|
m_freeList的插入和删除操作定义如下（均需要插入或删除节点的前驱结点，若前驱结点为空则需要操作的节点为m_freeList的头节点）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void RemoveNode(BlockNode* pPrev, const BlockNode* pDelete){
assert(pDelete != nullptr);
if (pPrev != nullptr){
pPrev->m_next = pDelete->m_next;
}
else{
m_freeList = pDelete->m_next;
}
}
void InsertNode(BlockNode* pPrev, BlockNode* pNew){
assert(pNew != nullptr);
if (pPrev != nullptr){
pNew->m_next = pPrev->m_next;
pPrev->m_next = pNew;
}
else{
pNew->m_next = m_freeList;
m_freeList = pNew;
}
}
|
myalloc实现
myalloc的完整定义如下(myalloc时每次申请的内存大小会被缩放为8的倍数)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| void* myalloc(size_t pSize){
size_t dataSize = pSize * 8;
if (dataSize <= m_remainSize){
BlockNode* prev = nullptr;
BlockNode* found = nullptr;
if (GetProperBlock(dataSize, m_mode, &prev, &found)){
assert(found != nullptr);
size_t founBlockSize = found->m_size;
size_t allocateSize = founBlockSize + sizeof(BlockNode);
if (founBlockSize > (dataSize + sizeof(BlockNode))){
SplitBlock(found, dataSize);
allocateSize = dataSize + sizeof(BlockNode);
}
RemoveNode(prev, found);
m_remainSize -= allocateSize;
++m_numAllocations;
cout << "Malloc success, num allocations: " << m_numAllocations << endl;
cout << "Remain size: " << m_remainSize << "B" << endl;
return found + 1;
}
}
cout << "Malloc failed!" << endl;
cout << "Remain size: " << m_remainSize << endl;
return nullptr;
}
|
若所需内存为0或者所需内存大于剩余总空闲内存则直接返回空指针(myalloc(0)是未定义型为也可以返回一个无法使用但可以被释放的内存块，即只有Header的块)，分配成功后将符合要求的空闲内存块移出m_freeList，并返回指向该块数据区的指针。
myfree实现
释放由myalloc所申请的内存时，通过指针比较，找到该内存块在m_freeList中的前驱节点(m_freeList中的节点以地址从小到大的顺序排列)，查找前驱节点的函数定义如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool GetPrevNode(BlockNode** pPrev, BlockNode* pNode){
assert(pNode != nullptr);
bool success = false;
BlockNode* prev = nullptr;
BlockNode* curr = m_freeList;
while (curr != nullptr){
if (pNode <= curr){
success = true;
break;
}
prev = curr;
curr = curr->m_next;
}
*pPrev = prev;
return success;
}
|
有了前驱节点和需要释放的内存块后，可以将需要释放的内存块插入到m_freeList中，这时可以判断所需释放的内存块的前部和后部的内存块(不是m_freeList中的前驱或后驱节点，而是和需要释放的内存块地址连续邻接的内存块)是否处于空闲状态(可以通过指针的地址进行检查所后驱节点和前驱节点与该节点的内存地址连续则为邻接块)，若是则进行合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void MergeBlock(BlockNode* pPrev, BlockNode* pMerge){
assert(pMerge != nullptr);
size_t mergeNodeSize = pMerge->m_size;
m_remainSize += mergeNodeSize;
if (pMerge->m_next != nullptr){
size_t nextNodeSize = pMerge->m_next->m_size;
if ((pMerge + (mergeNodeSize + sizeof(BlockNode)) / 8) == pMerge->m_next) {
RemoveNode(pMerge, pMerge->m_next);
cout << "Merge block with next block, size after merge :" << nextNodeSize << endl;
mergeNodeSize += sizeof(BlockNode) + nextNodeSize;
pMerge->m_size = mergeNodeSize;
m_remainSize += sizeof(BlockNode);
}
}
if (pPrev != nullptr){
size_t prevNodeSize = pPrev->m_size;
if ((pPrev + (prevNodeSize + sizeof(BlockNode)) / 8) == pMerge) {
cout << "Merge block with prev block, size before merge :" << prevNodeSize << endl;
RemoveNode(pPrev, pMerge);
prevNodeSize += mergeNodeSize + sizeof(BlockNode);
pPrev->m_size = prevNodeSize;
m_remainSize += sizeof(BlockNode);
}
}
}
|
myfree函数的具体实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
| void myfree(void* pPtr){
if (pPtr != nullptr){
BlockNode* freeBlock = (BlockNode*)pPtr - 1;
BlockNode* prev = nullptr;
GetPrevNode(&prev, freeBlock);
InsertNode(prev, freeBlock);
MergeBlock(prev, freeBlock);
--m_numAllocations;
cout << "Free success, num allocations: " << m_numAllocations << endl;
cout << "Remain size: " << m_remainSize << endl;
}
}
|
由于初始申请的一大块内存为8字节对齐，Header的大小为8，每次申请的内存大小也为8的倍数，所以myalloc所返回的指针均为8字节对齐，这种实现的优点是比较简单，而且对任何对齐大小(1,2,4,8字节对齐)都可以实现对齐，缺点是若所需的内存大小不是8的倍数则会浪费一部分的内存…。若想要实现更节省内存一点的分配方式则可以每次分配时计算内存对齐地址，然后再进行分配可以节省一些内存。
这里的myalloc实现只是一个玩具而已…，实际的malloc实现会更复杂一些，需要考虑到更多的问题。
ps:什么是内存碎片？
如果如果每次分配8字节内存，且每相邻的两块内存一个被使用而另一个空闲，此时总的空闲内存远大于8字节(空闲内存为：8*N，N为空闲块的数量)，但是此时却无法再分配一个16字节的内存，因为所有空闲块都不是连续的。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
| #include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include<string.h>
#include <cassert>
#include <iostream>
using namespace std;
struct BlockNode{
BlockNode* m_next;
size_t m_size;
};
enum class SEARCH_MODE{
FIRST_FIT,
BEST_FIT
};
class MemAllocator {
public:
MemAllocator(size_t pSize, SEARCH_MODE pMode) {
m_size = pSize * 8;
m_data = _aligned_malloc(m_size, 8);
m_mode = pMode;
memset(m_data, 0, m_size);
InitFreeList(m_data, m_size);
cout << "申请内存空间大小为：" << m_size << "B" << endl;
cout << "内存空间实际剩余为：" << m_remainSize << "B" << endl;
cout << "内存空间首地址为：0x" << m_data << endl;
}
void InitFreeList(void* pStart, size_t pSize){
assert(pStart != nullptr);
m_numAllocations = 0;
m_remainSize = pSize - sizeof(BlockNode);
m_freeList = static_cast<BlockNode*>(pStart);
m_freeList->m_next = nullptr;
m_freeList->m_size = m_remainSize;
}
bool GetProperBlock(size_t pSize, SEARCH_MODE pMode, BlockNode** pPrevNode, BlockNode** pFoundNode) {
if (pMode == SEARCH_MODE::FIRST_FIT) {
return GetFirstFitBlock(pSize, pPrevNode, pFoundNode);
}
return GetBestFitBlock(pSize, pPrevNode, pFoundNode);
}
bool GetFirstFitBlock(size_t pSize, BlockNode** pPrevNode, BlockNode** pFoundNode) {
BlockNode* prev = nullptr;
BlockNode* curr = m_freeList;
bool success = false;
while (curr != nullptr){
if (curr->m_size >= pSize){
success = true;
break;
}
prev = curr;
curr = curr->m_next;
}
*pPrevNode = prev;
*pFoundNode = curr;
return success;
}
bool GetBestFitBlock(size_t pSize, BlockNode** pPrevNode, BlockNode** pFoundNode){
BlockNode* prev = nullptr;
BlockNode* curr = m_freeList;
bool success = false;
BlockNode* best = nullptr;
BlockNode* bestPrev = nullptr;
size_t bestSize = m_size;
while (curr != nullptr){
size_t currSize = curr->m_size;
if (currSize >= pSize){
success = true;
if (currSize < bestSize){
bestSize = currSize;
best = curr;
bestPrev = prev;
}
}
prev = curr;
curr = curr->m_next;
}
*pPrevNode = bestPrev;
*pFoundNode = best;
return success;
}
void SplitBlock(BlockNode* pOld, size_t pSize){
assert(pOld != nullptr);
size_t oldBlockSize = pOld->m_size;
assert(oldBlockSize > pSize);
BlockNode* newBlock = pOld + (pSize + sizeof(BlockNode)) / 8;
newBlock->m_size = oldBlockSize - pSize - sizeof(BlockNode);
pOld->m_size = pSize;
InsertNode(pOld, newBlock);
cout << "Split block" << endl;
}
void RemoveNode(BlockNode* pPrev, const BlockNode* pDelete){
assert(pDelete != nullptr);
if (pPrev != nullptr){
pPrev->m_next = pDelete->m_next;
}
else{
m_freeList = pDelete->m_next;
}
}
void InsertNode(BlockNode* pPrev, BlockNode* pNew){
assert(pNew != nullptr);
if (pPrev != nullptr){
pNew->m_next = pPrev->m_next;
pPrev->m_next = pNew;
}
else{
pNew->m_next = m_freeList;
m_freeList = pNew;
}
}
void* myalloc(size_t pSize){
size_t dataSize = pSize * 8;
if (dataSize <= m_remainSize){
BlockNode* prev = nullptr;
BlockNode* found = nullptr;
if (GetProperBlock(dataSize, m_mode, &prev, &found)){
assert(found != nullptr);
size_t founBlockSize = found->m_size;
size_t allocateSize = founBlockSize + sizeof(BlockNode);
if (founBlockSize > (dataSize + sizeof(BlockNode))){
SplitBlock(found, dataSize);
allocateSize = dataSize + sizeof(BlockNode);
}
RemoveNode(prev, found);
m_remainSize -= allocateSize;
++m_numAllocations;
cout << "Malloc success, num allocations: " << m_numAllocations << endl;
cout << "Remain size: " << m_remainSize << "B" << endl;
return found + 1;
}
}
cout << "Malloc failed!" << endl;
cout << "Remain size: " << m_remainSize << endl;
return nullptr;
}
bool GetPrevNode(BlockNode** pPrev, BlockNode* pNode){
assert(pNode != nullptr);
bool success = false;
BlockNode* prev = nullptr;
BlockNode* curr = m_freeList;
while (curr != nullptr){
if (pNode <= curr){
success = true;
break;
}
prev = curr;
curr = curr->m_next;
}
*pPrev = prev;
return success;
}
void MergeBlock(BlockNode* pPrev, BlockNode* pMerge){
assert(pMerge != nullptr);
size_t mergeNodeSize = pMerge->m_size;
m_remainSize += mergeNodeSize;
if (pMerge->m_next != nullptr){
size_t nextNodeSize = pMerge->m_next->m_size;
if ((pMerge + (mergeNodeSize + sizeof(BlockNode)) / 8) == pMerge->m_next) {
RemoveNode(pMerge, pMerge->m_next);
cout << "Merge block with next block, size after merge :" << nextNodeSize << endl;
mergeNodeSize += sizeof(BlockNode) + nextNodeSize;
pMerge->m_size = mergeNodeSize;
m_remainSize += sizeof(BlockNode);
}
}
if (pPrev != nullptr){
size_t prevNodeSize = pPrev->m_size;
if ((pPrev + (prevNodeSize + sizeof(BlockNode)) / 8) == pMerge) {
cout << "Merge block with prev block, size before merge :" << prevNodeSize << endl;
RemoveNode(pPrev, pMerge);
prevNodeSize += mergeNodeSize + sizeof(BlockNode);
pPrev->m_size = prevNodeSize;
m_remainSize += sizeof(BlockNode);
}
}
}
void myfree(void* pPtr){
if (pPtr != nullptr){
BlockNode* freeBlock = (BlockNode*)pPtr - 1;
BlockNode* prev = nullptr;
GetPrevNode(&prev, freeBlock);
InsertNode(prev, freeBlock);
MergeBlock(prev, freeBlock);
--m_numAllocations;
cout << "Free success, num allocations: " << m_numAllocations << endl;
cout << "Remain size: " << m_remainSize << endl;
}
}
~MemAllocator() {
if (m_data != nullptr) {
_aligned_free(m_data);
}
}
private:
BlockNode* m_freeList;
void* m_data;
size_t m_size;
size_t m_numAllocations;
size_t m_remainSize;
SEARCH_MODE m_mode;
};
struct block {
string name;
size_t size;
BlockNode* ptr;
}block[100];
int main() {
char choice = ' ';
cout << "请从下列选项中进行选择" << endl;
cout << "1.最先适应算法" << endl;
cout << "2.最优适应算法" << endl;
cout << "3.退出" << endl;
cout << ">>";
cin >> choice;
SEARCH_MODE mode;
switch (choice) {
case '1':mode = SEARCH_MODE::FIRST_FIT; break;
case '2':mode = SEARCH_MODE::BEST_FIT; break;
case '3':
default:return 0;
}
MemAllocator ma(1024 / 8, mode);
int num = 0;
while (true) {
do {
cout << "请从下列选项中进行选择:" << endl;
cout << "1.分配内存" << endl;
cout << "2.回收内存" << endl;
cout << "3.结束操作" << endl;
cout << ">>";
cin >> choice;
} while (choice != '1' && choice != '2' && choice != '3');
switch (choice) {
case '1': {
cout << "请输入要分配的内存名称：";
string name;
cin >> name;
block[num].name = name;
cout << "请输入要分配的内存大小：";
int size;
cin >> size;
BlockNode* ptr = (BlockNode*)ma.myalloc(size / 8);
cout << "分配的地址空间为：0x" << ptr << "--" << "0x" << ptr + size / 8 << endl;
block[num].ptr = ptr;
block[num].size = size;
num++;
break;
}
case '2': {
string name;
bool success = false;
cout << "请输入要释放的内存名称：";
cin >> name;
for (int i = 0; i < num; i++) {
if (block[i].name == name) {
success = true;
ma.myfree(block[i].ptr);
}
}
if (!success) {
cout << "名称不存在！" << endl;
}
break;
}
case '3':return 0; break;
}
}
}
|
更多参考：浅谈C++内存管理