從事服務(wù)端開發(fā)，少不了要接觸網(wǎng)絡(luò)編程。Epoll 作為 Linux 下高性能網(wǎng)絡(luò)服務(wù)器的必備技術(shù)至關(guān)重要，Nginx、Redis、Skynet 和大部分游戲服務(wù)器都使用到這一多路復(fù)用技術(shù)。

Epoll 很重要，但是 Epoll 與 Select 的區(qū)別是什么呢?Epoll 高效的原因是什么?

網(wǎng)上雖然也有不少講解 Epoll 的文章，但要么是過于淺顯，或者陷入源碼解析，很少能有通俗易懂的。

筆者于是決定編寫此文，讓缺乏專業(yè)背景知識(shí)的讀者也能夠明白 Epoll 的原理。本文核心思想是：要讓讀者清晰明白 Epoll 為什么性能好。

文章會(huì)從網(wǎng)卡接收數(shù)據(jù)的流程講起，串聯(lián)起 CPU 中斷、操作系統(tǒng)進(jìn)程調(diào)度等知識(shí);再一步步分析阻塞接收數(shù)據(jù)、Select 到 Epoll 的進(jìn)化過程;最后探究 Epoll 的實(shí)現(xiàn)細(xì)節(jié)。

從網(wǎng)卡接收數(shù)據(jù)說起

下邊是一個(gè)典型的計(jì)算機(jī)結(jié)構(gòu)圖，計(jì)算機(jī)由 CPU、存儲(chǔ)器(內(nèi)存)與網(wǎng)絡(luò)接口等部件組成，了解 Epoll 本質(zhì)的第一步，要從硬件的角度看計(jì)算機(jī)怎樣接收網(wǎng)絡(luò)數(shù)據(jù)。

 

計(jì)算機(jī)結(jié)構(gòu)圖(圖片來源：Linux 內(nèi)核完全注釋之微型計(jì)算機(jī)組成結(jié)構(gòu))

下圖展示了網(wǎng)卡接收數(shù)據(jù)的過程：

• 在 1 階段，網(wǎng)卡收到網(wǎng)線傳來的數(shù)據(jù)。
• 經(jīng)過 2 階段的硬件電路的傳輸。
• 最終 3 階段將數(shù)據(jù)寫入到內(nèi)存中的某個(gè)地址上。

這個(gè)過程涉及到 DMA 傳輸、IO 通路選擇等硬件有關(guān)的知識(shí)，但我們只需知道：網(wǎng)卡會(huì)把接收到的數(shù)據(jù)寫入內(nèi)存。

 

網(wǎng)卡接收數(shù)據(jù)的過程

通過硬件傳輸，網(wǎng)卡接收的數(shù)據(jù)存放到內(nèi)存中，操作系統(tǒng)就可以去讀取它們。

如何知道接收了數(shù)據(jù)?

了解 Epoll 本質(zhì)的第二步，要從 CPU 的角度來看數(shù)據(jù)接收。理解這個(gè)問題，要先了解一個(gè)概念：中斷。

計(jì)算機(jī)執(zhí)行程序時(shí)，會(huì)有優(yōu)先級(jí)的需求。比如，當(dāng)計(jì)算機(jī)收到斷電信號(hào)時(shí)，它應(yīng)立即去保存數(shù)據(jù)，保存數(shù)據(jù)的程序具有較高的優(yōu)先級(jí)(電容可以保存少許電量，供 CPU 運(yùn)行很短的一小段時(shí)間)。

一般而言，由硬件產(chǎn)生的信號(hào)需要 CPU 立馬做出回應(yīng)，不然數(shù)據(jù)可能就丟失了，所以它的優(yōu)先級(jí)很高。

CPU 理應(yīng)中斷掉正在執(zhí)行的程序，去做出響應(yīng);當(dāng) CPU 完成對(duì)硬件的響應(yīng)后，再重新執(zhí)行用戶程序。

中斷的過程如下圖，它和函數(shù)調(diào)用差不多，只不過函數(shù)調(diào)用是事先定好位置，而中斷的位置由“信號(hào)”決定。

 

中斷程序調(diào)用

以鍵盤為例，當(dāng)用戶按下鍵盤某個(gè)按鍵時(shí)，鍵盤會(huì)給 CPU 的中斷引腳發(fā)出一個(gè)高電平，CPU 能夠捕獲這個(gè)信號(hào)，然后執(zhí)行鍵盤中斷程序。

