C语言中如何将队列任务分配给N个线程实现负载均衡？

需求说明 #

需要将队列 [the] -> [quick] -> [brown] -> [fox] -> [jumps] -> [over] -> [the] -> [lazy] -> [dog] 的出队并输出单词任务分配给N个线程，实现负载均衡，且要求至少有一个单词仅由单个线程输出。

现有实现代码（已修复空值打印问题） #

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

#define threadCount 8    // 设置线程数量

pthread_t* thread;
pthread_mutex_t lock;

//========= 队列结构定义 =========
struct node
{
    char *key;
    struct node *next;
};

struct Q 
{
    struct node *front, *rear;
};

struct node* newNode(char *key)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->key = key;
    temp->next = NULL;
    return temp;
}

struct Q* q;

void enqueue(char* key)
{
    struct node* temp = newNode(key);

    if(q->rear == NULL)
    {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

char* dequeue()
{
    if (q->front == NULL)
    {
        return NULL;
    }

    struct node* temp = q->front;
    char *key = temp->key;

    q->front = q->front->next;

    if(q->front == NULL)
    {
        q->rear = NULL;
    }
    free(temp);

    return key;
}
//========= 队列结构定义 =========

void *run(void* arg)
{
    int id = *(int*)arg;
    char* node;

    while(q->front != NULL)
    {
        pthread_mutex_lock(&lock);
        node = dequeue();
        pthread_mutex_unlock(&lock);

        if(node == NULL)
        {
            return NULL;
        }
        
        printf("Thread %d: %s\n", id, node);
    }

    return 0;
}

int main()
{
    q = (struct Q*)malloc(sizeof(struct Q));
    q->front = NULL;
    q->rear = NULL;

    enqueue("the");
    enqueue("quick");
    enqueue("brown");
    enqueue("fox");
    enqueue("jumps");
    enqueue("over");
    enqueue("the");
    enqueue("lazy");
    enqueue("dog");

    thread = malloc(sizeof(pthread_t)*threadCount);
    
    // 疑问：输出中是否应该只有N-1编号的线程？
    for(int id = 0; id < threadCount; id++)
    {
        pthread_create(&thread[id], NULL, (void *) run, &id);
    }

    for(int id = 0; id < threadCount; id++)
    {
        pthread_join(thread[id], NULL);
    }

    free(thread);
    free(q);

    return 0;
}

存在的问题 #

运行代码时，有时会出现打印Thread N（比如这里N=8）的情况，但按照main函数的逻辑，线程编号最大值应为threadCount-1（即7）。

问题原因 #

线程创建时传递的是循环变量id的地址，而main线程的循环执行速度远快于子线程的启动速度。当子线程还没来得及读取arg指向的id值时，main线程的循环已经将id递增到了threadCount（比如8），此时子线程读取到的就是这个超出范围的值，导致打印出Thread 8。

解决方案 #

有两种常见的修复方式：

方案1：为每个线程分配独立的ID存储 #

在main函数中创建一个数组，保存每个线程的ID，传递数组元素的地址给线程，避免循环变量覆盖：

int main()
{
    // ... 其他代码保持不变 ...

    thread = malloc(sizeof(pthread_t)*threadCount);
    int *thread_ids = malloc(sizeof(int)*threadCount); // 新增存储每个线程ID的数组
    
    for(int id = 0; id < threadCount; id++)
    {
        thread_ids[id] = id;
        pthread_create(&thread[id], NULL, run, &thread_ids[id]); // 传递数组元素地址
    }

    for(int id = 0; id < threadCount; id++)
    {
        pthread_join(thread[id], NULL);
    }

    free(thread_ids); // 释放数组内存
    free(thread);
    free(q);

    return 0;
}

方案2：直接传递ID值（利用指针长度兼容） #

将ID值转换为void*类型传递（需保证系统中int和指针长度一致，大多数现代系统满足），在子线程中再转换回int：

// 修改run函数
void *run(void* arg)
{
    int id = (int)(intptr_t)arg; // 转换回int类型
    // ... 其他代码保持不变 ...
}

// 修改main中的线程创建代码
for(int id = 0; id < threadCount; id++)
{
    pthread_create(&thread[id], NULL, run, (void*)(intptr_t)id); // 传递ID值
}

负载均衡说明 #

当前实现的抢锁取任务模式已经能实现较好的负载均衡：每个任务是单个单词，粒度很小，线程会公平竞争锁来获取下一个任务。由于队列共有9个任务，8个线程执行，必然有1个线程处理2个任务，其余7个线程各处理1个任务，天然满足“至少有一个单词仅由单个线程输出”的要求。

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