计算机系统概述
课件
内容少，以下为需要知道的概念
时钟频率（Hz）：单位时间执行最小操作的次数
时钟周期：执行一次最小操作所需的时间
CPI：一条指令所需的周期数，平均CPI则是考虑基准程序中指令的平均
MIPS（百万条/s）：每秒执行多少百万条指令
MFLOPS（百万条/s）：每秒执行多少百万次浮点操作
作业
冯·诺伊曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是指令周期的不同阶段
计算机的顶层视图
课件
属于概述，没有什么重要内容，需要知道冯诺依曼结构
作业
没有对应作业题
数据的机器级表示
课件
有符号整数表示
原码、反码不重要
补码实质：模$2^d$算术下的整数，并将小于$2^{d-1}$的元素解释为非负数，其余解释为负数。因此补码的加法逆元是取反加1，也就是$2^d-x$，在进行运算时结果总对$2^d$取模便得到正确结果，无需特殊处理。
浮点数表示
对于32位浮点数，最高位为符号位（0正1负），接下来8位为阶码，剩下23位为尾数
阶码使用移码，偏移量为$\frac{2^8-2}{2}=2^7-1=127$，减去的两个对应非规格化浮点与特殊值的特殊阶码
阶码非全0或全1的浮点数是规格化浮点数，对应的数字为$\text{符号} \times 1.\text{尾数} \times 2^{\text{阶码}-\text{偏移量}}$
阶码全0的浮点数为非规格化浮点数，对应的数字为$\text{符号} \times 0.\text{尾数} \times 2^{1-\text{偏移量}}$
阶码全1的浮点数为特殊值，若尾数为全0则对应相应符号的无穷大，否则对应NaN
NBCD
直接将十进制数位每位化成四位二进制数，并用一个额外的四位表示符号（1100正1101负）
作业
注意整数和浮点数相互转换时的精度损失
十进制有限小数在二进制中不一定是有限小数
数据校验码
课件
奇偶校验码
在数据后加一位校验码使最终结果中1的数量为奇数（奇校验码）/偶数（偶校验码），可以发现是否有奇数个位发生错误，但不能修复
海明码
实质：二进制分组奇偶校验
将所有的位从1开始编号，把数据依次放在编号不是$2^k$的位上。对于编号为$2^k$的位，填入$\displaystyle \bigoplus_{i \& 2^k \neq 0} \text{第}i\text{位的内容}$
可以发现并纠正任何一个位的错误
CRC
笔试不考。在模2多项式域上做除法，取余数即为CRC
对于$n+1$长的生成多项式，除之前要先在数据后补$n$个0
作业
注意位序，最右是低位
注意题述中生成校验码的单位（字节/整个数据）
整数运算
课件
具体计算方法笔试不考，大概了解即可
作业
CPU计算加减法时并不关心也不知道操作数是否是有符号的，所以标志位会分别设置操作数作为有符号和无符号运算的结果，与操作数本身具体是有符号/无符号无关
CF：进/借位标志，将操作数作为无符号整数考虑，如果无符号加法导致进位或无符号减法导致借位则CF=1
OF：溢出标志，将操作数作为有符号整数考虑，如果运算导致溢出则OF=1
浮点数运算
课件
具体计算方法笔试不考，大概了解即可，大概步骤是对阶（小阶码对齐到大阶码）、计算、重新规格化
作业
浮点数的左规指尾数左移，阶码-1；右归则指尾数右移，阶码+1。因此左规可能引起阶码下溢，右归可能引起阶码上溢
二进制编码的十进制数运算
课件
简单，而且笔试不考
作业
没有对应作业题
内部存储器
课件
存储器类型
以下存储器均支持随机访问，除RAM之外都是主要用于读取的存储器
- RAM，随机访问存储器，可读可写，易失。分DRAM和SRAM，DRAM便宜、密度更高，但更慢且需要刷新，SRAM更贵、密度更低，但更快且不需要刷新。SDRAM则是同步DRAM，使用一同步时钟信号控制输入输出。DDR SDRAM则在同步时钟信号的上升和下降沿各发送一次数据，速度更快
- ROM，只读存储器，出厂前被写入一次，之后只能读取
- PROM，可编程只读存储器，出厂后可被用户用电信号写入一次，之后只能读取
- EPROM，可擦除可编程只读存储器，可被用户写入一次，此后一般只能读取，但可以用紫外线擦除其中所有内容来再次写入
- EEPROM，电可擦除可编程只读存储器，类似EPROM，但使用电信号进行字节级擦除
- Flash，快闪存储器，类似EEPROM，但是只能进行块级擦除
存储器组成与访存
存储器芯片中一般将存储单元按照二维排布，并尽量排成正方形
访存时可以复用地址线，分别传一次行地址和列地址即可定位一个存储单元，因此存储器芯片最后只需要一半的地址线
DRAM刷新
DRAM中存储单元需要定期刷新来维持其内容，存储器芯片内的刷新以行为单位进行，每次刷新操作只能刷新某一行的所有单元。安排刷新的方法有若干种
集中刷新：周期性地花费一段时间，在这段时间中依次刷新芯片内所有的行，过程中禁止进行内存访问
分布式刷新：每次访问某个单元时，在访问操作结束前对这一行进行刷新，此后访问操作才算完成
异步刷新：使用一个定时的刷新信号，每次触发时选择当前空闲且最近尚未刷新过的一行进行刷新，刷新信号的间隔需要足够短来保证所有单元在内容失效前都会被刷新
多个存储芯片的组织
使用多个存储芯片时，可以通过不同的方式将他们组织在一起。注意，组织在一起的多个存储芯片的访问、刷新等操作互不干扰，所以一个周期内可以进行多个芯片的访问与刷新
字拓展：基本寻址单元大小不变，多个存储芯片带来更大的地址空间
位拓展：地址空间不变，多个存储芯片带来更大的寻址单元
字、位同时拓展：综合以上两种拓展
内存中数字的存储
大端序：高位字节存在低地址，低位字节存在高地址
小端序：低位字节存在低地址，高位字节存在高地址
作业
k体交叉编址：有编号为$0$到$k-1$的k个存储芯片，编址时将地址$A$放在$A \bmod k$号芯片上
访存冲突：若连续的四次访问中涉及同一个模块多次，便可能发生访存冲突
Cache
课件
局部性
时间局部性：在短时间内多次访问同一地址
空间局部性：在短时间内访问相邻的一串地址
缓存对访问时间的作用
若缓存命中率为$p$，访问缓存时间为$t_c$，访问主存时间为$t_m$，则使用缓存后平均访问时间为$t_c+(1-p)t_m$，对多级缓存计算方式类似
缓存的组成
使用SRAM构建，有Tag SRAM和Cache SRAM，分别用于存储缓存行当前的标签与缓存行的内容
缓存映射策略
记缓存行的大小为$S$，则地址$A$对应的块号为$B=\left\lfloor \frac{A}{S} \right\rfloor$
- 直接映射。记缓存行数量为$C$，直接将块$B$缓存到$B \bmod C$行，并将该行的标签设置为$\left\lfloor \frac{B}{C} \right\rfloor$
- 全关联映射。将块$B$缓存到某一行，并将该行的标签设置为$B$
- k路组关联映射。将每$k$个缓存行分为一组，共$G=\frac{C}{k}$组，把块$B$映射到$B \bmod G$组的某一行，并将该行的标签设置为$\left\lfloor \frac{B}{G} \right\rfloor$
缓存替换策略
当对应组内没有空闲缓存行，就需要选择某一非空闲行将其替换
- LRU，最近最少使用，替换掉最长时间未被访问的一行
- FIFO，先进先出，替换掉停留时间最长的一行
- LFU，最不经常使用，替换掉被访问次数最少的一行
- Random，随机替换，随机替换掉一行
缓存写策略
写入缓存的数据最终都要写回主存，需要确定写回主存的时机
- 写直达，每次写入缓存同时，将数据同步写入主存
- 写回，当缓存行被替换时，若该行已被修改，将其中数据写回主存
作业
没有什么特别的
外部存储器
课件
磁盘数据组织
盘片上的数据按若干同心圆环组织，称为磁道，每个磁道上有若干扇区（大小一般为512B），扇区间有间隙
不同磁道上的扇区划分一般使用恒定角速度划分，每个扇区对应的角速度相同，因此内外磁道尽管长度不同但是数据量是相同的，磁盘容量受到最内圈磁道数据密度的制约。也有使用多带式记录的磁盘，将磁道划分为若干组，不同的组允许不同的密度，这样可以提升容量，但需要更复杂的控制电路
所有盘片上处于相同位置的一组磁道被称为一个柱面
磁盘访问时间
需要考虑平均寻道时间，平均旋转延迟和数据访问时间
平均旋转延迟是磁盘转半圈所需的时间
当连续访问相邻的磁道，不需要加多次平均寻道时间，但需要加多次平均旋转延迟，以及如果题目明确给出了跨越一个磁道的时间也要算进去
磁盘寻道调度
- FCFS，先来先服务，按照请求到达的顺序进行服务
- SSTF，最短寻道时间优先，优先处理离当前磁头位置最近的磁道上的请求
- SCAN，扫描，按一个方向移动磁头并处理途中的请求，到达边缘后调转移动方向，继续过程
- C-SCAN，循环扫描，按一个方向移动磁头并处理途中的请求，到达边缘后立马回到起点，重复过程
- LOOK，类似SCAN方法，但是不需要到达边缘再调转方向，而是当前前进方向上没有请求就立刻调转方向
- C-LOOK，类似C-SCAN方法，但是不需要到达边缘再回到起点，而是当前前进方向上没有请求就立刻回到起点
作业
没有什么特殊的
RAID
课件
- RAID 0，无冗余，数据按条带在各个盘上分布，IO效率高
- RAID 1，复制冗余，每两个磁盘存储一样的数据，数据同样使用条带分布
- RAID 5，奇偶校验冗余，对于不同盘上同一相对位置的一组条带生成一个奇偶校验条带，将奇偶校验条带分布在所有盘上
作业
没有什么特殊的
虚拟存储器
课件
内存分页，使用虚拟内存地址，每次访问主存先通过页表将虚拟页号转换到物理页号，再进行访问。页表未命中会引发缺页异常，操作系统从外存加载页
页表也在主存内，访问较慢，因此还有TLB（SRAM实现）存储了关于页表映射的缓存，一般使用全关联或组关联
作业
页表、TLB、Cache命中关系需要清楚（Cache或TLB命中便一定有页表命中）
指令系统
课件
没有难点，有了解即可
寻址方式
- 立即寻址，指令中直接存储操作数
- 直接寻址，指令中存储操作数的地址
- 间接寻址，指令中存储操作数的地址所在的地址（用于解决直接寻址由于指令长度有限导致可寻址的地址空间受限的问题）
- 寄存器寻址，指令中存储操作数所在的寄存器编号
- 寄存器间接寻址，指令中存储操作数的地址所在的寄存器编号
- 偏移寻址，指令中指示（显式或隐式的）一个地址所在的寄存器编号和所需地址相对于该地址的偏移量。具体类型有相对寻址（PC相对寻址）、基址寄存器寻址（基址寄存器与偏移量）、变址寻址（基址与变址寄存器）
- 栈寻址，基于栈地址寄存器的寻址，实质上是一种寄存器间接寻址
作业
数据通路：指令执行过程中数据所经过的路径，包括路径上的部件
指令周期和指令流水线
课件
指令周期
- 取指周期，取得指令
- 间指周期，取得间接寻址的有效地址
- 执行周期，执行指令
- 中断周期，检查并处理中断
流水线
将指令执行的不同阶段分开，构造流水线，以此允许多条指令同时执行不同阶段
使用流水线后，CPU的周期时间只受到流水线中最慢的一段以及流水线各段之间通信延迟的限制，即$T=t_m+d$，CPU频率可以大幅提高
$k$阶段流水线从初始状态开始执行连续$n$个指令的耗时$t_{k,n}=(k-1+n)T$，最开始的$k-1$个周期用于填充流水线，随后每周期都会有一个指令完成
冒险
流水线上的指令并不是总能并行地执行，有时会发生冒险（hazard）导致流水线停顿（stall），可能发生的冒险有以下三种：
- 结构冒险，流水线上的两条指令同时需要同一硬件资源。解决办法为修改设计让他们分别使用独立的资源，或让它们分时使用所需资源
- 数据冒险，流水线上的某条指令依赖另一条未完成语句的结果。解决办法为旁路，通过特殊的电路设计，提前将未完成语句的结果提供给使用它的指令（这一方法可行是由于ALU的唯一性。因为只有一个ALU，所以当ALU使用未完成语句的结果时，该结果实际上已经被计算好了，只是还未被写回目的地而已）
- 控制冒险，跳转指令导致当前流水线上的指令不再需要执行。解决办法为分支预测，提前猜测分支语句的跳转结果，尽量避免流水线上的指令失效
作业
没有什么特殊的
控制器
课件
寄存器分类
- 用户可见寄存器，允许用户访问和控制的寄存器（通用寄存器、数据寄存器、地址寄存器、标志寄存器），在子程序调用时自动保护和恢复
- 控制和状态寄存器，用于控制CPU的执行状态，大部分时候用户不可见（PC、IR、MAR、MBR、PSW）
微操作
CPU每个指令周期完成一条指令，而指令周期分为我们上一节提到的各个子周期，每个子周期则是通过若干CPU微操作完成的
安排微操作时要保证有先后顺序的、有冲突的微操作安排在不同的时钟周期，在此基础上使用尽可能少的时钟周期
整个过程通过控制器进行控制，控制器可以是硬布线实现（将控制逻辑直接使用电路实现）也可以是微程序实现（使用微程序控制器执行预先存储的微程序来实现控制逻辑，微程序控制器的主要任务是定序与执行微指令）
作业
关于微指令与微操作：微操作会被分为若干互斥类，每条微指令可以同时执行属于不同互斥类的指令，因此计算微指令长度的时候要分别考虑所有互斥类，还要考虑不执行某个互斥类中指令的状态（因此一个c条指令的互斥类需要c+1个状态）
断定法(下地址字段法)：微指令中使用一个字段来指定下一条微指令的地址
总线
课件
总线类型
- 芯片内部总线：连接芯片内部的各个部分（如CPU内部连接各组件的总线）
- 系统总线：系统内部的总线，连接CPU、存储器、IO控制器和其他功能设备
- 通信总线：连接主机和I/O设备，或连接不同的计算机系统
总线用途
- 专用总线：始终只负责一项功能，或始终分配给特定的计算机组件
- 复用总线：将同一线路用于多种用途
总线仲裁
当多个设备需要使用总线时，需要一种方式来选择下一个使用总线的设备，需要考虑设备的优先级与选择的公平性
集中式仲裁：由专门的总线控制器来负责分配总线使用权（菊花链、计数器查询、独立请求）
分布式仲裁：每个设备都包含访问控制逻辑，各设备共同作用分享总线（自举式、冲突检测）
具体仲裁方案不便在此说明，请自行查看ppt
总线时序
同步时序：所有设备根据统一的同步时钟进行通讯
异步时序：设备不根据时钟进行通讯，而是进行握手来确保通信时序，有非互锁（只有Ready上升到Ack上升一次握手）、半互锁（在非互锁基础上增加Ack上升到Ready下降一次握手）与全互锁（在半互锁基础上增加Ready下降到Ack下降一次握手）
半异步时序：在异步时序中引入时钟，Ready和Ack信号在时钟上升沿改变
分离事务：将一个总线事务分为多个独立的过程，每执行完一个过程就释放总线，下一个过程再重新获取总线，以避免一个事务空占总线，提高总线利用率
总线带宽与数据传输率
总线带宽：不考虑握手等开销，只考虑总线上最大位元传输率
数据传输率：考虑地址传输、握手等开销下的最大数据传输率
同步总线和异步总线的数据传输速率
没什么特别的，但需要注意异步总线上同一事务中先后两次异步传输中间需要一次握手（如读取内存时先传输地址后传回数据，两次异步传输过程中间要有一次握手，因此整个事务中共7次握手）
一定注意计算各种耗时、速率等等时要考虑不同操作的并行（如异步总线上的握手可以和数据读取并行）
总线层次结构
单总线、双总线、多总线等，不重要，了解即可
作业
一定注意计算各种耗时、速率等等时要考虑不同操作的并行
典型的总线标准有ISA、EISA、VESA、PCI、PCI-Express、AGP、USB、RS-232C等
USB是一种连接外部设备的IO总线标准，属于设备总线，是设备和设备控制器之间的接口。而PCI、AGP、PCI-E作为计算机系统的局部总线标准，通常用来连接主存、网卡、视频卡等
PCI是并行总线，USB和PCI-E都是串行总线。注意并行总线并不一定比串行总线快（并行总线位间干扰大，难以做到高频率传输，反而更慢）
输入输出
课件
外围设备并不能直接连接在系统总线上，需要连接在通信总线上与系统的IO模块（IO控制器）通信
外部接口分并行总线（同时传输多位数据）与串行总线（每次传输一位数据）
I/O操作技术
编程式 I/O：处理器通过执行程序来直接控制I/O操作，当处理器发送一条命令到I/O模块时，它必须等待（不断轮询），直到I/O操作完成。操作过程中对CPU的占用率是100%
中断驱动式 I/O：处理器发送一条I/O命令后，继续执行其他指令；并且当I/O模块完成其工作后，才去中断处理器工作。只在中断发生时占用CPU资源
直接存储器读取（DirectMemoryAccess，DMA）：I/O模块与主存直接交换数据，而不需要处理器的干涉。只在DMA初始化和完成时占用处理器资源
中断
中断处理过程：中断发生时，处理器保存断点（当前程序位置），关中断，并跳转到中断处理程序；中断处理程序先保存现场（当前寄存器内容），然后重新打开中断（如果希望支持中断嵌套），处理中断；处理完毕后，中断处理程序再关中断，恢复现场，然后使用中断返回指令；使用中断返回指令后处理器负责恢复断点，并重新打开中断
响应优先级：当有多个中断同时发生时，响应优先级高的中断先被处理
处理优先级：允许中断嵌套时，只有处理优先级高于当前正在处理的中断的中断可以引发中断嵌套（即中断屏蔽字中所有处理优先级小于等于当前中断的中断全部置1）
DMA
DMA事务先由对应驱动程序初始化，然后由DMA模块自主完成，在完成后使用中断通知处理器
DMA会与CPU争用内存的访问权，为此需要一些方法解决冲突，具体有CPU停止法（CPU停止访问内存，等待DMA完成任务）、周期窃取（DMA在CPU不使用内存时才访问内存，进行一个周期的读写后立刻释放）和交替分时访问（CPU与DMA模块在周期内分时访问内存）
DMA配置机制不重要
作业
一定注意计算各种耗时、速率等等时要考虑不同操作的并行
计算数据传输耗时的时候记得考虑外部设备的数据传输率