Shortest Job First (Non preemptive) - Sort bursting time and arrival time simultaneously

Question

I am having a problem on how to sort the arrival time and burst time simultaneously. My code first checks the lower burst time and then checks the arrival time.

Shortest Job First (Non preemptive) CPU Scheduling checks the process burst time and if it the Process has the lowest Bursting Time and Arrival time then it will be executed.

Here's my snippet code for sorting the array:

inputs.sort((a1, a2) => (a1.burst < a2.burst) ? 1 : (a1.burst < a2.burst) ? 1 : -1);

and here's the result of the snippet code above:

This should be the output if the sorting formula is right:

Reference: Shortest Job First (SJF)

The logic is not clear. Can you explain how the sorting is supposed to happen? — HymnZzy
arrange them by two factors: first is arrival time and / or burst time.. if arrival time is lower than the other arrival time then that process is the first. if the burst time is lower than the other burst time then that process will be the first. — Denzell

Trentium Trentium · Accepted Answer · 2020-09-20T23:36:04

This appears to require iterating to determine the sequence of processes, as the finish time of the current process being "executed" is used to determine the available processes to consider executing next. That is, in your example P1 arrives at 0 and finishes at time interval of 5. Thus, all processes not finished that have arrived before time interval of 5 are now candidate processes to execute. The candidate with the minimal burst time is executed next, with arrival time being the tie breaker. (Note that this tie breaker simply assumes that the array is sorted by arrival time.)

let process = [
  { Process: 'P1', ArrivalTime: 0, BurstTime: 5 },
  { Process: 'P2', ArrivalTime: 1, BurstTime: 3 },
  { Process: 'P3', ArrivalTime: 2, BurstTime: 8 },
  { Process: 'P4', ArrivalTime: 2, BurstTime: 6 },
  { Process: 'P5', ArrivalTime: 3, BurstTime: 3 },
  { Process: 'P6', ArrivalTime: 15, BurstTime: 2 },
];

// Get the first ArrivalTime.
let time = Math.min( ...process.map( p => p.ArrivalTime ) );

while ( process.find( p => p.Finished == null ) ) {

  // Now, "execute" the process in which the BurstTime is the least
  // amoung the processes which haven't finished and have an ArrivalTime
  // less than or equal to the current time...
  let execute = process.reduce( ( ni, p, i ) => {
    if ( p.Finished == null && p.ArrivalTime <= time && (ni === -1 || p.BurstTime < process[ ni ].BurstTime ) ) {
      ni = i;
    }
    return ni;
  }, -1 );
  
  // Capture the start time...
  process[ execute ].Started = time;
  // ...and then calculate the finish time.
  time += process[ execute ].BurstTime;
  process[ execute ].Finished = time;

}

// For ease of viewing, sort by Started.
process.sort( ( a, b ) => a.Started - b.Started );

console.log( process );

I slipped in a few extra data points, and notice how P6 is a late comer, but since it's burst time is only 2, it gets to slide in before P3...

Shortest Job First (Non preemptive) - Sort bursting time and arrival time simultaneously

1 Answers