Scheduling Problems - Interview Problem Types | OneNoughtOne

0/236

Operating SystemsInterview Problem Types

Interview Problem Types

LevelAdvanced

Duration180 mins

TopicInterview Problem Types

1 / 5

Scheduling Problems

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.

What You Will Master

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

Scheduling Algorithm Classification Matrix
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

Interview Strategy

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)

Core Scheduling Metrics and Their Formulas
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

Critical Distinction: Waiting Time vs Response Time

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.

scheduling_metrics.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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

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

FCFS Metric Calculations
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.

fcfs_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 Decision Points

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

SRTF Metric Calculations
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.

Starvation Risk

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).

srtf_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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_chart

Round 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

Queue Ordering is Everything

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

Round Robin (q=2) Metric Calculations
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.

round_robin_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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_chart

Priority 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.

MLFQ Rules
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 in Interviews

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

Problem-Solving Strategy Summary

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.

Practice Problems with Solutions

Test your understanding with these carefully selected problems that cover core concepts and common edge cases.

Problem 1: SRTF with Ties

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.

Solution:

t=0: P1 starts (remaining=4)
t=1: P2 arrives (rem=2). P1(rem=3) vs P2(rem=2). P2 wins, preempt P1.
t=2: P3 arrives (rem=2). P2(rem=1) vs P3(rem=2). P2 continues.
t=3: P2 completes. P4 arrives. Ready: [P1(3), P3(2), P4(1)]. P4 wins (shortest).
t=4: P4 completes. Ready: [P1(3), P3(2)]. P3 wins.
t=6: P3 completes. P1 runs.
t=9: P1 completes.

Gantt: |P1|P2|P4|P3|P1| 0 1 3 4 6 9

Metrics:

P1: CT=9, TAT=9, WT=5
P2: CT=3, TAT=2, WT=0
P3: CT=6, TAT=4, WT=2
P4: CT=4, TAT=1, WT=0

Average WT = (5+0+2+0)/4 = 1.75

Problem 2: Round Robin Context Switches

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.)

Solution:

Gantt: |P1|P2|P3|P1|P2|P1| 0 3 6 8 11 14 18

Execution sequence: P1(3) → P2(3) → P3(2) → P1(3) → P2(3) → P1(4)

Context switches (transitions between different processes or from idle):

P1 → P2 at t=3
P2 → P3 at t=6
P3 → P1 at t=8
P1 → P2 at t=11
P2 → P1 at t=14

Answer: 5 context switches

Problem 3: Comparing FCFS and SJF

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?

Solution:

FCFS: Gantt: |P1|P2|P3| 0 8 9 12

P1: TAT = 8-0 = 8
P2: TAT = 9-1 = 8
P3: TAT = 12-2 = 10
Avg TAT = (8+8+10)/3 = 8.67

SJF (non-preemptive): At t=0, only P1 available → P1 runs to completion (non-preemptive!) At t=8, ready: [P2, P3]. P2 is shorter.

Gantt: |P1|P2|P3| 0 8 9 12

Same as FCFS because P1 must complete before decisions are made!

Answer: For this input, both give Avg TAT = 8.67

Key insight: SJF only helps when decisions between multiple ready processes are possible at decision points.

Summary: Scheduling Problem Mastery

Key Takeaways

•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.

Page Complete

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.

Operating SystemsInterview Problem Types

Interview Problem Types

LevelAdvanced

Duration180 mins

TopicInterview Problem Types

1 / 5

Scheduling Problems

The CPU Scheduling Interview Domain

What You Will Master

The Scheduling Problem Taxonomy

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

Scheduling Algorithm Classification Matrix
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

Interview Strategy

Essential Metric Definitions with Mathematical Precision

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)

Core Scheduling Metrics and Their Formulas
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

Critical Distinction: Waiting Time vs Response Time

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.

scheduling_metrics.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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

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

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

FCFS Metric Calculations
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.

fcfs_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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

Optimality Proof Intuition

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 Decision Points

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

SRTF Metric Calculations
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.

Starvation Risk

srtf_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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_chart

Round Robin: Time-Slicing and Fairness

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

Queue Ordering is Everything

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

Round Robin (q=2) Metric Calculations
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.

round_robin_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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_chart

Priority 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

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.

MLFQ Rules
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 in Interviews

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

Problem-Solving Strategy Summary

Practice Problems with Solutions

Test your understanding with these carefully selected problems that cover core concepts and common edge cases.

Problem 1: SRTF with Ties

Solution:

t=0: P1 starts (remaining=4)
t=1: P2 arrives (rem=2). P1(rem=3) vs P2(rem=2). P2 wins, preempt P1.
t=2: P3 arrives (rem=2). P2(rem=1) vs P3(rem=2). P2 continues.
t=3: P2 completes. P4 arrives. Ready: [P1(3), P3(2), P4(1)]. P4 wins (shortest).
t=4: P4 completes. Ready: [P1(3), P3(2)]. P3 wins.
t=6: P3 completes. P1 runs.
t=9: P1 completes.

Gantt: |P1|P2|P4|P3|P1| 0 1 3 4 6 9

Metrics:

P1: CT=9, TAT=9, WT=5
P2: CT=3, TAT=2, WT=0
P3: CT=6, TAT=4, WT=2
P4: CT=4, TAT=1, WT=0

Average WT = (5+0+2+0)/4 = 1.75

Problem 2: Round Robin Context Switches

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.)

Solution:

Gantt: |P1|P2|P3|P1|P2|P1| 0 3 6 8 11 14 18

Execution sequence: P1(3) → P2(3) → P3(2) → P1(3) → P2(3) → P1(4)

Context switches (transitions between different processes or from idle):

P1 → P2 at t=3
P2 → P3 at t=6
P3 → P1 at t=8
P1 → P2 at t=11
P2 → P1 at t=14

Answer: 5 context switches

Problem 3: Comparing FCFS and SJF

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?

Solution:

FCFS: Gantt: |P1|P2|P3| 0 8 9 12

P1: TAT = 8-0 = 8
P2: TAT = 9-1 = 8
P3: TAT = 12-2 = 10
Avg TAT = (8+8+10)/3 = 8.67

SJF (non-preemptive): At t=0, only P1 available → P1 runs to completion (non-preemptive!) At t=8, ready: [P2, P3]. P2 is shorter.

Gantt: |P1|P2|P3| 0 8 9 12

Same as FCFS because P1 must complete before decisions are made!

Answer: For this input, both give Avg TAT = 8.67

Key insight: SJF only helps when decisions between multiple ready processes are possible at decision points.

Summary: Scheduling Problem Mastery

Key Takeaways

•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.

Page Complete