El método de Newton/Raphson es un algoritmo muy conocido para la búsqueda de raíces de una función. Es una versión límite del método de la secante. Lo que se pretende es demostrar que la programación concurrente mediante procesos o hilos también es una buena solución para desarrollar algoritmos paralelos.
El planteamiento del problema es el siguiente :
Dada una función f(x) y una aproximación x0 a una de sus raíces Z, el método calcula la sucesión xn+1 = xn - f(xn)/f'(xn) para n = 0,1,2,..., hasta que abs(xn+1 - xn)<C, donde C es la precisión deseada de la aproximación a la raíz.
La siguiente aproximación xn+1 es la intersección con el eje X de la tangente a la función f(x) en el punto xn.
El problema del método se presenta cuando se encuentra un punto xn tal que su derivada f'(xn) = 0. En este caso el método se detiene sin éxito.
La popularidad de este método se debe a su rápida velocidad de convergencia, cuando x0 está cerca de Z. Esto se debe a que es una variante de los métodos iterativos de punto fijo, y todos ellos convergen de forma muy rápida.
El método de Newton tiene en común con el método de la "regula falsi" y el método de la secante, la simplificación del problema inicial del cálculo de Z, mediante la sustitución de la función f(x) por una recta, tomando como aproximación a la raíz Z de la función, la raíz de la recta.
Para asegurar la convergencia del método se necesitan buenas aproximaciones iniciales. Aunque esto no es tan necesario en la versión paralela del algoritmo como se verá más adelante. Las condiciones que aseguran la convergencia son :
El algoritmo del método de Newton en su versión
secuencial más simple es el siguiente :
- Sea [a,b] el intervalo de búsqueda.
- Desactivar Encontrado
- xant = (a + b)/2
- i = 0
- Mientras (i < MaxIteraciones y no Encontrado) hacer
- i = i + 1
- xact = xant - f(xant)/f'(xant)
- Si (abs(xact - xant) < C) entonces
- Raiz = xact
- Activar Encontrado
- xant = xact
- Fin_mientras
La versión paralela del algoritmo es muy similar,
y está pensada sobre un modelo MIMD (Multiple Instruction
Multiple Data), es decir un modelo de múltiples procesos
asíncronos. En esta versión lo que se hace es tomar
el intervalo (a,b) que contiene a la raíz Z, y dividirlo
en N+1 subintervalos de igual tamaño, siendo N el número
de procesos concurrentes trabajando en la búsqueda de la
solución, y con N>1. Los puntos medios de división
de los subintervalos se toman como aproximación inicial
la raíz para cada uno de los N procesos concurrentes. Cada
proceso aplica el método de Newton empezando en uno de
los puntos de la división anterior. Si alguno de los procesos
converge a la raíz, se almacena la solución en una
variable compartida y se indica la finalización al resto.
Si un proceso no converge y supera el número máximo
de iteraciones, finaliza su ejecución.
El algoritmo en su versión paralela se presenta
a continuación :
Procedimiento Newton(f, f', a, b, C, MaxIteraciones)
- Desactivar Encontrado
- S = (b-a)/(N+1)
- Para k=1 hata N hacer
- Crear el proceso k que ejecuta BuscarRaiz
- Fin_Para
Procedimiento BuscarRaiz(k, S, f, f', a, b, C, MaxIteraciones)
- xant = a + kS
- i = 0
- Mientras (i < MaxIteraciones y no Encontrado) hacer
- i = i + 1
- xact = xant - f(xant)/f'(xant)
- Si (abs(xact - xant) < C) entonces
- Raiz = xact
- Activar Encontrado
- xant = xact
- Fin_mientras
Las variables Encontrado y Raiz son variables globales,
y su acceso debe estar protegido frente a accesos concurrentes.
A continuación se presenta una versión del algoritmo de Newton/Raphson en su implementación mediante procesos concurrentes.
El objetivo es demostrar como varios procesos concurrentes pueden trabajar de forma independiente en la resolución de un problema dividido en subproblemas. Es claramente un ejemplo de la división del trabajo. Es pues una demostración de como se puede implementar un algoritmo paralelo para máquinas MIMD en un entorno multiproceso.
La implementación que se presenta se ha realizado
para el sistema operativo Linux 1.2, y se han empleado procesos,
memoria compartida, y primitivas de sincronización :
mútex. Los mútex se han simulado mediante semáforos,
al igual que en los ejemplos presentados anteriormente, con objeto
de que el código fuente tenga el mayor parecido posible
con la versión de hilos que se presenta posteriormente,
y de esta forma poder mostrar las similitudes y diferencias entre
la programación multiproceso y la programación multihilo.
La comunicación entre los procesos se realiza mediante
memoria compartida.
El proceso padre principal obtiene los argumentos de la línea de comandos, crea la zona de memoria compartida e inicializa las variables globales y el mútex de acceso a esta zona compartida. Después se divide el intervalo inicial en tantos subintervalos como procesos se vayan a ejecutar, y se procede a la creación de los procesos hijos mediante la primitiva fork(), que ejecutarán el algoritmo de Newton en la porción de intervalo que se les haya asignado. A continuación el proceso padre espera a que finalicen los procesos hijos, y presenta el resultado obtenido, junto con una serie de datos estadísticos que dan una idea del tiempo empleado en la resolución del problema, el tiempo medio empleado por cada proceso, y el número de iteraciones empleadas por el proceso que alcanzó la raíz. Finalmente destruye la memoria compartida y el mútex creado y finaliza.
Cada proceso hijo ejecuta el algoritmo de Newton, y cuando uno de ellos encuentra la solución, emplea el mútex para acceder a la memoria compartida y almacenar el resultado allí, junto con el tiempo empleado en la resolución.
Indicar que la función de estudio f(x), su derivada f'(x) y otros parámetros como el intervalo y el número de procesos se definen en el fichero FUNCION.H
La sintaxis del programa es la siguiente :
newton [-?|-h] [num_tareas [precision [num_iter [puntoB puntoA]]]] siendo :
El programa en su versión de procesos es el siguiente :
NEWTON.C :
/**************************************************************************** EJEMPLO DE BUSQUEDA DE RAICES MEDIANTE EL METODO DE NEWTON-RAPHSON Aplicacion: newton Version: 1.0p Fecha: 2/12/1996 Descripcion: Programa demostrativo de la busqueda de raices de una funcion mediante el metodo de Newton-Raphson. Implementacion empleando procesos. Autor: Jose Maria Toribio Vicente Mail: jmtoribi@poboxes.com *****************************************************************************/ #define VERSION "newton 1.0p - Busqueda de raices (vers. procesos)\n" #define SINTAX "Sintaxis: %s [-?|-h] [num_tareas [precision [num_iter [puntoB puntoA]]]]\n" /* #define DEBUG */ /* Define para compilar en modo DEBUG */ /* #define EXEC_TIME */ /* Define para compilar con tiempo de ejecucion */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <sys/types.h> #include <sys/wait.h> #include "mutex.h" #include "getstats.h" #include "tiempo.h" /* Definicion de la Funcion sobre la que deseamos obtener las raices */ #include "funcion.h" /* Definicion de Identificadores de Claves de Recursos del Sistema */ #define MUTEX1_KEY ((key_t)188761L) #define SHMEM_KEY ((key_t)188762L) /* Procedimiento de Calculo */ void *BuscarRaiz(void *); /* Estructura de datos empleada para comunicacion entre el programa principal y las tareas de servicio */ typedef struct s_datos_t { mutex_t lock; /* Mutex de acceso a los datos globales */ int Encontrado; /* Flag de finalizacion */ long ContadorServicios; /* Total de servicios realizados */ double Raiz; /* Raiz de la funcion */ struct timeval TotalServicio;/* Tiempo Total de Servicio */ } datos_t; /* Datos globales */ datos_t *Datos; /* Datos globales - Solo lectura */ #define MAX_TAREAS 30 /* Numero maximo de tareas permitido */ #define TAREAS 4 /* Numero de tareas por defecto */ double a = PUNTO_A; /* Punto a del intervalo [a,b] */ double s; /* Tamano de los subintervalos */ double Precision = PRECISION; /* Precision que se desea en la solucion */ long NumIteraciones = ITERACIONES; /* Numero de iteraciones maximo */ /* PROGRAMA PRINCIPAL */ int main(int argc, char **argv) { double b = PUNTO_B; /* Punto b del intervalo [a,b] */ int TotalTareas = TAREAS; /* Numero de tareas */ pid_t pid_hijo[MAX_TAREAS]; /* PID del proceso hijo */ struct timeval ts; /* Tiempo Medio de Servicio */ estad_t estad[2]; /* Datos estadisticos de la aplicacion */ int i; /* Var. contador temporal */ int shmem_id; /* Identif. para zona de memoria compartida */ # ifdef EXEC_TIME struct timeval t1,tp; /* Tiempos de programa */ /* Obtener el tiempo actual */ gettimeofday(&t1, NULL); # endif 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); } } /* Obtenemos la lista de argumentos */ switch(argc) { case 6: a = atof(argv[5]); case 5: b = atof(argv[4]); if ( a >= b) { printf("El intervalo [%d, %d] es incorrecto\n", a, b); exit(1); } case 4: NumIteraciones = atol(argv[3]); if ( NumIteraciones <= 0 ) NumIteraciones = ITERACIONES; case 3: Precision = atof(argv[2]); if ( Precision <= 0.0 || Precision >1.0) Precision = 0.01; case 2: TotalTareas = atoi(argv[1]); if (TotalTareas <= 0 || TotalTareas >= MAX_TAREAS) TotalTareas = TAREAS; case 1: break; default: printf(SINTAX, argv[0]); printf("El numero de argumentos es incorrecto\n"); exit(0); break; } /* Crear memoria compartida */ if ((shmem_id = shmget(SHMEM_KEY, sizeof(datos_t), 0666 | IPC_CREAT)) <0) ErrorFatal("No se pudo crear la memoria compartida"); /* Establecer el acceso a la memoria compartida */ if ((Datos = (datos_t *) shmat(shmem_id, (char *)0, 0)) == (datos_t *) -1) ErrorFatal("No se pudo enlazar con la memoria compartida"); /* Inicializacion de los datos globales */ mutex_init(&Datos->lock, MUTEX1_KEY); Datos->ContadorServicios = 0; Datos->Encontrado = 0; Datos->Raiz = 0.0; Datos->TotalServicio.tv_sec = 0; Datos->TotalServicio.tv_usec = 0; /* Presentacion de la informacion de trabajo */ printf("Realizando el calculo con los siguientes valores:\n"); printf("Intervalo = [%lf, %lf]\n", a, b); printf("No.Iteraciones = %d\n", NumIteraciones); printf("Precision = %lf\n", Precision); printf("Tareas = %d\n", TotalTareas); printf("Calculando ....\n"); /* Dividir el intervalo original en subintervalos de igual tamano */ s = (b-a)/(TotalTareas+1); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* Crear las Tareas */ for (i = 1; i<=TotalTareas; i++) { switch( (pid_hijo[i] = fork())) { /* No se pudo crar hijo */ case -1: Error("No se pudo crear hijo para procesar la tarea"); break; /* Proceso HIJO */ case 0: BuscarRaiz( (void *)i ); exit(0); break; /* Proceso PADRE */ default: break; } } /* Esperar la finalizacion de las tareas */ for (i = 1; i<=TotalTareas; i++) { waitpid(pid_hijo[i], NULL, 0); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Destruccion de los recursos */ mutex_destroy(&Datos->lock); /* Imprime los tiempos de servicio Total y Medio */ DivTimeInt(&Datos->TotalServicio, Datos->ContadorServicios, &ts); printf("\n DATOS ESTADISTICOS DEL PROCESO\n"); printf( "--------------------------------\n"); if (Datos->Encontrado) printf("Raiz = %.20f\n", Datos->Raiz); else printf("No se encontro una aproximacion suficientemente buena\n"); printf("Total de peticiones servidas = %d\n", Datos->ContadorServicios); printf("Tiempo Total de servicio = %d sg %d mms\n", Datos->TotalServicio.tv_sec, Datos->TotalServicio.tv_usec); printf("Tiempo Medio de servicio = %d sg %d mms\n", ts.tv_sec, ts.tv_usec); /* Destruir memoria compartida */ if ( shmdt((char *)Datos) <0 ) ErrorFatal("No se pudo desenlazar la memoria compartida"); if ( shmctl(shmem_id, IPC_RMID, (struct shmid_ds *)0) <0 ) ErrorFatal("No se pudo liberar la memoria compartida"); # ifdef EXEC_TIME /* Obtener el tiempo actual y el tiempo de ejecucion del programa */ gettimeofday(&tp, NULL); DiffTime(&t1, &tp, &tp); printf("Tiempo de ejecucion del programa = %d sg %d mms\n", tp.tv_sec, tp.tv_usec); # endif /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); /* Finaliza el programa */ return(0); } /* Proposito: Buscar una raiz en un subintervalo. Entrada: arg = Identificador del Socket del Cliente. Salida: Ninguna */ void *BuscarRaiz(void *arg) { /* a, s, NumIteraciones, Precision -> Var. globales solo lectura */ /* Raiz -> Var. global escritura */ double x, xn; /* Aproximaciones anterior y nueva a la raiz */ long i = 0; /* Contador de iteraciones */ int k = (int)arg; /* Numero del subintervalo */ double t; /* Var. temporal */ long c; /* Var.temporal contador */ struct timeval t1,t2; /* Tiempos Inicial y Final del servicio */ struct timeval ts; /* Tiempo de servicio */ /* Obtener el tiempo actual */ gettimeofday(&t1, NULL); /* Calcula la aproximacion inicial a la raiz en el subintervalo */ x = a + k*s; # ifdef DEBUG printf("Calculo: Hijo [%d]: tarea %d\n", getpid(), k); printf("Calculo: Hijo [%d]: soluc.inicial = %lf\n", getpid(), x); # endif /* Bucle de busqueda de la raiz */ while ( i < NumIteraciones ) { mutex_lock(&Datos->lock); if (Datos->Encontrado) { mutex_unlock(&Datos->lock); break; } mutex_unlock(&Datos->lock); i = i + 1; t = df(x); if (t == 0.0) { printf("Error: Hijo [%d]: df(%lf) = 0 => division por 0\n", getpid(), x); break; } xn = x - f(x)/t; # ifdef DEBUG printf("x=%lf f(x)=%lf df(x)=%lf fabs(xn-x)=%lf\n", x, f(x), df(x), fabs(xn-x)); # endif /* Mirar si la aproximacio a la raiz es suficiente */ if ( fabs(xn-x) < Precision ) { mutex_lock(&Datos->lock); Datos->Raiz = xn; Datos->Encontrado = 1; mutex_unlock(&Datos->lock); # ifdef DEBUG printf("Calculo: Hijo [%d]: Solucion encontrada = %lf en %d iteraciones\n", getpid(), xn, i); # endif break; } x = xn; }/* End-while */ /* Obtener el tiempo actual y el tiempo de servicio */ gettimeofday(&t2, NULL); DiffTime(&t1, &t2, &ts); /* Actualizar el Contador de Servicios */ mutex_lock(&Datos->lock); c = ++(Datos->ContadorServicios); AddTime(&Datos->TotalServicio, &ts, &Datos->TotalServicio); mutex_unlock(&Datos->lock); # ifdef DEBUG printf("Calculo: Hijo [%d]: Tiempo de servicio = %d sg %d mms\n", getpid(), ts.tv_sec, ts.tv_usec); printf("Calculo: Hijo [%d]: Total de peticiones = %d\n", getpid(), c); # endif /* Finalizar la tarea */ return ( (void *)0 ); }
FUNCION.H : Fichero de definición de la función de estudio y datos asociados.
#ifndef FUNCION_H #define FUNCION_H #ifndef PI #define PI 3.141592653589793116 #endif /* Definicion de la Funcion sobre la que deseamos obtener las raices: f(x) y su derivada df(x) */ #define f(x) ( sin(x)-x+2 ) #define df(x) ( cos(x)-1 ) /* Definicion del Intervalo de estudio, precision y no. max. de iteraciones */ #define PUNTO_A -3.0 /* Punto A del intervalo [A,B] */ #define PUNTO_B 3.0 /* Punto B del intervalo [A,B] */ #define PRECISION 0.001 /* Precision de calculo por defecto */ #define ITERACIONES 100000 /* Numero de iteraciones por defecto */ #endif /* FUNCION_H */
Además este programa necesita de los ficheros
de cabecera ERROR.H, PARAM.H, TIEMPO.H, SEMAFORO.H
y MUTEX.H, junto con los ficheros fuente ERROR.C,
TIEMPO.C, SEMAFORO.C y MUTEX.C empleados en
ejemplos anteriores, y que pertenecen a la biblioteca de rutinas
comunes a los ejemplos.
El fichero Makefile necesario para compilación es el siguiente :
############## ## Makefile ## ############## #DEFS=-DDEBUG -DEXEC_TIME DEFS=-DEXEC_TIME INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libproc OBJ=$(OBJDIR)/tiempo.o $(OBJDIR)/error.o $(OBJDIR)/semaforo.o \ $(OBJDIR)/mutex.o $(OBJDIR)/getstats.o CC=gcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) -lm #Definicion de dependencias all : newton .c.o: $(CC) $(CFLAGS) -c $< newton : newton.o $(CC) $(LINK) newton.o -o newton newton.o : newton.c funcion.h
A continuación se presenta una versión del algoritmo de Newton/Raphson en su implementación mediante hilos.
Este ejemplo es prácticamente 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, como en los ejemplo anteriores, aunque es muy posible que el programa funciona igualmente con cualquier otro paquete que siga el estándar POSIX.1c sobre hilos, ya que solo se han empleado funciones del estándar. El programa ha sido compilado y ejecutado con dicho paquete instalado bajo el sistema operativo Linux 1.2 y 2.0.
La apariencia de ambas versiones es muy similar.
La única diferencia la encontramos en la creación
de procesos. Aquí lo que se crean son hilos mediante la
llamada a pthread_create(), por lo
demás el funcionamiento es idéntico al descrito
en la versión de hilos. La sintaxis del programa es la
misma que en la versión de procesos.
El listado del programa en la versión de hilos es el siguiente :
NEWTON.C :
/**************************************************************************** EJEMPLO DE BUSQUEDA DE RAICES MEDIANTE EL METODO DE NEWTON-RAPHSON Aplicacion: newton Version: 1.0h Fecha: 2/12/1996 Descripcion: Programa demostrativo de la busqueda de raices de una funcion mediante el metodo de Newton-Raphson. El programa emplea las rutinas de la libreria Pthreads, que es compatible POSIX.1c Autor: Jose Maria Toribio Vicente Mail: jmtoribi@poboxes.com *****************************************************************************/ #define VERSION "newton 1.0h - Busqueda de raices (vers. hilos)\n" #define SINTAX "Sintaxis: %s [-?|-h] [num_tareas [precision [num_iter [puntoB puntoA]]]]\n" /* #define DEBUG */ /* Define para compilar en modo DEBUG */ /* #define EXEC_TIME */ /* Define para compilar con tiempo de ejecucion */ /* #define YIELD */ /* Define para compilar con pthread_yield() No-POSIX */ #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include "getstats.h" #include "tiempo.h" /* Definicion de la Funcion sobre la que deseamos obtener las raices */ #include "funcion.h" /* Procedimiento de Calculo */ void *BuscarRaiz(void *); /* Estructura de datos empleada para comunicacion entre el programa principal y las tareas de servicio */ typedef struct s_datos_t { pthread_mutex_t lock; /* Mutex de acceso a los datos globales */ int Encontrado; /* Flag de finalizacion */ long ContadorServicios;/* Total de servicios realizados */ double Raiz; /* Raiz de la funcion */ struct timeval TotalServicio;/* Tiempo Total de Servicio */ } datos_t; /* Datos globales */ datos_t Datos = { PTHREAD_MUTEX_INITIALIZER, 0, 0, 0.0 }; /* Datos globales - Solo lectura */ #define MAX_TAREAS 30 /* Numero maximo de tareas permitido */ #define TAREAS 4 /* Numero de tareas por defecto */ double a = PUNTO_A; /* Punto a del intervalo [a,b] */ double s; /* Tamano de los subintervalos */ double Precision = PRECISION; /* Precision que se desea en la solucion */ long NumIteraciones = ITERACIONES; /* Numero de iteraciones maximo */ /* PROGRAMA PRINCIPAL */ int main(int argc, char **argv) { double b = PUNTO_B; /* Punto b del intervalo [a,b] */ int TotalTareas = TAREAS; /* Numero de tareas */ pthread_t id_hilo[MAX_TAREAS]; /* PID del proceso hijo */ struct timeval ts; /* Tiempo Medio de Servicio */ estad_t estad[2]; /* Datos estadisticos */ int i; /* Var. contador temporal */ # ifdef EXEC_TIME struct timeval t1,tp; /* Tiempos de programa */ /* Obtener el tiempo actual */ gettimeofday(&t1, NULL); # endif 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); } } /* Obtenemos la lista de argumentos */ switch(argc) { case 6: a = atof(argv[5]); case 5: b = atof(argv[4]); if ( a >= b) { printf("El intervalo [%d, %d] es incorrecto\n", a, b); exit(1); } case 4: NumIteraciones = atol(argv[3]); if ( NumIteraciones <= 0 ) NumIteraciones = ITERACIONES; case 3: Precision = atof(argv[2]); if ( Precision <= 0.0 || Precision >1.0) Precision = 0.01; case 2: TotalTareas = atoi(argv[1]); if (TotalTareas <= 0 || TotalTareas >= MAX_TAREAS) TotalTareas = TAREAS; case 1: break; default: printf(SINTAX, argv[0]); printf("El numero de argumentos es incorrecto\n"); exit(0); break; } /* Inicializacion de los datos globales */ pthread_mutex_init(&Datos.lock, NULL); Datos.ContadorServicios = 0; Datos.Encontrado = 0; Datos.Raiz = 0.0; Datos.TotalServicio.tv_sec = 0; Datos.TotalServicio.tv_usec = 0; /* Presentacion de la informacion de trabajo */ printf("Realizando el calculo con los siguientes valores:\n"); printf("Intervalo = [%lf, %lf]\n", a, b); printf("No.Iteraciones = %d\n", NumIteraciones); printf("Precision = %lf\n", Precision); printf("Tareas = %d\n", TotalTareas); printf("Calculando ....\n"); /* Dividir el intervalo original en subintervalos de igual tamano */ s = (b-a)/(TotalTareas+1); /* Obtener los tiempos iniciales */ getestad(&estad[0]); /* Crear las Tareas */ for (i = 1; i<=TotalTareas; i++) { if (pthread_create(&id_hilo[i], NULL, BuscarRaiz, (void *)i) != 0) Error("No se pudo crear hilo para procesar la tarea"); } /* Esperar la finalizacion de las tareas */ for (i = 1; i<=TotalTareas; i++) { pthread_join(id_hilo[i], NULL); } /* Obtener tiempos finales */ getestad(&estad[1]); /* Destruccion de los recursos */ pthread_mutex_destroy(&Datos.lock); /* Imprime los tiempos de servicio Total y Medio */ DivTimeInt(&Datos.TotalServicio, Datos.ContadorServicios, &ts); printf("\n DATOS ESTADISTICOS DEL PROCESO\n"); printf( "--------------------------------\n"); if (Datos.Encontrado) printf("Raiz = %.20f\n", Datos.Raiz); else printf("No se encontro una aproximacion suficientemente buena\n"); printf("Total de peticiones servidas = %d\n", Datos.ContadorServicios); printf("Tiempo Total de servicio = %d sg %d mms\n", Datos.TotalServicio.tv_sec, Datos.TotalServicio.tv_usec); printf("Tiempo Medio de servicio = %d sg %d mms\n", ts.tv_sec, ts.tv_usec); # ifdef EXEC_TIME /* Obtener el tiempo actual y el tiempo de ejecucion del programa */ gettimeofday(&tp, NULL); DiffTime(&t1, &tp, &tp); printf("Tiempo de ejecucion del programa = %d sg %d mms\n", tp.tv_sec, tp.tv_usec); # endif /* Imprimir los tiempos */ printestad(stderr, &estad[0], &estad[1]); /* Finaliza el programa */ return(0); } /* Proposito: Buscar una raiz en un subintervalo. Entrada: arg = Identificador del Socket del Cliente. Salida: Ninguna */ void *BuscarRaiz(void *arg) { /* a, s, NumIteraciones, Precision -> Var. globales solo lectura */ /* Datos -> Var. global escritura */ double x, xn; /* Aproximaciones anterior y nueva a la raiz */ long i = 0; /* Contador de iteraciones */ int k = (int)arg; /* Numero del subintervalo */ long c; /* Var.temporal contador */ struct timeval t1,t2; /* Tiempos Inicial y Final del servicio */ struct timeval ts; /* Tiempo de servicio */ /* Obtener el tiempo actual */ gettimeofday(&t1, NULL); /* Calcula la aproximacion inicial a la raiz en el subintervalo */ x = a + k*s; # ifdef DEBUG printf("Calculo: Hilo [%d]: tarea %d\n", pthread_self(), k); printf("Calculo: Hilo [%d]: soluc.inicial = %lf\n", pthread_self(), x); # endif /* Bucle de busqueda de la raiz */ while ( i < NumIteraciones ) { pthread_mutex_lock(&Datos.lock); if (Datos.Encontrado) { pthread_mutex_unlock(&Datos.lock); break; } pthread_mutex_unlock(&Datos.lock); i = i + 1; xn = x - f(x)/df(x); # ifdef DEBUG printf("x=%lf f(x)=%lf df(x)=%lf fabs(xn-x)=%lf\n", x, f(x), df(x), fabs(xn-x)); # endif /* Mirar si la aproximacio a la raiz es suficiente */ if ( fabs(xn-x) < Precision ) { pthread_mutex_lock(&Datos.lock); Datos.Raiz = xn; Datos.Encontrado = 1; pthread_mutex_unlock(&Datos.lock); # ifdef DEBUG printf("Calculo: Hilo [%d]: Solucion encontrada = %lf en %d iteraciones\n", pthread_self(), xn, i); # endif break; } x = xn; }/* End-while */ /* Obtener el tiempo actual y el tiempo de servicio */ gettimeofday(&t2, NULL); DiffTime(&t1, &t2, &ts); /* Actualizar el Contador de Servicios */ pthread_mutex_lock(&Datos.lock); c = ++(Datos.ContadorServicios); AddTime(&Datos.TotalServicio, &ts, &Datos.TotalServicio); pthread_mutex_unlock(&Datos.lock); # ifdef DEBUG printf("Calculo: Hilo [%d]: Tiempo de servicio = %d sg %d mms\n", pthread_self(), ts.tv_sec, ts.tv_usec); printf("Calculo: Hilo [%d]: Total de peticiones = %d\n", pthread_self(), c); # endif /* Finalizar la tarea */ pthread_exit(NULL); return ( (void *)0 ); }
Además este programa también necesita
el fichero FUNCION.H y los ficheros
de la biblioteca de rutinas comunes a los ejemplos, empleados
en la versión de procesos.
El fichero Makefile necesario para compilación es el siguiente :
############## ## Makefile ## ############## #DEFS=-DDEBUG -DEXEC_TIME DEFS=-DEXEC_TIME INSDIR=../../.. INCDIR=$(INSDIR)/include OBJDIR=$(INSDIR)/libpthread OBJ=$(OBJDIR)/tiempo.o $(OBJDIR)/error.o $(OBJDIR)/getstats.o CC=pgcc CFLAGS=$(DEFS) -I$(INCDIR) LINK=$(CFLAGS) $(OBJ) #Definicion de dependencias all : newton .c.o: $(CC) $(CFLAGS) -c $< newton : newton.o $(CC) $(LINK) newton.o -o newton newton.o : newton.c funcion.h
Las dos implementaciones, como se habrá observado,
son prácticamente idénticas, no solo conceptualmente
sino a nivel de programación, ya que se dispone de las
rutinas de mútex (en la versión de procesos) que
enmascaran las llamadas a rutinas de semáforos, al igual
que sucedía en los ejemplos anteriores.
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 del programa para hallar
las raíces de varias funciones, repitiendo la prueba en
5 ocasiones para cada una de las funciones. Los tiempos están
dados en microsegundos.
1) f(x) = sin(x).cos(x) - x
f'(x) = -2 sin2(x) Procesos concurrentes: 20
Raíz : x = 0 Intervalo : [-1, 3] Precisión :
10-19
MUESTRAS | ||||||
Hilos T. Tot Proceso | ||||||
Hilos T. Medio Proc. | ||||||
Hilos T. Ejecución | ||||||
Hilos T. Usuario* | ||||||
Hilos T. Kernel* | ||||||
Hilos T. Respuesta* | ||||||
Proc.T. Tot Proceso | ||||||
Proc.T. Medio Proc. | ||||||
Proc.T. Ejecución | ||||||
Proc.T. Usuario* | ||||||
Proc.T. Kernel* | ||||||
Proc.T. Respuesta* |
* = Tiempos indicados por la utilidad time
de Linux, que mide los tiempos de ejecución en modo usuario,
modo kernel y tiempo de respuesta que ha realizado el programa.
Estos tiempos están en segundos.
2) f(x) = tan(x)
f'(x) = tan2(x)+1 Procesos concurrentes: 20
Raíz : x = PI Intervalo : [1.5, 3.5] Precisión :
10-19
MUESTRAS | ||||||
Hilos T. Tot Proceso | ||||||
Hilos T. Medio Proc. | ||||||
Hilos T. Ejecución | ||||||
Hilos T. Usuario* | ||||||
Hilos T. Kernel* | ||||||
Hilos T. Respuesta* | ||||||
Proc.T. Tot Proceso | ||||||
Proc.T. Medio Proc. | ||||||
Proc.T. Ejecución | ||||||
Proc.T. Usuario* | ||||||
Proc.T. Kernel* | ||||||
Proc.T. Respuesta* |
* = Tiempos indicados por la utilidad time
de Linux, que mide los tiempos de ejecución en modo usuario,
modo kernel y tiempo de respuesta que ha realizado el programa.
Inconvenientes de la versión de procesos :
Ventajas de la versión de procesos :
Inconvenientes de la versión multihilo :
Como inconvenientes de la versión multihilo se pueden destacar los siguientes :
Ventajas de la versión multihilo :
Por último, el programa emplea menos recursos del kernel, al no emplear memoria compartida a nivel kernel.