如何为数独验证器实现线程动态分配以提升性能？

问题背景 #

当前数独验证器的线程仅处理固定分配的单个任务（如4阶数独+2线程时，仅验证行1和列1），未利用空闲线程处理剩余任务。需要实现线程完成当前任务后自动分配新任务的机制——比如行1验证完成后，自动分配行2或列2这类未完成的任务，提升资源利用率。

当前运行输出 #

Enter the size of Sudoku (4, 9, 16, etc.): 4
Enter the number of threads: 2
Thread 1 checks row 1 and is valid.
Thread 2 checks column 1 and is valid.
Sudoku is valid.
The total time taken is 278.00 microseconds.

原始代码（静态任务分配） #

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

#define MAX_SIZE 64

int sudoku[MAX_SIZE][MAX_SIZE];

// 检查单个位置是否合法
int is_valid(int row, int col, int num, int size) {
    // 检查行
    for (int i = 0; i < size; i++) {
        if (i != col && sudoku[row][i] == num) {
            return 0;
        }
    }

    // 检查列
    for (int i = 0; i < size; i++) {
        if (i != row && sudoku[i][col] == num) {
            return 0;
        }
    }

    // 检查子网格
    int subgrid_size = (int)sqrt(size);
    int start_row = row - row % subgrid_size;
    int start_col = col - col % subgrid_size;
    for (int i = start_row; i < start_row + subgrid_size; i++) {
        for (int j = start_col; j < start_col + subgrid_size; j++) {
            if (i != row && j != col && sudoku[i][j] == num) {
                return 0;
            }
        }
    }

    return 1;
}

// 回溯法解数独（当前未用到）
int solve_sudoku(int row, int col, int size) {
    if (row == size) {
        return 1;
    }
    if (col == size) {
        return solve_sudoku(row + 1, 0, size);
    }
    if (sudoku[row][col] != 0) {
        return solve_sudoku(row, col + 1, size);
    }

    for (int num = 1; num <= size; num++) {
        if (is_valid(row, col, num, size)) {
            sudoku[row][col] = num;
            if (solve_sudoku(row, col + 1, size)) {
                return 1;
            }
            sudoku[row][col] = 0;
        }
    }

    return 0;
}

// 线程参数结构体
typedef struct {
    int thread_id;
    int start;
    int end;
    int size;
    int valid;
} ThreadArgs;

// 线程处理函数（静态分配任务）
void *thread_function(void *args) {
    ThreadArgs *thread_args = (ThreadArgs *)args;

    int local_valid = 1;

    // 检查行
    if (thread_args->thread_id <= thread_args->size) {
        int row = thread_args->thread_id - 1;
        for (int j = 0; j < thread_args->size; j++) {
            if (!is_valid(row, j, sudoku[row][j], thread_args->size)) {
                local_valid = 0;
                break;
            }
        }
        printf(local_valid ? "Thread %d checks row %d and is valid.\n" : "Thread %d checks row %d and is invalid.\n", 
               thread_args->thread_id, thread_args->thread_id);
    }

    // 检查列
    if (thread_args->thread_id > thread_args->size && thread_args->thread_id <= 2 * thread_args->size) {
        int col = thread_args->thread_id - 1 - thread_args->size;
        for (int i = 0; i < thread_args->size; i++) {
            if (!is_valid(i, col, sudoku[i][col], thread_args->size)) {
                local_valid = 0;
                break;
            }
        }
        printf(local_valid ? "Thread %d checks column %d and is valid.\n" : "Thread %d checks column %d and is invalid.\n", 
               thread_args->thread_id, thread_args->thread_id - thread_args->size);
    }

    // 检查子网格
    if (thread_args->thread_id > 2 * thread_args->size && thread_args->thread_id <= 3 * thread_args->size) {
        int subgrid_size = (int)sqrt(thread_args->size);
        int subgrid_num = thread_args->thread_id - 2 * thread_args->size;
        int start_row = ((subgrid_num - 1) / subgrid_size) * subgrid_size;
        int start_col = ((subgrid_num - 1) % subgrid_size) * subgrid_size;
        for (int i = start_row; i < start_row + subgrid_size; i++) {
            for (int j = start_col; j < start_col + subgrid_size; j++) {
                if (!is_valid(i, j, sudoku[i][j], thread_args->size)) {
                    local_valid = 0;
                    break;
                }
            }
        }
        printf(local_valid ? "Thread %d checks subgrid %d and is valid.\n" : "Thread %d checks subgrid %d and is invalid.\n", 
               thread_args->thread_id, subgrid_num);
    }

    // 仅线程1更新全局有效性（存在逻辑缺陷）
    if (thread_args->thread_id == 1) {
        thread_args->valid = local_valid;
    }

    pthread_exit(NULL);
}

