java juc,juc并发编程AQS详解

KLQ 2020-08-04 10:37:47 java常见问答 4708

你对于juc并发编程了解多少呢?下面的文章要给大家详细介绍的就是和juc并发编程有关的内容,一起来了解一下吧。

在java.util.concurrent.locks包当中有着很多Lock的实现类,经常使用的就有ReentrantLock、ReadWriteLock(实现类ReentrantReadWriteLock),内部实现都依赖AbstractQueuedSynchronizer类。

下面的话,就一起去了解一下大神是如何使用一个普通类就完成了代码块的并发访问控制的吧!为了方便的话,此文就用AQS代替AbstractQueuedSynchronizer。

定义:

public abstract class AbstractQueuedSynchronizer extends
AbstractOwnableSynchronizer implements java.io.Serializable
{
    //等待队列的头节点
    private transient volatile Node head;
    //等待队列的尾节点
    private transient volatile Node tail;
    //同步状态
    private volatile int state;
    protected final int getState()
    {
        return state;
    }
    protected final void setState(int newState)
        {
            state = newState;
        }
        ...
}

队列同步器AQS是用来构建锁或者是其他同步组件的基础框架,内部使用一个int成员变量表示同步状态,通过内置的FIFO队列来完成资源获取线程的排队工作。

在这当中内部状态state,等待队列的头节点head和尾节点head,都是通过volatile修饰,保证了多线程之间的可见。

再一起来了解一下内部的FIFO队列是怎样实现的:

static final class Node
{
    static final Node SHARED = new Node();
    static final Node EXCLUSIVE = null;
    static final int CANCELLED = 1;
    static final int SIGNAL = -1;
    static final int CONDITION = -2;
    static final int PROPAGATE = -3;
    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter;
    ...
}

黄色节点是默认head节点,其实是一个空节点,这里的话可以理解成代表当前持有锁的线程,每次有线程竞争失败,都是插入到队列的尾节点,tail节点始终指向队列中的最后一个元素。

每个节点当中,除去存储了当前线程,前后节点的引用之外,还有一个waitStatus变量,用于描述节点当前的状态,在多线程并发执行的时候,队列当中会有着多个节点的存在,这个waitStatus其实代表对应线程的状态,有的线程可能获取锁因为某些原因放弃竞争,有的线程在等待满足条件,满足之后才能执行等等。

一共的话有四种状态,一个是CANCELLED(取消状态),一个是SIGNAL(等待触发状态),一个是CONDITION(等待条件状态),一个是PROPAGATE(状态需要向后传播)。

注意,等待队列是FIFO先进先出,只有前一个节点的状态为SIGNAL时,当前节点的线程才可以被挂起。

实现原理

子类重写tryAcquire和tryRelease方法通过CAS指令修改状态变量state。

