¿Cómo explicar mejor el "punto muerto"?

La forma más fácil es que dos hilos diferentes intenten obtener dos bloqueos en diferentes órdenes:

thread 1:
lock(a)
lock(b)

thread2:
lock(b)
lock(a)

Supongamos que el hilo 1 obtiene el bloqueo A y luego se duerme. El hilo 2 obtiene el bloqueo B y luego intenta obtener el bloqueo A; desde que se toma el bloqueo A, el hilo 2 se pondrá en suspensión hasta que el hilo A se desbloquee. Ahora el hilo 1 se despierta de nuevo y trata de obtener el bloqueo B y se pondrá a dormir.

Para este caso, hay un par de maneras de prevenirlo:

1. Un hilo nunca debería necesitar mantenga dos cerraduras simultáneamente.
2. Si dos bloqueos deben mantenerse simultáneamente, siempre deben adquirirse en el mismo orden (por lo que en mi ejemplo anterior, el hilo 2 tendría que modificarse para solicitar bloqueo A antes de solicitar bloqueo B).

Prefiero explicarlo en términos totalmente ajenos a las computadoras, ya que a menudo es la mejor manera de transmitir una idea.

La hija agarra los lápices mientras que el hijo agarra el libro. Ninguno renunciará a lo que tienen hasta que consigan el otro.

Eso es un punto muerto. No hay nada más simple que eso.

Sus procesos (o hijos) están atascados esperando el uno para el otro y continuarán esperando indefinidamente hasta que algún otro proceso superior (como papá) entre y rompa el punto muerto.

Al menos con los niños, puede (a veces) hacer que uno de ellos entre en razón y renuncie a su candado. Esto no suele ser posible con ordenadores ya que los procesos no están haciendo nada excepto esperar ese recurso (aunque a veces los hijos también entran en este estado).

Seguir una regla garantizará ese punto muerto no puede ocurrir:

• Have all threads of execution allocate resources in the same order.

Seguir algunas reglas adicionales hará que sus hilos sean menos propensos a ralentizarse entre sí, pero tenga en cuenta que la regla anterior debe tener prioridad sobre todas las demás:

• Asigne recursos solo cuando los necesite.
• Libéralos tan pronto como hayas terminado con ellos.

  Thrd 1 --- Lock A        - atmpt lock on B -   
         \                /                   \
          \              /                     \           
           \            /                       \         
            --- Lock A /                         --- wait for lock on B

  Thrd 2--- Lock B         - atmpt lock on A -   
         \                /                   \
          \              /                     \           
           \            /                       \         
            --- Lock B /                         --- wait for lock on A

El hilo 1 se ejecuta, bloquea A, hace algunas cosas, y se interrumpe por Hilo 2 que bloquea B, hace algunas cosas y se interrumpe por Hilo 1 que intentan bloquear B, pero el hilo 2 ha bloqueado B por lo que el hilo 1 espera, y se interrumpe por El hilo 2 que intenta bloquear A, pero el hilo 1 tiene bloqueo en A, por lo que el hilo 2 tiene que esperar.

Ambos subprocesos están esperando que el otro subproceso libere un bloqueo sobre un recurso que están tratando de bloquear...

Punto muerto

Normalmente las clases de programación concurrente explican el punto muerto mediante ejemplos. Creo que el problema de los Filósofos Comedor será un buen ejemplo de uso. Puede desarrollar este ejemplo en Java y explicar la ocurrencia de punto muerto cuando dos filósofos sostienen una bifurcación izquierda y están esperando la bifurcación derecha. (o viceversa).

Aprendí muchos conceptos de programación concurrente usando estos ejemplos implementados en Java.

Otra buena manera de demostrar un punto muerto es con SQL Server.

Usando transacciones con diferentes niveles de aislamiento, puede demostrar cómo una transacción esperará indefinidamente una tabla que está bloqueada por otra transacción.

El plus aquí, es que puede demostrarlo con SQL Management Studio. He utilizado esto en el pasado para explicar los bloqueos a las personas mientras enseñaba cursos de capacitación de nivel "Introducción a SQL Server".

La mayoría de los participantes tienen problemas con la teoría, pero todo (por lo general) se hace claro cuando lo ven en acción.

En resumen: La transacción A (que no se ha completado) toma un bloqueo de tabla explícito. Una segunda Transacción B intenta leer de la tabla bloqueada por la Transacción A. La transacción B está bloqueada hasta que la Transacción A se confirma o se revierte.

Podría explicar esto en código con bastante facilidad creando dos hilos separados que, a su vez, crean las Transacciones. Espero que ayude.

El punto muerto es cuando dos hilos se esperan el uno al otro, ninguno puede continuar hasta que el otro lo haga primero, y por lo tanto ambos están atascados.

El deadlocking requiere al menos 2 bloqueos, y ambos hilos tienen que contener código que toma bloqueos y también espera que los bloqueos sean liberados.

