Project 6: Mutexes and Priority Inversion Demo

Implement mutexes and priority inheritance, then demonstrate and fix priority inversion on real hardware.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Main Programming Language C
Alternative Programming Languages Rust, Ada
Coolness Level Very High
Business Potential High
Prerequisites Projects 1-5, preemptive scheduler, task priorities
Key Topics Mutexes, priority inversion, priority inheritance, blocking semantics

1. Learning Objectives

By completing this project, you will:

  1. Implement a mutex with ownership tracking.
  2. Demonstrate priority inversion with three tasks.
  3. Implement priority inheritance to fix inversion.
  4. Validate correctness with timing measurements.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Mutexes, Ownership, and Blocking Semantics

Fundamentals

A mutex is a mutual exclusion lock that allows only one task to access a shared resource at a time. Unlike a binary semaphore, a mutex has ownership: only the task that acquired it can release it. In an RTOS, locking a mutex can block a task, changing its state to BLOCKED until the mutex becomes available. Correct mutex behavior prevents data races and ensures consistent access to shared resources.

Additional fundamentals: Mutexes exist because shared data is unavoidable. The goal is to serialize access without turning every shared operation into a long critical section. Ownership tracking makes mutexes safer than semaphores for protecting resources, because it prevents unrelated tasks from accidentally releasing a lock they do not hold.

Deep Dive into the concept

Mutex design in an RTOS must account for task states, ownership, and priority. The simplest mutex is a binary flag, but without ownership it cannot prevent a different task from unlocking it. Ownership is tracked by storing the current owner in the mutex structure. When a task tries to lock an already-owned mutex, it should block, and the scheduler should switch to another READY task. This requires integration with the scheduler: the mutex must maintain a wait queue or wait list of blocked tasks.

Blocking semantics introduce ordering questions. Should tasks be unblocked in FIFO order, priority order, or something else? Priority order is common in RTOS systems because it preserves responsiveness for high-priority tasks. However, FIFO ordering is simpler and can be acceptable if tasks have similar priorities. For this project, you can implement a simple priority-based wait queue to align with the scheduler’s priorities.

Mutexes also need to handle recursion. A recursive mutex allows the same task to lock multiple times, incrementing a count, and requires an equal number of unlocks. A non-recursive mutex will deadlock if the owner tries to lock again. Many RTOSes support both, but for this project you can either disallow recursion (and assert) or implement a simple recursion counter. The critical part is to define behavior clearly.

Another subtlety is lock/unlock from ISRs. Generally, mutexes are not ISR-safe because blocking inside an ISR is impossible. Therefore, your mutex API should explicitly state that it is task-only. If an ISR needs to signal a task, it should use a semaphore or queue instead. Being explicit about this restriction prevents a class of hard-to-debug faults.

Mutex correctness can be validated by stress testing. If you have two tasks incrementing a shared counter, the counter should be consistent only when protected by a mutex. Without it, you can demonstrate race conditions. This project goes further by showing how mutexes interact with priorities, which leads to priority inversion. But before tackling inversion, the mutex itself must be correct and deterministic.

Additional depth: Mutex design must account for the interaction between locking and scheduling. When a task blocks on a mutex, it should be removed from the READY list and placed in the mutex wait list. This requires careful ordering to avoid race conditions with interrupts. In a preemptive system, an ISR might also attempt to wake tasks or change states, so mutex operations should be protected by critical sections. It is also important to decide whether a task can lock a mutex from within a critical section, because if you disable interrupts and then block, you can deadlock the system. The simplest rule is: never block while interrupts are disabled. Your mutex implementation should enforce this or at least document it.

Mutex fairness is another consideration. A FIFO wait list is fair but may allow a lower-priority task to acquire the mutex before a higher-priority one, which can reduce responsiveness. A priority-based wait list is better for real-time systems because it aligns with scheduling priorities. The tradeoff is complexity: you must insert tasks into the wait list in priority order. For this project, this is manageable and aligns with the goal of demonstrating priority inversion.

You should also consider error handling. What happens if a task tries to unlock a mutex it does not own? In a production RTOS, this often triggers an assertion or error callback. For a learning kernel, you can choose to return an error code or halt the system. The important thing is to make the behavior deterministic and visible. Silent failure can lead to subtle data corruption.

