优享资讯 | 超详细万字图解并发容器2(CCQueue)

掘金后端 ( ) • 2024-05-02 09:38

超详细万字图解并发容器2(CCQueue)

这个文章居然要爆金币才能看...

个人理解, 有错误可以帮忙指正

https://dl.acm.org/doi/10.1145/2370036.2145849

读这篇之前，需要先看完专业术语部分，尤其是

要对CLH lock和MCS Lock 这种queue-lock的实现，和具体的优缺点有一个认识。
要对基本的并发原语，包括强弱性，缓存友好性，能提供的progress-guarantee有一定认识。

0. 英文翻译

state-of-the-art 最先端的

shed light to 使...更容易理解

elapsed time: 简单理解是实际执行操作的时间(办正事的时间)

1. 专业术语

1.1. RMR(Remote Memory References)

这里的Remote针对单个处理器(Processor)而言，只要是不访问本地缓存的访存操作，都可以视为一次RMR。比如访问L3共享Cache，访问内存。

要区分RDMA里的Remote，RDMA的Remote就更强大了，指的是直接访问另一个主机的Memory...

本文对RMR的定义为: 如果当前processor访问一块并非当前processor被执行的内存空间时，在NUMA架构中，这是一个很耗时的操作

1.2. Cache Coherent

缓存一致, 既然每个Processor都有自己的Cache，那如何让自己的修改同步到其他Processor呢? 这就需要很复杂的协议控制(一致性保证, 性能也不能太差)，MESI就是一种缓存一致性协议。

缓存一致性对CAS实现的影响: CAS每次都要去检查一块内存空间上是否仍然是expected_value，如果出现hotspot(CAS频繁失败), 那么相当于使得本地缓存里的变量频繁被update(失败就更新缓存行，以获取内存中被其他processor更新到的新数据)，从而降低了缓存命中率。

CAS操作在CC系统(使用缓存一致性协议的体系结构中)，由于每次操作都要观察shared_memory上的数据是否被修改，因此频繁失败会导致缓存行频繁更新，造成性能瓶颈。

1.3. NUMA

一种面向多核处理器的内存架构, Processor是无本地缓存的(Cacheless)，大家共同访问一块共享内存，但访存速度取决于processor和memory的距离，不同processor访问内存的不同区域访存速度都不同。

我们个人PC一般使用SMP(Symmetric Multi-Processor) 对称多处理器架构, 也就是缓存金字塔形的架构.

我们也叫DSM系统(Distributed Shared Memory)

1.4. CLH lock & MCS lock

简单来说，CLH和MCS都是自旋锁的一种，针对基于 while (CAS) 实现的锁提供了优化(比如缓存友好)，而且编写起来也比较简单。

可以用一句话总结这两把锁， Node-as-Lock，或者叫Queue-as-Lock, 也就是基于队列/结点实现的锁。

https://www.cnblogs.com/shoshana-kong/p/10831502.html

CLH实现:

难点

QNode 的 locked为什么要设置成volatile
unlock中 myNode.set(myPrev.get())的含义

// Lock.java
public interface Lock {  
    void lock();  
    void unlock();  
}

// QNode.java
public class QNode {  
    // Java volatile语义  
    // https://blog.csdn.net/u012988901/article/details/111313057  
    // 1. 禁止CPU重排序 通过内存屏障实现  
    // 2. 可见性: 保证读写绕过CPU内的缓存(happens-before) notice: 其他语言的volatile多数不保证可见性  
    // 3. 不保证原子性, 也就是不支持RMW一类指令级别非原子操作的的原子性，如果有相关需求要用atomic.XXX  
    
    // 思考: 这里的locked如果不加volatile，可能会死锁, 为什么
    volatile boolean locked;  
}

// CLHLock.java

import java.util.concurrent.atomic.AtomicReference;  
  
/**  
* 1. 空间复杂度 O(L+H) L 表示线程数(有L个线程, 就有L个QNode) H 表示锁个数(有H个锁，就有H个QNode)  
* 2. 无饿死，公平性，缓存友好，无惊群效应  
* 注意: 并发编程里的饿死指的是 线程会在 有限时间(finite-time step)内取得进展(make progress)  
* 本例中, 我们可能会想到如果一个线程处理过程一直在处理，或者一个线程前面排了很久的队，这种算是"饿死"吗  
* 对于前者，出现这个现象可能是死锁或者活锁，在CLH的设计中可以规避掉。因此不存在一个thread一直不释放资源。  
* 对于后者，尽管需要等很久，但总是有结果的，因此也符合"非饿死"的定义。  
* 所以，我们说CLH是非饿死的  
* 缓存友好: 不难发现CLH lock是自旋在自己关注的一块memory上，只有自己的前驱会修改这块memory，如果好几个线程都关注同一块memory，那一旦这块memory被修改了，所有线程的本地缓存也失效了。
* 因此CLH是寄存器级别的，每个Thread可以得到比较高的cache hit rate  
* 无惊群效应: 每个CLH lock解除锁定的前提是自己的prev被解除了锁定。每个node只等待自己的prev，node和prev一对一，不会虚假唤醒  
*/  
public class CLHLock implements Lock{  
    private final AtomicReference<QNode> tail; // 所有p共享的tail，每个p进入时将自己设置为tail 虚拟的链表头  
    
    private final ThreadLocal<QNode> myPred; // 每个p独有的前驱结点  

    private final ThreadLocal<QNode> myNode; // 每个p独有的结点，表示自己  
  
    public CLHLock() {  
        this.tail = new AtomicReference<QNode>(new QNode());  
        this.myNode = new ThreadLocal<QNode>() {  
            @Override  
            protected QNode initialValue() {  
                return new QNode();  // 默认为locked=false
            }  
        };  
        this.myPred = new ThreadLocal<QNode>();  
    }  

        public void lock() {  
        QNode node = myNode.get();  
        node.locked = true;  
        QNode pred = tail.getAndSet(node); // 获取tail之前的值，并将tail设置为node，这其实是一个Swap Object, 通过AtomicReference保证原子性  

        myPred.set(pred);  

        // 轮询之前的tail是不是解锁了，如果解锁则退出该死循环  
        while (pred.locked) {  

        }  
    }  
  
    public void unlock() {  
        QNode node = myNode.get();  
        // tips: 当前线程p对node.locked的修改，能否及时的被p的后继结点发现?
        // 思考一下QNode的locked属性设置成volatile的意义。
        node.locked = false;  
        
        /*
            初始状态: tail(locked=false)
            p1第一次lock 
                
            1. myNode(locked=false), tail(locked=false)
            2. myNode(locked=true), tail(locked=false)
            3. p1.old_tail = tail, tail = myNode
            4. myNode(l=true).prev = old_tail(l=false)
            
            p2第二次lock
            1. p2.myNode(locked=false), tail(p1.myNode)(locked=t)
            2. p2.myNode(locked=true), tail(p1.myNode)(locked=t)
            3. p2.old_tail = p1.myNode, tail = p2.myNode
            4. p2.myNode(l=true).prev = p1.MyNode(l=t) --> 自旋
            
            p1 unlock
            1. p1.myNode(l=t)
            2. p1.myNode(l=f)
            3. p1.myNode = old_tail(这里的old_tail就是一开始生成的tail，是一个AtomicReference)  
            真实的队列
            p_i <- p_i+1 <- ... <- p_i+n
                                    ⬆️
                                   tail(这里的tail随着lock()不断的被swap)
            
        */
        
        // tips: 能走到这里, 说明此时myNode的prev是链表首结点 很好证明
        // 这个操作相当于 把整个链表在myNode的位置上断开
        /*
         p_i <- p_i+1 <- ... <- p_i+n
         prev   myNode            ⬆️
                                   tail(这里的tail随着lock()不断的被swap)
         执行后:
         当前线程的视角
         p_i
         myNode,prev
         
         其他线程的视角
        p_i+1 <- p_i+2 ... <- p_i+n
         prev   myNode          ⬆️
                               tail(这里的tail随着lock()不断的被swap)
        此时p_i+1 作为下一个获取锁的线程p的 prev。
        我们发现，上一个unlock的线程把p_i+1的locked设置为true之后就和p_i+1切割了。
        于是乎，上一个unlock的线程 在下一次lock的时候，可以复用这个p_i的QNode。
        */
        myNode.set(myPred.get());  // 把当前node的locked设置为true(为下一个p腾位置)，然后和当前node切割，下次lock可以复用myPred这个node
    }  
}

