乐趣区

关于操作系统:Java实现操作系统中四种动态内存分配算法BFNFWFFF

jiezi

1 概述

本文是利用 Java 实现操作系统中的四种动态内存调配形式，别离是：

  • BF
  • NF
  • WF
  • FF

分两局部，第一局部是介绍四种调配形式的概念以及例子，第二局部是代码实现以及解说。

2 四种调配形式

2.1 概念

操作系统中有一个动静分区调配的概念，内存在初始化的时候不会划分区域，而是在过程装入的时候，依据所要装入的过程动静地对内存空间进行划分，以进步内存空间的利用率，升高碎片的大小，次要的办法有一下四种：

  • 首次适应算法（First Fit）：从闲暇分区链首开始查找，直到找到一个满足其大小要求的闲暇分区为止
  • 循环首次适应算法（Next Fit）：从上次找到的闲暇分区的下一个开始查找
  • 最佳适应算法（Best Fit）：把闲暇分区按大小递增的形式造成分区链，找到第一个能满足要求的闲暇分区就进行调配
  • 最坏适应算法（Worst Fit）：与最佳适应算法相同，把闲暇分区按大小递加的形式造成分区链，找到第一个能满足要求的闲暇分区就进行调配

2.2 例子

假如当初有 100MB 的内存空间，某一时刻先后调配了 20MB、4MB、10MB 内存，示意图如下：

当初须要再调配 5MB 内存。

若采纳 FF，因为FF 是间接按程序分配内存，从低地址开始搜寻闲暇分区，因而便会从第一块闲暇分区调配5MB（地址0-5），示意图：

若采纳 NF，NF 与FF相似，只不过 NF 是从上一次找到的闲暇分区的下一块开始查找，因为上一次调配的是10MB，因而会从最初一块闲暇分区（地址80-100）分配内存：

若采纳 BF，BF 是遍历所有闲暇分区并找到一个能满足要求的最小分区，也就会找到一个比 5MB 大的闲暇分区，且该闲暇分区是所有闲暇分区中最小的，也就是地址为 64-70 的闲暇分区：

若采纳 WF，WF 与BF相同，总是从最大的闲暇分区开始调配，因而会从地址为 30-60 的闲暇分区进行调配：

3 代码实现

3.1 总览

代码分成了四个类：

  • Main：测试
  • Print：输入打印
  • Table：示意每一个分区
  • TableList：对分区进行管制，包含初始化，调配，回收等

3.2 Main

Main是测试类，代码如下：

public class Main {private final static TableList list = new TableList(64);

    public static void main(String[] args) {list.useWF();
//        list.useBF();
//        list.useNF();
//        list.useFF();

        list.allocate(10);
        list.allocate(20);
        list.free(10);
        list.show();
        list.allocate(8);
        list.show();
        list.allocate(13);
        list.allocate(1);
        list.show();
        list.free(1);
        list.allocate(9);
        list.free(13);
        list.show();
        list.allocate(18);
        list.show();
        list.allocate(3);
        list.allocate(4);
        list.free(20);
        list.free(8);
        list.show();
        list.allocate(8);
        list.free(9);
        list.show();
        list.clear();
        list.show();}
}

通过 TableList 对内存进行调配以及开释，初始化调配 64MB 大小内存，切换调配算法时应用前四行的其中一行即可。

3.3 Table

Table类示意每一个分区，无论是闲暇的还是已调配的，成员变量有四个，别离是：

  • 起始地址
  • 大小
  • 是否闲暇（只有两种状态，闲暇或调配）
  • 是否是上一次调配（NF专用）

代码如下：

@AllArgsConstructor
public class Table {
    @Getter
    @Setter
    private int address;
    @Setter
    @Getter
    private int size;
    private boolean free;
    @Getter
    @Setter
    private boolean lastAllocated;

    public static Table freeTable(int address,int size)
    {return new Table(address,size,true,false);
    }

    public static Table allocatedTable(int address,int size)
    {return new Table(address,size,false,false);
    }

    public boolean isFree()
    {return free;}

    public boolean isAllocated()
    {return !isFree();
    }

    public void setFree()
    {free = true;}
}

只有一些 Getter 和Setter，为了不便提供了一个创立闲暇分区或已调配分区的静态方法，指定起始地址和大小即可。

3.4 TableList

TableList是整个算法的外围类，成员变量如下：

private final List<Table> list = new ArrayList<>();
private final int totalSize;
private boolean ff = false;
private boolean nf = false;
private boolean bf = false;
private boolean wf = false;
private boolean first = true;
private final static Print print = new Print();

