Staff-Level Embedded Systems Developer Interview Preparation Guide (FAANG Standards)

Problem formulation (continuous frequencies)

Minimize total energy by choosing fi for each task τi (period Pi, base cycles Ci) and a feasible schedule:

Objective:

E_total = sum_i E_i(f_i),   where   E_i(f_i) = alpha * C_i * f_i^{k-1}

(assuming power P(f)=alpha f^k and WCET_i(f)=C_i / f_i)

Schedulability constraints (single CPU, preemptive EDF):

forall t: sum_i WCET_i(f_i)/P_i = sum_i (C_i / f_i) / P_i <= 1

Bounds:

f_min <= f_i <= f_max   (and f_i continuous or from discrete set F)

Why these expressions

• WCET inversely proportional to f: WCET = C_i / f_i.
• Energy per task = power * execution time = alpha f^k * (C_i / f_i) = alpha C_i f^{k-1}.

Complexity

• Continuous version (fi continuous): objective is separable; since 1/f is convex on f>0 and E_i(f) = alpha C_i f^{k-1} is convex for k>=2 (common CMOS k≈2–3), the problem is a convex program (minimize convex objective over convex feasible set) and solvable efficiently with standard convex solvers.
• Discrete-frequency hardware or additional integer scheduling decisions (task-to-core partitioning, mode switching overheads) make it a mixed-integer nonconvex problem → NP-hard in general.

Practical heuristics for embedded systems

1. Continuous-relaxation + rounding
   • Solve convex relaxation for fi, then round each f_i up to nearest supported discrete frequency to preserve schedulability.
2. Utilization-based scaling (simple, cheap)
   • Compute required scaled utilization U_req = sum_i C_i / P_i.
   • Set a single global f = max(f_min, min(f_max, U_req * f_nominal)) or f proportional to U_req; good for very constrained RTOS.
3. Per-task DVFS with greedy allocation
   • Start at f_min for all; increase frequencies for tasks with largest marginal energy savings per schedulability gain until constraint met.
4. EDF slack reclamation (dynamic)
   • Run at conservative baseline frequency; reclaim slack at runtime per job deadlines, use greedy per-job speed-up.
5. Precomputed table / mode selection
   • Offline compute a small set of frequency assignments (modes) and switch modes based on workload; stores low memory footprints.

Implementation tips for embedded developers

• Prefer continuous solve offline (or lightweight convex solver) then quantize for device frequencies.
• Account for transition overheads and fast switching limits; include switching energy/time as constraints if relevant.
• Test with worst-case phasing and jitter; validate schedulability with measurement-based WCET margins.
• Use EDF with runtime slack reclaiming for best energy vs. complexity trade-off on single-core devices.

This gives a provably optimal continuous baseline and several practical approximations suitable for resource-constrained firmware.

Clarify requirements & assumptions

• 4 sensors @ 10 kHz each → 40,000 samples/s total.
• Sample size: 16-bit (2 bytes). Latency target: 5 ms from sample to CPU processing.
• MCU has DMA controller with at least 4 channels, supports circular mode and half/full buffer interrupts.

Strategy comparison (short)

• Polling: Simple but must sample 40k/s in software → tight timing, wastes CPU, jitter-prone.
• Interrupt-driven (per-sample IRQ): Low latency per sample but 40k IRQs/s → high interrupt overhead, poor scalability.
• DMA-based: Offloads transfers to hardware, CPU interrupted only on buffer events → very low CPU cost, deterministic bus usage.

Proposed hybrid architecture

• Each sensor wired to its own ADC/DMA channel. Configure DMA in circular, ping-pong (double) buffer per sensor.
• Timer triggers ADC conversions at 10 kHz for each sensor (or synchronized multiplexed ADC with DMA scatter/gather if single ADC).
• DMA generates interrupt on half/full buffer (choose half to reduce worst-case latency).
• CPU processes buffer in ISR or schedules RT task; processing must complete within buffer-interval (<= 5 ms).

Calculations

• Samples per sensor per 5 ms = 10,000 sps * 0.005 s = 50 samples.
• Choose 64-sample buffers (power of two). Bytes per buffer per sensor = 64 * 2 = 128 B.
• Double-buffer per sensor = 256 B. Total RAM for 4 sensors = 4 * 256 = 1024 B (1 KiB).
• DMA channels required: ideally 4 channels (one per sensor) for independent circular transfers. If single ADC multiplexed, 1 DMA channel + scatter/gather or memory layout to separate sensors.

Interrupt rate & CPU cycles

• Per-sample interrupts approach:
  • IRQs/s = 40,000.
  • Assume ISR overhead ~1,000 CPU cycles (enter, read sample, store, exit) → 40,000 * 1,000 = 40,000,000 cycles/s.
  • On a 120 MHz MCU this is ~33% CPU just for IRQ overhead (no processing).
