圖解 - epoll 怎麼實現的

epoll 可以說是編寫高性能服務端程序必不可少的技術,在介紹 epoll 之前,我們先來了解一下 多路複用I/O 吧。

多路複用 I/O

多路複用I/O:是指內核負責監聽多個 I/O 流,當任何一個 I/O 流處於就緒狀態(可讀或可寫)時都會通知進程,以便可以處理該 I/O 流上的數據。如 圖 1 所示:

如 圖 1 所示,內核負責監聽多個 I/O 流,當某些 I/O 流變爲就緒狀態,內核會把這些 I/O 流添加到就緒隊列中,然後通知進程處理就緒隊列中的 I/O 流。

與傳統的阻塞型 I/O 相比,多路複用 I/O 的優點是可以同時監聽多個 I/O 流,並且會把就緒的 I/O 流告知進程。

epoll 原理

介紹完多路複用 I/O,接下來開始介紹我們的主角:epoll

在 Linux 系統中,有多種多路複用 I/O 的實現,比如 select 和 poll 等。而 epoll 也是多路複用 I/O 一種實現,與 select 和 poll 相比,epoll 在性能上有較大的提升。

紅黑樹

epoll 內部使用紅黑樹來保存所有監聽的 socket,紅黑樹是一種平衡二叉樹,添加和查找元素的時間複雜度爲 O(log n),其結構如 圖 2 所示:

epoll 通過 socket 句柄來作爲 key,把 socket 保存在紅黑樹中。如 圖 2 所示,每個節點中的數字代表着 socket 句柄。

把監聽的 socket 保存在紅黑樹中的目的是,爲了在修改監聽 socket 的讀寫事件時,能夠通過 socket 句柄快速找到對應的 socket 對象。

就緒隊列

另外,epoll 還維護着一個就緒隊列,當 epoll 監聽的 socket 狀態發生改變(變爲可讀或可寫)時,就會把就緒的 socket 添加到就緒隊列中。如 圖 3 所示:

當 socket 從網絡中獲取到數據後,會發生通知給 epoll,epoll 會將當前 socket 添加到就緒隊列中,並且喚醒等待中的進程(也就是調用 epoll_wait 的進程)。

當 socket 狀態發生變化時,會調用 ep_poll_callback 函數來通知 epoll,我們來看看這個函數的處理過程:

static int ep_poll_callback(wait_queue_t *wait, unsigned mode, 
                            int sync, void *key)
{
    ...
    struct epitem *epi = ep_item_from_wait(wait);
    struct eventpoll *ep = epi->ep;
    ...
    // 1) 把 socket 添加到就緒隊列中
    list_add_tail(&epi->rdllink, &ep->rdllist);
is_linked:
    // 2) 喚醒調用 epoll_wait() 而被阻塞的進程
    if (waitqueue_active(&ep->wq))
        wake_up_locked(&ep->wq);
    ...
    return 1;
}

ep_poll_callback 函數的意圖很清晰,主要完成兩個工作:

當進程被喚醒後,就會從就緒隊列中,把就緒的 socket 複製到用戶提供的數組中。如 圖 4 所示:

如 圖 4 所示,在調用 epoll_wait 時需要提供一個 events 數組來存儲就緒的 socket。當 epoll_wait 返回後,用戶就可以從events 數組中獲取到就緒的 socket,並可對其進行讀寫操作。

總結

本文主要通過圖解的方式大概介紹了 epoll 的原理,但很多實現的細節只能通過閱讀源碼來了解。如果對 epoll 的實現有興趣,可以參考《epoll 如何工作的》這篇文章。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/Fvmf2rr7X4_-u3vWOiz4EA