點(diǎn)贊再看跋破，養(yǎng)成習(xí)慣簸淀，公眾號(hào)搜一搜【一角錢(qián)技術(shù)】關(guān)注更多原創(chuàng)技術(shù)文章。本文 GitHub org_hejianhui/JavaStudy 已收錄毒返，有我的系列文章租幕。

前言

• BIO 、NIO 拧簸、AIO 總結(jié)
• Unix網(wǎng)絡(luò)編程中的五種IO模型

為了加深對(duì) I/O多路復(fù)用機(jī)制 的理解劲绪，以及了解到多路復(fù)用也有局限性，本著打破砂鍋問(wèn)到底的精神盆赤，前面我們講了BIO贾富、NIO、AIO的基本概念以及一些常見(jiàn)問(wèn)題牺六，同時(shí)也回顧了Unix網(wǎng)絡(luò)編程中的五種IO模型颤枪。本篇重點(diǎn)學(xué)習(xí)理解IO多路復(fù)用的底層實(shí)現(xiàn)機(jī)制。

概念說(shuō)明

IO 多路復(fù)用有三種實(shí)現(xiàn)淑际，在介紹select畏纲、poll扇住、epoll之前，首先介紹一下Linux操作系統(tǒng)中基礎(chǔ)的概念：

• 用戶(hù)空間和內(nèi)核空間
• 進(jìn)程切換
• 進(jìn)程的阻塞
• 文件描述符
• 緩存 I/O

用戶(hù)空間 / 內(nèi)核空間

現(xiàn)在操作系統(tǒng)都是采用虛擬存儲(chǔ)器盗胀，那么對(duì)32位操作系統(tǒng)而言艘蹋，它的尋址空間（虛擬存儲(chǔ)空間）為4G（2的32次方）。
操作系統(tǒng)的核心是內(nèi)核票灰，獨(dú)立于普通的應(yīng)用程序女阀，可以訪(fǎng)問(wèn)受保護(hù)的內(nèi)存空間，也有訪(fǎng)問(wèn)底層硬件設(shè)備的所有權(quán)限米间。為了保證用戶(hù)進(jìn)程不能直接操作內(nèi)核（kernel）强品，保證內(nèi)核的安全，操作系統(tǒng)將虛擬空間劃分為兩部分屈糊，一部分為內(nèi)核空間的榛，一部分為用戶(hù)空間。

針對(duì)linux操作系統(tǒng)而言逻锐，將最高的1G字節(jié)（從虛擬地址0xC0000000到0xFFFFFFFF）夫晌，供內(nèi)核使用，稱(chēng)為內(nèi)核空間昧诱，而將較低的3G字節(jié)（從虛擬地址0x00000000到0xBFFFFFFF）晓淀，供各個(gè)進(jìn)程使用，稱(chēng)為用戶(hù)空間盏档。

進(jìn)程切換

為了控制進(jìn)程的執(zhí)行凶掰，內(nèi)核必須有能力掛起正在CPU上運(yùn)行的進(jìn)程，并恢復(fù)以前掛起的某個(gè)進(jìn)程的執(zhí)行蜈亩。這種行為被稱(chēng)為進(jìn)程切換懦窘。因此可以說(shuō)，任何進(jìn)程都是在操作系統(tǒng)內(nèi)核的支持下運(yùn)行的稚配，是與內(nèi)核緊密相關(guān)的畅涂，并且進(jìn)程切換是非常耗費(fèi)資源的。

從一個(gè)進(jìn)程的運(yùn)行轉(zhuǎn)到另一個(gè)進(jìn)程上運(yùn)行道川，這個(gè)過(guò)程中經(jīng)過(guò)下面這些變化：

1. 保存處理機(jī)上下文午衰，包括程序計(jì)數(shù)器和其他寄存器。
2. 更新PCB信息冒萄。
3. 把進(jìn)程的PCB移入相應(yīng)的隊(duì)列臊岸，如就緒、在某事件阻塞等隊(duì)列宦言。
4. 選擇另一個(gè)進(jìn)程執(zhí)行扇单，并更新其PCB。
5. 更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)奠旺。
6. 恢復(fù)處理機(jī)上下文蜘澜。

進(jìn)程阻塞

正在執(zhí)行的進(jìn)程施流，由于期待的某些事件未發(fā)生，如請(qǐng)求系統(tǒng)資源失敗鄙信、等待某種操作的完成瞪醋、新數(shù)據(jù)尚未到達(dá)或無(wú)新工作做等，則由系統(tǒng)自動(dòng)執(zhí)行阻塞原語(yǔ)(Block)装诡，使自己由運(yùn)行狀態(tài)變?yōu)樽枞麪顟B(tài)银受。可見(jiàn)鸦采，進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為宾巍，也因此只有處于運(yùn)行態(tài)的進(jìn)程（獲得了CPU資源），才可能將其轉(zhuǎn)為阻塞狀態(tài)渔伯。當(dāng)進(jìn)程進(jìn)入阻塞狀態(tài)顶霞，是不占用CPU資源的。

文件描述符

