Cpp-Note.md

操作系统

Linux内存管理

LInux的内存管理采用了段页式管理，同时，使用伙伴关系系统和slab分配来进行物理内存的分配管理

• 虚拟地址空间

每个进程都有自己的虚拟内存地址空间，32位操作系统下是4GB的内存空间，这些虚拟内存通过页表映射到实际的物理内存，他们被操作系统的内核维护并被处理器使用。

每个进程都有自己的页表，一旦虚拟地址被使用，它们会被所有运行在机器上的软件所使用，包括内核自身。因此虚拟地址空间必须留一些给内核专用，这并不意味着内核使用如此多的物理内存，而只是意味着内核使用该段地址来映射它所使用的物理内存，内核空间在页表中会设定特权级标示，内核的代码和数据总是可以被寻址的，并且始终为处理终端或者系统调用做好准备，相反，用户模式的进程地址空间映射总是随着进程的切换而变化。

下面是标准的Linux进程的段空间分布：（蓝色区域表示映射到物理内存的虚拟地址，白色区域表示没有映射的区域）

具体分析：

1. 栈：进程最上面的段是栈，用来保存局部变量和函数参数，一个经常被使用的栈区域会被保存在CPU缓存中，从而加快访问速度。进程中的每个线程都有各自独立的栈。通过压入足够多的数据可以用完所有stack可以映射的空间，这就会导致页错误，从而被Linux的expand_stack()函数所处理，它又会调用acct_stack_growth()来判断是否可以增加栈的大小，如果栈的大小低于RLIMIT_STACK的限制，那么栈会增长，从而程序会继续运行。这就是通常的根据要求调整栈大小的机制。

   然而，如果达到了最大所允许的栈大小，就会导致栈溢出，从而引发一个程序的segmentation fault。当一个映射的栈区域根据需要而扩大了，它是不会随着栈变小而再缩减回来。动态的栈增长是唯一的一种合法的访问未被映射的内存区域的场景。任何访问一个为被映射的内存的行为都会触发一个页错误，从而导致segmentation fault。

2. Memory Mapping Segment：栈的下面是Memory Mapping Segment。这里被内核用来把文件内容直接映射到内存。所有的应用程序都可以使用Linux提供的mmap()系统调用进行映射。

   在Linux中，如果你通过malloc()来申请一块大的内存(指的是大于128K)，C库就会在Memory Mapping Segment中创建一个匿名Memory Mapping而不是使用堆空间。

3. 堆：堆提供了运行时的内存分配。如果有足够的堆空间来满足内存请求，它就可以被该语言的运行时环境所管理而不需要内核的干预。否则，堆通过内核提供的系统调用brk()来满足所请求的空间。

4. BSS段：BSS中存放的是没有初始化的静态变量，它的值没有被程序在代码中设置。BSS内存区是匿名的，它不会映射到任何文件。

5. Data段：数据段保存的是在代码中被初始化的变量。这个内存区不是匿名的。它映射了程序二进制文件中包含的被初始化了的变量。

6. 代码段：代码段是只读的并且所有的代码都会保存在这里。(虚函数表存放位置)

malloc()的底层实现

从操作系统角度来看，进程分配内存的方式有两种，分别是两个系统调用完成：brk和mmap。

1. brk的实现方式是将数据段的最高地址指针往高地址推（分配的内存小于128k）(堆中分配)
2. mmap的实现方式是在内存映射段找一块空闲的虚拟内存（分配的内存大于128k）(内存映射段中分配)

这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。

伙伴关系算法

1. 原理

Linux的伙伴算法把所有的空闲页面分为10个块组，每组中块的大小是2的幂次方个页面，例如，第0组中块的大小都为2^0，第1组中块的大小都为2，第9组中块的大小都为2^9。也就是说，每一组中块的大小是相同的，且这同样大小的块形成一个链表。

通过一个简单的例子来说明该算法的工作原理：

假设要求分配的块其大小为128个页面（由多个页面组成的块叫做页面快）。该算法现在块大小为128个页面的链表中查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块，具体的说，就是在块大小为256个页面的链表中查找一个空闲块。如果存在这样的空闲块，内核就把这256个液面分为2等分，一份分配出去，另一份插入到块大小为128个页面的链表中。如果在块大小为256个页面的链表中也没有找到空闲页块，就继续寻找。

以上过程的逆过程就是块的释放过程，这也是该算法名字的来由。满足以下条件的两个块称为伙伴：

• 两个块的大小相同
• 两个块的物理地址连续

伙伴算法把满足以上条件的两个块合并为一个块，该算法是迭代算法，如果合并后的块还可以跟相邻的块进行合并，那么就继续合并。

slab分配器(个人理解类似于对象池)

slab的出现一是为了避免类似于伙伴系统内存分配方法产生大量内部碎片的问题，二是作为一个高速缓存，可以存储经常分配并释放的对象（例如进程描述符）。

• slab分配器的基本原理

slab分配器中用到了对象这个概念，所谓对象就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。它的基本思想是将内核中经常使用的对象放到高速缓存中，并且由系统保持为初始的可利用状态。比如进程描述符，内核中会频繁对此数据进行申请和释放。当一个新进程创建时，内核会直接从slab分配器的高速缓存中获取一个已经初始化了的对象；当进程结束时，该结构所占的页框并不被释放，而是重新返回slab分配器中。如果没有基于对象的slab分配器，内核将花费更多的时间去分配、初始化以及释放一个对象。

slab分配器有以下三个基本目标：

1. 减少伙伴算法在分配小块连续内存时所产生的内部碎片；
2. 将频繁使用的对象缓存起来，减少分配、初始化和释放对象的时间开销；
3. 通过着色技术调整对象以更好的使用硬件告诉缓存。

• slab分配器的结构

slab分配器为每种对象分配一个高速缓存，这个缓存可以看做是同类型对象的一种储备。每个高速缓存所占的内存区又被划分多个slab，每个slab是由一个或多个连续的页框组成。每个页框中包含若干个对象，既有已分配的对象，也包含空闲的对象。

每个高速缓存通过kmem_cache结构来描述，这个结构中包含了对当前高速缓存各种属性信息的描述。所有的高速缓存通过双链表组织在一起，形成高速缓存链表cache_chain。每个kmem_cache结构中并不包含对具体slab的描述，而是通过kmem_list结构来组织各个slab。slab描述符中的list字符表明了当前slab处于三个slab链表中的其中一个。

堆栈

• 程序的内存分配

一个由C/C++编译的程序占用的内存分为以下几个部分：

1. 栈区——由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2. 堆区——一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。其分配方式类似于链表。
3. 全局区(静态区)(static)——全局变量和静态变量的存储是需要放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和静态变量在相邻的另一块区域，程序结束后由系统释放。
4. 文字常量区——常量字符串就是放在这里的。
5. 程序代码区——存放函数体的二进制代码。

//main.cpp 
int a = 0; 全局初始化区 
char *p1; 全局未初始化区 
main() 
{ 
int b; 栈 
char s[] = "abc"; 栈 
char *p2; 栈 
char *p3 = "123456"; 123456\0在常量区，p3在栈上。 
static int c =0； 全局（静态）初始化区 
p1 = (char *)malloc(10); 
p2 = (char *)malloc(20); 
分配得来得10和20字节的区域就在堆区。 
strcpy(p1, "123456"); 123456\0放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。 
} 

• 申请方式

栈区：由系统自动分配。系统自动为变量开辟空间。

堆区：需要程序员自己申请，并指明大小，在C中使用malloc函数，在C++中可以使用new运算符。

• 申请后系统的响应

栈区：只要栈的剩余空间大于所申请的空间，系统将为程序提供内存，否则将报异常提示栈溢出。

堆区：内存分配的一系列操作

• 申请效率

栈区：由系统分配，速度较快。但程序员无法控制

堆区：由new分配的内存，一般速度比较慢，而且容易产生内存碎片，但用起来最方便。

• 存储内容

栈：**在函数调用时，第一个进栈的是函数调用语句的下一条可执行语句的地址，然后是函数的各个参数，在大多数的C编译器中，参数是从右往左入栈的，然后是函数中的局部变量。**注意静态变量是存放在静态区的。

当本次函数调用结束后，局部变量先出栈，然后是参数，最后是主函数中的下一条指令。

堆：一般是在堆的头部用一个字节存放堆的大小。

• 存取效率的比较

char s1[] = "aaaaaaaaaaaaaaa"; 
char *s2 = "bbbbbbbbbbbbbbbbb"; 
//aaaaaaaaaaa是在运行时刻赋值的； 
//而bbbbbbbbbbb是在编译时就确定的； 
//但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。 因为s2首先要访问存放在栈上的指针本身，然后通过s2来访问常量区

Linux进程间通信方式

1. 管道(pipe)
2. 信号
3. 消息队列
4. 共享内存
5. 信号量
6. 套接字

• 管道
• • 匿名管道通信

匿名管道：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有父子关系的进程间使用。

//需要的头文件
#include <unisted.h>
//通过pipe()函数来创建匿名管道，fd[0]指向管道的读端，fd[1]指向管道的写端
int pipe(int fd[2]);

通过匿名管道实现进程通信的步骤：

• 父进程创建管道，得到两个文件描述符指向管道的两端
• 父进程fork出子进程，子进程也有两个文件描述符指向同一管道
• 父进程关闭fd[0]，子进程关闭fd[1]，即父进程关闭管道的读端，子进程关闭管道的写端。父进程可以往管道中写，子进程可以从管道里读。管道使用环形队列实现的，数据从写端流入从读端流出

管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据，管道一段的进程顺序的将数据写入缓冲区，另一端的进程则顺序的读出数据。

该缓冲区可以看做是一个循环队列，读和写的位置都是自动增长的，不能随意改变，一个数据只能被读一次，读出来以后在缓冲区就不复存在了。

当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写。

• • 有名管道通信

有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在与文件系统中，这样，即使与有名管道的创建进程不存在父子关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信。因此，通过有名管道，不相关的进程也能交换数据。

• 信号量

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

为了获得共享资源，进程需要执行下列操作：

1. 创建一个信号量：这要求调用者指定初始值，对于二值信号量来说，它通常是1，也可以是0
2. 等待一个信号量：该操作会测试一个信号量的值，如果小于0，就阻塞。也称为P操作。
3. 挂出一个信号量：该操作将信号量的值加1，也称为V操作。

• 消息队列

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

消息队列是消息的链表，具有特定的格式。允许一个或多个进程向它写入与读取消息。

消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比FIFO更有优势。

• 信号

信号是用于进程间相互通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。

如果该进程当前未处于执行状态，则该信号就有内核保存起来，直到该进程回复执行并传递给它为止。

如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消时才被传递给进程。

Linux系统中常用信号： **SIGHUP：**用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。 **SIGINT：**程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。 **SIGQUIT：**程序退出信号。程序运行过程中，按Ctrl+\\键将产生该信号。 **SIGBUS和SIGSEGV：**进程访问非法地址。 **SIGFPE：**运算中出现致命错误，如除零操作、数据溢出等。 **SIGKILL：**用户终止进程执行信号。shell下执行kill -9发送该信号。 **SIGTERM：**结束进程信号。shell下执行kill 进程pid发送该信号。 **SIGALRM：**定时器信号。 **SIGCLD：**子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。

• 共享内存

共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的通信方式，它是针对其他进程间通信方式运行效率低而专门设计的。

使得多个进程可以访问同一块内存空间。

为了在多个进程间交换信息，内核专门流出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间。进程就可以直接读写这一块内存而不需要进行数据的拷贝，从而大大提高效率。

• 套接字(socket)

线程间通信的方式

• 临界区

通过多线程的串行化来访问公共资源或者一段代码，速度快，适合控制数据访问

• 互斥量

采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问

• 信号量

为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。

• 事件(信号)

Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

零拷贝

在服务器中，经常通过read()/write()来进行数据的传输，这其中涉及到多次的内核态到用户态的拷贝，拿read()来说，系统首先会检查内核缓冲区，查看是否最近访问过该文件，如果没有，系统会首先将磁盘中的数据拷贝到内核缓冲区中，然后再从内核缓冲区拷贝到用户堆栈的缓冲区中。write()同理，先从用户缓冲区(用户态)拷贝到内核缓冲区(内核态)，然后再发送到网卡上。

零拷贝技术指在计算机执行操作时，CPU不需要先将数据从一个内存区域复制到另一个内存区域，从而可以减少上下文切换以及CPU的拷贝时间。它的作用是在数据报从网络设备到用户程序空间传递的过程中，减少数据拷贝次数，减少系统调用，实现CPU的零参与，彻底消除CPU在这方面的负载。

• 零拷贝机制可以减少数据在内核缓冲区和用户进程缓冲区之间反复的I/O拷贝操作。
• 零拷贝机制可以减少用户进程地址空间和内核地址空间之间因为上下文切换而带来的CPU开销。

在Linux中零拷贝技术主要有3个实现思路：用户态直接进行IO、减少数据拷贝次数以及写时复制技术。

• 用户态直接IO：应用程序通过使用mmap()可以直接访问硬件存储，操作系统内核只是辅助数据传输。这种方式依旧存在用户空间和内核空间的上下文切换，硬件上的数据直接拷贝到了用户空间，不经过内核空间。因此，直接IO不存在内核空间缓冲区和用户空间缓冲区之间的数据拷贝。
• 减少数据拷贝次数：在数据传输过程中，避免数据在用户空间缓冲区和系统内核空间缓冲区之间的CPU拷贝，以及数据在系统内核空间内的CPU拷贝，这也是当前主流零拷贝技术的实现思路。

多线程和多进程的区别

	多进程	多线程
数据共享、同步	数据是分开的，共享复杂：需要使用IPC，同步简单	共享进程数据，同步复杂
内存、CPU	占用内存多、切换复杂、CPU利用率低	占用内存少、切换简单、CPU利用率高
创建销毁、切换	创建销毁、切换复杂、速度慢	创建销毁、切换简单，速度快
编程调试	简单	复杂
可靠性	进程间不会互相影响	一个线程挂掉会导致整个进程挂掉
分布式	适用于多核、多机分布；如果一台机器不够，扩展到多台比较简单	适用于多核分布

线程和进程的区别

进程和线程的区别主要在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其他进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程没有单独的地址空间，一个线程挂掉就等于整个进程挂掉，所以多进程的程序要比多线程更健壮。但在进程切换过程中的开销较大，效率较低。但对于一些要求同时进行并且又要共享某些变量的并行操作来说，只能用线程而不能用进程。

1. 简而言之，一个程序至少有一个进程，一个进程可以有多个线程。
2. 线程的划分尺度小于进程，使得多线程的并发性较好
3. 进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
4. 每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。**但是线程不能够独立执行，**必须依存在应用程序中，由应用程序提供多个线程执行控制。
5. 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

协程

协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切换回来的时候，恢复之前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销。可以不加锁访问全局变量，所以上下文的切换非常快。

协程本质上就是单线程，多个协程协作好比就是你一个人其实同时只能做一件事，但是你把几个任务拆成几截来交叉执行。

就是只是中间加了 yield，让它跑了一半暂停执行，然后产出结果给调度它（这个协程）的父级上下文，如果父级不再需要执行下去了可以先调用别的函数，等别的 yield 了再 transfer 回去执行这个。

程序的编译过程

1. 预处理阶段，主要处理宏定义以及导入引入的文件
2. 编译阶段，将预处理阶段得到的文本文件翻译为汇编文件
3. 汇编，将汇编文件翻译成机器语言文件
4. 链接，导入引入的动态库和静态库

静态库和动态库的区别

• 静态库

之所以称为静态库，是因为在链接阶段，会将汇编生成的目标文件.o与引用到的库一起链接打包到可执行文件当中。因此对应的链接方式称为静态链接。

静态库的特点总结为：

1. 静态库对函数库的链接是放在编译时期完成的
2. 程序在运行时与函数库再无瓜葛，移植方便
3. 浪费空间和资源，因为所有相关的目标文件与牵涉到的函数库被链接合成一个可执行文件。

• 动态库

为什么需要动态库，其实也是静态库的特点导致：

1. 空间浪费
2. 静态库对程序的更新、部署和发布会带来麻烦，更新一次需要全部重新编译。

动态库在程序编译时不会被连接到目标代码中，而是在程序运行时才被载入。不同的应用程序如果调用相同的库，那么在内存中只需要有一份该共享库的实例，规避了空间浪费的问题。动态库在程序运行时才被载入，也解决了静态库对程序的更新带来的麻烦。

动态库特点总结：

• 动态库把一些库函数的链接载入推迟到程序运行的时期。
• 可以实现进程之间的资源共享
• 将一些程序的升级变得简单
• 甚至可以真正做到链接载入完全由程序员在程序代码中控制。

gcc的编译参数

-l链接库，-L库路径，-S得到汇编文件，-E得到预处理文件。

fork和vfork

fork创建子进程，返回两个值。返回0的时候代表这是子进程，大于0代表父进程。子进程共享父进程的地址空间以及继承打开的文件描述符。Linux采用的是写时复制技术，只有在父子进程尝试修改地址空间的时候，才会出发缺页中断处理程序进行真正的拷贝。

vfork和fork类似，都是采用写时复制技术，不过vfork保证子进程优先运行，直到子进程调用了exec或者exit才轮到父进程运行。

• fork所复制的内容

fork时子进程获得父进程的数据空间、堆栈的复制,以及共同的文件描述符（写时复制）。

僵尸进程和孤儿进程

所谓僵尸进程，是指子进程退出时，父进程并未对其发出的SIGCLD信号进行适当处理，导致子进程停留在僵死状态等待父进程对其进行善后处理。

设置僵死状态的目的是维护子进程的信息，以便父进程在以后某个时候获取。这些信息包括子进程的进程ID、终止状态以及资源利用信息。如果一个进程终止，而该进程有子进程处于僵死状态，那么它的所有僵死子进程的父进程ID将被重置为1(init进程)。继承这些子进程的init进程将负责清理他们。

危害：如果僵尸进程不进行处理的话，那么保留的进程信息就不会被释放，其进程号就会被一直占用，但是系统所能使用的进程号是有限的，如果大量的产生僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程。

孤儿进程指的是在一个有父子关系的进程中，父进程比子进程更早的结束了，此时子进程会被init进程接手并进行善后。

守护进程

守护进程是在后台运行不受终端控制的进程，一般的网络服务都是以守护进程的方式运行。守护进程脱离终端的主要原因有两点：

1. 用来启动守护进程的终端在启动守护进程之后，需要执行其他任务
2. 由终端上的一些键所产生的信号(如中断信号)，不应对以前从该终端上启动的任何守护进程产生影响。

通常来说，守护进程没有任何存在的父进程，且在Unix系统进程层级中直接位于init之下。守护进程程序通常通过如下方法使自己称为守护进程：

1. 对一个进程运行fork，然后让父进程立刻终止
2. 让子进程被init进程接收，在init下运行
3. 在子进程中使用setsid()创建新会话。

setsid函数用于创建一个新的会话，并担任该会话组的组长。调用setsid有三个作用：让进程摆脱原会话的控制、让进程摆脱原进程组的控制和让进程摆脱原控制终端的控制。

在调用fork函数时，子进程全盘拷贝父进程的会话期(session，是一个或多个进程组的集合)、进程组、控制终端等，虽然父进程退出了，但原先的会话期、进程组、控制终端等并没有改变，因此，那还不是真正意义上使两者独立开来。setsid函数能够使进程完全独立出来，从而脱离所有其他进程的控制。

4. 改变工作目录
5. 重设文件常见掩码

文件创建掩码是指屏蔽掉文件创建时的对应位。由于使用fork函数新建的子进程继承了父进程的文件创建掩码，这就给该子进程使用文件带来了诸多的麻烦。因此，把文件创建掩码设置为0，可以大大增强该守护进程的灵活性。设置文件创建掩码的函数是umask，通常的使用方法为umask(0)。

5. 关闭文件描述符

惊群效应

一组睡眠线程等待同一个资源，当该资源就绪的时候，会同时通知所有线程退出睡眠状态，然后所有线程对该资源进行争抢，最后只有一个线程获得该资源，这就是惊群效应。惊群效应往往会造成过多的系统开销。这时的解决方式一般是加锁和队列方式。使得资源满足时，只唤醒队列中的第一个线程即可。

Reactor模式/Proactor模式/半同步半异步模式

• Reactor模式

同步阻塞IO模式，注册对应读写事件处理器，等待事件发生进而调用事件处理器处理事件。具体的说就是：主线程往epoll内核上注册socket读事件，主线程调用epoll_wait等待socket上有数据可读，当socket上有数据可读的时候，主线程把socket可读事件放入请求队列。睡眠在请求队列上的某个工作线程被唤醒，处理客户请求，然后往epoll内核上注册socket写请求事件。主线程调用epoll_wait等待写请求事件，当有事件可写的时候，主线程把socket可写事件放入请求队列。睡眠在请求队列上的某个工作线程被唤醒，处理客户请求。

• Proactor模式

异步IO模式，主线程调用aio_read函数向内核注册socket上的读完成事件，并告诉内核用户读缓冲区的位置，以及读完成后如何通知应用程序，主线程继续处理其他逻辑，当socket上的数据被读入用户缓冲区后，通过信号告知应用程序数据已经可以使用。应用程序预先定义好的信号处理函数选择一个工作线程来处理客户请求。工作线程处理完客户请求之后调用aio_write函数向内核注册socket写完成时间，并告诉内核写缓冲区的位置，以及写完成时如何通知应用程序。主线程处理其他逻辑。当用户缓冲区的数据被写入socket之后内核向应用程序发送一个信号，以通知应用程序数据已经发送完毕。应用程序预先定义的数据处理函数就会完成工作。

• 半同步/半异步模式

上层的任务(如数据库查询，文件传输)使用同步IO模型，简化了编写难度

底层的任务(如网络控制器的中断处理)使用异步IO模型，提供了执行效率

原子操作

原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始就一直运行到结束。

实现原理：总线锁和缓存锁定

乐观锁和悲观锁

• 乐观锁

总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量。

版本号机制

一般是在数据表中加上一个数据版本号version字段，表示数据被修改的次数，当数据被修改的时候，version值会加1.当线程A要更新数据值的时候，在读取数据的同时也会读取version值，在提交更新的时候，若刚才读取到的version值和现在的version值相等时才更新，否则重试更新操作。

CAS算法

即compare and swap(比较和交换)，是一种有名的无锁算法、无锁编程，即不适用锁的情况实现多线程之间的变量同步。CAS涉及三个操作数：

• • 需要读写的内存值V
  • 进行比较的A
  • 拟写入的新值B

当且仅当 V 的值等于 A时，CAS通过原子方式用新值B来更新V的值，否则不会执行任何操作（比较和替换是一个原子操作）。一般情况下是一个自旋操作，即不断的重试。

缺点：1. ABA问题 2. 自旋CAS开销大 3. 只能保证一个共享变量的原子操作

• 悲观锁

总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁**（共享资源每次只给一个线程使用，使用其他线程阻塞，用完后再把资源转让给其他线程）**。

用户态和内核态

首先，要说的是Linux的整体架构

----------------------
|       应用程序      |
----------------------
|	库函数	 |	Shell  |
--------系统调用-------
|		  内核        |

可以知道，通过系统调用将Linux整个体系分为用户态和内核态。

那么内核态到底是什么呢？其实从本质上来说就是内核，它是一种特殊的软件程序，控制计算机的硬件资源，例如协调CPU资源，分配内存资源，并且提供稳定的环境供应用程序运行。

用户态就是提供应用程序运行的空间，为了让应用程序访问到内核管理的资源例如CPU，内存，IO。内核必须提供一组通用的访问接口，也就是所谓的系统调用。

• 系统调用

系统调用是操作系统的最小的功能单位。这些系统调用组成了用户态跟内核态交互的基本借口，例如：用户态想要申请一块20K大小的动态内存，就需要系统调用，将数据段指针向下偏移。

• 库函数

库函数就是屏蔽这些复杂的底层实现细节，减轻程序员的负担，从而更加关注上层的逻辑实现。它对系统调用进行封装，提供简单的基本接口给用户，这样增强了程序的灵活性，当然对于简单的接口，也可以直接使用系统调用访问资源，例如：open()，write()，read()。

• 如何实现用户态到内核态的切换

往往我们的系统资源是固定的，例如内存2G，CPU固定，磁盘2TB，网络接口固定。所以就需要操作系统对资源进行有效的利用。假设某个应用程序过分的访问这些资源，就会导致整个系统的资源被占用，如果不对这种行为进行限制和区分，就会导致资源访问的冲突。所以，Linux就将权限等级分为了2个等级，分别就是内核态和用户态。

用户态的进程能够访问的资源受到了极大的控制，而运行在内核态的进程不会受到限制。一个进程可以运行在用户态也可以运行在内核态，那它们之间肯定存在用户态和内核态切换的过程。举个例子：库函数接口malloc申请动态内存，malloc的实现内部最终还是会调用brk()或者mmap()系统调用来分配内存。

所以，从用户态到内核态的切换方式，可以通过系统调用来切换，当然还有其他方式：

1. 系统调用：其实系统调用本身就是中断，不过软件中断和硬件中断不同
2. 异常：如果当前进程运行在用户态，如果这个时候发生了异常事件，就会出发切换。例如：缺页异常
3. 外设中断：当外设完成用户的请求时，会向CPU发送中断信号。

• 为什么要分内核态和用户态

为了安全性。在cpu的一些指令中，有的指令如果用错，将会导致整个系统崩溃。分了内核态和用户态后，当用户需要操作这些指令的时候，内核为其提供了API，可以通过系统调用陷入内核，让内核去执行这些操作

虚拟内存

为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。

虚拟内存技术使得不同进程在运行空间中，它所看到的是自己独自占有了当前系统的内存。所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。事实上，在每个进程创建加载时，内核只是为进程“创建”虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好，等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中，要动态分配内存，比如malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。

虚拟内存的代价：

1. 虚拟内存的管理需要建立很多的数据结构，这些数据结构要占用额外的内存
2. 虚拟地址到物理地址的转换，增加了指令的执行时间
3. 页面的换入/换出需要磁盘IO，耗时
4. 如果一页中只有一部分数据，会浪费内存

缺页中断

在调用malloc()和mmap()等分配内存函数时，在分配时只是建立了进程虚拟地址空间，并没有分配虚拟内存对应的物理内存。当进程访问这些没有建立映射关系的虚拟内存时，处理器自动触发一个缺页异常。

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

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

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

但是缺页中断是由于所要访问的页面不存在于内存时，由硬件所产生的一种特殊中断，因此，与一般的中断存在差别：

1. 在指令执行期间产生和处理缺页中断信号
2. 一条指令在执行期间，可能多次产生缺页中断
3. 缺页中断返回时，执行产生中断的一条指令，而一般的中断返回时，执行下一条指令

缺页置换算法

当访问一个内存中不存在的页，并且内存已满，则需要从内存中调出一个页或将数据送至磁盘对换区，替换一个页，这种现象叫做缺页置换。当前操作系统最常采用的缺页置换算法如下：

先进先出(FIFO)算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。

最近最少使用（LRU）算法: 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。

当前最常采用的就是LRU算法。

进程调度算法

1. 先来先服务算法
2. 时间片轮转算法
3. 短作业优先算法
4. 最短剩余时间优先
5. 高响应比优先
6. 优先级调度
7. 多级反馈队列调度算法

死锁

• 产生的必要条件

1. 互斥条件
2. 请求与保持条件
3. 不剥夺条件：进程已经获得的资源，在使用完之前，不能强行剥夺
4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系

• 死锁的避免

1. 进程启动拒绝：如果一个进程的请求会导致死锁，则不启动该进程
2. 资源分配拒绝：如果一个进程增加的资源请求会导致死锁，则不允许这次分配（银行家算法）

• • 银行家算法
  1. 如果request<=need，转向步骤2；否则认为出错，因为请求资源大于需要资源。
  2. 如果request<=available，转向步骤3,；否则尚无足够资源，进程p阻塞；
  3. 系统尝试为把资源分配给进程P，并修改available、allocation和need的数值。
  4. 系统执行安全性算法，检查此次分配后系统是否处于安全状态，若安全，才正式将资源分配给进程P，否则将本次试探性分配作废，让进程P等待。

  安全状态：系统能按照某种进程顺序，为每个进程分配资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。

• 死锁的预防

1. 占有且等待：为预防占有且等待条件，可以要求进程一次性的请求所需要的资源，并且阻塞这个进程知道所有请求都同事满足
2. 不可抢占：1.如果占有某些资源的一个进程进行进一步资源请求时被拒绝，则该进程必须释放它最初占有的资源。2.如果一个进程请求当前被另一个进程占有的一个资源，则该操作系统可以抢占另外一个进程，要求它释放资源
3. 循环等待：通过定义资源类型的线性顺序来预防。如果一个进程已经分配了R类资源，那么接下来请求的资源只能是那些排在R类型后面的资源类型。

阻塞和非阻塞、同步和异步

阻塞和非阻塞关注的是程序在等待调用结果时的状态

• 阻塞与非阻塞
• • 阻塞调用会一直等待远程数据就绪在返回，直到读取结束
  • 非阻塞无论在什么情况下都会立即返回，虽然非阻塞大部分时间不会被阻塞，但是它仍要求进程不断的去主动询问内核是否准备好数据，也需要进程主动再次调用recvfrom来将数据拷贝到用户内存
• 同步与异步
• • 同步会一直阻塞进程，直到IO操作结束
  • 异步不会阻塞调用者的进程，即使是从内核空间的缓冲区将数据拷贝到进程中这一操作也不会阻塞。

使用EPOLL时需要将socket设置为非阻塞吗？

边沿触发的问题：

1. sockfd 的边缘触发，高并发时，如果没有一次处理全部请求，则会出现客户端连接不上的问题。不需要讨论 sockfd 是否阻塞，因为 epoll_wait() 返回的必定是已经就绪的连接，所以不管是阻塞还是非阻塞，accept() 都会立即返回。
2. 阻塞 connfd 的边缘触发，如果不一次性读取一个事件上的数据，会干扰下一个事件，所以必须在读取数据的外部套一层循环，这样才能完整的处理数据。但是外层套循环之后会导致另外一个问题：处理完数据之后，程序会一直卡在 recv() 函数上，因为是阻塞 IO，如果没数据可读，它会一直等在那里，直到有数据可读。但是这个时候，如果用另一个客户端去连接服务器，服务器就不能受理这个新的客户端了。
3. 非阻塞 connfd 的边缘触发，和阻塞版本一样，必须在读取数据的外部套一层循环，这样才能完整的处理数据。因为非阻塞 IO 如果没有数据可读时，会立即返回，并设置 errno。这里我们根据 EAGAIN 和 EWOULDBLOCK 来判断数据是否全部读取完毕了，如果读取完毕，就会正常退出循环了。

总结一下：

1. 对于监听的 sockfd，最好使用水平触发模式，边缘触发模式会导致高并发情况下，有的客户端会连接不上。如果非要使用边缘触发，可以用 while 来循环 accept()。
2. 对于读写的 connfd，水平触发模式下，阻塞和非阻塞效果都一样，建议设置非阻塞。
3. 对于读写的 connfd，边缘触发模式下，必须使用非阻塞 IO，并要求一次性地完整读写全部数据。

Linux命令

ping