• DMA half-buffer interrupts with 64-sample half => interrupts per sensor = 10,000 / 32 = 312.5 -> choose 312 or 313.
  • Total IRQs/s ≈ 4 * 312.5 = 1,250 interrupts/s.
  • ISR overhead for buffer-ready: assume 1,000 cycles (or less because copying small block/process scheduling) → 1,250 * 1,000 = 1,250,000 cycles/s (~1.04% of 120 MHz).
  • If ISR is slimmer (500 cycles) => ~625k cycles/s.
• DMA controller bus cycles for transfers are off-CPU; negligible CPU cycles except setup: initial DMA config maybe few thousand cycles at boot and occasional reconfig.

Trade-offs & notes

• Per-sample IRQ gives minimal per-sample latency but unsustainable CPU load.
• DMA + half/full buffer meets 5 ms latency (50-sample window) — using half-buffer gives ~1.6 ms worst-case latency (half of 64 samples).
• If lower latency needed (<1 ms), reduce buffer to 16–32 samples (increase IRQ rate) and re-evaluate CPU budget.
• If MCU has fewer DMA channels, use one channel with scatter-gather or time-multiplexed ADC and ensure DMA can tag data to sensor buffers.

Recommendation
Use DMA circular with per-sensor double buffers (64 samples) and half-buffer interrupts. Allocate 1 KiB of RAM for buffers and 4 DMA channels. This keeps CPU load low (~1% of 120 MHz) while meeting 5 ms latency and providing predictable timing for processing.

Setup and assumptions

Priorities follow rate (shorter period, higher priority), so H is highest, M is middle and L is lowest. All deadlines equal the period. The mutex (a lock that lets one task at a time into a critical section) is used by M, which holds it for at most 1 ms, and by L, which holds it for at most 3 ms. H never takes it. Context-switch cost and interrupt load are taken as zero.

