动态分区分配算法c++

动态分区分配算法是一种内存管理算法，用于在程序运行时为进程分配内存空间。其中常用的动态分区分配算法有以下几种：

1. 首次适应算法（First Fit）：从内存的起始位置开始搜索，找到第一个能够满足进程大小的空闲分区进行分配。

2. 最佳适应算法（Best Fit）：从所有空闲分区中找到最小的能够满足进程大小的空闲分区进行分配。

3. 最坏适应算法（Worst Fit）：从所有空闲分区中找到最大的能够满足进程大小的空闲分区进行分配。

下面是一个使用C++实现首次适应算法的示例代码：

#include <iostream>
using namespace std;

struct Node {
    int start;  //空闲分区的起始地址
    int size;   //空闲分区的大小
    Node* next; //指向下一个空闲分区的指针
};

Node* head = nullptr;  //空闲分区链表的头指针

void init(int start, int size) {
    head = new Node{ start, size, nullptr };
}

void allocate(int processId, int size) {
    Node* p = head;
    Node* prev = nullptr;
    while (p != nullptr) {
        if (p->size >= size) {  //找到了满足进程大小的空闲分区
            Node* q = new Node{ p->start, size, nullptr };  //创建一个新的进程分区
            if (prev != nullptr) {
                prev->next = q;  //更新前一个空闲分区的next指针
            } else {
                head = q;  //更新头指针
            }
            p->start += size;  //修改原空闲分区的起始地址和大小
            p->size -= size;
            cout << "Process " << processId << " allocated " << size << " bytes from " << q->start << endl;
            return;
        }
        prev = p;
        p = p->next;
    }
    cout << "Process " << processId << " cannot be allocated " << size << " bytes" << endl;
}

void deallocate(int processId) {
    Node* p = head;
    Node* prev = nullptr;
    while (p != nullptr) {
        if (p->start == processId) {  //找到了该进程分配的分区
            if (prev != nullptr) {
                prev->next = p->next;  //更新前一个空闲分区的next指针
            } else {
                head = p->next;  //更新头指针
            }
            cout << "Process " << processId << " deallocated " << p->size << " bytes from " << p->start << endl;
            delete p;  //释放该进程分配的分区
            return;
        }
        prev = p;
        p = p->next;
    }
    cout << "Process " << processId << " does not have any allocated space" << endl;
}

void print() {
    Node* p = head;
    while (p != nullptr) {
        cout << "Free space: " << p->start << " - " << p->start + p->size - 1 << ", " << p->size << " bytes" << endl;
        p = p->next;
    }
}

int main() {
    init(0, 1024);  //初始化空闲分区链表
    allocate(1, 100);  //为进程1分配100个字节的空间
    allocate(2, 200);  //为进程2分配200个字节的空间
    print();  //输出空闲分区链表
    deallocate(1);  //释放进程1分配的空间
    print();  //输出空闲分区链表
    return 0;
}