一、知识点归纳

1. 并发计算导论

在早期，大多数计算机只有一个处理组件，称为处理器或中央处理器（CPU）。受这种硬件条件的限制，计算机程序通常是为串行计算编写的。要求解某个问题，先要设计一种算法，描述如何一步步地解决问题，然后用计算机程序以串行指令流的形式实现该算法。在只有一个CPU的情况下，每次只能按顺序执行某算法的一个指令和步骤。但是，基于分治原则（如二叉树查找和快速排序等）的算法经常表现出高度的并行性，可通过使用并行或并发执行来提高计算速度。并行计算是一种计算方案，它尝试使用多个执行并行算法的处理器更快速地解决问题。过去，由于并行计算对计算资源的大量需求，普通程序员很少能进行并行计算。近年来，随着多核处理器的出现，大多数操作系统（如Linux）都支持对称多处理（SMP）。甚至对于普通程序员来说，并行计算也已经成为现实。显然，计算的未来发展方向是并行计算。

1.1顺序算法与并行算法

在描述顺序算法时，常用的方法是用一个begin-end代码块列出算法。begin-end代码块中的顺序算法可能包含多个步骤。所有步骤都是通过单个任务依次执行的，每次执行一个步骤。当所有步骤执行完成时，算法结束。

相反，并行算法的描述使用cobegin-coend代码块来指定并行算法的独立任务。在cobegin-coend块中，所有任务都是并行执行的，紧接着cobegin-coend代码块的下一个步骤将只在所有这些任务完成之后执行。

1.2并行性与并发性

通常，并行算法只识别可并行执行的任务，但是它没有规定如何将任务映射到处理组件。在理想情况下，并行算法中的所有任务都应该同时实时执行。然而，真正的并行执行只能在有多个处理组件的系统中实现，比如多处理器或多核系统。在单CPU系统中，一次只能执行一个任务。在这种情况下，不同的任务只能并发执行，即在逻辑上并行执行。在单CPU系统中，并发性是通过多任务处理来实现的。

2. 线程

2.1线程的原理

一个操作系统（OS）包含许多并发进程。在进程模型中，进程是独立的执行单元。所有进程均在内核模式或用户模式下执行。在内核模式下，各进程在唯一地址空间上执行，与其他进程是分开的。虽然每个进程都是一个独立的单元，但是它只有一个执行路径。当某进程必须等待某事件时，例如I/O完成事件，它就会暂停，整个进程会停止执行。线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时，就会执行该进程的主线程。如果只有一个主线程，那么进程和线程实际上并没有区别。但是，主线程可能会创建其他线程。每个线程又可以创建更多的线程等。某进程的所有线程都在该进程的相同地址空间中执行，但每个线程都是一个独立的执行单元。在线程模型中，如果一个线程被挂起，其他线程可以继续执行。除了共享共同的地址空间之外，线程还共享进程的许多其他资源，如用户id、打开的文件描述符和信号等。打个简单的比方，进程是一个有房屋管理员（主线程）的房子，线程是住在进程房子里的人。房子里的每个人都可以独立做自己的事情，但是他们会共用一些公用设施，比如同一个信箱、厨房和浴室等。过去，大多数计算机供应商都是在自己的专有操作系统中支持线程。不同系统之间的实现有极大的区别。目前，几乎所有的操作系统都支持Pthread，它是IEEE POSIX 1003.1c的线程标准（POSIX 1995）。

2.2线程的优点

线程创建和切换速度更快
线程的响应速度更快
线程更适合并行计算

2.3线程的缺点

由于地址空间共享，线程需要来自用户的明确同步。
许多库函数可能对线程不安全，例如传统的strtok()函数将一个字符串分成一连串令牌。通常，任何使用全局变量或依赖于静态内存内容的函数都是线程不安全的。为了使库函数适应线程环境，还需要做大量的工作。
在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢，这是由于在运行时创建线程和切换上下文的系统开销造成的。

3. 线程操作

线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行。在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。线程是独立的执行单元，可根据操作系统内核的调度策略，对内核进行系统调用，变为挂起、激活以继续执行等。为了利用线程的共享地址空间，操作系统内核的调度策略可能会优先选择同一进程中的线程，而不是不同进程中的线程。

4. 线程管理函数

Pthread库提供了用于线程管理的以下API：

pthread_create(thread, attr, function, arg): 创建线程
pthread_exit(status): 终止线程
pthread_cancel(thread): 取消线程
pthread_attr_init(attr): 初始化线程属性
pthread_attr_destroy(attr): 销毁线程属性

4.1创建线程

使用pthread_create()函数创建线程：

int pthread_create(pthread_t *pthread_id, pthread_attr_t *attr, void *(*func)(void *), void *arg);

如果成功则返回0，如果失败则返回错误代码。pthread_create()函数的参数为：

pthread_id是指向pthread_t类型变量的指针，用于存储线程的ID。
attr是指向线程属性的指针，可以为NULL表示使用默认属性。
func是要执行的新线程函数的入口地址。
arg是指向线程函数参数的指针。

线程属性参数attr最复杂，可以使用pthread_attr_init()函数进行初始化，并设置属性，最后通过pthread_attr_destroy()函数释放资源。通常情况下，可以使用NULL作为属性参数，以使用默认属性。

4.2线程ID

线程ID是一种不透明的数据类型，取决于实现情况，因此不应该直接比较线程ID。如果需要比较线程ID，可以使用pthread_equal()函数进行比较：

int pthread_equal(pthread_t t1, pthread_t t2);

如果是不同的线程，则返回0，否则返回非0。

4.3线程终止

线程函数结束后，线程即终止，或者线程可以调用pthread_exit()函数进行显式终止，其中状态是线程的退出状态。通常，0表示正常终止，非0值表示异常终止。

4.4线程连接

一个线程可以等待另一个线程的终止，通过pthread_join()函数进行连接，同时终止线程的退出状态以status_ptr返回。

5. 线程同步

由于线程在进程的同一地址空间中执行，它们共享同一地址空间中的所有全局变量和数据结构。当多个线程试图修改同一共享变量或数据结构时，如果修改结果取决于线程的执行顺序，则称之为竞态条件。在并发程序中，绝不能有竞态条件，否则结果可能不一致。除了连接操作之外，并发执行的线程通常需要相互协作。为了防止出现竞态条件并且支持线程协作，线程需要同步。通常，同步是一种机制和规则，用于确保共享数据对象的完整性和并发执行实体的协调性。它可以应用于内核模式下的进程，也可以应用于用户模式下的线程。