高优先权优先调度算法（java实现）

忘是亡心i 2022-04-24 03:14 257阅读 0赞

**目录**

1、算法思想

2、算法主要类

2.1建立job.java类

2.2主方法类DynamicJobFirst.java类

2.3工具类DynamicJobFirstUtil。

3、算法执行结果

--------------------

**优先级调度的含义**

（1）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。

（2）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。

**调度算法的两种方式**

优先级调度算法细分成如下两种方式：

非抢占式优先级算法

在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，[系统][Link 1]才能将处理机分配给另一个优先级高的就绪进程。

附：模拟实现动态高优先权优先（若数值越大优先权越高，每运行一个时间单位优先权-n，若数值越小优先权越高，没运行一个时间单位优先权+n）有难度的算法实现。

链接：https://pan.baidu.com/s/1k0SWj8I6v02x8\_s4r\_N7kQ 提取码：8kvw

## 1、算法思想 ##

首先了解算法中工作实体中几个属性的求取方法

结束时间=开始时间+服务时间

周转时间=结束时间-到达时间

带权周转时间=周转时间/服务时间

作业中有相关的三个队列，第一个，输入队列，第二个，就绪队列，第三个，执行队列，也有一个临时队列，分别存储各个时期进程状态的集合。

在主线程main方法中，

1.1首先使用循环的方式逐个输入进程的相关信息，如进程名称，进程到达时间，进程服务时间。即方法init()。该方法内所完成的功能就是接受用户在控制台输入的信息，存储到一个进程实体中，将初始化的进程实体放入一个队列中。方便后序操作。

1.2再使用进程调度算法，dispatchJob()，该方法主要作用在于找出一条合理的，最高优先权先执行的一条路径。方法内容为：设置三个队列，第一个，用户输入的进程队列，第二个，中间暂存的进程队列，用于暂存从输入队列中挑选出的进程。第三个，最后需要执行的进程队列。

首先，cpu无工作时，第一个到达的进程先服务，在第一个进程执行结束时间前到达的进程其次执行。

将输入队列中的进程一个一个的移动到执行队列中去，这是模拟调度的关键所在，将最先到达的进程放入执行队列中，让其先执行。

使用迭代器，判断条件，将执行队列中的结束时间大于输入队列的到达时间的所有进程移动到执行队列。

若遍历后，执行队列结束时间还没有进程到达，则按照到达时间排序得到第一个。

每次循环中最后会得到一个临时队列，这就是就绪队列的前身，将循环得到的临时队列按照优先数排序，若优先数相同则按照到达时间的排序方法进行排序，

每次循环结束需要将临时队列置空，否则会出现错误。

使用求周转时间和平均周转时间的函数turnRoundTime()，将已经模拟好的执行队列中的进程，逐个的求出相应的时间。

按照 ：结束时间=开始时间+服务时间，周转时间=结束时间-到达时间，带权周转时间=周转时间/服务时间 。

## 2、算法主要类 ##

### 2.1建立job.java类 ###

封装进程的相关属性和方法。主要定义有关进程中封装的属性，比如进程名称，进程服务时间，进程到达时间，进程开始时间，进程优先级，进程状态，进程结束时间，进程周转时间，进程平均周转时间等，以及其get和set方法。

