Java总结-1

Java总结-1

一、计算机网络

1.OSI、TCP/IP、五层体系结构联系与区别？

（1）三种比较？

（2）七层结构细节？

（3）每一层对应的设备？

2.说一说TCP/IP协议簇？

• 应用层（它是计算机用户，以及各种应用程序和网络之间的接口，其功能是直接向用户提供服务，完成用户希望在网络上完成的各种工作。）
  • SNMP
  • SMTP
• 传输层（向用户提供可靠的端到端的差错和流量控制，保证报文的正确传输。传输层的作用是向高层屏蔽下层数据通信的细节，即向用户透明地传送报文。）
• 网络层（通过路由选择算法，为报文或分组通过通信子网选择最适当的路径。）
  • ICMP
  • IGMP
  • RIP
  • BGP
  • OSPF
  • IP
• 链路层（通过各种控制协议，将有差错的物理信道变为无差错的、能可靠传输数据帧的数据链路。）
  • ARP，RARP

3.TCP三次握手的过程？

握手过程可以由客户端调用socket开启，客户端发送SYN和Seq，closed状态变换为SYN_SEND状态，服务器端由LISTEN状态变换为SYN_RECV状态，服务端回送SYN+ACK，客户端接收，客户端状态变为Established，客户端发送ACK，服务端接收到ACK，状态变为Established，至此，TCP三次握手的过程就完成了。

（1）第一次握手：服务端确定（服务端可以接收数据，客户端可以发送数据）

（2）第二次握手：客户端确定（服务端可以发送数据，服务端可以接收数据）

（3）第三次握手：服务端确定（客户端可以接收数据）

以上，（1）（2）（3）是的双方确定彼此可以接收和发送数据。

4.TCP四次挥手的过程？

• 关闭连接的过程可以由服务端和客户端的任何一方发起，发起的一方状态变化为：

Established———>FIN_WAIT_1———>FIN_WAIT_2———>TIME_WAIT———>CLOSED;

• 被动关闭的一方的状态变化为：

Establised———>CLOSE_WAIT———>LAST_ACK———>CLOSED.

5.TCP在三次握手的过程中是如何超时重传的？

(1) 如果第一个包，A发送给B请求建立连接的报文(SYN)如果丢掉了，A会周期性的超时重传，直到B发出确认(SYN+ACK)；
(2) 如果第二个包，B发送给A的确认报文(SYN+ACK)如果丢掉了，B会周期性的超时重传，直到A发出确认(ACK)；
(3) 如果第三个包，A发送给B的确认报文(ACK)如果丢掉了，

- A在发送完确认报文之后，单方面会进入ESTABLISHED的状态，B还是SYN_RCVD状态
- 如果此时双方都没有数据需要发送，B会周期性的超时发送(SYN+ACK)，直到收到A的确认报文(ACK)，此时B也进入ESTABLISHED状态，双方可以发送数据；
- 如果A有数据发送，A发送的是(ACK+DATA)，B会在收到这个数据包的时候自动切换到ESTABLISHED状态，并接受数据(DATA)；
- 如果这个时候B要发送数据，B是发送不了数据的，会周期性的超时重传(SYN+ACK)直到收到A的确认(ACK)B才能发送数据。

6.为什么要三次握手，四次挥手？

（1）为什么要进行三次握手？

三次握手的目的是为了建立可靠的通信信道，简单地来说就是双方确认自己与对方的发送和接收是正常的。

这是防止已失效的连接请求报文段突然又传送到了B而引发错误。 举例，客户端A向服务端B发送数据，受到网络状态的影响，可能A发送的数据B很久以后才收到（实际上A已经通过重传机制重新发送了），当这个阻塞的数据到来的时候，B就会误以为这是一个新的连接，则B将等待A，但是实际上A并没有发起新的请求，这就导致了资源的浪费。

（2）为什么要进行四次挥手？ TCP通信是一个双工通信，在结束连接的时候FIN和ACK是分开发送的，A向B发送FIN仅仅表示A不在发送数据，并不表示自己不在接收数据，同理，B向A发送FIN仅仅表示B不在发送数据，但是自己是可以接收数据的。

为什么要在发起端加上TIME_WAIT？是为了保证ACK丢失的时候可以重传。客户端发送第四次挥手中的报文后，再经过2MSL，可使本次TCP连接中的所有报文全部消失，不会出现在下一个TCP连接中。考虑丢包问题，如果第四挥手发送的报文在传输过程中丢失了，那么服务端没收到确认ack报文就会重发第三次挥手的报文。如果客户端发送完第四次挥手的确认报文后直接关闭，而这次报文又恰好丢失，则会造成服务端无法正常关闭。

7.在浏览器地址栏输入一个url到浏览器返回页面的过程？

• 浏览器分析超链指向页面的 URL。
• 浏览器向 DNS 请求解析 www.tsinghua.edu.cn 的 IP 地址。
• 域名系统 DNS 解析出清华大学服务器的 IP 地址。
• 浏览器与服务器建立 TCP 连接
• 浏览器发出取文件命令：GET /chn/yxsz/index.htm。(HTTP)
• 服务器给出响应，把文件 index.htm 发给浏览器。
• TCP 连接释放。
• 浏览器显示“清华大学院系设置”文件 index.htm 中的所有文本。

8.说一说在三次握手的时候可能存在的安全问题？

当第二次握手后，服务端将会进入SYN_RECV状态（又叫做半连接状态），通过伪造客户端的地址，这个时候服务器端一直在等待客户端返回ACK，但是由于地址是伪造的，所以根本就无法收到ACK。当这种伪造的连接数量大的时候就会导致DDOS。

9.域名解析

m.xyz.com需要查找y.abc.com的IP地址：

• 主机m.xyz.com向本地域名服务器进行递归查询。

  主机向本地域名服务器查询时一般使用递归查询。

  • 递归查询：就是如果本地域名服务器没有所需域名的IP地址，本地域名服务器就以客户的方式向其他根域名服务器继续查询，而不是主机自己进行查询。返回给客户的是解析好的ip。（查查查，一直查到了再返回）

  本地域名服务器向其他根域名服务器进行查询的时一般使用迭代查询。

  • 迭代查询： 当某个根域名服务器收到本地域名服务器的请求报文时，要么告诉它所需域名的IP地址，要么告诉它下一步应该向哪个服务器发起询问。然后让本地域名服务器自己去查询。（查不到，你去别的地方查询吧）

• 本地域名服务器迭代查询，先向一个根域名服务器查询。

• 根域名服务器告诉本地域名服务器，下一步应该向顶级域名服务器dns.com查询。

• 顶级域名服务器dns.com告诉本地域名服务器，下一步查找权限域名服务器：dns.adc.com。

• 本地域名服务器向权限域名服务器发起查询。权限域名服务器告诉本地服务器所需的IP地址，本地服务器在告诉给本地主机。

根：美国（10），日本（1），英国（1），瑞士（1）

顶级域名：com，org，edu，gov等

二级域名：

子域：

总共有四层，最大深度127层

DNS资源记录：

SOA，每一个区在开始处都包含一个授权记录

NS资源记录，域名服务器记录

A资源记录，

PTR资源记录，

CNAME资源记录，别名记录

10.TCP是如何保证可靠传输的？(分编校丢流拥重超)

• （1）应用数据被TCP分割成为适合发送的数据块
• （2）TCP将会给每一个包进行编号，接收方会对数据进行排序，将有序的数据传输给应用层。 序列号：TCP传输时将每个字节的数据都进行了编号，这就是序列号。 确认应答：TCP传输的过程中，每次接收方收到数据后，都会对传输方进行确认应答。也就是发送ACK报文。这个ACK报文当中带有对应的确认序列号，告诉发送方，接收到了哪些数据，下一次的数据从哪里发。 序列号的作用不仅仅是应答的作用，有了序列号能够将接收到的数据根据序列号排序，并且去掉重复序列号的数据。这也是TCP传输可靠性的保证之一。
• （3）TCP将会保持首部和数据的校验和，目的是检查数据在传输的过程中是否被修改
• （4）丢弃重复发送的数据
• （5）流量控制：TCP连接的每一方都有一个固定的缓冲空间，TCP的接收端只允许发送端发送接收端缓冲区能够容纳的数据，当接收方来不及处理的时候，能够提示发送端降低发送的速率，防止丢包。（TCP使用的是滑动窗口进行流量控制)，如果发送端发送的数据太快，接收端来不及接收就会出现丢包问题。为了解决这个问题，TCP协议利用了滑动窗口进行了流量控制。在TCP首部有一个16位字段大小的窗口，窗口的大小就是接收端接收数据缓冲区的剩余大小。接收端会在收到数据包后发送ACK报文时，将自己的窗口大小填入ACK中，发送方会根据ACK报文中的窗口大小进而控制发送速度。如果窗口大小为零，发送方会停止发送数据。
• （6）拥塞控制（当网络阻塞的时候，减少数据的发送，拥塞控制就是防止过多的数据注入到网络中，这样使网络中的路由器或者链路不至于过载。）这里的发送方会维护一个拥塞窗口的状态变量，它和流量控制的滑动窗口是不一样的，滑动窗口是根据接收方数据缓冲区大小确定的，而拥塞窗口是根据网络的拥塞情况动态确定的，一般来说发送方真实的发送窗口为滑动窗口和拥塞窗口中的最小值。
• （7）自动重传（为了实现可靠的传输，每发送完一个分组就会停止发送，等待对方确认，确认后再发送下一个分组。）
• （8）超时重传（当TCP发出一个分组后，它将启动一个定时器，等待目的端确认接收，如果不及时，将会重传。）

11.TCP和UDP之间的区别？(面头流速可有界)

区别	TCP	UDP
面向连接	面向连接，TCP不提供广播和多播服务	面向无连接，UDP支持一对一、多对一、一对多、多对多的交互通信。
头部大小	头部至少为20个字节	头部为8个字节
流量控制	有流量控制	没有流量控制
速度	TCP速度较慢	UDP速度较快
可靠性	可靠传输	不可靠传输
有序	有序	无序
界	TCP有界，通过字节流传输	UDP无界，每一个包是单独传输的，发送方的UDP对应用程序交下来的报文添加首部后直接交付给IP层。UDP对应用层交下来的报文，既不合并，也不拆分，而是保留这些报文的边界。
适用场景	视频	文件传输

12.post和get的区别？

区别	POST	GET
可见性	数据在url中不可见	参数在url中可见
长度	没有长度限制	有长度限制
编码	application/x-www-form-urlencoded, multipart/form-data	application/x-www-form-urlencoded
缓存	不支持	支持
安全性	相对安全	相对不安全

13.在TCP和UDP之上都有哪些应用层的协议？

TCP：HTTP，HTTPS，SMTP（简单邮件传输协议），POP3，SSH

UDP：DNS，Telnet，SNMP（简单网络管理协议），IGMP（网络组管理协议）,RIP(路由信息协议)，DHCP（动态主机设置协议）

14.HTTPS握手的过程？

（1）客户端给出一个协议版本号、一个客户端生成的随机数（Client random）以及客户端支持的加密算法。（客户端发送了三件东西）

（2）服务端确认双方使用的加密算法，并且给出数字证书，以及一个随机数（server random）。（服务端发送了两件东西） （服务端将自己的公钥发给数字证书认证机构，数字证书认证机构利用自己的私钥对服务器的公钥进行数字签名，并给服务器颁发公钥证书。）

（3）客户端确认数字证书有效，然后生成一个新的随机数 ，并且使用数字证书中的公钥，加密这个随机数，将其发送给服务端。（客户端发送了一个非对称加密的随机数）

（4）服务端使用自己的私钥，获取来自客户端的加密随机数（Premaster secret）。（服务端使用非对称加密算法进行解密）

（5）客户端和服务端根据约定的加密方法，使用前面的三个随机数，生成对话密钥（session key），用来加密整个会话。（服务端使用对称密钥会话）

对称加密和非对称加密？

》 DES、3DES（TripleDES）、AES、RC2、RC4、RC5和Blowfish等

》RSA、ECC（移动设备用）、Diffie-Hellman、El Gamal、DSA（数字签名用）

