一、上下文切换技术

简述

在进一步之前，让我们先回顾一下各种上下文切换技术。

不过首先说明一点术语。当我们说“上下文”的时候，指的是程序在执行中的一个状态。通常我们会用调用栈来表示这个状态——栈记载了每个调用层级执行到哪里，还有执行时的环境情况等所有有关的信息。

当我们说“上下文切换”的时候，表达的是一种从一个上下文切换到另一个上下文执行的技术。而“调度”指的是决定哪个上下文可以获得接下去的CPU时间的方法。

进程

进程是一种古老而典型的上下文系统，每个进程有独立的地址空间，资源句柄，他们互相之间不发生干扰。

每个进程在内核中会有一个数据结构进行描述，我们称其为进程描述符。这些描述符包含了系统管理进程所需的信息，并且放在一个叫做任务队列的队列里面。

 

很显然，当新建进程时，我们需要分配新的进程描述符，并且分配新的地址空间(和父地址空间的映射保持一致，但是两者同时进入COW状态)。这些过程需要一定的开销。

 

进程状态

 

忽略去linux内核复杂的状态转移表，我们实际上可以把进程状态归结为三个最主要的状态：就绪态，运行态，睡眠态。这就是任何一本系统书上都有的三态转换图。

 

就绪和执行可以互相转换，基本这就是调度的过程。而当执行态程序需要等待某些条件(最典型就是IO)时，就会陷入睡眠态。而条件达成后，一般会自动进入就绪。

 

阻塞

 

当进程需要在某个文件句柄上做IO，这个fd又没有数据给他的时候，就会发生阻塞。具体来说，就是记录XX进程阻塞在了XX fd上，然后将进程标记为睡眠态，并调度出去。当fd上有数据时(例如对端发送的数据到达)，就会唤醒阻塞在fd上的进程。进程会随后进入就绪队列，等待合适的时间被调度。

 

阻塞后的唤醒也是一个很有意思的话题。当多个上下文阻塞在一个fd上(虽然不多见，但是后面可以看到一个例子)，而且fd就绪时，应该唤醒多少个上下文呢？传统上应当唤醒所有上下文，因为如果仅唤醒一个，而这个上下文又不能消费所有数据时，就会使得其他上下文处于无谓的死锁中。

 

但是有个著名的例子——accept，也是使用读就绪来表示收到的。如果试图用多个线程来accept会发生什么？当有新连接时，所有上下文都会就绪，但是只有第一个可以实际获得fd，其他的被调度后又立刻阻塞。这就是惊群问题thundering herd problem。

 

现代linux内核已经解决了这个问题，方法惊人的简单——accept方法加锁。

 

(inet_connection_sock.c:inet_csk_wait_for_connect)

线程

 

线程是一种轻量进程，实际上在linux内核中，两者几乎没有差别，除了一点——线程并不产生新的地址空间和资源描述符表，而是复用父进程的。

 

但是无论如何，线程的调度和进程一样，必须陷入内核态。

 

二、传统网络服务模型

 

进程模型

 

为每个客户分配一个进程。优点是业务隔离，在一个进程中出现的错误不至于影响整个系统，甚至其他进程。Oracle传统上就是进程模型。缺点是进程的分配和释放有非常高的成本。因此Oracle需要连接池来保持连接减少新建和释放，同时尽量复用连接而不是随意的新建连接。

 

线程模型

 

为每客户分配一个线程。优点是更轻量，建立和释放速度更快，而且多个上下文间的通讯速度非常快。缺点是一个线程出现问题容易将整个系统搞崩溃。

 

一个例子

 

py_http_fork_thread.py

在这个例子中，线程模式和进程模式可以轻易的互换。

 

如何工作的：

 

父进程监听服务端口

在有新连接建立的时候，父进程执行fork，产生一个子进程副本

如果子进程需要的话，可以exec(例如CGI)

