计算机系统结构第4章(存储系统)

第3章存储系统/MemorySystem

主存读缓存器指令读缓存器写缓存器

I/O

部件

I/O

部件CPU以存储器为中心的计算机结构现代计算机系统都以存储器为中心.在计算机运行过程中，存储器是各种信息存储和交换的中心.存储系统/MemorySystem【学习目标】1.领会存储系统的含义及其性能指标.2.

理解并行存储器的工作原理。3.掌握虚拟存储系统的工作原理和虚拟存储系统的页面替换算法。4.掌握Cache存储系统的地址映象及变换方法以及Cache存储系统的块替换算法。第4章存储系统/MemorySystem【学习内容】4.1存储系统的层次结构与性能指标4.2并行存储器4.3虚拟存储器4.4高速缓冲存储器（Cache)4.5三级存储系统4.1存储系统的层次结构与性能指标4.1.1存储器的层次结构4.1.2存储系统的性能指标存储器的层次结构计算机中的存储器类型:主存储器、Cache、通用寄存器、各种缓冲存储器构成材料:ECL,TTL,MOS，磁表面存储器，光存储器,SRAM,DRAM访问方式：直接译码、随机访问、相联访问、块交换、文件组、手工加载等存储器的层次结构存储器的主要性能指标速度:用存储器的访问周期、读出时间、频带宽度等表示容量:用字节B、千字节KB、兆字节MB和千兆字节GB等表示价格:用单位容量的价钱表示，例如$C/bit

两个或两个以上速度、容量和价格各不相同的存储器,用硬件、软件、或软件与硬件相结合的方法连接起来成为一个系统。这个系统对应用程序员透明，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。

具有这种层次的存储系统能获得比较高的性能价格比的重要依据是:程序对程序空间的访问具有程序访问局部性的特点.

存储系统的定义存储器的层次结构存储器的层次结构1.程序访问局部性2.存储系统的多级层次结构3.存储系统的透明性要求4.三级存储系统1.程序访问局部性程序访问局部性包括:时间局部性和空间局部性.时间局部性:程序在最近的未来要用到的信息很可能是在正在使用的信息.如循环程序的多次重复使用.空间局部性:程序在最近的未来用用到的信息很可能同现在使用的信息在存储空间位置上是相邻近的.程序访问局部性指出了最近的未来要使用的指令和数据很可能就是正在使用的指令和数据,或者是与正在使用的指令和数据在存储空间位置上相邻的指令和数据.因此,可以把存储空间位置相邻的信息作为一“块”或一“页”放到容量最小但速度最快的一级存储器中,从而可以使访问速度接近速度最快的那一级的存储器的速度.例如:2.存储系统的多级层次结构由n个速度、容量、价格各不相同的存储器组成的存储系统.其中,M1级最靠近CPU,它的速度最快,或者说M1的访问周期T1最小,正是通过高速的M1使存储系统的访问速度能与CPU的速度匹配.但是,高速的M1的单位容量的平均价格同速度较低的存储器相比要贵得多,容量S1也因为价格的限制不能T太大.多层次结构的存储系统的性能价格比有优于任何的单级存储器.3.存储系统的透明性要求

存储系统应满足以下透明性要求:

(1)在程序执行期间,CPU产生一个连续的逻辑地址流,逻辑地址需要变换为某个Mi的物理地址,才能实现对Mi的访问,这钟地址变换对程序员应该是透明的.

(2)在两个相临的存储器Mi

和Mi+1之间调入和调出块或页的操作对程序员也应该是透明的.存储系统的透明性是由对存储系统进行管理的硬件和软件来实现的.4.三级存储系统

多数计算机是由高速缓冲存储器(Cache)、主存储器和磁盘存储器(辅存)构成一个三级存储系统.实现方式:组织成2个独立的二级存储系统.

(1)由Cache和主存组成的“Cache-主存”存储系统,或称为Cache存储器.

(2)由主存和磁盘存储器组成的“主存-辅存”存储系统,因采用虚拟存储技术,也称为虚拟存储器.Cache主存辅存三级存储系统虚拟存储器(VirtualMemory)是针对主存容量不能满足要求而提出来的,在主存和辅存之间增加辅助的软件和硬件,使主存和辅存构成一个整体.等效的访问速度接近于主存访问速度,容量是辅存的容量,每位价格接近于辅存.Cache存储器是针对主存速度不能满足而提出来的,在物理Cache和主存之间增加辅助硬件,使Cache和主存构成一个整体,Cache存储器的等效访问速度接近物理Cache访问速度,容量却是主存的容量,每位价格接近主存的价格.虚拟存储器和Cache存储器对应用程序员都是透明的.由于CPU与主存的速度只差1个数量级,主存与辅存的速度却差3～4个数量级,因此,Cache只能全部采用硬件来实现.Cache存储器对系统程序员也是透明的,操作系统不会参与对Cache存储器的管理.

