Posts Linux进程通信与内存管理实验
Post
Cancel

Linux进程通信与内存管理实验

2-1 进程的软中断通信

实验要求

编制实现软中断通信的程序 使用系统调用fork()创建两个子进程,再用系统调用signal()让父进程捕捉键盘上发出的中断信号(即按delete键),当父进程接收到这两个软中断的某一个后,父进程用系统调用kill()向两个子进程分别发出整数值为16和17软中断信号,子进程获得对应软中断信号,然后分别输出下列信息后终止: Child process 1 is killed by parent !!
Child process 2 is killed by parent !!
父进程调用wait()函数等待两个子进程终止后,输入以下信息,结束进程执行: Parent process is killed!! 多运行几次编写的程序,简略分析出现不同结果的原因。

运行结果

运行多次之后, 发现结果有两种, 分别是

1
2
3
4
 Child process 2 is killed by parent !!
 Child process 1 is killed by parent !!

 Parent process is killed !!

1
2
3
4
 Child process 1 is killed by parent !!
 Child process 2 is killed by parent !!

 Parent process is killed !!

可以发现两个子进程process 1process 2被杀掉的顺序不确定, 但父进程parent必定在其之后

程序分析

这个程序主要通过signal()函数注册接收到信号后的操作, 再通过kill()函数发终端信号到指定进程

在这个程序中

  • 两个子进程创建后一直等待父进程的中断信号
  • 父进程则在等待一段时间之后将信号发给两个进程, 等待子进程全部退出后结退出

显然, 虽然向两个进程发中断信号不是严格同步的, 但两个独立的子进程接收到信号的前后关系是一个概率事件; 但父进程总需要等待子进程全部退出之后它才退出, 所以才有了运行结果的两种情况

此外, 由于父进程也”注册了中断事件”, 并且进程在sleep时可以被软中断打断, 所以父进程在sleep等待的时间段内接收到软终端后立刻将wait_flag置零并消灭两个子进程

源代码

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
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
int wait_flag;
void stop();

main()
{
    int pid1, pid2;  // 定义两个进程号变量
    signal(SIGINT, stop); // 或者 signal(14,stop);
    signal(SIGQUIT, stop);
    while ((pid1 = fork()) == -1)
        continue; // 若创建子进程1不成功,则空循环
    if (pid1 > 0)
    { // 子进程创建成功,pid1为进程号
        while ((pid2 = fork()) == -1)
            continue; // 创建子进程2
        if (pid2 > 0)
        {
            wait_flag = 1;
            sleep(5);//补充;				// 父进程等待5秒
            //补充
            kill(pid1, SIGUSR1);// 杀死进程1发中断号16
            kill(pid2, SIGUSR2);// 杀死进程2
            wait(0);        // 等待第1个子进程1结束的信号
            wait(0);        // 等待第2个子进程2结束的信号
            printf("\n Parent process is killed !!\n");
            exit(0); // 父进程结束
        }
        /*软中断通信实验程序残缺版(续)*/
        else
        {
            wait_flag = 1;
            signal(SIGUSR2, stop); //补充; // 等待进程2被杀死的中断号17
            while (wait_flag);
            printf("\n Child process 2 is killed by parent !!\n");
            exit(0);
        }
    }
    else
    {
        wait_flag = 1;
        signal(SIGUSR1, stop);
        while(wait_flag);
        printf("\n Child process 1 is killed by parent !!\n");
        exit(0);
    }
}
void stop()
{
    wait_flag = 0;//补充;
}

2-2 进程的管道通信

实验要求

先猜想一下这个程序的运行结果。分析管道通信是怎样实现同步与互斥的,然后按照注释里的要求把代码补充完整,运行程序。

猜想

这个程序中两个子进程共同向父进程中写入内容, 父进程分两次读出内容并打印

输出的顺序取决于写入的顺序, 而写入的顺序在两个独立的进程中实现, 故猜想两条消息输出顺序不确定

运行结果

多次运行之后, 均为如下一种情况, 和猜想有出入

1
2
3
 Child process 1 is sending message!

 Child process 2 is sending message!

