【操作系统】内存管理设计性实验报告_内存管理实验报告

操作系统#内存管理设计性实验报告

正文

一、 实验目的
1.通过本次试验体会操作系统中内存的分配模式；
2.掌握内存分配的方法（首次适应（FF），最佳适应（BF）,最差适应（WF））；
3.学会进程的建立，当一个进程被终止时内存是如何处理被释放块，并当内存不满足进程申请时是如何使用内存紧凑；
4.掌握内存回收过程及实现方法；
5.学会进行内存的申请释放和管理；

二、 实验设备

实验机房虚拟机里的中linux系统

三、 实验要求

1、运行如下的内存申请与释放序列：先设置内存大小为2048k，进程1申请500k，进程2申请300k，进程1完成，进程3申请200k，进程4申请100k，进程5申请300k；

2、分别选择不同的内存分配算法，输出上述序列的内存分配结果；

3、实现循环首次适应算法，并输出上述序列采用该分配算法后的结果。

四、 实验步骤

#include<stdio.h>
#include<stdlib.h>
#include<sys/types.h>

#define PROCESS_NAME_LEN     32        /*进程名称的最大长度*/
#define MIN_SLICE            10        /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE     1024      /*默认内存的大小*/
#define DEFAULT_MEM_START    0         /*默认内存的起始位置*/

/* 内存分配算法 */
#define MA_FF      1
#define MA_BF      2
#define MA_WF      3

int mem_size = DEFAULT_MEM_SIZE;         /*内存大小*/
int ma_algorithm = MA_FF;              /*当前分配算法*/
int flag = 0;            		       /*设置内存大小标志*/
static int pid = 0;                    /*初始pid*/
int algorithm;

/*描述每一个空闲块的数据结构*/
struct free_block_type {
    int size;
    int start_addr;
    struct free_block_type* next;
};


/*指向内存中空闲块链表的首指针*/
struct free_block_type* free_block;

/*每个进程分配到的内存块的描述*/
struct allocated_block {
    int pid;
    int size;
    int start_addr;
    char process_name[PROCESS_NAME_LEN];
    struct allocated_block* next;
};
/*进程分配内存块链表的首指针*/
struct allocated_block* allocated_block_head = NULL;

struct allocated_block* find_process(int id)
{
    struct allocated_block* p;
    p = allocated_block_head;
    while (p != NULL)
    {
        if (p->pid == id)
            p = p->next;
            return p;
    }
    return NULL;
}

void swap(int* p, int* q)
{
    int temp;

    temp = *p;
    *p = *q;
    *q = temp;

    return;
}

void do_exit()
{
    exit(0);
}

/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size) {
    struct free_block_type* fb;

    fb = (struct free_block_type*)malloc(sizeof(struct free_block_type));
    if (fb == NULL) {
        printf("No mem\n");
        return NULL;
    }
    fb->size = mem_size;
    fb->start_addr = DEFAULT_MEM_START;
    fb->next = NULL;
    return fb;
}

/*显示菜单*/
display_menu() {
    printf("\n");
    printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
    printf("2 - Select memory allocation algorithm\n");
    printf("3 - New process \n");
    printf("4 - Terminate a process \n");
    printf("5 - Display memory usage \n");
    printf("0 - Exit\n");
}

/*设置内存的大小*/
set_mem_size() {
    int size;
    if (flag != 0) {  //防止重复设置
        printf("Cannot set memory size again\n");
        return 0;
    }
    printf("Total memory size =");
    scanf("%d", &size);
    if (size > 0) {
        mem_size = size;
        free_block->size = mem_size;
    }
    flag = 1;  return 1;
}

/*按FF算法重新整理内存空闲块链表*/
rearrange_FF() {
    struct free_block_type* tmp, * work;
    printf("Rearrange free blocks for FF \n");
    tmp = free_block;
    while (tmp != NULL)
    {
        work = tmp->next;
        while (work != NULL) {
            if (work->start_addr > tmp->start_addr)
            { /*地址递增*/
                swap(&work->start_addr, &tmp->start_addr);
                swap(&work->size, &tmp->size);
            }

            work = work->next;
        }
        tmp = tmp->next;
    }
}

/*按BF最佳适应算法重新整理内存空闲块链表*/

