大学计算机组成原理 第3章 存储系统2.ppt

第第3 3章章 存储系统存储系统3.5 3.5 并行存储器并行存储器由于由于CPU和主存储器之间在速度上是不匹配和主存储器之间在速度上是不匹配的，这种情况便成为限制高速计算机设的，这种情况便成为限制高速计算机设计的主要问题。为了提高计的主要问题。为了提高CPU和主存之和主存之间的数据传输率，除了主存采用更高速间的数据传输率，除了主存采用更高速的技术来缩短读出时间外，还可以采用的技术来缩短读出时间外，还可以采用并行技术的存储器。并行技术的存储器。高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院 双端口存储器双端口存储器：是指同一个存储器具有两组相是指同一个存储器具有两组相互互独立的读写控制线路独立的读写控制线路,是一种高速工作的存储器。是一种高速工作的存储器。它提供了两个相互独立的端口，即左端口和它提供了两个相互独立的端口，即左端口和右端右端口。两个端口分别具有各自的地址线、数据线和控制口。两个端口分别具有各自的地址线、数据线和控制线，可以对存储器中任何位置上的数据进行独立的存线，可以对存储器中任何位置上的数据进行独立的存取操作。取操作。1.双端口存储器的逻辑结构双端口存储器的逻辑结构高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院双端口存储器双端口存储器IDT7133的介绍的介绍IDT7133IDT7133为为为为2K 2K 16 16位的双端口位的双端口位的双端口位的双端口SRAMSRAM 两个端口有各自的地址线两个端口有各自的地址线两个端口有各自的地址线两个端口有各自的地址线A A1010-A-A0 0，IOIO0 0-IO-IO1515，控制线（控制线（控制线（控制线（R/WR/W，CECE，OEOE，BUSYBUSY）郑州大学 1/16/2023 4:38 PM信息工程学院当两个端口的地址不相同时，在两个端口当两个端口的地址不相同时，在两个端口上进行读写操作，一定不会发生冲突。上进行读写操作，一定不会发生冲突。当任一端口被选中驱动时，就可对整个存储器当任一端口被选中驱动时，就可对整个存储器进行存取，每一个端口都有自己的片选控进行存取，每一个端口都有自己的片选控制制(CE)和输出驱动控制和输出驱动控制(OE)。读操作时，。读操作时，端口的端口的OE(低电平有效低电平有效)打开输出驱动器，打开输出驱动器，由存储矩阵读出的数据就出现在由存储矩阵读出的数据就出现在I/O线上。线上。2.无冲突读写控制无冲突读写控制高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院表表3.5无冲突读写控制无冲突读写控制左端口或右端口左端口或右端口功能 R/WLb R/WUb CEOEI/O0-7I/O8-1511ZZ端口不用端口不用000数据入数据入数据入数据入低位和高位字节数据写入低位和高位字节数据写入存储器存储器0100数据入数据入数据出数据出低位字节数据写入存储器，低位字节数据写入存储器，存储器中数据输出至高位存储器中数据输出至高位字节字节1000数据出数据出数据入数据入存储器中数据输出至低位存储器中数据输出至低位字节，高位字节数据写入字节，高位字节数据写入存储器存储器0101数据入数据入Z低位字节写入存储器低位字节写入存储器1001Z数据入数据入高位字节写入存储器高位字节写入存储器1100数据出数据出数据出数据出存储器中数据输出至低位存储器中数据输出至低位字节号高位字节字节号高位字节1101ZZ高阻抗输出高阻抗输出高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院v有冲突读写控制有冲突读写控制当两个端口同时存取存储器同一存储单元时，当两个端口同时存取存储器同一存储单元时，便发生读写冲突。便发生读写冲突。为解决此问题，特设置了为解决此问题，特设置了BUSY标志标志。在这种情况下，片上的判断逻。在这种情况下，片上的判断逻辑可以决定对哪个端口优先进行读写操作，辑可以决定对哪个端口优先进行读写操作，而对另一个被延迟的端口置而对另一个被延迟的端口置BUSY标志标志(BUSY变为低电平变为低电平)，即暂时关闭此端口。，即暂时关闭此端口。郑州大学 1/16/2023 4:38 PM信息工程学院 仲裁原则仲裁原则：1.CE1.CE判断判断:如果地址匹配且在如果地址匹配且在CECE之前有效，则：片之前有效，则：片上的控制逻辑在上的控制逻辑在CECEL L和和CECER R之间进行判断来选择端之间进行判断来选择端口，谁先有效，谁就优先获得对存储器的读写控口，谁先有效，谁就优先获得对存储器的读写控制权。制权。2.2.地址有效判断地址有效判断:如果如果CECE在地址匹配之前先有效，在地址匹配之前先有效，则：片上的控制逻辑在左、右地址间进行判断来则：片上的控制逻辑在左、右地址间进行判断来选择获得优先权的端口。谁先有效，谁就优先获选择获得优先权的端口。谁先有效，谁就优先获得对存储器的读写控制权。得对存储器的读写控制权。3.有冲突的读写控制有冲突的读写控制解决方法解决方法：设置设置BUSY标志，采用仲裁逻辑。标志，采用仲裁逻辑。由芯片上的判断逻辑决定由哪个端口优先进行由芯片上的判断逻辑决定由哪个端口优先进行读写操作，而暂时关闭另一个被延迟的端口。读写操作，而暂时关闭另一个被延迟的端口。1.1.存储器的模块化组织存储器的模块化组织 通常，一个由若干个模块组成的主存储器是线性通常，一个由若干个模块组成的主存储器是线性编址的。这些地址在各模块有两种安排方式：一编址的。这些地址在各模块有两种安排方式：一种是种是顺序方式顺序方式，一种是，一种是交叉方式交叉方式。顺序方式顺序方式：模块中的地址是连续的。高位：模块中的地址是连续的。高位地址选地址选择不同的模块择不同的模块,低位地址指向模块内存储字。低位地址指向模块内存储字。某个模块进行存取时，其他模块不工作；某个模块进行存取时，其他模块不工作；某一模块出现故障时，其他模块可以照常工作；某一模块出现故障时，其他模块可以照常工作；通过增添模块来扩充存储器容量比较方便。通过增添模块来扩充存储器容量比较方便。但由于各模块串行工作，存储器的带宽受到了限制。但由于各模块串行工作，存储器的带宽受到了限制。3.4.2多模块交叉存储器多模块交叉存储器 高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院一、顺序方式一、顺序方式如如,M0M3共四个模块，则每个模块共四个模块，则每个模块8个字个字顺序方式顺序方式M0：07M1：815M2：1623M3：24315位地址组织如下：位地址组织如下：XXXXX高位选模块，低位选块内地址高位选模块，低位选块内地址郑州大学 1/16/2023 4:38 PM信息工程学院地址按顺序分配给各模块，与字扩展相同，地址按顺序分配给各模块，与字扩展相同，32各各单元，共单元，共4个模块，每块个模块，每块8个单元。个单元。交叉方式交叉方式特点特点：连续地址分布在相邻的不同模块内，连续地址分布在相邻的不同模块内，同一个模块内的地址都是不连续的。同一个模块内的地址都是不连续的。地址码的低位字段经过译码选择不同地址码的低位字段经过译码选择不同的模块的模块,而高位字段指向相应模块内的存而高位字段指向相应模块内的存储字。储字。这种方式对连续字的成块传送可实现这种方式对连续字的成块传送可实现多模块流水式并行存取，因而可大大提高多模块流水式并行存取，因而可大大提高存储器的带宽。存储器的带宽。高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院每个模块各自以等同的方式与每个模块各自以等同的方式与CPUCPU传送信息。传送信息。CPUCPU同时访问同时访问4 4个模块，由存储器控制部件控制它们分时使用数据总线进个模块，由存储器控制部件控制它们分时使用数据总线进行信息传递。是一种并行存储器结构。行信息传递。是一种并行存储器结构。2.多模块交叉存储器的基本结构多模块交叉存储器的基本结构高速存储器高速存储器CPU存储器控制部件 M0M1M2M3四模块交叉存储器结构框图四模块交叉存储器结构框图0 1 2 30 1 2 34 5 6 74 5 6 7 定量分析定量分析：设模块字长等于数据总线宽度，模设模块字长等于数据总线宽度，模块块存取一个字的存储周期为存取一个字的存储周期为T，总线传送周期为总线传送周期为，存储器的存储器的交叉模块数为交叉模块数为m，为了实现流水线方为了实现流水线方式存取，应当满足式存取，应当满足：T=m（m=T/称为称为交叉存取度交叉存取度）交叉存储器要求其实际模块数交叉存储器要求其实际模块数m必须大于或等必须大于或等于于m，以保证启动某模块后经以保证启动某模块后经m时间再次启动该时间再次启动该模块时，它的上次存取操作已经完成。这样，连模块时，它的上次存取操作已经完成。这样，连续读取续读取m个字所需的时间为：个字所需的时间为：t1=T+(m-1)而顺序方式存储器连续读取而顺序方式存储器连续读取m个字所需时间个字所需时间为为t2=mT。可见，交叉存储器的带宽大大提高了。可见，交叉存储器的带宽大大提高了。高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院m=4m=4的流水线方式存取示意图的流水线方式存取示意图 【例例5】设：存储器容量为设：存储器容量为32字，字长字，字长64位，模块数位，模块数m=4，分别用顺序方式和分别用顺序方式和交叉方式进行组织。存储周期交叉方式进行组织。存储周期T=200ns，数据总线宽度为数据总线宽度为64位，总线传送周期位，总线传送周期=50ns。问顺序存储器和交叉存储器的问顺序存储器和交叉存储器的带宽各是多少带宽各是多少?高速存储器高速存储器 【解解】：顺序和交叉存储器连续读出顺序和交叉存储器连续读出m=4个字的个字的信息总量都是：信息总量都是：q=64位位4=256位位 顺序和交叉存储器连续读出顺序和交叉存储器连续读出4个字所需的时间分别个字所需的时间分别是：是：t2=mT=4200ns=800ns=810-7s;t1=T+(m-1)=200ns+350ns=350ns=3.510-7s顺序存储器和交叉存储器的带宽分别是：顺序存储器和交叉存储器的带宽分别是：W2=q/t2=256(810-7)=32107位位/s;W1=q/t1=256(3.510-7)=73107位位/s高速存储器高速存储器 DRAM存储器读存储器读/写周期时，在行选通信号写周期时，在行选通信号RAS有效下输入行地址，在列选通信号有效下输入行地址，在列选通信号CAS有效有效下输入列地址。下输入列地址。如果是读周期，此位组内容被读出；如果是读周期，此位组内容被读出；如果是写周期，将总线上数据写入此位组。如果是写周期，将总线上数据写入此位组。刷新周期是在刷新周期是在RAS有效下输入刷新地址，此地有效下输入刷新地址，此地址指示的一行所有存储元全部被再生。址指示的一行所有存储元全部被再生。A20A3的的18位地址用于模块位地址用于模块中中256K个存储字的选择。个存储字的选择。A2用模块选择用模块选择，连续的存储字交错分布在两个模，连续的存储字交错分布在两个模块上，偶地址在模块块上，偶地址在模块0，奇地址在模块，奇地址在模块1。3.二模块交叉存储器举例二模块交叉存储器举例高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院DRAMDRAM芯片芯片256K4256K43 18 1 23 18 1 2二模块交叉存储器方框图二模块交叉存储器方框图“存储体存储体-块块-字字”寻址寻址 DRAMDRAM存储器需要逐行定时刷新，而且存储器需要逐行定时刷新，而且,DRAM,DRAM芯片芯片的读出是一种的读出是一种破坏性读出破坏性读出，因此在读取之后要立即按，因此在读取之后要立即按读出信息予以充电再生。读出信息予以充电再生。这样，若这样，若CPUCPU先后两次读取先后两次读取的存储字使用同一的存储字使用同一RASRAS选通信号的话，选通信号的话，CPUCPU在接收到第在接收到第一个存储字之后必须插入等待状态，直至前一存储字一个存储字之后必须插入等待状态，直至前一存储字再生完毕才开始第二个存储字的读取。再生完毕才开始第二个存储字的读取。由于采用由于采用m=2m=2的交叉存取度的成块传送，两个连的交叉存取度的成块传送，两个连续地址字的读取之间不必插入等待状态（续地址字的读取之间不必插入等待状态（无等待存无等待存 取取）。）。高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院无等待状态成块存取示意图无等待状态成块存取示意图3.6 cache3.6 cache存储器存储器3.6.1 3.6.1 cachecache基本原理基本原理3.6.2 3.6.2 主存与主存与cachecache的地址映射的地址映射3.6.3 3.6.3 替换策略替换策略3.6.4 3.6.4 cachecache的写操作策略的写操作策略3.6.5 3.6.5 奔腾奔腾PCPC机的机的cachecachecache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院性能：速度、容量、每位价格性能：速度、容量、每位价格存储系统设计目标存储系统设计目标希望访问速度近似等于存储周期中最小者希望访问速度近似等于存储周期中最小者容量与最大者相近容量与最大者相近每位价格接近最便宜者每位价格接近最便宜者存储体系的基本要求和性能评价存储体系的基本要求和性能评价郑州大学 1/16/2023 4:38 PM信息工程学院存储层次的设计依据（局部性原则）存储层次的设计依据（局部性原则）程序的局部性（程序的局部性（Locality）原则）原则 在一段时间内，典型程序所需的地址在一段时间内，典型程序所需的地址趋向于集中在一个较小的范围内，在给定的趋向于集中在一个较小的范围内，在给定的主存内容被处理后，下一个要处理的指令或主存内容被处理后，下一个要处理的指令或数据极大可能的在该主存单元附近区域，即数据极大可能的在该主存单元附近区域，即程序的执行时的地址不是随机分布的，而是程序的执行时的地址不是随机分布的，而是自然的簇集成自然的簇集成“块块”和和“页页”。郑州大学 1/16/2023 4:38 PM信息工程学院空间的局部性空间的局部性(Spatial locality)当处理机访问某个单元时，该单元附近的存储单当处理机访问某个单元时，该单元附近的存储单元最有可能被随后访问。元最有可能被随后访问。时间的局部性时间的局部性(Temporal locality)处理机访问某个单元后，该单元最有可能再次被处理机访问某个单元后，该单元最有可能再次被访问。访问。处理机在某段时间经常使用的空间范围被称作处理机在某段时间经常使用的空间范围被称作工作集合工作集合（working set）。）。在几乎所有的程序中，在几乎所有的程序中，工作集合的改变是非常缓慢的，有时甚至是不变的工作集合的改变是非常缓慢的，有时甚至是不变的。3.5.1 cache基本原理基本原理1.cache的功能的功能 cache是介于是介于CPU和主存之间的小和主存之间的小容量存储器，存取速度比主存快容量存储器，存取速度比主存快(一般一般可达可达510倍以上）。它能高速地向倍以上）。它能高速地向CPU提供指令和数据，加快程序的执行速度。提供指令和数据，加快程序的执行速度。它是为了解决它是为了解决CPU和主存之间速度和主存之间速度不匹配而采用的一项重要技术。不匹配而采用的一项重要技术。cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院cache与与CPU的关系的关系 为追求高速，包括管理在内的全部功能为追求高速，包括管理在内的全部功能由硬件实现。对程序员是透明的。由硬件实现。对程序员是透明的。2.cache2.cache的基本原理的基本原理 CPU与与cache之间的数据交换之间的数据交换以以字字为单位，为单位，cache与主存之间的与主存之间的数据交换是以数据交换是以块块为单位。为单位。一个块由一个块由通常若干定长的字组成。通常若干定长的字组成。cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院2.cache2.cache的基本原理的基本原理 基本原理基本原理：当当CPU要读取主存中一个要读取主存中一个字时，将内存地址字时，将内存地址同时发给同时发给cache和主存和主存。cache控制逻辑依据地址，判断该字当前是控制逻辑依据地址，判断该字当前是否已在否已在 cache中：中：若是若是，将此字立即传送给，将此字立即传送给CPU，无需再访无需再访问主存（让主存访问失效）；问主存（让主存访问失效）；若非若非，用主存读周期把此字从主存读出送，用主存读周期把此字从主存读出送到到CPU，与此同时，把含有这个字的数据块与此同时，把含有这个字的数据块从主存读出并装入到从主存读出并装入到cache中，将中，将Cache中中较旧的内容（块）替换掉较旧的内容（块）替换掉。替换控制由管理替换控制由管理cache使用情况的硬件使用情况的硬件逻辑电路来实现，最常用的替换算法逻辑电路来实现，最常用的替换算法为为LRU。郑州大学 1/16/2023 4:38 PM信息工程学院LRU管理逻辑相联存储器CPU主存cache原理图原理图存放Cache地址Cache16字的容量郑州大学 1/16/2023 4:38 PM信息工程学院相联存储器按内容寻址的存储器按内容寻址的存储器 把存储单元所存内容的某一部分作为检索把存储单元所存内容的某一部分作为检索项，去检索该存储器，并对存储器中与该检项，去检索该存储器，并对存储器中与该检索项符合的存储单元内容进行读出或写入索项符合的存储单元内容进行读出或写入3.cache的命中率的命中率 增增加加cache的的目目的的，就就是是希希望望在在性性能能上上使使主主存存的的平平均均读读出出时时间间尽尽可可能能接接近近cache的的读读出出时时间间。因因此此,cache的的命命中中率率应应接接近近于于1。由由程程序序访访问问的的局局部性原理可知，这是可能的。部性原理可知，这是可能的。在在一一个个程程序序执执行行期期间间，设设Nc表表示示cache完完成成存存取取的的总总次次数数，Nm表表示示主主存存完完成成存存取取的的总总次次数数，h定定义为命中率，则有：义为命中率，则有：h=NcNc+Nm(3.4)cache存储器存储器 若若tc表示命中时的表示命中时的cache访问时间，访问时间，tm表示未表示未命中时的主存访问时间，（命中时的主存访问时间，（1-h）表示未命中率，表示未命中率，则则cache/主存系统的平均访问时间主存系统的平均访问时间ta为：为：ta=htc+(1-h)tm（3.5）设设r=tm/tc表示主存慢于表示主存慢于cache的倍率的倍率,e表示访表示访问效率，则有问效率，则有:tce=ta=tchtc+(1-h)tm1h+(1-h)r=1r+(1-r)h(3.6)cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院 为提高访问效率，命中率为提高访问效率，命中率h h越接越接近近1 1越好，越好，r r值以值以5 51010为宜，不宜太为宜，不宜太大大(防止防止CacheCache访问失效而造成过大访问失效而造成过大的时间损耗）。的时间损耗）。命中率命中率h h与与程序的行为、程序的行为、cachecache的容量、组织方式、块的大小有关的容量、组织方式、块的大小有关。【例例6】CPU执行一段程序时，执行一段程序时，cache完成存取的次数完成存取的次数为为1900次，主存完成存取的次数为次，主存完成存取的次数为100次，已知次，已知cache存取周期为存取周期为50ns，主存存取周期为主存存取周期为250ns，求，求cache/主存系统的效率和平均访问时间。主存系统的效率和平均访问时间。【解解】:h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=250ns/50ns=5 e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3%ta=tc/e=50ns/0.833=60ns 或者，或者，ta=htc+(1-h)tm=60nscache存储器存储器3.6.2.主存与主存与cache的地址映射的地址映射 cache的容量很小，它保存的内容只是的容量很小，它保存的内容只是主存内容的一个子集，且主存内容的一个子集，且cache与主存与主存的数据交换是以的数据交换是以块块为单位。为单位。地址映射地址映射:即是应用某种方法把主即是应用某种方法把主存地址定位到存地址定位到cache中。中。地址映射方式地址映射方式:全相联全相联、直接直接、组相联组相联。郑州大学 1/16/2023 4:38 PM信息工程学院3.6.2.主存与主存与cache的地址映射的地址映射 cache的的数据块数据块大小称为大小称为行行，用，用Li表示，表示，其中其中i=0,1,m-1,共有共有m=2r行。行。主存的主存的数据块数据块大小称为大小称为块块，用用Bj表示，表示，其中其中j=0,1,n-1,共有共有n=2s块。块。行与块是等长的行与块是等长的，每个块（行）由，每个块（行）由k=2w个连续的字组成，字是个连续的字组成，字是CPU每次访每次访问存储器时可存取的最小单位。问存储器时可存取的最小单位。1.1.全相联映射方式全相联映射方式 主存中一个块的地址与块的内容一起主存中一个块的地址与块的内容一起存于存于cache的行中，其中块地址存于的行中，其中块地址存于cache行的标记部分中。行的标记部分中。优点：优点：是可使主存的一个块直接拷贝是可使主存的一个块直接拷贝到到cache中的任意一行上，非常灵活。中的任意一行上，非常灵活。缺点：缺点：是比较器电路难于设计和实现是比较器电路难于设计和实现,尤其当尤其当Cache有一定容量时，查找某块有一定容量时，查找某块（行）比较麻烦。因此只适合于小容量（行）比较麻烦。因此只适合于小容量cache采用。采用。cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院全相联映射的全相联映射的示意图示意图最多可能有最多可能有256256块块与该行相映射与该行相映射郑州大学 1/16/2023 4:38 PM信息工程学院cache存储器存储器CAMCAMCache的该行保存主存的该行保存主存块的块号块的块号全相联映射全相联映射示意图示意图2.2.直接映射方式直接映射方式 这也是这也是一种多对一的映射一种多对一的映射关系，但关系，但一个主存块只能拷贝到一个主存块只能拷贝到cache的一个特的一个特定行位置上去。定行位置上去。cache的行号的行号i和主存的块号和主存的块号j有如下有如下关系：关系：i=j mod m（m为为cache中的总行数）中的总行数）cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院直接映射方式的直接映射方式的示意图演示示意图演示 最多可能有最多可能有3232块块与该行相映射与该行相映射郑州大学 1/16/2023 4:38 PM信息工程学院cache存储器存储器(主存的块号主存的块号j)mod(cache的行数的行数m)(主存的块号主存的块号j)(cache的行数的行数m)的的商商记录记录(主存的块号主存的块号j)mod(cache的行数的行数m)相同的所相同的所有的有的tag直接映射方式的直接映射方式的示意图示意图 郑州大学 1/16/2023 4:38 PM信息工程学院直接映射的检索过程：直接映射的检索过程：CPU送来主存地址后，首先用送来主存地址后，首先用r位行号找到位行号找到Cache中某一行，然后用标记与主存地址的标记中某一行，然后用标记与主存地址的标记部分在比较器中进行比较。部分在比较器中进行比较。如果符合，则命中，可根据字地址访问如果符合，则命中，可根据字地址访问Cache中的字；中的字；如果不符合，则未命中，就要从主存读入如果不符合，则未命中，就要从主存读入所要求的字。所要求的字。优点优点：硬件简单，成本低。：硬件简单，成本低。缺点缺点：每个主存块只有一个固定的行位置可：每个主存块只有一个固定的行位置可存放，容易产生冲突和存放，容易产生冲突和Cache空间使用效率的降空间使用效率的降低。因此一般只适合在大容量低。因此一般只适合在大容量cache中采用。中采用。3.3.组相联映射方式组相联映射方式 这种方式是前两种方式的折衷方案。这种方式是前两种方式的折衷方案。基本思想基本思想：将将cachecache分成分成u u组，每组组，每组v v行。主存块与行。主存块与CacheCache组之间采用直接映射方式，而每个组内部组之间采用直接映射方式，而每个组内部的块、行之间则采用全相联映射方式，即主存块的块、行之间则采用全相联映射方式，即主存块可以存放到固定组的任一行中。可以存放到固定组的任一行中。CacheCache被分为：被分为：u u（组）组）vv（行）行）cachecache组号组号q q与与主存块号主存块号j j的关系为：的关系为：q qj j（mod umod u）cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院3.3.组相联映射方式组相联映射方式 组相联映射方式中的每组行数组相联映射方式中的每组行数v v一般一般取值较小，常称之为取值较小，常称之为V V路组相联路组相联cachecache，这种规模的这种规模的v v路比较器容易设计和实现。路比较器容易设计和实现。而块在组中的排放又有一定的灵活性而块在组中的排放又有一定的灵活性,可可以减少冲突。以减少冲突。郑州大学 1/16/2023 4:38 PM信息工程学院组相联映射的组相联映射的示意图演示示意图演示组间采用直接映象，组内为全相联组间采用直接映象，组内为全相联组间采用直接映象，组内为全相联组间采用直接映象，组内为全相联最多可能有最多可能有6464块块与该组与该组/行相映射行相映射郑州大学 1/16/2023 4:38 PM信息工程学院(主存的块号主存的块号j)mod(cache的的组数组数u)2d=u(主存的块号主存的块号j)(cache的组数的组数u)的的商商每组有每组有v行，主存映射到行，主存映射到cache的的同一组中可有同一组中可有v种选择种选择3.5.3.3.5.3.替换策略替换策略 cachecache工作原理要求它尽量保存工作原理要求它尽量保存最新数据最新数据，因此，必然要，因此，必然要产生新、旧内容的替换问题。产生新、旧内容的替换问题。对直接映射的对直接映射的cachecache来说，只要把此特定位置上的原主存来说，只要把此特定位置上的原主存块换出块换出cachecache即可。即可。对全相联和组相联对全相联和组相联cachecache来说，来说，就要从允许存放新主存块就要从允许存放新主存块的若干特定行中选取一行换出。的若干特定行中选取一行换出。常用的替换算法如下图所示：常用的替换算法如下图所示：cache存储器存储器最不经常使用最不经常使用(Least Frequently Used,LFU),LFU)算法算法 将将Cache中一段时间内被访问次数最少的中一段时间内被访问次数最少的行数据换出。每行设置一个计数器，从行数据换出。每行设置一个计数器，从0开始计开始计数，每访问一次，被访行的计数器增数，每访问一次，被访行的计数器增1。当需替。当需替换时，将计数值最小的行换出，同时将这些行换时，将计数值最小的行换出，同时将这些行的计数器都清零。的计数器都清零。这种算法将计数周期限定在对这些特定行两这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，不能严格反映近期次替换之间的间隔时间内，不能严格反映近期访问情况。访问情况。cache存储器存储器近期最少使用近期最少使用(Least Recently Used,LRU)算法算法 LRU算法算法将近期内长久未被访问过的行换出。将近期内长久未被访问过的行换出。每行也设置一个计数器，每行也设置一个计数器，cache每命中一次，每命中一次，命中行计数器清命中行计数器清0，其它各行计数器增，其它各行计数器增1。当需。当需要替换时，将计数值最大的行换出。要替换时，将计数值最大的行换出。这种算法保护了刚拷贝到这种算法保护了刚拷贝到cache中的新数据中的新数据行，有较高的命中率。行，有较高的命中率。随机替换随机替换 随机替换策略从特定的行位置中随机地选随机替换策略从特定的行位置中随机地选取一行换出。在硬件上容易实现，且速度也比取一行换出。在硬件上容易实现，且速度也比前两种策略快。缺点是降低了命中率和前两种策略快。缺点是降低了命中率和cache工作效率。工作效率。cache存储器存储器3.5.4 cache3.5.4 cache的写操作策略的写操作策略 注意到注意到：当当CPUCPU对对cachecache有写入操作时，就可能会更改有写入操作时，就可能会更改cachecache的内容。而的内容。而CacheCache内容的内容的“原件原件”保留在主存中。因保留在主存中。因为数据真正的保存地点是在主存中，为数据真正的保存地点是在主存中，CacheCache所保存的内容只所保存的内容只是一部分主存内容的镜象而已。所以，应当采用方法，使是一部分主存内容的镜象而已。所以，应当采用方法，使cachecache内容和主存内容保持一致内容和主存内容保持一致，CacheCache的写操作策略就是的写操作策略就是解决这个问题。解决这个问题。cache存储器存储器写回法写回法(Write Back(Write Back，WB)WB)当当CPU写写cache命中时，只修改命中时，只修改cache的内容，而的内容，而不立即写入主存；只有当此行被换出时才写回主存。不立即写入主存；只有当此行被换出时才写回主存。若写未命中，则将此块整个拷贝到若写未命中，则将此块整个拷贝到cache后对其后对其进行修改。进行修改。这种方法减少了访问主存的次数，但是存在不一这种方法减少了访问主存的次数，但是存在不一致性的隐患。致性的隐患。实现这种方法时，每个实现这种方法时，每个cache行必须配置一个修行必须配置一个修改位，以反映此行是否被改位，以反映此行是否被CPU修改过。修改过。cache存储器存储器CPUCache主主 存存更新写入全写法（全写法（Write ThroughWrite Through，WTWT）当写当写cache命中时，命中时，cache与主存同时发生写与主存同时发生写修改，因而较好地维护了修改，因而较好地维护了cache与主存内容的一与主存内容的一致性。致性。当写当写cache未命中时，直接向主存进行写入。未命中时，直接向主存进行写入。cache中每行无需设置一个修改位以及相应的判中每行无需设置一个修改位以及相应的判断逻辑。断逻辑。缺点缺点是降低了是降低了cache的功效。的功效。cache存储器存储器CPUCache主主 存存郑州大学 1/16/2023 4:38 PM信息工程学院 在写在写Cache 不命中的情况下不命中的情况下，是否把所写是否把所写字在内的块读入字在内的块读入Cache？读入时可采用两种方法。读入时可采用两种方法。按写不分配法按写不分配法“WTNWA(WriteThrough-with.NO-Write-Allocate)”：写写Cache不命不命中，只把所要写的字写入主存，而包括所中，只把所要写的字写入主存，而包括所写的字在内的块不写入写的字在内的块不写入Cache。“按写分配法按写分配法WTWA”：写写Cache未命中，未命中，把所要写的字写入主存，而包括所写的字把所要写的字写入主存，而包括所写的字在内的块写入在内的块写入Cache。写一次法写一次法（基于写回法并结合全写法的写策略）（基于写回法并结合全写法的写策略）写命中与写未命中的处理方法与写回法基写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。本相同，只是第一次写命中时要同时写入主存。这便于维护系统全部这便于维护系统全部cache的一致性。的一致性。cache存储器存储器郑州大学 1/16/2023 4:38 PM信息工程学院3.6 3.6 虚拟存储器虚拟存储器3.6.1 3.6.1 虚拟存储器的基本概念虚拟存储器的基本概念3.6.2 3.6.2 页式虚拟存储器页式虚拟存储器3.6.3 3.6.3 段式虚拟存储器段式虚拟存储器3.6.4 3.6.4 段页式虚拟存储器段页式虚拟存储器3.6.5 3.6.5 替换算法替换算法3.6.6 3.6.6 奔腾系列机的虚拟存储组织奔腾系列机的虚拟存储组织虚拟存储器虚拟存储器P2821.1.虚拟存储器中关于地址与空间的若干名词：虚拟存储器中关于地址与空间的若干名词：物理地址（又称实地址）：物理地址（又称实地址）：（对应主存物理空间对应主存物理空间）由由CPU地址引脚送出，用于访问主存的地址。地址引脚送出，用于访问主存的地址。虚拟地址（又称虚地址）：虚拟地址（又称虚地址）：（对应主存逻辑空间对应主存逻辑空间）由编译程序生成的，是程序的逻辑地址。工作在由编译程序生成的，是程序的逻辑地址。工作在虚拟地址模式下虚拟地址模式下的的CPU理解这些虚拟地址，并将理解这些虚拟地址，并将他们转换成物理地址。若虚拟地址长为他们转换成物理地址。若虚拟地址长为n位，则虚位，则虚拟地址空间的大小可用拟地址空间的大小可用2n来表示。因虚拟存储器来表示。因虚拟存储器的内容要保存在磁盘上，故其地址空间的大小实的内容要保存在磁盘上，故其地址空间的大小实际上受到辅助存储器容量的限制。际上受到辅助存储器容量的限制。高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院主存主存-外存外存层次和层次和cache-cache-主存主存层次用的地址变换映射方层次用的地址变换映射方法和替换策略是相同的，都基于法和替换策略是相同的，都基于程序局部性原理程序局部性原理。遵循的原则：遵循的原则：把程序中最近把程序中最近常用常用的部分驻留在的部分驻留在高速高速存储器中。存储器中。一旦这部分变得一旦这部分变得不常用不常用了，把它们送回到了，把它们送回到低速低速的的存储器中。存储器中。这种换入换出是由这种换入换出是由硬件或操作系统硬件或操作系统完成的，对用完成的，对用户是户是透明透明的。的。力图使存储系统在力图使存储系统在性能性能上接近高速存储器、在上接近高速存储器、在价价格格上接近低速存储器。上接近低速存储器。高速存储器高速存储器郑州大学 1/16/2023 4:38 PM信息工程学院v2.虚存的访问过程虚存的访问过程v虚存空间的用户程序按照虚存空间的用户程序按照虚地址编程虚地址编程并存放并存放在辅存中。程序运行时，由在辅存中。程序运行时，由地址变换机构地址变换机构依依据当时分配给该程序的实地址空间把程序的据当时分配给该程序的实地址空间把程序的一部分调入实存。每次访存时，首先判断该一部分调入实存。每次访存时，首先判断该虚地址所对应的部分是否在实存中：如果是，虚地址所对应的部分是否在实存中：如果是，则进行地址转换并用实地址访问主存；否则，则进行地址转换并用实地址访问主存；否则，按照某种算法将辅存中的部分程序调度进内按照某种算法将辅存中的部分程序调度进内存，再按同样的方法访问主存。存，再按同样的方法访问主存。郑州大学 1/16/2023 4:38 PM信息工程学院v由此可见，由此可见，每个程序的虚地址空间可以每个程序的虚地址空间可以远大于实地址空间，也可以远小于实地远大于实地址空间，也可以远小于实地址空间址空间。前一种情况以提高存储容量为。前一种情况以提高存储容量为目的，后一种情况则以地址变换为目的。目的，后一种情况则以地址变换为目的。后者通常出现在多用户或多任务系统中：后者通常出现在多用户或多任务系统中：实存空间较大，而单个任务并不需要很实存空间较大，而单个任务并不需要很大的地址空间，较