专栏首页立权的博客select,poll,epoll,IO多路复用进化史

select,poll,epoll,IO多路复用进化史

  IO多路复用中的 “多路” 指的是同时监听多个打开文件(socket或者其他文件设备),“复用” 指的是复用一个 进程/线程 去监听这些打开文件

1.最早期的select

  伪代码表示:

    while (true) {
        for (fd : 监听的fd) {
          if (poll(设备)){
          返回就绪数 + 1;
               break;
          }
        }
     
           if (返回就绪数 > 0) {
         free_wait();
               break;
           } else {
            sleep();
          }
    }

free_wait 是从所有设备的等待队列中移除当前进程,在等待队列中的每个节点是 wait_queue_t 结构体的内存实例

当 设备就绪的时候,对设备的 poll 函数调用 会返回 true

假如要监听的文件数是 N,那么每次都要去都要去轮询所有的 设备,而不是轮询到一个就绪就停下来,因为要去计数有多少个就绪了

在就绪数量 > 0 的时候,又要调用 free_wait 去遍历所有要监听文件的 等待队列,如此一来,并且下一次调用 select 的时候,也要重复上述流程。

导致 select 每次调用的 时间复杂度是 O(N)

2. poll

  poll 和 select 一样,也是去轮询,时间复杂度也是 O (N) , 但是 poll 的监听对象不是用数组存储的,而是以链表存储的,一般select只支持监听 1024 个打开文件

  但是 poll 只要内存充足,就能监听远不止 1024 个打开文件

3. epoll

  select 和 poll 之所以低效,是因为每次的轮询,轮询到的大部分打开文件,可能都是未就绪状态

epoll 做的优化思路清晰,只把就绪的打开文件返回给 用户空间。具体的做法是 通过 epoll_create 创建 epollevent ,epollevent 内维护两个重要的数据结构:

  1.一颗便于查找的红黑树,红黑树的节点是待监听的打开文件号 + 待监听事件(其他内容省略)(rbr)

  2.一条便于增删改的双向链表,节点和上面一样,是打开文件号 + 待监听事件(其他内容省略),代表就绪的打开文件号 (rdlist)

  通过 epoll_ctl 添加 打开文件号 + 待监听事件 的时候,会把打开文件号 + 待监听事件打包成一个节点(epoll_item), 并且加入到上述的红黑树 和 双向链表中

  同时 创建一个 epoll_entry ,这种数据结构中有成员 wait_queue_t , wait_queue_t 就是设备的等待队列上节点的类型

  把epoll_entry 的 wait_queue_t 做为一个节点链入到 设备的等待队列中去,并且设置回调函数

  等待设备就绪的时候,驱动程序会清空等待队列,清空的方法是把等待队列的节点移除并且调用节点的回调函数

  这里的回调函数是直接唤醒 epollevent 的 wq 上等待的进程,调用 epoll_wait 的进程会被加入到 wq 上

  最后,就是调用 epoll_wait 等待打开文件就绪

  值得提问的是,是不是每次一个设备就绪,就唤醒进程,那不是经常因为一个设备就被唤醒?确实可能,但是在唤醒期间,如果有多个其他设备就绪,他们也会把自己的打开文件号放到 rdlist 上

  那不会出现并发冲突吗?比如进程刚好被唤醒去拿 就绪队列上的节点,复制到自己传入的参数events数组(存储就绪的文件打开号和事件)上,并且清空就绪队列,这时候其他就绪设备把自己挂到就绪队列了怎么办?

  复制 - 清空 的过程有 eventpoll 的 mutex 互斥量 保证并发安全,不用担心。

  如果正好 复制 - 清空的时候,有新的就绪设备要将自己挂到就绪队列的话,没挂上就被阻塞。等待复制-清空完成再把自己挂上去。

  下一次 epoll_wait 的时候,因为就绪队列上有节点,所以直接 复制-清空 后返回,不阻塞

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 简记 ARP 和 ARP攻击

    IP地址为A , 硬件地址为a 的主机,找IP地址为 B 的主机( 硬件地址为b ),但是A的缓存表中没有特定条目,即没有 B - b 的缓存条目。

    执生
  • 重量级锁的加锁-等待-撤销流程

    1.entry_list 中的 节点是等待被唤醒的节点,持有重量级锁的线程执行 exit 方法(Java层面:退出上述 synchronized区或调用 wai...

    执生
  • Hotpot 年轻代GC 源代码分析

    图解分析:https://www.cnblogs.com/lqlqlq/p/13912325.html

    执生
  • 封装 axios 取消重复请求

    在我们web开发过程中,很多地方需要我们取消重复的请求。但是哪种场合需要我们取消呢?我们如何取消呢?带着这些问题我们阅读本文。

    coder_koala
  • Java 程序员眼里的 Linux 内核 —— wait_event 源码分析

    导读:文章内容较多,也有不少代码,但是作者写的也很认真,对理解并发编程会有帮助,值得一读。 阅读完大约需要15分钟,如果对 linux 实在不太感冒,也可以选择...

    程序亦非猿
  • Javascript面向对象编程(三):非构造函数的继承

    这个系列的第一部分介绍了"封装",第二部分介绍了使用构造函数实现"继承"。 今天是最后一个部分,介绍不使用构造函数实现"继承"。 一、什么是"非构造函数"的继承...

    ruanyf
  • 性能监控之Telegraf+InfluxDB+Grafana+Python实现Oracle实时监控

    通过查询 V$FIXED_TABLE ,可以列出所有可用的动态性能视图和动态性能表。

    高楼Zee
  • ES6之Object.assign()详解

    将 A 对象的属性复制给 B 对象,这是 JavaScript 编程中很常见的操作。这篇博客将介绍ES6的Object.assign()属性,可以用于对象复制。

    Fundebug
  • Android Service 系统服务

    android sdk 提供很多公用的服务,也就是系统服务,开发者可以通过Activity类的getSystemService方法获取指定的服务。系统服务包含音...

    水击三千
  • 函数重构之道

    以下代码做了好几件事情。它创建缓冲区、获取页面、搜索继承下来的页面、渲染路径、添加神秘的字符串、生产HTML等等。

    栋先生

扫码关注云+社区

领取腾讯云代金券