Programacin Concurrente
Algoritmo de Dekker.
La exclusin mutua la podramos definir como una operacin de procesos concurrentes (comunicacin requerida entre dos o ms procesos), y que tiene la capacidad de prohibir a los dems procesos realizar una accin cuando un proceso haya obtenido el permiso. El ALGORITMO DE DEKKER: es un algoritmo de programacin concurrente para exclusin mutua, que permite a dos procesos o hilos de ejecucin compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusin mutua inventados, implementado por Edsger Dijkstra. Si ambos procesos intentan acceder a la seccin critica simultneamente, el algoritmo elige un proceso segn un variable turno. Si el otro proceso est ejecutando en su seccin critica, deber esperar su finalizacin. Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos en los primeros cuatro. La versin 5 es la que trabaja ms eficientemente, siendo una combinacin de la 1 y la 4.
Versin 1: Alternancia estricta. Garantiza la exclusin mutua, pero su desventaja es que acopla los procesos fuertemente, eso significa que los procesos lentos atrasan a los procesos rpidos.
Versin 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ah.
Versin 3: colisin regin crtica no garantiza la exclusin mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la regin crtica.
Versin 4:
postergacin indefinida. Aunque los procesos no estn en
interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.
Programacin Concurrente
Versin 5: Algoritmo ptimo, este algoritmo es una combinacin del algoritmo 1 y 4, garantiza la exclusin mutual, el progreso y tiene una espera limitada. A continuacin el pseudocdigo:
Algoritmo
Descripcin
Programacin Concurrente
Se
realiza las tareas iniciales, luego se verifica si hay otros procesos que Puede entrar, si lo hay se entra al ciclo y si es el turno de algn otro Proceso (lnea 12 y 34) cambia su estado a ya no poder entrar a la seccin Critica y nuevamente verifica si es el turno de algn otro proceso (lnea 15 y 37) si lo es se queda enciclado hasta que se da un cambio de turno, luego Nuevamente retoma su estado de poder entrar a la seccin critica, regresa Al ciclo y verifica si hay otro proceso que puede entrar entonces Nuevamente se encicla, de lo contrario entra a la seccin critica. Al salir de la seccin critica el proceso cambia su turno, cambia su estado y Realiza sus tareas finales. (Lnea 20 y 42).
Programacin Concurrente
Ejemplo:
Como actuara el algoritmo de Dekker teniendo el problema de unos carros en el Siguiente crucero:
Suponga que los carros de Cuauhtmoc quieren pasar al mismo tiempo que los de 20 de noviembre. Como actuara el algoritmo de Dekker para que no hubiera colisiones en la regin crtica.
Programacin Concurrente
El algoritmo de Dekker declara una bandera para cada proceso, en este caso ser la bandera cuau_1 y la bandera nov_2. Y declarando una variable turno asignada a 1 (Cuauhtmoc en verde). Indicando que primero pasarn los carros de cuau_1. Antes de poner el semforo de cuau en verde verifica si hay carros que puedan pasar, si los hay se entra en un ciclo para que avancen los carros de Cuauhtmoc, pero si hay carros de Noviembre avanzando y es el turno de los de noviembre, el semforo se pone en rojo para que los carros de cuau no choquen (seccin crtica) y nuevamente verifica si es el turno de los de noviembre, si lo es se queda enciclado hasta que se da un cambio de turno y comiencen a avanzar los de
Cuauhtmoc, regresa al ciclo y verifica si hay otro carro que quiera pasar, entonces nuevamente se encocla, de lo contrario entra a la seccin crtica. Al salir el carro de la seccin crtica cambia su turno, cambia su estado y se aleja del crucero. Repitindose el mismo proceso para los carros de 20 de noviembre y alternando el semforo no en tiempos definidos, si no conforme quieran pasar los carros.
