Anarkh的知识库

Exchanger是用于线程协作的工具类, 主要用于两个线程之间的数据交换。@anarkh

带着BAT大厂的面试问题去理解Exchanger
Exchanger简介
Exchanger实现机制
Exchanger源码解析
参考文章

带着BAT大厂的面试问题去理解Exchanger

提示

请带着这些问题继续后文，会很大程度上帮助你更好的理解Exchanger。@anarkh

Exchanger主要解决什么问题?
对比SynchronousQueue，为什么说Exchanger可被视为 SynchronousQueue 的双向形式?
Exchanger在不同的JDK版本中实现有什么差别?
Exchanger实现机制?
Exchanger已经有了slot单节点，为什么会加入arena node数组? 什么时候会用到数组?
arena可以确保不同的slot在arena中是不会相冲突的，那么是怎么保证的呢?
什么是伪共享，Exchanger中如何体现的?
Exchanger实现举例

Exchanger简介

Exchanger用于进行两个线程之间的数据交换。它提供一个同步点，在这个同步点，两个线程可以交换彼此的数据。这两个线程通过exchange()方法交换数据，当一个线程先执行exchange()方法后，它会一直等待第二个线程也执行exchange()方法，当这两个线程到达同步点时，这两个线程就可以交换数据了。

Exchanger实现机制

java

for (;;) {
    if (slot is empty) { 
        
        place item in a Node;
        if (can CAS slot from empty to node) {
            
            wait for release;
            
            return matching item in node;
        }
    } else if (can CAS slot from node to empty) { 
         
        
        get the item in node;
        set matching item in node;
        
        release waiting thread;
    }
    
}

比如有2条线程A和B，A线程交换数据时，发现slot为空，则将需要交换的数据放在slot中等待其它线程进来交换数据，等线程B进来，读取A设置的数据，然后设置线程B需要交换的数据，然后唤醒A线程，原理就是这么简单。但是当多个线程之间进行交换数据时就会出现问题，所以Exchanger加入了slot数组。

Exchanger源码解析

内部类 - Participant

java

static final class Participant extends ThreadLocal&lt;Node&gt; {
    public Node initialValue() { return new Node(); }
}

Participant的作用是为每个线程保留唯一的一个Node节点, 它继承ThreadLocal，说明每个线程具有不同的状态。

内部类 - Node

java

@sun.misc.Contended static final class Node {
     
    int index; 
    
    int bound; 
    
    int collides;
    
    int hash; 
    
    Object item; 
    
    volatile Object match; 
    
    volatile Thread parked;
}

在Node定义中有两个变量值得思考：bound以及collides。前面提到了数组area是为了避免竞争而产生的，如果系统不存在竞争问题，那么完全没有必要开辟一个高效的arena来徒增系统的复杂性。首先通过单个slot的exchanger来交换数据，当探测到竞争时将安排不同的位置的slot来保存线程Node，并且可以确保没有slot会在同一个缓存行上。如何来判断会有竞争呢? CAS替换slot失败，如果失败，则通过记录冲突次数来扩展arena的尺寸，我们在记录冲突的过程中会跟踪“bound”的值，以及会重新计算冲突次数在bound的值被改变时。

核心属性

java

private final Participant participant;
private volatile Node[] arena;
private volatile Node slot;

为什么会有arena数组槽?

slot为单个槽，arena为数组槽, 他们都是Node类型。在这里可能会感觉到疑惑，slot作为Exchanger交换数据的场景，应该只需要一个就可以了啊? 为何还多了一个Participant 和数组类型的arena呢? 一个slot交换场所原则上来说应该是可以的，但实际情况却不是如此，多个参与者使用同一个交换场所时，会存在严重伸缩性问题。既然单个交换场所存在问题，那么我们就安排多个，也就是数组arena。通过数组arena来安排不同的线程使用不同的slot来降低竞争问题，并且可以保证最终一定会成对交换数据。但是Exchanger不是一来就会生成arena数组来降低竞争，只有当产生竞争是才会生成arena数组 。

那么怎么将Node与当前线程绑定呢？

Participant，Participant 的作用就是为每个线程保留唯一的一个Node节点，它继承ThreadLocal，同时在Node节点中记录在arena中的下标index。

构造函数

java

public Exchanger() {
    participant = new Participant();
}

初始化participant对象。

核心方法 - exchange(V x)

等待另一个线程到达此交换点(除非当前线程被中断)，然后将给定的对象传送给该线程，并接收该线程的对象。

java