验证: 简单的++就行, ++是一个经典的指令级别非原子操作(RMW)

package org.example;

import java.util.concurrent.CountDownLatch;

public class Check {
    static int nonAtomicInt = 0;
    private static final CountDownLatch cdl = new CountDownLatch(10);

    public static void main(String[] args) throws InterruptedException {
        // 就用简单的++来验证正确性，10个线程对一个非Atomic的int进行++ 1000w次
        final CLHLock lock = new CLHLock();
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                public void run() {
                    for (int i = 0; i < 1200013; i++) {
                        // 如果这里不加锁，就是随机的结果，多线程同时++
                        // 如果加锁后结果正确，说明我们的锁的实现是正确的
                        lock.lock();
                        nonAtomicInt++;
                        lock.unlock();
                    }
                    cdl.countDown();
                }
            }).start();
        }
        cdl.await();
        System.out.println(nonAtomicInt);
    }
}

其中CLH的优点{无饿死, 公平性, 缓存友好, 无惊群效应} 已经在上面论述。其缺点在于 NUMA架构中, 如果node去获取前驱结点的locked字段，如果前驱结点的内存距离过长，这个自旋过程就非常耗费时间

CLH 在java的AQS也使用过，本文也提及了CLH lock的应用。

MCS也是一种常见的自旋锁实现

其核心在于

每个线程不跨线程访问，而是等待其他线程把自己的isWaiting设置为false。
每个线程每次加锁 都会初始化一个MCSNode对象，该对象的逻辑为

(1) 初始化一个isWaiting=true, next=null的node

(2) 访问全局Lock对象的node, 并将自己设置为其中的node，同时访问自己的前驱结点(跨processor)，将其next设置为自己. 这里不保证prev.next=node这个操作的过程中, prev不被其他人访问，我们后面重点看如何用CAS解决

(3) 如果lock的时候还有前驱, 自己陷入自旋. 否则自己执行操作

解锁操作

(1) 如果自己处于isWaiting，直接退出: 这个是为了连续unlock()的幂等性, 类似分布式锁为每个请求锁的client分配一个uuid

(2) 如果自己后继有人, 则将lock.node.next的isWaiting设置为false(跨线程的设置) (与此同时，某个线程正不断轮询该node以等待其变成false)

(3) 如果自己后继无人, 则尝试将lock.node设置为null。注意到这里的操作(3)和加锁的操作(2) 可能存在竞争。当尝试设置lock.node为null的同时, lock操作将lock.node.next设置为某个线程, 此时会导致unlock的CAS失败，陷入自旋。

5.Amdhal's law

简单来说, 就是利用并发体系带来的性能优化时, 同时又会存在协调并发行为的额外开销. 因此理论上不是核越多性能越高

https://en.wikipedia.org/wiki/Amdahl%27s_law

1.6 combiner

是一种并发容器的设计方案

每个线程有两个行为 announce 和 combine，announce负责向全局队列追加请求, combine会为整个队列加一把大锁, 然后执行不止当前processor的任务。具体实现上可以有更多的feature, 比如combiner执行一段时间后自动释放锁，保证每个processor都可以公平竞争combiner

1.7 常见的并发原语

并发原语就是 "能提供原子性的一套操作"。操作越少，性能越高，提供的并发保证就越简单。

getAndSet(O, v), 也叫Swap。将O设置为值v，并返回旧值
CAS(O, u, v), 看看O是否还是u，如果是则设置为v。CAS的语义明显比Swap更强(锁住的操作更多)，性能上会差一点，但是基于CAS实现的数据结构更强大。不难发现我们操作的地址为共享的，hotspot场景下u会被其他processor频繁修改(导致我们的本地缓存失效)，有较大的缓存一致性开销。

2. 并发容器具备的特征

在SMP和NUMA架构中, 性能良好(我们要理解并发算法不存在银弹, 每个算法在具体的架构具有更好的性能), 所以一般的实现都是在具体的系统上给出具体的实现。

本文中，介绍了三种主流架构

SMP: 经典的多核架构, 在个人PC中比较常见, 多级缓存结构. 本文给出的实现是CC-Synch方法
NUMA: 无缓存, 不同CPU slot访问不同的内存空间时间不相同. 本文给出DSM-Synch方法
Cluster: 将CPU资源划分为cluster, 每个cluster配置不同的processors, 本文给出的是H-Synch方法

scalable

翻译为"可伸缩性", 文章在Introduction部分给出了比较精炼的定义:

(1) 作为并行算法, 最优时间不应该比单线程顺序执行还差. 很好理解, 如果不如单线程执行, 那还设计并发算法干啥

(2) 办正事的时间应该是稳定的, 不应该和参与的线程数有关

满足上面两点的算法具备良好的可伸缩性

3. 和之前研究的斗蛐蛐

本文(2012年的产物)相比MSQueue(1990s的产物)，跨越比较久远，所以中间也经过了很多优秀的其他设计，主要有

fine-grained的算法

java的 AtomicReferenceFieldUpdater应该就是这样的。简单理解就是细粒度锁，而不是一把大锁梭哈.

combined-base的算法

见本文1.6

P-Sim
CLH自旋锁

要注意CC-Synch和DSM-Synch是一种并发设计的概念，文章作者使用它实现了queue和stack

一种wait-free的栈 SimStack

SimStack是一种 linked-based(链表实现), 基于flat-combining，并采取了elimination优化，这个优化的理念就是 "压缩操作"，比如两个线程一个push，一个pop，那就等价于啥也不做，由于所有操作在combiner的眼里就是队列的一个结点，combiner就可以在执行前有一个全局的概览，从而做出优化(这也是这种中心化处理的好处)

MSQueue, 这个在https://juejin.cn/post/7358622889681338380 介绍过了

但我们主要说的是无锁实现, 无锁实现用两个dummynode和一个list实现了无锁的并发队列。MS的文章还介绍了一个双锁实现的stack和queue，本文作者把里面的双锁替换成了CC-Synch based，发现又有性能提升。

论文给出了一种队列同时作为锁的实现和任务载体的数据结构，相比之前的纯combine-based算法，在编程实现上更简单，性能更好，公平性更高，并且可以在有限的RMR个数完成操作。

在CC-Synch中，RMR的次数为O(h+t), h为一个用户可调的参数，表示一个combiner最多可以处理多少被announced 的请求。t是处理这h个请求时，必须进行的访问共享对象的个数。

在DSM-Synch中，RMR的次数为O(dh), d为处理单个请求的平均RMR次数，可以认为是一个比较小的常量。

陷入自旋的线程平均需要O(d)次RMR。我们简单理解下自旋对性能的影响

无限次CAS: 缓存命中率差，会饿死，在hotspot(竞争比较大)的时候性能很差
无限CAS, 但是自带back-off(指数退避), 相比无限CAS性能更好，但是需要不断的找出一个很好的退避策略。
我们使用CAS一般都是 while(CAS)，在竞争比较大时，这个CAS频繁返回false，可能会导致分支预测失败，进一步导致性能下降。

DSM-Synch比CC-Synch更复杂，但CC-Synch更适合SMP+缓存一致性架构。DSM-Synch也适合于NUMA架构，以及更通用的体系结构(也就是我们如果把DSM-Synch实现的锁，投放到任何架构的CPU上，都可以取得一个"折中"的性能)

其他相关工作

如何实现combine

之前combine是实现在一棵树上的，然而作者对这些实现提出了挑战 (1) 这种实现的同步开销太大 (2) 多数实现无法满足强一致性(比如我们说的线性)