rearrange_BF() {
    struct free_block_type* tmp, * work;
    printf("Rearrange free blocks for BF \n");
    tmp = free_block;
    while (tmp != NULL)
    {
        work = tmp->next;
        while (work != NULL) {
            if (work->size < tmp->size) { /*地址递增*/
                swap(&work->start_addr, &tmp->start_addr);
                swap(&work->size, &tmp->size);
            }

            work = work->next;
        }
        tmp = tmp->next;
    }
}


/*按WF算法重新整理内存空闲块链表*/

rearrange_WF() {
    struct free_block_type* tmp, * work;
    printf("Rearrange free blocks for WF \n");
    tmp = free_block;
    while (tmp != NULL)
    {
        work = tmp->next;
        while (work != NULL) {
            if (work->size < tmp->size) { /*地址递增*/
                swap(&work->start_addr, &tmp->start_addr);
                swap(&work->size, &tmp->size);
            }
            else
                work = work->next;
        }
        tmp = tmp->next;
    }
}

/*按指定的算法整理内存空闲块链表*/
rearrange(int algorithm) {
    switch (algorithm) {
    case MA_FF:  rearrange_FF(); break;
    case MA_BF:  rearrange_BF(); break;
    case MA_WF:  rearrange_WF(); break;
    }
}

/* 设置当前的分配算法 */
set_algorithm() {

    printf("\t1 - First Fit\n");
    printf("\t2 - Best Fit \n");
    printf("\t3 - Worst Fit \n");
    scanf("%d", &algorithm);
    if (algorithm >= 1 && algorithm <= 3) ma_algorithm = algorithm;
    //按指定算法重新排列空闲区链表
    rearrange(ma_algorithm);
}

/*分配内存模块*/
int allocate_mem(struct allocated_block* ab) {
    struct free_block_type* fbt, * pre, * temp, * work;
    int request_size = ab->size;
    fbt = free_block;
    while (fbt != NULL)
    {
        if (fbt->size >= request_size)
        {
            if (fbt->size - request_size >= MIN_SLICE) /*分配后空闲空间足够大，则分割*/
            {
                mem_size -= request_size;
                fbt->size -= request_size;
                ab->start_addr = fbt->start_addr;
                fbt->start_addr += request_size;
            }
            else  if (((fbt->size - request_size) < MIN_SLICE) && ((fbt->size - request_size) > 0))
                /*分割后空闲区成为小碎片，一起分配*/
            {
                mem_size -= fbt->size;
                pre = fbt->next;
                ab->start_addr = fbt->start_addr;
                fbt->start_addr += fbt->size;
                free(fbt);
            }
            else
            {
                temp = free_block;

                while (temp != NULL)
                {
                    work = temp->next;

                    if (work != NULL)/*如果当前空闲区与后面的空闲区相连，则合并*/
                    {
                        if (temp->start_addr + temp->size == work->start_addr)
                        {
                            temp->size += work->size;
                            temp->next = work->next;
                            free(work);
                            continue;
                        }
                    }

                    temp = temp->next;
                }

                fbt = free_block;
                break;
            }
            rearrange(algorithm); /*重新按当前的算法排列空闲区*/
            return 1;
        }

        pre = fbt;
        fbt = fbt->next;
    }
    return -1;
}

/*创建新的进程，主要是获取内存的申请数量*/
new_process() {
    struct allocated_block* ab;
    int size;
    int ret;
    ab = (struct allocated_block*)malloc(sizeof(struct allocated_block));
    if (!ab) exit(-5);
    ab->next = NULL;
    pid++;
    sprintf(ab->process_name, "PROCESS-%02d", pid);
    ab->pid = pid;

    printf("Memory for %s:", ab->process_name);
    scanf("%d", &size);
    if (size > 0) ab->size = size;
    ret = allocate_mem(ab);  /* 从空闲区分配内存，ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值，则赋值*/
    if ((ret == 1) && (allocated_block_head == NULL)) {
        allocated_block_head = ab;
        return 1;
    }
    /*分配成功，将该已分配块的描述插入已分配链表*/
    else if (ret == 1) {
        ab->next = allocated_block_head;
        allocated_block_head = ab;
        return 2;
    }
    else if (ret == -1) { /*分配不成功*/
        printf("Allocation fail\n");
        free(ab);
        return -1;
    }
    return 3;
}

