在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


本文作者:刘伟