文件描述符（File descriptor）是計(jì)算機(jī)科學(xué)中的一個(gè)術(shù)語(yǔ)锣吼，是一個(gè)用于表述指向文件的引用的抽象化概念选浑。
文件描述符在形式上是一個(gè)非負(fù)整數(shù)。實(shí)際上玄叠，它是一個(gè)索引值古徒，指向內(nèi)核為每一個(gè)進(jìn)程所維護(hù)的該進(jìn)程打開(kāi)文件的記錄表。當(dāng)程序打開(kāi)一個(gè)現(xiàn)有文件或者創(chuàng)建一個(gè)新文件時(shí)读恃，內(nèi)核向進(jìn)程返回一個(gè)文件描述符隧膘。在程序設(shè)計(jì)中，一些涉及底層的程序編寫(xiě)往往會(huì)圍繞著文件描述符展開(kāi)寺惫。但是文件描述符這一概念往往只適用于UNIX舀寓、Linux這樣的操作系統(tǒng)膨处。

緩存I/O

緩存I/O又稱(chēng)為標(biāo)準(zhǔn)I/O王带，大多數(shù)文件系統(tǒng)的默認(rèn)I/O操作都是緩存I/O绊含。在Linux的緩存I/O機(jī)制中，操作系統(tǒng)會(huì)將I/O的數(shù)據(jù)緩存在文件系統(tǒng)的頁(yè)緩存中蒋搜，即數(shù)據(jù)會(huì)先被拷貝到操作系統(tǒng)內(nèi)核的緩沖區(qū)中，然后才會(huì)從操作系統(tǒng)內(nèi)核的緩沖區(qū)拷貝到應(yīng)用程序的地址空間判莉。

緩存 I/O 的缺點(diǎn)：

數(shù)據(jù)在傳輸過(guò)程中需要在應(yīng)用程序地址空間和內(nèi)核進(jìn)行多次數(shù)據(jù)拷貝操作豆挽，這些數(shù)據(jù)拷貝操作所帶來(lái)的 CPU 以及內(nèi)存開(kāi)銷(xiāo)是非常大的。

什么是IO多路復(fù)用券盅？

• IO 多路復(fù)用是一種同步IO模型帮哈，實(shí)現(xiàn)一個(gè)線(xiàn)程可以監(jiān)視多個(gè)文件句柄；
• 一旦某個(gè)文件句柄就緒锰镀，就能夠通知應(yīng)用程序進(jìn)行相應(yīng)的讀寫(xiě)操作娘侍；
• 沒(méi)有文件句柄就緒就會(huì)阻塞應(yīng)用程序咖刃，交出CPU。

多路是指網(wǎng)絡(luò)連接憾筏，復(fù)用指的是同一個(gè)線(xiàn)程

為什么有IO多路復(fù)用機(jī)制嚎杨？

沒(méi)有IO多路復(fù)用機(jī)制時(shí)，有BIO氧腰、NIO兩種實(shí)現(xiàn)方式枫浙，但它們都有一些問(wèn)題

同步阻塞（BIO）

• 服務(wù)端采用單線(xiàn)程，當(dāng) accept 一個(gè)請(qǐng)求后古拴，在 recv 或 send 調(diào)用阻塞時(shí)箩帚，將無(wú)法 accept 其他請(qǐng)求（必須等上一個(gè)請(qǐng)求處理 recv 或 send 完 ）（無(wú)法處理并發(fā)）

// 偽代碼描述
while (true) {
    // accept阻塞
    client_fd = accept(listen_fd);
    fds.append(client_fd);
    for (fd in fds) {
        // recv阻塞（會(huì)影響上面的accept）
        if (recv(fd)) {
            // logic
        }
    }
}

• 服務(wù)端采用多線(xiàn)程，當(dāng) accept 一個(gè)請(qǐng)求后黄痪，開(kāi)啟線(xiàn)程進(jìn)行 recv紧帕，可以完成并發(fā)處理，但隨著請(qǐng)求數(shù)增加需要增加系統(tǒng)線(xiàn)程满力，大量的線(xiàn)程占用很大的內(nèi)存空間焕参，并且線(xiàn)程切換會(huì)帶來(lái)很大的開(kāi)銷(xiāo)，10000個(gè)線(xiàn)程真正發(fā)生讀寫(xiě)實(shí)際的線(xiàn)程數(shù)不會(huì)超過(guò)20%油额，每次accept都開(kāi)一個(gè)線(xiàn)程也是一種資源浪費(fèi)叠纷。

// 偽代碼描述
while(true) {
  // accept阻塞
  client_fd = accept(listen_fd)
  // 開(kāi)啟線(xiàn)程read數(shù)據(jù)（fd增多導(dǎo)致線(xiàn)程數(shù)增多）
  new Thread func() {
    // recv阻塞（多線(xiàn)程不影響上面的accept）
    if (recv(fd)) {
      // logic
    }
  }  
}

同步非阻塞（NIO）

• 服務(wù)器端當(dāng) accept 一個(gè)請(qǐng)求后，加入 fds 集合潦嘶，每次輪詢(xún)一遍 fds 集合 recv (非阻塞)數(shù)據(jù)涩嚣，沒(méi)有數(shù)據(jù)則立即返回錯(cuò)誤，每次輪詢(xún)所有 fd （包括沒(méi)有發(fā)生讀寫(xiě)實(shí)際的 fd）會(huì)很浪費(fèi) CPU掂僵。

