State Machines & Protocol Implementation Questions

What is a ring buffer (circular buffer)
A ring buffer is a fixed-size array used as a FIFO where head (write) and tail (read) indexes advance and wrap to 0 when they hit the end. It stores streaming data without reallocations.

Typical embedded uses (concrete examples)

• UART + DMA RX: DMA writes bytes into a circular buffer; firmware advances tail to consume bytes when parsing frames. No mallocs, predictable latency.
• Audio sample buffering: Continuous ADC samples are pushed at ISR time; playback reads from buffer at audio interrupt rate, smoothing producer/consumer rate differences.
• Sensor logs, telemetry queues, inter-task message passing in RTOS.

Head/tail behavior & wrap-around

• head = index where next byte is written; tail = index where next byte is read.
• After increment: if (idx == size) idx = 0; (wrap-around)
• Full vs empty: common rule is keep one slot free or track count/overrun flag.
  • empty when head == tail (and count == 0)
  • full when (head + 1) % N == tail (one-slot-reserved)
• Increment atomically or with IRQ/lock to avoid races.

Advantages vs linked lists / dynamic arrays

• Predictable memory: single static array, no fragmentation.
• Low CPU: O(1) push/pop with simple index math.
• Deterministic timing and small code size—critical for constrained MCUs.
• Better cache locality than linked lists.

Implementation notes / pitfalls

• Use power-of-two size to replace modulo with bitmask: idx = (idx + 1) & (N-1).
• Handle overruns: set an error flag or drop oldest/newest per policy.
• Ensure atomic updates between ISR and main context (disable IRQs or use atomic counters).

What a watchdog timer (WDT) is
A WDT is hardware (or sometimes software) timer that forces a system reset if not periodically "kicked" within a configured window. It protects against hangs, live-locks, and certain classes of software faults.

How it improves resilience

• Forces recovery from unresponsive states when normal control flow is lost.
• Acts as last-resort fail-safe when other error handling fails.
• Combined with safe boot and diagnostics, it enables autonomous recovery in field devices.

Safe usage patterns

• Kick from a single, well-defined place (e.g., system supervisor or main control loop) — not scattered across code.
• Use a windowed watchdog when available to detect both stalls and runaway tasks.
• Feed only after completing health checks: scheduler alive, watchdog task heartbeat, memory/stack checks.
• On reset, perform minimal early initialization, check a persistent boot counter or CRCed state, and avoid automatic destructive actions until diagnostics run.
• Use non-volatile logs (with CRC) to record cause of reset and avoid blind loops; limit boot-loop retries with exponential backoff.

Example (C-style supervisor):

// called from main loop or supervisor task
void supervisor_tick(void) {
  if (health_checks_pass()) {
    watchdog_kick();
  } else {
    // log error, attempt controlled recovery
    attempt_recovery();
    // if unrecoverable, let WDT reset
  }
}

How to avoid masking real faults

• Never kick the WDT from ISRs or from many unrelated modules — this hides faults in main code.
• Ensure health_checks verify core subsystems (scheduler, comms, sensors).
• Prefer letting the WDT reset for unrecoverable faults instead of masking by naive kicks.

Common pitfalls

• Resetting without flushing persistent state: losing telemetry/config. Mitigate by atomic writes, journaling, or writing a shutdown marker before critical ops.
• Clearing watchdog prematurely in error paths: e.g., error handler that loops and keeps kicking. Instead, fail fast or escalate.
• Assuming WDT fixes logic bugs: it only recovers from stuck states; bugs causing repeated bad behavior after boot must be addressed (use counters, safe-mode).
• Boot loops: track reset count in RTC/NV and change behavior after N resets (enter safe mode or remote update).

Use WDT as a disciplined fail-safe integrated with health checks, persistent diagnostics, and boot protections to improve system resilience without hiding root causes.

FSM fundamentals (brief)

• An FSM = finite set of states, inputs/events, transitions, and outputs. At any time the machine is in one state; inputs trigger transitions possibly changing state and producing outputs. Useful in embedded systems for predictable control, low memory, and timing.

Mealy vs Moore

• Mealy: outputs = function(state, input). Faster reactions (can change output immediately on input) and fewer states.
• Moore: outputs = function(state) only. Outputs stable on state entry, simpler timing and easier to test; may need more states.

Embedded example — Button debounce FSM (Moore-style)

• States:
  • IDLE (released)
  • BOUNCE_DETECT (possible change)
  • PRESSED (confirmed)
  • RELEASE_DETECT
