L-2.4: Shortest Job First(SJF) Scheduling Algorithm with Example | Operating System

Main ideas / concepts covered

• Shortest Job First (SJF) Scheduling Algorithm

  • Decision criterion: select the process with the smallest Burst Time.
  • Variant used: Non-preemptive
    • Once a process gets the CPU, it runs to completion without interruption.

• Goal of the numerical problem

  • For each process P1, P2, P3, P4, compute:
    • Completion Time (CT)
    • Turnaround Time (TAT)
    • Waiting Time (WT)
    • Response Time (RT) (noting when it can be omitted)

Methodology / step-by-step procedure (as demonstrated)

• Inputs (given in the numerical)

  • For processes P1, P2, P3, P4:
    • Arrival Time
    • Burst Time
  • The specific arrival and burst values are used consistently throughout the Gantt chart.

• Step 1: Build the Gantt chart timeline

  • Start time = 0
  • For each time segment:
    • Check which processes have arrived by the current time.
    • If no process has arrived, the CPU stays idle (example: from 0 to 1).

• Step 2: Select the next process

  • Among arrived processes, pick the one with minimum Burst Time.
  • Since scheduling is non-preemptive, the chosen process runs until it finishes.

• Step 3: Handle ties (equal Burst Time)

  • If multiple arrived processes have the same Burst Time:
    • Prefer the one with earlier Arrival Time.
    • If Arrival Time is also the same, use the lower Process ID (smaller numbered process).

• Step 4: Compute completion times from the Gantt chart

  • Read CT from the points where each process finishes.
  • Example completion times used:
    • P3 completes at 3
    • P1 completes at 6
    • P2 completes at 10
    • P4 completes at 14

• Step 5: Compute Turnaround Time (TAT)

  • TAT = Completion Time − Arrival Time
  • Example values:
    • P1: 6 − 1 = 5
    • P2: 10 − 2 = 8
    • P3: 3 − 1 = 2
    • P4: 14 − 4 = 10

• Step 6: Compute Waiting Time (WT)

  • WT = TAT − Burst Time
  • Example values:
    • P1: 5 − 3 = 2
    • P2: 8 − 4 = 4
    • P3: 2 − 2 = 0
    • P4: 10 − 4 = 6

• Step 7: Response Time (RT) guidance

  • For non-preemptive SJF, Response Time = Waiting Time, so it’s often not required separately.
  • Response time definition (as stated):
    • RT = time when a process first gets CPU − Arrival Time
  • RT differs mainly in preemptive scheduling, where the CPU may switch and a process can wait before running again.

• Step 8: Compute averages (if asked)

  • Average Turnaround Time

    • [ \frac{\text{Sum of all TATs}}{\text{number of processes}} ]

    • Example:

      • ((5 + 8 + 2 + 10) / 4 = 25 / 4 = 6.25)
      • Average Waiting Time

    • [ \frac{\text{Sum of all WTs}}{\text{number of processes}} ]

    • Example:

      • ((2 + 4 + 0 + 6) / 4 = 12 / 4 = 3)

Speakers / sources featured

• Gate Smashers (channel/creator credited in subtitles as “Gate Smashers”)