组成原理

• 1: 概述
• 1.1: 计算机系统层次结构
• 1.2: 计算机性能指标
• 2: 数据表示和计算
• 2.1: 整数的表示
• 2.2: 浮点数表示
• 2.3: 运算电路
• 2.4: 类型转换
• 3: 存储系统
• 3.1: 存储系统
• 3.2: 内存
• 3.3: 外存
• 3.4: Cache
• 3.5: 虚拟存储器
• 4: 指令系统
• 4.1: 指令格式和寻址方式
• 4.2: 数据对齐方式
• 4.3: CISC和RISC
• 4.4: 高级语言和机器码
• 5: 中央处理器
• 5.1: 功能和结构
• 5.2: 控制器
• 5.3: 异常与中断
• 5.4: 指令流水线
• 5.5: 多核处理器
• 6: 总线和输入输出系统
• 6.1: 总线
• 6.2: I/O 系统

1 - 概述

# 计算机系统概述

## 计算机系统层次结构

- 计算机系统的基本组成
- 计算机硬件的基本结构
- 计算机软件和硬件的关系
- 计算机系统的工作原理

## 计算机性能指标

1.1 - 计算机系统层次结构

计算机系统的基本组成

硬件系统和软件系统共同构成了一个完整的计算机系统。硬件指的是有形的物理设备，是计算机系统中实际物理装置的总称。软件指的是在硬件上运行的程序和相关的数据及文档。

硬件和软件关系：硬件是计算机的物理部分，它提供了运行软件所需的基础设施，而软件则是指令集，指导硬件如何工作以执行特定的任务。

计算机硬件

冯·诺依曼基本思想

冯·诺依曼提出的 “存储程序” 的思想奠定了当代计算机的基本结构，以此概念为基础的各类计算机通称为 冯·诺依曼机，其特点如下：

1. 采用 “存储程序” 的工作方式。
2. 计算机硬件系统由 运算器、存储器、控制器、输入设备和输出设备5大部件组成。
3. 指令和数据以同等地位存储在存储器中，形式上没有区别，但计算机应能区分它们。
4. 指令和数据均用二进制代码表示，指令包含操作码和地址码，操作码指出操作的类型，地址码指出操作数的地址。

计算机的功能部件

1. 运算器 (Arithmetic Logic Unit, ALU)
   • 功能：负责执行所有的算术运算（如加、减、乘、除）和逻辑运算（如AND、OR、NOT、比较等）。
   • 组件：包括运算部件（执行具体的数学和逻辑操作）和临时存储用的寄存器。
2. 存储器 (Memory)
   • 功能：存储数据和指令。主存储器（如RAM）临时存储正在运行的程序和数据，而辅助存储器（如硬盘、SSD）用于长期存储。
   • 种类：包括随机存取存储器（RAM）、只读存储器（ROM）、硬盘、SSD等。
3. 控制器 (Control Unit)
   • 功能：管理和协调计算机的各个部件，确保指令按正确的顺序执行，并控制数据流。
   • 组件：包括指令寄存器、程序计数器和一个解码器，它们共同参与指令的获取、解码和执行。
4. 输入设备 (Input Devices)
   • 功能：允许用户或其他系统将数据输入计算机。
   • 重要性：它们构成了用户与计算机系统之间的主要交互界面。
5. 输出设备 (Output Devices)
   • 功能：显示或输出计算机处理的结果。
   • 例子：显示器、打印机、扬声器、投影仪等。

计算机软件

系统软件和应用软件

1. 系统软件 (System Software)
   • 定义：系统软件是直接运行在硬件上的软件，为其他软件提供一个运行和执行的平台。
   • 功能：
     • 管理和控制计算机硬件，使其能够与应用软件进行交互。
     • 提供应用软件开发的基础服务和接口。
2. 应用软件（Application Software）
   • 定义：应用软件是构建在系统软件之上，为用户提供特定功能或执行特定任务的软件。
   • 功能：
     • 解决用户的具体问题或满足特定需求。
     • 提供与用户的直接交互界面。

三个级别的语言

1. 机器语言 (Machine Language):
   • 定义：这是计算机硬件直接理解和执行的语言，它是用二进制代码表示的（通常是0和1）。
   • 特点：
     • 与特定计算机架构紧密相关。
     • 非常低级：每条机器代码对应硬件的一个操作。
     • 对于人类来说，阅读和编写是困难的。
2. 汇编语言 (Assembly Language):
   • 定义：这是一种低级编程语言，它使用符号和助记符（而非二进制代码）来代表机器语言的指令。
   • 特点：
     • 与特定计算机架构紧密相关。
     • 比机器语言更容易理解和编写。
     • 需要一个汇编器来将汇编代码转换为机器代码。
3. 高级语言 (High-Level Language):
   • 定义：这是为了更方便地编写和理解计算机程序而设计的语言。它们与特定的计算机架构相对独立。
   • 特点：
     • 抽象度高，语法通常更接近自然语言或数学符号。
     • 可以在不同的硬件平台上运行，只需适当地编译或解释。
     • 需要一个编译器或解释器来将高级语言代码转换为机器代码（或执行）。

计算机系统的工作原理

从源程序到可执行程序

