7.3. EL MÉTODO DE NEWTON EN PARALELO.

  1. Introducción al problema.
  2. Algoritmo de Newton con procesos.
  3. Algoritmo de Newton con hilos.
  4. Comparación de las dos implementaciones.

Introducción al problema.

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.

Algoritmo de Newton con procesos.

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



Algoritmo de Newton con hilos.

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


Comparación de las dos implementaciones.

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
1
2
3
4
5
Media
Hilos T. Tot Proceso
11388
10915
8964
11902
12344
11102,6
Hilos T. Medio Proc.
569
545
448
595
617
554,8
Hilos T. Ejecución
163872
103201
147625
158340
164951
147597,8
Hilos T. Usuario*
19
15
10
11
14
13,8
Hilos T. Kernel*
13
17
18
20
18
17,2
Hilos T. Respuesta*
33
33
29
31
32
31,6
Proc.T. Tot Proceso
30513
35883
90708
38792
34479
46075
Proc.T. Medio Proc.
1525
1794
4535
1939
1723
2303,2
Proc.T. Ejecución
276024
356207
390389
291654
275228
317900,4
Proc.T. Usuario*
9
11
11
17
15
12,6
Proc.T. Kernel*
31
37
30
25
26
29,8
Proc.T. Respuesta*
40
49
42
43
41
43

Figura 7-3 Tiempos de las dos implemantaciones para el caso 1.

* = 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
1
2
3
4
5
Media
Hilos T. Tot Proceso
7127
8189
7040
6319
5900
6915
Hilos T. Medio Proc.
356
409
352
315
295
345,4
Hilos T. Ejecución
147019
175370
162420
140073
139467
152869,8
Hilos T. Usuario*
14
15
13
11
12
13
Hilos T. Kernel*
13
19
18
18
15
16,6
Hilos T. Respuesta*
28
34
32
29
28
30,2
Proc.T. Tot Proceso
24494
22317
25106
25351
22741
24001,8
Proc.T. Medio Proc.
1224
1115
1255
1267
1137
1199,6
Proc.T. Ejecución
259223
347189
350309
256024
266737
295896,4
Proc.T. Usuario*
11
9
13
11
11
11
Proc.T. Kernel*
26
39
36
26
27
30,8
Proc.T. Respuesta*
39
48
49
37
39
42,4

Figura 7-4 Tiempos de las dos implementaciones para el caso 2.

* = 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.