父进程执行(理论上应当先执行子进程，因为exec执行的快可以避免COW)到accept后，发生阻塞

上下文调度，内核调度器选择下一个上下文，如无意外，应当就是刚刚派生的子进程

子进程进程进入读取处理状态，阻塞在read调用上，所有上下文均进入睡眠态

随着SYN或者数据报文到来，CPU会唤醒对应fd上阻塞的上下文(wait_queue)，切换到就绪态，并加入调度队列

上下文继续执行到下一个阻塞调用，或者因为时间片耗尽被挂起

评价

 

同步模型，编写自然，每个上下文可以当作其他上下文不存在一样的操作，每次读取数据可以当作必然能读取到。

 

进程模型自然的隔离了连接。即使程序复杂且易崩溃，也只影响一个连接而不是在整个系统。

 

生成和释放开销很大(效率测试的进程fork和线程模式开销测试)，需要考虑复用。

 

进程模式的多客户通讯比较麻烦，尤其在共享大量数据的时候。

 

性能

 

thread模式，虚拟机：

 

1: 909.27 2: 3778.38 3: 4815.37 4: 5000.04 10: 4998.16 50: 4881.93 100: 4603.24 200: 3445.12 500: 1778.26 (出现错误)

fork模式，虚拟机：

 

1: 384.14 2: 435.67 3: 435.17 4: 437.54 10: 383.11 50: 364.03 100: 320.51 (出现错误)

thread模式，物理机：

 

1: 6942.78 2: 6891.23 3: 6584.38 4: 6517.23 10: 6178.50 50: 4926.91 100: 2377.77

注意在python中，虽然有GIL，但是一个线程陷入到网络IO的时候，GIL是解锁的。因此从调用开始到调用结束，减去CPU切换到其他上下文的时间，是可以多线程的。现象是，在此种状况下可以观测到短暂的python CPU用量超过100%。

 

如果执行多个上下文，可以充分利用这段时间。所观测到的结果就是，只能单核的python，在小范围内，其随着并发数上升，性能居然会跟着上升。如果将这个过程转移到一台物理机上执行，那么基本不能得出这样的结论。这主要是因为虚拟机上内核陷入的开销更高。

 

三、C10K 问题

 

描述

 

当同时连接数在10K左右时，传统模型就不再适用。实际上在效率测试报告的线程切换开销一节可以看到，超过1K后性能就差的一塌糊涂了。

 

进程模型的问题

 

在C10K的时候，启动和关闭这么多进程是不可接受的开销。事实上单纯的进程fork模型在C1K时就应当抛弃了。

 

Apache的prefork模型，是使用预先分配(pre)的进程池。这些进程是被复用的。但即便是复用，本文所描述的很多问题仍不可避免。

 

线程模式的问题

 

从任何测试都可以表明，线程模式比进程模式更耐久一些，性能更好。但是在面对C10K还是力不从心的。问题是，线程模式的问题出在哪里呢？

 

内存？

 

有些人可能认为线程模型的失败首先在于内存。如果你这么认为，一定是因为你查阅了非常老的资料，并且没仔细思考过。

 

你可能看到资料说，一个线程栈会消耗8M内存(linux默认值，ulimit可以看到)，512个线程栈就会消耗4G内存，而10K个线程就是80G。所以首先要考虑调整栈深度，并考虑爆栈问题。

 

听起来很有道理，问题是——linux的栈是通过缺页来分配内存的(How does stack allocation work in Linux?)，不是所有栈地址空间都分配了内存。因此，8M是最大消耗，实际的内存消耗只会略大于实际需要的内存(内部损耗，每个在4k以内)。但是内存一旦被分配，就很难回收(除非线程结束)，这是线程模式的缺陷。

 

这个问题提出的前提是，32位下地址空间有限。虽然10K个线程不一定会耗尽内存，但是512个线程一定会耗尽地址空间。然而这个问题对于目前已经成为主流的64位系统来说根本不存在。

 

