计算机组成原理思维导图模板_ProcessOn思维导图、流程图

2：数据的表示和运算（第2章）

1：数制与编码

1.1：进位计数制及其相互转换

二进制转八进制

二进制转十六进制

r进制转十进制

十进制转r进制

整数部分

小数部分

1.2：真值和机器数

真值

机器数

1.3：校验码（计组大纲已删，但是计网还考）

奇偶校验码

校验原理

码字

码字间之间的距离

码距

若码距=2，有检错能力；若码距>=3，可能会有纠错能力

奇偶校验

奇校验码

偶校验码

奇偶校验码的码距d=2，仅能检测出”奇数个比特位“跳变发生的错误，且没有纠错能力

异或运算

循环冗余校验码（CRC码）

除数

被除数

余数

校验

收到K+R位数据（CRC码），与生成多项式确定“除数”（由生成多项式中X的系数组成）模二除，计算R位余数

余数为0，说明无错误

余数非0，说明出错

海明校验码

1：确定校验位个数k（k个校验位，n个信息位）

2：探索校验位应该放到哪些位置

3：确定每个校验位各自属于的分组并找到其应该存放什么值

将信息位的位置序号二进制数表示出来

”校验位第p[i]“的值与“信息位的位置序号“二进制第i位为1的归为同一组，进行“偶校验”。从而确定p[i]的值

4：进行校验纠错

对于校验位（P1，P2，P3...）所属各分组进行异或（相当于分组偶校验），求得S1，S2，S3.....

S1，S2，S3=000说明无错误

S1，S2，S3≠000，则其值反映出错的位置（比如110的话转换成10进制是6，就说明第6个位置出错了）

5：了解

海明吗有1位纠错，2位检错能力

注意：有的题目位置编号可能是从小到大，但是处理方法雷同

2：定点数的表示和运算（王道习题必做）

2.1：所谓定点数是指“小数点的位置”是固定的。与之相对应的浮点数是指-小数点的位置不固定

2.2：定点数的表示

“无符号数”的表示和运算

无符号数溢出标志

加减法，CF位为1，表示溢出

乘除法，OF位为1，表示溢出

“有符号数”的表示和运算

“定点整数”的表示

原码

加法

同号相加

异号相加

减法

转变为加法的异号相加

缺点

符号位不能参与运算，需要单独设计减法运算电路。===》费钱

注意

反码

正数的反码=原码。

负数的反码，原码符号位不变且”数值位“全部取反

补码

原码转补码

正数的补码=原码。

法1

负数的补码=反码末位+1

法2

将二进制从右向左数，第一个1为分界线，左侧的“数值位”全部取反，符号位不变

补码的加减法

总是要将“减法转变成加法”，“符号位也要参与运算”（补码肯定都是正的），发生溢出的话，把溢出位都舍去即可

注意，补码可以比原码多表示一种状态。因为原码的“正0和负0”用两个形式表示，而补码却只有一种形式（默认让1 0000000规定是-128）

移码

在“补码”的基础上将”符号位“取反。注意移码只能表示整数

移码的作用：可以很方便的比较数的大小。移码越大，他表示的整数也就越大

”定点小数“的表示

有符号数溢出标志

乘除法，OF位为1，表示溢出

2.3：定点数的运算

符号扩展运算

定点“整数”的符号扩展：在原符号位和数值位“中间”添加新位，正数都添0；负数原码添0，负数补码添1（负数的反码添1）

定点“小数”的符号扩展：在数值位的“后面”添加新位，正数都添0，负数原、补码添0（负数反码添1）

short扩展为undesign int比较特别，只需要改变int的解释方式就行，就是short先变成int，再从int变成undesign int

移位运算

算数移位

原码

算数右移

算数左移

补码

正数的算数移位：和原码一致

负数的算数移位：

右移：高位补1，低位舍弃

算数右移的时候，高位补的数要和原符号位一致。如果右移导致被丢弃的数是1，则发生精度丢失

左移：低位补0，高位舍弃

如果左移导致被丢弃的数和目前最高位的符号位的数不一致，表示发生溢出

逻辑移位

左移和右移都补0，移除的位直接舍弃

注意，如果逻辑左移导致丢弃的数是1的话，就表示发生了溢出

注意，如果逻辑右移导致丢弃的数是1的话，就表示精度丢失

循环移位

例题

溢出判断运算

手算判断

机器判断溢出

单符号位溢出判断

C语言中的强制类型转换

1：C语言中的定点整数如：int、short、long等都是用“补码的形式”存储的

2：在int、long、short前面用“unsigned”修饰可得到一个“无符号”定点整数

无符号数与有符号数的转换

无损

char->int->long->double

float->double

short（2B）转换成int（4B）

符号扩展

定点“整数”的符号扩展：在原符号位和数值位“中间”添加新位，正数都添0；负数原码添0，负数反码、补码添1

定点“小数”的符号扩展：在原符号位和数值位“后面”添加新位，正数都添0，负数原、补码添0

有损

int（4B）转换成short（2B）

int->float

float->int

乘法运算（22新增）

本质原理

原码乘法运算

乘法运算的实现思想

符号位“单独进行处理”参与运算的符号位进行“异或运算”

数值位取绝对值进行乘法运算（被乘数和乘数都要存绝对值）

原码的一位乘法

补码乘法运算

除法运算（22新增）

本质原理

原码除法运算

除法运算的思想

恢复余数法，本质商和手算是一样的

恢复余数法

符号位不参与运算，最后通过被除数和除数符号的异或运算的结果确定商的正负号

ACC寄存器中存放被除数/余数，通用寄存器中存放除数，MQ寄存器中存放要上的商值

