Informatica

Algoritmo de Dekker

1 De Wikipedia,

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 unrecurso 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, elalgoritmo elige un proceso según una variable turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Existen cinco versiones del algoritmo Dekker, teniendociertos 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 almismo 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 nuncasuceda.

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;
while (bandera[1-proc_id] == cierto)
{
if (turno == 1-proc_id)
{
bandera[proc_id] = 0;
while (turno == (1-proc_id)) /* espera a que sea su turno deintentar */;
bandera[proc_id] = 1;
}
}
/* ''Sección crítica'' */
turno = 1-proc_id; /* es el turno del otro proceso */
bandera[proc_id] = 0;...