概述

四大基本特征

并发：一段时间内多个程序同时运行（并行是一个时刻多个指令同时运行）
共享：资源共享
虚拟：虚拟地址，为物理硬件提供逻辑接口来降低使用难度
异步：进程走走停停，上下文切换

基本功能

进程管理
内存管理
文件管理
设备管理

用户态和内核态

区别

操作系统的两种运行级别

用户态：
- R3特权级，特权最低
- 进程所能访问的内存空间和对象受到限制
- 占有的处理器可被抢占
内核态：
- R0特权级，特权最高；
- 能访问所有的内存空间和对象
- 占有的处理器不允许被抢占

用户态到内核态的切换（三种中断）

其实就是三种中断

外中断

当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序
异常

当 CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常
系统调用

这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作。比如前例中fork()实际上就是执行了一个创建新进程的系统调用。常见的系统调用还有 read, write, open, create, close, readv, writev, fork, wait, exit, execve, clone 等等

宏内核和微内核

宏内核是将操作系统功能作为一个紧密结合的整体放到内核。

微内核是将一部分操作系统功能移出内核，从而降低内核的复杂性。在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因为需要频繁地在用户态和内核态之间进行切换，所以会有一定的性能损失。

进程管理

进程与线程的区别和联系

进程：资源分配的基本单位，由线程+内存+文件/网络句柄构成

线程：独立调度的基本单位，由 栈+PC(程序计数器)+TLS(线程本地存储) 组成

比如QQ和浏览器是两个进程，浏览器内的http请求是一个线程、渲染是一个线程。

联系：

进程是线程的容器，一个进程中可以并发多个线程，不同的线程共享进程的资源（堆），同一进程的线程各自维护自己的栈。

区别：

资源：操作系统会给每个进程分配资源，但线程不会，只能共享进程的资源
开销：由于要分配回收资源，创建撤销进程的开销远大于创建撤销线程的开销
通信：线程通信更简单，直接读写同一进程中的数据；进程通信需要通过IPC（进程间通信）

进程状态切换

进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统

没有太多的用户操作，目标是保证吞吐量和周转时间（从提交到终止的时间）

先来先服务

first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度

优点：任何进程不会饥饿
缺点：不利于短作业。

短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

短作业优先

shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度

优点：对短作业友好
缺点：长作业可能会饥饿（解决方案，设定阈值，年龄超过阈值使用先来先服务）

最短剩余时间优先（抢）

shortest remaining time next（SRTN）

抢占式调度算法，按剩余运行时间顺序调度。

当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

有大量的用户交互操作，目标是快速响应

时间片轮转（抢）

所有就绪进程按先来先服务原则排成一个队列，给队首一个时间片执行，执行结束放到队尾，再给新的队首一个时间片执行。

效率取决于时间片长度的设置，太短切换浪费过多时间，太长实时性得不到保证

优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

多级反馈队列（抢）

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程同步

同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。

临界区

对临界资源进行访问的那段代码称为临界区

同一时刻内同一段代码可能会有多个进程在执行，同一时刻只允许一个进程位于临界区内。

伪代码：

do{
	//进入区
	//临界区
	//退出区
	//剩余区
}while(TRUE)

临界区实现方式：

非抢占内核：没有竞争
抢占内核：
- 软件实现：使用两个变量记录是否有进程位于临界区以及哪个进程位于临界区
- 硬件实现：锁。进程在进入临界区前检测并申请锁，离开后释放锁。

信号量

信号量是用来协调进程对共享资源的访问

优点：可以同步进程
缺点：信号量有限

信号量是一个特殊的整型变量，程序对其访问都是原子操作，且只允许对它进行等待(P(sv)) 和发送(V(sv))信息操作。

P(sv)等待：如果 sv 的值大于零，就给它减 1 ；如果它的值为零，就挂起该进程的执行
V(sv)发送：如果有其他进程因等待 sv 而被挂起，就让它恢复运行，如果没有进程因等待 sv 而挂起，就给它加 1 。

举个例子，就是两个进程共享信号量 sv ，一旦其中一个进程执行了 P(sv) 操作，它将得到信号量，并可以进入临界区，使 sv 减1。而第二个进程将被阻止进入临界区，因为当它试图执行 P(sv) 时，sv 为 0 ，它会被挂起以等待第一个进程离开临界区域并执行 V(sv) 释放信号量，这时第二个进程就可以恢复执行。

