面试 基础：计网 OS 计组 Linux 安全

实习

计网

IP 层怎么实现网络通信

不同机器间怎么通信（HTTP，RPC？）

计算机网络7层模型，OSI (Open System Interconnection)

从底向上：
物理层：通过物理链接，传输比特流（比如用电信号传01）。最基础、最重要的。
数据链路层：将比特信息封装为数据帧。保证传输单元无误，处理传输错误（错误校验），提供一部分流量控制。有 以太网协议，规定了帧格式和 MAC 地址，由交换机负责。
网络层：将网络划分成很多子网，实现路由、逻辑寻址 (IP)、多个网络间通信。有 IP, ARP 协议，由路由器负责。如果没有 IP 子网，路由器就必须记住每个 MAC 地址要传到哪个路由器，这是不可能的。通过 IP，只需要发给一个层级更低的子网，再由子网发给更小的子网，直到找到目标机器。
传输层：提供端口号，保证进程间的通信；提供流量控制、错误校验。有 TCP, UDP 协议。
会话层：管理机器间的会话。提供部分服务，如进行同步，确认检查点。
表示层：语法转换、协商、加密或解密、编码或解码，解决设备间数据格式的差异。格式有 ASCII、JPEG 等。
应用层：给应用提供与网络的通信接口。有 HTTP、FTP、SMTP 等。

五层模型将会话层和表示层合并到了应用层。

发送方的数据会进行从上层到下层的封装，接收方会将数据从下层到上层解除封装。

HTTP 与 TCP

TCP 是传输层协议，决定数据在网络中如何传输，比如要不要建立信道、拥塞控制。
HTTP 是更上层的应用层协议，是直接与应用打交道的，可以封装用户数据、调用传输层的逻辑。

socket编程
一个Socket由一个IP地址和一个端口号唯一确定。
Socket偏向于底层。一般很少直接使用Socket来编程，框架底层使用Socket比较多。
流程：
单向传输：服务器监听、客户端请求、连接确认。
全双工：server、client执行端口绑定bind、listen，client执行connect，server执行accept，client发送自己的地址和端口用于server构造地址，然后执行accept，server执行connect。然后双方正常自由发送信息。

示例：https://zybuluo.com/SovietPower/note/2013258#%E4%BB%A3%E7%A0%81

Hex编码

很简单的定长编码，将二进制数据每4位编码成一个16进制符号（0~9, A~F）。所以一个字节8位需要2个Hex符号，也就是两字节表示。

ASCII编码

Hex是不可读的，不能直接表示文本，只能表示二进制数据。
ASCII 可以表示英文、数字和各种常用字符，共128个，用7位二进制数表示。后来有扩展 ASCII，共256个，用8位表示。

Unicode

统一码或万国码。为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的需求。
有三种编码方式：utf-8，utf-16，utf-32。（utf指：Unicode Transformation Format）
8和16是变长编码，32是定长编码，数字表示编码的最小单位，如8和16表示每个字符都需要8n或16n位来表示，32位每个字符固定需要32位来表示。
utf-8 由于直接与ASCII兼容，且是字节顺序无关的（它的字节顺序在所有系统中都是一样，不需要文件有字节顺序标记(Byte Order Mark)表明字节顺序），所以最常用。

Utf-8

定长编码中的每个字符使用固定位数，但浪费空间。
utf-8 是一种变长编码：

[0, 127] 用8位表示，第1位为0，后7位存数据。
[128, 2047] 用16位表示，第一字节的前3位为110（与10区分），后5位存数据；第二字节的前2位为10，后6位存数据。
[2048, 65535] 用24位表示，第一字节的前4位为1110，后4位存数据；第二、三字节的前2位为10，后6位存数据。
对于用$n(n>1)$字节表示的，第一字节前n位为1，第n+1位为0，后面存数据；其余字节的前2位为10，后6位存数据。

每个字符前几位1的个数可以计算其字节数，后面的10表示后续的字节。
存数据的位拼起来为实际数据。

base64

一种定长编码格式。将二进制数据每6位编码成一个64进制符号。
Base64使用64个可打印字符（A~Z, a~Z, 0~9, +, /）来表示二进制数据。
每个字符表示 0~63 的一个值，对应原数据的$\log_264=6$位。二进制数据中1字节为8位，所以3字节可以转换为4个base64字符（4字节）。
编码时，每3个字节为一组，转换为4个base64字符。所以Base64编码的数据体积通常比原数据大三分之一。
当数据字节数不是3的倍数时，补0直到3k个字节，最后在编码字符串的后面放=：一个=表示原字节数模3余1，两个=表示原字节数模3余2。

对于非ASCII字符，要先转为ASCII才能编码。

对于较小图片，合理使用Base64字符串替换并内嵌到前端，可以减少页面http请求，但是会导致页面体积变大。
这样也可以实现纯文本（非二进制）传输图片。

使用base64的原因：
base64可以将二进制数据编码成文本。某些情况下不能直接传输、存储或使用二进制数据，就可以先编码为base64。
虽然什么字符在底层都是二进制传输的，但是很多传输协议或硬件，会将某些二进制作为特殊用途，且它们之间并不兼容，传任意的二进制串很容易与这些值冲突，被识别错。但base64规定的64个字符的二进制值不会。
比如 http 协议的 url 是纯文本的，很多语言的 String 类也不能直接存二进制流（比如 C 里的 '\0'）。

Hex 原8位1字节数据需要2字节表示，base64 原24位3字节数据需要4字节表示（1B需要4/3B）。

MAC子层
P275 Media Access Control 介质访问控制子层
IEEE802标准把数据链路层分成LLC（Logical Link Control，逻辑链路控制）和MAC（Media Access Control，介质访问控制）两个子层。上面的LLC子层实现数据链路层与硬件无关的功能，比如流量控制、差错恢复等；较低的MAC子层提供LLC和物理层之间的接口。

CSMA
P284 Carrier Sense Multiple Access 指载波监听多路访问 位于MAC子层
当一个station要传输数据时，会监听要传输的信道是否有人在传输：
1-坚持 CSMA：若有，则等到没有，然后立刻传输。
p-坚持 CSMA：若有，则以 p 的概率等到没有，传输。有 p 的概率坚持等待并传输、1-p 的概率放弃当前。
非坚持 CSMA：若有，不传输，再等一段时间再看；若没有，传输。
若传输时发现冲突（传输失败），都需随机等待一段时间再运行该算法。

当$p=0.01$时一般最优。

CSMA/CD
P286 P303 CSMA with Collision Detection 带冲突检测的CSMA
通过在传输时监听信道，对比信道中的数据是否是自己刚刚发的数据，可提前检查是否有冲突（无需等反馈？）。

CSMA/CD with Binary Exponential Backoff 二进制指数后退的CSMA/CD
station保存一个$k=1$，每次检测到冲突时，随机等待$0\sim s^k-1$个槽，令$k++$（上限为$10$），再尝试发送。
当发送成功后，令$k=1$。

ICMP
P483 Internet Control Message Protocol Internet 控制报文协议 位于网络层
ICMP 协议的主要功能：

1. 确认IP包是否成功到达目标地址
2. 通知在发送过程中IP包被丢弃的原因

ICMP是基于IP协议工作的，但是它并不是传输层的功能，因此仍把它归为网络层协议。
ICMP只能搭配IPv4使用，如果是IPv6，使用ICMPv6。

一个ICMP报文包括IP报头（至少20B）、ICMP报头（至少8B）和ICMP报文。
报文包含消息类型、代码、检验和、内容。类型+代码标识了具体内容。

如ping（检查一个主机是否还在互联网上）使用ECHO，要求应答者发送ECHO REPLY。

ARP
P485 地址解析协议位于网络层。
在网络层、传输层中只需要知道IP地址就可进行传输，但更底层的数据链路层必须知道双方的MAC地址。ARP 协议用于 MAC 与 IP 地址之间的映射。
每个主机都有ARP缓存，保存了当前局域网内已知的 IP 与 MAC 的映射。
对于一个 IP 地址，如果缓存中没有，通过 ARP 可获取它的 MAC 地址：

1. 该主机进行广播，问谁的 IP 地址是这个地址（广播中附带自己的IP、MAC）
2. 拥有该 IP 的主机进行回复（单播），告诉询问者自己的 MAC 地址。
   双方将对方的 IP 与 MAC 映射保存。

主机只能在局域网中发送ARP广播。如果要跨LAN，则需要路由器代理主机发送跨网络广播。

MAC 地址

每个网卡都有一个世界唯一的 48 位 MAC 地址。MAC 地址也能唯一确定一个主机。

引入 IP 地址，是为了将网络划分成多个子网，路由器可以将子网看成一个整体，减少计算路由和存储的代价。如果没有子网，路由器必须记住每个 MAC 地址要传到哪个地方，而 MAC 地址有$2^{48}$个，根本存不下。
MAC 是物理地址，IP 是逻辑地址。

在设备没有 IP 地址时，还需要根据 MAC 地址区分主机，所以 MAC 也不能去掉。

CDMA
P155 Code Division Multiple Access 码分多址
允许station在整个频率上发送消息。
通过给每个基站发送两两正交的码片向量。直接用为1，取反为0。
基站间需要同步。但也有异步CDMA。

CRC 循环冗余校验码

只能发现一定的错误，不能纠正。

海明码

ECC？可以纠正错误。

路由算法
P380
最优原则：如果$j$在$i\to k$的最短路径上，则$j\to k$的最短路径与$i\to k$重合。

• 汇集树（Sink Tree）：即MST
• 最短路
• 泛洪：一个包发到某个路由器时，路由器将它转发给所有邻居（除了包来的方向）。每个路由器的包只会在每个路由器上转发一次。可用于广播，鲁棒性好，能找到所有路径。
• 距离矢量路由：每个路由器存一张表，记录它能到达的邻居、到达的最短路、最短路是走哪条出边。多次运行正确率会提高，但想收敛到最优可能很慢。
• 链路状态路由：
• 层次路由：
• 广播路由：进行广播时，如果包来自最优路径，则当前路由器将其转发给所有邻居，否则丢弃。可满足每个路由器只收到一次。

拥塞控制
P410
拥塞避免：流量感知路由（Traffic-Aware Routing，根据流量动态调节网络权重），准入控制（Admission Control，如果网络建立新的虚电路后会拥挤，则不建立）
拥塞反应：流量调节（Traffic Throttling，当路由器发现快发生阻塞时，告诉sender减慢发送速度。一般通过包的排队延迟的指数加权移动平均$d=\alpha d_{old}+(1-\alpha)d_{new}$估计是否快发生阻塞），负载脱落（Load Shedding，当路由器处理不了当前的包时，扔掉。优先扔哪些取决于包的服务类型）。

TCP滑动窗口
P246
TCP实现可靠传输依靠的是 序列号、自动重传、滑动窗口、确认应答等机制。
TCP的拥塞控制也是靠的滑动窗口。
发送方有一个发送窗口，处于发送窗口范围中的数据包都可以被发送，不需要等待前面数据包的ack包。

TCP连接建立时，双方可协商窗口大小。
发送窗口和接收窗口的本质是缓冲区。

Nagle算法允许缓存数据，然后一起发送。适用于实时性要求不高的场景。可通过optionTCP_NODELAY禁用。

窗口探测
接收方现在接收窗口是0，发送了0窗口的报文。但处理后接收窗口不再为0，于是发size=10的报文，但该报文丢失，则发送端一直等接收端的非0窗口通知，而接收端一直等数据的到来。
解决：发送端可以定期发送窗口探测数据包，要求接收方重新发送自己的窗口大小。

糊涂窗口综合症
若接收方要读取一个大文件，每次取1B缓冲区的数据，然后发送“我读了1B有1B空闲”，发送方再发送1B，则效率会很低。
解决：接收方等到缓冲区空闲空间足够多（如一半），才发送；发送方可少等待，积攒数据一起发送。

选择确认 (Selective ACKnowledgements)
如果在建立连接时，设置了 SACK permitted 选项，则启用选择确认。
接收方可以累积一部分确认信息，然后一次发送出去。SACK 会包含最近确认的最多 3 个区间的序列号。
可以减少 ACK 的次数，使发送方能针对地、选择性地发送确实没收到的数据包。

例：发送方发送 1,2,3,4,5，2,3 丢失，接收方可以回复 SACK 1,4,5（具体不一定这样，举个例子）。

ARQ
自动重传
当TCP发送端发送了一个TCP数据包的时候，会设置一个定时器，如果在定时器期间没有收到接收方对这个数据包的确认应答包，也成为ACK包，就会重新发送对应的TCP数据包。
自动重传有两个原因：数据包丢失；ACK数据包丢失。
RTO为重传超时时间。RTT为一个数据包从发送到接收到ACK确认包的花费时间，会随着网络变化、波动。
RTO略大于RTT。

超时重传

每发送一个数据段，就会启动一个计时器，在超时后重新发送，直到收到确认。
重传时间一般略大于数据包往返一次所花的时间 (RTT, round-trip time)。
但是，由于网络情况不稳定，RTT 是很难确定的。如果重传时间太短，就会发送太多重复数据；如果重传时间太长，等待重传的时间会很长。

确认重传时间 (RTO, retransmission timeout)，也就是估计 RTT 的简单方法有：

1. 指数加权移动平均：平滑的往返时间 $SRTT=\alpha SRTT+(1-\alpha)R$，$R$是上次收到确认所花的时间，即上次的 RTT。$RTO=SRTT$。
   最简单的方法。$\alpha$一般为$7/8$。
2. 方法1 对网络的变化不敏感，网络变拥堵很可能比较突然，不是平滑的。定义 往返时间变化 (round-trip time variation) $RTTVAR = \beta RTTVAR+(1-\beta)|SRTT-R|$，超时时间$RTO=SRTT+4\times RTTVAR$。
   系数4可以随意，不过*4可以直接位移实现，而且很少有数据包能一次变化4倍。

慢启动
P592 Slow Start
TCP拥塞控制策略的一部分。
TCP传统的控制窗口大小的方法为AIMD（Additive Increase Multiplicative Decrease）：没有丢包时，拥塞窗口加1；检测到丢包后，拥塞窗口除以2。
AIMD增长过慢，可能需要很久才能达到正常传输速率。

慢启动在没有丢包时，拥塞窗口CWND指数增长（初始为指定值，每次*2），增长达到阈值（slow start threshold）后恢复线性增长。
发生丢包时，阈值threshold除以2，窗口大小变为初值，重新开始增长。

快速重传
P595 Fast Retransmit and Recovery，FRR
当接收方收到失序的报文段时，不进行累计确认，立刻发送确认报文段。当发送方收到三个重复的确认报文段时，可认定发生了丢包，立刻重发该报文段。同时视作丢包，慢启动阈值/2，CWND设为初始值。
如果没有FRR，数据包丢失后，TCP会使用定时器要求传输暂停。在暂停的这段时间内，数据包不能被发送。而FRR可以快速重传、无需暂停。

快速恢复
P596 Fast Recovery
个别报文段的丢失不代表网络发生了拥塞，将拥塞窗口减为1会降低传输效率、所以当发生个别报文段的丢失时（或检测到3个重复ACK，视为丢包），采用快速恢复：阈值/2，但CWND变为阈值（+3），不会变为初始值，跳过慢启动。

流量控制
就是让发送方的发送速度不能太快，让接收方来得及接收，这是利用滑动窗口机制实现的。缓存区域存放的都是基于字节流的数据，当接收方处理不过来的时候就要减小接收窗口的大小，甚至设置为0。接收窗口不为0后，接收方会发一个报文通知发送方，为防止死锁，发送方也会启用一个定时器，每隔一段时间确认一遍接收窗口的大小是否改变。

NAT
P470
一些网络内部可以分配很多的IP地址（内网），但这样的IP会和整个网络上的很多重复。
有这些IP的设备在访问公网前，NAT box/firewall会进行其IP地址的转换。
通过NAT，一个IP地址可实际包含多个IP。
静态转换：将内部网络的私有IP地址转换为公有IP地址，IP地址对是一对一、永远不变的。
动态转换：将内部网络的私有IP地址转换为公用IP地址时，IP地址是不确定的、随机的（但合法）。

输入网址到获得页面的过程
见 HTTP。

拥塞控制和流量控制的必要性，只有一个可以吗
流量控制强调控制端与端之间的流量，保证发送方成功发送、接收方的正确接收（不溢出缓冲）。
拥塞控制是一个全局性的问题，需要控制网络中各个节点的流量。
都需要，缺了哪个都会体验很差。

TCP三次握手
P534 574

• TCP 中的状态标识（均为1位）：
  ACK：连接建立后的所有报文，ACK 必须为 1，否则信息无效。
  SYN：在连接建立时用来同步序号。当 SYN=1、ACK=0 时，表明这是一个连接请求。如果同意建立连接，则在响应报文中令 SYN=1、ACK=1。所以 SYN=1 就表示这是一个连接请求或连接接受报文。
  FIN：表示发送报文方的数据已发送完毕，请求释放连接。
• 握手时会进行同步序列号。为了保证数据有序传输，以及数据丢失后进行重传，通信双方都要保存对方的序列号（是全双工的），使本地应用按序处理数据包。（可以一次传多个到缓冲区）
  握手时传递的序列号，确保回复对象是正确的。
• 握手时不能使用相同的序列号（如0，避免早先发送的包再次到达导致错误）；也不应顺序递增编号，应随机（避免被伪造序列号，和错误的主机建立链接）
• SYN泛洪攻击：如果listener要对每个sender的建立连接请求保存一个序列号，当有大量sender请求时（如一个主机大量建立不完成的连接），listener必须保存大量序列号。在早期内存很贵时，是很难存下的。而使用一个随机函数（以sender请求的序列号$x$作为参数）计算返回的序列号$y$，就无需保存$y$。在最后一次握手时，由sender的$SEQ=x+1$即可确认是否有$ACK=y+1$。
• 防止序号回绕可以在TCP头部额外选项中加时间戳。
• 三次握手相比二次，确保了双方间能够正常通信（具体问题见下）：
  第一次握手，客户端发送 SYN 到服务端，服务端可以确认自己的接收能力正常，客户端的发送能力正常。
  第二次握手，服务端发送 SYN 和 ACK 到客户端，客户端可以确认自己的接收和发送能力正常，服务端的发送和接收能力也正常。
  第三次握手，客户端发送 ACK 给服务端，服务端也确认自己的发送能力正常，客户端的接收能力正常。
• 三次握手已经可以获取必需的信息了，但不能保证连接真正建立、第三次消息没有丢失。
  但即使进行第四次握手，也无法保证第四次消息也没有丢失。
  所以实际无论多少次都无法完全保证连接成功建立、没有信息丢失。
  （在消息可能丢失的 不可靠信道上 试图通过消息传递的方式达到一致性 是不可能的）
  建立失败的连接会在超时后重置（sender会尝试重新发送，发送多次后关闭。receiver发送给已关闭的sender，会收到reset）。

三次握手 只用 2 次有什么问题？

应该有很多。

1. 如果已失效的连接请求又传到了服务端。服务端依旧会回复连接，并在回复后就认为连接已建立，会等待客户端发送数据，浪费资源。
2. 即使服务端不能正常发送消息，也会认为连接已建立，等待客户端发送数据。
   如果没有第三次握手，它并不能确定自己能否成功发送消息。

第三次握手失败/丢包了怎么办

服务器收到建立连接请求后，会定时不断发送接受连接信息。
如果客户端还是长期未响应，就发送 RTS 连接重置报文，关闭连接。客户端也应关闭连接。

第一、二次握手的数据包同样，会在超时后重传，在一定时间后放弃。

TCP 有一个 keepalive timer (保活计时器)，如果连接长期空闲超过该时间，则检查另一方是否还在，如果不在就关闭连接。

四次挥手 timewait，closewait状态

1. sender发送FIN x，进入FIN_WAIT_1状态（表示无数据发送，但还可接收）
2. receiver收到后确认，发送ACK x+1，进入CLOSE_WAIT状态，等待发送完后关闭连接。
   sender收到后进入FIN_WAIT_2状态。此时一方已关闭连接。
3. receiver接收完数据后，发送FIN y，进入LAST_ACK状态，等待接收最后的报文 ACK。
4. sender收到后确认，发送ACK y+1，进入TIME_WAIT状态。receiver收到后，直接进入CLOSED。
5. sender发送ACK y+1后，等待2MSL（2*最大报文段生命周期），进入CLOSED。

等待原因：确保receiver没有重发FIN y。不等待直接CLOSE可能导致receiver不能关闭连接。若receiver重发了FIN，则sender需重新发送确认、重新等待2MSL。

SYN 泛洪攻击

攻击方利用伪造的IP地址向被攻击方不断发起连接请求，被攻击方发出的响应报文将永远发送不到目的地，从而会不断等待关闭连接、浪费资源。
处理方式：限制同一 IP 的连接次数。延迟分配连接资源：在第二次握手时随机返回一个值，不分配资源；在第三次握手并确认随机值正确后，才分配资源。

粘包

TCP 会将数据转换为字节流发送，并根据实际情况调整发送速度、报文大小。
比如：发送数据前可能会短暂等待，以便充分利用发送缓冲区、减少发送次数；当接收方的缓冲区过小时，减少发送的报文大小。
所以，应用无法决定 TCP 每次发送的数据大小。TCP 会按照实际情况，自己对数据流进行切分。
所以，如果应用用同一条 TCP 链接发送 消息A 和 消息B，TCP 可能会将它们连在一起发送，这就是粘包；TCP 还可能将 消息A 拆成多个报文（比如缓冲区不够大），这就是拆包。
所以，如果要用同一条链接发送不同的数据，应用要自己定义消息之间的边界，不能靠 TCP。
如果建立 TCP 的功能单一，比如就是为了传递某个文件，则不需要区分消息的边界。

在数据流中实现消息区分的方法：

1. 每条消息前，记录消息的长度。
2. 统一规定消息的长度。
3. 在消息尾部设置结束标识符。

UDP 是可以区分消息边界的，因为 UDP 面向数据报，会以数据报为单位接收和处理，只要在不同数据报中发不同消息即可。

IP 与这个问题无关，因为 IP 是更底层的协议，只是对 TCP 或 UDP 做封装、实现路由，上层怎么做的不管。应用的数据是与 TCP 或 UDP 直接相关的。

IPv4
P457 网络层
https://zybuluo.com/SovietPower/note/1912189

TCP
P574 传输层

• TCP头部和IP头部各占20B，所以TCP的数据最多为$65535-40=65495B$。
• TCP的16位端口号和IP的32位IP地址可以唯一确定一个连接终端。TCP连接是个五元组：(TCP, srcIP, srcPort, desIP, desPort)。

UDP
传输层
头部仅由4个16位（2B）构成：源端口号、目的端口号、长度、校验和。

TCP 与 UDP

1. TCP面向连接，开始前需先建立连接。UDP无连接。
2. TCP提供可靠的服务，无差错，不丢失，不重复，且按序到达。UDP尽最大努力交付，不保证可靠性。
3. TCP面向字节流，把数据看成一连串无结构的字节流。UDP面向报文，是一个一个独立的包。所以 TCP 会有所谓的粘包问题。
4. TCP有拥塞控制，会根据网络调整发送速率。UDP没有，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）（但也可能填满接收方的缓冲区）
5. 每一条TCP连接只能是点到点的。UDP支持一对一、一对多、多对一和多对多的交互通信。
6. TCP头部开销20字节。UDP的头部开销小，只有8个字节。
7. TCP用于可靠性要求高的场景，如文件传输、发送邮件、远程登录。UDP一般用于实时通信、游戏。
8. TCP是一个有状态服务，必须保证无差错。UDP是无状态服务，发出去就发出去了。

HTTP/3使用UDP，是 Google 提出的基于 UDP 改进的通信协议，其目的是降低网络通信的延迟，提供更好的用户互动体验。取代使用TCP的HTTP/2。

TCP 与 UDP 的具体的不同应用场景

TODO

TCP 如何保证可靠传输

每条消息在收到后都会进行确认；如果发送方一定时间没收到确认，就重发。
每条消息都会进行编号，接收方会按照顺序处理，保证没有丢失和乱序。

UDP 如何实现可靠传输

类似 TCP，要给每个包加序列号，接收方收到后必须进行确认，发送方在收不到确认时，超时重发。
基本和 TCP 一致，但不受 TCP 拥塞控制、发送窗口的限制，见下 TCP 的缺点。
不受拥塞控制限制，可能会短期提升发送效率；但如果网络长期拥堵，不加拥塞控制只会更慢。但现在一般不会有这种情况。
在丢包后，发送窗口会变小，影响发送。但现在一般是快速恢复，影响应该也不算大。

TCP 的缺点

• 发展和迭代速度慢：是基于操作系统内核实现的，想要更新必须所有机器的操作系统都更新。
  而 QUIC 是基于客户端实现的，只需要用户和服务器的应用程序支持就可以，不依赖系统，可以快速更新。
• 拥塞控制：这个对网络整体来说是优点，但对特定应用和用户来说可能是缺点，因为他们会想让自己的数据优先发送，或按特定策略控制，不被 TCP 调节。
• 建立连接的延迟高，等待时间长：TCP 建立连接很可靠，但也确实比较慢。包括 TCP 3次握手和 TLS 4次握手，而且最初的发送窗口较小。
  之后引入了 fast open，TCP 完成连接后，将信息保存到 cookie 里。下一次建立连接时，如果发现 cookie 有效，就只进行两次握手。但旧的系统不支持该特性。还不太安全？
• 队头阻塞：首先 TCP 的发送窗口和接收窗口的大小都是有限的，任意时刻只能发送窗口内的数据；然后 TCP 要保证消息是有序的，所以如果一个较小序列号的消息没有成功接收，即使序列号更大的很多消息都被接收了，发送窗口和接收窗口也不能移动，不能发送和接收新的数据。
  如：假设窗口大小是5，消息 2,3,4,5 发送成功，但只要消息 1 没发送成功，就不能发送和接收消息 6，窗口的意义就不大了。
  此外，HTTP2 中实现了多路复用，可同时传输多个流 (stream)，但多个流共用一个窗口，所以一个流等待可能导致其它流都等待。
• 链接迁移需要重新建立连接：当客户端的网络状态发生变化，比如流量切换到 WiFi，它的 IP 地址会发生变化，必须断开连接、重新建立，会导致短时间的卡顿。
  TCP 连接是通过四元组 (源IP，源端口，目的IP，目的端口) 标识的。

QUIC 协议

QUIC (Quick UDP Internet Connections, 快速 UDP 因特网连接) 是 Google 基于 UDP 实现的可靠传输协议，是一个应用层协议。

特点：

• QUIC 在应用层实现了各种拥塞控制，不仅可以根据用户需求选择控制方式，还不受操作系统和网络底层设备的限制，只需要修改应用或浏览器的配置就可以，所以迭代、普及的速度可以更快。
  此外拥塞控制可以以流为单位进行，不同流可使用不同策略、不同流量。
• 建立连接延迟更低或没有：只需要一次握手就可完成建立连接和交换密钥。
  还支持 0-RTT 快速重连：如果之前建立过链接，则使用上一次的密钥建立链接，不经过完整的握手过程，且会在发送公钥的同时发送数据。但有一定安全风险。
  具体见 HTTP 3.0。
• 数据包的序列号是严格递增的。
  在 TCP 中，重传的数据包有和之前一样的序列号，会引入歧义：因为确认数据包的到达时间会用来估计 RTT，但这个确认可能是确认的原数据包，也可能是确认的重传数据包。这样估计的 RTT 是不准确的。而重传超时时间 RTO 是根据 RTT 决定的，所以会导致 RTO 不准确，重传的代价变高。
  在 QUIC 中，重传的数据包也有新的序列号，可以更准确地估计 RTT。同时也消除了队头阻塞问题。
• 没有队头阻塞（见上）：TCP 的接收窗口左侧，取决于序列号最小的、未收到的数据包，它会导致窗口不能移动。
  QUIC 的接收窗口左侧，取决于收到的最大序列号的包（不太准确，可以看这的图），这样窗口的移动就不受限于最早未收到的数据包。
  此外 QUIC 的每个流都有自己的窗口，互不影响。
• 链接迁移：QUIC 连接是通过 64 位随机 ID 识别的（还有密钥），所以即使设备的 IP 发送变化，也不需要重新建立链接。
• 会使用前向纠错机制：每发送 n 个包，就再发送一个这 n 个包的校验和。如果其中的一个包丢失，可以通过该包恢复，不需要重传。
  但现在不用了，因为有额外的带宽消耗，收益一般也不大。

QUIC 握手过程

如果双方是第一次连接，需要 1 RTT 协商密钥：

1. 客户端发起连接请求，询问公钥。
2. 服务端返回公钥。
3. 客户端发送公钥，同时开始发送数据。会用相应的密钥对数据加密。
4. 服务端发送数据。也会用相应的密钥对数据加密。

如果双方不是第一次连接，通过过去的公钥，可直接从第三步开始建立连接，0 延迟。

HTTP

HTTP 1.0，1.1，2.0，3.0

https://blog.csdn.net/itcsdn_/article/details/109518671

HTTP 1.0

• 客户端和服务器只保持短暂的连接，不久就会关闭。
• 每次请求都需要创建一个连接。

HTTP 1.1

• 支持长连接，一个 TCP 连接可以处理多个请求，减少了创建和关闭连接带来的消耗和延迟。
• 支持流水线/管道 (pipeline) 传输：普通 http 请求只能按照 一请求一响应 的顺序处理。如果两边支持 pipeline，客户端可以批量发送多个请求，而不需要等待响应；服务端收到请求后可以并行处理？但返回结果的顺序必须跟请求保持一致。
  但有队头阻塞问题：为了保证正确，结果必须按顺序返回，所以后面的请求必须等待前面的请求处理结束、发送回去，才能发送。所以并发性并不好，不常用。
• 提供了身份认证、状态管理和缓存机制。
• 支持文件断点续传。允许数据分块，利于传输大文件
• 对一个域名的请求允许分配多个长连接。

HTTP 2.0

• 不再使用管道，使用流去标识属于同一次请求的数据包（每个流有唯一 ID），使得同一个 TCP 连接中，客户端和服务器可以同时发送多个请求和多个响应，且不用按照顺序，解决了队头阻塞的问题，提供了并发性。
  通过流做到了多路复用？
• 使用 HPACK 算法压缩头部：客户端和服务器同时维护一张头信息表，发过的头部信息都会存入这个表，并有对应的索引号，后续只需发送索引号即可。
• 允许服务器主动向客户推送数据，不需要用户请求。
• HTTP 1.1 中，header 只能包含 ASCII 字符，body 任意，可指定。为了提高传输效率，HTTP 2.0 的头部也使用二进制传输。
• 可基于 HTTPS，更安全？

HTTP 主要依托于什么协议？

3 是基于 UDP 的，其余基于 TCP？

HTTP 3.0（为什么用 UDP）
UDP 可能丢包、重复，为什么使用 HTTP 3.0 还能得到完整的网页、图像等？

TCP 有一些缺点，QUIC 基于 UDP 实现了同样可靠但效率更高的协议。
见 计网 - QUIC 协议。

对于 HTTP/1 和 HTTP/2 协议，TCP 和 TLS 是分层的，分别属于内核实现的传输层、openssl 库实现的表示层，因此它们难以合并在一起，需要分批次来握手，先 TCP 握手（1RTT），再 TLS 握手（2RTT），所以需要 3RTT 的延迟才能传输数据，就算 Session 会话服用，也需要至少 2 个 RTT。

HTTP/3 在传输数据前虽然需要 QUIC 协议握手，这个握手过程只需要 1 RTT，握手的目的是为确认双方的「连接 ID」，连接迁移就是基于连接 ID 实现的。

HTTP/3 的 QUIC 协议并不是与 TLS 分层，而是 QUIC 内部包含了 TLS，它在自己的帧会携带 TLS 里的“记录”，再加上 QUIC 使用的是 TLS1.3，因此仅需 1 个 RTT 就可以「同时」完成建立连接与密钥协商，甚至在第二次连接的时候，应用数据包可以和 QUIC 握手信息（连接信息 + TLS 信息）一起发送，达到 0-RTT 的效果。

HTTP 协议
https://www.nowcoder.com/discuss/819732?source_id=profile_create_nctrack&channel=-1

一个HTTP请求包括四部分：请求行（request line）、请求头部（header）、空行和请求数据。
HTTP响应也由四部分组成：状态行、消息报头、空行和响应正文。
HTTP 请求可以使用多种请求方法。

输入页面后的HTTP请求过程
1. 通过 DNS 解析，将域名映射到 IP 地址：
浏览器搜索自身的DNS缓存，如果找到则返回 IP；
否则，浏览器就向本地域名服务器请求查询 IP，如果存在，则返回 IP；
否则，本地域名服务器发起一个迭代DNS请求，向更高级的服务器查询，最后将 IP 返回给本地主机。
2. 浏览器获得域名对应的IP地址后，建立 TCP 连接，进行三次握手。
3. TCP 连接建立后，浏览器向服务器发送 http 请求，发送 header、body 等数据。
4. 服务器接受请求，根据路径参数，由后端生成HTML页面文件，返回给浏览器。
5. 浏览器解析和渲染返回的页面，如果遇到引用的外部JS、CSS、图片等静态资源，对每个都再次发送HTTP请求，让服务器返回数据。

get、post 方法有什么区别

https://www.zhihu.com/question/28586791

浏览器本身发送请求时：

• GET 的参数都在 URL 中，POST 的参数在 body 中。
  因此 GET 不安全，不适合传递敏感信息；POST 相对安全（也要加密）。
  因为 URL 长度一般有限制， GET 传递的参数不能很长（如 <2KB），但 POST 可以（如 8MB）。
• GET 是幂等的，可能会被缓存；POST 是非幂等的，不可缓存（一般是要做出恰当的、实际的更改）。
• 语义不同，GET 一般用于获取资源，POST 用于提交或执行操作。
  不过这个区别是人为规定的，如 RESTful。

如果使用ajax或工具等发送请求，只要符合HTTP格式的请求都可以。没有什么区别。
只是不用 GET 做提交是一个共识，浏览器也会特别对待。

RESTful

规定前后端的接口规则。

1. 每一个 URI 代表1种资源。
2. 客户端使用GET、POST、PUT、DELETE 4个表示操作方式的动词对服务端资源进行操作：GET用来获取资源，POST用来新建资源（也可以用于更新资源），PUT用来更新资源（一般需指定一个能标识资源的标识符），DELETE用来删除资源。
3. 通过操作资源的表现形式来操作资源。
4. 资源的表现形式是XML或者HTML。

http 如何实现长连接

在头部中设置Connection:keep-alive，建立TCP长连接。（短连接：Connection:close，一次请求/响应后，就会关闭连接）
客户端和服务器之间用于传输HTTP数据的TCP连接不会被很快关闭。如果客户端再次访问这个服务器，会继续使用这一条已经建立的连接。
服务器会定时检查客户端的状态，有几种可能：

1. 客户端正常，过段时间再检查。
2. 客户端挂了，主动close。
3. 客户端挂了，但是重启了，客户端发送RESET，服务器close。
4. 客户端无响应，重发几次后若依旧无响应，close。

强缓存 协商缓存

https://www.jianshu.com/p/9c95db596df5/

HTTP 缓存包括强缓存和协商缓存。
服务端在返回请求时，可以在 response header 中通过 cache-control 配置。
为cache-control: no-cache时没有强缓存，但可以设置协商缓存；为cache-control: no-store时不缓存。

强缓存：在资源过期前，不会再请求服务端，而是直接返回本地缓存。
例：cache-control: max-age=360, public, immutable，资源的过期时间是360s，public 表示可以被浏览器和代理服务器缓存（private 则代理不可缓存），immutable 表示即使用户刷新页面，也不会发送请求（不加的话，只是新打开页面时使用缓存，刷新后会发请求）。

协商缓存：每次都请求服务端，并在请求中附加 etag（一个文件的哈希值），当请求的资源没有发生改变，即 etag 没变时，服务端返回 304，客户端直接使用本地缓存；否则资源发生改变，服务端返回 200 和新的资源。

HTTP状态码
https://www.nowcoder.com/discuss/819732?source_id=profile_create_nctrack&channel=-1

其中206 (Partial Content) 的作用：
http1.0中，如果只需要对象中的一部分，但每次请求都要返回整个对象，造成性能浪费。
http1.1可以通过在请求头设置range，请求资源的某一部分，此时的返回码为206。
请求资源的一部分即断点续传。如用户需要下载一个大文件，可将这个大文件分成几部分，然后多进程同时进行。在请求头中设置range字段，可规定分割的byte范围。
服务端会给客户端返回一个包含content-range的响应头，相应分割byte的范围。
请求头中：Range: bytes=0-801（一般请求下载整个文件是bytes=0-或不用这个头）
响应头中：Content-Range: bytes 0-800/801（801：文件总大小）

常见浏览器跨域问题？

HTTP 与 HTTPS

HTTPS (Hypertext Transfer Protocol over Secure Socket Layer) 是以安全为目标的HTTP通道。

• https协议需要到ca（证书权威机构）申请证书，来保证服务器的身份是可信的，一般需要交费。
• http是超文本传输协议，信息是明文传输。https 则是具有安全性的SSL加密传输协议。
• http使用80端口，https使用443。
• http的连接很简单，是无状态的。

HTTPS 是在 TCP 和 HTTP 网络层之间加了 SSL/TLS 安全协议。
HTTPS 在 TCP 三次握手 建立连接后，还需 SSL/TLS 的握⼿过程（通过非对称加密，协商对称加密使用的密钥）。

HTTP 的安全风险
明文传输导致：
窃听：如通信链路上可以获取通信内容，盗取账号。
篡改：如强制植入垃圾广告，视觉污染。
冒充：冒充淘宝网站，骗取钱财。

HTTPS加密保证了：
信息加密：交互信息无法被窃取。
校验机制（会生成一个数字摘要/签名）：无法篡改通信内容，篡改了就不能正常显示。
身份证书：证明淘宝是真的淘宝网。

HTTPS 的 CA 证书工作原理

RPC 是什么

在哪一层

gRPC是什么
https://zhuanlan.zhihu.com/p/411315625
https://www.jianshu.com/p/9c947d98e192

gRPC为什么高效

gRPC用的什么协议？TCP三次握手？四次挥手？FIN-WAIT-2是什么时候的？

RPC有哪几种
gRPC的服务类型，分为一元RPC、服务端流式RPC、客户端流式RPC、双向流式RPC。

OS

源程序到可执行程序的过程

https://zhuanlan.zhihu.com/p/144589490

以 C 为例：

1. 预处理/预编译(preprocessing)：.c文件经过cpp（C预处理器）生成.i文件。
   替换预处理指令：替换宏定义，决定#ifdef的部分是否编译，导入#include的文件。

2. 编译(compilation)：.i文件经过ccl（C编译器）生成.s汇编文件。
   主要的优化都在编译过程中进行，所以编译会很复杂。

3. 汇编(assemble)：.s文件经过as（C汇编器）生成.o可重定位目标文件（二进制文件），也就是机器代码，对解释执行的语言则是对应虚拟机的字节码。
   除了将汇编翻译为机器指令，汇编器还会生成数据和表（与目标文件格式相关）。但在连接之前，它并不知道数据和代码会在内存的什么位置运行，也不知道那些本地引用的外部定义的全局变量和函数的位置（会标明undefined，之后再找）。
   汇编还会将各函数调用(callq f)替换为地址，但也不是运行时的有效地址，只是一个占位符。

4. 链接(link)：连接多个目标文件（包括各种动态链接库，比如libc.so(GNU C Library), .dll），生成可执行文件。

上面的4步有时候也统称为编译：源代码->词法分析->语法分析->中间代码生成和优化->汇编代码->机器码的过程。整个编译器也包括汇编器和链接器。

链接

在写大项目时经常把源程序放在不同的文件中，编译后再将它们链接成一个文件（gcc -o name a.c b.c c.c自动执行）。
放在不同文件中有以下好处：

1. 模块化：结构清晰；方便封装成一个库，供之后使用。
2. 效率高：改变某个文件时，只需重新编译这个文件，然后重新链接；可同时编译多个文件。

链接的主要工作：

1. 符号解析：将每个符号引用与一个符号定义关联起来。
2. 重定位：合并相同的节；重定位各个符号位置；更改引用符号的地址。

符号解析和重定位与可重定位目标文件的格式有关。

gcc -c表示只编译、汇编但不链接（对未定义符号不会报错），而gcc -o会进行链接（会试图查找未定义符号）。

目标文件

目标文件有三种：

• 可重定位目标文件（.o文件）

  • 包含代码和数据
  • 可与其他可重定位目标文件合并组成可执行目标文件
  • 每个可重定位目标文件都由一个.c文件生成

• 可执行目标文件（如默认的a.out文件）

  • 包含代码和数据
  • 可直接加载到内存中执行

• 共享目标文件（.so, .dll文件）

  • 一种特殊的可重定位目标文件
  • 可加载到内存中与可执行目标文件进行动态链接

a.out 意为 assembler output，但它不是汇编程序输出，而是链接器输出，只是以前没有链接所以就直接是汇编输出。

目标文件是以特定的文件格式存储在磁盘上的，各个系统的目标文件格式都不相同。
Linux 系统使用的是可执行可链接格式(Executable and Linkable Format, ELF)。ELF是.o文件、a.out文件和.so文件的一种统一的格式。

ELF文件格式

section(节)是ELF文件中的最小组织单位。一个段一般包含几个section。
符号是程序中的函数、全局变量以及静态变量。每个可重定位目标文件都有一个.symtab section，该节是一个符号表，包含该模块m定义和引用的符号的信息（符号解析过程要解析的符号）。

三种符号链接器符号：

• 全局符号：由模块m定义并能被其他模块引用，如非静态的C函数和非静态的全局变量。
• 外部符号：模块m引用的在其他模块中定义的全局符号。
• 局部符号：只能由模块m自己引用的符号，如静态的C函数和全局变量。

注意：局部变量不是局部符号。
静态变量和局部变量的区别：

• 存储位置不同：局部变量存储在栈上，静态变量存储在.bss或.data节。
• 作用域不同：局部变量的作用域是函数或循环体（代码块），静态变量由于存放在内存静态区，所以即使函数执行结束它的值也不会销毁，下次调用函数时仍然能用到这个值。

局部变量不保存在目标文件中，而是在运行时创建。链接器不需要知道局部变量是什么东西。

局部符号的解析：编译器保证每个模块中每个局部符号只有一个定义，所以只需要在本模块的符号表中查找。
对于不同函数体中定义同名的静态变量，编译器给它们不同的名字。

全局符号的解析：编译器遇到一个不在当前模块中定义的符号（变量或函数名）时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号条目，将它交给链接器处理。如果链接器在所有的输入模块中都找不到这个被引用符号的定义，就输出一条错误信息并终止。
多个目标文件可能会定义相同名字的全局符号，而全局符号有强弱之分：

• 强符号：函数和已初始化的全局变量。
• 弱符号：未初始化的全局变量。

Linux链接器使用以下规则来处理全局符号的多重定义问题：

1. 不允许有多个同名的强符号。
2. 如果有一个强符号和多个弱符号同名，那么选择强符号。
3. 如果有多个弱符号同名，那么从这些弱符号中随机选择一个。

全局变量可能会带来很多意想不到的问题，所以应该通过以下方法尽量避免这种意外的发生

• 如果可以的话，使用static（避免全局）。
• 定义全局变量时初始化（如果冲突能发现错误）。
• 引用外部全局变量时使用extern。
• gcc 使用-fno-common或-Werror选项。

重定位

将输入的多个可重定位目标文件合并为一个可执行目标文件。重定位由两步组成：

• 重定位节和符号定义：合并相同类型的节。
• 重定位节中的符号引用：更新代码节和数据节中对符号的引用。

装载

运行可执行文件时，因为不是shell的内置命令，所以shell会认为它是一个可执行目标文件，然后通过调用加载器(Loader)将它加载到内存中并运行。加载器在装载可执行目标文件时，根据程序头表(program header table)，将可执行目标文件中的节复制到内代码段和数据段，然后跳转到_start函数，_start函数调用系统启动函数__libc_start_main（定义在libc.so中），完成初始化执行环境，然后才调用main函数。

自定义库

https://zhuanlan.zhihu.com/p/144589490

方法1：用一个可重定位目标文件
可以自定义的库函数放在一个文件math.c中编译，在需要时链接：gcc main.o /usr/lib/math.o。
问题：
即使只使用里面的一个函数，也要链接整个目标文件；每个用到该库的程序中都会包含一份库函数的副本，浪费磁盘空间；即使只修改一个函数，也要重新编译整个文件。

方法2：静态库（可重定位目标文件）
把每个函数单独放在一个文件中，编译为独立的目标模块，然后把这些模块封装成一个单独的静态库文件：gcc -c atoi.c printf.c ...、ar rcs libc.a atoi.o printf.o ...（ar为archiver，归档为一个库libc。静态库用.a(archive)作为后缀）。
优点：
修改一个函数，只需编译该函数的文件，不需要重新编译所有；链接时，链接器只赋值被程序引用的目标模块。
问题：
如果静态库更新，需要显式地将程序与静态库重新链接（程序也要更新，对发布的应用影响很大）；几乎每个程序都会用到一些公用库函数，如标准IO函数printf和scanf，这些函数要在每个可执行文件和进程中都有一份拷贝，浪费磁盘和内存资源。

方法3：动态共享库（共享目标文件）
共享库被动态链接到可执行模块，磁盘和加载到内存中的一个共享目标文件可以被多个进程使用，节省了磁盘和内存空间。
动态链接不是在生成可执行文件时链接，而是运行或装载时才链接。分为两种：

• 加载时动态链接：可执行模块初次加载和运行时与共享库链接。Linux中很常见，由动态链接器自动完成。
• 运行时动态链接：可执行模块开始运行之后与共享库链接。在Linux中通过调用dlopen完成。

但有的说法是，动态链接实际上并没有节省空间，因为多数情况很难实现真正意义上的共享，且很多函数也用不到。但它带来了严重的安全问题（动态链接库中的代码被引用后，可以访问程序的本地数据；很多程序不会验证加载的动态链接库有没有被掉包；链接库被一个高权限程序引用后，可以执行一些高权限的敏感操作；所有调用该动态库的程序都会受影响）。
也有人说，如果没有好的包管理器（如windows），很多应用依然会重复安装或自带一些动态链接库，导致并没有节省硬盘空间。

动态链接库

https://www.zhihu.com/question/389126944

在引用标准库函数时，需要#include对应文件，而这些头文件仅仅是提供了大量标准函数的声明（在预处理时导入），这些外部符号要由链接器在一系列目标文件（动态链接库）中找到（gcc -o ..会自动为我们链接一些标准库，但基本的ld不会）。这些标准函数已经提前编译成了目标文件，放在链接库中（.so或.dll）。
一个编译好的函数，本质上是一段二进制数据（一组指令），可以反汇编成汇编。
调用一个函数，实际上就是找到这个函数对应的那块二进制数据的首地址，让CPU从这个位置开始执行。当然还要各种约定：调用者当前的执行位置如何保存（以便函数返回）、参数的压栈顺序、寄存器的保存与恢复由谁、怎么进行等。

如果func是一个定义在某个动态链接共享对象中的函数，那么链接器将会将这个符号的引用标记为一个动态链接的符号，在链接时不对它进行地址重定位，将这个过程留在装载或运行时再进行。

extern

extern 声明一个全局变量或函数，该变量或函数可能是在其它模块（其它源文件）中定义的。
即使当前模块没有定义 extern 对象，但在编译时该声明不会出错。会在链接时在其它模块中找到对应的变量或函数。

定义与声明是不同的。对于变量，不加 extern、或设置了初值，就是定义；对于函数，写明函数体是定义，否则是声明。
定义只能出现一次。

static 声明的函数与全局变量，称为局部符号，只能被当前模块所使用（类似类中的 private）。

后面可以加 "C"，表示按 C 的规则翻译函数名，而不是 C++ 的规则（涉及重载），用于 C 与 C++ 的混合编程。
如：extern "C" void func(int a, int b)，C 会将函数名编译为_func，C++ 会编译为_func_int_int。
后面可以加大括号，来声明一系列函数。注意 C 中没有 "C" 的用法，只在 cpp 里有。

函数调用过程

先mov保存参数到栈，然后调用call func，返回时调用ret。
过程调用通过call Q实现：该指令会先把下一条指令的地址 即返回地址 压入栈中，然后将 PC 设置为 Q 的起始地址，并保存当前寄存器。
过程返回通过ret实现：该指令恢复寄存器，将返回地址弹出并赋给 PC。

内核态与用户态

是操作系统的两种运行状态。内核态可以访问任意的数据和硬件，可以执行特权指令；用户态只能访问自己用户空间内的数据，只能执行部分指令。

在指令集中，某些指令是比较危险的，如果错用可能导致系统崩溃。
Intel 将指令集分为四个权限等级：ring 0,1,2,3。ring 0 权限最高，只能被操作系统使用；ring 3 权限最低，是应用程序能使用的指令；ring 1,2 可用于驱动程序，但很少用。
如果应用程序调用更高等级的指令，则会发生非法指令错误。
常见 ring 0 指令有：IO 读写，内存申请，访问硬件资源。

内核态与用户态的信息交互

内核态可直接读取用户态的信息。

用户态通过系统调用获取内核态信息。
在 Linux 中，有一个伪文件系统 procfs (进程文件系统)，保存在内存中，通常挂载在/proc目录下。
内核通过该目录下的文件，向用户态展示自己的一部分信息。用户态通过读写里面的虚拟文件，与内核态交互。
还有一个 netlink，本质是一个 socket，可以实现用户态与内核态的信息传递。

进程 线程 协程

进程是资源分配的基本单位，线程是os调度的基本单位。

进程间不共享任何资源（但子进程与父进程初始时共享内存页表，写时才复制）
线程间共享代码、数据（所有全局、静态变量）、文件、堆内存（就是进程资源）。寄存器和栈是独立的。
线程切换开销小，只需要保存、恢复寄存器；进程切换要保存、恢复进程信息（此外因为数据不一致，内存页集合差异大，会导致TLB缓存失效）。

此外，进程的创建和销毁需要分配进程资源，开销比线程高很多。
共同的开销还有：用户态和内核态切换（涉及内存、CPU、中断线程等高权限操作），缓存失效（缓存的原理就是局部性）。

由于共享数据、切换开销小，线程可以并发执行并提高效率，但是有安全性问题，需要同步进制保证多线程环境的安全。

一个进程至少有一个线程，被称为主线程。主线程是进程的第一个线程，一般由父进程或操作系统创建。其它线程一般由主线程创建。
OS为每个线程分别在用户空间、内核空间创建两个栈，即用户栈和内核栈。
线程切换到内核态时使用内核栈，避免用户对其进行修改。

OS以链表形式保存各进程的信息。win中使用PCB，Linux中使用task_struct（或任务控制块TCB）。
进程信息中包含其线程信息。

并行 (parallelism)：同一时刻，多个任务可以同时进行。
并发 (concurrent)：在一个时间段内，多个任务同时存在，且都会有进展，但不一定在同一时刻。

多线程能充分利用多核，来实现并行（并行属于并发）。
而多协程对应的其实是并发。协程的并行也是靠线程实现的，所以线程还是不可取代的（如果让协程实现与核的绑定，还是要去内核态，就又成了线程了）。
此外，虽然协程的上下文切换开销小、更轻量，但能否在合适的时机被调度也是很难确定的。

进程包括什么

代码段、数据段、堆、栈，还有运行时的信息（如各寄存器的值）。
数据段包含全局变量，栈包含临时变量，堆包含程序动态申请的内存。
进程会用 进程控制块 (PCB) 表示，包含进程状态（就绪、等待、运行、终止）、寄存器、调度信息（如优先级、调度使用的参数）、拥有的 IO 设备列表、文件列表、父子进程信息等。

线程包括什么

自己的线程ID、寄存器组、栈。

线程共享进程的地址空间，线程栈是在进程内的。所以一个线程能够访问和修改另一个线程的栈，只要有一个指向该栈的指针就可。

协程为什么开销更小

线程切换需要借助内核完成，意味着用户态 -> 内核态 -> 用户态。（因为线程是操作系统提供的，其它线程的信息只有内核才知道。而协程是软件自己实现的，可以直接获取协程信息用于切换，还可以自由选择调度算法。但协程不能方便地实现抢占）
而协程切换 只在用户态就可以完成，不需要切换状态。

协程不使用轮转切换等调度算法（没有调度算法），只是按需切换。协程需要被激活的时候才切换过去，而且不管有再多的协程需要被激活，都得等前一个协程主动谦让才会触发切换（不能抢占）。
所以线程的无用切换次数比协程高很多。

当然，协程的创建、销毁、调度都是有开销的（占用内存、增加调度器负担、增加 GC 开销），不能滥用。
如果要频繁创建、销毁协程，可以建协程池，与线程池类似，见 Go - 协程池。

Go 协程的特点

1. 协程有独立的栈空间，共享堆内存。
2. 协程由程序调度和控制，不是操作系统。
3. 比线程更轻量，创建、调度开销小。

线程上下文切换的过程

1. 保存用户态的上下文（寄存器、用户栈等）。
2. 进入内核态，将用户栈切到内核栈，可能要拷贝用户态的参数，并进行操作和参数检查。
3. 在内核态执行指令，将结果拷贝回用户态。
4. 恢复用户态的上下文。

多线程

如果 CPU 是多核的，就可以同时执行多个线程，多线程可以充分利用 CPU。
此外，如果一个线程被阻塞或等待，CPU 可以调度一个新的线程来执行，不会没事做。

但多线程不一定比单线程更优。
如果一个线程一直使用某个共享资源或持有锁，可能导致其它线程始终无法执行，这就和单线程差不多了。
多线程也有线程间同步和调度的开销，比如可能大量使用锁。
如果性能瓶颈不在 CPU，而是硬盘或网络，则提高 CPU 的利用率也不会有太大提高。

线程调度算法

线程是调度的基本单位。同一进程中，线程的切换不会引起进程切换；从一个进程的线程切换到另一个进程的线程时，会引起进程切换。
线程分为就绪态、运行态、阻塞态（实际os不区分线程和进程？下面都写进程）。

批处理系统（操作少，目标是保证吞吐量和周转时间（提交到运行完成的数据））：

1. FCFS (先来先服务，first-come first-served)：非抢占式。按照请求的顺序进行调度。
   进程执行完才会释放，可能导致其它线程长期阻塞。
2. SJB (短作业优先，shortest job first)：非抢占式。按照预估运行时间最短的顺序进行调度。
   长作业的进程可能会饿死。
3. SRTN (最短剩余时间优先，shortest remaining time next)：抢占式。按剩余运行时间最短的顺序进行调度。
4. CFS (完全公平调度, completely fair scheduler)：见下。尽量让所有进程都能运行一样多时间。

交互式系统（交互操作多，要保证响应时间）：

1. 时间片轮转/轮询调度 (round-robin scheduler)：为每个需要的进程分配时间片。如果时间片太小，会导致切换过于频繁；太大，不能保证实时性。
2. 优先级调度：为每个进程分配一个优先级，按优先级进行调度。
   未执行进程的优先级可随时间推移增加，避免饿死。
3. 多级反馈队列调度 (MLFQ, multi-level feedback queue)：分配多级队列，以满足需长时间执行的线程。最常用。
   每个队列时间片大小依次递增，进程在第一个队列没执行完，就会被移到下一个队列。时间片小的队列会优先执行（如IO密集型？）。
   为不同类型的进程按需分配不同的时间片，也减少一个进程长时间占用 CPU 的情况（它的优先级会低）。

实时系统（软实时：如果定期未完成，则有惩罚；硬实时：如果定期未完成，则有严重后果）：

1. 单调速率调度 (RMS, Rate Monotonic Scheduling)：任务的周期越短，优先级越高。
   不能保证所有进程都及时完成。
2. 最早截止时限优先 (EDF, Earliest Deadline First)：任务的截止时限越近，优先级越高（动态优先级）。
   可靠，但代价很高，很少用。每个计时器中断都要计算每个进程的截止时间。

完全公平调度, CFS

使每个进程都尽可能“公平”地获得相同的运行时间，所以每次都选择之前运行时间最少的进程运行。可以进行抢占。
与其它调度不同的是，没有时间片概念，而是根据已经运行的时间 分配不同比例的 CPU 使用时间。
当然不是完全公平的，依旧有优先级的概念。

每个任务都会记录 虚拟运行时间 vruntime，每次选择 vruntime 最低的任务执行。高优先级的进程 vruntime 增长慢，低优先级进程增长快。
通过红黑树实现。维护最左节点，可以 O(1) 获取要执行的任务。

是抢占式的。比如，相同优先级的 IO 密集型任务和 CPU 密集型任务，由于 IO 密集任务经常阻塞，每次调度占用的时间短，所以 vruntime 会小于 CPU 密集任务，使得它被优先执行。当 CPU 密集任务在执行，而 IO 密集任务就绪后，可能会进行抢占。

优先级通过 友好值 (nice value, -20~+19) 定义，较低的友好值有更高的优先级，会得到更多的 CPU 时间（对其它进程不友好，获得了更多执行时间）。
拥有更高优先级的任务，它的 vruntime 增长的越慢。比如可以令每次 vruntime 增长的值为 实际执行时间*进程权重/(所有进程的权重和)(?)，或 实际执行时间*进程权重/1024。（这个算法不确定）
当友好值为0时，进程权重为 1024，所以它的 vruntime 就等于实际执行时间。
但对于友好值小的进程，进程权重可能远大于 1024，导致 vruntime 执行很慢，拥有更多的 CPU 时间。

任务的优先级有两个范围，一个用于实时任务，在 0~99 间；另一个用于普通任务，在 100~139 之间，根据友好值决定优先级是多少。
这个优先级越低优先级越高，所以实时任务总会优先执行。

新进程的 vruntime 不是 0，而是当前运行队列中 vruntime 的最小值，所以它会优先执行，但不会执行太久。

Linux 的进程调度算法

CFS 是 Linux 默认的调度算法。
此外，Linux 的进程被分为若干调度类，每个调度类有不同优先级、不同调度算法。调度时选择最高优先级调度类中 优先级最高的进程。

windows 的进程调度算法

使用抢占式的优先级调度算法。

任务的优先级分为两类：可变类：优先级在 1~15；实时类：优先级在 16~31。分别使用不同的队列。
每个类中的线程还有一个相对优先级。实际的优先级由优先级类和相对优先级决定。
可变类中的线程优先级是可变的，可以自己设置。
如果一个可变优先级的线程用完了时间片，它的优先级会变低，以此限制计算密集型程序的 CPU 占用。
当一个可变优先级的线程从等待中释放时，会提高优先级。比如等待键盘输入的线程会得到很大提升（提高相应速度），等待磁盘 IO 的线程会得到部分提升。

优先级反转 问题

低优先级进程如果获得了临界资源（如锁），会阻塞高优先级进程的执行，导致低优先级进程反而先执行。
解决：优先级继承（掩耳盗铃的感觉）：
为系统资源设置优先级，比所有共享该资源的进程的优先级都高；
任何进程从OS请求该共享资源时，将优先级提升为该资源的优先级；
该进程返回资源后，将优先级恢复为原优先级。

多线程 和 多进程的区别及应用场景

都可以通过并发提高效率。
但多进程需要更多的系统资源和进程切换、通信的开销，多线程需要使用同步机制保证线程之间的安全，实现复杂。
具体根据场景决定。

多线程由于共享资源，可能造成竞争或不安全状态。编程复杂度更高。
多进程实现和调试更方便，但进程的创建、切换、通信开销要高很多。

线程间可以直接读写共享变量来通信（如锁、信号量），进程需要其它 IPC (Inter-Process Communication) 方式通信。
线程通信的开销很小，但是要考虑冲突；进程的通信更安全，互不影响，但开销大。

进程间通信方式 IPC

进程同步：控制多个进程按一定顺序执行。
进程通信：进程间传递信息。是进程同步的一种手段。

IPC 有两种基本模型：共享内存、消息传递。

1. （匿名）管道 (pipe)：也叫普通管道，是单向的。只能在父子进程间通信（因为子进程继承了父进程的文件，而管道是一种特殊的文件，所以子进程也继承了父进程的管道）。
2. 命名管道 (FIFO)：类似管道，但能在任意进程间通信。能双向传输，但只能是半双工通信（双方都可发，但同时只有一方能发）。
3. 消息队列：不会使发送者阻塞；可以实现消息的随机查询，接收者可有选择的接收。
4. 信号量：是一个系统资源，在多个进程间共享计数器，以控制对共享数据对象的访问。
5. 共享内存：进程共享一片内存区域。因为数据不需要在进程间复制，所以这是最快的一种 IPC。
   多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。
6. 套接字 (socket)：可用于机器间的进程通信。
7. RPC。RPC 的消息有明确的结构，不仅仅是数据包，会给出函数的标识符和参数。

线程间通信方式
锁、信号量、事件，及其他 IPC 方式。

虚拟内存

将虚拟内存中的地址（线性地址），映射到物理地址，从而让物理内存扩充为更大的逻辑内存。
操作系统将内存抽象成地址空间。每个进程拥有自己的虚拟地址空间，被划分为若干页(物理)或段(逻辑)(?)。虚拟地址空间逻辑上可以是连续的，但不需要映射到连续的物理内存，也不需要所有页都在物理内存当中，使得我们可以运行内存更大的程序（比如4G内存机器运行64位程序）、获得更多的虚拟内存（比如很多进程占用内存，但使用频率很低，可以将它们换入磁盘、空出实际的内存空间）。
映射转换由 CPU 的 MMU(内存管理单元) 进行，见下。
虚拟内存的地址最底端向上依次是：代码段 .text、已初始化数据段 .data、未初始化数据段 .bss、堆。地址最顶端向下是栈空间。

虚拟内存地址到物理内存地址的映射

进程通过自己的页表，将虚拟地址映射为物理地址。

每个进程的控制信息中（PCB或task_struct）保存了当前进程页目录的物理地址。
页目录是一级页表，存储二级页表的地址。每个页表存1024个物理内存页的起始地址，每个页4KB，所以二级页表能访问的地址空间为$1024*1024*4KB=4GB=2^{32}B$。所以32位下只需要二级页表就足够寻址。
所以一个虚拟地址的高10位确定一级页表中的条目，次高10位确定二级页表中的条目，即物理内存页，最后12位确定在页中的偏移量。

虚拟地址可以比物理地址长，不过这个例子中相等。
虚拟地址分为两部分：虚拟页号VPN、虚拟页面偏移量VPO。
TLB 是根据 VPN 进行映射的（一个 TLB 条目为一页），所以 VPN 可进一步分为：标记TLBT、组索引TLBI。
物理地址也分为两部分：物理页号PPN、物理页面偏移量PPO。
页表会将 VPN 映射到 PPN。为了加速映射，引入了缓存。

二级页表指向物理页地址。因为物理页大小均为4K，所以物理页起始地址是4K的整数倍，所以地址的低12位一定是0。所以每个物理页起始地址的低12位可用来表示该页的信息：是否可读、可写、可执行、是否已被映射等。

已映射过的地址，可保存到 TLB(Translation Lookaside Buffer) 中。若 TLB 中存在，则无需进行转换。
当前进程的页目录（一级页表）的物理地址，会保存到特定寄存器。进程切换时，寄存器保存的页目录也会改变，从而导致 TLB 失效。
每个进程拥有自己的页表，但 TLB 缓存是共享的。

地址映射的过程：

1. MMU 检查 TLB 中是否存在相应地址，存在则直接取出页表条目 PTE。
2. 如果 TLB 未命中，从缓存或内存中取出页表，找到相应的页表条目，并将其放入 TLB（可能会替换一个已存在的）。
3. 获得 PTE 后，将其翻译为物理地址（PTE 包含物理页号 PPN，虚拟地址包含页面偏移 VPO，合在一起就是实际地址）。

进程中不直接使用物理地址。在不同进程中，相同的虚拟地址也可映射到不同物理地址。
通过把同一组物理页面映射到不同进程的页表，可实现进程间共享内存。

当进程申请内存时，OS可能不会立刻分配内存，只记录一下当前的申请记录。实际的地址映射、分配会在进程访问该内存时，触发 Page Fault 时进行。页错误 Handler 会查询进程是否申请了该段内存，如果申请了，则分配物理页面、进行映射。若没有申请，则发送内存访问异常。
所以进程的虚拟地址空间只是可申请使用的范围，不一定都被映射到物理内存、可被合法使用。

进程间如何做到互不干扰/隔离
进程拥有不同的虚拟地址空间（即使物理内存可能重合），从而实现进程间地址空间的隔离。

分段

进程可以申请若干段作为自己的空间。每个段有独立的地址和映射。
页的大小不可变，段的大小可以动态改变，方便将程序划分为逻辑上独立的地址空间，有助于共享和保护。

页面置换算法
Belady异常：对某些页面置换算法，分配的页越多，缺页错误率反而可能增加
FIFO 就有这种问题。

最优置换算法 (optimal replacement algorithm)
置换最长时间不会使用的页面（置换下次使用时间最远的页面）。
无法实现。

LRU (最近最少使用算法) Least Recently Used，实际应为最早使用？
P276
置换最长时间没有使用的页（上次使用时间最早的页）。
使用最近的过去，作为最优算法中不远将来的近似。
实现方式：

• 时间戳：为每个页表条目保存上次使用的时间（CPU的逻辑时钟或计数器）。
• 双向链表：每当引用页面时，（若在链表中则先取出）将其放到链表顶部。则被置换的页面在链表底部。

LRU与最优置换都属于堆栈算法，满足“大小为n的内存页集合是大小为n+1的内存页面集合的子集”，不会有 Belady 异常。

近似LRU
很少有系统能提供足够的硬件，实现真正的LRU，代价高。所以需使用其它算法。
如：redis 随机采样几个，选择上次使用时间最早的，或用一个池维护多次采样中最早的几个。

额外引用位算法
为每页保存一个8位数，保存了最近8个周期该页的使用情况。该数的最高位表示当前周期是否使用了该页。每个周期将该数右移一位。
置换时选择编号最小的换掉。如果多个最小，全部置换，或在它们之间使用FIFO。
位数可选择。
额外引用位算法使用1位时，与第二次机会算法类似。

FIFO(先进先出)
换出最早被换入的页。会将经常被访问的页面换出，导致缺页率提高。

第二次机会算法
使用 FIFO 或循环指针决定替换的页面。
FIFO：队头的页如果引用位为0，换出，否则清零，将其放入队尾。仍需要链表操作，代价高。
循环指针：当选择一个页面后，若其引用位为1，则将其清零，尝试下一个；否则选择当前页置换。
页面被引用时，引用位会被置1。

增强型第二次机会算法
除了引用位，添加一个修改位，使用(引用位, 修改位)元组判断。
如果引用位相同，修改过的页面比未修改的页面有更低置换优先级（因为置换需要写出）。否则看引用位。

LFU(最不经常使用) Least Frequently Used
为每个页面的引用次数保存一个计数器。周期性右移计数器，已形成指数衰减的平均使用计数。
置换有最小计数的页面。
MFU(最经常使用) Most Frequently Used
置换有最大计数的页面（认为具有最小计数的页面可能刚刚被引入，还未使用）。

LFU MFU均不常用，代价高，实际效果差。

page cache

Linux 有 page cache，以页为单位缓存了文件系统的文件，以减少 IO 次数；还可以提供预读功能。
也有 buffer cache，会以块为单位缓存磁盘数据。如果不通过文件系统、直接读取磁盘，会使用这个 cache。
最初这两个 cache 会有数据重复，所以最后删除了 buffer cache（或者是合并了？）：文件系统与 page cache 交互，page cache 与磁盘交互。

中断处理

中断向量表中存放了各种中断处理例程的地址。
处理过程：

1. 屏蔽外部中断（FLAGS IF=0）。
2. 识别中断来源，确定中断类型。
3. 保存现场，将寄存器等数据入栈。
4. 执行中断服务程序，根据需要可选开放中断（FLAGS IF=1）。
5. 恢复现场，回到程序继续执行。

系统调用
因为系统调用数量多，不能都分配一个中断向量号。所以用一张系统调用表，通过系统调用编号获得函数入口。而中断向量表中用0x80代表进行系统调用。
用户程序将系统调用编号存入特定寄存器，通过寄存器或用户栈传递其它参数，然后用int 0x80（int为中断）触发系统调用中断，进行指定系统调用。

后来为了优化系统调用性能，使用特殊指令触发系统调用，无需先进行一次中断、查表。
如：x86的sysenter，amd64的syscall。

异常

异常包括：
中断：IO设备、时钟中断等外部信号，异步。
陷阱：有意的异常，同步，如系统调用。
故障：潜在的可恢复的错误，同步，如除0、缺页、段错误（读未定义区域或写只读区域）。
终止：不可恢复的错误，通常是硬件错误，同步。

除中断外，均为同步发生，即是执行一条指令的直接结果、由内部事件引起。

阻塞
进程被移入等待队列（移出就绪或运行队列），直到有信号将它唤醒。

CAS

CAS 可以代替锁，实现无锁、无阻塞算法。就类似自旋锁。
与锁相比，CAS 不会使线程休眠再唤醒，对于粒度比较小的操作能有更高的吞吐量。但如果共享资源要被长期使用，线程需要等待很久，CAS 就可能过于浪费 CPU；而锁可以使线程休眠，允许其它线程执行。

CAS 的加锁：while(!CAS(lock, 0, 1));，解锁：while(!CAS(lock, 1, 0));。

自旋锁

自旋锁是获取锁的一种方式：不断轮询等待锁释放。
另一种方法是阻塞，进程通知操作系统将自己挂起，或置入等待队列，等到锁释放（或信号，或下一轮时间片？）再尝试。

自旋锁可能避免不必要的上下文切换，但在申请不到锁时，会浪费CPU。

互斥锁 读写锁

互斥锁：只允许一个线程访问资源，无论读写。
读写锁：允许多个线程同时读资源，但只允许一个修改，读时不能修改。

读写锁可以有优先级：
读优先锁：只要有进程在读，写进程就阻塞。
写优先锁：如果出现写进程，则之后的读进程都阻塞，但当前的读进程继续。释放锁后，写进程能立刻获取锁。
公平锁：无优先级，按申请锁的顺序获得锁。

公平锁

公平锁：按申请锁的顺序获得锁。线程会进入等待队列。不会出现饥饿，但会影响吞吐量（除非只有一个线程使用锁，否则都会先阻塞）。
非公平锁：线程会尝试获取锁，如果正好获取到，则不等待，否则进入等待队列。会饥饿，但吞吐量高一些（会阻塞的线程更少）。

非公平锁有些类似 go，刚刚移出等待队列的线程，实际是在跟很多正在运行的线程争夺锁。
如果没有得到锁，它会被放到队头而不是队尾；如果长时间 (1ms) 都得不到锁，将锁切换到饥饿模式，直接给就绪队列的线程用。正在运行的线程不会尝试获得锁，而是直接进队列等待。
当饥饿状态的锁处理了一个等待时间很短的线程 (<1ms)，或等待队列为空了，它就变为正常状态，保证线程都没等太久。

乐观锁 悲观锁

乐观锁、悲观锁是两种设计锁的思路，或者两种处理并发冲突的策略。

悲观锁(Pessimistic Concurrency Control)认为数据时刻都可能改变，不加锁就会出问题，用于数据被并发修改、产生冲突的概率较大的情况。
常见的锁就是悲观锁：在使用前给数据上锁，使用后解锁，这期间只有自己能修改数据。

乐观锁(Optimistic Concurrency Control)认为数据不太会改变或冲突，不加锁也没事，用于数据不太可能产生冲突的情况。
一般会直接操作数据（不加锁），只有到数据提交时检查数据是否存在冲突。
常见实现：在表中增加一个版本号或时间戳，只有之前读的版本号与当前一致，才能进行修改，否则要重做。

乐观锁不用加锁、释放锁，但在写多或冲突频率高的情况下， 乐观锁可能导致大量重试。
如果要求高响应速度，则适合乐观锁，无论成功和失败都会很快给出结果，不需要等待锁。
如果重试的代价大，则适合悲观锁。

数据库锁 见应用：数据库。

局部性原理
时间局部性：被引用过一次的内存位置，将来很可能再被多次引用。
空间局部性：如果引用了一个内存位置，则将来很可能再引用它附近的一个位置。
如sum += A[i]这样的循环。sum时间局部性好，但没有空间局部性（标量）。A[i]时间局部性差，但空间局部性好。
步长（连续向量中，每个几个元素访问一次）越大，空间局部性越差。

取指令也有局部性（因为有icache？）。循环有好的时间、空间局部性。循环体越小，局部性越好。

饥饿

一个对象总是获取不到资源，导致无限阻塞。

死锁

一个过程长期没有进展，但又没有崩溃，可能是发生死锁。

死锁有4个必要条件：

1. 互斥：资源是互斥的，同时只能被分配给一个进程。
2. 占有并等待：一个进程至少占有一个资源，并等待另一资源，而该资源被其他进程所占有。
3. 非抢占：资源不能被抢占，只能在持有资源的进程完成任务后，由它释放。
4. 循环等待：存在一组等待进程{P0, P1,..., Pn}， P0等待的资源被P1占有P1等待的资源被P2占有，以此类推。

处理方法：

1. 鸵鸟策略：不管。用于死锁的概率很低、危害不大的情况，因为处理死锁的代价很高。
常见于复杂系统，如os。

2. 死锁检测与死锁恢复：不避免，及时发现和恢复。
检测方法：
如果每种资源都只有一个：通过检测资源分配图（有向图）是否存在环来实现。
如果一种资源可有多个：类似银行家，维护一个资源数组。

恢复方法：回滚；直接结束进程。进程的选择可取决于拥有资源数量、执行进度。

3. 死锁预防：彻底预防发生死锁。
破坏4个条件之一。
如：破坏占有且等待：规定所有进程在开始执行前请求所需要的全部资源。
破坏循环等待：给资源编号，进程只能按编号顺序请求资源。

4. 死锁避免：运行时避免发生死锁。
资源分配图算法：维护资源分配图，每次分配检查是否能成环。
银行家算法：没记。
但基本就是，每次进行分配前，检查分配是否是安全的（是否会导致死锁）。

内核分类

os 的架构分类。

1. 宏内核
将操作系统功能作为一个紧密结合的整体放到内核。
由于各模块共享信息，性能很高。

2. 微内核
将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。
在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。
进行 os 扩展非常方便，且大多数服务不在内核态进行，更安全可靠。
但因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

特殊进程

孤儿进程：父进程结束后，仍在运行的子进程。
正常情况下 父进程要 wait() 等待子进程结束。如果父进程先结束，剩下的子进程会被 init 进程接管负责，影响不大。

僵尸进程：子进程结束后，父进程没有用 wait()、waitpid() 等获取子进程状态信息，导致子进程残留的状态信息一直保留，占用进程号和资源。
进程终止后进入僵死状态，要等待通知父进程后才能完全结束，因为父进程可能需要获取子进程的信息。
如果结束或 kill 父进程，则僵尸进程会变为孤儿进程，由 init 处理，从而能够释放。

僵尸进程如何处理？
如果父进程结束，则 init 会处理。但有些时候不能很快结束父进程。
因为僵尸进程出现，是由于父进程没有处理子进程的结束信号，可以由父进程定期执行 wait 处理结束进程。

守护进程：一个特殊的在后台执行的进程，通常会重复执行某些任务，不与任何终端关联。

多路复用

https://www.zhihu.com/question/59975081

单个线程 通过记录多个 IO 流的状态，同时管理和监听多个 IO 流（多个 TCP 连接）。复用了单个线程。

最基础的通信方式，就是双方各创建一个进程，分别建立 socket （指定 IP 和端口），执行 listen 监听，然后 connect 建立连接，然后就可以执行 send 和 read 了（见这里）。

socket 是一个特殊的文件，所以会用文件描述符表示。
socket 是一套系统提供的接口，允许我们在软件编程中，通过函数调用实现 TCP 通信。

操作系统提供的 read 默认是阻塞的，所以传统的多进程模型是：每有一个客户端需要建立连接，就分配一个进程或线程进行处理，没有消息会阻塞。
当请求数很多时，创建、调度同样多的进程或线程的开销就很大了。
为此，引入了多路复用，允许一个线程处理多个连接。

我们知道 read 也可以是非阻塞的：没有数据时，立刻返回一个 -1。我们可以通过轮询一个 socket 数组、每次使用非阻塞 read 检查，实现一个简单的多路复用。
但问题是，每次调用 read 返回 -1，都是一次无效的系统调用，浪费资源。
所以，还是需要操作系统提供一个多路复用机制，让它在内核态检查一组 socket，而不是每个 socket 都进行一次系统调用。

Linux 下提供了三种多路复用的 API： select、poll、epoll。

Go 的网络模型就是多路复用的，会根据当前平台，决定使用的 API（Linux: epoll, win: iocp, Mac: kqueue）。
新建多路复用器为netpollinit()，注册监听事件为netpollopen()，查询就绪事件为netpoll()。

select, poll

通过 select，我们可以传递一组文件描述符，让操作系统进行遍历。标记出就绪的文件后，操作系统再返还给线程。
这个过程中有两次拷贝：首先将文件描述符列表拷贝到内核态，由 os 进行标记；然后 os 将标记后的列表传到用户态，供线程处理。
还有两次遍历：os 检查或标记就绪的文件，但不会告诉线程哪些文件就绪了，还是要线程自己遍历返回的列表。

所以 select 确实减少了系统调用次数，但没有避免遍历，还引入了拷贝，连接多时效率会很低。

select 与 poll 没有本质区别，不过 poll 使用链表维护描述符，去掉了 select 的文件描述符数量(1024)的限制（不过还受限于操作系统的文件描述符数量，65536）。
此外，它们都不是线程安全的，虽然一个线程能处理多组 IO，但不能使用多线程，只能多进程。

epoll

epoll (event poll) 是进一步改进，是异步的，可以发送通知，不需要进程一直检查和等待。

1. 内核态保存一个文件描述符集合，不需要每次传递，只需要告诉内核有什么修改（用红黑树保存。通过epoll_create创建 epoll、epoll_ctl更新）。
2. 内核不通过轮询找到就绪的文件，而是通过异步 IO 事件唤醒（事件驱动）。
3. 内核只将就绪的文件描述符返回给进程，不需要遍历（轮询O(n) -> O(1)）。

但是如果直接用这种非阻塞 IO，写起来比较麻烦，比如需要回调函数。
此外还是线程安全的？

epoll 的缺点 (epoll is not a better poll)：

• 高效的机制，逻辑和实现会更复杂，更难调试。
• 添加、修改和移除事件要通过epoll_ctl，需要进入内核态更新红黑树。而 poll 只需要在用户态修改文件描述符，下次传的新的就可以了。所以如果经常有大量的事件状态更新（read 变 write），或有大量的超短期链接，poll 可能更合适。
• 只有 Linux 支持 epoll，所以 select, poll 的可移植性更好。
• 如果事件就绪的频率非常高，那 poll 的轮询就不会很浪费性能，不一定比 epoll 差。

lt 与 et

epoll 有两种模式：水平触发 (level-triggered) 与 边缘触发 (edge-triggered)。
水平触发：对于接收方，如果缓冲区不为空，即有数据可读，就一直触发读事件；对于发送方，如果缓冲区不满，即可以继续写入，就一直触发写事件。
边缘触发：只有状态发生变化时，触发一次事件。对于接收方，就是缓冲区有新数据到来时（或从空变为非空？），触发读事件；对于发送方，缓冲区空出新的位置时（或从满变为不满？），触发写事件。
边缘触发还可设置阈值，来决定是否通知。

区别：

• epoll 中就绪队列维护了当前就绪的文件描述符，每次会取出队首进行通知。

• 水平触发在事件触发后，就再次放到就绪队列中，之后会继续通知，直到处理完毕。
  因为旧的事件会立刻放回队列里，可能会影响新事件的响应速度（好像影响并不大，因为毕竟公平）。
  不容易遗漏事件，不容易出 bug；但不需要的事件要及时移除，避免不必要的触发。

• 边缘触发在事件触发后，就从就绪队列中移除。
  所以边缘触发要求事件触发后，必须立刻处理完毕，否则就找不到它了。
  所以编程时要注意及时处理，避免遗漏事件。但这也提高了响应速度，新事件能够很快响应。

  此外，因为要求必须一次处理完，可能会导致饥饿：如果某个或某些文件描述符数据量太大，其它描述符会长时间不被处理。而水平触发更公平，可以只处理一部分后就处理下一个。
  不过一般发送接收的缓冲区都不会太大，一次要读的数据就不会太多。

• 水平触发还会导致 惊群现象。
  假设进程 A,B,C 都在等待文件描述符 fd 的输入。如果 fd 就绪了，epoll 会唤醒一个等待它的进程，比如 A，A 会读 fd。
  但如果 A 没有读完 fd，fd 会放回就绪队列，在不久后再次就绪。epoll 就又会唤醒一个等待的进程，比如 B，之后可能会唤醒 C。
  这种把所有进程都唤醒的操作可能是不需要的，因为只需要 A 唤醒往往就够了。所以 水平触发 会导致不必要的唤醒。

• 在 EPOLLOUT 事件上有区别，边缘触发的效率可能更高。
  使用 epoll 时，通过 epoll_create 创建 fd，通过 epoll_ctl 添加需要监听的 fd，并注册想监听的事件。
  常用的事件有两个，EPOLLIN, EPOLLOUT，前者是缓冲区可读，后者是缓冲区可写。

  当我们要发送数据时，如果缓冲区不足以一次将数据发完，我们就需要注册 EPOLLOUT 事件，在可写时继续写。
  如果我们使用水平触发，在这次发送完成后，必须注销 EPOLLOUT 事件，否则 EPOLLOUT 事件会一直发生，因为只要可写它就触发。但边缘触发不会，不用注销。
  而注册和注销事件需要加锁修改红黑树完成，如果每次发送都进行会影响效率。所以对一次发送的数据量大的应用，使用边缘触发；对每次响应数据较小的，比如 redis，可以用水平触发。
  不过有个解决方案是 oneshot，或 CAS 修改状态？

虚拟文件系统 (VFS)

VFS 是一个内核软件层，使得我们能用标准的 Linux 系统调用，读写位于不同物理介质上的不同文件系统，即为各类文件系统提供了一个统一的操作界面和应用编程接口。
VFS 是一个抽象层，提供了 open()、read()、write() 等统一文件接口，使我们不需要关心底层的存储介质和文件系统类型。

硬链接与软链接

两者都是为了给某一个文件，在另外一个位置，建立一个同步的链接，都会与链接对象进行自动同步。

软链接相当于快捷方式，只保存路径，如果原文件被删除，那软链接就失效。
硬链接相当于一个文件副本，与原文件一模一样，但不占用实际空间，与原文件指向同一个硬盘位置。
删除原文件不会导致硬链接失效。只要文件被某个硬链接指向，就不会被删除。

软链接比较简单，可以跨文件系统，可以对目录生成软链接。
硬链接只能在同一文件系统内创建，不能用于目录。

栈溢出

Linux 会限制程序的栈大小为 8MB，栈大小超过这个值就会导致运行错误。
栈大小限制是在编译时确定的。可以在通过编译参数，或在代码中指令添加指令修改栈限制。

限制的原因：
内存是很宝贵的，所以 os 或编译器会对程序施加限制，让程序员在申请大量内存时应该慎重，不要随意地在栈中开辟超大数组，尽量在堆中动态分配，不需要后及时释放。

栈溢出攻击

函数内定义的变量位于栈。如果输入的变量长度大于定义的局部变量长度（常见于字符串），输入的值就会覆盖栈内的某些变量，比如返回地址、参数。
如果返回地址被覆盖，程序就会跳转到输入指定的位置上，从而完成缓冲区溢出攻击。输入还可以包含某些指令，再通过指定返回地址跳到这些指令的位置，程序就会执行指定的指令。
为了防止攻击，程序通常要求：栈随机化（每次运行时变化栈的位置，使得不能确定插入代码的位置）、将栈内存段设为不可执行（不能执行插入的代码，只能执行代码段）。
但仍有攻击方法，见 CSAPP Lab3。

计组

RAM (Random Access Memory)

SRAM使用6个晶体管组成的反相器存储每一位数据。
SRAM快，贵，存储密度低。易失性。一般用于高速缓存。

高速缓存很难做的特别大，有成本、面积、功耗等问题，也会影响效率。
缓存通常分为指令缓存和数据缓存，因为两者的策略/访问情况可能不太一样，分开能进行优化。

DRAM使用1个晶体管、1个存储电容存储每一位数据。
DRAM需频繁刷新，较慢，较便宜，存储密度低。易失性。一般用于主存。

DRAM(内存)的构成

DRAM 中的存储结构，由上到下可分为：channel，rank，DRAM chip，bank，memory array，memory cell。
memory cell 的存储对象为1或0，是最基础的存储单元；bank为最小可控制单元；rank基本相当于一个“内存条”(一个内存条内也可以存在多个rank)；channel则大致对应内存条的数量。
Memory Controller 是直接对 Bank 下达读写指令的，所以每次读写都是以 8b 为单位，所以内存的基本单元是1字节。

memory array 一般为8*8的结构，包含64个 memory cell，故可存储64位。
bank 一般包含8个 memory array，每次可并行读取 8 个 array，构成 1 字节。这8位在物理空间上不是连续的。
chip 一般包含8个 bank，每次只能读 1 个 bank，即读 1 字节。
rank 一般包含8个 chip，构成 8*8 字节，可以是一个比较大的单位？

如果地址总线为64位，一次内存访问为：通过访问 8 个 chip 里地址相同的 8 个 bank，获得 64 位，即 8 字节。
所以一次内存访问只能获取 8k, 8k+1, 8k+2, ..., 8k+7 这样的 8 个字节（给它们分配连续的内存地址，但它们在物理上是不连续的）。
这就要求对于 4/8 字节的指令操作（如lw），地址参数必须是 4/8 的倍数。

chip 同时只能访问一个数据，但多个 chip 可以并行访问。所以 chip 0 包含的数据，实际上是 地址0, 8, 16... 上的数据。
注意，存储数据量和一次读取量是不相同的！array 间、chip 间 读取可并行，但 chip 内、bank 间不行。

内存对齐

https://zhuanlan.zhihu.com/p/539717599
https://www.bilibili.com/video/BV1hv411x7we?p=3

原因：
由于一次内存访问只能获取 8k, 8k+1, 8k+2, ..., 8k+7 这样的 8 个字节，这就要求：数据必须存储在 8k, 8k+1, ..., 8k+7 这8个字节内部，否则需拆成多次读取。
多次读取影响效率，所以编译器将不同类型的数据安排到合适位置、占用合适长度，尽量减少多次读取，也允许一次读取尽量多个数据。即内存对齐。

内存对齐要求：数据存储的起始地址和占用的字节数，是其对齐边界的倍数。

go中的寄存器宽度，为机器字长（4B或8B，是内存地址的最长长度，所以就是内存总线的位数），是机器平台对应的最大对齐边界。
数据的对齐边界：数据大小和平台最大对齐边界中的较小值。（所以与平台有关）
结构体对齐边界：各成员中最大的对齐边界。

一些编译器 现在能调整结构体中数据的分布，使得我们不需要注意声明顺序。

总线

总线是计算机各部件之间传输信息的公共通信导线。
根据功能分为三条：数据总线、地址总线和控制总线，分别传输数据、数据地址和控制信号。
数据总线、地址总线一般是32位或64位宽。

浮点数的原理

一个浮点数由三部分组成：符号位 S、指数部分 E（阶码）以及尾数(小数)部分 M，值为$(-1)^S\times M\times 2^E$。
实际的位表示为：1位符号位s，k位的阶码字段exp，n位小数字段frac。

当阶码字段既不全为0、也不全为1时（对 float，是不等于0和255），则数是规格化的：
阶码的值为$E=exp-Bias$。$Bias=2^{k-1}-1$，对 float 是127，对 double 是1023，使得指数的范围在-126~127 或 -1022~1023。
尾数的值为$M=1+frac$。因为$frac$的值为$\frac{frac2进制下的值}{2^n}$，即一个0开头的小数，所以M是隐含的以1开头的。

当阶码字段全为0时，为非规格化数，则阶码值为$E=1-Bias$，尾数的值为$M=frac$。
用于表示 0.0 和非常接近 0 的数字（并使它们尽量分布均匀）。

当阶码字段全为1时，为特殊值。
若尾数域全为0，则为无穷大（符号由 s 决定）；尾数域不全0时，表示 NaN。

有效位数

浮点数能准确表示的值为$x * 2^k$，$x$由尾数部分决定，所以精度有限。
单精度浮点数 float 总共 32 位，其中尾数有 23 位，此外小数点前有一位隐含的1，故表示范围为$2^{23+1} = 16,777,216$。因为$10^7 < 16,777,216 < 10^8$，所以单精度浮点数的有效位数是 7 位。由于第 8 位可能四舍五入，所以能保证的精度/有效数字为 6 位。
同理，双精度浮点数 double 总共 64 位，其中尾数有 52 位，故表示范围为$2^{52+1} = 9,007,199,254,740,992$，在$10^{16}$和$10^{17}$之间，所以双精度浮点数的有效位数是 16 位，四舍五入时 15 位。

多处理器编程

一个并发程序的示例：https://www.bilibili.com/video/BV13u411X72Q?t=5892.4

多处理器编程的难点：

1. 线程的执行顺序不同，会产生不同的结果。可以用状态机表示，每次随机选择一个线程执行一条指令，得到新的状态。
2. 编译器会假设程序是单线程执行的，并在此基础上做优化。
   对单线程的程序，只需要满足最终一致性，所以 CPU 可以延后一个寄存器到内存的写入；各变量值不会受其它线程影响，可以在编译期做很多优化（比如while(!flag);可能直接优化为if(!flag) while(1);）。
   但在多线程中，这样是不满足顺序一致性的。
3. 同一线程内，对于编译好的指令，处理器还可能同时执行多条指令（多发射），也就是指令的执行可能是乱序的。
   这与上一条类似，CPU 也会认为程序是单线程的，然后对指令的执行进行优化。但最终的提交是顺序的（乱序执行，按序提交）。

上面的描述就是宽松内存模型 (relaxed/weak memory model)？数据到内存的写入很可能不是实时的，不会对其它处理器立即课件。
x86 使用的就是宽松内存模型，每个线程有一个 write buffer，会在不确定多长时间后才会将数据写入内存。
而 ARM 是每个线程有一个自己的内存？不同内存间会进行读写，类似分布式系统，与内存模型完全不同？

现代处理器中，为了提高效率，引入了多发射 (multiple issue)：同时使用多条流水线并行执行多条指令。
多发射有两种：

• 静态多发射 (超长指令字，VLIW)：编译器在编译阶段识别哪些指令可以安全地并行执行，将它们封装为一个 VLIW 数据包，允许多条流水线一起取这些指令。
• 动态多发射 (超标量处理器，superscalar)：处理器在执行时动态识别可并行执行的指令。能提高并行度，但成本和能耗高。

内嵌汇编 asm

https://blog.csdn.net/yt_42370304/article/details/84982864

volatile

TODO
http://lxr.linux.no/linux+v4.5/Documentation/volatile-considered-harmful.txt
https://www.zhihu.com/question/31459750
https://zhuanlan.zhihu.com/p/33074506

volatile 告诉编译器，它修饰的变量是不安全的，可能会在线程外部被修改，不能像其他变量一样随意优化。
这与 barrier asm volatile("" ::: "memory")类似，它会告诉编译器，执行到这里时可能会有其它线程来访问，所以要？保证前后两部分的指令不被交换顺序执行？或保证去读写内存？

该关键字指示编译器优化忽略该变量缓存值，而是无论着么情况都是将数据立刻写入内存或者直接从内存读取数据。该变量并不必然代表是硬件IO口，也可能是程序进程可访问任何内存地址。告诉编译器不要把volatile修饰的数据优化到寄存器里，每次读取和写入都操作原始的数据地址。

volatile 并不是用来解决多线程的数据竞争问题的，应直接使用锁或原子操作等保证。

内存序

https://zh.cppreference.com/w/cpp/atomic/memory_order

在多处理器系统上，多个线程读写同样的变量时，一个线程能观测到变量值更改的顺序可能不同于另一个线程写它们的顺序。换句话说，多个线程看到的变量更改的顺序可能不一样，即不满足顺序一致性。一些类似的效果还能在单处理器系统上出现，因为内存模型允许编译器变换。

释放获得 load acquire

TODO
https://zh.cppreference.com/w/cpp/atomic/memory_order#.E5.AE.BD.E6.9D.BE.E9.A1.BA.E5.BA.8F

缓存一致性 MESI

TODO
https://mp.weixin.qq.com/s?__biz=MzUxODAzNDg4NQ==&mid=2247486479&idx=1&sn=433a551c37a445d068ffbf8ac85f0346&scene=21#wechat_redirect

错误共享/伪共享 (false sharing)

现在的 CPU 一般包含 3 级缓存，其中 L3 cache 是共享的，L1, L2 cache 是每个核独有的（L1 可分为 iCache, dCache）。

在多核多线程中，假设两个线程同时读写一个变量 a。首先线程1 写 a，会将 a 读入自己的 L1 缓存进行写；然后线程2 写 a，由于两个核共享该数据，线程1 需要先将 a 写回 L3（不确定，看具体实现），然后线程2 将最新的 a 从 L3 读入自己的 L1 缓存完成写；然后线程1 写 a，需要线程2 将 a 写回 L3，线程1 从 L3 读最新的 a 到 L1。
可见，在两个线程交替读写同一变量时，想要保持一致性，L1, L2 每次都会发生缓存不命中，导致程序效率很差。

缓存与内存之间交换的单位是 cache line (缓存行)。从内存读取变量时，会将与它相邻的一整个 cache line 大小的数据都放入缓存。
假设缓存行的大小为 64B，有两个在内存中相邻的 int 变量 a,b，那么 a,b 很可能在同一个缓存行里。
当线程1 读写 a 时，会将 a,b 同时读入 L1 缓存；如果线程2 需要读写 b， 也要求线程1 将 a,b 写回，然后从 L3 中读取。
可以发现，由于 a,b 相邻，错误地被共享到了同一缓存行中，即使两个线程交替使用不同的变量，也会导致连续的缓存不命中，影响效率。

解决错误共享很简单，保证 a,b 不在一个缓存行即可。下面的方法都是填充。
假设 a,b 是 long 占 8B，可以在 a,b 之间添加 7个 long。
在 C++ 中可以使用宏定义__cacheline_aligned_in_smp，在多核系统中该宏定义就是缓存行的大小。例子见这里或这里。
在 java 可以使用@jdk.internal.vm.annotation.Contended注解。

缓存为什么要分级

1. 假设只有 L1 缓存。在 L1 比较小时，缓存的命中率会随 L1 的大小提高；但当 L1 达到 64KB 或更小时，增大 L1 对命中率的影响就微乎其微了。这样的成本不如用在其它缓存或 CPU 上。
   缓存的命中率与程序的局部性有关，程序的常用数据可能就那么多，一定量的缓存就足够保存；而不常用的数据，再增大缓存也没用。
2. 假设 L1 缓存大小固定，考虑 L2 缓存。同上，L2 较小时，增大 L2 能提高整体的命中率；但达到一定值时，增大 L2 的收益也很小了。
3. 缓存越大，寻址和定位更慢，延迟更多。只要命中率足够高，小的缓存也未必比大缓存差（但好像现在也到不了这种程度？）。

最后一级缓存叫 LLC (Last Level Cache)。如果 LLC 的命中率不高，将对程序有很大影响。

缓存的 inclusive 与 exclusive

以三层缓存为例。
inclusive：缓存间为包含关系，L1 是 L2 的子集，L2 是 L3 的子集。
exclusive：缓存间为互斥关系，L1, L2, L3 中的数据没有交集。
non-inclusive：缓存间不强制为包含关系，具体内容任意。

区别：

• inclusive 下，当处理器未命中缓存时，不需要检查其它处理器的私有 cache，只需要去大的共享 cache 中检查，便于实现 cache 的一致性（大的 cache 是共享的）。只需要内层的小 cache 直写到外层 cache 即可（反正效率很高）。
  但缓存能存放的数据更少。
• exclusive 能增大缓存的有效容量，提高命中率；还可以用大 cache 作为内层缓存，进一步提高效率。
  但很难处理多核间的数据共享，比如可能需要访问其它处理器的 cache，或内层 cache 直写到内存。

Linux

常用命令

• less：分页显示文件，通过方向键和空格控制，Q 退出。不需要加载整个文件，响应速度快。
• more：分页显示文件，通过空格和 b 控制上下页。会加载整个文件到内存。
• cat：显示整个文件。没有翻页功能，会加载整个文件。

kill

kill 后可以加一个数字，表示使用的信号。通过kill -l查看所有的信号。

• kill -1：发送 SIGHUP 挂起信号，进程会尝试重新加载配置文件或重启服务，目的是更新环境，或启用新的配置文件。
• kill -2：INT 信号，（同 Ctrl C）。
• kill -3：QUIT 信号，类似 2？但会打印退出信息（同 Ctrl Z？）。
• kill -9：KILL 信号，强制进程立刻调用exit()结束，进程无法释放或保存资源。
  不建立使用。
• kill -15：TERM 信号，类似2，通知进程终止，进程会先释放资源，然后安全地结束。
  进程会：关闭打开的文件、通知其它进程自己的结束等。如果进程阻塞（如等待IO）不能立即处理，则该命令也会被阻塞。

在指定的路径里找所有文本文件中带有“abc”的内容

grep abc *.txt

CPU 100% 如何排查

1. 通过top查看所有进程占用的系统CPU（排序后的结果）。
2. 通过top -Hp 16进制进程号查看某个进程的所有线程的CPU占用情况。
3. 通过jstack查看线程的堆栈信息。见 http://www.taodudu.cc/news/show-3375798.html。

可能的几种原因：死锁；死循环；频繁的GC；大量线程访问同一接口。

安全与加密

对称加密（Symmetric Encryption）
指加密、解密使用一个相同的密钥的加密算法。在通信时，信源将原始数据（明文）经过加密处理（密文）后发送。接收方收到密文后，使用同样的密钥和加密算法的逆算法对密文进行解密，才能获得明文。密钥不能对外公开。
优点：算法公开，计算量小，加密、解密速度快，效率高。
缺点：双方需先同步密钥，且任意一方的密钥都不能泄露。使用对称加密时，要确保该密钥唯一、不被他人知道，会使得收、发双方所拥有的钥匙数量巨大、密钥管理成为双方的负担。

非对称加密/公钥加密（Public Key Encryption）
指由一对唯一性密钥（公开密钥和私有密钥）组成的加密方法。公开公钥不会对私钥安全性产生影响，且可用于发送方进行加密，只有接收方自己拥有私钥能够解密。
要求：利用公钥破解私钥在"计算上"是不可行的。
优点：安全，通信前不需先同步密钥，只需保证私钥不被泄露。便于管理密钥。
缺点：速度较慢，效率较低。

Hash
单向算法，为目标信息生成一段特定长度的唯一hash值，但不能通过这个hash值重新获得目标信息。常用在不可还原的密码存储、信息完整性校验等。

非对称加密慢怎么解决
非对称传递对称加密密钥，然后再用对称加密传输。然后对称加密通信的过程中顺便更换一下密钥，保证前向安全性？

CSRF攻击

输入过滤

XSS攻击

SQL注入

密码存储

编码 哈希 加密
编码任何人都可以 decode，hash 是单向函数，加密是拥有 key 的人才可以 decrypt。