ping程序是用来探测主机到主机之间是否可以通信的，使用的是ICMP协议，它发送icmp回送请求消息给目的主机。ICMP协议规定：目的主机必须返回ICMP回送应答消息给源主机。如果源主机在一定时间内收到应答，则认为主机可达。

ICMP协议通过IP协议发送的，IP协议是一种无连接的，不可靠的数据包协议。

ps

ps命令标识进程的5种状态码

D 不可中断 uninterruptible sleep (usually IO) 
R 运行 runnable (on run queue) 
S 中断 sleeping 
T 停止 traced or stopped 
Z 僵死 a defunct ("zombie") process 

也可以用下面的命令查看进程状态

ps -aux

top

top命令是Linux下常用的性能分析工具，能够实时显示系统中各个进程的资源占用状况，类似于Windows的任务管理器。

top是一个动态显示过程,即可以通过用户按键来不断刷新当前状态.如果在前台执行该命令,它将独占前台,直到用户终止该程序为止.比较准确的说,top命令提供了实时的对系统处理器的状态监视.它将显示系统中CPU最“敏感”的任务列表.该命令可以按CPU使用.内存使用和执行时间对任务进行排序；而且该命令的很多特性都可以通过交互式命令或者在个人定制文件中进行设定.

1．命令格式：
top [参数]

2．命令功能：
显示当前系统正在执行的进程的相关信息，包括进程ID、内存占用率、CPU占用率等

3．命令参数：
-b 批处理
-c 显示完整的治命令
-I 忽略失效过程
-s 保密模式
-S 累积模式
-i<时间> 设置间隔时间
-u<用户名> 指定用户名
-p<进程号> 指定进程
-n<次数> 循环显示的次数

4．使用实例：
实例1：显示进程信息
命令：
top

nohup

nohup的意思就是不挂断地运行命令，是no hang up的缩写，nohup命令忽略所有的挂断信号(SIGHUP) 语法：

nohup Command [ Arg ... ][ & ] 其中Command是指运行程序的命令，例如若要运行test.py程序，则Command部分就是python3 test.py。

• &

&是将进程提交到后台运行的命令，这样你就可以在控制台终端做其他事情，但是当把当前控制台(终端)关闭(退出账户)时，进程就会停止运行。 而nohup命令，可以保护进程在退出账户，释放连接后继续运行，所以使用该命令一般的形式是：

nohup command & &让进程转至后台运行，nohup让进程不会由于退出账户停止。

而如果想让进程停止，可以通过使用ps -ef来查看进程的pid。 然后kill掉pid来结束进程。

• 为什么关闭SSH连接，程序就停止运行？

要想回答这个问题，首先需要知道在Linux系统下有这两个概念： 进程组：一个或者多个进程的集合，每一个进程组都有唯一一个进程组ID，即进程组长进程的ID。 会话期：一个或多个进程组的集合，有唯一一个会话期首进程。会话期ID为首进程的ID。 会话期可以有一个单独的控制终端。与控制终端连接的会话期首进程叫做控制进程。当前与终端交互的进程称为前台进程组。其余进程组称为后台进程组。

挂断信号（SIGHUP）默认的动作是终止程序。 当终端接口检测到网络连接断开，将挂断信号发送给控制进程。 如果控制进程终止，则该信号发送到该会话期前台进程组。

结论：因此当网络断开或终端窗口关闭后，也就是SSH断开以后，控制进程收到SIGHUP信号退出，会导致该会话期内其他进程退出。

也就是说：当SSH连接开启的时候，bash等都会成为其进程组成员，当ssh关闭后，系统会将所有相关进程kill掉。

常用命令

1. 如何查看进程，如何查看线程，如何查看某个进程的线程,top -H [-p pid], ps -T [-p pid]。
2. 如何查看内存使用状况。 free
3. 如何查看磁盘的使用状况。df -h
4. 查看目录的使用状况。du -sh
5. 查看某个端口的使用状况。lsof -i:8088
6. 实时的查看日志文件。tailf -n 50 [fileName]
7. 查看某个日志文件中的内容。grep -i "xxx" file
8. 不想查看文件中的内容。grep -v "xxx" file，不想查看多个内容 grep -v "xxx | yyy" file
9. 取文件的前50行。head -n 50 file
10. 查看文件多少行。wc -l filename
11. 分割一个文件，以1000行为一个文件。spilt -l 1000 filename -d -a 5
12. 将一个文件中的A全部替换成B 。在命令行模式下 输入%s/A/B/g
13. 动态的查看进程状态，watch -nl "ps -ef" 或者 top
14. 显示1000行到3000行： cat filename |head -n 3000|tail -n +1000

C++

C++11新特性

1. 新增基于范围的for循环
2. 自动类型推断auto
3. 匿名函数
4. 后置返回类型
5. 显示重写(覆盖)override和final
6. 空指针常量 nullptr
7. long long int类型
8. 模板的别名
9. 运行sizeof运算符可以在类型数据成员上使用，而无需明确对象
10. 线程支持

C++11 实现原子操作

C++11通过引入原子类型帮助开发者轻松实现原子操作。

#include <atomic>
#include <thread>
#include <iostream>
using namespace std;

atomic_int64_t total = 0;       //atomic_int64_t相当于int64_t，但是本身就拥有原子性

//线程函数，用于累加
void threadFunc(int64_t endNum)
{
	for (int64_t i = 1; i <= endNum; ++i)
	{
		total += i;
	}
}

int main()
{
	int64_t endNum = 100;
	thread t1(threadFunc, endNum);
	thread t2(threadFunc, endNum);

	t1.join();
	t2.join();

	cout << "total=" << total << endl;    //10100
}

原子操作是平台相关的，原子类型能够实现原子操作是因为C++11对原子类型的操作进行了抽象，定义了统一的接口，并要求编译器产生平台相关的原子操作的具体实现。C++11标准将原子操作定义为atomic模板类的成员函数，包括读写、交换等。对于内置类型来说，主要是通过重载一些全局操作符来完成。

指针和引用的区别

指针储存的是原变量的地址，本质上也是一个变量，变量上的存储地址是存储对象的地址。

而引用本质上是和变量是一个东西，只不过是变量的一个别名。

指针可以有const指针，但是没有const引用；

指针可以有多级，但是引用只能是一级（int **p是合法的而 int &&a是不合法的）

指针的值可以为空，但是引用的值不能为NULL，并且引用在定义的时候必须初始化；

指针的值在初始化后可以改变，即指向其它的存储单元，而引用在进行初始化后就不会再改变了。

"sizeof引用"得到的是所指向的变量(对象)的大小，而"sizeof指针"得到的是指针本身的大小；

指针和引用的自增(++)运算意义不一样；

free 和 delete，new 与 malloc

首先是new与malloc的区别，首先，new是一个运算符，需要编译器的支持，而malloc是一个库函数，需要头文件的支持；

在使用new来创建一个对象的时候，流程如下：

1. 首先使用malloc来为该对象在自由存储区中分配对应大小的空间。
2. 调用该对象所属类的构造函数。
3. 返回指向该对象的指针。

所谓的自由存储区，是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，这块内存就是自由存储区。自由存储区可以等于堆，也可以不等于堆，取决于new内对于内存的分配方式。

而delete，和new性质一样，所做的和new恰恰相反。

在delete一个对象的时候，delete首先会调用该对象所属类的析构函数对对象进行析构操作，然后会将该对象所属的存储区域释放。

//operate new原型
void *__CRTDECL operator new(size_t size) _THROW1(_STD bad_alloc)
{
 // try to allocate size bytes
 void *p;
 while ((p = malloc(size)) == 0)
 if (_callnewh(size) == 0)
 {
 // report no memory
 // 如果申请内存失败了，这里会抛出bad_alloc 类型异常
 static const std::bad_alloc nomem;
 _RAISE(nomem);
 }
 return (p);
}
/*
operator delete: 该函数最终是通过free来释放空间的
*/
void operator delete(void *pUserData)
{
	_CrtMemBlockHeader * pHead;
 	RTCCALLBACK(_RTC_Free_hook, (pUserData, 0));
 	if (pUserData == NULL)
 		return;
 	_mlock(_HEAP_LOCK); /* block other threads */
 	__TRY
 		/* get a pointer to memory block header */
 		pHead = pHdr(pUserData);
 		/* verify block type */
 		_ASSERTE(_BLOCK_TYPE_IS_VALID(pHead->nBlockUse));
		_free_dbg( pUserData, pHead->nBlockUse );
	__FINALLY
		_munlock(_HEAP_LOCK); /* release other threads */
	__END_TRY_FINALLY
	 return;
}
/*
free的实现
*/
#define free(p) _free_dbg(p, _NORMAL_BLOCK)

move语义，左值和右值

要理解C++11的move语义，就需要理解C++中的左值和右值和临时对象的概念。

1. 左值与右值和临时对象：

简单地说：=左边的变量就是左值，=号右边的值就是右值。

更加深入一点讲就是：在多条代码中都可以使用，都是左值。右值是指临时的对象，只在当前的语句中有效。

	int i = 1； // i是左值, 1是右值
    int b =  i + 1;   // b是左值， (i+1) 会产生一个临时对象来接受 i+1的计算的结果，这个临时对象是右值，这个临时对象我们看不到，但是编译器会生成
   
    int fun( int&x ){
         int a = x+ 1;
         return a;
    } 
    x= fun(b);  //  这里注意， 要想将这个返回值a传递给左值的x，那么这里我们看不到的，但是编译器做的工作，他会用一个临时变量来存储这个 fun（b）的返回值。然后将这个临时变量赋值给 x;  

总结一下：左值就是等号左边用于接受对象的变量，右值就是等号右边的常量或者表达式计算出来的结果存放的临时对象。

2. move语义

只要了解了左右值，其实就可以理解C++11的move了，首先C++11提出move语义的初衷就是为了把临时变量变得可以使用，从而减少在运行时有多次构造和析构的代价，从而提高性能。

举个例子：

	#include<cstring>
    #include<algorithm>
    class string {
       char*  data;
     public:
         string(const char*  p) {
             size_t size=strlen(p)+1;
             data=new char[size];
             memcpy(data,p,size);
         }
         ~string() {
              delete[] data;
          }
         string(const string& that)   {
             size_t size = strlen(that.data) + 1;
             data = new char[size];
             memcpy(data, that.data, size);
         }
    }

其实在每一个类构造的时候，编译器都会默认出来五个函数，构造函数，拷贝构造函数，析构函数，operator=()，operator&()。C++11后应该是6个，多了move拷贝函数。

回到这个例子：

string fun(const std::string& a, const std::string& b){ reutnr Concat(a+b);}

string a("12345");
string b("abcde");
string c(fun(a,b));

这里对于这次调用，我们需要多分配出来一个临时对象作为fun函数的返回值，这个临时对象会在main的堆栈里面，然后我们再次调用拷贝构造函数构造C对象，这里的临时对象会在调用完成后释放掉，这里临时对象多申请了一次内存，然后又被析构后释放，这是一次无用的操作。

由于临时对象是在main的堆栈创建作为右值，那么就可以进行如下的操作。

		string(string&& that)   // string&& is an rvalue reference to a string
       {
            data = that.data;
            that.data = nullptr;
       }

这样的话，我们直接把临时对象申请的内存的所有权直接交给新的对象。从而避免了C对象的申请内存的操作。同时，这也就是move语义所做出的事情：它将产生的临时对象申请的内存直接交给所要赋值的对象，同时将临时对象置为空。

使用场景：

  1. 函数返回值时。
      string a = std::move(fun());
  2.STL的容器的插入时。 
      std::vector<string> vec;
      vec->push_back(std::move(string()));

Struct和class的区别

struct和class基本是通用的，唯有几个细节不同：

• 在使用class时，类中的成员默认都是private属性的；而使用struct时，结构体中的成员默认都是Public属性的
• class可以使用模板，而struct不行
• class有this，而struct没有

struct和union的区别

1. 在存储多个成员信息的时候，编译器会自动给struct的成员分配存储空间，struct可以存储多个成员信息，而union每个成员会用同一个存储空间，只能存储最后一个成员的信息。
2. 都是由多个不同的数据类型成员组成，但在任何时刻，union只存放一个被先选中的成员，而结构体的所有成员都存在。
3. 对于union的不同成员赋值，将会对其他成员重写，原来成员的值就不存在了。

define和const

关于define和const的区别，用一段程序说明：

#include<iostream>
using namespace std;
 
int main()
{
	int num = 1;
	#define t1 num + num
	#define t2 t1 % t1
	cout << "t2 is " << t2 << endl; // t2 is 2
	const int s1 = num + num;
	const int s2 = s1 % s1;
	cout << "s2 is " << s2 << endl; // s2 is 0
    return 0;
}

为什么t2是2，而s2是正确结果的0呢？这就涉及到了define和const的差别。

分析原因：const定义的常量s1、s2，则s1的值是num+num，s2的值是s1%s1，所以最后结果为“s2 is 0”；而define定义的变量作替换后，C++把cout<<"t2 is "<<t2<<endl;语句译成了：cout<<"t2 is "<<num+num%num+num<<endl;所以结果为“t2 is 2”（1+0+1=2）

具体分析const与define的区别，有几个方面：

const float pi = 3.14;
#define pi 3.14

• 类型安全性检查上，使用const定义的常量是具有数据类型的，在定义或者使用的时候，编译器会对其进行类型安全检查，而使用define定义的宏常量，只会进行简单的字符替换，并不会有数据类型。
• 调度上，部分调度工具可以对const常量进行调度，而不能对宏常量进行调度。
• 编译器的处理方式不同，define的宏常量是在预处理阶段进行展开的，而const常量则是编译运行阶段使用。
• 内存存储方式，const常量会在内存中被分配地址，而define定义的宏只会在遇到的时候进行展开。

在C++中const和static的用法（定义，用途）

对于C++来讲，

const就是只读的意思，只在声明中使用；

static有两个作用，规定作用域和存储方式。对于局部变量，static规定其为静态存储方式，每次调用的初始值为上一次调用的值，调用结束后存储空间不释放。

对于全局变量，如果以文件划分作用域的话，此变量只在当前文件中可见；对于static函数也是只在当前模块内函数可见。

static const是上面两者的合集。

• const的用法

1. 在定义的时候必须进行初始化
2. 定义为const的形参，即在函数内部是不能被修改的
3. 类的成员函数可以被声明为常成员函数，不能修改类的成员变量。
4. 类的成员函数可以返回的是常对象，即被const声明的对象
5. 类的成员变量是常成员变量，不能在声明时初始化，必须在构造函数的列表里进行初始化

const如何做到只读？

这些在编译期完成，对于内置类型，如int，编译器可能使用常数直接替换掉对此变量的引用。

• static的用法

1. 在函数体内，一个被声明的变量在这一函数被调用过程中维持其值不变。
2. 在模块内，一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其他函数访问，相当于一个本地的全局变量。
3. 在模块内，一个被声明为静态的函数只可被这一模块内的其他函数调用。
4. 类中的static成员变量属于整个类所拥有，不能在类内进行定义，只能在类的作用域内进行定义。
5. 类内的static成员函数属于整个类所拥有，不能包含this指针，只能调用static成员函数。

C++中的重载和重写的区别

重载：函数名相同，函数的参数个数、参数类型或参数顺序三者中必须至少有一个不同。函数返回值的类型可以相同，也可以不相同。发生在一个类的内部。

重写：也叫做覆盖，一般发生在子类和父类的继承关系之间。子类重新定义父类中有相同名称和参数的虚函数。

重写需要注意：

1. 被重写的函数不能是static的。必须是virtual的。
2. 重写函数必须有相同的类型，名称和参数列表。
3. 重新函数的访问修饰符可以不同。

C++的内存管理

new和delete、malloc和free、堆和栈

C++中的内存对齐

• 为什么需要字节对齐

