此份笔记是本人学习过程中自己总结记录的，其内容受到课堂教学内容、采用教材、个人认知水平的影响。虽然笔者力图保证内容准确以及易于理解（起码自己能看懂），但难免存在谬误或者渲染问题。非常欢迎您通过邮件等方式联系我修改，让我们一起让这份笔记变得更好！

一、绪论

1.1、微型计算机组成

  • 微处理器（即 CPU，包括控制器、运算器，寄存器）

  • 存储器

    • 外存
    • 内存
      • RAM
      • ROM

  • 输入、输出设备

  • 总线

    • DB：数据总线
    • CB：控制总线
    • AB：地址总线

1.2、有符号数的表示与运算

正数的原、反、补码相同

通常计算机内采用补码进行算术运算，若要得到结果还要转换为真值

因为[x]补+[±y]补=[x±y]补[x]_补+[\pm y]_补=[x\pm y]_补

补码在模 2 意义下运算，得到的就是正确结果的补码

有符号数运算时的溢出判别：双高位判别法

有符号数运算时，计算机不区分符号位与数值位，同样地对每一位进行模 2 意义下的运算

以 n 位二进制数的运算为例：

相加时，只有同号才可能溢出

  • 若两正数相加，符号位都为 0，本位不会有进位；数值位最高位有进位时，此时符号位变为 1，说明结果错误。这种情况叫做正溢出，此时有

    Cn⊕Cn−1=1C_n \oplus C_{n-1}=1

  • 若两负数相加，符号位都为 1，本位一定会有进位；数值位最高位没有进位时，此时符号位变为 0，说明结果错误。这种情况叫做负溢出，此时仍有

    Cn⊕Cn−1=1C_n \oplus C_{n-1}=1

其他情况都可以转化为上述两种情况。

综上，若满足Cn⊕Cn−1=1C_n \oplus C_{n-1}=1，说明有溢出，运算结果有误；否则无溢出，运算结果正确（只对有符号数有效）

标志寄存器中的 OF（Overflow Flag） 有：OF=Cn⊕Cn−1OF=C_n \oplus C_{n-1}

1.3、计算机的性能指标

计算机完成某项任务的时间称为响应时间或者执行时间

单位时间内完成的任务数量称之为吞吐率

每条指令需要的平均时钟周期数称为CPI

执行一个程序所需的CPU 时间可由以下公式计算：

CPU时间=指令数×CPI×时钟周期\text{CPU时间}=\text{指令数}\times \text{CPI} \times \text{时钟周期}

MIPS 数（Million Instructions Per Second）,也即每秒执行了几百万条的指令，计算公式如下：

MIPS=指令数执行时间×106\text{MIPS}=\frac {指令数}{执行时间\times 10^6}

二、8086 微处理器结构

2.1、总结构

主体分为两部分，总线接口单元 BIU 和执行单元 EU

BIU 每周期取指令，放入指令队列中（8086CPU 的指令队列大小是 6 个字节），指令通过 EU 控制器后，送入到 EU 执行。

实现了取指和执行分离。

8086CPU 的地址总线是 20 位的，内部的数据总线和接口都是 16 位的.。

地址的形式为段地址+偏移地址，比如 073F:0100

该地址中段值为 073F，偏移量为 0100，真实的物理地址就是(073F<<4)+0100=083F0，也即段地址左移四位后加上偏移地址得到真实地址。

2.2、8086 的寄存器结构

  • 通用寄存器

    • 数据寄存器，每个都是 16 位，可分为高低两个 8 位的寄存器，如 AX 可分为 AL、AH。虽然以下四个寄存器名字各不相同（在某些指令中，这些寄存器就体现了特殊性），但是他们相互“兼容”，有良好的通用性。

      • AX：累加器
      • BX：基址寄存器
      • CX：计数寄存器
      • DX：数据寄存器

    • 地址指针，变址寄存器，用于存放偏移地址

      • SP：堆栈指针
      • BP：基址指针
      • SI、DI：变址寄存器

      凡是含有 BP 的寻址方式，段地址由 SS 提供；否则由 DS 提供

  • 控制寄存器

    • IP：指令指针，16 位，相当于 8 位机中的 PC，用于存放下一次要取出的指令的偏移地址

    • FLAG：标志寄存器，16 位，其中包括 9 个 1 位的标志寄存器，如 OF，CF 等

  • 段寄存器，用于存放段地址

    • CS：代码段寄存器
    • DS：数据段寄存器

    CS:IP 即代表了下一条指令的地址

三、8086 指令系统

以移位指令 mov 为例

3.1、mov 指令的可能格式

1
2
3
MOV 目的操作数, 源操作数 /*基本格式*/
MOV R, R/M/im /*R代表寄存器，M代表存储器，im代表立即数*/
MOV M, R/im

其功能是将源操作数中的内容送到目的操作数中

要注意可能会出现字长不明确的问题，此时要在 mov 后面加上 Word 或者 Byte 进行指定

3.2、寻址

对应于操作数类型的不同，有很多种不同的寻址方式

  • 立即寻址：即通过立即数寻址。操作数就在指令代码中，该操作数就被称为立即数

    1
    MOV AX, 1234H

    上面这条指令执行后，AL 中的内容变为 34H，AH 中的内容别为 12H。低字节存放在低地址单元，所以 8086 是小端模式（Little Endian） 。

  • 寄存器寻址：操作数在某个寄存器中

    1
    MOV AX, BX

    上面这条指令执行后。AL 中的内容变得与 BL 相同，AH 中的内容与 BH 中相同

  • 存储器寻址：操作数在存储器中

    • 直接寻址：直接通过操作数的地址来访问数据段。通过加上中括号，将操作数或者操作数的内容解释为立即数，而不是地址

      1
      MOV AX, [1234H]

      上面这条指令等价于

      1
      MOV AX, DS:[1234H]

      也可以指定段值

      1
      MOV AX, ES:[1234H]

    • 间接寻址：

      1
      MOV AX, [BX]

  • I/O 端口寻址：操作数在 I/O 端口中

    I/O 端口常包括数据端口、状态端口、控制端口等，与存储单元统一编码。使用的是 IN 和 OUT 指令

    • 直接端口寻址：适用于端口地址只有 8 位

      1
      2
      IN AL, 10H
      OUT 50H, AX

    • 间接端口寻址：端口地址为 16 位时只能使用间接寻址。先将端口地址放在 DX 中（也只能用 DX 中转）

      1
      2
      MOV DX, 1000H
      OUT DX, AL

    在 IN 和 OUT 指令中，会自动把数字解释为端口地址

3.3、8086 指令的编码格式

操作码（1 字节）+寻址方式（0~1 字节）+位移量（0~2 字节）+立即数（0~2 字节）

可见 8086 指令的长度是不固定的

举个例子

1
MOV AL, [2018H]

对应的二进制指令为1000 1010 0000 0110 0001 1100 0010 0000可以如下表划分：

op d w mod reg r/m imm
100010 1 0 00 000 110 0001110000100000
  • op 段：操作码，100010 即 MOV 指令的操作码。
  • d 段：d=1 表示 reg 段是目的操作数（目的寄存器）的编码，d=0 表示 reg 段是源操作数（源寄存器）的编码。
  • w 段：w=1 表示字操作，w=0 表示字节操作。
  • reg 段：操作数的编码。操作数中必须有一个是寄存器，8086 指令系统不允许操作数全部来自存储器（这样指令的执行速度很慢）。
  • mod 段和 r/m 段：共同决定了寻址方式，可以查表得到
  • 位移量段：从左到右恰好为 1820H， 小端序

