动态分区分配算法c++首次适应算法

动态分区分配算法是操作系统中用于管理内存的一种方式，其中包括了多种分配算法。首次适应算法是其中一种，其思路是在内存中寻找第一个满足大小要求的空闲分区，并将该分区分配给请求进程。

以下是C++实现首次适应算法的代码，包括了一个分区结构体和一个动态分配类：

#include<iostream>
using namespace std;

struct Partition{
    int startAddr;   // 起始地址
    int length;      // 分区长度
    bool isFree;     // 是否空闲
};

class Allocate{
private:
    Partition *mem;  // 内存分区
    int n;           // 分区数

public:
    Allocate(int* sizes, int n);  // 分配内存
    void showMemory();            // 显示内存布局
    void allocate(int size);      // 分配内存
    void freeMem(int startAddr);  // 释放内存
};

Allocate::Allocate(int* sizes, int n){
    this->n = n;
    mem = new Partition[n];

    // 初始化内存分区
    for(int i=0;i<n;i++){
        mem[i].startAddr = i==0?0:mem[i-1].startAddr+mem[i-1].length;
        mem[i].length = sizes[i];
        mem[i].isFree = true;
    }
}

void Allocate::showMemory(){
    cout<<"Memory layout:"<<endl;
    for(int i=0;i<n;i++){
        cout<<"Partition "<<i+1<<" : ";
        cout<<mem[i].startAddr<<" - "<<mem[i].startAddr+mem[i].length-1<<" ";
        if(mem[i].isFree) cout<<"Free"<<endl;
        else cout<<"Occupied"<<endl;
    }
    cout<<endl;
}

void Allocate::allocate(int size){
    for(int i=0;i<n;i++){
        if(mem[i].isFree && mem[i].length>=size){
            cout<<"Memory allocated successfully at partition "<<i+1<<endl;
            mem[i].isFree = false;
            if(mem[i].length>size){
                Partition newPart;
                newPart.startAddr = mem[i].startAddr+size;
                newPart.length = mem[i].length-size;
                newPart.isFree = true;

                // 将新分区插入到空闲分区后面
                for(int j=i+1;j<n;j++){
                    if(mem[j].isFree){
                        mem[j] = newPart;
                        break;
                    }
                }
            }
            return;
        }
    }
    cout<<"Memory allocation failed."<<endl;
}

void Allocate::freeMem(int startAddr){
    for(int i=0;i<n;i++){
        if(mem[i].startAddr==startAddr && !mem[i].isFree){
            mem[i].isFree = true;

            // 合并相邻的空闲分区
            if(i>0 && mem[i-1].isFree){
                mem[i-1].length += mem[i].length;
                for(int j=i+1;j<n;j++) mem[j-1] = mem[j];
                n--;
                i--;
            }
            if(i<n-1 && mem[i+1].isFree){
                mem[i].length += mem[i+1].length;
                for(int j=i+2;j<n;j++) mem[j-1] = mem[j];
                n--;
            }
            cout<<"Memory freed successfully."<<endl;
            return;
        }
    }
    cout<<"Failed to free memory."<<endl;
}

int main(){
    int sizes[] = {100, 50, 200};  // 定义内存分区大小
    int n = sizeof(sizes)/sizeof(int);
    Allocate alloc(sizes, n);

    alloc.showMemory();

    alloc.allocate(60);
    alloc.showMemory();

    alloc.allocate(70);
    alloc.showMemory();

    alloc.freeMem(0);
    alloc.showMemory();

    alloc.freeMem(150);
    alloc.showMemory();

    return 0;
}

以上代码实现了动态分区分配算法中的首次适应算法，可以通过`Allocate`类的`allocate`方法分配内存，通过`freeMem`方法释放内存，通过`showMemory`方法展示内存布局。