# 计组亡魂

# 缩写汇总

# 第一章 - 计算机系统概述

# 1. 计算机发展的历史

计算机系统 = 硬件 + 软件

计算机硬件的发展：

第一代计算机：(使用电子管)，

Atanasoff Berry Computer (1937 - 1938) solved systems of linear equations. ✓ 可求解线性方程组

第二代计算机：(使用晶体管)，
第三代计算机：(使用较小规模的集成)，
第四代计算机：(使用较大规模的集成)，

VLSI

已经经历了 4 代，计算机的速度越来越快，并且体积变得越来越小。
发展趋势：更微型、多用途；更巨型、超高速

摩尔定律，集成电路上的晶体管数量每 18 月就会翻一翻，所以每 18 月计算机的处理效率就会提高一倍。

洛克定律，制造半导体的资本设备成本将每四年翻一番

# 计算机层次化结构

# 2. 云计算

云计算出现的契机：网络技术的发展、大型数据中心的兴起：冗余计算资源

云计算的优势：硬件成本、维护成本、管理成本大幅下降；服务弹性；资源利用率，云计算依赖于弹性概念，可以根据需要添加和删除资源

常见的云计算类型：计算即服务、软件即服务、平台即服务、基础设施即服务

# 3. 冯诺依曼模型

冯・诺依曼结构也称普林斯顿结构，是一种将程序指令存储器和数据存储器合并在一起的存储器结构。
程序的执行过程称为 “取指 - 译码 - 执行 “
主要特点有:
(1) 在 CPU 和主存之间有且仅有一个数据通路 (也被称为冯 - 诺依曼瓶颈)
(2) 由三部分硬件系统构成：中央处理单元 (CPU)、主存、输入 / 输出系统
(3) 可以执行指令序列；
(4) 数据以二进制表示；
(5) 指令由操作码和操作数组成；

# 4. 其他架构

# 哈佛架构

有两根总线，允许同时传送指令和数据，而且有数据和指令分开存储的存储器，数据和指令用不同的总线，

【没有划分总线类型】

# 系统总线模型

# 5. 现代计算机

# 6. 计算机性能指标

# 7.Excersice

C. 错误，数据存在地址里。指令通常包含操作码和地址码，地址码指向操作数的内存地址。

D.Arithmetic Operations and Logical Operations.

CPU 时间 = CPI * 指令总数 * 时钟周期 (s)

CPU_1 / CPU_2 = (2xn/1.5) / (1xn/1.2) = 1.6

# 第二章 - 计算机系统中的数据表示

# 1. 前缀乘数

大数

Kilo- (K)/Kibi-(Ki) = 1 thousand = 103 / 210 （千）
Mega- (M)/Mebi-(Mi) = 1 million = 106 / 220 （兆）
Giga- (G)/Gibi-(Gi) = 1 billion = 109 / 230 （吉）
Tera- (T) /Tebi-(Ti)= 1 trillion = 1012 / 240 （太）

小数

Milli- (m) = 1 thousandth = 10−3 （毫）
Micro- (μ) = 1 millionth = 10−6 （微）
Nano- (n) = 1 billionth = 10−9 （纳）
Pico- (p) = 1 trillionth = 10−12 （皮）

# 2. 进制转换

# 整数

# 小数

# 3. 计算机中的数字表示

# 3.1 整数和小数

# Signed magnitude

原码

原码表示允许零有两种表示：正零和负零

# One’s complement

1 的补码 反码

反码的实现比原码表示更简单，但还是存在零的两种表示： -0 和 + 0

# Two’s complement

计算机系统采用补码系统表示数值

2 的补码 补码

# 三码转换

# 三码总结

# 移码

# 布斯算法（乘法）

# 3.2 浮点数

# IEEE754 标准

# 单精度

尾数在小数点的左边有一个隐含的 1

IEEE-754 单精度浮点标准使用 8 位指数（偏置为 127）和 23 位尾数

【总长：1+8+23】32 位 4B

真实阶码 = 当前阶码 - 127

# 规格数

阶码为 2^(-126)

# 特殊数

# 0 的表示

0 的指数和尾数为全 0，但符号位可以是 1 或者 0

# 双精度

IEEE-754 双精度标准使用 11 位指数（偏置为 1023）和 52 位尾数

【总长：1+11+52】64 位 8B

# 3.3 小结

# 4. 编码

二进制编码十进制（BCD）Binary-coded decimal (BCD)

EBCDIC （扩展的 BCD）是最早广泛使用的支持大小写字母字符以及特殊字符（如标点符号和控制字符）的计算机代码之一

7 位 ASCII（美国信息交换标准编码）作为 6 位编码的替代品

当今的许多系统都采用 Unicode，这是一种 16 位编码系统，可以对世界上每种语言的字符进行编码。最低位的 Unicode 字符包括 ASCII 码

