hola a todos. tengo una consulta por un ejercicio de sincronizacion que la verdad no lo puedo terminar de plantear.

ahi va :


Se tiene un programa para simular la ejecución de penales de un partido de fútbol, el cual
consta de tres procesos: árbitro, jugador y arquero. El pseudo-código es el siguiente:

 

//proceso arbitro : 





while ( TRUE ) { 



	dar_orden () ; 

	validar_tiro () ; 



}



//proceso jugador : 



while ( TRUE ) { 



	posicionarse();

	patear (); 



	if ( GOL == TRUE ) { 

		festejar();

	} else {

		lamentarse (); 

	}



}



//proceso arquero : 



while ( TRUE ) {



	posicionarse (); 

	atajar(); 



	if ( GOL == FALSE ) { 

		festejar (); 

	} else { 

		lamentarse (); 

	} 

}

Las reglas que se deben cumplir son las siguientes:
• Existen cinco procesos jugadores, un proceso árbitro y un proceso arquero.
• Los jugadores no pueden patear si el árbitro no lo indicó.
• El arquero no puede atajar si el jugador no pateó.
• El árbitro solo puede dar la orden cuando el jugador y el arquero están posicionados.
• Existe una variable global GOL, la cual es modificada por la función validar_tiro(),que
indica si el último penal pateado fue gol o no.
• Una vez que se valide el penal, se le pasará el turno al próximo jugador.
• Los jugadores siempre patean en un orden definido (ej: jug1, jug2, ..., jug5, jug1, jug2,
etc).
• Existe a disposición la función actual() que retorna el id del pateador actual, y la función
siguiente() que retorna el id del próximo pateador.
Provea una solución que sincronice los tres procesos usando solamente semáforos,
asegurándose que se cumplan las reglas establecidas sin producirse deadlock ni starvation. Se
deberá inicializar cada semáforo, indicando también su tipo.


saludos

No sé si uso bien las funciones de turnos..

Acá está mi resolución por pasos

 

//*Los jugadores no pueden patear si el árbitro no lo indicó.





//Jugador

while ( TRUE ) { 



	posicionarse();

	wait(INDICACION_ARBITRO); //Espera la indicacion del árbitro

	

	patear (); 

	

	if ( GOL == TRUE ) { 

		festejar();

	} else {

		lamentarse (); 

	}	

	

}





//Árbitro

while ( TRUE ) { 



	

	

	dar_orden () ; 

	post(INDICACION_ARBITRO); //Le indica al jugador que patee

		

	validar_tiro () ; 

	

	



}





//*El arquero no puede atajar si el jugador no pateó.



//Arquero

while ( TRUE ) {

	

	posicionarse (); 

	

	

	wait(PATADA_JUGADOR); //Espera a que el jugador patee

	

	atajar(); 

	

	

	if ( GOL == FALSE ) { 

		festejar (); 

	} else { 

		lamentarse (); 

	} 

	

	

}



//Jugador

while ( TRUE ) { 



	

	

	posicionarse();

	

	wait(INDICACION_ARBITRO); //Espera la indicacion del árbitro

	

	patear (); 

	

	post(PATADA_JUGADOR);//Avisa que pateó

	

		

	if ( GOL == TRUE ) { 

		festejar();

	} else {

		lamentarse (); 

	}

	

	



}



//* El árbitro solo puede dar la orden cuando el jugador y el arquero están posicionados.



//Árbitro

while ( TRUE ) { 



	

	wait(JUGADOR_POSICIONADO); //Espera a que el jugador se posicione

	wait(ARQUERO_POSICIONADO); //Espera a que el arquero se posicione (no importa el orden)

	

	dar_orden () ; 

	

	

	validar_tiro () ; 

	

	



}





//Jugador : 

while ( TRUE ) { 



	

	posicionarse();

	

	post(JUGADOR_POSICIONADO); //Avisa que se posicionó

	wait(INDICACION_ARBITRO); //Espera la indicacion del árbitro

	

	patear (); 

	

	post(PATADA_JUGADOR);//Avisa que pateó

	

	

	

	if ( GOL == TRUE ) { 

		festejar();

	} else {

		lamentarse (); 

	}

	

	



}





//Arquero : 

while ( TRUE ) {

	

	posicionarse (); 

	

	post(ARQUERO_POSICIONADO);//Avisa que se posicionó

	wait(PATADA_JUGADOR); //Espera a que el jugador patee

	

	atajar(); 

	

	

	if ( GOL == FALSE ) { 

		festejar (); 

	} else { 

		lamentarse (); 

	} 

	

	

}



