DB 常见面试题目

发表于 2020-03-03 | 更新于 2020-03-28 | 分类于数据库

概念

数据模型由三部分构成：数据结构，数据操作和完整性约束。
关系模型三部分构成：关系数据结构，关系数据操作和关系完整性约束。
关系数据库是以集合论中关系的概念为基础发展起来的。

域：一组具有相同数据类型的值的集合。比如说{男，女｝，自然数等。
n个域的笛卡尔积上的任意一个子集称为这n个域的一个关系。当n=1时，称为一元关系，n=2时，称为二元关系。
关系中的每一行对应一个元组。
关系模式：关系模式是对关系的描述，包括关系名，属性名，属性的长度以及属性之间固有的数据关联关系，关系模式一般简记做关系名和属性名的集合。
关系模式的集合称为关系数据库模式，是对数据库中所有数据逻辑结构的描述。

键：能够唯一标识元组的属性或者属性组称为关系的键。
候选键：关系中能够起标识作用的键称为候选键。
主键：在一个关系中，如果有多个候选键，选其中的一个键作为主键。
外键：假设关系R的一个或一组属性F，但不是R的键。如果F与基本关系S的主键KS对应，称F是基本关系R的外键。

完整性约束：
实体完整性：主键的值不能为空或部分为空。
参照完整性：是对关系中作为外键的值的约束。如果关系R1中属性A是另一个关系R2中的主键，对于关系R1中的任意一个元组在属性A上的值或者为空，或者为R2中某个元组的值。
用户定义的完整性：用户根据需要设计的约束条件，比如成绩不能为负数，输入格式有要求。

数据库的三级模式结构，是三个抽象级别，为了实现数据的转换，数据管理系统必须提供两层映射功能，即外模式和模式的映射，模式和内模式的映射。
外模式（用户模式），外模式按用户视图定义数据，能够从模式中导出。
模式（逻辑模式），为了实现数据库数据的共享，进行数据库设计之后，得到的全局性数据逻辑关系的抽象和描写叙述。独立于数据的内模式
内模式（物理模式），用来描述数据在数据库中的存储和存取方式。

在数据库系统中，外模式可以有多个，而模式和内模式只能有一个。

SQL

在SQL中，关系模式称为基本表。基本表的集合形成数据库模式，对应三级模式结构的模式。
基本表在物理上与存储文件对应，所有存储文件的集合称为物理数据库。
视图构成外模式。

事务

什么是事务？
事务是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。
事务是恢复和并发控制的基本单位。

四个特性

Atom，原子性。要么全不做，要么全做。
Consistency，一致性。事务的执行结果必须是使数据库从一个一致性状态变成另一个一致性状态。
Isolation。并发执行的事务，一个事务的执行不能被其他事务干扰。
Durability。持久性。一个事务一旦提交，它对数据库中的数据的改变就应该是永久性的。

事务并发的问题

丢失更新。
不可重复读。
读脏数据。

事务的隔离级别

读未提交。
不可重复读。
可重复读。
串行化。

索引

是数据库管理系统中一个排序的数据结构，索引的实现通常使用B树或者B+树。

索引的优点

加快查找。

索引的缺点

耗费时间。
耗费空间。

索引的数据结构

为什么不使用hash。hash仅仅能满足=和IN查询，不能使用范围查询，因为hash后的hash值是无序的。
hash值也无法用来用来排序。
hash的冲突。

B树和B+树

为什么mysql使用B+树作为索引，而mongodb使用B树作为索引。
B+树的信息都存在叶子节点，并且叶子节点之间相互连接，便于进行顺序查找。B+树的单次查询时间是固定的（因为都在叶子节点）。
而B树在非叶子节点中也存有信息，单次查询时间最好是O(1)。单次平均查询时间要优于B+树，但是顺序查找的话，就没有B+树方便。

redis为什么是单线程的

看参考文献2的评论，别看文章！！！！

因为redis开始的使用场景是IO密集型的，单线程就可以满足，使用IO多路复用。而如果是CPU密集型的，就可以使用多线程。
而且多线程需要加锁，编码复杂，单线程避免了加锁。
线程上下文切换不是原因，IO和锁的开销要比线程上下文切换大的多。而且都多核CPU，根本不需要切换。

redis是key-value数据库，数据之间没有约束。

布隆过滤器[3]

布隆过滤器可以用来判断一个东西是不是一定不在某个集合或者可能存在在某个集合。

缓存穿透[4]

请求数据库中根本不存在的数据，这样子在缓存中查不到，就要到数据库查。

可以使用布隆过滤器，在数据库中插入一个key，更新一下布隆过滤器。这样子缓存中查不到，要到数据库查时，先使用布隆过滤器查一下是不是数据库中有这个东西。
或者直接在缓存中把这个查询key的结果置为空。

缓存雪崩

缓存的过期时间相同时，导致缓存在某一个时刻同时失效，所有的请求都转发到数据库。

加锁。
缓存过期时间不同，加上随机值。

缓存击穿

某个key过期时，忽然这一个key被高并发的访问，和雪崩的区别在于雪崩是多个key，而击穿是单个key。当请求发现缓存过期，都会从数据库加载并设置到缓存中，大并发的请求可能会把后台数据库压垮。

使用互斥锁。

参考文献

1.https://www.cnblogs.com/wenxiaofei/p/9853682.html
2.https://zhuanlan.zhihu.com/p/87233515
3.https://www.cnblogs.com/liyulong1982/p/6013002.html
4.https://www.cnblogs.com/bob-zb/p/12583624.html

UNIX advanced IO

发表于 2020-03-03 | 更新于 2020-03-14 | 分类于 UNIX

同步IO和异步IO

IO操作一般分成两个不同的阶段：

等待数据准备好
从内核向进程复制数据

比如说对于网络IO：

第一步通常是等待数据从网络中到达，然后复制到内核中的某个缓冲区。
把数据从内核缓冲区复制到应用进程缓冲区。

比如说对于系统调用read：

内核把数据在内核缓冲区中准备好。
然后把它复制到进程IO缓冲区。

而对于标准IO来说，还多了一个标准IO缓冲区。它们的设置是为了减少调用erad和write的次数。

同步IO操作导致请求进程阻塞，直到IO完成为止。在同步IO中，真正的IO操作会阻塞进程。不管是阻塞IO还是非阻塞IO，以及IO多路复用，信号驱动的IO模型，都是同步IO。
异步IO操作不导致请求进程阻塞，即使真正的IO操作也不会阻塞。相对于信号驱动的IO，内核通知我们的是什么时候可以启动一个IO操作，而异步IO模型是内核通知我们IO操作什么时候完成。

阻塞IO

所有的套接字都是阻塞的。从数据复制到内核，以及从内核复制到应用程序缓冲区，都是阻塞的。

非阻塞IO

非阻塞IO的意思是告诉内核如果当前的操作如果不能立即返回，而是要sleep才能完成时，返回一个错误。
等到某一次查询，数据已经准备了，然后进行相应的IO操作。

select和poll，epoll

IO复用模型的思想是同时处理多个文件描述符。

select和pselect

selecdt返回的条件：

等待的描述符准备好（读准备好，写准备好，异常准备好）只有两个异常的条件。
超时

满足任意一个就行。

poll

epoll

信号驱动的IO

利用信号，让内核在描述符就绪时发送SIGIO通知应用程序，然后调用相应的处理程序进行IO操作。

异步IO

内核把数据准备好，然后复制到应用程序缓冲区之后才通知我们。这个时候IO操作已经完成了。

记录锁

记录锁可以用来同步。打开一个空文件，使用第一个字节作为锁字节。要访问资源，需要对该字节加锁，要释放资源，需要对该字节解锁。
所以一个文件可以实现多个锁。

readv和writev

readv从文件描述符指定的文件中读取相应的数据到多个缓冲区。
writev将多个缓冲区中的内容写入文件描述符中。

readn和writen

适用于已经知道要读取和写入的字节数量的情景。其实就是多次调用非阻塞的read和write进行操作。

存储映射IO

mmap将一个磁盘文件映射到存储空间的一个缓冲区上。从缓冲区读，就相当于读文件中的相应字节。从缓冲区写，就相当于写文件中的相应字节。

参考文献

1.《APUE》第三版
2.《UNP》卷一

Network 常见面试题目

发表于 2020-02-29 | 更新于 2020-04-21 | 分类于面试

套接字

套接字是一个同一台主机内应用层和网络层之间的接口。由于套接字是在网络上建立网络应用程序的可编程接口，所以也把套接字称为应用程序和网络之间的应用编程接口。

一个UDP套接字是由目的IP地址和目的端口号标识的二元组。两个UDP报文段，只要目的IP地址和目的端口号一样，不论源IP地址和端口号是否一样，都被定向到相同的目的进程。
一个TCP套接字是由源IP地址，源端口号，目的IP地址，目的端口号构成的四元组。所有的这四元组都被用来进行多路分解。

常见应用层协议

DNS
FTP
HTTP
SMTP

HTTP

HTTP请求报文段

HTTP包含一行请求行和多行首部行。
请求行有三个字段：方法字段，URL字段，HTTP协议版本字段。
方法字段有GET，POST，HEAD，PUT和DELETE。

Host，目标主机。
Connection，浏览器告诉服务器不希望使用持久连接。
User-agent，浏览器。
Accept-language

HTTP响应报文段

一个状态行和6个首部行，然后是报文实体。
状态行：
协议版本，状态码和相应状态信息。
6个首部行：

Connection，不适用持久链接。
Date，服务器产生发送报文的时间。
Server，服务器类型。
Last-Modified，对象创建或者修改的最后日期。
Content-Length，发送内容的长度。
Content Type，发送内容的类型。

HTTP状态码[3,4, 5]

1xx信息
2xx成功
200 OK 请求成功
201 Created 当服务器按照客户端的的请求创建了一个新的资源时，发送此响应代码。
204 No Content。服务端拒绝对PUT，POST或者DELETE请求返回任何状态信息。返回空文件替换缓存。而304是使用上次的缓存。
3xx 重定向，客户端需要做一些额外的工作才能得到所需要的资源，他们通过用于GET请求。
301 Moved Permanently 服务器知道客户端请求的资源，但是不喜欢客户端使用当前URL。
302 Found。临时性重定向。不是永久性移动，而是临时性移动。比如说用户把uri保存为书签，出现301时，书签会被更新，出现302时不会。。
303 See Other。请求已经被处理，但是服务器返回的不是文档，是一个URI。和302功能一样，但是303明确表示客户端应该使用GET方法获取资源。
304 Not modified。客户端有数据主题，不需要重复发送。
307 Temporary Redict。临时性重定向，和302有着相同的意思。但是不会将POST修改成GET。
301,302,303响应状态码返回时，几乎所有的浏览器都会把POST改成GET，删除请求体，再次发送请求。尽管301,302是禁止将POST改成GET的，但是大家都会这么做。
4xx表示客户端错误
400 Bad Request，服务器收到了请求，但是不知道什么意思。
401 请求要求用户的身份认证，而客户端认证失败。
403 客户端的请求正确，但是服务端拒绝此请求，暗示了请求的资源确实存在。
404 Not Found，服务器无法把客户端请求的URI转换为一个资源。
405 客户端中请求的方法被禁止
5xx表示服务器错误
500 Internal Server Error对于大多数web框架，如果在执行请求处理代码时遇到了异常，就发送此代码。
502 bad gateway
503 Service Unavaiable，服务器当前不能处理处理客户端的请求，可能一会就好了。
505 HTTP Version Not Support

GET和POST区别

GET是安全的，POST是不安全的。
GET是幂等的，POST是不幂等的。
GET是可缓存的，POST通常是不可缓存的。

GET一般是请求服务器的指定资源，是安全，幂等，可缓存的。而post一般是根据请求的payload对指定的资源机械能给你处理，POST是不安全的，不幂等的，不可缓存的。

其他：

GET会把请求的数据会放在URL后面，而POST把请求的数据放在body中。注意，GET的body也可以存放request body，这是针对于接口来说的。
GET请求提交的url数据最多是1024字节是浏览器或者服务器限制的，而post则没有限制。
GET和POST都不安全，HTTP本身是明文协议，无论是url,header还是body，都是在网络中明文传播的。只不过url中的数据是可以在浏览器中直接看到的，而header和body中的数据更麻烦一些，需要使用抓包软件查看。
但是GET的效率要比post高。

HTTPS和HTTP[2]

HTTP协议是明文协议，TCP和UDP也没有加密。于是就有了SSL，利用非对称密码体系对发送的数据进行加密。
HTTPS是在TCP连接之后由客户端发起的。其实使用到了对称加密技术和非对称加密技术。

客户端发送一个Client Hello给服务器，包含一个随机数，以及客户端支持的加密条件和SSL版本。
服务端回应一个Server Hello给客户端，服务器选定一组加密套件，然后和第二个随机数，以及服务器的证书（包含服务器的公钥和名字）一块发送给客户端。服务器是由CA机构发送到，一个大家都信任的机构。
客户端验证服务端的证书的真实性。（使用CA的数字证书，服务端的证书含有CA对服务器信息的签名，然后客户端使用CA证书中的公钥对服务端的数字证书进行验证签名，验证签名即使用相同的摘要算法对服务器的信息进行摘要，然后和CA证书的签名对比。）
验证成功之后，生成第三个随机数，使用服务端的公钥对这个随机数加密生成PreMaster Key，然后发送给服务端。
服务端用自己的私钥解密生成PreMaster Key。这个时候，两边都拥有三个随机数，使用相同的算法生成一个秘钥。之后的通信都使用这个秘钥进行。

输入www.baidu.com发生的一切

用户输入网址。
DNS解析。一般情况下，本机是会知道DNS服务器的IP地址的。递归查询和迭代查询获得目的主机的IP地址。一般是在同一个局域网内，通过ARP请求，查询对应的DNS服务器的MAC地址，然后把请求包发给它。[8]
TCP连接。三次握手。
发送请求。
接收HTTP相应报文
浏览器渲染。

Cookie用户和服务器的交互。因为HTTP是无状态的，简化了服务器的设计。当想要识别用户的时候，可能限制用户的访问或者想把用户和内容关联起来。HTTP使用了cookie：
cookie有四个部分：

HTTP响应报文中有一个cookie首部行。
HTTP请求报文中有一个cookie首部行。
用户端系统有保留一个cookie文件。
Web站点后台有一个cookie数据库。

Web缓存

Web缓存器也叫代理服务器，它有自己的磁盘存储空间，并在自己的磁盘存储空间中保存最近请求过的对象拷贝。
然后可以配置浏览器，将用户的所有HTTP请求首先指向Web缓存器，一旦配置了浏览器，每个浏览器对象的请求首先被定向到Web缓存器。

浏览器建立一个到Web缓存器的TCP连接，并发送一个HTTP请求。
Web缓存器检查缓存是命中。
命中的话，Web缓存器向发送一个条件GET，查询Last-modified。
没有命中的话，Web缓存器请求该对象，并将其缓存。
Web缓存器向客户机浏览器发送报文。

TCP和UDP的选择

DNS通常采用UDP，因为TCP需要建立连接，会引入建立TCP连接的时延，这样子会慢得多。如果没有收到响应，就会向另一台DNS服务器发送查询，或者通知调用的程序它不能获得响应。[9]
而HTTP使用TCP而不是UDP，因为web网页需要的是可靠性。

UDP

UDP相对于TCP的优势：

应用层能更好的控制要发送的数据和发送时间。
无需连接建立。
无连接状态。
分组首部开销小。TCP报文段有20字节的首部开销，而UDP只有8字节的开销。

UDP报文段结构

UDP报文段的首部共8个字节，64位，每个字段8位，共4个字段，：

16位源端口号
16位目的端口号
16位长度字段，长度字段包含了首部在内的UDP报文段的长度（以字节为单位）。
16位检验和

UDP校验和

UDP校验和提供了差错检测功能，但是不能进行差错恢复。为什么UDP校验和work？
为什么要进行差错校验？链路中可能出错，内存中也可能出错。UDP必须在端到端基础上在运输层提供差错校验。
出错后如何处理。一些实现是丢弃受损的报文段，一些是将受损的报文段交给应用程序并告警。

可靠数据传输原理

停止等待协议

为了解决分组可能出错的情况，引入自动重传请求。自动重传请求协议需要另外三种协议：差错检验，接收方反馈和重传。
当一个分组到达时可能出错，接收方进行进行差错校验，如果出错，发送一个NAK给发送方。如果没有失败，发送一个ACK给接收方。
直到发送方确定接收方已经收到当前分组之后（收到一个ACK），才会继续发送新数据，这就是停止等待协议。如果收到一个NAK，就会重传当前分组。（接收方反馈）
但是ACK和NAK也可能出错或者丢失，通过引入重传解决这个问题。
到底什么时候重传呢？等待一个RTT太久了，可以使用一个定时器设置一个时间，超过这个时间就重传。
这样子在接收方引入了冗余分组的问题。冗余分组的问题在于不知道接收方发送的ACK或者NAK是否被发送方接收，或者是分组没有丢失，等到了一段时间又到了。接收方不知道接收到的分组到底是哪一个，是重发的分组还是新的分组。可以通过引入分组序号解决这个问题。在停止等待协议中，一个比特的分组序号就够了。所以也叫比特交替协议。

流水线可靠数据传输协议

停止等待协议的效率太低了。流水线可靠数据传输协议不是一次只发一个分组，而是一次发送多个分组，就好像一条流水线一样。这就产生了几个问题：

必须增加序号范围，原来只要一个比特就够了，现在需要多个。
协议的发送方和接收方也必须能够缓存多个分组。
流水线中如果分组丢失了，有两种方式进行差错恢复，回退N步（GBN）和选择重传（SR）。

回退N步

GBN的发送方要处理是三个工作，准备N个分组，处理接收方返回的ACK，以及超时重传。
GBN的接收方要处理的工作，只有接收到的分组的序号和上一次相同，会返回给发送方一个ACK，GBN采用累计确认（对序号n的分组的确认表明接收方已经正确接收到n以及n之前的分组了）。所有其他情况，都会丢弃分组。比如失序分组，接收方应该接收序号为n的分组，但是收到了序号为n+1的分组，就会丢弃，而不是缓存。

GBN维护一个大小为N的窗口。对于发送方，维护一个大小为N的窗口，如果这N个分组的ACK都没有收到，就不会发送新的数据，等待接收方返回ACK。发送方还有超时设置，（发送方发送的分组丢了，或者接收方返回的ACK丢了），都会重传。

选择重传

GBN有时候会效率太低，因为一个分组丢失，可能导致重传整个N个分组。选择重传可以用来解决这种问题。

TCP

TCP累计确认和GBN，选择重传之间的关系

GBN是滑动窗口协议，虽然也提供累计确认，但是它不会缓存失序报文，会把它们全部丢弃。假设序号为n的报文段丢失了，然后需要发送方重传n之后的所有报文。而TCP的发送方至多只会重传一个报文段，如果TCP接收方接收到了
选择重传对失序报文进行缓存，但是没有提供累计确认。

可靠数据传输

TCP发送方有三个与发送和重传有关的主要事件：

数据处理。TCP从发送缓存重拿数据，加上TCP首部，传递给IP层。然后传递给网络，TCP接收方的接收缓存获取数据。
超时。
通过重传引发超时的报文响应超时时间。如果多次超时的话，就倍增超时时间间隔。
冗余ACK触发快速重传（为什么发送方收到三个冗余ACK就立即快重传）。冗余ACK是对按序接收到的最后一个字节数据进行重复确认。
ACK处理。如果收到的ACK是窗口的最小未确认序号，那么修改窗口的最小未确认序号。

三次握手

A向B发送一个SYN报文段，并且包含自己的初始序列号。
B向A发送一个SYNACK报文段，并且包含自己的初始序列号。同时分配连接缓存，变量等。
A向B发送一个ACK报文段，不是SYN报文段。

为什么要随机初始化一个报文段序号

减少上次TCP连接中的报文段被当做两台主机之间新的TCP连接中的报文段。

为什么是三次握手而不是两次或者四次

其实是四次挥手，只不过第二次和第三次可以合并起来了。三次挥手的目的是确立TCP双方都能获得对方的初始序号。
为什么不是两次？如果A向B发送一个请求，B回应一个请求。而B的回应丢了，A就无法和B进行通信。如果设计成A重传，那么可能会建立很多个连接。如果设计成B重传，为什么要B重传？不是两次握手吗？他怎么知道要重传。这些都是如果设计成两次握手需要考虑的问题。
对于三次握手来说，如果

A发给B的丢了，A超时重传。
B发给A的丢了，B超时重传。B分配缓存，变量等。
A又发给B的丢了，这时候B已经认为建立了连接。
如果双方都没有数据，那么会触发第二步的超时重传。
如果A要发送数据，那么A会直接把数据发给B，就肯定建立连接了。
如果B要发送数据，也会触发第二步的超时重传。

四次挥手

A发给B FIN报文段。A执行主动关闭。
B发给A ACK。B进行WAIT-TIME。等待B终止连接，这个时候B可以给A发送数据，但是A不能给B发送数据。B执行被动关闭，B处于CLOSE_WAIT状态。
B发给A FIN报文段。A收到报文段之后处于TIME_WAIT状态。
A发给B ACK。这个时候A要等待30s或者1分钟，两分钟。因为需要确认B那边收到了ACK，否则的话，B就无法关闭。

流量控制

TCP通过让发送方维护一个16位的接收窗口（是接收方的）的变量来提供流量控制。不正式的说，接收窗口用于告诉发送方，接收方还有多少可用的缓存空间。TCP是全双工的，两端都维护一个接收窗口。
接收方将自己的缓冲区大小填入TCP首部的窗口长度字段。这个字段是多少：缓冲区的大小 - （缓冲区中的最后一个字节编号 - 从缓冲区中读出的最后一个字节）。
如果接收方窗口大小为0怎么办？这时发送方不给接收方发报文，而接收方也不发，只有在有数据或者ACK要发的时候，接收方才会给发送方发报文。随着接收方应用程序从缓冲区取走数据，发送方也不能继续发数据。这个时候怎么办？规定：当接收方的接收窗口大小为0时，发送方会不断发送含有一个数据字节的报文段。

为什么要有流量控制，为了防止快速的发送设备发出的数据过多，导致慢速的接收设备处理不过来，而发生大量数据的丢失。

拥塞控制

分组重传是网络拥塞的征兆，却不能解决网络拥塞问题。
什么时候知道出现了拥塞：

超时
收到3个冗余ACK。

为什么要有拥塞控制：

慢启动。
快恢复。收到三个ACK以后的方式叫做快恢复。
快重传。

开始时，指数方式增加，收到超时ACK时开始线性增乘性减。
但是如果发生超时，执行慢开始，即将拥塞窗口变为1MSS，然后指数速度增加，直到遇到超时事件的一半窗口值，开始线性增加。通过设置一个阈值来实现。

TIMEWAIT过多[6]

修改内核设置：

开启内核中TCP重用。
开启内核中TCP中快速回收。
修改TIMEOUT

CLOST_WAIT太多[7]

比如说一个爬虫服务器，爬取其他服务器上的内容，如果没有相应的内容，对方会断开连接，这时候爬虫服务器上的程序是被动断开，如果没有执行close引发第三次挥手，就会有很多CLOSE_WAIT。

long fat network

高带宽和长时延网络情况，被称为长肥网络。带宽和时延的乘积表示网络通道的容量，也就是能够在网络中缓冲的数据量，显然增加带宽和时延都增加在网络中缓冲的数据量。但是随着它们乘积的不断变大，TCP的局限就开始显露出来。常规的窗口大小是16位的，能接收和发送的最大大小为65535，而BDP远大于这个值。TCP就不得不发送一会数据就等待ACK，极端情况下有点像停止等待协议。
缺点

窗口小，序号少，无法充分利用带宽。窗口扩展项。
时延长。快重传。
序号用的很快。PAWS算法。
RTT比较难测量。引入时间戳。

TCP和UDP的区别

TCP面向连接，UDP无连接。
TCP提供可靠数据传输，UDP提供不可靠数据传输。
TCP的逻辑通信信道是全双工的可靠信道，而UDP是不可靠信道。
TCP面向字节流，把数据看成一个无结构但是有序的字节流。UDP面向报文段。
TCP有流量控制，拥塞控制，UDP无。
TCP很慢，而UDP很快。
TCP首部20个字节，UDP是8个字节。

Dos攻击

Dos（拒绝服务）攻击是一种宽泛类型的攻击，可以分为三类：

弱点攻击
带宽洪泛。攻击者向目的主机发送大量的分组，导致目标的介入链路变得非常拥塞，使得合法的分组无法到达服务器。
连接洪泛。创建大量的全开或者半开TCP连接。

DDos攻击，分布式拒绝服务攻击。

SYN洪泛攻击

攻击者发送大量的SYN报文段，而不完成TCP握手的第三步，服务器不断地为这些半开连接服务器分配资源，导致服务器资源被迅速消耗。
怎么预防？SYN cookies，当服务器收到一个TCP连接时，不生成一个TCP半开连接，只生成一个初始序列号（精心计算的序列号，被称为cookie），然后发送这种序列号的SYNACK报文段。
如果客户机是合法的，客户机返回一个ACK，服务器收到ACK。然后利用这个ACK计算一个，这个ACK是否对应客户机发送的SYN报文段，如果是，生成一个全开的连接。

DNS攻击

DDos带宽洪泛攻击。攻击者向多个DNS根服务器发送大量的分组，使得大多数合法的DNS请求得不到回答。比如发送大量的ICMP报文。
怎么预防？分组过滤器，过滤ICMP报文。还有就是本地DNS服务器缓存了顶级域名服务器的地址。使得请求绕过了DNS根服务器。

传输层协议

TCP协议。
UDP协议。
运输层协议是在端系统而不是网络路由器中实现的。
端口号。
socket？

网络层协议

IP协议，IP协议为主机之间提供了逻辑通信，它的服务模型是尽力而为交互服务。
ICMP协议。互联网控制消息协议。最典型的应用是差错报告。ICMP报文有一个类型字段和一个编码字段，并且包含由该ICMP报文首次生成的IP数据报的首部和前8字节内容，以便于发送方能够确定引发该差错的数据报。
ping程序发送一个ICMP类型为8编码为0的报文到指定主机（表示回显请求），看到该回显请求的目的主机发送一个类型0编码为0的报文回显回答。
traceroute原理。traceroute利用ICMP报文实现，源主机中的该程序向目的主机发送一系列普通的IP数据报，每一个数据报都携带了一个具有不可达UDP端口号的UDP报文段，第i个报文段的TTL(time to live，确保数据报不会永远在网络中循环，每过一个路由器，字段值减一)是i。同时，源主机为每个数据报启动定时器，当第i个数据报到达第i个路由器时，TTL为0。根据IP协议的规则，路由器会向源主机发送一个ICMP告警报文（类型为11，编码为0）。该告警报文含有路由器的名字和IP地址，该ICMP报文到达源主机时，源主机从定时器得到RTT，从ICMP报文得到路由器名字和IP地址。那么什么时候停止发送数据报？当其中一个报文到达目的主机的时候，由于数据报包含了一个不可达的端口，所以目的主机会发送类型为3，编码为3的目的端口不可达的ICMP报文。
IGMP协议。网际组管理协议。用于多播。
ARP协议，地址解析协议。是算在链路层还是网络层？把IPv4地址转换成硬件地址。
RARP协议，反向地址解析协议。把硬件地址映射成IPv4地址。
路由器属于网络层设备，它只检查网络层字段。
IP地址。

MTU（最大传输单元），以太网的MTU是1500字节。IPV4要求最小MTU是68字节（20字节首部长度和40字节选项，以及8字节的偏移）。IPV6要求的最小MTU是1280字节。两个主机路径上的最小MTU称为路径MTU。路径MTU可以不对称。
当IP数据报的大小超过链路MTU时，执行分片。
最小重组缓冲区是IPV4(6)的任何实现都必须保证支持的最小数据报大小，IPV4是576字节，IPV6是1500字节。超过这个大小，就不一定能被接收方识别。所以，使用UDP的网络应用的报文段一般都不超过这个大小。
MSS（最大报文段）是用来通过对方，自己这面能够接收的最大TCP报文段大小，也就是最小重组缓冲区的实际值。MSS的大小通常设置为MTU减去IP和TCP首部的长度。

如果

数据链路层

成帧，透明传输，差错检测。
MAC地址。
交换机，网桥。
MAC地址。

物理层

集线器，中继器。

TCP“粘包”问题

粘包问题实际上不是TCP的，它是开发者在设计应用数据传输时的数据结构没有设计好好，可能两个不同的应用层数据在同一个TCP报文段中发给了接收方。
怎么解决，需要在传输层的数据流中给出边界，然后对传输层的数据流进行解析得到相应的数据。不应该依赖于socket的缓冲区作为数据报的边界。

参考文献

1.《计算机网络自顶向下》
2.https://segmentfault.com/a/1190000016855991
3.https://www.cnblogs.com/xflonga/p/9368993.html
4.https://www.cnblogs.com/aliwa/p/8495014.html
5.https://blog.csdn.net/qq_39816673/article/details/89611936
6.https://www.cnblogs.com/dadonggg/p/8778318.html
7.http://www.httpclient.cn/archives/106.html
8.https://www.cnblogs.com/lolau/p/8137541.html
9.为什么DNS使用UDP而不是TCP？ - 车小胖的回答 - 知乎
https://www.zhihu.com/question/310145373/answer/583869215

OS 常见面试题目

发表于 2020-02-29 | 更新于 2020-03-28 | 分类于操作系统

字节对齐

许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K的整数倍，这种对齐能够简化处理器和内存系统之间接口的硬件设计。
比如说一个处理器总是从内存中读取8个字节，那么地址就为8的倍数。
一般是K字节基本对象的地址必须是K的倍数。这就是为什么空类的大小是一个字节！！！因为空类中补充了一个char类型的数据，它不需要对齐！！！

中断和异常

异常和异常是控制流终中的突变，用来相应处理器状态中的某些变化。什么是控制流？控制指令执行的序列。
中断提供了一种方式，使处理器转而去做正常控制流之外的代码。

中断和异常通常被定义为改变处理器执行指令顺序的事件。
中断是异步的，通常是其他硬件（比如IO）设备依照CPU时钟信号随机产生的。
异常是同步的，指令执行时由CPU控制单元产生的，可能是除零。（异常）
Intel x86把同步和异步中断分别称为异常和中断。

用户态进入内核态

系统调用。
异常。
中断。

mutex和信号量，读写锁的区别[5]

mutex和信号量它们都可以用来实现同步操作，而信号量可以大于1，而mutex不能大于1。还有就是信号量可以由不同的进程释放，而mutex只能由获得锁的进程释放。
mutex和读写锁的区别，读写锁的并行性更高，而mutex要不就是加锁，要不就是不加锁。而读写锁可以是读锁，可以是写锁，还可以是不加锁。
自旋锁和mutex的区别，自旋锁在没有获取锁之前，是忙等状态，它只能被持有一小段时间，否则就会影响性能。自旋锁一般用在非抢占式内核中，它们会阻塞中断。
条件量可以和mutex结合使用。
屏障。
可以用mutex实现读写锁。。。具体的思路是，当有人读时，就要阻塞写锁，但是可以加写锁。有人写时，就要阻塞读锁。

动态链接和静态链接的区别

静态链接在编译的时候就把用到的目标模块复制到可执行文件中。
而动态链接在编译的时候，只是链接器复制了一些重定位和符号表信息，使得它们在运行时可以解析对动态链接库中代码和数据的引用。加载器加载程序时，会先加载动态链接器，然后动态链接器通过执行重定位和完成链接。

netstat

netstat监控网络连接，路由表等，网络接口等。
netstat默认打印所有打开的socket连接。
-a, --all展示所有的listening和没有listening的sockets。
-l, --listening，展示所有listening的socket，默认情况下是忽略的。
-p, --program，每一个socket属于哪一个程序和pid。
-n, --numeric，数值展示host，port和用户名。
-t, --tcp
-u, --udp
-r打印路由表。
-i打印网络接口。

lsof

列出打开的文件。

ip

ip address，查看ip地址。
ip link，查看网络设备。

原子操作

原子操作指的是由多步组成的操作，要么执行完所有步骤，要不一步也不执行。

程序和线程

程序是一个存储在硬盘上的可执行文件。
程序的执行实例被称为进程，它是操作系统对一个正在运行的程序的一个抽象。

进程和线程的区别

进程是资源分配和调度的最小单位，而线程是CPU调度的最小单位。引入线程后，系统并发性更高。
进程拥有独立的地址空间，若干代码段，数据段，文件，主存以及至少一个线程。
一个进程内的多个线程共享该进程的所有资源，线程自己拥有很少的资源，比如线程ID，寄存器，线程私有数据，线程栈。
进程调度需要上下文切换，开销大。
同一进程内的线程切换，仅交换线程拥有的一小部分资源，效率高。不同进程的线程切换会引发进程调度。
线程中通常要进行同步操作，当多个线程共享线相同的内存时，需要使用同步操作确保他们看到一致的视图。
进程之间交换信息要使用进程间通信。
一个进程结束后所有线程都将终止。
而一个线程结束通常不会影响其他线程（如果调用了exit就会终止所有线程。）

进程都有哪些资源

寄存器
堆
栈
数据段
代码段
文件描述符
锁
信号

进程都有哪些区域

可执行代码
初始化数据
未初始化数据
堆
栈

进程创建

怎么创建一个进程。调用fork复制进程的数据空间，代码段，堆和栈的副本。现在的fork利用写时复制，这些区域由父进程和子进程共享，内核将它们的访问权限修改为只读，如果父进程和子进程中的任何一个试图修改这些区域，内核只为修改的那篇区域（通常是一页）制作一个副本，原来的页仍是受到保护的，当其他进程试图写入时，内核会检查写进程是不是这个页的唯一属主，如果是，他把这个页标记为对这个进程是可写的。通过使用一个引用计数记录共享相应页的进程数目。

task_struct包含PID，mm_struct（页表），可执行文件的名字，程序计数器等。
调用fork函数时，内核为新进程创建一个各种各样的数据结构，并给他分配一个唯一的PID，为了给这个进程创建虚拟内存，它创建了当前进程的mm_struct，area_struct和页表的副本。他将两个进程中的每个页面都标记为只读，并将两个进程中的area_struct都标记为私有的copy on write。
当fork在新进程返回时，新进程的虚拟内存和调用fork之间进程的虚拟内存相同。当这两个进程中的任意一个进程写操作的时候，COW就会创建新页面。因此，也就为每个进程保持了私有地址空间。

fork和vfork区别，clone

fork采用copy-on-write[4]，而vfork在调用exec之前和父进程共享数据。
fork不对子进程的执行顺序做任何要求，而vfork要求子进程先运行，父进程挂起，知道子进程调用了exec或者exit之后，父进程恢复运行。
clone可以指定要复制的内容。

进程执行

进程，是一个程序的执行实例。
每个进程都由一个进程描述符表示，这个描述符包含有关进程当前状态的信息。当内核暂停一个进程的执行时，它在进程描述符中保存好几个寄存器的内容：

程序计数器和栈指针寄存器
通过寄存器
包含CPU状态信息的处理器控制寄存器
内存管理寄存器。

进程描述符用一个结构体task_struct表示。这个结构体中包含tty_struct，fs_struct，files_struct, mm_struct和signal_struct以及其他更多。

进程状态

进程描述符中的状态域描述了进程当前可能所处的状态，有五种：

运行状态
中断
不可中断
停止
僵死状态。

进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行，这种行为被称为进程切换。linux中进程切换的主要内容：

地址空间。（快表和页表）。
硬件上下文，寄存器，程序计数器。

进程结束

使用exit，使用return ，使用Exit，进程的最后一个线程调用pthread_exit。
调用abort，进程接收到某些信号，最后一个线程对cancel做出请求。

进程通信

独立进程访问同一个对象的方法。使用共享内存，然后使用信号量，记录锁，或者读写锁进行进行保护。
如何传递一个字符串？使用FIFO？

线程都有哪些资源

私有的：程序计数器，栈空间和寄存器。

线程创建

pthread_create。

线程结束

pthread_exit
cancel
从启动例程返回。

线程同步

互斥量
读写锁
条件变量
屏障

协程

一个进程

死锁

什么是死锁

两个或多个进（线）程在运行过程中相互请求其他进（线）程拥有且不释放的资源，造成所有的进程或者线程都无法继续前进。

产生死锁的原因

资源竞争。资源类型：可抢占资源，不可抢占资源。
加锁的顺序不合适。

产生死锁的必要条件

互斥条件：每个资源是不可共享的。
请求和保持：进程因请求某个资源而阻塞时，保持已经获得的资源不放。
不剥夺：进程获得的资源没有使用完前，不能被其他进程强行剥夺，只能由获得资源的进程自己释放。
循环等待：A等待B，B等待A。

解决死锁的方法

忽略死锁问题，假设系统永远不死锁。
保证系统永远不进入死锁状态。
- 死锁预防
- 死锁避免
允许系统进入死锁状态，并且可以从死锁恢复。
- 死锁检测
- 死锁恢复

忽略死锁

鸵鸟算法，假设死锁永不发生。死锁在计算机中很少出现，预防死锁的代码调高。

死锁预防（静态资源分配）

对应死锁产生的后三个必要条件。资源的互斥条件不能改变。

破坏请求和保持条件：资源一次性分配，只要有有一个资源得不到分配，就不给这个进程分资源。资源利用率低，但是容易实现。
破坏不可剥夺条件：超时放弃已有的锁。
破坏循环等待条件：对所有资源进行排序，以确定的顺序获得锁。

死锁避免（动态资源分配）

允许进程动态的申请资源，一次申请部分资源。系统在进行资源分配之前，先计算资源分配的安全性，如果此次分配不会导致系统进入不安全状态（可能死锁），就将资源分配给进程。
银行家算法。
n表示进程数据，m表示资源类型。
可用资源向量。
最大需求矩阵。
分配矩阵。
需求矩阵。
当一个进程申请资源时，首先判断它的请求是不是小于avaiable，如果小于，就需要等到。否则，假设将资源分配给这个进程，然后修改相应的数据结构。执行安全性算法。
安全性算法是：

死锁检测

系统进行资源分配后，计算资源的安全性，如果此次分配会导致死锁，就采取恢复措施，否则继续。

死锁恢复

剥夺资源使系统恢复。
撤销进程使得系统恢复。

页式内存管理

原理

页框和页面

页框也叫物理块。将物理存储空间划分成大小相等的若干块。大小为2的整数幂，在512字节到8192字节之间。
页面。将进程的逻辑地址空间划分成与物理块大小相同的若干片。
为进程分配内存时，以块为单位将进程的若干页分别装入多个可以不相邻的物理块中。

地址空间

假设进程使用的逻辑空间是线性的，逻辑地址空间的大小是0到2的m次方(m是地址空间的位数）。每个进程使用相同的逻辑空间。!!!注意，页式内存管理的逻辑地址空间和段页式内存管理的逻辑地址空间是不一样。
假设每个页面的大小是2的n次方。逻辑地址空间中的地址是addr，
页号§：addr / 2的n次方。（总共有2的m次方/2的n次方个页）
页内偏移(d)：add % 2的n次方。

页表

记录进程的逻辑页和主存中物理块的对应关系，实现从页号到物理块的地址映射。
进程地址空间中的每一页在页表中有一个条目（page table entry, PTE)，指出该逻辑在主存中的物理块号。
页表存放在主存中，页表的主存地址与页表的长度在PCB中。
控制寄存器用来存放：
- 页表基址寄存器：指向页表。
- 页表长度寄存器：页表长度。

地址转化

将页表的初始地址和页表长度送入控制寄存器。
比较PC上的页号是否大于控制寄存器中的页表长度。
将页号和控制寄存器中的页表起始地址相加，得到页号在页表中的位置。（就相当于一个数据，判断当前要访问的元素下标是否越界，不越界的话，取得地址）。

上述过程是通过硬件完成的。
获得页表在主存中的位置后，将该主存块号乘上页面大小加上PC上的偏移量，得到在主存中的物理地址。

快表和联想寄存器

在地址变换单元中设置的专用缓冲存储器。用来存放页表的一部分。快表的组成：
页号，块号，访问位，状态位。
在查询时，先使用快表进行查询，没有找到时，继续使用主存进行正常的地址变换，直到形成访问主存的绝对地址。
然后将相应的逻辑页号和物理块号，写入快表中状态为为0的一行中。如果没有这样的，就把它写入访问位为0的某一行，同时置状态位和访问位为1。

多级页表

如果一个进程可以访问32位大小的逻辑空间，页的大小为4KB（2的12次方）。那么一个页表需要包含2的32次方/2的12次方=2的20次方个表项，假设一个表项4B，那么需要4MB连续物理空间存储页表。
解决方法，再分页，即多级页表。

页式管理的主存分配

页表是每个进程一张。

段式内存管理

原理

为什么引入段式管理？

方便编程。
信息共享。
信息保护。
动态增长。
动态链接。

分段

按照程序自身的逻辑关系将地址空间划分成若干部分。每个段都有自己的名字。每个段都从0开始编制。

每个逻辑地址都分为段号和段内偏移。
段式存储分配以段为单位进行，为作业的每一个分段分配一个连续的主存空间，各段之间可以不连续。

段表

用于记录进程分段和物理存储空间的对应关系，实现从逻辑分段到物理内存的地址映射。
每个逻辑分段对应一个table entry，指出该逻辑分段在主存中的起始地址和段的长度。（注意页表中存放的是页号和块号）。
段表存放于主存。段表的主存起始和段表长度保存在进程控制块中。
控制寄存器。
- 段表基址寄存器：指向段表。
- 段表长度寄存器：段表长度。

段式管理的主存分配

存在外碎片。
分段方法：
首次适应法。
最佳适应法。
最坏适应法。

段式和页式管理的比较

段是信息的逻辑单位，它是根据用户需要进行划分的。
页是信息的物理单位，为了管理主存方便，对用户是透明的。
段的大小不固定，由它的功能确定的。
页的大小固定，由系统决定。
段式管理向用户提供的是二维地址空间。
而页式管理用户提供的是一维地址空间，确定其页号和页内偏移是由机器硬件实现的。
页式管理产生内碎片
段式管理产生外碎片。

页面置换算法

最佳算法。从主存中移除永远不再需要的页面，如果没有这样的页面，选择接下来最长时间不再使用的那个。（需要我们有未卜先知的能力）。
先进先出。总是替换最先进来的那个。
最近最少未使用。每次将当前访问的数据放在最前面，当发生未命中的时候，替换最近未使用的那个。
时钟算法（最近未用）。给每一帧附一个附加位。某一帧第一次被使用的时候，使用位设置为1，下一次如果扫描到它，而不是使用它的话，就把1置换成0。如果现在是0，要使用它，就把它置换为1。

进程调度算法

先来先服务（FCFS)。非抢占式的，易于实现，效率不高，性能不好，有利于长作业，但是不利于短作业。
短作业优先（SJF）。可以剥夺，也可以不剥夺。
每次从作业队列中挑选服务时间最短的作业进行处理。非抢占式的，有限照顾短作业，具有很好的性能，降低平均等待时间，提高吞吐量。但是不利于长作业，长作业出现饥饿状态。不能用于实时系统。
不剥夺的话，就是最短剩余时间优先。首先按照作业时间最短的作业运行，如果运行时有新的作业到达，并且它的服务时间比当前作业的剩余服务时间短，就发生抢占。抢占式的，因为频繁抢占和进程切换，系统开销大，算法实现代价高，一般用于实时系统。
高响应比。优先运行运行时间短，等待时间长的进程。非抢占式的，每次选择响应比最高的作业运行。可以避免饥饿。
优先级调度算法。可以剥夺，也可以非剥夺。为每个进程指定一个优先级。
时间片轮转法。用于分时系统的进程调度，采用剥夺方式。不利于IO频繁的作业。
多级队列调度算法。

