计算机组成原理第三章存储系统[三]

1、第三章第三章 存储系统存储系统 存储器概述存储器概述主存储器的基本构造和操作主存储器的基本构造和操作 主存储器组织主存储器组织 高速缓冲存储器高速缓冲存储器Cache Cache 高速存储器高速存储器半导体存储器芯片半导体存储器芯片虚拟存储器虚拟存储器3.5 Cache3.5 Cache存储器存储器3.5.1 3.5.1 多级存储体系结构多级存储体系结构3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存与主存与CacheCache的地址映射和地址变换的地址映射和地址变换3.5.4 Cache3.5.4 Cache的替换策略及写操作策略的替换策略及写操作策略

2、中央处理器中央处理器主存主存外存外存cachecacheCPUCPUM1M1M2M3M3辅助辅助硬件硬件辅助辅助软硬件软硬件3.5.1 3.5.1 多级存储体系结构多级存储体系结构为解决存储容量、存取速度和价格之间的矛盾为解决存储容量、存取速度和价格之间的矛盾,通常通常将各种不同存储容量、不同存取速度的存储器将各种不同存储容量、不同存取速度的存储器,按一按一定的体系结构组织起来定的体系结构组织起来,形成一个统一整体形成一个统一整体.典型的三级存储系统典型的三级存储系统: :图图3.25 三级存储系统示意图三级存储系统示意图 Cache-Cache-主存层次主存层次 CacheCache一般由一

3、般由SRAMSRAM构成构成, ,容量小容量小, ,存取速度快，依存取速度快，依据程序局部性原理据程序局部性原理, ,存放的是主存中当前最需要执存放的是主存中当前最需要执行的信息副本行的信息副本. . 目的：主存容量不足的问题目的：主存容量不足的问题. 利用辅助硬件和操作系统中的存储管理软件利用辅助硬件和操作系统中的存储管理软件, ,将将 主存和辅存构成一个整体主存和辅存构成一个整体. .目的：解决目的：解决CPUCPU和主存速度不匹配的问题和主存速度不匹配的问题. . 主存主存- -辅存层次辅存层次 总体效果：存取速度接近总体效果：存取速度接近Cache,Cache,而存储容量接而存储容量接

4、 近于辅存近于辅存, ,整体价格也较合理整体价格也较合理. .3.5 Cache3.5 Cache存储器存储器3.5.1 3.5.1 多级存储体系结构多级存储体系结构3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存与主存与CacheCache的地址映射和地址变换的地址映射和地址变换3.5.4 Cache3.5.4 Cache的替换策略及写操作策略的替换策略及写操作策略 3.5.2 Cache3.5.2 Cache工作原理工作原理CacheCache的工作机制的工作机制 CacheCache工作是以工作是以程序访问的局部性原理程序访问的局部性原理为基础的为

5、基础的, ,即即, , 一个程序的指令大都顺序存放、顺序执行一个程序的指令大都顺序存放、顺序执行, ,与程序与程序相关的数据在存储器中也相对集中相关的数据在存储器中也相对集中. .所以程序运行时所以程序运行时,尤其有循环程序段和子程序段时尤其有循环程序段和子程序段时,在在较短时间区间内较短时间区间内,常会对局部范围的存储器频繁访问常会对局部范围的存储器频繁访问,而此范围之外的地址访问甚少而此范围之外的地址访问甚少.这种现象称为这种现象称为程序访程序访问的局部性问的局部性.把局部范围的主存内容从主存放到一个高速小容量把局部范围的主存内容从主存放到一个高速小容量存储器中存储器中, ,使使CPUCP

6、U在这一段时间内直接访问它在这一段时间内直接访问它, ,以减少以减少或不去访问慢速的主存或不去访问慢速的主存 , ,程序运行速度将明显提高程序运行速度将明显提高. . 2. Cache2. Cache工作原理工作原理例例: :某机主存容量为某机主存容量为1MB, Cache1MB, Cache容量为容量为8KB,8KB,若以字节编若以字节编址址, ,每每512B512B为一块为一块, ,则主存有则主存有20482048块块, Cache, Cache有有1616块块. .块块0 000000H 00001H. 001FFH块块20472047FFE00HFFE01HFFFFFH主存主存块块0

