色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

一文詳解epoll的實現(xiàn)原理

xCb1_yikoulinux ? 來源:一口Linux ? 作者:一口Linux ? 2022-08-01 13:28 ? 次閱讀

前言

本文以四個方面介紹epoll的實現(xiàn)原理,1.epoll的數據結構;2.協(xié)議棧如何與epoll通信;3.epoll線程安全如何加鎖;4.ET與LT的實現(xiàn)。

epoll的數據結構

多種數據結構進行決策

epoll至少需要兩個集合

  1. 所有fd的總集

  2. 就緒fd的集合

那么這個總集選用什么數據結構存儲呢?我們知道,一個fd,其底層對應一個TCB。那么也就是說key=fd,val=TCB,是一個典型的kv型數據結構,對于kv型數據結構我們可以使用以下三種進行存儲。

1. hash2. 紅黑樹3. b/b+tree

如果使用hash進行存儲,其優(yōu)點是查詢速度很快,O(1)。但是在我們調用epoll_create()的時候,hash底層的數組創(chuàng)建多大合適呢?如果我們有百萬的fd,那么這個數組越大越好,如果我們僅僅十幾個fd需要管理,在創(chuàng)建數組的時候,太大的空間就很浪費。而這個fd我們又不能預先知道有多少,所以hash是不合適的。

b/b+tree是多叉樹,一個結點可以存多個key,主要是用于降低層高,用于磁盤索引的,所以在我們這個內存場景下也是不適合的。

在內存索引的場景下我們一般使用紅黑樹來作為首選的數據結構,首先紅黑樹的查找速度很快,O(log(N))。其次在調用epoll_create()的時候,只需要創(chuàng)建一個紅黑樹樹根即可,無需浪費額外的空間。

那么就緒集合用什么數據結構呢,首先就緒集合不是以查找為主的,就緒集合的作用是將里面的元素拷貝給用戶進行處理,所以集合里的元素沒有優(yōu)先級,那么就可以采用線性的數據結構,使用隊列來存儲,先進先出,先就緒的先處理。

  1. 所有fd的總集 -----> 紅黑樹

  2. 就緒fd的集合 -----> 隊列

紅黑樹和就緒隊列的關系

紅黑樹的結點和就緒隊列的結點的同一個節(jié)點,所謂的加入就緒隊列,就是將結點的前后指針聯(lián)系到一起。所以就緒了不是將紅黑樹結點delete掉然后加入隊列。他們是同一個結點,不需要delete。

2f225f1a-1153-11ed-ba43-dac502259ad0.jpg

2f59eea8-1153-11ed-ba43-dac502259ad0.png

協(xié)議棧如何與epoll模塊通信

epoll的工作環(huán)境

應用程序只能通過三個api接口來操作epoll。當一個io準備就緒的時候,epoll是怎么知道io準備就緒了呢?是由協(xié)議棧將數據解析出來觸發(fā)回調通知epoll的。也就是說可以把epoll的工作環(huán)境看出三部分,左邊應用程序的api,中間的epoll,右邊是協(xié)議棧的回調(協(xié)議棧當然不能直接操作epoll,中間的vfs在此不是重點,就直接省略vfs這一層了)。

2f766b8c-1153-11ed-ba43-dac502259ad0.png

協(xié)議棧觸發(fā)回調通知epoll的時機

socket有兩類,一類是監(jiān)聽listenfd,一類是客戶端clientfd。對于sockfd而言,我們一般比較關注EPOLLIN和EPOLLOUT這兩個事件,所以如果是listenfd,我們通常的做法就是accept。對于clientfd來說,如果可讀我們就recv,如果可寫我們就send。

協(xié)議棧將數據解析出來觸發(fā)回調通知epoll。epoll是怎么知道哪個io就緒了呢?我們從ip頭可以解析出源ip,目的ip和協(xié)議,從tcp頭可以解析出源端口和目的端口,此時五元組就湊齊了。socket fd --- < 源IP地址 , 源端口 , 目的IP地址 , 目的端口 , 協(xié)議 > 一個fd就是一個五元組,知道了fd,我們就能從紅黑樹中找到對應的結點。

那么這個回調函數做什么事情呢?我們傳入fd和具體事件這兩個參數,然后做下面兩個操作