# 5. 数据查错和纠错

# 奇偶校验

一串二进制流，末尾加 1 / 0

1 的个数为奇数，奇校验

1 的个数为偶数，偶校验

# CRC

# 汉明码

# 6.Excersise

# 第三章 - 布尔代数和数字逻辑

# 通用门

# Excercise

# 第四章 - 一个简单的计算机模型

# 1.CPU 基本结构

基本作用：CPU 负责获取程序指令，解码获取的每条指令，并对正确的数据执行指示的操作序列。

# 数据通路 (Datapath)

# Register

Registers hold data that can be readily accessed by the CPU.

MARIE 中的参考如下

# ALU

The arithmetic-logic unit (ALU) carries out logical and arithmetic operations as directed by the control unit

# Bus

Two types of buses are commonly found in computer systems: point-topoint, and multipoint buses

Buses consist of data lines, control lines, and address lines.

# 控制单元（Control Unit）

监视，调度，控制数据通路中的数据传输。

# 实现

控制单元（Control Unit, CU）是计算机处理器的核心部件之一，负责生成控制信号以协调其他部件的操作。控制单元的实现方式主要有两种：组合逻辑控制和微程序控制。

# 组合逻辑控制（硬布线逻辑控制）

优点：

1. 速度快：由于是硬件直接实现，没有额外的解码过程，执行速度较快。
2. 结构简单：对于简单的指令集，组合逻辑控制可以实现较为直接的控制逻辑。

缺点：

1. 灵活性差：一旦设计完成，修改控制逻辑较为困难，不利于扩展。
2. 可维护性低：随着指令集的增加，控制逻辑变得复杂，难以维护。
3. 成本问题：对于复杂的指令集，所需的门电路数量增多，可能导致成本上升。

# 微程序控制

优点：

1. 灵活性高：通过改变微程序来实现不同的控制逻辑，方便修改和扩展。
2. 易于维护：微程序的修改和调试相对容易，有利于系统的长期维护。
3. 可读性好：微程序类似于程序设计，具有较好的可读性。

缺点：

1. 速度较慢：存在微指令的解码过程，可能导致执行速度较慢。
2. 硬件复杂性：需要额外的控制存储器和微指令寄存器等硬件支持。

# 2. 总线仲裁方法

# 总线构成

# 仲裁方式

菊链： 权限从最高优先级设备传递到最低优先级设备。

集中并行： 每个设备直接连接到一个仲裁电路。

使用自我检测的分布式： 设备决定哪一个在它们之间得到总线。

使用冲突检测的分布式：任何设备都可以尝试使用总线， 如果它的数据与另一个设备的数据冲突， 它会重试。

# 例题

# 3. 内存交叉寻址

# 4.MARIE

# 扩展指令集

# 5. 寄存器传输表示 / 语言

# RTL

# 取指

# eg.LOAD

# eg.SKIPCOND

# RTN

寄存器传输表示

# 6. 根据寄存器传输模式确定控制信号

# 7. 汇编

# 8.Real World

# CISC

Complex Instruction Set Computer 复杂指令集计算机 Intel 架构

# RISC

Reduced Instruction Set Computer 精简指令集计算机 MIPS、ARM

MIPS 的设计考虑了性能：它是一种加载 / 存储架构，这意味着只有加载和存储指令才能访问内存

# 9.Exercise

# 第五章 - 指令集架构

# 1. 计算模型

按照 CPU 中数据存储的方式，指令集所代表的计算模型可以分为：

・堆栈型架构 (stack architecture)

in a stack architecture, instructions and operands are implicitly taken from the stack.

・累加器型架构 (accumulator architecture)

In an accumulator architecture, one operand of a binary operation is implicitly in the accumulator.

Why？ One operand is in memory, creating lots of bus traffic

・通用寄存器型架构 (General-purpose register architecture, GPR)

Faster than accumulator architecture.

Efficient implementation for compilers.

Results in longer instructions.

# 2. 指令格式

# 字节序 Byte Ordering

endianness

# 前中后缀的表达转换

Stack architectures require us to think about arithmetic expressions a little differently。

平常：中缀 infix

堆栈：后缀 postfix RPN（reverse polish notation 逆波兰式）

中缀 => 后缀：先用中缀画出二叉树，注意连续减，不要变号，仔细读题，从左到右。

后缀转前缀：堆栈法

数字进栈，遇到操作符，弹出栈顶两元素，计算加括号再压入

# 3. 指令集的编码和扩展操作码

# 三地址

# 双地址 (要求至少一个 Reg)

# 单地址

# 栈指令

# 小结

# 扩展操作码

不需要操作数的操作，例如 HALT ，在使用固定长度指令时必然会浪费空间

一种恢复方法是使用扩展操作码

转义符 111- escape opcode

# 4. 内存寻址模式

