[数据结构与算法] Java实现模拟进调度算法-操作系统实验

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java实现模拟进调度算法-操作系统实验 -> 正文阅读

[数据结构与算法]Java实现模拟进调度算法-操作系统实验

实验要求：
模拟进程调度的各种算法：

先来先服务算法；(FCFS)
时间片轮转算法(TRR)
多级反馈队列算法(MQ)
动态优先级算法(JF)
高响应比优先算法(HRRN)
思路：
我们知道进程至少处于三种状态中的一种：
1. 就绪状态
2. 运行状态
3. 完成状态
  如果还考虑阻塞进程的话，有阻塞状态，
  如下图：
  本次实验使用的是LinkedList<> link 来模拟进程的各种状态。以及如何实现不同算法下的调度过程。
  我的思路是先定义一个进程对象的类：Pcb，
  应该包括以下属性：
进程名
进程id（可以使用uuid生成）
到达时间(先自己指定，便于检验进程调度过程)
服务时间(先自己指定)
完成时间
等待时间
已使用cpu时间(用于时间片算法)

总的来说，建立一个Pcb进程信息类，完成初始化操作，把多个进程对象放入队列中，使用的数据结构是LinkedList 把进程对象放入队列中之后，
就完成了初始化操作，而不同调度算法的不同之处是哪个进程先进入就绪队列呢？
如下图所示
在这里插入图片描述

理解了进程的调度过程，具体的实现如下：

定义Pcb类：

public class Pcb {
    //成员属性
    private String name;//进程名
    private String id;//进程id
    private int priorityNum;//优先数，自己指定，优先数越大，优先级越低
    private int arriveTime;//到达时间 //自己指定
    private int totalRuntime; //需要运行的时间 ,自己指定
    private int useCpuTime;//剩余运行时间=需要运行时间-固定时间片大小 自己求
    private int finishTime; //完成时间=上一进程的完成时间+当前进程的服务时间 自己求
    private int waitTime;//等待时间=上一进程的完成时间-当前进程的到达时间
    private double response;//响应比=1+等待时间/服务时间
    //生成构造方法和getter、setter方法
    ...
    //重写toString()方法
    ...
    }

定义一个实现各种算法调度的类：PcbMenu:
1. 初始化进程

public class ProcessMenu {
    LinkedList<Pcb> pcb;//存放所有的进程
    LinkedList<Pcb> readyLink;  //存放已经进入就绪队列的进程
    Pcb runLink; //存放运行状态的进程,只有一个
    //创建三级队列：多级反馈队列算法时使用
    LinkedList<Pcb> RQ1 = new LinkedList<>();
    LinkedList<Pcb> RQ2 = new LinkedList<>();
    LinkedList<Pcb> RQ3 = new LinkedList<>();

    //空构造方法
    public ProcessMenu() {
    }

    Transform transform = new TransformImp();
	//进程的初始化操作
    public LinkedList<Pcb> init(Pcb newProcess) {
        pcb = new LinkedList<>();
        readyLink = new LinkedList<Pcb>();
        Pcb p1 = new Pcb("进程1", "001", 3, 0, 3);
        Pcb p2 = new Pcb("进程2", "002", 2, 2, 6);
        Pcb p3 = new Pcb("进程3", "003", 3, 4, 4);
        Pcb p4 = new Pcb("进程4", "004", 1, 6, 5);
        Pcb p5 = new Pcb("进程5", "005", 5, 8, 2);
        pcb.add(p1);
        pcb.add(p2);
        pcb.add(p3);
        pcb.add(p4);
        pcb.add(p5);
        if(newProcess!=null){
            if(pcb.add(newProcess)){
                System.out.println("插入成功！");
            }
        }
        //对初始化进程进行排序就变成--进入就绪状态的队列
        Collections.sort(pcb, new compareAt_ServerTime());
//        System.out.println(pcb.toString());
        readyLink = pcb;
        runLink = null;
        return readyLink;
    }
}

2. 创建实现各种算法的比较器