window和linux都采用基于抢占的优先级调度算法。

IO数据传输的控制方式

程序查询方式。
程序中断方式。
直接存储器访问。
通道方式。

磁盘调度算法

先来先服务。容易实现，公平合理。但是完全不考虑队列中各个请求情况，使得磁头频繁移动。
最短寻道时间优先（SSTF）。在移动磁头时，总是选择移动磁头距离最小的磁道。可能会导致饥饿问题。
扫描法SCAN和循环扫描法CSCAN。
SCAN磁头不断的从一端移动到另一端，到头返回。（电梯算法）
CSCAN，从一端移动到另一端时，立即返回它开始的地方。
查询法LOOK和循环查询法C-LOOK。
SCAN和CSCAN都是将磁头从一端移动到另一端。
而LOOK和CLOOK是移动到最远的请求上的那个磁道，如果前进方向上没有请求，就反向移动。

参考文献

1.《APUE》第三版
2.https://stackoverflow.com/questions/200469/what-is-the-difference-between-a-process-and-a-thread
3.https://www.geeksforgeeks.org/difference-between-process-and-thread/
4.https://www.cnblogs.com/Rofael/archive/2013/04/13/3019153.html
5.https://blog.csdn.net/tt_love9527/article/details/82107549

C 常见面试题

