Un Ejemplo Sencillo: Cálculo de los Primos

Cálculo de los Números Primos en Secuencial

Para saber si un número $num es primo basta ver si es divisible por uno de los primos @primes anteriores a él:

hp@nereida:~/Lperl/src/threads$ cat -n primes-without-threads.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3
 4  my @primes = (2);
 5  my $n = (shift || 10);
 6
 7  NEW_NUMBER:
 8  for my $num (3 .. $n) {
 9          foreach (@primes) { next NEW_NUMBER if $num % $_ == 0 }
10          print "Found prime $num\n";
11          push @primes, $num;
12  }

Ejercicio 12.4.1   El bucle de la línea 9 puede hacerse mas corto. ¿Podrías decir como?

Cálculo de los Números Primos Usando Hilos

El cálculo anterior puede ser realizado de manera concurrente. La idea es tener un hilo por cada nuevo primo. Cada hilo se ''encarga'' de la división por un cierto número primo ($cur_prime) con el que está asociado.

Los hilos se estructuran en una topología de pipeline o canal. El hilo tiene dos canales de comunicación $upstream y $downstream que le comunican con - usando una terminología jerárquica - el ''hilo padre'' y el ''hilo hijo'' (referenciado por la variable $kid). Viendo el flujo de comunicaciones como una corriente denominaremos a los canales ''río arriba' ($upstream) y ''rio abajo'' ($downstream).

16  sub check_num {
17          my ($upstream, $cur_prime) = @_;
18          my $kid = undef;
19          my $downstream = new Thread::Queue;
20          while (my $num = $upstream->dequeue) {
21                  next unless $num % $cur_prime;
22                  if ($kid) {
23                          $downstream->enqueue($num);
24                  } else {
25                          print "Found prime $num\n";
26                          $kid = new threads(\&check_num, $downstream, $num);
27                  }
28          }
29          $downstream->enqueue(undef) if $kid;
30          $kid->join if $kid;
31  }

El hilo permanece en un bucle escuchando en el canal que viene del hilo padre (línea 20) hasta que llegue un undef indicando el final de la computación. En este último caso se propaga la señal de finalización (línea 29) y se espera a la finalización de la thread hija para terminar (línea 30).

El número $num que acaba de llegar es cribado en la línea 21. Si supera la criba se envía al hilo hijo.

La condición de la línea 22 comprueba si esta es la primera vez que un número supera la criba de los primos/hilos calculados hasta el momento. Si es así se procede a crear el hilo hijo (líneas 25-26).

El Arranque

El proceso inicial comienza creando la cola (línea 6) y arrancando el primer hilo que se encargará de la criba por el primer número primo. Después procede a insertar los números del 3 al $n para su cribado corriente abajo:

lhp@nereida:~/Lperl/src/threads$ cat -n primes-using-threads.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use threads;
 4  use Thread::Queue;
 5  my $n = (shift || 10);
 6  my $stream = new Thread::Queue;
 7  my $kid    = new threads(\&check_num, $stream, 2);
 8
 9  for my $i (3 .. $n) {
10          $stream->enqueue($i);
11  }
12
13  $stream->enqueue(undef);
14  $kid->join;

¿Es la Lista de Canales $stream Privada o Compartida?

Observe que $stream no tiene el atributo shared y es, en consecuencia, una estructura de datos privada. Sin embargo a través de su paso como parámetros a la subrutina check_num ejecutada por el hijo queda accesible a este. Nótese que cada canal de $stream es compartido por dos hilos consecutivos.



Subsecciones
Casiano Rodríguez León
Licencia de Creative Commons
Programación Distribuida y Mejora del Rendimiento
por Casiano Rodríguez León is licensed under a Creative Commons Reconocimiento 3.0 Unported License.

Permissions beyond the scope of this license may be available at http://campusvirtual.ull.es/ocw/course/view.php?id=44.
2012-06-19