← All resources

🛠️ Practice & Skills Workbook — the "know-how" you can't just memorise

SECJ4423 / SCSE3143 — Real-Time Software Engineering

The notes cover know-that (theory). This file covers know-how — the procedures you must be able to execute under time pressure: calculations, timelines, tracing, and code. Each skill has: ① the method (steps) → ② a worked example with real exam numbers → ③ common mistakes → ④ drills to redo yourself.

These are where the marks hide in Part B (≈40%) and Q3/Q1 of Part A. Do them with pen & paper, repeatedly, until the steps are automatic.

📋 Skill inventory (ranked by exam weight)

# Skill Where it's tested Type
S1 Assign RM priorities & compute processor utilization vs the bound Part B Q2(a) Calculation
S2 Adjust a period to make a set schedulable, re-compute U Part B Q2(b)(c) Calculation + reasoning
S3 Response Time Analysis iteration until convergence Part B Q2(d) Calculation
S4 Draw a preemptive fixed-priority timeline with semaphore blocking Part B Q1(c) Timeline
S5 Spot priority inversion & apply priority inheritance on the timeline Part B Q1(d)(e) Timeline + reasoning
S6 EDF ordering: who runs first / who misses Part B Q1(f) Reasoning
S7 Count interleavings & trace cobegin outputs Part A Q3(c)(i)(ii) Tracing
S8 Insert semaphores to fix a race (write code) Part A Q3(c)(iii) Code
S9 Map system components onto the RTOS 4-element structure Part A Q4(a) Applied mapping

S1 — Processor Utilization Analysis + RM priority

① Method

  1. List tasks with T (period) and C (WCET).
  2. Assign RM priority: smallest T = highest priority. (Rank them.)
  3. Compute each Uᵢ = Cᵢ / Tᵢ.
  4. Sum: U = Σ Cᵢ/Tᵢ.
  5. Compute the RM bound for n tasks: U(n) = n(2^(1/n) − 1). - Memorise the small table: U(1)=1.00, U(2)=0.828, U(3)=0.779, U(4)=0.756, U(5)=0.743 (→ 0.693 as n→∞).
  6. Decide: - U ≤ U(n) → schedulable (guaranteed). - U > U(n) under RM → inconclusive (test is sufficient only) → must use Response Time Analysis (S3). - For EDF the test is U ≤ 1 (necessary and sufficient).

② Worked example — Drone (ADNOA), Part B Q2(a)

Task T C RM priority (by T) Uᵢ = C/T
Stabilization Control 5 1 1 (highest) 0.20
Obstacle Detection 10 2 2 0.20
Collision Avoidance 20 5 3 0.25
Path Planning 50 10 4 0.20
Telemetry & Display 100 8 5 (lowest) 0.08

③ Common mistakes

④ Drills

S2 — Adjust a period to make it schedulable

① Method

  1. Find the gap: need = U − U(n). You must shed at least this much utilization.
  2. Utilization of a task drops when you increase its period (Uᵢ = Cᵢ/Tᵢ).
  3. Pick a task and set a new, larger period T' so its new Uᵢ' = Cᵢ/T' shrinks enough: Cᵢ/T' ≤ Cᵢ/Tᵢ − need.
  4. Recompute total U and confirm U ≤ U(n).
  5. Discuss the trade-off (this earns the marks in part c): a bigger period = the task runs less often = slower responsiveness. Acceptable for a soft task; dangerous for a hard/safety task.

② Worked example — Drone Q2(b)(c)

③ Common mistakes

④ Drills

S3 — Response Time Analysis (RTA) iteration

① Method

For task i, with hp(i) = all tasks of higher priority (shorter period under RM):

Rix+1 = Ci + Σj ∈ hp(i) ⌈ (Rix)/(Tj) ⌉ Cj
  1. Identify hp(i) — only shorter-period tasks interfere.
  2. Step 1: a₀ = Cᵢ + Σ Cⱼ (over hp).
  3. Step 2: substitute aₙ into the formula (use ceiling ⌈⌉ on each aₙ/Tⱼ).
  4. Step 3 — stop rules: - aₙ₊₁ > Dᵢ → misses deadline (unschedulable). - aₙ₊₁ = aₙ → converged; that value is the WCRT. Schedulable iff WCRT ≤ Dᵢ. - else → repeat Step 2.

② Worked example — Path Planning, Part B Q2(d)

💡 The punchline to write in the "compare" part: the utilization test failed (0.93 > 0.7435, inconclusive), yet RTA proves Path Planning schedulable (35 ≤ 50). RTA is exact (necessary & sufficient); the utilization bound is only sufficient. This is why RTA can pass where utilization "fails."

③ Common mistakes

④ Drills

S4 — Preemptive fixed-priority timeline (with semaphores)

You can't memorise this — you must simulate tick-by-tick. Learn the rules, then practise on Table B1.1.

① Method (rules to apply every tick)

  1. At each time tick, run the highest-priority task that is READY (arrived, not finished, not blocked).
  2. A task becomes ready at its arrival time.
  3. Preemption: if a higher-priority task arrives/unblocks, it immediately takes the CPU; mark the interrupted task preempted.
  4. Semaphore rule: to execute a tick that needs semaphore X, the task must hold X. If another task holds X, the requester blocks (mark blocked) until X is released.
  5. A binary semaphore allows one holder; it's released when the task finishes its use of it.
  6. Follow each task's execution sequence letter-by-letter (E = plain tick, S/C = tick while holding that semaphore).
  7. Continue until the window ends (e.g., t=0→15).

Legend to use: ▓ executing · ▒ preempted (ready but waiting for CPU) · █ blocked (waiting for a semaphore).

② Worked example (canonical priority-inversion pattern — apply the same method to the exam table)

