CPU Scheduling Interview Questions

Introduction

CPU scheduling is one of the most heavily tested topics in operating systems interviews and competitive exams. Interviewers expect you to explain algorithms conceptually, solve numerical problems accurately, and discuss trade-offs between different approaches. This page covers the most frequently asked questions with detailed answers.

Conceptual Questions

Q1: Why is CPU scheduling necessary?

Answer: In a multiprogramming environment, multiple processes compete for the CPU. When the running process performs I/O (and blocks), the CPU would sit idle without scheduling. The scheduler selects the next process from the ready queue, maximizing CPU utilization. Without scheduling, you would need to run processes sequentially, wasting the CPU during I/O waits. Scheduling also provides fairness — ensuring all processes get reasonable access to the CPU.

Q2: What is the difference between preemptive and non-preemptive scheduling?

Answer: In non-preemptive scheduling, once a process gets the CPU, it keeps it until it voluntarily releases (by terminating or blocking for I/O). In preemptive scheduling, the OS can forcibly take the CPU away — typically when a higher-priority process arrives or when a time quantum expires.

Trade-offs:

• Preemptive: Better response time, prevents monopolization, but higher overhead (context switches) and needs careful synchronization (process might be preempted while modifying shared data)
• Non-preemptive: Simpler, no synchronization issues during execution, but poor response time and one long process can block all others

Q3: Explain the convoy effect in FCFS.

Answer: The convoy effect occurs when a CPU-bound process with long burst time arrives first, and many I/O-bound processes with short burst times arrive behind it. All short processes must wait for the long process to complete, creating a "convoy" — like cars stuck behind a slow truck on a single-lane road. This dramatically increases average waiting time. SJF scheduling eliminates this by serving short processes first.

Q4: Why is SJF optimal but impractical?

Answer: SJF (Shortest Job First) gives the minimum average waiting time — this is mathematically provable. However, it is impractical because the OS cannot know future burst times. In practice, burst times are estimated using exponential averaging:

Where τ is the predicted burst, t is actual burst, and α (0 to 1) controls the weight of recent history versus older predictions.

Q5: How do you choose the time quantum in Round Robin?

Answer: The time quantum must balance responsiveness against overhead:

• Too small (e.g., 1ms): Excessive context switches; the CPU spends more time switching than executing
• Too large (e.g., 100s): Degrades to FCFS behavior; response time suffers
• Rule of thumb: 80% of CPU bursts should complete within one quantum

Typical values in practice: 10-100 milliseconds. The Linux CFS (Completely Fair Scheduler) uses a dynamic time slice based on the number of runnable processes.

Q6: What is starvation and how is it solved?

Answer: Starvation occurs when a low-priority process waits indefinitely because higher-priority processes continuously arrive. The solution is aging — gradually increasing the priority of waiting processes over time. For example, increase priority by 1 for every 10 seconds of waiting. Eventually, any process will reach high enough priority to be scheduled.

Numerical Problems

Q7: Calculate average waiting time for FCFS.

Given: Three processes with arrival times and burst times:

Solution (FCFS):

• P1 runs from 0 to 24 (arrived at 0)
• P2 runs from 24 to 27 (arrived at 1, waited 23)
• P3 runs from 27 to 30 (arrived at 2, waited 25)

Q8: Solve the same problem using SJF (non-preemptive).

Solution: At time 0, only P1 is available, so it runs first. At time 24, P2 and P3 are both available — choose shortest (both are 3, pick P2 by arrival).

Result: Same as FCFS here because P1 arrives alone at time 0. This demonstrates that SJF's advantage only manifests when multiple processes are available simultaneously.

Q9: Round Robin with quantum = 4.

Given:

Solution:

Q10: When does SRTF preempt?

Answer: SRTF (Shortest Remaining Time First) preempts the running process whenever a newly arriving process has a shorter remaining burst time. Check preemption at every process arrival event.

Example: P1 (burst=8) starts at time 0. P2 (burst=4) arrives at time 1. At time 1, P1's remaining time is 7, P2's is 4. Since 4 < 7, P2 preempts P1.

Comparison Questions

Q11: Compare all scheduling algorithms.

Q12: What scheduling does Linux use?

Answer: Linux uses the Completely Fair Scheduler (CFS), which models an "ideal" processor where all runnable tasks get equal CPU time simultaneously. It uses a red-black tree sorted by "virtual runtime" — the task with the least virtual runtime gets the CPU next. This provides proportional fairness based on task weights (nice values). For real-time tasks, Linux provides SCHED_FIFO and SCHED_RR policies.

Key Points for Interviews

1. Always draw the Gantt chart — it prevents calculation errors
2. Be precise about whether the algorithm is preemptive or non-preemptive
3. Know that SJF is optimal for average waiting time (non-preemptive among non-preemptive)
4. Understand that Round Robin time quantum trade-off is a classic interview discussion
5. Be ready to explain why real systems use multi-level feedback queues (adaptive behavior)
6. Know the difference between turnaround time and waiting time formulas