计算机组成原理计算机组成原理1计计 算算 机机 组组 成成 原原 理理Monday, July 29, 2024存存储系系统 计算机组成原理计算机组成原理2 通过本章的学习，要求掌握高速缓冲存储器cache的工作原理和理解虚拟存储器的工作原理，能够分析cahce和虚拟存储器的命中情况通过对命中情况的分析，对cahce和虚拟存储器的工作原理有深入的理解 本章教学内容：本章教学内容： 1、存储系统基本概念 2、cache存储器 3、虚拟存储器 本章重点：本章重点： 存储系统基本概念，Cache的工作原理及其地址映射方式，LRU替换策略 本章难点：本章难点： Cache的工作原理及其地址映射方式，虚拟存储器的工作原理存储系统存储系统 计算机组成原理计算机组成原理31．存储容量：要求大容量2．价格：要求价格低 主存速度的提高始终跟不上CPU的发展据统计，CPU的速度平均每年提高60%，而组成主存的DRAM的速度平均每年只改进7%由SRAM组成的高速缓冲存储器的运行速度则接近甚至等于CPU的速度1、存储层次概述存储器性能指标3．速度: 高速度带宽实际：速度、容量、价格存在巨大的矛盾希望：高速度、大容量、低价格 计算机组成原理计算机组成原理4 存储体系：存储体系：把各种不同存储容量、不同存取速度、不同价格的存储器，组成层次结构，并通过管理软件和辅助硬件将不同性能的存储器组合成有机的整体，称为计算机的存储层次或存储体系。
存储器系统的层次结构如下图所示：CPUCPU内的寄存器内的寄存器高速缓存高速缓存主存储器主存储器磁盘存储器磁盘存储器磁带机磁带机容容量量和和存存取取时时间间增增加加每每位位成成本本增增加加 为了解决对存储器要求容量大，速度快，成本低三者之间的矛盾，目前通常采用多级存储器体系结构，即高速缓冲存储器、虚拟存储器 计算机组成原理计算机组成原理5较低级：与处理器较远的存储级 ——容量较大、速度较慢、使用较廉价的技术工艺存储器系统的层次结构的特点：存储器系统的层次结构的特点：在任何指定时间，数据只能在相邻的两级之间拷贝：较高级：与处理器较近的存储级 ——容量较小、速度较快、使用较昂贵的技术工艺 计算机组成原理计算机组成原理62、程序访问的局部性原理 CPU访问存储器时，无论是取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问程序循环、堆栈)空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的指令顺序执行、数组存放) 这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序访问的局部性原理。
int a[M][N];for (i = 0; i < M; i++) for (j = 0; j < N; j++) sum += a[i][j];int a[M][N];for (j = 0; j < N; j++) for (i = 0; i < M; i++) sum += a[i][j];哪个程序具有更好的局部性 计算机组成原理计算机组成原理7 程序地址的分布是连续的，加上循环程序段和子程序段要重复执行多次，因此，对程序地址的访问具有相对集中的倾向 程序访问的局部性主要表现： 数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中其它原因：优先考虑最近经常被访问的代码最近可能被访问的数据放在小的但高速存储器里容量小、离CPU近的高速存储器存放最近要访问的数据 在高速机器中，信号传输是延迟的一个重要原因而大的存储器因地址译码级数多，信号延迟会更大相同器件条件下，小容量存储器比大容量存储器快 计算机组成原理计算机组成原理8 根据局部性原理，可以在主存和根据局部性原理，可以在主存和CPUCPU之间设置一个之间设置一个高速高速的的容量相对较小容量相对较小的存储器，如果当前正在执行的程序和数据存放的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在程序运行时，不必从主存储器取指令和取在这个存储器中，在程序运行时，不必从主存储器取指令和取数据，只需数据，只需访问这个高速存储器，以提高程序运行速度。
这个访问这个高速存储器，以提高程序运行速度这个存储器称作高速缓冲存储器存储器称作高速缓冲存储器CacheCache CacheCache由高速的由高速的SRAMSRAM组成组成，，它的工作速度数倍于主存，全它的工作速度数倍于主存，全部功能由部功能由硬件硬件实现，并且对实现，并且对程序员是透明程序员是透明的cachecache基本原理基本原理 计算机组成原理计算机组成原理9cachecache的基本结构的基本结构它由它由cache存储体、地址映象变换机构、存储体、地址映象变换机构、cache替换机构几大模块组成替换机构几大模块组成 计算机组成原理计算机组成原理10CacheCache概念：概念： （（1 1））CPUCPU与主存储器之间的一种高速缓冲装置与主存储器之间的一种高速缓冲装置 （（2 2））Cache-Cache-主存层次结构：由硬件地址变换和控制调度主存层次结构：由硬件地址变换和控制调度CacheCache具有如下特点：具有如下特点：①①位于位于CPUCPU与主存之间，是存储器层次结构中级别最高的一级；与主存之间，是存储器层次结构中级别最高的一级；②②容量比主存小，目前一般有数ＫＢ到数ＭＢ；容量比主存小，目前一般有数ＫＢ到数ＭＢ；③③速度一般比主存快５－１０倍速度一般比主存快５－１０倍, ,通常由存储速度高的双极型三通常由存储速度高的双极型三极管或极管或SRAMSRAM组成；组成；④④其内容是主存的部分副本；其内容是主存的部分副本；⑤⑤其用途可用来存放指令，也可用来存放数据；其用途可用来存放指令，也可用来存放数据；⑥⑥快存的功能全部由硬件实现，并对程序员透明。
快存的功能全部由硬件实现，并对程序员透明 计算机组成原理计算机组成原理11(2)(2)当比较结果不相等时，说明需要的数据尚未调入当比较结果不相等时，说明需要的数据尚未调入Cache，那，那 么就要把么就要把该数据所在的整个字块从主存一次调进来该数据所在的整个字块从主存一次调进来 前一种情况称为访问前一种情况称为访问Cache命中，后一种情况称为访问命中，后一种情况称为访问Cache不命中cachecache的命中的命中 任何时候都有一些主存块处在任何时候都有一些主存块处在CacheCache中 当当CPU发出读请求时，将主存地址发出读请求时，将主存地址s位（或位（或s位中的一部分）与位中的一部分）与Cache某块的某块的标记标记相比较，根据其比较结果是否相等而区分出两相比较，根据其比较结果是否相等而区分出两种情况：种情况： (1)(1)当比较结果相等时，说明需要的数据已在当比较结果相等时，说明需要的数据已在Cache中，那么直中，那么直接访问接访问Cache就行了，在就行了，在CPU与与Cache之间，通常一次传送一个之间，通常一次传送一个字；字； 计算机组成原理计算机组成原理12读请求命中与缺失命中与缺失命中（命中（HIT））缺失（缺失（MISS））读请求CacheCache缺失造成缺失造成访问速度急速度急剧下降下降 计算机组成原理计算机组成原理13cachecache的命中率的命中率• • 命中率命中率指指CPUCPU所要访问的信息在所要访问的信息在CacheCache中的比率；中的比率；• • 而将所要访问的信息不在而将所要访问的信息不在CacheCache中的比率称为中的比率称为失效率失效率。
增加增加cachecache的目的，就是在性能上使主存的平均读出的目的，就是在性能上使主存的平均读出时间尽可能接近时间尽可能接近cachecache的读出时间因此的读出时间因此, cache, cache的命中率的命中率应接近于应接近于1 1 由于程序访问的局部性由于程序访问的局部性 ，这是可能的这是可能的 在一个程序执行期间：在一个程序执行期间： 设设N Nc c表示表示cachecache完成存取的总次数，完成存取的总次数， N Nm m表示主存完成存取的总次数，表示主存完成存取的总次数， h h定义为命中率，则有：定义为命中率，则有： 计算机组成原理计算机组成原理14若若 tc表示命中时的表示命中时的cache访问时间，访问时间， tm表示未命中时的主存访问时间，表示未命中时的主存访问时间， 1-h表示不命中率，表示不命中率，则则cache/主存系统主存系统的平均访问时间的平均访问时间ta为：为：ta=htc+(1-h)tm 我们追求的目标是：我们追求的目标是： 以较小的硬件代价使以较小的硬件代价使cache/主存系统主存系统的平均访问的平均访问时间时间ta越接近越接近tc越好。
越好 计算机组成原理计算机组成原理15设设 r=tm/tc表示主存慢于表示主存慢于cache的倍率的倍率, e表示访问效率，则有表示访问效率，则有: 为提高访问效率：为提高访问效率： 命中率命中率h越接近越接近1越好，越好，r值以值以5—10为宜，不宜太大为宜，不宜太大 命中率命中率h与程序的行为、与程序的行为、cache的容量、组织方式、的容量、组织方式、块的大小有关块的大小有关 计算机组成原理计算机组成原理16例：例：CPUCPU执行一段程序时，执行一段程序时，cachecache完成存取的次数为完成存取的次数为19001900次，主次，主存完成存取的次数为存完成存取的次数为100100次，已知次，已知cachecache存取周期为存取周期为50ns50ns，主存，主存存取周期为存取周期为250ns250ns，求，求cache/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例例: :已知已知CacheCache存储周期为存储周期为40ns,40ns,主存存储周期为主存存储周期为200ns, Cache 200ns, Cache / /主存系统平均访问时间为主存系统平均访问时间为50ns,50ns,求求CacheCache的命中率是多少的命中率是多少? ?解解: : 因为因为 tata=htc+(1-h)tm=htc+(1-h)tm 所以所以 h=(h=(ta-tm)/(tc-tmta-tm)/(tc-tm)=(50-200)/(40-200)=15/16 )=(50-200)/(40-200)=15/16 计算机组成原理计算机组成原理17（（1 1））数据块在数据块在CacheCache中存放在哪个位置？即定位问题中存放在哪个位置？即定位问题（地址映（地址映象）象） 。
如果一个块存放在某一如果一个块存放在某一CacheCache中，怎样确定并找到该块，中，怎样确定并找到该块，即寻址问题即寻址问题（地址变换）（地址变换）CacheCache结构设计必须解决的问题：结构设计必须解决的问题：如何存放，如何访问，如何替换，如何改写？如何存放，如何访问，如何替换，如何改写？（（3））在写访问时，写入在写访问时，写入Cache必须在适当的时候写回主存储必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数器，何时写？写操作时采用什么策略保证两级存储器间的数据据一致性一致性写操作失配时是否将访问块取入高层存储器写操作失配时是否将访问块取入高层存储器2））不命中时将从主存储器中访问，并将该块调入不命中时将从主存储器中访问，并将该块调入Cache中，但是如果中，但是如果Cache中已无空闲空间，则势必将中已无空闲空间，则势必将Cache中的中的某一块调出，但应调出那一块，即某一块调出，但应调出那一块，即替换问题替换问题 计算机组成原理计算机组成原理18• • 地址映象地址映象 把把主主存存块块按按照照某某种种规规则则（（函函数数或或方方法法））装装入入或或定定位位到到CacheCache中的过程称中的过程称地址映象地址映象。
• • 地址变换地址变换 信息按这种映象关系装入信息按这种映象关系装入Cache后，执行程序时，将主存地后，执行程序时，将主存地址变换成址变换成 Cache地址的变换过程叫做地址的变换过程叫做地址变换地址变换 地址地址映象和变换映象和变换密切相关密切相关 使用使用CacheCache的动力在于它的高速，因此也要求这个地址变换的动力在于它的高速，因此也要求这个地址变换过程尽可能地快，故此过程是以硬件完成的这带来的另一好过程尽可能地快，故此过程是以硬件完成的这带来的另一好处是处是CacheCache的透明性，除了程序运行速度提高之外，用户包括的透明性，除了程序运行速度提高之外，用户包括系统软件编制人员，丝毫未感觉到系统软件编制人员，丝毫未感觉到CacheCache的存在1.1.地址映象地址映象( (映射映射) )与地址变换与地址变换基本的地址映象方式：基本的地址映象方式：直接映象；直接映象； 全相连映象；组相连映象全相连映象；组相连映象 计算机组成原理计算机组成原理19 在高速缓冲存储器中在高速缓冲存储器中, ,把把CacheCache和主存机械等分为和主存机械等分为相同大小相同大小的块的块, ,每一块是由若干个字每一块是由若干个字( (或字节或字节) )组成组成. . 块块0 0块块1 1块块1515CacheCache标记标记标记标记标记标记块块0 0块块1 1块块20472047主存主存m m位位 块块……字字0 0字字1 1字字511511 由于由于CacheCache的块数远小于主存的块数，因此一个的块数远小于主存的块数，因此一个CacheCache不能不能唯一地、永久地只对应一个贮存块，在唯一地、永久地只对应一个贮存块，在CacheCache中，每一块外加有中，每一块外加有一个标记，指明它是主存的哪一块的副本一个标记，指明它是主存的哪一块的副本( (拷贝拷贝) )。
例：例：某机某机主存容量主存容量为为1MB1MB, ,划分为划分为20482048块块, ,每块每块512B;512B;CacheCache容量容量为为8KB8KB, ,划分为划分为1616块块, ,每块每块512B512B 计算机组成原理计算机组成原理20 因刚加电时所有标记位都为因刚加电时所有标记位都为““0”0”，开始执行程序时，，开始执行程序时，命中率较低另外命中率较低另外CacheCache的命中率还与程序本身有关，即的命中率还与程序本身有关，即不同的程序，其命中率可能不同不同的程序，其命中率可能不同标记的有效位标记的有效位 每个标记设置有一个有效位机器每个标记设置有一个有效位机器加电启动时，加电启动时，Reset信号将所有标记信号将所有标记的有效位置的有效位置“0”，即无效程序执，即无效程序执行过程中，行过程中，Cache不命中时，逐步将不命中时，逐步将指令块或数据块从主存调入指令块或数据块从主存调入Cache中中的某一块，并将这一块标记的有效位的某一块，并将这一块标记的有效位置置“1”，当再次用到这一块中的指，当再次用到这一块中的指令或数据时，可直接从令或数据时，可直接从Cache中取指中取指令或数据。
令或数据字块字块0 0字块字块1 1字块字块L Lm-1m-1~ ~~ ~~ ~~ ~...... ............标记标记CacheCache0 01 12 2r r-1-1 标记标记有效位有效位 计算机组成原理计算机组成原理211 1）直接映射方式）直接映射方式 这是一种多对一的映射关系，但一个这是一种多对一的映射关系，但一个主存块只能映象到主存块只能映象到Cache的一个特定块位置上去的一个特定块位置上去 Cache的第的第i块块和和主存的第主存的第j块块有如下函数关系：有如下函数关系： i = j mod m ( m为为Cache的总块数）的总块数） i =0,1,2,…,m-1 j=0,1,2,…,n-1在这种映象方式中：在这种映象方式中：主存的第主存的第0 0块，第块，第1616块，第块，第3232块，块，……，只能映象到，只能映象到CacheCache的第的第0 0块；块；而主存的第而主存的第1 1块，第块，第1717块，第块，第3333块，块，……，只能映象到，只能映象到CacheCache的的第第1 1块；块；………… 计算机组成原理计算机组成原理22直接映象直接映象CacheCache地址地址4 4位位99位位主存地址主存地址7 7位位4 4位位99位位1111位位99位位主存地址主存地址7 7位位 计算机组成原理计算机组成原理23优点优点: :硬件简单硬件简单, ,成本低成本低 缺点缺点: :块冲突率很高块冲突率很高直接映象的直接映象的地址变换方法地址变换方法 计算机组成原理计算机组成原理24优点优点: : 实实现现简简单单，，只只需需利利用用主主存存地地址址块块号号字字段段直直接接判判断断，，即即可可确确定定所需字块是否已在所需字块是否已在Cache中。
中 缺点：缺点： 不不够够灵灵活活，，主主存存的的多多个个字字块块只只能能对对应应唯唯一一的的Cache字字块块，，因因此此，，即即使使Cache别别的的地地址址空空着着也也不不能能占占用用Cache存存储储空空间间得得不到充分利用，降低了命中率不到充分利用，降低了命中率 计算机组成原理计算机组成原理25直接映射地址变换 计算机组成原理计算机组成原理26例：例：设有一个设有一个cachecache的容量为的容量为2K2K字，每个块为字，每个块为1616字，求字，求(1) (1) 该该cachecache可容纳多少个块？可容纳多少个块？(2) (2) 如果主存的容量是如果主存的容量是256K256K字，则有多少个块？字，则有多少个块？(3) (3) 主存的地址有多少位？主存的地址有多少位？cachecache地址有多少位？地址有多少位？(4) (4) 在直接映象方式下，主存中的第在直接映象方式下，主存中的第i i块映象到块映象到cachecache中哪一个中哪一个块中？块中？(5) (5) 进行地址映象时，存储器的地址分成哪几段？各段分别有进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？多少位？解：解：(1) cache中有中有2048/16=128个块。
个块2) 主存有主存有256K/16=16384个块3) cache容量为容量为2K=211字，所以字，所以cache字地址为字地址为11位4) 主存中的第主存中的第i块映象到块映象到cache中第中第 i mod 128个块中5) 存储器的字地址分成三段：存储器的字地址分成三段：区号、块号、块内字地址区号、块号、块内字地址 区号的长度为区号的长度为18-11=7位，块号为位，块号为7位块内字地址为位块内字地址为4位 计算机组成原理计算机组成原理27块块 0块块 1块块 15CacheCache标记标记标记标记标记标记标记标记标记标记标记标记.........块块0块块1块块 15块块 16块块 17块块31块块2047主存主存TagTag2 2）全相联映象方式）全相联映象方式Cache地址地址4 4位位 9 9 位位1111位位 9 9 位位主存地址主存地址1111位位 允许主存中的每一个字块映象到允许主存中的每一个字块映象到CacheCache的任何一个字块位置上的任何一个字块位置上 最灵活但成本最高的一种方式。
最灵活但成本最高的一种方式 计算机组成原理计算机组成原理28全相联映象全相联映象的的地址变换方法地址变换方法 计算机组成原理计算机组成原理29全相联地址变换全相联地址变换 计算机组成原理计算机组成原理30这只是一个理想的方案这只是一个理想的方案两个原因使其两个原因使其实际上很少采用：实际上很少采用：(1) (1) 标标记记位位数数从从7 7位位增增加加到到1111位位，，使使CacheCache标标记记容容量量加加大大，， (2) (2) 访访问问CacheCache时时，，需需要要和和CacheCache的的全全部部标标记记进进行行““比比较较””才才能能判判断断出出所所访访主主存存地地址址的的内内容容是是否否已已在在CacheCache中中由由于于CacheCache速速度度要要求求高高，，通通常常由由““按按内内容容寻寻址址””的的相相联联存存储储器器完完成成，，所所需需硬硬件件逻逻辑辑电电路路很很多多，，以以至至于于无无法法用用于于cachecache中中实实际际的的CacheCache组织则是采取各种措施来减少所需比较的地址数目组织则是采取各种措施来减少所需比较的地址数目优优点点：：灵灵活活，，块块冲冲突突概概率率小小。
只只有有当当CacheCache中中全全部部装装满满后后, ,才才有可能出现块冲突有可能出现块冲突；；缺点：缺点：要作相联搜索，速度慢，代价高要作相联搜索，速度慢，代价高 计算机组成原理计算机组成原理31组相联映射方式组相联映射方式 CacheCache与主存均分组与主存均分组, ,主存中一个主存中一个组内的块数与组内的块数与Cache Cache 的的分组数相同分组数相同, ,主存中的各块与主存中的各块与CacheCache的组号有固定的映象关系的组号有固定的映象关系, ,但可自由映象到对应的但可自由映象到对应的CacheCache组中任一块组中任一块. .注意：注意：当只有一个组并且每组当只有一个组并且每组1616块时，此时为块时，此时为全相联映像全相联映像；； 当有当有1616组并且每组一个块时组并且每组一个块时, ,则为则为直接映像直接映像 计算机组成原理计算机组成原理32 把把CacheCache字块分为字块分为u u组，每组组，每组v v块，则块，则CacheCache的总块数为：的总块数为： m=m=u u v v 若若j j为主存块号为主存块号，，i i为为cachecache块号，块号，q q为组号为组号，，q=0,1,2,…,u-1q=0,1,2,…,u-1，， 按按u u为模将其映像到为模将其映像到cachecache，那么，主存字块可以用下列映象函，那么，主存字块可以用下列映象函数映象到数映象到CacheCache的第的第u u组内：组内： q = j mod uq = j mod uU=8 v=2 q = j mod 8If j=9 q=1 凡是符合以上求模公式的凡是符合以上求模公式的主存主存j j块块，均会映像到，均会映像到CacheCache的的q q组组内，一一对应，为直接映像关系。
可映像到内，一一对应，为直接映像关系可映像到q q组内的任何一块，组内的任何一块，组内是全相联映像组内是全相联映像v v值越大越灵活，相联搜索的规模越小值越大越灵活，相联搜索的规模越小 v v比较小，通常取比较小，通常取2 2、、4 4、、8 8 计算机组成原理计算机组成原理33组相联组相联的的地址变换方法地址变换方法 计算机组成原理计算机组成原理340组 1组 内存 计算机组成原理计算机组成原理35组相联地址变换组相联地址变换 计算机组成原理计算机组成原理36直接映象是：直接映象是：1 1路组相联路组相联全相联是：全相联是： m m路组相联路组相联N N个直接映射个直接映射cachecache并行工作并行工作直接映象和全相联映象是组相联的特例：直接映象和全相联映象是组相联的特例：•主存中的一块能对应到主存中的一块能对应到CacheCache中一个特定组中的任意一行中一个特定组中的任意一行上若组中有上若组中有n n个块，则称其为个块，则称其为 n n路组关联路组关联 计算机组成原理计算机组成原理37CacheCache直接相联映射载入过程直接相联映射载入过程222622261641618载入载入载入载入命中命中命中命中载入载入载入载入命中命中替换替换t22222222262626262222262622222626222216162626222226262222161622221616012345674 416161818顺序顺序 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 地址地址例例: :设一个设一个CacheCache中有中有8 8个个块块, ,访问主存进行读操作的块地址序列为访问主存进行读操作的块地址序列为2222、、2626、、2222、、2626、、1616、、4 4、、1616、、1818，给出每次访问后，给出每次访问后CacheCache中的内容。
中的内容 计算机组成原理计算机组成原理38CacheCache全相联映射载入过程全相联映射载入过程222622261641618载入载入载入载入命中命中命中命中载入载入载入载入命中命中载入载入t2222222226262222262622222626222226262222262616162222262616164 42222262616164 41616012345674 41818顺序顺序 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 地址地址 计算机组成原理计算机组成原理39CacheCache组相联映射载入过程组相联映射载入过程222622261641618载入载入载入载入命中命中命中命中载入载入载入载入命中命中载入载入t2222222226262626222226262222262622222626161622222626161622224 42626161622224 41616012345674 41818顺序顺序 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 地址地址 计算机组成原理计算机组成原理40 Cache的容量和块的大小是影响的容量和块的大小是影响Cache的效率的重要因素。
的效率的重要因素 • 一般来说，一般来说，Cache的存储容量比主存的容量小得多的存储容量比主存的容量小得多; • 但不能太小，太小会使命中率太低；但不能太小，太小会使命中率太低； • 也也没没有有必必要要过过大大，，过过大大不不仅仅会会增增加加成成本本，，而而且且当当容容量量超超过过一一 定值后，命中率随容量的增加将不会有明显地增长定值后，命中率随容量的增加将不会有明显地增长• 因此，因此，cache容量是总成本价与命中率的折衷值容量是总成本价与命中率的折衷值 CacheCache容量与命中率容量与命中率 计算机组成原理计算机组成原理41块长与命中率块长与命中率 块长与命中率的关系更为复杂，它取决于程序的局部特性块长与命中率的关系更为复杂，它取决于程序的局部特性块长的最优值很难确定，通常：块长的最优值很难确定，通常： • 每块取每块取4至至8个可编址单位（字或字节）较好；个可编址单位（字或字节）较好； • 也可取一个主存周期所能调出主存的信息长度也可取一个主存周期所能调出主存的信息长度 计算机组成原理计算机组成原理422.2.替换策略替换策略 当一个新的主存块要调入到当一个新的主存块要调入到cachecache，而允许存放此块的行位置，而允许存放此块的行位置都被其它主存块占满时，就要产生替换，因为都被其它主存块占满时，就要产生替换，因为cachecache工作原理要工作原理要求它应尽量保存最新的数据。
求它应尽量保存最新的数据1)(1)对于采用对于采用直接映射方式直接映射方式的的cachecache来说：来说： 因一个主存块只有一个特定的行位置可存放，所以问题解决因一个主存块只有一个特定的行位置可存放，所以问题解决很简单，把此特定行位置上的原主存块妥善处理后，换出很简单，把此特定行位置上的原主存块妥善处理后，换出CacheCache即可2)(2)对于对于全相联全相联的的cachecache来说，它的全部行都是可被替换的特定行；来说，它的全部行都是可被替换的特定行；而而组相联组相联的的cachecache中同组各路的行都是可被替换的特定行：这样中同组各路的行都是可被替换的特定行：这样就要从允许存放新主存块的若干特定行中选取一行换出就要从允许存放新主存块的若干特定行中选取一行换出• • 替换问题与替换问题与cachecache的组织方式紧密相关的组织方式紧密相关 计算机组成原理计算机组成原理43 如何选取就涉及到如何选取就涉及到替换策略替换策略或称或称替换算法替换算法的采用以硬件的采用以硬件实现的常用算法主要有以下三种实现的常用算法主要有以下三种 FIFOFIFO(First(First In First Out) In First Out)算法算法是把一组中最先调入是把一组中最先调入CacheCache的字块替换出去，不需要随时记录各个字块的使用情的字块替换出去，不需要随时记录各个字块的使用情况，所以实现容易，开销小。
况，所以实现容易，开销小1).1).先进先出先进先出（FIFO）算法算法 计算机组成原理计算机组成原理44 LRULRU （（Least Recent1y UsedLeast Recent1y Used））算法是将近期内长久未被访算法是将近期内长久未被访问过的行换出问过的行换出方法：方法： 每行设置一个计数器，每行设置一个计数器，cachecache每命中一次，命中行计数器清每命中一次，命中行计数器清零，其它各行计数器增零，其它各行计数器增1 1，因此它是，因此它是未访问次数计数器未访问次数计数器当需要替换时，比较各特定行的计数值，将计数值最大的行换出要替换时，比较各特定行的计数值，将计数值最大的行换出这种算法显然保护了刚拷贝进新数据的行，符合这种算法显然保护了刚拷贝进新数据的行，符合cachecache工作原工作原理，因而使理，因而使cachecache有较高的命中率有较高的命中率2).2).近期最少使用（近期最少使用（LRULRU）算法）算法 LRULRU算法硬件实现也不难如果是两路组相联的算法硬件实现也不难如果是两路组相联的cachecache，就，就更简单了。
更简单了 计算机组成原理计算机组成原理45例如：两路组相联的例如：两路组相联的cachecache 因为一个主存块只能在一个特定组的两行中来做替换选择，因为一个主存块只能在一个特定组的两行中来做替换选择， 二选一完全不需要计数器，一组两行只需要一个二进制位即可二选一完全不需要计数器，一组两行只需要一个二进制位即可 如规定一组中的如规定一组中的A A行拷贝进新数据将此位置行拷贝进新数据将此位置““1”1”，，B B行拷贝行拷贝进新数进新数 据将此位置据将此位置““0”0”那么当需要替换时只需检查此乒乓那么当需要替换时只需检查此乒乓位的状态即位的状态即 可，为可，为““0”0”换出换出A A行，为行，为““1”1”换出换出B B行，实现了保行，实现了保护新行的原则护新行的原则 PentiumPentium片内的数据片内的数据cachecache是一个两路组相联结构，采用的就是一个两路组相联结构，采用的就 是这种简捷的是这种简捷的LRULRU替换策略替换策略 计算机组成原理计算机组成原理46 随机替换（随机替换（Random Rep1acementRandom Rep1acement）策略实际上是不要什么算）策略实际上是不要什么算法，从特定的行位置中随机地选取一行换出即可。
法，从特定的行位置中随机地选取一行换出即可 这种策略以硬件实现最容易，而且速度也比前两种策略快这种策略以硬件实现最容易，而且速度也比前两种策略快 缺点缺点是随意换出的数据很可能马上又要用，从而增加了映射是随意换出的数据很可能马上又要用，从而增加了映射次数，降低了命中率和次数，降低了命中率和cache cache 的工作效率但这个缺点可以用的工作效率但这个缺点可以用增大增大cachecache的容量来克服，实验统计表明，随机替换策略的功的容量来克服，实验统计表明，随机替换策略的功效只是稍逊于前两种策略效只是稍逊于前两种策略3)3). .随机替换随机替换 计算机组成原理计算机组成原理47CacheCache先进先出替换策略先进先出替换策略(FIFO)(FIFO)2211221971643载入载入命中载入载入替换替换替换t01232222222211112222111119192222111119197 71616111119194 47 71616161611114 419191111222222222222111119194 43 3顺序顺序 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 地址地址 计算机组成原理计算机组成原理48CacheCache最不经常使用算法最不经常使用算法(LFU)(LFU)22112219111643载入载入命中载入命中载入替换替换t012322220 02222111122221 11111191922221 111111 1191922222 211111 14 4161611111 1161622222 211111 1161619191111222222221 122221 1111119194 43 322命中222211111 11616191922222 2顺序顺序 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 地址地址在选择被替换页面时，要从所有计数器中找出计数值最小的计数值。
计算机组成原理计算机组成原理49CacheCache近期最久未使用算法近期最久未使用算法(LRU)(LRU)2211221971643载入载入命中载入载入替换替换替换t012322220 022221 11111022222 211113 319191 122223 3111119192 27 71 14 41 116162 219197 73 37 70 016160 0222216161 17 72 219193 311111222222220 02222111112 219190 04 40 03 30 0它把LFU算法中要记录数量上的“多”与“少”简化成判断“有”与“无” 计算机组成原理计算机组成原理503.3.写操作策略写操作策略 因为因为cachecache的内容是部分主存内容的副本，应该与主存内容的内容是部分主存内容的副本，应该与主存内容保持一致而保持一致而CPUCPU对对cachecache的写入更改了的写入更改了cachecache内容，如何与主内容，如何与主存内容保持一致就有几种写操作工作方式可供选择，统称为存内容保持一致就有几种写操作工作方式可供选择，统称为写策略写策略。
1).1).写回法（写回法（write--backwrite--back）） 当当CPUCPU对对cachecache写命中时，只修改写命中时，只修改cachecache的内容不立即写入的内容不立即写入主存，只当此行被换出时才写回主存主存，只当此行被换出时才写回主存 对一对一cachecache行的多次写命中都在行的多次写命中都在cachecache中快速完成修改，只中快速完成修改，只是需被替换时才写回速度较慢的主存，减少了访问主存的次是需被替换时才写回速度较慢的主存，减少了访问主存的次数从而提高了效率数从而提高了效率1) (1) CPUCPU对对cachecache写命中时写命中时 计算机组成原理计算机组成原理51方法：方法：每个每个cachecache行必须配置一个修改位，以反映此行是否被行必须配置一个修改位，以反映此行是否被CPUCPU修改过当某行被换出时，根据此行修改位为修改过当某行被换出时，根据此行修改位为1 1还是为还是为0 0，，决定是将该行内容写回主存还是简单地弃之而不顾决定是将该行内容写回主存还是简单地弃之而不顾2) (2) CPUCPU对对cachecache写未命中时写未命中时 对于对于cachecache写未命中，写回法的处理是为包含欲写字的主存写未命中，写回法的处理是为包含欲写字的主存块在块在cachecache分配一行，将此块整个拷贝到分配一行，将此块整个拷贝到CacheCache后在后在cachecache中对中对其进行修改；拷贝主存块时虽已读访问到主存，但此时并不对其进行修改；拷贝主存块时虽已读访问到主存，但此时并不对主存块修改主存块修改，，统一地将主存写修改操作留待换出时进行统一地将主存写修改操作留待换出时进行。
3)(3)优缺点：优缺点： 写写cachecache与写主存分开进行方式可显著减少写主存次数，但与写主存分开进行方式可显著减少写主存次数，但写回法存在写回法存在cache/cache/主存不一致性的隐患主存不一致性的隐患 计算机组成原理计算机组成原理522)2). .写直达法（写直达法（write--throughwrite--through）） 也也称全写法称全写法1)(1)当当cachecache写命中时：写命中时：cachecache与主存同时发生写修改这种策略与主存同时发生写修改这种策略显然较好地维护了显然较好地维护了cachecache与主存的内容一致性与主存的内容一致性；；(2)(2)当当cachecache写未命中时：写未命中时：直接向主存写直接向主存写 但此时是否将修改过的主存块取到但此时是否将修改过的主存块取到cachecache，写直达法有两种，写直达法有两种选择选择：： • • 一种是取主存块到一种是取主存块到cachecache并为它分配一个行位置，并为它分配一个行位置， 称为称为WTWAWTWA法法(Write-Through-with-Write-Allocate(Write-Through-with-Write-Allocate）；）； • • 另一种是不取主存块到另一种是不取主存块到cache, cache, 称为称为WTNWAWTNWA法法 （（Write-Through-withWrite-Through-with．．NO-Write-AllocateNO-Write-Allocate）。
计算机组成原理计算机组成原理53写直达法是写写直达法是写cachecache与写主存同步进行，与写主存同步进行，优点是：优点是： cachecache每行无需设置一个修改位以及相应的判测逻辑；每行无需设置一个修改位以及相应的判测逻辑；缺点是：缺点是： cachecache对对CPUCPU向主存的写操作无高速缓存功能，降向主存的写操作无高速缓存功能，降 低了低了cachecache的功效 8048680486处理器片内处理器片内cachecache采用的就是写直达法采用的就是写直达法3)(3)优缺点：优缺点： 计算机组成原理计算机组成原理543)3)．写一次法（．写一次法（write--oncewrite--once））策略：策略：写一次法是一种基于写回法又结合了写直达法的写策略，写一次法是一种基于写回法又结合了写直达法的写策略，即写命中和写未命中的处理与写回法基本相同，只是第一次写即写命中和写未命中的处理与写回法基本相同，只是第一次写命中时要同时写入主存命中时要同时写入主存应用：应用： 这种策略主要用于某些处理器的片内这种策略主要用于某些处理器的片内cachecache，例如，例如PentiumPentium处理器的片内数据处理器的片内数据cachecache就采用的是写一次法。
因为片内就采用的是写一次法因为片内cachecache写命中时，写操作就在写命中时，写操作就在CPUCPU内部高速完成，若没有内存地址及内部高速完成，若没有内存地址及其它指示信号送出，就不便于系统中的其它其它指示信号送出，就不便于系统中的其它cachecache监听监听（（snoopsnoop） 计算机组成原理计算机组成原理55 在第一次片内在第一次片内cachecache写命中时，写命中时， CPUCPU要在总线上启动一个存要在总线上启动一个存储器写周期其它储器写周期其它cachecache监听到此主存块地址及写信号后，即监听到此主存块地址及写信号后，即可把它们各自保存可能有的该块拷贝及时作废（无效处理）可把它们各自保存可能有的该块拷贝及时作废（无效处理）尔后若有对片内尔后若有对片内cachecache此行的再次或多次写命中，则按回写法此行的再次或多次写命中，则按回写法处理，无需再送出信号了这样虽然第一次写命中时花费了一处理，无需再送出信号了这样虽然第一次写命中时花费了一个存储周期，但对维护系统全部个存储周期，但对维护系统全部cachecache的一致性有利而大多的一致性有利。
而大多的的cachecache写操作不涉及到片外，对指令流水执行有利写操作不涉及到片外，对指令流水执行有利 计算机组成原理计算机组成原理56CacheCache写操作流程写操作流程写请求写响应CacheCache写穿策略写穿策略 WriteThrough 写回策略写回策略 Write Back 写请求写响应无无脏数据，无数据，无丢失数据失数据风险，写速度慢，写速度慢 存在存在脏数据，有数据，有丢失数据失数据风险，写速度快，写速度快 计算机组成原理计算机组成原理57 Intel公司的公司的82385Cache控制器，控制器，是专为是专为8038680386设计的高性能设计的高性能3232位外围支持芯片它与静态位外围支持芯片它与静态RAM(RAM(简称简称SRAM)SRAM)芯片一起构成高速芯片一起构成高速缓冲存储器缓冲存储器 标志存储器和控制逻辑均在芯片内，使用标志存储器和控制逻辑均在芯片内，使用82385可大大简化高可大大简化高速缓冲存储器子系统的设计速缓冲存储器子系统的设计 82385没有把数据存储器集成与一体没有把数据存储器集成与一体 Intel 82385 cache控制器支持控制器支持直接映象直接映象和和两路组相联映象两路组相联映象两种两种地址映象方式。
地址映象方式1.Intel 82385 Cache1.Intel 82385 Cache简介简介 计算机组成原理计算机组成原理58结构框图结构框图(Snoop bus) 计算机组成原理计算机组成原理59 支持容量为支持容量为16K字节或字节或32K字节的字节的cache，它以，它以16MHz和和20MHz的操作速度与的操作速度与80386CPU相配合，组成与相配合，组成与80386相匹配相匹配的主存的主存-Cache存储系统，并可全部映象存储系统，并可全部映象80386的的32位地址，提位地址，提供供4GB（千兆字节）的地址空间，能使（千兆字节）的地址空间，能使CPU几乎无等待地读几乎无等待地读出数据，出数据，命中率可高达命中率可高达99％ 计算机组成原理计算机组成原理602.82385 Cache2.82385 Cache的直接映象的直接映象 计算机组成原理计算机组成原理61• Intel 80386的的4GB地址空间被分成地址空间被分成217页页；；• 页的大小和页的大小和Cache的容量相同的容量相同，均为，均为8K字字 (32位位) 或或32K字节字节.• Cache又分成又分成1024组组，每组，每组8个字个字 (8×32位位)。
• 每每个个字字叫叫做做一一“行行”，，行行是是主主存存和和Cache之之间间的的信信息息传传输输单单位位（（ 块）• 在在82385 Cache目录表中，对应目录表中，对应Cache的每一组有一个条目的每一组有一个条目(目目 录项），它有录项），它有26位高17位为标记，中间一位为标记有效位位为标记，中间一位为标记有效位 ，低，低8位为行有效位位为行有效位17位标记指出主存的页号，标记位标记指出主存的页号，标记217页页 中的某一页中的某一页• Cache由两部分组成：由两部分组成： 一部分存放由主存储器来的数据，称数据存储器一部分存放由主存储器来的数据，称数据存储器 另一部分存放该数据所在的主存储器的地址，故称地址标记另一部分存放该数据所在的主存储器的地址，故称地址标记 存储器，或目录存储器存储器，或目录存储器 这两个存储器都为静态存储器这两个存储器都为静态存储器 计算机组成原理计算机组成原理62直接映象方式：直接映象方式： • • 主存各页中的第主存各页中的第0 0组只能驻留在组只能驻留在CacheCache的第的第0 0组，其余各组依次组，其余各组依次 类推。
类推 • • 目录表中的目录表中的8 8位行有效位分别对应每组中的位行有效位分别对应每组中的8 8行，如某一行被行，如某一行被 调入调入CacheCache中，则该行有效位置中，则该行有效位置““1”1”，同时将标记有效位置，同时将标记有效位置 “ “1” 1” 图图中中所所示示为为主主存存第第二二页页的的第第九九行行正正驻驻留留在在CacheCache中中，，则则第第一一组组的的对对应应表表目目中中的的标标记记位位将将记记作作1 1由由于于第第0 0组组包包含含第第0 0～～7 7行行，，第第1 1组组包包含含第第8 8～～1515行行，，所所以以，，第第1 1组组对对应应表表目目中中第第2 2个个行行有有效效位位被被置置““1”1”，说明第，说明第9 9行已驻留在行已驻留在CacheCache中 计算机组成原理计算机组成原理63 • A• A3131～～A A1515为为1717位位标记标记字段，字段， • A• A1414～～A A5 5为为1010位位组地址组地址字段字段 • A• A4 4～～A A2 2 为行选择为行选择字字段 总线低总线低1313位地址位地址A A1414～～A A2 2又作为又作为CacheCache地址，它可以直地址，它可以直接选择接选择CacheCache中中8K8K字中的一行字中的一行。
82385Cache82385Cache控制器把控制器把8038680386地址线地址线A2—A31A2—A31分成分成3 3个字段个字段: : 17 10 3标记标记 组组 行行A31~A15 A14~A5 A4~A2 计算机组成原理计算机组成原理64• 82385用用A14～～A510位地址选择目录表中位地址选择目录表中1024个表目中的一条，个表目中的一条， 用用A4～～A2选择表目中选择表目中8个行有效位中的一位这个行有效位中的一位这13位位Cache 地址选择地址选择Cache中的一行中的一行 (4字节字节)• 82385将地址总线的标记字段（将地址总线的标记字段（A31～～A15）与目录表表目中的）与目录表表目中的 标记进行比较，若二者相等，并且目录中的标记有效位和行标记进行比较，若二者相等，并且目录中的标记有效位和行 有效位皆为有效位皆为“1”状态时，则读命中状态时，则读命中• 82385指示指示Cache将选中的字送入将选中的字送入80386的数据总线。
的数据总线 读命中不改变读命中不改变Cache和目录中的内容和目录中的内容当当8038680386启动读周期时：启动读周期时： 计算机组成原理计算机组成原理65(1) 行行失失效效. 这这时时,目目录录表表目目中中的的标标记记和和地地址址总总线线的的标标记记字字段段相相等等, 且标记有效位为且标记有效位为“1”，但行有效位为，但行有效位为“0”2) 标记失效标记失效. 这时，目录表目中的标记和地址总线标记字段不这时，目录表目中的标记和地址总线标记字段不 相等，或是标记有效位为相等，或是标记有效位为“0” 当当失失效效发发生生时时，，80386则则直直接接访访问问主主存存取取得得数数据据，，并并同同时时将将该该内容写入内容写入Cache，并修改目录表并修改目录表 • 若为行失效，则只将该行对应的行有效位置若为行失效，则只将该行对应的行有效位置“1”；； • 若为标记失效，则用上述地址页号用来修改标记，并将标记若为标记失效，则用上述地址页号用来修改标记，并将标记 有有效效位位置置“1”，，并并置置“1”相相应应的的行行有有效效位位，，清清 除其它七个行有效位。
除其它七个行有效位读失效可分为两种情况读失效可分为两种情况 计算机组成原理计算机组成原理66直接映象的直接映象的cachecache系统系统 它它把把每每页页分分成成含含有有相相同同数数量量行行（（块块））的的组组，，这这是是为为了了减减小小地址目录表的项数，以减小地址目录表的项数，以减小Cache目录表的容量目录表的容量82385 Cache82385 Cache采用的是一种改进的直接映象方式采用的是一种改进的直接映象方式: : 计算机组成原理计算机组成原理673.82385 Cache3.82385 Cache的组相联映象的组相联映象 计算机组成原理计算机组成原理68在两路组相联映象方式下：在两路组相联映象方式下： • Cache被分成被分成A和和B两个体两个体，每体为，每体为4K字字 • 主存页面的大小和主存页面的大小和Cache的一个体的容量相同，其页数则比直的一个体的容量相同，其页数则比直 接映象时增加一倍，共接映象时增加一倍，共218页页 • 对应两个体的目录表也为对应两个体的目录表也为A和和B两部分，每个部分有两部分，每个部分有27位位, 高高 18位标记主存页号位标记主存页号, 中间中间1位作标记有效位，低位作标记有效位，低8位作行有效位位作行有效位. • 目录表中的目录表中的LRU位是附加位，用以指定位是附加位，用以指定A和和B两个体中同一组两个体中同一组 的哪一行是近期最少使用行，即是被置换的对象。
的哪一行是近期最少使用行，即是被置换的对象 • 在两路组相联映象方式中，主存各页的同一组可以任意映象到在两路组相联映象方式中，主存各页的同一组可以任意映象到 Cache的两个体的同一组中同时可有两个页的同一组存于的两个体的同一组中同时可有两个页的同一组存于 Cache 计算机组成原理计算机组成原理6982385把地址总线划分为三段：把地址总线划分为三段： 18 9 3 标记标记 组组 行行A31~A14 A13~A5 A4~A2 当当82385选中选中9位组字段中的某一个特定组时，就要对位组字段中的某一个特定组时，就要对18位位的标记进行比较，如果地址匹配，对特定的一路命中，则把的标记进行比较，如果地址匹配，对特定的一路命中，则把标记的有效位置位，并且被选中的行也置位，标记的有效位置位，并且被选中的行也置位，82385允许对被允许对被选中的选中的cache存储体进行数据的读出或写入存储体进行数据的读出或写入 计算机组成原理计算机组成原理70两路组相联两路组相联cachecache系统系统 计算机组成原理计算机组成原理71奔腾奔腾PCPC机的机的CacheCacheL L2 2 ————安装在主板上，其容量是安装在主板上，其容量是256 KB256 KB或或512KB512KB，采用的两路，采用的两路组相联映射方式，每行可以是组相联映射方式，每行可以是3232，，6464或或128128字节。
字节L L1 1 ————集成在集成在CPUCPU内，其容量是内，其容量是16KB16KB，采用的也是两路组相联，采用的也是两路组相联映射方式，每行是映射方式，每行是3232字节 L L2 2的内容是的内容是4 4～～32MB32MB容量主存的子集，容量主存的子集，L L1 1又是又是L L2 2的子集，从的子集，从而使而使L L1 1未命中处理时间大为缩短，为未命中处理时间大为缩短，为L L1 1的高速使用提供了支持的高速使用提供了支持L L2 2L L1 11.Pentium PC1.Pentium PC采用两级采用两级cachecache结构结构 计算机组成原理计算机组成原理72• CPU• CPU中的中的L L1 1分立为各分立为各8KB8KB的指令的指令cachecache和数据和数据cachecache ( (有学者曾对某些程序进行跟踪研究，得到的统计结果是：取指令占有学者曾对某些程序进行跟踪研究，得到的统计结果是：取指令占6363％，取数占％，取数占2525％，写数占％，写数占1212％这一结果表明将指令％这一结果表明将指令cachecache与数据与数据cachecache分开是有好处的。
分开是有好处的) )• • 指令指令cachecache是只读的，单端口是只读的，单端口256256位（位（3232字节）向指令预取缓冲器提供字节）向指令预取缓冲器提供 指令代码指令代码• • 数据数据cachecache是读写的，双端口，每端口是读写的，双端口，每端口3232位（位（4 4字节），向两条流水线字节），向两条流水线 的整数运算单元和寄存器提供数据或接收数据，两个端口还可组合成的整数运算单元和寄存器提供数据或接收数据，两个端口还可组合成 一个一个6464位端口与浮点运算单元相接位端口与浮点运算单元相接• • 两个两个cachecache与与6464位数据、位数据、3232位地址的位地址的CPUCPU内部总线相连内部总线相连CPUCPU中的中的L L1 1 计算机组成原理计算机组成原理73预取缓冲存储器预取缓冲存储器指令译码指令译码256控制控制ROM控制部件控制部件地址生成地址生成(U流水线流水线)地址生成地址生成(V流水线流水线)整数寄存器组整数寄存器组ALU(U流水线流水线)ALU(V流水线流水线)筒型移位器筒型移位器8KB数据数据Cache浮点部件浮点部件控制控制寄存器组寄存器组加法器加法器除法器除法器乘法器乘法器80808KB代码代码Cache分支目标分支目标缓冲器缓冲器预取预取地址地址指令指针指令指针转移校验转移校验和和目标地址目标地址分页分页部件部件323232323232总总线线部部件件6464位读总线位读总线64位位数据总线数据总线32位位地址总线地址总线控制控制TLBTLB32位地址总线位地址总线PentiumPentiumCPUCPU框图框图 计算机组成原理计算机组成原理742.2.Pentium1Pentium1级级cachecache的组织结构的组织结构( (数据数据cache)cache) 计算机组成原理计算机组成原理75• • 8KB8KB的数据的数据cachecache采用采用两路组相联两路组相联的组织方式，每一的组织方式，每一 路为路为4KB4KB字节，分成字节，分成128128组，每组组，每组2 2行，每行行，每行3232字节字节 （（8 8个双字，个双字，1 1个双字个双字3232位）；位）；• • 每行有一个每行有一个2020位的标记和位的标记和2 2位的位的M/E/S/IM/E/S/I的状态位，的状态位， 这这2222位构成该行的目录项；位构成该行的目录项；• • 采用采用LRULRU替换策略，一组两行共用一个替换策略，一组两行共用一个LRULRU位；位； （（L1L1指令指令cachecache的组织类同于此，只是不再是的组织类同于此，只是不再是2 2位状位状 态位而是态位而是1 1位有效位。
位有效位 计算机组成原理计算机组成原理76• MESI协议协议—— 一种采用写一种采用写- -无效方式的监听协议，它要求每个无效方式的监听协议，它要求每个cache有两个状态位，有两个状态位，用以描述该行当前是处于修改态用以描述该行当前是处于修改态(M)、专有态、专有态(E)、共享态、共享态(S)、或者无效态、或者无效态(I)中的哪一个状态，从而决定对它的读中的哪一个状态，从而决定对它的读/写操作行为用于维护写操作行为用于维护cache的一的一致性 • L2级级cache采用写回法，采用写回法，L1级级cache采用写一次法为维护采用写一次法为维护 cache的一致性，的一致性， L1、、L2均采用均采用MESI协议 • L2负责整个系统的负责整个系统的cache/主存一致性，主存一致性，L1负责响应负责响应L2，与，与L2一起维护一起维护 L1/L2两个两个cache的一致性，从而保证了的一致性，从而保证了L1-L1-主存三级存储系统的一致性主存三级存储系统的一致性 计算机组成原理计算机组成原理77 • CPU与外部数据交换时，存储器读写总线周期主要有两类与外部数据交换时，存储器读写总线周期主要有两类: 一类是一类是256位猝发式传送，用于位猝发式传送，用于L1的行填入和行写出的行填入和行写出,一次完成整行的填一次完成整行的填入或写出。
入或写出 另一类是不经另一类是不经L1的的64位传送位传送 ，称为非超高速缓存式传送称为非超高速缓存式传送 计算机组成原理计算机组成原理783.3.两级两级cachecache和主存之间的工作环境方框图和主存之间的工作环境方框图 计算机组成原理计算机组成原理79虚拟存储器的基本概念虚拟存储器的基本概念页式虚拟存储器页式虚拟存储器段式虚拟存储器段式虚拟存储器替换策略替换策略段页式虚拟存储器段页式虚拟存储器奔腾奔腾PCPC的虚地址模式的虚地址模式 计算机组成原理计算机组成原理80虚拟存储器的基本概念虚拟存储器的基本概念1. 1. 虚拟存储器虚拟存储器 虚拟存储器是建立在主存虚拟存储器是建立在主存- -辅存（外存）物理结构基础上的，辅存（外存）物理结构基础上的，由负责信息划分及主存由负责信息划分及主存- -辅存之间信息调度的辅助硬件及操作系辅存之间信息调度的辅助硬件及操作系统的存储管理软件所组成的一种存储体系统的存储管理软件所组成的一种存储体系它将主存和辅存的它将主存和辅存的地址空间统一编址，形成一个庞大的存储空间，在这个大空间地址空间统一编址，形成一个庞大的存储空间，在这个大空间里，用户自由编程，完全不必考虑程序在主存中是否装得下，里，用户自由编程，完全不必考虑程序在主存中是否装得下，或者放在辅存中的程序将来在主存中的位置，编好的程序由计或者放在辅存中的程序将来在主存中的位置，编好的程序由计算机操作系统装入辅助存储器，程序运行时附加的辅助硬件机算机操作系统装入辅助存储器，程序运行时附加的辅助硬件机构和存储管理软件会把辅存的程序一块块自动调入内存由构和存储管理软件会把辅存的程序一块块自动调入内存由CPUCPU执执行或调出内存，用户感觉到的不再是处处受到主存容量限制的行或调出内存，用户感觉到的不再是处处受到主存容量限制的存储系统，而是好像具有一个容量充分大的存储器，这样的存存储系统，而是好像具有一个容量充分大的存储器，这样的存储体系称为储体系称为““虚拟存储器虚拟存储器””。
计算机组成原理计算机组成原理81 虚拟存储器只是一个容量非常大的存储器的虚拟存储器只是一个容量非常大的存储器的逻辑模型逻辑模型，不，不是任何实际的物理存储器它借助于磁盘等辅助存储器来扩是任何实际的物理存储器它借助于磁盘等辅助存储器来扩大主存容量，使之为更大或更多的程序所使用大主存容量，使之为更大或更多的程序所使用 虚拟存储器指的是主存虚拟存储器指的是主存- -辅存层次以透明的方式给用户辅存层次以透明的方式给用户提供了一个比实际主存空间大得多的提供了一个比实际主存空间大得多的程序地址空间程序地址空间它能使计算机具有辅存的容量，而接近于主存的速度它能使计算机具有辅存的容量，而接近于主存的速度 对应用程序员来说，好象有一个比实际主存大得多的、对应用程序员来说，好象有一个比实际主存大得多的、可使编程空间不受限制的虚可使编程空间不受限制的虚( (主主) )存空间存在存空间存在 计算机组成原理计算机组成原理822.2.虚地址和实地址虚地址和实地址 虚拟存储器的辅存部分也能让用户象内存一样使用，用户虚拟存储器的辅存部分也能让用户象内存一样使用，用户编程时的指令地址允许涉及辅存大小的空间范围，这种指令地编程时的指令地址允许涉及辅存大小的空间范围，这种指令地址称为址称为“虚拟地址虚拟地址”（虚地址）或（虚地址）或“逻辑地址逻辑地址”。
对应的存储对应的存储空间称为空间称为“虚拟地址空间虚拟地址空间”或或“逻辑空间逻辑空间” 实际的主存储器地址则称为实际的主存储器地址则称为 “物理地址物理地址”（（ 实地址）它实地址）它由由CPU引脚送出，是用于访问主存的地址对应的存储空间称引脚送出，是用于访问主存的地址对应的存储空间称为为“物理地址空间物理地址空间” 计算机组成原理计算机组成原理83 虚拟存储器的用户程序以虚拟地址编址并存放在辅存中，程虚拟存储器的用户程序以虚拟地址编址并存放在辅存中，程序运行时序运行时CPU以虚地址访问主存，由辅助硬件找出虚地址和物以虚地址访问主存，由辅助硬件找出虚地址和物理地址的对应关系，判断这个虚地址指示的存储单元是否已装理地址的对应关系，判断这个虚地址指示的存储单元是否已装入主存，如果在主存，入主存，如果在主存，CPU就直接执行已在主存的程序；如果就直接执行已在主存的程序；如果不在，要进行辅存向主存的调度，这种调度以块为单位进行，不在，要进行辅存向主存的调度，这种调度以块为单位进行， 存储管理软件和相应的硬件把访问单位所在的程序块从辅存调存储管理软件和相应的硬件把访问单位所在的程序块从辅存调入主存，且把程序虚地址变换成实地址，然后由入主存，且把程序虚地址变换成实地址，然后由CPU访问主存。
访问主存 虚拟存储器程序执行中各程序块在主存和辅存之间进行自虚拟存储器程序执行中各程序块在主存和辅存之间进行自动调度和地址变换，主存动调度和地址变换，主存-辅存形成一个统一的有机体，对于用辅存形成一个统一的有机体，对于用户是透明的户是透明的 计算机组成原理计算机组成原理843.3.几种虚拟存储器几种虚拟存储器 虚虚存存通通过过增增设设地地址址映映象象表表机机构构来来实实现现程程序序在在主主存存中中的的定定位位这这种种定定位位技技术术是是把把程程序序分分割割成成若若干干个个较较小小的的段段或或页页，，用用相相应应的的映映象象表表机机构构，，来来指指明明该该程程序序的的某某段段或或某某页页是是否否已已装装入入主主存存，，若若已已装装入入主主存存，，则则应应同同时时指指明明其其在在主主存存中中所所处处的的开开始始位位置置；；若若未未装装入入主主存存，，则则应应到到辅辅存存中中去去调调段段或或页页，，并并建建立立起起程程序序空空间间和和实实存存空空间间的的地地址址映映象象关关系系这这样样，，程程序序执执行行时时通通过查映象表，将程序过查映象表，将程序(虚虚)地址变成主存地址再访问主存。
地址变成主存地址再访问主存 由由于于采采用用的的存存储储映映象象算算法法不不同同，，形形成成了了多多种种不不同同的的存存储储器器管管理理方方式式的的虚虚拟拟存存储储器器，，其其中中主主要要有有段段式式、、页页式式、、段段页页式式三三种 计算机组成原理计算机组成原理85段式虚拟存储器段式虚拟存储器 段式虚拟存储器，是以段式虚拟存储器，是以程序的逻辑结构程序的逻辑结构所形成的段所形成的段( (如主如主程序、子程序、过程、表格等程序、子程序、过程、表格等) )作为主存分配单位的虚拟存储作为主存分配单位的虚拟存储器管理方式的存储器器管理方式的存储器 段表一般驻留在主存中段表一般驻留在主存中 每个段的大小可以不相等，有的甚至事先无法知道每个每个段的大小可以不相等，有的甚至事先无法知道每个程序都有一个段表程序都有一个段表( (映象表映象表) )，用于存放该道程序各程序段从，用于存放该道程序各程序段从辅存装入主存的状况信息辅存装入主存的状况信息 计算机组成原理计算机组成原理86段式虚拟存储器地址映象变换方法段式虚拟存储器地址映象变换方法主存地址空间主存地址空间程序地址空间程序地址空间 1000 3000(a) 地址映象关系地址映象关系0 段基址段基址 装入位装入位 段长段长 访问方式访问方式(b) 地址变换方法地址变换方法0段段1段段2段段段内地址段内地址段号段号 - 0 1K3000 1 2K1000 1 1K虚地址虚地址实地址实地址（相加形成）（相加形成）段表段表段基址寄存器段基址寄存器12段号段号段表基址段表基址 计算机组成原理计算机组成原理87 段表中的每一项段表中的每一项( (对应表中每一行对应表中每一行) )用于描述该道程序的一用于描述该道程序的一个自然段的基本情况：个自然段的基本情况：• • 段号用以存放程序段的段号，它与虚地址中的段号相一致。
段号用以存放程序段的段号，它与虚地址中的段号相一致 • • 装入位表明该段是否已装入主存装入位表明该段是否已装入主存• • 段基址字段用以指明当装入位为段基址字段用以指明当装入位为““1”1”时，该程序段装入主时，该程序段装入主存存 中的起始中的起始( (绝对绝对) )地址• • 段长指明该程序段的大小，段长指明该程序段的大小，• • 访问方式用以标记该段能允许访问的方式，如只读、可写、访问方式用以标记该段能允许访问的方式，如只读、可写、 只能执行等只能执行等 程序执行时，要先根据段表确定所访问的虚段是否已程序执行时，要先根据段表确定所访问的虚段是否已调入主存若没有调入，则先调入；若已调入，就要确定调入主存若没有调入，则先调入；若已调入，就要确定其在主存中的位置，也就是要进行虚实地址变换，然后方其在主存中的位置，也就是要进行虚实地址变换，然后方可执行 计算机组成原理计算机组成原理88表表表表 计算机组成原理计算机组成原理89把主存按段分配的存储管理方式称为段式管理把主存按段分配的存储管理方式称为段式管理段式管理段式管理系统的优点系统的优点是段的分界与程序的自然分界相对应段的逻辑是段的分界与程序的自然分界相对应段的逻辑独立性，使它易于编译、管理、修改和保护独立性，使它易于编译、管理、修改和保护, ,也便于多道也便于多道程序共享。
其程序共享其缺点缺点是容易在段间留下许多空余的零碎存储是容易在段间留下许多空余的零碎存储空间，造成浪费和段的起点和终点不定空间，造成浪费和段的起点和终点不定 计算机组成原理计算机组成原理90页式虚拟存储器页式虚拟存储器1.1.页、页表页、页表 页式虚拟存储器的主页式虚拟存储器的主存和虚拟空间划分成存和虚拟空间划分成大小大小相等相等的页，虚拟空间的页的页，虚拟空间的页数要比主存空间的页数多数要比主存空间的页数多很多1) 页页00000 0000…000000 1111…100001 0000…000001 1111…100010 0000…000010 1111…111111 0000…011111 1111…1高位高位(5位位) 低位低位(11位位)实地址实地址主存空间主存空间实页号实页号 页内地址页内地址2K2K2K2K2页页31页页0页页1页页 计算机组成原理计算机组成原理91 CPU访问主存时送出的是程序的虚地址，计算机必须判断访问主存时送出的是程序的虚地址，计算机必须判断出该地址的存储地址是否已在主存中：如果在的话，找出在主出该地址的存储地址是否已在主存中：如果在的话，找出在主存哪一页；如果不在的话，需要将所在页的内容调入指定的主存哪一页；如果不在的话，需要将所在页的内容调入指定的主存页后才能被存页后才能被CPU执行。
执行 为此，需要建立一张虚地址页号与实地址页号对照表，用以为此，需要建立一张虚地址页号与实地址页号对照表，用以记录程序的虚页面调入主存时被安排在主存的位置这张表叫记录程序的虚页面调入主存时被安排在主存的位置这张表叫页表页表 页表是存储管理软件根据主存运行情况自动建立的，内存中页表是存储管理软件根据主存运行情况自动建立的，内存中有固定区域存放页表每个程序都有一张页表有固定区域存放页表每个程序都有一张页表 页表的长度等于该程序虚页数页表的长度等于该程序虚页数2) (2) 页表页表 计算机组成原理计算机组成原理92页表信息字页表信息字 计算机组成原理计算机组成原理93主存页号主存页号 主存地址空间主存地址空间 虚存页号虚存页号 程序地址空间程序地址空间0132401272.2.地址映象地址映象(a) 地址映象关系地址映象关系 计算机组成原理计算机组成原理94页内地址页内地址页内地址页内地址实页号实页号虚页号虚页号 2 1 6 1(b) 地址变换方法地址变换方法主存页号主存页号 装入位装入位 - 0 7 1 - 0 页表基址页表基址虚地址虚地址实地址实地址页表页表页基址寄存器页基址寄存器 计算机组成原理计算机组成原理95虚实地址变换是由存储管理软件自动完成的。
虚实地址变换是由存储管理软件自动完成的来自来自CPU) 计算机组成原理计算机组成原理96 虚页内容若没有调入主存，则计算机启动输入输出系统，把虚页内容若没有调入主存，则计算机启动输入输出系统，把虚地址指示的一页内容从辅存调入主存，再提供虚地址指示的一页内容从辅存调入主存，再提供CPU访问注意：注意： 虚地址虚地址和和辅存地址辅存地址不是一回事，程序员按虚存空间编址，虚不是一回事，程序员按虚存空间编址，虚地址由虚页号和页内地址组成，辅存实际地址以磁盘为例，地地址由虚页号和页内地址组成，辅存实际地址以磁盘为例，地址由址由磁盘机号、磁头号、柱面号、块号、块内地址磁盘机号、磁头号、柱面号、块号、块内地址组成，因此组成，因此从辅存调页时还需要虚存地址空间到辅存地址的变换这个变从辅存调页时还需要虚存地址空间到辅存地址的变换这个变换也可以采用类似前述页表的方式此表称为换也可以采用类似前述页表的方式此表称为外页表外页表 CPU访问主存页面失效时，调用访问主存页面失效时，调用外页表外页表把程序的虚地址变换把程序的虚地址变换成辅存的实际地址，从辅存调出该虚页，而后根据页表指出实成辅存的实际地址，从辅存调出该虚页，而后根据页表指出实页号再把虚页内容调入主存。
页号再把虚页内容调入主存 调入由地址变换机构实现调入由地址变换机构实现 计算机组成原理计算机组成原理973.3.加速地址变换的方法加速地址变换的方法(1) 把表的最活跃部分放在高速存储器组成快表；把表的最活跃部分放在高速存储器组成快表；(2) 一些影响速度的关键部位引入硬件支持，如采用按内容一些影响速度的关键部位引入硬件支持，如采用按内容 查询的相联存储器查询的相联存储器 使用快表方法使用快表方法 快表由硬件组成，比页表小得多，查表时，由逻辑页号快表由硬件组成，比页表小得多，查表时，由逻辑页号同时去查快表和慢表，当在快表中有此逻辑页号时，就能同时去查快表和慢表，当在快表中有此逻辑页号时，就能很快地找到对应的物理页号送入实主存地址寄存器，从而很快地找到对应的物理页号送入实主存地址寄存器，从而做到虽采用虚拟存储器但访主存速度几乎没有下降做到虽采用虚拟存储器但访主存速度几乎没有下降 计算机组成原理计算机组成原理98 计算机组成原理计算机组成原理99页式管理方案页式管理方案 页式管理系统的信息传送单位是定长的页，主存的物理页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，称为页面。
新页调人主存也空间也被划分为等长的固定区域，称为页面新页调人主存也很容易掌握，只要有空白页面就可它比段式管理系统的空间很容易掌握，只要有空白页面就可它比段式管理系统的空间浪费要小得多页式管理系统的浪费要小得多页式管理系统的缺点缺点正好和段式管理系统相反，正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理保护和共享都不及段由于页不是逻辑上独立的实体，所以处理保护和共享都不及段式来得方便式来得方便 计算机组成原理计算机组成原理100例：例：一个有一个有3232位程序地址空间，页面容量为位程序地址空间，页面容量为1KB1KB，主存的容量，主存的容量为为8MB8MB的存储系统，问：的存储系统，问：(1) (1) 虚页号字段有多少位？页表将有多少行？虚页号字段有多少位？页表将有多少行？(2) (2) 页表的每一行有多少位？页表的容量有多少字节？页表的每一行有多少位？页表的容量有多少字节？解：解：(1) (1) 页表的长度为页表的长度为2 22222 =4M =4M行2) (2) 主存的容量为主存的容量为8MB=28MB=22323B B，， 主存中页框架的数量有主存中页框架的数量有2 22323 / 2 / 21010 = 2 = 21313个。
页表中主存页号字个页表中主存页号字段是段是1313位长，加上其它信息将超过位长，加上其它信息将超过1616位设页表的每一项为位设页表的每一项为1616位，页表的容量为位，页表的容量为4M×2 = 8MB4M×2 = 8MB 计算机组成原理计算机组成原理101例：例：一个虚拟存储器有一个虚拟存储器有8个页面，页面大小为个页面，页面大小为1024字，内存有字，内存有4个页面框架页表的内容为：个页面框架页表的内容为：虚页号虚页号实页号实页号0 31 12 -3 -4 25 -6 07 -对应于虚拟地址对应于虚拟地址4098的主存地址是什么？的主存地址是什么？解：解：4098÷1024 = 4......2，所以虚页号为，所以虚页号为4，页内地址为，页内地址为2从表中查得实页号为中查得实页号为2，实际地址为，实际地址为2×1024 + 2 = 2050 计算机组成原理计算机组成原理102• • 将段式管理和页式管理相结合，就构成了虚存的将段式管理和页式管理相结合，就构成了虚存的段页式段页式管理。
管理• • 它把程序按逻辑单位分段以后，再把每段分成固定大小的页它把程序按逻辑单位分段以后，再把每段分成固定大小的页• • 程序对主存的调入调出是按页面进行的，但它又可以程序对主存的调入调出是按页面进行的，但它又可以按段实按段实 现共享和保护现共享和保护，兼备页式和段式的优点所以目前大中型机，兼备页式和段式的优点所以目前大中型机 都采用这种虚拟存储器都采用这种虚拟存储器段页式虚拟存储器段页式虚拟存储器将段式和页式管理方式结合起来将段式和页式管理方式结合起来. .段页式将实际存储器机械等分成固定大小的页段页式将实际存储器机械等分成固定大小的页, ,程序则按模块分程序则按模块分段段, ,每段又分成与主存页面大小相同的页每段又分成与主存页面大小相同的页. .段页式管理兼有段式和页式的优点段页式管理兼有段式和页式的优点. . 计算机组成原理计算机组成原理103(a) 地址映象关系地址映象关系 段基址寄存器段基址寄存器 段表段表 页表页表 0 0 0 ... N-1 L-1 M-1 段表长度段表长度 段表基址段表基址 装入位装入位 段长段长 页表地址页表地址(b) 地址变换方法地址变换方法页内地址页内地址页内地址页内地址页号页号页号页号段号段号基号基号 1 M 1 L主存地址空间主存地址空间程序地址空间程序地址空间A段段B段段虚地址虚地址实地址实地址 计算机组成原理计算机组成原理104 在段页式虚拟存储系统中在段页式虚拟存储系统中, ,每道程序每道程序通过一个段表和相应的通过一个段表和相应的一组页表来定位。
一组页表来定位 段表中每一行对应一个段段表中每一行对应一个段，其中，其中““装入位装入位””表示该段的页表表示该段的页表是否已装入主存若未装入，则应请求从辅存中调入页表；若是否已装入主存若未装入，则应请求从辅存中调入页表；若已装入，则地址字段表示该段的页表在主存中的起始位置已装入，则地址字段表示该段的页表在主存中的起始位置 “ “段长段长””字段表示该段页表的行数字段表示该段页表的行数 每个段有一个页表每个段有一个页表，页表中用，页表中用““装入位装入位””指明此段该页是否指明此段该页是否已装入主存若未装入，就需从辅存调页；若已装入，则用地已装入主存若未装入，就需从辅存调页；若已装入，则用地址字段指明该页在主存中的页号址字段指明该页在主存中的页号 计算机组成原理计算机组成原理105 段页式虚存在程序地址向实际主存地址变换时，首先要查段段页式虚存在程序地址向实际主存地址变换时，首先要查段表，然后查页表表，然后查页表 如果有多个用户在机器上运行，多道程序的每一道需要一个如果有多个用户在机器上运行，多道程序的每一道需要一个基号基号, 由它指明该道程序的段表起始地址。
由它指明该道程序的段表起始地址虚拟地址格式如下：虚拟地址格式如下： 基号 基号 段号段号 页号 页号 页内地址 页内地址某道程序地址某道程序地址程序标志程序标志 计算机组成原理计算机组成原理106 当当CPU要用到的数据或指令不在主存时，产生要用到的数据或指令不在主存时，产生页面失效页面失效(缺页缺页)，此时要从辅存调进包含这条指令或数据的页面替，此时要从辅存调进包含这条指令或数据的页面替换规则和换规则和cache中的行替换策略有很多相似之处，但有三点显中的行替换策略有很多相似之处，但有三点显著不同：著不同：(1) 缺页至少要涉及一次磁盘存取，以读取所缺的页，缺页缺页至少要涉及一次磁盘存取，以读取所缺的页，缺页使使 系统蒙受的损失要比系统蒙受的损失要比cache未命中大得多未命中大得多2) 页面替换是由操作系统软件实现的页面替换是由操作系统软件实现的3) 页面替换的选择余地很大，属于一个进程的页面都可替页面替换的选择余地很大，属于一个进程的页面都可替换 虚拟存储器中的替换策略一般采用虚拟存储器中的替换策略一般采用LRU算法、算法、LFU算法算法 FIFO算法，或将两种算法结合起来使用。
算法，或将两种算法结合起来使用1.1.替换算法替换算法替换策略替换策略 计算机组成原理计算机组成原理107例：例：假设主存只有假设主存只有a,b,c三个页框，组成三个页框，组成a进进c出的出的FIFO队列，队列，进程访问页面的序列是进程访问页面的序列是0，，1，，2，，4，，2，，3，，0，，2，，1，，3，，2号若采用若采用①①FIFO算法，算法，②②LRU算法，用列表法分别求两种替换算法，用列表法分别求两种替换策略情况下的命中率策略情况下的命中率 页面访问序列页面访问序列 0 1 2 4 2 3 0 2 1 3 2FIFO算法算法 a 0 1 2 4 3 0 2 1 3 3 b 0 1 2 2 4 3 0 2 1 1 c 0 1 1 2 4 3 0 2 2 命中命中 命中命中LRU算法算法 a 0 1 2 4 2 3 0 2 1 3 2命中率命中率2/11=18.2%3/11=27.3% b 0 1 2 4 2 3 0 2 1 3 c 0 1 1 4 2 3 0 2 1 命中命中 命中命中 命中命中 4 计算机组成原理计算机组成原理1082.2.写操作写操作 对于将被替换出去的页面，假如该页调入主存后没有被修对于将被替换出去的页面，假如该页调入主存后没有被修改改, 就不必进行处理，否则就把该页重新写入外存，以保证就不必进行处理，否则就把该页重新写入外存，以保证外存中数据的正确性。
外存中数据的正确性方法：方法： 在页表的每一行应设置一修改位在页表的每一行应设置一修改位 计算机组成原理计算机组成原理109 现代计算机一般都有辅助存储器，但具有辅存的存储系统现代计算机一般都有辅助存储器，但具有辅存的存储系统不一定是虚拟存储系统虚拟存储系统有两大特点：不一定是虚拟存储系统虚拟存储系统有两大特点：（（1 1）允许用户用比主存空间大得多的空间来访问主存允许用户用比主存空间大得多的空间来访问主存2 2）每次访存都要进行虚实地址的转换每次访存都要进行虚实地址的转换 为为了了实实现现逻逻辑辑地地址址到到物物理理地地址址的的转转换换，，并并在在页页面面失失效效时时（（即即被被访访问问的的页页面面不不在在主主存存））进进入入操操作作系系统统环环境境，，设设置置了了由由硬硬件件实实现现的的存存储储管管理理部部件件MMUMMU，，而而整整个个虚虚拟拟存存储储器器的的管管理理是是由由MMUMMU部部件件与与操操作系统共同完成的作系统共同完成的3.3.存储管理部件存储管理部件MMUMMU 计算机组成原理计算机组成原理110虚拟存储器和虚拟存储器和CacheCache存储器的不同存储器的不同 (1)(1)CacheCache存储器采用与存储器采用与CPUCPU速度匹配的快速存储元件弥补了主速度匹配的快速存储元件弥补了主存和存和CPUCPU之间的速度差异之间的速度差异, ,而虚拟存储器主要用来弥补主存和辅而虚拟存储器主要用来弥补主存和辅存之间的容量差距存之间的容量差距. . (2)(2)CacheCache存储器每次传送的信息块是定长的存储器每次传送的信息块是定长的, ,只有几十字节只有几十字节, ,而而虚拟存储器信息块划分方案很多虚拟存储器信息块划分方案很多, ,有页、段等，长度均在几百至有页、段等，长度均在几百至几百几百K K字节字节. . (3)(3)CPUCPU访问访问 CacheCache存储器的速度比访问主存快存储器的速度比访问主存快5-105-10倍倍, ,虚拟存虚拟存储器中主存的速度比辅存缩短上千倍储器中主存的速度比辅存缩短上千倍. . (4) (4)主存主存—CacheCache存储体系中存储体系中CPUCPU与与CacheCache和主存都建立了直接访和主存都建立了直接访问的通路问的通路. .而辅助存储器与而辅助存储器与CPUCPU之间没有直接通路之间没有直接通路. .(5)(5)CacheCache存储器存取信息的过程、地址变换和替换策略全部用存储器存取信息的过程、地址变换和替换策略全部用硬件实现，而虚拟存储器基本上有操作系统的存储管理软件辅硬件实现，而虚拟存储器基本上有操作系统的存储管理软件辅助一些硬件进行信息块的划分和主助一些硬件进行信息块的划分和主- -辅存之间的调度。
辅存之间的调度 计算机组成原理计算机组成原理111奔腾的虚拟存储器奔腾的虚拟存储器 实模式实模式 保护模式保护模式 虚拟虚拟8686模式模式1.Pentium1.Pentium的工作模式的工作模式保护模式保护模式 受保护的虚拟地址模式（ 受保护的虚拟地址模式（Protected Virtual Address Protected Virtual Address ModeMode）简称为保护模式这是）简称为保护模式这是8038680386才具备并一直延续下来的才具备并一直延续下来的3232位模式PentiumPentium的存储管理部件的存储管理部件MMUMMU设有分段部件设有分段部件SUSU和分页部和分页部件件PUPU，允许，允许SUSU、、PUPU单独工作或同时工作于是保护模式又细分单独工作或同时工作于是保护模式又细分为如下三种模式：为如下三种模式： 计算机组成原理计算机组成原理112 虚拟地址（或逻辑地址），由一个虚拟地址（或逻辑地址），由一个1616位的段参照和一个位的段参照和一个3232位的偏移组成段参照的最低位的偏移组成段参照的最低2 2位与保护机构打交道，高位与保护机构打交道，高1414位位用于指定具体的段。
一个进程可拥有的最大虚拟地址空间是用于指定具体的段一个进程可拥有的最大虚拟地址空间是: :1.1.分段不分页模式分段不分页模式214+32 = 246 = 64TB 由由SUSU将二维的分段虚拟地址转换成一维的将二维的分段虚拟地址转换成一维的3232位线性地址位线性地址对于分段不分页模式，这也就是它的物理地址对于分段不分页模式，这也就是它的物理地址 逻辑地址逻辑地址(虚拟地址虚拟地址)线性地址线性地址物理地址物理地址分段分段管理管理机制机制分页分页管理管理机制机制分段不分页的好处是，无需访问页目录表和页表，地址转换分段不分页的好处是，无需访问页目录表和页表，地址转换速度快 计算机组成原理计算机组成原理113 这是一种在分段基础上添加分页存储管理的模式即将这是一种在分段基础上添加分页存储管理的模式即将SUSU转转换后的换后的3232位线性地址看成由页目录、页表和页内偏移三个字段位线性地址看成由页目录、页表和页内偏移三个字段组成，由组成，由PUPU完成两级页表的查找将其转换成完成两级页表的查找将其转换成3232位物理地址位物理地址 此模式下一个进程可拥有的最大虚拟地址空间，同于分段不此模式下一个进程可拥有的最大虚拟地址空间，同于分段不分页模式，也是分页模式，也是64TB64TB。
这是一种兼顾分段分页两种优点的虚拟地址模式，受到这是一种兼顾分段分页两种优点的虚拟地址模式，受到UNIXSystemUNIXSystem V V和和OS/2OS/2操作系统的偏爱操作系统的偏爱2 2. .分段分页模式分段分页模式 逻辑地址逻辑地址(虚拟地址虚拟地址)线性地址线性地址物理地址物理地址分段分段管理管理机制机制分页分页管理管理机制机制 计算机组成原理计算机组成原理114 这个模式下 这个模式下SUSU不工作，只是不工作，只是PUPU工作程序也不提供段参照，工作程序也不提供段参照，寄存器提供的寄存器提供的3232位地址被看成是由页目录、页表和页内偏移三个位地址被看成是由页目录、页表和页内偏移三个字段组成由字段组成由PUPU完成虚拟地址到物理地址的转换完成虚拟地址到物理地址的转换 进程所拥有的最大虚拟空间是进程所拥有的最大虚拟空间是2 23232=4GB=4GB，虽然虚拟空间减小了，，虽然虚拟空间减小了，但也够用但也够用 这种纯分页的虚拟地址模式，也称为这种纯分页的虚拟地址模式，也称为平坦地址模式平坦地址模式（（flat flat address modeaddress mode）。
它也能提供保护机制，而且将虚拟存储器看成）它也能提供保护机制，而且将虚拟存储器看成是线性分页地址空间，比分段模式具有更大的灵活性是线性分页地址空间，比分段模式具有更大的灵活性 Windows NTWindows NT、、Windows 95Windows 95操作系统采用了这种模式来支持操作系统采用了这种模式来支持3232位应用程序的运行位应用程序的运行3 3. . 不分段分页模式不分段分页模式 计算机组成原理计算机组成原理1152.2.保护模式的分段地址转换保护模式的分段地址转换GDT——全局描述符表全局描述符表LDT——局部描述符表局部描述符表 计算机组成原理计算机组成原理116(1)(1)分页分页 • • 分页机制将内存划分成大小相同分页机制将内存划分成大小相同 的存储块，称为的存储块，称为物理页面；物理页面； • • 每个物理页面大小为每个物理页面大小为4K4K字节字节；； • • 内存最大内存最大4GB4GB的空间可以分为的空间可以分为 1M(1M(10485761048576) )个页面页页0页页1页页10485754KB4KB4KB物物理理地地址址空空间间4GBI.4KB.4KB分页功能分页功能3.3.保护模式的分页地址转换保护模式的分页地址转换奔腾有两种分页方式：奔腾有两种分页方式：4KB页和页和4MB页；页；4KB页是从页是从80486传承下来的分页方式；传承下来的分页方式；4MB是新增加的方式。
是新增加的方式 计算机组成原理计算机组成原理117• • 如果不允许分页，那么分段机制确定的如果不允许分页，那么分段机制确定的3232位线性地址即为物位线性地址即为物理地址理地址; ;• • 如果允许分页，如果允许分页，3232位线性地址由位线性地址由3 3个域组成：个域组成：• • 分页机制通过分页机制通过两级页表结构两级页表结构将线性地址转换成物理将线性地址转换成物理地址地址: : 第一级是第一级是页目录表页目录表；； 第二级是第二级是页表页表2)(2)线性地址格式线性地址格式页目录页目录页表页表页内偏移量页内偏移量31 22 21 12 11 0线性地址格式线性地址格式10位位 10位位 12位位 计算机组成原理计算机组成原理1181023 页页0 页页…………2047 页页1024 页页…………3071 页页2048 页页…………1048575页页1047552页页…………数据数据代码代码页面页面数据数据代码代码页面页面数据数据代码代码页面页面数据数据代码代码页面页面数据数据代码代码页面页面页目录页目录页表页表页内偏移量页内偏移量1023 纪录纪录0 纪录纪录1 纪录纪录……2 纪录纪录………线性地址线性地址目录页目录页 页表页表页面页面物理地址物理地址(3)(3)地址转换地址转换 计算机组成原理计算机组成原理119DI 计算机组成原理计算机组成原理120II.4MB.4MB分页功能分页功能• • 页面（页框）大小为页面（页框）大小为4MB4MB的分页方式使用的分页方式使用单级页表单级页表，减少了一，减少了一 次主存访问，地址转换过程加快了。
次主存访问，地址转换过程加快了• • 此方式下，此方式下，3232位线性地址分为高位线性地址分为高1010位的页面（号）和低位的页面（号）和低2222位位 的页内偏移两个字段的页内偏移两个字段• • 32 32位地址模式下，位地址模式下，全系统只一张页表全系统只一张页表，由控制寄存器，由控制寄存器CR3CR3指向 此页表有此页表有1K1K个表项，每项个表项，每项4 4字节（字节（3232位） 计算机组成原理计算机组成原理121 计算机组成原理计算机组成原理122一．判断下列各题正误，并说明理由一．判断下列各题正误，并说明理由1．ALU就是运算器2．不使用74182芯片，仅使用16片74181芯片就能构成64位ALU3．设置高速缓冲存储器的主要目的是提高存储系统的速度4．时序产生器是产生控制信号的部件3、假设在一个采用组相联映像方式的Cache中，主存有B0～B7共8块组成，Cache有C0～C3共4块，组内块数为2块每块的大小为32个字节，采用FIFO块替换算法在一个程序执行过程中依次访问块地址流如下： B1，B4，B6，B3，B0，B4，B6，B2，B4，B5 （1） 写出主存地址的格式，并标出各字段的长度 （2） 写出Cache地址的格式，并标出各字段的长度 （3） 画出主存与Cache之间各个块的映像对应关系 （4） 列出程序执行过程中Cache的块地址流分布情况。
并计算Cache的块命中率 4.Cahe 的地址映射的方式有几种 ? 其主要特点是什么 ? 5. 什么是 地址映像、地址变换？什么是 Cache 的命中率 ? 2 一个组相联映象Cache由64个存储块构成，每组包含4个存储块主存包含4096个存储块，每块由128字组成访存地址为字地址8分） （1）求一个主存地址有多少位？一个Cache地址有多少位？ （2）计算主存地址格式中，区号、组号、块号和块内地址字段的位数 6 采用虚拟存贮器的主要目的是______A 提高主存贮器的存取速度 ；B 扩大主存贮器的存贮空间，并能进行自动管理和调度 ；C 提高外存贮器的存取速度 ；D 扩大外存贮器的存贮空间 计算机组成原理计算机组成原理1237 对存储器的要求是A.______，B.______，C.______为了解决这方面的矛盾，计算机采用多级存储体系结构8 在主存和CPU之间增加cache存储器的目的是______ A. 增加内存容量 B. 提高内存的可靠性 C. 解决CPU与内存之间的速度匹配问题 D.增加内存容量，同时加快存取速度11. 设主存容量为 1MB ， Cache 容量为 16KB ，每字块有 16 个字，每字 32 位。
(1)若Cache采用直接相联映像，求出主存地址字段中各段的位数 (2)若Cache采用四路组相联映像，求出主存地址字段中各段的位数有一主存——Cache层次的存储器，其主存容量1MB，Cache容量64KB，每块8KB，若采用直接映象方式，求：①主存的地址格式？②主存地址为25301H，问它在主存的哪一块？10.某cache-主存存储体系，主存分为16个字块，cahce分为8个字块，采用直接映像1)画出主存、cache地址的对应关系2)画出主存、cache地址的映像关系3)对下列地址流：5，7，14，11，13，7，2，10，7，15，4，8，9，6，12，画出cache 块使用情况，命中率是多少？ 计算机组成原理计算机组成原理124答： （ 1 ）若 Cache 采用直接相联映像： 字块中含 64 个字节，字块的位数为 6 Cache 中含有 256 个字块，所以字块地址位数 8 主存容量为 1M 字节，总位数为 20 主存字块标记位数 6 （ 2 ）若 Cache 采用四路组相联映像， 字块中含 64 个字节，字块的位数为 6 每组含有四个字块，每组含 256 个字节。
Cache 中含有 64 个字块，所以组地址位数 6 主存容量为 1M 字节，总位数为 20 主存字块标记位数 8 11. 设主存容量为 1MB ， Cache 容量为 16KB ，每字块有 16 个字，每字 32 位 (1)若Cache采用直接相联映像，求出主存地址字段中各段的位数 (2)若Cache采用四路组相联映像，求出主存地址字段中各段的位数。