管程

管程模型里，只能有一个进程或线程在执行。java用sychronize+wait notify来实现，即互斥锁+条件变量。

信号量是和资源绑定的，资源最多可以给多少个进程用，s就设置为多少，减到0了就阻塞了。管程只让一个进程运行。信号量和管程可以互相实现。

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

两种管道、两种信号、socket、消息队列、共享内存

管道（无名）

当一个进程创建了一个管道，并调用 fork 创建自己的一个子进程后，父进程关闭读管道端，子进程关闭写管道端，这样提供了两个进程之间数据流动的一种方式。

无名管道创建：

1	int pipe(int filedis[2])

当一个管道建立时，它会创建两个文件描述符(fd)：

filedis[0] 用于读管道。
filedis[1] 用于写管道。

特点：

半双工，数据只能单向流动
只能在父子进程或者兄弟进程中使用
数据被进程从管道读出后，在管道中该数据就不存在了
进程去读取空管道的时候，进程会阻塞
进程去写入满管道的时候，进程会阻塞
管道容量为 64KB(缓存区有限)
必须在系统调用fork( )前调用pipe( )，否则子进程将不会继承文件描述符

FIFO

有名管道，和无名管道基本相同，去除了管道只能在父子进程中使用的限制，不相关的进程也能交换数据

1	int mkfifo(const char * pathname, mode_tmode)

一旦创建了一个FIFO，就可用open打开它，一般的文件访问函数（close、read、write等）都可用于FIFO。FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据

优点：可以实现任意关系的进程间的通信
缺点：缓冲区有限

消息队列

消息队列是消息的链表，存放在内核中并由消息队列标识符标识

建立一个队列，先放入队列的消息被最先取出。和管道不同的是，消息队列允许多个进程放入消息，也允许多个进程取出消息。每个消息可以带有一个整数识别符( message_type )。你可以通过识别符对消息分类 (极端的情况是将每个消息设置一个不同的识别符)。某个进程从队列中取出消息的时候，可以按照先进先出的顺序取出，也可以只取出符合某个识别符的消息(有多个这样的消息时，同样按照先进先出的顺序取出)。

克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点

信号量

它是一个计数器，用于为多个进程提供对共享数据对象的访问。

共享内存

共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。

共享内存是⭐最快⭐的 IPC(interprocess communication) 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量配合使用，来实现进程间的同步和通信。

优点：无须复制，快捷，信息量大
缺点
- 通信是通过将共享空间缓冲区直接附加到进程的虚拟地址空间中来实现的，因此进程间的读写操作的同步问题(映射到文件映射段)
- 利用内存缓冲区直接交换信息，内存的实体存在于计算机中，只能同一个计算机系统中的诸多进程共享，不方便网络通信

信号

通知接收进程某个事件已经发生

套接字

可用于不同机器间的进程通信

优点：
1. 传输数据为字节级，传输数据可自定义，数据量小效率高
2. 传输数据时间短，性能高
3. 适合于客户端和服务器端之间信息实时交互
4. 可以加密，数据安全性强
缺点：需对传输的数据进行解析，转化成应用级的数据。

线程同步

锁机制：包括互斥锁/量（mutex）、读写锁（ reader-writer lock ）、自旋锁（ spin lock ）、条件变量（ condition variable ）
信号量机制( Semaphore )
信号机制( Signal )：类似进程间的信号处理

线程使用共享内存，所以数据是互通的。线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

协程

是一种比线程更加轻量级的存在，主要就是为了减少线程切换的资源消耗。

一个线程里可以有多个协程，它不是被操作系统内核所管理的，而是完全由程序所控制，也就是在用户态执行。这样带来的好处是性能大幅度的提升，因为不会像线程切换那样消耗资源。

一个线程的多个协程虽然可以切换，但运行是串行的。当一个协程运行时，其它协程必须挂起。

同一个线程中通过保存代码执行段状态，进行代码段的分次执行，以及多个代码段的交织执行。

上下文切换

