How to Calculate Average Waiting Time in CPU Scheduling Algorithms

📚 Understanding Average Waiting Time in CPU Scheduling

In operating systems, CPU scheduling algorithms manage the execution of processes. A key metric to evaluate these algorithms is the average waiting time. This metric helps us understand how long processes spend waiting in the ready queue before getting executed. A lower average waiting time generally indicates a more efficient scheduling algorithm, leading to better system performance.

📜 A Brief History of CPU Scheduling

The development of CPU scheduling algorithms is intertwined with the evolution of computer systems. Early systems used simple scheduling methods like First-Come, First-Served (FCFS). As systems became more complex, algorithms like Shortest Job First (SJF) and Priority Scheduling were introduced to improve resource utilization and reduce waiting times. Today, advanced algorithms like Round Robin and Multilevel Queue Scheduling are widely used to balance fairness and efficiency.

🔑 Key Principles for Calculation

• ⏱️ Waiting Time: The amount of time a process spends waiting in the ready queue.
• 🔄 Turnaround Time: The total time taken from the process's arrival to its completion ($Turnaround\ Time = Completion\ Time - Arrival\ Time$).
• ➕ Burst Time: The time required by the CPU to execute a process.
• 🧮 Calculation: $Waiting\ Time = Turnaround\ Time - Burst\ Time$. Average Waiting Time is the sum of the waiting times for all processes divided by the total number of processes.

✏️ Formula Breakdown

The average waiting time is calculated using the following formula:

$\text{Average Waiting Time} = \frac{\sum_{i=1}^{n} \text{Waiting Time}_i}{n}$

Where:

• 🔢 $n$ is the number of processes.
• ⏳ $\text{Waiting Time}_i$ is the waiting time for the $i$-th process.

📝 Step-by-Step Example: First-Come, First-Served (FCFS)

Let's consider four processes (P1, P2, P3, P4) with arrival times and burst times as follows:

Here's how to calculate the average waiting time using FCFS:

1. Gantt Chart:

   [0-8] P1 [8-12] P2 [12-21] P3 [21-26] P4

2. Completion Times:
   • P1: 8
   • P2: 12
   • P3: 21
   • P4: 26
3. Turnaround Times:
   • P1: 8 - 0 = 8
   • P2: 12 - 1 = 11
   • P3: 21 - 2 = 19
   • P4: 26 - 3 = 23
4. Waiting Times:
   • P1: 8 - 8 = 0
   • P2: 11 - 4 = 7
   • P3: 19 - 9 = 10
   • P4: 23 - 5 = 18
5. Average Waiting Time:

   $\frac{0 + 7 + 10 + 18}{4} = \frac{35}{4} = 8.75$

✏️ Example: Shortest Job First (SJF) (Non-Preemptive)

Using the same processes as above, let's calculate the average waiting time using SJF (Non-Preemptive):

1. Gantt Chart:

   [0-8] P1 [8-12] P2 [12-17] P4 [17-26] P3
2. Completion Times:
   • P1: 8
   • P2: 12
   • P3: 26
   • P4: 17
3. Turnaround Times:
   • P1: 8 - 0 = 8
   • P2: 12 - 1 = 11
   • P3: 26 - 2 = 24
   • P4: 17 - 3 = 14
4. Waiting Times:
   • P1: 8 - 8 = 0
   • P2: 11 - 4 = 7
   • P3: 24 - 9 = 15
   • P4: 14 - 5 = 9
5. Average Waiting Time:

   $\frac{0 + 7 + 15 + 9}{4} = \frac{31}{4} = 7.75$

🧪 Real-World Applications

• 🖥️ Operating Systems: CPU scheduling is fundamental to how operating systems manage processes.
• 🌐 Web Servers: Efficient scheduling ensures timely responses to client requests.
• 📱 Mobile Devices: Optimizes battery life and responsiveness by managing tasks efficiently.
• ⚙️ Embedded Systems: Critical for real-time systems where timely execution is paramount.

💡 Tips and Tricks

• ✅ Gantt Charts: Use Gantt charts to visualize the execution order and calculate waiting times accurately.
• 📝 Practice: Work through various examples to become comfortable with different scheduling algorithms.
• 🧮 Double-Check: Always double-check your calculations to avoid errors.
• 📚 Understand Algorithms: Have a clear understanding of each algorithm's principles to apply them correctly.

🎓 Conclusion

Calculating average waiting time is crucial for evaluating the performance of CPU scheduling algorithms. By understanding the principles and practicing with examples, you can effectively analyze and compare different scheduling strategies, leading to more efficient system design and management.