Concurrent Programming in Java 是 Coursera 的上的一门课程，一共有四周课程内容，讲述Java中的并行程序设计。这里是第4周课程的内容笔记。主要内容为 Concurrent Data Structures 并发数据结构。
在本模块中，我们将研究并发数据结构，该结构在所有多线程编程系统中构成必不可少的软件层。首先，我们将学习乐观并发性，这是一种重要的多线程模式，其中两个线程可以“乐观地”在分配的工作上取得进展，而不必担心相互冲突，并且仅在“提交”工作结果之前检查冲突。然后，我们将研究广泛使用的并发队列数据结构。尽管使用并发队列的API非常简单，但使用Optimistic Concurrency模型实现的API却可能很复杂且容易出错。为此，我们还将学习线性化的形式概念，以更好地理解并发数据结构的正确性要求。然后，我们将研究并发哈希图，另一个广泛使用的并发数据结构。最后，我们讨论一种用于查找无向图的最小生成树的并发算法，该算法依赖于在幕后使用并发数据结构。
关键概念
- 了解并发算法中的乐观并发原理
- 了解基于乐观并发的并发队列的实现
- 将线性化理解为并发数据结构的正确性条件
- 创建使用java.util.concurrent.ConcurrentHashMap库的并发Java程序
- 分析用于计算无向图的最小生成树的并发算法
Optimistic Concurrency
在本节中，我们研究了乐观并发模式，该模式可用于提高并发数据结构的性能。实际上，这种模式最常由实现并发库的组件（例如AtomicInteger和ConcurrentHashMap）的专家使用，但是对于所有程序员来说，了解这种方法的基础很有用。作为示例，我们考虑了通常如何对共享的AtomicInteger对象实现getAndAdd()方法。基本思想是允许多个线程在不进行任何同步的情况下读取共享对象的现有值（curVal），并且还可以在不进行同步的情况下计算添加后的新值（newVal）。假设在读取curVal和计算newVal之间的时间段内不会与其他线程发生干扰，可以乐观地执行这些计算。但是，每个线程都必须通过如下使用compareAndSet()方法来确认此假设。 （compareAndSet()用作乐观并发的重要构建块，因为它在许多硬件平台上都非常有效地实现。）
在AtomicInteger A上调用的方法调用A.compareAndSet(curVal，newVal)会检查A中的值是否仍等于curVal，如果是，则在返回true之前将A的值更新为newVal；否则，该方法仅返回false而不更新A。此外，可以保证compareAndSet()方法是原子执行的，就好像它在针对对象A的基于对象的隔离语句中一样。因此，如果有两个线程，T1和T2使用与A的当前值相匹配的相同curVal调用compareAndSet()，只有其中一个会成功地使用newVal更新A。此外，每个线程将在循环中重复调用诸如compareAndSet()之类的操作，直到操作成功。由于没有阻塞操作，因此可以确保永远不会导致死锁。同样，由于每次调用compareAndSet()都会确保最终成功，因此也不会存在活动锁。通常，只要在单个共享对象（如A）上的争用不高，返回false的对compareAndSet()的调用的数量将非常小，并且乐观并发方法在实践中可以表现得更好（但在比使用锁，隔离或参与者更复杂的代码逻辑的成本）。
image
Concurrent Queue
在本节中，我们研究了并发队列，并发队列是流行的队列数据结构的扩展，以支持并发访问。队列上最常见的操作是enq(x)，它使对象x进入队列的末尾（尾部），而deq()则删除并返回该队列的开始（头）处的项。并发队列的正确实现必须确保对enq()和deq()的调用保持正确的语义，即使从不同线程并发调用也是如此。尽管始终可以使用锁，隔离或参与者来获得并发队列的正确但效率较低的实现，但本讲座说明了专家如何使用乐观并发模式来实现更有效的并发队列。
这种实现方式的常见方法是用AtomicReference替换对象引用（例如tail）。由于compareAndSet()方法也可以在AtomicReference对象上调用，因此我们可以使用它来支持（例如）对enq()的并发调用，方法是确定对compareAndSet()的调用成功了，并重复失败的调用。这为并发专家通常开发的enq()和deq()的更有效实现提供了基本方法。 Java中流行的并发队列实现是java.util.concurent.ConcurrentLinkedQueue。
Linearizability
在本讲座中，我们研究了并发对象的重要正确性属性，称为线性化。并发对象是一种数据结构，旨在支持多个线程并行操作。线性化性回答的关键问题是，当多个线程并行执行这些操作时，考虑到我们对顺序执行这些操作的预期返回值的了解，可以允许哪些返回值。例如，我们考虑了两个线程，个和
，对共享的并发队列数据结构并行执行
enq(x)和enq(y)操作，并考虑了执行的
deq()操作可以返回哪些值2在调用enq(y)之后。从线性化的角度来看，deq()操作可以返回项x或项y。
一种看待线性化定义的方法是，您好像是一名律师，试图“捍卫”实现并发数据结构的朋友，并且您需要做的所有事情来证明您的朋友“无罪”（不是编写一个有缺陷的实现）是为了展示一种情况，其中所有操作都通过标识可以声称这些操作已经生效的逻辑时刻来返回与顺序执行一致的值。因此，如果deq()返回了项x或项y，则您可以声称这两种情况都是合理的，因为我们可以合理地假设enq(x)在enq(y)之前生效，反之亦然。但是，绝对不存在这样的情况：对deq()的调用可以正确返回代码/异常以指示队列为空，因为至少enq(y)必须在对deq()的调用之前生效。因此，并发数据结构的任何实现的目标是通过使用认为适当的结构组合（例如锁，隔离的，actor，乐观并发）来确保其正确性，同时提供最大的性能，从而确保其所有执行都是线性的。
image
Concurrent Hash Map
在本节中，研究了ConcurrentHashMap数据结构，该数据结构可作为Java中java.util.concurrent标准库的一部分获得。一个ConcurrentHashMap实例chm实现了Map接口，包括get(key)和put(key，value)操作。它还实现了ConcurrentMap接口中指定的其他操作（依次扩展了Map接口）；这样的操作之一就是putIfAbsent(key，value)。使用putIfAbsent()的动机是确保即使在多个线程尝试并行插入同一密钥的情况下，也只能在chm中插入密钥的一个实例。因此，对get()，put()和putIfAbsent()的调用的语义都可以由之前研究的线性化理论来指定。但是，值得注意的是，还有一些聚合操作，例如clear()和putAll()，无法安全地与put()，get()和putIfAbsent()并行执行。
受java.util.concurrent库中可用的大量并发数据结构的影响，本讲座主张，在可能的情况下，请使用诸如ConcurrentHashMap之类的库，而不是尝试实现自己的版本。
Minimum Spanning Tree Example
在本讲座中，我们讨论了如何应用在本课程中学习到的概念来设计并发算法，以解决为无向图找到最小成本生成树（MST）的问题。众所周知，无向图可用于表示各种网络，包括道路，火车路线和空中路线。生成树是一种数据结构，其中包含来自图的边的子集，该边的子集连接图中的所有节点而不包含循环。生成树的成本计算为树中所有边的权重之和。
在本讲座中研究的并发算法建立在众所周知的顺序算法的基础上，该算法迭代地执行edge收缩操作，这样，给定图中的节点N1，GetMinEdge(N1)返回与N1相邻的一条边包含在MST中的最低成本。如果最小成本边为（N1，N2），则算法将尝试合并图中的节点N1和N2，并用单个节点N3替换该对。要并行执行边缘收缩，我们必须注意两个线程可能在同一顶点上碰撞的情况。例如，即使两个线程以顶点A和D开头，它们都可能都以C作为结尾，并且具有最小的成本优势。我们必须避免算法尝试将A和C以及D和C组合的情况。一种可能的方法是将非结构化锁与对tryLock()的调用一起使用，以安全地执行合并，但又不会造成死锁或活锁情况。调用tryLock()的主要挑战是，如果调用返回false，则需要进行一些修复。最后，它还有助于使用并发队列数据结构来跟踪可用于处理的节点。
Project
在本作业中，我们将专注于并行化Boruvka算法的参考顺序版本。 Boruvka的顺序算法的以下摘要来自Galois项目对Boruvka的算法的描述：
“ Boruvka的算法通过在输入图上连续应用边缘收缩（没有自环）来计算最小生成树。在边缘收缩中，从图中选择一条边缘，并通过连通性的结合形成一个新节点选定边缘的入射节点的数量。在有重复边缘的情况下，联合中仅进行权重最小的一个。图2演示了此过程。Boruvka算法以无序方式进行。每个节点执行边缘收缩与最轻的邻居。”
在下面的示例中，连接节点M和N的边缘收缩，导致节点M和N被单个节点L取代。
image
在本次分配中，我们将探索并发队列，线程和非结构化锁的使用，并调用tryLock（），以产生Boruvka算法的并发且无数据竞争的实现。您的并行实施将在代表几个美国地区的道路网络的真实数据集上进行评估。
网友评论