Entry-Level Embedded Developer Interview Preparation Guide - FAANG Standards

Direct answer

A proposal was about to go out to a client built on an assumption from a regulatory area outside my usual scope, and nobody had actually verified it held. Since no one else had the bandwidth and it wasn't formally assigned to me, I picked it up myself, worked it in around existing commitments over about a week and a half, and it changed the outcome directly: the assumption turned out to be wrong.

Structured elaboration

Why the gap mattered to the business, not just to me personally: committing resources to a flawed assumption would have cost far more to unwind later than the time it took to check it up front, so this wasn't learning for its own sake, it was risk that had a real dollar and reputation cost attached.

How I fit it around existing delivery: a few focused hours most days, worked around my actual deliverables rather than replacing them, which is closer to the honest reality than pretending I found a clear open runway.

What I chose to learn from and why: the primary source material for the regulation itself, plus one conversation with someone closer to that domain to sanity-check my reading, rather than a general course, because the timeline didn't allow for breadth and precision mattered more here than depth of background.

The first real application and how I checked it before it counted: I used what I'd learned to redline the specific assumption in the proposal, then had the person closer to that domain review that specific change before it went out, since being self-taught on something this consequential doesn't make me the final authority on it.

Worked example

The flawed assumption got caught and corrected before the proposal went out, which avoided a costly rework and a credibility problem with the client later. What I'd do differently next time: flag the gap the moment I noticed it, rather than only surfacing it once the proposal was nearly final, which gave less room to fix it calmly. It's also worth naming the distinction directly: this is a stronger example precisely because nobody assigned it to me, I noticed the gap and closed it on my own, which is a different and harder signal than closing a gap someone else already identified for me.

Trade-offs and pitfalls

A common wrong turn in this kind of answer is treating "learning outside my expertise" as a story about personal growth in the abstract, disconnected from why the business actually needed it. The other is overstating the depth reached: the honest version isn't "I became an expert in it," it's "I got enough to catch the specific risk and knew to verify the fix with someone deeper in the area before it shipped."

Direct answer

Convert the smaller of the two arrays to a hash set, then scan the larger array once, keeping any element that's present in that set (collecting results in a second set so duplicates in the larger array don't produce duplicate output). This is O(n + m) time. Building the set from the smaller array specifically bounds the extra memory to O(min(n, m)) rather than O(max(n, m)).

Approach

1. Determine which input array is smaller; build a hash set from it.
2. Scan the other (larger) array once. For each element, check set membership (O(1) average); if present, add it to a result set.
3. Return the result set as a list. Using a set for the result (not a list with manual duplicate-checking) means each hit is still O(1) average to record, and duplicates collapse automatically.

Complexity

Time: O(n + m): O(min(n, m)) to build the smaller set, O(max(n, m)) to scan the other array with O(1) average membership checks. Space: O(min(n, m)) for the set that gets built, plus O(result size) for the output, which is at most min(n, m).

Edge cases

• No overlap at all: returns an empty list.
• One array is empty: returns an empty list immediately (no need to even build a set from the other one).
• Duplicates on either side don't affect the result, since both membership testing and the result collection are set-based.

