VIDEO
HIGHLIGHT
Log InSign up
Introduction to RTOS Part 10 - Deadlock and Starvation | Digi-Key Electronics
SummaryTranscriptChat

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

¿Cuál es el problema de los filósofos comensales?

Introducción al Problema

  • Cinco filósofos entran a un restaurante y se sientan en una mesa redonda, donde cada uno tiene un solo palillo entre ellos.
  • Cada filósofo necesita dos palillos para comer, lo que plantea el desafío de crear un algoritmo que garantice que todos tengan tiempo para comer.

Importancia del Problema

  • Este problema es una analogía para múltiples hilos con múltiples bloqueos intentando acceder a un recurso compartido.
  • Se abordarán dos problemas importantes: la inanición (starvation) y el bloqueo (deadlock), que pueden causar serios problemas en programas multihilo.

Inanición y Bloqueo: Definiciones y Soluciones

Inanición

  • En la analogía, algunos filósofos (hilos de alta prioridad) pueden monopolizar los palillos, dejando a otros sin acceso. Esto se conoce como inanición.
  • Para prevenir la inanición, se sugiere introducir retrasos o ceder el control al programador para permitir que otros hilos se ejecuten.

Técnicas para Prevenir Inanición

  • En sistemas multicore, las tareas de alta prioridad pueden ejecutarse en núcleos diferentes o activarse mediante interrupciones.
  • La técnica de envejecimiento (aging) permite aumentar gradualmente la prioridad de las tareas en espera, asegurando que eventualmente obtengan tiempo de CPU.

Bloqueo: Un Problema Crítico

Algoritmo Simple y sus Consecuencias

  • Un algoritmo simple donde cada filósofo toma primero su palillo izquierdo puede llevar a un estado de bloqueo si todos intentan hacerlo simultáneamente.
  • El bloqueo ocurre cuando todos los filósofos sostienen su palillo izquierdo pero no pueden tomar el derecho, quedando atrapados sin poder comer.

Prevención del Bloqueo

  • Se presentan técnicas consideradas mejores prácticas en programación concurrente para evitar bloqueos.

Prevención de Deadlocks en Sistemas Concurrentes

Introducción a los Deadlocks

  • Se explica cómo el uso de múltiples mutexes y semáforos puede llevar fácilmente a un deadlock, donde ninguna tarea puede continuar.
  • Para prevenir o detectar deadlocks, es crucial no permitir que una tarea se bloquee indefinidamente al esperar un mutex o semáforo. Se sugiere implementar un tiempo de espera (timeout).

Implementación de Timeouts

  • Al establecer un timeout de 1 segundo para la adquisición de mutexes, si una tarea excede este tiempo, imprime un mensaje de error y libera cualquier mutex adquirido.
  • Aunque los timeouts ayudan a evitar deadlocks totales, pueden dar lugar a otro problema conocido como "live lock", donde las tareas no están bloqueadas pero tampoco pueden avanzar.

Soluciones Propuestas para Deadlocks y Live Locks

  • Se presentan soluciones para abordar los problemas de deadlock y live lock. Una solución implica asignar una jerarquía o prioridad a los recursos compartidos (chopsticks).
  • En esta solución, cada filósofo comienza tomando el chopstick con el número más bajo. Esto evita que todos intenten tomar el mismo recurso simultáneamente.

Ejemplo Práctico con Mutexes

  • La implementación del algoritmo muestra que solo uno de los chopsticks queda disponible en la mesa, permitiendo que otros filósofos continúen comiendo sin entrar en deadlock.
  • Es importante liberar los mutexes en orden inverso al que fueron adquiridos como buena práctica, aunque no afecta directamente al algoritmo.

Introducción del Arbitraje

  • Otra solución es introducir un "arbitro" que determine quién puede acceder a los recursos compartidos. Este arbitro actúa como un mutex adicional.
  • El arbitro permite que solo una tarea acceda a ambos chopsticks a la vez, lo cual previene el deadlock pero limita la ejecución paralela.