list就是所有的闲暇分区与已调配分区组成的数组，totalSize是总大小，接着是四个控制算法的布尔变量，first示意是否是第一次分配内存，因为第一次的话四种算法都是固定的从地址为 0 处开始调配。

接下来就是内存调配算法以及开释算法。

3.4.1 FF

if (ff)
{for (int i = 0; i < list.size(); i++) {Table table = list.get(i);
        if(table.isFree() && table.getSize() >= size)
        {int address = table.getAddress();
            Table allocated = Table.allocatedTable(address,size);
            table.setAddress(address+size);
            table.setSize(table.getSize()-size);
            list.add(i,allocated);
            return;
        }
    }
}

FF的实现还是比较简单的，间接遍历列表，如果是闲暇分区并满足大小要求，间接进行调配，批改闲暇分区的起始地址和大小并插入一个新的已调配分区到列表中即可。

3.4.2 NF

else if (nf)
{int lastNFIndex = findLastAllocated();
    int i = lastNFIndex;
    do
    {if(i == list.size())
            i = 0;
        Table table = list.get(i);
        if(table.isFree() && table.getSize() >= size)
        {int address = table.getAddress();
            Table allocated = Table.allocatedTable(address,size);
            table.setAddress(address+size);
            table.setSize(table.getSize()-size);
            list.get(lastNFIndex).setLastAllocated(false);
            table.setLastAllocated(true);
            list.add(i,allocated);
            return;
        }
        ++i;
    }
    while (i != lastNFIndex);
}

NF的话须要提前记录上一次调配的地位，通过 Table 中的 lastAllocated 确定上一次调配的地位，找到后从该地位开始遍历列表，留神须要进行绕回解决，因为到开端地位后有可能还没有能满足的闲暇分区，此时须要将下标绕回到 0 并再次遍历直到达到上一次调配的地位。

3.4.3 BF+WF

因为 BF 与WF都须要遍历所有的闲暇分区，只是前者是抉择最小满足要求的，后者是抉择最大满足要求的，因而两者的实现差异在于一个判断大小的符号，代码如下：

else
{
    int i;
    int target = -1;
    for (i = 0; i < list.size(); i++) {Table table = list.get(i);
        if(table.isFree())
        {if(table.getSize() >= size)
            {if(target == -1)
                    target = i;
                else
                {if(bf)
                    {if(list.get(target).getSize() > table.getSize())
                            target = i;
                    }
                    else
                    {if(list.get(target).getSize() < table.getSize())
                            target = i;
                    }
                }
            }
        }
    }
    if(target != -1)
    {Table table = list.get(target);
        int address = table.getAddress();
        table.setAddress(address+size);
        table.setSize(table.getSize()-size);
        list.add(target,Table.allocatedTable(address,size));
        return;
    }
}

首先遍历找到符合条件的闲暇分区的下标，接着通过判断 target，也就是指标闲暇分区的下标，如果为-1 示意没有找到符合条件的闲暇分区，如果不为 -1 间接调配空间。

3.4.4 开释算法

开释算法的设计是比较复杂的，代码如下：

public void free(int size)
{
    int index = 0;
    while(index < list.size())
    {if(list.get(index).isAllocated() && list.get(index).getSize() == size)
            break;
        ++index;
    }
    if(index >= list.size())
    {print.freeFailed(size);
        return;
    }
    int address = list.get(index).getAddress();
    if(index == 0)
    {list.get(0).setFree();
        if(index+1 < list.size())
        {Table nextTable = list.get(index+1);
            if(nextTable.isFree())
            {list.get(0).setSize(nextTable.getSize()+size);
                list.remove(index+1);
            }
        }
    }
    else if(index == list.size()-1)
    {list.get(index).setFree();
        Table lastTable = list.get(index-1);
        if(lastTable.isFree())
        {lastTable.setSize(lastTable.getSize()+size);
            list.remove(index);
        }
    }
    else
    {Table before = list.get(index-1);
        Table after = list.get(index+1);

        if(before.isFree() && after.isFree())
        {before.setSize(before.getSize()+size+after.getSize());
            list.remove(index+1);
            list.remove(index);
        }
        else if(before.isFree() && after.isAllocated())
        {before.setSize(before.getSize()+size);
            list.remove(index);
        }
        else if(before.isAllocated() && after.isFree())
        {after.setSize(after.getSize()+size);
            after.setAddress(address);
            list.remove(index);
        }
        else
        {list.get(index).setFree();}
    }
}