在虚拟存储器中,为了降低成本,有部分功能由操作系统的存储管理软件来实现,因此,虚拟存储器对系统程序员是不透明的.

目前,很多CPU的芯片内集成有Cache,因此把Cache又分为相临的二级,片内Cache称为一级Cache,片外Cache称为二级Cache.三级存储系统4.1.2存储系统的性能指标两个存储器组成的存储系统.T1＜T2,S1

＜S2,C1＞C2存储系统的性能指标

1.存储系统的容量S存储系统对计算机的使用者提供尽可能大地址空间,且能够随机访问.对于Cache存储器,其容量等于主存的容量,既M=M2.对于虚拟存储器,其容量既不是主存的地址空间,也不是辅存的地址空间,而是比实际物理地址空间大得多的虚拟地址空间,并且用像主存一样的随机访问方式.2.存储系统的带宽存储器被连续访问时能提供的数据传输率称为存储器的最大带宽(一般用每秒钟所传送的信息位数来衡量)。由于存储器不一定始终满负荷工作,因此,存储器的实际带宽一般低于最大带宽.存储系统的性能指标当S2》S1时，C≈C2但S2与S1不能相差太大,否则,难实现调度使性能高3.单位容量的平均价格C计算公式:4.命中率HCPU产生的逻辑地址在M1存储器中访问到的概率其中：N1是对M1存储器的访问次数

N2是对M2存储器的访问次数H越接近1越好!

访问效率主要与命中率和两级存储器的速度之比有关5.存储系统的访问周期T表示方法：访问周期、存取周期、存储周期、存取时间等系统的访问周期T＝H×T1＋(1－H)×T2T1

和T2

分别是存储器M1

和M2的访问周期

当命中率H→1时，T→T16.存储系统的访问效率存储系统的性能指标主要与命中率和构成系统的两级存储器的访问周期比有关.可以看出:存储系统的访问效率主要与命中率和构成存储系统的两级存储器的速度之比有关.

结论:提高存储系统速度的两条途径：

一是提高命中率H

二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)因此,主要依靠提高命中率

存储系统的性能指标例1：假设T2＝５T１，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：当H＝0.9时，e1＝1／(0.9＋5×(1－0.9))＝0.72

当H＝0.99时，e2＝1／(0.99＋5×(1－0.99))＝0.96

存储系统的性能指标例2：在虚拟存储系统中，两级存储器的速度相差特别悬殊T2＝105T１。如果要使访问效率e＝0.9，问需要有多高的命中率？解：0.9H＋90000(1－H)＝189999.1H＝89999

计算得H＝0.999998888877777…≈0.999999存储系统的性能指标例3：在一个Cache存储系统中，当Cache的块大小为一个字时，命中率为H＝0.8；假设数据的重复利用率为5，计算Cache的块大小为4个字时，Cache存储系统的命中率是多少？假设T2＝５T1，分别计算访问效率。解：n＝4×5＝20，采用预取技术之后，命中率提高到：Cache的块大小为一个字时，H＝0.8，访问效率为：

e1＝1／(0.8＋5(1－0.8))＝0.55…Cache的块大小为4个字时，H＝0.99，访问效率为：

e2＝1／(0.99＋5(1－0.99))＝0.96存储系统的性能指标例4：在一个虚拟存储系统中，T2＝105T１，原来的命中率只有0.8，现采用预取技术，访问磁盘存储器的数据块大小为4K字，如果要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至少为多少？解：假设数据在主存储器中的重复利用率为m，根据前面的给出关系：解这个方程组，得到m＝44，即数据在主存储器中的重复利用率至少为44次。存储系统的性能指标4.2并行存储器存储器的存取速度直接影响着计算机系统的性能.为此:要解决存储器的频带平衡问题.计算机系统中各级存储器的频带应该达到平衡例如：有一台速度为500MIPS的计算机系统，主存储器的各种访问源的频带宽度如下：

CPU取指令：500MW/sCPU取操作数和保存运算结果：1000MW/s

各种输入输出设备访问存储器：50MW/s三项相加，要求存储器的频带宽度不低于1550MW/s。访问周期不大于0.64ns。

实际上目前作为主存储器的工作周期为100ns左右，两者相差150多倍.并行存储器