7、00000H 0001H.01FFH块块15151E00H1E01H1FFFH Cache Cache 块的概念块的概念一般将主存和一般将主存和CacheCache的存储空间分块的存储空间分块, ,每块大小相同每块大小相同, ,包括相同数量的存储单元包括相同数量的存储单元. . Cache Cache构成及工作过程构成及工作过程CPUCPU主主存存主存主存地址地址寄存寄存器器MARMAR主存主存CacheCache地址变换地址变换机构机构( (块表块表) )CacheCache存储器存储器CacheCache地址地址寄存器寄存器替换控制部件替换控制部件ABDB单字宽单字宽多多字字宽宽不不命命中

8、中命命中中(块块) CacheCache包括包括CacheCache存储器及存储器及相应控制部件相应控制部件, ,全部由全部由硬件组成硬件组成, ,速度快速度快, ,对所有程序员均透明对所有程序员均透明. .CARCAR CacheCache命中率命中率 设设NcNc为为Cache Cache 完成存取的总次数完成存取的总次数,Nm,Nm为主存完为主存完成存取的总次数成存取的总次数, ,h h为命中率为命中率, ,则有则有: : 设设r=tm/tcr=tm/tc表示主存慢于表示主存慢于CacheCache的倍率的倍率, ,e e表示访问表示访问效率效率, ,则有则有: : 高速缓存命中率高速缓

9、存命中率:CPU:CPU访存时访存时, ,信息恰巧在信息恰巧在CacheCache中的概率中的概率. .h=Nc/(Nc+Nm)h=Nc/(Nc+Nm) 若若tc tc表示命中时的表示命中时的CacheCache访问时间访问时间,tm,tm表示未命中表示未命中时的主存访问时间时的主存访问时间,1-h,1-h表示未命中率表示未命中率, ,则则Cache /Cache /主存系主存系统的统的平均访问时间平均访问时间tata为为: :ta=htc+(1-h)tmta=htc+(1-h)tm e=tc/ta=tc/htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)he=tc/ta=tc/

10、htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)h例：例：CPUCPU执行一段程序时执行一段程序时,Cache,Cache完成存取的次完成存取的次数数19001900次次, ,主存完成存取的次数为主存完成存取的次数为100100次次, ,已知已知CacheCache的存取周期为的存取周期为1ns,1ns,主存存取周期为主存存取周期为5ns,5ns,求求Cache/Cache/主存系统的效率和平均访问时间主存系统的效率和平均访问时间. .解：解：h=Nc/(Nc+Nm)=1900/(1900+100) h=Nc/(Nc+Nm)=1900/(1900+100) =0.95=0.95

11、 r=tm/tc=5ns/1ns=5r=tm/tc=5ns/1ns=5 e=1/r+(1-r)h=1/5+(1-5)X0.95=83.3% e=1/r+(1-r)h=1/5+(1-5)X0.95=83.3% ta=tc/e=1ns/0.833=1.2ns ta=tc/e=1ns/0.833=1.2ns例例: :某计算机的存储系统由某计算机的存储系统由CacheCache和主存组成和主存组成, ,某程某程序执行过程中访存序执行过程中访存10001000次次, ,其中访问其中访问CacheCache缺失缺失( (未命中未命中)50)50次次, ,则则CacheCache的命中率是的命中率是( ).

12、( ). A.5% B.9.5% C.50% D.95% A.5% B.9.5% C.50% D.95% 影响影响 CacheCache命中率的因素命中率的因素 Cache的大小的大小 容量相对较大的容量相对较大的Cache,命中率也相应提高命中率也相应提高,但容量但容量太大太大,成本会变得不合理成本会变得不合理. 程序的特点程序的特点 遵循局部性原理的程序在运行时遵循局部性原理的程序在运行时Cache的命中率的命中率也会很高也会很高,相反相反,在程序中频繁且无规则地使用在程序中频繁且无规则地使用Call或或JMP命令命令,将严重影响基于将严重影响基于Cache的系统性能的系统性能. Cach