1. 内存是以字节为单位存储的，但是处理器并不会按照一个字节为单位去存取内存。处理器存取内存是以块为单位，块的大小可以是2,4,8,16字节大小，这样的存取单位称为内存存取粒度。如果在64位的及其上，不论CPU是要读取第0个字节还是要读取第1个字节，在硬件上传输的信号都是一样的。因为它都会把地址0到地址7，这8个字节全部读到CPU，只是当我们需要读取第0个字节时，丢掉后面7个字节，当我们是需要读取第1个字节，丢掉第1个和后面6个字节。所以对于计算机硬件来说，内存只能通过特定的对齐地址进行访问。
2. 从内存存取效率考虑，内存对齐的情况下可以提升CPU存取内存的效率。比如有一个整型变量，现在有一块内存单元：地址从0到7.这个整型变量从地址为1的位置开始占据了1,2,3,4这4个字节。现在处理器需要读取这个整型变量。假设处理器是4字节4字节的读取，所以从0开始读取0,1,2,3发现并没有读完整这个变量，那么需要再读一次，读取4,5,6,7.然后对两次读取的结果进行处理，提取出1,2,3,4地址的内容。需要两次访问内存，同事通过一些逻辑计算才能得到最终的结果。如果进行内存对齐，将这个整型变量放在从0开始的地址存放，那么CPU只需要一次内存读取，并且没有额外的逻辑计算。

• 如何让字节对齐偏移量为1

#pragma pack(1)

C++多态的实现及原理+虚函数相关

多态机制的实现主要体现在两个方面：1. 函数的重载。2. 接口的重写。接口多态指的是：“一个接口多种形态”。每一个对象内部都有一个虚表指针，该虚表指针被初始化为本类的虚表。所以在程序中，不管你的对象类型如何转换 ，但该对象内部的虚表指针是固定的，所以才能实现动态的对象函数调用。

多态，简单来说，是指在继承层次中，父类的指针可以具有多种形态——当它指向某个子类对象时，通过它能够调用到子类的函数，而非父类的函数

C++的多态性用一句话概括就是：在基类的函数前加上virtual关键字，在派生类中重写该函数，运行时将会根据对象的实际类型来调用相应的函数。如果对象类型是派生类，就调用派生类的函数；如果对象类型是基类，就调用基类的函数。

1. 存在虚函数的类都有一个虚函数表叫做虚表，类的对象有一个指向虚表开始的虚指针。虚表和类是对应的，虚表指针和对象是对应的。
2. 多态性是一个接口多种实现，是面向对象的核心，分为类的多态性和函数的多态性。
3. 多态用虚函数来实现，结合动态绑定
4. 纯虚函数是虚函数再加上=0
5. 抽象类是指包括至少一个纯虚函数的类

纯虚函数：virtual void fun()=0即表示在子类中必须实现这个函数，即先有名称，没有内容，在派生类实现内容。

举个栗子：

//
// Created by alkaid on 2020/1/9.
//
#include <iostream>
using namespace std;
class A{
public:
    void say(){
        cout<<"A"<<endl;
    }
};
class B:public A{
public:
    void say(){
        cout<<"B"<<endl;
    }
};
int main(){
    B *b = new B;
    b->say(); //B
    A *a = b;
    a->say(); //A
}

从编译的角度来看：C++编译器在编译的时候，要确定每个对象调用的函数的地址，这称为早期绑定，当把B类对象的地址赋给A类对象a的时候，C++编译器进行了类型转换，此时C++编译器认为变量a保存的就是A类对象的地址。

从内存的角度来看：

--------------------------------
|                              |
|        A类对象所占内存          |
|							   |
|------------------------------|				B类对象所占的内存
|							   |
|		B类对象自身增加的部分      |
|							   |
--------------------------------

在构造B类对象的时候，首先要调用A类的构造函数去构造A类的对象，然后才调用B类的构造函数完成自身部分的构造，从而拼接处完整的B类对象。

而如果把函数改一改....

class A{
public:
    virtual void say(){
        cout<<"A"<<endl;
    }
};

class B:public A{
public:
    void say(){
        cout<<"B"<<endl;
    }
};

int main(){
    B *b = new B;
    b->say(); //B
    A *a = b;
    a->say(); //B
}

这里只是把基类函数转变为了虚函数，便显示出了正确的结果，那么背后到底发生了什么。

编译器在编译的时候，发现父类有虚函数，此时编译器便会为每个包含虚函数的类创建一个虚表，在表中存放每个虚函数的地址。并且每个类对象中还提供了一个指针指向该虚表。

在程序运行时，根据对象的类型去初始化虚表指针，从而让其正确的指向所属类的虚表，从而在调用虚函数的时候，能够正确的找到函数。

正是由于每个对象调用的虚函数都是通过虚表指针来索引的，也就决定了虚表指针的正确初始化是非常重要的，换句话说，在虚表指针没有正确初始化之前，我们不能够去调用虚函数，那么虚表指针是在什么时候，或者什么地方初始化呢？

答案是在构造函数中进行虚表的创建和虚表指针的初始化，在构造子类对象时，要先调用父类的构造函数，此时编译器只“看到了”父类，并不知道后面是否还有继承者，它初始化父类对象的虚表指针，该虚表指针指向父类的虚表，当执行子类的构造函数时，子类对象的虚表指针被初始化，指向自身的虚表。

为什么析构函数声明为虚函数

为多态性质的基类声明虚析构函数：

当继承类对象经由一个基类指针被删除，若基类是非虚的析构函数，则会导致只调用了基类的析构函数，继承类的成分没有被销毁，造成局部销毁对象，形成资源泄漏，败坏数据结构。

当一个类不被当做基类、或者不具有多态性时，令其析构函数为虚函数是多余的，浪费内存。

构造函数为什么一般不定义为虚函数

虚函数的作用在于通过父类的指针或者引用来调用它的时候能够变成调用子类的那个成员函数。 而构造函数是在创建对象时自动调用的，不可能通过父类的指针或者引用去调用，因此也就规定构造函数不能是虚函数。

构造函数或者析构函数中调用虚函数会怎样

第一个原因，在概念上，构造函数的工作是为对象进行初始化。在构造函数完成之前，被构造的对象被认为“未完全生成”。当创建某个派生类的对象时，如果在它的基类的构造函数中调用虚函数，那么此时派生类的构造函数并未执行，所调用的函数可能操作还没有被初始化的成员，将导致灾难的发生。

第二个原因，即使想在构造函数中实现动态联编，在实现上也会遇到困难。这涉及到对象虚指针（vptr）的建立问题。一个类的构造函数在执行时，并不能保证该函数所能访问到的虚指针就是当前被构造对象最后所拥有的虚指针，因为后面派生类的构造函数会对当前被构造对象的虚指针进行重写，因此无法完成动态联编。

所以，在构造函数或者析构函数中调用虚函数，虚函数会变成实调用。

如何定义只在堆上(栈上)生成对象的类

在C++中，类的对象建立分为两种，一种是静态建立，如A a；另一种是动态建立，如A* ptr=new A；这两种方式是有区别的。

静态建立一个类对象，是由编译器为对象在栈空间中分配内存，是通过直接移动栈顶指针，挪出适当的空间，然后在这片内存空间上调用构造函数形成一个栈对象。使用这种方法，直接调用类的构造函数。

动态建立类对象，是使用new运算符将对象建立在堆空间中。这个过程分为两步，第一步是执行operator new()函数，在堆空间中搜索合适的内存并进行分配；第二步是调用构造函数构造对象，初始化这片内存空间。这种方法，间接调用类的构造函数。

1. 只能建立在堆上

类对象只能建立在堆上，就是不能静态建立类对象，即不能直接调用类的构造函数。

容易想到将构造函数设为私有。在构造函数私有之后，无法在类外部调用构造函数来构造类对象，只能使用new运算符来建立对象。然而，前面已经说过，new运算符的执行过程分为两步，C++提供new运算符的重载，其实是只允许重载operator new()函数，而operator new()函数用于分配内存，无法提供构造功能。因此，这种方法不可以。

当对象建立在栈上面时，是由编译器分配内存空间的，调用构造函数来构造栈对象。当对象使用完后，编译器会调用析构函数来释放栈对象所占的空间。编译器管理了对象的整个生命周期。如果编译器无法调用类的析构函数，情况会是怎样的呢？比如，类的析构函数是私有的，编译器无法调用析构函数来释放内存。所以，**编译器在为类对象分配栈空间时，会先检查类的析构函数的访问性，其实不光是析构函数，只要是非静态的函数，编译器都会进行检查。**如果类的析构函数是私有的，则编译器不会在栈空间上为类对象分配内存。

因此，将析构函数设为私有，类对象就无法建立在栈上了。

上述方法的一个缺点就是，无法解决继承问题。如果A作为其它类的基类，则析构函数通常要设为virtual，然后在子类重写，以实现多态。因此析构函数不能设为private。还好C++提供了第三种访问控制，protected。将析构函数设为protected可以有效解决这个问题，类外无法访问protected成员，子类则可以访问。

2. 只能建立在栈上

只有使用new运算符，对象才会建立在堆上，因此，只要禁用new运算符就可以实现类对象只能建立在栈上。将operator new()设为私有即可。

静态绑定(编译期)和动态绑定(运行期)

为了支持C++的多态性，才用到了静态绑定和动态绑定。

• 对象的静态类型：对象在声明时采用的类型。是在编译期确定的。
• 对象的动态类型：目前所指对象的类型。是在运行期决定的。对象的动态类型可以更改，但是静态类型无法更改。

class B{}
class C : public B{}
class D : public B{}
D* pD = new D();//pD的静态类型是它声明的类型D*，动态类型也是D*
B* pB = pD;//pB的静态类型是它声明的类型B*，动态类型是pB所指向的对象pD的类型D*
C* pC = new C();
pB = pC;//pB的动态类型是可以更改的，现在它的动态类型是C*

静态绑定：绑定的是对象的静态类型，某特性(比如函数)依赖于对象的静态类型，发生在编译期。

动态绑定：绑定的是对象的动态类型，某特性(比如函数)依赖于对象的动态类型，发生在运行期。

class B
{
    void DoSomething();
    virtual void vfun();
}
class C : public B
{
    void DoSomething();//首先说明一下，这个子类重新定义了父类的no-virtual函数，这是一个不好的设计，会导致名称遮掩；这里只是为了说明动态绑定和静态绑定才这样使用。
    virtual void vfun();
}
class D : public B
{
    void DoSomething();
    virtual void vfun();
}
D* pD = new D();
B* pB = pD;

让我们看一下，pD->DoSomething()和pB->DoSomething()调用的是同一个函数吗？ 不是的，虽然pD和pB都指向同一个对象。因为函数DoSomething是一个no-virtual函数，它是静态绑定的，也就是编译器会在编译期根据对象的静态类型来选择函数。pD的静态类型是D，那么编译器在处理pD->DoSomething()的时候会将它指向D::DoSomething()。同理，pB的静态类型是B*，那pB->DoSomething()调用的就是B::DoSomething()。

让我们再来看一下，pD->vfun()和pB->vfun()调用的是同一个函数吗？ 是的。因为vfun是一个虚函数，它是动态绑定的，也就是说它绑定的是对象的动态类型，pB和pD虽然静态类型不同，但是他们同时指向一个对象，他们的动态类型是相同的，都是D*，所以，他们的调用的是同一个函数：D::vfun()。

动态绑定同样可以由引用来实现。因为对象的类型是在编译期就确定了的。而指针和引用是在运行期根据他们的具体指向或引用的对象才可以确定。

静态内存分配和动态内存分配的区别和过程

静态内存分配是在编译期完成的，不占用CPU资源；动态分配内存是在运行期间完成的，分配与释放需要占用CPU资源。

静态内存分配是在栈上的分配的，动态内存是在堆上分配的；

动态内存分配需要指针或引用的支持。

静态内存分配是按计划分配，在编译前确定内存块的大小，动态内存分配运行时按需要进行分配。

静态分配内存是把内存的控制权交给了编译器，动态内存把内存的控制权交给了程序员。

静态分配内存的运行效率要比动态分配内存的效率要高，因为动态内存分配与释放需要额外的开销；动态内存管理水平严重依赖开发者，处理不当容易造成内存泄露。

深拷贝和浅拷贝

浅拷贝实际上是对类成员的引用，深拷贝是对类成员的复制并且重新分配了内存。

对象复用的了解

如果一个对象的创建非常耗时或者代价非常昂贵，频繁去创建的话会非常低效。对象池通过对象复用的方式来避免重复创建对象，它会事先创建一定数量的对象放到池中，当用户需要创建对象的时候，直接从对象池中获取，用完对象后在放回对象池中，以便复用。这种方式避免了重复创建耗时或消耗资源的大对象，大幅提高了程序性能。

模板元编程

模板元编程就是利用模板来编写那些在编译时运行的C++程序。 模板元程序是由C++写成的，运行在编译器中的程序。当程序运行结束后，它的输出仍然会正常地编译。

基本原则：将负载由运行时转移到编译时，同时保持原有的抽象层次。其中负载可以分为两类，一类就是程序运行本身的开销，一类则是程序员需要编写的代码。前者可以理解为编译时优化，后者则是为提高代码复用度，从而提高程序员的编程效率。

成员初始化列表的概念以及性能优势

成员初始化列表就是在类的构造函数后面，紧跟着使用冒号和括号来初始化成员的一个列表，它在C++定义中的类型的初始化和在构造函数内部初始化的性能没什么区别；

但是若类中成员含有C++未定义的类型成员的话，则使用成员初始化列表的性能会比在构造函数中初始化的效率高。

class test{
    String a;
    int b;
    public:
    test(){
        a = "123";
        b = 1;
    }
}
//编译器扩张行为
test(){
    a.String()； // 初始化对象
    String cur = String("123");
    a = cur;
    cur.~String();
    b = 1;
}
//若使用初始化列表
test():a("123"){
    a.String("123"); // 扩充
    b = 1;
}

C++四种强制类型转换

• const_cast

常量指针被转化成非常量的指针，并且仍然指向原来的对象；

常量引用被转换成非常量的引用，并且仍然指向原来的对象；

简单地说：去常量

const_cast一般用来修改指针。

• static_cast

用于类层次结构中基类和派生类之间指针或引用的转换，注意：进行上行转换时是安全的，进行下行转换时，由于没有动态类型检查，所以是不安全的。

用于基本数据类型之间的转换，比如把int转换成char，把int转换成enum。

static_cast不能转换掉原有类型的const、volatile、或者 __unaligned属性。(前两种可以使用const_cast 来去除)

C++中的任何隐式转换都是使用static_cast来实现的

• dynamic_cast

与static_cast一样，dynamic_cast的转换也需要目标类型和源对象有一定的关系：继承关系。更准确的说，dynamic_cast是用来检查两者是否有继承关系。因此该运算符实际上只接受基于类对象的指针和引用的类转换。

• reinterpret_cast

reinterpret_cast是强制类型转换符用来处理无关类型转换的，通常为操作数的位模式提供较低层次的重新解释。但是它仅仅是重新解释了给出的对象的比特模型，并没有进行二进制的转换。 他是用在任意的指针之间的转换，引用之间的转换，指针和足够大的int型之间的转换，整数到指针的转换

extern关键字

放在变量或函数前，表示该变量或函数在别处已有定义，在该行只是声明，并没有分配内存，此处是为了引用别处已定义好的变量函数，起到跨越文件使用变量和函数的作用，其实可以直接inclue文件，主要是为了加快编译速度。

volatile

volatile int i = 19;

• volatile关键字是一种类型修饰符，用它声明的类型变量表示可能被某些编译器未知的因素更改、优化。所以使用volatile关键字告诉编译器不应对这样的对象进行优化。
• volatile关键字声明的变量，每次访问必须从内存中取出值(没有被修饰的变量，可能由于编译器的优化，从CPU寄存器中取值)

