编辑代码

import java.util.LinkedList;
import java.util.Random;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        new ProcessMemoryScheduling().run();
    }
}

public class PCB {
    String name;        // 进程名
    int needMemory;     // 所需内存
    int address;        // 主存起始位置
    double arriveTime;  // 到达时间
    double needTime;    // 需要运行时间
    double hasUsedTime; // 已用时间
    String status;      // 进程状态：运行中、就绪、阻塞(Running、 Waiting、 Blocking)
}

public class MemoryBlock {
    int address;            // 内存块地址
    int length;             // 内存块长度
    String status = "Free"; // 内存块的状态：Busy或 Free

    MemoryBlock(int address, int length) {
        this.address = address;
        this.length = length;
    }
}


public class ProcessMemoryScheduling {
    private static int PROCESS_NUM = 10;        // 进程数
    private int blocked = 0;             // 阻塞进程的标识，表示是否有进程属于阻塞状态
    private int blockIndex = -1;                // 阻塞进程的下标，没有阻塞进程则为-1
    private PCB[] pcb = new PCB[PROCESS_NUM];   // 进程数组，存放所有进程
    private LinkedList<MemoryBlock> memoryBlockList = new LinkedList<>();


    private double timeSlice;   // 时间片的大小
    private int runningIndex;   // 当前运行的进程的下标（索引），没有则为-1
    private long lastTime;      // 每次调度程序都记录当前时间
    private long beginTime;     // 程序开始运行的时间


    /* 用于判断所有进程是否运行完*/
    private boolean isFinishALLProcess() {
        for (int i = 0; i < PROCESS_NUM; i++) {
            if (!pcb[i].status.equals("Finish")) {
                return false;
            }
        }
        return true;
    }


    /* 初始化测试数据*/
    private void initData() {
        runningIndex = -1;
        Random r = new Random();
        for (int n = 0; n < PROCESS_NUM; n++) {
            pcb[n] = new PCB();
            pcb[n].name = "P" + Integer.toString(n + 1);   // 设置进程名
            pcb[n].needTime = r.nextDouble() * 4 + 12;   // 随机产生服务时间，4到12秒
            pcb[n].needMemory = r.nextInt(122) + 38;   // 随机产生需要的内存，38到150KB
            if (n == 0) {
                pcb[n].arriveTime = 0;  // 第一个作业默认0时刻到达
                pcb[0].needMemory = 50;
            } else {
                pcb[n].arriveTime = r.nextDouble() * 5 + 1;     // 随机设置到达时间
                pcb[n].needMemory = r.nextInt(122) + 38; // 随机产生需要的内存，38到150KB
            }
        }
        for (int n = 0; n < PROCESS_NUM; n++) {
            pcb[n].hasUsedTime = 0;
            pcb[n].address = 0;
            pcb[n].status = "U";
        }
        MemoryBlock firstBlock = new MemoryBlock(0, 1024);  //设置用户内存在0到1024之间
        memoryBlockList.add(firstBlock);
        print();
    }


    /*精确度位数的截图*/
    private String d2s(double d) {
        String tmp = d + "";
        int index = tmp.indexOf(".");
        int EXACT_DIGIT = 1;    // double型变量小数点后精确的尾数
        return tmp.substring(0, index + EXACT_DIGIT + 1);
    }


    /*一次划分算法，为快排做准备*/
    private int getStandard(int i, int j) {
        PCB key = pcb[i]; // 基准数据
        while (i < j) {
            // 因为默认基准是从左边开始，所以从右边开始比较
            // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
            while (i < j && pcb[j].arriveTime >= key.arriveTime) {
                j--;
            }
            // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
            if (i < j) {
                pcb[i] = pcb[j];
            }
            // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
            while (i < j && pcb[i].arriveTime <= key.arriveTime) {
                i++;
            }
            // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
            if (i < j) {
                pcb[j] = pcb[i];
            }
        }
        // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
        // 把基准数据赋给正确位置
        pcb[i] = key;
        return i;
    }


    /*根据到达时间使用快排算法进行排序*/
    private void quickSortByArriTime(int low, int high) {
        // 开始默认基准为 low
        if (low < high) {
            int standard = getStandard( low, high);         // 分段位置下标
            quickSortByArriTime( low, standard - 1);   // 左边排序
            quickSortByArriTime(standard + 1, high);    // 右边排序
        }
    }