Priority inheritance means that when a high-priority task waits for a lock, the task holding that lock temporarily runs at the waiter's priority, so medium-priority tasks cannot preempt it while it finishes. The blocking time B_i of task i is the longest it can be made to wait for lower-priority tasks. Each task's worst-case response time is then given by the response-time recurrence R = C + B + sum over higher-priority tasks j of ceil(R / Tj) x Cj, iterated from R = C + B until it stops changing (C is the task's execution time, Tj and Cj the period and execution time of a higher-priority task).

Blocking for each task

• H: B = 0 ms. H never takes the mutex, so it never waits for a lock. The only way a lower task could delay it is by inheriting a priority above H's, and the highest priority L can inherit is M's, which is below H. H preempts whatever is running.
• M: B = 3 ms. If L has just locked the mutex when M is released, M must wait for L to leave its critical section, at most 3 ms. Inheritance lets L run at M's priority for that time, so H can still preempt it but nothing else in between can. M's own 1 ms critical section is part of its 4 ms of execution, not blocking.
• L: B = 0 ms. Nothing has lower priority than L.

M is blocked only once per release. L can hold the mutex only while it runs, and while M or H is ready L cannot run, so after L releases the lock it cannot take it again before M has finished.

Worst-case response times

Each iteration is evaluated by the script below, which ships the arithmetic so the table is not asserted. Run in a python:3.12-slim container with python response_time.py:

from math import ceil

# (name, C, T) in ms, listed highest priority first (rate-monotonic, D = T)
tasks = [("H", 2, 10), ("M", 4, 20), ("L", 6, 50)]
# longest time each task holds the shared mutex (0 = never takes it)
cs = {"H": 0, "M": 1, "L": 3}

def blocking(i):
    # Priority inheritance, one mutex: task i can be blocked once, by the
    # longest critical section of a lower-priority task, if some task of
    # priority >= i (itself or a higher one) also uses the mutex.
    users_at_or_above = any(cs[t[0]] > 0 for t in tasks[: i + 1])
    if not users_at_or_above:
        return 0
    lower = [cs[t[0]] for t in tasks[i + 1 :]]
    return max(lower, default=0)

def response_time(i):
    C, T = tasks[i][1], tasks[i][2]
    B = blocking(i)
    R = C + B
    while True:
        R_next = C + B + sum(ceil(R / Tj) * Cj for _, Cj, Tj in tasks[:i])
        if R_next == R:
            return B, R
        if R_next > T:
            return B, R_next
        R = R_next

print("U =", sum(C / T for _, C, T in tasks))
for i, (n, C, T) in enumerate(tasks):
    B, R = response_time(i)
    print(f"{n}: C={C} T={T} B={B} R={R} deadline_met={R <= T}")

# If H also takes the mutex for 1 ms
cs["H"] = 1
print("variant: H also locks the mutex for 1 ms")
for i, (n, C, T) in enumerate(tasks):
    B, R = response_time(i)
    print(f"{n}: B={B} R={R} deadline_met={R <= T}")

U = 0.52
H: C=2 T=10 B=0 R=2 deadline_met=True
M: C=4 T=20 B=3 R=9 deadline_met=True
L: C=6 T=50 B=0 R=14 deadline_met=True
variant: H also locks the mutex for 1 ms
H: B=3 R=5 deadline_met=True
M: B=3 R=9 deadline_met=True
L: B=0 R=14 deadline_met=True

Worked by hand, for check:

• H: R = 2 ms. Deadline 10 ms. Met.
• M: R0 = 4 + 3 = 7; R1 = 4 + 3 + ceil(7/10) x 2 = 9; R2 = 4 + 3 + ceil(9/10) x 2 = 9. So R = 9 ms. Deadline 20 ms. Met.
• L: R0 = 6; R1 = 6 + ceil(6/10) x 2 + ceil(6/20) x 4 = 12; R2 = 6 + ceil(12/10) x 2 + ceil(12/20) x 4 = 14; R3 = 6 + ceil(14/10) x 2 + ceil(14/20) x 4 = 14. So R = 14 ms. Deadline 50 ms. Met.

Every deadline is met, and with total utilisation 0.2 + 0.2 + 0.12 = 0.52 there is wide margin: the tightest ratio is M at 9 of 20 ms.

If H also used the mutex

The same program prints a second block for the case where H also locks the mutex for 1 ms. Then H can arrive while L holds it, so B_H = 3 ms and R_H = 2 + 3 = 5 ms, still inside 10 ms. B_M stays 3 ms because H is above M and so is never a lower-priority blocker for it, and R_M is still 9 ms (H's critical section is part of H's own 2 ms). L is unchanged at 14 ms. The lesson is that blocking is charged to the task that waits, and only lower-priority holders of locks that the waiting task, or a task above it, can use count.

Several locks

With one lock and non-nested critical sections (no task takes a second lock while already holding one), as here, a task is blocked at most once. With several locks, priority inheritance can chain blocking: the task waits for one holder, and after that holder finishes another lower-priority task has meanwhile taken a different lock the waiter needs, so it waits again. Sha, Rajkumar and Lehoczky (1990) show a job can be blocked for at most min(n, m) critical sections, where n is the number of lower-priority tasks that could block it and m the number of locks that could be used to block it. For example, a task with three lower-priority tasks and two locks between them can be blocked for at most min(3, 2) = 2 critical sections, one per lock; with the single lock here, min(1, 1) = 1 for M (its only lower-priority task is L). The priority ceiling protocol (each lock gets a ceiling, the highest priority of any task that uses it, and a task may take a lock only if its priority is above the ceilings of all locks other tasks currently hold) cuts the bound to a single critical section, at the price of sometimes holding a task back even when the lock it wants is free.

Direct answer

Fail-fast stops the operation immediately and surfaces the error the moment something is wrong, trading availability for correctness and a clear signal; graceful degradation keeps the system partially functional by falling back to reduced capability, trading some correctness or completeness for continued availability. The right choice depends on whether a wrong or incomplete answer is worse than no answer at all for this specific system.

Structured elaboration

Fail-fast: when correctness matters more than availability. An internal data pipeline computing financial reconciliation numbers should fail fast and loudly the moment its inputs look wrong, because a wrong number that looks plausible and gets used in a report is a much worse outcome than the pipeline simply not running today. Fail-fast systems are also easier to operate: a hard failure with a clear error is diagnosable immediately, whereas a system that silently degrades can mask a real problem for a long time before anyone notices the quality of its output has quietly dropped.

Graceful degradation: when partial availability beats a hard stop. A customer-facing product page that depends on a recommendation service should degrade to a generic, non-personalized set of recommendations if that service is slow or down, rather than showing the customer an error page, because a slightly-worse-but-functional page is a much better outcome for both the customer and the business than a hard failure on a page that otherwise works fine.

Instrumentation differs by approach. A fail-fast system needs strong alerting on the failure itself, since the failure IS the signal: an error rate spike, a specific exception type, or a circuit breaker opening. A gracefully-degrading system needs the opposite kind of visibility: a metric or log line specifically for "we are currently in degraded mode", because the degraded path, by design, does not look like a failure to a simple error-rate dashboard, and a team that isn't specifically tracking degraded-mode usage can be running in a permanently degraded state for months without noticing.

Communicating degraded functionality. For a user-facing system, this usually means a visible but non-alarming UI signal ("Showing popular items while personalized recommendations are unavailable") rather than silence, since silent degradation erodes trust once a user notices the quality difference without being told why. For a downstream service-to-service dependency, this means an explicit field or header in the response indicating degraded mode, so the calling service can make its own informed choice about whether to also degrade or to fail.

Worked example

An internal pipeline vs. a downstream API dependency, side by side: the internal pipeline computing quarterly revenue numbers for a financial report should fail fast and halt if a required upstream table is empty or a row count sanity check fails, alerting the on-call data engineer immediately, because publishing a subtly wrong number in a financial report is far worse than the report being late. The customer-facing recommendation widget on the same company's storefront, dependent on a separate ML service, should instead catch a timeout from that service and immediately serve a cached "most popular this week" list, log a degraded_mode=true metric tagged with the reason, and continue serving the page, because an incomplete page for one widget is a minor UX cost, not a correctness failure the business needs to halt over.

Trade-offs and pitfalls

The most common mistake is applying the wrong default to a whole system uniformly: treating every dependency as fail-fast produces a fragile product where one non-critical service outage takes down an entire page, while treating every dependency as gracefully-degradable risks quietly serving wrong financial or safety-relevant data with no alert ever firing. The decision should be made dependency by dependency, based on whether being wrong is worse than being unavailable for that specific piece of functionality, not applied as a single system-wide policy.

Direct answer
When a mentee gets defensive and stops acting on feedback, the fastest way to make it worse is to double down with more direct feedback. Slow down, diagnose why the message isn't landing (the content, the delivery, or something the mentee brings into the room), then rebuild the conversation as a two-way one instead of a one-way correction. If the pattern doesn't shift after a genuine attempt at that, it needs to be named and escalated, not quietly tolerated.

Diagnose before you re-deliver

• Separate "defensive because of how I said it" from "defensive because of what's underneath it." Workload, unclear expectations, a confidence hit, or feedback that reads as a character judgment rather than a specific behavior all produce the same surface symptom (pushback, non-action) for different reasons.
• Ask, don't assume: open with a genuinely curious question rather than a repeat of the critique. "Walk me through how that landed for you" gets you information; "you need to stop being defensive" gets you more defensiveness.

Use motivational interviewing instead of more direct pressure

• Motivational interviewing is built for exactly this: someone who may intellectually agree but is resisting behaviorally. Instead of arguing for the change, reflect their own stated goals back to them and let them articulate the gap ("You mentioned you want to lead the next project. How does this pattern affect that?"). People act on reasons they generate themselves far more than reasons handed to them.
• Keep the ratio of affirmation to correction visible. If every interaction is corrective, the mentee starts hearing footsteps before you speak, which is what produces reflexive defensiveness.

Rebuild the mechanism, not just the next conversation

• Shrink the ask: instead of a broad critique, propose one small, concrete, reversible change and a short check-in window.
• Make feedback bidirectional: ask what kind of feedback has landed well for them before, and adjust format (written vs. verbal, immediate vs. batched) accordingly.

Know when coaching has run its course

• If, after two or three honest attempts using the above, the pattern is unchanged (commitments still not acted on, same defensiveness), that's a signal the issue may be outside what coaching alone fixes: a skill gap being misread as attitude, a values or fit mismatch, or a factor you're not positioned to see.
• At that point, loop in the mentee's manager, or HR if the dynamic has become adversarial, rather than continuing to privately absorb it. Frame it factually: what you tried, what changed, what didn't. This isn't giving up on the mentee; it's recognizing some situations need authority or context you don't have.

Worked example
A mentee kept missing agreed follow-ups on code review comments and would get visibly short in Slack whenever it came up. The instinct was to restate the same feedback more firmly. Instead, the better move: open the next 1:1 with "I want to understand how the review feedback has been landing for you, not go through it again," and listen first. It turned out the mentee had inherited a legacy module nobody had explained well, and every review comment felt like it was pointing out someone else's mess. The fix wasn't more feedback, it was pairing on the module once and shrinking the ask to one file at a time. If that hadn't worked, the next honest step would have been raising the pattern with the mentee's manager, not repeating the same conversation a fourth time.

Trade-offs and pitfalls

• The junior mistake is treating defensiveness as a discipline problem and pushing harder; that reliably produces more resistance, not less.
• Over-correcting the other way (going silent on real issues to avoid triggering defensiveness) just delays the same conversation and lets performance drift.
• Escalating too early, before you've tried adjusting your own approach, reads as offloading a coaching problem; escalating too late lets a stalled dynamic damage trust or delivery. The senior move is trying a genuine adaptation first, timeboxing it, and being honest about whether it moved anything.

Direct answer

Priority inheritance fixes priority inversion: a high-priority task H blocks on a mutex held by a low-priority task L, and a medium-priority task M that does not need the mutex keeps pre-empting L, so H effectively waits on M. The fix is that while H is blocked on L's mutex, L runs at H's priority (L inherits it). When L releases the mutex, L drops back to the priority its remaining locks justify, and the mutex goes to the highest-priority waiter. The mutex must therefore remember its owner and its waiters, and each task must remember its base priority, its current effective priority, the mutex it waits on, and the mutexes it holds.

State the design keeps

Convention here: a larger number means a higher priority.

Acquire and release

Acquire (pi_lock). If the mutex is free, take it. Otherwise record blocked_on, add the caller to the waiters, then propagate: set the owner's eff_prio to the caller's if that is higher; if that owner is itself blocked on another mutex, move to that mutex's owner and repeat. Stop when the next owner already has an equal or higher priority, when the owner is not blocked, or when you come back to the caller (a cycle, which is a deadlock: undo the wait and report it).

Release (pi_unlock). Remove the mutex from the owner's held list. Give it to the highest-priority waiter, who becomes the owner and stops being blocked. Then recompute the old owner: max(base_prio, highest waiter on each mutex it still holds). This is the nested-locks rule: a task holding two mutexes must not fall to its base priority when it releases one if a high-priority task still waits on the other.

Bounding the adjustments.

• Each task waits for at most one mutex, so the chain is a simple path and the walk visits each task at most once. Its length is bounded by the number of tasks, and a cycle is detected instead of looped on. The code also has a hard hop limit as a second guard.
• A boost is a copy of an existing priority, never an increase, so no task can exceed the highest priority present.
• Time spent blocked is bounded by the critical sections along the chain, so keep critical sections short and do not call blocking functions while holding a lock.
• Linux's real-time mutex does the same kind of chain walk, and the kernel's rt-mutex design document says that, to prevent denial-of-service attacks, it holds at most two different locks at a time while it walks the chain: it lets go of the earlier locks as it moves along, rather than holding every lock in the chain at once.

Worked example, compiled and run on the host model

This is a model of the kernel-side bookkeeping, with no real scheduler and no real blocking, so every state change can be asserted. It was compiled and run on a Linux container (not on an RTOS or microcontroller): gcc -std=c11 -O1 -Wall -Wextra -Wno-missing-field-initializers -fsanitize=address,undefined pimutex.c -o pi && ./pi. The model has no waiter timeouts and no priority-change calls; a real kernel must re-run the same recompute along the chain on either.

#include <assert.h>
#include <stdio.h>

/* Larger number = higher priority. This models the kernel-side bookkeeping only
   (no real scheduler, no real blocking), so every state change can be checked. */
#define MAX_TASKS 8
#define MAX_HELD 4
#define MAX_WAIT 4

typedef struct mutex mutex_t;
typedef struct task {
    const char *name;
    int base_prio;            /* never changed by inheritance */
    int eff_prio;             /* what the scheduler uses */
    mutex_t *blocked_on;      /* at most one: a task waits on one mutex at a time */
    mutex_t *held[MAX_HELD];
    int nheld;
} task_t;

struct mutex {
    const char *name;
    task_t *owner;
    task_t *waiters[MAX_WAIT];
    int nwait;
};

static int highest_waiter_prio(const mutex_t *m) {
    int p = -1;
    for (int i = 0; i < m->nwait; i++) if (m->waiters[i]->eff_prio > p) p = m->waiters[i]->eff_prio;
    return p;
}

/* eff = max(base, highest-priority waiter on ANY mutex still held) */
static void recompute(task_t *t) {
    int p = t->base_prio;
    for (int i = 0; i < t->nheld; i++) {
        int w = highest_waiter_prio(t->held[i]);
        if (w > p) p = w;
    }
    t->eff_prio = p;
}

/* Walk owner -> the mutex the owner waits on -> its owner ... raising priorities.
   The walk is bounded: it visits each task at most once and stops on a cycle (deadlock). */
static int propagate(task_t *from, int *depth) {
    mutex_t *m = from->blocked_on;
    int hops = 0;
    while (m && m->owner) {
        task_t *o = m->owner;
        if (o == from) return -1;                 /* cycle: report deadlock, do not loop */
        hops++;
        if (hops > MAX_TASKS) return -1;          /* defensive hard bound */
        if (o->eff_prio >= from->eff_prio) break; /* nothing more to raise down the chain */
        o->eff_prio = from->eff_prio;
        m = o->blocked_on;
    }
    *depth = hops;
    return 0;
}

/* returns 1 if acquired, 0 if the caller must block, -1 if blocking would deadlock */
static int pi_lock(task_t *t, mutex_t *m) {
    if (!m->owner) { m->owner = t; t->held[t->nheld++] = m; return 1; }
    t->blocked_on = m;
    m->waiters[m->nwait++] = t;
    int depth = 0;
    if (propagate(t, &depth) < 0) {               /* undo and report */
        m->nwait--; t->blocked_on = NULL;
        /* the failed walk already raised owners along the chain: recompute them, nearest first */
        int guard = 0;
        for (mutex_t *w = m; w && w->owner && guard < MAX_TASKS; w = w->owner->blocked_on, guard++)
            recompute(w->owner);
        return -1;
    }
    return 0;
}

/* returns the new owner (highest-priority waiter) or NULL */
static task_t *pi_unlock(task_t *t, mutex_t *m) {
    assert(m->owner == t);
    int k = 0;                                    /* drop m from t's held list */
    for (int i = 0; i < t->nheld; i++) if (t->held[i] != m) t->held[k++] = t->held[i];
    t->nheld = k;
    task_t *next = NULL; int bi = -1;
    for (int i = 0; i < m->nwait; i++)
        if (!next || m->waiters[i]->eff_prio > next->eff_prio) { next = m->waiters[i]; bi = i; }
    if (next) {
        m->waiters[bi] = m->waiters[--m->nwait];
        next->blocked_on = NULL;
        m->owner = next; next->held[next->nheld++] = m;
    } else m->owner = NULL;
    recompute(t);                                 /* deboost: only to what the OTHER held mutexes still justify */
    if (next) recompute(next);
    return next;
}

#define SHOW(t) printf("  %-4s base=%d eff=%d\n", (t)->name, (t)->base_prio, (t)->eff_prio)

int main(void) {
    task_t H = {"H", 30, 30}, M = {"M", 20, 20}, L = {"L", 10, 10};
    mutex_t A = {"A"}, B = {"B"};

    puts("1) basic inversion: L holds A, H blocks on A");
    assert(pi_lock(&L, &A) == 1);
    assert(pi_lock(&H, &A) == 0);
    SHOW(&L); assert(L.eff_prio == 30);          /* M (20) can no longer preempt L */
    assert(L.eff_prio > M.base_prio);

    puts("2) release restores base priority and hands A to H");
    task_t *n = pi_unlock(&L, &A);
    assert(n == &H); SHOW(&L); SHOW(&H);
    assert(L.eff_prio == 10);
    pi_unlock(&H, &A);

    puts("3) nested chain: L holds B; M holds A and waits on B; H waits on A");
    assert(pi_lock(&L, &B) == 1);
    assert(pi_lock(&M, &A) == 1);
    assert(pi_lock(&M, &B) == 0);                 /* M blocked on B, owner L -> L = 20 */
    assert(L.eff_prio == 20);
    assert(pi_lock(&H, &A) == 0);                 /* H blocked on A, owner M -> M = 30 -> L = 30 */
    SHOW(&M); SHOW(&L);
    assert(M.eff_prio == 30 && L.eff_prio == 30);

    puts("4) L releases B: L drops to base, M gets B and stays at 30 because H still waits on A");
    n = pi_unlock(&L, &B);
    assert(n == &M); SHOW(&L); SHOW(&M);
    assert(L.eff_prio == 10 && M.eff_prio == 30);

    puts("5) multiple held mutexes: deboost only as far as remaining waiters allow");
    task_t P = {"P", 5, 5}, Q = {"Q", 15, 15}, R = {"R", 28, 28};
    mutex_t C = {"C"}, D = {"D"};
    assert(pi_lock(&P, &C) == 1 && pi_lock(&P, &D) == 1);
    assert(pi_lock(&Q, &C) == 0);  assert(P.eff_prio == 15);
    assert(pi_lock(&R, &D) == 0);  assert(P.eff_prio == 28);
    pi_unlock(&P, &D);             SHOW(&P); assert(P.eff_prio == 15);   /* Q still waits on C */
    pi_unlock(&P, &C);             SHOW(&P); assert(P.eff_prio == 5);

    puts("6) a lock cycle is detected, not looped on");
    task_t U = {"U", 12, 12}, V = {"V", 14, 14};
    mutex_t E = {"E"}, F = {"F"};
    assert(pi_lock(&U, &E) == 1 && pi_lock(&V, &F) == 1);
    assert(pi_lock(&U, &F) == 0);
    int r = pi_lock(&V, &E);
    printf("  V tries E -> %d (-1 = would deadlock)\n", r);
    assert(r == -1);
    SHOW(&U); SHOW(&V);                           /* the failed attempt must leave no boost behind */
    assert(U.eff_prio == 12 && V.eff_prio == 14);
    puts("all checks passed");
    return 0;
}

Output:

1) basic inversion: L holds A, H blocks on A
  L    base=10 eff=30
