从内核开发者的角度看协程与线程

第一部分：协程的核心机制介绍

协程的历史其实要早于线程，线程在实现上可以说是一个特化的1:N协程。只不过今天大家接触进程、线程的概念更多。

这个群里老年人多，当年应该都是做过实模式下的编程的，那个时候理论上操作系统只能加载一个进程，那个时候进程要使用系统服务的方法非常简单，就是手工产生一个中断。然后CPU的中断处理机制，会保护好发起中断的现场，然后讲当前执行地址设置为对应的中断处理函数的地址，处理完以后，会回到刚刚保存的现场。

这个过程，本质上就是协程的核心流程了。 这一种和call/return不同的 逻辑路径跳转方式。区别在于call/return系统进入处理函数，被调用函数会继续使用调用函数的“context”,就是栈。返回的时候会释放栈资源。 而基于中断的方式，发起方和处理方，可以使用自己的context。那个时候的系统通过中断的方法来达到提供系统服务的目的，一个很重要的原因就是可以保障在很多情况下，都能让系统处理函数至少能有一个可用的”context”（属于系统的资源）.这样当用户进程的context资源耗尽的情况下，也能调用一些系统服务。否则一个递归的栈溢出，整个系统都挂了。

总结一下，协程的概念，并不是与线程对应的，二应该与函数调用 call/return对应。区别在雨协程允许一个函数有多个入口、出口（逻辑上的），并且在切换到另一个函数执行时，允许使用一个新的context(包括调用栈）
有了这个利器之后，再加上CPU支持了保护模式，操作系统就可以接着实现 进程、线程的概念了。保护模式让一个函数的context除了调用栈，还包括了自己的页表。这样给函数一个看起来自己完全独占的内存控件。给一个函数绑定一个context并启动，就是启动了一个进程。
那么多个进程之间如何获得CPU?

一种是君子协议，就是要求每个进程在自己的代码里主动让出CPU（发起一个中断），然后在中断的处理代码里系统并不会返回到发起中断的进程，而是返回到另一个曾经发起过中断的进程里。 这个流程从实现上,和现在各种协程库的核心逻辑是一样的。

另一种，就是操作系统说提供的扩展机制，加入了一个霸道的“定时器中断”，这样操作系统就有机会在进程不愿意让出CPU的时候，也有机会运行调度器代码，从而让另一个进程或的时间片。 所以，目前操作系统支持的多进程/线程机制，本质上就是一个带定时器的协程调度器。

总结一下第二部分：多线程/多进程的实现，对应的是基于等待队列 时间中断的协程调度算法
call/return <-> resume/yield
thread/process 调度<-> 1:N(wait_list) Timer 的一种调度算法

第二部分：协程要解决什么问题？

进程/线程解决了什么问题？

多进程和多线程的区别其实比较小，系统在创建进程的时候会分配独立的页表，而创建线程的时候会共享所属进程的页表，在调度的时候上统一对待的，下面的问题里我就不区分多进程、多线程了。只说多进程。多进程要解决的问题：首先是多任务，一个设备同时只能执行一个任务的局限性实在是太大了，其次是提高稳定性，用户态的进程能把系统给搞挂了稳定性太差（win9x时代一天重启n次）。这两个需求现代的操作系统是结合有保护模式的CPU共同完成的，解决方案已经非常经典了。

其实多进程还解决了一个问题，要在解决上述两个问题的基础上，降低了很多io相关需求的开发难度。在现在典型的计算机体系的架构里，io有两种：同步的和异步的。同步io会让cpu在一个port上进行in,out操作。比如in req,out resp。io总线的速度远远慢于CPU的处理速度，如果CPU需要进行大量的IO操作，那么整个机器都卡死了。

目前从硬件的角度看解决这个问题的方法就是异步IO,cpu先把请求in到硬件里，然后硬件处理完了之后会通过中断线触发一个中断，这个时候CPU就可以在中断处理函数里用out得到硬件处理的结果。如果这个操作的结果是从IO设备复制大量的数据到内存上，还可以用DMA的方法在后台并行复制，CPU只需再等DMA的复制完成通知就好。 这个模式虽然解决问题，但编程复杂度是很高的，在这个层面要仔细考虑各种中断重入的问题，代码难写的一踏糊涂。

从使用者的角度讲，大家还是更喜欢 device.in(req),resp=device.out() 这样的同步编程模型，这样的模型更符合人正常的逻辑思路习惯：流程是线性的。要满足使用者的需求，内核提供的系统API要保障：你可以卡死你自己的进程，但绝对不能卡死内核，否则其它进程就无法获得时间片了。所以内核的IO相关API,做的事情就是先把请求发送给想要的硬件，然后把发起进程“挂起”（协程的术语是yield 让出），然后可以把时间片分给其它的进程，当硬件完成操作的时候会触发中断，内核在中断里找到发起操作的进程，将其恢复（协程术语resume)。这样内核永远不会卡住，而进程写起来也简单。所以以各位对linux内核的了解，内核的调度器 做的就是协程调度的事情

