Algoritmo de Eisenberg - McGuire

De Wikipedia, la enciclopedia libre

Es el primer algoritmo conocido que soluciona el problema de la sección crítica para n procesos, con un límite de n-1 turnos.

Fue realizado por Murray A. Eisenberg y Michael R. McGuire en la década de 1970.

Algoritmo[editar]

Todos los procesos comparten las siguientes variables, siendo n el número de hebras. 

       enum estado = {IDLE, ESPERANDO, ACTIVO};
       estado flags[n];
       int turno;

A la variable turno se le asigna aleatoriamente un valor entre 0 y n-1 al inicio del algoritmo.

La variable flags (bandera) de cada hilo se pone en estado ESPERANDO cada vez que tiene intención de entrar en la sección crítica. La variable flags es inicializada en IDLE (inactivo). 

  Repetir {

		/* anunciar que  necesitamos el recurso */
		flags[i] := ESPERANDO;

		/* Escanear los procesos partiendo desde el que posee el turno. */
		/* Repite hasta encontrar todos los procesos en IDLE */
		indice := turno;
		mientras (indice != i) {
			Si (flags[índice] != IDLE) indice := turno;
			Si_no índice := (indice+1) mod n;
		}

		/* Reclamamos temporalmente el Recurso */
		flags[i] := ACTIVO;

		/* Encontrar el primer proceso activo además de nosotros, si existe */
		indice := 0;
		mientras ((índice < n) && ((indice = i) || (flags[indice] != ACTIVO))) {
			indice := indice+1;
		}

	/* Si no hay otros procesos activos, y tenemos el turno, o si todos los demás tienen estado IDLE, proceder, en otro caso, repetir */
        } Hasta que ((indice >= n) && ((turno = i) || (flags[turno] = IDLE)));

        /* INICIO SECCIÓN CRÍTICA */

	/* reclamar el turno y proceder */
	turno := i;

        /* Código de Sección Crítica */

        /* FIN de SECCIÓN CRÍTICA */

        /* Encuentra un proceso que no esté IDLE */
	/* (Si no hay otro nos encontraremos a nosotros mismos.) */
	indice := (turno+1) mod n;
	mientras (flags[indice] = IDLE) {
		indice := (indice+1) mod n;
	}

	/* Dar el turno a una hebra que lo necesita, o mantenerlo */
	turno := indice;

	/* Hemos acabado */
	flags[i] := IDLE;

       /* Sección de restante */

Véase también[editar]

Referencias[editar]

Enlaces externos[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Eisenberg_-_McGuire&oldid=158232104»