进程的切换者是操作系统，切换时机是根据操作系统自己的切换策略，用户是无感知的。进程的切换内容包括页全局目录、内核栈、硬件上下文，切换内容保存在内存中。进程切换过程是由“用户态到内核态到用户态”的方式，切换效率低。
线程的切换者是操作系统，切换时机是根据操作系统自己的切换策略，用户无感知。线程的切换内容包括内核栈和硬件上下文。线程切换内容保存在内核栈中。线程切换过程是由“用户态到内核态到用户态”，切换效率中等。
协程的切换者是用户（编程者或应用程序），切换时机是用户自己的程序所决定的。协程的切换内容是硬件上下文，切换内存保存在用户自己的变量（用户栈或堆）中。协程的切换过程只有用户态，即没有陷入内核态，因此切换效率高.

死锁

一组互相竞争资源的线程因互相等待，导致永久阻塞的现象。说白了就是：两个线程互相持有对方所需的资源，互不释放且互相等待

必要条件

产生死锁必须同时满足以下四个条件

互斥：进程申请的资源在一段时间内只能被一个进程使用
占有和等待：已经得到了某个资源的进程可以再请求新的资源，但对自己已获得的资源保持不放。
不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

处理方法

主要有以下四种方法：

鸵鸟策略
死锁检测与死锁恢复
死锁预防
死锁避免

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

检测：有向图有环

恢复：

利用抢占恢复
利用回滚恢复
通过杀死进程恢复

死锁预防

在程序运行之前预防发生死锁。

破坏四个必要条件

破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
破坏占有和等待条件

一种实现方式是规定所有进程在开始执行前请求所需要的全部资源
破坏不可抢占条件
破坏环路等待

给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

在程序运行时避免发生死锁

银行家算法

假设释放一个进程，然后把这个进程已分配的资源回收到剩余资源中，然后再找下一个能在剩余可用资源中被释放的进程。以此类推，如果都能被释放，系统处于安全状态，不会死锁。

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

活锁

是指线程1可以使用资源，但它很礼貌，让其他线程先使用资源，线程2也可以使用资源，但它很绅士，也让其他线程先使用资源。这样你让我，我让你，最后两个线程都无法使用资源。

解决办法：线程谦让时，尝试等待一个随机的时间就可以了

饥饿

低优先级的线程资源一直被高优先级抢占

IO

IO模型

IO操作分两步：

等待数据：用户进程向内核发起 IO 请求，等待内核数据准备
数据拷贝：将数据从内核拷贝到进程缓存区中

五种模型记忆方式：

数据没准备好，用户进程就一直等（阻塞IO）
用户进程不想一直等，就隔段时间来检查一次，即轮询（非阻塞IO）
用户进程不想管这事，交给中间人select，数据好了select会通知对应的用户进程（IO多路复用）
不想有中间人，直接内核来通知（信号驱动式IO）

以上四种都是同步IO，根据等待数据分类，在拷贝数据时都是阻塞的。

拷贝数据不阻塞（异步IO）

阻塞

进程发起IO系统调用后，进程被阻塞，转到内核空间处理，整个IO处理完毕后返回进程。操作成功则进程获取到数据。

特点：

进程阻塞挂起不消耗CPU资源，及时响应每个操作；
实现难度低、开发应用较容易；
适用并发量小的网络应用开发；
不适用并发量大的应用：因为一个请求IO会阻塞进程，所以，得为每请求分配一个处理进程（线程）以及时响应，系统开销大。

非阻塞

进程发起IO系统调用后，如果内核缓冲区没有数据，需要到IO设备中读取，进程返回一个错误而不会被阻塞；进程发起IO系统调用后，如果内核缓冲区有数据，内核就会把数据返回进程

典型应用：socket是非阻塞的方式（设置为NONBLOCK）

阻塞IO模型是一个阻塞IO调用，而非阻塞IO模型是多个非阻塞IO调用+一个阻塞IO调用，因为多个IO检查会立即返回错误，不会阻塞进程。

特点：

进程轮询（重复）调用，消耗CPU的资源；
实现难度低、开发应用相对阻塞IO模式较难；
适用并发量较小、且不需要及时响应的网络应用开发；

IO多路复用

多个的进程的IO可以注册到一个复用器(select)上，然后用一个进程调用该 select ， select 会监听所有注册进来的IO；如果 select 监听的IO在内核缓冲区都没有可读数据，select 调用进程会被阻塞；而当任一IO在内核缓冲区中有可数据时，select 调用就会返回；而后 select 调用进程可以自己或通知另外的进程（注册进程）来再次发起读取IO，读取内核中准备好的数据。可以看到，多个进程注册IO后，只有另一个select调用进程被阻塞。