由于子进程1是先创建的, 我们将子进程1写入管道前插入1秒的睡眠, 即得到以下结果

1
2
3
 Child process 2 is sending message!

 Child process 1 is sending message!

程序分析

这个程序是实现进程之间的管道通信的

管道pipe分为读端和写端, 两个子进程从写端写入数据, 父进程等待子进程退出之后从读端读出数据

创建管道

1
2
int fd[2];
pipe(fd);

这样fd就成为了一个管道

锁定/解锁管道

1
2
lockf(fd[1], 1, 0);	// 锁定管道
lockf(fd[1], 0, 0);	// 解除管道的锁定

为了解决异步写入导致的冲突问题, 可以在写入前锁定管道, 这样其他进程无法在此进程写入期间向管道写入, 达成互斥的目的

写入/读取管道

1
2
write(fd[1], OutPipe, 50);	//写入
read(fd[0], InPipe, 50);	//读取

管道充当文件描述符, 使用writeread函数进行写入和读取

源代码

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
#include <unistd.h>
#include <signal.h>
#include <stdio.h>
int pid1, pid2; // 定义两个进程变量
main()
{
      int fd[2];
      char OutPipe[100], InPipe[100]; // 定义两个字符数组
      pipe(fd);                       // 创建管道

      // 父进程创建一个子进程
      while ((pid1 = fork()) == -1);
      if (pid1 == 0)
      {
            // 子进程执行
            lockf(fd[1], 1, 0);//补充;	            // 锁定管道
            sprintf(OutPipe, "\n Child process 1 is sending message!\n");     // 给Outpipe赋值
            write(fd[1], OutPipe, 50);//补充;			                  // 向管道写入数据
            sleep(5);                                 // 等待读进程读出数据
            lockf(fd[1], 0, 0);//补充;                // 解除管道的锁定
            exit(0);                                  // 结束进程1
      }
      else
      {
            // 父进程执行
            // 父进程再创建一个子进程
            while ((pid2 = fork()) == -1);
            if (pid2 == 0)
            {
                  // 第二个子进程执行
                  lockf(fd[1], 1, 0);     // 锁定管道的写端
                  sprintf(OutPipe, "\n Child process 2 is sending message!\n");
                  write(fd[1], OutPipe, 50);
                  sleep(5);
                  lockf(fd[1], 0, 0);     // 解锁管道的写端
                  exit(0);
            }
            else
            {
                  // 父进程创建完第二个子进程之后执行
                  wait(0);//补充;               // 等待子进程1 结束
                  read(fd[0], InPipe, 50);//补充;         		      // 从管道中读出数据
                  printf("%s\n", InPipe);       // 显示读出的数据
                  wait(0);                      // 等待子进程2 结束
                  read(fd[0], InPipe, 50);//补充;
                  printf("%s\n", InPipe);
                  exit(0);                      // 父进程结束
            }
      }
}

2-3 内存的分配与回收

实验要求

通过深入理解内存分配管理的三种算法,定义相应的数据结构,编写具体代码。 充分模拟三种算法的实现过程,并通过对比,分析三种算法的优劣。 (1)掌握内存分配FF,BF,WF策略及实现的思路; (2)掌握内存回收过程及实现思路; (3)参考给出的代码思路,实现内存的申请、释放的管理程序,调试运行,总结程序设计中出现的问题并找出原因,写出实验报告。

实验思路

三种内存分配策略: FF/BF/WF

首次适应算法(First Fit)

从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法的目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区,在低址空间造成许多小的空闲区,在高地址空间保留大的空闲区

最佳适应算法(Best Fit)

从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法能使碎片尽量小。为适应此算法,空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区,但造成许多小的空闲区。

最差适应算法 (Worst Fit)

从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区,从而使链表中的结点大小趋于均匀,适用于请求分配的内存大小范围较窄的系统。为适应此算法,空闲分区表(空闲区链)中的空闲分区按大小从大到小进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区,尽量减少小的碎片产生

内存分配

