安徽大学 存储系统

《安徽大学 存储系统》由会员分享，可在线阅读，更多相关《安徽大学 存储系统（118页珍藏版）》请在金锄头文库上搜索。

1、第2章 存贮系统2.1存贮体系的形成与性能 2.2虚拟存贮 2.3高速缓冲存贮器Cache 2.4主存保护1本章重点：段页式和页式虚拟存贮器的原理；页式虚拟存 贮器的地址映像；LRU/FIFO/OPT替换算法进行页 面替换的过程模拟；LRU算法对页地址流的堆栈 处理模拟及性能分析；Cache存贮器的直接和组 相联地址映像；LRU替换算法的硬件实现及替换 过程模拟；Cache存贮器的性能分析等。 本章难点：段页式和页式中虚实地址的计算；各种页面替 换算法的模拟和页面命中率的计算；Cache组相 联映像和块替换算法的模拟。 分类信息 新闻 2.1 存贮体系的形成与性能 2.1.1发展存贮体系的必要

2、性1.存贮器的性能要求1)大容量2)高速度3)低价格 分类信息 新闻 2.容量SM=W l mW：存贮体的字长，单位为bit或Byte。l：每个存贮体的字数。m：并行工作的存贮体的个数。3.速度从下面三个方面来描述：1)访问时间TATA是存贮器接到访存到信息被读到数据总线上所需的时间。是确定CPU与存贮器时间关系的重要指标。 分 类信息 新闻 2)存贮周期TMTM是连续启动一个存贮体所需要的时间间隔。 一般来说总比TA大。3)存贮器频宽是指存贮器可以提供的数据传送率，一般用每 秒钟所传送的信息位数来衡量。a)最大频宽BM(极限频宽)是存贮器连续访问时能提供的频宽。单体： BM =W/TMm体并

3、行工作：BM =mW/TMb)实际频宽实际频宽小于最大频宽BM。 分 类信息 新闻 2.价格可以用总价格C或每位价格c来表示。具有SM位的存贮器每位价格c=C/SM。其中包括了存贮器本身的价格和为该存贮器操作所必须的外围电路的价格。 5.结论由于存贮器的价格、速度和容量的要求是矛盾的，为了同时满足三方面的要求，在一个完整的存贮体系中，必须采用不同工艺的存贮器，使得信息以各种方式分布于不同的存贮体。 分 类信息 新闻 比如：主存 当前活跃的信息，快，少辅存 暂时不用的信息，慢，多虚存 swap从速度来说，主存远远跟不上CPU的要求，为了弥补这一差距，特引入并行和重叠技术，构成并行主存系统，但这种

4、并行主存的方法提高频宽是有限的，因此还需从系统结构入手，发展存贮体系。 分 类信息 新闻 2.1.2并行主存系统频宽的分析1.类型1)单体单字存贮器字长W与CPU字长W相同,一次访问一个存贮器字,主存最大频宽BM =W/TMW位读出寄存器地址寄存器单体单字存贮器 分 类信息 新闻 2)单体多字存贮器字长等于m个CPU字,BM =mW/TMW位W位W位W位地址寄存器单体多字(m=4)存贮器W位单字长寄存器 分 类信息 新闻 3)多体单字交叉总线控制地址寄存器0 地址寄存器1地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件)CPUIOP多体(m=4)交叉存贮器 分 类信息 新闻 a)存贮

5、器字长等于m个CPU字，BM =mW/TM。实际 频宽大于单体多字。单体多字：并行读出的m个字要地址顺序的存 在于同一主存单元。多体单字：m个CPU字地址不必顺序存放，只 要不发生冲突。b)编址模式Mj体的编制模式为：m i+j；其中I=0，1， ，l-1，表示第i个字；j=0，1， ，m-1，表示第j个分体 ； 分 类信息 新闻 m模 单体多字：一个主存包含的CPU字数多体单字：分体体数模体地址编址序列二进制地址码末二位状态 M0M1 M2M30,4,8, 12, ,4i+0, 1,5,9, 13, ,4i+1, 2,6,10, 14, ,4i+2, 3,7,11, 15, ,4i+3, 0

6、0 01 1011地址的模4低位交叉编址 分 类信息 新闻 4)多体多字交叉多个存贮体，每个存贮体有CPU字。上述能并行读出多个CPU字的单体多字和多体 单字或多体多字的交叉存贮主存系统统称为并行 主存系统。 分 类信息 新闻 2.分析提高m值，可以提高主存系统的最大频率，但 并不能线性提高实际频率。原因：1)模m越高，存贮器数据总线越长，导致传输延迟增加；2)系统效率问题，对于顺序取指，效率可以 提高m倍，但遇到转移指令，效率就会下降 。 分 类信息 新闻 3.模型分析对于m个独立分体的主存系统，处理机发出一串地址为A1,A2, Aq的访存申请队，在每个主存周期到来前，申请队被扫描，截取从队

7、头起的A1,A2, Ak的申请序列。申请序列是个在要求访存申请的k个地址中，没有两个或两个以上的地址处于同一分体中的最长序列。显然k表示可以同时访问的分体个数的随机变量，不大于m ，系统效率取决于k的均值B，其值越大，可访问的分体个数越多，系统效率越高。 分 类信息 新闻 1)数学模型设p(k)表示申请序列长度为k的概率密度函数， 其中k=1,2,m。则k的均值B为B=kp(k)B实际就是每个主存周期所访问的平均字数。而 p(k)与程序的状态密切相关，特别是指令转移概 率p，它定义为给定下条指令地址为非顺序地址 的概率。因此p(k)=(1-p)k-1p， 1k2nv，使得页表中绝大部分行中实页