public final void acquire(int arg)
{
    if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

线程获取锁过程(下列步骤中线程A和B进行竞争):

(1)线程A执行CAS执行成功,state值被修改并返回true,线程A继续执行。

(2)线程A执行CAS指令失败,说明线程B也在执行CAS指令且成功,这样的情况下线程A会执行步骤3。

(3)生成新Node节点node,并且,通过CAS指令插入到等待队列的队尾(同一时刻可能会有多个Node节点插入到等待队列中),假如,tail节点为空,那么,就会将head节点指向一个空节点(代表线程B)。

下面是具体的实现代码:

private Node addWaiter(Node mode)
{
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    if (pred != null)
    {
        node.prev = pred;
        if (compareAndSetTail(pred, node))
        {
            pred.next = node;
            return node;
        }
    }
    enq(node);
    return node;
}
private Node enq(final Node node)
{
    for (;;)
    {
        Node t = tail;
        if (t == null)
        { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        }
        else
        {
            node.prev = t;
            if (compareAndSetTail(t, node))
            {
                t.next = node;
                return t;
            }
        }
    }
}

(4)node插入到队尾后,这个线程不会立马挂起,会进行自旋操作。

这主要是因为在node的插入过程,线程B(也就是之前没有阻塞的线程)可能已经执行完成,所以要判断这个node的前一个节点pred是否为head节点(代表线程B),假如,pred == head,表示当前节点是队列中第一个“有效的”节点,所以,再次尝试tryAcquire获取锁。

假如,成功获取到锁,表明线程B已经执行完成,线程A不需要挂起;假如,获取失败,表示线程B还没有完成,至少还未修改state值,进行步骤5。

final boolean acquireQueued(final Node node, int arg)
{
    boolean failed = true;
    try
    {
        boolean interrupted = false;
        for (;;)
        {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg))
            {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    }
    finally
    {
        if (failed)
            cancelAcquire(node);
    }
}

(5)前面已经讲过了,只有前一个节点pred的线程状态为SIGNAL的时候,当前节点的线程才可以被挂起。

假如,pred的waitStatus == 0,那么,通过CAS指令修改waitStatus为Node.SIGNAL。

假如,pred的waitStatus > 0,表明pred的线程状态CANCELLED,需从队列中删除。

假如,pred的waitStatus为Node.SIGNAL,那么,通过LockSupport.park()方法把线程A挂起,并等待被唤醒,被唤醒后进入步骤6。

下面是具体的实现:

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node)
{
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        /*
         * This node has already set status asking a release
         * to signal it, so it can safely park.
         */
        return true;
    if (ws > 0)
    {
        /*
         * Predecessor was cancelled. Skip over predecessors and
         * indicate retry.
         */
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    }
    else
    {
        /*
         * waitStatus must be 0 or PROPAGATE.  Indicate that we
         * need a signal, but don't park yet.  Caller will need to
         * retry to make sure it cannot acquire before parking.
         */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

(6)线程每次被唤醒的时候,都要进行中断检测,假如,发现当前线程被中断,那么抛出InterruptedException并退出循环。

从无限循环的代码能够看出,并不是被唤醒的线程一定能获得锁,一定要调用tryAccquire重新竞争,因为锁是非公平的,有可能被新加入的线程获得,从而导致刚被唤醒的线程再次被阻塞,这个细节充分体现了“非公平”的精髓。

线程释放锁过程:

假如,头结点head的waitStatus值为-1,那么,用CAS指令重置为0;找到waitStatus值小于0的节点s,通过LockSupport.unpark(s.thread)唤醒线程。

private void unparkSuccessor(Node node)
{
    /*
     * If status is negative (i.e., possibly needing signal) try
     * to clear in anticipation of signalling.  It is OK if this
     * fails or if status is changed by waiting thread.
     */
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
    /*
     * Thread to unpark is held in successor, which is normally
     * just the next node.  But if cancelled or apparently null,
     * traverse backwards from tail to find the actual
     * non-cancelled successor.
     */
    Node s = node.next;
    if (s == null || s.waitStatus > 0)
    {
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    if (s != null)
        LockSupport.unpark(s.thread);
}

ConcurrentHashMap核心扩容源码

private final void transfer(Node < K, V > [] tab, Node < K, V > [] nextTab)
{
    int n = tab.length, stride;
    // 将 length / 8 然后除以 CPU核心数。如果得到的结果小于 16,那么就使用 16。
    // 这里的目的是让每个 CPU 处理的桶一样多,避免出现转移任务不均匀的现象,如果桶较少的话,默认一个 CPU(一个线程)处理 16 个桶
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range 细分范围 stridea:TODO
    // 新的 table 尚未初始化
    if (nextTab == null)
    { // initiating
        try
        {
            // 扩容  2 倍
            Node < K, V > [] nt = (Node < K, V > []) new Node < ? , ? > [n << 1];
            // 更新
            nextTab = nt;
        }
        catch (Throwable ex)
        { // try to cope with OOME
            // 扩容失败, sizeCtl 使用 int 最大值。
            sizeCtl = Integer.MAX_VALUE;
            return; // 结束
        }
        // 更新成员变量
        nextTable = nextTab;
        // 更新转移下标,就是 老的 tab 的 length
        transferIndex = n;
    }
    // 新 tab 的 length
    int nextn = nextTab.length;
    // 创建一个 fwd 节点,用于占位。当别的线程发现这个槽位中是 fwd 类型的节点,则跳过这个节点。
    ForwardingNode < K, V > fwd = new ForwardingNode < K, V > (nextTab);
    // 首次推进为 true,如果等于 true,说明需要再次推进一个下标(i--),反之,如果是 false,那么就不能推进下标,需要将当前的下标处理完毕才能继续推进
    boolean advance = true;
    // 完成状态,如果是 true,就结束此方法。
    boolean finishing = false; // to ensure sweep before committing nextTab
    // 死循环,i 表示下标,bound 表示当前线程可以处理的当前桶区间最小下标
    for (int i = 0, bound = 0;;)
    {
        Node < K, V > f;
        int fh;
        // 如果当前线程可以向后推进;这个循环就是控制 i 递减。同时,每个线程都会进入这里取得自己需要转移的桶的区间
        while (advance)
        {
            int nextIndex, nextBound;
            // 对 i 减一,判断是否大于等于 bound (正常情况下,如果大于 bound 不成立,说明该线程上次领取的任务已经完成了。那么,需要在下面继续领取任务)
            // 如果对 i 减一大于等于 bound(还需要继续做任务),或者完成了,修改推进状态为 false,不能推进了。任务成功后修改推进状态为 true。
            // 通常,第一次进入循环,i-- 这个判断会无法通过,从而走下面的 nextIndex 赋值操作(获取最新的转移下标)。其余情况都是:如果可以推进,将 i 减一,然后修改成不可推进。如果 i 对应的桶处理成功了,改成可以推进。
            if (--i >= bound || finishing)
                advance = false; // 这里设置 false,是为了防止在没有成功处理一个桶的情况下却进行了推进
            // 这里的目的是:1. 当一个线程进入时,会选取最新的转移下标。2. 当一个线程处理完自己的区间时,如果还有剩余区间的没有别的线程处理。再次获取区间。
            else if ((nextIndex = transferIndex) <= 0)
            {
                // 如果小于等于0,说明没有区间了 ,i 改成 -1,推进状态变成 false,不再推进,表示,扩容结束了,当前线程可以退出了
                // 这个 -1 会在下面的 if 块里判断,从而进入完成状态判断
                i = -1;
                advance = false; // 这里设置 false,是为了防止在没有成功处理一个桶的情况下却进行了推进
            } // CAS 修改 transferIndex,即 length - 区间值,留下剩余的区间值供后面的线程使用
            else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex
                    , nextBound = (nextIndex > stride ?
                        nextIndex - stride : 0)))
            {
                bound = nextBound; // 这个值就是当前线程可以处理的最小当前区间最小下标
                i = nextIndex - 1; // 初次对i 赋值,这个就是当前线程可以处理的当前区间的最大下标
                advance = false; // 这里设置 false,是为了防止在没有成功处理一个桶的情况下却进行了推进,这样对导致漏掉某个桶。下面的 if (tabAt(tab, i) == f) 判断会出现这样的情况。
            }
        } // 如果 i 小于0 (不在 tab 下标内,按照上面的判断,领取最后一段区间的线程扩容结束)
        //  如果 i >= tab.length(不知道为什么这么判断)
        //  如果 i + tab.length >= nextTable.length  (不知道为什么这么判断)
        if (i < 0 || i >= n || i + n >= nextn)
        {
            int sc;
            if (finishing)
            { // 如果完成了扩容
                nextTable = null; // 删除成员变量
                table = nextTab; // 更新 table
                sizeCtl = (n << 1) - (n >>> 1); // 更新阈值
                return; // 结束方法。
            } // 如果没完成
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1))
            { // 尝试将 sc -1. 表示这个线程结束帮助扩容了,将 sc 的低 16 位减一。
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) // 如果 sc - 2 不等于标识符左移 16 位。如果他们相等了,说明没有线程在帮助他们扩容了。也就是说,扩容结束了。
                    return; // 不相等,说明没结束,当前线程结束方法。
                finishing = advance = true; // 如果相等,扩容结束了,更新 finising 变量
                i = n; // 再次循环检查一下整张表
            }
        }
        else if ((f = tabAt(tab, i)) == null) // 获取老 tab i 下标位置的变量,如果是 null,就使用 fwd 占位。
            advance = casTabAt(tab, i, null, fwd); // 如果成功写入 fwd 占位,再次推进一个下标
        else if ((fh = f.hash) == MOVED) // 如果不是 null 且 hash 值是 MOVED。
            advance = true; // already processed // 说明别的线程已经处理过了,再次推进一个下标
        else
        { // 到这里,说明这个位置有实际值了,且不是占位符。对这个节点上锁。为什么上锁,防止 putVal 的时候向链表插入数据
            synchronized(f)
            {
                // 判断 i 下标处的桶节点是否和 f 相同
                if (tabAt(tab, i) == f)
                {
                    Node < K, V > ln, hn; // low, height 高位桶,低位桶
                    // 如果 f 的 hash 值大于 0 。TreeBin 的 hash 是 -2
                    if (fh >= 0)
                    {
                        // 对老长度进行与运算(第一个操作数的的第n位于第二个操作数的第n位如果都是1,那么结果的第n为也为1,否则为0)
                        // 由于 Map 的长度都是 2 的次方(000001000 这类的数字),那么取于 length 只有 2 种结果,一种是 0,一种是1
                        //  如果是结果是0 ,Doug Lea 将其放在低位,反之放在高位,目的是将链表重新 hash,放到对应的位置上,让新的取于算法能够击中他。
                        int runBit = fh & n;
                        Node < K, V > lastRun = f; // 尾节点,且和头节点的 hash 值取于不相等
                        // 遍历这个桶
                        for (Node < K, V > p = f.next; p != null; p = p.next)
                        {
                            // 取于桶中每个节点的 hash 值
                            int b = p.hash & n;
                            // 如果节点的 hash 值和首节点的 hash 值取于结果不同
                            if (b != runBit)
                            {
                                runBit = b; // 更新 runBit,用于下面判断 lastRun 该赋值给 ln 还是 hn。
                                lastRun = p; // 这个 lastRun 保证后面的节点与自己的取于值相同,避免后面没有必要的循环
                            }
                        }
                        if (runBit == 0)
                        { // 如果最后更新的 runBit 是 0 ,设置低位节点
                            ln = lastRun;
                            hn = null;
                        }
                        else
                        {
                            hn = lastRun; // 如果最后更新的 runBit 是 1, 设置高位节点
                            ln = null;
                        } // 再次循环,生成两个链表,lastRun 作为停止条件,这样就是避免无谓的循环(lastRun 后面都是相同的取于结果)
                        for (Node < K, V > p = f; p != lastRun; p = p.next)
                        {
                            int ph = p.hash;
                            K pk = p.key;
                            V pv = p.val;
                            // 如果与运算结果是 0,那么就还在低位
                            if ((ph & n) == 0) // 如果是0 ,那么创建低位节点
                                ln = new Node < K, V > (ph, pk, pv, ln);
                            else // 1 则创建高位
                                hn = new Node < K, V > (ph, pk, pv, hn);
                        }
                        // 其实这里类似 hashMap 
                        // 设置低位链表放在新链表的 i
                        setTabAt(nextTab, i, ln);
                        // 设置高位链表,在原有长度上加 n
                        setTabAt(nextTab, i + n, hn);
                        // 将旧的链表设置成占位符
                        setTabAt(tab, i, fwd);
                        // 继续向后推进
                        advance = true;
                    } // 如果是红黑树
                    else if (f instanceof TreeBin)
                    {
                        TreeBin < K, V > t = (TreeBin < K, V > ) f;
                        TreeNode < K, V > lo = null, loTail = null;
                        TreeNode < K, V > hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        // 遍历
                        for (Node < K, V > e = t.first; e != null; e = e.next)
                        {
                            int h = e.hash;
                            TreeNode < K, V > p = new TreeNode < K, V >
                                (h, e.key, e.val, null, null);
                            // 和链表相同的判断,与运算 == 0 的放在低位
                            if ((h & n) == 0)
                            {
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    loTail.next = p;
                                loTail = p;
                                ++lc;
                            } // 不是 0 的放在高位
                            else
                            {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        // 如果树的节点数小于等于 6,那么转成链表,反之,创建一个新的树
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin < K, V > (lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin < K, V > (hi) : t;
                        // 低位树
                        setTabAt(nextTab, i, ln);
                        // 高位数
                        setTabAt(nextTab, i + n, hn);
                        // 旧的设置成占位符
                        setTabAt(tab, i, fwd);
                        // 继续向后推进
                        advance = true;
                    }
                }
            }
        }
    }
}

juc并发编程AQS的内容就给你介绍到这里啦,更多java编程常见问题,可以继续关注奇Q工具网来进行了解哦,希望上面的文章可以对你有所帮助呢。

推荐阅读:

javajuc消息队列,java并发包消息队列详解

高并发java实现方式有哪些?该怎么实现?

高并发解决方案,应该如何处理高并发问题?