El hilo 1 tiene bloqueo A y quiere bloqueo B, por lo que espera que el bloqueo B sea liberado.

El hilo 2 tiene bloqueo B y quiere bloqueo A, por lo que espera que el bloqueo A sea liberado.

Ahora tienes un punto muerto. Ambos hilos a esperando un bloqueo, por lo que ninguno de los dos está ejecutando, por lo que ninguno puede liberar el bloqueo que el otro está esperando.

El bloqueo ocurre cuando tienes 2 recursos diferentes que 2 hilos diferentes necesitan bloquear para usarlos. Los hilos los bloquean en el orden opuesto, por lo que es imposible que la ejecución continúe hasta que 1 de los hilos retroceda.

Wikipedia tiene un par de buenos ejemplos de la vida real de punto muerto.

Una cadena de bloqueo ocurre cuando un trabajador es bloqueado por otro trabajador. A no puede continuar debido a B. La cadena puede ser más larga: A es bloqueada por B, B es bloqueada por C, C es bloqueada por D.

Un punto muerto es cuando la cadena de bloqueo forma un bucle. A está bloqueado por B, B por C, C por A y la cadena había formado un bucle, no hay progreso posible.

La forma típica de evitar bloqueos es usar jerarquías de bloqueo: si los bloqueos son siempre adquiridos por todos los trabajadores en el mismo orden, entonces los bloqueos son no es posible porque cada bloqueo ocurre entre un trabajador que mantiene bloqueos clasificados X y espera recursos clasificados Y, donde X > Y siempre. Un bucle no puede formarse en este caso, ya que requeriría al menos un trabajador para ir en contra de la jerarquía con el fin de cerrar el bucle. Así es como va la teoría, al menos. En prcatice es muy, muy difícil llegar a jerarquías realistas (y no, la dirección del recurso no funciona).

Si los bloqueos no se pueden evitar (por ejemplo. sistemas de base de datos), a continuación, el la solución es tener hilos dedicados que comprueben las cadenas de punto muerto en busca de bucles y maten a uno de los participantes para liberar el bucle.

(Un poco simplificado) Hay dos personas, atornillando tuercas sobre pernos.

El procedimiento (el mismo para ambos) es:

1. Recoge una tuerca o un perno
2. Coge un perno o una tuerca (la que no tengas)
3. Atornille la tuerca en el perno
4. Coloque el conjunto terminado en la pila "Terminada".
5. si quedan tuercas y tornillos, vaya al paso 1

Entonces, ¿qué sucede cuando solo queda una tuerca y un perno? La primera persona toma una nuez, el segundo agarra un cerrojo. Hasta ahora todo bien, pero ahora están atascados, cada uno tiene un recurso que el otro necesita.

Sin instrucciones especiales se sentarán allí estancados para siempre.

O simplemente podrías mostrarles este video

Filósofos comedor - tienes 4 personas sentadas en una mesa, y 4 palillos. Necesitas 2 palillos para comer. Imagina que cada filósofo trata de comer de la siguiente manera:

1. Recoge el palillo izquierdo.
2. Recoge el palillo derecho.
3. Come.
4. Coloque el palillo derecho hacia atrás.
5. Coloque el palillo izquierdo hacia atrás.

Todos hacen el paso 1. Ahora el paso 2 es imposible, ya que cada persona espera a que el de su derecha deje caer el izquierdo, lo que no hará. Esto es un punto muerto. Si se turnaran, todos podrían comer, pero en lugar de eso, todos morirían de hambre.

La descripción de Guffa es buena.

La mejor manera que he encontrado para evitar bloqueos es bloquear solo los recursos que son privados para usted, y liberar el bloqueo antes de llamar a cualquier cosa sobre la que no tenga control exclusivo.

El único problema es que esto puede requerir que cambie de usar bloqueos para mantener la consistencia a usar acciones de compensación, pero es probablemente menos probable que cause problemas a largo plazo, de todos modos.

Este artículo es buena para leer sobre este problema.

Una analogía simple aquí: https://stackoverflow.com/a/21519666/3241237
y aquí: http://www.quora.com/Saurabh-Pandey-3/Posts/Never-ending-couple-fights-a-deadlock

Imagina que tú y tu novia discutían sobre quién debería abrir la puerta para salir de la casa.La persona que se disculpe abrirá la puerta. Ella está esperando que usted se disculpe, usted está esperando que ella se disculpe, lo que resulta en que la pareja nunca salga de la casa, ya que ambos se niegan a disculparse.

Imagina a un criminal sosteniendo a un rehén y pidiendo un rescate. Apareces con una maleta llena de dinero.

El criminal nunca liberará al rehén antes de recibir el dinero. Nunca liberarás el dinero antes de tener al rehén. Interbloqueo.

La analogía aquí es:

• Tú y el criminal son los hilos
• El maleta llena de dinero y el rehén son los recursos