1. 通過fd找到對應的結點

2. 把結點加入到就緒隊列

1、協(xié)議棧中,在三次握手完成之后,會往全連接隊列中添加一個TCB結點,然后觸發(fā)一個回調函數,通知到epoll里面有個EPOLLIN事件

2f815416-1153-11ed-ba43-dac502259ad0.jpg

2、客戶端發(fā)送一個數據包,協(xié)議棧接收后回復ACK,之后觸發(fā)一個回調函數,通知到epoll里面有個EPOLLIN事件

2fa506f4-1153-11ed-ba43-dac502259ad0.jpg

3、每個連接的TCB里面都有一個sendbuf,在對端接收到數據并返回ACK以后,sendbuf就可以將這部分確認接收的數據清空,此時sendbuf里面就有剩余空間,此時觸發(fā)一個回調函數,通知到epoll里面有個EPOLLOUT事件

2fc4a93c-1153-11ed-ba43-dac502259ad0.png

4、當對端發(fā)送close,在接收到fin后回復ACK,此時會調用回調函數,通知到epoll有個EPOLLIN事件

2fd8dfb0-1153-11ed-ba43-dac502259ad0.jpg

5、當接收到rst標志位的時候,回復ack之后也會觸發(fā)回調函數,通知epoll有一個EPOLLERR事件

2ff34f26-1153-11ed-ba43-dac502259ad0.png

通知的時機總結

一個有5個通知的地方

1. 三次握手完成之后2. 接收數據回復ACK之后3. 發(fā)送數據收到ACK之后4. 接收FIN回復ACK之后 5. 接收RST回復ACK之后

從回調機制看epoll 與 select/poll的區(qū)別

由于select和poll沒有本質的區(qū)別,所以下面統(tǒng)一稱為poll。

//  poll跟select類似, 其實poll就是把select三個文件描述符集合變成一個集合了。int select(int nfds, fd_set * readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);int poll(struct pollfd *fds, nfds_t nfds, int timeout);

我們看到每次調用poll,都需要把總集fds拷貝到內核態(tài),檢測完之后,再有內核態(tài)拷貝的用戶態(tài),這就是poll。而epoll不是這樣,epoll只要有新的io就調用epoll_ctl()加入到紅黑樹里面,一旦有觸發(fā)就用epoll_wait()將有事件的結點帶出來,可以看到他們的第一個區(qū)別:poll總是拷貝總集,如果有100w個fd,只有兩三個就緒呢?這會造成大量資源浪費;而epoll總是將需要拷貝的東西進行拷貝,沒有浪費。

第二個區(qū)別:我們從上面知道了epoll的事件都是由協(xié)議棧進行回調然后加入到就緒隊列的,而poll呢?內核如何檢測poll的io是否就緒?只能通過遍歷的方法判斷,所以poll檢測io通過遍歷的方法也是比較慢的。

所以兩者的區(qū)別:

  1. select/poll需要把總集copy到內核,而epoll不用

  2. 實現(xiàn)原理上面,select/poll 需要循環(huán)遍歷總集是否有就緒,而epoll是那個結點就緒了就加入就緒隊列里面。

注意:poll不一定就比epoll慢,在io量小的情況下,poll是比epoll快的,而在大io量下,epoll絕對是有主導地位的。至于有多少個io才算多,其實也很難說,一般認為500或者1024為分界點(我亂說的) 。

epoll線程安全如何加鎖

3個api做什么事情

  1. epoll_create() ===》創(chuàng)建紅黑樹的根節(jié)點

  2. epoll_ctl() ===》add,del,mod 增加、刪除、修改結點

  3. epoll_wait() ===》把就緒隊列的結點copy到用戶態(tài)放到events里面,跟recv函數很像

3014e2ee-1153-11ed-ba43-dac502259ad0.png

分析加鎖

如果有3個線程同時操作epoll,有哪些地方需要加鎖?我們用戶層面一共就只有3個api可以使用:

  1. 如果同時調用 epoll_create() ,那就是創(chuàng)建三顆紅黑樹,沒有涉及到資源競爭,沒有關系。

  2. 如果同時調用 epoll_ctl() ,對同一顆紅黑樹進行,增刪改,這就涉及到資源競爭需要加鎖了,此時我們對整棵樹進行加鎖。

  3. 如果同時調用epoll_wait() ,其操作的是就緒隊列,所以需要對就緒隊列進行加鎖。

