操作系统

堆和栈有什么区别？

1、堆栈空间分配不同。栈由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等，栈有着很高的效率；堆一般由程序员分配释放，堆的效率比栈要低的多。

2、堆栈缓存方式不同。栈使用的是一级缓存， 它们通常都是被调用时处于存储空间中，调用完毕立即释放；堆则是存放在二级缓存中，速度要慢些。（或者说速度不一样）

3、空间大小： 栈的空间大小并不大，一般最多为2M，超过之后会报Overflow错误。堆的空间非常大，理论上可以接近3G。（针对32位程序来说，可以看到内存分布，1G用于内核空间，用户空间中栈、BSS、data又要占一部分，所以堆理论上可以接近3G，实际上在2G-3G之间）。

4、能否产生碎片： 栈的操作与数据结构中的栈用法是类似的。‘后进先出’的原则，以至于不可能有一个空的内存块从栈被弹出。因为在它弹出之前，在它上面的后进栈的数据已经被弹出。它是严格按照栈的规则来执行。但是堆是通过new/malloc随机申请的空间，频繁的调用它们，则会产生大量的内存碎片。这是不可避免地。

五种IO模型

通常用户进程中的一个完整IO分为两阶段：用户进程空间<-->内核空间、内核空间<-->设备空间（磁盘、网络等）。

LINUX中进程无法直接操作I/O设备，其必须通过系统调用请求kernel来协助完成I/O动作；内核会为每个I/O设备维护一个缓冲区。

阻塞IO

进程发起IO系统调用后，进程被阻塞，转到内核空间处理，整个IO处理完毕后返回进程。

在内核将数据准备好之前，系统调用会一直等待所有的套接字。

非阻塞IO

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

发起调用后，内核会马上返回给进程，而不会阻塞住。但进程需要轮询（重复）调用，消耗CPU的资源

每次客户询问内核是否有数据准备好，即文件描述符缓冲区是否就绪。当有数据报准备好时，就进行拷贝数据报的操作。当没有数据报准备好时，也不阻塞程序，内核直接返回未准备就绪的信号，等待用户程序的下一个轮巡。

IO多路复用

多个进程的IO可以注册到一个复用器（select、poll、epoll）上，一个进程调用该复用器，会监控所有注册进来的IO。如果复用器监听的IO在内核缓冲区都没有可读数据（注册了的IO的文件描述符都没就绪），则复用器的调用线程会被阻塞；当任一IO有可读数据时，复用器的调用就会返回。

信号驱动IO

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

异步IO

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

在 Linux 下的异步 I/O 是不完善的， aio 系列函数是由 POSIX 定义的异步操作接口，不是真正的操作系统级别支持的，而是在用户空间模拟出来的异步，并且仅仅支持基于本地文件的 aio 异步操作，网络编程中的 socket 是不支持的，这也使得基于 Linux 的高性能网络程序都是使用 Reactor 方案。

IO多路复用（select、poll、epoll）

为什么要IO复用

让服务器服务多个客户端，那么最直接的方式就是为每一条连接创建线程，但是并发量一多就不现实。

使用「资源复用」的方式，让一个线程要处理多个连接的业务，然而线程在处理某个连接的 read 操作时，如果遇到没有数据可读，就会发生阻塞，那么线程就没办法继续处理其他连接的业务。

要解决这一个问题，最简单的方式就是将 socket 改成非阻塞，然后线程不断地轮询调用 read 操作来判断是否有数据，这种方式虽然该能够解决阻塞的问题，但是因为轮询是要消耗 CPU 的，而且随着一个 线程处理的连接越多，轮询的效率就会越低。

这个问题在于，线程并不知道当前连接是否有数据可读，从而需要每次通过 read 去试探。

那有没有办法在只有当连接上有数据的时候，线程才去发起读请求呢？答案是有的，实现这一技术的就是 I/O 多路复用。

select

使用位图来标示每一个监控的事件是否发生，所以可以监控的文件描述符数量是有上限的，一般为1024/2048，而且需要用不同的位图表示不同的事件类型：read/write/error。内核检测到文件描述符事件后，将对应的标志位置位，然后将位图复制到用户空间，用户需要遍历位图找到就绪事件，时间复杂度为O(n)

poll

poll使用pollfd表示每一个监控事件，用pollfd链表来存储事件表。

没读完的链接

这些在内核里面干了啥

Reactor和Proactor模型

Reactor模型

主线程只负责监听文件描述符事件，通知工作线程，除此之外不做其他事情。而读写数据、接受连接，以及处理客户请求等都在工作线程完成。==一般使用同步IO实现==（为什么）

三种角色：

1. Reactor：负责监听和分配时间，将IO事件分派给对应的Handler（主线程）
2. Acceptor：处理客户端连接
3. Handler：将自身与事件绑定，执行IO任务、处理业务逻辑并输出结果

使用同步 I/O 模型（以 epoll_wait 为例）实现的 Reactor 模式的工作流程是：

• 主线程往epoll内核事件表注册读就绪事件，并调用epoll_wait等待数据
• 当有数据可读时，epoll通知主线程，主线程将事件放入请求队列
• 某个工作线程被唤醒，从请求队列中取出事件，然后从socket中读取数据并处理业务逻辑。处理完成后往epoll事件表上注册写就绪事件
• 当socket可写后，epoll_wait通知主线程，主线程将可写事件放入请求队列
• 某个工作线程被唤醒，将数据写入socket

Proactor模型

工作线程只负责业务逻辑，将所有IO操作、连接维护工作都交给主线程和内核。一般使用异步IO实现

模拟Proactor：

使用同步IO模拟Proactor模式的原理是主线程执行数据读写操作，操作完成后，主线程通知工作线程。对于工作线程来说，它直接获得了读写的结果，只需对数据进行逻辑处理即可。

使用同步I/O模型（仍以epoll_wait为例）模拟出Proactor模式的工作流程如下：

（与reactor的区别是主线程将什么放入请求队列、谁具体完成读写任务）

• 主线程往epoll事件表上注册读就绪事件，并调用epoll_wait等待数据
• 当socket有数据可读时，epoll通知主线程。主线程循环读取数据，直到全部读完，并将读到的数据封装成请求对象插入到请求队列
• 某个工作线程被唤醒，获取请求队列上的对象，并处理业务逻辑。处理完后往epoll时间表上注册写就绪事件
• 当socket可写后，内核通知主线程，主线程写入处理结果。

二者的区别

Reactor是在事件发生时就通知事先注册的事件（读写由处理函数完成）；Proactor是在事件发生时进行异步I/O（读写由OS完成），待IO完成才调度处理器来处理。

优点：

1. 事务分离，将业务代码与调度代码分离开来
2. Reactor实现相对简单，对于耗时短的场景处理高效；
3. Proactor性能更高，能够处理耗时长的并发场景；

缺点：

1. Reactor处理耗时长的任务会造成事件分发的阻塞，影响后续事件的处理
2. Proactor实现逻辑复杂，依赖操作系统对异步的支持

零拷贝

对于读或写，都有两次状态转换、一次CPU拷贝、一次DMA拷贝：

