Real-Time Scheduling, Deadline, Jitter, and Latency Exercises

These exercises treat real-time embedded software as a timing assurance problem. The focus is schedulability, deadline margin, release jitter, bus latency, queue absorption and end-to-end response. Firmware recovery, watchdogs and persistent fault handling are covered in the companion firmware reliability exercise set.

Assume screening calculations unless an exercise states otherwise. A release decision still needs target-hardware timing traces, compiler and optimization control, measured worst-case execution time, scheduler configuration, bus captures, interrupt latency evidence and documented acceptance criteria.

Release Evidence Notes

Use each numerical answer as a release screen, not as proof by itself. A credible timing package should identify the released binary, processor clock, cache state, interrupt policy, scheduler tick, priority assignment, bus speed, message identifiers and load case used to justify the result.

Good timing evidence includes measured WCET, interrupt and preemption traces, queue high-water marks, bus analyzer captures, release-jitter bounds and a clear statement of whether the calculated margin is against a hard deadline or a soft service target.

Engineering Boundary Notes

These exercises use simplified fixed-priority, EDF and queue screens. They do not model every cache miss, DMA burst, disabled-interrupt window, garbage-collection pause, clock drift, multicore interference or peripheral erratum. If any of those effects are credible in the product, the calculated margin must be guarded or replaced by measured worst-case evidence.

Scenario Map

Scenario	Exercises	Primary check	Engineering decision
CPU and scheduler loading	1, 3, 4, 12, 15	Utilization, RM bound, EDF demand, sporadic capacity and overhead	Decide whether the processor can host the task set.
Deadline response	2, 6, 7, 8, 9, 16	Response time, jitter, blocking, inversion and interrupt latency	Decide whether hard-deadline tasks have guarded timing margin.
Bus and queue latency	5, 10, 11, 14	CAN arbitration, burst absorption, sampling load and event-loop lag	Decide whether data movement preserves timing and loss requirements.
System-level timing release	13, 17, 18	Hyperperiod, sensing-to-actuation path and release gate	Decide whether the integrated timing case can be released.

Exercise 1: CPU Utilization Including Interrupt Load

A controller has periodic tasks with WCET and period:

Task	WCET	Period
control	0.80\ \text{ms}	5\ \text{ms}
acquisition	0.45\ \text{ms}	10\ \text{ms}
communication	1.10\ \text{ms}	20\ \text{ms}
diagnostics	2.00\ \text{ms}	100\ \text{ms}

An interrupt runs at 3000\ \text{s}^{-1} with 5\ \mu\text{s} handler time. Estimate total CPU utilization.

Solution

Interrupt load is:

Total utilization is:

So the load is 29.5\%.

Engineering Comment

The average processor load is comfortable, but this is not a schedulability proof. It ignores release jitter, blocking, preemption overhead and disabled-interrupt sections.

Plausibility Check

The periodic tasks consume about 28\% and the interrupt adds 1.5\%, so a result just below 30\% is consistent.

Exercise 2: Fixed-Priority Response-Time Analysis

A control task has:

Two higher-priority tasks interfere:

Task	Execution	Period	Release jitter
ADC	0.16\ \text{ms}	1\ \text{ms}	0.08\ \text{ms}
guard	0.22\ \text{ms}	2.5\ \text{ms}	0.15\ \text{ms}

Use response-time iteration.

Solution

Start with:

First iteration:

Repeating gives the same ceilings, so:

Deadline margin is:

Engineering Comment

The task passes this screen because blocking and jitter are included and the response time remains below the deadline.

Plausibility Check

The response is less than half the deadline, so the margin is credible for a first-pass release screen.

Exercise 3: Rate-Monotonic Utilization Bound

Four periodic tasks have utilizations 0.12, 0.18, 0.09 and 0.16. Check them against the Liu-Layland sufficient bound for n=4.

Solution

Total utilization is:

The sufficient RM bound is:

For n=4:

Margin is:

Engineering Comment

The task set passes the sufficient utilization screen. A pass here is useful, but a fail would not prove unschedulability because the bound is conservative.

Plausibility Check

For four tasks the bound is near 76\%; a 55\% set should pass comfortably.

Exercise 4: EDF Processor-Demand Screen

Three implicit-deadline tasks have:

Task	Execution	Period
A	1.0\ \text{ms}	5\ \text{ms}
B	1.5\ \text{ms}	10\ \text{ms}
C	2.0\ \text{ms}	20\ \text{ms}

Check EDF utilization.

Solution

For implicit-deadline EDF, the utilization screen is:

Engineering Comment

The set passes the EDF utilization screen. The release package should still check overhead, timer granularity and whether deadlines are actually equal to periods.

