utiliza - Error de segmentación para pthreads en una llamada recursiva

funciones recursivas

Question

Dado el siguiente código, obtengo un error de segmentación si lo ejecuto con n> 16.

Creo que tiene algo que ver con la pila, pero no puedo resolverlo. ¿Alguien podría darme una mano? El código no es mío, y realmente no es importante. Me gustaría que alguien me diera una mano con lo que está sucediendo. Esta pregunta SO es muy similar, pero no hay suficiente información (la persona que publica la respuesta habla brevemente sobre el problema, pero luego habla sobre un idioma diferente). Además, observe que con dos gigas y sin recursión, puedo (si lo estoy haciendo bien) crear exitosamente más de 16000 subprocesos (aunque el SO solo crea alrededor de 500 y ejecuta alrededor de 300). De todos modos, ¿dónde estoy obteniendo la falla seg aquí y por qué? Gracias.

#include <pthread.h>
#include <stdio.h>

static void* fibonacci_thread( void* arg ) {
int n = (int)arg, fib;

pthread_t th1, th2;

void* pvalue; /*Holds the value*/

switch (n) {
case 0:  return (void*)0;
case 1:  /* Fallthru, Fib(1)=Fib(2)=1 */
case 2:  return (void*)1;
default: break;
}

pthread_create(&th1, NULL, fibonacci_thread, (void*)(n-1));

pthread_create( &th2, NULL, fibonacci_thread, (void*)(n-2));

pthread_join(th1, &pvalue);

fib = (int)pvalue;

pthread_join(th2, &pvalue);

fib += (int)pvalue;

return (void*)fib;
}

int main(int argc, char *argv[])
{
int n=15;
printf ("%d/n",(int)fibonacci_thread((void*)n));
return 0;
}

Answer 1

Diablos, podría ser una respuesta.

Primero, verifique los valores de retorno de pthread_create y pthread_join . (Siempre, siempre, siempre verifique si hay errores. Simplemente assert que regresa a cero si se siente flojo, pero nunca los ignore).

En segundo lugar, podría haber jurado que Linux glibc asigna de manera predeterminada algo así como 2 megabytes de pila por hilo (configurable a través de pthread_attr_setstacksize ). Claro, eso es solo memoria virtual, pero en un sistema de 32 bits que todavía te limita a ~ 2000 hilos en total.

Finalmente, creo que la estimación correcta de la cantidad de hilos que generará es básicamente fib(n) sí misma (qué recursividad tiene). O aproximadamente phi^n , donde phi es (1+sqrt(5))/2 . Entonces, el número de subprocesos aquí está más cerca de 2000 que de 65000, lo cual es consistente con mi estimación de dónde se quedará sin VM un sistema de 32 bits.

[editar]

Para determinar el tamaño de pila predeterminado para nuevos subprocesos en su sistema, ejecute este programa:

int main(int argc, char *argv[])
{
    size_t stacksize;
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_getstacksize(&attr, &stacksize);
    phthread_attr_destroy(&attr);
    printf("Default stack size = %zd/n", stacksize);
    return 0;
}

[editar 2]

Para repetir: Esto no está cerca de 2 ^ 16 hilos.

Sea f (n) la cantidad de hilos generados cuando se calcula fib (n).

Cuando n = 16, un hilo genera dos nuevos hilos: uno para calcular fib (15) y otro para calcular fib (14). Entonces f (16) = f (15) + f (14) + 1.

Y en general f (n) = f (n-1) + f (n-2) + 1.

Como resultado, la solución a esta recurrencia es que f (n) es solo la suma de los primeros n números de Fibonacci:

      1 + 1 + 2 + 3 + 5 + 8   // f(6)
+         1 + 1 + 2 + 3 + 5   // + f(5)
+ 1                           // + 1

= 1 + 1 + 2 + 3 + 5 + 8 + 13  // = f(7)

Esto es (muy) aproximadamente phi^(n+1) , no 2^n . El total de f (16) aún se mide en miles bajos, no en decenas de miles.

[editar 3]

Ah, ya veo, el quid de su pregunta es esto (planteado por los comentarios):

