存储系统

在讲述这一部分之前，我们先来回顾一下存储器的分类，按照在机器中的地位的不同，存储器被分为两大类：

1. 主存
2. 辅助存储器

按照存取方式的不同，存储器可以被分为三种：

1. 随机存储器
2. 顺序存储存储器：磁带
3. 直接存储器：硬盘

接下来我们引入存储系统的概念：

存储系统是由两个或两个以上，速度，价格各不相同的存储器，用软件或硬件相结合的方法连接起来。

存储器的层次结构

存储系统的用途和要求：

1. 用途：存放程序和数据
2. 要求：容量大，速度快，成本低

程序的局部性原理：

1. 时间局部性：在一段时间内，最近被访问过的时间和数据很有可能被再次访问
2. 空间局部性：程序和数据往往几种在一个小的存储区内
3. 访问顺序：指令顺序执行的可能性比转移执行大

问题的解决办法

选用生产成本不同、容量不同、存取速度不同的存储介质组成一个存储系统，每种介质处于不同的地位，发挥不同的作用，充分发挥各自的优点，从而达到最优的性能价格比。

层次之间应该满足的原则

大多数的机器都采用三层存储结构：

Cache-主存-辅存

1. 一致性原则：处于不同层次存储器的同一个信息应该保存相同的值
2. 包含性原则：处于内层的信息一定被包含在外层的存储器中，反之不成立

高速缓冲存储器（cache）

为了弥补主存速度的不足，引入cache来提高访问数据和程序的速度

cache的基本原理

CPU在某一段时间所要访问的程序和数据事先从主存中调入cache中，当CPU需要读取这些数据的时候，可以直接到cache中去取，提高的存取的速度。

**cache具有透明性。**cache的存在不需要系统辅助软件的干预，用户不必关心cache的存在，所以cache是透明的。

三层存储系统中的数据通路

主存数据和cache数据保持一致性的方法

1. 写回法：

   指向cache中写入，并用标志位加以著名，直到该数据被从cache中替换出来时才写入主存

2. 写直达法：

   Cache中的内容改变时，内存中的相应单元也应该相应地改变，如果要修改的数据不在cache中，则不写入cache，直接写入主存

Cache的组织

地址映像

为了把信息放到cache中，必须要以某种函数的方式将地址映像到cache中

执行主存地址到cache地址的这一过程叫地址变换。

有三种基本的地址映像方式：

1. 直接映像
2. 全相联映像
3. 组相联映像

cache的容量是远远小于主存容量的，所以要采取一种将cache地址映射到主存地址的方法，我们假设主存的地址有n位，其中我们将主存分块，块地址m位，块内地址b位，而我们同样将cache分成块，cache地址较小，块地址c位，块内地址b位，块内地址两者相同，我们给cache中的每个块一个标记，通过标记加c（块地址）分辨cache对应的主存的哪个块

直接映像

直接映像的方式的实现比较简单，通过一个公式进行映射：
$$
j = i{,}mod{,}2^c
$$
其中j为cache的块号，i为主存的块号，通过这种方式进行映射有以下优缺点：

1. 优点：实现简单
2. 缺点：主存的字块只会映射到唯一的cache块，使得cache的利用率不是那么充分，映像命中率

全相联映像

在全相联映像中，主存的每一块都有可能被映像到cache中的任何一个字块上，根据映像规则，需要将主存内容放入cache的时候会使用一个空闲的cache，这对其标记没有要求，并且比较时时通过m位的标记进行比较

访问cache时，需要cache的全部标记和主存地址相同才能确认数据在cache中

全相联映像的优缺点：

1. 优点：灵活，cache得到了充分的利用
2. 缺点：标记位数增加，cache标记容量增大，成本增大

组相联映像

组相联映像吸取了全相联映像和直接映像的优点，将映像分成2^c个组，组内有2^r个块，所以特点如下：

1. 组内时全相联映像
2. 组间直接映像

公式如下：
$$
j = (i{,}mod{,}2^c)*2r+k
$$

替换方法

1. FIFO
2. LRU
3. RAND（随机替换法）

多层次cache

哈弗结构

把cache分为数据cache和指令cache

提高了cache的效率，减少了取指令和取数据的冲突

多层次cache

cache 集成在芯片内，片内比片外 cache 速度快，但容量小

二级 cache：第一级 cache 在片内，第二级 cache 在片外，用总线相联。

MESI协议

因为cache一致性问题，提出以下协议：