// 偽代碼描述
while(true) {
  // accept非阻塞（cpu一直忙輪詢(xún)）
  client_fd = accept(listen_fd)
  if (client_fd != null) {
    // 有人連接
    fds.append(client_fd)
  } else {
    // 無(wú)人連接
  }  
  for (fd in fds) {
    // recv非阻塞
    setNonblocking(client_fd)
    // recv 為非阻塞命令
    if (len = recv(fd) && len > 0) {
      // 有讀寫(xiě)數(shù)據(jù)
      // logic
    } else {
       無(wú)讀寫(xiě)數(shù)據(jù)
    }
  }  
}

IO多路復(fù)用

服務(wù)器端采用單線(xiàn)程通過(guò) select/poll/epoll 等系統(tǒng)調(diào)用獲取 fd 列表航厚，遍歷有事件的 fd 進(jìn)行 accept/recv/send ，使其能支持更多的并發(fā)連接請(qǐng)求锰蓬。

// 偽代碼描述
while(true) {
  // 通過(guò)內(nèi)核獲取有讀寫(xiě)事件發(fā)生的fd幔睬，只要有一個(gè)則返回，無(wú)則阻塞
  // 整個(gè)過(guò)程只在調(diào)用select芹扭、poll麻顶、epoll這些調(diào)用的時(shí)候才會(huì)阻塞，accept/recv是不會(huì)阻塞
  for (fd in select(fds)) {
    if (fd == listen_fd) {
        client_fd = accept(listen_fd)
        fds.append(client_fd)
    } elseif (len = recv(fd) && len != -1) { 
      // logic
    }
  }  
}

IO多路復(fù)用的三種實(shí)現(xiàn)

• select
• poll
• epoll

select

它僅僅知道了舱卡，有I/O事件發(fā)生了辅肾，卻并不知道是哪那幾個(gè)流（可能有一個(gè)，多個(gè)轮锥，甚至全部）矫钓，我們只能無(wú)差別輪詢(xún)所有流，找出能讀出數(shù)據(jù)，或者寫(xiě)入數(shù)據(jù)的流新娜，對(duì)他們進(jìn)行操作赵辕。所以select具有O(n)的無(wú)差別輪詢(xún)復(fù)雜度，同時(shí)處理的流越多杯活，無(wú)差別輪詢(xún)時(shí)間就越長(zhǎng)匆帚。

select調(diào)用過(guò)程

image.png

（1）使用copy_from_user從用戶(hù)空間拷貝fd_set到內(nèi)核空間

（2）注冊(cè)回調(diào)函數(shù)__pollwait

（3）遍歷所有fd，調(diào)用其對(duì)應(yīng)的poll方法（對(duì)于socket旁钧，這個(gè)poll方法是sock_poll吸重，sock_poll根據(jù)情況會(huì)調(diào)用到tcp_poll,udp_poll或者datagram_poll）

（4）以tcp_poll為例，其核心實(shí)現(xiàn)就是__pollwait歪今，也就是上面注冊(cè)的回調(diào)函數(shù)嚎幸。

（5）__pollwait的主要工作就是把current（當(dāng)前進(jìn)程）掛到設(shè)備的等待隊(duì)列中，不同的設(shè)備有不同的等待隊(duì)列寄猩，對(duì)于tcp_poll來(lái)說(shuō)嫉晶，其等待隊(duì)列是sk->sk_sleep（注意把進(jìn)程掛到等待隊(duì)列中并不代表進(jìn)程已經(jīng)睡眠了）。在設(shè)備收到一條消息（網(wǎng)絡(luò)設(shè)備）或填寫(xiě)完文件數(shù)據(jù)（磁盤(pán)設(shè)備）后田篇，會(huì)喚醒設(shè)備等待隊(duì)列上睡眠的進(jìn)程替废，這時(shí)current便被喚醒了。

（6）poll方法返回時(shí)會(huì)返回一個(gè)描述讀寫(xiě)操作是否就緒的mask掩碼泊柬，根據(jù)這個(gè)mask掩碼給fd_set賦值椎镣。

（7）如果遍歷完所有的fd，還沒(méi)有返回一個(gè)可讀寫(xiě)的mask掩碼兽赁，則會(huì)調(diào)用schedule_timeout是調(diào)用select的進(jìn)程（也就是current）進(jìn)入睡眠状答。當(dāng)設(shè)備驅(qū)動(dòng)發(fā)生自身資源可讀寫(xiě)后，會(huì)喚醒其等待隊(duì)列上睡眠的進(jìn)程刀崖。如果超過(guò)一定的超時(shí)時(shí)間（schedule_timeout指定）惊科，還是沒(méi)人喚醒，則調(diào)用select的進(jìn)程會(huì)重新被喚醒獲得CPU亮钦，進(jìn)而重新遍歷fd馆截，判斷有沒(méi)有就緒的fd。

（8）把fd_set從內(nèi)核空間拷貝到用戶(hù)空間蜂莉。

select函數(shù)接口

#include <sys/select.h>
#include <sys/time.h>

#define FD_SETSIZE 1024
#define NFDBITS (8 * sizeof(unsigned long))
#define __FDSET_LONGS (FD_SETSIZE/NFDBITS)

// 數(shù)據(jù)結(jié)構(gòu) (bitmap)
typedef struct {
    unsigned long fds_bits[__FDSET_LONGS];
} fd_set;

