第3章存储器层次结构-5

计算机组成原理

—多层次的存储器(5)2016-3-30第3章多层次的存储器3.1存储器概述3.1.1存储器的分类3.1.2存储器的分级3.1.3主存储器的技术指标3.2SRAM存储器3.2.1基本的静态存储元阵列3.2.2基本的SRAM逻辑结构3.2.3读/写周期波形图3.3DRAM存储器3.3.1DRAM存储位元的记忆原理3.3.2DRAM芯片的逻辑结构3.3.3读/写周期、刷新周期3.3.4存储器容量的扩充3.4只读存储器和闪速存储器3.4.1只读存储器ROM3.4.2FLASH存储器3.5并行存储器3.5.1双端口存储器3.5.2多模块交叉存储器3.6cache存储器3.6.1cache基本原理3.6.2主存与cache的地址映射3.6.3替换策略3.6.4cache的写操作策3.7虚拟存储器*3.8奔腾系列的虚存组织计算机组成原理2上节回顾为解决主存和CPU之间的速度不匹配问题，依据程序访问的局部性原理，在主存和CPU之间引入Cache。Cache的功能全部通过硬件进行实现，在具体设计时，要考虑Cache容量、数据块的大小、地址映射方式、替换算法、写策略等问题。Cache的地址映射有直接映射、全相联映射、组相联映射三种方式。Cache的替换算法有FIFO法、LRU法、RAND法等。写策略有写回法、全写法（写直达法）等。计算机组成原理33.6.2主存与cache的地址映射选择哪种映射方式，要考虑：硬件是否容易实现(目标：容易)；地址变换的速度是否快(目标：快)；主存空间的利用率是否高(目标：高)；主存装入一块时，发生冲突的概率(目标：小)；计算机组成原理43.6.2主存与cache的地址映射1、全相联映射方式转换公式：

主存地址长度=(s+w)位； 主存寻址单元数=2(s+w)个字或字节； 主存的块数=2s； 块大小＝行大小=2w个字或字节； 标记tag长度=s位； cache的行数k=不由地址格式确定；特点：优点：灵活，冲突概率小，Cache的命中率和利用率高；缺点：⑴比较器难实现，需要一个访问速度很快代价高的相联存储器；⑵寻找块时，比较器比较的次数多；应用场合：小容量的Cache计算机组成原理53.6.2主存与cache的地址映射2、直接映射方式转换公式：

主存的块数=2s；

主存地址长度=(s+w)位； 寻址单元数=2s+w个字或字节； 块大小=行大小=2w个字或字节； cache的行数=m=2r； 标记大小=(s-r)位；优点：(1)硬件实现简单，成本低；(2)Cache地址为主存地址的低（r+w）位，不需变换。缺点：不灵活，存在Cache有空行不能存数据块问题，替换频繁，冲突概率高（抖动）。应用场合：适合大容量Cache，更多行数可减少冲突机会。计算机组成原理63.6.2主存与cache的地址映射3、组间直接相联、组内全相联的组相联映射方式转换公式： 主存地址长度=(s+w)位； 寻址单元数=2s+w个字或字节； 块大小=行大小=2w个字或字节； 主存的块数=2s；

Cache每组的行数=k； cache组数v=2d； cache标记大小=(s-d)位；计算机组成原理73.6.2主存与cache的地址映射1、全相联映射方式（随意坐）主存地址长度=(s+w)位； 主存寻址单元数=2(s+w)个字或字节； 主存的块数=2s； 块大小＝行大小=2w个字或字节； 标记长度=s位；

2、直接映射方式（按号入座）主存地址长度=(s+w)位； 主存寻址单元数=2(s+w)个字或字节； 主存的块数=2s； 块大小＝行大小=2w个字或字节； cache的行数=m=2r；

标记长度=(s-r)位；3、组相联映射方式（按排入座，排内随意做）

