Introduction
CPU scheduling determines which process gets the CPU and for how long. To evaluate different scheduling algorithms, we use several scheduling criteria. These criteria help in choosing the most efficient scheduling policy based on system requirements.
1. Important Scheduling Criteria
The performance of a scheduling algorithm is measured using the following criteria:
| Criterion | Definition | Goal |
|---|---|---|
| CPU Utilization | Percentage of time the CPU is busy. | Maximize CPU usage. |
| Throughput | Number of processes completed per unit time. | Maximize process execution rate. |
| Turnaround Time | Total time taken from process arrival to completion. | Minimize turnaround time. |
| Waiting Time | Total time a process spends in the ready queue. | Minimize waiting time. |
| Response Time | Time from process submission to first CPU response. | Minimize response time. |
| Fairness | Ensuring no process suffers from starvation. | Provide equal CPU access. |
Let’s discuss each criterion in detail.
2. Scheduling Criteria Explained
1. CPU Utilization
- Definition: Measures how effectively the CPU is utilized.
- Formula: CPU Utilization=CPU busy timeTotal time×100%CPU\ Utilization = \frac{\text{CPU busy time}}{\text{Total time}} \times 100\%CPU Utilization=Total timeCPU busy time×100%
- Goal: Maximize CPU utilization to ensure that the processor is not idle.
- Example:
- If a CPU runs for 80ms out of 100ms, the utilization is 80%.
Key Considerations:
✔ Should be as high as possible (typically 40-90% in general systems).
✖ 100% utilization can lead to overheating and system slowdowns.
2. Throughput
- Definition: Number of processes completed in a given time period.
- Formula: Throughput=Total processes completedTotal timeThroughput = \frac{\text{Total processes completed}}{\text{Total time}}Throughput=Total timeTotal processes completed
- Goal: Maximize throughput by reducing process waiting time.
- Example:
- If a system completes 5 processes in 10 seconds, the throughput is 0.5 processes per second.
Key Considerations:
✔ Higher throughput improves system performance.
✖ Large, long-running processes can lower throughput.
3. Turnaround Time (TAT)
- Definition: Total time taken for a process from arrival to completion.
- Formula: Turnaround Time=Completion Time−Arrival TimeTurnaround\ Time = Completion\ Time – Arrival\ TimeTurnaround Time=Completion Time−Arrival Time
- Goal: Minimize turnaround time for faster process execution.
- Example:
- A process arrives at time = 2 ms and completes at time = 10 ms.
- TAT = 10 – 2 = 8 ms.
Key Considerations:
✔ Shorter turnaround time improves system efficiency.
✖ Long TAT can delay user interactions.
4. Waiting Time (WT)
- Definition: Total time a process spends waiting in the ready queue before execution.
- Formula: Waiting Time=Turnaround Time−Burst TimeWaiting\ Time = Turnaround\ Time – Burst\ TimeWaiting Time=Turnaround Time−Burst Time
- Goal: Minimize waiting time to reduce process delays.
- Example:
- A process has TAT = 10 ms and CPU burst = 6 ms.
- WT = 10 – 6 = 4 ms.
Key Considerations:
✔ Low waiting time improves user experience.
✖ High waiting time can cause starvation (low-priority processes never getting CPU time).
5. Response Time
- Definition: Time from process arrival to the first execution on CPU.
- Formula: Response Time=First Execution Time−Arrival TimeResponse\ Time = First\ Execution\ Time – Arrival\ TimeResponse Time=First Execution Time−Arrival Time
- Goal: Minimize response time for better user interaction.
- Example:
- A process arrives at time = 1 ms and gets CPU for the first time at time = 4 ms.
- Response Time = 4 – 1 = 3 ms.
Key Considerations:
✔ Critical for interactive and real-time systems (e.g., gaming, live streaming).
✖ High response time frustrates users.
6. Fairness
- Definition: Ensuring all processes get CPU access without starvation.
- Goal: Prevent process starvation and promote equal CPU time distribution.
- Example:
- If high-priority processes always preempt low-priority ones, low-priority tasks never execute, leading to starvation.
- Fair scheduling ensures all processes get a chance to execute.
Key Considerations:
✔ Important for multi-user and real-time systems.
✖ Ensuring fairness can reduce efficiency (e.g., Round Robin scheduling gives equal time but increases overhead).
3. Trade-offs Between Scheduling Criteria
No single scheduling algorithm can optimize all criteria simultaneously. There are trade-offs:
| Scenario | Optimization Needed | Algorithm Choice |
|---|---|---|
| Batch Processing | Maximize CPU utilization, throughput | Shortest Job Next (SJN) |
| Time-Sharing System | Minimize response time | Round Robin (RR) |
| Real-Time System | Minimize waiting time, response time | Priority Scheduling (Preemptive) |
| Multitasking System | Balance fairness and turnaround time | Multilevel Queue Scheduling |
For example, Round Robin (RR) improves response time, but it increases context switching overhead. Similarly, Shortest Job Next (SJN) minimizes waiting time, but starves longer processes.
4. Summary of Scheduling Criteria
| Criterion | Goal | Best for |
|---|---|---|
| CPU Utilization | Maximize CPU use | All systems |
| Throughput | Maximize process execution rate | High-performance systems |
| Turnaround Time | Minimize process execution time | User applications |
| Waiting Time | Reduce time spent in queue | Interactive systems |
| Response Time | Minimize delay for first execution | Real-time and multitasking |
| Fairness | Ensure equal CPU access | Multi-user systems |
Key Takeaways
- Batch systems focus on CPU utilization and throughput.
- Interactive systems prioritize response time and waiting time.
- Real-time systems need low latency and fairness.