Bird
Raised Fist0
Interview Prepoperating-systemsmediumGoogleAmazonSwiggy

Shortest Job First (SJF) - Preemptive vs Non-Preemptive

Choose your preparation mode3 modes available
🎯
Shortest Job First (SJF) - Preemptive vs Non-Preemptive
mediumOSGoogleAmazonSwiggy

Imagine a busy kitchen where the chef always picks the dish that takes the least time to prepare next, but sometimes a quicker order arrives while cooking another dish.

💡 Beginners often confuse preemptive and non-preemptive scheduling as just 'fast' or 'slow' without understanding how process interruption and waiting times differ fundamentally. Think of preemptive as a chef who can pause cooking a long dish to start a shorter one immediately, while non-preemptive means the chef finishes the current dish before starting another.
📋
Interview Question

Explain the Shortest Job First (SJF) CPU scheduling algorithm and compare its preemptive and non-preemptive variants. What are the advantages and disadvantages of each?

CPU scheduling and process burst timePreemptive vs non-preemptive schedulingStarvation and fairness in scheduling
💡
Scenario & Trace
ScenarioA CPU scheduler has three processes arriving at different times with varying burst times.
In non-preemptive SJF, once a process starts executing, it runs to completion even if a shorter job arrives later. In preemptive SJF (also called Shortest Remaining Time First), if a new process arrives with a shorter remaining burst time than the currently running process, the CPU preempts the current process and switches to the new one.
ScenarioA print server handles print jobs of different lengths arriving at random times.
Using non-preemptive SJF, the server prints jobs in order of shortest job first but does not interrupt a printing job once started. Using preemptive SJF, if a shorter print job arrives while printing a longer one, the server pauses the current job and switches to the shorter one, improving average wait time but increasing complexity.
  • What happens if two processes have the same burst time?
  • What if a very short process arrives while a long process is running in non-preemptive SJF?
  • How does starvation occur in preemptive SJF when short jobs keep arriving?
⚠️
Common Mistakes
Confusing preemptive SJF with non-preemptive SJF as just faster scheduling

Interviewer doubts your understanding of process interruption and scheduling dynamics

✅ Clarify that preemptive SJF allows interruption based on remaining burst time, non-preemptive does not

Assuming SJF always prevents starvation

Interviewer suspects lack of awareness of fairness issues

✅ Explain that preemptive SJF can cause starvation if short jobs keep arriving, and mention mitigation techniques

Believing burst times are always known exactly

Interviewer questions practical applicability knowledge

✅ Mention that burst times are often estimated or predicted, which affects scheduling accuracy

Ignoring context switch overhead in preemptive SJF

Interviewer thinks candidate lacks understanding of system costs

✅ Acknowledge that frequent preemption increases context switches, which can degrade performance

🧠
Basic Definition - What It Is
💡 This level covers the fundamental idea and basic differences, enough to answer simple interview questions or screening calls.

Intuition

SJF schedules the process with the shortest burst time next; preemptive SJF can interrupt running processes, non-preemptive cannot.

Explanation

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest execution time (burst time) to run next. In the non-preemptive variant, once a process starts executing, it runs until completion without interruption. In the preemptive variant, also known as Shortest Remaining Time First (SRTF), the scheduler can interrupt the currently running process if a new process arrives with a shorter remaining burst time. This approach aims to minimize average waiting time and turnaround time.

Memory Hook

💡 Think of a cashier who always serves the customer with the fewest items next; if the cashier can pause serving a customer to serve a quicker one, that's preemptive SJF.

Illustrative Code

def sjf_non_preemptive(processes):
    # Sort processes by arrival time
    processes.sort(key=lambda x: x[0])
    n = len(processes)
    completed = 0
    current_time = 0
    waiting_time = [0]*n
    while completed < n:
        # Find process with shortest burst time among arrived and not completed
        idx = -1
        min_bt = float('inf')
        for i in range(n):
            if processes[i][0] <= current_time and waiting_time[i] == 0 and processes[i][1] < min_bt:
                min_bt = processes[i][1]
                idx = i
        if idx == -1:
            current_time += 1
            continue
        # Run process to completion
        current_time += processes[idx][1]
        waiting_time[idx] = current_time - processes[idx][0] - processes[idx][1]
        completed += 1
    return waiting_time

Interview Questions

