Bird
Raised Fist0
Interview Prepoperating-systemsmediumGoogleAmazonSwiggy

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

Choose your preparation mode3 modes available
▶
Steps
setup

Initialize variables and start scheduling

Initialize remaining times, counters, and time to start scheduling from time 0.

💡 Setting up these variables is essential to track progress and remaining burst times for each process.
Line:n = len(processes) remaining_time = [bt for _, bt in processes] complete = 0 current_time = 0
💡 We now have the initial state with all processes' burst times ready to be decremented as they run.
📊
Shortest Job First (SJF) - Preemptive vs Non-Preemptive - Watch the Algorithm Execute, Step by Step
Watching each scheduling decision and time increment reveals how the algorithm dynamically chooses processes, which is hard to grasp from code alone.
Step 1/20
·Active fill★Answer cell
Transition init → ready0 - start scheduling
0
ready
burst: 8
1
new
burst: 4
2
new
burst: 9
3
new
burst: 5
Ready Queue
empty
Waiting Queue
empty
🖥CPUidlet=0
Transition ready → running0 - selected shortest job
0
running
burst: 8
1
new
burst: 4
2
new
burst: 9
3
new
burst: 5
Ready Queue
empty
Waiting Queue
empty
🖥CPU0t=0
Transition running → running0 - executed 1 time unit
0
running
burst: 7
1
ready
burst: 4
2
new
burst: 9
3
new
burst: 5
Ready Queue
1
Waiting Queue
empty
🖥CPU0t=1
idle
Transition running → running pid:1 - preempted by shorter job
0
ready
burst: 7
1
running
burst: 4
2
new
burst: 9
3
new
burst: 5
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=1
idle
Transition running → running pid:1 - executed 1 time unit
0
ready
burst: 7
1
running
burst: 3
2
ready
burst: 9
3
new
burst: 5
Ready Queue
02
Waiting Queue
empty
🖥CPU1t=2
idle
1
Transition running → running pid:1 - continue running shortest job
0
ready
burst: 7
1
running
burst: 3
2
ready
burst: 9
3
ready
burst: 5
Ready Queue
023
Waiting Queue
empty
🖥CPU1t=2
idle
1
Transition running → running pid:1 - executed 1 time unit
0
ready
burst: 7
1
running
burst: 2
2
ready
burst: 9
3
ready
burst: 5
Ready Queue
023
Waiting Queue
empty
🖥CPU1t=3
idle
1
Transition running → running pid:1 - continue running shortest job
0
ready
burst: 7
1
running
burst: 2
2
ready
burst: 9
3
ready
burst: 5
Ready Queue
023
Waiting Queue
empty
🖥CPU1t=3
idle
1
Transition running → running pid:1 - executed 1 time unit
0
ready
burst: 7
1
running
burst: 1
2
ready
burst: 9
3
ready
burst: 5
Ready Queue
023
Waiting Queue
empty
🖥CPU1t=4
idle
1
Transition running → terminated pid:1 - process completed
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
ready
burst: 5
Ready Queue
023
Waiting Queue
empty
🖥CPU1t=5
idle
1
Transition ready → running pid:3 - selected shortest job
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
running
burst: 5
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=5
idle
1
Transition running → running pid:3 - executed 1 time unit
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
running
burst: 4
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=6
idle
1
3
Transition running → running pid:3 - continue running shortest job
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
running
burst: 4
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=6
idle
1
3
Transition running → running pid:3 - executed 1 time unit
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
running
burst: 3
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=7
idle
1
3
Transition running → running pid:3 - continue running shortest job
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
running
burst: 3
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=7
idle
1
3
Transition running → running pid:3 - executed 1 time unit
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
running
burst: 2
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=8
idle
1
3
Transition running → terminated pid:3 - process completed
0
ready
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
terminated
burst: 0
Ready Queue
02
Waiting Queue
empty
🖥CPU3t=10
idle
1
3
Transition ready → running0 - selected shortest job
0
running
burst: 7
1
terminated
burst: 0
2
ready
burst: 9
3
terminated
burst: 0
Ready Queue
2
Waiting Queue
empty
🖥CPU0t=10
idle
1
3
Transition running → terminated0 - process completed
0
terminated
burst: 0
1
terminated
burst: 0
2
ready
burst: 9
3
terminated
burst: 0
Ready Queue
2
Waiting Queue
empty
🖥CPU0t=17
idle
1
3
idle
Transition running → terminated pid:2 - process completed
0
terminated
burst: 0
1
terminated
burst: 0
2
terminated
burst: 0
3
terminated
burst: 0
Ready Queue
empty
Waiting Queue
empty
🖥CPU2t=26
idle
1
3
idle
2

Key Takeaways

✓ SJF preemptive scheduling always picks the process with the shortest remaining burst time at every time unit.

This dynamic selection is difficult to visualize from code alone but is clear when watching each scheduling decision.

✓ Preemption occurs immediately when a shorter job arrives, interrupting the currently running process.

Seeing the CPU switch processes step-by-step reveals how preemption minimizes waiting time.

✓ Waiting time is calculated precisely at process completion using finish time, burst time, and arrival time.

Understanding waiting time calculation is easier when you see the exact moment a process finishes and how the formula applies.

Practice

(1/5)
1. In which scenario is the Dining Philosophers problem a suitable model to analyze system behavior?
easy
A. When processes communicate via message passing without shared resources
B. When multiple processes compete for multiple identical resources without any ordering
C. When a single process requires exclusive access to a single resource
D. When multiple processes compete for multiple shared resources arranged in a circular wait pattern