下圖展示了各種硬件通過中斷與 CPU 交互的過程：

 

CPU 中斷(圖片來源：net.pku.edu.cn)

現(xiàn)在可以回答“如何知道接收了數(shù)據(jù)?”這個(gè)問題了：當(dāng)網(wǎng)卡把數(shù)據(jù)寫入到內(nèi)存后，網(wǎng)卡向 CPU 發(fā)出一個(gè)中斷信號(hào)，操作系統(tǒng)便能得知有新數(shù)據(jù)到來，再通過網(wǎng)卡中斷程序去處理數(shù)據(jù)。

進(jìn)程阻塞為什么不占用 CPU 資源?

了解 Epoll 本質(zhì)的第三步，要從操作系統(tǒng)進(jìn)程調(diào)度的角度來看數(shù)據(jù)接收。阻塞是進(jìn)程調(diào)度的關(guān)鍵一環(huán)，指的是進(jìn)程在等待某事件(如接收到網(wǎng)絡(luò)數(shù)據(jù))發(fā)生之前的等待狀態(tài)，Recv、Select 和 Epoll 都是阻塞方法。

下邊分析一下進(jìn)程阻塞為什么不占用 CPU 資源?為簡單起見，我們從普通的 Recv 接收開始分析，先看看下面代碼：

//創(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(...) 

這是一段最基礎(chǔ)的網(wǎng)絡(luò)編程代碼，先新建 Socket 對(duì)象，依次調(diào)用 Bind、Listen 與 Accept，最后調(diào)用 Recv 接收數(shù)據(jù)。

Recv 是個(gè)阻塞方法，當(dāng)程序運(yùn)行到 Recv 時(shí)，它會(huì)一直等待，直到接收到數(shù)據(jù)才往下執(zhí)行。那么阻塞的原理是什么?

工作隊(duì)列

操作系統(tǒng)為了支持多任務(wù)，實(shí)現(xiàn)了進(jìn)程調(diào)度的功能，會(huì)把進(jìn)程分為“運(yùn)行”和“等待”等幾種狀態(tài)。

運(yùn)行狀態(tài)是進(jìn)程獲得 CPU 使用權(quán)，正在執(zhí)行代碼的狀態(tài);等待狀態(tài)是阻塞狀態(tài)，比如上述程序運(yùn)行到 Recv 時(shí)，程序會(huì)從運(yùn)行狀態(tài)變?yōu)榈却隣顟B(tài)，接收到數(shù)據(jù)后又變回運(yùn)行狀態(tài)。

操作系統(tǒng)會(huì)分時(shí)執(zhí)行各個(gè)運(yùn)行狀態(tài)的進(jìn)程，由于速度很快，看上去就像是同時(shí)執(zhí)行多個(gè)任務(wù)。

下圖的計(jì)算機(jī)中運(yùn)行著 A、B 與 C 三個(gè)進(jìn)程，其中進(jìn)程 A 執(zhí)行著上述基礎(chǔ)網(wǎng)絡(luò)程序，一開始，這 3 個(gè)進(jìn)程都被操作系統(tǒng)的工作隊(duì)列所引用，處于運(yùn)行狀態(tài)，會(huì)分時(shí)執(zhí)行。

 

工作隊(duì)列中有 A、B 和 C 三個(gè)進(jìn)程

等待隊(duì)列

當(dāng)進(jìn)程 A 執(zhí)行到創(chuàng)建 Socket 的語句時(shí)，操作系統(tǒng)會(huì)創(chuàng)建一個(gè)由文件系統(tǒng)管理的 Socket 對(duì)象(如下圖)。

 

創(chuàng)建 Socket

這個(gè) Socket 對(duì)象包含了發(fā)送緩沖區(qū)、接收緩沖區(qū)與等待隊(duì)列等成員。等待隊(duì)列是個(gè)非常重要的結(jié)構(gòu)，它指向所有需要等待該 Socket 事件的進(jìn)程。

當(dāng)程序執(zhí)行到 Recv 時(shí)，操作系統(tǒng)會(huì)將進(jìn)程 A 從工作隊(duì)列移動(dòng)到該 Socket 的等待隊(duì)列中(如下圖)。

 

Socket 的等待隊(duì)列

由于工作隊(duì)列只剩下了進(jìn)程 B 和 C，依據(jù)進(jìn)程調(diào)度，CPU 會(huì)輪流執(zhí)行這兩個(gè)進(jìn)程的程序，不會(huì)執(zhí)行進(jìn)程 A 的程序。所以進(jìn)程 A 被阻塞，不會(huì)往下執(zhí)行代碼，也不會(huì)占用 CPU 資源。