13、e的组织结构的组织结构 Cache组织结构的好坏组织结构的好坏,对命中率也会产生较大影对命中率也会产生较大影响响. Cache的组织结构有三种类型的组织结构有三种类型:全相联映射、直接映全相联映射、直接映射和组相联映射射和组相联映射. 3.5 Cache3.5 Cache存储器存储器3.5.1 3.5.1 多级存储体系结构多级存储体系结构3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存与主存与CacheCache的地址映射和地址变换的地址映射和地址变换3.5.4 Cache3.5.4 Cache的替换策略及写操作策略的替换策略及写操作策略 3.5.3 3

14、.5.3 主存与主存与CacheCache的地址映射和地址变换的地址映射和地址变换1. 1. 全相联映射全相联映射: :允许主存中的每一个块可以映射到允许主存中的每一个块可以映射到CacheCache的任何一块位置上的任何一块位置上. .映射过程如下图所示映射过程如下图所示: : 一一. .全相联映射及其地址变换全相联映射及其地址变换l 二者密切相关二者密切相关- -地址变换由地址映射方式决定地址变换由地址映射方式决定. .主存主存-Cache-Cache地址变换地址变换: :程序运行时程序运行时, ,根据地址映射把主根据地址映射把主存地址变换成存地址变换成CacheCache地址地址. .

15、主存主存-Cache-Cache地址映射地址映射(mapping):(mapping):把存放在主存中的把存放在主存中的程序按某种规则装入程序按某种规则装入CacheCache中中, ,并依此建立主存地址与并依此建立主存地址与CacheCache地址的对应关系地址的对应关系, ,即块表即块表. . 块表块表存放数据或指令在内存中所在单元地址的存储存放数据或指令在内存中所在单元地址的存储器器, ,用于判断用于判断CacheCache命中以及实现地址映射命中以及实现地址映射, ,其字数等于其字数等于CacheCache的块数的块数. .块块0 块块1块块15块块0块块1块块2047CacheCac

16、he主存主存全相联映射全相联映射 2.2.全相联映射方式下的地址变换全相联映射方式下的地址变换主存块号主存块号块内地址块内地址 (1) (1) 主存地址格式主存地址格式: : (标志字段标志字段)图图3.26 全相联映射示意图全相联映射示意图l例例: :某机主存容量为某机主存容量为1MB, Cache1MB, Cache容量为容量为8KB8KB，若以字，若以字节编址，每节编址，每512B512B为一块为一块, ,则主存有则主存有20482048块块, Cache, Cache有有1616块。块。v主存地址格式：主存地址格式： 0000 0000 000 0000 0000 000 0 0000

17、 00000 0000 0000 0000 0000 000 0000 0000 000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1块号块号(0块块)块内存储单元块内存储单元(0-511)(0-511)块号块号(1块块) 块内存储单元块内存储单元( 0-511)( 0-511)0000 0000 001 0000 0000 001 0 0000 00000 0000 00000000 0000 001 0000 0000 001 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1块号块号(2047块块)块内存储单元块内存储单元(0-511)(0-5

18、11)1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 111 0 0000 00000 0000 00001 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1CacheCache块号块号块内地址块内地址 主存块号转换为主存块号转换为CacheCache块号块号, ,块内地址不变块内地址不变(3) (3) 地址变换地址变换( (将主存地址转换为将主存地址转换为CacheCache地址地址): ): (2) Cache(2) Cache地址格式地址格式: :块号块号(0块块)块内

19、存储单元块内存储单元(0-511)(0-511)块号块号(1块块) 块内存储单元块内存储单元( 0-511)( 0-511) 0 00 1 0 00 1 0 0000 00000 0000 0000 0 00 1 0 00 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1块号块号(15块块)块内存储单元块内存储单元(0-511)(0-511) 1 1 1 1 1 1 1 1 0 0000 00000 0000 0000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 0 00 0 0 0000 0000 0 00 0

20、 0 0000 0000 0 00 0 1 1 1 1 1 1 1 1 10 00 0 1 1 1 1 1 1 1 1 1主存块号主存块号B(B(标志字段标志字段) )块内地址块内地址WWCacheCache块号块号b b块内地址块内地址ww主存块号主存块号B BCacheCache块号块号b bB Bb b比较比较命中命中MARMARCARCAR 图图3.27 3.27 全相联映射的地址变换全相联映射的地址变换块表块表(块表容块表容量的计算：量的计算：字数等于字数等于高缓块数，高缓块数，字长由主字长由主存块数和存块数和高缓块数高缓块数决定决定)不命中则不命中则访问主存访问主存注意注意: :在

21、全相联映射中在全相联映射中, ,主存块号作为主存块号作为识别是否命中的标志识别是否命中的标志, ,标志位的长度由主存块数决定标志位的长度由主存块数决定. .字块字块0 0字块字块1 1字块字块2 2C C -1 -1标记标记标记标记标记标记设设CacheCache有有2 2C C-1 -1块块, ,主存有主存有2 2mm-1 -1块块, ,即即CacheCache块地址有块地址有c c位位, ,主存块地址有主存块地址有mm位位. .字块字块0 0字块字块1 1字块字块2 2C C -1 -1字块字块2 2mm -1 -1主存地址格式：主存地址格式：主存字块标记主存字块标记 块内地址块内地址mm

22、位位图图3.28 3.28 全相联映射的另一种常见图解全相联映射的另一种常见图解 3.3.全相联映射的优缺点全相联映射的优缺点 i= j mod m (m(m为为CacheCache中总块数中总块数) ) 映射规则映射规则: :主存中任何一组的第主存中任何一组的第i i块只能放入块只能放入Cache Cache 的的第第i i块块. . 主存第主存第j j块块( (大排块数大排块数) )和和CacheCache第第i i块有如下函数关块有如下函数关系系: :1. 1.直接映射直接映射: :首先首先, ,主存在分块的基础上分组主存在分块的基础上分组, ,每组大小与每组大小与CacheCache的

23、大小相同。的大小相同。二二. . 直接映射及其地址变换直接映射及其地址变换 (2) (2) 缺点缺点: :块表的查找时间长块表的查找时间长, ,速度慢速度慢. .(1) 1) 优点优点: :块冲突概率最低块冲突概率最低, ,只有当只有当CacheCache中全部装满后中全部装满后, , 才有可能出现块冲突才有可能出现块冲突, ,块分配灵活；块分配灵活；其中其中,商为主存第商为主存第j块所在主存的组数块所在主存的组数,余数为在该组的块数余数为在该组的块数.块块0块块1块块15CacheCache.0 0组组1 1组组127127组组块块 0 块块 1 块块15 块块16块块17 块块31 块块2

24、047主存主存块块2032块块2033图图3.29 直接映射示意直接映射示意图图2.2.直接联映射方式下的地址变换直接联映射方式下的地址变换 CacheCache块号块号 组组号号块内地址块内地址CacheCache块号块号块内地址块内地址组内块号组内块号 (2) Cache(2) Cache地址格式地址格式: :(1) (1) 主存地址格式主存地址格式: :块号块号(0块块)块内存储单元块内存储单元(0-511)(0-511)块号块号(1块块) 块内存储单元块内存储单元( 0-511)( 0-511)0000 0000000 0000 0010 001 0 0000 00000 0000 0

25、0000000 0000000 0000 0010 001 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1块号块号(2047块块)块内存储单元块内存储单元(0-511)(0-511)1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111 111 0 0000 00000 0000 00001 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111 111 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1主存地址格式：主存地址格式：0000 0000000 0000 0 000000 0 0000 00000 0000 00000

26、000 0000000 0000 0 000000 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1组号组号(0-127)组内块号组内块号(0-15)(3) (3) 地址变换地址变换( (将主存地址转换为将主存地址转换为CacheCache地址地址): ):CacheCache块号块号b b组号组号G G( (标志字段标志字段) )MARMARCache块号块号b块内地址块内地址w w CAR CAR命中命中不命中不命中访问主存访问主存块内地址块内地址W W比较比较组号组号GCache地址地址根据根据CARCAR的内容访问的内容访问CacheCache 主存地址中的主存地址