❓
    ⏱
    Depth Level
    Interview Time
    Depth

    For each process, we scan all processes to find the shortest job ready to run, leading to O(n^2) time. Space is O(n) for tracking waiting times and completion.

    Interview Target: Minimum floor - never go below this

    Knowing only this will help you pass initial rounds but not detailed technical interviews.

    🧠
    Mechanism Depth - How It Works
    💡 This level explains internal workings, scheduling decisions, and trade-offs expected in product company interviews.

    Intuition

    SJF schedules based on shortest burst time, with preemptive SJF dynamically adjusting to new arrivals by comparing remaining times.

    Explanation

    In non-preemptive SJF, the scheduler selects the process with the shortest burst time from the ready queue and runs it to completion. New arrivals wait until the CPU is free. This simplicity reduces context switches but can cause longer wait times for short jobs arriving late. In preemptive SJF (SRTF), the scheduler continuously monitors the ready queue. If a new process arrives with a burst time less than the remaining time of the currently running process, the CPU is preempted and assigned to the new process. This reduces average waiting time but increases context switching overhead and can cause starvation for longer processes if short jobs keep arriving. Both variants require knowledge of burst times, which may be estimated or known in advance.

    Memory Hook

    💡 Imagine a chef who can pause cooking a long dish to quickly prepare a short one that just arrived, then resume the long dish later.

    Illustrative Code

    def sjf_preemptive(processes):
        n = len(processes)
        remaining_time = [bt for _, bt in processes]
        complete = 0
        current_time = 0
        min_remaining = float('inf')
        shortest = -1
        check = False
        waiting_time = [0]*n
        while complete != n:
            for i in range(n):
                if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
                    min_remaining = remaining_time[i]
                    shortest = i
                    check = True
            if not check:
                current_time += 1
                continue
            remaining_time[shortest] -= 1
            min_remaining = remaining_time[shortest]
            if min_remaining == 0:
                min_remaining = float('inf')
            if remaining_time[shortest] == 0:
                complete += 1
                finish_time = current_time + 1
                waiting_time[shortest] = finish_time - processes[shortest][1] - processes[shortest][0]
                if waiting_time[shortest] < 0:
                    waiting_time[shortest] = 0
            current_time += 1
            check = False
        return waiting_time

    Interview Questions

    ❓
      ⏱
      Depth Level
      Interview Time
      Depth

      At each time unit, the scheduler scans all processes to find the shortest remaining time process, leading to O(n^2) time. Space is O(n) for tracking remaining and waiting times.

      Interview Target: Target level for FAANG on-sites

      Mastering this level distinguishes you from most candidates and prepares you for follow-up questions.

      📊
      Explanation Depth Levels
      💡 Choose your explanation depth based on interview stage and company expectations.
      LevelInterview TimeSuitable ForRisk
      Basic Definition30sScreening call or initial roundsToo shallow for on-site or deep technical interviews
      Mechanism Depth2-3 minutesOn-site interviews at FAANG and top tech companiesRequires good understanding; missing details may lose points
      💼
      Interview Strategy
      💡 Use this guide to structure your explanation clearly and confidently before every mock or real interview.

      How to Present

      Start with a clear definition of SJF and its goal to minimize average waiting timeExplain the difference between preemptive and non-preemptive variants with a simple analogyDescribe the internal mechanism of how scheduling decisions are madeDiscuss edge cases like starvation and tie-breakingConclude with pros and cons of each variant

      Time Allocation

      Definition: 30s → Example: 1min → Mechanism: 2min → Edge cases: 30s. Total ~4min

      What the Interviewer Tests

      Interviewer checks if you understand process interruption, scheduling fairness, and can reason about real-world implications.

      Common Follow-ups

      • How does SJF compare to Round Robin scheduling? → SJF optimizes average wait time, RR ensures fairness with time slices
      • How can starvation be mitigated in preemptive SJF? → Aging or priority adjustments
      💡 These follow-ups test your ability to connect concepts and propose practical solutions.
      🔍
      Pattern Recognition

      When to Use

      Interviewers ask about SJF when discussing CPU scheduling algorithms, process management, or performance optimization.

      Signature Phrases

      'Explain the Shortest Job First scheduling algorithm''Compare preemptive and non-preemptive scheduling''What happens when a shorter job arrives during execution?'

      NOT This Pattern When

      Similar Problems

      Practice

      (1/5)
      1. You are designing a web server that must handle thousands of simultaneous client requests efficiently. Which approach is most suitable to maximize resource sharing and minimize overhead?
      easy
      A. Use multiple threads within a single process to handle client requests concurrently
      B. Use multiple processes with shared memory segments for communication
      C. Use a single-threaded process with blocking I/O for all requests
      D. Use multiple processes, each handling a single client request independently

      Solution

      1. Step 1: Understand resource sharing in threads

        Threads within the same process share memory and resources, allowing efficient communication and lower overhead compared to processes.
      2. Step 2: Compare overhead of context switching

        Thread context switching is lighter than process context switching, making threads better for high concurrency.
      3. Step 3: Evaluate options

        Use multiple processes, each handling a single client request independently uses processes, which have higher overhead and less efficient resource sharing. Use a single-threaded process with blocking I/O for all requests is single-threaded and blocks, limiting concurrency. Use multiple processes with shared memory segments for communication adds complexity with shared memory and still has process overhead.
      4. Final Answer:

        Option A -> Option A
      5. Quick Check:

        Threads maximize resource sharing and minimize overhead for concurrent tasks [OK]
      Hint: Threads share memory; processes isolate resources [OK]
      Common Mistakes:
      • Assuming processes are always better for concurrency
      • Ignoring context switching overhead differences
      • Believing shared memory between processes is as simple as threads
      2. In which scenario is a Translation Lookaside Buffer (TLB) most beneficial for system performance?
      easy
      A. When the system uses a single-level page table with very few page faults
      B. When virtual memory accesses exhibit high temporal locality of page references
      C. When the system has a very small physical memory and no paging
      D. When all memory accesses are sequential and predictable

      Solution

      1. Step 1: Understand TLB purpose

        The TLB caches recent virtual-to-physical address translations to speed up address translation.
      2. Step 2: Analyze each option

        A: High temporal locality means repeated accesses to the same pages, so TLB hits are frequent, improving performance.
        B: Single-level page tables are fast, but TLB benefits more when page tables are large.
        C: Small physical memory with no paging reduces need for TLB since address translation is trivial.
        D: Sequential accesses may not reuse the same pages quickly, reducing TLB hit rate.
      3. Final Answer:

        Option B -> Option B
      4. Quick Check:

        TLB effectiveness depends on locality of reference, which is captured by when virtual memory accesses exhibit high temporal locality of page references.
      Hint: TLB shines when recent translations are reused quickly [OK]
      Common Mistakes:
      • Assuming TLB is always beneficial regardless of access pattern
      • Confusing physical memory size with TLB usefulness
      3. Which of the following statements about the FIFO page replacement algorithm is INCORRECT?
      medium
      A. FIFO always evicts the least recently used page
      B. FIFO can suffer from Belady's anomaly where increasing frames increases page faults
      C. FIFO is simple to implement with a queue data structure
      D. FIFO does not consider how frequently or recently a page was accessed

      Solution

      1. Step 1: Understand FIFO Eviction Policy

        FIFO evicts the oldest loaded page, not the least recently used.
      2. Step 2: Evaluate Each Option

        FIFO can suffer from Belady's anomaly where increasing frames increases page faults is correct; Belady's anomaly can occur with FIFO.
        FIFO always evicts the least recently used page is incorrect; FIFO does not track recency of use.
        FIFO is simple to implement with a queue data structure is correct; FIFO uses a queue for eviction order.
        FIFO does not consider how frequently or recently a page was accessed is correct; FIFO ignores frequency and recency.
      3. Final Answer:

        Option A -> Option A
      4. Quick Check:

        FIFO evicts by arrival order, not usage recency.
      Hint: FIFO evicts oldest loaded page, not least recently used [OK]
      Common Mistakes:
      • Confusing FIFO with LRU eviction criteria
      • Assuming FIFO tracks page usage
      • Believing FIFO cannot have anomalies
      4. Which of the following statements about the five-state process model is INCORRECT?
      medium
      A. The New state represents a process that is being created but not yet ready to run
      B. The Waiting state is used when a process is blocked for I/O completion
      C. A process in the Terminated state can be moved back to Ready state if needed
      D. The Running state means the process is currently executing on the CPU

      Solution

      1. Step 1: Review each statement

        A, B, and D correctly describe standard process states.
        C incorrectly states that a Terminated process can return to Ready, which violates the model.
      2. Step 2: Understand Terminated state

        Terminated means process execution is complete; it cannot be restarted or moved back.
      3. Final Answer:

        Option C -> Option C
      4. Quick Check:

        Terminated processes cannot be revived in the five-state model [OK]
      Hint: Terminated means final; no return to Ready [OK]
      Common Mistakes:
      • Thinking Terminated processes can be restarted
      • Confusing Waiting with Ready state
      • Misunderstanding New state as Ready
      5. If the time quantum is set equal to the longest CPU burst among all processes in Round Robin scheduling, what is the expected impact on turnaround time and fairness?
      hard
      A. Both turnaround time and fairness improve because processes get longer uninterrupted CPU bursts
      B. Turnaround time approaches that of First-Come-First-Serve scheduling, but fairness among processes decreases
      C. Fairness remains the same but turnaround time increases due to longer waiting times
      D. Turnaround time decreases significantly and fairness improves due to fewer context switches

      Solution

      1. Step 1: Understand quantum equal to longest burst

        Setting quantum to longest burst means processes run mostly to completion without preemption.
      2. Step 2: Compare to FCFS

        This behavior mimics FCFS, where processes run in arrival order without interruption.
      3. Step 3: Analyze fairness and turnaround

        Fairness decreases because shorter processes wait longer, losing RR's time-sharing benefit. Turnaround time approaches FCFS values.
      4. Step 4: Evaluate incorrect options

        Turnaround time decreases significantly and fairness improves due to fewer context switches is wrong because fewer context switches do not improve fairness. Fairness remains the same but turnaround time increases due to longer waiting times is wrong as fairness changes. Both turnaround time and fairness improve because processes get longer uninterrupted CPU bursts is wrong because fairness does not improve.
      5. Final Answer:

        Option B -> Option B
      6. Quick Check:

        Quantum = longest burst -> RR ≈ FCFS -> fairness ↓, turnaround ~ FCFS.
      Hint: Quantum = longest burst -> RR behaves like FCFS
      Common Mistakes:
      • Assuming fairness always improves with larger quantum
      • Believing fewer context switches always reduce turnaround
      • Ignoring that RR degenerates to FCFS with large quantum
      Recommended

      Ready to prove it?

      Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

      10 questions~5 mineasy hard