数据结构

并查集的union和find

优化的Union：节点数少的并到节点数大的，成为子树 Find，压缩路径

红黑树

左根右（二叉排序树），根叶黑（叶是指失败节点）  
不红红，黑路同

算一个节点黑高不会把该节点算进去，但会把失败节点算进去。  
如下图选项D节点“1”的黑高=1；节点“8”的黑高=2

B树和B+树

排序

计组

定点数表示与运算

边界对齐

磁盘阵列RAID

运算器和控制器

单重中断/多重中断

机器字长、指令字长、存储字长的区别与联系

区别：

1. 机器字长：
2. 定义：机器字长是指计算机能直接处理的二进制数据的位数，它决定了计算机的运算精度。
3. 特点：通常等于CPU内部寄存器（如通用寄存器，累加器、ALU等）的位数。例如，我们常说的64位机中的“64”即为机器字长。
4. 指令字长：
5. 定义：指令字长是指一个指令字中包含的二进制代码的位数。
6. 特点：指令字长取决于操作码和地址码的长度。它可以等于、大于或小于机器字长。常见的指令字长有半字长(机器字长/2)、单字长(机器字长)和双字长指令(2机器字长)。指令字长和机器字长没有任何关系。(双字长指令存放在两个内存单元，取指令需访存两次)*
7. 指令寄存器IR的位数等于指令字长
8. 存储字长：
9. 定义：存储字长是指一个存储单元存储的二进制代码的长度。具体看编址方式比如按字节编址（8位），按字编址（32位），按半字编址（16位）
10. 特点：通常与MDR（存储器数据寄存器）的位数相等。存储字长决定了存储单元能够存储的数据量。

MDR和MAR的位数

MDR（存储器数据寄存器）的位数：

• MDR用于暂存从存储器读写的信息，其位数通常=存储字长=数据线宽度。如果数据线位数不等于存储字长，则MDR位数由数据线位数决定。这意味着MDR能够一次性地存储或传输一个或多个存储单元的全部数据。取决于数据线宽度也就是MDR位数。
• 例如，如果MDR的位数为16位，那么每个存储单元可以存放16/8bit的数据，即存储字长等于16/8bit。

MAR（存储器地址寄存器）的位数： MAR存的是物理地址，不是虚拟地址 - MAR用于存储数据对应的地址信息，可以比作大楼的门牌号。MAR的位数等于存储器地址线数，决定了存储器的寻址范围。 - MAR的位数越多，能够表示的存储单元地址就越多，存储器的容量也就越大。例如，如果MAR有10位，那么理论上可以存储2^10=1024个地址信息，对应1024个存储单元。

寄存器既不属于RAM也不属于ROM。它是CPU内部的一个高速、小容量的快速存储器，用于暂存指令、数据和地址等信息，以支持CPU的高效执行。

中断响应和处理： 函数调用：

push xx   //1.esp-4；2.xx入栈
pop xx    //1.esp+4；2.esp出栈至xx

调用者保存寄存器: EAX,EDX,ECX

指令周期，机器周期，CPU周期，时钟周期

指令周期：CPU每取出并执行一条指令所需要的全部时间。一个指令周期由多个机器周期组成：取指周期--间址周期--执行周期--中断周期 指令字长等于存储字长的前提下取指周期等于机器周期。。 机器周期也叫CPU周期：指令执行中每部操作所需时间。机器周期由存取周期决定。 时钟周期:计算机操作的最小时间单位，是主频的倒数T=1/f 存取周期：存储器进行两次独立的存储操作所需要的最小时间。 读/写时间：存储器进行一次读或写操作所需时间。

操作系统

用户态与核心态 文件分配：索引分配和非索引分配时的FCB

 * 非索引分配时一个目录文件里的每一个目录项就是一个完整的FCB （一般64B）
 * 索引分配时一个目录文件里的每一个目录项只包含文件名和inode节点的序号/指针，咱就把一个inode节点看作一个FCB

open（）系统调用

三种文件分配

1. 连续分配：每个文件占用一个连续的存储
2. 隐式链接分配：每个文件占用一系列非连续磁盘块，每个磁盘块最后有指向下一个磁盘块的指针
3. 显式链接分配：每个文件占用一系列非连续磁盘块，用FAT（文件分配表）记录整个磁盘的分配情况
4. 索引分配：每个文件占用一个索引块inode，目录项和硬链接都指向索引块

磁盘格式化

计网

MAC：介质访问控制

评价MAC协议指标：高负载看吞吐量，低负载看时延

其中只有随机访问协议有冲突，需要检测/避免；
静态划分信道和轮询访问没有冲突

FDM、WDM--并行--共享时间，不共享空间
TDM--并发--共享空间，不共享时间
CDM--即共享时间，又共享空间
令牌传递协议--即不共享时间，也不共享空间

TDM：固定时隙分配
STDM：按需分配时隙

ALOHA

Pure ALOHA： vulnerable period=2t
Slotted ALOHA： vulnerable period=t

1.纯ALOHA比时隙ALOHA吞吐量更低，效率更低，
2.纯ALOHA想发就发，时隙ALOHA只有在时间片段开始时才能发

CSMA 载波侦听

vulnerable period=propagation delay

CSMA/CD ：载波侦听 with Collision Detection

无确认，无连接--用于总线型以太网（802.3）
CSMA/CD用于半双工，全双工不用CSMA/CD

• propagation delay= t

• vulnerable period=length of contention slot = detection time =2t （争用期，冲突窗口）

• 发送帧时间Ttr ≥争用期时间2t （对最短帧长64B也是）

• 最短帧长：争用期内因检测到冲突而中止发送的无效帧，凡是小于最小帧长的帧都是无效帧，应当丢弃。最小帧长计算公式：

• 最小帧长=2·传播时延t·数据传输速率=争用期时间·传输速率
• 以太网最小帧长64B
• 10Mb/s以太网争用期2t=64B的发送时间=64B/10Mb/s=51.2μs
• 100Mb/s以太网争用期2t=64B的发送时间=64B/100Mb/s=5.12μs

以下是CSMA/CD算法的详细工作流程：

一、载波监听

1. 监听信道：在发送数据之前，每个节点都会先监听（检测）网络线路，确认是否有其他节点正在传输数据。这是通过检测信道上的信号来实现的。
2. 判断信道状态：
3. 如果检测到信道忙（即有其他节点正在发送数据），则节点会进入等待状态，继续监听信道直到它变为空闲。
4. 如果信道空闲（即在一定时间内没有检测到其他节点的信号），则节点认为可以开始发送数据。

二、发送数据

1. 开始发送：当信道被判断为空闲时，节点会立即开始发送其数据帧。
2. 边发边听：在发送数据的同时，节点也会继续监听信道，以检测是否发生了冲突。

三、冲突检测

1. 检测冲突：节点通过检测信号波形的变化来判断是否发生了冲突。如果在同一信道上同时有两个或更多节点发送数据，它们的信号会相互干扰，导致信号波形失真，从而被检测到冲突。
2. 停止发送：一旦检测到冲突，所有参与冲突的节点会立即停止发送剩余的数据帧。

四、冲突解决

1. 发出阻塞信号（可选）：有些实现中，检测到冲突的节点会向信道上发出一个阻塞信号（jam signal），以通知其他节点冲突已经发生。
2. 执行退避算法：每个节点都会执行一个退避算法，通常是二进制指数退避算法，来确定在重新尝试发送数据之前需要等待的时间。这个时间间隔是随机的，以减少再次发生冲突的概率。
   • 注：公式中的重传次数==发生了几次冲突。比如第一次检测信道发现冲突就没传冲突计一，再次检测需要经过0t或1t，假设第二次检测也发现冲突冲突计二，第三次检测需经过【0，3】t，...

五、重发数据

1. 等待随机时间：节点在执行完退避算法后，会等待一个随机的时间间隔。
2. 再次监听信道：等待时间结束后，节点会再次监听信道，以确保信道空闲。
3. 重新发送数据：如果信道空闲，节点会重新发送其数据帧。如果再次发生冲突，则重复上述冲突解决和重发数据的步骤，直到数据成功发送或达到最大重试次数限制。

CSMA/CD算法的工作流程可以概括为：先听后发、边听边发、冲突停发、随机延迟后重发

CSMA/CA：载波侦听 with Collision Avoidance

有确认，无连接--WIFI（802.11） RTS--CTS--DATA--ACK

• CSMA/CA也有退避算法，但跟CSMA/CD不一样。
• 预约信道不是CSMA/CA必须实现的，是可选的。为了解决隐蔽站问题而设计的。
• 检测到信道空闲不会立即发送RTS/数据，有一个DIFS

RTS-CTS解决隐蔽站，暴露站问题？

令牌传递协议

无冲突，用主机组成令牌环网，得到令牌才能独自占领信道传数据

PPP数据链路层协议：

• PPP（Point-to-Point Protocol）是一种用于点对点连接的数据链路层协议
• 用软件实现，CRC检错
• 有连接，无确认
• 异步传输用字节填充，同步传输用零比特填充（一般PPP默认为异步传输）
• 面向字节，帧长度是整数倍字节 TCP/IP协议族：TCP，IP, ICMP,IGMP, ARP, RARP, UDP, DNS, FTP,HTTP, HTTPS

集线器

集线器是物理层设备，连接在同一个集线器的所有设备都处于同一个冲突域，广播域，使用集线器既不隔离广播域，又不隔离冲突域。半双工通信。以太网使用集线器时就需要用CSMA/CD协议检测冲突。集线器为每个用户平分线路带宽。 使用集线器建立的以太网称共享式以太网。

交换机

交换机是数据链路层设备，实际上是一个多接口的网桥。每个接口属于一个冲突域，所以交换机隔离了冲突域（但不隔离广播域），以太网使用了交换机就不必使用CSMA/CD协议了。一段时间内多个端口并行通信。默认全双工通信，交换机共享线路带宽（用户独占带宽），因此交换机总容量：N*10Mb/s。若特别强调半双工通信，则交换机总容量：（N*10Mb/s）/2交换机是自学习设备，即插即用，不必配置。 使用交换机建立的以太网称交换式以太网

网络层

分组交换分虚电路和数据报。虚电路提供面向连接服务，数据报提供无连接服务，如IP协议。 虚电路： 数据报：

IP数据报分片和重组

最大传送单元 MTU: MTU 是 链路层可封装数据 的上限 MTU 值 : 以太网的 最大传送单元 MTU 是 1500 字节

分片 : 链路层的数据部分 , 就是 IP 分组 , 该分组的 MTU 是 1500 字节 , 当以太网网络层的 IP 分组超过 1500 字节 , 此时就要进行分片

IP 数据报首部中的相关数据长度单位 : 速记 : 一种 ( 总长度 ) 八片 ( 片偏移 ) 的 首 ( 首部长度 ) 饰 ( 四 )

总长度单位 : 1 字节 （IP首部+数据部分） 片偏移单位 : 8 字节 (数据部分) 首部长度单位 : 4 字节 （IP首部）

IP地址 网段==子网 若一台主机有多个IP地址那么该主机属于多个网络，每个IP地址属于一个不同的网络 私有IP地址用于LAN内部，不用于WAN连接，需通过网关NAT把私有IP转换成公用合法全球IP后通信。 NAT-网络地址转换

子网划分 子网内的主机号全0，全1都不能被指派 子网掩码：IP地址对应网络号，子网号填1，主机号填0。如255.255.255.0 网络地址=IP地址 and 子网掩码 141.14.72.24 and 255.255.192.0 = 141.14.64.0（子网掩码）

CIDR无分类编址 用网络前缀代替网络号，而且网络前缀可变长的，这样可以灵活的分配ip地址 IP地址=网络前缀+主机号 CIDR记法/斜线记法: IP地址/网络前缀所占位数

128.14.32.5/20 所在CIDR地址块中最小，最大地址： 最小：128.14.32.0 最大地址：128.14.47.255 所以：总地址数：2^12=4096 ,可指派地址数：2^12-2=4094 (去掉全0，全1)

路由聚合/构成超网：路由器中连接统一端口的多个网段网络地址合并为一个共同网络地址，减少路由表项

ARP协议

• ARP协议通过广播把IP地址映射到MAC地址（找到下一跳MAC地址）
• ARP请求是广播，ARP响应是单播
• ARP看到了IP地址，因此工作在网络层，NAT路由器看到了端口，因此工作在应用层

ARP作用范围和工作流程

1. 局域网内

在同一个局域网（LAN）内，设备之间通过以太网通信，数据包需要使用目标设备的MAC地址来完成传输。

• ARP的作用：
• 当一台设备（如主机A）需要向同一局域网内的另一台设备（如主机B）发送数据时，如果它只有目标设备的IP地址，不知道MAC地址，则需要使用ARP协议。
• 主机A会发出一个ARP请求广播包(目的MAC：FF-FF-FF-FF-FF-FF)，询问"谁拥有这个IP地址？"。
• 局域网内所有设备都会收到这个广播包，只有IP地址匹配的设备（同一局域网：主机B；跨局域网：默认网关路由器）会响应，并返回其MAC地址。
• 主机A收到响应后，会将IP地址与MAC地址的对应关系存入ARP缓存中，并使用该MAC地址进行数据传输。

• ARP请求是通过广播发送的，广播会被局域网内的所有设备接收。但不会跨越路由器，因为路由器隔离广播。

• 此时主机A发送的数据包：

• 源IP地址：主机A的IP地址（假设为IP_A）。
• 目的IP地址：目标主机B的IP地址（假设为IP_B）。
• 源MAC地址：主机A的MAC地址（假设为MAC_A）。

• 目的MAC地址：将由主机A通过ARP（地址解析协议）获取。假设主机A和目标主机B在同一局域网内，主机A将通过ARP获取主机B的MAC地址MAC_B，然后将其作为目的MAC地址。如果不在同一局域网内，则目的MAC地址为默认网关（如路由器）的MAC地址（假设为MAC_R1）。

• 数据包到达交换机：交换机是工作在数据链路层的设备，它通过MAC地址表来转发数据包。

• 源IP地址：保持不变，仍为IP_A。

• 目的IP地址：保持不变，仍为IP_B。
• 源MAC地址：保持不变，仍为MAC_A。
• 目的MAC地址：保持不变，交换机根据目的MAC地址MAC_B或MAC_R1来决定将数据包转发到哪个端口。

2. 路由器间

如果主机A和目标主机B不在同一个局域网内，数据包将会经过一个或多个路由器。当数据包在路由器间传输时，路由器通过路由表获得下一跳IP地址和出端口号，后使用ARP在该端口广播获得下一跳IP对应的MAC地址，再替换数据报中源，目的MAC地址从该端口送出。

• 数据包到达路由器：
• 源IP地址：保持不变，仍为IP_A。
• 目的IP地址：保持不变，仍为IP_B。
• 源MAC地址：路由器会将源MAC地址更改为路由器接口的MAC地址（假设为MAC_R2）。
• 目的MAC地址：路由器会将目的MAC地址更改为下一个跳跃设备的MAC地址。如果数据包将被路由到下一个路由器，则目的MAC地址将是下一个路由器的接口MAC地址（假设为MAC_R3）。如果目的地是最终的主机B，则目的MAC地址为主机B的MAC地址MAC_B。

总结

• IP地址：在整个传输过程中，源IP和目的IP地址保持不变。
• MAC地址：在每一跳时，源MAC地址和目的MAC地址会发生变化，源MAC地址为当前设备的MAC地址，目的MAC地址为下一跳设备的MAC地址，直到最终到达目的主机。

DHCP动态主机配置

• 为客户主机动态配置IP地址
• 基于UDP的应用层协议,客户/服务器工作模型，四种“消息”都是广播
• 源IP：0.0.0.0 ，目的IP： 255.255.255.255

ICMP

ICMP（Internet Control Message Protocol，互联网控制消息协议）是TCP/IP协议族中的一个核心网络层协议，主要用于在IP网络中传递控制信息和错误消息。ICMP协议不直接传输用户数据，而是为其他协议（如IP）提供必要的控制和管理功能，所以ICMP报文被封装在IP数据报中发送。

ICMP协议的主要特点

• 无连接协议：ICMP不需要建立连接，也不需要维护状态，只需要发送报文和接收报文。
• 错误报告：当IP数据包无法送达目的地时，ICMP会发送错误消息给发送端，告知错误原因。
• 网络诊断：ICMP支持网络诊断工具，如Ping和Traceroute，用于测试网络连通性和追踪路由。

ICMP报文类型

ICMP报文主要分为两大类：差错报文和询问报文。

• 差错报文：用于通知发送端有错误发生，包括目的不可达、源站抑制、时间超过（Time Exceeded）、参数问题等。
• 询问报文：用于向目的主机发出请求，获取网络状态和信息，包括回显请求（Echo Request）和回显应答（Echo Reply）、时间戳请求和时间戳应答等。

ICMP使用例子

1. Ping命令
2. 功能：检测网络连通性。
3. 原理：发送ICMP回显请求（Echo Request）报文到目标主机，目标主机收到后返回ICMP回显应答（Echo Reply）报文。询问报文

4. 应用：通过Ping命令的响应时间和成功率，可以判断网络是否通畅以及大致的延迟情况。

5. Traceroute/Tracert命令

6. 功能：追踪数据包从源主机到目的主机的路由路径。
7. 原理：发送一系列具有递增TTL（Time To Live）值的ICMP回显请求报文，每经过一个路由器，TTL值减1，当TTL减为0时，路由器会返回ICMP时间超过（Time Exceeded）报文，从而追踪出整个路由路径。差错报文
8. 应用：用于诊断网络中的路由问题、延迟瓶颈等。

路由算法

• 距离向量[Distance Vector]协议只与直接邻居交谈，发送自己完整的路由表，路由表大小取决于网络中节点数目，代价较大
• 链路状态协议广播交谈全网节点，只发送与自己直接相连的链路费用，之后每个节点自己计算出完整的路由表（Dijkstra）

RIP 路由信息协议——Routing Information Protocol

• 属于距离向量，每个路由器维护一个距离向量，记录自己到其他所有节点的距离，一般用跳数当作距离，范围1-15，距离为16表示网络不可达。当然也可以拿延迟等参数当距离，此时没这个范围要求了。
• 好消息传得快，坏消息传得慢
• 应用层协议，用UDP通信，默认端口为520
  

OSPF 开放最短路径优先协议

• 属于链路状态协议，广播与本路由器相邻路由器链路状态，每隔路由器独自算出到个节点的最短路径，但不会存储完整路径，只存储吓一跳
• 网络层协议，直接用IP数据包传送而不依赖UDP，TCP等传输层协议

802.11地址1，地址2，地址3

当带权连通图的任意一个环中所包含的边的权值均不相同时，其 MST 是唯一的