27、中的“组内块号组内块号(Cache(Cache块号块号)+)+块内地址块内地址”= Cache= Cache地址地址注意：在直接映射中注意：在直接映射中, ,主存组号主存组号作为识别是否命中的标志，标作为识别是否命中的标志，标志位的长度由主存组数决定志位的长度由主存组数决定. .3.3.直接映射的优缺点：直接映射的优缺点：块内地址块内地址(9位位) 组内块号组内块号(4位位)组号组号(7位位) CacheCache地址格式地址格式块内地址块内地址(9位位) 块号块号(4位位)解解:(1) :(1) 主存地址格式主存地址格式 (1) (1) 分别写出主存地址格式和分别写出主存地址格式和Cache

28、Cache地址格式地址格式; ; (2) (2) 画出直接映射及地址变换图画出直接映射及地址变换图; ; (3) (3)主存地址为主存地址为0022AH0022AH的单元在的单元在CacheCache中什么位置中什么位置? ?例题例题: :某机主存容量为某机主存容量为1MB, Cache1MB, Cache容量为容量为8KB8KB，每块，每块512B,512B,如果采用直接映射如果采用直接映射, ,请回答请回答: :(2)(2)缺点缺点:Cache:Cache的空间利用率低的空间利用率低, ,块冲突较多块冲突较多, ,命中率也低命中率也低. .(1)(1)优点优点: :硬件实现简单硬件实现简单

29、, ,成本低成本低. .块块0块块1块块15Cache.0组组1组组块块 0 块块 1 块块15 块块16块块17 块块31 块块2047块块2032块块2033 127组组主存主存7位位4位位9位位组号组号G组内块号组内块号b块内地址块内地址主存地址主存地址比较比较组号组号不命不命中中,访访问主问主存存Cache地址地址01b15(2) (2) 直接映射及地址变换示意图直接映射及地址变换示意图命中命中,MARCAR4位位9位位则根据则根据CAR的内容访问的内容访问Cache地址映射地址映射地址变换地址变换 (3) 主存地址为主存地址为0022AH的单元在的单元在Cache中什么中什么位置位置

30、组组(0组组)组内块号组内块号(1块块)块内地址块内地址(42字字)另外一种求法另外一种求法: 0022AH=(0000 0000 0010 0010 1010)2因为主存第因为主存第j块和块和Cache第第i块有如下函数关系块有如下函数关系: i= j mod m (m为为Cache中总块数中总块数)这里这里,j=1,m=16,所以所以i=1 mod 16=1例例: :设一个设一个CacheCache中有中有8 8个块个块, ,访问主存进行读操作的块地址访问主存进行读操作的块地址序列为序列为2222、2626、2222、2626、1616、4 4、1616、18,18,求每次访问后求每次访问

31、后CacheCache中的内容中的内容( (设设CacheCache初始为空初始为空). ).解：解：地址地址命中与否命中与否地址转换关系地址转换关系 不命中不命中 22 MOD 8=622 MOD 8=6 不命中不命中 26 MOD 8=226 MOD 8=2 22 22 命中命中 22 MOD 8=6 22 MOD 8=6 命中命中 26 MOD 8=226 MOD 8=216 16 不命中不命中 16 MOD 8=016 MOD 8=04 4 不命中不命中 4 MOD 8=4 4 MOD 8=4 16 16 命中命中 16 MOD 8=016 MOD 8=0 18 18 不命中不命中 1

32、8 MOD 8=2 18 MOD 8=2 直接映象下直接映象下CacheCache访问情况访问情况 直接映象的块分配情况直接映象的块分配情况 访问顺序访问顺序 1 2 3 4 5 6 7 81 2 3 4 5 6 7 8 地址地址 22 26 22 26 16 4 16 1822 26 22 26 16 4 16 18块分配块分配 情况情况 2222操作操作状态状态调调进进22222626调调进进22222626命命中中22222626命命中中222226261616调调进进22224 416162626调调进进2222161626264 4命命中中2222161618184 4替替换换练习练