Oyama 算法

这个算法是一个基于Stack实现的combine-based算法，配合一个指向栈顶的指针，谁能CAS这个指针，谁就是combiner。

由于采取了CAS作为并发设计的构建块，就会有一定的CAS本身导致的问题 (1) CAS是谁能抢到谁就当，抢不到的就永远自旋，可能饿死 (2) combiner会处理所有被announced的请求，combiner也可能会饿死(光处理别人家孩子了，自己线程来不及去announce请求了，要理解annouce和handle是两个过程)。

作者同样对这个算法提出了挑战

(1) 由于底层基石选择更strong的CAS，开销较大(无论是annouce请求的开销，还是竞选combiner的开销)，我们要理解，线上使用算法的时候，肯定有频繁的 announce和竞选combiner的调用。如果这些调用可以换用更简单的并发原语，那整体算法就会更牛逼。

(2) 同样是因为采取CAS，某个线程可能陷入无限的RMR(一直尝试看看目标位置是不是预期的，每看一次就是一个RMR)。

Oyama的算法用CAS判断自己是否是队列头，这导致了竞选combiner这个操作的overhead和线程数成正比。

Flat-combine

这个算法在2010由Hendler等人提出。相比oyama的算法，有以下的不同

请求列表具有一个记录, 用于存放 每个线程是否有被宣告的请求, 这个设计有点像网络多路复用的Select? 这个设计的好处是，请求入队的开销少了，但是combiner在处理请求的时候需要自行迭代所有请求，复杂度变大。更重要的是，combiner在处理请求时是持有锁的，临界区开销增大，对整个算法的性能影响也很大。
该算法也用CAS作为设计的并发基石，但不用于竞选combiner，优化了oyama算法的问题, 但是combiner会定期清理请求队列(这就是trade-off，尽管优化了插入，但是在其他地方就需要额外的处理)。在flat-combine中，竞争combiner是依靠一把大锁，而且flat-combine提供的是"后来的请求先服务"的语义。
注意到可能某一时刻，每个线程都没有活跃的请求，但是combiner还是会轮询一次线程数组，带来额外开销。
同样的，算法选择CAS作为插入请求时的并发保证，就会有hotspot时一直无法插入导致的饿死问题。

Fatourou的算法

Fatourou给出了wait-free的并发结构实现。提出了理论版本(需要依赖不现实的大对象(是说内存不允许吗?))称为Sim，以及实践版本P-Sim。

作者对这个算法居然不是"否定"态度。。。主要夸了一下该算法是 通用的wait-free实现，wait-free实现在容错上有更大的优点。

这里的容错具体是什么含义，直接问了下gpt

在并发编程中，"wait-free" 算法是指保证每个参与的线程都能在有限的步数内完成其操作，即使其他线程被延迟或者停止。这种算法提供了一种强大的活性（liveness）保证，确保系统在面对个别线程的失败时仍能继续运行，这是其容错（fault-tolerant）特性的一个方面。

### Wait-Free 算法的容错性：

1.  **独立进度保证**：Wait-free 算法的核心特性是它们为每个线程提供独立的进度保证。这意味着即使某个线程因为故障（如崩溃或挂起）而无法继续执行，其他线程仍然能够完成它们的操作。
1.  **无中心化设计**：许多 wait-free 算法避免了依赖单个中心点，因为中心点可能成为故障的源头。通过分散算法的控制逻辑，即使部分系统组件失败，整个系统仍然能够正常运行。
1.  **限制竞争和依赖**：Wait-free 算法通常减少线程间的竞争和相互依赖，因为这些因素可能导致算法在面对故障时无法保持容错性。

### 使用“容错”来形容算法的场景：

我们通常在以下几种情况下使用“容错”（fault-tolerant）来形容一个算法：

1.  **算法可以处理组件失败**：如果算法能够在某些组件（如线程、进程、服务器）失败时继续正常工作，我们说它是容错的。
1.  **算法可以纠正错误**：算法在检测到数据错误或异常行为时，可以自动采取措施纠正这些问题，以维持系统的正确性和稳定性。
1.  **算法能够适应环境变化**：面对网络延迟、系统负载变化、资源限制等环境因素，算法仍能保持其功能和性能，显示出一定的鲁棒性。
1.  **算法提供数据副本和冗余**：在分布式系统中，算法可能通过维护数据副本和执行冗余操作来增强系统的容错能力。

总之，"wait-free" 算法通过确保即使在个别组件故障的情况下也能保证系统的持续运行，体现了其容错性。在设计分布式系统、数据库、文件系统和其他需要高可靠性的系统时，容错算法尤为重要，因为它们可以提高系统的整体稳定性和可用性。

P-Sim规避大对象的设计方法是 每个processor拷贝大对象的一部分到自己的局部缓存中，然后本地修改后写回，这个类似一种snapshot的技术。

Dice， Marathe等人

他们研究出了一个flat-combine的改版，适用于NUMA架构，设计出了一个层次化的自旋锁。

尽管这个算法比之前的都厉害，但是被我们的H-Synch打败了...(除了Fatourou的算法，都是这个论调)

为什么H-Synch能打败这个算法呢，作者给出了理论分析(后面就是benchwork，现在只是理论分析)

H-Synch更简单
H-Synch为每个cluster都绑定一个combiner
H-Synch是层次化的CC-Synch，相当于每个combiner都是CC-Synch implemented，而不是flat-combining implemented，CC-Synch相比flat-combine更厉害(见flat-combine的分析[其他相关工作.3])

4. 算法

4.1 设计

在实现上, 用一个FIFO queue 同时作为锁(可以参考CLH/MCS Lock的实现) 以及请求队列。这里怎么理解呢？

在本文1.4 介绍了一种 "队列自旋锁", 通过虚拟队列结点可以实现锁的行为, 而队列本身又可以作为"请求队列", 所以这个算法的实现就是 "自带lock和unlock功能的请求队列".

每个processor可以往队列里添加node，这个node作为 Lock node，同时也作为一个待处理的请求，简单理解就是，Node作为Lock本身的一个实现(见CLHNode, MCSNode)，同时Node本身的含义是一个被announced 的请求。

持有队列中首个结点的processor会成为combiner，会取出结点里的任务(自己的or其他人的)。其他的线程陷入自旋(回顾CLH Lock)。陷入自旋的线程需要一个常数级别的RMR。所以不会有线程被饿死(无限CAS)。

并发原语的选择

我们常说的CAS，其实就是compareAndSet，而本文选择的原语是getAndSet。文章描述为Swap(O, v), 其并发含义是"原子的将O设置为v，并返回其旧值"

CC-Synch选择的并发原语为Swap，尝试追加一个Node到lock的虚拟队列上，这个开销大概是O(n)。DSM-Synch同时选择了Swap和CAS，开销大概也是O(n)

经过性能测试，非Compare的并发原语(getAndSet)，的确比无论是否采取了优化的CAS更强大。

由于现代CPU存在Cluster体系(单个Cluster有自己的更快的高速缓存，跨cluster的访存更慢，可以视为SMP和NUMA的混合版)，作者又给出了层次的CC-Synch，称为H-Synch。

线性保证

回顾线性的定义: 多个processor对于同一个Shared Object，在同一时刻不会存在两个状态（也就是任何processor不会看到由其他processor造成的软状态）。也就是对于操作a，只要a被执行了，就会立刻生效(take effect)

同时在回顾下MSQueue是如何保证线性的: processor会帮助处理soft state。

硬件厂商的"内卷"

我们可以在程序上实现一些原子操作，比如RMW，CAS，基于软件实现的原子操作，本质上利用了指令级别的上锁。

那有没有一种可能，直接在CPU层面支持一些常见的原子操作? 这个就需要CPU实现上支持更多的指令集。

原子操作的强弱定义: 原子操作越强, 它提供的并发保证就越强, 但是额外开销也就越大. 比如基于compare的原子操作，相比非compare的，肯定开销更小，但基于弱一点的操作，可能达不到更强的progress语义(比如wait-free)。

