#### 前言
本部分主要说明一些计算机OS相关基础知识，后续会不断补充。文中部分内容可能来源于其他文章，所以你也可以参考文末的参考资料。

#### 1.进程 vs 线程
可以参考[进程与线程的一个简单解释](http://www.ruanyifeng.com/blog/2013/04/processes_and_threads.html),总结起来就是下面的内容:

(1)**地址空间和其它资源**:进程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见。

(2)**通信**:进程间通信IPC，线程间可以直接读写进程数据段（如`全局变量`）来进行通信。但是需要借助于互斥锁或者型号量以保证数据的一致性。

(3)**调度和切换**：线程上下文切换比进程上下文切换要快得多(因为线程不拥有系统资源)。

(4)进程是**系统**进行资源分配和调度的一个独立单位。线程是进程的一个实体,是**CPU**调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如**程序计数器,一组寄存器和栈**),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。

#### 2.进程同步与互斥的区别
互斥:是指**某一资源**同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

简单地说：同步体现的是一种协作性，互斥体现的是一种排他性。

#### 3.进程间的通信方式有哪些？
管道(pipe)：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有**亲缘关系**的进程间使用。进程的亲缘关系通常是指父子进程关系。

有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它**允许无亲缘关系**进程间的通信。

信号量(semophore) ： 信号量是一个计数器，可以用来**控制多个进程对共享资源的访问**。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为`进程间`以及`同一进程内不同线程之间`的同步手段。

消息队列(message queue) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

信号 (sinal) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

共享内存(shared memory) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但**多个进程都可以访问**。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

套接字( socket) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于**不同机器间**的进程通信。

#### 4.作业（或进程）的调度算法有哪些？
- 先来先服务（FCFS，First-Come-First-Served）: 
  此算法的原则是按照作业到达**后备作业队列**（或进程进入就绪队列）的先后次序来选择作业（或进程）。

- 短作业优先（SJF,Shortest Process Next）
  这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。

- 时间片轮转调度算法（RR，Round-Robin）
  当某个进程执行的**时间片**用完时，调度程序便停止该进程的执行，并将它送**就绪队列**的末尾，**等待分配下一时间片**再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。

- 高响应比优先（HRRN，Highest Response Ratio Next）:
  按照高响应比（（已等待时间＋要求运行时间）/ 要求运行时间 = 1+(已等待时间/要求运行时间)）优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行。

- 优先权(Priority)调度算法
  按照进程的优先权大小来调度，使**高优先权**进程得到优先处理的调度策略称为优先权调度算法。

- 多级队列调度算法
  多队列调度是根据作业的**性质**和**类型**的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法

#### 5.死锁产生的原因，死锁产生的必要条件是什么，如何预防死锁，如何避免死锁，死锁定理？
**死锁产生的原因**：
<pre>
1.竞争资源
2.进程推进顺序不当    
</pre>

**死锁产生的必要条件**：
<pre>
互斥条件：一个资源一次只能被一个进程所使用，即是排它性使用。
不剥夺条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。
请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。
环路等待条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。
</pre>
**预防死锁**：

破坏四个必要条件之一。

死锁的避免：银行家算法，该方法允许**进程动态地申请资源**，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。

**死锁定理**：S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的，该充分条件称为死锁定理。

**死锁的解除**：

方法1：**强制性**地从系统中**撤消**一个或多个死锁的进程以断开循环等待链，并收回分配给终止进程的全部资源供剩下的进程使用。

方法2：使用一个有效的挂起和解除机构来**挂起**一些死锁的进程，其实质是从被挂起的进程那里抢占资源以解除死锁。


#### 6.分段式存储管理、分页式存储管理，两个的区别？
分页式存储管理：分页存储管理是将一个进程的地址（**逻辑地址空间**）空间划分成若干个大小相等的区域，称为页，相应地，将内存空间划分成与页相同大小（为了保证页内偏移一致）的若干个物理块，称为块或页框（页架）。在为进程分配内存时，将进程中的若干页分别装入多个**不相邻接**的块中。

分段式存储管理：在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是**一组完整的逻辑信息**，如有主程序段、子程序段、数据段及堆栈段等，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。

