魔装少男的博客

我可爱又美丽却能唤来死亡
虽然我可爱又迷人,但我能招来死亡

0%

408流水账记录

408学习流水账，数据结构还差最后一章的部分

计算机组成原理

计算机系统概述

计算机系统概述

   def：计算机系统 = 硬件 + 软件

软件：

  • 系统软件：用来管理整个计算机系统
  • 应用软件：按任务需要编制成的各种程序

硬件的发展

第一台电子数字计算机：ENIAC(1946)（冯诺依曼）
占地面积约 170 平方米（体积大）
耗电量 150 千瓦（耗电量超大）
运算速度：5000 次加法/秒

发展阶段 时间 逻辑元件 速度(次/秒) 内存 外存
第一代 1946-1957 电子管 几千-几万 汞延迟线、磁鼓 穿孔卡片、纸带
第二代 1958-1964 晶体管（几万-几十万个） 几万几十万 磁芯存储器 磁带
第三代 1964-1971 中小规模集成电路 几十万-几百万 半导体存储器 磁带、磁盘
第四代 1972-现在 大规模、超大规模集成电路 上千万-万亿 半导体存储器 磁盘、磁带、光盘、半导体存储器

第二代体积、功耗降低，出现面向过程的程序设计语言：FORTRAN，有了操作系统维形。
第三代计算机主要用于科学计算等专业用途，高级语言迅速发展，开始有了分时操作系统。
第四代开始出现“微处理器”、微型计算机，个人计算机（PC）萌芽，操作系统：windows、Macos、Linux…
机器字长：计算机一次整数运算所能处理的二进制位数。

微处理器 机器字长 年份 晶体管数目
8080 8 位 1974
8086 16 位 1979 2.9 万
80286 16 位 1982 13.4 万
80386 32 位 1985 27.5 万
80486 32 位 1989 120.0 万
Pentium 64 位 1993 310.0 万
Pentium pro 64 位 1995 550.0 万
Pentium Il 64 位 1997 750.0 万
Pentium III 64 位 1999 950.0 万

1947 年，贝尔实验室，发明了“晶体管”；
1955 年，晶体管之父：威廉·肖克利在硅谷创建肖克利实验室股份有限公司；
1957 年，八叛徒（traitorouseight）创立仙童半导体公司；
1959 年，仙童半导体公司发明“集成电路”；
1968 年摩尔等人离开仙童，创立 Intel；
1969 年，仙童销售部负责人桑德斯离开仙童，创立 AMD。

摩尔定律：集成电路上可容纳的晶体管数：约每隔 18 个月便会增加一借，整体性能也将提升一倍。

知识回顾与重要考点

计算机硬件的基本组成

  • 早期冯诺依曼机的结构
  • 现代计算机的结构(也是冯的优化)

早期冯诺依曼机的结构

ENIAC（手动接线来控制计算）: arrow_right: 冯·诺依曼提出 “存储程序”: arrow_right: 第一台采用冯诺依曼结构的计算机 EDVAC(ElectronicDiscreteVariableAutomaticComputer）

“存储程序” 的概念是指 将指令以二进制代码的形式事先输入计算机的主存储器，然后按其在存储器中的首地址执行程序的第一条指令，以后就按该程序的规定顺序执行其他指令，直至程序执行结束。

image-20231027110010514

在计算机系统中，软件和硬件在逻辑上是等效的。Eg：对于乘法运算，可以设计一个专门的硬件电路实现乘法运算，也可以用软件的方式，执行多次加法运算来实现。

冯·诺依曼计算机的特点：

  1. 计算机由五大部件组成
  2. 指令和数据以同等地位存于存储器，可按地址寻访
  3. 指令和数据用二进制表示
  4. 指令由操作码和地址码组成
  5. 存储程序
  6. 以运算器为中心（导致数据计算效率降低）

现代计算机的结构

现代计算机的结构

CPU = 运算器+控制器

简化后：

i 现代计算机的结构

知识回顾与重要考点: star:

各个硬件的工作原理

主存储器的基本组成

主存储器

主存储器

存储单元

image-20231027113134024

运算器的基本组成

image-20231027113600782

通用寄存器可能有多个。

控制器的基本组成

image-20231027113757272

完成一条指令：

  • 取指令 ：根据 PC 记录的地址
  • 分析指令：指令放入 IR，CU 分析
  • 执行指令：CU 分析完后，控制其它部件配合完成指令的具体执行。

多数情况下，将前两个阶段称为取指，最后阶段称为执行。

计算机的工作过程

计算机的工作过程

取数过程

（MAR）表示 MAR 里面的内容。M（MAR）-> MDR 表示主存储器里 MAR 地址所指的存储单元的数据放到 MDR。取指令结束后，PC 自动加一。

乘

加

存

停机

总结：

取总结

知识回顾与重要考点

计算机系统的多级层次结构

计算机系统的多级层次结构

三种级别语言

知识回顾与重要考点

计算机性能指标

存储器的性能指标

总容量 = 存储单元个数×存储字长 bit 1Byte = 8bit
= 存储单元个数×存储字长/8 Byte
例：MDR 为 8 位，MAR 为 32 位
总容量 = 2^32 * 8 bit = 4GB
(做题时，MAR 位数直接反映实际容量，按最大值来算)

K：2^10 M：2^20 G：2^30 T：2^40

CPU 的性能指标

CPU 主频：CPU 内数字脉冲信号振荡的频率(每秒多少个时钟周期)。单位：赫兹，Hz。

CPU 时钟周期：每一个脉冲信号的时间。单位：微秒、纳秒。

CPU主频(时钟频率)=1CPU时钟周期\begin{array}{rl}\mathrm{CPU}\text{主频(时钟频率)}&=\frac1{CPU\text{时钟周期}} \end{array}

CPI（Clock cycle Per Instruction）：执行一条指令所需的时钟周期数

不同的指令，CPI 不同。甚至相同的指令，CPI 也可能有变。

执行一条指令的耗时 = CPI × CPU 时钟周期

Eg：某 CPU 主频为 1000Hz，某程序包含 100 条指令，平均来看指令的 CPl = 3。
该程序在该 CPU 上执行需要多久？t = 3 *（1/1000）* 100 = 0.3s

CPU执行时间(整个程序的耗时)=CPU时钟周期数/主频=(指令条数*CPI)/主频\text{CPU执行时间(整个程序的耗时)=CPU时钟周期数/主频=(指令条数*CPI)/主频}

IPS（Instructions Per Second )：每秒执行多少条指令 （KIPS、MIPS）

IPS=主频平均CPI{\mathrm{IPS}=\frac{\text{主频}}{\text{平均}\mathrm{CPI}}}

FLOPS（Floating-point Operations Per Second）：每秒执行多少次浮点运算（KFLOPS、MFLOPS、GFLOPS、TFLOPS，此处 K、M、G、T 为数量单位）

系统整体的性能指标

数据通路带宽：数据总线一次所能并行传送信息的位数（各硬件部件通过数据总线传输数据）

吞吐量：指系统在单位时间内处理请求的数量。
它取决于信息能多快地输入内存，CPU 能多快地取指令，数据能多快地从内存取出或
存入，以及所得结果能多快地从内存送给一台外部设备。这些步骤中的每一步都关系
到主存，因此，系统吞吐量主要取决于主存的存取周期。

响应时间：指从用户向计算机发送一个请求，到系统对该请求做出响应并获得它所需
要的结果的等待时间。
通常包括 CPU 时间（运行一个程序所花费的时间）与等待时间（用于磁盘访问、存储
器访问、I/O 操作、操作系统开销等时间）。

基准程序（跑分软件）是用来测量计算机处理速度的一种实用程序，以便于被测量的计算机性能可以与运行相
同程序的其它计算机性能进行比较。

知识回顾与重要考点

数据的表示和运算

进制计数制

进位计数制

任意进制: arrow_right: 十进制

image-20231027140225185

image-20231027140254082

二进制互转八进制、十六进制：3、4 分组。

补零：整数部分补在头部，小数部分补在尾部。

十进制转任意进制：
image-20231027141315288

小数部分：（也可以用凑的方式）
image-20231027141550168

此图说明，二进制无法准确表示 0.3。

真值：符合人类习惯的数字

机器数：数字实际存到机器里的形式，正负号需要被“数字化

知识回顾与重要考点

BCD 码（新大纲不考）

BCD 码

8421 码:
8421

例：5：0101，8：1000，5+8 = 1101（不在表里，无意义即结果为 1010~1111~10010）+6（0110，0-15 里余 6 个数）= 0001 0011（0011 为 3，前面补 3 个 0）

例：9+9：1001+1001 = 10010（超出）+0110 = 00011000（前面补 3 个 0）

余 3 码:（无权码）

余 3 码

2424 码：

2421

知识回顾与重要考点

无符号整数表示和运算

①全部二进制位都是数值位，没有符号位，第 i 位的位权是 2i−12^{\mathrm{i}-1}
② nbit 无符号整数表示范围 0∼2n−1\color{red}{0}\color{red}{\sim}\color{red}{2^{n}}\color{red}{-1}，超出则 溢出，意味着该计算机无法一次处理这么多
③可以表示的 最小的数全 0，可以表示的 最大的数全 1

计算机硬件如何做无符号整数的加法：从最低位开始，按位相加，并往更高位 进位。

计算机硬件如何做无符号整数的减法：

  1. “被减数”不变，“减数”全部位按位取反、末位+1, 减法变加法
  2. 从最低位开始，按位相加，并往更高位 进位

Tips: 加法电路造价便宜，减法电路造价昂贵。若可将减法转变为加法，省钱！

带符号整数表示和运算（原/反/补）

原码表示法

Tips：现在的个人计算机机器字长通常是 64 位，或至少 32 位。

原码

  • 符号位“0/1”对应正/负”，剩余的数值位表示真值的绝对值
  • 若机器字长 n+1 位，带符号整数的原码表示范围：−(2n−1)⩽x⩽2n−1\color{red}{-(2^n\color{red}{-1})}\quad\leqslant\color{red}{x}\leqslant\color{red}{2^n\color{red}{-1}}
  • 真值 0 有两种形式： +0 和 -0，[+0]原=0,0000000;[−0]原=1,0000000\begin{bmatrix}+0\end{bmatrix}_\text{原}{ = 0 , 0 0 0 0 0 0 0 ; }\quad\begin{bmatrix}-0\end{bmatrix}_\text{原}{ = 1 , 0 0 0 0 0 0 0}

考试写法：

  • 常见书面写法：X =-19，[x]原=1,0010011\left [x\right]_\text{原}{ = 1 , 0 0 1 0 0 1 1}
  • 若未指明机器字长，也可写为：\left.\left [\begin{smallmatrix}x\end{smallmatrix}\right.\right]_\text{原}{ = 1 , 1 0 0 1 1}

原码的缺点：符号位不能参与运算，需要设计复杂的硬件电路才能处理，费钱！贵！

用补码表示真值一一 符号位可以参与运算

原码→反码→补码的转换

原码→反码→ > 补码的转换

负数的补码转反码：

  • 末位减一（不好算）
  • 先转原码，再转反码

负数原码补码快速转换：从右往左找到第一个 1，这个 1 左边的所有“数值位”按位取反

补码运算

image-20231028072720919

计算机硬件如何做补码的加法：从最低位开始按位相加（符号位参与运算），并往更高位进位

求该数的相反数的补码：

image-20231028073606281

快速方法：找到的第一个 1，左边的全部取反。

知识回顾与重要考点

image-20231028074223046

原/反/补码特性对比

image-20231028074425970

n+1 bit 合法表示范围 最大的数 最小的数 真值 0 的表示
带符号整数：原码 −(2n−1)≤x≤2n−1-(2^n-1)\leq x\leq2^n-1 0,111...111=2n−1\begin{aligned}\mathbf{0},&111...111\\&=2^n-1\end{aligned} 1,111...111=−（2n−1）\begin{aligned}1, & 111...111\\ & =-（2^{n}-1）\end{aligned} [+0]原=0,000...000[−0]原=1,000...000\begin{array}{l}{[+0]_{\text{原}}=\mathbf{0},000...000}\\{[-0]_{\text{原}}=\mathbf{1},000...000}\\\end{array}
带符号整数：反码 −(2n−1)≤x≤2n−1\begin{array}{rr}-(2^n-1)&\leq x\leq2^n-1\end{array} 0,111...111=2n−1\begin{aligned}\mathbf{0},&111...111\\&=2^n-1\end{aligned} 1,111...111=−（2n−1）\begin{aligned}1, & 111...111\\ & =-（2^{n}-1）\end{aligned} [+0]反=0,000...000[−0]反=1,111...111\begin{array}{l}{[+0]_{\text{反}}=0,000...000}\\{[-0]_{\text{反}}=1,111...111}\\\end{array}
带符号整数：补码 −2n≤x≤2n−1\color{red}{-2^n}\leq x\leq2^n{-1} 0,111,...111=2n−1\begin{array}{c}\mathbf{0},111,...111\\=2^{n-1}\end{array} *⁡1,000...000=−2n\color{red}{\underset{=-2^n}{\operatorname*{1,000...000}}} [0]补=0,000...000真值0只有一种补码\begin{array}{c}\color{red}{[0]_\text{补}=0,000...000}\\\color{red}{\text{真值}0\text{只有一种补码}} \end{array}
带符号整数：移码 −2n≤x≤2n−1\color{red}{-2^n}\leq x\leq2^n{-1} 1,111,...111=2n−1\begin{array}{c}\mathbf{1},111,...111\\=2^{n-1}\end{array} *⁡0,000...000=−2n\color{red}{\underset{=-2^n}{\operatorname*{0,000...000}}} [0]补=1,000...000真值0只有一种补码\begin{array}{c}\color{red}{[0]_\text{补}=1,000...000}\\\color{red}{\text{真值}0\text{只有一种补码}} \end{array}
无符号整数 0≤x≤2n+1−10\leq x\leq2^{n+1}-1 1111...111=2n+1−1\begin{array}{c}1111...111\\=2^{n+1}-1\end{array} 0000...000=0\begin{array}{c}0000...000\\=0\end{array} 0000...000\text{0000...000}

原码和反码的合法表示范围完全相同，都有两种方法表示真值 0。
补码 的合法表示范围 比原码多一个负数，只有一种方法表示真值 0。

常见考点：两个数 A 和 B 进行某种运算后，是否发生溢出？手算做题可以带入十进制验证，是否超出合法范围

例：8bit，-64-64 =-128，原码表示移除，补码表示正好。

带符号整数移码表示

原反补移

补码的基础上将 符号位取反。注意：移码只能用于表示整数

[0]移=1000000[0] _{移}=1000000 注意！真值 0 只有一种表示形式。

若机器字长 n+1 位，移码整数的表示范围：−2n≤x≤2n−1\color{red}{-2^n\leq x\leq2^n-1} （与补码相同）

移码

移码常用于浮点数阶码中。

几种码的表示

定点小数表示和运算

image-20231028085125823

转换：一模一样

小数转换

加减运算：

对两个定点小数 A、B 进行加法/减法时，需要先转换为补码。

计算机硬件如何做定点小数外码的加法：从最低位开始，按位相加（符号位参与运算），并往更高位进位

计算机硬件如何做定点小数补码的减法：

  1. “被减数”不变，“减数”全部位按位取反、末位+1，减法变加法
  2. 从最低位开始，按位相加并，往更高位进位
n+1 bit 合法表示范围 最大的数 最小的数 真值 0 的表示
带符号整数：原码 −(2n−1)≤x≤2n−1-(2^n-1)\leq x\leq2^n-1 0,111...111=2n−1\begin{aligned}\mathbf{0},&111...111\\&=2^n-1\end{aligned} 1,111...111=−（2n−1）\begin{aligned}1, & 111...111\\ & =-（2^{n}-1）\end{aligned} [+0]原=0,000...000[−0]原=1,000...000\begin{array}{l}{[+0]_{\text{原}}=\mathbf{0},000...000}\\{[-0]_{\text{原}}=\mathbf{1},000...000}\\\end{array}
带符号整数：反码 −(2n−1)≤x≤2n−1\begin{array}{rr}-(2^n-1)&\leq x\leq2^n-1\end{array} 0,111...111=2n−1\begin{aligned}\mathbf{0},&111...111\\&=2^n-1\end{aligned} 1,111...111=−（2n−1）\begin{aligned}1, & 111...111\\ & =-（2^{n}-1）\end{aligned} [+0]反=0,000...000[−0]反=1,111...111\begin{array}{l}{[+0]_{\text{反}}=0,000...000}\\{[-0]_{\text{反}}=1,111...111}\\\end{array}
带符号整数：补码 −2n≤x≤2n−1\color{red}{-2^n}\leq x\leq2^n{-1} 0,111,...111=2n−1\begin{array}{c}\mathbf{0},111,...111\\=2^{n-1}\end{array} *⁡1,000...000=−2n\color{red}{\underset{=-2^n}{\operatorname*{1,000...000}}} [0]补=0,000...000真值0只有一种补码\begin{array}{c}\color{red}{[0]_\text{补}=0,000...000}\\\color{red}{\text{真值}0\text{只有一种补码}} \end{array}
带符号整数：移码 −2n≤x≤2n−1\color{red}{-2^n}\leq x\leq2^n{-1} 1,111,...111=2n−1\begin{array}{c}\mathbf{1},111,...111\\=2^{n-1}\end{array} *⁡0,000...000=−2n\color{red}{\underset{=-2^n}{\operatorname*{0,000...000}}} [0]补=1,000...000真值0只有一种补码\begin{array}{c}\color{red}{[0]_\text{补}=1,000...000}\\\color{red}{\text{真值}0\text{只有一种补码}} \end{array}
无符号整数 0≤x≤2n+1−10\leq x\leq2^{n+1}-1 1111...111=2n+1−1\begin{array}{c}1111...111\\=2^{n+1}-1\end{array} 0000...000=0\begin{array}{c}0000...000\\=0\end{array} 0000...000\text{0000...000}
定点小数：原码 −(1−2−n)≤x≤1−2−n-(1-2^{-n})\leq x\leq1-2^{-n} 0,111...111=1−2−n\begin{array}{c}{\mathbf{0},111...111}\\{=1-2^{-n}}\\\end{array} 1,111...111=−(1−2−n)\begin{matrix}1,111...111\\=-(1-2^{-n})\end{matrix} [+0]原=0,000...000[−0]原=1,000...000\begin{array}{c}{[+0]_{原}=\mathbf{0},000...000}\\ {[-0]_{原}=\mathbf{1},000...000}\end{array}
定点小数：反码 −(1−2−n)≤x≤1−2−n-(1-2^{-n})\leq x\leq1-2^{-n} 0,111...111=1−2−n\begin{array}{c}{\mathbf{0},111...111}\\{=1-2^{-n}}\\\end{array} 1,000...000=−(1−2−n)\begin{array}{c}\mathbf{1},000...000\\=-(1-2^{-n})\end{array} [+0]反=0,000...000[−0]反=1,1111...111\begin{array}{c}{[+0]_{反}=0,000...000}\\ {[-0]_{反}=1,1111...111}\end{array}
定点小数：补码 −1≤x≤1−2−n\color{red}{-1}\leq x\leq1-2^{-n} 0,111...111=1−2−n\begin{array}{c}{0,111...111}\\{=1-2^{-n}}\\\end{array} 1,000...000=−1\begin{aligned}\color{red}{1,000...000}\\\color{red}{=-1}\end{aligned} *⁡[0]补=0,000...000真值0只有一种补码\underset{\text{真值}0\text{只有一种补码}}{ \operatorname* { [ 0 ] _ {\text{补}=0,000...000}}}

4bit 扩展 8bit：定点小数补后面，定点整数补在符号位后。

image-20231028091502076

计算机硬件如何做补码的加法：从最低位开始，按位相加（符号位参与运算），并往更高位进位。

image-20231028091639355

计算机硬件如何做带符号数补码的减法：

  1. “被减数”不变，" 减数”全部位按位取反、末位+1，减法变加法
  2. 从最低位开始，按位相加，并往更高位进位

奇偶校验码（新大纲不考）

奇校验码：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
偶校验码：整个校验码（有效信息位和校验位）中“1 " 的个数为偶数。

image-20231028092525267

偶校验的硬件实现：各信息进行异或（模 2 加）运算，得到的结果即为偶校验位

算术逻辑单元

电路基本原理&加法器设计

ALU：

  • 算术运算：加、减、乘、除等
  • 逻辑运算：与、或、非、异或等
  • 铺助功能：移位、求补等

image-20231028093741674

image-20231028095008738

image-20231028095125058

一位全加器：

一位全加器

串行加法器：

串行加法器

并行加法器：

image-20231028101025376

image-20231028101207146

并行进位加法器

image-20231028101523588

image-20231028101741362

image-20231028102556574

缺点：继续套娃导致电路越来越复杂。

image-20231028124658357

补码加减运算器

加法器原理

补码加/减法运算方法

image-20231028130333796

image-20231028130359786

image-20231028130935289

加减运算溢出判断

原码的加减运算

原码的加减运算

image-20231028132333790

补码的加减运算

溢出判断

溢出判断

溢出判断

溢出判断

溢出判断

溢出判断

溢出判断

双符号位补码又称：模 4 补码（实际存储时只存储 1 个符号位，运算时会复制一个符号位）
单符号位补码又称：模 2 补码

符号扩展

image-20231028135605511

知识点回顾

image-20231028135706956

标志位生成

image-20231028140429626

image-20231028140539882

移位运算

image-20231028141133565

算数移位

image-20231028141541631

image-20231028141745288

image-20231028141822627

image-20231028141929587

image-20231028142223961

总结：

image-20231028142421062

image-20231028142456379

逻辑移位

image-20231028142601787

image-20231028142827462

循环移位

image-20231028143155940

知识点回顾

image-20231028143325769

定点数原码乘法运算

手算乘法

手算乘法

原码一位乘法

image-20231030035800524

image-20231030035819826

image-20231030035839975

image-20231030035920319

image-20231030040003240

image-20231030040053432

image-20231030040113095

image-20231030040140519

image-20231030040214814

image-20231030040227711

image-20231030040243117

image-20231030040318826

image-20231030040637122

补码一位乘法

image-20231030041109876

image-20231030041145464

image-20231030041239681

image-20231030041325829

image-20231030041751129

知识点回顾

image-20231030041856328

定点数原码除法运算

手算除法

image-20231030042432697

image-20231030042807590

image-20231030042953068

原码除法：恢复余数法

image-20231030043527359

image-20231030043608859

image-20231030043729207

image-20231030043810866

image-20231030043831796

image-20231030043904492

image-20231030044009296

image-20231030044031865

image-20231030044117335

image-20231030044142984

image-20231030044406256

image-20231030044700744

原码除法：加减交替法 又名：不恢复余数法

image-20231030045023941

image-20231030045052146

image-20231030050109938

定点小数：规定被除数小于除数，否则商大于 1，但定点小数不能表示大于 1。第一步被除数减除数得到的余数一定要是一个负值，如果是正值，说明商 1，说明被除数比除数大，此时硬件电路会检测出这个问题并停止除法运算。

补码除法运算

image-20231030050706280

image-20231030050808770

除法运算总结回顾

image-20231030050853936

C 语言中的强制类型转换

C 语言中定点整数是用“补码”存储的.

image-20231030051515297

数据的存储和排列

大小端模式

image-20231030051912968

image-20231030052152957

字逻辑左移得字节地址。

image-20231030052538902

浮点数的表示和运算

image-20231030052739496

浮点数的表示

image-20231030052857500

image-20231030053129938

image-20231030053505307

image-20231030053636190

image-20231030053915434

image-20231030054022541

image-20231030054214941

image-20231030054246312

image-20231030054522759

注：采用“双符号位”，当溢出发生时，可以挽救。更高的符号位是正确的符号位。

image-20231030055118183

image-20231030055215222

image-20231030055310921

image-20231030055659781

知识点回顾

image-20231030055757326

浮点数标准 IEEE754

image-20231030060421529

image-20231030060659258

image-20231030060752388

image-20231030061105476 image-20231030061403788

image-20231030061703883 image-20231030062152164

image-20231030062411383

image-20231030062703353

此处 E 看作无符号数: arrow_up:

image-20231030062718972

此处 E 看作无符号数: arrow_up_down:

image-20231030062924375

知识点回顾

image-20231030063024759

浮点数的运算

image-20231030063245393

加减运算

image-20231030063921904

image-20231030065201617

image-20231030065607184

强制类型转换

image-20231030065918907

image-20231030070121768

image-20231030070143910

本节回顾

image-20231030070237249

存储系统

存储系统基本概念

image-20231101094036643

image-20231101094859018

image-20231101095359961

image-20231101095521575

image-20231101095910196

image-20231101100106803

image-20231101100306163

image-20231101100518775

知识回顾

image-20231101100606388

主存储器的基本组成

image-20231101100724731

半导体元件的原理

基本的半导体元件及原理

存储芯片的基本原理

image-20231101101411953

image-20231101101527606

image-20231101101603659

image-20231101101903839

可能出题判断芯片引脚数量。

image-20231101102042408

如何实现不同的寻址方式

image-20231101102325022

本节回顾

image-20231101102350677

SRAM 和 DRAM

image-20231101102459046

存储元件不同导致的特性差异

image-20231101102554287 image-20231101103058719 image-20231101103116609

image-20231101103159250

image-20231101103343531

DRAM 的刷新

image-20231101103802901

image-20231101103640816

DRAM 的地址线复用技术

image-20231101104301097

本节回顾

image-20231101104431165

只读存储器 ROM

image-20231101105327749

image-20231101105954131

image-20231101110139838

image-20231101110159580

image-20231101110228161

本节回顾

image-20231101110309236

双端口 RAM 和多模块存储器

image-20231101110609254

image-20231101110623430

双口 RAM

image-20231101111144486

image-20231101111445479

image-20231101111752090

image-20231101111943125

image-20231101112115756

image-20231101112157656

image-20231101112251757

多模块存储器

image-20231101112625456

image-20231101112925748

主存储器与 CPU 的连接

image-20231101113354439

单块存储芯片与 CPU 的连接

image-20231101113707539

image-20231101113808143

image-20231101113950706

image-20231101114232611

image-20231101114308084

多块存储芯片与 CPU 的连接

image-20231101114935172

image-20231101115154858

image-20231101115311053

image-20231101115445976

image-20231101115627025

实际不采用，但考试采用: arrow_down:

image-20231101115734235

image-20231101115751874

image-20231101115924891

关于译码器知识的补充

image-20231101120148032

image-20231101120601559

本节回顾

image-20231101115949331

外部存储器

image-20231101120728626

磁盘存储器

image-20231101120946480

image-20231101121059262

image-20231101121218009

image-20231101121609493

image-20231101121627361

image-20231101122004413

旋转延迟时间通常是转半圈的时间。

image-20231101122339055

image-20231101122316666

image-20231101122550061

image-20231101122639968

磁盘阵列

image-20231101122942634

image-20231101123002818

image-20231101123115975

image-20231101123235902

image-20231101123412726

image-20231101123421203

本节回顾

image-20231101123511788

固态硬盘 SSD

image-20231101123850122

image-20231101123938803

image-20231101124218411

image-20231101124316913

image-20231101124943087

Cache（大小题高频考点）

基本原理基本概念

image-20231101125405203

image-20231101125731684

image-20231101125755369

image-20231101130248187

image-20231101130452630

image-20231101130611781

image-20231101130836439

image-20231101131034764

知识回顾

image-20231101131105627

Cache-主存映射方式

image-20231102072104746

image-20231102072130711

image-20231102072248929

全相联映射（随意放）

image-20231102072514442

image-20231102072738850

直接映射（只能放固定位置）

image-20231102073020035

image-20231102073115870

image-20231102073159841

组相联映射（可放到特定分组）

image-20231102073332167

image-20231102073418128

知识回顾

image-20231102073537237

Cache 替换算法

image-20231102073729039

image-20231102073739831

随机算法(RAND)

image-20231102073942408

先进先出算法(FIFO)

image-20231102074107313

image-20231102074223542

近期最少使用算法(LRU)

image-20231102074504030

image-20231102074953162

image-20231102075030444

image-20231102075128628

image-20231102075259409

最不经常使用算法(LFU)

image-20231102075422000

image-20231102075553690

知识回顾

image-20231102075653893

Cache 写策略

image-20231102075807771

写命中

image-20231102075945817