Three tasks, priorities H > M > L, one shared resource R (binary semaphore):

time →     0   1   2   3   4   5   6   7   8
L (low)   ▓R  ▓R  ·   ·   ·   ·   ▓R  ▓R  ·      L grabs R at t0
M (med)   ·   ·   ·   ▓   ▓   ▓   ·   ·   ·      M runs t3–t5 (preempts nothing high)
H (high)  ·   ·   █   █   █   █   ▓R  ...             H wants R at t2 → BLOCKED (L holds R)

③ Applying it to the exam (Table B1.1)

Tasks: T1 Very-High (arr 5, C3, E-S-C-E), T2 High (arr 2, C5, E-C-S-E-C), T3 Med (arr 0, C6), T4 Low (arr 5, C? seq E-S-S-S-E, uses S). Semaphores S, C.

③ Common mistakes

④ Drills

S5 — Priority inversion → priority inheritance

① Method to identify inversion (from your S4 timeline)

② Method to fix with priority inheritance

WITHOUT inheritance:  H blocked ██████ while M runs ▓▓▓ (long inversion)
WITH inheritance:     L inherits H's priority ▓R▓R (M can't preempt) → releases R fast → H runs ▓

③ What to write

④ Drill

S6 — EDF ordering (who runs first / who misses)

① Method

  1. Priority = earliest ABSOLUTE deadline at each decision point (dynamic — recheck as tasks arrive/complete).
  2. Absolute deadline = arrival + relative deadline (or given directly).
  3. First to run = smallest absolute deadline among ready tasks.
  4. To check misses: sum demands up to each deadline; if required work > time available before a deadline, it misses.

② Worked example — Part B Q1(f), Table B1.2

Task Arrival C Absolute deadline
T1 5 3 12
T2 2 5 9
T3 0 6 10
T4 0 5 15
- At t=0, ready = T3 (D=10), T4 (D=15). Earliest deadline = T3 (10) → T3 runs first.
- Watch T2 (arrives t2, D=9, needs 5) and T3 (D=10, needs 6): between them they demand 11 units of CPU before t≈9–10 while also sharing with others → check for a miss by summing required execution before each deadline.
- Evaluation (part iii): EDF gives better CPU utilization (up to 100%) and responsiveness to urgent deadlines, but is less predictable under overload (a single overrun can cascade — domino effect) and has higher runtime overhead than fixed-priority.

③ Common mistake

S7 — Count interleavings & trace cobegin output

① Method

② Worked example — Part A Q3, x=2, y=4

multiply: x = x*y · add: y = y+1+x. Program: cobegin { multiply(1); add(2); multiply(3); add(4); }

Order A — m1, a2, m3, a4:

step op x y prints
m1 x=2·4 8 4 T1: x=8, y=4
a2 y=4+1+8 8 13 T2: x=8, y=13
m3 x=8·13 104 13 T3: x=104, y=13
a4 y=13+1+104 104 118 T4: x=104, y=118
Final: x=104, y=118.

Order B — a2, a4, m1, m3:

step op x y
a2 y=4+1+2 2 7
a4 y=7+1+2 2 10
m1 x=2·10 20 10
m3 x=20·10 200 10
Final: x=200, y=10.

Two different final states → demonstrates non-determinism.

③ Common mistakes

S8 — Insert semaphores to fix a race (write code)

① Method / template

Wrap every shared-variable access in one critical section guarded by a binary semaphore initialised to 1:

semaphore mutex;
initialsem(mutex, 1);

void multiply(int i){
   p(mutex);                 // ← enter CS (wait)
   x = x * y;
   printf("Thread %d: x=%d\n", i, x);
   printf("Thread %d: y=%d\n", i, y);
   v(mutex);                 // ← leave CS (signal)
}
void add(int i){
   p(mutex);
   y = y + 1 + x;
   printf("Thread %d: x=%d\n", i, x);
   printf("Thread %d: y=%d\n", i, y);
   v(mutex);
}

② Common mistakes

S9 — Map components onto the RTOS 4-element structure

① Method

Recall the four elements, then bucket each given component:

RTOS element What goes here
Executive overall control: Task Scheduler, Task Management
Kernel facilities called by the executive: Interrupt Service, Resource Allocator
Application Program Interfaces (APIs) Control Command API, Sensor Data API, Communication API
Real-world interfaces hardware-handling: Infrared/Bumper/LiDAR sensor drivers, motor/brush actuators

② For the vacuum-cleaner obstacle event (Q4)

🧪 Self-test drill set (do these closed-book)

  1. U-test: Tasks (T,C): A(4,1), B(6,2), C(8,2). Assign RM priority, compute U, compare to U(3)=0.779. (U=0.25+0.333+0.25=0.833 > 0.779 → inconclusive.)
  2. RTA: For task C above (T=8,C=2; hp=A(4,1),B(6,2)), iterate to WCRT and compare to D=8.
  3. Interleave count: cobegin { p(); q(); r(); } → how many coarse orderings? (3! = 6.)
  4. Timeline: 2 tasks, H(arr2,C2), L(arr0,C5) preemptive fixed-priority — draw t=0→7, mark preemption.
  5. EDF: Given absolute deadlines D=8,6,10 for X,Y,Z all ready at 0 — which runs first? (Y, deadline 6.)
  6. Fix code: add p()/v() around a shared counter incremented by two cobegin procedures.

Redo #1–#2 and the drone RTA until you can finish each in under 4 minutes. Those are the mark-rich, memorisation-proof skills.

Pair this with Detailed_Notes_Ch5-9.md (theory) and Exam_Topic_Map.md (where each skill is asked). Practise the calculations by hand — reading them is not the same as being able to do them fast.