Free lesson · Operating Systems

Interview Patterns Scheduling

Easy11 min readoperating-systemsosconcurrency

How Scheduling Questions Appear in Interviews

Scheduling questions come in three flavors. The first is definition and comparison - "explain Round Robin" or "compare SJF and FCFS." The second is calculation - "given these processes, calculate the average waiting time under algorithm X." The third, and most valuable, is system design connection - "how does the OS scheduler affect the performance of your web server?" This topic prepares you for all three.

The key to strong scheduling answers is connecting algorithms to tradeoffs. An answer that says "Round Robin gives each process a time quantum" is correct but weak. An answer that says "Round Robin trades throughput for response time - the quantum controls the balance, and the right size depends on whether your workload is interactive or batch" demonstrates understanding.

Question 1: "Compare FCFS, SJF, and Round Robin"

This is the most common scheduling comparison question. The interviewer wants to see a structured comparison across the dimensions that matter, not a list of definitions.

The structured answer:

"These three algorithms represent different points on the throughput-versus-response-time spectrum.

FCFS runs processes in arrival order. It is simple and fair in the sense that nobody jumps the line. But it suffers from the convoy effect - one long process blocks all short processes behind it, producing high average waiting times. It is non-preemptive, so it is not suitable for interactive systems.

SJF runs the shortest process first. It is provably optimal for average waiting time - no non-preemptive algorithm can do better. But it requires knowing burst times in advance, which is impossible in practice, and it can starve long processes if short ones keep arriving.

Round Robin gives each process a fixed time quantum and cycles through them. It does not optimize for average waiting time, but it guarantees bounded response time - no process waits more than (n-1) × quantum between turns. The quantum size is the key parameter: small quanta give excellent response time but high overhead; large quanta improve throughput but hurt responsiveness."

Then provide the comparison framework:

Interview: When the interviewer asks for a recommendation:

"For an interactive system like a desktop OS or a web server, I would choose Round Robin or a descendant like MLFQ. Response time matters most, and Round Robin provides bounded response time. For a batch processing system where throughput matters and no users are waiting, FCFS is acceptable because the convoy effect does not hurt anyone interactively. SJF is the theoretical ideal but impractical in its pure form - real schedulers approximate it by estimating burst lengths."

Question 2: "What is starvation and how do you prevent it?"

This question tests whether you understand the failure mode of priority-based scheduling and the standard fix.

The structured answer:

"Starvation occurs when a process is ready to run but never gets CPU time because higher-priority processes keep being scheduled ahead of it. It is most common in priority scheduling - if high-priority processes arrive continuously, low-priority processes wait indefinitely.

The standard solution is aging - gradually increasing the priority of waiting processes over time. The longer a process waits, the higher its effective priority becomes. Eventually, even the lowest-priority process gets promoted above everything else and runs.

A related problem is priority inversion, where a high-priority process is indirectly blocked because a low-priority process holds a resource it needs, and medium-priority processes prevent the low-priority process from running. The fix for priority inversion is priority inheritance - temporarily raising the low-priority process's priority to the level of the blocked high-priority process so it can finish and release the resource."

If the interviewer asks for a real-world example, mention the Mars Pathfinder incident - the high-priority bus task was starved due to priority inversion, and NASA uploaded a priority inheritance fix remotely.

Question 3: "How does the Linux scheduler work?"

This question tests depth. Many candidates know FCFS and Round Robin but have no idea how a real OS scheduler works. Knowing CFS sets you apart.

The structured answer:

"Linux uses the Completely Fair Scheduler, or CFS. CFS assigns each process a virtual runtime (vruntime) that tracks how much CPU time it has received relative to its fair share. The process with the lowest vruntime - the one that has been treated most unfairly - runs next.

CFS maintains processes in a red-black tree sorted by vruntime. Selecting the next process is O(log n) - it is always the leftmost node. When a process runs, its vruntime increases. When it yields or is preempted, it goes back into the tree at its new vruntime position.

CFS does not use fixed time quanta. Instead, it calculates a target latency - the period within which every runnable process should get at least one turn. The target latency is divided among all runnable processes. If there are 10 runnable processes and the target latency is 20 ms, each gets roughly 2 ms. CFS also enforces a minimum granularity (about 0.75 ms) to prevent excessive context switching.

Nice values control how fast vruntime accumulates. A process with a lower nice value accumulates vruntime more slowly, so it stays near the front of the tree and gets more CPU time. This provides weighted fairness without discrete priority queues."

