实验题目

Project 2——多线程排序应用
编写一个多线程排序程序，其工作方式如下：一个整数列表被分成两个大小相等的较小列表。两个单独的线程（我们将其称为 sorting threads）使用您选择的排序算法对每个子列表进行排序。这两个子列表随后由第三个线程——a merging thread——它将两个子列表合并为一个排序列表。

相关原理与知识

  • 线程的概念

    ⼀个线程就是⼀个“执行流”.每个线程之间都可以按照顺序执行自己的代码多个线程之间“同时”执行着多份代码，main()⼀般被称为主线程（Main Thread）。

  • 多线程的优点和使用场景
    多线程程序在提高计算机系统的并发性和响应性方面有着极其重要的作用。它可以更好地利用计算机的多核和多处理器资源，在提高系统吞吐量的同时缩短响应时间。常见的使用场景包括：

    • 程序需要用户交互并保持响应性
    • 后台任务需要异步完成
    • 大量计算密集型任务需要加速
    • 线程的生命周期
  • 多线程程序的生命周期包括：
    • 创建线程
    • 运行线程
    • 线程流程控制
    • 等待其他线程完成
    • 销毁线程
  • pthread库相关函数
    • pthread_create线程创建
    • pthread_exit线程退出
    • pthread_join线程回收
    • pthread_detach线程分离
    • pthread_cancel线程取消

实验过程

（1）主要实现步骤

  1. 分割列表
    将输入的整数列表平均分成两个子列表。如果列表长度为奇数，可以将其中一个子列表多一个元素。
  2. 创建排序线程
    创建两个线程，分别负责对两个子列表进行排序。选择使用快速排序算法。
  3. 启动排序线程
    启动这两个线程，让它们并行地对子列表进行排序。
  4. 合并已排序的子列表
    创建一个合并线程，等待两个排序线程完成。合并线程将两个已排序的子列表合并为一个完整的排序列表。
  5. 输出结果
    将合并后的排序列表输出。

（2）引入相关库，初始变量
引入库，该库包含了多线程编程所需的函数和定义。
声明全局变量和常量分别表示列表地址、列表长度和线程数量。

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
 
// 定义线程数量 
#define NUM_THREADS 3 
 
// 全局变量：子列表和合并后的列表 
int *left, *right, *merged;
int left_size, right_size, merged_size;

