Explicar el algoritmo centralizado de detección de deadlocks.
El algoritmo centralizado de detección de deadlocks implica la existencia de un coordinador o líder que mantenga un grafo con los procesos y los recursos pedidos por cada uno.
Cuando un proceso quiere pedir un recurso, le avisa al coordinador, que agrega una arista conectando al recurso con el proceso. Cuando quiere liberar el recurso, el coordinador elimina la arista. Al ingresar una nueva arista, si se detecta un ciclo en el grafo, quiere decir que ocurrió un deadlock.
Se debe tener en cuenta que si los mensajes llegan en desorden, se pueden dar falsos positivos, donde se cree que se tiene un deadlock cuando en realidad no es así. Para resolver este problema, se pueden utilizar timestamps globales.
Explicar el algoritmo distribuido de detección de deadlocks.
El algoritmo distribuido de detección de deadlocks comienza cuando un proceso quiere pedir un recurso. En este caso, el proceso le envía un mensaje al proceso que ya tiene el recurso con su info y qué recurso está pidiendo. El proceso que recibe el mensaje, a su vez, envía un mensaje a los procesos que tienen los recursos que él quiere. Si el proceso original (el que comenzó el algoritmo) recibe un mensaje de este tipo, es porque hay un ciclo en la estructura del sistema distribuido, y se detectó un deadlock.
A nivel conceptual, en qué se diferencian los algoritmos de detección de deadlocks de los de prevención de deadlocks?
Los algoritmos de detección de deadlocks se utilizan para averiguar si hay un deadlock en el sistema, pero no resuelven el deadlock. Los algoritmos de prevención, en cambio, sí abortan el proceso o transacción correspondiente para salir de la situación de deadlock.
Explicar el algoritmo wait-die de prevención de deadlocks?
El algoritmo wait-die utiliza timestamps globales. Presupone dos transacciones, A y B, ambas con timestamp único. Si la transacción A pide un recurso que B ya tiene, se comparan los timestamps:
- Si timestamp_A > timestamp_B –> la transacción que pide es más nueva que la que tiene el recurso –> la transacción nueva se aborta.
- Si timestamp_B > timestamp_A –> la transacción que tiene el recurso es más nueva que la que pide el recurso –> la transacción vieja espera.
Se busca abortar la transacción vieja por sobre la nueva ya que, estadísticamente, la transacción vieja realizó más operaciones, por lo que abortarla será más laborioso y costoso que abortar una nueva.
Explicar el algoritmo wound-wait de prevención de deadlocks?
El algoritmo wound-wait utiliza timestamps globales. Presupone dos transacciones, A y B, ambas con timestamp único. Si la transacción A pide un recurso que B ya tiene, se comparan los timestamps:
- Si timestamp_A > timestamp_B –> la transacción que pide el recurso es más nueva que la que tiene el recurso –> la transacción nueva espera.
- Si timestamp_B > timestamp_A –> la transacción que tiene el recurso es más nueva que la que pide el recurso –> la transacción nueva se aborta y la transacción vieja toma el recurso.
Se busca abortar la transacción vieja por sobre la nueva ya que, estadísticamente, la transacción vieja realizó más operaciones, por lo que abortarla será más laborioso y costoso que abortar una nueva.
Explicar las complicaciones de los deadlocks en entornos de concurrencia distribuida.
- Nodo caído: se debe tener en cuenta que en sistemas distribuidos reales, los nodos pueden caerse
- Sincronizar timestamps globales: si los algoritmos implementados utilizan timestamps, se debe tener en cuenta que habrá que implementar algoritmos como el de Lamport para sincronizarlos
- Detección y prevención de deadlocks es más difícil: mientras que en sistemas en una computadora se pueden utilizar estructuras para evitar deadlocks o sincronizar procesos, en sistemas distribuidos se deben implementar algoritmos aparte, con su complejidad y costo, para garantizar exclusión mutua y ausencia y/o resolución de deadlocks, entre otros.
- Performance: de la mano del punto anterior, todos los algoritmos afectarán a la performance, no sólo por la complejidad del propio algoritmo, sino también por la complejidad y el tiempo de espera agregado en comunicar todos los componentes del sistema.
