操作系统实验三 动态分区(First Fit、Next Fit、Best Fit、Worst Fit )

实验三 动态分区算法

前言

• 参考教材《操作系统 第四版》汤小丹

• 首次适应算法(First Fit)。空闲分区以地址递增的次序连接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区

• 邻近适应算法(Next Fit)。又称循环首次适应算法，由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找

• 最佳适应算法(Best Fit)。空闲分区按容量递增的方式形成分区链，找到第一个满足要求的空闲分区

• 最坏适应算法(Worst Fit)。又称最大适应算法，空闲分区以容量递减的次序链接，找到第一个能满足要求的空闲分区，即挑选出最大的分区

• 实验三Memory类中建了很多内部内和方法，分开展示代码部分只是为了方便学习每段代码的具体逻辑。运行代码直接C2C完整代码即可，以防某个函数或类放错位置

实验目的

通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法的实现方法

实验内容

设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。分别利用四种动态分区分配算法将m个进程放入空闲分区，给出进程在空闲分区中的分配情况

实验步骤

内存分配菜单

// 内存分配菜单
public void allocation(int size) {
    System.out.println("1.首次适应算法 2.循环首次适应算法 3.最佳适应算法 4.最坏适应算法");
    System.out.print("请选择分配算法:");
    Scanner in = new Scanner(System.in);
    int choice = in.nextInt();
    switch (choice) {
        case 1:
            FF(size);
            break;
        case 2:
            NF(size);
            break;
        case 3:
            BF(size);
            break;
        case 4:
            WF(size);
            break;
        default:
            System.out.println("请重新选择!");
    }
}

首次适应算法

// 首次适应算法
private void FF(int size) {
    // 遍历分区链表
    for (pointer = 0; pointer < zones.size(); pointer++) {
        Zone tmp = zones.get(pointer);
        // 找到可用分区（空闲且大小足够）
        if (tmp.isFree && (tmp.size > size)) {
            doAllocation(size, pointer, tmp);
            return;
        }
    }
    // 遍历结束后未找到可用分区, 则内存分配失败
    System.out.println("无可用内存空间!");
}

循环首次适应算法

// 循环首次适应算法
private void NF(int size) {
    Zone tmp = zones.get(pointer);
    if (tmp.isFree && (tmp.size > size)) {
        doAllocation(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)) {
            doAllocation(size, i, tmp);
            return;
        }
    }
    // 全遍历后如果未分配则失败
    System.out.println("无可用内存空间!");
}

最佳适应算法

// 最佳适应算法
private void BF(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 {
        doAllocation(size, flag, zones.get(flag));
    }
}

最坏适应算法

// 最坏适应算法
private void WF(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 {
        doAllocation(size, flag, zones.get(flag));
    }
}

内存分配

// 开始分配
private void doAllocation(int size, int location, Zone tmp) {
    // 要是剩的比最小分区MIN_SIZE小，则把剩下那点给前一个进程
    if (tmp.size - size <= MIN_SIZE) {
        tmp.isFree = false;
    } else {
        Zone split = new Zone(tmp.head + size, tmp.size - size);
        zones.add(location + 1, split);
        tmp.size = size;
        tmp.isFree = false;
    }
    System.out.println("成功分配 " + size + "KB 内存!");
}

内存回收

// 内存回收
public void collection(int 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 < zones.size() - 1 && zones.get(id + 1).isFree) {
        Zone next = zones.get(id + 1);
        tmp.size += next.size;
        zones.remove(next);
    }
    // 回收的分区要是前一个是空闲就和前分区合并
    if (id > 0 && zones.get(id - 1).isFree) {
        Zone previous = zones.get(id - 1);
        previous.size += tmp.size;
        zones.remove(id);
        id--;
    }
    zones.get(id).isFree = true;
    System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
}

展示分区

// 展示分区状况
public void showZones() {
	System.out.println("分区编号\t    分区始址\t     分区大小\t 空闲状态\t");
	for (int i = 0; i < zones.size(); i++) {
		Zone tmp = zones.get(i);
		System.out.println(i + "\t\t" + tmp.head + "\t\t" + tmp.size + "  \t" + tmp.isFree);
	}
}

主函数

public class 动态分区算法 {
    public static void main(String[] args) {
        Memory my = new Memory();// 新建一个内存对象
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("请输入要分配内存还是要释放内存");
            System.out.println("1.分配内存 2.释放内存 3.展示分区状况");
            int n = sc.nextInt();
            switch (n) {
                case 1: {
                    System.out.println("请输入要分配的内存大小");
                    int size = sc.nextInt();
                    my.allocation(size);// 调用对象Memory中内存分配函数allocation
                    my.showZones();// 展示分区状况
                    break;
                }
                case 2: {
                    System.out.println("输入想要释放内存的分区号");
                    int id = sc.nextInt();
                    my.collection(id);// 调用对象Memory中内存释放函数collection
                    break;
                }
                case 3: {
                    my.showZones();// 展示分区状况
                    break;
                }
                default:
                    System.out.println("输的不对");
            }
        }
    }
}

完整代码

package 操作系统实验;

import java.util.Arrays;
import java.util.Scanner;
import java.util.LinkedList;

/*
 * 动态分区算法 FF NF BF WF
 * @author CSDN 张时贰
 * @data 2021年12月9日
 */