（3）定义排序函数(Quick Sort)
定义一个递归函数，用于对数组arr中从索引low到high的部分进行排序。
(Quick Sorts算法的实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 排序函数（使用快速排序）
void quick_sort(int *arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        int pi = i + 1;
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

（4）定义排序线程函数
sort_thread 函数的主要功能是在新线程中对输入的子列表进行快速排序。它接收一个指向整数数组的指针作为参数，根据该指针来确定子列表的大小，然后调用快速排序算法对子列表进行排序，最后通过 pthread_exit 正常结束线程。

1
2
3
4
5
6
7
// 排序线程函数 
void *sort_thread(void *arg) {
    int *sub_list = (int *)arg;
    int size = (sub_list == left) ? left_size : right_size;
    quick_sort(sub_list, 0, size - 1);
    pthread_exit(NULL);
}

（5）定义合并线程函数
这段代码的主要功能是合并两个已排序的子列表（left和right），并将它们合并成一个有序的列表（merged）。通过使用两个循环，首先比较两个子列表中的元素并按顺序合并，然后处理任何一个子列表中可能剩下的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 合并线程函数 
void *merge_thread(void *arg) {
    int i = 0, j = 0, k = 0;
    while (i < left_size && j < right_size) {
        if (left[i] < right[j]) {
            merged[k++] = left[i++];
        } else {
            merged[k++] = right[j++];
        }
    }
    while (i < left_size) {
        merged[k++] = left[i++];
    }
    while (j < right_size) {
        merged[k++] = right[j++];
    }
    pthread_exit(NULL);
}

（6）主函数的定义
主函数的功能是对一个整数数组进行排序和合并操作。通过使用多线程技术，程序将数组分割为两个子数组，并同时对这两个子数组进行排序，最后合并排序后的子数组以获得最终的排序结果。
pthread_create(&threads[0], NULL, sort_thread, (void )left);：创建第一个线程，传入sort_thread函数作为线程执行的函数，并将left数组作为参数传入。
pthread_create(&threads[1], NULL, sort_thread, (void )right);：创建第二个线程，同样使用sort_thread函数，但传入right数组。
在创建排序线程后，使用pthread_join函数等待这两个线程完成排序任务。
pthread_create(&threads[2], NULL, merge_thread, NULL);：创建第三个线程，传入merge_thread函数作为线程执行的函数，合并这两个已排序的子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int main() {
    // 示例输入列表 
    int input_list[] = {34, 7, 23, 32, 5, 62, 31, 25, 12, 22};
    int input_size = sizeof(input_list) / sizeof(input_list[0]);
 
    // 分割列表 
    left_size = input_size / 2;
    right_size = input_size - left_size;
    left = (int *)malloc(left_size * sizeof(int));
    right = (int *)malloc(right_size * sizeof(int));
    for (int i = 0; i < left_size; i++) {
        left[i] = input_list[i];
    }
    for (int i = 0; i < right_size; i++) {
        right[i] = input_list[left_size + i];
    }
 
    // 创建合并后的列表 
    merged_size = input_size;
    merged = (int *)malloc(merged_size * sizeof(int));
 
    // 创建线程 
    pthread_t threads[NUM_THREADS];
    pthread_create(&threads[0], NULL, sort_thread, (void *)left);
    pthread_create(&threads[1], NULL, sort_thread, (void *)right);
    pthread_join(threads[0], NULL);
    pthread_join(threads[1], NULL);
    pthread_create(&threads[2], NULL, merge_thread, NULL);
    pthread_join(threads[2], NULL);
 
    // 输出结果 
    printf("原始列表: ");
    for (int i = 0; i < input_size; i++) {
        printf("%d ", input_list[i]);
    }
    printf("\n排序后的列表: ");
    for (int i = 0; i < merged_size; i++) {
        printf("%d ", merged[i]);
    }
    printf("\n");
 
    // 释放内存 
    free(left);
    free(right);
    free(merged);
 
    return 0;
}

实验结果与分析

在Ubuntu20.04系统下编译并运行该程序，可以正确对原始列表进行排序。
实验结果

问题总结

问题：使用gcc编译时无法找到pthread库的相关函数(gcc -o project3 project3.c )。
方案：在使用gcc编译时链接到lpthread库(gcc -o project3 project3.c -lpthread)。

六、源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
 
// 定义线程数量 
#define NUM_THREADS 3 
 
// 全局变量：子列表和合并后的列表 
int *left, *right, *merged;
int left_size, right_size, merged_size;
 
// 排序函数（使用快速排序）
void quick_sort(int *arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        int pi = i + 1;
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}
 
// 排序线程函数 
void *sort_thread(void *arg) {
    int *sub_list = (int *)arg;
    int size = (sub_list == left) ? left_size : right_size;
    quick_sort(sub_list, 0, size - 1);
    pthread_exit(NULL);
}
 
// 合并线程函数 
void *merge_thread(void *arg) {
    int i = 0, j = 0, k = 0;
    while (i < left_size && j < right_size) {
        if (left[i] < right[j]) {
            merged[k++] = left[i++];
        } else {
            merged[k++] = right[j++];
        }
    }
    while (i < left_size) {
        merged[k++] = left[i++];
    }
    while (j < right_size) {
        merged[k++] = right[j++];
    }
    pthread_exit(NULL);
}
 
int main() {
    // 示例输入列表 
    int input_list[] = {34, 7, 23, 32, 5, 62, 31, 25, 12, 22};
    int input_size = sizeof(input_list) / sizeof(input_list[0]);
 
    // 分割列表 
    left_size = input_size / 2;
    right_size = input_size - left_size;
    left = (int *)malloc(left_size * sizeof(int));
    right = (int *)malloc(right_size * sizeof(int));
    for (int i = 0; i < left_size; i++) {
        left[i] = input_list[i];
    }
    for (int i = 0; i < right_size; i++) {
        right[i] = input_list[left_size + i];
    }
 
    // 创建合并后的列表 
    merged_size = input_size;
    merged = (int *)malloc(merged_size * sizeof(int));
 
    // 创建线程 
    pthread_t threads[NUM_THREADS];
    pthread_create(&threads[0], NULL, sort_thread, (void *)left);
    pthread_create(&threads[1], NULL, sort_thread, (void *)right);
    pthread_join(threads[0], NULL);
    pthread_join(threads[1], NULL);
    pthread_create(&threads[2], NULL, merge_thread, NULL);
    pthread_join(threads[2], NULL);
 
    // 输出结果 
    printf("原始列表: ");
    for (int i = 0; i < input_size; i++) {
        printf("%d ", input_list[i]);
    }
    printf("\n排序后的列表: ");
    for (int i = 0; i < merged_size; i++) {
        printf("%d ", merged[i]);
    }
    printf("\n");
 
    // 释放内存 
    free(left);
    free(right);
    free(merged);
 
    return 0;
}