实验名称

多线程编程实验

实验日期

2024年10月24日

实验目的

1. 深入理解多线程编程的概念。
2. 实践创建和管理多线程程序的方法。
3. 设计并实现一个多线程数独解决方案验证器。
4. 设计并实现一个多线程排序应用。

实验环境

• 操作系统：Ubuntu 20.04 LTS
• 编译器：GCC 9.3.0
• 开发工具：Visual Studio Code

实验内容

第一部分：数独解决方案验证器

设计思路

1. 定义数据结构：创建一个结构体来存储每个线程需要检查的行和列信息。
2. 创建线程：根据任务需求，创建相应数量的线程来检查数独的行、列和小方格。
3. 传递参数：使用结构体传递必要的参数给每个线程。
4. 结果收集：每个线程完成检查后，将结果存入共享数组中，父线程最后检查这些结果来确定数独解的有效性。

实现代码

#include 
#include 
#include 

#define N 9

typedef struct {
    int row;
    int col;
} parameters;

int sudoku[N][N] = {
    {5, 3, 0, 0, 7, 0, 0, 0, 0},
    {6, 0, 0, 1, 9, 5, 0, 0, 0},
    {0, 9, 8, 0, 0, 0, 0, 6, 0},
    {8, 0, 0, 0, 6, 0, 0, 0, 3},
    {4, 0, 0, 8, 0, 3, 0, 0, 1},
    {7, 0, 0, 0, 2, 0, 0, 0, 6},
    {0, 6, 0, 0, 0, 0, 2, 8, 0},
    {0, 0, 0, 4, 1, 9, 0, 0, 5},
    {0, 0, 0, 0, 8, 0, 0, 7, 9}
};

int results[11] = { 0 };

void* checkRow(void* arg) {
    parameters* p = (parameters*)arg;
    int count[10] = { 0 };
    for (int i = 0; i < N; ++i) { if (sudoku[p->row][i] == 0) continue;
        if (++count[sudoku[p->row][i]] > 1) {
            results[p->row] = 0;
            pthread_exit(NULL);
        }
    }
    results[p->row] = 1;
    pthread_exit(NULL);
}

void* checkCol(void* arg) {
    parameters* p = (parameters*)arg;
    int count[10] = { 0 };
    for (int i = 0; i < N; ++i) { if (sudoku[i][p->col] == 0) continue;
        if (++count[sudoku[i][p->col]] > 1) {
            results[p->col + N] = 0;
            pthread_exit(NULL);
        }
    }
    results[p->col + N] = 1;
    pthread_exit(NULL);
}

void* checkSubgrid(void* arg) {
    parameters* p = (parameters*)arg;
    int count[10] = { 0 };
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) { if (sudoku[p->row + i][p->col + j] == 0) continue;
            if (++count[sudoku[p->row + i][p->col + j]] > 1) {
                results[p->row / 3 * 3 + p->col / 3 + 2 * N] = 0;
                pthread_exit(NULL);
            }
        }
    }
    results[p->row / 3 * 3 + p->col / 3 + 2 * N] = 1;
    pthread_exit(NULL);
}

int main() {
    pthread_t threads[11];
    parameters params[11];

    for (int i = 0; i < N; ++i) {
        params[i].row = i;
        params[i].col = 0;
        pthread_create(&threads[i], NULL, checkRow, &params[i]);
    }

    for (int i = 0; i < N; ++i) {
        params[i].row = 0;
        params[i].col = i;
        pthread_create(&threads[i + N], NULL, checkCol, &params[i]);
    }

    for (int i = 0; i < 9; i += 3) {
        for (int j = 0; j < 9; j += 3) {
            params[i / 3 * 3 + j / 3].row = i;
            params[i / 3 * 3 + j / 3].col = j;
            pthread_create(&threads[i / 3 * 3 + j / 3 + 2 * N], NULL, checkSubgrid, &params[i / 3 * 3 + j / 3]);
        }
    }

    for (int i = 0; i < 11; ++i) {
        pthread_join(threads[i], NULL);
    }

    int isValid = 1;
    for (int i = 0; i < 11 && isValid; ++i) {
        if (!results[i]) {
            isValid = 0;
        }
    }
    printf("The Sudoku solution is %s.\n", isValid ? "valid" : "invalid");

    return 0;
}

第二部分：多线程排序应用

设计思路

1. 分割数据：将原始数组分为两部分。
2. 创建排序线程：创建两个线程分别对两部分数据进行排序。
3. 创建合并线程：创建一个线程用于合并两个已排序的部分。
4. 结果输出：排序完成后，由主程序输出排序结果。

实现代码

#include 
#include 
#include 

#define SIZE 1000

int originalArray[SIZE];
int sortedArray[SIZE];

void* sortThread(void* arg) {
    int* range = (int*)arg;
    int start = range[0];
    int end = range[1];
    for (int i = start; i < end; ++i) {
        for (int j = i + 1; j < end; ++j) { if (originalArray[i] > originalArray[j]) {
                int temp = originalArray[i];
                originalArray[i] = originalArray[j];
                originalArray[j] = temp;
            }
        }
    }
    pthread_exit(NULL);
}

void* mergeThread(void* arg) {
    int left = 0, mid = SIZE / 2, right = SIZE;
    int i = left, j = mid, k = 0;

    while (i < mid && j < right) {
        if (originalArray[i] <= originalArray[j]) {
            sortedArray[k++] = originalArray[i++];
        }
        else {
            sortedArray[k++] = originalArray[j++];
        }
    }

    while (i < mid) {
        sortedArray[k++] = originalArray[i++];
    }

    while (j < right) {
        sortedArray[k++] = originalArray[j++];
    }

    pthread_exit(NULL);
}

int main() {
    pthread_t threads[3];
    int ranges[2][2] = { {0, SIZE / 2}, {SIZE / 2, SIZE} };

    // 初始化数组
    for (int i = 0; i < SIZE; ++i) {
        originalArray[i] = rand() % 1000;
    }

    // 创建排序线程
    for (int i = 0; i < 2; ++i) {
        pthread_create(&threads[i], NULL, sortThread, &ranges[i]);
    }

    // 创建合并线程
    pthread_create(&threads[2], NULL, mergeThread, NULL);

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

    // 输出排序结果
    for (int i = 0; i < SIZE; ++i) {
        printf("%d ", sortedArray[i]);
    }
    printf("\n");

    return 0;
}

实验结果

数独解决方案验证器

运行结果：数独解决方案有效。

结果分析：程序成功创建了11个线程，分别检查数独的行、列和小方格。所有线程的结果都正确地传递回父线程，最终判断数独解决方案有效。

多线程排序应用

运行结果：数组成功排序。

结果分析：程序成功创建了3个线程，两个线程分别对数组的前半部分和后半部分进行排序，另一个线程将两个已排序的部分合并。最终输出的数组是有序的。

遇到的问题及解决方案

线程同步问题：在多线程环境中，需要确保线程之间的同步，避免数据竞争。通过使用 pthread_join 函数等待所有线程完成，确保结果的正确性。

内存管理问题：在传递参数时，需要注意内存的分配和释放，避免内存泄漏。使用 malloc 分配内存，并在不再需要时使用 free 释放内存。

总结

通过本次实验，我对多线程编程有了更深入的理解，掌握了创建和管理多线程程序的方法。实验过程中遇到的一些问题也得到了解决，进一步巩固了我的编程技能。未来将继续探索多线程编程在实际应用中的更多可能性。