Processes Scheduling by shortest job first (SJF)

Question

I'm trying to code a CPU Scheduling Simulator in java. The processes are processed in an order such that the process with the least burst time (Processing Time) should be processed first. before beginning I enter all the processes in an ArrayList specifying a name , burst Time & arrival Time. The code works logically fine if all the processes enters at the same time.

The problem is that the processes have different arrival times. how can I edit the code to take this arrival time in consideration.

I just need to edit the part of code that gets me the Process with the least burst time (with respect to arrival time)

public Process removeSJ(){  // removes & returns the process with the min. burst time
int minBurstTime = processes.get(0).getBurstTime(); // processes is ArrayList of Processe objects
int minIndex = 0;
for (int i=1 ; i<processes.size(); i++){
    int curBurstTime = processes.get(i).getBurstTime();
    if ( (curBurstTime < minBurstTime)){
        minBurstTime = curBurstTime;
        minIndex = i;
    }
}
numberOfProcesses--;
return (processes.remove(minIndex));}

sample output

The processor schedules process : P2
arrival time = 8 , burst time = 1 , waiting Time = 0
Turnaround time = 1
The processor schedules process : P3
arrival time = 5 , burst time = 3 , waiting Time = 1
Turnaround time = 4
The processor schedules process : P1
arrival time = 1 , burst time = 9 , waiting Time = 4
Turnaround time = 13
****** Average Turnaround Time = 6 ******

ajb ajb · Accepted Answer · 2016-12-04T01:46:47

Instead of simply searching for the smallest burst time, you'll also need to search for the nearest available time. To do this, you'll have to keep track of the "next time the processor is available", nextAvailableTime. Since the processor is free when you start, you can start with nextAvailableTime = 0.

Then:

Look for the processes with the smallest (nearest) arrival time. You will find all processes that share that arrival time. But if there are any processes with arrival time <= nextAvailableTime, then choose all of them. In this case, it doesn't matter which arrival time is earliest, since any process with arrival time <= nextAvailableTime will have to wait for the processor to become available anyway.
Whichever set of processes you select, find the one with the smallest burst time.
Schedule that process. The process will start at either its arrival time or at nextAvailableTime. Add the burst time to the start time, and that will be the new nextAvailableTime.

The way this would work in your small example:

There's a process with arrival time 1, and no other processes arriving at the same time, so you'd schedule that. That means the next available time will be 10.
Since the processor will become available at time 10, there will now be two processes waiting, with arrival times 5 and 8. Choose the one with the smallest burst time, P2. That will finish at time 10 + 1 = 11, which will be the next available time.
Now there's only one process left, P3. Its arrival time is 5, so it will be waiting. Schedule it.

Note: My first answer involved setting up an "event queue" which is a list, ordered by time, of events that the simulator would need to be aware of. In this case, the events would be processes arriving, and processes completing. That's a bit more complex a solution than you need for this problem. But it's a more general solution. If you started adding more factors, such as multiple processes or some processes that have urgent priority that must be scheduled ASAP, the simple solution I outlined probably wouldn't be good enough.

Processes Scheduling by shortest job first (SJF)

1 Answers