内核陷入开销？

 

所谓内核陷入开销，就是指CPU从非特权转向特权，并且做输入检查的一些开销。这些开销在不同的系统上差异很大。

 

线程模型主要通过陷入切换上下文，因此陷入开销大听起来有点道理。实际上，这也是不成立的。线程在什么时候发生陷入切换？正常情况下，应当是IO阻塞的时候。同样的IO量，难道其他模型就不需要陷入了么？只是非阻塞模型有很大可能直接返回，并不发生上下文切换而已。

 

效率测试报告的基础调用开销一节，证实了当代操作系统上内核陷入开销是非常惊人的小的(10个时钟周期这个量级)。

 

线程模型的问题在于切换成本高

 

熟悉linux内核的应该知道，近代linux调度器经过几个阶段的发展。

 

linux2.4的调度器

O(1)调度器

CFS

实际上直到O(1)，调度器的调度复杂度才和队列长度无关。在此之前，过多的线程会使得开销随着线程数增长(不保证线性)。

 

O(1)调度器看起来似乎是完全不随着线程的影响。但是这个调度器有显著的缺点——难于理解和维护，并且在一些情况下会导致交互式程序响应缓慢。

 

CFS使用红黑树管理就绪队列。每次调度，上下文状态转换，都会查询或者变更红黑树。红黑树的开销大约是O(logm)，其中m大约为活跃上下文数(准确的说是同优先级上下文数)，大约和活跃的客户数相当。

 

因此，每当线程试图读写网络，并遇到阻塞时，都会发生O(logm)级别的开销。而且每次收到报文，唤醒阻塞在fd上的上下文时，同样要付出O(logm)级别的开销。

 

分析

 

O(logm)的开销看似并不大，但是却是一个无法接受的开销。因为IO阻塞是一个经常发生的事情。每次IO阻塞，都会发生开销。而且决定活跃线程数的是用户，这不是我们可控制的。更糟糕的是，当性能下降，响应速度下降时。同样的用户数下，活跃上下文会上升(因为响应变慢了)。这会进一步拉低性能。

 

问题的关键在于，http服务并不需要对每个用户完全公平，偶尔某个用户的响应时间大大的延长了是可以接受的。在这种情况下，使用红黑树去组织待处理fd列表（其实是上下文列表），并且反复计算和调度，是无谓的开销。

 

四、多路复用

 

简述

 

要突破C10K问题，必须减少系统内活跃上下文数(其实未必，例如换一个调度器，例如使用RT的SCHED_RR)，因此就要求一个上下文同时处理多个链接。而要做到这点，就必须在每次系统调用读取或写入数据时立刻返回。否则上下文持续阻塞在调用上，如何能够复用？这要求fd处于非阻塞状态，或者数据就绪。

 

上文所说的所有IO操作，其实都特指了他的阻塞版本。所谓阻塞，就是上下文在IO调用上等待直到有合适的数据为止。这种模式给人一种“只要读取数据就必定能读到”的感觉。而非阻塞调用，就是上下文立刻返回。如果有数据，带回数据。如果没有数据，带回错误(EAGAIN)。因此，“虽然发生错误，但是不代表出错”。

 

但是即使有了非阻塞模式，依然绕不过就绪通知问题。如果没有合适的就绪通知技术，我们只能在多个fd中盲目的重试，直到碰巧读到一个就绪的fd为止。这个效率之差可想而知。

 

在就绪通知技术上，有两种大的模式——就绪事件通知和异步IO。其差别简要来说有两点。就绪通知维护一个状态，由用户读取。而异步IO由系统调用用户的回调函数。就绪通知在数据就绪时就生效，而异步IO直到数据IO完成才发生回调。

 

linux下的主流方案一直是就绪通知，其内核态异步IO方案甚至没有被封装到glibc里去。围绕就绪通知，linux总共提出过三种解决方案。我们绕过select和poll方案，看看epoll方案的特性。

 