1. 应用程序调用read/write，切换成内核态（状态切换）
2. CPU对DMA发起IO请求
3. DMA对磁盘发起IO请求
4. 磁盘将数据搬运到磁盘缓存区，然后发送完成信号
5. DMA将数据从磁盘缓存区拷贝到内核缓冲区（DMA拷贝）
6. CPU将数据从内核缓冲区拷贝到用户缓冲区（CPU拷贝）
7. read/write返回，切换到用户态（状态切换）

对于需要频繁读写文件的场景，如Web服务器读取本地磁盘文件并发送给客户端，会大量耗费CPU资源，所以需要零拷贝来降低冗余数据拷贝

零拷贝实现方式：1. mmap+write； 2. sendfile； 3. sendfile+DMA收集； 4. splice

假设一个需要从本地文件通过网卡发送的场景，有四次状态切换、2次CPU拷贝、2次DMA拷贝

mmap+write

将内核中的读缓冲区与用户空间缓冲区地址进行映射，从而实现了内核缓冲区与用户缓冲区的共享（就不需要上面的第6步，减少了一次状态切换和CPU拷贝），但在内核空间仍然有一次cpu拷贝

[图片上传失败...(image-227ad0-1691243406207)]

sendfile

sendfile建立了两个文件之间的传输通道，只需调用一次sendfile就可完成read+write功能，但是由于数据不经过用户缓冲区，数据无法被修改。减少了两次状态切换、一次CPU拷贝

[图片上传失败...(image-cee324-1691243406207)]

sendfile+DMA收集

这个方法只需要将内核缓冲区的文件描述符以及文件大小发送到套接字缓冲区，然后由DMA完成拷贝到网卡的操作，不需要CPU拷贝。（需要DMA控制器硬件支持）

[图片上传失败...(image-83bf73-1691243406207)]

splice

splice在内核缓冲区与套接字缓冲区之间建立管道来传输数据，不需要CPU拷贝操作，性能与上一个方法一样（同时不需要硬件支持）

但是有一个局限：它的两个文件描述符参数中有一个必须是管道设备

[图片上传失败...(image-599ccd-1691243406207)]

进程与线程

多线程与多进程的区别

在概念上：

1. 进程是系统中正在运行的程序，是计算机分配资源的单位。他有属于自己独立的内存空间、磁盘空间和IO设备等。
2. 线程是进程的子集，是任务调度的基本单元。各个线程间共享代码空间、全局变量和堆区；但是有独立的栈区，即局部变量是各线程私有的。

创建、销毁、切换

1. 进程创建销毁、切换比较复杂，速度慢
2. 线程创建销毁、切换比较简单、速度快

CPU和内存

1. 进程占用内存多、切换复杂，CPU利用率低
2. 线程占用内存少、切换简单，CPU利用率高

可靠性

1. 进程相互之间不会影响
2. 一个线程挂掉会导致整个进程挂掉

多线程的资源共享

1. 同一个进程的不同线程共享：
   1. 全局变量、静态变量
   2. 堆区
2. 每个线程独享：
   1. 栈区
   2. 寄存器
   3. 程序计数器

进程切换与线程切换的区别

最主要的区别是进程的切换涉及虚拟地址空间的切换，而线程的切换不会

地址空间切换

不同的进程的虚拟地址空间是完全独立的，地址空间分为内核地址空间和用户地址空间。对于内核空间，不同进程是共用同一个内核空间，只有用户空间才是各用各的（但每个进程有各自的内核栈）。所以在进程切换时，地址空间切换的时候只需要切换用户空间就可以了。

程序要访问物理内存，需要通过MMU内存管理单元来将虚拟地址转换成物理地址， 而MMU需要通过分页机制和页表来完成虚拟地址到物理地址的转换。每个进程都有独立的地址空间，为了这个进程独立完成映射，这就需要每个进程都有独立的进程页表。也就是说进程切换的时候需要进行页表切换。这里需要引入一个寄存器，在英特尔CPU中有个CR3寄存器，这个寄存器又叫PDBR（Page Directory Base Register）页表基址寄存器。这个寄存器保存的是真实的物理地址。每个任务的TSS段就有自己的CR3的物理地址。每次进行任务切换的时候，CR3的内容都会被替换改为新任务的CR3域中的物理地址。这里我们已经可以看到，页表切换其实也是通过寄存器切换来完成的。

任务切换的本质：任务切换的本质就是CPU状态的切换，把CPU上下文（寄存器和程序计数器）保存起来，然后加载下一个要运行的任务的上下文到CPU寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务

cpu上下文切换

CPU上下文切换的定义

CPU上下文是指CPU运行必须依赖的环境：

1. CPU寄存器
2. CPU程序计数器

CPU上下文切换的步骤：

1. 把前一个任务的上下文保存起来（保存在内核中，有一个结构体存储）
2. 加载新任务的上下文到这些寄存器和程序计数器
3. 跳转到程序计数器所指的位置，开始运行新任务

类型：

1. 进程的上下文切换
2. 线程上下文切换
3. 中断上下文切换

进程上下文切换

需要切换的内容：

• 用户空间资源
  • 虚拟地址空间
  • 全局变量
  • 栈区、堆区
• 内核空间资源
  • 内核堆栈
  • 寄存器值

线程上下文切换

需要切换的内容：

• 用户空间资源
  • 栈区
• 内核空间资源
  • CPU寄存器

中断上下文切换

需要切换的内容：

• 内核空间资源：
  • CPU寄存器
  • 内核堆栈

线程间切换会出现死锁吗

系统在需要从一个线程切换到另一个线的时候调用内核switch函数，在调用之前会先获取线程对应的进程的锁。如果在调用switch函数（切换线程）时，第一个线程持有除了该线程以外的锁，就有可能出现死锁。

例如，线程P1持有某个文件或UART的锁，通过调用switch/yield/sched函数出让CPU（切换了线程），这会导致进程P1持有了锁，但是进程P1又不在运行。CPU切换到P2线程运行，P2也想访问某资源，想要获取锁，但被P1占用，此时就会不断等待，造成死锁

解决方法：禁止在线程切换的时候加锁（线程持有其他锁的时候禁止切换线程）

线程间同步的方式

互斥量

强调的是资源之间的访问互斥：每个线程在对共享资源操作前都会尝试先加锁，加锁成功才能操作，操作结束之后解锁。

特点：

1. 原子性：锁住互斥量过程是一个原子操作，同一时间只能有一个线程共享该资源
2. 唯一性：如果某一线程锁定了该互斥量，只有该线程可以使用这个互斥量
3. 非繁忙等待：一个互斥量若已经被锁定，其他线程想访问时就会被挂起；当互斥量解锁后，等待的线程会被唤醒对互斥量进行访问

条件变量

用来锁定一个线程，直到设定的事件发生之后为止。条件变量是利用线程间共享的全局变量进行同步的一种机制。条件的检测是在互斥锁的保护下进行的。线程在改变条件变量的状态前需要先锁定互斥量

信号量

信号量分为有名信号量和无名信号量，无名信号量用于线程同步，有名信号量一般用于进程之间管理。

信号量本质上是一个非负的整数计数器，用于控制公共资源的访问，也被称为PV原子操作

P操作：信号量减一，若信号量小于等于0则阻塞，直到其大于0

V操作：信号量加一

死锁

线程需要以独占的形式访问资源时，可能会出现多个进程永远被阻塞的现象。

