problem

实验内容：

编写一个动态分区分配算法模拟程序，加深对动态分区存储管理方式及其实现过程的理解。

要求：

空闲分区通过空闲区链进行管理，在内存分配时，优先考虑低地址部分的空闲区。
分别采用首次适应算法、最佳适应算法和最坏适应算法模拟内存空间的动态分配与回收，每次分配和回收后显示出空闲区链的详细情况（说明：在申请不成功时，需要打印当前内存的占用情况信息）。
进程对内存空间的申请和释放可由用户自定义输入。
参考请求序列如下：
(1) 初始状态下可用内存空间为640KB；

(2) 进程1申请130KB；

(3) 进程2申请60KB；

(4) 进程3申请100KB；

(5) 进程2释放60KB；

(6) 进程4申请200KB；

(7) 进程3释放100KB；

(8) 进程1释放130KB；

(9) 进程5申请140KB；

(10) 进程6申请60KB；

(11) 进程7申请50KB；

(12) 进程6释放60KB。

测试用例格式如下：

输入：

动态分区分配算法选择

可用内存空间容量

序号/进程号/申请或释放操作/申请或释放的容量

其中：

(1) 动态分区分配算法：1----首次适应，2----最佳适应，3----最坏适应

(2) 申请或释放操作： 1----申请操作，2----释放操作

输出：

序号/内存空间状态1/内存空间状态2......

内存空间状态表示分为两种情况：

(1) 内存空间被占用：

内存空间起始地址-内存空间结束地址.1.占用的进程号

(2) 内存空间空闲

内存空间起始地址-内存空间结束地址.0

测试用例

测试输入

期待的输出

1 640 1/1/1/130 2/2/1/60 3/3/1/100 4/2/2/60 5/4/1/200 6/3/2/100 7/1/2/130 8/5/1/140 9/6/1/60 10/7/1/50 11/6/2/60

1/0-129.1.1/130-639.0 2/0-129.1.1/130-189.1.2/190-639.0 3/0-129.1.1/130-189.1.2/190-289.1.3/290-639.0 4/0-129.1.1/130-189.0/190-289.1.3/290-639.0 5/0-129.1.1/130-189.0/190-289.1.3/290-489.1.4/490-639.0 6/0-129.1.1/130-289.0/290-489.1.4/490-639.0 7/0-289.0/290-489.1.4/490-639.0 8/0-139.1.5/140-289.0/290-489.1.4/490-639.0 9/0-139.1.5/140-199.1.6/200-289.0/290-489.1.4/490-639.0 10/0-139.1.5/140-199.1.6/200-249.1.7/250-289.0/290-489.1.4/490-639.0 11/0-139.1.5/140-199.0/200-249.1.7/250-289.0/290-489.1.4/490-639.0

ac code

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;


class Memory {

    private int start;

    private int end;

    private boolean isUse;

    private int pid;

    public Memory(int start, int end, boolean isUse, int pid) {
        this.start = start;
        this.end = end;
        this.isUse = isUse;
        this.pid = pid;
    }

    public int getStart() {
        return start;
    }

    public void setStart(int start) {
        this.start = start;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getSize() {
        return this.end - this.start + 1;
    }

    public boolean isUse() {
        return isUse;
    }

    public void setUse(boolean use) {
        isUse = use;
    }

    public int getPid() {
        return pid;
    }

    public void setPid(int pid) {
        this.pid = pid;
    }

    @Override
    public String toString() {
        if(this.isUse()){
            return "/" + start + "-" + end + ".1." + pid;
        }
        return "/" + start + "-" + end + ".0";
    }
}

public class Main {

    private static int memorySpace;

    private static int method;

    private static List<Memory> memoryList = new LinkedList<>();


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        method = sc.nextInt();
        memorySpace = sc.nextInt();
        sc.nextLine();

        memoryList.add(new Memory(0,memorySpace-1,false,0));

        int idx = 1;
        while (sc.hasNextLine()){

            String str = sc.nextLine();

            String[] param = str.split("/");

            handle(Integer.parseInt(param[1]),Integer.parseInt(param[2]),Integer.parseInt(param[3]));

            System.out.print(idx++);
            for (Memory m : memoryList){
                System.out.print(m);
            }
            System.out.println();
        }


    }


    private static void handle(int pid,int todo,int space) {
        switch (method) {
            case 1:
                firstFit(pid, todo, space);
                break;
            case 2:
                bestFit(pid, todo, space);
                break;
            case 3:
                worstFit(pid, todo, space);
                break;
        }
    }


    private static void firstFit(int pid,int todo,int space) {
        if (todo == 1){
            for (Memory m:memoryList){
                if (m.isUse())continue;
                if (m.getSize() > space) {
                    int idx = memoryList.indexOf(m);
                    int end = m.getStart() + space - 1;
                    Memory memory = new Memory(m.getStart(),end,true,pid);
                    memoryList.add(idx,memory);
                    m.setStart(end + 1);
                    break;
                }
                if (m.getSize() == space) {
                    m.setUse(true);
                    m.setPid(pid);
                    break;
                }
            }
        }else {
            while (fix(pid, space));
        }
    }


    private static void bestFit(int pid,int todo,int space) {

        if (todo == 1){

            Memory best = memoryList.get(0);
            int min = Integer.MAX_VALUE;
            for (Memory m : memoryList){
                if (m.isUse())continue;
                if(m.getSize() >= space && m.getSize() < min){
                    min = m.getSize();
                    best = m;
                }
            }
            if (min == Integer.MAX_VALUE)return;
            
            if (best.getSize() == space) {
                best.setUse(true);
                best.setPid(pid);
                return;
            }
            
            int idx = memoryList.indexOf(best);
            int end = best.getStart() + space - 1;
            Memory memory = new Memory(best.getStart(),end,true,pid);
            memoryList.add(idx,memory);
            best.setStart(end + 1);
        }else {
            while (fix(pid, space));
        }
    }

    private static void worstFit(int pid,int todo,int space) {

        if (todo == 1){
            Memory best = memoryList.get(0);
            int max = Integer.MIN_VALUE;
            for (Memory m:memoryList){
                if(!m.isUse() && m.getSize() > space && m.getSize() > max){
                    max = m.getSize();
                    best = m;
                }
            }
            if (max == Integer.MIN_VALUE)return;

            if (best.getSize() == space) {
                best.setUse(true);
                best.setPid(pid);
                return;
            }
            
            int idx = memoryList.indexOf(best);
            int end = best.getStart() + space - 1;
            Memory memory = new Memory(best.getStart(),end,true,pid);
            memoryList.add(idx,memory);
            best.setStart(end + 1);
        }else {
            while (fix(pid, space));
        }
    }


    private static boolean fix(int pid,int space){

        for (Memory m : memoryList){
            if (m.isUse() && m.getPid() == pid){
                if(space == m.getSize()){
                    m.setUse(false);
                    break;
                }

                memoryList.add(memoryList.indexOf(m)+1,new Memory(m.getEnd() - space,m.getEnd(),false,0));

                m.setEnd(m.getStart() + space - 1);

                break;
            }
        }


        for (int i =0; i < memoryList.size() - 1 ; i++){

            Memory m = memoryList.get(i);
            if(m.isUse())continue;
            Memory nxt = memoryList.get(i+1);
            if(nxt.isUse()){
                continue;
            }
            m.setEnd(m.getEnd() + nxt.getSize());
            memoryList.remove(i + 1);

            return true;
        }
        return false;
    }

}