CPU scheduling
Operating Systems · 10 interview questions
The scheduler decides which ready process runs next. Non-preemptive schedulers only switch when a process blocks or exits; preemptive ones can take the CPU away, which is what makes interactive systems responsive.
The classic algorithms each optimise one thing. First-come-first-served is fair in arrival order but suffers the convoy effect, where one long job delays everything behind it. Shortest job first minimises average waiting time provably, but requires knowing burst lengths and can starve long jobs. Round robin gives predictable response time by rotating a fixed quantum. Priority scheduling respects importance but starves low-priority work unless aging is added.
Multilevel feedback queues are what real systems approximate: several queues with different quanta, where a process that uses its whole slice sinks to a lower-priority queue and one that blocks early stays high. That approximates shortest-job-first without needing to know burst times in advance.
CPU scheduling interview questions
- What's the difference between preemptive and non-preemptive scheduling?
- Preemptive scheduling can take the CPU from a running process — on a timer interrupt or when a higher-priority process becomes ready. Non-preemptive waits for the process to block or exit voluntarily.
- What is the convoy effect?
- Under first-come-first-served, one long CPU-bound job holds the processor while many short jobs queue behind it, wrecking average waiting time. It's the main argument against plain FCFS.
- What does shortest job first optimise, and what's the catch?
- It provably minimises average waiting time. The catch is that burst lengths aren't known in advance and must be estimated, and long jobs can starve if short ones keep arriving.
- What determines whether round robin performs well?
- The quantum. Too large and it degenerates into FCFS; too small and context-switch overhead dominates. It's chosen to comfortably exceed switch cost while staying under typical interactive burst length.
- What is starvation, and how does aging fix it?
- Starvation is a process never being scheduled because higher-priority work keeps arriving. Aging raises a process's priority the longer it waits, so anything waiting long enough eventually runs.
- How does a multilevel feedback queue approximate shortest job first?
- Processes start in a high-priority queue with a short quantum. One that uses its whole slice is demoted; one that blocks early stays high. Short interactive jobs therefore stay near the top without anyone knowing burst lengths in advance.
- Why they ask: The best answer to 'how do real schedulers work' — it connects the theory to practice.
- Define turnaround, waiting and response time.
- Turnaround is completion minus arrival — total elapsed time. Waiting is time spent in the ready queue. Response is arrival to first execution, which is what interactivity actually depends on.
- Why do schedulers favour I/O-bound processes?
- They use short CPU bursts and then block, so running them promptly keeps devices busy and improves overall throughput. Making them wait behind a CPU-bound job leaves hardware idle.
- What is priority inversion?
- A high-priority task waits on a lock held by a low-priority task, which is itself preempted by medium-priority work — so the high-priority task is effectively blocked by lower-priority ones. Priority inheritance fixes it by temporarily raising the lock holder's priority.
- Why they ask: Famous from the Mars Pathfinder failure, and a strong senior-level answer.
- What is dispatch latency?
- The time between the scheduler deciding to run a process and that process actually executing — the cost of saving one context and restoring another. It's the overhead every switch pays.
You'll forget most of this by next week
That's not a discipline problem, it's how memory works. In the app these come back on an expanding schedule — right before you'd lose them.
Start free for 7 days