--- title: "Avg turnaround: FCFS, RR, SJF, SRT, HRRN" subject: "Operating System" chapter: 2 key: "semester_6/operating_system:avg-turnaround-fcfs-rr-sjf-srt-hrrn" source: https://www.bctengineer.com/q/semester_6/operating_system/avg-turnaround-fcfs-rr-sjf-srt-hrrn site: BCT Engineering --- # Avg turnaround: FCFS, RR, SJF, SRT, HRRN Operating System · Chapter 2: Process Management - Asked in: 2070 Magh, 10 marks - Video: [L-2.7: Round Robin(RR) CPU Scheduling Algorithm with Example](https://www.youtube.com/watch?v=TxjIlNYRZ5M) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/avg-turnaround-fcfs-rr-sjf-srt-hrrn - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-2 ## Question For the processes listed in the following table, what is the average turnaround time using: (a) FCFS (b) RR (quantum=4) (c) SJF (d) SRT (e) HRRN | Process | Arrival Time (ms) | Processing Time (ms) | |---|---|---| | A | 0 | 3 | | B | 2 | 6 | | C | 4 | 4 | | D | 6 | 5 | | E | 8 | 2 | ## Short answer Average turnaround times are FCFS 8.6 ms, RR (q=4) 10.0 ms, SJF 7.6 ms, SRT 7.2 ms, and HRRN 8.0 ms. SRT gives the lowest average turnaround time. ## Answer Turnaround time = completion time − arrival time. Assumptions: in round robin, a process that arrives at the same instant a quantum expires joins the queue before the preempted process; SJF is non-preemptive; SRT (shortest remaining time) is its preemptive version. #### (a) FCFS **Order of arrival: A, B, C, D, E** ```text | A | B | C | D | E | 0 3 9 13 18 20 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | A | 0 | 3 | 3 | 3 | 0 | | B | 2 | 6 | 9 | 7 | 1 | | C | 4 | 4 | 13 | 9 | 5 | | D | 6 | 5 | 18 | 12 | 7 | | E | 8 | 2 | 20 | 12 | 10 | Average turnaround = 43/5 = **8.6 ms** #### (b) Round robin, q = 4 Queue evolution: A runs 0-3 (finishes); B 3-7 (needs 2 more); C 7-11 (finishes); D 11-15 (1 more); B 15-17 (finishes); E 17-19 (finishes); D 19-20 (finishes). **Gantt chart** ```text | A | B | C | D | B | E | D | 0 3 7 11 15 17 19 20 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | A | 0 | 3 | 3 | 3 | 0 | | B | 2 | 6 | 17 | 15 | 9 | | C | 4 | 4 | 11 | 7 | 3 | | D | 6 | 5 | 20 | 14 | 9 | | E | 8 | 2 | 19 | 11 | 9 | Average turnaround = 50/5 = **10 ms** #### (c) SJF (non-preemptive) At t = 3 only B is ready. At t = 9 the ready jobs are C(4), D(5) and E(2): E is shortest, then C, then D. **Gantt chart** ```text | A | B | E | C | D | 0 3 9 11 15 20 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | A | 0 | 3 | 3 | 3 | 0 | | B | 2 | 6 | 9 | 7 | 1 | | C | 4 | 4 | 15 | 11 | 7 | | D | 6 | 5 | 20 | 14 | 9 | | E | 8 | 2 | 11 | 3 | 1 | Average turnaround = 38/5 = **7.6 ms** #### (d) SRT (preemptive SJF) B (6) starts at 3. At t = 4, C (4) arrives with less remaining time than B (5), so C preempts B. At t = 8, C finishes just as E (2) arrives; E is now the shortest, so E runs. After that, B and D both need 5; B arrived earlier, so B runs, then D. **Gantt chart** ```text | A | B | C | E | B | D | 0 3 4 8 10 15 20 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | A | 0 | 3 | 3 | 3 | 0 | | B | 2 | 6 | 15 | 13 | 7 | | C | 4 | 4 | 8 | 4 | 0 | | D | 6 | 5 | 20 | 14 | 9 | | E | 8 | 2 | 10 | 2 | 0 | Average turnaround = 36/5 = **7.2 ms** #### (e) HRRN (non-preemptive) Response ratio = (waiting + service)/service. At t = 9: C = (5+4)/4 = 2.25, D = (3+5)/5 = 1.6, E = (1+2)/2 = 1.5, so C runs. At t = 13: D = (7+5)/5 = 2.4, E = (5+2)/2 = 3.5, so E runs, then D. **Gantt chart** ```text | A | B | C | E | D | 0 3 9 13 15 20 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | A | 0 | 3 | 3 | 3 | 0 | | B | 2 | 6 | 9 | 7 | 1 | | C | 4 | 4 | 13 | 9 | 5 | | D | 6 | 5 | 20 | 14 | 9 | | E | 8 | 2 | 15 | 7 | 5 | Average turnaround = 40/5 = **8 ms** #### Summary | Algorithm | Average turnaround time (ms) | |---|---| | FCFS | 8.6 | | RR (q=4) | 10 | | SJF | 7.6 | | SRT | 7.2 | | HRRN | 8 | **Answer: FCFS 8.6, RR 10.0, SJF 7.6, SRT 7.2, HRRN 8.0 ms.** SRT gives the lowest average turnaround time. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is turnaround time calculated for each process in this problem? A. Completion time - arrival time B. Completion time - burst time C. Arrival time + burst time D. Waiting time - burst time Answer: A. Turnaround is the time from arrival to completion; waiting time is then turnaround minus burst. (Key point: Turnaround formula) 2. How is the HRRN response ratio computed, and which process is picked? A. (waiting + service) / service; the highest ratio runs B. service / (waiting + service); the lowest ratio runs C. waiting / service; the lowest ratio runs D. (waiting + service) x service; the highest runs Answer: A. HRRN favours processes that have waited long relative to their length; at t=9 C has 2.25, the highest, so C runs. (Key point: HRRN response ratio) 3. In SRT, why does C (burst 4) preempt B at t=4? A. C has a higher priority number B. C arrived later C. C's burst 4 is less than B's remaining time 5 D. B's quantum expired Answer: C. SRT always runs the process with the shortest remaining time; B has 5 left, C needs only 4. (Key point: SRT preemption) 4. Which algorithm gave the least average turnaround time, and what value? A. FCFS, 8.6 ms B. SJF, 7.6 ms C. SRT, 7.2 ms D. HRRN, 8 ms Answer: C. SRT gives 36/5 = 7.2 ms, lower than SJF 7.6, HRRN 8, FCFS 8.6 and RR 10. (Key point: Best average turnaround) ## Related in Operating System - [FCFS, SJF, RR Gantt and turnaround](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afcfs-sjf-rr-q5-timeline) — Operating System, chapter 2 - [FCFS, SJF, Priority, RR Gantt; max AWT](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ascheduling-gantt-fcfs-sjf-priority-rr-q2) — Operating System, chapter 2 - [HRRN and RR scheduling (q=4)](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ahrrn-rr-q4-awt-att) — Operating System, chapter 2 - [RR, preemptive priority, preemptive SJF](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Aprocess-rr-priority-preemptive-sjf) — Operating System, chapter 2 - [Two processors: priority and RR (q=3)](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Atwo-processor-priority-rr-q3) — Operating System, chapter 2 ## Related in other subjects - [Preemptive SJF/SRT scheduling (10, 5, 7 ms)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-srt-10-5-7) — Embedded System, chapter 6