image-20231102080120690

写不命中

image-20231102080213624

image-20231102080300525

image-20231102080431245

知识回顾

image-20231102080955881

页式存储器（操作系统详细）

image-20231102081524499

image-20231102081916378

image-20231102082009635

image-20231102085046750

image-20231102085349833

image-20231102085509570

image-20231102085820783

知识回顾

image-20231102090209026

虚拟存储器（操作系统详细）

叶式虚拟存储器

扩展页表

image-20231102090906164

image-20231102091106225

image-20231102091234505

段式虚拟存储器

image-20231102091450246

image-20231102091555141

段页式虚拟存储器

image-20231102091731468

指令系统

指令格式

指令格式

指令（又称机器指令）：是指示计算机执行某种操作的命令，是计算机运行的最小功能单位。

一台计算机的所有指令的集合构成该机的指令系统，也称为指令集。

注：一台计算机只能执行自已指令系统中的指令，不能执行其他系统的指令。

Eg: x86 架构、ARM 架构

一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。

image-20231102092656382

一条指令可能包含 0 个、1 个、2 个、3 个、4 个地址码…

根据地址码数目不同，可以将指令分为零地址指令、一地址指令、二地址指令…

零地址指令 OP

  1. 不需要操作数，如空操作、停机、唤中断等指令
  2. 堆栈计算机，两个操作数隐含存放在栈顶和次栈顶，计算结果压回栈顶（后缀表达式）
image-20231102093211763

一地址指令 OP A1

  1. 只需要单操作数，如加 1、减 1、取反、求补等
    指令含义：OP(A)→ A1 ，完成一条指令需要 3 次访存：取指 > 读 A1 > 写 A1

  2. 需要两个操作数，但其中一个操作数隐含在某个寄存器（如隐含在 ACC）
    指令含义： (ACC)OP(A1)→ ACC

image-20231102093408203

二地址指令 OP A1（目的操作数）A2（源操作数）

常用于需要两个操作数的算术运算、逻辑运算相关指令

指令含义：(A1)OP(A2)→ A1

完成一条指令需要访存 4 次，取指-> 读 A1-> 读 A2-> 写 A1

三地址指令 OP A1 A2 A3（结果）

常用于需要两个操作数的算术运算、逻辑运算相关指令

指令含义：(A1)OP(A2)→ A3

完成一条指令需要访存 4 次，取指→ > 读 A1 → > 读 A2 → > 写 A3

四地址指令 OP A1 A2 A3（结果） A4（下址）

指令含义：(A1)OP(A2)> A3，A4 = 下一条将要执行指令的地址

完成一条指令需要访存 4 次，取指→ > 读 A1 → > 读 A2 > 写 A3

正常情况下：取指令之后 PC+1，指向下一条指令

四地址指令：执行指令后，将 PC 的值修改位 A4 所指地

image-20231102094303239

image-20231102094320743

image-20231102094500876

image-20231102094552838

image-20231102094944058

本节回顾

image-20231102095022172

扩展操作码指令格式

image-20231102095121415

image-20231102095439075

image-20231102095617977

image-20231102100059744

image-20231102100215077

设地址长度为 n，上一层留出 m 种状态，下一层可扩展出 m × 2^n 种状态

image-20231102100606276

image-20231102100705180

指令寻址

指令寻址

image-20231102100919445

image-20231102101238480

image-20231102101322503

变长指令字结构寻址

image-20231102101937357

image-20231102102048571

本节回顾

image-20231102102205223

数据寻址

image-20231102102438549

image-20231102102549294

image-20231102102722577

image-20231102102813993

直接寻址

image-20231102103005099

间接寻址

image-20231102103322852

image-20231102103427880

寄存器寻址

寄存器寻址

寄存器间接寻址

寄存器间接寻址

隐含寻址

隐含寻址

立即寻址

image-20231102104038508

image-20231102104116613

本节回顾

image-20231102104150003

偏移寻址(剩下 3 种)

image-20231102104409318

基址寻址

image-20231102104703722

image-20231102104934915

image-20231102104946955

采用基址寻址无需修改指令中的地址码。

拓展：程序运行前，CPU 将 BR 的值修改为该程序的起始地址（存在操作系统 PCB 中）

注：基址寄存器是 面向操作系统 的，其 内容由噪作系统或管理程序确定。在程序执行过程中，基址寄存器的内容不变（作为基地址），形式地址可变（作为偏移量）。

当采用通用寄存器作为基址寄存器时，可由 用户决定哪个寄存器作为基址寄存器，但其 内容仍由操作系统确定。

优点：可扩大寻址范围（基址寄存器的位数大于形式地址 A 的位数）：用户不必考虑自已的程序存于主存的哪一空间区域，故 有利于多道程序设计，以及可用于 编制浮动程序（整个程序在内存里边的浮动）。

变址寻址

变址寻址

image-20231102105901303

变址寻址

在数组处理过程中，可设定 A 为数组的首地址，不断改变变址寄存器的内容，便可很容易形成数组中任一数据的地址，特别适合编制循环程序。

基址&变址复合寻址

基址&变址复合寻址

注：实际应用中往往需要多种寻址方式复合使用。

相对寻址

相对寻址

image-20231102111101472

image-20231102111122707

优点：这段代码在程序内浮动时不用更改跳转指令的地址码。

拓展：ACC 加法指令的地址码可采用“分段”方式解决，即程序段、数据段分开。

总结

image-20231102111450872

本节回顾

本节回顾

硬件如何实现数的“比较”

硬件如何实现数的 J“比较”

汇编语言中，条件跳转指令有很多种，如 je 2 表示当比较结果为 a = b 时跳转到 2；ig2 表示当比较结果为 a > b 时跳转到 2。

有的机器把 PSW 称为“标志寄存器”。

堆栈寻址

image-20231102112355386

堆栈寻址

image-20231102112658101

堆栈寻址

本节回顾

本节回顾

高级语言与机器级代码之间的对应

image-20231102113053422

image-20231102113448059

image-20231102113845428

image-20231102114105308

image-20231102114738801

image-20231102114908106

image-20231102114932265

image-20231102115704995

总结

image-20231102115832481

常用的 x86 汇编指令

常见的算数运算指令

image-20231102120607309

两个操作数不能同时来自主存

image-20231102120922421

image-20231102120953133

AT&T 格式 V.S.Intel 格式

image-20231102131930193

image-20231102132052334

选择语句机器级表示（if-else）

image-20231102132342046

image-20231102132657891

image-20231102132852712

image-20231102133016433

image-20231102133300329

image-20231102133410772

image-20231102133635460

image-20231102133855445

image-20231102134035283

循环语句机器级表示（for while）

image-20231102134244910 image-20231102134403433 image-20231102134614246

x86 默认指定了 ecx 做为循环计数器: arrow_up:

image-20231102134832664

函数调用机器级表示

cell 和 ret 指令

image-20231102135121434

image-20231102135644231

总结

image-20231102135732895

如何访问栈顿

函数调用栈在内存中的位置

image-20231102140124741

image-20231102140143154

image-20231102140304057

image-20231102140332974

我：出入栈要注意栈指针的加减

image-20231102140543524

总结

image-20231102141235348

如何切换栈顿

image-20231102141839478

image-20231102141857864

image-20231102141957444

image-20231102142108926

总结

image-20231102142151181

image-20231102142442440

如何传递参数和返回值

image-20231102142802115

image-20231102142912259

image-20231102142934208

image-20231102143135304

image-20231102143733304

拓展总结

image-20231102143836377

image-20231102143933769

image-20231102143959058

总结

image-20231102144110731

CISC 和 RISC（第五章详细）

image-20231102145027893

image-20231102145334912

中央处理器

本章总览

CPU 的功能和基本结构

CPU 的功能

运算器和控制器的功能

image-20231103132135534

运算器的基本结构

运算器的基本结构

运算器的基本结构

运算器的基本结构

运算器的基本结构

image-20231103133317110

CPU 的基本结构

本节回顾

本节回顾

指令周期的数据流

image-20231104035837242

指令周期

指令周期

image-20231104040517850

image-20231104040729277

image-20231104041021446

image-20231104041308606

image-20231104041326416

image-20231104041957365

image-20231104042745167

本节回顾

image-20231104042947878

数据通路

单总线结构

指令周期的数据流

image-20231104043953882

image-20231104044252614

image-20231104044820268

image-20231104045322232

image-20231104045551088

image-20231104045709835

本节回顾

专用通路结构

image-20231104050102405

image-20231104050226713

image-20231104050423372

image-20231104050616048

可以再加上（pc）+1。

image-20231104051026890

image-20231104051214106

image-20231104051449529

image-20231104051554110

控制器的设计

硬布线控制器的设计
image-20231104052115624

image-20231104052445509

image-20231104053039679

image-20231104053234685

image-20231104053411699

image-20231104053726580

image-20231104054137453

罗列出所有指令在各个阶段的微操作序列，就可以知道在什么情况下需要使用这个微操作。

image-20231104054611924

image-20231104054628584

image-20231104054700451

image-20231104054839393

image-20231104054857908

image-20231104054947594

image-20231104055211918

image-20231104055326551

image-20231104055439839

image-20231104055618806

image-20231104055838421

image-20231104060049086

微程序控制器（频率高点）
微程序控制器的基本原理

image-20231104060531516

image-20231104060626365

image-20231104061250871

image-20231104061614154

image-20231104061721683

考试常考: arrow_down:

image-20231104062110157

微指令的设计

image-20231104063127446

image-20231104063534441

image-20231104063648487

image-20231104063813136

image-20231104064029755

image-20231104064308499

image-20231104064730854

image-20231104064800964

image-20231104064914950

image-20231104072053161

image-20231104072318986

####### 知识回顾

知识回顾

微程序控制单元的设计

image-20231104072714759

image-20231104073008815

image-20231104073138475

也可以: arrow_down:

image-20231104073319689

image-20231104073559410

image-20231104073640787

image-20231104073818329

image-20231104074056889

软硬比较

image-20231104074356249

微程序控制器回顾

微程序控制器回顾

指令流水线

指令流水线的基本概念

image-20231104075215209

image-20231104075525227

image-20231104075732642

流水线的性能指标

image-20231104075951128

image-20231104080136649

image-20231104080333074

image-20231104080725715

指令流水线影响因素和分类

image-20231104082306131

image-20231104082831048

结构相关（资源冲突）

image-20231104084540886

数据相关（数据冲突）（多）

image-20231104090533705

3.编译优化：通过编译器调整指令顺序来解决数据相关。

控制相关(控制冲突）

image-20231104093917583

image-20231104094001748

分类

image-20231104095908923

流水线的多发技术

image-20231104100458300

通过编译优化技术，把可并行执行的指令搭配起来

image-20231104100823076

image-20231104101009902

本节回顾

本节回顾

五段式指令流水线（大题）

image-20231104101254731

image-20231104101448359

image-20231104101939609

image-20231104102438851

image-20231104102815387

image-20231104103048784

image-20231104103329682

image-20231104103719722

image-20231104104421565

多处理器基本概念（只考选择题）

image-20231104124828169

image-20231104125005918

image-20231104125150617

image-20231104130226380

image-20231104125833966

image-20231104130356199

image-20231104130844098

image-20231104130706625

image-20231104131016835

image-20231104131040511

硬件多线程的基本概念（只考选择题）

image-20231104131122258

image-20231104131254439 image-20231104131438577

总线

总线简图

image-20231110064245968

可并行发送 4bit 数据。同一时刻只能有一个部件发送数据，但是可有多个部件接受数据

本章总览

概念与分类

image-20231110064836940

为什么要用总线？早期计算机外部设备少时多采用分散接方式，不易实现随时增减外部设备。为了更好地解决/O 设备和主机之间连接的灵活性问题，计算机的结构从分散连接发展为总线连接。

总线的特性

image-20231110065530076

总线的分类

串行总线与并行总线

image-20231110073549160

系统总线

总线的分类（按总线功能）

系统总线的结构

注：单总线并不是指只有一根信号线，系统总线按传送信息的不同可以细分为地址总线、数据总线和控制总线。

优点：结构简单，成本低，易于接入新的设备。

缺点：带宽低、负载重，多个部件只能争用唯一的总线，且不支持并发（意：并行）传送操作，

系统总线的结构

系统总线的结构

优点：提高了 I/O 设备的性能，使其更快地响应命令，提高系统吞吐量。

缺点：系统工作效率较低。（why：3 个总线，同一时刻只能有一个总线工作）

四总线结构简介

本节回顾

本节回顾

image-20231110080910819

性能指标

  1. 总线的传输周期（总线周期）

  2. 总线时钟周期

  3. 总线的工作频率

  4. 总线的时钟频率

  5. 总线宽度

  6. 总线带宽

  7. 总线复用

  8. 信号线数

传输周期（总线周期）

总线周期

时钟周期

时钟周期

image-20231110081454075

关系：1 对多，1 对 1，多对 1。

为什么有一个总线时钟周期可包含多个总线周期：image-20231110081648464

现在的计算机中，总线时钟周期也有可能由桥接器提供。

工作频率

总线上各种操作的频率，为 总线周期的倒数。
若总线周期 = N 个时钟周期，则总线的工作频率 = 时钟频率/N。
实际上指 一秒内传送几次数据。

时钟频率

即机器的时钟频率，为 时钟周期的倒数。
若时钟周期为 T，则时钟频率为 1/T。
实际上指 一秒内有多少个时钟周期。

总线宽度

文称为总线位宽，它是 总线上同时能够传输的数据位数，通常是指数据总线的根数，如 32 根称为 32 位（bit）总线。

总线带宽

可理解为总线的 数据传输率，即 单位时间内总线上可传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位可用字节/秒（B/s）表示。

总线带宽=总线工作频率×总线宽度(bit/s)=总线工作频率×(总线宽度/8)(B/s)\text{总线带宽}=\text{总线工作频率}\times\text{总线宽度(bit/s)}=\text{总线工作频率}\times(\text{总线宽度/8)(B/s)}

=总线宽度总线周期(bit/s)=总线宽度/8总线周期(B/s)=\frac{\text{总线宽度}}{\text{总线周期}} \mathrm{(bit/s)=\frac{\text{总线宽度/8}}{\text{总线周期(B/s)}}}

注：总线带宽是指总线本身所能达到的最高传输速率

总线的性能指标-带宽

image-20231110083453883

总线复用

总线复用是指一种信号线在不同的时间传输不同的信息。可以使用较少的线传输更多的信息，从而节省了空间和成本。

信号线数

地址总线、数据总线和控制总线 3 种总线数的总和称为信号线数。

总线的性能指标总结

总线的性能指标

仲裁（408 不考）

总线仲裁的基本概念

集中仲裁方式

image-20231110084944720

链式查询方式

链式查询方式

计数器查询方式

image-20231110093308282

2 表示 BS 和 BR。

独立请求方式

集中仲裁小结

image-20231110094143987

分布仲裁方式

分布仲裁方式

总线操作和定时

总线传输的四个阶段

image-20231110095242140

image-20231110100230619

如果从设备跟不上节奏，在 T3 给不出数据，就哦豁了~

同步定时方式

image-20231110104533736

image-20231110104813883

image-20231110105019055

半同步通信

分离式通信

image-20231110105537822

本节回顾

image-20231110105641288

总线标准（408 不考，简单看了看）

总线标准的发展

为何串行总线取代并行总线

输入/输出系统（偏硬件，操作系统偏软件）

1/O 系统基本概念

1/O 控制方式简介

image-20231112062847816

image-20231112063202370

image-20231112063343750

DMA 控制器与主存每次传送 1 个字。当传送完一整块数据后才向 CPU 发出中断请求。

image-20231112063715921

image-20231112063940691 image-20231112064354426

在含有通道的计算机中，CPU 执行/O 指令对通道发出命令，由通道执行一系列通道指令，代替 CPU 对 I/O 设备进行管理。

注：I/O 指令与普通指令格式略有不同，操作码指明了 CPU 要对 10 接口做什么，命令码指明了 I/O 接口要对设备做什么

本节回顾

image-20231112064709408

外部设备（说是 408 不考）

image-20231112065009236

image-20231112071746246

I/O 接口

image-20231112071912352

image-20231112072242590

image-20231112072456316

image-20231112072518395

image-20231112073138019

如何确定要操作的设备？每个设备对应一组寄存器，操作不同的寄存器就是在操作不同的设备。

image-20231112073900000

image-20231112074215741

image-20231112074604033

image-20231112074803568

知识回顾

image-20231112074823922

程序查询方式

image-20231112075144477

image-20231112080206217

image-20231112080402662

image-20231112081613357

image-20231112081659787

程序中断方式（大题选择题，重要）

image-20231112090541703

image-20231112082126629

image-20231112083212498

image-20231112083413284

image-20231112083905407

image-20231112084325362

image-20231112084717930

image-20231112085119771

image-20231112085344779

image-20231112085923592

image-20231112090133348

image-20231112090630927

image-20231112090956082

image-20231112091253073

image-20231112091454980

image-20231112091758651

image-20231112092057805

image-20231112092120468

image-20231112092436494

image-20231112092504664

image-20231112093115954

image-20231112093355552

image-20231112094611999

image-20231112094643489

DMA 方式

image-20231112094755817

image-20231112095449888

image-20231112095858985

image-20231112100241471

image-20231112100550131

image-20231112102104440

image-20231112102352204

image-20231112102706186

image-20231112102832827

操作系统

操作系统的概诉

操作系统(Operating System)是配置在计算机硬件上的第一层软件。

特点：

  • 并发性：并发性是指两个或多个事件在同一时间间隔内发生；
  • 共享性：是指系统中的资源可供内存中多个并发执行的进程（线程）共同使用。
    • 互斥共享方式
    • 同时访问方式
  • 虚拟性：通过某种技术把一个物理实体变为若干个逻辑上的对应物。
    • 时分复用技术：虚拟处理机技术、虚拟设备技术
    • 空分复用技术（如 abcd 盘）：虚拟磁盘技术、虚拟存储器技术
  • 异步性

操作系统的功能：

  • 用户与硬件的接口

    • ·命令方式：用户通过输入有关命令来取得操作系统的服务，并控制用户程序的运行；

      举例：联机命令(交互式命令）和脱机命令(批处理命令）；

    • 系统调用方式：OS 提供了一组系统调用（函数），用户可在自己的应用程序中通过相应的系统调用，来实现与操作系统的通信，并取得它的服务；

    • 图形、窗口方式：已允许用户通过屏幕上的窗口和图标来实现与操作系统的通信并取得它的服务。

  • 资源管理者

    • 处理机管理：用于分配和控制处理机；
    • 存诸器管理：主要负责内存的分配与回收；
    • I/O 设备管理：负责 1/O 设备的分配与操纵；
    • 文件管理：负责文件的存取、共享和保护。

  • 扩充机器

    image-20231114110344394

发展与: star: 分类: star:：

  • 手工操作（无操作系统）

    缺点：

    • (1)用户独占全机；
    • (2) CPU 等待人工操作。

  • 批处理系统(操作系统开始出现)

    • (1)单道批处理系统(无并发)

      特点：自动性、顺序性、单道性；

      缺点：I/O 操作时，CPU 无事可做

    • (2)多道批处理系统（有并发）

      特点：多道性、宏观上多任务并行、微观上多任务分片串行；

      优点：由于提高了 CPU、内存和 I/O 设备的利用率，因此系统吞吐量得到提高。

    需要解决的问题：处理机管理问题、内存管理问题、I/O 设备管理问题、文件管理问题和作业管理问题。

    缺点：无交互能力。

  • 分时系统

    特点：多路性（类似于分身，每个用户感觉一台电脑）、独立性（多用户感觉独占）、及时性（如反馈及时）和交互性；

  • 实时系统

    特点：多路性、独立性、及时性、交互性和可靠性（如军工需要）。

  • 微机操作系统（了解）

    单用户单任务系统（dos 磁盘操作系统）、单用户多任务系统（windows）和多用户多任务系统（unix 及变种 linux）。

运行环境操作系统体系结构：

运行环境

  • 内核态与用户态
  • 中断、异常
  • 系统调用

操作系统体系结构

image-20231114111953951 image-20231114112055390

目态：又叫常态或用户态。机器处于自态时，程序只能执行非特权指令

管态：又叫特权态，系统态或核心态。CPU 在管态下可以执行指令系统的全集。通常，操作统在管态下运行。

image-20231114112242284 image-20231114112543679

image-20231114112713046

image-20231114112816643 image-20231114112933896

image-20231114113030039 trap 指令、跳转指令和压栈指令均可以在用户态执行，其中 trap 指令负责由用户态转换成为内核态。而关中断指令为特权指令，必须在核心态于能执行。

image-20231114113121784

外部中断处理过程，程序计数器的内容由中断隐指令自动保存，通用寄存器的内容由操作系统保存。

image-20231114113202254 image-20231114113243076

硬件和软件资源：归纳起来可将资源分为 4 类：处理器、存储器、VO 设备以及信息（数据和程序）

image-20231114113321898

银行家算法，死锁避免。

image-20231114113546843 image-20231114113604014 image-20231114113645341 image-20231114113820945 image-20231114113912798 image-20231114113957602 image-20231114114122276

缺点：这种结构操作系统效率不高，因为所有户程都要通过微内核占通信，所以微内核本身就成了系统的“瓶颈，尤其是通信频紧的系统

image-20231114114403900 image-20231114114558304 image-20231114114832627 image-20231114114903975 image-20231114115106599 image-20231114115154953 image-20231114115243390 image-20231114115501181 image-20231114115543645 image-20231114115609584 image-20231114115709110

进程管理

进程引入

程序的执行特征：

  • 顺序性：处理机的操作产严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始；
  • 封闭性：程序是在封闭的环境下执行的，即程序运行时独占全机资源，资源的状态只有本程序能改变它；
  • 可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。

程序并发执行时的特征：

  • 间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系相互制约将导致并发程序具有“执行一暂停一执行”这种间断性的活动规律；
  • 失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性；
  • 不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。

为使程序能并发执行，且为了对并发执行的程序加以描述和控制，引入了“进程”的概念。

PCB(Process Control Block，进程控制块) image-20231116045838778

进程描述信息：

  • 进程标识符（唯一的，用整数表示）
  • 进程名（基于可执行文件名，用学符串表示，不唯一）
  • 用户标识符（哪个用户创建的）
  • 进程组关系

进程控制信息：

  • 当前状态
  • 优先级
  • 代码执行入口地址
  • 程序磁盘地址
  • 运行统计信息（执行时间、页面调度）
  • 进程间同步和通讯信息
  • 进程的队列指针
  • 进程的消息队列指针

所拥有的资源和使用情况：

  • 虚拟地址空间状况
  • 打开文件列表

CPU 现场信息：

  • 寄存器值（通用寄存器、PC、PSW、栈指针）
  • 指向该进程页表的指针

进程的特征：

  • 结构特征 进程实体
  • 动态性：进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。动态性还表现在：“它由创建而产生，由调度而执行，由撤消而消亡”
  • 并发性：多个进程实体同存于内存中，且能在一段时间内同时运行；
  • 独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位；
  • 异步性：是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。

进程的定义

曾有许多人从不同的角度对进程下过定义，其中较典型的进程定义有：

1）进程是程序的一次执行

2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

在引入了进程实体的概念后的进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

image-20231116050856862 image-20231116051003573

进程控制

进程的状态及转换：

  • 就绪：进程已分配到除 CPU 以外的所有必要资源后只要再获得 CPU 便可立即执行
  • 执行：进程已获得 CPU，其程序正在执行
  • 阻塞：正在执行的进程由于发生某事件而暂时无法续执行时，便放弃处理机而处于暂停状态，又叫等待、睡眠或者封锁状态
image-20231116051543241
  • 创建（为了考试）
  • 终止
image-20231116051648099

引入挂起状态（就绪状态、阻塞状态可能站着茅坑不拉屎）

image-20231116052555995

进程的创建：

  1. 申请空白 PCB；
  2. 为新进程分配资源；
  3. 初始化进程控制块：（初始化：标识信息、处理机状态信息、处理机控制信息）
  4. 将新进程插入就绪队列。

进程的终止：

1）根据被终止进程的标识符，从 PCB 集合中找出该进程的 PCB，从中取出该进程的状态；

2）若将被终止的进程正处于执行状态，则终止该进程的执行，并将处理机资源分配给其他进程；

3）若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的进程；

4）将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统；

5）将被终止进程的 PCB 从所在队列或链表）中移出。

进程的阻塞与唤醒：

  • 进程的阻塞：
    1. 先用进程标识符找到要被阻塞的进程；
    2. 若该进程处于运行状态，先立即停止执行，将其状态转为阻塞态；
    3. 将本进程插入到阻塞队列，如果系统中设置了因不同事件而阻塞的多个阻塞队列、则插入具有相同事件的阻塞（等待）队列；
    4. 转调度程序进行重新调度，将处理机分配给另一就绪进程
  • 进程的唤醒：
    1. 把被阻塞的进程从等待该事件的阻塞队列中移出；
    2. 将其 PCB 中的现行状态由阻塞改为就绪；
    3. 然后再将该 PCB 插入到就绪队列中。

注意：阻塞原语和唤醒原语是一对作用刚好相反的原语，必须成对出现，也就是如果在某进程中调用了阻塞原语，则必须在与之相合作的另一进程中或其他相关的进程中安排唤醒原语、方能唤醒阻塞进程；否则、被阻塞进程将会因不能被唤醒而长久地处于阻塞状态，从而再无机会继续运行。

引起各状态的事件和原语：

原语：创建原语、终止原语、阻塞原语和唤醒原语。

引起进程创建的事件有：用户登录（例：分时系统）、作业调度（例：批处理系统）、提供服务（例：要使用摄像头）和应用请求。

引起进程终正的事件可以分为三类，第一：进程正常结束；第二：进程异常结束；第三：外界干预。

其中异常结束的情况有：越界错误(例：地址空间)，保护错（例：写只读），非法指令（例：不存在指令，跳转错误，将数据当在指令），特权指令错（例：权限不够），运行超时，等待超时，算术运算错，I/O 故障等。

进程切换（上下文切换 context switch）：

1）保存被中断进程的处理机上下文信息；

2）更新被中断进程的 PCB 信息，如进程状态；

3）把被中断进程的 PCB 加入相关队列；

4）选择一个新进程并更新其 PCB 信息，如进程状态；

5）更新被选中进程的存储管理信息；

6）恢复被选中进程的处理机上下文信息。

image-20231116054644662 image-20231116054716350 image-20231116054800850

线程

进程存在的问题：

1）系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，如内存空间、I/O 设备，以及建立相应的 PCB，开销大；

2）系统在撤消进程时，又必须先回收其所占有的资源，然后再撤消 PCB，开销大；

3）对进程进行切换时，由于要保留当前进程的 CPU 环境和恢复新选中进程的 CPU 环境，因而须花费不少的处理机时间；

4）不同进程之间，资源独立分配，不共享地址空间，不便于协作。

线程的属性：

  • 轻型实体：基本上不拥有资源，只是有一点能保证其独立运行的资源，如 TCB（线程控制块），程序计数器，局部变量、寄存器和堆栈等。
  • 独立调度和分派的基本单位。
  • 可并发执行。
  • 共享进程资源：所有线程都共享地址空间（所属进程的地址空间）和所属进程已打开的文件等。

内核态和用户态 Kernel Mode and User Mode：

内核是一个软件程序，用来访问硬件的软件程序

内核态和用户态的切换：当一个进程陷入内核代码中执行时，我们就称进程处于内核态。进入内核态的方式主要有三种：系统调用、异常和外围设备的中断。

线程的实现：

image-20231116060230844

  • 用户级线程

    通过运行时系统来管理线程，运行时系统实际上是一套库函数，存在十用户空间内内核管理的还是进程，感觉不到线程的存在：线程切换不需要内核管理。

    优点：线程切换速度快，调度算法可根据应用程序需要而定制，可运行在任何操作系统上。

    缺点：内核只能将 CPU 以进程为单位分配，同一进程中的两个线程就无法分配到不同的 CPU。进程被阻塞，则进程内的所有线程都会被阻塞。

  • 内核支持线程

    内核管理所有线程，并向用户提供 AP 接口来创建线程；

    内核即维护进程相关数据结构还维护线程相关数据结构；

    线程切换由内核来支持；

    调度以线程为单位。

    优点：

    1）在多处理器系统中，内核能够同时调度同一进程中多个线程并行执行：

    2）进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行也可以运行其它进程中的线程；

    3）内核本身也可以采用多线程技术，可以提高系统的执行速度和效率

    缺点：

    对于用户的线程切换而言，其模式切换的开销较大，在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到内核态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的，系统开销较大。

多线程模型：

  • 多对一模型：多个用户线程映射到了一个内核线程上边，多对一模型就是用户级线程实现方式。

  • 一对一模型：一个用户线程映射到一个内核线程上，这其实就是之前讲过的内核支持线程。

  • 多对多模型

线程和进程的比较：

  • 调度：

    进程是拥有资源的基本单位和独立调度分派的基本单位。

    线程是独立调度分派的基本单位，几乎不拥有资源。

  • 并发性：

    在引入了线程的操作系统中，不仅进程之间可以并发，同进程中的线程之间也可以并发，可以说有了线程，操作系统的并发性得以提高。

  • 拥有资源：

    进程拥有资源，而线程几乎不拥有资源，只拥有一些保证运行的必不可少的资源。

  • 系统开销：

    在创建或撤消进程时，系统都要为之创建和回收进程控制块，分配或回收资源开销比线程大；

    进程切换时，涉及到 CPU 环境的保存与恢复和存储器管理方面的操作，而线程的切换则仅需保存和设置少量寄存器内容，所以线程切换代低得多。

image-20231116061125207 image-20231116061313084 image-20231116061437871

赋值操作可看作原子操作。

image-20231116061633428

处理机调度

  • 先来先服务调度算法 image-20231116062040401

    作业与进程的区别：

    1）作业是用户向计算机提交的任务实体。而进程则是完成用户任务的执行实体。任一进程，只要它被创建，总有相应的部分存在于内存中。

    2）根据一个作业可创建一个或多个进程来完成。

    3）作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道程序系统中。

    作业调度（ 高级调度 ）：根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。

    FIFO 用于作业调度： 每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列；

    FIFO 用于进程调度（低级调度）： 每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。

    低级调度 决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。

    中级调度 使那些暂时不能运行的进程不再占用内存资源，而将它们调至外存上去等待，把此时的进程状态称为挂起状态。当这些进程重又具备运行条件时，则将其重新调入内存，并修改其状态，挂在相应的队列上等待进程调度。

    image-20231116095729428 image-20231116095748044 image-20231116095824658 image-20231116100031624

    高级调度（作业调度）：外存→内存 频率最低

    1. 决定接纳多少个作业。取决于多道程序度：允许多少个作业同时在内存中运行。
    2. 决定接纳哪些作业。这将取决于所采用的调度算法

    低级调度（进程调度）：内存→ CPU，可见前进程切换 频率最高

    1. 保存处理机的现场信息；
    2. 按某种算法选取进程；
    3. 把处理器分配给进程。

    调度方式：1)非抢占方式（不能抢）2)抢占方式

    中级调度(中程调度)：内存: left_right_arrow: 外存 频率中等

    image-20231116101111288

    FCFS 算法比较有利于长作业（进程），而不利于短作业（进程）

    带权周转时间 =（完成时间一到达时间）/服务时间

    image-20231116101743423

  • 短作业（短进程、短线程)优先调度算法

    用于作业调度：从后备队列中选择一个或若千个估计运行时间最短的作业，将它们门调入内存运行。

    用于进程调度：从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给执行。

    1. 该算法对长作业不利；
    2. 该算法不能保证紧迫性作业进程）会被及时处理；
    3. 估计运行导致该算法不一定能真正做到短作业优先调度。

  • 优先级调度算法

    调度方式：

    • 非抢占式优先权算法
    • 抢占式优先权调度算法

    优先权的类型：

    • 静态优先权
    • 动态优先权

  • 高响应比优先调度算法： 属于动态优先权，不可抢占的优先级调度算法。

    RP=等待时间+服务时间服务时间\mathbf{R}_{\mathbf{P}}=\frac{\text{等待时间}+\text{服务时间}}{ \text{服务时间}}

    照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务，是一种短作业优先和先来先服务算法的较好的折裹。

  • 时间片的轮转调度算法：

    时间片轮转法：image-20231116103323750 image-20231116103413794 image-20231116103500249 image-20231116103559358

    时间片的选取：

    • 时间片过长则变成了先来先服务算法：
    • 时间片过短则会产生过多的上下文切换，系统内耗重

    一般根据经验：时间片选取的长度不应使得上下文切换开销超过 1%。

    还可以这样取：时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。

    多级反馈队列算法：image-20231116103942433 image-20231116104018764

    image-20231116104157034 image-20231116104334754

    多级反馈队列调度算法的特点：

    CPU 密集（不是 cpu 密集，而是占用时间多）型进程：进程优先级会下降很快，得到较大的时间片，减少进程切换的开销；

    I/O 密集型进程：进程会停留在高优先级队列中，因为每次需要 CPU 执行的时间很短。

    调度算法准则：

    • 面向用户的准则：

      1. 周转时间短

        周转时间 Ti，是指从作业被提交给系统开始，到作业完成为止的这没时间间隔（称为作业周转时间）

        平均周转时间 T =(T1+T2+…Tn)/n

        带权平均周转时间Tw=(T1TS1+T1TS1+……+TnTSn)/n.其中TSi为服务时间\begin{aligned}&\text{带权平均周转时间}T_{\mathbf{w}}=(\frac{T_{1}}{TS_{1}}+\frac{T_{1}}{TS_{1}}+\ldots\ldots+\frac{T_{n}}{TS_{n}})/n.\\&\text{其中}TS_i\text{为服务时间}\end{aligned}

      2. 响应速度快

        响应时间 = 等待时间+（第一次）服务务时间 （在批处理系统的情况下，响应时间等于周转时间）

        image-20231116105924900 image-20231116110513977

        通常用响应时间的长短评价分时系统的性能，是选择分时系统中进程调度算法的重要准则之一。

      3. 截止时间的保证

        截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。

        截止时间是评价实时系统性能的重要指标，是选择实时调度算法的重要准则。

    • 面向系统的准则

      1. 系统吞吐量高；
      2. 处理机利用率好；
      3. 各类资源的平衡利用。