public V exchange(V x) throws InterruptedException {
    Object v;
    
    Object item = (x == null) ? NULL_ITEM : x; 
    
    if ((arena != null ||
            (v = slotExchange(item, false, 0 L)) == null) &&
        ((Thread.interrupted() || 
            (v = arenaExchange(item, false, 0 L)) == null)))
        throw new InterruptedException();
    return (v == NULL_ITEM) ? null : (V) v;
}

这个方法比较好理解：arena为数组槽，如果为null，则执行slotExchange()方法，否则判断线程是否中断，如果中断值抛出InterruptedException异常，没有中断则执行arenaExchange()方法。整套逻辑就是：如果slotExchange(Object item, boolean timed, long ns)方法执行失败了就执行arenaExchange(Object item, boolean timed, long ns)方法，最后返回结果V。

NULL_ITEM 为一个空节点，其实就是一个Object对象而已，slotExchange()为单个slot交换。

slotExchange(Object item, boolean timed, long ns)

java

private final Object slotExchange(Object item, boolean timed, long ns) {
    
    Node p = participant.get();
    
    Thread t = Thread.currentThread();
    
    if (t.isInterrupted()) 
        return null;
	
    for (Node q;;) {
        
        if ((q = slot) != null) {
             
			
            if (U.compareAndSwapObject(this, SLOT, q, null)) {
                
                
                Object v = q.item;
                
                q.match = item;
                 
                Thread w = q.parked;
                if (w != null)
                    
                    U.unpark(w);
                
                return v;
            }
            
            
            
            
            if (NCPU > 1 && bound == 0 &&
                U.compareAndSwapInt(this, BOUND, 0, SEQ))
                
                arena = new Node[(FULL + 2) << ASHIFT];
        }
        
		
        else if (arena != null)
            
            return null; 
        else {
            
            
            
            p.item = item;
            
            if (U.compareAndSwapObject(this, SLOT, null, p))
                
                break;
            
            
            p.item = null;
        }
    }

    
    
    
    int h = p.hash;
    long end = timed ? System.nanoTime() + ns : 0 L;
    
    int spins = (NCPU > 1) ? SPINS : 1;
    Object v;
    
    while ((v = p.match) == null) {
        
        if (spins > 0) {
            h ^= h << 1;
            h ^= h >>> 3;
            h ^= h << 10;
            if (h == 0)
                h = SPINS | (int) t.getId();
            else if (h < 0 && (--spins & ((SPINS >>> 1) - 1)) == 0)
                Thread.yield();
        } else if (slot != p)
            spins = SPINS;
        
        else if (!t.isInterrupted() && arena == null &&
            (!timed || (ns = end - System.nanoTime()) > 0 L)) {
            
            U.putObject(t, BLOCKER, this);
            
            p.parked = t;
            if (slot == p)
                
                U.park(false, ns);
            
            p.parked = null;
            
            U.putObject(t, BLOCKER, null);
        
        } else if (U.compareAndSwapObject(this, SLOT, p, null)) {
             
            v = timed && ns &lt;= 0 L && !t.isInterrupted() ? TIMED_OUT : null;
            break;
        }
    }
    
    U.putOrderedObject(p, MATCH, null);
    
    p.item = null;
    p.hash = h;
    
    return v;
}

程序首先通过participant获取当前线程节点Node。检测是否中断，如果中断return null，等待后续抛出InterruptedException异常。

如果slot不为null，则进行slot消除，成功直接返回数据V，否则失败，则创建arena消除数组。
如果slot为null，但arena不为null，则返回null，进入arenaExchange逻辑。
如果slot为null，且arena也为null，则尝试占领该slot，失败重试，成功则跳出循环进入spin+block(自旋+阻塞)模式。

在自旋+阻塞模式中，首先取得结束时间和自旋次数。如果match(做releasing操作的线程传递的项)为null，其首先尝试spins+随机次自旋(改自旋使用当前节点中的hash，并改变之)和退让。当自旋数为0后，假如slot发生了改变(slot != p)则重置自旋数并重试。否则假如：当前未中断&arena为null&(当前不是限时版本或者限时版本+当前时间未结束)：阻塞或者限时阻塞。假如：当前中断或者arena不为null或者当前为限时版本+时间已经结束：不限时版本：置v为null；限时版本：如果时间结束以及未中断则TIMED_OUT；否则给出null(原因是探测到arena非空或者当前线程中断)。

match不为空时跳出循环。

arenaExchange(Object item, boolean timed, long ns)

此方法被执行时表示多个线程进入交换区交换数据，arena数组已被初始化，此方法中的一些处理方式和slotExchange比较类似，它是通过遍历arena数组找到需要交换的数据。

java

