实验（三）模拟存储器分配算法_分别实现采用首次适应算法和最佳适应算法的动态分区分配过程 alloc()和回收过

一、实验名称

实验（三）模拟存储器分配算法

二、实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

三、实验内容和要求

用高级语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
作业1申请130KB。
作业2申请60KB。
作业3申请100KB。
作业2释放60KB。
作业4申请200KB。
作业3释放100KB。
作业1释放130KB。
作业5申请140KB。
作业6申请60KB。
作业7申请50KB。
作业6释放60KB。
请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。

四、实验设计

1、实验内容

(1)实验原理：

①可变分区方式是按作业需要的主存空间大小来分割分区的。
当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。
②首次适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
③最佳适应算法分配主存空间。
与首次适应法不同，最佳适应法是先查看完各个空闲区的大小，找到比作业大小大且最小的空闲分区来分配。
④当一个作业执行结束撤离时，作业所占的区域应该归还。
归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。

(2)思路分析：

将内存封装成对象，并且只使用一次，它的属性有总内存大小640K，需要给它分块，有块数，块的大小，每块的起始地址（将地址分为0~640），每块的状态（已分配或未分配），主要程序的生命周期都依赖它；将作业也封装Homework，根据题目要求创建多个对象，它的属性有大小，有标记申请和释放的属性。

(3)实验环境：jdk1.8

(4)程序代码：

package com.symc.dsaa.os.test3;

public class MemoryTest {
    public static void main(String[] args) {

        MemoryManagement memoryManagement = new MemoryManagement();

        //创建作业
        HomeWork[] homeWorks = new HomeWork[11];
        homeWorks[0] = new HomeWork(1, 130, "申请");
        homeWorks[1] = new HomeWork(2, 60, "申请");
        homeWorks[2] = new HomeWork(3, 100, "申请");
        homeWorks[3] = new HomeWork(2, 60, "释放");
        homeWorks[4] = new HomeWork(4, 200, "申请");
        homeWorks[5] = new HomeWork(3, 100, "释放");
        homeWorks[6] = new HomeWork(1, 130, "释放");
        homeWorks[7] = new HomeWork(5, 140, "申请");
        homeWorks[8] = new HomeWork(6, 60, "申请");
        homeWorks[9] = new HomeWork(7, 50, "申请");
        homeWorks[10] = new HomeWork(6, 60, "释放");

        System.out.println("初始空闲说明表");
        memoryManagement.displayFreeArea();

        //执行作业
        for (HomeWork h : homeWorks) {
            System.out.println();
            System.out.println("执行作业" + h.id + "任务：" + h.doing + h.need + "k");
            try {
                memoryManagement.implementWork(h);
            } catch (HomeWorkNotFindException | MemoryFullException e) {
                e.printStackTrace();
            }
        }
    }
}
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
36

package com.symc.dsaa.os.test3;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

//因为要释放作业时 这个作业必须已经是申请过的不然会抛出一个异常
class HomeWorkNotFindException extends Exception {
    public HomeWorkNotFindException(String message) {
        super(message);
    }
}

//还需要一个异常表示 内存放不下
class MemoryFullException extends Exception {
    public MemoryFullException(String message) {
        super(message);
    }
}

//作业类 有一个id和要申请或者的内存大小 和要执行什么操作
class HomeWork {
    public int id;
    public int need;
    public String doing;

    public HomeWork(int id, int need, String doing) {
        this.id = id;
        this.need = need;
        this.doing = doing;
    }
}

//区域类 表示内存的起始地址和大小和状态
class Area {

    public int homeWorkId;
    public int indexBig;
    public int areaSize;
    public boolean state;

    public Area(int homeWorkId, int indexBig, int areaSize, boolean state) {
        this.homeWorkId = homeWorkId;
        this.indexBig = indexBig;
        this.areaSize = areaSize;
        this.state = state;//true表示未分配 false表示已分配
    }

    @Override
    public String toString() {
        return indexBig + "k" + "  " + areaSize + "k" + "  " + (state ? "未分配" : "已分配");
    }
}

//主存储器空间的分配和回收的一个类
//需要一个链表去记录所有已分配和未分配区域
//需要一个加作业的方法
//需要一个释放作业的方法
//需要一个打印空闲区域的一个链表
public class MemoryManagement {

    private List<Area> list = new LinkedList<>();

    public MemoryManagement() {
        list.add(new Area(0, 0, 640, true));
    }

    //只需要把作业传进来 在这个类里会判断是要申请空间还是释放空间
    public void implementWork(HomeWork homeWork) throws HomeWorkNotFindException, MemoryFullException {

        if ("申请".equals(homeWork.doing)) {
            apply(homeWork);
            displayFreeArea();
        } else {
            if ("释放".equals(homeWork.doing)) {
                free(homeWork);
                displayFreeArea();
            }
        }
    }

