信息安全系统设计基础第七周学习总结

一、课本内容

1.存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。

2.随机访问存储器

• SRAM（静态）：高速缓存存储器。将每个位存储在一个双稳态的存储器单元里面。（每个单元用一个六晶体管电路来实现；其属性是可以无限期保持在两个不同的典雅配置或者状态之一，其他的任何状态都是不稳定的）
• DRAM（动态）：将每个位存储为对一个电容的充电（这个电容很小）。存储单元对干扰（如光线、噪音等）很敏感；当电容的电压被扰乱之后就永远不会恢复。优势是密集度低，成本低。

3.关于DRAM

• DRAM的芯片中的单元被分成d个超单元，每个超单元都由w个DRAM单元组成。一个d*w的DRAM总共存储了dw位的信息。超单元被组织成一个r行c列的长方形阵列，这里rc = d。信息通过引脚的外部连接器流入和流出芯片。
• 每个DRAM芯片被连接到某个称为存储控制器的电路，这个电路可以一次传送w位到每个DRAM芯片或者依次从每个芯片传出w位。电路设计者将DRAM组织成二维而不是线性数组的一个原因是降低芯片上地址引脚的数量。
• DRAM芯片包装在存储器模块中，它是插到主版的扩展槽上的。

4.非易失型存储器：即使在关电后，也仍然保存着它们的信息；称为ROM。包括：

• PROM：只能被编程一次。
• 可擦可写编程ROM（EPROM）：被擦除和重写的次数可以达到10^3次
• 电子可擦除PROM（EEPROM）：能够被编程的次数可以达到10^3次。
• 闪存：基于EEPROM。基于此的磁盘驱动器称为固态硬盘 存储在ROM设备中的程序通常称为固件；当一个计算机系统通电之后，它会运行存储在ROM中的固件

5.数据流通过总线的共享电子电路在处理器和DRAM之间来回；包括读事务（从主存到CPU）和写事务。总线是一股并行的线，可以携带数据、控制信号和地址（数据总线，地址总线，控制总线）。

6.I/O桥、芯片组、主存

前两者之间通过系统总线连接；后两者通过存储器主线连接。在读写事务中，均是分三步完成。

7.磁盘结构

• 磁盘是保存大量数据的存储设备；但读取速度慢。
• 磁盘有若干盘片组成，密封在容器（磁盘驱动器）内；每个盘片的两个表面都有一组被称为磁道的同心圆；每个同心圆由一些间隙分隔成一组等容量磁道（通常是512字节），间隙中存储的是标识扇区的格式化位。
• 柱面：所有盘片表面到主轴中心距离相等的磁道的集合

8.磁盘容量

• 容量是指一个磁盘上可以记录的最大位数。决定因素：
• 记录密度；磁道密度；面密度（前两者乘积）

9.磁盘操作

• 读写通过连在传动臂一段的读写头完成；可以定位在盘面上的任何磁道上；这样的机械运动称为寻道。每个盘面对应一个读写头。所有的读写头一致行动，即在任意时刻，所有的读写都发生在同一盘面上
• 对扇区的访问主要有三个部分：
  • 寻道：将读写头定位到包含目标扇区的磁道上。Tseek取决于它以前的位置和传动臂在盘面上的移动速度。时间通常为3——9ms。
  • 旋转：一旦读写头定位到了期望的磁道，驱动器等待目标扇区的第一个位旋转到读写头下面。平均旋转时间是最大时间（等磁盘旋转一圈）
  • 传送：驱动器开始写或者读扇区的内容；时间长短取决于旋转速度和每条磁道的扇区数目。平均时延为 Tavg=1/RPM1/(平均扇区数/磁道)60secs/1min
  • 补充：访问一个磁盘扇区的512字节的主要时间在于寻道和旋转延迟。访问时间：磁盘>DRAM>SRAM

10.逻辑磁盘块

目的是为了向操作系统隐蔽磁盘的结构复杂性。磁盘将其呈现为一个有B个扇区的逻辑块的序列；磁盘中有一个固件设备——磁盘控制器，维护者逻辑酷爱号和实际磁盘扇区之间的映射关系。操作系统是以逻辑块号为单位进行寻址操作的。