定义：一个进程集合中每个进程都在等待由此集合其他线程才能引发的事件，而无限陷入阻塞的现象，成为死锁

死锁产生的条件

1. 互斥条件：对于临界资源，进程会以独占/互斥方式访问（临界资源即独占资源）
2. 占有和等待条件：进程在获取不到资源而等待的时候，不会释放已占资源
3. 不剥夺条件：进程只能由进程自愿释放，不会被其他进程剥夺
4. 循环等待条件：等待链中每一个进程都在等待下一个进程所持有的资源

死锁的避免

针对每一个行程条件，破坏条件即可防止死锁

1. 互斥条件：将互斥访问改成共享访问，就不会有进程阻塞。但是这只适合某些资源，临界资源只允许互斥访问

2. 占有与等待条件：采用静态分配的方式，即进程必须在执行之前就申请所需的全部资源，全部满足才开始执行。但是这会影响资源的利用效率。

3. 不剥夺条件：占有资源的进程若要申请新资源，必须主动释放已占有资源，若需要此资源，应该向系统重新申请。

4. 循环等待条件：采用层次分配策略，给资源（锁）分级。一个进程的到某层的资源，只能申请更高一级的资源，而想要释放某层资源时，先要释放较高层的资源。同层之间是互斥的

没读完的链接

进程的组成

定义：进程是程序在数据集合上的运行过程（在系统中正在运行的程序），是系统进行资源分配和调度的独立单位（是系统资源分配的单位）。

组成

进程是由程序控制块（PCB）、程序段、数据段组成的。

程序控制块：

1. 进程描述信息：进程标识符，用户标识符
2. 进程控制和管理信息：进程当前状态，进程优先级
3. 资源分配清单：程序段、数据段指针，IO设备（键盘鼠标等）
4. 处理器相关信息：寄存器和程序计数器的值（切换进程时需要保存）

程序段：

存放要执行的代码

数据段：

存放运行过程中处理的各种数据

进程的组织方式

进程的组织方式分为：链接方式和索引方式

链接方式

按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针。通常队列中优先级高的进程放在队头

[图片上传失败...(image-eeb71e-1691243406207)]

索引方式

根据进程的状态不同，建立几张索引表，操作系统持有指向各个索引表的指针。

[图片上传失败...(image-bcd8ae-1691243406207)]

进程间通信方式

管道

包括匿名管道(pipe)和命名管道(fifo)

匿名管道是半双工的，有固定的读端和写端，只能用于具有亲缘关系的的进程之间的通信。可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。它通过pipe()系统调用来创建并打开，当最后一个使用它的进程关闭对他的引用时，pipe将自动撤销。

命名管道在磁盘上有对应的节点，但没有数据块，通过mknode()系统调用或者mkfifo()函数来建立的。。一旦建立，任何进程都可以通过文件名将其打开和进行读写，而不局限于父子进程，当然前提是进程对FIFO有适当的访问权。当不再被进程使用时，FIFO在内存中释放，但磁盘节点仍然存在。使用open()函数通过文件名可以打开已经创建的命名管道；可以用删除普通文件的方法将其删除，实际删除的是磁盘上对应的节点信息。

除了建立、打开、删除的方式不同外，这两种管道几乎是一样的。

管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据：管道一端的进程顺序地将进程数据写入缓冲区，另一端的进程则顺序地读取数据，该缓冲区可以看做一个循环队列

消息队列

消息队列，就是一个消息的链表，是一系列保存在内核中消息的列表。

消息队列与管道通信相比，其优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件接收特定类型的消息。

共享内存

共享内存允许两个或多个进程共享一个给定的存储区，这一段存储区可以被两个或两个以上的进程映射至自身的地址空间中。

采用共享内存进行通信的一个主要好处是效率高，对于像管道和消息队里等通信方式，需要在内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次。

有两种实现方式：内存映射和共享内存机制

信号量

信号量（semaphore）是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。

每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。

套接字

信号

是一种软中断

没看完的链接

进程调度策略

批处理系统常用：

先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。

短作业优先调度算法

它们可以分别用于作业调度和进程调度。短作业优先(SJF)/短进程优先(SPF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业/进程，将它们调入内存运行/将处理器分配给它。

高优先权优先调度算法

1. 非抢占式优先权算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成
2. 把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。
3. （容易出现优先级反转问题）优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源，而低优先级任务由于优先级较低可能会被中优先级的任务阻塞，无法运行释放资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。

高相应比优先调度算法

在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理器。

分时系统常用：

时间片轮转调度

也就是时分复用。系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。

多级反馈队列调度

目前被公认的一种较好的进程调度算法。

1. 设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
2. 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去
3. 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，由调度程序把正在运行的进程放回到第i队列的末尾

单比例调度

限期调度

最少裕度法

进程的内核栈/用户栈

定义

内核在创建进程的时候，在创建task_struct的同时，会为进程创建相应的堆栈。每个进程会有两个栈，一个用户栈，存在于用户空间，一个内核栈，存在于内核空间。

当进程在用户空间运行时，cpu堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；

当进程在内核空间时，cpu堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈。

区别

内核栈是属于操作系统空间的一块固定区域，可以用于保存中断现场、保存操作系统子程序间相互调用的参数、返回值等。

用户栈是属于用户进程空间的一块区域，用户保存用户进程子程序间的相互调用的参数、返回值等。

虚拟内存

页面置换算法

缺页中断（Page fault，又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等）指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由中央处理器的内存管理单元所发出的中断。

进程运行过程中，如果发生缺页中断，而此时内存中有没有空闲的物理块是，为了能够把所缺的页面装入内存，系统必须从内存中选择一页调出到磁盘的对换区。但此时应该把那个页面换出，则需要根据一定的页面置换算法（Page Replacement Algorithm)来确定。

LRU 最久未使用置换算法

原理：可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时，便将该页面号压入栈顶，其他的页面号往栈底移，如果内存不够，则将栈底的页面号移除。这样，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未访问的页面的页面号。

缺点：如果真的用栈来实现的话会有大量的内存拷贝操作，性能太差

链表实现

每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

缺点：链表在定位数据的时候时间复杂度为O(n)。

使用HashMap+双向链表实现

使用HashMap来定位页面，HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点。如果存储满了，可以通过O(1)时间淘汰掉链表尾部的节点，每次新增或者访问数据，都可以通过O(1)的时间把新的节点增加到队头，或者把已经存在的节点移动到队头

[图片上传失败...(image-3c2add-1691243406207)]

内存映射

mmap()输入文件描述符与文件大小，返回一个指针ptr，它指向进程虚拟地址空间中的一个地址，可以通过指针直接对文件进行操作，而无需使用read/write函数。

但是mmap只是建立映射，并没有实际拷贝数据，当第一次对该指针内容进行读写时，MMU无法找到对应的物理地址，会产生一个硬缺页异常，从硬盘上将文件读取到物理内存中，然后再进行读写

效率

如果需要读写文件，需要使用系统调用read将文件从磁盘读入内核缓冲区，然后拷贝至用户空间，（使用系统调用write是反向的过程），需要两次数据拷贝。

而mmap在调用时不拷贝，在缺页异常处理时将数据读入物理内存，然后直接映射到用户空间，只需要一次数据拷贝。

缺页异常