int main() {
    int size, K;

    printf("Enter the size of Sudoku (4, 9, 16, etc.): ");
    scanf("%d", &size);

    if (size > MAX_SIZE || (int)sqrt(size) != sqrt(size)) {
        printf("Sudoku size must be a square number less than or equal to 64.\n");
        return 1;
    }

    printf("Enter the number of threads: ");
    scanf("%d", &K);

    if (K < 1) {
        printf("Number of threads must be at least 1.\n");
        return 1;
    }

    FILE *file = fopen("input.tex", "r");
    if (file == NULL) {
        printf("Error opening file.\n");
        return 1;
    }

    fscanf(file, "%d", &size);
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            fscanf(file, "%d", &sudoku[i][j]);
        }
    }
    fclose(file);

    clock_t start, end;
    double cpu_time_used;
    start = clock();

    int valid = 1;
    pthread_t threads[K];
    ThreadArgs thread_args[K];

    // 创建线程并分配固定任务
    for (int i = 0; i < K; i++) {
        thread_args[i].thread_id = i + 1;
        thread_args[i].start = i * size / K + 1;
        thread_args[i].end = (i + 1) * size / K;
        thread_args[i].size = size;
        thread_args[i].valid = 1;
        int rc = pthread_create(&threads[i], NULL, thread_function, (void *)&thread_args[i]);
        if (rc) {
            printf("Error: Unable to create thread %d.\n", i + 1);
            exit(-1);
        }
    }

    // 等待线程结束
    for (int i = 0; i < K; i++) {
        pthread_join(threads[i], NULL);
        if (!thread_args[i].valid) {
            valid = 0;
        }
    }

    printf(valid ? "Sudoku is valid.\n" : "Sudoku is invalid.\n");
    
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    double microseconds = cpu_time_used * 1000000;
    printf("The total time taken is %.2f microseconds.\n", microseconds);

    return 0;
}

优化后的代码（动态任务分配） #

通过全局任务队列+互斥锁+条件变量实现线程动态获取任务，线程完成当前任务后自动领取新任务，直到所有任务处理完毕或发现数独无效。

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

#define MAX_SIZE 64
#define TASK_TYPE_ROW 0
#define TASK_TYPE_COL 1
#define TASK_TYPE_SUBGRID 2

int sudoku[MAX_SIZE][MAX_SIZE];
int global_valid = 1; // 全局验证标记，一旦为0所有线程可提前退出

// 任务结构体
typedef struct {
    int type;       // 任务类型：行/列/子网格
    int index;      // 行号、列号或子网格编号
    int size;       // 数独尺寸
} Task;

// 任务队列节点
typedef struct TaskNode {
    Task task;
    struct TaskNode* next;
} TaskNode;

TaskNode* task_queue = NULL;
pthread_mutex_t queue_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t queue_cond = PTHREAD_COND_INITIALIZER;

// 检查单个位置是否合法
int is_valid(int row, int col, int num, int size) {
    // 检查行
    for (int i = 0; i < size; i++) {
        if (i != col && sudoku[row][i] == num) {
            return 0;
        }
    }

    // 检查列
    for (int i = 0; i < size; i++) {
        if (i != row && sudoku[i][col] == num) {
            return 0;
        }
    }

    // 检查子网格
    int subgrid_size = (int)sqrt(size);
    int start_row = row - row % subgrid_size;
    int start_col = col - col % subgrid_size;
    for (int i = start_row; i < start_row + subgrid_size; i++) {
        for (int j = start_col; j < start_col + subgrid_size; j++) {
            if (i != row && j != col && sudoku[i][j] == num) {
                return 0;
            }
        }
    }

    return 1;
}

// 向任务队列添加任务
void enqueue_task(Task task) {
    pthread_mutex_lock(&queue_mutex);
    
    TaskNode* new_node = (TaskNode*)malloc(sizeof(TaskNode));
    new_node->task = task;
    new_node->next = task_queue;
    task_queue = new_node;

    pthread_cond_signal(&queue_cond);
    pthread_mutex_unlock(&queue_mutex);
}