1：刚开始通过比较ACC中的被除数和通用寄存器中的除数大小，来确定MQ寄存器中的商应该上0还是上1 2：当被除数大于除数的时候，商上1，然后ACC中的值变成被除数“减去”除数得到的余数即可（默认一开始肯定会上1，然后发现商上1有问题才会执行商上0，也就是“恢复余数”）     当被除数小于除数的时候，商上0，然后ACC中的值不变（此时余数=被除数），因为有这种情况的存在，所以我们才给这种算法起名为恢复余数法~ 3：将上一步得到的余数进行逻辑左移（高位舍弃，低位补零。），得到的结果再和除数比较大小（这个结果当成新的被除数，重复2-3的步骤n次） 4：对原始的被除数和除数进行异或运算得到商的最终正负

加减交替法（不恢复余数法）

加减交替法其实就是把恢复余数法中间进行恢复余数的几步进行了”综合“，得到了最后的操作结果（省略了中间恢复余数的过程）

其实就是恢复余数法的一次优化，优化了“默认刚开始一定上1，发现不合适才上0然后去恢复正确的余数”

补码除法运算

加减交替法

符号位参与运算

被除数、除数、余数都采用双符号位

1：被除数和除数同号，则用被除数“减”除数；异号则用被除数“加”除数 2：余数和除数同号，商上1，然后余数左移1位“减去”除数；       余数和除数异号，商上0，余数左移1位“加上”除数 3：重复2步骤n次，但是最后一位商恒上1，不管倒数第二位的余数和除数是否异号

2.4：标志位PSW生成

CF

OF

SF

ZF

3：浮点数的表示和运算

3.1：浮点数的表示

阶码+尾数

尾数给出具体数值，阶码指明小数点前移或后移多少位

阶码反应的是“宏观数值”的大小，尾数反应的是数值的“精度”

阶码通常是用补码、移码表示的定点整数

尾数通常是用补码、原码表示的定点小数

真值

浮点数标准IEEE745

符号位+阶码（移码）+尾数（原码）

float短浮点数：1+8+23

double长浮点数：1+11+52

long double临时浮点数：1+15+64

IEEE745的“阶码用移码”表示

移码的定义：移码=真值+偏置值

float的偏置值=127，因为短浮点数的阶码=8位

double的偏置值=1023，因为长浮点数的阶码=11位

long double的偏置值=16383，因为临时浮点数的阶码=15位

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

转换步骤

1：首先确定基本格式（大多数是float-单精度浮点数）

2：将数值转换成2进制并完成对应的“规格化”步骤（规格化之后就可以确定“尾数”和“阶码”的具体值了）

3：根据第2步的规格化之后的数值确定“符号+阶码+尾数”（注意尾数“规格化"之后的最高位不用写在尾数中，他是隐含的）

例题1

例题2

将int类型的000011011111...11转换成float

单精度浮点数能表示的最小绝对值和最大绝对值分别是多少

最小：(1.0)*[2^(-126)]

最大：(1.1...)*(2^127)

3.3：浮点数的运算

对阶

两个参与运算的浮点数进行对阶，“小阶向大阶看齐”，尾数算数右移右移一位（尾数算术右移相当于小数点左移），阶码加1，直到阶码相同

注：对阶可能导致丢失末位精度

浮点数规格化

什么时候浮点数需要进行规格化

左规（最高数值位无效要左规）

“数值位”最高位无效时，通过“尾数算数左移”、阶码减1的方法处理，直到尾数最高数值位有效时停止

原码表示的尾数规格化

尾数的最高数值位必须是1（就是我们说的位数最高数值位必须是一个有效值的意思）

补码表示的尾数规格化

尾数“最高数值位”必须和“符号位”相反（就是我们说的位数最高数值位必须是一个有效值的意思）

右规（溢出需要右规）

若采用双符号位表示尾数，则当运算后尾数“假溢出”时，可以通过运算结果尾数右移、阶码加1的方法处理，得到正确结果

舍入

尾数的位数有限导致的问题，常用方法：0舍1入或者恒置1

尾数加减

通常采用双符号位表示尾数，这样可以挽救尾数溢出

溢出判断

若规定阶码不能超过2位，则规格化后阶码超出范围，表示溢出

阶码上溢

阶码下溢

采用双符号位，可通过右规拯救尾数溢出

4：运算方法和运算电路（新增考点）

加法器

电路基础知识

逻辑运算

与、或、非（基本逻辑运算）

与非、或非、异或、同或（复合逻辑运算）

图示

门电路

最基础的逻辑元件，用于实现逻辑运算

多路选择器和三态门

多路选择器

三态门

回忆：各种门电路的图形，全加器的图形和输入输出信号

加/减运算

补码加/减运算器

加法器的实现

一位全加器的设计

得到两个值：si和ci

si表示本为和，ci表示更高位的进位

*代表与，+代表或

串行加法器

一位全加器+进位触发器，只能一位一位的加

串行进位的并行加法器

多个全加器简单串联，可多位同时加

计算速度取决于进位产生和传递的速度

设计

带标志位的并行加法器

CF用于表示无符号数加减是否溢出、OF用于表示有符号位是否溢出

总结

算数逻辑单元ALU

实现算数运算、逻辑运算、辅助功能（移位、求补等）

图示

乘/除运算

定点数的移位运算

5：数据的存储

大小端模式

大端模式

小端模式

图示

存储在一个连续的内存块中的不同位置，只是顺序不一样（取决于大端或小端）

边界对齐

1：边界对齐：一块中必须存的是某个数据的“完整数据”。如果某一块剩余空间存不下就用空白填充，不能有残缺

2：边界不对齐：一块中剩余的小空间可以存放下一个数据的一部分，不需要用空白填充

3：对齐的具体要求就是内存的“起始地址“能被将要存储的”数据类型自身长度“整除。

4：边界对齐：起始地址可以被自身长度整除

6：数据类型转换可能出现的问题

1：溢出

2：精度丢失

3：存储系统

3.1：存储系统分类

主存（内存）

“随机存取”存储器RAM

动态RAM（DRAM）

主要用于“主存”