解决存储器频带平衡方法有多种,其中,设置多个独立的存储器,并行工作,在一个存储周期内可以访问多个数据,是提高存储器速度最直接的方法4.2.1单体多字并行存储器4.2.2低位交叉编址多体并行存储器4.2.1单体多字并行存储器逻辑实现：把地址码分成两个部分.一部分仍作为存储器的地址,访问存储器.另一部分去控制一个多路选择器,负责从读出的n个数据中选择一个数据输出.

方法：把m个字w位的存储器改变成为m/n字n×w位的存储器(把字长增加n倍,以存放n个指令字或数据字)主要优点:实现简单、容易主要缺点：访问冲突大,主要冲突来自:

(1)

取指令冲突（条件转移时）.(2)读操作数冲突（需要的多个操作数不一定都存放在同一个存储字中）.(3)写数据冲突（必须凑齐n个数才一起写入存储器）.(4)读写冲突（要读出的一个字和要写入的一个字处在同一个存储字内时，无法在一个存储周期内完成）。单体多字并行存储器交叉访问存储器通常有两种工作方式,一种是地址码高位交叉,另一种是地址码低位交叉.高位交叉访问存储器主要目的：扩大存储器容量

低位交叉访问存储器。主要目的：提高存储器访问速度,同时也增加了存储器的容量.4.2.2低位交叉编址多体并行存储器实现方法：用地址码的低位部分区分存储体号,高位是各存储体的体内地址.低位交叉编址多体并行存储器存储器地址A的计算公式为：A＝m×i＋k如果已经知道存储器的地址为A,则它的:存储器的体内地址：Ai＝存储器的体号Ak＝Amodm交叉编址方式低位交叉编址多体并行存储器地址码低位：存储体的个数为m,低位位数=log2m地址码高位：每个存储体的容量n,高位位数=log2n用i表示存储体的体内地址,用k表示存储体的体号存储体地址的编码方法

为了达到提高速度的目的,m个存储体必须分时启动.m个存储体分时启动每存储体的启动间隔为：t＝实际上是一种采用流水线方式工作的并行存储器,理论上，存储器的速度可望提高m倍.

由于每个存储单元都有自己的地址,低位交叉编址多体并行存储器的实际带宽也高于相同容量的单体多字存储器的实际带宽.

4.3虚拟存储器1961年英国曼彻斯特大学的Kilbrn等人提出的。到了70年代被广泛地应用于大中型计算机系统中。目前，许多微型机也开始使用虚拟存储器。

4.3.1虚拟存储器的地址变换4.3.2页面替换算法及其命中率*4.3.3堆栈型替换算法及其堆栈处理过程4.3.1虚拟存储器的地址变换几个概念:三种地址空间：虚拟地址空间(用来编写程序的地址空间)，主存储器地址空间(实存地址空间)，辅存地址空间(磁盘存储器的地址空间)。三种地址：虚拟地址(程序经编译生成的访存地址)、主存地址、磁盘地址地址映象：程序代码运行时,必须先把虚拟地址转换成主存实地址,才能访问主存.虚地址与实地址之间对应关系的规则(AddressMapping).地址变换：在程序运行过程中，虚拟存储系统按照某种地映象把虚拟地址变换成主存实地址,称为地址变换(AddressTranslation)因地址映象和变换方法不同，有三种虚拟存储器：段式虚拟存储器、页式虚拟存储器、段页式虚拟存储器。1.段式虚拟存储器的地址变换(1)地址映象方法：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。段式虚拟存储器的地址映象段号段长起始地址01k8k150016k22009k320030k虚拟存储器的地址变换

主程序0段1段2段3段程序空间01k050002000200主存空间8k9k16k30k段表(段号可以省掉)(2)段式虚拟存储器地址变换

地址变换方法：由用户号找到基址寄存器从基址寄存器中读出段表的起始地址把起始地址与多用户虚地址中段号相加得到段表地址把段表中给出的起始地址与段内偏移D相加就能得到主存实地址段式虚拟存储器的地址变换多用户虚地址由三部分组成:U,S,D在CPU中有一个段表基址寄存器堆,每道程序使用其中的一个基址寄存器,通过虚地址中的用户号可直接找到与这道程序相对应的基址寄存器.用户号U段号S段内偏移D6As段表长度段表基地址段式虚拟存储器地址变换方法：多用户虚地址01234段名起始地址装入位段长访问方式主存实地址0N-1+As+段表基址寄存器一个用户(一道作业)的段表(3)段式虚拟存储器的主要优点：程序的模块化性能好。便于程序和数据的共享。在主程序装入共享程序段.其他要调用这个程序段的程序,在其段表中都使用这个被共享的程序段的起始地址和段长.程序的动态链接和调度比较容易。便于实现信息保护。(4)段式虚拟存储器的主要缺点：地址变换所花费的时间比较长，做两次加法运算。主存储器的利用率往往比较低。对辅存（磁盘存储器）的管理比较困难。

