并发编程

本章论述了并发编程，介绍了并行计算的概念，指出了并行计算的重要性，比较了顺序算法与并行算法，以及并行性与并发性，解释了线程的原理及相对于进程的优势。通过示例介绍了 Pthread 中的线程操作，句括线程管理函数。互斥量、连接、条件变量和屏障等线程同步工具;通过具体示例演示了如何使用线程进行并发编程，包括矩阵计算、快速排序和用并发线程求解线性方程组等方法;解释了死锁问题，并说明了如何防止并发程序中的死锁问题;讨论了信号量，并论证了它们相对于条件变量的优点;还解释了支持Linux 中线程的独特方式。编程项目是为了实现用户级线程。它提供了一个基础系统来帮助读者开始工作。这个基础系统支持并发任务的动态创建、执行和终止，相当干在某个进程的同一地址空间中执行线程。读者可通过该项目实现线程同步的线程连接、互斥量和信号量，并演示它们在并发程序中的用法。该编程项目会让读者更加深入地了解多任务处理、线程同步和并发编程的原理及方法。

4.1并行计算导论

4.1.1顺序算法与并行算法

begin-end代码块中的顺序算法可能包括多个步骤，每次执行一个步骤；cobegin-end中所有任务并行执行。

4.2.2并行性与并发性

逻辑上并行执行——并发，比如在单核cpu上。真正的并行执行只有在有多处理组件的系统中实现。

4.2线程

4.2.1线程的原理

一个操作系统包含很多并发进程。在进程模型中，进程是独立的执行单元。线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时，就会执行该进程的主线程。如果只有一个主线程，那么进程和线程实际上并没有区别。但是，主线程可能会创建其他线程。每个线程又可以创建更多的线程等。

4.2.2线程的优点

1.线程创建和切换速度更快；
2.线程的相应速度更快；
3.线程更适合并行计算；

4.2.3线程的缺点

（1）由于地址空间共享，线程需要来自用户的明确同步。

（2）许多库函数可能对线程不安全，例如传统 strtok（）函数将一个字符串分成一连串令牌。通常，任何使用全局变量或依赖于静态内存内容的函数，线程都不安全。为了使库函数适应线程环境，还需要做大量的工作。

（3）在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢，这是由在运行时创建线程和切换上下文的系统开销造成的。

4.3线程操作

4.4 线程管理函数

4.4.1 创建线程

使用pthread_creat()函数创建线程

成功则返回0，失败则返回错误代码。

4.4.2线程ID

是一种不透明数据类型，取决于实现情况。使用pthread_equal()函数进行比较。不同线程返回0，否则返回非0

4.4.3线程终止

线程函数结束后，线程即终止。或者，线程可以调用函数

int pthread_equal(void*atatus);

进行显示终止。

4.线程同步

(1)互斥量最简单的同步工具是锁，它允许执行实体仅在有锁的情况下才能继续执行。在Pthread中，锁被称为互斥量。在使用之前必须对他们进行初始化。

静态方法：
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER
定义互斥量m，并使用默认属性对其进行初始化。

动态方法：使用pthread_mutex_init()函数，可通过attr参数设置互斥属性。
pthread_mutex_init(pthread_mutex_t *m,pthread_mutexattr_t,*attr);
(2)死锁预防
互斥量使用封锁协议。如果某线程不能获取互斥量，就会被阻塞，等待互斥量解锁后再继续。在任何封锁协议中，误用加锁可能会产生一些问题。最常见和突出的问题是死锁。

有多种方法可以解决可能的死锁问题，其中包括死锁预防、死锁规避、死锁检测和恢复等。

在实际系统中，唯一可行的方法是死锁预防，试图在设计并行算法时防止死锁的发生。一种简单的死锁预防方法是对互斥量进行排序，并确保每个线程只在一个方向请求互斥量，这样请求序列中就不会有循环。

(3)条件变量
作为锁，互斥量仅用于确保线程只能互斥地访问临界区中的共享数据对象。条件变量提供了一种线程协作的方法。在Pthread中，使用类型pthread_cond_t来声明条件变量，而且必须在使用前进行初始化。

静态方法
pthread_cond_t con = PTHREAD_COND_INITALLIZER；
动态方法
使用pthread_cond_init()函数，通过attr参数设置条件变量。
在互斥量的临界区中，线程可通过以下函数使用条件变量来相互协作。

pthread_cond_wait（conditlon，mutex）：该函数会阻塞调用线程，直到发出指定条件的信号。当互斥量被加锁时、应调用该例程。它会在线程等待时自动释放互斥量。互斥量将在接收到信号并唤醒阻塞的线程后自动锁定。

pthread cond signal（condition）;该函数用来发出信号，即唤醒正在等待条件变量的线程或解除阻塞。它应在互斥量被加锁后调用，而且必须解锁互斥量才能完成pthread_cond_wait ()。

pthread cond broadcast（condition）∶该函数会解除被阻塞在条件变量上的所有线程阻塞。所有未阻塞的线程将争用同一个互斥量来访问条件变量。它们的执行顺序取决于线程调度。

(4)信号量
信号量和条件变量之间的主要区别是，前者包含一个计数器，可操作计数器，测试计数器值以做出决策等，所有这些都是临界区的原子操作或基本操作，而后者需要一个特定的互斥量来执行临界区。在 Pthreads 中，互斥量严格用于封锁。而条件变量可用于线程协作。相反，可以把使用初始值1计算信号量当作锁。带有其他初始值的信号量可用于协作。因此，信号量比条件变量更通用、更灵活。下面的示例说明了信号量相对于条件变量的优势。

(5)屏障
线程连接操作允许某线程（通常是主线程）等待其他线程终止。在等待的所有线程都终止后，主线程可创建新线程来继续执行并行程序的其余部分。创建新线程需要系统开销。在某些情况下，保持线程活动会更好，但应要求它们在所有线程都达到指定同步点之前不能继续活动。

生产者—消费者问题

我们将使用线程和条件变量来实现一个简化版的生产者-消费者问题，也称有限缓冲问题。生产者-消费者问题通常将进程定义为执行实体，可看作当前上下文中的线程。下面是该问题的定义。

一系列生产者和消费者进程共享数量有限的缓冲区。每个缓冲区每次有一个特定的项目。最开始，所有缓冲区都是空的。当一个生产者将一个项目放人一个空缓冲区时，该缓冲区就会变满。当一个消费者从一个满的缓冲区中获取一个项目时，该缓冲区就会变空。如果没有空缓冲区，生产者必须等待。同样，如果没有满缓冲区，则消费者必须等待。此外，当等待事件发生时、必须允许等待进程继续。

代码实践

#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:initize 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 thread\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 toatal sum: ");
for(i=0;i<N;i++)
total+=sum[i];
printf("total =%d\n",total);
pthread_exit(NULL);
}