Preemptive Scheduling

Few days before, I was attending one programming contest, where I had to write Preemptive Scheduling programming for the set of process. I completed that solution but something was missing there so I did not got full marks. But later I found the solution in Infosys, Campusconnect web site. Which had provided the same solution as pdf format. So I would like to provide the same solution here in my blog too.

Question goes like this:

Write a program to return the waiting time of the process based on the arrival time and burst time under preemptive scheduling.

And some constraint has been given:

  • The arrival time of the first process should be started with 0, it never contain duplicate, the current process arrival time should be greater than previous process else return {0}.
  • The burst time should be greater than 0 and less than 10 else return {0}.

Solution goes like this:

/**
 *
 * @author Prashant
 */

public class PreemptiveSchedule {
    public int[] getWaitingList(int[] process, int[] arrival, int[] burst)
    {
        if (arrival[0] != 0)
        return new int[]{0};
        for (int i = 0; i < arrival.length; i++) {
            for (int j = i + 1; j < arrival.length; j++) {
                if (arrival[i] == arrival[j]) {
                    return new int[]{0};
                }
                else if (arrival[i] > arrival[j]) {
                   return new int[]{0};
                }
            }
        }
        for (int i = 0; i < burst.length; i++) {
            if (burst[i] <= 0)
                return new int[]{0};
            else if (burst[i] >= 10)
                return new int[]{0};
            }
            int[] waitingTime = new int[process.length];
            int[] bTime = new int[process.length];
            int arrTime = arrival[0];
            for(int i=0;i<process.length;i++){
                waitingTime[i] = 0;
                bTime[i] = burst[i];
                if(arrival[i] < arrTime) arrTime = arrival[i];
            }
            while(true){
                int[] val = new int[process.length];
                int nValues = 0;
                for(int i=0;i<process.length;i++){
                    if(arrTime >= arrival[i] && burst[i] > 0){
                        val[nValues++] = process[i]-1;
                    }
                }
                boolean exitFlag = true;
                for(int i=0;i<process.length;i++){
                    if(burst[i] != 0) {
                        exitFlag = false;
                        break;
                    }
                }
                if(exitFlag) break;
                if(nValues > 0){
                    int selected = val[0];
                    for(int i=1;i<nValues;i++){
                        if(burst[val[i]] < burst[selected])
                            selected = val[i];
                    }
                    burst[selected]--;
                if(burst[selected] == 0) {
                    waitingTime[selected] = (arrTime -(bTime[selected] + arrival[selected]))+1;
                }
            }
            arrTime++;
        }
        return waitingTime;
    }
    public static void main(String[] args)
    {
        //testcase 1:
        try {
            int[] process = {1, 2, 3, 4};
            int[] arrival = {0, 2, 4, 5};
            int[] burst = {7, 4, 1, 4};
            int[] output = new PreemptiveSchedule().getWaitingList(process, arrival, burst);
            for (int i = 0; i < output.length; i++) {
                System.out.print(output[i]+ " - ");
            }
        }
        catch (Exception e) {
        e.printStackTrace();
        }

    }
}

Output:
9 – 1 – 0 – 2 –

The process 1 has been entered the CPU first at the time of 2, process 2 has been entered and the burst time is less than of process 1’s burst time so process 1 is interrupted and process 2 holds the CPU, at the time of 4 process 3 has been entered and the burst time is less than previous two processes so it holds the CPU by interrupting process 2, at the time 5 process 3 gets over and process 2 holds the CPU which has lower burst time than all other process, keeps on interrupt and allocate until all the process got over. Finally, the waiting time of the process is as output.