当cpu通过一个虚拟地址访问内存时，如果页表中没有创建该虚拟地址到物理地址的映射，或者这个物理页面不可读/写时，就会产生一个缺页异常

产生缺页异常的情况

1. 访问的内存非法（比如内存地址越界访问、对空指针解引用）
2. 地址合法，但是还没有建立与物理地址的映射

缺页异常的分类

• 硬件缺页(Hard Page Fault): 此时物理内存中没有对应的页帧，需要CPU从已经打开的磁盘文件中读取相应的内容到物理内存，再让MMU建立虚拟地址和物理地址的映射
• 软缺页(Soft Page Fault): 此时物理内存中存在对应的页帧，只不过可能是其他进程调入，发生缺页异常的进程不知道，此时MMU只需要重新建立映射即可，无需从磁盘写入内存，一般出现在多进程共享内存区域
• 无效缺页(Invalid Page Falut): 比如进程访问的内存地址越界访问，空指针引用就会报段错误等

栈帧

每一次我们调用一个函数，函数都会为自己创建一个Stack Frame（栈帧），并且只给自己用。对于Stack来说，是从高地址开始向低地址使用。（而堆是从低向高生长的）

有两个重要的寄存器：

1. SP（Stack Pointer），它指向Stack的底部并代表了当前Stack Frame的位置。
2. FP（Frame Pointer），它指向当前Stack Frame的顶部。

一个函数的Stack Frame包含了保存的寄存器，本地变量，并且，如果函数的参数多于8个，额外的参数会出现在Stack中。

Stack Frame的大小是不一样的。但是有两件事情是确定的：

• Return address总是会出现在Stack Frame的第一位

• 指向前一个Stack Frame的指针也会出现在栈中的固定位置（比如在ReturnAddress之后）

陷阱帧

每个进程都有一个独立的陷阱帧（trapframe），在虚拟空间中被映射到同一个虚拟地址，用于保存CPU的寄存器信息。在编程时它可看作是一个结构体。

计算机网络

字节序问题

分类

• 大端字节序（网络字节序）：数据的高位字节(23-32bit)存储在内存的低字节处，而数据的低位字节(0-7bit)存储在内存的高字节处
• 小端字节序（主机字节序）：数据的高位字节(23-32bit)存储在内存的高字节处，而数据的低位字节(0-7bit)存储在内存的低字节处

用法

发送端总是要把数据转为大端字节序后再发送出去，而接收端可以默认收到的数据为大端字节序，按照需要决定是否转换。（注：同一个主机上不同进程进行通讯也要考虑字节序问题，如编写语言不同）

TCP/IP五层协议

应用层

传输层

网络层

网络层实现数据包的选路和转发。通信的两台主机一般不是直接联通的，而是通过多个中间节点连接的，网络层就是选择这些中间节点，确定两台主机之间的通信路径。

核心协议：IP协议。

IP协议根据数据包的目的IP地址来决定如何转发它。如果数据包不嫩发送给目标主机，就发送给合适的下一跳路由器。经过重复转发到达目的主机。

补充：ICMP协议。它是因特网控制报文协议，用于检测网络连接。可分为两大类：差错报文，用于回应网络错误；查询报文，用于查询网络信息（ping）。而ICMP不属于严格意义上网络层的协议，因为它使用处于同一层的IP提供的服务

IP路由：决定数据报到目标主机的路径，应该发送至哪一个下一跳路由。通过路由表实现IP路由，路由表根据目标IP地址分类，同一类型的IP数据报将被发到相同的下一跳路由器，否则选择默认路由项：网关。

路由表可以动态、静态更新：1. 静态更新。通过route命令或者其他工具手工修改路由表。2.通过BGP（边际网关协议）、RIP（路由信息协议）、OSPF等协议发现路径并动态更新路由表。

数据链路层

物理层

TCP如何保证可靠传输

• 建立连接：通过三次握手建立连接，保证连接实体真实存在
• 序号机制：保证数据是按序、完整到达
• 合理分片：tcp会按最大传输单元(MTU)合理分片，接收方会缓存未按序到达的数据，重新
  排序后交给应用层。
• 数据校验：TCP报文头有校验和，用于校验报文是否损坏
• 超时重传：如果发送一直收不到应答，可能是发送数据丢失，也可能是应答丢失，发送方再等待一段时间之后都会进行重传。
• 流量控制：当接收方来不及处理发送方的数据，能通过滑动窗口，提示发送方降低发送的速率，防止包丢失。
• 拥塞控制：网络层拥堵造成的拥塞，包括慢启动，拥塞避免，快速重传三种机制

TCP三次握手四次挥手

[图片上传失败...(image-7f3bf8-1691243406207)]

三次握手

刚开始客户端处于 Closed 的状态，而服务端处于 Listen 状态

-- 客户端：发送SYN报文，指定初始化序号X（SYN = 1，seq=X） ->SYN-SENT

-- 服务端：发送应答报文ACK和SYN报文，发送确认序号为X+1，同时指定一个序号Y（ACK=1，ack=X+1；SYN=1，seq=Y ）->SYN-RECEIVED

-- 客户端：发送应答报文ACK，发送确认序号Y+1，并指明此时客户端的序列号 seq = X + 1（ACK=1， ack=Y+1，seq=X+1） ->ESTABLISHED（服务器收到之后也变成这个状态）

[图片上传失败...(image-f92999-1691243406207)]

为什么要三次握手，两次不行吗

三次握手是为了双方确认自己与对方的发送与接收是正常的。

如果只有两次挥手，不足以让服务器端确定自己的发送是否正常。若是服务器发送的应答报文丢失，客户端会认为连接未建立，从而继续发送请求。而此时服务器认为已经建立连接，会认为这些请求来自别的客户端，继续分配资源，也无法开始通信。

握手过程中的报文可以携带数据吗

没看完的链接

四次挥手

双方都处于ESTABLISHED 状态

-- 主动方：发送FIN报文，并指定序列号u（FIN=1，seq=u）->FIN-WAIT-1

-- 被动方：发送应答报文ACK，并返回确认序号u+1，并随机发送序列号（ACK=1，ack=u+1，seq=？） ->CLOSE-WAIT（主动方收到后->FIN-WAIT-2）

如果被动方也想断开连接（剩余内容发送完后）

-- 被动方：发送FIN报文，并指定序列号w（FIN=1，seq=w, ack=u+1） ->LAST-ACK

-- 主动方：发送ACK报文，发送确认序列号w+1，并且发送u+1作为自己的序列号（ACK=1， ack=w+1，seq=u+1） ->TIME-WAIT（被动方收到后进入CLOSED）

经过2MSL（一个报文来回的时间）后，主动方才会进入CLOSED状态

[图片上传失败...(image-97d08b-1691243406207)]

主动方为什么要等待2MSL

（MSL：“报文最大生存时间”，他是任何报文在网络上存在的最长时间，超过这个时间报文将被丢弃。）

为了确保被动方收到自己的应答报文，如果在规定时间内被动方没收到应答报文，就会再次发送FIN报文，那么主动方就知道之前的报文丢失，从而重新发送应答报文。

为什么需要四次挥手，而不像三次挥手那样

