0x01 首次适应（First Fit，FF）算法

１. 简介

FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统系统中已没有足够大的内存分配给该进程，内存分配失败，返回。

2. 优缺点

该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑会增加查找可用空闲分区时的开销。

0x02 循环首次适应（Next Fit，NF）算法

1. 简介

为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。

2. 优缺点

该算法能使内存中的空闲分区分布得更均匀，从而减少了空闲分区时的开销，但这样会缺乏大的空闲分区

0x03 例子

1. 题目

假设内存总大小为1024，开始地址为0，结束地址为1023。有10个进程，它们所需要的内存大小随机在[100,200]之间产生。从第1个进程开始，使用指定的分区分配算法来依次为进程分配内存分区；如果还有足够大的空闲分区，则给该进程进行分配，并更新空闲分区链表。当对一块空闲分区进行划分时，在这块空闲分区的地址范围内随机产生一个划分的开始位置，然后划分出当前进程大小的分区。如果没有足够大的空闲分区，则提示内存分配失败，然后继续为下一个进程分配空闲内存分区，直到10个进程都处理完毕。
10个进程处理完内存分配后，执行内存回收过程。注意，在回收的时候，如果发现当前回收块的前面和后面都是空闲区块，则我们只把回收块与前面的空闲区块进行合并回收。依次从第1个成功分配了内存分区的进程开始，回收其占用的内存分区，直到所有被占用的分区都回收完毕。

2. 代码

#include<iostream>
#include<stdlib.h>
#include<time.h>


class MemoryAllocation {
private:
    struct Block {
        int id;             //分区的序号
        int size;           //分区的大小
        int startAddr;      //分区的开始位置
        bool status;        //分区的状态：true为空闲，false为被占用
        int pid;            //如果该分区被占用，则存放占用进程的id; 否则为 - 1
        struct Block* prev;  //指向前面一块内存分区
        struct Block* next;   //指向后面一块内存分区
    };

    struct PCB {
        int pid;            //进程的序号
        int neededMem;      //需要的内存分区大小
        int status;         //1: 内存分配成功；-1：分配失败
        int blockID;        //如果分配成功，保存占用分区的id,否则为 - 1
        struct PCB* next;   //指向下一个PCB
    };

    PCB* pcbHead = new PCB; // 进程链表
    Block* freeHead = new Block; // 分区链表

    void traverseList(int);
    void memCollect();
    void allocateFF();
    void allocateNF();

public:
    MemoryAllocation();
    ~MemoryAllocation();
};

// 垃圾回收
void MemoryAllocation::memCollect() {
    std::cout << "开始回收......\n";
    Block* fNode = freeHead->next;

    while (freeHead->next->next) {
        Block* buf = fNode->next->next;
        std::cout << "已合并分区" << fNode->id << "和分区" << fNode->next->id << '\n';
        fNode->size += fNode->next->size;
        delete fNode->next;
        if (buf) {
            fNode->next = buf;
            traverseList(2);
        }
        else {
            fNode->next = NULL;
            fNode = freeHead->next;
            traverseList(2);
        }
    }
    freeHead->next->size += 1;
    std::cout << "回收完毕\n";
}

// 遍历链表
void MemoryAllocation::traverseList(int flag) { 
    switch (flag) { // 1为打印两个链表，2为只打印分区链表
    case 1: {
        std::cout << "PCB链表\n";
        std::cout << "PID\t" << "需要内存\t" << "状态\t" << "分区ID\n";
        PCB* pNode = pcbHead->next;
        while (pNode) {
            std::cout << pNode->pid << '\t' << pNode->neededMem << "\t\t" << pNode->status << '\t' << pNode->blockID << '\n';
            pNode = pNode->next;
        }
    }
    case 2: {
        std::cout << "\n分区链表\n";
        std::cout << "ID\t" << "开始地址\t" << "分区大小\t" << "状态\t" << "PID\n";
        Block* fNode = freeHead->next;
        while (fNode) {
            std::cout << fNode->id << '\t' << fNode->startAddr << "\t\t" << fNode->size << "\t\t" << std::boolalpha << fNode->status << '\t' << fNode->pid << '\n';
            fNode = fNode->next;
        }
        std::cout << '\n';
        break;
    }
    }
}

MemoryAllocation::MemoryAllocation() {
    srand((unsigned)time(NULL));
    // 初始化PCB链表
    PCB* pre = pcbHead;
    for (int i = 0; i < 10; i++) {
        PCB* p = new PCB;
        p->pid = i;
        p->neededMem = rand() % 100 + 101;
        p->status = 0;
        p->blockID = -1;
        pre->next = p;
        pre = p;
        p->next = NULL;
    }
    // 初始化空闲分区链表
    Block* p = new Block;
    p->id = 0;
    p->size = 1024;
    p->startAddr = 0;
    p->status = true;
    p->pid = -1;
    freeHead->next = p;
    p->prev = NULL;
    p->next = NULL;
    traverseList(1);
    std::cout << "输入想要使用的算法：\n1 --- 首次适应算法（FF）\n2 --- 循环首次适应算法（NF）\n";
    int flag = 0;
    std::cin >> flag;
    switch (flag)
    {
    case 1:
        allocateFF();
        break;
    case 2:
        allocateNF();
        break;
    default:
        std::cout << "输入不合法\n";
        break;
    }
}

