第4章 存贮体系.ppt

第4章 存贮体系 4.1存贮体系的形成与性能 4.2虚拟存贮 4.3高速缓冲存贮器Cache 4.4主存保护•本章重点：段页式和页式虚拟存贮器的原理；页式虚拟存 贮器的地址映像；LRU/FIFO/OPT替换算法进行页 面替换的过程模拟；LRU算法对页地址流的堆栈 处理模拟及性能分析；Cache存贮器的直接和组 相联地址映像；LRU替换算法的硬件实现及替换 过程模拟；Cache存贮器的性能分析等 •本章难点：段页式和页式中虚实地址的计算；各种页面替 换算法的模拟和页面命中率的计算；Cache组相 联映像和块替换算法的模拟4.1 存贮体系的形成与性能 存储器系统是计算机系统的重要组成部分，现代计算机系统 都以存储器为中心，程序若要运行，必须先把有关程序和数据装 到存储器中 l存储器系统与存储器是两个完全不同的概念 如果在一台计算机中只有存储器，甚至有多种 存储器，但没有存储系统，那么，这台计算机 的性能将会是很差的，这些存储器的性能也不 可能得到充分发挥l在一台计算机中有多种存储器–种类：主存储器（或称内存）、Cache、通用寄存 器、磁盘存储器、各种缓冲存储器、磁带和光盘存 储器等。

–从构成存储器的材料上看，有ECL、TTL、MOS、 静态存储器SRAM、动态存储器DRAM，还有磁表 面存储器和光存储器等–从存储器的访问方式看，有直接译码、先进先出、 随机访问、相联访问，也有块交换、文件交换等4.1.1发展存贮体系的必要性1.存贮器的性能要求l一个存储器的性能通常用速度、容量、价格三个主要 指标来表示，以下也同样用这三个指标来表示存储系 统的性能 速度：指存储器的访问周期（又称存储周期、存取周 期、读写周期等）、读出时间、频带宽度等 容量：存储器中的字节B或者千字节KB，或者兆字节 MB和千兆字节GB等不同单位下的数量 价格：用每个二进制多少美分（$C/bit）等来表示追求的是：大容量、高速度、低价格2.容量SM=W · l · mW：存贮体的字长，单位为bit或Bytel：每个存贮体的字数m：并行工作的存贮体的个数3.速度从下面三个方面来描述：1)访问时间TATA是存贮器接到访存到信息被读到数据总线上所需的时间是确定CPU与存贮器时间关系的重要指标2)存贮周期TMTM是连续启动一个存贮体所需要的时间间隔一般来 说总比TA大3)存贮器频宽是指存贮器可以提供的数据传送率，一般用每秒钟所 传送的信息位数来衡量。

a)最大频宽BM(极限频宽)是存贮器连续访问时能提供的频宽单体： BM =W/TMm体并行工作：BM =mW/TMb)实际频宽实际频宽小于最大频宽BM4.价格可以用总价格C或每位价格c来表示具有SM位的存贮器每位价格c=C/SM其中包括了存贮器本身的价格和为该存贮器操作所必须的外围电路的价格 5.结论由于存贮器的价格、速度和容量的要求是矛盾的，为了同时满足三方面的要求，在一个完整的存贮体系中，必须采用不同工艺的存贮器，使得信息以各种方式分布于不同的存贮体比如：主存 当前活跃的信息，快，少辅存 暂时不用的信息，慢，多虚存 swap从速度来说，主存远远跟不上CPU的要求，为了弥补这一差距，特引入并行和重叠技术，构成并行主存系统，但这种并行主存的方法提高频宽是有限的，因此还需从系统结构入手，发展存贮体系4.1.2并行主存系统频宽的分析1.类型1)单体单字存贮器字长W与CPU字长W相同,一次访问一个存贮器字,主存最大频宽BM =W/TMW位读出寄存器地址寄存器单体单字存贮器l2)单体多字存贮器字长等于m个CPU字,BM =mW/TMW位W位W位W位地址寄存器单体多字(m=4)存贮器W位单字长寄存器在具体实现时，要把地址码 分成两个部分，其中一部分 仍作为存储器的地址去访问 存储器（因为存储器的字数 减少了，因此访问存储器的 地址码可以缩短），而另一 部分则去控制一个多路选择 器，从同时读出的n个数据 中选择一个数据输出。

