El problema de la cena de los filósofos. Cinco filósofos
se sientan en una mesa. Cada uno tiene un plato de espaghetti. El espaghetti
es tan escurridizo que un filósofo necesita dos tenedores (en nuestro
caso llamados palillos) para comerlo. Entre cada dos platos hay un "palillo",
luego existe el mismo númerode filósofos que de palillos.
La vida de un filósofo consta de periodos alternados de comer y pensar. Cuando un filósofo siente hambre, intenta coger el palillo de la izquerda y si lo consigue, lo intenta con el de la derecha. Si logra asir dos palillos toma unos bocados y después deja los cubiertos y sigue pensando.
La solución de este problema se basa en implementar un algoritmo eficiente en el manejo de semáforos y memoria compartida que seguidamente describimos. A lo largo del programa se utilizan funciones necesarias para el manejo de memoria compartida (véase "rshmem.h Y "rshmem.c") manejo de semáforos (véase "semaph.c" .)
Se considera a cada filósofo como un proceso y cada palillo como un recurso. De modo que, para que un proceso acceda al recurso que necesita, tenemos que considerar a cada palillo como un semáforo. Este semáforo es binario y vale 0 si el palillo está siendo utilizado por otro proceso y 1 si el palillo está disponible.
<Ver programa "FILOS.C" ,>
LA FUNCION MAIN:
Creación de un proceso padre y de sus N procesos hijos (filósofos).
FUNCIONES DEL PROGRAMA:
NOMBRE
incrementa;
filosofo;
SINOPSIS
incrementa ( int * mem , int k );
void filosofo( FILE * pf , key_t * sclave, int * spalillo, int scomer, int i, int * comer, int * fin);
DESCRIPCION
incrementa( ); Esta función implementa el acceso a un recurso compartido, que será la variable que contabiliza el total de veces que comen todos los filósofos. En esta función se han incluido varias llamadas al macro TP. Este macro implementa un retardo aleatorio con el fin de dar cierto tiempo a que ocurran interrupciones que puedan detener la ejecución del proceso en su "cuanto" de tiempo asignado por el S.O.. En nuestro caso, es necesario realizar unas cuantas llamadas para dar tiempo a que todos los filósofos tengan oportunidad de comer.
filosofo( ); Permite que el filósofo pueda acceder a los dos palillos que necesita (izquerda y derecha) y coma. Una vez que acaba de comer se encarga de dejar los palillos útiles para que sean de nuevao utilizados (por él o por otros). Para ello se basa en funciones de manejo de semáforos y memoria compartida.
Utiliza las siguientes funciones:
Manejo de semaforos:
Manejo de memoria compartida:
Cada vez que come un filósofo lo refleja en el incremento de la variable de memoria compartida.
Cuando los filósofos han comido un número M de veces prefijado se lo comunican al padre, no sin antes haber cerrado adecuadamente todos los semáforos utilizados en esta función.
NOTA IMPORTANTE:
El abrazo mortal se produce cuando todos los filósofos han cogido al mesmo tiempo su palillo izquierdo, con lo cual, ninguno puede coger el derecho , no pueden comer y se acabó.
DEPENDENCIAS:
ficheros:
macros:
variables de memoria compartida:
EJEMPLO:
La salida del programa se encuentra en el fichero "fich" <Vease el fichero "fich" >.
AUTORAS:
INES MARTIN SALVADOR
ISABEL MARTIN SALVADOR
FECHA:
VALLADOLID, 29 DE MAYO DE 1997.
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
#include "rshmem.h"
#include <stdlib.h>
#define N 5
#define M 50
/* Declaracion de la funcion incrementa */
incrementa (int *mem, int k){
int i;
i=*mem;
TP ; TP ; TP TP ;
TP ; TP TP ; TP ;
TP TP ; TP ; TP
i=i+k;
TP ; TP ; TP TP ;
TP ; TP TP ; TP ;
TP TP ; TP ; TP
*mem=i;
}
/* Declaracion de la funcion filosofo: uso de semaforos */
void filosofo(FILE *pf, key_t *sclave, int *spalillo, int scomer, int
i, int *comer, int *fin){
/* ABRIR SEMAFOROS */
/*Abrir semaforo de la izquierda del filosofo */
if (-1==(spalillo[i]=semOpen(sclave[i])))
fprintf(stderr,"no tengo el cualificador del semaforo palillo %d\n",i);
/*Abrir semaforo de la derecha del filosofo */
if (-1==(spalillo[(i+1)%N]=semOpen(sclave[(i+1)%N])))
fprintf(stderr,"no tengo el cualifacador semaforo palillo %d\n",(i+1)%N);
/*Abrir semaforo de la variable comer y variable fin:memoria compartida*/
if (-1==(scomer=semOpen(sclave[N])))
fprintf(stderr,"no tengo el cualifacador semaforo scomer\n");
/* COMER M VECES */
while(*comer<M){
semWait(spalillo[i]);
semWait(spalillo[(i+1)%N]);
semWait(scomer);
incrementa(comer,1);
(void) fprintf(pf,"[comer:%.4d] el filosofo %d ha comido\n",
*comer, i);
fflush(pf); /* para sincronizar la escritura de datos en el fichero de
saliadas */
semSignal(scomer);
semSignal(spalillo[(i+1)%N]);
semSignal(spalillo[i]);
}
/* CERRAR SEMAFOROS Y TERMINAR */
semClose(spalillo[i]);
semClose(spalillo[(i+1)%N]);
semClose(scomer);
(*fin)++;
exit(1);
}
int main(){
FILE *pf; /*puntero a fichero salidas */
key_t sclave[N+1]; /*array de claves para semaforos */
int scomer; /*semaforo para variable comer (s.c.) */
int spalillo[N]; /*un semaforo por palillo */
int *comer; /*variable de memoria compartida */
int *fin; /*variable de memoria compartida */
int i; /*contador */
/* Abrir fichero de salidas */
if((pf=fopen("fich", "w+"))==NULL){
fprintf(stderr,"error al abrir el fichero para salidas\n");
exit(-1);
}
/* SEMAFOROS PARA PALILLOS */
for(i=0; i<N; i++){
/*crear nombres claves palillos */
if((key_t)-1==(sclave[i]=ftok("filos",'s'+i))){
fprintf(stderr,"main: error crear clave palillo %d con ftok(%c)\n",
i,'s'+i);
exit(1);
}
/*crear semaforos palillos */
if(-1==(spalillo[i]=semCreate(sclave[i],1))){
fprintf(stderr,"main: no pude crear semaforo palillo %d\n",i);
exit(1);
}
}
/* SEMAFORO PARA VARIABLE COMER */
if((key_t)-1==(sclave[N]=ftok("filos",'r'))){
fprintf(stderr,"main: error crear clave comer con ftok()\n");
exit(1);
}
if(-1==(scomer=semCreate(sclave[N],1))){
fprintf(stderr,"main: no pude crear semaforo para comer (s.c.)\n");
exit(1);
}
/* CREAR ZONA DE MEMORIA COMPARTIDA: VARIABLE COMER */
if(!crearMemoria())
fprintf(stderr,"error de crearMemoria()\n");
/*inicializar variable comer y variable fin */
comer = (int *) memoria;
*comer = 0;
fin = (int *) comer + sizeof(int);
*fin = 0;
/* PROCESO PADRE */
for(i=0; i<N; i++){
if(0==fork())/* PROCESOS HIJOS */
filosofo(pf, sclave, spalillo, scomer, i, comer, fin);
}
while(*fin<5); /*espera a que los filosofos coman M veces */
fprintf(pf,"no habia comido ningun filososo y ahora han comido
%d", *comer);
fclose(pf);
/* TERMINA */
/* eliminar memoria de las variables compartidas */
if(!eliminarMemoria())
fprintf(stderr,"error de eliminarMemoria()\n");
/* cerrar semaforos */
semClose(scomer);
for(i=0; i<N; i++)
semClose(spalillo[i]);
exit(0);
} /*fin proceso padre, fin main */
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/*
* 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();
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
#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;
}
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
Implementación de funciones de manejo de semáforos en UNIX
/*
* 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
*
despues 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
/*
despues 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, /* despues incrementa [2] en 1 - esto lo bloquea */
1, 1, SEM_UNDO /* despues 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");
}
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
[comer:0001] el filosofo 0 ha comido
[comer:0002] el filosofo 0 ha comido
[comer:0003] el filosofo 1 ha comido
[comer:0004] el filosofo 0 ha comido
[comer:0005] el filosofo 0 ha comido
[comer:0006] el filosofo 0 ha comido
[comer:0007] el filosofo 1 ha comido
[comer:0008] el filosofo 1 ha comido
[comer:0009] el filosofo 1 ha comido
[comer:0010] el filosofo 1 ha comido
[comer:0011] el filosofo 1 ha comido
[comer:0012] el filosofo 1 ha comido
[comer:0013] el filosofo 1 ha comido
[comer:0014] el filosofo 1 ha comido
[comer:0015] el filosofo 1 ha comido
[comer:0016] el filosofo 1 ha comido
[comer:0017] el filosofo 1 ha comido
[comer:0018] el filosofo 1 ha comido
[comer:0019] el filosofo 1 ha comido
[comer:0020] el filosofo 1 ha comido
[comer:0021] el filosofo 1 ha comido
[comer:0022] el filosofo 1 ha comido
[comer:0023] el filosofo 1 ha comido
[comer:0024] el filosofo 1 ha comido
[comer:0025] el filosofo 1 ha comido
[comer:0026] el filosofo 1 ha comido
[comer:0027] el filosofo 1 ha comido
[comer:0028] el filosofo 1 ha comido
[comer:0029] el filosofo 1 ha comido
[comer:0030] el filosofo 3 ha comido
[comer:0031] el filosofo 0 ha comido
[comer:0032] el filosofo 4 ha comido
[comer:0033] el filosofo 3 ha comido
[comer:0034] el filosofo 4 ha comido
[comer:0035] el filosofo 4 ha comido
[comer:0036] el filosofo 4 ha comido
[comer:0037] el filosofo 2 ha comido
[comer:0038] el filosofo 1 ha comido
[comer:0039] el filosofo 3 ha comido
[comer:0040] el filosofo 2 ha comido
[comer:0041] el filosofo 1 ha comido
[comer:0042] el filosofo 1 ha comido
[comer:0043] el filosofo 1 ha comido
[comer:0044] el filosofo 1 ha comido
[comer:0045] el filosofo 1 ha comido
[comer:0046] el filosofo 1 ha comido
[comer:0047] el filosofo 1 ha comido
[comer:0048] el filosofo 1 ha comido
[comer:0049] el filosofo 1 ha comido
[comer:0050] el filosofo 1 ha comido
no habia comido ningun filososo y ahora han comido 50