Skip to content

Latest commit

 

History

History
29 lines (26 loc) · 2.76 KB

EntregaTeorica.md

File metadata and controls

29 lines (26 loc) · 2.76 KB

Algoritmos de detección de Deadlocks

Linux

Si buscamos en internet, es box populi que el kernel de linux no hace nada por evitar deadlocks. Muy probablemente esto se deba a que el ojo de sauron: Linus Torvalds lee cada línea de código1 que se sube al repo y evita estos problemas antes de que lleguen a una release.
Y esto mismo es lo que hace cada desarrollador del kernel GNU/Linux2. Dado que el costo operacional del checkeo en runtime es muy alto, se optó por no tener mecanismos de detección de deadlocks3. Sino que se puede agregar (en compilaciónes de debug) la feature lockdep4 5 al kernel, que checkea en cada adquisición de lock si el kernel entrará en deadlock.
Estos checkeos tienen un costo de O(2ⁿ), por ende sólo se checkean cadenas nuevas a través de la generación de un hash y un hash lookup en una tabla lock free6. Además se encargan de obtener estadísticas de todas las cadenas de locks obtenidas, de forma tal que despues puedan probar todos los posibles interleavings entre otros componentes. Finalmente, queda probado que no hay deadlocks por el momento, y en caso de que hayan se solucionarán en una próxima versión.
Cada cuanto checkea? Cada vez que hay una cadena nueva de locks, no es por tiempo fijo.

Windows

El caso de Windows es similar a linux, no se tiene un checkeo en runtime (que se sepa) y se pueden agregar herramientas para debuggear drivers!cambiar o el mismo kernel!cambiar a la consola de kernel debugging!cambiar. Tanto la consola de kernel como la de drivers estan integradas a Windows 10 por defecto.
Para habilitar el checkeo de deadlock se puede utilizar el comando: verifier /flags 0x20 /driver MyDriver.sys La el intervalo de checkeos no puede ser configurado ni desde la CLI ni desde la GUI.

Referencias

1
2
3
4
5
6
7