C语言使用信号量数组实现3线程按序打印0-3000素数

原代码的乱序问题本质是三个线程的打印时机完全由操作系统调度决定，没有同步约束，只要用信号量给三个线程的打印流程加上先后顺序依赖就能解决。

核心思路 #

用长度为3的信号量数组和三个线程一一对应，作为线程的「打印许可」：

• 初始状态只给负责0-999区间的0号线程许可，剩下两个线程启动后先阻塞等许可，不会抢着打印
• 每个线程打完自己区间的所有素数后，给下一个区间的线程发许可，唤醒对方执行
• 整个执行流程会严格按照0号线程→1号线程→2号线程的顺序走，打印结果自然是从小到大排列的

修改后完整代码 #

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

sem_t sem[3]; // 信号量数组，下标对应线程编号

void *findPrimes(void *arg)
{
    int val = *(int *)arg;
    sem_wait(&sem[val]); // 等待自己的打印许可，没拿到就阻塞
    
    for (int i = val * 1000; i < val * 1000 + 1000; i++)
    {
        int isPrime = 1;
        // 修复原代码bug：0和1不是素数，直接跳过
        if (i < 2) isPrime = 0;
        // 优化素数判断逻辑，原代码循环到i-1做了很多无用计算
        for (int j = 2; j * j <= i; j++)
        {
            if (i % j == 0)
            {
                isPrime = 0;
                break;
            }
        }
        if (isPrime)
        {
            printf("%d\n", i);
        }
    }
    
    // 当前线程打印完成，给下一个线程发许可
    if (val < 2) sem_post(&sem[val + 1]);
    
    pthread_exit(NULL);
}

int main()
{
    pthread_t p[3];
    int val[3] = {0, 1, 2};
    
    // 信号量初始化：0号线程初始有1个许可，其余线程初始许可数为0
    sem_init(&sem[0], 0, 1);
    sem_init(&sem[1], 0, 0);
    sem_init(&sem[2], 0, 0);
    
    for (int i = 0; i < 3; i++)
    {
        pthread_create(&p[i], NULL, findPrimes, &val[i]);
    }
    for (int i = 0; i < 3; i++)
    {
        pthread_join(p[i], NULL);
    }
    
    // 销毁信号量释放资源
    for (int i = 0; i < 3; i++)
    {
        sem_destroy(&sem[i]);
    }

    return 0;
}

可选优化 #

上面的实现是线程拿到许可之后才开始计算+打印，相当于三个线程串行执行，没有用到多核并行的能力。如果要兼顾并行效率和有序输出，可以调整线程逻辑：

1. 线程启动后先不等信号量，直接计算自己区间的所有素数，把结果存在线程私有的数组里
2. 全部算完之后再调用sem_wait等打印许可
3. 拿到许可后一次性把自己存的素数全部打印出来，再给下一个线程发许可
   这种改法下三个线程的计算过程是完全并行的，只有打印步骤串行排队，既保证输出有序，又不会浪费CPU性能。

内容的提问来源于stack exchange，提问作者Luca Pedersoli