发表于 2020-02-29 | 更新于 2020-04-23 | 分类于面试

什么是面向对象

在C语言中，数据和函数是分开来的，语言本身并不支持数据和函数之间的关联性，这种程序就称为程序性的。它们被一组算法驱动，处理共同的外部数据。
而C++将数据和函数封装起来，用户只能通过类设计者提供的接口访问类内封装的数据。
面对对象的三大特点：封装，继承和多态。
数据抽象和封装。类的基本思想是数据抽象和封装。数据抽象是一种依赖于接口和实现分离的编程技术。类的接口包括用户所能执行的操作，类的实现则包括类的数据成员，负责接口实现的函数以及定义类所需要的各种私有函数。封装实现了类的接口和实现的分离，封装后的类隐藏了它的实现细节，类的用户只能使用接口而无法访问实现部分。
继承的三种方式：public，private和protected继承。
多态，多态分为动态多态和静态多态。静态多态是通过模板实现的，动态多态是通过虚函数和RTTI实现的。
动态绑定和静态绑定。

指针和引用的区别

1 从定义上来说，可以定义指针的指针，但是不能（直接）定义引用的引用（模板参数推导的时候可以）。定义。
2 const引用可以指向字面值常量，而指针不能（除了字符数组）。
3 指针本身可以是const的，而引用不能。底层const和顶层const。
指针可以为空，引用不能。初始化。
指针可以被重新赋值。而引用一旦被绑定就不能修改。赋值。
指针必须被解引用才能使用，而引用不需要。访问。
指针变量可以进行运算，而引用不能。运算。
指针本身是一个变量，有它自己的内存地址，以及在栈上的大小。而引用的内存地址和它绑定的对象一样，看起来是一样的，但是实际上是不一样的（编译器做了一些操作），可以把引用当做它引用对象的别名。

