When it comes to CPU scheduling in operating systems, choosing the right algorithm helps improve system performance and responsiveness. One such important algorithm is Shortest Remaining Time First (SRTF), also known as Preemptive Shortest Job First (SJF).
In this blog post, we’ll explore this scheduling algorithm in detail through 11 solved questions, each with step-by-step solutions and Gantt charts. Before diving into the problems, let’s quickly understand what preemptive scheduling means and how SRTF works.
Jump To QuestionShortest Remaining Time First (SRTF) is a preemptive version of SJF preemptive scheduling algorithm used in operating systems. In this algorithm, the process with the shortest remaining burst time is selected for execution. If a new process arrives with a burst time shorter than the remaining time of the currently running process, the current process is preempted, and the new process starts execution.
- Step 1: Determine the burst time for all processes.
- Step 2: Select the process with the shortest remaining burst time from the ready queue.
- Step 3: If a new process arrives with a shorter burst time than the current process, preempt the current process.
- Step 4: Continue the above steps until all processes are completed.
- Step 5: Calculate the waiting time and turnaround time for each process.
- Step 6: Calculate the average waiting time and average turnaround time
| Advantages | Disadvantages |
|---|---|
| Minimizes average waiting time. | Can cause starvation for longer processes. |
| Improves overall system throughput. | Frequent context switching, which increases overhead. |
| Reduces turnaround time for shorter processes. | Not ideal for real-time systems. |
| Efficient for batch processing. | Difficult to predict the next shortest process in real time. |
| Ensures high processor utilization. | Requires precise information about burst time. |
| Dynamic adaptation to new processes. | Can lead to high response time variance. |
SRTF is considered better than non-preemptive scheduling algorithms like Shortest Job First (SJF) because it allows processes with shorter remaining burst times to be executed immediately, reducing the average waiting and turnaround time. Unlike algorithms such as First Come First Serve (FCFS), which may lead to high waiting times for shorter jobs, SRTF is more efficient in handling time-sensitive processes, especially when minimizing average wait time is the priority.
Question 1:Using Preemptive Shortest Job First (SJF) Scheduling, calculate the average Completion Time, Turn Around Time, and Waiting Time. Also, draw the Gantt chart for the processes listed with their Arrival and Burst Times.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 3 | 9 |
| P4 | 5 | 3 |
| P5 | 6 | 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
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 14 | 14 | 7 |
| P2 | 6 | 4 | 0 |
| P3 | 28 | 25 | 16 |
| P4 | 9 | 4 | 1 |
| P5 | 19 | 13 | 8 |
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 Turn Around Time (TAT) = (14+4+25+4+13)/5 = 12 units
Average Waiting Time (WT) = (7+0+16+1+8)/5 = 6.4 units
Question 2: Consider a set of processes with given Arrival and Burst Times. Apply Preemptive SJF Scheduling to compute the Gantt chart and determine the average Turnaround Time, Waiting Time, and Completion Time.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 2 |
| P3 | 3 | 4 |
| P4 | 4 | 3 |
| P5 | 5 | 6 |
Solution :
Formulas:
- Turn Around Time (TAT) = Completion Time (CT) - Arrival Time (AT)
- Waiting Time (WT) = Turn Around Time (TAT) - Burst Time (BT)
Gantt Chart
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 7 | 7 | 2 |
| P2 | 3 | 2 | 0 |
| P3 | 14 | 11 | 7 |
| P4 | 10 | 6 | 3 |
| P5 | 20 | 15 | 9 |
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 Turn Around Time (TAT) = (7+2+11+6+15)/5 = 8.2 units
Average Waiting Time (WT) = (2+0+7+3+9)/5 = 4.2 units
Question 3: For the processes provided in the table with their Arrival and Burst Times, use Preemptive Shortest Job First scheduling to find the Gantt chart and calculate average Waiting, Completion, and Turnaround Times.
| 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
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 19 | 19 - 0 = 19 | 19 - 8 = 11 |
| P2 | 5 | 5 - 1 = 4 | 4 - 4 = 0 |
| P3 | 28 | 28 - 2 = 26 | 26 - 9 = 17 |
| P4 | 12 | 12 - 3 = 9 | 9 - 5 = 4 |
| P5 | 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 4: Apply the Preemptive SJF (Shortest Remaining Time First) scheduling algorithm to the processes below. Find and display the Gantt chart, and calculate the average Completion Time, Waiting Time, and Turnaround Time.
| 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
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 12 | 12 - 0 = 12 | 12 - 6 = 6 |
| P2 | 6 | 6 - 1 = 5 | 5 - 4 = 1 |
| P3 | 26 | 26 - 2 = 24 | 24 - 9 = 15 |
| P4 | 17 | 17 - 3 = 14 | 14 - 5 = 9 |
| P5 | 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: Given a table of processes with Arrival and Burst Times, schedule them using Preemptive Shortest Job First. Then, draw the Gantt chart and compute the average Turn Around Time, Completion Time, and Waiting Time.
| 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
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 7 | 7 - 0 = 7 | 7 - 5 = 2 |
| P2 | 3 | 3 - 1 = 2 | 2 - 2 = 0 |
| P3 | 20 | 20 - 3 = 17 | 17 - 6 = 11 |
| P4 | 10 | 10 - 4 = 6 | 6 - 3 = 3 |
| P5 | 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 6: Analyze the processes using Preemptive Shortest Job First Scheduling. Based on their Arrival and Burst Times, draw a Gantt chart and calculate the average values for Completion Time, Turnaround Time, and Waiting Time.
| 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
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 6 | 6 - 0 = 6 | 6 - 5 = 1 |
| P2 | 20 | 20 - 1 = 19 | 19 - 7 = 12 |
| P3 | 13 | 13 - 2 = 11 | 11 - 4 = 7 |
| P4 | 4 | 4 - 3 = 1 | 1 - 1 = 0 |
| P5 | 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
Question 7: Use Preemptive Shortest Job First Scheduling for the following set of processes. Based on Arrival and Burst Time, create the Gantt chart and determine average Completion Time, Turnaround Time, and Waiting Time.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 9 |
| P2 | 1 | 3 |
| P3 | 2 | 6 |
| P4 | 3 | 2 |
| P5 | 5 | 4 |
Solution :
Formulas:
- Turnaround Time (TAT) = Completion Time - Arrival Time
- Waiting Time (WT) = Turnaround Time - Burst Time
Gantt Chart
| Process | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 24 | 24 - 0 = 24 | 24 - 9 = 15 |
| P2 | 4 | 4 - 1 = 3 | 3 - 3 = 0 |
| P3 | 16 | 16 - 2 = 14 | 14 - 6 = 8 |
| P4 | 6 | 6 - 3 = 3 | 3 - 2 = 1 |
| P5 | 10 | 10 - 5 = 5 | 5 - 4 = 1 |
Formulas for Average TAT and WT
- Average Turnaround Time = Sum of Turnaround Times / Number of Processes
- Average Waiting Time = Sum of Waiting Times / Number of Processes
Average TAT and WT
Average TAT = (24 + 3 + 14 + 3 + 5) / 5 = 49 / 5 = 9.8 units
Average WT = (16 + 0 + 8 + 1 + 1) / 5 = 26 / 5 = 5.2 units
Question 8: Given process information with Arrival and Burst Times, apply the Preemptive SJF (Shortest Remaining Time First) method to draw the Gantt chart and compute average Waiting, Completion, and Turnaround Times.
| 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
| Process | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 21 | 21 - 0 = 21 | 21 - 7 = 14 |
| P2 | 7 | 7 - 2 = 5 | 5 - 4 = 1 |
| P3 | 5 | 5 - 4 = 1 | 1 - 1 = 0 |
| P4 | 16 | 16 - 5 = 11 | 11 - 4 = 7 |
| P5 | 10 | 10 - 7 = 3 | 3 - 3 = 0 |
| P6 | 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 9: Schedule the processes using Preemptive SJF based on their Arrival and Burst Times. Then, illustrate the execution using a Gantt chart and calculate the average Turn Around Time, Waiting Time, and Completion Time.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 10 |
| P2 | 1 | 3 |
| P3 | 2 | 7 |
| P4 | 3 | 4 |
| P5 | 5 | 5 |
Solution :
Formulas:
- Turnaround Time (TAT) = Completion Time - Arrival Time
- Waiting Time (WT) = Turnaround Time - Burst Time
Gantt Chart
| Process | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 29 | 29 - 0 = 29 | 29 - 10 = 19 |
| P2 | 4 | 4 - 1 = 3 | 3 - 3 = 0 |
| P3 | 20 | 20 - 2 = 18 | 18 - 7 = 11 |
| P4 | 8 | 8 - 3 = 5 | 5 - 4 = 1 |
| P5 | 13 | 13 - 5 = 8 | 8 - 5 = 3 |
Formulas for Average TAT and WT
- Average Turnaround Time = Sum of Turnaround Times / Number of Processes
- Average Waiting Time = Sum of Waiting Times / Number of Processes
Average TAT and WT
Average TAT = (29 + 3 + 18 + 5 + 8) / 5 = 63 / 5 = 12.6 units
Average WT = (19 + 0 + 11 + 1 + 3) / 5 = 34 / 5 = 6.8 units