/* Existe una variable global GOL, la cual es modificada por la función validar_tiro(), que indica si el último penal pateado fue gol o no.



 Jugador y arquero no deberían fijarse el valor de la variable GOL hasta que el árbitro haya validado el tiro porque sino estarían mirando el valor viejo de la variable. 

También sabemos que el árbitro no debería validar el gol hasta que el arquero no haya intentado atajar.

        

*/



//Árbitro

while ( TRUE ) { 



	

	wait(JUGADOR_POSICIONADO); //Espera a que el jugador se posicione

	wait(ARQUERO_POSICIONADO); //Espera a que el arquero se posicione

	

	dar_orden () ; 

	

	wait(ATAJAR_ARQUERO); //Espera a que el arquero intente atajar

	

	validar_tiro () ; 



       //Avisa que validó el tiro

	post(VALIDACIO_TIRO); 

	post(VALIDACIO_TIRO); 



}







//Arquero : 

while ( TRUE ) {

	

	posicionarse (); 

	

	post(ARQUERO_POSICIONADO);//Avisa que se posicionó

	wait(PATADA_JUGADOR); //Espera a que el jugador patee

	

	atajar(); 

	

	post(ATAJAR_ARQUERO); //Avisa que intentó atajar.

	

	wait(VALIDACION_TIRO); //Espera a que el árbitro valide el tiro

	if ( GOL == FALSE ) { 

		festejar (); 

	} else { 

		lamentarse (); 

	} 

	

	

}





//Jugador : 

while ( TRUE ) { 



	

	

	posicionarse();

	

	post(JUGADOR_POSICIONADO); //Avisa que se posicionó

	wait(INDICACION_ARBITRO); //Espera la indicacion del árbitro

	

	patear (); 

	

	post(PATADA_JUGADOR);//Avisa que pateó

	

	wait(VALIDACION_TIRO); //Espera a que el árbitro valide el tiro

	

	if ( GOL == TRUE ) { 

		festejar();

	} else {

		lamentarse (); 

	}

	

	



}



/*

    No estoy segura de si lo que sigue está bien.



- Una vez que se valide el penal, se le pasará el turno al próximo jugador.

- Los jugadores siempre patean en un orden definido (ej: jug1, jug2, ..., jug5, jug1, jug2,

etc).

- Existe a disposición la función actual() que retorna el id del pateador actual, y la función

siguiente() que retorna el id del próximo pateador.



El jugador tendría que hacer un wait(TURNO), el problema es que si TURNO es un sólo semáforo los jugadores no van a saber de quién es el turno, una opción es tener un vector con un semáforo por jugador, y que el jugador espere por el semáforo que está en la posición que se corresponde a su id (ejemplo, para el jugador de id 0, el semáforo por el que espera es TURNO[0]), así que el jugador haría un wait(TURNO[id]) mientras que el árbitro le indicaría que es el próximo haciendo post(TURNO[ siguiente()]). La cosa es que no sé para qué se usa actual(), así que hice que los demás semáforos que usaban los jugadores también sean un semáforo por jugador, pero me parece innecesario :/

*/



//Árbitro : 

while ( TRUE ) { 



	post(TURNO_JUGADOR[siguiente()]); //Avisa al jugador siguiente que es su turno

	wait(JUGADOR_POSICIONADO[actual()]); //Espera a que el jugador se posicione

	wait(ARQUERO_POSICIONADO); //Espera a que el arquero se posicione

	

	dar_orden () ; 

	

	wait(ATAJAR_ARQUERO); //Espera a que el arquero intente atajar

	

	validar_tiro () ; 

	 //Avisa que validó el tiro

	post(VALIDACIO_TIRO); 

	post(VALIDACIO_TIRO); 

	



}



//Jugador : 

while ( TRUE ) { 



	wait(TURNO[id]);//Espera su turno

	

	posicionarse();

	

	post(JUGADOR_POSICIONADO[id]); //Avisa que se posicionó

	wait(INDICACION_ARBITRO); //Espera la indicacion del árbitro

	

	patear (); 

	

	post(PATADA_JUGADOR[id]);//Avisa que pateó

	

	wait(VALIDACION_TIRO); //Espera a que el árbitro valide el tiro

	

	if ( GOL == TRUE ) { 

		festejar();

	} else {

		lamentarse (); 

	}

	

	



}



//Arquero