package cn.zzuli.edu.dynamic;
    
    /**
     * 进程类，封装进程属性和方法
     * @author MMMMM
     *
     */
    public class PCB {
    
    	//进程名
    	private String pcbName;
    	//进程到达时间
    	private int pcbArrivalTime;
    	//进程服务时间
    	private int pcbServiceTime;
    	//进程初始优先权限
    	private int firstNum;
    	//进程状态
    	private char pcbState;
    	//进程间的链接指针
    	private PCB nextPCB;
    
    	//进程开始时间
    	private int pcbStartTime;
    	//进程完成时间
    	private int pcbOverTime;
    	//进程周转时间
    	private int pcbRoundTime;
    	//进程带权周转时间
    	private double pcbAvgRoundTime;
    
    	//get和set方法
    
    	public String getPcbName() {
    		return pcbName;
    	}
    
    	public void setPcbName(String pcbName) {
    		this.pcbName = pcbName;
    	}
    
    	public int getPcbArrivalTime() {
    		return pcbArrivalTime;
    	}
    
    	public void setPcbArrivalTime(int pcbArrivalTime) {
    		this.pcbArrivalTime = pcbArrivalTime;
    	}
    
    	public int getPcbServiceTime() {
    		return pcbServiceTime;
    	}
    
    	public void setPcbServiceTime(int pcbServiceTime) {
    		this.pcbServiceTime = pcbServiceTime;
    	}
    
    	public int getFirstNum() {
    		return firstNum;
    	}
    
    	public void setFirstNum(int firstNum) {
    		this.firstNum = firstNum;
    	}
    
    	public char getPcbState() {
    		return pcbState;
    	}
    
    	public void setPcbState(char pcbState) {
    		this.pcbState = pcbState;
    	}
    
    	public PCB getNextPCB() {
    		return nextPCB;
    	}
    
    	public void setNextPCB(PCB nextPCB) {
    		this.nextPCB = nextPCB;
    	}
    
    	public int getPcbStartTime() {
    		return pcbStartTime;
    	}
    
    	public void setPcbStartTime(int pcbStartTime) {
    		this.pcbStartTime = pcbStartTime;
    	}
    
    	public int getPcbOverTime() {
    		return pcbOverTime;
    	}
    
    	public void setPcbOverTime(int pcbOverTime) {
    		this.pcbOverTime = pcbOverTime;
    	}
    
    	public int getPcbRoundTime() {
    		return pcbRoundTime;
    	}
    
    	public void setPcbRoundTime(int pcbRoundTime) {
    		this.pcbRoundTime = pcbRoundTime;
    	}
    
    	public double getPcbAvgRoundTime() {
    		return pcbAvgRoundTime;
    	}
    
    	public void setPcbAvgRoundTime(double pcbAvgRoundTime) {
    		this.pcbAvgRoundTime = pcbAvgRoundTime;
    	}
    
    	@Override
    	public String toString() {
    		return "PCB{" +
    				"pcbName='" + pcbName + '\'' +
    				", pcbArrivalTime=" + pcbArrivalTime +
    				", pcbServiceTime=" + pcbServiceTime +
    				", firstNum=" + firstNum +
    				", pcbState=" + pcbState +
    				", nextPCB=" + nextPCB +
    				", pcbStartTime=" + pcbStartTime +
    				", pcbOverTime=" + pcbOverTime +
    				", pcbRoundTime=" + pcbRoundTime +
    				", pcbAvgRoundTime=" + pcbAvgRoundTime +
    				'}';
    	}
    }

### 2.2主方法类DynamicJobFirst.java类 ###

主方法类，主要是为了给所有类进行统一的调用，使程序有一定的顺序感，并且按顺序执行能够得到正确的答案。

主方法中，需要首先

1.对工作job类进行初始化数据，模拟进程的初始化。

2.再对进程进行模拟程序执行运行时间。

3.执行调度算法，将输入队列进程按照高优先权调度算法，插入到执行队列中。本次使用的是静态优先权调度。

4.计算执行队列中各个的进程的开始时间，结束时间，周转时间等等。

5.打印输出一定格式的执行队列中的工作信息。

package cn.zzuli.edu.dynamic;
    
    
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    /**
     * 短作业优先调度算法实现类
     * @author MMMMM
     *
     */
    public class DynamicJobFirst {
    
    	@SuppressWarnings("resource")
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		System.out.println("高优先权调度算法开始：");
    		System.out.println("请先输入作业的相关信息：（输入no代表结束）");
    		//输入作业队列
    		List<PCB> PCBs = new ArrayList<>();
    		//执行作业队列
    		List<PCB> execPCBs = new ArrayList<>();
    		//作业信息初始化
    		do {
    			PCB pcb = new PCB();
    			PCB initPCB = DynamicJobFirstUtil.init(pcb);
    			PCBs.add(initPCB);
    			System.out.println("是否要继续输入作业相关信息：（是输入yes，否输入no）");
    		} while (scanner.nextLine().equalsIgnoreCase("yes"));
    		System.out.println("-----------------");
    		//确认初始化成功
    		for (PCB pcb : PCBs) {
    			System.out.println(pcb.toString());
    		}
    
    
    		//执行调度算法，将输入队列作业按照算法，插入到执行队列中
    		execPCBs = DynamicJobFirstUtil.dispatchpcb(PCBs, execPCBs);
    		System.out.println("-----------------");
    
    		//求出周转时间和平均周转时间并记录在每一个作业实体中
    		DynamicJobFirstUtil.turnRoundTime(execPCBs);
    		for (PCB PCB : execPCBs) {
    			System.out.println(PCB.toString());
    		}
    
    		System.out.println("-----------------");
    		DynamicJobFirstUtil.showTime(execPCBs);
    	}
    }

