multithreading - starvation - ¿Cómo explicar mejor el "punto muerto"?
java thread pool (15)
Estoy luchando para explicar el "punto muerto" en los hilos con palabras sencillas, así que por favor ayuda. ¿Cuál podría ser el mejor ejemplo de "punto muerto" (por ejemplo, en Java), y cómo ocurre en los pasos y cómo prevenirlo? Pero sin entrar en detalles demasiado profundos. Sé que es como preguntar dos cosas opuestas, pero aún así. Si tiene experiencia previa en la capacitación de programación simultánea, ¡sería excelente!
El punto muerto es cuando dos hilos esperan el uno del otro, ninguno puede continuar hasta que el otro lo hace primero, y por lo tanto ambos están atascados.
El bloqueo de bloqueo requiere al menos 2 bloqueos, y ambos hilos deben contener un código que tome bloqueos y también espere a que se liberen los bloqueos.
El subproceso 1 tiene el bloqueo A y quiere el bloqueo B, por lo que espera que se libere el bloqueo B.
El Subproceso 2 tiene el bloqueo B y quiere el bloqueo A, por lo que espera que se libere el bloqueo A.
Ahora tienes un punto muerto. Ambos hilos a la espera de un bloqueo, por lo que ninguno de los dos se está ejecutando, por lo que ninguno puede liberar el bloqueo que el otro está esperando.
El punto muerto ocurre cuando tienes 2 recursos diferentes que necesitan 2 hilos diferentes para bloquearlos para usarlos. Los subprocesos los bloquean en el orden inverso, por lo que es imposible que la ejecución continúe hasta que uno de los subprocesos retroceda.
Wikipedia tiene un par de buenos ejemplos reales de punto muerto.
Filósofos gastronómicos: tienes 4 personas sentadas en una mesa y 4 palillos. Necesitas 2 palillos para comer. Imagine que cada filósofo intenta comer de la siguiente manera:
- Levante el palillo izquierdo.
- Levante el palillo derecho.
- Comer.
- Coloque el palillo derecho hacia atrás.
- Coloque el palillo izquierdo hacia atrás.
Todos hacen el paso 1. Ahora el paso 2 es imposible, ya que cada persona espera que el de su derecha caiga a la izquierda, lo cual no hará. Esto es un punto muerto. Si solo se turnaban, todos podían comer, pero todos morían de hambre.
La descripción de Guffa es buena.
La mejor manera que he encontrado para evitar los bloqueos es bloquear los recursos que son privados para ti y liberar el bloqueo antes de llamar a algo sobre lo que no tienes 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 de todos modos es menos probable que cause problemas a largo plazo.
Este artículo es bueno para leer sobre este problema.
La manera 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 va a dormir. El hilo 2 obtiene el bloqueo B y luego intenta obtener el bloqueo A; dado que se toma el bloqueo A, el hilo 2 se pondrá en reposo hasta que el hilo A se desbloquee. Ahora el hilo 1 se despierta y trata de obtener el bloqueo B y se pone a dormir.
Para este caso, hay un par de formas de prevenirlo:
- Un hilo nunca debería necesitar sostener dos bloqueos simultáneamente.
- Si se deben mantener dos bloqueos simultáneamente, siempre se deben adquirir en el mismo orden (por lo que en mi ejemplo anterior, el hilo 2 debería modificarse para solicitar el bloqueo A antes de solicitar el bloqueo B).
Por lo general, las clases de programación simultánea explican el punto muerto mediante ejemplos. Creo que el problema de los Filósofos del Comedor será un buen ejemplo para usar. Puede desarrollar este ejemplo en Java y explicar la aparición de un punto muerto cuando dos filósofos sostienen un tenedor a la izquierda y esperan el tenedor correcto. (o viceversa).
Aprendí muchos conceptos de la programación concurrente utilizando estos ejemplos implementados en Java.
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 ejecuta, Bloquea A, hace algunas cosas, y es interrumpido por el Hilo 2 que Bloquea B, hace algunas cosas y es interrumpido por el Hilo 1 que intenta Bloquear B, pero el hilo 2 ha bloqueado B por lo que el hilo 1 espera y se interrumpe por el Subproceso 2 que intenta bloquear A, pero el subproceso 1 tiene el bloqueo en A, por lo que el Subproceso 2 tiene que esperar.
Ambos subprocesos están esperando a que el otro subproceso libere un bloqueo en un recurso que están intentando bloquear.
Punto muerto
Imagínese que usted y su novia se pelearon por quién debería abrir la puerta para salir de la casa. La persona que se disculpa abrirá la puerta. Ella está esperando que te disculpes, estás esperando que 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 reteniendo a un rehén y pidiendo un rescate. Apareces con una maleta llena de dinero.
El criminal nunca liberará al rehén antes de que reciba el dinero. Nunca liberarás el dinero antes de obtener el rehén. Punto muerto.
La analogía aquí es:
- Tú y el criminal son los hilos
- La maleta llena de dinero y el rehén son los recursos
Una simple analogía aquí: https://.com/a/21519666/3241237
y aquí: http://www.quora.com/Saurabh-Pandey-3/Posts/Never-ending-couple-fights-a-deadlock
(Ligeramente simplificado) Hay dos personas, atornillando tuercas en pernos.
El procedimiento (lo mismo para ambos) es:
- Recoge una tuerca o un perno
- Levante un perno o una tuerca (lo que no tenga)
- Atornille la tuerca en el perno
- Coloque el conjunto terminado en la pila "Terminado".
- si quedan tuercas y pernos, vaya al paso 1
Entonces, ¿qué sucede cuando solo queda una tuerca y un perno? La primera persona toma una nuez, la segunda agarra un perno. Hasta ahora todo bien, pero ahora están estancados, cada uno tiene un recurso que el otro necesita.
Sin instrucciones especiales, se sentarán allí encerrados para siempre.
O podrías mostrarles este video
Jack y Jill pasan a querer hacer un emparedado al mismo tiempo. Ambos necesitan una rebanada de pan, así que ambos van a buscar la barra de pan y un cuchillo.
Jack primero saca el cuchillo, mientras que Jill primero se lleva el pan. Ahora Jack intenta encontrar la barra de pan y Jill intenta encontrar el cuchillo, pero ambos encuentran que lo que necesitan para terminar la tarea ya está en uso. Si ambos deciden esperar hasta que lo que necesitan ya no esté en uso, esperarán el uno al otro para siempre. Punto muerto.
Otra buena forma 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 para una tabla que está bloqueada por otra transacción.
La ventaja aquí es que puedes demostrarlo con SQL Management Studio. He utilizado esto en el pasado para explicar los bloqueos a las personas a la vez que enseño cursos de formación de nivel "Introducción a SQL Server".
La mayoría de los participantes tienen problemas con la teoría, pero todo (generalmente) se vuelve 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 desde la tabla bloqueada por la Transacción A. La Transacción B está bloqueada hasta que la Transacción A se compromete o se retrotrae.
Podría explicar esto en el código bastante fácilmente creando dos hilos separados que, a su vez, creen las Transacciones. Espero eso ayude.
Prefiero explicarlo en términos totalmente ajenos a las computadoras, ya que a menudo es la mejor manera de transmitir una idea.
Tengo un hijo de cinco años y una hija de tres años. Ambos quieren hacer el mismo libro para colorear.
La hija toma los lápices mientras el hijo agarra el libro. Ninguno de ellos renunciará a lo que tienen hasta que obtengan el otro.
Eso es un punto muerto. No hay nada más simple que eso.
Sus procesos (o hijos) están atrapados esperando el uno al 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) conseguir que uno de ellos vea la razón y renuncie a su bloqueo. Esto usualmente no es posible con las computadoras, ya que los procesos no están haciendo nada excepto esperar por ese recurso (aunque a veces los niños también ingresan a este estado).
Seguir una regla garantizará que no se produzca un punto muerto:
- Haga que todos los hilos de ejecución asignen recursos en el mismo orden.
Seguir algunas reglas adicionales hará que tus hilos sean menos propensos a ralentizarse unos a otros, pero ten en cuenta que la regla anterior debería tener prioridad sobre todas las demás:
- Asigne recursos solo cuando los necesite.
- Libérelos tan pronto como haya terminado con ellos.
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 está bloqueada por B, B está bloqueada por C, C está 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 ha formado un bucle, no hay progreso posible.
La forma típica de evitar interbloqueos es utilizar jerarquías de bloqueo: si los cerrojos siempre son adquiridos por cada trabajador en el mismo orden, entonces no es posible un bloqueo porque cada bloqueo ocurre entre un trabajador que tiene bloqueos clasificados X y espera recursos ordenados Y, donde X> Y siempre En este caso no se puede formar un bucle, ya que requeriría al menos un trabajador ir contra la jerarquía para cerrar el bucle. Así es como funciona la teoría, al menos. En prcatice es muy difícil encontrar jerarquías realistas (y no, la dirección del recurso no funciona).
Si no se pueden evitar los interbloqueos (por ejemplo, los sistemas de bases de datos), entonces la solución es tener hilos dedicados que verifiquen las cadenas de interbloqueo en busca de bucles y matar a uno de los participantes para liberar el bucle.