2) release restores base priority and hands A to H
  L    base=10 eff=10
  H    base=30 eff=30
3) nested chain: L holds B; M holds A and waits on B; H waits on A
  M    base=20 eff=30
  L    base=10 eff=30
4) L releases B: L drops to base, M gets B and stays at 30 because H still waits on A
  L    base=10 eff=10
  M    base=20 eff=30
5) multiple held mutexes: deboost only as far as remaining waiters allow
  P    base=5 eff=15
  P    base=5 eff=5
6) a lock cycle is detected, not looped on
  V tries E -> -1 (-1 = would deadlock)
  U    base=12 eff=12
  V    base=14 eff=14
all checks passed

Every assert passed. How propagate works, line by line: it starts at the task that just blocked (from) and looks at the mutex it waits on, m. The loop body takes that mutex's owner o; if o is from the chain has come back to the start, which is the cycle, so it returns -1; if o already has equal or higher priority nothing more needs raising, so it breaks; otherwise it copies from's priority into o and moves on to the mutex o itself waits on. hops counts steps and is capped at MAX_TASKS as a second guard. Case 6 in words: U holds E and V holds F. U asks for F and blocks (V already has priority 14 so nothing is raised). V then asks for E: the walk goes to E's owner U, raises U to 14, then to the mutex U waits on, F, whose owner is V, the caller, so it reports the cycle and -1. The failed attempt had raised U, so pi_lock recomputes the owners along the chain before returning, and the printed U and V lines show that no boost was left behind (U back at 12). Case 3 is the nested chain (H waits for M who waits for L, so L reaches 30). Case 4 shows M keeps 30 after receiving B because H still waits on A. Case 5 shows the deboost stops at 15, not at the base 5, while Q still waits on C.