inline[10,11]

inline函数对于封装提供了一种必要的支持，可以有效的存取封装于class中的nonpulibc数据。避免函数调用的开销，比如说参数入栈，出栈。
它是C程序中宏函数的一个安全替代品。宏函数是由预处理器对宏进行替换，而内联函数是通过编译器控制的。内联函数是函数，会进行参数检查。只不过在调用的时候像宏一样展开，减少函数调用。
如果一个inline函数被调用太多次的话，会产生太多的扩展代码，使得程序变得的道别大。
inline函数有多个局部变量或者参数带有副作用，都会产生临时性对象。
inline中调用inline可能会使得复杂度太大，而没有办法内联。
用inline声明的函数并不一定会inline，取决于编译器。编译器通过计算各种操作的复杂度，计算是否需要内联。
inline只适合函数体代码简单的函数使用，不能有循环等语句。适用于规模小，流程直接，频繁调用。
建议inline函数的定义放在头文件中。
类内定义的函数是隐式的inline函数。
inline关键字应该和实现放在一块，只在声明中说明没有用。
慎用内联。

static关键字[4]

隐藏全局变量和函数的作用域。这一个已经被标准抛弃了。
修饰局部变量，改变变量的生命周期。
修饰类的数据成员和成员函数。

const关键字

顶层const和底层const。主要是常量指针和常量引用。
const修饰形参和const修饰返回值。
和类相关。
修饰成员变量，必须使用初始化列表赋值。
const修饰成员函数。
修饰类对象，必须调用const类型的函数。
const可以用来区分重载。