// API
int select(
    int max_fd, 
    fd_set *readset, 
    fd_set *writeset, 
    fd_set *exceptset, 
    struct timeval *timeout
)                              // 返回值就緒描述符的數(shù)目

FD_ZERO(int fd, fd_set* fds)   // 清空集合
FD_SET(int fd, fd_set* fds)    // 將給定的描述符加入集合
FD_ISSET(int fd, fd_set* fds)  // 判斷指定描述符是否在集合中 
FD_CLR(int fd, fd_set* fds)    // 將給定的描述符從文件中刪除  

select使用示例

int main() {
  /*
   * 這里進(jìn)行一些初始化的設(shè)置孙咪，
   * 包括socket建立，地址的設(shè)置等,
   */

  fd_set read_fs, write_fs;
  struct timeval timeout;
  int max = 0;  // 用于記錄最大的fd巡语，在輪詢(xún)中時(shí)刻更新即可

  // 初始化比特位
  FD_ZERO(&read_fs);
  FD_ZERO(&write_fs);

  int nfds = 0; // 記錄就緒的事件，可以減少遍歷的次數(shù)
  while (1) {
    // 阻塞獲取
    // 每次需要把fd從用戶(hù)態(tài)拷貝到內(nèi)核態(tài)
    nfds = select(max + 1, &read_fd, &write_fd, NULL, &timeout);
    // 每次需要遍歷所有fd淮菠，判斷有無(wú)讀寫(xiě)事件發(fā)生
    for (int i = 0; i <= max && nfds; ++i) {
      if (i == listenfd) {
         --nfds;
         // 這里處理accept事件
         FD_SET(i, &read_fd);//將客戶(hù)端socket加入到集合中
      }
      if (FD_ISSET(i, &read_fd)) {
        --nfds;
        // 這里處理read事件
      }
      if (FD_ISSET(i, &write_fd)) {
         --nfds;
        // 這里處理write事件
      }
    }
  }

select缺點(diǎn)

select本質(zhì)上是通過(guò)設(shè)置或者檢查存放fd標(biāo)志位的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行下一步處理男公。這樣所帶來(lái)的缺點(diǎn)是：

• 單個(gè)進(jìn)程所打開(kāi)的FD是有限制的，通過(guò) FD_SETSIZE 設(shè)置，默認(rèn)1024 ;

• 每次調(diào)用 select枢赔，都需要把 fd 集合從用戶(hù)態(tài)拷貝到內(nèi)核態(tài)澄阳，這個(gè)開(kāi)銷(xiāo)在 fd 很多時(shí)會(huì)很大；

需要維護(hù)一個(gè)用來(lái)存放大量fd的數(shù)據(jù)結(jié)構(gòu)踏拜，這樣會(huì)使得用戶(hù)空間和內(nèi)核空間在傳遞該結(jié)構(gòu)時(shí)復(fù)制開(kāi)銷(xiāo)大

• 對(duì) socket 掃描時(shí)是線(xiàn)性?huà)呙杷橛捎幂喸?xún)的方法，效率較低（高并發(fā)）

當(dāng)套接字比較多的時(shí)候速梗，每次select()都要通過(guò)遍歷FD_SETSIZE個(gè)Socket來(lái)完成調(diào)度,不管哪個(gè)Socket是活躍的,都遍歷一遍肮塞。這會(huì)浪費(fèi)很多CPU時(shí)間。如果能給套接字注冊(cè)某個(gè)回調(diào)函數(shù)姻锁，當(dāng)他們活躍時(shí)枕赵，自動(dòng)完成相關(guān)操作，那就避免了輪詢(xún)位隶，這正是epoll與kqueue做的拷窜。

poll

poll本質(zhì)上和select沒(méi)有區(qū)別，它將用戶(hù)傳入的數(shù)組拷貝到內(nèi)核空間涧黄，然后查詢(xún)每個(gè)fd對(duì)應(yīng)的設(shè)備狀態(tài)篮昧， 但是它沒(méi)有最大連接數(shù)的限制，原因是它是基于鏈表來(lái)存儲(chǔ)的.

poll函數(shù)接口

#include <poll.h>
// 數(shù)據(jù)結(jié)構(gòu)
struct pollfd {
    int fd;                         // 需要監(jiān)視的文件描述符
    short events;                   // 需要內(nèi)核監(jiān)視的事件
    short revents;                  // 實(shí)際發(fā)生的事件
};

// API
int poll(struct pollfd fds[], nfds_t nfds, int timeout);

poll使用示例

// 先宏定義長(zhǎng)度
#define MAX_POLLFD_LEN 4096  