3)多体单字交叉总线控制地址寄存器0 地址寄存器1地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件)CPUIOP……………………多体(m=4)交叉存贮器00 00FF 0000 01FF 0100 11FF 11存储器地址寄存器（高位）低位a)存贮器字长等于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, · · ·00 01 1011地址的模4低位交叉编址4)多体多字交叉多个存贮体，每个存贮体有CPU字。

上述能并行读出多个CPU字的单体多字和多体 单字或多体多字的交叉存贮主存系统统称为并行 主存系统2.分析提高m值，可以提高主存系统的最大频率，但 并不能线性提高实际频率原因：1)模m越高，存贮器数据总线越长，导致传输延迟增加；2)系统效率问题，对于顺序取指，效率可以 提高m倍，但遇到转移指令，效率就会下降3.模型分析对于m个独立分体的主存系统，处理机发出一串地址为A1,A2,… Aq的访存申请队，在每个主存周期到来前，申请队被扫描，截取从队头起的A1,A2,… Ak的申请序列申请序列是在要求访存申请的k个地址中，没有两个或两个以上的地址处于同一分体中的最长序列显然k表示可以同时访问的分体个数的随机变量，不大于m，系统效率取决于k的均值B，其值越大，可访问的分体个数越多，系统效率越高1)数学模型设p(k)表示申请序列长度为k的概率密度函数， 其中k=1,2,…m则k的均值B为B=∑k‧p(k)B实际就是每个主存周期所访问的平均字数而 p(k)与程序的状态密切相关，特别是指令转移概 率p，它定义为给定下条指令地址为非顺序地址 的概率因此p(k)=(1-p)k-1‧p， 1≤k>2nv，使 得页表中绝大部分行中实页号nv字段及其它字段都不 再有用了，这就会大大降低页表的空间利用率。

c)解决办法•将页表中装入位为0的行用实页号nv字段存放该程序此 虚页在辅存中的实地址，以便调页时实现用户虚页号 到辅存实地址的变换•相联目录表法:把页表压缩成只存放已装入主存的那 些虚页(用基号b和Nv’标识)与实页位置(nv)的对应关系 这样该表最多为2nv行，简称为目录表法，采用按内 容访问的相联存贮器构成如下图：基号用户虚页号页内位移 某用户虚地址基号＋用户虚页号实页号其它 信息 目录表(存在相联存贮器中)相联比较查找到目录表法Nv’bNrnvnvnr(Nr)npb+Nv’2nv行d)相联存贮器在一个存贮周期内能将给定的Nv同时与目录表的全 部2nv个单元对应的虚页号字段内容比较进行相联查找 如有相符的即相联查找到时，表示此虚页已装入主存， 该单元存放的实页号nv就是此虚页所存放的实页位置， 将其读出拼接上Nr就可形成访存实地址np；如无相符的 即相联查找不到，表示此虚页未装入主存，发生页面失 效，请求从辅存中调页由此可见，采用目录表法不用 设置装入位了6)虚页的调入当发生页面失效时，要想把该道程序的虚页调入主存，必须给出该页在辅存中的实际地址为了提高调页效率，辅存一般是按信息块编址的，且块的大小等于页面大小。