另外提一点。有趣的是，当使用了epoll后(更准确说只有在LT模式下)，fd是否为非阻塞其实已经不重要了。因为epoll保证每次去读取的时候都能读到数据，因此不会阻塞在调用上。

 

epoll

 

用户可以新建一个epoll文件句柄，并且将其他fd和这个”epoll fd”关联。此后可以通过epoll fd读取到所有就绪的文件句柄。

 

epoll有两大模式，ET和LT。LT模式下，每次读取就绪句柄都会读取出完整的就绪句柄。而ET模式下，只给出上次到这次调用间新就绪的句柄。换个说法，如果ET模式下某次读取出了一个句柄，这个句柄从未被读取完过——也就是从没有从就绪变为未就绪。那么这个句柄就永远不会被新的调用返回，哪怕上面其实充满了数据——因为句柄无法经历从非就绪变为就绪的过程。

 

类似CFS，epoll也使用了红黑树——不过是用于组织加入epoll的所有fd。epoll的就绪列表使用的是双向队列。这方便系统将某个fd加入队列中，或者从队列中解除。

 

要进一步了解epoll的具体实现，可以参考这篇linux下poll和epoll内核源码剖析。

 

性能

 

如果使用非阻塞函数，就不存在阻塞IO导致上下文切换了，而是变为时间片耗尽被抢占（大部分情况下如此），因此读写的额外开销被消除。而epoll的常规操作，都是O(1)量级的。而epoll wait的复制动作，则和当前需要返回的fd数有关(在LT模式下几乎就等同于上面的m，而ET模式下则会大大减少)。

 

但是epoll存在一点细节问题。epoll fd的管理使用红黑树，因此在加入和删除时需要O(logn)复杂度(n为总连接数)，而且关联操作还必须每个fd调用一次。因此在大连接量下频繁建立和关闭连接仍然有一定性能问题(超短连接)。不过关联操作调用毕竟比较少。如果确实是超短连接，tcp连接和释放开销就很难接受了，所以对总体性能影响不大。

 

固有缺陷

 

原理上说，epoll实现了一个wait_queue的回调函数，因此原理上可以监听任何能够激活wait_queue的对象。但是epoll的最大问题是无法用于普通文件，因为普通文件始终是就绪的——虽然在读取的时候不是这样。

 

这导致基于epoll的各种方案，一旦读到普通文件上下文仍然会阻塞。golang为了解决这个问题，在每次调用syscall的时候，会独立的启动一个线程，在独立的线程中进行调用。因此golang在IO普通文件的时候网络不会阻塞。

 

五、事件通知机制下的几种程序设计模型

 

简述

 

使用通知机制的一大缺憾就是，用户进行IO操作后会陷入茫然——IO没有完成，所以当前上下文不能继续执行。但是由于复用线程的要求，当前线程还需要接着执行。所以，在如何进行异步编程上，又分化出数种方案。

 

用户态调度

 

首先需要知道的一点就是，异步编程大多数情况下都伴随着用户态调度问题——即使不使用上下文技术。

 

因为系统不会自动根据fd的阻塞状况来唤醒合适的上下文了，所以这个工作必须由其他人——一般就是某种框架——来完成。

 

你可以想像一个fd映射到对象的大map表，当我们从epoll中得知某个fd就绪后，需要唤醒某种对象，让他处理fd对应的数据。

 

当然，实际情况会更加复杂一些。原则上所有不占用CPU时间的等待都需要中断执行，陷入睡眠，并且交由某种机构管理，等待合适的机会被唤醒。例如sleep，或是文件IO，还有lock。更精确的说，所有在内核里面涉及到wait_queue的，在框架里面都需要做这种机制——也就是把内核的调度和等待搬到用户态来。

 

当然，其实也有反过来的方案——就是把程序扔到内核里面去。其中最著名的实例大概是微软的http服务器了。

 

这个所谓的“可唤醒可中断对象”，用的最多的就是协程。

 