Plausibility Check

Each task has modest load and the total is well below one full processor.

Exercise 5: CAN Arbitration Latency

A critical CAN frame has lower priority than three frames that may be ready first. Their transmission times are 0.24\ \text{ms}, 0.31\ \text{ms} and 0.18\ \text{ms}. The critical frame takes 0.28\ \text{ms}. Estimate worst-case bus delay before the critical frame is complete.

Solution

Assume all higher-priority frames transmit first:

Completion latency is:

Engineering Comment

The result is a simple arbitration screen. A real release case should include bit stuffing, error frames, retransmission policy and whether the assumed higher-priority set is complete.

Plausibility Check

The critical frame waits for less than one millisecond of higher-priority traffic, then uses about 0.3\ \text{ms} itself; 1.01\ \text{ms} is plausible.

Exercise 6: Release-Jitter Budget

A task deadline is 8\ \text{ms}. Its measured execution is 2.1\ \text{ms}, blocking is 0.4\ \text{ms}, interference is 2.8\ \text{ms} and release jitter allowance is 0.7\ \text{ms}. Find deadline margin.

Solution

Worst-case response estimate:

Margin is:

Engineering Comment

Jitter consumes real deadline budget. The release evidence should show how the 0.7\ \text{ms} value was bounded.

Plausibility Check

The largest contributor is interference; the final response being below the 8\ \text{ms} deadline is reasonable.

Exercise 7: Non-Preemptive Blocking Bound

A high-priority task can be blocked by one non-preemptive section. Candidate sections are 0.12\ \text{ms}, 0.45\ \text{ms} and 0.30\ \text{ms}. Determine the blocking term.

Solution

For this screen, the blocking bound is the longest lower-priority non-preemptive section:

Engineering Comment

Only one section is counted in this simplified bound, but the code review must prove that nesting or disabled interrupts cannot create a longer interval.

Plausibility Check

The selected blocking term is the largest listed section, so the arithmetic is direct.

Exercise 8: Priority Inversion with Inheritance

A task has base response 2.4\ \text{ms} before mutex blocking. Without priority inheritance, measured blocking can reach 3.2\ \text{ms}. With inheritance, the blocking bound is 0.55\ \text{ms}. Deadline is 5\ \text{ms}. Compare release decisions.

Solution

Without inheritance:

With inheritance:

Margins:

Engineering Comment

The system fails without priority inheritance and passes with it. The release condition should make the mutex protocol part of the controlled configuration.

Plausibility Check

Reducing blocking by more than 2.5\ \text{ms} changes a deadline miss into a pass, which matches the computed margins.

Exercise 9: Interrupt-Latency Screen

An input capture interrupt must run within 75\ \mu\text{s}. The maximum disabled-interrupt section is 38\ \mu\text{s}, synchronization delay is 9\ \mu\text{s} and ISR entry overhead is 6\ \mu\text{s}. Compute margin.

Solution

Engineering Comment

The interrupt latency screen passes, but the disabled-interrupt section must be measured on the released build and not just estimated from source code.

Plausibility Check

The largest term is the disabled section, and the total remains below the requirement.

Exercise 10: Telemetry Queue Burst Absorption

A queue receives a burst of 120 messages. The consumer drains 900\ \text{messages/s} and the burst lasts 80\ \text{ms}. During the burst, new messages arrive at 1800\ \text{messages/s}. How many queue slots are required?

Solution

Arrival count:

Drained count:

Peak added occupancy:

Engineering Comment

The queue needs more than 192 slots after adding guard margin and existing baseline occupancy. A release test should verify high-water marks under the worst diagnostic burst.

Plausibility Check

The burst itself is 120 messages and the net rate adds another 72, so 192 is consistent.

Exercise 11: Sampling and Processing Load

A sampled signal is acquired at 4\ \text{kHz}. Each sample costs 18\ \mu\text{s} of processing, and a block filter costs 0.60\ \text{ms} every 10\ \text{ms}. Compute CPU load for this acquisition path.

Solution

Per-sample load:

Block-filter load:

Total:

So the acquisition path uses 13.2\% CPU.

Engineering Comment

Sampling math belongs in the timing budget because acquisition can steal time from control tasks even when the signal-processing equations are correct.

Plausibility Check

The high-rate sample handler is noticeable but not dominant; adding a 6\% block filter gives a total near 13\%.

Exercise 12: Sporadic Server Capacity

A sporadic server has budget Q=1.2\ \text{ms} every period P=20\ \text{ms}. A diagnostic burst needs 0.35\ \text{ms} per request. How many requests can be served per server period without exceeding budget?