//按到达时间排序，到达时间相同，则按服务时间排序---用于进程的FCFS等算法
    class compareAt_ServerTime implements Comparator<Pcb> {
        @Override
        public int compare(Pcb o1, Pcb o2) {
            int a = o1.getArriveTime() - o2.getArriveTime();
            if (a > 0) {
                return 1;
            } else if (a == 0) {
                return o1.getTotalRuntime() > o2.getTotalRuntime() ? 1 : -1;

            } else
                return -1;
        }
    }
    //创建优先级比较器--从高到低
    class compareAt_Priority implements Comparator<Pcb> {

        @Override
        public int compare(Pcb o1, Pcb o2) {
            int a = o1.getPriorityNum() - o2.getPriorityNum();
            if(a>0){
                return 1;
            }else if(a == 0){
                return o1.getArriveTime() > o2.getArriveTime() ? 1: -1;
            }else {
                return -1;
            }
        }
    }
    //创建响应比比较器--高到低
    class compareAt_Response implements Comparator<Pcb> {

        @Override
        public int compare(Pcb o1, Pcb o2) {
            double a = o1.getResponse() - o2.getResponse();
            if(a<0.0){
                return 1;
            }
            else if(a == 0.0){
                return o1.getArriveTime() > o2.getArriveTime() ? 1: -1;
            }else{
                return -1;
            }
        }
    }

3. 各种算法的实现：
	1. FCFS算法----先来先服务算法

//先来先到原则调度算法
    public void FCFS(LinkedList<Pcb> readyLink) {
        LinkedList<Pcb> finishLink = new LinkedList<>();
        LinkedList<Pcb> waitLink = new LinkedList<>(); //存放等待状态的队列
        int size = readyLink.size();
        int lastFinishTime = 0;//上一进程的完成时间
        int waitTime = 0;//当前进程的等待时间
        System.out.println("就绪队列的元素个数："+readyLink.size());
        for(int i = 1; i<=size;i++){
            System.out.println("第"+i+"次进程调度情况");
            Time.startTime();
            if(i == 1){
                //将就绪状态转化为运行状态
                runLink = transform.readyToRun(readyLink);
                displayRun(runLink);
                //设置完成时间--=第一次是服务时间
                runLink.setFinishTime(runLink.getTotalRuntime());
                //初始化等待时间
                waitTime = 0;
                runLink.setWaitTime(waitTime);
            }
            else{
                lastFinishTime = runLink.getFinishTime();
                //将就绪状态转化为运行状态
                runLink = transform.readyToRun(readyLink);
                displayRun(runLink);
                //设置完成时间--=
                runLink.setFinishTime(runLink.getTotalRuntime()+lastFinishTime);
                //设置等待时间--
                runLink.setWaitTime(lastFinishTime-runLink.getArriveTime());
            }
            //---在第一次时做了是否要阻塞一个进程的逻辑实现
            if(i==1){
                System.out.println("需要阻塞当前进程吗？请输入Yes或No");
                Scanner scanner = new Scanner(System.in);
                String input = scanner.nextLine();
                if("Yes".equals(input)){
                    //阻塞一个进程
                    waitLink = transform.runToWait(runLink);
                    displayWaitLink(waitLink);
                    System.out.println("当前进程已经阻塞，需要停止阻塞吗？请输入Yes或No");
                    Scanner scanner1 = new Scanner(System.in);
                    String flag = scanner1.nextLine();
                    if("Yes".equals(flag)){
                        //取消阻塞
                        transform.WaitToReady(waitLink,readyLink);
                    }
                    continue;
                }
            }
            long midTime = runLink.getTotalRuntime();
            WaitTimeUtil.waitTime(midTime);
            //结束时间
            Time.endTime();
            //打印就绪队列的情况
            displayReadyLink(readyLink);
            //从运行状态变为完成状态--
            finishLink = transform.runToFinish(runLink);
            //打印finishLink列表
            displayFinishLink(finishLink);
        }
        //从运行状态变为完成状态---就绪状态变为运行状态
    }

	2. 时间片轮转调度算法