Gracias Nemo por una respuesta detallada. Hice una pequeña prueba y pthread_created ~ 10,000 hilos con solo un rato (1) loop dentro para que no terminen ... ¡y lo hizo! Es cierto que el sistema operativo era inteligente para crear solo alrededor de 1000 y ejecutar un número aún menor, pero no se quedó sin pila. ¿Por qué no obtengo un segfault cuando genero mucho más que THREAD_MAX, pero lo hago cuando lo hago recursivamente?

Aquí está mi suposición.

Solo tienes algunos núcleos. En cualquier momento, el kernel debe decidir qué hilos se ejecutarán. Si tiene (digamos) 2 núcleos y 500 hilos, entonces cualquier hilo en particular solo se ejecutará 1/250 de las veces. Por lo tanto, el bucle principal que genera nuevos hilos no se ejecutará con mucha frecuencia. Ni siquiera estoy seguro de si el programador del kernel es "justo" con respecto a los hilos dentro de un único proceso, por lo que es al menos concebible que con 1000 hilos el hilo principal nunca llegue a ejecutarse.

Por lo menos, cada hilo while (1); se ejecutará por 1/HZ en su núcleo antes de renunciar a su porción de tiempo. Esto es probablemente 1ms, pero podría ser tan alto como 10ms dependiendo de cómo se configuró su kernel. Entonces, incluso si el programador es justo, su hilo principal solo se ejecutará una vez por segundo cuando tenga miles de hilos.

Como solo el hilo principal está creando nuevos hilos, la tasa de creación del hilo se ralentiza y posiblemente incluso se detiene.

Prueba esto. En lugar de while (1); para los subprocesos hijo en su experimento, intente while (1) pause(); . ( pause is from unistd.h.) Esto mantendrá los subprocesos hijo bloqueados y debería permitir que el subproceso principal continúe eliminando creando nuevos subprocesos, lo que provocará su bloqueo.

Y de nuevo, compruebe qué devuelve pthread_create .

Answer 2

Esta no es una buena manera de hacer una secuencia de Fibonacci :-)

Tu primer hilo comienza con otros dos, cada uno de ellos inicia otros dos y así sucesivamente. Entonces, cuando n > 16 , puede terminar con una gran cantidad de hilos (en miles) ^(a) .

A menos que su CPU tenga muchos más núcleos que los míos, perderá su tiempo ejecutando miles de subprocesos para una tarea de CPU como esta. Para tareas puramente vinculadas a la CPU, es mejor tener tantos hilos como motores de ejecución física (núcleos o CPU) disponibles para usted. Obviamente, eso cambia donde no estás puramente vinculado a la CPU.

Si desea una calculadora Fibonacci recursiva (sin hilos) eficiente, debe usar algo como (pseudo-código):

def fib(n, n ranges from 1 to infinity):
    if n is 1 or 2:
        return 1
    return fib(n-1) + fib(n-2)

Fibonacci ni siquiera es realmente tan bueno para la recursión sin subprocesos ya que el problema no se reduce muy rápido. Por eso, me refiero a calcular fib(1000) utilizará 1000 marcos de pila. Compare esto con una búsqueda de árbol binario recursivo donde solo se necesitan diez marcos de pila. Esto se debe a que el primero solo elimina 1/1000 del espacio de búsqueda para cada marco de pila, mientras que el segundo elimina la mitad del espacio de búsqueda restante.

La mejor manera de hacer Fibonacci es con iteración:

def fib(n, n ranges from 1 to infinity):
    if n is 1 or 2:
        return 1
    last2 = 1, last1 = 1
    for i ranges from 3 to n:
        last0 = last2 + last1
        last2 = last1
        last1 = last0
    return last0

Por supuesto, si desea un generador de Fibonacci deslumbrantemente rápido, escriba un programa para generar todos los que pueda almacenar (en, por ejemplo, un valor largo) y escriba una estructura en C para contenerlos. Luego, incorpore esa salida en su programa C y sus "cálculos" de tiempo de ejecución expulsarán cualquier otro método fuera del agua. Este es su método estándar de optimización de "compensación de espacio por tiempo":

