存储管理：动态分区存储管理

问题描述

基于空闲内存分区链表的存储管理，设计一个动态分区存储管理程序，支持包括首次适配法、下次适配法、最佳适配法和最坏适配法在内的不同分区分配算法。

实现要求

维护一个记录已分配内存分区和空闲内存分区的链表；
设计申请、释放函数循环处理用户的请求；
实现首次适配法、下次适配法、最佳适配法和最坏适配法四种分区分配算法；
可视化展示内存使用情况。

实验平台

Windows OS；C# 10（.NET 6）

实现思路

0.基础数据结构

为了方便编程，我使用 C# 中内置的 List<T> 数据结构模拟存储管理中链表的操作。List<T> 数据结构提供了添加元素的方法 Add、删除元素的方法 DeleteAt、以及数组访问运算符 []。尽管 List<T> 底层并不是用链表实现的，但是不影响用它来模拟链表的操作。这里可以将它视为一个单向链表，封装了增加、删除、访问等操作。

1.总体架构

建立内存管理对象 MemoryManager，维护其中的空闲内存块链表 BlankList 和分配内存块链表 AllocateList 。设置内存管理对象中有两个回调函数：分配函数 Allocate 和释放函数 Free。这两个函数作为参数传入内存管理对象的构造函数中，构成特定适配方法的内存管理对象。内存管理类的定义如下：

public class MemoryManager
{
    public List<MemoryBlock> BlankList { get; set; } = new();
    public List<MemoryBlock> AllocateList { get; set; } = new();
    public int MemorySize { get; init; }
    public int StartAddr { get; init; }
    private Fit fit;
    public bool Allocate(int memorySize) => fit.Allocate(memorySize, BlankList, AllocateList, out _);
    public bool Allocate(int memorySize, out MemoryBlock? retBlock) => fit.Allocate(memorySize, BlankList, AllocateList, out retBlock);
    public bool Free(int startAddr) => fit.Free(startAddr, BlankList, AllocateList, out _);
    public bool Free(int startAddr, out MemoryBlock? retBlock) => fit.Free(startAddr, BlankList, AllocateList, out retBlock);
    public MemoryManager(int memorySize, int startAddr, Fit fit)
    {
        MemorySize = memorySize;
        StartAddr = startAddr;
        this.fit = fit;  
        BlankList.Add(new MemoryBlock(memorySize, startAddr));
    }
}

2.首次适配法

首次适配法，按空闲分区的起始地址排序，从前往后依次查找，找到符合要求的第一个空闲分区，将其分配。

为了避免每次适配时都重新对空闲链表排序，因此在释放分配内存、将释放的内存块加入空闲分区时，应保证空闲分区链表仍然是按起始地址有序的。

同时，每次释放分配内存块并将其加入空闲分区链表时，都应对空闲链表重新检查，将能合并的空闲内存块合并。

首次适配法的分配与释放的代码如下：

public class FirstFit: Fit
{
    public override bool Allocate(int memorySize, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        for (int i = 0; i < blankList.Count; i++)
        {
            if (blankList[i].MemorySize >= memorySize)
            {
                var memoryBlock = new MemoryBlock(memorySize, blankList[i].StartAddr);
                allocateList.Add(memoryBlock);
                retBlock = memoryBlock;
                blankList[i].MemorySize -= memoryBlock.MemorySize;
                if (blankList[i].MemorySize == 0)
                {
                    blankList.RemoveAt(i);
                }
                else
                {
                    blankList[i].StartAddr += memoryBlock.MemorySize;
                }
                return true;
            }
        }
        retBlock = null;
        return false;
    }

    public override bool Free(int startAddr, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        retBlock = null;
        var freeIdx = allocateList.FindIndex(x => x.StartAddr == startAddr);
        if (freeIdx == -1)
            return false;
        var freeBlock = allocateList[freeIdx];
        retBlock = freeBlock;
        allocateList.RemoveAt(freeIdx);
        int index = blankList.FindIndex(item => item.StartAddr > freeBlock.StartAddr);
        if (index == -1)
            blankList.Insert(blankList.Count, freeBlock);
        else
            blankList.Insert(index, freeBlock);
        int i = 1;
        while (i < blankList.Count)
        {
            if (blankList[i - 1].StartAddr + blankList[i - 1].MemorySize == blankList[i].StartAddr)
            {
                blankList[i - 1].MemorySize += blankList[i].MemorySize;
                blankList.RemoveAt(i);
                continue;
            }
            i++;
        }
        return true;
    }
}

3.下次适配法

下次适配法，从上次分配的分区后开始查找，找到符合要求的第一个分区。如果查找到最后分区时，下次查找就从头开始。

具体实现上，下次适配法中在每次分配时，都需要记录上次分配的内存块在空闲链表中的位置 lastAllocIdx，并维护这个值。当有内存块从分配链表中释放时，根据要释放的内存块的起始地址大小，维护 lastAllocIdx。若释放内存的起始地址小于当前空闲链表第 lastAllocIdx 位置的内存块起始地址，则说明释放内存块加入链表后，会使 lastAllocIdx++。当释放内存块加入空闲链表后，还需要对空闲链表搜索，合并能合并的空闲块。当完全合并了 lastAllocIdx 之前了内存块时，需要将 lastAllocIdx--。

代码上整体与首次适配法相似，如下

public class NextFit: Fit
{
    private int lastAllocIdx = 0;