private final Object arenaExchange(Object item, boolean timed, long ns) {
    Node[] a = arena;
    
    Node p = participant.get();
    
    for (int i = p.index;;) { 
        
        int b, m, c;
        long j; 
        
        
        Node q = (Node) U.getObjectVolatile(a, j = (i << ASHIFT) + ABASE);
        
        if (q != null && U.compareAndSwapObject(a, j, q, null)) {
            
            Object v = q.item; 
            q.match = item;
            Thread w = q.parked;
            if (w != null)
                U.unpark(w);
            return v;
        
        } else if (i &lt;= (m = (b = bound) & MMASK) && q == null) {
             
            p.item = item; 
            if (U.compareAndSwapObject(a, j, null, p)) {
                
                long end = (timed && m == 0) ? System.nanoTime() + ns : 0 L;
                Thread t = Thread.currentThread(); 
                
                for (int h = p.hash, spins = SPINS;;) {
                    Object v = p.match;
                    if (v != null) {
                        
                        
                        U.putOrderedObject(p, MATCH, null);
                        p.item = null; 
                        p.hash = h;
                        return v;
                    } else if (spins > 0) {
                        h ^= h << 1;
                        h ^= h >>> 3;
                        h ^= h << 10; 
                        if (h == 0) 
                            h = SPINS | (int) t.getId();
                        else if (h < 0 && 
                            (--spins & ((SPINS >>> 1) - 1)) == 0)
                            Thread.yield(); 
                    } else if (U.getObjectVolatile(a, j) != p)
                        
                       
                        spins = SPINS; 
                    else if (!t.isInterrupted() && m == 0 &&
                        (!timed ||
                            (ns = end - System.nanoTime()) > 0 L)) {
                        
                        U.putObject(t, BLOCKER, this); 
                         
                        p.parked = t; 
                        if (U.getObjectVolatile(a, j) == p)
                            
                            U.park(false, ns);
                        p.parked = null;
                         
                        U.putObject(t, BLOCKER, null);
                    } else if (U.getObjectVolatile(a, j) == p &&
                        U.compareAndSwapObject(a, j, p, null)) {
                        
                        if (m != 0) 
                            U.compareAndSwapInt(this, BOUND, b, b + SEQ - 1);
                        p.item = null;
                        p.hash = h;
                        i = p.index >>>= 1; 
                        if (Thread.interrupted())
                            return null;
                        if (timed && m == 0 && ns &lt;= 0 L)
                            return TIMED_OUT;
                        break; 
                    }
                }
            } else
                
                p.item = null; 
        } else {
            
           
            if (p.bound != b) { 
                p.bound = b;
                p.collides = 0;
                
                i = (i != m || m == 0) ? m : m - 1;
            } else if ((c = p.collides) < m || m == FULL ||
                !U.compareAndSwapInt(this, BOUND, b, b + SEQ + 1)) {
                 
                p.collides = c + 1;
                
                i = (i == 0) ? m : i - 1; 
            } else
                
                i = m + 1; 
            
            p.index = i;
        }
    }
}

首先通过participant取得当前节点Node，然后根据当前节点Node的index去取arena中相对应的节点node。

前面提到过arena可以确保不同的slot在arena中是不会相冲突的，那么是怎么保证的呢？

java

arena = new Node[(FULL + 2) << ASHIFT];

static final int FULL = (NCPU &gt;= (MMASK << 1)) ? MMASK : NCPU >>> 1;
private static final int ASHIFT = 7;

private static final int NCPU = Runtime.getRuntime().availableProcessors();
private static final int MMASK = 0xff;        


Node q = (Node)U.getObjectVolatile(a, j = (i << ASHIFT) + ABASE);


Class<?> ak = Node[].class;
ABASE = U.arrayBaseOffset(ak) + (1 << ASHIFT);

用@sun.misc.Contended来规避伪共享？

伪共享说明 ：假设一个类的两个相互独立的属性a和b在内存地址上是连续的(比如FIFO队列的头尾指针)，那么它们通常会被加载到相同的cpu cache line里面。并发情况下，如果一个线程修改了a，会导致整个cache line失效(包括b)，这时另一个线程来读b，就需要从内存里再次加载了，这种多线程频繁修改ab的情况下，虽然a和b看似独立，但它们会互相干扰，非常影响性能。

我们再看Node节点的定义, 在Java 8 中我们是可以利用sun.misc.Contended来规避伪共享的。所以说通过 << ASHIFT方式加上sun.misc.Contended，所以使得任意两个可用Node不会再同一个缓存行中。

java

@sun.misc.Contended static final class Node{
....
}

我们再次回到arenaExchange()。取得arena中的node节点后，如果定位的节点q 不为空，且CAS操作成功，则交换数据，返回交换的数据，唤醒等待的线程。