33、习1. 1. 设有一个设有一个CacheCache的容量为的容量为2K2K字字, ,每块每块1616字字, ,在直接映在直接映象方式下象方式下, ,求求: :(1)(1)该该CacheCache可容纳多少个块可容纳多少个块? ?(2)(2)如果主存的容量为如果主存的容量为256K256K字字, ,则有多少个块则有多少个块? ?(3)(3)主存的地址格式主存的地址格式? Cache? Cache的地址格式的地址格式? ?(4) (4) 主存中的第主存中的第032AB032AB单元映象到单元映象到CacheCache中哪一块中哪一块? ?练习练习2. 2. 设计算机的存储器为设计算机的存储器为64

34、K64K1616位位, ,直接地址映射直接地址映射的的CacheCache容量为容量为1K1K字字, ,每块每块4 4字字, ,问问: : (1) (1) 主存中地址的标志字段、块号和块内地址字段分主存中地址的标志字段、块号和块内地址字段分别有多少位？别有多少位？ （2 2）CacheCache中可装入多少块数据？中可装入多少块数据？三三. . 组相联映射组相联映射及其地址变换及其地址变换n n路组相联路组相联: :每组中有每组中有n n块块. .有有全相联映射全相联映射: :主存第主存第g g组第组第i i块可映射到块可映射到CacheCache第第i i组中任组中任一块的位置一块的位置.

35、. 有直接映射有直接映射: :主存第主存第g g组第组第i i块只能映射到块只能映射到CacheCache第第i i组组. . 1. 1.组相联映射组相联映射:Cache:Cache分成大小相等的组分成大小相等的组, ,各组再分成大各组再分成大小相等的块小相等的块. . 主存在分块的基础上分组主存在分块的基础上分组, ,每组块数等于每组块数等于Cache Cache 组数组数. . 映射规则映射规则:Cahe:Cahe分为分为mm组组, ,每组有每组有n n块块, ,则有以下关系则有以下关系: : i=j mod m i=j mod m 其中其中,i ,i为为CacheCache组号组号,j

36、,j为主存块号为主存块号( (大排大排). ).商为主存第商为主存第j j块块所在组数所在组数, ,余数为该组所在块数余数为该组所在块数. . 块块0 0块块1 1块块2 2块块3 3块块1414块块1515 0 0组组1 1组组7 7组组CacheCache主存主存块块0 0块块1 1块块2 2块块3 3块块7 7块块8 8块块1515块块1616块块1717块块20472047图图3.30 3.30 组相联映射示意图组相联映射示意图同上例同上例, ,采用采用2 2路组相联路组相联 块块9 90 0组组1 1组组 2.2.组相联映射方式下的地址变换组相联映射方式下的地址变换块内地址块内地址

37、( (CacheCache组号组号) )(1) (1) 主存地址格式主存地址格式: :(主存字块标记主存字块标记) (2) Cache(2) Cache地址格式地址格式: :块内地址块内地址组号组号组内块号组内块号 组号组号组内块号组内块号(3) (3) 地址变换地址变换( (将主存地址转换为将主存地址转换为CacheCache地址地址): ):块内地址块内地址组号组号组内块号组内块号块内地址块内地址 ( (CacheCache组号组号) )(主存字块标记主存字块标记) 组号组号组内块号组内块号主存字块标记主存字块标记组号组号G G块内地址块内地址WWMARMAR组号组号g g组内块号组内块号

38、b b块内地址块内地址wwCARCAR比较比较不命中不命中访问主存访问主存命中命中主存字块标记主存字块标记CacheCache组内块号组内块号b b访问访问CacheCache图图3.31 3.31 组相联映射的地址变换示意图组相联映射的地址变换示意图块表块表v 例例(2009):(2009):某计算机的某计算机的CacheCache共有共有1616块块, ,采采用用2 2路组相联路组相联( (即每组即每组2 2块块). ).每个主存块大每个主存块大小为小为3232字节字节, ,按字节编址按字节编址. .主存主存129129号单元号单元所在主存应装入到得所在主存应装入到得CacheCache组

