一、计算机系统概论

1.1 计算机系统简介

1.1.1 计算机系统的组成

计算机由硬件与软件两部分组成
软件分为系统软件与应用软件两大类
- 系统软件：管理整个计算机系统
- 应用软件：根据任务需要编制的程序

1.1.2 计算机系统的层次结构

层次	说明
应用层	用户直接使用的软件
高级语言机器$M_4$	高级语言编译成汇编语言
汇编语言机器$M_3$	汇编语言汇编成机器语言
操作系统机器$M_2$	用机器语言解释操作系统
机器语言机器$M_1$	用微程序解释机器指令
微程序机器$M_0$	用硬件直接执行微指令

虚拟机器：$M_4$、$M_3$、$M_2$；实际机器：$M_1$；微程序机器：$M_0$

机器语言、汇编语言、高级语言的区别
- 机器语言是一种用二进制代码表示的计算机语言，机器可以直接执行用机器语言编写的程序。
- 汇编语言是一种用助记符表示的与机器语言一一对应的语言，用汇编语言编写的程序需经过汇编后才能执行。
- 高级语言是一种接近人类自然语言的与计算机结构无关的语言，用高级语言编写的程序要经过解释和编译才能执行。

1.2 计算机的基本组成

1.2.1 冯·诺依曼计算机的特点

核心特征：存储程序的工作方式
计算机由五大功能部件组成：运算器、控制器、存储器、输入设备、输出设备
- 运算器：完成算术运算和逻辑运算
- 控制器：控制程序的执行
- 存储器：存放指令和数据
- 输入输出设备：与外部环境交换信息
指令和数据用二进制代码表示
- 原因：
  1. 二进制编码的运算规则简单
  2. 制造2个稳定状态的物理器件较容易
  3. 便于使用逻辑电路实现算术运算
工作原理：存储程序、程序控制
- 存储程序程序控制方式：事先编写程序，再由计算机把这些程序存储起来，然后连续地、快速地执行程序，从而完成各种运算过程。
- 根据存储程序原理，计算机具有五大功能：数据传送、数据存储、数据处理、操作控制、操作判断
基本工作方式：控制流驱动方式
指令和数据以同等地位存放在存储器中，可按地址寻访
指令由操作码和地址码组成
以运算器为中心

1.2.2 计算机的硬件框图

改进：以存储器为核心
冯·诺依曼计算机结构VS以存储器为中心的体系结构
（实线：数据传输；虚线：指令传输）
冯·诺依曼体系结构VS哈弗体系结构

1.3 计算机硬件的主要技术指标

1.3.1 字长

机器字长：计算机一次能处理的二进制数的位数，通常与CPU的寄存器位数有关。等于ALU位数，直接影响数据总线和存储字长的位数
指令字长：计算机指令中二进制代码的总位数。
存储字长：存储器的一个存储单元中能存放的二进制数的位数。
三者可以相当也可以不等，视不同机器而定。

1.3.2 存储容量

存储容量：计算机存储器中能存放的二进制数的位数
存储容量 = 主存+辅存 = 存储单元数×存储字长（/8（字节））

1.3.3 存储器带宽

存储器带宽：存储器的数据传输速率
存储器带宽=存储字数/存储周期（字/秒）
存储字长（字长）：一个存储单元中存放的二进制数的位数
字节：8位二进制数

1.3.4 运算速度

CPI（Cycle Per Instruction）：每条指令的平均时钟周期数
- $CPI = CPU时钟周期数 \div 指令数（加权平均）$
- 注意平均指令周期（时间）与CPI（时钟周期数）的区别
MIPS（Million Instructions Per Second）：每秒执行的百万条指令数
- $MIPS = \dfrac{指令条数N}{执行时间t×10^6} = \dfrac{主频f}{CPI\times 10^6}$
主频f：CPU时钟频率；时钟周期T：CPU时钟周期
执行时间t：执行一组指令所需的时间
- $t = \dfrac{指令条数N\times CPI}{主频f}$ = $\dfrac{指令条数N}{MIPS\times 10^6}$
每秒浮点运算次数：FLOPS（Floating Point Operations Per Second）

二、计算机发展史（了解）

三、系统总线

3.1 总线的基本概念

3.1.1 总线的作用

总线：连接各个部件的信息传输线，各个部件共享的传输介质
提供信息交换时所需的数据、地址、时序和控制信息
提供一个共同遵循的协议或标准

3.2 总线的分类（按连接部件）

片内总线：CPU内部的总线
系统总线：CPU与其他部件之间的总线
- 根据传输的信息划分：数据总线、地址总线、控制总线
- 数据总线：双向，位数与机器字长相关
- 地址总线：单向，位数与存储单元个数相关
- 控制总线：双向，传输控制信息
通信总线：连接计算机与其它系统的总线

3.3 总线的特性与性能指标

3.3.1 总线的特性

机械特性（物理特性）：总线的物理连接方式（根数、插口形状）
电气特性：传输方向、有效电平范围
功能特性：根据传输的信息划分（数据、地址、控制）
时间特性：同步、异步、功能复用

3.3.2 总线的性能指标

总线宽度：数据总线的位数
总线带宽：单位时间内传输的数据量（Bps：字节/秒）
总线时钟频率：总线的工作频率
总线复用
信号线数量
总线控制方式

3.4 总线结构

3.4.1 总线事务

总线事务：从请求总线到完成总线使用的操作序列
典型事务：存储器R/W，I/O-R/W，中断请求，DMA请求
典型事务操作：请求、仲裁、地址传输、数据传输、总线释放

3.4.2 单总线结构

结构简单、使用方便、易扩充
统一编址、简化指令系统、存储空间减少
共享总线、分时使用、通讯速度慢
高速设备的高速性能得不到发挥

3.4.3 双总线结构1：增加CPU-主存的存储总线

存储总线有效的降低了系统总线的负载，提高了并行性能
需要增加专门的I/O指令，存储空间增加
结构简单、易扩充

3.4.4 双总线结构2：增加I/O总线

3.4.5 三总线结构

高速与低速传输活动分离
- I/O设备与主存之间的通信和CPU活动分离
- 高速设备靠近CPU，低速设备远离CPU
不同层次的总线之间采用桥接方式连接和缓冲