以电容充电原理寄存信息。这是一种“破坏性”读取的存储方式

DRAM的刷新策略

DRAM芯片采用“地址线复用”技术

线选法（扩展）

SRAM默认有1根片选线。 DRAM默认有2根片选线

“随机只读”存储器ROM

MROM

PROM

EPROM

EEPROM

辅存（外存）

辅存：磁盘、机械硬盘

缓存Cache

静态RAM（SRAM）

主要用于“高速缓冲存储器Cache”

以触发器原理寄存信息。这是一种“非破坏性”读取的存储方式

SRAM->位于“主存”和“CPU”之间，用来存放正在执行的程序段和数据，以便CPU能高速地使用它们。Cache的存取速度可与CPU的速度相匹配，但其容量小，单位成本高

CPU内的寄存器

位于CPU内部，它比缓存cache更加金贵

外存

CD、磁带等

3.2：存储器与CPU连接

1：连接原理

连接原理

1：“主存和CPU”通过“数据总线（MDR线）、地址总线（MAR线）和”控制总线“相连

2：“数据总线（MDR）的位数”与“工作频率的”的“乘积”与数据传输率成正比

3：“地址总线（MAR）的位数”决定了“可寻址的”最大内存空间

4：“控制总线”控制了总线周期的类型和本次IO操作的完成时刻

存储芯片的结构(主存)

图解

存储芯片的基本结构

存储矩阵（存储体的集合）

存储体由多个“存储单元”构成，每个存储单元又由多个“存储元”构成

存储单元：存放一串二进制代码。

存储字：存储单元中的二进制代码

存储字长：存储单元中二进制代码位数。

存储字数：理解为有多少个存储字

译码器

译码器将地址信号转化为字选通线的高低电平

MAR

存储器地址寄存器，反应存储单元个数。保存了存储体的地址（存储单元的编号），反应了存储单元的个数。所以MAR的位数和存储单元的个数有关。

MDR

存储器数据寄存器，反应存储字长（存储单元长度）。保存了要送入CPU中的数据或要保存到存储体中的数据或者刚刚从存储体中取出来来的数据。这个寄存器的长度和存储单元的长度相同。

读写控制线

每次读/写一个存储字（CPU对内存发出读、写的命令）

片选线

用于选择特定的存储芯片，在多芯片的情况下，片选线决定了哪一块存储器被选中进行操作。

说明

1.“主存”由“半导体元件和电容器件”组成。

2.驱动器、译码器、读写电路均位于“主存储芯片”中。

3.MAR、MDR位于CPU的内部芯片中

4.“存储芯片”和“CPU芯片”通过系统总线（数据总线、系统总线）连接。

2：寄存器扩张

单块存储芯片和CPU连接

8KB*16位的存储芯片是指：这个芯片有2的13次方位个存储单元（此时存储单元个数等于存储字数），每个存储字的字长是16。我们可以根据这一信息确定MAR和MDR的位数

多块存储芯片和CPU连接

字（MAR）扩展法

通过”扩展字“来达到可以连接多块“存储芯片”的目的（可以寻找到更多位数的位置）

译码片选法

译码器的使用分析地址空间

位（MDR）扩展法

存储字长是指一个存储单元中可存储的最大二进制位数。位数一般等于大小，存储字长可以是8位、16位、32位等

现在的数据线一般都是64位的，如果存储字长是小于64位的话会导致CPU的性能无法完全发挥出来，数据传输能力从存储单元"向CPU输送数据的能力"会因为MDR的不足而下降很多

效果上相当于提高了CPU处理数据的宽度

字位扩展法

只要上面两种理解了，这个就是上面两种的结合

3：双口RAM“和”多模块存储器

双口RAM（空间并行）

RAM是“按照存储地址”随机存取的存储器

支持“两个CPU”通过“地址总线”同时访问主存RAM

可以“同时”读“同一个存储单元”； “不能同时”写“同一个”存储单元； “不能同时”一读一写“同一个”存储单元

多模块存储器（时间并行）

多体“并行(MAR)”存储器

高位交叉编址

实际效果“相当于单纯的扩容”，并不会过多的提升访问主存速度

采用内存地址的“最高位的2bit”内容，来区分不同的“存储体”，此时同一个存储体的存储单元“最高2bit信息”肯定是一样的

理论上多个存储体可以并行访问，但是由于通常会连续访问（0~9）存储地址，这些地址都“位于同一内存条”上，访问完一次之后都需要等恢复时间

低位交叉编址

当存储块数M>=T/r，可使流水线不间断（CPU不用等内存，因为当一个内存正在恢复的时候，我们cpu直接就去访问别的已经恢复好的内存行）

每个存储周期内可读写地址连续M个字

微观上，M个模块被串行访问。宏观上，每个存取周期内所有模块被并行访问

单体“多字(MDR)”存储器

为了减少恢复时间的“恢复次数”，我们可以扩展每个存储单元的字数

MDR的总线宽度也要扩展为M个字，每次并行读出M个连续的字

缺点

3.4：高速存储器Cache

6.0：cahce行包含的信息

Cache中存储地址内容组成

格式：有效位（0/1）+标记Tag（对应的物理地址块号）+块内数据

一定存在的

有效位：用来表示当前cache块的数据是否有效。

标记位：“唯一确定”标识当前cache（相当于人名）

块内数据位：用的最多的是，当前数据块的大小

不一定存在的

“脏位”位数：用于表示当前cache是否被修改过

行号/组号位数：直接相连映射/组相连映射有用

替换信息（映射方式）：cache“替换”方式策略需要用到的标志位

6.1：Cache的基本工作原理

工作原理

将“某些经常使用的”主存数块据复制到Cash中，缓和CPU与主存之间的速度代差

局部性原理

时间局部性：现在访问的地址，不久之后很可能被再次访问

空间局部性：现在访问的地址，其附近的地址很有可能会被访问到

性能分析

