¡¡¡¡¡¡Bienvenidos a nuestra pagina WEB!!!!!!! :

Si quieres navegar por nuestra practica, esto es lo que te ofrecemos (sugerimos la vean para ampliar sus conocimientos sobre la materia):

PROBLEMA

DOCUMENTACION

LIBRERIAS

IMPLEMENTACION

SALIDA

AUTORAS

************************************************************************************************

************************************************************************************************

Un estudiante que se especializa en antropologia y sigue una asignatura secundaria en computacion se ha comprometido en un proyecto de investigacion para observar si los mandriles africanos se les puede ensenar estacamientos. Localiza un canon profundo y sujeta una cuerda a traves de el, de manera que los mandriles puedan cruzar pasando a mano. Varios mandriles pueden atravesar al mismo tiempo, siempre que vayan en la misma direccion. Si los mandriles que viajan hacia el norte y los que viajan hacia el sur abordan la cuerda al mismo tiempo se producir  un estancamiento (los mandriles se encuentran en el centro ) porque es imposible que un mandril pase sobre otro estando suspendidos sobre el canon. Si uno de ellos desea atravesar el canon, debe verificar que ningun mandril este atravesando el canon en ese momento en direccion contraria.

volver al menu

************************************************************************************************

************************************************************************************************

Se considera cada mandril como un proceso, y el puente es el recurso compartido, de modo que, para que los mandriles que vienen del norte y los que vienen del sur no coincidan en el centro del puente utilizamos dos semaforos (permisoN y permisoS). Hemos seguido el sigiente protocolo:

-El paso de los mandriles por el puente debe ser justo, es decir, no se debe favorecer a los mandriles de algun sentido a costa de perjudicar a los del otro. Para ello no permitimos que pasen mas de cuatro mandriles seguidos de un mismo sentido.

FUNCIONES DEL PROGRAMA:

caminoNorte(int,*FILE);

caminoSur(int,*file);

A estas dos funcines se les manda por argumentos: un entero que especifica el mandril que llega a ese camino. un puntero al fichero de salida

Existe una variable global (puente), definida de tipo PUENTE, que es una estructura en la que se encuentran los semaforos y las variables que regulan el paso de los mandriles por el puente.

DEPENDENCIAS:

ficheros: "rshmem.h" "rshmem.c" "semaph.c"

macros: nummandrilN = numero de mandriles que vienen por el Norte

nummandrilS = numero de mandriles que vienen por el Sur

VARIABLE DE MEMORIA COMPARTIDA: La variable de memoria compartida es una estructura del tipo:

typedef struct puente{

int dentroN; int dentroS;

int esperandoN; int esperandoS;

int turnoN; /*FALSE=1,true=0*/

int turnoS;

int pasadosN; int pasadosS;

int permisoN; /*semaforos*/ int permisoS;

}PUENTE;

Donde : dentroN y dentroS son dos enteros que nos dicen el numero de mandriles que hay dentro del puente del norte y del sur respectivamente.

esperandoN y esperandoS son dos enteros que nos dicen el numero de mandriles que estan esperando en el norte y en el sur respectivamente.

turnoN y turnoS son dos enteros que nos dicen si tienen o no turno de entrada en el puente, aunque no es la unica condicion de entrada en el. Estas variables se han definido para no dar mas prioridad a los mandriles que vienen por un camino, que a los que vienen por el otro; el primer mandril que llega negara  el camino al mandril de sentido contrario. Inicialmente valen 0(TRUE).

pasadosN y pasadosS son dos enteros qu nos dicen el numero de mandriles que han pasado del norte y del sur respectivamente.Sirven para poder realizar el protocolo de que pasen lo maximo 4 mandriles seguidos de un mismo lado.Se cuenta cada mandril nada mas entrar en el puente.

permisoN y permisoS son dos semaforos que nos ayudan a sincronizar el paso de los mandriles.

¡¡¡¡¡ NOTA IMPORTANTE !!!: En una primera version del programa en la funciones caminoNorte() se puso como condicion de entrada en el bucle:

(dentroS>0) o (turnoS=TRUE y esperandoS>0)

lo que producia un interbloqueo. Por ejemplo: Si hay un mandril del norte cruzando el puente y tres del sur esperando, el siguiente(s) mandril(es) del norte espera(n), lo cual es erroneo. Ademas, los mandriles del sur siguen sin poder entrar, porque turnoN=TRUE y esperandoN > 0; por su lado los mandriles del norte tampoco podran entrar porque turnoS=TRUE y esperandoS > 0.

Para solucionar este problema cambiamos la condicion de entrada por:

