Algoritmos de prevención de interbloqueo - Deadlock prevention algorithms
En informática , los algoritmos de prevención de interbloqueo se utilizan en la programación concurrente cuando varios procesos deben adquirir más de un recurso compartido . Si dos o más procesos concurrentes obtienen múltiples recursos de manera indiscriminada, puede ocurrir una situación en la que cada proceso tenga un recurso que otro proceso necesita. Como resultado, ninguno de los procesos puede obtener todos los recursos que necesita, por lo que todos los procesos están bloqueados para su posterior ejecución. Esta situación se denomina punto muerto . Un algoritmo de prevención de interbloqueo organiza el uso de recursos por cada proceso para garantizar que al menos un proceso siempre pueda obtener todos los recursos que necesita. Un ejemplo de algoritmo de interbloqueo es el algoritmo de Banker.
Descripción general
| Nombre | Condiciones de Coffman | Descripción |
|---|---|---|
| Algoritmo bancario | Exclusión mutua | El algoritmo del banquero es una asignación de recursos y punto muerto evitación algoritmo desarrollado por Edsger Dijkstra . |
| Prevención de bloqueos recursivos | Exclusión mutua | Esto evita que un solo hilo ingrese al mismo bloqueo más de una vez. |
Interbloqueo distribuido
Los interbloqueos distribuidos pueden ocurrir en sistemas distribuidos cuando se utilizan transacciones distribuidas o control de simultaneidad . Los interbloqueos distribuidos se pueden detectar mediante la construcción de un gráfico de espera global , a partir de gráficos de espera locales en un detector de interbloqueo o mediante un algoritmo distribuido como la persecución de bordes .
Los interbloqueos fantasmas son interbloqueos que se detectan en un sistema distribuido debido a retrasos internos del sistema, pero que ya no existen en el momento de la detección.
Prevención de interbloqueo
Hay muchas formas diferentes de aumentar el paralelismo donde los bloqueos recursivos causarían interbloqueos. Pero hay un precio. Y ese precio es rendimiento / gastos generales, permite la corrupción de datos o ambos.
Algunos ejemplos incluyen: bloquear jerarquías, bloquear el recuento de referencias y la preferencia (ya sea mediante el control de versiones o permitiendo la corrupción de datos cuando se produce la preferencia); Algoritmos Wait-For-Graph (WFG) [1] , que rastrean todos los ciclos que causan interbloqueos (incluidos interbloqueos temporales); y algoritmos heurísticos que no necesariamente aumentan el paralelismo en el 100% de los lugares en los que son posibles los interbloqueos, sino que se comprometen resolviéndolos en suficientes lugares para que el rendimiento / sobrecarga frente al paralelismo sea aceptable.
Considere una situación de "cuando dos trenes se acercan en un cruce". La prevención justo a tiempo funciona como tener una persona parada en el cruce (el guardia de cruce) con un interruptor que permitirá que solo un tren ingrese a las "súper vías" que corren por encima y por encima de los otros trenes en espera.
- Para bloqueos no recursivos, se puede ingresar un bloqueo solo una vez (donde un solo hilo que ingrese dos veces sin desbloquearse causará un interbloqueo o lanzará una excepción para hacer cumplir la prevención de espera circular).
- Para bloqueos recursivos, solo se permite que un subproceso pase a través de un bloqueo. Si otros subprocesos entran en el bloqueo, deben esperar hasta que el subproceso inicial que pasó se complete n número de veces que ha entrado.
Entonces, el problema con el primero es que no hace ninguna prevención de interbloqueo. El segundo no hace prevención de interbloqueo distribuido. Pero el segundo se redefine para evitar un escenario de punto muerto que el primero no aborda.
De forma recursiva, solo se permite que un hilo pase a través de un candado. Si otros subprocesos entran en el bloqueo, deben esperar hasta que el subproceso inicial que pasó se complete n veces. Pero si el número de subprocesos que ingresan al bloqueo es igual al número de los que están bloqueados, asigne un subproceso como superproceso y solo permita que se ejecute (rastreando el número de veces que ingresa / sale del bloqueo) hasta que se complete.
Una vez finalizado un superhilo, la condición vuelve a usar la lógica del bloqueo recursivo y el superhilo existente
- se establece a sí mismo como no ser un superhilo
- notifica al casillero que otros subprocesos bloqueados y en espera deben volver a verificar esta condición
Si existe un escenario de interbloqueo, establezca un nuevo superproceso y siga esa lógica. De lo contrario, reanude el bloqueo regular.
Problemas no tratados anteriormente
Mucha confusión gira en torno al problema de la detención . Pero esta lógica no resuelve el problema de la detención porque se conocen las condiciones en las que se produce el bloqueo, lo que proporciona una solución específica (en lugar de la solución general requerida de otro modo que requiere el problema de la detención). Aún así, este casillero evita todos los interbloqueos considerando solo los bloqueos usando esta lógica. Pero si se utiliza con otros mecanismos de bloqueo, un bloqueo que se inicia nunca se desbloquea (excepción lanzada saltando sin desbloquear, bucle indefinidamente dentro de un bloqueo o error de codificación al olvidar llamar al desbloqueo), el interbloqueo es muy posible. Para aumentar la condición para incluirlos, sería necesario resolver el problema de la detención, ya que uno estaría lidiando con condiciones de las que no sabe nada y no puede cambiar.
Otro problema es que no aborda el problema del interbloqueo temporal (no es realmente un interbloqueo, sino un asesino del rendimiento), donde dos o más subprocesos se bloquean entre sí mientras se ejecuta otro subproceso no relacionado. Estos puntos muertos temporales podrían tener un hilo ejecutándose exclusivamente dentro de ellos, aumentando el paralelismo. Pero debido a cómo funciona la detección de interbloqueo distribuido para todos los bloqueos, y no para los subconjuntos, el subproceso en ejecución no relacionado debe completarse antes de realizar la lógica del superhilo para eliminar el interbloqueo temporal.
Uno puede ver el escenario de bloqueo en vivo temporal en el anterior. Si otro subproceso en ejecución no relacionado comienza antes de que salga el primer subproceso no relacionado, se producirá otra duración de interbloqueo temporal. Si esto sucede continuamente (extremadamente raro), el interbloqueo temporal se puede extender hasta justo antes de que el programa salga, cuando se garantiza que los otros subprocesos no relacionados terminarán (debido a la garantía de que un subproceso siempre se ejecutará hasta su finalización).
Mayor expansión
Esto se puede expandir aún más para involucrar lógica adicional para aumentar el paralelismo donde, de lo contrario, podrían ocurrir puntos muertos temporales. Pero por cada paso de agregar más lógica, agregamos más gastos generales.
Un par de ejemplos incluyen: expandir el mecanismo de bloqueo de superhilo distribuido para considerar cada subconjunto de bloqueos existentes; Algoritmos Wait-For-Graph (WFG) [2] , que rastrean todos los ciclos que causan interbloqueos (incluidos interbloqueos temporales); y algoritmos heurísticos que no necesariamente aumentan el paralelismo en el 100% de los lugares donde son posibles los interbloqueos temporales, sino que se comprometen resolviéndolos en lugares suficientes para que el rendimiento / sobrecarga frente al paralelismo sea aceptable (por ejemplo, para cada procesador disponible, trabaje para encontrar el interbloqueo ciclos menos que el número de procesadores + 1 de profundidad).