Finally, mutexes are a good place to integrate tracing. Logging lock and unlock events, along with task IDs and priorities, gives you visibility into synchronization behavior. This logging should be done carefully to avoid changing timing too much. A common approach is to log into a fixed-size buffer and print later from a low-priority task. This kind of instrumentation will help you verify that your mutex semantics are correct and will be useful in later performance analysis.

How this fit on projects

Mutex locking is implemented in Sec. 3.1 and used in the inversion demo (Sec. 3.7.2). The mutex structure is referenced in Project 7 when comparing ISR-safe primitives.

Definitions & key terms

  • Mutex: Mutual exclusion lock with ownership.
  • Owner: Task currently holding the mutex.
  • Wait queue: List of tasks blocked on the mutex.
  • Recursive mutex: Allows same task to lock multiple times.

Mental model diagram (ASCII)

Task A locks -> mutex owner = A -> Task B blocks -> Task A unlocks -> Task B wakes

How it works (step-by-step, with invariants and failure modes)

  1. Task calls mutex_lock.
  2. If mutex free, set owner and continue.
  3. If owned, block task and add to wait queue.
  4. Owner unlocks; highest priority waiter becomes owner.
  5. Failure mode: unlocking by non-owner corrupts state.

Minimal concrete example

typedef struct {
    tcb_t *owner;
    uint8_t locked;
} mutex_t;

void mutex_lock(mutex_t *m) {
    enter_critical();
    if (!m->locked) { m->locked = 1; m->owner = current; }
    else { block_current_on_mutex(m); }
    exit_critical();
}

Common misconceptions

  • “Mutex and semaphore are the same” -> mutex has ownership; semaphore does not.
  • “Unlocking from ISR is fine” -> ISRs cannot block or own mutexes.
  • “Recursive locks always safe” -> they can hide deadlocks and logic errors.

Check-your-understanding questions

  1. Why must mutexes track ownership?
  2. What should happen if a task tries to lock its own mutex again?
  3. Why are mutexes typically not ISR-safe?

Check-your-understanding answers

  1. To prevent non-owners from unlocking and corrupting state.
  2. Either block (deadlock) or allow recursion with a count; define behavior.
  3. ISRs cannot block and should not hold locks.

Real-world applications

  • Shared bus access (SPI/I2C) in firmware.
  • Protecting logging buffers or shared state in RTOS tasks.

Where you’ll apply it

  • This project: Sec. 3.1, Sec. 3.7.2, Sec. 5.10 Phase 1.
  • Also used in: Project 6 and Project 7.

References

  • “Real-Time Concepts for Embedded Systems” by Qing Li, Ch. 6.
  • FreeRTOS mutex implementation docs.

Key insights

Mutexes are more than locks; they encode ownership and task scheduling behavior.

Summary

Correct mutex behavior prevents data races and forms the basis for safe synchronization in an RTOS.

Homework/Exercises to practice the concept

  1. Implement a simple mutex and test with two tasks incrementing a counter.
  2. Add a wait queue and unblock tasks in priority order.
  3. Add a recursion count and decide behavior on recursive lock.

Solutions to the homework/exercises

  1. Compare counter result with and without mutex protection.
  2. Sort waiters by priority and wake highest first.
  3. Increment count on lock and decrement on unlock; release when zero.

2.2 Priority Inversion and Priority Inheritance

Fundamentals

Priority inversion occurs when a low-priority task holds a mutex needed by a high-priority task, while a medium-priority task preempts the low-priority task, delaying the high-priority task. This can break real-time deadlines. Priority inheritance is a mitigation technique: when a high-priority task blocks on a mutex, the mutex owner temporarily inherits the higher priority to finish its work and release the mutex.

Additional fundamentals: Priority inversion is a direct threat to real-time guarantees. If a high-priority task can be blocked indefinitely by lower-priority work, the system is no longer predictable. Understanding this failure mode is essential before you can claim your RTOS is suitable for real-time workloads.

Deep Dive into the concept

Priority inversion is not a theoretical corner case; it famously caused failures in real systems, including the Mars Pathfinder mission. In an RTOS with priorities, the scheduler always runs the highest-priority READY task. Suppose Task L (low) holds a mutex, Task H (high) blocks on it, and Task M (medium) is READY. Without inheritance, Task M will run and preempt Task L, preventing it from releasing the mutex. Task H remains blocked, even though it has the highest priority. This inversion can last as long as Task M runs, and if Task M runs frequently, Task H can be delayed indefinitely.

