在找工作时，经常被面试官问起网络IO五种模型、同步异步、阻塞非阻塞之类的问题，尤其是字节跳动面试时被当做一道大题进行了次全面的分析。但是我始终没有彻底的研究过，由于疫情影响不得不宅在家里，在学习时无意想起这个知识点，便深入的学习整理了一下。

因将要使用Linux开发，故这里所说的为Linux下在进行网络通信时，常用的IO模型。

写在前面

IO过程分为两个步骤

1. 内核准备好数据
2. 应用程序从内核空间将数据复制到用户空间

根据网络检索的POSIX定义，同步异步的区别在于第二个步骤是否由应用程序完成。在我自己个人看来，同步异步的主要区别在于做这个IO的时机是否是应用程序可控的。

同步在我们平常的术语解释中一般应理解为做事情的先后顺序是有序可循的，而异步时并不能确定对方做某件事的时机。具体到linux下的网络IO模型中来，我认为第二个步骤是否由应用程序完成，就代表着应用程序是否能控制真正IO进行的时机，也就代表着应用程序的执行流程是否是可控的。

五种IO模型

阻塞

应用程序在进行阻塞IO时，程序暂停运行，等待内核将数据准备完毕并通知应用程序，应用程序唤醒并从内核将数据读取到用户空间。

程序停止运行，等待内核准备数据，所以叫做阻塞。应用程序自己控制数据从内核的读取，因此阻塞方式为同步的。

非阻塞

非阻塞IO模式时，应用程序会不停地去询问内核数据是否准备完成，类似轮询的方式。非阻塞应用程序在内核未准备完成数据时，会返回失败。当内核准备完成数据，应用程序再去询问时就会开始处理数据。

在非阻塞IO模型里，应用程序每次在询问之后，回去处理别的事情，程序不会阻塞在IO上， 因此是非阻塞的方式。同样在处理数据时是应用程序自行处理的，所以也为同步模型。

IO复用

IO复用这个概念用于解决单一进程处理多个文件描述符的情况，不单单可以解决网络IO复用的问题。

IO复用模型会同时监测多个文件描述符的IO请求。执行时会阻塞在这里，当任一文件描述符数据已准备好时，内核会通知应用程序，有应用程序来进行IO。

在IO复用相关函数执行时，应用程序不会执行其他的程序，因此IO复用模型是阻塞的。当数据准备好时，由应用程序来处理IO操作，这是整个程序也是阻塞到IO操作上，所以IO复用模型为同步模型。

信号驱动IO

信号是Linux系统处理突发事件的一种方式，我们可以通过设置信号处理函数来接收其他程序或系统发送的信号，我们当然也可以选择忽略。

信号驱动IO模型在设置了即将处理的信号的信号处理函数之后，就可以去做别的工作了。当内核准备好数据后，会使用信号的方式通知应用程序，应用程序便会启用信号处理函数来处理IO操作。

信号驱动方式在等待内核准备数据时可以去处理别的工作，因此信号驱动IO模式是非阻塞的。但是在收到内核发送的信号之后，IO操作仍然需要应用程序来完成，因此信号驱动IO模型任然为同步模型。

异步IO

应用程序使用异步IO相关的API时，会同时告知内核IO操作的目的缓存，将真正的IO操作也交给了内核。内核在完成数据准备和IO操作后，会发送信号告知应用程序。

因为应用程序不需要去做真正的IO，一切操作都交给了内核，因此为异步模型。

总结

上述五种IO模型为Linux下的IO模型，在《UNIX环境高级编程》这本书的6.2节有介绍。

其中前四种都为同步模型，其中既有阻塞模型也有非阻塞模型。只有异步IO模型为真正的异步模型。

同步和异步的区别就在于真正的IO由谁来完成。

一 关于AVL树,红黑树和B树的对比

• AVL树是比较原始的一个平衡树,它通过保证每个节点的两个子树的高度最多为1,来保证整棵树没有过于突出的树枝.在查找每个关键字的时候都不会有过慢的情况发生.它查找的时间复杂度是对数级的,可以实现较快的查找.

