--- title: "FCFS, SJF, Priority, RR Gantt; max AWT" subject: "Operating System" chapter: 2 key: "semester_6/operating_system:scheduling-gantt-fcfs-sjf-priority-rr-q2" source: https://www.bctengineer.com/q/semester_6/operating_system/scheduling-gantt-fcfs-sjf-priority-rr-q2 site: BCT Engineering --- # FCFS, SJF, Priority, RR Gantt; max AWT Operating System · Chapter 2: Process Management - Asked in: 2070 Bhadra, 4+4 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/scheduling-gantt-fcfs-sjf-priority-rr-q2 - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-2 ## Question Consider the following set of processes with the length of the CPU burst time given in millisecond. | Process | P1 | P2 | P3 | P4 | P5 | |---|---|---|---|---|---| | Burst time | 10 | 1 | 2 | 1 | 2 | | Priority | 3 | 1 | 3 | 4 | 2 | Assume the processes arrived in the order P1, P2, P3, P4 and P5 all at time 0, priority 1 as highest and 4 as lowest. a) Draw the Gantt chart for FCFS, SJF, Priority and Round Robin (Quantum = 2). b) Which algorithm results in the maximum average waiting time? ## Short answer FCFS yields the maximum average waiting time of 9.6 ms due to the convoy effect, while SJF gives the minimum at 2.6 ms. The Gantt charts are: FCFS P1-P2-P3-P4-P5; SJF P2-P4-P3-P5-P1; Priority P2-P5-P1-P3-P4; RR P1-P2-P3-P4-P5-P1. ## Answer Assumptions: all processes arrive at time 0 in the order P1 to P5; priority 1 is highest; for the priority algorithm, ties (P1 and P3 both priority 3) are broken by arrival order (FCFS); SJF is non-preemptive. Waiting time = turnaround − burst (arrival is 0, so turnaround = completion time). #### a) Gantt charts **FCFS** ```text | P1 | P2 | P3 | P4 | P5 | 0 10 11 13 14 16 ``` **SJF** (order of burst: P2=1, P4=1, P3=2, P5=2, P1=10) ```text | P2 | P4 | P3 | P5 | P1 | 0 1 2 4 6 16 ``` **Priority** (order: P2, P5, P1, P3, P4) ```text | P2 | P5 | P1 | P3 | P4 | 0 1 3 13 15 16 ``` **Round Robin, quantum = 2** ```text | P1 | P2 | P3 | P4 | P5 | P1 | 0 2 3 5 6 8 16 ``` #### Waiting and turnaround times | Process | FCFS WT | FCFS TAT | SJF WT | SJF TAT | Priority WT | Priority TAT | RR WT | RR TAT | |---|---|---|---|---|---|---|---|---| | P1 | 0 | 10 | 6 | 16 | 3 | 13 | 6 | 16 | | P2 | 10 | 11 | 0 | 1 | 0 | 1 | 2 | 3 | | P3 | 11 | 13 | 2 | 4 | 13 | 15 | 3 | 5 | | P4 | 13 | 14 | 1 | 2 | 15 | 16 | 5 | 6 | | P5 | 14 | 16 | 4 | 6 | 1 | 3 | 6 | 8 | | **Average** | **9.6** | **12.8** | **2.6** | **5.8** | **6.4** | **9.6** | **4.4** | **7.6** | Example (FCFS): waiting times are 0, 10, 11, 13, 14, so average = 48/5 = 9.6 ms. #### b) Algorithm with the maximum average waiting time | Algorithm | Average waiting time (ms) | |---|---| | FCFS | 9.6 | | SJF | 2.6 | | Priority | 6.4 | | Round Robin (q=2) | 4.4 | **Answer: FCFS gives the maximum average waiting time (9.6 ms)**, because the long process P1 (10 ms) is served first and all short jobs wait behind it (convoy effect). SJF gives the minimum (2.6 ms). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. With priorities P1=3, P2=1, P3=3, P4=4, P5=2 (1 is highest) and ties by arrival order, what is the priority execution order? A. P1, P2, P3, P4, P5 B. P2, P5, P1, P3, P4 C. P4, P1, P3, P5, P2 D. P2, P4, P3, P5, P1 Answer: B. Run priority 1 (P2), then 2 (P5), then P1 before P3 (tie, earlier arrival), and finally P4. (Key point: Priority order) 2. Since all processes arrive at time 0, how is waiting time found? A. Waiting = completion time B. Waiting = turnaround - burst C. Waiting = burst - arrival D. Waiting = quantum x number of turns Answer: B. Turnaround equals completion time here, and waiting time is turnaround minus burst. (Key point: Waiting time method) 3. What is the FCFS average waiting time for the bursts 10, 1, 2, 1, 2 in order? A. 2.6 ms B. 4.4 ms C. 6.4 ms D. 9.6 ms Answer: D. Waiting times are 0, 10, 11, 13, 14, which sum to 48; 48/5 = 9.6 ms. (Key point: FCFS average waiting time) 4. Which algorithm gives the maximum average waiting time and why? A. SJF, because it delays long jobs B. Round robin, because of many context switches C. FCFS, because the long job P1 runs first and short jobs wait behind it (convoy effect) D. Priority, because P4 has the lowest priority Answer: C. FCFS gives 9.6 ms, the highest of 9.6, 2.6, 6.4 and 4.4, due to the convoy effect; SJF gives the minimum. (Key point: Maximum average waiting time) ## 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 - [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 - [Real-time scheduling; two-processor numerical](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arealtime-two-processor-fcfs-sjf-priority-rr) — Operating System, chapter 2 - [Preemptive priority and SRTF Gantt](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apreemptive-priority-srtf-gantt) — 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 - [CPU criteria; RR Gantt and times](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acpu-criteria-rr-gantt) — Operating System, chapter 2 ## Related in other subjects - [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× - [Preemptive priority scheduling with P4 (6 ms)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-priority-10-5-7-p4) — Embedded System, chapter 6, asked 2× - [Priority scheduling (7, 8, 5 ms) with P4](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-priority-7-8-5-p4) — Embedded System, chapter 6, asked 2× - [Non-preemptive SJF with P4 arriving](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-sjf-nonpreemptive-6-8-2) — Embedded System, chapter 6, asked 2×