PSoC5LP RTOS
Lab 26 — Schedulability Analysis (RMA, WCET & Response-Time Analysis)

FreeRTOS on PSoC 5LP · Lab Series Platform: CY8CKIT-059 (PSoC 5LP, Cortex-M3) · PSoC Creator 4.4 · FreeRTOS Kernel V11 Theme: assign priorities by rule, measure the numbers, then prove the deadlines Pairs with: Chapter 2 — Timing & Priority & Chapter 13 — Architecture & Reliability

1. Introduction & Objectives

Every lab so far has assigned task priorities by judgement — "the sensor is more important, give it a higher number". For a real-time system that is not enough: you need a method to assign priorities and a proof that every task still meets its deadline under the worst case. This lab is the theory that underpins all the others. You model the tasks as periodic (period T, worst-case execution time C, deadline D), assign priorities by the Rate-Monotonic rule, and test schedulability two ways: the quick utilisation bound and the exact response-time analysis (RTA) — checking the maths against a real schedule on the board.

After this lab you can:

Model tasks with the periodic parameters T, C, D and compute utilisation U = C/T.
Measure a task's WCET (C) on the hardware (timing pins, Lab 12; run-time stats, Lab 23).
Assign priorities by Rate-Monotonic (shorter period → higher priority) and say why it is optimal.
Apply the Liu & Layland utilisation bound and know that it is sufficient but not necessary.
Compute exact worst-case response times with RTA and decide schedulability (R ≤ D).
Account for blocking (B) from shared resources, linking Lab 09/17/24 into the analysis.

2. Prerequisites

Hardware - CY8CKIT-059 PSoC 5LP Prototyping Kit - RobotSoC Kit: three timing pins to a logic analyzer (to measure C and observe preemption)

Software - PSoC Creator 4.4 with the FreeRTOS V11 BaseProject

Chapters (sync progress) - Required: Chapter 2 (Timing & Priority — preemption and fixed priorities) and Chapter 13 (architecture & reliability). - Related: Lab 04 (preemption, priorities, starvation), Lab 05 (periodic tasks), Lab 12 (timing pins for WCET), Lab 23 (run-time stats), Lab 09/17/24 (the blocking sources).

3. Reading Materials / References

Chapter 2 slides — Timing & Priority (fixed-priority preemptive scheduling).
Liu & Layland (1973) — the Rate-Monotonic bound; response-time analysis (Joseph & Pandya; Audsley et al.).
FreeRTOS API: xTaskDelayUntil, uxTaskPriorityGet/Set, the run-time stats from Lab 23 for measuring C.

4. Background & Theory of Operation

The periodic task model. Model each task i by three numbers: its period Tᵢ (how often it is released), its worst-case execution time Cᵢ (the longest it ever runs per release), and its deadline Dᵢ (by when it must finish — commonly Dᵢ = Tᵢ). Its utilisation is Uᵢ = Cᵢ / Tᵢ, the fraction of the CPU it needs; the system's total is U = Σ Uᵢ. C is the one number you cannot guess — you measure it on the real hardware (pulse a pin around the work, Lab 12; or read the run-time counter, Lab 23) and take the maximum over many runs.

Rate-Monotonic assignment. Given the periods, the Rate-Monotonic (RM) rule assigns shorter period → higher priority. For independent periodic tasks with D = T, RM is the optimal fixed-priority assignment: if any fixed-priority ordering can meet all deadlines, RM can. It turns "what priority?" from a judgement call into a rule you can defend.

Test A — the utilisation bound (quick, sufficient). Liu & Layland proved that n periodic tasks under RM are schedulable if

Σ Cᵢ/Tᵢ ≤ n ( 2^(1/n) − 1 )

The right-hand side falls from 1.00 (n=1) to 0.828 (n=2) to 0.780 (n=3) … toward ln 2 ≈ 0.693 as n → ∞. If your total utilisation is at or below the bound, you are guaranteed schedulable — done. But the bound is sufficient, not necessary: a set above it may still meet every deadline. A fail is inconclusive, not a verdict of unschedulable — so you move to the exact test.