    private void free(HomeWork homeWork) throws HomeWorkNotFindException {
        for (Area a : this.list
        ) {
            if (a.homeWorkId == homeWork.id) {
                a.state = true;
                for (int index = list.indexOf(a) - 1; index >= 0 && list.get(index).state; index--) {
                    Area area = list.get(index);
                    area.areaSize += a.areaSize;
                    list.remove(a);
                    a = area;
                }

                for (int index = list.indexOf(a) + 1; index < list.size() && list.get(index).state; index++) {
                    Area area = list.get(index);
                    a.areaSize += area.areaSize;
                    list.remove(area);
                }
                return;
            }
        }
        //抛出一个异常
        throw new HomeWorkNotFindException("未找到要释放的内存区域");
    }

    private void apply(HomeWork homeWork) throws MemoryFullException {
        //申请的时候遍历区域链表找到未分配的并且可以放的下作业的区域  如果没找到就放在最后面
        //但是此时肯可能会把未分配的一个区域变成俩个区域 一个表示已分配 一个表示未分配
        //最后要记得排序区域链表
        //区域状态true表示未分配 false表示已分配
        for (Area a : this.list)
        {
            if (a.state && a.areaSize >= homeWork.need) {
                //找到那个我们需要的区域
                if (a.areaSize == homeWork.need) {
                    //空闲区域和需要的区域大小相等
                    a.homeWorkId = homeWork.id;
                    a.state = false;
                } else {
                    Area areaTrue = new Area(homeWork.id, a.indexBig, homeWork.need, false);
                    Area areaFalse = new Area(homeWork.id, a.indexBig + homeWork.need, a.areaSize - homeWork.need, true);
                    list.remove(a);
                    list.add(areaTrue);
                    list.add(areaFalse);
                }

                this.list.sort(new Comparator<Area>() {
                    @Override
                    public int compare(Area o1, Area o2) {
                        return o1.indexBig - o2.indexBig;
                    }
                });

                return;
            }
        }

        //如果最后一个空闲区域内存还是不够大
        throw new MemoryFullException("内存放不下");
    }

    //打印空闲区域
    public void displayFreeArea() {
        System.out.println("======================");
        System.out.println("起址" + "  " + "长度" + "  " + "状态");
        for (Area a : this.list) {
        	System.out.println(a.toString());
        }
        System.out.println("======================");
    }
}

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

2、实验结果

五、实验中出现的问题及解决方法

问题1：分配空间算法的实现
对于首次适应算法的分配，需要使作业插入首个能容下的空闲区间，还会产生一个剩余空间（当这个空间足够小，就是碎片），也就是说，原本的一个大的空闲的空间，由于插入作业，变成了两个空间，一个空间已经分配，其大小与作业大小一致，另一个空间就是剩余空间，并且属于未分配的空间。算法中task表示传入的进程，blockNum表示当前内存的空间块数，blockSize是一个ArrayList集合，存放的是各个空间块的大小。我们从头开始遍历空间块的大小，如果它的状态是已分配的，那肯定得跳过；当遇到一个未分配的空间，判断是否能容纳这个作业，如果不能，肯定也要继续往下找；如果空间够用，那就把当前空间取出，给集合blockSize的i的位置重新插入一个已分配作业的块，还需要在i+1 的位置插入一个剩余空间的块，这样就需要blockSize中i+1后面的对象依次往后挪一位。这样就实现了分配的效果了，既然已经分配完了，此循环就不必再执行下去，直接return！

public void alloc(Task task) {
    for (int i = 0; i < blockNum; i++) {
        if (!"未分配".equals(blockStatus.get(i))){
            continue;
        }
        if (blockSize.get(i) >= task.getSize()) {
            int temp = blockSize.get(i);
            blockSize.remove(i);
            blockSize.add(i, task.getSize());
            for (int j = blockNum; j > i + 1; j--) {
                blockSize.add(j, blockSize.get(j - 1));
                blockSize.remove(j - 1);
            }
            blockSize.add(i + 1, temp - task.getSize());
            blockNum++;
            return;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

七、结论

1、采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么不同的影响？

首次适应算法对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区；该算法每次都是从低地址找起，导致其低地址留下了许多无法使用的外部碎片，降低了后续查找的效率。
最佳适应算法选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰；从空间利用率来看，NF算法确实是物尽其用，但是每次分割留下的都是难以利用的外部碎片，又降低了查找效率

2、如何解决因碎片而造成内存分配速度降低的问题？

想到的是动态分配内存，在alloc()和free()中添加对应的代码。