3.4.6 总线结构与设备性能之间的关系

最大存储容量：单总线系统中，内存要为外部设备预留地址
指令系统：单总线结构无需专门的I/O指令
吞吐率：三总线系统比单总线系统大得多

3.4.7 采用南北桥结构的奔腾机系统总线结构

南北桥结构

北桥靠近CPU，连接高速设备：主存、图形设备、CPU
南桥连接低速设备：I/O设备、硬盘、USB、网卡
南北桥之间通过PCI总线连接

3.5 总线控制

3.5.1 信息传送方式

串行传送
- 位信息从低到高在一条传输线上逐位以脉冲方式传送
- 成本低、速度慢、传输距离远
并行传送
- 每位一条数据线，同时传送多位信息
- 速度快、传输距离短
分时传送
- 采用总线复用技术，地址数据共用
- 分时使用总线

3.5.2 总线判优控制（总线仲裁）

总线仲裁：多个设备同时请求总线时，由总线控制器判定哪个设备优先使用总线
根据总线控制部件的位置，仲裁方式分为两类：集中式、分布式

集中式仲裁	链式查询方式	计数器定时查询方式	独立请求方式
控制线	3根：总线状态BS，总线请求BR，总线授权BG	$2+log_2n$根：总线状态BS，总线请求BR，地址计数线（$log_2n$根）	$2n$根：总线请求BR（$n$根），总线授权BG（$n$根）
响应速度	慢	慢	快
优先级	固定	可适当变化	可灵活调整
故障敏感性	敏感	不敏感	不敏感
扩展性	容易	困难	容易

3.5.3 总线定时

总线定时主要解决通信双方如何获知传输开始和传输结束，通信双方如何配合的问题
同步方式：用公共时钟信号对传输过程的每一步进行控制，适合快速设备
- 无应答方式
- 事件时刻由总线时钟信号决定，采用公共时钟，数据传输率高
- 木桶效应：必须按照最慢的设备定时
异步方式：用应答信号对传输过程进行控制。又分为非互锁、半互锁和全互锁；适合慢速设备
- 不互锁
  - 主模块：发出请求一段时间，认为副模块收到请求，撤销请求并通信
- 半互锁
  - 主模块：发出请求，收到副模块应答后撤销请求并通信
  - 副模块：收到请求后应答一段时间，认为主模块收到应答，撤销应答并通信
- 全互锁
  - 主模块：发出请求，收到副模块应答后撤销请求并通信
  - 副模块：收到请求后应答，收到主模块撤销请求后撤销应答并通信
半同步方式：结合同步方式和异步方式的特点，在同步时钟的控制下进行采样和应答
分离式通信

3.5.4 总线通讯控制/总线传输过程

总线申请（总线仲裁）：部件提出请求，总线控制器确定将下一个总线使用权分配给谁
地址阶段（总线寻址）：主设备通过总线发出从部件的存储器地址或I/O端口地址及相关命令，启动从设备
数据传输阶段
结束阶段：主部件撤消总线请求等有关信息，总线控制器释放总线

3.6 例题

假定某总线的时钟周期为50ns,每次总线传输需要1个时钟周期，总线宽度为32位，存储器的存储周期为300ns,求同步方式下从该存储器中读一个字时总线的数据传输率为多少?
- 同步方式下按顺序进行以下步骤：
  1. 送地址和读命令：1个总线周期 = 50ns
  2. 存储器读数据：300ns
  3. 总线传输数据：1个总线周期 = 50ns
- 一个字的总时间：$50+300+50=400ns$
- 数据传输率：$32bit/8/400ns=10MBps$
系统总线传输的信息类型为：数据、地址、控制信号
- 握手应答信号是通信总线传输的信息类型！
提高同步总线数据传输速率的方法
1. 增加总线宽度
2. 增加总线时钟频率
3. 支持突发传输
- 地址/数据线复用不能提高数据传输速率
主存通过总线类型识别地址和数据

四、存储器

4.1 概述

4.1.1 存储器的分类

按存储介质分类
- 半导体存储器（易失性：断电即失）
  - TTL：高速
  - MOS：高集成度、低功耗、低成本、应用广泛
- 磁表面存储器：磁头+磁载体
- 磁芯存储器：体积大、功耗大、工艺复杂
- 激光存储器：CD、DVD
按存取方式分类
- 物理地址和存取时间无关（随机访问）
  - 随机存储器（RAM）可读可写
    - SRAM（静态RAM）：速度快、价格高、集成度低
    - DRAM（动态RAM）：速度慢、价格低、集成度高
  - 只读存储器（ROM）
    - M：Masked（掩模）；P：Programmable（可编程）；E：Erasable（可擦写）；EE：Electrically-Erasable（电可擦写）
- 物理地址和存取时间有关（串行访问）
  - 顺序存储器：磁带
  - 直接存储器：磁盘
按在计算机中的作用分类
- $
  存储器\begin{cases}
  主存\begin{cases}
  随机存储器（RAM）\begin{cases}
  SRAM \\
  DRAM
  \end{cases} \\
  只读存储器（ROM）\begin{cases}
  MROM\\
  PROM\\
  EPROM\\
  EEPROM
  \end{cases}
  \end{cases}\\
  闪速存储器（Flash Memory）\\
  辅助存储器\begin{cases}
  磁盘\\
  磁带\\
  光盘
  \end{cases}\\
  缓存（Cache）
  \end{cases}
  $

4.1.2 存储器的层次结构

存储系统的层次结构（自上到下从内到外）

CPU寄存器
缓存Cache（SRAM）（内存）
主存储器（DRAM） （内存）
磁盘 （辅助存储器）
磁带、光盘 （辅助存储器）

存储器的主要特性（自上到下）

速度：快 -> 慢
- 存储时间、存取周期、存储带宽
容量：小 -> 大
价格：贵 -> 便宜

存储器的层次结构的作用

缓存-主存层次：解决CPU与主存之间速度不匹配的问题
- 透明：对系统程序员和应用程序员屏蔽
- 主存储器、实地址、物理地址
主存-辅存层次：解决存储系统的容量问题
- 不透明：系统程序员可以对此层次进行修改
- 虚拟存储器、虚地址、逻辑地址