典型应用：select、poll、epoll三种方案，nginx都可以选择使用这三个方案;

特点：

专一进程解决多个进程IO的阻塞问题，性能好；Reactor模式;
实现、开发应用难度较大；
适用高并发服务应用开发：一个进程（线程）响应多个请求；

信号驱动

当进程发起一个IO操作，会向内核注册一个信号处理函数，然后进程返回不阻塞；当内核数据就绪时会发送一个信号给进程，进程便在信号处理函数中调用IO读取数据.

特点：回调机制，实现、开发应用难度大；

异步

当进程发起一个IO操作，进程返回（不阻塞），但也不能返回结果；内核把整个IO处理完后，会通知进程结果。如果IO操作成功则进程直接获取到数据。

特点：

不阻塞，数据一步到位；Proactor模式；
需要操作系统的底层支持，LINUX 2.5 版本内核首现，2.6 版本产品的内核标准特性；
实现、开发应用难度大；
非常适合高性能高并发应用；

IO多路复用

在计算机领域常说的 I/O 包括磁盘 I/O 和网络 I/O ，我们所说的 I/O 复用主要是指网络 I/O ，在 Linux 中一切皆文件，因此网络 I/O 也经常用文件描述符 FD 来表示。

多个描述符的IO操作都能在一个线程内并发交替地顺序完成，这就叫IO多路复用。

复用指的是复用同一个进程/线程。

select

简单来说就是：select去看IO是否就绪（读、写、异常三种文件描述符），好了就启动用户线程。

描述符集合底层用数组实现。

下面是详细介绍，重点是那个select函数。

select 使用一个宏定义函数按照 bitmap 原理填充 fd ，默认大小是 1024 个，因此对于 fd 的数值大于 1024 都可能出现问题。

select 函数准许进程指示内核等待多个事件中的任何一个发送，并只在有一个或多个事件发生或经历一段指定的时间后才唤醒。

运行机制：

select会将全量fd_set从用户空间拷贝到内核空间，并注册回调函数，在内核态空间来判断每个请求是否准备好数据。select在没有查询到有文件描述符就绪的情况下，将一直阻塞（I/O多路服用中提过：select是一个阻塞函数）。如果有一个或者多个描述符就绪，那么select将就绪的文件描述符置位，然后select返回。返回后，由程序遍历查看哪个请求有数据。

缺点：

每次调用select，都需要把fd集合从用户态拷贝到内核态，fd越多开销则越大；
每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
select支持的文件描述符数量有限，默认是1024。

函数原型：

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

int select(int maxfdp1,fd_set *readset,fd_set *writeset,fd_set *exceptset,const struct timeval *timeout);

返回值：就绪描述符的数目，超时返回 0 ，出错返回 -1 。

函数参数介绍如下：

第一个参数 maxfdp1 指定待测试的描述字个数，它的值是待测试的最大描述字加 1 （因此把该参数命名为maxfdp1 ），描述字 0、1、2...maxfdp1 - 1 均将被测试。因为文件描述符是从 0 开始的。
中间的三个参数 readset 、writeset 和 exceptset 指定我们要让内核测试读、写和异常条件的描述字。如果对某一个的条件不感兴趣，就可以把它设为空指针。struct fd_set 可以理解为一个集合，这个集合中存放的是文件描述符FD，可通过以下四个宏进行设置：

void FD_ZERO(fd_set *fdset);          //清空集合
void FD_SET(int fd, fd_set *fdset);   //将一个给定的文件描述符加入集合之中
void FD_CLR(int fd, fd_set *fdset);   //将一个给定的文件描述符从集合中删除
int FD_ISSET(int fd, fd_set *fdset);  // 检查集合中指定的文件描述符是否可以读写

timeval *timeout 告知内核等待所指定描述字中的任何一个就绪可花多少时间。其 timeval 结构用于指定这段时间的秒数和微秒数。

struct timeval{
    long tv_sec;   //seconds
    long tv_usec;  //microseconds
};

这个参数有三种可能：

（1）永远等待下去：仅在有一个描述字准备好 I/O 时才返回。为此，把该参数设置为空指针 NULL 。

