Esta página web
contiene un trabajo sobre el problema de comunicación entre procesos
denominado Rendez-vous.
Veamos los distintos puntos a tratar:
Explicación del problema.
Solución al problema.
Implementación en C.
Documentación del programa.
Ejemplo.
Otros datos de interés.
Autores.
-Desarrollo modular de programas.
-Procesos.
-Operaciones de bajo nivel.
-Procesamiento de excepción.
Para la cita dos procesos que deseen intercambiar las señales
de sincronización y/o datos deben estar ambos activos
y procurando la interacción. Una cita realmente tiene lugar sólo
cuando ambas partes están preparadas y desean la
sincronización. De lo contrario, la primera parte en llegar espera.
Cuando llega la segunda, los dos procesos están
brevemente sincronizados para intercambiar datos y posiblemente ejecutar
algún código cuyos resultados se pueden
necesitar para su continuación. En cualquier caso, después
de una cita, se separan las partes y continua cada una por
su cuenta. Aunque en ADA hay varias sentencias diferentes para conseguir
la cita nosotras hemos implementado en C
solamente una de ellas:
El mecanismo de entrada-aceptación ("entry-accept").
La sintaxis y semántica de este mecanismo es algo reminiscente
de una llamada a un procedimento externo. En particular uno de los procesos
involucrados contine y posee una secuencia
de sentencias para ser ejecutadas durante una cita con otro proceso. Tales
sentencias se encierran en una construcción
Aceptación que puede no contener sentencias ejecutables si
sólo se requiere sincronización. Para que los otros procesos
se reunan con él poseedor de la sentencia Accept le dá
un nombre único que se hace públlico poniendo una sentencia
Entry correspondiente en la parte pública de la declaración
de ese proceso.
En otras palabras, la definición de Rendez-vous
es :
Comunicación
entre procesos DIRECTA (uno y sólo un enlace por cada par
de procesos)
y
de CAPACIDAD cero (cuando mandamos una petición hasta que
no se despache no hacemos
otra
cosa).
Características:
*Encuentro
simétrico (el que llega antes espera al otro).
*Encuentro
simple (sólo una transacción de información).
*Existencia
de exclusión mutua.(sólo dos procesos en un encuentro).
*De
doble sentido. (Puede haber información de ida y vuelta).
Para volver al principio pulsar aqui
Veamos un ejemplo práctico
de ejecución del programa, este será el fichero de salida
en el caso de ejecutarle con
veinte iteraciones:
Numero de iteraciones 20:
39 =====> < XXX IX> y El numero SI es primo
507 =====> < D VII> y El numero SI es primo
591 =====> < D XC I> y El numero SI es primo
683 =====> < DC LXXX III> y El numero NO es primo
879 =====> <DCCC LXX IX> y El numero SI es primo
427 =====> < CL XX VII> y El numero SI es primo
551 =====> < D L I> y El numero SI es primo
163 =====> < C LX III> y El numero NO es primo
119 =====> < C X IX> y El numero SI es primo
547 =====> < D XL VII> y El numero NO es primo
111 =====> < C X I> y El numero SI es primo
443 =====> < CL XL III> y El numero NO es primo
759 =====> < DCC L IX> y El numero SI es primo
867 =====> <DCCC LX VII> y El numero SI es primo
271 =====> < CC LXX I> y El numero NO es primo
523 =====> < D XX III> y El numero NO es primo
799 =====> < DCC XC IX> y El numero SI es primo
387 =====> < CCC LXXX VII> y El numero SI es primo
31 =====> < XXX I> y El numero NO es primo
403 =====> < CL III> y El numero SI es primo
Cómo entender nuestro programa en
una situación cotidiana:
Los dos procesos serán, en este
caso dos amigas (Sonia y Sara) que quedan una tarde para comprarse colonia
ambas la necesitan pero deciden que sólo una de ellas (Sara) entre
a la tienda a comprarla.
Imaginemos que quedan a las 16:00 horas en la puerta del comercio, la que
primero llegue ha de esperar
a la otra porque:
-Si llega Sara primero deberá esperar
a Sonia para que le dé el dinero y pueda entrar a comprar las dos
colonias.
-Si es Sonia la que llega antes debe esperar
a Sara porque es la que ha de entrar en la tienda.
Ahora ya están las dos en la puerta y es el momento de que Sara
entre a comprar mientras Sonia espera fuera; no podrá
irse hasta que su amiga no le dé la colonia. Cuando Sara termina
su compra sale, se reparten las colonias y cada una
se va a su casa para arreglarse y salir a dar un paseo.
Para volver al principio pulsar aqui
OTROS DATOS DE INTERÉS
Veamos como varían los tiempos
real, de ususario y de sistema en función del número de iteraciones.
Nº de Iteraciones | Tiempo Real | Tiempo de Usuario | Tiempo de Sistema |
10 |
0.04" |
0.1" |
0.1" |
50 |
0.14" |
0.1" |
0.1" |
100 |
0.26" |
0.2" |
0.2" |
500 |
1.21" |
0.8" |
0.6" |
1000 |
2.42" |
0.14" |
0.9" |
2000 |
13.30" |
0.27" |
0.17" |
5000 |
51.51" |
0.68" |
0.46" |
10000 |
1'53.02" |
1.21" |
0.76" |
Es clara la gran diferencia en todos los tiempos con respecto al número de iteraciones.
Veamos la gráfica resultante, en escala logarítmica
Para volver al principio pulsar aqui
Para implementar una comunicación entre
procesos tan especial como el "rendez-vous" (cita) hemos
simulado
la sentencia Accept de ADA. El problema surge a la hora de
sincronizar nuestros procesos, podíamos optar por
dos posibles soluciones:
*Utilizar semáforos.
*Exclución mútua.
Decidimos utilizar semáforos.
Para simular un encuentro programamos dos procesos: uno, para pasar un
número entero a romano y otro, para ver
si ese número es primo o no; el número entero será
generado por un método congruencial multiplicativo.
Para volver al principio pulsar aqui
/********************************************************************************************
Programa que simula la sentencia Accept
de ADA.
Para compilarle escribir:
gcc
-o nombre_fichero nombre_programa rshmem.c semaph.c
En el archivo "nombre_fichero" se guardará
el ejecutable del programa, por tanto para ejecutarle escribir:
nombre_fichero
número
Número hace referencia al total de veces
que queremos repetir el programa. Ver argumentos de la función principal.
*********************************************************************************************/
/*********************************************************************************************
NOMBRE: aux_romano
SINOPSIS: void aux_romano(int numero);
ARGUMENTOS:
int numero ===>numero entero que
queremos pasar a romano.
DESCRIPCIÓN: función auxiliar
del proceso hijo que dado un número entero lo convierte en su transcipción
a romano
imprimiéndolo
por pantalla.
**********************************************************************************************/
/*********************************************************************************************
NOMBRE: aux_primo
SINOPSIS: void aux_primo(int numero);
ARGUMENTOS:
int numero===>numero entero que queremos
comprobar si es o no primo.
DESCRPCIÓN: función auxiliar del proceso padre
que dado un número entero, nos dice si es primo. Para ello compro-
bamos
si es divisible por cualquier otro número distinto de uno o de sí
mismo.
**********************************************************************************************/
/*********************************************************************************************
NOMBRE: busca_primo
SINOPSIS: void busca_primo(int nIter, int mutexp, int mutexr,
int *recurso);
ARGUMENTOS:
int nIter===>numero de iteraciones.
int mutexp===>semáforo del proceso busca_primo (Padre).
int mutexr===>semáforo del proceso pasa_a_romano
(Hijo).
int *recurso===>puntero a memoria compartida.
DESCRIPCIÓN: proceso padre
Es el que accede a memoria compartida
genera un número entero mediante un método congruencial multiplicativo
y comprueba si es primo utilizando la función auxiliar aux_primo.
Para la sincronización, utilizamos dos semáforos, que este
proceso debe abrir y cerrar:
1º Cierra su propio semáforo (se "duerme"
hasta que llegue el proceso hijo).
2º Abre el semáforo del hijo (le despierta
para avisarle de que ya accedió a memoria), para que éste
pueda seguir su
camino.
Esta función se ejecutará tantas veces como indique
nIter.
**********************************************************************************************/
/*********************************************************************************************
NOMBRE: pasa_a_romano
SINOPSIS: void pasa_a_romano(int nIter, int mutexp, int mutexr,
int *recurso);
ARGUMENTOS:
int nIter===>numero de iteraciones.
int mutexp===>semáforo del proceso
busca_primo.
int mutexr===>semáforo del proceso
pasa_a_romano.
int *recurso===>puntero a memoria compartida.
DESCRIPCIÓN: proceso hijo
Utiliza el número entero generado
por el proceso padre , que se encuentra en *recurso, y lo pasa a romano
haciendo
uso de su función auxiliar aux_romano.
Para conseguir que todo funcione bien este proceso, manipula los semáforos
de la siguiente manera:
1º Abre el semáforo del proceso busca_primo (le
"despierta" para avisarle que el ha llegado al "encuentro"
).
2º Cierra su propio semáforo, esperando a que,
en la siguiente iteración el proceso padre le "despierte".
Se ejecutará tantas veces como indique nIter.
**********************************************************************************************/
/*********************************************************************************************
NOMBRE: main
SINOPSIS: void main(int argn, char *argv[]);
ARGUMENTOS:
int argn===>número de argumentos.
char *argv[]===>argv[0]=nombre del programa,
argv[1]=numero
de iteraciones.
DESCRIPCIÓN: función principal
Se encarga de:
=>Obtener las
claves para los recursos ipc de cada semáforo: clave_mutexp, clave_mutexr.
En caso de error, el programa termina, mostrando por pantalla un mesaje
de advertencia.
=>Crear los semáforos
con comprobación de los posibles errores y terminación del
programa si fuese necesario.
=> Crear la memoria compartida y en caso de error terminar el programa, cerrando antes los dos semáforos.
=>Simular el
"encuentro" entre los procesos utilizando la funcion fork()
que realiza una copia del programa,
a partir de ella, a la que llamaremos proceso hijo. Sincronizamos así
el encuentro entre los procesos.
NOTA: Como librerías utilizamos las funciones "rshmem.h" y <sys/sem.h>.
Parar volver al principio pulse aqui.
**********************************************************************************************/
#include "rshmem.h"
#include <sys/sem.h>
/***************************************************************************
*Funcion que dado un numero entero pasado como parametro
* a la funcion lo convierte en su transcripcion a romanos sacandolo
* por pantalla
***************************************************************************/
void aux_romano(int numero) {
static char *codigos[3][10] = { { " ", "I", "II",
"III", "IV", "V", "VI", "VII",
"VIII", "IX" },
{
" ", "X", "XX", "XXX", "XL",
"L", "LX", "LXX", "LXXX", "XC"
},
{
" ", "C", "CC", "CCC", "CL",
"D", "DC", "DCC", "DCCC", "CM"
}} ;
int unidades,decenas,centenas; /*Guardamos respectivamente las unidades
las decenas y las centenas del numero*/
unidades = numero%10;
numero = numero/10;
decenas = numero%10; /*Hallamos las decenas del numero*/
centenas = numero/10; /*Hallamos las centenas del numero*/
printf("<%4s %4s %4s> y ", codigos[2][centenas],
codigos[1][decenas
],
codigos[0][unidades]);
fflush(stdout);
}
/*fin del procedimiento que escribe un numero en romanos */
/**************************************************************************
* Funcion que dado un numero entero, nos dice si es o no primo. Para
* ello comprobamos si el numero es divisible por cualquier otro numero
* distinto de 1 o de si mismo ***************************************************************************/
void aux_primo(int numero) {
int n_medios; /*almacena el valor n/2 y solo lo calculamos una vez*/
int i;
int aux=1;
n_medios = numero/2; /*variable contador*/
/* realizo un bucle
desde 2 hasta n/2. SI el resto es 0 no es primo */
for (i=2; i<=n_medios && aux!=0;i++)
if ((numero%i)==0) aux=0;
printf("\tEl numero %s es primo\n", (aux) ? "NO" :
"SI");
}
/***************************************************************************
* Proceso Padre: funcion que busca si un numero es primo.
**************************************************************************/
void busca_primo(int nIter, int mutexp, int mutexr, int *recurso) {
int i;
*recurso=3; /*semilla */
for(i=0;i<nIter;i++){
semWait(mutexp);
*recurso=(13*(*recurso))%1000;/*numero
entre 0 y 999*/
printf("%5d====> ",*recurso);
fflush(stdout);
semSignal(mutexr);
aux_primo(*recurso);
}
}
/************************************************************************
* Proceso Hijo: funcion que pasa a romano ************************************************************************/
void pasa_a_romano(int nIter, int mutexp, int mutexr, int *recurso) {
int i;
for(i=0; i<nIter; i++){
semSignal(mutexp); /*abro a primo */
semWait(mutexr); /*me duermo */
aux_romano(*recurso);
}
}
/**********************************************************************
* Funcion Principal Main()
***********************************************************************/
void main(int argn, char *argv[]) {
int *recurso; /*puntero a memoria compartida*/
int *marcaFin; /*marca de fin del proceso hijo */
int mutexp; /*semaforo para el proceso de buscar_primo*/
int mutexr; /*semaforo para el proceso de pasa_a_romano*/
key_t claveMutexp;
key_t claveMutexr;
int n ;
char buffer[128] ;
/*Obtener una clave cualquiera para el recurso ipc*/
if ((key_t)-1 == (claveMutexp = ftok("alicia.c",'p'))){
fprintf(stderr,"main:error al
crear la clave semp con ftok()\n");
exit(1);
}
if ((key_t)-1 == (claveMutexr = ftok("alicia.c",'r'))){
fprintf(stderr,"main:error al
crear la clave semr con ftok()\n");
exit(1);
}
/* tomar el numero de iteraciones por argumento */
if (2!=argn) {
n = 100;
} else {
if (0 == (n = atoi(argv[1])))
n
= 100;
}
printf("Numero de iteraciones = %d\n", n); fflush(stdout);
/*Crear el semaforo*/
if (1 == (mutexp=semCreate(claveMutexp,0))){
fprintf(stderr,"main:No puede crear
semaforo\n");
exit(1);
}
if(1 == (mutexr=semCreate(claveMutexr,0))){
fprintf(stderr,"main:No puede crear semaforo\n");
semClose(mutexp);
exit(1);
}
/*Crear memoria compartida*/
if (!crearMemoria()){
fprintf(stderr,"error de crear Memoria\n");
semClose(mutexr);
semClose(mutexp);
exit(1);
}
recurso = (int*) memoria;
marcaFin = (int*) recurso + sizeof(int);
*marcaFin = 1;
if (0!=fork()) { /*Proceso Padre*/
/**************/
busca_primo(n, mutexp,
mutexr, recurso);
/**************/
semClose (mutexp);
semClose (mutexr);
while (*marcaFin) ; /* espera la finalizacion
del proceso hijo */
if (!eliminarMemoria())
fprintf(stderr,"\nError
en eliminar memoria\n");
exit(0);
} else {
/*Proceso Hijo*/
if(-1==(mutexp=semOpen(claveMutexp)))
fprintf(stderr,"No
tengo cualificador de mutexp \n");
if(-1==(mutexr=semOpen(claveMutexr)))
fprintf(stderr,"No
tengo cualificador de mutexr \n");
/**************/
pasa_a_romano(n,
mutexp, mutexr, recurso);
/**************/
semClose (mutexp);
semClose (mutexr);
*marcaFin =
0; /* marca de fin del proceso */
exit(0);
}
} /*Fin del main*/
Para volver al principio pulsar aqui
AUTORES
Esta prática ha sido realizada por:
Patricia
Núñez Jiménez.
Alicia
Pedraza Núñez.
Para volver al principio pulsar
aqui.