Los interbloqueos son un problema fundamental en los sistemas distribuidos. Un proceso puede solicitar recursos en cualquier orden y un proceso puede solicitar recursos mientras retiene otros. Un interbloqueo es una situación en la que se bloquea un conjunto de procesos, ya que cada proceso en un sistema distribuido tiene algunos recursos y otros procesos necesitan los recursos adquiridos.
Ejemplo:
Si hay tres procesos, p1, p2 y p1 están adquiriendo el recurso r1 y ese r1 lo necesita p2, que está adquiriendo otro recurso r2 y ese lo necesita p1. Aquí se produce el ciclo. Se llama interbloqueo.
Aquí, en el gráfico anterior, encontramos un ciclo de P1 a P2 y nuevamente a P1. Entonces podemos decir que el sistema está en un estado de interbloqueo.
El Problema de los interbloqueos ha sido generalmente estudiado en sistemas distribuidos bajo los siguientes modelos:
- El sistema solo tiene recursos reutilizables.
- A los procesos solo se les permite el acceso exclusivo a los recursos.
- Solo hay una copia de cada recurso.
Detección de punto muerto:
El algoritmo de detección de punto muerto es de dos tipos:
- Algoritmo de espera para gráfico (instancia única)
- Algoritmo del banquero (instancias múltiples)
Algoritmo Wait-for-Graph: es una variante del gráfico de asignación de recursos. En este algoritmo, solo tenemos procesos como vértices en el gráfico. Si Wait-for-Graph contiene un ciclo, entonces podemos decir que el sistema está en un estado Deadlock. Ahora discutiremos cómo el gráfico de asignación de recursos se convertirá en un gráfico de espera en un enfoque algorítmico. Necesitamos eliminar recursos durante la conversión de Resource Allocation Graph a Wait-for-Graph.
- Gráfico de asignación de recursos: contiene procesos y recursos.
- Wait-for-Graph: contiene solo procesos después de eliminar los recursos durante la conversión del gráfico de asignación de recursos.
Algoritmo:
Paso 1: Tome el primer proceso (Pi) del gráfico de asignación de recursos y verifique la ruta en la que está adquiriendo el recurso (R i ) e inicie un gráfico de espera con ese proceso en particular.
Paso 2: cree una ruta para la espera para el gráfico en la que no se incluirá ningún recurso desde el proceso actual (P i ) hasta el siguiente proceso (P j ), desde ese próximo proceso (P j ) encuentre un recurso (R j ) que será adquirido por el siguiente Proceso (P k ) que se libera del Proceso (P j ).
Paso 3: Repita el Paso 2 para todos los procesos.
Paso 4: después de completar todos los procesos, si encontramos un ciclo de circuito cerrado, entonces el sistema está en un estado de punto muerto y se detecta un punto muerto.
Ahora veremos el funcionamiento de este Algoritmo con un Ejemplo. Considere un gráfico de asignación de recursos con 4 procesos P1, P2, P3, P4 y 4 recursos R1, R2, R3, R4. Encuentre si hay un interbloqueo en el gráfico utilizando el algoritmo de detección de interbloqueos basado en Esperar gráfico.
Paso 1: Primero tome el Proceso P1 que está esperando el Recurso R1, el Proceso P2 adquiere el recurso R1, Inicie un Gráfico de espera para el Gráfico de asignación de recursos anterior.
Paso 2: ahora podemos observar que hay un camino de P1 a P2 ya que P1 está esperando a R1 que ha sido adquirido por P2. Ahora el gráfico sería después de eliminar el recurso R1.
Paso 3: Desde P2 podemos observar un camino de P2 a P3 ya que P2 está esperando a R4 que es adquirido por P3. Así que haga una ruta de P2 a P3 después de eliminar el recurso R4.
Paso 4: Desde P3 encontramos un camino a P4 ya que está esperando a P3 que es adquirido por P4. Después de eliminar R3, el gráfico se ve así.
Paso 5: Aquí podemos encontrar que el Proceso P4 está esperando a R2, que es adquirido por P1. Entonces, finalmente, el Wait-for-Graph es el siguiente:
Paso 6: Finalmente En este Gráfico, encontramos un ciclo ya que el Proceso P4 volvió nuevamente al Proceso P1 que es el punto de partida (es decir, es un circuito cerrado). Entonces, de acuerdo con el algoritmo, si encontramos un circuito cerrado, entonces el sistema está en un estado de interbloqueo. Así que aquí podemos decir que el sistema está en un estado de interbloqueo.
Ahora considere otro gráfico de asignación de recursos con 4 procesos P1, P2, P3, P4 y 3 recursos R1, R2, R3. Encuentre si hay un interbloqueo en el gráfico utilizando el algoritmo de detección de interbloqueos basado en Esperar gráfico.
Paso 1: Primero tome el Proceso P1 que está esperando el Recurso R1, el Proceso P2 adquiere el recurso R1, Inicie un Gráfico de espera para el Gráfico de asignación de recursos anterior.
Paso 2: ahora podemos observar que hay un camino de P1 a P2 y también de P1 a P4, ya que P1 está esperando a R1, que es adquirido por P2, y P1 también está esperando a R2, que es adquirido por P4. Ahora el gráfico sería después de eliminar los recursos R1 y R2.
Paso 3: Desde P2 podemos observar un camino de P2 a P3 ya que P2 está esperando a R3 que es adquirido por P3. Así que haga una ruta de P2 a P3 después de eliminar el aspecto del recurso R3.
Paso 4: Aquí podemos encontrar que el Proceso P4 está esperando a R3 que es adquirido por P3. Entonces, finalmente, se ve la espera para el gráfico después de eliminar el aspecto del recurso R3.
Paso 5: En este gráfico, no encontramos un ciclo ya que ningún proceso volvió al punto de partida (es decir, no hay ciclo cerrado). Entonces, de acuerdo con el algoritmo, si encontramos un circuito cerrado, entonces el sistema está en un estado de interbloqueo. Pero aquí no encontramos ningún circuito cerrado, por lo que el sistema no está en un estado de interbloqueo. El sistema está en un estado seguro.
Nota: En el Ejemplo 2, aunque parece un bucle, no hay ningún proceso que haya llegado al primer proceso o al punto de partida nuevamente. Así que no hay circuito cerrado.
Problemas en el algoritmo de detección de interbloqueo basado en espera de gráfico:
Para cada recurso que llamamos algoritmo de detección WFG, el tiempo de cálculo sería muy alto para la CPU si hay muchos recursos. La solución para esto es, en lugar de llamar a este algoritmo para cada solicitud de recursos que no se puede otorgar de inmediato. Simplemente invoque el algoritmo después de un intervalo definido.
Publicación traducida automáticamente
Artículo escrito por devasishakula503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA