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

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

    Transform transform = new TransformImp();
	//进程的初始化操作
    public LinkedList init(Pcb newProcess) {
        pcb = new LinkedList<>();
        readyLink = new LinkedList();
        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 {
        @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 {

        @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 {

        @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 readyLink) {
        LinkedList finishLink = new LinkedList<>();
        LinkedList 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. 时间片轮转调度算法


    public void TRR(LinkedList readyLink,int time,boolean flag){
        LinkedList 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. 多级反馈队列算法

    public void MQ(LinkedList RQ1){
        int RQ1Time = 1;
        int RQ2Time = 2;
        int RQ3Time = 10;
        LinkedList 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.  动态优先级算法

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

    
    public void JF(LinkedList 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. 高响应比优先算法

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

    
    public void HRRN(LinkedList readyLink){
        LinkedList 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 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 readyLink);
    //2. 运行状态转化为完成状态
    LinkedList runToFinish(Pcb runLink);
    //3.运行状态转化为就绪状态
    LinkedList runToReady(Pcb runLink,LinkedList readyLink);

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

transform接口的实现类

package com.gcl.process.service;

import com.gcl.process.model.Pcb;

import java.util.LinkedList;

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

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

    
    @Override
    public LinkedList runToFinish(Pcb runLink) {
        finishLink.addLast(runLink);
        return finishLink;
    }

    
    @Override
    public LinkedList runToReady(Pcb runLink,LinkedList readyLink) {
        readyLink.addLast(runLink);
        return readyLink;
    }

    
    @Override
    public LinkedList runToWait(Pcb runLink) {
        waitLink.addLast(runLink);
        runLink = null;
        return waitLink;
    }

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

    
    @Override
    public LinkedList addProcess(Pcb newProcess,LinkedList readyLink) {
        if(newProcess!=null){
            readyLink.addLast(newProcess);
            return readyLink;
        }
        return readyLink;
    }
}

Java实现模拟进调度算法-操作系统实验

Java相关栏目本月热门文章