内存分配实验

数据结构

本次实验一共定义了三个类

  1. MemoryAllocation — 主类，负责初始化，分配内存的工作，主类中存放了三个链表
    • 全部的内存空间链表
    • 处于等待中的作业链表
  2. MemorySeg — 内存块类，有4个属性
    • 起始位置
    • 块长度
    • 状态，0代表空闲，1代表占用
    • 分区编号
  3. Job — 作业类，有2个属性
    • 需要申请的内存
    • 状态，0代表等待中，1代表运行中，2代表结束

内存分配流程

  1. 首先需要根据内存分区初始化所有内存块

    一开始的时候就是有多少分区，就有多少块

    之后随着任务分配，块数会增加，分区数不会变

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public static void initMemory() {
        // 初始化内存空间
        System.out.println("初始化内存空间...");
        memory = new ArrayList<>();
        // 我们假设内存被拆分成 300KB, 600KB, 350KB, 200KB, 750KB和125KB这六段
        int start = 0;
        int[] sizes = { 300, 600, 350, 200, 750, 125 };
        MemorySeg ms;
        int no = 0;
        for (int size : sizes) {
            ms = new MemorySeg(no++, start, size, 0);
            memory.add(ms);
            start += size;
        }
        System.out.println("内存空间初始化完成!");
        System.out.println("-----------------------------------");
    }

  2. 初始化作业链表（写的比较无脑）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public static void initJobs() {
        // 初始化所有作业
        waitingJobs = new ArrayList<>();
        // 假设有5个作业
        Job job1 = new Job(115);
        Job job2 = new Job(500);
        Job job3 = new Job(358);
        Job job4 = new Job(200);
        Job job5 = new Job(375);
        waitingJobs.add(job1);
        waitingJobs.add(job2);
        waitingJobs.add(job3);
        waitingJobs.add(job4);
        waitingJobs.add(job5);
    }

  3. 定义给一个任务分配内存的方法

    • 首次适应算法
      • 遍历内存块，找到空闲且满足作业需求的第一个内存块，直接分配即可
      • 分配之后有两种情况
        • 当前内存块仍有空余内存，则我们需要把这个空闲的块分割出来
        • 当前内存块正好被分配完，则不需要进行分割
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    public static Boolean allocate(Job job) {
        int flag = 0; // 用来记录当前作业是否得到了内存
        // 假设现在采用的是首次适应算法
        for (int i = 0; i < memory.size(); i++) {
            // 遍历所有内存空间
            MemorySeg mSeg = memory.get(i);
            // 找到空闲且分区大小足够的内存块
            if (mSeg.status == 0 && mSeg.length >= job.memo) {
                memory.remove(i);
                // 新建一段被占用的内存空间
                MemorySeg occupied = new MemorySeg(mSeg.no, mSeg.start, job.memo, 1);
                memory.add(i, occupied);
                // 计算占用内存后的空闲分区
                int left = mSeg.length - job.memo;
                if (left > 0) {
                    // 如果剩余空闲分区内存大于0
                    MemorySeg notOccupied = new MemorySeg(mSeg.no, mSeg.start + job.memo, left, 0);
                    memory.add(i + 1, notOccupied);
                }
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            // 说明p没有申请到内存，需要加入等待队列
            waitingJobs.add(job);
            return false;
        } else {
            return true;
        }
    }
    • 最优适应算法
      • 遍历内存块，找到空闲，能满足作业内存需要且尽可能小的内存块
      • 分割过程同最先适应算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    public static Boolean allocate(Job job) {
        int flag = 0; // 用来记录当前作业是否得到了内存
        // 假设现在采用的是最优适应算法
        int best = -1;
        for (int i = 0; i < memory.size(); i++) {
            // 遍历所有内存空间
            MemorySeg mSeg = memory.get(i);
            // 找到空闲且分区大小足够且尽量小的内存块
            if (mSeg.status == 0 && mSeg.length >= job.memo) {
                if (best == -1) {
                    best = i;
                } else if (mSeg.length - job.memo < memory.get(best).length - job.memo) {
                    best = i;
                }
                flag = 1;
            }
        }
        if (flag == 1) {
            MemorySeg bestSeg = memory.get(best);
            memory.remove(best);
            // 新建一段被占用的内存空间
            MemorySeg occupied = new MemorySeg(bestSeg.no, bestSeg.start, job.memo, 1);
            memory.add(best, occupied);
            // 计算占用内存后的空闲分区
            int left = bestSeg.length - job.memo;
            if (left > 0) {
                // 如果剩余空闲分区内存大于0
                MemorySeg notOccupied = new MemorySeg(bestSeg.no, bestSeg.start + job.memo, left, 0);
                memory.add(best + 1, notOccupied);
            }
            return true;
        }else{
            return false;
        }
    }

  4. 给所有等待中的作业分配内存

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public static void malloc() {
        // 为所有等待中的作业分配内存
        for (int i = 0; i < allJobs.size(); i++) {
            Job job = allJobs.get(i);
            if (job.status > 0)
                continue;
            Boolean res = allocate(job);
            if (res) {
                job.status = 1;
            }
        }
    }

分区回收流程

当一个作业结束之后要考虑对分区的回收操作

首先要明确的是每次的回收是针对某个分区而言，即只有同一个分区中的空闲块可以合并，不同分区的空闲块是不能合并的

回收流程

  • 首先取出对应这块内存，将状态设置为0，标明它现在是空闲状态

  • 记录下这块回收的内存的分区号freeNo

  • 遍历所有内存块，每当找到两块连续的属于freeNo分区的块时，就需要尝试合并

    • 如果两块都是空闲状态，就把它们合并成一块

  • 遍历到结束即可实现对空闲分区的回收

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    public static void free(int index) {
        // 清空某一块内存并进行合并
        System.out.println("正在尝试回收第"+index+"块内存...");
        if (index >= memory.size()) {
            System.out.println("需要释放的内存块超过范围");
            return;
        }
        MemorySeg ms = memory.get(index);
        if (ms.status == 0) {
            System.out.println("内存为空，无需释放");
            return;
        }
        ms.status = 0; // 将内存块状态设为0，模拟已经清空了内存
        int no = ms.no;
        // 接下去进行合并
        int i = 0;
        while (i < memory.size() - 1) {
            MemorySeg ms1 = memory.get(i);
            MemorySeg ms2 = memory.get(i + 1);
            if (ms1.no != no || ms2.no != no || ms1.status == 1 || ms2.status == 1) {
                // 确保合并的两个内存块都和刚刚释放的内存块都处于一个分区内
                // 同时要确保两个内存块都是空闲的
                i++;
                continue;
            }
            MemorySeg msNew = new MemorySeg(no, ms1.start, ms1.length + ms2.length, 0);
            // 删除原来的两个内存块，替换为一个新的更大的内存块
            memory.remove(i);
            memory.remove(i);
            memory.add(i, msNew);
        }
        System.out.println("内存回收完毕");
        System.out.println("-----------------------------------");
    }

实验输入数据

给定6个内存分区：300KB, 600KB, 350KB, 200KB, 750KB, 125KB

给定5个作业：115KB, 500KB, 358KB, 200KB, 375KB

运行结果展示

分配内存

  • 首次适应算法
image-20201211114347872

  • 最佳适应算法

    image-20201211114303462

回收内存

  • 假设之前是用首次分配算法分配的内存空间，此时有11块内存，6个分区
    • 可以看到我尝试回收第1块内存的时候，由于第一块本身就是空闲的，所以提示无需回收。
    • 当我尝试回收第2块内存时，将第2块状态设为0之后，我发现第2块和第3块都属于第1个分区，所以合并两个内存块，重新变成一块连续的600KB大小的内存。
image-20201211192918333

总结与感想

很有意思的一次实验。算法本身很好理解，首次适应和最佳适应都是字面意思。写代码的时候更多的是对数据结构的设计和对算法更深入的思考。“如何实现我脑子里的过程”，要解决这个问题着实不简单。

参考了网上的教程和实验报告的要求之后，初步设计成了这个样子，也算是简单实现了实验要求。但是设计本身实际上还有很多不足，比如，我没有尝试去实现命令窗口或者GUI的交互操作，而是直接把我的模拟操作写在了main函数里。另一方面，在内存回收的时候，更加真实的实现方式应该是通过某个任务的完成导致的释放它本身占用的内存，但是我只实现了指定内存块号进行释放并回收。整体实验的重心还是偏重于实现算法，对模拟的实现程度较低。