并行计算导论
受硬件条件的限制，计算机程序通常是为串行计算编写的。
顺序算法与并行算法
-
begin-end 代码块中顺序算法可能包含多个步骤，所有步骤都是通过单个任务依次执行的，每次执行一个步骤。
-
所有步骤执行完成，算法结束。
-
右侧为并行算法描述，使用cobegin-coend代码块指定并行算法的独立任务。在该块中，所有任务并行执行。
并行性与并发性
通常，并行算法只识别可并行执行的任务，但是它没有规定如何将任务映射到处理组件。在理想情况下，并行算法中的所有任务都应该同时实时执行。然而，真正的并行执行只能在有多个处理组件的系统中实现，比如多处理器或多核系统。在单 CPU 系统中，一次只能执行一个任务。在这种情况下，不同的任务只能并发执行、即在逻辑上并行执行。在单CPU系统中，并发性是通过多任务处理来实现的。
线程
线程的原理
线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。 线程是独立调度和分派的基本单位。线程可以为操作系统内核调度的内核线程 同一进程中的多条线程将共享该进程中的全部系统资源，如虚拟地址空间，文件描述符和信号处理等等。 一个进程可以有很多线程，每条线程并行执行不同的任务。 使用多线程程序设计的好处是显而易见，即提高了程序的执行吞吐率。在单CPU单核的计算机上，使用多线程技术，也可以把进程中负责I/O处理、人机交互而常被阻塞的部分与密集计算的部分分开来执行，编写专门的workhorse线程执行密集计算，从而提高了程序的执行效率。
线程的优点
与进程相比，线程有许多优点。
-
线程创建和切换速度更快∶进程的上下文复杂而庞大。其复杂性主要来自管理进程映像的需要。例如，在具有虚拟内存的系统中。进程映像可能由叫作页面的许多内存单元组成。在执行过程中，有些页面在内存中，有些则不在内存中。操作系统内核必须使用多个页表和多个级别的硬件辅助来跟踪每个进程的页面。要想创建新的进程，操作系统必须为进程分配内存并构建页表。若要在某个进程中创建线程，操作系统不必为新的线程分配内存和创建页表。因为线程与进程共用同一个地址空间。所以创建线程比创建进程更快。 另外，由于以下原因，线程切换比进程切换更快。进程切换涉及将一个进程的复杂分页环境替换为另一个进程的复杂分页环境，需要大量的操作和时间。相比之下。同一个进程中的线程切换要简单得多、也快得多，因为操作系统内核只需要切换执行点，而不需要更改进程映像。
-
线程的响应速度更快：一个进程只有一个执行路径。当某个进程被挂起时、整个进程都将停止执行。相反，当某个线程被挂起时，同一进程中的其他线程可以继续执行。这使得有多个线程的程序响应速度更快。例如，在一个多线程的进程中.当一个线程被阻塞以等待I/O时，其他线程仍可在后台进行计算。在有线程的服务器中，服务器可同时服务多个客户机。
-
线程更适合并行计算∶并行计算的目标是使用多个执行路径更快地解决问题。基于分治原则（如二叉树查找和快速排序等）的算法经常表现出高度的并行性。可通过使用并行或并发执行来提高计算速度。这种算法通常要求执行实体共享公用数据。在进程模型中，各进程不能有效共享数据，因为它们的地址空间都不一样。为了解决这个问题，进程必须使用进程间通信（IPC）来交换数据或使用其他方法将公用数据区包含到其地址空间中。相反. 同一进程中的所有线程共享同一地址空间中的所有（全局）数据。因此，使用线程编写并行执行的程序比使用进程编写更简单、更自然。
线程的缺点
-
由于地址空间共享，线程需要来自用户的明确同步。
-
许多库函数可能对线程不安全，例如传统 strtok()函数将一个字符串分成一连串令牌。通常，任何使用全局变量或依赖于静态内存内容的函数，线程都不安全。为了使库函数适应线程环境，还需要做大量的工作。
-
在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢，这是由在运行时创建线程和切换上下文的系统开销造成的。
线程管理函数
Pthread库提供了用于线程管理的以下API：
pthread_create(thread,attr,function,arg):create thread
pthread_exit(status) :terminate thread
pthread_cancel(thread) ：initialize thread attributes
pthread_attr_destroy(attr) destroy thread attribute
创建新线程
#include <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,void *(*start_routine) (void *), void *arg);
线程终止
void pthread_exit(void *retval);
等待线程结束
int pthread_join(pthread_t thread, void **retval);
返回线程ID
pthread_t pthread_self(void);
取消一个线程
int pthread_cancel(pthread_t thread);
将一个线程从进程中分离
int pthread_detach(pthread_t thread);
线程同步
由于线程在进程的同一地址空间中执行 它们共享同一地址空间中的所有全局变量和数据结构。当多个线程试图修改同一共享变量或数据结构时，如果修改结果取决于线程的执行顺序，则称之为竞态条件。在并发程序中，绝不能有竞态条件。否则，结果可能不一致。除了连接操作之外，并发执行的线程通常需要相互协作。为了防止出现竞态条件并且支持线程协作，线程需要同步。通常，同步是一种机制和规则，用于确保共享数据对象的完整性和并发执行实体的协调性。它可以应用于内核模式下的进程，也可以应用于用户模式下的线程。
互斥量
同步工具是锁，它允许执行实体仅在有锁的情况下才能执行。锁被称为互斥量，意思是相互排斥。 互斥变量是用pthread_mutex_t类型声明的，在使用之前必须进行初始化。
-
静态方法：
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;定义互斥量m，并使用默认属性对其进行初始化。 -
动态方法:
pthread_mutex_init(pthread_mutex_t *m,pthread_mutexattr_t,*attr);通常attr参数可以设置位NULL，作为默认属性。 初始化完成后，线程可以通过以下函数使用互斥量。
int pthread_mutex_lock(pthread_mutex_t *m);
int pthread_mutex_unlock(pthread_mutex_t *m);
int pthread_mutex_trylock(pthread_mutex_t *m);
int pthread_mutex_destory(pthread_mutex_t *m);
线程使用互斥量来保护共享数据对象。
死锁预防
-
互斥量使用封锁协议。有多种方法可以解决可能的死锁问题，其中包括死锁防御、死锁规避、死锁检测和回复等。在实际情况中，唯一可行的方法时死锁预防，试图在设计并行算法是防止死锁发生。
-
一种简单的死锁预防时对互斥量进行排序，并确保每个线程只在一个方向请求互斥量，这样请求序列中就不会有循环。
-
条件加锁和退避预防死锁
while(1){
lock(m1);
if(!trylock(m2))
unlock(m1);
else
break;
}
条件变量
作为锁，互斥量仅用于确保线程只能互斥地访问临界区中的共享数据对象。条件变量提供了一种线程协作的方法。在Pthread中，使用othread_cond_t来声明条件变量，而且必须在使用前进行初始化。
-
静态方法
pthread_cond_t con = PTHREAD_COND_INITALLIZER; -
动态方法 使用pthread_cond_init()函数，通过attr参数设置条件变量。
信号量
信号量是进程同步的一般机制。（计数）信号量是一种数据结构。
struct sem{
int value;
struct process *queue
}s;
最有名的信号量操作时P和V
屏障
线程连接操作允许某线程（通常是主线程）等待其他线程终止。在某些情况下，保持线程活动会更好，但应要求他们在所有线程都达到指定同步点之前不能继续活动。在Pthreads中，可以采用屏障以及一系列屏障函数。 首先，主线程创建一个屏障对象 pthread_barrier_init(&barrier NULL,nthreads); 用屏蔽中同步线程数字对他进行初始化。然后，主线程创建工作线程来执行任务。
创建屏障步骤 ①主线程创建一个屏障对象pthread_barrier_t barrier; ②调用pthread_barrier_init(&barrier NULL, nthreads)；,用屏障中同步的线程数字对它进行初始化 ③工作线程使用pthread_barrier_wait(&barrier)在屏障中等待指定数量的线程到达屏障
Linux中的线程
与许多其他操作系统不同，Linux不区分进程和线程。对于Linux内核，线程只是一个 与其他进程共享某些资源的进程。在Linux中，进程和线程都是由clone()系统调用创建的
实践环节
用并发线程快速排序：
源代码
#include <stdio.h>