1. 预处理（Preprocessing）：预处理器会执行诸如宏替换、文件包含、条件编译等任务，仅限于某些语言，比如C和C++。
2. 编译（Compilation）：编译器将源代码或预处理后的源代码转换为中间代码或目标代码，标代码通常是特定平台的汇编语言代码或机器代码。
3. 汇编（Assembly）：汇编器将汇编语言代码转换为机器代码。
4. 链接（Linking）：链接器将一个或多个目标文件与所需的库文件链接在一起，生成一个可执行文件。这个步骤确保所有函数或方法的调用都能找到它们在内存中的正确位置。
5. 加载和执行（Execution）：当你运行可执行文件时，操作系统的加载器会将它加载到内存中。CPU开始按照程序的指令执行任务。

# 预处理
gcc -E hello.c -o hello.i
# 编译
gcc -c hello.c -o hello.o
# 汇编
gcc -S hello.c
# 链接
gcc hello.o -o hello
# 加载和执行
./hello

1.2 - 计算机性能指标

CPU指标

主频

主频是指计算机中时钟信号的频率，通常以赫兹（Hz）为单位表示。例如，一个3.0 GHz的CPU意味着它的时钟周期每秒钟震荡30亿次。

时钟周期

CPU时钟周期是CPU完成一个基本操作所需的时间，与主频是互为倒数的关系。例如，3.0 GHz的CPU的时钟周期是1/3.0亿 = 0.333纳秒。

指令执行指标

CPI

CPI 的全称是 Cycle Per Instruction，也称每指令周期，即一条指令所需要的平均时钟周期。

IPC

IPC 的全程是 Instruction Per Cycle，也称每周期指令，即每个时钟周期执行的平均指令数，是 CPI 的倒数。

IPS

IPS 的全程是 Instruction Per Second，也称每秒指令数，即每秒平均能够执行多少条指令。

MIPS

MIP 的全称是 Million Instructions Per Second，及每秒能够执行 多少个 百万的指令。

浮点运算指标

各种FLOPS

这些都是评估计算机性能的指标，尤其在浮点运算方面。它们分别代表每秒可以执行的浮点运算次数：

• MFLOPS: 百万次每秒
• GFLOPS: 十亿次每秒
• TFLOPS: 万亿次每秒
• PFLOPS: 千万亿次每秒
• EFLOPS: 百亿亿次每秒
• ZFLOPS: 万亿亿次每秒

计算机指标

字长

字长（Word Length）指的是计算机在内部一次操作中所能处理的二进制数字位数。例如，一个32位的CPU一次可以处理32位的数据。

数据通路带宽（Data Bus Width）

数据通路带宽是CPU和内存之间传输数据的宽度，通常以位为单位表示。比如，64位的数据总线意味着每个时钟周期内，可以传输64位的数据。

主存容量

主存储器能够存储信息的最大容量，通常用字节来衡量。

吞吐量

吞吐量（Throughput）表示在单位时间内，系统可以完成的任务数量。在计算机网络中，它可能表示数据的传输速率；在计算中，它可能表示每秒执行的操作数。

2 - 数据表示和计算

# 数据的表示和运算

## 数制和编码

- 进位计数制及其数据之间的相互转换
- 定点数的编码表示

## 运算方法和运算电路

- 基本运算部件
- 加/减运算
- 乘/除运算

## 整数的表示和运算

- 无符号整数
- 带符号整数

## 浮点数的表示和运算

- IEEE 754标准
- 浮点数的加/减运算

2.1 - 整数的表示

BCD码

BCD（Binary-Coded Decimal）码是一种二进制编码方法，用于表示十进制数字。每个十进制数字（0-9）都使用四位二进制数字表示。

BCD码的基本思路是单独表示每个十进制数字的二进制值，而不是像传统的二进制数系统那样对整个数字进行编码。例如，在传统的二进制编码中，数字"19"会表示为10011，但在BCD中，它被表示为两个独立的数字：“0001”（对应于1）和“1001”（对应于9），因此整个表示为“0001 1001”。

0 - 0000    1 - 0001    2 - 0010
3 - 0011    4 - 0100    5 - 0101
6 - 0110    7 - 0111    8 - 1000
9 - 1001

BCD编码在某些应用中是很有用的，特别是在需要与十进制界面进行交互的地方，如数字显示或某些早期的计算机系统。尽管它不如纯二进制编码效率高，但它简化了与十进制数据的转换过程。

整数的表示

原码

原码（Sign-Magnitude）是一种简单的方式来表示二进制中的有符号整数。在这种表示法中，数字的最高位（最左边的位）用于表示符号，其余的位表示数字的大小。通常，符号位为0表示正数，而1表示负数。

表示方法

原码的表示方法：

1. 正数的原码：最高位为0，其余位表示这个数的绝对值的二进制形式。
2. 负数的原码：最高位为1，其余位表示这个数的绝对值的二进制形式。
3. 零的原码：符号位可以是0（表示+0）或1（表示-0），但在实际应用中，通常只使用一个零，即符号位为0。

举例（以8位二进制数为例）：

• +5 的原码是：00000101
• -5 的原码是：10000101

原码的缺点

• 存在正零和负零的表示。
• 在进行算术运算时，正数和负数需要不同的处理，这使得硬件设计变得复杂。

由于上述的缺点，原码并不是计算机中最常用的表示法。在现代计算机中，补码是更常用的方式来表示有符号整数，因为它简化了算术运算的处理，并且没有+0和-0的冗余表示。

补码

补码（Two’s complement）是计算机科学中用于表示整数的一种方法，特别是在现代计算机的算术和逻辑操作中。使用补码可以使得加法、减法和负数的表示变得简单和统一。

表示方法

