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

No description
by

Azarael Itai Romero Ramirez

on 6 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmos de Dekker y Peterson

El algoritmo de Dekker es un algoritmo de programación concurrente (simultáneamente se ejecutan múltiples tareas interactivas) para exclusión mutua, con el fin de evitar el uso simultáneo de recursos comunes, como variables globales, por fragmentos de código (conocidos como secciones críticas), que permite a dos procesos compartir un recurso sin conflictos.

Fue uno de los primeros algoritmos de exclusión mutua inventados e implementado por Edsger Dijkstra.

Algoritmo de Dekker
Algoritmos de Dekker y Peterson
Mientras el valor de la variable "turno" sea distinto al de su identificador de proceso debe esperar.

Cuando coincida entrará en la sección crítica.

Cuando un proceso sale de la sección crítica, actualiza “turno” con el código de otro proceso en espera.
El algoritmo maneja una variable global “turno” para controlar la entrada en la sección crítica.

Cualquier proceso que desee entrar en su sección crítica comprobará primero el valor de la variable “turno”.

Algoritmo de Dekker
Si dos 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.

Algoritmo de Dekker
Simplifica al algoritmo de Dekker, garantiza la exclusión mutua:
•Cada proceso tiene un turno para entrar en la sección crítica.
• Si un proceso desea entrar en la sección crítica, debe activar su señal y puede que tenga que esperar a que llegue su turno.

Peterson desarrolló el primer algoritmo en 1981 para dos procesos que fue una simplificación del algoritmo de Dekker para dos procesos. Posteriormente este algoritmo fue generalizado para N procesos.
Algoritmo de Peterson
Si sólo uno de los procesos intenta acceder a la sección crítica lo podrá hacer sin ningún problema.

Sin embargo, si dos procesos intentan entrar a la vez el valor de turno se pondrá a 1 y 2 pero sólo un valor de ellos permanecerá al escribirse sobre el otro, permitiendo el acceso de un proceso a su región crítica.
Algoritmo de Peterson

// Variables compartidas
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[k] == i)] do;
}
<sección crítica>
bandera[i] = -1;
Algoritmo para N procesos
Delgado Meza Julieta Jocelyne
Martínez Jiménez Francisco de Jesús
Medina López Enid Teresa
Orozco Arizaga José Luis
Romero Ramírez Azarael Itai

Integrantes del equipo
¿Cómo funciona?
Algoritmo de Dekker
¿Cómo funciona?
Dekker hizo 5 versiones de su algoritmo, teniendo fallas en los primeros cuatro. La ultima versión es la que trabaja más eficientemente, siendo una combinación de la primera y la cuarta versión.

Algoritmo de Dekker
Algoritmo de Peterson para 2 procesos
Diseñado para poder pasar el control de ejecución entre los procesos, pero no es una técnica apropiada para dar soporte al procesamiento concurrente.
Algoritmo de Dekker
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.
Proceso O
... ...
/*esperar*/
while (turno!=0);
/*sección crítica*/
... ...
turno=1;
... ...
Proceso 1
... ...
/*esperar*/
while (turno!=1);
/*sección crítica*/
... ...
turno=0;
... ...
Verifica la sección crítica del otro proceso y coloca una señal al entrar y salir en su sección crítica.
Algoritmo de Dekker
Versión 2: 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.
Algoritmo de Dekker
Versión 3: Problema interbloqueo
Los procesos ya no están en interbloqueo, pero un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.
Algoritmo de Dekker
Versión 4: Postergación indefinida
Proceso O
... ...
/*esperar*/
while (señal[1]);
señal[0] = cierto;
/*sección crítica*/
... ...
señal[0] = falso;
... ...
Proceso 1
... ...
/*esperar*/
while (señal[0]);
señal[1] = cierto;
/*sección crítica*/
... ...
señal[1] = falso;
... ...
Algoritmo de Dekker
Versión 2: Colisión región crítica no garantiza la exclusión mutua
Ambos procesos están en su sección crítica, esto se debe a que esta solución no es independiente de la velocidad de ejecución relativa de los procesos.
Si uno de los procesos falla dentro de su sección crítica el otro quedará bloqueado permanentemente.
No garantiza la Exclusión Mutua:
1. P0 ejecuta el while y encuentra señal[1] a falso.
2. P1 ejecuta el while y encuentra señal[0] a falso.
3. P0 pone señal[0] a cierto y entra en su sección crítica.
4. P1 pone señal[1] a cierto y entra en su sección crítica.
Las desventajas de esta versión son:
Combinación entre el primer intento, donde se usa la variable turno (se utiliza turno para indicar quien tiene prioridad para entrar a su sección crítica), y el cuarto intento.
Algoritmo de Dekker
Versión 5
p1: bandera[1] = true
turno = 0

while( bandera[0] && turno == 0 );
//no hace nada; espera.

// sección crítica

// fin de la sección crítica
bandera[1] = false
Proceso O
... ...
señal[0] = cierto;
/*esperar*/
while (señal[1]);
/*sección crítica*/
... ...
señal[0] = falso;
... ...
Proceso 1
... ...
señal[1] = cierto;
/*esperar*/
while (señal[0]);
/*sección crítica*/
... ...
señal[1] = falso;
... ...
bandera[0] = false
bandera[1] = false
turno = 0
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
Una vez que un proceso ha puesto su señal en cierto, el otro no puede entrar a su sección crítica hasta que el primero salga de ella.

Garantiza la exclusión mutua, sin embargo, se
generará interbloqueo si ambos procesos ponen su
señal a cierto antes de ambos hayan ejecutado el
while. Además, si un proceso falla en su
sección crítica, el otro queda
bloqueado permanentemente.
Algoritmo de Dekker
Versión 3: Problema interbloqueo
El interbloqueo que se había originado porque cada proceso establecía su señal sin conocer el estado del otro proceso, se soluciona haciendo que los procesos activen y desactiven su señal.
Proceso O
... ...
señal[0] = cierto;
/*esperar*/
while (señal[1]){
señal[0] = falso;
/*retardo*/
señal[0] = cierto;
}
/*sección crítica*/
... ...
señal[0] = falso;
... ...
Proceso 1
... ...
señal[1] = cierto;
/*esperar*/
while (señal[0]){
señal[1] = falso;
/*retardo*/
señal[1] = cierto;
}
/*sección crítica*/
... ...
señal[1] = falso;
... ...
Proceso O
... ...
señal[0] = cierto;
while (señal[1])
if (turno==1){
señal[0] = falso;
while (turno==1);
/*esperar*/
señal[0] = cierto;
}
/*sección crítica*/
turno = 1
señal[0] = falso;
... ...
Proceso 1
... ...
señal[1] = cierto;
while (señal[0])
if (turno==0){
señal[1] = falso;
while (turno==0);
/*esperar*/
señal[1] = cierto;
}
/*sección crítica*/
turno = 0
señal[1] = falso;
... ...
Algoritmo de Dekker
Versión 5
Cuando P0 quiere entrar en su sección crítica pone señal[0]=cierto y comprueba la señal de P1.
Si está a falso, entra inmediatamente.
Si está a cierto, consulta turno:
Si turno==0; sigue verficando la señal de P1.
Si turno==1; desactiva su señal y espera
hasta que turno==0;
Full transcript