前文已经提到，我们选择Swap这个原子操作作为我们的 "构建块", 也可以叫基底(foundation)。在大多数体系架构都支持指令级别的原子Swap。

常见的指令集原子操作有

LL/SC 强原语可以达成更强的progress guarantee(e.g. wait-free)

CAS 强原语

SWAP

复杂的结构如何保证并发性?

本文提及到可以用 多实例CC-Synch锁来达成复杂数据结构，比如多叉树的并发保证。

这里也是个值得研究的点, 比如mysql的底层设计，B+Tree是如何上锁的

https://catkang.github.io/2022/01/27/btree-lock.html

CC-Synch 实际上就是CLH Lock的改进版，相比CLH Lock的队列其实是一个虚队列，结点也是虚结点(implicit), CC-Synch的结点都是实际的(explicit) 代表一个真实的请求，可以被combiner遍历

同理DSM-Synch则是对MCS的改进版

4.2 实现

1. CC-Synch

我们说CC-Synch既然是CLH Lock的改版，那就一定有一个Node结构，不同于CLH Lock里的Node仅作为一个dummy结点，CC-Synch的Node是有实际含义的

// 可以看到, Node其实是双料特工, 同时作为锁的实现和Reqeust的载体
class Node {
    Request req; // node as request
    RetVal ret;  // result of request
       
    // need volatile
    boolean wait; // node as lock
    boolean completed; // state of request
    Node* next;
}

同时CLH Lock也有一个Tail, 可以理解为队列本体这个队列是被所有线程共享访问的

Tail保证: 总是位于list的最后一个node，我们可以看代码是如何保证这一点的


// 初始化为 {null, null, false, false, null}
// Tail是一个Swap对象，我们主要用原子的getAndSet操作
AtomicReference<Node> Node* Tail;

同时，CLH中每个processor都有自己的Node，我们可以设计为TLS(Thread-Local Storage)

// with initial value {null, null, false, false, null}
private final ThreadLocal<Node> currentThread; // prev

算法伪代码

RetVal CC-Synch(Request req) {

    // 这里curNode只是每个线程内持有的一个node饮用，我们在下面也会用prevNode混用
    // 其实针对 "线程完成插入后引用的node" 这个概念，prevNode和curNode是一样的
    // 之所以会有名字上的区分，是因为在整个插入请求过程中，对这个node的引用会Swap，所以一会他是"cur", 一会他是"prev"
    Node nextNode, curNode, tmpNode, tmpNodeNext;
    int counter = 0; // 用于表示当前combiner处理多少个请求了
    
    // 这几步其实和CLH Lock差不多
    nextNode = currentThread;
    nextNode.next = null;
    nextNode.wait = true;
    nextNode.completed = false;
    curNode = tail.getAndSet(nextNode);
    curNode.next = nextNode;
    
    curNode.req = req;
    
    // tips: 这里体现了combiner的竞选 思考如何体现的呢?
    currentThread = curNode;
    while (curNode.wait); // spining
    
    if (curNode.completed) return curNode.ret;
    
    tmpNode = curNode;
    
    while (tmpNode.next != null && counter < h) {
        counter++;
        tmpNodeNext = tmpNode.text;
        
        // handle it
        // 执行这一步操作的时间也叫 elapsed time
        // 说白了前面都是"前戏部分"， 也就是并发的overhead
        tmpNode.ret = doRequest(tmpNode.req);
        tmpNode.completed = true;
        tmpNode.wait = false;
        tmpNode = tmpNodeNext;
    }
    tmpNode.wait = false;
    return curNode.ret;
}

算法大体可以分为几部分

插入到队列: 原子性的交换currentThread和此时队列尾巴, 交换后, 队列的尾部成为currentThread, 这其实有两个含义 (1) 当前线程announce了一个请求 (2) 当前线程称为combiner的竞争者。
我们重点分析

    currentThread = curNode;
    while (curNode.wait); // spining

这两步, 这里currentThread是一个线程局部变量，一开始被初始化为一个dummyNode，随着lock/unlock，会不断的被更新。

当执行完node insert操作后，我们说curNode此时指向新Tail的前一个结点(Swap(Tail, node))

这两行代码是没有任何锁的，所以同一时刻有多个线程会竞争。但只有此时队列首部的thread会成功。

我们可以简单理解下，队列首部结点对应的processor，实际保存着一开始的那个被初始化的Tail(wait=false)。

算法初始化:

假设thread1 thread2 thread3 都执行announceRequest()操作，并且假设顺序是 thread2->thread1->thread3(由于annouceRequest是个复杂的操作，所以并发执行中，语句实际上是交织[interleave]的)

这里Swap的含义就是，把自己和Tail原子性交换。这样可以避免如果此时Thread1也在交换的话，Thread2会看到Thread1执行了一半的结果

这里原子交换的结果就是，Tail指向自己原来的Node，然后自己指向原来Tail的位置

同时，我们把原来Tail的next设置为新的Tail。这里保证了Tail永远是队列的最后一个结点

我们模拟Thread1此时加锁的行为

把dummyNode1的wait设置为true
Swap(dummyNode1, Tail) 红线表示prevNode原本指向dummyNode1，然后指向Tail(在上一步被设置为dummyNode2)。绿线表示Tail原本指向dummyNode2，现在指向dummyNode1，dummyNode1成为新的Tail，完成插入
让prevNode的next指向新的Tail，也就是蓝线部分

我们继续模拟Thread3的加锁行为，和上面一样，不再赘述。

整理一下按照Thread2，Thread1，Thread3加锁后的整体状态:

然后算法进入下一步: 竞选combiner

只有prevNode对应的结点wait=false才能成为combiner，我们发现此时就是Thread2，也就是第一个成功提交请求的结点。此时它刚好指向了一开始用于初始化Tail的dummyNode

分析完了加锁(annouceRequestAndLock)和竞选combiner(toCombinerElseSpin)的过程，接下来就是combiner如何处理请求(handleRequest)的过程

combiner退出时，tmpNode(最后一个被处理的结点的下一个)的状态如图，completed=false, wait=false

思考: 如果此时Thread2又执行了一次announceRequest后，整个状态是什么样的呢

思考: 我们发现此时Thread3在执行自己combiner的操作，Thread2并发的插入了一个新任务，其并发正确性如何保证? [也就是算法正确性保证]. 如何设计压测方案？

因此，为了避免combiner无限执行(combiner执行期间，其他processor也是可以向list追加请求的)，所以可以有一个上限处理数h，超过h，combiner就自动放弃request的执行。h的选择对算法的实际性能影响不大，一种启发式的h选择的逻辑是，让h = cn(c是一个小常数，n是系统的线程数?)

答案

这里最不好懂的就是这个指针交换操作。我们可以用 3种颜色，5钟变化，2个操作来描述

3种颜色: Tail和prevNode修改指向，prevNode指向新的Tail的过程。

5种变化: Swap四种, prevNode修改next一种

2个操作: Swap, prevNode.next = Tail

文中指出对算法的一个小"批评"是

注意图中的红线部分，当thread1执行完了prevNode = Swap(nextNode, Tail), 在执行prevNode->next=nextNode(图中的红线)时，被调度走了(可能刚好执行完时间片)，然后其他线程这时候照常执行。这就会导致一个问题，理应成为combiner的线程被调走了，其他线程反正也成不了combiner就空转，这就导致这次调度是完全没意义的，好比"这件事只有我能干，然后给我调走了"

由于只有首个加入request的线程才能成为combiner，但只有我们是知道这一点的，也就是如果当前thread处在队列的首部，应该继续执行下去，反正其他线程也不会竞争成为combiner，就应该以我为优先，但是在调度器的视角里，所有processor一律平等，不管你是不是老大，到了时间片就得调度走(这就是领域特定和通用设计的trade-off)。但实际上我们可以用CPU提供的对scheduler的 hint机制，在应用程序中判断这种case，然后提示OS scheduler不要在Swap和设置next之间把线程调度走。

