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