int main() {
  /*
   * 在這里進(jìn)行一些初始化的操作笋妥，
   * 比如初始化數(shù)據(jù)和socket等懊昨。
   */

  int nfds = 0;
  pollfd fds[MAX_POLLFD_LEN];
  memset(fds, 0, sizeof(fds));
  fds[0].fd = listenfd;
  fds[0].events = POLLRDNORM;
  int max  = 0;  // 隊(duì)列的實(shí)際長(zhǎng)度，是一個(gè)隨時(shí)更新的挽鞠，也可以自定義其他的
  int timeout = 0;

  int current_size = max;
  while (1) {
    // 阻塞獲取
    // 每次需要把fd從用戶(hù)態(tài)拷貝到內(nèi)核態(tài)
    nfds = poll(fds, max+1, timeout);
    if (fds[0].revents & POLLRDNORM) {
        // 這里處理accept事件
        connfd = accept(listenfd);
        //將新的描述符添加到讀描述符集合中
    }
    // 每次需要遍歷所有fd疚颊，判斷有無(wú)讀寫(xiě)事件發(fā)生
    for (int i = 1; i < max; ++i) {     
      if (fds[i].revents & POLLRDNORM) { 
         sockfd = fds[i].fd
         if ((n = read(sockfd, buf, MAXLINE)) <= 0) {
            // 這里處理read事件
            if (n == 0) {
                close(sockfd);
                fds[i].fd = -1;
            }
         } else {
             // 這里處理write事件     
         }
         if (--nfds <= 0) {
            break;       
         }   
      }
    }
  }

poll缺點(diǎn)

它沒(méi)有最大連接數(shù)的限制，原因是它是基于鏈表來(lái)存儲(chǔ)的信认，但是同樣有缺點(diǎn)：

• 每次調(diào)用 poll 材义，都需要把 fd 集合從用戶(hù)態(tài)拷貝到內(nèi)核態(tài)，這個(gè)開(kāi)銷(xiāo)在 fd 很多時(shí)會(huì)很大嫁赏；
• 對(duì) socket 掃描是線(xiàn)性?huà)呙杵涞啵捎幂喸?xún)的方法，效率較低（高并發(fā)時(shí)）

epoll

epoll可以理解為event poll潦蝇，不同于忙輪詢(xún)和無(wú)差別輪詢(xún)款熬，epoll會(huì)把哪個(gè)流發(fā)生了怎樣的I/O事件通知我們。所以我們說(shuō)epoll實(shí)際上是事件驅(qū)動(dòng)（每個(gè)事件關(guān)聯(lián)上fd）的攘乒，此時(shí)我們對(duì)這些流的操作都是有意義的贤牛。（復(fù)雜度降低到了O(1)）

epoll函數(shù)接口

當(dāng)某一進(jìn)程調(diào)用epoll_create方法時(shí)，Linux內(nèi)核會(huì)創(chuàng)建一個(gè)eventpoll結(jié)構(gòu)體则酝，這個(gè)結(jié)構(gòu)體中有兩個(gè)成員與epoll的使用方式密切相關(guān)殉簸。eventpoll結(jié)構(gòu)體如下所示：

#include <sys/epoll.h>

// 數(shù)據(jù)結(jié)構(gòu)
// 每一個(gè)epoll對(duì)象都有一個(gè)獨(dú)立的eventpoll結(jié)構(gòu)體
// 用于存放通過(guò)epoll_ctl方法向epoll對(duì)象中添加進(jìn)來(lái)的事件
// epoll_wait檢查是否有事件發(fā)生時(shí)，只需要檢查eventpoll對(duì)象中的rdlist雙鏈表中是否有epitem元素即可
struct eventpoll {
    /*紅黑樹(shù)的根節(jié)點(diǎn)，這顆樹(shù)中存儲(chǔ)著所有添加到epoll中的需要監(jiān)控的事件*/
    struct rb_root  rbr;
    /*雙鏈表中則存放著將要通過(guò)epoll_wait返回給用戶(hù)的滿(mǎn)足條件的事件*/
    struct list_head rdlist;
};

// API
int epoll_create(int size); // 內(nèi)核中間加一個(gè) ep 對(duì)象般卑，把所有需要監(jiān)聽(tīng)的 socket 都放到 ep 對(duì)象中
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); // epoll_ctl 負(fù)責(zé)把 socket 增加武鲁、刪除到內(nèi)核紅黑樹(shù)
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);// epoll_wait 負(fù)責(zé)檢測(cè)可讀隊(duì)列，沒(méi)有可讀 socket 則阻塞進(jìn)程

每一個(gè)epoll對(duì)象都有一個(gè)獨(dú)立的eventpoll結(jié)構(gòu)體蝠检，用于存放通過(guò)epoll_ctl方法向epoll對(duì)象中添加進(jìn)來(lái)的事件沐鼠。這些事件都會(huì)掛載在紅黑樹(shù)中，如此叹谁，重復(fù)添加的事件就可以通過(guò)紅黑樹(shù)而高效的識(shí)別出來(lái)(紅黑樹(shù)的插入時(shí)間效率是lgn饲梭，其中n為紅黑樹(shù)元素個(gè)數(shù))。

而所有添加到epoll中的事件都會(huì)與設(shè)備(網(wǎng)卡)驅(qū)動(dòng)程序建立回調(diào)關(guān)系本慕，也就是說(shuō)排拷，當(dāng)相應(yīng)的事件發(fā)生時(shí)會(huì)調(diào)用這個(gè)回調(diào)方法。這個(gè)回調(diào)方法在內(nèi)核中叫ep_poll_callback,它會(huì)將發(fā)生的事件添加到rdlist雙鏈表中锅尘。

在epoll中监氢，對(duì)于每一個(gè)事件，都會(huì)建立一個(gè)epitem結(jié)構(gòu)體藤违，如下所示：