线性证明:

我们之前的图都是把一整个announceRequest视为一个整体来看的，那同一时刻，所有线程观察到的状态都是一样的吗? 线性就是反应这个性质: 同一时刻，其他线程的操作对所有线程是否一致。

这就好比"不在场证明"，如果我说我去买菜了，那 买菜() 这个调用，在所有人眼里应该是一样的，但如果有一个线程看到的买菜() 是买刀(), 但实际上呢，这个线程看到的是"路过买水果刀的摊位，然后去买菜"这个过程的前半部分，那就说不清了。换句话说如果一个线程声明自己进行了一个调用，所有其他线程应该看到该调用起作用(take effect)后的结果，而不是中间的某个结果。

简单理解, 任务的执行是顺序的，相当于同一时刻combiner按顺序执行list上的所有request，然后其他thread时刻盯盘。

所以不存在一个processor看到某个任务被完成了，另一个processor看到这个任务没被完成。

RMR复杂性度和空间额外开销分析

每个thread只会有两种退出的case

自己不是combiner，一直在自旋，旋着旋着发现自己node上的completed为true了，说明combiner大哥帮自己做完了，直接返回。此时只需要常数级别的RMRs，更重要的是每个processor都只盯盘自己的node，而不像CAS那样大家都盯一块共享的内存，大大提高了缓存友好性
注意combiner执行过程，需要访问h个任务对象，这会带来O(h)次RMR, 这里我们注意到，combiner会访问其他processor提交的任务(本体是一个node)，在NUMA架构中，这种跨processor的内存访问开销比较大，在SMP中就没有那么大。t代表需要完成h个操作需要访问共享存储的次数，简单理解就是: 执行任务需要的访存。我们把Request视为一个个的operation，这些operation负责操作底层的共享数据。这里把队列理解成一个调用队列，e.g. put(1), put(2), pop()，这些操作最终会执行到底层共享存储结构，我们称操作底层结构的复杂度为O(t), 一共就是O(h+t)。
CC-Synch的空间复杂度为O(n)，简单理解就是n个线程，对应n个node。

需要的内存屏障

在本例中，

修改cur的两条语句 cur->req = req, cur->next = next

修改tmpNode的两条语句 tmpNode->completed = true tmpNode->wait = false

如果处理器遵循TSO处理语义，那么是不需要额外的写屏障的，因为我们发现，其他线程会轮询在tmpNode.wait上，这里是一个关联的读写。

combiner -> 一直写wait: combiner要保证自己如果把wait写成false后，这个"写false" 的行为会被其他的processor看到，也就是不能光写到自己的本地缓存里，要同步会主存。

其他processor -> 一直轮询wait

在combiner退出前，此时会把最后一个node的wait设置为false，但是不处理这个node。这里必须要让修改被其他线程看到。

作者的意思是，当combiner执行处理任务时，将那些已经被执行完的node.wait设置为false，其实可见性没那么重要，因为就算其他processor看不到，也不影响当前算法取得进展(make progress)。但combiner如果退出时，会把last node.wait设置为false，这里的可见性就非常重要，因为如果刚好指向当前node的processor没看到combiner把wait设为false了，就会导致一定时间的空转，直到看见这个修改，会导致算法进入一定时间的空转。

在java里，直接把wait设成volatile就能解决这一点

2. H-Synch

适用于处理器被分为C个cluster，一共m个processor，相当于一个cluster具有m/C个processor。

每个Cluster都运行一个CC-Synch，同时有一把全局大锁L，如果Cluster之间的通信是采取SMP架构的(跨cluster的通信访存开销一样)，那么这把大锁可以用CLH Node实现，否则可以用MCS Lock实现。

相比CC-Synch，只需要在竞选combiner之前acquire 这把全局大锁L即可。

H-Synch可以很轻松的改成层级结构，适用于更复杂的层次网络。

每个Combiner会优先按照FIFO的顺序处理本Cluster的请求(? 如果还能处理，就处理其他cluster的)，所有Combiner在全局大锁的顺序也是FIFO的(见CLH Lock的实现，公平获取🔒)。请求处理顺序是局部FIFO的，全局并不保证FIFO。

DSM-Synch

依旧是结点定义

struct Node {
    volatile Request req;
    volatile RetVal ret;
    volatile boolean wait; // 涉及到跨线程的读写，最好一律弄成volatile
    volatile boolean completed;
    volatile Node* next;
}

全局的tail，时刻指向链表的尾部


shared Node* Tail = null; // 注意: DSM-Synch中，Tail不再初始化为一个dummy Node

线程局部变量：


private ThreadLocal<Node[2]> myNodes; // 每个线程保存两个node
private int toggle = 0;

算法流程: DSM-Synch(可以理解为 announceRequest, toCombinerOrSpining, handleRequests 一个方法三合一)

RetVal DSM-Synch(Request req) {
    
    Node tmpNode, myNode, myPredNode;
    int counter = 0;
    
    toggle = 1 - toggle;  // 每调用一次，就是0->1或者1->0
    
    myNode = myNodes[toggle];
    
    myNode.wait = true;
    myNode.completed = false;
    myNode.next = null;
    myNode.req = req;
    myPrevNode = swap(Tail, myNode);
    
    if (myPrevNode != null) {
        myPrevNode.next = myNode;
        while (myNode.wait); // spining
        
        // 解除自旋并立刻返回值，不竞选combiner
        if (myNode.completed) {
            return myNode.ret)
        }
    }
    
    tmpNode = myNode;
    
    // 尽可能多的处理(可以设置一次最多可处理的量h)
    while (true) {
        counter++;
        
        // 执行请求(办正事), 我们可以把req视为一个对数据结构的操作，比如get(), put(), push(), pop()等
        tmpNode.ret = doRequest(tmpNode.req);
        
        // 如果completed=true, tmpNode.wait=false, 那么自旋在这个node上的thread就可以立刻返回
        // completed和wait都需要是volatile的
        tmpNode.completed = true;
        tmpNode.wait = false;
        
        if (tmpNode.next == null || tmpNode.next.next == null || counter >= h) break;
        tmpNode = tmpNode.next;
    }
    
    if (tmpNode.next == null) {
        // 试图唤醒下一个node
        if (CAS(Tail, tmpNode, null) return myNode.ret;
        while (tmpNode.next == null)
    }
    
    // 此时next.wait = false, next.completed = false
    // 那么该node对应的thread不会直接返回，而是成为下一轮的combiner
    tmpNode.next.wait = false;
    tmpNode.next = null;
    return myNode.ret;
}

图解流程

1. 初始化

相比CC-Synch，一开始Tail被设置为null。

2. DSM-Synch流程

[初始化myNode]初始化myNode，反转toggle，交换myNode和Tail。

[根据myNode的情况竞选combiner]只有myNode和Tail交换时，Tail为null的线程才能成为combiner

假设thread1和thread2同时执行DSM-Synch，那么只有thread1的prevNode此时指向null，所以thread1成为combiner, 同时如果myPrevNode非空，就让这个结点指向myNode。

[开始执行] combiner从myNode开始执行任务

由于我们每次插入一个结点，都维护了prevNode到myNode的指向关系，所以我们让combiner的tmpNode遍历tmpNode.next 就可以。

直到 队列中结点个数 < 2，或者已经处理的请求数 > h时，则退出

[其他线程] 其他线程要么在发现(wait=false, completed=true)时直接退出，要么在发现(wait=false, completed=false)时成为新的combiner

[combiner] 临走前两种case (1) 此时队列里已经没有请求了，需要把Tail设置为null。 (2) 此时队列里还有请求，需要把此时tmpNode的wait设置为false，但是不改变其他属性。

这里设计上，要求combiner不会强制执行最后一个请求，也就是combiner至多执行min(h, 到倒数第二个结点的个数)个请求。这是因为，比如我们图中的情况

