三、高速缓冲存储器
1、某容量为256MB的存储器，由若干4M × 8位的DRAM芯片构成，则该DRAM芯片的地址引脚和数据引脚总数是多少？提示：注意 DRAM 的地址线是复用的。
4M需要22根地址线，地址线复用减半。所以需要地址线11根，数据线8根。
3.1概述
1.问题的提出
CPU和主存间存在速度差异，避免出现CPU“空等”现象
局部性原理：
空间局部性：在将来要用到的信息，可能与现在正在使用的信息在存储空间上是相近的。
时间局部性：在将来要用到的信息，可能是现在正在使用的信息。
2.Cache的工作原理
（1）主存和缓存的编址
主存，地址有n位，b位用于块内存储单元的编号，m位用于块号的编号
缓存，块内地址和主存相同，但块数较少，而且有标记用于标记对应主存的块号
缓存块长为4个16位的字，容量为4096字，主存容量为64K字，则缓存有[填空 1 ]块，主存有[填空 2 ] K块。
1024，16
（2）命中与未命中
缓存共有C块，主存共有M块，M>>C
命中：主存块已调入缓存，主存块与缓存块建立了对应关系
未命中：主存块未调入缓存，主存块与缓存块未建立对应关系
任何时刻都有一些主存块处在缓存块中。 CPU 欲读取主存某字时，有两种可能：一种是所需要的字已在缓存中，即可直接访问 cache( CPU 与 Cache 之间通常一次传送一个字）；另一种是所需的字不在 Cache 内，此时需将该字所在的主存整个字块一次调人 cache 中（ cache 与主存之间是字块传送）。如果主存块已调人缓存块，则称该主存块与缓存块建立了对应。
（3）Cache的命中率
CPU欲访问的信息在Cache中的比率。
命中率：
，Nc为访问Cache的总命中次数，Nm为访问主存的总次数。
命中率与Cache的容量和块长有关。一般每块可取4~8个字。块长取一个存取周期内从主存中调出的信息长度。
如IBM 370 / 168，4体交叉，块长取4个存储字
（4）Cache-主存系统的效率
效率e与命中率有关
平均访问时间 = h*tc +（1-h）*tm，tc是访问Cache的时间，tm是访问主存的时间。
e = 访问Cache的时间/平均访问时间*100%
3.Cache的基本结构
CPU申请到总线后，开始发送地址；地址被拆解为块号和块内地址；块号到主存/Cache地址映射变换结构进行查找；如果命中，块号对应变换，和块内地址结合为Cache地址，Cache取数据送至CPU；如果未命中，进入Cache替换策略；如果Cache已满，则将Cache某段数据交换到主存中；如果未满，主存将数据调入Cache，且送至CPU。
4.Cache的读写操作
Cache的读操作
首先查看Cache的第x行，检查此时Cache的标记位是否与想要访问的标记位相同，且有效位位为1；若都满足，则命中，按块内地址读出数据，送入CPU中完成访存；若标记不符或有效位为0，则访问主存取出数据送往CPU和对应Cache，将主存地址最高y位存入Cache的Tag中，将有效位改为1。
Cache的写操作
1.写直达法
写数据时同时写入Cache和内存，保持一致性，但增加了访存次数
2.写回法
先写入Cache，当Cache数据被替换出去时再写回主存。Cache和主存的数据不一致，要在Cache每个块增加一个脏位
5.Cache的改进
（1）增加Cache的级数
片载（片内）Cache
片外Cache
（2）统一缓存和分立缓存
分立缓存不符合冯诺依曼体系
指令Cache
数据Cache
与主存结构有关
与指令执行的控制方式有关 是否流水
现在的缓存可分为片载缓存和片外缓存两级，并将指令缓存和数据缓存分开设置（）
对
采用指令Cache与数据Cache分离的主要目的是（）
A降低 Cache 的缺失损失
B提高 Cache 的命中率
C降低 CPU 平均访存时间
D减少指令流水线资源冲突
D
3.2Cache-主存的地址映射
1.直接映射
主存的字块只能对应Cache的固定位置，Cache块号=主存块号%Cache总块数
Cache的总容量=数据+地址映射表；每一块有一个映射表，写着主存的标记和1位有效位。
假设一个主存地址被分为abc三部分，a表示主存的标记，长度=主存块数/cache块数
b表示cache行号，长度由cache的行数决定
c表示块内地址，由一个块内的存储大小决定
例如，主存256M=228，前22位为主存块号，后6位为块内地址
由于主存和Cache的块内地址相同，所以将主存块号的一部分作为Cache的标记
我们发现，主存块号与Cache位数2n取余，相当于取主存块号末n位，所以末n位不用当作Cache标记。
利用率低，冲突较多，命中计算快
2.全相联映射
冲突少、利用率高、命中率计算变复杂
3.组相联映射
主存对应唯一的缓存块、块内不分顺序
当c=r时，退化为全相联。所以可以调整参数平衡速度与利用率
主存地址对组数取余得到组号
主存地址分为abc三部分，a是主存标记，b是组号，c是块内地址（注意，这个块不是建组后的大块，是和主存一样的小块！）
每个cache行都会对应一个标记项，用于标记当前cache行保存的数据状态，cache行标记项包含：
- * 有效位：（一定有）固定占 1 位，由于cache未装进数据块时，主存字块标记默认为0，所以有效位是为了区分当前cache块是没装数据还是装了一个主存第0的数据
- * 标记位：（一定有）主存字块标记位数，用于标识当前cache行存放的主存哪一行数据，
- 脏位：（特定条件下才有）也叫一致性维护位，只有当cache写策略采用 写回法 时，该位生效并且占 1 位
- 替换控制位： （特定条件下才有）或叫替换算法位，用于标记替换cache哪一行会被换出，在cache替换策略中，当采用 LRU和LFU替换算法 时，这个控制位会作为被换出的依据。
1.cache的总容量包括块的大小+1位有效位+标识
2.主存地址先转换为主存块号，再转换为cache块号
标记是当作数据存储的，所以cache地址是行号+块内地址
考察组相联模式下主存地址的划分
答案为148K
标记阵列容量=有效位1位+标记位n位+脏位1位+替换算法控制位
假设主存容器为512KB,Cache容量为4KB，每个字块为16个字，每个字有32位。
（1）Cache地址有多少位？可容纳多少块？
（2）主存地址有多少位？可容纳多少块？
（3）在直接映射方式下，主存的第几块映射到Cache中的第五块（设起始字块为第一块）？
（4）画出直接映射方式下主存地址字段中各段的位数。
注意：默认按字节编址，最小单位是B
某计算机的 Cache 共有 16 块，采用 2 路组相联映射方式，每个主存块大小为 32 字节，按字节编址。主存 129 号单元所在主存块应装入到 Cache 的组号是？
4
每个块32字节，129单元在主存第4块（从0开始编号）。cache共8块，4模8得4。
三、替换算法
1.先进先出（FIFO）算法
先调入的先出去，不能提高命中率
2.近期最少使用（LRU）算法
对使用情况计数，使用最少的出去；或者计算最后一次使用的时间
3.随机法
小结：
直接映射——某一主存块只能固定映射到某一主存块
全相联映射——某一主存块可以映射到任一缓存块
组相联映射——某一主存块只能映射到某一缓存组的任一块
优点总结
命中率高且电路实现简单的Cache 与内存的映射方式是（）映射方式
A全相联
B直接
C组相联
D哈希
C直接映射简单但命中率不高；全相联命中率高但复杂。
四、海明码
编码的最小距离：任意两组合法代码间二进制位数的最少差异
编码的纠错、检错能力与编码最小距离有关
L-1=D+C（D>=C）
L：编码最小距离
D：检错位数
C：纠错位数
检错纠错的原理：和合法代码不一样就是出错；n位错的概率小于n-1位错的概率。
汉明码具有一位纠错能力
汉明码采用奇偶校验、采用分组校验
汉明码的组成：
（1）需添加k位检测位
2k>=n+k+1 n是原码的位数
（2）检测位的位置
2i = （1，2，4，8，16……）
（3）检测位的取值
与组内的奇偶校验有关
（4）每个检测位的小组
2i位的检测位负责二进制第i位取1的位
编码从1开始计数
求0101按“偶校验”配置的汉明码
1，n=4，由2k>=n+k+1得k=3
2，总共4+3=7位，把1~7写好，0101填到非校验位上
3，根据分组计算校验位，1357第一组、2367第二组、4567第三组，偶校验
4，结果为0100101
用海明码对长度为 8 位的数据进行检错/纠错时，若能纠正一位错，则校验位数至少为
4
按配奇原则配置1100101的汉明码
11101001101
汉明码的纠错方法
如果为偶校验，按照分组进行组内相与。结果为0说明组内都没出错，1说明组内有错。
已知接收到的汉明码为0100111，偶校验，请问要传送的信息是什么？
第一组：1，3，5，7，与结果为0，都没错
第二组：2，3，6，7，与结果为1，2、6可能有错
第三组：4，5，6，7，与结果为1，4、6可能有错
所以6出错，1应改为0
去掉检验位，原信息为：0101
五、硬盘
一、概述
1.特点：不直接与CPU交换信息，与IO进行交换
2.磁表面存储器的技术指标
（1）记录密度 道密度Dt（单位距离有多少道） 位密度Db
（2）存储容量=盘面数*道数*每道上的位数（每道上的位数一样）
（3）平均寻址时间=寻道时间+等待时间（先找到道，再等盘转到对应扇区）
辅存的速度=寻址时间+磁头读写时间
（4）数据传输率=每道字节数*转速，单位B/s
（5）误码率 出错信息位数和读出信息的总位数之比
注意最外两侧盘面是否可以记录；内径是直径
（1）6*2=12面
（2）存储区域总道数=（（33-22）/ 2）*40=220=柱面数
（3）2*pi*（22/2）*400*220*12/8=9118560B
（4）一道的数据量=400*2*pi*22/2=27632，数据率=27632*3600/60/8=207240B/s
最小半径115mm，最大半径115+275/5=170mm
最高位密度=12288*8/（115*2*pi）=136位/mm
最低位密度=12288*8/（170*2*pi）=92位/mm
硬磁盘存储器
1.类型：固定磁头和移动磁头、可换盘和固定盘
2.结构
假设磁盘存储器共6个盘片，最外侧两盘面不能记录。每面204条磁道，每磁道12扇段，每扇段512B，转速7200rpm，平均定位时间为8ms
（1）计算该存储器的存储容量
（2）计算平均寻址时间
1.（6*2-2）*204*12*512=12533760B
2.寻址时间=寻道时间（定位时间）+等待时间
有可能恰好不需要等待，有可能要转一圈，概率均为0.5，所以是0+转一圈用时乘0.5
寻址时间=8 + (60*10^3)/7200*0.5=12.165ms