Priority inheritance resolves this by boosting Task L’s priority to that of Task H when Task H blocks on the mutex. This causes Task L to preempt Task M, finish its critical section, and release the mutex quickly. Once the mutex is released, Task L’s priority is restored to its original value, and Task H becomes READY again. Implementing this requires the mutex to track the highest priority of tasks waiting on it and to propagate that priority to its owner. If a task holds multiple mutexes, inheritance must consider all waiting tasks across them; for this project, a simplified single-mutex case is acceptable, but you should note the limitation.

Priority inheritance is not free. It adds complexity and can cause temporary priority inflation, which can affect other scheduling decisions. It also does not prevent deadlocks; if two tasks lock mutexes in opposite order, they can still deadlock. Another nuance is that inheritance should only apply to mutexes, not semaphores, because semaphores are not owned. This is why mutexes exist as a distinct primitive in RTOS designs.

Implementation details matter. You must store the original priority of the owner so you can restore it after unlocking. You also must handle nested inheritance if multiple high-priority tasks block on the same owner. A simple approach is to set the owner priority to the highest waiting priority and recompute on unlock. In a small system, this is sufficient. The key is to demonstrate the behavior with a reproducible scenario and verify that inheritance fixes the inversion.

Additional depth: Priority inheritance has limitations that you should understand to avoid overconfidence. It addresses only the case where a low-priority owner blocks a higher-priority task. It does not prevent deadlock, and it does not solve unbounded priority inversion caused by multiple locks in complex graphs. More advanced protocols like priority ceiling or stack resource policy (SRP) provide stronger guarantees but are more complex to implement. In this project, a single-mutex inheritance model is enough, but you should document that nested locks are not fully supported.

Implementation details matter: if a task holds multiple mutexes and multiple higher-priority tasks block on different mutexes, the owner should inherit the highest of those priorities. If you only store one inherited priority, you might restore to the wrong value when one mutex is released. A simple approach is to compute the highest waiting priority each time a mutex is unlocked and set the owner’s priority to the maximum of the remaining waiters. This is O(n) but sufficient for small systems. The key is to avoid leaving the task boosted after it no longer needs to be.

Priority inheritance can also interact with time slicing. If your scheduler uses time slices within a priority level, a boosted task might still share CPU time with other tasks of the same priority, delaying the release of the mutex. This can reduce the effectiveness of inheritance. In many RTOSes, a boosted task is treated as the highest priority and should run immediately. In your kernel, you can implement this by rescheduling immediately after boosting and by placing the boosted task at the head of its priority queue.

Finally, demonstrating priority inversion convincingly requires a deterministic experiment. Use GPIO toggles or timestamps to show exactly when each task runs and how long the high-priority task is blocked. Without clear evidence, it is easy to misinterpret the behavior. A reproducible timeline is also useful in interviews and documentation because it shows that you understand not just the theory but the practical system behavior.

How this fit on projects

Priority inheritance is implemented in Sec. 3.1 and demonstrated in Sec. 3.7.2. It connects directly to Project 4 because it relies on priority scheduling.

Definitions & key terms

  • Priority inversion: High-priority task blocked by lower-priority task due to a mutex.
  • Priority inheritance: Temporarily boosting owner priority to that of waiting task.
  • Priority ceiling: Alternative protocol that pre-boosts priority.

Mental model diagram (ASCII)

Without inheritance:
H waits -> L holds mutex -> M runs -> H delayed
With inheritance:
H waits -> L inherits H priority -> L runs -> releases -> H runs

How it works (step-by-step, with invariants and failure modes)

  1. Task H blocks on mutex held by Task L.
  2. Owner L inherits H’s priority.
  3. Scheduler runs L over M.
  4. L releases mutex; priority restored.
  5. Failure mode: forgetting to restore priority.

Minimal concrete example

void mutex_lock(mutex_t *m) {
    if (m->locked && m->owner != current) {
        if (current->priority > m->owner->priority) {
            m->owner->priority = current->priority; // inherit
        }
        block_current_on_mutex(m);
    }
}

Common misconceptions

  • “Priority inheritance prevents deadlocks” -> it only addresses inversion.
  • “Inheritance should apply to semaphores” -> semaphores have no owner.
  • “Boosting priority is always safe” -> it can affect unrelated tasks.