Trade-offs and pitfalls

• Inheritance does not prevent deadlock. The cycle case simply detects it. Preventing it needs a lock ordering rule. A priority ceiling protocol (every mutex has a ceiling equal to its highest-priority user) is the other classic fix: if a mutex is used by tasks at priorities 10 and 30, its ceiling is 30, and any task that locks it runs at 30 for the whole critical section, so no medium-priority task can preempt it, and no waiting is needed to trigger the boost.
• Never lock it from an interrupt handler. An ISR (interrupt service routine, the code the CPU runs when a hardware event fires) is not a schedulable task with a priority to inherit, and it cannot block.
• Cost. Chain walks happen in the slow path (when blocked), and the fast path is one atomic operation. The price is bookkeeping and a longer slow path.
• Pitfall. Forgetting to recompute from the remaining held mutexes on release leaves a task boosted forever, or drops it too early. Case 5 is the test that catches it.

Approach summary
Use a byte-array canonical on-wire format and implement portable bit-level pack/unpack routines rather than C compiler bitfields. Reserve a version and flags field, include a CRC8 for error detection, and allow optional extension blocks. Handle endianness by reading/writing bits in a defined MSB-first or LSB-first order.

Packet layout (12 bytes = 96 bits) — example

• byte 0: [ version:3 | flags:5 ]
• bits 8..31: fieldA:24
• bits 32..47: fieldB:16
• bits 48..71: fieldC:24
• bits 72..87: fieldD:16
• bits 88..95: checksum:8 (CRC-8 of bytes 0..10)