段式虚拟存储器地址的映象

地址的映象与变换0页1页2页3页用户程序主存储器2.页式虚拟存储器的地址变换(1)页式虚拟存储器的地址映象把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块—页(page)，每页的大小相同。主存储器的页称为实页，虚拟存储器中的页称为虚页。由用户号U直接找到相对应的基址寄存器从基址寄存器中读出页表起始地址把页表起始地址与多用户虚地址中虚页号相加得到页表地址，从页表中读出主存页号p与虚地址中的页内偏移D拼接得到主存实地址

2.页式虚拟存储器的地址变换(1)页式虚拟存储器的地址变换用户号U虚页号P页内偏移DPa1P装入位修改位主存页号各种标志实页号p页内偏移d页表基址寄存器页表多用户虚地址Av主存实地址APa+2.页式虚拟存储器的地址变换(2)页式虚拟存储器的地址变换(3)页式虚拟存储器的主要优点：主存储器的利用率比较高。页表相对比较简单，节省了页表的存储容量。地址映象和变换的速度比较快。对辅存（磁盘存储器）的管理比较容易。(4)页式虚拟存储器的主要缺点：程序的模块化性能不好。页表很长，需要占用很大的存储空间。例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字，16MB。3.页式虚拟存储器内部地址变换：多用户虚拟地址Av变换成主存实页号p多用户虚拟地址中的页内偏移D直接作为主存实地址中的页内偏移d，主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A。进行外部地址变换：首先查外页表得到磁盘存储器的实地址.然后再查内页表，看主存储器中是否有空页。若空,把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机，要访问数据所在的一整页都从磁盘存储器调入到主存储器。若不空,进行页面替换,把主存中暂时不用的一页写回到磁盘存储器中原来的位置上.外部地址变换不命中,启动海量存储器,把所需数据相关的文件调磁盘存储器.页式虚拟存储器虚拟存储器工作原理先内后外再海量,内部变换最优先,AV换成实页号(p),工作全由操、硬完,得到实页(号p)尚未了,还需得到页内偏(d),最后将p拼接d,用A访存不麻烦;内部变换不成功,软件进行外变换,首先查查外页表,相应实址在磁盘,然后再查内页表,检查主存页有闲?若是主存有空页,整页调进主存间;如果变换不成功,操作系统启光盘,信息调入磁盘器,组织方式是文件.3.段页式虚拟存储器

基本思想是用户用来编写程序的虚拟存储空间采用分段的方法管理,主存物理空间采用分页的方法进行管理.用户按照程序段来编写程序，每个程序段分成几个固定大小的页。(1)地址映象方法：每个程序段在段表中占一行。在段表中给出该程序段的页表长度和页表的起始地址.页表中给出这个程序段的每一页在主存储器中的实页号。虚拟存储器的地址变换

段页式虚拟存储器

０段（12K）０段０页０段１页０段２页２段（5K）地址映象方法页表长度页表地址３３２１段０页１段１页１段２页１段（10K）２段０页２段１页０段页表１段页表２段页表每页４ＫＢ段表用户程序主存储器(2)地址变换方法：先查段表，得到该程序段的页表起始地址和页表长度．再查页表找到要访问的主存实页号．最后把实页号p与页内偏移d拼接得到主存的实地址。

段页式虚拟存储器

10/1Ap装入位修改位标志页表长页表地址As1p0/1装入位实页号修改位标志段页式虚拟存储器

地址变换方法：用户号U段号S虚页号P页内偏移D实页号p页内偏移d多用户虚地址Av主存地址A段表地址寄存器多用户段表多用户页表ApAs++造成虚拟存储器速度降低的主要原因：要访问主存储器必须先查段表或页表，如果页表和段表在主存储器内,包括访问主存储器本身这一次在内,主存储器的访问速度下降.当页表和段表的容量超过了一个页面的大小时,可能被映象到不连续的页面位置上,这样按照地址查找不能成立.可能需要多级页表。4.加快地址变换的方法

为此采取几种加快内部地址变换的方法:

(1)目录表(2)快慢表虚拟存储器的地址变换

基本思想：用目录表代替页表,目录表的行数是实页数,使用容量较小的相联存储器.