3.4、移位指令

基本格式：

1
指令助记符 目的操作数, 移位次数（可以是数字或寄存器）

包括以下四种：

  • SHL：逻辑左移，最高位移到 CF，最低位补 0，其余位左移
  • SHR：逻辑右移，最高位补 0，最低位移到 CF，其余位右移
  • SAL：算术左移，与逻辑左移一样
  • SAR：算术右移，最高位不变，最低位移到 CF，其余位右移

3.5、转移指令

以无条件转移指令 JMP 为例，用于段内直接转移的时候

1
JMP 目标标号

可分为：

  • 短程转移：转移量在-128~127 的转移。假如17D7:0109上的指令为

    1
    JMP 100

    对应的二进制指令为EBF5，前两位EB十六进制数是短程转移对应的操作码，后两位F5代表的是从当前 PC 转移到目标标号的偏移量。

    本条指令占两个字节，PC 指向的下一条指令的地址为17D7:010B。下一条指令的地址加上偏移量：010B+FFF5=1 0100（运算时，要把两位十六进制数的偏移量按照补码规则拓展为四位后再相加），所以正确跳转到了 17D7:0100。

    可以在 JMP 后面加上 SHORT 来指定短程转移（计算机会判断是否可以短程转移，如果不能，还是会进行进程转移）

    1
    JMP SHORT 100

  • 近程转移：转移位移量大小在-2^-31~2^31-1 之间的转移。假如17D7:0100上的指令为

    1
    JMP 300

    对应的二进制指令为E9FD01，前两位十六进制数E9是近程转移对应的操作码，后四位FD01是偏移量。由0103+01FD=0300，可见确实转移到了 17D7:0300。注意指令中的立即数是按小端模式存放的。

    可以通过在 JMP 后面加上 NEAR 来指定近程转移。

3.6、算术运算指令

  • 乘法指令

    • 无符号数乘法指令 MUL

      1
      MUL BL

      默认将 BL 与 AL 相乘，结果放在 AX 中

      1
      MUL BX

      默认将 BX 与 AX 相乘，结果放在 [DX,AX] 中

      当乘积的位数超过乘数的位数时，会设置 OF=CF=1

    • 有符号数乘法指令 IMUL

      与无符号乘法类似，区别在于对乘积进行符号拓展时的位数并不算乘积本身的位数，这会影响 OF 和 CF 的设置。例如：

      1
      2
      3
      MOV AL, -1
      MOV BL, 2
      IMUL BL

      易得结果是-2，也即 0xFE，符号拓展后 AX 中应该为 0xFFFE。乘积实际上并没有超出 8 位二进制数可以表示的范围，乘积虽然是 16 位，超过了 8 位，但只是符号拓展的结果，所以 OF=CF=0。

  • 除法指令

    • 无符号除法 DIV

      1
      DIV BL

      默认是 AX 做被除数，BL 做除数，AL 放商，AH 放余数

      1
      DIV BX

      默认是 DX+AX 做被除数，BX 做除数，AX 放商，DX 放余数

    • 有符号除法

      完全类似

四、MIPS 指令系统

4.1、MIPS 指令初步

下面是一条 MIPS 指令

1
add $s0,$t0,$t1

这一条指令的意思是，将寄存器 t0 和 t1 中的数相加，送到寄存器 s0 中

以$开头表示是一个寄存器，MIPS 中一共有 32 个寄存器（$0~$31），统一用五位二进制数编码

其中有

  • $zero（$0），恒为 0，只读
  • $v0~$v1（$2~$3），一般用于保存结果（result）
  • $a0~$a3（$4~$7），一般用于放参数、变量（argument）
  • $t0~$t7（$8~$15），一般用于临时存放数据
  • $s0~$s7（$16~$23），一般用于保存值

MIPS 不允许操作数为存储器。必须先将存储器的数据装载（load）到寄存器中，才可以操作，对应的指令为 lw（load word）

MIPS 是大端模式

4.2、MIPS 指令编码格式

MIPS 指令的长度是固定的，都是 32 位，大致分为三种

  • R 型（用于寄存器）

    op rs rt rd shamt funct
    6bit 5bit 5bit 5bit 5bit 6bit
    • op：操作码
    • rs：第一个源操作数的寄存器编码
    • rt：第二个源操作数的寄存器编码
    • rd：目的操作数的寄存器编码
    • shamt：位移量，某些指令会用到
    • funct：功能码，是操作码的扩展，与 op 一起表示操作的类型

    举个例子

    1
    2
    3
    add $s0,$t0,$t1

         rd  rs  rt

    对应的机器码应该是

    1
    000000 01000 01001 10000 00000 100000

    其中 op 段值为 0，funct 段值为 32 就表示 add 操作。不是移位指令，所以写 shamt 部分为 0，然后写上操作数对应的寄存器编码

  • I 型（用于立即数）

    这种类型的指令里只有两个寄存器，多出的一个寄存器编码的位置加上 shamt 段和 funct 段，一共 16 位，用于储存立即数。所以格式如下：

    op rs rt imm
    6bit 5bit 5bit 16bit

    立即数在在指令中是补码形式（MIPS 是大端模式，所以顺序和我们习惯的一样）

    举个例子

    1
    2
    3
    addi $s0,$t0, 3

          rt  rs imm

    对应的机器码应该是

    1
    001000 01000 10000 00000000 00000011

    注意这里的 rs 应该是$t0，rt 是$s0

    另一个例子

    1
    2
    3
    lw $t0,1200($t1)

        rt  im  rs

    lw即 load word，加载字节，将以$t1 中地址为首地址，第 1200 个字节的东西，也即 t1[300]

    对应的机器码是

    1
    100011 01001 01000 00000100 10110000

    特别地，sw（store word）指令中

    1
    2
    3
    sw $t0,1200($t1)

        rt  im   rs

    是把 rt 的内容送到 rs 与 imm 一起指明的存储单元中。rs 不意味着源寄存器，rt 不意味着目的寄存器了。

    另一个特殊的例子，beq、bne 有条件跳转指令

    1
    2
    3
    beq $s0,$s1,1

         rs  rt imm

    上面这条指令的意思是如果$s0和$s1的内容相同，跳转到当前 PC+imm*4 的地址去。（因为每个指令都是四个字节，为了扩大转移范围，一定要记得乘 4）

  • J 型指令（无条件跳转）

    这种指令的格式如下：

    op addr
    6bit 26bit

    举个例子

    1
    2
    3
    60020：j EXIT
    ...
    60100：EXIT

    对应的机器码应该是

    1
    000010 00000000000011101010110001

    前 6 位就是 j 指令的操作码，后面的是 60100/4=15025 的二进制表示。

    当前 PC（加 4 之后）的高四位（4bit）与地址部分左移两位之后（28bit），一起拼接成要跳转到的地址。

4.3、调用子程序

在 8086 系统中

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
; 主程序
MOV AX,5
MOV BX,8
; 调用F1子程序段，会自动将下一条指令的PC压栈，方便返回
; 栈是从高地址存到低地址。压栈过程，先将堆栈指针SP的值-2，然后往栈里压入IP
CALL F1
ADD AX,BX