image-20231116111035908 image-20231116111237852

AD 有饥饿现象，C 没有短任务优先。

image-20231116111613089

A 有助于用户的交互，涉及大量 I/O 操作；C 追求周转时间最短，不利于 CPU 繁忙型的，有利于 I/O 繁忙型；D 根据调整优先级的规则，两者皆可有利于。

image-20231116112354267

A 周转时间说法。

image-20231116112543802

A 抢占破坏规则，BC 是作业调度算法。

image-20231116112739511 image-20231116112844297 image-20231116112944981 image-20231116113031899 image-20231116113124489 image-20231116113222214 image-20231116113255548

进程同步与互斥（重头戏）

竞争条件(Race Condition)：由于两个或者多个进程竞争使用不能被同时访问的资源，使得这些进程有可能因为时间上推进的先后原因而出现问题，这叫做竞争条件。

image-20231116115241036

P、V 操作为原语操作；

在信号量上只有三种操作，初始化（值非负）、P 操作、V 操作；

初值设为 1，可解决互斥问题；初值设为大于 1 的值可解决同步问题

多道程序系统中一次仅允许一个进程使用的资源称为 临界资源 ；

在每个进程中访问临界资源的那段代码称为 临界区 ；

实现临界区的互斥访问只需定义一个初值为 1 的信号量，一般命名为 mutex，在临界区前后，分别执行 P（mutex）和 V(mutex）操作即可；

临界区的范围应该尽可能小。

生产者消费者问题：

一群生产者和一群消费者共享一个初始为空、空间大小为 n 的仓库。生产者生产产品，只有仓库没满时，生产者才能把产品放入到仓库，一次一个产品（每个产品占一个空间），否则必须等待；同时，消费者消耗产品，只有缓冲区不空时，消费者才能从中取出产品，一次一个产品，否则必须等待。

image-20231118110102979 image-20231118111100932

读者写者问题：

多个读、写进程共享一片数据存储区，读、写进程的操作如下：

  • 读者进程只从存储区内读数据；
  • 写者进程只往存储区内写数据。

要求：·

  • 多个读者同时可读；
  • 不允许多个写者同时写；
  • 不允许读者、写者同时操作；
  • 若有读者正在读，且有写者正在等待，则允许其他读者读。( 读者优先 )
image-20231118111100932
  • 若有读者正在读，且有写者正在等待，则允许其他读者读。
  • 如果一个读者申请进行读操作时已有另一写者在等待写，则该读者必须等到没有写者处于等待状态后才能开始读操作。（ 写则优先 ）
image-20231118113018699

哲学家进餐问题：

image-20231118113747324 image-20231118113905402

实现临界区互斥的基本方法：

  • 软件解决办法

    image-20231118114544712

​ 轮换法 ：只有一个进程运行时，只能运行一次。

​ 轮换法可以实现互访问，但无法保证临界区空闲的时候一定能进入。

​ 实现临界区互斥的设计原则：

  • 互斥访问 ：如果有一个进程处在临界区中，则其余进程不能进入。互访间保证协作进程的正确运行；

  • 空闲让进 ：多个进程等待进入临界区时，只要临界区为空，应尽快使某一进程进入。有空让进保证进程协作高效运行；

  • 有限等待 ：从进程发出进入请求到充允许进入，不能无限等待

    image-20231118115429684

    会出现无法进入和无限等待的情况。（why：任何一个进程都可以留下标记）

    标记法 ：不满足有空让进也不满足有限等待！

    image-20231118115829310

    Peterson 算法 ：满足互进入；

    如果没有进程试图进入临界区，则 flag 数组中必全为则 while 循环条件为假，可进入，因此满足空闲让进；

    turn 要么为 0、要么为 1，因此不可能两个 while 同时循环，因此满足有限等待。

  • 硬件解决办法

    image-20231118120516335 image-20231118120541135

    中断屏蔽法:

    特点:

    • 实现简单，执行效率高；
    • 代价高，限制 CPU 并发能力；
    • 不适用于多处理器系统;
    • 适用于操作系统本身的进程，不适于用户进程。
    image-20231118120902476

    原子指令法：

管程：

管程：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程由四部分组成：

  • 管程的名称；
  • 局部于管程内部的共享数据结构说明对该数据结构的一组操作；
  • 对局部于管程内部的共享数据设置初始值的语句。

管程的特性：

  • 模块化；
  • 抽象数据类型。管程中不仅有数据，而且有对数据的操作；
  • 信息掩蔽。

管程实现互斥的原理：
局部于管程内部的数据结构，仅能被局部于管程内部的操作所访问局高部于管程内部的操作也仅能访问管程内的数据结构；且管程一次仅允许一个进程进入调用其操作，因此实现了对管程内的临界资源的互斥访问。

管程实现同步的原理：
管程中设置条件变量，用以解决同步问题。

条件变量：条件变量是一个队列以及附加在这个队列上的两个操作：等待（wait）和唤醒（signal)

例如：进程执行需要某种条件，即可定义一个代表这种条件的条件变量 X，当进程缺少这种条件而无法执行的时候，就调用 X.wait 将该进程阻塞在 X 中的队列上。当另一个进程的执行导致条件出现的时候，就调用 X.signal（），将阻塞在 X 中队列上的进程唤醒一个。

用管程实现消费者和生产者问题：
image-20231118123306335

image-20231118123600140

初值为 3：资源有 3 个；当前值为 1：有 2 个资源已经被分配了，还剩 1 个资源可用。所以没有进程等待。

image-20231118123843667 image-20231118124452329

将 i 为 0、1 的代码写出。 答案为 B

image-20231118124359474 style = "zoom: 50%;"

饥饿：由于别的并发的进程持久占有某资源，使某个异步进程长时间不能得到该资源而无法执行的现象。

死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的种阻塞的现象，若无外力作用，它们都将无法推进下去。

image-20231118124944717 style = "zoom: 50%;"

image-20231118125149975 image-20231118125434339 image-20231118125509418 image-20231118125644778 image-20231118125717039 image-20231118125744183

正信号量表示资源个数，负信号量绝对值表示等带进程的个数。

image-20231118125953590 style = "zoom: 50%;"

image-20231118130053452 style = "zoom: 50%;"

image-20231118130128644 style = "zoom: 50%;"

image-20231118130543828 style = "zoom: 50%;"

Peterson 算法

image-20231118130723027 style = "zoom: 50%;"

死锁：

image-20231118131118504 image-20231118131257933 style="zoom:50%;"

死锁：多个进程因互相等待对方所持有的资源而造成的谁也无法继续执行的状态叫死锁。

死锁的成因：

  • 资源是互使用的，一担占有别人无法使用；
  • 进程占有了部分资源不释放，再去申请其他已被占有的资源；
  • 各自占有的资源和相互申请的资源形成了环路等待。

死锁的必要条件：

  • 资源互斥使用；
  • 资源不可抢占；
  • 保持资源并请求新资源；
  • 环路等待。

死锁处理：

  • 死锁预防：用对进程的资源申请添加约束条件的方法来确保至少一个死锁必要条件不会出现进而防止死锁的出现。

    死锁预防是一种静态策略，是从事情开始之前就确保不会发生死锁的方法。

    • 在执行前，一次性申请进程所需的所有资源，申请不到就不执行，这样就不会出现占有并申请的情况。

      缺点：需要预估进程所需资源量，编程难度高；许多资源分配后长时间得不到利用，资源利用率低。（类比顺序表和链表）

    • 对资源类型排序，申请按序进行，避免出现环路等待。

      缺点：资源利用率低。

  • 死锁避免：

    如果系统中的所有进程都存在一个可完成的执行序列 P1P2…Pn，则称系统处于安全状态。

    image-20231118132649747

    银行家算法:

    image-20231118133001626

    用银行家算法进行死锁避免、假设 Po 准备申请资源，系统先假装把资源分配给 Po 然后以此为初值执行银行家算法，若能成功找出可完成的执行序列，则证明可把资源分配给 Po，否则不分配。

    采用银行家算法进行死锁避免，效率较低。（m*n 的复杂度，n 是进程数，m 是资源种类）

  • 死锁预防和死锁避免的区别

    死锁预防是一种静态策略，是从事情开始之前就确保不会发生死锁的方法。

    死锁避免便一种动态策略，是随着一系列进程的执行，边边看会不会发生死锁，会则停止分配资源。

  • 死锁检测并恢复：

    • 死锁检测：系统允许死锁发生，但是会不断进行监视，判断死锁是否真的发生。

      • 检测时机：

        • 当进程由于资源不足而进入等待状态的时候进行检测（效率低）；
        • 定时监测;
        • 系统资源利用率下降的时候进行监测。

      • 检测算法：

        • 给每个进程和资源分配唯一编号；
        • 设置一张资源点有表，记录各进程与其已占用资源之间的关系；
        • 设置一张资源等待表，记录各进程与要申请资源之间的关系。image-20231118133920124

    • 死锁解除：

      • 撤销所有发生死锁的进程；
      • 进程回滚(RollBack)；
      • 按某种原则逐一撤销进程，直到死锁解除；
      • 按桌种原则逐一剥夺进程资源，直到死锁解除；

  • 死锁不管(忽略)（例如重启）

image-20231118134243736 image-20231118134509230 image-20231118134616368 image-20231118134729600 image-20231118134908593

先排除 A（1 个怎么死锁），再排除 D（可以），再尝试 CB。

image-20231118135129012

image-20231118135254790

C 选项会出现只有一个车能动的情况。

image-20231118135349380 image-20231118135515182 image-20231118135555124 image-20231118135605268 image-20231118135727348 image-20231118135836667 style="zoom:50%;"

抖动：通常是因为内存或其他资源耗尽或有限而无法完成所要执行的操作。

image-20231118135927912 style="zoom:50%;"

image-20231118140022546 style = "zoom: 50%;"

进程通讯：

通过操作信号量进行的进程通信：信号量或者管程只能在进程之间传递少量且简单的数据，大量复杂数据无法传递，因此引入了新的进程通信机制。

通信方式：

  • 共享内存

    1. 1 在内存中找一片空间，专门为两个进程共享，也就是两个进程都可以操作的一片存诸空间。实现方法就是让同一块物理内存空间映射到给两个进程的地址空间中去；
    2. 共享内存区域需要解决互斥问题，解决方法和读者写者问题是一样的，因为共享内存中不能多个进程同时进行写操作，但是可以同时进行读操作。

  • 管道通信：利用一个缓冲传输介质来连接两个相互通信的进程。image-20231118140730418

    1. 以字节流的方式写入/读出数据：
    2. FIFO 先进先出的数据传输方式）；
    3. 管道提供简单的协调能力，只需要判断双方进程是否存在和判断管道内是否有数据。因读和写在不同的位置进行，所以无需复杂的互斥管理。

  • 消息传递：两个原语(primitive)：send、receive

    • send (P1, message); 直接方式

      receive (P2, message);

    • send (mailBox, message); 间接方式

      receive (mailBox, message);

内存管理

连续分配：

  • 静态分区分配

    • 单一连续分配（分配对象为程序）（一次只有一个进程在内存运行）：只能用于单用户、单任务的操作系统中。

      image-20231123055656128

    • 固定分区分配

      image-20231123055803207

      • 分区大小相等：缺点：若进程太小则空间浪费大，若进程大，超过一个分区大小，则无法装入。

        image-20231123060013610

      • 分区大小不等：

        image-20231123060221598

  • 动态分区分配

    image-20231123060512754

    内部碎片：就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；

    外部碎片：指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

    image-20231123060758958

    • 首次适应算法

      • 空闲分区列表按照地址递增顺序排序；
      • 分配时，搜索第一个合适的分区；
      • 回收时，检查是否可以于临近分区合并。

      优点：简单，在高地址区域有大块空闲空间，便于后来的大空间进程用。

      缺点：会产生大量外部碎片，分配大块空间速度较慢

      image-20231123061038390

    • 最佳适应算法

      • 空闲分区列表按分区块大小排序（从小到大）；
      • 分配时，按序扫描分区表，找第一个比进程空间大的分配之；
      • 回收时，查找并合并地址临近的空闲分区，合并后需进一步处理使之保持按分区大小有序；

      优点：可减少大空闲分区被拆分的可能，缩小外部碎片的大小。

      缺点：外部碎片多且小，回收速度慢。

    • 最坏适应算法

      • 空闲分区列表按分区块大小排序（从大到小）；
      • 分配时，按序扫描分区表，找第一个比进程空间大的分配之；
      • 回收时，查找并合并地址临近的空闲分区，合并后需进一步处理使之保持按分区大小有序。

      优点：可减少小碎片出现的概率；

      缺点：会产生外部碎片，会破坏大空闲分区（对后续大空间要求进程不利），回收速度慢。

  • 伙伴系统：伙伴系统方式是对以上两种内存方式的一种折衷方案

    image-20231123063127728

    • 空间分配：

      • 整个可分配的分区大小为 2U。
      • 对于到来的进程请求空间 S，可将分区进行次划分，得到空间大小为 2U-i的分区。
      • 当满足 2U-i-1< S ≤ 2U-i的时候，则把大小为 2U-i的分区分配给进程。

    • 空间回收：合并条件：大小相同，地址相邻；即由同一块分割而来。

      image-20231123063522028
image-20231123063608242 image-20231123063755075 image-20231123063933073 image-20231123064231299

非连续分配：

image-20231123064544670 image-20231123064616489

如果可以将进程分散地装入到许多不相邻接的分区中，则即可利用分散的存储区，又无须进行“紧凑”。

  • 页式存储管理

    image-20231123070236111

    内存分配规则 ：以页为单位进行分配，逻辑上相邻的页，物理上不一定相邻。

    逻辑地址：又叫虚地址 ，如用户程序遍后形成的自标代码：其首地址为 0、其余地址都是相对于首地址编址，不可直接寻址；

    物理地址：又叫实地址 ，内存中存储单元的地址，可直接寻址。

    image-20231123070637867

    页面划分是系统自动完成的，大小由系统决定，对用户透明。

    image-20231123070804533

    页表记录了页号和页框号的对应关系；

    页表是进程的一部分，每个进程都有一个，存放在内存中；

    进程正在执行，则页表起始地址保存在页表基址寄存器；若进程没有在执行，则页表起始地址保存在 PCB 中。

    image-20231123071214906

  • 段式存储管理

    • 设计思想

      进程地址空间按某种逻辑关系划分为若干个段，每个段都有自己的名字。比如主程序段 main、子程序段 ADD、数据段 D。

    • 内存分配

      以段为单位分配，每段一片连续的内存空间，段之间可以不连续。

    image-20231123072222750 image-20231123072437167

  • 段式、页式对比 image-20231123072544275

    可重入代码：是一种允许多个进程同时访问的代码。为了使各进程所执行的代码完全相同，故不允许任何进程对其进行修改。

    image-20231123073624771 image-20231123073653979

    • 页是物理单位，分页目的是实现离散分配，减少外部碎片，提高内存的利用率。分页仅仅是由于系统管理的需要而不是用户的需要。

      段是信息的逻辑单位，每段都有一组其意义相对完整的信息。分段的目的是为更好地满足用户的需要；

    • 页大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，由硬件实现，在系统中只有一种大小的页面；

      段长不固定，取决于用户编写的程序，通常由编译程序在对源程序进行编译时，由信息的性质划分；

    • 分页的地址空间对程序员是一维的；

      分段地址空间对程序员是二维的, 程序员在标识一个地址时，既需给出段名，又需给出段内地址。

  • 段页式存诸管理

    • 为什么设计段页式：为了综合段式和页式的优点，克服两者缺点。

    • 设计思想

      image-20231123074515830 image-20231123074751409
image-20231123075157061 image-20231123075513778 image-20231123075729614 image-20231123075821985

代价最小：维持这种管理系统正常运行的额外开销最小。D 最复杂；BC 差不多，一个要页表，一个要段表。

image-20231123080107640 image-20231123080227810 image-20231123080347710 image-20231123080431570

虚拟内存管理：

  • 覆盖技术

    • 功能：可在较小的内存内运行空间需求较大的进程。
    • 实现方法：让不会同时执行的程序模块共享一片存储区
    • 提示：不存在调用关系的模块不会同时执行，可共享一片存储区。
    image-20231123081322681

    优点：小空间运行大进程。

    缺点：增加了编程困难，增加了执行时间。

  • 交换(对换)技术

    • 功能：可增加正在执行或需要执行的进程的内存。
    • 实现方法：将暂不执行的进程换出内存，将满足执行条件的进程换入内存。
    • 提示：换入换出的单位是整个进程。
    • 交换的时机：正在执行的进程发现内存不足，则需要把其他未在执行的进程换出；或看将要进入内存执行的进程发现内存不足则换出内存中未在执行的进程。
    • 进程的换出与换入：
      • 换出（swapin）。当某进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间时，则系统将某进程换出。一般选择处于阻塞状态且优先级最低的进程换出。
      • 换入（swapin）。系统定时地查看所有进程的状态，从中找出就绪”状态且已换出的进程，将其中换出时间最久的进程换入。

  • 覆盖与交换(对换)的比较

    • 覆盖

      发生在同一个进程内的不同时执行的模块间；

      解决一个进程的空间需求无法满足的问题；

      程序员须给出模块间的逻辑覆盖结构。

    • 交换

      以进程为单位；

      解决多个进程的空间需求无法满足的问题；

      不需要模块的逻辑覆盖结构。

  • 局部性原理

    • 时间局部性：一条指令的一次执行和下一次执行，一个数据的一次访问和下一次访问都集中在一个较短的时期内。
    • 空间局部性：当前执行的指令和临近的几条指令，当前访问的数据和临近的儿个数据都集中在一个较小的区域内。
    • 分支局部性：一条跳转指令的两次执行，很可能跳到相同的位置。

虚拟存储技术：

  • 原理：

    • 装载程序的时候，仅将当前需要执行的页面或者段装入内存；
    • 执行过程中所需要的程序或数据不在内存，则将相应的页或者段调入内存；
    • 将暂时不用的页或者段保存到外存中。

  • 实现方式：虚拟页式存储方式和虚拟段式存储方式

  • 虚拟页式存储方式（大纲）

    image-20231123083016058 image-20231123083222785 image-20231123083304065

    • 缺页中断机构

      每当所要访问的页面不在内存时，便产生缺页中断，请求系统将所缺之页调入内存。

      缺页中断的特点：

      • 在指令执行期间产生和处理中断信号，而非通常的在指令执行完之后检测处理中断。
      • 一条指令在执行期间，可能产生多次缺页中断

    • 页面置换算法

      • 最佳(Optimal)置换算法

        选择换出的页面：将是以后永不使用的或在最长（未来）时间内不再被访问的页面。因无法预知哪个页面永远不再使用或者最长时间不再被访问，所以这是一种理想算法。

      • 先进先出(FIFO)置换算法(理解：滞留时间最长) FIFO 算法基于队列类的算法

        总是将最先进入内存的页面换出，或者说选择在内存中驻留时间最久的页面换出。

      • 最近最久未使用(LRU)置换算法 LRU 是堆栈类的算法

        选择最近最久未使用的页面换出，是一种用“最近的过去”作为“最近的将来”的估计的方法。

        image-20231123084041956

        具体方法：用访问字段来记录一个页面自上次被访问以来所经历的时间 t，当要换出一个页面时、选择现有页面中其值最大的，即最近最久未使用的页面换出

      image-20231123084340768 image-20231123084432020

      image-20231123084604694 image-20231123084655578

      image-20231123084831304 image-20231123084859975

      image-20231123084946436

      • Clock 置换算法

        访问页面时，在页表项中记录下访问情况；缺页时，从上次查找结束的位置顺序查找未被访问的页面换出。

        image-20231123085431915

        具体方法：页表中增加访问位、用来描述过去一段时间的访问情况、各个页面组织成循环链表，用一个指针指向最先调入的页面。指针扫描循环链表，找到第一个未被访问的页面换出。

        image-20231123085642648

        p 代表访问对应的页面，访问后把访问位置 0，指针后移，发现 1 置 0，发现 0 则换出并更新页表中的页表项，把新换入的置 1。

        算法改进：两个访问位为 0 的页面，应该优先选择未被修改的，因为不需要写回外存，减少开销。

        image-20231123090623497

        从当前位置开始扫描第一个（0，0）的页作为替换的页；

        如果上一轮扫描不存在（0，0）的页，则选择（0，1）的作为替换的页，并将所有扫描过的页面访问位设置为 0。

        如果上一轮扫描失败，则重新扫描，选择第一个（0，0）的页作为替换页；

        如果上一轮扫描失败，则重新扫描，选择第一个（0，1）的页作为替换页。

页面分配策略：

  • 固定分配局部置换

    为每个进程分配固定数自的页框（物理块），假设个，如果发生缺贝，则只能从这厂个中选出一个换出。

    这种方法难以确定 n 的大小。n 太小，则缺页频繁，系统吞吐量低；n 太大，则内存中能够驻留的进程数量少，系统井行率低。

  • 可变分配全局置换

    系统保持一个空闲页框队列，为进程分配内存时首先给进程分配一定量的页框，当发生缺页时，系统从空闲页框队列取出一个给进程，并将缺页装入。

    当空闲页框队列中的页框用完时、系统才能从内存中选择一页调出，该页可能是系统中任一进程的页，因此叫全局置换。

  • 可变分配局部置换

    首先为每个进程分配一定数目的页框，发生缺页时，只允许从该进程在内存的页面中换出一页。

    若缺页频繁，系统会适当的增加进程的页框数。若缺页率很低，则系统会适当减少进程的页框数目。

驻留集：分配给进程的页框的集合。

抖动：如果多道程度过高，导致过于频繁的页面换入与换出，使得调度页面的耗时比进程实际运行行的时间还多，系统效率急剧下降的现象称之为抖动。
产生原因：内存中并行的进程过多，每个进程分到的页框数过少，缺页过于频繁，页面换入换出耗时过大，导额 CPU 利用率过低，调度程序误以为 CPU 利用率低的原因是并行度不够高，就会增加多道程序的度，使得新进程进一步装入内存，反而进一步导致 CPU 利用率下降。

工作集：在当前一段时间内使用的页面的集合。描述工作集的二元函数：W(t，△)，当前一段时间内使用的页面的集合。

image-20231123091733101

根据工作集的大小系统来调整分配给进程的页框数。一般进程分得的页框数应大于工作集大小。