注：操作系統(tǒng)添加等待隊(duì)列只是添加了對(duì)這個(gè)“等待中”進(jìn)程的引用，以便在接收到數(shù)據(jù)時(shí)獲取進(jìn)程對(duì)象、將其喚醒，而非直接將進(jìn)程管理納入自己之下。上圖為了方便說明，直接將進(jìn)程掛到等待隊(duì)列之下。

喚醒進(jìn)程

當(dāng) Socket 接收到數(shù)據(jù)后，操作系統(tǒng)將該 Socket 等待隊(duì)列上的進(jìn)程重新放回到工作隊(duì)列，該進(jìn)程變成運(yùn)行狀態(tài)，繼續(xù)執(zhí)行代碼。

同時(shí)由于 Socket 的接收緩沖區(qū)已經(jīng)有了數(shù)據(jù)，Recv 可以返回接收到的數(shù)據(jù)。

內(nèi)核接收網(wǎng)絡(luò)數(shù)據(jù)全過程

這一步，貫穿網(wǎng)卡、中斷與進(jìn)程調(diào)度的知識(shí)，敘述阻塞 Recv 下，內(nèi)核接收數(shù)據(jù)的全過程。

 

內(nèi)核接收數(shù)據(jù)全過程

如上圖所示，進(jìn)程在 Recv 阻塞期間：

• 計(jì)算機(jī)收到了對(duì)端傳送的數(shù)據(jù)(步驟 ①)
• 數(shù)據(jù)經(jīng)由網(wǎng)卡傳送到內(nèi)存(步驟 ②)
• 然后網(wǎng)卡通過中斷信號(hào)通知 CPU 有數(shù)據(jù)到達(dá)，CPU 執(zhí)行中斷程序(步驟 ③)

此處的中斷程序主要有兩項(xiàng)功能，先將網(wǎng)絡(luò)數(shù)據(jù)寫入到對(duì)應(yīng) Socket 的接收緩沖區(qū)里面(步驟 ④)，再喚醒進(jìn)程 A(步驟 ⑤)，重新將進(jìn)程 A 放入工作隊(duì)列中。

喚醒進(jìn)程的過程如下圖所示：

 

喚醒進(jìn)程

以上是內(nèi)核接收數(shù)據(jù)全過程，這里我們可能會(huì)思考兩個(gè)問題：

• 操作系統(tǒng)如何知道網(wǎng)絡(luò)數(shù)據(jù)對(duì)應(yīng)于哪個(gè) Socket?
• 如何同時(shí)監(jiān)視多個(gè) Socket 的數(shù)據(jù)?

第一個(gè)問題：因?yàn)橐粋€(gè) Socket 對(duì)應(yīng)著一個(gè)端口號(hào)，而網(wǎng)絡(luò)數(shù)據(jù)包中包含了 IP 和端口的信息，內(nèi)核可以通過端口號(hào)找到對(duì)應(yīng)的 Socket。

當(dāng)然，為了提高處理速度，操作系統(tǒng)會(huì)維護(hù)端口號(hào)到 Socket 的索引結(jié)構(gòu)，以快速讀取。

第二個(gè)問題是多路復(fù)用的重中之重，也正是本文后半部分的重點(diǎn)。

同時(shí)監(jiān)視多個(gè) Socket 的簡單方法

服務(wù)端需要管理多個(gè)客戶端連接，而 Recv 只能監(jiān)視單個(gè) Socket，這種矛盾下，人們開始尋找監(jiān)視多個(gè) Socket 的方法。Epoll 的要義就是高效地監(jiān)視多個(gè) Socket。

從歷史發(fā)展角度看，必然先出現(xiàn)一種不太高效的方法，人們?cè)偌右愿倪M(jìn)，正如 Select 之于 Epoll。先理解不太高效的 Select，才能夠更好地理解 Epoll 的本質(zhì)。

假如能夠預(yù)先傳入一個(gè) Socket 列表，如果列表中的 Socket 都沒有數(shù)據(jù)，掛起進(jìn)程，直到有一個(gè) Socket 收到數(shù)據(jù)，喚醒進(jìn)程。這種方法很直接，也是 Select 的設(shè)計(jì)思想。

為方便理解，我們先復(fù)習(xí) Select 的用法。在下邊的代碼中，先準(zhǔn)備一個(gè)數(shù)組 FDS，讓 FDS 存放著所有需要監(jiān)視的 Socket。