while ( TRUE ) {

	

	posicionarse (); 

	

	post(ARQUERO_POSICIONADO);//Avisa que se posicionó

	wait(PATADA_JUGADOR[actual()]); //Espera a que el jugador patee

	

	atajar(); 

	

	post(ATAJAR_ARQUERO); //Avisa que intentó atajar.

	

	wait(VALIDACION_TIRO); //Espera a que el árbitro valide el tiro

	if ( GOL == FALSE ) { 

		festejar (); 

	} else { 

		lamentarse (); 

	} 

	

	

}

 



*/

para los turnos te faltan unas funciones que cucho no puso en el enunciado, pero ta bien, el otro día lo resolvimos en clase.

ok, gracias a ambos.

les paso lo que hice en otro ejercicios para que si pueden me confirmen si estan bien o no.

---

Suponga que un proceso tiene por tarea compilar un conjunto de programas y luego enviar el
resultado de cada compilación por email al encargado de ese proyecto. Dicho proceso está
organizado de la siguiente manera: N hilos de kernel compilan cada uno un programa distinto, y
luego cada uno de ellos depositan en una lista (compartida para todo el proceso) el resultado;
por otro lado, un hilo de kernel retira los resultados de las compilaciones y manda un email por
cada uno de ellos.

caso 1 : M posiciones disponibles en la lista

Estructura compartida: lista // Lista de resultados de compilaciones


KLT compilador (N instancias)

While (TRUE){
id_programa = obtener_nuevo_programa();
r = compilar_programa(id_programa);
depositar_resultado(r, lista);
}

KLT notificador (1 instancia)
While (TRUE){
r2 = retirar_resultado(lista);
enviar_email(r2);
}


resolucion :

 



semaphore FREESLOT = M ;

semaphore AVAILABLE = 0 ; 

semaphore MUTEX = 1 ; 



// producer 



while ( TRUE ) { 



	id_programa = obtener_nuevo_programa();

	r = compilar_programa(id_programa);

	

	wait ( FREESLOT ) ; 

	

	wait ( MUTEX ) ; 

	depositar_resultado(r, lista);

	signal ( MUTEX ) ; 

	

	signal ( AVAILABLE ) ; 

	



}



// consumer 



while ( TRUE ) {



	wait ( AVAILABLE ) ; 

	

	wait ( MUTEX ) ; 

	r2 = retirar_resultado(lista);

	signal ( MUTEX ) ; 

	

	signal ( FREESLOT ) ; 

		

	enviar_email(r2);

	

}






Suponga que un proceso tiene por tarea compilar un conjunto de programas y luego enviar el

resultado de cada compilación por email al encargado de ese proyecto. Dicho proceso está

organizado de la siguiente manera: N hilos de kernel compilan cada uno un programa distinto, y

luego cada uno de ellos depositan en una lista (compartida para todo el proceso) el resultado;

por otro lado, un hilo de kernel retira los resultados de las compilaciones y manda un email por

cada uno de ellos.



caso 2 : infinitas posiciones en la lista



Estructura compartida: lista // Lista de resultados de compilaciones





KLT compilador (N instancias)



While (TRUE){

id_programa = obtener_nuevo_programa();

r = compilar_programa(id_programa);

depositar_resultado(r, lista);

}



KLT notificador (1 instancia)

While (TRUE){

r2 = retirar_resultado(lista);

enviar_email(r2);

}



resolucion : 

[code=c]





semaphore AVAILABLE = 0 ; 

semaphore MUTEX = 1 ; 



// producer 



while ( TRUE ) { 



	id_programa = obtener_nuevo_programa();

	r = compilar_programa(id_programa);

	

	wait ( MUTEX ) ; 

	depositar_resultado(r, lista);

	signal ( MUTEX ) ; 

	

	signal ( AVAILABLE ) ; 

	



}



// consumer 



while ( TRUE ) {



	wait ( AVAILABLE ) ; 



	wait ( MUTEX ) ; 

	r2 = retirar_resultado(lista);

	signal ( MUTEX ) ; 

	

		

	enviar_email(r2);

	

}

---

ejercicio de los aviones :

Existe un aeropuerto que se utiliza como base de operaciones de una flota de aviones.
Existen muchos aviones, diez pistas de aterrizaje / despegue y dos controladores aéreos. Cada
vez que un avión desea despegar o aterrizar, debe utilizar una pista. Para ello, la misma es
solicitada al controlador de entrada, y luego de ser utilizada se le notifica al controlador de salida
para que vuelva a estar disponible.
Se pide que sincronice el siguiente pseudo-código respetando las reglas establecidas, sin que se
produzca deadlock ni starvation (cuando el avión ya pidió pista). Para ello solamente debe
utilizar semáforos, indicando el tipo de los mismos y sus valores iniciales.
pistasLibres = 10; // variable compartida


AVIÓN

