Die Fibonacci-Folge, die Verwendung von threads in C
Schrieb ich ein Programm in C zu generieren, die eine Fibonacci-Sequenz mit n zahlen, wobei jede Fibonacci-Zahl, die sich durch einen separaten thread, dem Eltern thread Ausgänge ganze produziert Fibonacci-Folge doch ich bekam falsche Reihenfolge für n>2 ist es, wie einige schreiben Sie den Wert des letzten Elements in der Fibonacci-Sequenz-array ist 0, wenn n>2 .Wie kann ich es beheben? bitte finden Sie den code unten.
/*============================================================================
Description :The Fibonacci sequence
============================================================================ */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int n; //size of fibonacci sequence.
int *fibseq; //arry holds the value of each fibonacci term.
int i; //counter for the threads.
void *runn(void *arg);
int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("format is:./a.out <intgervalue>\n");
return -1;
} //valdiate num of args.
if (atoi(argv[1]) < 0)
{
printf("%d must be>=0\n", atoi(argv[1]));
return -1;
} //valdiate value of arg1.
n = atoi(argv[1]);
fibseq = (int *)malloc(n * sizeof(int));
pthread_t *threads = (pthread_t *) malloc(n * sizeof(pthread_t));
pthread_attr_t attr; //set of thread attribute
pthread_attr_init(&attr);
for (i = 0; i < n; i++)
{
pthread_create(&threads[i], &attr, runn, NULL);
} //End of creating threads.
int j;
for (j = 0; j < n; j++)
{
pthread_join(threads[j], NULL);
} //End of wating the threads to exit.
//printing fibseq.
printf("The Fibonacci sequence.:");
int k;
for (k = 0; k < n; k++)
{
printf("%d,", fibseq[k]);
} //End of printing fibseq.
return 0;
} //End of main.
void *runn(void *arg)
{
if (i == 0)
{
fibseq[i] = 0;
pthread_exit(0);
} //first fib term
if (i == 1)
{
fibseq[i] = 1;
pthread_exit(0);
} //seconed fib term
else
{
fibseq[0] = 0;
fibseq[1] = 1;
int p, pp, fibp, fibpp;
p = (i - 1);
pp = (i - 2);
fibp = fibseq[p];
//printf("fibseq[%d]%d\n",p,fibp);
fibpp = fibseq[pp];
//printf("fibseq[%d]%d\n",pp,fibpp);
fibseq[i] = fibseq[i - 1] + fibseq[i - 2];
//printf("fibseq[%d]%d,\n",i,fibseq[i]);
pthread_exit(0); //thread exit.
} //End of else
} //End of run.
- Da jeder Wert ist abhängig von der vorherigen, warum willst du es mit threads? Es wird nur zu Problemen führen, da Sie mitbekommen habe. Nichts sagt, dass der Wert n bestimmt werden, bevor n+1, so Werte sind Müll.
- Warum wollen Sie dies tun? Es scheint ziemlich ungeeignet zur Parallelisierung. Sie hätten die Reihenfolge der threads eine nach der anderen sowieso.
- Ziel ist es, zu üben, wie Fäden produzieren können, die Reihenfolge, und ich pthread_join zum synchronisieren der threads, die aber immer noch nicht die richtige Ausgabe
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sehe ich, dass diese post ist von Dezember 2015, aber die Antwort auf dein problem ist ganz einfach. Der Grund ist, weil Sie mit zwei separaten for-Schleifen zu erstellen und sich die threads. Was wird dies tun, verursacht die i < n threads zu erstellen und auszuführen, die durch Ihre *runn Funktion zur gleichen Zeit. Sinn des threads warten nicht auf das array aktualisiert werden.
Sollten Sie in einer einzigen for-Schleife, so werden die thread_join Anweisung regelt in jedem thread bei jedem Schleifendurchlauf. Wie ich unten.
Nun deine threads gehen durch Ihre *runn Funktion ein zu einer Zeit. So fixieren Sie Ihr Problem.
On a side note, die Sie zu haben scheinen einige unnötige code an das Ende Ihrer *runn-Funktion ist das nicht notwendig und ist nur nochmal die Arbeit, die Sie getan haben.
Dies ist auch unnötig. Obwohl, wenn ich es richtig verstehe, das war verwendet für debugging-Zwecke richtig?
Nur relevanten code für den else-Anweisung ist hier
Ich hoffe, dies hilft, diese Frage zu beantworten.
Die Fibonnaci-Folge ist schlecht geeignet, um eine parallelisierte Lösung. Es ist eigentlich eine in geschlossener form-Lösung das ist nicht allzu schwer zu berechnen und mit ziemlicher Sicherheit schneller, als auch eine thread-basierte Lösung:
wo
φ = (1 + √5) /2
undψ = (1 - √5) /2
.Bearbeiten - auf meinem system, die geschlossene form abweicht, die für
n
> 71 durch akkumulierte Rundungsfehler; verwenden Sie eine beliebige Präzision Bibliothek würde helfen.Wenn Sie entschlossen sind, diese Arbeit zu machen, jedoch müssen Sie die folgenden im Auge behalten:
Können Sie nicht berechnen
fibseq[i]
es sei dennfibseq[i-1]
undfibseq[i-2]
bereits berechnet; man muss eine Bedingung variable zum anhalten der Ausführung von threadi
bis threadsi-1
undi-2
abgeschlossen haben;Haben Sie eine race-condition wo
main
ist die Aktualisierung des Wertsi
während die threads versuchen, den Wert voni
zur gleichen Zeit. Man könnte ein mutex zu synchronisieren, greift deri
, aber ehrlich, eine bessere Lösung wäre, das passieren der Wert voni
als argument an den thread (übergabe der Adresse wird nicht helfen; Sie haben die gleichen Synchronisations-Problem).i
an die thread-Funktion, aber ich habe immer noch die gleiche falsche Ausgabe .Gibt es einen anderen Weg, umpthread_join
zum synchronisieren der Zugriffe ich da, wie man sehen kann in dem code, den ich versuchte, es zu benutzen, aber ich kann nicht sehen, die problem. Dankefibseq[i]
kann nicht berechnet werden, bisfibseq[i-1]
undfibseq[i-2]
berechnet wurden; wenn das array Elemente berechnet werden, die out-of-order, dann Sie werden nicht erhalten die richtige Ausgabe. Das ist, warum ist das so ein bad fit für einen parallel-thread-basierte Lösung. Fäden 2 bisn
warten, während threads 0 und 1 machen Ihr Ding, dann ein Gewinde 3 durchn
warten, bis thread 2 fertig ist, dann Fäden 4 durchn
warten, bis thread 3 etc.