8、号nv字段及其它字段都不再有用了，这就会大大降低页表的空间利用率 。 分 类信息 新闻 c)解决办法将页表中装入位为0的行用实页号nv字段存放 该程序此虚页在辅存中的实地址，以便调页时 实现用户虚页号到辅存实地址的变换。相联目录表法:把页表压缩成只存放已装入主 存的那些虚页(用基号b和Nv标识)与实页位置 (nv)的对应关系。这样该表最多为2nv行，简称 为目录表法，采用按内容访问的相联存贮器构 成。如下图： 分 类信息 新闻 基号用户虚页号页内位移 某用户虚地址基号用户虚页号实页号其它 信息 目录表(存在相联存贮器中)相联比较查找到目录表法NvbNrnvnvnr(Nr)npb+Nv2nv行

9、分 类信息 新闻 d)相联存贮器在一个存贮周期内能将给定的Nv同时与目录表的全部2nv个单元对应的虚页号字段内容比较进行相联查找。如有相符的即相联查找到时，表示此虚页已装入主存，该单元存放的实页号nv就是此虚页所存放的实页位置，将其读出拼接上Nr就可形成访存实地址np；如无相符的即相联查找不到 ，表示此虚页未装入主存，发生页面失效，请求从辅存中调页。由此可见，采用目录表法不用设置装入位了。 分 类信息 新闻 6)虚页的调入当发生页面失效时，要想把该道程序的虚页调入主存，必须给出该页在辅存中的实际地址 。为了提高调页效率，辅存一般是按信息块编址的，且块的大小等于页面大小。以磁盘为例，辅存实(块)

10、地址格式Nvd为：这样就需要将多用户虚页号Nv变换成辅存实地址Nvd 。磁盘号柱面号磁头号块 号N 分 类信息 新闻 外页表:存放用户虚页号Nv与辅存实地址Nvd的 映像关系，用于外部地址变换。内页表:存放用户虚页号Nv与主存实页号nv的映 像关系，用于内部地址变换。由于虚拟存贮器的页面失效率很低，很少调用外页表进行地址变换，因此外页表存放在辅存中 ，当某道程序初始运行时，才把外页表的内容转录到已建立内页表的实页号地址字段中，这也是前述当内页表装入位为0时让实页号地址字段改放该虚页在辅存中的实地址的原因。而且对外页表速度要求低，可以用软件实现。如下图： 分 类信息 新闻 磁盘号柱面号 磁头号

11、块号Nvd多用户虚地址辅存地址NrNSuNvNvd1装入位辅存实地址地址变换 (软件实现)已装入外页表 虚地址到辅存实地址的变换2N 分 类信息 新闻 2.替换算法1)解决问题当处理机要用到的指令或数据不在主存中时 ，就会产生页面失效，应去辅存中将包含该指令或数据的一页调入主存。由于虚存空间比主存空间大得多，必然会出现主存页面位置已全被占用后又发生页面失效，这时再将辅存中的一页调入主存时就发生页面争用。只用强制腾出主存中某页后才能接纳从辅存调来的新页。具体选择主存中哪一页作为被替换的页，就是替换算法要解决的问题。 分 类信息 新闻 2)原则a)有高的主存命中率b)算法便于实现c)辅助软、硬件成

12、本尽量低3)常用算法a)随机算法(Random,RAND)用软的或硬的随机数产生器来形成主存中要 被替换页的页号。这种算法简单，易于实现， 但没有利用主存使用情况的历史信息，反映不 了程序的局部性，使主存命中率低，很少采用 。 分 类信息 新闻 b)先进先出算法(First In First Out,FIFO)选择最早装入的页作为被替换的页。这种算法实现方便，虽然利用了主存使用情况的历史信息 ，但是不一定能正确反映出程序的局部性，因为最先进入的页很可能是现在经常要用到的页。实页号 占用位 程序号 段页号计数器 (使用位) 程序优先位 HS其它信息 0 12nv-1主存页面表 分 类信息 新闻

13、c)近期最少使用算法(Least Recently Used,LRU)选择近期最少访问的页作为被替换的页。这种算法能比较正确的反映程序的局部性，因为当前最少使用的页一般来说未来也将很少访问，但完全按此算法实现比较困难，需要为每个实页都配置一个字长很长的计数器字段才行。所以一般采用它的变形，即近期最久没被访问过的页作为被替换的页。这样把“多”和“少”简化成“有”和“无”之后，实现起来比较方便。 分 类信息 新闻 主存页面表OS为实现主存管理而设置的，是对主存而言的，整个主存只有一个。每一行用来记录主存中各页的使用状况。而页表是对程序空间而言的，每道程序都有一个，是用来存贮地址映像关系和实现地址变换的。实页号:主存页号是顺序的，可以省略占用位:表示该主存页面是否被占用程序号/段页号:该主存页被哪道程序的哪段 哪页占用使用位:表示该主存页近期是否被使用过 分 类信息72news.wdsxx.co