[数据结构与算法]《并发数据结构与多核编程》“并发”知识整理，复习笔记，建议收藏！

并发的思想和基本知识对于一个从程序员来说很重要，尤其是在当下的大数据、分布式、多处理器的时代。

但是并发这门课学习起来可不轻松，这里整理我学习并发的知识，与大家分享~

欢迎大家关注我的公众号DataFortune，文章包括但不限于人工智能、信号处理、python、图像处理。之后还会发布更多优秀博文，期待你的关注！

第一讲 绪论

并发（Concurrent）计算：多个计算主体（称为进程或线程）同时运行，通过通信进行协作，以共同完成一个给定的计算任务。如果这些计算主体分布在不同的计算机上，通常称为分布式并发计算；如果这些计算主体分布在同一台共享存储多处理器计算机的不同核上，通常称为共享内存式并发计算。
多核计算（Multicore computing）是共享内存式并发计算。多个线程运行在不同的核上，通过共享变量实现通信。并发编程的目的是通过尽可能地提高线程的并发度，来提升总体的计算速度。

互斥就是让一段代码（也称为临界区）至多只能由一个线程执行（进入临界区），其它线程必须等该线程执行完这段代码（离开临界区）后才能开始执行。互斥通常用于保护对共享变量操作的完整性，使其免受来自异步线程的不可预测的干扰，**是并发编程中最重要、最基本的概念之一。**但是互斥使得临界区成为不可并行执行的顺序代码，从而降低了并发度。如果所有的代码都互斥，任何时刻只有一个线程运行。

此要尽可能少用互斥，尽可能降低互斥的粒度，以提高并发度，提升加速比。

锁的性质：

互斥，不同线程的临界区不交叠

无死锁说明系统整体上在进展，尽管个别线程可能没有进展。

无饥饿表明每个线程都在进展。无饥饿蕴含无死锁。

锁应当满足的三个基本性质：互斥（安全性），无死锁（活性)，无饥饿（活性)。

第二讲 互斥算法

1.彼得森算法（Peterson’s Algorithm）

2.过滤器算法

3.面包房算法

“先到先服务”。基本思想是让每个要进入临界区的线程取个号，号小的比号大的先进入

临界区。号是单调增加的

第三讲 并发对象

一个对象封装了一个数据结构，提供一组方法用以对该数据结构进行操作。

在同一时刻可以有多个线程都在执行一个对象的方法，并且它们执行的相对速度是不确定的。这导致对象的状态不确定。在一个线程执行某个方法过程中的每一步，都可能受到其它线程的干扰。

可线性化：

直观地说，如果一个并发对象的每个方法的每次调用对系统状态改变的效果都可以看作是在该次调用的开始和结束之间的某个时间点发生的，这个并发对象就是可线性化的。这个时间点称为该次调用的可线性化点。

可线性化是并发算法的基本要求。

不同的方法调用可以在时间上交叠，但它们的可线性化点不可能交叠。

可线性化的两个条件：

1.先进先出：可线性化就将并发对象的正确性归结为顺序执行的正确性。

2.可以并发。不发生交叠

一个方法的所有调用的可线性化点都对应于该方法代码中的同一个位置，这种可线性化点称为固定可线性化点。但是也有不少并发对象的同一个执行中，同一个方法的不同调用具有不同的可线性化点，有的甚至对应于其它方法代码中的位置。

同一线程对方法进行调用的次序称为程序次序（程序次序对不同线程调用方法的次序不做要求）。顺序一致性要求方法调用产生效果的顺序与程序次序一致。

顺序一致性与可线性化性的不同在于，不要求?G ? ?S。顺序一致性不要求不同线程的方法调用保持它们的实时次序。

第四讲 共享内存基础

并发计算有两种主要的模式：共享内存和消息传递模式。课程默认的计算模式为共享内存的并发计算模式。

在单核处理器下，并发程序的特点是宏观并行、微观串行。

