6a:T64f,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 times6b:T7fa,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 }6c:T603,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)6d:T4ab,**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** 1. When the CPU becomes idle, examine all processes currently in the ready queue 2. Select the process with the shortest burst time 3. Execute to completion 4. Ties: Use arrival time (earlier first) or process ID as tiebreaker **SRTF (Preemptive SJF) Algorithm** 1. At every scheduling decision point (process arrival, process completion), examine all ready processes 2. Select the process with the shortest *remaining* burst time 3. If a newly arrived process has shorter remaining time than the currently running process, preempt 4. Continue until all processes complete6e:Tc57,from heapq import heappush, heappop from 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_chart6f:T41b,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** 1. Processes execute for a fixed **time quantum (q)** 2. After quantum expires, the process is preempted and moved to the back of the ready queue 3. If a process completes before its quantum expires, CPU immediately switches to next process 4. 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: 1. Running process is preempted 2. New arrivals at time t are added to queue 3. Preempted process is added to queue 4. Scheduler selects from front of queue70:T9c2,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_chart71:T4a4,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** 1. **Static Priority, Non-Preemptive**: Priority assigned once, run to completion 2. **Static Priority, Preemptive**: Higher-priority arrival preempts lower-priority running process 3. **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 priority72:T488,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 Priority63:{"json":{"id":"seed_586b8278a92bee674ee2903ee3e97b5e","slug":"interview-problem-types","category":"Operating Systems","topic":"Interview Problem Types","title":"Interview Problem Types","description":"Master the systematic categorization and solution strategies for operating systems interview problems. This module covers scheduling, synchronization, memory, file system, and system design problems with deep analysis and worked examples.","difficulty":"ADVANCED","estimatedMinutes":180,"pages":[{"id":"seed_dc50c4e9e564a79edb58e2d340633658","title":"Scheduling Problems","order":0,"content":[{"id":"opening-hook","title":"The CPU Scheduling Interview Domain","content":[{"data":{"content":"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.\n\n**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."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"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.","variant":"info"},"type":"callout"}]},{"id":"scheduling-taxonomy","title":"The Scheduling Problem Taxonomy","content":[{"data":{"content":"$6a"},"type":"text"},{"data":{"rows":[["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"]],"caption":"Scheduling Algorithm Classification Matrix","headers":["Algorithm","Preemptive?","Selection Criterion","Optimal For","Starvation Risk"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Interview Strategy","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"essential-metrics","title":"Essential Metric Definitions with Mathematical Precision","content":[{"data":{"content":"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.\n\n**Process Lifecycle Timestamps**\n\nFor each process P with:\n- **Arrival Time (AT)**: When P enters the ready queue\n- **Start Time (ST)**: When P first receives CPU\n- **Completion Time (CT)**: When P finishes execution entirely\n- **Burst Time (BT)**: Total CPU time P requires\n\n**Derived Metrics (Per Process)**"},"type":"text"},{"data":{"rows":[["**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)"]],"caption":"Core Scheduling Metrics and Their Formulas","headers":["Metric","Formula","Interpretation","Optimal Value"]},"type":"table"},{"data":{"content":"**System-Wide Metrics**\n\n**Throughput** = Number of processes completed / Total time span\n\n**CPU Utilization** = (Total burst time of all processes) / (Completion time of last process - Arrival time of first process) × 100%\n\nAlternatively: CPU Utilization = (Total time CPU was busy) / (Total elapsed time) × 100%\n\n**Average Turnaround Time** = Σ(TAT for all processes) / Number of processes\n\n**Average Waiting Time** = Σ(WT for all processes) / Number of processes\n\n**Average Response Time** = Σ(RT for all processes) / Number of processes"},"type":"text"},{"data":{"icon":"AlertCircle","title":"Critical Distinction: Waiting Time vs Response Time","content":"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.","variant":"warning"},"type":"callout"},{"data":{"content":"**Waiting Time Calculation Methods**\n\nThere are two equivalent methods to compute waiting time, and you should know both:\n\n**Method 1: Direct Formula**\nWT = TAT - BT = CT - AT - BT\n\n**Method 2: Summation of Wait Intervals**\nSum all time intervals when the process was in the ready queue but not executing.\n\nFor preemptive algorithms, Method 2 is often more intuitive during step-by-step tracing:\n\nWT = (First execution start - Arrival) + Σ(Each preemption gap duration)\n\nWhere preemption gap = (Resume time - Preemption time) for each preemption event."},"type":"text"},{"data":{"fileName":"scheduling_metrics.py","languages":[{"code":"$6b","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":2},{"id":"fcfs-analysis","title":"FCFS (First-Come First-Served): Complete Analysis","content":[{"data":{"content":"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.\n\n**Algorithm Specification**\n\n1. Maintain a ready queue ordered by arrival time\n2. When CPU becomes idle, select the process at the front of the queue\n3. Execute the selected process to completion (non-preemptive)\n4. If no process is ready when CPU is idle, CPU remains idle until next arrival\n\n**Edge Cases to Handle**\n\n- **Simultaneous arrivals**: If multiple processes arrive at the same time, use process ID order (or problem specification) as tiebreaker\n- **CPU idle periods**: When no process is available, the Gantt chart shows an idle gap\n- **Long process first**: The convoy effect occurs when short processes queue behind a long process"},"type":"text"},{"data":{"icon":"Info","title":"The Convoy Effect","content":"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.","variant":"note"},"type":"callout"},{"data":{"content":"**Worked Example: FCFS with CPU Idle Time**\n\nConsider the following processes:"},"type":"text"},{"data":{"rows":[["P1","0","4"],["P2","2","3"],["P3","4","1"],["P4","8","2"]],"headers":["Process","Arrival Time","Burst Time"]},"type":"table"},{"data":{"content":"**Step-by-Step Execution:**\n\n- **t=0**: P1 arrives and starts immediately (only process available)\n- **t=2**: P2 arrives, enters ready queue (P1 still executing)\n- **t=4**: P1 completes (CT=4). P3 arrives. Ready queue: [P2, P3]. P2 starts.\n- **t=7**: P2 completes (CT=7). Ready queue: [P3]. P3 starts.\n- **t=8**: P4 arrives. P3 completes (CT=8). P4 starts immediately.\n- **t=10**: P4 completes (CT=10).\n\n**Gantt Chart:**\n```\n| P1 | P2 | P3 | P4 |\n0 4 7 8 10\n```"},"type":"text"},{"data":{"rows":[["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"]],"caption":"FCFS Metric Calculations","headers":["Process","AT","BT","CT","TAT (CT-AT)","WT (TAT-BT)","RT (ST-AT)"]},"type":"table"},{"data":{"content":"**Average Metrics:**\n- Average Turnaround Time = (4 + 5 + 4 + 2) / 4 = **3.75 time units**\n- Average Waiting Time = (0 + 2 + 3 + 0) / 4 = **1.25 time units**\n- Average Response Time = (0 + 2 + 3 + 0) / 4 = **1.25 time units**\n- CPU Utilization = (4 + 3 + 1 + 2) / (10 - 0) × 100% = **100%** (no idle time in this case)\n- Throughput = 4 / 10 = **0.4 processes per time unit**\n\nNote: For FCFS (non-preemptive), Response Time always equals Waiting Time since each process waits until it can run to completion without interruption."},"type":"text"},{"data":{"fileName":"fcfs_scheduler.py","languages":[{"code":"$6c","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"sjf-srtf-analysis","title":"SJF and SRTF: Optimal Average Turnaround Algorithms","content":[{"data":{"content":"$6d"},"type":"text"},{"data":{"icon":"AlertCircle","title":"SRTF Decision Points","content":"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.","variant":"warning"},"type":"callout"},{"data":{"content":"**Worked Example: SRTF with Preemptions**"},"type":"text"},{"data":{"rows":[["P1","0","7"],["P2","1","4"],["P3","2","1"],["P4","3","4"]],"headers":["Process","Arrival Time","Burst Time"]},"type":"table"},{"data":{"content":"**Detailed Execution Trace:**\n\n- **t=0**: P1 arrives (remaining=7). P1 starts.\n- **t=1**: P2 arrives (remaining=4). P1 has remaining=6. Since 4 < 6, **preempt P1**, start P2.\n- **t=2**: P3 arrives (remaining=1). P2 has remaining=3. Since 1 < 3, **preempt P2**, start P3.\n- **t=3**: P3 completes. P4 arrives (remaining=4). Ready: [P1(6), P2(3), P4(4)]. P2 has shortest (3). P2 starts.\n- **t=6**: P2 completes. Ready: [P1(6), P4(4)]. P4 has shortest (4). P4 starts.\n- **t=10**: P4 completes. Ready: [P1(6)]. P1 starts.\n- **t=16**: P1 completes.\n\n**Gantt Chart:**\n```\n| P1 | P2 | P3 | P2 | P4 | P1 |\n0 1 2 3 6 10 16\n```"},"type":"text"},{"data":{"rows":[["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"]],"caption":"SRTF Metric Calculations","headers":["Process","AT","BT","CT","TAT","WT","RT"]},"type":"table"},{"data":{"content":"**Average Metrics:**\n- Average TAT = (16 + 5 + 1 + 7) / 4 = **7.25 time units**\n- Average WT = (9 + 1 + 0 + 3) / 4 = **3.25 time units**\n- Average RT = (0 + 0 + 0 + 3) / 4 = **0.75 time units**\n\n**Comparison: What if we used FCFS?**\n\nWith FCFS, the Gantt chart would be: P1(0-7), P2(7-11), P3(11-12), P4(12-16)\n- Average TAT = (7 + 10 + 10 + 13) / 4 = **10 time units**\n- Average WT = (0 + 6 + 9 + 9) / 4 = **6 time units**\n\nSRTF achieves **54% better waiting time** than FCFS for this workload, demonstrating its optimality for turnaround/waiting time."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Starvation Risk","content":"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).","variant":"error"},"type":"callout"},{"data":{"fileName":"srtf_scheduler.py","languages":[{"code":"$6e","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"round-robin-analysis","title":"Round Robin: Time-Slicing and Fairness","content":[{"data":{"content":"$6f"},"type":"text"},{"data":{"icon":"AlertCircle","title":"Queue Ordering is Everything","content":"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!","variant":"warning"},"type":"callout"},{"data":{"content":"**Worked Example: Round Robin with q=2**"},"type":"text"},{"data":{"rows":[["P1","0","5"],["P2","1","3"],["P3","2","1"],["P4","4","2"]],"headers":["Process","Arrival Time","Burst Time"]},"type":"table"},{"data":{"content":"**Detailed Queue State Trace:**\n\n- **t=0**: P1 arrives. Queue: [P1]. P1 starts.\n- **t=1**: P2 arrives. Queue: [P2]. P1 executing (remaining=4).\n- **t=2**: Quantum expires. P3 arrives. Queue: [P2, P3, P1(rem=3)]. P2 starts.\n- **t=4**: Quantum expires. P4 arrives. Queue: [P3, P1(3), P4, P2(rem=1)]. P3 starts.\n- **t=5**: P3 completes (only needed 1). Queue: [P1(3), P4, P2(1)]. P1 starts.\n- **t=7**: Quantum expires. Queue: [P4, P2(1), P1(rem=1)]. P4 starts.\n- **t=9**: P4 completes. Queue: [P2(1), P1(1)]. P2 starts.\n- **t=10**: P2 completes. Queue: [P1(1)]. P1 starts.\n- **t=11**: P1 completes.\n\n**Gantt Chart:**\n```\n| P1 | P2 | P3 | P1 | P4 | P2 | P1 |\n0 2 4 5 7 9 10 11\n```"},"type":"text"},{"data":{"rows":[["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"]],"caption":"Round Robin (q=2) Metric Calculations","headers":["Process","AT","BT","CT","TAT","WT","RT"]},"type":"table"},{"data":{"content":"**Time Quantum Tradeoffs**\n\nThe choice of time quantum q significantly affects performance:"},"type":"text"},{"data":{"rows":[["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"]],"headers":["q Value","Context Switches","Response Time","Throughput","Behavior"]},"type":"table"},{"data":{"content":"**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.\n\n**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."},"type":"text"},{"data":{"fileName":"round_robin_scheduler.py","languages":[{"code":"$70","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":5},{"id":"priority-scheduling","title":"Priority Scheduling and Multi-Level Queues","content":[{"data":{"content":"$71"},"type":"text"},{"data":{"content":"**Multi-Level Queue Scheduling**\n\nProcesses are partitioned into classes with different priority levels. Each queue may use a different scheduling algorithm.\n\n**Example Configuration:**\n- **Queue 0 (Highest)**: System processes - FCFS\n- **Queue 1**: Interactive processes - Round Robin (q=8)\n- **Queue 2**: Batch processes - FCFS\n- **Queue 3 (Lowest)**: Student processes - Round Robin (q=16)\n\nProcesses are permanently assigned to queues based on classification.\n\n**Multi-Level Feedback Queue (MLFQ)**\n\nMLFQ allows processes to move between queues based on behavior:\n- New processes start in highest-priority queue\n- If a process uses entire quantum, it moves down a level (CPU-bound behavior)\n- If a process yields before quantum, it stays at same level (I/O-bound behavior)\n- Periodic boosting prevents starvation\n\nMLFQ automatically learns process characteristics and optimizes accordingly."},"type":"text"},{"data":{"rows":[["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"]],"caption":"MLFQ Rules","headers":["Rule","Description","Purpose"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"MLFQ in Interviews","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"advanced-problems","title":"Advanced Scheduling Problem Patterns","content":[{"data":{"content":"$72"},"type":"text"},{"data":{"content":"**Pattern 4: Real-Time Scheduling**\n\nFor real-time problems, you need different algorithms and analysis techniques.\n\n**Rate Monotonic Scheduling (RMS)**:\n- Static priority based on period (shorter period = higher priority)\n- Optimal for static-priority preemptive scheduling\n- Schedulable if: Σ(Ci/Pi) ≤ n(2^(1/n) - 1)\n\nFor n=3: utilization bound = 0.78 (78%)\n\n**Earliest Deadline First (EDF)**:\n- Dynamic priority based on absolute deadline\n- Optimal for dynamic-priority scheduling\n- Schedulable if: Σ(Ci/Pi) ≤ 1 (100% utilization possible)\n\n**Pattern 5: Multi-Processor Scheduling**\n\nWith m processors, problems become significantly more complex:\n- Global queue vs. per-processor queues\n- Effect of processor affinity\n- Load balancing considerations\n- Amdahl's Law for parallelism limits"},"type":"text"},{"data":{"icon":"Sparkles","title":"Problem-Solving Strategy Summary","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"practice-problems","title":"Practice Problems with Solutions","content":[{"data":{"content":"Test your understanding with these carefully selected problems that cover core concepts and common edge cases."},"type":"text"},{"data":{"icon":"Target","title":"Problem 1: SRTF with Ties","content":"Given processes: P1(AT=0, BT=4), P2(AT=1, BT=2), P3(AT=2, BT=2), P4(AT=3, BT=1). Use SRTF scheduling. Calculate average waiting time. **Tiebreaker**: When remaining times are equal, prefer the process that arrived earlier.","variant":"info"},"type":"callout"},{"data":{"content":"**Solution:**\n\n- t=0: P1 starts (remaining=4)\n- t=1: P2 arrives (rem=2). P1(rem=3) vs P2(rem=2). P2 wins, preempt P1.\n- t=2: P3 arrives (rem=2). P2(rem=1) vs P3(rem=2). P2 continues.\n- t=3: P2 completes. P4 arrives. Ready: [P1(3), P3(2), P4(1)]. P4 wins (shortest).\n- t=4: P4 completes. Ready: [P1(3), P3(2)]. P3 wins.\n- t=6: P3 completes. P1 runs.\n- t=9: P1 completes.\n\nGantt: |P1|P2|P4|P3|P1|\n 0 1 3 4 6 9\n\nMetrics:\n- P1: CT=9, TAT=9, WT=5\n- P2: CT=3, TAT=2, WT=0\n- P3: CT=6, TAT=4, WT=2\n- P4: CT=4, TAT=1, WT=0\n\n**Average WT = (5+0+2+0)/4 = 1.75**"},"type":"text"},{"data":{"icon":"Target","title":"Problem 2: Round Robin Context Switches","content":"Given processes: P1(AT=0, BT=10), P2(AT=0, BT=6), P3(AT=0, BT=2). Time quantum = 3. How many context switches occur? (Do not count the initial load or final termination.)","variant":"info"},"type":"callout"},{"data":{"content":"**Solution:**\n\nGantt: |P1|P2|P3|P1|P2|P1|\n 0 3 6 8 11 14 18\n\nExecution sequence: P1(3) → P2(3) → P3(2) → P1(3) → P2(3) → P1(4)\n\nContext switches (transitions between different processes or from idle):\n1. P1 → P2 at t=3\n2. P2 → P3 at t=6\n3. P3 → P1 at t=8\n4. P1 → P2 at t=11\n5. P2 → P1 at t=14\n\n**Answer: 5 context switches**"},"type":"text"},{"data":{"icon":"Target","title":"Problem 3: Comparing FCFS and SJF","content":"Processes: P1(AT=0, BT=8), P2(AT=1, BT=1), P3(AT=2, BT=3). Compare average turnaround time for FCFS vs SJF (non-preemptive). Which is better and by how much?","variant":"info"},"type":"callout"},{"data":{"content":"**Solution:**\n\n**FCFS:**\nGantt: |P1|P2|P3|\n 0 8 9 12\n\n- P1: TAT = 8-0 = 8\n- P2: TAT = 9-1 = 8\n- P3: TAT = 12-2 = 10\n- Avg TAT = (8+8+10)/3 = **8.67**\n\n**SJF (non-preemptive):**\nAt t=0, only P1 available → P1 runs to completion (non-preemptive!)\nAt t=8, ready: [P2, P3]. P2 is shorter.\n\nGantt: |P1|P2|P3|\n 0 8 9 12\n\n*Same as FCFS because P1 must complete before decisions are made!*\n\n**Answer: For this input, both give Avg TAT = 8.67**\n\n*Key insight: SJF only helps when decisions between multiple ready processes are possible at decision points.*"},"type":"text"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: Scheduling Problem Mastery","content":[{"data":{"type":"ordered","items":["**Classify the problem first**: Identify the algorithm, preemption model, metrics, and any special conditions before solving.","**Master metric formulas**: TAT = CT - AT, WT = TAT - BT, RT = ST - AT. Know them cold.","**Trace step-by-step**: Always draw the timeline and track ready queue state. Mental shortcuts cause errors.","**Handle edge cases**: Ties, simultaneous events, CPU idle periods, and queue ordering conventions are common traps.","**Know the tradeoffs**: FCFS is simple but convoy effect hurts. SJF/SRTF are optimal but cause starvation. RR provides fairness but incurs overhead.","**Practice algorithm identification**: Given a Gantt chart, be able to reverse-engineer which algorithm produced it."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have comprehensive knowledge of scheduling problems in OS interviews. The next page covers synchronization problems—another core interview category that tests your understanding of concurrency primitives, race conditions, and classic synchronization problems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_f0d9c76d84e249e017e1c1dd24baa60d","title":"Synchronization Problems","order":1,"content":null,"isLocked":true},{"id":"seed_1b6c23fae7e1ac41acc8b3ba5c1470d6","title":"Memory Calculations","order":2,"content":null,"isLocked":true},{"id":"seed_d51a0a5776c86dff5ef28686ebf413cb","title":"File System Calculations","order":3,"content":null,"isLocked":true},{"id":"seed_bd12ccee95159ea9dd0075bb5e8dcbb8","title":"System Design","order":4,"content":null,"isLocked":true}]}}