（2）等待一段固定时间：在有一个描述字准备好 I/O 时返回，但是不超过由该参数所指向的 timeval 结构中指定的秒数和微秒数。

（3）根本不等待：检查描述字后立即返回，这称为轮询。为此，该参数必须指向一个 timeval 结构，而且其中的定时器值必须为 0 。

poll

poll 与 select

相似点：管理多个描述符都是进行轮询，根据描述符的状态进行处理。
不同点：
- poll 使用链表实现，没有最大文件描述符数量的限制；
- select使用数组实现，最多1024个文件描述符。

共同的缺点：

包含大量文件描述符的数组被整体复制于用户态和内核的地址空间之间，包括未就绪的文件描述符，它的开销随着文件描述符数量的增加而线性增大。

下面是详细介绍

函数格式如下所示：

1 2	# include <poll.h> int poll ( struct pollfd * fds, unsigned int nfds, int timeout);

pollfd 结构体定义如下：

struct pollfd {
    int fd;         	  /* 文件描述符 */
    short events;         /* 等待的事件 */
    short revents;        /* 实际发生了的事件 */
} ;

每一个 pollfd 结构体指定了一个被监视的文件描述符，可以传递多个结构体，指示 poll() 监视多个文件描述符。每个结构体的 events 域是监视该文件描述符的事件掩码，由用户来设置这个域。revents 域是文件描述符的操作结果事件掩码，内核在调用返回时设置这个域。events 域中请求的任何事件都可能在 revents 域中返回。合法的事件如下：

POLLIN 　　　　　　　　有数据可读。
POLLRDNORM 　　　　  有普通数据可读。
POLLRDBAND　　　　　 有优先数据可读。
POLLPRI　　　　　　　　 有紧迫数据可读。
POLLOUT　　　　　　      写数据不会导致阻塞。
POLLWRNORM　　　　　  写普通数据不会导致阻塞。
POLLWRBAND　　　　　   写优先数据不会导致阻塞。
POLLMSGSIGPOLL 　　　　消息可用。

此外，revents 域中还可能返回下列事件：

1
2
3

POLLER　　   指定的文件描述符发生错误。
POLLHUP　　 指定的文件描述符挂起事件。
POLLNVAL　　指定的文件描述符非法。

timeout 参数指定等待的毫秒数，无论 I/O 是否准备好，poll 都会返回。timeout 指定为负数值表示无限超时，使 poll() 一直挂起直到一个指定事件发生；timeout 为 0 指示 poll 调用立即返回并列出准备好I/O的文件描述符，但并不等待其它的事件。这种情况下，poll() 就像它的名字那样，一旦选举出来，立即返回。

返回值和错误代码
成功时，poll() 返回结构体中 revents 域不为 0 的文件描述符个数；如果在超时前没有任何事件发生，poll() 返回 0 ；失败时，poll() 返回 -1 ，并设置 errno 为下列值之一。

epoll

epoll 使用一个文件描述符管理多个描述符，将用户关心的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的 copy 只需一次。

poll_ctl()用于向内核注册新的描述符或者改变描述符的状态
已注册的描述符存储在内核的红黑树上
IO就绪的描述符会加入到链表中
用户进程调用epoll_wait()可以得到就绪的IO描述符

如图展示了红黑树、双链表、epitem之间的关系：

工作模式：

LT模式（默认）：当epoll_wait检测到描述符事件发生并将此事件通知应用程序，应用程序可以不立即处理该事件。下次调用epoll_wait时，会再次响应应用程序并通知此事件。
ET模式：当epoll_wait检测到描述符事件发生并将此事件通知应用程序，应用程序必须立即处理该事件。如果不处理，下次调用epoll_wait时，不会再次响应应用程序并通知此事件。

LT更安全，ET更高效；

LT可以使用阻塞或者非阻塞IO，ET必须用非阻塞IO防止其他任务饿死。

ET模式指的是当数据从无到有时，才通知该fd。数据读不完，也不会再次通知，所以read时一定要采用循环的方式一直读到read函数返回-1为止。此时采用阻塞的read，那么就阻塞了整个线程。

常见问题：

使用epoll是否需要将socket设置为nonblocking?