主存地址长度=(s+w)位； 主存寻址单元数=2s+w个字或字节； 块大小=行大小=2w个字或字节； 主存的块数=2s；

cache每组的行数=k； cache组数v=2d； cache标记大小=(s-d)位；计算机组成原理83.6.2主存与cache的地址映射全相联映射实例分析（注意：行=块,字长32位）[例1]：假设主存块大小为16B，主存有4096B(则有：4096B÷16B=256块，即256行)，cache有128B

(则有：128B÷16B=8行)，按字节编址(16=24，所以块内地址码4位)，若采用全相联映射；cache的当前存储情况如下所示，若访存指令的地址码依次为101010011010和100101101001，分别简述其访存过程；计算机组成原理93.6.2主存与cache的地址映射[解]：⑴访问内存单元101010011010时：取地址码的高8位10101001依次与cache中8行的标记比较，当比较到第011行的标记时发现相同(即命中cache)，则访问该行的第1010号单元，即内存地址101010011010映射到cache地址0111010；计算机组成原理103.6.2主存与cache的地址映射[解]：⑵访问内存单元100101101001时：取地址码的高8位10010110依次与cache中8行的标记比较，发现没有相同的(即不命中cache)，则访问内存的100101101001号单元;同时把内存的第10010110块（即100101100000至100101101111单元）的内容调入cache，根据一定的替换策略替换cache的某一行，假设是第101行，并用10010110覆盖第101行的标记；计算机组成原理113.6.2主存与cache的地址映射直接相联映射实例分析（注意：行=块）[例2]：假设内存块大小为16B，主存有4096B(则有:4096B÷16B=256块，即256行)，cache有128B

(则有:128B÷16B=8行)，按字节编址(16=24，所以块内地址码4位)，若采用直接相联映射；cache的当前存储情况如下所示，若访存指令的地址码依次为101010011010和100101101001，分别简述其访存过程；计算机组成原理123.6.2主存与cache的地址映射[解]：

⑴访问内存单元101010011010时：取地址码的高5位组号10101与cache中第001行的标记比较，发现相同(即命中cache)，则访问该行的第1010号单元,即内存地址101010011010映射到cache地址0011010；计算机组成原理133.6.2主存与cache的地址映射[解]：⑵访问内存单元100101101001时：取地址码的高5位组号10010与cache中第110行的标记比较，发现不相同(即不命中cache)，则访问内存的100101101001号单元；同时把内存的第10010110块（即100101100000至100101101111单元）的内容调入cache，替换cache的第110行内容，并用组号10010覆盖第110行的标记00111；计算机组成原理143.6.2主存与cache的地址映射组相联映射实例分析（注意：行=块）[例3]：假设内存块大小为16B，主存有65536B(即65536B÷16B=4096块)，cache有256B(即256B÷16B=16行)；若cache分4组(因为16÷4=4,所以每组4行)。若采用组间直接相联、组内全相联的组相联映射方式；cache的当前存储情况如下所示，若两次访存的地址码依次为1010110110011010和1001001100111001，试简述其操作过程；计算机组成原理153.6.2主存与cache的地址映射

[解]：⑴访问内存单元1010110110011010时：取地址码的高10位组号1010110110与cache中第01组的4行标记依次比较，发现与第01组的第10行相同(即命中cache)，则访问该行的第1010号单元，即内存地址1010110110011010映射到cache地址01101010；

计算机组成原理163.6.2主存与cache的地址映射