原码的表示方法：

1. 正数的原码：最高位为0，其余位表示这个数的绝对值的二进制形式。
2. 负数的原码：最高位为1，其余位表示这个数的绝对值的二进制形式。
3. 零的原码：符号位可以是0（表示+0）或1（表示-0），但在实际应用中，通常只使用一个零，即符号位为0。

以8位二进制数为例：

1. 对于正数，例如 +5，其二进制表示为 00000101，补码也是 00000101。
2. 对于负数，例如 -5，首先写出5的二进制表示：00000101。
   • 按位取反得到：11111010
   • 加1得到：11111011
   • 所以，-5的补码是 11111011。

补码的计算方式

以8位补码为例讲解一下补码是如何从二进制位与实际数字结合的：

例子：

• 10000001对应的值为 $-128 + 1 = -127$
• 10001001对应的值为 $-128 + 8 + 1 = -119$
• 01000001对应的值为 $64 + 1 = 65$

为什么要使用补码

补码的设计使得负数的加法变得简单。当使用补码表示时，可以直接将两个数相加，即使其中一个数是负数，而不需要进行任何特殊处理。这简化了计算机硬件的设计。

2.2 - 浮点数表示

实数的二进制表示

浮点数在计算机中的存储遵循IEEE标准，但在这里为了方便理解IEEE标准，这里首先阐明一般实数在计算机中是如何存储的。

在这里实数分为两个部分存储：整数部分 和 小数部分，两个部分在逻辑上用 · 隔开。

比如对于以下浮点数的二进制表示：

$$d_m d_{m-1} \cdots d_1 d_0 \cdot d_{-1} d_{-2} \cdots d_{-n}$$

其中每一位对应的数值如下表所示：

上述二进制表示对应的数值为

$$b = \sum_{i=-n}^{m} {2^{i} \times b_{i}}$$

其中$b_i = 0$ 或 $b_i = 1$，表示第i为是0还是1。

举例说明如何使用上述表示法计算实数：

• $101.11_{2}$ 对应的数值为 $1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 + 1 \times 2^{-1} + 1 \times 2^{-2} = 5.75$
• $1011.1_{2}$ 对应的数值为 $8 + 0 + 2 + 1 + \frac{1}{2} = 11.5$

IEEE Floating-Point

上述浮点数存储方式的缺点在于如果要表示比较大的数，就需要比较多的二进制位数，比如对于$5 \times 2^{100}$ 就需要103位。IEEE表示就解决了这个问题，在IEEE表示中，浮点数 $V$ 被表示为 $V = (-1)^{s} \times M \times 2^{E}$，其中 $s, M, E$ 的含义如下：

• $s$ 为符号位
• $M$ 为乘法因子
• $E$ 为浮点数的指数部分

IEEE 754标准是定义浮点数表示和算术的国际标准，它定义了多种不同精度的浮点数格式，但最常见的是单精度 single precesion（32位）和双精度 double precesion（64位），浮点数分为 s, exp, frac 三个部分存储：

• $1$ 位的 $s$ 与上述计算公式中的符号位 $s$ 相同，位于浮点数二进制表示的最高位，标志了浮点数的正负，如果 $s = 1$ 的话 $V$ 是负数，如果 $s = 0$ 的话 $V$ 为正数
• $k$ 位的 $exp = e_{k-1} \cdots e_1 e_0$ 用于计算指数部分 $E$，使用原码表示，其中 $E = exp - Bias$，其中 $Bias = 2^{k-1} - 1$
  • 对于单精度浮点数，$k = 8$，$Bias = 2^{8-1} - 1 = 127$，$1 \le exp \le 254$，$-126 \le M \le 127$
  • 对于双精度浮点数，$k = 11$，$Bias = 2^{11-1} - 1 = 1023$, $1 \le exp \le 1022$，$-1022 \le M \le 1023$
• $n$ 位的 $frac = 0 \cdot f_{n-1} \cdots f_1 f_0$ 用于计算因子 $M$，其中 $M = 1 + frac$，$frac$ 表示的小数计算方式见实数的二进制表示
  • 对于单精度浮点数，$n = 23$，$M$ 的最大值为 $2 - 2^{-23}$，$M$ 最小值为 $1$
  • 对于双精度浮点数，$n = 52$，$M$ 的最大值为 $2 - 2^{-52}$，$M$ 最小值为 $1$

视频讲解

2.3 - 运算电路

加法运算电路

最基本的加法单元是 半加器（Half Adder）。它有两个输入，一个是加数，一个是被加数，并有两个输出，一个是和，一个是进位。

全加器（Full Adder）是半加器的扩展，它加上了前一位的进位作为第三个输入，并有两个输出，一个是和，一个是进位。全加器可以级联，用于多位加法。

串联全加器：构成加法器

为了进行多位数的加法，全加器可以串联起来形成一个串行进位加法器（ripple carry adder）。在这种安排中，每个全加器的进位输出连接到下一个全加器的进位输入。这样，一个 n 位的加法器可以通过串联 n 个全加器来实现。

减法运算电路

二进制中的减法可以通过加法来实现。减去一个数等同于加上它的补码。为了得到一个数的补码，你首先得到它的反码（每一位都取反）然后再加1。所以，一个简单的减法器可以通过使用加法器并对第二个输入（被减数）进行补码转换来构建。

乘法运算电路