This is MSB-first within each byte (network order).

Why not compiler bitfields

• Compiler-dependent packing/endianness/ordering. Portable code should manipulate bytes and bits explicitly.

Parsing/writing pseudocode (C-style)

// read bitfield helper (MSB-first within bytes)
uint64_t read_bits(const uint8_t *buf, int bit_offset, int bit_len) {
    uint64_t v = 0;
    for (int i = 0; i < bit_len; ++i) {
        int b = bit_offset + i;
        uint8_t byte = buf[b / 8];
        int bit_in_byte = 7 - (b % 8); // MSB-first
        v = (v << 1) | ((byte >> bit_in_byte) & 1);
    }
    return v;
}

void write_bits(uint8_t *buf, int bit_offset, int bit_len, uint64_t value) {
    for (int i = bit_len - 1; i >= 0; --i) {
        int b = bit_offset + (bit_len - 1 - i);
        uint8_t *byte = &buf[b / 8];
        int bit_in_byte = 7 - (b % 8);
        uint8_t bit = (value >> i) & 1;
        *byte = (*byte & ~(1 << bit_in_byte)) | (bit << bit_in_byte);
    }
}

High-level parser

• Verify packet length == 12
• Compute CRC-8 over bytes 0..10, compare to checksum at byte 11
• Extract version = read_bits(buf, 0, 3)
• Switch on version; for unknown higher version return controlled error (or attempt best-effort)
• Extract fields via read_bits()
• Validate ranges and flags

