2

我正在编写一个多线程的 Eratosthenes 筛，我必须使用 pthreads。我很确定这样做的方法是使用互斥锁和 cond_waits。我在程序开始时创建了 4 个线程，然后我必须强制它们等待，直到 Eratosthenes 的筛子找到一个素数。然后我必须解除阻塞线程，以便它们可以标记位数组中该素数的每次迭代。然后，他们必须再次阻塞并等待下一个素数，直到埃拉托色尼筛算法耗尽自己的新数字。

这是我的线程函数的代码：

while(!doneFlag){
        printf("Thread wile loop\n");
        pthread_mutex_lock(&lock);
        pthread_cond_wait(&cond, &lock);

        startingPosition = (double)(maxNum/numThreads) * i;
        endingPosition = (double)(maxNum/numThreads) * (i+1)-1;
        if(i == numThreads-1){
            endingPosition = maxNum;
        } 
... Until the end of the function ... 
pthread_mutex_unlock(&lock);
}
return (void*)0;

doneFlag 是我在埃拉托色尼筛算法完成所有数字时设置为 1 的标志。我希望带有 cond_wait() 函数的 while 循环会导致线程等待输入（只要还有输入要给出）

这是 main() 函数中的 Sieve 部分：

while(outerCounter < sqrt(maxNum)){
    //searching numbers above the current for prime numbers
    //printf("Sieve While\n");
    for(innerCounter = outerCounter+1; innerCounter <= maxNum; innerCounter++){
        //not composite
        //printf("Sieve for\n");
        if(composite[innerCounter] == 0){

            printf("Prime found: %d\n", innerCounter);
            pthread_mutex_lock(&lock);
            pthread_cond_broadcast(&cond);
            pthread_mutex_unlock(&lock);

            outerCounter = innerCounter;
            numPrimes++;

        }
    }
}
doneFlag = 1;

不知何故，复合数字没有被标记为复合数字（尽管有几个是）。我假设因为它与 main() 函数的竞争条件有关，它如何在线程仍在后台运行时不断找到更多素数，从而在线程仍在工作时更改素数。

我怎样才能解决这个问题？我的 locks/cond_wait 设置正确吗？我很难在网上找到这方面的资源。

谢谢！

编辑：我还想确保我的每个线程都可以同时运行该函数（该函数将数组中的元素标记为复合元素）。也许互斥锁在我的线程函数中不是一个好主意，因为我希望它们一起运行？（每个线程占用数组的不同段）

4

1 回答 1

1

Fayyazkl首先说。使用计数信号量而不是静音。查找生产者/消费者，因为这就是您要解决的问题！

所以，我不熟悉你使用的算法，但我试图理解，所以我可以提供更多帮助。我假设每个新的素数都是一份新工作？

无论如何，您需要您的主循环来生成自包含的作业，以便作业线程可以从作业队列中拉出新作业并拥有它需要的所有信息。如果作业只是新的素数，则将新的素数添加到队列并发布计数信号量。（请记住，队列需要同步）

线程将首先挂在计数信号量上。当信号量发出信号时，线程将唤醒并获取在 sem 发出信号之前放置在队列中的作业。然后线程将处理作业并发布结果。

我认为您的问题是您没有集中的方式来生成具有显式作业参数的新作业，因此两个或多个线程正在唤醒并获得相同的作业，或者没有。

于 2013-03-05T07:18:27.370 回答