Deadlocks

In real-time and embedded operating systems, multiple tasks often compete for shared resources such as memory buffers, peripherals, or semaphores. A deadlock is a critical system failure condition where two or more tasks are permanently blocked, each waiting for a resource held by the other. Understanding deadlock conditions and prevention strategies is essential for building reliable embedded systems and is a frequently tested topic in GATE examinations.

Core Concept: What is a Deadlock

A deadlock occurs when a set of tasks are each waiting for an event that only another task in the set can trigger. None of the tasks can run, release resources, or make any progress. In embedded and real-time operating systems (RTOS), this is especially dangerous because the system must remain responsive. A deadlocked system will simply stop responding without any visible crash or error message, making it one of the hardest failures to diagnose.

The four Coffman conditions, published in 1971, define the necessary and sufficient conditions for a deadlock to exist. All four must hold simultaneously for deadlock to occur. Removing even one of these conditions prevents deadlock entirely.

The Four Coffman Conditions

1. Mutual Exclusion

At least one resource must be held in a non-shareable mode. Only one task can use the resource at a time. If another task requests that resource, it must wait. In embedded systems, this applies directly to hardware peripherals such as SPI buses, UART, and DMA channels, which cannot be accessed by two tasks simultaneously.

2. Hold and Wait

A task is currently holding at least one resource while simultaneously waiting to acquire additional resources held by other tasks. This condition creates the core accumulation problem in deadlock. If a task releases all held resources before requesting new ones, this condition is broken.

3. No Preemption

A resource cannot be forcibly taken away from the task holding it. Resources can only be released voluntarily by the task after it finishes using them. In an RTOS context, this typically applies to software mutexes and binary semaphores, which must be released explicitly by the owning task.

4. Circular Wait

There exists a circular chain of tasks such that each task holds a resource needed by the next task in the chain. If Task A holds Resource 1 and waits for Resource 2, while Task B holds Resource 2 and waits for Resource 1, a circular wait is formed. This is often visualized as a resource allocation graph containing a cycle.

Mathematical Expression

For a system with N tasks and M resource types, deadlock freedom can be checked using the Banker's algorithm. The key inequality is: if the maximum need of each task is known, the system can determine whether allocating a resource leads to a safe state. A state is safe if there exists a safe sequence in which all tasks can complete. The condition for safe state is:

Available Resources >= Need of at least one task for all task categories in the system. If at any point the remaining available resources cannot satisfy any waiting task's minimum need, the system is in an unsafe state and deadlock may be imminent.

Deadlock Prevention Strategies

Deadlock prevention works by ensuring at least one of the four Coffman conditions cannot hold. Each strategy has tradeoffs in terms of system efficiency and complexity. In RTOS-based embedded systems, the most commonly used strategies are lock ordering and timeout-based acquisition.

• Break Mutual Exclusion: Not always feasible for hardware resources, but for software resources, read-only sharing can eliminate this condition.
• Break Hold and Wait: Require tasks to acquire all needed resources at once before execution begins, or release all held resources before requesting more.
• Allow Preemption: If a task holding resources cannot get additional resources, force it to release all held resources. This requires careful state saving.
• Break Circular Wait: Impose a global ordering on all resources. Tasks must always acquire resources in ascending order of their assigned numbers. This eliminates the possibility of a circular chain.

Practical Understanding

In FreeRTOS and similar RTOS environments, deadlocks most commonly arise through improper use of mutexes and binary semaphores. A common scenario is two tasks each acquiring their own mutex and then trying to acquire the other task's mutex. The system hangs indefinitely with no error output, making debugging difficult.

The most practical prevention technique in embedded systems is lock ordering. Assign a unique integer ID to every mutex in the system. Enforce a strict rule that all tasks must always acquire mutexes in increasing order of ID. This single policy eliminates circular wait without adding runtime overhead.

Timeout-based acquisition is another widely used technique. Instead of blocking indefinitely on a mutex, use a timed wait (for example, xSemaphoreTake with a timeout in FreeRTOS). If the timeout expires, the task releases its held resources and retries after a delay. This introduces livelock risk if not handled carefully, but avoids infinite blocking.

Numerical Example

The Banker's algorithm determines whether a resource allocation is safe. Consider a simplified system with three tasks and one resource type. The goal is to verify whether the current allocation leads to a deadlock or a safe state.

Given:
  Tasks: T1, T2, T3
  Total Resource Instances: 10
  Allocated: T1=2, T2=3, T3=2 → Total Allocated = 7
  Available = 10 - 7 = 3
  Maximum Need: T1=9, T2=5, T3=7
  Remaining Need: T1=7, T2=2, T3=5

Why this formula applies:
  A safe sequence exists if available resources can satisfy
  at least one task's remaining need at each step.

Formula:
  Safe if: Available >= Remaining_Need(Ti) for some Ti at each step

Substitution:
  Step 1: Available=3 >= T2 remaining need=2 → Run T2
          After T2 completes: Available = 3 + 3 = 6
  Step 2: Available=6 >= T3 remaining need=5 → Run T3
          After T3 completes: Available = 6 + 2 = 8
  Step 3: Available=8 >= T1 remaining need=7 → Run T1

Calculation:
  Safe sequence found: T2 → T3 → T1

Final Answer:
  System is in a SAFE STATE. No deadlock will occur.

Exam Tip: GATE problems on deadlock often ask whether a given state is safe using the Banker's algorithm. Always compute remaining need as (Max - Allocated) first, then check if available resources can satisfy any task in sequence. The circular wait condition is the one most commonly tested for identification in resource allocation graphs.

Mechanism Explained

• Lock ordering assigns a numeric ID to every mutex. All tasks must acquire locks strictly in ascending ID order, which mathematically prevents any circular chain from forming.
• Timeout-based acquisition prevents indefinite blocking. If a task cannot acquire a mutex within a defined period, it releases its currently held locks and retries after a backoff delay.
• The Banker's algorithm performs a safety check before each allocation. It grants a resource only if the resulting state has at least one valid completion sequence for all tasks.
• Deadlock detection (rather than prevention) can also be used. The system periodically checks the resource allocation graph for cycles and forces one task to release resources if a cycle is detected.
• In most practical embedded systems, lock ordering combined with short timeout periods is the preferred approach due to its low overhead and deterministic behavior.

Quick Revision

• Deadlock requires all four Coffman conditions simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait.
• Removing any one condition prevents deadlock. The most practical to remove in embedded systems is circular wait via lock ordering.
• Banker's algorithm determines safe state: Available >= Remaining Need for at least one task at every allocation step.
• Remaining Need = Maximum Need minus Currently Allocated.
• A safe sequence guarantees all tasks can complete; an unsafe state does not always mean deadlock has occurred, only that it is possible.
• GATE trap: An unsafe state is not the same as a deadlock state. Deadlock is a subset of unsafe states.
• Timeout-based mutex acquisition is the most common practical prevention in FreeRTOS; Banker's algorithm is used in theoretical OS design.