由于combiner执行请求，和其他thread追加请求是并行的，而且我们注意MCS Node的设计

插入的时候，我获取前一个 thread的node，把它的next设置成我，然后我自旋在我的变量上。
而CC-Synch中，我获取前一个thread的node，把它的next设置成我，然后我自旋在前一个线程的变量上。
二者区别在于频繁的自旋一个发生在自己的变量区，另一个发生在别的线程的变量区。对于SMP架构这俩是一样的，但是对于NUMA架构的区别就比较大。

回归正题，简单理解这个原因，就是 tmpNode.next.next == null, 不一定表示tmpNode.next.next真的是null。也就是combiner 可能会存在眼花(幻读)，比如图中。当combiner执行到第二个请求时，它观察是没观察到第4个请求的，因此如果我们在第2个请求就放弃执行，是绝对不会漏掉第四个请求的。

相反，如果我们在执行第3个请求时，没发现第四个请求，那么tmpNode = tmpNode.next 会把tmpNode设置为null, 此时第四个请求就被跳过了。

图中的大绿箭头表示 "请求4还没来得及把请求3的next指向自己"

因为我们在执行到倒数第二个请求就退出了，所以又有一个问题: 为什么每个线程要持有两个node? 一个不行吗，复用之前已经被处理完的node不是更省空间?

看不懂呀，看不懂呀。。

简单理解就是，如果我们选择复用一个node，而不是两个node轮班倒，那编程的方式肯定是，每次处理完就 重新初始化 一个node，作者考虑一个case是，如果node被处理完了，又很快的加入到队列里

node_i -> node_j ⬆️ combiner

此时combiner是会退出循环的，因为当前总的结点个数 <= 2，combiner在退出前会把当前指向结点的next.wait设置为false

`node_i -> node_j(wait=false)`
  ⬆️
 combiner.tmpNode

我们假设进到这里之前，node_i又加入了一个请求，那么此时就是

node_i(已经销毁) -> node_j -> node_i(新创建的)
tmpNode
此时combiner在 执行tmpNode.next.wait = false 的时候退出，此时，我们发现tmpNode指向的对象已经寄了，我们还在访问它的next，那就非法了(野指针)。

这反映了个啥case呢?

1. combiner很倒霉的在需要用到node.next的时候被调走了
2. 这个node很不合时宜的重新加入了队列
3. combiner回来的时候还持有旧的node，如果采取复用的做法，就会导致访问到被释放的内存。

DSM和MSC Lock一样，存在CAS的使用，因此可能出现无限步骤的RMRs

正确性和内存屏障

线性

也就是，如果一个线程宣告的请求被执行了，其他线程应该看到该请求作用于共享数据结构的结果(而且必须要看到一样的)

请求真正被执行，在DSM-Synch只有两个地方

非combiner线程看到自己自旋的node上 wait=false&&completed=true时，则返回。
combiner线程在执行完自己的任务，释放最后一个结点的wait之后，返回。

证明线性，就是证明只要这两个case完成了，所有线程都应该看到他们作用于数据结构产生的结果。

如果任务完成，其前提一定是combiner把任务所在node的completed设置为true，然后wait设置为false。

线性一方面可以从 "每个线程不会看到中间状态"，其实另一个解释是 "每个线程对所有操作，看到的顺序是一样的"。

也就是，如果我说"先买西瓜再买包子"，所有人看到我都是先买西瓜再买包子，而不是先买包子再买西瓜。

这个解释和"是否存在中间状态"是一样的，也就是合法的状态是 "只有西瓜，以及同时有西瓜和包子"，非法状态是"只有包子"。所以类比这个例子。

每个线程看到的，都是先操作node，再返回结果。也就是存在两个合法的状态"只操作了node，没返回结果"和"操作了node并返回结果"。

我们假设序列是put(1, 1), get(1), put(1, 2) get(1)，会不会有的线程get返回3，有的返回2?

首先combiner是按顺序执行请求的，所以理论上不会发生。我们假设一个可能性

旧combiner执行的最后一个操作是get(1)，然后解锁了下一个node，
新combiner从put(1, 2) 开始执行。

有没有可能，旧combiner此时get(1)返回2，而不是预期的1呢，这就是违背了线性。

答案是不可能，我们发现put(1, 2)想发生的前提是，旧combiner把该node的wait设置为false，在此之前，旧combiner已经基于当时的环境，完成了get(1) 这个操作，所以返回1

put(1, 1), get(1), put(1, 2), get(1), put(1, 3), get(1)

对于这个序列，假设3个get分别是t1，t2，t3发起的，那么理论上

t1看到的是1，t2看到的是2，t3看到的是3

这个就是线性。

combiner假设负责执行上面的所有操作，那么则有

put(1, 1)这个node的wait和completed分别设置为false和true，返回put的结果(假设put返回null)，tmpNode = tmpNode.next
get(1)这个node的wait和completed分别设置为false和true，执行get(1)，返回此时的结果。

以此类推。

其实，我们发现 get(1) 是被combiner按顺序执行的，所以t1拿到的是combiner的执行结果，同一时刻只有一个线程执行，故线性是可以被保证的。

内存屏障，只需要在combiner解锁tmpNode.wait的时候加一个写屏障，保证修改这个变量被其他线程能读到就行。

RMR分析

除了循环处理请求的RMR为O(hd), h表示单个循环处理的请求，d表示平均每个请求的RMR。

还有MCS Lock自带的CAS的开销，我们让所有自旋都发生在线程的本地(我们不称缓存，因为假设NUMA是无缓存的)，这个自旋可以忽略，所以唯一的RMR发生在仅当combiner为最后一个node，并且此时有thread加入的情况，复杂度为O(n)。

4.3 性能测试

1. 体系结构选择

既然是并发容器，自然离不开体系结构的选择

作者在两个体系结构下进行了测试

Magny Cours Machine

一个处理器(processor), 有两个die, 每个die里有4个核心。die和die之间的通信组成了一个复杂的拓扑(整个机器有6134个处理器)。die内的cores之间的通信基于L3 Cache

"Magny-Cours" 是 AMD Opteron 6100 系列处理器的代号，这是 AMD 为服务器市场推出的多核处理器产品。这款处理器首次发布于 2010 年，以法国的一条著名赛车道命名。它是 AMD 在多核处理器技术上的一个重要里程碑，因为它提供了更多的核心以及改进的性能，特别是针对多线程和多任务处理的服务器应用。

Magny-Cours 处理器的一些特点包括：

1. **多核心设计**：Magny-Cours 处理器最多包含 12 个物理核心，这在当时是相当高的核心数量，使得它非常适合需要大量并行处理能力的应用，如虚拟化、高性能计算（HPC）和大型数据库系统。

2. **NUMA（Non-Uniform Memory Access）架构**：这些处理器采用了 NUMA 内存架构，它允许每个处理器核心或处理器节点直接访问自己的本地内存，同时也可以访问其他节点的内存。这种设计可以提高内存访问速度，尤其是在本地内存访问时，但也增加了设计和编程的复杂性，因为需要考虑不同内存区域的访问延迟。

3. **热效率和能源效率**：Magny-Cours 处理器提供了改进的热设计功耗（TDP），在提供更多核心的同时，还能保持合理的能源效率。

4. **HyperTransport 技术**：这些处理器使用 AMD 的 HyperTransport 技术来提供高速的处理器间通信，这对于确保在多核环境中高效数据传输至关重要。

在多核处理器上，Magny-Cours 处理器的这些特性使得它们在处理并发任务和高负载工作时表现出色。对于并发数据结构和算法的设计来说，这意味着开发者需要考虑如何最大化利用多核心和 NUMA 架构的优势，同时需要解决潜在的内存一致性和线程同步问题。

Niagara 2

每个处理器有8个核心，核心之间的通信经过L2 Cache。

Niagara 2 是 Sun Microsystems（后被甲骨文公司收购）开发的 UltraSPARC T2 处理器的昵称。这款处理器是为服务器设计的多线程、多核处理器，于 2007 年推出。UltraSPARC T2 处理器建立在其前身 UltraSPARC T1（也被称为Niagara）的基础上，带来了一系列的改进和增强。