取决于你使用的触发方式，如果你使用水平触发(Level-triggered) 那么此时的 epoll 相当于高级的 select ，你的论述是对的，是不需要一定将 socket 设置为非阻塞的; 然而，当你使用边缘触发(Edge-triggered) 那么此时从业务的完整性考虑，是建议将 socket 设置为 nonbocking 模式，并且在读写触发 EAGAIN 之后再进行epoll_wait 。
epoll的优点
1. 没有最大并发连接的限制。能打开的 FD 的上限远大于 1024（ 1G 的内存上能监听约10万个端口）
2. 效率提升，不是轮询而是回调。不会随着 FD 数目的增加效率下降。只有活跃可用的 FD 才会调用 callback 函数。即 Epoll 最大的优点就在于它只管你“活跃”的连接，而跟连接总数无关，因此在实际的网络环境中，Epoll 的效率就会远远高于 select 和 poll 。
LT和ET的读写问题
1. LT
  - read
    - LT 对于 read 操作比较简单，有 read 事件就读，读多读少都没有问题。
  - write
    - 但是 write 就不那么容易了，一般来说socket在空闲状态时发送缓冲区一定是不满的，假如 fd 一直在监控中，那么会一直通知写事件，不胜其烦。
    - 所以必须保证没有数据要发送的时候，要把 fd 的 写 事件监控从 epoll 列表中删除，需要的时候再加入回去，如此反复。
    - 对应 write 的过度提醒，需要使用者随用随加，否则将一直被提醒可写事件。
2. ET
  - read
    - fd 可读则返回可读事件，若开发者没有把所有数据读取完毕，epoll 不会再次通知 read 事件。
    - 也就是说如果没有全部读取所有数据，那么导致 epoll 不会再通知该 socket 的 read 事件，事实上一直读完很容易做到。
  - write
    - 若发送缓冲区未满，epoll通知write事件，直到开发者填满发送缓冲区，epoll才会在下次发送缓冲区由满变成未满时通知write事件。
  - ET 模式下只有socket的状态发生变化时才会通知，也就是读取缓冲区由无数据到有数据时通知read事件，发送缓冲区由满变成未满通知write事件。

下面是详细介绍

epoll 使用 事件 的就绪通知方式，通过 epoll_ctl 注册 fd ，一旦该 fd 就绪，内核就会采用类似 callback 的回调机制来激活该 fd ，epoll_wait 便可以收到通知。

//用户数据载体
typedef union epoll_data {
   void    *ptr;
   int      fd;
   uint32_t u32;
   uint64_t u64;
} epoll_data_t;
//fd装载入内核的载体
 struct epoll_event {
     uint32_t     events;    /* Epoll events */
     epoll_data_t data;      /* User data variable */
 };

epoll 函数

epoll 操作过程需要三个接口，分别如下：

#include <sys/epoll.h>
int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

int epoll_create(int size);
在内核区创建一个 epoll 相关的一些列结构，并且将一个句柄 fd 返回给用户态，后续的操作都是基于此 fd 的，size 用来告诉内核这个监听的数目一共有多大，类似于 STL 的 vector 动态数组，如果 size 不合适会涉及复制扩容，不过貌似 4.1.2 内核之后 size 已经没有太大用途了；这个参数不同于 select() 中的第一个参数，select 给出的是最大监听的 fd+1 的值。需要注意的是，当创建好 epoll 句柄后，它就是会占用一个 fd 值，在 linux 下如果查看 /proc/ 进程 id/fd/ ，是能够看到这个 fd 的，所以在使用完 epoll 后，必须调用 close() 关闭，否则可能导致 fd 被耗尽。
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

epoll 的事件注册函数， select() 是在监听事件时告诉内核要监听什么类型的事件，而是在这里 epoll 是先注册要监听的事件类型。第一个参数是 epoll_create() 的返回值，第二个参数 epoll_event 是用户态和内核态交互的结构，定义了用户态关心的事件类型和触发时数据的载体 epoll_data ；
- EPOLL_CTL_ADD：注册新的 fd 到 epfd 中；
- EPOLL_CTL_MOD：修改已经注册的 fd 的监听事件；
- EPOLL_CTL_DEL：从 epfd 中删除一个 fd ；
  第三个参数是需要监听的 fd ，第四个参数是告诉内核需要监听什么事，epoll_event是用户态需监控fd的代言人，后续用户程序对fd的操作都是基于此结构的，struct epoll_event 结构如下：