image-20231123092025882 image-20231123092318504 image-20231123092457207

请求分页存储管理系统 ：虚拟页式管理系统。 cpu 利用率低，磁盘交换区利用率高：频繁地缺页，页面一直在换入换出。

image-20231123093909395 image-20231123094112915

为什么不是 D。

image-20231123094402397 image-20231123094930373 image-20231123095057852 image-20231123095147271 image-20231123095212019 image-20231123095247002 image-20231123095317560 image-20231123095455927 image-20231123095621903 image-20231123095653332 image-20231123095728510

文件管理

文件管理基础

文件 是由创建者所定义的、具有文件名的一组相关元素的集合。 image-20231124055214128

数据项 ：文件系统中最低级的数据组织形式。

数据项有 基本数据项 和 组合数据项 两类。

记录 ：一组相关数据项的集合，用于描述一个对象在某方面的属性。

在记录中确定出一个或几个数据项把它们的集合称为 关键字（key)，来作为记录的唯一标识。

文件可分为 有结构文件 和 无结构文件 两种。在有结构的文件中，文件由若个相关记录组成；

而无结构文件则被看成是一个字符流。

文件的操作：

  • 创建文件：分配外存空间、建立自录项
  • 删除文件：删除目录项、释放其外存空间
  • 读文件：文件名：a、读入内存的自标地址：A image-20231124060136003
  • 写文件：文件名：a、读入内存的自标地址：A image-20231124060229597
  • 截断文件：放弃原有的文件内容（将原有文件的长度设置为 0）
  • 设置文件的读写位置：设置文件读/写指针的位置，以便每次读/写文件时不是从其始端而是从所设置的位置开始操作
  • 文件的打开与关闭：
    • 文件的打开：是指系统将文件控制块从外存拷贝到内存打开文件表的一个表自中，并将该表自的编号返回给用户，以方便之后的文件操作
    • 文件的关闭：将文件控制块从打开文件表自中删除

文件的逻辑结构

从用户观点出发所观察到的文件组织形式，它独立于文件的物理特性。

  • 记录的长度是否可以变化

    • 定长记录文件 image-20231124060717535

    • 变长记录文件 image-20231124060811594

  • 记录的组织形式

    • 顺序文件：记录按某种顺序排列所形成的文件。

      • 串结构文件：记录之间的顺序与关键字无关，通常按照记录添加的时间先后顺序排列，先来的记录在前后来的在后

      • 顺序结构文件：指文件中的所有记录按关键字排序，排序规则可以有多种。

      • 顺序文件的读写操作 image-20231124061401905

      • 顺序文件的优缺点

        优点：便于对记录进行批量处理；

        缺点：查找记录效率低，增加或删除记录效率低。

    • 索引文件

      image-20231124061713029

    • 索引顺序文件

      将顺序文件中的所有记录分为若于个组，并建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。

      image-20231124062233210

目录管理

  • 文件控制块(FCB)

    一个文件控制快对应一个文件，文件控制块的有序集合称为文件目录，一个文件控制块就是一个文件目录项。

    • 文件控制块包含的基本信息：文件名、文件物理位置、文件逻辑结构和文件的物理结构。
    • 文件控制块包含的存取控制信息：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限 。
    • 文件控制块包含的文件使用信息：文件的建立日期和时间、文件上一次修改的期和时间及当前便用信息。

  • 索引结点

    • 索引结点存放于磁盘上时
      1. 文件主标识符（属于谁）；
      2. 文件类型；
      3. 文件存取权限；
      4. 文件物理地址；
      5. 文件长度;
      6. 文件连接计数（指针计数，涉及文件共享）；
      7. 文件存取时间。
    • 索引结点存放于内存上时
      1. 索引结点编号：
      2. 状态;
      3. 访问计数；
      4. 文件所属文件系统的逻辑设备号（类似于标出属于 C 盘 D 盘……）。

  • 目录结构

    • 单级目录结构（理解：只有一个大文件夹）

      image-20231124070220650

      优点：实现简单，能实现按名存取；

      缺点：查找速度慢，不允许重名，不便于实现文件共享。

    • 两级目录结构

      image-20231124070413713

      优点：提高了检索自录的速度；

      在不同的用户自录中，可以使用相同的文件名；

      不同用户还可使用不同的文件名来访问系统中的同一个共享文件。

      缺点：不便于共享文件。

    • 树型目录结构

      image-20231124070946326

      优点：检索速度更快，文件目录命名更灵活；

      缺点：依然不便于文件共享。

    • 图型目录结构

      image-20231124071309810

      优点：检索速度更快，文件目录命名更灵活，方便文件（目录）共享。

外存分配

  • 连续分配：为每一个文件分配一组相邻接的盘块。

    image-20231124071857476

    连续分配的优点：顺序访问容易；顺序访问速度快。

    连续分配的缺点：会产生外部碎片；必须先知道文件的长度；文件空间扩展不方便。

  • 链接分配（非连续分配）

    通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成个链表。

    • 隐式链接

      image-20231124072450364

      优点：不会产生外部碎片，外存利用率高，易于文件存储空间扩展。

      缺点：只适合于顺序访问，它对随机访问是极其低效的；

      可靠性差，只要其中的任何一个指针出现问题，者都会导致整个链的断开。

    • 显式链接

      image-20231124072833732

      FAT 常驻内存，整个系统只有一张，所有文件共用，物理块号从 0 开始，每一个表项长度相同。

      优点：不会产生外部碎片，外存利用率高，易于文件存储空间扩展，且支持“直接存取（随机存取）”（why：只访问一次外存就可以找到目标磁盘块，与隐式链接要多次访问外存才能找到目标磁盘块不同），相比于隐式链接分配，地址转换不需要访问外存，效率高。

      缺点：文件分配表(FAT)需要占用不小的存储空间；不支持高效的直接存取。

    • 索引分配

      image-20231124073919601

      优点：支持随机访问（直接访问），不会产生外部碎片；

      缺点：文件较小的时候可能要花费较多的外存空间

    • 多级索引分配

      image-20231124074248223 image-20231124074410039

    • 混合索引分配方式

      image-20231124074602238

      直接地址、一次间接地址、多次间接地址

文件存诸空间的管理

  • 空闲表法

    image-20231124075119648

    空闲表法属于连续分配方式，为每个文件分配一块连续的存储空。

    表项按起始盘块号递增的次序排序。

    存储空间的分配与回收：与内存的动态分配类似，如首次适应算法；回收空间的时候也与内存回收方法类似，需要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。

  • 空闲链表法

    将所有空闲盘区拉成一条空闲链表。

    image-20231124075442822

  • 位示图法

    image-20231124075933549

    优点：

    从位示图中很容易找到一个或一组相邻接的空闲盘块；

    位示图很小，可将它保存在内存中，进行盘区分配时，无需首先把盘区分配表读入内存，节省了磁盘的启动操作。

  • 成组链接法

    image-20231124080420539 image-20231124080510682 image-20231124080651886

    空间分配：超级块中出栈，将块分配给文件，之后 N 减 1，不够则继续出栈，如果块中包含栈信息（说明到下一组了），将信息保存到超级块中（超级块已经出栈完了），然后将此块分配给文件，更新指针。

    空间回收：来一个压入栈中，栈满，将超级块复制到新回收的盘块中，更新指针，再更新超级块的栈和 N。

image-20231124081842881 image-20231124082030147 image-20231124082132217 image-20231124082209325 image-20231124082255276 image-20231124082405071 image-20231124082702689 image-20231124082825009

image-20231124082844507

image-20231124082924634 image-20231124082936671 image-20231124083048433 image-20231124083147888 image-20231124083256556 image-20231124083358190 image-20231124083430735 image-20231124083503794 image-20231124083556109 image-20231124083621283

image-20231124083929480 image-20231124084841443

image-20231124085032581

补充内容

  • 外存储器

    • 硬磁盘存储器

      • 结构：
        (1) 碟片。
        (2)磁盘驱动器，包括主轴、定位驱动和数据控制器三部分，作用是接收由主机发来的命令，将它换成磁盘驱动器的控制命令，实现主机和驱动器之间的数据格式转换和数据传送，并控制驱动器的读/写；

      • 硬磁盘轨道记录格式

        (1)磁头数，等于记录面数；

        (2)柱面数，表示硬盘每一面盘面上有多少磁道；

        (3)扇区数，表示每一条磁道上有多少个扇区。

      • 磁记录原理

        原理，磁表面存储器通过磁头和记录介质的相对运动完成读/写操作；

        编码方法，按某种规律，把一连串的二进制信息变成存储介质磁层中磁化的反转状态的序列；

        记录方式有调频式(FM)和改进调频式(MFM)。

      • 磁盘地址 image-20231124085711014

      • 磁盘阵列(RAID)

        RAID，是将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上交叉存储、并行访问，存储性能、可靠性和安全性都较高。

        RAID 有 6 个分级，其中 RAID1～RAID5 无论何时有磁盘损坏，都可以随时拔出损坏的磁盘再插入好的磁盘，而数据不会丢失。

        RAIDO: 无穴余，无校验的磁盘阵列

        RAID1 : 镜像磁盘阵列；
        RAID2: 含有可纠错的海明码校验；
        RAID3 : 采用位交叉奇偶校验；
        RAID4 : 采用块交叉奇偶校验；
        RAID5: 无独立校验的奇偶校验磁盘阵列

      • 磁盘访问时间

        • 寻道时间：把磁头移动到指定磁道上所经历的时间。
        • 旋转延迟时间：扇区移动到磁头下面所经历的时间。通常我们用磁盘旋转一周时间的一半来估计。
        • 传输时间：这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。

      • 磁盘调度

        1. 先来先服务(FCFS)
        2. 最短寻道时间优先(SSTF)
        3. SCAN 算法（根据磁头移动方向进行扫描，扫到低后折回来）
        4. 循环扫描(CSCAN)算法（规定方向扫描，一直走到底，直接回到 0，接着扫 ）
        5. LOOK 算法（根据磁头移动方向进行扫描，不会扫到低，当前方向没有任务就会折回）

    • 光盘

      存储密度高，成本低、容量大、携带方便、存储期长等

      CD-ROM：只读光盘；

      CD-R：只可写入一次的光盘

      CD-RW：可读可写光盘，可以重复读写；

      DVD-ROM ：高容量的 CD-ROM。

image-20231124091744901 image-20231124094051962 image-20231124094144849 image-20231124094227878 image-20231124094356991

image-20231124094620487 style = "zoom: 50%;"

image-20231124094721423 image-20231124095104359 image-20231124095233369 image-20231124095343382 image-20231124095417789

I/O 管理

概述

image-20231124095635363 image-20231124100206915

设备控制器：设备并不是直接与 CPU 进行通信，而是与设备控制器通信，设备控制器的主要职责是控制一个或多个/O 设备，以实现/O 设备和计算机之间的数据交换，

image-20231124100355061

设备控制器的基本功能：

  • 接收和识别命令
  • 数据交换
  • 标识和报告设备的状态
  • 地址识别
  • 数据缓冲
  • 差错控制（要求作废、重发）

总线：

  1. ISA 和 EISA 总线
    ISA(Industry Standard Architecture)总线其总线的带宽为 8 位，最高传输速率为 2Mb/s。
    EISA(Extended ISA)总线其总线的带宽为 32 位，最高传输速率为 32Mb/s。
  1. 局部总线
    VESA 总线和 PCI 总线。