判断大小端

大端是指低地址存放的是最高有效字节，小端则是指低地址存放最低有效字节。如果将0x1234abcd写入0x0000开始的内存中，则结果：

#include <iostream>
using namespace std;
union Test{
    short a;
    char b[sizeof(short)];
};
int main(){
    Test test;
    test.a = 0x0102;
    if(test.b[0]==0x01&&test.b[1]==0x02){
        cout<<"大端"<<endl;
    }
    else if(test.b[0] == 0x02&&test.b[1] == 0x01){
        cout<<"小端"<<endl;
    }
    return 0;
}

C++面向对象的五大原则solid

1. 单一职责原则SRP：

是指一个类的功能要单一，不能包罗万象。如同一个人一样，分配的工作不能太多，否则一天到晚虽然忙碌，但效率高不起来。比如一个职员类，如果将工程师，销售人员，销售经理都放在这个类里面，每个方法都需要用if else来进行判断是哪种情况，结构臃肿，且无论哪一个成员发生需求变化，就会改变整个职员类。

2. 开闭原则：

一个模块在扩展性方面应该是开放的而在更改性方面应该是封闭的。比如：一个网络模块，原来只有服务端功能，而现在要加入客户端功能，那么应当在不用修改服务端功能代码的前提下，就能够增加客户端功能的实现代码。这要求在设计之初，就应当将服务端和客户端分开，公共部分抽象出来。

3. 里式替换原则

子类应当可以替换父类并出现在父类能够出现的任何地方。这是因为当子类可以替换父类，而软件单位的功能不受到影响的时候，基类才能真正被复用，而子类也能在基类的基础上增加新的行为。

4. 依赖倒置原则

高层次不应依赖于低层次，应依赖于抽象；抽象不应依赖于具体的实现，具体的实现依赖抽象。因为抽象变化的概率比较小，即使实现细节在发生不断的变化，只要抽象不变，程序就不需要发生变化。

5. 接口分离原则

模块间要通过抽象接口隔离开，而不是通过具体的类强耦合起来；使用多个专门的借口比使用单个接口好得多，这样在实现和维护接口上会省去很多精力；一个接口最好只提供一类对外功能。

智能指针

• shared_ptr

shared_ptr多个指针指向相同的对象。shared_ptr使用引用计数，每一个shared_ptr的拷贝都指向相同的内存。每使用他一次，内部的引用计数加1，每析构一次，内部的引用计数减1，减为0时，自动删除所指向的堆内存。shared_ptr内部的引用计数是线程安全的，但是对象的读取需要加锁

• weak_ptr

weak_ptr是为了配合shared_ptr而引入的一种智能指针，因为它不具有普通指针的行为，没有重载operator*和->,它的最大作用在于协助shared_ptr工作，像旁观者那样观测资源的使用情况。

weak_ptr可以从一个shared_ptr或者另一个weak_ptr对象构造，获得资源的观测权。但weak_ptr没有共享资源，它的构造不会引起指针引用计数的增加。使用weak_ptr的成员函数use_count()可以观测资源的引用计数;

另一个成员函数expired()的功能等价于use_count()==0,但更快，表示被观测的资源(也就是shared_ptr的管理的资源)已经不复存在。weak_ptr可以使用一个非常重要的成员函数lock()从被观测的shared_ptr获得一个可用的shared_ptr对象， 从而操作资源。但当expired()==true的时候，lock()函数将返回一个存储空指针的shared_ptr。

• shared_ptr和weak_ptr

shared_ptr是引用计数型指针；引用计数是资源管理的常用手法，当引用计数降为０的时候，对象即被销毁。weak_ptr也是一个引用计数型智能指针，但是它不会增加对象的引用次数，即弱引用．

shared_ptr控制对象的生命期．shared_ptr是强引用，只要有一个指向对象的shared_ptr存在，该对象就不会被析构，当指向对象的最后一个shared_ptr析构或reset()的时候，对象保证会被销毁．

weak_ptr不控制对象的生命期，但是它知道对象是否还活着。如果对象还活着，那么它可以提升为有效的shared_ptr，如果对象已经死了，提升会失败。

这两种智能指针的计数在主流平台上是原子操作，没有用锁，性能很好。

• unique_ptr

unique_ptr唯一拥有其所指对象，同一时刻只能有一个unique_ptr指向给定对象（通过禁止拷贝语义、只有移动语义来实现）。相比与原始指针unique_ptr用于其RAII的特性，使得在出现异常的情况下，动态资源能得到释放。unique_ptr指针本身的生命周期：从unique_ptr指针创建时开始，直到离开作用域。离开作用域时，若其指向对象，则将其所指对象销毁(默认使用delete操作符，用户可指定其他操作)。unique_ptr指针与其所指对象的关系：在智能指针生命周期内，可以改变智能指针所指对象，如创建智能指针时通过构造函数指定、通过reset方法重新指定、通过release方法释放所有权、通过移动语义转移所有权。

//手写智能指针
#include <utility>  // std::swap
#include <atomic>
class shared_count {
public:
    shared_count() noexcept
            : count_(1) {}
    void add_count() noexcept
    {
        ++count_;
    }
    atomic_int64_t reduce_count() noexcept
    {
        return --count_;
    }
    atomic_int64_t get_count() const noexcept
    {
        return count_;
    }
private:
    atomic_int64_t count_;
};

template <typename T>
class smart_ptr {
public:
    template <typename U>
    friend class smart_ptr;

    explicit smart_ptr(T* ptr = nullptr)
            : ptr_(ptr)
    {
        if (ptr) {
            shared_count_ =
                    new shared_count();
        }
    }
    ~smart_ptr()
    {
        if (ptr_ &&
            !shared_count_
                    ->reduce_count()) {
            delete ptr_;
            delete shared_count_;
        }
    }

    smart_ptr(const smart_ptr& other) //拷贝构造
    {
        ptr_ = other.ptr_;
        if (ptr_) {
            other.shared_count_
                    ->add_count();
            shared_count_ =
                    other.shared_count_;
        }
    }
    template <typename U>
    smart_ptr(const smart_ptr<U>& other) noexcept
    {
        ptr_ = other.ptr_;
        if (ptr_) {
            other.shared_count_->add_count();
            shared_count_ = other.shared_count_;
        }
    }
    template <typename U>
    smart_ptr(smart_ptr<U>&& other) noexcept
    {
        ptr_ = other.ptr_;
        if (ptr_) {
            shared_count_ =
                    other.shared_count_;
            other.ptr_ = nullptr;
        }
    }
    template <typename U>
    smart_ptr(const smart_ptr<U>& other,
              T* ptr) noexcept
    {
        ptr_ = ptr;
        if (ptr_) {
            other.shared_count_
                    ->add_count();
            shared_count_ =
                    other.shared_count_;
        }
    }
    smart_ptr&
    operator=(smart_ptr rhs) noexcept
    {
        rhs.swap(*this);
        return *this;
    }

    T* get() const noexcept
    {
        return ptr_;
    }
    long use_count() const noexcept
    {
        if (ptr_) {
            return shared_count_
                    ->get_count();
        } else {
            return 0;
        }
    }
    void swap(smart_ptr& rhs) noexcept
    {
        using std::swap;
        swap(ptr_, rhs.ptr_);
        swap(shared_count_,
             rhs.shared_count_);
    }
    T& operator*() const noexcept
    {
        return *ptr_;
    }
    T* operator->() const noexcept
    {
        return ptr_;
    }
    operator bool() const noexcept
    {
        return ptr_;
    }
private:
    T* ptr_;
    shared_count* shared_count_;
};
template <typename T>
void swap(smart_ptr<T>& lhs,
          smart_ptr<T>& rhs) noexcept
{
    lhs.swap(rhs);
}

C++生产者消费者模式

priority_queue<timer*,vector<timer*>,cmp> q;
pthread_mutex_t qlock;
pthread_cond_t n;
void *check(void *args){
        while(true) {
            pthread_mutex_lock(&qlock);
            if(q.empty()) {
                cout << "等待" << endl;
                pthread_cond_wait(&n, &qlock);
            }
            if (time(NULL) - q.top()->get_time() > 5) {
                cout << q.top()->get_time() << "超时删除" << endl;
                timer *cur = q.top();
                q.pop();
                delete cur;
            }
            //pthread_cond_signal(&n);
            pthread_mutex_unlock(&qlock);
        }
    }

void *add(void *args){
    for(;;){
        pthread_mutex_lock(&qlock);
        timer *a = new timer();
        cout<<a->get_time();
        q.push(a);
        cout<<" "<<q.top()->get_time()<<endl;
        if(q.size()==1) {
            pthread_cond_signal(&n);
        }
        pthread_mutex_unlock(&qlock);
        sleep(1);}
}
int main(){
    priority_queue<timer*> q;
    pthread_mutex_init(&qlock,NULL);
    pthread_cond_init(&n, NULL);
    pthread_t *add_thread = (pthread_t *)malloc(sizeof(pthread_t));
    pthread_create(add_thread,NULL,add,NULL);
    pthread_t *check_thread = (pthread_t *)malloc(sizeof(pthread_t)); //检查线程
    pthread_create(check_thread,NULL, check, NULL);
    while(true){}
    return 0;
}

计网

输入URL后发生了什么

1. 在浏览器中输入url 用户输入url，例如http://www.baidu.com/。其中http为协议，http://www.baidu.com为网络地址，及指出需要的资源在那台计算机上。一般网络地址可以为域名或IP地址，此处为域名。使用域名是为了方便记忆，但是为了让计算机理解这个地址还需要把它解析为IP地址。

2. 应用层DNS解析域名

   客户端先检查本地是否有对应的IP地址，若找到则返回响应的IP地址。若没找到则请求上级DNS服务器，直至找到或到根节点。

3. 应用层客户端发送HTTP请求

   HTTP请求包括请求报头和请求主体两个部分，其中请求报头包含了至关重要的信息，包括请求的方法（GET / POST）、目标url、遵循的协议（http / https / ftp…），返回的信息是否需要缓存，以及客户端是否发送cookie等。

4. 传输层TCP传输报文

   位于传输层的TCP协议为传输报文提供可靠的字节流服务。它为了方便传输，将大块的数据分割成以报文段为单位的数据包进行管理，并为它们编号，方便服务器接收时能准确地还原报文信息。TCP协议通过“三次握手”等方法保证传输的安全可靠。

   “三次握手”的过程是，发送端先发送一个带有SYN（synchronize）标志的数据包给接收端，在一定的延迟时间内等待接收的回复。接收端收到数据包后，传回一个带有SYN/ACK标志的数据包以示传达确认信息。接收方收到后再发送一个带有ACK标志的数据包给接收端以示握手成功。在这个过程中，如果发送端在规定延迟时间内没有收到回复则默认接收方没有收到请求，而再次发送，直到收到回复为止。

5. 网络层IP协议查询MAC地址

   IP协议的作用是把TCP分割好的各种数据包传送给接收方。而要保证确实能传到接收方还需要接收方的MAC地址，也就是物理地址。IP地址和MAC地址是一一对应的关系，一个网络设备的IP地址可以更换，但是MAC地址一般是固定不变的。ARP协议可以将IP地址解析成对应的MAC地址。当通信的双方不在同一个局域网时，需要多次中转才能到达最终的目标，在中转的过程中需要通过下一个中转站的MAC地址来搜索下一个中转目标。

6. 数据到达数据链路层

   在找到对方的MAC地址后，就将数据发送到数据链路层传输。这时，客户端发送请求的阶段结束

7. 服务器接收数据

   接收端的服务器在链路层接收到数据包，再层层向上直到应用层。这过程中包括在运输层通过TCP协议讲分段的数据包重新组成原来的HTTP请求报文。

8. 服务器响应请求

   服务接收到客户端发送的HTTP请求后，查找客户端请求的资源，并返回响应报文，响应报文中包括一个重要的信息——状态码。状态码由三位数字组成，其中比较常见的是200 OK表示请求成功。301表示永久重定向，即请求的资源已经永久转移到新的位置。在返回301状态码的同时，响应报文也会附带重定向的url，客户端接收到后将http请求的url做相应的改变再重新发送。404 not found 表示客户端请求的资源找不到。

9. 服务器返回相应文件

   请求成功后，服务器会返回相应的HTML文件。接下来就到了页面的渲染阶段了。

OSI七层协议

OSI七层协议从上到下分别是：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层。

其中，有其他的划分方式将网络划分为五层：将应用层、表示层、会话层合并为应用层。

物理层

字面意思：涉及物理传输、硬件、物理特性

计算机与计算机之间的通信，必须要有底层物理层方面的连通。

中间的物理链接可以是光缆、电缆 、双绞线、无线电波。

数据链路层

数据链路层是用来对电信号来做分组的，一组电信号称之为一个数据包，或者叫做一个"帧"

• 每一个数据帧分成报头head和数据data两部分

head固定18个字节，包含的信息有：

• 发送者(源地址，6个字节)
• 接收者(目标地址，6个字节)
• 数据类型(6个字节)

data最短46个字节，最长1500个字节，包含有数据包的具体内容。

其中，源地址和目标地址指的都是MAC地址。

接下来要讲的，需要首先要明确的一点：互联网其实是由一个个局域网组成的。

数据链路层的工作方式是广播，广播出去以后，所有客户端都会收到并拆开这个包，判断接收者是不是自己，如果不是就将其丢弃。

在同一个局域网下的计算机是靠广播来通信，而不同局域网下的计算机通信是需要进行跨网络通信的，数据链路层是解决不了这个问题的，这时候就需要网络层来解决。

ARP协议

OSI模型把网络工作分为七层，IP地址在OSI模型的第三层，MAC地址在第二层，彼此不直接打交道。在通过以太网发送IP数据包的时候，需要先封装第三层、第二层的报头，但由于发送时只知道目标IP地址，不知道其MAC地址，又不能跨第二、三层，所以需要使用地址解析协议。使用地址解析协议，可根据网络层IP数据包的包头中的IP地址信息解析出目标硬件地址信息，以保证通信的顺利进行。

工作过程

• 同一局域网内：

主机A的IP地址为192.168.1.1，MAC地址为0A-11-22-33-44-01；

主机B的IP地址为192.168.1.2，MAC地址为0A-11-22-33-44-02；

当主机A要与主机B通信时，地址解析协议可以将主机B的IP地址（192.168.1.2）解析成主机B的MAC地址，以下为工作流程：

第1步：根据主机A上的路由表内容，IP确定用于访问主机B的转发IP地址是192.168.1.2。然后A主机在自己的本地ARP缓存中检查主机B的匹配MAC地址。

第2步：如果主机A在ARP缓存中没有找到映射，它将询问192.168.1.2的硬件地址，将ARP请求帧广播到本地网络上的所有主机。源主机A的IP地址和MAC地址都包括在ARP请求中。本地网络上的每台主机都接收到ARP请求并且检查是否与自己的IP地址匹配。如果主机发现请求的IP地址与自己的IP地址不匹配，它将丢弃ARP请求。

第3步：主机B确定ARP请求中的IP地址与自己的IP地址匹配，则将主机A的IP地址和MAC地址映射添加到本地ARP缓存中。

第4步：主机B将包含其MAC地址的ARP回复消息直接发送回主机A。

第5步：当主机A收到从主机B发来的ARP回复消息时，会用主机B的IP和MAC地址映射更新ARP缓存。本机缓存是有生存期的，生存期结束后，将再次重复上面的过程。主机B的MAC地址一旦确定，主机A就能向主机B发送IP通信了。

• 不同局域网

若是在不同局域网下，则会将目标IP改为默认网关的IP进行广播ARP请求