• 红黑树又叫做RB树,它也通过一些限制保证树的大致平衡.红黑树节点分为红色和黑色两类,红黑树要求根节点和叶子节点都必须为黑色节点,而且要求从根节点到每个叶子节点的路径上的黑色节点个数都是一样的,而且红色节点的子节点必须为黑色节点.通过着一系列的要求,就可以实现从根节点到某个叶子节点的长度不可能比到另一个叶子节点的长度的两倍还多,也就保证了整个树的大致稳定.红黑树给节点赋予了颜色,在插入或者删除节点的时候就不仅可以通过旋转,也可以通过改变颜色来保持树的平衡,这样就使得红黑树旋转的次数相对AVL树要少一些.但是红黑树因为要判断颜色,所以在操作上比AVL树要繁琐一些,所以感觉上他们在整体效率上差距并不是特别明显.通过我查阅的一些资料,发现确实是这样.红黑树现在应用非常的广泛,STL中就大量使用红黑树作为底层的实现.

• B树主要广泛应用于外设存储.AVL树和红黑树虽然查找速度很快,但因受限于每个节点只能有两个节点,当数据量上去的时候,查找起来就要从根节点向下找很多层.因内存速度较快,所以对数级的时间复杂度已经可以接受了,但是在磁盘中每向下搜索一层或几层就要从磁盘中读取,对于磁盘来说这个开销是非常大的.B树的出现正是由于这个背景,它虽然在其他方面可能较AVL和红黑树差一些,但是它可以很有效的减少磁盘读取的次数,因此得到了广泛的应用.

二 B树的限制条件

1. 设B树的度为m,则除了根节点外每个节点最少有m-1个关键字,最多有2m-1个关键字
2. 每个节点中关键字按照非降序存放
3. 每个关键字对其子树的关键字加以分割
4. 每个叶子节点具有相同的深度

下图为一个度为3的B树举例

一个树的性能主要由他的插入删除操作来决定的.

三 B树的插入

1. B树普通插入和红黑树插入类似,从根部一直比到叶子节点,找到想要插入的节点,如果节点没有满的话,就插入到合适位置,插入结束.
2. 如果节点数量满了的话,把中间值找出来,升入父节点,原节点拆分为两个节点,如果父节点未超过最大个数,插入结束.
3. 如果父节点插入后超过最大个数,则对父节点执行第二步,直至插入结束.

四 B树的删除

定义一个节点个数为m-1个时,称这个节点不丰满,否则定义为丰满.

1. 搜索要删除的节点,搜索过程中,对路径上经过的节点进行判断,如果丰满则继续,如果不丰满
   1. 判断其兄弟节点是否丰满,如果有丰满的,则兄弟节点把合适的节点传递给父节点,父节点再把合适的节点传递给当前节点,即完成了当前节点的丰满化.
   2. 如果兄弟节点中没有丰满的,则选择其中一个兄弟节点,把他们父节点相应的关键字拉下来,和他们合并成一个新节点,也完成了节点的丰满化.
2. 对关键字所在的节点也要进行丰满化,之后删除找到的节点,删除完成.

整个过程为我在读过了很多博客之后总结出来的算法,自己感觉比较简洁,如果有问题的话,欢迎指正.

一 accept函数原型

1
2
3
4

#include <sys/types.h>          /* See NOTES */
#include <sys/socket.h>

int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);

二 accept函数参数分析

• sockfd参数是创建的socket的描述符,用来唯一表示一个socket.传入的socket必须是监听socket,这个参数较为简单,一般不会出错.

• addr参数需注意是sockaddr结构体的指针,因历史原因,它仍然使用sockaddr结构体.现在较为常用的是sockaddr_in结构体,因为sockaddr_in能提供端口和ip的成员变量,在使用这个函数时应注意把sockaddr_in结构体的指针强制转换成sockaddr类型的指针.

• addrlen参数较为容易出错,它是一个value-result参数,所以它不单单用来接收收到的addr结构体的大小,还要穿入一个值,在man手册中查到:

  The addrlen argument is a value-result argument: the caller must initialize it to contain the size (in bytes) of the structure pointed to by addr; on return it will contain the actual size of the peer address.

也就是说在调用函数之前,需要传入大于sockaddr结构体大小的值,这样才能正常获取请求连接的信息.