二进制乘法与十进制乘法的手工计算方式类似：

       1011   (this is binary for decimal 11)
     × 1110   (this is binary for decimal 14)
     ======
       0000   (this is 1011 × 0)
      1011    (this is 1011 × 1, shifted one position to the left)
     1011     (this is 1011 × 1, shifted two positions to the left)
  + 1011      (this is 1011 × 1, shifted three positions to the left)
  =========
   10011010   (this is binary for decimal 154)

在计算机中实现乘法指令可以通过如下几种方式模拟以上过程：

1. 软件算法

如果没有专有硬件支持，可以通过一系列加法和位移操作来实现乘法。编译器将乘法运算转换为一个循环代码段，在循环代码段中通过比较、加法和移位等指令实现乘法运算。

// 如何使用加法和位移来实现两个整数的乘法（了解即可）
unsigned int multiply(unsigned int a, unsigned int b) {
    unsigned int result = 0;  // 结果初始化为0
    while (b > 0) {           // 当第二个操作数大于0时继续循环
        if (b & 1) {          // 检查b的最低位是否为1
            result += a;      // 如果是，将a加到结果上
        }
        a <<= 1;              // 将a左移一位，相当于a乘以2
        b >>= 1;              // 将b右移一位，去掉已经处理过的最低位
    }
    return result;            // 返回计算的乘积
}

2. 顺序乘法器

通过硬件的方式实现以上的软件算法，这是最基础的实现方式，类似于我们在纸上做乘法那样，一步一步进行。

3. 阵列乘法器

阵列乘法器（Array Multiplier）是一种用于执行乘法运算的硬件电路，它通过布置一系列全加器和半加器在一个二维网格或阵列中来实现，它能够并行处理多个位的乘法和累加，可以在一个或多个时钟周期内完成乘法操作。

除法运算电路

二进制除法在计算机中的实现与我们在十进制中所执行的传统长除法类似。与二进制乘法一样，我们将使用基本的二进制操作，如移位和减法。

   商（Quotient）
    0110
   =======
10 | 1101
-      10   (这是从 `110` 中减去的，因为它大于或等于 10)
   --------
        100 
    -   10   (这是从 `100` 中减去的，因为它大于或等于 10)
   --------
         10
     -   10   (这是从 `10` 中减去的，因为它大于或等于 10)
   --------
          0   (这是余数 Remainder)

2.4 - 类型转换

有符号整数和无符号整数

这里需要了解有符号整数（int）和无符号整数（unsigned）这两个类型：

• int：使用补码来存储数据。
• unsigned：所有位，包括最高位，都用于表示数值，表示非负数。

以8位有符号整数和无符号整数说明一下

• 8 位有符号整数
  • 表示的范围为 -128 ~ 127
  • 最大数为127，对应的二进制为0111 1111
  • 最小数为-128，对应的二进制为1000 0000
• 8 位无符号整数
  • 表示的范围为 0 ~ 255
  • 最大数为255，对应的二进制为1111 1111
  • 最小数为0，对应的二进制为0000 0000

当int和unsigned进行类型转化时，位模式不变，可以理解成计算机存储单元中的二进制表示没有变化，只是从程序层面阐述该二进制数据的方式变了。

当我们将8位的有符号整数-128转化为无符号整数时，其值变成了128。

整形和浮点数

• 从 float 到 int: 将浮点数转换为整数时，小数部分会被舍去。例如，将 3.9 转换为整数将得到 3。
• 从 int 到 float: 将整数转换为浮点数时，结果会是一个等值的浮点数。例如，将整数 4 转换为浮点数将得到 4.0。

不同长度的类型转换

• 较小的整数类型被转换为较大的整数类型时，高位会被自动填充为0
• 较大的整数类型被转换为较小的整数类型时，高位会被自动截断

以short和int的类型转化为例说明：

/* 将short转为int */
short s = 0x1234;
int i = s;
// 高16位被填充为0
// i = 0x00001234

/* 将int转为short */
int i = 0x12345678;
short s = i;
// 高16位被截断
// s = 0x5678

隐式和显式类型转换

1. 隐式类型转换

你在一个表达式中混合使用 int 和 float 时，C语言会自动进行类型转换以使得表达式可以正确计算。通常情况下，低精度类型会被提升到高精度类型，即 int 会被转换为 float。

2. 显式类型转换

也可以使用类型转换运算符显式地转换一个类型为另一个类型。

/* 隐式类型转换 */
int i = 5;
float f = 2.5;
float result = i + f;  // i 被隐式转换为5.0然后进行计算

/* 显式类型转换 */
int i = 5;
float f = 3.2;
int result = (int)f + i; // f 被显式转换为3，然后与i相加

3 - 存储系统

# 存储器层次结构

## 存储器分类

## 层次化存储器的基本结构

## 半导体随机存取存储器

- SRAM存储器
- DRAM存储器
- Flash存储器

## 主存储器

- DRAM芯片和内存条
- 多模块存储器
- 主存和CPU之间的连接

## 外部存储器

- 磁盘存储器
- 固态硬盘

## 高速缓冲存储器

- cache的基本原理
- cache和主存之间的映射方式
- cache中主存块的替换算法
- cache写策略

## 虚拟存储器

- 基本概念
- 页式虚拟存储器
- 段式虚拟存储器
- 段页式虚拟存储器

3.1 - 存储系统

存储系统的层次结构

1. 寄存器（Registers）:
   • 寄存器是位于处理器内部的最快速存储单元。
   • 它们提供极快的数据访问速度，但其容量非常有限。