[解]：⑵访问内存单元1001001100111001时：取地址码的高10位组号1001001100与cache中第11组的4行标记依次比较,发现都不相同(即不命中cache),则访问内存的1001001100111001号单元；同时把内存的第100100110011块(即1001001100110000至1001001100111111单元)的内容调入cache，根据某种策略替换cache的第11组的某一行(假设是第00行),并用组号1001001100覆盖第11组的第00行标记1010001101；计算机组成原理173.6.2主存与cache的地址映射行号计算机组成原理183.6.2主存与cache的地址映射典型例题计算机组成原理192014-4-293.6.2主存与cache的地址映射[例9]有一个处理器，主存容量1MB，块大小16B，Cache容量64KB。若Cache采用全相联映射，对内存地址(F0010)H给出相应的标记和字号。注意：教材上该题目疏漏多，注意纠正。计算机组成原理203.6.2主存与cache的地址映射解：块大小=行大小=24字节w=4主存寻址单元数=2s+w=1M=220s+w=20位，s=16位主存的块数2s=216

，标记大小s=16位内存格式内存地址（F0010）16=（11110000000000010000）2对应的标记=1111000000000001字号=0000标记s字号w16位4位计算机组成原理213.6.3cache的替换策略1、LFU(最不经常使用)：最近一段时间内访问次数最少的行换出：每行设置计数器，初值为0；被访问的行计数器每次增1；替换计数器值最小的行；不能反映近期cache的访问情况；2、LRU(近期最少使用)：近期长久未被访问的行换出：每行设置计数器，初值为0；访问某行时，其行计数器清零，而其它行的计数器增1；替换计数器值最大的行；反映近期cache的访问情况，体现程序局部性原理；符合cache的工作原理；计算机组成原理223.6.3cache的替换策略3、FIFO(先进先出)：命不中采用先进先出策略，命中单元重新位于队首优点：容易实现缺点：没有依据程序访问的局部性原理，可能会把经常使用的程序块（循环程序）替换掉。4、随机替换：从特定的行位置中随机地选取一行换出即可优点：硬件上容易实现，且速度也比前两种策略快。缺点：没有体现程序局部性原理，随意换出的数据很可能马上又要使用，从而降低命中率和cache工作效率。但这个不足随着cache容量增大而减小。计算机组成原理233.6.4cache的写操作策略(1)写回法：写cache命中时，只修改cache内容，不立即写入主存，当此行被换出时才写回主存。每行设修改位（脏位），修改cache时，该位置1。当该行需换出时，对其修改位进行判断，决定写回主存或简单舍掉优点：减少访问主存次数；缺点：主存与cache存在不一致性隐患；(2)全写法（写直达法）：写cache命中时，Cache与内存同时写入；优点：cache不必设修改位，不存在不一致性问题；缺点：访存次数多，降低cache功效；(3)写一次法：前两种方法的结合；与写回法基本一致，不同的是第一次写Cache命中时采用全写法；计算机组成原理24小结计算机组成原理25某一主存块只能固定

映射到某一

缓存块直接全相联组相联某一主存块能映射到任一缓存块某一

主存块只能

映射到某一

缓存组

中的任一块不灵活成本高练习1.

在主存与Cache间建立地址映射，有几种不同的地址映射方式，没有的是

。A全相联映射方式 B直接映射方式C组相联映射方式 D随机映射方式2.某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是