TCP 连接的一端在结束它的发送后还能接收来自另一端数据的能力（半关闭特性），任何一方都可以在数据传送结束后发出连接释放的通知，待对方确认后进入半关闭状态。主动方提出关闭连接，被动方可能还有数据没发送完，所以在发送完后再连接释放通知，对方确认后就完全关闭了TCP连接。

通俗的来说，两次握手就可以释放一端到另一端的 TCP 连接，完全释放连接一共需要四次握手。

UDP

UDP报文格式

UDP报文由UDP头部和数据组成。UDP头部里包含：源端口、目标端口、数据包长度、校验值

1. 数据包长度指的是数据长度加上UDP头部的长度
2. 如果校验和出错，则直接丢弃
3. 数据包长度大小为16位，即数据长度最大不超过64k（算上头部，比64k还小）

UDP的特点

1. 无连接：只要知道目的ip和端口即可发送，不需要建立连接
2. 不可靠：没有确认机制，没有重传机制。如果因网络问题没有发送成功，应用层也不会收到错误信息
3. 面向数据包：应用层交给UDP的数据包，UDP会原样发送，不会拆分，也不会合并
4. 没有发送缓冲区，但有接收缓冲区：因为UDP是不可靠的，没有重传机制，不需要发送缓冲区

TCP与UDP的区别

1. TCP是有连接的，UDP是无连接的
2. TCP建立一对一的通信，UDP可以一对一、一对多、多对多
3. TCP提供可靠传输，通过序号机制、确认应答、超时重传、拥塞控制等机制，而UDP只提供尽可能交付
4. TCP头部占的空间较大（20字节），UDP头部占的空间较少（8字节）
5. TCP的开销较大，UDP的开销比较小
6. TCP提供可靠的传输，适用于对通讯质量要求高的场景，而UDP传输效率高，适合

Http基础

请求：GET和POST的区别

HTTP请求报文由请求行（request line）、请求头部（header）、空行和请求数据（request body）四部分组成

1. GET把参数包含在URL中，POST通过request body传递参数
2. 由于GET把参数包含在URL里，所以GET的参数会被浏览器缓存（隐私性较差），会被完整地保存在历史记录里，而POST不会
3. 由于GET把参数包含在URL中，所以GET请求的参数是有长度限制的，通常是在2K以下
4. GET产生1个TCP数据包，而POST产生2个TCP数据包：GET将header和data一并发送出去，服务器返回响应200ok；而POST先发送header，然后服务器返回响应100continue，然后浏览器再发送data部分，服务器响应200ok

响应报文

HTTP状态码

一共有5种类型：

1xx：指示信息，表示请求已接受，继续处理

100 continue

2xx：成功，表示请求正常处理

200 OK：客户端请求正常处理

206 Partial content：客户端进行了范围请求，用于断点续传

3xx：重定向，需要进一步操作

301 Moved Permanently：永久重定向，资源已经移动到新位置

302 Found：临时重定向

4xx：客户端错误，服务器无法处理

400 Bad Request：请求报文语法错误

403 Forbidden：请求被服务器拒绝

404 Not Found：请求不存在

5xx：服务器错误

500 Internal Server Error：服务器处理请求时出错

HTTP缓存技术

强制缓存

只要浏览器判断缓存没有过期，则直接使用浏览器的本地缓存，决定是否使用缓存的主动性在于浏览器这边。

1. 头部Cache-Control 是一个相对时间。实现流程如下
   • 浏览器第一次请求该资源时，服务器返回资源的同时，会在响应报文的头部加上Cache-control，设置了缓存的有效期
   • 浏览器再次访问该资源时，会先计算Cache-Control的过期时间，如果还没过期，则使用本地数据
   • 服务器再次收到请求后，会更新Cache-Control
2. Expires是一个绝对时间

协商缓存

某些请求的响应码是 304，这个是告诉浏览器可以使用本地缓存的资源，通常这种通过服务端告知客户端是否可以使用缓存的方式被称为协商缓存。

1. 请求头部的If-Modified_Since和响应头部的Last-Modified
   • Last-Modified：标示这个响应资源的最后修改时间
   • If-Modified_Since：当资源过期后，浏览器发现响应头中有 Last-Modified，则在请求报文If-Modified_Since头部设成 Last-Modified时间给服务器。服务器收到这个头部会对比资源的最后修改时间，如果需要更新，则返回资源以及200OK；如果不需要更新，则返回304。
2. 请求头部的 If-None-Match 和响应头部的 ETag
   • Etag：唯一标识响应资源
   • If-Not-Match：当资源过期时，浏览器发现响应头里有Etag，则在请求报文中将If-Not-Match值设为ETag的值。服务器收到这个头部会与资源进行对比，如果没有变化，则返回304；如果变化了，则返回资源和200OK。

HTTP与HTTPS的区别

1. 从是否加密上看：HTTP是超文本传输协议，消息明文传输，存在安全风险；而HTTPS在HTTP和TCP之间加入了SSL/TLS安全协议，使得报文可以加密传输
2. 从建立连接上看：HTTP的建立相对简单，只需要TCP三次握手即可进行传输；而HTTPS在TCP三次握手后，还需要进行SSL/TSL的握手过程，才可以进行加密报文传输
3. 默认端口不一样，HTTP是80，HTTPS是443
4. HTTPS协议需要向证书权威机构（CA）申请数字证书，保证服务器身份是可信的

HTTP存在的风险以及HTTPS如何解决

HTTP存在三大风险：

1. 窃听风险：明文传输，通信链路上可以获取通信内容
2. 篡改风险：消息报文容易被篡改
3. 冒充风险：服务器的身份可以被冒充

HTTPS的解决方法：

1. 信息加密：使用混合加密方式实现消息的机密性
2. 校验机制：使用摘要算法来检验消息的完整性，为数据生成唯一的指纹用于校验数据的完整性，防止被篡改
3. 身份证书：将服务器公钥放入到数字证书中交给证书权威机构，保证身份可信

HTTPS如何建立连接

1. TCP三次握手
2. SSL/TSL四次握手
   1. 客户端握手：客户端发送一个随机数、SSL版本号、加密套件列表
   2. 服务端握手：服务端发送一个随机数、确认SSL版本号、加密套件，并发送服务器的证书
   3. 客户端回应：客户端向CA验证服务器证书，取出服务器公钥，用于加密报文。报文包括一个随机数、加密通信算法改变通知、客户端握手结束通知（上述三个随机数用于计算出会话密钥，之后的通信就用这个会话密钥）
   4. 服务端回应：服务器用私钥解密报文，取出随机数，计算出会话密钥。向客户端发送加密通信算法改变通知、服务端握手结束通知。

HTTP/1

HTTP/1.1相对于HTTP/1.0的改进

1. HTTP/1.1新增了长连接，改善了短连接带来的开销（长连接：只要任意一端没有明确提出断开连接，则保持 TCP 连接状态，使用connection:Keep-Alive头部）
2. HTTP/1.1新增了管道网络传输，第一个请求发出去后，不需要等其回来，就可以发第二个请求，减少了响应时间。

HTTP/1.1的优点

1. 简单：报文格式是header+body，头部信息也是 key-value 简单文本的形式
2. 灵活和易于拓展：
   1. 报文的URL、请求头部和状态码都没有固定，可以自己拓展
   2. 工作在应用层，下层可以拓展：比如加上SSL层(HTTPS)，将TCP换成UDP(3)