    /*结果显示函数*/
    private void print() {
     System.out.println("\n-----------------------------------------------------------------------------");
        System.out.println("内存分区表(Busy:占用 Free:空闲)：");
        System.out.println("起址(K)  长度（KB）    状态");
        for (MemoryBlock memoryBlock : memoryBlockList) {
            System.out.printf("%-8d  %-10d  %-6s\n", memoryBlock.address, memoryBlock.length, memoryBlock.status);
        }

        /* 打印后备队列中的作业 */
        System.out.println("\n后备队列中的作业:");
        for (int i = 0; i < PROCESS_NUM; i++) {
            if (pcb[i].status.equals("U")) {
                System.out.print(pcb[i].name + "\t");
            }
        }

        /* 打印就绪队列、运行中、阻塞状态、完成调度这几个状态的进程 */
        System.out.println("\n当前各进程PCB信息：");
        System.out.print("进程名  到达时间/s  需要时间/s  已用时间/s  所需内存/KB      内存起址      进程状态\n");
        for (int i = 0; i < PROCESS_NUM; i++) {
            if (!pcb[i].status.equals("U")) {
                System.out.printf("%-6s  %-10s  %-10s  %-10s  %-11d  %-8d  %-8s\n", pcb[i].name, d2s(pcb[i].arriveTime)
                        , d2s(pcb[i].needTime), d2s(pcb[i].hasUsedTime), pcb[i].needMemory, pcb[i].address, pcb[i].status);
            }
        }
        System.out.println("-----------------------------------------------------------------------------");
        lastTime = System.currentTimeMillis(); // 更新上次调度时间
    }

    /* 获取后续等待进程信息*/
    private int getNextWaiting(int curr) {
        int p = curr;
        while ((p = ++p % PROCESS_NUM) != curr) {
            if (pcb[p].status.equals( "Waiting") ) {
                return p;
            }
        }
        return -1;
    }


    /*从后备队列中选择作业并申请内存*/
    private void getNextOnDisk(double allTime) {
        int memoryProcessNum = 0;   // 在内存中的进程个数
        for (PCB aPcb : pcb) {
            if (aPcb.status.equals("Waiting") || aPcb.status.equals("Running") || aPcb.status.equals("Blocking")) {
                memoryProcessNum++;
            }
        }
        int MAX_OCCURS = 5; //允许并发的进程数量，小于这个数时从后备队列调入进程
        if (memoryProcessNum < MAX_OCCURS) { // 如果内存中程序数少于最大并发数，从后备队列找到最先到达的进程调入内存
            for (int p = 0; p < pcb.length && memoryProcessNum < MAX_OCCURS; p++) {
                if (pcb[p].status.equals("U") && allTime >= pcb[p].arriveTime) {
                    int address = applyMemory(p);
                    if (address != -2) { // 分配内存成功才修改状态
                        pcb[p].address = address;
                        pcb[p].status = "Waiting";
                        memoryProcessNum++;
                    }
                }
            }
        }
    }


    /*申请内存*/
    private int applyMemory(int curr) {
        if (!pcb[curr].status.equals("U")) {
            return -2;
        }
        MemoryBlock target = null;
        int needMemory = pcb[curr].needMemory;
        for (MemoryBlock memoryBlock : memoryBlockList) {
            if (memoryBlock.status.equals("Free") && memoryBlock.length >= needMemory) {
                target = memoryBlock;
                break;
            }
        }
        if (target == null) { // 找不到合适的内存块用于分配
            return -2;
        } else if (target.length == needMemory) { // 申请的内存和内存分区刚好相等，直接将整块分区分给该进程
            target.status = "Busy";
            return target.address;
        } else {
            target.status = "Busy";
            MemoryBlock block = new MemoryBlock(target.address + needMemory, target.length - needMemory);
            target.length -= block.length;
            memoryBlockList.add(memoryBlockList.indexOf(target) + 1, block); // 将新建的空闲分区插入到分区连中
            return target.address;
        }
    }