。A.0B.2C.4D.6【例】假设主存容量为512KB，cache容量为4KB，每个字块为16个字，每个字为32位。（1）cache地址有多少位？可容纳多少块？（2）主存地址有多少位？可容纳多少块？（3）在直接映射方式下，主存的第几块映射到cache中的第5块（设起始字块为第1块）（4）画出直接映射方式下的主存地址字段中各段的位数。【例】假设主存容量为512KB，cache容量为4KB，每个字块为16个字，每个字为32位。（1）cache地址有多少位？可容纳多少块？【解】（1）cache容量为4KB=212B，即cache地址为12位，c+b=12。每个字32位=4B，每个字块为16个字，则每字块16×4B=26B，则每个字块的块内地址为6位，即b=6。c=12-b=6，C=26=64块。【例】假设主存容量为512KB，cache容量为4KB，每个字块为16个字，每个字为32位。（2）主存地址有多少位？可容纳多少块？【解】（2）主存容量512KB=219B，即主存地址为19位。m=19-b=13。M=213=8192块。【例】假设主存容量为512KB，cache容量为4KB，每个字块为16个字，每个字为32位。（3）在直接映射方式下，主存的第几块映射到cache中的第5块（设起始字块为第1块）【解】（3）i=jmodCi是cache的字块号，j是主存的字块号，C为Cache的字块数量为26=64块，主存的字块数量为213=8192块。i=5，主存的字块数分别是5，64+5，…，(27-1)26+5，共128个块。【例】假设主存容量为512KB，cache容量为4KB，每个字块为16个字，每个字为32位。（4）画出直接映射方式下的主存地址字段中各段的位数。【解】m=13，c=6，b=6，即得到t=7位。主存地址为：103.7虚拟存储器3.7.1虚拟存储器的基本概念3.7.2页式虚拟存储器3.7.3段式虚拟存储器和段页式虚拟存储器3.7.4虚存的替换算法计算机组成原理353.7.1虚拟存储器的基本概念1、虚拟存储器：一个容量非常大的存储器逻辑模型，非实际的物理存储器，由主存和联机工作的辅存共同组成，在硬件和系统软件的共同管理下工作，对应用程序员透明。2、目的：解决存储容量和存取速度矛盾问题，它具有主存的速度和辅存的容量。3、实地址和虚地址(1)虚地址(逻辑地址)：用户编程时程序(或数据)使用的地址，对应存储空间称虚存空间(逻辑地址空间)(2)实地址(物理地址)：程序或数据调入主存的主存地址，对应的存储空间称主存空间(物理存储空间)计算机组成原理363.7.1虚拟存储器的基本概念4、虚存的访问过程编程时：按虚地址编程并存在辅存；程序运行时，由地址变换机构依当时分配给该程序的实地址空间把程序(或程序一部分)调入实存。每次访存时，先判断该虚地址对应程序是否在实存：若在，则进行地址转换并访问实存；若不在，则按某算法将辅存中的程序(或程序一部分)调入实存，再按同样方法访问实存；注意：⑴每程序的虚空间大小依赖于辅存大小和程序本身实际需要，与主存大小无关：可远大于、远小于主存空间；⑵若主存命中率很高，则虚存访问时间就接近主存访问时间，此虚存机制就能实现“每个程序可拥有一个虚拟存储器，该虚拟存储器具辅存容量和接近主存的访问速度”；⑶“内存=cache+主存”；而“虚存=主存+辅存+存储管理部件(软件和硬件)”。虚存对应用程序员透明，但对设计存储管理软件的系统程序员不透明。计算机组成原理373.7.1虚拟存储器的基本概念5、虚存机制要解决的关键问题：⑴调度问题：决定哪些程序和数据调入主存；⑵地址映射问题：主存命中而访问主存时如何把虚地址变为主存地址，即“内地址变换”；主存不命中而访问辅存时如何把虚地址变为辅存地址，即“外地址变换”；此外还要解决主存分配、存储保护、程序重定位等问题；⑶替换问题：决定哪些信息调出主存而腾出空间让位于新调入的信息；⑷更新问题：确保主存和辅存的一致性；计算机组成原理383.7.2页式虚拟存储器1、页式虚存地址映射

