在C10M secret中，Errata Security 的首席执行官Robert Graham提出了一个观点:The Kernel Is The Problem, Not The Solution，他说如果想要解决C10M实现高性能，需要从以下三个方面入手:

  • 内存管理: 不要让内核管理应用的内存， 应用应该自己管理自己的内存

  • 数据包: 不要让内核处理数据，尽量让应用自己处理数据包

  • 调度: 不要让内核去调度，尽量让应用自己去调度

本篇博客就讲讲调度相关的协程

协程(coroutine)

协程最开始是kunth(<计算机程序设计的艺术>的作者)定义的，由co和routine组成，与之对应的是subroutine。subroutine是把一个大的程序拆分成很多小块，这些小块就是subroutine，这些subroutine是有层级关系的，子subroutine总是在父subroutine之前执行完。subroutine只有一个入口，只返回一次，退出就结束了。而coroutine可以有多个重入点，coroutine之间可以相互协作，主动让出cpu和恢复执行，他们之间的地位是对等的

看一个生产者-消费者的协程示例:

Plain Textvar q := new queue
coroutine produce loop while q is not full  create some new items  add the items to q # 这里的yield to == yield + resume yield to consume
coroutine consume loop while q is not empty  remove some items from q  use the items yield to produce
call produce

协程的阻塞这段代码创建了两个协程，生产者协程和消费者协程，生产者把队列填满后，会切换到消费者协程执行，消费者协程消费完队列后会唤起生产者协程。注意，这不是递归。这个例子是通过yield to来实现协程的调度。

有了yield和resume之后，我们可以在协程之间任意切换，当然也不是说所有的地方都需要去切换，一般是在阻塞的地方，去yield让出cpu，然后切换到其他协程。在Linux操作系统中，如果线程调用了阻塞的api，比如socket等待数据，当线程发现socket没有已就绪的数据，会修改自己的线程状态，然后让出cpu，接着内核会进行调度，选出下一个执行的线程。如果对这些阻塞的api不做修改，协程调用了这些系统函数，那么会把整个线程阻塞住，所以要实现协程还需把阻塞的api换成非阻塞的，然后应用自己调度出下一个要执行的协程，这样就达到了应用自己调度的目的。在把阻塞api替换成非阻塞api时，要保证这些api的入参和出参是一致的。腾讯的c++协程库libco就出过一个bug，在创建socket的时候设置nonBlock，然后获取的时候依然是block

下面是系统调用futex的火焰图:

图片

上图可以看出，调用futex争抢锁失败后，线程把自己加入到wait_queue，然后内核会去调度，决定下一个执行的线程。调度这部分是最耗时的，所以在实现的时候，去优化这些阻塞的系统调用，这样在阻塞后，不再让出cpu，而是去执行下一个协程。至于系统调用和上下文切换的消耗都是比较小的，系统调用的开销大概是几百ns，上下文的切换大概是5us左右。在替换阻塞api这块，大部分的语言的第三方类库协程都是通过hook来实现的，hook类似于一层代理，把阻塞的api包装成非阻塞。

协程栈

实现协程除了替换阻塞调用之外，还需要实现协程栈。线程是有自己的栈的，在线程切换的时候，需要保存上个线程栈的状态，基本上就是把寄存器的值放回到栈帧上，修改程序计数器之类的。但是一个线程下的协程逻辑上是共用一个栈，细分下来，每个协程的栈都是不一样的，所以在协程切换时需要考虑是把保存上一个协程的状态到内存中，然后把下一个协程的栈恢复到线程的系统栈上？还是每个协程都有自己独立的栈或是其他。协程栈的实现一般分为两种：有栈协程和无栈协程。有栈协程和无栈协程的区别在于 协程切换的时候是否需要保存和恢复协程栈

有栈协程

栈帧的大小在编译期就能确定，但是栈的大小在编译期是无法确定的，随着栈帧的开辟和销毁，栈的大小也是动态变化的。实现协程的挂起和恢复需要保存上下文，挂起的时候把该协程的栈帧和寄存器都保存下来，恢复的时候把保存下来的值恢复成栈帧，这种方式能够在任意时候恢复协程，称之为有栈协程。下面是几种有栈协程的实现：

静态栈: 每个协程有自己独立的固定大小的栈。但是大小不好控制，设置太小，栈容易溢出 。如果设置过大，容易造成内存浪费。

共享栈: 申请一个比较大的栈，比如2M。每次执行协程时，把保存下来的协程栈复制到共享栈，挂起时保存，所有协程共用一个栈，这样可以避免内存的浪费。但是像C这种允许地址引用的编程语言，如果有指针指向协程栈的地址，那么当下次运行时，指针就会不可用，因为下次协程恢复栈后，栈帧中局部变量表的地址会发生变化

虚拟栈(c++都用这个): 思想来自于操作系统的虚拟内存。其实现和共享栈类似，不过会把协程栈的地址映射成虚拟地址，当别的指针指向协程栈上的变量时，把虚拟地址给它

无栈协程

 如下图所示，无栈协程有点像状态机，全程只用了一个栈，把一个协程拆分成很多小块，这些小块的入口只有一个，然后通过改变state的值来实现协程的不同逻辑。这种实现无需保存协程的栈帧，可以节省内存提高速度，但是不能实现协程的任意切换，比如在执行firstCoroutinePart1时，无法切换到其他协程，除非把firstCoroutinePart1执行完，而有栈协程是可以在任意地方切换。c++20实现了无栈协程
















int state = 0;func next(){ if state == 0 { return firstCoroutinePart1(); }else if state == 1 { return firstCoroutinePart2(); }}func firstCoroutinePart1(){ state = 1 ...}func firstCoroutinePart2(){ state = 0 ...}


协程的调度

在好多文档里，都说协程是不需要实现调度，协程应该有应用或者说程序员自己去调度,他们认为协程+调度器=fiber。各个语言的实现也不尽相同，lua的协程是需要手动调度，go自带了调度器，c++两个都有。如果程序员手动协作，万一某个协程执行很久,其他协程就都得等着,所以一般库会实现调度器，使用起来更加无感,同时达到了抢占时的目的。下面是两种经典的调度机制：

星型切换调度: 协程A->调度程序->协程B->调度程序

循环调度: 协程A->->协程B->调度程序(效率比较高)

现在一般选择循环调度。除此之外，在线程模型这块，一般会选择M:N这种线程，那么调度就由原先的单线程调度变成了多线程调度，为了保证每个内核线程都有协程运行，多线程调度时会使用worksteal算法来实现协程的窃取。对于IO事件，还会使用epoll防止调度数据未就绪的协程。


参考文档

  1. http://highscalability.com/blog/2013/5/13/the-secret-to-10-million-concurrent-connections-the-kernel-i.html

  2. programming language pragmatics


本文作者：刘伟