wiki

我在北京邮电大学计算机科学与技术专业学习中所撰写的课程笔记。主要为大二和大三两个学年中学习的部分专业课和部分选修课，其中还包含课余时间自学的MIT公开课程计算机教学中消失的一学期。

限于笔记为上课过程中实时撰写，仅有部分笔记在课余时间进行了校对，因此存在大量的错漏，仅供参考。基于同样的原因，本次笔记中覆盖的内容仅为部分课程的部分内容，所记录的内容无法覆盖上课中的所有实际内容，不能作为教学范围和考试范围的参考，亦不能代表相关课程中的重点内容。同时，本笔记中涉及的课程内容仅代表2022至2023学年的大二年级和2023至2024学年的大三年级的课程内容。

在笔记中涉及到各位授课老师授课过程中的PPT截图，这些截图的版权归诸位授课老师和PPT作者所有，如有侵权请和我们联系，我们会立即删除相关内容。

在本笔记中，源远流长同学(@112292454)贡献了部分其自己的笔记，包括形式语言与自动机课程的笔记、计算机网络课程的复习笔记等的内容，在这里一并表示感谢。

笔记使用mdbook工具生成静态网页，生成的静态网页可以在Github Pages上查看。

协议

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

人工智能原理

大三上学期专业选修课——人工智能原理。

授课教师

• 邓芳
• 王晓茹

概述

本学期的主要内容

• 问题和知识表示方式
• 搜索和推理
• 典型应用
• 机器学习

要求：

• 课堂练习
• 作业
• 开卷考试

人工智能及发展

人工智能(Artificial Intelligence)是研究如何在机器上实现人类智能的学科。

智能：有效获取、传递、处理、再生和利用信息，从而在任意给定的环境达到预定目的的能力。

智能的特征：

• 具有感知能力
• 具有记忆和思维的能力

可以将智能分为：

• 计算智能
• 感知智能
• 认知智能

人工智能的研究方法

• 结构派：神经计算、生理学派、连接主义。

  智能活动的基础是神经细胞。

  智能活动过程是神经网络的状态演化过程。

  智能活动的基础是神经细胞的突触相互连接。

• 功能派：符号主义、心理学派、逻辑学派

  思维的基础是符号。

  思维的过程是符号运算。

  相较于神经网络，拥有可解释性。

• 行为模拟派：行为主义、进化主义、控制论学派

  基于感知-行为模型的研究途径和方法。

  智能行为是感知-行为的反射机制。

人工智能的发展历史

• 1956 人工智能的诞生
• 1956~1974 黄金之年，人工智能的第一次热潮
• 1974~1980 第一个AI冬天
• 1980~1987 人工智能的繁荣，人工智能的第二次热潮
• 1987~1993 第二个AI冬天
• 1993~现在 人工智能的突破

研究基础内容

按照研究的角度分：

• 符号智能
• 计算智能
• 人工生命

按照功能分：

• 机器感知/知识获取
• 机器思维/知识获取
• 机器行为/知识运用

目前研究遇到的问题

• 数据瓶颈
• 泛化问题
• 能耗
• 语义鸿沟
• 可解释性
• 可靠性

问题和知识表示

知识的基本内容

数据和信息、知识

数据：包含事实和数字、未经加工的事实和符号。

信息：从数据中提炼出来的有关信息、经过分析处理的数据形成信息。数据是信息的载体和表示，信息是数据在特定场合下的具体含义。

知识：是有关信息关联在一起所形成的信息结构，反映客观世界中事物之间的关系。

知识具有一下的特点：

• 客观性
• 相对正确性：在一定条件、时间、环境下
• 进化性
• 依附性：离开载体的知识是不存在的
• 不确定性
• 经验性
• 可表示性
• 可利用性
• 可重用性
• 共享性

知识的层次

• 事实
• 概念
• 规则
• 启发式知识

知识的分类

1. 作用范围：常识性知识，领域性知识
2. 作用及表示：事实性知识、过程性执行、控制性知识
3. 确定性：确定性知识、不确定性知识
4. ...

知识表达方法

知识表示是如何将以获得的有关知识以计算机易于接受的形式加以合理的描述、存储、有效的利用。

状态空间的表示

利用状态变量和操作符号，表示系统和问题的有关知识的符号体系。

使用三元组$(S,F,G)$表示：

• $S$是初始状态向量
• $F$是操作，表示引起状态变化的过程性知识的一组关系或者函数
• $G$是目标状态向量

这种状态空间的变化可以使用图的方式表示出来：

图中的：

• 节点：相应的状态描述
• 弧线：表示操作和状态的变化

寻找操作系统等价于寻求图中的某一路径。最佳路径就是两节点间具有最小的代价。

在状态描述中引入变量

与或树表示

问题归约法：已知问题描述，通过一系列的变换将问题转换为一个子问题的集合，并可以直接求解，解决初始问题。

与或图：使用类似于图的结构来表示把问题归约为后继问题的替换集合。

• 与图：将复杂的大问题分解为一组简单的小问题
• 或图：将复杂的大问题变化为等价或者等效的问题

或与图由以下四个部分组成：

• 初始节点：原始问题
• 终叶节点：本原问题，没有后继节点
• 与节点：子问题对应的节点为与逻辑
• 或节点：子问题对应的节点为或逻辑
• 可解节点：
  • 终叶节点为可解节点
  • 非终叶节点为或节点，后继节点中至少存在一个可解节点
  • 非终叶节点为与节点，后继节点均为可解节点
• 不可解节点：同可解节点对应的节点

产生式规则

产生式规则也称为基于规则的知识表示。产生式规则的基本结构分为： $$前提状态\to 结论动作$$ 产生式规则的特点：

• 善于表达领域知识
• 控制和知识相分离
• 知识的模块性强
• 便于实现解释推理
• 便于使用启发性知识

同时产生式规则的缺点是：

• 单条规则容易解释，但是规则之间的逻辑关系难以确定
• 规则数太大时，知识库的一致性难以维护
• 某些类型的知识难以表示，如结构性的知识

谓词表示法

命题逻辑和谓词逻辑是人工智能应用中的两种逻辑。

• 命题：具有真假意义的语句。常常使用大写字母表示。

知识的组织与管理

算法设计与分析

大三上学期专业必修课——算法设计与分析。

授课教师：邵蓥侠

算法导论

算法

算法是指解决问题的一种方法或者一个过程。

算法是若干指令的有穷序列：

• 输入
• 输出
• 确定性
• 有限性

算法的时间复杂度分析

渐进性原理及表示符号

使用渐进性原理对于算法的时间复杂度进行分析，反映算法的时间复杂度随着$N$变化发生变化的情况，衡量了算法的规模。

使用渐进分析的专用记号对于渐进性进行分析：

• 渐进上界记号$O$
• 渐进下界记号$\Omega$
• 非紧上界记号$o$
• 非紧下界记号$\omega$
• 紧渐进界记号$\Theta$

渐进分析中中的符号类似于比较：

• $f(n)=O(g(n))\approx a\le b$
• $f(n)=\Omega (g(n))\approx a\ge b$
• $f(n)=\Theta (g(n))\approx a=b$
• $f(n)=o(g(n))\approx a<b$
• $f(n)=\omega (g(n))\approx a>b$

同时渐进分析记号还具有若干性质：

1. 传递性

2. 反身性

3. 对称性

4. 互对称性

5. 支持算术运算

   $O(f(n)+g(n))=O(max\{f(n),g(n)\})$

   $O(f(n))+O(g(n))=O(f(n)+g(n))$

   $O(f(n))\times O(g(n))=O(f(n)\times g(n))$

   $O(cf(n))=O(f(n))$

在算法中存在这些常见的复杂性函数：

对于小规模的数据，这些复杂性函数的图像：

对于较大规模的数据，则图像为：

递归方程渐进阶的求解

代入法

先推测递归方法的显式解，然后使用数学归纳法证明这一推测的正确性。

例： 求证$T(N)=2T(\lfloor \frac{N}{2}\rfloor )+n$的渐进阶。

首先，推测$T(N)=O(nlogn)$， 即存在正的常数$C$和自然数$n_0$，使得当$n\ge n_0$时： $$T(N)\le Cnlogn$$ 假设当$2^{k-1}{n}_o\le n\le 2^k{n}_0$，$k>1$是，上面的推论成立，那么当$2^k{n}_0\le n\le 2^{k+1}{n}_0$时，有： \[ \begin{eqnarray} T(n) &=& 2T(\lfloor \frac{n}{2} \rfloor) + n \ &\le& 2 C \lfloor \frac{n}{2} \rfloor log(\lfloor \frac{n}{2} \rfloor) + n \ &<& 2C\frac{n}{2} log(\frac{n}{2}) + n \ &=& Cnlogn - Cn + n \ &=& Cnlogn - (c-1)n \ &\le& Cnlogn \end{eqnarray} \] 原假设成立。

迭代法

迭代展开递归方程的右端，使之成为一个非递归的合式，然后通过对合式的估计来达到对于方程左端解的估计。