可以这么理解。很多用户态的协程调度器，就是一个针对当前应用场景定制的调度算法，内核里实现的是一个更关注公正的通用调度算法。进程解决的问题就是让大家写的时候更简单，同时系统更稳定

我这里再总结一下： 硬件提供了本质上的异步处理能力，即给硬件一个输入，硬件可以通过中断的方式告知CPU处理结果。内核在这个机制之上，构建了执行体切的调度算法，再基于这个调度算法，提供了看起来同步的系统调用给应用开发者。

有了多进程后，为什么要多线程？ 多个进程之前持有不同的页表，需要在进程间交换数据的话要使用进程同步设施。这个一是麻烦，二是有性能开销，于是就有了线程。从调度器的角度来看线程与进程基本一样，只是并没有一份独立的页表

海量IO的挑战

上述多进程+多线程的设计非常经典，也非常好用。但到了今天，一个典型的后台服务器有巨大的IO吞吐需求，那么按之前系统提供的设施，最直观的处理方法就是多进程，以http服务为例子：
void process_http_acceptor(s)
{
s.listen();
while(1){
clients = s.accept();
spawn(process_http_req_main,s);
}
}

void process_http_req_main(s)
{
req = s.read();
resp = real_process(req);
s.write(resp);
s.close();
}

这种方法在海量的IO吞吐面前有了性能问题。
首先spawn会创建一个进程，这个动静是很大的。而且目前内核的调度算法，当系统的进程数变大的时候性能会下降。最后，上述代码里的accept,read,write,close都是系统的IO函数。那么回忆一下这些函数的背后有多少工作？ system_call()->u/k switch->device.in()->save_context() & yield_to_schedule()->device.backwork()-> irq()->load_context()->schedule_resume_process()->k/u switch

这里面u/k switch,save_context(),load_context() 都是冗余开销（不参与具体工作，而是架构要求），当需要大量调用IO函数的时候，这些开销也是不小的。