理解Cache的命中率、缺失率

命中率：CPU想要访问的信息已经在Cache中的比率

缺失率：1-（命中率）

两种访存方式

先访问Cache，发现未命中，再访问主存

同时访问主存和Cache，若Cache命中则停止访问主存

其他概念

主存和Cache之间以“块”为单位进行数据交换

主存的“块”又叫“页/页框/页面”。Cache的“块”又叫“行”

主存地址可拆分为主存块号，块内地址的形式

6.2：Cache和主存之间的映射方式

全相连映射

全相连映射映射关系

没有公式，可以随便放

访存步骤

“物理地址结构”

标记（主存字块标记）+块内地址

优缺点

优点：Cache存储空间利用充分，命中率高

缺点：查找“标记”最慢，有可能需要“对比所有行的标记”（线路复杂，成本高，速度低）

直接映射

直接映射的关系

Cache块号=（主存块号） mod （Cache的总块数）

访存步骤

“物理地址结构”

标记（主存字块标记）+Cache号（cache字块标记）+块内地址

优缺点

优点：对于任意一个地址，只需对比一个“标记”,速度最快（硬件简单，容易实现）

缺点：Cachec存储空间利用不够充分，命中率低

组相连映射

组相连映射的关系

Cache组号=（主存块号）mod（Cache的总组数）

访存步骤

“物理地址结构”

标记（主存字块标记）+组号（cache字块标记）+块内地址

优点

上面两种映射方式的折中，综合效果最好（硬件较简单，速度较快，命中率较高）

地址特征

术语

n路组相连映射-每“n个Cache行”为一组

2路组相连说明每个cash组中包含2个cash行。

6.3：Cache中主存块的替换算法

随机算法（RAND）

实现简单，但是完全没有考虑局部性原理问题

命中率低，稳定性极差

先进先出算法（FIFO）

若Cache已满，则替换掉最先被调入的Cache块

可能出现抖动现象：刚被替换的Cache很快又被重新掉回来

“最久”未使用算法（LRU）

为每一个Cache块设置一个计数器，用于记录每个Cache块多久没有被访问过。直到Cache满了以后把计数器最大的那个Cache替换掉

LRU是基于局部性原理，近期被访问过的主存块，在不久的将来可能被再次访问，因此淘汰掉最久没有被访问到的Cache块是合理的

“最近不经常”使用（LFU）

为每一个Cache设置一个计数器，用于记录每个Cache块被访问了多少次，当Cache块满了之后，淘汰掉计数器最小的

LFU算法-可能某一段时间经常用到的Cache，导致计数器猛增,如：视频聊天的相关块。但是关闭视频聊天以后，这个Cache块可能就没用了。所以LFU的实际效果不如LRU效果理想

6.4：Cache写操作策略

写命中（内容在Cache和主存中都有）

全写法（直写）

当CPU对Cache写命中时，必须“同步修改”Cache和主存中的数据块，一般使用写缓冲

使用写缓冲，CPU写的速度很快，若写操作不频繁，则效果很好。但是若写操作频繁的话可能会因为写缓冲饱和而发生阻塞

写回法（回写）

当CPU对Cache写命中时，只修改Cache中的内容，而不立即写回主存，只有“当此Cache被淘汰的时候才会写会主存”

减少了访存的次数，可以提高效率，但是“存在数据不一致的隐患”

写不命中（只在主存中存在，Cache中没有）

写分配法

当CPU对Cache写不命中时，把主存的块调入Cache，在Cache中修改，通常搭配写回法使用

非写分配法

当CPU对Cache写不命中时，直接在主存中修改写入即可，跟Cache没关系。通常搭配全写法使用

多级Cache

现代计算机通常采用多级Cache结构，各级Cache间常采用“全写法”+“非写分配法”，Cache和主存间常采用“写回法”+写分配法

6.5：大题解答

3.5：虚拟内存（分配回收、置换、扩充）

铺垫（操作系统需要熟知的内容）

虚拟存储器的基本概念

页式虚拟存储器

页表的作用只是为了映射当前页的数据被映射到了内存的那个地址

有效位

磁盘地址

主存地址

访问位（引用位）

脏位

逻辑地址和物理地址

逻辑地址又叫虚地址，就是我们程序员看到的地址

物理地址又叫实地址，指的是在主存中的实际存放地址

CPU执行的机器指令中，使用的是逻辑地址，因此需要通过页表将逻辑地址转换为物理地址

段式虚拟存储器

按照“功能模块拆分”，区别于上面的按照页的形式拆分方式

由于段式虚拟存储器在辅存分成的块大小都是不一样的，所以在主存（内存）中也就不再进行分块了，只需要记录下起始位置

段页式虚拟存储器

先按照功能模块拆分成段，然后再把各个段划分成大小固定的页

TLB快表

TLB构成

Tag标记位

有效位

页框号

只有2种映射方式

全相连映射

组相连映射

没有直接相连映射

操作系统涉及的精讲

1：内存管理基本概念

1.1：什么是内存，有何作用

存储单元、内存地址的概念和联系

按字节编码VS按字编码

按字节编址

按字编址

1.2：“进程运行”的基本原理和要求

指令的工作原理

形式：操作码+若干参数（可能包含地址参数）

程序的链接和装入

编译

链接

装入前静态链接

装入时动态链接

运行时动态链接

装入

编译时绝对装入

装入时可重定位装入

运行时动态重定位装入

运行

1.3：内存管理的功能

内存空间的分配和回收

连续分配管理方式

单一连续分配

固定分区连续分配

动态分区连续分配

首次适应算法（First fit）

临近适应算法（Next fit）

最佳适应算法（Best fit）

最坏适应算法（Worst fit）

非连续分配管理方式

基本分页存储管理基本概念

基本分页存储管理

页表

逻辑地址结构---可拆分为[页号P，页内偏移量W]

如何实现地址转换（逻辑地址---》物理地址）