方法：把多用户虚地址中的虚页号(U与P拼接起来)作为关键字段对目录表中所有存储字的多用户虚页号字段进行并行查找.如相等,把实页号p与多用户虚地址中的页内偏移D直接拼接起来,即是要访问的主存实地址.如果没有相等的,则表示要访问的虚页还没有装入主存,此时发出页面失败请求,从磁盘存储器中把要访问的那个页调入主存.加快内部地址变换的方法(1)目录表用户号U虚页号P页内偏移D实页号p页内偏移d目录表地址变换方法U,Pp0/1多用户虚页号(U,P拼接)实页号修改位其他标志主存实地址多用户虚地址相联访问目录表(按内容访问的相联存储器)根据程序在执行过程中的局部性特性,在一段时间内,地址变换对页表的访问会局限在少数存储字内,因此,可大大缩小目录表的存储容量,例如,容量为8～16个存储字,访问速度与CPU中的通用寄存器相当,这个小容量的页表成为快表TLB(Translation

LookasideBuffer).快表的容量小(几～几十个字)，高速硬件实现，采用相联方式访问.

与快表相对应的存放在主存储器中的页表成为慢表,慢表是一个全表,快表是慢表的一个副本,而且只存放了慢表中很少一部分.快表与慢表也构成了一个两级存储系统。加快内部地址变换的方法(2)快慢表加快内部地址变换的方法快慢表地址变换过程用多用户虚页号同时查快表和慢表.在快表中查到,终止查慢表,读出实业页号p送主存的地址寄存器.在快表中没有查到,不终止慢表的查表过程.若在慢表中查到,把慢表中的实业页号p送主存的地址寄存器.同时把实页号连同用户虚地址送人快表中.若慢表中也未查到,则发出页面失败请求.1

p装入位实页号U,Pp多用户虚页号(U,P拼接)实页号用户号U虚页号P页内偏依D快慢表地址变换过程实页号p页内偏移d多用户虚地址慢表(按地址访问)快表(按内容相联访问)主存实地址慢表快表例:IMB370/168计算机的虚拟存储器快表结构及地址变换过程。采用页式虚拟存储器,虚拟地址长48位，页面大小为4KB，每个用户最多占用4K个页面，最多允许2∧24个用户，实际上同时上机的用户数一般不超过6个。快表按地址访问,快表的地址由多用户虚页号经硬件散列部件压缩后生成.快表地址共6位,故快表容量为64个存储字.

采用了两项新的措施：

一是在快表的每一个存储字中多用户虚页号与主存实页号,并采用两个相等比较器。二是用相联寄存器组把24位用户号U压缩成3位的ID.把这个ID与虚页号直接拼接起来作为散列变换部件的输入.虚拟存储器举例U1010U2011U3100U4101U5110U6111ID与P拼接pID与P拼接p多用户虚页号实地址多用户虚页号实地址用户号U虚页号P页内偏移DIMB370/168计算机的虚拟存储器快表结构及地址变换过程实页号p页内偏移d多用户虚地址24位12位12位相联比较散列变换相联寄存器组ID快表(按地址访问,有两组)相等比较相等比较拼接相等不等或相等不等12位主存实地址15位6位例4.14.3.2页面替换算法及其命中率页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。评价页面替换算法好坏的标准：一是命中率要高;二是算法要容易实现。页面替换算法的使用场合：(1)虚拟存储器中，主存页面的替换，一般用软件实现。(2)Cache中的块替换，一般用硬件实现。(3)虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。(4)虚拟存储器中，用户基地址寄存器的替换，用硬件实现。(5)在有些虚拟存储器中，目录表的替换。页面替换算法及其命中率1.几种页面替换算法常用的页面替换算法：(1)随机算法（RANDRandomalgorithm）：算法简单，容易实现。没有利用历史信息，没有反映程序的局部性，命中率低。(2)先进先出算法（FIFOFirst-InFirst-Outalgorithm）：选择最早装入主存的虚页作为被替换页.在页表和目录表中对每个页增设一个“年龄记数器”字段,刚调入的虚页的计数器的记数值为0,每调入一个虚页时,其他装入页的记数值都加1,需要替换时,只需要找出记数值最大的装入页就是最进入的虚页.比较容易实现，利用了历史信息，没有反映程序的局部性。最先调入主存的页面，很可能也是经常要使用的页面。页面替换算法及其命中率(3)近期最少使用算法（LRULeastRecentlyUsedalgorithm

）：选择过去近期访问次数最少的虚页作为被替换页.这种算法能比较好地反映程序局部性,因为一般近期最少使用的页在未来一段时间内也将最少被访问.在目录表或页表中,对每个页增设一个“使用次数计数器”字段,某个页被访问一次时,该页的计数器字段加1.计数值最小的页被替换.