(dentroS>0) o ( NO(turnoN=TRUE) y esperandoS>0)

Es obvio que NO(turnoN=TRUE) es equivalente a turnoS=TRUE. Esta condicion de entrada es analoga para la funcion caminoSur().

volver al menu

***********************************************************************************************

***********************************************************************************************

Hemos utilizado las siguientes librerias:

rshmem.c:

/* rshmem.c

Fichero con funciones de creación de memoria compartida y varias de utilidad. */

#define RUTINAS_SHMEM

#include "rshmem.h"

/* Crea memoria compartida. * - el manejador de memoria es interno * - manda mensajes de error por salida de error estándar. */ int crearMemoria() { char *funcName = "crearMemoria"; if ((shmid=shmget(IPC_PRIVATE, SHM_SIZE, SHM_MODE))<0) { fprintf(stderr, "%s: error de shmget()\n", funcName); } else if ((memoria=shmat(shmid, 0, 0)) == (void *) -1) { fprintf(stderr, "%s: error de shmat()\n", funcName); } else { return TRUE; } return FALSE; }

/* Destruye la memoria compartida creada por crearMemoria() */ int eliminarMemoria() { char *funcName = "eliminarMemoria"; if (shmctl(shmid, IPC_RMID, 0) < 0) { fprintf(stderr,"%s: error de shmctl()\n", funcName); return FALSE ; } else return TRUE ; }

/* Coloca una semilla en el temporizador del bucle de * tiempoPasa() */ void origenTiempo(){ srand((unsigned int) time(NULL)) ; }

/* Rutina que hace pasar un poco de tiempo con un bucle * sencillo */ void tiempoPasa() { unsigned int i; int a=3;

/* Los parametros "50" y "2" dependen mucho de la velocidad * de la computadora y de la configuracion del SO. Espero que * funcionen bien */ for (i=rand()/50; i>0; i--) a = a%3 + i; }

rshmem.h:

/*rshmem.h

Fichero de cabecera con definiciones y declaraciones para usar memoria compartida. */

#include <stdio.h> #include <time.h> #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h>

#define ARRAY_SIZE 4000 #define MALLOC_SIZE 10000 #define SHM_SIZE 10000 #define SHM_MODE (SHM_R | SHM_W) /* read/write */

#define TRUE 1 #define FALSE 0

#ifdef RUTINAS_SHMEM static int shmid; /* handler de memoria compartida */ char *memoria; /* puntero a zona de memoria compartida */ #else extern char *memoria; #endif

/* Prototipos de funciones de memoria compartida */

void origenTiempo(); void tiempoPasa(); int crearMemoria() ; int eliminarMemoria() ;

#define TP tiempoPasa();

semaph.c:

/*********************************

Provee un interface mas sencillo de entender que las llamadas a sistema de semaforos de System V. Hay 7 rutinas disponibles:

* id = semCreate(key, initval); # Crear con un valor inicial o abrir.

* id = semOpen(key); # Abrir (debe existir ya)

semWait(id); # espera = P = down en 1

semSignal(id); # senal = V = up en 1

semOp(id, cantidad); # espera si (cantidad < 0)

# senal si (cantidad > 0)

semClose(id); # cierra

semRm(id); # destruye (borra)

* Se disegna un semaforo soportado por un conjunto de tres, dos de ellos auxiliares. (Los semaforos se crean por arrays)

- El primer miembro, [0], es el valor real del semaforo.

- El segundo miembro, [1], es un contador utilizado para conocer

si todos los procesos han acabado con el semaforo. El contador

se inicializa con un numero grande (BIGCOUNT) y se decrementa cada

vez que se crea o abre, y se incrementa en cada cierre.

De esta forma se puede "ajustar" la caracteristica de System V

de forma que se tenga en cuenta cualquier proceso que salga

sin llamar a semClose(). A pesar de ello, no ahuda mucho si el

ultimo proceso sale sin cerrar el semaforo, ya que no hay forma

de destruir el semaforo, pero puede ayudar si acaba (intencional

o no intencionalmente) cualquier otro proceso diferente del ultimo.

- El tercer miembro, [2], del conjunto de semaforos se utiliza para

bloquear las secciones criticas en semCreate() y semClose().

********************************************************/

#include <stdio.h>

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

#include <errno.h>

void semOp(int, int);

int semCreate(key_t, int);

int semOpen(key_t);

void semRm(int);

void semClose(int);

void semWait(int);

void semSignal(int);

#define BIGCOUNT 10000 /* Valor inicial para el contador de procesos */

/* Define los arrays de operaciones del semaforo para llamadas a

* semop().

*/