两者的区别：

页是信息的物理单位，分页是为了`实现非连续的分配，以便解决内存的碎片问题`，或者说分页是为了由于系统管理的需要。

页的大小固定是由系统确定的，`将逻辑地址划分为页号和页内地址是由机器硬件实现的`。而段的长度是不固定的，决定于用户的程序长度，通常由编译程序进行编译时根据信息的性质来划分。分页式存储管理的作业地址空间是一维的，分段式的存储管理的作业管理地址空间是`二维`的。

#### 7.页面置换算法有哪些？
(1)最佳置换算法（Optimal）：即选择那些`永不使用`的，或者是在`最长时间内`不再被访问的页面置换出去。（它是一种理想化的算法，性能最好，但在实际上难于实现）。

(2)先进先出置换算法FIFO：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

(3)最近最久未使用置换算法LRU（Least Recently Used）：该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。

(4)Clock置换算法：也叫`最近未用算法NRU（Not RecentlyUsed）`。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置“1”。在选择一页淘汰时，就检查其访问位，如果是“0”，就选择该页换出；若为“1”，则重新置为“0”，暂不换出该页，在循环队列中检查下一个页面，直到访问位为“0”的页面为止。由于该算法`只有一位访问位`，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，所以把该算法称为最近未用算法。最少使用置换算法LFU：该算法选择最近时期使用最少的页面作为淘汰页