2. 一级缓存（L1 Cache）:
   • L1缓存位于处理器内部，比寄存器稍大，但比其他缓存慢。
   • 它通常分为数据缓存（用于存储数据）和指令缓存（用于存储指令）。
3. 二级缓存（L2 Cache）:
   • L2缓存比L1缓存大，并且位于处理器和主内存之间。
   • 它的速度比L1慢，但比主内存快。
4. 三级缓存（L3 Cache）:
   • 在某些系统中，还有L3缓存，这是一种更大但速度更慢的缓存。
   • 它位于L2缓存和主内存之间，旨在进一步减少对主内存的访问。
5. 主内存（RAM）:
   • 就是我们常说的内存，比缓存慢，但比硬盘快得多，并且容量比缓存大。
   • 主内存用于存储正在运行的程序和当前使用的数据。
6. 辅助存储（如硬盘驱动器或固态驱动器）:
   • 辅助存储设备提供大量的永久存储。
   • 与RAM相比，这些设备访问速度较慢，但能够存储更多的数据，并且在断电时不会丢失数据。
   • 硬盘驱动器（HDD）和固态驱动器（SSD）是常见的辅助存储设备。

半导体随机存储器

半导体随机存储器的英文为 Semiconductor Random-Access Memory （ RAM ）。

首先说一下这个名词中的几个部分：

• 半导体：这种存储器使用半导体材料（如硅）制成。晶体管是构成半导体存储器的基本组成部分。
• 随机：随机的意思是随机访问，意味着可以以几乎恒定的时间访问存储器中的任意位置，它与其他存储技术（如磁盘或磁带）不同，后者需要按顺序访问数据。

随机存储器主要分为SRAM和DRAM，注意两者的区别：

半导体随机存储器是 易失性 的，这意味着一旦断电，其中存储的信息就会丢失。SRAM 主要用于实现cache，DRAM 主要用于实现主存。

Flash存储

Flash存储器是一种 非易失性 的电子存储设备，它利用半导体技术来存储数据。通常用于长期数据存储，如USB闪存驱动器、固态硬盘（SSD）和移动设备的内部存储。它在读取速度上比RAM慢，但优于传统的硬盘驱动器（HDD）。

Flash存储器使用电子方式来擦写和重新编程存储单元。这意味着可以通过电信号快速擦除和写入数据。数据存储在小型存储单元中，每个单元由浮动门晶体管组成。这些晶体管可以保持其充电状态，从而代表不同的数据位。

Flash存储主要分为 NAND Flash 和 NOR Flash 这两种类型。

ROM

ROM（Read-Only Memory）是一种 非易失性 存储设备，主要用于永久性地存储数据。

ROM主要用于读取操作。虽然早期的ROM在制造过程中就已经被编程，不能修改，但现代的ROM（如EPROM和Flash存储器）可以被重新编程。

ROM常用于存储固件，这是一种软件程序，直接嵌入在硬件设备中，用于控制设备的基本操作。例如，BIOS（基本输入输出系统）通常存储在ROM中。

注意一下ROM和RAM的对比如下：

ROM 类型：

• EPROM：可以通过紫外线照射来擦除数据，然后重新写入数据。写入数据和擦除数据都较为繁琐，且需要物理操作。常用作电脑的 BIOS 芯片，支持随机存取。
• CDROM： 一种光盘存储设备，数据在生产时一次性写入，不能被修改（只能读取）。

3.2 - 内存

DRAM 芯片

刷新方式

多模块存储器

利用多个结构完全相同的存储模块的并行工作来提高存储器的吞吐率：

• 单体多字存储器
• 多体交叉存储器
  • 高位交叉存储器
  • 低位交叉存储器

单体多字存储器

按同一地址码并行地访问各自对应单元，每一个单元为一个字，每字 m 位。可以同时选中存储器的 n 个单元，可以将带宽提高 n 倍。

仅做简单了解，这里不详细说明，考试重点在多体交叉存储器。

多体交叉存储器

在多体交叉存储器的实现方案中，有两种编码方式：高位交叉编制和低位交叉编址。其中低位交叉编址可以实现多个存储器的并行访问，高位交叉编址只能增大存储器的空间。

高位交叉编址

在高位交叉编址中，地址分为两个部分，高位用于存储存储器的下标，低位用于存储地址在该存储器内的偏移。

连续的数据在同一个存储器内编址，当一个存储器满了，接下来的数据在下一个存储器中编址。 如下图所示，若计算机地址空间大小为 4n，存储器 M0 中存储地址 0 到 n-1 的数据，存储器 M0 中存储地址 n 到 2n-1 的数据，以此类推。

所以在高位交叉编址中，相邻地址的数据存储在一个存储体中。

在这种地址组织形式下，多个存储器芯片 串行工作，只需要一个地址存储器即可，不必为每个芯片都配一个地址存储器（根据程序的局部性原理） 。

这种串行工作方式是无法提高 CPU 的性能的。 如上图所示，所有存储器都共享一个地址寄存器（AR，Address Register）和数据寄存器（DR，Data Regsiter）。

低位交叉编址

在低位交叉编址中，地址分为两个部分，低位用于存储存储器的下标，高位用于存储地址在该存储器内的偏移。

连续的数据交叉地在不同的存储器之间编址。 如下图所示，若计算机地址空间大小为 4n，地址为 0~3 的数据分别存储在 M0、M1、M2 和 M3 上，地址为 4~7 的数据也分别存储在 M0、M1、M2 和 M3 上，以此类推。

