epoll的原理和流程

【轉(zhuǎn)載作者】 羅培羽
【文章來源】 https://zhuanlan.zhihu.com/p/64746509

創(chuàng)建epoll對象

如下圖所示卓鹿，當(dāng)某個(gè)進(jìn)程調(diào)用epoll_create方法時(shí)，內(nèi)核會(huì)創(chuàng)建一個(gè)eventpoll對象（也就是程序中epfd所代表的對象）。eventpoll對象也是文件系統(tǒng)中的一員属划，和socket一樣涧至，它也會(huì)有等待隊(duì)列。

image

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

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

創(chuàng)建epoll對象后，可以用epoll_ctl添加或刪除所要監(jiān)聽的socket舱馅。以添加socket為例缰泡，如下圖，如果通過epoll_ctl添加sock1代嗤、sock2和sock3的監(jiān)視棘钞，內(nèi)核會(huì)將eventpoll添加到這三個(gè)socket的等待隊(duì)列中。

image

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

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

當(dāng)socket收到數(shù)據(jù)后硝逢，中斷程序會(huì)給eventpoll的“就緒列表”添加socket引用宝恶。如下圖展示的是sock2和sock3收到數(shù)據(jù)后，中斷程序讓rdlist引用這兩個(gè)socket趴捅。

image

eventpoll對象相當(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語句额各。如下圖所示，內(nèi)核會(huì)將進(jìn)程A放入eventpoll的等待隊(duì)列中吧恃，阻塞進(jìn)程虾啦。

image

當(dāng)socket接收到數(shù)據(jù)，中斷程序一方面修改rdlist痕寓，另一方面喚醒eventpoll等待隊(duì)列中的進(jìn)程傲醉，進(jìn)程A再次進(jìn)入運(yùn)行狀態(tài)（如下圖）。也因?yàn)閞dlist的存在呻率，進(jìn)程A可以知道哪些socket發(fā)生了變化硬毕。

image

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

至此，相信讀者對epoll的本質(zhì)已經(jīng)有一定的了解礼仗。但我們還留有一個(gè)問題吐咳，eventpoll的數(shù)據(jù)結(jié)構(gòu)是什么樣子逻悠？

再留兩個(gè)問題，就緒隊(duì)列應(yīng)該應(yīng)使用什么數(shù)據(jù)結(jié)構(gòu)韭脊？eventpoll應(yīng)使用什么數(shù)據(jù)結(jié)構(gòu)來管理通過epoll_ctl添加或刪除的socket蹂风？

（——我是分割線，想好了才能往下看哦~）

如下圖所示乾蓬，eventpoll包含了lock惠啄、mtx、wq（等待隊(duì)列）任内、rdlist等成員撵渡。rdlist和rbr是我們所關(guān)心的。

image

就緒列表的數(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ì)列（對應(yīng)上圖的rdllist）孩擂。

索引結(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)（對應(yīng)上圖的rbr）蘸嘶。

ps：因?yàn)椴僮飨到y(tǒng)要兼顧多種功能，以及由更多需要保存的數(shù)據(jù)氯析，rdlist并非直接引用socket亏较，而是通過epitem間接引用莺褒，紅黑樹的節(jié)點(diǎn)也是epitem對象掩缓。同樣，文件系統(tǒng)也并非直接引用著socket遵岩。為方便理解你辣，本文中省略了一些間接結(jié)構(gòu)巡通。

結(jié)論

epoll在select和poll（poll和select基本一樣，有少量改進(jìn)）的基礎(chǔ)引入了eventpoll作為中間層舍哄，使用了先進(jìn)的數(shù)據(jù)結(jié)構(gòu)宴凉，是一種高效的多路復(fù)用技術(shù)。

再留一點(diǎn)作業(yè)表悬！

下表是個(gè)很常見的表弥锄，描述了select、poll和epoll的區(qū)別蟆沫。讀完本文籽暇，讀者能否解釋select和epoll的時(shí)間復(fù)雜度為什么是O(n)和O(1)？

image