calculate average waiting time for a preemptive shortest job first scheduling algorithm

Question

My target is to calculate average waiting time for a preemptive shortest job first scheduling algorithm.

Assume the arrival times for the jobs are in intervals of 2 units, like 0,2,4,6..... Ie, 1st job enters in 0 units and 2nd job after 2 units of time and so on.

I tested for 3 test cases for my program and got right answers:

Test case 1:
jobs:8,4,9,5
avg Time:6.5

Test case 2:
jobs:7,4,1,4
avg Time:3

But when I took a file having 1000 jobs as input I got avg Time:16872.434 But the code i got from internet gave me answer as avg Time : 16024 I didn`t understand how to attach that text file here... so, I just want to know if my code is right? if not where did I go wrong.?

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

The above code is in java and thanks in advance.!

Answer 1

The average time for test case 1 is correct if the jobs arrive respectively at times 0,1,2,3.

You need a way to specify those arriving times or to step time as you add new processes.

Here is a working implementation a 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);
        }
    }
}

And here are the test cases:

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


}

Always separete test cases from your code.

I hope this helps.

I believe you got examples from here:

Shortest-Job-First Scheduling