I/O 方式：

  • 程序查询方式

    image-20231124101607721

    程序查询方式的特点是每时每刻不断查询/O 设备是否准备就绪。

    image-20231124101822470

  • 程序中断方式

    中断响应和处理

    响应条件：必须满足 CPU 中的允许中断触发器 EINT 为“1”；该触发器可以用开中断指令打开，可以用关中断指令或者由硬件自动关闭；

    响应时间：CPU 响应中断的时间是在每条指令执行阶段的结束时刻。

    中断处理:

    ​ 1.保护现场

    ​ 2.中断服务

    ​ 3.恢复现场

    ​ 4.中断返回

    image-20231124102203169

  • DMA 方式

    主存和 DMA 接口之间有一条专用的数据通路，因此主存和设备交换信息时，不需要通过 CPU，也不需要暂停 CPU 现行程序去为设备服务，使得 I/O 与主机并行工作，程序和数据传输并行工作，省去了保护现场和恢复现场的步骤，因此速度较快。

    DMA 传输过程

    ​ 预处理

    ​ 给 DMA 控制逻辑指明数据传输方向是输入还是输出；

    ​ 向 DMA 设备地址寄存器送入设备号，并启动设备；

    ​ 向 DMA 主存地址寄存器送入交换数据的主存起始地址；

    ​ 对字计数器赋予交换数据的个数；

    上述操作由 CPU 执行几条输入输出指令来完成，这些工作完成后 CPU 继续执行原来的程序

    ​ 数据传输（输出）

    1. 当设备准备好一个字时，发出选通信号，将该字读到 DMA 的数据缓冲寄存器(BR）中，表示数据缓冲寄存器“满”
    2. 与此同时设备向 DMA 接口发请求(DREQ)
    3. DMA 接口向 CPU 申请总线控制权(HRQ)
    4. CPU 发回 HLDA 信号，表示充允许将总线控制权交给 DMA 接口
    5. 将 DMA 主存地址寄存器中的主存地址送地址总线，并命令存储器写
    6. 通知设备已被授予一个 DMA 周期月(DACK)，并为交换下一个字做准备
    7. 将 DMA 数据寄存器中的内容送数据总线；
    8. 主存将数据总线上的信息写至地址总线指定的存储单元中
    9. 修改主存地址和字计数器值
    10. 判断数据块是否传送结束，若未结束，则继续传送；若已结束，则向 CPU 申请程序中断，标志数据块传输结束。

    ​ 数据传输（输入）

    1. 当设备准备好一个字时，发出选通信号，将该字读到 DMA 的数据缓冲寄存器(BR）中，表示数据缓冲寄存器“满”；
    2. 与此同时设备向 DMA 接口发请求（DREQ）；
    3. DMA 接口向 CPU 申请总线控制权（HRQ）；
    4. CPU 发回 HLDA 信号，表示允许将总线控制权交给 DMA 接口；
    5. 将 DMA 主存地址寄存器中的主存地址送地址总线，并命令存储器写；
    6. 通知设备已被授予一个 DMA 周期（DACK），并为交换下一个字做准备；
    7. 将 DMA 数据寄存器中的内容送数据总线；
    8. 主存将数据总线上的信息写至地址总线指定的存储单元中；
    9. 修改主存地址和字计数器值；
    10. 判断数据块是否传送结束，若未结束，则继续传送；若已结束，则向 CPU 申请程序中断，标志数据块传输结束。

    DMA 方式特点

    • DMA 使 CPU 与主存之间不存在固定联系，主存即可以被 CPU 访问，又可以被外设访问；
    • 在数据传输的时候，主存地址确定、传输数据的计数都由硬件电路直接实现；
    • 主存中要开辟专用缓冲区，以便随时供给和接收外设的数据；
    • DMA 使得 CPU 和外设并行，提高系统效率；
    • DMA 在开始前要通过程序进行预处理，结束后要通过中断方式进行后处理。

  • I/O 通道控制方式

    I/O 通道方式是 DMA 方式的改进，它进一步减少 CPU 的干预，把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。

    CPU 向/O 通道发送/O 指令，通道执行通道程序完成 I/O 任务

    通道指令的构成:(1) 操作码;(2) 内存地址;(3) 计数;(4)通道程序结束位 P;(5)记录结束标志 R。

    image-20231124104127579
image-20231124104243110 image-20231124104336129 image-20231124104430790

I/O 核心子系统

I/O 设备种类繁多，传输速率和功能差异都很大，需要多种方法来进行设备控制管理，这些方法的集合就是操作系统的 I/O 核心子系统（内核 I/O 子系统）。

它将内核的其他方面从繁重的 I/O 设备管理中解放了出来。

I/O 核心子系统服务包括：I/O 调度、缓冲区与高速缓存、设备分配与回收、假脱机等。

  • I/O 调度概念

    I/O 调度就是确定一个好的顺序来执行这些 I/O 请求。

  • 假脱机（主机）技术

    image-20231124104848300 image-20231124104953162 233

    应用：共享打印机 image-20231124105324531

    SPOOLing 技术的主要特点：

    • 提高了 1/O 的速度;
    • 将独占设备改造为共享设备；
    • 实现了虚拟设备功能。
image-20231124105607642 image-20231124105659480 image-20231124105808431 image-20231124105923452 image-20231124110032935 image-20231124110112401

image-20231124110139487

  • 设备分配

    设备分配中的数据结构：

    • 设备控制表(DCT)image-20231124110334584

    • 控制器控制表、通道控制表和系统设备表

      image-20231124110555787

    • 设备分配时应考虑的因素

      • 设备的固有属性：独占性，共享性，可虚拟性。

        • 独占设备：采用独享分配策略 。

          缺点是：设备得不到充分利用，而且还可能引起死锁。

        • 共享设备：可同时分配给多个进程使用，须注意对这些进程访问该设备的先后次序进行合理的调度。

        • 可虚拟设备：可虚拟设备是指一台物理设备在采用虚拟技术后，可变成多台逻辑上的虚拟设备，可虚拟设备被认为是可共享的设备，可以将它同时分配给多个进程使用。

      • 设备分配算法

        • 先来先服务；
        • 优先级高者优先。

      • 设备分配中的安全性

        • 安全分配方式
        • 不安全分配方式

    • 独占设备的分配程序

      • 基本的设备分配程序：进程提出 I/O 请求后，系统的设备分配程序可按下述步骤进行设备分配：

        • 分配设备：
          1. 取出/O 请求中的 物理设备名 逻辑名；
          2. 查找系统设备表(SDT)找出该设备的 DCT；
          3. 根据 DCT 中的设备状态字段判断该设备是否忙；
          4. 忙，则将请求 I/O 进程的 PCB 挂在设备队列上；
          5. 不忙，便按照一定的算法来计算本次设备分配的安全性；
          6. 如果不会导致系统进入不安全状态，便将设备分配给请求进程；
          7. 否则，将其 PCB 插入设备等待队列；
        • 分配控制器:
          1. 到其 DCT 中找出与该设备连接的控制器的 COCT；
          2. 从 COC 的状态字段中可知该控制器是否忙碌；
          3. 若忙，便将请求 I/O 进程的 PCB 挂在该控制器的等待队列上;
          4. 否则，便将该控制器分配给进程；
        • 分配通道:
          1. 在该 COCT 中找到与该控制器连接的通道的 CHCT;
          2. 根据 CHCT 内的状态信息，可知该通道是否忙碌；
          3. 若忙，便将请求 I/O 的进程挂在该通道的等待队列上；
          4. 否则，将该通道分配给进程。

      • 设备分配程序的改进

        • 增加设备的独立性
          使用逻辑设备名请求 I/O，一个逻辑设备对应多个物理设备，系统首先从 SDT 中找出第一个该类物理设备的 DCT，若该设备忙，又查找第二个该类物理设备的 DCT，仅当所有该类物理设备都忙时，才把进程挂在该类物理设备的等待队列上。

        • 考虑多通路情况
          若设备(控制器)所连接的第一个控制器(通道)忙时，应查看其所连接的第二个控制器(通道)，仅当所有的控制器(通道)都忙时，此次的控制器(通道)分配才算失败才把进程挂在控制器（通道的等待队列上。而只要有一个控制器（通道）可用，系统便可将它分配给进程。

  • 高速缓存与缓冲区

    1. 磁盘高速缓存 image-20231125062740741

    磁盘高速缓是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。磁盘高速缓存在逻辑上属于磁盘，物理上则是驻留在内存中的盘块。

    高速缓存分为两种形式：
    1）在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定；
    2）把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘 I/O 时共享。

    1. 缓冲区(Buffer)

    引入缓冲区的主要目的
    1）缓和 CPU 与 I/O 设备间的速度不匹配
    2）减少对 CPU 的中断频率；
    3）解决基本数据单元大小不匹配的问题；
    4）提高 CPU 和 I/O 设备之间的并行性。

    其实现方法有：
    ⑴采用硬件缓冲器，成本高，仅用于一些关键部件；
    ⑵采用缓冲区(属于内存的一片区域)。

    缓冲技术分类：
    1）单缓冲：在设备和处理器之间设置一个缓冲区。设备和处理机进行数据交换时，先把被数据写入缓冲区，然后需要数据的设备或处理机从缓冲区取走数据。
    image-20231125070943379 image-20231125071126720
    综上： 单缓冲区处理每块数据用时 MAX(B, C)+M。

    2）双缓冲：
    image-20231125071642227 image-20231125071653439
    综上，对于双缓冲区，读取一个块的时间为 MAX(B，M+C)。

    3）循环缓冲：系统包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，多个缓冲区构成一个循环链表，另设两个辅助指针 in 和 out，in 指针指向可以输入数据的第一个空缓冲区，out 指针指向可以提取数据的第一个满缓冲区。

    数据输入/输出：输入时，从设备接收数据到 in 所指缓冲区中，in 移向下一个空缓冲区；当进程需要数据时，取 out 所指的一个缓冲区，并从此缓冲区中提取数据，out 移向下一个满缓冲区。输出过程则正好相反。

    4）缓冲池
    image-20231125072210659

image-20231125072553938 image-20231125072622678 image-20231125072712940 image-20231125072838078 image-20231125073101029 image-20231125073253885 image-20231125073455520 image-20231125073722615 image-20231125073755887 image-20231125073851213 image-20231125073937627 image-20231125074035097

计算机网络

计算机网络体系结构

image-20231127215251296

计算机网络概述

概念及功能

计算机网络：是一个将分散的、具有独立功能的 计算机系统 ，通过 通信设备 与 线路 连接起来，由功能完善的 软件 实现 资源共享 和 信息传递 的系统。

计算机网络是 互连 的、 自治 的计算机集合。
互连 -通过通信链路互联互通
自治 -无主从关系

计算机网络的功能

  • 数据通信：image-20231127220323788
  • 资源共享：同一个计算机网络上的其他计算机可使用某台计算机的计算机资源的行为，可共享 硬件、软件、数据 。
  • 分布式处理：多台计算机各自承担同一工作任务的不同部分（ Hadoop 平台 ）
  • 提高可靠性：替代机
  • 负载均衡

计算机网络的发展

  • 第一阶段
    image-20231127220716978
  • 第二阶段
    三级结构 image-20231127220906062
  • 第三阶段
    多层次 ISP 结构 image-20231127221026729
image-20231127221433008

组成与分类

计算机网络的组成

  1. 组成部分：硬件、软件、协议（一系列规则和约定的集合）

  2. 工作方式

    • 边缘部分 用户直接使用
      • C/S 方式
      • P2P 方式
    • 核心部分 为边缘部分服务

  3. 功能组成

    • 通信子网 实现 数据通信
    • 资源子网 实现 资源共享/ 数据处理
    image-20231127222701615

计算机网络的分类

  1. 按分布范围分 广域网 WAN（常：交换技术） 城域网 MAN 局域网 LAN(常：广播技术) 个人区域网 PAN
  2. 按使用者分 公用网 专用网
  3. 按交换技术分 电路交换（电话） 报文交换（技术：存储转发） 分组交换（技术：存储转发）
  4. 按拓扑结构分 总线型 星型 环型 网状型
  5. 按传输技术分
    • 广播式网络 共享公共通信信道
    • 点对点网络 使用 分组存储转发 和 路由选择 机制
image-20231127223757539

标准化工作及相关组织

标准化工作

标准的分类

  • 法定标准 由权威机构制定的正式的、合法的标准 OSI
  • 事实标准 某些公司的产品在竞争中占据了主流时间长了，这些产品中的协议和技术就成了标准 TCP/IP
image-20231127224530574

标准化工作的相关组织

  • 国际标准化组织 ISO OSI 参考模型、HDLC 协议
  • 国际电信联盟 ITU 制定通信规则
  • 国际电气电子工程师协会 IEEE 学术机构、IEEE802 系列标准、5G
  • Internet 工程任务组 IETF 负责因特网相关标准的制定 （RFC XXXX）
image-20231127224754508

性能指标之速率、带宽、吞吐量

  • 速率

    速率即 数据率 或称 数据传输率 或 比特率 。
    连接在计算机网络上的 主机 在数字信道上传送数据 位数的速率。
    单位是 b/s，kb/s，Mb/s，Gb/s，Tb/s
    千1kb/s=103b/s兆1Mb/s=103kb/s=106b/s吉1Gb/s=103Mb/s=106kb/s=109b/s太1Tb/s=103Gb/s=106Mb/s=109kb/s=1012b/s\begin{aligned} &千 1kb/s = 10^3b/s \\ &兆 1Mb/s = 10^3kb/s = 10^6b/s \\ &吉 1Gb/s = 10^3Mb/s = 10^6kb/s = 10^9b/s \\ &太 1Tb/s = 10^3Gb/s = 10^6Mb/s = 10^9kb/s = 10^{12}b/s \end{aligned}

    存储容量 1Byte(字节)= 8bit(比特)1KB=210B=1024B=1024∗8b1MB=210KB=1024KB1GB=210MB=1024MB1TB=210GB=1024GB\begin{aligned} &\text{存储容量 1Byte(字节)= 8bit(比特)} \\ &1KB = 2^{10}B = 1024B = 1024*8b \\ &1MB = 2^{10}KB = 1024KB \\ &1GB = 2^{10}MB = 1024MB \\ &1TB = 2^{10}GB = 1024GB \end{aligned}

  • 带宽

    “带宽”原本指某个信号具有的频带宽度，即最高频率与最低频率之差，单位是赫兹（Hz）

    计算机网络中，带宽用来表示网络的通信线路传送数据的能力，通常是指单位时间内从网络中的某一点到另一点所能通过的“ 最高数据率 ”。单位是“比特每秒”，b/s，kb/s，Mb/s，Gb/s。

    image-20231127230056671

  • 吞吐量

    表示在 单位时间 内通过 某个网络（或信道、接口） 的数据量。单位 b/s，kb/s，Mb/s 等

    吞吐量受网络的带宽或网络的额定速率的限制

性能指标之时延、时延带宽积、往返时间 RTT、利用率

  • 指数据（报文/分组/比特流从网终（或链路）的一端传送到另一端所需的时间。也叫 延迟或迟延 。单位是 S。
    image-20231127231417314

  • 时延带宽积
    时延带宽积 bit = 传播时延 S × 带宽 b/s
    image-20231127231627020

  • 往返时延 RTT

    从 发送方发送数据开始，到发送方收到接收方的确认（接收方收到数据后立即发送确认），总共经历的时延。
    今

    RTT 越大，在收到确认之前，可以发送的数据越多。

    RTT 包括往返传播时延 = 传播时延*2、未端处理时间

    不包括传输（发送）时延（主机把数据放到信道的时间），只是管信道上的时延。

  • 利用率

    • 信道利用率 有数据通过时间(有+无)数据通过时间\frac{\text{有数据通过时间}}{\text{(有+无)数据通过时间}}
    • 网络利用率 信道利用率加权平均值
    image-20231127232438395
image-20231127232527072

体系结构&参考模型

image-20231127232758378

分层结构、协议、接口、服务

分层的基本原则

  • 各层之间相互 独立 ，每层只实现一种相对独立的功能。
  • 每层之间 界面自然清晰 ，易于理解，相互交流尽可能少。
  • 结构上可分割开。每层都采用 最合适的技术 来实现。
  • 保持 下层对上层 的独立性，上层单向使用下层提供的服务
  • 整个分层结构应该能促进标准化工作

实体：第 n 层中的活动元素称为 n 层实体 。同一层的实体叫 对等实体 。
协议：为进行网络中的 对等实体 数据交换而建立的规则、标准或约定称为网络协议。【水平】

  • 语法：规定传输数据的格式
  • 语义：规定所要完成的功能
  • 同步：规定各种操作的顺序

接口（访问服务点 SAP）：上层使用下层服务的入口。
服务：下层为相邻上层提供的功能调用。【垂直】
image-20231128092001682

SDU 服务数据单元：为完成用户所要求的功能而应传送的数据
PCI 协议控制信息：控制协议操作的信息
PDU 协议数据单元：对等层次之间传送的数据单位。
image-20231128092141849

image-20231128092604713 image-20231128092637711 image-20231128092949183

OSI 参考模型（1）

提出第一个网络体系结构！image-20231128093031933

目的：支持异构网络系统的互联互通。
国际标准化组织（ISO）于 1984 年提出开放系统互连（OSI）参模型。（但是！理论成功，市场失败。）
image-20231128093501035

image-20231128094131528

image-20231128094504769

OSI 参考模型（2）

应用层：用户与网络的界面 所有能和用户交互产生网络流量的程序。
典型应用层服务：文件传输（FTP）电子邮件（SMTP）万维网（HTTP）

表示层：用于处理在两个通信系统中交换信息的表示方式（语法和语义）
功能： 数据格式变换 、 数据加密解密 、 数据压缩和恢复
没有单独的协议

会话层：向表示层实体/用户进程提供 建立连接并 在接上 有序 地 传输 数据。这是会话，也是 建立同步 (SYN)
功能：❶建立、管理、终止会话❷使用校验点可使会话在通信失效时从 校验点/同步点 继续恢复通信，实现数据同步。
适用于传输大文件。
主要协议：ADSP、ASP（不用记）

传输层：负责主机中 两个进程 的通信，即 端到端 的通信。传输单位是报文段或用户数据报。
功能：① 可 靠传输、不可靠传输② 差 错控制③ 流 量控制（意思：控制发送方速度）④复 用 分用
复用：多个应用层进程可同时使用下面运输层的服务。
分用：运输层把收到的信息分别交付给上面应用层中相应的进程
主要协议：TCP、UDP

网络层（重要）：主要任务是把 分组 从源端传到目的端，为分组交换网上的不同主机提供通信服务。网络层传输单位是 数据报 。
功能：⑴路由选择（ 最佳路径 ）⑵流量控制⑶差错控制（如奇偶校验）⑷拥塞控制（意思：宏观控制速度）
若所有结点都来不及接受分组，而要丢弃大量分组的话，网络就处于拥塞状态。因此要采取一定措施缓解这种拥塞。
主要协议：IP、IPX、ICMP、IGMP、ARP、RARP、OSPF

数据链路层：主要任务是把网络层传下来的数据报 组装成帧 。数据链路层/链路层的传输单位是 帧 。
功能：㈠成帧（定义帧的开始和结束）㈡差错控制（ 帧错+位错 ）㈢流量控制（意思：告诉发送方慢点发）㈣访问（接入）控制控制（ 控制对信道的访问 ）image-20231128101100240
主要协议：SDLC、HDLC、 PPP、STP

物理层：主要任务是在 物理媒体 上实现比特流的 透明传输 。物理层传输单位是 比特 。
透明传输 ：指不管所传数据是什么样的比特组合，都应当能够在链路上传送。
功能：Ⅰ定义接口特性Ⅱ定义传输模式（ 单工、半双工、双工 ）Ⅲ定义传输速率Ⅳ比特同步Ⅴ比特编码
要协议：Rj45 802.3

image-20231128101531109

TCP/IP 参考模型

image-20231128101712209

OSI 参考模型与 TCP/IP 参考模型相同点：

  • 都分层
  • 基于独立的协议栈的概念
  • 可以实现异构网络互联

OSI 参考模型与 TCP/IP 参考模型不同点：

  • OSI 定义二点：服务、协议、接口
  • OSI 先出现，参考模型先于协议发明，不偏向特定协议
  • TCP/IP 设计之初就考虑到异构网 互联 问题，将 IP 作为重要层次
  • image-20231128102107034 面向连接 分为三个阶段，第一是建立连接，在此价段，发出一个建立连接的请求。只有在连接成功建立之后，才能开始数据传输，这是第二阶段接着，当数据传输完毕，必须释放连接。 而面向 无连接 没有这么多阶段，它直接进行数据传输。
image-20231128102431730 image-20231128102642644 image-20231128102739978

第一章知识总结

image-20231128102831321

物理层

image-20231128103229225

通信基础

物理层基本概念

物理层解决如何在连接各种计算机的传输媒体上 传输数据比特流 ，而不是指具体的传输媒体

物理层主要任务：确定与传输媒体 接口 有关的一些特性: arrow_right: 定义标准

物理层接口特性:

  1. 机械特性
    定义物理连接的特性，规定物理连接时所采用的规格、接口形状、引线数目、引脚数量和排列情况。
  2. 电气特性
    规定传输二进制位时，线路上信号的 电压范围 、阻抗匹配、传输 速率 和 距离 限制等。
  3. 功能特性
    指明某条线上出现的某一 电平表示何种意义 ，接口部件的信号线的用途。
  4. 规程特性（过程特性）
    定义各条物理线路的工作规程和时序关系。

数据通信基础知识（1）

image-20231128104229096

通信的自的是传送消息、（消息：语音、文字、图像、视频等）

数据通信指在不同计算机之间传输表示信息的二进制数 0、1 序列的过程。

数据 data：传送信息的实体，通常是有意义的符号序列。

信号：数据的电气/电磁的表现，是数据在传输过程中的 存在形式 。
数学信号/离散信号：代表消息的参数的取值是离散的。image-20231128104419085
模拟信号/连续信号：代表消息的参数的取值是连续的，image-20231128104431673

信源：产生和发送数据的源头。

信宿：接收数据的终点。

信道：信号的传输媒介。一般用来表示向某一个方向传送信息的介质，因此一条通信线路往往包含一
条发送信道和一条接收信道。

  • 按传输信号分
    模拟信道（传送模拟信号）、数字信道（传送数字信号）
  • 按传输介质分
    无线信道、有线信道

单工通信 ：只有一个方向的通信而没有反方向的交互，仅需要一条信道。
半双工通信/双向交替通信 ：通信的双方都可以发送或接收信息，但任何一方都不能同时发送和接收，需要 两条 信道。
全双工通信/双向同时通信 ：通信双方可以同时发送和接受信息，也需要 两条 信道。

数据传输方式：

  • 串行传输
    将表示一个字符的 8 位二进制数按由低位到高位的顺序依次发送。
    速度 慢 ，费用 低 ，适合 远 距离 image-20231128110223381
  • 并行传输
    将表示一个字符的 8 位二进制数同时通过 8 条信道发送。
    速度 快 ，费用 高 ，适合 近 距离 image-20231128110355447

同步传输：在同步传输的模式下，数据的传送是以一个数据区块为单位，因此同步传输义称为区块传输。在传送数据时，需先送出 1 个或多个同步字符，再送出整批的数据。image-20231128110658937

异步传输：异步传输将比特分成小组进行传送，小组可以是 8 位的 1 个字符或更长。发送方可以在任何时刻发送这些比特组，而接收方不知道它们会在什么时候到达。传送数据时，加一个字符起始位和一个字符终正位。image-20231128110957259

image-20231128111044893

数据通信基础知识（2）

码元 是指用一个 固定时长 的 信号波形 （数字脉冲），代表不同离散数值的基本波形，是数字通信中数字信号的计量单位，这个时长内的信号称为 k 进制码元，而该时长称为码元宽度。当码元的离散状态有 M 个时（M 大于 2），此时码元为 M 进制码元。
1 码元可以携带多个比特的信息量。例如，在使用二进制编码时，只有两种不同的码元，表 1 状态
种代表 0 状态，另一种代表 1 状态。
image-20231129023316035
K 进制码元——4 进制码元: arrow_right: 码元的离散状态有 4 个: arrow_right: 4 种高低不同的信号波形 00、01、10、11

速率也叫数据率，是指数据的 传输速率 ，表示单位时间内传输的数据量。可以用 码元传输速率 和 信息传输速率 表示。
⑴ 码元传输速率：别名码元速率、波形速率、调制速率、符号速率等，它表示单位时间内数字通信系统所传输的码元个数（也可称为 脉冲个数或信号变化的次数 ），单位是 波特（Baud）。1 波特表示数字通信系统每秒传输一个码元。（一个码元到另一个码元算变化次数，即使信号图形没有变）image-20231129024009506

数字信号有多进制和二进制之分，但 码元速率与进制数无关，只与 码元长度 T （占的时长）有关。RB=1T(B)R_{B}=\frac1T(B)
⑵ 信息传输速率：别名信息速率、比特率等，表示单位时间内数字通信系统传输的二进制码元个数（即比特数），单位是比特/秒（b/s）。
关系 ：若一个码元携带 n bit 的信息量，则 M Baud 的码元传输速率所对应的信息传输速率为 MXn bit/s。
image-20231129025030117

image-20231129025255840

带宽（Bandwidth）
①模拟信号系统中：当输入的信号频率高或低到一定程度，使得系统的输出功率成为输入功率的一半时(即-3dB)，最高频率和最低频率间的差值就代表了系统的通频带宽，其单位为 赫兹 Hz
②数字设备中：表示在单位时间内从网络中的某一点到另一点所能通过的 “最高数据率”/单位时间内通过链路的数量，常用来表示网络的通信线路所能传输数据的能力。单位是比特每秒(bps)。

奈氏准则、香农定理（重点考察计算的知识点）

失真
image-20231129025913329
影响失真程度的因素： 1.码元传输速率 2.信号传输距离 3.噪声干扰 4.传输媒体质量
失真的一种现象一一码间串扰

奈氏准则（奈奎斯特定理）：在理想低通（无噪声，带宽受限）条件下，为了避免码间串扰，极限码元传输速率为 2WBaud，W 是信道带宽，单位是 Hz。 只有在这两个公式这带宽才用 Hz！！
为了混淆大家，再求一步极限数据率吧～

理想低通信道下的极限数据传输率=2Wlog2V(b/s)\boxed{\text{理想低通信道下的极限数据传输率=2}\mathsf{Wlog}_2\mathsf{V(b/s)}}

V：几种码元/码元的离散电平数目（我：对数应该是表示有多少位）
W：带宽（Hz）
①在任何信道中， 码元传输的速率是有上限的 。若传输速率超过此上限，就会出现严重的码间串扰问题，使接收端对码元的完全正确识别成为不可能。
②信道的 频带越宽（即能通过的信号高频分量越多），就可以用更高的速率进行码元的有效传输。
③ 奈氏准则给出了码元传输速率的限制，伯并没有对信息传输速率给出限制。
④由于码元的传输速率受奈氏准则的制约，所以要提高数据的传输速率，就必须设法使每个码元能携带更多个比特的信息量，这就需要米用多元制的调制方法。
image-20231129034723820

噪声 存在于所有的电子设备和通信信道中。由于噪声随机产生，它的瞬时值有时会很大，因此噪声会使接收端对码元的判决产生错误。但是噪声的影响是相对的，若信号较强，那么噪声影响相对较。因此， 信噪比 就很重要。
信噪比=信号的平均功率/噪声的平均功率\text{信噪比=信号的平均功率/噪声的平均功率}，常记为 S/N，并用分贝（dB）作为度量单位，即： 信噪比(dB)=10log10(S/N)\text{信噪比(dB)=}10\mathrm{log}_{10}(\mathsf{S/N}) 数值等价
香农定理：在带宽受限且有噪声的信道中，为了不产生误差，信息的数据传输速率有上限值。

信道的极限数据传输速率=Wlog2(1+S/N)(b/s)\boxed{\text{信道的极限数据传输速率=Wlog}_2(1+\mathrm{S/N})\quad(\mathrm{b/s})}

S 是信道所传信号的平均功率
N 是信道内的高斯噪声功率
当题中给出信噪比单位为 dB，则要求出 S/N：S/N=10信噪比10S/N = 10^{\frac{\text{信噪比}}{10}}
①信道的 带宽 或信道中的 信噪比 越大，则信息的极限传输速率就 越高。
②对一定的传输带宽和一定的信噪比，信息传输速率的上限就确定了。
③只要信息的传输速率低于信道的极限传输速率，就一定能找到某种方法来实现 无差错的传输 。
④香农定理得出的为极限信息传输速率，实际信道能达到的传输速率要比它低不少。
⑤从香农定理可以看出，若信道带宽 W 或信噪比 S/N 没有上限（不可能），那么信道的极限信息传输速率也就没有上限。
image-20231129045156971

image-20231129045657295

编码&调制（1）

信道上传送的信号

  • 基带信号
    将数字信号 1 和 0 直接用两种不同的电压表示，再送到 数字信道 上去传输（ 基带传输 ）。
    来自信源 的信号，像计算机输出的代表各种文字或图像文件的数据信号都属于基带信号。基带信号就是发出的 直接表达了要传输的信息的信号，比如我们说话的声波就是基带信号。
  • 宽带信号
    将基带信号进行调制后形成的频分复用模拟信号，再传送到 模拟信道 上去传输（ 宽带传输 ）。
    把基带信号经过 载波调制 后，把信号的 频率范围搬移 到 较高的频段 以便在信道中传输（即仅在一段频率范围内能够通过信道）。

在传输距离较近时，计算机网络采用 基带传输 方式（近距离衰减小，从而信号内容不易发生变化）
在传输距离较远时，计算机网络采用 宽带传输 方式（远距离衰减大，即使信号变化大也能最后过滤出来基带信号）

image-20231129050622418 image-20231129050718810

编码&调制（2）

image-20231129053747936

二进制码元

  1. 非归零编码【NRZ】 image-20231129053833748
    高 1 低 0 ，编码容易实现，但没有检错功能且无法判断一个码元的开始和结束，以至于收发双方难以保持同步。
  2. 曼彻斯特编码（信号变化 2 次，理解：一个码元里电平的不同变化表示不同数据）曼彻斯特编码1
    将一个码元分成两个相等的间隔前一个间隔为低电平后一个间隔为高电平表示码元 1：码元 0 则正好相反。也可以采用相反的规定该编码的特点是在每一个码元的中间出现电平跳变，位中间的跳变既作时钟信号（可用于同步）又作数据信号，但它所占的频带宽度是原始的基带宽度的两倍。每一个码元都被调成两个电平， 所以数据传输速率只有调制速率的 1/2。</font
  3. 差分曼彻斯特编码（同样变化两次，但是在两个码元之间，电平相同则表示下一个是 1，电平不同，则表示下一个是 0）差分曼彻斯特编码1
    同 1 异 0 ，常用于局域网传输，其规则是：若码元为 1，则前半个码元的电平与上个个码元的后半个码元的申平相同，若为 0，则相反。该编码的特点是，在每个码元的中间，都有一次电平的跳转，可以实现自同步，且抗干扰性 强 于曼彻斯特编码。
  4. 归零编码【RZ】归零编码1
    信号电平在一个码元之内都要恢复到零的这种编码成编码方式。
  5. 反向不归零编码【NRZI】反向不归零编码1
    信号电平翻转表示 0，信号电平不变表示 1。（全 1，接收方不方便）
  6. 4B/5B 编码
    比特流中插入额外的比特以打破一连串的 0 或 1，就是用 5 个比特来编码 4 个比特的数据，之后再传给接收方，因此称为 4B/5B。编码效率为 80%。
    只采用 16 种对应 16 种不同的 4 位码其他的 16 种作为控制码（的开始和结束，线路的状态息等）或保留。
    image-20231129061310572
image-20231129062026754 image-20231129062413279 image-20231129063308406 image-20231129063345378

数据交换方式

image-20231129063851483 image-20231129063917365

电路交换（CircuitExchanging）
原理：在数据传输期间，源结点与目的结点之间有一条由中间结点构成的专用物理连接线路，在数据传输结束之前，这条线路一直保持。
image-20231129064018258
image-20231129064120380
到 B 后，B 沿节点原路返回发送呼叫应答，建立链接了。
释放时，发送释放请求，接收方发送释放应答。
特点：独占资源，用户始终占用端到端的固定传输带宽。适用于远程批处理信息传输或系统间实时性要求高的大量数据传输的情况。
image-20231129064543283

报文交换（MessageExchanging）
报文：报文(message)是网络中交换与传输的数据单元，即站点一次性要发送的数据块。报文包含了将要发送的完整的数据信息，其长短很不一致，长度不限且可变。
报文交换的原理：无需在两个站点之间建立一条专用通路，其数据传输的单位是报文，传送过程采用 存储转发 方式。
image-20231129065029021
image-20231129065400774

分组交换(PacketExchanging)
分组：大多数计算机网络都不能连续地传送任意长的数据，所以实际上网络系统把数据分割成小块，然后逐块地发送，这种小块就称作分组（packet）。
分组交换的原理：分组交换与报文交换的工作方式基本相同，都采用存储转发方式，形式上的主要差别在于，分组交换网中要 限制所传输的数据单位的长度，一般选 128B。发送节点首先对焦终端设备送来的数据报文进行接收、存储，而后将报文划分成一定长度的分组，并以分组为单位进行传输和交换。接收结点将收到的分组组装成信息或报文。
image-20231129065804912
image-20231129065922744

image-20231129070148011

数据报方式
image-20231129070436771
特点：
①数据报方式为网络层提供 无连接服务 。发送方可随时发送分组，网络中的结点可随时接收分组。
无连接服务：不事先为分组的传输确传输路径，每个分组独立确是传输路径，不同分组传输路径可能不同。
②同一报文的不同分组达到自的结点时可能发生刮序、重复与丢失。
③母个分组在传输过程中都必须携带源地址和目的地址，以及分组号。
④分组在交换结点存储转发时，需要排队等候处理，这会带来一定的时延。当通过交换结点的通信量较大或网络发生拥塞时，这种时延会大大增加，交换结点还可根据情况丢弃部分分组。

虚电路方式
虚电路将数据报方式和电路交换方式结合，以发挥两者优点。
虚电路：一条源主机到目的主机类似于电路的路径（逻辑连接），路径上所有结点都要维持这条虚电路的建立，都维持一张虚电路表，每一项记录了一个打开的虚电路的信息。
image-20231129071049025
特点：
①虚电路方式为网络层提供 连接服务 。源节点与目的结点之间建立一条逻辑连接，而非实际物理连接。
连接服务：首先为分组的传输确定传输路径（建立连接），然后沿该路径（连接）传输系列分组，系列分组传输路径相同，传输结束后拆除连接。
②一次通信的所有分组都通过虚电路顺序传送，分组不需携带源地址、自的地址等信息，包含虚电路号，相对数据报方式开销小，同一报文的不同分组到达目的结点时不会乱序、重复或丢失。
③分组通过虚电路上的每个节点时，节点只进行差错检测，不需进行路由选择。
④每个节点可能与多个节点之间建立多条虚电路，每条虚电路支持特定的两个端系统之间的数据传输，可以对两个数据端点的流量进行控制，两个端系统之间也可以有多条虚电路为不同的进程服务。
⑤致命弱点：当网络中的某个结点或某条链路出故障而彻底失效时，则所有经过该结点或该链路的虚电路将遭到破坏。
image-20231129071403473 image-20231129071555960

传输介质及分类

传输介质也称传输媒体/传输媒介，它就是数据传输系统中在发送设备和接收设备之间的物理通路。
传输媒体并不是物理层。
传输媒体在物理层的下面，因为物理层是体系结构的第一层，因此有时称传输媒体头 0 层。在传输媒体中传输的是信号，伯传输媒体开不知道所传输的信号代表什么意思。但物理层规定了 电气特性，因此能够识别所传送的比特流。
物理层是傻瓜，传输媒体连傻瓜都不如。
传输介质：

  • 导向性传输介质：电磁波被导向沿看着固体媒介（铜线/光纤）传播。
  • 非导向性传输介质一→自由空间，介质可以是空气、真空、海水等。

导向性传输介质一一 1.双绞线
双绞线是古老、又最常用的传输介质，它由两根采用一定规则并排绞合的、相互绝缘的铜导线组成。为了进一步提高抗电磁干扰能力，可在双绞线的外面再加上一个由金属丝编织成的屏蔽层，这就是屏蔽双绞线（STP），无屏蔽层的双绞线就称为非屏蔽双绞线（UTP）。
双绞线价格便宜，是最常用的传输介质之一，在局域网和传统电话网中普遍使用。模拟传输和数字传输都可以使用双绞线，其通信距离一般为几公里到数十公里。距离太远时，对于模拟传输：要用放大器放大衰减的信号；对于数字传输，要用中继器将失真的信号整形。

导向性传输介质一一 2.同轴电缆
同轴电缆由导体铜质芯线、绝缘层、网状编织屏蔽层和塑料外层构成。按特性阻抗数值的不同，通常将同轴电缆分为两类：50Q 同轴电缆和 75Q 同轴电缆。其中，50Q 同轴电缆主要用于传送基带数学信号，文称为基带同轴电缆，它在局域网中得到广泛应用；75Q 同轴电缆主要用于传送宽带信号，文称为宽带同轴电缆，它主要用于有线电视系统。

导向性传输介质一一 3.光纤
光纤通信就是利用光导纤维（简称光纤）传递光脉冲来进行通信。有光脉冲表示 1，无光脉冲表示 0。而可见光的频率大约是 108MHz，因此光纤通信系统的带宽远远大于目前其他各种传输媒体的带宽。
光纤在发送端有光源，可以采用发光二极管或半导体激光器，它们在电脉冲作用下能产生出光脉冲：在接收端用光电二极管做成光检测器，在检测到光脉冲时可还原出电脉冲。
光纤主要由纤芯(实心的！)和包层构成，光波通过纤芯进行传导，包层较纤芯有较低的折射率。当光线从高折射率的介质射向低折射率的介质时，其折射角将大于入射角。因此，如果入射角足够大，就会出现全反射，即光线碰到包层时候就会折射回纤芯、这个过程不断重复，光也就沿着光纤传输下去。
image-20231129073034381
光纤的特点：
①传输摄群小，中继距离长，对远距离传输特别经济。
②抗雷电和电磁干扰性能好。
③无串音干扰，保密性好，也不易被窃听或截取数据。
④体积小，重量轻。

image-20231129073735657 image-20231129073820351

物理层设备

中继器
诞生原因： 由于存在损耗，在线路上传输的信号功率会逐渐衰减，衰减到一定程度时将造成信号失真，因此会导致接收错误。
中继器的功能： 对信号进行 再生和还原 ，对衰减的信号进行放大，保持与原数据相同，以增加信号传输的距离，延长网络的长度。
中继器的两端： 两端的网络部分是网段，而不是子网，适用于完全相同的两类网络的互连，且两个网段速率要相同。
中继器只将任何电缆段上的数据发另一段电缆上。它仅作用于信号的电气部分，并不管数据中是否有错误数据或 不适于网段的数据。
两端可连相同媒体，也可连不同媒体。
中继器两端的网段一定要是同一个协议。（中继器不会存储转发，傻）
5-4-3 规则： 网络标准中都对信号的延迟范围作了具体的规定，因而中继器只能在规定的范围内进行，否则会网络故障。
5：不超过 5 个网段。
4：最多 4 个物理层设备。
3：只有 3 个段可连接计算机。

集线器（多口中继器）：再生，放大信号
集线器的功能： 对信号进行 再生放大转发 ，对衰减的信号进行放大，接着转发到其他所有（除输入端口外）处于工作状态的端口上，以增加信号传输的距离，延长网络的长度。不具备信号的定向传送能力，是一个共享式设备。
集线器不能分割冲突域。

第二章总结

image-20231129075837523 image-20231129075912406

数据链路层（重要 考题灵活 包括第四章网络层）

image-20231129080024318

数据链路层功能概述

image-20231129080758570

数据链路层基本概念
结点：主机、路由器。
链路：网络中两个结点之间的 物理通道，链路的传输介质主要有双绞线、光纤和微波。分为有线链路、无线链路。
数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路。
帧：链路层的协议数据单元，封装网络层数据报。
数据链路层 负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。

数据链路层功能概述
数据链路层在物理层提供服务的基础上 向网络层提供服务，其最基本的服务是将源自网络层来的数据 可靠 地传输到相邻节点的目标机网络层。其主要作用是 加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为 逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路
功能一：为网络层提供服务。 无确认无连接服务 ， 有确认无连接服务 ， 有确认面向连接服务。（有连接一定有确认！）
功能二：链路管理，即连接的建立、维持、释放（用于面向连接的服务）。
功能四：流量控制。（限制发送方哦~）
功能五：差错控制（帧错/位错）。

封装成顿&透明传输

image-20231129081814555 image-20231129082507286 封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。 首部和尾部包含许多的控制信息，他们的一个重要作用： 帧定界 （确定帧的界限）。 帧同步 ：**接收方** 应当能从接收到的二进制比特流中区分出帧的起始和终止。 组帧的四种方法 ：1.字符计数法，2.字符（节)填充法，3.零比特填充法，4.违规编码法。

透明传输
透明传输 是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。
当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。

  1. 字符计数法
    帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数。
    image-20231129082804938
    痛点：鸡蛋装在一个篮子里了。

  2. 字符填充法

    1. 当传送的帧是由文本文件组成时（文本文件的符都是从键盘上输入的，都是 ASCI 码）。不管从键盘上输入什么字符都可以放在帧里传过去，即 透明传输 。
    2. 当传送的帧是由非 ASCI 码的文本文件组成时（二进制代码的程序或图像等）。就要 采用字符填充方法实现透明传输 。
      image-20231129083304421

    实现方法：
    image-20231129083531345

  3. 零比特填充法（5“1”1“0”）
    image-20231129083836405

  4. 违规编码法
    image-20231129085036106

差错控制

差错从何而来？概括来说，传输中的差错都是由于噪声引起的。

全局性 1.由于线路本身电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。
解决办法：提高信噪比来减少或避免干扰。（对传感器下手）

局部性 2.外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
​ 解决办法：通常利用编码技术来解决

差错：

  • 位错【比特位出错，1 变成 0，0 变成 1。】
  • 帧错 [#1]-[#2]-[#3]
    • 丢失：收到 [#1]-[#3]
    • 重复：收到 [#1]-[2]-[#2]-[#3]
    • 失序：收到 [#1]-[#3]-[#2]
image-20231129120011214 image-20231129120231526

检错编码

奇偶校验码

image-20231129120644882 奇偶校验码特点：只能检查出奇数个比特错误，检错能力为 50%。

CRC 循环亢余码
image-20231129121411263
image-20231129121942350
image-20231129122114510
在数据链路层仅仅使用循环几余检验 CRC 差错检测技术，只能做到对顺的无差错接收，即凡是接收端数据链路层接受的，我们都能以非常接近于 1 的概率认为这些顺在传输过程中没有产生差错”。接收端丢弃的顺虽然曾收到了，但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的顺均无差错”。

“可靠传输”：数据链路层发送端发送什么，接收端就收到什么。
链路层使用 CRC 检验，能够实现无比特差错的传输，但这还不是可靠传输。

纠错编码

海明码
image-20231129122648684
海明距离（码距）：两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的海明距离（码距)，一个有效编码集中，任意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)。

可通过异或，看 1 的个数得码距。

检测 d 位，码距是 d+1；
纠错 d 位，码距是 2d+1。
image-20231129123849246

image-20231129124108131 image-20231129124219633 233 image-20231129124912555

image-20231129124949352 image-20231129125127878

image-20231129125206838

流量控制、可靠传输（重要）

流量控制与可靠传输机制

较高的发送速度 和 较低的接收能力 的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。

数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。

数据链路层流量控制手段：接收方收不下就不回复确认。

传输层流量控制手段：接收端给发送端一个窗口公告。

流量控制的方法：

  • 停止-等待协议（可理解为窗口为 1 的滑动窗口）：每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。image-20231130062958657
  • 滑动窗口协议
    • 后退 N 顿协议(GBN)
    • 选择重传协议(SR)
image-20231130063346503 image-20231130073226487 image-20231130073311745

停止-等待协议

为什么要有停止-等待协议？
除了比特出差错，底层信道还会出现丢包问题。为了实现流量控制。
丢包：物理线路故障、设备故障、病毒攻击、路由信息错误等原因，会导致数据包的丢失。

研究停等协议的前提？
虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据（接收方）。
因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。
“停止-等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。

停等协议有几种应用情况？
无差错情况&有差错情况

image-20231130074025122 image-20231130074454300 image-20231130074625199 image-20231130074757699 image-20231130075106888 image-20231130075358209 image-20231130075504466

后退 N 帧协议（GBN)

image-20231130075905884 image-20231130080326118

我例：发送方可按序发送，接收方发送确认帧表示前面的帧都收到了。
重传会传已发送但没有确认的帧。

image-20231130081126100 image-20231130081404877 image-20231130081958838 image-20231130083423389 image-image-20231130082325034 image-20231130082524951 image-20231130083302458 image-20231130083448841

选择重传协议（SR）

image-20231130083805901

解决办法：设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧。

image-20231130084301731 image-20231130084556348 image-20231130084925805 image-20231130085342116 image-20231130085814301 image-20231130090202873

image-20231130090354303

image-20231130090412895

介质访问控制

传输数据使用的两种链路

  • 点对点链路
    两个相邻节点通过一个链路相莲，没有第三者。
    应用：PPP 协议，常用于 广域网。
  • 广播式链路
    所有主机共享通信介质。
    应用：早期的总线以太网、无线局域网，常用于 局域网 。
    典型拓扑结构：总线型、星型（逻辑总线型）。

介质访问控制 的内容就是，采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况

  • 静态划分信道—— 信道划分介质访问控制
    • 频分多路复用 FDM
    • 时分多路复用 TDM
    • 波分多路复用 WDM
    • 码分多路复用 CDM
  • 动态分配信道（ 动态媒体接入控制/多点接入 ）
    特点：信道并非在用户通信时固定分配给用户。
    • 轮询访问介质访问控制 令牌传递协议
    • 随机访问介质访问控制 （一定选择题）
      所有用户可随机发送信息。
      发送信息时占 全部带宽。
      • ALOHA 协议 不听就说！
      • CSMA 协议 先听再说
      • CSMA/CD 协议 先听再说，边听边说。
      • CSMA/CA 协议

信道划分介质访问控制

信道划分介质访问控制：将使用介质的每个设备与来自同一信道上的其他设备的 通信隔离开，把 时域 和 频域 资源合理地分配给网络上的设备。

多路复用技术：把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备 共享信道资源 提高信道利用率。
把一条广播信道，逻辑上分成几条用于两个节点之间通信的互不于扰的子信道， 实际就是把广播信道转变为点对点信道

频分多路复用 FDM
用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的带宽（频率带宽）资源。
充分利用传输介质带宽，系统 效率较高；
由于技术比较成熟，实现也比较 容易。
image-20231130092732781

时分多路复用 TDM（我：单人可占总共分之一的速率）
将时间划分为一段段等长的时分复用顺（TDM）。每一个时分复用的用户在每一个 TDM 顺中占用 固定序号的时隙，所有用户轮流占用信道。
TDM 帧是在物理层传送的比特流所划分的，标志一个周期。
image-20231130093022303 image-20231130093034655

改进的时分复用一一统计时分复用 STDN（我：单人可占满速）
image-20231130093354775

波分多路复用 WDM
波分多路复用就是 光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率）不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来。

image-20231130093808823

码分多路复用 CDM

image-20231130100553025

ALOHA 协议

纯 ALOHA 协议
纯 ALOHA 协议思想：不监听信道，不按时间槽发送，随机重发。 想发就发
image-20231130104125553

时隙 ALOHA 协议
时隙 ALOHA 协议的思想：把时间分成若于个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送。 控制想发就发的随意性
image-20231130104457418

image-20231130104631166

CSMA 协议

image-20231130105054224

1-坚持 CSMA
坚持指的是对于监听信道 忙 之后的坚持。
1-坚持 CSMA 思想：如果一个主机要发送消息，那么它先监听信道
空闲则直接传输，不必等待。
忙则一直监听，直到空闲马上传输。
如果有冲突（一段时间内未收到肯定回复），则等待一个随机长的时间再监听，重复上述过程。
优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。
缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免。

非坚持 CSMA
非坚持指的是对于监听信道忙之后就不继续监听。
非坚持 CSMA 思想：如果一个主机要发送消息，那么它先监听信道。
空闲则直接传输，不必等待。
忙则等待一个随机的时间之后再进行监听。
优点：采用随机的重发延迟时间可以减少冲突发生的可能性。
缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低。

p-坚持 CSMA（p 表示概论）
p-坚持指的是对于监听信道空闲的处理。
p-坚持 CSMA 思想：如果一个主机要发送消息，那么它先监听信道。
空闲则以 p 概率直接传输，不必等待；概率 1-p 等待到下一个时间槽再传输。
忙则持续监听直到信道空闲再以 p 概率发送。
若冲突则等到下一个时间槽开始再监听并重复上述过程。
优点：既能像非坚持算法那样减少冲突，又能像 1-坚持算法那样减少媒体空闲时间的这种方案。

缺点：（三种）发生冲突后还是要坚持把数据发送完，造成了浪费。

image-20231130110509757

CSMA/CD 协议（重要）

image-20231130111705797 image-20231130112438805 image-20231130112556390 只要经过 2 时间还没有检测到碰撞，就能肯定这次发送不会发生碰撞。 image-20231130121712398 image-20231130121812078

A 站发了一个很短的帧，但发生了碰撞，不过顺在发送完毕后才检测到发生碰撞，没法停止发送，因为发完了。
最小帧长：帧的传输时延至少要两倍于信号在总线中的传播时延。

帧长(bit)数据传输速率≥2τ\frac{\text{帧长(bit)}}{\text{数据传输速率}} \geq 2 \tau

最小帧长=总线传播时延x 数据传输速率 x 2=2τ× 数据传输速率\text{最小帧长=总线传播时延x 数据传输速率 x 2} = \boxed{2\tau\times\text{ 数据传输速率}}

以太网规定最短帧长为 64B，凡是长度小于 64B 的都是由于冲突而异常终止的无效帧。（对小帧进行填充）

image-20231130122648709

CSMA/CA 协议（重要）

image-20231130123530538 image-20231130124206904

image-20231130124400669

轮询访问介质访问控制

image-20231201034825664

image-20231201035142003 image-20231201035753619

局域网、以太网、VlAN

局域网基本概念和体系结构

局域网
局域网（LocalAreaNetwork）：简称LAN，是指在某一区域内由多台计算机互联成的计算机组，使用广播信道。
特点1：覆盖的地理范围较小，只在一个相对独立的局部范围内联，如一座或集中的建筑群内。
特点2：使用专门铺设的传输介质（双绞线、同轴电缆）进行联网，数据传输速率高（10Mb/s～10Gb/s）。
特点3：通信延迟时间短，i误码率低，可靠性较高。
特点4：各站为平等关系，共享传输信道。
特点5：多采用分布式控制和广播式通信，能进行广播和组播。
决定局域网的主要要素为：网络拓扑，传输介质与介质访问控制方法。

局域网拓扑结构
image-20231201040915085

局域网传输介质

  • 有线局域网 常用介质：双绞线、同轴电缆、光纤
  • 无线局域网 常用介质：电磁波

局域网介质访问控制方法

image-20231201041409104

局域网的分类
image-20231201041958838

IEEE802标准
IEEE802.3：以太网介质访问控制协议（CSMA/CD）及物理层技术规范。
IEEE802.5：令牌环网（Token-Ring)的介质访问控制协议及物理层技术规范。
IEEE802.8：光纤技术咨询组，提供有关光纤联网的技术咨询（FDDI）。
IEEE802.11：无线局域网（WLAN）的介质访问控制协议及物理层技术规范。

MAC子层和LLC子层
image-20231201042530116

image-20231201042553624

以太网

以太网概述
以太网(Ethernet)指的是由Xerox公司创建并由Xerox、Intel和DEC公司联合开发的基带总线局域网规范，是当今现有局域网采用的最通用的通信协议标准。以太网络使用CSMA/CD（载波监听多路访问及冲突检测）技术。
以太网在局域网各种技术中占统治性地位：1.造价低廉（以太网网卡不到100块）；2.是应用最广泛的局域网技术；3.比令牌环网、ATM网便宜，简单；4.满足网络速率要求：10Mb/s~10Gb/s；
以太网两个标准：DIXEthernetV2：第一个局域网产品（以太网）规约。IEEE802.3：IEEE802委员会802.3工作组制定的第一个IEEE的以太网标准。（帧格式有一丢丢改动）

以太网提供无连接、不可靠的服务
无连接：发送方和接收方之间无“握手过程”。
不可靠：不对发送方的数据顿编号，接收方不向发送方进行确认，差错直接丢弃，差错纠正由高层（指传输层）负责。
以太网只实现无差错接收，不实现可靠传输。

image-20231201043527324

10BASE-T以太网（容易考到）
1OBASE-T是传送基带信号的双绞线以太网，T表示采用双绞线，现1OBASE-T采用的是无屏蔽双绞线（UTP），传输速率是10Mb/s。
物理上采用星型拓扑，逻辑上总线型，每段双绞线最长为100m。
采用曼彻斯特编码。
采用CSMA/CD介质访问控制

适配器与MAC地址
计算机与外界有局域网的连接是通过通信适配器的。
适配器上装有处理器和存储器（包括RAM和ROM）。
ROM上有计算机硬件地址MAC地址。
在局域网中，硬件地址文称为物理地址，或MAC地址。（实际上是标识符）
MAC地址：每个适配器有一个全球唯一的48位二进制地址，前24位代表厂家（由IEEE规定），后24位厂家自已指定。常用6个十六进制数表示，如02-60-8c-e4-b1-21。

以太网MAC帧
最常用的MAC帧是以太网V2的格式
image-20231201044812200

高速以太网
速率≥100Mb/s的以太网称为高速以太网。

  • 100BASE-T以太网
    在双绞线上传送100Mb/s基带信号的星型拓扑以太网，仍使用IEEE802.3的CSMA/CD协议。
    支持全双工和半双工，可在全双工方式下工作而无冲突。
  • 吉比特以太网
    在光纤或双绞线上传送1Gb/s信号
    支持全双工和半双工，可在全双工方式下工作而无冲突。
  • 10吉比特
    10吉比特以太网在光纤上传送10Gb/s信号。
    只支持全双工，无争用问题。
image-20231201045148281

IEEE 802.11、无线局域网

IEEE802.11是无线局域网通用的标准，它是由IEEE所定义的无线网络通信的标准。

802.11的MAC头格式
image-20231201045852676
image-20231201050119089

有固定基础设施无线局域网
image-20231201050636655

无固定基础设施无线局域网的自组织网络
image-20231201050741729

VLAN基本念及基本原理

image-20231201051018694 ![image-20231201051140406](https://s2.loli.net/2023/12/01/dxFYLruXZBHJOe6.png) ![image-20231201051600040](https://s2.loli.net/2023/12/01/XrOeh1y72GRgVdk.png) image-20231201051614330 ![image-20231201051903836](https://s2.loli.net/2023/12/01/YWErRhyeQPLBob2.png) image-20231201052121326 image-20231201052600231 image-20231201052724115

广域网及相关协议

广域网（WAN，WideAreaNetwork），通常跨接很大的物理范围，所覆盖的范围从几十公里到几千公里，它能连接多个城市或国家，或横跨几个洲并能提供远距离通信，形成国际性的远程网络。
广域网的通信子网主要使用分组交换技术。广域网的通信子网可以利用公用分组交换网、卫星通信网和无线分组交换网，它将分布在不同地区的局域网或计算机系统互连起来，达到资源共享的目的。如因特网（Internet）是世界范围内最大的广域网。
image-20231201053125012

PPP协议
点对点协议PPP（Point-to-PointProtocol）是目前使用最广泛的数据链路层协议，用户使用拨号电话接入因特网时一般都使用PPP协议。只支持全双工链路
PPP协议应满足的要求：

  • 简单 对于链路层的帧，无需纠错，无需序号，无需流量控制。
  • 封装成帧 帧定界符
  • 透明传输 与帧定界符一样比特组合的数据应该如何处理：异步线路用字节填充，同步线路用比特填充。
  • 多种网络层协议 封装的IP数据报可以采用多种协议。
  • 多种类型链路 串行/并行，同步/异步，电/光…
  • 差错检测 错就丢弃。
  • 检测连接状态 链路是否正常工作。
  • 最大传送单元 数据部分最大长度MTU（1500）。
  • 网络层地址协商 知道通信双方的网络层地址。
  • 数据压缩协商

PPP协议无需满足的要求：纠错、流量控制、序号、不支持多点线路。

image-20231201054315117

image-20231201054435598

image-20231201054709421

HDLC协议
高级数据链路控制（High-Level Data Link Control或简称HDLC），是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织(ISO)根据IBM公司的SDLC(SynchronousData Link Control)协议扩展开发而成的
数据报文可透明传输，用于实现透明传输的“0比特插入法（5“1”1“0”）”易于硬件实现
采用全双工通信
所有帧采用CRC检验，对信息进行顺序编号，可防止漏收或重份，传输可靠性高。
image-20231201055118867
image-20231201055321791
image-20231201055624037

image-20231201055712757

链路层设备

image-20231201060138453 ![image-20231201060610665](https://s2.loli.net/2023/12/01/gJzbFm7NfBZMl2y.png) image-20231201061359210 image-20231201061634302 image-20231201061839067 image-20231201062009948 image-20231201062417652 image-20231201062553370image-20231201062804970

image-20231201062819956

第三章百结

bg

网络层

image-20231201083432012

概述和功能

网络层功能概述

主要任务是把分组从源端传到目的端，为分组交换网上的不同主机提供通信服务。网络层传输单位是数据报。
功能一：路由选择与分组转发（最佳路径）
功能二：异构网络互联
功能三：拥塞控制
若所有结点都来不及接受分组，而要丢弃大量分组的话，网络就处于拥塞状态。因此要采取一定措施，缓解这种拥塞。

  • 开环控制 静
    - 闭环控制 动

SDN基本念

image-20231201084827141

数据平面
数据平面执行的主要功能是根据转发表进行转发，这是路由器的本地动作。
image-20231201085516676

控制平面（传统方法/每路由器法）
image-20231201085723913

控制平面(SDN方法:Software-Defined Networking)
image-20231201085950071

控制平面中的路由选择处理器
image-20231201090153339

SDN控制平面

image-20231201090456810

SDN控制器的三个层次
image-20231201090706404

image-20231201091013074 image-20231201091243201

路由算法及路由协议

路由算法
最佳路由：“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

  • 静态路由算法（非自适应路由算法）管理员手工配置路由信息
    简便、可靠，在负荷稳定、拓扑变化不大的网络中运行效果很好，广泛用于高度安全性的军事网络和较小的商业网络。
    路由更新慢，不适用大型网络。
  • 动态路由算法（自适应路由算法）路由器间彼此交换信息，按照路由算法优化出路由表项。
    路由更新快，适用大型网络，及时响应链路费用或网络拓扑变化。
    算法复杂，增加网络负担。
    • 全局性 链路状态路由算法 OSPF
      所有路由器掌握完整的网络拓扑和链路费用信息。
    • 分散性 距离向量路由算法 RIP
      路电器只掌握物理租连的令居及链路费用。

分层次的路由选择协议
image-20231201092530966
image-20231201092621428

IP数据报、IPv4、网络地址转换NAT、子网、编址CIDR、ARP、DHCP、ICMP

IP数据报格式

TCP/IP协议栈
image-20231201093217885

IP数据报格式
image-20231201093349487
image-20231201094247448

IP数据报分片

最大传送单元MTU
链路层数据帧可封装数据的上限。
以太网的MTU是1500字节。
image-20231201094422704
如果所传送的数据报长度超过某链路的MTU值？分片

IP数据报格式
image-20231201094929462
image-20231201095438349

总长度单位是1B、片偏移单位是8B、首部长度单位是4B。（一种八片首饰）

IPv4地址

IP编址的历史阶段

  • 分类的IP地址
  • 子网的划分
  • 构成超双（无分类编址方法）

分类的IP地址

IP地址：全世界唯一的32位/4字节标识符，标识路由器主机的接口。
IP地址：:={<网络号>,<主机号>}image-20231201100355992
image-20231201100920673

image-20231201101322632

image-20231201101513995

image-20231201103144341

网络地址转换(NAT)

image-20231201103254136

网络地址转换NAT（Network Address Translation）：在专用网连接到因特网的路由器上安装NAT软件，安装了NAT软件的路由器叫NAT路由器，它至少有一个有效的外部全球IP地址。
image-20231201103817348

子网划分与子网掩码

image-20231201104101995

image-20231201104418763
image-20231201104559803
image-20231201104747506
子网掩码与IP地址逐位相与，就得到子网网络地址。image-20231201104956134
image-20231201105412826
image-20231201110459127

image-20231201111209078

三级网路技术的部分技巧(笔记较老，较简单，现在不一定看明白，可能存在问题)

地址聚合可用 看主机号

  • 掩码相同（3个）
    30：3*（22-2）+2=8
    29：3*（22-2）+2=20
    28：3*（22-2）+2=44
    27：3*（22-2）+2=92
    ……
  • 2个n位，1个n-1位：聚合后：n-2位，2n-2

网络地址

  • 2个n位，1个n-1位：n-2位
    “前同.3个中最后不同的 取最小的”
  • 2个n位：n-1位
    同理

大题一

类别 值
IP地址（已知） 125.151.28.63
子网掩码（已知） 255.240.0.0
地址类别 A类
网络地址 125.144.0.0（掩码对应的前面）
直接广播地址 125.159.255.255（掩码不对应的地方变1）
受限广播地址 255.255.255.255（送分）
子网内的第一个可用IP地址 125.144.0.1（当作网络地址加一）
主机号 0.7.28.63（ip地址与掩码不对应的部分）
最后一个可用IP 125.159.255.254（直接广播地址减一）

路由表题

网络结构
目的网络（192.168）/掩码长度 输出端口（已填）
.6.129和.6.130聚合➡️6.1000 0001和6.1000 0010➡️6.128/30 S0(直接连接）
.6.133和.6.134聚合➡️6.1000 0101和6.1000 0110➡️6.132/30 S1(直接连接)
.6.66和.6.65和.6.67聚合➡️6.0100 0010和6.0100 0001和6.0100 0011➡️6.64/29 S0
同理 S1
.65.0/24和.64.0/24和.66.0/24和.67.0/24聚合➡️0100 0001.0和0100 0000.0和0100 0010.0和0100 0011.0➡️64.0/22 S0
同理 S1

（不知掩码）左边填写相应的聚合，聚合时将不同的地方用二进制表示，从右往左看（相当于移动竖线），要求找到对应位相同的最大部分，（三个聚合，应该是当不同在最后一段时）但是剩余不同部分不能是全0或全1。image-20231201120522768

无分类编址CIDR

image-20231201124847039
image-20231201124942950

无分类域间路由选择CIDR：1.消除了传统的A类，B类和C类地址以及划分子网的概念。
2.融合子网地址与子网掩码，方便子网划分。

CIDR记法：IP地址后加上“/”，然后写上网络前缀（可以任意长度）的位数。e.g. 128.14.32.0/20
image-20231201125311669

构成超网
将多个子网聚合成一个较大的子网，叫做构成超网，或路由聚合。
方法：将网络前缀缩短（所有网络地址取交集）。
image-20231202083107252
image-20231202083358221

最长前缀匹配
使用CIDR时，查找路由表可能得到几个匹配结果（跟网络掩码按位相与），应选择具有最长网络前缀的路由。前缀越长，地址块越小，路由越具体。
bg

ARP协议

image-20231202085658583 ![bg1](https://s2.loli.net/2023/12/02/qQS5LpIRUrgGPJf.png)

由于在实际网络的链路上传送数据时，最终必须使用MAC地址。ARP协议：完成主机或路由器IP地址到MAC地址的映射。

ARP协议使用过程：
检查ARP高速缓存，有对应表项则写入MAC帧，没有则用目的MAC地址为FF-FF-FF-FF-FF-FF的帧封装并广播ARP请求分组，同一局域网中所有主机都能收到该请求。目的主机收到请求后就会向源主机单播一个ARP响应分组，源主机收到后将此映射写入ARP缓存（10-20min更新一次）。

ARP协议4种典型情况：

  1. 主机A发给本网络上的主机B：用ARP找到主机B的硬性地址；
  2. 主机A发给另一网络上的主机B：用ARP找到本网络上一个路由器（网关）的硬件地址；
  3. 路由器发给本网络的主机A：用ARP找到主机A的硬件地址；
  4. 路由器发给另一网络的主机B：用ARP找到本网络上的一个路由器的硬件地址。
image-20231202091626119

DHCP协议

主机如何获得IP地址？静态配置、动态配置image-20231202091837832
IP地址、子网掩码、默认网关

动态主机配置协议DHCP是应用层协议，使用客户/服务器方式，客户端和服务端通过广播方式进行交互，基于UDP。

DHCP提供即插即用联网的机制，主机可以从服务器动态获取IP地址、子网掩码、默认网关、DNS服务器名称与IP地址允许地址重用，支持移动用户加入网络，支持在用地址续租。

①主机广播DHCP发现报文 “有没有DHCP服务器呀？” 试图找到网络中的服务器，服务器获得一个IP地址
②DHCP服务器厂播DHCP提供报文 “有！”“有！”“有！” 服务器拟分配给主机一个IP地址及相关配置，先到先得
③主机广播DHCP请求报文 “我用你给我的IP地址啦？” 主机向服务器请求提供IP地址
④DHCP服务器厂播DHCP确认报文 “用吧！” 正式将IP地址分配给主机。

ICMP协议

image-20231202095149623

网际控制报文协议ICMP
image-20231202095418132

ICMP差错报告报文(5种）

  1. 终点不可达：当路由器或主机不能交付数据报时就向源点发送终点不可达报文。
    无法交付
  2. 源点抑制：当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道应当把数据报的发送速率放慢。
    拥塞丢数据（取消、基本不会用到）
  3. 时间超过：当路由器收到生存时间TTL=O的数据报时，除丢弃该数据报外，还要向源点发送时间超过报文。当终点在预先规定的时间内不能收到一个数据报的全部数据报片时，就把已收到的数据报片都丢弃，并向源点发送时间超过报文。
    TTL=0
  4. 参数问题：当路由器或目的主机收到的数据报的首部中有的字段的值不正确时，就丢弃该数据报，并向源点发送参数问题报文。
    首部字段有问题
  5. 改变路由（重定向）：路由器把改变路由报文发送给主机，让主机知道下次应将数据报发送给另外的路由器（可通过更好的路由）。
image-20231202100128682

不应发送ICMP差错报文的情况

  1. 对ICMP差错报告报文不再发送ICMP差错报告报文。
  2. 对第一个分片的数据报片的所有后续数据报片都不发送ICMP差错报告报文。
  3. 对具有组播地址的数据报都不发送ICMP差错报告报文。
  4. 对具有特殊地址（如27.0.0.0或0.0.0.0）的数据报不发送ICMP差错报告报文

ICMP询问报文

  1. 回送请求和回答报文
    主机或路由器向特定目的主机发出的询问，收到此报文的主机必须给源主机或路由器发送ICMP回送回答报文。
    测试目的站是否可达以及了解其相关状态。（ping）

  2. 时间请求和回答报文
    请某个主机或路由器回答当前的日期和时间。
    用来进行时钟同步和测量时间。

  3. 掩码地址请求和回答报文（不使用）

  4. 路由器询问和通告报文（不使用）

ICMP的应用
PING 测试两个主机之间的连通性，使用了ICMP回送请求和回答报文。
Traceroute 跟踪一个分组从源点到终点的路径，使用了ICMP时间超过差错报告报文
image-20231202113924874

IPv6

32位IPv4地址空间已分配始尽，CIDR、NAT 治标不治本。IPv6从根本上解决地址耗尽问题。
其他动机：改进首部格式、快速处理/转发数据报、支持QoS。

QoS（QualityofService，服务质量）指一个网络能够利用各种基础技术，为指定的网络通信提供更好的服务能力，是网络的一种安全机制，是用来解决网络延迟和阳塞等问题的一种技术。

IPv6数据报格式
image-20231202115302181
image-20231202115858277

IPv6和IPv4

  1. IP6格地证从32 （4B）扩大到128位（16B）， 更大的地址空间。
  2. IPv6将IPv4的校验和字段彻底移除，以减少每跳的处理时间。
  3. IPv6将IPv4的可选字段移出首部，变成了扩展首部，成为灵活的首部格式，路由器通常不对扩展首部进行检查大大提高了路由器的处理效率。
  4. IPv6支持即插即用 （即自动配置），不需要DHCP协议。
  5. IPV6首长度以须是8B的整数倍，IPV4首部是4B的整数倍。
  6. IPv6只能在主机处分片，IPv4可以在路由器和主机处分片。
  7. ICMPv6：附加报文类型“分组过大”。
  8. IPv6支持资源的预分配，支持实时视像等要求，保证一定的带宽和时延的应用。
  9. IPv6取消了协议字段，改成下一个首部字段。
  10. IPv6取消了总长度字段，改用有效载荷长度字段。
  11. IPv6取消了服务类型字段。

IPv6地址表示形式
一般形式 冒号十六进制记法：4BF5:AA12:0216:FEBC:BA5F:039A:BE9A:2170
压缩形式 4BF5:0000:0000:0000:BA5F:039A:000A:2176➡️4BF5:0:0:0:BA5F:39A:A:2176（将零压缩，同时保证每一部分有数字）
零压缩：一连串连续的0可以被一对冒号取代FF05:0:0:0:0:0:0:B3➡️FF05::B3（双冒号表示法在一个地址中仅可出现一次）

IPv6基本地址类型
①单播 一对一通信 可做源地址+的地址
②多播 一对多通信 可做自的地址
③任播 一对多中的一个通信（通常最近的一台） 可做目的地址

IPv6向IPv4过渡的策略
双栈协议 双协议栈技术就是指在一台设备上同时启用IPv4协议栈和IPv6协议栈。这样的话，这台设备既能和IPv4网络通信，文能和IPv6网络通信。如果这台设备是一个路由器，那么这台路由器的不同接口上，分别配置了IPv4地址和IPv6地址，并很可能分别连接了IPv4网络和IPv6 网络。如果这台设备是一个计算机，那么它将同时拥有IPv4地址和IPv6地址，并具备同时处理这两个协议地址的功能。
隧道技术 通过使用互联网络的基础设施在网络之间传递数据的方式。使用隧道传递的数据（或负载可以是不同协议的数据帧或包。隧道协议将其它协议的数据帧或包重新封装然后通过隧道发送。

image-20231202121436395

路由

image-20231202121728763

RIP协议及距离向量算法

RIP协议
RIP是一种分布式的基于距离向量的路由选择协议，是因特网的协议标准，最大优点是简单。
RIP协议要求网络中母一个路由器都维护从它自一到其他每一个自的网络的唯一最佳距离记录（即一组距离）。
距离：通常为“跳数”，即从源端口到自的端口所经过的路由器个数，经过一个路由器跳数+1。特别的，从一路由器到直接连接的网络距离为1（题目可能规定）。RIP充许一条路由最多只能包含15个路由器，因此距离为16表示网络不可达。
RIP协议只适用于小互联网。
image-20231202122210299

仅和相邻路由器交换信息。
路由器交换的信息是自己的路由表。
每30秒交换一次路由信息，然后路由器根据新信息更新路由表。若超过180s没收到邻居路由器的通告，则判定邻居没了，并更新自己已路由表。

路由器刚开始工作时，只知道直接接的网络的距离（距离为1），接着每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。

经过若干次更新后，所有路由器最终都会知道到达本自治系统任何一个网络的最短距离和下一跳路由器的地址即**“收敛”**。

路由表怎么更新的？
距离向量算法

  1. 修改相邻路由器发来的RIP报文中所有表项
    对地址为X的相邻路由器发来的RIP报文，修改此报文中的所有项目：把“下一跳”字段中的地址改为X，并把所有的“距离”字段+1。
    image-20231202123142957
  2. 对修改后的RIP报文中的每一个项目，进行以下步骤：
    1. R1路由表中若没有Net3， 则把该项目填入R1路由表
    2. R1路由表中若有Net3，则查看下一跳路由器地址：
      若下一跳是×，则用收到的项目替换源路由表中的项目；
      若下一跳不是×， 原来距离比从走的距离远则更新，否则不作处理。
    3. 若180s还没收到相邻路由器X的更新路由表，则把X记为不可达的路由器，即把距离设置为16。
    4. 返回
image-20231202124139720 image-20231202124841509

RIP协议的报文格式
image-20231202124956293

RIP协议好消息传得快， 坏环消息传得慢
RIP的特点：当网络出现故障时，要经过比较长的时间（例如数分钟）才能将此信息传送到所有的路由器 ，“慢收敛”。
bg - 55

image-20231202130416110

OSPF协议及链路状态算法

OSPF协议
开放最短路径优先OSPF协议：“开放”标明OSPF协议不是受某一家厂商控制，而是公开发表的： ：“最短路径优先”是因为使用了Dijkstra提出的最短路径算法SPF。
OSPF最主要的特征就是使用分布式的链路状态协议。
OSPF的特点：
①使用洪泛法向自治系统内所有路由器发送信息，即路由器通过输出端口向所有相邻的路由器发送信息，而每一个相 邻路由器文再次将此信息发往其所有的相邻路由器。广播
最终整个区域内所有路由器都得到了这个信息的一个副本。
②发送的信息就是与本路由器相邻的所有路由器的链路状态（本路由器和哪些路由器相邻，以及该链路的度量/代价一 一费用、距离、时延、带宽等）。
③只有当链路状态发生变化时，路由器才向所有路由器洪泛发送此信息。
最后，所有路由器都能建立一个链路状态数据库，即全网拓扑图

链路状态路由算法
①每个路由器发现它的邻居结点**【HELLO问候分组】，并了解邻居节点的网络地址。
②设置到它的每个居的成本度量metric**。
③构造**【DD数据库描述分组】，**向邻站给出自已的链路状态数据库中的所有链路状态项自的摘要信息。
④如果DD分组中的摘要自已都有，则站不做处理：如果有没有的或者是更新的，则发送【LSR链路状态请求分组】请求自己没有的和比自己更新的信息。
⑤收到邻站的LSR分组后，发送【LSU链路状态更新分组】进行更新。
⑥更新完毕后，邻站返回一个【LSAck链路状态确认分组】进行确认。
只要一个路由器的链路状态发生变化：
⑤泛洪发送【LSU链路状态更新分组】进行更新。
⑥更新完毕后，其他站返回一个【LSAck链路状态确认分组】进行确认。
⑦使用Dijkstra根据自已的链路状态数据库构造到其他节点间的最短路径。

OSPF的区域
为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统再划分为若于个更小的范围，叫做区域。
每一个区域都有一个32位的区域标识符（用点分十进制表示）。
区域也不能太大，在一个区域内的路由器最好不超过200个。

image-20231202132120502

OSPF分组
image-20231202132328424

OSPF其他特点
image-20231202132511851

BGP协议

与其他AS的邻站BGP发言人交换信息。
交换的网络可达性的信息，即要到达某个网络所要经过的一系列AS。
发生变化时更新有变化的部分。
image-20231202132746805

pintu-fulicat.com-1701541999145 image-20231202133437464 image-20231202133547952 image-20231202133744974

三种路由协议比较
image-20231202133906341image-20231202133957145

image-20231202134119259

IP组播

image-20231202134633244 image-20231202134930086 image-20231202135018595 image-20231202135639427

image-20231202140211319

做题映射：前面写01-00-5E,接着写0，接着写ip地址的后23位，转每4位一个16进制数。

image-20231202140704283 image-20231202140859158 image-20231202141130067 image-20231202141327449 image-20231202141428432 image-20231202141548998

移动IP

移动IP技术是移动结点（计算机/服务器等）以固定的网络IP地址，实现跨越不同网段的漫游功能，并保证了基于网络IP的网络权限在漫游过程中不发生任何改变。
image-20231202141903034

image-20231202142128697 image-20231202142526591

网络层设备

路由器
image-20231202142907137

image-20231202143050653 image-20231202143156205

三层设备的区别
路由器 可以互联两个不同网络层协议的网段
网桥 可以互联两个物理层和链路层不同的网段
集线器 不能互联两个物理层不同的网段
image-20231202143321546

路由表与路由转发
image-20231202143625893

传输层

只有主机才有的层次

image-20231203071142816

传输层概述

为应用层提供通信服务
使用网络层的服务

传输层的功能：
⒈传输层提供进程和进程之间的逻辑通信（网络层提供主机之间的逻辑通信）
⒉复用和分用
⒊专输层对收到的报文进行差错检测
⒋传输层的两种协议。

面向连接的传输控制协议TCP：传送数据之前必须建立连接，数据传送结束后要释放连接。不提供厂广播或多播服务。由于TCP要提供可靠的面向连接的传输服务，因此不可避免增加了许多开销：确认、流量控制、计时器及连接管理等。可靠，面向连接，时延大，适用于大文件。

无连接的用户数据报协议UDP：传送数据之前不需要建立连接收到UDP报文后也不需要给出任何确认。不可靠，无连接，时延小，适用于小文件。

传输层的寻址与端口
复用：应用层所有的应用进程都可以通过传输层再传输到网络层。
分用：传输层丛网络层收到数据后交付指明的应用进程。
逻辑端口/软件端口 端口 是传输层的SAP 标识主机中的应用进程
端口号只有本地意义，在因特网中不同计算机的相同端口是没有联系的。
端口号长度为16bit，能表示65536个不同的端口号。
端口号（按范围分）

  • 服务端使用的端口号
    • 熟知端口号 0~1023 给TCP/IP最重要的一些应用程序，让所有用户都知道。
    • 登记端口号 1024~49151 为没有熟知端口号的应用程序使用的。
  • 客户端使用的端口号 49152~65535 仅在客户进程运行时才动态选择。

传输层的寻址与端口
image-20231203075222658
在网络中采用发送方和接收方的套接字组合来识别端点，套接字唯一标识了网络中的一个主机和它上面的一个进程。
套接字Socket= （主机IP地址， 端口号)

UDP协议

UDP只在IP数据报服务 上增加了很少功能，即复用分用和差错检测功能。

UDP的主要特点：
①UDP是无连接的，减少开销和发送数据之前的时延。
②UDP使用最大努力交付，即不保证可靠交付。
③UDP是面向报文的，适合一次性传输少量数据的网络应用。image-20231203075704224
应用层给UDP多长的报文，UDP就照样发送，即一次发一个完整报文。
④UDP无拥塞控制，适合很多实时应用。
⑤UDP首部开销小，8B，TCP20B。

UDP首部格式
image-20231203080255745

UDP校验
image-20231203080509285
image-20231203081243193

TCP

TCP协议特点和TCP报文段

TCP协议的特点
①TCP是面向连接（虚连接）的传输层协议。
②每一条TCP连接只能有两个端点，每一条TCP连接只能是点对点的。
③TCP提供靠交付的服务， 无差错、不关失、不重复、按序到达。可靠有序，不丢不重
④TCP提供全双工通信。
发送缓存 准备发送的数据&已发送但尚未收到确认的数据
接收缓存 按序到达但尚未被接受应用程序读取的数据&不按序到达的数据
⑤TCP面向字节流 TCP把应用程序交下来的数据看成仅仅是一连串的无结构的字节流。

TCP报文段首部格式（重点，尤其大题 字段理解）
image-20231203082318950

image-20231203082840494 image-20231203083234425

TCP连接管理

image-20231203083423278

TCP的连接建立
假设运行在一台主机（客户）上的一个进程想与另一台主机（服务器）上的一个进程建立一条连接，客户应用进程首先通知客户TCP，他想建立一个与服务器上某个进程之间的连接，客户中的TCP会用以下步骤与服务器中的TCP建立一条TCP连接：

image-20231203111531997 :one:客户端发送**连接请求报文段**，无应用层数据。SYN=1（同步位），seq=x(随机)（序号） :two:服务器端为该TCP连接**分配缓存和变量**，并向客户端返回**确认报文段**，允许连接，无应用层数据。SYN=1，ACK=1 （确认位），seg=y(随机)，ack=x+1（期待对方发送接下来发送的报文段的下一个字节） :three:客户端为该TCP连接**分配缓存和变量**，并向服务器端返回确认的确认，可以携带数据。SYN=0（已经连接了）,ACK=1,seq=x+1（相当于前面发送的x，序号加一），ack=y+1（期望的下一个)

SYN洪泛攻击发生在OSI第四层，这种方式利用TCP协议的特性，就是三次握手。攻击者发送 TCPSYN，SYN是TCP三次握手中的第一个数据包，而当服务器返回ACK后，该攻击者就不对其进行再确认，那这个TCP连接就处于挂起状态，也就是所谓的半接状态，服务器收不到再确认的话，还会重复发送ACK给攻击者。这样更加会浪费服务器的源。攻击者就对服务器发送非常大量的这种TCP连接，由于每一个都没法完成三次握手，所以在服务器上，这此 TCP连接会因为挂起状态而消耗CPU和内存，最后服务器可能死机，就无法为正常用户提供服务了。方法：SYN cookie

TCP的连接释放
参与一条TCP连接的两个进程中的任何一个都能终止该连接，连接结束后，主机中的“资源”（缓存和变量）将被释放。
image-20231203111752581
1️⃣客户端发送连接释放报文段，停止发送数据，主动关闭TCP连接。
FiN=1，seg=u（序号）
2️⃣服务器端回送一个确认报文段，客户到服务器这个方向的连接就释放了一一半关闭状态。
ACK=1,seq=V（取决之前发送的序号）,ack=u+1（期望的下一个报文段）
3️⃣服务器端发完数据，就发出连接释放报文段，主动关闭TCP连接。
FIN=1，ACK=1， seq=w（不一定是v+1，中间服务器还可发送数据），ack=u+1（A没有发送，所有还是）
4️⃣客户端回送一个确认报文段，再等到时间等待计时器设置的2MSL（最长报文段寿命）后，连接彻底关闭。
ACK=1, seq=u+1,ack=w+1

TCP可靠传输

网络层 提供尽最大努力交付，不可靠传输

传输层 使用TCP实现可靠传输

可靠 保证接收方进程从缓存区读出的字节流与发送方发出的字节流是完全一样的。

TCP实现可靠传输的机制：1.校验（与UDP校验一样，增加伪首部）2.序号3.确认4.重传

序号
一个字节占一个序号。
序号字段指的是一个报文段第一个字节的序号。
image-20231203113040393

确认
image-20231203113337867

image-20231203113435129

重传
确认重传不分家，TCP的发送方在规定的时间内没有收到确认就要重传已发送的报文段。超时重传

TCP采用自适应算法，动态改变重传时间RTTs（加权平均往返时间）。

image-20231203113812429

image-20231203114143410

TCP流量控制（重点）

流量控制：让发送方慢点，要让接收方来得及接收。
TCP利用滑动窗口机制实现流量控制。
在通信过程中，接收方根据自己接收缓存的大小，动态地调整发送方的发送窗口大小，即接收窗口rwnd（接收方设置确认报文段的窗口字段来将rwnd通知给发送方），发送方的发送窗口取接收窗口rwnd和拥塞窗口cwnd的最小值。
image-20231203115738265

TCP为每一个连接设有一个持续计时器，只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器。
若持续计时器设置的时间到期，就发送一个零窗口探测报文段。 接收方收到探测报文段时给出现在的窗口值。
若窗口仍然是0，那么发送方就重新设置持续计时器。

TCP拥塞控制（重点）

出现拥塞的条件：对资源需求的总和>可用资源
网络中有许多资源同时呈现供应不足➡️网络性能变环➡️网络吞吐量将随输入负荷增大而下降
拥塞控制：防止过多的数据注入到网络中。全局性

拥塞控制四种算法慢开始 拥塞避免 快重传 快恢复

假定：
1.数据单方向传送，而另一个方向只传送确认
2.接收方总是有足够大的缓存空间，因而发送窗口大小取决于拥塞程度
（发送窗口=Min｛接收窗口rwnd，拥塞窗口cwnd｝）
接收窗口 接收方根据接受缓存设置的值，并告知给发送方，反映接收方容量。
拥塞窗口 发送方根据自已估算的网络拥塞程度而设置的窗口值，反映网络当前容量。

bg - 5

收到确认就翻倍

image-20231203122258281

应用层

image-20231203122815806

网络应用模型

应用层概述
应用层对应用程序的通信提供服务。
应用层协议定义：
应用进程交换的报文类型，请求还是响应？
各种报文类型的语法，如报文中的各个字段及其详细描述。
字段的语义，即包含在学段中的信息的含义
进程何时、如发送报文，以及对报文进行响应的规则

应用层的功能：文件传输、访问和管理、电子邮件、虚拟终端、查询服务和远程作业登录。

客户/服务器模型（Client/Server）
服务器：提供计算服务的设备
1.永久提供服务
2.永久性访问地址/域名
客户机：请求计算服务的主机
1.与服务器通信，使用服务器提供的服务
2.间歇性接入网络
3.可能使用动态IP地址

应用：Web，文件传输FTP，远程登录，电子邮件

P2P 模型 （Peer-to-peer）
不存在永远在线的服务器
每个主机既可以提供服务，也可以请求服务
任意端系统/节点之间可以直接通讯
节点间歇性接入网络
节点可能改变IP地址
可扩展性好
网络健壮性强

域名解析系统DNS

根：例com后面没写的点
顶级域名

  • 国家顶级域名cn,us,uk
  • 通用顶级域名 com,net,org,gov,int（国际组织）, aero（航空）,museum,travel
  • 基础结构域名/反向域名arpa

二级域名

  • 类别域名 ac,com,edugov,mil,net,org
  • 行政区域名 用于我国各省、自治区、直辖市bj.js

三级域名

四级域名

image-20231203124916719 image-20231203125841799

域名解析过程
image-20231203130014722

image-20231203130231060

文件传输协议FTP

文件传送协议FTP（File Transfer Protocol）提供不同种类主机系统（硬、软件体系等都可以不同）之间的文件传输能力。
简单文件传送协议TFTP（Trivial File Transfer Protocol）（可尝试自己实现）

拷贝：上传、下载

FTP服务器和用户端
FTP是基于客户/服务器（C/S）的协议。
用户通过一个客户机程序连接至在远程计算机上运行的服务器程序。
依照FTP协议提供服务，进行文件传送的计算机就是FTP服务器。
连接FTP服务器，遵循FTP协议与服务器传送文件的电脑就是FTP客户端。

FTP工作原理
登陆 ftp地址 用户名&密码（匿名登陆）
互连网中有很大一部分FTP服务器被称为“匿名”（Anonymous）FTP服务器。这类服务器的目的是向公众提供文件拷贝服务，不要求用户事先在该服务器进行登记注册，也不用取得FTP服务器的授权。 Anonymous（匿名文件传输）能够使用户与远程主机建立连接并以匿名身份从远程主机上拷贝文件，而不必是该远程主机的注册用户。用户使用特殊的用户名“anonymous"登陆FTP服务，就可访问远程主机上公开的文件。
FTP使用TCP实现可靠传输。
服务器进程

  • 1个主进程
  • n个从属进程
image-20231203131732290 image-20231203131742229

电子邮件

image-20231203132024110 image-20231203132431066 image-20231203132510306

简单邮件传送协议SMTP
SMTP规定了在两个相互通信的SMTP进程之间应如何交换信息。
负责发送邮件的SMTP进程就是SMTP客户，负责接收邮件的进程就是SMTP服务器。
SMTP规定了14条命令（几个字母）和21种应答信息（三位数字代码+简单文字说明）。
image-20231203132659986
image-20231203133028317
image-20231203133131782
image-20231203133207582

邮局协议POP3
image-20231203133351696

网际报文存取协议IMAP
image-20231203133454791

基于万维网的电子邮件
image-20231203133602865

image-20231203133612769

万维网和 HTTP协议

image-20231203134004741 image-20231203134258642 image-20231203134523971 image-20231203134649143 image-20231203134832311 image-20231203135054916

数据结构

第一章

数据类型

image-20231206043716734 image-20231206044652763 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main()
{
    int a;
    int b = 10;
    a = 11;
    cout<<"a: "<<a<<endl;//11
    cout<<"b: "<<b<<endl;//10
    
    int *p = &a;
    cout<<"*p: "<<*p<<endl;//11
    *p = *p +1;
    cout<<"a: "<<a<<endl;//12
    
    p = NULL;
    cout<<"p: "<<p<<endl;//0
    return 0;
}

image-20231206045833298q

image-20231206050212476 image-20231206050522873 image-20231206050855743

控制流

image-20231206051037094 image-20231206051558175

函数

image-20231206052435445 image-20231206053128474 image-20231206053313526 image-20231206053520435

逻辑结构与存储结构

image-20231206053945413 image-20231206054519449 image-20231206054627960

算法分析基础

时间复杂度、空间复杂度

定义:如果存在正常数c 和 n0使得当 N≥n0时,T(N)≤cf(N),则记为 T(N)=O(f(N));\text{定义:如果存在正常数}c\text{ 和 }n_0\text{使得当 }N\geq n_0\text{时},T(N)\leq cf(N),\quad\text{则记为 }T(N)=O(f(N));

定义:如果存在正常数c 和 n0 使得当 N≥n0 时 ,T(N)≥cg(N),则记为 T(N)=Ω(g(N));\text{定义:如果存在正常数}c\text{ 和 }n_0\text{ 使得当 }N\geq n_0\text{ 时 },\quad T(N)\geq cg(N),\quad\text{则记为 }T(N)=\Omega(g(N));

image-20231206055856438

定义:T(N)=Θ(h(N)), 当且仅当 T(N)=O(h(N)) 且T (N)=Ω(h(N));\text{定义:}T(N)=\Theta(h(N)),\text{ 当且仅当 }T(N)=O(h(N))\text{ 且T }(N)=\Omega(h(N));

image-20231206060309197

定义:如果T(N)=O(p(N))且T(N)≠Θ(p(N)),则T(N)=o(p(N))。\text{定义:如果}T(N)=O(p(N))\text{且}T(N)\neq\Theta(p(N)),\quad\text{则}T(N)=o(p(N))。

image-20231206060405211

简化问题：把加、减、乘、除、比较和赋值都视作耗时相同的运算

最坏、最好与平均情况

对于输入数据，所执行的基本操作次数最多的情况，为最坏情况。如果没有特殊说明，我们要求的都是最坏情况。

image-20231206061255637

一次循环运行时间是循环内语句的运行时间乘以循环次数；

嵌套循环运行时间为最内层语句执行次数乘以总循环次数；

并列的两个循环运行时间与执行次数数量级大的那个相同；

递归函数时间复杂度分析

image-20231206061944187 image-20231206062144954 image-20231206062455349

T(n)=O(nlog2n)T(n)=O(nlog_2n)

image-20231206062707672 image-20231206062931939 image-20231206063015151 image-20231206063049593 image-20231206063243271 image-20231206063309182 image-20231206063350612 image-20231206063507489 image-20231206063551391 image-20231206063642997

补充讲解一些常考题型

image-20231206064006873 image-20231206064105308 image-20231206064451773

第二章线性表

线性表的逻辑结构

线性表示是具有相同特性数据元素的有限序列。
相同特性：把同一类事物归类，方便批量处理。
有限：表中元素个数为 n，n有限大，n 可以为0。
序列：表中元素排成一列，体现了一对一的逻辑特性（每个元素有则仅有一个前驱和一个后继）。

线性表的存储结构

image-20231206081624746 image-20231206081906605 image-20231206082033039 image-20231206082654802

image-20231206082759476image-20231206082934007

image-20231206083021677 image-20231206083052829 image-20231206083144646 image-20231206083302591 image-20231206083342458 image-20231206083404093 image-20231206083520227 image-20231206084335772 image-20231206084440283

特性对比问题

在顺序表中插入和删除元素可能会导致移动大量元素的连带操作（插入或删除操作发生在表尾位置例外），而链表不会。

在单链表中找到任意一个结点的位置不像顺序表那么简单，因为顺序表支持随机存取（任意存取），而单链表不支持；

为了尽可能弥补上一条中单链表的不足，开发了双链表、循环单链表和循环双连表等存诸结构，这些存诸结构可以在仅知道链表中任一个结点地址的情况下推知其余所有结点的地址，但仍然不支持随机存取。

有时候还会给链表定义一个额外的指针，最常见的是表尾指针，它指向链表中最后一个结点。可以借助它来提高某些常用操作的执行效率。

线性表采用顺序存储结构，必须占用一片连续的存储单元而采用链式存储结构则不需要这样；

从表整体来看，一般顺序表存储空间利用率低于链表；而从单个存储单元来看，顺序表存储空间利用率要高于链表

image-20231206090228555 image-20231206090428016 image-20231206090552374 image-20231206090647705 image-20231206090949859

image-20231206091437791

image-20231206091612693 image-20231206091648532 image-20231206091743081 image-20231206091928722 image-20231206092143727 image-20231206092523519 image-20231206092741405

移动次数计算和静态链表

image-20231206093136095

image-20231206093200739 image-20231206093335054 image-20231206093825278 image-20231206094026894 image-20231206094155922 image-20231206094417508 image-20231206094808072 image-20231206094923184 image-20231206095153463

插入删除

单链表结点插入
image-20231206095733287

单链表结点删除
image-20231206095924596

插入特殊情况、删除特殊情况
给链表设置头结点，可以使得在第一个数据结点之前插入一个新结点和删除第一个数据结点的操作同表中部结点的这些操作统一起来，方便写代码；
带头结点的链表，其头指针值不随操作而改变，可以减少错误。

双链表结点插入
image-20231206100550680

双链表结点删除
image-20231206100731315

元素插入算法
image-20231206101012165

1
2
3
4
5
6
7
8
9
10
11
12
13
int sqList[maxSize] = {1,2,3,……,n};
int length = n;

int insertElem(int sqList[], int &length, int p, int e)
{
    if(p<0 || p>length || length==maxSize)//不合法条件
        return 0;
    for(int i = length-1; i >= p; --i)
        sqList[i+1] = sqlList[i];
    sqList[p] = e;
    ++length;
    return 1;
}

元素删除算法
image-20231206101843527

1
2
3
4
5
6
7
8
9
10
int deleteElem(int sqList[]，int &length, int p, int &e)
{
    if（p<0 || p>length-1)
        return 0;
    e = sqList[p];
    for（int i= p; i<length-l; ++i)
        sqList[i] = sqList[i+l];
    --length;
    return 1;
}
image-20231206102314076 image-20231206102757071 image-20231206103039126 image-20231206103411555 image-20231206103547152 image-20231206104039709 image-20231206104243502

image-20231206104448599image-20231206104523936

image-20231206104615363

image-20231206104914778

建表

顺序表建表算法代码

1
2
3
4
5
6
7
8
9
10
11
int A[maxsize];
int length;//无符号整形好一些
int createList(int A[], int &length)
{
    cin>>length;
    if(length > maxsize)
        return 0;
    for（inti=o; i<length; ++i)
        cin>>A[i];
    return l;
}

链表建表算法代码
尾插法（头结点，单链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void createLinkListR(LNode *&head)
{
    head=(LNode*)malloc(sizeof(LNode));//考研视为不用考虑失败
    head->next = NULL;//好习惯
    LNode *p NULL, *r = head;//p新结点，r始终指向尾结点
    int n;
    std::cin>>n；//scanf("%d",&n);
    for(int i = o；i<n; ++i) 
    {
        p= (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
        std::cin>>p->data;//scanf("%d",&(p->data)）;
        p->next = r->next;//和中部插入没有区别，对尾插可删
        r->next =p;
        r= p;
    }
}

头插法（头结点，单链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void createLinkListH(LNode *&head)
{
    head=(LNode*)malloc(sizeof(LNode));//考研视为不用考虑失败
    head->next = NULL;//好习惯
    LNode *p NULL;//p新结点
    int n;
    std::cin>>n；//scanf("%d",&n);
    for(int i = o；i<n; ++i) 
    {
        p= (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
        std::cin>>p->data;//scanf("%d",&(p->data)）;
		p->next=head->next;
        head->next=p;
    }
}
image-20231206110855077 image-20231206110932961 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void createLinkNosameElem(LNode *&head)
{
    head= (LNode*)malloc(sizeof(LNode));
    head->next = NULL;
    LNode *p;
    int n;
    char ch;
    std::cin>>n;
    for(int i =o; i <n; ++i)
    {
        std::cin>>ch;
        p = head->next;
        while (p!=NULL){
            if (p->data==ch)
                break;
            p=p->next;
        }
        if(p == NULL)
        {
            p=(LNode*)malloc(sizeof(LNode));
            p->data=ch;
            p->next = head->next;
            head->next =p;
        }
    }
}

归并

顺序表归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void mergaearray(int a[],int m,int b[],int n,int c[])
{
    int i=0,j=0;
    int k = 0;
    while (i<m&&j<n)
    {
        if (a[i] <b[i])
            c[k++] = a[i++];//c[k] = a[i];k++;i++;
        else
            c[k++] = b[j++];
    }
    while (i<m)
        c[k++] = a[i++];
    while (j<n)
        c[k++] = b[j++];
}

链表归并

尾插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void merge(LNode *A, LNode *B, LNode *&C)//c 指针的引用型
{
    LNode *p=A->next;
    LNode *g=B->next;
    LNode *r;//标记尾部
    C=A;
    C->next = NULL;
    free(B);
    r= C;
    while(p!=NULL&&q!=NULL)
    {
        if(p->data<=q->data)
        {
            r->next = p;
            p=p->next;
            r = r->next;
        }
        else{
            r->next=q;
            q= q->next;
            r = r->next;
        }
    }
    if(p!=NULL) r->next = p;
    if(q!=NULL) r->next = q;
}

头插（可得逆序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void mergeR(LNode *A, LNode *B, LNode *&C)//c 指针的引用型
{
    LNode *p=A->next;
    LNode *g=B->next;
    LNode *s;//标记
    C=A;
    C->next = NULL;
    free(B);
    while(p!=NULL&&q!=NULL)
    {
        if(p->data<=q->data)
        {
           	s=p;p=p->next;
            s->next=C->next;C->next=s;
        }
        else{
           	s=q;q=q->next;
            s->next=C->next;C->next=s;
        }
    }
    while(p!=NULL) 
    {
        s=p;
        p=p->next;
        s->next=C->next;C->next=s;
    }
    while(q!=NULL)
    {
        s=q;q=q->next;
        s->next=C->next;C->next=s;
    }
}

逆置

顺序表

1
2
3
4
5
6
for(int i = left,j = right;i<j;  ++i，--j)
{
    temp = a［i]; 
    a[i] = a［j]; 
    a［j] = temp;
}