存储系统为什么采用分层体系结构？
- 采用层次化存储体系的目的包括两方面：其一是解决快速的CPU和慢速的主存之间的速度差异；其二是解决主存容量不够大的问题。存储系统的分级结构由Cache、主存和辅助存储器三级结构构成。其理论基础是时间局部性原理和空间局部性原理，Cache—主存存储层次解决了主存速度不快的问题；而主存-辅存存储层次解决了主存容量不足的问题。

4.2 主存储器

4.2.1 概述

主存的基本组成
- 存储体：存储数据
- MAR：存储器地址寄存器，保存要访问的存储单元地址
  - 经过译码器进行译码，选定存储单元
- MDR：存储器数据寄存器，存储要写入或读出的数据
  - 通过读写电路和控制电路控制数据的读写
主存中存储单位地址分配方式
- 子地址+字节地址
- 大端存储（大尾存储）：0x12345678存储为12 34 56 78
- 小端存储（小尾存储）：0x12345678存储为78 56 34 12
- （小格中顺序正常，大格中顺序颠倒）小端存储例：x86
- n根地址线可按字节寻址$2^n$个字节（按字寻址按比例计算）
主存中的数据组织和边界对齐

寄巧：每种数据类型的数据存储在存储器中的起始地址必须是该数据所占字节数的整数倍

主存储器的技术指标
1. 字长：一个存储单元存放的二进制数的位数
2. 存储容量：存储器中能存放的二进制数的总位数
- 存储容量=存储单元数×存储字长（位）/8（字节）
1. 存储速度：由存取周期表示
- 存取周期：连续2次存取所需的最小时间间隔
- 分为读周期和写周期
1. 存储器带宽=存储字数/存储周期（字/秒）=(存储字数*存储字长)/8/存储周期（字节/秒）

4.2.2 半导体存储芯片

基本结构与芯片容量
- 例：地址线10位；数据线8位
- 存储单元：$2^{10}$个；存储字长：8位；芯片容量：$2^{10}\times 8=1K*8位=8Kbit=1KB$
- 片选线CS/CE：选择芯片Chip Select/Enable
- 读写控制线WE/OE：读写控制Write/Output Enable
译码驱动方式
- 单译码结构：$n$位地址输入，经$n$位译码器译码，指向$2^n$个存储单元
- 双译码结构：将存储芯片阵列，分为行译码和列译码，指向$2^{2n}$个存储单元
  - 地址译码器：将二进制地址译码为存储单元的物理地址（类比3-8线译码器）
  - Y向驱动器：将地址译码后的列地址送到存储矩阵的列选择线

4.2.3 随机存取存储器（RAM）

SRAM（静态RAM）
1. 存储原理：触发器
  - 中心与GND相连的T1, T2：存储数据
  - 中心与VCC相连的T3, T4：补充电荷
  - 外侧的T5-T8：T5、T6行选，T7、T8列选
2. SRAM芯片（以Intel 2114为例）
  - 地址线：$A_{9-0}$，地址数=$2^{10}$个
  - 数据线：$I/O_{3-0}$，数据位数=$4$位
  - 芯片存储容量=$2^{10}\times 4bit=1K\times 4bit$
3. SRAM的不足
  - 晶体管数量多，集成度低，功耗大
DRAM（动态RAM）
1. 分单管式和三管式，存储原理：电容
2. DRAM的优点
- 存储密度高，集成度高，功耗低
- 速度慢，需要刷新
1. DRAM刷新
  1. 刷新：DRAM存储单元中的电荷会逐渐泄漏，需要定期刷新补充
  2. 刷新周期：存储器两次完整刷新之间的时间间隔
  3. 刷新方式：集中式、分散式、异步式（假设刷新周期为2ms）
    - 集中式
      - 一个刷新间隔（2ms）：|-----R/W/维持-----|—集中刷新n行—|
      - 在数据丢失之前集中刷新所有行
      - 保持存储单体的高速特性，存在死区（死时间）
      - 死区=存取周期*刷新行数，死时间率=死区/刷新间隔
      - 场景：实时性要求不高
    - 分散式
      - 一个刷新间隔（小于2ms）：|R/W|刷新第0行|R/W|刷新第1行|…|R/W|刷新第n行|
      - 存储周期=读写+刷新：各刷新周期分散安排在存取周期中
      - 过度刷新，通常刷新间隔远小于所需最大刷新间隔，芯片性能下降
      - 不存在死区
    - 异步式
      - 一个刷新间隔（2ms）：|R/W|R/W|…|R/W|刷新第0行|R/W|R/W|…|R/W|刷新第n行|
      - 每行每隔一定时间/多次读写后刷新一次，（平均）分散在一个刷新间隔的任意部分
      - 存在死区，但可以将刷新安排在指令译码阶段
SRAM与DRAM的比较

	SRAM	DRAM
存储原理	触发器	电容
集成度	低	高
刷新	不需要	需要
存储成本（功耗）	高	低
速度	快（无需重写）	慢（需重写）
破坏性读出	非	是
送行列地址	同时	分2次
主要用途	Cache高速缓存	主存

4.2.4 只读存储器（ROM）

MROM：Masked（掩模）
PROM：Programmable（可编程）
EPROM：Erasable P（可擦写可编程）
EEPROM：Electrically-Erasable P（电可擦写可编程）
Flash Memory：闪速存储器

4.2.5 主存与CPU的连接方式（不考察）

$MREQ(存储器请求)\Rightarrow CS(片选线)$
$A_{17-0}(地址线)\Rightarrow A$：存储单元数=$2^{18-10} K$个
$R/W(读写控制)\Rightarrow WE(写使能)$
$D_{31-0}(数据线)\Rightarrow D$：数据位数=$32$位

4.2.6 存储器容量扩展（不考察）

位扩展（DBUS）：增加存储字长
- 方法：
  - MREQ、A同时连接$n$个芯片
  - R/W同时连接所有RAM芯片
  - D位数扩展到原来的$n$倍，按顺序分配给每个芯片
- 特点：
  - 从每个芯片内部相同的地址单元中读取数据，同时读写
  - 位扩展后的存储容量=单元数×（字长×片数）
