Daily Plan
更新: 5/31/2025 字数: 0 字 时长: 0 分钟
#todo
Daily Study
更新: 5/31/2025 字数: 0 字 时长: 0 分钟
关于select、poll、epoll
- 这三个是Linux中IO多路复用的三种实现，IO多路复用解决了阻塞IO和非阻塞IO中多次进程切换和单连接对单进程的问题
- 先大概说一下他们三者的区别。select和poll比较类似，不同的是select采用fd_set，一个1024或者2048位的bitmap来记录fd，这里限制了最大文件描述符的数量，poll在这里做了优化，变成了一个pollfd结构体，基于链表来实现，不会有数量问题。select和epoll的区别包括几个方面：
- select每次都会把fd_set从用户态拷贝到内核态，执行完之后需要把更新的fd_set拷贝到用户态，然后再遍历一遍fd_set来确认哪些socket就绪，epoll则只会在socket创建时，通过epoll_ctl连接到对应的event事件上，数据就绪时通过异步通知相应的进程接受数据。
- select有最大文件描述符限制，epoll没有。
- 具体介绍一下epoll。首先是epoll_event数据结构。使用一个红黑树来记录文件描述符（为什么用），一个进程等待队列（用来记录阻塞的用户程序），一个文件就绪队列（用来记录数据准备就绪的socket）。
- 然后是epoll过程的三个方法。epoll_create创建一个event对象，epoll_ctl把socket添加到对应的event对象上，epoll_wait监听socket的数据是否到达。
- epoll的关键在于其中的两个回调函数，当监听的socket有数据到达时，会通过回调函数epoll_callback找到event红黑树中对应的socket节点，然后把他加入到event的socket就绪队列中，然后再通过回调函数wake唤醒阻塞队列中对应的用户进程，并把就绪队列传递给用户进程进行数据的读取。
延伸问题1：为什么用红黑树不用hash表（需要从具体问题的场景出发） 答案：主要问题在于hash表的增删上，由于hash表内部存在一套扩容/缩容机制，可能会导致在某一次增删文件符操作后，导致相比其他之前操作内存突增，然后影响空间和时间开销。而红黑树的增删操作则更为时空更为平均，更加可控。 linux中的hash表，底层位hlist，采用拉链法来解决哈希碰撞，查找复杂度为O(1)，具体来说是通过哈希映射到每个桶，并通过负载因子a来约束元素大小
延伸问题2：为什么用红黑树不用b+树 首先明白epoll数据结构设计的目的：快速的增删改查，低延迟（不能有额外的磁盘IO或大块内存移动），内存中纯CPU操作（关注CPU缓存命中和指针开销） 答案：根据epoll的设计来看，首先是增删改查主要针对单节点，并不涉及到范围查询，B+树更适合范围查询。然后是关于内存开销，红黑树一个节点只需要父指针左右指针和一个颜色标记，而B+树的设计是以页为单位，每个节点一般为一个页大小。
Daily Problem
更新: 5/31/2025 字数: 0 字 时长: 0 分钟