ChiuCheng

ChiuCheng 查看完整档案

上海编辑东南大学  |  信息工程 编辑  |  填写所在公司/组织 segmentfault.com/a/1190000016058789 编辑
编辑

Talk is cheap, show me the code!

个人动态

ChiuCheng 评论了文章 · 2019-05-07

逐行分析AQS源码(3)——共享锁的获取与释放

前言

前面两篇我们以ReentrantLock为例了解了AQS独占锁的获取释放,本篇我们来看看共享锁。由于AQS对于共享锁与独占锁的实现框架比较类似,因此如果你搞定了前面的独占锁模式,则共享锁也就很容易弄懂了。

系列文章目录

共享锁与独占锁的区别

共享锁与独占锁最大的区别在于,独占锁是独占的,排他的,因此在独占锁中有一个exclusiveOwnerThread属性,用来记录当前持有锁的线程。当独占锁已经被某个线程持有时,其他线程只能等待它被释放后,才能去争锁,并且同一时刻只有一个线程能争锁成功。

而对于共享锁而言,由于锁是可以被共享的,因此它可以被多个线程同时持有。换句话说,如果一个线程成功获取了共享锁,那么其他等待在这个共享锁上的线程就也可以尝试去获取锁,并且极有可能获取成功。

共享锁的实现和独占锁是对应的,我们可以从下面这张表中看出:

独占锁共享锁
tryAcquire(int arg)tryAcquireShared(int arg)
tryAcquireNanos(int arg, long nanosTimeout)tryAcquireSharedNanos(int arg, long nanosTimeout)
acquire(int arg)acquireShared(int arg)
acquireQueued(final Node node, int arg)doAcquireShared(int arg)
acquireInterruptibly(int arg)acquireSharedInterruptibly(int arg)
doAcquireInterruptibly(int arg)doAcquireSharedInterruptibly(int arg)
doAcquireNanos(int arg, long nanosTimeout)doAcquireSharedNanos(int arg, long nanosTimeout)
release(int arg)releaseShared(int arg)
tryRelease(int arg)tryReleaseShared(int arg)
-doReleaseShared()

可以看出,除了最后一个属于共享锁的doReleaseShared()方法没有对应外,其他的方法,独占锁和共享锁都是一一对应的。

事实上,其实与doReleaseShared()对应的独占锁的方法应当是unparkSuccessor(h),只是doReleaseShared()逻辑不仅仅包含了unparkSuccessor(h),还包含了其他操作,这一点我们下面分析源码的时候再看。

另外,尤其需要注意的是,在独占锁模式中,我们只有在获取了独占锁的节点释放锁时,才会唤醒后继节点——这是合理的,因为独占锁只能被一个线程持有,如果它还没有被释放,就没有必要去唤醒它的后继节点。

然而,在共享锁模式下,当一个节点获取到了共享锁,我们在获取成功后就可以唤醒后继节点了,而不需要等到该节点释放锁的时候,这是因为共享锁可以被多个线程同时持有,一个锁获取到了,则后继的节点都可以直接来获取。因此,在共享锁模式下,在获取锁和释放锁结束时,都会唤醒后继节点。 这一点也是doReleaseShared()方法与unparkSuccessor(h)方法无法直接对应的根本原因所在。

共享锁的获取

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

我们拿它和独占锁模式对比一下:

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

这两者的结构看上去似乎有点差别,但事实上是一样的,只不过是共享锁模式下,将与addWaiter(Node.EXCLUSIVE)对应的addWaiter(Node.SHARED),以及selfInterrupt()操作全部移到了doAcquireShared方法内部,这一点我们在下面分析doAcquireShared方法时就一目了然了。

不过这里先插一句,相对于独占的锁的tryAcquire(int arg)返回boolean类型的值,共享锁的tryAcquireShared(int acquires)返回的是一个整型值:

  • 如果该值小于0,则代表当前线程获取共享锁失败
  • 如果该值大于0,则代表当前线程获取共享锁成功,并且接下来其他线程尝试获取共享锁的行为很可能成功
  • 如果该值等于0,则代表当前线程获取共享锁成功,但是接下来其他线程尝试获取共享锁的行为会失败

因此,只要该返回值大于等于0,就表示获取共享锁成功。

acquireShared中的tryAcquireShared方法由具体的子类负责实现,这里我们暂且不表。

接下来我们看看doAcquireShared方法,它对应于独占锁的acquireQueued,两者其实很类似,我们把它们相同的部分注释掉,只看不同的部分:

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    /*boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();*/
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            /*if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }*/
}

关于上面的if部分,独占锁对应的acquireQueued方法为:

if (p == head && tryAcquire(arg)) {
    setHead(node);
    p.next = null; // help GC
    failed = false;
    return interrupted;
}

因此,综合来看,这两者的逻辑仅有两处不同:

  1. addWaiter(Node.EXCLUSIVE) -> addWaiter(Node.SHARED)
  2. setHead(node) -> setHeadAndPropagate(node, r)

这里第一点不同就是独占锁的acquireQueued调用的是addWaiter(Node.EXCLUSIVE),而共享锁调用的是addWaiter(Node.SHARED),表明了该节点处于共享模式,这两种模式的定义为:

/** Marker to indicate a node is waiting in shared mode */
static final Node SHARED = new Node();
/** Marker to indicate a node is waiting in exclusive mode */
static final Node EXCLUSIVE = null;

该模式被赋值给了节点的nextWaiter属性:

Node(Thread thread, Node mode) {     // Used by addWaiter
    this.nextWaiter = mode;
    this.thread = thread;
}

我们知道,在条件队列中,nextWaiter是指向条件队列中的下一个节点的,它将条件队列中的节点串起来,构成了单链表。但是在sync queue队列中,我们只用prev,next属性来串联节点,形成双向链表,nextWaiter属性在这里只起到一个标记作用,不会串联节点,这里不要被Node SHARED = new Node()所指向的空节点迷惑,这个空节点并不属于sync queue,不代表任何线程,它只起到标记作用,仅仅用作判断节点是否处于共享模式的依据:

// Node#isShard()
final boolean isShared() {
    return nextWaiter == SHARED;
}

这里的第二点不同就在于获取锁成功后的行为,对于独占锁而言,是直接调用了setHead(node)方法,而共享锁调用的是setHeadAndPropagate(node, r)

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);

    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

在该方法内部我们不仅调用了setHead(node),还在一定条件下调用了doReleaseShared()来唤醒后继的节点。这是因为在共享锁模式下,锁可以被多个线程所共同持有,既然当前线程已经拿到共享锁了,那么就可以直接通知后继节点来拿锁,而不必等待锁被释放的时候再通知。

关于这个doReleaseShared方法,我们到下面分析锁释放的时候再看。

共享锁的释放

我们使用releaseShared(int arg)方法来释放共享锁:

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        doReleaseShared();
        return true;
    }
    return false;
}

该方法对应于独占锁的release(int arg)方法:

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

在独占锁模式下,由于头节点就是持有独占锁的节点,在它释放独占锁后,如果发现自己的waitStatus不为0,则它将负责唤醒它的后继节点。

在共享锁模式下,头节点就是持有共享锁的节点,在它释放共享锁后,它也应该唤醒它的后继节点,但是值得注意的是,我们在之前的setHeadAndPropagate方法中可能已经调用过该方法了,也就是说它可能会被同一个头节点调用两次,也有可能在我们从releaseShared方法中调用它时,当前的头节点已经易主了,下面我们就来详细看看这个方法:

private void doReleaseShared() {
    for (;;) {
        Node h = head;
        if (h != null && h != tail) {
            int ws = h.waitStatus;
            if (ws == Node.SIGNAL) {
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                    continue;            // loop to recheck cases
                unparkSuccessor(h);
            }
            else if (ws == 0 &&
                     !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;                // loop on failed CAS
        }
        if (h == head)                   // loop if head changed
            break;
    }
}

该方法可能是共享锁模式最难理解的方法了,在看该方法时,我们需要明确以下几个问题:

(1) 该方法有几处调用?

该方法有两处调用,一处在acquireShared方法的末尾,当线程成功获取到共享锁后,在一定条件下调用该方法;一处在releaseShared方法中,当线程释放共享锁的时候调用。

(2) 调用该方法的线程是谁?

在独占锁中,只有获取了锁的线程才能调用release释放锁,因此调用unparkSuccessor(h)唤醒后继节点的必然是持有锁的线程,该线程可看做是当前的头节点(虽然在setHead方法中已经将头节点的thread属性设为了null,但是这个头节点曾经代表的就是这个线程)

在共享锁中,持有共享锁的线程可以有多个,这些线程都可以调用releaseShared方法释放锁;而这些线程想要获得共享锁,则它们必然曾经成为过头节点,或者就是现在的头节点。因此,如果是在releaseShared方法中调用的doReleaseShared,可能此时调用方法的线程已经不是头节点所代表的线程了,头节点可能已经被易主好几次了。

(3) 调用该方法的目的是什么?

无论是在acquireShared中调用,还是在releaseShared方法中调用,该方法的目的都是在当前共享锁是可获取的状态时,唤醒head节点的下一个节点。这一点看上去和独占锁似乎一样,但是它们的一个重要的差别是——在共享锁中,当头节点发生变化时,是会回到循环中再立即唤醒head节点的下一个节点的。也就是说,在当前节点完成唤醒后继节点的任务之后将要退出时,如果发现被唤醒后继节点已经成为了新的头节点,则会立即触发唤醒head节点的下一个节点的操作,如此周而复始。

(4) 退出该方法的条件是什么

该方法是一个自旋操作(for(;;)),退出该方法的唯一办法是走最后的break语句:

if (h == head)   // loop if head changed
    break;

即,只有在当前head没有易主时,才会退出,否则继续循环。
这个怎么理解呢?
为了说明问题,这里我们假设目前sync queue队列中依次排列有

dummy node -> A -> B -> C -> D

现在假设A已经拿到了共享锁,则它将成为新的dummy node,

dummy node (A) -> B -> C -> D

此时,A线程会调用doReleaseShared,我们写做doReleaseShared[A],在该方法中将唤醒后继的节点B,它很快获得了共享锁,成为了新的头节点:

dummy node (B) -> C -> D

此时,B线程也会调用doReleaseShared,我们写做doReleaseShared[B],在该方法中将唤醒后继的节点C,但是别忘了,在doReleaseShared[B]调用的时候,doReleaseShared[A]还没运行结束呢,当它运行到if(h == head)时,发现头节点现在已经变了,所以它将继续回到for循环中,与此同时,doReleaseShared[B]也没闲着,它在执行过程中也进入到了for循环中。。。

由此可见,我们这里形成了一个doReleaseShared的“调用风暴”,大量的线程在同时执行doReleaseShared,这极大地加速了唤醒后继节点的速度,提升了效率,同时该方法内部的CAS操作又保证了多个线程同时唤醒一个节点时,只有一个线程能操作成功。

那如果这里doReleaseShared[A]执行结束时,节点B还没有成为新的头节点时,doReleaseShared[A]方法不就退出了吗?是的,但即使这样也没有关系,因为它已经成功唤醒了线程B,即使doReleaseShared[A]退出了,当B线程成为新的头节点时,doReleaseShared[B]就开始执行了,它也会负责唤醒后继节点的,这样即使变成这种每个节点只唤醒自己后继节点的模式,从功能上讲,最终也可以实现唤醒所有等待共享锁的节点的目的,只是效率上没有之前的“调用风暴”快。

由此我们知道,这里的“调用风暴”事实上是一个优化操作,因为在我们执行到该方法的末尾的时候,unparkSuccessor基本上已经被调用过了,而由于现在是共享锁模式,所以被唤醒的后继节点极有可能已经获取到了共享锁,成为了新的head节点,当它成为新的head节点后,它可能还是要在setHeadAndPropagate方法中调用doReleaseShared唤醒它的后继节点。

明确了上面几个问题后,我们再来详细分析这个方法,它最重要的部分就是下面这两个if语句:

if (ws == Node.SIGNAL) {
    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
        continue;            // loop to recheck cases
    unparkSuccessor(h);
}
else if (ws == 0 &&
         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
    continue;                // loop on failed CAS

第一个if很好理解,如果当前ws值为Node.SIGNAL,则说明后继节点需要唤醒,这里采用CAS操作先将Node.SIGNAL状态改为0,这是因为前面讲过,可能有大量的doReleaseShared方法在同时执行,我们只需要其中一个执行unparkSuccessor(h)操作就行了,这里通过CAS操作保证了unparkSuccessor(h)只被执行一次。

比较难理解的是第二个else if,首先我们要弄清楚ws啥时候为0,一种是上面的compareAndSetWaitStatus(h, Node.SIGNAL, 0)会导致ws为0,但是很明显,如果是因为这个原因,则它是不会进入到else if语句块的。所以这里的ws为0是指当前队列的最后一个节点成为了头节点。为什么是最后一个节点呢,因为每次新的节点加进来,在挂起前一定会将自己的前驱节点的waitStatus修改成Node.SIGNAL的。(对这一点不理解的详细看这里)

其次,compareAndSetWaitStatus(h, 0, Node.PROPAGATE)这个操作什么时候会失败?既然这个操作失败,说明就在执行这个操作的瞬间,ws此时已经不为0了,说明有新的节点入队了,ws的值被改为了Node.SIGNAL,此时我们将调用continue,在下次循环中直接将这个刚刚新入队但准备挂起的线程唤醒。

其实,如果我们再结合外部的整体条件,就很容易理解这种情况所针对的场景,不要忘了,进入上面这段还有一个条件是

if (h != null && h != tail)

它处于最外层:

private void doReleaseShared() {
    for (;;) {
        Node h = head;
        if (h != null && h != tail) { // 注意这里说明了队列至少有两个节点
            int ws = h.waitStatus;
            if (ws == Node.SIGNAL) {
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                    continue;            
                unparkSuccessor(h);
            }
            else if (ws == 0 &&
                     !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;               
        }
        if (h == head)
            break;
    }
}

这个条件意味着,队列中至少有两个节点。

结合上面的分析,我们可以看出,这个

else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))

描述了一个极其严苛且短暂的状态:

  1. 首先,大前提是队列里至少有两个节点
  2. 其次,要执行到else if语句,说明我们跳过了前面的if条件,说明头节点是刚刚成为头节点的,它的waitStatus值还为0,尾节点是在这之后刚刚加进来的,它需要执行shouldParkAfterFailedAcquire,将它的前驱节点(即头节点)的waitStatus值修改为Node.SIGNAL但是目前这个修改操作还没有来的及执行。这种情况使我们得以进入else if的前半部分else if (ws == 0 &&
  3. 紧接着,要满足!compareAndSetWaitStatus(h, 0, Node.PROPAGATE)这一条件,说明此时头节点的waitStatus已经不是0了,这说明之前那个没有来得及执行的 shouldParkAfterFailedAcquire将前驱节点的的waitStatus值修改为Node.SIGNAL的操作现在执行完了。

由此可见,else if&& 连接了两个不一致的状态,分别对应了shouldParkAfterFailedAcquirecompareAndSetWaitStatus(pred, ws, Node.SIGNAL)执行成功前和执行成功后,因为doReleaseShared
shouldParkAfterFailedAcquire是可以并发执行的,所以这一条件是有可能满足的,只是满足的条件非常严苛,可能只是一瞬间的事。

这里不得不说,如果以上的分析没有错的话,那作者对于AQS性能的优化已经到了“令人发指”的地步!!!虽说这种短暂的瞬间确实存在,也确实有必要重新回到for循环中再次去唤醒后继节点,但是这种优化也太太太~~~过于精细了吧!

我们来看看如果不加入这个精细的控制条件有什么后果呢?

这里我们复习一下新节点入队的过程,前面说过,在发现新节点的前驱不是head节点的时候,它将调用shouldParkAfterFailedAcquire

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;
}

由于前驱节点的ws值现在还为0,新节点将会把它改为Node.SIGNAL,

但修改后,该方法返回的是false,也就是说线程不会立即挂起,而是回到上层再尝试一次抢锁:

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            // shouldParkAfterFailedAcquire的返回处
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

当我们再次回到for(;;)循环中,由于此时当前节点的前驱节点已经成为了新的head,所以它可以参与抢锁,由于它抢的是共享锁,所以大概率它是抢的到的,所以极有可能它不会被挂起。这有可能导致在上面的doReleaseShared调用unparkSuccessor方法unpark了一个并没有被park的线程。然而,这一操作是被允许的,当我们unpark一个并没有被park的线程时,该线程在下一次调用park方法时就不会被挂起,而这一行为是符合我们的场景的——因为当前的共享锁处于可获取的状态,后继的线程应该直接来获取锁,不应该被挂起。

事实上,我个人认为:

else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
    continue;  // loop on failed CAS

这一段其实也可以省略,当然有了这一段肯定会加速唤醒后继节点的过程,作者针对上面那种极其短暂的情况进行了优化可以说是和它之前“调用风暴”的设计一脉相承,可能也正是由于作者对于性能的极致追求才使得AQS如此之优秀吧。

总结

  • 共享锁的调用框架和独占锁很相似,它们最大的不同在于获取锁的逻辑——共享锁可以被多个线程同时持有,而独占锁同一时刻只能被一个线程持有。
  • 由于共享锁同一时刻可以被多个线程持有,因此当头节点获取到共享锁时,可以立即唤醒后继节点来争锁,而不必等到释放锁的时候。因此,共享锁触发唤醒后继节点的行为可能有两处,一处在当前节点成功获得共享锁后,一处在当前节点释放共享锁后。

(完)

系列文章目录

查看原文

ChiuCheng 评论了文章 · 2019-05-07

深入理解HashMap(四): 关键源码逐行分析之resize扩容

前言

系列文章目录

上一篇我们说明了HashMap的构造函数, 谈到构造函数中并不会初始化table 变量, table 变量是在 resize过程中初始化的.

本篇我们就来聊聊HashMap的扩容: resize

本文的源码基于 jdk8 版本.

resize

resize用于以下两种情况之一

  • 初始化table
  • 在table大小超过threshold之后进行扩容

下面我们直接来对照源码分析:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 原table中已经有值
    if (oldCap > 0) {
    
        // 已经超过最大限制, 不再扩容, 直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 注意, 这里扩容是变成原来的两倍
        // 但是有一个条件: `oldCap >= DEFAULT_INITIAL_CAPACITY`
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    
    // 在构造函数一节中我们知道
    // 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
    // 如果指定了initialCapacity, 该值被初始化成大于initialCapacity的最小的2的次幂
    
    // 这里是指, 如果构造时指定了initialCapacity, 则用threshold作为table的实际大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    
    // 如果构造时没有指定initialCapacity, 则用默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 计算指定了initialCapacity情况下的新的 threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    
    //从以上操作我们知道, 初始化HashMap时, 
    //如果构造函数没有指定initialCapacity, 则table大小为16
    //如果构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
    
    
    // 从下面开始, 初始化table或者扩容, 实际上都是通过新建一个table来完成的
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 下面这段就是把原来table里面的值全部搬到新的table里面
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是清除旧表的引用, 但是真正的node节点还在, 只是现在由e指向它
                oldTab[j] = null;
                
                // 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 如果该存储桶里面存的是红黑树, 则拆分树
                else if (e instanceof TreeNode)
                    //红黑树的部分以后有机会再讲吧
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                
                // 下面这段代码很精妙, 我们单独分一段详细来讲
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize时的链表拆分

下面我们单独来看看这段设计的很精妙的代码

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

首先我们看源码时要抓住一个大框架, 不要被它复杂的流程唬住, 我们一段一段来看:

第一段

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

上面这段定义了四个Node的引用, 从变量命名上,我们初步猜测, 这里定义了两个链表, 我们把它称为 lo链表hi链表, loHeadloTail 分别指向 lo链表的头节点和尾节点, hiHeadhiTail以此类推.

第二段

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

上面这段是一个do-while循环, 我们先从中提取出主要框架:

do {
    next = e.next;
    ...
} while ((e = next) != null);

从上面的框架上来看, 就是在按顺序遍历该存储桶位置上的链表中的节点.

我们再看if-else 语句的内容:

// 插入lo链表
if (loTail == null)
    loHead = e;
else
    loTail.next = e;
loTail = e;

// 插入hi链表
if (hiTail == null)
    hiHead = e;
else
    hiTail.next = e;
hiTail = e;

上面结构类似的两段看上去就是一个将节点e插入链表的动作.

最后再加上 if 块, 则上面这段的目的就很清晰了:

我们首先准备了两个链表 lohi, 然后我们顺序遍历该存储桶上的链表的每个节点, 如果 (e.hash & oldCap) == 0, 我们就将节点放入lo链表, 否则, 放入hi链表.

第三段

第二段弄明白之后, 我们再来看第三段:

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

这一段看上去就很简单了:

如果lo链表非空, 我们就把整个lo链表放到新table的j位置上
如果hi链表非空, 我们就把整个hi链表放到新table的j+oldCap位置上

综上我们知道, 这段代码的意义就是将原来的链表拆分成两个链表, 并将这两个链表分别放到新的table的 j 位置和 j+oldCap 上, j位置就是原链表在原table中的位置, 拆分的标准就是:

(e.hash & oldCap) == 0

为了帮助大家理解,我画了个示意图:
rezise
(ps: 画个图真的好累啊, 大家有什么好的画图工具推荐吗?)

关于 (e.hash & oldCap) == 0j 以及 j+oldCap

上面我们已经弄懂了链表拆分的代码, 但是这个拆分条件看上去很奇怪, 这里我们来稍微解释一下:

首先我们要明确三点:

  1. oldCap一定是2的整数次幂, 这里假设是2^m
  2. newCap是oldCap的两倍, 则会是2^(m+1)
  3. hash对数组大小取模(n - 1) & hash 其实就是取hash的低m

例如:
我们假设 oldCap = 16, 即 2^4,
16 - 1 = 15, 二进制表示为 0000 0000 0000 0000 0000 0000 0000 1111
可见除了低4位, 其他位置都是0(简洁起见,高位的0后面就不写了), 则 (16-1) & hash 自然就是取hash值的低4位,我们假设它为 abcd.

以此类推, 当我们将oldCap扩大两倍后, 新的index的位置就变成了 (32-1) & hash, 其实就是取 hash值的低5位. 那么对于同一个Node, 低5位的值无外乎下面两种情况:

0abcd
1abcd

其中, 0abcd与原来的index值一致, 而1abcd = 0abcd + 10000 = 0abcd + oldCap

故虽然数组大小扩大了一倍,但是同一个key在新旧table中对应的index却存在一定联系: 要么一致,要么相差一个 oldCap

而新旧index是否一致就体现在hash值的第4位(我们把最低为称作第0位), 怎么拿到这一位的值呢, 只要:

hash & 0000 0000 0000 0000 0000 0000 0001 0000

上式就等效于

hash & oldCap

故得出结论:

如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap

根据这个条件, 我们将原位置的链表拆分成两个链表, 然后一次性将整个链表放到新的Table对应的位置上.

怎么样? 这个设计是不是很巧妙, 反正LZ是无比佩服源码作者的!

总结

  1. resize发生在table初始化, 或者table中的节点数超过threshold值的时候, threshold的值一般为负载因子乘以容量大小.
  2. 每次扩容都会新建一个table, 新建的table的大小为原大小的2倍.
  3. 扩容时,会将原table中的节点re-hash到新的table中, 但节点在新旧table中的位置存在一定联系: 要么下标相同, 要么相差一个oldCap(原table的大小).

(完)

下一篇: 深入理解HashMap(五): 关键源码逐行分析之put

查看更多系列文章:系列文章目录

查看原文

ChiuCheng 评论了文章 · 2019-04-28

线程间的同步与通信(3)——浅析synchronized的实现原理

前言

系列文章目录

前面两篇文章我们介绍了synchronized同步代码块以及wait和notify机制,大致知道了这些关键字和方法是干什么的,以及怎么用。

但是,知其然,并不知其所以然。

例如:

  1. 什么是监视器锁?
  2. JAVA中任何对象都可以作为锁,那么锁信息是怎么被记录和存储的?
  3. 监视器锁是怎样被获取的?
  4. 监视器锁是怎样被释放的?
  5. 什么是wait set

本篇我们将来解答这些问题。

spin-lock 和 suspend-lock

总的来说,锁有两种不同的实现方式,一种是自旋,一种是挂起。

(suspend-lock不知道怎么翻译,感觉叫"挂起锁"或"悬挂锁"都太难听了,后面就直接不翻译了)

自旋锁是一种乐观锁,它乐观地认为锁资源没有被占用,或者即使被占用了,也很快就会被释放, 所以当它发现锁已经被占用后,大多会在原地忙等待(一般是在死循环中等待,这也就是自旋的由来), 直到锁被释放,我们在之前分析AQS的文章中提过,AQS处在阻塞队列头部的线程用的就是自旋的方式来等待锁。

suspend-lock是一种悲观锁,它悲观地认为锁竞争总是经常发生的,如果锁被占用了,基本短时间内不会释放,所以他会让出CPU资源,直接挂起,等待条件满足后,别人将自己唤醒。

自旋锁的优点是实现简单,只需要很小的内存,在竞争不多的场景中性能很好。但是如果锁竞争很多,那么大量的时间会浪费在无意义的自旋等待上,造成CPU利用率降低。

suspend-lock的优点是CPU利用率高,因为在发现锁被占用后,它会立即释放自己剩下的CPU时间隙(time-slice)给其他线程,以期望获得更高的CPU利用率。但是因为线程的挂起与唤醒需要通过操作系统调用来完成,这涉及到用户空间和内核空间的转换,线程上下文的切换,所以即使在竞争很少的场景中,这种锁也会显得很慢。但是如果锁竞争很激烈,则这种锁就可以获得很好的性能。

由此可见,自旋锁和suspend-lock各有优劣,他们分别适用于竞争不多和竞争激烈的场景中。

在实际的应用中,我们可以综合这两种方式的优点,例如AQS中,排在阻塞队列第一位的使用自旋等待,而排在后面的线程则挂起。

而我们今天要讲的synchronized,使用的是suspend-lock方式。

synchronized的实现

既然前面提到了synchronized用的是suspend-lock方式,在看synchronized的实现原理之前,我们不妨来思考一下: 如果要我们自己设计,该怎么做?

前几篇我们提到过:

每个java对象都可以用做一个实现同步的锁, 这些锁被称为内置锁(Intrinsic Lock)或者监视器锁(Monitor Lock).

要实现这个目标,则每个java对象都应该与某种类型的锁数据关联。

这就意味着,我们需要一个存储锁数据的地方,并且每一个对象都应该有这么个地方。

在java中,这个地方就是对象头。

其实Java的对象头和对象的关系很像Http请求的http headerhttp body的关系。

对象头中存储了该对象的metadata, 除了该对象的锁信息,还包括指向该对象对应的类的指针,对象的hashcode, GC分代年龄等,在对象头这个寸土寸金的地方,根据锁状态的不同,有些内存是大家公用的,在不同的锁状态下,存储不同的信息,而对象头中存储锁信息的那部分字段,我们称作Mark Word, 这个我们就不展开了讲了。我们只需要知道:

锁信息存储在对象头的Mark Word

在synchronized锁中,这个存储在对象头的Mark Word中的锁信息是一个指针,它指向一个monitor对象(也称为管程或监视器锁)的起始地址。这样,我们就通过对象头,将每一个对象与一个monitor关联了起来,它们的关系如下图所示:

java fat lock
(图片来源: Evaluating and improving biased locking in the HotSpot virtual machine

图片的最左边是线程的调用栈,它引用了堆中的一个对象,该对象的对象头部分记录了该对象所使用的监视器锁,该监视器锁指向了一个monitor对象。

那么这个monitor对象是什么呢? 在Java虚拟机(HotSpot)中,monitor是由ObjectMonitor实现的,其主要数据结构如下: (源码在这里)

 ObjectMonitor() {
    _header       = NULL;
    _count        = 0;
    _waiters      = 0,
    _recursions   = 0;
    _object       = NULL;
    _owner        = NULL;
    _WaitSet      = NULL;
    _WaitSetLock  = 0 ;
    _Responsible  = NULL ;
    _succ         = NULL ;
    _cxq          = NULL ;
    FreeNext      = NULL ;
    _EntryList    = NULL ;
    _SpinFreq     = 0 ;
    _SpinClock    = 0 ;
    OwnerIsThread = 0 ;
    _previous_owner_tid = 0;
 }

上面这些字段中,我们只需要重点关注三个字段:

  • _owner : 当前拥有该 ObjectMonitor 的线程
  • _EntryList: 当前等待锁的集合
  • _WaitSet: 调用了Object.wait()方法而进入等待状态的线程的集合,即我们上一篇一直提到的wait set

在java中,每一个等待锁的线程都会被封装成ObjectWaiter对象,当多个线程同时访问一段同步代码时,首先会被扔进 _EntryList 集合中,如果其中的某个线程获得了monitor对象,他将成为 _owner,如果在它成为 _owner之后又调用了wait方法,则他将释放获得的monitor对象,进入 _WaitSet集合中等待被唤醒。

monitor对象

(图片来源: Inter-thread communication in Java)

另外,因为每一个对象都可以作为synchronized的锁,所以每一个对象都必须支持wait()notifynotifyAll方法,使得线程能够在一个monitor对象上wait, 直到它被notify。这也就解释了这三个方法为什么定义在了Object类中——这样,所有的类都将持有这三个方法。

总结:

  1. 每一个java对象都和一个ObjectMonitor对象相关联,关联关系存储在该java对象的对象头里的Mark Word中。
  2. 每一个试图进入同步代码块的线程都会被封装成ObjectWaiter对象,它们或在ObjectMonitor对象的_EntryList中,或在 _WaitSet 中,等待成为ObjectMonitor对象的owner. 成为owner的对象即获取了监视器锁。

所以,说是每一个java对象都可以作为锁,其实是指将每一个java对象所关联的ObjectMonitor作为锁,更进一步是指,大家都想成为 某一个java对象所关联的ObjectMonitor对象的_owner,所以你可以把这个_owner看做是铁王座,所有等待在这个监视器锁上的线程都想坐上这个铁王座,谁拥有了它,谁就有进入由它锁住的同步代码块的权利。

附加题

其实,了解到上面这个程度已经足够用了,如果你想再深入的了解,例如synchronized在字节码层面的具体语义实现,这里推荐几篇博客:

另外,如果你想深入了解偏向锁,轻量级锁,以及锁膨胀的过程,强烈建议看下面这篇论文:

该篇论文的介绍非常详细,关键是有很多图示,对于Mark Word在不同锁状态的描述很清晰。

(完)

查看更多系列文章:系列文章目录

查看原文

ChiuCheng 评论了文章 · 2019-04-02

逐行分析AQS源码(3)——共享锁的获取与释放

前言

前面两篇我们以ReentrantLock为例了解了AQS独占锁的获取释放,本篇我们来看看共享锁。由于AQS对于共享锁与独占锁的实现框架比较类似,因此如果你搞定了前面的独占锁模式,则共享锁也就很容易弄懂了。

系列文章目录

共享锁与独占锁的区别

共享锁与独占锁最大的区别在于,独占锁是独占的,排他的,因此在独占锁中有一个exclusiveOwnerThread属性,用来记录当前持有锁的线程。当独占锁已经被某个线程持有时,其他线程只能等待它被释放后,才能去争锁,并且同一时刻只有一个线程能争锁成功。

而对于共享锁而言,由于锁是可以被共享的,因此它可以被多个线程同时持有。换句话说,如果一个线程成功获取了共享锁,那么其他等待在这个共享锁上的线程就也可以尝试去获取锁,并且极有可能获取成功。

共享锁的实现和独占锁是对应的,我们可以从下面这张表中看出:

独占锁共享锁
tryAcquire(int arg)tryAcquireShared(int arg)
tryAcquireNanos(int arg, long nanosTimeout)tryAcquireSharedNanos(int arg, long nanosTimeout)
acquire(int arg)acquireShared(int arg)
acquireQueued(final Node node, int arg)doAcquireShared(int arg)
acquireInterruptibly(int arg)acquireSharedInterruptibly(int arg)
doAcquireInterruptibly(int arg)doAcquireSharedInterruptibly(int arg)
doAcquireNanos(int arg, long nanosTimeout)doAcquireSharedNanos(int arg, long nanosTimeout)
release(int arg)releaseShared(int arg)
tryRelease(int arg)tryReleaseShared(int arg)
-doReleaseShared()

可以看出,除了最后一个属于共享锁的doReleaseShared()方法没有对应外,其他的方法,独占锁和共享锁都是一一对应的。

事实上,其实与doReleaseShared()对应的独占锁的方法应当是unparkSuccessor(h),只是doReleaseShared()逻辑不仅仅包含了unparkSuccessor(h),还包含了其他操作,这一点我们下面分析源码的时候再看。

另外,尤其需要注意的是,在独占锁模式中,我们只有在获取了独占锁的节点释放锁时,才会唤醒后继节点——这是合理的,因为独占锁只能被一个线程持有,如果它还没有被释放,就没有必要去唤醒它的后继节点。

然而,在共享锁模式下,当一个节点获取到了共享锁,我们在获取成功后就可以唤醒后继节点了,而不需要等到该节点释放锁的时候,这是因为共享锁可以被多个线程同时持有,一个锁获取到了,则后继的节点都可以直接来获取。因此,在共享锁模式下,在获取锁和释放锁结束时,都会唤醒后继节点。 这一点也是doReleaseShared()方法与unparkSuccessor(h)方法无法直接对应的根本原因所在。

共享锁的获取

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

我们拿它和独占锁模式对比一下:

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

这两者的结构看上去似乎有点差别,但事实上是一样的,只不过是共享锁模式下,将与addWaiter(Node.EXCLUSIVE)对应的addWaiter(Node.SHARED),以及selfInterrupt()操作全部移到了doAcquireShared方法内部,这一点我们在下面分析doAcquireShared方法时就一目了然了。

不过这里先插一句,相对于独占的锁的tryAcquire(int arg)返回boolean类型的值,共享锁的tryAcquireShared(int acquires)返回的是一个整型值:

  • 如果该值小于0,则代表当前线程获取共享锁失败
  • 如果该值大于0,则代表当前线程获取共享锁成功,并且接下来其他线程尝试获取共享锁的行为很可能成功
  • 如果该值等于0,则代表当前线程获取共享锁成功,但是接下来其他线程尝试获取共享锁的行为会失败

因此,只要该返回值大于等于0,就表示获取共享锁成功。

acquireShared中的tryAcquireShared方法由具体的子类负责实现,这里我们暂且不表。

接下来我们看看doAcquireShared方法,它对应于独占锁的acquireQueued,两者其实很类似,我们把它们相同的部分注释掉,只看不同的部分:

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    /*boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();*/
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            /*if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }*/
}

关于上面的if部分,独占锁对应的acquireQueued方法为:

if (p == head && tryAcquire(arg)) {
    setHead(node);
    p.next = null; // help GC
    failed = false;
    return interrupted;
}

因此,综合来看,这两者的逻辑仅有两处不同:

  1. addWaiter(Node.EXCLUSIVE) -> addWaiter(Node.SHARED)
  2. setHead(node) -> setHeadAndPropagate(node, r)

这里第一点不同就是独占锁的acquireQueued调用的是addWaiter(Node.EXCLUSIVE),而共享锁调用的是addWaiter(Node.SHARED),表明了该节点处于共享模式,这两种模式的定义为:

/** Marker to indicate a node is waiting in shared mode */
static final Node SHARED = new Node();
/** Marker to indicate a node is waiting in exclusive mode */
static final Node EXCLUSIVE = null;

该模式被赋值给了节点的nextWaiter属性:

Node(Thread thread, Node mode) {     // Used by addWaiter
    this.nextWaiter = mode;
    this.thread = thread;
}

我们知道,在条件队列中,nextWaiter是指向条件队列中的下一个节点的,它将条件队列中的节点串起来,构成了单链表。但是在sync queue队列中,我们只用prev,next属性来串联节点,形成双向链表,nextWaiter属性在这里只起到一个标记作用,不会串联节点,这里不要被Node SHARED = new Node()所指向的空节点迷惑,这个空节点并不属于sync queue,不代表任何线程,它只起到标记作用,仅仅用作判断节点是否处于共享模式的依据:

// Node#isShard()
final boolean isShared() {
    return nextWaiter == SHARED;
}

这里的第二点不同就在于获取锁成功后的行为,对于独占锁而言,是直接调用了setHead(node)方法,而共享锁调用的是setHeadAndPropagate(node, r)

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);

    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

在该方法内部我们不仅调用了setHead(node),还在一定条件下调用了doReleaseShared()来唤醒后继的节点。这是因为在共享锁模式下,锁可以被多个线程所共同持有,既然当前线程已经拿到共享锁了,那么就可以直接通知后继节点来拿锁,而不必等待锁被释放的时候再通知。

关于这个doReleaseShared方法,我们到下面分析锁释放的时候再看。

共享锁的释放

我们使用releaseShared(int arg)方法来释放共享锁:

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        doReleaseShared();
        return true;
    }
    return false;
}

