--- title: "Rate Monotonic real-time schedule" subject: "Operating System" chapter: 2 key: "semester_6/operating_system:rate-monotonic-schedule" source: https://www.bctengineer.com/q/semester_6/operating_system/rate-monotonic-schedule site: BCT Engineering --- # Rate Monotonic real-time schedule Operating System · Chapter 2: Process Management - Asked in: 2073 Magh, 5 marks - Video: [Rate Monotonic Realtime Scheduling](https://www.youtube.com/watch?v=ERg3tnHxms0) — Ekeeda - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/rate-monotonic-schedule - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-2 ## Question Make a schedule as per Rate Monotonic (RM) algorithm for the following set of real time tasks: | Task, T | Period, P | Execution time, E | Phase, ∅ | |---|---|---|---| | T1 | 4 | 1 | 0 | | T2 | 5 | 2 | 0 | | T3 | 20 | 5 | 0 | ## Short answer Using Rate Monotonic, task T1 (period4) has highest priority, then T2 (period5), then T3 (period20). The schedule meets all deadlines up to the hyperperiod20; CPU utilization0.9 allows feasible execution, so the set is schedulable under RM. ## Answer **Rate Monotonic (RM)** is a static-priority, preemptive scheduling algorithm for periodic real-time tasks: the shorter the period (higher rate), the higher the priority. Priorities are fixed before run time. Each task's deadline is assumed to equal its period. #### Priorities T1 (period 4) > T2 (period 5) > T3 (period 20). All phases are 0, so all tasks are released together at t = 0. The schedule repeats every LCM(4, 5, 20) = 20 time units. #### Utilisation U = 1/4 + 2/5 + 5/20 = 0.25 + 0.40 + 0.25 = **0.90**. The RM bound for 3 tasks is 3(2^(1/3) − 1) = 0.78. Since 0.90 > 0.78 the sufficient test fails, so we must check by simulation (the exact test), and since U ≤ 1 it may still be feasible. #### Schedule (0 to 20) ```text | T1 | T2 | T3 | T1 | T2 | T3 | T1 | T3 | T2 | T1 | 0 1 3 4 5 7 8 9 10 12 13 | T3 | T2 | T1 | T2 | 13 15 16 17 18 ``` Releases: T1 at 0, 4, 8, 12, 16; T2 at 0, 5, 10, 15; T3 at 0. #### Deadline check | Job | Release | Finishes at | Deadline | Met? | |---|---|---|---|---| | T1 (1st-5th) | 0, 4, 8, 12, 16 | 1, 5, 9, 13, 17 | 4, 8, 12, 16, 20 | Yes | | T2 (1st-4th) | 0, 5, 10, 15 | 3, 7, 12, 18 | 5, 10, 15, 20 | Yes | | T3 | 0 | 15 | 20 | Yes | T3 gets only 5 units in the gaps left by T1 and T2: 3-4, 7-8, 9-10 and 13-15, completing at t = 15. The CPU is idle during 18-20 (10% idle, matching U = 0.9). **Answer: The task set is schedulable under RM; all deadlines are met, and the schedule above repeats every 20 time units.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How does Rate Monotonic assign priorities? A. Longer execution time means higher priority B. Shorter period (higher rate) means higher priority, fixed before run time C. Earliest deadline gets highest priority dynamically D. Random priorities each period Answer: B. RM is static-priority: T1 (period 4) > T2 (period 5) > T3 (period 20). (Key point: RM priority rule) 2. What is U for this task set, and what does it imply about the RM bound test? A. 0.90; exceeds the 3-task bound 0.78, so the sufficient test fails and simulation is needed B. 0.60; passes the bound C. 1.2; unschedulable D. 0.78; exactly at the bound Answer: A. U = 1/4 + 2/5 + 5/20 = 0.9 > 0.78, so the test is inconclusive and the exact schedule must be checked. (Key point: Utilisation test) 3. After how many time units does the schedule repeat? A. 4 B. 5 C. 20 (LCM of 4, 5 and 20) D. 40 Answer: C. The schedule repeats every LCM(4,5,20) = 20 units. (Key point: Schedule period) 4. When does T3 complete and are its deadlines met? A. At t=20 and it misses its deadline B. At t=15, meeting its deadline of 20 C. At t=5, before others D. It never runs Answer: B. T3 only gets the gaps 3-4, 7-8, 9-10 and 13-15 (5 units), finishing at 15 before its deadline 20. (Key point: T3 completion) ## Related in Operating System - [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 vs non-preemptive; real-time scheduling](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apreemptive-nonpreemptive-realtime) — Operating System, chapter 2 - [Short note: SSTF algorithm with example](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asstf-algorithm-note) — Operating System, chapter 6 - [Supervisor call; batch, RT, time sharing](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asupervisor-call-os-types) — Operating System, chapter 1 ## Related in other subjects - [Reactance diagram: G, T1, j18 Ω line, T2, M](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Areactance-diagram-g-t1-t2-m) — Power System Analysis I, chapter 3 - [p.u. impedance diagram: G, T1, line, T2, M](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Apu-impedance-diagram-20mva) — Power System Analysis I, chapter 3 - [Corrected bearings, closed link traverse T1-T2](https://www.bctengineer.com/question.md?key=semester_3%2Fsurveying_i%3Aclosed-link-traverse-t1-t2-corrected-bearings) — Surveying I, chapter 4 - [Rate analysis: 20 mm plaster 1:4 per 100 m²](https://www.bctengineer.com/question.md?key=semester_7%2Festimating_and_costing%3Arate-plaster-20mm-1-4) — Estimating and Costing, chapter 4, asked 3×