实验名称：动态分区分配方式模拟_本实验是模拟分段存储管理,系统需要建立两张分区表,分别是已分配和未分配分区表,

实验名称：动态分区分配方式模拟

实验目的

进一步加深对动态分区分配管理方式的理解；掌握动态分区分配方式使用的数据结构、分配算法和回收算法

实验内容

编写C语言程序，模拟实现首次/最佳/最坏适应算法的内存块分配和回收，要求每次分配和回收后显示出空闲分区和已分配分区的情况。假设初始状态下，可用的内存空间为640K。

数据结构设计

1. 空闲分区表：Unallocated Table

2. 已分配分区表：Allocated Table

分配算法设计

1. 首次适应算法
2. 最佳适应算法
3. 最差适应算法

根据选择的分配算法决定空闲分区表的排序方式

回收算法设计

1. 上下都无空分区
2. 有上空分区无下空分区
3. 无上空分区有下空分区
4. 上下分区都为空分区

代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAX 640

struct node  //定义分区
{
  int address, size;
  struct node *next;
};
typedef struct node RECT;

/*-----函数定义-------*/
void firstfit(RECT *head,int application); //针对首次适应分配算法分配分区
void bestfit(RECT *head,int application);  //针对最佳适应分配算法分配分区
void worstfit(RECT *head,int application);  //针对最坏适应分配算法分配分区
int backcheck(RECT *head,RECT *back1); //合法性检查
void recycle(RECT *head,RECT *heada,RECT *back1); //回收分区
void print(RECT *head);   //输出已分配分区表或空闲分区
/*-----变量定义-------*/
RECT *head,*heada,*back,*assign1,*p;
int application1,maxblocknum;
char way;  //用于定义分配方式：首先适应(f)、最佳适应(b)、最差适应(w)
int main()
{
  char choose;
  int check;
  RECT *allocated;  //
  head=malloc(sizeof(RECT)); //建立空闲分区表的初始状态
  p=malloc(sizeof(RECT));
  head->size=MAX;
  head->address=0;
  head->next=p;
  maxblocknum=1; //初始只有一块空闲区
  p->size=MAX;
  p->address=0;
  p->next=NULL;
  print(head);  //输出空闲分区表的初始状态
  printf("Enter the way (first, best or worst (f/b/w))\n");
  scanf("%c",&way);
  heada=malloc(sizeof(RECT)); //建立已分配分区表的初始状态
  heada->size=0;
  heada->address=0;
  heada->next=NULL;
  //print(heada);  //输出空闲分区表的初始状态
  //way='f';
  do
  {
    printf("Enter the allocate or reclaim (a/r),or press other key to exit.\n");
    scanf(" %c",&choose);     //选择分配或回收
    if(tolower(choose)=='a')                 //a为分配
    {
      printf("Input application:\n");
      scanf("%d",&application1);              //输入申请空间大小
        if(tolower(way)=='f')
          firstfit(head,application1);    //首先适应算法分配
        else if(tolower(way)=='b')
          bestfit(head,application1);     //调用最佳适应分配算法函数分配内存
        else
          worstfit(head,application1);    //最坏适应算法分配
      if (assign1->address==-1)               //分配不成功
        printf("Too large application! Allocation fails! \n\n");
      else{//分配成功
          printf("Allocation Success! ADDRESS=%5d\n",assign1->address);
        printf("\n*********Unallocated Table**********\n");
        print(head);  //输出
        printf("\n*********Allocated Table************\n");
          print(heada);
      }
    }
    else if (tolower(choose)=='r')          //回收内存
    {
      back=malloc(sizeof(RECT));
      printf("Input address and Size:\n");
      scanf("%d%d",&back->address,&back->size);//输入回收地址和大小
      check=backcheck(head,back);
      if (check==1)
      {
        recycle(head,heada,back);
        printf("\n*********Unallocated Table**********\n");
        print(head);  //输出
        printf("\n*********Allocated Table************\n");
        print(heada);
       }
    }
  }while(tolower(choose)=='a'||tolower(choose)=='r');
  exit(0);
} //main() end.