static struct sembuf op_lock[2] = {

2, 0, 0, /* espera para [2] (bloqueo) sea igual 0

*entonces incrementa [2] en 1 - esto lo bloquea */

2, 1, SEM_UNDO /* UNDO para liberar el bloqueo si el proceso sale

* antes de desbloquear explicitamente */

};

static struct sembuf op_endcreate[2] = {

1, -1, SEM_UNDO, /* decrementa [1] (contador de procesos) con undo en

* caso de finalizar */

/* UNDO para ajustar el contador de procesos en caso de

* acabar antes de llamar explicitamente a semClose() */

2, -1, SEM_UNDO /* entonces decrementa [2] (bloqueo) de vuelta a 0 */ };

static struct sembuf op_open[1] = { 1, -1, SEM_UNDO /* decrementa [1] (contador de proceso) con undo en

* caso de finalizar */

};

static struct sembuf op_close[3] = {

2, 0, 0, /* espera hasta que [2] (bloqueo) sea igual a 0 */ 2, 1, SEM_UNDO, /* entonces incrementa [2] en 1 - esto lo bloquea */ 1, 1, SEM_UNDO /* entonces incrementa [1] (contador de procesos) */

};

static struct sembuf op_unlock[1] = {

2, -1, SEM_UNDO /* decrementa [2] (bloqueo) de vuelta a 0 */

};

static struct sembuf op_op[1] = {

0, 99, SEM_UNDO /* decrementa o incrementa [0] con undo en caso de

* finalizar */

/* El 99 se substituye con la cantidad real que hay

* que substraer (positiva o negativa) */

};

/****************************************************************************

* Crea un semaforo con un valor inicial especificado.

* Si el semaforo existe, no se inicializa (por su puesto).

* Se devuelve la identidad del semaforo si todo va bien, si no -1.

*/

int semCreate(key_t key, int initval) {

register int id, semval;

union semun {

int val;

struct semid_ds *buf; ushort *array;

} semctl_arg;

if (key == IPC_PRIVATE)

return(-1); /* no utilizable para semaforos privados */

else if (key == (key_t) -1) return(-1); /* probablemente una llamada erronea anterior a ftok() */

deNuevo:

if ( (id = semget(key, 3, 0666 | IPC_CREAT)) < 0)

return(-1); /* problemas de permisos o tablas llenas */

/* Cuando se crea el semaforo, sabemos que el valor de todos los * miembros es 0. * * Bloquear el semaforo esperando a que [2] sea 0, e incrementarlo. * * Hay una condicion de carrera: Cabe la posibilidad de que entre el * semget() de arriba y el semop() de abajo, otro proceso pueda llamar * a semClose() que puede borrar el semaforo si el ultimo lo esta * usando. * * Ademas, se maneja la condicion de error sobre el identificador. * Si esto ocurre, se vuelve atras y se intenta crear de nuevo. */

if (semop(id, &op_lock[0], 2) < 0) {

if (errno == EINVAL)

goto deNuevo;

fprintf(stderr, "semCreate: no puedo bloquear\n");

}

/* Obtener el valor del contador de procesos. Si es igual a 0,

* entonces ninguno ha inicializado el semaforo aun. */

if ( (semval = semctl(id, 1, GETVAL, 0)) < 0)

fprintf(stderr, "semCreate: no puedo realizar GETVAL\n");

if (semval == 0) {

/* Podriamos inicializar mediante SETALL, pero podria borrar el

* ajuste del valor que se realizo cuando se bloqueo el semaforo antes.

* En su lugar, se hacen dos llamadas al sistema para inicializar

* [0] y [1].

*/

semctl_arg.val = initval;

if (semctl(id, 0, SETVAL, semctl_arg) < 0)

fprintf(stderr, "semCreate: puedo SETVAL[0]\n");

semctl_arg.val = BIGCOUNT;

if (semctl(id, 1, SETVAL, semctl_arg) < 0)

fprintf(stderr, "semCreate: puedo SETVAL[1]\n"); }

/* Decrementar el contador de procesos y desbloquear. */

if (semop(id, &op_endcreate[0], 2) < 0)

fprintf(stderr, "semCreate: no puedo acabar semCreate()\n");

return(id); }

/****************************************************************************

* Abre un semaforo que debe existir ya.

* Esta funcion deberia de usarse, en vez de semCreate(), si en la llamada

* se sabe que el semaforo deberia ya existir. Por ejemplo un cliente

* de un par cliente-servidor podria utilizarla, si es responsabilidad del

* servidor crear el semaforo. * Se vuelve la identidad del semaforo si va bien, si no -1.

*/

