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

🎯

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.

Level	Interview Time	Suitable For	Risk
Basic Definition	30s	Screening call or initial rounds	Too shallow for on-site or deep technical interviews
Mechanism Depth	2-3 minutes	On-site interviews at FAANG and top tech companies	Requires 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. 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 Round Robin scheduling with a fixed time quantum most appropriate compared to First-Come-First-Serve or Priority scheduling?

easy

A. When processes have highly variable CPU burst times and fairness among all processes is required

B. When all processes have identical priorities and long CPU bursts

C. When minimizing average turnaround time is the only goal

D. When processes have strict deadlines and real-time constraints

Solution

1. Step 1: Understand Round Robin's fairness goal

   Round Robin scheduling is designed to allocate CPU time slices fairly among all processes, especially when burst times vary widely.

2. Step 2: Analyze other options

   When all processes have identical priorities and long CPU bursts is less suitable because identical priorities and long bursts favor FCFS or SJF for efficiency, not fairness. When minimizing average turnaround time is the only goal ignores fairness and focuses only on turnaround time, which RR does not optimize. When processes have strict deadlines and real-time constraints requires real-time guarantees, which RR cannot provide due to its time slicing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   RR is best when fairness and responsiveness matter, especially with variable burst times.

Hint: RR = fairness with variable bursts

Common Mistakes:

• Assuming RR always minimizes turnaround time
• Believing RR suits real-time deadlines
• Confusing RR with priority-based scheduling

3. Trace the sequence of events when a user program invokes a system call to read a file. Which step happens immediately after the CPU switches to kernel mode?

easy

A. The kernel verifies the system call number and arguments

B. The hardware raises an interrupt to the device

C. The user program resumes execution in user mode

D. The kernel copies data directly to the user buffer without validation

Solution

1. Step 1: User program issues system call

   The user program executes a special instruction causing a trap to kernel mode.

2. Step 2: CPU switches to kernel mode

   Control transfers to the OS kernel with elevated privileges.

3. Step 3: Kernel validates system call

   The kernel inspects the system call number and arguments to ensure they are valid and safe.

4. Step 4: Why other options are incorrect

   The kernel copies data directly to the user buffer without validation is unsafe; kernel must validate before copying data. The user program resumes execution in user mode happens after system call completion, not immediately after mode switch. The hardware raises an interrupt to the device is unrelated here; hardware interrupts occur asynchronously, not immediately after mode switch.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   System call trap -> kernel mode -> validate call -> execute service [OK]

Hint: Kernel validates system call immediately after mode switch

Common Mistakes:

• Assuming kernel copies data before validation
• Confusing interrupt handling with system call flow
• Thinking user mode resumes immediately after trap

4. Which of the following statements about livelock is INCORRECT?

medium

A. Livelock differs from deadlock because processes remain active rather than blocked.

B. Livelock can be resolved by introducing random delays or backoff strategies.

C. Livelock occurs when processes continuously change state in response to each other without making progress.

D. In livelock, processes are blocked and waiting indefinitely for resources.

Solution

1. Step 1: Define livelock behavior

   Livelock involves processes actively changing states but failing to make progress, unlike deadlock where processes are blocked.

2. Step 2: Analyze each statement

   Livelock occurs when processes continuously change state in response to each other without making progress correctly describes livelock. Livelock can be resolved by introducing random delays or backoff strategies is true; random backoff can resolve livelock. In livelock, processes are blocked and waiting indefinitely for resources is incorrect because livelock processes are not blocked but active. Livelock differs from deadlock because processes remain active rather than blocked correctly contrasts livelock and deadlock.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Livelock means active but no progress, not blocked waiting.

Hint: Livelock = active spinning without progress, not blocked

Common Mistakes:

• Confusing livelock with deadlock
• Assuming livelock processes are blocked

5. Which of the following statements about user mode and kernel mode is INCORRECT?

medium

A. Mode switches are triggered by traps or interrupts to ensure controlled privilege escalation.

B. Kernel mode has unrestricted access to all hardware and memory.

C. User mode code cannot directly access kernel memory for protection reasons.

D. System calls execute entirely in user mode without switching to kernel mode.

Solution

1. Step 1: Review privilege separation

   User mode is restricted; kernel mode has full privileges.

2. Step 2: Validate each statement

   User mode code cannot directly access kernel memory for protection reasons. is true; user mode cannot access kernel memory. Kernel mode has unrestricted access to all hardware and memory. is true; kernel mode has full access. Mode switches are triggered by traps or interrupts to ensure controlled privilege escalation. is true; traps/interrupts cause mode switches.

3. Step 3: Identify incorrect statement

   System calls execute entirely in user mode without switching to kernel mode. is false; system calls require switching to kernel mode to execute privileged operations.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   System calls always involve mode switch to kernel [OK]

Hint: System calls require kernel mode execution

Common Mistakes:

• Believing system calls run entirely in user mode
• Confusing hardware interrupts with system calls
• Assuming user mode can access kernel memory