Seguimos con concurrencia: ejemplo de uso de semáforos

¡Buenas! Hacía varias semanas que no podía sacar tiempo para escribir alguna entrada, pero bueno, aquí volvemos de nuevo :D, esta vez seguimos hablando de la concurrencia de procesos, y voy a intentar explicar un poco el uso de semáforos mediante un ejemplo 🙂

Bien, lo primero, ¿qué es un semáforo?, el concepto se asemeja bastante a la realidad, vendría a ser una metáfora del semáforo de tráfico, si está en rojo, no podremos pasar, mientras que si está en verde, avanzaremos, podría darse el caso de:

no puedes pasar

Hablando ya en términos más técnicos, un semáforo vendría a ser un tipo de dato abstracto que está en el limbo entre un TDA de alto nivel y de bajo nivel, en el caso de JAVA, tendremos que implementarlo por nosotros mismos, cosa que dejo para una próxima entrada 🙂

Podemos hablar de dos tipos de semáforos, el binario, que toma valores en el conjunto {0,1}, y el general, que toma valores en el conjunto de los números enteros positivos Z+.

Otra cosa importante a comentar son las operaciones que podemos utilizar, en este caso comentaremos 2:

– Operación WAIT –> El proceso que haga Wait decrementa el semáforo en 1 y se bloquea si su valor está a 0 (el decremento se hace una vez “pasa por el semáforo”).
– Operacion SIGNAL –> Es la operación inversa, si tenemos un semáforo a 0, es decir, en rojo, y un proceso hace Signal sobre él, lo pone “verde”, con valor a 1

Esto en el caso del semáforo binario, para el general, si tenemos el valor 10 y hacemos 10 veces Wait, el nuevo valor será 0, y viceversa con la operación Signal, los generales se suelen utilizar cuando un recurso puede ser accedido por más de un proceso al mismo tiempo, por ejemplo. 🙂

Una vez dicho esto, vamos con un ejemplo práctico muy sencillo y algo famoso:

Supongamos que disponemos de un tarro de galletas, y ‘k’ niños accediendo al bote, cuando este toca a su fin, los niños avisan a la madre para que reponga el tarro.

Primero, tendremos 3 clases en nuestro proyecto JAVA, una clase ‘niño’, encargada de actuar como el monstruo de las galletas xD, la clase ‘mama’, encargada de reponer el tarro cuando los niños lloren porque se acabó su “mirienda” (al estilo Shin Chan xD), y por último, una clase principal encargada de ‘crear’ a los niños y a la madre, para después lanzarlos ;).

Una cosa que creo que ya expliqué en la entrada anterior: las clases que se lanzan concurrentemente implementan a Runnable, y esto conlleva sobrecargar el método run ;).

clase principal:

public class TARROGALLETAS {
	public void main () {
		galletas=n
		semáforo NoHayGalletas -> 0
		semáforo HayGalletas -> 0
		semáforo mutex -> 1
		CrearNiños()
		CrearMadre()
		LanzarNiños()
		LanzarMadre()
	}
}

Veamos la clase niño:

public class niño implements Runnable {  
	public void run () {
		while(true)	     	     //Los niños son pachones y siempre estarán comiendo galletas
			Wait(mutex)  		//Aquí evitamos que dos procesos comprueben el número de galletas a la vez, ya que podría darse una falsa lectura
			if(galletas==0){ 	//Si no hay galletas...
				Signal(NohayGalletas)	//Desbloquea a la madre para que rellene
				Wait(HayGalletas)	//Espera a que la madre rellene para continuar
				galletas-;		//coge galleta 🙂
			}else{
				galletas--; 	//una galleta menos
			}
                        signal(mutex)
	}
}

Vamos con la clase mamá:

public class mama implements Runnable {      
	public void run () {
		while(true)	     	     //La madre siempre estará esperando para reponer el tarro
			Wait(NoHayGalletas)  //Aquí se bloquea por que el semáforo "NoHayGalletas" está a 0
			Wait(mutex)
			galletas=n           //Relleno el tarro de galletas
			Signal(mutex)	     //El semáforo mutex impide que 2 procesos comprueben la variable "galletas" a la vez 😉
			Signal(HayGalletas)  //Aviso a los niños de que hay galletas poniendo a 1 el semáforo "HayGalletas"
	}
}

Disculpad si hay algún fallo en el código, no está compilado ;), es solo a modo de ejemplo y en pseudocódigo.

Por último, comentar que la variable “galletas” y los semáforos, son compartidas por niño y mama, de ahí que la variable galletas deba leerse/escribirse en exclusión mútua.

Bien, espero que os haya sido de ayuda, comentad si teneis alguna duda 😉

HackSaludos!

Anuncios

Acerca de Darkvidhck

Estudiante de ingeniería informática, haciendo mis pinitos como desarrollador web, programador, gamer y Linuxero. Aficionado a la seguridad. Eterno viciado al conocimiento.
Esta entrada fue publicada en Programación y etiquetada , , , , , . Guarda el enlace permanente.

9 respuestas a Seguimos con concurrencia: ejemplo de uso de semáforos

  1. Alfonso dijo:

    Genial el ejemplo :-).
    Muchas gracias por compartir tus conocimientos.

  2. Qué tiempos aquellos en los que yo estudiaba esto. No parece que hiciese un año de esto…
    Este problema, junto con el de los filósofos, es el problema estándar para aprender a programar concurrentemente.
    Con los filósofos nunca llegué a comprender por qué necesitan dos tenedores para comer. ¿No les bastará con uno? ¿Quieren que les acusen de apropiación indebida?

  3. Gusseppe dijo:

    Pienso que en la clase niño despues de la linea 11 debe haber un signal(mutex) para desbloquear a otro niño.

  4. jorge dijo:

    Hola! entiendo que hay un problema en el run de niño, ya que hace un wait(mutex) y en caso de no haber galletas nunca levanta ese mutex para que la madre pueda acceder.
    podría ser que quede así el código? o me está faltando algo?

    while(true) {
    Wait(mutex)
    if(galletas==0){
    Signal(NohayGalletas)
    }else{
    galletas–;
    }
    Signal(mutex)
    }

  5. Víctor dijo:

    En mi opinión, la clase “mama” está bien, pero la clase “niño” no ya que cuando ejecuta la instrucción Signal(NoHayGalletas), la clase “mama” nunca podrá rellenar el tarro ya que se quedará bloqueada en la instrucción Wait(mutex). Por ello, he realizado unas modificaciones en la clase “niño” y queda finalmente así:

    public class niño implements Runnable {
    public void run () {
    while(true) {
    Wait(mutex)
    if(galletas==0) {
    Signal(NohayGalletas)
    Signal(mutex)
    Wait(HayGalletas)
    Wait(mutex)
    galletas–;
    }
    else galletas–;
    Signal(mutex)
    }
    }
    }

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s