计算机存储器的层次结构

3.1.2存储器的层次结构每级存储器的性能参数可以表示为Ti，Si，Ci。存储系统的性能可表示为：Ti<Ti+1；Si<Si+1；Ci>Ci+1。速度提高容量增加DatalocationDataidentifacationDatareplacementDataWritepolicy地址映象与变换(P174)基本术语：逻辑地址（又称为相对地址、虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。物理地址（又称为绝对地址、实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。地址变换（又叫虚实变换）指逻辑地址到物理地址的变换过程或者算法。页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。实页争用又叫实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。存储层次的管理方式(P147)根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 不同，存在3种存储层次管理方式。(1)段式管理(P148)段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。每段使用独立的逻辑地址空间，即都从0开始计算地址。段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。段式管理方法的虚实变换算法是查段表(P150)。段式虚拟存储器的地址映象段式虚拟存储器的优点如下：程序的模块性能好。对于大程序，可以划分成多个程序段，每个程序段赋予不同的名字，由多个程序员并行编写，分别编译和调试。由于各个程序段在功能上是相互独立的，因此，一个程序段的修改和增删等不会影响其他程序段，从而可以缩短程序的编制和调试时间。便于程序和数据的共享。由于程序段是按功能来划分的，如子程序段、数据段、表格段等。每个程序段有比较完整的功能，因此，被共享的可能性很大。程序的动态链接和调试比较容易。由于每个程序段都是一组有独立意义的数据块或具有完整功能的程序段，因此，在程序运行过程中，可以根据需要一次就把一个程序段或数据块都装入到主存储器中，并且在装入时才实行动态链接。便于实现信息保护。在一般情况下，一段程序是否需要保护是根据这个程序的功能来决定的。因此，只有在段表中设置一个信息保护字段，就能根据需要很方便地实现对该程序的保护。段式虚拟存储器的缺点：地址变换所花费的时间比较长。从多用户虚地址变换到主存实地址需要查两次，做两次加法运算。主存储器的利用率往往比较低。由于每个程序段的长度不同的，一个程序段通常要装在一个连续的主存空间中，程序段在主存储器中不断地调入调出，有些程序段在执行过程中还要动态增加长度，从而使得主存储器中有很多的空隙存在。当然，也可以采用一些好的算法来减少空隙的数量，或者通过定时运行回收程序来合并着这些空隙，但这无疑增加了系统的开销。对辅存（磁盘存储器）的管理比较难。磁盘存储器通常是按固定大小的块来访问的，如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要做一次地址变换。(2)页式管理(P151)。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。我们把用户文件划分得到的一个长度单位称为“虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页”。页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。页式管理方法的虚实变换算法是查页表(P152)。页式虚拟存储器的地址映象页式虚拟存储器的优点是：主存储器的利用率比较高。每个用户程序只有不到一页（平均为半页）的浪费，与段式虚拟存储器每两个程序段之间都有浪费相比要节省许多。页表相对比较简单。它需要保存的字段数比较少，一些关键字段的长度要短许多，因此，节省了页表的存储器容量。地址映象和变换的速度比较快。在把用户程序装入到主存储器的过程中，只要建立用户程序的虚页号与主存储器的实页号之间的对应关系即可不必使用整个主存的地址长度，也不必考虑页号的长度等。对辅存（磁盘存储器）的管理比较容易。因为页的大小一般取磁盘存储器物理块的大小（512字节）的整数倍。页式虚拟存储器的缺点主要有两个：程序的模块化性能不好。由于用户程序是强制按照固定大小的页来划分的，而程序段的实际长度一般是不固定的。因此，页式虚拟存储器中一页通常不能表示一个完整的程序功能。页表很长，需要占用很大的存储空间。通常，虚拟存储器中的每一页在页表中都需要占用一个存储字。(3)段页式管理(P153)。它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P154)。段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理，为了叙述简单，下面的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 还是以页式管理为模型。段页式虚拟存储器的地址映象相联目录表技术1.页表占用空间过大问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 页表必须存放在实存M1里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在M2。页表占用空间=页表行数×每行宽度其中，页表行数=虚存容量/页面大小以PC机为例，页表行数≥64G/4K=236/212=224≈1600万！按每行宽度6字节估算约需96MB。减少页表空间的思路分减少行数和减少行宽两类。2.相联目录表方法（P158）仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。3.快慢表方法（P159）4.通过地址映象减少行宽如下文所示4种常见的地址映象方式3.3.1全相联(P174)全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。全相联的地址映象方式与地址变换原理示意图(a)(b)全相联的地址映象方式与地址变换原理示意图(c)全相联的虚实变换信息完全来自于变换表。全相联映象使虚页调入有最大的选择范围，发生实页争用可能性最小，调入/调出操作开销也最少，有利于命中率提高。但页表占用空间和查表时间开销较大,实现成本较高，命中时的虚实变换时间也较多。由于页表必须常驻实存，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象一般用于主存-辅存层次。3.3.2直接相联(P176)直接相联是一种最强的约束关系，规定每个虚页只对应唯一实页。为便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现简单，二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位。例 已知虚页号=7，实页总数=4，用直接相联求实页号。解：可用十进制形式求：7mod4=3；也可用二进制形式求：由于n=4，所以log2n=2，取7的二进制形式111B的最低2位，得11B，即3。直接相联映象不需借助页表进行虚实变换，节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页选择范围太小，实页争用频率较高，常出现实存有空闲空间却不得不调出一个现有虚页以腾出实页的情况，使系统的命中率和运行效率大大下降。这种映象方式主要用于对实存价格非常敏感的Cache-主存层次。直接相联的地址映象方式与地址变换原理例：假设在某计算机系统中Cache容量为64K字节，数据块大小是16个字节，主存容量是4M，地址映象为直接相联方式。（1）主存地址多少位？如何分配？（2）Cache地址多少位？如何分配？（3）目录表的格式和容量？目录表的格式：610解：容量：应与缓存块数量相同即212=40963.3.3组相联(P178)组相联映象是全相联与直接相联的一个折中 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，性能也是二者折中。做法：先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。虚组按直接相联方式映射到实组集合，对应虚实组间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。组相联的地址映象方式与地址变换原理(a)(b)组相联的地址变换由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”例：主存容量为1MB，缓存容量为32KB，每块为64个字节，缓存共分128（27）组。请写出：（1）主存与Cache的格式；（2）相关存储器的格式与容量解：相关存储器的容量，应与缓存的块数相同，即:组数×组内块数=128×4=512这两方面优点互相抵触：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。这种映象方式性价比较好，在Cache-主存层次中被普遍使用。组相联映象方式的优点：块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低：每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低。另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。组相联映象方式的缺点：实现难度和造价要比直接映象方式高。3.3.4段相联(P184)段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图(a)、(b)所示（设实段数为2）。段相联的地址映象方式与地址变换原理(a)(b)段相联的虚实变换与组相联类似，不过通过计算来确定的部分是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为“段号查表、段内复制”。段相联方式的主要优点：段表比较简单，实现成本低。例如：容量为256KBCache，分8段，每段2048块，每块16B。在段表存储器中只需要存储8个主存地址的段号S。段相联方式的主要缺点：当发生段失效时，要把本段内已经建立的映象关系全部撤消。段相联映象方式的虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以虚段号比实段号位数多，也就意味着“多→少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。多用户虚地址格式在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从CPU发出的虚地址还需要在前面拼接上一个“当前用户号”字段，形成“多用户虚地址”，如下图所示(参见P154)。在虚实变换时，上面所说的各种查表操作之前还得先去查一个“段表基址寄存器组”或“页表基址寄存器组”的小表格(P150，P152)，确定现在该查哪一张段表或页表。这个小表格建立在CPU里，读写时间很短。思考题：P203，题113.4替换算法(P164)上面所讲地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。不命中时需要增加的操作就是首先调出一页，调出之后再调入称为“替换”。替换算法要解决的是选择调出对象的问题。替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。3.4.1几种常用的替换算法(P164)(1)随机算法RAND──在比较范围内任取一页作为淘汰页；优点：算法简单，容易实现。缺点：没有利用历史信息，没有反映程序的局部性，命中率低。(2)先进先出算法FIFO──在比较范围内选取调入最早的一页作为淘汰页；优点：比较容易实现，利用了历史信息，没有反映程序的局部性。缺点：最先调入主存的页面，很可能也是经常要使用的页面。(3)最不经常使用算法LFU──在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；优点：既充分利用了历史信息，又反映了程序的局部性缺点：实现起来非常困难。(4)最不接近使用算法LRU──在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；(5)最优替换算法OPT──在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页。优点：它把LFU算法中的“多”与“少”简化成“有”与“无”，实现起来比较容易。是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。从LFU到LRU的近似逻辑推理：近期最少使用LFU→最近一个单位时间内使用次数最少→相邻两次使用的平均间隔时间最大→上次使用时间离现在最久→最久没有使用LRU偶然偏差：使用稀疏的页面有可能恰巧刚刚用过，离现在更近。统计性能：“现在”离“上次”使用时间的平均距离，应为相邻两次使用时间距离的1/2，所以大多数情况下LRU与LFU的判断结论应该是一致的。算法模拟：实存状况图（P166图3.32）以LRU算法为例（其中*号表示被选中的淘汰页）：这是对某些替换算法的统称。如果某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集（当容量超过虚页总数时，保留页面集合相同），则小容量下的命中点到大容量情况下仍然是命中点，并且随着容量加大，还可能会有新的命中点产生。具有这一特性的一类替换算法中成为“堆栈型算法”。例如：P166图3.32中，对LRU算法，如果实页数增加到4，则t=5时为了调入虚页4就不必替换掉虚页2，而是将虚页1、2、4、5都留在实存，这时大容量分区情况下的保留页面集合S2={1，2，4，5}，同一时刻的小容量分区情况下的保留页面集合S1={1，4，5}。显然有S1 S2。P167第4～8行是堆栈型算法的数学定义。堆栈型替换算法的主要性质就是命中率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)实例：堆栈模拟图研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如P167倒数第3行的PFF法），另一方面也可推导出一些分析工具，例如“堆栈模拟法”。堆栈模拟图可以通过一次作图，描述同一地址流在各种实存分区容量下的命中情况。例3.43.5提高命中率的方法影响命中率的主要因素：(1)程序在执行过程中的页地址流分布情况。(2)所采用的页面替换算法。(3)页面大小。(4)存储器的容量(5)所采用的页面调度方法。以下，对后三个因素进行分析。1.页面大小与命中率的关系页面大小为某个值时，命中率达到最大。解释：假设At和At+1是相邻两次访问主存储器的逻辑地址，d=|At-At+1|。如果d<Sp，随着Sp的增大，At和At+1在同一页面的可能性增加，即Ｈ随着Sp的增大而提高。如果d>Sp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。Ｈ随着Sp的增大而降低。1命2S中率SH页面大小SP页面大小与主存命中率的关系当Sp比较小的时候，前一种情况是主要的，Ｈ随着Sp的增大而提高。当Sp达到某一最大值后，后一种情况成为主要的，Ｈ随Sp增大而降低。当页面大小增大时，造成的浪费也要增加；当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。2.主存容量与命中率的关系主存命中率H随着分配给该程序的主存容量S的增加而单调上升。在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。1.0命中率H主存容量S主存命中率H于贮存容量S的关系3.页面调度方式与命中率的关系请求式：当使用到的时候，再调入主存。预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。优点：可以避免在程序开始运行时，频繁发生页面失效的情况。缺点：如果调入的页面用不上，浪费了调入的时间，占用了主存资源。3.6虚拟存储器与Cache的特点(P146，P172)常用的两种存储系统:1.Cache存储系统:由Cache+主存储器构成2.虚拟存储系统:主存储器+磁盘存储器虚拟存储器与Cache的主要区别（P173页）存储系统Cache虚拟存储器要达到的目标提高（主存）速度扩大（主存）容量实现方法全部硬件软件为主，硬件为辅两级存储器的速度比3倍～10倍105倍页（块）大小1字～16字1KB～16KB等效存储容量主存储器虚拟存储器透明性对系统和应用程序员仅对应用程序员不命中时处理方式等待主存储器任务切换使用Cache的动机动机：容量大的存储器（DRAM）速度慢容量小的存储器（SRAM）速度快通过如下策略，使得平均访问时间变小：在小量、高速的存储器中完成大多数访问减少对大容量存储器的带宽要求。工作流程与虚存（VM）的区别当未命中的时候，在Cache中，用主存地址访问主存储器，从主存中读出一个字直接送入CPU，同时将被访问的信息从主存中装入到Cache里。而在VM中，必须先将虚存的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 调入到主存，再从主存送入CPU，虚存和CPU间没有直接的数据通路。在Cache存储系统中，把Cache和主存储器都划分成相同大小的块。因此，主存地址由块号B和块号W两部分组成。同样，Cache的地址也由块b和块内地址w组成。工作原理Cache的写操作1.全写法，亦称写直达法(WT法——Writethrough)：在对Cache进行写操作的同时，也对主存该内容进行写。2.写回法(WB法——Writeback)：在CPU执行写操作时，只写Cache，不写入主存；需要替换时，把修改过的块写回主存。3.写不命中：不按写分配法按写分配法按写分配法不按写分配法直接将数据写入主存，不调入缓存。数据写入主存，并将该数据调入Cache。Cache的实用举例1.Cache的分体多体存储器：分为数据体Cache与指令体Cache。原因：数据与指令不在一体可以减少多个访问源访问存储器的冲突；两个体的访问操作不完全相同，数据体有读操作和写操作，而指令体只有读操作。因此在替换时，只有数据体有写回的问题。在Cache容量相等的情况下，指令与数据分体的Cache比一体化的Cache命中率要高。PentiumⅡcache结构二级CacheL2(256/512KB)两个一级CacheL1。指令Cache：8kB只读，输入到预取缓冲器；数据Cache：8kB为整数和浮点数操作提供数据。取指/译码单元指令池派遣执行单元回收单元本章小结(1)并行存储系统原理；(2)存储层次的原理及5项性能指标；(3)存储层次的3种管理方式；(4)4种地址映象与地址变换方式；(5)5种替换算法；(7)主存-辅存层次与Cache-主存层次的特点。习题：P206，题3，题15，题19(3)(4)(6)(8)。第三章补充练习题1（堆栈模拟图应用）一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下P1=12341321P2=12342233试作2个实存分配方案，分别使2道程序满足(1)命中率相同；(2)命中次数之和最大。解：分别为2道程序作“堆栈模拟图”，其中“√”表示命中。