SJF (Shortest Job First) in Operating Systems - Step-by-Step Execution

Concept Flow - SJF (Shortest Job First)

Jobs arrive

↓

Check ready queue

↓

Select job with shortest burst time

↓

Execute selected job

↓

Job completes

↓

Remove job from queue

↓

Repeat until no jobs left

SJF schedules jobs by always picking the one with the shortest execution time next, repeating until all jobs finish.

Execution Sample

Operating Systems

Jobs = [("P1", 6), ("P2", 2), ("P3", 8), ("P4", 3)]
Order = []
while Jobs:
  # Pick job with shortest burst
  job = min(Jobs, key=lambda x: x[1])
  # Execute job
  # Remove job
  Jobs.remove(job)
  # Add to Order
  Order.append(job[0])

This simulates picking and running the shortest job from a list until all are done.

Analysis Table

Step	Ready Queue	Selected Job	Action	Order of Execution
1	P1(6), P2(2), P3(8), P4(3)	P2(2)	Execute P2	P2
2	P1(6), P3(8), P4(3)	P4(3)	Execute P4	P2, P4
3	P1(6), P3(8)	P1(6)	Execute P1	P2, P4, P1
4	P3(8)	P3(8)	Execute P3	P2, P4, P1, P3
5	Empty	None	All jobs done	P2, P4, P1, P3

💡 All jobs executed; ready queue is empty.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
Ready Queue	P1(6), P2(2), P3(8), P4(3)	P1(6), P3(8), P4(3)	P1(6), P3(8)	P3(8)	Empty	Empty
Order	[]	[P2]	[P2, P4]	[P2, P4, P1]	[P2, P4, P1, P3]	[P2, P4, P1, P3]

Key Insights - 3 Insights

Why does the scheduler pick P2 before P4 even though both are short?

Because P2 has the shortest burst time (2) compared to P4 (3), so it is selected first as shown in step 1 of the execution_table.

What happens if two jobs have the same shortest burst time?

The scheduler picks the one that arrived first or is listed first in the queue. This is not shown here but is a common rule to break ties.

Why is the ready queue smaller after each step?

Because after executing a job, it is removed from the queue, reducing the number of jobs left to schedule, as seen in the variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2. Which job is selected and why?

A P4 because it has the shortest burst time left

B P1 because it arrived first

C P3 because it has the longest burst time

D P2 because it is still in the queue

💡 Hint

Check the 'Selected Job' column at Step 2 in the execution_table.

At which step does the ready queue become empty?

A Step 4

B Step 5

C Step 3

D Never

💡 Hint

Look at the 'Ready Queue' column in the execution_table to see when it shows 'Empty'.

If P4 had a burst time of 1 instead of 3, which job would be selected at Step 2?

A P1

B P3

C P4

D P2

💡 Hint

Refer to the selection rule: pick the job with the shortest burst time from the ready queue.

Concept Snapshot

SJF (Shortest Job First) schedules jobs by always running the job with the smallest burst time next.
It reduces average waiting time but can cause longer jobs to wait.
Jobs are selected from the ready queue until all are done.
Tie-breakers usually pick the earliest arrived job.
Non-preemptive SJF runs each job fully once started.

Full Transcript

SJF (Shortest Job First) is a scheduling method where the system picks the job with the shortest execution time from the ready queue to run next. This process repeats until all jobs finish. In the example, jobs P1, P2, P3, and P4 have burst times 6, 2, 8, and 3 respectively. The scheduler picks P2 first because it has the shortest burst time, then P4, then P1, and finally P3. After each job completes, it is removed from the queue, shrinking the ready queue until empty. This method helps reduce average waiting time but may delay longer jobs. If two jobs have the same burst time, the one that arrived first is chosen. The execution table and variable tracker show these steps clearly, helping beginners visualize how SJF works step-by-step.

Practice

1. What is the main goal of the SJF (Shortest Job First) scheduling algorithm?

easy

A. To schedule the shortest job next to minimize average waiting time

B. To schedule jobs in the order they arrive

C. To schedule the longest job first to maximize CPU usage

D. To schedule jobs randomly without any priority

Solution

1. Step 1: Understand SJF scheduling principle

   SJF always picks the job with the shortest execution time next to run.

2. Step 2: Identify the goal of SJF

   This approach reduces the average waiting time for all jobs in the queue.

