El problema de la cena de los filósofos o de los filósofos cenando fue propuesto por Dijkstra en 1965. Es un problema de gran importancia en la programación concurrente, ya que permite modelar muchas de las situaciones que se producen en la programación concurrente de una forma muy gráfica.
El problema de la cena de los filósofos consiste en lo siguiente. Existen cinco filósofos que se dedican básicamente a pensar. Sin embargo, ocasionalmente necesitan cubrir la necesidad fisiológica de comer. La vida de un filósofo consiste en el ciclo pensar, comer y volver a pensar. Cuando necesitan comer se sientan a la mesa, pero para comer necesitan emplear los dos tenedores que se encuentran al lado de su plato. El problema es que sólo hay cinco tenedores, lo que impide que todos los filósofos puedan comer a la vez. En la figura se muestra la mesa.
Cuando el filósofo va a comer intenta obtener el tenedor derecho y el tenedor izquierdo situados al lado de su plato. Si consigue los dos tenedores come durante un tiempo, y después deja los dos tenedores, por los que pueden estar esperando los filósofos vecinos a él, y se pone a pensar nuevamente.
El problema consiste en encontrar un algoritmo que permita administrar el proceso de los cinco filósofos.
El filósofo i sólo puede utilizar los tenedores adyacentes a su plato. Nunca pueden comer a la vez dos filósofos vecinos.
Así pues este problema presenta las siguientes situaciones :
Existen varias soluciones a este problema, planteadas
según el tipo de primitivas empleadas para su resolución.
A continuación se plantean algunas de estas soluciones :
La solución obvia empleando semáforos
consistiría en la ejecución concurrente del procedimiento
siguiente, para cada uno de los filósofos :
N = Número de filósofos, numerados de 0 a N-1
Tenedor = Vector de semáforos. Un semáforo por cada tenedor, de 0 a N-1. Inicialmente los semáforos están a 1 (libres).
Filósofo(i) :
- Repetir
- Pensar()
- wait(Tenedor(i)) /* Esperar que esté libre y Coger el tenedor izquierdo */
- wait(Tenedor(i+1 mod N)) /* Esperar esté libre y Coger el tenedor derecho */
- Comer()
- signal(Tenedor(i)) /* Dejar el tenedor izquierdo */
- signal(Tenedor(i+1 mod N)) /* Dejar el tenedor derecho */
- Fin_repetir
Esta solución garantiza el acceso exclusivo a los recursos, ya que un tenedor sólo puede pertenecer a un filósofo. Además la exclusión mutua se garantiza ya que un filósofo sólo come después de que los dos tenedores en forma de semáforos han sido bloqueados.
Desafortunadamente, esta solución no es correcta,
ya que puede ocurrir que los cinco filósofos se pongan
a comer a la vez y adquieran su tenedor izquierdo correspondiente,
pero se queden esperando infinitamente a que su vecino derecho
libere el tenedor que les falta. Así pues, esta solución
produce bloqueo mutuo o dead-lock.
Una solución simple sería modificar
el algoritmo de tal forma que después de coger el tenedor
izquierdo, el filósofo comprueba si el tenedor derecho
está ocupado ; si lo está deja el tenedor izquierdo,
espera cierto tiempo y lo vuelve a intentar. Pero esta solución
también puede fallar en una situación de mala suerte,
si todos los filósofos comienzan al mismo tiempo, esperan
al mismo tiempo, y lo intentan de nuevo al mismo tiempo. A esta
situación se le denomina inanición (ya que ningún
filósofo comería, a pesar de que tiene actividad).
Otra solución es proteger la sección crítica mediante un semáforo binario. De esta forma tendríamos la siguiente solución :
seccion_critica : semáforo binario de acceso a la sección critica, inicialmente a 1.
Filósofo(i) :
- Repetir
- Pensar()
- wait(seccion_critica) /* Espera y Entra en la sección crítica */
- wait(Tenedor(i)) /* Esperar que esté libre y Coger el tenedor izquierdo */
- wait(Tenedor(i+1 mod N)) /* Esperar esté libre y Coger el tenedor derecho */
- Comer()
- signal(Tenedor(i)) /* Dejar el tenedor izquierdo */
- signal(Tenedor(i+1 mod N)) /* Dejar el tenedor derecho */
- signal(seccion_critica) /* Deja libre el acceso a la sección crítica */
- Fin_repetir
Esta solución aunque es correcta, ya que no
produce deadlock ni tampoco inanición, no parece adecuada,
ya que en cada instante sólo existiría un filósofo
comiendo, lo cual no maximiza el paralelismo del problema.
Una solución similar a la anterior en cuanto estructura, pero con cierta variación consiste en proteger el acceso a la sección crítica mediante un semáforo que tome valores entre 0 y N-1, de tal forma que todos los filósofos no pueden sentarse a comer a la vez en la mesa. El procedimiento a ejecutar por cada uno de los N filósofos sería :
mesa : semáforo de acceso a la mesa (sección critica), inicialmente a N-1.
Filósofo(i) :
- Repetir
- Pensar()
- wait(mesa) /* Espera por la mesa y Entra en la sección crítica */
- wait(Tenedor(i)) /* Esperar que esté libre y Coger el tenedor izquierdo */
- wait(Tenedor(i+1 mod N)) /* Esperar esté libre y Coger el tenedor derecho */
- Comer()
- signal(Tenedor(i)) /* Dejar el tenedor izquierdo */
- signal(Tenedor(i+1 mod N)) /* Dejar el tenedor derecho */
- signal(mesa) /* Deja libre el acceso a la mesa */
- Fin_repetir
Esta solución es correcta, pues garantiza la exclusión mutua. Además, no produce dead-lock, ya que el semáforo mesa garantiza que sólo pueden estar N-1 filósofos comiendo a la vez, con lo cual siempre habrá algún filósofo que pueda adquirir los dos tenedores, y tras comer, libere sus tenedores para los filósofos vecinos. Todo se debe a que se verifica en todo momento el siguiente invariante :
Valor semáforo mesa + Nº de procesos
en la sección crítica = N-1
Otra solución válida al problema de los filósofos consiste en implementar la solución mediante monitores. Con esta solución el monitor recubre los procedimientos de acceso a los recursos críticos. De esta forma se garantiza que sólo un proceso de cada filósofo estará ejecutando un procedimiento del monitor, y accediendo por tanto a los recursos críticos, que en este caso son los tenedores (variable EstadoFil en el ejemplo).
En la implementación que se presenta, la variable EstadoFil es un vector con una componente por cada uno de los N filósofos, que puede tomar valores 0 (los dos tenedores izquierdo y derecho están ocupados), 1 (el tenedor izquierdo está ocupado y el derecho libre) y 2 (los dos tenedores izquierdo y derecho están libres).
Los algoritmos del monitor y de cada filósofo
son los siguientes :
Monitor TenedorFilosofo :
* EstadoFil : vector de estado de los N filósofos. Cada componente puede tomar el valor 0, 1 ó 2
* PoderComer : vector de variables de condición para los N filósofos.
Procedimiento CogerTenedor(i)
- Si EstadoFil(i) != 2 /* Si los dos tenedores no están disponibles */
wait(PoderComer(i)) /* espero a que lo indiquen para comer */
- Fin_si
/* Actualizamos el estado de los filósofos vecinos */
EstadoFil((i-1) mod N)) = EstadoFil((i-1) mod N)) - 1
EstadoFil((i+1) mod N)) = EstadoFil((i+1) mod N)) - 1
Fin_procedimiento
Procedimiento DejarTenedor(i)
/* Actualizamos el estado de los filósofos vecinos */
EstadoFil((i-1) mod N)) = EstadoFil((i-1) mod N)) + 1
EstadoFil((i+1) mod N)) = EstadoFil((i+1) mod N)) + 1
/* Si los tenedores del filósofo izquierdo están libres, indicárselo */
- Si EstadoFil((i-1) mod N)) == 2
signal(PoderComer((i-1) mod N))
- Fin_si
/* Si los tenedores del filósofo derecho están libres, indicárselo */
- Si EstadoFil((i+1) mod N)) == 2
signal(PoderComer((i+1) mod N))
- Fin_si
Fin_procedimiento
Fin_monitor
Filósofo(i) :
- Repetir
- Pensar()
- CogerTenedor(i) /* Coger los tenedores izquierdo y derecho */
- Comer()
- DejarTenedor(i) /* Dejar los tenedores izquierdo y derecho */
- Fin_repetir
La solución con monitores parece muy atractiva, pero su implementación no suele ser posible en los lenguajes de programación, ya que éstos no poseen primitivas de gestión de monitores. Sin embargo mediante variables de condición y mútex se pueden implementar procedimientos cuyo funcionamiento es idéntico a si perteneciesen a un monitor. La solución consiste en recubrir el acceso a cada procedimiento del monitor mediante un mútex (semáforo binario que garantiza el acceso exclusivo). De esta forma se garantiza que en un momento dado sólo habrá un filósofo ejecutando el interior de los procedimientos CogerTenedor o DejarTenedor, el resto podrán estar bloqueados a la espera de poder acceder.
De esta forma el algoritmo del monitor se transforma
en los siguientes procedimientos :
EstadoFil : vector de estado de los N filósofos. Cada componente puede tomar el valor 0, 1 ó 2
PoderComer : vector de variables de condición para los N filósofos.
seccion_critica : mutex de acceso a la sección crítica. Inicialmente liberado.
CogerTenedor(i) :
- bloquear_mutex(seccion_critica) /* Bloquear el acceso a la sec. crítica */
- Mientras EstadoFil(i) != 2 /* Si los dos tenedores no están disponibles */
wait(PoderComer(i), seccion_critica) /* espero a que lo indiquen para comer */
- Fin_mientras /* sino, me bloqueo y libero la sec. crítica */
/* Actualizamos el estado de los filósofos vecinos */
EstadoFil((i-1) mod N)) = EstadoFil((i-1) mod N)) - 1
EstadoFil((i+1) mod N)) = EstadoFil((i+1) mod N)) - 1
- liberar_mutex(seccion_critica) /* Liberar el acceso
a la sec. crítica */
DejarTenedor(i) :
- bloquear_mutex(seccion_critica) /* Bloquear el acceso a la sec. crítica */
/* Actualizamos el estado de los filósofos vecinos */
EstadoFil((i-1) mod N)) = EstadoFil((i-1) mod N)) + 1
EstadoFil((i+1) mod N)) = EstadoFil((i+1) mod N)) + 1
/* Si los tenedores del filósofo izquierdo están libres, indicárselo */
- Si EstadoFil((i-1) mod N)) == 2
signal(PoderComer((i-1) mod N))
- Fin_si
/* Si los tenedores del filósofo derecho están libres, indicárselo */
- Si EstadoFil((i+1) mod N)) == 2
signal(PoderComer((i+1) mod N))
- Fin_si
- liberar_mutex(seccion_critica) /* Liberar el acceso
a la sec. crítica */
Filósofo(i) :
- Repetir
- Pensar()
- CogerTenedor(i) /* Coger los tenedores izquierdo y derecho */
- Comer()
- DejarTenedor(i) /* Dejar los tenedores izquierdo y derecho */
- Fin_repetir
El problema de la cena de los filósofos que
se presenta a continuación corresponde a la implementación
del algoritmo empleando mútex y variables de condición.
El programa que se muestra como ejemplo es meramente demostrativo
y permite que se le varíen una serie de parámetros
para comprobar su funcionamiento. Los periodos de cena y pensamiento
están simulados mediante un bucle de iteraciones que puede
ser fijo o aleatorio según se indique. Además existe
un factor de tiempo para comer y un factor de tiempo para pensar
que se pueden modificar, y que influyen en los tiempos de cena
y pensamiento, respectivamente. Se puede, opcionalmente, presentar
una serie de textos explicativos de la evolución de los
estados de los filósofos.
La implementación que se presenta se ha realizado para el sistema operativo Linux 1.2, y se han empleado procesos. Se crea un proceso hijo por cada filósofo mediante la sentencia fork() de UNIX. Mientras que el proceso padre se limita a esperar a que los filósofos perezcan. Los datos de interés (estado de los filósofos, variables de condición y mútex de acceso) se almacenan en memoria compartida, para que puedan ser accedidos por todos los procesos filósofos. La sincronización del acceso al estado de los filósofos se ha conseguido empleando las variables de condición, relacionadas con la condición de poder comer (tenedores disponibles) y un mútex (equivalente a un semáforo binario) que garantiza el acceso exclusivo a los datos críticos. Tanto las variables condicionales como los mútex son estructuras que no existen en un sistema UNIX habitual, pero se han simulado mediante semáforos a través de una serie de pequeñas funciones que encapsulan su funcionamiento, y que se encuentran en la biblioteca de rutinas comunes a todos los ejemplos. La razón para hacer esto es presentar un aspecto similar, a fin de comparar el programa con la versión multihilo del mismo programa que se presenta posteriormente, y distinguir claramente las pequeñas diferencias.
La sintaxis del programa es la siguiente :
filo [-?|-h] [num_filosofos [num_iteraciones [flag_aleatorio flag_eco [factor_comer [factor_pensar]]]]]] siendo :
El listado del programa fuente es el siguiente :
FILO.C /**************************************************************************** EJEMPLO DEL PROBLEMA DE LA CENA DE LOS FILOSOFOS (vers. procesos) Aplicacion: filo Version: 1.0p Fecha: 11/12/1996 Descripcion: Programa demostrativo del problema de los "filosofos-comiendo". Tenemos una serie de N filosofos con N tenedores. Cada filosofo ejecuta el ciclo pensar-comer. Pero para comer necesita dos tenedores el de su izquierda y el de su derecha. El problema es que los tenedores estan compartidos entre los filosofos adyacentes. Se crea un proceso hijo por cada filosofo y se emplea la tecnica de monitores apoyada en variables de condicion y mutex para regular el acceso a los tenedores. Implementacion mediante procesos. Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="filo 1.0p - Problema de la cena de los filosofos (vers. procesos)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [num_filosofos [num_iterac \ [flag_aleatorio [flag_echo [t_comer [t_pensar]]]]]]\n"; #include <stdlib.h> #include "error.h" #include "getstats.h" #include "mutex.h" #include "cond.h" /* Definicion de Identificadores de Claves de Recursos del Sistema */ #define SHMEM0_KEY ((key_t)188760L) #define SHMEM1_KEY ((key_t)188761L) #define SHMEM2_KEY ((key_t)188762L) #define MUTEX_KEY ((key_t)188863L) #define COND_BASE_KEY ((key_t)188864L) /* Definicion de constantes */ #define N_FILOSOFOS 50 /* Numero maximo de filosofos */ #define DEFAULT_ITER 30 /* Numero de ciclos para un filosofo por defecto */ #define T_PENSAR 100 /* Factor de tiempo empleado en pensar por defecto */ #define T_COMER 100 /* Factor de tiempo empleado en comer por defecto */ /* Filosofo a la IZQUIERDA del filosofo i */ #define IZQ(t) ( (t==0) ? (nfilos-1) : ((t-1) % nfilos) ) /* Filosofo a la DERECHA del filosofo i */ #define DER(t) ((t+1) % nfilos) /* Estados de un filosofo */ #define DOS_TENEDORES_LIBRES 2 #define UN_TENEDOR_OCUPADO 1 #define DOS_TENEDORES_OCUPADOS 0 /* Estructura de los datos criticos del MONITOR */ typedef struct s_datos_t { int *EstadoFilos; /* Vector de Estado de los Filosofos */ cond_t *PoderComer; /* Vector de Condiciones de poder comer */ mutex_t sc; /* Mutex de acceso a la secc.critica */ } datos_t; /* Datos del MONITOR compartidos por los filosofos */ datos_t *Datos; /* Variables globales para los filosofos: solo-lectura */ int nfilos; /* Numero de filosofos. Var. global */ int niter; /* Numero de iteraciones para cada filosofo */ int aleatorio; /* Flag de aleatoriedad de los tiempos: 1 = aleatorio; 0 = No_aleatorio */ int eco; /* Flag de eco: 1 = eco si; 0 = eco no */ int factorTc; /* Factor de tiempo de comer */ int factorTp; /* Factor de tiempo de pensar */ /* Declaracion de procedimientos auxiliares */ void GetArgs(int argc, char *argv[], int *n, int *ni, int *faleat, int *feco, int *ftc, int *ftp); datos_t *CrearMemoria(int *shmem_id, int n); void DestruirMemoria(int *shmem_id, datos_t *d); void init_data (datos_t *d, int n); void destroy_data (datos_t *d, int n); void VerEstadoFilosofos(); /* Declaracion de Procedimientos sobre el Problema */ void *Filosofo(void *arg); void Comer (int i, int v); void Pensar(int i, int v); /* Declaracion de Procedimientos del MONITOR*/ void CogerTenedor(int i); void DejarTenedor(int i); /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pid_t *fid; /* Vector de Identificadores de los Filosofos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int i; /* Var. temporal */ int shmem_id[3]; /* Identif. para la zona de memoria compartida */ /* Obtencion de argumentos */ GetArgs(argc, argv, &nfilos, &niter, &aleatorio, &eco, &factorTc, &factorTp); /* Crear memoria compartida */ Datos = CrearMemoria(shmem_id, nfilos); /* Inicializacion de los datos del Monitor */ init_data(Datos, nfilos); /* Crear memoria para los identificadores de los filosofos */ if ( (fid = (pid_t *) malloc(nfilos * sizeof(pid_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los filosofos"); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* Creacion de los filosofos */ for (i = 0; i<nfilos; i++) { switch ( (fid[i] = fork()) ) { /* No se pudo crear hijo */ case -1: ErrorFatal("Error en la creacion de un filosofo"); break; /* Proceso HIJO */ case 0: Filosofo( (void *)i ); exit(0); break; /* Proceso PADRE */ default: break; } } /* Esperamos la finalizacion de los filosofos */ for (i = 0; i<nfilos; i++) if (waitpid(fid[i], NULL, 0) <0) ErrorFatal("Error en la espera de un filosofo"); /* Obtener tiempos finales */ getestad(&estad[1]); /* Destruir los datos del monitor */ destroy_data(Datos, nfilos); /* Destruir memoria de los identificadores de los hilos */ free((void *)fid); /* Destruir memoria compartida */ DestruirMemoria(shmem_id, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); exit(0); } void *Filosofo(void *arg) { int c; int i = (int)arg; for (c = 0; c<niter; c++) { Pensar(i, c); CogerTenedor(i); Comer(i, c); DejarTenedor(i); } } /* PROCEDIMIENTOS DEL MONITOR */ void CogerTenedor(int i) { mutex_lock(&Datos->sc); while (Datos->EstadoFilos[i] != DOS_TENEDORES_LIBRES) { # ifdef DEBUG printf("Filosofo %d se bloquea en la condicion\n", i); # endif cond_wait(&Datos->PoderComer[i], &Datos->sc); } # ifdef DEBUG printf("Filosofo %d COGE tenedores\n", i); # endif Datos->EstadoFilos[IZQ(i)]--; Datos->EstadoFilos[DER(i)]--; # ifdef DEBUG VerEstadoFilosofos(); # endif mutex_unlock(&Datos->sc); } void DejarTenedor(int i) { mutex_lock(&Datos->sc); # ifdef DEBUG printf("Filosofo %d DEJA tenedores\n", i); # endif Datos->EstadoFilos[IZQ(i)]++; Datos->EstadoFilos[DER(i)]++; if (Datos->EstadoFilos[IZQ(i)] == DOS_TENEDORES_LIBRES) { cond_signal(&Datos->PoderComer[IZQ(i)]); } if (Datos->EstadoFilos[DER(i)] == DOS_TENEDORES_LIBRES) cond_signal(&Datos->PoderComer[DER(i)]); # ifdef DEBUG VerEstadoFilosofos(); # endif mutex_unlock(&Datos->sc); } void Pensar(int i, int v) { long c; long tpensar; tpensar = ( aleatorio ? (random() % 100) : 100 ) * factorTp; if (eco) printf("Filosofo %d PENSANDO por %d vez ...\n", i, v); /* Bucle de simulacion */ for (c = 0; c<tpensar; c++); } void Comer(int i, int v) { long c; long tcomer; tcomer = ( aleatorio ? (random() % 100) : 100 ) * factorTc; if (eco) printf("Filosofo %d COMIENDO por %d vez ...\n", i, v); /* Bucle de simulacion */ for (c = 0; c<tcomer; c++); } void VerEstadoFilosofos() { int i; for (i = 0; i<nfilos; i++) printf("Ten[%d] = %d\n", i, Datos->EstadoFilos[i] ); } /* Obtener la linea de argumentos */ void GetArgs(int argc, char *argv[], int *n, int *niter, int *faleat, int *feco, int *ftc, int *ftp) { printf(VERSION); /* Comprobar si se solicita ayuda */ if (argc > 1) { if ( strcmp(argv[1],"-?") == 0 || strcmp(argv[1],"-h") == 0 ) { printf(SINTAX, argv[0]); exit(0); } } *n = N_FILOSOFOS; *niter = DEFAULT_ITER; *faleat = 1; *feco = 1; *ftc = T_COMER; *ftp = T_PENSAR; /* Obtenemos la lista de argumentos */ switch(argc) { case 7: *ftp = atoi(argv[6]); if (*ftp<1) *ftp = T_PENSAR; case 6: *ftc = atoi(argv[5]); if (*ftc<1) *ftc = T_COMER; case 5: *feco = ( (atoi(argv[4]) == 0) ? 0 : 1 ); case 4: *faleat = ( (atoi(argv[3]) == 0) ? 0 : 1 ); case 3: *niter = atoi(argv[2]); if (*niter<1) *niter = DEFAULT_ITER; case 2: *n = atoi(argv[1]); if (*n<2 || *n>N_FILOSOFOS) *n = N_FILOSOFOS; case 1: break; default: printf(SINTAX, argv[0]); printf("El numero de argumentos es incorrecto!\n"); exit(1); } } /* Proposito: Crear zona de memoria compartida por los filosofos. Entrada: n = Numero de filosofos. Salida: shmem_id[] = Vector de identificadores de memoria compartida. return = Puntero a la zona de memoria compartida. */ datos_t *CrearMemoria(int *shmem_id, int n) { datos_t *d; /* Crear memoria compartida */ if ((shmem_id[0] = shmget(SHMEM0_KEY, sizeof(datos_t), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida"); if ((d = (datos_t *) shmat(shmem_id[0], (char *)0, 0)) == (datos_t *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); if ((shmem_id[1] = shmget(SHMEM1_KEY, n * sizeof(int), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida para los Filosofos"); if ((d->EstadoFilos = (int *) shmat(shmem_id[1], (char *)0, 0)) == (int *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); if ((shmem_id[2] = shmget(SHMEM2_KEY, n * sizeof(cond_t), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida para las Condiciones"); if ((d->PoderComer = (cond_t *) shmat(shmem_id[2], (char *)0, 0)) == (cond_t *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); return(d); } /* Proposito: Destruir zona de memoria compartida por los filosofos. Entrada: shmem_id = Vector de identif. de memoria compartida. d = Puntero a la zona de memoria compartida. Salida: Ninguna */ void DestruirMemoria(int *shmem_id, datos_t *d) { /* Destruir memoria compartida */ if ( shmdt((char *)d->PoderComer) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_id[2], IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); if ( shmdt((char *)d->EstadoFilos) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_id[1], IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); if ( shmdt((char *)d) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_id[0], IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); } /* Inicializacion de los datos del MONITOR */ void init_data(datos_t *d, int n) { int i; /* Inicializacion del mutex */ if ( mutex_init(&d->sc, MUTEX_KEY )<0 ) ErrorFatal("Error en la inicializacion del mutex"); /* Inicializacion del estado de los Filosofos y var. de condicion */ for (i = 0; i<n; i++) { d->EstadoFilos[i] = DOS_TENEDORES_LIBRES; if (cond_init(&d->PoderComer[i], COND_BASE_KEY+i )<0) ErrorFatal("Error en la inicializacion de una condicion"); } } /* Destruccion de los datos del MONITOR */ void destroy_data(datos_t *d, int n) { int i; /* Destruccion de las variables de condicion y mutex */ for (i = 0; i<n; i++) cond_destroy(&d->PoderComer[i]); mutex_destroy(&d->sc); }
Este programa necesita, como ocurre en otros ejemplos,
los ficheros de cabecera GETSTATS.H, ERROR.H,
PARAM.H, SEMAFORO.H, MUTEX.H y COND.H, y los
ficheros fuente GETSTATS.C, ERROR.C, SEMAFORO.C, MUTEX.C
y COND.C, que se encuentran en la biblioteca
de rutinas comunes a todos los ejemplos.
El fichero Makefile necesario para compilación se presenta en el siguiente ejemplo, ya que es válido para ambos casos.
############## ## Makefile ## ############## #DEFS=-DDOS_HILOS -DDEBUG -DYIELD #DEFS=-DDEBUG INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libproc OBJ=$(OBJDIR)/getstats.o $(OBJDIR)/error.o $(OBJDIR)/semaforo.o \ $(OBJDIR)/mutex.o $(OBJDIR)/cond.o CC=gcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) #Definicion de dependencias all : filo .c.o: $(CC) $(CFLAGS) -c $< filo : filo.o $(CC) $(LINK) filo.o -o filo filo.o : filo.c
El problema de la cena de los filósofos que se presenta a continuación corresponde a la implementación del algoritmo empleando mutex y variables de condición. Este ejemplo es exactamente el mismo que el caso anterior, excepto que ahora hemos implementado el programa mediante hilos en vez de procesos. Para ello se ha utilizado la librería Pthreads del paquete de hilos de Chris Provenzano, aunque es muy posible que el programa funciona igualmente con cualquier otro paquete que siga el estándar POSIX.1c sobre hilos. El programa se ha realizado con dicho paquete instalado bajo el sistema operativo Linux 1.2.
La apariencia de la versión con procesos y esta versión multihilo es casi idéntica, de tal forma que cambian muy pocas cosas. El programa, al igual que la versión de procesos, permite que se le varíen una serie de parámetros para comprobar su funcionamiento. Se crea un hilo por cada filósofo mediante la sentencia pthread_create(). Mientras que el hilo padre se limita a esperar a que los filósofos finalicen. Los datos de interés (estado de los filósofos, variables de condición y mutex de acceso) son variables globales compartidas, para que puedan ser accedidos por todos los hilos filósofos. La sincronización del acceso al estado de los filósofos se ha conseguido empleando las variables de condición, relacionadas con la condición de poder comer (tenedores disponibles) y un mútex (equivalente a un semáforo binario) que garantiza el acceso exclusivo a los datos críticos. Tanto las variables condicionales como los mutex son estructuras implementadas por la librería Pthreads.
La sintaxis del programa es la siguiente :
filo [-?|-h] [num_filosofos [num_iteraciones [flag_aleatorio flag_eco [factor_comer [factor_pensar]]]]]] siendo :
El listado del programa fuente es el siguiente :
FILO.C /**************************************************************************** EJEMPLO DEL PROBLEMA DE LA CENA DE LOS FILOSOFOS (vers. hilos) Aplicacion: filo Version: 1.0h Fecha: 11/12/1996 Descripcion: Programa demostrativo del problema de los "filosofos-comiendo". Tenemos una serie de N filosofos con N tenedores. Cada filosofo ejecuta el ciclo pensar-comer. Pero para comer necesita dos tenedores el de su izquierda y el de su derecha. El problema es que los tenedores estan compartidos entre los filosofos adyacentes. Se crea un hilo por cada filosofo y se emplea la tecnica de monitores apoyada en variables de condicion y mutex para regular el acceso a los tenedores. El programa emplea las rutinas de la libreria Pthreads, que es compatible POSIX.1c Autor: Jose Maria Toribio Vicente E-Mail: jmtoribi@poboxes.com *****************************************************************************/ const char VERSION[]="filo 1.0h - Problema de la cena de los filosofos (vers. hilos)\n"; const char SINTAX[]= "Sintaxis: %s [-?|-h] [num_filosofos [num_iterac \ [flag_aleatorio [flag_echo [t_comer [t_pensar]]]]]]\n"; #include <pthread.h> #include <stdlib.h> #include "error.h" #include "getstats.h" /* Definicion de constantes */ #define N_FILOSOFOS 50 /* Numero maximo de filosofos */ #define DEFAULT_ITER 30 /* Numero de ciclos para un filosofo por defecto */ #define T_PENSAR 100 /* Factor de tiempo empleado en pensar por defecto */ #define T_COMER 100 /* Factor de tiempo empleado en comer por defecto */ /* Filosofo a la IZQUIERDA del filosofo i */ #define IZQ(t) ( (t==0) ? (nfilos-1) : ((t-1) % nfilos) ) /* Filosofo a la DERECHA del filosofo i */ #define DER(t) ((t+1) % nfilos) /* Estados de un filosofo */ #define DOS_TENEDORES_LIBRES 2 #define UN_TENEDOR_OCUPADO 1 #define DOS_TENEDORES_OCUPADOS 0 /* Estructura de los datos criticos del MONITOR */ typedef struct s_datos_t { int *EstadoFilos;/* Vector de Estado de los Filosofos */ pthread_cond_t *PoderComer; /* Vector de Condiciones de poder comer */ pthread_mutex_t sc; /* Mutex de acceso a la secc.critica */ } datos_t; /* Datos del MONITOR compartidos por los filosofos */ datos_t *Datos; /* Variables globales para los filosofos: solo-lectura */ int nfilos; /* Numero de filosofos. Var. global */ int niter; /* Numero de iteraciones para cada filosofo */ int aleatorio; /* Flag de aleatoriedad de los tiempos: 1 = aleatorio; 0 = No_aleatorio */ int eco; /* Flag de eco: 1 = eco si; 0 = eco no */ int factorTc; /* Factor de tiempo de comer */ int factorTp; /* Factor de tiempo de pensar */ /* Declaracion de procedimientos auxiliares */ void GetArgs(int argc, char *argv[], int *n, int *ni, int *faleat, int *feco, int *ftc, int *ftp); datos_t *CrearMemoria(int *shmem_id, int n); void DestruirMemoria(int *shmem_id, datos_t *d); void init_data (datos_t *d, int n); void destroy_data (datos_t *d, int n); void VerEstadoFilosofos(); /* Declaracion de Procedimientos sobre el Problema */ void *Filosofo(void *arg); void Comer (int i, int v); void Pensar(int i, int v); /* Declaracion de Procedimientos del MONITOR*/ void CogerTenedor(int i); void DejarTenedor(int i); /* PROGRAMA PRINCIPAL */ void main(int argc, char *argv[]) { pthread_t *fid; /* Vector de Identificadores de los Filosofos */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int i; /* Var. temporal */ /* Obtencion de argumentos */ GetArgs(argc, argv, &nfilos, &niter, &aleatorio, &eco, &factorTc, &factorTp); /* Crear memoria */ Datos = CrearMemoria(NULL, nfilos); /* Inicializacion de los datos del Monitor */ init_data(Datos, nfilos); /* Crear memoria para los identificadores de los filosofos */ if ( (fid = (pthread_t *) malloc(nfilos * sizeof(pthread_t))) == NULL ) ErrorFatal("No hay memoria para crear los identificadores de los filosofos"); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* Creacion de los filosofos */ for (i = 0; i<nfilos; i++) if (pthread_create(&fid[i], NULL, Filosofo, (void *)i) <0) ErrorFatal("Error en la creacion de un filosofo"); /* Esperamos la finalizacion de los filosofos */ for (i = 0; i<nfilos; i++) if (pthread_join(fid[i], NULL) <0) ErrorFatal("Error en la espera de un filosofo"); /* Obtener tiempos finales */ getestad(&estad[1]); /* Destruir los datos del monitor */ destroy_data(Datos, nfilos); /* Destruir memoria de los identificadores de los hilos */ free((void *)fid); /* Destruir memoria compartida */ DestruirMemoria(NULL, Datos); /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); exit(0); } void *Filosofo(void *arg) { int c; int i = (int)arg; for (c = 0; c<niter; c++) { Pensar(i, c); CogerTenedor(i); Comer(i, c); DejarTenedor(i); } } /* PROCEDIMIENTOS DEL MONITOR */ void CogerTenedor(int i) { pthread_mutex_lock(&Datos->sc); while (Datos->EstadoFilos[i] != DOS_TENEDORES_LIBRES) { # ifdef DEBUG printf("Filosofo %d se bloquea en la condicion\n", i); # endif pthread_cond_wait(&Datos->PoderComer[i], &Datos->sc); } # ifdef DEBUG printf("Filosofo %d COGE tenedores\n", i); # endif Datos->EstadoFilos[IZQ(i)]--; Datos->EstadoFilos[DER(i)]--; # ifdef DEBUG VerEstadoFilosofos(); # endif pthread_mutex_unlock(&Datos->sc); } void DejarTenedor(int i) { pthread_mutex_lock(&Datos->sc); # ifdef DEBUG printf("Filosofo %d DEJA tenedores\n", i); # endif Datos->EstadoFilos[IZQ(i)]++; Datos->EstadoFilos[DER(i)]++; if (Datos->EstadoFilos[IZQ(i)] == DOS_TENEDORES_LIBRES) { pthread_cond_signal(&Datos->PoderComer[IZQ(i)]); } if (Datos->EstadoFilos[DER(i)] == DOS_TENEDORES_LIBRES) pthread_cond_signal(&Datos->PoderComer[DER(i)]); # ifdef DEBUG VerEstadoFilosofos(); # endif pthread_mutex_unlock(&Datos->sc); } void Pensar(int i, int v) { long c; long tpensar; tpensar = ( aleatorio ? (random() % 100) : 100 ) * factorTp; if (eco) printf("Filosofo %d PENSANDO por %d vez ...\n", i, v); /* Bucle de simulacion */ for (c = 0; c<tpensar; c++); } void Comer(int i, int v) { long c; long tcomer; tcomer = ( aleatorio ? (random() % 100) : 100 ) * factorTc; if (eco) printf("Filosofo %d COMIENDO por %d vez ...\n", i, v); /* Bucle de simulacion */ for (c = 0; c<tcomer; c++); } void VerEstadoFilosofos() { int i; for (i = 0; i<nfilos; i++) printf("Ten[%d] = %d\n", i, Datos->EstadoFilos[i] ); } /* Obtener la linea de argumentos */ void GetArgs(int argc, char *argv[], int *n, int *niter, int *faleat, int *feco, int *ftc, int *ftp) { printf(VERSION); /* Comprobar si se solicita ayuda */ if (argc > 1) { if ( strcmp(argv[1],"-?") == 0 || strcmp(argv[1],"-h") == 0 ) { printf(SINTAX, argv[0]); exit(0); } } *n = N_FILOSOFOS; *niter = DEFAULT_ITER; *faleat = 1; *feco = 1; *ftc = T_COMER; *ftp = T_PENSAR; /* Obtenemos la lista de argumentos */ switch(argc) { case 7: *ftp = atoi(argv[6]); if (*ftp<1) *ftp = T_PENSAR; case 6: *ftc = atoi(argv[5]); if (*ftc<1) *ftc = T_COMER; case 5: *feco = ( (atoi(argv[4]) == 0) ? 0 : 1 ); case 4: *faleat = ( (atoi(argv[3]) == 0) ? 0 : 1 ); case 3: *niter = atoi(argv[2]); if (*niter<1) *niter = DEFAULT_ITER; case 2: *n = atoi(argv[1]); if (*n<2 || *n>N_FILOSOFOS) *n = N_FILOSOFOS; case 1: break; default: printf(SINTAX, argv[0]); printf("El numero de argumentos es incorrecto!\n"); exit(1); } } /* Proposito: Crear zona de memoria compartida por los filosofos. Entrada: n = Numero de filosofos. Salida: shmem_id[] = Vector de identificadores de memoria compartida. return = Puntero a la zona de memoria compartida. */ datos_t *CrearMemoria(int *shmem_id, int n) { datos_t *d; /* Crear memoria para los datos del monitor */ if ( (d = (datos_t *) malloc(sizeof(datos_t))) == (datos_t *)NULL ) ErrorFatal("No se pudo crear la memoria compartida"); if ( (d->EstadoFilos = (int *) malloc(n * sizeof(int))) == (int *) NULL ) ErrorFatal("No se pudo crear la memoria compartida para los Filosofos"); if ( (d->PoderComer = (pthread_cond_t *) malloc(n * sizeof(pthread_cond_t))) == (pthread_cond_t *) NULL ) ErrorFatal("No se pudo crear la memoria compartida para las Condiciones"); return(d); } /* Proposito: Destruir zona de memoria compartida por los filosofos. Entrada: shmem_id = Vector de identif. de memoria compartida. d = Puntero a la zona de memoria compartida. Salida: Ninguna */ void DestruirMemoria(int *shmem_id, datos_t *d) { free((void *)d->EstadoFilos); free((void *)d->PoderComer); free((void *)d); } /* Inicializacion de los datos del MONITOR */ void init_data(datos_t *d, int n) { int i; /* Inicializacion del mutex */ if ( pthread_mutex_init(&d->sc, NULL)<0 ) ErrorFatal("Error en la inicializacion del mutex"); /* Inicializacion del estado de los Filosofos y var. de condicion */ for (i = 0; i<n; i++) { d->EstadoFilos[i] = DOS_TENEDORES_LIBRES; if (pthread_cond_init(&d->PoderComer[i], NULL)<0) ErrorFatal("Error en la inicializacion de una condicion"); } } /* Destruccion de los datos del MONITOR */ void destroy_data(datos_t *d, int n) { int i; /* Destruccion de las variables de condicion y mutex */ for (i = 0; i<n; i++) pthread_cond_destroy(&d->PoderComer[i]); pthread_mutex_destroy(&d->sc); }
Este programa necesita, como ocurre en otros ejemplos,
los ficheros de cabecera GETSTATS.H, ERROR.H y
PARAM.H y los ficheros fuente GETSTATS.C
y ERROR.C, que se encuentran en la biblioteca
de rutinas comunes a todos los ejemplos.
El fichero Makefile necesario para compilación se presenta en el siguiente ejemplo, ya que es válido para ambos casos.
############## ## Makefile ## ############## #DEFS=-DDOS_HILOS -DDEBUG -DYIELD #DEFS=-DDEBUG INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libpthread OBJ=$(OBJDIR)/getstats.o $(OBJDIR)/error.o CC=pgcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) #Definicion de dependencias all : filo .c.o: $(CC) $(CFLAGS) -c $< filo : filo.o $(CC) $(LINK) filo.o -o filo filo.o : filo.c
Las dos implementaciones (procesos e hilos) del problema
de la cena de los filósofos son prácticamente idénticas,
como se habrá observado en los listados del código
fuente, no solo conceptualmente sino a nivel de programación.
Como referencia para discutir las ventajas e inconvenientes
de las dos implementaciones : multihilo y procesos, se indican
los siguientes tiempos de ejecución obtenidos como
muestra en un sistema formado por una CPU Intel 486-66Mhz - 9Mb
RAM - Linux 1.2.13, y con carga mínima en el sistema. En
el sistema se ejecutaron las dos versiones, repitiendo la prueba
en 5 ocasiones para cada uno de los programas. Todos los tiempos
están expresados en milisegundos.
El cuadro comparativo se realizó con los siguientes parámetros :
MUESTRAS | ||||||
Hilos T. Usuario | ||||||
Hilos T. Kernel | ||||||
Hilos T. Real | ||||||
Hilos Faltas Página | ||||||
Proc.T. Usuario | ||||||
Proc.T. Kernel | ||||||
Proc.T. Real | ||||||
Proc. Faltas Página |
En el cuadro se observa que ambas versiones producen un número
de faltas de página idéntico. Sin embargo, se observa
una gran diferencia en el tiempo de programa en modo usuario y
en modo sistema entre ambas versiones, que entre otras cosas puede
deberse a la utilización de memoria compartida, gestionada
por el kernel, en la versión de procesos. La versión
multihilo es bastante más rápida en ejecución
que la versión de procesos.
Inconvenientes de la versión de procesos :
Ventajas de la versión de procesos :
Inconvenientes de la versión multihilo :
Ventajas de la versión multihilo :