Semaphore

Semaphore

A counting semaphore. Conceptually, a semaphore maintains a set of permits. Each {@link #acquire} blocks if necessary until a permit is available, and then takes it. Each {@link #release} adds a permit, potentially releasing a blocking acquirer.
一个计数信号量。顾名思义，一个信号量拥有一定数量的许可证，一个线程acquire需要申请到许可证才能获取锁，否则阻塞等待；释放的时候会返还许可证给阻塞的线程申请。

首先看一下Semaphore的类图结构,内部也是通过AQS的子类Sync实现，分为非公平和公平两种。

Diagram.png

下面是Semaphore的通常用法:

import java.util.concurrent.Semaphore;

/**
 * @author Yale.Wei
 * @date 2018/10/19 下午5:38
 */
public class Semaphore_1 {
    private static Semaphore semaphore = new Semaphore(5); //permit 数量 设置5

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            final int j = i;
            new Thread(() -> {
                try {
                    action(j);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }).start();

        }
    }

    public static void action(int i) throws InterruptedException {
        semaphore.acquire();

        System.out.println(i + "kill the iphone x in JD");
//        Thread.sleep(3000);
//        System.out.println(i + "kill successful");
//
//        semaphore.release();
    }
}

然后结果显示只有5个线程能申请到许可证

1kill the iphone x in JD
3kill the iphone x in JD
2kill the iphone x in JD
0kill the iphone x in JD
4kill the iphone x in JD

Semaphore的methods结构图:

api.png

• constructor 构造方法

    public Semaphore(int permits) { //默认创建permits数量的非公平策略Semaphore
        sync = new NonfairSync(permits);
    }
    
    public Semaphore(int permits, boolean fair) {
        sync = fair ? new FairSync(permits) : new NonfairSync(permits);
    }

• Semaphore# acquire() : void