Solution

Engineering Comment

The server can admit three requests per period. The remaining budget is useful slack but not enough for a fourth request.

Plausibility Check

Three requests cost 1.05\ \text{ms} and four cost 1.40\ \text{ms}, so the floor result is correct.

Exercise 13: Hyperperiod Check

Tasks have periods 5\ \text{ms}, 10\ \text{ms}, 20\ \text{ms} and 50\ \text{ms}. Find the hyperperiod for a cyclic timing review.

Solution

The hyperperiod is the least common multiple:

Prime factors are:

Thus:

Engineering Comment

A 100\ \text{ms} hyperperiod is short enough for trace review. Longer hyperperiods often require statistical trace selection plus targeted critical-instant tests.

Plausibility Check

100\ \text{ms} is divisible by all four periods, and no smaller common multiple includes both 20 and 50.

Exercise 14: Event-Loop Lag Budget

An event loop must service a health timer within 40\ \text{ms}. The queue ahead contains six callbacks taking 3.5\ \text{ms} each, one file callback taking 11\ \text{ms} and scheduler overhead of 2\ \text{ms}. Compute lag margin.

Solution

Engineering Comment

The timer passes, but only with 6\ \text{ms} of margin. A release test should include callback bursts and logging modes, not only nominal UI or service traffic.

Plausibility Check

The six ordinary callbacks contribute 21\ \text{ms}, so a total in the mid-thirties is expected.

Exercise 15: Context-Switch Overhead Load

A system performs 1800 context switches per second. Each switch costs 4.5\ \mu\text{s}. Compute CPU load due to context switching.

Solution

So context switching consumes:

Engineering Comment

This overhead is small, but high-frequency task fragmentation can make it important. The released scheduler tick and tracing configuration should match the test.

Plausibility Check

Thousands of switches at a few microseconds each should remain below one percent CPU.

Exercise 16: Deadline-Monotonic Priority Screen

Three tasks have deadlines 4\ \text{ms}, 12\ \text{ms} and 8\ \text{ms}. Assign deadline-monotonic priority order.

Solution

Deadline-monotonic scheduling assigns higher priority to shorter relative deadlines.

Order by deadline:

So the priority order is:

1. task with 4\ \text{ms} deadline;
2. task with 8\ \text{ms} deadline;
3. task with 12\ \text{ms} deadline.

Engineering Comment

The priority rule is simple, but release evidence must still check blocking and interference. Priority order alone does not prove the task set passes.

Plausibility Check

The task with the tightest deadline receives the highest priority, which is the intended policy.

Exercise 17: End-to-End Sensing-to-Actuation Latency

A control path has ADC wait 0.25\ \text{ms}, input task response 1.4\ \text{ms}, controller response 2.2\ \text{ms}, bus transfer 0.8\ \text{ms} and actuator command update 0.6\ \text{ms}. Requirement is 7\ \text{ms}. Compute margin.

Solution

Engineering Comment

End-to-end timing should be traced across task and bus boundaries. Component-level deadline passes are not enough if the composed path has weak margin.

Plausibility Check

The controller response is the largest single term, and the total remains below the requirement.

Exercise 18: Real-Time Release Gate

A release checklist requires all hard-deadline paths to have at least 15\% timing margin. A path has requirement 12\ \text{ms} and measured guarded worst-case latency 10.7\ \text{ms}. Decide release status.

Solution

Required margin is:

Actual margin is:

Because:

the path fails the release gate.

Engineering Comment

The path meets the raw deadline but fails the guarded release criterion. That should trigger optimization, reduced jitter, changed priority, or a justified exception with stronger evidence.

Plausibility Check

10.7\ \text{ms} is close to 12\ \text{ms}, so failing a 15\% margin rule is expected.

Common Release Mistakes

• Treating average CPU utilization as proof of schedulability.
• Omitting release jitter, blocking, interrupt masking and context-switch overhead.
• Testing bus latency without the worst-priority identifiers and diagnostic bursts.
• Sizing queues from average arrival rate instead of burst occupancy.
• Reporting a deadline pass without documenting the released binary and scheduler configuration.
• Ignoring end-to-end timing across sensor, task, bus and actuator boundaries.

Validation Package Checklist

• WCET evidence for every released task, callback, ISR and non-preemptive section.
• Scheduler configuration, priority table, tick policy and timing source documented.
• Bus captures for worst allowed arbitration, payload, retry and diagnostic traffic.
• Queue high-water marks and overflow counters from stress tests.
• Release-jitter, interrupt-latency and preemption-overhead measurements on target hardware.
• End-to-end latency traces tied to requirements and acceptance criteria.