If the interviewer follows up with "what is the time complexity of CFS?", you can add: "Selection is O(log n) because it is finding the leftmost node in a red-black tree. Insertion after a process runs is also O(log n). This is more expensive than Round Robin's O(1) FIFO operations, but the fairness guarantees are worth it. For most workloads (tens to hundreds of runnable processes), the difference between O(1) and O(log n) is negligible - we are talking nanoseconds."

Question 3b: "How would you choose the time quantum for Round Robin?"

This is a follow-up question that tests deeper understanding of the throughput-versus-response-time tradeoff.

The structured answer:

"The quantum must balance two concerns: response time and context switch overhead.

For response time: the maximum wait before a process gets its next turn is approximately (n-1) × quantum, where n is the number of runnable processes. If I have 100 processes and need response time under 1 second, the quantum must be under 10 ms. If I have 10 processes and can tolerate 100 ms response time, a 10 ms quantum works well.

For overhead: if the context switch takes C microseconds and the quantum is Q milliseconds, the fraction of CPU time wasted on switching is C / (Q + C). With a switch time of 100 microseconds and a quantum of 10 ms, overhead is about 1% - acceptable. With a quantum of 1 ms, overhead rises to 9% - significant for CPU-bound workloads.

The rule of thumb is that 80% of CPU bursts should complete within a single quantum. For I/O-bound workloads (web servers, database query processing), bursts are typically 1-5 ms, so a quantum of 10-20 ms works well. For CPU-bound workloads (batch processing, compilation), longer quanta of 50-100 ms reduce overhead. Most production systems use 10-100 ms depending on the workload mix."

Question 4b: "What scheduling algorithm does your database/web server use?"

This question tests whether you can connect scheduling theory to real infrastructure.

For a web server (e.g., Tomcat, Nginx):

"Tomcat uses a thread pool where the OS scheduler (CFS on Linux) schedules the threads. Within the pool, work is dispatched from a bounded queue - effectively FCFS within the pool. The OS-level scheduling provides fairness across threads, while the pool bounds the number of threads to prevent excessive context switching. Nginx takes a different approach - it uses an event-driven model with very few threads, so the OS scheduler has very little work to do. Nginx's internal event loop handles request scheduling directly."

For a database (e.g., PostgreSQL):

"PostgreSQL uses a process-per-connection model. Each client connection gets its own OS process, and the OS scheduler (CFS) handles all the scheduling. PostgreSQL does not implement its own scheduler - it relies entirely on the OS. This simplifies PostgreSQL's code but means its performance characteristics are tied to CFS's behavior. For example, a long-running analytics query in one connection will accumulate vruntime quickly, and CFS will naturally give shorter OLTP queries more frequent turns."

graph TD
    subgraph COMPARISON["Scheduling Algorithm Decision Tree"]
        START["What is your<br/>primary concern?"]
        
        START -->|"Response time<br/>(interactive system)"| RR["Round Robin<br/>or MLFQ"]
        START -->|"Average waiting time<br/>(batch system)"| SJF_Q["Can you estimate<br/>burst times?"]
        START -->|"Simplicity<br/>(low contention)"| FCFS["FCFS"]
        START -->|"Both response time<br/>and throughput"| MLFQ["MLFQ or CFS"]
        
        SJF_Q -->|"Yes"| SJF["SJF / SRTF"]
        SJF_Q -->|"No"| RR2["Round Robin<br/>(approximates SJF<br/>behavior for I/O-bound)"]
        
        RR -->|"Need starvation<br/>prevention"| MLFQ2["MLFQ with<br/>periodic boost"]
        MLFQ -->|"Linux"| CFS["CFS<br/>(vruntime + red-black tree)"]
    end

This decision tree helps choose a scheduling algorithm. If response time is the primary concern, use Round Robin or MLFQ. If average waiting time matters and you can estimate burst times, use SJF. If simplicity is needed for low-contention workloads, use FCFS. If both response time and throughput matter, use MLFQ or CFS. The tree also shows that MLFQ with periodic boost addresses starvation, and CFS is what Linux actually uses.

Question 4: "Given these processes, calculate the average waiting time under algorithm X"

This is the calculation-based question. The interviewer gives you 3-5 processes with arrival times and burst times, names a scheduling algorithm, and asks you to compute the metrics. Here is the systematic approach:

Step 1: Draw a timeline (Gantt chart) showing when each process runs. For FCFS, this is arrival order. For SJF, pick the shortest available process at each scheduling point. For Round Robin, cycle through the queue with the given quantum.

Step 2: Record the completion time for each process - the moment it finishes its last CPU burst.

Step 3: Calculate turnaround time: Completion Time − Arrival Time.