3. 应用广泛、跨平台

HTTP的缺点

1. 无状态带来的缺点：完成有关联性的操作时会非常麻烦（无状态的好处是不需要额外的资源来记录状态信息，减轻服务器的负担）
2. 不安全
   1. 明文传输，信息容易被窃听
   2. 不验证通信方身份，容易被伪冒
   3. 不验证报文完整性，信息容易被篡改

对应的解决方式

1. Cookie：在请求和响应报文中写入 Cookie 信息来控制客户端的状态
   • 客户端第一次请求时，服务端为该客户端生成Cookie，并在响应报文中带上Cookie信息
   • 客户端保存下Cookie，后续客户端请求服务时带上Cookie信息，服务端就能认出客户端
2. 加上SSL/TLS层

C++基础

C++编译过程

编译

1. 预处理：（.i）

   预处理会处理所有的预处理指令，如#include、#define、#ifndef，将指令替换成对应的代码，生成一个新的文本，这个文本就是编译器的输入

2. 编译（.s）

   进行词法分析、语法分析等工作，将代码转换成中间代码，并对代码进行优化，提高程序的运行效率与节省内存空间

3. 汇编（.o）

   将中间代码汇编成机器指令，使得处理器可以直接执行，每个源文件汇编成一个目标文件

链接

汇编程序生成的目标文件并不能立即就执行:(1)某个源文件用了另一个源文件的函数或常量；(2)某个源文件调用了某个库中的函数。

链接的过程就是将有关的目标文件链接起来，生成可执行文件。

C与C++的特点

C语言：

1. C语言是面向过程的结构化语言，易于维护
2. 可以直接访问内存的物理地址
3. C语言的效率高，实现了对硬件的编程

C++：

1. C++在C语言的基础上扩充，成为了一种面向对象的语言
2. 使用抽象数据进行基于对象的编程，可以使用多继承、多态等特性
3. 可以以模版为特征的泛型化编程

C与C++的区别

1. C语言是面向过程语言，而C++是面向对象语言
2. C是C++的子集，C++对C进行了丰富的拓展
3. C++引入了新的特性比如重载函数、引用、类、对象、继承
4. C++还引入了new/delete关键字，用来代替C语言中的malloc()/free()函数

GDB调试

1. 首先要生成可供GDB调试的可执行文件：编译时加入-g选项
2. 启动GDB调试器：gdb 可执行文件
3. 开始调试，有如下常用调试选项，括号中的是缩写：
   1. (b)break xxx：在源代码指定的某一行设置断点，其中 xxx 用于指定具体打断点的位置。
   2. (r)run：执行程序，其会自动在第一个断点处暂停执行。
   3. (c)continue：程序在断点停止后，可选择继续执行，直至遇到下一个断点或者程序结束。
   4. (n)next：令程序一行代码一行代码地执行
   5. (p)print xxx：打印指定变量的值，其中xxx表示某一变量名。
   6. watch xxx：关注某个变量，变量发生变化时会打印出来，xxx表示某一变量名
   7. (l)list：显示源程序代码的内容，包括各行代码所在的行号。
   8. (q)quit：终止调试

const修饰的变量可以修改吗

可以。在C语言中，const变量只不过是修饰该变量名，它并不能使内存变为只读。也就是说，我们不能通过变量名再去操作这块内存。但是可以通过其它方法，如指针，通过指针是可以修改被const修饰的那块内存的。

我定义一个指针，指向a变量所代表的内存，然后修改这个指针指向的内存。

为什么模版编程需要把实现放在头文件中

C++编译器在编译代码时是以cpp为单位的，常把cpp叫做翻译单元。至于头文件，在预处理的时候都以文本复制的形式变成cpp的一部分了。cpp文件里如果使用了模板（实例化），那么在它之前必须要有模板的定义（实现）。这和非模板函数不同，函数使用时只要有声明，不用有定义。

因为这个限制，如果你的模板要给多个cpp使用，那就必须保证这些cpp都能看到你的模板定义（而不只是声明）。

如果把同一个模板的定义复制多份分别放到不同的cpp里面去是极其危险的做法：当C++编译器编译每一个翻译单元时，它会将实例化的模板记录下来。然后在链接阶段，比对所有翻译单元中是不是用到了相同的模板实例（比如f<int>()），最后把所有相同的模板实例合并成一个，合并的时候，它会随机**的保留某一个翻译单元中的定义，把其他的全部丢弃。如果一旦不同翻译单元中，同一个模板的定义不一致会未知的问题。

C++不同的锁：

互斥锁

为了避免多个线程在某一时刻同时操作一个共享资源。在某一时刻，只有一个线程可以获取互斥锁，在释放互斥锁之前其他线程都不能获取该互斥锁。如果其他线程想要获取这个互斥锁，那么这个线程只能以阻塞方式进行等待。

条件锁

条件锁就是条件变量，会阻塞线程直到满足某个设置的条件。一旦条件满足，会以“信号量”的方式唤醒一个因为该条件而被阻塞的线程。最为常见就是在线程池中，一开始任务队列为空线程都在阻塞状态；一旦有任务进来，就会以信号量的方式唤醒一个线程来处理这个任务。

自旋锁

互斥锁是一种sleep-waiting锁：假设线程T1获取互斥锁并且在core1上运行，而线程T2也想获取该锁，则T2则会处于阻塞状态，被放入到等待队列中，但是处理器core2会去处理其他任务，不必一直等待（忙等）。也就是说处理器不会因为线程阻塞而空闲着。

自旋锁是一种busy-waiting锁：如果T1正在使用自旋锁，而T2去申请该锁，就会出去阻塞状态。与互斥锁不同的是，此时运行T2的处理器回不断循环检查锁是否可用，直到获取这个自旋锁。

当发生阻塞时，互斥锁可以让CPU去处理其他的任务；而自旋锁让CPU一直不断循环请求获取这个锁。通过这个定义可知“自旋锁”是比较耗费CPU的。

读写锁

数据被多个进程共享，对数据的操作有两种：1.读操作，读取数据的内容而不会修改数据；2.写操作，会修改数据的内容。

读写锁可以允许对这个数据同时执行多个读操作，但同一时刻只能有一个写操作更新数据。

在C++中，可以通过boost::shared_mutex来实现读写锁

1. 写线程通过std::lock_guard<boost::shared_mutex>和std::unique_lock<boost::shared_mutex>来独占访问
2. 读线程通过boost::shared_lock<boost::share_mutex>来共享访问

任意一个线程拥有共享锁，试图获得独占锁的线程会被阻塞；而如果有一个线程具有独占锁，其他线程都不能获取共享锁或独占锁。

锁的优化方式

1. 减少锁的持有时间（只在必须的时候持有锁）
2. 锁分离（使用读写锁替换互斥锁，在读多写少的情景可以有效提高性能。读写锁根据读写操作功能上的不同，进行了有效的锁分离。依据应用程序的功能特点，使用类似的分离思想）
3. 降低锁的粒度（比如在hashmap中分成不同的段，只对需要操作的段加锁）
4. 锁粗化（要是锁需要频繁申请和释放，也会影响性能，此时可以适当粗化）

unordered_map与map

unordered_map实现方式

hashmap，存储时时根据key的哈希值判断元素是否相同，所以unordered_map内部元素是无序的