协程

 

协程是一种编程组件，可以在不陷入内核的情况进行上下文切换。如此一来，我们就可以把协程上下文对象关联到fd，让fd就绪后协程恢复执行。

当然，由于当前地址空间和资源描述符的切换无论如何需要内核完成，因此协程所能调度的，只有在同一进程中的不同上下文而已。

 

如何做到

 

这是如何做到的呢？

 

我们在内核里实行上下文切换的时候，其实是将当前所有寄存器保存到内存中，然后从另一块内存中载入另一组已经被保存的寄存器。对于图灵机来说，当前状态寄存器意味着机器状态——也就是整个上下文。其余内容，包括栈上内存，堆上对象，都是直接或者间接的通过寄存器来访问的。

 

但是请仔细想想，寄存器更换这种事情，似乎不需要进入内核态么。事实上我们在用户态切换的时候，就是用了类似方案。

 

C coroutine的实现，基本大多是保存现场和恢复之类的过程。python则是保存当前thread的top frame(greenlet)。

 

但是非常悲剧的，纯用户态方案(setjmp/longjmp)在多数系统上执行的效率很高，但是并不是为了协程而设计的。setjmp并没有拷贝整个栈(大多数的coroutine方案也不应该这么做)，而是只保存了寄存器状态。这导致新的寄存器状态和老寄存器状态共享了同一个栈，从而在执行时互相破坏。而完整的coroutine方案应当在特定时刻新建一个栈。

 

而比较好的方案(makecontext/swapcontext)则需要进入内核(sigprocmask)，这导致整个调用的性能非常低。

 

协程与线程的关系

 

首先我们可以明确，协程不能调度其他进程中的上下文。而后，每个协程要获得CPU，都必须在线程中执行。因此，协程所能利用的CPU数量，和用于处理协程的线程数量直接相关。

 

作为推论，在单个线程中执行的协程，可以视为单线程应用。这些协程，在未执行到特定位置(基本就是阻塞操作)前，是不会被抢占，也不会和其他CPU上的上下文发生同步问题的。因此，一段协程代码，中间没有可能导致阻塞的调用，执行在单个线程中。那么这段内容可以被视为同步的。

 

我们经常可以看到某些协程应用，一启动就是数个进程。这并不是跨进程调度协程。一般来说，这是将一大群fd分给多个进程，每个进程自己再做fd-协程对应调度。

 

基于就绪通知的协程框架

 

首先需要包装read/write，在发生read的时候检查返回。如果是EAGAIN，那么将当前协程标记为阻塞在对应fd上，然后执行调度函数。

调度函数需要执行epoll(或者从上次的返回结果缓存中取数据，减少内核陷入次数)，从中读取一个就绪的fd。如果没有，上下文应当被阻塞到至少有一个fd就绪。

查找这个fd对应的协程上下文对象，并调度过去。

当某个协程被调度到时，他多半应当在调度器返回的路上——也就是read/write读不到数据的时候。因此应当再重试读取，失败的话返回1。

如果读取到数据了，直接返回。

这样，异步的数据读写动作，在我们的想像中就可以变为同步的。而我们知道同步模型会极大降低我们的编程负担。

 

CPS模型

 

其实这个模型有个更流行的名字——回调模型。之所以扯上CPS这么高大上的玩意，主要是里面涉及不少有趣的话题。

 

首先是回调模型的大致过程。在IO调用的时候，同时传入一个函数，作为返回函数。当IO结束时，调用传入的函数来处理下面的流程。这个模型听起来挺简单的。

 

然后是CPS。用一句话来描述这个模型——他把一切操作都当作了IO，无论干什么，结果要通过回调函数来返回。从这个角度来说，IO回调模型只能被视作CPS的一个特例。

 

例如，我们需要计算1+2*3，在cps里面就需要这么写：

 

mul(lambda x: add(pprint.pprint, x, 1), 2, 3)

