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