Dekker's algorithm

rdf:langString Algoritmo de Dekker

rdf:langString El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra. Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización. Condiciones • No hay prioridad entre procesos. • La capacidad de los equipos es irrelevante. • Si un proceso muere fuera de la región crítica, el algoritmo sigue funcionando. • Un bloqueo mutuo no se considera como solución válida. Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos los primeros cuatro. La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4. * Versión 1: Alternancia estricta. Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos. * Versión 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí. * Versión 3: Colisión región crítica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región crítica. * Versión 4: Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda. shared int cierto = 1;/* ''Definición de variables compartidas'' */ shared int bandera[2] = {0,0}; shared int turno = 0; while (cierto) { bandera[proc_id] = cierto; // Está listo para acceder a la Sección Crítica while (bandera[1-proc_id] == cierto) { // Mientras el otro esté procesando if (turno == 1-proc_id) { // si es su turno bandera[proc_id] = 0; // indicar que no está listo y while (turno == (1-proc_id)) {} // esperar activamente. bandera[proc_id] = 1; // Cuando terminó de esperar, está listo } } /* ''Sección crítica'' */ turno = 1-proc_id; // Indicar el turno del otro proceso bandera[proc_id] = 0; // Indicar que ya no está listo (para acceder a la Sección Crítica) /* ''Sección no crítica'' */ } Ventajas • Este algoritmo garantiza la exclusión mutua. • Garantiza la libertad de bloqueos mutuos. • Garantiza la libertad de inanición. • Es un algoritmo simple y portable. Desventajas • Solo puede manejar un máximo de dos procesos. • Hace uso de espera activa. • No suspende a los procesos que están esperando acceso. • Puede llegar a entrar en ciclos infinitos.