AQS阻塞队列

绝地灬酷狼 2022-05-29 00:29 192阅读 0赞

## AQS阻塞队列管理 ##

*  资料  
    [http://blog.csdn.net/wangyangzhizhou/article/details/42048453][http_blog.csdn.net_wangyangzhizhou_article_details_42048453]  
    [http://moon-walker.iteye.com/blog/2406446][http_moon-walker.iteye.com_blog_2406446]
 *  自旋锁&CLH锁  
    ![这里写图片描述][SouthEast]

Craig, Landin, and Hagersten的CLH锁  
![这里写图片描述][SouthEast 1]

*  而在AQS中有一个内部类ConditionObject实现了Condition接口。所谓条件队列，其实是一个单向链表；在讲解AQS的实现原理时只讲解了AQS队列，AQS队列前面讲过是双向链表结构。也就是说在AQS整体实现中维护了两个链表：一个是“同步队列”双向链表(这里简称AQS队列)，另一个是“条件队列”单向链表。
 *  Node数据结构

static final class Node {
    
        volatile int waitStatus;//节点状态
    
        volatile Node prev;//前指针 指向前一个节点
    
        volatile Node next;//后指针指向后一个节点
    
        volatile Thread thread;//线程实例
    
        Node nextWaiter;//下一个等待节点
    
        //共享类型
        static final Node SHARED = new Node();
        //独占类型
        static final Node EXCLUSIVE = null;
    
        /**状态列表，对应waitStatus字段值*/
        //线程取消类型
        static final int CANCELLED =  1;
        //线程唤醒状态类型 对应condition的 signal、signalAll方法
        static final int SIGNAL    = -1;
        //线程阻塞状态类型，对应condition的await方法
        static final int CONDITION = -2;
        //对应共享类型释放资源时，传播唤醒线程状态
        static final int PROPAGATE = -3;
    
    
        //省略其他
    }

*  AQS成员变量

//队列的头节点 
        private transient volatile Node head;  
    
        //队列的尾节点 
        private transient volatile Node tail;  
    
        //资源 状态
        //表示一种共享的“资源”的状态，比如：在ReentrantLock锁的实现中，它表示锁是否被占用（为0是表示可用）；在信号量Semaphore的实现中，表示剩余的“许可数量”，大于0表示可用；CountDownLatch中表示需全部完成的工作数量。
        private volatile int state;

*  AQS数据双向链表

![这里写图片描述][SouthEast 2]

*  AQS的核心功能就是：  
    在多线程竞争有限的“资源”的情况下，只允许部分线程（或单个线程）访问这种“资源”，并阻塞其他“线程”。AQS的所有方法几乎都是在根据“资源”的状态，操作和维护一个“**双向链表**”。
 *  由于资源是有限的，所以AQS的核心方法分为两大类：获取“资源”方法和释放“资源”方法，同时这两类方法又都有公平和非公平实现。

## ReentrantLock ##

*  资料  
    [http://blog.csdn.net/prestigeding/article/details/53084883][http_blog.csdn.net_prestigeding_article_details_53084883]
 *  独占锁获取方法

公平Lock，如何保证公平？

final void lock() {
                acquire(1);
            }

public final void acquire(int arg) {
            /* 1. 尝试获取“资源”，如果获取到 该线程继续执行 2. 否则加入队列，并阻塞该线程 */
            if (!tryAcquire(arg) &&
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
                selfInterrupt();
        }

![acquire方法流程][acquire]

/** * Fair version of tryAcquire. Don't grant access unless * recursive call or no waiters or is first. */
            protected final boolean tryAcquire(int acquires) {
                final Thread current = Thread.currentThread();
                int c = getState();
                if (c == 0) {
                    // 表示自愿没有被其它线程占用
    
                    /* 如何保证公平？ 返回true:说明当前线程前面有一个排队的线程， 返回false:说明当前线程是队列中的头结点或者队列为空 也就是说只有在AQS队列未空的时候，才会去抢占资源 */
                    if (!hasQueuedPredecessors() &&
                        // CAS设置state
                        compareAndSetState(0, acquires)) {
                        // 设置AQS持有锁的独占线程为当前线程
                        setExclusiveOwnerThread(current);
                        return true;
                    }
                }
                else if (current == getExclusiveOwnerThread()) {
                    int nextc = c + acquires;
                    if (nextc < 0)
                        throw new Error("Maximum lock count exceeded");
                    setState(nextc);
                    return true;
                }
                return false;
            }

不公平Lock

/** * Performs non-fair tryLock. tryAcquire is * implemented in subclasses, but both need nonfair * try for trylock method. */
            final boolean nonfairTryAcquire(int acquires) {
                final Thread current = Thread.currentThread();
                int c = getState();
                if (c == 0) {
                    // 直接CAS抢用资源
                    if (compareAndSetState(0, acquires)) {
    
                        setExclusiveOwnerThread(current);
                        return true;
                    }
                }
                else if (current == getExclusiveOwnerThread()) {
                    int nextc = c + acquires;
                    if (nextc < 0) // overflow
                        throw new Error("Maximum lock count exceeded");
                    setState(nextc);
                    return true;
                }
                return false;
            }

*  独占锁的释放方法

public final boolean release(int arg) {
            if (tryRelease(arg)) {
                Node h = head;
                // 唤醒下一个需要锁的AQS节点
                if (h != null && h.waitStatus != 0)
                    unparkSuccessor(h);
                return true;
            }
            return false;
        }

protected final boolean tryRelease(int releases) {
                int c = getState() - releases;
                if (Thread.currentThread() != getExclusiveOwnerThread())
                    throw new IllegalMonitorStateException();
                boolean free = false;
                if (c == 0) {
                    free = true;
                    // 设置AQS持有锁的独占线程为null
                    setExclusiveOwnerThread(null);
                }
                setState(c);
                return free;
            }

/** * Wakes up node's successor, if one exists. * * @param node the node */
        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)
                // 清空头结点的waitStatus=0，也就是不再需要锁了
                // 谁来去清理这些Node呢？在AQS acquireQueued方法shouldParkAfterFailedAcquire清理
                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;
                // 从后往前遍历，找最后1个<=0的Node
                for (Node t = tail; t != null && t != node; t = t.prev)
                    if (t.waitStatus <= 0)
                        s = t;
            }
            if (s != null)
                LockSupport.unpark(s.thread);
        }

## Samphore&Condition ##

1.  作用：Semaphore可以控制某个资源可被同时访问的个数，通过\*\* acquire() **获取一个许可，如果没有就等待，而 \*\*release()**释放一个许可。
2.  场景举例：Semaphore实现的功能就类似厕所有5个坑，假如有10个人要上厕所，那么同时只能有多少个人去上厕所呢？同时只能有5个人能够占用，当5个人中 的任何一个人让开后，其中等待的另外5个人中又有一个人可以占用了。另外等待的5个人中可以是随机获得优先机会，也可以是按照先来后到的顺序获得机会，这取决于构造Semaphore对象时传入的参数选项。
3.  Condition实现  
    [conditon实现][conditon]

![ConditionObject数据结构][ConditionObject]

实质是在两个队列之间切换：  
ReentrantLock为例先简单讲解下这两个队列的关系：通过ReentrantLock的lock方法，如果获取不到锁当前线程会进入AQS队列阻塞；被唤醒后继续获取锁，如果获取到锁，移出AQS队列，继续执行；遇到Condition的await方法，加入“条件队列”，阻塞线程；被其他现象的signal方法唤醒，从“**条件队列**”中删除，并加入到**AQS队列**，如果获取到锁就继续执行。可以看到上述操作，线程节点（Node）其实在两个队列之间切换，由于“条件队列”在被唤醒时都是从头开始遍历，所以只需要使用单向链表实现即可。

## ThreadPoolExecutor submit&execute ##

## RateLimiter ##

## Redis ##

# 解决方法 #

[http_blog.csdn.net_wangyangzhizhou_article_details_42048453]: http://blog.csdn.net/wangyangzhizhou/article/details/42048453
[http_moon-walker.iteye.com_blog_2406446]: http://moon-walker.iteye.com/blog/2406446
[SouthEast]: /images/20220529/a21896855e28464aa6e5e53e8eb618ec.png
[SouthEast 1]: /images/20220529/d8364b157348496bb19b9cf1f824e146.png
[SouthEast 2]: /images/20220529/9de9ddb522da42c68a017e74517ac2fe.png
[http_blog.csdn.net_prestigeding_article_details_53084883]: http://blog.csdn.net/prestigeding/article/details/53084883
[acquire]: /images/20220529/50858b9253364fc381afe4b613c6a6b7.png
[conditon]: http://blog.csdn.net/jeffleo/article/details/77099953
[ConditionObject]: /images/20220529/c1e53df8293f4fe8acc2e9d0ae8a2599.png