Test B — response-time analysis (exact). RTA computes each task's worst-case response time Rᵢ — the longest from release to completion — which occurs at the critical instant, when the task is released together with every higher-priority task. The response is the task's own work plus all the interference from higher-priority tasks that preempt it:

Rᵢ = Cᵢ + Bᵢ + Σ_{j ∈ hp(i)} ⌈Rᵢ / Tⱼ⌉ · Cⱼ

Rᵢ appears on both sides, so you solve it by iteration: start at Rᵢ = Cᵢ + Bᵢ, recompute, repeat until it stops changing (a fixed point) or exceeds Dᵢ. The set is schedulable if and only if Rᵢ ≤ Dᵢ for every task — this test is both necessary and sufficient for fixed-priority preemptive scheduling, so it gives a definitive answer where the bound could not.

The blocking term Bᵢ. A high-priority task can be delayed not only by preemption but by waiting on a lower-priority task that holds a shared resource — a mutex (Lab 09/17) or a critical section (Lab 24). That delay is the blocking term Bᵢ, added into the RTA. Priority inheritance (Lab 09) is what makes Bᵢ bounded — without it, blocking could be unbounded (priority inversion) and no deadline guarantee would hold. This is where the synchronisation labs connect to the timing proof.

The worked example (used in the figures). Three tasks, D = T: τ1(T=10, C=4), τ2(T=15, C=4), τ3(T=20, C=4). Utilisations 0.40 + 0.27 + 0.20 = 0.87. The bound for n=3 is 0.78, and 0.87 > 0.78, so Test A cannot decide. RM order is τ1 > τ2 > τ3. RTA gives R1 = 4, R2 = 8, and R3 = 20 — and since R3 = 20 ≤ D3 = 20, the set is schedulable, with τ3 just meeting its deadline. This is exactly why you need both tests: the bound is a fast screen, RTA is the proof.

5. The Analysis, at a Glance

The workflow: measure C on real hardware, assign priorities by Rate-Monotonic, apply Test A (the utilisation bound) as a quick screen, and when it is inconclusive, apply Test B (response-time analysis) for an exact answer. The blocking term Bᵢ folds the shared-resource delays from Labs 09/17/24 into the response time. The panels give both tests and the example where the bound fails but RTA proves schedulability.

6. The Analysis Over Time

The utilisation bound — and why it is only the first test:

A task set at or below the curve is guaranteed schedulable under RM; our set (ΣU = 0.87, above the n=3 bound of 0.78) sits in the region where the bound cannot decide — so RTA settles it.

Critical instant — the worst case for the lowest-priority task:

Released together with τ1 and τ2, τ3 is preempted by every one of their releases; summing that interference is exactly the RTA equation, and the schedule confirms R₃ = 20 ms = D₃.

Together the diagrams show the method's logic: the bound is a fast screen, the critical-instant response time is the proof, and a real schedule on the board confirms the arithmetic.

7. Schematic Circuit & Pin Configuration

TP1 / TP2 / TP3 → one timing pin per task to a logic analyzer; pin-high time = that task's execution, so you read C directly and see preemption.
Assign the pins in <project>.cydwr → Pins.

8. PSoC Creator Configuration

Three Digital Output Pins (TP1–TP3); optionally the run-time-stats timer from Lab 23 for a second C measurement.
FreeRTOSConfig.h (already set): configUSE_PREEMPTION = 1, configUSE_TIME_SLICING = 1 (course default — note it does not affect tasks at distinct priorities, which is the RM case), heap_4.

9. Provided Template

You are given Lab26_Template_main.c:

Given: all includes (note #include "FreeRTOS_PSoC.h"), three periodic tasks on xTaskDelayUntil grids (10/15/20 ms) that pulse a TP pin around a busy_work() chunk, a complete main() that creates them with Rate-Monotonic priorities, and an rta_check() helper that runs the RTA iteration for you.
You write: calibrate busy_work() to hit each target C, measure each C on the scope, and feed the measured numbers into rta_check() to get the verdict.
Do not change the boot sequence in main().

/* RTA iteration (the heart of rta_check): ceil(R/Tj) = (R + Tj - 1)/Tj */
uint32_t R = C[i] + B[i];
for (;;) {
    uint32_t w = C[i] + B[i];
    for (j = 0; j < i; j++)                 /* higher-priority tasks */
        w += ((R + T[j] - 1) / T[j]) * C[j];
    if (w == R) break;                      /* fixed point reached   */
    R = w;
    if (R > D[i]) break;                    /* deadline already missed */
}
/* schedulable iff R <= D[i] */

10. Lab Experiments

Exp01 — Basic: measure the WCET

Calibrate busy_work() so each task's execution matches a target C, then measure the actual C of each task as the pin-high time on the analyzer, taking the maximum over many releases. Compute each Uᵢ and the total U. Expected: three measured C values, a utilisation table, and the observation that C must be measured, not assumed.

Exp02 — Advanced: run both tests

Apply Test A (the utilisation bound for n=3) to your measured U; then run Test B by feeding the measured C, T, D into rta_check(). Read R1, R2, R3 and compare each to its deadline. Confirm the case where the bound is inconclusive but RTA gives a definitive pass (as in the example set). Expected: a bound result, an RTA result (R ≤ D per task), and a statement of why a "fail" on the bound did not mean unschedulable.

Exp03 — Challenge: push to the edge, and add blocking

Raise one task's C until RTA reports Rᵢ > Dᵢ for some task, and confirm on the analyzer that the predicted task indeed misses its deadline at that load — the theory matches the board. Then add a shared mutex between two tasks (Lab 17), measure the blocking Bᵢ the critical section imposes, add it to rta_check(), and show how it changes the response times. Expected: a measured deadline miss that RTA predicted, and a demonstration that the blocking term is a real part of the response time (and why inheritance must bound it).

11. Testing & Verification

#	Pass condition
Exp01	Each task's C (WCET) is measured on the analyzer; U per task and total computed.
Exp02	The utilisation bound and RTA are both applied; R ≤ D decided per task with the given helper.
Exp03	A predicted deadline miss is reproduced on the board; a measured blocking term is folded into RTA.

Submit: your measured C/U table, your Test A and Test B results with R per task, and your Exp03 deadline-miss + blocking demonstration.

12. Q&A & Troubleshooting

Measured C varies a lot → take the maximum over many runs; cache/flash-wait and interrupts cause spread — that spread is why you measure WCET, not average.
RTA iteration never settles → it only converges while U < 1; if it climbs past Dᵢ the task is unschedulable — stop and report the miss.
The bound says "fail" but the board meets deadlines → correct and expected; the bound is sufficient, not necessary — trust RTA (or the measured schedule).
A task misses its deadline that RTA passed → your measured C was too low (not the true worst case), or there is unaccounted blocking Bᵢ; re-measure and add B.
Time slicing muddies the picture → RM uses distinct priorities, where slicing has no effect; equal priorities (round-robin) are outside this model.
Priorities look wrong → RM is by period, not by importance; the shortest period must be the highest priority.

13. Analysis Questions & Lab Report

Define T, C, D, and U, and explain why C must be measured as a worst case rather than assumed.
State the Rate-Monotonic rule and why it is the optimal fixed-priority assignment for D = T.
Why is the utilisation bound sufficient but not necessary, and what does a "fail" on it actually tell you?
Write the RTA equation, explain the critical instant, and show how the blocking term Bᵢ and priority inheritance enter the analysis.

Your report should include your measured C/U table, both test results with R per task, your deadline-miss demonstration, and answers to the four questions.

PSoC5LP RTOSLab 26 — Schedulability Analysis (RMA, WCET & Response-Time Analysis)