; 子程序
; PROC表示子程序开始，NEAR表示是在同一个段内，所以前面压栈的时候只要压偏移量即可
F1 PROC NEAR
; 先将可能被覆盖的寄存器值也压栈，保护现场
; PUSH指令会自动先将SP-2，然后把AX压入栈中（注意是小端模式）
; 80x86系统中，有PUSHA,POPA指令，自动将所有寄存器压栈，弹栈
PUSH AX
PUSH BX
ADD AX,7
ADD BX,8
; 子程序结束时，按照逆序弹栈，恢复到进入时的状态
; POP指令会自动将栈顶的值赋给BX，然后SP+2
POP BX
POP AX
; RET指令相当于POP IP，即返回主程序
RET
F1 ENDP

在 MIPS 系统中

一般约定，$t0~$t7是可以被覆盖的，$s0~$s7必须要被压栈保存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*主程序*/
L1:
...
/*JAL指令会自动将当前PC放到$ra（$31）中*/
JAL fact
...


/*子程序*/
fact:
/*MIPS指令都是32位，堆栈指针一次要-4*/
addi $sp,$sp,-8
sw $ra,4($sp)
sw $a0,0($sp)

slti $t0,$a0,1
beq $t0,$zero, L1

/*用v寄存器储存结果，这也是不会被覆盖的*/
addi $v0,$zero,1
addi $sp,$sp,8
/*回到主程序*/
jr $ra

五、计算机中的算术运算

5.1、有符号无符号数的加减法

之前的笔记已经介绍过，不再赘述

5.2、乘法

被乘数 m 位，乘数 n 位，则积需要 m+n 位存储

5.2.1、无符号数乘法

以两个 32 位无符号二进制数相乘为例

朴素手工乘法的结构

image-not-found

一开始被乘数放在被乘数寄存器的低 32 位，积被初始化为 0

  • 检测乘数寄存器的最低位，如果是 0，不需要经过加法器；如果是 1，被乘数和积送加法器相加，然后送回积寄存器

  • 被乘数左移一位，乘数右移一位

改进乘法器结构

image-not-found

改进的核心思想就是让被乘数左移改成让积右移。积寄存器的低 32 位放乘数，积寄存器的高 32 位一开始置 0，表示积。

  • 检测积寄存器的最低位（也就是乘数的最低位），如果是 0，不需要加法器；如果是 1，被乘数与积寄存器的高 32 位相加
  • 整个积寄存器右移一位

实际上，积寄存器是 65 位，最高位用于保存加法器的进位。然后移位的时候就移进去。

现代乘法器

改进的乘法器使全加器的位数减少了一半。但是在现代的计算机设计中，有足够多的元件可供使用，用大量的加法器直接并行运算，大大提高速度。

5.2.2、有符号数乘法

有符号数乘法，一种处理办法是符号位和数值位分开处理。乘数和被乘数的符号位相异或得到积的符号位，剩下的数值位正常做乘法，最后再合在一起。

5.2.3、MIPS 中的乘法指令

MIPS 中用一对 32 位寄存器 Hi, Lo 来存储 64 位的积

具体指令如下

1
2
mult $s0, $s1
multu $s0, $s1

将两个寄存器中的数相乘，放到{Hi, Lo}中

可以用

1
2
mflo $t0
mfhi $t1

将 Hi, Lo 寄存器的值移到指定的寄存器

​

5.3、除法

5.3.1、无符号数除法

首先假设除数为 32 位无符号数

5.3.1.1、朴素手工除法（恢复余数法）

image-not-found

  1. 一开始，余数寄存器放被除数，除数寄存器的高 32 位放除数

  2. 余数寄存器中的数减去除数寄存器中的数，结果送余数寄存器：

    • 如果此时余数寄存器中的数非负，商寄存器左移，最低位设为 1
    • 如果余数寄存器中的数是负数，则余数寄存器中的数再加上除数寄存器中的数，结果送回到余数寄存器，回到原状态。商寄存器左移，最低位设为 0。

  3. 若余数小于除数，或者商的位数正好达到存储限制，则结束；否则除数右移一位，返回第二步

同样，类似乘法器，也可以改进

image-not-found

改进核心思想是把除数右移改成余数左移。一开始，余数寄存器初始化为被除数（补齐为 64 位），每次用余数寄存器的高 32 位减去除数。然后运算时不断左移，余数寄存器右边空出来的位置正好放商，每次商最低位。

最后余数寄存器高 32 位就是余数，低 32 位就是商。

实际上，余数寄存器也是 65 位，保证加法器进位不丢失（减除数就是加“负除数”的补码）

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

步骤如下：

  1. 首先用余数减掉除数，得到新余数

  2. 判断余数的正负

    • 如果余数为正，商 1
    • 如果余数为负，商 0

    如果商恰好达到存储上限，结束运算；否则继续第三步

  3. 余数左移一位，根据第二步中的正负情况，余数加上或者减去除数，回到第二步

注：因为余数寄存器左移了，所以最终要记得移回去，才能得到正确的余数

分析：假设除数是DD，某次余数减完除数后的得到除数变成RR。按照前面的恢复余数法，若R>0R>0，则下一次余数减完除数后余数应该变成2R−D2R-D；若R<0R<0，则应该先恢复余数，则下一次余数减完除数后余数会变成 2(R+D)−D=2R+D2(R+D)-D=2R+D

所以可以统一起来，无论余数正负，先左移一位，再加或者减除数

这种方法使得除法所需的时钟周期减少了，而且计算一个除法的时间相对固定，容易控制

5.3.2、有符号数除法

同样是符号位与数值位分开处理，但是除法中，若不加以规定，余数为正或为负时会出现不同的商。

所以一般规定余数的符号与被除数的符号相同，这样可以保证结果唯一

5.3.3、MIPS 中的除法指令

可以发现改进后触除法器和乘法器的结构是一样的，MIPS 中实现除法用到的寄存器也与乘法相同

MIPS 中用 Hi 存放余数，Lo 存放商，具体指令如下：

1
2
div $s0, $s1
divu $s0, $s1

5.4、浮点数

规格化数：一个采用科学记数法表示的数，如果没有前导零且小数点左边只有一位有效位，则这个数是规格化数。

二进制数的科学记数法形如：1.0111011×2110001111.0111011\times 2^{11000111}(为了简便，指数用十进制数来写)。

IEEE754 标准中：

单精度浮点数

符号位 S 指数 E 尾数 F
1bit 8bit 23bit

表示的值为

(−1)S×(1+F)×2E−127(-1)^S\times (1+F)\times 2^{E-127}

双精度浮点数

符号位 S 指数 E 尾数 F
1bit 11bit 52bit

表示的值为

(−1)S×(1+F)×2E−1023(-1)^S\times (1+F)\times 2^{E-1023}

一些特例，以单精度浮点数为例：

指数 尾数 表示对象
0 0 0
0 非 0 非规格化的数（但是也有意义）
1~254 任何值 正常的浮点数
255 0 无穷（转化一下可发现指数已经是最大了）
255 非 0 NaN

5.5、浮点数运算

5.5.1、浮点数加法

  1. 对阶。指数小的往指数大的对，也就是小阶对大阶。这是因为尾数位数比较多，小阶对大阶的时候，就是把阶数小的数的尾数右移，就算丢失，也是幂次比较小的那些，无伤大雅。总而言之，是为了提高运算精度。
  2. 相加
  3. 规格化
  4. 舍入，保证尾数部分长度不超出

5.5.2、浮点数乘法

  1. 指数直接相加，再减去一个偏阶
  2. 有效位相乘
  3. 有效位的乘积规格化
  4. 舍入

六、设计 CPU

为了设计一个 CPU，我们从最简单的情况开始，并逐步完善并理解一个真正的 CPU 是怎样构成的。

以下为单周期 CPU