基本地址变换机构

页表寄存器的作用

地址变换过程

1：根据逻辑地址算出页号、页内偏移量

2：页号的合法性检查（与页表长度对比）

3：若页号合法，再根据页表起始地址、页号找到对应内存块号（第一次访存：查页表）

4：根据页表项中记录的内存块号、结合页内偏移量得到最终真实的物理地址

5：访问物理内存对应的内存单元（第二次访问内存：访问目标内存单元）

图示

具有快表的地址变换机构

什么是快表

引入快表后，地址的变换过程

1：根据逻辑地址算出页号、页内偏移量

2：页号的合法性检查（与页表长度对比）

3：若页号合法，首先去快表（TLB）中，根据逻辑页号找对应的内存块号，可以命中的话就直接进入第5步，否则就执行第4步

4：若页号合法且快表中没有访问记录，再根据页表起始地址、页号找到对应内存块号（第一次访存：查页表），然后将该逻辑页号对应的内存块号存入快表（TLB）中，方便下一次使用

5：根据页表项中记录的内存块号、页内偏移量得到最终真实的物理地址

6：访问物理内存对应的内存单元（第二次访问内存：访问目标内存单元）

局部性原理

时间局部性

空间局部性

两级页表

单级页表存在什么问题？如何解决

所有“页表项”必须连续存放，“页表过大”时需要很大的连续空间

一段时间内并非所有的页面都能用到，因此“没必要让整个页表”常驻内存

两级页表的原理

将长长的页表“再分页”

*逻辑地址结构：一级页号、二级页号、页内偏移量

*常用术语：页目录表、外层页表、顶级页表

如何实现地址表换

1：按照地址结构将逻辑地址拆分成三部分

2：从PCB中读出页目录表始址，根据一级页号查页目录表，找到“下一级页表”在内存中的存放位置

3：根据二级页号查表，找到最终想要访问的“内存块号”

4：结合页内偏移量得到物理地址

两级页表问题需要注意的细节

多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级

多级页表的访存次数（假设没有快表机构）---N级页表访问一个逻辑地址需要N+1次访存

基本分段存储管理

分段

将地址空间按照程序“自身的逻辑关系划分为若干段”，每个段都有自己的段名（在低级语言中，程序员都是使用这些段名来编程），每段从0开始编制。每个段在内存中占据连续的空间，但各段之间可以不相邻

逻辑地址结构：（段号-》段名，段内地址-》段内偏移量）

”段号的位数“决定了每个进程”最多“可以分成几个段

”段内地址的位数“决定了每个段的最大长度

段表寄存器的作用

存放段表起始地址

存放段表长度

段表

记录"逻辑段"到"实际存储"地址的映射关系

地址变换

1：由逻辑地址得到段号、段内地址

2：段号与段表寄存器中的段长度比较，检查是否越界

3：由段表始址、段号找到对应的段表项

4：根据段表中记录的段长、检查段内地址是否越界

5：由段表中“基址+段内地址”得到最终的物理地址

6：访问目标单元

图示

段页式管理方式

分段和分页的优缺点

分页管理

优点：内存利用率高，不会产生外部碎片，只会有少量的页内碎片

缺点：不方便按照逻辑模块实现信息的共享和保护

分段管理

优点：很方便按照逻辑模块实现信息的共享和保护

缺点：如果段长过长，需要为其分配很大的连续空间。另外段式管理会产生外部碎片

分段+分页

将地址空间按照程序自身逻辑关系划分为若干段，在将各段分为大小相等的页面

将内存空间分为和页面大小相等的一个个内存块，系统以块为单位为进程分配内存

逻辑地址结构：（段号，页号，页内偏移量）

段表、页表

每个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表存放地址组成

每个页对应一个页表项。各页表项长度相同，由页号（隐含）、页面存放的内存块号组成

地址变换

1：由逻辑地址得到段号、页号、页内偏移量

2：段号与段表寄存器中的段长度比较，检查是否越界

3：由段表始址、段号找到对应段表项

4：根据段表中记录的页表长度，检查页号是否越界

5：由段表中的页表地址、页号得到查询页表，找到相应页表项

6：由页面存放的内存块号、页内偏移量得到最终的物理地址

7：访问目标单元

访问一个逻辑地址所需访存次数

第一次：查段表，找到目标页表存放位置、第二次：查页表，找到目标数据存放位置、第三次：访问目标单元

可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存

内存空间的扩充（实现虚拟性）

覆盖技术

一个固定区

若干覆盖区

对用户不透明，增加了用户编程负担。覆盖技术只适用于早期的操作系统，现早已成为历史

交换技术

内存空间紧张时，系统将内存中“某些进程”暂时换出到外存，把外存中具备运行条件的进程换入到内存

磁盘分为“文件区”和“对换区”，换出的进程放在对换区

覆盖和交换技术的区别

覆盖是在“同一个进程”或程序中进行的

交换是在“不同进程间”进行的

地址转换

绝对装入

可重定位装入

动态运行时装入

内存保护

目的

保证各个进程在自己的内存空间运行，不会越界访问

两种方式

设置“上下限寄存器”，进程指令要访问某个地址时，CPU进行越界检查

利用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。基址寄存器中存放的是进程的起始物理地址。界地址寄存器存放的是进程的最大逻辑地址

2：虚拟内存管理

2.1：虚拟内存的基本概念

传统存储管理方式的特征

内存空间的分配与回收

连续分配

单一连续分配

固定分区分配

动态分区分配

首次适应算法（First fit）

临近适应算法（Next fit）

最佳适应算法（Best fit）

最坏适应算法（Worst fit）

非连续分配

基本分页存储管理

基本分段存储管理

基本段页式存储管理

特征

1：一次性

2：驻留性

虚拟内存的定义和特征

多次性

对换性

虚拟性

如何实现虚拟内存技术

访问的信息不在内存时，由“操作系统”负责将所需信息从外存调入内存