在共享内存的（异步）多核处理器下，并发程序的特点是宏观并行、微观并行。并发线程可独占处理器（核）运行，而不被阻塞（non-blocking），实现满足 lock-freedom 或 wait-freedom 特性的运行。

本讲和后面几讲的任务是提出一个与图灵机类似的共享内存并发计算模型，并考察在此模型下，哪些问题在特定的并发性质下是可计算的，哪些问题在此性质下是不可计算的；主要关注仅通过读写共享内存，可以实现哪些可计算的并发对象，而有哪些并发对象是不能这样实现的。

按照寄存器满足的性质划分，可分为安全的（safe）、正规的（regular）和原子的（atomic）三类。

对于 safe 寄存器来说，如果写操作和读操作不重叠，读操作会正确读出之前（最近）一个写操作的值；如果写操作和读操作重叠，读操作可以读到该寄存器所允许的任意值。Regular寄存器在此基础上增加了一条限制：当读、写操作重叠时，读操作要么读到当前重叠的写操作的值，要么读到在读操作之前完成的最近一个写操作的值。Regular 寄存器的问题在于，对于连续的两个读操作，当前一个读操作已读到新值时，后一个读操作仍然会读到旧值。

为此我们再增加一条限制：当前一个读操作读到新值后，后续的读操作不再被允许读到旧值。满足这些性质的寄存器是原子的。

下面将展示的是其它类型的寄存器对象可以完全基于可单独单写的安全布尔寄存器对象来实现，而不需要引入额外的互斥机制。也就是说，仅通过读写共享内存，能够多线程（可线性化地）“互斥”或者“原子”访问共享寄存器对象，在方法级的粗粒度层面实现宏观并发。

从安全 SRSW 布尔寄存器构建原子 MRMW 多值寄存器

通过改变对原子多读单写寄存器数组的访问方式还可以构建另一类数据结构：**原子快照。**在原子快照中，每个寄存器对应一个线程，每个写线程在自己对应的索引位置写入数据，称为 update 方法。每个读线程使用 scan 方法扫描整个数组。原子快照构造了一个原子内存组的瞬间视图。

第五讲 共识协议和同步操作原语

线程间的同步，就是在发生访问冲突时确定相互的执行顺序。经典的同步依赖于锁（lock）实现。这样的同步是阻塞的（blocking），因为持有锁的线程（即临界区内的线程）阻塞着仍在申请锁的线程（即临界区外的线程，等待获得锁以进入临界区）。

从多读多写原子寄存器可以看出，任意有穷多个线程对共享内存的并发“读”-“写”访问可以原子地（可线性化地）执行，即在时间上发生重叠的读操作和写操作之间实现 wait-free 的同步。这样的同步是非阻塞的（non-blocking），总能在有穷步内完成。

第六讲 空转锁和争用

第七讲 管程和阻塞同步

第八讲 链表

**空转锁（spin locks）**能够保证即使在锁被频繁使用时仍具有良好的可扩展性。一般地，对于任意数据结构而言，构造基于粗粒度锁（Coarse-Grained Synchronization，粗粒度同步）的并发实现是相对简单的。

**下面给出几种高并发实现的一般方法，**不仅对并发链表有效，而且对后续各种并发数据结构的实现具有指导和借鉴意义：

集合的特点是：不包含重复元素；元素之间是无序的。链表由结点组成，提供三种方法：add(x)将元素 x 加入集合；remove(x)从集合中删除元素 x；contains(x)判断 x 是否在集合中。

细粒度锁的性能出乎意料的差，主要是因为链表操作在本质上还是顺序执行的，锁越多，性能损失越大。无锁链表的性能一般都比较好，但是在某些场景下，惰性链表的性能反而比无锁链表的性能好。所以，并发计算的性能与具体的运行环境密切相关。

第九讲 并发队列和并发栈

