第三章 第四章 并发编程

并行计算

并行计算是一种计算方案，它尝试使用多个执行并行算法的处理器更快速的解决问题

顺序算法与并行算法

并行性与并发性

并行算法只识别可并行执行的任务。CPU系统中，并发性是通过多任务处理来实现的

线程

线程的原理

某进程同一地址空间上的独立执行单元

线程的优点

• 线程创建和切换速度更快
• 线程的响应速度更快
• 线程更适合并行运算

线程的缺点

• 线程需要来自用户的明确同步
• 库函数不安全
• 单CPU系统中，线程解决问题实际上要比使用顺序程序慢

线程示例程序

用线程计算矩阵的和

#include <stdlib.h>
#include <pthread.h>
#define N 4
int A[N][N], sum[N];
void *func(void *arg)
{
    int j, row;
    pthread_t tid = pthread_self(); // get thread ID number 
    row = (int)arg;	// get row number from arg
    printf("Thread %d [%lu] computes sum of row %d\n", row, tid, row); 
    for (j=0; j<N; j++)
    {
        sum[row] += A[row][j];
    }
    printf("Thread %d [%lu] done sum[%d] = %d\n",row, tid, row, sum[row]);
    pthread_exit((void*)0); // thread exit: 0=normal termination
}

int main (int argc, char *argv[])
{
    pthread_t thread[N];	// thread IDs
    int i, j, r, total = 0;
    void *status;
    printf("Main: initialize A matrix\n");

    for (i=0; i<N; i++)
    {
        sum[i] = 0;
        for (j=0; j<N; j++)
        {
            A[i][j] = i*N + j + 1;
            printf("%4d" ,A[i][j]);
        }
    printf("\n");
    }
    printf("Main: create %d threads\n", N);
    for(i=0; i<N; i++)
    {
        pthread_create(&thread[i], NULL, func, (void *)i);
    }
    printf("Main: try to join with threads\n");
    for(i=0; i<N; i++) 
    {
        pthread_join(thread[i], &status);
        printf("Main: joined with %d [%lu]: status=%d\n",i, thread[i], (int)status);
    }
    printf("Main: compute and print total sum:"); 
    for (i=0; i<N; i++)
    {
        total += sum[i];
    }
    printf("tatal = %d\n", total); 
    pthread_exit(NULL);
}

实践

编程项目：用线程进行快速排序
相关的代码：

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

#define MAX_SIZE 100

void quickSort(int arr[], int left, int right);
void* quickSortThread(void* arg);

void quickSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    int temp = arr[left];
    arr[left] = arr[j];
    arr[j] = temp;
    
    pthread_t threads[2];
    int args1[] = {arr, left, j - 1};
    int args2[] = {arr, j + 1, right};
    pthread_create(&threads[0], NULL, quickSortThread, (void*)args1);
    pthread_create(&threads[1], NULL, quickSortThread, (void*)args2);
    
    pthread_join(threads[0], NULL);
    pthread_join(threads[1], NULL);
}

void* quickSortThread(void* arg) {
    int* args = (int*)arg;
    int* arr = args[0];
    int left = args[1];
    int right = args[2];
    
    quickSort(arr, left, right);
    
    pthread_exit(NULL);
}

int main() {
    int arr[MAX_SIZE];
    int size;
    
    printf("Enter the number of elements: ");
    scanf("%d", &size);
    
    printf("Enter the elements:\n");
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    
    int args[] = {arr, 0, size - 1};
    
    pthread_t sortThread;
    pthread_create(&sortThread, NULL, quickSortThread, (void*)args);
    
    pthread_join(sortThread, NULL);
    
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

运行结果：

苏格拉底挑战

1. 知识点1：线程同步

   我在学习线程同步知识点，请你以苏格拉底的方式对我进行提问，一次一个问题。

 - 针对我线程同步知识点，我理解了吗？

 - 我的回答结束了，请对我的回答进行评价总结。

2. 知识点2：线程管理函数

   • 我在学习使用线程管理函数知识点，请你以苏格拉底的方式对我进行提问，一次一个问题。
     

   • 针对我线程管理函数知识点，我理解了吗？
     

   • 我的回答结束了，请对我的回答进行评价总结。

问题与解决思路

在学习过程中，我遇到了以下问题，并使用chatgpt等AI工具解决：

1. 问题1：多个进程相互等待对方释放资源，导致所有进程都无法继续执行