高并发之Semaphore、Exchanger、LockSupport

本系列研究总结高并发下的几种同步锁的使用以及之间的区别,分别是:ReentrantLock、CountDownLatch、CyclicBarrier、Phaser、ReadWriteLock、StampedLock、Semaphore、Exchanger、LockSupport。由于博客园对博客字数的要求限制,会分为三个篇幅:

Semaphore

信号量(Semaphore)，有时被称为信号灯，是在多线程环境下使用的一种设施, 它负责协调各个线程, 以保证它们能够正确、合理的使用公共资源。Semaphore分为单值和多值两种，前者只能被一个线程获得，后者可以被若干个线程获得。

情境引入

以一个停车场是运作为例。为了简单起见，假设停车场只有三个车位，一开始三个车位都是空的。这是如果同时来了五辆车，看门人允许其中三辆不受阻碍的进入，然后放下车拦，剩下的车则必须在入口等待，此后来的车也都不得不在入口处等待。这时，有一辆车离开停车场，看门人得知后，打开车拦，放入一辆，如果又离开两辆，则又可以放入两辆，如此往复。

在这个停车场系统中，车位是公共资源，每辆车好比一个线程，看门人起的就是信号量的作用。更进一步，信号量的特性如下：信号量是一个非负整数（车位数），所有通过它的线程（车辆）都会将该整数减一（通过它当然是为了使用资源），当该整数值为零时，所有试图通过它的线程都将处于等待状态。在信号量上我们定义两种操作： Wait（等待）和 Release（释放）。当一个线程调用Wait等待）操作时，它要么通过然后将信号量减一，要么一自等下去，直到信号量大于一或超时。Release（释放）实际上是在信号量上执行加操作，对应于车辆离开停车场，该操作之所以叫做“释放”是应为加操作实际上是释放了由信号量守护的资源。

使用代码示例

public class TestSemaphore {

    public static void main(String[] args) {

        //Semaphore s = new Semaphore(2);

        Semaphore s = new Semaphore(2, true);

        //允许一个线程同时执行

        //Semaphore s = new Semaphore(1);

        new Thread(()->{

            try {

                s.acquire();

                System.out.println("T1 running...");

                Thread.sleep(200);

                System.out.println("T1 running...");

            } catch (InterruptedException e) {

                e.printStackTrace();

            } finally {

                s.release();

            }

        }).start();

        new Thread(()->{

            try {

                s.acquire();

                System.out.println("T2 running...");

                Thread.sleep(200);

                System.out.println("T2 running...");

                s.release();

            } catch (InterruptedException e) {

                e.printStackTrace();

            }

        }).start();

    }

}

Exchanger

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

Exchanger是在两个任务之间交换对象的栅栏，当这些任务进入栅栏时，它们各自拥有一个对象。当他们离开时，它们都拥有之前由对象持有的对象。它典型的应用场景是：一个任务在创建对象，这些对象的生产代价很高昂，而另一个任务在消费这些对象。通过这种方式，可以有更多的对象在被创建的同时被消费。

应用示例

Exchange实现较为复杂，我们先看其怎么使用，然后再来分析其源码。现在我们用Exchange来模拟生产-消费者问题：

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();

    }

}

打印结果

生产者第1次提供

生产者装入1--1

生产者装入1--2

生产者装入1--3

生产者装满，等待与消费者交换...

生产者第2次提供

生产者装入2--1

生产者装入2--2

生产者装入2--3

生产者装满，等待与消费者交换...

消费者第1次提取

消费者 : buffer：1--1

消费者 : buffer：1--2

消费者 : buffer：1--3

消费者第2次提取

......

首先生产者Producer、消费者Consumer首先都创建一个缓冲列表，通过Exchanger来同步交换数据。消费中通过调用Exchanger与生产者进行同步来获取数据，而生产者则通过for循环向缓存队列存储数据并使用exchanger对象消费者同步。到消费者从exchanger哪里得到数据后，他的缓冲列表中有3个数据，而生产者得到的则是一个空的列表。上面的例子充分展示了消费者-生产者是如何利用Exchanger来完成数据交换的。

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

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

实现分析

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

    }

index：arena的下标；
bound：上一次记录的Exchanger.bound；
collides：在当前bound下CAS失败的次数；
hash：伪随机数，用于自旋；
item：这个线程的当前项，也就是需要交换的数据；
match：做releasing操作的线程传递的项；
parked：挂起时设置线程值，其他情况下为null；

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

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交换。

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

