Jump To Question
What Is Shortest Remaining Time First (SRTF) Scheduling Algorithm ?
Shortest Remaining Time First (SRTF) or Shortest Job Next (SJN) is a 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.
Method to Solve SRTF Scheduling Algorithm
- 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 and Disadvantages of SRTF Scheduling Algorithm
| 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. |
Why SRTF is Better than Other Scheduling Algorithms
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 11: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 | 6 |
| P2 | 2 | 4 |
| P3 | 4 | 3 |
| P4 | 6 | 5 |
| P5 | 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 | Arrival Time | Burst Time | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 6 | 6 | 6 | 0 |
| P2 | 2 | 4 | 15 | 13 | 9 |
| P3 | 4 | 3 | 9 | 5 | 2 |
| P4 | 6 | 5 | 20 | 14 | 9 |
| P5 | 8 | 2 | 11 | 3 | 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 Turn Around Time (TAT) = (6+13+5+14+3)/5 = 8.2 units
Average Waiting Time (WT) = (0+9+2+9+1)/5 = 4.2 units
Question 12: 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 | 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 | Arrival Time | Burst Time | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 14 | 14 | 7 |
| P2 | 2 | 4 | 6 | 4 | 0 |
| P3 | 3 | 9 | 28 | 25 | 16 |
| P4 | 5 | 3 | 9 | 4 | 1 |
| P5 | 6 | 5 | 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 13: 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 | 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 | Arrival Time | Burst Time | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 8 | 8 | 0 |
| P2 | 1 | 4 | 15 | 14 | 10 |
| P3 | 2 | 9 | 29 | 27 | 18 |
| P4 | 3 | 5 | 20 | 17 | 12 |
| P5 | 4 | 3 | 11 | 7 | 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 Turn Around Time (TAT) = (8+14+27+17+7)/5=14.6 units
Average Waiting Time (WT) = (0+10+18+12+4)/5 = 8.8 units
Question 14: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF or SRTF(SHORTEST REMAINING TIME FIRST) process scheduling algorithm?
| 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 | Arrival Time | Burst Time | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 5 | 7 | 7 | 2 |
| P2 | 1 | 2 | 3 | 2 | 0 |
| P3 | 3 | 4 | 14 | 11 | 7 |
| P4 | 4 | 3 | 10 | 6 | 3 |
| P5 | 5 | 6 | 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 15: 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 | 10 |
| P2 | 1 | 1 |
| P3 | 2 | 2 |
| P4 | 3 | 1 |
| P5 | 4 | 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 | Arrival Time | Burst Time | Completion Time | Turn Around Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 10 | 10 | 10 | 0 |
| P2 | 1 | 1 | 11 | 10 | 9 |
| P3 | 2 | 2 | 14 | 12 | 10 |
| P4 | 3 | 1 | 12 | 9 | 8 |
| P5 | 4 | 5 | 19 | 15 | 10 |
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) = (10+10+12+9+15)/5 = 11.2 units
Average Waiting Time (WT) = (0+9+10+8+10)/5 = 7.4 units
Question 16: 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 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
| P5 | 6 | 3 |
Solution :
Formulas:
- Turnaround Time (TAT) = Completion Time - Arrival Time
- Waiting Time (WT) = Turnaround Time - Burst Time
Gantt Chart
| Process | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 - 0 = 7 | 7 - 7 = 0 |
| P2 | 2 | 4 | 15 | 15 - 2 = 13 | 13 - 4 = 9 |
| P3 | 4 | 1 | 8 | 8 - 4 = 4 | 4 - 1 = 3 |
| P4 | 5 | 4 | 19 | 19 - 5 = 14 | 14 - 4 = 10 |
| P5 | 6 | 3 | 11 | 11 - 6 = 5 | 5 - 3 = 2 |
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 = (7 + 13 + 4 + 14 + 5) / 5 = 43 / 5 = 8.6 units
Average WT = (0 + 9 + 3 + 10 + 2) / 5 = 24 / 5 = 4.8 units
Question 17: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF or SRTF(SHORTEST REMAINING TIME FIRST) process scheduling algorithm?
| 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 | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 9 | 24 | 24 - 0 = 24 | 24 - 9 = 15 |
| P2 | 1 | 3 | 4 | 4 - 1 = 3 | 3 - 3 = 0 |
| P3 | 2 | 6 | 16 | 16 - 2 = 14 | 14 - 6 = 8 |
| P4 | 3 | 2 | 6 | 6 - 3 = 3 | 3 - 2 = 1 |
| P5 | 5 | 4 | 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 18: 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:
- Turnaround Time (TAT) = Completion Time - Arrival Time
- Waiting Time (WT) = Turnaround Time - Burst Time
Gantt Chart
| Process | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 8 | 8 - 0 = 8 | 8 - 8 = 0 |
| P2 | 1 | 4 | 14 | 14 - 1 = 13 | 13 - 4 = 9 |
| P3 | 2 | 9 | 28 | 28 - 2 = 26 | 26 - 9 = 17 |
| P4 | 3 | 5 | 19 | 19 - 3 = 16 | 16 - 5 = 11 |
| P5 | 4 | 2 | 10 | 10 - 4 = 6 | 6 - 2 = 4 |
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 = (8 + 13 + 26 + 16 + 6) / 5 = 69 / 5 = 13.8 units
Average WT = (0 + 9 + 17 + 11 + 4) / 5 = 41 / 5 = 8.2 units
Question 19: find the average Turn Around Time and Waiting Time of following processes using Preemptive SJF or SRTF(SHORTEST REMAINING TIME FIRST)process scheduling algorithm?
| 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 | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 10 | 29 | 29 - 0 = 29 | 29 - 10 = 19 |
| P2 | 1 | 3 | 4 | 4 - 1 = 3 | 3 - 3 = 0 |
| P3 | 2 | 7 | 20 | 20 - 2 = 18 | 18 - 7 = 11 |
| P4 | 3 | 4 | 8 | 8 - 3 = 5 | 5 - 4 = 1 |
| P5 | 5 | 5 | 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
Question 20: 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 | 1 | 6 |
| P2 | 2 | 3 |
| P3 | 3 | 4 |
| P4 | 4 | 2 |
| P5 | 5 | 5 |
| P6 | 6 | 3 |
Solution :
Formulas:
- Turnaround Time (TAT) = Completion Time - Arrival Time
- Waiting Time (WT) = Turnaround Time - Burst Time
Gantt Chart
| Process | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 1 | 6 | 7 | 7 - 1 = 6 | 6 - 6 = 0 |
| P2 | 2 | 3 | 12 | 12 - 2 = 10 | 10 - 3 = 7 |
| P3 | 3 | 4 | 19 | 19 - 3 = 16 | 16 - 4 = 12 |
| P4 | 4 | 2 | 9 | 9 - 4 = 5 | 5 - 2 = 3 |
| P5 | 5 | 5 | 24 | 24 - 5 = 19 | 19 - 5 = 14 |
| P6 | 6 | 3 | 15 | 15 - 6 = 9 | 9 - 3 = 6 |
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 = (6 + 10 + 16 + 5 + 19 + 9) / 6 = 65 / 6 = 10.83 units
Average WT = (0 + 7 + 12 + 3 + 14 + 6) / 6 = 42 / 6 = 7 units