2

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

假设作业的到达时间以 2 个单位为间隔，例如 0、2、4、6...... 即，第 1 个作业以 0 个单位进入，第 2 个作业在 2 个单位时间后进入，依此类推。

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

测试用例 1：
jobs:8,4,9,5
avg Time:6.5

测试用例 2：
jobs:7,4,1,4
avg Time:3

但是当我将一个包含 1000 个工作的文件作为输入时，我得到了 avg Time:16872.434 但是我从互联网上得到的代码给了我答案 avg Time : 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中，提前谢谢！

4

1 回答 1

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);
    }


}

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

我希望这有帮助。

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

最短作业优先调度

于 2014-03-13T21:48:54.677 回答