// 从任务队列取出任务（队首）
int dequeue_task(Task* out_task) {
    pthread_mutex_lock(&queue_mutex);

    while (task_queue == NULL && global_valid) {
        pthread_cond_wait(&queue_cond, &queue_mutex);
    }

    if (!global_valid) {
        pthread_mutex_unlock(&queue_mutex);
        return 0; // 已发现无效，无需继续取任务
    }

    TaskNode* temp = task_queue;
    *out_task = temp->task;
    task_queue = temp->next;
    free(temp);

    pthread_mutex_unlock(&queue_mutex);
    return 1;
}

// 线程工作函数：循环取任务并处理
void* thread_function(void* arg) {
    int thread_id = *(int*)arg;
    free(arg); // 释放传入的线程ID内存

    Task task;
    while (global_valid && dequeue_task(&task)) {
        int local_valid = 1;

        switch (task.type) {
            case TASK_TYPE_ROW: {
                int row = task.index;
                for (int j = 0; j < task.size && local_valid; j++) {
                    if (!is_valid(row, j, sudoku[row][j], task.size)) {
                        local_valid = 0;
                    }
                }
                printf(local_valid ? "Thread %d checks row %d and is valid.\n" : "Thread %d checks row %d and is invalid.\n", 
                       thread_id, row + 1);
                break;
            }
            case TASK_TYPE_COL: {
                int col = task.index;
                for (int i = 0; i < task.size && local_valid; i++) {
                    if (!is_valid(i, col, sudoku[i][col], task.size)) {
                        local_valid = 0;
                    }
                }
                printf(local_valid ? "Thread %d checks column %d and is valid.\n" : "Thread %d checks column %d and is invalid.\n", 
                       thread_id, col + 1);
                break;
            }
            case TASK_TYPE_SUBGRID: {
                int subgrid_size = (int)sqrt(task.size);
                int start_row = (task.index / subgrid_size) * subgrid_size;
                int start_col = (task.index % subgrid_size) * subgrid_size;
                for (int i = start_row; i < start_row + subgrid_size && local_valid; i++) {
                    for (int j = start_col; j < start_col + subgrid_size && local_valid; j++) {
                        if (!is_valid(i, j, sudoku[i][j], task.size)) {
                            local_valid = 0;
                        }
                    }
                }
                printf(local_valid ? "Thread %d checks subgrid %d and is valid.\n" : "Thread %d checks subgrid %d and is invalid.\n", 
                       thread_id, task.index + 1);
                break;
            }
        }

        // 若当前任务无效，更新全局标记并通知所有线程退出
        if (!local_valid) {
            pthread_mutex_lock(&queue_mutex);
            global_valid = 0;
            pthread_cond_broadcast(&queue_cond);
            pthread_mutex_unlock(&queue_mutex);
        }
    }

    pthread_exit(NULL);
}

int main() {
    int size, K;

    printf("Enter the size of Sudoku (4, 9, 16, etc.): ");
    scanf("%d", &size);

    if (size > MAX_SIZE || (int)sqrt(size) != sqrt(size)) {
        printf("Sudoku size must be a square number less than or equal to 64.\n");
        return 1;
    }

    printf("Enter the number of threads: ");
    scanf("%d", &K);

    if (K < 1) {
        printf("Number of threads must be at least 1.\n");
        return 1;
    }

    FILE *file = fopen("input.tex", "r");
    if (file == NULL) {
        printf("Error opening file.\n");
        return 1;
    }

    fscanf(file, "%d", &size);
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            fscanf(file, "%d", &sudoku[i][j]);
        }
    }
    fclose(file);

    clock_t start, end;
    double cpu_time_used;
    start = clock();

    // 初始化任务队列：添加所有行、列、子网格任务
    for (int i = 0; i < size; i++) {
        Task row_task = {TASK_TYPE_ROW, i, size};
        enqueue_task(row_task);
        
        Task col_task = {TASK_TYPE_COL, i, size};
        enqueue_task(col_task);
    }

    int subgrid_count = size;
    for (int i = 0; i < subgrid_count; i++) {
        Task sub_task = {TASK_TYPE_SUBGRID, i, size};
        enqueue_task(sub_task);
    }

    // 创建线程
    pthread_t threads[K];
    for (int i = 0; i < K; i++) {
        int* thread_id = (int*)malloc(sizeof(int));
        *thread_id = i + 1;
        int rc = pthread_create(&threads[i], NULL, thread_function, (void*)thread_id);
        if (rc) {
            printf("Error: Unable to create thread %d.\n", i + 1);
            exit(-1);
        }
    }

    // 等待所有线程完成
    for (int i = 0; i < K; i++) {
        pthread_join(threads[i], NULL);
    }

    // 输出结果
    printf(