15.TCP头部，UDP头部比较？

（1）TCP头部至少由20个字节构成（最长60个），如下图：

（2）UDP头部由8个字节构成，如下图：

16.IP头部

17.HTTP请求，HTTP响应，字段？

（1）HTTP请求

• 请求行
  • 方法，url，协议版本
• 请求首部字段
• 空行（这一个空行一定存在）
• 内容实体

序号	方法	描述
1	GET	请求指定的页面信息，并返回实体主体。
2	HEAD	类似于 GET 请求，只不过返回的响应中没有具体的内容，用于获取报头
3	POST	向指定资源提交数据进行处理请求（例如提交表单或者上传文件）。数据被包含在请求体中。POST 请求可能会导致新的资源的建立和/或已有资源的修改。
4	PUT	从客户端向服务器传送的数据取代指定的文档的内容。
5	DELETE	请求服务器删除指定的页面。
6	CONNECT	HTTP/1.1 协议中预留给能够将连接改为管道方式的代理服务器。
7	OPTIONS	允许客户端查看服务器的性能。
8	TRACE	回显服务器收到的请求，主要用于测试或诊断。
9	PATCH	是对 PUT 方法的补充，用来对已知资源进行局部更新 。

（2）HTTP响应

• 响应行
  • 协议版本，响应状态码，原因短语
• 响应首部字段
• 空行
• 内容实体

（3）字段

• 通用头（通用头域包含请求和响应消息都支持的头域，通用头域包含缓存头部Cache-Control、Pragma及信息性头部Connection、Date、Transfer-Encoding、Update、Via）

名字	含义
Date	Date头域表示消息发送的时间，服务器响应中要包含这个头部，因为缓存在评估响应的新鲜度时要用到，其时间的描述格式由RFC822定义。例如，Date:Mon,31 Dec 2001 04:25:57 GMT。Date描述的时间表示世界标准时，换算成本地时间，需要知道用户所在的时区。
Transfer-Encoding	WEB 服务器表明自己对本响应消息体（不是消息体里面的对象）作了怎样的编码，比如是否分块（chunked），例如：Transfer-Encoding: chunked
Pragma	Pragma头域用来包含实现特定的指令，最常用的是Pragma:no-cache。在HTTP/1.1协议中，它的含义和Cache- Control:no-cache相同。
Connection	Connection表示是否需要持久连接。
Cache-Control	Cache-Control指定请求和响应遵循的缓存机制。在请求消息或响应消息中设置 Cache-Control并不会修改另一个消息处理过程中的缓存处理过程。请求时的缓存指令包括no-cache、no-store、max-age、max-stale、min-fresh、only-if-cached，响应消息中的指令包括public、private、no-cache、no-store、no-transform、must-revalidate、proxy-revalidate、max-age。
Upgrade	它可以指定另一种可能完全不同的协议，如HTTP/1.1客户端可以向服务器发送一条HTTP/1.0请求，其中包含值为“HTTP/1.1”的Update头部，这样客户端就可以测试一下服务器是否也使用HTTP/1.1了。
Via	列出从客户端到 OCS 或者相反方向的响应经过了哪些代理服务器，他们用什么协议（和版本）发送的请求。

• HTTP请求头（请求头用于说明是谁或什么在发送请求、请求源于何处，或者客户端的喜好及能力。服务器可以根据请求头部给出的客户端信息，试着为客户端提供更好的响应。）

