找回密碼
 注冊帳號

掃一掃,訪問微社區

碧俐千仞 如果這篇文章說不清epoll的本質,那就過來掐死我吧! (3)

4
回復
887
查看
打印 上一主題 下一主題
[ 復制鏈接 ]
排名
19948
昨日變化

41

主題

222

帖子

876

積分

Rank: 9Rank: 9Rank: 9

UID
53741
好友
39
蠻牛幣
2647
威望
0
注冊時間
2014-11-6
在線時間
207 小時
最后登錄
2019-8-8

專欄作家

馬上注冊,結交更多好友,享用更多功能,讓你輕松玩轉社區。

您需要 登錄 才可以下載或查看,沒有帳號?注冊帳號

x
本帖最后由 tyxxxx 于 2019-6-13 19:16 編輯

從事服務端開發,少不了要接觸網絡編程。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高性能服務器編程》



《網絡游戲實戰(第2版)》是一本專門介紹如何開發多人網絡游戲的書籍,用實例介紹開發游戲的全過程,非常實用。書中對網絡編程有詳細的講解,全書用一個大例子貫穿,真正的“實戰”教程。





回復

使用道具 舉報

7日久生情
2056/5000
排名
4092
昨日變化

0

主題

1340

帖子

2056

積分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
254705
好友
1
蠻牛幣
1871
威望
0
注冊時間
2017-11-16
在線時間
354 小時
最后登錄
2019-8-7
沙發
2019-6-14 08:11:48 只看該作者
66666666666666666666666666666666666
回復 支持 反對

使用道具 舉報

5熟悉之中
699/1000
排名
10706
昨日變化

0

主題

451

帖子

699

積分

Rank: 5Rank: 5

UID
301976
好友
1
蠻牛幣
1048
威望
0
注冊時間
2018-10-31
在線時間
150 小時
最后登錄
2019-8-8
板凳
2019-6-14 10:03:12 只看該作者
感謝大佬普及知識
回復 支持 反對

使用道具 舉報

排名
64931
昨日變化

0

主題

29

帖子

69

積分

Rank: 2Rank: 2

UID
259926
好友
0
蠻牛幣
143
威望
0
注冊時間
2017-12-16
在線時間
38 小時
最后登錄
2019-8-8
地板
2019-6-24 16:58:13 只看該作者
很詳細 感謝大佬分享
回復 支持 反對

使用道具 舉報

5熟悉之中
699/1000
排名
10706
昨日變化

0

主題

451

帖子

699

積分

Rank: 5Rank: 5

UID
301976
好友
1
蠻牛幣
1048
威望
0
注冊時間
2018-10-31
在線時間
150 小時
最后登錄
2019-8-8
5#
2019-7-4 10:12:03 只看該作者
回復

使用道具 舉報

您需要登錄后才可以回帖 登錄 | 注冊帳號

本版積分規則

女校游泳队彩金