链表

1
2
3
4
5
6
7
8
//逆置p->next到q之间的结点
while(p->next !=q)
{
    t = p->next;  
    p->next =t->next; 
    t->next=q->next;
	q->next = t;
}
image-20231206120940403

image-20231206125531597image-20231206125547616

image-20231206121118459 image-20231206125638122 image-20231206125702781 image-20231206125718586 image-20231206125732552 image-20231206125828455 image-20231206130128438 image-20231206130213203 image-20231206130251658 image-20231206130322295 image-20231206130412696

例（1234567）左边逆置一下（21），右边逆置一下（76543），整体逆置一下（2176543->3456712）

image-20231206130613456 image-20231206131344856

取最值

image-20231206222118477image-20231206222234128
image-20231206222323671image-20231206222427306

image-20231206222546922 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void maxFirst(DLNode *head)
{
    DLNode *p=head->rlink, *q=p;//p扫描指针 q找到的最大结点指针
    int max =p->data;
    //找最值：
    while (p != NULL)
    {
        if (max < p->data)
        {
            max = p->data; 
            q= p;
        }
        p = p->rlink;
    }
    //"删除"：
    DLNode *l = q->llink, *r = q->rlink;//保存最大结点的前驱和后继
    l->rlink = r;//将q的后面接到r上
        if (r != NULL)
        {
           r->llink=l; //将q的前面接到r前
        }
    //插入：
    q->llink = head;
    q->rlink = head->rlink;
    head->rlink =q;
    q->rlink->llink = q;
}
image-20231206224159908 image-20231206224455284 image-20231206224527514