名字	含义
Accept	告诉WEB服务器自己接受什么介质类型，/ 表示任何类型，type/* 表示该类型下的所有子类型，type/sub-type。
Accept-Charset	浏览器告诉服务器自己能接收的字符集。
Accept-Encoding	浏览器申明自己接收的编码方法，通常指定压缩方法，是否支持压缩，支持什么压缩方法（gzip，deflate）。
Accept-Language	浏览器申明自己接收的语言。语言跟字符集的区别：中文是语言，中文有多种字符集，比如big5，gb2312，gbk等等。
Authorization	当客户端接收到来自WEB服务器的 WWW-Authenticate 响应时，用该头部来回应自己的身份验证信息给WEB服务器。
If-Match	如果对象的 ETag 没有改变，其实也就意味著对象没有改变，才执行请求的动作，获取文档。
If-None-Match	如果对象的 ETag 改变了，其实也就意味著对象也改变了，才执行请求的动作，获取文档。
If-Modified-Since	如果请求的对象在该头部指定的时间之后修改了，才执行请求的动作（比如返回对象），否则返回代码304，告诉浏览器该对象没有修改。例如：If-Modified-Since：Thu, 10 Apr 2008 09:14:42 GMT
If-Unmodified-Since	如果请求的对象在该头部指定的时间之后没修改过，才执行请求的动作（比如返回对象）。
If-Range	浏览器告诉 WEB 服务器，如果我请求的对象没有改变，就把我缺少的部分给我，如果对象改变了，就把整个对象给我。浏览器通过发送请求对象的ETag 或者自己所知道的最后修改时间给 WEB 服务器，让其判断对象是否改变了。总是跟 Range 头部一起使用。
Range	浏览器（比如 Flashget 多线程下载时）告诉 WEB 服务器自己想取对象的哪部分。例如：Range: bytes=1173546
Proxy-Authenticate	代理服务器响应浏览器，要求其提供代理身份验证信息。
Proxy-Authorization	浏览器响应代理服务器的身份验证请求，提供自己的身份信息。
Host	客户端指定自己想访问的WEB服务器的域名/IP 地址和端口号。如Host：rss.sina.com.cn
Referer	浏览器向WEB 服务器表明自己是从哪个网页URL获得点击当前请求中的网址/URL，例如：Referer：http://www.jb51.net
User-Agent	浏览器表明自己的身份（是哪种浏览器）。例如：User-Agent：Mozilla/5.0 (Windows; U; Windows NT 5.1; zh-CN;rv:1.8.1.14) Gecko/20080404 Firefox/2.0.0.14

• HTTP响应头（响应头向客户端提供一些额外信息，比如谁在发送响应、响应者的功能，甚至与响应相关的一些特殊指令。这些头部有助于客户端处理响应，并在将来发起更好的请求。）

名字	含义
Age	当代理服务器用自己缓存的实体去响应请求时，用该头部表明该实体从产生到现在经过多长时间了。
Server	WEB 服务器表明自己是什么软件及版本等信息。例如：Server：Apache/2.0.61 (Unix)
Accept-Ranges	WEB服务器表明自己是否接受获取其某个实体的一部分（比如文件的一部分）的请求。bytes：表示接受，none：表示不接受。
Vary	WEB服务器用该头部的内容告诉 Cache 服务器，在什么条件下才能用本响应所返回的对象响应后续的请求。假如源WEB服务器在接到第一个请求消息时，其响应消息的头部为：Content-Encoding:gzip; Vary: Content-Encoding，那么Cache服务器会分析后续请求消息的头部，检查其Accept-Encoding，是否跟先前响应的Vary头部值一致，即是否使用相同的内容编码方法，这样就可以防止Cache服务器用自己Cache里面压缩后的实体响应给不具备解压能力的浏览器。例如：Vary：Accept-Encoding。

• HTTP实体头部（实体头部提供了有关实体及其内容的大量信息，从有关对象类型的信息，到能够对资源使用的各种有效的请求方法。总之，实体头部可以告知接收者它在对什么进行处理。请求消息和响应消息都可以包含实体信息，实体信息一般由实体头域和实体组成。实体头域包含关于实体的原信息，实体头包括信息性头部Allow、Location，内容头部Content-Base、Content-Encoding、Content-Language、Content-Length、Content-Location、Content-MD5、Content-Range、Content-Type，缓存头部Etag、Expires、Last-Modified、extension-header。）

名字	含义
Allow	服务器支持哪些请求方法（如GET、POST等）。
Location	表示客户应当到哪里去提取文档，用于将接收端定位到资源的位置（URL）上。Location通常不是直接设置的，而是通过HttpServletResponse的sendRedirect方法，该方法同时设置状态代码为302。
Content-Base	解析主体中的相对URL时使用的基础URL。
Content-Encoding	WEB服务器表明自己使用了什么压缩方法（gzip，deflate）压缩响应中的对象。例如：Content-Encoding：gzip
Content-Language	WEB 服务器告诉浏览器理解主体时最适宜使用的自然语言。
Content-Length	WEB服务器告诉浏览器自己响应的对象的长度或尺寸，例如：Content-Length: 26012
Content-Location	资源实际所处的位置。
Content-MD5	主体的MD5校验和。
Content-Range	实体头用于指定整个实体中的一部分的插入位置，他也指示了整个实体的长度。在服务器向客户返回一个部分响应，它必须描述响应覆盖的范围和整个实体长度。一般格式：Content-Range:bytes-unitSPfirst-byte-pos-last-byte-pos/entity-legth。例如，传送头500个字节次字段的形式：Content-Range:bytes0-499/1234如果一个http消息包含此节（例如，对范围请求的响应或对一系列范围的重叠请求），Content-Range表示传送的范围，Content-Length表示实际传送的字节数。
Content-Type	WEB 服务器告诉浏览器自己响应的对象的类型。例如：Content-Type：application/xml
Etag	就是一个对象（比如URL）的标志值，就一个对象而言，比如一个html文件，如果被修改了，其Etag也会别修改，所以，ETag的作用跟Last-Modified的作用差不多，主要供WEB服务器判断一个对象是否改变了。比如前一次请求某个html文件时，获得了其 ETag，当这次又请求这个文件时，浏览器就会把先前获得ETag值发送给WEB服务器，然后WEB服务器会把这个ETag跟该文件的当前ETag进行对比，然后就知道这个文件有没有改变了。
Expires	WEB服务器表明该实体将在什么时候过期，对于过期了的对象，只有在跟WEB服务器验证了其有效性后，才能用来响应客户请求。是 HTTP/1.0 的头部。例如：Expires：Sat, 23 May 2009 10:02:12 GMT
Last-Modified	WEB服务器认为对象的最后修改时间，比如文件的最后修改时间，动态页面的最后产生时间等等。例如：Last-Modified：Tue, 06 May 2008 02:42:43 GMT

18.HTTP1.0，HTTP1.1，HTTP2.0之间的区别？

（1）HTTP1.0：

• 无法复用连接
• 对头阻塞（head of line blocking）:对于同一个tcp连接，所有的http1.0请求放入队列中，只有前一个请求的响应收到了，然后才能发送下一个请求。可见，http1.0的队首组塞发生在客户端。

（2）HTTP1.1：

• 长连接（在头部加入了connection：keep-alive）
• 管道化（将请求队列移动到服务端队列）HTTP/1.1通过pipelining管道技术实现一次性发送多个请求，以期提高吞吐和性能,可见，http1.1的队首阻塞发生在服务器端。
• 缓存机制（引入了新的字段cache-control，支持断点重传）
• 增加了host字段（使得一个服务器可创建多个站点）

(3）HTTP2.0：

• 二进制分帧
• 多路复用（消息由一个帧或者多个帧组成，可以乱序进行发送，之后使用帧的stream id进行重组，二进制分帧使得多路复用成为可能，多路复用实现真正的并发）
• 头部压缩，通信双方保存header filed表
• 服务器推送（不用客户端进行明确请求）

（4）最新的HTTP版本？

https://developer.mozilla.org/en-US/docs/Web/HTTP/Basics_of_HTTP/Evolution_of_HTTP

• Post-HTTP/2 evolution
• HTTP/3 - HTTP over QUIC

（5）在应用中如何配置HTTP版本？

> # For HTTP, the proxy_http_version directive should be set to “1.1” and the “Connection” header field should be cleared:
> upstream http_backend {
>     server 127.0.0.1:8080;
> 
>     keepalive 16;
> }
> 
> server {
>     ...
> 
>     location /http/ {
>         proxy_pass http://http_backend;
>         proxy_http_version 1.1;
>         proxy_set_header Connection "";
>         ...
>     }
> }
>

>

新HTTP1.0与HTTP1.1区别：

HTTP1.0最早在网页中使用是在1996年，那个时候只是使用一些较为简单的网页上和网络请求上，而HTTP1.1则在1999年才开始广泛应用于现在的各大浏览器网络请求中，同时HTTP1.1也是当前使用最为广泛的HTTP协议。 主要区别主要体现在：

• 缓存处理，在HTTP1.0中主要使用header里的If-Modified-Since,Expires来做为缓存判断的标准，HTTP1.1则引入了更多的缓存控制策略例如Entity tag，If-Unmodified-Since, If-Match, If-None-Match等更多可供选择的缓存头来控制缓存策略。
• 带宽优化及网络连接的使用，HTTP1.0中，存在一些浪费带宽的现象，例如客户端只是需要某个对象的一部分，而服务器却将整个对象送过来了，并且不支持断点续传功能，HTTP1.1则在请求头引入了range头域，它允许只请求资源的某个部分，即返回码是206（Partial Content），这样就方便了开发者自由的选择以便于充分利用带宽和连接。
• 错误通知的管理，在HTTP1.1中新增了24个错误状态响应码，如409（Conflict）表示请求的资源与资源的当前状态发生冲突；410（Gone）表示服务器上的某个资源被永久性的删除。
• Host头处理，在HTTP1.0中认为每台服务器都绑定一个唯一的IP地址，因此，请求消息中的URL并没有传递主机名（hostname）。但随着虚拟主机技术的发展，在一台物理服务器上可以存在多个虚拟主机（Multi-homed Web Servers），并且它们共享一个IP地址。HTTP1.1的请求消息和响应消息都应支持Host头域，且请求消息中如果没有Host头域会报告一个错误（400 Bad Request）。
• 长连接、持续连接，HTTP 1.1支持长连接（PersistentConnection）和请求的流水线（Pipelining）处理，在一个TCP连接上可以传送多个HTTP请求和响应，减少了建立和关闭连接的消耗和延迟，在HTTP1.1中默认开启Connection： keep-alive，一定程度上弥补了HTTP1.0每次请求都要创建连接的缺点。

HTTP1.1与HTTP2.0的区别：

• 新的二进制格式（Binary Format），HTTP1.x的解析是基于文本。基于文本协议的格式解析存在天然缺陷，文本的表现形式有多样性，要做到健壮性考虑的场景必然很多，二进制则不同，只认0和1的组合。基于这种考虑HTTP2.0的协议解析决定采用二进制格式，实现方便且健壮。
• 多路复用（MultiPlexing），即连接共享，即每一个request都是是用作连接共享机制的。一个request对应一个id，这样一个连接上可以有多个request，每个连接的request可以随机的混杂在一起，接收方可以根据request的 id将request再归属到各自不同的服务端请求里面。
• header压缩，如上文中所言，对前面提到过HTTP1.x的header带有大量信息，而且每次都要重复发送，HTTP2.0使用encoder来减少需要传输的header大小，通讯双方各自cache一份header fields表，既避免了重复header的传输，又减小了需要传输的大小。
• 服务端推送（server push），同SPDY一样，HTTP2.0也具有server push功能

19.cookie和session的区别？

说先说一下为什么需要cookie和session？

（1）cookie数据存放在客户的浏览器上，session存放在服务器上。

（2）cookie不是安全的，别人可以分析存放在本地的cookie进行cookie欺骗。

（3）session会一定时间内存放在服务器上，当访问次数增多的时候，会影响性能。

（4）单个cookie保存的数据不会超过4K，很多浏览器限制一个站点的cookie数目不超过20个。

20.状态码？

（1）概括：

	类别	原因短语
1XX	Informational（信息状态码）	接收的请求正在处理
2XX	Success（成功状态码）	请求正常处理完毕
3XX	Redirection（重定向状态码）	需要进行附加操作以完成请求
4XX	Client Error（客户端错误状态码）	服务器无法处理请求
5XX	Server Error（服务器错误状态码）	服务器处理请求出错

（2）细节

状态码	状态码英文名称	中文描述
100	Continue	继续。客户端应继续其请求
101	Switching Protocols	切换协议。服务器根据客户端的请求切换协议。只能切换到更高级的协议，例如，切换到HTTP的新版本协议
200	OK	请求成功。一般用于GET与POST请求
201	Created	已创建。成功请求并创建了新的资源
202	Accepted	已接受。已经接受请求，但未处理完成
203	Non-Authoritative Information	非授权信息。请求成功。但返回的meta信息不在原始的服务器，而是一个副本
204	No Content	无内容。服务器成功处理，但未返回内容。在未更新网页的情况下，可确保浏览器继续显示当前文档
205	Reset Content	重置内容。服务器处理成功，用户终端（例如：浏览器）应重置文档视图。可通过此返回码清除浏览器的表单域
206	Partial Content	部分内容。服务器成功处理了部分GET请求
300	Multiple Choices	多种选择。请求的资源可包括多个位置，相应可返回一个资源特征与地址的列表用于用户终端（例如：浏览器）选择
301	Moved Permanently	永久移动。请求的资源已被永久的移动到新URI，返回信息会包括新的URI，浏览器会自动定向到新URI。今后任何新的请求都应使用新的URI代替
302	Found	临时移动。与301类似。但资源只是临时被移动。客户端应继续使用原有URI
303	See Other	查看其它地址。与301类似。使用GET和POST请求查看
304	Not Modified	未修改。所请求的资源未修改，服务器返回此状态码时，不会返回任何资源。客户端通常会缓存访问过的资源，通过提供一个头信息指出客户端希望只返回在指定日期之后修改的资源
305	Use Proxy	使用代理。所请求的资源必须通过代理访问
306	Unused	已经被废弃的HTTP状态码
307	Temporary Redirect	临时重定向。与302类似。使用GET请求重定向
400	Bad Request	客户端请求的语法错误，服务器无法理解
401	Unauthorized	请求要求用户的身份认证
402	Payment Required	保留，将来使用
403	Forbidden	服务器理解请求客户端的请求，但是拒绝执行此请求
404	Not Found	服务器无法根据客户端的请求找到资源（网页）。通过此代码，网站设计人员可设置”您所请求的资源无法找到”的个性页面
405	Method Not Allowed	客户端请求中的方法被禁止
406	Not Acceptable	服务器无法根据客户端请求的内容特性完成请求
407	Proxy Authentication Required	请求要求代理的身份认证，与401类似，但请求者应当使用代理进行授权
408	Request Time-out	服务器等待客户端发送的请求时间过长，超时
409	Conflict	服务器完成客户端的 PUT 请求时可能返回此代码，服务器处理请求时发生了冲突
410	Gone	客户端请求的资源已经不存在。410不同于404，如果资源以前有现在被永久删除了可使用410代码，网站设计人员可通过301代码指定资源的新位置
411	Length Required	服务器无法处理客户端发送的不带Content-Length的请求信息
412	Precondition Failed	客户端请求信息的先决条件错误
413	Request Entity Too Large	由于请求的实体过大，服务器无法处理，因此拒绝请求。为防止客户端的连续请求，服务器可能会关闭连接。如果只是服务器暂时无法处理，则会包含一个Retry-After的响应信息
414	Request-URI Too Large	请求的URI过长（URI通常为网址），服务器无法处理
415	Unsupported Media Type	服务器无法处理请求附带的媒体格式
416	Requested range not satisfiable	客户端请求的范围无效
417	Expectation Failed	服务器无法满足Expect的请求头信息
500	Internal Server Error	服务器内部错误，无法完成请求
501	Not Implemented	服务器不支持请求的功能，无法完成请求
502	Bad Gateway	作为网关或者代理工作的服务器尝试执行请求时，从远程服务器接收到了一个无效的响应
503	Service Unavailable	由于超载或系统维护，服务器暂时的无法处理客户端的请求。延时的长度可包含在服务器的Retry-After头信息中
504	Gateway Time-out	充当网关或代理的服务器，未及时从远端服务器获取请求
505	HTTP Version not supported	服务器不支持请求的HTTP协议的版本，无法完成处理

1XX——表示通知信息，如请求收到了或正在进行处理

2XX——表明请求被正常处理了

• 200 OK：请求已正常处理。
• 204 No Content：请求处理成功，但没有任何资源可以返回给客户端，一般在只需要从客户端往服务器发送信息，而对客户端不需要发送新信息内容的情况下使用。
• 206 Partial Content：是对资源某一部分的请求，该状态码表示客户端进行了范围请求，而服务器成功执行了这部分的GET请求。响应报文中包含由Content-Range指定范围的实体内容。

3XX——表明浏览器需要执行某些特殊的处理以正确处理请求

• 301 Moved Permanently：资源的uri已更新，你也更新下你的书签引用吧。永久性重定向，请求的资源已经被分配了新的URI，以后应使用资源现在所指的URI。
• 302 Found：资源的URI已临时定位到其他位置了，姑且算你已经知道了这个情况了。临时性重定向。和301相似，但302代表的资源不是永久性移动，只是临时性性质的。换句话说，已移动的资源对应的URI将来还有可能发生改变。
• 303 See Other：资源的URI已更新，你是否能临时按新的URI访问。该状态码表示由于请求对应的资源存在着另一个URL，应使用GET方法定向获取请求的资源。303状态码和302状态码有着相同的功能，但303状态码明确表示客户端应当采用GET方法获取资源，这点与302状态码有区别。当301,302,303响应状态码返回时，几乎所有的浏览器都会把POST改成GET，并删除请求报文内的主体，之后请求会自动再次发送。
• 304 Not Modified：资源已找到，但未符合条件请求。该状态码表示客户端发送附带条件的请求时（采用GET方法的请求报文中包含If-Match，If-Modified-Since，If-None-Match，If-Range，If-Unmodified-Since中任一首部）服务端允许请求访问资源，但因发生请求未满足条件的情况后，直接返回304。
• 307 Temporary Redirect：临时重定向。与302有相同的含义。

4XX——表明客户端是发生错误的原因所在。

• 400 Bad Request：服务器端无法理解客户端发送的请求，请求报文中可能存在语法错误。
• 401 Unauthorized：该状态码表示发送的请求需要有通过HTTP认证（BASIC认证，DIGEST认证）的认证信息。
• 403 Forbidden：不允许访问那个资源。该状态码表明对请求资源的访问被服务器拒绝了。（权限，未授权IP等）
• 404 Not Found：服务器上没有请求的资源。路径错误等。

5XX——服务器本身发生错误

• 500 Internal Server Error：貌似内部资源出故障了。该状态码表明服务器端在执行请求时发生了错误。也有可能是web应用存在bug或某些临时故障。
• 503 Service Unavailable：抱歉，我现在正在忙着。该状态码表明服务器暂时处于超负载或正在停机维护，现在无法处理请求。

21.TCP是如何实现面向连接的？面向连接和非面向连接的区别？

（1）状态和序列号，以及错误校验。描述TCP和UDP头之间的差异！

22.TCP的拥塞控制？（重传就可能导致拥塞）

TCP通过慢启动、拥塞避免、快重传以及快恢复这四个算法来进行拥塞控制（使用滑动窗口进行流量控制）：

• 慢启动：一开始先设置一个比较小的拥塞窗口值cwnd（报文段的倍数），然后进行数据传输，每收到一个报文段的确认，我们就将cwnd+1，这样下来，cwnd总体上是乘以2^n的倍数增长。（慢启动非增长速度慢，只是增长的初始基数比较小）
• 拥塞避免： 因为慢启动算法的增长比较快，当cwnd = ssthresh（预先设置好的门限值）时，我们启动拥塞避免算法，窗口值开始线性增长。

随着拥塞避免算法的进行，网络出现超时的情况（这时判断为拥塞出现）。这时将cwnd降为一开始的值，重新进行慢开始-拥塞避免，并且此时的门限值设为出现拥塞时的cwnd的一半。

• 快重传： 快重传的目的是为了让发送方尽早知道某个报文段的丢失。如何知道呢？当我们重复收到某一个报文段的3次确认时，我们就可以判断，它的下一个报文段可能出现了丢失。这时我们启动快重传算法，立即重传丢失的报文段。
• 快恢复： 上面快重传算法的启动只是因为个别报文段的丢失，我们这时并不判断为网络拥塞，而是启动快恢复算法。我们将cwnd=ssthresh=当前cwnd的一半，并且开始拥塞避免算法。

当然，也有的快恢复算法是将当前拥塞窗口再增大3个报文段的值，因为既然收到了3个重复的ACK，则说明有三个分组已经离开了网络，不在占用网络资源而是停留在对方缓存当中，可以适当将窗口值增大。

23.TCP的流量控制？

滑动窗口协议

24.重传算法？

SACK方法

• 为了解决快速重传的缺点，一种更好的SACK重传策略被提出
• 基于快速重传，同时在tcp头里加了一个SACK的东西
• 解决了什么问题：客户端应该发送哪些超时包的问题

25.路由算法？

（1）路由：找到任意两个节点之间开销最小的路径。

（2）距离向量，链路状态

• 距离向量：网络中没有任何一个节点知道整张表的信息，自己只知道它自己的路由表的内容。好处：所有的节点在没有任何集中授权的额情况下取得网络的一致视图。（RIP协议）
• 链路状态：每一个节点都有足够的信息构建完整的网络映象。（OSPF协议，开放最短路径优先），路由的计算采用迪杰特斯拉算法进行计算。

26.IP数据报格式？

27.ABC类地址

• A、B、C类IP地址的网络号字段分别是1、2、3个字节长，而在网络号的1-3位是类别位，分别是：0、10、110。
• A、B、C类IP地址的主机号字段分别为3、2、1个字节。
• A、B、C类IP地址是单播地址，D类IP地址（前四位为1110）为多播地址，E类IP地址（前四位1111）保留为以后使用。
• A类地址的网络号中：全0和127是不指派的；主机号中：全0代表本主机所连接的单个网络地址，全1代表网络上的所有主机，也是不指派的。
• B类IP地址网络号中：128.0.0.0不指派；主机号中：全0和全1也不指派。
• C类IP地址网络号中：192.0.0.0不指派；主机号中：全0和全1也不指派。

28.端口号

应用程序	FTP	TELNET	SMTP	DNS	TFTP	HTTP	SNMP	SNMP(trap)	HTTPS
熟知端口号	21	23	25	53	69	80	161	162	443

29.滑动窗口（解决的是速率不匹配问题）

• 解决了什么问题：发送方和接收方速率不匹配时，保证可靠传输和包乱序的问题
• 机制：接收方根据目前缓冲区大小，通知发送方目前能接收的最大值。发送方根据接收方的处理能力来发送数据。通过这种协调机制，防止接收端处理不过来。
• 窗口大小：接收方发给发送端的这个值称为窗口大小

30.拥塞窗口（控制的是发送方）

• 解决什么问题：发送方发送速度过快，导致中转路由器拥堵的问题
• 机制：发送方增加一个拥塞窗口（cwnd），每次受到ack，窗口值加1。发送时，取拥塞窗口和接收方发来的窗口大小取最小值发送
• 起到发送方流量控制的作用

31.细节

• MIME (Multipurpose Internet Mail Extensions) 是描述消息内容类型的因特网标准。
• Request For Comments（RFC），是一系列以编号排定的文件。文件收集了有关互联网相关信息，以及UNIX和互联网社区的软件文件。
• RIP使用UDP，OSPF使用IP,而BGP使用TCP。(R—-U,O—-I,B—-P)
  • OSPF本身提供主从协商机制，可以保证可靠的传输，另外全网路由器保持着同样的一个LSDB（链路状态数据库），当拓扑发生变化时，需要携带的变更信息较少，
  • 通过IP协议即可完成RIP协议采用UDP是因为RIP每周期需全网组播路由信息，路由信息数目较大，故使用UDP协议可以提高效率
  • BGP为边界网关协议，因携带的路由信息较多，且可能跨不同网络传送路由信息，为保证可靠性，需使用TCP协议，可兼顾容量和可靠性

32.HTTP和HTTPS的区别？

证书机构： 阿里巴巴

(1) https协议需要到CA申请证书，一般免费证书较少，因而需要一定费用。(原来网易官网是http，而网易邮箱是https。)

(2) http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。

(3) http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。

33.同源策略？

URL	结果	原因
http://store.company.com/dir2/other.html	成功	只有路径不同
http://store.company.com/dir/inner/another.html	成功	只有路径不同
https://store.company.com/secure.html	失败	不同协议 ( https和http )
http://store.company.com:81/dir/etc.html	失败	不同端口 ( http:// 80是默认的)
http://news.company.com/dir/other.html	失败	不同域名 ( news和store )

34.跨域问题？

同源策略限制了从同一个源加载的文档或脚本如何与来自另一个源的资源进行交互。这是一个用于隔离潜在恶意文件的重要安全机制。

CSRF（Cross-site request forgery），中文名称：跨站请求伪造，也被称为：one click attack/session riding，缩写为：CSRF/XSRF。

　　1.你不能保证你登录了一个网站后，不再打开一个tab页面并访问另外的网站。

　　2.你不能保证你关闭浏览器了后，你本地的Cookie立刻过期，你上次的会话已经结束。（事实上，关闭浏览器不能结束一个会话，但大多数人都会错误的认为关闭浏览器就等于退出登录/结束会话了……）

　　3.上图中所谓的攻击网站，可能是一个存在其他漏洞的可信任的经常被人访问的网站。

CORS是一个W3C标准，全称是”跨域资源共享”（Cross-origin resource sharing）

35. websocket和SSE的区别？

36. epoll

• epoll_create
• epoll_ctl
• epoll_wait

37. cacheline，MESI

4kb

64bytes

二、操作系统

（一）基础

1.原码、补码、反码

• 原码：原码用第一位表示符号, 其余位表示值. 比如如果是8位二进制
• 补码
  • 正数：正数的补码就是其本身
  • 负数：负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1。 (即在反码的基础上+1)
  • 为什么要用补码？
    • 原因很简单，如果使用补码表示负整数，那么ALU在做整数之间的操作时，就不用区分符号了，所有位都会参与运算，其上上面的例子中，符号位都参与了运算。
• 反码
  • 正数：正数的反码是其本身
  • 负数：负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.

2.fork函数

int main(){fork()||fork();}共创建几个进程：3

fork()给子进程返回一个零值，而给父进程返回一个非零值；

在main这个主进程中，首先执行 fork() || fork(), 左边的fork()返回一个非零值，根据||的短路原则，前面的表达式为真时，后面的表达式不执行，故包含main的这个主进程创建了一个子进程，

由于子进程会复制父进程，而且子进程会根据其返回值继续执行，就是说，在子进程中， fork() ||fork()这条语句左边表达式的返回值是0, 所以||右边的表达式要执行，这时在子进程中又创建了一个进程， 即main进程->子进程->子进程，一共创建了3个进程。

（二）并发

1.进程、线程、管程、协程？

（1）线程和进程(Thread & Process)

线程是程序执行的一条路径，在多线程的OS中，线程是调度和分配的基本单位，而进程是拥有资源的基本单位。结合Java的内存区域（线程共享和线程私有）。

package JavaDemo.MultiThreadTest;

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;

/**
 * @Author MaoTian
 * @Classname MultiThread
 * @Description 查看有哪些线程
 *
 * [5] Monitor Ctrl-Break
 * [4] Signal Dispatcher
 * [3] Finalizer
 * [2] Reference Handler
 * [1] main
 *
 * @Date 下午9:23 2019/8/13
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */
public class MultiThread {
    public static void main(String[] args) {
        ThreadMXBean threadMXBean= ManagementFactory.getThreadMXBean();
        ThreadInfo[] threadInfos=threadMXBean.dumpAllThreads(false,false);
        for (ThreadInfo threadInfo:threadInfos){
            System.out.println("[" + threadInfo.getThreadId() + "] " + threadInfo.getThreadName());
        }
    }
}