6.1、一个 MIPS 的核心子集

为了实现一个最基本的 CPU，我们只需要以下指令：

  • 存储器访问指令：lw, sw
  • 算术逻辑指令：add, sub, and, or, slt
  • 分支指令：beq, j

这个 MIPS 指令的子集已经足够说明 CPU 基本原理

6.2、执行指令时发生了什么

根据指令类型的不同，会有不同的执行过程，但是都大同小异

  • 第一步：程序计数器 PC 中的内容是下一条指令的地址，根据这个我们取出下一条指令
  • 第二步：对指令内容进行解析，可能要读取某些寄存器

在上述两步中，我们需要注意几个细节：

  • 出现了程序计数器 PC，也就是说我们需要一个PC 单元
  • 根据 PC 的内容来取出指令，则有一个专门存放指令的区域，也即指令存储器
  • 读完指令之后，PC 仍要指向下一条指令的地址，也就是说，我们要对 PC 中的内容加 4，然后再送回 PC，所以我们需要一个加法器。
  • 要读取某些寄存器。我们知道 MIPS 系统一共有 32 个寄存器，我们需要一个寄存器堆来放这些寄存器，并且能根据编码访问到这些寄存器。

接下来，我们根据要实现的指令类型来进一步分析，我们还需要那些模块

  • 对于存储器访问指令，涉及到地址的计算和对存储器的访问，自然需要算术逻辑单元 ALU，以及数据存储单元。此时 ALU 的运算结果是作为地址送到数据存储单元中。数据存储单元的内容也可以被读，然后写到寄存器堆中。
  • 对于算术逻辑指令，当然也需要 ALU。但是此时 ALU 的运算结果是送回到寄存器堆中。
  • 对于分支指令，如果是跳转指令，要对 PC 进行算术运算，也需要一个加法器。

由上面的分析，我们可以得到这样一个结构图：

image-not-found

注意到，有时候某些单元会有两种可能的输入来源。例如送入 PC，既可能是原 PC+4，也有可能是跳转指令运算后得到的地址。这时，就要加上多路选择器 MUX。

同理，送回寄存器堆的可能是 ALU 的计算结果，也可能是储存器中的内容，也同样要加上 MUX。

另一个方面，根据指令的不同，相同单元可以表现出不同行为，这需要根据指令中的操作码和功能码，给出不同的控制信号。

加上 MUX 和控制信号后，可以得到下图：

image-not-found

6.3、设计数据通路

针对每一个不同的单元，我们要确定哪些数据流向这个单元，哪些数据从这个单元流出去，这就是数据通路。

  • PC 单元：根据 PC 的内容，到指令存储器获取到下一条指令，然后 PC 本身的值要经过加法器（或者说始终设置为加法模式的 ALU）加 4 之后，送回 PC

  • 指令存储器：根据输进来的地址，找到对应单元，输出该单元上指令

    image-not-found

  • 寄存器堆：根据送进来的指令，以 R 型指令为例，会解析出四个输入，三个寄存器编号和一个数据。三个寄存器编号中，有两个是要读的寄存器编号，一个是要写的寄存器编号。

    如果是存数和取数指令，则是理解为三个输入，基址、偏移量和目的地址。

    还需要一个单元进行符号拓展，将偏移量拓展为 32 位后再与基址相加

  • 数据存储器：两个输入，一个是要写入单元的地址，一个是要写入的数据；一个输出，是被读单元的内容

  • ALU：两个输入，即两个运算数；一个输出，运算结果

6.4、控制信号的实现

在上图中，可以看到许多控制信号。为了使其正确运行，我们也要进行编号，对不同的指令，给出不同的控制信号。

以 ALU 单元的控制信号为例，可以设计三位的控制信号如下：

ALU 控制信号 0000 0001 0010 0110 0111 1100
功能 与 或 加 减 小于则置位 或非

最后引入控制单元，负责根据指令，发出所有相应的控制信号

image-not-found

6.5、多周期 CPU 与流水线技术

单周期技术是在一个周期内完成一条完整的指令，单周期 CPU 的时钟周期受限于执行时间最长的那条指令，这样会使 CPU 的性能受到限制。

多周期技术是将一条指令分为几个步骤，每个时钟周期完成一个步骤，也是流水线技术的基础。但是下一条指令仍然要等待上一条指令完成后才能开始执行。

流水线技术是一种实现多条指令重叠执行的技术，使多条指令可以并行，重叠执行。

一个 MIPS 指令通常可以分为五个步骤，每一个步骤称为一个流水级：

  • IF：取指令
  • ID：指令译码和读寄存器
  • EX：执行操作或者计算地址
  • MEM：访问内存
  • WB：写寄存器

MIPS 指令集就是为流水线而设计的：

  • 指令均为 32 位，可以很容易进行取值和译码
  • MIPS 指令格式类型少

流水线运行过程中，可能会出现许多冒险现象，从而引起流水线堵塞：

  • 结构冒险：同一个部件可能被多条指令在同一个周期使用，导致冒险。所以我们使用分离的指令存储器和数据存储器，且对一个存储器，读、写在不同时刻进行，从而避免这种情况。

  • 数据冒险：一个流水级必须等待另一个流水级完成，导致当前流水级不得不暂停。如

    1
    2
    add $s0, $t0, $t1
    sub $t2, $s0, $t3

    按照流水线来讲，sub 指令准备读$s0 时，add 指令还没有写进去，这就导致了数据冒险。

    为了解决这个问题，可以在编写代码的时候，尽量避免连续使用某寄存器的情况（现在一般编译器都会对这个问题进行优化）

    或者可以直接在要用的时候提前取出所需数据（在上面这个例子中，是直接从 ALU 取出所需数据），这就叫做前推（forwarding）或者旁路（bypassing）

    即便用上了旁路，有时还是不得不阻塞一个流水级的时间，我们称为流水线阻塞，也称为气泡。

  • 控制冒险：下一条指令是否要执行依赖于上一条指令的结果，但是上一条指令正在执行过程中。

    一个典型的例子就是分支跳转指令。

    可以用阻塞的办法，等结果出来后再继续执行

    也可以采用预测的方法，比如预测分支跳转不会发生，一直往前走，只有分支确实发生的时候，才停下来（阻塞），然后根据结果来执行正确的指令。另一种预测的方法是，根据之前预测的情况，来决定性这次预测。

6.6、流水线的数据通路与控制信号

流水线中的数据通路和单周期中的数据通路是类似的，但是流水线中会出现一些问题：

例如，当某条指令已经要准备写寄存器了，但是此时指令译码得到的 rd 不是它本来要写入的寄存器的编码，而是它后面的指令中的 rd。

我们当然可以让每一条指令都有自己的独立通路，但面对大量的指令时，这显然是不现实的。实际上，通过在流水级与流水级之间增加保存中间数据的寄存器，可以解决这个问题。

image-not-found

根据寄存器在哪两个流水级之间，可以自然地给出四个流水级的命名。