然后調(diào)用 Select，如果 FDS 中的所有 Socket 都沒有數(shù)據(jù)，Select 會(huì)阻塞，直到有一個(gè) Socket 接收到數(shù)據(jù)，Select 返回，喚醒進(jìn)程。

用戶可以遍歷 FDS，通過 FD_ISSET 判斷具體哪個(gè) 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ù)處理 
        } 
    } 
} 

Select 的流程

Select 的實(shí)現(xiàn)思路很直接，假如程序同時(shí)監(jiān)視如下圖的 Sock1、Sock2 和 Sock3 三個(gè) Socket，那么在調(diào)用 Select 之后，操作系統(tǒng)把進(jìn)程 A 分別加入這三個(gè) Socket 的等待隊(duì)列中。

 

操作系統(tǒng)把進(jìn)程 A 分別加入這三個(gè) Socket 的等待隊(duì)列中

當(dāng)任何一個(gè) Socket 收到數(shù)據(jù)后，中斷程序?qū)酒疬M(jìn)程。下圖展示了 Sock2 接收到了數(shù)據(jù)的處理流程：

 

Sock2 接收到了數(shù)據(jù)，中斷程序喚起進(jìn)程 A

注：Recv 和 Select 的中斷回調(diào)可以設(shè)置成不同的內(nèi)容。

所謂喚起進(jìn)程，就是將進(jìn)程從所有的等待隊(duì)列中移除，加入到工作隊(duì)列里面，如下圖所示：

 

將進(jìn)程 A 從所有等待隊(duì)列中移除，再加入到工作隊(duì)列里面

經(jīng)由這些步驟，當(dāng)進(jìn)程 A 被喚醒后，它知道至少有一個(gè) Socket 接收了數(shù)據(jù)。程序只需遍歷一遍 Socket 列表，就可以得到就緒的 Socket。

這種簡單方式行之有效，在幾乎所有操作系統(tǒng)都有對(duì)應(yīng)的實(shí)現(xiàn)。但是簡單的方法往往有缺點(diǎn)，主要是：

• 每次調(diào)用 Select 都需要將進(jìn)程加入到所有監(jiān)視 Socket 的等待隊(duì)列，每次喚醒都需要從每個(gè)隊(duì)列中移除。這里涉及了兩次遍歷，而且每次都要將整個(gè) FDS 列表傳遞給內(nèi)核，有一定的開銷。

正是因?yàn)楸闅v操作開銷大，出于效率的考量，才會(huì)規(guī)定 Select 的最大監(jiān)視數(shù)量，默認(rèn)只能監(jiān)視 1024 個(gè) Socket。

• 進(jìn)程被喚醒后，程序并不知道哪些 Socket 收到數(shù)據(jù)，還需要遍歷一次。

那么，有沒有減少遍歷的方法?有沒有保存就緒 Socket 的方法?這兩個(gè)問題便是 Epoll 技術(shù)要解決的。

補(bǔ)充說明：本節(jié)只解釋了 Select 的一種情形。當(dāng)程序調(diào)用 Select 時(shí)，內(nèi)核會(huì)先遍歷一遍 Socket，如果有一個(gè)以上的 Socket 接收緩沖區(qū)有數(shù)據(jù)，那么 Select 直接返回，不會(huì)阻塞。

這也是為什么 Select 的返回值有可能大于 1 的原因之一。如果沒有 Socket 有數(shù)據(jù)，進(jìn)程才會(huì)阻塞。

Epoll 的設(shè)計(jì)思路

Epoll 是在 Select 出現(xiàn) N 多年后才被發(fā)明的，是 Select 和 Poll(Poll 和 Select 基本一樣，有少量改進(jìn))的增強(qiáng)版本。Epoll 通過以下一些措施來改進(jìn)效率：

措施一：功能分離

Select 低效的原因之一是將“維護(hù)等待隊(duì)列”和“阻塞進(jìn)程”兩個(gè)步驟合二為一。

 

相比 Select，Epoll 拆分了功能

如上圖所示，每次調(diào)用 Select 都需要這兩步操作，然而大多數(shù)應(yīng)用場景中，需要監(jiān)視的 Socket 相對(duì)固定，并不需要每次都修改。

Epoll 將這兩個(gè)操作分開，先用 epoll_ctl 維護(hù)等待隊(duì)列，再調(diào)用 epoll_wait 阻塞進(jìn)程。顯而易見地，效率就能得到提升。

