Calculating Average Waiting Time with Preemptive SJF Scheduling

The question asks us to find the average waiting time for four processes using the preemptive Shortest Job First (SJF) CPU scheduling algorithm. We are given the arrival time and CPU burst time for each process.

Understanding Preemptive SJF Scheduling

Preemptive SJF is a scheduling algorithm where the CPU is allocated to the process with the smallest burst time. When a new process arrives, if its burst time is less than the remaining time of the currently executing process, the currently executing process is preempted (interrupted), and the new process starts executing. This continues until a process completes or is preempted by a newly arriving process with a shorter remaining burst time.

Given Process Information

Here is the information for the given processes:

Simulating Execution with Gantt Chart (Preemptive SJF)

Let's trace the execution of these processes using a Gantt chart. We will keep track of the remaining burst time for each process.

• Time 0: P1 arrives. It's the only process, so it starts executing. Remaining Burst Time for P1 = 8 ms.
• Time 1: P2 arrives (Burst Time = 4 ms). P1 has been running for 1 ms, remaining Burst Time for P1 = $8 - 1 = 7$ ms. Compare P2's burst time (4 ms) with P1's remaining time (7 ms). Since 4 < 7, P1 is preempted, and P2 starts executing.
• Time 2: P3 arrives (Burst Time = 9 ms). P2 has been running for 1 ms, remaining Burst Time for P2 = $4 - 1 = 3$ ms. Compare P3's burst time (9 ms) with P2's remaining time (3 ms). Since 9 > 3, P2 continues executing.
• Time 3: P4 arrives (Burst Time = 5 ms). P2 has been running for another 1 ms, remaining Burst Time for P2 = $3 - 1 = 2$ ms. Compare P4's burst time (5 ms) with P2's remaining time (2 ms). Since 5 > 2, P2 continues executing.
• Time 4: P2 continues executing. Remaining Burst Time for P2 = $2 - 1 = 1$ ms.
• Time 5: P2 completes execution. The processes available are P1 (remaining 7 ms), P3 (9 ms), P4 (5 ms). Among these, P4 has the shortest remaining burst time (5 ms). P4 starts executing.
• Time 6 - 9: P4 continues executing.
• Time 10: P4 completes execution ($5 + 5 = 10$). The processes available are P1 (remaining 7 ms), P3 (9 ms). Among these, P1 has the shortest remaining burst time (7 ms). P1 starts executing.
• Time 11 - 16: P1 continues executing.
• Time 17: P1 completes execution ($10 + 7 = 17$). The only remaining process is P3 (9 ms). P3 starts executing.
• Time 18 - 25: P3 continues executing.
• Time 26: P3 completes execution ($17 + 9 = 26$). All processes are completed.

Based on the simulation, the Gantt chart looks like this:

| P1 (0-1) | P2 (1-5) | P4 (5-10) | P1 (10-17) | P3 (17-26) |

Calculating Waiting Time for Each Process

Waiting time for a process is the total time it spent waiting in the ready queue. This can be calculated as:

Waiting Time = (Completion Time - Arrival Time) - Burst Time

• P1:
  • Arrived at 0, started at 0.
  • Ran until 1, preempted.
  • Restarted at 10.
  • Completed at 17.
  • Waiting Time = (17 - 0) - 8 = 17 - 8 = 9 ms.
  • Alternatively, wait time = (time ready but not running). P1 waited from time 1 to time 10 while P2 and P4 ran. Wait time = $10 - 1 = 9$ ms.
• P2:
  • Arrived at 1, started at 1.
  • Completed at 5.
  • Waiting Time = (5 - 1) - 4 = 4 - 4 = 0 ms.
  • Alternatively, wait time = (Start Time - Arrival Time) = $1 - 1 = 0$ ms.
• P3:
  • Arrived at 2, started at 17.
  • Completed at 26.
  • Waiting Time = (26 - 2) - 9 = 24 - 9 = 15 ms.
  • Alternatively, wait time = (Start Time - Arrival Time) = $17 - 2 = 15$ ms.
• P4:
  • Arrived at 3, started at 5.
  • Completed at 10.
  • Waiting Time = (10 - 3) - 5 = 7 - 5 = 2 ms.
  • Alternatively, wait time = (Start Time - Arrival Time) = $5 - 3 = 2$ ms.

The waiting times are: P1 = 9 ms, P2 = 0 ms, P3 = 15 ms, P4 = 2 ms.

Calculating Average Waiting Time

Average Waiting Time = (Sum of Waiting Times) / (Number of Processes)

Average Waiting Time = $\frac{9 + 0 + 15 + 2}{4} = \frac{26}{4} = 6.5$ ms.

The average waiting time for the preemptive SJF scheduling algorithm is 6.5 ms.

Revision Table: Preemptive SJF Scheduling

Sum of Waiting Times = $9 + 0 + 15 + 2 = 26$ ms.

Number of Processes = 4.

Average Waiting Time = $\frac{26}{4} = 6.5$ ms.

Additional Information: CPU Scheduling Concepts

CPU scheduling is the process of deciding which process will own the CPU for use, and when. It is fundamental to operating systems.

• CPU Burst: The amount of time a process needs the CPU to execute its instructions.
• Arrival Time: The time at which a process enters the ready queue.
• Completion Time: The time at which a process finishes its execution.
• Turnaround Time: The total time from arrival until completion of a process. $\text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time}$.
• Waiting Time: The total time a process spends in the ready queue waiting for the CPU. $\text{Waiting Time} = \text{Turnaround Time} - \text{Burst Time}$.
• Preemption: The act of interrupting a currently executing process to run another process.
• SJF (Shortest Job First): A scheduling algorithm that schedules the process with the smallest CPU burst time. It can be preemptive or non-preemptive. Preemptive SJF is also known as Shortest Remaining Time First (SRTF).

Understanding these concepts is crucial for analyzing the performance of different CPU scheduling algorithms.