Difficulty: Beginner
Explain the main CPU scheduling algorithms (FCFS, SJF, SRTF, Round Robin, Priority) and their pros, cons and criteria for comparison.
CPU scheduling is the decision of which ready process gets the CPU next, and it is one of the most commonly examined OS topics because it combines theory with calculations. To evaluate any algorithm we use standard metrics: CPU utilization, throughput (jobs completed per unit time), turnaround time (completion minus arrival), waiting time (turnaround minus burst) and response time (first run minus arrival). Algorithms are also classified as non-preemptive, where a running process keeps the CPU until it finishes or blocks, or preemptive, where the OS may take the CPU away.
First Come First Served (FCFS) is the queue at a ticket counter: whoever arrives first is served first. It is non-preemptive and trivial to implement. Its problem is the convoy effect: a long CPU-bound job at the front makes many short jobs wait behind it, giving a high average waiting time.
Shortest Job First (SJF) picks the process with the smallest next CPU burst. In its non-preemptive form, it is provably optimal in minimizing average waiting time for a given set of processes. The catch is that you cannot know the next burst length in advance, so real systems estimate it using exponential averaging of previous bursts. SJF can also starve long jobs. Its preemptive version is Shortest Remaining Time First (SRTF): whenever a new process arrives with a burst shorter than the remaining time of the current one, the CPU is preempted. SRTF gives an even lower average waiting time but with more context switches.
Round Robin (RR) is designed for time-sharing. Each process gets a fixed time quantum, and if unfinished, goes to the back of the ready queue. It is preemptive, fair and gives good response time, and it cannot starve anyone. The quantum is the key tuning knob. If it is too large, RR degenerates to FCFS. If it is too small, context switch overhead dominates. A rule of thumb is that about 80 percent of CPU bursts should be shorter than the quantum. With n processes and quantum q, no process waits more than (n-1) times q for its next turn.
Priority scheduling assigns each process a priority and always runs the highest one, either preemptively or not. Priorities can be internal (based on memory needs, I/O to CPU ratio) or external (importance, user). The danger is starvation of low-priority processes, which is fixed by aging, gradually raising the priority of processes that wait a long time. SJF is really a priority algorithm where priority is the inverse of the next burst.
Real systems combine these ideas. A Multilevel Queue partitions processes into fixed queues (system, interactive, batch) with different algorithms. Multilevel Feedback Queue (MLFQ) lets processes move between queues based on behaviour: CPU hogs sink to lower priority, interactive jobs stay high. Linux's Completely Fair Scheduler uses a virtual runtime to give each task a fair share, and Windows uses a priority-based preemptive scheduler with dynamic boosts.
When answering in an interview, give a one-line characteristic for each: FCFS is simple but suffers convoy effect, SJF is optimal but needs prediction and starves, RR is fair and responsive but depends on quantum, priority is flexible but risks starvation. Then offer to work through a numerical example, which leads directly into the Gantt chart question.
CPU scheduling, FCFS, SJF, Round Robin, priority scheduling