体系结构要点知识系列三：存储体系

一、存储体系

存储体系就是让构成存储系统的几种不同的存储器(M₁ ~M_n )直接配上付诸软硬件，让存储层次的等效访问速度是接近于M₁的，容量是M_n的，每位价格接近于M_n的。从应用程序员来看，它们在逻辑上是一个整体，应用程序员可用机器指令的地址对整个程序统一编址，称该地址为虚地址(程序地址)，而把实际主存地址称为实地址(实存地址)。

虚拟存储器只能适用于多道程序(多用户)环境，而Cache存储器既可以是单用户环境，也可以是多用户环境。

存储器容量S_m = W * l * m。W为存储体的字长(单位是位/字节)，l为存储体的字数，m为并行工作的存储体数。

存储器频宽B_m 是存储器可提供的数据传送速率。最大频宽B_m是存储器连续访问时的频率。单体的B_m= W/T_m (T_m为存储周期，连续启动一个存储体所需用的时间间隔)；m个存储体并行的最大频宽是B_m= W*m/T_m 。

对未来被访问信息的地址的预知能力是存储体系构成的关键因素。这种预知的可能性是基于计算机程序具有局部性，包括时间和空间的局部性。故而访存局部性原理是存储体系设计的基础。

二、页面替换算法

替换算法一般是通过用典型的页地址流模拟其替换过程，再根据所得到的命中率的高低来评价其好坏。影响命中率的因素：替换算法、地址流、页地址、分配给程序的主存页数、页面大小、主存容量。一般分配给程序的主存页数越多，虚页装入主存的机会越多，命中率也越高，但是否提高还和替换算法有关。

随机算法：用随机数发生器产生要被替换页的页号。该算法反映不了程序局部性，使主存命中率很低。

先进先出算法FIFO：选择最早装入主存的页作为被替换的页。在操作系统为主存管理所设的主存页面表中给每个实页配一个计数器字段，每当一页装入主存时，让该页的计数器清0，其它已装入主存的那些页的计数器都加1，需要替换时，计数器值最大的页的页号就是最先进入主存而现在准备替换掉的页号。该算法不一定能正确地反映出程序的局部性。使用该算法时，主存页数增加，命中率可能反而下降。

近期最少适用算法LRU：选择近期最少访问的页作为替换页。该算法比较能够正确地反映程序局部性。相似的还有近期最久未访问算法，充分利用了程序局部性原理。使用LRU算法时，主存页数增加，命中率增加，至少不会下降。

优化替换算法OPT：该算法为堆栈型算法。堆栈型算法的特点：命中率随分配给该道程序的主存页数n的增加而单调上升，至少不会下降。

备注：

主存页面表是OS为实现主存管理设置的，每一行用来记录主存中各页的使用状况，它存在于主存，整个主存中只有一个。页表用于存储地址映像关系和实现地址变换的，是对用户程序空间而言，每道程序都有一个。

三、快表和慢表

快慢表是用来提高虚存等效访问速度的措施。用快速硬件构成比全表小得多的目录表存放当前正用的虚实地址映像关系，我们称这部分目录表为快表；将原先存放全部虚实地址映像关系的表称为慢表。

快表只是慢表中很小的一部分副本，所以快表和慢表也构成了二级存储体系。为了提高快表的命中率和查表速度，可以用高速按地址访问的存储器来构成更大容量的快表，并用散列(Hashing)方法实现按内容查找。

主存命中率也与所有的页面调度策略有关，页面调度方式有：分页方式、请求页式、预取式+请求页相结合。大多数虚拟存储器都采用请求式调页，仅当页面失效时才把所需页调入主存，针对程序存在局部性，可改用预取工作区调度策略。

四、cache存储器的等效访问速度和命中率的关系

设t_c 为Cache访问时间，t_m为主存周期，H_c为访cache的命中率，则cache存储器的等效存储周期为：t_a = H_c *t_c +(1-H_c)*t_m。

与虚拟存储器不同的是一旦cache不命中，主存与CPU经直接通路传送，所以CPU对第二级的访问时间是t_m，而不是调块时间再加一个访cache时间。

采用cache存储器比之处理器直接访问主存，其等效访问速度提高的倍数为：

e =t_m / t_a= t_m / [H_c t_c +(1- H_c)* t_m] = 1/[1 - (1 - t_c / t_m)* H_c]