动态内存分配主要有四种算法：
(1) 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
(2) 循环首次适应算法：首次适应算法每次要从头找，增加了查找的开销，也可能在低地
址上产生难以利用的小碎片。循环首次适应算法从上一次结束的位置开始查找。
(3) 最佳适应算法：为了保证当“大进程”到来时能有连续的大片空间，可以尽可能的多
留下大片空闲区，即，优先使用更小的空闲区。
(4) 最坏适应算法：为了解决最佳适应算法的问题——留下太多难以利用的小碎片。可以优先使用最大的连续空闲区。

各自的优缺点：
(1) 首次适应算法：综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序。
(2) 循环首次适应算法：不用每次都从低地址的小分区开始检索。算法开销小，但会使高地址的大分区也被用完。
(3) 最佳适应算法：会有更多的大分区被保留下来，更能满足大进程的需求。但会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序。
(4) 最坏适应算法：可以减少难以利用的小碎片。但大分区容易被利用完，不利于大进程，算法开销大。

这里我们说说代码的构造：
你要有一个分区块的类，用来保存分区块的起始地址，大小，和状态

class Zone{                      //分区结点信息类
        private int size;           //分区大小
        private int head;           //分区起始位置
        private boolean isFree;    //空闲状态

        public Zone(int head, int size) {
            this.head = head;
            this.size = size;
            this.isFree = true;
        }
    }

之外嵌套我们的主类：

private int size;                     //总内存大小
    private LinkedList<Zone> zones;   //保存内存分区
    private int pointer;             //上次分配的空闲区位置

代码逻辑图：
1、我们先初始化内存的大小
2、进入主界面

1. 输入作业
2. 回收内存
3. 显示分区

3、输入作业后，先输入大小，然后选择分配的算法

1. 首次适应算法
2. 循环首次算法
3. 最佳适应算法
4. 最坏适应算法

下面是源码阶段：

package Experiment;

import java.util.LinkedList;
import java.util.Scanner;
public class Test2{
    private int size;                 //内存大小
    private LinkedList<Zone> zones;   //内存分区
    private int pointer;             //上次分配的空闲区位置

    class Zone{                      //分区结点信息类
        private int size;           //分区大小
        private int head;           //分区起始位置
        private boolean isFree;    //空闲状态

        public Zone(int head, int size) {
            this.head = head;
            this.size = size;
            this.isFree = true;
        }
    }
    public Test2(){
        this.size = 400;
        this.pointer = 0;
        this.zones = new LinkedList<>();
        zones.add(new Zone(0, size));
    }
    public Test2(int size) {
        this.size = size;
        this.pointer = 0;
        this.zones = new LinkedList<>();
        zones.add(new Zone(0, size));
    }