既充分利用了历史信息，又反映了程序的局部性实现起来非常困难。

(4)最久没有使用算法（LFULeastFrequentlyUsedalgorithm

）：选择过去近期最久访问的虚页作为被替换的页.这种算法也比较好地反映了程序的局部性,因为一般近期最久使用的页在未来一段时间也将最久被访问.在页表或目录表中,对每个页增设一个“使用计数器”字段,某页被访问时,该页的计数器字段请0,其他装入页的计数器的值都加1,计数器的值最大的页是被替换的页.它与LRU算法相比,为支持替换算法的实现,增加的内容要少，实现起来比较容易。几种页面替换算法几种页面替换算法

(5)最优替换算法（OPTOPTimal

replacemantalgorithm）：

是一种理想化的算法。是选择将来一段时间最久被访问的的页作为被替换的页.为了算法的实现,需让程序先运行一遍得到程序的全部虚页号序列(虚页地址流),才能在替换时确定未来一段时间内哪一页是最久被访问的.这是一种最优的替换算法,常用来作为评价其它页面替换算法好坏的标准。例:一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）如下：P1，P2，P1，P5，P4，P1，P3，P4，P2，P4

假设分配给这个程序的主存储器共有3个页面。给出FIFO、LFU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。页面替换算法及其命中率2.页面替换算法的命中率计算*例2：一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LFU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LFU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。2.页面替换算法的命中率计算

页面替换算法的主存命中率H与分配给程序的主存实页数n有关.如果替换算法具有下述性质:随着分配给程序的主存实页数n的增加,替换算法到主存命中率H也随之增加,至少不下降.那么,这种替换算法就称为堆栈型替换算法.1.堆栈型替换算法的含义：设A为长度为L的任意一个虚页地址流,t为已处理过t-1个虚页的时间点,n为分配给该虚页地址流的主存实页数,Bt(n)表示在t时间点、在n个实页的虚页集合,Lt表示到t时间点已处理过的虚页地址流中虚页号相异的页号.如果替换算法具有下列包容性质:n＜Lt时Bt(n)

Bt(n+1)

n≥Lt

时Bt(n)＝Bt(n+1)则这类算法称为堆栈型替换算法。

4.3.3堆栈型替换算法及其堆栈处理过程堆栈型替换算法的含义：也可以定义为:对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt（m）

Bt（n)

堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。堆栈型替换算法的含义根据堆栈型替换算法的含义,可以证明LRU、LFU和OPT算法都是堆栈型替换算法.对于LRU算法,由于在主存中保留的是最近使用过的虚页,如果先给某个程序分配n个主存实页,那么在t时刻,这n个主存实页位置中都是最近使用过的虚页.如果再给这个程序多分配一个主存实页,那么在t时刻,这n+1个主存实页的位置中也都是最近使用过的虚页.因此,这n+1个主存实页位置中的虚页集合Bt(n+1)必然包含了其中n个主存实页位置的虚页集合Bt(n).所以,LRU算法是堆栈型替换算法.FIFO算法不是堆栈型算法(见下例)LFU算法、LRU算法和OPT算法都是堆栈型算法。FIFO算法不是堆栈型算法堆栈型替换算法及其堆栈处理过程2.堆栈对访存虚页地址流的处理过程用堆栈处理技术对访存虚页地址流进行处理时,主存在t时间点的状态用堆栈St表示,

St是

Lt个不同虚页号在堆栈中的

有序集,St(1)是St

的栈顶项,St(2)是St

的次顶项,依次类推.按照堆栈型替换算法具有的包容性,有n＜Lt

时Bt(n)=｛St(1),

St(2),St(n)｝

n≥Lt

时,Bt(n)=｛St(1),St(2),St(Lt)｝

这样,对程序分配n个实页,且在这n个实页位置上存放了哪些虚页的虚页号就在堆栈St的前n项中.因此,对虚页地址流A在t时间点的At

虚页是否命中,只需看St-1的前n项是否有At页,若有,则命中.所以,经过一次处理获得St(1),St(2),St(Lt)之后,就知道对应于不同n值时的主存命中率,从而为该道程序按所需要达到的访问命中率来确定应分配给它的主存实页数.堆栈对访存虚页地址流的处理过程

对于不同的堆栈型替换算法,堆栈St各项的改变过程是不同的.例如LRU算法把刚访问过的虚页号压入栈顶单元后,把栈顶单元中的虚页号与其他堆栈单元中的虚页号进行比较,去掉与栈顶单元虚页号相同的其他栈顶单元,从而保证堆栈单元中保留的虚页号都是相异页号.使得在任何时刻,堆栈中的虚页号集合是按过去访问的时间顺序排序的,刚访问的虚页的置于栈顶单元中,最久访问的虚页的虚页号置于栈底单元中.例4.54.3高速缓冲存储器（Cache）4.4.1Cache的地址映象与地址变换4.4.2Cache的替换算法及其实现4.4.3Cache的性能分析Cache与虚拟存储器的主要区别