如果q等于null且下标在bound & MMASK范围之内，则尝试占领该位置，如果成功，则采用自旋 + 阻塞的方式进行等待交换数据。
如果下标不在bound & MMASK范围之内获取由于q不为null但是竞争失败的时候：消除p。加入bound 不等于当前节点的bond(b != p.bound)，则更新p.bound = b，collides = 0 ，i = m或者m - 1。如果冲突的次数不到m 获取m 已经为最大值或者修改当前bound的值失败，则通过增加一次collides以及循环递减下标i的值；否则更新当前bound的值成功：我们令i为m+1即为此时最大的下标。最后更新当前index的值。

更深入理解

SynchronousQueue对比？

Exchanger是一种线程间安全交换数据的机制。可以和之前分析过的SynchronousQueue对比一下：线程A通过SynchronousQueue将数据a交给线程B；线程A通过Exchanger和线程B交换数据，线程A把数据a交给线程B，同时线程B把数据b交给线程A。可见，SynchronousQueue是交给一个数据，Exchanger是交换两个数据。

不同JDK实现有何差别？
在JDK5中Exchanger被设计成一个容量为1的容器，存放一个等待线程，直到有另外线程到来就会发生数据交换，然后清空容器，等到下一个到来的线程。
从JDK6开始，Exchanger用了类似ConcurrentMap的分段思想，提供了多个slot，增加了并发执行时的吞吐量。

JDK1.6实现可以参考这里在新窗口打开

Exchanger示例

来一个非常经典的并发问题：你有相同的数据buffer，一个或多个数据生产者，和一个或多个数据消费者。只是Exchange类只能同步2个线程，所以你只能在你的生产者和消费者问题中只有一个生产者和一个消费者时使用这个类。

java

public class Test {
    static class Producer extends Thread {
        private Exchanger&lt;Integer&gt; exchanger;
        private static int data = 0;
        Producer(String name, Exchanger&lt;Integer&gt; exchanger) {
            super("Producer-" + name);
            this.exchanger = exchanger;
        }

        @Override
        public void run() {
            for (int i=1; i<5; i++) {
                try {
                    TimeUnit.SECONDS.sleep(1);
                    data = i;
                    System.out.println(getName()+" 交换前:" + data);
                    data = exchanger.exchange(data);
                    System.out.println(getName()+" 交换后:" + data);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    static class Consumer extends Thread {
        private Exchanger&lt;Integer&gt; exchanger;
        private static int data = 0;
        Consumer(String name, Exchanger&lt;Integer&gt; exchanger) {
            super("Consumer-" + name);
            this.exchanger = exchanger;
        }

        @Override
        public void run() {
            while (true) {
                data = 0;
                System.out.println(getName()+" 交换前:" + data);
                try {
                    TimeUnit.SECONDS.sleep(1);
                    data = exchanger.exchange(data);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(getName()+" 交换后:" + data);
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Exchanger&lt;Integer&gt; exchanger = new Exchanger&lt;Integer&gt;();
        new Producer("", exchanger).start();
        new Consumer("", exchanger).start();
        TimeUnit.SECONDS.sleep(7);
        System.exit(-1);
    }
}

可以看到，其结果可能如下：

html

Consumer- 交换前:0
Producer- 交换前:1
Consumer- 交换后:1
Consumer- 交换前:0
Producer- 交换后:0
Producer- 交换前:2
Producer- 交换后:0
Consumer- 交换后:2
Consumer- 交换前:0
Producer- 交换前:3
Producer- 交换后:0
Consumer- 交换后:3
Consumer- 交换前:0
Producer- 交换前:4
Producer- 交换后:0
Consumer- 交换后:4
Consumer- 交换前:0

带着BAT大厂的面试问题去理解Exchanger ​

Exchanger简介 ​

Exchanger实现机制 ​

Exchanger源码解析 ​

内部类 - Participant ​

内部类 - Node ​

核心属性 ​

构造函数 ​

核心方法 - exchange(V x) ​

slotExchange(Object item, boolean timed, long ns) ​

arenaExchange(Object item, boolean timed, long ns) ​

更深入理解 ​

Exchanger示例 ​

参考文章 ​

带着BAT大厂的面试问题去理解Exchanger

Exchanger简介

Exchanger实现机制

Exchanger源码解析

内部类 - Participant

内部类 - Node

核心属性

构造函数

核心方法 - exchange(V x)

slotExchange(Object item, boolean timed, long ns)

arenaExchange(Object item, boolean timed, long ns)

更深入理解

Exchanger示例

参考文章