【体系结构 四 存储结构】

1.层次结构

存储器的三个主要指标：

• 容量
• 速度
• 价格

1.1 多层存储层次

整个存储系统想要达到的目标为：从CPU来看，该存储系统的速度接近M1的速度，而容量和每位价格都接近Mn的容量和价格

实现目标，必须做到存储器若越靠近CPU，则CPU对它的访问频率越高，而且最好大多数的访问都能在M1完成。

局部性原理：早在 1968 年，Denning.P就曾指出：
程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。
他提出了下述几个论点：

• 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。该论点也在后来的许多学者对高级程序设计语言(如 FORTRAN语言、PASCAL 语言)及 C 语言规律的研究中被证实。
• 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过 5。这就是说，程序将会在一段时间内都局限在这些过程的范围内运行。
• 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。
  局限性还表现为下述两个方面：
  • 时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。
  • 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。存储器中，如磁带上，这样做还能降低存储价格

1.2 “Cache-主存” && “主存-辅存”

	Cache-主存	主存-辅存
目的	为了弥补主存速度的不足	为了弥补主存容量的不足

Cache:高速缓冲存储器

• 速度快 容量小，每位价格高

1.3 存储层次的四个问题

问题	方法
当把一个块调入高一层（靠近CPU）存储器时，可以放在哪个位置	映像规则
当所要访问的块在高一层存储器中时，如何查找该块	查找算法
当发生失效时，应替换哪一块	替换算法
当进行写访问时，应该进行哪些操作	写策略

2.Cache

• Cache是按照块进行管理的。
• Cache和主存均被分成大小相同的块。
• 信息以块为单位进行调入Cache。
• 相应地，Cpu的访存地址被分割成两部分：块地址和块内位移
  • 主存块地址： 查找该块在Cache中的位置
  • 块内位移：确定所访问的数据在该块中的位置

2.1 映像规则

当把一个块调入高一层（靠近CPU）存储器时，可以放在哪个位置

• 直接映射:(块地址)MOD(cache中的块数),每个块只能出现在唯一位置上

• 

• 全相连映射:一个块可以放置在cache中的任意位置上

• 

• 组相连:(块地址)MOD(cache的组数), 一个块首先被映射到一个组中,然后它可以被放置在组中的任何一个块中

• 

2.2 查找算法

当所要访问的块在高一层存储器中时，如何查找该块

查找目录表：
  Cache中设置有一个目录表，该表共有M项，每一项对应于Cache中的一个块，用于指出当前该块中存放的信息是哪个主存块的（可能有多个主存块映像到该Cache中）。实际上是记录了该主存块的块地址的高位部分，称为标识（tag）。每个主存块能唯一地由其标识来确定。
  根据映像规则的不同，一个主存块可能映像到Cache中的一个或多个Cache块位置（候选位置）。当CPU访问该主存块时，必须且只需要查找它的候选位置所对应的目录表项（标识）。如果有与所访问的主存块相同的表示，且有效位为1，则它所对应的Cache块即是要找的块。
  同时，为了保证速度，对各个候选位置的标识的检查比较，应并行进行。

2.3 替换算法

由于主存中块比Cache中块多，所以所要从主存调入一个块到Cache时，会出现该块所映像到的一组（或一个）Cache已经完成被占用的情况。这时需要强迫腾出其中某一块，以接纳新调入的块，应该替换哪一块呢？

直接映射:直接替换不命中的块
在组相联与全相联中需要在多块中进行选择,主要的替换算法主要有如下四种：
(1) 随机替换,产生伪随机数块号
(2) LRU，记录块的访问次数,替换长时间没有被访问的
(3) FIFO，最早进入cache的块被替换
(4) OPT,优化算法

2.4 写策略

当进行写访问时，应该进行哪些操作

只有在标志位有效而且地址命中时，块才能修改。检查标志位不能与写操作同时进行.写操作比读操作花费时间更长.

Cache写策略:

• 写直达:执行写操作时，不仅仅把信息写入Cache中相对应的块，而且也写入下一级存储器中相对应的块
• 写回法:信息写入Cache想对应的块，该块只有在被替换时，才被写回主存。

为了减少在替换时块的写回，常采用“污染位”标志，为每一块Cache的每一块设置一个"污染位"（设置在与该块对应的目录表项中），用于指出该块是脏的（被修改过）还是干净的（没有被修改过）。替换时，若被替换的块时干净的，则不必写回下一级存储器。

写回法	写直达
速度快，写操作能以Cache存储器的速度进行	易于实现
对于同一单元的多个写最后只需一次写回下一级存储器	下一级存储器中的数据总是最新的
有些写只达到Cache不到主存，使用存储器频带较低

我们需要利用写回法来减少访问存储器的通信量，又希望通过写直达法来保证存储器层次结构中cache和低层存储器的数据一致性.

写直达法:

• 处理器的操作必须等待写操作完成，此时处理器称为写停顿，
• 减少写停顿的策略是写缓存技术，允许处理器把数据写入到缓冲区之后立即继续工作.

写访问并不需要用到所访问单元中原有的数据。所以在发生写失效时，是否调入相应的块，有两种选择

• 写分配:写缺失发生时，内存的块被读到cache中，然后执行上个写命中时的操作
• 不按写分配:写缺失发生时，仅修改低层存储器的该块，而不将该块取到cache中

3. 主存

主存是数据输入的目的地，也是数据输出的源发地。既被用来满足Cache的请求，也被用作I/O接口。

---

主存性能主要关注：延迟和带宽

4. 虚拟存储器

4.1 基本原理

虚拟存储器(VirtualMemory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。

虚拟存储器的分类	实现方式	备注
页式	把空间划分成大小相同的块	对空间的机械划分
段式	把空间划分成可变长的块	程序逻辑意义划分
段页式	每段分成若干个页面，段不必作为整体全部一次调入主存，而是可以以页面为单位部分调入

问题	方法
映像规则	操作系统允许将块放在主存的任一位置，采用全相联映像
查找算法	页表和段表
替换算法	LRU
写策略	写回策略

4.2 快表TLB

页表一般很大，一般放在主存中，每次访问都需要引起对主存的两次访问，一次是读取页表项，一次是访问数据本身。 在实际应用中性能受影响太大。因此一般采用快表来解决这个问题。

TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项，其内容是页表部分内容的一个副本。
只有在偶尔在TLB不命中时，才需要去访问内存中的页表。

TLB的项与Cache中的项类似，也是由两部分构成：标识和数据。

• 标识中存放了虚地址的一部分
• 数据中存放物理页帧号、有效位、存储保护信息、其他辅助信息等。

为了使得TLB的内容与页表保持一致，当修改页表中某一项时，操作系统必须保证TLB中没有该页表的副本。