字扩展（ABUS）：增加存储单元数
- 方法：
  - D同时连接$n$个芯片
  - R/W同时连接所有RAM芯片
  - MREQ连接到3-8译码器的OE
  - A位数增加$log_2n$，原来的部分与每一片连接，增加的部分分配给3-8译码器
  - 3-8译码器的输出连接到$n$个芯片的CS（片选）
- 特点：
  - 从单个芯片（组）中的地址单元中读取数据
  - 字扩展后的存储容量=（单元数×片数）×字长
字位综合扩展：同时增加存储单元数和存储字长
- 方法：
  - R/W同时连接所有RAM芯片组
  - D位数扩展到原来的$n$倍，连接每个芯片组
  - MREQ连接到3-8译码器的OE
  - A位数增加$log_2n$，原来的部分与每一片连接，增加的部分分配给3-8译码器
  - 3-8译码器的输出连接到$n$个芯片的CS（片选）
例：存储器容量扩展
- 需求：
  - 0x0000到3FFF为ROM存储区域
  - 0x4000到0x5FFF为保留地址区域
  - 0x6000到0xFFFF为RAM地址区域
  - RAM的控制信号为CS#和WE#，CPU地址线A15~A0，数据线D7~D0，控制信号有读写控制R/W#和访存请求MREQ#
- 材料：16K×8 ROM 4K×8 RAM
- 注意：
  - 译码器一位信号对应两片芯片时，高位地址（$A_{12}$）参与片选
  - 译码器两位信号对应一片芯片时，信号取或传入片选
- 不同区域选择芯片类型：
  - 系统程序区域：ROM
  - 保留区域：无需选择
  - 用户程序区域：RAM

4.2.7 优化主存性能的方法

采用高速器件：SDRAM（同步DRAM）
增加Cache：采用层级结构 Cache-主存（CDRAM）
双端口存储器

具有两个独立的读写控制线
地址不冲突时，可并行读写

增加字长、每个存储周期存取多个字：单体多字存储器（位扩展）

多个单字长存储器并行工作
共用一个地址寄存器
单存储周期内访问多个存储字

将主存分为多个模块，并行存取：多体并行存储器

高位交叉、顺序编址（顺序方式）（字扩展）
低位交叉、轮流编址（交叉方式）
- 流水线式存储：
  - 总线传输周期$\tau$，存储周期$T$，交叉模数$m$
  - 流水线方式存储的条件：$T=m\tau$
  - 连续传输n个字的时间：$T+(n-1)\tau$
- 存储体数量：不小于$\dfrac{存储周期}{总线传输周期}$

	高位交叉	低位交叉
相邻数据地址	同一存储体	不同存储体
地址寄存器	一个	每个存储体一个
局部性原理	高位片选，多模块串行	低位片选，多模块并行
性能	无提升	提升
故障隔离	方便	-
连续读取$n$个字的时间	$nT$	$T+(n-1)\tau$

4.3 高速缓存存储器Cache

4.3.1 概述

Cache解决的问题

避免CPU“空等”状态
弥补CPU与主存的速度差异

程序访问的局部性原理

时间局部性：刚访问过的数据很可能马上再次访问
空间局部性：刚访问过的数据附近的数据很可能马上访问
优化手段：调度算法（时间局部性）；预读优化（空间局部性）

Cache的工作原理

主存地址：n位=m位主存块号+b位块内地址（字地址）
Cache地址：c位Cache块号+b位块内地址（c << m）
按块存储，块大小相同
命中（HIT）：Cache中有所需数据
缺失（MISS）：Cache中无所需数据，需要从主存中读取
标记记录某缓存块对应的主存块号

命中率、访问时间、访问效率

记$N$为访问次数，$N_c$为命中次数，$N_m$为缺失次数（访问主存次数）；$t_c$为Cache存取时间，$t_m$为主存存取时间
命中率：$h=\dfrac{N_c}{N}$ / 缺失率：$1-h$
平均访问时间：$t_{avg}=ht_c+(1-h)t_m$
访问效率：$E=\dfrac{t_c}{t_{avg}}$

关键技术

数据查找、地址映射、替换策略、写入策略

Cache的读操作

Cache的写操作

写穿法（Write Through）：写Cache同时写主存
- 优点：维持了主存和Cache的数据一致性
- 缺点：写主存次数多，在连续多次更新同一数据时效率低
写回法（Write Back）：只写Cache，标记为脏，被替换时才写回主存
- 优点：减少了写主存次数，提高了效率
- 缺点：需要额外的标记位和判断，增加了Cache复杂度

Cache的改进

增加Cache级数（CPU片内、片外）
统一Cache（指令、数据共用）和分立Cache（指令、数据分开）

4.3.2 Cache-主存地址映射

直接映射

根据Cache块数对主存块号取模，只能存放在对应模数的位置
主存地址n位=t位标记位+c位Cache块号+b位块内地址（t+c=m）

全相联映射（主存容量大考虑采用）

任意主存块可以存放在任意Cache块中
主存地址n位=m位标记位+b位块内地址

组相联映射

组间直接映射，组内全相联映射，先分组
组数$2^q$，组内Cache块数$2^r$，$q+r=c$
主存地址n位=(t+r)位标记位+q(c-r)位组号+b位块内地址

	直接映射	全相联映射	组相联映射
冲突	最容易	最不容易	中等
Cache利用率	低	高	中等
淘汰算法	无	需要	需要

4.3.3 Cache的替换策略

先进先出（FIFO）

优点：易实现、开销小
缺点：未考虑局部性原理，被替换的数据再次被访问

近期最少使用（Least Recently Used，LRU）

优点：减少了被替换的数据再次被访问的概率，提高了命中率

随机法

4.4 存储器的校验

概述

存储器校验的意义：解决编码在时间、空间上传输可靠性问题；减少基于软件检错的代价
码距：两个合法码之间的不同位数。
- 码距越大，抗干扰能力、纠错能力越强，数据冗余越大，编码效率越低
检错和纠错：检错位数=码距//2，纠错位数=（码距-1）//2

奇偶校验（以偶校验为例）