1. 当网关(大多数时候是路由器)收到这个ARP请求后，发现是请求自己的，于是发送给源主机一个ARP应答，告诉主机自己的MAC地址。
2. 源主机收到后，将目标MAC地址改为路由器的MAC地址，然后将数据包发给路由器。(数据包的目标IP地址仍然是不同局域网下的主机)
3. 路由收到数据包，检查目的IP地址，发现不是给自己的，决定要进行路由，查询路由表。准备从相应接口发送，查询MAC地址表，发现没有对方主机的映射，于是发送ARP请求查询目标主机的MAC地址(原理一样，主机收到请求后首先会添加网关的MAC地址，然后单播回复ARP请求)。
4. 路由器收到对方主机的MAC地址后，将其添加到路由MAC地址表中，封装自己的MAC地址为源MAC，对方主机的MAC地址为目的MAC（源和目的IP地址不变），加上二层帧头及校验，发送给对方主机。

网络层

网络层定义的是一个IP协议。

当通信的双方位于不同的局域网的时候，只靠数据链路层广播的工作方式是无法进行通信的，对外的广播是无效的。这时候就需要一个“负责人”，由“负责人”找到对方所属局域网的“负责人”，进行对话。所谓的“负责人”就是网关。

MAC地址是用来定位局域网内的地址，而IP地址是用来表示位于哪个局域网的。如果要跨网络发包，首先要知道对方的IP地址。在发包前，计算机会判断双方是否在同一个局域网内，如果是就根据MAC地址进行广播发送，不是就发送给网关，让网关进行转发。MAC地址加上IP地址的组合唯一标识了计算机位于互联网中的位置。

数据链路层中会把网络层的数据包封装到数据链路层的data位置，然后再添加上自己的head，再发给物理层，物理层发给网关，网关再发给对方局域网的网关，对方教室的网关收到后在局域网内进行广播。

传输层

网络层的IP帮我们区分子网，数据链路层的的MAC帮我们找到主机，但计算机中可能随时开着多个应用程序，在数据到达目标计算机时，怎么判断数据是发送给哪个应用的呢？

答案就是端口，端口是应用程序与网卡关联的编号。

而传输层的功能就是建立端口到端口的通信。

端口范围在0-65535之间，其中0-1023为系统占用端口。

TCP协议

可靠传输，TCP数据包没有长度限制，理论上可以无限长，但是为了保证网络的效率，通常TCP数据包的长度不会超过IP数据包的长度，以确保单个TCP数据包不必再分割，减少消耗。

以太网头	IP头	TCP头	数据

UDP协议

不可靠传输，“报头”部分一共只有8个字节，总长度不超过65535字节，正好放进一个IP数据包。

应用层

应用层由来：用户使用的都是应用程序，均工作于应用层，互联网是开发的，大家都可以开发自己的应用程序，数据多种多样，必须规定好数据的组织形式 。

应用层功能：规定应用程序的数据格式。

例：TCP协议可以为各种各样的程序传递数据，比如Email、WWW、FTP等等。那么，必须有不同协议规定电子邮件、网页、FTP数据的格式，这些应用程序协议就构成了”应用层”。

常见路由协议以及路由算法

• RIP

RIP是路由信息协议的简写，主要传递路由信息，通过每隔30秒广播一次路由表，维护相邻路由器的位置关系，同时根据收到的路由表信息计算自己的路由表信息。

RIP还是一个距离矢量路由协议，最大跳数为16跳，16跳及超过16跳的网络则认为目标网络不可达。此协议通常用在网络架构较为简单的小型网络环境下。

路由收敛指的是网络的拓扑结构发生变化后，路由表重新建立再到学习直到稳定，并通过网络中所有相关路由器都得知该变化的过程。也就是网络拓扑变化引起的通过重新计算路由二发现替代路由的行为。

• OSPF

OSPF协议是“开放式最短路径优先”的缩写，属于链路状态路由协议。

OSPF提出了“区域”的概念，每个区域中所有路由器维护一个相同的链路状态数据库。区域又分为骨干区域和非骨干区域，如果一个运行OSPF的网络只存在单一区域，则该区域可以是骨干也可以是非骨干。如果该网络存在多个区域，那么必须存在骨干区域，并且所有非骨干区域必须和骨干区域直接相连。OSPF利用所维护的链路状态数据库，通过最短生成树算法计算得到路由表。OSPF的收敛速度较快。

• BGP

BGP是边界网关协议的缩写。

BGP系统与其他BGP系统之间交换网络可到达信息。这些信息包括数据到达这些网络所必须经过的自治系统AS中的所有路径。这些信息足以构造一副自治系统连接图。然后，可以根据连接图删除选路环，制订选路策略。

• LS算法

链路状态算法（也称最短路径算法）发送路由信息道互联网上所有的节点，对于每个路由器，仅发送它的路由表中描述了自身链路状态的那一部分。

采用LS算法时，每个路由器必须遵循以下步骤：

1. 确认在物理上与之相连的路由器并获取它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个分组数据包。每个接收到数据包的路由器都将返回一条信息，其中包含它自身的IP地址。
2. 测量相邻路由器的延时。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。通过计算，便可以计算出延时。
3. 向网络中的其他路由器广播自己的信息，同时也接受其他路由器的信息。

在这一步中，所有的路由器共享他们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够直到网络的结构以及状态。

1. 使用同一个合适的算法，确定网络中两个节点之间的最佳路由。

• DV算法

距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面，链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些。

TCP与UDP的区别

1. TCP基于连接，UDP无连接
2. 从系统资源的角度来看，TCP要求的系统资源较多，UDP要求的系统资源较少
3. UDP程序结构较为简单
4. 流模式与数据报模式
5. TCP保证数据的正确性和顺序，这些UDP都不做保证。
6. TCP有拥塞控制和流量控制

TCP提供的是面向连接、可靠的字节流服务。当客户和服务器彼此交换数据前，必须现在双方之间建立一个TCP连接，之后才能传输数据。TCP提供超时重发，丢弃重复数据，检验数据，流量控制等功能，保证数据能从一段传输到另一端。

UDP是一个简单的面向数据报的运输层协议。UDP不提供可靠性，它只是把应用程序传给IP层的数据报发送出去，但是并不能保证他们能到达目的地。由于UDP在传输前不用先建立连接，所以传输速度很快。

三次握手

1. 建立连接时，客户端发送SYN包到服务器，并进入SYN_SENT状态，等待服务器确认。
2. 服务器收到SYN包，必须确认客户的SYN，同时自己也发送一个SYN包，即是SYN+ACK包，此时服务器进入SYN_RECV状态。
3. 客户端收到服务器的SYN+ACK包，向服务器发送确认包ACK，此包发送完毕，客户端和服务器进入ESTABLISHED（TCP连接成功）状态，完成三次握手。三次握手完成两个重要的功能：让双方都确认对方已做好发送和接收数据的准备工作，允许双方就初始序列号进行协商。

四次挥手

1. 客户端进程发出连接释放报文，并且停止发送数据。释放数据报文首部，FIN=1，其序列号seq=u（等于经传送过来的数据的最后一个字节的序号+1），此时，客户端进入FIN-WAIT-1(终止等待1)状态。TCP规定报文段即使不携带数据，也要消耗一个序号。
2. 服务端收到连接释放报文，发出确认报文，ACK=1，ack=u+1，并且带上自己的序列号seq=v，此时，服进入了CLOSE-WAIT（关闭等待）状态。TCP服务器通知高层的应用进程，客户端向服务器的方向就释放时候处于半关闭状态，即客户端已经没有数据要发送了，但是服务器若发送数据，客户端依然要接受。这态还要持续一段时间，也就是整个CLOSE-WAIT状态持续的时间。
3. 客户端收到服务器的确认请求后，此时，客户端就进入了FIN-WAIT-2（终止等待2）状态，等待服务器发释放报文（在这之前还需要接受服务器发送的最后的数据）。
4. 服务器将最后的数据发送完毕后，就向客户端发送连接释放报文，FIN=1，ack=u+1，由于在半关闭状态器很可能又发送了一些数据，假定此时的序列号为seq=w，此时，服务器就进入了LAST-ACK（最后确认态，等待客户端的确认。
5. 客户端收到服务器的连接释放报文后，必须发出确认，ACK=1，ack=w+1，而自己的序列号是seq=u+1时，客户端就进入了TIME-WAIT（时间等待）状态。此时TCP连接还没有释放，必须经过**2*MSL（最长报文寿命）**的时间后，当服务器撤销相应的TCP后，才进入CLOSED状态。
6. 服务器只要收到了客户端发出的确认，立即进入CLOSED状态。同样，撤销TCB后结束这次的TCP

为什么TIME-WAIT状态要经过2MSL才进入CLOSED状态

MSL：报文最大存活时间

1. 虽然按道理来说，四个报文都发送完毕后，是可以直接进入CLOSED状态的，但是必须假想网络是不可靠的，有可能客户端发送出的最后一个ACK丢失，服务器端没收到ACK，将不断重复发送FIN片段，所以客户端不能立即关闭，它必须确认服务器端收到了最后一个ACK。所以TIME-WAIT状态就是用来重发可能丢失的ACK报文的，如果在2MSL之后，客户端都没有再次收到FIN，那么可以推断客户端的ACK被成功接收，则结束TCP连接。
2. 防止已失效的连接请求报文段出现在本连接中。A在发送完最后一个ACK报文段后，再经过时间2MSL，就可以使本连接持续的时间内产生的所有报文段都可以从网络中小时。这样就可以使下一个连接中不会出现这种旧的连接请求报文段。

UDP如何实现可靠传输

UDP不属于连接协议，具有资源消耗少，处理速度快的优点，所以通常音频，视频和普通数据在传送时，使用UDP较多，因为即使丢失少量的包，也不会对接收结果产生较大的影响。

传输层无法保证数据的可靠传输，只能通过应用层来实现。实现的方式可以参照TCP可靠性传输的方式，只是实现不在传输层，而是转移到了应用层。

最简单的方式就是在应用层模仿传输层的TCP可靠性传输。

1. 添加seq/ack机制，确保数据发送到对端
2. 添加发送和接收缓冲区，主要是用户超时重传
3. 添加超时重传机制

详细说明：发送端发送数据的时候，生成一个随机seq=x，然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存，并发送一个ACK=x的包，表示对方已经收到了数据。发送端收到了ACK包后，删除缓冲区对应的数据。时间到后，定时任务检查是否需要重传数据。

面向数据报(UDP)和面向字节流(TCP)的区别

面向报文的传输方式是应用层交给UDP多长的报文，UDP就照常发送，即一次发送一个报文。因此，应用程序必须选择合适大小的报文。若报文太长，则IP层需要分片，降低效率。UDP堆应用层交下来的报文，既不合并，也不拆分，而是保留这些报文的边界。这也就是说，应用层交给UDP多长的报文，UDP就照样发送，即一次发送一个报文。

面向字节流的话，虽然应用程序和TCP的交互是一次一个数据块(大小不等)，但TCP把应用程序看成是一连串的无结构的字节流。TCP有一个缓冲，当应用程序传送的数据块太长，TCP就可以把它划分短一些再传送。如果应用程序一次只发送一个字节，TCP也可以等待积累有足够多的字节后再构成报文段发送出去。

TCP流量控制的实现机制---滑动窗口

MSS：TCP一次传输发送的最大数据段长度

RTT：往返时延，表示从发送端发送数据开始，到发送端收到来自接收端的确认，总共经历的时延

TCP使用端到端流量控制协议来避免发送方发送数据太快，以致TCP接收方不能可靠地接收和处理数据。在不同网络速度的机器进行通信的环境中，具有流量控制机制至关重要。

所谓流量控制，主要是接收方传递信息给发送方，使其不要发送数据太快，是一种端到端的控制。主要的方式就是返回的ACK会包含自己的接收窗口的大小，并且利用大小来控制发送方的发送窗口。

所谓滑动窗口，就是类似于窗口一样的东西，是用来告诉发送端可以发送数据的大小或者说是窗口标记了接收端缓冲区的大小。

TCP利用一个滑动的窗口来告诉发送端对它所发送的数据能提供多大的缓冲区。由于窗口由16位bit所定义，所以接收端TCP能最大提供65535个字节的缓冲。由此，可以利用窗口大小和第一个数据的序列号计算出最大可接收的数据序列号。

发送方根据接收方发送的win字段来判断自己能发送多长的数据。如果发送方收到接收方的窗口大小为0的TCP数据报，那么发送方将停止发送数据，等到接收方发送窗口大小不为0的数据报的到来。

1. 接收端将自己可以接收的缓冲区大小放入TCP首部中的“win”字段，通过ACK来通知发送端
2. 窗口大小字段越大，说明网络的吞吐率越高
3. 窗口大小指的是无需等待确认应答而可以继续发送数据的最大值，就是说不需要接收端的应答，可以一次连续的发送数据。
4. 操作系统内核为了维护滑动窗口，需要开辟发送缓冲区，来记录当前还有哪些数据没有应答，只有确认应答过的数据，才能从缓冲区删掉。
5. 接收端一旦发现自己的缓冲区快满了，就会将窗口大小设置成一个更小的值通知给发送端，发送端接收到这个值后，就会减慢自己的发送速度。
6. 如果接收端发现自己的缓冲区满了，就会将窗口大小设置为0，此时发送端将不再发送数据，但是需要定期发送一个窗口探测数据段，使接收端把窗口大小告诉发送端。

发送方没有收到接收方发回的ACK，就不能向右滑动。假设发送方向接收方发了ABCD就滑动，只要对方没收到A，就不能滑动，那么就会出现二者不同步的局面。

滑动窗口提高了信道利用率，TCP是发送报文段为单位的，假如每发一个报文就要等ACK，那么对于大数据包，等待时间就太长了。只要发送的报文在滑动窗口里面，不用等每个ACK回来就可以向右滑动。

窗口大小不能大于序号空间大小的一半。目的是为了不让两个窗口出现交迭，比如总大小为7，窗口大小都为4，接收窗口应当滑动4，但只剩3个序号，导致两个窗口交迭。

有一种情况没出现：发送方发ABCD，接收方都收到然后向右滑动，但回复的ACK包全丢了。发送方未收到任何ACK， timeout后会重发ABCD，此时的接收方按累计确认的原则，收到ABCD后只会重发D的ACK，发送方收到后向右滑动。

由于“滑动窗口”协议的性能取决于窗口大小和网络接收数据包的速度，在流量不稳定的环境中，性能下降甚至可能会使网络发生冲突.

TCP停止等待

在网络传输中，我们认为最理想的传输状态是：

1. 传输信道不产生差错
2. 不管发送方以多快的速度发送数据，接收方都能来得及接收以及处理这些数据

当然，这种只是理想状态，在实际运用中，几乎是不可能的。因此，我们需要采取一些可靠的传输协议。

1. 当出现差错时，让发送方重传该差错数据。
2. 接收方来不及处理数据时，及时告知发送放适当的降低发送速度。

而要做到第一点，就需要采用停止等待协议

所谓停止等待协议就是每发送完一组数据后，等待对方确认并且收到确认后，再发送下一组数据。

但由于效率较低，目前已经采用连续ARQ协议+快速重传

TCP拥塞控制

概念：在某段时间，如果对网络中的某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要发生变化，这种情况便是阻塞。

拥塞控制要做的就是防止过多的数据注入到网络当中，这样可以使网络中的路由器或链路不至于过载。

与流量控制的区别：流量控制往往使指端到端通信量的控制。拥塞控制所要做的就是控制发送端发送数据的速率。

代价：需要所得网络内部流量分布的信息。在实施拥塞控制之前，还需要再节点之间交换信息和各种命令，以便选择控制的策略和实施控制。这样就产生了额外的开销。

几种方法：

• 慢启动

该算法通过观察到新分组进入网络的速率应该与另一端返回确认的速率相同而开始工作。