（2）线程的属性

• 轻型实体：线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证独立运行的资源。线程的实体包括程序、数据和TCB。线程是动态概念，它的动态特性由线程控制块TCB（Thread Control Block）描述。TCB包括以下信息：
• 线程状态。
  • 当线程不运行时，被保存的现场资源。
  • 一组执行堆栈。
  • 存放每个线程的局部变量主存区。
  • 访问同一个进程中的主存和其它资源。

用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。

• 独立调度和分派的基本单位：在多线程OS中，线程是能独立运行的基本单位，因而也是独立调度和分派的基本单位。由于线程很“轻”，故线程的切换非常迅速且开销小（在同一进程中的）。
• 可并发执行：在一个进程中的多个线程之间，可以并发执行，甚至允许在一个进程中所有线程都能并发执行；同样，不同进程中的线程也能并发执行，充分利用和发挥了处理机与外围设备并行工作的能力。
• 共享进程资源：在同一进程中的各个线程，都可以共享该进程所拥有的资源，这首先表现在：所有线程都具有相同的地址空间（进程的地址空间），这意味着，线程可以访问该地址空间的每一个虚地址；此外，还可以访问进程所拥有的已打开文件、定时器、信号量机构等。由于同一个进程内的线程共享内存和文件，所以线程之间互相通信不必调用内核。

（3）管程

（4）协程

协程：协程，英文Coroutines，是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。最重要的是，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。（线程内核管理，协程自己控制切换，用户态和内核态切换，比线程切换代价更小）

2.进程之间的通信？（套共消，管信信）

（1）套接字

（2）共享内存

（3）消息队列

（4）管程

（5）信号

（6）信号量

信号量

是一个确定的二元组（s，q），其中s是一个具有非负初值的整形变量，q是一个初始状态为空的队列，整形变量s表示系统中某类资源的数目：

• 当其值 >= 0 时，表示系统中当前可用资源的数目
• 当其值 < 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目

除信号量的初值外，信号量的值仅能由P操作和V操作更改，操作系统利用它的状态对进程和资源进行管理

P操作

P操作记为P(s)，其中s为一信号量，它执行时主要完成以下动作：

>s.value = s.value - 1；  /*可理解为占用1个资源，若原来就没有则记帐“欠”1个*/
>

若s.value ≥ 0，则进程继续执行，否则（即s.value < 0），则进程被阻塞，并将该进程插入到信号量s的等待队列s.queue中

实际上，P操作可以理解为分配资源的计数器，或是使进程处于等待状态的控制指令

V操作

V操作记为V(s)，其中s为一信号量，它执行时，主要完成以下动作：

>s.value = s.value + 1；/*可理解为归还1个资源，若原来就没有则意义是用此资源还1个欠帐*/
>

若s.value > 0，则进程继续执行，否则（即s.value ≤ 0），则从信号量s的等待队s.queue中移出第一个进程，使其变为就绪状态，然后返回原进程继续执行

实际上，V操作可以理解为归还资源的计数器，或是唤醒进程使其处于就绪状态的控制指令

3.信号和信号量之间的区别？

• 信号量：（Semaphore）进程间通信处理同步互斥的机制。是在多线程环境下使用的一种设施, 它负责协调各个线程, 以保证它们能够正确、合理的使用公共资源。（特点，pv操作，用于同步进程）

  若信号S的初值为2，当前值为－1，则表示有（B　）个等待进程。

  A.0 B.1 C.2 D.3

  2代表有两个资源空闲,负数的绝对值表示在等待的进程数量

• 信号：（signal）是一种处理异步事件的方式。信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程外，还可以发送信号给进程本身。（特点，通知）

4.线程之间的通信？

（1）锁机制

• 互斥锁：提供了以排它方式阻止数据结构被并发修改的方法。
• 读写锁：允许多个线程同时读共享数据，而对写操作互斥。
• 条件变量：可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

（2）信号量机制

（3）信号机制

5.死锁产生的条件？

（1）互斥

（2）请求与保持:指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

（3）循环等待（解决：按照顺序来申请和释放资源）

（4）不可剥夺（解决：主动释放）

6.死锁的解除和预防的方法？

• 死锁避免:银行家算法

我们只要破坏产生死锁的四个条件中的其中一个就可以了。

• 破坏互斥条件

这个条件我们没有办法破坏，因为我们用锁本来就是想让他们互斥的（临界资源需要互斥访问）。

• 破坏请求与保持条件

一次性申请所有的资源。

• 破坏不剥夺条件

占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。

• 破坏循环等待条件

靠按序申请资源来预防。按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件。

7.调度

（1）调度策略

• 响应时间：从用户输入到产生反应的时间
• 周转时间：从任务开始到任务结束的时间
• 平均周转时间：周转总时间除以作业个数

（2）调度算法(8种)

• 1 FCFS：调度的顺序就是任务到达就绪队列的顺序。对短作业不公平。

  公平、简单(FIFO队列)、非抢占、不适合交互式。未考虑任务特性，平均等待时间可以缩短

• 2 SJF：最短的作业(CPU区间长度最小)最先调度。

  可以证明，SJF可以保证最小的平均等待时间。

• [3] SRJF：SJF的可抢占版本，比SJF更有优势。

SJF(SRJF): 如何知道下一CPU区间大小？根据历史进行预测: 指数平均法。

• [4] HRN：最高响应比优先法，是FCFS和SJF的综合平衡，响应比R定义如下： R =(W+T)/T 。

• [5] 优先权调度：每个任务关联一个优先权，调度优先权最高的任务。

  注意：优先权太低的任务一直就绪，得不到运行，出现“饥饿”现象。

  FCFS是RR的特例，SJF是优先权调度的特例。这些调度算法都不适合于交互式系统。

• [6] Round-Robin(RR)：设置一个时间片，按时间片来轮转调度

  优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；

  时间片太大，响应时间太长；吞吐量变小，周转时间变长；当时间片过长时，退化为FCFS。

• [7] 多级队列调度

  • 按照一定的规则建立多个进程队列
  • 不同的队列有固定的优先级（高优先级有抢占权）
  • 不同的队列可以给不同的时间片和采用不同的调度方法

  存在问题1：没法区分I/O bound和CPU bound；

  存在问题2：也存在一定程度的“饥饿”现象；

• [8] 多级反馈队列：在多级队列的基础上，任务可以在队列之间移动，更细致的区分任务。可以根据“享用”CPU时间多少来移动队列，阻止“饥饿”。

  最通用的调度算法，多数OS都使用该方法或其变形，如UNIX、Windows等。

####

8.锁，死锁怎么检查？

• 锁的类型

（1）互斥锁

同一时间只能有一个线程访问加锁的数据。

（2）自旋锁

互斥锁的一种实现，如果自旋锁已经被别的执行单元保持，调用者就一直 循环等待 是否该自旋锁的保持者已经释放了锁。

（3）读写锁

一种特殊的自旋锁，它把对共享资源的访问者划分成读者和写者，读者只对共享资源进行读访问，写者则需要对共享资源进行写操作。写者是排他性的，一个读写锁同时只能有一个写者或多个读者（与CPU数相关），但不能同时既有读者又有写者。

（4）阻塞锁

与自旋锁不同，改变了线程的运行状态。让线程进入阻塞状态进行等待，当获得相应的信号（唤醒，时间） 时，才可以进入线程的准备就绪状态，准备就绪状态的所有线程，通过竞争，进入运行状态。

在Java中synchronized,ReentrantLock,Object.wait() / notify()都属于阻塞锁。

（5）可重入锁

也叫做递归锁，指的是同一线程上该锁是可重入的，对于不同线程则相当于普通的互斥锁。

（6）公平锁

加锁前检查是否有排队等待的线程，优先排队等待的线程，先来先得。

（7）非公平锁

加锁时不考虑排队等待问题，直接尝试获取锁，获取不到自动到队尾等待。ReentrantLock中的lock()默认就是非公平锁。

（8）悲观锁

假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。加锁的时间可能会很长，也就是说悲观锁的并发访问性不好。

（9）乐观锁

假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。乐观锁不能解决脏读的问题，可以通过添加时间戳和版本来来解决。

• 死锁的检查

https://blog.csdn.net/weixin_28760063/article/details/81266578

• Jconsole
• Jstack

9.CAS

比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

在使用上，通常会记录下某块内存中的旧值，通过对旧值进行一系列的操作后得到新值，然后通过CAS操作将新值与旧值进行交换。如果这块内存的值在这期间内没被修改过，则旧值会与内存中的数据相同，这时CAS操作将会成功执行使内存中的数据变为新值。如果内存中的值在这期间内被修改过，则一般来说旧值会与内存中的数据不同，这时CAS操作将会失败，新值将不会被写入内存。

在Java中，锁在并发中占据了一席之地，但是使用锁的一个问题是：当一个线程没有获取到锁的时候就会被挂起，这将导致线程的上下文切换和重新调度的开销。

10.临界区

进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。

11.yield方法，join方法

• yield方法

而当一个线程调用了 Thread 类的静态方法 yield 时，是在告诉线程调度器自己占有的时间片中还没有使用完的部分自己不想使用了，这暗示线程调度器现在就可以进行下一轮的线程调度 。

• join方法

t.join()方法阻塞调用此方法的线程(calling thread)进入 TIMED_WAITING 状态，直到线程t完成，此线程再继续；

通常用于在main()主线程内，等待其它线程完成再结束main()主线程。

>public class JoinTester01 implements Runnable {
> 
> private String name;
> 
>public JoinTester01(String name) {
> this.name = name;
>}
> 
>public void run() {
> System.out.printf("%s begins: %s\n", name, new Date());
>try {
> TimeUnit.SECONDS.sleep(4);
>} catch (InterruptedException e) {
> e.printStackTrace();
>}
> System.out.printf("%s has finished: %s\n", name, new Date());
> }
> 
> public static void main(String[] args) {
> Thread thread1 = new Thread(new JoinTester01("One"));
> Thread thread2 = new Thread(new JoinTester01("Two"));
> thread1.start();
> thread2.start();
> 
> try {
> thread1.join();
> thread2.join();
>   } catch (InterruptedException e) {
> // TODO Auto-generated catch block
>   e.printStackTrace();
> }
> System.out.println("Main thread is finished");
> }
> }
>

12.一般在什么时候使用volatile？

写入的变量不依赖当前的值的时候。因为依赖当前值的话，将会是获取—-计算—-写入三步操作，这三步操作不是原子性的，volatile不保证原子性。

13.Linux内核select poll epoll？

14.周转时间

=作业完成时间减去作业到达时间

15.响应比

=（作业等待时间+作业执行时间）/作业执行时间

关于平均周转时间的一些题目

（１）设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？

答：周转时间=作业完成时间减去作业到达时间

所以

A　完成时间　０＋３＝３　周转时间Ａ＝３－０；

B　完成时间　３＋６＝９　周转时间Ｂ＝９－２＝７；

C　完成时间　９＋４＝１３　周转时间Ｃ＝１３－４＝９；

D　完成时间　１３＋５＝１８　周转时间Ｄ＝１８－６＝１２；

E　完成时间　１８＋２＝２０　周转时间　Ｅ＝２０－８＝１２；

所以平均周转时间是　（３＋７＋９＋１２＋１２）／５＝８.６

（２）单道批处理系统有４个作业，J1 的提交时间为8 运行时间2， J2的提交时间8.6 运行时间0.6 ，J3的提交时间8.8 运行时间0.2 J4的提交时间9.0 运行时间0.5 在采用响应比优先调度算法时，其平均周转时间是？

响应比=（作业等待时间+作业执行时间）/ 作业执行时间

J1 周转时间(8+2) -8 =2；

此时

J2等待时间为(8+2-8.6)=1.4 响应比为（1.4+0.6）/0.6=10/3

J3 等待时机是(8+2-8.8)=1.2 响应比（1.2+0.2）/0.2=7

J4 等待时间是(8+2-9.0)=1.0 响应比（1.0+0.5）/0.5=3

因为J3的响应比最高，所以J3开始运行。J3 的完成时间是10+0.2=10.2周转时间是10.2-8.8=1.4

此时

J2的等待时间是10.2-8.6=1.6 响应比( 1.6+0.6)/0.6=11/3=3.6667

J4的等待时间是10.2-9.0=1.2 响应比（1.2+0.5）/0.5=3.4

因为J2的响应比高，所以J2 开始运行，J2的完成时间是10.2+0.6=10.8；周转时间10.8-8.6=2.2；

这时候运行J4,J4 的完成时间是10.8+0.5=11.3 周转时间是11.3-9.0=2.3；

因此平均周转时间是（2+1.4+2.2+2.3 )/4=1.975

16. fork函数

在fork函数执行完毕后，如果创建新进程成功，则出现两个进程，一个是子进程，一个是父进程。在子进程中，fork函数返回0，在父进程中，fork返回新创建子进程的进程ID。我们可以通过fork返回的值来判断当前进程是子进程还是父进程。fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：

1）在父进程中，fork返回新创建子进程的进程ID；
2）在子进程中，fork返回0；
3）如果出现错误，fork返回一个负值；

#include <unistd.h>  
#include <stdio.h>   
int main ()   
{   
    pid_t fpid; //fpid表示fork函数返回的值  
    int count=0;  
    fpid=fork();   
    if (fpid < 0)   
        printf("error in fork!");   
    else if (fpid == 0) {  
        printf("i am the child process, my process id is %d/n",getpid());   
        printf("我是爹的儿子/n");//对某些人来说中文看着更直白。  
        count++;  
    }  
    else {  
        printf("i am the parent process, my process id is %d/n",getpid());   
        printf("我是孩子他爹/n");  
        count++;  
    }  
    printf("统计结果是: %d/n",count);  
    return 0;  
}

运行结果是：
i am the child process, my process id is 5574
我是爹的儿子
统计结果是: 1
i am the parent process, my process id is 5573
我是孩子他爹
统计结果是: 1

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
 
int main(void)
{
   int i;
   for(i=0; i<2; i++){
      fork();
      printf("%d.-\n",i);
   }
 
   wait(NULL);
   wait(NULL);
 
   return 0;
}

17. 上下文切换

​ Linux 是一个多任务操作系统，它支持远大于 CPU 数量的任务同时运行。当然，这些任务实际上并不是真的在同时运行，而是因为系统在很短的时间内，将 CPU 轮流分配给它们，造成多任务同时运行的错觉。而在每个任务运行前，CPU 都需要知道任务从哪里加载、又从哪里开始运行，也就是说，需要系统事先帮它设置好 CPU 寄存器和程序计数器(Program Counter，PC)。CPU 寄存器，是 CPU 内置的容量小、但速度极快的内存。而程序计数器，则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。它们都是 CPU 在运行任何任务前，必须的依赖环境，因此也被叫做 CPU 上下文。而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。根据任务的不同，CPU的上下文切换可以分为不同的场景，也就是进程上下文切换、线程上下文切换、中断上下文切换。

​ 上下文切换指的是内核（操作系统的核心）在CPU上对进程或者线程进行切换。上下文切换过程中的信息被保存在进程控制块（PCB-Process Control Block）中。PCB又被称作切换帧（SwitchFrame）。上下文切换的信息会一直被保存在CPU的内存中，直到被再次使用。

https://www.cnblogs.com/williamjie/p/9466941.html

18. 进程切换

（三）内存管理

1.页面置换算法

• FIFO算法：先入先出，即淘汰最早调入的页面。
• OPT(MIN)算法：选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。可惜，MIN需要知道将来发生的事，只能在理论中存在，实际不可应用。
• LRU(Least-Recently-Used)算法：用过去的历史预测将来，选最近最长时间没有使用的页淘汰(也称最近最少使用)。性能最接近OPT。与页面使用时间有关。

• LFU(Least Frequently Used)算法：即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。与页面使用次数有关。
• Clock：给每个页帧关联一个使用位，当该页第一次装入内存或者被重新访问到时，将使用位置为1。每次需要替换时，查找使用位被置为0的第一个帧进行替换。在扫描过程中，如果碰到使用位为1的帧，将使用位置为0，在继续扫描。如果所谓帧的使用位都为0，则替换第一个帧。

在一个请求页式存储管理中，一个程序的页面走向为 3、4、2、1、4、5、3、4、5、1、2，并采用 LRU算法。设分配给该程序的存储块数 S 分别为 3 和 4，在该访问中发生的缺页次数 F 是8,7

https://www.nowcoder.com/questionTerminal/780dce19969445c5a7814c0ff087c103

2. 内存分页

现代计算机都使用分页（Paging）的方式对虚拟地址空间和物理地址空间进行分割和映射，以减小换入换出的粒度，提高程序运行效率。

分页（Paging）的思想是指把地址空间人为地分成大小相等（并且固定）的若干份，这样的一份称为一页，就像一本书由很多页面组成，每个页面的大小相等。如此，就能够以页为单位对内存进行换入换出：

当程序运行时，只需要将必要的数据从磁盘读取到内存，暂时用不到的数据先留在磁盘中，什么时候用到什么时候读取。
当物理内存不足时，只需要将原来程序的部分数据写入磁盘，腾出足够的空间即可，不用把整个程序都写入磁盘。

（四）I/O

1.I/O模式？参考

阻塞I/O（blocking IO）	非阻塞I/O（nonblocking IO）
调用blocking IO会一直block住对应的进程直到操作完成	non-blocking IO在kernel还准备数据的情况下会立刻返回。
I/O多路复用（ IO multiplexing）	异步I/O（asynchronous IO）

下图对IO模型进行了对比：

（1）阻塞I/O（blocking IO）

​ 当用户进程调用了 recvfrom 这个系统调用， kernel 就开始了 IO 的第一个阶段：准备数据（对于网络IO来说，很多时候数据在一开始还没有到达。比如，还没有收到一个完整的 UDP 包。这个时候 kernel 就要等待足够的数据到来）。这个过程需要等待，也就是说数据被拷贝到操作系统内核的缓冲区中是需要一个过程的。而在用户进程这边，整个进程会被阻塞（当然，是进程自己选择的阻塞）。当 kernel 一直等到数据准备好了，它就会将数据从 kernel 中拷贝到用户内存，然后 kernel 返回结果，用户进程才解除 block 的状态，重新运行起来。

blocking IO的特点就是在IO执行的两个阶段都被block了

（2）非阻塞I/O（nonblocking IO）

​ 当用户进程发出 read 操作时，如果 kernel 中的数据还没有准备好，那么它并不会 block 用户进程，而是立刻返回一个 error 。从用户进程角度讲 ，它发起一个 read 操作后，并不需要等待，而是马上就得到了一个结果。用户进程判断结果是一个 error 时，它就知道数据还没有准备好，于是它可以再次发送 read 操作。一旦 kernel 中的数据准备好了，并且又再次收到了用户进程的 system call ，那么它马上就将数据拷贝到了用户内存，然后返回。

nonblocking IO的特点是用户进程需要不断的主动询问kernel数据好了没有.

（3）I/O多路复用（ IO multiplexing）

​ （Java中的NIO使用channel来完成多路复用）,IO multiplexing就是我们说的select，poll，epoll，有些地方也称这种IO方式为event driven IO。select/epoll的好处就在于单个process就可以同时处理多个网络连接的IO。它的基本原理就是select，poll，epoll这个function会不断的轮询所负责的所有socket，当某个socket有数据到达了，就通知用户进程。所以，I/O 多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符，而这些文件描述符（套接字描述符）其中的任意一个进入读就绪状态，select()函数就可以返回。

（4）信号驱动I/O（ signal driven IO）

（5）异步I/O（asynchronous IO）

​ （并不会加快io的过程）用户进程发起 read 操作之后，立刻就可以开始去做其它的事。而另一方面，从 kernel 的角度，当它受到一个 asynchronous read 之后，首先它会立刻返回，所以不会对用户进程产生任何 block 。然后，kernel 会等待数据准备完成，然后将数据拷贝到用户内存，当这一切都完成之后，kernel 会给用户进程发送一个 signal ，告诉它 read 操作完成了。

2.零拷贝zero-copy

​ 零拷贝操作减少了在用户空间与内核空间之间切换模式的次数。磁盘可以说是计算机系统最慢的硬件之一，读写速度相差内存 10 倍以上，所以针对优化磁盘的技术非常的多，比如零拷贝、直接 I/O、异步 I/O 等等，这些优化的目的就是为了提高系统的吞吐量，另外操作系统内核中的磁盘高速缓存区，可以有效的减少磁盘的访问次数。

2.1 用户空间和内核空间

​ 说到零拷贝，首先“用户空间”和“内核空间”说起，用户空间和内核空间的空间、权限以及作用是不一样的，用户空间是提供给各个用户使用的主要空间，内核空间是操作系统自身使用的空间，主要提供给程序调度、内存分配、连接硬件资源等。

用户空间不具备访问内核空间资源的权限，因此如果应用程序需要使用到内核资源的话，必须切换到内核空间：首先从用户空间切换到内核空间，然后在完成相关的操作后再从内核空间切换到用户空间。

2.2 DMA技术

在没有 DMA 技术前，I/O 的过程是这样的：

• CPU 发出对应的指令给磁盘控制器，然后返回；
• 磁盘控制器收到指令后，于是就开始准备数据，会把数据放入到磁盘控制器的内部缓冲区中，然后产生一个中断；
• CPU 收到中断信号后，停下手头的工作，接着把磁盘控制器的缓冲区的数据一次一个字节地读进自己的寄存器，然后再把寄存器里的数据写入到内存，而在数据传输的期间 CPU 是无法执行其他任务的。

流程如下：

​ 可以看到，整个数据的传输过程，都要需要 CPU 亲自参与搬运数据的过程，而且这个过程，CPU 是不能做其他事情的。简单的搬运几个字符数据那没问题，但是如果我们用千兆网卡或者硬盘传输大量数据的时候，都用 CPU 来搬运的话，肯定忙不过来。计算机科学家们发现了事情的严重性后，于是就发明了 DMA 技术，也就是直接内存访问（Direct Memory Access）技术。

什么是 DMA 技术？简单理解就是，在进行 I/O 设备和内存的数据传输的时候，数据搬运的工作全部交给 DMA 控制器，而 CPU 不再参与任何与数据搬运相关的事情，这样 CPU 就可以去处理别的事务。流程如下：

具体过程：

• 用户进程调用 read 方法，向操作系统发出 I/O 请求，请求读取数据到自己的内存缓冲区中，进程进入阻塞状态；
• 操作系统收到请求后，进一步将 I/O 请求发送 DMA，然后让 CPU 执行其他任务；
• DMA 进一步将 I/O 请求发送给磁盘；
• 磁盘收到 DMA 的 I/O 请求，把数据从磁盘读取到磁盘控制器的缓冲区中，当磁盘控制器的缓冲区被读满后，向 DMA 发起中断信号，告知自己缓冲区已满；
• DMA 收到磁盘的信号，将磁盘控制器缓冲区中的数据拷贝到内核缓冲区中，此时不占用 CPU，CPU 可以执行其他任务；
• 当 DMA 读取了足够多的数据，就会发送中断信号给 CPU；
• CPU 收到 DMA 的信号，知道数据已经准备好，于是将数据从内核拷贝到用户空间，系统调用返回；

​ 可以看到， 整个数据传输的过程，CPU 不再参与数据搬运的工作，而是全程由 DMA 完成，但是 CPU 在这个过程中也是必不可少的，因为传输什么数据，从哪里传输到哪里，都需要 CPU 来告诉 DMA 控制器。早期 DMA 只存在在主板上，如今由于 I/O 设备越来越多，数据传输的需求也不尽相同，所以每个 I/O 设备里面都有自己的 DMA 控制器。

2.3 传统文件传输有多糟糕？

代码通常如下，一般会需要两个系统调用：

read(file, tmp_buf, len);
write(socket, tmp_buf, len);

首先，期间共发生了 4 次用户态与内核态的上下文切换，因为发生了两次系统调用，一次是 read() ，一次是 write()，每次系统调用都得先从用户态切换到内核态，等内核完成任务后，再从内核态切换回用户态。

上下文切换到成本并不小，一次切换需要耗时几十纳秒到几微秒，虽然时间看上去很短，但是在高并发的场景下，这类时间容易被累积和放大，从而影响系统的性能。

其次，还发生了 4 次数据拷贝，其中两次是 DMA 的拷贝，另外两次则是通过 CPU 拷贝的，下面说一下这个过程：

• 第一次拷贝，把磁盘上的数据拷贝到操作系统内核的缓冲区里，这个拷贝的过程是通过 DMA 搬运的。
• 第二次拷贝，把内核缓冲区的数据拷贝到用户的缓冲区里，于是我们应用程序就可以使用这部分数据了，这个拷贝到过程是由 CPU 完成的。
• 第三次拷贝，把刚才拷贝到用户的缓冲区里的数据，再拷贝到内核的 socket 的缓冲区里，这个过程依然还是由 CPU 搬运的。
• 第四次拷贝，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程又是由 DMA 搬运的。

我们回过头看这个文件传输的过程，我们只是搬运一份数据，结果却搬运了 4 次，过多的数据拷贝无疑会消耗 CPU 资源，大大降低了系统性能。

这种简单又传统的文件传输方式，存在冗余的上文切换和数据拷贝，在高并发系统里是非常糟糕的，多了很多不必要的开销，会严重影响系统性能。

所以，要想提高文件传输的性能，就需要减少「用户态与内核态的上下文切换」和「内存拷贝」的次数。

2.4 零拷贝—-mmap+write

在前面我们知道，read() 系统调用的过程中会把内核缓冲区的数据拷贝到用户的缓冲区里，于是为了减少这一步开销，我们可以用 mmap() 替换 read() 系统调用函数。

具体过程如下：

• 应用进程调用了 mmap() 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区；
• 应用进程再调用 write()，操作系统直接将内核缓冲区的数据拷贝到 socket 缓冲区中，这一切都发生在内核态，由 CPU 来搬运数据；
• 最后，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程是由 DMA 搬运的。

​ 我们可以得知，通过使用 mmap() 来代替 read()， 可以减少一次数据拷贝的过程。但这还不是最理想的零拷贝，因为仍然需要通过 CPU 把内核缓冲区的数据拷贝到 socket 缓冲区里，而且仍然需要 4 次上下文切换，因为系统调用还是 2 次。

2.5 零拷贝—-sendfile

在 Linux 内核版本 2.1 中，提供了一个专门发送文件的系统调用函数 sendfile()，函数形式如下：

#include <sys/socket.h>
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

以上，只有一条系统命令，只会引起以此上下文切换。

它的前两个参数分别是目的端和源端的文件描述符，后面两个参数是源端的偏移量和复制数据的长度，返回值是实际复制数据的长度。

• 首先，它可以替代前面的 read() 和 write() 这两个系统调用，这样就可以减少一次系统调用，也就减少了 2 次上下文切换的开销。

• 其次，该系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态，这样就只有 2 次上下文切换，和 3 次数据拷贝。如下图：

2.6 零拷贝—-SG-DMA

如果网卡支持 SG-DMA（The Scatter-Gather Direct Memory Access）技术（和普通的 DMA 有所不同），我们可以进一步减少通过 CPU 把内核缓冲区里的数据拷贝到 socket 缓冲区的过程。

你可以在你的 Linux 系统通过下面这个命令，查看网卡是否支持 scatter-gather 特性：

$ ethtool -k eth0 | grep scatter-gather
scatter-gather: on

于是，从 Linux 内核 2.4 版本开始起，对于支持网卡支持 SG-DMA 技术的情况下， sendfile() 系统调用的过程发生了点变化，具体过程如下：

• 第一步，通过 DMA 将磁盘上的数据拷贝到内核缓冲区里；
• 第二步，缓冲区描述符和数据长度传到 socket 缓冲区，这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中，这样就减少了一次数据拷贝；

所以，这个过程之中，只进行了 2 次数据拷贝，如下图：

这就是所谓的零拷贝（Zero-copy）技术，因为我们没有在内存层面去拷贝数据，也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进行传输的。（零拷贝：全程没有使用CPU搬运数据）

零拷贝技术的文件传输方式相比传统文件传输的方式，减少了 2 次上下文切换和数据拷贝次数，只需要 2 次上下文切换和数据拷贝次数，就可以完成文件的传输，而且 2 次的数据拷贝过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。

所以，总体来看，零拷贝技术可以把文件传输的性能提高至少一倍以上。

2.7 Netty的零拷贝实现？

​ 在 OS 层面上的 Zero-copy 通常指避免在 用户态(User-space) 与 内核态(Kernel-space) 之间来回拷贝数据。而在 Netty 层面 ，零拷贝主要体现在对于数据操作的优化。

• Netty 中的零拷贝体现在以下几个方面：使用 Netty 提供的 CompositeByteBuf 类, 可以将多个ByteBuf 合并为一个逻辑上的 ByteBuf, 避免了各个 ByteBuf 之间的拷贝。
• ByteBuf 支持 slice 操作, 因此可以将 ByteBuf 分解为多个共享同一个存储区域的 ByteBuf, 避免了内存的拷贝。
• 通过 FileRegion 包装的FileChannel.tranferTo 实现文件传输, 可以直接将文件缓冲区的数据发送到目标 Channel, 避免了传统通过循环 write 方式导致的内存拷贝问题.

3.同步异步，阻塞非阻塞的区别。

（1）阻塞，非阻塞指的有无返回值

（2）同步异步指的是能否继续执行

无论阻塞式IO还是非阻塞式IO，都是同步IO模型，区别就在与第一步是否完成后才返回，但第二步都需要当前进程去完成，异步IO呢，就是从第一步开始就返回，直到第二步完成后才会返回一个消息，也就是说，非阻塞能够让你在第一步时去做其它的事情，而真正的异步IO能让你第二步的过程也能去做其它事情.

（五）linux使用

1.CPU占用过高排查

（1）top

（2）ps -ef | grep java或者jps定位

（3）定位到具体的线程：ps -mp 进程 -o THREAD,tid,time

（4）将线程ID转换为16进制的格式：print “%x\n” 数字

（5）jstack 进程id | grep tid（16进制线程id的小写）-A60

2.补充

• 计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成。
• 操作系统的五大功能，分别为：作业管理、文件管理、存储管理、输入输出设备管理、进程及处理机管理
• 中断：所谓的中断就是在计算机执行程序的过程中，由于出现了某些特殊事情，使得CPU暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序。中断一般分为三类：
  • 内部异常中断：由计算机硬件异常或故障引起的中断；
  • 软中断：由程序中执行了引起中断的指令而造成的中断（这也是和我们将要说明的系统调用相关的中断）；
  • 外部中断：由外部设备请求引起的中断，比如I/O请求。
• 系统调用：进程的执行在系统上的两个级别：用户级和核心级，也称为用户态和系统态(user mode and kernel mode)。程序的执行一般是在用户态下执行的，但当程序需要使用操作系统提供的服务时，比如说打开某一设备、创建文件、读写文件等，就需要向操作系统发出调用服务的请求，这就是系统调用。

3.命令?

• lsof -i:80 查看端口
• awk

>#/usr/bin env
> # 通过find递归，得到所有的文件的完整路径,在当前路径下，递归遍历所有的文件，每个文件使用逗号分割，找出每一行第一列值为10的所有文件的记录的行号和文件名。
> files=$(find ./ -type f)
> for i in $files
>do
>  # awk的-F选项指定分割符号，-v是指定的变量，可以在print中打印，'$1=="10"是指第一列中等于10的，print NR表示的是指示的行号，uniq指的是过滤掉重复的，>>out指的是追加到out文件
>awk -F "," -v mao=$PWD '$1=="10"{print NR,FILENAME}' $i | uniq >>out
> done
>

• sed

  • 选项
    • -n
    • -e（多条命令顺序执行，命令使用分号切割）
    • -f
    • -r
    • -i（写入文件）
  • 命令
    • a（append新增）
    • c（行替换）
    • d（delete删除）
    • i（insert前面插入）
    • p（print打印）
    • s（字符串的替换

三、数据结构

1.B-树，B+树？

画出一颗简单的B+树，给定一个ID（主键），简述B+树的查找过程

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

B树 https://blog.csdn.net/li_canhui/article/details/85305147

编号	特点
1	定义任意非叶子结点最多只有M个儿子；且M>2；
2	根结点的儿子数为[2, M]；根节点的数目是个例外
3	除根结点以外的非叶子结点的儿子数为[M/2, M]；,除了根节点,最少有M/2向上取整个子节点
4	每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5	非叶子结点的关键字个数=指向儿子的指针个数-1；（有减1,一个绳子砍三刀分为四截）
6	非叶子结点的关键字：K1, K2, …, K[M-1]；且K[i] < K[i+1]；
7	非叶子结点的指针：P1, P2, …, P[M]；其中P1指向关键字小于K1的 子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；,当成数轴来看, K[M-1]——————K[M],因为中间节点包含了数值,所以都是开区间
8	所有叶子结点位于同一层；

B+树

（3,5,8,9,10,12,13,15,17,26,28,29,30,35,36,60,65,75,79,87,90,99）

B+树是B-树的变体，也是一种多路搜索树，其定义基本与B-树同，除了：

（1）非叶子结点的子树指针与关键字个数相同；(没有减1)

（2）非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])(前闭后开)的子树（B-树是开区间）；

（3）为所有叶子结点增加一个链指针；

（4）所有关键字都在叶子结点出现；

• 关键字和指针数量的关系:B树减1,B+树相等
• 指向区间:B树开区间,B+树前闭后开
• 叶节点是否增加指针?B树没有,B+树有

2.二叉树的遍历，非递归？

• 前序

public void preorder1(BinaryTreeNode root){
    if (root==null)
        return;
    System.out.print(root.getData()+"\t");
    preorder1(root.getLeft());
    preorder1(root.getRight());
}
public void preorder2(BinaryTreeNode root){
    Stack<BinaryTreeNode>stack =new Stack<BinaryTreeNode>();
    if (root==null)
        return;
    BinaryTreeNode cur;
    cur=root;
    while(cur!=null||!stack.isEmpty()){
        if (cur!=null){
            System.out.print(cur.getData()+"\t");//根
            stack.push(cur);
            cur=cur.getLeft();//左
        }else{
            cur=stack.peek();
            stack.pop();
            cur=cur.getRight();//右
        }
    }
}

• 中序

public void inorder1(BinaryTreeNode root){
    if (root==null)
        return;
    inorder1(root.getLeft());
    System.out.print(root.getData()+"\t");
    inorder1(root.getRight());
}
public void inorder2(BinaryTreeNode root){
    Stack<BinaryTreeNode>stack =new Stack<BinaryTreeNode>();
    if(root==null)
        return;
    BinaryTreeNode cur=root;
    while(cur!=null||!stack.isEmpty()){
        if(cur!=null){
            stack.push(cur);
            cur=cur.getLeft();
        }else{
            cur=stack.peek();
            stack.pop();
            System.out.print(cur.getData()+"\t");
            cur=cur.getRight();
        }
    }
}

• 后序

public void postorder1(BinaryTreeNode root){
    if (root==null)
        return;
    postorder1(root.getLeft());
    postorder1(root.getRight());
    System.out.print(root.getData()+"\t");
}
public void postorder2(BinaryTreeNode root){
    Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
    while (true){
        if(root!=null){
            stack.push(root);
            root=root.getLeft();
        }
        else {
            if(stack.isEmpty())
                return;
            if(stack.lastElement().getRight()==null){
                root=stack.pop();
                System.out.print(root.getData()+"\t");
                while (stack.lastElement().getRight()==root){
                    System.out.print(stack.lastElement().getData()+"\t");
                    root=stack.pop();
                    if (stack.isEmpty()){
                        break;
                    }
                }
            }
            if(!stack.isEmpty())
                root=stack.lastElement().getRight();
            else
                root=null;
        }
    }
}
public void postorder3(BinaryTreeNode root){//修改前序遍历的方式为：根右左
    if(root==null)
        return;
    Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
    BinaryTreeNode cur;
    cur=root;
    List<Integer> res=new ArrayList<>();

    while (cur!=null||!stack.isEmpty()){
        if (cur!=null){
            res.add(cur.getData());
            stack.push(cur);
            cur=cur.getRight();
        }else{
            cur=stack.peek();
            stack.pop();
            cur=cur.getLeft();
        }
    }
    Collections.reverse(res);
    for (Integer i:res){
        System.out.print(i+"\t");
    }
}

• 层次遍历

public void levelorder(BinaryTreeNode root){
     BinaryTreeNode temp;
     Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
     queue.offer(root);
     while (!queue.isEmpty()){
         temp=queue.poll();
         System.out.print(temp.getData()+"\t");
         if(temp.getLeft()!=null){//左
             queue.offer(temp.getLeft());
         }
         if(temp.getRight()!=null){//右
             queue.offer(temp.getRight());
         }
     }
 }

3.循环队列？

package CommonProblems.ArrayProblems;

/**
 * @Author MaoTian
 * @Classname CycQueue
 * @Description 循环队列
 * @Date 上午9:46 2019/9/17
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */
public class CycQueue<T> {
    private int maxsize;
    private Object[] arr;
    private int front;
    private int tail;

    public CycQueue(int maxsize) {
        this.maxsize = maxsize;
        this.arr =new Object[maxsize];
        this.front = 0;
        this.tail = 0;
    }
    //判断是否为空
    public boolean isEmpty(){
        if (front==tail){
            return true;
        }else {
            return false;
        }
    }
    //销毁
    public CycQueue destroy(){
        arr=null;
        front=tail=0;
        return this;
    }
    //清空
    public CycQueue clear(){

        front=tail=0;
        for (int i = 0; i <maxsize ; i++) {
            arr[i]=null;
        }
        return this;
    }
    //求元素的个数
    public int size(){
        return (tail-front+maxsize)%maxsize;
    }
    //
    public Object head(){
        return arr[front];
    }
    //入队
    public boolean add(Object e){
        if((tail+1)%maxsize==front){
            return false;
        }

        tail=(tail+1)%maxsize;
        arr[tail]=e;
        return true;
    }
    //出队
    public Object pop(){
        if(front==tail){
            return null;
        }
        T e=(T)arr[front];
        front=(front+1)%maxsize;
        return e;
    }

    public static void main(String[] args) {
        CycQueue c=new CycQueue(6);
        c.add(1);
        c.add(2);
        c.add(3);
        c.add(4);
        c.add(5);
        c.add(6);
        System.out.println(c.add(7));
        System.out.println(c.pop());
        System.out.println(c.pop());
        System.out.println(c.add(7));
        System.out.println(c.add(8));
        for (int i = 0; i <6 ; i++) {
            System.out.print(c.arr[i]+" ");
        }
    }

}

4.Trie Tree（208. Implement Trie (Prefix Tree)）

Trie，又经常叫前缀树，字典树等等。它有很多变种，如后缀树，Radix Tree/Trie，PATRICIA tree，以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。

• 应用
  • 字符串检索
  • 文本预测、拼写检查
  • 词频统计
  • 排序
  • 字符串最长公共前缀
  • 字符串搜索的前缀匹配
  • 作为其他数据结构和算法的辅助结构

5.树，图节点以及度数相关？

• 二叉树中n个节点，0度、 1度、 2度的关系？

  度为2节点数 = 叶子节点数 - 1

  证明：

  • 树支路总数 = 树节点总数 - 1
  • 树支路总数=0x0 + 1x1 + 2*x2
  • 树节点总数=x0 + x1 + x2 - 1
  • 得到：度为0与度为2的节点数的关系x2 = x0 - 1

• 无向图度数和边数的关系：度数等于二倍的边数。

四、算法

1.算法的分类？

2.弗洛伊德算法？

（三层for循环，通过第三个点不断更新两个点之间的距离）https://www.cnblogs.com/lc-java/p/7840464.html

3.迪杰斯特拉算法？

https://www.cnblogs.com/he-px/p/6677063.html

https://www.cnblogs.com/zengzhihua/p/6755439.html

4.二分法？（边界问题）

public int binarySearch(int[] nums,int target){
    int start=0;
    //减1
    int end=nums.length-1;
    //等号
    while (start<=end){
        int mid=(start+end)/2;
        if (nums[mid]==target){
            return mid;
        }else if(nums[mid]<target){
            start=mid+1;
        }else{
            end=mid-1;
        }
    }
    return -1;
}

5.排序算法

（1）堆排序

package ALiBaBa;

/**
 * @Author MaoTian
 * @Classname HeapSort
 * @Description
 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 * @Date 下午11:35 2019/8/17
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */
import java.util.Arrays;
public class HeapSort {
    public static void main(String []args){
        int []arr = {3,1,4,2,8,5,9,7,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){

        //1.构建大顶堆（头部就是0）
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构（不包含length）
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素（取值length-1次）
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整（不包含j）
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

（2）归并排序

package ALiBaBa;

import org.junit.Test;

/**
 * @Author MaoTian
 * @Classname MergeSort
 * @Description TODO
 * @Date 上午11:40 2019/8/17
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */
public class MergeSort {
    

    public void mergeSort(int[] nums,int left,int right){
        if(left<right){
            int mid=(left+right)>>1;
            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);
            merge(nums,left,right,mid);
        }
    }
    public void merge(int[] nums,int left,int right,int mid){

        int leftPos=left;
        int pos=left;
        int rightPos=mid+1;
        int len=right-left+1;
        int[] tmp=new int[nums.length];

        while(leftPos<=mid&&rightPos<=right){
            if(nums[leftPos]>nums[rightPos]){
                tmp[pos++]=nums[rightPos++];
            }else{
                tmp[pos++]=nums[leftPos++];
            }
        }

        while(leftPos<=mid){
            tmp[pos++]=nums[leftPos++];
        }

        while(rightPos<=right){
            tmp[pos++]=nums[rightPos++];
        }
        int m=left;
        int n=left;
        for(int i=0;i<len;i++){
            nums[m++]=tmp[n++];
        }
    }
    @Test
    public void check(){
        int[] nums={2,4,2,5,73,2};
        mergeSort(nums,0,nums.length-1);
        for(int i=0;i<nums.length;i++){
            System.out.println(nums[i]);
        }
    }

}

（3）快速排序

package ALiBaBa;

import org.junit.Test;

/**
 * @Author MaoTian
 * @Classname QuickSort
 * @Description TODO
 * @Date 上午11:39 2019/8/17
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */
public class QuickSort {
    public void quickSort(int[] nums,int left,int right){
        if(left<right){
            int mid=partition(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }
    public int partition(int[] nums,int left,int right){
        int pos=left;
        int value=nums[pos];
        for (int i=left;i<=right;i++){
            if(nums[i]<value){
                pos++;
                if(pos!=i){
                    int tmp=nums[pos];
                    nums[pos]=nums[i];
                    nums[i]=tmp;
                }
            }
        }
        nums[left]=nums[pos];
        nums[pos]=value;
        return pos;
    }
    @Test
    public void check(){
        int[] nums={2,4,2,6,7,3,2,6,8};
        quickSort(nums,0,nums.length-1);
        for (int i=0;i<nums.length;i++){
            System.out.println(nums[i]);
        }
    }
}

6.LRU算法？

• 双向链表加HashMap的实现，重要需要完成的功能点为：
  • 将当前访问的节点放到队列的头部
  • 当容量不够的时候，将队列尾部的元素移走，并且在HashMap中消除

package JavaDemo.AlgorithmDemo;

import java.util.HashMap;

/**
 * @Author MaoTian
 * @Classname LRUCache
 * @Description 使用链表保证相对顺序，使用栓链表，两个指针可以使得两种删除操作更加容易，使用HashMap是为了快速查找！
 * @Date 上午9:16 2019/8/23
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */

class LRUNode {
    String key;
    Object value;
    LRUNode prev;
    LRUNode next;
    public LRUNode(String key, Object value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    
    
    private HashMap<String, LRUNode> map;
    private int capacity;
    private LRUNode head;//记录尾部
    private LRUNode tail;//记录尾部

    public void set(String key, Object value) {
        LRUNode node = map.get(key);
        if (node != null) {
            //原来的节点
            node = map.get(key);
            node.value = value;
            remove(node, false);
        } else {
            //新节点
            node = new LRUNode(key, value);
            if (map.size() >= capacity) {
                // 每次容量不足时先删除最久未使用的元素
                remove(tail, true);
            }
            map.put(key, node);
        }
        // 将刚添加的元素设置为head
        setHead(node);
    }
    public Object get(String key) {
        LRUNode node = map.get(key);
        if (node != null) {
            // 将刚操作的元素放到head，将node从原来的位置删除（这里的删除其实就是将这个node移动到队列的头部）
            remove(node, false);
            setHead(node);
            return node.value;
        }
        return null;
    }
    private void setHead(LRUNode node) {
        // 建立双向指针
        if (head != null) {
            node.next = head;
            head.prev = node;
        }
        head = node;
        
        //第一个加入的node设置为尾节点
        if (tail == null) {
            tail = node;
        }
    }
    // 从链表中删除此Node，此时要注意该Node是head或者是tail的情形
    private void remove(LRUNode node, boolean flag) {
        //双向指针
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            //删除的节点是head
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            //删除的节点是tail，需要重新设置tail为当前节点的前一个节点
            tail = node.prev;
        }
        //删除
        node.next = null;
        node.prev = null;
        
        //容量不够的时候从map中删除
        if (flag) {
            map.remove(node.key);
        }
    }
    //构造函数
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<String, LRUNode>();
    }
}

• LRU的缓存，需要完成超时淘汰和LRU淘汰？,对上面的代码进行修改，每一次get或者set操作将不是当前的LRUNode的age加上一，当前的置为0，紧接着对于HashMap中的所有LRUNode的年龄进行判断，当年龄不够的时候从链表和HashMap中移走。
• 基于LinkedHashMap的实现

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class Main {
    static class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
        //定义缓存的容量
        private int capacity;
        //带参数的构造器
        LRULinkedHashMap(int capacity){
            //如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序(最近访问的将会被放到队列尾部，即后删除)
            //如果accessOrder为flase的话，则按插入顺序来遍历
            super(16,0.75f,true);//父类的构造器
            //传入指定的缓存最大容量
            this.capacity=capacity;
        }
        //实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
        @Override
        public boolean removeEldestEntry(Map.Entry<K, V> eldest){
            return size()>capacity;
        }
    }
    //test
    public static void main(String[] args) {
        LRULinkedHashMap<String, Integer> testCache = new LRULinkedHashMap<>(3);
        testCache.put("A", 1);
        testCache.put("B", 2);
        testCache.put("C", 3);
        System.out.println(testCache.get("B"));
        System.out.println(testCache.get("A"));
        testCache.put("D", 4);
        System.out.println(testCache.get("D"));
        System.out.println(testCache.get("C"));
    }
}

7.洗牌算法？

8.朋友圈LeetCode547?

9.卡特兰数

• 字节跳动客户端2019笔试题目，圆圈，点，道路
• 阿里巴巴括号匹配的种类

10.排序算法

https://www.runoob.com/w3cnote/sort-algorithm-summary.html

• 八大排序算法真的是面试宠儿
• 最常考 快速排序 和归并排序
• 不稳定(快些选堆)
• 时间复杂度（快些归堆O(nlogn)）
• 堆排 也应该掌握

11. 树

• 根据遍历结果恢复树，递归
• 二叉搜索树第k大
• 树的和为k的路径
• 树的最大路径和
• 层次遍历
• 根据层次遍历和后序遍历恢复树
• 镜像树
• 树的深度
• 是不是平衡二叉树

红黑树

中序遍历是有序的。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。(黑色节点完美平衡)

下面是一个具体的红黑树的图例：

• 操作

  • 着色
  • 左旋转：你当我儿子，我的左二子当你的右儿子；

  /**
  *		p                               p
  *		|                               |
  *		x                               y
  *	   / \          ------>            / \
  *	 lx   y                           x   ry
  *        / \                         / \
  *       ly  ry                      lx  ly
  */
  private void leftRotate(RBNode x) {
      RBNode y = x.right;
      
      // 我的左儿子变为你的右儿子
      x.right = y.left;
      // 注意parent不能够丢下！！！
      if(y.left != null) {
          y.left.parent = x;
      }
      
      // 我变成爸爸啦
      if(x.parent != null) {
          y.parent = x.parent;
          if(x == x.panrent.left) {
              x.parent.left = y;
          } else {
              x.parent.right = y;
          }
      } else {
          this.root = y;
      }
      
      // 你变成我儿子
      x.parent = y;
      y.left = x;
  }

• 右旋转：你当我儿子，我的右儿子当你的左儿子。

hashmap

1.说说你对hash算法的理解
追问：hash算法任意长度的输入 转化为了 固定长度的输出，会不会有问题呢？
追问：hash冲突能避免么？
2.你认为好的hash算法，应该考虑点有哪些呢？
3.HashMap中存储数据的结构是什么样的呢？
4.创建HashMap时，不指定散列表数组长度，初始长度是多少呢？
追问：散列表是new HashMap() 时创建的么？
5.默认负载因子是多少呢，并且这个负载因子有什么作用？
6.链表转化为红黑树，需要达到什么条件呢？
7.Node对象内部的hash字段，这个hash值是key对象的hashcode()返回值么？
追问：这个hash值是怎么得到呢？
追问：hash字段为什么采用高低位异或？
8.HashMap put 写数据的具体流程，尽可能的详细点！
9.红黑树的写入操作，是怎么找到父节点的，找父节点流程？
10.TreeNode数据结构，简单说下。
11.红黑树的原则有哪些呢？
12.JDK8 hashmap为什么引入红黑树？解决什么问题？
追问：为什么hash冲突后性能变低了？【送分题】
13.hashmap 什么情况下会触发扩容呢？
追问：触发扩容后，会扩容多大呢？算法是什么？
追问：为什么采用位移运算，不是直接*2？
14.hashmap扩容后，老表的数据怎么迁移到扩容后的表的呢？
15.hashmap扩容后，迁移数据发现该slot是颗红黑树，怎么处理呢？

12.链表

• 反转链表
• 链表环的入口
• 交叉链表的交点
• 复杂链表的复制
• 二叉搜索树变成双向链表

13.回溯算法

• 走迷宫
• 游戏通关

14.递推算法

• 走台阶
• 断钢筋

15. 背包问题

• 装最多的东西

16.贪心算法

• 覆盖问题
• 时间问题

17.编辑距离

• 对一个八位数有三种操作： 加一、减一、反转 。 至少多少次操作可以把一个八位数A变成八位数B。？
• leetcode 72

package CommonProblems.Dynamic;

/**
 * @Author MaoTian
 * @Classname EditDistance
 * @Description TODO
 * @Date 下午3:40 2019/9/17
 * @Version 1.0
 * @Created by mao<tianmao818@qq.com>
 */
public class EditDistance {
    public int helper(String s1,String s2){
        int m=s1.length();
        int n=s2.length();
        //dp[i][j]表示长度为i的s1的子串转换为长度为j的s2的子串的操作次数
        int[][] dp=new int[m+1][n+1];
        for (int i = 0; i <=m ; i++) {
            dp[i][0]=i;//删除
        }
        for (int i = 0; i <=n ; i++) {
            dp[0][i]=i;//插入
        }       
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                int replaces=0;
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    replaces=dp[i-1][j-1];
                }else {
                    replaces=dp[i-1][j-1]+1;
                }
                dp[i][j]=Math.min(replaces,//替换
                        Math.min(dp[i-1][j],//插入
                                dp[i][j-1]+1)//删除
                );
            }
        }
        return dp[m][n];
    }
}

18.dfs

• 一个有向图用邻接矩阵表示，并且是有权图，现在问怎么判断图中有没有环。使用一个全局的一维数组保存访问的状态，对于每一个节点i，递归遍历当前节点指向的节点，当重新访问到当前的节点的时候，就是存在环路，直接返回true。

19.两个str 最大公共子序列和子串？

   public int getMaxCommon(String s1,String s2){
        char[] arr1=s1.toCharArray();
        int m=arr1.length+1;
        char[] arr2=s2.toCharArray();
        int n=arr2.length+1;

        int[][] dp=new int[m][n];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(arr1[i-1]==arr2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);//最长公共子序列
//                    dp[i][j]=0;//最长公共子串
                }
            }
        }
        int res=0;
        for(int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if(res<dp[i][j]){
                    res=dp[i][j];
                }
            }
        }

        return res;
    }