例：求 $$T(n)=\{\begin{array}{l}7,n=1\\ 2T(\frac{n}{2})+5n^2,n>1\end{array}$$ 的渐进阶。 \[ \begin{eqnarray} T(n) &=& 2T(\frac{n}{2}) + 5n^2 \ &=& 2(2T(\frac{n}{4}) + 5(\frac{n}{2}))^2 + 5n^2 \ &=& 2(2(2T(\frac{n}{8}) + 5 (\frac{n}{4}) ^ 2) + 5(\frac{n}{2}))^2 + 5n^2 \ &=& 2^kT(1) + 2^{k-1} 5(\frac{n}{2^{k-1}}) ^ 2 + \cdots + 2 \times 5 (\frac{n}{2})^2 + 5n^2 \end{eqnarray} \] 不难发现： $$T(n)=O(n^2)$$ 迭代法还有一个衍生的方法——递归树法：

实际上就是使用树的方式表示整个递推公式。

套用公式法

针对如下的递推方程 $$T(n)=\{\begin{array}{l}c,n=1\\ aT(\frac{n}{b})+c{n}^k,n>1\end{array}$$ 我们有 $$T(n)=\{\begin{array}{l}O(n^{lo{g}_b^a}),a>b^k\\ O(n^{k}lo{g}_{b}n),a=b^k\\ O(n^k),a<b^k\end{array}$$ 这个公式还有一般化的情况：

如果递归方程的形式为： $$T(n)=\{\begin{array}{l}c,n=1\\ aT(\frac{n}{b})+f(n),n>1\end{array}$$ 则针对$f(n)$进行讨论：

1. 如果$\exists ϵ>0$, 使得$f(n)=O(n^{lo{g}_{b}a-ϵ})$，那么我们有 $$T(n)=\theta (n^{lo{g}_{b}a})$$

2. 如果$f(n)=\theta (n^{lo{g}_{b}a})$，那么我们有 $$T(n)=\theta (n^{lo{g}_{b}a}\cdot logn)$$

3. 如果$\exists ϵ>0$，使得$f(n)=\Omega (n^{lo{g}_b(a+ϵ)})$，且当$\exists c<1$时，当$n$充分大时有$af(\frac{n}{b})\le cf(n)$，那么我们有 $$T(n)=\theta (f(n))$$

母函数法

通用的方法总是复杂的。

设$a_0,a_1,\cdots ,a_n$是任意的数列，那么称下面这个函数为数列的母函数： $$f(x)=a_0+a_{1}x+\cdots +a_n{x}^n$$ 如果数列是算法的复杂性函数$\{T(n)\}$，则其母函数为： $$f(x)=T(0)+T(1)x+\cdots +T(n)x^n$$ 如果能由$T(n)$也就是的数列的递归方程求出母函数，那么其第$n$项系数为$T(n)$。

递归和分治

递归算法

直接或者间接调用自己的算法是递归算法。

递归算法的特点是：

• 结构清晰，可读性强，容易使用数学归纳法证明正确性
• 运行效率低

我们有几种方法来优化递归算法：

• 采用用户定义的栈来模拟系统的递归调用
• 用递推来实现递归函数
• 使用Cooper变换、反演变换将递归转换为尾递归，进而用迭代求解

分治算法

将一个难以解决的问题分成一些规模较小的问题，以便分而治之，各个击破。

编译原理和技术

大三上学期专业必修课——编译原理和技术。

授课教师：王雅文

编译概述

翻译和解释

程序设计语言

程序设计语言可以分成两种：

• 低级语言：机器语言、符号语言、汇编语言
• 高级语言

翻译程序

扫面所输入的源程序，并将其转换为目标程序，或者直接将源程序之间翻译成结果。

翻译程序可以分成两个大类：

• 编译程序：将源程序翻译为目标程序
• 解释程序：直接执行源代码

一种有效的方法是：现将源程序转换为某种中间形式、然后对中间形式的程序解释执行。

编译的阶段和任务

编译可以被分成两个阶段。

分析阶段，更具源语言的定义，分析源程序。包括词法分析，语法分析和语义分析。

综合阶段，根据分析结果构造目标程序。包括中间代码生成、代码优化和目标代码生成等阶段。

符号表的管理。

错误诊断和处理。

分析阶段

词法分析

线性分析和扫描。

词法分析程序需要对构成源程序的字符串进行分析，识别出每个具有独立意义的单词，将其转换成记号，并组织为记号流。同时把需要存放的单词放到符号表，如变量名、标号、常量名等。

词法分析程序的工作依据就是构词规则，也称为模式。

对于空格、注释的处理和其他：

• 分隔单词的空格：被跳过
• 源程序中的注释：被跳过
• 识别出来的标识符需要放入符号表中
• 某些记号还需要具有属性值

语法分析

层次结构分析。

将记号流按照语言的语法结构层次的分组，形成语法短语。源程序的语法短语通过使用分析树表示。

语法分析的层次结构通过由递归的规则表示。

例：total := total + rate * 4的分析树如下所示：

语义分析

对于语法成分的意义进行检查分析。语法成分就是语法分析确定的层次结构。同时收集必要的信息：类型、作用域等。工作依据是语义规则。

语义分析的一个重要人物是完成类型检查。

综合阶段

中间代码生成

中间代码是一种抽象的机器程序。，具有易于产生和易于翻译为目标代码等的特点。中间代码可以拥有多种形式。

常用三地址代码作为中间代码。

代码优化

对于代码进行改进，占用空间少，运行速度快。

目标代码生成

目标代码是可重定位的机器代码，一般就是汇编语言代码。

目标代码生成涉及到两个重要的问题：

• 对程序中使用的每个变量指定存储单元
• 对变量进行寄存器分配

符号表管理

符号表管理是编译程序中的一项重要工作，需要记录在源程序中使用的标识符和每个标识符相关的各种属性信息。

符号表是由若干记录组成的数据结构，每个标识符都在表中有一条记录，记录的域是标识符的属性。要求可以快速在符号表中可以找到标识符的记录，并且可以存取数据。

标识符的各种属性是在编译的各个不同的阶段填入符号表的。

错误处理

在编译的各个阶段都可能检测到源程序中存在的错误。

在发现源程序中的错误之后，编译器还需要判断错误的位置和性质，同时进行适当的恢复。

编译有关的其他概念

前端和后端

前端：与源语言有关而与目标机器无关的部分。

前端包括词法分析、语法分析、符号表的建立、语义分析和中间代码的生成。与机器无关的代码优化工作和相应的错误处理工作和符号表操作也在前端完成。

后端：和目标代码有关的部分，进行目标代码的生成、与机器有关的代码优化，相应的错误处理和符号表操作。

划分前端和后端的优点：

• 便于编译程序的移植
• 便于编译程序的构造

遍

一遍：对源程序或者其中间形式从头到尾扫描一遍，并作相关的加工处理，生成新的中间形式或者目标程序。

编译程序的结构受到遍的影响。

典型的一遍扫描的编译程序如图所示：

典型的多遍编译程序如图所示：

将编译程序分遍的优点：

• 减少对于主存容量的要求
• 编译程序的结构清晰
• 优化工作更加充分，获得高质量的目标程序
• 为编译程序的移植创造条件

将编译程序分遍也增加了不少重复性的工作。

编译程序的伙伴工具

预处理器

进行宏处理、文件包含、语言扩充等的功能。

汇编程序

汇编语言用助记符表示操作码，用标识符表示存储地址。

最简单的汇编程序需要对输入进行两遍扫描：

1. 找出表示存储单元的所有标识符，并将它们写入汇编符号表。在符号表中记录该标识符所对应的存储单元地址，此地址是在首次遇到该标识符的时候确定的。
2. 把每个用助记符表示的操作码翻译为二进制表示的机器代码。将用标识符表示的存储地址翻译为汇编符号表中该标识符对应的地址。

汇编程序需要输出可重定位的机器代码，同时需要对哪些需要重定位的指令做出标记。

连接装配程序

将多个经过编译或者汇编的目标模块连接装配成一个完整的可执行程序。

可将连接装配程序分成两个程序：

• 连接编辑程序：扫描外部符号表，寻找所连接的程序段，根据重定位信息表解决外部引用和重定位，最终将中整个程序涉及的目标模块逐个调入内存并连接在一起，组合成一个待装入的程序。
• 重定位装配程序：把目标模块的相对地址转换为绝对地址。

词法分析

词法分析任务由词法分析程序完成。

词法分析程序的作用

词法分析程序扫描源程序的字符流，按照源语言的词法规则识别出各类单词符号，产生用于语法分析的记号序列。

• 词法检查
• 同用户接口的一些任务：
  • 跳过源程序中的注释和空白
  • 把错误信息和源程序联系起来
• 创建符号表

词法分析程序和语法分析程序的关系

存在三种关系：

• 词法分析程序作为独立的一遍

  

  输出放到一个中间文件中，可以时磁盘文件/内存文件。

• 词法分析程序作为语法分析程序的子程序

  

  这种关系避免了中间文件，省去了取送符号的工作，有利于条编译程序的效率。

  是否在词法分析阶段生成符号表由源程序是否由块结构语言决定。块结构语言是变量含有作用域的语言，而非块结构语言是变量没有作用域的语言。

• 词法分析程序与语法分析程序作为协同程序

  词法分词程序与语法分析程序在同一遍中工作，以生产者和消费者的关系同步运行。

在上述三种关系中，词法分析程序都是作为一个单独的程序存在，这样的好处为：

• 简化设计
• 改进编译程序的效率
• 加强编译程序的可移植性

源程序的输入与词法分析程序的输出

词法分析程序的实现方法

1. 利用词法分析程序自动生成器

   从基于正规表达式的规范说明自动生成词法分析程序

   生成器提供用于源程序字符流读入和缓冲的若干子程序

2. 利用系统程序设计语言来编写

3. 利用汇编语言编写

缓冲区

为了得到某一个单词符号的确切性质，需要超前扫面若干个字符。

把一个缓冲区分为大小相同的两半，每半各含N个字符，这被称为缓冲区配对。

使用配对缓冲区的意义是为了避免在缓冲区的结束处读取到不完成的单词。测试的过程如下的伪代码所示：

我们还可以在每半个缓冲区的最后添加结束标记来提高测试的效率：

词法分析程序的输出

记号、模式和单词

记号是某一类单词符号的类别编码。如标识符的记号为id，常数的记号是num。

模式是某一类单词符号的构词规则。如标识符的模式是“由字母开头的字母数字串”。

单词是某一类单词符号的一个特例。

记号的属性

词法分析程序在识别出一个记号后，要将与之有关的信息作为属性保存下来。

记号影响语法分析的决策，属性影响记号的翻译。

在词法分析阶段，对一个记号只能确定一种属性。

• 标识符：单词在符号表中的入口指针
• 常数：表示的值
• 关键词：一符一种/一类一种
• 运算符：一符一种/一类一种
• 分界符：一符一种/一类一种

由于关键词、运算符和分节符，由于确定的编程语言只能有有限的关键词、与运算符和分界符，因此可以使用一符一种。

例：total := total * rate * 4的词法分析结果

• 标识符，指向标识符total`在符号表中的入口指针
• 赋值运算符，
• 标识符，指向标识符total在符号表的入口指针
• 加法运算符，
• 标识符，指向标识符rate在符号表中的入口指针
• 乘法运算符，
• 常数，整数值4

输出实际上就是一个<记号，属性>的二元组。

单词符号的描述及识别

识别单词是按照记号的模式进行的，一种种记号的模型匹配一类单词的集合。

正规表达式和正规文法是描述模式的重要工具。

词法：描述语言的标识符、常数、运算法和标点符号等记号的文法，使用正规文法。

语法：借助于记号来描述语言的结构的文法，使用上下文无关的文法。

记号的文法

标识符

假设标识符定义为“由字母开头的，由字母或数字组成的符号串”。

则描述标识符集合的正规表达式为： $$ \rm{letter(letter|digit) ^*} $$ 转换为正规文法： $$ id \to {\rm letter}\ rid $$

$$ rid \to \epsilon | {\rm letter}\ rid | {\rm digit}\ rid $$

常数

1. 整数 $$ （digit)^+ $$ 转换为正规文法：

   

2. 无符号数 $$ \rm (digit)^+(.(digit)^+)?(E(+|-)?(digit)^+)? $$ 转换为正规文法：

   

3. 运算符 $$ \rm <|<=|=|<>|>=|> $$

状态转换图与记号的识别

状态转换图是一张有限的方向图。

由上文中无符号数的右线性文法可以画出状态转换图：

词法分析程序的设计与实现

就是写一个程序。

文法和状态转换图

首先根据语言的说明写出记号的正规文法、画出状态转换图。

语法分析

语法分析简介

语法分析是编译程序的核心规则，按照源语言的语法规则进行分析，输出分析树并进行语法分析阶段的错误处理。

• 从源程序记号序列中识别出各类的语法成分
• 进行语法检查

鉴于分析树的树状数据结构，我们有两种分析方法：

• 自顶向下的分析方法
• 自底向上的分析方法

语法错误的处理

错误处理的目标是：

• 报告错误的位置和性质
• 迅速从错误中恢复
• 不应该明显影响对于正确程序的分析速度

错误处理有如下的策略：

• 紧急恢复：一旦发现错误，分析程序每次抛弃一个输入记号，直到扫描到的记号属于某个指定的同步记号集合。

  同步记号集合往往是定界符，如语句结束符（分号），语句起始符，块结束符（END）。

• 短语级恢复

• 出错产生式

• 全局纠正

自顶向下的分析防范

递归下降分析

从文法的开发符号出发，进行推导，试图推导出要分析的输入串的过程。对于给定的输入符号串，从对应于文法开始符号的根节点出来，建立分析树。整个过程是一个试探的过程，反复使用不同的产生式谋求匹配输入符号串的过程。

例：按照如下的文法分析abbcde $$\begin{gathered} \mathrm{S}\to \mathrm{aAcBe} \\ \mathrm{A}\to b|Ab \\ \mathrm{B}\to \mathrm{d} \end{gathered}$$ 首先尝试$\mathrm{S}\to \mathrm{aAcBe}$，对于$A$分别尝试两种生成情况递归生成中间两个$\mathrm{b}$，依次类推递归尝试所有的生成式。

使用递归下降分析可以得到一个最左推导序列。

关于推导的补充知识：

现在有 $$>\alpha \mathrm{A}\beta =>\alpha \gamma \beta >$$ 其中$=>$ 表示一步推导，其中称左边直接推导出右边，也可以说右边是左边的直接推导，或者右边直接归约到左边。

关于短语的补充知识：

假定$\alpha \beta \delta$ 是文法的一个句型，如果存在： $$\begin{gathered} >S{\Rightarrow }^{\ast }\alpha A\delta \\ >A{\Rightarrow }^{+}\beta > \end{gathered}$$ 就称$\beta$ 是句型$\alpha \beta \delta$关于非终结符号$A$的短语。

如果存在： $$\begin{gathered} >S{\Rightarrow }^{\ast }\alpha A\delta \\ >A\Rightarrow \beta > \end{gathered}$$ 那么就称$\beta$ 是句型$\alpha \beta \delta$关于非终结符号$A$的直接短语。

一个句型的最左直接短语称为该局性的句柄。

因此对于输入串的扫描是自左至右进行的，只有使用最左推导，才能保证按照扫描的顺序匹配输入串。

但是递归下降分析方法存在缺陷：

• 左递归的文法，可能导致分析过程陷入死循环
• 回溯
• 工作的重复
• 效率低

递归调用预测分析

一个确定的，不带回溯的递归下降分析方法。

1. 如何克服回溯？

   根据所面临的输入符号准确的指派一个候选式去执行任务。

2. 那么如何准确指派，首先对文法存在要求。

   • 不含有左递归
   • $FIRST({\alpha }_i)\cap FIRST({\alpha }_j)=\varnothing$ 其中$i\ne j$

   解释一下$FIRST$的规定： $$>FIRST(\alpha )=\{a|\alpha \Rightarrow a\beta \}>$$ 也就是非终结符$\alpha$能够推出的一个终结符。

预测分析程序的构造

1. 构造预测分析程序转换图

   每个非终结符号都有一张图，边的标记可以使终结符号和非终结符号。

   对于非终结符号$A$的转移表示对$A$的过程调用。

   对于终结符号$a$的转移，表示下一个输入符号应该是$a$

   为了从文法构造一个转换图，我们需要首先对文法进行改写：

   • 重写文法
   • 消除左递归
   • 提取左公因子

   消除左递归：

   首先考虑简单情况。如果存在产生式： $$>\mathrm{A}\to \mathrm{A}\alpha |\beta >$$ 可以改写为： $$\begin{gathered} >A\to \beta A^{\prime } \\ >A^{\prime }\to \alpha A^{\prime }|ϵ> \end{gathered}$$

   提取左公因子：

   如果存在产生式： $$>\mathrm{A}\to \alpha {\beta }_1|\alpha {\beta }_2>$$ 那么提取左公因子$\alpha$，有： $$\begin{gathered} >A\to \alpha A^{\prime } \\ >A^{\prime }\to {\beta }_1|{\beta }_2> \end{gathered}$$

   然后对于每个非终结符号$A$：创建一个初始状态和一个终结状态，对于每一个产生式$A\to X_1{X}_2\cdots X_n$创建一条从初态到终态的路径。

2. 转换图的工作过程

   从文法开始符号所对应的转换图的开始状态开始分析。

   经过若干动作之后，处于状态$S$，指针指向符号$a$:

   

3. 转换图的化简

   反复代入化简。

   

4. 预测分析程序的实现

   

   void procE()
   {
       procT();
       if (input == '+')
       {
           pointer.forward();
           procE();
       }
   }
   

非递归预测分析

使用一张分析表和一个栈联合控制，输入对输入符号的自顶向下分析。

预测分析程序的模型如图所示：

• 输入缓冲区：存储被分析的输入符号串
• 符号栈：存放文法符号
• 分析表：存储产生式，根据给定的栈顶和当前指针定位产生式
• 输出流

说明，$表示起始和终结符号

预测分析控制程序

根据栈顶符号X和当前输入符号a，分析动作存在四种可能：

1. X和a都是终结符号，停止分析
2. X=a但是不为终结符号，弹栈并向前移动输入指针
3. X在分析表中但是a不是，调用错误处理程序报告错误并进行错误恢复
4. 访问分析表获得产生式，先弹栈，并将生成式的右部符号串按反序压入栈中

可以写出伪代码：

预测分析表的构造

1. 首先进行文法的改写，同递归调用分析预测的要求和步骤一致。

2. FIRST集合及其构造

   FIRST集合的定义为：

   对于任何文法符号串$\alpha$，$FIRST(\alpha )$是$\alpha$可以推导出的开头终结符号集合。 $$FIRST(\alpha )=\{a|\alpha {\Rightarrow }^{\ast }a\cdots \}$$ 特别需要注意的是，如果$\alpha$可以推出空串，那么$ϵ\in FIRST(\alpha )$。

   构造FIRST集合：

   • 如果$X\in V_T$, 那么$FIRST(X)=\{x\}$
   • 如果$X\in V_N$， 那么针对所有$X$的生成式$X\to a\cdots$，将$a$加入
   • 如果$X\to ϵ$ ,加入空串
   • 如果存在$X\to Y\cdots$ ，加入$FIRST(Y)$中所有非空的元素

   重复该过程，知道所有的集合不再变化为止。

3. FOLLOW集合及其构造

   FOLLOW集合的定义为：

   假定$S$为文法的开始符号，对于文法中的任何非终结符，集合$FOLLOW(A)$式在所有句型中紧跟$A$之后出现的终结符号或者$\$$组成的集合。 $$FOLLOW(A)=\{a|S{\Rightarrow }^{\ast }\cdots Aa\cdots \}$$ 特别的，如果$S{\Rightarrow }^{\ast }\cdots A$，那么规定$\$\in FOLLOW(A)$，注意集合中不能存在空串。

   构造FOLLOW集合：

   • 对于文法开始符号$S$，将$\$$放入$FOLLOW(S)$中
   • 如果存在产生式$A\to \alpha B\beta$，那么将$FIRST(\beta )$中的所有非空元素加入$FOLLOW(B)$中
   • 如果$A\to \alpha B$，或者$A\to \alpha B\beta$且存在$\beta {\Rightarrow }^{\ast }ϵ$，那么将$FOLLOW(A)$中的所有元素加入到$FOLLOW(B)$中

   重复此过程，直到所有集合不再变化为止。

4. 预测分析表的构造

   

LL(1文法：如果一个文法的预测分析表不含有多重定义的表项，则称该文法为LL(1)文法。

LL(1)文法的判定方法：

当且仅当对于该文法的每一个产生式$A\to \alpha |\beta$ ，都有：

• $FIRST(\alpha )\cap FIRST(\beta )=\varnothing$
• 如果$\beta \to ϵ$, 那么 $FIRST(\alpha )\cap FOLLOW(A)=\varnothing$

或者根据分析表来判断。

自底向上的分析方法

从左到右进行对输入串的扫描，自底向上的进行分析树的构造。分析的过程如下：

• 从输入符号串开始分析
• 查找当前句型的可归约串
• 使用规则，把它归约成相对应的非终结符号
• 重复

优先分析法

优先分析法分成简单优先分析法和算符优先分析法。

1. 简单优先分析法 按照文法符号之间的优先关系确定当前句型的可归约串。但是存在分析效率低且只适用于简单优先文法的问题。

   简单优先文法： 任何两个文法符号之间最多存在一种优先关系。 不存在具有相同右部的产生式。

2. 算符优先分析法 只考虑中介符号之间的优先关系。分析速度快，但是只适用于算符优先文法。

   算符文法： 没有形如$A\to \cdots BC\cdots$的产生 式的文法。

   算符优先文法：算符文法，且不含有$ϵ$生成式。任何两个构成有序对的终结符号之间最多有$>$、$<$、$=$三种优先关系中的一种成立。

   可归约串是句型的最左素短语。素短语是句型的一个短语，至少含有一个中介符号，并且除它自身之外不存在其他更小的素短语。最左素短语就是处在句型最左边的素短语。

移进——归约分析方法

该方法需要设置一个符号栈存放文法符号。

1. 将输入符号一个个地移进栈中；

2. 当栈顶的符号串形成某个产生式的一个候选式时，在一定条件下，把该符号串替换为该产生式的左部符号；

3. 重复2，直到栈顶符号不再是可归约串为止；

4. 重复1~3，直到最终归约出开始符号。

规范归约

假设$\alpha$是文法$G$的一个句子，存在右句型序列${\alpha }_n,{\alpha }_{n-1},\cdots ,{\alpha }_1,{\alpha }_0$是$\alpha$的一个规范归约，如果序列满足：

• ${\alpha }_n=\alpha ,{\alpha }_0=S$
• 对于任何$i$，${\alpha }_{i-1}$是经过把${\alpha }_i$的句柄替换成相应产生式的左部符号而得到的

LR分析方法

首先介绍LR(k)的含义：L表示自左向右扫描输入字符串，R表示为输入符号串构造一个最右推导的逆过程，k表示为作出分析决定而向前看的输入符号个数。

LR分析方法的基本思想：

• 历史信息：记住已经移进和归约出的整个符号串
• 预测信息：根据所用的产生式推测未来可能遇到的输入符号

根据历史信息和预测信息，以及现实的输入符号确定栈顶的符号串是否构成相对于某一产生式的句柄。

LR分析程序的模型和工作过程

• 栈
• 控制程序
• 分析表
• 输入
• 输出

分析表

LR分析控制程序工作的依据，有着两张表：

• $goto[S_m,X]$ 状态$S_m$经过$X$转移的后继状态
• $action[S_m,a_i]$ 状态$S_m$遇到输入符号$a_i$应该采取的分析动作。

分析动作可以有四种：

• shift S：将当前输入符号$a_i$和状态$S$推进栈中，向前扫描指针前移，其中$S=goto[S_m,a_i]$
• reduce by：生成式为$A\to \beta$，如果$\beta$的长度为$r$，则从栈顶向下弹出$r$项，使得$S_{m-r}$成为栈顶状态，然后把文法符号$A$以及状态$S$推进栈中，其中$S=goto[S_{m-r},A]$
• accept：宣布分析成功
• error：调用出错处理程序，进行错误恢复

分析控制程序

活前缀：一个规范句型的一个前缀，如果不含句柄之后的任何符号，则称它为该句型的一个活前缀。

SLR分析表的构造

为给定的文法构造一个识别它所有活前缀的DFA，根据这个DFA构造文法的分析表。

LR(0)项目：右部某个位置上标有圆点的产生式成为文法G的一个LR(0)项目。例如生成式$A\to XYZ$对应有4个LR(0)项目：

• $A\to \cdot XYZ$
• $A\to X\cdot YZ$
• $A\to XY\cdot Z$
• $A\to XYZ\cdot$

各种LR(0)项目可以分为：

• 归约项目：远点在产生式最右端的项目
• 接受项目：对文法开始符号的归约项目
• 待约项目：圆点后第一个符号为非终结符号的项目
• 移进项目：圆点后第一个符号为终结符浩的项目

下面再定义LR(0)有效项目：

对于项目$A\to {\beta }_1\cdot \beta 2$，活前缀$\gamma \to \alpha {\beta }_1$，如果存在 $$S{\Rightarrow }^{\ast }\alpha A\omega \Rightarrow \alpha {\beta }_1{\beta }_2\omega$$ 则称该项目对于该前缀是有效的。

文法G·的某个活前缀$\gamma$的所有LR(0)有效项目组成的集合称为该活前缀的LR(0)有效项目集。

文法G的所有LR(0)有效项目集组成的集合称为G的LR(0)项目集规范族。

SLR分析方法的一个特征：如果文法的有效项目集中有冲突动作，多数冲突可以通过考查有关非终结符号的FOLLOW集合可以解决。

例如对于项目集 $$I=\{X\to a\cdot b\beta ,A\to \alpha \cdot ,B\to \beta \cdot \}$$ 同时存在移进-归约冲突和归约-归约冲突。

通过查看FOLLOW(A)和FOLLOW(B)解决：如果 $$\begin{gathered} FOLLOW(A)\cap FOLLOW(B)=\varnothing \\ b\notin FOLLOW(A)\&\&b\notin FOLLOW(A) \end{gathered}$$ 决策：

• 当$a=b$，将$b$入栈
• 当$a\in FOLLOW(A)$时，使用$A\to \alpha$进行归约
• 当$a\in FOLLOW(B)$时，使用$B\to \beta$进行归约

LR(1)分析表的构造

首先给出LR(K)项目： $$[A\to \alpha \cdot \beta ,a_1,a_2,\cdots ,a_k]$$

• $A\to \alpha \cdot \beta$ 是一个LR(0)项目
• $a_1,a_2,\cdot a_n$是向前看符号串

注意，向前看符号串只对归约项目起作用。

LR(k)项目意味着当它所属的项目集状态在栈顶且后续的输入符号序列和向前看符号串匹配的时候才允许归约。

定义：LR(1)有效项目

对于一个LR(1)项目$[A\to \alpha \cdot \beta ,a]$，如果存在一个规范推导： $$S{\Rightarrow }^{\ast }\delta A\omega \Rightarrow \delta \alpha \beta \omega$$ 其中$\omega$的第一个符号为$a$，则该项目对于活前缀$\delta \alpha$是有效的

推广：

如果项目$[A\to \alpha \cdot B\beta ,a]$对于$\delta \alpha$是有效的，并且由产生式$B\to \eta$，则对于任何的$b\in FIRST(\beta a)$ ，项目 $$[B\to \cdot \eta ,b]$$ 对于该活前缀也是有效的。

利用定义和推广获得项目集的闭包：

构造LR(1)分析表

LALR(1)分析表的构造

首先给出两个描述LR(1)项目集特征的定义：

• 同心集：如果两个LR(1)项目集在去掉搜索符号之后是相同的，则称这两个项目具有相同的心。
• 项目集的核：除了初态项目集之后，一个项目集的核是由该项目集中那些圆点不在最左边的项目组成。

构造LALR(1)分析表的基本思想：

• 合并项目集规范族中的同心集，减少分析表的状态数
• 用核代替项目集，减少项目集所需的存储空间

注意，同心集的合并可能会导致新的归约-归约冲突。

因此，构造LALR(1)分析表的过程如下：

1. 首先构造LR(1)项目集的规范族

2. 检查LR(1)项目集规范族

   如果存在冲突，不是LR(1)文法。

   不存在冲突。

3. 检查是否存在同心集，合并同心集

4. 检查合并之后的项目集是否存在冲突

   如果存在冲突，不是LALR(1)文法

   不存在冲突。

5. 根据LALR(1)项目集规范族构造分析表

文法的分类：

LR分析方法对于二义文法的应用

定理：任何二义文法绝不是LR文法，因而也不是SLR或者LALR文法。

但是在程序设计语言中的某些结构使用二义性文法来描述比较直观，使用方便。可以定义一些规则来解决文法的二义性，例如：

• 算数表达式

  使用运算符优先级或者运算结合规则

• if语句

  else的最近最后匹配规则

LR分析的错误处理与恢复

当分析文法发生错误时，可以采用如下的恢复策略：从栈顶开始弹栈，可能会弹出若干个状态直到出现状态S。其中状态S满足以下某一个条件：

• 状态S有相对于当前输入符号的转移

  移进，分析继续

• goto表中有S相对于某非终结符号A的后继

  跳过若干个输入符号，直到出现符号a，$a\in FOLLOW(A)$，然后将状态goto[S, A]压入栈顶，分析继续

语法制导翻译技术

语法制导翻译的整体思路：

1. 根据翻译目标确定每个产生式的语义
2. 根据产生式的含义确定每个符号的含义
3. 将这些语义以属性的形式附加到相应的文法符号上，将语义和语言结构联系起来
4. 根据产生式的语义给出符号属性的求值规则形成语法制导定义

翻译目标决定了产生式的含义，决定文法符号应该具有的属性，也决定了产生式的语义规则。

翻译目标决定语义规则：翻译目标决定产生式的含义，决定文法符号应该具有的属性，也决定了产生式的语义规则。

翻译目标可以是：

• 生成代码
• 对输入符号串进行解释执行
• 向符号表中存放信息
• 给出错误信息

翻译结果依赖于语义规则：使用语义规则进行计算所得到的结果就是对输入符号串进行翻译的结果。

语法制导翻译的一般步骤是：

语义规则的执行时机：

语法制导定义及翻译方法

语法制导定义

对于上下文无关文法的推广。

每个文法符号都可以拥有一个属性集，其中可以包括两类属性：

• 综合属性

  左部符号的综合属性是从该产生式的右部文法符号的属性值计算处理的

  在分析树中，一个内部结点的综合属性是从其子节点的属性值计算出来的

• 继承属性

  对于每一个文法产生式$A\to \alpha$，都有与之相联系的一组语义规则，其形式为

  $$b=f(c_1,c_2,\cdots ,c_k)$$ 其中$f$是一个函数，而且：

  如果b是A的一个综合属性，则$c_1,c_2,\cdots ,c_k$是产生式右部文法符号的属性或者是A的继承属性；如果b是右部某个文法符号的继承属性，那么$c_1,c_2,\cdots ,c_k$是A或者产生式右部任何文法符号的属性。

在一般情况下，语义规则函数可以写成表达式的形式： $E.val=E_1.val+T.val$。但是在某些特定的情况下，一个语义规则的目的就是完成一个特定的动作，例如打印一个值或者向符号表中插入一条记录。这样的属性称为虚拟综合属性，写成过程调用或者是程序段的形式，例如print(E.val)。

依赖图

分析树中，结点的继承属性和综合属性之间的相互依赖关系可以由依赖图表示。在依赖图中，

• 为每个属性设置一个结点
• 如果属性b依赖于属性c，那么从属性c的结点由一条有向边连接到属性b的结点。

计算次序

依赖图的任何拓扑排序给出了分析树中结点的语义规则计算的有效顺序。

综上，语法制导翻译过程为：

1. 最基本的文法用于建立输入符号串的分析树
2. 为分析树构造依赖图
3. 对依赖图进行拓扑排序
4. 从这个序列得到语义规则的计算顺序
5. 照此计算顺序进行求值，得到对于输入符号串的求值。

S属性定义和L属性定义

S属性定义：仅涉及到综合属性的语法制导定义。

L属性定义：一个语法制导定义如果满足每个产生式$A\to X_1{X}_2\cdots X_n$对应的每条语义规则计算的属性都是：

• A的综合属性
• $X_j$的继承属性，且该继承属性仅继承于A的继承属性或者产生式中$X_j$左边的符号属性

按照定义，每个S属性定义都是L属性定义。

L属性定义的属性都可以用深度优先遍历的顺序计算：

• 在进入结点前，计算继承属性
• 在从结点返回时，计算他的综合属性

翻译方案

上下文无关文法的一种便于翻译的书写形式。

• 属性和文法符号相对应
• 语义动作写在花括号中，并插入到产生式右部某个合适的位置上
• 给出了使用语义规则进行属性计算的顺序
• 分析过程中翻译的注释

深度优先遍历树中的结点，执行动作，打印出95-2+。

翻译方案的设计：

1. 对于S属性定义：

   为每一个语义规则建立一个包含赋值的动作，把这个动作放在相应的产生式右边末尾。

2. 对于L属性定义：

   左部符号的综合属性只有在它所引用的所有属性都计算出来之后才能计算，因此这种属性的计算动作要放在产生式的末尾。

   右部符号的继承属性必须在这个符号以前的动作中计算出来，因此计算该继承属性的动作必须出现在相应文法符号之前。

S-属性定义的自底向上翻译

为表达式构造语法树的语法制导定义

S-属性定义的自底向上实现

基于LR分析方法。

在LR分析方法中，分析程序使用栈存放已经分析过的子树的信息。因此，在分析栈中增加一个域保存综合属性值。

修改分析程序：

• 对于终结符号：

  综合属性值由词法分析程序产生。

  当分析程序执行移进操作时，属性值随着状态符号一起入栈。

• 为每个语义规则编写一段代码计算属性值

• 对于每个产生式$Z\to XYZ$:

  在进行归约动作时执行属性值的计算代码。将右部符号的相应状态和属性出栈，左部符号的相应状态和属性入栈。

L-属性定义的自底向上翻译

在自底向上的分析过程实现L属性定义的翻译。

• 可以实现任何基于LL(1)文法的L属性定义
• 可以实现许多基于LR(1)文法的L属性定义

下面介绍四种实现方法。

移走翻译方案中嵌入的语义规则

自底向上地处理继承属性。对翻译方案进行等价变换，使所有嵌入的动作都出现在产生式的右端末尾。

方法：

• 在基础文法中引入新的产生式，形如$M\to ϵ$，即只生成空串
• 将$M$称为标记非终结符号，用来代替嵌入在产生式中的动作
• 把被$M$替代的动作放在产生式的末尾

例如对于下列文法进行等价变换： $$\begin{gathered} E\to TR \\ R\to +T\{print{(}^{\prime }{+}^{\prime })\}R|-T\{print{(}^{\prime }{-}^{\prime })\}|ϵ \\ T\to num\{print(num.val)\} \end{gathered}$$ 引入非终结符号$M$和$N$，形成新的翻译方案 $$\begin{gathered} E\to TR \\ R\to +TMR|-TNR|ϵ \\ T\to num\{print(num.val)\} \\ M\to ϵ\{print{(}^{\prime }{+}^{\prime })\}N\to ϵ\{print{(}^{\prime }{-}^{\prime })\} \end{gathered}$$ 可以画出等价变化之后的分析树：

直接使用分析栈中的继承属性

利用复制规则传递继承属性。

变换继承属性的计算规则

当且仅当属性值在栈中存放的位置可以预测时，可以从栈中取得继承属性。

例如对于语法制导定义：

当使用$Z\to z$进行归约时，属性$Z.i$可能出现在top - 1和top - 2中。

因此使用模拟继承属性的计算：

引入标记非终结符号$M$，

这样使用$Z\to z$进行归约时，属性$Z.i$一直在top - 1的位置上。

​

语义分析概述

程序设计语言的结构常常使用上下文无关文法来描述，基于此开发的语法分析程序可以检查程序中存在的语法错误。但是语法正确的程序不一定时完全正确的，程序的正确还和程序中的上下文有关系：

• 变量的作用于问题
• 同一作用域中的同名变量问题
• 表达式和赋值语句中的类型一致问题

注意：

设计使用上下文有关文法来描述语言中的上下文结构在理论上是可行的，但是实践上非常困难。

因此，使用语法制导的翻译技术实现语义的分析，设计专门的语义动作补充山下文无关文法的分析程序。

语义分析的任务

语义分析程序通过将变量的定义和变量的引用联系起来，对源程序的含义进行检查。

语义分析程序会在分析声明语句时，将所声明标识符的信息收集到符号表中，收集到信息包括：类型、存储位置、作用域等。主要编译时控制处在声明该标识符的程序块中，就可以从符号表中查到该标识符的记录。

类型检查可以分成两种：在目标程序运行时进行的检查称为动态检查。而读入源程序但不执行源程序的情况下进行的检查就是静态检查。类型检查的内容包括：

• 检验结构的类型是否和上下文所期望的一致、检查操作的合法性和数据类型的相容性
• 唯一性检查：一个标识符在同一作用域中只能被声明一次
• 控制流检查：控制语句是否转移到一个合法的位置

语义分析程序的位置

以语法树作为基础，根据语言的语义，检查每个语法程序在语义上是否满足上下文对于它的要求。

同时，语义分析的结果也有利于生成正确的目标代码，例如在存在重载运算符和类型强制转换的场景中。

错误处理

语义分析程序在发现错误时，需要显示出错信息，报告错误出现的位置和错误的性质。在完成报告之后还需要恢复分析器，继续对后面的结构进行检查。

符号表

符号表在翻译过程中有着两方面的作用：

• 检查语义的正确性
• 辅助正确的生成代码

符号表是一张动态表，在编译期间符号表的入口会不断的增加或者删除。编译程序需要频繁和符号表进行交互，符号表的效率会直接影响到编译程序的效率。

符号表的建立和访问时机

对于多遍的编译程序：

在词法分析的阶段建立符号表，标识符在符号表中的位置作为记号的属性。适用于非块结构语言的编译。

对于合并遍的编译程序：

符号表的内容

符号表的操作

符号表组织

非块结构语言

块结构语言

对于夸结构语言来说，模块中可嵌套字块，每个块中均可以定义局部变量。每个程序块中有一个字表，保存该块中声明的变量和属性。

符号表使用栈式符号表或者栈式哈希符号表组织。

例如，对于如下的PASCAL程序：

根据上述程序可以

栈式符号表简介：

当遇到变量声明时，将包含变量属性的记录入栈；当到达块结尾时，将该块中声明的所有变量的记录出栈。在块索引表中记录每个块开始的栈位置。

在栈式符号表中的各种操作：

1. 插入：需要检查字表中是否有重名的变量，如果没有就正常入栈，反之报告错误
2. 检索：从栈顶到栈底线性检索。如果在当前字表中找到就是局部变量，在其他字表中找到就是非局部变量。通过遍历顺序实现了最近嵌套作用域的原则。
3. 定位：将栈顶战阵的位置压入块索引表，块索引表中的元素就指向相应块的字表中第一个记录在栈中的位置。
4. 重定位：用块索引表中顶端元素的值恢复栈顶指针，直接清除了刚刚编译完的块在栈中的记录。

栈式哈希表符号表的简介：

使用哈希函数将符号名字映射到符号表中的地址。

类型检查

对于类型检查，不同的语言有着不同的观点。

• 强调最大程序的限制，执行严格的类型检查。
• 强调数据类型应用的灵活性，建议采用隐式类型，在编译时不进行类型检查，在程序运行期间对类型进行扩展检查。

一个简单的类型检查程序

假设现在存在一个简单语言的文法如下：

运行环境

程序运行时的存储组织

存储分配策略

在运行时存储代码的划分一般为：

其中除了目标代码之后，其余三种数据空间采用的存储分配策略是不同的：

• 静态存储分配
• 栈式存储分配
• 堆式存储分配

静态存储分配

使用静态存储分配的条件式在编译时源程序中声明的各种数据对象所需的存储空间的大小可以确定。

因此在编译时，为静态存储分配的变量分配固定的存储空间：

• 每个过程的活动记录的大小及位置
• 活动记录中每一个名字所占用存储空间的大小及位置
• 数据对象的地址可以生成在目标代码中

使用静态存储分配时，名字的左值在运行期间时保存不变的。

使用静态存储分配对于源程序有一定的限制：

• 数据对象的大小和位置必须在编译时可以确定
• 不允许出现过程递归调用
• 不能建立动态的数据结构

栈式存储分配

存储空间按照栈的方式组织：

• 活动开始的时候，活动相对应的活动记录入栈。局部变量的存储空间分配在活动记录中，同一过程中声明的名字在不同的活动中绑定到不同的存储空间中。
• 活动结束时，活动记录出栈，分配给局部名字的存储空间被释放，名字的值丢失不再可用。

在栈式存储分配中存在调用序列和返回序列：

• 调用序列：目标程序中实现控制从调用程序进入被调用程序的一段代码。

  用于实现活动记录的入栈和控制的转移。

• 返回序列：目标程序中实现控制从被调用过程返回到调用过程的一段代码。

  用于实现活动记录的出栈和控制的转移。

非局部名字的访问

如何处理非局部名字的应用取决于作用域规则：

• 静态作用域规则：词法作用域规则、最近嵌套规则：由程序中名字的声明的位置决定
• 动态作用域规则：由运行时最近的活动决定应用到一个名字上的声明

对于非局部名字的访问通过访问链来实现，因此关键是如何创建、使用、维护访问链。

程序块

程序块时符合语句的基本结构：

begin
	声明语句
	语句序列
end

块之间的关系可以使并列和嵌套。

参数传递机制

中间代码生成

中间代码生成的任务是将分析之后得到的源程序的中间表示形式翻译成中间代码表示。

使用中间代码的缺点：

• 便于编译程序的建立和移植，可以将编译程序分离为前端和后端两个部分，针对不同的语言可以复用针对同一个机器的后端，针对不同的机器可以复用针对同一个语言的前端。
• 便于记性于机器无关的代码优化工作。

但是使用中间代码的表示增加了IO操作的数量，编译程序的效率有所降低。

中间代码形式

图形表示形式

分成两种形式：

• 语法树：描绘了源程序的自然层次结构
• DAG图：以更紧凑的形式给出了和语法树相同的信息，公共子表达式也被标示出来

三地址代码

使用三地址语句组成的代码描述中间代码。

三地址语句是一种类似于汇编语句的代码，有赋值语句和空间语句，语句可以有标号。三地址语句的一般形式为： $$x:=yopz$$ 其中x可以是临时变量或者是名字，y和z可以是名字、常数或者是临时变量。op是运算符号，如算数运算符或者是逻辑运算符。语句中最多有三个地址。

三地址语句的种类和形式如下所示：

1. 简单赋值语句：

   x := y op z

   x := op y

   x := y

2. 含有变址的赋值语句：

   x := y[i]

3. 含有地址和指针的赋值语句：

   x := &y

   x := *y

4. 转移语句：

   goto L

   if x relop y goto L

5. 过程调用语句：

   param x

   call p, n

6. 返回语句：

   return y

例如，对于赋值语句x := (-y) * z + (-y) * z：

1. 对应语法树的三地址代码为：

   

2. 对于DAG图的三地址代码为：

   

三地址语句的实现

1. 四元式

   使用四元组(op, arg1, arg2, result) 表示。

   例如对于三地址语句x := y + z，其的四元式表示为：

   ('+', y, z, x)
   

2. 三元式

   使用三元组(op, arg1, arg2)表示，相对于四元式省略了返回值的临时变量，减少了符号表的空间，用语句的指针代替存放中间结果的临时变量。

   例如，对于赋值语句x := (-y) * z + (-y) * z:

   

3. 间接三元式

   为三元式的序列增加了一个间接码表，其每个元素依次指向三元式序列中的一个元素。

   对于赋值语句x := (-y) * z + (-y) * z:

   

赋值语句的翻译

布尔表达式的翻译

控制语句的翻译

计算机组成原理课程笔记

大二下学期专业课《计算机组成原理》课程笔记。

授课教师：王玉龙

计算机系统概论

预备知识

组成计算机的硬件设备

• 输入输出设备
• 中央处理设备
• 接口转换卡
• 存储设备
• 部件连接线

一个完整的计算机系统应该包括硬件系统和软件系统两个部分。

计算机的分类

• 数字计算机：处理数字量的信息，按位进行计算

  • 专用计算机：针对某一任务设计的最有效、最经济和最快速的计算机，但是适应性比较差。

  • 通用计算机：适应性很大，但是牺牲了效率、速度和经济性。

    • 单片机
    • 微型机
    • 服务器
    • 大型机
    • 超级计算机

    从上到小：更加复杂、性能更加强大

• 模拟计算机：处理模拟量系统，数值连续

‍

计算机的发展历史

• 第一代计算机：1946~1957年，电子管计算机
• 第二代计算机：1958~1964年，晶体管计算机
• 第三代计算机：1965~1971年：中小规模集成电路
• 第四代计算机：1972~1990年：超大规模集成电路
• 第五代计算：1991年~，巨大规模集成电路

第一代计算机

采用电子管制造。代表机型：ENIAC​，1946年诞生在宾夕法尼亚大学。

第二代计算机

采用晶体管制造。

摩尔定律：每18个月，集成电路的性能就会提高一倍，价格将下降一半。

半导体存储器的发展

• 磁芯存储器：20世纪50~60年代
• 半导体存储器：1970年出现。

微处理器的历史发展

4004-8008-8080-8086-8088

80286-386TM DX-386TM SX-486TM DX

Pentium- Pentium Pro - Pentium 2 - Pentium 3 - Pentium 4

计算机的性能指标

• 吞吐量：表征一台计算机在某一时间内能狗狗处理得的信息量

• 响应时间：从输入有效到系统产生响应之间的时间度量，用时间单位表示

• 利用率：在指定的时间间隔内，系统被完全利用的时间所占的比率，用百分比表示

• 处理器字长（机器字长）：处理器运算器中一次能够完成二进制运算的位数，比如32位，64位

• 总线宽度：运算器与存储器之间的数据总线宽度

• 主存储器容量：主存储器能存储的二进制数据的位数

• 主存储器带宽：单位时间从主存储器读出的二进制信息量，一般用bit/s​来表示

• 主频/时钟周期：CPU主时钟的频率，其倒数为CPU的时钟周期

• CPU的运算速度：

  • CPU执行时间：CPU执行一般程序所占用的CPU时间

  • CPI：执行一条指令所需要的平均时钟周期数

  • MIPS：每秒百万指令数，也就是单位时间内执行的指令数

    对于标量机，一次运算只能得到一个结构

  • MFLOPS：每秒百万次浮点操作数

    对于向量机：一次运算往往可以得到多个结果

CPU的运算速度可以用以下两种方式来计算：

$CPU时间=\frac{一个程序的CPU时钟周期数}{时钟频率}$

$CPU时间=IC\times CPI\times 时钟周期$

因此CPU时间主要和三个参数有关系：

• 时钟周期的长度是由硬件技术和计算机组成决定的
• CPI是由计算机组成和指令集的系统结构决定
• 指令数是由指令集的系统结构和编译器决定

计算机的硬件

硬件的组成要素

冯诺以曼计算机特点：

• 由运算器、存储器、控制器、输入设备和输出设备五个部分组成

• 存储器以二进制形式存储的指令和数据

• 指令由操作码和地址码组成

• 存储程序并按地址顺序执行

  冯诺以曼计算机的核心设计思想，让计算机自动工作的基础

• 以运算器为核心

而现代计算机和冯诺以曼计算机的主要区别就是现代计算机以存储器位核心。

现代计算机的特点：

• 将运算器、控制器和片内的高速缓存统称为CPU，将CPU，主存储器、输入/输出接口和系统总线统称为主机，其余的设备均为外设

  主机内仅包含主存储器，辅助存储器属于辅助IO

运算器

处理所有的算数及逻辑运算。通常称作ALU​，算数逻辑单元。

• 采用二进制数据进行运算
• 运算器一次可以处理的数据位数成为机器字长
• 机器字长一般为8，16，32，64位，机器字长直接决定运算的精度和能力
• 运算器主要有ALU​和各类通用寄存器构成

存储器

保存所有的程序和数据。

• 二进制形式保存程序和数据
• 存储器是按照存储单元组织的，读写存储单元必须给出单元地址

相关的概念：

• 存储元：用于保存一位二进制数据的物理器件
• 存储单元：能够保存一个字数据的器件，由若干个存储元构成
• 单元地址：能区分每一个存储单元的编号，一般从0开始
• 存储容量：一个存储器能保存的二进制数据量

存储器一般分成几类：

• 外存，又称作辅助存储器，例如磁盘存储器，光盘存储器。但是CPU​不能直接访问外存.
• 内存：也就是主存储器，是半导体，CPU​可以直接访问

还有两个和内存相关的寄存器：

• ​MAR​，存储器地址七寸其，接受由CPU送来的地址信息
• ​MDR​，存储器数据寄存器，作为外界与存储器之间的数据通路

控制器

根据所要执行指令的功能，按顺序发出各种控制指令，协调各个部件的工作。

主要的任务是：

• 解释并执行指令
• 控制指令的执行顺序
• 负责指令执行过程中，操作数的寻址
• 根据指令的执行，协调相关部件的工作

其中指令一般的形式为：

操作码+地址码

• 操作码：指出指令锁进行的操作，如加减，数据传送

• 地址码：指出进行以上操作的数据存放位置

存储器的工作周期：

• 取值周期：取指定的一段时间
• 执行周期：执行指令的一段时间

使指令按照顺序指定的控制部件：指令计数器。每取出一条指令，指令计数器就加一步（一条指令的字节数）。如果遇到转移类的指令，控制器根据所执行的指令设置指令计数器的值。

其中相关的概念有：

• 数据字：该字代表要处理的数据
• 指令字：该字为一条指令
• 指令流：取值周期中，从内存中读出的信息流
• 数据流，执行周期中，从内存中读出的数据流

适配器和输入输出设备

输入设备：将么某种信息形式转换为机器能够识别的二进制信息的设备。

输出设备：将计算机处理的结果变成人或者其他机器设备所能够接受和识别的信息形式的设备。

适配器：保证外围设别用计算机系统特性要求的形式发送或者接受信息。

系统总线：将计算机各个部分连接在一起，并且提供数据传送的功能。

计算机中的软件

系统程序

用来简化程序设计，简化使用方法，提高计算机的使用效率，发挥和扩大计算机的功能及用途。

比如操作系统。

应用程序

用户为了解决实际问题而编写的软件。

计算机系统的层次结构

从不同角度看到的计算机的构成

• 微程序设计级
• 一般机器级
• 操作系统级
• 汇编语言级
• 高级语言级

软件与硬件的逻辑等价性

硬件：计算机系统的电子电路

软件：编写的程序

固件：通常存储在ROM​中的软件，可以当作硬件来使用

运算方法和运算器

数据的类型

在日常生活中通常使用十进制，但是十进制在计算机中实现非常的困难。

二进制在计算机系统中占用的存储空间小，在硬件上易于实现，易于计算。

十六进制便于用来表示二进制数，因为一位十六进制数恰好就是4位二进制数。

定点数：小数点位置固定的数，数据表示的范围比较小。

浮点数：小数点位置不固定，数据表示的范围很大。

无符号数：所有位均表示数值，直接用二进制数表示。

有符号数：有正负之分，一般最高位表示符号位，剩下的位数是符号位。

定点数

小数点固定在某一位置的数据。

通过约定小数点在某一个固定的位置，小数点之前为2的正次幂，小数点之后为2的负次幂。

小数点的位置是事先约定的，实际上不用保存小数点的信息。

数的机器码表示

1. 原码表示法

   $$x_n{x}_{n-1}\cdots x_1{x}_0$$

   第一位是符号位，余下的位数才表示数值。

   在这种表示法中，0存在着两种表示方法，+0​和-0​。

   这种表示方法非常的简单，但是才参与运算非常的复杂。

2. 补码表示法

   在计算机中的运算都有最大的范围，从数学上来说就是含有模运算。

   $$[x{]}_{补}=(2^n-x)mod{2}^n$$

   从二进制的角度上来说，补码一般就是数值部分的反码加1。

   补码不影响加减运算，也就是补码的加减等于加减的补码。

   0具有唯一的表示。

   最小值的补码和原值一样，补码的补码是原码。

   求相反数的补码：对原数的补码每位求反再加1，注意这里需要对符号位也取反。

3. 移码表示法

   通常用在表示浮点数的阶码，用定点整数形式的移码，把真值平移$2^n$个单位。

   $$[x{]}_{移}=2^n+x$$

   同补码直接只有符号位取反的区别。

浮点数

小数点的位置可以变化，如同科学计数法中的数据表示。

$$N=R^e\times M$$

• M​​称做尾数，为一个纯小数，表示数据的全部有效数位，决定着数值的精度
• R​​称做基数，可以取2，4，8，16，表示当前的数制。在计算机中一般默认取2
• e​​称做阶码，为一个整数，表示小数点在数中的位置，决定着数据的大小

浮点数的规格化

当尾数使用原码表示的时候：

• 尾数数值最高位一定是1
• 尾数形如0xxxxx(正)或者1xxxxxxx(负)
• 这样做能让表达的精度更高

当尾数使用补码表示的时候：

• 尾数的最高数值位和尾数符号位符号相反
• 尾数就会形如01xxxxxx（正）或者10xxxxxx（负）

浮点数的表示范围

​

‍

浮点数存在上溢出和下溢出两种情况。

上溢出：阶码大于所能表示的最大值，表示无穷

下溢出：阶码小于所能表示的最小值，表示0

当尾数为0或者阶码小于所能表示的最小值时均表示0

浮点数的最值

阶码采用移码，表示范围是：

$$[-2^m,+(2^m-1)]$$

尾数采用补码，表示范围是：

$$[-1,(1-2^{-n}]$$

在实际做题中，不同的题目不同字段的含义可能不同。

IEEE754 浮点数

该标准规定了32位浮点数和64位浮点数。

32位浮点数

​

• 符号位表示浮点数的符号。0表示正数，1表示负数
• 尾数：23位。原码纯小数表示，小数点在尾数的最前面。由于规格化的要求，最高位应该始终为1，因此标准中隐藏了这个值，实际值应为1.M​
• 阶码：8位，采用有偏移值和移码表示，移动的位数是127。

$$(-1{)}^S\times (1.M)\times 2^{E-127}$$

64位浮点数

• 符号位的规定和32位时的情况是一致的。
• 尾数：52位。
• 阶码：11位，移动的位数为1023。

特殊数据的表示

‍

十进制数串的表示方法

采用字符串的形式来表示：

• 每个十进制数位使用一个字节来表示
• 需要注明串的起止位置和长度

采用8421BCD​码表示。

字符和字符串的表示方法

字符一般采用ASCII​码的方式表示。

字符串就是一串连续的字符，每个字节存储一个字符。

数据传输中的校验

为了避免在删除传输的过程中发生错误，在数据的编码上添加检错和纠正的能力。

数据校验的基本原理是扩大码距。

奇偶校验码

在数据中增加一位冗余位，将码距从1增加到2。

如果编码中发生了奇数个错误，就可以被发现。

奇偶校验有着两种类型：

• 奇校验：每个字中包含1的数目是奇数
• 偶校验：每个字中包含1的个数是偶数

在发送方发送数据之前，按照提前约定的校验类型在数据后添加校验位。接收方接受数据之后按照于约定的校验方式进行校验。

定点加法减法运算

补码加法

加法的补码就是补码的加法。

补码的减法

相反数的补码就是补码的相反数。

定点数的乘除法

串行乘法

如图，乘数是0.1011，那么总共四轮，从低位往高位看。初始我们取部分积为0

乘数最低位是1，所以第一轮，部分积=0+A。然后将部分积右移一位

第二轮，同上

第三轮，乘数的对应位是0，所以部分积不变，只有右移一位的操作。第四轮同第一轮，结束

并行乘法

逃课：不去管上面两个图讲的原理是怎么用电路实现的。反正我们考试写过程应该就可以写最后一图，也就是我们普通的计算多位数乘法时的方式。速通.jpg

若为带求补器的（即可以乘负数的），那么算前取绝对值，然后上述乘。符号位单独运算，算后再根据符号来变成补码

并行除法

加减交替法

应该不考.jpg

浮点数的运算

加法

1.检查0操作数

如有，那不用算了。

2. 对阶

将阶码较小的操作数的阶码放大，同时它的尾数右移对应的位数

3.尾数相加

如题，用双符号位的尾数加起来即可

4. 尾数的规格化

• 首先，如果双符号位出现了10或01这种非法值，那么右规直到合法，同时阶码增加对应的值
• 然后，检查是否符合规格化小数的要求，比如00.001001，小数点两边相同，那么就左规直到不同（即00.100100），阶码对应。（就是正数的前缀0和负数的前缀1其实在浮点数里都没有表示实际的意义，可以直接移位消掉）

5. 尾数的舍入

• 尾数最后一位恒置为1
• 或者看一下前面操作过程中（可能的）右移出去的内容，0舍1入——此时可能再次导致尾数溢出从而右规，比如00.1111，舍入+1

6. 阶码的溢出检查

若阶码下溢，置0返回

若阶码上溢，报告异常

结束

减法

即加上减数的补码，略

乘法

阶码相加，尾数用定点数的相乘

除法

阶码相减，尾数用定点数的相除

指令系统

指令系统的发展与性能要求

指令系统的发展

程序：用于解决实际问题的一系列的指令。

指令：使计算机执行某种操作的命令。

从组成的层次结构来说，计算机中的指令可以分为以下几类：

• 微指令：微程序级的命令，属于硬件层级

• 机器指令：简称指令。可完成一个独立的算术或者逻辑指令

• 宏指令：由若干条机器指令组成的软件指令，属于软件

指令系统：一台计算机中所有机器指令的集合。直接影响机器的硬件结构、软件结构以及机器的使用范围。

计算机指令系统的发展过程

• 50年代：

  只有定点加减、逻辑运算、数据传送、转移等几十条指令

• 60年代后期：

  增加了乘除指令，浮点运算、十进制运算，字符串处理等指令，指令数量大大增加，寻址方式也趋向于多样化。

  出现了系列计算机。

  系列计算机简介：

  基本指令系统、基本系统结构相同的一系列计算机，但是具体的器件、结构和性能不会完全相同。一般来说，新的机种在各种方面优于原来的机种

  一个系统往往有多种型号，但是都是向后兼容的。

• 70年代中期：

  复杂指令系统计算机CISC

  采用复杂的指令系统，来达到增强计算机的功能，提高机器速度的目的。

  精简指令系统计算机RISC

  从简化指令系统和优化硬件设计的角度来提高系统的性能与速度。

指令系统性能的要求

指令系统的性能决定了计算机的基本功能，关系到计算机的硬件结构和用户的需求。

完善的指令系统应该满足以下的要求：

• 完备性：常用指令齐全，编程方便

• 有效性：程序占用内存少，运行速度快

• 规整性：指令和数据的使用规则统一，易学易记

  规整性包括对称性，匀齐性，指令格式和数据格式的一致性。

  • 对称性：所有指令都可以使用各种寻址方式

  • 匀齐性：一种操作性质的指令可以支持各种数据类型

  • 指令格式和数据格式的一致性：指令长度和数据长度有一定的关系

• 兼容性：同一系列的计算机均可以运行编写的程序

低级语言与硬件结构的关系

低级语言：面向机器的语言，和具体机器的指令系统密切相关。

指令格式

指令的一般格式

指令字：表示一条指令的机器字

指令格式：用二进制代码表示的指令字结构形式，由操作码字段和地址码字段组成。

操作码：表征指令的操作特性与功能

地址码字段：通常指令参与操作的操作数的地址

操作码

操作码字段的位数取决与指令系统的规模。

操作码可以分成两种类型：

• 固定长度的操作码：

  所有指令的长度均相同。

  控制简单，速度快，适用于指令条数不多的场合。

• 可变长度的操作码：

  频繁使用的指令用位数较少的操作码。

  不常使用的指令可利用操作码扩展技术进行扩展。

  充分利用软硬件资源，适用于大规模的指令系统。

地址码

一条指令格式中有几个地址码字段，就称为是几地址指令。

• 零地址指令

  

  没有任何操作数运算，比如NOP。

  单操作数运算，隐含了一个操作数，比如CBW。

• 一地址指令

  

  单操作数运算: OP(A1)-> A1

  双操作数运算，但是隐含了一个操作数

• 两地址指令

  

  (A1) OP (A2)->A1

• 三地址指令

  

  (A1)OP(A2)->A3

• 多地址指令

  这类指令功能比较强，一般用于中大型机，用于实现批数据处理，字符串处理或者向量和矩阵运算。

两地址指令的分类

一般根据操作数的物理位置分。

• 存储器——存储器

• 寄存器——寄存器

• 寄存器——存储器

指令的操作码扩展技术

在指令系统中，如果操作码的长度固定但是指令格式不同，那么对于地址码较少的指令就存在编码浪费。

因此就诞生了操作码扩展技术：

• 对于不需要某个地址码的指令，将它们的操作码扩充到地址字段

操作码扩展技术即充分利用指令字的各字段，又在不增加指令长度的情况下扩展操作码的长度。

指令字长度

机器字长：运算器一次能处理的二进制数的位数。

机器指令的长度直接决定着CPU运算的精度和直接寻址的能力。

指令字长：一个指令字中包含二进制代码的位数。指令字长由操作码长度、操作数个数和个数共同决定。

指令含有半字长、单字长、双字长、多字长等不同的长度类型。

指令系统可以分为等长指令字结构、变长指令字结构。

指令助记符

使用3~4个英文缩写字母来表示的指令操作码。

在不同的计算机中指令助记符的规定是不一样的。

操作数类型

机器指令对数据进行操作，数据通常分为以下四类：

• 地址数据：无符号整数，通过某种运算确定操作数在主存中的有效地址

• 数值数据：定点整数，小数，浮点数

• 字符数据：文本数据或者字符串

• 逻辑数据：由若干二进制位组成

指令和数据的寻址方式

指令的寻址方式

1. 顺寻寻址方式

   当程序按顺序执行时的指令寻址方式。

   需要用程序计数器PC记录所要执行指令的存放单元地址。

   • 一般做顺序加1的操作，这里的“加1”表示加上指令的长度。

   • 程序计数器又称做指令指针寄存器。

2. 跳跃寻址方式

   当程序转移控制执行时的指令寻址方式。

   程序计数器的内容由本条指令提供，而不是顺序改变。

操作数的寻址方式

一种单地址码指令的结构如图所示：

将指令中的形式地址变换为操作数有效地址的过程就是寻址过程。

隐含寻址

操作数地址隐含在操作码中。在指令字中减少了一个地址字段，可以缩短指令字长。

立即寻址

形式地址就是操作数。

指令执行阶段不需要访存，速度快，但是形式地址字段的位数限制了立即数的范围。

直接寻址

有效地址由形式地址字段直接给出。

在执行结构需要访问一次存储器，形式地址的位数决定了指令操作数的寻址范围，而且操作数的地址不易修改。

间接寻址

有效地址由形式地址字段简介提供。

可以扩大寻址的范围。寻址时，可以根据需要进行多次间接寻址，存在一个寻址特制字段区分直接寻址和间接寻址。

寄存器寻址

形式地址字段为寄存器的编号。

在执行阶段不需要访存，只访问寄存器，执行速度较快。寄存器的个数有限，可以缩短指令的字长。

寄存器间接寻址

形式地址字段用于指出存放有效地址的寄存器编号。

在执行阶段需要访问内存，便于编写循环的程序。

偏移寻址

常用的偏移寻址：

• 相对寻址：指令转移发生的时候常用。

  Address=A+(PC)

• 基址寻址：

  Address=(R)+A，其中A每次加1

• 变址寻址：

  Address=A+(R)，其中R每次加1

典型指令

老师说讲题更重要，所以没讲。

本章练习题

设计指令系统

按照操作码的长度分别设计。

计算程序计数器的值

计算本身简单，但是需要考虑指令的长度。

计算不同操作数指令的最大数量

不同寻址方式设计指令格式

中央处理器

中央处理器的组成和功能

CPU的功能

中央处理器：控制程序按设定方式执行。

CPU的主要功能：

• 指令控制：顺序寻址和跳跃寻址

  控制程序的执行顺序

• 操作控制：对指令操作码译码之后产生控制信号。

  产生和发送各操作信号

• 时间控制：维持各类操作的时序关系

  控制指令或操作的实施时间

• 数据加工：ALU完成具体的运算

  对数据进行算术和逻辑运算

CPU的基本组成

现代CPU的组成：运算器、控制器、片内cache

控制器的主要功能：

• 从内存中取出一条指令，并指出下条指令的存放位置

  PC， IR寄存器

• 对指令进行译码，产生相应的控制信号

• 控制CPU、内存和输入输出设备之间的数据流动

运算器的主要功能（ALU、DR、寄存器组）：

• 执行所有的算术运算

• 执行所有的逻辑运算并进行逻辑测试

CPU中的主要寄存器

1. 数据缓冲寄存器DR

   运算器使用。ALU的缓存，一切待运算数据先存放到DR，然后送入寄存器组，然后送给ALU

   暂时存放ALU的运算结果或者CPU与外界传输的数据

   • 作为ALU运算结果同通用寄存器之间的信息传送中时间上的缓冲

   • 补偿CPU和内存、外围设备之间在操作速度上的差别

2. 通用寄存器

   如x86的%rsp、%rdi、%rax等

   暂时存放ALU的运算结果或者运算数据

3. 状态条件寄存器PSW

   保存各种状态和条件控制信号，例如进位标志C，溢出标志V

   每个信号由一个触发器保存，从而拼成一个寄存器

4. 地址寄存器AR

   存放待访存的地址。如（R1）则先将R1寄存器的值移到AR，然后根据此地址去内存（实为cache，但是可以当成内存）中读数，然后送DBUS、DR、PC等

   保存当前CPU所访问数据的内存单元地址。

   主要用于解决主存/外设同CPU之间的速度差异，使地址信息能够保持到主存/外设的读写操作完成

5. 程序计数器PC

   始终存放下一条指令的地址，对于指令Cache的访问

   内容变化有着两种情况：

   • 顺序执行：PC+1->PC

   • 转移执行：指令->PC

6. 指令寄存器IR

   控制器使用。存放待执行指令，OP部分送去译码，然后给出控制信号，地址码部分送到DBUS

   保存当前正在执行的指令

   指令寄存器中操作码字段的输出就是指令译码器的输入

操作控制器与时序产生器

数据通路：寄存器之间传送信息的通路

操作控制器：根据指令操作码和时序信号，产生各种操作控制信号。建立正确的数据通路，从而完成指令的执行。

• 硬布线控制器：利用时序逻辑实现

• 微程序控制器：采用存储逻辑实现

• 前两种方式的结合

时序控制器：对各种操作实施时间的限制。

指令周期

指令周期的基本概念

CPU执行程序是一个”取指令-执行指令“的循环过程。

指令周期：CPU从内存中取出一条指令并执行的时间总和。

CPU周期：机器周期，一般为从内存中读取一条指令字的最短时间。一个CPU周期可以完成CPU的一个基本操作。

时钟周期：也叫节拍脉冲或者T周期，是计算机处理操作的基本时间单位。

一个完成的指令周期由若干机器周期构成：

取值周期->间值周期->执行周期->中断周期

本教材上间址周期和执行周期统称为执行周期。

MOV R0, R1指令的指令周期

mov是一条RR型指令，它需要两个CPU周期。

• 取值周期：从储存器中取出指令，程序计数器加1，译码或者测试指令操作码，输出控制信号。

  1. PC->指令Cache, 译码并启动

  2. 指令Cache->ABUS->IR

  3. PC->PC+1, 为取下一条指令做好准备

  4. IR中的操作码被译码或者测试，识别出是指令mov

• 执行周期：在控制信号的作用下，将R1中的数据通过ALU送入R0

  1. R1->ALU, 数据是通过ALU传送的

  2. ALU->DBUS->DR->R0

LAD R1, 6指令的周期

LAD指令是RS型指令，需要方寸获取操作数，共包含三个CPU周期。

• 取值周期

• 间址周期：从IR的地址码字段获得操作数的地址

  1. IR->DBUS->AR 该过程为寻址周期

  2. AR->ABUS->数据cache 译码并启动

  3. 数据cache->DBUS->DR->R1

• 执行周期：访存获取操作数送入通用寄存器

ADD R1, R2指令的指令周期

ADD指令的指令周期由两个CPU周期组成。

• 取值周期

• 执行周期

  1. R1, R2 -> ALU

  2. ALU 进行加运算，将两数相加

  3. ALU->DBUS->DR->R2，保存结果

STO R2, (R3)指令的指令周期

STO指令是RS型指令，需要3个CPU周期。

• 取值周期

• 间址周期：根据R3中的地址寻址所要访问的存储单元

  1. R3->DBUS->AR, 发送地址启动数据Cache

  2. R2->DBUS->数据Cache

• 执行周期：将寄存器R2中的数据送入指定的存储单元

JMP 101指令的指令周期

JMP指令是一条无条件转移指令，用来改变程序的执行顺序

• 取值周期

• 执行周期：使用JMP指令中的直接地址为PC赋值

  IR->DBUS->PC

用方框图语言表示指令周期

方框：代表一个CPU周期，内容表示数据通路的操作或者某种控制操作

菱形：通常表示某种判别或者测试，时间上依附于之前一个方框的CPU周期，而不单独占用一个CPU周期

公操作符号~：表示一条指令已经执行完毕，转入公操作

所谓公操作就是对一条指令执行完毕之后，CPU所开始的一些操作，比如对外围设备请求的处理等

微程序控制器

微程序控制原理

微命令和微操作

是控制部件和执行部件之间的联系，包括发出控制信号和返回状态信息。

• 微命令：控制部件通过控制线向执行部件发出的各种控制命令

• 微操作：执行部件接受微命令之后执行的操作

• 状态操作：执行部件通过反馈线向控制部件告知当前状态，方便决定下一步的操作

微命令就是控制电路中一个个不同的控制信号。

微操作可以分为：

• 相容性微操作：在同时/同一个CPU周期内可以并行执行的微操作
• 相斥性微操作：不能在同时或不能在同一个CPU周期内并行执行的微操作

微指令和微程序

微指令：在一个CPU周期内，实现一定操作功能的一组微命令的组合。

• 操作控制：用于管理和指挥全机工作的控制信号
• 顺序控制：用于决定产生下一条微指令的地址

微指令都在存储控制器中存储，使用地址微地址访问。

每段机器指令都对对应这一段微程序，而微程序就是实现一条机器指令的多条微指令序列。

微指令的基本格式

微程序控制器原理

• 取指微指令是所有指令的公用微指令，通常存放在0000的位置，所有机器指令的最后一条微指令的直接地址都指向这个地址单元，用来取下一条微指令。
• 取得机器指令之后，经过p1测试——操作码测试，产生对应的微程序入口指令，并送入微地址寄存器。
• 指令执行的过程中，通过p2测试，修正下一条微指令的地址，逐条读取微指令执行。
• 执行完对应于一条机器指令的微程序之后，返回到取值微指令，不断重复知道程序执行完成。

机器指令与微指令的关系

一条机器指令对应一个微程序，一个微程序由若干条微指令序列组成的。

指令存储在内存中，而微指令存储在控制存储器中。

每一个CPU周期对应一条微指令。

微程序设计技术

微命令编码

微指令中操作控制字段的编码表示方法，以及如何将编码翻译到对应的微指令。

采用编码表示微指令的原因主要是：

• 有效缩短微指令字长
• 缩短微程序的长度，减小所需的空存空间
• 提高微程序的执行速度

一般常用的微命令编码方式有以下三种：

1. 直接表示法

   操作控制字段中的每一位代表一个微命令。

   简单直观，输出直接用于控制，执行速度快。但是微指令比较长，似的控制存储器的容量必须比较大。

2. 编码表示法

   将微指令操作控制字段划分为若干个子字段，将每个子字段的所有微命令统一编码，每个子字段的不同编码表示不同的微命令。

   其中设计编码还需要满足下面这些要求：

   • 把相斥的微命令划分到同一个字段，相容的微命令划分到不同的字段。

   感觉设计子字段的目的就是为了方便相容指令的并行

   • 字段的划分应该和数据通路相吻合
   • 每个子字段应该留出一个空操作状态
   • 每个子字段所定义的微命令不宜太多

   使用这种方式可以大大缩短微指令的字长，但是在执行过程中需要对微命令进行译码，所以执行的速度会较慢。

微地址的形成方法

• 微程序的入口地址：微程序的第一条微指令所在控存单元的地址
• 现行微指令：在执行微程序的过程中，当前正在执行的微指令，这个指令的地址就是先行微地址
• 后继微地址：现行微指令执行完之后再执行的微指令地址

确定下一条微指令地址的方法：

1. 计数器方式

   同CPU中程序计数器产生机器指令地址的方法类似。

   这样微指令的顺序控制字段较短，微地址产生结构简单，但是多路并行转移的功能比较弱，速度慢，灵活性差。

2. 根据判断测试标志和状态条件信息选定某一个候选微地址的方法。

   这种方法能够以较短的顺序控制字段配合，实现多路并行，灵活性比价好，速度快，但是转移地址的逻辑需要比较复杂的组合逻辑实现。

微指令格式

微指令格式有以下两种：

1. 水平型微指令：

   一次能定义并执行多个并行操作微命令的微指令。一般有操作控制字段，判断测试字段和下地址字段构成。

   根据控制字段编码方式不同，可以分为全水平型，字段译码水平型和直接译码混合型。

2. 垂直型微指令

   类似于机器指令的结构，设置微操作码字段，采用微操作码编译法，由微操作码规定微指令的功能。

水平型微指令并行操作能力比较强，执行一条指令的时间段，而垂直型微指令则较差。

但是由水平型微指令解释指令的微程序，微指令字比较长但是程序短，而垂直型刚好相反。

垂直型微指令和指令相似，利于用户掌握。

动态微程序设计

1. 静态微程序设计：

   对于一台计算机的机器指令只有一组微程序，而且设计好之后，无需改变也不易改变。

2. 动态微程序设计：

   通过改变微指令和微程序来改变机器的指令系统

硬布线控制器

直接用组合逻辑完成从指令到微命令的控制器。

同微程序控制器相比，硬布线控制器更快。

流水线CPU

并行处理技术

并行性具有两种含义：

• 同时性：两个以上事件在同一时刻发生
• 并发性：两个以上事件在同时间间隔发生

并行性具有三种形式：

• 时间并行：使用流水处理部件，时间重叠
• 空间并行：设置重复资源，同时工作
• 时间并行和空间并行

对于微指令来说：

流水CPU的结构

流水计算机的系统组成

指令部件：本身构成一个流水想，由取指令、指令译码、计算操作数地址、去操作数等过程段组成。

指令队列：指令队列是一个先进先出的寄存器队列，用于存放经过译码的指令和取来的操作数。

执行部件：执行部件可以具有多个算术逻辑运算部件，这些部件本身又用流水线方式构成。

主存采用多体交叉存储器，以提高访问速度。

执行段的速度匹配问题：

将执行部件分成定点执行部件和浮点执行部件两个可并行执行部分，在浮点执行部件还可以分成浮点加法部件和浮点乘除部件，他们也可以同时执行不同的指令。

浮点运算部件本身也是流水线。

这样基本上解决了执行速度不匹配的问题。

流行CPU的时空图

流水线具有下面三种特点：

• 一般流水线pipeline：只有一条指令流水线
• 超流水线superpipeline：多级流水线，每个阶段内部还可以继续划分
• 超标量流水线superscale：具有两条以上的指令流水线

流水线分类

流水线可以分成以下三类：

1. 指令流水线：指令执行的并行处理。

   指令流水线可以划分成取值、译码、取操作数、执行和写回等等过程。

2. 算术流水线：在运算步骤中的并行处理

   为了提供速度，现代计算机多采用流水的算术运算器，而不是传统的组合逻辑。

3. 处理机流水线：程序步骤的并行处理。

   将每一阶段的处理分散在不同的计算机上。

流水线中的主要问题

在设计流水线CPU是，会遇到不少的问题，我们分成几个不同的类别来查看。

• 资源相关的问题：

  多条指令进入流水线后在同一机器时钟周期内争用同一个功能部件造成的冲突。

  解决这类问题的思路：

  • 推迟指令的执行
  • 设置重复的资源

• 数据相关的问题：

  在一个程序中，必须等待上一条指令执行完毕之后才能执行下一条指令，例如下一条指令使用了上一条指令得到的结果。

  数据相关有着三种不同的类型：

  • 先读后写：前一条指令读取某一个数据，后一条指令写入这个数据，但是在异步执行的过程中，后一条指令写入数据可能会发生在前一条指令读取数据之后，造成程序执行错误。
  • 写写：前后两条指令都会写入同一个数据单元，但是由于在异步执行的过程中后一条指令可能优于前一条指令执行，导致最后该数据单元的数据和期望的不同。
  • 先读后写类似。

  解决这类问题的思路：

  • 推迟指令的执行
  • 定向传送技术

• 控制相关的问题：

  在执行转移指令是，根据转移条件是否发生来控制指令的执行顺序。

  解决这类问题的思路：

  • 延迟转移法
  • 转移预测法

存储系统

存储器概述

存储器分类

按存储介质分类：

• 半导体存储器：使用MOS管组成的存储器
• 磁表面存储器：使用磁性材料做成的存储器
• 光盘存储器：使用光介质构成的存储器

按存取方式分：

• 随机存储器：存取时间和存储单元的物理位置无关：比如半导体存储器

• 顺序存储器：存取时间和存储单元的物理位置有关：比如磁盘存储器

• 半顺序存储器：存取时间部分依赖于存储单元的位置：硬盘

按照存储内容可变性分：

• 只读存储器ROM​
• 随机读写存储器RAM​

按信息易失性分：

• 易失性存储器：断电后信息即消失的存储器
• 非易失性存储器：断电后仍能保存信息的存储器

按在计算机系统中的作用：

• 主存储器：能够被CPU直接访问，速度较快，用于保存系统在当前运行所需的所有程序和数据。一般情况下使用半导体存储器实现。

• 辅助存储器：不能被CPU直接访问，速度较慢，用于保存系统中所有的程序和数据。

• 高速缓冲存储器：能够直接被CPU访问，速度快，用于保存系统当前运行中频繁使用的程序和数据。

• 控制存储器（寄存器）：CPU内部的存储单元。

存储器的分级结构

计算机对存储器的要求：大容量、高速度和低成本。为了解决这个问题，提出了计算机的分级存储结构。

计算机中有着三级存储结构：

缓存——主存结构

主存——辅存结构

1. 加上缓存cache​的目的是提高速度
2. 内存包括缓存和主存
3. 多层次的存储结构降低了成本，提高了容量

但是采用分级结构需要解决一些问题：

• 从辅存中寻找指定的内容放入主存应该如何定位？
• 当CPU访问缓存而需要的内容并不在缓存中，应该如何处理？

以上的问题由操作系统解决

主存储器的技术指标——存储容量

存储容量：存储器中能存放的二进制代码总量

$$存储容量=储存单元个数\times 存储字长$$

主存储器的技术指标——存储速度

存取时间：从启动一次访问操作到完成该操作为止所经历的时间。一般以ns​为单元，分为读出时间和写入时间。

存取周期：存储器连续启动两次独立的访问操作所需的最小间隔时间。以ns​为单元。

$$存取周期=存取时间+复原时间$$

存储器带宽：单位时间能够读取或者写入的数据量。

$$存储器带宽=\frac{每周期的信息量}{周期时长}$$

存储器容量的扩充

单个存储芯片的容量有限，实际存储器由多个芯片扩展而成。

SRAM、DRAM、ROM均可以进行容量扩充

存储器同CPU的连接

数据、地址、控制三个总线的连接。

那么多个存储芯片同CPU之间的连接应该如何处理？

• 首先不是一一对应连接

• 关注存储器和CPU的外部引脚

• 存储器的容量扩充

存储芯片与CPU的引脚

存储芯片的外部引脚：

• 数据总线：位数和存储单元的字长相同，传输数据信息

• 地址总线，位数和存储单元的个数为$2^n$关系，用于选择存储单元

• 读写信号WE：决定当前对芯片的访问类型

• 片选信号CS：决定当前芯片是否正在被访问

CPU与存储器连接的外部引脚：

• 数据总线：位数和机器字长相同，用于传输数据信息

注意：机器字长和存储单元的字长不一定一致。机器字长往往是存储单元字长的整数倍

• 地址总线：位数与系统中可访问单元个数为$2^n$的关系，用于选择访问单元

• 读写信号WE：决定当前CPU的访问类型

• 访存允许信号MREQ：内存控制器决定是否允许CPU访问内存

存储器容量的位扩展

存储单元数量不变，每个单元的位数增加。

例：将1Kx4的存储器芯片扩展为1Kx8的存储器芯片：

将地址线增加为原来的两倍，将前四根分配给第一个存储芯片，后四根分配给第二个存储芯片。即：

• 各芯片的地址线直接和CPU的地址线相连

• 各芯片的数据线分别和CPU数据线的不同位相连

• 片选信号和读写线直接和CPU的对应接口相连接。

CPU对存储器的访问是对所有扩展芯片的同一单元的同时访问。

存储器的字扩展

每隔单元的位数不变，但是总的单元个数增加。

例如，使用1Kx8的存储芯片构成2Kx8的存储器：

• 各芯片的地址线和CPU的地位地址线相连

• 数据线和CPU的数据线直接相连

• 读写线直接和CPU的读写线

• 片选信号：片选信号由CPU地址的高位地址和访存信号产生

CPU对于存储器的访问是对于某个扩展芯片的一个单元的访问。

存储芯片的字位扩展

每隔存储单元位数和总的单元个数都会增加。

• 首先进行位扩展，得到满足位要求的存储芯片组

• 再使用存储芯片组进行字扩展

因此，需要计算出需要的存储芯片个数。

如果需要利用$L\times K$的芯片构成$M\times N$的存储系统，需要的芯片个数为：

$$\frac{M\times N}{L\times K}$$

存储器容量扩展例题

SRAM存储器概述

SRAM: static Random Access Memory

主存储器的构成

• SRAM：由MOS电路构成的双稳态触发器保存的二进制信息。

  优点：访问速度快，不掉电可以永久保存信息

  缺点：集成度低，功耗大，价格高

• DRAM：用MOS电路中的栅极电容保存二进制信息

  优点：集成度高，功耗低，价格低

  缺点：访问速度慢，电容的放电作用会使信息丢失，需要定期刷新

  可以分为SDRAM，DDR SDRAM。

基本的静态存储元阵列

基本存储元：由6个MOS管组成，可以存储一位信号。

基本存储元组成存储阵列，但是不一定完全完全按照存储单元形式组织

在封装完成之后，阵列会引出三种控制线

• 地址线：确定需要读写的存储单元
• 数据线：输入输出需要读取写入的数据
• 控制线：控制是读取还是写入

地址线的译码方式有两种：

• 单译码：地址由一根地址线直接指定
• 双译码：地址线由两根地址线共同制定

SRAM存储器的组成结构：

• 存储体：存储单元的集合，将各个存储元组成一个存储矩阵。大容量存储器中，通常使用双译码的方式来确定存储单元。

• 地址译码器：将CPU发出的地址信号转换为确定存储单元的信号

• 驱动器

• 片选：确定当前芯片是否被CPU选中

• 读写电路：读写选定的存储单元

读写周期波形图

存储器读写原则：

• 读写信号要在地址信号和片选信号起作用，经过一段时间之后才有效
• 读写信号有效期间不允许地址、数据发生变化
• 地址、数据要维持整个周期内有效

读周期操作过程：

• CPU发出有效的地址信号
• 译码电路产生有效的片选信号
• 读信号控制下，从存储单元中读出数据
• 各个控制信号撤销，数据维持一段时间

读出时间：从地址有效到外部数据总线上数据信号稳定的时间

片选有效时间：从片选信号有效到数据信号稳定的时间

读出信号有效时间：从读出信号到数据信号稳定的时间

​

写周期操作过程：

• CPU发出有效的地址信号，提供需要写入的数据
• 译码电路延迟产生有效的片选信号
• 写信号控制下，数据写入存储单元中
• 控制信号撤销，数据维持一段时间

​

DRAM存储器

DRAM存储器必须定时刷新，维持其中的信息不变。

DRAM的存储元是MOS管和电容组成的记忆电路，利用电容中的电量来表示存储的信息。

DRAM存储元的记忆原理

利用MOS管控制对于电容的充放电，利用电容中的电量来表示存储的信息。

行线（字线）控制MOS管的开关，位线读出电容中的数据。

DRAM控制电路的组成

• 地址多路开关：刷新时需要提供刷新地址，非刷新时提供读写地址
• 刷新定时器：定时进行刷新操作
• 刷新地址计数器：刷新按行进行，对所要刷新的行进行计数
• 仲裁电路：对CPU访问存储器的请求和刷新存储器的请求优先级进行仲裁

DRAM的读写周期

读时序为：

• 行地址信号有效
• 列地址有效
• 读写信号置为读信号
• 输出信号有效

​

写时序：

• 行地址信号有效
• 列地址有效
• 读写信号置为写信号
• 输入信号有效

​

DRAM的刷新周期

在固定的时间内对所有的存储单元，通过读取——写入的方式恢复信息的操作过程，刷新过程中不可进行读写操作。

DRAM的刷新有着以下几种方式：

• 集中式刷新：在一个刷新周期内，利用一段固定时间对存储矩阵中的所有行逐一刷新，在此期间停止所有的读写操作
• 分散式刷新：将系统工作周期分成两部分，前半部分用户读写操作，后半部分用于存储器的刷新
• 异步式刷新：计算需要刷新的频率，在需要刷新的时候再进行刷新操作

ROM存储器

掩模式ROM：数据在芯片制造的过程中写入，不能更改

• 优点：可靠，集成度高，价格比较低

• 缺点：通用性差，不能改写

一次编程ROMPROM:用户第一次使用时写入确定内容

• 优点：用户可根据需要对ROM进行编程

• 缺点：只能编程一次

多次编程ROM：可用紫外光照射EROM或者电擦除EEPROM，多次改写其中的内容

• 优点：通用性好，可反复使用

闪存存储器Flash：一种高密度，非易失性的读写半导体存储器，即常用的U盘

高速存储器

双端口存储器

双端口存储器采用空间并行技术，同一个存储体使用两组相互独立的读写控制线路，可并行操作。

读写特点：

• 无冲突读写：访问不同的存储单元，可以并行读写存储体
• 有冲突读写：访问同一存储单元，通过特定的信号控制读写的先后顺序

多模块交叉存储器

多模块交叉存储器采用时间并行技术。

存储器的有两种模块化的组织方式：

• 顺序方式

  每个模块中的单元地址是连续的。某个模块在进行存取的时候，其他模块不工作，某一模块出现故障，其他模块可以照常工作。

  存储单元的地址就可以分成两部分：高位是模块号，低位是模块内的字号。

  

• 交叉方式

  每个模块的单元地址是不连续的，连续地址分布在相邻的不同模块内。对于数据的成块传送，各模块可以实现多模块流水式并行存取。

  存储单元的地址恰好和顺序方式相反：低位是模块号，高位是模块内的字号。

  

Cache存储器

Cache的基本原理

由于CPU的运算速度越来越快，主存储器的速度和CPU之间的差距越来越大。

基于程序访问的局部性原理，即在一段时间内，CPU所执行的程序和访问的数据大部分都在某一段地址范围内，而在该段范围之外的地址访问很少，在CPU和主存之间加一块高速的SRAM，称为Cache。将主存中将要被访问的数据提前送到缓存中，CPU在访问数据中，优先在缓存中寻找，如果没有命中再到主存甚至更低的存储层次中寻找。

缓存在实现过程中使用结构模块化的思想。CPU访问Cache或者主存时，以字为单位，当Cache和主存交换信息时，以块/行为单位，一次读入一块或者多块内容。此部分完全由硬件实现，对程序员透明。

缓存由以下的几个部分组成：

• 存储体，基本单位为字，若干个字构成一个数据块
• 地址映射变换机构：用于将主存地址变换为缓存地址，以利用CPU发送的主存地址访问缓存
• 替换机构：更新缓存中数据时使用的机制
• 相联存储器，缓存的块表，快速指示所访问的信息是否在缓存中
• 读写控制逻辑

缓存的读操作大致会经过以下几个步骤：

1. CPU发出有效的主存地址

2. 经过地址变换机构，成为可能的缓存地址

3. 查找块表，判断访问的信息是否在缓存中

4. 如果在，CPU直接读取缓存获得数据

   如果不在，CPU访问主存，并判断缓存是否已满。如果缓存未满，将该数据所在块放入缓存中，如果缓存已满，使用某种替换机制，使用当前数据块替换缓存中的某些块

缓存的写操作：

1. CPU发出有效的主存地址

2. 经过地址变换机构，称为可能的缓存地址

3. 查找相联存储器，判断访问的信息是否在缓存中

4. 如果不在，则CPU直接写入主存

   如果不在，使用某种写策略将数据写入缓存

判断缓存性能由两个指标：

• 命中率：CPU要访问信息在缓存中的比率
• 主存系统的平均访问时间

“cache-主存系统的效率”：用$\frac{cache的访问时间}{平均访问时间}$来衡量，通常为百分比，越接近100越好

主存到缓存中的地址映射

全相联映射

主存中的任意字块可调进缓存中的任一行中。

使用这种方式的块表就是缓存行号和主存块号的对应表，因此块表的大小就是缓存中行的数量乘以主存块号的长度。

这种方式的优点是灵活性号，在缓存中只要存在空行，就可以调入所需要的主存数据块。

缺点比较多：

• 成本高，标记需要的位数比较多，使得缓存的标记容量变大
• 速度慢，访问缓存时需要同所有的标记进行比较，才能判断出所需要的数据是否在缓存中

直接映射

主存中的每一块数据只能调入缓存的特定行中。

有点类似于将缓存当作一个哈希表来使用：如果主存的块号为i，缓存的行数为c，那么主存当前行号对应的缓存行号为： $$imodc$$

直接映射的优点是映射函数的实现简单，查找速度快，但是灵活性差。

组相联映射

组相联映射是直接映射和全相联映射的一种折中方案。

将缓存中的行等分为若干组，主存中的每一块只能映射到缓存中的特定组中，但是可调入该组中的任一行中。也就是组间为直接映射，组内为全相联映射。

一般上缓存中的一组含有r行时，称为r路组相联映射。

缓存的替换策略

1. 最不经常使用算法LFU

   将一段时间内被访问次数最少的那行数据替换出去。

   为每行设置一个计数器，每访问一次，被访问行的计数器自增，当需要替换时，将计数值最小的行换出，清空计数器。

   缺点：这种算法将技术周期限制在对这些特定行的两次替换中，不能严格反映近期访问情况

2. 近期最少使用算法LRU

   将近期内长久未使用的行替换出去。

   为每行设置一个计数器，没访问一次，将被访问行的计数器清空，其他行自增。在需要替换时，将计数器最大的行替换出去。

   这种方式保护了刚进入缓存的新数据行，效率高。

3. 随机替换算法

   随机选一行替换。

   在硬件上容易实现，速度也快，但是命中路和工作效率低。

缓存的写策略

修改缓存中的内容之后，需要将数据写入主存中保存起来。

1. 写回式

   只修改缓存中的内容，不立即写入内存，只有当该行被替换时才写入内存。

   减少了访问内存的次数，但是存在缓存和主存不一致的问题。且需要设置一个标志位，标识这个行是否被修改过。

2. 全写式

   缓存和主存同时发生写修改，维护缓存和主存的一致性。

   缓存的功效被降低，但是实现简单。

3. 写一次式

   基于写回法，但是结合了全写法的特点。

   在第一次写命中的时候，写入主存。

   第一次写命中时，启动一个主存的写周期，目的是其他缓存可以及时更新或者废止该块内容。

虚拟内存

别的班都讲了在复习，就我们没有讲。赌一把它不考

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

输入输出设备

外围设备的速度分级与信息交换方式

外围设备的速度分级

根据外设的工作射速，CPU和外设的定时方式有三种：

• 速度极慢或者简单的外围设备，使用CPU世界接收和发送数据

  机械开关和LDE

• 慢速或者中速的外围设备，采用异步定时方式/应答式数据交换，CPU与外设之间通过两个相互的联络信号来决定开始数据传送的时间

  键盘，显示器

• 高速的外围设备，采用同步定时的方式，CPU以等间隔的速度执行输入/输出指令

  主存，辅存

外设信息交换方式

• 程序查询方式

  早期计算机中使用，效率低。

• 程序中断方式

  适用于随机出现的服务

• 直接内存访问DMA方式

  适用于内存和高速外围设备之间大批量数据交换的场合

• 通道方式

  增加一个具有特殊功能的处理器——通道，将CPU输入输出的权力下方

程序查询方式

数据的输入输出完全由程序控制。

设备编制

1. 统一编址方式

   将I/O系统与主存系统作为一个整体进行编址。

   访问I/O端口可以使用访存指令，操作类型多样，使用灵活，且I/O端口也有较大的编址空间。

   但是占用了主存空间，使得实际主存容量减小。I/O访问的指令字长较长，执行的速度慢。

2. 独立编址方式

   将I/O系统和主存系统分别编址。

   I/O端口不占用主存空间，使用专用的I/O指令，执行速度快，与主存空间容易区分。

输入输出指令

输入指令：IN AL/AX, DX/PORT，从指定的端口读入一个字节/字数到累加器

输出指令：OUT DX/PORT, AL/AX，将累加器中的一个字节/字数送到指定端口输出

指令一般的功能有：

• 对于接口的控制触发器置0或者1，控制其进行某些操作
• 测试设备的某些状态
• 输入或者输出数据

程序查询方式的接口

CPU通过地址信号选中某设备接口。

CPU通过向该接口发送命令字的方式，启动外设。

当外设开始工作之后，设置当前“忙”状态。

CPU和外设通过接口内部的数据缓冲器传送数据。

程序查询输入/输出方式

1. CPU请求数据传送
2. CPU从I/O接口读入状态字
3. 检查状态字中的标志
4. 为就绪，则重复2.3.步
5. CPU输入或者输出数据，同时复位接口中的状态标志。

可以通过改变查寻顺序修改设备的优先权。

程序中断方式

中断的概念

中断是指CPU正常运行程序时，由系统内/外部非预期事件或程序中预先安排好的指令性事件引起的，CPU暂停当前程序的执行，转去为该事件服务的程序中执行，服务完毕后，再返回原程序继续执行的过程。

需要注意的是：

• 中断是CPU执行程序的变化过程
• 所有能够引起中断的事件称为中断源
• 处理中断事件的中断服务程序是预先设计的
• 结束中断处理元程序之后，要以原状态附后返回暂停处继续执行

中断处理过程是由硬件和软件结合来完成的。

使用中断的好处为：

• 解决速度问题，使用CPU和I/O并行工作
• 对于意外的情况可以即使处理，例如磁盘损坏，运算溢出
• 在实时控制领域中，即时响应外来信号的干扰。

CPU的中断处理流程：

1. 中断请求

   CPU在结束一个指令周期后，检测中断请求信号。

   就是CPU的公操作检测保存中断请求信号的寄存器

2. 中断响应

   关闭中断，保护断电现场，判断中断源，获取中断向量，根据中断向量转入中断服务程序运行。

   关闭中断的目的是为了避免再次中断影响当前中断响应，屏蔽中断源。

   保护断电现场是为了CPU还能回到主程序

3. 中断服务

   保护CPU现场，执行中断服务程序，打开中断，恢复CPU现场

4. 中断返回

   恢复断点现场，返回主程序继续执行。

中断向量：中断服务程序的入口地址，一共4个字节的内容，包括段地址和段内偏移地址。在CPU响应中断时，将中断源对应的中断向量送入段地址CS、段内偏移地址IP寄存器中，以跟踪中断服务程序的执行。

集中存放系统中所有中断向量的存储器就是中断向量表。中断类型号是中断向量在表中的编号，乘上中断向量的长度4字节，就是中断向量在表中的偏移地址。

硬件产生中断向量的方式有三种：

1. 向量中断

   由硬件直接产生一个与该中断源对应的向量地址，该向量地址就是中断源对应的中断服务程序入口地址。

   但是这种方式要求在硬件设计时考虑所有中断源的向量地址。

2. 位移量中断

   由硬件产生一个位移量，该位移量加上CPU中某寄存器的基地址就是中断处理程序的入口地址。

3. 向量地址转移

   由硬件直接产生

程序中断方式的基本I/O接口

接口内部有下列组成部件：

• 数据缓冲寄存器
• 就绪触发器RD，忙状态触发器BS，允许中断触发器EI
• 中断向量产生逻辑

CPU中响应的处理部件是

• 中断请求触发器IR
• 中断屏蔽触发器IM

单级中断

计算机系统中一般拥有多个中断。在处理时，有着如下两种处理策略：

• 单级中断：所有的中断源属于同一个中断，不允许有中断嵌套
• 多级中断：中断源分成不同的级别，可以发生中断嵌套，高优先权的中断源请求可以打断低优先权的中断服务

我们先分析单级中断：

在收到中断时识别中断源来源的方法是串行排队链法。

外围设备

外围设备概述

外围设备的一般功能

在计算机系统中，除CPU和主存之外的部件都可看作外设。

外设的功能是在计算机之间、计算机和用户之间提供联系。

外围设备的分类

• 输入/输出设备
• 外存设备
• 数据通信设备
• 过程控制设备

外设都是通过适配器与主机连接的。外围设备在自己的设备控制器控制下进行工作，控制器通过接口与主机利恩加，并受主机控制。

磁盘存储设备

磁记录原理

磁表面存储器：将磁性材料均匀的涂抹在金属铝或者塑料表示作为载磁体来存储信息。

磁表面存储器的优点为：

• 存储容量大，位价格低
• 记录介质可以重复使用
• 记录信息可以重复使用
• 记录信息可以长期保存而不丢失
• 非破坏性的读出，读出时不需要再生信息

同时磁表面存储器也有一些缺点：

• 存取速度较慢，机械机构复杂
• 非接触式读写，对于工作环境要求较高

总线系统

总线的概念和结构形态

总线的基本概念

总线是构成计算机系统的互联机构，是系统内各功能不见之间进行信息传送的公共通路。

按照不同的分类依据，总线有着不同的分类结果：

如果按照传送信息分类：

• 地址总线：

  单向的三态总线，用于传送地址信息。其的位数决定可执行寻址的范围。

• 数据总线：

  双向的三态总线，用于传送数据信息。位数有很多种。

• 控制总线：

  传送控制和状态信息。

如果按照连接部件分类的总线

• 内部总线：CPU内部逻辑不见的连接总线
• 局部总线：CPU与其他部件的连接总线，介于CPU内部总线和系统总线之间
• 系统总线：计算机各功能不见的连接总线
• 通信总线（IO总线）：微机系统之间，微机系统和其他设备之间的连接总线

总线的特性

1. 物理特性：

   总线的位数，总线插头、插座的形状，引脚的排列方式。

2. 功能特性

   确定每一根总线的名称、定义、功能与逻辑关系等。

3. 电器特性

   规定每一根总线上信号的传送方向及有效电平范围等内容。

4. 时间特性

   总线上各信号有效的时序关系。

总线标准

为了保证总线的性能充分发挥以及兼容问题将总线标准化，主要包括总线的各种特性：数据传输率，总线通信协议、仲裁协议等一系列规定和约定。

总线标准的来源可以分为权威组织正式公布的标准和实际存在的工业标准。

按照总线标准设计的总线结构就是通用接口。

总线的性能指标

1. 总线宽度

   在一次总线操作中，最多可以传送的数据位数。

2. 总线周期

   一次总线操作所需要的最小间隔时间。

   总线周期与总线的时钟频率成反比。

3. 总线带宽

   单位时间内通过总线的数据位数，总线的数据传输率。

总线的连接方式

总线之间需要通过适配器连接起来。

适配器（接口）：实现高速CPU同低速的外设之间工作速度上的匹配和同步，并完成计算机和外设之间的所有数据传送和控制。

在单机结构中，总线的结构比较多样。

单总线结构

系统内的所有不见均由系统总线连接。

优点：各部件之间可直接进行通信，系统易于扩充。

缺点：总线负载重，如果系统中存在慢速设备，则会产生较大的时间延迟，降低系统的工作效率。

双总线设备

系统内的所有部件均由系统总线连接，在CPU和主存之间再设置一组高速的存储总线。

特点：

• 保持了单总线的优点：简单，易于扩充。
• 减轻了系统总线的工作负担，使CPU工作效率有所提高。
• 增加了硬件成本。

三总线结构

系统总线负责连接CPU、主存、IO通道，存储总线负责连接CPU与主存，IO总线负责连接各个IO适配器。

特点：

• 设置了通道，对外设进行统一的管理，分担了CPU的负担。
• 提高了CPU的工作效率，同时也最大限度提高了外设的工作速度。
• 但是硬件的成本进一步增加。

三总线结构还有下面这种形式：

多总线结构

总线的内部结构

早期的总线内部实际上就是CPU引脚的物理延伸。

CPU是总线上唯一的控制者。这种方式让总线结构和CPU紧密相关，通用性比较差。

现代总线多采用标准总线。标准总线和结构、CPU、技术无关，亦被称作底板总线。

现代总线可以分成四个部分：

• 数据传送总线：地址线、数据线和控制线
• 仲裁总线：总线请求线，总线授权线
• 中断和同步总线：中断请求线，中断认可线
• 公用线：时钟信号，电源

总线结构实例

总线接口

信息的传送方式

1. 串行传输：使用一条传输线，采用脉冲传输。成本低廉，但是信息的传送速度慢。
2. 并行传输：每一个数据位使用一条传输线，一般使用电位传送。系统总线的信息传送方式。
3. 分时传输：总线传输信息的分时复用，共享总线部件对总线的分时复用。

接口的基本概念

接口是IO设备的适配器，CPU和主存，外围设备之间通过总线进行连接的逻辑部件。

接口一般具有下面这些功能：控制，缓冲，状态，转换，中断等。

一个适配器必须要有两个接口：

• 一个同系统总线相连接，采用并行的方式
• 一个同设备相连，可能采用并行或者串行方式

总线的仲裁

连接到总线上的功能模块有主动和被动两种形态：

• 主方可以启动一个总线周期
• 从方只能响应主方请求
• 每次总线操作，只能有一个主方，但是可能存在多个从方
• 主方持续控制总线的时间就是总线占用期

多个功能部件争用总线时，需要由总线仲裁部件选择一个设备使用总线。

总线仲裁有以下两种方式：

• 集中式：由中央仲裁其决定总线使用权的归属
• 分布式：多个仲裁器竞争使用总线

集中式仲裁

1. 链式查询方式

   采用菊花链的方式连接所有具有总线使用能力的部件，各设备公用一根总线请求信号线BR，总线授权信号线BG，总线忙信号性BS和中央仲裁器连接。总线授权信号BG串行的从一个接口连接到下一个接口。

   

   在这种控制模式下，设备的优先权同与总线控制器的距离有关系。

   

   使用这种方式的特点是：

   • 硬件连接简单，判断优先级容易，设备的增删容易
   • 对电路故障敏感，各个部件的优先级固定

2. 计数器定时查询方式

   在链式查询方式的基础上省去了总线授权信号BG，增加了计数器和设备地址线，每次收到总线申请，由计数器决定响应的顺序。

   

   在有总线请求时，发出计数值，选择设备查询请求状态，依次查询每一个设备的状态。

   在这种仲裁方式下，设备的优先级由计数值决定，计数值为0时同链式查询方式一样，

   这种方式的特点是：

   • 优先权控制灵活，对电路故障不敏感
   • 硬件成本增加，控制复杂度高

3. 独立请求方式

   每个部件均由独立的请求和响应信号线，由中央仲裁器的部分排队逻辑决定响应顺序。

   

   设备的优先权有中央仲裁器的内部排队逻辑决定

   使用这种仲裁方式的特点为：

   • 响应时间快，确定优先响应的设备花费的时间少，对优先次序的控制也相当的灵活
   • 硬件的复杂程度高

分布式仲裁

分布式仲裁不需要使用中央仲裁器，由分布在各部件中的多个仲裁器竞争使用总线。

每个潜在的主模块都有独立的仲裁器和唯一的仲裁号，通过仲裁总线上仲裁号大小的比较，决定可占用总线的部件。具体的仲裁步骤如下：

• 某部件有总线申请，将其仲裁号发送到共享仲裁总线上
• 每个仲裁器将仲裁总线上得到的号和自己的号相比较
• 如果仲裁总线上的号大，则它的总线请求不予响应，并撤销它的仲裁号
• 最后，获胜者的仲裁号保留在仲裁总线上

分布式仲裁是以优先级仲裁策略为基础的。

总线的定时和数据传送模式

总线的定时

总线的一次信息传送过程，大致可以分成以下五个阶段：

• 请求总线
• 总线仲裁
• 寻址
• 信息传送
• 状态返回/错误报告

定时就是指事件出现在总线上的时序关系，为了同步主方、从方的操作，需要通过定时协定。在数据传送过程中，有下面几种定时协定：

• 同步定时协定
• 异步定时协定
• 半同步定时协定
• 周期分裂式总线协定

下面介绍前两种定时协定：

1. 同步定时协议：

   

   优点：简单，传输的频率高

   缺点：只适用于总线长度短，功能模块存取时间接近的场景

2. 异步定时协定

   

   优点：总线周期长度可变，允许快慢速功能模块都连接到同一总线上

   缺点：增加了总线的复杂性和成本

总线数据传送模式

读、写操作

读操作是由从方到主方的数据传输，写操作是从主方到从方的大数据传送。

一般的，主方先以一个总线周期发送命令和从方地址，经过一定的演示再开始数据传送总线周期。

为了提高总线利用效率，减少延时损失，主方在完成寻址总线周期后可让出总线控制权，让其他主方完成更急迫的操作，然后再重新竞争总线控制权，完成数据传送总线周期。

块传送操作

只需给定块的起始地址，然后对固定块长度的数据一个接一个的读出和写入。CPU读取存储器的块传送操作常称作猝发是传送。块的长度一般固定为数据线宽度（存储器字长）的4倍。

写后读、读修改写操作

两种组合操作模式，只给出地址一次，或者进行先写后读操作，或者进行先读后写操作。先写后读操作常常用于校验目的，先读后写操作用于多程序系统中对于共享存储资源的保护。

块传送操作和写后读、读修改写操作都是主方控制总线直到整个操作结束。

广播、广集操作

广播、广集操作是一个较为特殊的操作。一般来说，总线只允许一个主方和一个从方之间进行通信，但是一些总线允许一个主方对多个从方进行操作。如果是对于多个从方进行写操作，这种操作称为广播，如果是从多个从方读取，并在总线上完成and或者or操作再被读取，这种操作称为广集。广集操作在检测多个中断源时非常好用。

PCI总线和PCIe总线

多总线结构

Host总线

有CPU总线，系统总线，主存总线，前端总线等等名称。

连接北桥芯片和CPU之间的信息通路，是一个64位数据线和32位地址线的同步总线。

PCI总线

连接各种高速的PCI设备，是一个与处理器无关的高速外围总线。

采用同步时序协议和集中式仲裁策略，并且可以自动配置。PCI设备可以是主设备，也可以是从设备，或者兼而有之。

LAGACY总线

此处疑有讹误，应为LEGACY总线。

一般是ISA，EISA和MCA这类性能较低的传统总线，在这里的主要意义是提供向前的兼容性。

PCI总线中的桥

桥起着将两条总线连接起来的作用。桥同时也是一个总线转换部件，将一条总线上的地址空间映射到另一条总线的地址空间中，使用两条总线上的设备可以直接通信。

PCI 总线信号

PCI总线的基本传输机制是猝发式传输。

在进行写操作时，桥把上层总线的写周期缓存起来，以后再在下层总线上生成写周期，即写延迟。当进行读操作时，桥可以早于上层总线，直接在下层总线上预读。无论延迟写还是预读，桥的作用可使所有的存取都按照CPU的要求出现在总线上。

PCI总线仲裁

PCI总线采用集中式仲裁方式。每个设备都有总线请求nREQ线和总线授权nGNT线和中央仲裁器连接，中央仲裁器根据算法对设备的申请做出仲裁。

PCIe总线

对于PCI总线的扩展，提供了更快的传输速度，在软件和应用上兼容PCI设备。

PCIe总线相对于PCI总线做出了如下的改进：

• 高速差分传输
• 串行传输
• 全双工端到端传输
• 基于多通道的数据传递方式
• 基于多通道的数据传递方式
• 基于数据包的传输

计算机网络课程笔记

大二下学期专业课《计算机网络》课程笔记。

授课教师：程莉

说明

由于Internet“粗糙的约定和可以运行的代码”的特点，所以笔记中可能出现，逻辑混乱，上下文毫无关系，语无伦次等等问题。

引言

什么是计算机网络

通过同一种技术​相互连接的计算机就构成一种计算机网络。

容易被混淆的概念：

• 通信\计算机

  通信处理数据从一个实体到另外一个实体的传输

  计算机负责帮助人类处理信息

• 通信网络\计算机网络

  通信网络就是一个负责传输信息的链接和节点

  计算机网络是一组相互链接的互联网

• 分布式系统\计算机网络

  分布式系统：将一系列独立的计算机组成一个逻辑上的计算机

  系统内部是对用户透明的​

计算机网络不是：

• Internet：全球唯一的巨大互联网
• internet：多个计算机网络链接构成的计算机网络
• www：一种基于计算机网络提供的服务\应用

计算机网络的硬件组成

• 计算机\主机host​​\终端系统End System​​
• 通信链接：有线\无线
• 交换机switch​​\路由器router​​

拓扑结构

通过图的形式表示网络中节点，包括交换机和路由器，之间的连接关系。

计算机网络的组成

• 硬件
• 软件：操作系统以及一些应用软件
• 计算机的标识：IP地址、域名
• 通信规则

计算机网络的应用

商业应用

• 资源共享
• 同用户的交流通信

移动网络用户

计算机网络的分类

按照使用的范围进行分类

• 个域网

  通常采用蓝牙等技术进行链接

• 局域网LAN​

  将主机同边缘路由器连接起来

  共有一个链接链路，一般是星型组网

• 城域网MAN​

  通常是广电网络

  通常是树形组网

• 广域网WAN​

  存储转发、分组交换、通过路由算法决定路由路径

  为了保证可靠性通常采用网孔型组网

按照传输技术分类

• 广播网络

  将数据包发送给所有的目标主机，每个主机再来检查数据包的目标地址，如果这个数据包就是发给这台主机的就接受这个数据包，反之忽略这个数据包

  在局域网中广泛应用

  同时发送数据包可能存在冲突

• 点对点网络

  数据包直接从源地址发送到目的地址

  在广域网中应用广泛。

按照在互联网络中的位置

• 接入网Access Networks​

  在网络的边缘，主要辅助用户来接入互联网

• 核心网Core Networks​

  将接入网和其他核心网连接在一起

网络架构和网络协议

分层的网络体系结构

网络是按照一个层栈的方式组成起来的。这样做可以：

• 这样设计简化了设计的复杂性

• 每一层向更高层提供来具体的服务，同时屏蔽了具体实现的细节

• 每一层都会和相邻的层之间进行交互（不是通信），每一层都和对方的对等层Peers​之间有着通信，协议就规定来对等层之间通信的协议

• 相邻的两层直接通过接口定义了允许的操作和服务

• 数据的流向实际上是U型的，发送系统自顶向下，最底层实际传输数据，接受系统自底向上

• 每层可能在上一层交付数据的基础上进行封装，加上本层的控制信息，构成本层的数据包，控制信息和添加的方式是由协议规定的。每次构成的数据包称作协议数据包PDU​

层次设计过程中需要注意的问题

• 可靠性

  • 差错检测和回复
  • 路由选择

• 网络演进

  • 协议的分层设计：将问题细分，隐藏每层实现的细节
  • 地址：标识不同的发送者和接受者
  • 网络的互通性
  • 协议的可扩展性

• 资源定位

  • 统计复用Statistical Multiplexing​
  • 流量控制：防止过快的发送倒是数据在接受方丢失

• 服务质量QoS​

• 安全

层需要指定的标准

同层之间通信的协议：

• 语法Syntax​：协议的消息格式
• 语义Semantics​：消息的字段区某个值的含义

向上一层提供的服务接口

服务接口可以分成两种类型：

• 面向连接的Connection-oriented​

  在连接的过程中连接就被建立起来，需要的资源就已经被分配好了，后续的数据将按照这条已经建立的道路前进

  连接将会使可靠的

  在建立连接的时候需要完整的地址，在之后只需要指定连接的就可以完全发送

• 无连接的Connectionless​

  资源将会是动态分配的

  但是连接是不可靠的，数据包可以会丢失、放弃和乱序

  每次连接都需要完整的地址来建立连接

服务原语​Service Primitives​：描述层与层之间提供服务的方法。一个服务就是有一组服务原语来定义的。

在计算机中实现服务原语：

如果协议栈是由操作系统实现的：服务原语通过是通过系统调用的方式提供的。

如果需要定义一个简单的面向连接的服务，一般需要5个服务原语：

• 监听：阻塞直到收到一个连接请求
• 连接：同对应层建立一个连接
• 接收：阻塞直到收到数据
• 发送：发送数据
• 断开连接：终止一个连接

服务和协议的关系

服务定义了本层对外提供的操作，而协议定义了同层之间通信的方式。

服务是通过协议实现的，在服务不变的情况下，层可以自由改变协议。

参考模型

OSI参考模型

模型将设备分为两类：主机和节点。

主机不负责数据的转发，但是需要负责数据的处理，主机具有完整的七层。

节点负责数据的转发，不具有处理数据的能力，节点只具有三层。

参看模型的七层具体为：

• 物理层Physical​​

  直接通过通信设备处理字节流。

  定义了1​位和0​位的电压范围和位的数据率，定义了传输是全双工还是半双工的，定义了初始连接如何建立和终止，定义了接口的物理规格。

• 数据链路层Data Link​​

  通过逻辑通道进行原始数据的传输。

  发送者会将数据封装为帧发送，接受者会在收到数据之后发送确认帧给发送者以确保服务的可靠性。数据链路层还会提供流量控制的功能，避免过快的发送阻塞了接受者。广播网络和单点网络的区分也是在数据链路层产生的。

• 网络层Network​​

  控制子网上的操作。

  网络层主要的功能就是转发数据，路由的功能就主要在网络层实现。除此之外，网络层还提供拥塞控制，服务质量的控制等功能。

• 传输层Transport​​

  端到端层。从上层接受数据，将数据分成较小的数据包并且通过网络层正确的传输到对方。

  同一计算机上不同进程的区分也是在传输层完成的。

• 会话层Session

  提供会话控制、令牌管理和同步的功能。

• 表示层Presentation​

  获得传输信息的语法和语义。

  在这层可以提供数据加密和数据压缩等的功能。

• 应用层Application​​

  直接被用户使用的各种应用协议。

TCP/IP参考模型

该模型一般只有四层：

• 链路层Link​
• 网络层/网际层Internet​
• 传输层Transport​
• 应用层Application​

链路层

协议并未强制规定，具体的实现由其他的机构规定，比如Ethernet​，WiFi​和SDH​。

只负责传输IP​数据包。

网络层

主要协议是IP​协议，是一个不可靠的传输协议。

传输层

​TCP​传输协议：面向连接的可靠传输协议，传输字节流。

​UDP​传输协议：无连接的不可靠传输协议，传输字节流。

应用层

由用户使用的各种应用协议。

OSI和TCP/IP参考模型的对比

​

OSI模型的特点、优缺点

特点：

• 服务：某层实体对于上一层实体的支持
• 结构：定义某层实体对于上一层提供的原语操作
• 协议：两个系统同层之间同喜需要遵守的规范

OSI模型没有能够取得主导地位的问题：

• 生不逢时
• 技术设计上有缺陷，比如会话层和展示层比较简单而且和应用关系密切，不算是很合适的抽象

TCP/IP模型的特点、优缺点

• 服务、接口和协议没有很清晰的划分
• 不算是很通用的模型
• 链路层实际上不算层，并没有严格的规定
• 物理层和数据链路层上没有区分
• 部分老旧协议

混合模型

注意：这个模型并不是实际标准化的模型，只是学习的过程中便于学习而提出的。

两个模型都存在缺陷，因此为了较好的描述整个体系，我们将两个模型混合在一起：

• 应用层
• 传输层
• 网络层
• 数据链路层
• 物理层

‍

‍

‍

‍

物理层

物理层的位置和功能

网络架构中最低的层，定义了字节如何通过转换为信号并通过各种通道传输。

基础概念和数据传输

• 信道Channel​：传送信息的媒体（介质）

• 带宽Bandwidth​：可以稳定传输的频率范围

• 速率bps​：每秒内传输的位数量

• 波特率baud​：每秒钟能能够发送的信号单元数量

  $$Baud=\frac{1}{T}$$

  T​是发送信号单元之间的间隔

速率和波特率之间存在着关系，主要取决于单个信号单元能够携带的位数量，而单个信号单元能够携带的位数量由取决于单个信号单元的有效状态V​，而且有：

$$Bps=Baud\times lo{g}_{2}V$$

• 信道容量：信道的最大数据率

• 吞吐量：单位时间内网络可以传送的数据位数

• 负载：单位时间内进入网络的数据位数

• 误码率：传输出错的数量占总传输量的时间

• 时延：从向网络中发送数据块的第一位开始，到数据块的最后一位被接受为止，中间经过的时间

  时延一般由以下这些部分组成：发送时延、传播时延、节点处理时延、排队时延

  • 发送时延：设备发送一个数据块需要的时间，和数据块的长度和发送的速率有关
  • 传播时延：信号通过传输介质的时间
  • 节点处理时延：交换机和路由器检查数据和选路的时间
  • 排队时延：在交换机和路由器中排队等待的时间

单工、半双工、全双工

• 单工simplex​：传输只能单向发生。
• 半双工half-duplx​：传输可以双向发生，但是同一时间只能单向传输
• 全双工full-duplx​：双向传输可以同时发生

并行传输和串行传输、异步传输和同步传输

并行传输同时传输多个字符，串行传输同时传输一个字符。

• 异步串行传输

  拥有独立的时钟，两个设备之间不需要进行同步。

  以字符位单位进行传输。

  发送两个字符之间的间隔是任意的。

  接受方依靠字符中中的起始位和停止位进行同步。

• 同步串行传输

  以时钟信号线对传输的数据线上的信号进行同步。

  按照数据块（帧）为单位进行传输

传输损伤

收到的信号同发出的信号不同的现象称作传输损伤。这种损伤表现在模拟型号中就是信号质量的下降，在数据信号中表现为位错误。

传输损伤通常是由信号衰减、失真，传输时延和通信噪声造成的。

传输数据的理论基础

Nyquist定理

Nyquist​定理：如果一个随机的信号通过一个带宽为B​的低通滤波器，那么只需要2B​的采样率就能够重建出这个信号。

于是对于一个无噪声，带宽为B​​的信道，可以支持的最高波特率就是2B​​。

如果单个信号单元包含了V​状态，那么最大传输速率为：

$$Capacity=2\times bandwidth\times lo{g}_{2}V$$

‍

香农公式

利用香农公式可以得到一个指定的信道最大的传输带宽，这是从物理的角度上给出的一个信道的极限带宽。

香农公式：

Capacity=bandwith×log2​(1+noisepowersignalpower​)

而在具体实践中信噪比SNR​常常使用分贝作为单位进行表示：

$$(\frac{S}{N}{)}_{db}=10\times lo{g}_{10}(\frac{S}{N})$$

在计算中需要注意换算。

传输介质

• 双绞线Twisted Pair​
• 同轴电缆Coaxial Cable​
• 光纤Fiber​
• 电力线Power Line​
• 射频Radio​

双绞线UTP

最常见的通信介质，可以传输模拟信号和数字信号。

双绞线的带宽取决于：

• 线缆的粗细

• 传输的距离

• 每米的匝数

  双绞线通过两根相互缠绕的铜线来抗干扰，因此缠绕的越密集，抗干扰的能力就越强，带宽就更宽。

同轴电缆

比双绞线有着更好的屏蔽性能和更广的带宽。

在局域网组网中使用很少，但是在核心交换机之间比较常用。

光纤

相较于使用电信号进行通信的前两者，光纤具有高带宽，轻量和安全等特点。

电力线

通过家庭电路进行网络的传输，提高电线的利用效率。

射频

无线的传输方式。相较于有线的传输方式，射频传输会有更高的误码率和更高的延迟。

数字调试和编码

信号调制技术

• 电话：模拟信号到模拟信号
• 调制：数字信号到模拟信号

调制

通过模拟信号来传输数字信号：

• 通过不同的频率来表示不同的比特位
• 通过不同的振幅来表示不同的比特位
• 通过不同的相位来表示不同的比特位

多级调制技术

通过同时利用不同的振幅和相位来表示传输的比特位，提高单个信号单元能携带的信息数量。

通常使用星云图来表示：

​

而且相同的调制级数可能存在不同的实现。

编码

使用电平表示状态

使用高电平表示1， 使用低电平表示0。这种编码方式被称作不归零NRZ。

但是使用这种方式可能会导致同步失败：

一段连续的高电平/低电平可能会被误判。

使用电平翻转表示状态

在时钟开始的时候如果发生调变就是1，不发生调变就是0。

曼彻斯特编码

指定电平的变化必须发生在时钟周期的中间。这样同时传输来信号和时钟，有着自同步功能。

电平由高变低表示1，电平由低变高表示0。

​

是现在局域网编码使用的编码格式。

但是目前的高速局域网已经不适用了，因为需求的频率较高。（十兆网升级到百兆网仍然使用曼彻斯特编码，只是同时将线路缩短十倍，但是千兆网及更高就不用了（或帧突发、载波扩展？））

数字化模拟信号PCM

通过记录一系列离散的点来表示原来的模拟信号。

PCM一般具有三个步骤：

• 采样

  按照Nyquist​定理，采样率需要是最高频率的两倍。

• 量化

  将信号强度对应为指定好的量级。

  不同的国家和地区可能有着不同的量化方式。

• 编码

复用

频分复用FDM

将不同频率的信号合并在一起传输，最大化提高信道的利用效率。

时分复用TDM

将时间分为若干个不同的时间片timeslot​，信号将被分配到不同的时间片发送。

静态时分复用（static）

在每一个发送帧中都为每个用户保留空间以进行复用，一种同步的时分复用方式。

但是这样做可能会导致比较大的浪费。在电话网络中应用比较广泛，而在计算机网络中应用比较少。

统计时分复用（synchronous）

只发送需要发送的数据，在需要时分复用的时候才进行复用。

​

但是这样需要加上地址头以区分不同的用户发送的数据。

码分复用

每一个用户都可以使用整个信号在任意时间发送信息，不同用户之间传输的数据是通过编码理论的方式分开的。

物理网络例子：PSTN

就是最原始的电话网络，相关：T1链路标准

​

• 本地环路Local Loop​：一般还是采用模拟双绞线传输，从端局到用户。
• 中继线路Trunk​：一般是数字同轴线/光纤传输，在端局和不同交换机之间传输。
• 交换机Switch Offices​：将电话呼叫在不同的端局之间联通。

传输的速率

当计算机利用电话网络进行通信的时候，需要采用调制解调器进行数字信号和模拟信号之间的转换。端局还需要进行一次数模转换，那么如果两台采用调制解调器的计算机之间直接通信，由于数模转换之间产生的噪声，通过香农公示进行计算得到的最大传输速度大概是35kpbs​。如果之间和ISP的服务器之间通信，这是就可以省去一般的数模转换，这里的传输速率就可以达到56kpbs​。

xDSL 服务

为了提高电话网上网的速度，同时也解决上网的时候就不能打电话，传真的问题，非对称数字用户线ADSL​技术出现了。

ADSL​技术采用频分复用技术，将大概1.1Mhz的信号分成256个4312.5Hz的信道，其中信道0用于电话通信，信道1~5不被使用，而是用作电话信号和数字信号之间的隔离带。剩下的250个信道都被用于数据通信，其中两个信道用于控制，剩下的信道都是用来通信。

每个信道都采用类似于V.34​的编码方式，采样率为4000 baud​，通过正交调幅发送的数据大概为15 bit/buad​，在极限情况下的最大传输速度能达到13Mpbs​左右。同时为了提高用户体验，ISP往往都会把更多的信道用来作为下行信道，使提供的下载带宽大于上传带宽。

物理网络例子：有线电视网络

​

同样采用频分复用的技术。

下载链路采用QAM-64​编码，传输速度大概能达到30Mbps，上传链路采用QPSK​编码，传输速度大概能达到12Mpbs。

链路交换和分组交换

链路交换

在需要交换时，在通信的双方之间建立专用的通路，资源提前分配。通信有着三个阶段：链接建立，数据传输，链接中止。

电话网络交换中常采用这种方式。

优点是延迟比较低，服务的质量比较好，缺点是在建立链接的时候需要花费比较长的时间，固定的带宽也不适合计算机使用，当双方都不发送数据的时候，建立数据链路就会被浪费。

分组交换

数据在发送之初就被分成不同的组，每个包单独进行路由选择，每个节点都会先存储收到的数据包再发送给下一个节点（存储——转发策略），在这过程中资源是动态分配的。每个包都需要携带路由需要的信息。

链路交换和分组交换所花费的时间

​

物理层协议示例：10BaseT

物理层需要规定物理接口：

• 机械特性
• 电气特性
• 功能特性
• 过程特性

IEEE802.3——10BaseT

以双绞线作为传输介质，传输速度能够达到10Mpbs的协议。

• 机械特性：使用RJ-45​接口作为物理接口
• 电气特性：使用曼彻斯特编码，电压范围在-2.5V~2.5V​之间
• 功能特性：使用接口中的pin1&2​对线作为发送线，pin3&6​对线作为接受线

‍

‍

‍

‍

‍

数据链路层

数据链路层的位置、功能和服务

数据链路层和位置和功能

数据链路层负责通过物理层以可靠、高效的方式将数据包（帧）在相邻节点之间传输。

数据链路层提供了打包，流量控制，地址索引，错误控制，介质访问控制等的功能。

其中介质访问控制是专属于局域网的技术，主要负责处理数据包广播中遇到的问题，而在广域网中常用点对点链接的方式，故没有相关的问题。

设计目标就是在两个响铃的节点之间实现可靠、高效的通信。

封装

​

在数据链路层的封装：将上一层传输过来的净荷附加上帧头和帧尾构成一个帧。

数据链路层中的传输是逐级进行的，被称作逐级通信hop-to-hop communication​。

数据链路层一般由网卡实现

• 发送方：将网络层的包打包为一个帧，在加上错误纠正，可靠传输和流量控制等的功能
• 接收方：首先检验传输过程中是否发生错误，并进行流量控制和可靠传输等的功能
• 数据链路层常常通过硬件实体——网卡实现

数据链路层提供的服务

• 无连接的服务：

  • 无确认的无连接服务：没有确认帧和逻辑链接，大多数的局域网属于这种方式
  • 有确认的无连接服务：含有一个确认帧，在不可靠的传输信道中应用比较广泛，比如Wi-Fi

• 面向连接的服务：

  需要建立连接，每一个传输的帧都会被编号。常见的有ATM​和HDLC​

设计中处理的问题

成帧控制

如何从物理层中传输的字节流中识别出不同的帧。

设计成帧功能的要求

• 简单：易于实现
• 透明：同传输的内容无关
• 高效：使用的字节尽量少
• 鲁棒：不易出错，即使出错也应该尽快恢复

字符计数法

​​

在帧头中添加一个表示内容中字符的数量（包括帧头）。但是如果传输的时候帧头中字符数量的字段发生了错误，这个错误不易纠正。

字节/字符填充

在帧的首尾添加标志符以标记帧的开始和结束。标志符往往是传输内容中不常使用的字符。

这种方式实现透明传输比较复杂：因为作为标志符的字符在传输内容中也可能使用。于是为了实现透明传输，在传输内容中使用标志符时需要在前面加上转义字符，通知接受者后面的标志符并不是标志符。

这种方式在PPP​协议中得到使用。

这种方式同传输内容的编码方式高度相关，而且往往都是字符编码，直接传输字节就显得不太可能。

比特填充

使用固定的二进制位串位置帧开始和结束的标志：01111110​。

但是在传输的数据中也会存在出现标志位串的可能性，于是为了避免这种问题，硬件会在内容中每遇到5个连续的1就在后面添加一个0。在接受方接受数据的时候，每接受到五个连续的1就去掉后面的0。

​​

但是如果在传输的过程中遇到01110110​这种位串，其中发生了一次位翻转成为标志位，或者反过来，就可能导致传输错误。

物理层编码违例法

利用物理层编码中违法的编码作为帧的开始和结束标志。

错误控制

错误的类型

• 帧丢失：发出的帧就没有达到接收方。这种错误属于流量控制的部分。
• 帧损坏：接受帧的部分比特错误。

单比特错误就是只有一个比特发生了错误。

突发错误意味着至少两个比特在传输过程中发生了错误。突发错误的长度不是指错误比特的数量。

​​

错误的侦测

• 奇偶校验检测单个比特错误
• 循环冗余校验可以检测部分突发性的错误

奇偶校验

通过添加一个奇偶校验位来验证数据的传输过程中是否发生错误。

奇偶校验只能检验奇数的错误。

汉明码

为了校验单个错误需要的校验码位数：

设m​表示信息的位数，r​表示校验码的位置，n​为传输的位置，即n=m+r​。

为了纠正单个的错误，需要有下列的不等式成立：

$$(n+1)2^m\le 2^n$$

化简得到：

$$m+r+1\le 2^r$$

为了设计汉明码，首先需要给每一位编号：从左到右，从1开始依次编号。

在编码中，2的次方位（2，4，8，16）是校验码位，剩下的位数就是传输的数据位。其中每一个校验位覆盖的数据为是不同的，例如对于8位的ASCII码的进行编码：

发送前编码：

3=1+2，5=1+4，6=2+4，7=1+2+4，9=1+8，10=2+8，11=1+2+8

所以校验码1就需要检验1，3，5，7，9，11，所以值就是0，其他的检验码依次类推，需要检验所有编码中设计的位。

生成汉明码还有一种简便方法：

在需要生成编码时，将码字中为1的各位码字表示为二进制码，再按模2求和，所得的结果就是校验码，下图中是将数据1011进行编码的示例：

需要注意的是，得到的校验码是倒序的。

在需要阶码的时候，将码字中为1的各位码字位号表示为二进制码，再按模2求和，如果和为0表示无差错，如果不为0表示差错的位号。

CRC循环冗余校验

CRC主要用于突发错误的侦测。

将位串当作多项式项目的系数。例如110001​就可以写成多项式：

$$x^5+x^4+x^0$$

发送方和接收方首先需要约定好一个相同的校验多项式$G(x)$。校验码的位数同校验多项式最高次项的次数相同。

发送方在生成校验码时，首先在数据的后面补上同校验码位数相同的零，再和校验多项式做除法取余数，余数就是生成的校验位。

​

接受方在接收到数据之后利用校验多项式计算除法的余数，如果余数为0则说明传输中没有问题，反之则存在错误。

​r​位的校验码可以发现所有长度在r​以下的错误。

所有奇数个比特翻转的错误一定能够被发现。

对于长度大于r​的错误被遗漏的概率为$2^{-r}$。

错误的纠正

当传输的介质比较可靠的时候，使用错误侦测再进行重传是更加便宜的方式。

当传输的介质不是特别可靠的时候，比如无线网络，最好使用错误纠正码来确保接受者能够纠正少量的错误。

流量控制

流量控制的目的就是为了防止接收方被发送方过快的发送阻塞，导致传输的数据丢失。

数据链路层的流量控制都是基于反馈的流量控制，即通过发送方通过接受接受方发送的ACK​信息来决定怎么发送数据。

基础流量控制协议

使用C​语言编写代码表示协议，定义一个头文件protocol.h​：

//
// Created by ricardo on 23-3-17.
//

#ifndef DATA_LINK_LAYER_PROTOCOL_H
#define DATA_LINK_LAYER_PROTOCOL_H

#define MAX_PKT 1024

typedef enum {
    false,
    true
} boolean;

typedef unsigned int seq_nr;

typedef struct {
    unsigned char data[MAX_PKT];
} packet;

typedef enum {
    data,
    ack,
    nck,
} frame_kind;

typedef struct {
    frame_kind kind;
    seq_nr seq;
    seq_nr ack;
    packet info;
} frame;

void wait_for_event(event_type *event);

void from_network_layer(packet *p);

void to_network_layer(packet* p);

void from_physical_layer(packet *p);

void to_physical_layer(packet* p);

void start_timer(seq_nr k);

void end_timer(seq_nr k);

void start_ack_time();

void end_ack_time();

void enable_network_layer();

void disable_network_layer();

#endif //DATA_LINK_LAYER_PROTOCOL_H

协议1 乌托邦单工协议

这个协议假设：

• 通信的单工的
• 通信是无错的
• 接收方有着无限的缓存

即：这个协议不需要任何的错误控制和流量控制

​​

//
// Created by ricardo on 23-3-17.
//

typedef enum {
    frame_arrival
} event_type;
#include "protocol.h"

void send() {
    frame s;
    packet buffer;

    while (true) {
        from_network_layer(&buffer);
        s.info = buffer;
        to_physical_layer(&s);
    }
}

void receive() {
    frame r;
    event_type event;

    while (true) {
        wait_for_event(&event);

        from_physical_layer(&r);
        to_network_layer(&r.info);
    }
}

协议2 单工发送——等待协议

这个协议假设：

• 通信是单工的
• 通信是没有错误的
• 接受者有着有限的缓存

这个协议使用了一种发送——等待机制：

• 发送方发送数据开始等待
• 接收方接受数据并发送确认帧ACK​​
• 发送方收到确认帧，继续发送

​​

//
// Created by ricardo on 23-3-17.
//

typedef enum {
    frame_arrival
} event_type;

#include "protocol.h"

void send()
{
    frame s;
    packet buffer;
    event_type event;

    while (true)
    {
        from_network_layer(&buffer);
        s.info = buffer;
        to_physical_layer(&s);
        wait_for_event(&event);
    }
}

void receive()
{
    frame r, s;
    event_type event;

    while (true) {
        wait_for_event(&event);
        from_physical_layer(&r);
        to_network_layer(&r.info);
        to_physical_layer(&s);
    }
}

协议3 带有重试的主动确认协议

如果将协议2应用在不可靠的传输信道上：

• 传输过程中帧损坏了：

  接受者可以使用CRC​纠错码发现和丢弃这个损坏的帧

  发送者在等待ACK​帧的过程中超时之后重新发送这个帧

• 传输过程中帧丢失了：

  如果是数据帧丢失了：发送者超时之后重新发送

  如果是ACK​帧丢失了：发送者超时之后重新发送

但是ACK​帧丢失之后重传可能遇到一个问题：发送者重新发送的数据帧会被接受者当作是新的数据帧。

​​

为了解决这个问题，我们可以在数据帧的帧头上添加序列编号。

在这里由于实际上只需要两种状态，序列编号只需要一个比特，传输0或者1就可以了。

这样就将这个协议改造成了一个自动重传协议Automatic Repeat reQuest aka ARQ​。

这个协议称为：单向传输数据的停止等待ARQ协议

• 发送方在数据帧中添加校验字段，发送之后启动超时定时器
• 接受方在接受数据之后利用校验码检查错误，出错就丢弃数据，校验无误的情况下发送确认帧
• 发送法收到确认帧，发送下一帧，重启定时器
• 如果发送方定时器超时，发送方重新发送刚发送的数据帧
• 在数据帧还携带一个序号，接受方根据序号来判断是否是重复发送的数据帧
• 确认帧中也携带序号，发送方通过序号确定是否是重复的确认帧

‍那么确认帧是必须携带序号吗：

在确认帧发送比较缓慢的时候，缺少序号的确认帧就可能导致问题。

因此确认帧是需要序号的，发送方通过序确认是否是重复的确认帧。

#define MAX_SEQ 1
typedef enum
{
    frame_arrival,
    cksum_err,
    timeout
} event_type;

#include "protocol.h"

void send()
{
    seq_nr next_frame_to_send;
    frame s;
    packet buffer;
    event_type event;

    next_frame_to_send = 0;
    from_network_layer(&buffer);
    while (true)
    {
        s.info = buffer;
        s.seq = next_frame_to_send;
        to_physical_layer(&s);
        start_timer(s.seq);
        wait_for_event(&event);

        if (event == frame_arrival)
        {
            from_physical_layer(&s);
            if (s.ack == next_frame_to_send)
            {
                stop_timer(s.ack);
                from_network_layer(&buffer);
                next_frame_to_send = 1 - next_frame_to_send;
            }
        }
    }
}

void receive()
{
    seq_nr frame_expected;
    frame r, s;
    event_type event;

    frame_expected = 0;
    while (true)
    {
        wait_for_event(&event);

        if (event == frame_arrival)
        {
            from_physical_layer(&r);
            if (r.seq == frame_expected)
            {
                to_network_layer(&r.info);
                frame_expected = 1 - frame_expected;
            }
            s.ack = 1 - frame_expected;
            to_physical_layer(&s);
        }
    }
}

协议4 实用的停止等待ARQ协议

设计原则：

• 在数据帧中增加校验字段，发送帧之后启动超时定时器

• 接收方对于收到的数据进行校验，如果出错则丢弃，如果校验无错，就发送确认帧或者通过下一个帧进行捎带确认

• 收到确认之后发送下一帧，重启定时器

• 如果定时器超时，则重新发送刚发送的数据帧

• 数据帧中携带发送序号，根据需要判断是否需要是重复的数据帧

• 根据确认帧判断是否重复的确认帧

捎带应答：

当收到一个数据帧时，不同于立刻发送一个确认帧，而是等待网络层给出下一个需要发送的数据包，并把确认帧附在需要发送的数据帧之后一同发送出去。

在这个过程中，发送方和确认方都需要维持一个滑动窗口。

#define MAX_SEQ 1
typedef enum
{
    frame_arrival,
    cksum_err,
    timeout
} event_type;

#include "protocol.h"

void protocol()
{
    seq_nr next_frame_to_send;
    seq_nr frame_expected;

    frame r, s;
    packet buffer;
    event_type event;

    from_network_layer(&buffer);
    s.info = buffer;
    s.seq = next_frame_to_send;
    s.ack = 1 - frame_expected;
    to_physical_layer(&s);
    start_timer(s.seq);

    while (true)
    {
        wait_for_event(&event);

        if (event == frame_arrival)
        {
            from_physical_layer(&r);

            if (r.seq = frame_expected)
            {
                to_network_layer(&r.info);
                frame_expected = 1 - frame_expected;
            }

            if (r.ack == next_frame_to_send)
            {
                stop_timer(r.ack);
                from_network_layer(&buffer);
                next_frame_to_send = 1 - next_frame_to_send;
            }

            s.info = buffer;
            s.seq = next_frame_to_send;
            s.ack = 1 - frame_expected;
            to_physical_layer(&s);
            start_timer(s.seq);
        }
    }
}

但是这个协议的效率非常的低。

在大部分的时间里，使用这个协议的信道都被阻塞等待确认帧。

协议5 回退N步协议

设计原则：

• 发送方和接收方都需要维持一个滑动窗口：

  发送窗口： 发送帧的缓冲队列

  接受窗口：接受帧的缓冲队列

• 发送者将被允许在收到确认帧之前发送多个数据帧

• 如果接收方发现了传输错误，那么发送方必须回退到这个错误的帧重发进行纠错，已经发送的数据帧就废弃了

‍发送窗口大小的约束：

当序号的位数只有$n$时，假设发送窗口的大小达到$2^n$。

如果发送方发送所有可以发送的帧，而接收方在接受所有的数据之后发送确认帧时失败了，但是此时接受者的序号和发送者的序号相同，接受者会把发送者重新发送的帧当作新发送的帧接受。

‍因此该协议的发送窗口大小必须满足：

$$WindowSize\le 2^n-1$$

式子中的n表示序号的位数。

协议5的示例实现：

协议6 选择重传协议

Select Repeat/Select Reject。

接收方的缓存大于1，可以接受乱序的帧，并且只要求重传错误的帧。

选择重传中对于窗口大小的限制：

• 发送窗口和接受窗口大小之和不能大于$2^n$:

$$w_s+w_r\le 2^n$$

• 发送窗口的大小大于接受窗口的大小

• 一般来说，取发送窗口和接受窗口大小为$2^{n-1}$

协议6相对于协议5的改进：

• 设置确认帧定时器：

  在收到数据帧之后，等待一段时间的回传帧以进行捎带确认。如果定时器超时还没有等到回传的数据，直接发送确认帧。

  利用这种方式减少单独确认帧的发送，提高信道的使用效率。

• NAK帧：对于同一帧的错误，发送一次NAK

  NAK帧的序号就是出错帧的序号。

  帧接受之后校验出错和序号不对都算是出错。

协议6的示例实现：

协议效率的分析

为了比较不同的协议效率的不同，一般采用最大信道利用率来描述一个协议的效率。

停等协议的效率

在发送过程中没有遇到错误，需要确认帧的情况下，发送数据帧的总时间：

$$T_F=T_{tran}+T_{prop}+T_{proc}+T_{ack}+T_{prop}+T_{proc}$$

一般来说认为处理时间和发送确认帧的时间是可以忽略不计的，所以总的时间就是：

$$T_F=T_{tran}+2T_{prop}$$

计算出信道利用率：

$$U=\frac{T_{tran}}{2T_{prop}+T_{tran}}$$

因此当传播延迟$T_{prop}$越小，信道的利用率越高。

再考虑传输中遇到错误的问题。假设每一帧遇到错误的概率为p，可以首先计算出传输出错的数量为：

$$N_r=\sum _{i=1}^{\infty }i{p}^{i-1}(1-p)=\frac{1}{1-p}$$

不难发现测试的信道利用率就是：

$$U=\frac{T_{tran}}{2T_{prop}+T_{tran}}\times N_r=\frac{T_{tran}\times (1-p)}{2T_{prop}+T_{tran}}$$

引入一个概念——带宽时延积BD：在单程传播时延的时间内，信道可以容纳多少为的数据。带宽时延积还可以用传输时延$T_{prop}$和发送时延来计算$T_{tran}$：

$$BD=\frac{T_{prop}}{T_{tran}}$$

上述协议的效率还可以写成：

$$U=\frac{1}{1+2BD}$$

$$U=\frac{1-p}{1+2BD}$$

现在再研究具有滑动窗口的停等协议：

$$U=\frac{W}{1+2a}$$

其中W是发送窗口的大小，而且效率的最大值是1。

在考虑上捎带确认的功能，不用发送单独的确认帧，信道的效率还可以提高为：

$$U=\frac{U}{2+2BD}$$

示例协议

HDLC

HDLC 帧结构

• 同步传输

• 以位为单位

• 可以点对点之间通信，也可以按照主从模型进行通信

其中HDLC的帧还有三种类型：

• 信息：需要传输给上一层的数据。

  流量控制，错误纠正等的确认帧也在这部分

• 监督帧：当没有使用

PPP

• 无连接的协议，没有确认帧

• 以字节为单元进行传输

• 只能进行点对点直接通信

PPP和HDLC之间的对比

总的来说就是更加简单。

PPP增加了：

• 可以和多种网络协议共同工作

• 连接和数据压缩的协商

• 用户的身份认证

• 物理层可以使同步或者异步的

同时PPP移除了：

• 错误纠正，但是保留了错误发现

• 流量控制

• 序列号

PPPoE

就是PPP over Ethernet，广泛用于家庭网络中

• 没有序号的帧结构

• 使用字节填充

  0x7D作为转义字符

  在所有的ASCII控制字符（也就是0x20及其以下）之前都需要添加转义字符

• 地址0xFF表示所有用户都可以接受，但是由于是点对点通信，故实际意义不大

• 控制0x03表示使用无序号的模式

• 协议字段指明负载中使用的协议，比如IP

• 校验和，使用CRC校验，可以是16位或者是32位

然后介绍一下PPP的状态转移图：

介质访问控制子层

信道分配问题

一般来说，共享信道有着下面几种方式：

在图中：

• SDTM表示同步时分复用

  将时间分成不同的时间片，不同的设备轮流使用介质发送或者接受数据。每个设备都会得到固定长度的时间片供其使用，如果没有使用这个时间片就浪费了。

• ADTM表示异步时分复用，也被称作统计复用。

对于局域网来说，静态信道分配（FDM、STDM）工作的并不良好。

为了说明为什么工作的不好，我们首先引入一个公式：

$$T=\frac{1}{u-\lambda }$$

在公式中：

• $u$表示平均服务速度

• $\lambda$表示平均到达时间

• $T$表示平均等待时间

如果信道被平均分配到N个静态的子信道：

通过公式可以计算出平均等待时间变成了原来的N倍。

$$T=\frac{1}{\frac{uC}{N}-\frac{\lambda }{N}}=NT$$