39、号是组号是( ).( ).vA. 0 B.2 C.4 D.6A. 0 B.2 C.4 D.6v 例例: :在下列因素中在下列因素中, ,与与CacheCache的命中率无关的命中率无关的是的是( ).( ).v A. Cache A. Cache块的大小块的大小v B. CacheB. Cache的容量的容量v C. C. 主存的存取时间主存的存取时间v 例：假设主存容量为例：假设主存容量为512K512K1616位位,Cache,Cache容量容量为为409640961616位位, ,块长为块长为4 4个个1616位的字位的字, ,访存地址访存地址为字地址为字地址. .v(1)(1)在直接映

40、射方式下在直接映射方式下, ,设计主存地址格式设计主存地址格式. .v(2)(2)在全相联映射方式下在全相联映射方式下, ,设计主存地址格式设计主存地址格式. .v(3)(3)在在2 2路组相联映射方式下路组相联映射方式下, ,设计主存地址格设计主存地址格式式. .v 解解:(1):(1)在直接映射方式下在直接映射方式下,Cache,Cache分分4096/4=24096/4=21010块块, ,主存分主存分2 21919/4=2/4=21717块块, ,主存分主存分2 21919/2/21212=2=27 7组组. .v 故主存地址格式故主存地址格式: :主存组数主存组数(7(7位位) )组

41、内块数组内块数(10(10位位) )块内地址块内地址(2(2位位) )v(2)(2)在全相联方式下在全相联方式下, ,CacheCache分分4096/4=24096/4=21010块块, ,主存分主存分2 21919/4=2/4=21717块块. .v故主存地址格式故主存地址格式: :主存块数主存块数(17(17位位) )块内地址块内地址(2(2位位) ) (3)(3)在组相联映射方式下在组相联映射方式下, , CacheCache分分4096/4=24096/4=21010块块,2,2块一组块一组,Cache,Cache分分2 21010/2=2/2=29 9组组; ;主主存分存分2 21

42、919/4=2/4=21717块块, ,每组分每组分2 29 9块块, ,主存分主存分2 21717/2/29 9=2=28 8组组. .v故主存地址格式故主存地址格式: :块内地址块内地址 ( (CacheCache组号组号) )(主存字块标记主存字块标记)组号组号(8位位)组内块号组内块号(9位位) (2位位)练习练习1. 1. 设有一个设有一个CacheCache的容量为的容量为2K2K字字, ,每块每块1616字字, ,在直接在直接映象方式下映象方式下, ,求求: :(1)(1)该该CacheCache可容纳多少个块可容纳多少个块? ?(2)(2)如果主存的容量为如果主存的容量为256

43、K256K字字, ,则有多少个块则有多少个块? ?(3)(3)主存的地址格式主存的地址格式? Cache? Cache的地址格式的地址格式? ?(4) (4) 主存中的第主存中的第032ABH032ABH单元映象到单元映象到CacheCache中哪一块中哪一块? ? 解解:(1):(1) CacheCache可容纳的块数为可容纳的块数为:2K/16=2:2K/16=27 7=128(=128(块块) )(2) (2) 主存的可容纳的块数为主存的可容纳的块数为: 256K/16=2: 256K/16=21414( (块块) ) (3) (3) 主存地址格式为主存地址格式为: :块内地址块内地址(

44、4位位) 组内块号组内块号(7位位)组号组号(7位位) CacheCache地址格式为地址格式为: :块内地址块内地址(4位位) 组内块号组内块号(7位位)(4) 主存中的主存中的032ABH单元单元:032ABH=(0000 0011 0010 1010 1011)2 6 6组组 42 42块块1111字字另外一种求法另外一种求法: :因为主存第因为主存第j j块和块和CacheCache第第i i块有如下函数关系块有如下函数关系: : i= j mod m (m i= j mod m (m为为CacheCache中总块数中总块数) )这里这里,j=2,j=29 9+2+28 8+2+25

45、5+2+23 3+2+21 1=810,m=128,=810,m=128,所以所以i=1 mod m=810 mod 128=42i=1 mod m=810 mod 128=42 3.5 Cache3.5 Cache存储器存储器3.5.1 3.5.1 多级存储体系结构多级存储体系结构3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存与主存与CacheCache的地址映射和地址变换的地址映射和地址变换3.5.4 Cache3.5.4 Cache的替换策略及写操作策略的替换策略及写操作策略3.5.4 3.5.4 CacheCache的替换策略及写操作策略的替换

