2017/5/22,计算机系统结构,1,3.1.2 存储器的层次结构,每级存储器的性能参数可以表示为Ti，Si，Ci。存储系统的性能可表示为：TiTi+1；SiCi+1。,速 度 提 高,容 量 增 加,2017/5/22,计算机系统结构,2,Data locationData identifacationData replacementData Write policy,2017/5/22,计算机系统结构,3,地址映象与变换(P174),基本术语： 逻辑地址（又称为相对地址、虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。 物理地址（又称为绝对地址、实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。 从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。 地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。 地址变换（又叫虚实变换）指逻辑地址到物理地址的变换过程或者算法。 页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。 实页争用又叫实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。,2017/5/22,计算机系统结构,4,存储层次的管理方式(P147),根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。(1)段式管理(P148) 段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。 每段使用独立的逻辑地址空间，即都从0开始计算地址。 段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。 段式管理方法的虚实变换算法是查段表(P150)。,2017/5/22,计算机系统结构,5,段式虚拟存储器的地址映象,2017/5/22,计算机系统结构,6,段式虚拟存储器的优点如下：程序的模块性能好。对于大程序，可以划分成多个程 序段，每个程序段赋予不同的名字，由多个程序员并行编写，分别编译和调试。由于各个程序段在功能上是相互独立的，因此，一个程序段的修改和增删等不会影响其他程序段，从而可以缩短程序的编制和调试时间。便于程序和数据的共享。由于程序段是按功能来划分的，如子程序段、数据段、表格段等。每个程序段有比较完整的功能，因此，被共享的可能性很大。程序的动态链接和调试比较容易。由于每个程序段都是一组有独立意义的数据块或具有完整功能的程序段，因此，在程序运行过程中，可以根据需要一次就把一个程序段或数据块都装入到主存储器中，并且在装入时才实行动态链接。 便于实现信息保护。在一般情况下，一段程序是否需要保护是根据这个程序的功能来决定的。因此，只有在段表中设置一个信息保护字段，就能根据需要很方便地实现对该程序的保护。,2017/5/22,计算机系统结构,7,段式虚拟存储器的缺点：地址变换所花费的时间比较长。从多用户虚地址变换到主存实地址需要查两次，做两次加法运算。主存储器的利用率往往比较低。由于每个程序段的长度不同的，一个程序段通常要装在一个连续的主存空间中，程序段在主存储器中不断地调入调出，有些程序段在执行过程中还要动态增加长度，从而使得主存储器中有很多的空隙存在。当然，也可以采用一些好的算法来减少空隙的数量，或者通过定时运行回收程序来合并着这些空隙，但这无疑增加了系统的开销。对辅存（磁盘存储器）的管理比较难。磁盘存储器通常是按固定大小的块来访问的，如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要做一次地址变换。,2017/5/22,计算机系统结构,8,(2)页式管理(P151)。 页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。 我们把用户文件划分得到的一个长度单位称为“虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页”。 页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。 页式管理方法的虚实变换算法是查页表(P152)。,页式虚拟存储器的地址映象,2017/5/22,计算机系统结构,9,页式虚拟存储器的优点是：主存储器的利用率比较高。每个用户程序只有不到一页（平均为半页）的浪费，与段式虚拟存储器每两个程序段之间都有浪费相比要节省许多。页表相对比较简单。它需要保存的字段数比较少，一些关键字段的长度要短许多，因此，节省了页表的存储器容量。地址映象和变换的速度比较快。在把用户程序装入到主存储器的过程中，只要建立用户程序的虚页号与主存储器的实页号之间的对应关系即可不必使用整个主存的地址长度，也不必考虑页号的长度等。对辅存（磁盘存储器）的管理比较容易。因为页的大小一般取磁盘存储器物理块的大小（512字节）的整数倍。页式虚拟存储器的缺点主要有两个： 程序的模块化性能不好。由于用户程序是强制按照固定大小的页来划分的，而程序段的实际长度一般是不固定的。因此，页式虚拟存储器中一页通常不能表示一个完整的程序功能。页表很长，需要占用很大的存储空间。通常，虚拟存储器中的每一页在页表中都需要占用一个存储字。,2017/5/22,计算机系统结构,10,(3)段页式管理(P153)。 它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。 其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P154)。 段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。 由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理，为了叙述简单，下面的分析还是以页式管理为模型。,2017/5/22,计算机系统结构,11,段页式虚拟存储器的地址映象,2017/5/22,计算机系统结构,12,相联目录表技术,1.页表占用空间过大问题 页表必须存放在实存M1里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在M2。 页表占用空间 = 页表行数 每行宽度其中，页表行数 = 虚存容量 / 页面大小 以PC机为例，页表行数 64G / 4K = 236 / 212 = 224 1600万！按每行宽度6字节估算约需96MB。 减少页表空间的思路分减少行数和减少行宽两类。2.相联目录表方法（P158） 仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。3.快慢表方法（P159）4.通过地址映象减少行宽 如下文所示,2017/5/22,计算机系统结构,13,4种常见的地址映象方式,3.3.1 全相联(P174) 全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。,全相联的地址映象方式与地址变换原理示意图(a)(b),2017/5/22,计算机系统结构,14,全相联的地址映象方式与地址变换原理示意图(c),全相联的虚实变换信息完全来自于变换表。 全相联映象使虚页调入有最大的选择范围，发生实页争用可能性最小，调入/调出操作开销也最少，有利于命中率提高。但页表占用空间和查表时间开销较大, 实现成本较高，命中时的虚实变换时间也较多。由于页表必须常驻实存，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象一般用于主存-辅存层次。,2017/5/22,计算机系统结构,15,3.3.2 直接相联(P176),直接相联是一种最强的约束关系，规定每个虚页只对应唯一实页。为便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现简单，二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位。 例已知虚页号 = 7，实页总数 = 4，用直接相联求实页号。 解：可用十进制形式求：7 mod 4 = 3； 也可用二进制形式求：由于n = 4，所以log2n = 2， 取7的二进制形式111B的最低2位，得11B，即3。 直接相联映象不需借助页表进行虚实变换，节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页选择范围太小，实页争用频率较高，常出现实存有空闲空间却不得不调出一个现有虚页以腾出实页的情况，使系统的命中率和运行效率大大下降。 这种映象方式主要用于对实存价格非常敏感的Cache-主存层次。,2017/5/22,计算机系统结构,16,直接相联的地址映象方式与地址变换原理,2017/5/22,计算机系统结构,17,例：假设在某计算机系统中Cache容量为64K字节，数据块大小是 16个字节，主存容量是4M，地址映象为直接相联方式。,（1）主存地址多少位？如何分配？（2）Cache地址多少位？如何分配？（3）目录表的格式和容量？,目录表的格式：,6 1 0,解：,容量：应与缓存块数量相同即212=4096,2017/5/22,计算机系统结构,18,2017/5/22,计算机系统结构,19,3.3.3 组相联(P178),组相联映象是全相联与直接相联的一个折中方案，性能也是二者折中。做法：先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。虚组按直接相联方式映射到实组集合，对应虚实组间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。,组相联的地址映象方式与地址变换原理(a)(b),2017/5/22,计算机系统结构,20,组相联的地址变换,由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”,2017/5/22,计算机系统结构,21,例：主存容量为1MB，缓存容量为32KB，每块为64个字节， 缓存共分128（27）组。请写出：,（1）主存与Cache的格式；（2）相关存储器的格式与容量,解：,相关存储器的容量，应与缓存的块数相同，即: 组数组内块数=1284=512,2017/5/22,计算机系统结构,22,这两方面优点互相抵触：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。 这种映象方式性价比较好，在Cache-主存层次中被普遍使用。, 组相联映象方式的优点： 块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低：每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低。另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。 组相联映象方式的缺点： 实现难度和造价要比直接映象方式高。,2017/5/22,计算机系统结构,23,3.3.4 段相联(P184),段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图(a)、(b)所示（设实段数为2）。,