Step 4: Calculate waiting time: Turnaround Time − Burst Time.

Step 5: Average the turnaround times and waiting times across all processes.

Let us practice with a full example. Processes:

Under Round Robin (quantum = 2):

Time 0-2: P1 runs (2ms of 6). P1 remaining: 4. Time 2-4: P2 runs (2ms of 3). P2 remaining: 1. (P2 arrived at time 2.) Time 4-6: P1 runs (2ms of 4). P1 remaining: 2. (P3 arrived at time 4, behind P1 in queue.) Time 6-7: P3 runs (1ms - finishes). P3 done. Time 7-9: P4 runs (2ms of 4). P4 remaining: 2. Time 9-10: P2 runs (1ms - finishes). P2 done. Time 10-12: P1 runs (2ms - finishes). P1 done. Time 12-14: P4 runs (2ms - finishes). P4 done.

gantt
    title Round Robin (quantum=2ms) worked example
    dateFormat X
    axisFormat %s

    section Schedule
    P1 (2 of 6)  :p1a, 0, 2
    P2 (2 of 3)  :p2a, 2, 4
    P1 (2 of 4)  :p1b, 4, 6
    P3 (1-done)  :p3, 6, 7
    P4 (2 of 4)  :p4a, 7, 9
    P2 (1-done)  :p2b, 9, 10
    P1 (2-done)  :p1c, 10, 12
    P4 (2-done)  :p4b, 12, 14

This Gantt chart traces a Round Robin schedule with a 2ms quantum. P1 runs first for 2ms, then P2 for 2ms, then P1 again for 2ms, then P3 finishes in 1ms, then P4 for 2ms, then P2 finishes in 1ms, then P1 finishes in 2ms, and P4 finishes in 2ms. Total time is 14ms. Average waiting time is 4.5ms.

Question 5: "How does scheduling affect system design?"

This is the highest-value question because it connects OS knowledge to system design decisions. The interviewer wants to see that you can apply scheduling theory to real architecture choices.

The structured answer:

"Scheduling affects three system design decisions. First, the concurrency model. A thread-per-request server with 10,000 threads forces the scheduler to manage 10,000 schedulable entities - the context switch overhead becomes significant. A thread pool with 200 threads bounds scheduling overhead. An event-driven server with one thread eliminates scheduling overhead entirely for I/O-bound work.

Second, tail latency. CFS's fair scheduling means a latency-sensitive service can be delayed by a colocated batch process that happens to have the lowest vruntime. This is why production services at FAANG use cgroup-based CPU isolation - to give each service its own scheduling domain with guaranteed CPU time.

Third, the choice between processes and threads. Process context switches are more expensive than thread switches because they involve TLB flushes. A microservice that handles 50,000 requests per second needs to minimize context switch cost. Using threads within a process (or goroutines within a Go runtime) avoids the TLB flush overhead."

Tip: For the interview: The most powerful scheduling answer connects a specific algorithm property to a specific system design consequence. "Round Robin provides bounded response time, which is why web servers use thread pools with Round Robin scheduling - it guarantees that no request waits longer than pool_size × quantum before getting attention." This type of connection is what separates a textbook answer from a strong interview answer.

How to Practice

Scheduling calculations need to become automatic. Spend one practice session doing this:

Take 4 processes with different arrival times and burst times. Calculate the schedule and metrics under FCFS, SJF, Round Robin (quantum = 2), and Priority. Do the calculations by hand, on paper, without a computer. Check your work by writing a simulation.

Then do the verbal practice. Set a 2-minute timer. Pick one of the five questions above. Deliver the answer out loud. Focus on structure: name the tradeoff, explain the mechanism, give the recommendation. When you can answer all five questions in under 2 minutes each, you are ready.

Exercise: Starter: Given P1 (arrival=0, burst=7, priority=2), P2 (arrival=1, burst=3, priority=1), P3 (arrival=2, burst=2, priority=3), calculate average waiting time under FCFS, SJF, and Priority. Which algorithm gives the best result?

Intermediate: Calculate the average waiting time for the same three processes under Round Robin with quantum=2. Then compare all four algorithms side by side. Which would you choose for (a) a batch processing system, (b) an interactive desktop, (c) a web server?

Advanced: Design a scheduling policy for a web server that handles two types of requests: health checks (must complete within 10 ms, arrive every second) and user requests (should complete within 200 ms, arrive at variable rates). The server has a thread pool of 200 threads. What scheduling algorithm would you use within the thread pool? How would you handle overload (when more requests arrive than the pool can handle)? How would you ensure health checks are always responsive even under heavy user traffic?

Back to Operating Systems