Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmos de Dekker y Peterson

Sistemas Operativos
by

Elisa Guadalupe

on 3 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmos de Dekker y Peterson

EQUIPO 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 ahi.
Versión 3: Colisión región critica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región critica.
Versión 4: Postergación indefinida. Aunque los procesos no estan en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda. Combinación entre:
Primer intento: donde se usa la variable turno (ahora usamos turno para indicar quien tiene prioridad para entrar a su sección critica).
Cuarto intento.
Funcionamiento: Cuando P0 quiere entrar en su sección critica pone señal[0]=a cierto; y comprueba la señal de P1.
Si esta en falso entra inmediatamente.
Si esta en cierto consulta turno:
Si turno es==0; sigue verificando la señal de P1.
Si turno es==1; desactiva su señal y espera hasta que turno==0. Algoritmo de Dekker:Solución final El algoritmo de Dekker es un algoritmos 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 primero algoritmos de exclusión mutua inventado, implementado por Edsger Dijkstra.
Existen 5 versiones del algoritmo Dekker , teniendo ciertos fallos los primeros 4. La versión 5 es la que trabaja mas eficientemente, siendo una combinacion de la 1 y la 4. Algoritmo de Dekker Diseñado para poder pasar el control de ejecución entre ellos, no es una técnica apropiada para dar soporte al procesamiento concurrente. Cuando hay diferencias grandes de velocidad es el proceso mas lento el que marca el ritmo.
Programa UNO;
Variables
turno:Entero;
Inicialización
turno=1; Algoritmo de Dekker: Primer Intento Verifico la sección critica del otro proceso y coloco una señal al entrar y salir en su sección critica.
Si el Quantum de tiempo de los procesos finaliza precisamente despues del cambio de la variable PnQE, pero antes de la validación del "while", puede darse que las dos condiciones son verdaderas y los procesos se queden en un ciclo infinito a este proceso se le conoce cono INTERBLOQUEO.
Programa DOS;
Variables :
P1QE, P2QE:BOOL;
Inicialización:
P1QE=false;
P2QE=false; Algoritmo de Dekker: Segundo intento Algoritmo de Dekker: Tercer intento Una vez que un proceso a puesto su señal en cierto, el otro no puede entrar a su seccion critica hasta que el primero salga de ella. Se garantiza la exclusión mutua, sin embargo, se generara interbloqueo si ambos procesos ponen su señal a cierto antes que ambos hayan ejecutado el "while". Además si un proceso falla en su sección critica, el otro queda bloqueado permanentemente. Algoritmo de Dekker: Cuarto intento. El interbloqueo se había originado porque casa proceso establecía su señal sin conocer el estado del otro proceso. Para solucionarlo haremos que los procesos activen y desactiven su señal. Esta solución garantiza exclusión mutua y prácticamente evita el interbloqueo.
Aunque podría darse la secuencia:
P0 pone señal [0] a cierto.
P1 pone señal [1] a cierto.
P0 comprueba señal [1].
P0 pone señal [0] a falso.
P1 pone señal [1] a falso.
P0 pone señal [0] a cierto.
P1 pone señal [1] a cierto.
Esta situación de bloqueo puede prolongarse mucho tiempo. Algoritmo de Peterson El algoritmo de Peterson, también conocido como solución de Peterson, es un algoritmo de programación concurrente para exclusion mutua, que permite a dos o mas procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando solo memoria compartida para la comunicación.
Peterson desarrollo el primer algoritmo (1981) para dos procesos que fue una simplificación del algoritmo de Dekker para dos procesos.
Posteriormente este algoritmo fue generalizado para N procesos. Mas simple que el de Dekker, garaniza la exclusión mutua.
Cada proceso tiene un turno para entrar en la sección critica.
Si un proceso desea entrar a la sección critica, debe activar su señal y puede que tenga que esperar a que llegue su turno.
Impide el interbloqueo ya que si un proceso se encuentra esperando en el "while", entonces la señal y el turno del otro proceso estan activadas. El proceso que esta esperando entrara en su sección critica cuando la señal o el turno del otro se desactiven Referencias http://es.wikipedia.org/wiki/Algoritmo_de_Peterson
http://es.wikipedia.org/wiki/Algoritmo_de_Dekker
http://www.infor.uva.es/~figonzalez/apuntes/Tema6.pdf
http://www.slideshare.net/mastermind87/algoritmo-de-dekker ALGORITMO DE DEKKER Y PETERSON
Full transcript