原文：http://www.cnblogs.com/sharra/archive/2010/12/30/1921287.html
因为需要了解底层设备访问的原理，所以惯用高层应用语言的我，需要了解一下Linux的设备访问机制，尤其是处理一组非阻塞IO的原理方法，标准的术语好像是叫多路复用。以下文章部分句子有引用之处，恕没有一一指出出处。
对于接触过Linux内核或设备驱动开发的读者，一定清楚poll和select系统调用，以及从2.5版本引入的epoll机制（epoll机制包含三个系统调用）。网上关于它们的文章，有说用法的，甚为详细，更有分析源代码的，又比较深入，且枝节颇多。经过几篇文章的阅读，我把觉得比较核心的东西写下来吧。我的用意是尽可能以简单的概念，比对他们三者的异同。
几经查找我才确定下来，poll和select应该被归类为这样的系统调用，它们可以阻塞地同时探测一组支持非阻塞的IO设备，是否有事件发生（如可读，可写，有高优先级的错误输出，出现错误等等），直至某一个设备触发了事件或者超过了指定的等待时间——也就是它们的职责不是做IO，而是帮助调用者寻找当前就绪的设备。同类型的产品是Windows的IOCP，它也是处理多路复用，只是把IO和探测封装在了一起了。
准备的知识有两点：1、fd；2、op->poll。
在Linux里面，设备都被抽象为文件，一系列的设备文件就有自己独立的虚拟文件系统，所以，设备在系统调用参数中的表示就是file description。fd其实就是一个整数（特别地，标准输入，输出，错误输出分别对应的fd是0，1，2）。与内核打交道的时候，传递整数的fd可以在自己的文件系统中作进一步的检查是否合法，如果只是返回指针就不能这样操作了，毕竟指针是无差别无意义的。
通过fd访问file，通过file可以访问其fileOperator，这里面我们要关心的一个fileOp就是poll。因为系统调用poll和select，就是依靠这个文件操作poll实现的。poll文件操作有两个参数，一个是文件本身，一个可以看做是当设备尚未就绪时调用的回调函数，这个函数是把设备自己特有的等待队列传给内核，让内核把当前的进程挂载到其中（因为当设备就绪时，设备就应该去唤醒在自己特有等待队列中的所有节点，这样当前进程就获取了完成的信号了）。poll文件操作返回的必须是一组标准的掩码，其中的各个位指示当前的不同的就绪状态（全0为没有任何事件触发）。
再谈谈早期多路复用的版本poll和select。
本质而言，poll和select的共同点就是，对全部指定设备做一次poll，当然这往往都是还没有就绪的，那就会通过回调函数把当前进程注册到设备的等待队列，如果所有设备返回的掩码都没有显示任何的事件触发，就去掉回调函数的函数指针，进入有限时的睡眠状态，再恢复和不断做poll，再作有限时的睡眠，直到其中一个设备有事件触发为止。只要有事件触发，系统调用返回，回到用户态，用户就可以对相关的fd作进一步的读或者写操作了。当然，这个时候还不是所有的设备都就绪的喔，那就得不断地poll或者select了，而做一次这样的系统调用都得轮询所有的设备，次数是设备数*（睡眠次数-1），也就是时间复杂度是O（n），还得做几次O（n）呢。可见，对于现在普遍的服务器程序，需要同时并发监听数千个连接，并且连接需要重复使用的情况，poll和select就存在这样的性能瓶颈。另外，数千个设备fd在每次调用时，都需要将其从用户空间复制到内核空间，这里的开销不可忽略。
poll和select放在一起，是因为其机制一致，而参数和数据结构就略有不同。select一次性传入三组作用于不同信道的设备fd，分别是输入，输出和错误异常。各组的fd期待各组所特有的，由代码指定的一组事件，如输入信道期待输入就绪，输入挂起和错误等事件。 然后，select就挑选调用者关心的fd做poll文件操作，检测返回的掩码，看看是否有fd所属信道感兴趣的事件，比如看看这个属于输出信道的fd有没有输出就绪等一系列的事件发生，一样地，如果有一个fd发生感兴趣事件就返回调用了。select，为了同时处理三组使用不同的事件判断规则的fd，采用了位图的方式表示，一组一个位图，位长度是当中最大的fd值，上限是1024，三组就是3072，而且这还只是传入的位图，还有一样大小的传出的位图。当fd数越来越多时，所需的存储开销比较大。
既然，一组fd处理起来比较粗放，那就各个fd自己准备好了。poll()系统调用是System V的多元I/O解决方案。它有三个参数，第一个是pollfd结构的数组指针，也就是指向一组fd及其相关信息的指针，因为这个结构包含的除了fd，还有期待的事件掩码和返回的事件掩码，实质上就是将select的中的fd，传入和传出参数归到一个结构之下，也不再把fd分为三组，也不再硬性规定fd感兴趣的事件，这由调用者自己设定。这样，不使用位图来组织数据，也就不需要位图的全部遍历了。按照一般队列地遍历，每个fd做poll文件操作，检查返回的掩码是否有期待的事件，以及做是否有挂起和错误的必要性检查，如果有事件触发，就可以返回调用了。
回到poll和select的共同点，面对高并发多连接的应用情境，它们显现出原来没有考虑到的不足，虽然poll比起select又有所改进了。除了上述的关于每次调用都需要做一次从用户空间到内核空间的拷贝，还有这样的问题，就是当处于这样的应用情境时，poll和select会不得不多次操作，并且每次操作都很有可能需要多次进入睡眠状态，也就是多次全部轮询fd，我们应该怎么处理一些会出现重复而无意义的操作。
这些重复而无意义的操作有：1、从用户到内核空间拷贝，既然长期监视这几个fd，甚至连期待的事件也不会改变，那拷贝无疑就是重复而无意义的，我们可以让内核长期保存所有需要监视的fd甚至期待事件，或者可以再需要时对部分期待事件进行修改；2、将当前线程轮流加入到每个fd对应设备的等待队列，这样做无非是哪一个设备就绪时能够通知进程退出调用，聪明的开发者想到，那就找个“代理”的回调函数，代替当前进程加入fd的等待队列好了（这也是我后来才总结出来，Linux的等待队列，实质上是回调函数队列吧，也可以使用宏来将当前进程“加入”等待队列，其实就是将唤醒当前进程的回调函数加入队列）。这样，像poll系统调用一样，做poll文件操作发现尚未就绪时，它就调用传入的一个回调函数，这是epoll指定的回调函数，它不再像以前的poll系统调用指定的回调函数那样，而是就将那个“代理”的回调函数加入设备的等待队列就好了，这个代理的回调函数就自己乖乖地等待设备就绪时将它唤醒，然后它就把这个设备fd放到一个指定的地方，同时唤醒可能在等待的进程，到这个指定的地方取fd就好了。我们把1和2结合起来就可以这样做了，只拷贝一次fd，一旦确定了fd就可以做poll文件操作，如果有事件当然好啦，马上就把fd放到指定的地方，而通常都是没有的，那就给这个fd的等待队列加一个回调函数，有事件就自动把fd放到指定的地方，当前进程不需要再一个个poll和睡眠等待了。
epoll的优点
1. 支持一个进程打开大数目的socket描述符(FD)
select 最不能忍受的是一个进程所打开的FD是有一定限制的，由FD_SETSIZE设置，默认值是2048。对于那些需要支持的上万连接数目的IM服务器来说显然太少了。这时候你一是可以选择修改这个宏然后重新编译内核，不过资料也同时指出这样会带来网络效率的下降，二是可以选择多进程的解决方案(传统的Apache方案)，不过虽然linux上面创建进程的代价比较小，但仍旧是不可忽视的，加上进程间数据同步远比不上线程间同步的高效，所以也不是一种完美的方案。不过 epoll则没有这个限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。
2. IO效率不随FD数目增加而线性下降
传统的select/poll另一个致命弱点就是当你拥有一个很大的socket集合，不过由于网络延时，任一时间只有部分的socket是"活跃"的，但是select/poll每次调用都会线性扫描全部的集合，导致效率呈现线性下降。但是epoll不存在这个问题，它只会对"活跃"的socket进行操作---这是因为在内核实现中epoll是根据每个fd上面的callback函数实现的。那么，只有"活跃"的socket才会主动的去调用 callback函数，其他idle状态socket则不会，在这点上，epoll实现了一个"伪"AIO，因为这时候推动力在os内核。在一些 benchmark中，如果所有的socket基本上都是活跃的---比如一个高速LAN环境，epoll并不比select/poll有什么效率，相反，如果过多使用epoll_ctl,效率相比还有稍微的下降。但是一旦使用idle connections模拟WAN环境,epoll的效率就远在select/poll之上了。
3. 使用mmap加速内核与用户空间的消息传递。
这点实际上涉及到epoll的具体实现了。无论是select,poll还是epoll都需要内核把FD消息通知给用户空间，如何避免不必要的内存拷贝就很重要，在这点上，epoll是通过内核于用户空间mmap同一块内存实现的。而如果你想我一样从2.5内核就关注epoll的话，一定不会忘记手工 mmap这一步的。
4. 内核微调
这一点其实不算epoll的优点了，而是整个linux平台的优点。也许你可以怀疑linux平台，但是你无法回避linux平台赋予你微调内核的能力。比如，内核TCP/IP协议栈使用内存池管理sk_buff结构，那么可以在运行时期动态调整这个内存pool(skb_head_pool)的大小--- 通过echo XXXX>/proc/sys/net/core/hot_list_length完成。再比如listen函数的第2个参数(TCP完成3次握手的数据包队列长度)，也可以根据你平台内存大小动态调整。更甚至在一个数据包面数目巨大但同时每个数据包本身大小却很小的特殊系统上尝试最新的NAPI网卡驱动架构。
epoll机制就是这样改进的了。诚然，fd少的时候，当前进程一个个地等问题不大，可是现在和尚多了，方丈就不好管了。以前设备事件触发时，只负责唤醒当前进程就好了，而当前进程也只能傻傻地在poll里面等待或者循环，再来一次poll，也不知道这个由设备提供的poll性能如何，能不能检查出当前进程已经在等待了就立即返回，当然，我也不明白为什么做了一遍的poll之后，去掉回调函数指针了，还得再做，不是说好了会去唤醒进程的吗？
现在就让事件触发回调函数多做一步。本来设备还没就绪就调用一个回调函数了，现在再在这个回调函数里面做一个注册另一个回调函数的操作，目的就是使得设备事件触发多走一步，不仅仅是唤醒当前进程，还要把自己的fd放到指定的地方。就像收本子的班长，以前得一个个学生地去问有没有本子，如果没有，它还得等待一段时间而后又继续问，现在好了，只走一次，如果没有本子，班长就告诉大家去那里交本子，当班长想起要取本子，就去那里看看或者等待一定时间后离开，有本子到了就叫醒他，然后取走。这个道理很简单，就是老师和班干们常说的，大家多做一点工作，我的工作就轻松很多了，尤其是需要管理的东西越来越多时。
这种机制或者说模式，我想在Java的FutureTask里面应该也会用到的，一堆在线程池里面跑着的线程（当然这是任务，不是线程，接口是Callable，不是Runnable.run，是Callable.call，它是可以返回结果的），谁先做好就应该先处理呀，可是难道得一个个问吗？干脆就谁好了，谁就按照既定的操作暴露自己，这样FutureTask的get方法就可以马上知道当前最先完成的线程了，就可以取此线程返回结果了。