#### 8.文件描述符？
**内核（kernel）**利用[文件描述符](http://blog.csdn.net/captain_mxd/article/details/52153233)（file descriptor）来访问文件。文件描述符是`非负整数`。打开现存文件或新建文件时，内核会返回一个文件描述符。读写文件也需要使用文件描述符来指定待读写的文件。

实际上，文件描述符是一个索引值，指向内核为每一个**进程**所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于\*nix这样的操作系统。

![](./images/inode.png)

在Linux系统中一切皆可以看成是文件，文件又可分为：普通文件、目录文件、链接文件和设备文件。文件描述符（file descriptor）是内核为了`高效管理已被打开的文件所创建的索引`，其是一个非负整数（通常是小整数），用于指代被打开的文件，所有执行I/O操作的系统调用都通过文件描述符。程序刚刚启动的时候，0是标准输入，1是标准输出，2是标准错误。如果此时去打开一个新的文件，它的文件描述符会是3。POSIX标准要求每次打开文件时（含socket）必须使用当前进程中最小可用的文件描述符号码。

每一个文件描述符会与一个打开文件相对应，同时，`不同的文件描述符也会指向同一个文件`。相同的文件可以被不同的进程打开`也可以在同一个进程中被多次打开`。系统为每一个进程维护了一个文件描述符表，该表的值都是从0开始的，所以在不同的进程中你会看到相同的文件描述符，这种情况下相同文件描述符有可能指向同一个文件，也有可能指向不同的文件。

#### 9.[网络IO模型：同步IO和异步IO，阻塞IO和非阻塞IO](https://www.cnblogs.com/Forever-Kenlen-Ja/p/4480718.html)
##### 9.1 recvfrom函数

[recvfrom](https://baike.baidu.com/item/recvfrom/4459985?fr=aladdin)用来接收远程主机经`指定的socket`传来的数据,并把数据传到由参数buf指向的内存空间,参数len为可接收数据的最大长度。参数flags一般设0,其他数值定义参考recv()。参数from用来指定欲传送的网络地址,结构sockaddr请参考bind()函数，参数fromlen为sockaddr的结构长度。
```c
ssize_t recvfrom(int sockfd,void *buf,size_t len,unsigned int flags, struct sockaddr *from,socket_t *fromlen)
```

##### 9.2 recv函数
[recv()](https://baike.baidu.com/item/recv%28%29/10082153?fr=aladdin&fromid=17200658&fromtitle=recv)
这里只描述**同步Socket**的recv函数的执行流程。
```c
int recv( _In_ SOCKET s, _Out_ char *buf, _In_ int len, _In_ int flags);
// 发送缓冲区 vs 接受缓冲区
```
当应用程序调用recv函数时：

（1）recv先`等待`s的发送缓冲中的数据被协议传送完毕，如果协议在传送s的发送缓冲中的数据时出现网络错误，那么recv函数返回**SOCKET_ERROR**。

（2）如果s的发送缓冲中`没有数据`或者`数据被协议成功发送完毕后`，recv先检查套接字s的接收缓冲区，如果s接收缓冲区中没有数据或者协议正在接收数据，那么recv就一直等待，直到协议把数据接收完毕。当协议把数据接收完毕，recv函数就把s的接收缓冲中的数据`copy到buf中`（注意协议接收到的数据可能大于buf的长度，所以在这种情况下要调用几次recv函数才能把s的接收缓冲中的数据copy完。recv函数仅仅是copy数据，真正的接收数据是协议来完成的）。

recv函数返回其实际copy的字节数。如果recv在copy时出错，那么它返回**SOCKET_ERROR**;如果recv函数在等待协议接收数据时网络中断了，那么它返回0。

注意：在Unix系统下，如果recv函数在等待协议接收数据时网络断开了，那么调用recv的进程会接收到一个SIGPIPE信号，进程对该信号的默认处理是进程终止。


##### 9.3 select函数
##### 9.3.1 select函数简介
select是一个计算机函数，位于头文件#include <sys/select.h>。该函数用于监视**文件描述符**的变化情况——读写或是异常。
```c
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, 
    struct timeval *timeout) 
//一个指向timeval结构的指针，用于决定select等待I/o的最长时间。如果为空将一直等待
```
 这里，fd_set 类型可以简单的理解为**按bit位标记句柄的队列**，例如要在某fd_set 中标记一个值为16的句柄，则该fd_set的第16个bit位被标记为1。具体的置位、验证可使用FD_SET、FD_ISSET等宏实现。在select()函数中，readfds、writefds和exceptfds`同时作为输入参数和输出参数`。如果输入的readfds标记了16号句柄，则select()将检测16号句柄是否可读。在select()返回后，可以通过检查readfds有否标记16号句柄，来判断该“可读”事件是否发生。另外，用户可以设置timeout时间。

 Select在Socket编程中还是比较重要的，可是对于初学Socket的人来说都不太爱用Select写程序，他们只是习惯写诸如`connect、accept、recv或recvfrom`这样的阻塞程序（所谓阻塞方式block，顾名思义，就是进程或是线程执行到这些函数时必须等待某个事件的发生，如果事件没有发生，进程或线程就被阻塞，**函数不能立即返回**）。可是使用Select就可以完成`非阻塞`（所谓非阻塞方式non-block，就是进程或线程执行此函数时不必非要等待事件的发生，一旦执行肯定返回，`以返回值的不同来反映函数的执行情况`，如果事件发生则与阻塞方式相同(从内核copy数据到用户进程)，若事件没有发生则返回一个代码来告知事件未发生，而进程或线程继续执行，所以效率较高方式工作的程序，它能够监视我们需要监视的文件描述符的变化情况——读写或是异常。

##### 9.3.2 select函数原理
在Linux中，我们可以使用select函数实现I/O端口的复用，传递给select函数的参数会告诉内核：
<pre>
•我们所关心的文件描述符
•对每个描述符，我们所关心的状态。(读/写/异常)
•我们要等待多长时间。(我们可以等待无限长的时间，等待固定的一段时间，或者根本就不等待)
</pre>
**每次**select函数返回后，内核告诉我们一下信息：
<pre>
•对我们的要求已经做好准备的描述符的个数
•对于三种条件哪些描述符已经做好准备.(读/写/异常)
</pre>
有了这些返回信息，我们可以调用合适的I/O函数(通常是read或write)，并且这些函数[不会出现阻塞的情况](http://blog.csdn.net/u012317833/article/details/39343915)。如果在open一个设备时指定了`O_NONBLOCK`标志，read/write就不会阻塞。以read为例，如果设备暂时没有数据可读就返回-1，同时置errno为EWOULDBLOCK（或者EAGAIN，这两个宏定义的值相同），表示本来应该阻塞在这里（would block，虚拟语气），事实上并没有阻塞而是直接返回错误，调用者应该试着再读一次（again）。这种行为方式称为轮询（Poll），调用者只是查询一下，而不是阻塞在这里死等，这样可以同时监视多个设备:
```js
// 1.进程block，while(true)循环
// 2.但是process是被select这个函数block，而不是被socket IO给block。因此select()与非阻塞IO类似
// 3.select()接口可以同时对多个句柄进行读状态、写状态和错误状态的探测，所以可以很容易构建为多个客户端提供独立问答服务的
// 服务器系统
while(1) {  
    // 4.当用户进程调用了select，那么整个进程会被block，而同时，kernel会“监视”所有select负责的socket，当任何一个socket中的
    // 数据准备好了，select就会返回。这个时候用户进程再调用read操作，将数据从kernel拷贝到用户进程
    非阻塞read(设备1);  
    // 可以继续往下读取
    if(设备1有数据到达)  
        处理数据;  
    非阻塞read(设备2);  
    // 可以继续往下读取
    if(设备2有数据到达)  
        处理数据;  
    ...  
}  
```
如果read(设备1)是阻塞的，那么只要设备1没有数据到达就会`一直阻塞`在设备1的read调用上，即使设备2有数据到达也不能处理，使用非阻塞I/O就可以避免设备2得不到及时处理。

非阻塞I/O有一个**缺点**，如果所有设备都一直没有数据到达，调用者需要`反复查询`做无用功，如果阻塞在那里，操作系统可以调度别的进程执行，就不会做无用功了。在使用非阻塞I/O时，通常不会在一个while循环中一直不停地查询（这称为**Tight Loop**），而是每延迟等待一会儿来查询一下，以免做太多无用功，在延迟等待的时候可以调度其它进程执行。
```js
while(1) {  
    非阻塞read(设备1);  
    if(设备1有数据到达)  
        处理数据;  
    非阻塞read(设备2);  
    if(设备2有数据到达)  
        处理数据;  
    ...  
    sleep(n);  
}  
```
这样做的问题是，设备1有数据到达时可能不能及时处理，最长需延迟n秒才能处理，而且反复查询还是做了很多无用功。而select函数提供的最后一个参数可以`阻塞地`同时监视多个设备，还可以设定阻塞等待的超时时间，从而解决了这个问题。

##### 9.4 poll函数
###### 9.4.1 poll函数简介
poll与select很类似，都是对描述符进行遍历，查看是否有描述符就绪。如果有就返回就绪文件描述符的个数。select系统调用最终会引发设备驱动中的poll函数被执行。
###### 9.4.2 poll函数详解
下面是函数的签名:
```c
#include <poll.h>  
// fds为pollfd结构体数组
int poll(struct pollfd fds[], nfds_t nfds, int timeout)；  
```
结构体pollfd的值为:
```c
struct pollfd {  
    int fd;  
    //1.数组中每一个元素都有文件描述符
    short events;  
    // 2.每一个文件描述符都有检测的事件，是short类型。读，写，异常事件
    short revents;  
    // 3.每一个文件描述符检测后返回的事件
};  
```
这个结构中fd表示文件描述符，events表示请求检测的事件，revents表示检测之后返回的事件，如果当某个文件描述符有状态变化时，revents的值就不为空。下面是**参数**的详细说明:
<pre>
(1)fds：存放需要被检测状态的Socket描述符;与select不同（select函数在调用之后，会**清空**检测socket描述符的数组），每当调用这个函数之后，系统不会清空这个数组，而是将有状态变化的描述符结构的**revents变量状态变化**，操作起来比较方便；

(2)nfds：用于标记数组fds中的struct pollfd结构元素的总数量；

(3)timeout：poll函数调用阻塞的时间，单位是MS（毫秒）

</pre>
下面是**返回值**的详细说明:
<pre>
(1)大于0：表示数组fds中有socket描述符的状态发生变化，或可以`读取`、或可以`写入`、或`出错`。并且返回的值表示这些状态有变化的socket描述符的总数量；此时可以对fds数组进行遍历，以寻找那些revents不空的socket描述符，然后判断这个里面有哪些事件以读取数据。

(2)等于0：表示没有socket描述符有状态变化，并且调用超时。

(3)小于0：此时表示有错误发生，此时全局变量errno保存错误码。
</pre>

##### 9.5 epoll函数
###### 9.5.1 epoll简介
1.epoll是Linux内核为**处理大批量文件描述符**而作了改进的poll，是Linux下多路复用IO接口select/poll的增强版本，它能显著提高程序在`大量并发连接中只有少量活跃的情况下的系统CPU利用率`。

2.epoll获取事件的时候无须**遍历**整个被侦听的描述符集，只要遍历那些被**内核IO事件异步唤醒而加入Ready队列的描述符集合**就行了。epoll除了提供select/poll那种IO事件的水平触发(下次调用select/poll后会再次通知)外，还提供了边缘触发（Edge Triggered），这就使得用户空间程序有可能缓存IO状态，减少epoll_wait/epoll_pwait的调用，提高应用程序效率。

###### 9.5.2 epoll_create函数
下面仔细分析下epoll的三个函数,首先是**epoll_create**:
```c
int epoll_create(int size)
// 返回值是fd
```
创建一个epoll的句柄，size用来告诉`内核`这个监听的数目一共有多大。这个参数不同于select()中的第一个参数，给出最大监听的fd+1的值。需要注意的是，当创建好epoll句柄后，它是会**占用一个fd值**，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所以在使用完epoll后，必须调用close()关闭，否则可能导致fd被耗尽。自从Linux2.6.8开始，size参数被忽略，但是依然要大于0。(注意:在内核实现中epoll是根据`每个`fd上面的callback函数实现的。那么，只有`“活跃”`的socket才会主动的去调用callback函数，其他idle状态socket则不会，在这点上，epoll实现了一个“伪”AIO，因为这时候推动力在`os内核`)。

###### 9.5.3 epoll_ctl函数
下面是**epoll_ctl**函数:
```c
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
// 第一个参数是epoll_create返回值，它可以监听size的文件描述符
// 第二个参数表示操作
// 第三个参数表示需要监听的fd
// 第四个参数告诉内核需要监听的事件
```
epoll的事件注册函数，它不同于select是在调用时告诉内核要监听什么类型的事件，而是在这里**先**注册要监听的事件类型。第一个参数是epoll_create的`返回值`，第二个参数表示`操作`，用三个宏来表示：
<pre>
EPOLL_CTL_ADD:注册新的fd到epfd(create方法返回值，占用一个文件描述符)中；
EPOLL_CTL_MOD:修改已经注册的fd的监听事件；
EPOLL_CTL_DEL:从epfd中删除一个fd；
</pre>
第三个参数是需要监听的fd，第四个参数是告诉内核需要监听的事件，struct epoll_event结构如下:
```c
struct epoll_event {
__uint32_t events; 
/*Epoll事件类型，通过下面的宏表示*/
epoll_data_t data; 
/*用户数据变量*/
};
```
events可以是以下几个宏的集合:
<pre>
EPOLLIN:表示对应的文件描述符可以读(包括对端SOCKET正常关闭)
EPOLLOUT:表示对应的文件描述符可以写
EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来)
EPOLLERR:表示对应的文件描述符发生错误；
EPOLLHUP:表示对应的文件描述符被挂断；
EPOLLET:将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT:只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里。
</pre>

###### 9.5.4 epoll_wait函数
```c
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout)
// events:表示从内核获取到的事件集合
// maxevents:每次能处理的最大事件数，该值不能大于epoll_create的size
// timeout:超时时间（毫秒，0会立即返回，-1将不确定)
// 返回值:需要处理的事件数目，如返回0表示已超时
```
该函数等待事件的产生，类似于select()调用。参数events表示从内核得到事件的集合，maxevents表示每次能处理的最大事件数，告之内核这个events有多大，这个maxevents的值不能大于创建epoll_create()时的size，参数timeout是超时时间（毫秒，0会立即返回，-1将不确定，也有说法说是永久阻塞）。该函数返回需要处理的事件数目，如返回0表示已超时。

###### 9.5.5 epoll具体原理(事件通知,执行回调,而不是遍历查询)
要深刻理解epoll，首先得了解epoll的三大关键要素：**mmap、红黑树、链表**。

epoll是通过`内核`与`用户空间`mmap同一块内存实现的。mmap将用户空间的一块地址和内核空间的一块地址同时映射到相同的一块物理内存地址（不管是用户空间还是内核空间都是虚拟地址，最终要通过地址映射映射到物理地址），使得这块物理内存对内核和对用户均可见，减少用户态和内核态之间的数据交换。内核可以直接看到epoll监听的句柄，效率高。

**一方面**:红黑树将存储epoll所监听的**套接字(套接字本身通过红黑树存储)**。上面mmap出来的内存如何保存epoll所监听的套接字，必然也得有一套数据结构，epoll在实现上采用红黑树去存储所有套接字，当添加或者删除一个套接字时（epoll_ctl），都在红黑树上去处理，红黑树本身插入和删除性能比较好，时间复杂度O(logN)。因此添加或者删除套接字通过红黑树解决了性能问题。

**另一方面**:通过epoll_ctl函数添加进来的事件都会被放在**红黑树的某个节点**(套接字)内，所以，重复添加是没有用的。当把事件添加进来的时候时候会完成关键的一步，那就是该事件都会与相应的**设备（网卡）驱动程序建立回调关系**，当相应的事件发生后，就会调用这个回调函数，该回调函数在内核中被称为：`ep_poll_callback`,这个回调函数其实就所把这个事件添加到rdllist这个双向链表中。一旦有事件发生，epoll就会将该事件添加到双向链表中。那么当我们调用epoll_wait时，epoll_wait只需要检查rdlist双向链表中是否有存在注册的事件，效率非常可观。这里也需要将发生了的事件复制到用户态内存中即可。

![](./images/epoll-the.jpg)

epoll_wait的工作流程：
<pre>
1.epoll_wait调用ep_poll，当rdlist为空（无就绪fd）时挂起当前进程，直到rdlist不空时进程才被唤醒
2.文件fd状态改变（buffer由不可读变为可读或由不可写变为可写），导致相应fd上的回调函数ep_poll_callback()被调用
3.ep_poll_callback将相应fd对应epitem加入rdlist，导致rdlist不空，进程被唤醒，epoll_wait得以继续执行
4.ep_events_transfer函数将rdlist中的epitem拷贝到txlist中，并将rdlist清空
5.ep_send_events函数(很关键)，它扫描txlist中的每个epitem，调用其关联的fd对应的poll方法。此时对poll的调用仅仅是取得fd上较新的events（防止之前events被更新），之后将取得的events和相应的fd发送到用户空间（封装在struct epoll_event，从而epoll_wait返回）
</pre>

###### 9.5.6 epoll与AIO
epoll的**epoll_wait()**方法是阻塞操作。当前线程等待事件的发生，事件发生以后交由不同的程序/函数处理，所以需要事件轮询操作(见9.6下图)。而在AIO中，回调函数的`地址`被传递给系统内核，而在事件发生后回调交给内核处理，内核会通过事件机制来通知应用程序。而AIO也是有一点问题:回调函数的代码是在系统线程中执行，同时也处于系统调用栈的顶部。这样可能会产生意想不到的结果。

##### 9.6 阻塞IO/非阻塞IO/多路复用IO/异步IO图解
**阻塞IO（blocking IO）**过程如下:

 ![](./images/blocking-io.jpg)

**非阻塞IO（non-blocking IO）**过程如下:

![](./images/none-blocking-io.jpg)

**多路复用IO（IO multiplexing）/select/poll/epoll**过程如下:

![](./images/multipexing-io.jpg)

**异步IO(Asynchronous I/O)**过程如下:

![](./images/async-io.jpg)

**同步IO/异步IO区别**:两者的区别就在于synchronous IO做”IO operation”的时候会将`process阻塞`。按照这个定义，之前所述的blocking IO，non-blocking IO，IO multiplexing都属于synchronous IO。有人可能会说，non-blocking IO并没有被block啊。这里有个非常“狡猾”的地方，定义中所指的”IO operation”是指真实的IO操作，就是例子中的recvfrom这个系统调用。non-blocking IO在执行recvfrom这个系统调用的时候，`如果kernel的数据没有准备好，这时候不会block进程。但是当kernel中数据准备好的时候，recvfrom会将数据从kernel拷贝到用户内存中，这个时候进程是被block的`。而asynchronous IO则不一样，当进程发起IO操作之后，就直接返回再也不理睬了，直到kernel发送一个信号，告诉进程说IO完成。在这整个过程中，`进程完全没有被block`。

##### 9.6 select/poll/epoll的比较
详细内容请见下面表格:

![](./images/epollpluspoll.png)

#### 10.内核
内核是`操作系统最基本的部分`。它是为众多应用程序提供对计算机**硬件的安全访问**的一部分软件，这种访问是有限的，并且内核决定一个程序在什么时候对某部分硬件操作多长时间。内核的分类可分为单内核和双内核以及微内核。严格地说，内核并不是计算机系统中必要的组成部分。

内核，是一个`操作系统的核心`。是基于硬件的第一层软件扩充，提供操作系统的最基本的功能，是操作系统工作的基础，它负责管理系统的进程、内存、设备驱动程序、文件和网络系统，决定着系统的性能和稳定性

现代操作系统设计中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序、设备驱动程序等）、基本的、公共的、运行频率较高的模块（如时钟管理、进程调度等）以及关键性数据结构独立开来，使之`常驻内存`，并对他们进行保护。通常把这一部分称之为操作系统的内核。


参考资料:

[进程与线程的一个简单解释](http://www.ruanyifeng.com/blog/2013/04/processes_and_threads.html)

[进程与线程的区别](https://jingyan.baidu.com/article/624e74598efcc834e9ba5a66.html)

[操作系统原理面试题目总结](http://wenboo.site/2016/10/16/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%8E%9F%E7%90%86%E9%9D%A2%E8%AF%95%E9%A2%98%E7%9B%AE%E6%80%BB%E7%BB%93/)

[操作系统概念（第九章） 虚拟内存](http://blog.csdn.net/u013007900/article/details/50231933)

[操作系统存储管理之分段存储](http://blog.csdn.net/qwe6112071/article/details/70500258)

[操作系统存储管理之页式存储管理深入浅出](http://blog.csdn.net/qwe6112071/article/details/70500060)

[文件描述符](https://baike.baidu.com/item/%E6%96%87%E4%BB%B6%E6%8F%8F%E8%BF%B0%E7%AC%A6/9809582?fr=aladdin)

[文件描述符](http://blog.csdn.net/captain_mxd/article/details/52153233)

[每天进步一点点——Linux中的文件描述符与打开文件之间的关系](http://blog.csdn.net/cywosp/article/details/38965239)

[转网络IO模型：同步IO和异步IO，阻塞IO和非阻塞IO](https://www.cnblogs.com/Forever-Kenlen-Ja/p/4480718.html)

[select （Linux 网络编程）](https://baike.baidu.com/item/select/12504672?fr=aladdin)

[linux select函数详解](https://www.cnblogs.com/ccsccs/articles/4224253.html)

[阻塞和非阻塞read/write](http://blog.csdn.net/u012317833/article/details/39343915)

[I/O多路复用技术（multiplexing）是什么？](https://www.zhihu.com/question/28594409)

[Linux中epoll用法总结（转）](https://www.cnblogs.com/chunlinge/p/3394649.html)

[Linux下的I/O复用与epoll详解](https://www.cnblogs.com/lojunren/p/3856290.html)

[红黑树](https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91/2413209?fr=aladdin)

[poll调用深入解析](http://blog.csdn.net/zmxiangde_88/article/details/8099049)

[epoll百度百科](https://baike.baidu.com/item/epoll/10738144?fr=aladdin)

[带外数据](https://baike.baidu.com/item/%E5%B8%A6%E5%A4%96%E6%95%B0%E6%8D%AE)

[epoll函数](https://baike.baidu.com/item/epoll%E5%87%BD%E6%95%B0/10792875?fr=aladdin)

[What's the difference between event-driven and asynchronous? Between epoll and AIO?](https://stackoverflow.com/questions/5844955/whats-the-difference-between-event-driven-and-asynchronous-between-epoll-and-a)