Niagara 2（UltraSPARC T2）处理器具有以下特点和优势：

1. **多核多线程**：Niagara 2 处理器具有多个核心，每个核心能够同时执行多个硬件线程。这种设计极大地提高了线程密集型应用的处理能力，特别是在面对大规模并行处理任务时。

2. **集成网络和安全功能**：UltraSPARC T2 是首批将关键系统功能集成到单个芯片上的处理器之一，包括网络和安全功能。这减少了对外部组件的依赖，降低了延迟并提高了效率。

3. **能源效率**：尽管提供了高度并行的处理能力，Niagara 2 处理器也非常注重能源效率，这对于减少数据中心的运营成本至关重要。

4. **针对吞吐量优化**：Niagara 2 处理器特别适合运行多任务和需要高吞吐量的应用，如Web服务、数据库和商业应用。

在多核处理器领域，Niagara 2 的这些优势使其成为处理大量并发任务和数据密集型工作负载的理想选择。对于并发数据结构和算法的设计来说，这意味着可以利用处理器的高线程密集度来优化性能，尤其是在任务可以被分解为许多小的、并行的工作单元时。然而，这也带来了挑战，因为开发者需要考虑如何有效地管理这么多的线程，并确保算法能够在高线程环境下正常工作。

2. 编译器&OS选择

在MC机器上选择gcc 4.3.4， linux内核版本2.6.18。在Niagara2机器上选择gcc 4.5.1，OS选择Solaris 10，内存分配器选择Hoard Memory allocator。

Hoard 是一个高性能的内存分配器，它专门为多线程应用程序设计，以解决传统内存分配器在多线程环境中可能遇到的性能问题，如内存膨胀（memory bloat）和锁争用（lock contention）。Hoard 最初由 Emery Berger 教授开发，旨在提高并发程序在动态内存分配方面的效率。

### Hoard 内存分配器的特点：

1.  **线程局部性**：Hoard 将内存分配到各个线程的本地堆中，这样每个线程都可以在自己的堆上分配和释放内存，减少了不同线程间的锁争用。
1.  **全局堆**：除了线程局部堆之外，Hoard 还维护了一个全局堆，用于处理大型内存请求和在线程之间平衡内存。
1.  **低内存膨胀**：Hoard 通过精心设计的内存分配策略来减少内存膨胀现象，即过度消耗内存空间的问题。
1.  **避免假共享**：Hoard 分配器试图避免分配在同一缓存线上的内存块给不同的线程，从而减少了多处理器系统中的假共享问题。

### 相比 Linux 自带的内存分配器的好处：

Linux 自带的内存分配器（如 glibc 中的 ptmalloc）在单线程应用中表现良好，但在多线程环境中可能会遇到性能瓶颈。相比之下，Hoard 分配器提供了以下好处：

1.  **减少锁争用**：通过为每个线程提供独立的堆，Hoard 减少了多线程环境中的锁争用，从而提高了并发性能。
1.  **控制内存膨胀**：Hoard 通过有效的内存管理策略减少了内存膨胀，这对于内存敏感的应用尤其重要。
1.  **提高缓存效率**：通过避免假共享，Hoard 可以提高缓存效率，因为它减少了不同线程对同一缓存线的竞争。
1.  **跨平台**：Hoard 可以在多种操作系统上运行，它不仅限于 Linux，这使得它适用于更广泛的场景。

Hoard 分配器适用于多线程密集型的应用程序，尤其是在多核处理器上运行的那些应用。它通过减少锁争用和内存膨胀来提高性能，这在标准的内存分配器中可能是一个挑战。然而，随着 Linux 内核和 glibc 的不断发展，它们也在不断引入新的优化和改进，以提高多线程环境下的性能。因此，选择哪个内存分配器取决于特定应用的需求和工作负载特性。

另外，测试选择了绑核thread binding技术，如果不这么做，当处理器数量 > 线程数时，两个线程可能在相同核心上执行，也可能在不同核心上执行(scheduler调度器决定)。在相同核心执行的额外开销比在不同核心执行低一个数量级。(不同核心执行意味着线程1的缓存完全失效了，线程1如果取用elem1, 2, 3，线程2也取用elem2，3，4。那么如果在同一个核心上，elem2和elem3可以享受到本地缓存)。

类似的，还有多核心，多芯片，多槽位。每种组合下核心之间的额外开销都不同，因此都需要相同配置。在Niagara2的处理器中，作者将所有核心分为两组，每组位于同一个slot。

3. 和哪些算法斗蛐蛐

当然是和最先进的比(2012年之前的所有并发算法)

P-Sim 基于Fetch&add作为构建块的wait-free算法
flat-combine 基于CAS作为原语，轮询任务的做法比较类似网络多路复用里的Select
CLH 自旋锁使用一个虚拟队列巧妙的处理了CAS缓存命中率差的情况。
OyamaAlg 使用CAS作为combiner的选举
lock-free实现，就是简单的用CAS代替锁的实现，没有任何定制/优化。

测试中，假设每个算法执行的操作是"取并做乘法(Fetch&Multiple)"这样的操作，这个应该是RMW, 还是只取，做乘法是在线程内执行，不写回？

Niagara2 由于不支持Fetch&Add，所以P-Sim跑不了。

最后，还有

用CAS代替Swap的lock-free版本CC-Synch

后面我们会看到，并不是"无锁"就意味着性能好，基于原子Swap(锁)实现的算法要比基于CAS(无锁)的性能普遍好。

在Niagara2中，作者用H-Synch和层次化的锁结构进行了斗蛐蛐。由于MC这个机器上没有明确的层级概念(可以理解为MC这个机器是由一个由非常多个处理器组成的单个cluster组成，由于cluster个数比较少，不具备层次概念。)

在多核处理器的上下文中，“层次”（hierarchical）通常指的是处理器内部组件的物理和逻辑组织方式，这种组织方式反映了不同组件之间的关系、通信路径和性能特征。处理器的层次结构可以包括核心、缓存、内存控制器、互连网络等多个层面。

### 多核处理器中的层次结构可能包含：

1.  **核心层（Core Layer）** ： 包含独立的处理器核心，每个核心可能具有自己的局部缓存（L1和L2缓存）。
1.  **缓存层（Cache Layer）** ： 包括共享缓存（如L3缓存），它可以被同一处理器芯片上的多个核心共享。
1.  **内存控制器层（Memory Controller Layer）** ： 负责管理处理器和主内存之间的数据交换。
1.  **互连层（Interconnect Layer）** ： 提供核心、缓存和内存控制器之间的通信路径，例如使用快速互连如Intel的QuickPath Interconnect（QPI）或AMD的HyperTransport。

### 多个集群（Clusters）的处理器如何划分为多个层次：

多集群的处理器是指一个处理器芯片包含多个独立的核心集群，每个集群可能有自己的一组资源，如缓存和内存控制器。这种设计通常用于提高处理器的可扩展性和性能。

划分多个层次的过程可能包括：

1.  **按性能划分**： 高性能核心和低功耗核心可以分为不同的集群，以便根据不同的性能需求进行优化。
1.  **按资源划分**： 每个集群可能有自己的缓存层次和内存控制器，以减少不同集群之间的资源竞争。
1.  **按物理位置划分**： 芯片上不同的物理位置可能形成不同的集群，每个集群内部的核心通信延迟较低，而跨集群通信可能需要更长的时间。
1.  **按功能划分**： 特定功能或特殊硬件加速器可能被划分为独立的集群，以提供特殊的计算能力或支持特定类型的工作负载。

多集群处理器的层次化设计使得它们能够更好地处理多种类型的应用和工作负载，提高了资源利用率和能源效率。然而，这种设计也增加了编程和资源管理的复杂性，因为开发者需要考虑数据在不同层次和集群之间的移动和优化。