所以在低位交叉编址中，相邻地址的数据存储在不同存储体中。

在这种地址组织形式下，多个存储芯片是 并行工作 的，且相邻地址处在不同的存储体中，因此就可以实现存储体的并行访问； 为了并行访问，每一个存储体均需要一个地址寄存器；

使用 低位交叉编制 这种编址方式，计算机可以实现对于多个存储器的并行访问。 如上图所示，每个存储器都单独地配有一个地址寄存器（AR，Address Register）和数据寄存器（DR，Data Regsiter）。

并行访问存储器可以采用 流水线 的方式，与 指令流水线 概念类似，在并行存储器的流水线中，对于每一个存储器中存储单元的读取可以被分为三个阶段：

• $P_1$：送地址和命令（送地址至存储器的 AR 中）
• $P_2$：存储器读取数据（读取数据到 DR 中，该周期也称作 存储周期）
• $P_3$：传送数据（从 DR 中读取数据并传输到内存的物理地址中）

假设 CPU 的时钟周期为 $t$，$P_1$ 和 $P_3$ 的耗时为一个时钟周期即 $t$。$P_2$ 的耗时为四个时钟周期即 $4 \times t$，那么对于上图所示的 四体交叉存储器，读取 八个字长的数据 的流水线如下所示：

主存容量的扩展

虽然单体存储芯片的容量和字长在不断扩大，但是在实际应用的过程中，任然会出现芯片的容量或者字长满足不了应用的情况，因此就有了存储扩展的需求；

假设存储芯片的字长为 $N$，存储字数为 $M$，则存储芯片的容量为 $M \times N$。

常见的存储扩展包括三种：位扩展、字扩展、字位扩展：

• 位扩展：扩展字长
• 字扩展：扩展字数
• 字位扩展：同时扩展字长和字数

位扩展

如上图所示，用 $16K \times 8\ bit$ 的存储芯片用来构建 $16K \times 32\ bit$ 的存储器。

需要的芯片数量为 $(16K \times 32) / (16K \times 8) = 4$。

由于是位扩展，所以四个芯片的片选信号要连接在一起，并处在常有效的状况；（片选信号是读写操作的开关）。

由于原存储器的 $8$ 位的，扩展之后变为 $32$ 位，这 $32$ 位的位线同 CPU 的 $32$ 位数据线相连接，所有存储芯片并行工作，贡献 $32$ 位数据中的不同 $8$ 位；

图中，4 个存储器共同构成 $64KB = 2^{16}B$ 的存储空间，所以地址总线为 $16$ 位，即从 $A_{0}$ 到 $A_{15}$。 但是由于 $16KB$ 的存储芯片只需要 $14$ 根地址线，因此只需要 $14$ 位地址线与存储线相连，即从 $A_{2}$ 到 $A_{15}$。 这里 $A_{0}$ 到 $A_{1}$ 不被使用，因为这 低两位地址线 相当于被用来扩展字长。

字扩展

如上图所示，用 $16K \times 8\ bit$ 的存储芯片用来构建 $64K \times 8\ bit$ 的存储器。

需要的芯片数量为 $(64K \times 8) / (16K \times 8) = 4$。

地址总线的位数为 $16$， 但是由于 $16KB$ 的存储芯片只需要 $14$ 根地址线，因此只需要 $14$ 位地址线与存储线相连，即从 $A_{0}$ 到 $A_{13}$。 高两位地址线 $A_{14}$ 到 $A_{15}$ 与片选译码器相连，由此产生片选信号。

字位扩展

如上图所示，用 $16K \times 8\ bit$ 的存储芯片用来构建 $32K \times 16\ bit$ 的存储器。

需要的芯片数量为 $(32K \times 16) / (16K \times 8) = 4$。

地址总线的位数为 $16$，地址线 $A_{1} \sim A_{14}$ 与存储器相连，$A_{0}$ 不使用，被用来扩展字长。$A_{15}$ 用来产生片选信号。

视频讲解

3.3 - 外存

磁盘存储器

存储区域

1. Heads（磁头）：磁头是位于硬盘驱动器的读/写臂上的设备，用于读取和写入磁盘上的数据。每个盘片（硬盘通常包含多个盘片，每个盘片都有两个表面）上都有一个磁头，因此每个磁头都可以读取或写入盘片上的数据。磁头通过移动到不同的磁道（track）来寻找并访问数据。
2. Track（磁道）：磁道是磁盘上的一个同心圆环。
3. Cylinders（柱面）：柱面是硬盘上的一个数据存储区域，由相同半径位置上的多个盘片上的磁道组成。换句话说，它是所有盘片上相同半径位置的磁道的集合。
4. Sectors（扇区）：扇区是磁盘上的最小数据存储单元。磁盘通常被划分成许多扇区，每个扇区可以存储一定数量的数据。扇区的大小通常是512字节或4KB。操作系统和磁盘控制器使用扇区作为数据的最小单元，以读取和写入数据。

性能指标

• 平均存取时间 = 寻道时间（磁头移动到目的磁道的时间） + 旋转延迟时间（磁头定位到要读取扇区的时间） + 传输时间（传输数据所花费的时间），由于寻道和找扇区的距离远近不一，所以寻道时间和旋转延迟时间通常取平均值。
• 数据传输率：磁盘单位时间向主机传送数据的字节数。假设磁盘转速为 $r$ 传/秒，每条磁道容量为 $N$ 字节，则数据传输率为 $D_{r} = rN$

