短作业优先调度算法（sjf）java实现

妖狐艹你老母 2022-02-26 03:42 349阅读 0赞

**目录**

短作业（进程）优先调度算法：

1.作业类job

2.sjf主方法类shortJobFirst

3.sjf工具类shortJobFirstUtil。

4.运行结果

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

# 短作业（进程）优先调度算法： #

是指对短作业（进程）优先调度的算法。短作业优先(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。

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

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

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

<table>  短作业优先调度算法  
 <tbody> 
  <tr> 
   <td>作业名称</td> 
   <td>到达时间</td> 
   <td>服务时间</td> 
   <td>开始时间</td> 
   <td>结束时间</td> 
   <td>周转时间</td> 
   <td>带权周转时间</td> 
  </tr> 
  <tr> 
   <td>作业1</td> 
   <td>2</td> 
   <td>50</td> 
   <td>2</td> 
   <td>52</td> 
   <td>50</td> 
   <td>1.0</td> 
  </tr> 
  <tr> 
   <td>作业2</td> 
   <td>8</td> 
   <td>2</td> 
   <td>52</td> 
   <td>54</td> 
   <td>46</td> 
   <td>23.0</td> 
  </tr> 
  <tr> 
   <td>作业3</td> 
   <td>6</td> 
   <td>5</td> 
   <td>54</td> 
   <td>59</td> 
   <td>53</td> 
   <td>10.6</td> 
  </tr> 
 </tbody> 
</table>

3个作业的平均周转时间为：49.6667

3个作业的平均带权周转时间为：11.5333

类似于这样的算法。

首先，我先定义三个类，作业类job，sjf主方法类shortJobFirst，sjf工具类shortJobFirstUtil。

代码如下

## 1.作业类job ##

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

package cn.zzuli.edu;
    
    /**
     * 作业类，封装作业属性和方法
     * @author MMMMM
     *
     */
    public class Job {
    
    	//作业名
    	private String jobName;
    	//作业到达时间
    	private int jobArrivalTime;
    	//作业服务时间
    	private int jobServiceTime;
    	//下一个作业的链接
    	private Job lastJob;
    	
    	//作业开始时间
    	private int jobStartTime;
    	//作业完成时间
    	private int jobOverTime;
    	//作业周转时间
    	private int jobRoundTime;
    	//作业带权周转时间
    	private double jobAvgRoundTime;
    
    	//get和set方法
    	public String getJobName() {
    		return jobName;
    	}
    	public void setJobName(String jobName) {
    		this.jobName = jobName;
    	}
    	public int getJobArrivalTime() {
    		return jobArrivalTime;
    	}
    	public void setJobArrivalTime(int jobArrivalTime) {
    		this.jobArrivalTime = jobArrivalTime;
    	}
    	public int getJobServiceTime() {
    		return jobServiceTime;
    	}
    	public void setJobServiceTime(int jobServiceTime) {
    		this.jobServiceTime = jobServiceTime;
    	}
    	public Job getLastJob() {
    		return lastJob;
    	}
    	public void setLastJob(Job lastJob) {
    		this.lastJob = lastJob;
    	}
    	public int getJobOverTime() {
    		return jobOverTime;
    	}
    	public void setJobOverTime(int jobOverTime) {
    		this.jobOverTime = jobOverTime;
    	}
    	public int getJobRoundTime() {
    		return jobRoundTime;
    	}
    	public void setJobRoundTime(int jobRoundTime) {
    		this.jobRoundTime = jobRoundTime;
    	}
    
    	public int getJobStartTime() {
    		return jobStartTime;
    	}
    
    	public void setJobStartTime(int jobStartTime) {
    		this.jobStartTime = jobStartTime;
    	}
    
    	public double getJobAvgRoundTime() {
    		return jobAvgRoundTime;
    	}
    
    	public void setJobAvgRoundTime(double jobAvgRoundTime) {
    		this.jobAvgRoundTime = jobAvgRoundTime;
    	}
    
    	@Override
    	public String toString() {
    		return "Job{" +
    				"jobName='" + jobName + '\'' +
    				", jobArrivalTime=" + jobArrivalTime +
    				", jobServiceTime=" + jobServiceTime +
    				", lastJob=" + lastJob +
    				", jobStartTime=" + jobStartTime +
    				", jobOverTime=" + jobOverTime +
    				", jobRoundTime=" + jobRoundTime +
    				", jobAvgRoundTime=" + jobAvgRoundTime +
    				'}';
    	}
    }

## 2.sjf主方法类shortJobFirst ##

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

sjf方法中，需要首先

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

2.再对作业进行模拟程序执行运行时间，

3.执行调度算法，将输入队列作业按照sjf算法，插入到执行队列中

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

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

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

## 3.sjf工具类shortJobFirstUtil。 ##

sjf的工具类，方法有

1.作业初始化  init()

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

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

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

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

package cn.zzuli.edu;
    
    import java.text.SimpleDateFormat;
    import java.util.*;
    
    /**
     * 短作业优先调度算法工具类
     * @author MMMMM
     *
     */
    public class ShortJobFirstUtil {
        private  static SimpleDateFormat tm= new SimpleDateFormat("HH:mm:ss");
    	//作业初始化
    	@SuppressWarnings("resource")
    	public static Job init(Job job) {
    		Scanner scanner = new Scanner(System.in);
    		System.out.println("请输入作业名称：如（作业1）");
    		job.setJobName(scanner.nextLine());
    		System.out.println("请输入作业到达时间：如（1）");
    		job.setJobArrivalTime(scanner.nextInt());
    		System.out.println("请输入作业服务时间：如（3）");
    		job.setJobServiceTime(scanner.nextInt());
    		return job;
    	}
    
    	//按照服务时间去排序
    	public static void sortByServerTime(List<Job> jobs){
    	    //使用Collections工具类中的自定义条件排序方法
    		Collections.sort(jobs , new Comparator<Job>() {
                @Override
                public int compare(Job job1, Job job2) {
                    return (int) (job1.getJobServiceTime() - job2.getJobServiceTime());
                }
            });
    	}
        //按照到达时间去排序
        public static void sortByArrivalTime(List<Job> jobs){
            //使用Collections工具类中的自定义条件排序方法
            Collections.sort(jobs , new Comparator<Job>() {
                @Override
                public int compare(Job job1, Job job2) {
                    return (int) (job1.getJobArrivalTime() - job2.getJobArrivalTime());
                }
            });
        }
    
    	//调度算法函数，最终将需要按顺序执行的作业放入execJobs中
        //jobs，输入队列，
        //execJobs，执行队列
        public static List<Job> dispatchJob(List<Job> jobs,List<Job> execJobs){
    	    //中间队列，暂存从输入队列中挑选出的作业
            List<Job> tempJobs = new ArrayList<>();
            //cpu无工作时，第一个到达的作业先服务，结束时间前到达的作业在执行
            ShortJobFirstUtil.sortByArrivalTime(jobs);
            execJobs.add(jobs.get(0));
            jobs.remove(jobs.get(0));
            //将输入队列中的作业一个一个的移动到执行队列中
            while (jobs.size()>0) {
                //execJobs队列的最后一个exexJob的结束时间
                Job exexJob = execJobs.get((execJobs.size() - 1));
                int endTime = exexJob.getJobArrivalTime() + exexJob.getJobServiceTime();
                //使用迭代器，便于输入队列的删除，不会出错
                Iterator<Job> iterator = jobs.iterator();
                //迭代判断
                while (iterator.hasNext()){
                    Job job = iterator.next();
                    //将执行队列中的结束时间大于输入队列的到达时间的所有作业移动到执行队列
                    if (endTime >= job.getJobArrivalTime()) {
                        tempJobs.add(job);
                        iterator.remove();
                    }
                }
                //若遍历后，执行队列结束时间还没有作业到达，则按照到达时间排序得到第一个
                if (tempJobs==null){
                    ShortJobFirstUtil.sortByArrivalTime(jobs);
                    execJobs.add(jobs.get(0));
                    jobs.remove(jobs.get(0));
                }
                //按照服务时间长短进行排序，便于下面移动到执行队列的作业的顺序不出错
                ShortJobFirstUtil.sortByServerTime(tempJobs);
                execJobs.addAll(tempJobs);
                tempJobs.clear();
            }
    	    return execJobs;
        }
    
        //求出周转时间,平均周转时间等其他信息
        public static void turnRoundTime(List<Job> jobs){
    	    //第一个的到达时间
            int temp = jobs.get(0).getJobArrivalTime();
            for (Job job : jobs){
                //如果前一个作业的结束时间小于当前作业的到达时间
                if (temp < job.getJobArrivalTime()){
                    temp = job.getJobArrivalTime();
                }
                //设置作业的开始时间.前一个的结束时间等于本次的开始时间
                job.setJobStartTime(temp);
                //得到每个作业的服务时间
                int serviceTime = job.getJobServiceTime();
                temp+=serviceTime;
                //结束时间=开始时间+服务时间
                job.setJobOverTime(temp);
                //周转时间=结束时间-到达时间
                int turnRound = temp-job.getJobArrivalTime();
                job.setJobRoundTime(turnRound);
                //带权周转时间=周转时间/服务时间
                job.setJobAvgRoundTime((1.0*turnRound)/serviceTime);
            }
        }
    
        //输出作业运行时间
        public static void showTime(List<Job> jobs){
    	    System.out.println("作业名称\t\t到达时间\t\t服务时间\t\t开始时间\t\t结束时间\t\t周转时间\t\t带权周转时间");
    	    double turnRound = 0.0;
    	    double avgTurnRound = 0.0;
            for (Job job : jobs){
                System.out.println("\t"+job.getJobName()+"\t\t\t"+job.getJobArrivalTime()+"\t\t\t"+job.getJobServiceTime()
                        +"\t\t\t"+job.getJobStartTime()+"\t\t\t"+job.getJobOverTime()+"\t\t\t"+job.getJobRoundTime()
                        +"\t\t\t"+job.getJobAvgRoundTime());
                turnRound+=job.getJobRoundTime();
                avgTurnRound+=job.getJobAvgRoundTime();
            }
            System.out.println(jobs.size()+"个作业的平均周转时间为："+String.format("%g %n",(1.0*turnRound)/jobs.size()));
            System.out.println(jobs.size()+"个作业的平均带权周转时间为："+String.format("%g %n",(1.0*avgTurnRound)/jobs.size()));
        }
    
        //模拟作业到达时间的过程
        public static void sleepJob(List<Job> jobs){
            long l = System.currentTimeMillis();
            ShortJobFirstUtil.sortByArrivalTime(jobs);
            for (Job job : jobs){
                try {
                    Thread.sleep(job.getJobArrivalTime()*1000);
                    System.out.print("作业执行情况为："+job.getJobName()+"在"+tm.format(new Date())+"到达！");
                    Thread.sleep(job.getJobServiceTime()*1000);
                    System.out.println("---在"+tm.format(new Date())+"结束作业！");
                } catch (InterruptedException e) {
                    System.out.println("系统出错！！请退出重试！！！");
                }
            }
        }
    
    }

## 4.运行结果 ##

D:\Java\jdk1.7.0_07\bin\java "-javaagent:D:\idea\IntelliJ IDEA 
    短作业优先调度算法（sjf）开始：
    请先输入作业的相关信息：（输入no代表结束）
    请输入作业名称：如（作业1）
    作业1
    请输入作业到达时间：如（1）
    2
    请输入作业服务时间：如（3）
    50
    是否要继续输入作业相关信息：（是输入yes，否输入no）
    yes
    请输入作业名称：如（作业1）
    作业2
    请输入作业到达时间：如（1）
    6
    请输入作业服务时间：如（3）
    5
    是否要继续输入作业相关信息：（是输入yes，否输入no）
    yes
    请输入作业名称：如（作业1）
    作业3
    请输入作业到达时间：如（1）
    8
    请输入作业服务时间：如（3）
    2
    是否要继续输入作业相关信息：（是输入yes，否输入no）
    no
    作业名称为：作业1在17:57:33到达！---在17:58:23结束作业
    作业名称为：作业2在17:58:29到达！---在17:58:34结束作业
    作业名称为：作业3在17:58:42到达！---在17:58:44结束作业
    -----------------
    -----------------
    Job{jobName='作业1', jobArrivalTime=2, jobServiceTime=50, lastJob=null, jobStartTime=2, jobOverTime=52, jobRoundTime=50, jobAvgRoundTime=1.0}
    Job{jobName='作业3', jobArrivalTime=8, jobServiceTime=2, lastJob=null, jobStartTime=52, jobOverTime=54, jobRoundTime=46, jobAvgRoundTime=23.0}
    Job{jobName='作业2', jobArrivalTime=6, jobServiceTime=5, lastJob=null, jobStartTime=54, jobOverTime=59, jobRoundTime=53, jobAvgRoundTime=10.6}
    -----------------
    作业名称		到达时间		服务时间		开始时间		结束时间		周转时间		带权周转时间
    	作业1			2			50			2			52			50			1.0
    	作业3			8			2			52			54			46			23.0
    	作业2			6			5			54			59			53			10.6
    3个作业的平均周转时间为：49.6667 
    
    3个作业的平均带权周转时间为：11.5333