Interview Problem Types
Scheduling Problems
Read aloud is unavailable in this browser.
The CPU Scheduling Interview Domain
CPU scheduling represents one of the most mathematically rigorous and frequently tested areas in operating systems interviews. These problems assess your understanding of fundamental OS concepts, your ability to trace algorithm behavior step-by-step, your numerical computation skills under pressure, and your capacity to reason about performance tradeoffs.
Scheduling problems are deceptively simple in appearance but require precise execution. A single off-by-one error in arrival time handling, an incorrect understanding of preemption semantics, or confusion about how time quantum expiration works can cascade into completely wrong answers. This page provides the comprehensive framework and systematic methodology needed to master every scheduling problem variant you'll encounter.
By the end of this page, you will be able to: (1) Construct accurate Gantt charts for any scheduling algorithm, (2) Calculate all scheduling metrics—turnaround time, waiting time, response time, throughput, and CPU utilization—with precision, (3) Handle edge cases that trip up most candidates, (4) Compare algorithms analytically, and (5) Solve advanced multi-queue and real-time scheduling problems.
The Scheduling Problem Taxonomy
Before diving into specific algorithms, you must understand the problem space. Scheduling interview problems can be classified along several dimensions, and recognizing the problem type immediately is half the battle.
Dimension 1: Preemption Model
-
Non-preemptive scheduling: Once a process starts executing, it runs to completion (or until it voluntarily yields). The scheduler only makes decisions when a process terminates or blocks. Algorithms: FCFS, SJF (non-preemptive)
-
Preemptive scheduling: The scheduler can interrupt a running process to switch to another. Decisions occur at process arrival, timer interrupts, or priority changes. Algorithms: SRTF, Round Robin, Preemptive Priority, MLFQ
Dimension 2: Information Availability
-
Offline scheduling: All process information (arrival times, burst times) is known in advance. This allows optimal solutions. Most interview problems fall here.
-
Online scheduling: Processes arrive dynamically with unknown future arrivals. The scheduler operates with incomplete information. This is the real-world scenario.
Dimension 3: Optimization Criteria
- Minimize average turnaround time: How quickly processes complete from arrival to termination
- Minimize average waiting time: How long processes spend in the ready queue
- Minimize average response time: How quickly processes first get CPU access
- Maximize throughput: How many processes complete per unit time
- Maximize CPU utilization: What fraction of time the CPU is executing processes
- Ensure fairness: Prevent starvation, bound waiting times
| Algorithm | Preemptive? | Selection Criterion | Optimal For | Starvation Risk |
|---|---|---|---|---|
| FCFS (First-Come First-Served) | No | Arrival order | Simplicity | No |
| SJF (Shortest Job First) | No | Shortest burst time | Avg. turnaround (non-preemptive) | Yes (long jobs) |
| SRTF (Shortest Remaining Time First) | Yes | Shortest remaining time | Avg. turnaround (preemptive) | Yes (long jobs) |
| LRTF (Longest Remaining Time First) | Yes | Longest remaining time | Special cases | Yes (short jobs) |
| HRRN (Highest Response Ratio Next) | No | Highest (W+S)/S ratio | Balance + no starvation | No |
| Round Robin | Yes | Time quantum rotation | Avg. response time, fairness | No |
| Priority Scheduling | Either | Priority value | Importance ordering | Yes (low priority) |
| MLFQ (Multi-Level Feedback Queue) | Yes | Dynamic priority/history | Adaptive behavior | Configurable |
When presented with a scheduling problem, immediately identify: (1) Which algorithm? (2) Preemptive or non-preemptive? (3) What metric is being asked? (4) Are there any special conditions (priorities, time quantum, IO bursts)? This classification prevents you from applying the wrong algorithm variant.
Essential Metric Definitions with Mathematical Precision
Scheduling metrics form the quantitative basis for evaluating algorithm performance. You must understand these definitions precisely—interviewers test whether you know the exact formulas and can apply them correctly.
Process Lifecycle Timestamps
For each process P with:
- Arrival Time (AT): When P enters the ready queue
- Start Time (ST): When P first receives CPU
- Completion Time (CT): When P finishes execution entirely
- Burst Time (BT): Total CPU time P requires
Derived Metrics (Per Process)
| Metric | Formula | Interpretation | Optimal Value |
|---|---|---|---|
| Turnaround Time (TAT) | CT - AT | Total time from arrival to completion | Minimize |
| Waiting Time (WT) | TAT - BT = CT - AT - BT | Time spent waiting in ready queue | Minimize |
| Response Time (RT) | ST - AT | Time from arrival to first CPU access | Minimize |
| Normalized Turnaround | TAT / BT | Turnaround relative to service time | Minimize (≥1) |
System-Wide Metrics
Throughput = Number of processes completed / Total time span
CPU Utilization = (Total burst time of all processes) / (Completion time of last process - Arrival time of first process) × 100%
Alternatively: CPU Utilization = (Total time CPU was busy) / (Total elapsed time) × 100%
Average Turnaround Time = Σ(TAT for all processes) / Number of processes
Average Waiting Time = Σ(WT for all processes) / Number of processes
Average Response Time = Σ(RT for all processes) / Number of processes
Waiting Time and Response Time are NOT the same in preemptive scheduling! Response Time measures only until first CPU access, while Waiting Time accumulates ALL time spent in the ready queue (including when preempted). For non-preemptive algorithms, Response Time = Waiting Time only if the process never blocks.
Waiting Time Calculation Methods
There are two equivalent methods to compute waiting time, and you should know both:
Method 1: Direct Formula WT = TAT - BT = CT - AT - BT
Method 2: Summation of Wait Intervals Sum all time intervals when the process was in the ready queue but not executing.
For preemptive algorithms, Method 2 is often more intuitive during step-by-step tracing:
WT = (First execution start - Arrival) + Σ(Each preemption gap duration)
Where preemption gap = (Resume time - Preemption time) for each preemption event.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
class Process: def __init__(self, pid: str, arrival_time: int, burst_time: int): self.pid = pid self.arrival_time = arrival_time self.burst_time = burst_time self.remaining_time = burst_time self.start_time = -1 # -1 indicates not yet started self.completion_time = 0 @property def turnaround_time(self) -> int: """Total time from arrival to completion.""" return self.completion_time - self.arrival_time @property def waiting_time(self) -> int: """Time spent waiting in ready queue (not executing).""" return self.turnaround_time - self.burst_time @property def response_time(self) -> int: """Time from arrival until first CPU access.""" if self.start_time == -1: raise ValueError(f"Process {self.pid} never started") return self.start_time - self.arrival_time @property def normalized_turnaround(self) -> float: """Turnaround time relative to service requirement.""" return self.turnaround_time / self.burst_time if self.burst_time > 0 else 0 def calculate_system_metrics(processes: list[Process], schedule_end: int) -> dict: """Calculate system-wide scheduling metrics.""" n = len(processes) total_burst = sum(p.burst_time for p in processes) schedule_start = min(p.arrival_time for p in processes) avg_turnaround = sum(p.turnaround_time for p in processes) / n avg_waiting = sum(p.waiting_time for p in processes) / n avg_response = sum(p.response_time for p in processes) / n elapsed_time = schedule_end - schedule_start cpu_utilization = (total_burst / elapsed_time) * 100 if elapsed_time > 0 else 0 throughput = n / elapsed_time if elapsed_time > 0 else 0 return { "avg_turnaround_time": avg_turnaround, "avg_waiting_time": avg_waiting, "avg_response_time": avg_response, "cpu_utilization_percent": cpu_utilization, "throughput": throughput }FCFS (First-Come First-Served): Complete Analysis
FCFS is the simplest scheduling algorithm: processes execute in the order they arrive. Despite its simplicity, FCFS problems test your ability to handle arrival time gaps, compute metrics correctly, and understand the convoy effect.
Algorithm Specification
- Maintain a ready queue ordered by arrival time
- When CPU becomes idle, select the process at the front of the queue
- Execute the selected process to completion (non-preemptive)
- If no process is ready when CPU is idle, CPU remains idle until next arrival
Edge Cases to Handle
- Simultaneous arrivals: If multiple processes arrive at the same time, use process ID order (or problem specification) as tiebreaker
- CPU idle periods: When no process is available, the Gantt chart shows an idle gap
- Long process first: The convoy effect occurs when short processes queue behind a long process
The convoy effect is FCFS's fundamental weakness. If a CPU-bound process with a long burst time arrives first, all subsequent short processes must wait behind it, dramatically increasing average waiting time. This is why FCFS performs poorly when process burst times vary significantly.
Worked Example: FCFS with CPU Idle Time
Consider the following processes:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 2 | 3 |
| P3 | 4 | 1 |
| P4 | 8 | 2 |
Step-by-Step Execution:
- t=0: P1 arrives and starts immediately (only process available)
- t=2: P2 arrives, enters ready queue (P1 still executing)
- t=4: P1 completes (CT=4). P3 arrives. Ready queue: [P2, P3]. P2 starts.
- t=7: P2 completes (CT=7). Ready queue: [P3]. P3 starts.
- t=8: P4 arrives. P3 completes (CT=8). P4 starts immediately.
- t=10: P4 completes (CT=10).
Gantt Chart:
| P1 | P2 | P3 | P4 |
0 4 7 8 10
| Process | AT | BT | CT | TAT (CT-AT) | WT (TAT-BT) | RT (ST-AT) |
|---|---|---|---|---|---|---|
| P1 | 0 | 4 | 4 | 4 | 0 | 0 |
| P2 | 2 | 3 | 7 | 5 | 2 | 2 |
| P3 | 4 | 1 | 8 | 4 | 3 | 3 |
| P4 | 8 | 2 | 10 | 2 | 0 | 0 |
Average Metrics:
- Average Turnaround Time = (4 + 5 + 4 + 2) / 4 = 3.75 time units
- Average Waiting Time = (0 + 2 + 3 + 0) / 4 = 1.25 time units
- Average Response Time = (0 + 2 + 3 + 0) / 4 = 1.25 time units
- CPU Utilization = (4 + 3 + 1 + 2) / (10 - 0) × 100% = 100% (no idle time in this case)
- Throughput = 4 / 10 = 0.4 processes per time unit
Note: For FCFS (non-preemptive), Response Time always equals Waiting Time since each process waits until it can run to completion without interruption.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
def fcfs_schedule(processes: list[Process]) -> list[tuple[str, int, int]]: """ Execute FCFS scheduling algorithm. Returns: List of (process_id, start_time, end_time) tuples for Gantt chart. """ # Sort by arrival time, then by process ID for ties sorted_processes = sorted(processes, key=lambda p: (p.arrival_time, p.pid)) gantt_chart = [] current_time = 0 for process in sorted_processes: # Handle CPU idle time if process hasn't arrived yet if current_time < process.arrival_time: gantt_chart.append(("IDLE", current_time, process.arrival_time)) current_time = process.arrival_time # Record start time (first time this process gets CPU) process.start_time = current_time # Execute to completion (non-preemptive) start = current_time end = current_time + process.burst_time gantt_chart.append((process.pid, start, end)) # Update state process.completion_time = end process.remaining_time = 0 current_time = end return gantt_chart def print_gantt_chart(chart: list[tuple[str, int, int]]) -> None: """Display Gantt chart in visual format.""" print("Gantt Chart:") line1 = "|" line2 = "0" for pid, start, end in chart: duration = end - start label = f" {pid} ".center(duration * 2) line1 += label + "|" line2 += " " * (duration * 2) + str(end) print(line1) print(line2)SJF and SRTF: Optimal Average Turnaround Algorithms
Shortest Job First (SJF) and its preemptive variant Shortest Remaining Time First (SRTF) are provably optimal for minimizing average turnaround time (and therefore average waiting time). Understanding why they're optimal and how to execute them precisely is essential.
Optimality Proof Intuition
SJF minimizes average waiting time because shorter jobs complete quickly, reducing the wait time accumulated by all jobs behind them. Mathematically, if you have jobs with burst times b₁ < b₂ < ... < bₙ, scheduling them in ascending order minimizes Σ(waiting times).
SJF (Non-Preemptive) Algorithm
- When the CPU becomes idle, examine all processes currently in the ready queue
- Select the process with the shortest burst time
- Execute to completion
- Ties: Use arrival time (earlier first) or process ID as tiebreaker
SRTF (Preemptive SJF) Algorithm
- At every scheduling decision point (process arrival, process completion), examine all ready processes
- Select the process with the shortest remaining burst time
- If a newly arrived process has shorter remaining time than the currently running process, preempt
- Continue until all processes complete
SRTF makes scheduling decisions at: (1) Process arrival - check if new process has shorter remaining time than current, (2) Process completion - select next shortest remaining time. NOT at arbitrary time intervals! This is different from Round Robin.
Worked Example: SRTF with Preemptions
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 1 | 4 |
| P3 | 2 | 1 |
| P4 | 3 | 4 |
Detailed Execution Trace:
- t=0: P1 arrives (remaining=7). P1 starts.
- t=1: P2 arrives (remaining=4). P1 has remaining=6. Since 4 < 6, preempt P1, start P2.
- t=2: P3 arrives (remaining=1). P2 has remaining=3. Since 1 < 3, preempt P2, start P3.
- t=3: P3 completes. P4 arrives (remaining=4). Ready: [P1(6), P2(3), P4(4)]. P2 has shortest (3). P2 starts.
- t=6: P2 completes. Ready: [P1(6), P4(4)]. P4 has shortest (4). P4 starts.
- t=10: P4 completes. Ready: [P1(6)]. P1 starts.
- t=16: P1 completes.
Gantt Chart:
| P1 | P2 | P3 | P2 | P4 | P1 |
0 1 2 3 6 10 16
| Process | AT | BT | CT | TAT | WT | RT |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 16 | 9 | 0 |
| P2 | 1 | 4 | 6 | 5 | 1 | 0 |
| P3 | 2 | 1 | 3 | 1 | 0 | 0 |
| P4 | 3 | 4 | 10 | 7 | 3 | 3 |
Average Metrics:
- Average TAT = (16 + 5 + 1 + 7) / 4 = 7.25 time units
- Average WT = (9 + 1 + 0 + 3) / 4 = 3.25 time units
- Average RT = (0 + 0 + 0 + 3) / 4 = 0.75 time units
Comparison: What if we used FCFS?
With FCFS, the Gantt chart would be: P1(0-7), P2(7-11), P3(11-12), P4(12-16)
- Average TAT = (7 + 10 + 10 + 13) / 4 = 10 time units
- Average WT = (0 + 6 + 9 + 9) / 4 = 6 time units
SRTF achieves 54% better waiting time than FCFS for this workload, demonstrating its optimality for turnaround/waiting time.
Both SJF and SRTF can cause starvation of long jobs if short jobs keep arriving. A long job may wait indefinitely. This is a critical weakness—interviewers often ask how to mitigate this (answer: aging, where priority increases with wait time).
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
from heapq import heappush, heappopfrom typing import Optional def srtf_schedule(processes: list[Process]) -> list[tuple[str, int, int]]: """ Execute SRTF (Shortest Remaining Time First) scheduling. Returns Gantt chart as list of (pid, start, end) tuples. """ # Sort by arrival time sorted_procs = sorted(processes, key=lambda p: p.arrival_time) gantt_chart = [] current_time = 0 process_index = 0 # Next process to potentially arrive n = len(processes) completed = 0 # Priority queue: (remaining_time, arrival_time, pid, process) ready_queue = [] current_process: Optional[Process] = None current_start_time = 0 while completed < n: # Add all processes that have arrived by current_time while process_index < n and sorted_procs[process_index].arrival_time <= current_time: p = sorted_procs[process_index] heappush(ready_queue, (p.remaining_time, p.arrival_time, p.pid, p)) process_index += 1 if not ready_queue: # CPU idle - jump to next arrival if process_index < n: next_arrival = sorted_procs[process_index].arrival_time if current_process: gantt_chart.append((current_process.pid, current_start_time, current_time)) current_process = None gantt_chart.append(("IDLE", current_time, next_arrival)) current_time = next_arrival continue # Get process with shortest remaining time remaining, _, pid, process = heappop(ready_queue) # Check if we're switching processes (for Gantt chart) if current_process != process: if current_process: gantt_chart.append((current_process.pid, current_start_time, current_time)) # Put current process back in queue if not complete if current_process.remaining_time > 0: heappush(ready_queue, ( current_process.remaining_time, current_process.arrival_time, current_process.pid, current_process )) current_process = process current_start_time = current_time if process.start_time == -1: process.start_time = current_time # Determine how long we run this process # Run until next arrival or completion, whichever is first if process_index < n: next_arrival = sorted_procs[process_index].arrival_time run_time = min(process.remaining_time, next_arrival - current_time) else: run_time = process.remaining_time current_time += run_time process.remaining_time -= run_time if process.remaining_time == 0: process.completion_time = current_time completed += 1 gantt_chart.append((process.pid, current_start_time, current_time)) current_process = None return gantt_chartRound Robin: Time-Slicing and Fairness
Round Robin (RR) is the most common scheduling algorithm for interactive systems because it provides fairness and bounded response time. It's also the most error-prone algorithm in interviews due to subtle edge cases in queue management.
Algorithm Specification
- Processes execute for a fixed time quantum (q)
- After quantum expires, the process is preempted and moved to the back of the ready queue
- If a process completes before its quantum expires, CPU immediately switches to next process
- Newly arriving processes are added to the back of the ready queue
Critical Edge Case: Simultaneous Events
What happens when a process's quantum expires at the same time a new process arrives?
Standard Convention: The arriving process joins the queue BEFORE the preempted process. This is crucial for getting correct answers!
Order at time t when quantum expires:
- Running process is preempted
- New arrivals at time t are added to queue
- Preempted process is added to queue
- Scheduler selects from front of queue
The order in which processes join the ready queue determines the entire execution sequence. Always clarify or follow the standard convention: arrivals at time t join before the process being preempted at time t. Different assumptions yield different answers!
Worked Example: Round Robin with q=2
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 1 |
| P4 | 4 | 2 |
Detailed Queue State Trace:
- t=0: P1 arrives. Queue: [P1]. P1 starts.
- t=1: P2 arrives. Queue: [P2]. P1 executing (remaining=4).
- t=2: Quantum expires. P3 arrives. Queue: [P2, P3, P1(rem=3)]. P2 starts.
- t=4: Quantum expires. P4 arrives. Queue: [P3, P1(3), P4, P2(rem=1)]. P3 starts.
- t=5: P3 completes (only needed 1). Queue: [P1(3), P4, P2(1)]. P1 starts.
- t=7: Quantum expires. Queue: [P4, P2(1), P1(rem=1)]. P4 starts.
- t=9: P4 completes. Queue: [P2(1), P1(1)]. P2 starts.
- t=10: P2 completes. Queue: [P1(1)]. P1 starts.
- t=11: P1 completes.
Gantt Chart:
| P1 | P2 | P3 | P1 | P4 | P2 | P1 |
0 2 4 5 7 9 10 11
| Process | AT | BT | CT | TAT | WT | RT |
|---|---|---|---|---|---|---|
| P1 | 0 | 5 | 11 | 11 | 6 | 0 |
| P2 | 1 | 3 | 10 | 9 | 6 | 1 |
| P3 | 2 | 1 | 5 | 3 | 2 | 2 |
| P4 | 4 | 2 | 9 | 5 | 3 | 3 |
Time Quantum Tradeoffs
The choice of time quantum q significantly affects performance:
| q Value | Context Switches | Response Time | Throughput | Behavior |
|---|---|---|---|---|
| Very small (q→0) | Very high | Excellent | Poor (overhead dominates) | Approaches processor sharing |
| Very large (q→∞) | Minimal | Poor | Good | Degenerates to FCFS |
| Optimal | Moderate | Good | Good | Balances responsiveness and overhead |
Rule of Thumb: q should be large enough that 80% of CPU bursts complete within a single quantum, minimizing unnecessary context switches while maintaining responsiveness.
Context Switch Overhead: Each preemption incurs overhead (typically 1-10 microseconds on modern systems). If q is too small relative to context switch time, the CPU spends more time switching than executing useful work.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
from collections import deque def round_robin_schedule(processes: list[Process], quantum: int) -> list[tuple[str, int, int]]: """ Execute Round Robin scheduling with given time quantum. Implements standard convention: arrivals join before preempted process. """ # Sort by arrival time sorted_procs = sorted(processes, key=lambda p: (p.arrival_time, p.pid)) gantt_chart = [] ready_queue = deque() current_time = 0 process_index = 0 n = len(processes) completed = 0 # Add initial processes arriving at time 0 while process_index < n and sorted_procs[process_index].arrival_time <= current_time: ready_queue.append(sorted_procs[process_index]) process_index += 1 while completed < n: if not ready_queue: # CPU idle - jump to next arrival if process_index < n: next_arrival_time = sorted_procs[process_index].arrival_time gantt_chart.append(("IDLE", current_time, next_arrival_time)) current_time = next_arrival_time while process_index < n and sorted_procs[process_index].arrival_time <= current_time: ready_queue.append(sorted_procs[process_index]) process_index += 1 continue # Get next process from front of queue process = ready_queue.popleft() # Record first execution time if process.start_time == -1: process.start_time = current_time # Execute for quantum or until completion execution_time = min(quantum, process.remaining_time) start_time = current_time current_time += execution_time process.remaining_time -= execution_time # Record in Gantt chart gantt_chart.append((process.pid, start_time, current_time)) # Standard convention: Add new arrivals BEFORE preempted process while process_index < n and sorted_procs[process_index].arrival_time <= current_time: ready_queue.append(sorted_procs[process_index]) process_index += 1 # Check if process completed or needs to be re-queued if process.remaining_time == 0: process.completion_time = current_time completed += 1 else: # Preempted - add to back of queue (after new arrivals) ready_queue.append(process) return gantt_chartPriority Scheduling and Multi-Level Queues
Priority scheduling introduces an external preference ordering on processes. It comes in multiple flavors, and interview problems often combine priority with other mechanisms.
Priority Conventions
Be careful: different systems use different conventions!
- Lower number = Higher priority: Priority 0 is most important (Unix tradition)
- Higher number = Higher priority: Priority 100 is more important than 50
Always clarify or check which convention the problem uses!
Priority Scheduling Variants
- Static Priority, Non-Preemptive: Priority assigned once, run to completion
- Static Priority, Preemptive: Higher-priority arrival preempts lower-priority running process
- Dynamic Priority: Priority changes over time (aging, MLFQ)
Priority Inversion Problem
A nasty edge case: A high-priority process H is blocked waiting for resource held by low-priority process L. A medium-priority process M preempts L. Now H is indirectly blocked by M, which has lower priority than H!
Solutions:
- Priority Inheritance: L temporarily inherits H's priority
- Priority Ceiling: Each resource has a priority ceiling; acquiring it raises priority
Multi-Level Queue Scheduling
Processes are partitioned into classes with different priority levels. Each queue may use a different scheduling algorithm.
Example Configuration:
- Queue 0 (Highest): System processes - FCFS
- Queue 1: Interactive processes - Round Robin (q=8)
- Queue 2: Batch processes - FCFS
- Queue 3 (Lowest): Student processes - Round Robin (q=16)
Processes are permanently assigned to queues based on classification.
Multi-Level Feedback Queue (MLFQ)
MLFQ allows processes to move between queues based on behavior:
- New processes start in highest-priority queue
- If a process uses entire quantum, it moves down a level (CPU-bound behavior)
- If a process yields before quantum, it stays at same level (I/O-bound behavior)
- Periodic boosting prevents starvation
MLFQ automatically learns process characteristics and optimizes accordingly.
| Rule | Description | Purpose |
|---|---|---|
| Rule 1 | If Priority(A) > Priority(B), A runs | Higher priority executes first |
| Rule 2 | If Priority(A) = Priority(B), A & B run in RR | Fair sharing within level |
| Rule 3 | New jobs start at highest priority | Assume interactive until proven otherwise |
| Rule 4 | If job uses entire quantum, priority drops | Penalize CPU-bound behavior |
| Rule 5 | After time period S, boost all jobs to top queue | Prevent starvation |
MLFQ problems test whether you understand adaptive scheduling. Key insight: MLFQ approximates SJF without knowing burst times in advance. Short jobs complete quickly at high priority; long jobs eventually drop to lower levels.
Advanced Scheduling Problem Patterns
Beyond basic algorithm execution, interviews may present advanced scheduling scenarios that test deeper understanding.
Pattern 1: Algorithm Comparison
"Given these processes, which algorithm provides the best average waiting time?"
Approach: Execute each algorithm, compute metrics, compare. Remember:
- SRTF is optimal for average waiting time (preemptive)
- SJF is optimal for average waiting time (non-preemptive)
- RR is optimal for average response time (small quantum)
- FCFS may be best when all burst times are equal
Pattern 2: Parameter Optimization
"What time quantum minimizes average waiting time for these processes?"
Approach: Try quantum values and analyze. Key insight: extremely small q introduces overhead; extremely large q becomes FCFS. Often optimal q is related to the mode or median of burst times.
Pattern 3: Algorithm Identification
"Given this Gantt chart, which scheduling algorithm was used?"
Analyze the pattern:
- Strict arrival order → FCFS
- Preemption at arrivals with shortest remaining → SRTF
- Regular preemption intervals → Round Robin
- No preemption, not arrival order → SJF or Priority
Pattern 4: Real-Time Scheduling
For real-time problems, you need different algorithms and analysis techniques.
Rate Monotonic Scheduling (RMS):
- Static priority based on period (shorter period = higher priority)
- Optimal for static-priority preemptive scheduling
- Schedulable if: Σ(Ci/Pi) ≤ n(2^(1/n) - 1)
For n=3: utilization bound = 0.78 (78%)
Earliest Deadline First (EDF):
- Dynamic priority based on absolute deadline
- Optimal for dynamic-priority scheduling
- Schedulable if: Σ(Ci/Pi) ≤ 1 (100% utilization possible)
Pattern 5: Multi-Processor Scheduling
With m processors, problems become significantly more complex:
- Global queue vs. per-processor queues
- Effect of processor affinity
- Load balancing considerations
- Amdahl's Law for parallelism limits
For any scheduling problem: (1) Identify the algorithm and variant, (2) Draw the timeline step-by-step, (3) Track the ready queue state carefully, (4) Build the Gantt chart incrementally, (5) Calculate metrics from the Gantt chart. Never skip the detailed trace—mental execution leads to errors.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.