并行计算导论
顺序算法与并行算法
并行性与并发性
- 通常,并行算法只识别可并行执行的任务,但是它没有规定如何将任务映射到处理组件。在理想情况下,并行算法中的所有任务都应该同时实时执行
- CPU系统中,并发性是通过多任务处理来实现的
线程
线程的原理
- 线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线程并行执行不同的任务。
线程的优点
- 线程创建和切换速度更快
- 库函数不安全
- 单CPU系统中,线程解决问题实际上要比使用顺序程序慢
线程的缺点
- 由于地址空间共享,线程需要来自用户的明确同步
- 许多库函数可能对线程不安全,例如传统 strtok()函数将一个字符串分成一连串令牌。通常,任何使用全局变量或依赖于静态内存内容的函数,线程都不安全。为了使库函数适应线程环境,还需要做大量的工作
- 在单CPU系统上,使用线程解决问题实际上要比使用顺序程序慢,这是由在运行时创建线程和切换上下文的系统开销造成的
线程操作
- 线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行
线程管理函数
创建线程
int pthread_create(pthread_t *pthread_id,pthread_attr_t *attr,void *(*func)(void*),void *arg)
线程ID
int pthread_equal(pthread_t t1,pthread_t t2);
线程终止
int pthread_exit(void *status);
线程连接
int pthread_join(pthread_t thread,void **status_ptr)
线程示例程序
- 用线程快速排序
#include <stdlib.h>
#include <pthread.h>
#define N 10
typedef struct{
int upperbound;
int lowerbound;
}PARM;
int A[N]={5,1,6,4,7,2,9,8,0,3};
int print() // print current a[] contents
{
int i;
printf("[ ");
for (i=0; i<N; i++)
{
printf("%d ", A[i]);
}
printf("]\n");
}
void *qsort_1(void *aptr)
{
PARM *ap, aleft, aright;
int pivot, pivotIndex, left, right, temp;
int upperbound, lowerbound;
pthread_t me, leftThread, rightThread;
me = pthread_self();
ap = (PARM *)aptr;
upperbound = ap->upperbound;
lowerbound = ap->lowerbound;
pivot = A[upperbound];
left = lowerbound - 1;
right = upperbound;
if (lowerbound >= upperbound)
pthread_exit(NULL);
while (left < right)
{
do { left++;} while (A[left] < pivot);
do { right--;}while (A[right] > pivot);
if (left < right )
{
temp = A[left];
A[left] = A[right];
A[right] = temp;
}
}
print();
pivotIndex = left;
temp = A[pivotIndex];
A[pivotIndex] = pivot;
A[upperbound] = temp; // start the "recursive threads"
aleft.upperbound = pivotIndex - 1;
aleft.lowerbound = lowerbound;
aright.upperbound = upperbound;
aright.lowerbound = pivotIndex + 1;
printf("%lu: create left and right threads\n", me);
pthread_create(&leftThread, NULL, qsort_1, (void *)&aleft);
pthread_create(&rightThread, NULL, qsort_1, (void *)&aright);// wait for left and right threads
pthread_join(leftThread, NULL);
pthread_join(rightThread, NULL);
printf("%lu: joined with left & right threads\n", me);
}
int main(int argc, char *argv[])
{
PARM arg;
int i, *array;
pthread_t me, thread;
me = pthread_self();
printf("main %lu: unsorted array =" ,me);
print();
arg.upperbound = N-1;
arg.lowerbound = 0;
printf("main %lu create a thread to do QS\n", me);
pthread_create(&thread, NULL, qsort_1, (void *)&arg); // wait for QS thread to finish
pthread_join(thread, NULL);
printf("main %lu sorted array = ", me);
print();
}
线程同步
互斥量
- 最简单的同步工具是锁,它允许执行实体仅在有锁的情况下才能继续执行
死锁预防
- 互斥量使用封锁协议。如果某线程不能获取互斥量,就会被阻塞,等待互斥量解锁后再继续。
条件变量
- 作为锁,互斥量仅用于确保线程只能互斥地访问临界区中的共享数据对象。条件变量提供了一种线程协作的方法。在Pthread中,使用类型pthread_cond_t来声明条件变量,而且必须在使用前进行初始化。
- 条件变量可以通过两种方法进行初始化
- 静态方法
- 动态方法
信号量
- 信号量是进程同步的一般机制
屏障
- 线程连接操作允许某线程等待其他线程终止,在pthread中可以采用的机制是屏障以及一系列屏障函数