struct epitem{
    struct rb_node  rbn;//紅黑樹(shù)節(jié)點(diǎn)
    struct list_head    rdllink;//雙向鏈表節(jié)點(diǎn)
    struct epoll_filefd  ffd;  //事件句柄信息
    struct eventpoll *ep;    //指向其所屬的eventpoll對(duì)象
    struct epoll_event event; //期待發(fā)生的事件類(lèi)型
}

當(dāng)調(diào)用epoll_wait檢查是否有事件發(fā)生時(shí)浪腐，只需要檢查eventpoll對(duì)象中的rdlist雙鏈表中是否有epitem元素即可。如果rdlist不為空顿乒，則把發(fā)生的事件復(fù)制到用戶(hù)態(tài)议街，同時(shí)將事件數(shù)量返回給用戶(hù)。

image.png

• 第一步：epoll_create()系統(tǒng)調(diào)用搓蚪。此調(diào)用返回一個(gè)句柄蛤售，之后所有的使用都依靠這個(gè)句柄來(lái)標(biāo)識(shí)。
• 第二步：epoll_ctl()系統(tǒng)調(diào)用妒潭。通過(guò)此調(diào)用向epoll對(duì)象中添加悴能、刪除、修改感興趣的事件雳灾，返回0標(biāo)識(shí)成功漠酿，返回-1表示失敗。
• 第三部：epoll_wait()系統(tǒng)調(diào)用谎亩。通過(guò)此調(diào)用收集收集在epoll監(jiān)控中已經(jīng)發(fā)生的事件记靡。

epoll使用示例

int main(int argc, char* argv[])
{
   /*
   * 在這里進(jìn)行一些初始化的操作谈竿，
   * 比如初始化數(shù)據(jù)和socket等。
   */

    // 內(nèi)核中創(chuàng)建ep對(duì)象
    epfd=epoll_create(256);
    // 需要監(jiān)聽(tīng)的socket放到ep中
    epoll_ctl(epfd,EPOLL_CTL_ADD,listenfd,&ev);
 
    while(1) {
      // 阻塞獲取
      nfds = epoll_wait(epfd,events,20,0);
      for(i=0;i<nfds;++i) {
          if(events[i].data.fd==listenfd) {
              // 這里處理accept事件
              connfd = accept(listenfd);
              // 接收新連接寫(xiě)到內(nèi)核對(duì)象中
              epoll_ctl(epfd,EPOLL_CTL_ADD,connfd,&ev);
          } else if (events[i].events&EPOLLIN) {
              // 這里處理read事件
              read(sockfd, BUF, MAXLINE);
              //讀完后準(zhǔn)備寫(xiě)
              epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd,&ev);
          } else if(events[i].events&EPOLLOUT) {
              // 這里處理write事件
              write(sockfd, BUF, n);
              //寫(xiě)完后準(zhǔn)備讀
              epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd,&ev);
          }
      }
    }
    return 0;
}

epoll的優(yōu)點(diǎn)

• 沒(méi)有最大并發(fā)連接的限制摸吠，能打開(kāi)的FD的上限遠(yuǎn)大于1024（1G的內(nèi)存上能監(jiān)聽(tīng)約10萬(wàn)個(gè)端口）；
• 效率提升嚎花，不是輪詢(xún)的方式寸痢，不會(huì)隨著FD數(shù)目的增加效率下降。只有活躍可用的FD才會(huì)調(diào)用callback函數(shù)紊选；即Epoll最大的優(yōu)點(diǎn)就在于它只管你“活躍”的連接啼止，而跟連接總數(shù)無(wú)關(guān)，因此在實(shí)際的網(wǎng)絡(luò)環(huán)境中兵罢，Epoll的效率就會(huì)遠(yuǎn)遠(yuǎn)高于select和poll献烦；
• 內(nèi)存拷貝，利用mmap()文件映射內(nèi)存加速與內(nèi)核空間的消息傳遞卖词；即epoll使用mmap減少?gòu)?fù)制開(kāi)銷(xiāo)巩那。

epoll缺點(diǎn)

• epoll只能工作在 linux 下

epoll LT 與 ET 模式的區(qū)別

epoll 有 EPOLLLT 和 EPOLLET 兩種觸發(fā)模式，LT 是默認(rèn)的模式此蜈，ET 是 “高速” 模式即横。

• LT 模式下，只要這個(gè) fd 還有數(shù)據(jù)可讀裆赵，每次 epoll_wait 都會(huì)返回它的事件东囚，提醒用戶(hù)程序去操作；
• ET 模式下战授，它只會(huì)提示一次页藻，直到下次再有數(shù)據(jù)流入之前都不會(huì)再提示了，無(wú)論 fd 中是否還有數(shù)據(jù)可讀植兰。所以在 ET 模式下份帐，read 一個(gè) fd 的時(shí)候一定要把它的 buffer 讀完，或者遇到 EAGIN 錯(cuò)誤钉跷。

epoll使用“事件”的就緒通知方式弥鹦，通過(guò)epoll_ctl注冊(cè)fd，一旦該fd就緒爷辙，內(nèi)核就會(huì)采用類(lèi)似callback的回調(diào)機(jī)制來(lái)激活該fd彬坏，epoll_wait便可以收到通知。

select/poll/epoll之間的區(qū)別