    private void doAlloc(int size, int location, Zone tmp) {
        //size 作业大小 location 内存位置 tmp可用空闲区
        Zone newHome = new Zone(tmp.head + size, tmp.size - size);
        //产生一个新空闲区;
        zones.add(location + 1, newHome);//插入新节点
        tmp.size = size;
        tmp.isFree = false;
        System.out.println("成功分配 " + size + "KB 内存!");
    }
    public void FirstFit(int size){
        //将point赋值为零 从头开始找
        for (pointer = 0; pointer < zones.size(); pointer++){
            Zone tmp = zones.get(pointer);
            //找到可用分区（空闲且大小足够）
            if (tmp.isFree && (tmp.size > size)){
                doAlloc(size, pointer, tmp);
                return;
            }
        }
        //遍历结束后未找到可用分区, 则内存分配失败
        System.out.println("无可用内存空间!");
    }
    public void NextFit(int size){
        //直接获得上次point位置，开始遍历分区链表
        Zone tmp = zones.get(pointer);
        if (tmp.isFree && (tmp.size > size)){
            doAlloc(size, pointer, tmp);
            return;//查看当前块是否符合要求
        }
        int len = zones.size();
        int i = (pointer + 1) % len; //循环的过程，
        for (; i != pointer; i = (i+1) % len){
            tmp = zones.get(i);
            //找到可用分区（空闲且大小足够）
            if (tmp.isFree && (tmp.size > size)){
                doAlloc(size, i, tmp);
                return;
            }
        }
        //遍历结束后未找到可用分区, 则内存分配失败
        System.out.println("无可用内存空间!");
    }
    public void BestFit(int size){
        //最佳适应算法
        int flag = -1;//记录位置
        int min = this.size;//初始化为内存长度，用来保存最小碎片大小;
        for (pointer = 0; pointer < zones.size(); pointer++){//从头开始遍历;
            Zone tmp = zones.get(pointer);
            if (tmp.isFree && (tmp.size > size)){//找到合适条件的内存区
                if (min > tmp.size - size){//如果产生的碎片小于上一个最小值，就重新标记最小值位置
                    min = tmp.size - size;
                    flag = pointer;//更新位置
                }
            }
        }
        if (flag == -1){//初始值，没找到
            System.out.println("无可用内存空间!");
        }else {
            doAlloc(size, flag, zones.get(flag));
        }
    }
    public void WorstFit(int size){//最坏适应算法
        int flag = -1;
        int max = 0;//类似于最佳算法
        for (pointer = 0; pointer < zones.size(); pointer++){
            Zone tmp = zones.get(pointer);
            if (tmp.isFree && (tmp.size > size)){
                if (max < tmp.size - size){
                    max = tmp.size - size;
                    flag = pointer;
                }
            }
        }
        if (flag == -1){
            System.out.println("无可用内存空间!");
        }else {
            doAlloc(size, flag, zones.get(flag));
        }
    }
    public void collection(int id){//id 指定要回收的分区号
        if (id >= zones.size()){
            System.out.println("无此分区编号!");
            return;
        }
        Zone tmp = zones.get(id);//找到分区块
        int size = tmp.size;//取出大小
        if (tmp.isFree) {//判断状态
            System.out.println("指定分区未被分配, 无需回收");
            return;
        }

        //检查前面是否空闲，是则合并
        if (id > 0 && zones.get(id - 1).isFree){
            Zone fronKuer = zones.get(id - 1);
            fronKuer.size += tmp.size;
            zones.remove(id);
            id--;
        }

        //检查后面是否空闲，是则合并
        if (id < zones.size() - 1 && zones.get(id + 1).isFree){
            Zone nextKuer = zones.get(id + 1);//取到下一个区块
            tmp.size += nextKuer.size;
            zones.remove(nextKuer);
        }
        zones.get(id).isFree = true;
        System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
    }
    public void showZones(){//展示内存分区状况
        System.out.println("***************************************");
        System.out.println("*分区编号 分区始址 分区大小 空闲状态  *");
        for (int i = 0; i < zones.size(); i++){
            Zone tmp = zones.get(i);
            System.out.println("*  "+i + "          "
                                   + tmp.head + "      "
                                   + tmp.size + "      "
                                   + tmp.isFree+"    *");
        }
        System.out.println("****************************************");
    }

}

这是我们算法的类，下面是调用的类

package Experiment;

import java.util.Scanner;

public class Main {
    public static Test2 user; //声明一个用户;
    public static void Init(){ //初始化内存大小
        System.out.println("请输入内存大小(如果输入0，则按默认400分配)");
        Scanner scanner=new Scanner(System.in);
        int choose=scanner.nextInt();
        if(choose==0){
            user=new Test2();
        }else {
            user=new Test2(choose);
        }
    }
    public static void mainMenu(){
        System.out.println("***********************");
        System.out.println("*     1.输入作业      *");
        System.out.println("*     2.回收内存块    *");
        System.out.println("*     3.展示分区情况  *");
        System.out.println("*     4.退出系统      *");
        System.out.println("***********************");
        System.out.println("请输入你要进行的操作:");
    }
    public static void algorithmMenu(int size){
        System.out.println("请选择分配算法:");
        System.out.println("1.首次适应算法");
        System.out.println("2.循环首次算法");
        System.out.println("3.最佳适应算法");
        System.out.println("4.最坏适应算法");
        Scanner in = new Scanner(System.in);
        int choose = in.nextInt();
        switch (choose){
            case 1:
                user.FirstFit(size);break;
            case 2:
                user.NextFit(size);break;
            case 3:
                user.BestFit(size);break;
            case 4:
                user.WorstFit(size);break;
            default:
                System.out.println("请重新选择!");
        }
    }
    public static void main(String[] args) {
        Init();     //初始化内存条大小
        Scanner sc=new Scanner(System.in);

        while(true){
            mainMenu();             //主菜单
            int choice=sc.nextInt();
            if(choice == 4){
               return;
            }else if(choice == 1){
               System.out.println("请输入你要插入的内存块大小");
               int length=sc.nextInt();
               algorithmMenu(length);
            }else if(choice==2){
                System.out.println("请输入你要回收的分区号码");
                int ID=sc.nextInt();
                user.collection(ID);
            }else if(choice == 3){
                user.showZones();
            }else{
               System.out.println("输入错误，请检查");
           }
        }
    }

}

