計算搶先式最短作業優先調度算法的平均等待時間

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


} 

始終separete測試用例從您的代碼。

我希望這會有所幫助。

我相信你從這裏得到的例子：

Shortest-Job-First Scheduling