以磁盘为例，辅存实(块)地址格式Nvd为：这样就需要将多用户虚页号Nv变换成辅存实地址Nvd 磁盘号柱面号磁头号块 号Nvd•外页表:存放用户虚页号Nv’与辅存实地址Nvd的 映像关系，用于外部地址变换•内页表:存放用户虚页号Nv’与主存实页号nv的映 像关系，用于内部地址变换由于虚拟存贮器的页面失效率很低，很少调用外 页表进行地址变换，因此外页表存放在辅存中，当某 道程序初始运行时，才把外页表的内容转录到已建立 内页表的实页号地址字段中，这也是前述当内页表装 入位为0时让实页号地址字段改放该虚页在辅存中的 实地址的原因而且对外页表速度要求低，可以用软 件实现如下图：磁盘号柱面号 磁头号 块号Nvd多用户虚地址辅存地址NrNSuNv’Nvd1装入位辅存实地址地址变换 (软件实现)••已装入外页表 虚地址到辅存实地址的变换2Nv’2.替换算法1)解决问题当处理机要用到的指令或数据不在主存中时，就会产生页面失效，应去辅存中将包含该指令或数据的一页调入主存由于虚存空间比主存空间大得多，必然会出现主存页面位置已全被占用后又发生页面失效，这时再将辅存中的一页调入主存时就发生页面争用只用强制腾出主存中某页后才能接纳从辅存调来的新页。

具体选择主存中哪一页作为被替换的页，就是替换算法要解决的问题2)原则a)有高的主存命中率b)算法便于实现c)辅助软、硬件成本尽量低3)常用算法a)随机算法(Random,RAND)用软的或硬的随机数产生器来形成主存中要被替换页 的页号这种算法简单，易于实现，但没有利用主存使 用情况的历史信息，反映不了程序的局部性，使主存命 中率低，很少采用b)先进先出算法(First In First Out,FIFO)选择最早装入的页作为被替换的页这种算法实现方便，虽然利用了主存使用情况的历史信息，但是不一定能正确反映出程序的局部性，因为最先进入的页很可能是现在经常要用到的页实页号 占用位 程序号 段页号计数器 (使用位) 程序优先位 HS其它信息 0 12nv-1……主存页面表c)近期最少使用算法(Least Recently Used,LRU)选择近期最少访问的页作为被替换的页这种算法能比较正确的反映程序的局部性，因为当前最少使用的页一般来说未来也将很少访问，但完全按此算法实现比较困难，需要为每个实页都配置一个字长很长的计数器字段才行所以一般采用它的变形，即近期最久没被访问过的页作为被替换的页这样把“多”和“少”简化成“有”和“无”之后，实现起来比较方便。

•主存页面表OS为实现主存管理而设置的，是对主存而言的，整个主存只有一个每一行用来记录主存中各页的使用状况而页表是对程序空间而言的，每道程序都有一个，是用来存贮地址映像关系和实现地址变换的实页号:主存页号是顺序的，可以省略占用位:表示该主存页面是否被占用程序号/段页号:该主存页被哪道程序的哪段 哪页占用使用位:表示该主存页近期是否被使用过实页号 占用位 程序号 段页号计数器 (使用位) 程序优先位 HS其它信息 0 12nv-1……开始时所有页的使用位全为“0”，只要某个页的任何单元被访问过，硬件就自动将该页使用位置“1”由于采用全相联映像，调入页可进入对应于主存页面表中任何占用位为“0”的实页位置，一旦装入主存某实页上，就置该实页的占用位为“1”只有当所有占用位都是1且又发生页面失效时才有页面替换问题，这时就要用到使用位，只需替换使用位为“0”的页即可•使用位全“1 ”处理一种办法是由硬件强制全部使用位都为“0”从概念上看，近期最少使用的“期”是从上次使用位 全0到这次使用位全0的这段时间由于这个期的长短 是随机的，所以称为随机期法另一种办法是它定期的置全部使用位为“0”每间隔一个固定的时间，如几个毫秒或几秒。

把所 有页面的使用位全部清为“0“那么，这时候的“近期“ 就是一个固定的时间间隔当然，这个固定的时间间 隔要选择得恰当既要保证不发生全部使用为位都为 “1“的情况，又要使这个时间间隔尽可能长些 l另一种比较好的办法是，在主存页面表中再设置一个 历史位Hs，或者叫做“。