按照上文的三种不同的内存分配策略进行: 首先执行rearrange操作, 将空闲内存按照策略进行排序, 再寻找合适的空闲分区进行分配

  • 找到可满足空闲分区且分配后剩余空间足够大,则分割
  • 找到可满足空闲分区且但分配后剩余空间比较小(小于约定的MIN_SLICE),则一起分配
  • 找不到可满足需要的空闲分区但空闲分区之和能满足需要,则采用内存紧缩技术,进行空闲分区的合并,然后再分配
  • 在成功分配内存后,应保持空闲分区按照相应算法有序
  • 分配成功则返回1,否则返回-1

为了实现以上的策略, 应为FF/BF/WF定义三个函数rearrange_FF, rearrange_BFrearrange_WF用于重新排序空闲内存块, 再定义三个函数allocate_FF, allocate_BFallocate_WF用于应用三种策略分配内存, 在这三种分配函数中, 先排序空闲内存, 再找到要分配的空间, 使用allocate函数进行分配, 如果找不到足够大的内存, 则将所需内存和当前剩余的总内存current_free_mem_size进行比较, 如果可以, 则使用内存紧缩mem_retrench合并空闲区并分配给目标进程

内存回收

进行内存回收的基本策略如下:

  • 将新释放的结点插入到空闲分区队列末尾
  • 对空闲链表按照地址有序排列
  • 检查并合并相邻的空闲分区
  • 将空闲链表重新按照当前算法排序

实验总结回顾

本次实验的重点是操作两个链表:

  • free_block为首的空闲块链表, 存储free_block_type
  • allocated_block_head为首的进程分配内存块链表, 存储allocated_block

主要的操作是进行内存分配和内存回收, 即协调修改两个链表

由于我对单链表的排序和修改不是很熟练, 所以花了一点心思去琢磨这方面的内容, 好在都是很浅显的东西, 把过程理顺就可以了

此外, 通过这次实验, 也对操作系统分配内存的三种策略, 还有内存紧缩等技术有了进一步的了解

源代码

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
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
#include <stddef.h>
#include <stdio.h>
#include <malloc.h>
#include <unistd.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

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

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

// 描述已分配的内存块
/*每个进程分配到的内存块的描述*/
struct allocated_block
{
    int pid;
    int size;
    int start_addr;
    char process_name[PROCESS_NAME_LEN];
    struct allocated_block *next;
};

int mem_size = DEFAULT_MEM_SIZE; /*内存大小*/
int ma_algorithm = MA_FF;        /*当前分配算法*/
static int pid = 0;              /*初始pid*/
int flag = 0;                    /*设置内存大小标志*/
/*进程分配内存块链表的首指针*/
struct allocated_block *allocated_block_head = NULL;

int free_block_count = 0; // 补充

struct free_block_type *init_free_block(int mem_size);
display_menu();
set_mem_size();
set_algorithm();
rearrange(int algorithm);
rearrange_FF();
rearrange_BF();
rearrange_WF();
new_process();
int allocate_mem(struct allocated_block *ab);
int allocate(struct free_block_type *pre, struct free_block_type *allocate_free_block, struct allocated_block *ab);
int allocate_FF(struct allocated_block* ab);
int allocate_BF(struct allocated_block* ab);
int allocate_WF(struct allocated_block* ab);
int mem_retrench(struct allocated_block *ab);
kill_process();
int free_mem(struct allocated_block *ab);
int dispose(struct allocated_block *free_ab);
display_mem_usage();
struct allocated_block* find_process(int pid);


main()
{
    char choice;
    pid = 0;
    free_block = init_free_block(mem_size); //初始化空闲区
    while (1)
    {
        display_menu(); //显示菜单
        fflush(stdin);
        choice = getchar(); //获取用户输入
        if(choice == '\n'){
            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); //释放链表并退出
            default:
                break;
        }
    }
}

/*初始化空闲块,默认为一块,可以指定大小及起始地址*/
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;
    current_free_mem_size = mem_size;
    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;
        current_free_mem_size = mem_size;
    }
    flag = 1;
    return 1;
}

/* 设置当前的分配算法 */
set_algorithm()
{
    int 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);
}

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