Check-your-understanding questions

  1. Why does priority inversion occur in preemptive systems?
  2. How does inheritance restore system responsiveness?
  3. What happens if you forget to restore the owner’s priority?

Check-your-understanding answers

  1. A medium-priority task preempts the low-priority mutex owner.
  2. It boosts the owner’s priority so it can run and release the mutex.
  3. The owner remains at high priority and can starve others.

Real-world applications

  • Safety-critical systems that must meet deadlines.
  • Aerospace and automotive kernels using priority inheritance or ceiling.

Where you’ll apply it

  • This project: Sec. 3.1, Sec. 3.7.2, Sec. 5.10 Phase 2.
  • Also used in: Project 4.

References

  • “Real-Time Concepts for Embedded Systems” by Qing Li, Ch. 15.
  • Mars Pathfinder priority inversion incident reports.

Key insights

Priority inheritance is a targeted fix for a specific scheduling failure mode, not a general concurrency solution.

Summary

Priority inversion can destroy real-time guarantees; priority inheritance is the standard remedy in RTOS kernels.

Homework/Exercises to practice the concept

  1. Simulate three tasks and draw the inversion timeline.
  2. Implement inheritance and measure how long Task H waits.
  3. Compare inheritance vs no inheritance in GPIO timing logs.

Solutions to the homework/exercises

  1. Show Task M preempting Task L while H waits.
  2. Measure wait time reduction after inheritance.
  3. GPIO trace should show faster H response with inheritance.

3. Project Specification

3.1 What You Will Build

A mutex implementation with ownership tracking and priority inheritance, plus a demonstration program with three tasks (low, medium, high) that shows priority inversion and its resolution.

3.2 Functional Requirements

  1. Mutex Lock/Unlock: Only owner can unlock.
  2. Blocking Behavior: Tasks block when mutex owned.
  3. Priority Inheritance: Owner temporarily boosted when higher-priority task blocks.

3.3 Non-Functional Requirements

  • Performance: Mutex lock/unlock < 20 us.
  • Reliability: No deadlocks in the demo scenario.
  • Usability: Inversion visible via UART or GPIO timestamps.

3.4 Example Usage / Output

  • UART logs show Task H blocked until mutex released.
  • With inheritance, Task H runs sooner and logs reduced latency.

3.5 Data Formats / Schemas / Protocols

  • Mutex struct: {owner, locked, waiting_list}.

3.6 Edge Cases

  • Task tries to unlock without owning.
  • Recursive lock attempt (if not supported).
  • Multiple tasks waiting with different priorities.

3.7 Real World Outcome

You can reproduce priority inversion and then eliminate it with priority inheritance, proving your kernel protects deadlines under contention.

3.7.1 How to Run (Copy/Paste)

make clean all
make flash

Exit codes:

  • make: 0 success, 2 build failure.
  • openocd: 0 flash success, 1 connection failure.

3.7.2 Golden Path Demo (Deterministic)

  1. Task L locks mutex and performs a long loop.
  2. Task H tries to lock and blocks.
  3. Task M runs and delays Task L (inversion visible).
  4. Enable inheritance; Task L boosts and runs, releasing mutex.

3.7.3 Failure Demo (Deterministic)

  1. Disable inheritance logic.
  2. Observe Task H blocked for long duration while Task M runs.
  3. Re-enable inheritance and verify reduced delay.

4. Solution Architecture

4.1 High-Level Design

Task H -> mutex_lock -> block -> owner inherits -> owner runs -> unlock

4.2 Key Components

Component Responsibility Key Decisions
mutex.c Lock/unlock and wait queue Priority order vs FIFO
sched.c Apply inherited priority Restore on unlock
demo.c Task scenarios and measurement UART vs GPIO logging

4.4 Data Structures (No Full Code)

typedef struct {
    tcb_t *owner;
    uint8_t locked;
    uint8_t owner_orig_prio;
} mutex_t;

4.4 Algorithm Overview

Key Algorithm: Inheritance

  1. If lock is owned, compare priorities.
  2. If waiting task higher, boost owner.
  3. On unlock, restore owner priority and wake highest waiter.

Complexity Analysis:

  • Time: O(n) if searching wait list.
  • Space: O(n) for wait list.

5. Implementation Guide

5.1 Development Environment Setup

brew install arm-none-eabi-gcc openocd

5.2 Project Structure

rtos-p06/
|-- src/
|   |-- mutex.c
|   |-- demo.c
|   `-- main.c
|-- include/
`-- Makefile