慢启动为发送方的TCP增加了另一个窗口：拥塞窗口（cwnd），当与另一个网络的主机建立TCP连接时，拥塞窗口被初始化为1个报文段（即另一端通告的报文段大小）。每收到一个ACK，拥塞窗口就增加一倍报文段。发送方取拥塞窗口与通告窗口中的最小值作为发送上线，拥塞窗口是发送方使用的流量控制，而通告窗口是接收方使用的流量控制。

当cwnd足够大的时候，为了防止拥塞窗口的增长引起网络阻塞，还需要另一个变量——慢启动门限ssthresh。

1. 当cwnd<ssthresh时，使用上述慢启动算法；
2. 当cwnd>ssthresh时，停止使用慢启动算法，改用拥塞避免算法；

• 拥塞避免

该算法让拥塞窗口缓慢的增大，即每经过一个往返时间RTT就把发送方的拥塞窗口加1，而不是加倍，这样拥塞窗口按线性规律缓慢的增长，比慢启动算法的拥塞窗口增长速率缓慢的多。

并且，当发生超时和接收到重复的确认时，就判断再源主机和目的主机之间的某处网络发生了阻塞。当阻塞时，会把慢启动门限设定为拥塞前的值的一半，拥塞窗口重新置1，再开始慢启动算法。

• 快速重传

一条TCP连接有时会因为等待重传计时的超时而空闲较长时间，慢开始和拥塞避免无法解决这类问题，因此提出了快重传和快恢复的拥塞控制方法。

快速重传算法要求首先接收方收到一个失序的报文段后立刻发出重复确认，而不要等待自己发送数据时才进行捎带确认，如图：

在上图中，接收方成功的接受了发送方发来的M1,M2并且分别发送了ACK，现在接收方没有收到M3，而收到了M4，显然接收方不能确认M4，因为M4是失序的报文段。如果根据可靠性传输原理接收方什么都不做，但是按照快速重传算法，在收到M4,M5等报文段的时候，不断重复的向发送方发送M2的ACK，如果接收方一连收到三个重复的ACK，那么发送方不必等待重传计时器到期，由于发送方尽早重传未被确认的报文段

• 快速恢复

1. 当发送方连续收到三个重复ACK确认后，将慢启动门限设置为当前拥塞窗口的一般。重传丢失的报文段，设置cwnd为慢启动门限加上3倍的报文段大小。
2. 每次收到另一个重复的ACK时，cwnd增加一个报文段并发送一个分组。
3. 当下一个确认新数据的ACK到达时，设置cwnd为慢启动门限。这个ACK应该是在进行重传后的一个往返时间内对步骤1重传的确认。另外，这个ACK也应该是对丢失的分组和收到的第一个重复的ACK之间的所有中间报文段的确认。这一步采用的是拥塞避免，因为当分组丢失时我们将当前的速率减半。

TCP超时重传

超时重传是TCP保证数据传输可靠性的措施，其指的是，发送数据包在一定的时间周期内没有收到对应的ACK，等待一定的时间，超时之后就认为这个数据包丢失，就会重新发送。这个等待时间被称为RTO。

每一次开始发送一个数据包的时候，就启动重传定时器，定时器的时间一开始是一个预设的值(Linux规定为1s)，随着通讯的变化以及时间的推移，这个定时器的溢出值是不断的在变化的，如果在ACK收到之前，定时器到期，协议栈就会认为这个片段丢失，重新发送。

• 超时重传时间RTO

超时重传时间的设置是比较复杂的，超时重传时间或多或少都会影响传输效率，但可以肯定的是：超时重传时间设置要比数据报往返时间长一点，而这多出来的一点，其实就是指的是数据报往返时间的偏差。

那么，如何计算RTO呢，要计算RTO，首先要计算的是数据报往返时间RTT，通常来说，RTT是每次都会更新的数据：新RTTS=(1−α)×旧RTTS+α×RTT ，既然已经知道了往返时间RTT的测量，就可以根据往返时间RTT来设置超时重传时间了。

• • 计算RTT的偏差

超时重传时间 = 加权平均往返时间RTTS+偏差，于是就有了下面的公式：

RTO = RTTS(加权平均往返时间) + RTTD(偏差)

RFC建议这样计算偏差：当第一次测量偏差时，偏差值取为测量到的RTT样本值的一半，在以后的每次测量误差中，使用加权公式平均偏差，这样得到的就是更为平滑的偏差值：

新RTTD(偏差)=(1−β)×旧RTTD+β×|RTTS(目前所得平均加权往返时间)−RTT(该次测量所得往返时间)|

• • 计算超时重传时间RTO

RFC规定的计算公式为：RTO = RTTS + 4*RTTD

通过上面的公式可知，RTO的计算就是RTTs 加上当前平滑的RTTD的4倍。

HTTP与TCP协议之间的联系

HTTP是基于TCP连接为基础的。简单的说，TCP就是单纯的建立连接，不涉及任何我们需要请求的数据，简单的传输。HTTP是用来收发数据的，即实际应用上来的。

1. 从传输层来看，先是TCP连接，要和客户端建立TCP连接，需要通过三次连接，包括：请求，确认，建立连接，也就是常说的：三次握手协议

2. 从实际的数据应用上来看HTTP，在前面客户端和服务器建立连接后，就需要用HTTP协议来传输数据了，HTTP简单的说依旧是请求，确认，连接。

   总体来说就是C发送一个HTTP请求给S，S收到了这个http请求，然后返回给C一个http响应，然后C的中间件或者说浏览器把这些数据渲染成为了网页，展示在用户面前。

总结： TCP是底层通讯协议，定义的是数据传输和连接方式的规范； HTTP是应用层协议，定义的是传输数据的内容的规范； HTTP协议中的数据是利用TCP协议传输的，所以支持HTTP也就一定支持TCP ； HTTP支持的是www服务 ； 而TCP/IP是协议， 是Internet国际互联网络的基础，是网络中使用的基本的通信协议。 TCP/IP实际上是一组协议，它包括上百个各种功能的协议，如：远程登录、文件传输和电子邮件等，而TCP协议和IP协议是保证数据完整传输的两个基本的重要协议。通常说TCP/IP是Internet协议族，而不单单是TCP和IP。

HTTP1.0和HTTP1.1的区别(HTTP 2.0)

1. 持久连接

在HTTP1.0中，每对Request/Response都使用一个新的连接

在HTTP1.1则支持持久连接，并且默认使用持久连接。在同一个TCP的连接中可以传送多个HTTP请求和响应。多个请求和响应可以重叠，多个请求和响应可以同时进行。

HTTP1.0规定浏览器与服务器只保持短暂的连接，浏览器的每次请求都需要与服务器建立一个TCP连接，服务器完成请求处理后立即断开TCP连接，服务器不跟踪每个客户也不记录过去的请求。

在1.0时的会话方式：

1. 建立连接
2. 发出请求信息
3. 回送响应信息
4. 关掉连接

总结：浏览器和web服务器之间的连接很短，每次连接只处理一个请求和响应。对每一个页面的请求，浏览器都要与服务器建立一次单独的连接。浏览器没有关闭前，连接就已经断开了。浏览器和服务器之间的通信是完全独立分开的请求和响应对。因为这样没法判断浏览器是否断开，没法做连接状态控制。建立和关掉连接会很占用连接时间。

2. 请求头多了Host字段，一个服务器多个网站 在HTTP1.0中认为每台服务器都绑定一个唯一的IP地址，因此，请求消息中的URL并没有传递主机名（hostname）。但随着虚拟主机技术的发展，在一台物理服务器上可以存在多个虚拟主机（Multi-homed Web Servers），并且它们共享一个IP地址。 HTTP1.1的请求消息和响应消息都应支持Host头域，且请求消息中如果没有Host头域会报告一个错误（400 Bad Request）。此外，服务器应该接受以绝对路径标记的资源请求。
3. 文件断点续传
4. 身份认证，状态管理，Cache缓存

• 和HTTP2.0的区别
• • 新的二进制格式，HTTP1.x的解析是基于文本。基于文本协议的格式解析存在天然缺陷，文本的表现形式有多样性，要做到健壮性考虑的场景必然很多，二进制则不同，只认0和1的组合。
  • 多路复用，即连接共享，即每一个request都是用作连接共享机制的。一个request对应一个id，这样一个连接上可以有多个Request，每个连接的Request可以随机的混杂在一起，接收方可以根据Request的id将Request再归属到各自不同的服务端请求里面。
  • header压缩，使用encoder来减少需要传输的头部大小，通讯双方都各自缓存一份header fields表，既避免了重复header的传输，又减少了需要传输的大小。
  • 服务端推送

跨域问题

什么是跨域

当一个请求url的协议、域名、端口三者之间任意一个与当前页面URL不同即为跨域。

HTTP(80)和HTTPS(443)的区别

HTTP：是互联网上应用最为广泛的一种网络协议，是一个客户端和服务器端请求和应答的标准，用于从WWW服务器传输超文本到本地浏览器的传输协议，它可以让浏览器更加搞笑，使网络传输减少。

HTTPS：是以安全为目标的HTTP通道，简单说是HTTP的安全版，即HTTP下加入SSL层，HTTPS的安全基础是SSL，因此加密的详细内容就需要SSL。

HTTPS协议的主要作用可以分为两种：一种是建立一个信息安全通道，来保证数据传输的安全；另一种就是确认网站的真实性。

两者的区别主要如下：

1. HTTPS协议是具有安全性的SSL加密传输协议，相当于是SSL+HTTP协议
2. HTTPS和HTTP使用的是完全不同的连接方式，用的端口也不一样。

HTTPS的工作原理：

1. 客户端发起HTTPS请求
2. 服务端配置

采用HTTPS协议的服务器必须要有一套数字证书，可以自己制作，也可以向组织申请，区别就是自己颁发的证书需要客户端验证通过，才可以继续访问，而使用受信任的公司申请的证书则不会弹出提示页面。

这套证书其实就是一对公钥和私钥，如果对公钥和私钥不太理解，可以想象成一把钥匙和一个锁头，只是全世界只有你一个人有这把钥匙，你可以把锁头给别人，别人可以用这个锁把重要的东西锁起来，然后发给你，因为只有你一个人有这把钥匙，所以只有你才能看到被这把锁锁起来的东西。

3. 传送证书
4. 客户端解析证书

如果证书没问题，那么就生成一个随机值，然后用证书对该随机值进行加密。

5. 传送加密信息

这部分传送的是用证书加密后的随机值，目的就是让服务端得到这个随机值，以后客户端和服务端的通信就可以通过这个随机值来进行加密解密。

6. 服务端解密
7. 传输加密后的信息
8. 客户端解密

HTTPS握手

结合上面的流程图，可以看出整个流程分解为：

1. 客户端向服务器发送握手请求报文，告诉服务器，我支持的协议版本，加密套件，随机数等信息。
2. 服务器收到响应，选择双方都支持的协议，套件，向客户端发送报文。同时服务器也将自己的证书，随机数发送到客户端。
3. 客户端自己随机生产预主密钥，通过服务器证书中的公钥，用协商的算法加密，将加密后的预主密钥发送给服务器。同时浏览器用客户端随机数，服务器随机数，预主秘钥生成主密钥。
4. 服务器用自己的私钥解密加密过的预主密钥。

之后，客户端与服务器用相同的算法根据客户端随机数，服务器随机数，预主密钥生产主密钥，之后的通信都将用主密钥加密解密。

如何解决TCP粘包问题

1. 使用带有消息头的协议、消息头存储消息开始标识及消息长度信息，服务端获取消息头的时候解析出消息长度，然后向后读取该长度的内容。
2. 设置定长信息，服务端每次读取既定长度的内容作为一条完整消息，当消息不够长时，空位补上固定字符。
3. 设置消息边界，服务端从网络流中按消息编辑分离出消息内容，一般使用'\n'。

HTTP报文格式

HTTP报文有请求报文和响应报文两种

这两种报文都由三部分组成：开始行、首部行、实体主体

• 开始行

区分请求报文与响应报文。

请求报文的开始行由方法【空格】URL【空格】HTTP版本组成

GET /csrfToken HTTP/1.1

响应报文的开始行由HTTP版本【空格】状态码

HTTP/1.1 200 OK

• 首部行

1. 是用来说明浏览器、服务器或报文主体的一些信息。
2. 可以有好几行，也可以不使用
3. 每个首部行都是由 首部字段名、[空格] 和 值 组成
4. 每个首部行在结束地方都有 CRLF（\r\n）

• 实体主体
• 在请求报文中，一般是post/put提交的表单信息。与首部行之间有\r\n。

HTTP状态码

• 1xx 消息

这一类型的状态码，代表请求已被接收，需要继续处理。这类响应是临时响应，只包含状态行和某些可选的响应头信息，并以空行结束。

• 2xx 成功

这一类型的状态码，代表请求已成功被服务器接收、理解并接受。

• 3xx 重定向

这类状态码代表需要客户端采取进一步的操作才能完成请求。通常，这些状态码用来重定向，后续的请求地址在Location域中指明。

• 4xx 客户端错误

这类状态码代表了客户端看起来可能发生了错误，妨碍了服务器的处理。除非响应的是一个HEAD请求，否则服务器就应该返回一个解释当前错误状况的实体，以及这是临时的还是永久性的状况。这些状态码适用于任何请求方法。浏览器应当向用户显示任何包含在此类错误响应中的实体内容。

• 5xx 服务器错误

表示服务器无法完成明显有效的请求。这类状态码代表了服务器在处理请求的过程中有错误或者异常状态发生，也有可能是服务器意识到以当前的软硬件资源无法完成对请求的处理。除非这是一个HEAD请求，否则服务器应当包含一个解释当前错误状态以及这个状况是临时的还是永久的解释信息实体。浏览器应当向用户展示任何在当前响应中被包含的实体。这些状态码适用于任何响应方法。

Session和Cookie

• 由于HTTP协议是无状态的协议，所以服务端需要记录用户的状态时，就需要用某种机制来识别具体的用户，这个机制就是Session。在服务器端保存session的方法有很多，内存、数据库、文件都有。集群的时候也要考虑session的转移，在大型网站上，一般会有专门的session服务器集群，用来保存用户会话，这个时候session信息都是放在内存中的，使用一些缓存服务来放session。
• 那么，服务器如何识别特定的用户，并取出相应的session？这个时候Cookie就登场了。每次HTTP请求的时候，客户端都会发送相应的Cookie信息到客户端。实际上大多数的应用都是用Cookie来实现session跟踪的，第一次创建session的时候，服务端会在HTTP协议中告诉客户端，需要在Cookie里面记录一个session ID，以后每次请求把这个会话ID发送给服务器，就可以知道对应的session了。如果浏览器禁用了Cookie，会使用一种叫做URL重写的技术来进行会话跟踪，即每次HTTP交互，URL后面都会被附加上一个参数，服务端根据这个来识别用户。

定时器的实现

• 最小堆定时器
• 时间轮定时器

1. 轮盘上有若干个插槽
2. 把tick放进合适的插槽中
3. 每次轮训直接出发插槽里面的tick

服务器主动推送新消息给客户端

客户端与服务端维持一个长连接，客户端定时向服务端发送心跳以维持这个长连接。当有新消息过来的时候，服务端查出该消息对应的TCP Channel的ID并找到对应的通道进行消息下发。

1. Ajax轮训
2. Ajax长轮询

网络字节序

网络字节顺序是TCP/IP中规定好的一种数据表示格式，它与具体的CPU类型、操作系统等无关，从而可以保证数据在不同主机之间传输时能够被正确解释。网络字节顺序采用big endian排序方式。

1. 大端和小端

“大端”和“小端”表示多字节值的哪一端存储在该值的起始地址处；小端存储在起始地址处，即是小端字节序；大端存储在起始地址处，即是大端字节序。