46、策略及写操作策略LRU-Least Recently UsedLRU-Least Recently UsedFIFO-First In First OutFIFO-First In First OutRANDRAND 常用替换算法常用替换算法: : 注意注意: :只有全相联和组相联的高速缓存中有替换策略只有全相联和组相联的高速缓存中有替换策略问题问题. . 替换策略替换策略(replacement policy): Cache(replacement policy): Cache地址变换中地址变换中一旦发生不命中一旦发生不命中, ,需将主存中一个新块调入需将主存中一个新块调入Cache,Cac

47、he,如如果此时发生块冲突果此时发生块冲突, , 决定从决定从CacheCache中选择哪一个数据中选择哪一个数据块块, ,并将其从并将其从CacheCache中移去中移去, ,将新的数据块写入的方法将新的数据块写入的方法. . 一一. Cache. Cache的替换策略的替换策略 1. RAND1. RAND算法算法 特点特点: :符合局部性原理符合局部性原理, ,命中率较高命中率较高. . 方法方法: :根据局部性原理选择近期用的最少的数据块根据局部性原理选择近期用的最少的数据块作为替换的块作为替换的块. .具体做法具体做法: :为每一块设置一个计数器为每一块设置一个计数器, ,当当某一块

48、命中时某一块命中时, ,其计数器清其计数器清0,0,其它各块的计数器增其它各块的计数器增1, 1,当当需要替换时需要替换时, ,将计数值大的块替换出将计数值大的块替换出. .3. 3. LRULRU算法算法 特点特点: :较简单较简单, ,但没有体现程序局部性规律但没有体现程序局部性规律, ,不能提不能提高高CacheCache命中率命中率. .方法方法: :选择最早调入选择最早调入CacheCache的块进行替换的块进行替换. . 2. 2. FIFOFIFO算法算法 方法方法: :随机地确定替换块随机地确定替换块. .特点特点: :容易实现容易实现, ,执行速度快执行速度快, ,但没有体现

49、程序局部性规律但没有体现程序局部性规律, ,不能提高不能提高CacheCache命中率命中率. .二、二、CacheCache的写操作策略的写操作策略 CacheCache内容是主存部分内容的副本内容是主存部分内容的副本, ,在命中的情在命中的情况下况下, ,如果如果CPUCPU对对CacheCache写入写入, ,改变了改变了Cache (dirty block)Cache (dirty block)的内容的内容, ,如何保证主存内容与如何保证主存内容与CacheCache内容一致内容一致. .缺点缺点: :当当CPUCPU向主存写操作时向主存写操作时, Cache, Cache无高速缓冲无

50、高速缓冲功能功能, ,降低了降低了CacheCache的功效的功效. . 优点优点: :写主存与写写主存与写CacheCache同步同步. . 1. 1.直达法直达法(write through)(write through)(通过式写入通过式写入): ):每次写入每次写入CacheCache时同时写入主存时同时写入主存, ,使主存与使主存与CacheCache相关块内容始终保持一相关块内容始终保持一致致. . 2. 2. 写回法写回法(write back)(write back)(标志交换方式标志交换方式): Cache): Cache中每一块各作一个标记中每一块各作一个标记( (清清未修

51、改过未修改过; ;浊浊修修改过改过), ),命中需将信息写入主存时命中需将信息写入主存时, ,暂只写入暂只写入 Cache, Cache, 并不写入主存并不写入主存, , 只有当该块需要从只有当该块需要从CacheCache中替换出来时中替换出来时, ,若其标记为若其标记为”浊浊”, ,再一次性写入再一次性写入主存主存. . 缺点缺点: :存在存在CacheCache与主存数据不一致的隐患与主存数据不一致的隐患. .优点优点: :减少对主存的写操作次数减少对主存的写操作次数, , 工作速度较快工作速度较快. .作业作业1: 1:某一某一Cache-Cache-主存采用组相联的方法进行地址转换主存采用组相联的方法进行地址转换.