    /*进程运行完之后释放内存*/
    private void releaseMemory(int address) {
        MemoryBlock target = null;
        for (MemoryBlock memoryBlock : memoryBlockList) {
            if (memoryBlock.address == address) {
                target = memoryBlock;
                break;
            }
        }
        if (target == null){
            return;
        }
        if(memoryBlockList.size()==1){
            target.status = "Free";
            return;
        }

        int index = memoryBlockList.indexOf(target);
        if (index == 0) {
            MemoryBlock memoryBlock = memoryBlockList.get(1);
            if (memoryBlock.status.equals( "Free")) {
                target.length += memoryBlock.length;
                memoryBlockList.remove(memoryBlock);
            }
            target.status = "Free";
        } else if (index == memoryBlockList.size() - 1) {
            MemoryBlock m = memoryBlockList.get(index - 1);
            if (m.status.equals("Free") ) {
                m.length += target.length;
                memoryBlockList.remove(target);
            }
            target.status = "Free";
        } else {
            MemoryBlock preMemoryBlock= memoryBlockList.get(index - 1);
            MemoryBlock nextMemoryBlock = memoryBlockList.get(index + 1);
            if (preMemoryBlock.status.equals("Free")  && nextMemoryBlock.status.equals( "Free")) {
                preMemoryBlock.length += target.length;
                preMemoryBlock.length += nextMemoryBlock.length;
                memoryBlockList.remove(target);
                memoryBlockList.remove(nextMemoryBlock);
            } else if (preMemoryBlock.status.equals("Free")  && nextMemoryBlock.status.equals("Busy") ) {
                preMemoryBlock.length += target.length;
                memoryBlockList.remove(target);
            } else if (preMemoryBlock.status.equals("Busy")  && nextMemoryBlock.status.equals("Free") ) {
                target.length += nextMemoryBlock.length;
                target.status = "Free";
                memoryBlockList.remove(nextMemoryBlock);
            } else {
                target.status = "Free";
            }
        }
    }

    /*调度方法 */
    private void dispatch() throws InterruptedException {
        if (isFinishALLProcess()) {
            return;
        }
        long now = System.currentTimeMillis();
        double passedTime = (now - lastTime) / 1000.0; //距离上次调度经过的时间
        double allTime = (now - beginTime) / 1000.0;

        /* 从后备队列调入进程 */
        getNextOnDisk(allTime);
        if (runningIndex != -1) {
            double oldhasUsedTime = pcb[runningIndex].hasUsedTime;
            if (passedTime >= timeSlice) {
                if (oldhasUsedTime + passedTime >= pcb[runningIndex].needTime) {
                    pcb[runningIndex].hasUsedTime = pcb[runningIndex].needTime;
                    pcb[runningIndex].status = "Finish";
                    releaseMemory(pcb[runningIndex].address);
                } else {
                    pcb[runningIndex].hasUsedTime = oldhasUsedTime + timeSlice;
                    pcb[runningIndex].status = "Waiting";
                }
                /* 从就绪队列中选择下一个进程 */
                int next = getNextWaiting(runningIndex);
                if (next != -1) {
                    pcb[next].status = "Running";
                    runningIndex = next;
                    print();
                }
            }
        } else {
            pcb[0].status = "Running";
            runningIndex = 0;
            print();
        }

        /* 随机阻塞进程 */
        Random random = new Random();
        int randomNum = random.nextInt(3);
        if (randomNum == 2 && (blocked == 0 ) ) { // 符合此条件的进程将被阻塞
            blockIndex = runningIndex;
            pcb[runningIndex].status = "Blocking";
            blocked = 1;
            runningIndex = getNextWaiting(runningIndex);
        }

        /* 唤醒进程 */
        if (blocked == 1) {
            long time = System.currentTimeMillis();
            double intervalTime = (time - lastTime) / 1000.0;
            if (runningIndex == -1) {
                // 只剩下最后一个阻塞进程未执行完，则该进程休眠1秒后唤醒
                Thread.sleep(1000);
                runningIndex = blockIndex;
                pcb[runningIndex].status = "Waiting";
                blocked = 0;
            } else if (intervalTime > 2.0) {
                // 有进程属于阻塞状态时，满足阻塞时间大于2s则唤醒进程
                if (blockIndex != -1) {
                    pcb[blockIndex].status = "Waiting";
                    blocked = 0;
                }
            }
        }
    }

    /*启动进程调度*/
    public void run() throws InterruptedException {
        System.out.println();
        System.out.println("------------------------------------------------------");
        System.out.println("           课程设计：进程管理系统                 ");
        System.out.println("------------------------------------------------------");
        initData();
        timeSlice=2;

        /* 使用快速排序算法，按照先来先服务的原则排序 */
        quickSortByArriTime(0, PROCESS_NUM - 1);
        beginTime = System.currentTimeMillis();
        lastTime = System.currentTimeMillis();
        while (true) {
            dispatch();
            if (isFinishALLProcess()) { // 如果所有进程都已经完成调度，则退出循环
                break;
            }
        }
        print();
        System.out.print("------------------所有进程运行结束------------------\n\n");
    }
}