C语言结构体中的空数组[20]

声明一个不占用空间的指针，redis的sds就用到了这种方法。

include ""和`<>`区别

它们的查找路径不同，<>先查找系统目录，"“先查找当前目录。
”"查找到的会隐藏<>查找到的。

const和宏常量的区别

const常量有数据类型，而宏常量没有。编译器可以对前者进行安全检查，对后者只能进行字符替换。

内存泄露

忘记delete
array delete
虚析构函数
指针数组，没有对每个指针进行释放。

指针函数和函数指针

指针函数是一个函数，返回类型是一个指针而已。
函数指针是一个指针，是一个指向函数的指针。

数组和指针

数组是一块连续存放的空间，指针是一个地址，指针变量是一个变量。
初始化。
大小。
指针数组和数组指针。
作为函数参数。

vector扩容

为什么不是常数

成倍增长可以保持常数时间复杂度的插入操作。
常数增长的插入时间复杂度是O(n)。
为什么？假设要插入n个元素，成倍增长的倍数是p，常数增长的大小是q。
成倍增长总共的复制开销：
$$ \sum_{i=1}^{log_p^n } p^i $$
常数增长总共的复制开销：
$$\sum_{i=1}^{n/q} qi $$

为什么是1.5或者2

为什么是1.5？可以复用之间的空间。
为什么是2？实现简单。