1
2
3
4
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
events 可以是以下几个宏的集合：
- EPOLLIN ：表示对应的文件描述符可以读（包括对端 SOCKET 正常关闭）
- EPOLLOUT：表示对应的文件描述符可以写
- EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）
- EPOLLERR：表示对应的文件描述符发生错误
- EPOLLHUP：表示对应的文件描述符被挂断
- EPOLLET：将 EPOLL 设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的
- EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个 socket 的话，需要再次把这个 socket 加入到 EPOLL 队列里。
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

是阻塞等待内核返回的可读写事件，epfd 还是 epoll_create 的返回值，events 是个结构体数组指针存储 epoll_event ，也就是将内核返回的待处理 epoll_event 结构都存储下来，maxevents 告诉内核本次返回的最大 fd 数量，这个和 events 指向的数组是相关的；

底层实现看这里

内存管理

内存管理机制

分为连续（块式）和非连续（页式、段氏等）

块式管理 ：给每个进程分配整块内存
页式管理 ：把主存分为大小相等且固定的一页一页的形式，页较小，相对相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址。
段式管理 ：页式管理虽然提高了内存利用率，但是页式管理其中的页实际并无任何实际意义。段式管理把主存分为一段段的，每一段的空间又要比一页的空间小很多。但是，最重要的是段是有实际意义的，每个段定义了一组逻辑信息，例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。段式管理通过段表对应逻辑地址和物理地址。
段页式管理机制 ：结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说段页式管理机制中段与段之间以及段的内部的都是离散的。

内存分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。

分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。

段选择因子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

缺点：

内存碎片
内存交换效率低

内存分页

把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB。虚拟地址与物理地址之间通过页表来映射，如下图：

页表实际上存储在 CPU 的内存管理单元 （MMU）中，于是 CPU 就可以直接通过 MMU，找出要实际要访问的物理内存地址。

分页弥补分段缺陷：

内存碎片问题：由于内存空间都是预先划分好的，也就不会像分段会产生间隙非常小的内存，这正是分段会产生内存碎片的原因。而采用了分页，那么释放的内存都是以页为单位释放的，也就不会产生无法给进程使用的小内存。
交换效率问题：如果内存空间不够，操作系统会把其他正在运行的进程中的 LRU 等页面置换算法计算出的的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。

页表

特点如下：

页映射到帧
页是连续的虚拟内存
帧是非连续的物理内存
不是所有的页都有对应的帧(缺页异常page fault)

页表不分级的话，页表太多占用空间，所以改进使用多级页表。

多级页表

多级页表实际上是增加了索引，有了索引就可以定位到具体的项。

缺点是增加了寻址的时间（时间换空间）

快表TLB

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB。MMU可以先在TLB中查找页表，如果没有命中再去找页表里找。

当TLB不命中时，MMU必须从L1缓存中取出对应的*页表条目PTE，新取出的PTE存放在TLB中，可能会覆盖一个已经存在的PTE条目。

反向页表

传统页表的缺点是：逻辑地址空间增长速度快于物理地址空间，所以反向页表，也就是index是物理地址，value是逻辑地址，它的大小会小于传统页表。

以页帧号为 index，页号地址为 value，每次访问从前到后遍历页表，将 value 和逻辑地址比对，这样做的原因就是大大节省了内存的开销，全局只需要一张页表。再通过hash加速判断

段页式

先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制(代码段、数据段、栈段、堆段等等)；
接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；

虚拟内存

虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，并且把内存扩展到硬盘空间。

虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。这样会更加有效地管理内存并减少出错。

局部性原理

时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

实现方式

主要就是分内存和外存。

请求分页存储管理 ：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
请求分段存储管理 ：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
请求段页式存储管理

缺页中断

在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

保护CPU现场
分析中断原因
转入缺页中断处理程序进行处理
恢复CPU现场，继续执行

页面置换算法

地址映射过程中，若在页面中发现所要访问的页面不在内存中，则发生缺页中断。如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则叫做页面置换算法。

OPT 页面置换算法（最佳页面置换算法） ：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。一般作为衡量其他置换算法的方法。
FIFO（First In First Out）页面置换算法（先进先出页面置换算法） : 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
LRU （Least Currently Used）页面置换算法（最近最久未使用页面置换算法） ：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
LFU （Least Frequently Used）页面置换算法（最少使用页面置换算法） : 该置换算法选择在之前时期使用最少的页面作为淘汰页。

