第四章总结
并行计算导论
要求解某个问题,先要设计一种算法,描述如何一步步地解决问题,然后用计算机程序以串行指令流的形式实现该算法。在只有一个 CPU的情况下,每次只能按顺序执行某算法的一个指令和步骤。但是,基于分治原则(如二又树查找和快速排序等)的算法经常表现出高度的并行性,可通过使用并行或并发执行来提高计算速度。并行计算是一种计算方案,它尝试使用多个执行并行算法的处理器更快速地解决问题。
- 顺序算法与并行算法
描述顺序算法,常用的方法是用一个begin-end代码块列出算法;并行算法使用cobegin-coend代码块来指定并行算法的独立任务。如下图所示:
- 并行性与并发性
- 在理想情况下,并行算法中的所有任务都应该同时实时执行。
- 真正的并行执行只能在有多个处理组件的系统中实现,比如多处理器或多核系统。
- 在单CPU系统中,一次只能执行一个任务。在这种情况下,不同的任务只能并发执行,即在逻辑上并行执行。
线程
- 线程的原理
- 线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时,就会执行该进程的主线程。
- 线程的优点
- 线程创建和切换速度更快
- 线程的响应速度更快
- 线程更适合并行运算
- 线程的缺点
- 由于地址空间共享,线程需要来自用户的明确同步。
- 许多库函数可能对线程不安全。通常,任何使用全局变量或依赖于静态内存内容的函数,线程都不安全。
- 在单CPU系统上,使用线程解决问题实际上要比使用顺序程序慢。
线程操作
- 线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行。在用户模式下,线程在进程的相同地址空间中执行,但每个线程都有自己的执行堆栈。
线程管理函数
-
创建线程
- 使用pthread_create()
int pthread_create(pthread_t *pthread_id,pthread_attr_t *attr,void *(*func)(void*),void *arg)
- attr 参数的使用步骤。
- 定义一个pthread属性变量pthread attr tattr。
- 用pthread attrinit (&attr)初始化属性变量。
- 设置属性变量并在pthread create0)调用中使用。
- 必要时,通过pthread attr destroy (&attr)释放attr 资源。
- 使用pthread_create()
-
线程ID
int pthread_equal(pthread_t t1,pthread_t t2);
如果是不同的线程,返回0,否则返回非0 -
线程终止
int pthread_exit(void *status);
进行显式终止,其中状态是线程的退出状态。 -
线程连接
int pthread_join(pthread_t thread,void **status_ptr)
终止线程的退出状态以status_ptr返回。
线程示例程序
- 实践1:用线程计算矩阵的和
#include <stdio.h>
#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();
row = (int)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);
}
int main (int argc, char *argv[])
{
pthread_t thread[N];
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);
}
- 实践2:用线程快速排序
#include <stdio.h>
#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();
row = (int)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);
}
int main (int argc, char *argv[])
{
pthread_t thread[N];
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);
}
线程同步
多个线程试图修改同一共享变量或数据结构时,如果修改结果取决于线程的执行顺序,则称之为竞态条件。在并发程序中,绝不能有竞态条件。否则,结果可能不一致。
- 互斥量
- 最简单的同步工具是锁,它允许执行实体仅在有锁的情况下才能继续执行。在 Pthread中,锁被称为互斥量,意思是相互排斥。
- 静态方法
- 动态方法
- 死锁预防
- 互斥量使用封锁协议。
- 在任何封锁协议中,误用加锁可能会产生一些问题。
- 死锁是一个状态,在这种状态下,许多执行实体相互等待,无法继续进行下去
- 条件变量
- 静态方法
- 动态方法
- 生产者-消费者问题
共享全局变量:
int buf[NBUF];
int head,tail;
int data;
- 信号量
- 信号量是进程同步的一般机制。
- 在使用信号量之前,必须使用一个初始值和一个空等待队列进行初始化。
- 屏障
- 在 Pthreads中,可以采用的机制是屏障以及一系列屏障函数。
- 用并发线程解线性方程组
- Linux中的线程
- Linux不区分进程和线程。
- 对于Linux内核,线程只是一个与其他进程共享某些资源的进程。
- 在 Linux 中,进程和线程都是由 clone()系统调用创建的:
int clone(int (*fn)(void*),void *child_stack,int flags,void *arg)
苏格拉底挑战
- 关于线程的苏格拉底挑战
- 关于线程同步的苏格拉底挑战
遇到的问题
什么时候适合死锁?