--- title: "Real-time scheduling; two-processor numerical" subject: "Operating System" chapter: 2 key: "semester_6/operating_system:realtime-two-processor-fcfs-sjf-priority-rr" source: https://www.bctengineer.com/q/semester_6/operating_system/realtime-two-processor-fcfs-sjf-priority-rr site: BCT Engineering --- # Real-time scheduling; two-processor numerical Operating System · Chapter 2: Process Management - Asked in: 2075 Baisakh, 2+8 marks - Video: [Rate Monotonic Scheduling](https://www.youtube.com/watch?v=xgW8VhEOpFg) — Manoj MVR - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/realtime-two-processor-fcfs-sjf-priority-rr - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-2 ## Question What is the real time scheduling? Consider the following set of process, with the length of the burst time given in milliseconds: (Assume the system has two processors P1 and P2). | Process | Burst time | Priority | |---|---|---| | P1 | 10 | 3 | | P2 | 1 | 1 | | P3 | 2 | 3 | | P4 | 1 | 4 | | P5 | 5 | 2 | The processes are assumed to have arrived in order p1, p2, p3, p4, p5 all at time 0. Compute the AWT and ATAT for each of the scheduling algorithms: (1) FCFS (2) SJF (3) Pre-emptive priority (4) RR (q=1) scheduling. ## Short answer Real-time scheduling ensures tasks complete by deadlines. For the two-processor set, average waiting and turnaround times are: FCFS 1.6 ms and 5.4 ms; SJF 1 ms and 4.8 ms; preemptive priority 2.6 ms and 6.4 ms; Round Robin (q=1) 1.4 ms and 5.2 ms. SJF yields the lowest values. ## Answer **Real-time scheduling** is scheduling of tasks that must complete within given deadlines. The correctness of the system depends on both the result and the time at which it is produced. In **hard** real-time systems a missed deadline is a failure; in **soft** ones it only degrades quality. Tasks are periodic or aperiodic; algorithms include Rate Monotonic (static, shortest period = highest priority) and Earliest Deadline First (dynamic), using preemptive priority-based dispatching with bounded latency. #### Numerical (two processors CPU1 and CPU2) Assumptions: one shared ready queue; a free CPU takes the next process; all arrive at time 0 in order P1 to P5; priority 1 is highest; SJF is non-preemptive; CPU1 is filled first. **1) FCFS** ```text CPU1 | P1 | 0 10 CPU2 | P2 | P3 | P4 | P5 | 0 1 3 4 9 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 10 | 10 | 10 | 0 | | P2 | 0 | 1 | 1 | 1 | 0 | | P3 | 0 | 2 | 3 | 3 | 1 | | P4 | 0 | 1 | 4 | 4 | 3 | | P5 | 0 | 5 | 9 | 9 | 4 | AWT = 8/5 = **1.6 ms**; ATAT = 27/5 = **5.4 ms** **2) SJF** ```text CPU1 | P2 | P3 | P1 | 0 1 3 13 CPU2 | P4 | P5 | 0 1 6 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 10 | 13 | 13 | 3 | | P2 | 0 | 1 | 1 | 1 | 0 | | P3 | 0 | 2 | 3 | 3 | 1 | | P4 | 0 | 1 | 1 | 1 | 0 | | P5 | 0 | 5 | 6 | 6 | 1 | AWT = 5/5 = **1 ms**; ATAT = 24/5 = **4.8 ms** **3) Preemptive priority** ```text CPU1 | P2 | P1 | 0 1 11 CPU2 | P5 | P3 | P4 | 0 5 7 8 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 10 | 11 | 11 | 1 | | P2 | 0 | 1 | 1 | 1 | 0 | | P3 | 0 | 2 | 7 | 7 | 5 | | P4 | 0 | 1 | 8 | 8 | 7 | | P5 | 0 | 5 | 5 | 5 | 0 | AWT = 13/5 = **2.6 ms**; ATAT = 32/5 = **6.4 ms** **4) Round Robin (q = 1)** ```text CPU1 | P1 | P3 | P5 | P3 | P1 | 0 1 2 3 4 12 CPU2 | P2 | P4 | P1 | P5 | 0 1 2 3 7 ``` | Process | Arrival | Burst | Completion | Turnaround | Waiting | |---|---|---|---|---|---| | P1 | 0 | 10 | 12 | 12 | 2 | | P2 | 0 | 1 | 1 | 1 | 0 | | P3 | 0 | 2 | 4 | 4 | 2 | | P4 | 0 | 1 | 2 | 2 | 1 | | P5 | 0 | 5 | 7 | 7 | 2 | AWT = 7/5 = **1.4 ms**; ATAT = 26/5 = **5.2 ms** #### Summary | Algorithm | AWT (ms) | ATAT (ms) | |---|---|---| | FCFS | 1.6 | 5.4 | | SJF | 1 | 4.8 | | Preemptive priority | 2.6 | 6.4 | | Round Robin (q = 1) | 1.4 | 5.2 | **Answer:** FCFS 1.6 / 5.4; SJF 1 / 4.8; preemptive priority 2.6 / 6.4; RR (q=1) 1.4 / 5.2 ms (AWT / ATAT). SJF is the best. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What distinguishes hard from soft real-time systems? A. Hard: missed deadline is a failure; soft: it only degrades quality B. Hard: no deadlines; soft: strict deadlines C. Hard systems use only RR D. There is no difference Answer: A. In real-time systems correctness depends on timeliness; a missed deadline is a failure in hard systems and only lowers quality in soft ones. (Key point: Real-time scheduling) 2. What are AWT and ATAT for non-preemptive SJF in this problem? A. 1.6 and 5.4 B. 1 and 4.8 C. 2.6 and 6.4 D. 1.4 and 5.2 Answer: B. Waiting times 3, 0, 1, 0, 1 sum to 5 (1 ms) and turnarounds sum to 24 (4.8 ms). (Key point: SJF on two CPUs) 3. Which of the four algorithms is best and which is worst by AWT? A. Best: FCFS; worst: SJF B. Best: SJF (1 ms); worst: preemptive priority (2.6 ms) C. Best: RR; worst: SJF D. Best: preemptive priority; worst: RR Answer: B. AWT values are FCFS 1.6, SJF 1, priority 2.6, RR 1.4, so SJF is best and preemptive priority is worst. (Key point: Best algorithm) ## 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 - [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 - [Preemptive priority and SRTF Gantt](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apreemptive-priority-srtf-gantt) — 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 - [Preemptive vs non-preemptive; real-time scheduling](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apreemptive-nonpreemptive-realtime) — Operating System, chapter 2 - [Context switching, 5-state model, MLFQ](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acontext-switch-5state-mlfq) — 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 priority scheduling (10, 5, 7 ms)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-priority-nonpreemptive-10-5-7) — Embedded System, chapter 6, asked 2×