2. 在进行网络通信时是否需要进行字节序转换

相同字节序的平台在进行网络通信时可以不进行字节序转换，但是跨平台进行网络数据通信时必须进行字节序转换。

原因如下：网络协议规定接收到的第一个字节是高字节，存放到低地址，所以发送时会首先去低地址取数据的高字节。小端模式的多字节数据在存放时，低地址存放的是低字节，而被发送方网络协议函数发送时会首先去低地址取数据（想要取高字节，真正取得是低字节），接收方网络协议函数接收时会将接收到的第一个字节存放到低地址（想要接收高字节，真正接收的是低字节），所以最后双方都正确的收发了数据。而相同平台进行通信时，如果双方都进行转换最后虽然能够正确收发数据，但是所做的转换是没有意义的，造成资源的浪费。而不同平台进行通信时必须进行转换，不转换会造成错误的收发数据，字节序转换函数会根据当前平台的存储模式做出相应正确的转换，如果当前平台是大端，则直接返回不进行转换，如果当前平台是小端，会将接收到得网络字节序进行转换。

数据库

数据库事物的四大特性

ACID

• 一致性：  一致性是指在事务开始之前和事务结束以后，数据库的完整性约束没有被破坏。这是说数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性。
• 原子性：事物是一个不可再分割的工作单位，事物中的操作要么都发生，要么都不发生
• 隔离性：多个事务并发访问时，事务之间是隔离的，一个事务不应该影响其它事务运行效果。
• 持久性：在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。

其中，原子性、隔离性、持久性都是为了实现一致性这个目标的手段。

隔离级别

1. 读未提交，其隔离级别最低，允许脏读。换句话说就是，如果一个事务正在处理某一数据，并对其进行了更新，但是同时没有提交事务，允许另一个事务访问
2. 读已提交，和读未提交的区别就是：读未提交可以读取到别人没有提交的数据，但是读已提交只能读取到别人提交后的数据，事务进行的中间值不会读取到
3. 可重复读，简单来说就是事务的处理过程中多次读取同一数据的时候，这个值不会发生改变，其值都和第一次查询到的数据是一致的
4. 串行化，是最严格的隔离级别，它要求所有的事务都是串行执行，既事务只能一个接一个的进行处理。

脏读（读取未提交数据）

A事务读取B事务尚未提交的数据，此时如果B事务发生错误并执行回滚操作，那么A事务读取到的数据就是脏数据。就好像原本的数据比较干净、纯粹，此时由于B事务更改了它，这个数据变得不再纯粹。这个时候A事务立即读取了这个脏数据，但事务B又回滚把数据回复成原来干净的数据，而事务A并不知道，最终结果就是事务A读取了此次的脏数据。

不可重复读（前后多次读取，数据内容不一致）

事务A在执行读取操作，由整个事务A比较大，前后读取同一条数据需要经过很长的时间。而在事务A第一次读取数据，比如此时读取了C的年龄为20岁，事务B执行更改操作，将C的年龄更改为30岁，此时事务A第二次读取到小明的年龄时，发现其年龄是30岁，和之前的数据不一样了，也就是数据不重复了，系统无法读取到重复的数据，称为不可重复读。

幻读（前后多次读取，数据总量不一致）

事务A在执行读取操作，需要两次统计数据的总量，前一次查询数据总量后，此时事务B执行了新增数据的操作并提交后，这个时候事务A读取的数据总量和之前统计的不一样，就像产生了幻觉一样，平白无故的多了几条数据，称为幻读

三大范式

1. 第一范式

确保每列保持原子性。

第一范式是最基本的范式。如果数据库表中的所有字段值都是不可分解的原子值，就说明该数据库表满足了第一范式。

2. 第二范式

确保表中的每列都和主键相关。

第二范式在第一范式的基础之上更进一层。第二范式需要确保数据库表中的每一列都和主键相关，而不能只与主键的某一部分相关。也就是说在一个数据库表中，一个表中只能保存一种数据，不可以把多种数据保存在同一张数据库表中。

消除非主属性对码的部分函数依赖

3. 第三范式

第三范式需要确保数据表中的每一列数据都和主键直接相关，而不能间接相关。

消除非主属性对码的传递函数依赖

4. BC范式

消除主属性对码的部分和传递函数依赖

索引

• 索引怎么加快查询速度？

将无序的数据变成相对有序

索引的底层数据结构是B+树，B+树作为树的一种实现，能够让我们很快的查找出对应的记录。

很明显的是：没有用索引的话，我们需要遍历双向链表来定位对应的页，现在只要通过对树节点进行判断就可以很快的定位到对应的页上了。

• 索引会降低增删改的速度

由于B+树是一颗平衡树，如果对这棵树进行增删改的话，那会破坏树的原有结构。而要维持平衡，就必须做额外的工作。正是因为这些额外的工作开销，导致索引会降低增删改的速度。

• 聚集和非聚集索引

简单概括：

• 聚集索引就是以主键创建的索引
• 非聚集索引就是以非主键创建的索引

区别：

• 聚集索引在叶子节点存储的是表中的数据
• 非聚集索引在叶子节点存储的是主键和索引列
• 使用非聚集索引查询数据时，拿到叶子上的主键再去查到想要查找的数据

创建多个非聚集索引的时候，会生成多个索引树（所以过多创建索引会占用磁盘空间）

• 索引最左匹配原则
• • 索引可以是简单的一个列，也可以复杂如多个列，即联合索引
  • 如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在，遇到范围查询就不能进行进一步匹配了，后续退化为线性查找
  • 因此，列的排列顺序决定了可命中索引的列数。

例子：

如有索引（a，b，c，d），查询条件a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中a、b、c，无法命中d。

锁

1. 共享锁（又称读锁）、排他锁（又称写锁）：

InnoDB引擎的锁机制：InnoDB支持事务，支持行锁和表锁用的比较多，Myisam不支持事务，只支持表锁。

共享锁（S）：允许一个事务去读一行，阻止其他事务获得相同数据集的排他锁。

排它锁（X）：允许获得排它锁的事务更新数据，阻止其他事务取得相同数据集的共享读锁和排他写锁。

意向共享锁（IS）：事务打算给数据行加共享锁，事务在给数据行加共享锁之前必须先取得该表的IS锁。

意向排他锁（IX）：事务打算给数据行加排它锁，事务再给一个数据行加排它锁前必须先取得该表的IX锁。

2. 乐观锁、悲观锁

悲观锁：指的是对数据被外界（包括本系统当前的其他事务，以及来自外部系统的事务处理）修改持保守态度，因此，在整个数据处理过程中，将数据处于锁定状态。悲观锁的实现，往往依靠数据库提供的锁机制。

乐观锁：乐观锁假设认为数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则让返回用户错误的信息，让用户决定如何去做（一般是回滚事务）。如何实现乐观锁？一般来说有以下两种方式：

两段加锁协议

1. 扩展阶段

在对任何数据项的读、写之前，要申请并获得该数据项的锁

2. 收缩阶段

每个事务中，所有的加锁请求必须先于解锁请求。

InnoDB和MyISAM比较

InnoDB是事务型的。实现了四个标准的隔离级别，默认级别是可重复读。表是基于聚簇索引建立的，它对主键的查询性能有很高的提升。

InnoDB支持在线热备份。

MyISAM设计简单。

MyISAM只支持表锁，而InnoDB支持行级锁。

MyISAM支持全文索引，地理空间索引。

InnoDB支持外键，MyISAM不支持。

分库与分表

1. 分表与分区的不同

分表，就是将一张表分成多个小表，这些小表拥有不同的表名；而分区是将一张表的数据分为多个区块，这些区块可以存储在同一个磁盘上，也可以存储在不同的磁盘上，这种方式下表依然只有一个。

2. 使用分库与分表的原因

随着时间和业务的发展，数据库中的表会越来越多，并且表中的数据量也会越来越大，那么读写操作的开销也会随之增大。

3. 垂直切分

将表按功能模块、关系密切程度划分出来，部署到不同的库上。例如，建立商品数据库、用户数据库等，分别用来存储项目与商品有关的表和与用户有关的表。

4. 水平切分

把表中的数据按照某种规则存储到多个结构相同的表中，例如按id的散列值、性别等进行划分。

5. 垂直切分与水平切分的选择

如果数据库中的表太多，并且项目各项业务逻辑清晰，那么垂直切分是首选。

如果数据库的表不多，但是单表的数据量很大，应该选择水平切分。

算法\数据结构

TopK问题

• 堆排序

思路：只找到TopK，而不对TopK进行排序

先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的K个元素。

接着，从第k+1个元素开始扫描，和堆顶比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。

• 快排

void quick_sort(int[]arr, int low, inthigh){
         if(low== high) return;
         int i = partition(arr, low, high);
         quick_sort(arr, low, i-1);
         quick_sort(arr, i+1, high);
}

核心思路:分治法，把一个大的问题，转化为若干个子问题，每个子问题都解决，大的问题便随之解决。

分治法有一个特例，叫减治法。

减治法，把一个大的问题，转化为若干个子问题，这些子问题中只解决一个，大的问题便随之解决。

快速排序的核心是：

i = partition(arr,low,high)

顾名思义，partition会把整体分为两个部分。

更具体的，会用数组arr中的一个元素为划分依据，将数据arr[low,high]划分成左右两个子数组：

• 左半部分，都比t大
• 右半部分，都比t小
• 中间是划分元素

以TopK的数组为例，先用第一个元素t=arr[low]为划分依据，扫描一遍数组，把数组分成了两个半区：

• 左半区比t大

• 右半区比t小

• 中间是t

partition返回的是t最终的位置i。

很容易知道，partition的时间复杂度是O(n)。

那么partition和TopK有什么关系呢？

TopK是希望求出arr[1,n]中最大的K个数，如果找到了第k大的数，做一次partition，就可以一次性找到最大的K个数了。

于是，问题变成了找到arr数组中的第K个最大的数。

再来看看第一次的partition，划分之后：

• 如果i>k，则说明arr[i]左边的元素都大于k，于是只递归arr[1,i-1]里第k大的元素即可；
• 如果i<k，则说明第k大的元素在右边，于是只递归arr[i+1,n]里第k-i大的元素即可；

int RS(arr, low, high, k){
  if(low== high) return arr[low];
  i= partition(arr, low, high);
  temp= i-low; //数组前半部分元素个数
  if(temp>=k)
      return RS(arr, low, i-1, k); //求前半部分第k大
  else
      return RS(arr, i+1, high, k-i); //求后半部分第k-i大
}

rand5 to rand7

对于任意的randn()，都可以通过randn()×n+randn()来扩展随机数范围。

然而，尽管可以生成rand25()，但采取上述方式来获取rand7()会消耗大量的时间，因此不能消极等待小于7的随机数的出现。

于是，可以使用rand25()%7来得到rand7()，但是这样又会导致概率不均衡，因此采用rand25()来生成rand21()，然后通过rand21对7取余数来生成rand7()

int rand7()
{
  int res = rand5()*5 + rand5();
  while(res>20)
  {
    res = rand5()*5 + rand5();
  }
  return res%7;
}

动态规划

与分治法不同的是，适合于用动态规划求解的问题，经过分解得到的子问题往往不是互相独立的。若用分治法来解决这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果能够保存已解决子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

与分治法最大的差别是：适用动态规划求解的问题，经过分解后得到的子问题往往不是相互独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)

适用动态规划的问题必须满足最优化原理、无后效性和重叠性。

1. 最优化原理：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略。
2. 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。
3. 子问题的重叠性：动态规划将原来具有指数时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这就是动态规划的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。

红黑树

所谓红黑树，不仅是一个二叉搜索树，而且必须满足以下规则：

1. 每个节点不是红色就是黑色
2. 根节点为黑色
3. 如果节点为红，其子节点必须为黑；如果节点为红，则其父节点必须为黑
4. 任一节点到NULL，也就是树尾端的任何路径，所含的黑节点数目必须一样。

红黑树就是靠着以上四个规则来保持平衡。

以及，通过规则4，确保没有一条路径会比其他路径长出两倍。因而，红黑树是相对接近平衡的二叉树。

时间复杂度：O(logn)

B树

B树又名平衡多路查找树，它和平衡二叉树的不同有这么几点：

1. 平衡二叉树节点最多有两个子树，而B树每个节点可以有多个子树，M阶B树表示该树每个节点最多有M个子树。
2. 平衡二叉树每个节点只有一个数据和两个指向孩子的指针，而B树每个中间节点有K-1个关键字(可以理解为数据)和K个子树
3. B树的所有叶子节点都在同一层，并且叶子节点只有关键字，指向孩子的指针为NULL

一颗B树必须满足以下条件：

1. 若根节点不是终端节点，则至少有2棵子树
2. 除根节点以外的所有非叶子节点至少有M/2棵子树，至多有M棵子树
3. 所有的叶子节点都位于同一层

可以看出，B树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据的过程中，可以减少磁盘IO的次数，从而提高查找速度。

B树中的查找

1. 从根节点开始，如果查找的数据比根节点小，就去左子树找，否则去右子树
2. 和子树的多个关键字进行比较，找到它所处的范围，然后去范围对应的子树中继续查找
3. 以此循环，直到找到或者到叶子节点还没找到为止。

B树的平衡

1. 叶子节点都在同一层
2. 每个节点的关键字数为子树个数减一
3. 子树的关键字保证左小右大的顺序

B+树

一棵B+树需要满足以下条件：

1. 节点的子树数和关键字数目相同
2. 节点的关键字表示的是子树中的最大树，在子树中同样含有这个数据
3. 叶子节点中包含了所有的数据

特点：

1. 关键字数目和子树数目相同
2. 非叶子节点仅用作索引，关键字和子节点有重复元素
3. 叶子节点用指针连在一起

优点：

1. 层级更低，IO次数更少
2. 每次都需要查询到叶子节点，查询性能稳定
3. 叶子节点形成有序链表，范围查询方便。

使用场景

文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。

Hash算法

Hash就是把任一长度的输入，通过hash算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会hash成相同的输出，而不可能从hash值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息的函数。

简单的说，hash就是找到一种数据内容和数据存放地址之间的映射关系。

一致性哈希

一致性哈希算法也是使用取模的方法，只是，一致性哈希算法是对2^32取模。一致性哈希算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形)，那么整个哈希环会呈现如下形式：

整个空间按照顺时针的方向组织，圆环的正上方的点代表0,0点右侧的第一个点代表1，以此类推，2\3\4\5\6……直到2^32-1。

下一步，将各个服务器的特征(IP或主机名)进行Hash运算，算出来的结果在圆环上进行标记：

接下来当有数据需要存储或查询的时候，只需要对数据的key使用相同的hash算法进行运算得出哈希值，确定出数据在圆环中的位置，然后按照顺时针的方向进行移动，存入遇到的第一个服务器节点上。

一致性哈希的容错性和可扩展性

假设Node C宕机，可以知道对象A、B、D不会受到影响，只有C对象需要被重定位到Node D。一般情况下，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器之间的数据，其他不会受到影响

而如果想要在系统中增加一台服务器Node X，如下图所示：

此时，对象A、B、D不受影响，只有对象C需要重新定位到X。

所以，一致性哈希算法对于节点的增减都只需要重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

数据倾斜问题

一致性哈希算法在服务节点太少的时候，容易因为节点分布不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题，例如系统中如果只有两台服务器，如果节点都处在同一个半圆上，此时必然会造成大量数据集中在一台服务器上。

为了解决这个问题，一致性哈希引入了虚拟节点机制，对每一个服务节点计算多个哈希，每个计算结果位置都防止一个服务节点。

布隆过滤器

布隆过滤器的核心是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k

以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。

查询元素是否存在集合中的时候，同样的方法将元素通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。

可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

应用场景

常见的应用场景有，利用布隆过滤器减少磁盘IO或网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

排序