以 lw 指令为例，看一下这些新增的寄存器何时被写入或读出了哪些数据：

  • IF：指令存储器取出的指令写入 IF/ID 寄存器中，增加后的 PC 地址也写入 IF/ID 寄存器中
  • ID：从 IF/ID 寄存器中读出指令，将译码出的两个寄存器编号和一个十六位的立即数扩展后写入 ID/EX 寄存器中。同时，递增后的 PC 地址继续向下传递。
  • EX：从 ID/EX 寄存器中读出相应的值（理论上只需要 rs 寄存器的值，但是处理器并不知道此时是在编码那一条指令，所以会把 rs、rd 寄存器的值都读出来。这样可以简化控制信号。）送入 ALU 中相加，然后将结果存入 EX/MEM 寄存器中。同时递增后的 PC 地址继续向下传递。写寄存器的编号也要继续向下传递，不然就会出现之前提到的问题。
  • MEM：从 EX/MEM 中读出要访问的地址，并将该地址上的数据存入 MEM/WB 寄存器中。写寄存器编号与递增后的 PC 地址继续传递。
  • WB：从 MEM/WB 寄存器中读取数据，并根据传递过来的写寄存器编号写到寄存器堆中的对应位置。

以上过程中，一直在强调把可能会用到的数据全部往下传，以及要把可能会被覆盖掉的数据一并传下来（比如这里提到的写寄存器的编号）

6.7、流水线上的数据冒险

6.7.1、检测数据冒险

考虑下面这段代码

1
2
3
4
5
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)

这里第二条指令马上要在 EX 阶段使用（更新后的）$2 的值，但是此时第一条指令要在 WB 阶段才把值写入寄存器堆，所以产生了数据冒险。

解决方法就是使用旁路，提前将数据送入 ALU 的输入端。

把这种情况抽象出来，也就是 EX 冒险：

EX/MEM.RegRd=ID/EX.RegRs,EX/MEM.RegRd=ID/EX.RegRt\text{EX/MEM.RegRd=ID/EX.RegRs}, \text{EX/MEM.RegRd=ID/EX.RegRt}

对于第一条和第三条指令之间的冒险，则是 MEM 冒险：

MEM/WB.RegRd=ID/EX.RegRsMEM/WB.RegRd=ID/EX.RegRt\text{MEM/WB.RegRd=ID/EX.RegRs} \text{MEM/WB.RegRd=ID/EX.RegRt}

除此之外，某些指令不需要写回寄存器，自然也不会对该指令后面的指令产生影响，这时不用检测冒险。也即如果要构成冒险，还要满足：

EX/MEM.RegWrite=1\text{EX/MEM.RegWrite}=1

同时，还不能把零寄存器作为目的寄存器，也即：

EX/MEM.RegRd≠0,MEM/WB.RegRd≠0\text{EX/MEM.RegRd}\neq0, \text{MEM/WB.RegRd}\neq0

6.7.2、实现旁路

image-not-found

添加旁路模块，将 ID/EX 寄存器中的 Rs 或 Rt 与 EX/MEM.RegRd 或 MEM/WB.RegRd 送入旁路模块比较，给出 Foward 和 FowardB 信号，从而将需要的值从 EX/MEM 寄存器或 MEM/WB 寄存器中直接送到 ALU 中。

6.7.3、一些更复杂的情况

1
2
3
add $1, $1, $2
add $1, $1, $3
add $1, $1, $4

这种情况下，执行第三条指令时，若按上面的条件进行检测，会同时检测出 EX 冒险和 MEM 冒险，也即

ID/EX.RegRs=EX/MEM.RegRd且ID/EX.RegRs=MEM/WBRegRd\text{ID/EX.RegRs=EX/MEM.RegRd} 且 \text{ID/EX.RegRs=MEM/WBRegRd}

而实际上，此时 EX/MEM 寄存器中的结果才是我们想要的，所以不能按照 MEM 冒险处理，而应该按照 EX 冒险处理。所以在检测 MEM 冒险中还要加上一个条件：没有 EX 冒险

这样第三条指令就会按照 EX 冒险执行旁路了

6.7.4、必须要阻塞的情况

1
2
3
4
5
lw $2, 20($1)
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7

这种情况下，当 and 指令要用$2寄存器的内容时，lw 指令才刚执行完 EX 阶段，EX/MEM 存储器中还没有$2的内容，旁路也无能为力，只能阻塞流水线。

这种情况要在 ID 级进行检测

ID/EX.MemRead==1&&(ID/EX.RegRt==IF/ID.RegRs∣∣ID/EX.RegRt==IF/ID.RegRt)\text{ID/EX.MemRead}==1 \&\& ( \text{ID/EX.RegRt==IF/ID.RegRs}||\text{ID/EX.RegRt==IF/ID.RegRt})

一旦检测到成立，要马上阻塞一个时钟周期（在使用旁路的情况下，阻塞一个周期就足够了；如果不使用，还要额外阻塞一个周期）

检测冒险，要用到 ID/EX 寄存器中相应的值，一定是 lw 指令已经过了 ID 阶段，现在到了 EX 阶段。阻塞的周期是还要再下一个周期。

lw 指令在 EX 阶段时

  • 对于在 IF 和 ID 阶段的指令，不能让它们再往前执行了，要在原地“滞留”一个周期。具体方法就是让 PC 和 IF/ID 寄存器的值保持不变，这样这两个阶段的指令相当于原样再执行了一次
  • 本周期结束后，ID/EX 寄存器会更新，在下一个周期，add 指令的 EX 阶段将会执行，而我们不应该让它执行。也就是说 EX 这一级要“空转”。具体方法就是，将 ID/EX 中所有的控制信号清除，这样不会对其他状态产生影响。

6.8、流水线上的控制冒险

1
2
3
4
5
6
40: beq $1, $3, 28
44: and $12, $2, $5
48: or $13, $6, $2
52: add $14, $2, $2
...
72: lw $4, 50($7)

上面这段代码中，只有 beq 执行完 EX 阶段，到 MEM 阶段，才能由 EX/MEM 寄存器中的值判断能不能进行跳转。而此时，下面的三条指令都已经开始执行了。

6.8.1、假定分支不发生

容易想到的一种办法就是在遇到 beq 指令时，就马上对流水线进行阻塞，直到知道能不能跳转。

一种改进的方法就是假定分支不会发生，先往下正常进行取指，译码等。假设分支确实要发生，则将之前的已经在执行的指令，相应的控制信号清空。

具体而言，就是将 IF/ID，ID/EX，EX/MEM 寄存器都清空

6.8.2、缩短分支延迟

我们之前都假定只能在 MEM 阶段判断分支发不发生，其实这种简单的计算不一定需要经过 ALU，可以转为用逻辑门来实现。这样我们就可以把分支判断提前到 ID 级

应用这个方法还会有其他的问题要考虑：比如 beq 指令前恰好是一条用了 ALU 的指令或者 load 指令，这样要比较的数在 ID 级是拿不到的，会产生数据冒险，需要阻塞；…

6.8.3、动态分支预测

在执行到某条分支指令时，看看上一次分支发生了没有。如果发生了，就从上次分支发生的地方来取新指令。

为了实现这样的操作，我们需要用一块缓存来记录分支指令的地址和上一次的结果（预测位）。

如果只使用一位预侧位来预测，则在分支总是发生的情况下，会导致误判的概率增加：

假设某个分支会连续发生 9 次，然后不发生 1 次。一开始是预测分支不发生的，所以第一次碰到这个分支的时候一定会发生一次误判；最后一次分支不发生时，由于之前连续发生了 9 次，此时的预侧位是会预测分支发生的，又发生了一次误判。

分支发生的概率有 90%，但是预测发生的概率只有 80%

所以我们一般采用两位预侧位，只有连续两次都发生或者连续两次都不发生时才更改预测结果。

6.9、中断

中断可以分为内外部

内中断有时也称为异常

事件类型 来源 对应术语
I/O 设备请求 外部 中断
用户程序进行操作系统调用 内部 异常
算术溢出 内部 异常
使用未定义的指令 内部 异常
硬件故障 外部或内部 异常或中断