Solution

  1. Step 1: Identify the resource allocation pattern

    The Dining Philosophers problem models processes (philosophers) competing for shared resources (forks) arranged in a circular manner, leading to potential circular wait and deadlock.
  2. Step 2: Analyze each option

    When multiple processes compete for multiple shared resources arranged in a circular wait pattern correctly describes competition with a circular wait pattern, which is essential for the Dining Philosophers problem; When multiple processes compete for multiple identical resources without any ordering lacks the circular wait pattern; When a single process requires exclusive access to a single resource is a trivial single resource case; When processes communicate via message passing without shared resources involves no shared resources, so no deadlock from resource contention.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Only When multiple processes compete for multiple shared resources arranged in a circular wait pattern captures the circular wait condition essential to the Dining Philosophers problem.
Hint: Dining Philosophers = circular wait over shared resources [OK]
Common Mistakes:
  • Confusing any resource competition with circular wait
  • Assuming single resource contention models the problem
  • Ignoring the circular dependency aspect
2. In which scenario is the SSTF (Shortest Seek Time First) disk scheduling algorithm most appropriate compared to SCAN or C-SCAN?
easy
A. When minimizing average seek time is the highest priority and starvation is acceptable
B. When fairness and avoiding starvation are more important than minimizing seek time
C. When the disk requests are uniformly distributed and the workload is heavy
D. When the disk head movement must always proceed in one direction only

Solution

  1. Step 1: Understand SSTF's goal

    SSTF selects the closest request to the current head position to minimize seek time.
  2. Step 2: Consider starvation risk

    SSTF can cause starvation for requests far from the current head position because it always picks the nearest request.
  3. Step 3: Compare with SCAN and C-SCAN

    SCAN and C-SCAN move the head in a fixed direction to provide fairness and avoid starvation, sacrificing some seek time efficiency.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    When minimizing average seek time is the highest priority and starvation is acceptable correctly identifies SSTF's strength and its tradeoff with starvation risk.
Hint: SSTF = fastest seek but can starve distant requests
Common Mistakes:
  • Assuming SSTF always avoids starvation
  • Believing SCAN/C-SCAN minimize seek time better than SSTF
  • Confusing uniform distribution with SSTF suitability
3. When a CPU switches from running one thread to another within the same process, what sequence of events occurs internally?
easy
A. The OS terminates the current thread and creates a new thread for the next task
B. The OS saves the entire process state and reloads it for the new thread
C. The OS flushes the process's memory cache and reloads it for the new thread
D. The OS saves the thread's CPU registers and stack pointer, then loads the next thread's registers and stack pointer

Solution

  1. Step 1: Identify what is saved during thread context switch

    Only the CPU registers and stack pointer specific to the thread are saved and restored, since threads share the process memory space.
  2. Step 2: Understand process state remains unchanged

    The process's memory and resources remain intact; no need to save or reload the entire process state.
  3. Step 3: Evaluate options

    The OS saves the entire process state and reloads it for the new thread incorrectly saves the entire process state. The OS flushes the process's memory cache and reloads it for the new thread incorrectly flushes memory cache. The OS terminates the current thread and creates a new thread for the next task incorrectly terminates and recreates threads.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Thread context switch saves/restores thread-specific CPU state only [OK]
Hint: Thread switch saves CPU registers, not whole process state [OK]
Common Mistakes:
  • Confusing process context switch with thread context switch
  • Assuming memory cache must be flushed on thread switch
  • Believing threads are terminated and recreated on each switch
4. Which of the following statements about deadlock prevention in the Dining Philosophers problem is INCORRECT?
medium
A. Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation
B. Allowing a philosopher to pick up both forks only if both are available prevents deadlock
C. Imposing a strict ordering on resource acquisition always prevents deadlock
D. Breaking one of the four Coffman conditions is sufficient to prevent deadlock

Solution

  1. Step 1: Analyze each statement

    Imposing a strict ordering on resource acquisition always prevents deadlock is correct: ordering resources prevents circular wait; Allowing a philosopher to pick up both forks only if both are available prevents deadlock is correct: atomic acquisition avoids partial hold; Breaking one of the four Coffman conditions is sufficient to prevent deadlock is correct: breaking any Coffman condition prevents deadlock.
  2. Step 2: Evaluate Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation

    Asymmetric fork picking prevents deadlock but does not guarantee no starvation, as some philosophers may be repeatedly delayed.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Only Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation incorrectly claims starvation is guaranteed prevented.
Hint: Deadlock prevention ≠ starvation prevention [OK]
Common Mistakes:
  • Assuming deadlock prevention implies starvation freedom
  • Believing asymmetric picking solves all synchronization issues
  • Confusing Coffman conditions with starvation conditions
5. If a system using the buddy system frequently experiences internal fragmentation, which of the following strategies would best reduce it without sacrificing allocation speed?
hard
A. Increase the minimum block size in the buddy system to reduce splitting overhead
B. Use compaction to rearrange allocated blocks and reduce fragmentation
C. Implement a slab allocator on top of the buddy system for frequently requested object sizes
D. Switch to fixed partitioning to eliminate internal fragmentation

Solution

  1. Step 1: Identify internal fragmentation cause

    Buddy system rounds allocations to power-of-two sizes, causing internal fragmentation.
  2. Step 2: Evaluate strategies

    Slab allocator efficiently manages fixed-size objects, reducing internal fragmentation without slowing allocation.
  3. Step 3: Analyze other options

    Increasing minimum block size (A) increases internal fragmentation; compaction (C) addresses external fragmentation; fixed partitioning (D) is inflexible and can worsen fragmentation.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Slab allocators complement buddy system to reduce internal fragmentation [OK]
Hint: Slab allocator + buddy system = less internal fragmentation [OK]
Common Mistakes:
  • Thinking compaction reduces internal fragmentation
  • Assuming bigger minimum block size reduces fragmentation
  • Believing fixed partitioning eliminates fragmentation
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