### 2.3工具类DynamicJobFirstUtil。 ###

调度算法的工具类，方法有

1.进程初始化  init()

2.按照服务时间去排序 sortByServerTime()

3.按照到达时间去排序 sortByArrivalTime()

4. 先按照优先度排序，优先度相同的按照到达时间去排序 sortByStateAndArrivalTime()。

4.调度算法函数，最终将需要按顺序执行的进程放入execJobs中dispatchJob()。

5.求出周转时间,平均周转时间等其他信息 turnRoundTime()。

package cn.zzuli.edu.dynamic;
    
    
    import java.text.SimpleDateFormat;
    import java.util.*;
    
    /**
     * 动态高优先权优先调度算法工具类
     * @author MMMMM
     *
     */
    public class DynamicJobFirstUtil {
        private  static SimpleDateFormat tm= new SimpleDateFormat("HH:mm:ss");
    	//进程初始化
    	@SuppressWarnings("resource")
    	public static PCB init(PCB pcb) {
    		Scanner scanner = new Scanner(System.in);
    		System.out.println("请输入进程名称：如（进程1）");
    		pcb.setPcbName(scanner.nextLine());
    		System.out.println("请输入进程到达时间：如（1）");
            pcb.setPcbArrivalTime(scanner.nextInt());
    		System.out.println("请输入进程服务时间：如（3）");
            pcb.setPcbServiceTime(scanner.nextInt());
            System.out.println("请输入进程初始优先权：如（1）");
            pcb.setFirstNum(scanner.nextInt());
            pcb.setPcbState('w');
    		return pcb;
    	}
    
    	//按照服务时间去排序
    	public static void sortByServerTime(List<PCB> pcbs){
    	    //使用Collections工具类中的自定义条件排序方法
    		Collections.sort(pcbs , new Comparator<PCB>() {
                @Override
                public int compare(PCB pcb1, PCB pcb2) {
                    return (int) (pcb1.getPcbServiceTime() - pcb2.getPcbServiceTime());
                }
            });
    	}
        //按照到达时间去排序
        public static void sortByArrivalTime(List<PCB> pcbs){
            //使用Collections工具类中的自定义条件排序方法
            Collections.sort(pcbs , new Comparator<PCB>() {
                @Override
                public int compare(PCB pcb1, PCB pcb2) {
                    return (int) (pcb1.getPcbArrivalTime() - pcb2.getPcbArrivalTime());
                }
            });
        }
        //先按照优先度排序，优先度相同的按照到达时间去排序
        public static void sortByStateAndArrivalTime(List<PCB> pcbs){
            //使用Collections工具类中的自定义条件排序方法
            Collections.sort(pcbs , new Comparator<PCB>() {
                @Override
                public int compare(PCB pcb1, PCB pcb2) {
                    int cr = 0;
                    //先按优先级排降序
                    int a = pcb1.getFirstNum() - pcb2.getFirstNum();
                    if (a != 0) {
                        cr = (a < 0) ? 3 : -1;
                    } else {
                        //再按到达时间排升序
                        a =  pcb1.getPcbArrivalTime() - pcb2.getPcbArrivalTime();
                        if (a != 0) {
                            cr = (a > 0) ? 2 : -2;
                        }
                    }
                    return cr;
                }
            });
        }
    
    	//调度算法函数，最终将需要按顺序执行的进程放入execpcbs中
        //pcbs，输入队列，
        //execpcbs，执行队列
        public static List<PCB> dispatchpcb(List<PCB> pcbs,List<PCB> execpcbs){
    	    //中间队列，暂存从输入队列中挑选出的进程
            List<PCB> temppcbs = new ArrayList<>();
            //cpu无工作时，第一个到达的进程先服务，结束时间前到达的进程在执行
            DynamicJobFirstUtil.sortByArrivalTime(pcbs);
            execpcbs.add(pcbs.get(0));
            pcbs.remove(pcbs.get(0));
            //将输入队列中的进程一个一个的移动到执行队列中
            while (pcbs.size()>0) {
                //execpcbs队列的最后一个exexpcb的结束时间
                PCB exexpcb = execpcbs.get((execpcbs.size() - 1));
                int endTime = exexpcb.getPcbArrivalTime() + exexpcb.getPcbServiceTime();
                //使用迭代器，便于输入队列的删除，不会出错
                Iterator<PCB> iterator = pcbs.iterator();
                //迭代判断
                while (iterator.hasNext()){
                    PCB pcb = iterator.next();
                    //将执行队列中的结束时间大于输入队列的到达时间的所有进程移动到执行队列
                    if (endTime >= pcb.getPcbArrivalTime()) {
                        temppcbs.add(pcb);
                        iterator.remove();
                    }
                }
                //若遍历后，执行队列结束时间还没有进程到达，则按照到达时间排序得到第一个
                if (temppcbs==null){
                    DynamicJobFirstUtil.sortByArrivalTime(pcbs);
                    execpcbs.add(pcbs.get(0));
                    pcbs.remove(pcbs.get(0));
                }
                //按照服务时间长短进行排序，便于下面移动到执行队列的进程的顺序不出错
                DynamicJobFirstUtil.sortByStateAndArrivalTime(temppcbs);
                execpcbs.addAll(temppcbs);
                temppcbs.clear();
            }
            for (PCB pcb : execpcbs){
                pcb.setPcbState('r');
            }
    	    return execpcbs;
        }
    
        //求出周转时间,平均周转时间等其他信息
        public static void turnRoundTime(List<PCB> pcbs){
    	    //第一个的到达时间
            int temp = pcbs.get(0).getPcbArrivalTime();
            for (PCB pcb : pcbs){
                //如果前一个进程的结束时间小于当前进程的到达时间
                if (temp < pcb.getPcbArrivalTime()){
                    temp = pcb.getPcbArrivalTime();
                }
                //设置进程的开始时间.前一个的结束时间等于本次的开始时间
                pcb.setPcbStartTime(temp);
                //得到每个进程的服务时间
                int serviceTime = pcb.getPcbServiceTime();
                temp+=serviceTime;
                //结束时间=开始时间+服务时间
                pcb.setPcbOverTime(temp);
                //周转时间=结束时间-到达时间
                int turnRound = temp-pcb.getPcbArrivalTime();
                pcb.setPcbRoundTime(turnRound);
                //带权周转时间=周转时间/服务时间
                pcb.setPcbAvgRoundTime((1.0*turnRound)/serviceTime);
            }
        }
    
        //输出进程运行时间
        public static void showTime(List<PCB> pcbs){
    	    System.out.println("进程名称\t\t到达时间\t\t服务时间\t\t开始时间\t\t优先级\t\t状态\t\t结束时间\t\t周转时间\t\t带权周转时间");
    	    double turnRound = 0.0;
    	    double avgTurnRound = 0.0;
            for (PCB pcb : pcbs){
                System.out.println(pcb.getPcbName()+"\t\t\t"+pcb.getPcbArrivalTime()+"\t\t\t"+pcb.getPcbServiceTime()
                        +"\t\t\t"+pcb.getPcbStartTime()+"\t\t\t"+pcb.getFirstNum()+"\t\t\t"+pcb.getPcbState()+"\t\t\t"+pcb.getPcbOverTime()+"\t\t\t"+pcb.getPcbRoundTime()
                        +"\t\t\t"+pcb.getPcbAvgRoundTime());
                turnRound+=pcb.getPcbRoundTime();
                avgTurnRound+=pcb.getPcbAvgRoundTime();
            }
            System.out.println(pcbs.size()+"个进程的平均周转时间为："+String.format("%g %n",(1.0*turnRound)/pcbs.size()));
            System.out.println(pcbs.size()+"个进程的平均带权周转时间为："+String.format("%g %n",(1.0*avgTurnRound)/pcbs.size()));
        }
    
    
    }

# #

##   3、算法执行结果 ##

算法最后应该有的结果。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lpaWlpaWxpa2FuZ3NodWFp_size_16_color_FFFFFF_t_70][]

最终输出情况

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lpaWlpaWxpa2FuZ3NodWFp_size_16_color_FFFFFF_t_70 1][]

[Link 1]: https://baike.baidu.com/item/%E7%B3%BB%E7%BB%9F
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lpaWlpaWxpa2FuZ3NodWFp_size_16_color_FFFFFF_t_70]: /images/20220220/faac47299be74f49a978644e66628c78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lpaWlpaWxpa2FuZ3NodWFp_size_16_color_FFFFFF_t_70 1]: /images/20220220/71b871c2713747ab88090e8bdb825c09.png