/*将ab所表示的已分配区归还，并进行可能的合并*/
int free_mem(struct allocated_block* ab)
{
    int algorithm = ma_algorithm;
    struct free_block_type* fbt, * work;

    fbt = (struct free_block_type*)malloc(sizeof(struct free_block_type));
    if (!fbt) return -1;
    fbt->size = ab->size;
    fbt->start_addr = ab->start_addr;
    /*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
    fbt->next = free_block;
    free_block = fbt;
    rearrange(MA_FF);
    fbt = free_block;
    while (fbt != NULL) {
        work = fbt->next;
        if (work != NULL)
        {
            /*如果当前空闲区与后面的空闲区相连，则合并*/
            if (fbt->start_addr + fbt->size == work->start_addr)
            {
                fbt->size += work->size;
                fbt->next = work->next;
                free(work);
                continue;
            }
        }
        fbt = fbt->next;
    }
    rearrange(algorithm); /*重新按当前的算法排列空闲区*/
    return 1;
}


/*释放ab数据结构节点*/
int dispose(struct allocated_block* free_ab) {
    struct allocated_block* pre, * ab;

    if (free_ab == allocated_block_head) { /*如果要释放第一个节点*/
        allocated_block_head = allocated_block_head->next;
        free(free_ab);
        return 1;
    }

    pre = allocated_block_head;
    ab = allocated_block_head->next;

    while (ab != free_ab) { pre = ab;  ab = ab->next; }
    pre->next = ab->next;
    free(ab);
    return 2;
}

/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */
display_mem_usage() {
    struct free_block_type* fbt = free_block;
    struct allocated_block* ab = allocated_block_head;
    if (fbt == NULL) return(-1);
    printf("----------------------------------------------------------\n");

    /* 显示空闲区 */
    printf("Free Memory:\n");
    printf("%20s %20s\n", "      start_addr", "       size");
    while (fbt != NULL) {
        printf("%20d %20d\n", fbt->start_addr, fbt->size);
        fbt = fbt->next;
    }
    /* 显示已分配区 */
    printf("\nUsed Memory:\n");
    printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
    while (ab != NULL)
    {
        printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
        ab = ab->next;
    }
    printf("----------------------------------------------------------\n");
    return 0;
}

/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
kill_process()
{
    struct allocated_block* ab;
    int pid;
    printf("Kill Process, pid=");
    scanf("%d", &pid);
    ab = find_process(pid);
    if (ab != NULL)
    {
        free_mem(ab); /*释放ab所表示的分配区*/
        dispose(ab);  /*释放ab数据结构节点*/
    }
}

main()
{
    char choice;
    pid = 0;
    free_block = init_free_block(mem_size); //初始化空闲区
    for (;;)
    {
        display_menu();	//显示菜单
        fflush(stdin);
        choice = getchar();	//获取用户输入
        switch (choice)
        {
        case '1':  set_mem_size();                   break;       //设置内存大小
        case '2': set_algorithm();        flag = 1;    break;	       //设置分配算法
        case '3': new_process();          flag = 1;    break;	       //创建新进程
        case '4':   kill_process();       flag = 1;    break;	       //删除进程
        case '5':   display_mem_usage();  flag = 1;    break;         //显示内存使用
        case '0':   do_exit(); exit(0);                break;	    //释放链表并退出
        default: break;
        }
    }
}
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

五、结果分析与总结

FF算法是以空闲链的首地址递增顺序组织起来，当提出分配需求时，遍历组织好的空白链，找到第一个空间大于等于分配需求的空白分配块分配。若遍历一遍都未找到满足需求的空白块，则分配失败；BF“最佳”指的是大小合适，最接近。空白链以容量大小的顺序组织，每次遍历空白链查找第一个能满足需求的空白块进行分配，这样就一定程度减少了外部碎片的大小。也避免了“大材小用”；WF最坏适应算法和最佳使用算法的空白块选择策略刚好相反，它在扫描整个空表链时，总是挑选一个最大空闲块，从中分割需求的内存块，实际上，这样的算法未必是最坏的
循环首次适应算法的排序方式和首次适应算法相同（查找的起始位置不同），在修改过程中添加一个指针来指明上次查找的位置，从而从下次查找时从此处开始。在从特定位置进行查找时，查找结束的标志有所改变，前面几种结束的表示均是到链尾，而循环首次适应算法查找结束标志是再次查找特定位置。