- 1. 计算机网络
- 2. 操作系统
- 2-12. 线程与进程
- 2-13. 文件读写基本流程
- 3. C/C++ 问题
- 4. 数据库相关
- 4-5. Innodb的锁机制
- 4-6. 其他锁机制
- 5. Java问题
- 6. 算法问题
- 十大排序算法">6-1. 十大排序算法
- KMP算法 - 字符串匹配">6-2. KMP算法 - 字符串匹配
- 五大常用算法——分治法，动态规划，回溯法，分支界限法，贪心算法">6-3. 五大常用算法——分治法，动态规划，回溯法，分支界限法，贪心算法
- 红黑树">6-4. 红黑树
- 双重数组实现vector">6-5. 双重数组实现vector
- 五种路径算法">6-6. 五种路径算法
- 6-6. 海量数据处理
- 6-7. 二叉树相关
1. 计算机网络
1-1. TCP三次握手
最开始客户端和服务器都是处于CLOSED状态的，其中客户端是主动打开连接，服务端被动打开连接。
第一次握手
客户端主动发送请求连接服务器，设定同步序列编号SYN为J，进入SYN_SEND状态，等待回复。
第二次握手
服务器在收到SYN请求包后，会发送一个SYN以及一个ACK给客户端，进入SYN_RECV状态。其中ACK的序列号是 J+1表示是给SYN J请求包的应答，新发送的SYN请求包的序列号是K。
第三次握手
客户端在收到新SYN K+ACK J+1 后，也回应ACK K+1 以表示收到了，此包传输完成后，两端都进入ESTABLISH状态，完成三次握手，建立连接，可以开始通行了。
1-2. TCP连接中的SYN洪泛攻击
在第二次握手阶段结束后，服务器发送SYN-ACK包，等待客户端的ACK时，服务器处于SYN-RECV状态，此时TCP连接称为半连接half-open connect。
客户端在短时间内伪造大量不存在的IP地址，不断向服务器发送SYN请求包，使得服务器一直处于半连接状态，并需要资源对不存在的IP地址重发请求导致正常的SYN请求因队列满而被丢弃，从而引发网络堵塞甚至系统瘫痪，这就是SYN攻击。
可以通过降低服务器SYN timeout时间或配置外部防火墙等来防御SYN攻击。
1-3. TCP连接中的四次挥手
中断连接端可以是Client端，也可以是Server端。
以客户端发起中断请求FIN报文为例，服务器接收FIN报文后发送ACK。这两次挥手后意味着客户端不再发送数据给服务器了。此时客户端进入FIN_WAIT状态。
等待服务器将所需数据发送完后，向客户端发送FIN报文，客户端收到后返回ACK报文给服务器，而服务器收到ACK后则断开连接。但如果服务器没有收到ACK意味着报文可能丢失，需要重发报文，因此客户端在发送ACK后需要等待2个MSL最大报文段生存时间后再断开连接。
为了保证客户端发送的最后一个ACK报文段能到达服务端，如果没收到的话服务端会在超时后将重发第三次握手的FIN包，并且初始化计时器2MSL。还有就是防止之前失效的连接分组再次出现，而2MSL的时间足够让他消失。
1-4. TCP连接中需要三次握手四次挥手的原因
为什么不是两次握手：
（1）防止已经失效的连接建立请求突然又传送到服务端了，导致错误。
假设A第一个给B发送建立连接请求，因为传送过程中在某个网络节点停留了很久，由于A迟迟没有收到B的确认报文，误以为请求丢失，于是重新向B发送请求。当A和B完成数据传送准备关闭连接时先前停留的请求报文到达了B，此时B会再次建立连接导致资源浪费。有第三次握手的情况下即使第一次迟到的报文不幸被B接受到了，A也不会发送确认报文，连接不会打开。
（2）假设第二次握手之后没有第三次握手，则服务端会在发送确认报文（第二次握手）后，开始发送数据，如果确认报文在客户端接收之前丢失，客户端没有收到，便不知道服务端建立了什么样的序列号，则客户端不会处理服务端发送过来的数据一直等待确认报文，而服务端发送的数据超时后会继续重传相同的数据造成死锁。
因为三次握手中的第二次时，服务器可以同时发送确认的ACK报文和用于同步的SYN报文。
而四次挥手时接收方不能确定自己的结束时间，所以只能先发送ACK报文，等待数据发送结束后，再结束自己的连接。
1-5. TCP/IP协议的四个层次
1-6. OSI（open system interconnect）模型
应用层：网络服务与最终用户的一个接口。
协议有：HTTP FTP TFTP SMTP SNMP DNS TELNET HTTPS POP3 DHCP
表示层：数据的表示、安全、压缩。（在五层模型里面已经合并到了应用层）
格式有，JPEG、ASCll、EBCDIC、加密格式等 [2]
会话层：建立、管理、终止会话。（在五层模型里面已经合并到了应用层）
对应主机进程，指本地主机与远程主机正在进行的会话
传输层：定义传输数据的协议端口号，以及流控和差错校验。
协议有：TCP UDP，数据包一旦离开网卡即进入网络传输层
网络层：进行逻辑地址寻址，实现不同网络之间的路径选择。
协议有：ICMP IGMP IP（IPV4 IPV6）
数据链路层：建立逻辑连接、进行硬件地址寻址、差错校验 [3] 等功能。（由底层网络定义协议）
将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
物理层：建立、维护、断开物理连接。（由底层网络定义协议）
1-7. 简述从输入网址到浏览器显示的过程
一，浏览器查找解析域名IP地址
① 在浏览器中输入网址域名，操作系统会先检查自己本地的hosts文件是否有这个网址映射关系，如果有，就先调用这个IP地址映射，完成域名解析。经常浏览的网页在开发者模式下可以看到部分资源缓存在内存中（memory cache），打开新的网站就会看见全是http请求，没有缓存。
② 如果hosts里没有这个域名的映射，则查找本地DNS解析器缓存，是否有这个网址映射关系，如果有，直接返回，完成域名解析。本地DNS服务器一般由网络接入服务器商提供，比如中国电信，中国移动。
③如果hosts与本地DNS解析器缓存都没有相应的网址映射关系，首先会找TCP/IP参数中设置的首选DNS服务器，在此我们叫它本地DNS服务器，此服务器收到查询时，如果要查询的域名，包含在本地配置区域资源中，则返回解析结果给客户机，完成域名解析，如果没有，本地DNS服务器还要向DNS根服务器进行查询。
④本地DNS就把请求发至 “根DNS服务器”，根DNS服务器没有记录具体的域名和IP地址的对应关系，而是收到请求后判断这个域名(.com)是谁来授权管理的，告诉本地DNS服务器，你可以到相应的域服务器上去继续查询，并给出域服务器的地址。
⑤本地DNS服务器继续向域服务器发出请求，请求的对象是 .com 域服务器 。 .com域服务器收到请求之后，如果自己无法解析，它就会找一个管理.com域的下一级DNS服务器地址(baidu.com)给本地DNS服务器。
⑥最后，本地DNS服务器向域名的解析服务器发出请求，这时就能收到一个域名和IP地址对应关系，本地DNS服务器不仅要把IP地址返回给用户电脑，还要把这个对应关系保存在缓存中，以备下次别的用户查询时，方便下次访问时直接返回结果，加快网络访问。
注：若网站和用户之间加入过CDN，DNS经过本地域名解析后将最终域名解析权交给CDN专用的DNS服务器，然后CDN的DNS服务器将CDN的全局负载均衡设备IP地址返回用户，用户向其发起URL访问，CDN全局负载均衡设备根据用户IP地址，以及用户请求的内容URL，选择一台用户所属区域的区域负载均衡设备，告诉用户向这台设备发起请求。服务商能使用Web Cache技术在本地缓存用户访问过的Web页面和对象，利用全局负载技术将用户的访问指向距离最近的工作正常的缓存服务器上，由缓存服务器直接响应用户请求（但是一般问输入url的过程不是指这个）。
二，TCP连接
在拿到域名对应的IP地址后，会以随机端口（1024~~65535）向WEB服务器程序80端口发起TCP的连接请求，这个连接请求进入到内核的TCP/IP协议栈（用于识别该连接请求，解封包，一层一层的剥开），还有可能要经过Netfilter防火墙（属于内核的模块）的过滤，最终到达WEB程序，经过三次握手，最终建立了TCP/IP的连接。
三，发送HTTP请求
建立起安全的加密信道后，浏览器开始发送 HTTP 请求，一个HTTP请求报文由请求行（request line）、请求头部（headers）、空行（blank line）和请求数据（request body）4个部分组成。
四、服务器端处理
服务器端收到请求后的由web服务器（准确说应该是http服务器）处理请求，诸如Apache、Ngnix、IIS等。web服务器解析用户请求，知道了需要调度哪些资源文件，再通过相应的这些资源文件处理用户请求和参数，并调用数据库信息，最后将结果通过web服务器返回给浏览器客户端。完成一次 HTTP 请求后，服务器并不是马上断开与客户端的连接。在 HTTP/1.1 中，Connection: keep-alive 是默认启用的，表示持久连接，以便处理不久后到来的新请求，无需重新建立连接而增加慢启动开销，提高网络的吞吐能力。在反向代理软件 Nginx 中，持久连接超时时间默认值为 75 秒，如果 75 秒内没有新到达的请求，则断开与客户端的连接。同时，浏览器每隔 45 秒会向服务器发送 TCP keep-alive 探测包，来判断 TCP 连接状况，如果没有收到 ACK 应答，则主动断开与服务器的连接。注意，HTTP keep-alive 和 TCP keep-alive 虽然都是一种保活机制，但是它们完全不相同，一个作用于应用层，一个作用于传输层。
断开连接
五，关闭TCP连接
避免服务器与客户端双方的资源占用和损耗，当双方没有请求或响应传递时，任意一方都可以发起关闭请求，四次挥手关闭TCP连接，了解可转 简述TCP连接与释放过程中的三次握手和四次挥手.
六，浏览器解析html数据渲染web画面
首先解析html，构建dom树 -> 构建render树 -> 布局render树 -> 绘制render树
解析过程中，浏览器首先会解析HTML文件构建DOM树，然后解析CSS文件构建渲染树，等到渲染树构建完成后，浏览器开始布局渲染树并将其绘制到屏幕上。在浏览器显示HTML时，会获取其他地址内容的标签。浏览器会发送一个获取请求来重新获得这些文件。比如我要获取外图片，CSS，JS文件等浏览器自上而下执行，过程中如遇到css、图片等，此时是异步请求。当文档加载过程中遇到js文件，html文档会挂起渲染（加载解析渲染同步）的线程，不仅要等待文档中js文件加载完毕，还要等待解析执行完毕，才可以恢复html文档的渲染线程。因为JS有可能会修改DOM；所以在编写代码时尽可能的把js写在html的底部，等html主体和css加载完之后再进行加载js；浏览器已经知道哪些节点要显示，每个节点的CSS属性是什么，每个节点在屏幕中的位置是哪里，最后一步painting（渲染）,按照算出来的规则，通过显卡，把内容画到屏幕上，显示出内容。
两个概念
reflow（回流）：几乎无法避免。现在界面上流行的一些效果，比如树状目录的折叠、展开（实质上是元素的显 示与隐藏），文字和窗口的改变，都将引起浏览器的reflow。鼠标滑过、点击……只要这些行为引起了页面上某些元素的占位面积、定位方式、边距等属性的变化，都会引起它内部、周围甚至整个页面的重新渲染。
repain（重绘）：如果只是改变某个元素的背景色、文字颜色、边框颜色等等不影响它周围或内部布局的属性，将只会引起浏览器repaint。
注：
回流必将引起重绘，而重绘不一定会引起回流。比如：只有颜色改变的时候就只会发生重绘而不会引起回流。
有些情况下，比如修改了元素的样式，浏览器并不会立刻 reflow 或 repaint 一次，而是会把这样的操作积攒一批，然后做一次 reflow，这又叫异步 reflow 或增量异步 reflow。
1-8. UDP如何实现可靠性传输
1、udp与tcp的区别
- TCP（TransmissionControl Protocol 传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层通信协议。
- UDP是User Datagram Protocol，一种无连接的传输层协议，提供面向事务的简单不可靠信息传送服务。可靠性由上层应用实现，所以要实现udp可靠性传输，必须通过应用层来实现和控制。
2、TCP如何实现可靠性传输？
确认机制、重传机制、滑动窗口。
2.1可靠性
1．应用数据被分割成TCP认为最适合发送的数据块。这和UDP完全不同，应用程序产生的数据长度将保持不变。由TCP传递给IP的信息单位称为报文段或段（segment）。
2．当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。当TCP收到发自TCP连接另一端的数据，它将发送一个确认。TCP有延迟确认的功能，在此功能没有打开，则是立即确认。功能打开，则由定时器触发确认时间点。
3．TCP将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP将丢弃这个报文段和不确认收到此报文段（希望发端超时并重发）。
4．既然TCP报文段作为IP数据报来传输，而IP数据报的到达可能会失序，因此TCP报文段的到达也可能会失序。如果必要，TCP将对收到的数据进行重新排序，将收到的数据以正确的顺序交给应用层。
5．既然IP数据报会发生重复，TCP的接收端必须丢弃重复的数据。[2] 6．TCP还能提供流量控制。TCP连接的每一方都有固定大小的缓冲空间。TCP的接收端只允许另一端发送接收端缓冲区所能接纳的数据。这将防止较快主机致使较慢主机的缓冲区溢出。2.2重传策略
TCP协议用于控制数据段是否需要重传的依据是设立重发定时器。在发送一个数据段的同时启动一个重传，如果在重传超时前收到确认(Acknowlegement)就关闭该重传，如果重传超时前没有收到确认，则重传该数据段。在选择重发时间的过程中，TCP必须具有自适应性。它需要根据互联网当时的通信情况，给出合适的重发时间。
这种重传策略的关键是对定时器初值的设定。采用较多的算法是Jacobson于1988年提出的一种不断调整超时时间间隔的动态算法。其工作原理是：对每条连接TCP都保持一个变量RTT（Round Trip Time），用于存放当前到目的端往返所需要时间最接近的估计值。当发送一个数据段时，同时启动连接的定时器，如果在定时器超时前确认到达，则记录所需要的时间（M），并修正[2] RTT的值，如果定时器超时前没有收到确认，则将RTT的值增加1倍。通过测量一系列的RTT（往返时间）值，TCP协议可以估算数据包重发前需要等待的时间。在估计该连接所需的当前延迟时通常利用一些统计学的原理和算法（如Karn算法），从而得到TCP重发之前需要等待的时间值。2.3窗口确认
TCP的一项功能就是确保每个数据段都能到达目的地。位于目的主机的TCP服务对接受到的数据进行确认，并向源应用程序发送确认信息。使用数据报头序列号以及确认号来确认已收到包含在数据段的相关的数据字节。
TCP在发回源设备的数据段中使用确认号，指示接收设备期待接收的下一字节。这个过程称为期待确认。
源主机在收到确认消息之前可以传输的数据的大小称为窗口大小。用于管理丢失数据和流量控制。3、udp如何实现可靠性传输？
UDP它不属于连接型协议，因而具有资源消耗小，处理速度快的优点，所以通常音频、视频和普通数据在传送时使用UDP较多，因为它们即使偶尔丢失一两个数据包，也不会对接收结果产生太大影响。<br /> 传输层无法保证数据的可靠传输，只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式，只是实现不在传输层，实现转移到了应用层。<br /> 实现确认机制、重传机制、窗口确认机制。<br />[UDP实现可靠性传输](https://blog.csdn.net/gettogetto/article/details/76736365)
2. 操作系统
2-1. 文件系统的相关概念
文件系统是什么，单位，目的
文件系统是操作系统中负责管理持久数据的子系统，文件系统的基本数据单位是文件，它的目的是对磁盘上的文件进行组织管理，那组织的方式不同，就会形成不同的文件系统。
索引节点，也就是 inode，用来记录文件的元信息，比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识，它们之间一一对应，也同样都会被存储在硬盘中，所以索引节点同样占用磁盘空间。为加速读取，通常把读取过的索引节点缓存在内存中。
目录项，也就是 dentry，用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成目录结构，但它与索引节点不同的是，目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存。多个目录项可以指向同一个文件，也即一个索引节点有多个别名。
磁盘进行格式化的时候，会被分成三个存储区域，分别是超级块、索引节点区和数据块区。
- 超级块，用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。
- 索引节点区，用来存储索引节点；
-
2-2. 虚拟文件系统VFS
文件系统的种类众多，而操作系统希望对用户提供一个统一的接口，于是在用户层与文件系统层引入了中间层，这个中间层就称为虚拟文件系统（Virtual File System，VFS）。
**
2-3. 文件系统的存储方式
那早期 Unix 文件系统是组合了前面的文件存放方式的优点
它是根据文件的大小，存放的方式会有所变化： 如果存放文件所需的数据块小于 10 块，则采用直接查找的方式；
- 如果存放文件所需的数据块超过 10 块，则采用一级间接索引方式；
- 如果前面两种方式都不够存放大文件，则采用二级间接索引方式；
- 如果二级间接索引也不够存放大文件，这采用三级间接索引方式；
那么，文件头（Inode）就需要包含 13 个指针：
- 10 个指向数据块的指针；
- 第 11 个指向索引块的指针；
- 第 12 个指向二级索引块的指针；
- 第 13 个指向三级索引块的指针；
所以，这种方式能很灵活地支持小文件和大文件的存放：
- 对于小文件使用直接查找的方式可减少索引数据块的开销；
- 对于大文件则以多级索引的方式来支持，所以大文件在访问数据块时需要大量查询；
这个方案就用在了 Linux Ext 2/3 文件系统里，虽然解决大文件的存储，但是对于大文件的访问，需要大量的查询，效率比较低。
2-4. I/O模型
根据是「否利用操作系统的缓存」，可以把文件 I/O 分为直接 I/O 与非直接 I/O：
- 直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
- 非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。
1、 阻塞 I/O，当用户程序执行 read ，线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷贝到应用程序的缓冲区中，当拷贝过程完成，read才会返回。
2、非阻塞 I/O，非阻塞的 read 请求在数据未准备好的情况下立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷贝到应用程序缓冲区，read 调用才可以获取到结果。
3、I/O 多路复用，系统提供了一种函数可以同时监控多个IO请求的操作，这个函数就是我们常说到的select、poll、epoll函数，有了这个函数后，应用线程通过调用select函数就可以同时监控多个IO请求，select函数监控的IO请求中只要有任何一个数据状态准备就绪了，select函数就会返回可读状态，这时询问线程再去通知处理数据的线程，对应线程此时再发起recvfrom请求去读取数据。（数据从内核态拷贝到用户态的过程）
4、信号驱动I/O模型，当进程发起一个IO操作，会向内核注册一个信号处理函数，然后进程返回不阻塞；当内核数据就绪时会发送一个信号给进程，进程便在信号处理函数中调用IO读取数据。
阻塞 I/O、非阻塞 I/O，还是基于非阻塞 I/O 的多路复用都是同步调用。因为它们在 read 调用时，内核将数据从内核空间拷贝到应用程序空间，过程都是需要等待的，也就是说这个过程是同步的，如果内核实现的拷贝效率不高，read 调用就会在这个同步过程中等待比较长的时间。
5、异步 I/O 是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程都不用等待。
当我们发起 aio_read 之后，就立即返回，内核自动将数据从内核空间拷贝到应用程序空间，这个拷贝过程同样是异步的，内核自动完成的，和前面的同步操作不一样，应用程序并不需要主动发起拷贝动作。
2-5. 简述进程切换的流程
如果想要从A进程切换到 B 进程，必定要先从用户态切换到内核态，因为这个切换的工作你不能让用户进程去实现，不然当 CPU 在用户进程手上的时候，他可以选择一直执行，不让出 CPU，这肯定是不允许的。所以操作系统需要先挂起正在占用 CPU 的 A 进程，才能切换到 B 进程。
由于从用户态切换到内核态的时候，CPU 是在用户进程手中，所以这个是通过硬中断来实现的。在从用户态切换到内核态之前需要保存用户进程的上下文，以便下一次执行时可以继续之前的工作。
这个上下文就是进程执行的环境，包括所有的寄存器变量，进程打开的文件、内存信息等。一个进程的上下文可以分为用户级上下文，寄存器上下文，系统级上下文。用户级上下文存储的是用户进程的内存数据以及堆栈数据等；寄存器上下文是一些通用寄存器；系统级上下文是内核栈、PCB (进程控制块)等。
2-6. 操作系统为什么分内核态和用户态，这两者之间如何切换
1、因为在CPU的指令中，有一些是非常危险的，比如清理内存、设置时钟等，如果所有的程序都能使用，就可能造成系统的崩溃，所以，CPU 将指令分为特权指令和非特权指令，对于那些危险的指令，只允许操作系统使用。2、CPU 的特权级别有四级，从 Ring0 到 Ring3，正常使用时一般只有两级，即用户态的 Ring3 和内核态的 Ring0。Ring3 状态不能访问 Ring0 的地址空间，包括代码和数据。
3、用户态切换到内核态的三种方式
- 系统调用（系统调用是通过软中断实现的）
- 中断（硬）
- 异常
2-7. 进程间通信IPC方式
- 管道（pipe）,流管道(s_pipe)和有名管道（FIFO）
- 信号（signal）
- 消息队列
- 共享内存
- 信号量
- 套接字（socket)
2-8. 死锁发生的条件
死锁是指两个或两个以上进程在执行过程中，因争夺资源而造成的相互等待的现象。
死锁发生的四个必要条件如下：
- 互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源；
- 请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源
- 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放
- 环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链
解决死锁的方法即破坏上述四个条件之一，主要方法如下：
- 资源一次性分配，从而剥夺请求和保持条件
- 可剥夺资源：即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可剥夺的条件
资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件
2-9. IO调度的算法
noop（不干涉算法）
noop算法，假设硬盘IO能力是足够的，有一定的IO合并优化，大致按照先来后到的顺序分配IO，适用于SSD，传统硬盘因为存在寻址，在noop算法下，性能会非常差。
cfq （完全公平算法）
cfq算法，给每个进程一个IO队列，然后轮询各个队列，达到公平的效果。适用于传统硬盘，也是长久以来的默认算法。为减少寻址，该算法尝试给IO排序，极端情况可导致IO饥饿，即如果一个程序有大量顺序读写，那么它就会插队，导致其他程序IO饥饿。CentOS 6默认使用cfq算法。
deadline （倒计时算法）
deadline算法，维护读写两个队列，每个队列都有各自的超时时间，确保每个IO在一定时间内可以得到满足，有效防止IO饥饿，适用于传统硬盘，ubuntu以及CentOS 7 都默认使用deadline算法。
anticipatory（预估分配算法）
anticipatory算法，为了减少IO寻址，在每个IO结束时停留一段时间，如果下一个IO正好发生在硬盘的临近位置，那么可以立即满足。适用于传统硬盘，在大量顺序读写时比较合适。2-10. 动态分区分配方法（首次匹配，最佳匹配，最坏匹配）
动态分区分配 就是在处理作业的过程中，建立分区，依用户请求的大小分配分区。在分区回收的过程中会涉及一个空间利用效率相关的放置策略，即选择空闲区的策略。
首次适应算法（First Fit）：该算法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链 中。
特点： 该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。
缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。最佳适应算法（Best Fit）：该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。
特点：每次分配给文件的都是最合适该文件大小的分区。
缺点：内存中留下许多难以利用的小的空闲区。最坏适应算法（Worst Fit）：最坏适应算法是将输入的作业放置到主存中与它所需大小差距最大的空闲区中。空闲区大小由大到小排序。
特点：尽可能地利用存储器中大的空闲区。<br /> 缺点：绝大多数时候都会造成资源的严重浪费甚至是完全无法实现分配。
2-11. 几种线程锁
悲观锁（多锁，适合写多，竞争激烈的场景）
悲观（先取锁再访问）：每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会block直到它拿到锁。悲观锁主要分为共享锁或排他锁
（1）共享锁【Shared lock】又称为读锁，简称S锁。顾名思义，共享锁就是多个事务对于同一数据可以共享一把锁，都能访问到数据，但是只能读不能修改。
（2）排他锁【Exclusive lock】又称为写锁，简称X锁。顾名思义，排他锁就是不能与其他锁并存，如果一个事务获取了一个数据行的排他锁，其他事务就不能再获取该行的其他锁，包括共享锁和排他锁，但是获取排他锁的事务是可以对数据行读取和修改。乐观锁（少锁，适用于写少，竞争不激烈的应用场景，可以提高吞吐量）
乐观锁是相对悲观锁而言的，乐观锁假设数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则返回给用户错误的信息，让用户决定如何去做。
问题1：CPU开销较大（线程冲突严重时乐观锁的自旋） 在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很大的压力。
问题2：不能保证代码块的原子性 CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新，就不得不使用Synchronized了。公平锁与非公平锁：
在非公平锁策略之下，不一定First in First Serve，而是出现各种线程随意抢占的情况。默认的ReentrantLock对象构造出来就是非公平的。当线程被挂起排队等待的时候，会被其他线程趁着线程还未被唤醒的空挡抢占锁（将state置为1）。
在构造ReentrantLock对象的时候传入一个true即可获得公平锁。公平锁会在抢占前先查询队列中是否有线程在等待，如果有就加入等待队列，如果没有就直接执行。ReentrantLock lock = new ReentrantLock(true)优劣：在CPU线程状态切换的空挡期较长的情况下，非公平锁性能高于公平锁性能。首先，在恢复一个被挂起的线程与该线程真正运行之间存在着严重的延迟。而且，非公平锁能更充分的利用cpu的时间片，尽量的减少cpu空闲的状态时间。
自旋锁：
当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环。
互斥锁 mutex：
在访问共享资源之前对进行加锁操作，在访问完成之后进行解锁操作。
加锁后，任何其他试图再次加锁的线程会被阻塞，直到当前进程解锁。读写锁 rwlock：
（也叫作共享互斥锁：读模式共享，写模式互斥） 适用场景： 读写锁非常适合对数据结构读的次数远远大于写的情况。
RCU锁（Read-Copy Update）： 读-复制 更新
RCU中，读者不需要使用锁，要访问资源尽管访问就好了。
RCU中，写者的同步开销比较大，要等到所有的读者都访问完成了才能够对被保护的资源进行更新。2-12. 线程与进程
线程与进程的区别
进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；
线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；
一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。线程的资源
共享资源为：进程代码段、进程的公有数据、进程打开的文件描述符、信号处理器、进程的当前目录和进程用户ID以及进程组ID
私有资源为：线程ID、寄存器组的值、线程堆栈、错误返回码、信号屏蔽码、线程优先级
进程通信与线程通信
进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。
多进程的缺点
创建进程的开销高（每个进程都拥有自己独立的数据和代码空间）
- 进程之间的通信不方便
- 进程切换开销高
2-13. 文件读写基本流程
读文件
1、进程调用库函数向内核发起读文件请求；
2、内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表表项；
3、调用该文件可用的系统调用函数read()
3、read()函数通过文件表项链接到目录项模块，根据传入的文件路径，在目录项模块中检索，找到该文件的inode；
4、在inode中，通过文件内容偏移量计算出要读取的页；
5、通过inode找到文件对应的address_space；
6、在address_space中访问该文件的页缓存树，查找对应的页缓存结点：
（1）如果页缓存命中，那么直接返回文件内容；
（2）如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页；重新进行第6步查找页缓存；
7、文件内容读取成功。写文件
前5步和读文件一致，在address_space中查询对应页的页缓存是否存在：
6、如果页缓存命中，直接把文件内容修改更新在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。
7、如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页。此时缓存页命中，进行第6步。
8、一个页缓存中的页如果被修改，那么会被标记成脏页。脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘：
（1）手动调用sync()或者fsync()系统调用把脏页写回
（2）pdflush进程会定时把脏页写回到磁盘
同时注意，脏页不能被置换出内存，如果脏页正在被写回，那么会被设置写回标记，这时候该页就被上锁，其他写请求被阻塞直到锁释放。mmap
总结来说，常规文件操作为了提高读写效率和保护磁盘，使用了页缓存机制。这样造成读文件时需要先将文件页从磁盘拷贝到页缓存中，由于页缓存处在内核空间，不能被用户进程直接寻址，所以还需要将页缓存中数据页再次拷贝到内存对应的用户空间中。这样，通过了两次数据拷贝过程，才能完成进程对文件内容的获取任务。写操作也是一样，待写入的buffer在内核空间不能直接访问，必须要先拷贝至内核空间对应的主存，再写回磁盘中（延迟写回），也是需要两次数据拷贝。
而使用mmap操作文件中，创建新的虚拟内存区域和建立文件磁盘地址和虚拟内存区域映射这两步，没有任何文件拷贝操作。而之后访问数据时发现内存中并无数据而发起的缺页异常过程，可以通过已经建立好的映射关系，只使用一次数据拷贝，就从磁盘中将数据传入内存的用户空间中，供进程使用。
总而言之，常规文件操作需要从磁盘到页缓存再到用户主存的两次数据拷贝。而mmap操控文件，只需要从磁盘到用户主存的一次数据拷贝过程。说白了，mmap的关键点是实现了用户空间和内核空间的数据直接交互而省去了空间不同数据不通的繁琐过程。因此mmap效率更高。
3. C/C++ 问题
3-1. C/C++，重载/重写，new/malloc，map/set
设计思想上：C++是面向对象的语言，而C是面向过程的结构化编程语言
语法上：
C++具有封装、继承和多态三种特性
C++相比C，增加多许多类型安全的功能，比如强制类型转换、
C++支持范式编程，比如模板类、函数模板等
重载：两个函数名相同，但是参数列表不同（个数，类型），返回值类型没有要求，在同一作用域中
重写：子类继承了父类，父类中的函数是虚函数，在子类中重新定义了这个虚函数，这种情况是重写
首先，new/delete是C++的关键字，而malloc/free是C语言的库函数，后者使用必须指明申请内存空间的大小，对于类类型的对象，后者不会调用构造函数和析构函数
map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree），其元素都是const的。
unordered map底层结构是哈希表
3-2. C++中static关键字的作用
对于函数定义和代码块之外的变量声明，static修改标识符的链接属性，由默认的external变为internal，作用域和存储类型不改变，这些符号只能在声明它们的源文件中访问。
对于代码块内部的变量声明，static修改标识符的存储类型，由自动变量改为静态变量，作用域和链接属性不变。这种变量在程序执行之前就创建，在程序执行的整个周期都存在。
对于被static修饰的普通函数，其只能在定义它的源文件中使用，不能在其他源文件中被引用
对于被static修饰的类成员变量和成员函数，它们是属于类的，而不是某个对象，所有对象共享一个静态成员。静态成员通过<类名>::<静态成员>来使用。
3-3. C++中类成员访问权限
public限定符
被public限定符所修饰的成员变量和函数可以被类的函数、子类的函数、友元函数，也可以由类的对象来访问，即可以使用成员运算符来访问。这里的友元函数，可以是该类的友元函数，也可以是该类的友元类的成员函数。
protected限定符
protected限定符修饰的成员变量和成员函数可以被该类的成员函数访问，但是不能被类对象所访问，即不能通过类对象的成员运算符来访问。另外，这些成员可以被子类的函数和友元函数访问，相比public成员 少了一个可以使用类对象直接访问的特性。具体使用与public类似，这里不再贴出代码。
private限定符
被private限定符修饰的成员变量只能被该类的方法和友元函数访问，子类函数无法访问，在这三个限定符中封装程度是最高的，一般来说，应该尽可能将类的成员变量声明为private而不是其他，减少成员变量的暴露，只提供getter和settter方法给外界访问，这样能提高类的安全性。具体使用与public类似。
3-4. C++源文件从文本到可执行文件经历的过程
对于C++源文件，从文本到可执行文件一般需要四个过程：
预处理阶段：对源代码文件中文件包含关系（头文件）、预编译语句（宏定义）进行分析和替换，生成预编译文件。
编译阶段：将经过预处理后的预编译文件转换成特定汇编代码，生成汇编文件
汇编阶段：将编译阶段生成的汇编文件转化成机器码，生成可重定位目标文件
链接阶段：将多个目标文件及所需要的库连接成最终的可执行目标文件
3-5. C++的内存管理
在C++中，虚拟内存分为代码段、数据段、BSS段、堆区、文件映射区以及栈区六部分。
代码段:包括只读存储区和文本区，其中只读存储区存储字符串常量，文本区存储程序的机器代码。
数据段：存储程序中已初始化的全局变量和静态变量
bss 段：存储未初始化的全局变量和静态变量（局部+全局），以及所有被初始化为0的全局变量和静态变量。
堆区：调用new/malloc函数时在堆区动态分配内存，同时需要调用delete/free来手动释放申请的内存。
映射区:存储动态链接库以及调用mmap函数进行的文件映射
栈：使用栈空间存储函数的返回地址、参数、局部变量、返回值
3-6. 堆和栈的区别是什么
1、堆栈空间分配区别
栈（操作系统）：由操作系统（编译器）自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆（操作系统）： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。
2、堆栈缓存方式区别
栈使用的是一级缓存， 它们通常都是被调用时处于存储空间中，调用完毕立即释放。
堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
3、堆栈数据结构区别
堆（数据结构）：堆可以被看成是一棵树，如：堆排序。
栈（数据结构）：一种先进后出的数据结构。
3-7. 智能指针
auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持，并且第一个已经被11弃用。
智能指针的作用是管理一个指针，因为存在以下这种情况：申请的空间在函数结束时忘记释放，造成内存泄漏。使用智能指针可以很大程度上的避免这个问题，因为智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间，不需要手动释放内存空间。
auto_ptr: 采用所有权模式，所有权可以被剥夺，存在潜在的内存崩溃问题。
unique_ptr：采用所有权模式，所有权不可剥夺，可以赋值为临时右值。也可以使用move移动值。
shared_ptr: 实现共享式拥有概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。除了可以通过new来构造，还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。当我们调用release()时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。
成员函数：
use_count 返回引用计数的个数
unique 返回是否是独占所有权( use_count 为 1)
swap 交换两个 shared_ptr 对象(即交换所拥有的对象)
reset 放弃内部对象的所有权或拥有对象的变更, 会引起原有对象的引用计数的减少
get 返回内部对象(指针), 由于已经重载了()方法, 因此和直接使用对象是一样的.如 shared_ptr
weak_ptr: 是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象. 进行该对象的内存管理的是那个强引用的 shared_ptr. weak_ptr只是提供了对管理对象的一个访问手段。weak_ptr 设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少。weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr。
3-8. 使用迭代器删除元素的问题
for ( ; it != arrayList.end(); it++) {if (...)arrayList.erase(it);}
如上使用迭代器删除元素时，会产生崩溃问题。根本原因是：当容器中的一个元素被删除时，指向该元素后续的迭代器变得无效。上面的代码中，只要执行了erase(it),那么it就会变得无效，那么执行it++就肯定会出错。
通常有两条规则：
1. 对于节点式容器(map, list, set)元素的删除，插入操作会导致指向该元素的迭代器失效，其他元素迭代器不受影响。但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个 元素的迭代器即可。
for (map<int, int>::iterator iter = mp.begin(); iter != mp.end(); ) {if (iter->first == 1) mp.erase(iter++); // NOTE it is SAFE!else iter->second++;}
2. 对于顺序式容器(vector，string，deque)元素的删除、插入操作会导致指向该元素以及后面的元素的迭代器失效。但是后边每个元素都会往前移动一个位置，当前的迭代器指针直接指向了下一个元素;。
while (it != arrayInt.end()){if (...){// 需要注意的是，因为顺序式容器会使本身和后面的元素迭代器都失效，所以不能简单的++操作// 顺序式容器的erase()会返回紧随被删除元素的下一个元素的有效迭代器（节点式容器的erase()的返回值是void）it = arrayInt.erase(it);}else it++;}
3-9. 指针和引用的区别
指针和引用主要有以下区别：
- 引用必须被初始化，但是不分配存储空间。指针可以不在声明时初始化，需要分配存储空间。
- 引用初始化后不能被改变，指针可以改变所指的对象。
- 不存在指向空值的引用，但是存在指向空值的指针。
指针本质是一个变量，具有独立性，可以被改变。
引用本质是一个别名，具有依附性，在初始化后无法改变。
3-10. vecotr的实现原理
template<class _Ty,class _Ax>class vector: public _Vector_val<_Ty, _Ax>{ // varying size array of valuespublic:/********/protected:pointer _Myfirst; // pointer to beginning of arraypointer _Mylast; // pointer to current end of sequencepointer _Myend; // pointer to end of array};
vector是由三个指针来实现对空间的管理，当插入数据时，vecotr的容量已满，则需要二次分配空间。在VS下，capacity会扩大为1.5倍，若仍旧不足，则扩大为size+count。并将原有数据和新数据拷贝到新空间下，释放原有空间。
3-10. const和constexpr的区别
constexpr为常量表达式：值不会改变并且在编译过程中就会得到计算结果的表达式。
C++中的const的目的是通过编译器来保证对象的常量性，对象的常量性可以分为两种：物理常量性（即每个bit都不可改变）和逻辑常量性（即对象的表现保持不变）。C++中采用的是物理常量性。
指针变量的类型按变量名左边最近的‘*’分成两部分，右边的部分表示指针变量自己的性质，而左边的部分则表示它指向元素的性质。
3-11. c++11的新特性
- C++ auto类型推导：根据变量的值自动类型推导。不能用于参数；不能用于非静态成员；不能定义数组；不能作为模版参数；
- C++ decltype类型推导：根据exp表达式推导类型，加上了一层或多层括号，则编译器会推断得到引用类型。可以用于非静态成员。
- 左值和右值：在C++11中，可以取地址的，有名字的是左值。反之为右值，其中纯右值为临时变量值、不跟对象关联的字面量值；而其中另一个将亡值为将要被移动的对象，如move的返回值。引用类型本身自己并不拥有所绑定对象的内存，只是该对象的一个别名。左值引用是具名变量值的别名，而右值引用则是不具名（匿名）变量的别名。
- C++11右值引用：const type & 常量左值引用为万能引用。T&& 返回值为右值引用，为了充分利用在函数调用过程中产生的临时变量，对这个临时变量达到最大限度的使用率。
- C++返回值类型后置：为了解决函数返回值类型依赖于参数而导致难以确定返回值类型的问题，对返回值类型的推导就可以用清晰的方式（直接通过参数做运算）描述。
- 对模板实例化中连续右尖括号＞＞的改进：C++98/03中模板实例化的连续两个右尖括号（>>）会被编译器解释成 右移操作符，而不是 模板参数表的结束需要加入空格。C++11不再需要空格，但右移运算符会引起歧义。
- C++11使用using定义别名：typedef无法重定义一个模版类，using可以定义模版别名。template
\n using str_map_t = std::map - C++11在函数模板和类模板中使用可变参数。
- 支持函数模板的默认模板参数。
- C++11 tuple元组：实例化的对象可以存储任意数量、任意类型的数据。
- C++11列表初始化。
- C++11 lambda匿名函数：[外部变量访问方式说明符] (参数) mutable noexcept/throw() -> 返回值类型{函数体；}； [=]以值传递方式导入全部变量，局部变量不可变，全局变量可变； [&]以引入传递方式导入全部变量； [=,&val]将val引入传递，其他值传递。 mutable可以改变值传递的局部变量，但不会修改外部变量。
- C++11非受限联合体（union）。
- C++11 for循环（基于范围的循环）详解。
- 移动构造函数：临时对象原本控制的内存的空间转移给构造出来的对象。拷贝构造：在新的空间构造对象。
- C++11 move()函数：将左值强制转换为右值。
- C++11引用限定符。
- C++11完美转发及实现方法详解。
- C++11 nullptr：初始化空指针。
3-13. 大端小端 内存对齐
#pragma pack(1) 意味着全部以1的整数倍对齐
4. 数据库相关
4-1 什么是事务？四个特征？
1、事务是应用程序中一系列严密的操作，所有操作必须成功完成，否则在每个操作中所作的所有更改都会被撤消。
2、事务的结束有两种，当事务中的所以步骤全部成功执行时，事务提交。如果其中一个步骤失败，将发生回滚操作，撤消撤消之前到事务开始时的所以操作。
3、四个特性：原子性（ Atomicity ）、一致性（ Consistency ）、隔离性（ Isolation ）和持续性（ Durability ）。这四个特性简称为 ACID 特性。
- 原子性。事务是数据库的逻辑工作单位，事务中包含的各操作要么全部成功，要么一个都不做。
- 一致性。事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。（因此当数据库只包含成功事务提交的结果时，就说数据库处于一致性状态。如果数据库系统运行中发生故障，有些事务尚未完成就被迫中断，这些未完成事务对数据库所做的修改有一部分已写入物理数据库，这时数据库就处于一种不正确的状态，或者说是不一致的状态。）
- 隔离性。一个事务的执行不能其它事务干扰。即一个事务内部的操作及使用的数据对其它并发事务是隔离的，并发执行的各个事务之间不能互相干扰。
持续性。也称永久性，指一个事务一旦提交，它对数据库中的数据的改变就应该是永久性的。接下来的其它操作或故障不应该对其执行结果有任何影响
4-2 mysql四种隔离级别？
1、SQL标准定义了4类隔离级别，包括了一些具体规则，用来限定事务内外的哪些改变是可见的，哪些是不可见的。低级别的隔离级一般支持更高的并发处理，并拥有更低的系统开销。
Read Uncommitted（读取未提交内容） 在该隔离级别，所有事务都可以看到其他未提交事务的执行结果。本隔离级别很少用于实际应用，因为它的性能也不比其他级别好多少。读取未提交的数据，也被称之为脏读（Dirty Read）。
- Read Committed（读取提交内容） 这是大多数数据库系统的默认隔离级别（但不是MySQL默认的）。它满足了隔离的简单定义：一个事务只能看见已经提交事务所做的改变。这种隔离级别 也支持所谓的不可重复读（Nonrepeatable Read），因为同一事务的其他实例在该实例处理其间可能会有新的commit，所以同一select可能返回不同结果。
- Repeatable Read（可重读） 这是MySQL的默认事务隔离级别，它确保同一事务的多个实例在并发读取数据时，会看到同样的数据行。不过理论上，这会导致另一个棘手的问题：幻读 （Phantom Read）。简单的说，幻读指当用户读取某一范围的数据行时，另一个事务又在该范围内插入了新行，当用户再读取该范围的数据行时，会发现有新的“幻影” 行。InnoDB和Falcon存储引擎通过多版本并发控制（MVCC，Multiversion Concurrency Control）机制解决了该问题。
- Serializable（可串行化） 这是最高的隔离级别，它通过强制事务排序，使之不可能相互冲突，从而解决幻读问题。简言之，它是在每个读的数据行上加上共享锁。在这个级别，可能导致大量的超时现象和锁竞争。
4-3. 四种隔离级别解决了什么问题？
1、这四种隔离级别采取不同的锁类型来实现，若读取的是同一个数据的话，就容易发生问题。例如： • 脏读(Drity Read)：某个事务已更新一份数据，另一个事务在此时读取了同一份数据，由于某些原因，前一个RollBack了操作，则后一个事务所读取的数据就会是不正确的。
• 不可重复读(Non-repeatable read):在一个事务的两次查询之中数据不一致，这可能是两次查询过程中间插入了一个事务更新的原有的数据。
• 幻读(Phantom Read):在一个事务的两次查询中数据笔数不一致，例如有一个事务查询了几列(Row)数据，而另一个事务却在此时插入了新的几列数据，先前的事务在接下来的查询中，就有几列数据是未查询出来的，如果此时插入和另外一个事务插入的数据，就会报错。
4-4.MVCC多版本并发控制（undo log/next-key locks)
1、MVCC，全称Multi-Version Concurrency Control，即多版本并发控制。MVCC是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问，在编程语言中实现事务内存。
- 当前读 像select lock in share mode(共享锁), select for update ; update, insert ,delete(排他锁)这些操作都是一种当前读，为什么叫当前读？就是它读取的是记录的最新版本，读取时还要保证其他并发事务不能修改当前记录，会对读取的记录进行加锁。
- 快照读 像不加锁的select操作就是快照读，即不加锁的非阻塞读；快照读的前提是隔离级别不是串行级别，串行级别下的快照读会退化成当前读；之所以出现快照读的情况，是基于提高并发性能的考虑，快照读的实现是基于多版本并发控制，即MVCC,可以认为MVCC是行锁的一个变种，但它在很多情况下，避免了加锁操作，降低了开销；既然是基于多版本，即快照读可能读到的并不一定是数据的最新版本，而有可能是之前的历史版本
2、数据库并发场景有三种，分别为：
- 读-读：不存在任何问题，也不需要并发控制
- 读-写：有线程安全问题，可能会造成事务隔离性问题，可能遇到脏读，幻读，不可重复读
- 写-写：有线程安全问题，可能会存在更新丢失问题，比如第一类更新丢失，第二类更新丢失 MVCC带来的好处是？
3、多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前的数据库的快照。 所以MVCC可以为数据库解决以下问题
- 在并发读写数据库时，可以做到在读操作时不用阻塞写操作，写操作也不用阻塞读操作，提高了数据库并发读写的性能
- 同时还可以解决脏读，幻读，不可重复读等事务隔离问题，但不能解决更新丢失问题
4、MVCC的目的就是多版本并发控制，在数据库中的实现，就是为了解决读写冲突，它的实现原理主要是依赖记录中的 3个隐式字段，undo日志 ，Read View 来实现的。
隐式字段
每行记录除了我们自定义的字段外，还有数据库隐式定义的DB_TRX_ID,DB_ROLL_PTR,DB_ROW_ID等字段
- DB_TRX_ID
6byte，最近修改(修改/插入)事务ID：记录创建这条记录/最后一次修改该记录的事务ID - DB_ROLL_PTR
7byte，回滚指针，指向这条记录的上一个版本（存储于rollback segment里） - DB_ROW_ID
6byte，隐含的自增ID（隐藏主键），如果数据表没有主键，InnoDB会自动以DB_ROW_ID产生一个聚簇索引 实际还有一个删除flag隐藏字段, 既记录被更新或删除并不代表真的删除，而是删除flag变了
undo日志主要分为两种：
insert undo log 代表事务在insert新记录时产生的undo log, 只在事务回滚时需要，并且在事务提交后可以被立即丢弃
- update undo log 事务在进行update或delete时产生的undo log; 不仅在事务回滚时需要，在快照读时也需要；所以不能随便删除，只有在快速读或事务回滚不涉及该日志时，对应的日志才会被purge线程统一清除
5、对MVCC有帮助的实质是update undo log ，undo log实际上就是存在rollback segment中旧记录链，它的执行流程如下：
- 在事务1修改该行(记录)数据时，数据库会先对该行加排他锁
- 然后把该行数据拷贝到undo log中，作为旧记录，既在undo log中有当前行的拷贝副本
- 拷贝完毕后，修改该行name为Tom，并且修改隐藏字段的事务ID为当前事务1的ID, 我们默认从1开始，之后递增，回滚指针指向拷贝到undo log的副本记录，既表示我的上一个版本就是它
- 事务提交后，释放锁
- 在事务2修改该行数据时，数据库也先为该行加锁
- 然后把该行数据拷贝到undo log中，作为旧记录，发现该行记录已经有undo log了，那么最新的旧数据作为链表的表头，插在该行记录的undo log最前面
- 修改该行age为30岁，并且修改隐藏字段的事务ID为当前事务2的ID, 那就是2，回滚指针指向刚刚拷贝到undo log的副本记录
- 事务提交，释放锁
next-key locks
InnoDB有三种行锁的算法：
1，Record Lock：单个行记录上的锁。
2，Gap Lock：间隙锁，锁定一个范围，但不包括记录本身。GAP锁的目的，是为了防止同一事务的两次当前读，出现幻读的情况。
3，Next-Key Lock：1+2，锁定一个范围，并且锁定记录本身。对于行的查询，都是采用该方法，主要目的是解决幻读的问题。
- Record Locks 锁定一个记录上的索引，而不是记录本身。
- 如果表没有设置索引，InnoDB 会自动在主键上创建隐藏的聚簇索引，因此 Record Locks 依然可以使用。
- Gap Locks 锁定索引之间的间隙，但是不包含索引本身。例如当一个事务执行以下语句，其它事务就不能在 t.c 中插入 15。
- SELECT c FROM t WHERE c BETWEEN 10 and 20 FOR UPDATE;
Next-Key Locks 是 MySQL 的 InnoDB 存储引擎的一种锁实现。MVCC 不能解决幻读的问题，Next-Key Locks 就是为了解决这个问题而存在的。在可重复读（REPEATABLE READ）隔离级别下，使用 MVCC + Next-Key Locks 可以解决幻读问题。当查询的索引含有唯一属性的时候，Next-Key Lock 会进行优化，将其降级为Record Lock，即仅锁住索引本身，不是范围。它是 Record Locks 和 Gap Locks 的结合，不仅锁定一个记录上的索引，也锁定索引之间的间隙。
4-5. Innodb的锁机制
InnoDB与MyISAM的最大不同有两点：一是支持事务（TRANSACTION）；二是采用了行级锁。关于事务我们之前有专题介绍，这里就着重介绍下它的锁机制。
总的来说，InnoDB按照不同的分类共有七种类型的锁：共享/排它锁(Shared and Exclusive Locks) 意向锁(Intention Locks) 间隙锁(Gap Locks) 记录锁(Record Locks) 临键锁(Next-key Locks) 插入意向锁(Insert Intention Locks) 自增锁(Auto-inc Locks)
Innodb的锁机制
总结 以上总结的7种锁，可以按两种方式来区分：
1. 按锁的兼容性来划分，可以分为共享、排他锁； 共享锁(S锁、IS锁)，可以提高读读并发；
- 为了保证数据强一致，InnoDB使用强互斥锁(X锁、IX锁)，保证同一行记录修改与删除的串行性；
- 按锁的粒度来划分，可以分为：
- 表锁：意向锁(IS锁、IX锁)、自增锁；
- 行锁：记录锁、间隙锁、临键锁、插入意向锁；
其中，InnoDB的细粒度锁(即行锁)，是实现在索引记录上的(如果未命中索引则会失效)；
记录锁锁定索引记录；间隙锁锁定间隔，防止间隔中被其他事务插入；
临键锁锁定索引记录+间隔，防止幻读；
InnoDB使用插入意向锁，可以提高插入并发；
间隙锁(gap lock)与临键锁(next-key lock)只在Repeatable-Read（RR可重复读）以上的级别生效，Read-Committed（RC已提交读）下会失效。
4-6. 其他锁机制
互斥锁
互斥锁用于控制多个线程对他们之间共享资源互斥访问的一个信号量。也就是说是为了避免多个线程在某一时刻同时操作一个共享资源。
在某一时刻，只有一个线程可以获取互斥锁，在释放互斥锁之前其他线程都不能获取该互斥锁。如果其他线程想要获取这个互斥锁，那么这个线程只能以阻塞方式进行等待。
条件锁
条件锁就是所谓的条件变量，某一个线程因为某个条件未满足时可以使用条件变量使该程序处于阻塞状态。一旦条件满足以“信号量”的方式唤醒一个因为该条件而被阻塞的线程。最为常见就是在线程池中，起初没有任务时任务队列为空，此时线程池中的线程因为“任务队列为空”这个条件处于阻塞状态。
自旋锁
与互斥锁sleep-waiting不同，自旋锁是一种busy-waiting的锁。也就是说，如果线程T1正在使用自旋锁，而线程T2也去申请这个自旋锁，此时T2虽然得不到这个自旋锁，但运行T2的核心会一直不断地循环检查锁是否可用（自旋锁请求），直到获取到这个自旋锁为止，而不会将T2投入等待队列。也就是说自旋锁会产生盲等，一般适用于轻量级的加锁。
读写锁
某一时刻可以有多个进程同时读一个共享变量，但同一时刻只有有一个进程可以写，且读写无法同时进行。读锁可以在没有写锁的时候被多个线程同时持有，写锁是独占的。
使用互斥锁实现读写锁
count_mutex = mutex_init();write_mutex = mutex_init();read_count = 0;void read_lock {lock(count_mutex);read_count++;if (read_count == 1) {lock(write_mutex);}unlock(count_mutex);}void read_unlock {lock(count_mutex);read_count--;if (read_count == 0) {unlock(write_mutex);}unlock(count_mutex);}void write_lock { lock(write_mutex); }void write_unlock { unlock(write_mutex); }
5. Java问题
5-1. Java bean是什么
- 1、所有属性为private
- 2、提供默认构造方法
- 3、提供getter和setter
- 4、实现serializable接口
5-2. IOC( Inversion of Control ), 控制反转解析与实现.
5-3. Spring框架
Spring框架简介
Spring框架总结
6. 算法问题
6-1. 十大排序算法
6-2. KMP算法 - 字符串匹配
6-3. 五大常用算法——分治法，动态规划，回溯法，分支界限法，贪心算法
6-4. 红黑树
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
- 性质1：每个节点要么是黑色，要么是红色。
- 性质2：根节点是黑色。
- 性质3：每个叶子节点（NIL）是黑色。
- 性质4：每个红色结点的两个子结点一定都是黑色。
- 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。
- 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
- 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
- 变色：结点的颜色由红变黑或由黑变红。
为什么要要用红黑树？
1、首先红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色，红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高
2、红黑树能够以O(log2 (n)) 的时间复杂度进行搜索、插入、删除操作
3、简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
红黑树和平衡树的对比和选择
1、平衡树结构更加直观，读取性能比红黑树要高；增加和删除节点 恢复平衡的性能不如红黑树
2、红黑树，读取性能不如平衡树；增加和删除节点 恢复平衡性能比平衡树好
6-5. 双重数组实现vector
6-6. 五种路径算法
6-6. 海量数据处理
- 海量URL找相同——Hash到不同小文件中，通过hashset在小文件中寻找。
- 海量URL找高频——Hash到不同小文件中，通过HashMap和小顶堆实现。
- 海量数字找存在or找重复——位图法，每一bit表示一个数字。
海量query频度排序——Hash后通过HashMap计算频度，使用归并排序。
6-7. 二叉树相关
递归定义：二叉树是一颗空树或是由根节点和互不相交的左右子树构成，左右子树也是二叉树。
- 满二叉树：只有度为0和2的节点，且度为0的节点在同一层。
- 完全二叉树：深度为k的二叉树的N个节点都与深度为k的满二叉树的1到N个节点位置完全相同，称为完全二叉树。
- 平衡二叉树：空树或左右子树的高度差绝对值不超过1，且左右子树都是平衡二叉树。
若有收获，就点个赞吧
0 人点赞
