计算机存储器的层次结构-文档资料

1、2003.3.113.1.2 存储器的层次结构存储器的层次结构第一层第二层第三层第四层第五层每级存储器的性能参数可以表示为每级存储器的性能参数可以表示为TiTi，SiSi，CiCi。存储系统的。存储系统的性能可表示为：性能可表示为：TiTi+1TiTi+1；SiSi+1SiCi+1CiCi+1。速速 度度 提提 高高容容 量量 增增 加加 通用寄存器通用寄存器M1高速缓冲存储器高速缓冲存储器M2 主存储器主存储器M3 脱机大容量存储器脱机大容量存储器M5 辅助存储器辅助存储器M4 2003.3.12 Data location Data identifacation Data replacem

2、ent Data Write policy2003.3.13地址映象与变换(P174)基本术语：基本术语： 逻辑地址逻辑地址（又称为相对地址相对地址、虚地址虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间逻辑地址空间、虚空间虚空间或虚存虚存。 物理地址物理地址（又称为绝对地址绝对地址、实地址实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间物理地址空间、实空间实空间或实存实存。 从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空

3、间只有一个。 地址映象地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。 地址变换地址变换（又叫虚实变换虚实变换）指逻辑地址到物理地址的变换过程或者算法。 页失效页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。 实页争用实页争用又叫实页冲突实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。2003.3.14存储层次的管理方式(P147) 根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。(1)段式管理段式管理(P148) 段是程序中的一个逻辑单位，可以是一个程

4、序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。 每段使用独立的逻辑地址空间，即都从0开始计算地址。 段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。 段式管理方法的虚实变换算法是查段表(P150)。2003.3.15段式虚拟存储器的地址映象 主程序（0段）1段2段3段段号段长起始地址01231K5002002008K16K9K30K段 表程序空间主存储器01K05000200020008K9K16K30K2003.3.16段式虚拟存储器的优点如下：程序的模块性能好。对于大程序，可以划分成多个程 序段，每个程

5、序段赋予不同的名字，由多个程序员并行编写，分别编译和调试。由于各个程序段在功能上是相互独立的，因此，一个程序段的修改和增删等不会影响其他程序段，从而可以缩短程序的编制和调试时间。便于程序和数据的共享。由于程序段是按功能来划分的，如子程序段、数据段、表格段等。每个程序段有比较完整的功能，因此，被共享的可能性很大。程序的动态链接和调试比较容易。由于每个程序段都是一组有独立意义的数据块或具有完整功能的程序段，因此，在程序运行过程中，可以根据需要一次就把一个程序段或数据块都装入到主存储器中，并且在装入时才实行动态链接。 1.便于实现信息保护。在一般情况下，一段程序是否需要保护是根据这个程序的功能来决定

6、的。因此，只有在段表中设置一个信息保护字段，就能根据需要很方便地实现对该程序的保护。2003.3.17段式虚拟存储器的缺点：地址变换所花费的时间比较长。从多用户虚地址变换到主存实地址需要查两次，做两次加法运算。主存储器的利用率往往比较低。由于每个程序段的长度不同的，一个程序段通常要装在一个连续的主存空间中，程序段在主存储器中不断地调入调出，有些程序段在执行过程中还要动态增加长度，从而使得主存储器中有很多的空隙存在。当然，也可以采用一些好的算法来减少空隙的数量，或者通过定时运行回收程序来合并着这些空隙，但这无疑增加了系统的开销。1.对辅存（磁盘存储器）的管理比较难。磁盘存储器通常是按固定大小的块

7、来访问的，如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要做一次地址变换。 2003.3.18(2)页式管理页式管理(P151)。 页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。 我们把用户文件划分得到的一个长度单位称为“虚页虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页实页”。 页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。 页式管理方法的虚实变换算法是查页表(P152)。页号主存页号0123主存储器页 表0页1页2页3页用户程序页式虚拟存储器的地址映象2003.3