Versioning & extensibility

• 3-bit version allows evolving format. New fields appended into reserved flag space or new extension region flagged by flags bits. Receiver ignores unknown optional extensions.

Error detection

• Use CRC-8 (polynomial e.g., 0x07) in last byte. Also include sanity checks (range, reserved bits zero).

Testing strategy (big/little-endian)

• Unit tests use reference vectors: construct packet via write_bits on a known-endian host, compare against known good hex string.
• Cross-build and run tests on both little-endian and big-endian boards (or QEMU for big-endian sim).
• Property tests: randomize fields, pack then unpack and assert equality; also flip single bits and assert CRC catches errors.
• Fuzz tests: malformed lengths, corrupted checksum, version mismatch.
• CI: include tests running in a deterministic emulator for both endiannesses and check reference CRC and fields.

Trade-offs

• Bit-wise helpers cost a few cycles but are small and portable. If performance critical, offer optimized versions for common platforms using aligned reads with explicit byte-order conversions.

Brief approach
On a 256KB-RAM device with large firmware in external flash, verify image integrity by choosing a scheme that trades RAM and CPU for resume/partial-check capabilities. Compare three options below.

Incremental (single-pass) hashing

• Memory: minimal (buffer ~1–4KB for read chunk + hash state ~32 bytes for SHA-256).
• CPU: one SHA-256 stream over whole image — optimal total CPU.
• Resume/partial: poor — to resume you must store intermediate hash state periodically or rehash from start.
• Use when RAM is tight and full-verify on boot is acceptable.