RAID

RAID全称为独立磁盘冗余阵列（Redundant Arrar of Independent Disks） 由于磁盘存储介质数据的可靠性容易受到环境影响，而发生数据错误的代价非常大，因此需要考虑存储的容灾与恢复。

RAID将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割交叉存储、并行访问，具有更好的存储性能、可靠性和安全性。

固态硬盘SSD

• 无机械部件：SSD没有旋转盘片、磁头或机械臂等移动部件，它使用闪存存储芯片来存储数据。这意味着它不会受到机械故障的威胁，具有更高的耐用性。
• 更快的读写速度：SSD的读写速度远远超过传统的机械硬盘，因为数据可以立即访问，无需等待盘片旋转和磁头寻道。这使得计算机启动更快，应用程序响应更迅速。
• 低访问时间：由于没有机械延迟，SSD的访问时间极低，通常在微秒级别。这有助于加快文件读取和数据检索。
• 长寿命：虽然每个存储单元有写入次数的限制，但现代SSD使用错误检查和纠正（ECC）技术，以延长其寿命，并且通常拥有较长的保修期。
• 无碎片化：SSD不会发生碎片化问题，因此无需定期进行碎片整理操作。

3.4 - Cache

cache 原理

cache 工作原理

缓存（cache）是计算机系统中的一种用于加速数据访问的技术，其原理是在高速存储介质中暂时存储常用数据，以便更快地满足后续的访问请求。

缓存对于程序执行的加速主要来自于 计算机程序 的 时间局部性 和 空间局部性：

1. 时间局部性：
   • 如果一个数据项被访问，那么它在不久的将来很可能再次被访问。
   • 这种特性常见于循环结构和频繁访问的变量，例如循环中的计数器或者经常读取的配置值。
   • 在缓存设计中，利用时间局部性意味着一旦数据被加载到缓存中，它应该在那里保留一段时间，因为很可能很快会再次需要它。
2. 空间局部性：
   • 如果一个数据项被访问，那么存储在其附近的数据项也很可能在不久的将来被访问。
   • 这种特性在数组遍历或结构体访问时尤为明显，因为这些数据元素通常在内存中是连续存储的。
   • 利用空间局部性的缓存设计会在访问一个数据项时，同时把它附近的数据也加载到缓存中，因为这些数据很可能在接下来的操作中被用到。

cache 概念

• 缓存块（cache 块）：cache 中的一块存储空间
• 主存块：主存中的一块存储空闲，主存块的大小一般与 cache 块一致
• 块内偏移：某一个地址在块内的偏移，找到对应的块后，通过块内偏移找到改地址的具体位置
• 块大小：用于判断块内偏移的位数，比如$1024 = 2^{10}$，所以 1KB 的块对应的块内偏移位数为 10

缓存块

什么是缓存块？

Cache block（缓存块），也被称为缓存行（cache line），是计算机系统中用于存储的最小数据单元，它是缓存中的一个固定大小的数据块。每个缓存块包含一定数量的字节或字（通常是 2 的幂次方个字节），并用于存储从主存（或更低级别的缓存）中加载的数据。

cache block 的目的是为了方便对于主存（main memory）数据的缓存，主存数据块的大小与缓存块大小一致，这样就可以将 cache block 和 main memory block 对应起来。

缓存块的大小？

Cache block 的大小在不同计算机体系结构中可以有所不同，通常以字节（bytes）或字（words）为单位来表示。典型的缓存块大小可以是 32 字节、64 字节、128 字节等。较大的缓存块可以容纳更多的数据，提高了数据的局部性，但在某些情况下，较小的缓存块可能更适合，特别是对于小规模的数据访问。

cache block 的大小在题目中一般会给你。

cache 和主存映射方式

1. 直接映射

在直接映射（directed mapped）缓存中，每个主存块只能映射到缓存中的一个特定缓存块。这意味着每个主存块只有一个缓存块可以存储它。

例子

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，对于直接映射的cache：

• 缓存被分为 256KB / 64B = 4096 个缓存块。
• 内存中的数据可以直接映射到这 4096 个位置中的其中一个，比如第 10000 个主存块映射到 10000 % 4096 = 1808个缓存块。
• 当一个新的数据块需要被加载时，它会替换掉当前映射到该位置的数据块，不管缓存的其他位置是否为空。

2. 全相联映射

在全相联缓存（full associative）中，主存中的任何块可以映射到缓存中的任何缓存块。这意味着主存块的地址没有限制，可以映射到任何可用的缓存块。

例子

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，对于全相联映射的cache：

• 缓存被分为 256KB / 64B = 4096 个缓存块。
• 全相联缓存中的每个主存块可以放置在任何缓存块中，即第 0 到第 4095 个缓存块都可以存储该主存块。
• 当缓存满时，基于某种替换策略替换掉 4096 个缓存块中的某一个。

3. 组相联映射

组相联缓存（set associative 或 group associative）是直接映射缓存和全相联缓存之间的一种折中方案。它将缓存块分为多个组，每个组包含多个缓存块。主存块可以映射到组中的一个缓存块。

N 路组相联

当我们说一个缓存是 N路组相连 的，意味着缓存被分为多个组，每个组有N个缓存块（N路）。这样，当一个内存地址被映射到一个特定的组时，它可以放在该组的任何一个缓冲块（一路）上。如果一个组是满的，新的数据会根据某种替换策略来替换组中的一个缓存块。