strlen和sizeof的区别

sizeof是运算符。它的值在编译时就已经确定了，所以不能用来获得动态分配的内存空间的大小。
strlen是函数，在运行时计算的。
静态数组传递给strlen就会退化成指针，在传递给sizeof的时候还是数组。strlen是数组中内容的长度，而sizeof是静态数组声明时的大小。
动态数组(malloc)分配的，strlen能获得数组中内容的大小，而sizeof只能获得指针的大小。
strlen不会计算空字符，而sizeof会。

override和overload

只有虚函数能被ovrride。
override是用来实现多态的，函数的参数类型和声明和可以父类中完全一样。
而overload中，函数的参数列表必须不同。它的作用我觉得可能是方便记忆，方便理解。实现同一个功能的函数具有同样的名字。

空类的大小为1字节

标准规定空类的大小为1，因为两个不同的对象需要不同的地址表示。标准规定完整对象的大小大于0。

虚函数和虚函数表[12]

当某个类中声明了虚函数时，编译器会为该类创建一个虚函数表，存放虚函数的地址，这个是在编译时期完成的。然后编译器会在该类的对象中添加一个虚指针指向这样一个虚函数表。
当有其他类继承这个类时，编译器为这个类也创建一个虚函数表。如果派生类重写了基类的虚函数，那么编译器会更新虚函数表中的函数地址为派生类的虚函数地址。
当发生虚函数调用时，编译器会根据指针指向的对象，找到该对象的虚函数表，然后调用相应的虚函数。

虚析构函数

一个基类总是需要虚析构函数。

虚继承

为什么要有虚继承？
派生类可能多次继承同一个类。默认情况下，派生类会含有继承链上每个类对应的子部分，如果某个类在派生过程中出现了多次，派生类中将包含该类的多个子对象。比如iostream之类的类，肯定不行。
声明成虚继承的继承体系中，无论虚基类在继承体系中出现了多少次，派生类中都只含有一个共享的虚基类子对象。

多态

C++的多态分为两种，一种是静态多态，通过函数重载和模板实现。
一种是动态多态，虚函数实现。

C实现C++的多态[5,6, 29]。

RTTI[13]

C++ 缺乏安全的向下转型（将派生类指针转换成基类指针），只有类型真的可以被转型的时候，才会执行向下转型。

RTTI提供了一个安全的向下转型，但是只对那些多态类型有效（使用继承和动态绑定）。为什么？因为那些ADT和非多态类型不需要这些东西，所以，很自然的就想到，在虚函数表上进行操作，通过在虚函数表中增加一个slot（通常是第一个slot），它是通过编译器在编译器指定的，和虚函数一起。

dynamic_cast可以用来实现向下转型，，如果向下转型是安全的，就可以执行，而如果是不安全的，就返回0。
dynamic_cast可以在执行期决定真正的类型。代价是什么呢，一个就是编译时在虚函数表中增加的一项，另一个就是运行期间，获取type_info对象的地址，这个地址和指向对象的类型有关，然后获得它的类型。
对于引用和指针的异常处理不同：
对于指针，如果返回0，表示这个指针是空指针。
对于引用，如果引用不是一种真的派生类，就会抛出bad_cast异常。

type_info对象对于内置类型和非多态的类型也适用。不过这种type_info对象是编译器取得的（在需要的时候），而不是运行期。

`cast`

`static_cast`

和C中提供的强制类型转换一样。

`const_cast`

只能改变运算对象的底层const，可能去掉也可以添加底层const。

`reinterprect_cast`

为运算对象的bit mode提供新的解释。比如可以把一个整数解释成字符串。

`dynamic_cast`

dynamic_cast实现安全的动态转换。
它可以可以安全实现的执行downcast，但是需要是含有虚函数的类。

智能指针

shared_ptr实现

引用计数放在指针成员中。

template<typename T>
class shared_ptr
{

public:
    shared_ptr():pd(nullptr)
    { }

    shared_ptr(T *data): pd(data), new size_t(1)
    { } 

    // 拷贝构造函数
    explicit shared_ptr(const shared_ptr<T> &rhs)
    {
        pd = rhs.pd; 
        count = rhs.count;

        ++*rhs.count;
    }

    shared_ptr<T>& operator=(const shared_ptr<T> &rhs)
    {
        if(count && --*count == 0)
        {
            delete pd;
            delete count;
        }

        pd = rhs.pd;
        count = rhs.count;
        if(rhs.count)
            ++*count;

        return *this;
    }

