Algoritmo de Dekker

Algoritmo de Dekker

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 turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

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;
    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 de intentar */;
          bandera[proc_id] = 1;
       }
    }
    /* ''Sección crítica'' */
    turno = 1-proc_id;                 /* es el turno del otro proceso */
    bandera[proc_id] = 0;
    /* ''Sección no crítica'' */
 }

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Algoritmo de Dekker — pre shared int bandera[2] = 0,0;    /* Variables compartidas */ shared int turno      = 0;       /* Del Moldibot          */ while (1)    bandera[proc id] = 1;    while (bandera[1 proc id] == 1)           if (turno == 1 proc id)       … …   Enciclopedia Universal

  • Dekker — Saltar a navegación, búsqueda Dekker es un apellido que puede referirse a las siguientes personas: Desmond Dekker, cantante de ska; Erik Dekker, ciclista retirado ganado …   Wikipedia Español

  • Algoritmo de Peterson — El algoritmo de Peterson, también conocido como solución de Peterson, es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo… …   Wikipedia Español

  • Algoritmo de la panadería de Lamport — El algoritmo de la panadería de Lamport es un algoritmo de computación creado por el científico en computación Dr Leslie Lamport, para implementar la exclusión mutua de N procesos o hilos de ejecución. Contenido 1 Algoritmo 2 Entrada en sección… …   Wikipedia Español

  • Exclusión mutua (informática) — Para otros usos de este término, véase Exclusión mutua. Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar el uso simultáneo de recursos comunes, como variables …   Wikipedia Español

  • Regresión no lineal — Saltar a navegación, búsqueda En estadística, la regresión no lineal es un problema de inferencia para un modelo tipo: basado en datos multidimensionales x,y, donde f es alguna función no lineal respecto a algunos parámetros desconocidos θ. Como… …   Wikipedia Español

  • Curva ROC — Saltar a navegación, búsqueda Contenido 1 Curva ROC (Receiver Operating Characteristic) 2 Conceptos Básicos 3 El espacio ROC 4 …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”