所以，作者不在MC这个架构比对H-Synch的性能。

另外，作者会根据具体的体系结构，对基于CAS的实现进行调优(比如设置退避规则 back-off)。以保证每个算法都是不吃亏的(否则没法让人信服自己的算法的确比其他的厉害)。

同时，作者还对flat-combiner的实现在源代码级别进行优化，以保证所有算法都是以满状态站在起跑线的。

4. 测试流程，测试的维度

这个测试流程和MSQueue非常像，都是取一秒钟10^7 个操作，分配给n个线程来做，相当于每个线程分到10^7 / n个操作。当然每个操作都是Fetch&Multiply。

作者重复上面的流程N次，最终压测结果取平均值。同时对于相同core上的执行，作者插入了一段no-op。

同时，作者还给出了"随机workload"的测试版本，因为对于固定数量且固定操作，平均缓存命中率肯定很高，这不符合实际生产。同时固定数量的操作，还可能存在long-run现象，一个线程一直执行操作而不及时的切换给另一个combiner。

1. 吞吐量

反应算法每秒可以处理多少操作

横坐标是线程数量(既然采取了绑核，那自然就是核心数量)。两个图标分别表示基于Niagara2 和 Magny Cours的机器。

几个注意点

可以看到CC-Synch遥遥领先，尽管DSM-Synch适用于 DSM的处理器架构，但在Magny Cours Machines上依然遥遥领先。
如果用CAS代替CC-Synch里的Swap实现无锁算法，性能反倒下降2倍。

Figure2的注意点

FC-MCS 是层次化的MCS Lock实现，可以看到在NUMA架构中，依然不敌CC-Synch。也就是专业人员输给了非专业的人员。作者分析原因可能是FC-MCS的缓存命中率比较低，其次没有采取combiner的处理方法。这里combiner可以理解成一个线程要么不处理，要么处理一批。批处理不仅有利于效率，一个线程处理请求更有良好的缓存命中率。
H-Synch遥遥领先，不仅利用了多Cluster处理器的层次架构，设计上还能保证combiner批处理，并且缓存友好。
基于CAS的CC-Synch直接没展示，因为CAS在NUMA体系是一个非常差的原语，性能低到爆炸。

Figure3: 在超多线程时各算法的表现

H-Synch也是相对领先，但最后几个算法收敛到一点上了（可以回顾下这是哪个定律）答案 amdahl's law，这个定律告诉我们，并发算法的扩展性不是无限大的，终归会收敛到一点上。
FC-MCS 和CLH Lock在这样的case下性能极差，不展示了直接。

2. 单操作的平均原子操作个数

Figure5解读:

OyamaAlg和Lock-Free都是基于CAS的, 尽管作者进行了调优，选择了更适合的back-off时间，但还是需要较多的原子操作次数(CAS在hotspot时频繁重试)，这就是CAS算法劣势的根源之一（还有其他劣势为缓存不友好，CLH和MCS是针对缓存不友好进行的优化）。

3. 单combiner的 combine度

简单理解就是，一个combiner每次执行多少操作，也就是批操作里批的大小

CC-Synch和H-Synch比P-Sim厉害3倍
可以通过调优实现更高的combine degree，比如提高combine轮次(? 是说每轮处理更多请求)以及改变轮询级别(? 是说更快的处理队列里的请求)。但注意combine degree越大，不意味着吞吐量越大，这个应该是经验之谈，反正二者不是正相关。
Flat-Combine中，我们可以看到combine-degree大致上就是线程数，这是因为flat-combine的实现中，维护了一个线程列表，类似Select那样，因此最多可以有多少个线程同时执行，其combine-degree就是最多的线程数。
我们没展示OyamaAlg，是因为它的combine-degree是无限大，因为这个算法，只要有请求加入，combiner就会处理，不管这个过程是不是无底洞(也就是combiner本身可能starve)

4. 随机操作性能

现在测试为 "固定线程数(32个)时，执行超多的随机操作"。

Figure6解读:

当随机操作的个数比较小的时候，可以看到多数线程都是平稳的，此时主要的开销是 CPU间的通信，而不是操作本身。而当随机操作数比较大时，所有算法都有一些下降，这主要是循环操作的开销大于了CPU间的通信，此时随着随机工作的个数增加，吞吐量随之下降。
基于CAS的实现中(lock-free), Flat-combine在随机工作数非常小时，有不正常的性能表现(非常高)，这是因为存在long-run, 此时算法表现为操作都被单一线程执行了，这自然会让性能虚高。

5. 各算法的缓存命中率

Table1解读

可以看到，flat-combine相比基于Swap的CC-Synch和基于Fetch&Add的Sim算法，缓存命中率尤其差。这是因为CAS本身的缓存不友好 + 分支预测不友好导致的。

因此我们要采取combine-base尽量让一个combiner执行尽可能多的request，然后其他的线程自旋在自己关注的内存地址上(避免了多个线程自旋在同一个共享地址上导致的较大的缓存未命中率+分支预测失败)。

5. 其他的数据结构

首先我们理解下层级关系

并发原语级别，e.g. CAS, Swap, Fetch&Add, ...
算法实现级别: Flat-Combiner, CC-Synch, DSM-Synch
数据结构级别: 将算法应用在数据结构的具体操作上。

其中，并发原语可以互相模拟 e.g. 用CAS模拟Swap，比较强的原语可以模拟比较弱的原语，比较弱的原语配合一定的业务逻辑理论上也可以达成比较强的原语(但是是在用户态完成的，而不是硬件支持)。

而并发原语是构建并发算法的基石。

并发算法又是构建并发容器的基石。

CC-Synch也好，H-Synch也好，都是算法实现级别的，自然可以基于此构造并发结构。

作者给出了

CC-Stack，一个共享的，基于CC-Synch实现的栈结构。竞品是基于P-Sim实现的SimStack和基于CLH Lock实现的栈，基于Flat-Combining实现的栈，称为FC-Stack。

栈在实现上使用了eliminate 优化，也就是如果序列是push(xx), pop(), 那么combiner会直接优化掉(中心化执行的好处)

FC-MCS和H-Synch实现的栈，适用于Niagara2这种支持层级化的体系结构。

和上面一样，上面是对于算法本身的测试，也就是单个请求就是取数+乘法。现在结合具体的并发结构，那么单个请求可能是enqueue，或者dequeue。

作者的测试方法是，每秒10^7个请求，交给n个线程，相同线程的执行插入一个 <= 64次的no-op操作。

1. 吞吐量

Figure7 解读

我们的几个算法还是遥遥领先啊。这个没啥说的

Figure8 解读

现在是在NUMA架构中，可以看到

H-Synch遥遥领先，这个没毛病，利用到了层级结构。
CC-Synch和DSM-Synch比 FCMCS还厉害，FCMCS是专门在层次结构架构中设计的，专用设计没打过通用的。

除了CC-Stack，作者还实现了CC-Queue，同时请出了我们的老朋友MS-Queue，在MS-Queue有一个双锁的实现，回顾下MS-Queue的无锁实现是一个基于CAS+双指针的线性算法，有锁实现基于double-lock进行了优化。作者继续优化这个双锁实现: 把锁换成CC-Synch。

Figure 9 解读

排行榜

CC-Queue和DSM-Queue还是遥遥领先
SimQueue P-Sim作为整个文章中，唯一被作者"夸厉害"的算法，紧追其后
FC-Queue作为combine-based的实现，相比CAS有更多优势，紧追其后。
最后是Two-locks Queue也经过了CC-Synch的优化，老末是老朋友MS-Queue

Figure10 解读

H-Queue遥遥领先
其次是CC-Queue和DSM-Queue。CC-Queue比DSM-Queue厉害一点。在这个体系中，基于CLH的CC-Synch更吃香
老朋友SimQueue不在，是因为Niagara2不支持Fetch&Add
FC-Queue比FCMCS-Queue差一点，因为后者利用了层次关系，但即便是在专业领域也打不过非专业的CC-Queue和DSM-Queue