SJF(SHORTEST JOB FIRST) premptive and non-premptive question

Here are 30 questions on SJF(SHORTEST JOB FIRST) process scheduling algorithms (premptive AND non-premptive). Each question is presented in a table format, followed by the solution with Gantt charts, average turnaround time (TAT), and average waiting time (WT).

Jump To Question

What Is Shortest Job First (SJF) Scheduling Algorithm in Operating System ?

Shortest Job First (SJF) is a process scheduling algorithm in which the process with the shortest execution time is selected for execution next. This scheduling technique is also known as Shortest Job Next (SJN) and can be either preemptive or non-preemptive.

Method to Solve SJF Scheduling Algorithm

  • Step 1: Identify all processes in the queue along with their burst times.
  • Step 2: Sort the processes based on their burst times (shortest to longest).
  • Step 3: Select the process with the shortest burst time and execute it.
  • Step 4: Once completed, remove it from the queue and update the waiting and turnaround times for all processes.
  • Step 5: Repeat steps 2 to 4 until all processes are executed.

Advantages and Disadvantages of SJF Scheduling Algorithm

Advantages Disadvantages
Minimizes average waiting time. Not practical for real-time scheduling as burst times are often unknown.
Simple and easy to understand. Can cause starvation for longer processes.
Effective in a batch processing environment. Requires knowledge of all process burst times.
Optimal in terms of reducing average waiting time. Challenging to implement in interactive systems.
Works well with a small number of processes. Not suitable for time-sharing environments.
Lower CPU idle time for batch jobs. High overhead if Burst Times vary widely.

Why SJF is Better than Other Scheduling Algorithms

SJF is more efficient in reducing the average waiting time compared to other scheduling algorithms, especially when burst times are predictable. It prioritizes shorter tasks, which helps optimize the utilization of CPU resources. However, it is only optimal when burst times can be determined in advance, which is often possible in batch processing systems but not in real-time or interactive environments.

Question 1: find the average Turn Around Time and Waiting Time of following processes using Non-Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
P5 4 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 1 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 8 8 8 - 0 = 8 8 - 8 = 0
P5 2 10 10 - 4 = 6 6 - 2 = 4
P2 4 14 14 - 1 = 13 13 - 4 = 9
P4 5 19 19 - 3 = 16 16 - 5 = 11
P3 9 28 28 - 2 = 26 26 - 9 = 17

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (8 + 6 + 13 + 16 + 26) / 5 = 13.8
Average WT = (0 + 4 + 9 + 11 + 17) / 5 = 8.2

Question 2: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
P5 7 3
P6 8 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 2 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 7 21 21 - 0 = 21 21 - 7 = 14
P2 4 7 7 - 2 = 5 5 - 4 = 1
P3 1 5 5 - 4 = 1 1 - 1 = 0
P4 4 16 16 - 5 = 11 11 - 4 = 7
P5 3 10 10 - 7 = 3 3 - 3 = 0
P6 2 12 12 - 8 = 4 4 - 2 = 2

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (21 + 5 + 1 + 11 + 3 + 14) / 6 = 9.16
Average WT = (14 + 1 + 0 + 7 + 0 + 2) / 6 = 4

Question 3: find the average Turn Around Time and Waiting Time of following processes using Non-Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 5
P2 1 3
P3 2 8
P4 3 6
P5 4 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 3 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 5 5 5 - 0 = 5 5 - 5 = 0
P5 2 7 7 - 4 = 3 3 - 2 = 1
P2 3 10 10 - 1 = 9 9 - 3 = 6
P4 6 16 16 - 3 = 13 13 - 6 = 7
P3 8 24 24 - 2 = 22 22 - 8 = 14

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (5 + 3 + 9 + 13 + 22) / 5 = 10.4
Average WT = (0 + 1 + 6 + 7 + 14) / 5 = 5.6

Question 4: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 6
P2 1 4
P3 2 9
P4 3 5
P5 4 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 5 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 6 12 12 - 0 = 12 12 - 6 = 6
P2 4 6 6 - 1 = 5 5 - 4 = 1
P3 9 26 26 - 2 = 24 24 - 9 = 15
P4 5 17 17 - 3 = 14 14 - 5 = 9
P5 2 7 7 - 4 = 3 3 - 2 = 1

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (12 + 5 + 24 + 14 + 3) / 5 = 11.6
Average WT = (6 + 1 + 15 + 9 + 1) / 5 = 6.4