我們要扣住epoll的工作環(huán)境,在應用程序調用 epoll_ctl() ,協(xié)議棧會不會有回調操作紅黑樹結點?調用epoll_wait() copy出來的時候,協(xié)議棧會不會操作操作紅黑樹結點加入就緒隊列?綜上所述:

epoll_ctl() 對紅黑樹加鎖epoll_wait()對就緒隊列加鎖回調函數()   對紅黑樹加鎖,對就緒隊列加鎖

那么紅黑樹加什么鎖,就緒隊列加什么鎖呢?

對于紅黑樹這種節(jié)點比較多的時候,采用互斥鎖來加鎖。就緒隊列就跟生產者消費者一樣,結點是從協(xié)議棧回調函數來生產的,消費是epoll_wait()來消費。那么對于隊列而言,用自旋鎖(對于隊列而言,插入刪除比較簡單,cpu自旋等待比讓出的成本更低,所以用自旋鎖)。

ET與LT如何實現(xiàn)

  • ET邊沿觸發(fā),只觸發(fā)一次

  • LT水平觸發(fā),如果沒有讀完就一直觸發(fā)

代碼如何實現(xiàn)ET和LT的效果呢?水平觸發(fā)和邊沿觸發(fā)不是故意設計出來的,這是自然而然,水到渠成的功能。水平觸發(fā)和邊沿觸發(fā)代碼只需要改一點點就能實現(xiàn)。從協(xié)議棧檢測到接收數據,就調用一次回調,這就是ET,接收到數據,調用一次回調。而LT水平觸發(fā),檢測到recvbuf里面有數據就調用回調。所以ET和LT就是在使用回調的次數上面的差異。

那么具體如何實現(xiàn)呢?協(xié)議棧流程里面觸發(fā)回調,是天然的符合ET只觸發(fā)一次的。那么如果是LT,在recv之后,如果緩沖區(qū)還有數據那么加入到就緒隊列。那么如果是LT,在send之后,如果緩沖區(qū)還有空間那么加入到就緒隊列。那么這樣就能實現(xiàn)LT了。

302505de-1153-11ed-ba43-dac502259ad0.png


審核編輯:湯梓紅


聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 存儲
    +關注

    關注

    13

    文章

    4296

    瀏覽量

    85800
  • 數據結構
    +關注

    關注

    3

    文章

    573

    瀏覽量

    40123
  • epoll
    +關注

    關注

    0

    文章

    28

    瀏覽量

    2951

原文標題:從4個方面分析epoll的實現(xiàn)原理