match不为空时跳出循环。

整个slotExchange清晰明了。

arenaExchange

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.arrayBaseOffset获取对象头长度，数组元素的大小可以通过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不会再同一个缓存行中。

LockSupport

LockSupport是一个线程阻塞工具类，所有的方法都是静态方法，可以让线程在任意位置阻塞，当然阻塞之后肯定得有唤醒的方法。

常用方法

接下面我来看看LockSupport有哪些常用的方法。主要有两类方法：park和unpark。

public static void park(Object blocker); // 暂停当前线程

public static void parkNanos(Object blocker, long nanos); // 暂停当前线程，不过有超时时间的限制

public static void parkUntil(Object blocker, long deadline); // 暂停当前线程，直到某个时间

public static void park(); // 无期限暂停当前线程

public static void parkNanos(long nanos); // 暂停当前线程，不过有超时时间的限制

public static void parkUntil(long deadline); // 暂停当前线程，直到某个时间

public static void unpark(Thread thread); // 恢复当前线程

public static Object getBlocker(Thread t);

park英文意思为停车。我们如果把Thread看成一辆车的话，park就是让车停下，unpark就是让车启动然后跑起来。

写一个例子来看看这个工具类怎么用

public class LockSupportDemo {

    public static Object u = new Object();

    static ChangeObjectThread t1 = new ChangeObjectThread("t1");

    static ChangeObjectThread t2 = new ChangeObjectThread("t2");

    public static class ChangeObjectThread extends Thread {

        public ChangeObjectThread(String name) {

            super(name);

        }

        @Override public void run() {

            synchronized (u) {

                System.out.println("in " + getName());

                LockSupport.park();

                if (Thread.currentThread().isInterrupted()) {

                    System.out.println("被中断了");

                }

                System.out.println("继续执行");

            }

        }

    }

    public static void main(String[] args) throws InterruptedException {

        t1.start();

        Thread.sleep(1000L);

        t2.start();

        Thread.sleep(3000L);

        t1.interrupt();

        LockSupport.unpark(t2);

        t1.join();

        t2.join();

    }

}

运行的结果如下：

in t1

被中断了

继续执行

in t2

继续执行

这儿park和unpark其实实现了wait和notify的功能，不过还是有一些差别的。

park不需要获取某个对象的锁
因为中断的时候park不会抛出InterruptedException异常，所以需要在park之后自行判断中断状态，然后做额外的处理

我们再来看看Object blocker，这是个什么东西呢？这其实就是方便在线程dump的时候看到具体的阻塞对象的信息。

"t1" #10 prio=5 os_prio=31 tid=0x00007f95030cc800 nid=0x4e03 waiting on condition [0x00007000011c9000]

   java.lang.Thread.State: WAITING (parking)

    at sun.misc.Unsafe.park(Native Method)

    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:304)

    // `下面的这个信息`

    at com.wtuoblist.beyond.concurrent.demo.chapter3.LockSupportDemo$ChangeObjectThread.run(LockSupportDemo.java:23) //

    - locked <0x0000000795830950> (a java.lang.Object)

相对于线程的stop和resume，park和unpark的先后顺序并不是那么严格。stop和resume如果顺序反了，会出现死锁现象。而park和unpark却不会。这又是为什么呢？还是看一个例子

public class LockSupportDemo {

    public static Object u = new Object();

    static ChangeObjectThread t1 = new ChangeObjectThread("t1");

    public static class ChangeObjectThread extends Thread {

        public ChangeObjectThread(String name) {

            super(name);

        }

        @Override public void run() {

            synchronized (u) {

                System.out.println("in " + getName());

                try {

                    Thread.sleep(1000L);

                } catch (InterruptedException e) {

                    e.printStackTrace();

                }

                LockSupport.park();

                if (Thread.currentThread().isInterrupted()) {

                    System.out.println("被中断了");

                }

                System.out.println("继续执行");

            }

        }

    }

    public static void main(String[] args) {

        t1.start();

        LockSupport.unpark(t1);

        System.out.println("unpark invoked");

    }

}

t1内部有休眠1s的操作，所以unpark肯定先于park的调用，但是t1最终仍然可以完结。这是因为park和unpark会对每个线程维持一个许可（boolean值）

unpark调用时，如果当前线程还未进入park，则许可为true
park调用时，判断许可是否为true，如果是true，则继续往下执行；如果是false，则等待，直到许可为true

巴特西