/*按FF算法重新整理内存空闲块链表*/
rearrange_FF()  // 补充
{
    /*
        首次适应算法(First Fit):从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给
        作业,这种方法的目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲分区要按地址由低到
        高进行排序。该算法优先使用低址部分空闲区,在低址空间造成许多小的空闲区,在高地址空间保留大的空闲区。
    */
    struct free_block_type *forehead = free_block, *pre, *rear;
    struct free_block_type *end = NULL;
    printf("debug3.1\n");
    // 如果空闲块头部为空, 即没有空闲块, 返回-1
    if(free_block == NULL)
        return -1;
    printf("debug3.2\n");
    // forehead, pre, rear 遍历
    pre = forehead -> next;
    if(pre != NULL){
        // 比较第一个空闲块和第二个空闲块开始地址的大小
        if(forehead->start_addr > pre->start_addr){
            // 交换开头两个空闲块
            // 修改 next
            free_block->next = pre->next;
            pre->next = free_block;
            // 修改空闲块链表头
            free_block = pre;
            // 更新 forehead pre rear
            forehead = free_block;
            pre = forehead->next;
            rear = pre->next;
        }
    }else{
        // 如果空闲块只有一个, 则无需排序
        return 0;
    }


    if(rear == NULL){
        // 如果只有两个空闲块, 已经排序完毕, 直接返回即可
        return 0;
    }
    // 对于两个以上的空闲块, 使用冒泡排序
    // 此时 forehead指向第一个空闲块, end 初始值为 NULL
    // 遍历过程中比较交换 pre, rear
    while (end != free_block->next)
    {
        forehead = free_block;
        pre = forehead->next;
        rear = pre->next;
        if(forehead->start_addr > pre->start_addr){
            // 交换开头两个空闲块
            // 修改 next
            free_block->next = pre->next;
            pre->next = free_block;
            // 修改空闲块链表头
            free_block = pre;
            // 更新 forehead pre rear
            forehead = free_block;
            pre = forehead->next;
            rear = pre->next;
        }
        while (pre->next != end)
        {
            // 比较 pre 和 rear开始地址的大小
            if(pre->start_addr > rear->start_addr){
                // 交换 pre和 rear
                // 修改next
                pre->next = rear->next;
                rear->next = pre;
                forehead->next = rear;
                // 更新 forehead pre rear
                forehead = rear;
                rear = pre->next;
            }
            else{
                // 不进行交换
                // 更新 forehead pre rear
                forehead = pre;
                pre = rear;
                rear = pre->next;
            }
        }
        end = pre;
    }
    return 0;
}
/*按BF算法重新整理内存空闲块链表*/
rearrange_BF()  //补充
{   
    /*
        最佳适应算法(Best Fit):从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法能使
        碎片尽量小。为适应此算法,空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序,自表头开始查找到第一
        个满足要求的自由分区分配。该算法保留大的空闲区,但造成许多小的空闲区。
    */

    // 实现类似于 rearrange_FF, 将按照内存起始地址排序换位按照空间大小排序
    struct free_block_type *forehead = free_block, *pre, *rear;
    struct free_block_type *end = NULL;
    printf("debug3.1\n");
    // 如果空闲块头部为空, 即没有空闲块, 返回-1
    if(free_block == NULL)
        return -1;
    printf("debug3.2\n");
    // forehead, pre, rear 遍历
    pre = forehead -> next;
    if(pre != NULL){
        // 比较第一个空闲块和第二个空闲块的大小
        if(forehead->size > pre->size){
            // 交换开头两个空闲块
            // 修改 next
            free_block->next = pre->next;
            pre->next = free_block;
            // 修改空闲块链表头
            free_block = pre;
            // 更新 forehead pre rear
            forehead = free_block;
            pre = forehead->next;
            rear = pre->next;
        }
    }else{
        // 如果空闲块只有一个, 则无需排序
        return 0;
    }


    if(rear == NULL){
        // 如果只有两个空闲块, 已经排序完毕, 直接返回即可
        return 0;
    }
    // 对于两个以上的空闲块, 使用冒泡排序
    // 此时 forehead指向第一个空闲块, end 初始值为 NULL
    // 遍历过程中比较交换 pre, rear
    while (end != free_block->next)
    {
        forehead = free_block;
        pre = forehead->next;
        rear = pre->next;
        if(forehead->size > pre->size){
            // 交换开头两个空闲块
            // 修改 next
            free_block->next = pre->next;
            pre->next = free_block;
            // 修改空闲块链表头
            free_block = pre;
            // 更新 forehead pre rear
            forehead = free_block;
            pre = forehead->next;
            rear = pre->next;
        }
        while (pre->next != end)
        {
            // 比较 pre 和 rear的大小
            if(pre->size > rear->size){
                // 交换 pre和 rear
                // 修改next
                pre->next = rear->next;
                rear->next = pre;
                forehead->next = rear;
                // 更新 forehead pre rear
                forehead = rear;
                rear = pre->next;
            }
            else{
                // 不进行交换
                // 更新 forehead pre rear
                forehead = pre;
                pre = rear;
                rear = pre->next;
            }
        }
        end = pre;
    }
    return 0;
}