该方法对应于独占锁的release(int arg)方法:

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

在独占锁模式下,由于头节点就是持有独占锁的节点,在它释放独占锁后,如果发现自己的waitStatus不为0,则它将负责唤醒它的后继节点。

在共享锁模式下,头节点就是持有共享锁的节点,在它释放共享锁后,它也应该唤醒它的后继节点,但是值得注意的是,我们在之前的setHeadAndPropagate方法中可能已经调用过该方法了,也就是说它可能会被同一个头节点调用两次,也有可能在我们从releaseShared方法中调用它时,当前的头节点已经易主了,下面我们就来详细看看这个方法:

private void doReleaseShared() {
    for (;;) {
        Node h = head;
        if (h != null && h != tail) {
            int ws = h.waitStatus;
            if (ws == Node.SIGNAL) {
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                    continue;            // loop to recheck cases
                unparkSuccessor(h);
            }
            else if (ws == 0 &&
                     !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;                // loop on failed CAS
        }
        if (h == head)                   // loop if head changed
            break;
    }
}

该方法可能是共享锁模式最难理解的方法了,在看该方法时,我们需要明确以下几个问题:

(1) 该方法有几处调用?

该方法有两处调用,一处在acquireShared方法的末尾,当线程成功获取到共享锁后,在一定条件下调用该方法;一处在releaseShared方法中,当线程释放共享锁的时候调用。

(2) 调用该方法的线程是谁?

在独占锁中,只有获取了锁的线程才能调用release释放锁,因此调用unparkSuccessor(h)唤醒后继节点的必然是持有锁的线程,该线程可看做是当前的头节点(虽然在setHead方法中已经将头节点的thread属性设为了null,但是这个头节点曾经代表的就是这个线程)

在共享锁中,持有共享锁的线程可以有多个,这些线程都可以调用releaseShared方法释放锁;而这些线程想要获得共享锁,则它们必然曾经成为过头节点,或者就是现在的头节点。因此,如果是在releaseShared方法中调用的doReleaseShared,可能此时调用方法的线程已经不是头节点所代表的线程了,头节点可能已经被易主好几次了。

(3) 调用该方法的目的是什么?

无论是在acquireShared中调用,还是在releaseShared方法中调用,该方法的目的都是在当前共享锁是可获取的状态时,唤醒head节点的下一个节点。这一点看上去和独占锁似乎一样,但是它们的一个重要的差别是——在共享锁中,当头节点发生变化时,是会回到循环中再立即唤醒head节点的下一个节点的。也就是说,在当前节点完成唤醒后继节点的任务之后将要退出时,如果发现被唤醒后继节点已经成为了新的头节点,则会立即触发唤醒head节点的下一个节点的操作,如此周而复始。

(4) 退出该方法的条件是什么

该方法是一个自旋操作(for(;;)),退出该方法的唯一办法是走最后的break语句:

if (h == head)   // loop if head changed
    break;

即,只有在当前head没有易主时,才会退出,否则继续循环。
这个怎么理解呢?
为了说明问题,这里我们假设目前sync queue队列中依次排列有

dummy node -> A -> B -> C -> D

现在假设A已经拿到了共享锁,则它将成为新的dummy node,

dummy node (A) -> B -> C -> D

此时,A线程会调用doReleaseShared,我们写做doReleaseShared[A],在该方法中将唤醒后继的节点B,它很快获得了共享锁,成为了新的头节点:

dummy node (B) -> C -> D

此时,B线程也会调用doReleaseShared,我们写做doReleaseShared[B],在该方法中将唤醒后继的节点C,但是别忘了,在doReleaseShared[B]调用的时候,doReleaseShared[A]还没运行结束呢,当它运行到if(h == head)时,发现头节点现在已经变了,所以它将继续回到for循环中,与此同时,doReleaseShared[B]也没闲着,它在执行过程中也进入到了for循环中。。。

由此可见,我们这里形成了一个doReleaseShared的“调用风暴”,大量的线程在同时执行doReleaseShared,这极大地加速了唤醒后继节点的速度,提升了效率,同时该方法内部的CAS操作又保证了多个线程同时唤醒一个节点时,只有一个线程能操作成功。

那如果这里doReleaseShared[A]执行结束时,节点B还没有成为新的头节点时,doReleaseShared[A]方法不就退出了吗?是的,但即使这样也没有关系,因为它已经成功唤醒了线程B,即使doReleaseShared[A]退出了,当B线程成为新的头节点时,doReleaseShared[B]就开始执行了,它也会负责唤醒后继节点的,这样即使变成这种每个节点只唤醒自己后继节点的模式,从功能上讲,最终也可以实现唤醒所有等待共享锁的节点的目的,只是效率上没有之前的“调用风暴”快。

由此我们知道,这里的“调用风暴”事实上是一个优化操作,因为在我们执行到该方法的末尾的时候,unparkSuccessor基本上已经被调用过了,而由于现在是共享锁模式,所以被唤醒的后继节点极有可能已经获取到了共享锁,成为了新的head节点,当它成为新的head节点后,它可能还是要在setHeadAndPropagate方法中调用doReleaseShared唤醒它的后继节点。

明确了上面几个问题后,我们再来详细分析这个方法,它最重要的部分就是下面这两个if语句:

if (ws == Node.SIGNAL) {
    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
        continue;            // loop to recheck cases
    unparkSuccessor(h);
}
else if (ws == 0 &&
         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
    continue;                // loop on failed CAS

第一个if很好理解,如果当前ws值为Node.SIGNAL,则说明后继节点需要唤醒,这里采用CAS操作先将Node.SIGNAL状态改为0,这是因为前面讲过,可能有大量的doReleaseShared方法在同时执行,我们只需要其中一个执行unparkSuccessor(h)操作就行了,这里通过CAS操作保证了unparkSuccessor(h)只被执行一次。

比较难理解的是第二个else if,首先我们要弄清楚ws啥时候为0,一种是上面的compareAndSetWaitStatus(h, Node.SIGNAL, 0)会导致ws为0,但是很明显,如果是因为这个原因,则它是不会进入到else if语句块的。所以这里的ws为0是指当前队列的最后一个节点成为了头节点。为什么是最后一个节点呢,因为每次新的节点加进来,在挂起前一定会将自己的前驱节点的waitStatus修改成Node.SIGNAL的。(对这一点不理解的详细看这里)

其次,compareAndSetWaitStatus(h, 0, Node.PROPAGATE)这个操作什么时候会失败?既然这个操作失败,说明就在执行这个操作的瞬间,ws此时已经不为0了,说明有新的节点入队了,ws的值被改为了Node.SIGNAL,此时我们将调用continue,在下次循环中直接将这个刚刚新入队但准备挂起的线程唤醒。

其实,如果我们再结合外部的整体条件,就很容易理解这种情况所针对的场景,不要忘了,进入上面这段还有一个条件是

if (h != null && h != tail)

它处于最外层:

private void doReleaseShared() {
    for (;;) {
        Node h = head;
        if (h != null && h != tail) { // 注意这里说明了队列至少有两个节点
            int ws = h.waitStatus;
            if (ws == Node.SIGNAL) {
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                    continue;            
                unparkSuccessor(h);
            }
            else if (ws == 0 &&
                     !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;               
        }
        if (h == head)
            break;
    }
}

这个条件意味着,队列中至少有两个节点。

结合上面的分析,我们可以看出,这个

else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))

描述了一个极其严苛且短暂的状态:

  1. 首先,大前提是队列里至少有两个节点
  2. 其次,要执行到else if语句,说明我们跳过了前面的if条件,说明头节点是刚刚成为头节点的,它的waitStatus值还为0,尾节点是在这之后刚刚加进来的,它需要执行shouldParkAfterFailedAcquire,将它的前驱节点(即头节点)的waitStatus值修改为Node.SIGNAL但是目前这个修改操作还没有来的及执行。这种情况使我们得以进入else if的前半部分else if (ws == 0 &&
  3. 紧接着,要满足!compareAndSetWaitStatus(h, 0, Node.PROPAGATE)这一条件,说明此时头节点的waitStatus已经不是0了,这说明之前那个没有来得及执行的 shouldParkAfterFailedAcquire将前驱节点的的waitStatus值修改为Node.SIGNAL的操作现在执行完了。

由此可见,else if&& 连接了两个不一致的状态,分别对应了shouldParkAfterFailedAcquirecompareAndSetWaitStatus(pred, ws, Node.SIGNAL)执行成功前和执行成功后,因为doReleaseShared
shouldParkAfterFailedAcquire是可以并发执行的,所以这一条件是有可能满足的,只是满足的条件非常严苛,可能只是一瞬间的事。

这里不得不说,如果以上的分析没有错的话,那作者对于AQS性能的优化已经到了“令人发指”的地步!!!虽说这种短暂的瞬间确实存在,也确实有必要重新回到for循环中再次去唤醒后继节点,但是这种优化也太太太~~~过于精细了吧!

我们来看看如果不加入这个精细的控制条件有什么后果呢?

这里我们复习一下新节点入队的过程,前面说过,在发现新节点的前驱不是head节点的时候,它将调用shouldParkAfterFailedAcquire

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;
}

由于前驱节点的ws值现在还为0,新节点将会把它改为Node.SIGNAL,

但修改后,该方法返回的是false,也就是说线程不会立即挂起,而是回到上层再尝试一次抢锁:

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            // shouldParkAfterFailedAcquire的返回处
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

当我们再次回到for(;;)循环中,由于此时当前节点的前驱节点已经成为了新的head,所以它可以参与抢锁,由于它抢的是共享锁,所以大概率它是抢的到的,所以极有可能它不会被挂起。这有可能导致在上面的doReleaseShared调用unparkSuccessor方法unpark了一个并没有被park的线程。然而,这一操作是被允许的,当我们unpark一个并没有被park的线程时,该线程在下一次调用park方法时就不会被挂起,而这一行为是符合我们的场景的——因为当前的共享锁处于可获取的状态,后继的线程应该直接来获取锁,不应该被挂起。

事实上,我个人认为:

else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
    continue;  // loop on failed CAS

这一段其实也可以省略,当然有了这一段肯定会加速唤醒后继节点的过程,作者针对上面那种极其短暂的情况进行了优化可以说是和它之前“调用风暴”的设计一脉相承,可能也正是由于作者对于性能的极致追求才使得AQS如此之优秀吧。

总结

  • 共享锁的调用框架和独占锁很相似,它们最大的不同在于获取锁的逻辑——共享锁可以被多个线程同时持有,而独占锁同一时刻只能被一个线程持有。
  • 由于共享锁同一时刻可以被多个线程持有,因此当头节点获取到共享锁时,可以立即唤醒后继节点来争锁,而不必等到释放锁的时候。因此,共享锁触发唤醒后继节点的行为可能有两处,一处在当前节点成功获得共享锁后,一处在当前节点释放共享锁后。

(完)

系列文章目录

查看原文

ChiuCheng 关注了标签 · 2019-02-21

c#

C#是微软推出的一种基于.NET框架的、面向对象的高级编程语言。C#由C语言和C++派生而来,继承了其强大的性能,同时又以.NET 框架类库作为基础,拥有类似Visual Basic的快速开发能力。

关注 5666

ChiuCheng 评论了文章 · 2019-02-20

Docker volume 挂载时文件或文件夹不存在

背景介绍

docker volume 可以使我们在启动docker容器时,动态的挂载一些文件(如配置文件), 以覆盖镜像中原有的文件,但是,挂载一个主机上尚不存在的文件夹或者文件到容器中会怎样呢?LZ在工作中就遇到了这样的问题,故自己实践了一下,记录实验结果如下:

文件夹挂载

docker在文件夹挂载上的行为是统一的,具体表现为:

  • 若文件夹不存在,则先创建出文件夹(若为多层文件夹,则递归创建)
  • 用host上的文件夹内容覆盖container中的文件夹内容
docker run -v /path-to-folder/A:/path-to-folder/B test-image

详细说明如下:

host上文件夹存在,且非空

hostcontainermount result
存在的非空文件夹A不存在的文件夹B先在contanier中创建文件夹B,再将A文件夹中的所有文件copy到B中
存在的非空文件夹A存在的非空文件夹B先将container中文件夹B的原有内容清空,再将A中文件copy到B中
无论container中的文件夹B是否存在, A都会完全覆盖B的内容

host上文件夹存在,但为空

hostcontainermount result
存在的空文件夹A存在的非空文件夹Bcontainer中文件夹B的内容被清空
container中对应的文件夹内容被清空

host上文件夹不存在

hostcontainermount result
不存在的文件夹A存在的非空文件夹B在host上创建文件夹A,container中文件夹B的内容被清空
不存在的文件夹A/B/C存在的非空文件夹B在host上创建文件夹A/B/C,container中文件夹B的内容被清空
container中对应的文件夹内容被清空

总结

host上文件夹一定会覆盖container中文件夹:

hostcontainermount result
文件夹不存在/文件夹存在但为空文件夹不存在/存在但为空/存在且不为空container中文件被覆盖(清空)
文件夹存在且不为空文件夹不存在/存在但为空/存在且不为空container中文件夹内容被覆盖(原内容清空, 覆盖为host上文件夹内容)

文件挂载

文件挂载与文件夹挂载最大的不同点在于:

  • docker 禁止用主机上不存在的文件挂载到container中已经存在的文件
  • 文件挂载不会对同一文件夹下的其他文件产生任何影响

除此之外, 其覆盖行为与文件夹挂载一致,即:

  • 用host上的文件的内容覆盖container中的文件的内容
docker run -v /path-to-folder/non-existent-config.js:/path-to-folder/config.js test-image # forbidden

详细说明如下:

host上文件不存在

hostcontainermount result
不存在的文件configA.js已经存在的文件congfigB.js报错,Are you trying to mount a directory onto a file (or vice-versa)? Check if the specified host path exists and is the expected type. 同时会在host上生成两个空目录 configA.js 和 configB.js, 但是container无法启动

host上文件存在

hostcontainermount result
存在的文件configA.js存在的文件congfigB.jscontainer中文件名configB.js保持不变,但是文件内容被congfigA.js的内容覆盖了
存在的文件configA.js不存在的文件congfigB.jscontainer中新建一个文件configB.js,其内容为configA.js的文件内容, configB.js所在文件下的所有其他文件维持不变

总结

host上文件一定会覆盖container中文件夹

hostcontainermount result
不存在的文件已经存在的文件禁止行为
存在的文件不存在的文件/已经存在的文件新增/覆盖 (若目录不存在则会创建目录)

结论

文件夹挂载

  • 允许不存在的文件夹或者存在的空文件夹挂载进container, container中对应的文件夹将被清空
  • 非空文件夹挂载进container将会覆盖container中原有文件夹

文件挂载

  • 禁止将不存在的文件挂载进container中已经存在的文件上
  • 存在的文件挂载进container中将会覆盖container中对应的文件, 若文件不存在则新建

应用场景

  1. 从上面的分析可知,文件夹挂载以整个文件夹为单位进行文件覆盖,故可在需要将大量文件挂载进container时使用,另外,如果挂载一个空文件夹或者不存在的文件夹,一般是做逆向使用: 即容器启动后,可能会在容器内挂载点的文件夹下生成一些文件(如日志),此时,在对应的host上的文件夹内就能直接看到。
  2. 文件挂载由于只会覆盖单个文件而不会影响container中同一文件夹下的其他文件,常常被用来挂载配置文件,以在运行时,动态的修改默认配置。

(完)

查看更多文章:系列文章目录

查看原文

ChiuCheng 收藏了文章 · 2019-01-22

宇宙最强vscode教程(基础篇)

本文主要介绍vscode在工作中常用的快捷键及插件,目标在于提高工作效率

本文的快捷键是基于mac的,windows下的快捷键放在括号里 Cmd+Shift+P(win Ctrl+Shift+P)

[TOC]

零、快速入门

有经验的可以跳过快速入门或者大致浏览一遍

1. 命令面板

命令面板是vscode快捷键的主要交互界面,可以使用f1或者Cmd+Shift+P(win Ctrl+Shift+P)打开。

在命令面板中你可以输入命令进行搜索(中英文都可以),然后执行。

命名面板中可以执行各种命令,包括编辑器自带的功能和插件提供的功能。

所以一定要记住它的快捷键Cmd+Shift+P

image-20190120143658078

2. 界面介绍

刚上手使用vscode时,建议要先把它当做一个文件编辑器(可以打字然后保存),等到有了一定经验再去熟悉那些快捷键

先来熟悉一下界面及快捷命令(不用记)

3. 在命令行中使用vscode

如果你是 Windows用户,安装并重启系统后,你就可以在命令行中使用 code 或者 code-insiders了,如果你希望立刻而不是等待重启后使用,可以将 VS Code 的安装目录添加到系统环境变量 PATH

如果你是mac用户,安装后打开命名面板Cmd+Shift+P,搜索shell命令,点击在PAth中安装code命令,然后重启终端就ok了

image-20190120144757840

最基础的使用就是使用code命令打开文件或文件夹

code 文件夹地址,vscode 就会在新窗口中打开该文件夹

如果你希望在已经打开的窗口打开文件,可以使用-r参数

vscode命令还有其他功能,比如文件比较,打开文件跳转到指定的行和列,如有需要自行百度:bowing_woman:

注意:

在继续看文章之前记住记住打开命令面板的快捷键Cmd+shift+P(win下是Ctrl+shift+p)

一、代码编辑

windows下的快捷键放在括号里

光标的移动

基础

  1. 移动到行首 Cmd+左方向键 (win Home)
  2. 移动到行尾 Cmd+右方向键 (win End)
  3. 移动到文档的开头和末尾 Cmd+上下方向键 (win Ctrl+Home/End)
  4. 在花括号{}左边右边之间跳转 Cmd+Shift+ (win Ctrl+Shift+)

进阶

  1. 回到上一个光标的位置,Cmd+U(win Ctrl+U) 非常有用,有时候vue文件,你改了html,需要去下面改js,改完js又需要回去,这时候Cmd+U直接回
  2. 在不同的文件之间回到上一个光标的位置 Control+- (win 没测试,不知道),你改了a文件,改了b文件之后想回到a文件继续编辑,mac使用controls+-

文本选择

  1. 你只需要多按一个shift键就可以在光标移动的时候选中文本
  2. 选中单词 Cmd+D 下面要讲的多光标也会讲到Cmd+D
  3. 对于代码块的选择没有快捷键,可以使用cmd+shift+p打开命令面板,输入选择括号所有内容,待会说下如何添加快捷键

1

删除

  1. 你可以选中了代码之后再删除,再按Backpack(是backpack吗)或者delete删除,但是那样做太low了
  2. 所以,最Geek的删除方式是Cmd+Shift+K (win Ctrl+Shift+K),想删多少删多少,当前你可以使用ctrl+x剪切,效果一样的

2

代码移动

  • Option+上下方向键(win Alt+上下)

3

  • 代码移动的同时按住shift就可以实现代码复制 Option+Shift+上下3

添加注释

注释有两种形式,单行注释和块注释(在js中,单行注释//,块注释/**/)

  • 单行注释 Cmd+/ (win Ctrl +/)
  • 块注释 Option+Shift+A

注意:不同语言使用的注释不同

二、代码格式

代码格式化

  • 对整个文档进行格式化:Option+Shift+F (win Alt+Shift+F),vscode会根据你使用的语言,使用不同的插件进行格式化,记得要下载相应格式化的插件
  • 对选中代码进行格式化: Cmd+K Cmk+F win(Ctrl+K Ctrl+F)

代码缩进

  • 真个文档进行缩进调节,使用Cmd+Shift+P打开命令面板,输入缩进,然后选择相应的命令
  • 选中代码缩进调节:Cmd+] Cmd+[ 分别是减小和增加缩进(win 下不知道,自行百度)

三、一些小技巧

  • 调整字符的大小写,选中,然后在命令面板输入转化为大写或者转化为小写

  • 合并代码行,多行代码合并为一行,Cmd+J(win下未绑定)

  • 行排序,将代码行按照字母顺序进行排序,无快捷键,调出命令面板,输入按升序排序或者按降序排序

四、多光标特性

使用鼠标:

按住Option(win Alt),然后用鼠标点,鼠标点在哪里哪里就会出现一个光标

注意:有的mac电脑上是按住Cmd,然后用鼠标点才可以

快捷命令

  1. Cmd+D (win Ctrl+D) 第一次按下时,它会选中光标附近的单词;第二次按下时,它会找到这个单词第二次出现的位置,创建一个新的光标,并且选中它。(注:cmd-k cmd-d 跳过当前的选择)

  2. Option+Shift+i (win Alt+Shift+i) 首先你要选中多行代码,然后按Option+Shift+i,这样做的结果是:每一行后面都会多出来一个光标

撤销多光标

  • 使用Esc 撤销多光标
  • 鼠标点一下撤销

五、快速跳转(文件、行、符号)

快速打开文件

Cmd+P (win Ctrl+P)输入你要打开的文件名,回车打开

这里有个小技巧,选中你要打开的文件后,按Cmd+Enter,就会在一个新的编辑器窗口打开(窗口管理,见下文)

在tab不同的文件间切换,cmd+shift+[]

行跳转

加入浏览器报了个错,错误在53行,如何快速跳转到53行

Ctrl+g 输入行号

如果你想跳转到某个文件的某一行,你只需要先按下 “Cmd + P”,输入文件名,然后在这之后加上 “:”和指定行号即可。

符号跳转

符号可以是文件名、函数名,可以是css的类名

Cmd+Shift+O(win Ctrl+Shift+o) 输入你要跳转的符号,回车进行跳转

win下输入Ctrl+T,可以在不同文件的符号间进行搜索跳转

定义(definition)和实现(implementation)处

f12跳到函数的定义处

Cmd+f12(win Ctrl+f12)跳转到函数的实现处

引用跳转

很多时候,除了要知道一个函数或者类的定义和实现以外,你可能还希望知道它们被谁引用了,以及在哪里被引用了。这时你只需要将光标移动到函数或者类上面,然后按下 Shift + F12,VS Code 就会打开一个引用列表和一个内嵌的编辑器。在这个引用列表里,你选中某个引用,VS Code 就会把这个引用附近的代码展示在这个内嵌的编辑器里。

六、代码重构

当我们想修改一个函数或者变量的名字时候,我们只需把光标放到函数或者变量名上,然后按下 F2,这样这个函数或者变量出现的地方就都会被修改。

查看原文

ChiuCheng 收藏了文章 · 2019-01-21

JavaScript是如何工作的:引擎,运行时和调用堆栈的概述!

阿里云最近在做活动,低至2折,有兴趣可以看看:
https://promotion.aliyun.com/...

为了保证的可读性,本文采用意译而非直译。

本文是旨在深入研究JavaScript及其实际工作原理的系列文章中的第一篇:我们认为通过了解JavaScript的构建块以及它们是如何工作的,将能够编写更好的代码和应用程序。我们还将分享构建 SeStHealsStad 时使用的一些经验法则,这是一个轻量级的 JavaScript 应用程序,必须保持健壮和高性能以保持竞争力。

想阅读更多优质文章请猛戳GitHub博客,一年百来篇优质文章等着你!

GitHut 统计 数据所示,在GitHub中的活动存储库和总推送方面,JavaScript处于顶部。它也不落后于其他类别。

图片描述

如果项目越来越依赖于 JavaScript,这意味着开发人员必须利用语言和生态系统提供的所有内容,对内部进行更深入的了解,以便构建出色的软件。

事实证明,有很多开发人员每天都在使用JavaScript,但却不知道背后发生了什么。

概述

几乎每个人都已经听说过 V8 引擎,大多数人都知道 JavaScript 是单线程的,或者它使用的是回调队列。

在本文中,我们将详细介绍这些概念,并解释 JavaScrip 实际如何运行。通过了解这些细节,你将能够适当地利用所提供的 API 来编写更好的、非阻塞的应用程序。

如果您对JavaScript还比较陌生,那么本文将帮助您理解为什么JavaScript与其他语言相比如此“怪异”。

如果你是一个有经验的JavaScript开发人员,希望它能让您对每天使用的JavaScript运行时的实际工作方式有一些新的见解。

JavaScript引擎

JavaScript引擎的一个流行示例是Google的V8引擎。例如,在Chrome和Node.js中使用V8引擎,下面是一个非常简化的视图:

图片描述

V8引擎由两个主要部件组成:

  • emory Heap(内存堆) — 内存分配地址的地方
  • Call Stack(调用堆栈) — 代码执行的地方

Runtime(运行时)

有些浏览器的 API 经常被使用到(比如说:setTimeout),但是,这些 API 却不是引擎提供的。那么,他们是从哪儿来的呢?事实上这里面实际情况有点复杂。

图片描述

所以说我们还有很多引擎之外的 API,我们把这些称为浏览器提供 API 称为 Web API,比如说 DOM、AJAX、setTimeout等等。

然后我们还拥有如此流行的事件循环和回调队列。

调用栈

JavaScript是一种单线程编程语言,这意味着它只有一个调用堆栈。因此,它一次只能做一件事。

调用栈是一种数据结构,它记录了我们在程序中的位置。如果我们运行到一个函数,它就会将其放置到栈顶,当从这个函数返回的时候,就会将这个函数从栈顶弹出,这就是调用栈做的事情。

来个栗子:

图片描述

当程序开始执行的时候,调用栈是空的,然后,步骤如下:

图片描述

每一个进入调用栈的都称为调用帧。

这能清楚的知道当异常发生的时候堆栈追踪是怎么被构造的,堆栈的状态是如何的,让我们看一下下面的代码:

图片描述

如果这发生在 Chrome 里(假设这段代码实在一个名为 foo.js 的文件中),那么将会生成以下的堆栈追踪:

图片描述

"堆栈溢出",当你达到调用栈最大的大小的时候就会发生这种情况,而且这相当容易发生,特别是在你写递归的时候却没有全方位的测试它。我们来看看下面的代码:

图片描述

当引擎开始执行这段代码时,它首先调用函数“foo”。然而,这个函数是递归的,并且在没有任何终止条件的情况下开始调用自己。因此,在执行的每一步中,相同的函数都会被一次又一次地添加到调用堆栈中,如下所示:

图片描述

然而,在某些时候,调用堆栈中的函数调用数量超过了调用堆栈的实际大小,浏览器决定采取行动,抛出一个错误,它可能是这样的:

图片描述

在单个线程上运行代码很容易,因为你不必处理在多线程环境中出现的复杂场景——例如死锁。
但是在一个线程上运行也非常有限制,由于 JavaScript 只有一个调用堆栈,当某段代码运行变慢时会发生什么?

并发与事件循环

当调用堆栈中的函数调用需要花费大量时间来处理时会发生什么情况? 例如,假设你希望在浏览器中使用JavaScript进行一些复杂的图像转换。

你可能会问-为什么这是一个问题?问题是,当调用堆栈有函数要执行时,浏览器实际上不能做任何其他事情——它被阻塞了,这意味着浏览器不能呈现,它不能运行任何其他代码,它只是卡住了,如果你想在应用中使用流畅的页面效果,这就会产生问题。

而且这不是唯一的问题,一旦你的浏览器开始处理调用栈中的众多任务,它可能会停止响应相当长一段时间。大多数浏览器都会这么做,报一个错误,询问你是否想终止 web 页面。

图片描述

这并不是最好的用户体验,不是吗?

那么,我们怎样才能在不阻塞UI和不使浏览器失去响应的情况下执行大量代码呢?解决方案是异步回调。

这个在下一篇说明,我尽快把原作者的内容整理好!

代码部署后可能存在的BUG没法实时知道,事后为了解决这些BUG,花了大量的时间进行log 调试,这边顺便给大家推荐一个好用的BUG监控工具 Fundebug

原文:https://blog.sessionstack.com...

你的点赞是我持续分享好东西的动力,欢迎点赞!

交流

干货系列文章汇总如下,觉得不错点个Star,欢迎 加群 互相学习。

https://github.com/qq44924588...

我是小智,公众号「大迁世界」作者,对前端技术保持学习爱好者。我会经常分享自己所学所看的干货,在进阶的路上,共勉!

关注公众号,后台回复福利,即可看到福利,你懂的。

clipboard.png

查看原文

ChiuCheng 赞了文章 · 2019-01-21

JavaScript是如何工作的:引擎,运行时和调用堆栈的概述!

阿里云最近在做活动,低至2折,有兴趣可以看看:
https://promotion.aliyun.com/...

为了保证的可读性,本文采用意译而非直译。

本文是旨在深入研究JavaScript及其实际工作原理的系列文章中的第一篇:我们认为通过了解JavaScript的构建块以及它们是如何工作的,将能够编写更好的代码和应用程序。我们还将分享构建 SeStHealsStad 时使用的一些经验法则,这是一个轻量级的 JavaScript 应用程序,必须保持健壮和高性能以保持竞争力。

想阅读更多优质文章请猛戳GitHub博客,一年百来篇优质文章等着你!

GitHut 统计 数据所示,在GitHub中的活动存储库和总推送方面,JavaScript处于顶部。它也不落后于其他类别。

图片描述

如果项目越来越依赖于 JavaScript,这意味着开发人员必须利用语言和生态系统提供的所有内容,对内部进行更深入的了解,以便构建出色的软件。

事实证明,有很多开发人员每天都在使用JavaScript,但却不知道背后发生了什么。

概述

几乎每个人都已经听说过 V8 引擎,大多数人都知道 JavaScript 是单线程的,或者它使用的是回调队列。

在本文中,我们将详细介绍这些概念,并解释 JavaScrip 实际如何运行。通过了解这些细节,你将能够适当地利用所提供的 API 来编写更好的、非阻塞的应用程序。

如果您对JavaScript还比较陌生,那么本文将帮助您理解为什么JavaScript与其他语言相比如此“怪异”。

如果你是一个有经验的JavaScript开发人员,希望它能让您对每天使用的JavaScript运行时的实际工作方式有一些新的见解。

JavaScript引擎

JavaScript引擎的一个流行示例是Google的V8引擎。例如,在Chrome和Node.js中使用V8引擎,下面是一个非常简化的视图:

图片描述

V8引擎由两个主要部件组成:

  • emory Heap(内存堆) — 内存分配地址的地方
  • Call Stack(调用堆栈) — 代码执行的地方

Runtime(运行时)

有些浏览器的 API 经常被使用到(比如说:setTimeout),但是,这些 API 却不是引擎提供的。那么,他们是从哪儿来的呢?事实上这里面实际情况有点复杂。

图片描述

所以说我们还有很多引擎之外的 API,我们把这些称为浏览器提供 API 称为 Web API,比如说 DOM、AJAX、setTimeout等等。

然后我们还拥有如此流行的事件循环和回调队列。

调用栈

JavaScript是一种单线程编程语言,这意味着它只有一个调用堆栈。因此,它一次只能做一件事。

调用栈是一种数据结构,它记录了我们在程序中的位置。如果我们运行到一个函数,它就会将其放置到栈顶,当从这个函数返回的时候,就会将这个函数从栈顶弹出,这就是调用栈做的事情。

来个栗子:

图片描述

当程序开始执行的时候,调用栈是空的,然后,步骤如下:

图片描述

每一个进入调用栈的都称为调用帧。

这能清楚的知道当异常发生的时候堆栈追踪是怎么被构造的,堆栈的状态是如何的,让我们看一下下面的代码:

图片描述

如果这发生在 Chrome 里(假设这段代码实在一个名为 foo.js 的文件中),那么将会生成以下的堆栈追踪:

图片描述

"堆栈溢出",当你达到调用栈最大的大小的时候就会发生这种情况,而且这相当容易发生,特别是在你写递归的时候却没有全方位的测试它。我们来看看下面的代码:

图片描述

当引擎开始执行这段代码时,它首先调用函数“foo”。然而,这个函数是递归的,并且在没有任何终止条件的情况下开始调用自己。因此,在执行的每一步中,相同的函数都会被一次又一次地添加到调用堆栈中,如下所示:

图片描述

然而,在某些时候,调用堆栈中的函数调用数量超过了调用堆栈的实际大小,浏览器决定采取行动,抛出一个错误,它可能是这样的:

图片描述

在单个线程上运行代码很容易,因为你不必处理在多线程环境中出现的复杂场景——例如死锁。
但是在一个线程上运行也非常有限制,由于 JavaScript 只有一个调用堆栈,当某段代码运行变慢时会发生什么?

并发与事件循环

当调用堆栈中的函数调用需要花费大量时间来处理时会发生什么情况? 例如,假设你希望在浏览器中使用JavaScript进行一些复杂的图像转换。

你可能会问-为什么这是一个问题?问题是,当调用堆栈有函数要执行时,浏览器实际上不能做任何其他事情——它被阻塞了,这意味着浏览器不能呈现,它不能运行任何其他代码,它只是卡住了,如果你想在应用中使用流畅的页面效果,这就会产生问题。

而且这不是唯一的问题,一旦你的浏览器开始处理调用栈中的众多任务,它可能会停止响应相当长一段时间。大多数浏览器都会这么做,报一个错误,询问你是否想终止 web 页面。

图片描述

这并不是最好的用户体验,不是吗?

那么,我们怎样才能在不阻塞UI和不使浏览器失去响应的情况下执行大量代码呢?解决方案是异步回调。

这个在下一篇说明,我尽快把原作者的内容整理好!

代码部署后可能存在的BUG没法实时知道,事后为了解决这些BUG,花了大量的时间进行log 调试,这边顺便给大家推荐一个好用的BUG监控工具 Fundebug

原文:https://blog.sessionstack.com...

你的点赞是我持续分享好东西的动力,欢迎点赞!

交流

干货系列文章汇总如下,觉得不错点个Star,欢迎 加群 互相学习。

https://github.com/qq44924588...

我是小智,公众号「大迁世界」作者,对前端技术保持学习爱好者。我会经常分享自己所学所看的干货,在进阶的路上,共勉!

关注公众号,后台回复福利,即可看到福利,你懂的。

clipboard.png

查看原文

赞 298 收藏 179 评论 3

ChiuCheng 关注了专栏 · 2018-11-28

Java知识点大全

Java3y原创技术文章

关注 2844

认证与成就

  • 获得 511 次点赞
  • 获得 4 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2018-06-01
个人主页被 7.3k 人浏览