内存分配算法-C语言 | Memory Allocation Algorithms in C

母亲节快乐 🌹
Happy Mother's Day 🌹
2023-05-14

Made by Mike_Zhang

---

Unfold Operating Systems Topics | 展开操作系統主题 >

---

Intro

导言

这学期学了操作系统 (Operating Systems) 课程，当中的一大重点是 内存分配算法 (Memory Allocation Algorithms) 。此算法有几种变式，但是其中的逻辑相对固定，因此我用C语言编写了程序来模拟这些算法。这使得我能够对这些算法有更深的理解，同时也能对我自己演算的结果进行验证。

本文将介绍三种内存分配算法，及其对应的代码和运行示例。
包括：

• First Fit (FF);
• Best Fit (BF);
• Worst Fit (WF).

---

0. Talk is Cheap. Show Me the Code.

不废话，上代码。

下文代码的GitHub链接: Memory Allocation Algorithms

按照惯例，我计划将在UltraFish Plus上开发网页版的内存分配算法模拟器，如果你对此感兴趣，可以联系我合作开发，感谢。

---

1. First Fit

FF算法的逻辑很直接，找到第一个能够满足该进程内存的空闲分区，将进程放入其中。

以下为代码的主要部分:

int* memAllocFF;

// First Fit Algorithm
void FF(int* inMemSize, int *inHoleSize, int inM, int inH){
    memAllocFF = (int*) malloc(sizeof(int)*inM);
    int i;
    for (i=0;i<inM;i++) {
        memAllocFF[i]=-1;
    }
    for (i=0;i<inM;i++) {
        int j;
        for (j=0;j<inH;j++) {
            if (inMemSize[i]<=inHoleSize[j]) { // first fit
                memAllocFF[i]=j;
                inHoleSize[j]-=inMemSize[i];
                break;
            }
        }
    }
}

以下为运行结果示例:

~$ ./Memory_Allocation
Memory Allocation Algorithms:
> Original Request Memory:      50 88 96 37 93 35 63 27 49 68 33 58 
> Original Hole Size:           234 321 108 
----------------------------------------------
1. First Fit Algorithm
Request No.     Request Size    Allocated Hole
1               50              1
2               88              1
3               96              1
4               37              2
5               93              2
6               35              2
7               63              2
8               27              2
9               49              2
10              68              3
11              33              3
12              58              Not Allocated
> Remaining Hole Size:          0 17 7 
> Average Fit Rate:             0.917
> Average Memory Utilization:   0.976
> Average Fragmentation Rate:   0.036

---

2. Best Fit

BF算法对FF算法进行了优化，采用保守的策略，找到能够满足该进程内存的最小空闲分区，将进程放入其中。

• 该算法产出最小的剩余空闲分区；
• 不浪费大的空闲分区，以满足后续的大进程。

以下为代码的主要部分:

int* memAllocBF;

// Best Fit Algorithm
void BF(int* inMemSize, int *inHoleSize, int inM, int inH){
    memAllocBF = (int*) malloc(sizeof(int)*inM);
    int i;
    for (i=0;i<inM;i++) {
        memAllocBF[i]=-1;
    }
    for (i=0;i<inM;i++) {
        int j;
        int bfIndex=-1;
        for (j=0;j<inH;j++) {
            if (inMemSize[i]<=inHoleSize[j]) { // fit
                if (bfIndex==-1) { // first time fit
                    bfIndex=j;
                } else if (inHoleSize[j]<inHoleSize[bfIndex]) { // best fit
                    bfIndex=j;
                }
            }
        }
        if (bfIndex!=-1) {
            memAllocBF[i]=bfIndex;
            inHoleSize[bfIndex]-=inMemSize[i];
        }
    }
}

以下为运行结果示例:

~$ ./Memory_Allocation
Memory Allocation Algorithms:
> Original Request Memory:      50 88 96 37 93 35 63 27 49 68 33 58 
> Original Hole Size:           234 321 108 
----------------------------------------------
1. Best Fit Algorithm
Request No.     Request Size    Allocated Hole
1               50              3
2               88              1
3               96              1
4               37              1
5               93              2
6               35              3
7               63              2
8               27              2
9               49              2
10              68              2
11              33              Not Allocated
12              58              Not Allocated
> Remaining Hole Size:          13 21 23 
> Average Fit Rate:             0.833
> Average Memory Utilization:   0.943
> Average Fragmentation Rate:   0.086

---

3. Worst Fit

WF算法与BF算法相反，采用激进的策略，找到能够满足该进程内存的最大空闲分区，将进程放入其中。

• 该算法产出最大的剩余空闲分区；
• 确保剩下的空闲分区足够大；

以下为代码的主要部分:

int* memAllocWF;

// Worst Fit Algorithm
void WF(int* inMemSize, int *inHoleSize, int inM, int inH){
    memAllocWF = (int*) malloc(sizeof(int)*inM);
    int i;
    for (i=0;i<inM;i++) {
        memAllocWF[i]=-1;
    }
    for (i=0;i<inM;i++) {
        int j;
        int wfIndex=-1;
        for (j=0;j<inH;j++) {
            if (inMemSize[i]<=inHoleSize[j]) { // fit
                if (wfIndex==-1) { // first time fit
                    wfIndex=j;
                } else if (inHoleSize[j]>inHoleSize[wfIndex]) { // worst fit
                    wfIndex=j;
                }
            }
        }
        if (wfIndex!=-1) {
            memAllocWF[i]=wfIndex;
            inHoleSize[wfIndex]-=inMemSize[i];
        }
    }
}

以下为运行结果示例:

Memory Allocation Algorithms:
> Original Request Memory:      50 88 96 37 93 35 63 27 49 68 33 58 
> Original Hole Size:           234 321 108 
----------------------------------------------
3. Worst Fit Algorithm
Request No.     Request Size    Allocated Hole
1               50              2
2               88              2
3               96              1
4               37              2
5               93              2
6               35              1
7               63              3
8               27              1
9               49              1
10              68              Not Allocated
11              33              2
12              58              Not Allocated
> Remaining Hole Size:          27 20 45 
> Average Fit Rate:             0.833
> Average Memory Utilization:   0.908
> Average Fragmentation Rate:   0.139

一般来说，FF和BF算法的表现优于WF算法。

---

References

A. Silberschatz, Peter Baer Galvin, and G. Gagne, Operating system concepts. Hoboken (Nj): Wiley, Cop, 2018.

---

Outro

尾巴

操作系统相关内容的代码会马上继续更新。
最后，希望大家一起交流，分享，指出问题，谢谢！

---

原创文章，转载请标明出处
Made by Mike_Zhang

感谢你的支持