惊群效应
原文地址 blog.csdn.net
什么是惊群效应
这个话题来自一个面试，当问到 Socket 编程中的 accept() 是否有惊群问题，引深又问到 epoll 多路复用中 epoll_wait() 是否有惊群问题。因为没有准备背过八股文，突然问到这个问题，还是稍微有点措手不及，当然就没有背过的那么快速干脆了，而对方在强调结果，也没给我思考分析的时间，我还在仔细回想这个里哪里存在惊群问题的时候，对方已经打断我说好了。所以这里就记录分析一下，到底什么是惊群效应，以及在并发编程中的应对方式。
简单粗暴理解，惊群效应就是，给一堆睡觉的鸟群 (羊群、牛群都行，随你高兴) 中，扔一颗石子，结果就是会惊醒这一群的鸟，这就是所谓的惊群效应。
对应到并发编程中，当多个线程阻塞到相同资源上 (比如锁) 时，当这个资源 ready 后，资源就绪的信号唤醒了所有阻塞到这个资源上的所有线程。
以锁为例，说明一下惊群的问题。比如某一个时刻 lock1 被其他线程占用，这个时候线程 A、线程 B、线程 C 来获取锁 lock1，则就都会被阻塞在 lock1 的阻塞队列中。当 lock1 被释放的时候，那么就会唤醒所有的阻塞在 lock1 上的线程 (这个不一定是唤醒所有线程，不同实现方式是有不一样的，java 的锁实现是唤醒所有线程的)。当线程 A、线程 B、线程 C 都被唤醒后，他们干的第一件事就是去争抢 lock1，最终只会有一个线程成功获取锁 (加入是线程 A)，那么其他线程就又会重新被阻塞住，所以线程 B、线程 C 被唤醒啥也没干成，又被阻塞了。
要知道，线程的唤醒、挂起，都是需要通过系统调用的，操作系统也需要有一系列的动作老完成线程状态的转换，比如将线程从 lock1 阻塞队列中出队，然后放到 cpu 的就绪队列中，然后将线程状态变成 running，然后操作系统的 cpu 调度就才能给就绪队列中的线程分配 cpu。挂起线程，同样是需要逆向的这一些列动作的。然而对于线程 B、线程 C 唤醒 / 挂起，这些操作都是无用的，是对资源的浪费。当并发非常大，线程争抢一个锁的竞争非常大，那么就会有非常多的这种无用的唤醒 / 挂起，cpu 飙高了，但是业务响应反而变慢了。那么这个时候观察系统，会发现上下文切换变多了、中断也变多了。
总结起来就是：在并发编程中，当有多个线程 / 进程争抢同一资源，因资源不足而被阻塞的时，当阻塞事件解除后，如果唤醒了所有阻塞在该事件上的所有线程 / 进程，那就触发了惊群效应。
惊群效应的应对
在并发编程中，之所以出现了并发安全问题，是因为多个线程同时去修改相同的资源，所以随之而来的应对线程安全问题就是破坏这个条件，所以到处都会告诉你，应对并发安全问题：
- 不可变。这里破坏的就是 "修改" 这个条件。都不可变了，肯定是就没有问题了。但是这个应用场景其实是非常有限的，毕竟一个应用中，真的完全不变的数据并不是很多。但是在 java 变成中，要实现不可变，就得小心了，不是加个 final 修饰符就是不可变了，最稳妥的方式就是封装起来不听过任何修改方法，初始化后就不能该。
- 线程同步。这个破坏的就是 "多个" 条件。通过线程同步的方式，保证同一时刻只有一个线程去修改资源，其实就变成串行的了，自然也就不会有并发安全问题了。这也是最直观、最简单、实际生产中用的最多的方式了。所以几乎是只要提到线程安全，第一反应就是加锁，以至于如果谁深入思考后使用不可变 / 不共享来解决并发安全问题，要么就是被认为是不靠谱、要么就被认为是高阶操作。不过确实：加锁相对来说是更不容易出错一些，而不共享往往容易跌坑里。
- 不共享。这个破坏的就是 "相同资源" 的条件。只要不修改相同的资源，那么肯定就没有并发安全的问题了。但是只要说到不共享，第一反应肯定就是 ThreadLocal，但是好像也只能想到 ThreadLocal。而这里主要就想想要把不共享的思路打开。也从这个角度看下怎么去解决惊群效应。
对于不共享，ThreadLocal 其实就是给每个线程一个副本，自己玩自己的，那就不会共享了。把视角拉高一点，如果多个线程同时去修改相同的资源这句话中的资源，是可切分的、或者部分可切分呢？那是不是说当一个线程来修改的时候，就给这个线程分配一部分、让这个线程独占，依次类推 (当然，这里只是说的思路，实际实现的时候可能还是得配合锁)
JDK 中的例子就是 LongAddr，它的基本思想就是将一个数分成了量大部分：base 和多个 cell。当调用 add() 方法修改这个数的时候，先 CAS 尝试修改 base，如果不成功 (说明有竞争)，那就找个 cell 给当前线程，让它修改这个 cell，这个时候线程是独占 cell 的，也就不存在竞争了；而当我们读取这个数的时候，就需要将 base 以及所有的 cell 进行合并，这里明眼一看就知道有数据一致性问题，所以 LongAdder 也是不使用一致性要求非常高的场景。
具体可参考：CAS vs 数据库乐观锁_georgesnoopy 的博客 - CSDN 博客。jdk 中另外的一个例子就是 ConcurrentHashMap，已经抛弃了 jdk7 中分段锁的实现，而是采用了 LongAdder 的这个思路来进一步优化了
基于这个思路，我们来看下惊群效应，之所以一颗石子会惊醒所有的鸟，不就是因为所有的鸟都睡在一起么，所以解决惊群的问题思路就两个：别让鸟都睡在一起；另一个就是叫醒的时候别都叫醒。
第一个思路：别让鸟都睡在一起，对应到锁的实现上，其实就是条件变量。一个锁可以关联多个条件变量，每个条件变量上一个阻塞队列，争抢同一个锁的线程不是都最在一个队列中，而是多个队列中，当一个条件发生时，只是唤醒对应的条件变量队列中的线程。
举个栗子：生产者 - 消费者模型中，会使用锁来防护那个装馒头的篮子，生产者和消费者都会去争抢这个篮子上的锁，但是抢到锁后，如果生产者发现篮子是满的，则继续挂起自己；消费者发现篮子是空的，则继续挂起自己。但是篮子从空变成不空了，会唤醒所有生产者、消费者线程，但这里起目的其实是想唤醒消费者消费的。有了条件变量就可以精准控制了：一个控制篮子为空、一个控制篮子满了，生产者发现篮子满了阻塞在队满条件变量上、消费者发现篮子为空阻塞在篮子空了的条件变量上。当篮子由空变成不空，只是唤醒篮子空了条件变量阻塞队列上的线程；当篮子由满变成不满，只是唤醒篮子满了条件变量阻塞队列上的线程，这样就会大大减少惊群效应。
所以我们可以看到，条件变量其实可以大大减少惊群效应，但是并不能消除。对于睡在同一卧的鸟还是会被同时唤醒。
另外一个思路就是：你特么的别扔石头一下子都叫醒，一个一个去喊不行么？
当然可以，但是到底喊谁呢？java 的实现就是随机，所以会看到条件变量唤醒线程都是有两个方法：notifyAll()-- 相当于扔石头，砸醒所有的鸟；还有一个 notify()-- 相当于随机去叫醒一只鸟。
这么看好像 notify() 更好呀，没有惊群效应了，只是搞醒了一只鸟，很棒。但是你会发现很多地方都不建议去使用 notify()，而是建议使用 notifyAll()。其原因就是防止线程饿死，一个线程可能一直都没有被随机到，那它就一直不会被唤醒。
站在系统调度的角度看，如果说被阻塞的这些线程，优先级不是一样的，有更高的优先级，那这种随机的方式，并不一定就会唤醒高优先级的那个线程，但是唤醒所有，操作系统调度就会考虑线程优先级的。
另外一个问题，为啥没有一个 notify(Thread t)，让程序员来指定唤醒那个线程呢？扪心自问，你知道改怎么选么，到底该选哪个？如果再深入说下去，那是不是就得自己来实现一个调度框架了，调度框架来决定该唤醒哪个。
Socket 中的惊群
总结一下，出现惊群效应的场景：多个线程阻塞在相同资源上，当资源 ready 后，唤醒阻塞在该资源上的所有线程，而唤醒的所有线程中，其实只有一个能够成功获得这个资源。
基于此，我们来看 Socket 编程中哪些地方可能出现惊群，首先就是看哪些操作是阻塞的：
- 初始化 socket。初始化了 socket 的内存结构。不阻塞
- socket.bind。将 socket 和 ip + 端口绑定，只是修改内存数据，不阻塞。
- socket.liseten。将主动 socket 变成被动 socket，表示这个 socket 是用来监听客户端连接请求的，并开始监听客户端的链接请求。因为这个只是让服务端 Socket 处于侦听状态，listen() 系统调用本身是不阻塞的。
- socket.accept。去 listener 完全链接队列中获取连接，当完全链接队列中为空的时候阻塞当前线程。当完成三次握手链接建立后，操作系统内核会将连接放入到完全连接队列中，然后开始唤醒阻塞在完全连接队列上的线程。
- socket.connect。主动 socket 发起链接请求，背后就是三次握手。是阻塞的。
- socket.read/write。read 是从读缓冲区读取数据、write 是向写缓冲区写入数据。当读缓冲区空，则 read 阻塞；当写缓冲区满，write 阻塞。ps：当然也有不阻塞的重载。
所以总结起来看，整个 socket 编程中，会阻塞线程的就只有：
- 服务端 socket(被动 socket) 的 accept()。当多个线程都对同一个被动 Socket 调用了 accept() 后，如果完全链接队列是空的，那么这些线程都会阻塞到完全链接队列中；当有客户端与服务端完成三次握手，完成了连接建立，则内核会将这个连接放到完全队列中，并唤醒阻塞在这个完全连接队列中的线程。
- 客户端 socket(主动 socket) 的 connect()。这个确实会阻塞，但是不支持多线程调用，因为当三次握手完成，连接建立，这个连接就是对应到当前的这个 sokcet 中的。所以对一个已经完成三次握手连接的 socket 再次调用 connect()，会直接报错。因为不会出现多个线程阻塞在同一个队列中，那也就不会出现惊群问题了。
- 服务端 / 客户端 socket 完成通信的 read()/write()。对于 read()，实际是去读缓冲区获取数据，当读缓冲区是空的，当前线程就会阻塞在读缓冲区上。那么当多个线程使用相同的 socket 调用 read()，当读缓冲区是空的，则所有线程都会阻塞在这个 socket 的读缓冲区上。当对端发送来数据，网卡收到数据后，会将数据放到读缓冲区中。这个时候操作系统就会唤醒所有阻塞在读缓冲区上的所有进程。出现惊群效应。写也是一样的道理。
所以综上所述，在 Socket 编程中，有三个地方是阻塞的，但只有两个地方会出现多个线程阻塞在相同资源上的问题，所以也就只有两处可能存在惊群问题：serverSocket.accept() 和 socket.read()/socket.write()
linux 新版内核中，在阻塞队列中引入了 WQ_FLAG_EXCLUSIVE 标识，可以用它来解决惊群问题，基本思路是在进入到阻塞队列的时候给线程加上一个 WQ_FLAG_EXCLUSIVE 标识，当阻塞事件解除后，唤醒阻塞队列中的线程时，会依次遍历阻塞队列：遍历时如果阻塞队列中的线程没有 WQ_FLAG_EXCLUSIVE 标识，那就直接唤醒；当遇到第一个带有 WQ_FLAG_EXCLUSIVE 的线程时，同样去唤醒该线程，然后结束遍历。这样就保证了一次就绪事件发生，就只会唤醒一个 WQ_FLAG_EXCLUSIVE 标识的线程。
accept() 的惊群就是这么解决的，因为调用 accept() 而被阻塞的线程，进入阻塞队列的时候，就会被打上 WQ_FLAG_EXCLUSIVE 标识，这样当客户端连接请求到来的时候，就只会有一个因 accept 而阻塞的线程被唤醒，从而避免惊群问题。
从 linux 的 fork 子进程看，父进程中初始化了 listenFd(serverSocket 内封装那个 fd)，然后 fork 出了子进程，子进程就将父进程中的 linstenFd 个 copy 过来了，所以多个进程就是公用了一个 listenFd，那这个时候都去调用 accept(listenFd)，就存在多个进程都阻塞在 listenFd 上，从而引发惊群效应。
从 java 的角度看：使用线程池去调用同一个 serverSocket.accept()，这样就存在惊群问题，所以同样可以依靠内核的 WQ_FLAG_EXCLUSIVE 标识来解决。
但是从另外一个角度，变换一个线程池设计，其实也就是可以避 accept() 的惊群的：那就是单线程执行 accept()，将 accept() 获得的 clientSocket 交给另外一个线程池去处理。
这种方式的问题就在于 accept() 是单线程的，如果网络并发非常大，以至于单程处理不过来，那么客户端的链接请求完成后，就会在完全队列中挤压，极端情况就是完全对了满了，已经链接上来的客户单通信延迟增大，而再有客户端连接请求，则会失败。
ps：accept() 操作很费时么？如果它仅仅是当三次握手完成后，从完全连接队列中获取链接，然后初始化 ClientSocket，那么这都是纯内存操作，岂不是应该很快才对 (Redis 的单线程很快不是就是因为单线程执行的操作都是纯内存操作么)，linux 内核大神求解。
epoll 中的惊群
同样的，先来看 epoll 的哪些操作是阻塞的，再来分析是否有惊群问题
- epoll_create：初始化一个 epoll，即初始化那个红黑树、就绪队列结构。是不阻塞的。
- epoll_ctl：增删改查那个红黑树。比如将 ft 注册到 epoll 中、从 epoll 中删除等等。也是不阻塞的。
- epoll_wait。这个就是去轮询就绪队列的，看哪些 io 就绪了。这个操作是阻塞的
所以在 epoll 多路复用中，多线程调用 epoll_waite() 的时候，可能会导致惊群问题。具体参考：http://t.csdn.cn/i2mFP
jdk 线程池中的惊群
产生惊群的本质就多个线程阻塞在同一个资源上，当资源 readdy 的时候，会唤醒所有的线程，但唤醒的所有线程中，其实只有一个线程能够获得资源，其他线程又会被阻塞，所以其他线程就是无用的唤醒。
对于线程池就来看线程池中的线程是阻塞在哪里的？档案当然是线程池中的工作队列，而这个工作队列使用的是一个阻塞队列 BlockingQueue。所以问题就转换成线程池使用的阻塞队列，当队非空的时候，如何唤醒阻塞在这个队列上的线程了。
以比较常见的 ArrayBlockingQueu 和 LinkedBlockQueue 为例，会发现，当有元素入队的时候，唤醒线程它使用的是 signal() 方法，而不是 signalAll()，那么就只会随机唤醒一个阻塞在当前队列的中的线程 (notEmpty 是一个条件变量)，所以，当使用这两个阻塞队列的时候，jdk 中的线程池是没有惊群问题的。
前面也说过，使用 signal() 方法唤醒的一个最大问题就是饥饿问题、特别是高优先级线程饥饿问题。但是对于线程池来说，其目的只是要求有线程来驱动执行提交过来的任务，但到底哪个线程来执行，是无所谓的，这里 care 的是任务，有优先级也是任务的优先级，而不是线程的优先级。在线程池中的线程是没有任何差别的。
ps：在学习操作系统的时候，肯定都看到过一个说法，线程就是任务、任务就是线程，这两者是可以等价的。这句话既对又不对。对是因为在操作系统中，线程和任务的生命期是一样的，线程执行完任务，线程也就消失了，所以从这个层面来说，这句话是对的。
但是在高级语言中的线程池，其实是将这两个概念分开了，对任务进行实现了更高层面的抽象：
- 线程：是对 cpu 资源的一个抽象，cpu 调度完全依赖线程这个概念，所以在高级语言中，就特指获取 cpu 的一个载体。
- 任务：是指一系列的指令。对应到高级编程语言来说，就是一段代码，比如 java 中可以任务 Runnable 接口就是任务，它可以提交给线程池让线程来执行 Runnable#run() 方法的代码。
所以从这个层面说，线程是去驱动任务来执行的。但一定要注意，如果对应到操作系统中的任务 (exec() 执行的指令序列)，线程池中执行的任务还是 Runnable 么？答案是否定的，它实际上执行的是 blockingQueue.take().run()。所以 jdk 是利用了阻塞队列来实现了线程的复用。所以说 jdk 使用 Runnable 对任务实现了进一步高于线程概念的抽象。