2

私の目標は、プリエンプティブな最短ジョブ優先スケジューリング アルゴリズムの平均待機時間を計算することです。

ジョブの到着時間は、0、2、4、6 のように 2 単位の間隔であると仮定します。つまり、最初のジョブは 0 単位で入力され、2 番目のジョブは 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であり、事前に感謝します.!

4

1 に答える 1

1

ジョブがそれぞれ時刻 0、1、2、3 に到着する場合、テスト ケース 1 の平均時間は正確です。

これらの到着時刻を指定する方法、または新しいプロセスを追加するときに時間をステップする方法が必要です。

これは、Preemptive Shortest Job First Scheduling の実用的な実装です。

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 に答える