為方便理解后續(xù)的內(nèi)容，我們先了解一下 Epoll 的用法。如下的代碼中，先用 epoll_create 創(chuàng)建一個(gè) Epoll 對(duì)象 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){ 
        //處理 
    } 
} 

功能分離，使得 Epoll 有了優(yōu)化的可能。

措施二：就緒列表

Select 低效的另一個(gè)原因在于程序不知道哪些 Socket 收到數(shù)據(jù)，只能一個(gè)個(gè)遍歷。如果內(nèi)核維護(hù)一個(gè)“就緒列表”，引用收到數(shù)據(jù)的 Socket，就能避免遍歷。

 

就緒列表示意圖

如上圖所示，計(jì)算機(jī)共有三個(gè) Socket，收到數(shù)據(jù)的 Sock2 和 Sock3 被就緒列表 Rdlist 所引用。

當(dāng)進(jìn)程被喚醒后，只要獲取 Rdlist 的內(nèi)容，就能夠知道哪些 Socket 收到數(shù)據(jù)。

Epoll 的原理與工作流程

本節(jié)會(huì)以示例和圖表來講解 Epoll 的原理和工作流程。

創(chuàng)建 Epoll 對(duì)象

如下圖所示，當(dāng)某個(gè)進(jìn)程調(diào)用 epoll_create 方法時(shí)，內(nèi)核會(huì)創(chuàng)建一個(gè) eventpoll 對(duì)象(也就是程序中 Epfd 所代表的對(duì)象)。

 

內(nèi)核創(chuàng)建 eventpoll 對(duì)象

eventpoll 對(duì)象也是文件系統(tǒng)中的一員，和 Socket 一樣，它也會(huì)有等待隊(duì)列。

創(chuàng)建一個(gè)代表該 Epoll 的 eventpoll 對(duì)象是必須的，因?yàn)閮?nèi)核要維護(hù)“就緒列表”等數(shù)據(jù)，“就緒列表”可以作為 eventpoll 的成員。

維護(hù)監(jiān)視列表

創(chuàng)建 Epoll 對(duì)象后，可以用 epoll_ctl 添加或刪除所要監(jiān)聽的 Socket。以添加 Socket 為例。

 

添加所要監(jiān)聽的 Socket

如上圖，如果通過 epoll_ctl 添加 Sock1、Sock2 和 Sock3 的監(jiān)視，內(nèi)核會(huì)將 eventpoll 添加到這三個(gè) Socket 的等待隊(duì)列中。

當(dāng) Socket 收到數(shù)據(jù)后，中斷程序會(huì)操作 eventpoll 對(duì)象，而不是直接操作進(jìn)程。

接收數(shù)據(jù)

當(dāng) Socket 收到數(shù)據(jù)后，中斷程序會(huì)給 eventpoll 的“就緒列表”添加 Socket 引用。

 

給就緒列表添加引用

如上圖展示的是 Sock2 和 Sock3 收到數(shù)據(jù)后，中斷程序讓 Rdlist 引用這兩個(gè) Socket。

eventpoll 對(duì)象相當(dāng)于 Socket 和進(jìn)程之間的中介，Socket 的數(shù)據(jù)接收并不直接影響進(jìn)程，而是通過改變 eventpoll 的就緒列表來改變進(jìn)程狀態(tài)。

當(dāng)程序執(zhí)行到 epoll_wait 時(shí)，如果 Rdlist 已經(jīng)引用了 Socket，那么 epoll_wait 直接返回，如果 Rdlist 為空，阻塞進(jìn)程。

阻塞和喚醒進(jìn)程

假設(shè)計(jì)算機(jī)中正在運(yùn)行進(jìn)程 A 和進(jìn)程 B，在某時(shí)刻進(jìn)程 A 運(yùn)行到了 epoll_wait 語句。

 

epoll_wait 阻塞進(jìn)程

如上圖所示，內(nèi)核會(huì)將進(jìn)程 A 放入 eventpoll 的等待隊(duì)列中，阻塞進(jìn)程。

當(dāng) Socket 接收到數(shù)據(jù)，中斷程序一方面修改 Rdlist，另一方面喚醒 eventpoll 等待隊(duì)列中的進(jìn)程，進(jìn)程 A 再次進(jìn)入運(yùn)行狀態(tài)(如下圖)。

 

Epoll 喚醒進(jìn)程