    public override bool Allocate(int memorySize, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        for (int j = 0; j < blankList.Count; j++)
        {
            int i = (j + lastAllocIdx) % blankList.Count;
            if (blankList[i].MemorySize >= memorySize)
            {
                var memoryBlock = new MemoryBlock(memorySize, blankList[i].StartAddr);
                allocateList.Add(memoryBlock);
                retBlock = memoryBlock;
                lastAllocIdx = i;
                blankList[i].MemorySize -= memoryBlock.MemorySize;
                if (blankList[i].MemorySize == 0)
                {
                    blankList.RemoveAt(i);
                }
                else
                {
                    blankList[i].StartAddr += memoryBlock.MemorySize;
                }
                return true;
            }
        }
        retBlock = null;
        return false;
    }

    public override bool Free(int startAddr, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        retBlock = null;
        var freeIdx = allocateList.FindIndex(x => x.StartAddr == startAddr);
        if (freeIdx == -1)
            return false;
        var freeBlock = allocateList[freeIdx];
        retBlock = freeBlock;
        allocateList.RemoveAt(freeIdx);
        int index = blankList.FindIndex(item => item.StartAddr > freeBlock.StartAddr);
        if (index == -1)
            blankList.Insert(blankList.Count, freeBlock);
        else
            blankList.Insert(index, freeBlock);
        if (index <= lastAllocIdx)  // record the last allcate index of blank list
            lastAllocIdx++;
        int i = 1;
        while (i < blankList.Count)
        {
            if (blankList[i - 1].StartAddr + blankList[i - 1].MemorySize == blankList[i].StartAddr)
            {
                blankList[i - 1].MemorySize += blankList[i].MemorySize;
                blankList.RemoveAt(i);
                if (i <= lastAllocIdx)  // lastAllocIdx-- when merging the blank blocks
                    lastAllocIdx--;
                continue;
            }
            i++;
        }
        return true;
    }
}

4.最佳适配法

每次分配时，找到其大小与要求相差最小的空闲分区进行分配。

由于这里需要按照内存大小进行查找，因此空闲分区链表可以按照空闲内存块大小进行排序。这样在查找时，只需找到第一个比要申请的内存大小大的内存块，就可以进行分配。

在释放内存时，由于空闲分区链表并不是按照内存块起始地址排序的，所以在合并时，要先将空闲分区链表按起始地址排序，这样方便合并相邻的空闲块。合并好后，再将空闲链表按内存块大小排序。

代码如下：

public class BestFit: Fit
{
    public override bool Allocate(int memorySize, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        retBlock = null;
        int idx = -1;
        for (int i = 0; i < blankList.Count; i++)
        {
            if (blankList[i].MemorySize >= memorySize)
            {
                idx = i;
                break;
            }
        }
        if (idx == -1)
            return false;

        var allocBlock = new MemoryBlock(memorySize, blankList[idx].StartAddr);
        allocateList.Add(allocBlock);
        retBlock = allocBlock;
        blankList[idx].MemorySize -= allocBlock.MemorySize;
        if (blankList[idx].MemorySize == 0)
        {
            blankList.RemoveAt(idx);
        }
        else
        {
            blankList[idx].StartAddr += allocBlock.MemorySize;
            blankList.Sort((x, y) => x.MemorySize.CompareTo(y.MemorySize));
        }
        return true;
    }

    public override bool Free(int startAddr, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        retBlock = null;
        var freeIdx = allocateList.FindIndex(x => x.StartAddr == startAddr);
        if (freeIdx == -1)
            return false;
        var freeBlock = allocateList[freeIdx];
        retBlock = freeBlock;
        allocateList.RemoveAt(freeIdx);
        blankList.Insert(blankList.Count, freeBlock);
        int i = 1;
        blankList.Sort((x, y) => x.StartAddr.CompareTo(y.StartAddr));
        while (i < blankList.Count)
        {
            if (blankList[i - 1].StartAddr + blankList[i - 1].MemorySize == blankList[i].StartAddr)
            {
                blankList[i - 1].MemorySize += blankList[i].MemorySize;
                blankList.RemoveAt(i);
                continue;
            }
            i++;
        }
        blankList.Sort((x, y) => x.MemorySize.CompareTo(y.MemorySize));
        return true;
    }
}

5.最坏适配法

每次分配时，找到最大的空闲分区进行分配。

最坏适配法的实现几乎与最佳适配法一样。只是在分配时，我们可以直接使用最大的空闲分区（即按内存块大小排序的空闲块链表的最后一个元素）进行分配。如果连最大的空闲分区都无法满足要求，则内存申请失败。

最坏适配法的内存释放函数与最佳适配法一模一样；内存申请函数有改动，如下：

public class WorstFit : Fit
{
    public override bool Allocate(int memorySize, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
    {
        retBlock = null;
        int idx = blankList.Count - 1;
        if (idx == -1 || blankList[idx].MemorySize < memorySize)
            return false;
        var allocBlock = new MemoryBlock(memorySize, blankList[idx].StartAddr);
        allocateList.Add(allocBlock);
        retBlock = allocBlock;
        blankList[idx].MemorySize -= allocBlock.MemorySize;
        if (blankList[idx].MemorySize == 0)
        {
            blankList.RemoveAt(idx);
        }
        else
        {
            blankList[idx].StartAddr += allocBlock.MemorySize;
            blankList.Sort((x, y) => x.MemorySize.CompareTo(y.MemorySize));
        }
        return true;
    }

    public override bool Free(int startAddr, List<MemoryBlock> blankList, List<MemoryBlock> allocateList, out MemoryBlock? retBlock)
}