实验三 可变分区内存分配首次适应算法模拟

实验内容

模拟内存分配，了解并掌握动态分区分配中所用的数据结构、分区分配算法，深刻理解首次适应内存分配算法。

• 模拟实现可变分区内存分配首次适应算法；
• 空闲分区表要求有空闲块的起始地址、大小、状态等信息；
• 设计一个功能函数，实现已分配块的回收及空闲块合并功能。

实现代码

这个原本的实验描述给的很模糊，也没有输入示例，只能从示例代码里猜一猜要实现什么效果。所以这里就按自己想法做了。

由于可变内存分区的数据用链表来存储比较合适，这里引入了一个链表类。

#include <iostream>
using namespace std;

class LinkedList {
public:
    struct LinkedNode {
        int memorySize;
        int usedMemorySize;
        int beginAddress;
        bool isUsed;
        LinkedNode* next;
        
        LinkedNode() : memorySize(0), beginAddress(0), usedMemorySize(0), isUsed(false), next(nullptr) {}
        explicit LinkedNode(int memorySize,int beginAddress) : memorySize(memorySize), beginAddress(beginAddress), usedMemorySize(0), isUsed(false), next(nullptr){}
    };

    LinkedList() {
        _dummyHead = new LinkedNode();
        _size = 0;
    }

    void insertAtTail(int memorySize,int beginAddress) {
        LinkedNode* newNode = new LinkedNode(memorySize, beginAddress);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    void AllocateAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        cur->isUsed=true;
    }

    //分配内存
    void allocateMemory(int requiredMemorySize) {
        LinkedNode* cur = _dummyHead;
        if(cur->next== nullptr){
            cout<<"无可分配内存!\n";
        }
        while(cur!= nullptr) {
            if(cur->memorySize>requiredMemorySize){
                cur->isUsed=true;
                cur->usedMemorySize=requiredMemorySize;
                cout<<"分配成功";
                return;
            } else {
                cur = cur->next;
            }
        }
        cout<<"无可分配内存!\n";
   }

   void revokeMemory(int index) {
       if (index >= _size || index < 0) {
           cout<<"不存在该内存块\n";
           return;
       }
       LinkedNode* cur = _dummyHead;
       while(index--) {
           cur = cur ->next;
       }
       cur->isUsed=false;
       cur->usedMemorySize=0;
    }

   //整理内存
   void reshuffleMemory() {
        LinkedNode* cur = _dummyHead;
        while (cur != nullptr && cur->next != nullptr) {
            //如果当前节点内存已经分配过，且下一个节点是空的，就把内存移到下一个空节点去
            if(cur->next->usedMemorySize==0) {
                int leftMemory = cur->memorySize - cur->usedMemorySize;
                cur->memorySize=cur->usedMemorySize;
                cur->next->memorySize+=leftMemory;
            }
            cur=cur->next;
        }
    }
    
    void printMemoryUse() {
        LinkedNode* cur = _dummyHead;
        int index=0;
        while (cur->next != nullptr) {
            cout << "内存块号: "<<index<<" 起始地址: "<<cur->next->beginAddress<<" 内存用量: " <<cur->next->usedMemorySize<<" 内存总量: " <<cur->next->memorySize<<" 分配状态: "  <<cur->next->isUsed<<endl;
            index++;
            cur = cur->next;
        }
        cout << endl;
    }

    void printFreeMemory() {
        LinkedNode* cur = _dummyHead;
        int index=0;
        while (cur->next != nullptr ) {
            if(cur->next->isUsed==false){
                cout << "内存块号: "<<index<<" 起始地址: "<< cur->next->beginAddress <<" 内存总量: " <<cur->next->memorySize << endl;
                index++;
            }
            cur = cur->next;
        }
        cout << endl;
    }

private:
    int _size;
    LinkedNode* _dummyHead;
};

int main() {
    LinkedList memoryList;
    while(true) {
        int operation;
        cout<<"输入操作, 1输入内存块数据, 2分配内存, 3回收内存, 4自动整理内存, 5查看全部内存分配情况, 6查看空闲内存分区, 7退出: ";
        cin>>operation;
        switch (operation) {
            case 1:
                cout<<"输入内存大小及内存起始地址: ";
                int memorySize,beginAddress;
                cin>>memorySize>>beginAddress;
                memoryList.insertAtTail(memorySize,beginAddress);
                break;
            case 2:
                int requiredMemorySize;
                cout<<"输入需求内存大小: ";
                cin>>requiredMemorySize;
                memoryList.allocateMemory(requiredMemorySize);
                break;
            case 3:
                int index;
                cout<<"输入要回收的内存块号: ";
                cin>>index;
                memoryList.revokeMemory(index);
                break;
            case 4:
                memoryList.reshuffleMemory();
                break;
            case 5:
                memoryList.printMemoryUse();
                break;
            case 6:
                memoryList.printFreeMemory();
                break;
            default:
                return 0;
        }
    }
}

运行结果