具有线程的递归Fib,分段错误?

任何想法为什么它适用于0,1,2,3,4等值,并且像> 15这样的值的seg故障? #include #include #include

void *fib(void *fibToFind); main(){ pthread_t mainthread; long fibToFind = 15; long finalFib; pthread_create(&mainthread,NULL,fib,(void*) fibToFind); pthread_join(mainthread,(void*)&finalFib); printf("The number is: %d\n",finalFib); } void *fib(void *fibToFind){ long retval; long newFibToFind = ((long)fibToFind); long returnMinusOne; long returnMinustwo; pthread_t minusone; pthread_t minustwo; if(newFibToFind == 0 || newFibToFind == 1) return newFibToFind; else{ long newFibToFind1 = ((long)fibToFind) - 1; long newFibToFind2 = ((long)fibToFind) - 2; pthread_create(&minusone,NULL,fib,(void*) newFibToFind1); pthread_create(&minustwo,NULL,fib,(void*) newFibToFind2); pthread_join(minusone,(void*)&returnMinusOne); pthread_join(minustwo,(void*)&returnMinustwo); return returnMinusOne + returnMinustwo; } } 

运行内存(堆栈空间不足)或有效的线程句柄?

你需要大量的线程,这需要大量的堆栈/上下文。 Windows(和Linux)有一个愚蠢的“大[连续]堆栈”的想法。

从pthreads_create上的文档:“在Linux / x86-32上,新线程的默认堆栈大小是2兆字节。” 如果您生产10,000个线程,则需要20 Gb的RAM。 我构建了一个版本的OP程序,它在Windows XP64上轰炸了3500(p)个线程。

有关为什么大堆栈是一个非常糟糕的想法的更多详细信息,请参阅此SO线程: 为什么堆栈溢出仍然是一个问题?

如果你放弃大堆栈,并为激活记录实现堆分配的并行语言(我们的PARLANSE就是其中之一)问题就会消失。

