El algoritmo de detección de puntos muertos distribuidos de Chandy-Misra-Haas es un algoritmo de búsqueda de bordes para detectar puntos muertos en sistemas distribuidos.
En el algoritmo de búsqueda de bordes, se utiliza un mensaje especial llamado sonda en la detección de puntos muertos. Una sonda es un triplete (i, j, k) que denota que el proceso Pi ha iniciado la detección de interbloqueo y el sitio de inicio del proceso P j envía el mensaje al sitio de inicio del proceso P k .
El mensaje de la sonda circula a lo largo de los bordes de WFG para detectar un ciclo. Cuando un proceso bloqueado recibe el mensaje de sondeo, reenvía el mensaje de sondeo a lo largo de sus bordes salientes en WFG. Un proceso Pi declara el interbloqueo si los mensajes de prueba iniciados por el proceso Pi regresan a sí mismos.
Otras terminologías utilizadas en el algoritmo:
- Proceso dependiente:
Se dice que un proceso P i es dependiente de algún otro proceso P j , si existe una secuencia de procesos P i , P i1 , P i2 , P i3 …, P im , P j tal que en la secuencia, cada proceso, excepto Pj , está bloqueado y cada proceso, excepto Pi , tiene un recurso que espera el proceso anterior de la secuencia.
- Proceso dependiente localmente:
Se dice que un proceso Pi depende localmente de algún otro proceso P j si el proceso Pi depende del proceso P j y ambos están en el mismo sitio.
Estructuras de datos:
una array booleana, dependiente i . Inicialmente, el dependiente i [j] es falso para todos los valores de i y j. dependiente i [j] es verdadero si el proceso P j depende del proceso P i .
Algoritmo:
Proceso de envío de sonda:
1. Si el proceso P i depende localmente de sí mismo, declare un interbloqueo.
2. De lo contrario, para todos los P j y P k verifique la siguiente condición:
- (a). El proceso P i depende localmente del proceso P j
- (b). El proceso P j está esperando al proceso P k
- (C). El proceso Pj y el proceso Pk están en sitios diferentes.
Si todas las condiciones anteriores son verdaderas, envíe la sonda (i, j, k ) al sitio de origen del proceso Pk .
Al recibir la sonda (i, j, k) en el lugar de origen del proceso P k :
1. El proceso Pk verifica las siguientes condiciones:
- (a). El proceso Pk está bloqueado.
- (b). dependiente k [i] es falso .
- (C). El proceso P k no ha respondido a todas las requests del proceso P j
Si todas las condiciones anteriores se cumplen, entonces:
1. Establezca k dependiente [i] en verdadero.
2. Ahora, si k == i entonces, declare que el P i está en punto muerto.
3. De lo contrario, para todos los P m y P n verifique las siguientes condiciones:
- (a). El proceso P k depende localmente del proceso P m y
- (b). El proceso P m está esperando al proceso P n y
- (C). El proceso P m y el proceso P n están en sitios diferentes.
4. Envíe la sonda (i, m, n) al sitio de origen del proceso P n si se cumplen las condiciones anteriores.
Por lo tanto, el mensaje de prueba viaja a lo largo de los bordes del gráfico de espera de transacción (TWF) y cuando el mensaje de prueba vuelve a su proceso de inicio, se dice que se ha detectado un interbloqueo.
Actuación:
- El algoritmo requiere como máximo el intercambio de m(n-1)/2 mensajes para detectar interbloqueos. Aquí, m es el número de procesos y n es el número de sitios.
- El retraso en la detección del interbloqueo es O(n) .
ventajas:
- No hay necesidad de una estructura de datos especial. En el proceso de detección de puntos muertos se utiliza un mensaje de sondeo, que es muy pequeño e incluye solo 3 números enteros y una array booleana bidimensional dependiente .
- En cada sitio, solo se requiere un pequeño cálculo y la sobrecarga también es baja
- A diferencia de otros algoritmos de detección de interbloqueos, no hay necesidad de construir ningún gráfico o pasar ni pasar la información del gráfico a otros sitios en este algoritmo.
- El algoritmo no informa ningún punto muerto falso (también llamado punto muerto fantasma).
Desventajas:
La principal desventaja de los algoritmos de detección distribuidos es que todos los sitios pueden no ser conscientes de los procesos involucrados en el interbloqueo, lo que dificulta la resolución. Además, la prueba de la corrección del algoritmo es difícil.