待传输数据：$D_1D_2D_3D_4D_5D_6D_7D_8$
校验位：$P=D_1\oplus D_2\oplus D_3\oplus D_4\oplus D_5\oplus D_6\oplus D_7\oplus D_8$（奇校验取反）
发送与接收的数据：$D_1D_2D_3D_4D_5D_6D_7D_8P$（末尾加校验码）
检错码：$G=D_1\oplus D_2\oplus D_3\oplus D_4\oplus D_5\oplus D_6\oplus D_7\oplus D_8\oplus P$
- $G=0$，无错；$G=1$，有错
码距：2
检1位错，纠0位错

汉明校验

待传输数据：$D_n…D_3D_2D_1$
增加校验位$P$数量：$k$，$2^k\geq n+k+1$ （$n=4$时，$k=3$）
校验位$P_i$处于$2^{i-1}$位置，即传输数据：$H_{7-1}=D_4D_3D_2P_3D_1P_2P_1$
校验位$P_i$为位置下标二进制第$i$位为1的数据（除自己外）的异或和。
- $P_1= H_3\oplus H_5\oplus H_7=D_1\oplus D_2\oplus D_4$
- $P_2= H_3\oplus H_6\oplus H_7=D_1\oplus D_3\oplus D_4$
- $P_3= H_5\oplus H_6\oplus H_7=D_2\oplus D_3\oplus D_4$
检错码$G_i$为位置下标二进制第$i$位为1的数据的异或和。
- $G_1=H_1\oplus H_3\oplus H_5\oplus H_7=P_1\oplus D_1\oplus D_2\oplus D_4$
- $G_2=H_2\oplus H_3\oplus H_6\oplus H_7=P_2\oplus D_1\oplus D_3\oplus D_4$
- $G_3=H_4\oplus H_5\oplus H_6\oplus H_7=P_3\oplus D_2\oplus D_3\oplus D_4$
每一组数据都是一次偶校验
检错码的排列$G_3G_2G_1$所示的二进制数表示出错的位置
码距：3
检1位错，纠1位错
实现检2位错
- 开头增加一个总偶校验位$P_4=H_1\oplus H_2\oplus H_3\oplus H_4\oplus H_5\oplus H_6\oplus H_7$
- 检错码：$G_4=P_4\oplus H_1\oplus H_2\oplus H_3\oplus H_4\oplus H_5\oplus H_6\oplus H_7$
优点
- 编码效率高：数据增加一倍，校验位增加1位
- 可纠正1位错，检错2位错

CRC循环冗余校验

待传输数据：$1100$
约定一个$r+1$位二进制数$1011$（r=3）
将待传输数据左移$r$位，得到$1100|000$
做模二除法，做减法时做异或，余数首位为1时商上1
$1100000\div1011=1110\cdots 010$其中余数$010$是校验位
$1100|000$和余数$010$相加，得到传输数据$D=1100|010$
接收方将接收到的数据$D$除以约定的数$1011$，余数为0则无错

4.5 辅助存储器/外存储器

4.5.1 概述

磁表面存储器、硬盘存储器、光盘存储器
特点；容量大、速度慢、价格低、长期存储、非破坏性读出
原理：电磁变换

4.5.2 磁表面存储器的技术指标

记录密度

道密度$D_t(TPI)$
位密度$D_b(BPI)$
面密度$D_s=D_t\times D_b$

$圆柱面数N_c=(外径R-内径r)\times F_t$
$磁道长度l=2\pi r(内径)$
$存储容量C=l\times D_b\times N_c\times 盘面数$
$寻址时间/定位时间T_a=寻道时间t_s+等待时间t_w$
数据传输率$D_r$：单位时间传输的数据量
误码率：$\dfrac{错误位数}{总位数}$，通常用CRC校验纠正

4.5.3 硬磁盘存储器

类型

固定磁头/移动磁头
可换盘/固定盘

结构

$主机\Leftrightarrow 磁盘控制器\Leftrightarrow 磁盘驱动器\Leftrightarrow 磁盘盘片$

磁盘控制器：主机与磁盘驱动器之间的接口

功能：数据传输、数据校验、磁盘调度、磁盘格式化

4.5.4 软盘存储器

	硬盘	软盘
速度	快	慢
磁头	固定/活动、浮动	固定、接触盘片
盘片	固定、盘组、大部分不可换	可换盘片
价格	高	低
工作环境	苛刻

4.5.5 光盘存储器

采用光存储技术，利用激光读写
第一代：非磁性介质、不可擦写
第二代：磁性介质、可擦写
只读型/只写一次型：热作用
可擦写型：热磁效应

五、输入输出系统

5.1 概述

5.1.1* 输入输出系统的发展概况

早期阶段
- 分散连接
- CPU与I/O设备串行工作
- 程序查询方式
接口模块和DMA阶段
- 总线连接
- CPU与I/O设备并行工作
- 中断方式/直接存储器访问（DMA）
具有通道结构的阶段
具有I/O处理机的阶段

5.1.2* 输入输出系统的组成

I/O软件
- I/O指令：CPU指令的部分。操作码|命令码|设备码
  - 操作码：I/O指令的标志，指出该指令是I/O指令
  - 命令码：指出I/O操作的类型：输入、输出、状态测试、控制
  - 设备码：指出I/O设备的地址（端口号）
- 通道指令
  - 通道：具有特殊功能的处理器IOP
  - 指出要传输的字节数、数据地址、操作命令
I/O硬件
- 接口方式：设备、I/O接口：设备通过接口连接到总线，和主机进行数据交换
- 通道方式：设备、设备控制器、通道

5.1.3 I/O设备与主机的联系方式

外设分类
- 按功能：输入设备、输出设备
- 按速度：低速设备、中速设备、高速设备
- 按作用：人机交互设备、外存储器设备、通信设备
I/O设备的编址方式
- 统一编址方式：将I/O设备看作是内存地址的一部分，共用地址空间，指令集相对简单
- 不统一编址方式：内存之外专设I/O设备地址空间，有专门的I/O指令集
设备寻址：通过设备选择电路
传送方式：串行、并行
联络方式/外围设备定时方式
- 立即响应方式（极慢的设备）
- 异步工作采用应答信号联络（慢速和中速设备）
- 同步工作采用同步时标联络（高速设备）
I/O设备和主机的连接方式
- 辐射式（分散连接）：每台设备都配有独立的控制电路和信号线
- 总线式：便于增删设备