这是我们在PARLANSE中编写的第一个(顺序)程序:

 (define fibonacci_argument 45) (define fibonacci (lambda(function natural natural )function `Given n, computes nth fibonacci number' (ifthenelse (<= ? 1) ? (+ (fibonacci (-- ?)) (fibonacci (- ? 2)) )+ )ifthenelse )lambda )define 

这是i7上的执行:

  C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonaccisequential Starting Sequential Fibonacci(45)...Runtime: 33.752067 seconds Result: 1134903170 

这是第二个,它是平行的:

 (define coarse_grain_threshold 30) ; technology constant: tune to amortize fork overhead across lots of work (define parallel_fibonacci (lambda (function natural natural )function `Given n, computes nth fibonacci number' (ifthenelse (<= ? coarse_grain_threshold) (fibonacci ?) (let (;; [n natural ] [m natural ] ) (value (|| (= m (parallel_fibonacci (-- ?)) )= (= n (parallel_fibonacci (- ? 2)) )= )|| (+ mn) )value )let )ifthenelse )lambda )define 

使并行性显式化使得程序也更容易编写。

我们通过调用(parallel_fibonacci 45)测试的并行版本。 这是在同一个i7上执行的运行(可以说它有8个处理器,但实际上有4个超线程处理器,所以它真的不是8个等效的CPU):

 C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonacciparallelcoarse Parallel Coarse-grain Fibonacci(45) with cutoff 30...Runtime: 5.511126 seconds Result: 1134903170 

加速度接近6+,对不到8个处理器来说也不错。 这个问题的另一个答案就是运行pthreads版本; 计算Fib(18)需要“几秒钟”(炸毁),而Fib(45)则需要5.5秒。 这告诉你pthreads是一种根本不好的方法来做很多细粒度并行,因为它有非常非常高的分叉开销。 (PARLANSE旨在最小化分叉开销)。

如果您将技术常量设置为零( 每次调用fib时分叉),会发生以下情况:

 C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonacciparallel Starting Parallel Fibonacci(45)...Runtime: 15.578779 seconds Result: 1134903170 

您可以看到,即使您有快速分叉,分摊摊销也是一个好主意。

Fib(45)产生大量谷物。 激活记录的堆分配解决了OP的一阶问题(成千上万个pthread,每个堆栈有1Mb堆烧掉数十亿字节的RAM)。

但是有一个二阶问题:即使你的颗粒控制块很小,2 ^ 45 PARLANSE“颗粒”也会燃烧你所有的记忆,只是跟踪颗粒。 因此,一旦你有“很多”(对于“很多”的一些定义明显少于2 ^ 45)晶粒,以防止并行性爆炸使用“谷物”跟踪数据淹没机器,有一个调度程序可以限制分叉结构。 当谷物数量也低于阈值时,它必须不用油门,以确保物理CPU总是有很多逻辑,并行的工作。

您没有检查错误 – 特别是来自pthread_create() 。 当pthread_create()失败时, pthread_t变量未定义,后续的pthread_join()可能会崩溃。

如果确实检查了错误,则会发现pthread_create()失败。 这是因为您尝试生成近2000个线程 – 使用默认设置,这将需要单独分配16GB的线程堆栈。

您应该修改算法,以便它不会生成这么multithreading。

我试图运行你的代码,并遇到了几个惊喜:

 printf("The number is: %d\n", finalFib); 

这一行有一个小错误: %d表示printf需要一个int ,但是传递一个long int 。 在大多数平台上,这是相同的,或者会有相同的行为,但是迂腐地说(或者如果你只是想阻止警告出现,这也是一个非常崇高的理想),你应该使用%ld代替,期待一个long int

另一方面,你的fibfunction似乎不起作用。 在我的机器上测试它,它不会崩溃,但它产生1047 ,这不是斐波纳契数。 仔细观察,似乎你的程序在几个方面是不正确的:

 void *fib(void *fibToFind) { long retval; // retval is never used long newFibToFind = ((long)fibToFind); long returnMinusOne; // variable is read but never initialized long returnMinustwo; // variable is read but never initialized pthread_t minusone; // variable is never used (?) pthread_t minustwo; // variable is never used if(newFibToFind == 0 || newFibToFind == 1) // you miss a cast here (but you really shouldn't do it this way) return newFibToFind; else{ long newFibToFind1 = ((long)fibToFind) - 1; // variable is never used long newFibToFind2 = ((long)fibToFind) - 2; // variable is never used // reading undefined variables (and missing a cast) return returnMinusOne + returnMinustwo; } } 

始终注意编译器警告:当你得到一个警告时,通常,你真的在做一些可疑的事情。

也许你应该稍微修改算法:现在,你所有的函数都返回两个未定义值的总和,因此我得到的是1047。

使用递归算法实现Fibonacci套件意味着您需要再次调用该函数。 正如其他人所指出的那样,这是一种效率很低的方式,但这很简单,所以我想所有计算机科学教师都以此为例。

常规递归算法如下所示:

 int fibonacci(int iteration) { if (iteration == 0 || iteration == 1) return 1; return fibonacci(iteration - 1) + fibonacci(iteration - 2); } 

我不知道你应该在多大程度上使用线程 – 只需在辅助线程上运行算法,或者为每个调用创建新线程? 让我们假设现在是第一个,因为它更直接。

将整数转换为指针反之亦然是一种不好的做法,因为如果你试图在更高层次上看待事物,它们应该是截然不同的。 整数执行数学运算,指针解析内存地址。 它恰好起作用,因为它们以相同的方式表示,但实际上,你不应该这样做。 相反,您可能会注意到,运行新线程的函数接受void*参数:我们可以使用它来传达输入的位置和输出的位置。

因此,基于我之前的fibonacci函数,您可以使用此代码作为线程主程序:

 void* fibonacci_offshored(void* pointer) { int* pointer_to_number = pointer; int input = *pointer_to_number; *pointer_to_number = fibonacci(input); return NULL; } 

它需要一个指向整数的指针,并从中获取输入,然后将输出写入其中。 1然后,您将创建这样的线程:

 int main() { int value = 15; pthread_t thread; // on input, value should contain the number of iterations; // after the end of the function, it will contain the result of // the fibonacci function int result = pthread_create(&thread, NULL, fibonacci_offshored, &value); // error checking is important! try to crash gracefully at the very least if (result != 0) { perror("pthread_create"); return 1; } if (pthread_join(thread, NULL) { perror("pthread_join"); return 1; } // now, value contains the output of the fibonacci function // (note that value is an int, so just %d is fine) printf("The value is %d\n", value); return 0; } 

如果你需要从新的不同线程中调用Fibonacci函数(请注意:这不是我建议的,其他人似乎同意我的观点;它会爆发足够大量的迭代),你首先要做需要将fibonaccifibonacci函数与fibonacci_offshored函数合并。 它会大大增加它,因为处理线程比处理常规函数更重。

 void* threaded_fibonacci(void* pointer) { int* pointer_to_number = pointer; int input = *pointer_to_number; if (input == 0 || input == 1) { *pointer_to_number = 1; return NULL; } // we need one argument per thread int minus_one_number = input - 1; int minus_two_number = input - 2; pthread_t minus_one; pthread_t minus_two; // don't forget to check! especially that in a recursive function where the // recursion set actually grows instead of shrinking, you're bound to fail // at some point if (pthread_create(&minus_one, NULL, threaded_fibonacci, &minus_one_number) != 0) { perror("pthread_create"); *pointer_to_number = 0; return NULL; } if (pthread_create(&minus_two, NULL, threaded_fibonacci, &minus_two_number) != 0) { perror("pthread_create"); *pointer_to_number = 0; return NULL; } if (pthread_join(minus_one, NULL) != 0) { perror("pthread_join"); *pointer_to_number = 0; return NULL; } if (pthread_join(minus_two, NULL) != 0) { perror("pthread_join"); *pointer_to_number = 0; return NULL; } *pointer_to_number = minus_one_number + minus_two_number; return NULL; } 

现在您已经拥有了这个庞大的function,对main函数的调整将变得非常简单:只需将对fibonacci_offshored的引用更改为threaded_fibonacci

 int main() { int value = 15; pthread_t thread; int result = pthread_create(&thread, NULL, threaded_fibonacci, &value); if (result != 0) { perror("pthread_create"); return 1; } pthread_join(thread, NULL); printf("The value is %d\n", value); return 0; } 

您可能已经被告知线程可以加速并行进程,但是在某些地方设置线程比运行其内容更昂贵。 这是这种情况的一个很好的例子 :程序的线程版本比非线程版本运行得多,速度慢得多。

出于教育目的,当所需迭代次数为18时,此程序在我的机器上运行线程,并且需要几秒钟才能运行。 相比之下,使用迭代实现,我们永远不会耗尽线程,我们的答案只需几毫秒。 它也相当简单。 这将是一个很好的例子,说明如何使用更好的算法修复许多问题。

此外,出于好奇,看看它是否在您的机器上崩溃以及在何处/如何崩溃将会很有趣。

1.通常,您应该尽量避免在函数返回后更改输入值与其值之间的变量含义。 例如,这里,在输入时,变量是我们想要的迭代次数; 在输出上,它是函数的结果。 这是两个非常不同的含义,这不是一个好的做法。 我不想使用动态分配通过void*返回值返回值。