本文主體轉(zhuǎn)自https://zhuanlan.zhihu.com/p/63179839衫哥，加上了自己的理解和批注
從事服務端開發(fā)孝治，少不了要接觸網(wǎng)絡編程冈欢。epoll作為linux下高性能網(wǎng)絡服務器的必備技術至關重要活玲，nginx瞒津、redis、skynet和大部分游戲服務器都使用到這一多路復用技術来氧。
因為epoll的重要性诫给，不少游戲公司（如某某九九）在招聘服務端同學時，可能會問及epoll相關的問題啦扬。比如epoll和select的區(qū)別是什么考传？epoll高效率的原因是什么僚楞？如果只靠背誦泉褐，顯然不能算上深刻的理解膜赃。
網(wǎng)上雖然也有不少講解epoll的文章挺邀，但要不是過于淺顯，就是陷入源碼解析跳座，很少能有通俗易懂的端铛。于是決定編寫此文，讓缺乏專業(yè)背景知識的讀者也能夠明白epoll的原理疲眷。文章核心思想是：
要讓讀者清晰明白EPOLL為什么性能好禾蚕。
本文會從網(wǎng)卡接收數(shù)據(jù)的流程講起，串聯(lián)起CPU中斷狂丝、操作系統(tǒng)進程調(diào)度等知識换淆；再一步步分析阻塞接收數(shù)據(jù)、select到epoll的進化過程几颜；最后探究epoll的實現(xiàn)細節(jié)倍试。
目錄
四攘已、內(nèi)核接收網(wǎng)絡數(shù)據(jù)全過程
下圖是一個典型的計算機結(jié)構(gòu)圖伞辛，計算機由CPU踊兜、存儲器（內(nèi)存）于游、網(wǎng)絡接口等部件組成筷频。了解epoll本質(zhì)的第一步担忧，要從硬件的角度看計算機怎樣接收網(wǎng)絡數(shù)據(jù)。
? ? ? ? ? 計算機結(jié)構(gòu)圖（圖片來源：linux內(nèi)核完全注釋之微型計算機組成結(jié)構(gòu)）
下圖展示了網(wǎng)卡接收數(shù)據(jù)的過程。在①階段，網(wǎng)卡收到網(wǎng)線傳來的數(shù)據(jù)锯厢；經(jīng)過②階段的硬件電路的傳輸剪撬；最終將數(shù)據(jù)寫入到內(nèi)存中的某個地址上（③階段）。這個過程涉及到DMA傳輸梨水、IO通路選擇等硬件有關的知識，但我們只需知道：網(wǎng)卡會把接收到的數(shù)據(jù)寫入內(nèi)存。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 網(wǎng)卡接收數(shù)據(jù)的過程
通過硬件傳輸，網(wǎng)卡接收的數(shù)據(jù)存放到內(nèi)存中腺律。操作系統(tǒng)就可以去讀取它們谬返。
了解epoll本質(zhì)的第二步鹿鳖，要從CPU的角度來看數(shù)據(jù)接收。要理解這個問題，要先了解一個概念——中斷歼疮。
計算機執(zhí)行程序時讯榕，會有優(yōu)先級的需求。比如送浊，當計算機收到斷電信號時（電容可以保存少許電量闭树，供CPU運行很短的一小段時間），它應立即去保存數(shù)據(jù)米奸，保存數(shù)據(jù)的程序具有較高的優(yōu)先級逐工。
一般而言者吁，由硬件產(chǎn)生的信號需要cpu立馬做出回應（不然數(shù)據(jù)可能就丟失），所以它的優(yōu)先級很高对途。cpu理應中斷掉正在執(zhí)行的程序膳犹，去做出響應渐裂；當cpu完成對硬件的響應后膝捞，再重新執(zhí)行用戶程序央渣。中斷的過程如下圖拔第，和函數(shù)調(diào)用差不多逛万。只不過函數(shù)調(diào)用是事先定好位置得封，而中斷的位置由“信號”決定。
? ?中斷程序調(diào)用
以鍵盤為例指郁，當用戶按下鍵盤某個按鍵時忙上，鍵盤會給cpu的中斷引腳發(fā)出一個高電平。cpu能夠捕獲這個信號闲坎，然后執(zhí)行鍵盤中斷程序手形。下圖展示了各種硬件通過中斷與cpu交互艘虎。
cpu中斷（圖片來源：net.pku.edu.cn）
現(xiàn)在可以回答本節(jié)提出的問題了：當網(wǎng)卡把數(shù)據(jù)寫入到內(nèi)存后须蜗，網(wǎng)卡向cpu發(fā)出一個中斷信號，操作系統(tǒng)便能得知有新數(shù)據(jù)到來忘蟹，再通過網(wǎng)卡中斷程序去處理數(shù)據(jù)寝受。
了解epoll本質(zhì)的第三步队魏，要從操作系統(tǒng)進程調(diào)度的角度來看數(shù)據(jù)接收膛虫。阻塞是進程調(diào)度的關鍵一環(huán)抓歼，指的是進程在等待某事件（如接收到網(wǎng)絡數(shù)據(jù)）發(fā)生之前的等待狀態(tài)茵休，recv捕儒、select和epoll都是阻塞方法。了解“進程阻塞為什么不占用cpu資源？”叮称，也就能夠了解這一步横媚。
為簡單起見狡忙，我們從普通的recv接收開始分析，先看看下面代碼：
//創(chuàng)建socket
ints = socket(AF_INET, SOCK_STREAM,0);
//綁定
bind(s, ...)
//監(jiān)聽
listen(s, ...)
//接受客戶端連接
intc = accept(s, ...)
//接收客戶端數(shù)據(jù)
recv(c, ...);
//將數(shù)據(jù)打印出來
printf(...)
這是一段最基礎的網(wǎng)絡編程代碼址芯，先新建socket對象灾茁，依次調(diào)用bind、listen谷炸、accept北专，最后調(diào)用recv接收數(shù)據(jù)。recv是個阻塞方法旬陡，當程序運行到recv時拓颓，它會一直等待，直到接收到數(shù)據(jù)才往下執(zhí)行季惩。
那么阻塞的原理是什么录粱？
工作隊列
操作系統(tǒng)為了支持多任務腻格，實現(xiàn)了進程調(diào)度的功能画拾，會把進程分為“運行”和“等待”等幾種狀態(tài)。運行狀態(tài)是進程獲得cpu使用權(quán)菜职，正在執(zhí)行代碼的狀態(tài)青抛；等待狀態(tài)是阻塞狀態(tài)，比如上述程序運行到recv時酬核，程序會從運行狀態(tài)變?yōu)榈却隣顟B(tài)蜜另，接收到數(shù)據(jù)后又變回運行狀態(tài)适室。操作系統(tǒng)會分時執(zhí)行各個運行狀態(tài)的進程，由于速度很快举瑰，看上去就像是同時執(zhí)行多個任務捣辆。
下圖中的計算機中運行著A、B此迅、C三個進程汽畴，其中進程A執(zhí)行著上述基礎網(wǎng)絡程序，一開始耸序，這3個進程都被操作系統(tǒng)的工作隊列所引用忍些，處于運行狀態(tài)，會分時執(zhí)行坎怪。
工作隊列中有A罢坝、B和C三個進程
等待隊列
當進程A執(zhí)行到創(chuàng)建socket的語句時，操作系統(tǒng)會創(chuàng)建一個由文件系統(tǒng)管理的socket對象（如下圖）搅窿。這個socket對象包含了發(fā)送緩沖區(qū)嘁酿、接收緩沖區(qū)、等待隊列等成員男应。等待隊列是個非常重要的結(jié)構(gòu)痹仙，它指向所有需要等待該socket事件的進程。
創(chuàng)建socket
當程序執(zhí)行到recv時殉了，操作系統(tǒng)會將進程A從工作隊列移動到該socket的等待隊列中（如下圖）开仰。由于工作隊列只剩下了進程B和C，依據(jù)進程調(diào)度薪铜，cpu會輪流執(zhí)行這兩個進程的程序众弓，不會執(zhí)行進程A的程序。所以進程A被阻塞隔箍，不會往下執(zhí)行代碼谓娃，也不會占用cpu資源。
socket的等待隊列
ps：操作系統(tǒng)添加等待隊列只是添加了對這個“等待中”進程的引用蜒滩，以便在接收到數(shù)據(jù)時獲取進程對象滨达、將其喚醒，而非直接將進程管理納入自己之下俯艰。上圖為了方便說明捡遍，直接將進程掛到等待隊列之下。
喚醒進程
當socket接收到數(shù)據(jù)后竹握，操作系統(tǒng)將該socket等待隊列上的進程重新放回到工作隊列画株，該進程變成運行狀態(tài)（當socket事件觸發(fā)時，也就是有數(shù)據(jù)到來，會取下一個進程結(jié)構(gòu)調(diào)用其回調(diào)谓传，將其掛到工作隊列中）蜈项，繼續(xù)執(zhí)行代碼。也由于socket的接收緩沖區(qū)已經(jīng)有了數(shù)據(jù)续挟，recv可以返回接收到的數(shù)據(jù)紧卒。
四、內(nèi)核接收網(wǎng)絡數(shù)據(jù)全過程
這一步诗祸，貫穿網(wǎng)卡常侦、中斷、進程調(diào)度的知識贬媒，敘述阻塞recv下聋亡，內(nèi)核接收數(shù)據(jù)全過程。
如下圖所示际乘，進程在recv阻塞期間坡倔，計算機收到了對端傳送的數(shù)據(jù)（步驟①）。數(shù)據(jù)經(jīng)由網(wǎng)卡傳送到內(nèi)存（步驟②）脖含，然后網(wǎng)卡通過中斷信號通知cpu有數(shù)據(jù)到達罪塔，cpu執(zhí)行中斷程序（步驟③）。此處的中斷程序主要有兩項功能养葵，先將網(wǎng)絡數(shù)據(jù)寫入到對應socket的接收緩沖區(qū)里面（步驟④）征堪，再喚醒進程A（步驟⑤），重新將進程A放入工作隊列中关拒。
內(nèi)核接收數(shù)據(jù)全過程
喚醒進程的過程如下圖所示佃蚜。
喚醒進程
以上是內(nèi)核接收數(shù)據(jù)全過程
這里留有兩個思考題，大家先想一想着绊。
其一谐算，操作系統(tǒng)如何知道網(wǎng)絡數(shù)據(jù)對應于哪個socket？
其二归露，如何同時監(jiān)視多個socket的數(shù)據(jù)洲脂？
（——我是分割線，想好了才能往下看哦~）
公布答案的時刻到了剧包。
第一個問題：因為一個socket對應著一個端口號恐锦，而網(wǎng)絡數(shù)據(jù)包中包含了ip和端口的信息，內(nèi)核可以通過端口號找到對應的socket疆液。當然一铅，為了提高處理速度，操作系統(tǒng)會維護端口號到socket的索引結(jié)構(gòu)枚粘，以快速讀取馅闽。（就是說網(wǎng)卡中斷CPU后，CPU的中斷函數(shù)從網(wǎng)卡存數(shù)據(jù)的內(nèi)存拷貝數(shù)據(jù)到對應fd的接收緩沖區(qū)馍迄，具體是哪一個fd福也，CPU會檢查port，放到對應的fd中）
第二個問題是多路復用的重中之重攀圈，是本文后半部分的重點暴凑！
服務端需要管理多個客戶端連接赘来，而recv只能監(jiān)視單個socket现喳，這種矛盾下，人們開始尋找監(jiān)視多個socket的方法犬辰。epoll的要義是高效的監(jiān)視多個socket嗦篱。從歷史發(fā)展角度看，必然先出現(xiàn)一種不太高效的方法幌缝，人們再加以改進灸促。只有先理解了不太高效的方法，才能夠理解epoll的本質(zhì)涵卵。
假如能夠預先傳入一個socket列表浴栽，如果列表中的socket都沒有數(shù)據(jù)，掛起進程轿偎，直到有一個socket收到數(shù)據(jù)典鸡，喚醒進程。這種方法很直接坏晦，也是select的設計思想萝玷。
為方便理解，我們先復習select的用法昆婿。在如下的代碼中间护，先準備一個數(shù)組（下面代碼中的fds），讓fds存放著所有需要監(jiān)視的socket挖诸。然后調(diào)用select汁尺，如果fds中的所有socket都沒有數(shù)據(jù)，select會阻塞多律，直到有一個（也可以是多個）socket接收到數(shù)據(jù)痴突，select返回，喚醒進程狼荞。用戶可以遍歷fds辽装，通過FD_ISSET判斷具體哪個socket收到數(shù)據(jù)，然后做出處理相味。
ints = socket(AF_INET, SOCK_STREAM,0);
bind(s, ...)
listen(s, ...)
intfds[] =? 存放需要監(jiān)聽的socket
while(1){
intn = select(..., fds, ...)
for(inti=0; i < fds.count; i++){
if(FD_ISSET(fds[i], ...)){
//fds[i]的數(shù)據(jù)處理
? ? ? ? }
? ? }
}
select的流程
select的實現(xiàn)思路很直接拾积。假如程序同時監(jiān)視如下圖的sock1、sock2和sock3三個socket，那么在調(diào)用select之后拓巧，操作系統(tǒng)把進程A（包括了select邏輯）分別加入這三個socket的等待隊列中（前文說過斯碌，放的其實是進程A的引用）。
操作系統(tǒng)把進程A分別加入這三個socket的等待隊列中
當任何一個socket收到數(shù)據(jù)后肛度，中斷程序?qū)酒疬M程傻唾。下圖展示了sock2接收到了數(shù)據(jù)的處理流程。
ps：recv和select的中斷回調(diào)可以設置成不同的內(nèi)容承耿。
sock2接收到了數(shù)據(jù)冠骄，中斷程序喚起進程A
所謂喚起進程，就是將進程從所有的等待隊列中移除加袋，加入到工作隊列里面兴想。如下圖所示碗降。
將進程A從所有等待隊列中移除，再加入到工作隊列里面
經(jīng)由這些步驟，當進程A被喚醒后凸丸，它知道至少有一個socket接收了數(shù)據(jù)怎棱。程序只需遍歷一遍socket列表九默，就可以得到就緒的socket蒸殿。
這種簡單方式行之有效，在幾乎所有操作系統(tǒng)都有對應的實現(xiàn)恬总。
但是簡單的方法往往有缺點前普，主要是：
其一，每次調(diào)用select都需要將進程加入到所有監(jiān)視socket的等待隊列壹堰，每次喚醒都需要從每個隊列中移除拭卿。這里涉及了兩次遍歷（遍歷進程A關心的所有socket，需要注意的是添加從等待隊列頭部添加贱纠，刪除通過回調(diào)直接實現(xiàn)峻厚，所以每個socket的等待隊列不用遍歷），而且每次都要將整個fds列表傳遞給內(nèi)核谆焊，有一定的開銷惠桃。正是因為遍歷操作開銷大，出于效率的考量辖试，才會規(guī)定select的最大監(jiān)視數(shù)量辜王，默認只能監(jiān)視1024個socket。
其二罐孝，進程被喚醒后呐馆，程序并不知道哪些socket收到數(shù)據(jù)，還需要遍歷一次（這一次遍歷是在應用層）莲兢。
那么汹来，有沒有減少遍歷的方法续膳？有沒有保存就緒socket的方法？這兩個問題便是epoll技術要解決的收班。
當程序調(diào)用select時坟岔，內(nèi)核會先遍歷一遍socket，如果有一個以上的socket接收緩沖區(qū)有數(shù)據(jù)闺阱，那么select直接返回炮车，不會阻塞舵变。這也是為什么select的返回值有可能大于1的原因之一酣溃。如果沒有socket有數(shù)據(jù)，進程才會阻塞
epoll是在select出現(xiàn)N多年后才被發(fā)明的赊豌，是select和poll的增強版本。epoll通過以下一些措施來改進效率绵咱。
措施一：功能分離
select低效的原因之一是將“維護等待隊列”和“阻塞進程”兩個步驟合二為一碘饼。如下圖所示，每次調(diào)用select都需要這兩步操作悲伶，然而大多數(shù)應用場景中艾恼，需要監(jiān)視的socket相對固定，并不需要每次都修改麸锉。epoll將這兩個操作分開钠绍，先用epoll_ctl維護等待隊列，再調(diào)用epoll_wait阻塞進程（解耦）花沉。顯而易見的柳爽，效率就能得到提升。
相比select碱屁，epoll拆分了功能
為方便理解后續(xù)的內(nèi)容磷脯，我們先復習下epoll的用法。如下的代碼中娩脾，先用epoll_create創(chuàng)建一個epoll對象epfd赵誓，再通過epoll_ctl將需要監(jiān)視的socket添加到epfd中，最后調(diào)用epoll_wait等待數(shù)據(jù)柿赊。
ints = socket(AF_INET, SOCK_STREAM,0);
bind(s, ...)
listen(s, ...)
intepfd = epoll_create(...);
epoll_ctl(epfd, ...);//將所有需要監(jiān)聽的socket添加到epfd中
while(1){
intn = epoll_wait(...)
for(接收到數(shù)據(jù)的socket){
//處理
? ? }
}
功能分離架曹，使得epoll有了優(yōu)化的可能。
措施二：就緒列表
select低效的另一個原因在于程序不知道哪些socket收到數(shù)據(jù)闹瞧，只能一個個遍歷绑雄。如果內(nèi)核維護一個“就緒列表”，引用收到數(shù)據(jù)的socket奥邮，就能避免遍歷万牺。如下圖所示罗珍，計算機共有三個socket，收到數(shù)據(jù)的sock2和sock3被rdlist（就緒列表）所引用脚粟。當進程被喚醒后覆旱，只要獲取rdlist的內(nèi)容，就能夠知道哪些socket收到數(shù)據(jù)核无。（這里引出了另一個問題：
一般認為如果在并發(fā)量低，socket都比較活躍的情況下团南，select效率更高噪沙，也就是說活躍socket數(shù)目與監(jiān)控的總的socket數(shù)目之比越大，select效率越高吐根，因為select反正都會遍歷所有的socket正歼，如果比例大，就沒有白白遍歷拷橘。加之于select本身實現(xiàn)比較簡單局义，導致總體現(xiàn)象比epoll好）
就緒列表示意圖
本節(jié)會以示例和圖表來講解epoll的原理和流程冗疮。
創(chuàng)建epoll對象
如下圖所示萄唇，當某個進程調(diào)用epoll_create方法時，內(nèi)核會創(chuàng)建一個eventpoll對象（也就是程序中epfd所代表的對象）术幔。eventpoll對象也是文件系統(tǒng)中的一員另萤，和socket一樣，它也會有等待隊列（有線程會等待其事件觸發(fā)特愿，比如調(diào)用epoll_wait的線程就會阻塞在其上）仲墨。
內(nèi)核創(chuàng)建eventpoll對象
創(chuàng)建一個代表該epoll的eventpoll對象是必須的，因為內(nèi)核要維護“就緒列表”等數(shù)據(jù)揍障，“就緒列表”可以作為eventpoll的成員目养。
維護監(jiān)視列表
創(chuàng)建epoll對象后，可以用epoll_ctl添加或刪除所要監(jiān)聽的socket毒嫡。以添加socket為例癌蚁，如下圖，如果通過epoll_ctl添加sock1兜畸、sock2和sock3的監(jiān)視努释，內(nèi)核會將eventpoll添加到這三個socket的等待隊列中。
添加所要監(jiān)聽的socket
當socket收到數(shù)據(jù)后咬摇，中斷程序會操作eventpoll對象伐蒂，而不是直接操作進程（也就是調(diào)用epoll的進程）。
接收數(shù)據(jù)
當socket收到數(shù)據(jù)后肛鹏，中斷程序會給eventpoll的“就緒列表”添加socket引用逸邦。如下圖展示的是sock2和sock3收到數(shù)據(jù)后恩沛，中斷程序讓rdlist引用這兩個socket。
給就緒列表添加引用
eventpoll對象相當于是socket和進程之間的中介缕减，socket的數(shù)據(jù)接收并不直接影響進程雷客，而是通過改變eventpoll的就緒列表來改變進程狀態(tài)。
當程序執(zhí)行到epoll_wait時桥狡，如果rdlist已經(jīng)引用了socket搅裙，那么epoll_wait直接返回，如果rdlist為空裹芝，阻塞進程部逮。
阻塞和喚醒進程
假設計算機中正在運行進程A和進程B，在某時刻進程A運行到了epoll_wait語句局雄。如下圖所示甥啄，內(nèi)核會將進程A放入eventpoll的等待隊列中存炮，阻塞進程炬搭。
epoll_wait阻塞進程
當socket接收到數(shù)據(jù)，中斷程序一方面修改rdlist穆桂，另一方面喚醒eventpoll等待隊列中的進程宫盔，進程A再次進入運行狀態(tài)（如下圖）。也因為rdlist的存在享完，進程A可以知道哪些socket發(fā)生了變化灼芭。
epoll喚醒進程
至此般又，相信讀者對epoll的本質(zhì)已經(jīng)有一定的了解彼绷。但我們還留有一個問題，eventpoll的數(shù)據(jù)結(jié)構(gòu)是什么樣子茴迁？
再留兩個問題寄悯，就緒隊列應該應使用什么數(shù)據(jù)結(jié)構(gòu)？eventpoll應使用什么數(shù)據(jù)結(jié)構(gòu)來管理通過epoll_ctl添加或刪除的socket堕义？
（——我是分割線猜旬，想好了才能往下看哦~）
如下圖所示，eventpoll包含了lock倦卖、mtx洒擦、wq（等待隊列）、rdlist等成員怕膛。rdlist和rbr是我們所關心的熟嫩。
epoll原理示意圖，圖片來源：《深入理解Nginx：模塊開發(fā)與架構(gòu)解析(第二版)》褐捻，陶輝
就緒列表的數(shù)據(jù)結(jié)構(gòu)
就緒列表引用著就緒的socket掸茅，所以它應能夠快速的插入數(shù)據(jù)洋侨。
程序可能隨時調(diào)用epoll_ctl添加監(jiān)視socket，也可能隨時刪除倦蚪。當刪除時希坚，若該socket已經(jīng)存放在就緒列表中，它也應該被移除陵且。（事實上裁僧，每個epoll_item既是紅黑樹節(jié)點，也是鏈表節(jié)點慕购，刪除紅黑樹節(jié)點聊疲，自然刪除了鏈表節(jié)點）
所以就緒列表應是一種能夠快速插入和刪除的數(shù)據(jù)結(jié)構(gòu)。雙向鏈表就是這樣一種數(shù)據(jù)結(jié)構(gòu)沪悲，epoll使用雙向鏈表來實現(xiàn)就緒隊列（對應上圖的rdllist）获洲。
索引結(jié)構(gòu)
既然epoll將“維護監(jiān)視隊列”和“進程阻塞”分離，也意味著需要有個數(shù)據(jù)結(jié)構(gòu)來保存監(jiān)視的socket殿如。至少要方便的添加和移除贡珊，還要便于搜索，以避免重復添加涉馁。紅黑樹是一種自平衡二叉查找樹门岔，搜索、插入和刪除時間復雜度都是O(log(N))烤送，效率較好寒随。epoll使用了紅黑樹作為索引結(jié)構(gòu)（對應上圖的rbr）。
ps：因為操作系統(tǒng)要兼顧多種功能帮坚，以及由更多需要保存的數(shù)據(jù)妻往，rdlist并非直接引用socket，而是通過epitem間接引用试和，紅黑樹的節(jié)點也是epitem對象讯泣。同樣，文件系統(tǒng)也并非直接引用著socket灰署。為方便理解判帮，本文中省略了一些間接結(jié)構(gòu)。
epoll在select和poll（poll和select基本一樣晦墙，有少量改進）的基礎引入了eventpoll作為中間層，使用了先進的數(shù)據(jù)結(jié)構(gòu)肴茄，是一種高效的多路復用技術晌畅。
再留一點作業(yè)！
下表是個很常見的表寡痰，描述了select抗楔、poll和epoll的區(qū)別棋凳。讀完本文，讀者能否解釋select和epoll的時間復雜度為什么是O(n)和O(1)连躏？
select剩岳、poll和epoll的區(qū)別。圖片來源《Linux高性能服務器編程》