Per-chunk hashes

• Memory: store one chunk and its precomputed hash table in flash; RAM only for one chunk buffer + state.
• CPU: verify only needed chunks; fewer CPU cycles if partial checks common.
• Resume/partial: excellent — verify chunks independently; easy OTA delta verification.
• Storage: requires extra flash to store per-chunk hashes (e.g., 32 bytes per chunk).

Merkle tree

• Memory: compute/verify using O(1) RAM (buffer + path stack length ~log2(num_chunks) hashes); store tree or top root in secure area.
• CPU: higher (multiple hash ops to recompute internal nodes) but supports compact proofs.
• Resume/partial: excellent — can authenticate any chunk with small proof; ideal for secure boot and partial downloads.
• Trade-off: complexity and more flash storage for tree nodes or ability to fetch proofs.

Recommendation
If minimal RAM usage and fastest single verify is priority → incremental hashing. If frequent partial/OTA verifies → per-chunk hashes. If strong authenticated partial access with small proofs and secure root storage → Merkle tree. For 256KB RAM with large firmware, Merkle or per-chunk are preferred for OTA/resume; incremental for one-shot boot-time verifies.

Difference (brief)

• MMIO: peripheral registers mapped into the CPU physical address space; drivers access them via normal loads/stores to specific addresses.
• PMIO (a.k.a. port I/O / PIO): separate I/O address space accessed via special CPU instructions (e.g., in/out on x86) or special bus cycles.

How drivers access

• MMIO: map physical address (or use provided virtual mapping) and perform volatile read/write in C (e.g., *(volatile uint32_t *)addr). On OSes, use ioremap()/ioread32()/iowrite32().
• PMIO: use inb/outb or equivalent functions wrapping asm I/O instructions.

Embedded pros/cons

• MMIO pros: simpler programming model, unified address space, easier DMA and MMU integration. Cons: must prevent caching and reorderings.
• PMIO pros: explicit separation reduces accidental access; cons: limited port space, fewer platforms support it.

Caching, memory barriers, compiler optimizations

• Mark accesses volatile and use platform-provided I/O accessors to avoid compiler reordering/optimization.
• Use explicit memory barriers (e.g., wmb(), rmb(), smp_mb()) to enforce ordering between device and CPU.
• Caching: map device regions as non-cacheable; cached MMIO can corrupt device state.

MMU interaction and marking device memory

• With an MMU, create page table entries for device regions with device memory attributes (non-cacheable, strongly-ordered or device-type memory). In Linux: ioremap() / ioremap_wc()/ioremap_nocache() and set PAT/PTE flags. That ensures cache behavior and ordering rules are enforced by hardware.

Why volatile alone is insufficient

• volatile prevents the compiler from optimizing away or reordering the source-level stores, but it does not prevent the CPU or the bus from reordering or buffering memory writes.
• Modern ARM CPUs use store buffers and posted (write-combining) transactions; a later store (CONTROL.START) can be accepted/observed by the device before an earlier store (CONFIG) has actually reached the peripheral unless the CPU/bus is told to drain/order writes.
• Devices and interconnects may also reorder or buffer transfers, so software-visible ordering needs explicit barriers.

Minimal guaranteed sequence (ARM embedded)

1. Write CONFIG (volatile MMIO store).
2. Ensure the write is complete and visible to the device: Data Synchronization Barrier (DSB SY) or an appropriate write-complete barrier.
3. Write CONTROL.START (volatile MMIO store).

Optionally follow the START write with another DSB if you must wait for the start write to be fully posted before proceeding.

C example (inline ARM barrier)

// CONFIG and CONTROL are volatile pointers to MMIO registers
*CONFIG = config_value;                // volatile store to peripheral
asm volatile("dsb sy" ::: "memory");   // ensure CONFIG write completed
*CONTROL = CONTROL_START;              // start operation

Notes

• DMB orders memory accesses but may not wait for posted writes to complete; DSB SY is the stronger choice to guarantee completion of prior transactions to device-before issuing the START.
• In kernel drivers use the architecture-provided wmb()/dsb equivalents per platform; userspace drivers may need ioctl/syscall helpers that perform barriers in kernel.