12-J.U.C之并发工具类：Exchanger

阳光穿透心脏的1/2处 2021-08-29 23:55 316阅读 0赞

### Exchanger ###

*  1. 简介
 *  2. 应用示例
 *  3. 实现分析
 *  4. exchange(V x)
 *   *  4.1 slotExchange(Object item, boolean timed, long ns)
     *  4.2 arenaExchange(Object item, boolean timed, long ns)

# 1. 简介 #

`Exchanger`是最简单的也是最复杂的，简单在于`API`非常简单，就一个构造方法和两个`exchange()`方法，最复杂在于它的实现是最复杂的。

在`API`是这么介绍的：可以在对其中元素进行配对和交换。每个线程将条目上的某个方法呈现给 `exchange`方法，与伙伴线程进行匹配，并且在返回时接收其伙伴的对象。

`Exchanger` 可能被视为 `SynchronousQueue` 的双向形式。`Exchanger` 可能在应用程序（比如遗传算法和管道设计）中很有用。`Exchanger`，它允许在并发任务之间交换数据。

具体来说，`Exchanger`类允许在两个线程之间定义同步点。当两个线程都到达同步点时，他们交换数据结构，因此第一个线程的数据结构进入到第二个线程中，第二个线程的数据结构进入到第一个线程中。

# 2. 应用示例 #

我们用`Exchangee`来模拟生产者-消费者问题：