Linux

常用命令

chmod 777 file_name #更改文件权限，421 rwx
df -h #查看磁盘目录使用情况

top #实时查看每个进程CPU、内存利用率
top -H #排序查看
top -p 139 #查看进程号139的CPU内存占有率

 ps -aux #瞬间查看，不实时，进程查看命令
 grep #文本搜索 例如ps -aux|grep yfw
 
 netstat -an #查看网络是否连通,监听TCP和UDP连接
 
 ifconfig #查看ip地址网卡信息及接口信息
 
 du #显示目录或文件的大小
 du -h --max-depth=1 #查看当前文件夹下文件和目录大小
 
 cat /proc/version #查看系统版本
 cat /proc/cpuinfo #查看cpu信息
 free #查看内存
 fdisk -l #查看磁盘
 
 #修改环境变量
 /etc/profile #所有用户生效
 ~/.bashrc #当前用户生效

文件IO

文件描述符fd ：一个非负整数，范围是0~OPEN_MAX-1。内核用它来标识进程正在访问的文件。当进程创建时，默认为它打开了3个文件描述符，它们都链接向终端：

0：标准输入
1：标准输出
2：标准错误输出

通常我们应该使用STDIN_FILENO，STDOUT_FILENO和 STDERR_FILENO来替代这三个幻数，从而提高可读性。

打开文件：open和openat函数

1
2
3

#include<fcntl.h>
int open(const char* path,int oflag,.../*mode_t mode*/);//只能绝对路径
int openat(int fd,const char*path,int oflag,.../*mode_t mode */);//fd可以指定相对路径为目录

创建文件：creat函数

成功返回fd，失败返回-1

关闭文件：close函数

关闭文件释放所有锁，进程终止时自动关闭所有它打开的文件

读取文件：read函数

从文件的当前偏移量开始读。

实际读到的字节数少于期望读到的字节数：

普通文件：在读到期望字节数之前到达了文件尾端
终端设备：通常一次最多读取一行（行缓存）
网络：缓存机制
FIFO和管道：管道包含的字节少于所需的数量
被中断

写入文件：write函数

原子定位读和原子定位写：pread/pwrite函数

调用pread相当于先调用lseek再调用read.但是调用pread时，无法中断其定位和读操作，并且不更新当前文件偏移量；

调用pwrite相当于先调用lseek再调用write.但是调用pwrite时，无法中断其定位和写操作，并且不更新当前文件偏移量

延迟写刷盘：sync, fsync, fdatasync函数

磁盘IO先写到缓冲区，再刷盘，称作延迟写。这三个函数能显式刷盘

1
2
3

void sync(void);         //刷盘，不等待刷盘结束
int fsync(int fd);       //只对fd指定的单个文件刷盘，等待刷盘结束才返回
int fdatasync(int fd);   //同fsync，但是只影响文件的数据部分，不更新文件属性

文件和目录

获取文件信息结构：4个stat函数

int stat(const char * restrict pathname, struct stat*restrict buf);//当前文件信息
int fstat(int fd, struct stat* buf);//指定fd文件信息
int lstat(const char* restrict pathname,struct stat *restrict buf);//软链接信息
int fstatat(int fd,const char*restrict pathname,struct stat*restrict buf,int flag);//相对路径文件信息

文件类型：

普通文件
目录文件
系统的所有设备
- 块特殊文件
- 字符特殊文件
FIFO
socket
软链接

文件系统

分区：每个分区包含一个文件系统
柱面
- inode图：指示哪些 i 节点已经被使用，哪些未被使用
- 块位图：用于指示哪些数据块已经被使用，哪些未被使用
- inode:许多个
- 数据区
  - 数据块
  - 目录块

硬链接和软链接

文件都有文件名与数据，这在 Linux 上被分成两个部分：用户数据 (user data) 与元数据 (metadata)。

用户数据，即文件数据块(data block)，记录文件真实内容的地方；
元数据：记录文件的附加属性，如文件大小、创建时间、所有者等信息。
- inode 号：元数据的一部分，不包含文件名，是文件的唯一标识。文件名仅是为了方便人们的记忆和使用，系统或程序通过 inode 号寻找正确的文件数据块。