1. M-修改：某一 cache 字块中的数据被修改，仅在本 cache 中的数据是正确的。
2. E-排他：本 cache 字块中的数据与主存的数据相同，但不存在于其他 cache 中。
3. S-共享：本 cache 字块中的数据与主存的数据相同，而且可存在于其他 cache 中。
4. I-无效：本 cache 字块中的数据无效。

cache的性能评价

命中率

在一个程序执行期间，设Nc表示Cache 完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率。则有:
$$
h=\frac{N_c+N_m}
$$
命中率跟程序、 cache容量、组织方式、块的大小有关。

存储系统平均存取时间

cache存取时间为tc ，命中率为h，主存的存取时间为tm则系统平均存取时间为：
$$
t_a = h*t_c+(1-h)*t_m
$$

存储系统访问效率

$$
e=t_c/t_a
$$

虚拟存储器

虚拟存储器是指主存-辅存层面，使计算机具有辅存的容量，并接近于主存的速度和价位比

虚拟存储器的目的：用户可以自由编程，完全不必考虑程序在主存是否装得下，以及这些程序将来在主存中的实际存放位置

虚拟存储器由主存和联机辅存组成，以透明的方式给用户提供一个比主存空间大的多的程序地址空间。

虚地址：用户编程的地址成为虚地址或逻辑地址

实地址：实际主存单元的地址称位实地址或物理地址

简要工作原理：平时程序和数据都保留在辅存，当程序运行时，将即将运行的部分调入主存

段式存储器

定义：把主存按段分配的存储管理方式称为段式管理。

段式存储器的实现

段的长度不固定，所以存在一些空间的浪费，在实际实现上，我们使用一个段表，段表中有一些关键字段：

1. 短号：段的编号
2. 段起点：段的起始位置
3. 装入位：是否被装入
4. 段长：段的长度

CPU使用一个段表基址存储器，要计算段的地址，需要将基址加上段号就得到了程序段的段表地址，如果需要的段在主存中，则把段表相加给出的该段的起始地址与段内偏移相加即可得到实地址

段式管理的优缺点

优点：

1. 段的逻辑独立性强，便于共享
2. 便于实现信息保护

缺点：

1. 地址变换时间长
2. 主存利用率低
3. 辅存管理难度大

页式存储器

将主存空间和虚存空间划分成若干个大小相等的页。并将主存按页分配的存储管理方式成为页式管理。

页式存储器的实现

页式存储器用一张存放在主存中的页表来实现，其中记录着程序虚页调入主存时，被安排在主存中的位置

页表地址由页表起始地址加上虚页号得到，实际地址由页号和页内偏移拼接得到

块表

把页表的最活动部分放到快速存储器中，组成一个表，称位快表。块表由硬件组成，通常称位转换旁路缓冲器。

页式管理的优缺点

优点：

1. 主存利用率高
2. 页表字段少
3. 地址变换速度快
4. 辅存管理容易

缺点：

1. 页的独立性不高
2. 页表长

段页式存储器

将程序按其逻辑结构分段，每段再划分为若干大小相等的页。虚存和实存之间以页为基本传送单位，每个程序对应一个段表，每段再对应一个页表。

段页式管理具有段式管理和页式管理的优点。

存储管理部件

特点：

1. 允许用户比主存空间大的多的空间来访问主存
2. 每次访问都需要进行虚实地址的转换

相联存储器和存储保护

按所存数据字的全部内容或部分内容进行查找的存储器

按照内容比较查找

相联存储器的基本组成

1. CR：比较数寄存器
2. MR：屏蔽寄存器
3. SRR：查找结果寄存器
4. WSR：字选择寄存器

存储保护

存储保护包含两个内容：存储区保护和访问方式保护

存储区保护

1. 页表保护

   每个程序都有自己的段表和页表，无论地址怎么出错，错误也就发生在该程序的段页中，如果在地址转换中出现错误，则此保护方式无效

2. 键方式

   给主存的每一页分配一个存储键，用户访问存储键，如果两键相符，可以访问主存

3. 环保护

   对程序的重要性和影响程序进行分层，赋予环号，如果要转换页的时候，如果现行环号小于或等于要转去的那个页，则放行，否则交给操作系统处理

访问方式保护

对主存信息的三种使用方式： R（读）、W（写）、E（执行）。 这些访问方式保护通常作为程序状态寄存器的保护位，并且和区域保护结合起来实现。