def intersection(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    small_set = set(nums1)
    result = set()
    for x in nums2:
        if x in small_set:
            result.add(x)
    return list(result)


nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(sorted(intersection(nums1, nums2)))

nums1b = [4, 9, 5]
nums2b = [9, 4, 9, 8, 4]
print(sorted(intersection(nums1b, nums2b)))

Output:

[2]
[4, 9]

The first case matches the question's own example directly: duplicates on both sides (2 appears twice in nums1, twice in nums2) still produce a single 2 in the output. The second case shows the general behavior with distinct arrays: 4 and 9 are the only values common to both, 5 and 8 are not shared.

Trade-offs and pitfalls

• The core memory trade-off: the hash-set approach spends O(min(n, m)) extra memory to buy O(n + m) time; that memory cost is the price of O(1) average membership checks, and choosing to build the set from the smaller array specifically minimizes how much of that price you pay.
• Time-vs-space alternative: if both arrays are already sorted (or can be sorted), a two-pointer sweep over both does the same job in O((n + m) log(n + m)) time (dominated by the sort, if not already sorted) but only O(1) extra space beyond the output, trading time for space. This matters when memory is the binding constraint and the arrays are large enough that even the smaller hash set doesn't comfortably fit.
• Hashability requirement: the set-based approach only works directly on hashable elements (ints, strings, tuples of hashables); a list of unhashable items (e.g. dicts) needs a different comparison strategy, such as sorting by a derived key or using a hashable representation of each element.
• Streaming / memory-bound variant, tied to the question's "overlapping users between datasets" framing: if one of the two "arrays" is really a live dataset too large to hold entirely in memory, you can still build the in-memory set from whichever side is smaller and stream the larger side through it one record at a time without ever materializing the larger side fully, which is the same core technique as above just applied to a data pipeline instead of an in-memory list. If even the smaller side doesn't fit in memory, that's a genuinely different problem (approximate membership / external-memory joins), and calls for infrastructure well beyond this warm-up technique.
• Common miscount: returning a list built by iterating nums2 and appending on every match without deduplication reproduces the multiplicity of matches (intersect with repeats) rather than the "unique elements only" result the question asks for.

Direct answer

A sorting algorithm is stable if it preserves the relative order of elements
that compare equal on the sort key. If two records tie on the key you sorted
by, a stable algorithm guarantees the one that came first in the input still
comes first in the output. This matters for multi-key sorts: if you sort by a
secondary key after already sorting by a primary one, stability is what lets
the primary ordering survive as a tiebreaker inside each secondary-key group.
Merge sort and Python's Timsort (the algorithm behind sorted() and list.sort())
are stable; classic in-place selection sort and a typical quicksort are not.

Structured elaboration

Why stability matters for multi-key sorts. The standard trick for sorting
by (primary key, secondary key) without writing a composite comparator is:
sort once by the primary key, then sort the result by the secondary key. This
only produces the correct combined order if the second sort is stable: a
stable sort only reorders elements that actually differ on the secondary key,
so within any group of equal secondary-key values, the primary-key order from
step one is left untouched. An unstable sort makes no such promise: it may
reorder equal-secondary-key elements arbitrarily while grouping them, silently
destroying the primary ordering you already paid to establish.

A stable sort: merge sort, and Timsort (the hybrid merge/insertion sort
used by Python and Java's Collections.sort for objects). Both work by
merging or shifting elements without ever swapping two elements past an equal
one, so ties keep their input order.

An unstable sort: classic in-place selection sort (repeatedly swap the
current position with the position of the next-smallest remaining element).
The swap step moves elements across long distances in the array, including
past other elements with the same key, which is exactly what breaks ties.
Typical in-place quicksort implementations are unstable for the same reason
(the partition step swaps non-adjacent elements).

If you only have an unstable sort available, you can force stability by
attaching the original index to each record and sorting by (key, original_index)
instead of key alone. Ties on key are then broken by index, which exactly
reproduces stable behavior, at the cost of allocating one extra field per record.

Worked example

Take four employee records, already sorted by name (the primary key):

Now sort by department (the secondary key). A stable sort must produce:

Eng: Chen, Ito       (name order preserved)
Sales: Alvarez, Diallo  (name order preserved)

Running this in Python, where sorted() is stable, versus a hand-rolled
unstable selection sort, on the exact same input:

records = [
    {"name": "Alvarez", "dept": "Sales"},
    {"name": "Chen", "dept": "Eng"},
    {"name": "Diallo", "dept": "Sales"},
    {"name": "Ito", "dept": "Eng"},
]

stable_result = sorted(records, key=lambda r: r["dept"])

def unstable_selection_sort_by_dept(items):
    items = list(items)
    n = len(items)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if items[j]["dept"] < items[min_idx]["dept"]:
                min_idx = j
        items[i], items[min_idx] = items[min_idx], items[i]
    return items

unstable_result = unstable_selection_sort_by_dept(records)

print([(r["dept"], r["name"]) for r in stable_result])
print([(r["dept"], r["name"]) for r in unstable_result])

Output (verified by running this exact code):

[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Alvarez'), ('Sales', 'Diallo')]
[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Diallo'), ('Sales', 'Alvarez')]

The Eng group comes out identical either way, but the Sales group is
reversed under the unstable sort: Diallo now precedes Alvarez, even though
Alvarez came first alphabetically. That reversal is the bug: any downstream
code relying on "same department, alphabetical order" is now silently wrong,
and the failure is data-dependent, so it will not show up on every input.

Trade-offs & pitfalls

• Stability is a property of the algorithm's specification, not just a given
  implementation detail: "quicksort" is not stable by definition, but a
  particular library's sort might document stability as a guarantee (check
  the docs rather than assuming from the algorithm's name).
• The index-as-tiebreaker trick works with any comparison sort, stable or not,
  but costs O(n) extra memory for the index field and slightly more comparison
  overhead per element; it is the right choice when the language's built-in
  sort is unstable by contract (e.g. a raw quicksort library call) and you
  cannot swap in a stable one.
• A common wrong turn is assuming "the final order looks right on my test
  data" is proof of stability; instability is a tie-breaking behavior that
  only shows up when there are actual ties, so it hides in datasets with few
  duplicate keys and surfaces later at a different data distribution.
• Do not confuse stability with sort correctness on the primary sort key
  itself: an unstable sort still produces a fully correct order on the key it
  was told to sort by, it only fails to preserve unrelated prior ordering
  among equal elements.

Direct answer

State a genuine preference (or an honest "it depends on this stage of my own career") backed by two or three concrete trade-offs that matter most to you personally, not a generic recited list of pros and cons.

Structured elaboration

What this question screens for
Whether you've actually thought about how company stage affects your day-to-day work, versus giving a textbook answer. It also probes whether you can name a genuine downside of your own stated preference.

The core trade-offs

Name which two or three rows matter most to YOU specifically, and why. That's what turns this table into a real answer instead of a recited summary.

Worked example

The same trade-offs show up in what kind of problems you get handed. At an early-stage company, a candidate in this field might get an open-ended question like "[a validation or discovery-shaped question typical of your discipline early in a company's life]." At an established company, the equivalent question is narrower, something like "[a well-scoped optimization or risk-reduction question typical of your discipline at scale]." Swap the example questions for your own discipline: a security-focused role might weigh "is this new integration safe to ship" at an early-stage company against "how do we harden a system that's already in production" at an established one; a data role might weigh "do we even have the right metric" against "how do we make this metric pipeline auditable at scale."

Trade-offs and pitfalls

• Red flag: a generic answer that lists textbook pros and cons without saying which ones matter to you and why; interviewers want your actual priorities, not a summary.
• Red flag: dismissing the company you're interviewing with, if it's the "other" stage from your stated preference, without addressing the mismatch directly.
• Pitfall: treating this as strictly binary. The honest answer often depends on the specific team's stage, not just company headcount, since a large company can have a scrappy, early-stage-feeling internal team.
• Pitfall: over-indexing on compensation structure alone (equity vs. cash) as the deciding trade-off, which reads as motivated more by upside than by the work itself.

Definitions

Priority inversion is a high-priority task waiting on a lower-priority one. Two protocols bound it:

• Priority inheritance (PIP): a task holding a lock runs at the priority of the highest-priority task waiting for it. Inheritance happens only when someone actually waits.
• Priority ceiling protocols: every lock gets a ceiling, the highest priority of any task that ever uses it. In the original protocol (PCP, analysed by Sha, Rajkumar and Lehoczky, 1990), a task may lock something only if its priority is higher than the ceilings of all locks currently held by other tasks. In the immediate variant (ICPP, used in the program below), a task jumps to the lock's ceiling priority the moment it locks it. Both bound blocking to one critical section, and both can make a task wait even when the lock it wants is free; that is the price, sometimes called ceiling or avoidance blocking because the wait avoids a later chain or deadlock. The rest of this answer says "inheritance" or PIP for the first protocol and "ceiling" or ICPP for the second.

Blocking time B is the longest a task can be delayed by lower-priority tasks. It enters the response-time recurrence R = C + B + (interference from higher-priority tasks).

The example

Three tasks, priorities H above M above L, two mutexes R1 and R2. Longest critical sections:

Ceilings: R1 is used by H and M, so its ceiling is H's priority. R2 is used by H and L, so its ceiling is also H's priority. The script computes both bounds from the table by rule, and then runs a tick-level simulation (1 tick is 0.1 ms) of the worst arrival order for each protocol, printing the measured blocking and a timeline of who ran when. Run in a python:3.12-slim container with python blocking_bounds.py:

# Blocking bounds under priority inheritance (PIP) and the immediate priority
# ceiling protocol (ICPP), plus a tick-level simulation (1 tick = 0.1 ms) that
# measures the blocking and prints who runs when.

# priority: bigger number = more urgent
# cs[task] = list of (mutex, length_in_ms) outermost, non-nested critical sections
def bounds(prio, cs):
    # ceiling[r] = priority of the most urgent task that ever locks r
    ceiling = {}
    for t, secs in cs.items():
        for r, _ in secs:
            ceiling[r] = max(ceiling.get(r, 0), prio[t])
    out = {}
    for i in prio:
        lower = [j for j in prio if prio[j] < prio[i]]
        # Collect the critical sections of lower-priority tasks that can delay i:
        # per_task[j] = longest such section of task j, per_mutex[r] = longest on lock r
        per_task, per_mutex, singles = {}, {}, []
        for j in lower:
            for r, d in cs.get(j, []):
                if ceiling[r] >= prio[i]:  # j holds r; r is used by i or by a task above i
                    per_task[j] = max(per_task.get(j, 0), d)
                    per_mutex[r] = max(per_mutex.get(r, 0), d)
                    singles.append(d)
        # PIP: each lower task blocks i at most once, and each lock blocks i at most
        # once, so the bound is the smaller of the two sums (the min(n, m) rule).
        pip = min(sum(per_task.values()), sum(per_mutex.values()))
        # ICPP: i is blocked at most once, by the single longest such section.
        icpp = max(singles, default=0)
        out[i] = (pip, icpp)
    return out

def show(title, prio, cs):
    print(title)
    for t, (pip, icpp) in sorted(bounds(prio, cs).items(), key=lambda kv: -prio[kv[0]]):
        print(f"  {t}: B_pip={pip} ms  B_icpp={icpp} ms")

three_prio = {"H": 3, "M": 2, "L": 1}
three_cs = {"H": [("R1", 1), ("R2", 1)], "M": [("R1", 2)], "L": [("R2", 3)]}
show("Three tasks, two mutexes", three_prio, three_cs)

four_prio = {"H": 4, "M": 3, "L1": 2, "L2": 1}
four_cs = {"H": [("R2", 1)], "M": [("R1", 2)], "L1": [("R1", 2)], "L2": [("R2", 3)]}
show("Same set with the low task split in two", four_prio, four_cs)

# ---------- simulation ----------
def simulate(protocol, prio, releases, progs, horizon=200):
    ceil = {}
    for t, p in progs.items():
        for op in p:
            if op[0] == "lock":
                ceil[op[1]] = max(ceil.get(op[1], 0), prio[t])
    pc = {t: 0 for t in progs}; left = {t: 0 for t in progs}
    owner = {}; held = {t: [] for t in progs}; blocked_on = {t: None for t in progs}
    done = {t: False for t in progs}; inv = {t: 0 for t in progs}
    def eff(t):
        # effective priority: base priority, raised by the protocol
        e = prio[t]
        if protocol == "ICPP":
            for r in held[t]:
                e = max(e, ceil[r])
        else:
            for u in progs:
                if blocked_on[u] is not None and owner.get(blocked_on[u]) == t:
                    e = max(e, eff(u))
        return e
    last = None
    finish = {}
    segs = []  # (task, first tick, last tick) of each uninterrupted run
    for now in range(horizon):
        while True:
            ready = [t for t in progs if releases[t] <= now and not done[t] and blocked_on[t] is None]
            if not ready:
                run = None; break
            run = max(ready, key=lambda t: (eff(t), t == last, -list(progs).index(t)))
            op = progs[run][pc[run]] if pc[run] < len(progs[run]) else None
            if op is None:
                done[run] = True; finish[run] = now; continue
            if op[0] == "lock":
                if op[1] in owner:
                    blocked_on[run] = op[1]; continue
                owner[op[1]] = run; held[run].append(op[1]); pc[run] += 1; continue
            if op[0] == "unlock":
                owner.pop(op[1]); held[run].remove(op[1]); pc[run] += 1
                for u in progs:
                    if blocked_on[u] == op[1]:
                        blocked_on[u] = None
                continue
            break  # a "run" op
        if run is None:
            continue
        for t in progs:
            if releases[t] <= now and not done[t] and prio[run] < prio[t]:
                inv[t] += 1
        if segs and segs[-1][0] == run and segs[-1][2] == now - 1:
            segs[-1][2] = now
        else:
            segs.append([run, now, now])
        last = run
        left[run] = left[run] or progs[run][pc[run]][1]
        left[run] -= 1
        if left[run] == 0:
            pc[run] += 1
    return inv, segs

U = 10

def timeline(segs):
    return " ".join(f"{t}[{a / U:.1f}-{(b + 1) / U:.1f}]" for t, a, b in segs)  # ticks per ms
def prog(*ops):
    out = []
    for o in ops:
        out.append((o[0], o[1] * U) if o[0] == "run" else o)
    return out

# three tasks: L takes R2 at t=0, M is released at 0.1 ms and takes R1,
# H is released at 0.2 ms and needs R1 then R2
progs3 = {
    "H": prog(("run", 0.1), ("lock", "R1"), ("run", 1), ("unlock", "R1"), ("lock", "R2"), ("run", 1), ("unlock", "R2")),
    "M": prog(("lock", "R1"), ("run", 2), ("unlock", "R1"), ("run", 0.5)),
    "L": prog(("lock", "R2"), ("run", 3), ("unlock", "R2")),
}
rel3 = {"L": 0, "M": 1, "H": 2}
for proto in ("PIP", "ICPP"):
    inv, segs = simulate(proto, three_prio, rel3, progs3)
    print(f"sim 3 tasks {proto}: ticks spent behind a lower-priority task ->",
          {t: inv[t] / U for t in ("H", "M", "L")}, "ms")
    print("   ", timeline(segs))

# four tasks: L2 takes R2 at t=0, L1 (released 0.1 ms) takes R1,
# M (0.2 ms) needs R1, H (0.3 ms) needs R2
progs4 = {
    "H": prog(("run", 0.1), ("lock", "R2"), ("run", 1), ("unlock", "R2")),
    "M": prog(("lock", "R1"), ("run", 2), ("unlock", "R1"), ("run", 0.5)),
    "L1": prog(("lock", "R1"), ("run", 2), ("unlock", "R1")),
    "L2": prog(("lock", "R2"), ("run", 3), ("unlock", "R2")),
}
rel4 = {"L2": 0, "L1": 1, "M": 2, "H": 3}
for proto in ("PIP", "ICPP"):
    inv, segs = simulate(proto, four_prio, rel4, progs4)
    print(f"sim 4 tasks {proto}: ticks spent behind a lower-priority task ->",
          {t: inv[t] / U for t in ("H", "M")}, "ms")
    print("   ", timeline(segs))

Three tasks, two mutexes
  H: B_pip=5 ms  B_icpp=3 ms
  M: B_pip=3 ms  B_icpp=3 ms
  L: B_pip=0 ms  B_icpp=0 ms
Same set with the low task split in two
  H: B_pip=3 ms  B_icpp=3 ms
  M: B_pip=5 ms  B_icpp=3 ms
  L1: B_pip=3 ms  B_icpp=3 ms
  L2: B_pip=0 ms  B_icpp=0 ms
sim 3 tasks PIP: ticks spent behind a lower-priority task -> {'H': 4.8, 'M': 2.9, 'L': 0.0} ms
    L[0.0-0.1] M[0.1-0.2] H[0.2-0.3] M[0.3-2.2] H[2.2-3.2] L[3.2-6.1] H[6.1-7.1] M[7.1-7.6]
sim 3 tasks ICPP: ticks spent behind a lower-priority task -> {'H': 2.8, 'M': 2.9, 'L': 0.0} ms
    L[0.0-3.0] H[3.0-5.1] M[5.1-7.6]
sim 4 tasks PIP: ticks spent behind a lower-priority task -> {'H': 2.9, 'M': 4.8} ms
    L2[0.0-0.1] L1[0.1-0.3] H[0.3-0.4] L2[0.4-3.3] H[3.3-4.3] L1[4.3-6.1] M[6.1-8.6]
sim 4 tasks ICPP: ticks spent behind a lower-priority task -> {'H': 2.7, 'M': 2.8} ms
    L2[0.0-3.0] H[3.0-4.1] M[4.1-6.6] L1[6.6-8.6]

Reading the program

• bounds() applies the rules to the table. A critical section of a lower-priority task counts against task i only if the lock's ceiling is at least i's priority (ceiling[r] >= prio[i]), because only then can the holder run at a priority above i's. Under inheritance, each lower-priority task can block i at most once (per_task keeps the longest such section of each task) and each lock can block i at most once (per_mutex keeps the longest section on each lock), so the bound is the smaller of the two sums, which is the min(n, m) rule (n counts tasks, m counts locks). Under the ceiling protocol the bound is the single longest such section (singles), because i can be blocked only once.
• simulate() advances time one tick at a time. progs gives each task a script of operations: ("run", ms) uses the CPU, ("lock", r) and ("unlock", r) take and release a mutex. eff(t) is a task's effective priority: its own priority, raised by the protocol (under ICPP, to the highest ceiling among the locks it holds; under PIP, to the highest effective priority among the tasks waiting for a lock it holds, which handles chains because eff calls itself). blocked_on[t] records which lock a task is waiting for and owner[r] who holds it.
• The while True loop repeats the choice of the highest-priority ready task at every instant where something changes without time passing: if the chosen task's next operation is a lock that someone owns, the task is marked blocked and the choice is made again; an unlock wakes the waiters and the choice is made again; only a "run" operation ends the loop and uses the tick.
• inv counts, for each task, the ticks during which it is released and unfinished while a lower-priority task is running, which is exactly the priority-inversion time the bounds limit. The printed timeline lists each uninterrupted run as task[start-end] in ms.

Bounds for the medium-priority task

For M in the three-task set, both protocols give 3 ms. M has only one lower-priority task, L, and L's only critical section is the 3 ms one on R2. It counts against M even though M never locks R2, because R2's ceiling (H's priority) is above M's: if L holds R2 and H then waits for it, L inherits H's priority and runs ahead of M (push-through blocking, in Sha's terms: being delayed by a task that is running at an inherited priority above yours, although you never use its lock). M can be blocked by L only once, because after L leaves the section M outranks it and L cannot take another lock before M finishes. So with a single lower-priority task the two protocols cannot differ for M. The simulation agrees: M spends 2.9 ms behind L under both (L had already run 0.1 ms of its 3 ms when M arrived), and each protocol's printed timeline shows L running to the end of its R2 section before M finishes (under inheritance M's R1 section ends at 2.2 ms, but M's last 0.5 ms of work waits until L has left R2 at 6.1 ms).

Where the protocols differ: more than one lower-priority task, or the top task

Under inheritance, 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 block it; under the original ceiling protocol (PCP) it is at most one critical section (both results are in Sha et al., 1990). ICPP has the same one-critical-section bound, but the 1990 paper analyses the original protocol; ICPP is the variant POSIX calls priority protect and Ada calls ceiling locking. The difference shows up when n and m are both at least 2:

• H in the same set has n = 2 (M and L) and m = 2 (R1, R2). Inheritance bound: M's 2 ms on R1 plus L's 3 ms on R2 = 5 ms. Ceiling bound: 3 ms, the longest single section.
• M in a four-task set where the low-priority work is split into L1 (R1 for 2 ms) and L2 (R2 for 3 ms), with H using R2 for 1 ms and M using R1 for 2 ms: M can be blocked by L1 on R1 directly (2 ms) and by L2 through R2's ceiling (3 ms), so the inheritance bound for M is 5 ms and the ceiling bound is 3 ms. The program prints this second case too (M: 5 vs 3), and its timeline shows where the 5 comes from. Under inheritance, L2 locks R2 at t = 0 and L1 (released at 0.1 ms) preempts it and locks R1. M is released at 0.2 ms and waits for R1, so L1 runs on at M's priority. H is released at 0.3 ms, runs 0.1 ms, then waits for R2, so L2 runs at H's priority from 0.4 to 3.3 ms (L2[0.4-3.3]) while M waits, then H runs, then L1 finishes its section (L1[4.3-6.1]) while M still waits and only then does M run at 6.1 ms. M is held up by L1 for 0.1 + 1.8 = 1.9 ms and by L2 for 2.9 ms, 4.8 ms in all, close to the 5 ms bound (the 0.2 ms difference is the 0.1 ms each task had already run before the next one arrived). Under the ceiling protocol, L2 runs at H's priority from its lock at t = 0, so L1 never gets to take R1; M waits only for L2 until 3.0 ms (L2[0.0-3.0]), then H and M run, and M's blocking is 2.8 ms, inside the 3 ms bound.

Why the ceiling gives the lower bound

The chain is what inheritance cannot prevent. In the simulation of the three-task set, L takes R2 first. M then arrives, preempts L (it has higher priority and nothing has been inherited yet) and takes R1. H arrives and needs R1, which M holds, so H waits for M (roughly 2 ms); H gets R1, finishes with it, and then needs R2, still held by the preempted L, so H waits again (roughly 3 ms). Total 4.8 ms behind lower-priority tasks, close to the 5 ms bound (the gap is the 0.1 ms that L ran before M arrived plus the 0.1 ms that M ran before H arrived at 0.2 ms). Under ICPP, L is raised to R2's ceiling, H's priority, the instant it locks R2, so M cannot preempt it and never gets to take R1 while L is inside R2. H waits only for L's remaining time, 2.8 ms, within the 3 ms bound. Ceiling blocking is the price: M is held back even though R1 was free.

The original ceiling protocol also prevents deadlock between tasks (Sha et al. prove it, assuming a task does not deadlock with itself), because the situation in which two tasks each hold a lock the other needs cannot form.

What to do with the numbers

Use the ceiling bound when the design has several locks and a tight task above the lowest priority: it is smaller and gives one number to reason about. Inheritance needs no table of ceilings, so it suits code where the set of lock users is not known in advance. Add the chosen B to the response-time recurrence for each task; for H a bound of 3 ms instead of 5 ms can decide whether a task with a tight deadline passes the test.

Design overview
Implement a portable bit-banged SPI driver written in C with a pluggable “port” layer for GPIO set/clear/read. Expose a transfer API: int spi_transfer(const spi_cfg_t *cfg, const uint8_t *tx, uint8_t *rx, size_t len). cfg includes CPOL/CPHA, SCLK pin, MOSI, MISO, mode, and target frequency (<=1 MHz). The driver implements full-duplex by sampling MISO on the configured phase while toggling SCLK and outputting MOSI bits.

Timing choices

• Target: 1 MHz -> 500 ns half-period. For Cortex-M, prefer DWT_CYCCNT or SysTick/hardware timer to get accurate delays when available.
• Busy-wait loops (tight cycle-counted NOP sequences) are simplest and lowest-overhead if you can guarantee no preemption and know core clock. Use only when running with IRQs masked or at high priority.
• Hardware-timer driven delays (single-shot compare) give accurate timing without burning CPU but add ISR overhead; good when preemption/RTOS coexist or lower CPU load is desired.

Recommendation: use a hybrid: prefer cycle-counter busy-waits when DWT available and driver runs with IRQs allowed but briefly temporarily elevated; fall back to a high-resolution hardware timer when DWT missing or when OS preemption cannot be controlled.

Optimizations

• Inline the bit loop and mark hot with inline/always_inline.
• Loop unrolling for common lengths (bytes): transmit 8 bits in an unrolled sequence to remove loop overhead.
• Precompute per-byte toggle sequences into a small table of 8 toggle actions for CPHA/CPOL variants so per-bit branching is minimized.
• Use word-sized GPIO registers (write mask) to toggle SCLK/MOSI in a single atomic register write when MCU supports it.
• Use DWT cycle reads to spin until target cycles instead of function-call delays.
• If multiple transfers to same device, cache computed timing parameters and pin masks.

RTOS preemption and IRQs

• Full-duplex bit-bang is timing-sensitive: either
  • perform short transfers with IRQs enabled but rely on cycle-counted delays (acceptable for millisecond-level transfers), or
  • take a short critical section: raise task priority / disable scheduler preemption (not global IRQs unless needed) during each byte to guarantee timing.
• Document that very long transfers should use hardware SPI to avoid blocking scheduler.
• Protect GPIO and device state with mutexes; allow ISR-driven higher-priority tasks to preempt but ensure transfer recovers if interrupted (restart byte or abort with error).

Dynamic hardware detection & switching

• Provide an SPI backend abstraction: bitbang_backend and hw_backend. At init, probe for hardware SPI by:
  • Checking SoC peripheral registers/enumeration (device tree / HAL API) and configuring chip-select pins.
  • Attempting a quick loopback transfer through hardware SPI to validate functioning.
• If hardware available and pins match (or can be remapped), switch to hw_backend which uses DMA + peripheral.
• Allow runtime override: spi_set_backend(handle, prefer_hw) so system can choose based on concurrent load, power, or timing needs.

Trade-offs

• Busy-wait: lowest latency, highest CPU usage, fragile under preemption.
• Timer/ISR: lower CPU use, higher latency and code complexity.
• Precompute/unroll: memory vs CPU trade-off — acceptable for performance-critical paths.

This design balances portability, 1 MHz timing, low CPU overhead via cycle counters and register writes, RTOS safety via short critical sections and mutexes, and runtime flexibility to use hardware SPI when available.

High-level approach
Provide a driver core that abstracts transfer submission to a mode-agnostic "transfer engine" which dispatches to either PIO or DMA backends. Maintain descriptor queues, a small state machine for each transfer, and centralized error/retry/timer logic. Ensure suspend/resume serializes outstanding work and quiesces DMA.

Data structures

• Transfer descriptor (per transfer)
• Ring/linked queue for pending/completed transfers
• Backend ops vtable for PIO/DMA
• Driver/global context with mode, locks, timers

Example C structures:

// transfer descriptor
struct xfer_desc {
    uint32_t id;
    void *buf;
    size_t len;
    enum { XFER_PENDING, XFER_BUSY, XFER_DONE, XFER_ERROR } state;
    int retries;
    uint32_t timeout_ms;
    struct completion done; // kernel-style or RTOS event
    struct xfer_desc *next;
};

// backend ops
struct backend_ops {
    int (*start)(struct xfer_desc *);
    int (*abort)(struct xfer_desc *);
    void (*irq_handler)(void *);
};

Queues

• pending_queue (FIFO): user submits -> pending
• active_list: in-flight transfers
• done_queue: completed for user dequeue/callback

Protect with a spinlock/mutex; use atomic flags for suspend.

State machine (per transfer)

• PENDING -> (start) -> BUSY
• BUSY -> (completion IRQ or poll) -> DONE
• BUSY -> (timeout) -> RETRY if retries>0 -> restart; else -> ERROR
• On ERROR -> move to DONE with error code; notify user

Global states: RUNNING, SUSPENDING, SUSPENDED, RESUMING, SHUTDOWN. Suspend waits for active transfers or aborts based on policy.

Error recovery

• Per-transfer timeout timer: on expiry, call backend->abort, increment retries, requeue or fail
• Exponential backoff for retries optional
• Fatal error escalation: mark device offline and notify upper layers

Suspend/resume

• suspend() sets state SUSPENDING, prevents new submissions, optionally waits bounded time for active transfers then:
  • For DMA: stop controller, save DMA descriptor pointers, flush caches, disable IRQs
  • For PIO: abort/complete or requeue
• resume(): restore controller registers, reprogram DMA pointers, re-enable IRQs, restart pending transfers
• All steps are idempotent and protected by locks

Runtime mode selection

• driver_set_mode(enum MODE_PIO, MODE_DMA): atomically swap backend_ops pointer; if transfers active, either block until idle or fail with BUSY
• Expose sysfs/ioctl to change mode at runtime with validation

Key APIs (embedded C style)

int driver_init(struct device *dev);
int driver_set_mode(int mode);
int driver_submit(void *buf, size_t len, uint32_t timeout_ms, int flags);
int driver_cancel(uint32_t xfer_id);
int driver_suspend(void);   // called by power manager
int driver_resume(void);
void driver_isr(void *arg); // top-half calls backend irq handler

Notes & trade-offs

• DMA: best throughput; requires cache maintenance and coherent memory or IOMMU.
• PIO: simpler, lower latency for tiny transfers; CPU-bound.
• Choosing to abort-in-flight vs wait on suspend depends on power/latency constraints.
• Keep critical paths lock-free where possible; use small bounded retry counts to avoid livelock.

This design balances runtime flexibility, robust recovery, and safe low-power transitions appropriate for embedded systems.

Design: one array ring buffer, one writer index, one CAS-advanced reader index. An ISR (interrupt service routine) is a handler the hardware runs when an interrupt fires; on a Cortex-M the NVIC (nested vectored interrupt controller) lets a higher-priority interrupt preempt (interrupt in the middle of) a lower-priority handler, and a handler running in any priority preempts the main-loop "thread" code. So the producer in thread context can be interrupted by any consumer ISR, and a low-priority consumer can be interrupted by a higher-priority consumer that pops from the same queue. Nothing here masks interrupts, so no interrupt is ever delayed by the queue.

Two C11 atomics (indivisible reads and writes, with ordering rules the compiler and CPU must respect) do the work. tail has exactly one writer, the producer. head has several writers, the consumer ISRs, so it advances with CAS (compare-and-swap: store the new value only if the variable still holds the value I read, else report failure). Indices count forever and wrap at 2^32; the slot is index % QN, and QN = 8 divides 2^32, so the mapping stays correct across the wrap and tail - head (unsigned) is the fill level. The ordering arguments in the code are the C11 memory orders: memory_order_relaxed gives atomicity only; a release store promises that every write made before it is visible to any thread that reads the stored value with an acquire load; an acquire load is the other half of that pairing (it also keeps later reads from being moved before it); acq_rel on a read-modify-write like compare-exchange is both at once. The _weak compare-exchange is allowed to report failure even when the values matched, which is harmless inside a retry loop and can be cheaper.

#include <stdatomic.h>
#include <stdbool.h>
#include <stdint.h>

#define QN 8u /* power of two */

#ifndef PREEMPT_POINT
#define PREEMPT_POINT() ((void)0)
#endif

typedef struct {
    _Atomic uint32_t head; /* next index to pop; advanced by CAS from any ISR */
    _Atomic uint32_t tail; /* next index to push; written by the producer only */
    uint32_t slot[QN];
} isr_queue;

/* Producer: thread context only. Never masks interrupts. */
static inline bool q_push(isr_queue *q, uint32_t v)
{
    uint32_t t = atomic_load_explicit(&q->tail, memory_order_relaxed);
    uint32_t h = atomic_load_explicit(&q->head, memory_order_acquire);
    if (t - h == QN)
        return false;                       /* full */
    q->slot[t % QN] = v;
    PREEMPT_POINT();                        /* test hook: ISRs may run here */
    atomic_store_explicit(&q->tail, t + 1, memory_order_release);
    return true;
}

/* Consumer: callable from any ISR, at any priority. */
static inline bool q_pop(isr_queue *q, uint32_t *out)
{
    uint32_t h = atomic_load_explicit(&q->head, memory_order_acquire);
    for (;;) {
        uint32_t t = atomic_load_explicit(&q->tail, memory_order_acquire);
        if (h == t)
            return false;                   /* empty */
        uint32_t v = q->slot[h % QN];
        PREEMPT_POINT();                    /* test hook: a higher ISR may pop here */
        if (atomic_compare_exchange_weak_explicit(&q->head, &h, h + 1,
                memory_order_acq_rel, memory_order_acquire)) {
            *out = v;
            return true;
        }
        /* CAS failed: h now holds the fresh head; retry */
    }
}

/* Broken variant for comparison: the head update is a plain read-then-write. */
static inline bool q_pop_plain(isr_queue *q, uint32_t *out)
{
    uint32_t h = atomic_load_explicit(&q->head, memory_order_acquire);
    uint32_t t = atomic_load_explicit(&q->tail, memory_order_acquire);
    if (h == t)
        return false;
    uint32_t v = q->slot[h % QN];
    PREEMPT_POINT();
    atomic_store_explicit(&q->head, h + 1, memory_order_release);
    *out = v;
    return true;
}

Why each operation is safe if a higher-priority ISR preempts it.

1. q_push, between loading head and storing tail. Only the producer writes tail, so no one changes it under the producer. head can only grow, so a stale head makes the queue look fuller than it is: at worst a push is refused when it could have succeeded, never an overwrite of an unread slot.
2. q_push, between writing the slot and the tail release-store. A consumer that runs now still sees the old tail, so it treats the new slot as not yet there. The release store orders the slot write before the tail update (and stops the compiler moving the write after it). A consumer that acquire-loads the new tail therefore also sees the slot contents. Acquire and release are the ordering annotations that make "data written, then flag published" work. The disassembly below shows GCC emitting dmb (data memory barrier) for them even on one core, which is harmless; on one core, atomic_signal_fence plus relaxed accesses would be enough for the compiler-ordering half.
3. q_pop, between reading tail and the CAS. If a higher-priority ISR pops in this gap, head moves from h to h + 1. The preempted consumer resumes with a stale h and a copy v of a slot that is already delivered. The CAS compares head against that stale h, fails, refreshes h, and the loop re-reads the slot. v is discarded, not delivered, so an item is handed out exactly once.
4. q_pop, between the slot read and the CAS, with a producer. The producer can only reuse slot h % QN after head has moved past h, and the CAS succeeds only if head is still h. A wrap-around false match (the ABA problem: the CAS sees the value it expected, head == h, although head has changed and come back to the same number) would need head to advance exactly 2^32 times inside one preemption window, which a 32-bit index makes unreachable here.
5. The CAS itself, between its load and store. On Cortex-M3, M4 and M7 (Armv7-M) the compiler turns it into ldrex / strex (load-exclusive and store-exclusive: the store succeeds only if nothing intervened). The core keeps a small state machine, the local monitor, that remembers that an ldrex is waiting for its strex; "Open Access" is the state meaning no such reservation is pending, and strex then fails and writes 1 to its status register. The Armv7-M Architecture Reference Manual (DDI 0403E.e, section A3.4.4, Context switch support) says: "In Armv7-M, the local monitor is changed to Open Access automatically as part of an exception entry or exit sequence." Its exception-entry pseudocode (ExceptionTaken) calls ClearExclusiveLocal. So an interrupt taken between ldrex and strex makes strex fail, and the loop retries from the top. In this queue correctness does not rest on that rule alone: every writer of head is a CAS, a pop that wins ends with its own strex, and a Store-Exclusive always leaves the local monitor in Open Access, so a stale reservation cannot survive an intervening pop. The rule is the backstop for any other route by which head changes, and it is also why an unrelated interrupt costs a spurious retry. It is also a reason never to mix a plain store to head into the CAS protocol: the manual leaves it IMPLEMENTATION DEFINED whether an ordinary write to the tagged address clears the local monitor. The weak form is used because it is allowed to fail spuriously and is the cheaper form inside a retry loop.

Progress guarantee. A consumer retries only when something preempted it or popped first. The highest-priority consumer cannot be preempted by another consumer, so it retries only if an unrelated higher ISR exception hits the ldrex/strex window (or the weak compare-exchange fails spuriously). Retries by a lower consumer are bounded by the number of times higher-priority code runs during its pop. That is lock-free (some caller always completes, even if others are preempted), not wait-free (which would bound every caller to a fixed number of steps), and a higher-priority ISR never waits for a lower one, which is the property a mask-based critical section gives up.

Evidence: a scripted preemption, run under QEMU. The harness pends (marks as waiting) a high-priority IRQ from inside the low-priority consumer, after it has read slot 0 and before its CAS. Files: isrq.h above, plus these.

demo.c walk-through: the REG, UART_* and NVIC_* macros defined at its top turn fixed addresses into volatile registers (NVIC_ISPR0 pends an interrupt from software, NVIC_ISER0 enables interrupts 0 and 1, NVIC_IPR(n) is the priority byte of interrupt n, where a smaller number is more urgent); putc_, puts_ and putu write characters and decimal numbers to the UART. preempt_here is the test hook: the queue code calls it at the marked points, and when hook_armed is set and the low-priority handler is the caller (in_low), it pends the high-priority interrupt once, which runs immediately because it is more urgent. irq_low_handler and irq_high_handler each pop one item and record it. main pushes 1, 2, 3, arms the hook, and pends the low interrupt.

demo.c:

void preempt_here(void);
#define PREEMPT_POINT() preempt_here()
#include "isrq.h"
#ifdef PLAIN
#define q_pop q_pop_plain
#endif

#define REG(a) (*(volatile uint32_t *)(a))
#define UART_DR    REG(0x4000C000u)
#define UART_CR    REG(0x4000C030u)
#define NVIC_ISER0 REG(0xE000E100u)
#define NVIC_ISPR0 REG(0xE000E200u)
#define NVIC_IPR(n) (*(volatile uint8_t *)(0xE000E400u + (n)))
#define IRQ_LOW  0                    /* priority 0xE0 */
#define IRQ_HIGH 1                    /* priority 0x40: preempts IRQ_LOW */

static isr_queue q;
static volatile uint32_t got_low, got_high, n_low, n_high;
static volatile int hook_armed, in_low;

static void putc_(char c) { UART_DR = (uint32_t)c; }
static void puts_(const char *s) { while (*s) putc_(*s++); }
static void putu(uint32_t v) {
    char b[11]; int i = 0;
    if (!v) b[i++] = '0';
    while (v) { b[i++] = (char)('0' + v % 10); v /= 10; }
    while (i) putc_(b[--i]);
}

/* Test hook: once, make the high-priority IRQ pending while the low one is mid-pop. */
void preempt_here(void)
{
    if (hook_armed > 0 && in_low) {
        hook_armed--;
        NVIC_ISPR0 = 1u << IRQ_HIGH;
        __asm volatile("dsb; isb");
    }
}

void irq_low_handler(void)  { uint32_t v; in_low = 1; if (q_pop(&q, &v)) { got_low = v;  n_low++;  } in_low = 0; }
void irq_high_handler(void) { uint32_t v;              if (q_pop(&q, &v)) { got_high = v; n_high++; } }

int main(void)
{
    UART_CR = (1u << 0) | (1u << 8);                     /* UARTEN | TXE */
    NVIC_IPR(IRQ_LOW) = 0xE0; NVIC_IPR(IRQ_HIGH) = 0x40;
    NVIC_ISER0 = (1u << IRQ_LOW) | (1u << IRQ_HIGH);
    __asm volatile("cpsie i");

    for (uint32_t i = 1; i <= 3; i++) q_push(&q, i);     /* queue holds 1, 2, 3 */
    hook_armed = 1;
    NVIC_ISPR0 = 1u << IRQ_LOW;                          /* low-priority consumer runs */
    __asm volatile("dsb; isb");

    puts_("high popped "); putu(got_high); puts_(" ("); putu(n_high); puts_(" pop)\n");
    puts_("low popped ");  putu(got_low);  puts_(" ("); putu(n_low);  puts_(" pop)\n");
    puts_("head="); putu(atomic_load(&q.head)); puts_(" tail="); putu(atomic_load(&q.tail)); putc_('\n');
    for (;;) {}
}

start.c supplies the minimum this demo needs before main: _estack (the initial stack pointer, defined by the linker script as the end of RAM), reset (the reset entry that calls main) and the vector table. It does not zero .bss or copy .data; the demo relies on QEMU starting with zeroed RAM, and startup code for a real part must do both. link.ld places that table at the start of flash, the code after it, and the variables in RAM. start.c (vector table, 18 entries, IRQ0 and IRQ1 point at the two handlers; the IRQs are only pended from software, no peripheral is involved):

#include <stdint.h>
extern uint32_t _estack;
int main(void);
void irq_low_handler(void); void irq_high_handler(void);
void reset(void) { main(); for(;;){} }
void dflt(void) { for(;;){} }
__attribute__((section(".vectors"), used))
void (*const vectors[])(void) = {
  (void(*)(void))&_estack, reset, dflt, dflt, dflt, dflt, dflt, 0,0,0,0, dflt, dflt, 0, dflt, dflt,
  irq_low_handler, irq_high_handler,
};

link.ld:

MEMORY { FLASH (rx): ORIGIN = 0, LENGTH = 256K  RAM (rwx): ORIGIN = 0x20000000, LENGTH = 64K }
SECTIONS {
 .text : { KEEP(*(.vectors)) *(.text*) *(.rodata*) } > FLASH
 .data : { *(.data*) } > RAM AT > FLASH
 .bss : { *(.bss*) *(COMMON) } > RAM
 _estack = ORIGIN(RAM) + LENGTH(RAM);
}

run.sh, executed in a --rm gcc:14 container (Debian gcc-arm-none-eabi 14.2.1, QEMU lm3s6965evb, a Cortex-M3 board model):

apt-get update -qq >/dev/null; apt-get install -y -qq qemu-system-arm gcc-arm-none-eabi >/dev/null 2>&1
arm-none-eabi-gcc --version | head -1
F="-mcpu=cortex-m3 -mthumb -O2 -Wall -Wextra -ffreestanding -nostartfiles -nostdlib -T link.ld"
rm -f cas.elf plain.elf
arm-none-eabi-gcc $F demo.c start.c -o cas.elf
arm-none-eabi-gcc $F -DPLAIN demo.c start.c -o plain.elf
echo "--- CAS pop"; timeout 5 qemu-system-arm -M lm3s6965evb -nographic -kernel cas.elf
echo "--- plain pop"; timeout 5 qemu-system-arm -M lm3s6965evb -nographic -kernel plain.elf

Output, deterministic for this scripted scenario:

--- CAS pop
high popped 1 (1 pop)
low popped 2 (1 pop)
head=2 tail=3
--- plain pop
high popped 1 (1 pop)
low popped 1 (1 pop)
head=1 tail=3

Reading it: with the CAS, the high ISR takes item 1 while the low ISR is mid-pop, the low ISR's CAS fails, it retries and takes item 2: each item goes out once and head is 2 after two pops. With q_pop_plain, which does a plain read then a plain store of the head, both ISRs deliver item 1 and head ends at 1 after two pops, so item 1 is duplicated and the second pop's progress is lost. The harness does not use timing: QEMU is not cycle-accurate and cannot show how rare the real race window is, so this demonstrates the logic, not the probability.

What the scripted run does not cover. The hook pends the high-priority interrupt after the slot read and before the ldrex, so the low consumer's CAS fails because head no longer equals h: that exercises the compare-and-retry logic, not the exclusive monitor. No PREEMPT_POINT sits between ldrex and strex. A separate probe covers that window (it reuses start.c and link.ld; the handler names are the ones start.c expects). It does an ldrex, optionally pends IRQ0 so the handler runs right there, then does the strex:

#include <stdint.h>
#define REG(a) (*(volatile uint32_t *)(a))
#define UART_DR    REG(0x4000C000u)
#define UART_CR    REG(0x4000C030u)
#define NVIC_ISER0 REG(0xE000E100u)
#define NVIC_ISPR0 REG(0xE000E200u)

static void putc_(char c) { UART_DR = (uint32_t)c; }
static void puts_(const char *s) { while (*s) putc_(*s++); }
static volatile uint32_t var = 5, isr_ran;

void irq_low_handler(void)  { isr_ran = 1; }   /* touches nothing the probe reads */
void irq_high_handler(void) { }

/* ldrex; (optionally pend IRQ0 so it runs here); strex. Returns the strex status. */
static uint32_t probe(uint32_t pend)
{
    uint32_t val, status;
    __asm volatile(
        "ldrex  %0, [%2]       \n"
        "cmp    %3, #0         \n"
        "beq    1f             \n"
        "str    %5, [%4]       \n"   /* pend IRQ0: it preempts right here */
        "dsb                   \n"
        "isb                   \n"
        "1:                    \n"
        "adds   %0, %0, #1     \n"
        "strex  %1, %0, [%2]   \n"
        : "=&r"(val), "=&r"(status)
        : "r"(&var), "r"(pend), "r"(&NVIC_ISPR0), "r"(1u)
        : "cc", "memory");
    return status;
}

int main(void)
{
    UART_CR = (1u << 0) | (1u << 8);
    NVIC_ISER0 = 1u;
    __asm volatile("cpsie i");
    for (uint32_t pend = 0; pend < 2; pend++) {
        isr_ran = 0;
        uint32_t st = probe(pend);
        puts_(pend ? "interrupt between ldrex and strex: strex status=" : "no interrupt:                      strex status=");
        putc_((char)('0' + st));
        puts_(", handler ran="); putc_((char)('0' + isr_ran)); putc_('\n');
    }
    for (;;) { }
}

Built with the same flags as above and run under QEMU lm3s6965evb (identical at -O0, -O1, -O2 and -Os):

no interrupt:                      strex status=0, handler ran=0
interrupt between ldrex and strex: strex status=1, handler ran=1

The first line is the control: with no interrupt the strex succeeds (status 0), so the second line's failure is caused by the interrupt. The "=&r" constraints mark both asm outputs as early-clobber, so the compiler cannot place the status register in one of the input registers that the strex still needs. This probe is QEMU evidence of the rule quoted above, not a hardware measurement; the manual is the authority for real parts.

Code generated for the CAS pop (arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -O2, GCC 14.2.1, an excerpt, addresses 0x100 to 0x11c, of the objdump of irq_low_handler, which has q_pop inlined; opcode bytes are left out and the comments are added by hand):

 100: add.w  lr, r2, #1        ; lr = h + 1, the new head value
 104: dmb    ish               ; barrier before the exclusive access
 108: ldrex  r0, [r1]          ; load head and mark the address as reserved
 10c: cmp    r0, r2            ; is head still h?
 10e: bne.n  116               ; no: skip the store, the CAS has failed
 110: strex  r5, lr, [r1]      ; store h + 1; r5 = 0 on success, 1 if the reservation was lost
 114: cmp    r5, #0
 116: dmb    ish               ; barrier after the exclusive access
 11a: mov    r2, r0            ; h = the fresh head value
 11c: bne.n  de                ; failed (compare or strex): go round the loop again

The dmb ish (data memory barrier) instructions are how the acquire and release orderings are implemented: a barrier makes memory accesses before it take effect before those after it, as seen by other observers. On this single core no other core observes the queue (a DMA engine that read it would count as an observer), so they cost a few cycles and change no behaviour, which is why they are harmless here and needed if the product moves to a multicore part. q_push has a dmb ish after the head load and another immediately before the tail store.

When to choose something else. If each consumer ISR can have its own queue, use one single-producer single-consumer ring per consumer: no CAS, just a release store on one index per side, and it works on cores without exclusives (Armv6-M parts such as Cortex-M0 lack ldrex/strex; confirm in your core's manual). The shared CAS queue is the right choice when consumers are interchangeable and any one of them may take the next item.

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.

Direct answer

Don't try to average everyone's position into a compromise nobody's happy with. Ground the negotiation in the shared outcome, make the trade-offs between options explicit with evidence, and force a real decision (with an owner and a documented rationale) within a fixed timeframe. A compromise sticks when people can see why it was chosen, not just that it split the difference.

Structured elaboration

1. Reframe around outcome, not position. Ask each stakeholder what success looks like for them, not what they want built. Two stakeholders who seem opposed on the "what" often agree on the "why," which is where the real compromise lives.
2. Bring evidence, not opinions. Gather whatever is available and relevant: usage data, cost/effort estimates, prior incidents, qualitative feedback. A room full of opinions negotiates forever; a room with a shared set of facts converges faster.
3. Make trade-offs visible. Lay out 2-3 real options with their costs and benefits side by side, instead of a single proposal to accept or reject. People compromise more easily when they're choosing between concrete alternatives than when they're being asked to give up a specific ask.
4. Use a structured negotiation move. Propose a balanced default option first, then invite each side to request a bounded concession from it, rather than starting from each side's maximal ask and negotiating down. Time-box the discussion so it doesn't drift into re-litigating the same points.
5. Document the decision and name an owner. Write down what was decided, why, who owns it, and when it will be revisited. If the group truly can't converge, escalate with a specific recommendation rather than an open question, so the escalation itself doesn't become another unresolved debate.
6. Build in a review point. Treat the agreement as provisional and testable, not permanent. A short follow-up (after the next milestone, or a fixed number of weeks) to check whether the compromise is actually working keeps people bought in because they know it isn't final and unappealable.

Worked example

Three stakeholders disagree on scope for a feature: one wants the full version shipped now, one wants it deferred a quarter, one wants a stripped-down version shipped immediately. Instead of negotiating "how much scope," the facilitator asks each what outcome they're protecting: the first is protecting a customer commitment, the second is protecting engineering capacity for other work, the third is protecting the team's ability to learn before over-investing. That reframing surfaces a real option none of them had proposed: ship a narrow version that satisfies the customer commitment, explicitly scoped as a first iteration, with the deferred work logged and re-prioritized at the next planning cycle. The decision, the scope boundary, and the re-prioritization date are written down and shared with all three stakeholders.

Trade-offs & pitfalls

• Pitfall: false compromise, where everyone gets a token piece of what they asked for and the result satisfies no one's actual underlying need.
• Pitfall: skipping documentation. An undocumented "agreement" gets re-argued the moment someone's memory of it differs.
• Pitfall: treating consensus as required. Some decisions need a single accountable owner to make the call after input, not unanimous agreement, especially under a deadline.
• Senior differentiator: designing the forcing function (a default option, a timebox, a named decision owner) instead of facilitating an open-ended discussion indefinitely. That's what turns "several people who each want something different" into an actual decision.