while ( TRUE ) {

mantenimiento () ;
despegar () ;
volar () ;
aterrizar () ;

}


CONTROLADOR ENTRADA

while ( TRUE ) {


otorgarPista ();
pistasLibres -- ;
log ( pistasLibres ) ;


}


CONTROLADOR SALIDA

while ( TRUE ) {


liberarUnaPista () ;
pistasLibres ++ ;
log(pistasLibres) ;

}

Nota: La function log() imprime por pantalla el valor actual de pistas
libres.

 





semaphore PISTALIBRE = 10 ; 

semaphore ENTRADA_REQ = 0 ; 

semaphore ENTRADA_CONFIRM = 0 ; 

semaphore SALIDA = 0 ; 

semaphore LIBREMUTEX = 1 ; 



// avion 



while ( TRUE ) { 



	mantenimiento () ; 

	

	// solicitar pista 

	signal ( ENTRADA_REQ ) ; 

	

	// esperar confirmacion

	wait ( ENTRADA_CONFIRM ) ; 

	

	despegar () ; // usar la pista

	

	// avisar fin de uso al controlador de salida 

	signal ( SALIDA ) ; 

	

	volar () ; // cualquier cosa 

	

	// idem anteriores 

	signal ( ENTRADA_REQ ) ; 

	wait ( ENTRADA_CONFIRM ) ; 

	

	aterrizar () ; // usar la pista 

	

	signal ( SALIDA ) ; 

	

}





// controlador de entradas 



while ( TRUE ) { 



	// esperar pedido de entrada 

	wait ( ENTRADA_REQ ) ;  



	// esperar pista libre 

	wait ( PISTALIBRE ) ;  



	// actualizar contador 

	wait ( LIBREMUTEX ) ; 

	otorgarPista (); 

	pistasLibres -- ;  

	log ( pistasLibres ) ; 

	signal ( LIBREMUTEX ) ; 

	

	// informar pista libre 

	signal ( ENTRADA_CONFIRM ) ; 

	

		

} 



// controlador de salidas 



while ( TRUE ) { 



	// esperar confirmacion de salida ( de los aviones ) 

	wait ( SALIDA ) ;

	

	// actualizar contador de pistas disponibles 

	wait ( LIBREMUTEX ) ; 

	liberarUnaPista () ;

	pistasLibres ++ ; 

	log(pistasLibres) ;

	signal ( LIBREMUTEX ) ; 

	

	// mas pistas libres 

	signal ( PISTALIBRE ) ; 

	



}

Pareciera que están bien

con "pareciera" me alcanza y me sobra.

abrazo

hola gente, revivo esto para para preguntar por el ejercicio :

dados los procesos A,B y C sincronizarlos para que se ejecuten segun la secuencia ABACABAC...

si alguno me puede dar una mano, mil gracias.

saludos

Tene en cuenta esto... vos estas sincronizando A con X... y despues X lo separas en B y C (y los alternas).
De esa forma sale facil...

Exitos con eso

ok , algo asi fue lo que hice ( voy a obviar el while(TRUE) en todos los casos )

valores iniciales TA=1 , TB=1 , TC=0 , A=0

A:

wait (TA)
signal (A)

B:

wait(TB)
wait(A)
signal(TA)
signal(TC)

C:

wait(TC)
wait(A)
signal(TA)
signal(TB)


supongo que esta bien.

aprovecho para preguntar por el ejercicio : dados A,B y C sincronizar para ABBBCABBBCABBBC

solucion :

iniciales TA=1 , TB=0 , TC=0

A:

wait( TA )
signal(TB)
signal(TB)
signal(TB)
signal(TC)

B:

wait(TB)

C:

wait(TC)
signal(TA)


saludos

Gente para hacer algo parecido a lo que dijo Adriano de pensarlo como A con X y luego alternar B con C, si yo tengo que sincronizar BACABACA... como lo tendria que encarar?

Me sumo al pedido, cuales serían las claves al resolver ejercicios de semaforos/sincronizacion??

Los más simples los entiendo, pero cuando se complican un poco no se como pensarlos

el de BACA BACA BACA lo planteé así:



sa=0;sb=1;sc=0;sd=0;

PA
wait(sa);

signal(sc);

wait(sd);

signal(sb);

PB

wait(sb);

signal(sa);


PC

wait(sc);

signal(sd);



Vi uno resuelto que andaba por acá por utnianos que lo plantea distinto, por eso dudo si está bien así.

Hay solo UNA manera de plantear un ejercicio de semaforos???


Saludos!

Como en todo lo referente a la programación, poner un buen nombre a las variables es fundamental para que las cosas tengan sentido.

