如果這篇文章說不清epoll的本質，那就過來掐死我吧！ （3）
epoll是開發linux高性能伺服器的必備技術至，epoll本質，是服務端程序員的必須掌握的知識。
文/羅培羽
上篇回顧
四、內核接收網路數據全過程
五、同時監視多個socket的簡單方法
六、epoll的設計思路
七、epoll的原理和流程
本節會以示例和圖表來講解epoll的原理和流程。
創建epoll對象
如下圖所示，當某個進程調用epoll_create方法時，內核會創建一個eventpoll對象（也就是程序中epfd所代表的對象）。eventpoll對象也是文件系統中的一員，和socket一樣，它也會有等待隊列。
創建一個代表該epoll的eventpoll對象是必須的，因為內核要維護「就緒列表」等數據，「就緒列表」可以作為eventpoll的成員。
維護監視列表
創建epoll對象後，可以用epoll_ctl添加或刪除所要監聽的socket。以添加socket為例，如下圖，如果通過epoll_ctl添加sock1、sock2和sock3的監視，內核會將eventpoll添加到這三個socket的等待隊列中。
當socket收到數據後，中斷程序會操作eventpoll對象，而不是直接操作進程。
接收數據
當socket收到數據後，中斷程序會給eventpoll的「就緒列表」添加socket引用。如下圖展示的是sock2和sock3收到數據後，中斷程序讓rdlist引用這兩個socket。
eventpoll對象相當於是socket和進程之間的中介，socket的數據接收並不直接影響進程，而是通過改變eventpoll的就緒列表來改變進程狀態。
當程序執行到epoll_wait時，如果rdlist已經引用了socket，那麼epoll_wait直接返回，如果rdlist為空，阻塞進程。
阻塞和喚醒進程
假設計算機中正在運行進程A和進程B，在某時刻進程A運行到了epoll_wait語句。如下圖所示，內核會將進程A放入eventpoll的等待隊列中，阻塞進程。
當socket接收到數據，中斷程序一方面修改rdlist，另一方面喚醒eventpoll等待隊列中的進程，進程A再次進入運行狀態（如下圖）。也因為rdlist的存在，進程A可以知道哪些socket發生了變化。
八、epoll的實現細節
至此，相信讀者對epoll的本質已經有一定的瞭解。但我們還留有一個問題，eventpoll的數據結構是什麼樣子？
再留兩個問題，就緒隊列應該應使用什麼數據結構？eventpoll應使用什麼數據結構來管理通過epoll_ctl添加或刪除的socket？
（——我是分割線，想好了才能往下看哦~）
如下圖所示，eventpoll包含了lock、mtx、wq（等待隊列）、rdlist等成員。rdlist和rbr是我們所關心的。
就緒列表的數據結構
就緒列表引用著就緒的socket，所以它應能夠快速的插入數據。
程序可能隨時調用epoll_ctl添加監視socket，也可能隨時刪除。當刪除時，若該socket已經存放在就緒列表中，它也應該被移除。
所以就緒列表應是一種能夠快速插入和刪除的數據結構。雙向鏈表就是這樣一種數據結構，epoll使用雙向鏈表來實現就緒隊列（對應上圖的rdllist）。
索引結構
既然epoll將「維護監視隊列」和「進程阻塞」分離，也意味著需要有個數據結構來保存監視的socket。至少要方便的添加和移除，還要便於搜索，以避免重複添加。紅黑樹是一種自平衡二叉查找樹，搜索、插入和刪除時間複雜度都是O(log(N))，效率較好。epoll使用了紅黑樹作為索引結構（對應上圖的rbr）。
ps：因為操作系統要兼顧多種功能，以及由更多需要保存的數據，rdlist並非直接引用socket，而是通過epitem間接引用，紅黑樹的節點也是epitem對象。同樣，文件系統也並非直接引用著socket。為方便理解，本文中省略了一些間接結構。
九、結論
epoll在select和poll（poll和select基本一樣，有少量改進）的基礎引入了eventpoll作為中間層，使用了先進的數據結構，是一種高效的多路復用技術。
再留一點作業！
下表是個很常見的表，描述了select、poll和epoll的區別。讀完本文，讀者能否解釋select和epoll的時間複雜度為什麼是O(n)和O(1)？
筆者的《Unity3D網路遊戲實戰（第2版）》是一本專門介紹如何開發多人網路遊戲的書籍，用實例介紹開發遊戲的全過程，手把手教你如何製作一款多人開房間的坦克對戰遊戲。
「同步」也是網路遊戲開發的核心課題。如何恰當的使用不同的同步演算法？幀同步的應用場景和優越有哪些？筆者即將開展一場知乎live《網路遊戲同步演算法》，歡迎收聽。
網路遊戲同步演算法
致謝：本文力圖詳細說明epoll的原理，特別感謝 @陸俊壕 @AllenKong12 雄爺、堂叔 等同事審閱了文章並給予修改意見。
（完結）
推薦閱讀：
