Search code examples
javascriptsortingschedulingjob-scheduling

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

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:

enter image description here

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

enter image description here

Reference: Shortest Job First (SJF)

Solution

  • 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...