    ~shared_ptr()
    {
        if(count && --*count == 0)
        {
            delete pd; 
            delete count;
        }
        
    }

    T& operator*() 
    {
        return *p;
    }
    T& operator*() const 
    {
        return *p;
    }

private:

    T *pd;
    size_t *count;

};

unique_ptr实现

template<typename T>
class unique_ptr
{
public:
    unique_ptr():p(nullptr)
    { }
    // 构造函数
    explicit unique_ptr(T *data): p(data)
    { }

    //拷贝构造
    unique_ptr(const unique_ptr&) = delete;

    //拷贝赋值
    unique_ptr& operator=(const unique_ptr &rhs) = delete;

    //析构
    ~unique_ptr()
    {
        if(p)
            delete p;
    }

    T* release()
    {
        T *q = p;

        p = nullptr;
        return q; 
    }

    T* reset(T *data)
    {
        if(p)
            delete p;
        p = data;
    }

    T& operator*() {return *p;}
    //指针本身是个常量
    // const 修饰this指针，常量指针，指向不能改变，指针指向的值可以改变。为什么这里返回值不是常量。这个指针可不可以指向常量对象，可以。
    T& operator*() const {return *p};

private:
    T *p;

};

shared_ptr和unique_ptr

它们管理保存指针的策略，前者可以共享指针，而后者则独占指针。
它们允许用户重载deleter的方式。只要在创建或者reset指针时给shared_ptr提供一个deleter即可。但是，deleter是unique_ptr对象的一部分。
shared_ptr的deleter是运行时绑定，所以需要使用指针，开销大，但是用户重载更方便。它的执行方式可能如下：del?del(p): delete p。
而unique_ptr的deleter是编译时绑定，避免了间接调用deleter的运行时开销。
shared_ptr不能动态管理数组，而unique_ptr可以动态管理数组。

智能指针和数组

shared_ptr不支持管理动态数组。需要提供自定义的delete（只要是一个可调用对象就行）。
unique_ptr支持动态管理数组，需要在类型后面加上一对方括号。当unique_ptr销毁时，会自动使用delete[]。不能使用成员访问运算符（点和箭头），但是可以使用下标访问运算符。

weak_ptr

weak_ptr可以解决循环引用问题，比如双向链表中的循环引用。[9]

类模板和函数模板的区别

类模板用来生成类，函数模板的参数是由编译器推导的，而类模板的参数必须指定。

模板特化和偏特化

模板特化的本质是模板实例化，定义特化版本时，我们实际上是接替了编译器的工作。
函数模板只能全特化。
类模板可以全特化也可以偏特化。偏特化既有类型的偏特化，也有个数的偏特化。

为什么模板的声明和实现要写在一起而类的实现和声明要分开[7]

C++ 采用分离式编译。可以不用将所有的代码写在一个文件中，可以将他们分解为更小，更好管理的模块，可以独立的修改和编译这些模板。当我们改变这些模板时，只需要重新的编译它，并重新链接，不必重新编译其他文件。这一功能主要是通过链接器实现的。更多的内容可以查看CSAPP上介绍的。
对于普通对象和函数而言，类的声明写在头文件中，实现写在cpp文件中。cpp文件是可以单独被编译的。
但是模板函数的声明并不能直接被直接编译成二进制代码，在遇到template时编译器不会为它分配任何空间。因为只有在真正使用模板的时候，才会知道模板参数的值。编译器和链接器的某一个部分，可以去掉模板的多重定义。

哈希表

哈希表冲突严重的话会退化成单链表。这个时候哈希表的各种操作的时间复杂度都提升了一个量级，会占用大量CPU时间，降低系统响应时间，可以用来做DDos攻击。
解决冲突的方法：

内存管理

new

new一个空数组是和合法的，但是不能解引用！！！可以把它当做尾后迭代器来使用。

malloc, calloc和realloc

malloc分配指定字节的数组，初值不定。
calloc分配nobj个size字节的对象，每一位都初始化为0。
realloc在以前分配的区域的基础上扩大为新的容量。如果原来的区域后面有足够大的空间，就在那里，否则复制到一个新的空间中。

placement new

重载operator new函数。placement new可以为分配函数提供额外的信息。
Placement new允许我们将对象构造在已经分配好的内存上，分配好的内存不一定是operator new分配的内存，甚至可以是静态内存。
allocator的内存分配和构造函数的调用是分开进行的，通过两个函数allocate和construct。
对应于new，可以使用operator new进行空间分配，使用placement new调用构造函数。

stl allocator

管理的是malloc分配的虚拟内存，比如STL的alloc分配器。
大于128B的，直接malloc。
小于等于128B的，维护16个链表，每个都是8的倍数。

用户空间内存分配[22]

malloc实现[21]

管理的是虚拟内存。
除了mmap外的几种方式，一般分配大内存的话都是mmap，小内存的话都是通过bin实现的。

mmap

ptmalloc实现

tcmalloc实现

jemalloc实现

内核空间内存分配[22]

伙伴算法用于大块连续物理内存的分配。
slab和kmalloc用于小块连续物理内存的分配。
vmalloc用于连续虚拟内存的分配。
注意，这三种方法都是内核空间的内存分配。

伙伴算法[24]

什么是伙伴算法

伙伴算法，把所有的空闲页框分成11个链表，每个链表分别管理2的0到10次方大小的连续页框。伙伴算法只能分配2的幂次页的空间。通常一个页框是4K大小，所以伙伴算法维持的最大连续内存4M大小，最小是4K大小。

伙伴的回收

什么是伙伴，由同一个块分裂开来的两个块。所有大小为2的k的块，它的地址一定是2^k次方的整数倍。将它的地址除以2的k+1次方，然后再加减2的k次方，就可以得到它的伙伴的地址。
比如大小为16的块，可能是0-16，16-32，32-48，48-64。它们的地址都是16的倍数，0-16和16-32互为伙伴，而32-48和48-64互为伙伴。但是16-32和32-48不是伙伴！！！因为它们不是从同一个块分裂来的。。。。

优点和缺点[25]

优点

解决了外部碎片问题。
解决了连续页框的分配问题。
针对于大内存。

缺点：

合并的要求太严格了。
内碎片问题。
合并和拆分的开销，如果刚合并又要拆分等等。

slab[26]

slab机制通常由三类对象构成：kmem_cache，slab和slab对象构成。[27]
一个kmem_cache通常有1个或者多个slab，一个slab通常是1个或者多个连续物理页，然后它被分成多个slab对象。这个cache管理的就是相应大小的slab对象。

kmalloc实现[23]

分配的是小的连续的物理内存，基于slab实现的。
slab又是基于伙伴系统的。

vmalloc实现

分配的是连续的虚拟内存，物理内存不一定连续。

对齐

gcc 默认对齐是4字节对齐。在结构体中要注意。
malloc是16字节对齐。

cmake, make和makefile

cmake根据CMakeLists.txt生成makefile，make执行makefile。
makefile是文件，包含了怎么样进行编译和链接。makefile可以手动写，但是它不跨平台（即不同平台的makefile不同），而且工程大很麻烦。
CMakeLists.txt是我们自己写的。cmake指向CMakeLists.txt所在的目录，cmake可以根据CMakeList.txt跨平台自动生成makefile。
make用来执行makefile，调用makefile中用户指定的命令进行编译和链接。

void *

可以接收任意类型的赋值，无需强制类型转换。
经过类型转换可以赋值给任意类型的变量。

lambda表达式

为什么要有lambda表达式？

总共有四种可调用对象，函数，函数指针，重载了函数运算符的类和lambda表达式。
lambda表达式的声明。
auto f = [local variable](int x){return a;};
对于那种只在一两个地方使用的简单操作，lambda表达式是有用的。当在多个地方使用的话，通过应该使用一个函数，或者需要很多语句的话，也是函数比较好。
capture list中引用和值的作用。
可以和STL中的算法进行交互。

lambda的底层实现

面向对象的几大原则

单一职责原则。解耦，增强内聚，即高内聚低耦合。
开放封闭原则。对扩展开放，对修改关闭。
里氏替换原则。子类可以替换父类。
依赖倒置原则。依赖于抽象而不是依赖细节。
接口分离原则。不需要让客户程序依赖它们不需要的方法。一个接口应该只提供一种对外的功能。
合成复用原则。
迪米特原则。

设计模式

单例模式
reactor模式。是事件驱动模式，它由一个或者多个并发输入源，有一个service handler和多个request handler。这个service handler会同步的将输入多路复用给相应的request handler。
比如说redis的

数据结构相关

堆

二叉堆是完全二叉树，一般可以用数组实现。最大堆就是每个根节点的值大于其子节点的值，最小堆就是每个根节点的值小于其子节点的值。

SGI STL heap相关的算法

push_heap，将新的节点插在最后一个位置。
pop_heap，弹出最大堆的堆顶元素。（或者就是heapify）
sort_heap，就是排序。
make_heap，创建一个最大堆。

优先队列

底层实现是二叉堆，总是弹出key最大的元素。

哈希和哈希表

什么是哈希