CPU 标志寄存器总的中断允许位（IF）可以控制 CPU 是否响应外部中断：

  • IF=0，即关闭中断，可以用指令 CLI 实现
  • IF=1，即开启中断，可以用指令 STI 实现

异常发生时，处理器的基本操作是：

  • 关中断，防止其他中断破坏处理进程

  • 保护现场。将断点和此时程序的状态保存在堆栈或者特殊寄存器中。出错指令的地址放在异常程序计数器（EPC）中，程序状态保存在 PSW 寄存器中。

  • 识别异常。

    • MIPS 用的是非向量中断，操作系统通过一个异常处理程序，按照优先级查询异常状态寄存器，从而识别出异常事件，转到相应的中断服务程序执行。
    • 8086 采用向量中断。用硬件查询电路来识别异常，得到“中断类型号”。然后根据类型号到中断向量表中读取对应的中断服务程序的入口地址。

例如：

1
int 3

就是跳转到 3 号中断子程序。系统内部有一张向量表，可以查找到编号为 3 的子程序的首地址。向量表中可以只存储首地址，也可以存储直接整个程序（如果子程序比较短的话）

6.10、微程序控制

另一种控制的实现方式。

仿照程序设计的方法，将一条机器指令看作一个微程序。微程序由若干条微指令构成。一条微指令包含若干位微命令。

每条微指令可以理解为一个微操作，微命令就可以理解为微操作的控制信号。

所有指令对应的微程序都存储在只读存储器（又称为控制存储器）中。

七、总线

7.1、总线的概念

总线是各功能部件之间传递信息的公共通路。

使用总线结构，比点对点控制简单，成本低，扩展性好；可以将各功能部件连接起来构成一个完整系统

按连接部件分，可以分为片内总线（CPU 内各功能单元件的连线），系统总线（PCI、ISA），通信总线

系统总线是给计算机系统主要功能部件（CPU、主存、各种 I/O 控制器）之间提供连接的。可以进一步分为单总线和多总线结构。

单总线结构。CPU、存储器、I/O 接口等都连接在底板总线（Backplane Bus） 上。多设备竞争总线，而且设备之间速度差异大，性能受限。

多总线结构。有多条总线，包括局部总线、处理器——主存总线，高速 I/O 总线等。主要分为两大类：处理器——主存总线（Processor-Memory Bus），I/O 总线（I/O Bus）

系统总线通常由一组控制线、一组数据线和一组地址线构成，有些总线没有单独的地址线，地址信息通过数据线来传送，称为数据/地址复用。

7.2、总线设备

从总线使用权的角度，总线可以分为主设备和从设备。

总线主设备是能够申请获得总线使用权的设备，具有控制总线的能力，能够发起总线事务。例如 CPU。

总线从设备是不能申请总线使用权的设备，是被总线事务激活的模块或者设备。例如存储器模块。

任意时刻，一条总线上只允许存在一个主设备

八、存储

8.1、基本概念

时间局部性原理：如果某个数据项被访问，则不久的将来该数据项被访问的可能性就很大

空间局部性原理：如果某个数据项被访问，则与其相邻的数据项可能也会被访问（如循环处理一个数组）

利用这两个局部性原理就可以将存储器组织为存储器层次结构。这样的层次结构可以向用户提供尽可能大的存储容量，同时存取速度与最快的存储器相当。

CPU——Cache(SRAM)——主存(DRAM)——辅存（磁盘、闪存）

以上层次结构从左到右，速度由快到慢，成本由高到低。我们一般把 Cache 与主存统称为内存。

两个层次之间（注意没有指定是哪两个层次，所以有不同大小的块），存储信息的最小单元称为块或者行。两个层次分别称为高层存储器和低层存储器。

如果处理器需要的数据在高层存储器找到了，称为一次命中；否则称为一次缺失，要到低层存储器中寻找，以此类推。

从处理器发出请求，到访问到高层存储器中的数据并传回给处理器所需的时间称为命中时间。相对应的，从发出请求，到发现缺失，到最终从低层存储器中访问到数据并传回给处理器的时间称为缺失代价。

显然，命中时间要远远小于缺失代价。

8.2、Cache 的基本原理

当 CPU 请求访问某个数据项时，怎么知道这个数据项是否在 Cache 中，如果在的话怎么找到该数据项。这就涉及到数据在 Cache 是如何组织和存储的。

8.2.1、直接映射

直接映射就是将真实物理地址对应的数据映射到 Cache 唯一的块上。

考虑简单的情况，假设按字节编址，处理器每次请求一个字，处理器与 Cache 之间的块也是一个字。Cache 大小 8 个块。

假设要把一个数据项存到 Cache 里，最简单的方法就是把该数据的地址模 Cache 的块数，得到的就是存放在 Cache 中的位置。例如，地址(11101)2(11101)_2上的数据，应该存放在 Cache 的 第(11101)2≡(101)2≡5mod  8(11101)_2\equiv(101)_2\equiv 5 \mod 8块 中。

这种直接映射的方法实现起来比较简单，查找的时候也比较高效；但是冲突和缺失的概率比较高。

举一个更具体的例子：

  • MIPS 体系结构，地址是 32 位
  • Cache 有2n2^n个块，每个块是2m2^m个字

现在计算机一般都是按字节编址，也就是说一个物理地址对应的是一个字节的数据。但是存储器层次之间存储信息的最小单元是块，不管是存储还是访问，都是以块为单位的。所以当 CPU 要访问某个地址时，我们操作的对象是包含这个地址对应数据的那一整块数据。

MIPS 体系结构的字长是 32 位，也即 4 个字节。所以这个 Cache 的一个块有2m+22^{m+2}个字节。对于一个地址，除了低m+2m+2位外，其他高位相同的所有数据都作为一个整体存进来。主存地址中这低m+2m+2位我们就称为字节偏移，用于在块中查找具体的字节。

这个块要存放在 Cache 中编号为多少的块中呢？按照之前提到的直接映射，主存地址去掉字节偏移的若干位，再模 Cache 的块数，就得到相应的编号。这个编号我们称为索引（Index）。实际上，由于 Cache 有2n2^n位，再由模的意义，索引其实就是主存地址第m+n+2m+n+2到第m+3m+3位。

为了区分索引相同的主存地址，Cache 中还要存储地址的高位（也即剩下的部分）。这个部分称为标记（Tag)。

至此，主存地址已经被我们划分为了三个部分：

标记 索引 字节偏移
31~m+n+2 m+n+1 ~ m+2 m+1 ~ 0

与之对应的，Cache 中的每一块如下划分：

有效位 标记 数据
1 位 即主存地址中的标记部分 主存地址对应的那一块的数据

所以 Cache 中存储一个块（2m2^m个字）的数据，实际上需要2m×32+(31−(n−m−2)+1)+12^m\times32+(31-(n-m-2)+1)+1位

假如令n=10,m=0n=10,m=0，则存放210×20×4=4096KB2^{10}\times2^0\times4=4096\text{KB}的数据，实际上需要210×(20×32+(32−10−0−2)+1)/8=6784KB2^{10}\times(2^0\times32+(32-10-0-2)+1)/8=6784\text{KB}的空间。但是我们仍然称这是一个4KB4\text{KB}的缓存。

块更大，则可以更好地利用空间局部性原理，降低缺失率。但是由于 Cache 本身的大小是相对固定的，则块的数量会变少，这样就会导致块之间的竞争变多，导致块被频繁替换。同时块越大，替换一个块或者说缺失时的成本也会变大。