将unordered_map用于自定义类型时，需要定义hash_value函数和重载operator==运算符

unordered_map如何防止冲突

使用开链法（又叫bucket，哈希桶）。

当同位置上的元素节点小于8个的时候， 这些数据会是一个链表式的方式组织起来；而当节点大于8个时，会转化为一个红黑树存储。

map的实现方式

红黑树，所以进行中序遍历会得到有序遍历。

将map用于自定义类型时需要重载operator<

STL

vector

vector的特点

1. 空间（容量）可以动态拓展，通常体现在push_back()和pop_back()上
2. 可以随机访问，支持像数组一样操作
3. 在内存中连续存储，节省空间
4. 在内部插入和删除操作效率比较低，这一点与数组是一样的
5. 只能在数组后面push和pop，而不能数组首部操作
6. 当动态添加的元素超过分配的内存大小时需要重新分配内存，并将原内容拷贝过去。扩容操作比较耗时，所以最好在定义时指定容量大小。

map

作为关联式容器的一种，map 容器存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。更确切的说，该容器存储的都是 pair<const K, T> 类型（所以键的内容一旦确定便不可改变）

为什么要用红黑树作为底层实现：

相对于unordered_map使用散列表（哈希表）实现，红黑树以O(logN)的时间复杂度进行插入、删除、查询操作。在插入和删除操作比较多的情况下，红黑树的效率比散列表要高。在查找方面，散列表的效率比红黑树要高。

重载

运算符重载

运算符重载方式有类内成员函数重载与全局友元函数重载两种

1. 一般情况下，单目运算符最好重载为类的成员函数；双目运算符则最好重载为类的友元函数。
2. 类型转换函数只能定义为成员函数，而不能使用友元函数重载。
3. 若运算符所需的操作数（尤其是第一个）希望有隐式类型转换，则只能选择友元函数重载。
4. 当使用成员函数重载时，最左边的操作数必须是类的对象。如果左操作数必须是不同类的对象，则需要选择友元函数重载。
5. 当需要重载运算符具有可交换性时，选择重载为友元函数

函数重载

重载与重写的区别

函数指针

1. 函数地址：

函数名就是函数指针，要将函数作为参数进行传递，必须传递函数名

2. 函数指针的声明：

声明指针时，必须指定指针指向的数据类型；而声明函数需要指明函数的类型（包括返回值与参数列表）

double (*pf)(int);  // 形参为int，返回类型为double的函数指针
char (*pf)(int, string);

3. 函数指针的调用

double d = pf(5);  // 通过函数调用
double d = (*pf)(5);  // 通过函数指针调用

void estimate(int line_num, double (*pf)(int lines))  // 函数指针作参数

智能指针

智能指针可以帮助管理动态分配的内存，避免内存泄露

智能指针类型：

（c++98）auto_ptr

（c++11）unique_ptr, shared_ptr, week_ptr

auto_ptr

定义了管理指针的对象，将new获得的地址赋给这个对象，可以像普通指针一样使用。当对象离开作用域时，析构函数将会调用delete来释放内存。

头文件：#include <memory>

用法：auto_ptr<T> 变量名(new T);

为什么智能指针可以像普通指针那样使用:

因为其里面重载了 *和 -> 运算符， * 返回普通对象，而 -> 返回指针对象。

成员函数

1. T* get()：获取智能指针托管的指针地址
2. T* release()：取消智能指针对动态内存的托管
3. void reset(T* ptr)：重置智能指针托管的内存地址，如果地址不一致，原来的会被析构掉

被替代的原因

1. 赋值和复制会改变资源的所有权，不符合人的直觉
2. 在STL容器中使用auto_ptr存在着重大风险，因为容器内的元素必须支持可复制和可赋值
3. 不支持对象数组的内存管理

unique_ptr

unique_ptr 用于取代auto_ptr，使用基本一致，除了一些特殊情况

unique_ptr特性（前两个为auto_ptr共有）

1. 基于排他所有权模式：两个指针不能指向同一个资源

2. 保存指向某个对象的指针，当它本身离开作用域时会自动释放它指向的对象。

3. unique_ptr无法进行左值复制构造，也无法进行左值复制赋值操作，但允许临时右值赋值构造和赋值（即用move将变量转为右值）

   unique_ptr<T> uni_p1 = uni_p2;  // 是不被允许的
   unique_ptr<T> uni_p1 = std::move(uni_p2);  // 是允许的
   

4. 在容器中保存指针是安全的，在 STL 容器中使用unique_ptr，不允许直接赋值

share_ptr

Share_ptr用于需要多个指针变量共享指定内存空间的时候。

用一种方式记录引用特定内存对象的智能指针数量，当复制或拷贝时，引用计数加1，当智能指针析构时，引用计数减1，如果计数为零，代表已经没有指针指向这块内存，那么该内存空间就被释放了。

use_count()函数可以获得当前托管指针的引用计数

初始化方式：

1. 构造函数 share_ptr<T> sp(new T(10)); // 也可以使用复制构造
2. make_share（分配效率更高） share_ptr<T> sp = make_share<T> (val);

分享：

sp2 = sp1;

主动释放：

sp = NULL; // 或者nullptr

重置：

1. 重置成空指针 sp.reset();
2. 重置成另一个指针 sp.reset(sp2);
3. 重置成另一个指针，并接受一个D作为原对象的内存删除器 sp.reset(sp2, D);

交换：

std::swap(sp1, sp2);

使用陷阱：shared_ptr作为被管控的对象的成员时，交叉互相持有对方的管理对象会造成内存泄露

weak_ptr

设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造，它的构造和析构不会引起引用记数的增加或减少。被称为weak_ptr是因为它只是指向对象，并不能进行操作。

注意：weak_ptr 没有重载*和->，但可以使用 lock 获得一个可用的 shared_ptr 对象

使用：

weak_ptr wp1;  // 定义空的弱指针
weak_ptr wp2(sp);  // 使用共享指针构造
wp3 = sp;  // 允许共享指针赋值给弱指针

sp.use_count();  // 它也可以获得引用计数

sp.expired();  //判断当前weak_ptr智能指针是否还有托管的对象，有则返回false，无则返回true
// 用于检查指针的合法性

// 需要使用时可转换成共享指针
sp_ = wp.lock();
// 使用完再释放
sp_ = NULL;

针对共享指针的使用陷阱：

在类中使用弱指针接管共享指针，在需要使用时就转换成共享指针去使用即可

使用场景

1. 观察者：可以用use_count观测资源引用计数，用expired观测资源是否销毁
2. 解决shared_ptr循环引用问题
3. 弱回调：一种“如果对象还活着就调用它的成员函数，否则忽略”的场景

共享指针的使用陷阱

不要把一个原生指针给多个智能指针管理

禁止用任何类型智能指针get 函数返回的指针去初始化另外一个智能指针！

右值引用

左值与右值

左值指既能够出现在等号左边，也能出现在等号右边的变量；右值则是只能出现在等号右边的变量。

1. 左值是可寻址的变量，有持久性
2. 右值一般是不可寻址的常量、无名的临时变量

右值引用的意义

无名的临时变量不能出现在赋值号左边，因而是右值。右值引用就可以引用无名的临时变量。

