操作系统内存动态分区分配算法（Java实现）

操作系统内存动态分区分配算法主要有三种：首次适应算法（First Fit）、最佳适应算法（Best Fit）和最差适应算法（Worst Fit）。下面是它们的Java实现。

首次适应算法（First Fit）：

public class FirstFit {
    private int[] memory; // 内存空间
    private boolean[] status; // 内存状态，true表示已被占用，false表示未被占用

    public FirstFit(int size) {
        memory = new int[size];
        status = new boolean[size];
    }

    /**
     * 分配内存
     *
     * @param size 请求的内存大小
     * @return 分配的起始地址，若分配失败则返回-1
     */
    public int allocate(int size) {
        for (int i = 0; i < memory.length; i++) {
            if (!status[i]) { // 找到一个未被占用的内存块
                int j = i;
                int count = 0;
                while (j < memory.length && !status[j] && count < size) { // 查找连续的未被占用的内存块
                    count++;
                    j++;
                }
                if (count == size) { // 找到了满足要求的内存块
                    for (int k = i; k < j; k++) {
                        status[k] = true; // 将内存状态设置为已被占用
                    }
                    return i; // 返回分配的起始地址
                } else {
                    i = j - 1; // 继续查找下一个未被占用的内存块
                }
            }
        }
        return -1; // 分配失败
    }

    /**
     * 释放内存
     *
     * @param start 起始地址
     * @param size  释放的内存大小
     */
    public void deallocate(int start, int size) {
        for (int i = start; i < start + size; i++) {
            status[i] = false; // 将内存状态设置为未被占用
        }
    }
}

最佳适应算法（Best Fit）：

public class BestFit {
    private int[] memory; // 内存空间
    private boolean[] status; // 内存状态，true表示已被占用，false表示未被占用

    public BestFit(int size) {
        memory = new int[size];
        status = new boolean[size];
    }

    /**
     * 分配内存
     *
     * @param size 请求的内存大小
     * @return 分配的起始地址，若分配失败则返回-1
     */
    public int allocate(int size) {
        int min = Integer.MAX_VALUE; // 初始化最小空闲块大小
        int index = -1; // 初始化最小空闲块的下标
        for (int i = 0; i < memory.length; i++) {
            if (!status[i]) { // 找到一个未被占用的内存块
                int j = i;
                int count = 0;
                while (j < memory.length && !status[j] && count < size) { // 查找连续的未被占用的内存块
                    count++;
                    j++;
                }
                if (count >= size && count < min) { // 找到了满足要求的内存块
                    min = count;
                    index = i;
                }
                i = j - 1; // 继续查找下一个未被占用的内存块
            }
        }
        if (index != -1) { // 分配内存
            for (int i = index; i < index + size; i++) {
                status[i] = true; // 将内存状态设置为已被占用
            }
            return index; // 返回分配的起始地址
        } else {
            return -1; // 分配失败
        }
    }

    /**
     * 释放内存
     *
     * @param start 起始地址
     * @param size  释放的内存大小
     */
    public void deallocate(int start, int size) {
        for (int i = start; i < start + size; i++) {
            status[i] = false; // 将内存状态设置为未被占用
        }
    }
}

最差适应算法（Worst Fit）：

public class WorstFit {
    private int[] memory; // 内存空间
    private boolean[] status; // 内存状态，true表示已被占用，false表示未被占用

    public WorstFit(int size) {
        memory = new int[size];
        status = new boolean[size];
    }

    /**
     * 分配内存
     *
     * @param size 请求的内存大小
     * @return 分配的起始地址，若分配失败则返回-1
     */
    public int allocate(int size) {
        int max = Integer.MIN_VALUE; // 初始化最大空闲块大小
        int index = -1; // 初始化最大空闲块的下标
        for (int i = 0; i < memory.length; i++) {
            if (!status[i]) { // 找到一个未被占用的内存块
                int j = i;
                int count = 0;
                while (j < memory.length && !status[j] && count < size) { // 查找连续的未被占用的内存块
                    count++;
                    j++;
                }
                if (count >= size && count > max) { // 找到了满足要求的内存块
                    max = count;
                    index = i;
                }
                i = j - 1; // 继续查找下一个未被占用的内存块
            }
        }
        if (index != -1) { // 分配内存
            for (int i = index; i < index + size; i++) {
                status[i] = true; // 将内存状态设置为已被占用
            }
            return index; // 返回分配的起始地址
        } else {
            return -1; // 分配失败
        }
    }

    /**
     * 释放内存
     *
     * @param start 起始地址
     * @param size  释放的内存大小
     */
    public void deallocate(int start, int size) {
        for (int i = start; i < start + size; i++) {
            status[i] = false; // 将内存状态设置为未被占用
        }
    }
}