/*-------内存回收函数,back1为回收节点到地址-------*/
void recycle(RECT *head,RECT *heada,RECT *back1)
{
  RECT *before, *after, *back2;
  int insert = 0, del;
  back2 = malloc(sizeof(RECT));
  back2->address = back1->address;
  back2->size = back1->size;
  back2->next = back1->next;
  before = head;
  after = head->next;

  if (head->next == NULL) // 没有空闲区，直接回收
  {
    head->size = back1->size;
    head->next = back1;
    maxblocknum++;
    back1->next = NULL;
  }
  else
  {
    while (!insert&&after!=NULL)                                 // 遍历空闲区
    {
      if (back1->address == after->size + after->address) /*要回收的内存在当前空闲区之后，与上一块合并*/
      {//第一种情况，回收区与相邻低地址合并
        after->size+=back1->size;
        insert=1;
        // before->next = after->next;
        // back->size = after->size + back1->size;
        // free(after);
        // after = NULL;
      }else if(back1->address+back1->size==after->address)
      { //第二种情况，回收区与相邻高地址合并
        after->size+=back1->size;
        after->address=back1->address;
        insert=1;
      }else if(before->address<back1->address&&after->address>back1->address)
      { //第三种情况，回收区与相邻的高地址、低地址合并，被夹在中间
        before->size+=back1->size+after->size;
        insert=1;
      }
        after = after->next;
        before = before->next;
    }

    //第四种情况，回收区独自一块，需要在空闲表中新增一项
    before = head; /*将回收节点插入到合适到位置*/
    after = head->next;
    do
    {
      if (after == NULL)
      {
        before->next = back1;
        back1->next = after;
        insert = 1;
      }
      else
      {
        before = before->next;
        after = after->next;
      }
    } while (!insert);

    if (head->size < back1->size) /*修改最大块值和最大块数*/
    {
      head->size = back1->size;
      maxblocknum++;
    }
    else
    {
      if (head->size == back1->size)
        maxblocknum++;
    }
  }

  // 修改已分配分区表，删除相应节点
  before = heada;
  after = heada->next;
  del = 0;
  while (!del &&after != NULL) // 1，循环在已删除或者遍历结束时退出，将回收区从已分配分区表中删除
  {
    if ((after->address == back2->address) && (after->size == back2->size))
    {
      before->next = after->next;
      free(after);
      del = 1;
    }
    else
    {
      before = before->next;
      after = after->next;
    }
  }
  heada->size--;
}

/*------------------首次适应分配算法------------*/
void firstfit(RECT *head,int application)
{
  RECT *after, *before, *assign;
  assign = malloc(sizeof(RECT)); // 申请分配空间
  assign->size = application;
  assign->next = NULL;
  if (application > head->size || application < 0)
    assign->address = -1; // 申请无效
  else
  {
    before = head;
    after = head->next;
    while (after->size < application) // 遍历链表，查找合适到节点
    {
      before = before->next;
      after = after->next;
    }
    if (after->size == application) // 若节点大小等于申请大小则完全分配
    {
      if (after->size == head->size)
        maxblocknum--;
      before->next = after->next;       // 指向后面的空闲区
      assign->address = after->address; // 将这个同样大小的地址直接赋给分配的对象
      free(after);
    }
    else
    {
      if (after->size == head->size) // 这个可分配空间等于剩余总的空闲空间
        maxblocknum--;
      after->size = after->size - application;        // 大于申请空间则截取相应大小分配
      assign->address = after->address + after->size; // 分配靠后的地址
    }

    if (maxblocknum == 0) // 修改最大数和头节点
    {
      before = head;
      head->size = 0;
      maxblocknum = 1;
      while (before != NULL) // 遍历空闲区
      {
        if (before->size > head->size)
        {
          head->size = before->size;
          maxblocknum = 1;
        }
        else if (before->size == head->size)
          maxblocknum++;
        before = before->next;
      }
    }
  }
  assign1 = assign;

  // 修改已分配分区表，添加节点
  after = heada;
  while (after->next != NULL)
    after = after->next;
  after->next = assign;
  heada->size++;
}