Question 5: find the average Turn Around Time and Waiting Time of following processes using Non-Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 3
P2 1 6
P3 3 8
P4 5 5
P5 6 4
P6 7 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 5 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 3 3 3 - 0 = 3 3 - 3 = 0
P2 6 9 9 - 1 = 8 8 - 6 = 2
P3 8 28 28 - 3 = 25 25 - 8 = 17
P4 5 20 20 - 5 = 15 15 - 5 = 10
P5 4 15 15 - 6 = 9 9 - 4 = 5
P6 2 11 11 - 7 = 4 4 - 2 = 2

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (3 + 8 + 25 + 15 + 9 + 4) / 6 = 10.6
Average WT = (0 + 2 + 17 + 10 + 5 + 2) / 6 = 6

Question 6: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
P5 5 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 6 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 8 19 19 - 0 = 19 19 - 8 = 11
P2 4 5 5 - 1 = 4 4 - 4 = 0
P3 9 28 28 - 2 = 26 26 - 9 = 17
P4 5 12 12 - 3 = 9 9 - 5 = 4
P5 2 7 7 - 5 = 2 2 - 2 = 0

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (19+4+26+9+2) / 5 = 12
Average WT = (11+0+17+4+0) / 5 = 6.4

Question 7: find the average Turn Around Time and Waiting Time of following processes using Non-Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 2
P2 1 3
P3 2 4
P4 3 6
P5 4 1
P6 5 5

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 7 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 2 2 2 - 0 = 2 2 - 2 = 0
P2 3 5 5 - 1 = 4 4 - 3 = 1
P3 4 10 10 - 2 = 8 8 - 4 = 4
P4 6 21 21 - 3 = 18 18 - 6 = 12
P5 1 6 6 - 4 = 2 2 - 1 = 1
P6 5 15 15 - 5 = 10 10 - 5 = 5

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (2+4+8+18+2+10) / 6 = 7.33
Average WT = (0 + 1 + 4 +12 + 1+5) / 6 = 3.83

Question 8: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 5
P2 1 2
P3 3 6
P4 4 3
P5 5 4

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 8 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 5 7 7 - 0 = 7 7 - 5 = 2
P2 2 3 3 - 1 = 2 2 - 2 = 0
P3 6 20 20 - 3 = 17 17 - 6 = 11
P4 3 10 10 - 4 = 6 6 - 3 = 3
P5 4 14 14 - 5 = 9 9 - 4 = 5

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (7 + 2 + 17 +6 + 9) / 5 = 8.2
Average WT = (2 + 0 + 11 + 3 + 5) / 5 = 4.2

Question 9: find the average Turn Around Time and Waiting Time of following processes using Non-Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 8
P2 1 3
P3 2 7
P4 3 4
P5 4 2

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 9 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 8 8 8 - 0 = 8 8 - 8 = 0
P2 3 13 13 - 1 = 12 12 - 3 = 9
P3 7 24 24 - 2 = 22 22 - 7 = 15
P4 4 17 17 - 3 = 14 14 - 4 = 10
P5 2 10 10 - 4 = 6 6 - 2 = 4

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (8 + 6 + 12 + 14 + 22) / 5 = 12.4
Average WT = (0 + 4 + 9 + 10 + 15) / 5 = 7.6

Question 10: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF(SHORTEST JOB FIRST) process scheduling algorithm?

Process Arrival Time Burst Time
P1 0 5
P2 1 7
P3 2 4
P4 3 1
P5 4 3

Solution :

Formulas:

  • Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
  • Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)

Gantt Chart

SJF SCHEDULING | Question 10 Solution | Gantt Chart
Process Burst Time Completion Time Turn Around Time (TAT) Waiting Time (WT)
P1 5 6 6 - 0 = 6 6 - 5 = 1
P2 7 20 20 - 1 = 19 19 - 7 = 12
P3 4 13 13 - 2 = 11 11 - 4 = 7
P4 1 4 4 - 3 = 1 1 - 1 = 0
P5 3 9 9 - 4 = 5 5 - 3 = 2

Formula for average TAT and WT:

  • Average Turn Around Time (Average TAT) = Σ(TAT) / Number of Processes
  • Average Waiting Time (Average WT) = Σ(WT) / Number of Processes

Average TAT = (6 + 19 + 11 + 1 + 5) / 5 = 8.4
Average WT = (1 + 12 + 7 + 0 + 2) / 5 = 4.4