异步
Jack <jack@net9.org>
香港科技大学
简介
一般来说，简单的异步（Asynchronous）调用是这样一种调用方式：发起者请求一个异步调用，通知执行者，然后处理其他工作，在某一个同步点等待执行者的完成；执行者执行调用的实际操作，完成后通知发起者。可以看出，在异步调用中有两种角色：发起者和执行者，它们都是能主动运行的对象，我们称为主动对象，同时还有一个同步点，主动对象在同步点协调同步。在本文中，我们讨论主要是通用计算机、多进程多线程的分时操作系统上的异步调用。在操作系统的角度上来看，主动对象包括了进程、线程和硬件上的IC等，至于中断，可以看作总是在某个进程或者线程的上下文借用一下CPU。而同步操作可以通过操作系统得各种同步机制：互斥锁，信号灯等等来完成。
我们可以先看看异步调用在Windows(本文中一般不加指出的话，都是特指NT/2000)读写文件中的应用。Windows中的ReadFile和WriteFile都提供了异步的接口。以ReadFile为例，
BOOL ReadFile(HANDLE hFile, LPVOID lpBuffer, DWORD nNumberOfBytesToRead, LPDWORD lpNumberOfBytesRead, LPOVERLAPPED lpOverlapped);
如果最后一个参数lpOverlapped不为NULL，并且文件以FILE_FLAG_OVERLAPPED标志打开，那么这个调用就是异步的：ReadFile会立刻返回，如果操作没有立刻完成（返回FALSE并且GetLastError()返回ERROR_IO_PENDING），那么调用者可以在某个时刻通过WaitForSingleObject等函数来等待中的hEvent来等待操作完成（可能已经完成）进行同步，当操作完成以后，可以调用GetOverlappedResult者获得操作的结果，比如是否成功，读取了多少字节等等。这里的发起者就是应用程序，而执行者就是操作系统本身，至于执行者是怎么执行的，我们会在后面的篇幅讨论。而两者的同步就是通过一个Windows Event来完成。
把这个异步调用的过程再抽象和扩展一些，我们可以把异步调用需要解决的问题归结为两个：一个是执行的动力，另一个是主动对象的调度。简单来说，前者是各个主动对象（线程、进程或者一些代码）是如何获得CPU，后者是各个主动对象如何协同工作，保证操作的流程是协调正确的。一般来说，进程和线程都可以由操作系统直接调度而获得CPU，而更细粒度的，比如一些代码的调度，往往就需要一个更复杂的模型（比如在操作系统内部的实现，这时候线程的粒度太粗了）。而主动对象的调度，当参与者较少的时候，可以通过基本的同步机制来完成，在更复杂的情况下，可能通过一个schedule机制来做会更实际一些。
动力和调度
如前所述，异步调用主要需要解决两个问题：执行的动力和执行的调度。最普遍的情况就是，一个主导流程的调用者进程（线程），一个或多个工作者进程（线程），通过操作系统提供的同步机制来完成异步调用。这个同步机制在扩展化的情形下，是一个或多个栅栏Barrier，对应于每个同步的执行点。所有需要在这个执行点同步的主动对象会等待相应的Barrier，直到所有对象都完成。在一些简化的情形，比如说工作者并不关心调用者的同步，那么这个Barrier可以简化成信号灯，在只有一个工作者的情况下，可以简化成一个Windows事件Event或者条件变量 Condition Variable。
现在来考虑复杂的情形。假设我们用一些线程来协作完成一项工作，各个线程的执行之间有先后顺序上的限制，而操作系统就是这项工作的调度者，负责在适当的时候调度适当的线程来获得CPU。显然，并发执行中的一个线程对于另外一个线程来说，本质上就是异步的，假如它们之间有调用关系，那也就是一个异步调用。而操作系统可以通过基本的同步机制使得合适的线程才被调度，其他未完成的线程则处于等待状态。举例说，我们有4个线程A,B,C,D来完成一项工作，其中的顺序限制是A>B;C>D，“>”表示左边的线程完成必须先于右边的线程执行，而“;”表示两个线程可以同时进行。同时假设B的一个操作需要调用C来完成，显而易见，这时候这个操作就是一个异步调用。我们可以在每个“>”的位置设定一个同步点，然后通过一个信号灯来完成同步。线程B，C等待第一个信号灯，而D会等待第二个信号灯。这个例子的动力和调度都是通过操作系统的基本机制（线程调度和同步机制）来完成。
把这个过程抽象一下，可以描述为：若干个主动对象（包括代码）协调来完成一项工作，通过一个调度器来调度，实际上，这个调度器可能只是一些调度规则。显然，进程或者线程只要被调度就能获得CPU，所以我们主要考虑代码（比如一个函数）怎么样才能获得执行。用工作者线程来调用这个函数显然是直观和通用的一个方案。事实上，在用户空间(user space)或者用户态(user mode)，这个方法是很常用的。而在内核态(kernel mode)，则可以通过中断来获得CPU，这个通过注册IDT入口和触发软中断就可以完成。硬件设备上的IC是另一个动力之源。而主动对象的调度，最基本的也是前面说的各种同步机制。另一个常用的机制就是回调函数，需要注意的是，回调函数一般会发生在跟调用者不一样的上下文，比如说同一个进程的不同线程，这个差别会带来一些限制。如果需要回调发生在调用者的进程（线程）上下文，则需要一些类似Unix下的signal或者Windows下的APC机制，这一点我们在后面会有所阐述。那么在回调函数里面一般作些什么事情呢？最常用的，跟同步机制结合在一起，当然就是释放一个互斥锁，信号灯或者Windows Event（Unix的条件变量）等等，从而使得等待同步的其他对象可以得到调度而重新执行，实际上，也可以看作是通知调度器（操作系统）某些主动对象（等待同步的）可以重新被调度了，从而调度器重新调度。但是对于另外一些调度器，在这个过程中可能不需要同步对象的参与。在一些极端一些的例子里，调度甚至不要求严格有序的。
在实际应用中，根据环境的限制，异步调用的动力和调度的实现方式可以有很大差别。我们会在后面的例子里加以说明。
操作系统中的异步：Windows的异步I/O
Windows NT/2000是一个抢占式的分时操作系统。Windows的调度单位是线程，它的 I/O架构是完全异步的，也就是说同步的I/O实际上都基于异步I/O来完成。一个用户态的线程请求一个I/O的时候会导致一个运行状态从user mode到kernel mode的转变（操作系统把内核映射到每个进程的2G-4G的地址上，对于每个进程都是一样的）。这个过程是通过中断调用内核输出的一些System Service来完成，比如说ReadFile实际上会执行NtReadFile（ZwReadFile），需要注意的是，运行上下文仍然是当前线程。NtReadFile的实现则基于Windows内核的异步I/O框架，在I/O Manager的协助下完成。需要指出的是，I/O Manager只是由若干API构成的一个抽象概念，并没有一个真正的I/O Manager线程在运行。
Windows的I/O驱动程序是层次堆积的。每个驱动程序会提供一致的接口以供初始化、清理和功能调用。驱动程序的调用基于I/O请求包（I/O Request Packet, IRP），而不是像普通的函数调用那样使用栈来传递参数。操作系统和PnP管理器根据注册表在适当的时机初始化和清理相应的驱动程序。在一般的功能调用的时候，IRP里面会指定功能调用号码以及相应的上下文或者参数（I/O stack location）。一个驱动程序可能调用别的驱动程序，这个过程可能是同步的（线程上下文不改变)，也可能是异步的。NtReadFile的实现，大致是向最上层的驱动程序发出一个或多个IRP，然后等待相应事件的完成（同步的情况），或者直接返回（带Overlapped的情况），这些都在发起请求的线程执行。
当驱动程序处理IRP的时候，它可能立刻完成，也可能在中断里才能完成，比如说，往硬件设备发出一个请求（通常可以是写I/O port），当设备完成操作的时候会触发一个中断，然后在中断处理函数里得到操作结果。Windows有两类中断，硬件设备的中断和软中断，分成若干个不同的优先级（IRQL）。软中断主要有两种：DPC(Delayed Procedure Call)和APC(Asynchronous Procedure Call)，都处于较低的优先级。驱动程序可以为硬件中断注册ISR(Interrupt Service Routine)，一般就是修改IDT某个条目的入口。同样，操作系统也会为DPC和APC注册适当的中断处理例程（也是在IDT中）。值得指出的是，DPC是跟处理器相关的，每个处理器会有一个DPC队列，而APC是跟线程相关的，每个线程会有它的APC队列（实际上包括一个Kernel APC队列和User APC队列，它们的调度策略有所区别），可以想象，APC并不算严格意义上的中断，因为中断可能发生在任何一个线程的上下文中，它被称为中断，主要是因为IRQL的提升（从PASSIVE到APC），APC的调度一般在线程切换等等情形下进行。当中断发生的时候，操作系统会调用中断处理例程，对于硬件设备的ISR，一般处理是关设备中断，发出一个DPC请求，然后返回。不在设备的中断处理中使用太多的CPU时间，主要考虑是否则可能丢失别的中断。由于硬件设备中断的IRQL比DPC中断的高，所以在ISR里面DPC会阻塞，直到ISR返回IRQL回到较低的水平，才会触发DPC中断，在DPC中断里执行从硬件设备读取数据以及重新请求、开中断等操作。ISR或者DPC可能在任何被中断的线程上下文（arbitrary thread context）执行，事实上线程的上下文是不可见的，可以认为是系统借用一下时间片而已。
总的来说，Windows的异步I/O架构中，主要有两种动力，一是发起请求的线程，一部分内核代码会在这个线程上下文执行，二是ISR和DPC，这部分内核代码会在中断里完成，可能使用任何一个线程的上下文。而调度常见使用回调和事件（KEVENT），比如说在往下一层的驱动程序发出请求的时候，可以指定一个完成例程Completion Routine，当下层的驱动完成这个请求的时候会调用这个例程，而往往在这个例程里，就是简单的触发一下一个事件。
另外可以顺便提一下Linux。Linux 2.6也有类似的中断机制，它有更多的软中断优先级，即不同优先级的softirq，而类似于DPC，Linux也提供了专门的软中断，对应DPC的就是tasklet。Linux没有一个像windows这么一致的层次驱动程序架构，所以它的异步I/O稍微粗糙一些，主要是通过以前的一些阻塞点，现在直接返回-EIOCBRETRY，而让调用者在合适的时机继续重试。在这个方法中，可以认为整个操作由一个函数完成，每次操作有进展时，都把这个函数从头执行一遍，当然已经完成的部分就不会再有实际的I/O。这样的最大好处是原有的文件系统和驱动程序不用完全重写。而对于同步调用，只要阻塞就可以了，这样对系统的修改较小。这时候，要提供POSIX aio的语义，就可能需要提供一些用户线程来完成重试的过程了（回想Windows可以通过中断和DPC完成的）。而对于Solaris，也是类似的处理，如果设备支持异步I/O，那就通过中断可以完成，否则就使用内部的LWP来模拟。
应用程序：一个异步的HTTP服务器的设计
假设我们要设计一个HTTP服务器，它的设计目标包括：高并发性、精简（部分支持HTTP/1.1）、支持plug-in结构。在不少场合可能都有这个需求。总体上来说，HTTP服务器可以类比成一个基于多线程的操作系统：OS调度每个工作线程在适当的时候获得执行，而工作线程提供服务（也就是处理HTTP请求）。在这个基础上，主要的考虑就是调度粒度的大小，粒度太大的时候并发性会降低，而粒度太小又可能因为任务切换（考虑OS的Context Switching）而导致效率降低，所以这又是一个折衷的结果。类似于Apache（以及其他的HTTP服务器），我们可以把一个HTTP处理过程分为若干个状态，基于这些状态可以构造出一个HTTP处理的状态机。这种情况下，我们就可以把每个状态的处理作为调度的粒度。一个调度过程就是：一个工作线程从全局的任务队列里取出一个HTTP_Context结构；根据当前的状态完成相应处理；然后根据状态机设置下一个状态；再放回到全局的任务队列里。这样子，若干个HTTP状态就可以通过这个调度策略构成一个完整HTTP处理过程。显而易见，一个状态对于下一个状态处理的调用都可以认为是异步的。一个HTTP状态机的设计如下图所示。
图1. HTTP状态机
工作线程的函数其实就是两个操作：从状态队列里取出一个HTTP_Context，调用HTTP_Context的service()函数，周而复此。在这个架构上，就很容易引入异步I/O和Plug-in的机制了。事实上我们也可以使用基于事件（例如select/poll）的I/O策略来模拟异步I/O，实现中使用一个用户线程就可以了。
对于异步I/O和Plug-in的调用，我们也是采用类似于Linux 2.6里面aio的重试方案，而异步完成的时候采用回调函数。在某个状态上，如果系统需要I/O操作（recv或者send），则会请求一个异步I/O（操作系统提供的异步I/O或者由用户线程模拟的异步I/O），这时候相应的HTTP_Context不会重新回到状态队列里，而在I/O完成的回调函数里面才会重新放回到状态队列，得到重新调度的机会。HTTP_Context得到重新调度的时候会检查I/O状态（这个可以通过一些标志位来完成），如果已经完成，则处理然后设置下一状态，重新调度，否则可以重新请求一个新的I/O请求。Plug-in也可以使用类似的方案，比如说一个Plug-in要跟外部的一个服务器通信，这时候就可以在通信完成的时候才把HTTP_Context重新放回到状态队列。显然，Plug-in跟HTTP状态是多对多的关系，一个Plug-in可以在若干个关心的状态注册自身，同时还可以设置一些short-path来提高处理的效率。
结论
总的来说，异步调用的设计和应用归根结底就是对多个主动对象的管理问题：如何提供执行的动力以及如何保证执行的顺序逻辑。主要考虑的问题是主动对象的粒度以及执行方式，同步或者回调来完成顺序的调度，或者使用近似的调度而加一些鲁棒的错误处理机制来保证语义的正确。后者可以考虑在使用基于事件的socket的时候，readable事件的通知可以是冗余的，或者说可以比实际中发生的readable事件更多，这个时候使用非阻塞的socket,有些read()（或者recv()）会直接返回EWOULDBLOCK，系统只要考虑处理这种情况（使用non blocking socket而不是blocking socket），当例外的情况不多的时候是可以接受的。这时候可以说事件的报告就只是近似的。
