Algoritmo Dekker y Peterson
Algoritmo Dekker y Peterson
Algoritmo Dekker y Peterson
Algoritmo Dekker
El algoritmo de Dekker es un algoritmo de programación concurrente para la exclusión
mutua, que permite a dos procesos o hilos de ejecución compartida 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 critica simultáneamente, el
algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en
su sección critica, deberá esperar su finalización.
Existen 5 versines del algoritmo Dekker, teniendo ciertos fallos los primeros 4. La versión 5
es la que trabaja mas eficientemente, siendo una combinación de la 1 y 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 critica no garantizada 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 están en interbloqueo,
un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca
suceda.
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'' */}
Algoritmo de Peterson
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.
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 solo memoria compartida para la
comunicación.
Peterson desarrollo el primer algoritmo (¡981) para dos procesos que fue una simplificación
de Dekker para dos procesos. Posteriormente este algoritmo fue generalizado para N
procesos.
// 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;