- 2073 Magh · 5 marks
Rate Monotonic real-time schedule
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.
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 |
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)
| 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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Real-time scheduling; two-processor numerical · Operating System, chapter 2
- Preemptive vs non-preemptive; real-time scheduling · Operating System, chapter 2
- Short note: SSTF algorithm with example · Operating System, chapter 6
- Supervisor call; batch, RT, time sharing · Operating System, chapter 1
- Reactance diagram: G, T1, j18 Ω line, T2, M · Power System Analysis I, chapter 3
- p.u. impedance diagram: G, T1, line, T2, M · Power System Analysis I, chapter 3
- Corrected bearings, closed link traverse T1-T2 · Surveying I, chapter 4
- Rate analysis: 20 mm plaster 1:4 per 100 m² · Estimating and Costing, chapter 4 · asked 3×