11.（I/O）设备是通过I/O总线（例如intel的PCI）连接到CPU和主存的。虽然它比系统总线和存储器总线要慢，但是可以容纳种类众多的第三方I/O设备。比如：通用串行总线；图形卡；主机总线适配器

12.CPU使用一种称为存储器映射I/O的技术来向I/O设备发出命令的。在使用其的系统中，地址空间中，有一块地址是为与I/O设备通信保留的；叫做I/O端口

13.局部性

• 计算机程序倾向于引用邻近于其他最近引用过的数据项的数据或其本身；这种倾向性，被称为局部性原理。包括：时间局部性，空间局部性。有良好局部性的程序比局部性差的程序运行的更快。
• 体现：在硬件层，局部性原理允许计算机设计者通过引入称为高速缓存器的小而快的存储器来保存最近被引用的指令和数据项；在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被使用的磁盘块。
• 重复引用一个变量的程序具有良好的时间局部性；对于取指令来说，循环具有良好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

14.存储器层次结构——缓存

• 存储器层次结构的中心思想是：对于每个k，位于k层的更快更小的存储设备作为位于（k+1）层的更大更慢的存储设备的缓存。
• 第（k+1）层的存储器被划分成连续的数据对象片，称为块；数据总是以块大小为传送单元在相邻两层之间来回拷贝的；在任何时刻，第k层的缓存包括第（k+1）层块的一个子集的拷贝。

15.缓存命中及缓存不命中

• 缓存命中：当程序需要第(k+1)层的数据对象d的时候，首先会在第k层找d；如果d刚好缓存在第k层，那么就叫做缓存命中；反之，不命中
• 如果缓存不命中，那么第k层缓存就从第（k+1）层取出包含该数据的块，有可能会覆盖现有的块。覆=决定替换哪个块是由缓存的替换策略来控制的；例如，一个具有随机替换策略的缓存会随机选择；而LRU替换策略会选择被访问时间距今最远的块

16.缓存管理

在每一层上，某种形式的逻辑必须管理缓存；可以是硬件也可以是硬件、软件的结合。

16.高速缓存存储器（S,E,B,m）

• 作用：连接CPU和主存
• 每个存储器地址有m位，形成M=2^m个不同地址。这m位被划分成t个标记位、s个组索引位和b个块偏移位。
• 这样一个机器的高速缓存被组织成S=2^s个高速缓存组的数组；每个数组包含E个高速缓存行；每行由一个B=2^b字节的数据块、一个有效位（指明这个行是否包含有效信息）、t=m-(b+s)个标记位（唯一标识存储在这个高速缓存行中的块）组成

【理解：从高向低来看，M=2^m个地址平均分给S=2^s个组，每组获得2^(m-s)个地址，即（m-s）位；减去t位用于标记块，还有2^(m-t-s)个地址可以表示一个块，也就是说，一个块可以有2^(m-t-s)个字节的信息】 - 高速缓存的大小为C=SEB

17.直接映射高速缓存

• 高速缓存确定一个请求是否命中，然后抽搐被请求字的过程，分为：组选择，行匹配，字抽取
• 组选择：从w的地址中抽取组索引；这些位被解释成对应于一个组号的无符号整数
• 行匹配：对于直接映射高速缓存，行匹配是容易而且快的；因为每个组只有一行
• 字匹配：块偏移提供的是这个字的第一个字节是从哪个位置开始的

18.根据P413图6-32，可以得出：

• 标记位和索引位连起来唯一地标识了存储器中的每个块
• 当储存块多于缓存组（每组一行）的时候，多个块映射到一个组；这样的块由标记位唯一标识（可能会产生冲突不命中）

二、练习题筛选

1.P391 6.2

【计算这样一个磁盘的容量。它有2个盘片，10 000个柱面，每条磁道平均有400个扇区，每个扇区平均有512个字节】 磁盘容量 = 512字节/扇区400扇区/磁道10 000磁道/表面2表面/盘片2盘片/磁盘 = 8 192 000 000 字节 = 8.192GB

2.P393 6.3

