2021-2022-1-diocs-并发编程（学习笔记7）

思维导图

知识归纳

本章论述了并发编程，介绍了并行计算的概念。指出了并行计算的重要性∶比较了顺序算法与并行算法，以及并行性与并发性；解释了线程的原理及其相对于进程的优势；介绍了Pthread中的线程操作，包括线程管理函数，互斥量、连接、条件变量和屏障等线程同步工具；解释了死锁问题，并说明了如何防止并发程序中的死锁问题；讨论了信号量，并论证了它们相对于条件变量的优点；还解释了支持Linux中线程的独特方式。

并行计算基础

在早期，大多数计算机只有一个处理组件，称为处理器或*处理器（CPU）。受这种硬件条件的限制，计算机程序通常是为串行计算编写的。

要求解某个问题，先要设计一种算法，描述如何一步步地解决问题，然后用计算机程序以串行指令流的形式实现该算法。在只有一个CPU的情况下，每次只能按顺序执行某算法的一个指令和步骤。但是，基于分治原则（如二叉树查找和快速排序等）的算法经常表现出高度的并行性，可通过使用并行或并发执行来提高计算速度。并行计算是一种计算方案，它尝试使用多个执行并行算法的处理器更快速地解决问题。

过去，由于并行计算对计算资源的大量需求，普通程序员很少能进行并行计算。近年来，随着多核处理器的出现，大多数操作系统（如Linux）都支持对称多处理（SMP）。甚至对于普通程序员来说，并行计算也已经成为现实。显然，计算的未来发展方向是并行计算。因此，迫切需要在计算机科学和计算机工程专业学生的早期学习阶段引入并行计算。

1. 顺序算法与并行算法
   在描述顺序算法时，常用的方法是用一个begin-end代码块列出算法，如下方所示。

---       顺序算法      ---|---      并行算法       ---
       begin              |         cobegin
         step_1           |           task_1
         step_2           |           task_2
         ...              |           ...
         step_n           |           task_n
       end                |         coend
       //next step        |         //next step
-----------------------------------------------------

begin-end代码块中的顺序算法可能包含多个步骤。所有步骤都是通过单个任务依次执行的，每次执行一个步骤。当所有步骤执行完成时，算法结束。相反，并行算法使用cobegin-coend代码块来指定并行算法的独立任务。在cobegin-coend块中，所有任务都是并行执行的。紧接着cobegin-coend代码块的下一个步骤将只在所有这些任务完成之后执行。

并行性与并发性

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

线程基本特点

1. 线程的原理
   一个操作系统（OS）包含许多并发进程。

在进程模型中，进程是独立的执行单元。

所有进程均在内核模式或用户模式下执行。在内核模式下，各进程在唯一地址空间上执行，与其他进程是分开的。虽然每个进程都是一个独立的单元，但是它只有一个执行路径。

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

目前，几乎所有的操作系统都支持Pthread，它是IEEE POSIX 1003.1c的线程标准（POSIX1995）。如需了解更多信息，读者可查阅更多关于Pthread编程的书籍（Buttlar 等1996）和在线文章（Pthreads 2017）。