void MemoryAllocation::allocateFF() {
    std::cout << "开始使用FF算法分配......\n";
    PCB* pNode = pcbHead->next;
    bool flag = false;
    int id = 1;
    while (pNode) {
        flag = false;
        Block* fNode = freeHead->next;
        while (fNode) { // 遍历空闲分区表尝试分配
            if (pNode->neededMem <= fNode->size && fNode->status) {
                int nextAddr;
                Block* buf = fNode->next; // 准备切割的区块的下一个区块
                if (buf) {
                    nextAddr = buf->startAddr;
                }
                else {
                    nextAddr = 1023;
                }
                pNode->status = 1;
                // 切割空闲区块
                int startAddr = fNode->startAddr + 1 + rand() % (fNode->size - pNode->neededMem + 1); // 在空闲区块中随机选取一个开始地址并保证分配后不会超出空闲区块
                int startAddr2 = startAddr + pNode->neededMem; // p2区块的开始地址紧跟新区块
                fNode->size = startAddr - fNode->startAddr;
                // 创建分配内存的区块
                Block* p = new Block;
                p->prev = fNode;
                p->id = id++;
                p->size = pNode->neededMem;
                p->startAddr = startAddr;
                p->status = false;
                p->pid = pNode->pid;
                pNode->blockID = p->id;
                fNode->next = p;
                // 创建下一个区块
                Block* p2 = new Block;
                p2->prev = p;
                p2->id = id++;
                p2->size = nextAddr - (p->startAddr + p->size);
                p2->startAddr = startAddr2;
                p2->status = true;
                p2->pid = -1;
                p2->next = buf;
                p->next = p2; // p、p2以及p2后面的区块连接
                flag = true;
                break;
            }
            else {
                fNode = fNode->next;
            }
        }
        if (flag) { // 如果分配成功
            std::cout << "进程" << pNode->pid << "分配成功！占用区块" << fNode->next->id <<"，开始地址为："<< fNode->next->startAddr << '\n';
            traverseList(1);
        }
        else {
            std::cout << "进程" << pNode->pid << "分配失败！\n";
        }
        pNode = pNode->next;
    }
    std::cout << "所有进程分配完毕\n\n";
    memCollect();
}

void MemoryAllocation::allocateNF() {
    std::cout << "开始使用NF算法分配......\n";
    PCB* pNode = pcbHead->next;
    bool flag = false;
    int id = 1;
    int deep = 0;
    Block* fNode = freeHead->next; // FF和NF的这个语句位置不同
    while (pNode) {
        flag = false;
        while (fNode) { // 遍历空闲分区表尝试分配
            if (pNode->neededMem <= fNode->size && fNode->status) {
                int nextAddr;
                Block* buf = fNode->next; // 准备切割的区块的下一个区块
                if (buf) {
                    nextAddr = buf->startAddr;
                }
                else {
                    nextAddr = 1023;
                }
                pNode->status = 1;
                // 切割空闲区块
                int startAddr = fNode->startAddr + 1 + rand() % (fNode->size - pNode->neededMem + 1); // 在空闲区块中随机选取一个开始地址并保证分配后不会超出空闲区块
                int startAddr2 = startAddr + pNode->neededMem; // p2区块的开始地址紧跟新区块
                fNode->size = startAddr - fNode->startAddr;
                // 创建分配内存的区块
                Block* p = new Block;
                p->prev = fNode;
                p->id = id++;
                p->size = pNode->neededMem;
                p->startAddr = startAddr;
                p->status = false;
                p->pid = pNode->pid;
                pNode->blockID = p->id;
                fNode->next = p;
                // 创建下一个区块
                Block* p2 = new Block;
                p2->prev = p;
                p2->id = id++;
                p2->size = nextAddr - (p->startAddr + p->size);
                p2->startAddr = startAddr2;
                p2->status = true;
                p2->pid = -1;
                p2->next = buf;
                p->next = p2; // p、p2以及p2后面的区块连接
                flag = true;
                break;
            }
            else {
                if (fNode->next) {
                    fNode = fNode->next;
                }
                else {
                    fNode = freeHead->next;
                    deep++;
                    if (deep > 2)break;
                }
            }
        }
        if (flag) { // 如果分配成功
            std::cout << "进程" << pNode->pid << "分配成功！占用区块" << fNode->next->id << "，开始地址为：" << fNode->next->startAddr << '\n';
            traverseList(1);
        }
        else {
            std::cout << "进程" << pNode->pid << "分配失败！\n";
        }
        pNode = pNode->next;
    }
    std::cout << "所有进程分配完毕\n\n";
    memCollect();
}


MemoryAllocation::~MemoryAllocation() {
    delete pcbHead;
    delete freeHead;
}

int main() {
    MemoryAllocation memAlloc = MemoryAllocation();
    return 0;
}

3. 结果