第三章 第四章 并发编程
并行计算
并行计算是一种计算方案，它尝试使用多个执行并行算法的处理器更快速的解决问题
顺序算法与并行算法
并行性与并发性
并行算法只识别可并行执行的任务。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：线程同步
我在学习线程同步知识点，请你以苏格拉底的方式对我进行提问，一次一个问题。
- 针对我线程同步知识点，我理解了吗？
- 我的回答结束了，请对我的回答进行评价总结。
-
知识点2：线程管理函数
-
我在学习使用线程管理函数知识点，请你以苏格拉底的方式对我进行提问，一次一个问题。
-
针对我线程管理函数知识点，我理解了吗？
-
我的回答结束了，请对我的回答进行评价总结。
-
问题与解决思路
在学习过程中，我遇到了以下问题，并使用chatgpt等AI工具解决：
- 问题1：多个进程相互等待对方释放资源，导致所有进程都无法继续执行