3. Final Answer:

   To schedule the shortest job next to minimize average waiting time -> Option A

4. Quick Check:

   SJF = shortest job first, reduces waiting time [OK]

Hint: SJF picks shortest job first to reduce waiting time [OK]

Common Mistakes:

• Confusing SJF with FCFS (First Come First Serve)
• Thinking SJF schedules longest jobs first
• Assuming SJF schedules jobs randomly

2. Which of the following is the correct way to describe the SJF scheduling algorithm?

easy

A. Schedules jobs based on their arrival time only

B. Schedules the job with the shortest burst time next

C. Schedules jobs in a round-robin fashion

D. Schedules jobs randomly without considering job length

Solution

1. Step 1: Recall SJF scheduling criteria

   SJF selects the job with the shortest burst (execution) time next.

2. Step 2: Match the description to options

   Only Schedules the job with the shortest burst time next correctly states scheduling by shortest burst time.

3. Final Answer:

   Schedules the job with the shortest burst time next -> Option B

4. Quick Check:

   SJF = shortest burst time scheduling [OK]

Hint: SJF = shortest burst time next, not arrival time [OK]

Common Mistakes:

• Confusing SJF with FCFS which uses arrival time
• Mixing SJF with round-robin scheduling
• Ignoring job length in scheduling decision

3. Given the following jobs with their burst times:
Job A: 6 units, Job B: 2 units, Job C: 8 units, Job D: 3 units
What is the average waiting time using non-preemptive SJF scheduling?

medium

A. 5.0 units

B. 3.5 units

C. 4.5 units

D. 6.0 units

Solution

1. Step 1: Order jobs by burst time for SJF

   Order: Job B (2), Job D (3), Job A (6), Job C (8).

2. Step 2: Calculate waiting times for each job

   Waiting times: B=0, D=2, A=5 (2+3), C=11 (2+3+6).

3. Step 3: Compute average waiting time

   Average = (0 + 2 + 5 + 11) / 4 = 18 / 4 = 4.5 units.

4. Final Answer:

   4.5 units -> Option C

5. Quick Check:

   Average waiting time = 4.5 units [OK]

Hint: Sort jobs by burst time, sum waiting times, divide by count [OK]

Common Mistakes:

• Not sorting jobs by burst time
• Calculating waiting time incorrectly by mixing completion times
• Forgetting to start first job waiting time at zero

4. Consider this non-preemptive SJF schedule with jobs and burst times:
Job X: 4 units, Job Y: 3 units, Job Z: 5 units
If the scheduler mistakenly picks Job Z first, what is the main error?

medium

A. Scheduling jobs randomly

B. Scheduling jobs based on arrival time

C. Using preemptive instead of non-preemptive scheduling

D. Ignoring the shortest job first rule

Solution

1. Step 1: Identify correct SJF behavior

   SJF should pick the job with the shortest burst time first, which is Job Y (3 units).

2. Step 2: Analyze the mistake

   Picking Job Z (5 units) first ignores the shortest job first rule.

3. Final Answer:

   Ignoring the shortest job first rule -> Option D

4. Quick Check:

   Picking longer job first breaks SJF rule [OK]

Hint: SJF must pick shortest job first, not longer ones [OK]

Common Mistakes:

• Confusing arrival time with burst time priority
• Mixing preemptive and non-preemptive concepts
• Assuming random scheduling is allowed in SJF

5. In a system using preemptive SJF (Shortest Remaining Time First), if a new job arrives with a burst time shorter than the remaining time of the current job, what happens?

hard

A. The new job preempts the current job immediately

B. The current job continues until completion

C. The new job waits until the current job finishes

D. Both jobs run simultaneously

Solution

1. Step 1: Understand preemptive SJF behavior

   Preemptive SJF (Shortest Remaining Time First) allows interruption if a shorter job arrives.

2. Step 2: Apply rule to scenario

   If new job's burst time is less than current job's remaining time, it preempts immediately.

3. Final Answer:

   The new job preempts the current job immediately -> Option A

4. Quick Check:

   Preemptive SJF switches to shortest remaining job [OK]

Hint: New shorter job preempts current in preemptive SJF [OK]

Common Mistakes:

• Assuming current job always runs to completion
• Confusing preemptive with non-preemptive SJF
• Thinking jobs run in parallel