内存空间不够时，将内存中“暂时用不到的”信息换出到外存

虚拟内存的实现

请求分页存储管理

请求分段存储管理

请求段页式存储管理

2.2：请求分页管理方式

页表机制

修改位

状态位

外存地址

访问字段

缺页中断机构

缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面

缺页中断是因为要访问的目标页面不在内存中，属于“内中断”，属于内中断中的“故障”--也就是可能被系统修复的异常

地址变换机构

找到页表项是需要“检查页面”是否存在内存中

若页面不在内存中，需要“请求调页”

若内存空间不够，还需要“换出页面”

页面调入内存后，需要“修改相应的页表项”

2.3：页面置换算法

最佳置换算法（OPT）

先进先出置换算法（FIFO）

最“久”未使用算法（LRU）

时钟置换算法（CLOCK）---又叫“最近未用算法”

为每个页面设置一个“访问位”，再将“内存中”的页面都通过链接指针链接成 一个“循环队列”。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。 如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面。

若第一轮扫描所有页面都是1，则在第一轮结束后进行第二轮扫描的时候将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会 有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）。

改进型的时钟置换算法

条件都相同时，应“优先淘汰”没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。

“修改位”=0，表示页面没有被修改过；修改位=1，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过， 且被修改过。

算法规则：

1：将所有可能被置换的页面排成一个循环队列

2：第一轮：从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位

3：第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧“访问位”设为0

4：第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于 替换。本轮扫描不修改任何标志位

5：第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于 替换。

6：由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一 定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多 会进行四轮扫描

例题

特别注意

2.4：页面分配策略

驻留集

页面分配、置换策略

固定分配VS可变分配

局部置换VS全局置换

三种策略

*固定分配局部置换

*可变分配局部置换

*可变分配全局置换

调入页面的时机

预调页策略

请求调页策略

从哪里调页

对换区、文件区区别

对换区足够大

对换区不够大

UNIX方式

2.5：工作集

2.6：抖动（颠簸）现象

CPU访存过程

3.6：固态硬盘SSD

固态硬盘的结构

1：固态硬盘是由“多个闪存芯片”构成，每个闪存芯片包含”多个块“，每个块包含”多个页“。固态硬盘的块相当于磁盘的磁道。固态硬盘的页，相当于磁盘的扇区

2：固态硬盘存储数据是以“页”为单位的，不同于磁盘，磁盘存取数据是以数据“扇区”为单位的。

3：固态硬盘读写数据是以“页”为单位，但是擦除SSD上的数据必须以“块”为单位

闪存翻译层

固态硬盘与磁盘相比的特点

1：SSD用电路的方式控制访问，可以“随机访问”位置，读写速度快，支持随机访问。而磁盘是通过“移动磁臂旋转”磁盘控制访问的位置，因此不支持随机访问，只能按照顺序依次访问

2：固态硬盘安静无噪音，耐摔抗震，能耗更低但造价更贵

3：SSD的一个快被擦除的次数过多的话，可能会导致磁盘块坏死，而机械硬盘不会产生坏死现象

读写性能特性

1：以“页”为单位进行读写

2：以“块”为单位进行擦除

3：SSD支持“随机访问”数据，闪存翻译成可根据电路迅速定位数据的存储位置。这就是为什么固态硬盘速度快于机械硬盘

4：读数据很快，写入数据相对较慢

磨损均衡技术

1：就是使用均衡擦除，尽可能让“擦除”操作均衡的分布在各个块上，以提升使用寿命

2：动态磨损均衡

3：静态磨损均衡

5：中央处理器

5.1：CPU的“功能和结构”

CPU内部结构1

控制器（CU）

1：程序（指令）计数器（PC）

2：指令寄存器（IR）

3：指令译码器（CU）

4：微操作信号发生器

5：MAR和MDR

运算器（ALU）

FR：程序状态字寄存器(PSW)

暂存寄存器（ACC、MQ等）

通用寄存器

移位器

计数器

8086CPU内部结构2

BIU（控制器）

1：程序（指令）计数器（PC）

2：指令寄存器（IR）

3：指令译码器（CU）

4：4个段寄存器

5：地址累加器

6：指令队列缓冲寄存器

EU（运算器）

1：通用寄存器X

2：FR标志寄存器（PSW）

3：暂存寄存器（ACC、MQ）

4：算数逻辑单元ALU

图示

功能

指令控制

操作控制

时间控制

数据加工

中断处理

根据用户是否可见分类

5.2：指令执行过程

指令的周期

取址周期

间址周期

执行周期

中断中期

指令执行方案

单指令周期

多指令周期

流水线方案

三种周期概念

指令周期（最大）

机器周期（中间）

时钟周期（最小）

补充：存取周期

5.3：数据通路的功能和基本结构

专用数据通路

一般数据通路

内部总线

单总线结构

多总线结构

系统总线

5.4：控制器(CU)的功能和工作原理

控制器（CU）如何指挥整个系统工作

微命令和微操作的关系

1：CU发出一个“微命令”，可完成”对应的“微操作

2：N条微命令，构成一条微指令

3：N条微指令，构成一个微程序

4：一个“微程序”指令对应一条“指令”，具体是由 “机器指令的操作码” 字段指明“微程序的入口”地址

控制存储器（CM）

控制存储器（CM）用来存放实现全部“指令系统”的“所有微程序”，它是一种只读型存储器 .一旦微程序固化，机器运行时则只读不写

注意

一个”时钟周期“内可以并行完成“多个相容的”微操作，且”同一个微操作“可以在”不同的指令运行阶段“使用

不同指令的“执行周期”所需“时钟周期”不相同，为了简化设计，往往选择“定长的机器周期”（CPU周期）

我们可以根据”指令操作码、目前的机器周期（CPU周期）、时钟周期、机器状态条件“即可确定现在这个”时钟周期“下应该发出哪些微命令