划分

image-20231206225204744 image-20231206225231444 image-20231206225703770 image-20231206225737836 image-20231206230002886

数组中任意作为枢轴
image-20231206230124009image-20231206230539001

image-20231206230837021 image-20231206231736953 image-20231206232141404 image-20231206232302951 image-20231206232319471

第三章栈和队列

栈

栈是一种只能在一端进行插入或删除操作的线性表。
线性表：栈的逻辑结构属于线性表，只不过在操作上加了一些约束。
一端：可以插入或者册删除元素的一端叫栈顶，另一端叫栈底。

image-20231207075645509

栈存储结构
image-20231207080102949
top ==-1 为真，则栈空；top==maxsize - 1 为真，则栈满

image-20231207080334480 image-20231207080416597

head->next==NULL 为真，则栈空；只要有足够的内存，栈就不会满。

队列

队列是一种插入元素只能在一端能进，册删除元素只能在另一端进行的线性表。
线性表：队列的逻辑结构属于线性表，只不过在操作上加了一些约束。
一端：可以插入元素的一端叫队尾 (Rear）。
另一端：另一端可以删除元素的一端叫队头 (Front）。

队列存储结构
image-20231207081446508

image-20231207081640141 image-20231207081838665

队空： front==rear为真。队满： front==(rear + 1) % maxsize为真(rear往前一步等于front)。

image-20231207082547110

fornt的next为null时队空。

image-20231207082650943

front为null时队空。

输出序列

image-20231207082836972image-20231207083107188

image-20231207083154614image-20231207083256385

image-20231207083504140 image-20231207083659047 image-20231207083812308 image-20231207084204763 image-20231207084315074 image-20231207085933629 image-20231207090024556

3最后一个入栈，第一个出栈，那其余出栈元素不可能有1、2这个顺序。

image-20231207090357866 image-20231207090503901

表达式转换

image-20231207091014871

中转其他
我：转换时，中缀转其他时，按照运算规则将整体分成三个部分，将这三个部分进行转换，再在个部分递归操作。
他：不停在每一个运行上加括号，将括号里的操作符根据要转换的目标提到括号前或后，最后删除括号。
image-20231207092209852

其他转中
（后缀）从左往右扫描，（前缀）从右往左扫描遇到两个操作数和一个操作符，用括号括起来，将操作符放到操作数中间，继续扫描。
image-20231207092640326

前后互转
同样括起来，但操作符不是放中间而是根据转换目标放在左或右，继续扫描。
image-20231207092919521

用栈实现表达式转换

中缀转后缀：
从左到右依次扫描中缀表达式，遇到操作数就直接写出来（顺序是从前往后写），遇到运算符时，判断当前运算符与栈顶运算符的优先级，如果当前运算符的优先级小于或者等于栈顶元素运算符的优先级，就把栈顶运算符出栈，并将其写入当前结果表达式中（这个比较是个循坏，依次把当前元素和新的栈顶元素进行比较，如果还是小于等于则继续出栈，直到比较的是结果是大于栈顶运算符优先级则把当前运算符出栈）。
对于表达式中含有括号，当遇到左括号则直接入栈，当栈顶元素是左括号时则扫描的元素全入栈，当扫描的运算符是右括号时则执行一系列出栈操作，把当前栈中从栈顶到左括号的元素全部出栈，并将其写入结果表达式中，把括号丢弃。
最后当扫描完中缀表达式中所有字符时，此时若栈中还有剩余的运算符，则将其全部出栈并写入结果表达式中。
image-20231207102615671

中缀转前缀：
和转前转前缀式一个相反的过程，这个需要从右往左依次扫描。写结果表达式是从后往前写。
遇到右括号入栈遇到左括号把它们之间的元素全部出栈。还有一点，在转后缀时，如果此时运算符的优先级小于或者等于栈顶算符优先级则出栈，而在转前缀时是小于。
image-20231207102815709

后缀转前缀：每次扫描到一个运算符时，就把这个运算符所对应的两个子表达式移到运算符后面。（这个移动的过程我们借助栈来实现）（从左往右，扫描到操作数入栈，扫描到操作符时，将栈顶前两个操作数出栈（先出在右，后出在左）与操作符结合成前缀形式，放入栈中作为一个操作数，继续扫描）

image-20231207095046742 image-20231207095533626

用栈实现表达式求值

用栈求中缀表达式值

  1. 建立两个栈，其中左边的栈，暂存操作数（记为S1）；右边 的栈，暂存运算符（记为S2）。从左到右，扫描中缀表达式。
  2. 遇到操作数，则入S1栈；遇到左括号，则入S2栈；如遇到运算符，则准备入S2栈。入栈前须进行如下判断：
    1. 若S2栈为空或S2栈的栈顶为左括号，则运算符可直接入S2栈。
    2. 若当前运算符的优先级大于栈顶运算符，则可入S2栈。
    3. 若当前运算符的优先级小于等于栈顶运算符，则现将栈顶运算符出栈（s1要出栈2个进行运算），直到当前运算符的优先级大于栈顶运算符，即可如S2栈。
    4. 若运算符为右括号，则将S2中从栈顶到左括号的所有运算符均出栈（s1要出栈进行运算）。

**总结：**S2栈每出栈一个运算符，则S1栈出栈两个操作数进行一次运算，其中先出栈的操作数位于运算符右边，后出栈的运算符位于运算符左边，计算出结果并入栈S1。当整个中缀表达式全部扫描完后，S2栈中依旧有运算符，则将所有运算符出栈，最后在S1栈顶的数即为整个表达式的求值结果。
image-20231207105959653

用栈求后缀表达式值

从左往右扫描，操作数入栈，遇到运算符出栈2个运算入栈，继续。

用栈求前缀表达式值

从右往左扫描，操作数入栈，遇到运算符出栈2个运算入栈（先出在左，后出在右），继续。
image-20231207111700559

配置问题

正常配置(f没有指向元素，r有指向元素)
队空：front == rear 为真。
入队：rear = (rear + 1)%maxsize; queue[rear]=x;
出队：front = （front + 1)%maxsize; x=gueue[front];
队满： front== (rear + 1)%maxsize 为真。

队中元素有多少个？
image-20231207112517356

非正常配置（f有指向元素，r没有指向元素）
队空：front ==rear 为真。
入队: queue[rear] = x; rear= (rear + 1)%maxsize;
出队：x=queue[front]; front=（front+1)%maxsize;
队满： front== (rear + 1)%maxsize 为真。

