--- title: "Scheduling algorithms with numerical" subject: "Operating System" chapter: 2 key: "semester_6/operating_system:scheduling-algorithms-numerical" source: https://www.bctengineer.com/q/semester_6/operating_system/scheduling-algorithms-numerical site: BCT Engineering --- # Scheduling algorithms with numerical Operating System · Chapter 2: Process Management - Asked in: year not given - 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/scheduling-algorithms-numerical - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-2 ## Question Explain the FCFS, SJF, SRTN, Round Robin, Priority and HRRN scheduling algorithms with numerical examples. ## Short answer FCFS services in arrival order (AWT 4.75 ms, ATAT 8.75 ms); SJF picks shortest job next (AWT 4, ATAT 8); SRTN preempts for shortest remaining time (AWT 3, ATAT 7); Round Robin (q=2 ms) slices time (AWT 5, ATAT 9); Priority schedules by static rank (AWT 5.5, ATAT 9.5); HRRN uses response ratio to limit starvation (AWT 4, ATAT 8). ## Answer Common data used for all examples (times in ms; priority 1 = highest, used only for the priority algorithm): | Process | Arrival | Burst | Priority | |---|---|---|---| | P1 | 0 | 7 | 3 | | P2 | 2 | 4 | 1 | | P3 | 4 | 1 | 4 | | P4 | 5 | 4 | 2 | Turnaround time = completion − arrival; waiting time = turnaround − burst. #### 1. FCFS Processes are served in order of arrival; non-preemptive. Simple but suffers from the convoy effect. ```text | P1 | P2 | P3 | P4 | 0 7 11 12 16 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 7 | 7 | 7 | 0 | | P2 | 2 | 4 | 11 | 9 | 5 | | P3 | 4 | 1 | 12 | 8 | 7 | | P4 | 5 | 4 | 16 | 11 | 7 | AWT = 19/4 = **4.75**, ATAT = 35/4 = **8.75** #### 2. SJF (non-preemptive) At each completion the ready process with the smallest burst is chosen. It gives minimum average waiting time among non-preemptive algorithms but needs burst estimates and may starve long jobs. ```text | P1 | P3 | P2 | P4 | 0 7 8 12 16 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 7 | 7 | 7 | 0 | | P2 | 2 | 4 | 12 | 10 | 6 | | P3 | 4 | 1 | 8 | 4 | 3 | | P4 | 5 | 4 | 16 | 11 | 7 | AWT = 16/4 = **4**, ATAT = 32/4 = **8** #### 3. SRTN (SRTF, preemptive SJF) The process with the shortest remaining time runs; a new arrival with less remaining time preempts the current one. At t=2 P2 (4) preempts P1 (5 left); at t=4 P3 (1) preempts P2 (2 left); P2 resumes at 5 and ends at 7, then P4 (4) runs, and P1 last. ```text | P1 | P2 | P3 | P2 | P4 | P1 | 0 2 4 5 7 11 16 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 7 | 16 | 16 | 9 | | P2 | 2 | 4 | 7 | 5 | 1 | | P3 | 4 | 1 | 5 | 1 | 0 | | P4 | 5 | 4 | 11 | 6 | 2 | AWT = 12/4 = **3**, ATAT = 28/4 = **7** #### 4. Round Robin (q = 2) Each process runs for at most 2 ms and then goes to the tail of the ready queue; new arrivals join before the preempted process. ```text | P1 | P2 | P1 | P3 | P2 | P4 | P1 | P4 | P1 | 0 2 4 6 7 9 11 13 15 16 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 7 | 16 | 16 | 9 | | P2 | 2 | 4 | 9 | 7 | 3 | | P3 | 4 | 1 | 7 | 3 | 2 | | P4 | 5 | 4 | 15 | 10 | 6 | AWT = 20/4 = **5**, ATAT = 36/4 = **9** #### 5. Priority (non-preemptive) The ready process with the highest priority (smallest number) is chosen at each completion. Low-priority P3 may starve (solved by aging). ```text | P1 | P2 | P4 | P3 | 0 7 11 15 16 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 7 | 7 | 7 | 0 | | P2 | 2 | 4 | 11 | 9 | 5 | | P3 | 4 | 1 | 16 | 12 | 11 | | P4 | 5 | 4 | 15 | 10 | 6 | AWT = 22/4 = **5.5**, ATAT = 38/4 = **9.5** #### 6. HRRN (non-preemptive) Response ratio = (waiting + burst)/burst. At t=7: P2 = (5+4)/4 = 2.25, P3 = (3+1)/1 = 4, P4 = (2+4)/4 = 1.5, so P3 runs; at t=8: P2 = 2.5, P4 = 1.75, so P2 runs. It limits starvation by aging. ```text | P1 | P3 | P2 | P4 | 0 7 8 12 16 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 7 | 7 | 7 | 0 | | P2 | 2 | 4 | 12 | 10 | 6 | | P3 | 4 | 1 | 8 | 4 | 3 | | P4 | 5 | 4 | 16 | 11 | 7 | AWT = 16/4 = **4**, ATAT = 32/4 = **8** #### Comparison | Algorithm | AWT | ATAT | |---|---|---| | FCFS | 4.75 | 8.75 | | SJF (non-preemptive) | 4 | 8 | | SRTN (SRTF, preemptive SJF) | 3 | 7 | | Round Robin (q = 2) | 5 | 9 | | Priority (non-preemptive) | 5.5 | 9.5 | | HRRN (non-preemptive) | 4 | 8 | **Answer:** SRTN gives the least AWT (3.0 ms) and ATAT (7.0 ms); FCFS 4.75 / 8.75; SJF and HRRN 4.0 / 8.0; RR 5.0 / 9.0; priority 5.5 / 9.5. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the FCFS example (P1 0/7, P2 2/4, P3 4/1, P4 5/4), what is the waiting time of P3? A. 5 ms B. 8 ms C. 7 ms D. 12 ms Answer: C. P3 completes at 12, turnaround 12-4 = 8, waiting = 8-1 = 7 ms. (Key point: FCFS waiting time) 2. In SRTN at t=4, why does P3 (burst 1) preempt P2? A. P3 has the highest priority number B. P3 has less remaining time than P2's remaining 2 ms C. P3 arrived last D. P2's quantum expired Answer: B. SRTN always runs the process with shortest remaining time; P3 needs 1 ms while P2 has 2 ms left. (Key point: SRTN preemption) 3. At t=7 in HRRN, which process is chosen and why? A. P3, with the highest response ratio (3+1)/1 = 4 B. P2, because it arrived first C. P4, with the longest burst D. P2, with ratio 2.25 being highest Answer: A. Response ratio = (waiting + burst)/burst; P3 has 4, higher than P2 (2.25) and P4 (1.5). (Key point: HRRN selection) 4. Which algorithm gave the least average waiting time (3 ms) for this data? A. SJF non-preemptive B. SRTN C. Round Robin (q=2) D. HRRN Answer: B. SRTN gave AWT 3 and ATAT 7, better than SJF and HRRN (4), FCFS (4.75), RR (5) and priority (5.5). (Key point: Comparison of algorithms) ## Related in Operating System - [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 - [Avg turnaround: FCFS, RR, SJF, SRT, HRRN](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Aavg-turnaround-fcfs-rr-sjf-srt-hrrn) — Operating System, chapter 2 - [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 - [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 - [Disk scheduling algorithms with numerical](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-scheduling-algorithms-numerical) — Operating System, chapter 6 - [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 ## Related in other subjects - [Round robin scheduling (5, 8, 7 ms, q=2)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-5-8-7-q2) — Embedded System, chapter 6 - [Priority and SJF scheduling with P4 and P5](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-priority-and-sjf-5-process) — Embedded System, chapter 6, asked 2× - [Round robin scheduling (9, 6, 3 ms, q=2)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-9-6-3-q2) — Embedded System, chapter 6, asked 4× - [Round robin scheduling (9, 6, 3 ms, q=3)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-rr-9-6-3-q3) — Embedded System, chapter 6, asked 4×