2. 线程的优点
   与进程相比，线程有许多优点。
   （1）线程创建和切换速度更快∶进程的上下文复杂而庞大。其复杂性主要来自管理进程映像的需要。例如，在具有虚拟内存的系统中。进程映像可能由叫作页面的许多内存单元组成。在执行过程中，有些页面在内存中，有些则不在内存中。操作系统内核必须使用多个页表和多个级别的硬件辅助来跟踪每个进程的页面。要想创建新的进程，操作系统必须为进程分配内存并构建页表。若要在某个进程中创建线程，操作系统不必为新的线程分配内存和创建页表。因为线程与进程共用同一个地址空间。所以创建线程比创建进程更快。
   另外，由于以下原因，线程切换比进程切换更快。进程切换涉及将一个进程的复杂分页环境替换为另一个进程的复杂分页环境，需要大量的操作和时间。相比之下。同一个进程中的线程切换要简单得多、也快得多，因为操作系统内核只需要切换执行点，而不需要更改进程映像。
   （2）线程的响应速度更快：一个进程只有一个执行路径。当某个进程被挂起时、整个进程都将停止执行。相反，当某个线程被挂起时，同一进程中的其他线程可以继续执行。这使得有多个线程的程序响应速度更快。例如，在一个多线程的进程中.当一个线程被阻塞以等待I/O时，其他线程仍可在后台进行计算。在有线程的服务器中，服务器可同时服务多个客户机。
   （3）线程更适合并行计算∶并行计算的目标是使用多个执行路径更快地解决问题。基于分治原则（如二叉树查找和快速排序等）的算法经常表现出高度的并行性。可通过使用并行或并发执行来提高计算速度。这种算法通常要求执行实体共享公用数据。在进程模型中，各进程不能有效共享数据，因为它们的地址空间都不一样。为了解决这个问题，进程必须使用进程间通信（IPC）来交换数据或使用其他方法将公用数据区包含到其地址空间中。相反. 同一进程中的所有线程共享同一地址空间中的所有（全局）数据。因此，使用线程编写并行执行的程序比使用进程编写更简单、更自然。
3. 线程的缺点
   （1）由于地址空间共享，线程需要来自用户的明确同步。
   （2）许多库函数可能对线程不安全，例如传统 strtok()函数将一个字符串分成一连串令牌。通常，任何使用全局变量或依赖于静态内存内容的函数，线程都不安全。为了使库函数适应线程环境，还需要做大量的工作。
   （3）在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢，这是由在运行时创建线程和切换上下文的系统开销造成的。

线程操作

线程的执行轨迹与进程类似。

线程可在内核模式或用户模式下执行。
在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。线程是独立的执行单元，可根据操作系统内核的调度策略，对内核进行系统调用，变为挂起、激活以继续执行等。

为了利用线程的共享地址空间，操作系统内核的调度策略可能会优先选择同一进程中的线程，而不是不同进程中的线程。

截至目前，几乎所有的操作系统都支持 POSIX Pthread，定义了一系列标准应用程序编程接口（API）来支持线程编程。

线程管理函数

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填充。在POSIX中，pthread_t是一种不透明的类型。程序员应该不知道不透明对象的内容，因为它可能取决于实现情况。线程可通过pthread_self()函数获得自己的ID。在 Linux 中，pthread_t类型被定义为无符号长整型，因此线程ID可以打印为%lu。
• attr是指向另一种不透明数据类型的指针，它指定线程属性，下面将对此进行更详细的说明。
• func是要执行的新线程函数的入口地址。 arg是指向线程函数参数的指针，可写为:void *func(void *arg)
• attr参数
  (1)定义一个pthread属性变量pthread_attr_t attr。
  (2)用pthread_attr_init (&attr)初始化属性变量。
  (3)设置属性变量并在pthread_create()调用中使用。
  (4)必要时，通过pthread_attr_destroy (&attr)释放attr资源。

2. 线程ID
   线程ID是一种不透明的数据类型，取决于实现情况。因此，不应该直接比较线程ID。如果需要,可以使用
   pthread_equal()函数对它们进行比较。
   int pthread_equal (pthread_t t1, pthread_t t2);
   如果是不同的线程，则返回0，否则返回非0。

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

4. 线程连接
   一个线程可以等待另一个线程的终止,通过:
   int pthread_join (pthread_t thread, void **status ptr);终止线程的退出状态以status_ptr返回。

实践过程

实践过程代码均已上传到我的码云仓库

1. 用线程快速排序
   
   在Windows10上可以正常运行，
   
   但在OpenEuler下显示错误
   
   查找有关解决方案，在尝试了几篇博客的做法后发现这篇博客的方法是最有效的Linux下undefined reference to ‘pthread_create’问题解决
   即在gcc编译的时候，附加要加 -lpthread参数即可解决
   
   运行结果
   

2. 生产者-消费者问题