其中mul和add在python里面如下定义：

 

add = lambda f, *nums: f(sum(nums))

mul = lambda f, *nums: f(reduce(lambda x,y: x*y, nums))

而且由于python没有TCO，所以这样的写法会产生非常多的frame。

 

但是要正确理解这个模型，你需要仔细思考一下以下几个问题：

 

函数的调用过程为什么必须是一个栈？

 

IO过程在什么时间发生？调用发生时，还是回调时？

 

回调函数从哪里调用？如果当时利用工具去看上下文的话，调用栈是什么样子的？

 

函数组件和返回值

 

不知道你是否思考过为什么函数调用层级(上下文栈)会被表述为一个栈——是否有什么必要性，必须将函数调用的过程定义为一个栈呢？

 

原因就是返回值和同步顺序。对于大部分函数，我们需要得到函数计算的返回值。而要得到返回值，调用者就必须阻塞直到被调用者返回为止。因此调用者的执行状态就必须被保存，等到被调用者返回后继续——从这点来说，调用其实是最朴素的上下文切换手段。而对于少部分无需返回的函数，我们又往往需要他的顺序外部效应——例如干掉了某个进程，开了一个灯，或者仅仅是在环境变量里面添加了一项内容。而顺序外部效应同样需要等待被调用者返回以表明这个外部效应已经发生。

 

那么，如果我们不需要返回值也不需要顺序的外部效应呢？例如启动一个背景程序将数据发送到对端，无需保证发送成功的情况下。或者是开始一个数据抓取行为，无需保证抓取的成功。

 

通常这种需求我们就凑合着用一个同步调用混过去了——反正问题也不严重。但是对于阻塞相当严重的情况而言，很多人还是会考虑到将这个行为做成异步过程。目前最流行的异步调用分解工具就是mq——不仅异步，而且分布。当然，还有一个更简单的非分布方案——开一个coroutine。

 

而CPS则是另一个方向——函数的返回值可以不返回调用者，而是返回给第三者。

 

IO 过程在什么时间发生

 

其实这个问题的核心在于——整个回调模型是基于多路复用的还是基于异步IO的？

 

原则上两者都可以。你可以监听fd就绪，也可以监听IO完成。当然，即使监听IO完成，也不代表使用了内核态异步接口。很可能只是用epoll封装的而已。

 

回调函数的上下文环境

 

这个问题则需要和上面提到的“用户态调度框架”结合起来说。IO回调注册的实质是将回调函数绑定到某个fd上——就如同将coroutine绑定上去那样。只是coroutine允许你顺序的执行，而callback则会切碎函数。当然，大部分实现中，使用callback也有好处——coroutine的最小切换开销也在50ns，而call本身则只有2ns。

 

状态机模型

 

状态机模型是一个更难于理解和编程的模型，其本质是每次重入。

 

想像你是一个周期失忆的病人(就像“一周的朋友”那样)。那么你如何才能完成一项需要跨越周期的工作呢？例如刺绣，种植作物，或者——交一个男朋友。

 

当然，类比到失忆病人的例子上必须有一点限制。正常的生活技能，还有一些常识性的东西必须不能在周期失忆范围内。例如重新学习认字什么的可没人受的了。

 

答案就是——做笔记。每次重复失忆后，你需要阅读自己的笔记，观察上次做到哪个步骤，下一个步骤是什么。这需要将一个工作分解为很多步骤，在每个步骤内“重入”直到步骤完成，转移到下一个状态。

 

同理，在状态机模型解法里，每次执行都需要推演合适的状态，直到工作完成。这个模型已经很少用到了，因为相比回调函数来说，状态机模型更难理解和使用，性能差异也不大。

 

最后顺带一提，交一个男友的方案和其他几个略有不同，主要靠颜好高冷反差萌，一般人就不要尝试挑战了。。。当然一般人也不会一周失忆一次，毕竟生活不是韩剧也不是日本动漫。。。