5.2 I/O端口

设置I/O端口的原因
- 外部设备工作的异步性：外部设备工作的时钟和时序与微处理器不同
- 速度差异：外部设备的速度远远低于微处理器
- 信号线与数据格式不同
- 便于外设发展
I/O端口的功能
- 实现数据缓冲
- 执行CPU的命令返回外设状态
- 设备选择
- 数据格式、信号的转换
- 中断管理
I/O接口的组成
- 基本电路：寄存器及逻辑控制
- 端口地址译码电路
- 供选电路：可选器件

5.3 I/O控制方式 / 信息交换方式总览

程序查询方式
- $启动设备\Rightarrow 反复查询设备状态直至设备准备好\Rightarrow 传输单个数据\Rightarrow 结束设备$
- 信息交换完全由CPU执行程序实现
- 串行工作、反复查询、系统效率低
- 用于早期计算机系统
程序中断方式
- $CPU发起指令\Rightarrow 设备准备数据+CPU处理其他进程\Rightarrow 设备准备好数据，向CPU发出中断请求\Rightarrow CPU响应中断$
- 主动告知避免反复查询
- 仍需CPU占用
- 一次中断传输数据少，CPU开销大
直接存储器存取（DMA）方式
- 适用于成组数据传输
- 传输阶段DMAC从CPU接管总线，直接在内存及外设之间进行，节约了中断开销
- 需要更多硬件
通道方式
- 通道：具有特殊功能的处理器IOP，独立于CPU，分担I/O处理，可实现外设的统一管理和DMA操作
- 通道执行通道程序来完成CPU指定的I/O任务，通道程序是由一系列通道指令组成的

5.4 程序中断方式

中断概念
- 中断：CPU暂时中止现行程序的执行，转去执行为某个随机事件服务的中断处理子程序，处理完后自动恢复原程序的执行
- 作用：实现CPU与I/O设备的并行工作、故障处理等
中断的分类
- $
  中断\begin{cases}
  内中断（异常）：来自CPU内部\begin{cases}
  软件中断\\
  异常\begin{cases}
  故障Fault\\
  陷阱Trap\\
  终止Abort
  \end{cases}
  \end{cases} \\
  外中断（强迫中断）：来自CPU外部\begin{cases}
  不可屏蔽中断NMI：由系统内部硬件引发的中断\\
  可屏蔽中断INTR：由外设通过中断请求线向处理器申请
  \end{cases}
  \end{cases}
  $
中断系统基本功能
1. 中断请求的保持和清除：硬件实现
2. 中断仲裁：多个中断请求同时到达时，确定优先级
3. 中断源识别：获取中断号（识别中断源）
4. 中断处理
5. 中断控制
- 中断触发方式：边沿触发、电平触发
- 中断排队方式：优先级高先服务
单级中断和多级中断
- 单级中断：所有中断同级，离CPU近的优先，处理中断时不响应其他中断
- 多级中断：优先级高的中断可打断优先级低的中断，中断嵌套
优先级划分一般规律
- 硬件中断最高，程序错误中断其次
- NMI>INTR
- DMA>I/O
- 高速设备>低速设备
- 输入设备>输出设备
- 实时设备>非实时设备
中断屏蔽字与优先级设定
- 以A,B,C为例，设定优先级B>C>A
- A：100；B：111；C：101
- 0所在的位置表示允许被该位中断
缺点
1. 传输一次数据就要中断一次，CPU开销大
2. 效率低，不适合高速传输系统

5.5 DMA（直接存储器存取）方式

优点
- 外设与主存间建立一个由硬件管理的数据通路
- CPU不介入外设与主存的数据传输
- 减少CPU开销，提高系统效率
内存争用： DMA控制器和CPU可能同时访问内存
1. DMA访内过程中，停止CPU访问内存
  - DMA批量数据传输周期过长，CPU长期无法访内
  - 外设传送两个数据的时间间隔大于存储周期，内存未充分利用
2. DMA与CPU交替访问内存
  - 每个CPU工作周期分成两段：DMA访内和CPU访内
  - 无主存使用权移交过程
3. 周期挪用法
  - DMA要求访问主存时，CPU暂停一个或多个存储周期。一个数据传送结束后，CPU继续运行。

六、计算机的运算方法

6.1 无符号数和有符号数

6.1.1 无符号数

按照规定的长度（字长）以二进制保存，只有数值部分，没有符号位。

6.1.2 有符号数

机器数与真值
- 机器数：计算机内部表示的数
- 真值：数的实际值
- 四种机器码：原码、反码、补码、移码
  - 最高位表示符号：0为正，1为负
  - 其余位表示数值
  - 小数的定点表示：原码、反码、补码
原码
- 整数：数值位表示小数点前的整数部分
- 小数：数值位表示小数点后的小数部分（绝对值小于1）
- 特点：
  1. 有+0(0,000)和-0(1,000)两种0
  2. 加、减运算方式不统一，符号相异不能直接计算
反码
- 正数：原码
- 负数：其正数原码的各位取反
- 特点：
  1. 有+0(0,000)和-0(1,111)两种0
  2. 运算较复杂
补码
- 正数：原码
- 负数：反码+1
- 特点：
  1. 0有唯一的表示方式
  2. 加、减运算方式统一
  3. 机器数的唯一表示
  4. 小数可以表示-1(1.000)
- 补码运算：
  1. $[[X]_补]_补=-(-X)=X$
  2. //2：右移1位，最高位补符号位（正数补0，负数补1）
  3. *2：左移1位，最低位补0，符号位变化即为溢出
  4. 不同位数加减法：位数少的数，高位补符号位直至位数相同，然后按位加减
移码
- 补码的符号位取反
- 保持数据原有的大小顺序，便于比较
- 仅用于表示整数，通常用于浮点数的阶码

6.2 小数的浮点表示（原码表示）