long fib (size_t n) {
    static long fibs[] = {0, 1, 1, 2, 3, 5, 8, 13, ...};
    if (n > sizeof(fibs) / sizeof(*fibs))
        return -1;
    return fibs[n];
}

Estas pautas se aplican a la mayoría de las situaciones donde el espacio de búsqueda no se reduce tan rápido (no solo Fibonacci).

^(a) Originalmente, pensé que esto sería 2 ¹⁶ pero, como muestra el siguiente programa (y gracias a Nemo por haberme aclarado), no es tan malo, no tomé en cuenta la naturaleza reductora de los hilos engendrados a medida que te acercas a fib(0) :

#include <stdio.h>
static count = 0;
static void fib(int n) {
        if (n <= 2) return;
        count++; fib(n-1);
        count++; fib(n-2);
}
int main (int argc, char *argv[]) {
        fib (atoi (argv[1]));
        printf ("%d/n", count);
        return 0;
}

Esto es equivalente al código que tiene, pero simplemente incrementa un contador para cada subproceso generado en lugar de engendrarlos realmente. El número de subprocesos para varios valores de entrada es:

 N    Threads
---  ---------
  1          0
  2          0
  3          2
  4          4
  5          8
  6         14
  :
 14
 15      1,218
 16      1,972
  :
 20     13,528
  :
 26    242,784
  :
 32  4,356,616

Ahora tenga en cuenta que, aunque dije que no era tan malo, no dije que fuera bueno :-) Incluso dos mil hilos es una carga justa en un sistema, cada uno con sus propias estructuras y pilas de kernel. Y puede ver que, mientras los aumentos comienzan pequeños, aceleran rápidamente hasta el punto en que son inmanejables. Y no es que el número 32 sea grande, es solo un poco más de dos millones.

Así que la línea de fondo sigue en pie: use la recursión donde tenga sentido (donde puede reducir el espacio de búsqueda relativamente rápido para no quedarse sin espacio en la pila), y use threds donde tenga sentido (donde no termine ejecutando tantos que sobrecarga los recursos del sistema operativo).

Answer 3

Lo primero que haría sería ejecutar una declaración como printf("%i", PTHREAD_THREADS_MAX); y ver cuál es el valor; No creo que los hilos máximos del SO sean necesariamente los mismos que el número máximo de subprocesos, aunque sí veo que puedes decir que puedes lograr 16000 subprocesos sin recurrencia, así que solo lo menciono como algo que haría. comprobar en general.

si PTHREAD_THREADS_MAX es significativamente> el número de hilos que está logrando, comenzaría a verificar los valores de retorno de las llamadas pthread_create () para ver si está obteniendo EAGAIN . Sospecho que la respuesta a su pregunta es que está obteniendo un segfault al intentar usar un hilo no inicializado en una unión ...

también, como mencionó paxdiablo, estás hablando del orden de 2^16 hilos en n=16 aquí (un poco menos suponiendo que algunos terminen antes de que se creen los últimos); Probablemente intentaría mantener un registro para ver en qué orden fue creado. probablemente lo más fácil sería usar los valores (n-1) (n-2) como elementos de registro, de lo contrario, tendría que usar un semáforo o similar para proteger un contador ...

printf podría atascarse, de hecho, no me sorprendería si eso realmente afectara las cosas al permitir que más subprocesos terminaran antes de que se iniciaran los nuevos, pero entonces probablemente solo iniciaría sesión usando el archivo write() ; puede ser un archivo simple, usted debería ser capaz de hacerse una idea de lo que está sucediendo al observar los patrones de los números allí. (Espera, eso supone que las operaciones de archivo son seguras para hilos, creo que lo son, ha pasado un tiempo).

también, una vez que compruebe si EAGAIN podría intentar dormir un poco y volver a intentarlo; quizás aumente con el tiempo y el sistema simplemente se vea abrumado por la gran cantidad de solicitudes de subprocesos y falle por alguna otra razón que no sea por falta de recursos; esto verificaría si tan solo esperar y reiniciar pudiera llevarte a donde quieres estar.

finalmente; podría tratar de volver a escribir la función como un fork() (sé que fork () es malo o lo que sea;)) y ver si tienes mejor suerte allí.

:)