在Cache系统中,Cache和主存储器都划分成相同大小的(Block）。主存地址由块号B和块内地址W两部分组成。Cache的地址也由块号b和块内地址w组成。地址映象是把存放在主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。

地址变换是当程序已经装入到Cache之后，在实际运行过程中，把主存地址变换成Cache地址。

4.4.1Cache的地址映象与地址变换高速缓冲存储器地址映象与变换方法1.

全相联映象及其变换映象规则：主存的任意一块可以映象到Cache

中的任意一块的位置上。如果Cache的块数为Cb，主存的块数为Mb，映象关系共有Cb×Mb种。全相联映象及其变换地址变换规则用主存地址的块号B与目录表中的主存块号字段进行相联比较如果相等,命中;不等,失效;用主存地址访问主存,把读出的一个字送往CPU,同时把包含这个字那一块装入Cache,并修改目录表.全相联映象及其变换的优点:冲突率低,Cache的利用率高;缺点是需要一个访问速度快、容量为Cb

个字的相联存储器.相联存储器的存储字字长=B的长度+b的长度+1=log2CB+log2Cb+1全相联映象及其变换

例:在Cache存储器中,Cache的容量是字节,主存是由m个存储体组成的低位交叉并行存储器,主存容量是字节,按存储单元编址,每个存储体的存储单元是k字节.采取全相联映象,用相联目录表实现地址变换.(1)写出主存地址和Cache地址的格式,并指出各字段的长度.(2)求出目录表的行数、相联比较的位数和目录表的宽度.例4.62.直接映象及其变换映象规则：主存地址分为三部分:区号E,区内块号B,块内地址W主存各区的容量与Cache的容量相等.Cache地址分为块号b和块内地址w.主存中各区内的一块只能装到与Cache块号相同的那个特定的位置上。

整个Cache地址与主存地址的低位部分完全相同。

地址映象与变换方法2.直接映象及其变换直接映象方式的地址变换过程：(由存放在Cache中的区表实现,区表行数等于Cache的块数,一行二个字段:区号E,有效位)用主存地址中的块号B去访问区表存储器;把读出来的区号与主存地址中的区号E进行比较：比较结果相等:有效位为1，则Cache命中;有效位为0,该块同已被修改过的主存的副本块的内容不一致,已经作废,需重写该块,并把有效位置1;比较结果不相等:有效位为1，没有命中,但Cache中的该块是有用的，需把该块调出写入主存,再从主存调入所需要的新块;有效位为0,没有命中,且该Cache块已作废,可直接调入所需要的新块。

2.直接映象及其变换直接映象方式的地址变换规则

提高Cache速度的一种方法：

把区号存储器与Cache合并成一个存储器2.直接映象及其变换的优缺点

主要优点：

硬件实现很简单，不需要相联访问存储器访问速度也比较快，实际上不需要进行地址变换主要缺点：块的冲突率比较高地址映象与变换方法3.组相联映象及其变换

是介于全相联映象和直接映象之间的一种折中方式,是目前应用的比较多的一种映象方式.

映象规则：主存按Cache的大小分区,区内和Cache按同样大小划分成块和组。从主存的组到Cache的组之间采用直接映象方式。在两个对应的组内部采用全相联映象方式。组相联映象的地址变换地址变换过程：通过块表实现.块表行数是Cache的块数,每行包括E、B、b和有效位e.用主存地址中的组号G作首址,在块表存储器中连续访问多行(一组内各块)。把读出来的一组字中区号和块号与主存地址中的区号和块号进行相联比较：如果有一行相等，表示Cache命中；如果没有相等的，表示Cache没有命中。(1)用相联访问存储器的组相联地址变换有效位(块表的行数是Cache的块数)(2)用多个相等比较器来代替相联访问的组相联地址变换-—提高Cache的访问速度的一种方法.块表的行数是Cache的组数,块表的一行由多存储字组成（组内块数Cb),一个存储字由4个字段组成:主存区号E,主存组内块号B,Cache组内块号b和有效位.把CPU送来的主存地址中的组号G与块表基址相加作为访问块表的物理地址,读出该行中有效位是“有效”的所有存储字;通过相等比较电路把主存地址中的区号E和块号B同时与这些有效存储字中的区号E字段和块号B字段进行比较:若其中有一个有效存储字的区号E和块号B分别与主存地址中的区号E和块号B相等,则把该存储字中的块号b和主存地址中的组号G以及块内地址W组成Cache地址;若没有一个存储字相等,则发生块失败.组相联映象及其变换