表示格式
- $N=S\times r^j$
- S：尾数（小数）；r：基数($2^k$)；j：阶码（二进制表示）
- $S_f$：浮点数的符号
- $n$：决定浮点数的精度
- $m$：决定浮点数的表示范围
规格化数
- 基数$r=2^k$时
- 尾数$S$的最高的$k$位（小数点后$k$位）不全为0
- 特别的，$r=2$时，S=0.1xxxxxx
- 尾数左右移动$k$位，阶码变化$1$
表示范围
- 尾数$S$：$0,[2^{-n},1-2^{-n}]$
- 阶码$j$：$[-2^m+1,2^m-1]$
- 表示范围：$[-(1-2^{-n})\times 2^{2^m-1},-(2^{-n})\times 2^{-2^m+1}],0,[2^{-n}\times 2^{-2^m+1},(1-2^{-n})\times 2^{2^m-1}]$
机器0
- 尾数$S=0$的数：x,xxxx;0.0000000000
- 阶码小于等于精度（$-2^m+1,-15$）的数：1,0000(-16);x.xxxxxxxxxx
- 阶码用移码时，机器$0$为：0,0000;0.0000000000
IEEE754 Standard
- 构成：符号位$m_s$（数符），阶码$E$（含阶符，移码表示，基数为2），尾数$M$（隐去开头的1，原码表示）
- $(-1)^{m_s}\times 1.M\times 2^E$
- 偏置值：阶码的移码与原码的差值（$2^{k-1}-1$）

	符号位	阶码	尾数	总位数
单精度float	1	8	23	32
双精度double	1	11	52	64
临时实数	1	15	64	80

6.3 定点运算

6.3.1 移位运算

算术移位与逻辑移位
- 算术移位：符号位不变
- 逻辑移位：左移右移补0
算术移位添补

正负	码值	添补
+	原码、反码、补码	补0
-	原码	补0
-	反码	补1
-	补码	左移补0，右移补1

丢失有效位
- 左移丢高位：溢出
- 右移丢低位：损失精度

6.3.2 加减法运算

补码加减运算公式
1. 加法：$[A]_补+[B]_补=[A+B]_补$
2. 减法：$[A]_补-[B]_补=[A+(-B_补)]_补=[A]_补+[-B]_补$
3. 连同符号位一起相加，溢出位舍去
4. 真实溢出：正正得负/负负得正
硬件实现
1. 串行加法器：逐位相加，进位传递
  2. 缺点：高位依赖低位，速度慢
  3. $S_i=X_i\oplus Y_i\oplus C_{i-1}$
  4. $C_i=X_iY_i+X_iC_{i-1}+Y_iC_{i-1}=X_iY_i+(X_i\oplus Y_i)C_{i-1}$
2. 并行加法器：每一位并行计算
  1. 原理
    1. 记：
      - $G_i=X_iY_i$：生成位（Generate）
      - $P_i=X_i\oplus Y_i$：传递位（Propagate）
    2. 则：
      - $C_i = G_i + P_iC_{i-1}$
    3. 传递得到：
      - $C_i = G_i + P_iG_{i-1} + P_iP_{i-1}G_{i-2} + \cdots + P_iP_{i-1}\cdots P_1C_0$
      - $以i=4为例，C_4 = G_4 + P_4G_3 + P_4P_3G_2 + P_4P_3P_2G_1 + P_4P_3P_2P_1C_0$
    4. 记：
      - $G_4^* = G_4 + P_4G_3 + P_4P_3G_2 + P_4P_3P_2G_1$：组进位生成位
      - $P_3^* = P_4P_3P_2P_1$：组进位传递位
      - $C_4 = G_4^* + P_4^*C_0$：组进位传递函数
    5. $S_i=P_i\oplus C_{i-1}$
  2. 1级门电路延迟-与门异或门电路：计算$G_i,P_i$
  3. 2级门电路延迟-先行进位电路：计算$C_i$
  4. 四位快速加法器

6.3.3 乘法运算

思想：移位相加

6.3.3.1 原码乘法

符号位：单独计算
数值位：从$Y$的最低位开始，逐位决定$SUM$是否加$X$，然后$Sum$右移一位。

原码乘法

6.3.3.2 （重点）补码乘法：Booth算法

给定：$[X]_补,[Y]_补$，求$[X]_补\times [Y]_补$

求$[-X]_补$，$[Y]_补$最后补一位0
当前$Y$的末2位$Y_{-2}Y_{-1}$决定$SUM$加$X,0,-X$的哪一个
- $SUM+=X\times (Y_{-1}-Y_{-2})=\begin{cases}
  0 & Y_{-2}Y_{-1}=00\\
  X & Y_{-2}Y_{-1}=01\\
  -X & Y_{-2}Y_{-1}=10\\
  0 & Y_{-2}Y_{-1}=11
  \end{cases}$
右移$SUM$，左边补符号位
去掉$Y$的最低位，重复步骤2-3，直到$Y$只剩1位

补码乘法

6.3.4 除法运算

6.3.4.1 恢复余数法

给定：$[X]_补,[Y]_补$，求$[X]_补\div [Y]_补$（$X,Y$为正数）

求$[-Y]_补$
计算$X+=(-Y)$
若双符号位为$11$，即$X$为负数，不够减，则该位为$0$，恢复余数：$X+=Y$
若双符号位为$00$，即$X$为正数，够减，该位为$1$
$X$左移一位，右边补0
重复步骤2-5，直到$X$左移$4$位（$Y$的位数）
当前的余数为$X\times 2^{-4}$

恢复余数法

6.3.4.2 (重点)非恢复余数法/加减交替法

给定：$[X]_补,[Y]_补$，求$[X]_补\div [Y]_补$（$X,Y$为正数）

求$[-Y]_补$
若双符号位为$00$，即$X$为正数，计算$X+=(-Y)$（第一次必定做减法）
若双符号位为$11$，即$X$为负数，计算$X+=Y$
若双符号位为$00$，即$X$为正数，该位为$1$
若双符号位为$11$，即$X$为负数，该位为$0$
$X$左移一位，右边补0
重复步骤2-6，直到$X$左移$4$位（$Y$的位数）
当前的余数为$X\times 2^{-4}$

非恢复余数法

6.4 浮点运算

规格化浮点数

6.4.1 浮点加减法