/*按WF算法重新整理内存空闲块链表*/
rearrange_WF()  // 补充
{

   /*
        最差适应算法 (Worst Fit): 从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区,从而使链表中
        的结点大小趋于均匀,适用于请求分配的内存大小范围较窄的系统。为适应此算法,空闲分区表(空闲区链)中的空
        闲分区按大小从大到小进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区,尽量
        减少小的碎片产生
    */
    // 实现类似于 rearrange_FF, 将按照内存起始地址排序换位按照空间大小排序
    struct free_block_type *forehead = free_block, *pre, *rear;
    struct free_block_type *end = NULL;
    
    // 如果空闲块头部为空, 即没有空闲块, 返回-1
    if(free_block == NULL)
        return -1;
    // forehead, pre, rear 遍历
    pre = forehead -> next;
    if(pre != NULL){
        // 比较第一个空闲块和第二个空闲块的大小
        if(forehead->size < pre->size){
            // 交换开头两个空闲块
            // 修改 next
            free_block->next = pre->next;
            pre->next = free_block;
            // 修改空闲块链表头
            free_block = pre;
            // 更新 forehead pre rear
            forehead = free_block;
            pre = forehead->next;
            rear = pre->next;
        }
    }else{
        // 如果空闲块只有一个, 则无需排序
        return 0;
    }


    if(rear == NULL){
        // 如果只有两个空闲块, 已经排序完毕, 直接返回即可
        return 0;
    }
    // 对于两个以上的空闲块, 使用冒泡排序
    // 此时 forehead指向第一个空闲块, end 初始值为 NULL
    // 遍历过程中比较交换 pre, rear
    while (end != free_block->next)
    {
        forehead = free_block;
        pre = forehead->next;
        rear = pre->next;
        if(forehead->size < pre->size){
            // 交换开头两个空闲块
            // 修改 next
            free_block->next = pre->next;
            pre->next = free_block;
            // 修改空闲块链表头
            free_block = pre;
            // 更新 forehead pre rear
            forehead = free_block;
            pre = forehead->next;
            rear = pre->next;
        }
        while (pre->next != end)
        {
            // 比较 pre 和 rear的大小
            if(pre->size < rear->size){
                // 交换 pre和 rear
                // 修改next
                pre->next = rear->next;
                rear->next = pre;
                forehead->next = rear;
                // 更新 forehead pre rear
                forehead = rear;
                rear = pre->next;
            }
            else{
                // 不进行交换
                // 更新 forehead pre rear
                forehead = pre;
                pre = rear;
                rear = pre->next;
            }
        }
        end = pre;
    }
    return 0;
}

/*创建新的进程,主要是获取内存的申请数量*/
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;
    // }
    if (ret == -1)
    { /*分配不成功*/
        printf("Allocation fail\n");
        free(ab);
        return -1;
    }
    return 3;
}

