Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.
Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
Understanding Shortest Remaining Time First (SRTF) Scheduling
The question asks us to calculate the average turnaround time for four processes ($P_1, P_2, P_3, P_4$) using the Shortest Remaining Time First (SRTF) CPU scheduling algorithm. SRTF is a preemptive scheduling algorithm. This means that if a new process arrives and its execution time is shorter than the remaining time of the currently running process, the CPU will switch to the new process.
Process Details
Here is the information provided for each process:
- Process $P_1$: Arrival Time ($AT_1$) = 0ms, Execution Time ($ET_1$) = 10ms
- Process $P_2$: Arrival Time ($AT_2$) = 1ms, Execution Time ($ET_2$) = 13ms
- Process $P_3$: Arrival Time ($AT_3$) = 2ms, Execution Time ($ET_3$) = 6ms
- Process $P_4$: Arrival Time ($AT_4$) = 8ms, Execution Time ($ET_4$) = 9ms
We need to find the average turnaround time, which is the average time each process spends in the system from arrival to completion.
SRTF Simulation and Gantt Chart
Let's simulate the process execution using SRTF. We'll track the remaining time (RT) for each process. Remember, the process with the shortest RT always runs.
| Time Interval (ms) | Running Process | Event / Ready Queue State | $P_1$ RT | $P_2$ RT | $P_3$ RT | $P_4$ RT | Notes |
|---|---|---|---|---|---|---|---|
| [0, 1) | $P_1$ | $P_1$ arrives (ET=10) | 9 | - | - | - | $P_1$ starts running. |
| [1, 2) | $P_1$ | $P_2$ arrives (ET=13). Ready: {$P_2$(13)} | 8 | 13 | - | - | $P_1$ continues because its remaining time (8ms) is less than $P_2$'s execution time (13ms). |
| [2, 8) | $P_3$ | $P_3$ arrives (ET=6). Ready: {$P_2$(13), $P_3$(6)}. Preemption occurs! | 8 | 13 | 0 (Remaining 0 at t=8) | - | $P_3$'s execution time (6ms) is less than $P_1$'s remaining time (8ms). $P_1$ is preempted, and $P_3$ starts running. $P_3$ completes its execution at time 8ms. $CT_3 = 8$ms. |
| 8 | $P_1$ | $P_3$ completes. $P_4$ arrives (ET=9). Ready Queue: {$P_1$(8), $P_2$(13), $P_4$(9)}. | 8 | 13 | 0 | 9 | From the ready queue, $P_1$ has the shortest remaining time (8ms). $P_1$ resumes execution. |
| [8, 16) | $P_1$ | Ready Queue: {$P_2$(13), $P_4$(9)}. | 0 (Completed at t=16) | 13 | 0 | 9 | $P_1$ runs for the remaining 8ms and completes at time 16ms. $CT_1 = 16$ms. |
| [16, 25) | $P_4$ | Ready Queue: {$P_2$(13), $P_4$(9)}. $P_4$ has the shortest remaining time (9ms). | 0 | 13 | 0 | 0 (Completed at t=25) | $P_4$ starts running and completes its 9ms execution at time 25ms. $CT_4 = 25$ms. |
| [25, 38) | $P_2$ | Ready Queue: {$P_2$(13)}. $P_2$ is the only process left. | 0 | 0 (Completed at t=38) | 0 | 0 | $P_2$ starts running and completes its 13ms execution at time 38ms. $CT_2 = 38$ms. |
Calculating Individual Turnaround Times
The Turnaround Time ($TAT$) for each process is calculated using the formula: $TAT = \text{Completion Time (CT)} - \text{Arrival Time (AT)}$.
- For $P_1$: $TAT_1 = CT_1 - AT_1 = 16ms - 0ms = 16ms$
- For $P_2$: $TAT_2 = CT_2 - AT_2 = 38ms - 1ms = 37ms$
- For $P_3$: $TAT_3 = CT_3 - AT_3 = 8ms - 2ms = 6ms$
- For $P_4$: $TAT_4 = CT_4 - AT_4 = 25ms - 8ms = 17ms$
Calculating Average Turnaround Time
The average turnaround time is the sum of all the individual turnaround times divided by the number of processes (which is 4 in this case).
Average $TAT = \frac{TAT_1 + TAT_2 + TAT_3 + TAT_4}{4}$
Average $TAT = \frac{16ms + 37ms + 6ms + 17ms}{4}$
Average $TAT = \frac{76ms}{4}$
Average $TAT = 19ms$
Thus, the average turnaround time for the four processes using the SRTF algorithm is 19ms.
Important Questions from CPU Scheduling
Assume that the following tasks are to be executed on a single processor system. All tasks have arrived at 0 msec.
Job ID CPU a 4 b 1 c 7 d 2 How long does it take for task "a" to complete if the scheduling time slice is a round-robin with 1 ms?
- Consider the following processes with CPU Burst time P1, P2, P3 arrived at time 0.
Process CPU Burst Time (MS) P1 24 P2 3 P3 3
What is the average waiting time of these processes executed using FCFS algorithm. Consider the following table about processes, their burst time and arrival time
Process Burst Time Arrival Time P1 09 0 P2 30 0 P3 04 0 P4 08 2 P5 11 6
Now which of the process shall finish second last as per the respective GANTT charts for the non- preemptive SJF and Round Robin (time quantum = 10) scheduling methods.- A computer has two processors, $M_1$ and $M_2$. Four processes $P_1, P_2, P_3, P_4$ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:
- $M_1$ uses priority of execution for the processes as, $P_1 > P_3 > P_2 > P_4$, i.e., $P_1$ and $P_4$ have highest and lowest priorities, respectively.
- $M_2$ uses priority of execution for the processes as, $P_2 > P_3 > P_4 > P_1$, i.e., $P_2$ and $P_1$ have highest and lowest priorities, respectively.
- Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time $t = 10$, 20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time $t = 11$, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at $t = 10$ seconds. The average waiting time (in seconds) for the 10 processes is ___________. (rounded off to one decimal place)