8、.19页式虚拟存储器的优点是：主存储器的利用率比较高。每个用户程序只有不到一页（平均为半页）的浪费，与段式虚拟存储器每两个程序段之间都有浪费相比要节省许多。页表相对比较简单。它需要保存的字段数比较少，一些关键字段的长度要短许多，因此，节省了页表的存储器容量。地址映象和变换的速度比较快。在把用户程序装入到主存储器的过程中，只要建立用户程序的虚页号与主存储器的实页号之间的对应关系即可不必使用整个主存的地址长度，也不必考虑页号的长度等。对辅存（磁盘存储器）的管理比较容易。因为页的大小一般取磁盘存储器物理块的大小（512字节）的整数倍。页式虚拟存储器的缺点主要有两个： 程序的模块化性能不好。由于用户程

9、序是强制按照固定大小的页来划分的，而程序段的实际长度一般是不固定的。因此，页式虚拟存储器中一页通常不能表示一个完整的程序功能。1.页表很长，需要占用很大的存储空间。通常，虚拟存储器中的每一页在页表中都需要占用一个存储字。2003.3.110(3)段页式管理段页式管理(P153)。 它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。 其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P154)。 段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。 由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理，为

10、了叙述简单，下面的分析还是以页式管理为模型。2003.3.111段页式虚拟存储器的地址映象0段（12K）1段（10K）2段（5K）每页4KB页表长度页表地址332段 表0段0页0段1页0段2页1段0页1段1页1段2页0段页表1段页表2段0页2段1页2段页表用户程序主存储器2003.3.112相联目录表技术1.1.页表占用空间过大问题页表占用空间过大问题 页表必须存放在实存M1里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在M2。 页表占用空间 = 页表行数 每行宽度其中，页表行数 = 虚存容量 / 页面大小 以PC机为例，页表行数 64G / 4K = 23

11、6 / 212 = 224 1600万！按每行宽度6字节估算约需96MB。 减少页表空间的思路分减少行数和减少行宽两类。2.2.相联目录表方法（相联目录表方法（P158P158） 仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。3.3.快慢表方法（快慢表方法（P159P159）4.4.通过地址映象减少行宽通过地址映象减少行宽 如下文所示2003.3.1134种常见的地址映象方式3.3.1 全相联(P174) 全相联全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。 虚存 实页 0 1 2 3 0