/*为新进程分配内存空间*/
int allocate(struct free_block_type *pre, struct free_block_type *allocate_free_block, struct allocated_block *ab){
    struct allocated_block *p = allocated_block_head;
    ab->start_addr = allocate_free_block->start_addr;
    
    // 如果被分配的空闲块的剩余空间小于最小 SLICE, 视为这个空闲块被使用完毕
    if(allocate_free_block->size - ab->size < MIN_SLICE){
        ab->size = allocate_free_block->size;
        if(pre != NULL){
            pre->next = allocate_free_block->next;
        }
        else
        {
            free_block = allocate_free_block->next;
        }
        free(allocate_free_block);
    }
    // 反之可以继续利用这个空闲块
    else{
        allocate_free_block->start_addr += ab->size;
        allocate_free_block->size -= ab->size;
    }

    // 把分配好的块加入链表
    if(p==NULL){
        allocated_block_head = ab;
    }
    else{
        while(p->next != NULL){
            p = p->next;
        }
        p->next = ab;
    }

    return 1;
}

/*按照 First fit算法为新进程分配空间*/
int allocate_FF(struct allocated_block* ab){
    // 补充
    // 先根据 FF策略整理内存, 整理后空闲链表按照地址从低到高排序
    rearrange_FF();
    int ret;
    struct free_block_type *pre = NULL, *ff = free_block;
    if(ff == NULL){
        return -1;
    }
    while (ff != NULL)
    {
        if(ff->size >= ab->size){
            ret = allocate(pre, ff ,ab);
            break;
        }
        // 更新 pre, ff
        pre = ff;
        ff = pre->next;
    }
    if(ff == NULL && current_free_mem_size >= ab->size){
        ret = mem_retrench(ab);
    }
    else{
        return -2;
    }
    rearrange_FF();
    return ret;
}

/*按照 Best fit算法为新进程分配空间*/
int allocate_BF(struct allocated_block* ab){
    // 补充
    // 先根据 BF策略整理内存, 整理后空闲链表按照从小到大排序
    rearrange_BF();
    int ret;
    struct free_block_type *pre = NULL, *bf = free_block;
    if(bf == NULL){
        return -1;
    }
    while (bf != NULL)
    {
        if(bf->size >= ab->size){
            ret = allocate(pre, bf, ab);
            break;
        }
        pre = bf;
        bf = pre->next;
    }
    if(bf == NULL && current_free_mem_size >= ab->size){
        ret = mem_retrench(ab);
    }
    else{
        return -2;
    }
    rearrange_BF();
    return ret;
}

/*按照 Worst fit算法为新进程分配空间*/
int allocate_WF(struct allocated_block* ab){
    // 补充
    // 先根据 WF策略整理内存, 整理后最大的一块内存在链表头
    rearrange_WF();
    printf("debug4.1.1\n");
    int ret;
    struct free_block_type *wf = free_block;
    if(wf == NULL){
        return -1;
    }
    printf("debug4.1.2\n");
    if(wf->size >= ab->size){
        printf("debug4.2\n");
        ret = allocate(NULL, wf, ab);
        printf("debug4.3\n");
    }
    else if(current_free_mem_size >= ab->size){
        printf("debug4.4\n");
        ret = mem_retrench(ab);
    }
    else
    {
        printf("debug4.5\n");
        return -2;
    }
    rearrange_WF();
    return ret;
}


