Katyusha's blog

DRAM的读写#

每个DRAM单元存储一位信息，$w$个DRAM单元组成一个超单元，再由$d$个超单元组成一个DRAM芯片 $d$个超单元构成一个$r \times c$的二维阵列，每个超单元有由行列构成的二元组地址$(i, j)$ DRAM芯片通过地址引脚和数据引脚与外部传递信息，通过两次在地址引脚上传入行地址和列地址来确定要读写的超单元，再通过数据引脚传递具体数据。将超单元设计为二维，减少了需要的地址引脚个数，代价是地址需要分两次传入，降低了效率

内存模块#

内存模块中封装了多个DRAM芯片，我们以8个8M的DRAM芯片，每个超单元存储1个字节为例 当需要访问一个地址为A的字的时候，内存控制器将A翻译成超单元地址$(i,j)$并发送到内存模块中，内存模块再将$(i,j)$广播到每一个DRAM芯片，8个芯片都取出它地址为$(i,j)$的超单元中存储的字节，再将这八个字节合并起来，传送到内存控制器中 将一个字存储在不同的DRAM芯片内的好处：通过提高并行性提高了访问效率，同时减少整个字丢失的可能，提高了可靠性

磁盘的构造#

每个磁盘包含了一个或多个盘片，每个盘片有着两个盘面，盘片绕着中心的主轴，以固定的角速度旋转 每个盘片包含了多个被称为磁道的同心圆，每个磁道上都有着多个用来存储信息的扇区，每个扇区存储的信息量大小相同，扇区间由用来标记格式化位的间隙分开 我们用柱面称呼到主轴间距相等的磁道构成的集合

磁盘的存储#

磁盘存储的信息量取决于面密度，即单位面积内可存储的位数；它通常由磁道密度和每条磁道上的线性位密度共同决定

为了简化控制，磁道的扇区数需要尽量保持相等 在技术不发达，面密度比较低的时期，每个磁道的扇区数完全相同，这导致外围的扇区间隙相比内围大了很多，造成了不必要的浪费 现代磁盘使用多区记录的技术，在每个记录区中保存了一段连续的柱面，每个记录区中的磁道扇区数相同，记录区间的扇区数不同。通过多区记录，达到了存储空间和控制难度的平衡

为什么标注1TB大小的硬盘电脑显示只有931GB？ 这是制造商使用的十进制（$1TB = 1000^4$ 字节）与操作系统使用的二进制（$1TiB = 1024^4$ 字节 $\approx 931GiB$）之间的差异。

磁盘的读写#

磁盘中的读/写头连接到外围的传动臂上，通过绕着传动臂转动，进行寻道以定位到某个给定的磁道上，当磁道上的某个扇区旋转到读写头正下方时，就可以对其进行读写操作

对一个扇区的访问时间，取决于一下三个部分： 1.寻道时间：传动臂将读写头移动到指定磁道的时间，这个值取决于读写头之前的位置和传动臂移动的速度 2.旋转时间：等待需要操作的扇区旋转到读写头的正下方，这取决于盘片旋转的角速度和此时目标扇区的位置 3.传送时间：这个扇区从头到尾经过读写头需要的时间，这取决于盘片旋转的角速度

计算的一个示例

可见读写的时间主要取决于寻道时间和旋转时间

磁盘经过封装得到硬盘驱动器，简称硬盘，“硬盘”一词不加修饰时，通常指基于磁盘技术的机械硬盘（Hard Disk Drive, HDD），但需注意与固态硬盘（SSD）区分

逻辑磁盘块#

在逻辑上，我们可以将扇区看成一个大小为$B$的单元结构，使用一个逻辑块号进行寻址，磁盘控制器从操作系统接收这个逻辑块号，将其翻译成一个(盘面，磁道，扇区)的三元组，再对其进行寻址并进行操作

缓存的概念#

存储器的每一层都是下一层更大更慢存储器中数据的一个缓冲空间，该过程被称为缓存

相邻的两层会以相同大小的块作为传输单位，更上层的存储器维护的是更底层存储器中若干块的副本，数据以块为基本单位在两层之间传输。不相邻层次块的大小可能不同

缓存访问概述#

1.缓存命中：当需要访问第$k+1$层中块号为$A$的数据时，先在第$k$层中查找是否保存了该数据，如果存在直接高效访问即可，我们称之为缓存命中