解决这个问题有两个思路
一个是改变结构变成进程池结构活多线程结构，但不管是哪一种都会碰到一个问题：由于不能每次为一个请求分配一个独立的，可被内核调度器识别的执行体，那么就不能使用系统提供的同步IO函数，而是要自己实现异步的机制，来保障“不卡住任何执行体”(或短暂的卡住执行体）。这个思路是现在的经典解决方法，需要依赖系统提供poll函数或更彻底的aio函数 （把面向硬件的发起请求，完成中断的特征通过统一的方法暴露给用户态代码），具体细节资料非常多，我就不展开了。结果上就是开发不够友好，而且是专家级编程，因为系统调度器里为了不卡内核提供的各种便利都用不上了。

另一个就是协程的思路：spawn()调用创建的是协程，在用户态实现协程的调度器，并提供基于这个机制设计的新io函数。 这个思路提升性能的方法是
a.降低spawn启动执行体的成本
b.自己实现的协程调度算法对调度器管理的执行体总数不太敏感，能支持同时管理海量的协程执行体
c.协程库提供的yield/resume的实现是用户态的，没有u/k switch.
d.协程库提供的save_context/load_context更多是语言相关的而不是体系结构相关的，在有些脚本语言里会及其轻量。
e.要基于系统提供的异步io函数来重新实现所有的”同步io函数”
这些工作都做完之后，在能保持高性能的同时，也让继续保持了应用开发的简单性。那么上面的http服务代码会变成：

void main()
{
mainco = co.spawn(process_http_acceptor);
join(mainco);
}

void process_http_acceptor(s)
{
s.listen();
while(1){
clients = s.accept();
co.spawn(process_http_req_main,s);
}
}

void process_http_req_main(s)
{
req = co.read(s);
resp = real_process(req);
co.write(s,resp);
co.close(s);
}

那co.read怎么实现呢？

bytes co.read(s)
{
current_co = co.getcurrent();
system.aio_read(s,on_read, current_co);
bytes = co.yield(schedule_co);
return bytes;
}

void on_read(s,current_co,bytes)
{
schedule.colist.move_to_front(current_co,bytes)
}

void schedule_co()
{
while(1)
{
nextco,bytes = colist.popfront()
if(nextco.resume(bytes) != end)
colist.pushback(nextco)
}
}

可以看到，系统需要提供system.aio机制来模拟硬件的异步工作方式。这个是整个协程库能工作的基础。其次需要实现一个最简单的调度器,定义io完成后保存io结果的方法。最后需要基于这些机制，把同步io的api再实现一遍。

总结一下：通过协程的方法来解决海量IO的问题，是通过减少创建执行体的成本，减少context切换的成本来办到的。在使用上和多进程方式一致（是的，和多进程更像），对应用开发非常友好。

对比表格
创建进程：创建协程
devcie.in()：调用系统提供的aio函数
保存context,让出CPU:保存context(语言相关),通过yield转到调度协程
irq():aio函数完成回调
读取context,并让执行体活的cpu:读取context(语言相关),通过resume转到调用协程

第三部分：在产品中使用协程的问题
上面从两个维度解释了协程的相关概念,看起来协程又快又好用，那就立刻用起来吧！且慢，这个世界的现实是残酷的。
第一个问题，如何挑选协程库：
有些脚本语言好像内置了协程的实现， C语言实现协程的方式好多，有些系统好像也提供了对协程的直接API支持，这些这些… 本来以为搞明白的事情，在现实面前又糊涂了。

从刚刚的理论可知，协程最底层的是定义”执行体“，并设计”一套yield/resume”机制，这个概念是强语言相关的。本质上可以分为两类：在机器语言里实现 / 在脚本语言里实现。
在机器语言里实现：这个执行体的定义是体系结构相关的，所以系统提供的API最靠谱，自己实现容易掉到各种坑里。当然这个成本很多时候并不低，比如保存context至少需要保存寄存器和栈。
在脚本语言里：如果语言本身就支持，就用这个语言提供的基础设施（比如lua的协程库），通常脚本语言里的执行体都更为轻量，lua里保存context只是保存一个lua_state的虚拟机指针而已，而新建一个虚拟机的成本，连1k内存都不需要 。
有些脚本语言本身没有提供支持，但可以在其虚拟机上扩展实现出类似机制，比较典型的是python的greenlet库。

有了第一层的执行体与执行体切换机制后，还需要在此基础上定义调度算法并实现调度器。比较主流的调度算法是1：N的调度算法，即系统有一个协程称作调度协程，这个协程肯能把执行流转给起掌管的N个用户协程中的任意一个，而这N个被掌管的用户协程只能把执行流切换会调度协程。还有N:M,N:M:K 性的调度算法，具体这些选择可以看一些讨论调度算法的论文，传统上是为了解决调度算法如何解决多个CPU的问题的。但用户态协程通常是在一个进程上跑的，这些更复杂的调度算法一般都用不上。

有了调度器后，真正坑的地方才开始：需要结合调度器，以及系统提供的”异步io”设施，把所有的同步IO函数都实现一遍。这才是各个“协程库”最大代码量的地方。比如在python里，基于greenlet的gevent,就自己实现了调度算法，并提供了一大堆的io函数的重实现。

总结一下：协程库包括三层内容,即定义执行体以及实现执行体之间切换的方法，定义并实现调度器，重新实现同步IO函数。以上三层，是一层套一层的，并且每一层都是一个制式。在同一个进程里，多个制式的“协程库”之间无法。
第一层 co.spawn(),co.yield(co),co.resume(co)
第二层 schedule.suspend(co),schedule.ready(co)
第三层 io.read(),io.open()

第二个问题：
基于第一个问题，每个协程库都实现了一打io函数。注意，这个时候协程库提供的这打io函数可不是可选项，而是必选项！因为这用来替代系统函数的。只是用户态的协程库，没办法强制用kernel-mode来阻止应用开发干坏事：比如调用一个其它的io函数。这种行为相当于引用开发直接在内核层做事，很容易把这个系统搞挂。

这个问题理解起来很容易，但解决起来非常困难，这要求协程库的使用者，使用的其它第三方库也要基于这个协程库。很多时候这个约定是让人绝望的… 所以现在选协程库就和选系统API一样重要。

这里做的比较好的是python,有很多第三方库都有基于gevent的版本，而且gevent也可以用hook的方法试着让一些第三方库把io调用切换到其提供的io函数上来。其它语言都没有一个得到广泛支持的协程库（看到这里该叫框架了吧），用起来都是非常费劲的。（作为一个lua的深粉，我默默的流泪）

大部分脚本语言都支持用C扩展功能，如何在C扩展里做好协程兼容，涉及到了一些更本质的问题。下次再讲。。。

总结一下：协程框架的选择是强侵入性的，一个进程只能选择一个协程框架，并且所有的库都需要基于这个框架提供的io函数进行开发。