虚存空间分成等大小逻辑页，主存空间分成与逻辑页等大小的物理页；虚、实地址都分2字段：高字段页号，低字段页内地址(偏移量)，虚、实页内地址长度一样每个进程对应一个页表页表每一项对应一个逻辑页每页表项包含有效位和主存页号页表大小由进程大小确定页表的基地址保存在页表基址寄存器页表本身一般放在主存中计算机组成原理393.7.2页式虚拟存储器2、内页表和外页表内页表：实现虚地址到主存物理地址的变换外页表：实现虚地址到辅存地址变换的表当主存缺页时，调页操作首先通过外页表确定辅存地址，外页表的结构与辅存的寻址机制有关；外页表通常放在辅存中，主存缺页时调入主存，由存储管理部件向CPU发出“缺页中断”进行调页操作。计算机组成原理403.7.2页式虚拟存储器3、页式存储器的优缺点优点：页等长且页长固定，构造页表容易，易于管理，不存在外碎片缺点：页长与程序无关，易于产生内碎片；同一程序可能部分在主存，部分在辅存，给换入换出、存储保护、存储共享等带来麻烦。计算机组成原理413.7.3段式虚拟存储器和段页式虚拟存储器1、段式虚拟存储器根据程序的自然分界将程序占据的虚空间分成长度可动态变化的若干不同类型段(如程序段、操作数段、常数段等)；虚地址由“段号”和“段内地址”组成；虚地址到实地址的转换由段表实现。每个程序设置一个段表，段表每一项对应一个段，每个段表项由“有效位(标示该段是否调入主存)”、“段起址(标示该段在主存的首地址)”和“段长(标示该段的实际长度)”三部分组成；段表大小由程序大小确定，段表的基地址保存在段表基址寄存器中，段表本身一般放在主存中，也可以放在辅存中；计算机组成原理423.7.3段式虚拟存储器和段页式虚拟存储器段式虚拟存储器的优点：段的逻辑独立性使其易于编译、管理、修改和保护，便于多道程序共享；段长可动态变化，允许自由调度，以便有效利用主存空间；段式虚拟存储器的缺点：主存空间分配麻烦；易于产生外碎片：没有内碎片，外碎片多；形成实地址麻烦：段长不一定是2的整数倍，因而虚地址的低位部分未必是段内偏移，形成实地址时必须把段起址和段内偏移相加才行(页式虚拟存储器：主存页号与逻辑页内地址拼接即可)；计算机组成原理432014-4-293.7.3段式虚拟存储器和段页式虚拟存储器地址转换：据虚地址段号和段表基地址找到对应段表项，若段表项有效位为0，则产生调段中断，从辅存调入该段；若段表项有效位为1，则取虚地址的段内地址和段表项的段长比较，段内地址大产生越界中断，段内地址小则将“段起址”+“虚地址的段内地址”形成主存的物理地址。计算机组成原理443.7.3段式虚拟存储器和段页式虚拟存储器2、段页式虚拟存储器：页式与段式的集合实存分成等大的页，程序按逻辑结构分成若干段，每段再按实存页大小分成若干页，程序按页调入调出(注意：实存中，同一程序的各段未必连续、各页未必连续)，程序按段编程、保护和共享；虚地址由“段号S、段内页号P、页内偏移D”组成，多任务操作系统还在虚地址前加一个标示程序在系统中的序号的“基号N”；每道程序通过一个段表和多个页表进行两级再定位：段表每一项对应一个段的页表首地址，页表的每一项对应一个物理页号；计算机组成原理453.7.3段式虚拟存储器和段页式虚拟存储器段页式虚拟存储器地址变换实例：[例12]假设有三道程序，基号用A、B、C表示，对应的基地址寄存器内容(段表基地址)分别为SA、SB、SC，程序A有2个段，程序B有3个段，程序C有3个段，则其逻辑地址到物理地址的变换过程如下：计算机组成原理463.7.3段式虚拟存储器和段页式虚拟存储器计算机组成原理473.7.3段式虚拟存储器和段页式虚拟存储器计算机组成原理483.7.4快表转换后援缓冲器(TLB)(块表)页表、逻辑页都在主存中，CPU取得信息至少要访问两次物理存储器为减少访存次数，对页表实现二级缓存，即把页表中活跃部分放在高速存储部件中，这种专用于存放页表部分副本的小容量高速存储部件称之为“转换后援缓冲器，通常由相连存储器实现，其作用与工作过程类似于cache)”，主存中的完整页表叫慢表；计算机组成原理492014-4-29