2.缓存不命中：当第$k$层中没有该数据时，就从第$k+1$层读出$A$号块。若能采用某种放置策略，将$A$号块放入一个空块，则就这样放置并访问；否则采取某种替换策略，用$A$号块替换$k$中某个块并访问

3.放置策略与替换策略：为了降低采用策略的代价，这两种策略一般都比较简单。如放置策略就采取简单地将$k+1$层中的每个块都放入在$k$层映射所对应的块中(如对块编号取模得到的数对应的块)，替换策略采用随机替换，最不常使用替换，最近最少使用替换等策略

4.缓存不命中的种类：第一次访问某个块时，缓存中必然没有它，我们称之为冷不命中；当放置策略使多个常用块竞争同一组时，可能导致冲突不命中，如只有4个组的直接映射缓存反复访问第0、4、0、4…号块，缓存就会一直不命中；当需要访问的数据构成的工作集太大，大于缓存能容纳的块数时发生的缓存不命中，称为容量不命中

5.缓存的管理：管理缓存的逻辑可以是硬件，软件，或者是两者的结合

缓存的通用结构#

以在一个m位的系统中进行缓存$k$级读为例

对于一个高速缓存，我们将其分为$S=2^s$个组，每个组内有$E$行，每一行有着一个1位的有效位，$t$位的标记位，以及$B=2^b$个字节的数据块，下标分别为$0, 1, \ldots, B-1$，我们称缓存的数据容量为$C = B \times E \times S$

我们该系统地址有m位，即有$M=2^m$个地址，那么我们用会通过一个长$m$位的数$A$来确定访问的地址 考虑将这个$A$分成三个部分，分别是前$t$位作为标记，中间$s$位作为组索引，最后$b$位作为字节偏移值，满足$m=t+s+b$

通过组索引定位到缓存中的某一组，再并行地与组中的每一行进行比较，当这一行有效位为1且标记和标记位相等时，以字节偏移值为下标读出的这个字节就是需要读出的值

否则每一行都是有效位为0或和标记位不相等，这说明需要读的数不在$k$级缓存中，从$k+1$中重复该步骤，尝试读出该地址的值，在$k$级缓存中进行放入或者替换即可

本质上是地址到一个能唯一确定某个块的三元组的映射，但是完美利用了二进制的性质，发明这个的人真的是天才，计组真的太美了（

补充：为什么不使用更自然的高s位作为组索引，中间t位作为标记，后b位作为偏移值？ 若采用高s位为组索引，那么以连续访问地址为0到$2^{t+b}-1$的数据为例，这些数全都被分到了第一组，没有利用了其它组的，会多次发生缓存不命中，局部性良好的代码反而因此效率降低

缓存的各种类型#

1.直接映射高速缓存：取 $E=1$，即每组只有一行，此时因为只有一行，替换策略极度简化，直接将新的数据块放入该行即可 2.全相联高速缓存：取$E = \frac{C}{B}$，即只有一组，故可以舍去组索引位，理论上可以对每一行并行判断，但是行数过多，成本昂贵，只适合规模小的高速缓存 3.组相联高速缓存：取 $1 < E < \frac{C}{B}$，即有多个组，每组有多个行，可以在组内并行地判断每一行，同时采取随机替换，最不常使用，最近最少使用等替换策略

缓存写#

当需要进行写操作时，若对应地址在$k$级缓存中，即缓存命中，则有以下两种方法： 1.直写：同时更新第$k$层和第$k+1$层中的副本。该方法实现简单，但会增加下层访问流量 2.回写：类似于惰性删除，每一行维护一个初始为0的修改位，写的时候只在第$k$层进行写并将修改位设置为1，直到该行要被替换的时候再将修改后的块写回第$k+1$层。该方法减少了下层写流量，但实现更复杂 当缓存不命中时，同样有两种方法： 1.写分配：从第$k+1$层读入包含写地址的块到第$k$层，再在第$k$层执行写操作，常与回写搭配 2.非写分配：不把该块载入第$k$层，而是直接把写操作传递给第$k+1$层，常与直写搭配

实际的缓存结构#

高速缓存既保存数据(d-cache)，又保存指令(i-cache)，也有数据和指令都保存的统一高速缓存，由于d-cache读写都需要，而i-cache只读，所以分开设计，采用不同的访问模式来优化这两种缓存