12、0 1 实存 1 2 0 2 3 1 虚 3 4 2 页 4 5 3 5 6 6 7 7 (a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系） 全相联的地址映象方式与地址变换原理示意图(a)(b)2003.3.114全相联的地址映象方式与地址变换原理示意图(c)虚地址虚页号 P页内偏移量 D实地址实页号 p页内偏移量d实页号 装入位 修改位表项 0 ： ： ： ： ：表项 P p1 0 ： ： ：表项 7 ： ：(c) 通过查表进行虚实变换全相联的虚实变换信息完全来自于变换表。 全相联映象使虚页调入有最大的选择范围，发生实页争用可能性最小，调入/调出操作开销也最少，有利于命中率

13、提高。但页表占用空间和查表时间开销较大, 实现成本较高，命中时的虚实变换时间也较多。由于页表必须常驻实存，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象一般用于主存-辅存层次。2003.3.1153.3.2 直接相联(P176) 直接相联直接相联是一种最强的约束关系，规定每个虚页只对应唯一实页。为便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现简单，二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位。 例已知虚页号 = 7，实页总数 = 4，用直接相联求实页号。 解：可用十进制形式求：

14、7 mod 4 = 3； 也可用二进制形式求：由于n = 4，所以log2n = 2， 取7的二进制形式111B的最低2位，得11B，即3。 直接相联映象不需借助页表进行虚实变换，节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页选择范围太小，实页争用频率较高，常出现实存有空闲空间却不得不调出一个现有虚页以腾出实页的情况，使系统的命中率和运行效率大大下降。 这种映象方式主要用于对实存价格非常敏感的Cache-主存层次。2003.3.116直接相联的地址映象方式与地址变换原理 虚存 实页0123 00 1 实存1 202 31虚 3 42页 4 535 66 77(a

15、) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）虚地址 虚页号 1 1 1页内偏移量 D实地址实页号 1 1页内偏移量d(c) 通过求模运算进行虚实变换示例2003.3.117例：假设在某计算机系统中Cache容量为64K字节，数据块大小是 16个字节，主存容量是4M，地址映象为直接相联方式。（1）主存地址多少位？如何分配？（2）Cache地址多少位？如何分配？（3）目录表的格式和容量？主存地址格式：主存地址格式： 区号区号区内块号区内块号块内地址块内地址21 16 15 4 3 0 缓存地址格式：缓存地址格式： 块块 号号块内地址块内地址15 4 3 0 目录表的格式：目录表

16、的格式： 主存区号主存区号有效位有效位6 1 0 解： 容量：应与缓存块数量相同即容量：应与缓存块数量相同即212=4096 2003.3.1182003.3.1193.3.3 组相联(P178) 组相联组相联映象是全相联与直接相联的一个折中方案，性能也是二者折中。做法：先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。虚组按直接相联方式映射到实组集合，对应虚实组间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。组相联的地址映象方式与地址变换原理(a)(b) 虚存 实页0123虚组 0 00 1 实存1虚组 1 20 实组 02 31虚3虚组 2 42 实组

17、1页4 535虚组 3 66 77(a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）2003.3.120组相联的地址变换区号区号E组号组号G组内块号组内块号B块内地址块内地址W块内地址块内地址w组内块号组内块号b组号组号g相联比较相联比较主存地址主存地址相等相等Cache地址地址Cb个块个块区号区号E，组内块号，组内块号B组内块号组内块号b由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”2003.3.121例：主存容

18、量为1MB，缓存容量为32KB，每块为64个字节， 缓存共分128（27）组。请写出：（1）主存与Cache的格式；（2）相关存储器的格式与容量解：主存地址：主存地址： 区号区号组号组号块号块号块内地址块内地址19 15 14 8 7 6 5 0 缓存地址：缓存地址： 组号组号块号块号块内地址块内地址14 8 7 6 5 0 区号区号Ei块号块号Bi缓存块号缓存块号bi装入位装入位9 5 4 3 2 1 0 相关存储器的格式：相关存储器的格式：相关存储器的容量，应与缓存的块数相同，即相关存储器的容量，应与缓存的块数相同，即: 组数组数组内块数组内块数=1284=512 2003.3.122 这

19、两方面优点互相抵触：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。 这种映象方式性价比较好，在Cache-主存层次中被普遍使用。 组相联映象方式的组相联映象方式的优点优点： 块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低：每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低。另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。 组相联映象方式的组相联映象方式的缺点缺点： 实现难度和造价要比

20、直接映象方式高。2003.3.1233.3.4 段相联(P184) 段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图(a)、(b)所示（设实段数为2）。 虚存 实页0123虚段 0 00 1 实存1虚段 1 20 实段 02 31虚 3虚段 2 42 实段 1页 4 535虚段 3 66 77(a) 虚页集合与实页集合的对应关系 (b) 对应关系表（为有关系）段相联的地址映象方式与地址变换原理(a)(b)2003.3.124 段

21、相联的虚实变换与组相联类似，不过通过计算来确定的部分是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为“段号查表、段内复制”。2003.3.125 段相联方式的主要段相联方式的主要优点优点：段表比较简单，实现成本低。例如：例如：容量为256KB Cache，分8段，每段2048块，每块16B。 在段表存储器中只需要存储8个主存地址的段号S。 段相联方式的主要段相联方式的主要缺点缺点： 当发生段失效时，要把本段内已经建立的映象关系全部撤消。 段相联映象方式的虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相

22、同，所以虚段号比实段号位数多，也就意味着“多少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。2003.3.126多用户虚地址格式 在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从CPU发出的虚地址还需要在前面拼接上一个“当前用户号”字段，形成“多用户虚地址”，如下图所示(参见P154)。 在虚实变换时，上面所说的各种查表操作之前还得先去查一个“段表基址寄存器组”或“页表基址寄存器组”的小表格(P150，P152)，确定现在该查哪一张段表或页表。这个小表格建立在CPU里，读写

23、时间很短。当前用户号虚段号虚页号页内偏移量思考题：P203，题112003.3.1273.4 替换算法(P164) 上面所讲地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。 不命中时需要增加的操作就是首先调出一页，调出之后再调入称为 “替换”。 替换算法要解决的是选择调出对象的问题。 替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。2003.3.1283.4.1 几种常用的替换算法(P164)(1) 随机算法RAND 在比较范围内

24、任取一页作为淘汰页；优点：算法简单，容易实现。缺点：没有利用历史信息，没有反映程序的局部性，命中率低。(2) 先进先出算法FIFO 在比较范围内选取调入最早的一页作为淘汰页；优点：比较容易实现，利用了历史信息，没有反映程序的局部性。缺点：最先调入主存的页面，很可能也是经常要使用的页面。(3) 最不经常使用算法LFU 在比较范围内选取最近单位时间内使用 次数最少的一页作为淘汰页；优点：既充分利用了历史信息，又反映了程序的局部性缺点：实现起来非常困难。2003.3.129(4) 最不接近使用算法LRU 在比较范围内选取最后一次使用离现在最久 的一页作为淘汰页；(5) 最优替换算法OPT 在比较范围

25、内选取下一次使用时间离现在最久 的一页作为淘汰页。优点：它把LFU算法中的“多”与“少”简化成“有”与“无”， 实现起来比较容易。是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。2003.3.130从LFU到LRU的近似逻辑推理：近期最少使用LFU 最近一个单位时间内使用次数最少 相邻两次使用的平均间隔时间最大 上次使用时间离现在最久 最久没有使用LRU偶然偏差：使用稀疏的页面有可能恰巧刚刚用过，离现在更近。统计性能：“现在”离“上次”使用时间的平均距离，应为相邻两次使用时间距离的1/2，所以大多数情况下LRU与LFU的判断结论应该是一致的。页面 A 访问使用频繁，相邻使用间隔小上

26、次使用时间离现在近时间 t页面 B 访问使用稀疏，相邻使用间隔大上次使用时间离现在远时间 t现在（要淘汰一页）2003.3.131算法模拟：实存状况图（P166图3.32）以 LRU 算法为例（其中*号表示被选中的淘汰页）：已访问次数 t012345678910被访问虚页号无1215413424命中总次数0空11111*111*221空空222*444*444实存空间使用情况（实页号为 0、1、2）2空空空空555*333*3*操作名称初态(空)调入调入命中调入替换命中替换命中替换命中4 次被访问实页号01021021012003.3.1322003.3.133 这是对某些替换算法的统称。如果

27、某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集（当容量超过虚页总数时，保留页面集合相同），则小容量下的命中点到大容量情况下仍然是命中点，并且随着容量加大，还可能会有新的命中点产生。具有这一特性的一类替换算法中成为“堆栈型算法”。例如：P166图3.32中，对LRU算法，如果实页数增加到4，则t=5时为了调入虚页4就不必替换掉虚页2，而是将虚页1、2、4、5都留在实存，这时大容量分区情况下的保留页面集合S2 = 1，2，4，5，同一时刻的小容量分区情况下的保留页面集合S1 = 1，4，5。显然有S1S2。 P167第48行是堆栈型算法的数学定

28、义。 堆栈型替换算法的主要性质就是命中率H随着实页分区容量n的上升而单调上升（不减性）。 可以证明，LFU、LRU、OPT等算法都是堆栈型算法，而RAND和FIFO算法不是堆栈型算法。P168的图3.34是一个实例，当实页数从3增加到4时，FIFO的命中率反倒从3降到2。具体观察，比如t = 7时，S1 = 1，2，5，S2 = 2，3，4，5，不满足子集关系。所以FIFO不能保证当实页数增加时，原来的命中点不丢。3.4.2 堆栈型替换算法(P166)2003.3.134实例：堆栈模拟图 研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如P167倒数第3行的PFF法），另一方面也

29、可推导出一些分析工具，例如“堆栈模拟法”。 堆栈模拟图可以通过一次作图，描述同一地址流在各种实存分区容量下的命中情况。 例3.4t123456789101112P232152453252st(1)232152453252st(2)23215245325st(3)321524533st(4)33112444st(5)331111st(6)命中次数n=10n=2*2n=3*5n=4*6n=5*72003.3.1353.5 提高命中率的方法影响命中率的主要因素：(1) 程序在执行过程中的页地址流分布情况。(2) 所采用的页面替换算法。(3) 页面大小。(4) 存储器的容量(5) 所采用的页面调度方法

30、。以下，对后三个因素进行分析。 2003.3.1361. 页面大小与命中率的关系 页面大小为某个值时，命中率达到最大。 解释：假设At和At+1是相邻两次访问主存储器的逻辑地址，d=|At - At+1|。 如果dSp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。随着Sp的增大而降低。1命命 2S中中率率 SH 页面大小页面大小SP 页面大小与主存命中率的关系页面大小与主存命中率的关系当Sp比较小的时候，前一种情况是主要的，随着Sp的增大而提高。当Sp达到某一最大值后，后一种情况成为主要的，随Sp增大而降低。 当页面大小增大时，造成的浪费也要增加

31、；当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。2003.3.1372. 主存容量与命中率的关系 主存命中率H随着分配给该程序的主存容量S的增加而单调上升。 在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。1.0 命命 中中 率率 H 主存容量主存容量S 主存命中率主存命中率H于贮存容量于贮存容量S的关系的关系2003.3.1383. 页面调度方式与命中率的关系 请求式：当使用到的时候，再调入主存。 预取式：在程序重新开始运行之前，把上次停止运行前一段 时间内用到的页面先调入到主存储器，然后才开始 运行程序。 优点

32、：可以避免在程序开始运行时，频繁发生页面失效的情况。 缺点：如果调入的页面用不上，浪费了调入的时间，占用了主 存资源。 2003.3.1393.6 虚拟存储器与Cache的特点(P146，P172)常用的两种存储系统:1. Cache 存储系统: 由 Cache + + 主存储器构成Cathe主存储器从系统程序员看2. 虚拟存储系统 : 主存储器 + 磁盘存储器主存磁盘存储器从应用程序员看2003.3.140虚拟存储器与Cache的主要区别（P173页）存储系统存储系统Cache虚拟存储器虚拟存储器要达到的目标提高（主存）速度扩大（主存）容量实现方法全部硬件软件为主，硬件为辅两级存储器的速度比

33、3倍10倍105倍页（块）大小1字16字1KB16KB等效存储容量主存储器虚拟存储器透明性对系统和应用程序员仅对应用程序员不命中时处理方式等待主存储器任务切换2003.3.141 使用Cache的动机动机： 容量大的存储器（DRAM）速度慢 容量小的存储器（SRAM）速度快通过如下策略，使得平均访问时间变小： 在小量、高速的存储器中完成大多数访问减少对大容量存储器的带宽要求。2003.3.142Cache 块号B块内地址W 主存-Cache地址变换 块号b块内地址w Cache替换部件 主存地址替换块装入块不命中命中数据或指令Cache地址主存地址(来自CPU) 已满未满主存储器2003.3.143 工作流程命中不命中已满替换策略替换块未满装入块 与虚存（VM）的区别