控制器的设计（22考研弱化了）

硬布线控制器

硬布线控制器的设计

1：分析每个阶段的操作序列

2：选择CPU的控制方式

3：安排微操作的时序

4：电路设计

特点

微程序控制器

5.5：指令流水线

指令流水线的基本实现

顺序执行方式（不用流水线）

一次重叠执行方式

二次重叠执行方式

图示

指令流水线

超标量和动态流水线的基本概念

5.6：多处理器的基本概念（22新增）

1：计组概述

1：计算机系统的层次结构（硬件+软件）

2.1：计算机系统的基本组成

硬件包括

软件包括

2.2：计算机硬件的五大基本组成

早期的冯诺依曼机结构

五大组成部分

输入设备

输出设备

存储器

存储体

存储元

存储单元

存储字

存储字长-MDR

存储字数-MAR

CPU内的寄存器

MAR

MAR位数反应了存储单元的个数，学名是“存储地址寄存器”

MAR=4个2进制位就可以表示16种状态（一共能寻址16个地址）

MDR

MDR位数反应了存储单元字长。取出来的数据可以放到这里，学名是“存储数据寄存器”

MDR=16个二进制位的话，每个存储单元大概率也只能存储16个二进制位，以确保不会造成资源浪费

控制器

PC/IP

IR

CU

运算器

ALU（关键）

ACC

MQ

X

PSW

工作过程

控制器中的操作

运算器中的操作

图示

现代计算机结构

2.3：计算机软件的分类

1：系统软件和应用软件

1：系统软件

2：应用软件

2：三个级别的语言

编译程序

汇编程序

解释程序

2.4：计算机的工作过程

1：把程序和数据“装入主存储器”

2：把源程序“转换成可执行文件”

3：从可执行文件的首地址开始“逐条执行指令”

五层

M4：高级语言机器（执行高级语言）

M3：汇编语言机器（执行汇编语言）

M2：操作系统机器（向上提供广义的指令）

M1：传统机器（执行机器语言指令0、1）

M0：指将传统机器的二进制指令M1分解成更小的几部分二进制指令，进而解析其中含义

2：计算机性能指标

机器字长

CPU一次能执行的字长（它通常是MDR（存储字长）的整数倍（0.5/1/2/3...）方便取值）

总线宽度

存储带宽

存储器容量

CPU

时钟周期

主频（时钟频率）CPS

数值上等于“时钟周期的倒数”

CPI

Clock cycles Per Instruction

IPS

Instructions Per Second

数值上=（主频/CPI）

CPU执行时间

（指令条数*CPI）/主频

指令条数*CPI*时钟周期

FLOPS

其他

4：指令系统（大题结合汇编）

4.1：概述

4.2：指令格式

基本格式

操作码

定长操作码

变长操作码

操作数

寻址方式

偏移量/立即数

二进制代码表示指令

零地址指令

一地址指令

二地址指令

三地址指令

四地址指令

4.3：指令的寻址方式

操作码指令寻址

顺序寻址

(PC)+“1”---》PC

跳跃寻址

执行“转移类指令”，导致PC不按常理走了，直接跳跃到其他位置

操作数地址寻址

主存

直接寻址

间接寻址

偏移寻址

基址寻址

变址寻址

相对寻址

寄存器

寄存器直接寻址

寄存器间接寻址

隐含寻址

立即数

4.4：完整的指令周期

取指阶段

间指阶段

执行阶段

中断阶段

4.5：CISC和RISC的基本概念

1：复杂指令系统计算机（CISC）

一条指令完成“一个复杂的基本功能”

代表：X86架构，主要用于笔记本电脑、台式机等

绝大多数是“微程序”控制

使用不定长操作码”指令格式

优点：在指令字长有限的前提下仍保持比较“丰富的指令种类”

缺点：增加了指令译码和分析的难度，使“控制器的设计复杂化”

2：精简指令系统计算机（RISC-适合流水线）

指令流水线大多数都采用的RISC架构

一条指令“只完成一个”基本的动作，“一个复杂的基本功能”需要多条基本动作（指令）来完成。

代表：ARM架构，主要用于手机、平板等

绝大多数是"组合逻辑"控制，并且只有Load和Store指令才允许访存

使用定长操作码”指令格式

优点：定长操作码对于“简化计算机硬件设计”，提高指令译码和识别很有利

缺点：指令数量增加时会占用更多的固定位，留给“操作数地址的位数受限制”

3：数据的对齐方式和大小端存放方式

大小端模式

大端模式

小端模式

图示

存储在一个连续的内存块中的不同位置，只是顺序不一样（取决于大端或小端）

边界对齐

1：边界对齐：一块中必须存的是某个数据的“完整数据”。如果某一块剩余空间存不下就用空白填充，不能有残缺

2：边界不对齐：一块中剩余的小空间可以存放下一个数据的一部分，不需要用空白填充

3：对齐的具体要求就是内存的“起始地址“能被将要存储的”数据类型自身长度“整除。

4：边界对齐：起始地址可以被自身长度整除

4.6：高级语言程序与机器代码之间的对应（22年新增）

1：编译器、汇编器、链接器的基本概念

1：高级语言如C语言，经过“编译器的编译”形成汇编语言。

2：汇编语言经过“汇编器的操作”变成一条条的机器语言。

3：汇编语言再记过“链接器”的链接，形成完整的机器语言

2：选择结构语句的机器级表示

3：循环结构语句的机器级表示

4：过程（函数）用对应的机器级表示

要求我们可以自己读懂2019年的汇编类型真题的每一行代码

5：函数调用

6：总线

6.1：总线概述

1.1：什么是总线

1.2：总线有哪些特性

机械特性

电气特性

时间特性

功能特性

总线的猝发传输

1.3：总线的分类

按总线功能

片内总线

系统总线

控制总线（CB）

数据总线（DB）

地址总线（AB）

通信总线

按数据传输格式

串行总线