/*-----------------最佳适应分配算法--------------*/
void bestfit(RECT *head,int application)
{
  RECT *after, *before, *assign;
  assign = malloc(sizeof(RECT)); // 申请分配空间
  assign->size = application;
  assign->next = NULL;
  if (application > head->size || application < 0)
    assign->address = -1; // 申请无效
  else
  {
    before = head;
    RECT* ptr = head->next;
    int tmp=0;
    //找到第一块最合适的空闲分区，即空间大于application的最小分区
    while (ptr!=NULL) // 遍历链表，查找合适到节点
    {
      if(ptr->size>=application){
        if(!tmp||ptr->size<tmp){
          after=ptr;
          tmp=ptr->size;
        }
      }
      ptr=ptr->next;
    }
    if (after->size == application) // 若节点大小等于申请大小则完全分配
    {
      if (after->size == head->size)
        maxblocknum--;
      before->next = after->next;       // 指向后面的空闲区
      assign->address = after->address; // 将这个同样大小的地址直接赋给分配的对象
      free(after);
    }
    else
    {
      if (after->size == head->size) // 这个可分配空间等于剩余总的空闲空间
        maxblocknum--;
      after->size = after->size - application;        // 大于申请空间则截取相应大小分配
      assign->address = after->address + after->size; // 分配靠后的地址
    }

    if (maxblocknum == 0) // 修改最大数和头节点
    {
      before = head;
      head->size = 0;
      maxblocknum = 1;
      while (before != NULL) // 遍历空闲区
      {
        if (before->size > head->size)
        {
          head->size = before->size;
          maxblocknum = 1;
        }
        else if (before->size == head->size)
          maxblocknum++;
        before = before->next;
      }
    }
  }
  assign1 = assign;

  // 修改已分配分区表，添加节点
  after = heada;
  while (after->next != NULL)
    after = after->next;
  after->next = assign;
  heada->size++;
}


/*-----------------最坏适应分配算法--------------*/
void worstfit(RECT *head,int application)
{
RECT *after, *before, *assign;
  assign = malloc(sizeof(RECT)); // 申请分配空间
  assign->size = application;
  assign->next = NULL;
  if (application > head->size || application < 0)
    assign->address = -1; // 申请无效
  else
  {
    before = head;
    RECT* ptr = head->next;
    int tmp=0;
    //找到最大的空闲分区进行分配
    while (ptr!=NULL) // 遍历链表，查找合适到节点
    {
      if(ptr->size>=application){
        if(ptr->size>tmp){
          after=ptr;
          tmp=ptr->size;
        }
      }
      ptr=ptr->next;
    }
    if (after->size == application) // 若节点大小等于申请大小则完全分配
    {
      if (after->size == head->size)
        maxblocknum--;
      before->next = after->next;       // 指向后面的空闲区
      assign->address = after->address; // 将这个同样大小的地址直接赋给分配的对象
      free(after);
    }
    else
    {
      if (after->size == head->size) // 这个可分配空间等于剩余总的空闲空间
        maxblocknum--;
      after->size = after->size - application;        // 大于申请空间则截取相应大小分配
      assign->address = after->address + after->size; // 分配靠后的地址
    }

    if (maxblocknum == 0) // 修改最大数和头节点
    {
      before = head;
      head->size = 0;
      maxblocknum = 1;
      while (before != NULL) // 遍历空闲区
      {
        if (before->size > head->size)
        {
          head->size = before->size;
          maxblocknum = 1;
        }
        else if (before->size == head->size)
          maxblocknum++;
        before = before->next;
      }
    }
  }
  assign1 = assign;

  // 修改已分配分区表，添加节点
  after = heada;
  while (after->next != NULL)
    after = after->next;
  after->next = assign;
  heada->size++;
}

/*-----------------打印输出链表--------------*/
void print(RECT *output)
{
  RECT *before;
  int index;
  before=output->next;
  index=0;
  if(output->next==NULL)
    printf("NO part for print!\n");
  else
  {
    printf("index****address****end*****size**** \n");
    while(before!=NULL)
    {
      printf("------------------------------------\n");
      printf(" %-9d%- 9d%- 9d%- 9d\n",index,before->address,before->address+before->size-1,before->size);
      printf("------------------------------------\n");
      index++;
      before=before->next;
    }
  }
}

/*检查回收块到合法性，back1为要回收到节点地址*/
int backcheck(RECT *head,RECT *back1)
{
  RECT *before;
  int check=1;
  if(back1->address<0 || back1->size<0) check=0;  //地址和大小不能为负数
  before=head->next;
  while((before!=NULL)&&check) //地址不能和空闲区表中节点出现重叠
  if(((back1->address<before->address)&&(back1->address+back1->size>before->address))||((back1->address>=before->address)&&(back1->address<before->address+before->size)))
    check=0;
  else
    before=before->next;
  if(check==0) printf("Error input!\n");
  return check;
}
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
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
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425