/* 通过内存紧缩, 为进程分配空间 */
int mem_retrench(struct allocated_block *ab){
    // allocated_block_head指向原分配链的头部
    struct allocated_block *allocated_work,*allocated_pre = allocated_block_head;
    // free_pre指向原空闲链的第二块
    struct free_block_type *free_work,*free_pre = free_block->next;
    if(allocated_pre == NULL)
        return -1;
    // 将分配链头部的起始地址设为内存起始地址
    allocated_pre->start_addr = DEFAULT_MEM_START;
    // 根据分配链, 把所有分配块的空间重分配, 使其满足内存紧缩的要求
    allocated_work= allocated_pre->next;
    while(allocated_work!= NULL)
    {
        allocated_work->start_addr= allocated_pre->start_addr+ allocated_pre->size;
        allocated_pre = allocated_work;
        allocated_work = allocated_pre->next;
    }
    // 更改空闲链头部的起始地址为分配区的末端
    free_block->start_addr= allocated_pre->start_addr+ allocated_pre->size;
    // 剩余的一整块大内存直接分配给空闲链头部
    free_block->size= current_free_mem_size;
    // 断开其余空闲块链表项
    free_block->next = NULL;
    // 清空除空闲链中除头部以外的其它表项
    free_work = free_pre->next;
    while(free_pre != NULL)
    {
        free(free_pre);
        free_pre = free_work;
        if(free_pre != NULL)
            free_work = free_pre->next;
    }
    // 根据最新的空闲链进行分配
    allocate(NULL,free_block,ab);
    return 1;
}


/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{
    struct free_block_type *fbt, *pre;
    int request_size = ab->size;
    fbt = pre = free_block;
    //根据当前算法在空闲分区链表中搜索合适空闲分区进行分配,分配时注意以下情况:
    // 1. 找到可满足空闲分区且分配后剩余空间足够大,则分割
    // 2. 找到可满足空闲分区且但分配后剩余空间比较小,则一起分配
    // 3. 找不到可满足需要的空闲分区但空闲分区之和能满足需要,则采用内存紧缩技术,进行空闲分区的合并,然后再分配
    // 4. 在成功分配内存后,应保持空闲分区按照相应算法有序
    // 5. 分配成功则返回1,否则返回-1
    
    // 补充
    printf("debug4.1\n");
    int ret;
    switch (ma_algorithm)
    {
    case MA_FF:
        ret = allocate_FF(ab);
        break;
    case MA_BF:
        ret = allocate_BF(ab);
        break;
    case MA_WF:
        ret = allocate_WF(ab);
        break;
    default:
        break;
    }
    if(ret == 1){
        current_free_mem_size -= request_size;
    }
    return ret;

}




/*删除进程,归还分配的存储空间,并删除描述该进程内存分配的节点*/
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数据结构节点*/
    }
}

/*将ab所表示的已分配区归还,并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
    int algorithm = ma_algorithm;
    struct free_block_type *fbt, *pre, *work;
    fbt = (struct free_block_type *)malloc(sizeof(struct free_block_type));
    if (!fbt)
        return -1;
    // 进行可能的合并,基本策略如下
    // 1. 将新释放的结点插入到空闲分区队列末尾
    // 2. 对空闲链表按照地址有序排列
    // 3. 检查并合并相邻的空闲分区
    // 4. 将空闲链表重新按照当前算法排序
    // 补充
    pre = free_block;
    
    // 1. 将新释放的结点插入到空闲分区队列末尾
    fbt->start_addr = ab->start_addr;
    fbt->size = ab->size;
    fbt->next = NULL;
    if(pre != NULL){
        while (pre->next != NULL)
        {
            pre = pre->next;
        }
        pre->next = fbt;
    }else{
        free_block = fbt;
    }
    printf("debug1\n");
    // 2. 对空闲链表按照地址有序排列
    rearrange_FF();
    printf("debug2\n");
    // 3. 检查并合并相邻的空闲分区
    pre = free_block;
    // pre != NULL 因为刚释放过内存, 所以一定有空闲内存
    work = pre->next;
    while (work != NULL)
    {
        // 满足相邻的合并条件
        if(pre->start_addr + pre->size == work->start_addr){
            pre->size += work->size;
            pre->next = work->next;
            free(work);
            work = pre->next;
        }
        else{
            pre = work;
            work = pre->next;
        }
    }
    current_free_mem_size += ab->size;
    printf("debug3\n");
    // 4. 将空闲链表重新按照当前算法排序
    switch (ma_algorithm)
    {
    case MA_FF:
        rearrange_FF();
        break;
    case MA_BF:
        rearrange_BF();
        break;
    case MA_WF:
        rearrange_WF();
        break;
    default:
        break;
    }

    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;
}

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

This post is licensed under CC BY 4.0 by the author.