select膝晾，poll栓始，epoll都是IO多路復(fù)用的機(jī)制。I/O多路復(fù)用就通過(guò)一種機(jī)制血当，可以監(jiān)視多個(gè)描述符幻赚，一旦某個(gè)描述符就緒（一般是讀就緒或者寫(xiě)就緒）禀忆，能夠通知程序進(jìn)行相應(yīng)的讀寫(xiě)操作。但select落恼，poll箩退，epoll本質(zhì)上都是同步I/O，因?yàn)樗麄兌夹枰谧x寫(xiě)事件就緒后自己負(fù)責(zé)進(jìn)行讀寫(xiě)佳谦，也就是說(shuō)這個(gè)讀寫(xiě)過(guò)程是阻塞的戴涝，而異步I/O則無(wú)需自己負(fù)責(zé)進(jìn)行讀寫(xiě)，異步I/O的實(shí)現(xiàn)會(huì)負(fù)責(zé)把數(shù)據(jù)從內(nèi)核拷貝到用戶(hù)空間钻蔑。

epoll跟select都能提供多路I/O復(fù)用的解決方案啥刻。在現(xiàn)在的Linux內(nèi)核里有都能夠支持，其中epoll是Linux所特有咪笑，而select則應(yīng)該是POSIX所規(guī)定可帽，一般操作系統(tǒng)均有實(shí)現(xiàn)

epoll是Linux目前大規(guī)模網(wǎng)絡(luò)并發(fā)程序開(kāi)發(fā)的首選模型。在絕大多數(shù)情況下性能遠(yuǎn)超select和poll路鹰。目前流行的高性能web服務(wù)器Nginx正式依賴(lài)于epoll提供的高效網(wǎng)絡(luò)套接字輪詢(xún)服務(wù)贷洲。但是，在并發(fā)連接不高的情況下晋柱，多線(xiàn)程+阻塞I/O方式可能性能更好优构。

支持一個(gè)進(jìn)程所能打開(kāi)的最大連接數(shù)

• select：?jiǎn)蝹€(gè)進(jìn)程所能打開(kāi)的最大連接數(shù)有FD_SETSIZE宏定義，其大小是32個(gè)整數(shù)的大醒憔骸（在32位的機(jī)器上钦椭，大小就是32_32，同理64位機(jī)器上FD_SETSIZE為32_64）碑诉，當(dāng)然我們可以對(duì)進(jìn)行修改彪腔，然后重新編譯內(nèi)核，但是性能可能會(huì)受到影響进栽，這需要進(jìn)一步的測(cè)試德挣。
• poll：poll本質(zhì)上和select沒(méi)有區(qū)別，但是它沒(méi)有最大連接數(shù)的限制快毛，原因是它是基于鏈表來(lái)存儲(chǔ)的格嗅。
• epoll：雖然連接數(shù)有上限番挺，但是很大，1G內(nèi)存的機(jī)器上可以打開(kāi)10萬(wàn)左右的連接屯掖，2G內(nèi)存的機(jī)器可以打開(kāi)20萬(wàn)左右的連接玄柏。

FD劇增后帶來(lái)的IO效率問(wèn)題

• select：因?yàn)槊看握{(diào)用時(shí)都會(huì)對(duì)連接進(jìn)行線(xiàn)性遍歷，所以隨著FD的增加會(huì)造成遍歷速度慢的“線(xiàn)性下降性能問(wèn)題”贴铜。
• poll：同上
• epoll：因?yàn)閑poll內(nèi)核中實(shí)現(xiàn)是根據(jù)每個(gè)fd上的callback函數(shù)來(lái)實(shí)現(xiàn)的禁荸，只有活躍的socket才會(huì)主動(dòng)調(diào)用callback，所以在活躍socket較少的情況下阀湿，使用epoll沒(méi)有前面兩者的線(xiàn)性下降的性能問(wèn)題，但是所有socket都很活躍的情況下瑰妄，可能會(huì)有性能問(wèn)題陷嘴。

消息傳遞方式

• select：內(nèi)核需要將消息傳遞到用戶(hù)空間，都需要內(nèi)核拷貝動(dòng)作
• poll：同上
• epoll：epoll通過(guò)內(nèi)核和用戶(hù)空間共享一塊內(nèi)存來(lái)實(shí)現(xiàn)的间坐。

總結(jié)

select灾挨，poll實(shí)現(xiàn)需要自己不斷輪詢(xún)所有fd集合，直到設(shè)備就緒竹宋，期間可能要睡眠和喚醒多次交替劳澄。而epoll其實(shí)也需要調(diào)用epoll_wait不斷輪詢(xún)就緒鏈表，期間也可能多次睡眠和喚醒交替蜈七，但是它是設(shè)備就緒時(shí)秒拔，調(diào)用回調(diào)函數(shù)，把就緒fd放入就緒鏈表中飒硅，并喚醒在epoll_wait中進(jìn)入睡眠的進(jìn)程砂缩。雖然都要睡眠和交替，但是select和poll在“醒著”的時(shí)候要遍歷整個(gè)fd集合三娩，而epoll在“醒著”的時(shí)候只要判斷一下就緒鏈表是否為空就行了庵芭，這節(jié)省了大量的CPU時(shí)間。這就是回調(diào)機(jī)制帶來(lái)的性能提升雀监。