注释写得很清楚，有什么不懂可以私信。

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
• 码云
• GitCode

成 绩：

***大学计算机学院
课 程 设 计

课 程 操作系统Ⅰ
题 目 存储器管理模拟
学 院 计算机学院
专 业 软件工程
班 级
姓 名
学 号
指导教师 ***

2019 年 6 月 16 日

目 录
1.设计目的与要求
1.1设计目的
1.2设计要求
2.设计思想及系统平台
2.1设计思想
2.2系统平台及使用语言
3.详细算法描述
4.源程序清单
5.运行结果与运行情况
6.总结

1.设计目的与要求

1.1设计目的

本设计的目的是使学生熟悉存储器管理系统的设计方法；加深对所学各种存储器管理方案的了解；要求采用一些常用的存储器分配算法，设计一个存储器管理模拟系统并调试运行。

1.2设计要求

用C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理；首次适应算法在进行内存分配时，系统优先使用空闲区低端的空间。回收时应注意相邻空闲分区的合并。

2.设计思想及系统平台

2.1设计思想

在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，选择适应算法（首次适应算法，最佳适应算法），实现分区存储管理的内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接。

2.2系统平台及使用语言

平台：Window10，codeblocks17.12
语言：c++

3.详细算法描述

在写这个内存的动态分区模拟算法时，我是用c++中的可变数组来模拟的。分别用一个可变数组表示空闲分区链，和已分配的内存分区链，在收到为进程分配内存请求时，在空闲链找看有没有符合条件的。首次适应算法是先分配低地址段的内存，所以在分配时，先对空闲分区链按首地址排序；最佳适应算法是为进程分配能可以满足的最小分区，所以在分配时，先对空闲分区链按分区的大小排序。相邻空闲分区合并，先按首地址排序，对整个空闲链遍历一遍，如果加上分区大小与后下一个地址相同，就合并。具体请看代码实现。

4.源程序清单

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

struct ready_node{//就绪的进程
    int id;//进程编号
    int flag;//表是进程的状态，1：表示进入内存，0：表示从内存撤出
    int size;//进程长度
};

struct free_node{//空闲区域表的结构体，首地址和长度
    int id;//保存在该区域的进行号
    int start;//首地址
    int len;//长度
    int state=0;//状态(0-空闲,1-已分配)
};
vector<free_node> free_list;//保存空闲区域表的内容，分别是区域首址和区域长度
vector<free_node> used_list;//保存已占用区域表的内容，分别是区域首址和区域长度
queue<ready_node> wait_list;//等待的进程队列
int flag;//选择的算法(1-首次适应算法 2-最佳适应算法)

//函数定义
int cmp1(free_node a,free_node b);//按开始地址从小到大排序
int cmp2(free_node a,free_node b);//按分区大小从小到大排序
void Show();//显示空闲区域表和已占用表的信息
void solve();//解决方案
void Alloc(ready_node node);//动态分区分配函数
void Free(ready_node node);//回收过程函数
void Oper_FIRO();//操作函数

int main()
{
    solve();
	return 0;
}

int cmp1(free_node a,free_node b){
    return a.start<b.start;//按开始地址从小到大排序
}

int cmp2(free_node a,free_node b){
    return a.len<b.len;//按分区大小从小到大排序
}

void Show(){//显示空闲区域表和已占用表的信息
    vector<free_node> qlist;
    for(int i=0;i<free_list.size();i++){
        qlist.push_back(free_list[i]);
    }
    for(int i=0;i<used_list.size();i++){
        qlist.push_back(used_list[i]);
    }
    sort(qlist.begin(),qlist.end(),cmp1);//操作之前首先按首地址从小到大排序

    printf("----------------------------------------------\n");
    printf("|               内存分区的情况:              |\n");
    printf("----------------------------------------------\n");
    printf("----------------------------------------------\n");

    for(int i=0; i<qlist.size(); i++){
        printf("| 分区号 | 首址 | 分区大小 |  状态  | 进程号 |\n");
        printf("|  %3d   | %3d  |  %3d     ",i+1,qlist[i].start,qlist[i].len);
        if(qlist[i].state==0)      printf("|  空闲  |  ----  |\n");
        else                       printf("| 已分配 | %3d    |\n",qlist[i].id);
        printf("----------------------------------------------\n");
    }

}