5.3 The Core Question You’re Answering

“How do I prevent a low-priority task from blocking a high-priority deadline?”

5.4 Concepts You Must Understand First

  1. Mutex ownership and blocking behavior.
  2. Priority inversion and inheritance.

5.5 Questions to Guide Your Design

  1. How will you store the owner’s original priority?
  2. What order should blocked tasks be woken?
  3. How will you demonstrate inversion with timing traces?

5.6 Thinking Exercise

Draw a timeline with three tasks and show how inheritance changes the order.

5.7 The Interview Questions They’ll Ask

  1. “What is priority inversion?”
  2. “How does priority inheritance work?”
  3. “Why are mutexes different from semaphores?”

5.8 Hints in Layers

Hint 1: Implement basic mutex first Verify correctness before adding inheritance.

Hint 2: Add a simple wait queue Wake the highest-priority waiter.

Hint 3: Measure with GPIO Toggle pins on lock/unlock to visualize delays.

5.9 Books That Will Help

Topic Book Chapter
Mutexes and inversion “Real-Time Concepts for Embedded Systems” Ch. 6,15
RTOS scheduling “Making Embedded Systems” Ch. 6

5.10 Implementation Phases

Phase 1: Basic Mutex (3-4 days)

Goals: Implement ownership and blocking. Tasks: Lock/unlock, wait queue. Checkpoint: Shared counter protected correctly.

Phase 2: Inversion Demo (2-3 days)

Goals: Reproduce inversion with three tasks. Tasks: Create L/M/H tasks, log timing. Checkpoint: High task blocked by medium task.

Phase 3: Inheritance Fix (3-4 days)

Goals: Add priority inheritance. Tasks: Boost owner, restore on unlock. Checkpoint: High task latency reduced.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Wait queue order FIFO vs priority Priority Preserves real-time responsiveness
Inheritance scope Single vs nested Single Simpler for learning

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |——————|——————————–|———————————-| | Unit Tests | Mutex correctness | Owner unlock validation | | Integration Tests | Inversion scenario | L/M/H timing trace | | Edge Case Tests | Recursive lock attempt | Expect assert or error |

6.2 Critical Test Cases

  1. Non-owner unlock triggers error handling.
  2. Inheritance reduces high-priority wait time.
  3. Mutex locks/unlocks 10,000 times without corruption.

6.3 Test Data

Expected: High task wait time reduced by >50% with inheritance

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——————————|——————————|————————————| | No owner tracking | Random unlocks | Store and check owner | | Priority not restored | Owner stays boosted | Save original priority | | Blocking in ISR | System deadlock | Restrict mutex to tasks |

7.2 Debugging Strategies

  • Log priority changes over UART.
  • Toggle GPIO on lock/unlock for timing visibility.

7.3 Performance Traps

  • O(n) wait queue scans can be costly with many tasks.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add recursive mutex support.
  • Add a mutex timeout API.

8.2 Intermediate Extensions

  • Implement priority ceiling protocol.
  • Add instrumentation for wait times.

8.3 Advanced Extensions

  • Support nested inheritance across multiple mutexes.
  • Add deadlock detection for common patterns.

9. Real-World Connections

9.1 Industry Applications

  • Automotive and aerospace RTOS kernels.
  • Industrial control systems with priority constraints.
  • FreeRTOS: Mutexes with priority inheritance.
  • ThreadX: Priority inheritance and ceiling.

9.3 Interview Relevance

  • Priority inversion is a classic embedded interview scenario.

10. Resources

10.1 Essential Reading

  • “Real-Time Concepts for Embedded Systems” by Qing Li.

10.2 Video Resources

  • Priority inversion case studies and demos.

10.3 Tools & Documentation

  • Logic analyzer for timing visualization.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain priority inversion and inheritance.
  • I understand why mutex ownership is required.

11.2 Implementation

  • Mutexes block and wake tasks correctly.
  • Inheritance fixes inversion in the demo.

11.3 Growth

  • I can explain when to use a mutex vs a semaphore.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Mutex lock/unlock works with ownership checks.
  • Inversion scenario reproducible.

Full Completion:

  • Priority inheritance implemented and validated.
  • Timing evidence documented.

Excellence (Going Above & Beyond):

  • Priority ceiling protocol implemented.
  • Deadlock detection added for common patterns.