次要思考了六种状况（黄色代表须要开释的空间，橙色是已调配的内存空间）：

  • 第一种状况就是须要开释首部的分区，此时须要批改前面闲暇分区的起始地址和大小，并删除指标分区
  • 第二种状况是开释尾部的分区，此时须要批改后面闲暇分区的大小即可，无需批改起始地址，并删除指标分区
  • 第三种状况是前面是已调配的分区，后面的闲暇分区，须要批改后面闲暇分区的大小，并删除指标分区
  • 第四种状况是后面是已调配的分区，前面是闲暇分区，须要批改前面的闲暇分区的起始地址以及大小，并删除指标分区
  • 第五种状况是前后都是已调配的分区，此时只须要批改指标分区的标记为闲暇即可，无需额定操作
  • 第六种状况是前后都是闲暇分区，这种状况下须要进行连贯操作，具体来说就是先批改后面闲暇分区的大小，接着删除指标分区以及前面的闲暇分区

上面回到代码，首先是判断第一种状况：

if(index == 0)
{list.get(0).setFree();
    if(index+1 < list.size())
    {Table nextTable = list.get(index+1);
        if(nextTable.isFree())
        {list.get(0).setSize(nextTable.getSize()+size);
            list.remove(index+1);
        }
    }
}

也就是须要开释首部的分区，通过 setFree() 设置标记位示意闲暇状态，接着判断是否须要批改前面闲暇分区的大小，因为有可能前面是一个已调配的分区而不是闲暇分区。

else if(index == list.size()-1)
{list.get(index).setFree();
    Table lastTable = list.get(index-1);
    if(lastTable.isFree())
    {lastTable.setSize(lastTable.getSize()+size);
        list.remove(index);
    }
}

这里是判断第二种状况，也就是开释尾部的分区，同样须要判断前一个分区是已调配的分区还是闲暇的分区，是闲暇分区的话批改大小并移除指标分区。

else
{Table before = list.get(index-1);
    Table after = list.get(index+1);

    if(before.isFree() && after.isFree())
    {before.setSize(before.getSize()+size+after.getSize());
        list.remove(index+1);
        list.remove(index);
    }
    else if(before.isFree() && after.isAllocated())
    {before.setSize(before.getSize()+size);
        list.remove(index);
    }
    else if(before.isAllocated() && after.isFree())
    {after.setSize(after.getSize()+size);
        after.setAddress(address);
        list.remove(index);
    }
    else
    {list.get(index).setFree();}
}

接下来是最初四种状况的判断，首先获取前一个以及后一个分区，接着按下面算法的思路进行判断即可。

4 测试

以 WF 为例，默认大小64MB，测试程序如下：

  • 调配10MB
  • 调配20MB
  • 开释10MB
  • 打印后果
  • 调配8MB
  • 打印后果
  • 调配13MB
  • 调配1MB
  • 打印后果
  • 开释1MB
  • 调配9MB
  • 开释13MB
  • 打印后果
  • 调配18MB
  • 打印后果
  • 调配3MB
  • 调配4MB
  • 开释20MB
  • 开释8MB
  • 打印后果
  • 调配8MB
  • 开释9MB
  • 打印后果
  • 清空
  • 打印后果

输入：

Free           :      0-10MB
Allocated      :      10-30MB
Free           :      30-64MB

----------------------------------------------------------------

Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-64MB

----------------------------------------------------------------

Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Allocated      :      38-51MB
Allocated      :      51-52MB
Free           :      52-64MB

----------------------------------------------------------------

Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-51MB
Allocated      :      51-60MB
Free           :      60-64MB

----------------------------------------------------------------

Do nothing.
Allocated failed, out of memory
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-51MB
Allocated      :      51-60MB
Free           :      60-64MB

----------------------------------------------------------------

Allocated      :      0-4MB
Free           :      4-38MB
Allocated      :      38-41MB
Free           :      41-51MB
Allocated      :      51-60MB
Free           :      60-64MB

----------------------------------------------------------------

Allocated      :      0-4MB
Allocated      :      4-12MB
Free           :      12-38MB
Allocated      :      38-41MB
Free           :      41-64MB

----------------------------------------------------------------

Free           :      0-64MB

----------------------------------------------------------------

读者能够自行画图验证。

5 源码

  • Github
  • 码云
  • CODE.CHINA

如果感觉文章难看，欢送点赞。
同时欢送关注微信公众号：氷泠之路。

退出移动版