8.2.2、全相联 Cache

直接映射中，一个主存地址只能映射到唯一一个块中；在全相联 Cache 中，一个主存地址可以映射到 Cache 中的任意一个块中。

所以全相联 Cache 中不需要索引，主存地址仅划分为标记和字节偏移两部分，Cache 中也仅有有效位、标记、数据。

全相联 Cache 可以最大限度地减少缓存冲突，但是查找和替换时需要查找所有的块，所以一般适用于块数较少的 Cache。替换时需要一个策略来决定换哪个块，一般用LRU（Least Recently Used），替换掉最近最少使用的块。

8.2.3、组相联 Cache

是一种“折中”的做法，缓存被分为若干个组，每个组中有nn块。这样的 Cache 称为nn路组相联 Cache。一个主存地址可以映射到某个组中的任意一个块。

相联度是整个 Cache 分为的组数。显然从直接映射的相联度就是块数，全相联的相联度是 1，组相联的相联度介于两者之间。

相联度每增加一倍，索引的位数就可以减少一，标记的位数相应增加一。

组相联 Cache 中，查找和替换时，要和组内的所有块进行比较。

8.2.4、 LRU 法

在相联的 Cache 中，一个主存地址对应的块不是唯一的，替换的时候就要决定替换掉哪一个块。最常用的方法就是最近最少使用法（Least Recently Used, LRU）。

LRU 法中，被替换的块就是最久没用被使用的块。

一般用双向链表来维护，再用一个哈希表来存储主存地址与块索引的对应关系。

8.2.5、Cache 与主存的一致性

写数据时，如果只把数据写入 Cache，这会导致 Cache 与主存中的内容不一致。

为了保证一致性，可以将新数据同时写入主存和 Cache，这就是**写直达（write through）**策略。

写直达策略的时间开销非常大，一种改进是写缓冲。也即先将数据写到 Cache 和一个写缓冲区，CPU 继续执行。当数据写入主存后，再将写缓冲区中的内容释放。

另一种保持一致性的方法是写回（write back）。发生写操作时，仅写入 Cache 块中。当被修改过的块要被替换出去时，才写到主存中。一般，用一位脏位来标记某个块是否被修改过。

当写缺失时，也有两种策略。写分配，是先更新主存中对应的块，再将该块装入 Cache；写不分配是只写主存，但不装回 Cache。

通常，写直达 Cache 可以用写分配和写不分配；写回 Cache 通常用写分配。

8.3、汉明码

普通的奇偶校验码只能检测出错误，不能纠正错误。汉明码可以检测错误，同时也能纠错。

定义两个等长二进制数中对应位置不同的位的数量为这两个二进制数之间的汉明距离。

在设计编码系统时，我们希望任意两个有效码字之间都维持一定的汉明距离，这样一旦某个码字某些位发生了错误，该码字与其他有效码字的汉明距离会变小，就不满足要求，从而能检测出来。

通常的方法是利用冗余码，即给原来的信息编码中加入一些冗余位（校验位），从而维持汉明距离，提高编码系统的检测和纠错能力。

刚才提到的奇偶校验就是一种常见的方式。以偶校验为例，计算原码字中 1 的个数，然后在码字末尾添上一位是 1 或者 0 的校验位，使得添加后得到的新码字中 1 的个数总为偶数。

这样得到的所有所有码字两两之间的汉明距离至少为 2。这是因为假如改变一位校验位之外的位，校验位也必须随之改变，则改变前后的码字之间的汉明距离一定不小于 2。而且这样的码字一定满足 1 的个数是偶数。

添加奇偶校验位后的码字，如果只有一位出错了，则一定与某个有效码字间的汉明距离为 1，这就说明这是一个无效码字。也可以直接计算该码字中 1 的个数是否为偶数，来快速判断这是不是有效码字。

总结：奇偶校验的方法，通过添加一位校验位（冗余位），维持有效码字之间的汉明距离为 2，能够检测出一位的错误（实际上，可以检测出偶数位或者奇数位的错误）。

我们将这种能够检测出一位错误的编码方式称为1 位错误检测编码。奇偶校验就是最常见的 1 为错误检测编码。

汉明纠错码（ECC） 是通过对数据码添加额外的校验位得到的编码。汉明纠错码中最小汉明距离为 3，从而实现能够确定并纠正一位错误。

我们将数据码用dd表示，从左往右，从 1 开始编码：d1d2d3…d_1d_2d_3\dots

校验码用pp表示，则添加的校验码之后的码字形如：p1p2d1p4d2d3d4p8d5d6d7d8…p_1p_2d_1p_4d_2d_3d_4p_8d_5d_6d_7d_8\dots

我们用cc来统一表示：c1c2c3…c_1c_2c_3\dots

添加的校验码具体含义如下：

  • 校验位p1p_1是根据c1,c3,c5,…c_1,c_3,c_5,\dots进行偶校验生成的，这些位的编号在二进制表示下，从右往左第一位都是 1

  • 校验位p2p_2是根据c2c3,c6c7,c10c11,…c_2c_3,c_6c_7,c_{10}c_{11},\dots进行偶校验生成的，这些位的编号在二进制表示下，从右往左第二位都是 1

  • 校验位p4p_4是根据c4c5c6c7,c12c13c14c15,…c_4c_5c_6c_7,c_{12}c_{13}c_{14}c_{15},\dots进行偶校验生成的，这些位的编号在二进制表示下，从右往左第三位都是 1

  • 校验位p8p_8是根据c8c9c10c11c12c13c14c15,c24c25c26c27c28c29c30c31,…c_8c_9c_{10}c_{11}c_{12}c_{13}c_{14}c_{15},c_{24}c_{25}c_{26}c_{27}c_{28}c_{29}c_{30}c_{31},\dots进行偶校验生成的，这些位的编号在二进制表示下，从右往左第四位都是 1

  • 以此类推……

假设收到一个汉明纠错码，根据数据码先计算出校验码，与原来的校验码进行比较，如果不一致，则说明有错误。

例如收到的纠错码中，校验码(p8p4p2p1)2=(1101)2(p_8p_4p_2p_1)_2=(1101)_2，而计算出的校验码是(p8p4p2p1)=(0100)2(p_8p_4p_2p_1)=(0100)_2。将不一致的校验码的下标相加8+1=98+1=9，就说明c9c_9出现了错误。

原理是：哪一位纠错码有问题，就说明该纠错码覆盖的那些位有问题，而纠错码pip_i覆盖的是所有编号在二进制下第ii位为 1 的位。这就是集合交的过程，一个校验位就对应着出错位编号的某个二进制位。

假设某个编码系统的最小汉明距离为 d。我们将所有可能的码字抽象为空间中的点，点与点的距离就是汉明距离。

则该编码系统中，所有有效码字对应的点的距离都不小于dd，或者说所有以有效码字对应的点为球心，半径为dd的球体两两不相交。

假设有两个有效码字A,BA, B

  • 如果要检测出ee位的错误：假设AA出现了ee位的错误变成A′A'，此时所有的A′A'可以映射到以AA为球心，半径为ee的球面上的某些点。要检测出错误，也就是说不能以为这是正确的，则不能有其他有效码字在这个球面上，也即d⩾e+1d\geqslant e+1

  • 如果要纠正ee位的错误：假设AA出现了ee位的错误变成A′A'。要纠正错误，也就是能判断A′A'是AA的错码，而不是BB的错码。则分别以A,BA, B为球心的，半径为ee的球不能相交，也即d⩾2e+1d\geqslant 2e+1