不同的数据结构类型有不同的访问方法。例如，访问寄存器的基本方法是读或者写寄存器；访问链表的基本方法是插入、删除或查找元素。仅就数据结构类型而言，本课程涉及的并发对象与相应的顺序对象是一致的，而差别在于并发对象是其数据结构类型的并发实现，支持任意多线程的并发访问。事实上，对于一些数据结构类型，可能不存在、或者存在但不需要特别处理的“并行场景”，例如队列和栈。

队列和栈都属于池（pool），不提供 contains 方法来查找其中的元素，且允许重复元素存 在其中。池中可容纳元素的数量称为池的容量。就池的容量而言，池可以是有界的（bounded），即可容纳有限多个元素；或者是无界的，即可容纳任意多个元素。

1.队列

按先进先出（FIFO, first-in-first-out）的全序即可构成一个队列。在并发系统中，常常使用消息队列或任务队列进行异步处理，使用数据总线队列进行数据同步以保证数据修改的有序性。队列须提供入队方法 enq(x)：将元素 x 加入队尾（tail），出队方法 deq(x)：删除队首 （head）元素 x 并返回之。典型地，没有查询方法。经典的并发队列应可线性化为顺序队列（即符合队列的 FIFO 顺序规范），这是因为队列不实现数据集合，而关注数据的生产和消费顺序保持一致。

采用 CAS 原语修改共享变量，变量值从 A 变为 B，然后又变回 A，但指令不能区分前后两个 A 值。这被称为 ABA 问题，是 CAS 原语的典型问题。

解决 ABA 问题的基本思路是对前后两个 A 值加以区分。这可以通过引入时间戳（timed stamp）来实现。在上述示例中，可以为 head 附加一个时间戳，每次修改 head 时，同时写入当前的时间戳，如下图所示。在 Java 中，AtomicStampedReference 类将引用和时间戳封装 在一起。

2.并发栈

栈也属于池（pool），不需要提供 contains 方法来查找其中的元素，且允许存在重复元 素。按后进先出（LIFO, last-in-first-out）的全序即可构成一个栈，提供入栈 push(x)方法和出栈 pop()方法，前者从栈顶添加元素 x，后者删除栈顶元素并返回之。

栈似乎“先天”是顺序的，因为入栈和出栈都发生在栈顶。因此，栈顶构成并发访问栈 的“顺序瓶颈”。在第 6 讲，空转锁也是“顺序瓶颈”，但由于锁的互斥本质，能够达到顺序访问的性能，就是最理想的。对于并发栈而言，其目的在于共享，能否超越其“顺序瓶颈”，提高并发性能，是这一节的重点。

第十讲 共享计数

第十一讲 并发哈希和固有并行

封闭寻址哈希表一般是链式结构。链表是动态生成的，链表上的相邻结点一般不会在同 一个 cache line 中，对链表结点的访问会产生 cache miss。开放寻址哈希表通常是静态数组结构，在初始化时预先分配一块完整的内存区域，相邻数组元素可以存放在同一个 cache line中，这样的 cache 性能会比较好。

第十二讲 调度和工作分配

本课程从具体数据结构和算法的角度，展示了多核编程的“内幕”——面向不同类型共
享对象的高效并发访问机制。在最后一讲，我们将讨论如何对一般的计算任务实现并行化处理，在语言或开发环境层面需要哪些支持并行化处理的机制。这里，我们主要关注并发访问的主体——线程。

学习资料补充

你以为看到这里就结束了吗？并没有。这门课终究还是不好学，所以这里放上我的一些笔记整理和相关资料~
并发数据结构与多核编程 – 列车售票系统

并发级别：阻塞、无障碍、无锁、无等待-----区别与联系

《并发数据结构与多核编程》作业题答案

《多处理器编程艺术》课后答案

码字不易，都看到这里了不如点个赞哦~
我还写了很多文章，欢迎关注我哦~

亲爱的朋友，这里是我新成立的公众号，欢迎关注！公众号内容包括但不限于人工智能、图像处理、信号处理等等~

本博客的优秀博文也将陆续搬运到公众号，之后还将推出更多优秀博文，并将优先发在公众号，敬请期待！ 关注起来，让我们一起成长！