Desafío Final: Filósofos Comensales

  • Se presenta el desafío completo del problema de los filósofos comensales utilizando cinco tareas en lugar de dos. Cada filósofo intenta tomar sus chopsticks y comer.
Playlists: Introduction to RTOS
Video description

Starvation and deadlock are two common bugs that can occur in concurrent programming. Starvation happens when one one or more threads do not get a chance to run or do not get access to a shared resource because other (often higher priority) threads are hogging the CPU or resource. The code for the Dining Philosophers challenge can be found here: https://github.com/ShawnHymel/introduction-to-rtos/blob/main/10-deadlock/esp32-freertos-10-challenge-dining-philosophers/esp32-freertos-10-challenge-dining-philosophers.ino The solution to the challenge in the video can be found here: https://www.digikey.com/en/maker/projects/introduction-to-rtos-solution-to-part-10-deadlock-and-starvation/872c6a057901432e84594d79fcb2cc5d Code for this video series (including demonstrations, challenges, and solutions) can be found here: https://github.com/ShawnHymel/introduction-to-rtos We can avoid starvation by ensuring that higher-priority tasks yield the processor periodically to allow lower-priority tasks a chance to run. Additionally, the higher-priority tasks should make sure to release any shared resources they might have to allow lower-priority tasks access to them. We can also implement a technique called “aging” in a high priority task or in the scheduler itself. Aging gradually increases the priority of any task that has been in the blocked state for some period of time. Eventually, the task will reach the same priority level as the high priority tasks that are hogging the CPU/resource, and the previously low-priority task will get a chance to run. After performing its required actions, the low-priority task will have its priority downgraded to its original level to start the aging process again. In the video, we provide the classic “Dining Philosophers” as an analogy to demonstrate starvation and deadlock. Deadlock occurs when all tasks are waiting on each other for a lock (e.g. mutex or semaphore) and no task is able to continue execution. Deadlock can result in system-wide failure and should be avoided at all costs. We also give two possible solutions to the Dining Philosophers problem, including assigning a hierarchy to the locks as well as using a mutex to control access to the locks. Product Links: https://www.digikey.com/en/products/detail/adafruit-industries-llc/3405/7244967 Related Videos: Introduction to RTOS Part 1 - What is a Real-Time Operating System (RTOS)? - https://youtu.be/F321087yYy4​ Introduction to RTOS Part 2 - Getting Started with FreeRTOS - https://youtu.be/JIr7Xm_riRs​ Introduction to RTOS Part 3 - Task Scheduling - https://youtu.be/95yUbClyf3E​ Introduction to RTOS Part 4 - Memory Management - https://youtu.be/Qske3yZRW5I​ Introduction to RTOS Part 5 - Queue - https://youtu.be/pHJ3lxOoWeI​ Introduction to RTOS Part 6 - Mutex - https://youtu.be/I55auRpbiTs​ Introduction to RTOS Part 7 - https://youtu.be/5JcMtbA9QEE​ Introduction to RTOS Part 8 - https://youtu.be/b1f1Iex0Tso Introduction to RTOS Part 9 - https://youtu.be/qsflCf6ahXU Introduction to RTOS Part 10 - https://youtu.be/hRsWi4HIENc Introduction to RTOS Part 11 - https://youtu.be/C2xKhxROmhA Introduction to RTOS Part 12 - https://youtu.be/LPSHUcH5aQc Related Project Links: https://www.digikey.com/en/maker/projects/introduction-to-rtos-solution-to-part-10-deadlock-and-starvation/872c6a057901432e84594d79fcb2cc5d Related Articles: https://www.digikey.com/en/maker/videos/shawn-hymel/getting-started-with-stm32-and-nucleo-part-3-how-to-run-multiple-threads-with-cmsis-rtos-interface Learn more: Maker.io - https://www.digikey.com/en/maker Digi-Key’s Blog – TheCircuit https://www.digikey.com/en/blog Connect with Digi-Key on Facebook https://www.facebook.com/digikey.electronics/ And follow us on Twitter https://twitter.com/digikey