例：
$$
X=2^{E_x}M_x=2^{101}\times 0.11011011 \\
Y=2^{E_y}M_y=2^{111}\times-0.10101100
$$
尾数在计算机中以补码表示，可存储10位尾数，2位符号位，阶码以补码表示，双符号位, 求$X+Y$

6.4.1.1 将X,Y转化为带符号的浮点补码格式

$$
X=00101,00.11011011 \\
Y=00111,11.01010100(-0.10101100)
$$

6.4.1.2 对阶

原则：小阶对大阶

计算$[-E_y]_补=11001$
计算阶差$E=E_x+(-E_y)=00101+11001=11110=-2(D)<0$
$X$是小阶，$M_x$右移$|E|=2$位：$M_x=00.0011011011$，$E=111$
$X=00111,00.0011011011$

6.4.1.3 尾数求和/差

$$M=M_x+M_y=00.0011011011+11.01010100=11.1000101011 \\
X+Y=00111,11.1000101011
$$

6.4.1.4 结果规格化

双符号位为$11$，是负数，规格化到小数点后一位为$0$。（本题中，$M$双符号位为$11$）
双符号位为$00$，是正数，规格化到小数点后一位为$1$。
结果左移一位得到：
$$
X+Y=00110,11.000101011
$$
尾数溢出时可能需要尾数右移

6.4.1.5 舍入处理

0舍1入：$X+Y=00111,11.00010110$
截断：$X+Y=00111,11.00010101$

6.4.1.6 得出结果

$$
X+Y=00110,11.00010101 \\
=2^{110}\times -0.11101011
$$

6.4.1.7 溢出判断

根据阶码的双符号位进行判断：

01：正溢出
10：负溢出

6.4.2 浮点乘法/除法

乘法：尾数定点相乘，阶码相加
除法：尾数定点相除，阶码相减

七、指令系统

7.0 基本概念

指令：计算机能直接识别、执行的操作命令（机器指令）；冯诺依曼结构“程序控制”原理实现的载体
指令集：一台计算机能执行的全部指令的集合
等长指令（MIPS）/变长指令（x86）
指令系统的特点：完备、高效、规整、兼容
为什么说“指令系统是计算机系统硬件与软件之间的界面”？
- 从程序的编写与执行角度看，指令规定了计算机的操作类型及操作数地址，它们是产生各种控制信号的基础。
- 从硬件设计角度看，在设计计算机的时候先要确定硬件能够直接执行哪些操作，表现为一组指令集合，称之为计算机的指令系统。
- 因此，指令系统体现了一台计算机的软、硬件界面。

7.1 机器指令

7.1.1 指令的一般格式

$操作码OP|(寻址模式Mode)|地址码A_1|地址码A_2|\cdots$

操作码字段：反映机器（对什么数据）做什么操作
1. - 定长操作码：总操作种类=2^k
  - 变长操作码：操作码向不用的地址码字段扩展
2. 扩展操作码技术
  - 假设二操作数指令格式为：$OP(4)|A_1(6)|A_2(8)$ 15条
  - 只保留全1为长操作数的锚点，那么：
    - 单操作数指令格式可以为：$1111|OP(6)|A_1(8)$ 63条
    - 无操作数指令格式可以为：$1111|111111|OP(8)$ 256条
  - 原则：短操作码不能是长操作码的前缀
  - 可以根据实际指令数量，通过保留多个锚点，识别更多的操作码：
    - 假设二操作数指令有10条，则可以保留6个锚点
    - 可用于单操作数指令的条数变为$6\times 2^6$ 条
    - 按需分配后剩下的可以作为无操作数指令的锚点
  - 例题：设某指令系统指令字长16位，每个地址码为6位。若要求设计二地址指令15条、一地址指令34条，问最多还可设计多少条零地址指令？
    - 指令格式：$OP(4)|A_1(6)|A_2(6)$
    - 二地址指令条数15，保留锚点数$2^4-15=1$
    - 一地址指令条数34，保留锚点数$1\times 2^6 - 34 = 30$
    - 零地址指令条数：$30\times 2^6 = 1920$
3. 经常使用的操作设计为短操作码，不常用的设计为长操作码
操作数字段（地址码字段）：
- 四地址指令（$OP|A_1|A_2|A_3|A_4$）：$(A_1)OP(A_2)\rightarrow A_3$，下一条指令位于$A_4$
- 三地址指令（$OP|A_1|A_2|A_3$）：$(A_1)OP(A_2)\rightarrow A_3$，下一条指令位于$PC+1$（利用$PC$代替$A_4$）
- 二地址指令（$OP|A_1|A_2$）：$(A_1)OP(A_2)\rightarrow AC$，下一条指令位于$PC+1$（利用$AC$代替$A_3$）
- 一地址指令（$OP|A_1$）：$(A_1)OP(AC)\rightarrow AC$，下一条指令位于$PC+1$（利用$AC$代替$A_2,A_3$）
- 零地址指令（$OP$）：基本的无操作数操作指令，如空操作、停机、中断、返回等
- 访存次数：取指令1次+读取操作数次数+存结果到操作数次数（若存入AC则不计）
- 直接寻址范围：$2^k$，k是单个地址码位数
- 减少操作数个数的优点：
  1. 利用硬件资源代替地址码字段
  2. 扩大指令的寻址范围
  3. 缩短指令字长

7.1.2 指令字长

指令字长决定于：

操作码的长度
操作数地址的长度
操作数的个数

- 定长指令：指令字长=存储字长
- 变长指令：通常按字节的倍数存储

7.2* 操作数类型和操作类型

7.2.1 操作数类型

地址：用于表示地址的无符号整数
数字：定点数、浮点数、十进制数
字符：ASCII
逻辑：逻辑数据/运算

7.2.2 数据在存储器中的存储方式

边界对齐/边界不对齐
大端存储/小端存储

7.2.3 操作类型

1.数据传送 2.算术/逻辑运算 3.移位运算 4.控制转移

7.3 寻址方式

7.3.1 指令寻址

顺序寻址：通过程序计数器PC+指令占用字节数，自动生成下一条指令地址
- PC的变化时机：每当CPU从存储器中读取出一个字节时，PC+1
跳跃寻址：通过指令中的转移类操作，跳转到指定地址

7.3.2 数据寻址