(2)用多个相等比较器来代替相联访问的组相联地址变换组相联映象及其变换一些典型机器的Cache分组情况组相联映象及其变换组相联映象方式的优点：

块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。组相联映象方式的缺点：

实现难度和造价要比直接映象方式高。组相联映象及其变换

例4.7采用组相联映象的Cache存储器,Cache的容量为1K字,要求Cache的每一块在一个主存访问周期能从主存取得.主存采用4个低位交叉编址的存储体组成,主存容量为256K字.采用按地址访问存储器存放块表来实现地址变换,并采用4个相等比较电路.请设计地址变换的块表,求出该表的行数和容量.说明地址变换过程及每个相等比较电路进行相等比较的位数.例4.8何时使用Cache替换算法：

发生块失效，且可以装入新调入块的几个Cache块都已经被装满时,使用替换算法将Cache中某一块替换出去。

对于:直接映象方式实际上不需要替换算法。全相联映象方式的替换算法最复杂。在组相联和位选择相联映象及地址变换中,需要从Cache同一组内的几个块中选择一块替换出去.Cache替换算法及其实现Cache替换算法要解决的问题：1.记录每次访问Cache的块号。2.管理好所记录的Cache块号，为找出被替换的块号提供方便。3.根据记录和管理的结果，找出被替换的块号。Cache替换算法的主要特点：全部用硬件实现Cache替换算法及其实现几种替换算法Cache替换算法及其实现1.随机替换算法2.FIFO替换算法

通常用于组相联映像及地址变换方式中,有以下两种实现方法:(1)每块一个计数器实现方法在块表内增加一个替换计数器字段,计数器的长度与Cache地址中的组内块号b字段的长度相同。新装入或替换的块，它的计数器清0，同组其它块的计数器都加“1”。在同组中选择计数器的值最大的块作为被替换的块。例1：Solar-16/65小型机的Cache采用位选择组相联映象方式。Cache每组的块数为4，因此，每块用一个2位的计数器。Cache替换算法及其实现2.FIFO替换算法(2)每组一个计数器的实现方法FIFO替换算法实际上是同组内的块按顺序轮流替换,因此只要为每一组设置一个计数器即可.如果每组的块数为Cb,设置一个模为Cb

的计数器,它最先指向该组最先进来的块,该块被替换后记数值加1,指向下一个要替换的块.最先装入的块,有可能是经常要用的块,因此,FIFO替换算法的效果虽然比随机替换算法好,但仍不理想.例2：NOVA3机的Cache采用组相联映象方式，Cache每组的块数为8，每组设置一个3位计数器。在需要替换时，计数器的值加“1”，用计数器的值直接作为被替换块的块号。3.LFU算法及其实现(最久没有使用算法,Leastfrequentlyusedalgorithm)(1)计数器法为每一块设置一个计数器计数器的长度与Cache地址中的组内块号字段的长度相同.计数器的使用及管理规则：新装入或替换的块，计数器清“0”，同组中其它块的计数器都加“1”。命中块的计数器清0，同组的其它计数器中，凡计数器的值小于命中块计数器原来值的加1，其余计数器不变。需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块被替换。例：IBM370/165机的Cache采用组相联映象方式。每组有4块，为了实现LFU替换算法，在块表中为每一块设置一个2位的计数器。在访问Cache的过程中，块的装入、替换及命中时，计数器的工作情况如表.LFU算法及其实现LFU算法及其实现(2)比较对法基本思想用2个块组成一个比较对,利用一个触发器的状态表示该比较对的两块被访问的先后顺序,经门电路组合,可从多个块中找出最久被访问过的块.实现方法以3个块为例.设有3个块A、B、C,可组合成3个比较对:AB、AC和BC.用一个触发器的状态表示一个比较对中两块被访问的顺序,例如,触发器TAB=1,表示A比B更近被访问过,TAB=0表示B比A更近被访问过.3个块最久被访问过的条件分别是:LRU算法及其实现(2)比较对法实现方法01TAB01TAC01TBC&&&ALFUBLFUCLFU访问B访问C访问ACache的性能分析Cache存储系统的主要目标：提高存储系统的速度Cache存储系统的加速比Cache存储系统的一致性问题1.加速比与命中率的关系Cache存储系统的加速比SP为：

其中：Tm为主存储器的访问周期，

Tc为Cache的访问周