Lecture Notes: Pre-emptive Shortest Job First (SJF) Scheduling

Overview of Pre-emptive SJF (RT)

• Preemptive SJF is a CPU scheduling algorithm.
• Also known as Shortest Remaining Time (SRT).
• Prioritizes processes with the shortest remaining execution time.

Process Arrival Timeline

• At time 0: Only process P0 is present.
  • P0 starts execution.
• At time 2: Process P1 arrives.
  • P1 has a burst time shorter than P0's remaining time.
  • Preempt P0, enqueue P1.
• At time 5: Process P2 arrives.
  • P2 has a shorter remaining time than P1.
  • Preempt P1, enqueue P2.
• At time 7: Process P3 arrives.
  • Compare with P2's remaining time; P2 is shorter.
  • Continue P2 until completion.
• At time 10: Process P4 arrives.
  • Compare with the remaining processes P0, P1, P3.
  • Continue with P1 as it has the shortest remaining time.

Detailed Execution Steps

1. Time 0 - 2:
   • P0 executes for 2 milliseconds, 14 ms remaining.
2. Time 2 - 5:
   • P1 executes for 3 milliseconds, 7 ms remaining.
   • P0 is placed back in the queue.
3. Time 5 - 8:
   • P2 executes, finishing in 3 ms as it had the shortest time.
4. Time 8 - 15:
   • P1 resumes execution and completes.
5. Time 15 - 23:
   • P3 executes for 8 ms and completes.
6. Time 23 - 35:
   • P4 executes, completing its 12 ms burst.
7. Time 35 - 49:
   • P0 resumes and completes the remaining execution.

Key Points

• Preemption occurs when a new process arrives with a shorter burst time than the current executing process.
• Final Execution Order: P0 → P1 → P2 → P3 → P4
• Completion times:
  • P1 completes at 15
  • P3 completes at 23
  • P4 completes at 35
  • P0 completes at 49

This scheduling ensures processes with shorter remaining times get prioritized, optimizing overall process completion time.