【估计访问下面的一个磁盘上的一个扇区需要的时间（以ms为单位）。旋转速率：15000RPM；Taveseek = 8ms;每条磁道的平均扇区数：500】 访问时间 = Taveseek+Taverotation+Tavetransfer = 8ms+0.51/15000RPM60secs.min1000ms/s+1/15000RPM1/50060secs/min1000ms/s=8ms+2ms+0.008ms=10.008ms

3.P394 6.4

【假设1MB的文件由512字节的逻辑块组成，存储在有如下特性的磁盘驱动器上（旋转速率：10 000RPM，Taveseek=5ms，平均扇区/磁道 = 1000）。

（1）最好的情况：给定逻辑块到磁盘扇区的最好的可能的映射（即，顺序的），估计读这个文件需要的最优时间

（2）随机的情况：如果块是随机地映射到磁盘扇区的，估计读这个文件需要的时间】

首先明确：1MB=2^20字节，即数据存储在2000个逻辑块中；对于磁盘，Taverotation=0.51/10000RPM60secs/1min*1000ms/s=3ms

则：（1）T=Taveseek+Taverotation+2Tmaxrotation=5ms+3ms+26ms=20ms

(2)在这种情况下，块被随机的映射到扇区上，读2000块的每一块都需要Taveseek+Tavgrotation=8ms。所以读这个文件的总时间为T = 8ms*2000=16000ms=16s

4.P404 6.8

【改变下面函数中的循环顺序，使得它以步长为1的引用模式扫描三维数组a】

int sumarray3d(int a[N][N][N])
{
    int i,j,k,sum=0;
    for(i=0;i<N;i++)
    {
        for(j =0;j<N;j++)
        {
            for(k=0;k<N;k++)
            {
                sum+=a[k][i][j];
            }
        }
    }
    return sum;
}

只需要对三层嵌套循环体的顺序进行调整即可：

int sumarray3d(int a[N][N][N])
{
    int i,j,k,sum=0;
    for(i=0;k<N;i++)
    {
        for(j =0;i<N;j++)
        {
            for(k=0;j<N;k++)
            {
                sum+=a[k][i][j];
            }
        }
    }
    return sum;
}   

5.P415 6.11

【在前面dotprod的例子中，在我们对数组x做了填充之后，所有对x和y的引用的命中率是多少？】 在填充了之后，对于x和y数组，只有在引用第0个和第4个元素的时候发生不命中。因而命中率为75%

6.P415 6.12

【一般而言，如果一个地址的高s位被用作组索引，那么存储块连续的片会映射到同一个高速缓存组。

1.每个这样连续的数组有片多少个块？

2.考虑下面的代码；它运行在一个高速缓存形式为（S,E,B,m）=（512，1，32，32）的系统上

int array[4096]
for(i=0;i<4096;i++)
    sum+=array[i];

在任意时刻，存储在高速缓存中的数组块的最大数量是多少？】 1.2^t个块

【这道题揭示了我们为什么不用高s位做组索引；这样的话，前2^t个地址都映射到一个组中（详细解释见下）】

2.如果地址的前s=9位做组索引，那么之后的t=18位做标记位；高速缓存容量是512个32字节的块。数组只需要（4096*4）/32=512个块；这些块均会被映射到组0中（数组是连续存放的），因此，在任何时刻，高速缓存中只能保存一个数组块（尽管它的容量可以存放数组）。这样极大降低了高速缓存利用率。

疑问

1.P383

有些系统也使用纠错码，其中计算机的字会被多编码几个位（例如，32位的字可能用38位来编码），这样一来，电路可以发现并纠正一个字中任何单个的错误位。 并不明白，这样前后有什么因果关系？

2.P402

另一方面，因为sum是标量，对于sum来说，没有空间局部性。 为什么标量没有空间局部性（如果一个存储位置被引用了一次，那么程序很可能在不远的将来被引用附近的一个存储器位置）

3.P403

图6-20中

int sumaraycols(int a[M][N])
{
    ……
    for(i=0;i<N;j++)
        for(j=0;j<M;j++)
            sum+=a[i][j];
    ……
}

这里，为什么是"i<N","j<M"？是不是应该对调一下变成"i<M"，"j<N"？