En lugar de "sa" llamemos a las variables "puedeEjecutarX", siendo X el proceso. Si tuvieramos que formar BAC BAC BAC, arranca habilitada la B (osea, puedeEjecutarB = 1), y el resto en 0. El proceso B, ¿qué hace? Espera a poder ejecutar, ejecuta, y luego habilita a que se ejecute A. Lo mismo pasa con A y la C.

 puedeEjecutarA = 0;

puedeEjecutarB = 1;

puedeEjecutarC = 0;



void a() {

  wait(puedeEjecutarA);

  printf("A");

  signal(puedeEjecutarC);

}



void b() {

  wait(puedeEjecutarB);

  printf("B");

  signal(puedeEjecutarA);

}



void c() {

  wait(puedeEjecutarC);

  printf("C");

  signal(puedeEjecutarB);

}

Peeeeeero en este caso necesitamos que cada vez que ejecuta la A habilite a una letra distinta. Entonces, después de imprimir A no tenemos que habilitar a C, si no a C y B:

 void a() {

  wait(puedeEjecutarA);

  printf("A");

  signal(puedeEjecutarBoC);

}

Entonces, B y C van a estar esperando semáforos con nombre distinto al anterior:

 void b() {

  wait(puedeEjecutarBoC);

  printf("B");

  signal(puedeEjecutarA);

}



void c() {

  wait(puedeEjecutarBoC);

  printf("C");

  signal(puedeEjecutarA);

}

Y estaría todo joya salvo por el hecho de que tenemos que hacer que sea alternado el asunto entre B y C: si los dejamos así como están, los dos van a intentar ejecutar atrás de cada A, por lo que hay que agregar alguna restricción para evitar cosas como ACAC. Si entre ellos tienen que alternarse, pongamos un semáforo más para cada uno que desambigue entre ellos dos:

 void b() {

  wait(puedeEjecutarB);

  wait(puedeEjecutarBoC);

  printf("B");

  signal(puedeEjecutarC);

  signal(puedeEjecutarA);

}



void c() {

  wait(puedeEjecutarC);

  wait(puedeEjecutarBoC);

  printf("C");

  signal(puedeEjecutarB);

  signal(puedeEjecutarA);

}

Entonces, cada una de estas dos funciones trata de conseguir el permiso que le da la otra para ejecutar, y LUEGO trata de conseguir el permiso que le da A indicándole que es el turno de alguna de ellas dos. Recién ahí ejecuta, habilita a la otra función del par, y luego habilita a la A.

¿Por qué es importante que primero pida por SU variable y luego por la de BoC? Porque, si lo hiciera al revés, podría darse que B consuma el semáforo de BoC, pero que haya sido C la que estaba habilitada. B se quedaría esperando a que le signaleen puedeEjecutarB, que no va a ocurrir hasta que C no ejecute... Pero C está esperando el permiso compartido, que no va a darse hasta que A no vuelva a ejecutar... lo que no va a ocurrir ¡hasta que B termine de ejecutarse! Ninguno de los tres procesos avanza, porque entre sí se están molestando: ahí tenés un deadlock clarito como el agua clara.



Y, lo único que falta ahora: corregir el estado inicial.

Tiene que arrancar B corriendo, y los otros dos procesos no, así que sólo hay que habilitar las banderas necesarias para que B arranque:

 puedeEjecutarA = 0;

puedeEjecutarB = 1;

puedeEjecutarC = 0;

puedeEjecutarBoC = 1;

Y ahí no sólo tenemos algo que anda, sino que a golpe de vista podemos entender de qué se trata: "B espera hasta poder ejecutar él y poder ejecutar él o C, imprime una B y da permiso para que ejecuten C y A". Tal vez "permisoEjecucion" hubiera sido otro prefijo útil, pero decir "wait (esperar) puedeEjecutar" es bastante más coloquial, no se.

Eso!

Muchísimas gracias por tomarte la molestia de explicármelo tan detalladamente!

Creo haberlo entendido! Voy a seguir practicando.

¿No hay ninguna herramienta online para ver como se ejecutarían los semáforos y ver una secuencia? Así podría probar, aprender y autocorregirme

Off-topic:

PD:me encantó el banner de 'fuerza gaby, aguante catupecu!

No se me ocurre ninguna (tampoco busqué), pero no estaría nada mal que hagamos una. ¿Qué creés que necesitarías que haga la herramienta?

Más allá de este ejercicio, para ver otros decía:

ver de manera interactiva como el código ejecuta la secuencia, como va pasando de una sección a otra (frenandose y pasandole la posta al otro proceso).