哈希：把任意长度的输入，变成固定长度的输出，这个映射的规则就是对应的哈希算法，原始数据映射后的输出叫做哈希值。哈希值存在的目的是加速key-value的查找速度。
哈希常见的几种实现方式：顺序，链式，散列，索引。哈希表是其中的一种。
注意把哈希和哈希表区分开来。

碰撞（冲突）

什么是碰撞？输入不同的数据得到相同的输出，哈希一定会发生碰撞。

hash

好的hash要求

抗碰撞。不同的输入得到相同输出的概率要小。
抗篡改。输入数据的小的变化会得到完全不同的值，输入相同的数据会得到相同的值。（雪崩效应）。
速度要好。哈希算法的效率要高
根据输出不能反推输入。

hash的应用

保存密码，保存用户密码的哈希值。（这也是很多地方只能重置密码的原因，因为它们也不知道你的密码。。。）
数据校验。
负载均衡。在服务器扩容时，使用一致性哈希。

hashtable

哈希表是用哈希算法实现的表，提供了对任何有名字项的存取和删除操作，也可以查看是一种字典，提供常数时间的读写操作。
哈希表的扩容(rehash)，元素个数比bucket个数多，再打散，把bucket个数增加两倍（接近两倍的质数）。

hashtable碰撞的解决方法

负载系数：元素个数除以表格大小，除了开链法，都要在0,1之间。
线性探测：插入的时候，找到一个不可用的位置（被其他值占了），继续找下下一个位置，直到找到一个空位置。查找的时候，如果找到一个和当前搜索的目标不同的值，就继续往下找。删除的话，采用惰性删除，只删除记号，实际操作等到rehash时再进行。
最坏情况下，哈希表退化成链表。
二次探测：发生冲突是，而是使用H+n^2的平方寻找可用的位置。

对于二次探测，假设表格大小为质数，负载因子为0.5，保持负载因子在0.5以下，超过0.5就rehash，可以保证插入每一个元素的探测次数不多于2。
二次探测本身所需的计算量其实和一次探测差不多。
rehash的时候，必须重新计算表中的每一个元素。

开链(seperate chaining)：在每一个表格中维护一个链表。表格的负载系数会大于1。

hashtable的桶

SGI使用开链法，表格（桶的集合）使用vector（为了动态扩容），而链表使用自定义的结构体。

SGI使用bkt_num()获得每个元素应该存放在哪个bucket中，这个函数负责调用hash function取得一个可以执行取模运算的值。为什么不直接使用hash_function，因为有些元素类型无法直接拿来对hashtable的大小进行模运算，这时候需要做一些转换。
开链法没有要求表格的大小为质数，但是SGI依然这么做了，并且准备了28个质数的表，并且提供一个函数去获取最接近并大于某个数的质数。
在创建一个hashtable对象时，首先要进行实例化，指明hashtable的各个模板参数，然后提供参数给构造函数（没有默认构造函数数）。其中有一个参数大小为n，表明要创建的hashtable的桶的个数（它会自动寻找一个接近n的质数）。
插入元素的时候，每插入一个就会判断是否需要resize。这个是一个很常用的操作，插入操作，首先判断需不要扩容，比如vector等。
扩容的原则：元素数量大于bucket的数量就resize。
复制和删除，删除的时候需要对bucket中每一个链表都删除。而复制的时候需要先把原有的给删除掉，然后保留和复制对象至少一样的空间。
hashtable的示例，在新版本的STL中，不能直接使用hashtable，unordered_set和unordered_map都是对hashtable的封装，调用构造函数时传入一个n是桶的数量，这个n必须指定（STL会自动改成比n大的最小质数）。

hash函数

STL定义了很多仿函数，都是模板。hash也是一个仿函数，返回size_t类型。对于char, int,等类型，通常就返回原值，而对字符串和string等设计了相应的转换函数，对于浮点数，怎么办，没有说，STL源码剖析的版本没有实现，但是cppreference上说有，应该是新增加的。

其他

unordered类容器和非ordered类容器最大的区别就是一个是默认有序，一个是默认无序。

树

二叉搜索树：任何节点的键值一定大于它的左子树中的所有节点，小于右子树中每一个节点的键值。
关联式容器的内部结构是平衡二叉树，平衡二叉树有AVL树，红黑树，AA树等。平衡的大概意思就是没有一个节点过深。

AVL树

确保整颗树的深度是logn，任何节点的左右子树高度最多相差1。
AVL利用单旋和双旋，可以将所有不平衡的情况转换为平衡的情况。
对于深度最深的节点X，造成节点X不平衡只有四种情况：
插入点在X的左子节点的左子树。
插入点在X的左子节点的右子树。
插入点在X的右子节点的左子树。
插入点在X的右子节点的右子树。
双旋第一步做完，第二步就是单旋了。

红黑树[17]

红黑树需要满足以下规则：

所有节点非红即黑。
根节点为黑色。
如果节点为红，子节点必须为黑。
任一节点到叶子节点的任何路径，所包含的黑色节点必须相同。

为什么有了AVL还要有红黑树。AVL的条件太苛刻了，基本上每次插入和删除都需要重新调整。这样子在插入和删除比较频繁的情况下代价太大了。就提出了AVL树，查找的时间复杂度也是logn的，但是它的平衡条件要比AVL树宽松一些，插入和删除时也不会像AVL那样频繁破坏规则。
查找的代价：最长路径长度不超过最短路径长度的2倍。
插入代价：插入节点最多只需要两次操作，和AVL一样，变色的时间复杂度是O(logN)。
删除代价：删除一个节点最多只需要旋转3次，但是变色操作的时间复杂度在O(logN)。

插入有四种情况：

父节点为黑色，直接插入一个红色节点就好了。
父节点为红色，这个时候，取决于叔节点的颜色。
- 叔节点为红色，这个时候还取决祖父节点的父节点的颜色。如果那个节点是黑，把新增加的节点和父节点（叔节点）交换一下就好了。如果那个节点是红色，还需要更改祖父节点的颜色。
- 叔节点为黑色，
- 叔节点为黑色，

一个有n个节点的红黑树的高度至多为2log(n+1)。

B树[18]

B树是对二叉树的推广，B树一般有一个阶数m，m阶代表每个树节点最多有m个查找路径，其实就是有多少个分叉，有m个分叉，最多就能存储m-1个数据。m=2时，就是二叉树，二叉树每个节点能分两叉，只能存1个数据。

如果根节点不是叶子节点，必须有两个叶节点，一个数据，也就是两个分叉。
每个非叶子节点的子节点数大于等于m/2的上界，小于m；每个节点的关键字个数必须大于m/2-1（这里除法是有小数的）的上界小于m-1，就是对应的分叉数-1。
所有的叶子节点都位于同一层，不包含关键字信息。

B+树[18]

B+树和B树的区别：

每个节点有n个子节点，n个关键字，而B树n个子节点有n-1个关键字。
还有就是根节点和叶子节点关键字和子节点的个数范围。
叶子节点包含全部关键字，所有非叶子节点都只起到了索引的作用。非叶子节点上有关键字，但是只用来索引，没有对应记录的存储地址。
非叶子节点中出现的关键字是会重复出现在叶子节点中的。

B+树的好处，扫库的时候直接顺序查找就好了，而B树需要中序遍历。B+树还支持区间查询，而B树不支持。
通常在B+树中有两个头指针，一个指向根节点，一个指向关键字最小的叶节点。所以支持顺序查找，也支持多路查找。

gcc和gdb[14]

gcc 常用选项：
-O编译器优化，Og最低等级的优化，On，数字越大优化等级越高。
-Wall发出所有警告
-g产生调试信息
-o指定输出文件。
-E只进行预处理
-S编译，就是产生汇编代码
-c之汇编，不链接，就是产生目标代码
-static禁止使用动态链接库，只链接静态库，编译后可独立执行，不需要动态库，但是得到的可执行目标文件比较大。
-L dir在库文件的搜索列表添加dir目录
-I dir在头文件的搜索列表添加dir目录
-shared

使用gdb调试时，需要使用使用gcc -g选项添加调试信息。

gdb program，
gdb program core，用gdb查看core dump文件
gdb program pid，用gdb查看已经开始运行的进程。

使用quit或者q退出。

gdb调试选项
help
run，开始调试程序
break，设置断点。
info break，查看断点信息。
watch，为一个表达式设置一个检视点，可以加上-l选项，当监视的变量改变时，就会自动打印。
catch,
list，打印源码展示出指定的函数或者行。
print，打印出表达式的值。
display，每次程序停止的时候打印出
bt，显示程序的调用栈信息。
framen，简要查看第n帧的信息。
info frame，详细查看当前帧的信息
info registers，查看寄存器
info args，查看当前帧的参数。
info locals，查看当前帧中的局部变量。
continue
step

移动(move)语义和右值引用[16]

移动语义，是为了避免无用的复制开销。右值引用的出现，让移动语义变得可能。将指针指向的内存直接拿过来使用。
Move semantics is a new way of moving resources around in an optimal way by avoiding unnecessary copies of temporary objects, based on rvalue references. In my opinion, the best way to understand what move semantics is about is to build a wrapper class around a dynamic resource (i.e. a dynamically allocated pointer) and keep track of it as it moves in and out functions. Keep in mind however that move semantics does not apply only to classes!