Introduction to RTOS Part 10 - Deadlock and Starvation | Digi-Key Electronics

Name: Introduction to RTOS Part 10 - Deadlock and Starvation | Digi-Key Electronics
Uploaded: 2021-03-22T13:30:03.000Z
Duration: 24 min 18 s

Dining Philosophers Problem: Understanding Starvation and Deadlock

Introduction to the Dining Philosophers Problem

Five philosophers sit at a round table, each with one chopstick placed between them. They can only eat when they have two chopsticks.

This scenario illustrates the classic dining philosophers problem, which is a metaphor for multiple threads trying to access shared resources in computing.

Importance of the Problem

The dining philosophers problem highlights critical issues in multi-threading: starvation and deadlock.

In this analogy, philosophers represent tasks or threads, chopsticks symbolize semaphores or mutexes, and the bowl of noodles represents shared resources like global variables or serial ports.

Starvation Explained

If higher priority tasks (e.g., Sorawana and Confucius) continuously take chopsticks without yielding, lower priority tasks may starve due to lack of access to resources.

To prevent starvation on single-core systems, high-priority tasks should yield periodically to allow other tasks to run.

Techniques to Prevent Starvation

On multi-core systems, high-priority tasks can be assigned different cores or triggered by interrupts/events for better resource sharing.

Aging is another technique where waiting tasks gradually increase their priority over time if they remain unexecuted. This ensures that all tasks eventually get CPU time.

Deadlock Overview

A simple algorithm where each philosopher picks up one chopstick can lead to deadlock if all hold onto their left chopstick without being able to pick up the right one.

Deadlock occurs when no philosopher can proceed because they are all waiting for a resource held by another philosopher.

Best Practices Against Deadlock

Implementing best practices in concurrent programming helps prevent deadlocks. For example, ensuring that task priorities are managed effectively during mutex acquisition.

A practical example involves two tasks taking two mutexes; introducing delays can force deadlocks for demonstration purposes but also highlights potential bugs in real applications.

Conclusion on Managing Resources

Understanding Deadlock and Livelock in Concurrency

The Problem of Deadlock

A deadlock occurs when two tasks are waiting on each other to release resources, preventing both from continuing. This highlights the risks associated with using multiple mutexes and semaphores.

To prevent deadlocks, it's crucial to avoid having a task block indefinitely while waiting for a mutex or semaphore. Implementing timeouts can help manage this issue effectively.

Implementing Timeouts

By creating a timeout (e.g., 1 second) for tasks attempting to acquire a mutex, if a task times out, it releases any held mutexes and retries after a delay. This allows one task to proceed if another is blocked.

However, timeouts do not eliminate all concurrency issues; they can lead to livelock where tasks continuously retry without making progress due to synchronized timeouts.

Solutions for Deadlock and Livelock

Dijkstra's Solution: Hierarchical Resource Allocation

Dijkstra proposed assigning priorities or numbers to resources (chopsticks). Philosophers pick up the lower-numbered chopstick first, ensuring that at least one philosopher can eat without blocking others.

In this scenario, only one chopstick remains unpicked at any time, allowing other philosophers access sequentially and preventing deadlocks.

Implementation of Mutex Order

When coding this solution, it's good practice to release mutexes in reverse order of acquisition. This maintains consistency and reduces complexity in resource management.

Both tasks should acquire the same order of mutexes (e.g., always acquiring mutex 1 before mutex 2), mirroring the hierarchical approach used by philosophers.

Introducing an Arbitrator

Another method involves using an arbitrator (like a waiter), which grants permission for tasks to access shared resources. This ensures that only one task operates at any given moment.

While effective in preventing deadlocks, this approach limits parallel execution since it serializes access to resources.

The Dining Philosophers Challenge

The challenge involves implementing both hierarchical allocation and arbitrator solutions within an Arduino sketch simulating five philosophers trying to eat without encountering deadlock.

Participants must ensure that all philosophers get their chance without falling into deadlock scenarios while managing delays intentionally included in the code for testing purposes.