抢占最短作业优先调度算法的平均等待时间计算

Question

我的目标是计算抢占最短作业优先调度算法的平均等待时间。

假设作业的到达时间以2个单位为间隔，如0,2,4,6……即，第一个作业以0个单位进入，第二个作业在2个单位的时间后进入，以此类推。

我为我的程序测试了 3 个测试用例并得到了正确答案：

测试用例1：
作业：8,4,9,5
平均时间：6.5

测试用例2：
作业：7,4,1,4
平均时间：3

但是当我把一个有1000个作业的文件作为输入时，我得到的平均时间是:16872.434，但是我从互联网上得到的代码给我的答案是平均时间:16024，我不明白如何在这里附加那个文本文件...所以，我只想知道我的代码对不对？如果不是，我哪里错了。？

package algoritm_W4_M6;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;
/**
 * To calculate the average Waiting Time of jobs when done in shortest Job First(SJF)-Preemptive
 * @author Rahul Konda
 *
 */
public class Preemptivr_SJV {
    Vector<Float> burstTimes ;
    public Preemptivr_SJV() {
        burstTimes = new Vector<Float>();
    }
    public void loadFile() {
        try {
            float f;
            Scanner scan = new Scanner(new FileInputStream("cpu_burst_times.txt"));
            while(scan.hasNext()) {
                f = Float.parseFloat( scan.nextLine());             
                burstTimes.add(f);
            }
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
    public void readc() {
        burstTimes.add((float) 7);
        burstTimes.add((float) 4);
        burstTimes.add((float) 1);
    //  burstTimes.add((float) 8);
        burstTimes.add((float) 4);
    //  burstTimes.add((float) 2);
    }
    public float calculateAvgWaitingTime() {
//      readc(); //this is for test cases 1 and 2
        loadFile(); //this is to read from file
        float waitingTime= 0.0f;
        float totalTime = 0.0f;

        PriorityQueue<Float> pq = new PriorityQueue<Float>();

        for (Float time : burstTimes) {
            pq.add(time);
            Float minTime = pq.poll();
            if(time<=2) {
                waitingTime = waitingTime +(minTime*pq.size());
                continue;
            }
            waitingTime = waitingTime +2*pq.size();
            pq.add(minTime-2);//as job not completed I add back to queue
        }
        totalTime = totalTime + waitingTime;    //summing up the above waiting times
        waitingTime = 0.0f;
        while(!pq.isEmpty()) {
            waitingTime = waitingTime +pq.poll();
            totalTime = totalTime + waitingTime;    //summing up the above waiting times
        }

        totalTime = totalTime - waitingTime;
        System.out.println("Jobs burst values:\n"+burstTimes.toString());
        return (totalTime/1000);



    }
    public static void main(String[] args) {
        Preemptivr_SJV fs = new Preemptivr_SJV();
        System.out.println("\nAverage Waiting Time is: "+fs.calculateAvgWaitingTime());
    }
}

以上代码是用java编写的，请提前感谢。！

Answer 1

如果作业分别在时间0、1、2、3到达，测试用例1的平均时间是正确的。

您需要一种方法来指定这些到达时间或在添加新流程时逐步计时。

这是一个抢占最短作业优先调度的工作实现：

import java.util.PriorityQueue;


public class PreemptiveSJF {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    private int waiting = 0;
    private int numberOfProcesses = 0;

    public void addProcess(int time) {
        numberOfProcesses ++;
        pq.add(time);
    }

    public float getAverageWaitingTime() {
        while (pq.size() > 1) {
            stepTime(1);
        }

        return (float)waiting / numberOfProcesses;
    }

    public void stepTime(int timeStep) {
        int time = pq.poll();
        if (time <= timeStep) {
            waiting = waiting + time * pq.size();
        } else {
            waiting = waiting + timeStep * pq.size();
            time = time - timeStep;
            pq.add(time);
        }
    }
}

以下是测试用例：

import static org.junit.Assert.*;

import org.junit.Test;


public class PreemptiveSJFTest {

    @Test
    public void test1() {
        PreemptiveSJF psjf = new PreemptiveSJF();
        psjf.addProcess(6);
        psjf.addProcess(8);
        psjf.addProcess(7);
        psjf.addProcess(3);
        assertEquals(7, psjf.getAverageWaitingTime(), 0.000001);
    }

    @Test
    public void test2() {
        PreemptiveSJF psjf = new PreemptiveSJF();
        psjf.addProcess(8);
        psjf.stepTime(1);
        psjf.addProcess(4);
        psjf.stepTime(1);
        psjf.addProcess(9);
        psjf.stepTime(1);
        psjf.addProcess(5);
        assertEquals(6.5f, psjf.getAverageWaitingTime(), 0.000001);
    }

    @Test
    public void test3() {
        PreemptiveSJF psjf = new PreemptiveSJF();
        psjf.addProcess(7);
        psjf.stepTime(2);
        psjf.addProcess(4);
        psjf.stepTime(2);
        psjf.addProcess(1);
        psjf.stepTime(1);
        psjf.addProcess(4);
        assertEquals(3f, psjf.getAverageWaitingTime(), 0.000001);
    }


}

始终将测试用例与代码分开。

我希望这有所帮助。

我相信你从这里得到了例子：

最短作业优先调度