文章出處:【微信號:yikoulinux,微信公眾號:一口Linux】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    epoll的使用

    以下內容是參考華清遠見《linux/unix系統(tǒng)編程手冊》對epoll個個人總結,是我在華清遠見比較全面的總結。epoll的優(yōu)點同I/O多路復用和信號驅動I/O
    發(fā)表于 05-11 13:22

    揭示EPOLL些原理性的東西

    我們對這些流的操作都是有意義的。(復雜度降低到了O(1))在討論epoll實現(xiàn)細節(jié)之前,先把epoll的相關操作列出:epoll_create 創(chuàng)建
    發(fā)表于 08-24 16:32

    poll&&epollepoll實現(xiàn)

    poll&&epollepoll實現(xiàn)
    發(fā)表于 05-14 14:34 ?2790次閱讀
    poll&&<b class='flag-5'>epoll</b>之<b class='flag-5'>epoll</b><b class='flag-5'>實現(xiàn)</b>

    詳解精密封裝技術

    詳解精密封裝技術
    的頭像 發(fā)表于 12-30 15:41 ?1654次閱讀

    詳解分立元件門電路

    詳解分立元件門電路
    的頭像 發(fā)表于 03-27 17:44 ?3161次閱讀
    <b class='flag-5'>一</b><b class='flag-5'>文</b><b class='flag-5'>詳解</b>分立元件門電路

    詳解pcb和smt的區(qū)別

    詳解pcb和smt的區(qū)別
    的頭像 發(fā)表于 10-08 09:31 ?3341次閱讀

    詳解pcb地孔的作用

    詳解pcb地孔的作用
    的頭像 發(fā)表于 10-30 16:02 ?1637次閱讀

    epoll實現(xiàn)多路復用

    本人用epoll實現(xiàn)多路復用,epoll觸發(fā)模式有兩種: ET(邊緣模式) LT(水平模式) LT模式 是標準模式,意味著每次epoll_wait()返回后,事件處理后,如果之后還有
    的頭像 發(fā)表于 11-09 10:15 ?507次閱讀
    用<b class='flag-5'>epoll</b>來<b class='flag-5'>實現(xiàn)</b>多路復用

    epoll實現(xiàn)原理

    今兒我們就從源碼入手,來幫助大家簡單理解epoll實現(xiàn)原理,并在后邊分析下,大家都說 epoll 性能好,那到底是好在哪里。
    的頭像 發(fā)表于 11-09 11:14 ?532次閱讀
    <b class='flag-5'>epoll</b> 的<b class='flag-5'>實現(xiàn)</b>原理

    epoll的基礎數據結構

    epoll的基礎數據結構 在開始研究源代碼之前,我們先看epoll 中使用的數據結構,分別是 eventpoll、epitem 和 eppoll_entry。 1、event
    的頭像 發(fā)表于 11-10 10:20 ?797次閱讀
    <b class='flag-5'>epoll</b>的基礎數據結構

    epoll源碼分析

    個函數進行源碼分析。 源碼來源 由于epoll實現(xiàn)內嵌在內核中,直接查看內核源碼的話會有些無關代碼影響閱讀。為此在GitHub上寫的簡化版TCP/IP協(xié)議棧,里面實現(xiàn)
    的頭像 發(fā)表于 11-13 11:49 ?1034次閱讀
    <b class='flag-5'>epoll</b>源碼分析

    Epoll封裝類實現(xiàn)

    )的事件,并將事件從內核通知到用戶區(qū),實現(xiàn)對特定事件的響應處理,而epoll可認為是poll的改進版,在多個方面大幅度提高了性能(當然也是在監(jiān)聽描述符多、活躍描述符少的條件下)。 epoll的主要特點有以下幾點: 1.支持
    的頭像 發(fā)表于 11-13 11:54 ?499次閱讀

    詳解pcb不良分析

    詳解pcb不良分析
    的頭像 發(fā)表于 11-29 17:12 ?1160次閱讀

    詳解pcb的msl等級

    詳解pcb的msl等級
    的頭像 發(fā)表于 12-13 16:52 ?9556次閱讀

    詳解pcb的組成和作用

    詳解pcb的組成和作用
    的頭像 發(fā)表于 12-18 10:48 ?1528次閱讀
    主站蜘蛛池模板: 亚洲 成人网| 天天久久狠狠色综合| 青柠在线视频| 十分钟在线观看免费视频高清WWW| 亚洲免费无码中文在线| music radio在线收听| 国产国拍精品AV在线观看| 久久精品国产亚洲AV妓女不卡| 女王羞辱丨vk| 亚洲精品天堂无码中文字幕影院| 99国产精品久久人妻| 国产午夜精品久久理论片| 免费看到湿的小黄文软件APP| 无码国产伦一区二区三区视频| 中文字幕亚洲欧美在线视频| 国产99在线视频| 麻豆国产人妻精品无码AV| 午夜啪啪免费视频| 97精品国产高清在线看入口 | 在线视频免费国产成人| 大肥婆丰满大肥奶bbw肥| 久久精选视频| 先锋资源久久| SM高H黄暴NP辣H调教性奴| 久久99r66热这里有精品| 色欲国产麻豆一精品一AV一免费| 在线观看国产精选免费| 国产精品爽爽久久久久久竹菊| 男女免费观看在线爽爽爽视频| 亚洲精品国产熟女久久久| 成3d漫二区三区四区| 美女被黑人巨大进入| 亚洲日韩乱码人人爽人人澡人| 囯产精品一品二区三区| 伦理片飘花免费影院| 亚洲精品网址| 国产成人精品电影| 欧洲内射VIDEOXXX3D| 自拍视频亚洲综合在线精品| 国产在线一卡二卡| 偷拍亚洲色自拍|