例子

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，我们希望有 4 路组相联的组织。

• 这意味着缓存被分为 256KB / 64B = 4096 个缓存块。
• 因为是 4 路组相联，所以这些块被进一步组织为 4096 / 4 = 1024 个组。
• 每个组包含 4 个位置（即 4 路），任何内存地址映射到这个组的时候，可以放在这四个位置中的任何一个。
• 比如第 10000 个主存块位于第 10000 % 1024 = 784个组，可能对应组内的任何一个缓存块。

cache 地址结构

当给定一个物理地址时，需要判断该地址对应的主存块可能被哪些 cache 块所缓存，并且检查所有可能的 cache 块的 tag 字段以判断是否被缓存，所以 cache 地址的结构从逻辑上可以分为如下部分：

• 标记（tag）：判断当前地址是否命中对应的 cache 块
• cache 块匹配字段：通过该字段判断主存块可能被哪些 cache 块缓存
  • 对于直接映射为块号（cache block number）：位数为$log_2{(\text{cache 块数量})}$
  • 对于全相联映射为空，因为每一个主存块都可能被任何一个 cache 块所缓存
  • 对于组相联映射为组号（group number）：位数为$log_2{(\text{组数})}$
• 块内地址（block offset）：物理地址在主存块内的偏移

总结三种不同映射方式的地址结构如下：

cache 存储结构

cache 的存储结构可以理解为一张表：

其中字段的含义与页表近似：

• 有效位：该 cache 行是否存储有缓存数据，位数为1位。
• 标记：根据物理地址中的 tag 字段与该字段匹配，以判断是否命中，位数按照cache地址结构进行计算。
• 修改位：标记该 cache 是否修改过，与写策略相关。
  • 如果采用全写法，则无需设置修改位。
  • 如果采用写回法，设置1位修改位。
• 访问位：用于记录访问信息，服务于块替换算法，其位数取决于替换算法。
  • 如果采用LRU替换算法，则修改位的位数为$log_2{(\text{主存快对应的缓存块数量})}$。
• 数据块：缓存的数据块，为物理内存中数据块的一个副本。

cache 中的块替换算法

块替换算法适用于全相联映射和组相联映射，因为一个主存块可能被多个cache块中的某一个 所缓存，查询和替换过程如下：

• 根据 cache 块匹配字段找到所有可能缓存 该物理地址对应主存块 的 cache 块
• 遍历所有可能缓存该主存块的cache块
  • 如果cache块的有效位为0，则替换该cache块，将主存块加载进来，并将有效位设置为1，停止遍历
  • 如果cache块的tag字段与物理地址的tag字段相匹配，则表示该次地址查询命中cache，停止遍历
• 如果遍历完所有cache块都无法满足如上条件时，则根据块替换算法选择一个cache块进行替换

当我们访问一个物理地址时未命中时，需要将对应的主存块加载到 cache 中，如果这个该主存块对应的 cache 块都满了的话，就需要替换掉其中的某个 cache 块，替换算法包含如下种类：

• LRU
• FIFO
• 随机算法
• LFU

这里的具体思想与操作系统中的页面置换算法一致，请参考页面置换算法

cache 写策略

cache 的写策略代表当我们对某个物理地址上的数据进行写入时，应该如何写入对应的存储单元，以及如何协调cache和主存之间的数据一致性，写策略按照地址查询是否命中cache可以分为四种方式。

如果某次地址查询命中 cache，可以使用如下策略：

• write-through（全写法）：每次写操作都会同时更新缓存和主存。
• write-back（回写法）：当数据被修改时，它首先被缓存在 cache 中，只有当 cache 块被替换时才写入对应的主存块。

如果没有命中 cache，也有如下策略：

• write-allocate（写分配）：物理地址对应主存块被加载到 cache 块中（先执行一次对应主存块的读操作），然后更新 cache 块
• not-write-allocate（非写分配）：不加载主存块至 cache 中，直接更新主存块，只有当执行读操作时才将主存块加载进入cache块

命中和未命中的方法常常通过如下方式一起使用：

• 全写法（write-through）和非写分配法（not-write-allocate）通常会一起使用，适用于那些写操作不频繁或者写操作不太可能访问同一数据的情况。
• 回写法（write-back）和写分配法（write-allocate）通常会一起使用，适用于那些写操作频繁的情况。

不同映射方式对比

视频讲解

3.5 - 虚拟存储器

虚拟存储器

虚拟存储器是一种计算机内存管理技术，它在物理内存和磁盘存储之间创建了一个抽象的、扩展的内存空间，以提供更大的可用内存容量。

虚拟内存和物理内存

1. 虚拟内存（Virtual Memory）：
   • 虚拟内存是一种计算机内存管理技术，它将计算机的物理内存扩展到磁盘上，从而提供了更大的可用内存空间。
   • 每个进程拥有自己的虚拟地址空间，这个地址空间通常比物理内存大得多。
   • 进程使用虚拟地址来访问内存中的数据和指令，而不需要了解物理内存的详细情况。
2. 物理内存（Physical Memory）：
   • 物理内存是计算机上实际存在的内存硬件，包括 RAM（随机存储器）芯片和其他存储设备。
   • 物理内存是计算机硬件用来存储正在运行的进程和操作系统内核的数据和指令的地方。
   • 物理地址是实际的内存地址，对应于计算机硬件上的存储器芯片中的位置。

页式虚拟存储器

地址翻译机构