/**
     * 算法思想：
     * 1. 指定固定的时间片大小
     * 2. 到达顺序一开始初始化的时候就要完成---顺序同fcfs一样
     * 3. 如果就绪队列不为空--就要循环执行
     * 4. 每次取出就绪队首的元素进入运行状态
     * 5. 单位时间片时间到，剩余运行时间减单位时间片。
     * 6.判断剩余时间是否为零---为零则进入完成队列，不为零则进入就绪队列的队尾。
     * 7. 开始下一次的循环。
     *
     */

    public void TRR(LinkedList<Pcb> readyLink,int time,boolean flag){
        LinkedList<Pcb> finishLink = new LinkedList<>();
        int size = readyLink.size();//获取就绪队列中的进程数
        int count = 1;
        System.out.println("========处于就绪状态的进程数=======："+size);
        initUseTime(readyLink);
        while(readyLink!=null && readyLink.size()!=0){
            //开始时间
            System.out.println("第"+count+"次进程调度情况");
            Time.startTime();
            //取出就绪队列的队首元素---就绪状态变为运行状态
            int useTime = readyLink.getFirst().getUseCpuTime();
            runLink = transform.readyToRun(readyLink);
            //打印此时正在运行的队列元素
            displayRun(runLink);
            //计时器--倒计时
            long midTime = time;
            WaitTimeUtil.waitTime(midTime);
            //结束时间
            Time.endTime();
            useTime-=time;
            runLink.setUseCpuTime(useTime);
            if(runLink.getUseCpuTime()<=0){
                //如果剩余时间为零--撤销该进程--进入完成队列
                finishLink = transform.runToFinish(runLink);
                displayFinishLink(finishLink);
            }
            else{
                //flag为true,代表的是高优先级算法调用时--优先数要变化
                //flag为false,代表的是时间片算法调用时---优先数不需要变化
                if(flag == true){
                    int priorityNum = runLink.getPriorityNum();
                    runLink.setPriorityNum(priorityNum+1);
                }
                //不为零则进入就绪队列队尾
                readyLink = transform.runToReady(runLink,readyLink);
            }
            if(flag == true){
                Collections.sort(readyLink,new compareAt_Priority());
                System.out.println("就绪队列中的进程信息\n"+readyLink.toString());
            }
            runLink = null;
            count++;
        }

    }

	3. 多级反馈队列算法