int semOpen(key_t key) {

register int id;

if (key == IPC_PRIVATE)

return(-1); /* no utilizable para semaforos privados */

else if (key == (key_t) -1)

return(-1); /* probablemente una llamada erronea anterior a ftok() */

if ( (id = semget(key, 3, 0)) < 0)

return(-1); /* no existe o las tablas estan llenas */

/* Decrementa el contador de procesos. No necesitamos un bloqueo

* para hacer esto. */

if (semop(id, &op_open[0], 1) < 0)

fprintf(stderr, "semOpen: no puedo abrir\n");

return(id); }

/****************************************************************************

* Borrar un semaforo.

* Se supone que esta llamada se realiza desde un servidor en operaciones como

* apagarServidor ... No importa si los otros procesos estan usandolo o no.

* El resto de los procesos deberian emplear semClose().

*/

void semRm(int id) {

if (semctl(id, 0, IPC_RMID, 0) < 0)

fprintf(stderr, "semRm: no puedo borrar semaforo (IPC_RMID)\n");

}

/****************************************************************************

* Cerrar el semaforo.

* Funcion por proceso que decrementa el numero de procesos activos en el

* semaforo. Se emplea al salir. Si el proceso es el ultimo destruye el

* semaforo.

*/

void semClose(int id) {

register int semval;

/* En primer lugar bloquear el recurso semaforo e incrementar el contador

* de procesos [1].

*/

if (semop(id, &op_close[0], 3) < 0)

fprintf(stderr, "semClose: no puedo bloquer en semClosep\n");

/* Comprobar si el valor leido es la ultima referencia al semaforo.

*/

if ( (semval = semctl(id, 1, GETVAL, 0)) < 0)

fprintf(stderr, "semClose: no puedo realizar GETVAL\n");

if (semval > BIGCOUNT)

fprintf(stderr, "<<sem[1] > BIGCOUNT>>\n");

else if (semval == BIGCOUNT)

semRm(id);

else if (semop(id, &op_unlock[0], 1) < 0)

fprintf(stderr, "semClose: no puedo desbloquear\n"); /* desbloqueo */

}

/****************************************************************************

* Espera hasta que el valor del semaforo sea mayor que 0, entonces

* decrementa en 1 y vuelve. Operador wait, DOWN (Tanenbaum) o P (Dijkstra).

*/

void semWait(int id) {

semOp(id, -1);

}

/****************************************************************************

* Incrementar el semaforo en 1. Operador segnal, UP (Tanenbaum) o

* V (Dijkstra).

*/

void semSignal(int id) {

semOp(id, 1);

}

/****************************************************************************

* Operacion generica de semaforo:

* incrementar o decrementar cierta cantidad positiva o negativa, distinta

* de cero.

*/

void semOp(int id, int value) {

if ( (op_op[0].sem_op = value) == 0)

(void) fprintf(stderr, "semOp: 'valor' no puede ser 0\n");

if (semop(id, &op_op[0], 1) < 0) (void) fprintf(stderr, "semOp: error\n"); }

volver al menu

************************************************************************************************

************************************************************************************************

/* librerias*/

#include "rshmem.h"

#include <sys/sem.h>

/*numero de mandriles que vienen por el norte*/

#define NummandrilN 10

/* numero de mandriles que vienen por el sur*/

#define NummandrilS 15

/*estructura de variable compartida que sirve para regular el paso de los mandtiles por el puente*/

typedef struct puente{

int dentroN;

int dentroS;

int esperandoN;

int esperandoS;

int turnoN; /*FALSE=1,true=0*/

int turnoS;

int pasadosN;

int pasadosS;

int permisoN; /*semoforos*/

int permisoS;

}PUENTE;

PUENTE *puente; /* declaracion global */

/*DECLARACION DE LA FUNCION caminoNorte */

void caminoNorte(int mandrilN,FILE *pf){

puente->esperandoN=puente->esperandoN+1;

/*si al llegar un mandril por el norte, hay algun mandril Sur cruzando el puente o turnoSur es falso junto con que hay mandriles esperando en el sur, entonces el mandril debe esperar*/

while((puente->dentroS>0) || (!puente->turnoS>0 && puente->esperandoS>0)){

semWait(puente->permisoN); /*espera del semaforo norte*/

}

puente->esperandoN=puente->esperandoN-1;

puente->dentroN=puente->dentroN+1;

puente->pasadosN=(puente->pasadosN+1)%4; /*como maximo pasan 4 seguidos */

if(puente->pasadosN==0){

puente->turnoN=1;/*false*/

puente->turnoS=0;/*true*/

}

/* los mandriles estan cruzando el puente*/

puente->dentroN=puente->dentroN-1;

if((puente->dentroN==0)&&(puente->turnoS==0||puente->esperandoN==0)){

/*para escribir en fichero de salida*/

(void)fprintf(pf,"El mandril %d del norte ha pasado\n",mandrilN);

fflush(pf);

semSignal(puente->permisoS); /*señal semaforo sur*/

} exit(0);

}/*FIN FUNCION*/