Acquires a permit, if one is available and returns immediately, reducing the number of available permits by one.If no permit is available then the current thread becomes disabled for thread scheduling purposes and lies dormant until one of two things happens:
1. Some other thread invokes the {@link #release} method for this semaphore and the current thread is next to be assigned a permit;
2. or Some other thread {@linkplain Thread#interrupt interrupts} the current thread.
当前线程申请获取一个许可证(permit)，如果成功则Semaphore的permit数量减一并立即返回。如果当前没有可获取的permit，则线程进入阻塞等待状态，直到其他线程归还permit被当前线程获取或者当前线程被打断。

If the current thread:
has its interrupted status set on entry to this method;
or is {@linkplain Thread#interrupt interrupted} while waiting for a permit,
then {@link InterruptedException} is thrown and the current thread's interrupted status is cleared。
如果当前线程在等待permit时被其他线程interrupt 则抛出InterruptedException病情清除interrupted标记。

acquire()其实内部调用的AbstractQueuedSynchronizer#acquireSharedInterruptibly(1)，acquireSharedInterruptibly(1)首先检查interrupted状态，如果线程处于打断状态则抛出InterruptedException:

    public void acquire() throws InterruptedException {
        sync.acquireSharedInterruptibly(1); //-->>AbstractQueuedSynchronizer#acquireSharedInterruptibly
    }
    //java.util.concurrent.locks.AbstractQueuedSynchronizer#acquireSharedInterruptibly
    public final void acquireSharedInterruptibly(int arg) throws InterruptedException { 
        if (Thread.interrupted()) //检查线程是否被打断，打断则抛出InterruptedException
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0) //这里再次尝试获取锁,返回值小于0说明获取失败
            doAcquireSharedInterruptibly(arg);//再次获取失败进入doAcquireSharedInterruptibly
    }

我们先看非公平策略下的tryAcquireShared:

     protected int tryAcquireShared(int acquires) {
            return nonfairTryAcquireShared(acquires);
     }

    //java.util.concurrent.Semaphore.Sync#nonfairTryAcquireShared
    final int nonfairTryAcquireShared(int acquires) {
            for (;;) {
                int available = getState(); //获取AbstractQueuedSynchronizer#state
                int remaining = available - acquires;//state -1
                if (remaining < 0 || //若小于0则直接返回值不修改state
                    compareAndSetState(available, remaining))//大于等于0座CAS修改 然后返回remaining
                    return remaining;
            }
    }

若获取失败后进入doAcquireSharedInterruptibly:

//java.util.concurrent.locks.AbstractQueuedSynchronizer#doAcquireSharedInterruptibly
   private void doAcquireSharedInterruptibly(int arg)
        throws InterruptedException {
        final Node node = addWaiter(Node.SHARED);//组装成共享节点
        boolean failed = true;
        try {
            for (;;) {
                final Node p = node.predecessor(); //获取前驱节点
                if (p == head) { //若前驱节点是头节点尝试tryAcquire
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);//成功了设置节点为头节并将线程从节点取出点并向后传播
                        p.next = null; // help GC 前驱节点后驱指针指向null 即新插入的出列
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

shouldParkAfterFailedAcquire,parkAndCheckInterrupt,cancelAcquire之前在ReentrantLock说过。这里关注看一下setHeadAndPropagate:

    //java.util.concurrent.locks.AbstractQueuedSynchronizer#setHeadAndPropagate
    private void setHeadAndPropagate(Node node, int propagate) {
        Node h = head; // Record old head for check below
        setHead(node);//设置节点，并解除持有线程
        /*
         * Try to signal next queued node if:
         *   Propagation was indicated by caller,
         *     or was recorded (as h.waitStatus either before
         *     or after setHead) by a previous operation
         *     (note: this uses sign-check of waitStatus because
         *      PROPAGATE status may transition to SIGNAL.)
         * and
         *   The next node is waiting in shared mode,
         *     or we don't know, because it appears null
         *
         * The conservatism in both of these checks may cause
         * unnecessary wake-ups, but only when there are multiple
         * racing acquires/releases, so most need signals now or soon
         * anyway.
         */
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
            (h = head) == null || h.waitStatus < 0) {//如果头节点为空或者waitStatus<0即未被取消
            Node s = node.next;//获取后继节点
            if (s == null || s.isShared())//如果后继节点是共享节点，则自旋唤醒后继节点
                doReleaseShared();//这里都后面释放操作看
        }
    }

这里就提现了共享模式和独占模式的区别，共享模式成功唤醒线程，节点出队后会继续唤醒后继节点。

• Semaphore# release() : void
  Semaphore#release()调用了Sync#releaseShared

    public void release() {
        sync.releaseShared(1);//-->>AbstractQueuedSynchronizer#releaseShared
    }
    
    //java.util.concurrent.locks.AbstractQueuedSynchronizer#releaseShared
    public final boolean releaseShared(int arg) { //-->>java.util.concurrent.Semaphore.Sync#tryReleaseShared
        if (tryReleaseShared(arg)) {//首先尝试释放锁
            doReleaseShared();//-->>java.util.concurrent.locks.AbstractQueuedSynchronizer#doReleaseShared
            return true;
        }
        return false;
    }
    //java.util.concurrent.Semaphore.Sync#tryReleaseShared
    protected final boolean tryReleaseShared(int releases) { //默认是写死传1
            for (;;) { 
                int current = getState();
                int next = current + releases;
                if (next < current) // overflow
                    throw new Error("Maximum permit count exceeded");
                if (compareAndSetState(current, next)) //修改当前state+1
                    return true;
            }
     }

     private void doReleaseShared() {
        /*
         * Ensure that a release propagates, even if there are other
         * in-progress acquires/releases.  This proceeds in the usual
         * way of trying to unparkSuccessor of head if it needs
         * signal. But if it does not, status is set to PROPAGATE to
         * ensure that upon release, propagation continues.
         * Additionally, we must loop in case a new node is added
         * while we are doing this. Also, unlike other uses of
         * unparkSuccessor, we need to know if CAS to reset status
         * fails, if so rechecking.
         */
        for (;;) {
            Node h = head;
            if (h != null && h != tail) {//头节点不为空不等于尾节点说明队列不为空
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {//如果状态为SIGNAL则设置为0唤醒后继节点
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h);
                }
                else if (ws == 0 &&
                         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE)) //如果为0设置PROPAGATE失败则跳过当前循环
                    continue;                // loop on failed CAS
            }
            if (h == head)                   // loop if head changed
                break;
        }
    }

总结一下默认的非公平Sync策略下的Semaphore#acquire()的整体流程:

Semaphore#acquire().png

1. 首先当前线程调用java.util.concurrent.Semaphore#acquire()开始申请许可获取同步器锁。
2. 进入AQS同步器AbstractQueuedSynchronizer#acquireSharedInterruptibly，此时先检查interrupted打断标识，如果打断则直接抛出异常结束方法。
3. 未被打断则进入NonfairSync#tryAcquireShared尝试获取共享模式的锁，此时判断state-1是否<0,即是否有可获取的permit，若<0则不做操作直接返回负值；若>=0说明有可申请permit，然后通过CAS操作将state设置state-1,然后返回修改后的非负值，此时表明当前线程获取锁成功，方法结束返回。
4. tryAcquireShared(arg) < 0即上面申请permit失败，进入AQS#doAcquireSharedInterruptibly。先将当前线程组装成共享节点插入FIFO队尾。然后获取插入节点前驱节点，若前驱节点为头节点则再次尝试获取共享模式锁，如成功将当前节点设置为头节点，并检查后继节点，若后继节点是共享节点执行共享模式的释放操作(这里下面讲)，方法结束；若前驱节点不是头节点额检查节点状态设置为SIGNAL(AbstractQueuedSynchronizer#shouldParkAfterFailedAcquire),然后通过parkAndCheckInterrupt()挂起线程并检查打断状态，等待线程被重新唤醒，获取到锁后若需要则抛出InterruptedException。
5. 若等待期间异常则调用AbstractQueuedSynchronizer#cancelAcquire取消节点。

非公平策略下Semaphore#release()的整体流程:

Semaphore#release().png

1. 当前线程调用Semaphore#release()，进入AbstractQueuedSynchronizer#releaseShared同步器共享模式释放锁方法。
2. 首先尝试释放当前线程的持有锁，释放成功后state+1即归还持有的permit，然后继续进入AQS#doReleaseShared
3. 当前线程释放锁成功后会去尝试唤醒后继节点，无论后继节点唤醒成功或失败，释放操作都已成功，方法结束。