/**
     * 算法思想：
     * 将就绪队列分为多个就绪队列，分别叫做第1级RQ1，第二级RQ2...
     * 设置这些队列的优先级：第1级最高，依次递减。
     *
     * 本次算法采用三级反馈队列调度算法
     *  把所有的进程放入就绪队列中---
     *  三级队列都采用时间片算法进行调度
     *  时间片长度依次递增
     * 步骤：
     * 1. 初始化
     * 2. 进行第一级反馈队列的算法调度--
     * 3. 第一级队列的就绪队列都运行一个时间片后，若进程的所需时间没有达到，则进入第二级队列
     * 若进程服务时间完成，则撤销该进程，进入完成队列中
     * 4. 第二队列同第一队列，只是时间片长度不一样。
     * 5. 第三队列的进程运行一个时间片后，同时间片调度算法，
     * 若进程的所需时间没有达到，则添加到队尾
     * 若进程服务时间完成，则撤销该进程，进入完成队列中
     * 直到第三级队列为空，所有的进程都进入完成队列，退出循环。
     *
     *
     */
    public void MQ(LinkedList<Pcb> RQ1){
        int RQ1Time = 1;
        int RQ2Time = 2;
        int RQ3Time = 10;
        LinkedList<Pcb> finishLink = new LinkedList<>();
        initUseTime(RQ1);
        //对第一级反馈队列进行调度---时间片为1
        System.out.println("第一级反馈队列调度--时间片为1");
        System.out.println("RQ1的大小"+RQ1.size());
        while(RQ1.size()>0 &&RQ1!=null){
                runLink = transform.readyToRun(RQ1);
                displayRun(runLink);
                int useTime = runLink.getUseCpuTime();
                //剩余时间减去一个时间片
                useTime-=RQ1Time;
                runLink.setUseCpuTime(useTime);
                if(useTime>0){
                    //进入下一级队列中
                    RQ2.addFirst(runLink);
                }else{
                    //将运行状态变为完成状态
                    finishLink = transform.runToFinish(runLink);
                    //打印完成队列的信息---没有计算等待时间和完成时间
//                    displayFinishLink(finishLink);
                    displayReadyLink(finishLink);
                }
                //按FCFS的顺序
                Collections.sort(RQ1,new compareAt_ServerTime());
            }
        System.out.println("====第一级队列进程调度完之后已经完成的进程有：\n"+finishLink);
        System.out.println("====第一级时间片用完也没有结束的进入第二级队列====\n"+RQ2.toString());
        System.out.println("=====开始第二级队列调度======");
        while(RQ2.size()>0&& RQ2!=null){
            //将二级队列中的进程以时间片2运行，如剩余时间>0则进入第三级队列
            //获取当前队首需要服务的时间
            //按FCFS的顺序
            Collections.sort(RQ2,new compareAt_ServerTime());
            runLink = transform.readyToRun(RQ2);
            displayRun(runLink);
            int useTime = runLink.getUseCpuTime();
            //剩余时间减去一个时间片
            useTime-=RQ2Time;
            runLink.setUseCpuTime(useTime);
            if(useTime>0){
                //进入下一级队列中
                RQ3.addFirst(runLink);
            }else{
                //将运行状态变为完成状态
                finishLink = transform.runToFinish(runLink);
//                displayFinishLink(finishLink);
                displayReadyLink(finishLink);
            }
        }
        System.out.println("第二级队列进程调度完之后已经完成的进程有：\n"+finishLink);
        System.out.println("====第二级时间片用完也没有结束的进入第三级队列====\n"+RQ3.toString());
        if(RQ3.size()>0&& RQ3!=null){
            System.out.println("=====开始第三级队列调度======时间片为8====");
            Collections.sort(RQ3,new compareAt_ServerTime());
            TRR(RQ3,RQ3Time,false);
        }
    }

	4.  动态优先级算法


 // //创建动态优先级调度算法

    /**
     *
     * 优先数越大，优先级越低
     * 创建动态优先级调度算法
     * 算法思想：
     * 1. 就绪队列先按照优先级从高到低排列===优先数从低到高
     * 2. 获取队首的进程，将它变为运行状态---采用的是时间片算法调度
     * 3. 运行完毕，将它的剩余时间减一，判断剩余时间是否<=0,若是，
     * 则撤销该进程，若不是，则将它的优先数+1，把运行进程插入到就绪队列队尾。
     * 4.循环1,2,3，直到就绪队列的大小为0
     *
     *
     */
    public void JF(LinkedList<Pcb> readyLink){
        while(readyLink.size()>0&& readyLink!=null){
            //1. 就绪队列先按照优先级从高到低排列
            System.out.println("当前就绪队列的进程数："+readyLink.size());
            Collections.sort(readyLink,new compareAt_Priority());
            System.out.println("输出排序之后的队列-----\n"+readyLink);
            //2. 获取队首进程--将就绪状态变为运行状态---时间片算法
            TRR(readyLink,2,true);
        }
    }

	5. 高响应比优先算法

 //创建高响应比优先算法---

    /**
     * 等待时间=上一进程的完成时间-当前进程的到达时间
     * 当前进程的完成时间=上一进程的完成时间+当前进程的服务时间
     * 算法思路：
     * 1. 初始化就绪队列---按到达时间排序
     * 2. 将队首进程变为运行状态--
     * 3. 计算就绪队列中的响应比=1+等待时间/服务时间，每个进程运行完毕之后都会改变响应比
     * 4. 排序算法--按照高响应比优先进行调度
     *
     */
    public void HRRN(LinkedList<Pcb> readyLink){
        LinkedList<Pcb> finishLink = new LinkedList<>();
        int i = 0;
        int lastFinishTime = 0;
        int waitTime = 0;
        while(readyLink.size()>0 && readyLink!=null){
            //开始时间
            //打印就绪队列信息
            displayReadyLink(readyLink);
            System.out.println("第"+(i+1)+"次进程调度情况");
           //开始时间
            Time.startTime();
            if(i == 0){
                //1.将队首进程变为运行状态
                runLink = transform.readyToRun(readyLink);
                //打印运行状态的进程信息---
                displayRun(runLink);
                //计时器--倒计时
                long midTime = runLink.getTotalRuntime();
                WaitTimeUtil.waitTime(midTime);
                //结束时间
               Time.endTime();

                //设置完成时间--=第一次是服务时间
                runLink.setFinishTime(runLink.getTotalRuntime());
                //初始化等待时间
                waitTime = 0;
                runLink.setWaitTime(waitTime);
            }
            else{
                lastFinishTime = runLink.getFinishTime();
                //1.将队首进程变为运行状态
                runLink = transform.readyToRun(readyLink);
                //打印运行状态的进程信息---
                displayRun(runLink);

                //计时器--倒计时
                long midTime = runLink.getTotalRuntime();
                WaitTimeUtil.waitTime(midTime);
                //结束时间
                Time.endTime();
                //设置完成时间--=
                runLink.setFinishTime(runLink.getTotalRuntime()+lastFinishTime);
                //设置等待时间--
                runLink.setWaitTime(lastFinishTime-runLink.getArriveTime());
            }
            //将运行状态变为完成状态
            finishLink = transform.runToFinish(runLink);
            //打印完成队列信息--
            displayFinishLink(finishLink);
            //计算响应比
            response(readyLink,runLink);
            //重新排序--根据响应比的大小
            Collections.sort(readyLink, new compareAt_Response());
            i++;
        }
    }

    //计算响应比--
    public void response(LinkedList<Pcb> readyLink,Pcb runLink){
        double response = 0.0;
        //响应比= 1+等待时间/服务时间
        for(int i = 0 ;i< readyLink.size();i++){
            int waitTime = runLink.getFinishTime() - readyLink.get(i).getArriveTime();
            int serveTime = readyLink.get(i).getTotalRuntime();
            DecimalFormat df = new DecimalFormat("0.00");
            String y = df.format((float)waitTime/serveTime);
            double s = Double.valueOf(y);
            response = s +1.0;
            readyLink.get(i).setResponse(response);
            System.out.println(readyLink.get(i).getName()+"的响应比为"+readyLink.get(i).getResponse());
        }
    }
    //