public class 动态分区算法 {
    public static void main(String[] args) {
        Memory my = new Memory();// 新建一个内存对象
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("请输入要分配内存还是要释放内存");
            System.out.println("1.分配内存 2.释放内存 3.展示分区状况");
            int n = sc.nextInt();
            switch (n) {
                case 1: {
                    System.out.println("请输入要分配的内存大小");
                    int size = sc.nextInt();
                    my.allocation(size);// 调用对象Memory中内存分配函数allocation
                    my.showZones();// 展示分区状况
                    break;
                }
                case 2: {
                    System.out.println("输入想要释放内存的分区号");
                    int id = sc.nextInt();
                    my.collection(id);// 调用对象Memory中内存释放函数collection
                    break;
                }
                case 3: {
                    my.showZones();// 展示分区状况
                    break;
                }
                default:
                    System.out.println("输的不对");
            }
        }
    }
}

//新建一个内存类
class Memory {
    private int size;// 内存大小
    private static final int MIN_SIZE = 2;// 最小剩余分区大小
    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;
        }
    }

    // 默认内存大小512K
    public Memory() {
        this.size = 512;
        this.pointer = 0;// 默认首次运行程序，上次分配的空闲区位置为0
        this.zones = new LinkedList<>();
        zones.add(new Zone(0, size));
    }

    public Memory(int size) {
        this.size = size;
        this.pointer = 0;
        this.zones = new LinkedList<>();
        zones.add(new Zone(0, size));
    }

    // 内存分配菜单
    public void allocation(int size) {
        System.out.println("1.首次适应算法 2.循环首次适应算法 3.最佳适应算法 4.最坏适应算法");
        System.out.print("请选择分配算法:");
        Scanner in = new Scanner(System.in);
        int choice = in.nextInt();
        switch (choice) {
            case 1:
                FF(size);
                break;
            case 2:
                NF(size);
                break;
            case 3:
                BF(size);
                break;
            case 4:
                WF(size);
                break;
            default:
                System.out.println("请重新选择!");
        }
    }

    // 首次适应算法
    private void FF(int size) {
        // 遍历分区链表
        for (pointer = 0; pointer < zones.size(); pointer++) {
            Zone tmp = zones.get(pointer);
            // 找到可用分区（空闲且大小足够）
            if (tmp.isFree && (tmp.size > size)) {
                doAllocation(size, pointer, tmp);
                return;
            }
        }
        // 遍历结束后未找到可用分区, 则内存分配失败
        System.out.println("无可用内存空间!");
    }

    // 循环首次适应算法
    private void NF(int size) {
        Zone tmp = zones.get(pointer);
        if (tmp.isFree && (tmp.size > size)) {
            doAllocation(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)) {
                doAllocation(size, i, tmp);
                return;
            }
        }
        // 全遍历后如果未分配则失败
        System.out.println("无可用内存空间!");
    }

    // 最佳适应算法
    private void BF(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 {
            doAllocation(size, flag, zones.get(flag));
        }
    }

    // 最坏适应算法
    private void WF(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 {
            doAllocation(size, flag, zones.get(flag));
        }
    }

    // 开始分配
    private void doAllocation(int size, int location, Zone tmp) {
        // 要是剩的比最小分区MIN_SIZE小，则把剩下那点给前一个进程
        if (tmp.size - size <= MIN_SIZE) {
            tmp.isFree = false;
        } else {
            Zone split = new Zone(tmp.head + size, tmp.size - size);
            zones.add(location + 1, split);
            tmp.size = size;
            tmp.isFree = false;
        }
        System.out.println("成功分配 " + size + "KB 内存!");
    }

    // 内存回收
    public void collection(int 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 < zones.size() - 1 && zones.get(id + 1).isFree) {
            Zone next = zones.get(id + 1);
            tmp.size += next.size;
            zones.remove(next);
        }
        // 回收的分区要是前一个是空闲就和前分区合并
        if (id > 0 && zones.get(id - 1).isFree) {
            Zone previous = zones.get(id - 1);
            previous.size += tmp.size;
            zones.remove(id);
            id--;
        }
        zones.get(id).isFree = true;
        System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
    }

    // 展示分区状况
    public void showZones() {

        System.out.println("分区编号\t    分区始址\t     分区大小\t 空闲状态\t");
        for (int i = 0; i < zones.size(); i++) {
            Zone tmp = zones.get(i);
            System.out.println(i + "\t\t" + tmp.head + "\t\t" + tmp.size + "  \t" + tmp.isFree);
        }

    }
}

运行结果

首先分配一些内存(手动先输好)，然后展示四个算法的运行结果。如图

使用首次适应算法，申请内存大小10kb，遍历空闲分区找到第二个分区为空，所以插入分区2，剩下40kb作为分区3

使用循环首次适应算法，申请内存大小10kb，上一次运行位置在2号分区，所以从2号分区开始寻找，3号分区为空，将10kb放入三号分区，剩下30kb作为分区4

使用最佳适应算法算法，申请内存大小3kb。首先从小到大遍历空闲分区，7号分区大小15kb，满足条件。将3kb插入7号分区，剩余10kb作为8号分区

使用最坏适应算法，申请内存大小2kb。首先从大到小遍历分区，14号分区最大，所以将2kb插入14号分区，剩余232kb作为15号分区

释放11号分区，将10、11、12号分区合并为10号分区

总结

首次适应算法，从链首开始，查找可以用的空闲区，保留了高地址部分的大空闲区，缺点，低地址部分不断被划分，留下许多小的、很难利用的空闲区

循环首次适应算法，不是每次都从首地址查找，而是从上次查找结束的地方开始找，使空闲区分布的更加均匀，减少查询的开销，缺乏大的空闲区

最佳适应算法，每次查找时，将刚刚好的、稍微大一点点的空闲区分给作业，避免了“大材小用”，但留下许多难以利用的小空闲区

最差适应算法，与“最佳”相反，每次都将最大的空闲区分配给作业，产生碎片的可能性小，对中小型作业有利

附一张《王道考研-操作系统》第37讲动态分区总结