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.

Advertisements

One Response to Preemptive Scheduling

  1. Hmm is anyone else encountering problems with the
    pictures on this blog loading? I’m trying to determine if its a problem on my end or if it’s the blog.

    Any responses would be greatly appreciated.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: