计算机综合基础知识记录（408、面试）

计算机综合基础知识记录（408、面试）

基础-计算机综合

一、数据结构

1.1 排序算法

1.1.1 八大排序

算法	最好	平均	最坏	空间	稳定
直接插入	O ( n ) O(n) O(n)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	是
冒泡	O ( n ) O(n) O(n)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	是
简单选择	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	否
希尔	O ( n ) O(n) O(n)	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	否
快排	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n 2 ) O(n^2) O(n2)	O ( l o g 2 n ) O(log_2n) O(log2​n)	否
堆排	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( 1 ) O(1) O(1)	否
2路归并	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)	O ( n ) O(n) O(n)	是
基数排序	O ( d ( n + r ) ) O(d(n + r)) O(d(n+r))	O ( d ( n + r ) ) O(d(n + r)) O(d(n+r))	O ( d ( n + r ) ) O(d(n + r)) O(d(n+r))	O ( r ) O(r) O(r)	是

1.1.2 如何选择

• n较小： 直插，简选

• n较大： 快排，堆排，归并

• n超大： 外部归并

• 基本有序： 直插，冒泡

• 稳定： 基，归，插，冒

• 关键字可分解： 基排

• 比较次数与初态无关： 归，选，基

• 排序趟数与初态无关： 插，归，选，基

• 时间复杂度与初态无关： 堆，归，选，基

• 每一趟能确定一个最终位置： 泡，快，选，堆

1.2 最小生成树 MST

Prim	Kruskal
O ( V 2 ) O(V^2) O(V2)	O ( l o g E ) O(logE) O(logE)
边稠密	边稀疏，顶点多

1.3 最短路径

BFS	Dijkstra	Floyd
O ( V 2 ) / O ( V + E ) O(V^2) / O(V + E) O(V2)/O(V+E)	O ( V 2 ) O(V^2) O(V2)	O ( V 3 ) O(V^3) O(V3)
单源 + 无权	单源 + 有权 +无权	多源 + 有权 + 无权
/	不适用负权	适用负权，不适用负回路

1.4 图的存储方式

	邻接矩阵	邻接表	十字链表	邻接多重表
适合	稠密图	稀疏图	有向图	无向图
空间	O ( V 2 ) O(V^2) O(V2)	无向： O ( V + 2 E ) O(V + 2E) O(V+2E) 有向： O ( V + E ) O(V + E) O(V+E)	O ( V + E ) O(V + E) O(V+E)	O ( V + E ) O(V + E) O(V+E)
表达	唯一	不唯一	不唯一	不唯一

1.5 树的存储方式

双亲表示	孩子表示	孩子兄弟表示
顺序存储	顺序 + 链式	二叉链表（左孩，右兄）
找爸方便，找孩不便	找爸不便，找子方便	找爸不便，找子方便，方便转二叉树

1.6 哈希冲突解决

开放定址法

• 线性探测法
• 平方探测法
• 再散列法
• 伪随机序列法

拉链法

1.7 查找

（线性）

• 顺序查找
• 折半查找
• 分块查找

（树形）

• 二叉排序树
• 二叉平衡树
• 红黑树
• B 树
• B + 树

（散列）

• 哈希表

适合静态查找： 顺序，折半，哈希

适合动态： 二叉排序，哈希

1.8 杂问

1.8.1 度为2的树 VS 二叉树

度为2则树中度最大为2，二叉树可以为空树。

1.8. 2 栈和队列实现

• 栈： 递归，进制转换，迷宫求解，括号匹配，树的后序遍历，表达式求值，函数调用，DFS
• 队列： 缓冲区，页面替换，树的层序遍历，BFS

1.8.3 判断环

• 拓扑排序
• DFS
• 求关键路径（第一步是拓扑排序）

1.8.4 判断链表环

快慢双指针

1.8.5 头指针 VS 头节点

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

1.8.6 唯一确定一个二叉树

中序 + 先序 / 中序 / 层序

二、计算机组成

2.1 系统概述

2.1.1 冯诺依曼机组成

• 运算
• 存储
• 控制
• 输入
• 输出

2.1.2 冯诺依曼机特点

• 指令和数据以二进制表示
• 指令数据同等地位
• 指令由操作码和地址码组成
• 指令在存储器顺序存放
• 以运算器为中心

2.1.3 计算机的层次结构

高汇操传微

1. 高级语言机器：执行高级语言
2. 汇编语言机器：执行汇编语言
3. 操作系统机器：向上提供广义指令
4. 传统机器：执行机器语言指令
5. 微程序机器：执行微指令

2.1.4 字长辨析

• 机器字长：计算机一次处理二进制长度（64/32) ，cpu 内数据通路宽度，等于寄存器位数。
• 存储字长：MDR 位数
• 数据字长：数据总线一次能传输信息的位数
• 指令字长：指令含二进制位数

2.1.5 程序分类

• 汇编程序：汇编程序翻译成机器语言
• 编译程序：高级语言翻译成机器语言（一次性翻译，生成可执行代码）
• 解释程序：高级语言翻译成机器语言（一句一句翻译）

2.1.6 计算机性能指标

• 主频：1s内有多少个时钟周期
• IPS：1s内执行多少条指令
• CPI：1条指令消耗多少之中周期
• FLOPS：1s内执行多少次浮点运算（最能反映计算机的计算速度）

2.2 数据表示

2.2.1 检错和纠错编码

• 奇偶校验码：检测出奇数位错误，没有纠错能力
• 循环冗余校验码CRC：利用多项式生成校验码，
  检测出奇数位错误和双比特错误，选择合适的生成多项式才有纠错能力
• 海明校验码：海明码有1位纠错，2位检错能力

2.3 存储

2.3.0 存储简介

• 主存-缓存：用来缓解 速度 压力，完全由硬件实现，缓存是主存的副本

• 主存-辅存：用来缓解 容量 压力，有操作系统和硬件配合实现，主存是缓存的副本

• 主存：运行时数据

• 辅存：暂时不用，永久保存

• RAM（随机存储器）：随机存取，存取时间与物理位置无关

• ROM（只读存储器）：断电内容保存

2.3.1 衡量存储器的三个指标

• 单位价格
• 时间
• 速度

2.3.2 SRAM & DRAM

类型	SRAM（静态）	DRAM（动态）
存储（核心区别）	触发器	电容
破坏性读出	否	是
读出需重写	否	是
速度	快	慢
集成度	低	高
成本	高	低
断电后	丢失	丢失
需要刷新	否	是（分散，集中，异步）
送行列地址	同时送	分开送（地址复用）

2.3.3 Cache 的映射方式

方式	全相联映射	直接映射	组相联映射
原理	主存块可以在Cache的任意位置	每个主存块有一个特定位置	Cache块分为若干组，每个组成块分到特定组的任一位置
命中率	最高	最低	——
判断开销	最大	最小	——
空间开销	最大	最小	——

2.4 指令系统

2.4.1 CISC & RISC

类别	CISC	RISC
指令系统	复杂、庞大	简单、精简
指令数目	多	少
指令字长	不固定	固定
访存	无限制	仅限 Load / Store
指令时间	相差较大	类似
指令频率	相差较大	均常用
通用寄存器	少	多
控制方式	多数为微程序控制	多数为组合逻辑控制
流水线	可以实现	必须实现

2.4.2 寻址方式

寻址方式	特点	有效地址
隐含寻址	最短（简）	程序指定
立即寻址	最快	A
直接寻址	最长	EA = A
间接寻址	最慢	EA = （A）
寄存器寻址	最短	EA =（R）
相对寻址	转移指令	EA =（PC）+ A
基址寻址	多道程序 浮动程序	EA =（BR）+ A
变址寻址	循环程序 数组问题	EA =（IX）+ A

2.5 CPU

2.5.1 程序 VS 微程序

• 程序是指令的集合，对程序员不透明
• 微程序是微指令的集合，对程序员透明
• 一条指令对应一个微程序，一个微程序由多个微指令构成，一条微指令对应多个微命令

2.5.2 流水线冲突

• 资源冲突：争用同一资源造成 | 解决办法（下同）：暂停一时钟周期
• 数据冲突：下一指令要用到当前指令的结果造成 | 采用数据旁路技术，即把前一条指令的ALU计算结果直接输入到下一条指令
• 控制冲突：转移、调用断流造成 | 采用分支预测

2.5.3 流水线改进

• 超标量流水线：每个时钟周期并发多条独立的指令，配置多个功能部件
• 超流水线：一个时钟周期内在分段，允许一个部件在一个时钟周期内多次使用
• 超长指令字：多个操作码字段，多个部件并行执行

2.6 总线

2.6.1 总线结构

• 单总线：
  • cpu和外设直接进行信息交换，速度不匹配
• 双总线：
  • 主存总线 + io总线
  • 将低速设备从单总线上分离出来，增加通道等硬件设备
• 三总线：
  • 主存总线 + io总线 + DMA总线
  • DMA 总线在内存和高速外设之间传输数据，系统吞吐量提高，但是系统工作效率低

2.6.2 总线有几种，单向还是双向

3种，数据总线和控制总线是双向的，地址总线是单向是只能CPU到I/O口。

2.6.3 总线周期

• 取址周期
• 间指周期
• 执行周期
• 中断周期

2.6.4 总线通信

• 同步
• 异步
• 半同步
• 分离式

2.7 I/O

2.7.1 I/O 控制方式

• 程序查询方式：不断查询I/O设备是否准备好，浪费大量CPU时间。
• 程序中断方式：指令执行完成后检查是否有中断发生，若出现中断则处理，否则继续执行下一条指令。
• DMA方式：DMA方式是指外部设备不通过CPU而直接与主存进行数据交换的方式，
  DMA控制器发出请求，CPU让出系统总线由DMA接管，让外设可以直接访问内存，这样外设的读写就不需要CPU参与，降低了CPU的占用率。
• 通道方式：通道方式是构建一个通道，主存和I/O设备之间的数据交换通过通道来完成，通道方式是对DMA的发展，由一个数据块的读写发展成为一组数据块的处理。

2.8 杂问

2.8.1 重定位需要哪些硬件

重定位寄存器

2.8.2 指令数据存储在同一位置，计算机如何区分

根据不同指令阶段

2.8.3 MAR MDR 存储器容量

MAR：地址寄存器

MDR：指令寄存器

存储器容量 = 2 寄存器位数 ∗ 地址寄存器位数 存储器容量 = 2^{寄存器位数}*地址寄存器位数 存储器容量=2寄存器位数∗地址寄存器位数

2.8.4 DMA VS 中断

中断需要保护现场和恢复现场；DMA方式除了预处理和后处理，不使用cpu资源；

中断请求只能在执行周期后接收到；DMA可以是任何一个机器周期结束后。

中断过程需要cpu干预，DMA传送过程不需要cpu干预；

DMA 优先级更高，速度更快。

中断靠程序，DMA靠硬件。

三、操作系统

3.0 操作系统

3.0.1 OS 功能

• 进程管理

• 内存管理

• 文件管理

• 设备管理

3.0.2 OS 分类

• 批处理系统
• 分时操作系统（运行时间划分为时间片，具有 交互性）
• 实时操作系统 （规定时间内完成，及时可靠

3.0.3 OS 特点

• 共享
• 并发（宏观同时，微观交互）
• 虚拟
• 异步

3.0.4 用户态 & 内核态

内核程序 & 应用程序
特权指令 & 非特权指令

内核态（核心态，管态）：运行的是内核程序，可以执行特权指令，也可以执行非特权指令
用户态（目态）：运行的是应用程序，只能执行非特权指令

用户态 --》内核态：系统调用、中断、异常

内核态 --》用户态：修改程序状态字PSW

3.0.5 系统调用

OS 与应用程序（程序员）之间的接口，它是用户程序取得 OS 内核服务的唯一途径。

系统调用 VS 库函数：库函数是 编程语言提供 给程序员的接口，系统调用是 操作系统提供 的接口。

什么功能需要系统调用：凡是与共享资源或者影响其他进程的操作都需要操作系统介入，需要系统调用。

系统调用指令 = 广义指令：在用户态下调用，在核心态执行
陷入指令 = trap指令 = 访管指令：在用户态下执行

3.1 进程

3.1.0 进程

• 程序是静态的指令集和
• 进程是是动态的,是程序的一次执行过程
• 进程是系统分配和调度的基本单位

3.1.1 进程 VS 线程

进程 是资源分配的最小单位，线程 是 程序执行（处理机），调度分配的最小单位。

一个线程只能属于一个进程，而 一个进程可以有多个线程，但至少有一个线程。

3.1.2 进程实体组成

• PCB：面向 OS，进程的唯一标识，进程创建时创建，进程结束时结束，包含进程标识符，用户标识符，进程优先级等
• 程序段：面向进程自己
• 数据段：面向进程自己

3.1.3 进程状态

3.1.4 挂起 VS 阻塞

• 挂起是中级调度中的概念，是把暂时不运行的进程从内存调入外存，以降低内存负担。
• 阻塞是低级调度中的概念，是进程的申请某个资源而不得的主动行为

（算法）3.1.5 进程调度算法

• 先来先服务 （利于CPU繁忙型，不利于I/O繁忙。）

• 短作业优先 （最短平均周转时间，不一定能真正做到短作业优先，且会饥饿。）

• 高相应比优先 （上两种折中）

  （下面三种更适合交互）

• 时间片轮转

• 优先权调度

• 多级反馈队列

（详见 ipad 笔记）

3.1.6 进程的同步互斥准则

• 空闲让进：临界区空闲时，应允许一个进程访问
• 忙则等待：有一个进程正在临界区内，其他进程只能等待
• 有限等待：不能等不到呀
• 让权等待：自己进入不了临界区的进程，要释处理机，防止忙等

3.1.7 进程切换的过程

保持处理机上下文 -> 更新 PCB -> 把 PCB 移入相应队列(就绪、阻塞) ->选择另一个进程并更新其 PCB -> 更新内存管理的数据结构 -> 恢复处理机上下文

3.1.8 进程通信

• （低级方式）PV 信号量

• （高级方式：高效大量）共享：速度快（使用同步互斥工具操作共享空间）

• 消息：传递结构化的消息，直接通信或者信箱通信

• 管道：特殊共享文件，一个半双工，两个全双工

3.1.9 管程

组成： 共享数据结构 + 初始化语句 + 访问数据结构的过程（函数）。

目的： 解决信号量机制编程麻烦、易出错的问题。（封装思想)

特征： 外部进程只能通过管程提供的特定入口访问共享数据；每次仅允许一个进程执行内部过程。

3.2 死锁

（注意区分 死锁、饥饿、死循环）

根本原因是 独占资源分配不当，不是资源不足。

3.2.1 死锁条件

互不寻求

• 互斥
• 不可剥夺
• 请求保持
• 循环等待 （必要不充分）

区分不剥夺和请求保持：不剥夺是拿着苹果不吃也不能被拿走，请求保持是左手有一个，右手还可以再拿一个。

3.2.2 死锁解决

破坏死锁必要条件

1. 死锁预防 （先分配）
2. 死锁避免 （运行时判断）银行家
3. 死锁检测 （出问题再处理）

3.2.3 解除死锁

• 资源剥夺法
• 撤销进程法
• 进程回退法

3.3 内存

3.3.1 逻辑地址 & 物理地址

• 逻辑地址是相对地址，是在编译链接后指明的地址
• 物理地址是在内存中的实际地址，是装入后指明的位置

3.3.2 内存空间的分配方式

• 连续分配管理：一道作业被分配在一片连续的内存空间（分区）中

  • 单一连续分配：内存中只能有一道用户程序
  • 固定分区分配：最简单的多道程序管理方式，一个分区只能装入一道作业
  • 动态分区分配：装入时根据进程大小和动态分区分配算法（见下面）动态建立分区

• 非连续分配管理：以页或者段为分配单位，一道作业可能被划分为多个页或段装入内存，因此不连续

  • 基本分页存储管理

  • 基本分段存储管理

  • 基本段页存储管理：先分段再分页

（算法）3.3.3 动态分区分配算法

• 首次适应：最好，最简单，最快，但是会在低地址出产生大量碎片
• 最佳适应：最容易产生碎片
• 最坏适应：排序要消耗时间，效果差
• 邻近适应：内存尾部出现很多碎片

（算法）3.3.4 页面置换

• OPT： 优先淘汰最长时间不会访问页面（理想对照，无法实现）
• FIFO：优先淘汰最先进入内存的页面（唯一可能出现 belady）
• LRU：优先淘汰最近最久没访问（硬件支持，性能好，开销大）
• CLOCK：循环扫描（访问位），最多两轮
• 改进 CLOCK：加入修改位

3.3.5 虚拟内存性能因素

虚拟存储 性能 主要受 ” 缺页率 “ 影响（高会抖动），缺页率受 页面大小、分配物理块数、页面置换算法 等影响

3.4 I/O

3.4.1 I/O控制

• 程序直接控制方式：CPU 不断轮询
• 中断驱动方式：（单位是字）I/O 完成后 DMA 控制器发出中断信号
• DMA 方式：（块）
• 通道控制方式：（一组块）通道相当于弱版CPU

3.4.2 中断隐指令

• 关中断：避免保存断点被打断
• 保存断点：将当前的PC值保存在内核堆栈栈顶
• 引出中断服务程序：将当前PC修改位中断服务程序的入口地址

3.4.3 中断服务程序

• 保存现场：保存通用寄存器中的内容
• 中断服务：外部设备开始工作
• 恢复现场：将通用寄存器的内容恢复成和原来一样
• 开中断：取回中断隐指令保存在栈顶的原始程序的PC值

3.4.4 假脱机技术 spooling

• 脱离主机的控制进行输入输出，缓解设备与cpu之间的速度矛盾，实现预输入缓输出
• 利用缓冲区，将独占设备改造为共享设备（只是宏观上的共享）

3.5 文件

3.5.0 目录文件

文件控制块FCB

FCB中包括文件名，类型，文件存放的物理位置等等信息
FCB 是为了实现按名存取而存在的

inode结点（FCB改进）

目录项为文件名+所以节点的指针

由于查找的过程中只需要用到文件名这个信息，所以将除了文件名之外的文件信息放在索引结点中。
使得目录项较小，每个磁盘可以存更多的目录项，大大提高了文件索引速度。

3.5.1 逻辑结构

• 顺序文件（顺序存储）
• 顺序文件（索引存储）
• 索引文件
• 索引顺序文件

3.5.2 物理结构

• 连续分配（顺序分配）：速度块，随机访问，有碎片
• 链接分配（默认隐式）：每个盘都存有指向下一个盘块的指针，只能顺序访问，不能随机访问
• 链接分配（显式）：建立 文件分配表 FAT，常驻内存
• 索引分配 ： 建立索引表，支持随机访问

3.5.3 文件共享

• 硬链接
• 软链接

3.5.4 磁盘读写时间

一次磁盘读写时间 = 寻道时间（找磁道）+ 旋转延迟时间（找扇区）+ 传输时间（传输数据）

（算法）3.5.5 磁盘调度算法

• FCFS （先来先服务）公平、简单、性能差
• SSTF（最短寻找时间优先）选最近的，可能饥饿
• SCAN（扫描到最边缘）响应不平均
• C-SCAN（返回途中不响应）响应平均

3.5.6 磁盘初始化

1. 物理格式化：划分扇区，确定管理扇区所需的数据结构等
2. 磁盘分区：磁盘由多个柱面构成
3. 逻辑格式化：创建文件系统

3.6 中断

3.6.1 中断 & 异常

外中断：指令无关，来自 CPU 外部，如 I/O 中断、定时器中断、外部信号中断等。狭义上也叫中断;
异常：指令相关，来自 CPU 内部，也称陷入。如校验错、页面失效、溢出、除数为零 等。

3.6.2 中断 & 系统调用

中断是由外设产生,无意的, 被动的

系统调用是由应用程序请求操作系统提供服务产生, 有意的,主动的。要从用户态通过中断进入内核态。

四、计算机网络

4.1 网络结构

4.1.1 OSI 层次

【物联网淑慧试用】

• 物理层： 单位 bit，传输透明 bit 流
• 数据链路层： 单位 帧，组帧，差错控制，流量控制，协议： MAC HDLC PPP
• **网络层：**单位 数据报，差流拥网，路由选择，**协议：**IP ARP ICMP
• **传输层：**单位 报文，端到端的可靠传输，**协议：**TCP UDP
• **会话层：**建立、管理和终止会话
• **表示层：**数据压缩、加密解密
• **应用层：**网络应用，协议： FTP HTTP DNS

4.2 物理层

4.2.1 物理层设备

• 中继器：对信号进行放大和再生
• 集线器：多接口中继器，这两个设备都不会隔离冲突域

4.2.2 数据交换方式

• **电路交换：**两节点之间有一条专用的物理通路

  （下两种为 存储转发式）

• **报文交换：**存储转发报文，报文长度 大小没有限制

• 分组交换：将报文分为若干分组

  • 数据报
  • 虚电路

4.2.3 数据报 VS 虚电路

	数据报	虚电路
链接	不需要	必要
目的地址	每个分组都有	建立阶段有，后用虚电路号
路由选择	各分组独立选择	各分组一样
有序到达	不保证	保证
可靠	不保证	保证
故障适应	不影响全局	影响全局

4.2.4 通信基础

• 奈氏准则：（内忧）无噪声， 极限数据传输率 = 2 W l o g 2 V 极限数据传输率 = 2Wlog_2V 极限数据传输率=2Wlog2​V
• 香农定理：（外患）有噪声， 极限数据传输率 = W l o g 2 ( 1 + S / N ) 极限数据传输率 = Wlog_2(1 + S/N) 极限数据传输率=Wlog2​(1+S/N)
• 编码（转数字）
  • 数字数据转数字信号：曼彻斯特（01图像是定好的），差分曼彻斯特（同1异0）
  • 模拟数据转数字信号：抽样，量化，编码
• 调制（转模拟）
  • 数字数据转模拟信号：调频，调幅，调相
  • 模拟数据转模拟信号：频分复用

4.3 数据链路层

4.3.1 重要功能

• 【流川（差）枫】
• 流量控制：通过停等协议，后退N帧协议，选择重传协议等达到流量控制
• 差错控制：通过奇偶校验码，循环冗余码，海明码等实现差错控制
• **封装成帧：**用转义字符法，0比特填充法等实现帧同步和帧定界

4.3.2 滑动窗口协议

• 停止等待协议：
  • 发送窗口 = 1，接收窗口 = 1，传输效率很低
• 后退N帧协议：
  • 发送窗口 > 1，接收窗口 = 1，接收方按序接收，累积确认
  • 虽然可以连续发送，但出错之后要把原来已经发送过的帧全部重传，他的效率并不一定比停止等待好
• 选择重传协议：
  • 发送窗口 > 1，接收窗口 > 1
  • 不采用累积确认，谁超时了就重传谁

4.3.3 介质访问控制

解决广播信道上两对结点之间的通信不受干扰的问题

• 静态划分信道

  • 频分多路复用：每个用户被分配到一个频带
  • 时分多路复用：每个用户占用一个时隙
  • 波分多路复用：光的频分多路复用
  • 码分多址：即共享频率又共享时间，规则很复杂有点类似向量的叠加

• 动态划分信道

  • 随机访问
    • ALOHA：不监听信道，冲突了就重发
    • CSMA：监听信道，发送数据之前检测总线上是否有其他用户在发
      • 三策略：1坚持（发，听），非坚持（发，随机听），p坚持（随机发，听）
    • CSMA/CD：载波监听多点接入，碰撞检测
      • 先听后发，边发边听，冲突立停，执行退避
      • 重传时机：二进制指数退避算法
      • 最小帧长：如果帧很短，在检测到碰撞之前就已经传完了，会无法挽回，所以规定了最短帧长。最小帧长=往返传播时延t*数据传输率。（以太网规定最小帧长为64B）
    • CSMA/CA：发前先广播通知，随机退避，没确认重发
  • 轮流访问
    • 轮询协议：主节点轮流邀请从属节点发送数据
    • 令牌传递协议：在环形网络上利用令牌来实现公平地轮流访问信道

4.3.4 MAC地址 & IP 地址

信息传递时需要知道：终点地址和下一跳地址。

ip地址本质上是终点地址，过路由器的时候不会改变；

MAC地址是下一跳地址，每跳过一次路由器都会改变一次；

4.3.5 数据链路层设备

网桥和交换机（交换机是多接口的网桥）

功能：查看mac帧中的目的mac地址，确定转发的接口

具有自学习的能力，能够自己建立并更新转发表

4.4 网络层

4.4.1 路由协议

URBT 你是变态

4.4.2 RIP & OSPF

RIP

• UDP
• 定期传送
• 仅和 “邻居” 谈
• 整个路由表
• 每条路径目的、跳数

OSPF

• IP
• 主动测试邻居节点状态
• 发给域内所有节点（泛洪法）
• 指导所有网络拓扑信息
• 发送部分路由表
• Dijkstra 计算

4.4.3 ARP

根据 IP 地址，求得 MAC 地址

4.4.4 ICMP

功能是检错而不是纠错；

它将出错的报文返回给发送方的设备，发送方根据 ICMP 报文确定错误类型，从而更好的重发错误的数据包。

为了更有效地转发ip数据报和提高交付成功的机会

• 差错报文
• 询问报文

4.5 传输层

4.5.1 TCP & UDP

TCP	UDP
有连接	无连接
可靠	不可靠
面向字节	面向报文
首部开销大（20B）	首部开销小（8B）
分用复用，差流拥，可靠传输	分用复用，差
用于可靠性要求高的场景	用于及时性要求高的场景

4.5.2 TCP 握手

建立连接，三次握手

断开连接，四次挥手

4.5.3 TCP 流控 & 塞控

（发送窗口=min(拥塞窗口，接收窗口）

塞控和流控均能改变发送窗口大小，控制发送速度

	拥塞控制	流量控制
目的	防止过载	控制速度
范围	整个网络	当前连接
任务	根据算法告知拥塞窗口大小	及时告知发送（接收）窗口大小

4.5.4 TCP 拥塞控制

• 慢开始：cwnd（拥塞窗口）为 1，小于阈值时，收到加倍
• 拥塞避免：大于阈值时，cwnd 每次 + 1
• 快重传：收到三个重复 ACK，则判断拥塞，直接重传
• 快恢复：cwnd 直接设为 阈值

TCP 建立连接和网络出现超时时，采用 慢开始 和 拥塞避免；当收到冗余 ACK，采用快重传和快恢复。

4.5.5 TCP 可靠传输

• **校验：**目的是检测数据在传输中有没有任何变化
• **序号：**报文段中第一个字节的序号作为报文段的序号
• **确认：**TCP使用累计确认，确认按需到达的报文段
• 重传：
  • 超时重传：每个报文段有一个计时器，采用自适应算法，动态改变重传时间RRTs(加权平均往返时间)
  • 快速重传：接收到三个冗余ACK时重传

4.6 应用层

4.6.1 DNS

**作用：**域名 转 IP地址

**原理：**ip地址与域名的对应关系会存储在某一个“权限域名服务器”上，DNS的解析过程就是查找这个权限域名服务器，并且从该服务器上获取域名对应的ip地址的过程。

查询方式：

• 递归查询：靠别人来查
• 迭代查询：靠自己来查，本地域名服务器的负担较重。

查询过程：

1. 拿到域名之后现在本地高速缓存中查询，如果最近访问过这个域名，本地缓存中会保存对应的ip
2. 没找到，向本地域名服务器发起查询请求
3. 本地域名服务器向根域名服务器发起请求
4. 根域名服务器向顶级域名服务器发起请求
5. 顶级域名服务器找到权限域名服务器
6. 逐步返回查询到的请求，并缓存在本地的DNS高速缓存中

4.6.2 HTTP（超文本传输协议）

**特点：**基于TCP：HTTP本身是没有连接的，但是TCP是有连接的

4.6.3 FTP（文件传输协议）

**作用：**允许客户指明文件的类型和格式，提供不同主机系统之间的文件传输能力（上传和下载）

**连接：**控制连接 + 数据连接

• 控制连接：始终保持
• 数据连接：保持一会，没有数据要传就断开

端口：

• 主动模式下，服务器使用20端口进行数据连接，
• 被动模式下，双方协商数据连接的端口

默认情况，服务器端使用控制连接21，数据连接20，客户端使用的都是临时端口

4.6.4 邮件协议

• **SMTP：**发送方到邮件服务器，邮件服务器到邮件服务器之间使用的邮件协议
• **POP3：**邮件服务器到接收方使用的邮件协议
• **MINE：**SMTP只能传送 ASCII，MINE 扩展了传送范围

4.6.5 DHCP（动态 IP地址）

特点：

• 基于UDP，（因为在DHCP结束之前，本机都是没有ip地址的）
• 支持地址重用，每个ip地址都有一个租用期

过程：

主机 广播 DHCP发现报文：请问有没有DHCP服务器呀？

所有的DHCP服务器 广播 提供报文：有的，我在

主机 广播 DHCP请求报文：请给我一个ip地址吧~

DHCP 广播 DHCP确认报文：好的

4.7 杂问

4.7.1 各层设备对比

	能否隔离冲突域	能否隔离广播域
中继器、集线器	否	否
网桥、交换机	是	否
路由器	是	是