void solve(){
    free_node fnod;
    printf("请输入空闲分区初值(Kb):\n");
    cin>>fnod.len;
    fnod.start=0;//初始化空闲表
    free_list.push_back(fnod);
    printf("请输入实现算法：\n");
    printf(" 1-首次适应算法\n 2-最佳适应算法\n");
    cin>>flag;
    ready_node node;
    printf("请输入进程号,内存大小(Kb),执行的操作(1-申请,0-释放)\n");
    while(scanf("%d%d%d",&node.id,&node.size,&node.flag)){
        wait_list.push(node);
        Oper_FIRO();
        //cout<<node.size<<endl;
        printf("请输入进程号,内存大小(Kb),执行的操作(1-申请,0-释放)\n");
    }
}

void Alloc(ready_node node){//动态分区分配函数
    if(flag==1)//1-首次适应算法
        sort(free_list.begin(),free_list.end(),cmp1);
    else//2-最佳适应算法
        sort(free_list.begin(),free_list.end(),cmp2);
    //cout<<free_list.size()<<endl;
    free_node fnod;
    int ok=0;//表示是否匹配成功
    vector<free_node>::iterator it;//定义迭代器
    for(it=free_list.begin();it!=free_list.end();++it){
        //cout<<(*it).start<<endl;
        if(((*it).len) >= node.size){
            //记录已占用空间
            fnod.len=node.size;
            fnod.start=(*it).start;
            fnod.id=node.id;
            fnod.state=1;
            used_list.push_back(fnod);//放入已占用区域表

            (*it).start+=node.size;
            (*it).len-=node.size;//修改空闲区域表的信息
            if((*it).len==0){//剩余空闲长度为0，移除这个空闲区域
                free_list.erase(it);
            }
            ok=1;//已找到匹配
            break;
        }
    }
    if(ok==0){//证明当前进程没有匹配成功，则放入就绪队列
        //ready_list.push(node);
        printf("    | 对不起，内存分配失败！ |\n");
    }
    printf("进程%d申请进入内存,内存占用大小为%dkb：\n",node.id,node.size);
    Show();
}
void Free(ready_node node){//回收过程函数
    //释放内存的过程中，进程正常都会在内存中出现，这里就假设释放的进程全部合法
    free_node fnod;
    //node.state=0;
    vector<free_node>::iterator it;//定义迭代器
    for(it=used_list.begin();it!=used_list.end();++it){
        if(((*it).id) == node.id){//找到撤销进程
            //回收空闲空间，并放入空闲区域白哦，此时不用记录进程号，因为好没有进程占有空间
            fnod.start=(*it).start;
            fnod.len=node.size;
            fnod.state=0;
            free_list.push_back(fnod);//放入空闲区域表

            (*it).len-=node.size;//修改占用区域表的信息
            if((*it).len==0){//撤销内存后，剩余的占有空间为0，移除这个空闲区域
                used_list.erase(it);
            }
            break;
        }
    }
    sort(free_list.begin(),free_list.end(),cmp1);//操作之前首先按首地址从小到大排序)
    vector<free_node>::iterator its;//定义迭代器
    its=free_list.begin();
    its++;
    //相邻空闲区合并
    for(it=free_list.begin();it!=free_list.end();++it,++its){
        if(its!=free_list.end()){//如果与后面的空闲块
            int address=it->start+it->len;
            if(address==its->start){
                (it->len) += its->len;
                free_list.erase(its);
                its=it;
                it--;
            }
        }
    }
    printf("进程%d申请撤销,收回内存大小为%dkb：\n",node.id,node.size);
    Show();
}

void Oper_FIRO(){//操作函数
    ready_node node;

    while(!wait_list.empty()){//操作等待数列，有分配和回收两个过程
        node=wait_list.front();
        wait_list.pop();
        if(node.flag==1){//申请进入内存的进程
            Alloc(node);
        }
        else{//要撤出内存的进程
            Free(node);
        }
    }
}

5.运行结果与运行情况
分别用首次适应和最佳适应算法演示下列请求序列的完整截图：

初始内存空间640kb
作业1申请130kb
作业2申请60kb
作业3申请100kb
作业2释放60kb
作业4申请200kb
作业3释放100kb
作业1释放130kb
作业5申请140kb
作业6申请60kb
作业7申请50kb
作业6申请60kb

1-首次适应算法(从上往下，从左往右看)

2-最佳适应算法

6.总结

通过本次的课程设计，使我能够正确运用操作系统课程中所学的基本理论和知识，加深了对进程调度基本概念的理解。在设计过程中，阅读了教材和一些资料，不断的发现问题、提出问题、解决问题，加深自己对这些算法的理解，。在编程和调试的过程中，我们要自己设计用于存储的数据结构，和调试bug来模拟这个过程。通过这样的实验和学习，使我们的知识体系变的更加牢固