・立即寻址 (Immediate Addressing) 数据是指令的一部分

・直接寻址 (Direct Addressing) 在指令中给出数据地址

​ 寻址空间：地址位数决定，12 位则为 2^12

​ ・寄存器直接寻址 (Register Direct Addressing) 数据位于寄存器中

・间接寻址 (Indirect Addressing) 给出指令中数据地址的地址

​ 寻址空间：字长决定，因为真正寻的是内存里存的

​ ・寄存器间接寻址 (Register Indirect Addressing) 使用寄存器存储数据地址的地址

・变址寻址 (Indexed Addressing) 使用寄存器作为偏移量，将其添加到操作数中的地址中

​ 寻址空间为 字长 和 地址 一个加法，直接 + 间接的

・基址寻址 (Based Addressing) 使用基址寄存器而非索引寄存器

・堆栈寻址 (Stack Addressing) 操作数在堆栈中

# 5. 指令流水线

# 理论加速比计算

# 例题

# 冲突产生与解决

・常见的流水线冒险可以分为三类：

–结构冒险（Structural hazard） 资源冲突

–数据冒险（Data hazard） 数据依赖

–控制冒险（Control hazard）

・解决流水线冒险的方式：

–数据旁路

–流水线阻塞

–分支预测

- 指令优化

# 6.Exercise

# 第六章 - 存储器

# 1. 存储器的类型

# ROM (Read-only memory)

–数据读取速度快、存储时间长

–只需要很少的电能用于维持数据

–通常指数据在主机断电后依然有效的存储器，并非完全 “只读”

–例子：BIOS，CD-ROM，闪存

# RAM (Random-access memory)

–可以对随机位置的数据进行读写

–需要通电才能保存数据

–SRAM & DRAM

# 2. 层次化存储结构

# 金字塔

# 优势

最大化利用局部原理：一旦访问到某字节，附近的元素很快也会被访问

局部特性的三种形式：时间局部性，空间局部性，顺序局部性

时间局部性 (temporal locality)：最近访问的数据在不远的将来很有可能会再次访问
空间局部性 (spatial locality)：即将访问的数据和最近访问的数据地址空间接近
顺序局部性 (sequential locality)：数据按顺序访问

# 局部性应用在实际程序中

高速缓存

# 根据实际访问过程计算 EAT 有效访问时间

# 数据访问过程

为了访问特定的数据， CPU 首先向其最近的内存（通常是缓存）发送请求。

如果数据不在缓存中，则查询主存。如果数据不在主存中，则请求转到磁盘。

一旦数据被定位，那么数据及其附近的一些数据元素就被提取到高速缓存中。

# 例题

并行：Parallel

# 3. 缓存以及缓存映射策略

# 高速缓存

高速缓存的目的是通过将最近使用的数据存储在靠近 CPU 的位置来加快访问速度，而不是将其存储在主存中；单个大缓存搜索需要更长的时间

CAM：content addressable memory

# 直接映射

# 全相联映射

# 组相连映射

相当于把多个块合成一个 set，就是把 set 变大了，结合了全相联和直接映射。

2-way 代表一个组有两个块

# 小结

# 4. 缓存的替换策略

替换策略通常源于局部性，尤其是时间局部性

# LRU（最近最少使用）

最近最少使用（LRU）算法追踪上次访问块的时间，并驱逐最长时间未使用的块。

# FIFO（先进先出）

无论最后一次使用是什么时候，缓存中最长的块会被替换

# 随机替换

随机选择一个块并用一个新块替换它，这回使得经常使用或者就要使用的块被替换，但它不会导致颠簸（Thrash）

# LFU

# RR（轮转）

# 5. 缓存的写策略

# 写策略发生

# 其他方案

1. 许多现代系统为数据和指令使用单独的缓存，即哈佛缓存，代价是变得复杂

2. 更大的缓存空间

3. 跟踪高速缓存

# 6. 缓存状态分析

# 7. 虚拟内存

# 虚拟内存的意义

1）（主存）程序的可寻址地址空间大于主存的实际容量

2）（硬盘）实际使用的内存空间大于主存的实际容量

虚拟内存的核心思想：将一部分数据存储在硬盘上，提高内存的存储能力。

存储在硬盘上的部分称为页面文件（page file）

# 地址转换

# 分页

0x1363->0x0553

# 分段

分页会受到内部碎片的影响，因为进程可能不需要页面中包含的整个地址范围。因此，可能有许多页面包含未使用的内存片段。

分段受到外部碎片的影响，当连续的内存块随着时间的推移分配和释放段而被分解时，就会发生这种情况

虚拟地址分为两个字段：段编号 + 段内偏移值

对应的物理地址为 基地址 + 偏移值

段编号 ===> 基地址，得到物理地址

# 查找缺失

发生页面故障，触发中断，中断程序将页面加载到内存中，更新页表。

