What are the criteria of CPU Scheduling algorithms?

What is CPU Scheduling?

CPU scheduling is a fundamental function of operating systems that determines which process gets access to the CPU and for how long. Since the CPU is the most critical and often the most limited resource, managing it efficiently ensures high system performance.

When multiple processes are waiting to be executed, the CPU Scheduler selects one based on a defined scheduling algorithm. This decision directly affects the system’s responsiveness, throughput, and overall efficiency.

Objective of CPU Scheduling

The primary goal of CPU scheduling is to:

• Maximize CPU utilization
• Minimize waiting time, turnaround time, and response time
• Improve throughput
• Ensure fairness and predictability

CPU Scheduling Criteria 

Various metrics are used to compare and evaluate CPU scheduling algorithms. These are known as scheduling criteria.

1. CPU Utilization

CPU utilization measures how effectively the CPU is kept busy. The goal is to maximize CPU use, ideally between 40% and 90% in real-world systems. A higher utilization rate means better performance, as the CPU spends less time idle.

2. Throughput

Throughput refers to the number of processes completed per unit of time. It indicates how productive the system is. Shorter processes increase throughput, while longer ones reduce it. It’s a key metric in batch processing and heavily influences system efficiency.

3. Turnaround Time

Turnaround time is the total time a process takes from arrival to completion. It includes all phases like waiting, execution, and I/O. Lower turnaround times mean faster job completion and higher system responsiveness in batch or general-purpose computing environments.

Formula:

Turnaround Time = Completion Time – Arrival Time

4. Waiting Time

Waiting time is the period a process spends in the ready queue before execution. It excludes time spent in execution or I/O. Reducing waiting time improves system efficiency and user experience by decreasing process delays in scheduling.

Formula:

Waiting Time = Turnaround Time – Burst Time

5. Response Time

Response time is the interval between a process’s submission and its first CPU execution. It’s crucial for interactive systems like terminals or user interfaces. Lower response time improves perceived performance and interactivity, even if the process isn’t completed immediately.

Formula:

Response Time = First CPU Allocation Time – Arrival Time

6. Completion Time

Completion time is the moment when a process finishes its total execution. It marks the end of a process’s lifecycle and is used to calculate turnaround and waiting times. Monitoring completion time helps assess system delays and scheduling effectiveness.

7. Priority

Priority scheduling executes higher-priority processes first, based on assigned levels. It’s common in real-time or time-sensitive systems. However, it can lead to starvation of low-priority tasks unless countered by techniques like aging to gradually increase their priority.

8. Predictability

Predictability ensures that processes complete in roughly the same time under similar conditions. It is vital for real-time and embedded systems where consistent timing is critical. A predictable system avoids performance spikes and offers stable user experiences.

Why Choosing the Right CPU Scheduling Algorithm Matters

Different CPU scheduling algorithms prioritize different performance criteria. Selecting the correct one for a given system leads to:

• Efficient use of CPU and other resources
• Faster system response
• Improved user satisfaction
• Higher throughput and lower overhead

Real-world examples

• The Round Robin scheduling algorithm is best suited for time-sharing systems, such as multitasking operating systems, where each process gets an equal share of CPU time in a cyclic manner.
• The Shortest Job First (SJF) algorithm, especially in its non-preemptive form, works well in batch processing systems where the duration of each job is known in advance, helping maximize throughput.
• The Priority Scheduling algorithm is ideal for real-time systems, where certain critical tasks must be prioritized and executed promptly to meet system deadlines or safety constraints.

Types of CPU Scheduling Algorithms

A. Non-Preemptive Algorithms

In these, once a process gets the CPU, it runs to completion.

• First Come First Serve (FCFS)
• Shortest Job First (SJF)
• Longest Job First (LJF)

B. Preemptive Algorithms

In these, the CPU can be taken away from a running process.

• Priority Scheduling
• Round Robin (RR)
• Shortest Remaining Time First (SRTF)
• Longest Remaining Time First (LRTF)
• Multilevel Queue Scheduling
• Multilevel Feedback Queue Scheduling

Frequently Asked Questions (FAQs)

Q1. What is the most important criterion in CPU scheduling?

It depends on the system type. For interactive systems, response time is crucial. In batch systems, throughput and turnaround time are more important. In real-time systems, priority and predictability are key.

Q2. Why is CPU utilization not always 100%?

In real systems, CPUs spend time waiting for I/O or handling context switches, so utilization typically ranges between 40% and 90%. Aiming for 100% could lead to overloading and decreased system responsiveness.

Q3. How does response time differ from turnaround time?

Response time is the time from process submission to the first output, while turnaround time is the total time from submission to completion. Response time matters in interactive systems; turnaround time matters in batch systems.

Q4. Can scheduling algorithms cause starvation?

Yes. Algorithms like Priority Scheduling can cause starvation if low-priority processes are continuously postponed. This can be prevented using techniques like aging, which gradually increases the priority of waiting processes.

Q5. Which scheduling algorithm is best for time-sharing systems?

Round Robin is best suited for time-sharing systems as it gives each process equal CPU time in cycles, ensuring responsiveness and fairness across multiple users and applications.

Conclusion

CPU scheduling decides which process gets the CPU and for how long. It aims to improve performance using criteria like CPU utilization, throughput, turnaround time, waiting time, and response time. The right scheduling algorithm like Round Robin, SJF, or Priority Scheduling depends on the system’s needs (e.g., time-sharing, batch, or real-time). Choosing wisely ensures efficient, fair, and responsive computing.