优点

缺点

并行总线

优点

缺点

按时序控制方式

同步总线

异步总线

分离式通信

1.4：总线结构（按功能划分）

单总线结构

双总线结构

三总线结构

性能指标（大题常用）

总线周期（以时钟周期衡量）

总线的工作频率

总线的时钟周期（以s、ns等时间单位衡量）

总线的时钟频率

总线宽度

总线带宽

总线复用

信号线数

6.2：总线仲裁

”集中仲裁“方式

链式查询方式

优点

缺点

计数器定时查询方式

优点

缺点

独立请求方式

优点

缺点

“分部仲裁”方式

6.3：总线操作和定时

总线传输的四个阶段

总线的“申请分配阶段”

总线的“寻址阶段”

数据的“传输阶段”

结束阶段

总线传输的定时

同步定时方式（同步通信）

异步定时方式（异步通信）

不互锁、半互锁、全互锁

半同步通信（了解）

分离式通信（了解）

1："主模块"申请占用总线，使用完成之后就“放弃"总线的使用权。

2："从模块"准备数据，这个时候总线“可以被其他设备使用”，这点是分离式通信和以上3种不同的地方。大大提高了总线的使用效率

3：从模块准备完毕之后再次申请占用总线，将各种信息送至总线上

7：IO系统（第7章）

7.1：I/O系统基本概念

1.1：IO（输入输出）系统

IO硬件

IO设备

IO接口

IO软件

IO指令

操作码

命令码

设备码

通道指令

通道程序是提前编好存放在主存中的

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

1.2：CPU对IO的控制方式

低速设备

程序定时IO查询方式

程序中断IO方式

高速设备

DMA方式

通道方式

7.2：IO外部设备（额外关注）

磁盘存储器

磁盘设备的组成

磁头

磁道

盘面

柱面

扇区

磁盘驱动器

磁盘控制器

盘片

性能指标

容量

记录密度

平均存取时间

数据传输率

工作过程

寻道+旋转+传输

旋转时间

传输时间

例题

磁盘调度算法

先来先服务（FCFS）

最短寻找时间优先（SSTF）

扫描寻找算法（电梯算法、SCAN）

循环扫描算法（C-SCAN）

LOOK算法

C-LOOK算法

磁盘阵列RAID

RAID0

RAID1

RAID2~5

常见的校验方式

光盘存储器

固态硬盘SSD

7.3：IO接口和IO端口

3.1：IO接口的结构和对应的作用

IO接口的功能

1：实现“CPU和外设”的通信，将对应的数据格式转换成双方都能够识别的信号。

2：传送“主机和外设”之间的“控制信息”和“状态信息”，只有“外设状态为就绪”的时候，主机才会发送命令。只有”主机发送控制命令后“外设才会执行。

3：对“主机和外设”的速度差异进行缩小，主要是通过设置“数据缓冲寄存器”用于暂存数据，避免速度不一致而丢失数据

4：根据“主机对外设”发出的命令，进行“地址选择和设备选择”。

IO接口的基本结构

“控制寄存器”和“状态寄存器”

控制寄存器

状态寄存器

数据缓冲寄存器（DBR）

图示

3.2：IO端口及其编址

IO端口

控制端口

状态端口

数据端口

地址译码逻辑

统一编址

独立编址

3.3：功能区别

7.4：IO接口的控制方式

4.1：程序查询方式

分类

独占式查询

定时查询

1：每次“检查IO接口缓存”数据是否准备完毕

2：一次程序查询的时间开销是多少个时钟周期

3：CPU的介入频率是多少-取决于查询程序上CPU的时间频率

特点

优点

接口设计简单，设备量少

缺点

有可能产生“数据丢失”的问题

图示

4.2：程序“中断查询”方式

1：中断系统

中断的类型

内中断

”人为“内中断

“被迫”内中断

外中断

“人为”外中断

“被迫”外中断

被迫外中断工作流程

中断请求

中断响应

1：中断源有中断请求

2：CPU允许中断，即没有“关中断”的前提

3：当前指令“执行完毕”且没有更加紧急的任务

中断处理

1：中断隐指令

保存断点

关中断

引出中断服务程序（中断引指令）

2：中断服务程序

1：保护现场

2：中断服务

3：恢复现场

4：开中断

5：中断返回

3：图示

单重中断和多重中断

单重中断

多重中断

中断屏蔽技术

中断响应优先级

中断处理优先级

2：含义

缺点

有可能产生“数据丢失”的问题

补充图示

4.3：DMA方式

DMA控制器

组成（了解）

主存地址计数器(AR)

传送长度计数器（WC）

数据缓冲寄存器

DMA触发器

控制/状态逻辑

中断机构

主要功能（同下面的传送过程）

传送前（预处理）

传送时

传送后（后处理）

传送过程

预处理

CPU向DMA接口发送一系列指令

后处理

一整块数据传输完成后，DMA接口给CPU中断

数据传送

CPU继续执行主程序，DMA控制器完成数据传送

传送方式

停止CPU访存

优点：控制简单

缺点：未充分发挥CPU对主存的利用率

交替访存

优点：不需要总线使用权的申请建立和归还的过程

缺点：硬件逻辑较为复杂

DMA的周期挪用

IO设备需要访存时，挪用一个或几个存取周期

和程序中断方式的区别

4.4：通道方式

通道是一种具有”特殊功能的处理器“，能对IO设备进行统一管理（有的大型商用机上可能会接很多IO设备，如果都让CPU管理，CPU就会累死）

通过IO指令启动通道，通道执行通道指令序列，控制指定的IO设备完成一系列任务，（通道程序存放在主存中）通道执行完规定的任务后，向CPU发出中断请求，之后CPU对中断进行处理。

通道和DMA都是不直接让CPU管理外设，但是不同于DMA的是”通道可以理解成是弱鸡版的CPU，有专门的处理器以及指令语言，DMA没有