定义实现状态转换的接口和接口的实现类：
transform接口


```java
package com.gcl.process.service;

import com.gcl.process.model.Pcb;

import java.util.LinkedList;

public interface Transform {
    //1. 就绪状态转化为运行状态
    Pcb readyToRun(LinkedList<Pcb> readyLink);
    //2. 运行状态转化为完成状态
    LinkedList<Pcb> runToFinish(Pcb runLink);
    //3.运行状态转化为就绪状态
    LinkedList<Pcb> runToReady(Pcb runLink,LinkedList<Pcb> readyLink);

    //3.运行状态转化为等待状态
    LinkedList<Pcb> runToWait(Pcb runLink);
    //4. 等待状态转化为就绪状态
    void WaitToReady(LinkedList<Pcb> WaitLink,LinkedList<Pcb> readyLink);
    //5. 新增一个进程
    LinkedList<Pcb> addProcess(Pcb newProcess,LinkedList<Pcb> readyLink);
}

transform接口的实现类

package com.gcl.process.service;

import com.gcl.process.model.Pcb;

import java.util.LinkedList;

public class TransformImp implements Transform {
    LinkedList<Pcb> finishLink =new LinkedList<>();
    LinkedList<Pcb> waitLink = new LinkedList<>();

    /**
     * 就绪状态转化为运行状态
     * 从队首出队，从队尾入队
     * @param readyLink
     *
     */
    @Override
    public Pcb readyToRun(LinkedList<Pcb> readyLink) {
        if(readyLink.size()>0){
            //1.取出就绪队列中队首的元素赋值给运行状态中
           return readyLink.removeFirst();
        }
        return null;
    }

    /**
     * 运行状态变为完成状态
     * @param runLink
     */
    @Override
    public LinkedList<Pcb> runToFinish(Pcb runLink) {
        finishLink.addLast(runLink);
        return finishLink;
    }

    /**
     * 用于时间片算法中
     * 运行状态变为就绪状态
     * @param runLink
     * @param readyLink
     * @return
     */
    @Override
    public LinkedList<Pcb> runToReady(Pcb runLink,LinkedList<Pcb> readyLink) {
        readyLink.addLast(runLink);
        return readyLink;
    }

    /**
     * 返回等待队列
     * @param runLink
     * @return
     */
    @Override
    public LinkedList<Pcb> runToWait(Pcb runLink) {
        waitLink.addLast(runLink);
        runLink = null;
        return waitLink;
    }

    @Override
    public void WaitToReady(LinkedList<Pcb> WaitLink, LinkedList<Pcb> readyLink) {
        for(int i = 0;i<WaitLink.size();i++){
            Pcb element = WaitLink.remove(i);
            readyLink.addLast(element);
        }
    }

    /**
     * 新增一个进程算法
     * @param readyLink
     * @return
     */
    @Override
    public LinkedList<Pcb> addProcess(Pcb newProcess,LinkedList<Pcb> readyLink) {
        if(newProcess!=null){
            readyLink.addLast(newProcess);
            return readyLink;
        }
        return readyLink;
    }
}