select双吆，poll每次調(diào)用都要把fd集合從用戶(hù)態(tài)往內(nèi)核態(tài)拷貝一次，并且要把current往設(shè)備等待隊(duì)列中掛一次会前，而epoll只要一次拷貝好乐，而且把current往等待隊(duì)列上掛也只掛一次（在epoll_wait的開(kāi)始，注意這里的等待隊(duì)列并不是設(shè)備等待隊(duì)列回官，只是一個(gè)epoll內(nèi)部定義的等待隊(duì)列）曹宴。這也能節(jié)省不少的開(kāi)銷(xiāo)。

高頻面試題

什么是IO多路復(fù)用?

看完上面的文章歉提，相信你可以回答出來(lái)了笛坦。

nginx/redis 所使用的IO模型是什么区转？

Nginx的IO模型

Nginx 支持多種并發(fā)模型，并發(fā)模型的具體實(shí)現(xiàn)根據(jù)系統(tǒng)平臺(tái)而有所不同版扩。

在支持多種并發(fā)模型的平臺(tái)上废离，nginx 自動(dòng)選擇最高效的模型。但我們也可以使用 use 指令在配置文件中顯式地定義某個(gè)并發(fā)模型礁芦。

NGINX中支持的并發(fā)模型：

1蜻韭、select

IO多路復(fù)用、標(biāo)準(zhǔn)并發(fā)模型柿扣。在編譯 nginx 時(shí)肖方，如果所使用的系統(tǒng)平臺(tái)沒(méi)有更高效的并發(fā)模型，select 模塊將被自動(dòng)編譯未状。configure 腳本的選項(xiàng)：–with-select_module 和 --without-select_module 可被用來(lái)強(qiáng)制性地開(kāi)啟或禁止 select 模塊的編譯

2俯画、poll

IO多路復(fù)用、標(biāo)準(zhǔn)并發(fā)模型司草。與 select 類(lèi)似艰垂，在編譯 nginx 時(shí)，如果所使用的系統(tǒng)平臺(tái)沒(méi)有更高效的并發(fā)模型埋虹，poll 模塊將被自動(dòng)編譯猜憎。configure 腳本的選項(xiàng)：–with-poll_module 和 --without-poll_module 可用于強(qiáng)制性地開(kāi)啟或禁止 poll 模塊的編譯

3、epoll

IO多路復(fù)用搔课、高效并發(fā)模型胰柑，可在 Linux 2.6+ 及以上內(nèi)核可以使用

4、kqueue

IO多路復(fù)用辣辫、高效并發(fā)模型旦事，可在 FreeBSD 4.1+, OpenBSD 2.9+, NetBSD 2.0, and Mac OS X 平臺(tái)中使用

5、/dev/poll

高效并發(fā)模型急灭，可在 Solaris 7 11/99+, HP/UX 11.22+ (eventport), IRIX 6.5.15+, and Tru64 UNIX 5.1A+ 平臺(tái)使用

6姐浮、eventport

高效并發(fā)模型，可用于 Solaris 10 平臺(tái)葬馋，PS：由于一些已知的問(wèn)題卖鲤，建議 使用/dev/poll替代。

Redis IO多路復(fù)用技術(shù)

redis 是一個(gè)單線(xiàn)程卻性能非常好的內(nèi)存數(shù)據(jù)庫(kù)畴嘶， 主要用來(lái)作為緩存系統(tǒng)蛋逾。 redis 采用網(wǎng)絡(luò)IO多路復(fù)用技術(shù)來(lái)保證在多連接的時(shí)候， 系統(tǒng)的高吞吐量窗悯。

為什么 Redis 中要使用 I/O 多路復(fù)用這種技術(shù)呢区匣？

首先，Redis 是跑在單線(xiàn)程中的蒋院，所有的操作都是按照順序線(xiàn)性執(zhí)行的亏钩，但是由于讀寫(xiě)操作等待用戶(hù)輸入或輸出都是阻塞的莲绰，所以 I/O 操作在一般情況下往往不能直接返回，這會(huì)導(dǎo)致某一文件的 I/O 阻塞導(dǎo)致整個(gè)進(jìn)程無(wú)法對(duì)其它客戶(hù)提供服務(wù)姑丑，而 I/O 多路復(fù)用 就是為了解決這個(gè)問(wèn)題而出現(xiàn)的蛤签。

redis的io模型主要是基于epoll實(shí)現(xiàn)的，不過(guò)它也提供了 select和kqueue的實(shí)現(xiàn)栅哀，默認(rèn)采用epoll震肮。

select、poll留拾、epoll之間的區(qū)別

看完上面的文章戳晌，相信你可以回答出來(lái)了。

epoll 水平觸發(fā)（LT）與 邊緣觸發(fā)（ET）的區(qū)別痴柔？

EPOLL事件有兩種模型：

• Edge Triggered (ET) 邊緣觸發(fā)只有數(shù)據(jù)到來(lái),才觸發(fā),不管緩存區(qū)中是否還有數(shù)據(jù)躬厌。
• Level Triggered (LT) 水平觸發(fā)只要有數(shù)據(jù)都會(huì)觸發(fā)。

看完上面的文章竞帽，相信你可以回答出來(lái)了。

文章持續(xù)更新鸿捧，可以公眾號(hào)搜一搜「 一角錢(qián)技術(shù) 」第一時(shí)間閱讀屹篓，本文 GitHub org_hejianhui/JavaStudy 已經(jīng)收錄，歡迎 Star匙奴。