如果這篇文章說不清epoll的本質,那就過來掐死我吧! (3) epoll是開發linux高性能伺服器的必備技術至,epoll本質,是服務端程序員的必須掌握的知識。文/羅培羽上篇回顧四、內核接收網路數據全過程五、同時監視多個socket的簡單方法 六、epoll的設計思路 七、epoll的原理和流程 本節會以示例和圖表來講解epoll的原理和流程。創建epoll對象如下圖所示,當某個進程調用epoll_create方法時,內核會創建一個eventpoll對象(也就是程序中epfd所代表的對象)。eventpoll對象也是文件系統中的一員,和socket一樣,它也會有等待隊列。 內核創建eventpoll對象創建一個代表該epoll的eventpoll對象是必須的,因為內核要維護「就緒列表」等數據,「就緒列表」可以作為eventpoll的成員。維護監視列表創建epoll對象後,可以用epoll_ctl添加或刪除所要監聽的socket。以添加socket為例,如下圖,如果通過epoll_ctl添加sock1、sock2和sock3的監視,內核會將eventpoll添加到這三個socket的等待隊列中。 添加所要監聽的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的等待隊列中,阻塞進程。 epoll_wait阻塞進程當socket接收到數據,中斷程序一方面修改rdlist,另一方面喚醒eventpoll等待隊列中的進程,進程A再次進入運行狀態(如下圖)。也因為rdlist的存在,進程A可以知道哪些socket發生了變化。 epoll喚醒進程 八、epoll的實現細節 至此,相信讀者對epoll的本質已經有一定的瞭解。但我們還留有一個問題,eventpoll的數據結構是什麼樣子?再留兩個問題,就緒隊列應該應使用什麼數據結構?eventpoll應使用什麼數據結構來管理通過epoll_ctl添加或刪除的socket?(——我是分割線,想好了才能往下看哦~)如下圖所示,eventpoll包含了lock、mtx、wq(等待隊列)、rdlist等成員。rdlist和rbr是我們所關心的。 epoll原理示意圖,圖片來源:《深入理解Nginx:模塊開發與架構解析(第二版)》,陶輝就緒列表的數據結構就緒列表引用著就緒的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)? select、poll和epoll的區別。圖片來源《Linux高性能伺服器編程》 筆者的《Unity3D網路遊戲實戰(第2版)》是一本專門介紹如何開發多人網路遊戲的書籍,用實例介紹開發遊戲的全過程,手把手教你如何製作一款多人開房間的坦克對戰遊戲。 「同步」也是網路遊戲開發的核心課題。如何恰當的使用不同的同步演算法?幀同步的應用場景和優越有哪些?筆者即將開展一場知乎live《網路遊戲同步演算法》,歡迎收聽。網路遊戲同步演算法?www.zhihu.com致謝:本文力圖詳細說明epoll的原理,特別感謝 @陸俊壕 @AllenKong12 雄爺、堂叔 等同事審閱了文章並給予修改意見。(完結) 推薦閱讀: 相關文章 {{#data}} {{title}} {{/data}}