Usuario:Javramirez9/Algoritmo de Eisenberg - McGuire

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 decada de 1970.

Algoritmo

editar

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

       enum pstate = {IDLE, WAITING, ACTIVE};
       pstate flags[n];
       int turn;

A la variable turno se le asigna aleatoriamente un valor entre 0 y n-1 al incio 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 flasgs 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) && ((vuelta = 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
  • http://portal.acm.org/citation.cfm?id=361895

Enlaces externos

editar