/*DECLARACION DE LA FUNCION caminoSur*/

void caminoSur(int mandrilS,FILE *pf){

puente->esperandoS=puente->esperandoS+1;

while((puente->dentroN>0)||(!puente->turnoN>0 && puente->esperandoN>0)){

semWait(puente->permisoS); /*espera semaforo sur*/ }

puente->esperandoS=puente->esperandoS-1;

puente->dentroS=puente->dentroS+1;

puente->pasadosS=(puente->pasadosS+1)%4; /*como maximo pasan 4 seguidos */

if(puente->pasadosS==0){

puente->turnoS=1;/*false*/

puente->turnoN=0;/*true*/ }

/*los mandriles estan cruzando el puente*/

puente->dentroS=puente->dentroS-1;

if((puente->dentroS==0)&&(puente->turnoN==0||puente->esperandoS==0)){

/*para escribir en fichero de salida*/

(void)fprintf(pf,"El mandril %d del sur ha pasado\n",mandrilS);

fflush(pf);

semSignal(puente->permisoN); /*se¤al semaforo norte */

}

exit(0);

}/*FIN FUNCION*/

void main(){

/*declaracion de variables*/

FILE *pf;

int i;

key_t sclaveN, sclaveS;

/* CREAR ZONA DE MEMORIA COMPARTIDA: VARIABLE PUENTE */

if(!crearMemoria())

fprintf(stderr,"error de crearMemoria()\n");

puente=(PUENTE*) memoria;

/*INICIALIZO PUENTE*/

memset(puente,0,sizeof(PUENTE));

/* ABRIR FICHERO SALIDA */

if((pf=fopen("salida", "w+"))==NULL){

fprintf(stderr,"error al abrir el fichero para salidas\n"); exit(-1); }

/* CLAVE SEMAFORO PERMISO NORTE */

if((key_t) -1 ==(sclaveN=ftok("fich.tmp",'A'))){

fprintf(stderr,"main: error crear clave semaforo permiso norte\n");

exit(1);

}

/*CREAR SEMAFORO NORTE*/

if(-1==(puente->permisoN=semCreate(sclaveN,1))){

fprintf(stderr,"main: no pude crear semaforo norte)\n"); exit(1);

}

/* CLAVE SEMAFORO PERMISO SUR */

if((key_t)-1==(sclaveS=ftok("fich.tmp",'B'))){

fprintf(stderr,"main: error crear clave semaforo permiso sur \n");

exit(1);

}

/*CREAR SEMAFORO SUR*/

if(-1==(puente->permisoS=semCreate(sclaveS,1))){

fprintf(stderr,"main: no pude crear semaforo sur \n");

exit(1);

}

/*ABRIR SEMAFOROS*/

if (-1==(puente->permisoN=semOpen(sclaveN)))

fprintf(stderr,"no tengo el cualifacador semaforo norte\n");

if (-1==(puente->permisoS=semOpen(sclaveS)))

fprintf(stderr,"no tengo el cualifacador semaforo sur\n");

/*MANDRILES NORTE*/

for(i=0;i<NummandrilN;i++){

if(0==fork())

caminoNorte(i,pf);

}

/*MANDRILES SUR*/

for(i=0;i<NummandrilS;i++){

if(0==fork())

caminoSur(i,pf);

}

/*ESPERAR A QUE TERMINEN LOS PROCESOS HIJOS*/

for(i=0;i<NummandrilN+NummandrilS;i++)

wait(NULL);

/*CERRAR FICHERO SALIDA*/

fclose(pf);

/*ELIMINAR MEMORIA COMPARTIDA DE LA VARIABLE PUENTE */

if(!eliminarMemoria())

fprintf(stderr,"error de eliminarMemoria()\n");

/* CERRAR SEMAFOROS */

semClose(puente->permisoN);

semClose(puente->permisoS);

exit(0);

} /* FIN MAIN */

volver al menu

************************************************************************************************

************************************************************************************************

volver al menu

************************************************************************************************

************************************************************************************************

VERONICA BACIERO GONZALEZ

MONICA DE LA IGLESIA GARCIA

volver al menu