也因?yàn)?Rdlist 的存在，進(jìn)程 A 可以知道哪些 Socket 發(fā)生了變化。

Epoll 的實(shí)現(xiàn)細(xì)節(jié)

至此，相信讀者對(duì) Epoll 的本質(zhì)已經(jīng)有一定的了解。但我們還需要知道 eventpoll 的數(shù)據(jù)結(jié)構(gòu)是什么樣子?

此外，就緒隊(duì)列應(yīng)該使用什么數(shù)據(jù)結(jié)構(gòu)?eventpoll 應(yīng)使用什么數(shù)據(jù)結(jié)構(gòu)來管理通過 epoll_ctl 添加或刪除的 Socket?

 

Epoll 原理示意圖，圖片來源：《深入理解 Nginx：模塊開發(fā)與架構(gòu)解析(第二版)》，陶輝

如上圖所示，eventpoll 包含了 Lock、MTX、WQ(等待隊(duì)列)與 Rdlist 等成員，其中 Rdlist 和 RBR 是我們所關(guān)心的。

就緒列表的數(shù)據(jù)結(jié)構(gòu)

就緒列表引用著就緒的 Socket，所以它應(yīng)能夠快速的插入數(shù)據(jù)。程序可能隨時(shí)調(diào)用 epoll_ctl 添加監(jiān)視 Socket，也可能隨時(shí)刪除。

當(dāng)刪除時(shí)，若該 Socket 已經(jīng)存放在就緒列表中，它也應(yīng)該被移除。所以就緒列表應(yīng)是一種能夠快速插入和刪除的數(shù)據(jù)結(jié)構(gòu)。

雙向鏈表就是這樣一種數(shù)據(jù)結(jié)構(gòu)，Epoll 使用雙向鏈表來實(shí)現(xiàn)就緒隊(duì)列(對(duì)應(yīng)上圖的 Rdlist)。

索引結(jié)構(gòu)

既然 Epoll 將“維護(hù)監(jiān)視隊(duì)列”和“進(jìn)程阻塞”分離，也意味著需要有個(gè)數(shù)據(jù)結(jié)構(gòu)來保存監(jiān)視的 Socket，至少要方便地添加和移除，還要便于搜索，以避免重復(fù)添加。

紅黑樹是一種自平衡二叉查找樹，搜索、插入和刪除時(shí)間復(fù)雜度都是 O(log(N))，效率較好，Epoll 使用了紅黑樹作為索引結(jié)構(gòu)(對(duì)應(yīng)上圖的 RBR)。

注：因?yàn)椴僮飨到y(tǒng)要兼顧多種功能，以及有更多需要保存的數(shù)據(jù)，Rdlist 并非直接引用 Socket，而是通過 Epitem 間接引用，紅黑樹的節(jié)點(diǎn)也是 Epitem 對(duì)象。

同樣，文件系統(tǒng)也并非直接引用著 Socket。為方便理解，本文中省略了一些間接結(jié)構(gòu)。

總結(jié)

Epoll 在 Select 和 Poll 的基礎(chǔ)上引入了 eventpoll 作為中間層，使用了先進(jìn)的數(shù)據(jù)結(jié)構(gòu)，是一種高效的多路復(fù)用技術(shù)。

這里也以表格形式簡單對(duì)比一下 Select、Poll 與 Epoll，結(jié)束此文。希望讀者能有所收獲。

 

圖片來源《Linux 高性能服務(wù)器編程》

作者：羅培羽

簡介：正在創(chuàng)作好玩游戲的程序員，作為游戲行業(yè)從業(yè)人員，曾參與《卡布西游》、《卡布仙蹤》、《卡布魔鏡》、《坦克射擊》與《海陸大戰(zhàn)》等多個(gè)項(xiàng)目研發(fā)工作;作為獨(dú)立游戲開發(fā)者，主導(dǎo)《仙劍 5 前傳之心愿》與《蝕夢(mèng)》等項(xiàng)目研發(fā)，擁有豐富的實(shí)戰(zhàn)經(jīng)驗(yàn)。自 2009 年發(fā)布第一部視頻教程《教你用 VB 制作 RPG 游戲》以來，先后出版專業(yè)書籍《手把手教你用 C# 制作 RPG 游戲》與《Unity3D 網(wǎng)絡(luò)游戲?qū)崙?zhàn)》。目前關(guān)注手機(jī)游戲與 AI 技術(shù)等領(lǐng)域，并以第三方視角記錄普通開發(fā)者的心路歷程。