參考鏈接：
https://zhuanlan.zhihu.com/p/63179839
https://zhuanlan.zhihu.com/p/64138532
https://zhuanlan.zhihu.com/p/64746509
在講解之前拷况，我們需要先知道計算機(jī)是如何接受網(wǎng)絡(luò)數(shù)據(jù)的步绸。簡單來講质蕉，就是當(dāng)網(wǎng)絡(luò)數(shù)據(jù)到達(dá)網(wǎng)卡的時候，網(wǎng)卡會通過中斷控制器向CPU發(fā)送中斷信號，CPU接受到中斷信號的時候會根據(jù)接受到的中斷向量號調(diào)用提前在中段描述符表中注冊好的中斷處理程序，中斷處理程序會保存當(dāng)前正在執(zhí)行的程序的上下文，然后將網(wǎng)卡的中的數(shù)據(jù)復(fù)制到內(nèi)核緩沖區(qū)葵萎，在等待空閑的時間將內(nèi)核緩沖區(qū)的數(shù)據(jù)復(fù)制到用戶緩沖區(qū)中供用戶進(jìn)程處理。
而我們知道唱凯，對于服務(wù)端建立socket的過程如下：
//創(chuàng)建socket
int s = socket(AF_INET, SOCK_STREAM, 0);
//綁定
bind(s, ...)
//監(jiān)聽
listen(s, ...)
//接受客戶端連接
int c = accept(s, ...)
//接收客戶端數(shù)據(jù)
recv(c, ...);
//將數(shù)據(jù)打印出來
printf(...)
當(dāng)和客戶端成功完成3次握手后羡忘，便會調(diào)用recv阻塞等待接收客戶端發(fā)送過來的數(shù)據(jù)。
實(shí)際上波丰，當(dāng)某個進(jìn)程A執(zhí)行到創(chuàng)建socket語句的時候， 操作系統(tǒng)就會創(chuàng)建一個由文件系統(tǒng)管理的socket對象舶得。socket包含了發(fā)送緩沖區(qū)掰烟、接收緩沖區(qū)、等待隊列等沐批。其中發(fā)送緩沖區(qū)和接收緩沖區(qū)就是我們TCP流量控制中用到的滑動窗口纫骑，而TCP本身就是全雙工的，既可以發(fā)送數(shù)據(jù)九孩，又可以接收數(shù)據(jù)先馆，因此會有2個緩沖區(qū)。而等待隊列指向的是所有等待該socket事件的進(jìn)程躺彬。
當(dāng)程序執(zhí)行到recv的時候煤墙，操作系統(tǒng)會將進(jìn)程A從工作隊列移動到該socket的等待隊列中（傳個引用），進(jìn)程B宪拥、C繼續(xù)調(diào)度執(zhí)行仿野，A進(jìn)程被阻塞
當(dāng)socket接收到數(shù)據(jù)，操作系統(tǒng)便會將在該socket的等待隊列上的進(jìn)程重新放回工作隊列中她君，由內(nèi)核調(diào)度器繼續(xù)調(diào)度執(zhí)行脚作，該進(jìn)程變成運(yùn)行狀態(tài)，繼續(xù)執(zhí)行代碼，由于socket的接收緩沖區(qū)已有了數(shù)據(jù)球涛，recv便可接收返回的數(shù)據(jù)劣针。
那么當(dāng)數(shù)據(jù)到來的時候，操作系統(tǒng)如何知道是哪一個socket呢亿扁？一個進(jìn)程又是如何監(jiān)聽多個socket的數(shù)據(jù)呢捺典？
因?yàn)橐粭lTCP連接對應(yīng)一個四元組，TCP首部的信息中含有接收方的端口號信息魏烫，而一個socket對應(yīng)著一個端口號辣苏，因此可以根據(jù)TCP頭部的信息找到對應(yīng)的socket，將數(shù)據(jù)復(fù)制到socket的接收緩沖區(qū)中哄褒；而進(jìn)程正是通過IO多路復(fù)用的形式來監(jiān)聽多個socket（select和epoll）稀蟋。
我們先來看一下select是怎么做的：
如下的代碼中，準(zhǔn)備一個數(shù)組fds呐赡，存放需要監(jiān)視的所有socket退客，然后調(diào)用select，如果fds中所有的socket都沒有數(shù)據(jù)链嘀，select會阻塞萌狂，直到有一個socket收到數(shù)據(jù)，select返回怀泊，喚醒進(jìn)程茫藏，用戶可以遍歷fds，通過FD_ISSET判斷哪個socket收到了數(shù)據(jù)霹琼，然后做出處理务傲。
int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...)
listen(s, ...)
int fds[] = 存放需要監(jiān)聽的socket
while(1){
int n = select(..., fds, ...)
for(int i=0; i < fds.count; i++){
if(FD_ISSET(fds[i], ...)){
//fds[i]的數(shù)據(jù)處理
}
}
}
加入進(jìn)程A同時監(jiān)視如下圖的sock1、sock2枣申、sock3售葡，調(diào)用select后操作系統(tǒng)會將進(jìn)程A分別加入這3個socket的等待隊列中。
當(dāng)任何一個socket收到數(shù)據(jù)后忠藤，中斷處理程序喚醒線程挟伙，加入工作隊列
然后A繼續(xù)執(zhí)行，只需遍歷一遍socket列表模孩，就可以得到就緒的socket尖阔。
但是簡單的方法往往有缺點(diǎn)，主要是：
其一榨咐，每次調(diào)用select都需要將進(jìn)程加入到所有監(jiān)視socket的等待隊列诺祸，每次喚醒都需要從每個隊列中移除。這里涉及了兩次遍歷祭芦，而且每次都要將整個fds列表傳遞給內(nèi)核筷笨，有一定的開銷。正是因?yàn)楸闅v操作開銷大，出于效率的考量胃夏，才會規(guī)定select的最大監(jiān)視數(shù)量轴或，默認(rèn)只能監(jiān)視1024個socket。
其二仰禀，進(jìn)程被喚醒后照雁，程序并不知道哪些socket收到數(shù)據(jù)，還需要遍歷一次答恶。
那么饺蚊，有沒有減少遍歷的方法？有沒有保存就緒socket的方法悬嗓？這兩個問題便是epoll技術(shù)要解決的污呼。
補(bǔ)充說明： 本節(jié)只解釋了select的一種情形。當(dāng)程序調(diào)用select時包竹，內(nèi)核會先遍歷一遍socket燕酷，如果有一個以上的socket接收緩沖區(qū)有數(shù)據(jù)，那么select直接返回周瞎，不會阻塞苗缩。這也是為什么select的返回值有可能大于1的原因之一。如果沒有socket有數(shù)據(jù)声诸，進(jìn)程才會阻塞酱讶。
epoll解決了上述select低效的問題：
epoll先用epoll_create創(chuàng)建一個epoll對象epfd，再通過epoll_ctl將需要監(jiān)視的socket添加到epfd中彼乌，最后調(diào)用epoll_wait等待數(shù)據(jù)泻肯。
int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...)
listen(s, ...)
int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //將所有需要監(jiān)聽的socket添加到epfd中
while(1){
int n = epoll_wait(...)
for(接收到數(shù)據(jù)的socket){
//處理
}
}
內(nèi)核維護(hù)一個“就緒鏈表”，引用收到數(shù)據(jù)的socket囤攀，防止對socket的遍歷软免，如下所示宫纬，收到數(shù)據(jù)的sock2和sock3會被rdlist（就緒鏈表所引用）焚挠，進(jìn)程被喚醒后，只需要獲取rdlist的內(nèi)容就能夠知道哪些socket收到了數(shù)據(jù)漓骚。
epoll原理和流程:
如下圖所示蝌衔，當(dāng)某個進(jìn)程調(diào)用epoll_create方法時，內(nèi)核會創(chuàng)建一個eventpoll對象（也就是程序中epfd所代表的對象）蝌蹂。eventpoll對象也是文件系統(tǒng)中的一員噩斟，和socket一樣，它也會有等待隊列孤个。
創(chuàng)建eventpoll對象后剃允，可以通過epoll_ctl添加或者刪除需要監(jiān)聽的socket。以添加socket為例，如下圖斥废，如果通過epoll_ctl添加sock1椒楣、sock2和sock3的監(jiān)視，內(nèi)核會將eventpoll添加到這三個socket的等待隊列中牡肉。
當(dāng)socket收到數(shù)據(jù)后捧灰，中斷程序會操作eventpoll對象，而不是直接操作進(jìn)程统锤。
當(dāng)socket收到數(shù)據(jù)后毛俏，中斷程序會給eventpoll的“就緒列表”添加socket引用。如下圖展示的是sock2和sock3收到數(shù)據(jù)后饲窿，中斷程序讓rdlist引用這兩個socket煌寇。
所以eventpoll相當(dāng)于一個中間層，位于socket和進(jìn)程之間免绿，socket的數(shù)據(jù)通過改變eventpoll的就序列表來改變進(jìn)程狀態(tài)唧席。
假設(shè)計算機(jī)中正在運(yùn)行進(jìn)程A和進(jìn)程B，在某時刻進(jìn)程A運(yùn)行到了epoll_wait語句嘲驾。如下圖所示淌哟，內(nèi)核會將進(jìn)程A放入eventpoll的等待隊列中，阻塞進(jìn)程辽故。
當(dāng)socket接收到數(shù)據(jù)徒仓，中斷程序一方面修改rdlist，另一方面喚醒eventpoll等待隊列中的進(jìn)程誊垢，進(jìn)程A再次進(jìn)入運(yùn)行狀態(tài)（如下圖）掉弛。也因?yàn)閞dlist的存在，進(jìn)程A可以知道哪些socket發(fā)生了變化喂走。
就緒列表的數(shù)據(jù)結(jié)構(gòu)
就緒列表引用著就緒的socket殃饿，所以它應(yīng)能夠快速的插入數(shù)據(jù)。
程序可能隨時調(diào)用epoll_ctl添加監(jiān)視socket芋肠，也可能隨時刪除乎芳。當(dāng)刪除時，若該socket已經(jīng)存放在就緒列表中帖池，它也應(yīng)該被移除坛吁。
所以就緒列表應(yīng)是一種能夠快速插入和刪除的數(shù)據(jù)結(jié)構(gòu)散吵。雙向鏈表就是這樣一種數(shù)據(jù)結(jié)構(gòu)，epoll使用雙向鏈表來實(shí)現(xiàn)就緒隊列（對應(yīng)上圖的rdllist）。
索引結(jié)構(gòu)
既然epoll將“維護(hù)監(jiān)視隊列”和“進(jìn)程阻塞”分離箕昭，也意味著需要有個數(shù)據(jù)結(jié)構(gòu)來保存監(jiān)視的socket蹋盆。至少要方便的添加和移除况脆，還要便于搜索柒爵，以避免重復(fù)添加友扰。紅黑樹是一種自平衡二叉查找樹，搜索庶柿、插入和刪除時間復(fù)雜度都是O(log(N))焕檬，效率較好。epoll使用了紅黑樹作為索引結(jié)構(gòu)（對應(yīng)上圖的rbr）澳泵。
