GATE Overflow Test Series | Operating Systems | Test 1 | Question: 30

Question

Consider the following set of processes, with the arrival times and the CPU-burst times gives in milliseconds.
$$\begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Burst Time}
\\\hline P_{1} & 0 & 8
\\\hline P_{2} & 1 & 4
\\\hline P_{3} & 3 & 3
\\\hline P_{4} & 4 & 2
\\\hline \end{array}$$
The average turnaround time for these processes with the preemptive shortest remaining time first (SRTF) algorithm is _______

Answer 1

Starting times of the processes are $0,1,7$ and $5$ respectively.

Completion times of the processes are $17,5,10$ and $7$ respectively.

Turnaround times of the processes are $17-0 = 17, 5-1=4, 10-3=7$ and $7-4=3$ respectively.

So, average turnaround time $ = \dfrac{17+4+7+3}{4} = 7.75$

Answer 2

$\textbf{Shortest Remaining Time First (SRTF)}:$ Selects the process for execution which has the smallest amount of time remaining until completion.

• The shortest remaining time first scheduling algorithm may lead to starvation. If the short processes are continually added to the CPU scheduler then the currently running process will never be able to execute, hence SRTF is not starvation free.
• The shortest remaining time is optimal and it mostly gives a minimum average waiting time for a given set of CPU bursts of the processes.
• In SRTF, We will never know the next burst length. We can only estimate the length of the next burst length.

1. Turnaround Time:   It is the total time taken by the process between starting and the completion
2. Waiting Time: It is the time for which process is ready to run but not executed by the CPU scheduler
3. Response time: The time taken in a program from the issuance of a command to the commence of a response to that command. (i.e., the time interval between submission of a request, and the first response to that request, not the output ). (or) response time is the difference between first execution time and Arrival time.

$$\begin{array}{|c|c|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Burst Time} &  \textbf{Completion Time} & \textbf{Turn Around Time} & \textbf{Waiting Time} & \textbf{Response Time}
\\\hline P_{1} & 0 & 8 & 17 & 17 & 9 & 0
\\\hline P_{2} & 1 & 4 & 5 & 4 & 0 & 0
\\\hline P_{3} & 3 & 3 & 10 & 7 & 4 & 4
\\\hline P_{4} & 4 & 2 & 7 & 3 & 1 & 1
\\\hline \end{array}$$

Average turnaround time $ = \dfrac{17 + 4 + 7 + 3}{4} = \dfrac{31}{4} = 7.75.$

So, the correct answer is $7.75\;\text{msec}.$