# TLB

（translation look-aside buffer）转换后备缓冲器

一种特殊的关联缓存，用于存储虚拟页面到物理页面的映射

# EAT

# 内存管理

# 8.Exercise

直接映射：direct mapped

偏移：word fieleds

全相联映射：fully associative

# 地址转换

128M = 2^7*220 ==> addr have 27 bits

32K/2 = 2^4 * 2^10 ==> set have 14bits

# EAT 计算和访问顺序

d）如果页面不再存在于页表中，那么缓存的值就会变得陈旧

# 虚拟内存

# 计算机存储设计

【多级缓存 + TLB + 关联存储类型】

如果您是计算机组装者，试图使您的系统尽可能具有价格竞争力，您将为其内存层次结构选择以下特性和组织方式：【便宜 + 大容量】

• 选择更便宜的非关联性缓存（如直接映射缓存）。
• 为了降低成本，可能完全不包括第二级缓存。
• 可以设置一个非常小的 TLB（Translation Lookaside Buffer，转换后备缓冲器）。
• 使用成本较低的主存，但配备一个大容量硬盘以吸引购买者。

如果您是计算机购买者，希望从系统中获得最佳性能，您在其内存层次结构中应寻找以下特性：【关联缓存 + 二级缓存 + 省钱 + 性价比】

• 寻找具有两级缓存的机器，第一级是某种类型的关联性内存。
• 注意，更大的缓存并不总是意味着更好。在一定程度上，更多的缓存可以提高命中率，但超过某个点后，命中率的提高就不再显著（所以不要为不需要的东西支付）。
• 一个合适大小的 TLB 将有助于提高性能。
• 一个大型且快速的主存绝对是一个显著的优势。

# 第 7 章 - I/O 和存储系统

# 1. 阿姆达尔定律

系统的整体性能提升受到其最慢部分的限制。换句话说，如果系统中有一部分无法并行处理，即使其他部分的并行性能得到极大提升，整个系统的性能提升也会受到限制。

f 是由更快组件完成的工作比例；而 k 是更快组件的加速比

# 2.I/O 访问的方式

・有五种常见的 I/O 控制方法

–程序控制 I/O (Programmed I/O)

–中断驱动 I/O (Interrupt-driven I/O)

–内存映射 I/O (Memory-mapped I/O)

–直接内存访问 I/O (Direct Memory Access, DMA)

–通道 I/O (Channel I/O)

# 3. 磁盘结构和计算

# 磁盘结构

# 机械硬盘数据读写

# 硬盘访问时间与数据传输时间

Seek time + rotational delay = access time.

# 硬盘的缺陷

Low cost is the major advantage of hard disks.
But their limitations include:
◼ Very slow compared to main memory
✓ 与主内存相比非常慢
◼ Fragility
✓ 脆弱性
◼ Moving parts wear out
✓ 运动部件磨损

# 4. 持久化存储

固态硬盘（Solid State Drive, SSD）

# 5.RAID

RAID，即独立磁盘冗余阵列（Redundant Array of Independent Disks）

按照 RAID 中的数据组织方式进行划分：

• 容错能力指的是 RAID 系统能够容忍多少磁盘同时出现故障而数据不丢失。
• 访问速度是指数据读写的速度，其中读快写慢意味着读取操作可以快速完成，但写入操作可能较慢，特别是涉及到奇偶校验更新的情况。
• 有效存储比是指相对于总磁盘容量，实际可用于数据存储的空间比例。

备注：

1.RAID-0: 性能最高

2.RAID-5：避免奇偶校验驱动器的竞争，不将奇偶校验放在同一驱动器上，是应用最广泛的 RAID 系统

3.Dual Parity RAID：双重奇偶校验 RAID

# 6.Exercise

The hardest part of data storage may be in locating the data after it’s stored.
✓ 数据存储中最困难的部分可能是在数据存储后定位数据

# I/O 架构

# 容量、访问时间计算

容量 = 全部乘起来

access time = rotatioanl delay + seek time

为什么除以 2？

由于磁盘是均匀旋转的，平均情况下，目标扇区距离当前磁头位置的角度是磁盘周长的一半，即 180 度，所以除以 2。

# 第 8 章 - 系统软件

# 1. 环境保护

・多用户场景下需要对计算、存储等资源进行分配和隔离

・保护环境是提供资源、进程和数据的运行环境

–由硬件、（主机）操作系统或虚拟机监控程序进行保护

・实现受保护环 S 境的常见技术

–虚拟机（Virtual Machine，VM）

–子系统（Subsystem）

–逻辑分区（Logical Partitioning，LPAR）

•实现保护环境的技术的对比和实例分析

# 第 9 章 - 体系结构

# 1.RISC & CISC

# 2. 费林分类法

# 3. 并行体系结构

# 4. 多处理器体系结构