Diferencia entre revisiones de «Algoritmo de Peterson»
| Línea 13: | Línea 13: | ||
//no hace nada; espera. //no hace nada; espera. |
//no hace nada; espera. //no hace nada; espera. |
||
// sección crítica // sección crítica |
// sección crítica // sección crítica |
||
//vales |
//vales vrga |
||
// fin de la sección crítica // fin de la sección crítica |
// fin de la sección crítica // fin de la sección crítica |
||
bandera[0] = 0 bandera[1] = 0 |
bandera[0] = 0 bandera[1] = 0 |
||
Revisión del 17:20 11 may 2011
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 memoria compartida para la comunicación.
Peterson desarrolló 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.
Algoritmo para dos procesos
bandera[0] = 0
bandera[1] = 0
turno = 0
p0: bandera[0] = 1; p1: bandera[1] = 1;
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
//vales vrga
// fin de la sección crítica // fin de la sección crítica
bandera[0] = 0 bandera[1] = 0
Los procesos p0 y p1 no pueden estar en la sección crítica al mismo tiempo: si p0 está en la sección crítica, entonces bandera[0] = 1, y ocurre que bandera[1] = 0, con lo que p1 ha terminado la sección crítica, o que la variable compartida turno = 0, con lo que p1 está esperando para entrar a la sección crítica. En ambos casos, p1 no puede estar en la sección crítica.
Algoritmo para N procesos (pseudo-codigo)
// 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[j] == i)] do;
}
<sección crítica>
bandera[i] = -1;