• Events / transitions:
  • input = sampled_gpio_high/low; timer expiry (debounce timeout)
  • IDLE + gpio_high -> BOUNCE_DETECT (start timer)
  • BOUNCE_DETECT + timer_expired and gpio still high -> PRESSED
  • PRESSED + gpio_low -> RELEASE_DETECT (start timer)
  • RELEASE_DETECT + timer_expired and gpio still low -> IDLE
• Entry/Exit actions:
  • Enter BOUNCE_DETECT: start debounce timer (entry action)
  • Exit BOUNCE_DETECT: stop timer (exit action)
  • Enter PRESSED: latch press timestamp (entry)
• Outputs:
  • In Moore: output asserted while in PRESSED state (e.g., debounced_button = 1)
  • In Mealy variant: produce a single pulse output on transition BOUNCE_DETECT -> PRESSED

Why explicitness matters

• Define states for testability and power/CPU budgeting; choose Mealy for lower latency pulses, Moore for deterministic timing and simpler hardware-timed outputs.

Overview / goal
I would implement a small, deterministic FSM that decodes framed, byte‑stuffed packets (0x7E delimiter, 0x7D escape + XOR 0x20) while tolerating noise, misalignment, and partial buffers. The parser must stream bytes into a consumer buffer with minimal RAM and fast resynchronization.

States

• IDLE: waiting for 0x7E start. Ignore all other bytes.
• IN_FRAME: collecting payload bytes into consumer buffer until 0x7E seen.
• ESCAPE: last byte was 0x7D; next incoming byte is XORed with 0x20 and appended.
• DISCARD: frame being dropped due to error (overflow, invalid escape); wait for next 0x7E to re-enter IN_FRAME.

Actions per state

• IDLE: on 0x7E -> transition to IN_FRAME and reset length; else remain.
• IN_FRAME:
  • 0x7E -> if length>0, emit complete frame to consumer; stay in IN_FRAME (handles back-to-back frames).
  • 0x7D -> transition to ESCAPE.
  • normal byte -> append if space; on overflow -> set error, transition to DISCARD.
• ESCAPE:
  • if byte present -> decoded = byte ^ 0x20; append if space; transition to IN_FRAME.
  • if unexpected (e.g., EOF) -> handle as partial; transition accordingly.

Error handling

• Buffer overflow: move to DISCARD; increment drop counters; continue scanning for next 0x7E.
• Invalid escape (e.g., missing byte): treat as corrupted frame; DISCARD until 0x7E.
• Corrupted frame detection: optional CRC check performed on emit; if CRC fails, record error and continue.

Resynchronization strategy

• Always treat 0x7E as strong resync marker. In DISCARD or after error, scan incoming stream for next 0x7E; upon seeing it, start new IN_FRAME.
• Support streaming chunks: maintain current state across buffer boundaries so partial escape or partial frame resumes correctly.
• To handle run‑in noise (many non-0x7E bytes), IDLE simply ignores until delimiter—cheap and fast.

Memory & performance

• Single small fixed-size ring or linear buffer sized to max expected frame (no dynamic allocation).
• Minimal state (enum + index + counters). Append-only writes; consumer reads completed frames or processes bytes incrementally (callback) to avoid large buffering.

Example robustness tweaks

• If high noise causes frequent single 0x7E spurious bytes, require minimal frame length or CRC to accept frames.
• Expose counters for drops, escapes, and CRC failures for telemetry and adaptive tuning.

Definition & Why it matters

Deterministic behavior in embedded systems means that given the same inputs and timing, the system’s execution times and observable outputs are predictable and bounded. For real-time (especially hard real-time) applications this ensures deadlines are always met — we can compute a worst-case execution time (WCET) and guarantee correctness under timing constraints.

Example of runtime non-determinism

• Dynamic memory allocation (malloc/free) can introduce unbounded latency due to fragmentation, locking, or variable-time algorithms. This causes unpredictable response times and breaks WCET guarantees.

Mitigation strategy

• Eliminate dynamic allocation at run-time: use static allocation for buffers, objects, and data structures.
• Use fixed-size memory pools (object pools) with O(1) allocation/free; pre-allocate at init.
• If allocator needed, use a real-time allocator with worst-case bounds and lock-free or per-thread heaps.
• Complement with instrumentation: measure WCET, run stress tests, and perform stack/heap usage analysis.

Other practices

• Keep ISRs short and bounded; defer work to prioritized threads (bottom halves).
• Use priority inheritance/protection to avoid priority inversion.
• Configure interrupt rate limiting and analyze worst-case interrupt arrival to include in schedulability analysis.

These steps remove unbounded latencies and make WCET estimations reliable for hard real-time guarantees.