要注意的是，检测出ee位的错误说的是，如果有ee位被改变了，确实能判断出这是个错误；但是不能确定这一定是个ee位的错误，也可能是一个d−ed-e位的错误。如果要确定一个错误，且能判断出这个错误是ee位的，那要满足d⩾2ed\geqslant 2e

通过给 ECC 的末尾再加上一位对于整个 ECC 的奇偶校验位，则将最小汉明距离提升到了 4，从而可以实现检测两位错误、纠正一位错误，称之为SEC/DED

更一般的，要能实现dd位数据的 SEC/DED，假设需要pp个校验位，有2p−1⩾(p−1)+d+12^{p-1}\geqslant (p-1)+d+1

8.4、虚拟存储器

Cache 是 CPU 与主存之间的缓冲，虚存可以简单理解为主存和辅存之间的缓冲。

一个程序的大部分数据存在辅存中，当程序运行时，为了快速与 CPU 交互，会把程序中最活跃的部分放到主存上来。但是实际情况是，我们需要同时运行多个程序，每个程序用哪部分的主存空间？如果主存位置不够，是不是可以将其他程序不再活跃的部分腾出来用。

为了允许多个程序共享同一个存储器，同时消除主存容量对程序的限制，实现更有效地调度，就提出了虚拟存储器技术，用于自动管理主存和辅存之间的两级存储器结构。

程序对存储器的使用情况是动态变化的，我们希望每个程序都有自己的相对固定的地址空间，也即主存中只能由该程序访问的一系列存储位置。再由虚拟存储器调度管理，再将这个地址空间映射到实际的物理地址上。这样各个进程之间不会相互干涉，从而隔离开来。

虚存与 Cache 类似，都是管理两个层次存储器。

虚拟存储器中，基本单位被称为页而不是块，访问缺失叫做缺页。运行实际程序时，处理器会产生一个虚拟地址，然后通过软件和硬件转换成一个物理地址，然后根据物理地址来访问主存、这个过程称之为地址映射或者地址转换。

虚拟地址可以划分为虚拟页号和页偏移，物理地址可以划分为物理页号和页偏移。虚拟页可以比物理页多，页偏移的位数决定了页的大小，虚拟地址和物理地址的页偏移是一样的。

由于虚存涉及到磁盘，众所周知磁盘的速度相对于主存来说是非常慢的，所以缺页的代价是巨大的，因此一般页都会比较大。

8.5、页的存放与查找

由于缺页的代价十分高，我们采用全相联的策略，也即一个虚拟页可以映射到任意一个物理页。除此之外，我们还在虚拟存储技术中用一个表来保存虚拟页和物理页之间的映射关系，从而避免遍历整个主存，这个表就称之为页表，一般放在主存中。

页表的键就是虚拟页号，值就是物理页号。除此之外还有一位有效位，如果有效位为 1，说明这个也在主存中；否则说明不在主存中，发生缺页，需要从辅存中将对应的页取过来。

既然主存上没有，那虚拟地址映射出来的是什么呢？

实际上一开始，我们会为在磁盘上为所有可能用到的页创建一片叫做交换区的空间，操作系统也会相应创建一个数据结构来记录虚拟页与这些磁盘上的页的对应关系。这个数据结构一般就是页表的一部分。

当然操作系统还会创建另一个数据结构用来跟踪哪些程序在使用哪些物理页。如果某次缺页发生时，所有的页都在被使用，就要决定替换掉哪个页。一般还是会采用 LRU 策略。

大多数操作系统采用的是近似的 LRU 算法，给每一个页添加一个引用位。如果这个页被访问了，就置 1，然后定期清零，依此就可以挑选出最近没有被访问过的页。

数据最终存储在磁盘上，如果要修改某个页的内容，按道理是在磁盘上修改。但是写磁盘的代价是巨大的，所以一般选择在主存对应的页上修改，只有该页被替换的时候，才写回磁盘。

如果这个页从写入主存，到被替换出去，都没有被修改过，那就没必要再写回磁盘，直接丢弃就好了。我们一般在页表中添加一位脏位来标识，当这个页被修改后，就将脏位置 1。被修改过的页也称为脏页。

引入页表后，程序每次访问主存都至少需要两次，第一次先访问主存中的页表，第二次才访问具体的某个物理地址。同样利用局部性原理，页表中的某个项被访问之后，也即某个虚拟地址被使用之后，不久的将来就很可能再次被使用到。所以现代处理器还有一个特殊的 Cache 来维护最近使用过的地址映射关系（页表的一个子集），这个 Cache 就称作TLB（Translation Lookaside Buffer），也称为快表。

这个 Cache 的“标记”就是虚拟页号，“数据”就是物理页号，还包括有效位、脏位、引用位等状态位。

十、I/O 系统

10.1、基本概念

输入输出系统是用于控制外设与主存、外设与 CPU 之间进行数据交换的软硬件系统

输入输出操作有以下特点：

  • 异步性：外设的速度远远低于处理器，两者采用不一样的时钟。
  • 实时性：外设的速度很慢，启动之后会按照固定的速率工作，要求主机在规定时间内完成信息交换。

I/O 接口是主机与 I/O 设备之间的桥梁与数据交换的界面。接口与主机之间通常以并行的方式传送信息；接口与外设之间有的是串行，有的是并行。

由于速度的不匹配，外设和主机之间通常是并行运行的。为了能立刻知道外设的工作状态，I/O 接口中有状态寄存器，包括忙/就绪/中断/故障等。

10.2、I/O 设备的通用模型

I/O 设备都可以抽象为三个部分：

  • 控制逻辑：根据相关信息控制设备的操作，检测设备的状态
  • 缓冲器：用于保存交换的数据信息，解决速度不匹配的问题
  • 变化器：用于电信号形式的数据与其他形式的数据进行转换

设备的电缆线一般也可以分为三种：控制信号、状态信号、数据信号

10.3、I/O 设备的控制方式

  • 无条件传送方式

    不判断 I/O 设备状态的操作方式。

    优点是软硬件实现都很简单。

    缺点是一般在外设的各种动作时间相对固定、已知时（如定时采样）才使用，否则容易出错。所以也称为程序定时传送方式。而且，对 CPU 的干扰很大，效率低。

  • 程序查询方式（I/O Polling）
    I/O 设备将自己的状态放到状态寄存器中，操作系统阶段性地主动查询状态寄存器中的特定状态，决定下一步的操作，也称为程序直接控制方式。

    整个 I/O 操作完全在 CPU 的控制之下，数据的传递是在 CPU 的寄存器与外设及其接口的数据缓冲寄存器之间（DBR），I/O 设备不直接访问内存。

    优点是简单、容易控制。

    缺点是，CPU 与外设是串行工作，CPU 完全在等待“外设完成”，效率低。

  • 中断驱动方式（I/O Interrupt）
    当某个 I/O 设备需要 CPU 干预时，就向 CPU 发出中断请求。如果 CPU 成功响应，CPU 就终止当前程序的执行，调出中断处理程序处理该中断。处理完成后，CPU 再返回原程序继续执行。

  • DMA 方式（Direct Memory Access）

    是磁盘等高速外设特有的 I/O 方式。

    该方式下，磁盘与主存直接进行数据交换。需要专门的 DMA 控制器。

    当外设准备好数据之后，想 DMA 控制器发送 DMA 请求信号，DMA 控制器再向 CPU 发起总线请求。CPU 让出总线后，有 DMA 控制器控制总线进行传输，过程中不需要 CPU 干涉。