实验七、动态分区分配方式的模拟
一、实验目的
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
二、实验环境
- 硬件环境：计算机一台，局域网环境；
- 软件环境：Linux Ubuntu 操作系统，gcc 编译器；
三、实验内容和步骤
-
用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程
alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 -
假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
- 作业1申请130KB。
- 作业2申请60KB。
- 作业3申请100KB。
- 作业2释放60KB。
- 作业4申请200KB。
- 作业3释放100KB。
- 作业1释放130KB。
- 作业5申请140KB。
- 作业6申请60KB。
- 作业7申请50KB。
- 作业6释放60KB。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
-
实验步骤：
-
设计过程：
- 最佳适应算法：
首先，定义一个p指针，让p指针遍历空闲分区链表，当找到第一个满足进程请求空间大小的空闲区时，记录此位置，并且保存请求大小与空闲分区实际大小的差值记为a，然后让p指针继续遍历空闲分区链表，每当满足请求内存大小小于空闲区大小时，就记录两者的差值并且记录为b，比较a与b的大小关系，当a>b时，将b的值赋予a，并且修改记录位置为此空闲区的位置。若，a<=b,不做操作。继续遍历链表，重复上面的操作，直到p->next指向null为止。 - 首次适应算法：
首次适应算法比较简单，只要找到满足条件的空闲区，就将此区的空间分配给进程。首先，用P指针遍历链表，找到第一个空间大于或者等于请求大小的位置，将此空间分配给进程，当此空闲区大小大于请求空间大小时，将空闲区分为两部分，一部分分配给进程，另一部分为空闲区，它的大小为之前空闲区大小减去分配给进程的空间大小。 - 内存回收算法：
内存回收时，回收分区与空闲分区有四种关系。第一种情况为回收分区r上临一个空闲分区，此时应该合并为一个连续的空闲区，其始址为r上相邻的分区的首地址，而大小为两者大小之和。第二种情况为回收分区r与下相邻空闲分区，合并后仍然为空闲区，该空闲区的始址为回收分区r的地址。大小为两者之和，第三种情况为回收部分r与上下空闲区相邻，此时将这三个区域合并，始址为r上相邻区域的地址，大小为三个分区大小之和。当回收部分r上下区域都为非空闲区域，此时建立一个新的空闲分区，并且加入到空闲区队列中去。
- 最佳适应算法：
-
实验代码：
▶Code1
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
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349#include<stdio.h>
#include<stdlib.h>
typedef struct lei_item // 表示空闲分区表中的表箱
{
int id; // 假如 id 为-1，表示此分区时一个空闲分区。
int base; // 指向分区的首地址
int size; // 表示分区大小
int status; // 表示此分区是否已经分配，0表示空闲，1表示已经分配
} Item;
typedef Item datatype;
typedef struct lei_list {
datatype *node; // 表示一个datatype类型的链表的结点
struct lei_list *front;
struct lei_list *next;
} List;
#define Max 640
int memory = Max; // 定义可用内存空间为640
// 初始化一个链表;
List init() {
List list;
list.node = (datatype *) malloc(sizeof(datatype));
list.node->base = 0;
list.node->id = -1; // -1表示是空闲分区
list.node->size = memory;
list.node->status = 0;
list.front = list.next = NULL;
return list;
}
// 初始化打算申请的内存分区节点
datatype *input() {
datatype *item = (datatype *) malloc(sizeof(datatype));
printf("请输入作业号：");
scanf("%d", &item->id);
printf("请输入所需要的内存的大小：");
scanf("%d", &item->size);
item->status = 0;
return item;
}
void Momery_state(List *list) {
List *temp = list;
printf("-----------------------------------\n");
printf("内存分配状况\n");
printf("-----------------------------------\n");
while (temp) {
if (temp->node->status == 0 && temp->node->id == -1) {
printf("分区号：FREE\n");
printf("起始地址：%d\n", temp->node->base);
printf("内存大小：%d\n", temp->node->size);
printf("分区状态：空闲\n");
} else {
printf("分区号：%d\t起始地址：%d\n", temp->node->id, temp->node->base);
printf("内存大小：%d\n", temp->node->size);
printf("分区状态：已分配\n");
}
printf("-----------------------------------\n");
temp = temp->next;
}
}
int First_fit(List *list) {
datatype *item = input();
// 定义一个临时变量list* ，指向list
List *temp = list;
while (temp) {
if (temp->node->status == 0 &&
temp->node->size > item->size) { // 如果此前的分区未分配，并且分区大小大于请求分配的大小，那么此时就可以进行分配
List *front = temp->front; // 存储当前未分配分区的上一个分区地址
List *next = temp->next; // 存储当前未分配分区的下一个分区地址
int base = temp->node->base; // 记录未分配当前分区的首地址
datatype *new_node = (datatype *) malloc(sizeof(datatype)); // 多余出来的部分要新建立一个分区
new_node->id = -1; // 然后需要对这个新的分区进行一些信息的设置
new_node->size = temp->node->size - item->size; // 新分区的大小等于还未分配的时的分区大小 - 请求分配的结点的大小
temp->node = item; // 对请求分配的分区结点进行分配
temp->node->status = 1;
new_node->status = 0;
new_node->base = base + temp->node->size; // 新建立分区的首地址是 请求分配的分区的首地址 + 请求分配的分区的大小
List *temp_next = (List *) malloc(sizeof(List)); // 临时节点 （申请一个新的链表节点 表示下一个分区） 并且进行初始化
temp_next->node = new_node; // 保存下一个的分区的信息
temp_next->front = temp_next->next = NULL;
// 如果 front和next节点都是空，表明它是第一次分配分区
if (front == NULL && next == NULL) {
temp->node->base = 0; // 初始化首地址
temp->next = temp_next;
temp_next->front = temp;
}
// 在第一个分区中插入新的分区
if (front == NULL && next != NULL) {
temp->node->base = 0;
temp->node->status = 1;
temp_next->front = temp;
temp_next->next = temp->next;
temp->next = temp_next;
}
// 表明不是第一次分配节点，此时需要在中间插入下一个节点
if (front != NULL) {
temp->node->base = temp->front->node->base + temp->front->node->size; // 初始化首地址
temp_next->next = temp->next; // 保证新插入的节点会记录原先节点的下一个节点的首地址
temp_next->front = temp; // 首尾都需要保证
temp->next = temp_next; // 最后让所申请的分区节点的下一个节点指向我们刚刚建立的临时节点
}
return 1;
} else if (temp->node->status == 0 && temp->node->size == item->size) {
item->base =
temp->front->node->base + temp->front->node->size; // 新插入分区的首地址 等于上一个分区的 首地址+分区的大小
item->status = 1; // 表示已经分配
temp->node = item;
return 1;
} else {
temp = temp->next;
continue;
}
temp = temp->next;
}
return 0;
}
int Momory_recycle(List *list) {
List *temp = list; // 申请一个链表节点，指向list 的头节点
int number; // 用于存放要释放的节点的分区号
printf("请输入需要回收的ID号：");
scanf("%d", &number);
while (temp) {
//首先找到节点 id = number 的节点，然后分四种情况讨论
if (temp->node->id == number)
{
// 一、要回收的是第一个结点
if (temp->front == NULL) {
temp->node->status = 0;
temp->node->id = -1;
if (temp->next == NULL) {
temp->node->size = temp->node->size + temp->next->node->size;
temp->next = temp->next;
return 1;
}
if (temp->next->node->id == -1 && temp->next->node->status == 0) {
List *next = temp->next;
// 此时来判断 temp->next 是否是系统的最后一个结点
// 此时只将当前节点 和下一个结点合并就可以了
// 即首地址不变，分区状态和分区id进行变化
temp->node->size = temp->node->size + next->node->size;
temp->node->status = 0;
temp->node->id = -1;
temp->next = next->next;
if (next->next == NULL) {
free(next);
return 1;
}
// 如果不是最后一个结点的话就会多一个步骤
// 让 next->next->front 指向上一个结点
else {
next->next->front = temp;
free(next);
return 1;
}
}
return 1;
}
// 二、前后都没有空闲的分区
// 最简单，直接改变分区的 id 和分区的状态就可以了。
// 如果回收第一个分区的话必须要先进行处理，如果不先进行处理，判断 temp->front->node->id != -1 会报一个段错误。因为temp->front 此时指向的是null
if (temp->front->node->id != -1 && temp->front->node->status != 0 && temp->next->node->id != -1 &&
temp->next->node->status != 0) {
temp->node->status = 0;
temp->node->id = -1;
return 1;
}
// 三、要回收的节点，前面和后面都是空闲的
// 将三个空闲区合并到一起，起始地址为前面的分区的起始地址，大小为三个空闲区大小之和
if (temp->front->node->id == -1 && temp->front->node->status == 0 && temp->next->node->id == -1 &&
temp->next->node->status == 0) {
List *front = temp->front;
List *next = temp->next;
front->node->size = front->node->size + temp->node->size + next->node->size;
front->next = next->next;
if (next->next == NULL) {
free(temp);
return 1;
}
// 如果不是最后一个结点的话就会多一个步骤
// 让 next->next->front 指向上一个结点
else {
next->next->front = front;
free(temp);
return 1;
}
return 1;
}
// 四、要回收的节点，前面的节点是空闲的
// 合并后的分区起始地址为前一个结点，分区大小为前一个节点与当前节点之和
if (temp->front->node->id == -1 && temp->front->node->status == 0) {
List *front = temp->front;
front->next = temp->next;
temp->next->front = front;
front->node->size += temp->node->size;
free(temp);
return 1;
}
// 五、要回收的节点，后面的额节点是空闲的
// 合并后的分区首地址为当前节点，分区大小为当前节点与当前节点的下一个结点大小之和
// 这个需要多一个步骤，改变分区的 id 和分区的状态
// 还要注意一点：当要回收的空间是和系统最后的空闲区相邻时，temp->next->next 指向的是null
if (temp->next->node->id == -1 && temp->next->node->status == 0) {
List *next = temp->next;
// 此时来判断 temp->next 是否是系统的最后一个结点
// 此时只将当前节点和下一个结点合并就可以了
// 即首地址不变，分区状态和分区id进行变化
temp->node->size = temp->node->size + next->node->size;
temp->node->status = 0;
temp->node->id = -1;
temp->next = next->next;
if (next->next == NULL) {
free(next);
return 1;
} else {
// 如果不是最后一个结点的话就会多一个步骤
// 让 next->next->front 指向上一个结点
next->next->front = temp;
free(next);
return 1;
}
}
}
temp = temp->next;
}
return 0;
}
int Best_fit(List *list) {
// 记录最小分区的结点的大小
int min = 0;
// 记录最小节点的结点的起始地址
int base_min = 0;
List *temp = list;
// 要对 item 的起始地址和分配状态进行初始化
datatype *item = input();
while (temp) {
// 如果分区未分配,就要进行比较操作，并且记录差值和分区的 id 号
if (temp->node->status == 0 && temp->node->id == -1 && temp->node->size > item->size) {
// 加入min为0表示还未找到一个可以分配的分区
if (min == 0) {
min = temp->node->size;
base_min = temp->node->base;
} else {
// 找到一个之后，需要找出最小的分区也就是它的 size 最小
if (temp->node->size < min) {
min = temp->node->size;
base_min = temp->node->base;
}
}
}
if (temp->node->status == 0 && temp->node->id == -1 && temp->node->size == item->size) {
int base = temp->node->base;
temp->node = item;
temp->node->status = 1;
temp->node->base = base;
return 1;
}
temp = temp->next;
}
// 因为可能没有任何一个空间可以满足要求需要做一个判断处理
temp = list;
while (temp) {
if (temp->node->base == base_min) {
//会有多余的空间多出来, 所以需要在建立一个结点插入到链表中
datatype *temp_node = (datatype *) malloc(sizeof(datatype));
temp_node->id = -1;
temp_node->status = 0;
temp_node->base = base_min + item->size;
temp_node->size = temp->node->size - item->size;
// 对item进行完整的初始化
temp->node = item;
temp->node->base = base_min;
temp->node->status = 1;
// 新申请一个链表的结点并且初始化
List *temp_list_node = (List *) malloc(sizeof(List));
temp_list_node->node = temp_node;
temp_list_node->front = temp;
temp_list_node->next = temp->next;
if (temp->next != NULL) {
temp->next->front = temp_list_node;
}
temp->next = temp_list_node;
return 1;
}
temp = temp->next;
}
}
int main() {
printf("分区模拟\n");
List list = init();
int select;
int insert_state, recycle_state;
int insert_state_best;
do {
printf("请输入要进行的操作\n");
printf("1-首次适应算法， 2-最佳适应算法， 3-内存回收， 4-显示内存状况， 5-退出\n");
scanf("%d", &select);
switch (select) {
// 1. 首次适应算法
case 1:
insert_state = First_fit(&list);
if (insert_state == 0) {
printf("分配失败\n");
} else {
printf("分配成功！\n");
}
break;
// 2. 最佳适应算法
case 2:
insert_state_best = Best_fit(&list);
if (insert_state_best == 1) {
printf("分配成功\n");
} else {
printf("分配失败\n");
}
break;
// 3.内存回收
case 3:
recycle_state = Momory_recycle(&list);
if (recycle_state == 1) {
printf("回收成功！\n");
} else {
printf("回收失败\n");
}
break;
// 4.显示内存状况
case 4:
Momery_state(&list);
break;
}
} while (select != 5);
system("pause");
}
-
四、实验总结
存储管理是指对外部存储资源和内存进行管理，可以完成存储分配，存储共享，存储保护，存储扩充，地址映射等重要功能，对操作系统的性能有很重要的影响。在计算机科学中，存储管理是操作系统的一个重要组成部分，它负责管理计算机内存和外部存储器的使用。
实验七、动态分区分配方式的模拟
https://flowerdown.org/posts/20230610-201211.html