Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 195 vistas

    Dekker

    Cargado por

    david lopez
    El documento describe cinco versiones del algoritmo de Dekker para exclusión mutua entre dos procesos que comparten un recurso crítico. La versión 1 usa variables de estado pero puede generar interbloqueo. La versión 2 evita el interbloqueo pero un proceso puede quedar bloqueado. La versión 3 introduce retrasos aleatorios pero un proceso puede esperar indefinidamente. La versión 4 mejora la 3 pero aún permite esperas largas. La versión 5 es una combinación óptima de las versiones 1 y 4 que garantiza exclusión mut

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Dekker

    Cargado por

    david lopez
    195 vistas5 páginas
    El documento describe cinco versiones del algoritmo de Dekker para exclusión mutua entre dos procesos que comparten un recurso crítico. La versión 1 usa variables de estado pero puede generar interbloqueo. La versión 2 evita el interbloqueo pero un proceso puede quedar bloqueado. La versión 3 introduce retrasos aleatorios pero un proceso puede esperar indefinidamente. La versión 4 mejora la 3 pero aún permite esperas largas. La versión 5 es una combinación óptima de las versiones 1 y 4 que garantiza exclusión mut

    Descripción original:

    trabajo dekker

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe cinco versiones del algoritmo de Dekker para exclusión mutua entre dos procesos que comparten un recurso crítico. La versión 1 usa variables de estado pero puede generar interbloqueo. La versión 2 evita el interbloqueo pero un proceso puede quedar bloqueado. La versión 3 introduce retrasos aleatorios pero un proceso puede esperar indefinidamente. La versión 4 mejora la 3 pero aún permite esperas largas. La versión 5 es una combinación óptima de las versiones 1 y 4 que garantiza exclusión mut

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    195 vistas5 páginas

    Dekker

    Cargado por

    david lopez
    El documento describe cinco versiones del algoritmo de Dekker para exclusión mutua entre dos procesos que comparten un recurso crítico. La versión 1 usa variables de estado pero puede generar interbloqueo. La versión 2 evita el interbloqueo pero un proceso puede quedar bloqueado. La versión 3 introduce retrasos aleatorios pero un proceso puede esperar indefinidamente. La versión 4 mejora la 3 pero aún permite esperas largas. La versión 5 es una combinación óptima de las versiones 1 y 4 que garantiza exclusión mut

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 5

     evita que dos procesos puedan acceder al mismo tiempo a la región crítica.

    Una vez que un proceso ha puesto su señal en verdadero, el otro proceso no puede
    entrar en la sección critica hasta que el primer proceso salga de ella.
    Variables
    P1A, P2A: Bool;
    Inicialización
    P1A = false;
    P2A = false;
    P1 (Proceso 1) P2 (Proceso 2)
    Repeat Repeat
    Hace_Cosas(); Hace_Cosas();
    While P2A Do; While P1A Do;
    P1A = true; P2A = true;
    REGION_CRITICA(); REGION_CRITICA();
    P1A = False; P2A = False;
    Hace_mas_cosas(); Hace_mas_cosas();
    Until Fin Until Fin

    Se garantiza la exclusión mutua, sin embargo se genera interbloqueo si ambos


    procesos ponen su señal en verdadero antes que ambos hayan ejecutado el while.
    Además si un proceso falla en su sección critica, el otro queda bloqueado
    permanentemente.

     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.
    El interbloqueo se había originado por que cada proceso establecía su señal sin
    conocer el estado del otro proceso, para solucionarlo se hizo que los procesos
    activaran y desactivaran sus señales, esta solución garantiza la exclusión mutua y
    evita el interbloqueo.

    Variables
    P1, P2: Bool;
    Inicialización
    P1 = false;
    P2 = false;
    P1 (Proceso 1) P2(Proceso 2)
    Repeat Repeat
    Hace_Cosas(); Hace_Cosas ();
    P1 = true; P1 = true;
    While P2 Do; While P2 Do;
    Begin Begin
    P1 = false; P2 = false;
    Delay (random()); Delay (random());
    P1 = true; P2 = true;
    end; end;
    REGION_CRITICA(); REGION_CRITICA();
    P1 = False; P2 = False;
    Hace_mas_cosas(); Hace_mas_cosas();
    Until Fin Until Fin

    Aunque al tener un tiempo de espera aleatorio entre la terminación de un proceso


    y el comienzo del siguiente, podría quedar mucho tiempo entre procesos.

    Prueba escritorio V4
    Para cada proceso una variable, v0 para P0 y v1 para P1 respectivamente, que
    indica si el correspondiente proceso está usando el recurso.

    P0 P1
    a: Bucle Bucle
    b: Establecer v0 en verdadero Establecer v1 en verdadero
    c: Espera hasta que v1 sea falso Espera hasta que v0 sea falso
    d: SECCION CRITICA SECCION CRITICA
    e: Establecer v0 en falso Establecer v0 en falso
    f: SECCION NO CRITICA SECCION NO CRITICA
    g: Fin del bucle Fin del bucle

    o Está garantizado que no entren ambos procesos al mismo tiempo en sus


    secciones críticas.
    o Pero se bloquean mutuamente en caso que lo intentan simultáneamente
    que resultaría en una espera infinita.

     Versión 5: El quinto algoritmo de Dekker es la versión optimizada y que no


    presenta problemas como las cuatro versiones anteriores, para su estructuración
    se hace una combinación de dos algoritmos de acuerdo al orden de prioridad de
    desempeño y funcionamiento de las cuatro versiones conocidas.

    Variables
    P1, P2: Bool;
    turno: Entero;
    Inicialización
    P1 = false;
    P2 = false;
    turno = 1;
    P1 (Proceso 1) P2 (Proceso 2)
    Repeat Repeat
    Hace_Cosas(); Hace_Cosas();
    P1 = true; P2 = true;
    While P2 Do While P1 Do
    Begin Begin
    if(turno = 2) if(turno = 1)
    Begin Begin
    P2 = false; P1 = false;
    Delay (random()); Delay (random());
    P2 = true; P1 = true;
    end; end;
    end; end;
    REGION_CRITICA(); REGION_CRITICA();
    turno = 1; turno = 2;
    P2 = False; P1 = False;
    Hace_mas_cosas(); Hace_mas_cosas();
    Until Fin Until Fin

    Se realiza las tareas iniciales, luego se verifica si hay otro procesos que puede
    entrar, si lo hay se entra al ciclo y si es el turno de algún otro proceso, cambia su
    estado a ya no poder entrar a la sección crítica y nuevamente verifica si es el turno
    de algún otro proceso, si lo es se queda en un ciclo hasta que se da un cambio de
    turno, luego nuevamente retoma su estado de poder entrar a la sección critica,
    regresa al ciclo y verifica si hay otro proceso que puede entrar entonces
    nuevamente entra al ciclo, de lo contrario entra a la sección critica.
    Quinta versión del algoritmo de Dekker Algoritmo Optimo, este algoritmo es una
    combinación del algoritmo 1 y 4, este algoritmo garantiza la exclusión mutua, el
    progreso y tiene una espera limitada.

    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 de ejecución
    compartir un recurso sin conflictos utilizando solo memoria compartida para la
    comunicación.
    Peterson desarrollo el algoritmo en 1981 para dos procesos, lo cual fue una
    simplificación del algoritmo de Dekker para dos procesos, posteriormente este
    algoritmo fue generalizado para “N” procesos.

    Algoritmos para 2 procesos

    bandera[0] = false
    bandera[1] = false
    turno // No es necesario asignar un turno
    p0: bandera[0] = true p1: bandera[1] = true
    turno = 1 turno = 0
    while( bandera[1] && turno == 1 ); while( bandera[0] && turno == 0 );
    { //no hace nada; espera. } { //no hace nada; espera. }
    // sección crítica // sección crítica
    // fin de la sección crítica // fin de la sección crítica
    bandera[0] = false bandera[1] = false
    Algoritmos para N procesos

    bandera: array[0..N-1] of -1..n-2; /* inicializada a –1 */


    turno: array[0..N-2] of 0..n-1; /* inicializada a 0 */

    // Protocolo para Pi ( i=0,...,N-1 )


    j:0..N-2; /* variable local indicando la etapa */
    for j = 0 to N-2
    {
    bandera[i] = j;
    turno[j] = i;
    while [(∃ k ≠ i : bandera[k] ≥ j) ∧ (turno[j] == i)] do;
    }
    <sección crítica>
    bandera[i] = -1;

    o Más simple que el de Dekker, garantiza la exclusión mutua.


    o Cada proceso tiene un turno para entrar en la sección crítica.
    o Si un proceso desea entrar en la sección crítica, debe activar su señal y debe
    esperar a que llegue su turno.
    o Impide el interbloqueo ya que si un proceso se encuentra esperando en el
    while, entonces la señal y el turno del otro proceso están activadas, el
    proceso que está esperando entrara en su sección critica cuando la señal o
    el turno del otro se desactiven.

    REFERENCIAS

     https://es.wikipedia.org/wiki/Algoritmo_de_Dekker
     http://aprendiendo-software.blogspot.com/2011/12/algoritmo-de-dekker-version-
    5.html
     http://algoritmosdekker.blogspot.com/2018/02/versiones-del-algoritmo-de-
    dekker.html

    También podría gustarte