引入右值引用的主要目的是提高程序运行的效率。当类持有其它资源时，例如动态分配的内存、指向其他数据的指针等，拷贝构造函数中需要以深拷贝（而非浅拷贝）的方式复制对象的所有数据。深拷贝往往非常耗时，合理使用右值引用可以避免没有必要的深拷贝操作。

这里引入了移动语义，所谓移动语义（Move语义），指的就是以移动而非深拷贝的方式初始化含有指针成员的类对象。对于程序执行过程中产生的临时对象，往往只用于传递数据（没有其它的用处），并且会很快会被销毁。因此在使用临时对象初始化新对象时，我们可以将其包含的指针成员指向的内存资源直接移给新对象所有，无需再新拷贝一份，这大大提高了初始化的执行效率。

右值引用的格式

类型 && 引用名 = 右值表达式;

static关键字

static可用于修饰全局变量和局部变量->静态全局变量和静态局部变量

作用

1. 隐藏和隔离（针对于静态全局变量/函数）

全局变量（或函数）在各个源文件中都是可用的，有时我们会希望它只作用于本文件，而对外部文件不可用，所以使用static修饰

2. 保持变量内容的持久性（针对于静态局部变量，类的静态函数）

局部变量在函数退出后就会被回收，有时我们希望保留它所占用的内存空间，并保持它的值不变，所以使用static修饰

初始化时机

1. 在C语言中，全局变量、静态全局变量、静态局部变量都属于编译期初始化，即在程序运行前初始化

2. 在C++中，有三种情况：编译期初始化、加载时初始化、运行时初始化

   1. 编译期初始化：静态全局变量和静态局部变量都有可能。静态变量是基本数据类型，而且初始化值为常量
   2. 加载时初始化：是指静态全局变量在运行main函数前初始化。静态变量是基本数据类型但初始化值为变量；静态变量为类对象
   3. 运行时初始化：是指静态局部变量在第一次被引用时初始化。

Lambda函数

定义

lambda函数定义了一个匿名函数， 可以捕获一定范围的变量在函数内部使用

auto func = [capture](params)opt->ret {};

注意：

opt可省略，一般有：

1. mutable，可以修改按值传递进来的拷贝（注意是能修改拷贝，而不是值本身）
2. exception，指定函数抛出的异常，如抛出整数类型的异常，可以使用 throw ()

ret如果是基本数据类型，可自动推导

捕获列表

1. []：不捕捉任何变量
2. &：按引用传递捕捉外部作用域的所有变量
3. =：按值捕捉外部作用域的所有变量（将外部作用域的所有变量拷贝进函数，但在函数中是==只读==的）
4. var：按值传递捕捉var变量，同时不捕捉其他变量
5. &var：按引用传递捕捉var变量，同时不捕捉其他变量
6. =,&var：按值传递外部所有变量，并按引用捕捉var变量
7. this：捕获当前类的this指针，拥有与当前类成员同样的访问权限（如果用了&或=，默认会带上这个）

本质解析

为什么通过值拷贝的方式捕获的外部变量是只读的：

lambda表达式的类型在C++11中会被看做是一个带operator()重载的类，即仿函数。捕获的变量为类成员变量

按照C++标准，lambda表达式的operator()默认是const的，一个const成员函数是无法修改成员变量值的。

mutable 选项的作用就在于取消 operator () 的 const 属性。

对于没有捕获任何变量的 lambda 表达式，还可以转换成一个普通的函数指针

宏定义与内联函数

宏是在代码处不加任何验证的简单替代，而内联函数是将代码直接插入调用处

宏定义

1. 定义

   在形式及使用上像一个函数，但它使用预处理器、实现，没有了参数压栈，代码生成等一系列的操作。

2. 生效阶段：预编译阶段

3. 优缺点

   1. （优点）没有调用的开销，效率很高
   2. （缺点）只是在预处理阶段做简单替换，不会进行类型检查
   3. （缺点）如果操作涉及类的私有/保护成员，不能使用宏定义实现

内联函数

内联关键字：inline 关键词的本意是作为给优化器的指示器，以指示优先采用函数的内联替换而非进行函数调用，即并不执行将控制转移到函数体内的函数调用 CPU 指令，而是代之以执行函数体的一份副本而无需生成调用。这会避免函数调用的开销（传递实参及返回结果），但它可能导致更大的可执行文件，因为函数体必须被复制多次。

1. 定义

   内联函数是一个函数，为了解决一些频繁调用的小函数大量消耗栈空间的问题，特别的引入了inline修饰符。函数的代码被放入符号表（编译器的数据结构）中，在使用时直接进行替换（像宏一样展开），没有了调用的开销，效率也很高。而且可以进行参数类型检测、返回类型强制转换。

   它的作用是替代宏定义，消除宏定义的缺点。

2. 生效阶段：编译阶段

3. 优缺点

   1. （优点）没有调用的开销，效率很高
   2. （优点）inline函数是真正的函数，所以会进行一系列的数据类型检查、对返回做强制类型转换
   3. （优点）作为类的成员函数，可以使用类的保护成员及私有成员
   4. （缺点）函数体内的代码如果太长会消耗过多内存（生成的可执行程序会变大，影响cache对数据的命中）

4. 编译器拒绝inline关键字的情况：

   虚调用，函数体积过大，有递归，可变数目参数，通过函数指针调用

两者的区别

1. 生效阶段不同：宏定义在预编译时展开，内联函数在编译时展开；
2. 宏定义做简单的文本替换，内联函数直接插入到目标代码；
3. 内联函数是函数，有类型检测、语法判断等功能，而宏定义没有；
4. 宏定义要有可能会产生歧义，需要用括号括起来，内联函数不会。

内存泄漏的几个常见原因

内存泄漏的定义

用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元，直到程序结束。（程序结束后全都会由操作系统回收）

常见原因

1. 单例模式的对象生命周期与应用一样长，如果该对象已经不再使用了，但没有回收，就造成了内存泄漏
2. 析构函数没有释放申请的内存，或者忘记手动delete申请的内存
3. 基类的析构函数没有设为虚函数
4. 申请了堆内存的类没有重载合适的构造函数以及赋值运算符，导致浅拷贝，释放时会使堆内存崩溃
5. shared_ptr循环引用导致的问题：当类A和类B中分别含有类型为对方的智能指针，并且在各自创建实例a和b后，对实例a/b中的智能指针传入b/a进行了赋值。那么在离开作用域后，实例a和实例b中的智能指针引用计数都是1，但是都在等待对方释放后才能释放，这种情况便造成了循环引用的问题。

其他

QPS与TPS

QPS

即每秒查询量，对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准

计算方式：QPS = 并发量 / 平均响应时间

TPS

指每秒处理的事务数。一个事务是指一个客户机向服务器发送请求然后服务器做出反应的过程。TPS也称为每秒吞吐量

如何确定线程池的线程数量

参考链接

1. 经验

   1. CPU 密集型应用，线程池大小设置为 N + 1（+1是为了防止有线程意外阻塞）
   2. IO 密集型应用，线程池大小设置为 2N

2. 利特尔法则计算

线程池大小 = （（线程 IO time + 线程 CPU time ）/线程 CPU time ） CPU数目

当前公式理想状态下CPU利用率为100%，还可以乘上目标CPU利用率，便可以调节想要达到的的利用率

3. 压测指导