队中元素有多少个？
image-20231207112953690

非正常配置（f和r都有指向元素）
队空：front==(rear+1）%maxsize为真。
入队：rear= (rear + 1)%maxsize; queue[rear] = x;
队满： front==(rear+2)%maxsize 为真。

队中元素有多少个？
image-20231207113417340

image-20231207113844009

双端队列

image-20231207114126833 image-20231207114143718 image-20231207114259102 image-20231207114415584 image-20231207114633576 image-20231207114840585 image-20231207115000359 image-20231207115135552 image-20231207115412501

栈的扩展

共享栈

image-20231207115904643 image-20231207115953764 image-20231207120159444

top[o]+1 l== top［1］为真，栈满。

用栈模拟队列

image-20231207120802641

括号匹配和计算

括号匹配

image-20231207120852272 image-20231207121421177 image-20231207121443050

计算问题

image-20231207121615570 image-20231207121749348 image-20231207122049342

第四章串

串是特殊的线性表image-20231207122407265

image-20231207122513773

maxSize为已经定义的常量，表示串的最大长度；str数组长度定义为maxSize+1，是因为多出一个"\0"作为结束标记。

image-20231207122924514

赋值操作

image-20231211075203466 image-20231211075224395

取串长度

1
2
3
4
int strLength(Str str)
{
    return str.length;
}

串比较

设两串C1和C2中的待比较字符分别为a和b：
*如果a的ASCll码小于b的ASCll码，则返回C小于C2标记（一个负数）;
*如果a的ASCll码大于b的ASCll码，则返回C1大于C2标记（一个正数）；
*如果a的ASCII码等于b的ASCII码，则按照之前的规则继续比较两串中下一对字符；
*经过上述步骤没有比较出C和C2大小的情况下，先结束的串为较小串，两串同时结束则返回两串相等标记（o）。

1
2
3
4
5
6
7
int strCompare(Str s1, Str s2)
{
    for(int i=0;i<s1.length&&i<s2.length;++i)
        if (s1.ch[i]!=s2.ch[i])
            return sl.ch[i] - s2.ch[i];
    return sl.lenath-s2.length;
}

串连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int concat(Str& str,Str strl,Str str2)
{
    if(str.ch)
    {
        free(str.ch);
        str.ch=NULL;
    }
    str.ch=(char*)malloc(sizeof(char)*(strl.length+str2.length+l));
    if(!str.ch) return 0;
    int i=0;
    while(i<str1.length)
    {
        str.ch[i]=str1.ch[i]; 
        ++i;
    }
    int j=0;
    while(j<=str2.length)
    {
        str.ch[i+j]=str2.ch[j];
        ++j;
    }
	str.length=str.length+str2.length;
    return 1;
}

求子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int substring(Str& substr,Str str,int pos,int len)
{
    if(pos<o||pos>=str.length||len<0||len>str.length-pos)
		return 0;
    if(substr.ch)
    {
        free(substr.ch);
        substr.ch=NULL;
    }
    if(len==0)
    {
        substr.ch=NULL;
        substr.length=0; 
        return 1;
    }else
    {
        substr.ch=(char*)malloc(sizeof(char)*(len+l));
        int i=pos;
        int j=0;
        while(i<pos+len)
        {
            substr.ch[j]=str.ch[i];
            ++i; ++j;
        }
        substr.ch[j]='\0';
        substr.length=len;
        return 1;
    }
    
}

清空串

1
2
3
4
5
6
7
8
9
10
int clearstring(Str& str)
{
    if(str.ch)
    {
        free(str.ch);
        str.ch=NULL;
    }
    str.length=0; 
    return 1;
}

KMP算法

image-20231211082813244 image-20231211083025254 image-20231211084519225 image-20231211085837331 image-20231211090325046 image-20231211091217908 image-20231211091313517 image-20231211091457735 image-20231211091542685 image-20231211091655955 image-20231211091822330

求解next数组

image-20231211083649405 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getNext(Str substr,int next[])
{
    int j = 1, t;//j当前主串正在匹配的字符位置，也是next数组的索引
    next[l] = 0;
    while(j<substr.length)
    {
        if (t==0 ||substr.ch[j]==substr.ch[t])//如果前缀后一个字符和后缀后一个字符相同
        {
            next[j+1] = t+1; 
            ++t; ++j;
        }else{
            t = next[t];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int KMP (Str str, Str substr,int next[])
{
    int i=1,j=1;
    while（i< str.length &&j<=substr.length)
    {
        if(j==0||str.ch[i]==substr.ch[j])
        {
            ++i; ++j;
        }else{
            j=next[j];
        }
    }
    if(j>substr.length)
        return i-substr.length;//比较成功后，返回位置
    else
        return 0;
}

改进KMP算法

image-20231211093149612 image-20231211093216648 image-20231211093455003 image-20231211093711784 image-20231211093746917

求解nextval数组

image-20231211093811062

image-20231211094047173

第五章

数组

image-20231211094604087 image-20231211094700921 image-20231211094744007 image-20231211094905697 image-20231211094924523 image-20231211095122347

矩阵

image-20231211095826267 image-20231211095925817 image-20231211100037735 image-20231211100250795 image-20231211100458612 image-20231211101010876

三元组表示法

image-20231211101456871

三元组表示法

image-20231211101706420 邻接表表示法

邻接表表示法

image-20231211102103719

十字链表表示法

image-20231211102617848

广义表

image-20231211103609368 image-20231211103941473 image-20231211104156658 image-20231211104402395 image-20231211104641259 image-20231211104712624 image-20231211104743480

第六章二叉树

树

image-20231211105541598

结点：A1-A6

结点的度 ：结点引出分支的个数

树的度：最大结点的度

叶子节点：度为0

A2、A3、A4的双亲为A1。
A2、A3、A4为A1的孩子。

A1、A2为A5的祖先。
A2～A6为A1的子孙。

A2、A3、A4互为兄弟。
A6和A7互为堂兄弟。

树的高度（深度）为3；（从上往下）
A1的深度为1，高度为3。（从下往上）

image-20231211105920278

image-20231211110920027

顺序存储结构

image-20231211111336102

双亲存储结构

image-20231211111427335

链式存储结构

image-20231211111833898

还有一种

添加一些约束成为二叉树

image-20231211112102385

image-20231211112137427

image-20231211112159451

可将满二叉树看作特殊的完全二叉树

image-20231211112547112 image-20231211112828530 image-20231211112946855

image-20231211113225676

性质

image-20231211113507032 image-20231211113549311 image-20231211113722219 image-20231211113840296 image-20231211113911801

顺序存储结构

image-20231211114433072

链式存储结构

image-20231211114813875

二叉链表存储结构

image-20231211114916380 image-20231211115151271

树的孩子兄弟存储结构

image-20231211115322402

树（森林）与二叉树的互相转换

树与“二叉树”的互相转换

image-20231211115749551image-20231211115812451image-20231211115831254

image-20231211120016421image-20231211120045155image-20231211120056190

森林与“二叉树”的互相转换

image-20231211120305924 image-20231211120359604 image-20231211120827217 Snipaste_2023-12-03_07-25-24-overlay

遍历

image-20231211133655994

不同的时机（第一次、第二次、第三次）对结点进行访问可得不同便利序列

image-20231211134153993image-20231211134256499image-20231211134336047

image-20231211134442232 image-20231211134508787 image-20231211134734154 image-20231211135023404 image-20231211135141536 image-20231211135202547

image-20231211135255787image-20231211135321129

image-20231211135426514

递归

image-20231212093824853

三个位置是前中后遍历

二叉树非递归遍历

先序遍历非递归化
用栈模拟原先的递归。
入栈根节点，栈顶出栈，将出栈结点的右结点、左结点入栈，继续出栈。
image-20231212100159244

后序遍历非递归化
image-20231212100641162
image-20231212100812527
用栈模拟原先的递归。
入栈根节点，栈顶出栈入辅助栈，将出栈结点的左结点、右结点入栈，继续出栈入辅助栈。最后辅助栈出栈的后序遍历。
image-20231212101158403

中序遍历非递归化
从根节点开始往左走，途径入栈，直到没有左结点，栈顶出栈访问。若出栈结点没有右孩子，则继续出栈；若有右孩子，则入栈，将其当作根节点继续。
image-20231212102453330

其他遍历算法

二叉树层次遍历
借助队列。
根节点入队，出队访问，将左右结点入队（有则入，无则不入）。继续出队。

image-20231212103200543

树的深度优先遍历
image-20231212103841119
image-20231212104003335
image-20231212104157638
image-20231212104254510

树的广度优先 （层次） 遍历
还是借助队列
image-20231212104453175

中序线索二叉树

线索二叉树：在二叉树中，对每一个结点直接引出指向前驱结点或后驱结点的路径（这个过程就是把二叉树线索化）
结点有左空指针则指向其前驱，有右空指针则指向其后继。
image-20231212105556656
image-20231212105859570
image-20231212105932634

image-20231212110253811

第一个结点：一直往左走
最后一个结点：一直往右走
前驱：如果有且左指针为线索，则线索所指结点就是前驱结点；如果左指针不是线索，从这个结点往左走一步，然后一直往右
后继：如果有且右指针为线索，则线索所指结点就是后继结点；如果右指针不是线索，从这个结点往右走一步，然后一直往左
image-20231212112158763

前序线索二叉树

image-20231212112314360 image-20231212112818554

第一个结点：根节点
如果左不空且不是线索，则左指针指向后继；如果是左是线索，则指向前驱。
如果左空且右不空，不管是不是线索，右指针都指向后继。

执行前序遍历
image-20231212114040193

后序线索二叉树

image-20231212114115048 image-20231212114402946 image-20231212114918473 image-20231212120310791

三种线索二叉树的比较：主要考找后继，中序比较完美。

image-20231212120917010

哈夫曼树

image-20231212121410703

先挑选最小的次小的组成树，将树作为下次拼接右子树，再挑选剩余最小的作为左子树，继续将组成的树作为右子树，继续挑选左子树。（每次选两个权值最小的结点组成新的结点，权相加）

image-20231212121532772

根据0、1在树上行走得出字符。

image-20231212122422608

路径：路径是指从树中一个结点到另一个结点的分支所构成的路线。
路径长度：路径长度是指路径上的分支数目。
树的路径长度：树的路径长度是指从根到每个结点的路径长度之和。
带权路径长度：结点具有权值，从该结点到根之间的路径长度乘以结点的权值，就是该结点的带权路径长度。如：E的带权路径长度=4×2（权为2 ）=8image-20231212122714175
树的带权路径长度（WPL）：树的带权路径长度 (WPL）是指树中所有叶子结点的带权路径长度之和。如WPL=1x5+3x2+2x3+2x4+1x4=29image-20231212122812383

哈夫曼二又树的特点
权值越大的结点，距离根结点越近。
树中没有度为1的结点。这类树又叫作正则 (严格）二叉树。
树的带权路径长度最短。

哈夫曼n叉树
image-20231212123302234
每次选三个最小的
image-20231212123432654
例：无法组成三叉树，补上权为0的结点

image-20231212123543629

二叉树的确定（根据特定序列确定二叉树）

image-20231212125104012 image-20231212125758564 image-20231212130056939 image-20231212130147483 image-20231212125951492

子序列不连续，所以挑出来并保持顺序。

image-20231212130857120 image-20231212131228021 image-20231212131402002 image-20231212131429910

二叉树的估计

image-20231212131643784 image-20231212131733444

由上图得右单分枝树

image-20231212132411840 image-20231212132718450

根据表达式建立二叉树

手工建树
image-20231212132854475

利用栈建树（这里建的树中序遍历可得表达式）
image-20231212133405100
image-20231212133545805
image-20231212133736290
image-20231212133914671
image-20231212134039361
image-20231212134158353
image-20231212134334391
image-20231212134718191
image-20231212134923325
image-20231212135006631
image-20231212135231068
image-20231212135626690

第七章图

基础

image-20231219082046855

图由顶点的有穷集合V和边的集合E组成。

无向图，即每条边都没有方向；边：(A1, A3)
有向图，即每条边 (弧） 都有方向。弧: <A1, A3>

image-20231219082304506 image-20231219082420836 image-20231219082459081 image-20231219082523370 image-20231219082543555 image-20231219082557695 image-20231219082618452 image-20231219082652492 image-20231219082732419 image-20231219082814483 image-20231219082814483 image-20231219082857377 image-20231219082908915 image-20231219083240435

顺序存储结构
image-20231219083320284
image-20231219083517229
image-20231219083550290
image-20231219083821390image-20231219083838469

image-20231219084228277 image-20231219085250491

链式存储结构
邻接表（起点）image-20231219085741600
逆邻接表（终点）image-20231219085839682
十字链表（同时保存入边和出边）image-20231219091342939
邻接多重表（每条边只需唯一的结点表示，是对无向图的邻接表的改进 ）image-20231219092457575

深度优先遍历 （DFS）

image-20231219094127567

广度优先遍历 （BFS）

image-20231219094624290 image-20231219095152897 image-20231219095448264

最小生成树（Prim算法）（理解：依次选择最小代价）

image-20231219095529754

可以是保留一些边，也可以理解为去掉环。

最小：构成树的分支权值和最小。

（Prim算法）过程：将构成的树与剩余相邻的顶点找出，选择其中权值最小的顶点组成新的树，继续这个过程。在这个过程中，树中的边不考虑。image-20231219100405755
此代码主要是求最小代价image-20231219101609468
image-20231219103108823

最小生成树（Kruskal克鲁斯卡尔算法）（理解：直接从边中挑选组成树）

image-20231219103904681 image-20231219104008546 image-20231219104124958 image-20231219104531928 image-20231219104659880 image-20231219104802571 image-20231219105653366 image-20231219110449529 image-20231219110715548

最短路径（迪杰斯特拉算法）（其中一个点到其余各点的最短路径）

image-20231219112547246 image-20231219112824509

扫描与0相连的，发现1最近，将1并入。接下来就是扫描剩余点判断是否经过1的并入，导致到0的距离变短，变短则更新到0的距离，以及到0的前一个点。

image-20231219112342386 image-20231219113347950 image-20231219113720479 image-20231219113906268

点6同理。此时已经扫描了23456了，从还未并入的顶点（23456）中找到距离起点0最近的结点（2），将2并入，更新set[2]=1。

image-20231219114846294

接下来就是以2再次扫描剩余点，判断并更新，并找出最短点并入。

image-20231219115221857 image-20231219115335805 image-20231219115449730

点6同理。扫描完剩余未并点后就该并入了，显然3距离0为6最短，并入，更新set[3]=1。接下来就是以3为中介点检测剩余未并入点（456）。

image-20231219115847952

点56同理。同理将5并入，更新set[5]。接下来就是以5为中介点检测剩余未并入点（46）。

image-20231219120312609

将4并入，同理，并入6。

image-20231219120541006 image-20231219120634344 image-20231219120918249 image-20231219121143514 image-20231219121523950

弗洛伊德算法（任意两个点的最短路径）

image-20231219121835164 image-20231219122224483 image-20231219123014132 image-20231219123243133

同理，A【1】【3】> A【1】【0】 + A【0】【2】不成立，不更新。来到｛2，0｝跳过。来到｛2，1｝，条件不成立，一直判断，发现中间点0来说，都不用更新。接下来选择点1作为中间点，判断所有不包含1的顶点队，看是否更新。

image-20231219133833277

更新完所有中间点后，得出path。

image-20231219135117100 image-20231219135247271 image-20231219135655940

拓扑排序

image-20231219140252641image-20231219140333224image-20231219140355343

image-20231219140510094 image-20231219140844473 image-20231219141548077 image-20231219141818424 image-20231219141849833

通过此代码不仅可以输出拓扑排序，还可以判断图中有没有环。

image-20231219142204138

逆拓扑排序
image-20231219142250723

借助栈使用递归可以实现输出。（出栈后输出）

image-20231219142549104 image-20231219142623398 image-20231219142833453

关键路径

事件：顶点；活动：边。

image-20231219144727755

求事件发生最早时间，根据拓扑排序选择事件，将事件的发生时间计算出选择最晚（大）的一条。

image-20231219145111117

求事件发生最迟时间，根据逆拓扑排序选择事件，第一个规定为事件最早的时间，将事件的发生时间计算出选择最早（小）的一条。

image-20231219145807665

求活动发生最早时间，它等于前面顶点的最早发生时间（发出它的事件的最早发生时间），根据事件最早可得出。

image-20231219150251021

求活动最迟时间，它等于后面最迟发生时间减去活动持续时间。比如l（a0）=vl（1）-a0=3

image-20231219150921450 image-20231219151102765

这条路径上的活动是否按时完成关系到整个工程是否按时完成。缩短这条路径的上活动的时间，工程时间可能缩短，相反也是。

image-20231219151707987

快速求关键路径
image-20231219152721913

逆推：将终点作为起点，它的活动时间为0，将它写在前面活动上。有多个路径这选择最大，相同表示有多条。

image-20231219154417179

第八章排序

简单排序（直接插入、简单选择、冒泡）

直接插入排序（将前面视为有序序列，依次将后面的插入，此过程中，关键字在temp里，同比较将元素后移，将关键字放入合适位置。不用担心覆盖，因为temp）（序列越有序，插入操作执行越快）

image-20231220053507552

简单选择排序（从无序序列里挑选最小的，将其放到有序的最右端（与无序序列最左交换））

image-20231220054708087

冒泡排序（在无序序列里依次比较选择两元素，将大的移动到右端（两者交换），重复，慢慢的大元素都到右端了）（我认为可以不需要交换标记）（当发现没有产生交换，就可结束，所以标记可用来提前结束排序）

image-20231220055052169

希尔排序（直接插入改进）

通过增量构造子序列，将子序列进行直接插入排序（将选中的关键字两两进行交换），一遍后序列相对有序。

将增量减小，一般是一半向下取整，最后将变成1。

从gap往前扫描子序列，代码容易实现。

image-20231220061930682

快速排序

通过ij交换（i的要大关键字，j的要小关键字），将两部分变得相对有序同时也选择出枢轴，用枢轴将序列分为两个部分，对两个部分再次选择枢轴递归（枢轴不用参与递归）。

j先移动。

image-20231220063317017 image-20231220064157018 image-20231220064415122

堆排序

image-20231220064527481 image-20231220064853432

建堆

找出最后一个非叶结点（n/2向下取整-1），若其孩子结点有小于当前结点的，交换，交换还要看被交换的结点与孩子结点情况，直到不交换；若其孩子结点都小于当前结点，则看前一个非叶结点。直到根节点

插入结点

将插入结点放入最后，找到到根结点的路径，从下往上进行交换，直到根节点或则不用交换。

image-20231220070647209image-20231220070705721image-20231220070818454

删除结点

用最后一个结点放到删除位置，从删除位置开始运用规则（比如大根堆，有孩子结点大于当前结点，交换，重复，至不用交换）进行一次调整。

image-20231220071345199image-20231220071405962image-20231220071455552

可以发现，根结点是最大或最下的，通过删除根结点，可以输出有序序列。同时在查找中不用查找所有无序序列。

将关键字建立完全二叉树（放到数组中），按照建堆方法（最后一个非叶结点，到根结点进行调整）建堆，然后“删除”根结点，删除后要调整，重复删除根结点。（可以将“删除”的结点放到最后，从而在原数组中得到有序序列）

image-20231220074152297 image-20231220074330783 image-20231220074626398

归并排序（讲二路归并排序）

先将所有关键字看作有序序列，序列两两归并，重复。

image-20231220075721366

image-20231220080107742image-20231220080249895

基数排序

不经过关键字比较。

要求关键字位数一致，不足高位补0。

桶，如果是数字，则桶为0-9，如果字母，则桶为a-z。

image-20231220080714477

按照关键字最低位（个位）进行分配。

image-20231220080824081

收集，按序收集。先出桶低。出桶后从左往右排列

image-20231220081108664

往前进一位（十位），分配（可以发现同一个桶中是按照上一次分配位的有序排列）。

image-20231220081423668

收集。

image-20231220081523841

进一位分配（百位）。（可以发现有几位就有几次分配）。

image-20231220081702559

收集。

image-20231220081808525 image-20231220081910200 image-20231220082040617 image-20231220082126232 image-20231220082510312 image-20231220082644805 image-20231220082734725 image-20231220082804980 image-20231220083049751 image-20231220083236637 image-20231220083733653 image-20231220084017230

ABD两趟之后，最大值次大值或最小值次小值出现在序列的一端；对最小值情况，如果出现在左端，则为最小值、次小值。如果出现在右端，则为次小值、最小值。

image-20231220084537079 image-20231220084637133 image-20231220084733397 image-20231220084846314 image-20231220084931035 image-20231220085151628 image-20231220085226136 image-20231220085339047

稳定性判读

image-20231220085517061image-20231220085532761

相同元素次序保持不变。

排序算法 稳定性 内部过程记忆
冒泡if（arr[j-1]>arr[j]）交换; 稳定 两两比较、交换
(顺序存储结构，交换)简单选择if(arr[k] > arr[j])k=j; 不稳定 无序序列中，关键字和扫描到的最小值交换
（链表，插入）简单选择if(p->data > g->data)p=q; 稳定 无序序列中，扫描到的最小值插入到无序序列前（插入到有序序列后）
直接插入 稳定 将第一个视为有序序列，依次挑选后面关键字插入到有序序列中（由于是有序序列，不用比较当前和前一个，只需比较当前，就可插入）（涉及元素移动）
快速 不稳定 i指向头，j指向尾，先动j，相向而行，每次移动要进行比较，将大的换到后面，小的换到前面，直到i=j（枢轴），此时将i前面和后面（不包括i）进行递归
希尔 不稳定 将步长一致上的两个元素比较交换，缩小步长，重复（写代码时重步长处往后扫描，每次扫描都将前多个步长的元素交换）（最后一趟插入排序）
或理解为：用相同间隔将序列分成子序列，对子序列进行排序，缩小间隔重复（例：12345678，间隔4，子序列有15、26、37、48，接下来间隔2，子序列有1357、2468）
归并 稳定（通过证明一次归并，通过if条件可稳定） 递归：将序列分成两部分，比较取出元素放到数组中
堆 不稳定 完全二叉树用数组存储，建堆（从最后非叶结点调整），删根调整
基数 稳定 关键字中位数为桶的个数；从左往右看位，根据位放入桶中，依次从桶低取出元素成为序列，看进一位，重复
image-20231220094149811 image-20231220094434810

排序（外存）（外部）（之前可称内部排序）

多路归并排序

从多个序列的头部选出最值并入结果序列。

只需往内存载入一部分关键字。

置换-选择排序

将内存读满，循环选择最值-写出外存-进入一个到内存。

在挑选过程要保证比外存中有序序列的最大（小）值大（小）。不能输出的进行标记，从未标记中挑选。

内存满且中所有关键字都被标记了 ，将标记抹去，输出到另一个有序序列。

内存中所有关键都标记了，即使有空位子，外存没有待输入关键字，将标记抹去，输出到另一个有序序列。

适合为多路归并排序构造初始归并段。但是各段长度不一致。

每个关键字每次归并有2次IO操作。

image-20231220101816026 image-20231220102015010

最佳归并树

用哈夫曼构造最佳归并树。IO次数最少。

image-20231220102320916

败者树

选择最值关键值。