import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.Exchanger;
    
    /** * @author wangzhao * @date 2020/6/4 11:30 */
    public class ExchangerTest { 
    
        static class Producer implements Runnable{ 
    
            //生产者、消费者交换的数据结构
            private List<String> buffer;
    
            //生产者和消费者的交换对象
            private Exchanger<List<String>> exchanger;
    
            Producer(List<String> buffer,Exchanger<List<String>> exchanger){ 
                this.buffer = buffer;
                this.exchanger = exchanger;
            }
    
            @Override
            public void run() { 
                for(int i = 1 ; i < 5 ; i++){ 
                    System.out.println("生产者第" + i + "次提供");
                    for(int j = 1 ; j <= 3 ; j++){ 
                        System.out.println("生产者装入" + i  + "--" + j);
                        buffer.add("buffer：" + i + "--" + j);
                    }
    
                    System.out.println("生产者装满，等待与消费者交换...");
                    try { 
                        exchanger.exchange(buffer);
                    } catch (InterruptedException e) { 
                        e.printStackTrace();
                    }
                }
            }
        }
    
        static class Consumer implements Runnable { 
            private List<String> buffer;
    
            private final Exchanger<List<String>> exchanger;
    
            public Consumer(List<String> buffer, Exchanger<List<String>> exchanger) { 
                this.buffer = buffer;
                this.exchanger = exchanger;
            }
    
            @Override
            public void run() { 
                for (int i = 1; i < 5; i++) { 
                    //调用exchange()与生产者进行数据交换
                    try { 
                        buffer = exchanger.exchange(buffer);
                    } catch (InterruptedException e) { 
                        e.printStackTrace();
                    }
    
                    System.out.println("消费者第" + i + "次提取");
                    for (int j = 1; j <= 3 ; j++) { 
                        System.out.println("消费者 : " + buffer.get(0));
                        buffer.remove(0);
                    }
                }
            }
        }
    
        public static void main(String[] args){ 
            List<String> buffer1 = new ArrayList<String>();
            List<String> buffer2 = new ArrayList<String>();
    
            Exchanger<List<String>> exchanger = new Exchanger<List<String>>();
    
            Thread producerThread = new Thread(new Producer(buffer1,exchanger));
            Thread consumerThread = new Thread(new Consumer(buffer2,exchanger));
    
            producerThread.start();
            consumerThread.start();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]

首先生产者`Producer`、消费者`Consumer`首先都创建一个缓冲列表，通过`Exchanger`来同步交换数据。

消费中通过调用`Exchanger`与生产者进行同步来获取数据，而生产者则通过`for`循环向缓存队列存储数据并使用`exchanger`对象消费者同步。到消费者从`exchanger`哪里得到数据后，他的缓冲列表中有`3`个数据，而生产者得到的则是一个空的列表。

上面的例子充分展示了消费者-生产者是如何利用`Exchanger`来完成数据交换的。

在`Exchanger`中，如果一个线程已经到达了`exchanger`节点时，对于它的伙伴节点的情况有三种：

1.  如果它的伙伴节点在该线程到达之前已经调用了`exchanger`方法，则它会唤醒它的伙伴然后进行数据交换，得到各自数据返回。
2.  如果它的伙伴节点还没有到达交换点，则该线程将会被挂起，等待它的伙伴节点到达被唤醒，完成数据交换。
3.  如果当前线程被中断了则抛出异常，或者等待超时了，则抛出超时异常。

# 3. 实现分析 #

`Exchanger`算法的核心是通过一个可交换数据的`slot`，以及一个可以带有数据`item`的参与者。

源码中的描述如下：

for (;;) { 
        if (slot is empty) {                        // offer
            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) {  // release
            get the item in node;
            set matching item in node;
            release waiting thread;
        }
        // else retry on CAS failure
    }

`Exchanger`中定义了如下几个重要的成员变量：

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

`participant`的作用是为每个线程保留唯一的一个`Node`节点。`slot`为单个槽，`arena`为数组槽。他们都是Node类型。在这里可能会感觉到疑惑，`slot`作为`Exchanger`交换数据的场景，应该只需要一个就可以了啊？为何还多了一个`Participant`和数组类型的`arena`呢？

一个`slot`交换场所原则上来说应该是可以的，但实际情况却不是如此，多个参与者使用同一个交换场所时，会存在严重伸缩性问题。既然单个交换场所存在问题，那么我们就安排多个，也就是数组`arena`。通过数组`arena`来安排不同的线程使用不同的`slot`来降低竞争问题，并且可以保证最终一定会成对交换数据。但是`Exchanger`不是一来就会生成`arena`数组来降低竞争，只有当产生竞争是才会生成`arena`数组。那么怎么将`Node`与当前线程绑定呢？`Participant`，`Participant`的作用就是为每个线程保留唯一的一个`Node`节点，它继承`ThreadLocal`，同时在`Node`节点中记录在`arena`中的下标`index`。

`Node`定义如下：

@sun.misc.Contended static final class Node { 
        int index;              // Arena index
        int bound;              // Last recorded value of Exchanger.bound
        int collides;           // Number of CAS failures at current bound
        int hash;               // Pseudo-random for spins
        Object item;            // This thread's current item
        volatile Object match;  // Item provided by releasing thread
        volatile Thread parked; // Set to this thread when parked, else null
    }

1、index：arena的下标；

2、bound：上一次记录的Exchanger.bound；

3、collides：在当前bound下CAS失败的次数；

4、hash：伪随机数，用于自旋；

5、item：这个线程的当前项，也就是需要交换的数据；

6、match：做releasing操作的线程传递的项；

7、parked：挂起时设置线程值，其他情况下为null；

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

# 4. exchange(V x) #

`exchange(V x)`：等待另一个线程到达此交换点（除非当前线程被中断），然后将给定的对象传送给该线程，并接收该线程的对象。方法定义如下：

public V exchange(V x) throws InterruptedException { 
        Object v;
        Object item = (x == null) ? NULL_ITEM : x; // translate null args
        if ((arena != null ||
             (v = slotExchange(item, false, 0L)) == null) &&
            ((Thread.interrupted() || // disambiguates null return
              (v = arenaExchange(item, false, 0L)) == 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`交换。

## 4.1 slotExchange(Object item, boolean timed, long ns) ##

private final Object slotExchange(Object item, boolean timed, long ns) { 
        // 获取当前线程的节点 p
        Node p = participant.get();
        // 当前线程
        Thread t = Thread.currentThread();
        // 线程中断，直接返回
        if (t.isInterrupted())
            return null;
        // 自旋
        for (Node q;;) { 
            //slot != null
            if ((q = slot) != null) { 
                //尝试CAS替换
                if (U.compareAndSwapObject(this, SLOT, q, null)) { 
                    Object v = q.item;      // 当前线程的项，也就是交换的数据
                    q.match = item;         // 做releasing操作的线程传递的项
                    Thread w = q.parked;    // 挂起时设置线程值
                    // 挂起线程不为null，线程挂起
                    if (w != null)
                        U.unpark(w);
                    return v;
                }
                //如果失败了，则创建arena
                //bound 则是上次Exchanger.bound
                if (NCPU > 1 && bound == 0 &&
                    U.compareAndSwapInt(this, BOUND, 0, SEQ))
                    arena = new Node[(FULL + 2) << ASHIFT];
            }
            //如果arena != null，直接返回，进入arenaExchange逻辑处理
            else if (arena != null)
                return null;
            else { 
                p.item = item;
                if (U.compareAndSwapObject(this, SLOT, null, p))
                    break;
                p.item = null;
            }
        }
    
        /* * 等待 release * 进入spin+block模式 */
        int h = p.hash;
        long end = timed ? System.nanoTime() + ns : 0L;
        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()) > 0L)) { 
                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 <= 0L && !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`(做r`eleasing`操作的线程传递的项)为`null`，其首先尝试`spins+随机次自旋`（改自旋使用当前节点中的hash，并改变之）和退让。当自旋数为`0`后，假如`slot`发生了改变（`slot != p`）则重置自旋数并重试。

否则假如：当前未中断&`arena=null`&（当前不是限时版本或者限时版本+当前时间未结束）：阻塞或者限时阻塞。

假如：当前中断或者`arena!=null`或者当前为限时版本+时间已经结束：不限时版本：置`v`为`null`；限时版本：如果时间结束以及未中断则`TIMED_OUT`；否则给出`null`（原因是探测到`arena`非空或者当前线程中断）。`match`不为空时跳出循环。  
       整个`slotExchange`清晰明了。

## 4.2 arenaExchange(Object item, boolean timed, long ns) ##

private final Object arenaExchange(Object item, boolean timed, long ns) { 
        Node[] a = arena;
        Node p = participant.get();
        for (int i = p.index;;) {                       // access slot at i
            int b, m, c; long j;                       // j is raw array offset
            Node q = (Node)U.getObjectVolatile(a, j = (i << ASHIFT) + ABASE);
            if (q != null && U.compareAndSwapObject(a, j, q, null)) { 
                Object v = q.item;                     // release
                q.match = item;
                Thread w = q.parked;
                if (w != null)
                    U.unpark(w);
                return v;
            }
            else if (i <= (m = (b = bound) & MMASK) && q == null) { 
                p.item = item;                         // offer
                if (U.compareAndSwapObject(a, j, null, p)) { 
                    long end = (timed && m == 0) ? System.nanoTime() + ns : 0L;
                    Thread t = Thread.currentThread(); // wait
                    for (int h = p.hash, spins = SPINS;;) { 
                        Object v = p.match;
                        if (v != null) { 
                            U.putOrderedObject(p, MATCH, null);
                            p.item = null;             // clear for next use
                            p.hash = h;
                            return v;
                        }
                        else if (spins > 0) { 
                            h ^= h << 1; h ^= h >>> 3; h ^= h << 10; // xorshift
                            if (h == 0)                // initialize hash
                                h = SPINS | (int)t.getId();
                            else if (h < 0 &&          // approx 50% true
                                     (--spins & ((SPINS >>> 1) - 1)) == 0)
                                Thread.yield();        // two yields per wait
                        }
                        else if (U.getObjectVolatile(a, j) != p)
                            spins = SPINS;       // releaser hasn't set match yet
                        else if (!t.isInterrupted() && m == 0 &&
                                 (!timed ||
                                  (ns = end - System.nanoTime()) > 0L)) { 
                            U.putObject(t, BLOCKER, this); // emulate LockSupport
                            p.parked = t;              // minimize window
                            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)                // try to shrink
                                U.compareAndSwapInt(this, BOUND, b, b + SEQ - 1);
                            p.item = null;
                            p.hash = h;
                            i = p.index >>>= 1;        // descend
                            if (Thread.interrupted())
                                return null;
                            if (timed && m == 0 && ns <= 0L)
                                return TIMED_OUT;
                            break;                     // expired; restart
                        }
                    }
                }
                else
                    p.item = null;                     // clear offer
            }
            else { 
                if (p.bound != b) {                     // stale; reset
                    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;          // cyclically traverse
                }
                else
                    i = m + 1;                         // grow
                p.index = i;
            }
        }
    }

首先通过`participant`取得当前节点`Node`，然后根据当前节点`Node`的`index`去取`arena`中相对应的节点`node`。前面提到过`arena`可以确保不同的`slot`在`arena`中是不会相冲突的，那么是怎么保证的呢？我们先看`arena`的创建：

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

这个`arena`到底有多大呢？我们先看`FULL` 和`ASHIFT`的定义：

static final int FULL = (NCPU >= (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;      // 255

假如我的机器`NCPU = 8`，则得到的是`768`大小的`arena`数组。然后通过以下代码取得在`arena`中的节点：

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

他仍然是通过右移`ASHIFT`位来取得`Node`的，`ABASE`定义如下：

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

`U.arrayBaseOffse`t获取对象头长度，数组元素的大小可以通过`unsafe.arrayIndexScale(T[].class)`方法获取到。这也就是说要访问类型为`T`的第`N`个元素的话，你的偏移量`offset`应该是`arrayOffset+N*arrayScale`。也就是说`BASE = arrayOffset+ 128` 。其次我们再看`Node`节点的定义

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

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

1.  我先到一个叫做`Slot`的交易场所交易，发现你已经到了，那我就尝试喊你交易，如果你回应了我，决定和我交易那么进入第2步；如果别人抢先一步把你喊走了，那我就进入第5步。
2.  我拿出钱交给你，你可能会接收我的钱，然后把货给我，交易结束；也可能嫌我掏钱太慢(超时)或者接个电话(中断)，TM的不卖了，走了，那我只能再找别人买货了(从头开始)。
3.  我到交易地点的时候，你不在，那我先尝试把这个交易点给占了(一屁股做凳子上…)，如果我成功抢占了单间(交易点)，那就坐这儿等着你拿货来交易，进入第4步；如果被别人抢座了，那我只能在找别的地方儿了，进入第5步。
4.  你拿着货来了，喊我交易，然后完成交易；也可能我等了好长时间你都没来，我不等了，继续找别人交易去，走的时候我看了一眼，一共没多少人，弄了这么多单间(交易地点Slot)，太TM浪费了，我喊来交易地点管理员：一共也没几个人，搞这么多单间儿干毛，给哥撤一个！。然后再找别人买货(从头开始)；或者我老大给我打了个电话，不让我买货了(中断)。
5.  我跑去喊管理员，尼玛，就一个坑交易个毛啊，然后管理在一个更加开阔的地方开辟了好多个单间，然后我就挨个来看每个单间是否有人。如果有人我就问他是否可以交易，如果回应了我，那我就进入第2步。如果我没有人，那我就占着这个单间等其他人来交易，进入第4步。 6.如果我尝试了几次都没有成功，我就会认为，是不是我TM选的这个单间风水不好？不行，得换个地儿继续(从头开始)；如果我尝试了多次发现还没有成功，怒了，把管理员喊来：给哥再开一个单间(Slot)，加一个凳子，这么多人就这么几个破凳子够谁用！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210813/3b9a87859601446fb0db1b05814a01a0.png