Algoritmos de Detección

Algoritmo Centralizado

• El proceso coordinador mantiene el grafo de uso de recursos
• Los procesos envían mensajes al coordinador cuando obtienen/liberan un recurso y el coordinador actualiza el grafo
• Problema: los mensajes pueden llegar llegar desordenados y generar falsos deadlocks
• Posible solución: utilizar timestamps globales para ordenar los mensajes (algoritmo de Lamport)

Algoritmo Distribuido

• Cuando un proceso debe esperar por un recurso, envía un probe message al proceso que tiene el recurso. El mensaje contiene: id del proceso que se bloquea, id del proceso que envía el mensaje y id del proceso destinatario
• Al recibir el mensaje, el proceso actualiza el id del proceso que envía y el id del destinatario y lo envía a los procesos que tienen el recurso que necesita
• Si el mensaje llega al proceso original, tenemos un ciclo en el grafo

Algoritmos de Prevención

Algoritmo Wait - die

• Se asigna un timestamp único y global a cada transacción al iniciar (algoritmo de Lamport)
• Cuando un proceso está por bloquearse en un recurso (que tiene otro proceso), se comparan los timestamps
  • Si el timestamp es menor (proceso más viejo), espera
  • Si no, el proceso aborta la transacción

Algoritmo wound - wait

• Se asigna un timestamp único y global a cada transacción al iniciar (algoritmo de Lamport)
• Cuando un proceso está por bloquearse en un recurso (que tiene otro proceso), se comparan los timestamps
  • Si el timestamp es menor (proceso más viejo), se aborta la transacción del proceso que tiene el recurso, para que el más viejo pueda tomarlo
  • Si no, el proceso espera

Bibliografía

• Distributed Operating Systems, Andrew S. Tanenbaum, capítulo 3
• Computer Networks, Andrew S. Tanenbaum y David J. Wetherall, quinta edición