CPU Scheduling Algorithms
Subject: Computer Science Fundamentals · Language: Operating System · Level: intermediate · 9 min read
Learn CPU scheduling algorithms including FCFS, SJF, SRTF, Priority, Round Robin, multilevel queues, and key scheduling problems.
CPU scheduling algorithms are rules used by the operating system to choose which process should run next. Different algorithms make different decisions. Some are simple, some give better average waiting time, some improve response time, and some are better for interactive systems. Before learning algorithms, students should understand the common terms: arrival time, burst time, completion time, turnaround time, waiting time, and response time. These terms help compare scheduling algorithms.
No single scheduling algorithm is best for every system. A batch system, time-sharing system, and real-time system may need different scheduling strategies. The correct choice depends on the goal of the operating system.
First Come First Serve Scheduling
First Come First Serve, or FCFS, is the simplest CPU scheduling algorithm. The process that arrives first gets the CPU first. Processes are executed in arrival order. FCFS is easy to understand and easy to implement. It works like a normal queue. The first process enters the ready queue, gets CPU first, completes, and then the next process runs.
The main problem with FCFS is that a long process can make shorter processes wait for a long time. This is called the convoy effect. A group of short processes may get stuck behind one long process. For example, suppose P1 needs 20 units of CPU time, P2 needs 2 units, and P3 needs 1 unit. If P1 arrives first, P2 and P3 must wait until P1 finishes. Their waiting time becomes high even though they are short jobs. FCFS is usually non-preemptive. Once a process gets CPU, it runs until it finishes or blocks for input-output.
Shortest Job First Scheduling
Shortest Job First, or SJF, selects the process with the smallest CPU burst time. The idea is simple: if shorter jobs finish first, average waiting time can become smaller. SJF can give very good average waiting time when burst times are known. If P1 needs 8 units, P2 needs 3 units, and P3 needs 2 units, SJF will run P3 first, then P2, then P1.
The main difficulty with SJF is knowing the CPU burst time in advance. In real systems, the OS may not know exactly how long a process will need the CPU. It may estimate burst time based on previous behavior. Another problem is starvation. If short jobs keep arriving, a long job may wait for a very long time. This is unfair to long processes. SJF can be non-preemptive or preemptive. The preemptive version is often called Shortest Remaining Time First.
Shortest Remaining Time First
Shortest Remaining Time First, or SRTF, is the preemptive version of SJF. The CPU is given to the process with the shortest remaining CPU time. If a new process arrives with a shorter remaining time than the currently running process, the OS may preempt the current process and run the new process. SRTF can reduce average waiting time, but it causes more context switches than non-preemptive SJF. It also requires the OS to continuously compare remaining burst times. SRTF is useful to understand preemption clearly. It shows how a running process can lose CPU when a shorter job arrives.
Priority Scheduling
Priority scheduling assigns a priority to each process. The process with the highest priority gets CPU first. Priority may be based on importance, memory requirement, user type, deadline, or system policy. Priority scheduling can be preemptive or non-preemptive. In preemptive priority scheduling, if a higher-priority process arrives, it can take the CPU from the currently running lower-priority process.
The main problem with priority scheduling is starvation. Low-priority processes may wait indefinitely if higher-priority processes keep arriving. A common solution to starvation is aging. Aging gradually increases the priority of a waiting process. The longer a process waits, the higher its priority becomes. This ensures that low-priority processes eventually get CPU time.
Round Robin Scheduling
Round Robin scheduling is designed for time-sharing systems. Each process gets a fixed amount of CPU time called a time quantum or time slice. If the process finishes within its time quantum, it leaves the system. If it does not finish, it is moved back to the end of the ready queue, and the next process gets CPU.
Round Robin is preemptive because the OS takes the CPU away when the time quantum expires. It gives every process a fair chance and improves response time for interactive users. The time quantum is very important. If the time quantum is too large, Round Robin behaves like FCFS. If the time quantum is too small, too many context switches happen, reducing performance. For example, if the time quantum is 4 units and a process needs 10 units, it will run for 4 units, then wait, then run for another 4 units, then finally run for 2 units later.
Multilevel Queue Scheduling
In multilevel queue scheduling, processes are divided into different queues based on type or priority. For example, system processes may be in one queue, interactive processes in another queue, and batch processes in another queue. Each queue can have its own scheduling algorithm. The interactive queue may use Round Robin, while the batch queue may use FCFS. A fixed priority may be assigned among queues. For example, system processes may always get higher priority than user batch processes. This can improve important task handling but may cause starvation for lower queues.
Multilevel Feedback Queue Scheduling
Multilevel feedback queue scheduling is more flexible than multilevel queue scheduling. In this method, processes can move between queues based on their behavior. If a process uses too much CPU, it may move to a lower-priority queue. If a process waits too long, it may move to a higher-priority queue. This helps balance fairness and performance. This algorithm is useful because it does not permanently classify a process. A process can be treated differently as its behavior changes.
FCFS vs SJF vs Priority vs Round Robin
FCFS is simple but can cause high waiting time due to the convoy effect. SJF gives low average waiting time but needs burst time knowledge and may cause starvation. Priority scheduling is useful for important tasks but can starve low-priority processes. Round Robin is good for time-sharing and interactive systems but depends heavily on time quantum size. A beginner should not only memorize algorithm names. It is more important to understand what each algorithm chooses first and what problem it may create.
Important Problems in Scheduling
Starvation happens when a process waits indefinitely because other processes keep getting selected. Priority scheduling and SJF can suffer from starvation. Convoy effect happens when short processes wait behind a long process, especially in FCFS. This increases average waiting time and reduces system responsiveness. Context-switching overhead happens when the OS switches too frequently between processes. Round Robin with a very small time quantum can cause this problem.
Choosing a Scheduling Algorithm
For batch systems, throughput and turnaround time may be more important. For interactive systems, response time is very important. For real-time systems, meeting deadlines is the main goal. This is why operating systems may use a combination of scheduling ideas instead of relying on only one simple algorithm. Modern systems often use advanced priority-based and feedback-based scheduling methods.
Summary
CPU scheduling algorithms decide which process gets CPU next. FCFS uses arrival order. SJF chooses the shortest burst time. SRTF chooses the shortest remaining time and allows preemption. Priority scheduling chooses the highest-priority process. Round Robin gives each process a fixed time quantum.
The important beginner concepts are convoy effect, starvation, aging, time quantum, preemptive scheduling, non-preemptive scheduling, and context-switching overhead. Understanding these ideas makes scheduling questions much easier in interviews.
Why Algorithms Are Compared
CPU scheduling algorithms are compared because each one behaves differently under different workloads. An algorithm that is simple and fair may not give the shortest waiting time. An algorithm that reduces waiting time may be harder to implement or may cause starvation. Students should compare algorithms using examples, not only definitions. The same set of processes can produce different waiting time, turnaround time, and response time depending on the scheduling method used.
No Single Best Algorithm
There is no single CPU scheduling algorithm that is best for every system. FCFS is simple, SJF can reduce average waiting time, Round Robin is useful for time-sharing systems, and priority scheduling is useful when some tasks are more important than others. Real operating systems often use more advanced or combined scheduling policies. The beginner algorithms are still important because they teach the trade-offs behind CPU scheduling decisions.
More Operating System Lessons
- Introduction to Operating System
- Types of Operating System
- Operating System Functions and Services
- System Calls in Operating System
- Process Management in Operating System
- Process Scheduling in Operating System
- Threads and Multithreading in Operating System
- Process Synchronization in Operating System
- Deadlock in Operating System
- Memory Management in Operating System
- Virtual Memory in Operating System
- File System in Operating System