Algoritmos de prevención de interbloqueos

En informática , los algoritmos de prevención de interbloqueos 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 indiscriminadamente, puede darse 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 se bloquean y no pueden continuar su ejecución. Esta situación se denomina interbloqueo . Un algoritmo de prevención de interbloqueos organiza el uso de recursos por parte de cada proceso para garantizar que al menos un proceso siempre pueda obtener todos los recursos que necesita. Un ejemplo de algoritmo de prevención de interbloqueos es el algoritmo del banquero .

Descripción general

Interbloqueo distribuido

Los interbloqueos distribuidos pueden ocurrir en sistemas distribuidos cuando se utilizan transacciones distribuidas o control de concurrencia . Estos interbloqueos pueden detectarse mediante la construcción de un grafo de espera global , a partir de grafos de espera locales en un detector de interbloqueos o mediante un algoritmo distribuido como el seguimiento de aristas.

Los interbloqueos fantasma son interbloqueos que se detectan en un sistema distribuido debido a retrasos internos del sistema, pero que en realidad ya no existen en el momento de la detección.

prevención de bloqueos

Existen diversas maneras de aumentar el paralelismo en situaciones donde los bloqueos recursivos provocarían interbloqueos. Sin embargo, esto tiene un precio: un aumento del rendimiento, una mayor probabilidad de corrupción de datos o ambas cosas.

Algunos ejemplos incluyen: jerarquías de bloqueo, ^{[ 1 ]} conteo de referencias de bloqueo y preempción (ya sea usando versionado o permitiendo la corrupción de datos cuando ocurre la preempción); Wait-For-Graph (WFG)algoritmos que rastrean todos los ciclos que causan interbloqueos (incluidos los interbloqueos temporales); y algoritmos heurísticos que no necesariamente aumentan el paralelismo en el 100% de los lugares donde son posibles los interbloqueos, sino que buscan un compromiso resolviéndolos en suficientes lugares como para que el rendimiento/sobrecarga en relación con el paralelismo sea aceptable.

Consideremos la situación de que dos trenes se aproximan en un cruce. La prevención justo a tiempo funciona como si una persona estuviera en el cruce (el guarda) con un interruptor que permite que solo un tren acceda a las vías especiales, que pasan por encima de los demás trenes que esperan.

En el caso de bloqueos no recursivos, solo se puede acceder a un bloqueo una vez (si un mismo hilo accede dos veces sin desbloquearlo, se producirá un interbloqueo o se generará una excepción para evitar la espera circular).
En los bloqueos recursivos, solo un hilo puede atravesar el bloqueo. Si otros hilos acceden al bloqueo, deben esperar hasta que el hilo inicial que lo atravesó complete el número de veces que ha accedido a él.

El problema con el primero es que no previene ningún interbloqueo. El segundo no previene interbloqueos distribuidos. Sin embargo, el segundo se ha redefinido para prevenir un escenario de interbloqueo que el primero no contempla.

De forma recursiva, solo un hilo puede atravesar un bloqueo. Si otros hilos acceden al bloqueo, deben esperar hasta que el hilo inicial que lo atravesó complete su operación un número determinado de veces. Sin embargo, si el número de hilos que acceden al bloqueo es igual al número de hilos bloqueados, se asigna un hilo como superhilo y solo se le permite ejecutarse (registrando el número de veces que accede y sale del bloqueo) hasta que finalice su operación.

Una vez que un superhilo ha terminado, la condición vuelve a utilizar la lógica del bloqueo recursivo y el superhilo saliente.

Se establece como no ser un hilo principal
notifica al bloqueador que otros subprocesos bloqueados en espera necesitan volver a comprobar esta condición.

Si se produce un interbloqueo, cree un nuevo hilo principal y siga su lógica. De lo contrario, reanude el bloqueo normal.

Cuestiones no abordadas anteriormente

Existe mucha confusión en torno al problema de la parada . Sin embargo, esta lógica no lo resuelve, ya que 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 que requiere el problema de la parada). Aun así, este mecanismo de bloqueo evita todos los interbloqueos considerando únicamente los bloqueos que utilizan esta lógica. Pero si se utiliza con otros mecanismos de bloqueo, un bloqueo que se inicia nunca se desbloquea (se lanza una excepción que se ejecuta sin desbloquearse, se produce un bucle infinito dentro de un bloqueo o se produce un error de codificación al olvidar llamar a la función de desbloqueo), lo que hace muy probable que se produzca un interbloqueo. Ampliar la condición para incluir estos casos requeriría resolver el problema de la parada, ya que se estaría trabajando con condiciones desconocidas e inmodificables.

Otro problema es que no aborda el problema del interbloqueo temporal (que en realidad no es un interbloqueo, pero sí un obstáculo para el rendimiento), donde dos o más hilos se bloquean entre sí mientras se ejecuta otro hilo independiente. Estos interbloqueos temporales podrían tener un hilo ejecutándose exclusivamente dentro de ellos, lo que aumentaría el paralelismo. Sin embargo, debido a cómo funciona la detección de interbloqueos distribuidos para todos los bloqueos, y no para subconjuntos, el hilo en ejecución independiente debe finalizar antes de que se ejecute la lógica del superhilo para eliminar el interbloqueo temporal.

En la imagen anterior se puede observar un escenario de interbloqueo temporal. Si otro hilo de ejecución independiente comienza antes de que finalice el primero, se producirá otro período de interbloqueo temporal. Si esto ocurre de forma continua (algo extremadamente raro), el interbloqueo temporal puede prolongarse hasta justo antes de que finalice el programa, momento en el que se garantiza que los demás hilos independientes terminarán (debido a la garantía de que al menos uno de ellos siempre se ejecutará hasta su finalización).

Mayor expansión

Esto se puede ampliar aún más para incluir lógica adicional que aumente el paralelismo en situaciones donde podrían producirse interbloqueos temporales. Sin embargo, con cada paso que se añade a la lógica, se incrementa la sobrecarga.

Algunos ejemplos incluyen: ampliar el mecanismo de bloqueo de superhilos distribuidos para considerar cada subconjunto de bloqueos existentes; Wait-For-Graph (WFG).algoritmos que rastrean todos los ciclos que causan interbloqueos (incluidos los 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 suficientes lugares para que el rendimiento/sobrecarga frente al paralelismo sea aceptable (por ejemplo, para cada procesador disponible, trabajar para encontrar ciclos de interbloqueo con una profundidad menor que el número de procesadores + 1).

Espera-muere

Recorra las acciones del cronograma en orden cronológico. Si una transacción se cancela debido a una política, no continúe con el resto de las acciones de dicha transacción. Si una transacción de menor prioridad espera a que finalice una transacción de mayor prioridad (ya sea confirmada o no) que no se haya cancelado, la transacción de menor prioridad se cancelará.

Prueba: Para que se produzca un interbloqueo, T1 debe estar esperando un bloqueo que posee T2, mientras que T2 está esperando un bloqueo (diferente) que posee T1. Pero T2, al esperar a T1, debe tener una prioridad menor, por lo que T2 muere y se evita el interbloqueo.

Espera de la herida

Recorra las acciones del cronograma en orden cronológico. Si una transacción se cancela debido a una política, no continúe con el resto de las acciones de dicha transacción. Si una transacción de mayor prioridad espera a una transacción de menor prioridad no confirmada ni cancelada, la transacción de menor prioridad se cancela.