§ 4通道（ CH）
一,CH的基本工作原理
CH执行 CH程序的过程
CH的任务
二,CH流量计算和时空图绘制
CH的类型
CH流量计算
字节多路 CH响应处理时空图的绘制
1） 计算每个子 CH提供一个字节时间 （ 1/f）
2） 画出一个完整申请周期时空图
3） 计算字节多路 CH对每个字节响应的最长用时
子 CH
5
4
3
2
1
0 10 20 30 40 50 60 70 80 90 100 t (μ s)
等待 5μ s
第四章 存贮体系
§ 1 引言
一, 存贮体系原理
1 存贮器的参数不足
1） 容量不足的解决办法
① 直接增加主存容量 （ S）
这种办法从第一代到现在都采用, 但只有此法不够,
因此法随容量 S↑ 增加, 总价格 C总 ↑, C位 不变, 用
此法不能使 C位 ↓, 因而不可能提高性能价格比 。
通用寄存器堆
指令、数据缓冲栈
C a c h e
（静态随机存储器S R A M ）
主存储器
（动态随机存储器D R A M ）
联机外部存储器
（硬盘）
脱机外部存储器
（U 盘、磁带、光盘等）
C P U 内部
第1 层
第2 层
第3 层
第4 层
第5 层
第6 层
存
储
容
量
越
来
越
大
，
位
价
格
越
来
越
低
访
问
速
度
越
来
越
快
存储器的层次结构图
② 采用两级存贮器
利用低价格的辅存扩充存贮容量，三种信息：
活跃的信息,即当前正在使用的；
待命的信息,将要使用的；
静止的信息,已被使用而不再处理。
可将活跃的和部分待 命的信息放在主存，其余放在
辅存，以减少主存容量的要求，从而可降低 C位 。
在采用两级存贮器后, 主辅存之间的信息调出与调进
的问题 。
Ⅰ ） 由程序员考虑和安排 —— 增加了程序员的负担 。
Ⅱ ） 用辅助机构自动定位, 从而引出了虚拟存贮器 。
③ 虚拟存贮器
将高速辅存 （ 如磁盘 ） 伪装成主存访问, 信息在主存,
辅存之间的调进 （ 与调出 ） 完全由辅助机构自动完成,
象这种将主存与辅存作为有机整体的存贮系统称为虚拟
存贮器 。
2） 速度不足
① 存贮器的速度往往是整个计算机系统速度的一个瓶颈 。
② 办法之一是直接提高主存速度, 此法也在采用, 但此
法随存贮器速度的提高位价格 C位 ↑ 。
③ 在 CPU和主存之间加入高速缓存 （ cache） 。
CPU 主存cache
让 CPU直接面对与它的速度相匹配的 cache访问, 此法
也需要在 CPU与 cache之间利用辅助机构完成 cache与主存
之间的信息调进调出, cache与主存作为一个有机整体,
这也是一种存贮体系结构, 称 C-主存体系 。
2 存贮体系中的辅助机构功能
1） 地址映象功能：解决将 M2中的信息采用何种规则调
入到 M1中 （ 即调入规则问题 ） 。
CPU— M1— M2
2） 地址变换功能：根据映象规则, 如何将包括 M2在内
的大空间的地址变换为 CPU能直接访问的 M1中的地址
（ 即地址变换问题 ） 。
3） 替换算法功能：在 M1中装满信息的条件下, 采用何
种算法, 算出调出 M1的部分信息, 使 M2中的部分能调
到 M1中 （ 即替换算法问题 ） 。
3 存贮器中的有关术语
1） 存贮器：凡是能存放信息的记忆装置, 称存贮器 。
2） 存贮系统：要有两种或两以上的存贮器, 才能称存
贮系统, 如主存与辅存 。
3） 存贮体系：只有将两 （ 多 ） 种不同的存贮器作为一
个有机整体的存贮系统, 才能称为存贮体系 。
4） 存贮体系的两个分支
① 虚拟存贮器, 为扩充主存容量 。
② Cache-主存体系, 为提高访问速度 。
存储系统
存储体系 存储器
虚存 C-主
4 对存贮体系的基本要求
1） 容量 S,S2?? S1（ 有足够的扩充空间 ）
2） 存取周期 tm,tm1 ＜ tm2（ 提高访问速度 ）
3） 位价格 C位, C位 2 ?? C位 1（ 才能降低 C总,
提高性能价格比 ）
二, 存贮器中的页式管理
1 页的概念
页式管理中将虚拟存贮空间和实际存贮空间
等分成固定大小的页, 使虚拟页可装入主存
中不同的实际页面位置 。
2 页式管理的地址表示
1）虚地址（逻辑地址，程序地址）：包括 M2在内
的大空间地址。
Nv Nr
Nv：虚页号
Nr：页内地址
2） 实地址（物理地址）：为 CPU能直接访问的
M1中的地址。
nv nr
nv：实页号
nr：页内地址
3 页表
1）页表所需行数与虚页号数相等，虚页号与页表
行号对应，因此无需虚页号字段。
2）页表中每行内容可认为两个字段：实页号 nv及装
入位（ 1位）,0表示虚页未装入,1表示已装入。
4 页式管理的地址变换
1）根据 Nv去查页表中的某一行 m。
2）查该行的装入位。
3）装入位 =1时，命中。表示该虚页已装入。
① 从该行中送出 nv（实页号）。
② 再将 Nr直送 nr，
即完成 NvNr → nv nr。
4）装入位 =0时，失效，表示
该虚页未装入 M1中。
实页号 装入位
0
1
2
3
4
5
6
7
01 1
10 0
00 1
11 1
11 0
01 0
10 1
00 0
5 页式管理中的表层次结构
1） 产生页表层次的条件
当用一页放不下页表时, 就要用两页或两
个以上的页面来放页表, 此时会出现页表层
次结构 。
2） 页表层次的计算
设 虚页面数为 2N,页面容量 （ 大小 ） 2P
则 页表层次数 =?N/P?
如：某虚存空间有 220个虚页面, 页面容量
512=29个单元
则 页面层次数 =?20/9?=3
3） 计算每层表的单元数
① 底层表页的单元数与虚页面数 2n=220相
等, 即 220行 。 再计算底层页表号占多
少页面,220÷ 29=211个页面
② 中层页表单元数与底层页表页面数相等,
即 211行, 而中层又占用多少页面：
211÷ 29=22个页面
③ 上层页表单元数与中层页表的页面数相
等 22行 。
4） 画出各层页表层次结构示意图 。
上层 (22行 )
0 1 2 … 511 0 1 2 … 511 0 1 2 … 511 0 1 2 … 511
中层
(2n行 4页 )
底层
(220行 …
211页 )
0 1 211-1
总页面单元数,220+211+22
5） 设所有页面数都放在主存, 计算从查表开始
到最后实现访问所需时间为：
访存次数 *tm=（ 表层次数 +1） *tm=（ ?N/P?+1） *tm
访最后的数据信息
三, 并行主存系统
1 定义：凡在一个 存取周期 之内, 能向 CPU提供多个
字的存贮系统都可称为并行主存系统 。
2 实现方法
1） 单体多字结构
利用增加一个单元中的字数来实现, 只需增加存贮
器中的数据线而地址线可不增加, 且控制难度并未增加,
但对同时取出的多个字的利用不一定充分 。
W ?? W ??W ??W ??
W ??
μ? ?· ?? ′? ?÷
μ￥ ×? 3¤?? ′? ?÷
W ??
μ? ?· ?? ′? ?÷
?á 3? ?? ′? ?÷
L
L/4
2） 多体单字结构
利用增加独立的存贮体数来实现，每个体内的数据线
未增加，但增加了控制复杂度和地址线数。
如,4K字（每字 32位）
单体多字 —— 可用 1K单元，每单元 4字，则地址线 10
条（ 210=1K），数据线 32条 *4=128条。
多体单字 —— 每个体内数据线 32条,4个体共 128条，
但地址线要 12条（ 212=4K）。
地址寄存器2地址寄存器1地址寄存器0 地址寄存器3
存 控（主存控制部件）
M0 M2 M3M1
总 线 控 制
IOP
CPU
...,..,..,..
3） 多体多字结构
将上述 1）, 2） 两结构组合而成, 控制难度大,
但每个 tm向 CPU提供的字最多, 不过也存在对同
时取出的字利用不一定充分的问题 。
3 多体单字的编址方式 （ 设有 4个体, 每个体 1K单元 ）
1） 体内连续编址 （ 基本不用 ）
体号 首址 末址
0 0 1023
1 1024 2047
2 2048 3071
3 3072 4095
特点：编址容易，控制方便；
由于指令执行时，顺序执行的情况较多，上条指
令与下一条指令往往来自同一个体，因而在一个 tm时
间内，不能向 CPU提供 2条或 2条以上指令。
2）体内断续，体间连续（流水线技术在存贮器中的应
用）。
体号 0 1 2 3
地
址
0
4
8
┇
4092
1
5
9
┇
4093
2
6
10
┇
4094
3
7
11
┇
4095
1 某辅存共 8个页面, 每页 1024
字, 实际主存为 4096字, 采用
页表法进行地址映象, 映象表
内容如下表所示：
1） 列出会发生页面失效的全部虚
页号 。
2） 列出命中页面的全部虚页号 。
3） 以下地址计算主存实地址：
0,3728,1023,1024,2055，
7800,4096,6800。
实页号 装入位
3 1
1 1
2 0
3 0
2 1
1 0
0 1
0 0
1 解,失效的虚页号,2,3,5,7。
命中的虚页号,0,1,4,6。
查地址 Nv Nr nv 实地址 装入位 命中否
0 0 0 3 3072 1 命中
3728 3 656 3 3728 0 失效
1023 0 1023 3 4095 1 命中
1024 1 0 1 1024 1 命中
2055 2 7 2 2055 0 失效
7800 7 632 0 632 0 失效
4096 4 0 2 2048 1 命中
6800 6 656 0 656 1 命中
首址 尾址
0 1023
1024 2047
2048 3071
3072 4095
4096 5119
5120
6144
6143
7167
7168 8191
虚页
0
1
2
3
4
5
6
7
存贮器的参数不足,
容量不足 =>虚拟存贮器
速度不足 =>C-主存体系
存贮体系中的辅助机构功能,
地址映象功能
地址变换功能
替换算法功能
存贮器中的页式管理,
页式管理的地址变换
虚地址 =>实地址变换
虚地址 =>页式虚地址 =>页式实地址 =>实地址
页表层次的计算
§ 2地址映象及其变换
有四种映象规则：全相联, 直接, 组相联和段相联,
为便于介绍以主, 辅存体系为例 。
一, 全相联映象及其变换
1 含义：对辅存中的任何一个页面都可以放到主存中
的任何一个页面上的映象规则, 称全相联映象 。
2 映象规则示意图
NV辅 主 nV
0
1
??
7
0
1
2
3
??
3 地址变换
1)地址表示
2)全相联页表法 。
与前面介绍的页式管理中的地址变换过程相同 。
??
Nv Nr
nv nr
1
Dé μ? ?·
￠ù
￠ú
￠?
￠ü
êμ μ? ?·
Nv Nr
nv nr
虚地址
实地址
3） 全相联目录表法
要求用相联存贮器作目录表 （ 相联存贮器是一种
可按内容的特征字段来访问的一种存贮器 ） 。
① 目录表的行数与 主存页面数相等 （ 本例四
行 ） 。
② 目录表中每行的内容：
Ⅰ ） NV为相联比较字段；
Ⅱ ） nV为主存页号 （ 非相联比较字段 ） 。
?í 3? n v
±è ??
±è ??
±è ??
±è ??
Nv
Nv nv
?à μè
③ 地址变换过程
Ⅰ ） 将虚地址中的 NV送目录表中去进行相联比较
（ 一个 tm） 。
Ⅱ ） 当有某个比较器比较相等时, 将该行 nV送出,
同时 Nr→ nr,实现了 NvNr→n vnr的变换 （ 命中 ）,
Ⅲ ） 若设有相等的, 不命中, 等待调入 。
这种办法, 可降低表的容量, 但要求有相联存贮器,
（ 目录表的行数与主存页数相等 ） 。
4 特点：
1） 产生页面冲突的可能性极小；
2） 不能实现查表与访存同时进行, 不利于访问速
度提高 。
二, 直接映象及其变
换
１ 含义：先将辅存按
主存大小分为若干
块, 在辅存的每块
内都有与主存相同
的页面数, 辅存每
块内的页面只能调
入到与主存相同的
页面上的映象规则
称直接映象 。
２ 映象示意图
Ｎ d,块号
Nv′,块内页号
3 地址变换
1） 地址表示
2） 块表
① 块表长度与主存页面数相等
（ 本例四行 ） 。
② 块表行中的内容：块号Ｎ d。
3） 地址变换过程
① 根据 Nv′ 去查块表中的
Nv′ 行；
② 将虚地址中的块号Ｎ d与所
选块表中的Ｎ d比较；
③ 比较相同时命中, 直接将
Nv′ →n v,Nr→n r。
④ 比较不相同时, 不命中 。
0
1
M-1
??
Nd Nv' Nr
nv nr
±è ?? X
·? ?÷′?
2? μè
?é ê§D§
?÷′? μ? ?·
n
Dé ′? μ? ?·
N
4 特点
1） 可将查表与访问同时进行, 有利于访问速度的提
高 （ 命中时 ） 。
2） 产生页面冲突的可能性极大 （ 因无灵活的存放余
地 ） 。
三, 组相联映象及其变换
1 含义：先将主存分为页面数相同的若干组, 再将辅
存按主存划分为若干区, 组内采用全相联映象, 组间采
用直接映象 。
2 示意图
其中,Nd区号
q 组号
s 组内页号 —— 辅存
q′ 组号
s′ 组内页号 —— 主存
0
1
0
1
0
1
?÷′? s ' q 'Nd q s · ¨′?
0
1
0
1
0
1
0
1
0
1
0
1
0
1 ×é ?? ?± ?ó
×é ?ú è? ?à á′3 地址变换过程
1）地址表示
辅（虚） Nd q s Nr
主（实） q’ s’ nr
2） 随机存贮器表
① 表的行数与组数
相等 （ 本例 2组,
即 2行 ） 。
② 每行大字段数与
组内页面数相等
（ 本例 2个 ） 。
③ 每个大字段又分
为三个小字段 。
Nd：区号； s：组
内页号； s′, 主存
组内页号 。
④ 每个大字段还有
一个比较器 。
N d q s N r辅( 虚)
比较
N d S S ' N d S S '
比较
N d, S
N d, S
==
S'
大字段1 大字段2
≠
3）地址变换过程
① 根据虚地址中的 q去查随机存贮器表中的某一行。
② 将虚地址中的 Nd,s同时送各比较器与所选行中的
Nd,s进行比较。
③ 当有一个比较器相等时：
Ⅰ ）将 q→ q’（组间直接）。
Ⅱ ）将相等大字段中 S’送出作 S’。
Ⅲ ）再将 Nr→n r,即实现了将虚址 Nd q s Nr
→q′s′n r命中时的地址变换 。
4,特点：
即有直接映象中对号入座部分 (组间直接 ),可减少查
表范围, 缩短查表时间, 又有全相联中的灵活存放规则
(组内全相联 ),从而可降低页面冲突 。 但控制机构复杂 。
组间直接映象
Nd q s q′s′
0 0 0 0 0
0 1
组内全相联映象
四, 段相联映象简介
对主辅的划分与组相联映象相同, 但为区分两种不同
的映象规则, 将组相联中的组改为段, 段间采用全相联,
段内采用直接映象 。
0
1
0
1
0
1
?÷′? s ' q 'Nd q s · ¨′?
0
1
0
1
0
1
0
1
0
1
0
1
0
1 ?? ?? è? ?à á′
?? ?ú ?± ?ó
段间全相联
可映象
Nd q s q′ s′
0 0 0 0 0
1 0
段内直接映象
五, 四种映象规则关系
1） 在组相联映象中, 当每组只有一页时, 此时
的组相联就是直接映象 。
当把主存只分为一个组时, 此时的组相联也就
是全相联映象, 即直接映象和全相联映象是组相联
映象的两个特例 。
2） 在段相联映象中, 当每段只有一页时, 此时
的段相联映象就是全相联映象 。
当把主存只分为一个段时, 此时的段相联也就
是直接映象 。
§ 3 替换算法及其实现
一, 概述 （ 以主辅存页式管理 ）
1 含义：在主存装满页面时, 采用何种算法, 计算出
主存中的被替换页面, 以便辅存中的页面能调入到
主存, 为此而采用的算法称替换算法 。
2 对替换算法的评价
1） 要利于实现, 某种算法其命中率很高, 但它实现
不了, 因此不能采用 。
2） 要保证有一定的命中率, 某种算法很好实现, 但
命中率无保证, 因而不能采用 。
3 为保证一定的命中率, 对被替换页面的要求：
1） 以后不再使用的页面, （ 很难确定以后是否不会
使用, 除非固定页面地址流 ） 。
2） 都要使用时, 先替换最后使用的页面 。
3） 替换最久没有使用的页面 （ 可以统计出来 ） 。
4 有哪些替换算法
1） 随机替换算法 （ 利用随机函数发生器产生
一个被替换页面号 ） 。 不能反映程序的局部
性, 命中率低 。
2） FIFO替换算法：最早进入实存的页替换出
去, 出现了, 历史, 信息, 但并没能正确反
映程序的局部性 。
3 ） LRU替换算法：近期最少使用 （ Least
Recently Used）, 替换最久未被使用的页面 。
4） OPT优化替换算法：是一种理想的算法,
实现不了, 只能作为衡量其它算法优劣的标
准 。
二, 地址流, 算法, 调进替换页面变化时空图
1 第一组地址流 A,2,3,2,1,5,2,4,5,3,2,5,2
1） 几个符号
i,调入第 i页；
i,第 i页命中 (已在主存中的页面, 重新被使用称命中 )
i#：第 i页将被替换
i：在主存中的普通页面
n：主存页面数 。
2） 分别写出 FIFO,LRU,OPT随时间推移页面变化示
意图 （ 设 n=3,主存开始为空 ） 。
3） 计算命中率 H。
H=命中页数 /访问时间
时间 t, 1 2 3 4 5 6 7 8 9 10 11 12
地址流 A 替换
算法 2 3 2 1 5 2 4 5 3 2 5 2
H
F I F O
② 2
③
2
3
2#
3
①
⑤
3#
1
5
②
1#
5#
2
④
5 #
2
4
③
2#
4
3
2 #
4
3
⑤
4#
3#
5
②
3/ 12
L R U
② 2
③
2
3
2
3#
①
2#
⑤
1
2
5
1#
2
5#
④
2#
5
4
③
5
4#
3
5#
②
3#
5
2
3 #
5
2
5/ 12
O P T
② 2
③
2
3
2
3
① #
2
3#
⑤
2 #
3
5
④ #
3
5
4#
3
5
4#
3
5
②
3#
5
2
3#
5
2
3#
5
6/ 12
第二种地址流 A,1,2,3,4,1,2,5,1,2,3,4,5
分析 n对 H的影响,n=3与 4 。
时间 t, 1 2 3 4 5 6 7 8 9 10 11 12
地址流 A替换
算法
n
1 2 3 4 1 2 5 1 2 3 4 5
H
3
① 1
②
1#
2
③
④
2#
3
4
①
3#
4#
1
②
⑤
1#
2
5
1 #
2
5
1 #
2
5
③
2#
5#
3
④
5 #
3
4
3/ 12
F I F O
4
① 1
②
1
2
③
1#
2
3
④
1 #
2
3
4
1#
2
3
4
⑤
2#
3
4
5
①
3#
4
5
1
②
4#
5#
1
2
③
④
1#
2
3
4
⑤
2#
3
2 / 12
3
①
1
②
1#
2
③
④
2#
3
4
①
3#
4#
1
②
⑤
1#
2
5
1
2#
5#
1
2
③
1#
2
3
④
2#
3 #
4
⑤
2/ 12
L R U
4
① 1
②
1
2
③
1#
2
3
④
1
2#
3
4
1
2
3#
4
1
2
⑤
4#
1
2
5
4#
1
2
5
4#
1
2
5#
③
1#
2
④
3
⑤
2#
4
3
4 / 12
3
① 1
②
1
2
③ #
1
2
④ #
1
2
4#
1
2
4#
1
2
⑤ #
1
2
5#
1#
2
5
③
2#
5
3#
④
5
3#
4
5
5/ 12
O P T
4
① 1
②
1
2
③
1
2
3
④ #
1
2
3
4#
1
2
3
4#
1
2
3
⑤ #
1 #
2
3
5
1#
2
3
5
1#
2
3
5
④
2#
3
5
4
2#
3
5
6/ 12
§ 2地址映象及其变换
四种映象规则及地址变换：
全相联映象：页表、目录表
直接映象：块表
组相联和段相联：随机存贮器表
§ 3 替换算法及其实现
FIFO,LRU,OPT
上述算法在给定地址流及主存页面数下页面变化时空图
主存页面数 n的大小对命中率的影响
3 堆栈型替换算法
1） 两个符号
① Lt:某题目,随时间 t推移所 出现过的 不同页面数,
L1=1,L2=2,…,L12 =5。
② Bt(n):在 t时刻, 某算法在所分配的 n个页面中,
当前的 页面集 。
如 FIFO,B3(3)={1,2,3} B7(4)={5,2,3,4}
2) 定义：
① 当页面 n≥Lt 时, Bt(n)=Bt(n+1)
② 当页面 n＜ Lt时, Bt(n)? Bt(n+1)
凡是同时满足上述两条件的算法都可称为 堆栈型算法 。
3） 哪些替换算法属于堆栈型算法
① FIFO,不属于 ∵ B7(3) ? B7(4)
② LRU,属于
③ OPT,属于
4） 堆栈型算法的意义：
可利用堆栈技术, 真实模拟 LRU在不同 n条件下页面变
化时空图及命中率 。
① 调入的页面放入栈顶, 栈中其余页面均向栈底方向
移动一个单元 。
② 处于栈中的页面命中时, 将它从栈中抽出放在栈顶,
处于它之上的页面同时向栈底挪动一个单元 。
例：也用上次的第二组地址流模拟 n=3,4、
5,此外，用 3行分别描述命中页。
1 2 3 4 1 2 5 1 2 3 4 5
1
3
2
1
4
3
2
1
4
3
2
1
4
5
2
1
1
5
2
2
1
5
3
2
1
4
3
2
5
4
3
1 2 3 4 4 4 5 1 2
地址流 A:
栈顶 →
n=3 栈底 →
n=4 栈底 →
n=5 栈底 → 3 3 3 4 5 1
命中率
n=3 1 2 2/12
n=4 1 2 1 2 4/12
n=5 1 2 1 2 3 4 5 7/12
1 2
三, LRU算法的实现
1 堆栈法
1） 设置, 需要有一定容量的堆栈 。
2） 替换页面的条件, 处于栈底的页面将被替换 。
3） 堆栈功能要求：
① 相联比较；
② 全下移及部分下移；
③ 从中间取出一项 。
4） 用处
① 当采用存贮器堆栈时, 用于主 -辅存体系中；
② 当采用寄存器堆栈时, 用于 C-主体系中 。
2 比较对法
1） 设置, 每两个页面设一个比较对触发器, 比较对触
发器的数目 N与页面数 P的关系,N=[P*（ P-1） ]/2
如 P=3时, N=3,即有 A,B,C三个页面, 触发器
为 TAB,TAC,TBC。 (左置 0,右置 1）
2） 记录页面使用状况
0 表示 A页比 B页更久未被使用
① TAB= 1 表示 B页比 A页更久未被使用
0 表示 A页比 C页更久未被使用
② TAC= 1 表示 C页比 A页更久未被使用
0 表示 B页比 C页更久未被使用
③ TBC= 1 表示 C页比 B页更久未被使用
Q Q
T AB
Q Q
T AC
Q Q
T BC
A LRU B LRU C LRU
·? B
·? C
·? A
3） 页面替换条件
① A页替换条件 ALKU=TAB * TAC
② B页替换条件 BLKU=TAB * TBC
③ C页替换条件 CLKU=TAC * TBC
4） 页面替换电路
触发器左输入端置 0,触发器右输入端置 1
TAB表示 Q端的状态
5） 用处：电路简单, 速度快, 在页面数不多的
条件下, 替换条件形成快, 可用于 C - 主体
系中 。
§ 4 存贮体系的两个分支
一, 虚拟存贮器
1 含义,将高速辅存伪装成主存来访问的一种体系结
构, 称虚拟存贮器, 在主辅存之间的信息调进与调出
都由辅助机构自动完成 。
2 主要结构
1） 主存, 是 CPU直接访问的存贮器 。
2） 辅存：用来扩充访存空间 。
3） 地址寄存器 （ 以页式管理为例 ） 。
① 虚地址寄存器, 存放虚地址；
② 实地址寄存器, 存放实地址 。
4） 页表机构 （ 按映象规则安排 ）
① 内页表, 页面放在主存中的页表 。
② 外页表, 页面放在辅存中的页表 。
5） 替换算法机构
页面满否判别机构及 LRU替换算法机构
6） I/O通道用来实现主辅存之间的页面交换 。
3 虚拟存贮器的简单工作过程
1） 用虚地址中的 NV去查内页表, 并检查相应页表行中
装入位；
2） 当装入位 =1时, 表示该页已在主存 。
① 从该页表行中送出 nV；
② 再将 Nr→n r；即完成命中时的 NV Nr→n v nr。
3） 用变换好的 nv nr实地址访问主存；
4） 当装入位 =0时, 表示不命中 。
此时要产生失页中断, CPU也要响应此失页中断,
且可在指令执行途中响应, 若为多用户系统时还要产
生用户切换 。
5） 再用 Nv去查外页表, 并查出该页在辅存中的位置 。
6） 查主存装满页面否？
7） 当主存页面未满时 （ 主存有空页 ）, 将辅存页面经
I/O通道调入到主存的页面上 。
8） 当主存已装满时, 利用 LRU替换算法机构算出调出
主存的页面号 。
9） 再将辅存页面经 I/O通道调入到主存被替换的页面上 。
注,通常主存中的页面是辅存中某些页面的副本, 但当它
从辅存调到主存时, 若有修改, 且需保存修改, 还应先将
被替换的页面经 I/O通道调回到辅存保存, 然后再调入 。
4 性能评价
除命中率 H外, 还有存贮空间利用率 μ, μ =(Ss-Su)/Ss
其中 Ss：分配给某用户的所有存贮单元数；
Su：开销, 包括所有页表单元数及最后一页未用完
的零头, 通常用 1/2页面容量 Sp表示 。
例：某虚存空间共有 220个虚页面, 页面容量
Sp=512,若某用户占据整个虚存空间, 采用页
式管理, 全部页表均在主存, 计算存贮空间利
用率 μ 。
解：
Ss=220×512=229
Su=220+(220÷ 29)+(220÷ 29) ÷ 29+ Sp /2
=220+211+22+28
∴ μ =(Ss- Su)/ Ss
=[229-(220+211+22+28)]?229
≈ 511/512
二, Cache— 主存体系
1,与虚拟存储器相同之处
1） 都属于存储体系结构 。
2） 都有地址映象及其变换机构 。
3） 都有替换算法机构, 且都采用 LRU算法 。
4） 都要求有高的命中率 H。
2,不同之处
3,tA的计算 tA=H*tc+(1-H)*tm
tc：访问 cache的时间
tm：访问主存的时间
体系
层次地位 虚拟存贮器 Cache— 主存
层次地位 主辅存体系 Cache— 主存体系
主要目的 扩充访存空间 提高访存速度
实现方式 （辅助）软、硬件 （辅助）全硬件
存贮器连接 CPU只与主存有直接通路 CPU与两种存贮器都有通路
不命中时处理 产生失页中断，多用户时要切换用户 不产生失页中断，也不切换用户,CPU直接访问主存
评价指标 H及 μ H及 tA(等效访问时间 )
6 解,1）
主存 Nd q s Nr
q’ s’ nrCache
2）
0
1
0
1
0
1
C a c h e s ' q 'N d q s 主存
0
1
0
1
0
1
0
1
0
1
0
1
0
1 组间直接
组内全相链
0
1
2
3
4
5
6
7
主存页号
1位 1位 1位
1位 1位
3) 可放入 Cache 0组的主存块号, 0 1 4 5
可放入 Cache 1组的主存块号, 2 3 6 7
t
块流q s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 4 1 3 7 0 1 2 5 4 6 4 7 2
0 0 ① 1 1 1 1 1 1# 1 1 1 4 4 4 4 4
1 ④ 4 4 4# 0 0 0 ⑤ 5 5 5 5# 5#
1 0 ② 2 2 2# ⑦ 7 7 7# 7# 7# ⑥ 6 6 ②
1 ③ 3 3 3# ② 2 2 2# 2# ⑦ 7
失 失 失 中 失 失 失 中 失 争 争 失 中 失 争
4) 块失效,凡是不命中都属于失效 ;
块争用, 换出了不该换出的页面,
所以,即失效又争用的时刻是, t10,t11及 t15
5)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns)
李学干：
时间 t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
地址流 1 2 4 1 3 7 0 1 2 5 4 6 4 7 2
0 0 1 1 1# 1 1 1 1# 1 1 1# 4 4 4 4 4
1 4 4# 4# 4# 0 0# 0# 5 5# 5# 5# 5# 5#
1 0 2 2 2 2# 7 7 7 7# 7# 7# 6 6 6# 2
1 3 3# 3# 3# 2 2 2 2# 2# 7 7#
命中
情况 失 失 失 H 失 争 争 H 争 争 争 争 H 争 争
[例 1] 考虑一个 920个字的程序, 其访问辅存的地
址流为 20,22,208,214,146,618,370，
490,492,868,916,728。
(1)若页面大小为 200字, 主存容量为 400字,
采用 FIFO替换算法, 请按访存的各个时刻, 写
出其虚页地址流, 计算主存的命中率；
(2)若页面大小改为 100字, 再做一遍；
(3)若页面大小改为 400字，再做一遍；
[解 ] 虚页号＝ └虚地址／页面大小 ┘
(1)页面大小为 200字, 主存容量为 400字, 可知主
存页数为 2页 。 其虚页地址流为
0,0,1,1,0,3,1,2,2,4,4,3
下图给出了采用 FIFO替换算法替换时的实际
装入和替换过程 。 其中,, #”标记的是候选替换的
虚页页号, H表示命中 。
虚地址
虚页流
20 22 208 214 146 618 370 490 492 868 916 728
0 0 1 1 0 3 1 2 2 4 4 3
? 0 0# 0# 0# ③ 3 3# 3# ④ 4 4#
① 1 1 1# 1# ② 2 2# 2# ③
H=6/12=0.5
(2)页面大小为 100字, 主存容量为 400字, 可知主
存页数为 4页 。 其虚页地址流为
0,0,2,2,1,6,3,4,4,8,9,7
下图给出了采用 FIFO替换算法的时空图 。
虚地址
虚页流
20 22 208 214 146 618 370 490 492 868 916 728
H=3/12=0.25
0 0 2 2 1 6 3 4 4 8 9 7
? 0 0 0 0 0# ? 3 3 3 3# ?
? 2 2 2 2# ? 4 4 4 4#
? 1 1 1# 1# ? 8 8
? 6 6 6 6# ? 9
(3)页面大小为 400字, 主存容量为 400字, 可知主
存页数为 1页 。 其虚页地址流为
0,0,0,0,0,1,0,1,1,2,2,1
下图给出了采用 FIFO替换算法页面装入和替
换过程 。
虚地址
虚页流
20 22 208 214 146 618 370 490 492 868 916 728
H=6/12=0.5
0 0 0 0 0 1 0 1 1 2 2 1
? 0 0 0 0 ? ? ? 1 ? 2 1
由 (1),(2),(3)的结果可以看出，在分配给程序的
实存容量一定 (400字 )的条件下，页面容量 Sp过小
时，命中率 H较低；页面容量增大后，两个地址在
同页内的机会增大，使命中率 H有所上升，由于指
令之间因远距离的跳转引起命中率 H下降的因素不
起主要作用，还未出现随页面容量增大，而使命中
率 H下降的情况。如果页地址流有大量的远距离转
移，随页面容量增大，因在主存中的页面数过少，
而导致出现虚存页面被轮流替换出去的“颠簸”现
象时，命中率 H反而会下降。
[例 2] 用组相联映象的 Cache存贮器, 页的大小为 28个单
元, 主存容量是 Cache容量的 4倍 。 映象表用单体多字
按地址访问存贮器构成, 已装入内容如下表所示 。 用四
套外比较电路实现组内相联查找块号 。 各字段用四进制
编码表示 。
(1)给出四进制码表示的主存地址 3122203,问主存该
单元内容能否在 Cache中找到 。
(2)给出四进制码表示的主存地址 1210000及 2310333，
问主存该单元内容能否在 Cache中找到。若能找到，指
出相应的 Cache地址。
Nd S S’ Nd S S’ Nd S S’ Nd S S’
0 0 0 1 2 0 0 2 2 2 3 2 3
1 0 1 3 0 3 2 3 3 1 0 0 0
2 3 3 0 3 2 1 3 1 2 1 1 3
3 0 2 2 3 1 3 2 1 1 2 0 0
[分析 ] 根据题意, 主存容量是 Cache容量的 4倍, 区号 Nd
字段为 2位 。 页的大小为 28个单元, Nr字段为 8位 。 4套
外比较电路实现组内相联查找块号, 组内页号 S字段为 2
位 。 映象表的行数为组数, 所以, 表中行号 0,1,2,3，
对应于组号 q的取值, q为 2位 。 可见, 主存的二进制地
址各字段的划分和位数为：
(2位 ) (2位 ) (2位 ) (8位 )
Cache的二进制地址各字段的划分和位数为：
(2位 ) (2位 ) (8位 )
区号 组号 组内页号 页内位移
组号 组内页号 页内位移
例 2 [解 ]
(1)由主存地址中的 q＝ 1,到映象表中的第 1行里去查各个
Nd,S,在表中均未找到有 Nd＝ 3,S＝ 2 的内容, 所
以主存的该页不在 Cache中, 发生 Cache块失效, 无物
理 Cache地址 。
(2)由主存地址 (121000 )4知,q＝ 2,在映象表的第 2行中
的最右面找到 （ 命中 ） 有 Nd＝ 1,S＝ 1,S’=3
其 Cache中物理单元的地址为 q’=q=2,S’=3,nr=0000
即,2*1024+3*256+0=2048+768=2816
由主存地址 (2310333)4知,q=3,在映象表的第 3行中
的第 3部分找到有 Nd＝ 2,S＝ 1,S’=1
其 Cache中物理单元的地址为 q’=3,S’=1,nr=(0333)4
即,3*1024+1*256+(333)4=3072+256+63=3391
一,CH的基本工作原理
CH执行 CH程序的过程
CH的任务
二,CH流量计算和时空图绘制
CH的类型
CH流量计算
字节多路 CH响应处理时空图的绘制
1） 计算每个子 CH提供一个字节时间 （ 1/f）
2） 画出一个完整申请周期时空图
3） 计算字节多路 CH对每个字节响应的最长用时
子 CH
5
4
3
2
1
0 10 20 30 40 50 60 70 80 90 100 t (μ s)
等待 5μ s
第四章 存贮体系
§ 1 引言
一, 存贮体系原理
1 存贮器的参数不足
1） 容量不足的解决办法
① 直接增加主存容量 （ S）
这种办法从第一代到现在都采用, 但只有此法不够,
因此法随容量 S↑ 增加, 总价格 C总 ↑, C位 不变, 用
此法不能使 C位 ↓, 因而不可能提高性能价格比 。
通用寄存器堆
指令、数据缓冲栈
C a c h e
（静态随机存储器S R A M ）
主存储器
（动态随机存储器D R A M ）
联机外部存储器
（硬盘）
脱机外部存储器
（U 盘、磁带、光盘等）
C P U 内部
第1 层
第2 层
第3 层
第4 层
第5 层
第6 层
存
储
容
量
越
来
越
大
，
位
价
格
越
来
越
低
访
问
速
度
越
来
越
快
存储器的层次结构图
② 采用两级存贮器
利用低价格的辅存扩充存贮容量，三种信息：
活跃的信息,即当前正在使用的；
待命的信息,将要使用的；
静止的信息,已被使用而不再处理。
可将活跃的和部分待 命的信息放在主存，其余放在
辅存，以减少主存容量的要求，从而可降低 C位 。
在采用两级存贮器后, 主辅存之间的信息调出与调进
的问题 。
Ⅰ ） 由程序员考虑和安排 —— 增加了程序员的负担 。
Ⅱ ） 用辅助机构自动定位, 从而引出了虚拟存贮器 。
③ 虚拟存贮器
将高速辅存 （ 如磁盘 ） 伪装成主存访问, 信息在主存,
辅存之间的调进 （ 与调出 ） 完全由辅助机构自动完成,
象这种将主存与辅存作为有机整体的存贮系统称为虚拟
存贮器 。
2） 速度不足
① 存贮器的速度往往是整个计算机系统速度的一个瓶颈 。
② 办法之一是直接提高主存速度, 此法也在采用, 但此
法随存贮器速度的提高位价格 C位 ↑ 。
③ 在 CPU和主存之间加入高速缓存 （ cache） 。
CPU 主存cache
让 CPU直接面对与它的速度相匹配的 cache访问, 此法
也需要在 CPU与 cache之间利用辅助机构完成 cache与主存
之间的信息调进调出, cache与主存作为一个有机整体,
这也是一种存贮体系结构, 称 C-主存体系 。
2 存贮体系中的辅助机构功能
1） 地址映象功能：解决将 M2中的信息采用何种规则调
入到 M1中 （ 即调入规则问题 ） 。
CPU— M1— M2
2） 地址变换功能：根据映象规则, 如何将包括 M2在内
的大空间的地址变换为 CPU能直接访问的 M1中的地址
（ 即地址变换问题 ） 。
3） 替换算法功能：在 M1中装满信息的条件下, 采用何
种算法, 算出调出 M1的部分信息, 使 M2中的部分能调
到 M1中 （ 即替换算法问题 ） 。
3 存贮器中的有关术语
1） 存贮器：凡是能存放信息的记忆装置, 称存贮器 。
2） 存贮系统：要有两种或两以上的存贮器, 才能称存
贮系统, 如主存与辅存 。
3） 存贮体系：只有将两 （ 多 ） 种不同的存贮器作为一
个有机整体的存贮系统, 才能称为存贮体系 。
4） 存贮体系的两个分支
① 虚拟存贮器, 为扩充主存容量 。
② Cache-主存体系, 为提高访问速度 。
存储系统
存储体系 存储器
虚存 C-主
4 对存贮体系的基本要求
1） 容量 S,S2?? S1（ 有足够的扩充空间 ）
2） 存取周期 tm,tm1 ＜ tm2（ 提高访问速度 ）
3） 位价格 C位, C位 2 ?? C位 1（ 才能降低 C总,
提高性能价格比 ）
二, 存贮器中的页式管理
1 页的概念
页式管理中将虚拟存贮空间和实际存贮空间
等分成固定大小的页, 使虚拟页可装入主存
中不同的实际页面位置 。
2 页式管理的地址表示
1）虚地址（逻辑地址，程序地址）：包括 M2在内
的大空间地址。
Nv Nr
Nv：虚页号
Nr：页内地址
2） 实地址（物理地址）：为 CPU能直接访问的
M1中的地址。
nv nr
nv：实页号
nr：页内地址
3 页表
1）页表所需行数与虚页号数相等，虚页号与页表
行号对应，因此无需虚页号字段。
2）页表中每行内容可认为两个字段：实页号 nv及装
入位（ 1位）,0表示虚页未装入,1表示已装入。
4 页式管理的地址变换
1）根据 Nv去查页表中的某一行 m。
2）查该行的装入位。
3）装入位 =1时，命中。表示该虚页已装入。
① 从该行中送出 nv（实页号）。
② 再将 Nr直送 nr，
即完成 NvNr → nv nr。
4）装入位 =0时，失效，表示
该虚页未装入 M1中。
实页号 装入位
0
1
2
3
4
5
6
7
01 1
10 0
00 1
11 1
11 0
01 0
10 1
00 0
5 页式管理中的表层次结构
1） 产生页表层次的条件
当用一页放不下页表时, 就要用两页或两
个以上的页面来放页表, 此时会出现页表层
次结构 。
2） 页表层次的计算
设 虚页面数为 2N,页面容量 （ 大小 ） 2P
则 页表层次数 =?N/P?
如：某虚存空间有 220个虚页面, 页面容量
512=29个单元
则 页面层次数 =?20/9?=3
3） 计算每层表的单元数
① 底层表页的单元数与虚页面数 2n=220相
等, 即 220行 。 再计算底层页表号占多
少页面,220÷ 29=211个页面
② 中层页表单元数与底层页表页面数相等,
即 211行, 而中层又占用多少页面：
211÷ 29=22个页面
③ 上层页表单元数与中层页表的页面数相
等 22行 。
4） 画出各层页表层次结构示意图 。
上层 (22行 )
0 1 2 … 511 0 1 2 … 511 0 1 2 … 511 0 1 2 … 511
中层
(2n行 4页 )
底层
(220行 …
211页 )
0 1 211-1
总页面单元数,220+211+22
5） 设所有页面数都放在主存, 计算从查表开始
到最后实现访问所需时间为：
访存次数 *tm=（ 表层次数 +1） *tm=（ ?N/P?+1） *tm
访最后的数据信息
三, 并行主存系统
1 定义：凡在一个 存取周期 之内, 能向 CPU提供多个
字的存贮系统都可称为并行主存系统 。
2 实现方法
1） 单体多字结构
利用增加一个单元中的字数来实现, 只需增加存贮
器中的数据线而地址线可不增加, 且控制难度并未增加,
但对同时取出的多个字的利用不一定充分 。
W ?? W ??W ??W ??
W ??
μ? ?· ?? ′? ?÷
μ￥ ×? 3¤?? ′? ?÷
W ??
μ? ?· ?? ′? ?÷
?á 3? ?? ′? ?÷
L
L/4
2） 多体单字结构
利用增加独立的存贮体数来实现，每个体内的数据线
未增加，但增加了控制复杂度和地址线数。
如,4K字（每字 32位）
单体多字 —— 可用 1K单元，每单元 4字，则地址线 10
条（ 210=1K），数据线 32条 *4=128条。
多体单字 —— 每个体内数据线 32条,4个体共 128条，
但地址线要 12条（ 212=4K）。
地址寄存器2地址寄存器1地址寄存器0 地址寄存器3
存 控（主存控制部件）
M0 M2 M3M1
总 线 控 制
IOP
CPU
...,..,..,..
3） 多体多字结构
将上述 1）, 2） 两结构组合而成, 控制难度大,
但每个 tm向 CPU提供的字最多, 不过也存在对同
时取出的字利用不一定充分的问题 。
3 多体单字的编址方式 （ 设有 4个体, 每个体 1K单元 ）
1） 体内连续编址 （ 基本不用 ）
体号 首址 末址
0 0 1023
1 1024 2047
2 2048 3071
3 3072 4095
特点：编址容易，控制方便；
由于指令执行时，顺序执行的情况较多，上条指
令与下一条指令往往来自同一个体，因而在一个 tm时
间内，不能向 CPU提供 2条或 2条以上指令。
2）体内断续，体间连续（流水线技术在存贮器中的应
用）。
体号 0 1 2 3
地
址
0
4
8
┇
4092
1
5
9
┇
4093
2
6
10
┇
4094
3
7
11
┇
4095
1 某辅存共 8个页面, 每页 1024
字, 实际主存为 4096字, 采用
页表法进行地址映象, 映象表
内容如下表所示：
1） 列出会发生页面失效的全部虚
页号 。
2） 列出命中页面的全部虚页号 。
3） 以下地址计算主存实地址：
0,3728,1023,1024,2055，
7800,4096,6800。
实页号 装入位
3 1
1 1
2 0
3 0
2 1
1 0
0 1
0 0
1 解,失效的虚页号,2,3,5,7。
命中的虚页号,0,1,4,6。
查地址 Nv Nr nv 实地址 装入位 命中否
0 0 0 3 3072 1 命中
3728 3 656 3 3728 0 失效
1023 0 1023 3 4095 1 命中
1024 1 0 1 1024 1 命中
2055 2 7 2 2055 0 失效
7800 7 632 0 632 0 失效
4096 4 0 2 2048 1 命中
6800 6 656 0 656 1 命中
首址 尾址
0 1023
1024 2047
2048 3071
3072 4095
4096 5119
5120
6144
6143
7167
7168 8191
虚页
0
1
2
3
4
5
6
7
存贮器的参数不足,
容量不足 =>虚拟存贮器
速度不足 =>C-主存体系
存贮体系中的辅助机构功能,
地址映象功能
地址变换功能
替换算法功能
存贮器中的页式管理,
页式管理的地址变换
虚地址 =>实地址变换
虚地址 =>页式虚地址 =>页式实地址 =>实地址
页表层次的计算
§ 2地址映象及其变换
有四种映象规则：全相联, 直接, 组相联和段相联,
为便于介绍以主, 辅存体系为例 。
一, 全相联映象及其变换
1 含义：对辅存中的任何一个页面都可以放到主存中
的任何一个页面上的映象规则, 称全相联映象 。
2 映象规则示意图
NV辅 主 nV
0
1
??
7
0
1
2
3
??
3 地址变换
1)地址表示
2)全相联页表法 。
与前面介绍的页式管理中的地址变换过程相同 。
??
Nv Nr
nv nr
1
Dé μ? ?·
￠ù
￠ú
￠?
￠ü
êμ μ? ?·
Nv Nr
nv nr
虚地址
实地址
3） 全相联目录表法
要求用相联存贮器作目录表 （ 相联存贮器是一种
可按内容的特征字段来访问的一种存贮器 ） 。
① 目录表的行数与 主存页面数相等 （ 本例四
行 ） 。
② 目录表中每行的内容：
Ⅰ ） NV为相联比较字段；
Ⅱ ） nV为主存页号 （ 非相联比较字段 ） 。
?í 3? n v
±è ??
±è ??
±è ??
±è ??
Nv
Nv nv
?à μè
③ 地址变换过程
Ⅰ ） 将虚地址中的 NV送目录表中去进行相联比较
（ 一个 tm） 。
Ⅱ ） 当有某个比较器比较相等时, 将该行 nV送出,
同时 Nr→ nr,实现了 NvNr→n vnr的变换 （ 命中 ）,
Ⅲ ） 若设有相等的, 不命中, 等待调入 。
这种办法, 可降低表的容量, 但要求有相联存贮器,
（ 目录表的行数与主存页数相等 ） 。
4 特点：
1） 产生页面冲突的可能性极小；
2） 不能实现查表与访存同时进行, 不利于访问速
度提高 。
二, 直接映象及其变
换
１ 含义：先将辅存按
主存大小分为若干
块, 在辅存的每块
内都有与主存相同
的页面数, 辅存每
块内的页面只能调
入到与主存相同的
页面上的映象规则
称直接映象 。
２ 映象示意图
Ｎ d,块号
Nv′,块内页号
3 地址变换
1） 地址表示
2） 块表
① 块表长度与主存页面数相等
（ 本例四行 ） 。
② 块表行中的内容：块号Ｎ d。
3） 地址变换过程
① 根据 Nv′ 去查块表中的
Nv′ 行；
② 将虚地址中的块号Ｎ d与所
选块表中的Ｎ d比较；
③ 比较相同时命中, 直接将
Nv′ →n v,Nr→n r。
④ 比较不相同时, 不命中 。
0
1
M-1
??
Nd Nv' Nr
nv nr
±è ?? X
·? ?÷′?
2? μè
?é ê§D§
?÷′? μ? ?·
n
Dé ′? μ? ?·
N
4 特点
1） 可将查表与访问同时进行, 有利于访问速度的提
高 （ 命中时 ） 。
2） 产生页面冲突的可能性极大 （ 因无灵活的存放余
地 ） 。
三, 组相联映象及其变换
1 含义：先将主存分为页面数相同的若干组, 再将辅
存按主存划分为若干区, 组内采用全相联映象, 组间采
用直接映象 。
2 示意图
其中,Nd区号
q 组号
s 组内页号 —— 辅存
q′ 组号
s′ 组内页号 —— 主存
0
1
0
1
0
1
?÷′? s ' q 'Nd q s · ¨′?
0
1
0
1
0
1
0
1
0
1
0
1
0
1 ×é ?? ?± ?ó
×é ?ú è? ?à á′3 地址变换过程
1）地址表示
辅（虚） Nd q s Nr
主（实） q’ s’ nr
2） 随机存贮器表
① 表的行数与组数
相等 （ 本例 2组,
即 2行 ） 。
② 每行大字段数与
组内页面数相等
（ 本例 2个 ） 。
③ 每个大字段又分
为三个小字段 。
Nd：区号； s：组
内页号； s′, 主存
组内页号 。
④ 每个大字段还有
一个比较器 。
N d q s N r辅( 虚)
比较
N d S S ' N d S S '
比较
N d, S
N d, S
==
S'
大字段1 大字段2
≠
3）地址变换过程
① 根据虚地址中的 q去查随机存贮器表中的某一行。
② 将虚地址中的 Nd,s同时送各比较器与所选行中的
Nd,s进行比较。
③ 当有一个比较器相等时：
Ⅰ ）将 q→ q’（组间直接）。
Ⅱ ）将相等大字段中 S’送出作 S’。
Ⅲ ）再将 Nr→n r,即实现了将虚址 Nd q s Nr
→q′s′n r命中时的地址变换 。
4,特点：
即有直接映象中对号入座部分 (组间直接 ),可减少查
表范围, 缩短查表时间, 又有全相联中的灵活存放规则
(组内全相联 ),从而可降低页面冲突 。 但控制机构复杂 。
组间直接映象
Nd q s q′s′
0 0 0 0 0
0 1
组内全相联映象
四, 段相联映象简介
对主辅的划分与组相联映象相同, 但为区分两种不同
的映象规则, 将组相联中的组改为段, 段间采用全相联,
段内采用直接映象 。
0
1
0
1
0
1
?÷′? s ' q 'Nd q s · ¨′?
0
1
0
1
0
1
0
1
0
1
0
1
0
1 ?? ?? è? ?à á′
?? ?ú ?± ?ó
段间全相联
可映象
Nd q s q′ s′
0 0 0 0 0
1 0
段内直接映象
五, 四种映象规则关系
1） 在组相联映象中, 当每组只有一页时, 此时
的组相联就是直接映象 。
当把主存只分为一个组时, 此时的组相联也就
是全相联映象, 即直接映象和全相联映象是组相联
映象的两个特例 。
2） 在段相联映象中, 当每段只有一页时, 此时
的段相联映象就是全相联映象 。
当把主存只分为一个段时, 此时的段相联也就
是直接映象 。
§ 3 替换算法及其实现
一, 概述 （ 以主辅存页式管理 ）
1 含义：在主存装满页面时, 采用何种算法, 计算出
主存中的被替换页面, 以便辅存中的页面能调入到
主存, 为此而采用的算法称替换算法 。
2 对替换算法的评价
1） 要利于实现, 某种算法其命中率很高, 但它实现
不了, 因此不能采用 。
2） 要保证有一定的命中率, 某种算法很好实现, 但
命中率无保证, 因而不能采用 。
3 为保证一定的命中率, 对被替换页面的要求：
1） 以后不再使用的页面, （ 很难确定以后是否不会
使用, 除非固定页面地址流 ） 。
2） 都要使用时, 先替换最后使用的页面 。
3） 替换最久没有使用的页面 （ 可以统计出来 ） 。
4 有哪些替换算法
1） 随机替换算法 （ 利用随机函数发生器产生
一个被替换页面号 ） 。 不能反映程序的局部
性, 命中率低 。
2） FIFO替换算法：最早进入实存的页替换出
去, 出现了, 历史, 信息, 但并没能正确反
映程序的局部性 。
3 ） LRU替换算法：近期最少使用 （ Least
Recently Used）, 替换最久未被使用的页面 。
4） OPT优化替换算法：是一种理想的算法,
实现不了, 只能作为衡量其它算法优劣的标
准 。
二, 地址流, 算法, 调进替换页面变化时空图
1 第一组地址流 A,2,3,2,1,5,2,4,5,3,2,5,2
1） 几个符号
i,调入第 i页；
i,第 i页命中 (已在主存中的页面, 重新被使用称命中 )
i#：第 i页将被替换
i：在主存中的普通页面
n：主存页面数 。
2） 分别写出 FIFO,LRU,OPT随时间推移页面变化示
意图 （ 设 n=3,主存开始为空 ） 。
3） 计算命中率 H。
H=命中页数 /访问时间
时间 t, 1 2 3 4 5 6 7 8 9 10 11 12
地址流 A 替换
算法 2 3 2 1 5 2 4 5 3 2 5 2
H
F I F O
② 2
③
2
3
2#
3
①
⑤
3#
1
5
②
1#
5#
2
④
5 #
2
4
③
2#
4
3
2 #
4
3
⑤
4#
3#
5
②
3/ 12
L R U
② 2
③
2
3
2
3#
①
2#
⑤
1
2
5
1#
2
5#
④
2#
5
4
③
5
4#
3
5#
②
3#
5
2
3 #
5
2
5/ 12
O P T
② 2
③
2
3
2
3
① #
2
3#
⑤
2 #
3
5
④ #
3
5
4#
3
5
4#
3
5
②
3#
5
2
3#
5
2
3#
5
6/ 12
第二种地址流 A,1,2,3,4,1,2,5,1,2,3,4,5
分析 n对 H的影响,n=3与 4 。
时间 t, 1 2 3 4 5 6 7 8 9 10 11 12
地址流 A替换
算法
n
1 2 3 4 1 2 5 1 2 3 4 5
H
3
① 1
②
1#
2
③
④
2#
3
4
①
3#
4#
1
②
⑤
1#
2
5
1 #
2
5
1 #
2
5
③
2#
5#
3
④
5 #
3
4
3/ 12
F I F O
4
① 1
②
1
2
③
1#
2
3
④
1 #
2
3
4
1#
2
3
4
⑤
2#
3
4
5
①
3#
4
5
1
②
4#
5#
1
2
③
④
1#
2
3
4
⑤
2#
3
2 / 12
3
①
1
②
1#
2
③
④
2#
3
4
①
3#
4#
1
②
⑤
1#
2
5
1
2#
5#
1
2
③
1#
2
3
④
2#
3 #
4
⑤
2/ 12
L R U
4
① 1
②
1
2
③
1#
2
3
④
1
2#
3
4
1
2
3#
4
1
2
⑤
4#
1
2
5
4#
1
2
5
4#
1
2
5#
③
1#
2
④
3
⑤
2#
4
3
4 / 12
3
① 1
②
1
2
③ #
1
2
④ #
1
2
4#
1
2
4#
1
2
⑤ #
1
2
5#
1#
2
5
③
2#
5
3#
④
5
3#
4
5
5/ 12
O P T
4
① 1
②
1
2
③
1
2
3
④ #
1
2
3
4#
1
2
3
4#
1
2
3
⑤ #
1 #
2
3
5
1#
2
3
5
1#
2
3
5
④
2#
3
5
4
2#
3
5
6/ 12
§ 2地址映象及其变换
四种映象规则及地址变换：
全相联映象：页表、目录表
直接映象：块表
组相联和段相联：随机存贮器表
§ 3 替换算法及其实现
FIFO,LRU,OPT
上述算法在给定地址流及主存页面数下页面变化时空图
主存页面数 n的大小对命中率的影响
3 堆栈型替换算法
1） 两个符号
① Lt:某题目,随时间 t推移所 出现过的 不同页面数,
L1=1,L2=2,…,L12 =5。
② Bt(n):在 t时刻, 某算法在所分配的 n个页面中,
当前的 页面集 。
如 FIFO,B3(3)={1,2,3} B7(4)={5,2,3,4}
2) 定义：
① 当页面 n≥Lt 时, Bt(n)=Bt(n+1)
② 当页面 n＜ Lt时, Bt(n)? Bt(n+1)
凡是同时满足上述两条件的算法都可称为 堆栈型算法 。
3） 哪些替换算法属于堆栈型算法
① FIFO,不属于 ∵ B7(3) ? B7(4)
② LRU,属于
③ OPT,属于
4） 堆栈型算法的意义：
可利用堆栈技术, 真实模拟 LRU在不同 n条件下页面变
化时空图及命中率 。
① 调入的页面放入栈顶, 栈中其余页面均向栈底方向
移动一个单元 。
② 处于栈中的页面命中时, 将它从栈中抽出放在栈顶,
处于它之上的页面同时向栈底挪动一个单元 。
例：也用上次的第二组地址流模拟 n=3,4、
5,此外，用 3行分别描述命中页。
1 2 3 4 1 2 5 1 2 3 4 5
1
3
2
1
4
3
2
1
4
3
2
1
4
5
2
1
1
5
2
2
1
5
3
2
1
4
3
2
5
4
3
1 2 3 4 4 4 5 1 2
地址流 A:
栈顶 →
n=3 栈底 →
n=4 栈底 →
n=5 栈底 → 3 3 3 4 5 1
命中率
n=3 1 2 2/12
n=4 1 2 1 2 4/12
n=5 1 2 1 2 3 4 5 7/12
1 2
三, LRU算法的实现
1 堆栈法
1） 设置, 需要有一定容量的堆栈 。
2） 替换页面的条件, 处于栈底的页面将被替换 。
3） 堆栈功能要求：
① 相联比较；
② 全下移及部分下移；
③ 从中间取出一项 。
4） 用处
① 当采用存贮器堆栈时, 用于主 -辅存体系中；
② 当采用寄存器堆栈时, 用于 C-主体系中 。
2 比较对法
1） 设置, 每两个页面设一个比较对触发器, 比较对触
发器的数目 N与页面数 P的关系,N=[P*（ P-1） ]/2
如 P=3时, N=3,即有 A,B,C三个页面, 触发器
为 TAB,TAC,TBC。 (左置 0,右置 1）
2） 记录页面使用状况
0 表示 A页比 B页更久未被使用
① TAB= 1 表示 B页比 A页更久未被使用
0 表示 A页比 C页更久未被使用
② TAC= 1 表示 C页比 A页更久未被使用
0 表示 B页比 C页更久未被使用
③ TBC= 1 表示 C页比 B页更久未被使用
Q Q
T AB
Q Q
T AC
Q Q
T BC
A LRU B LRU C LRU
·? B
·? C
·? A
3） 页面替换条件
① A页替换条件 ALKU=TAB * TAC
② B页替换条件 BLKU=TAB * TBC
③ C页替换条件 CLKU=TAC * TBC
4） 页面替换电路
触发器左输入端置 0,触发器右输入端置 1
TAB表示 Q端的状态
5） 用处：电路简单, 速度快, 在页面数不多的
条件下, 替换条件形成快, 可用于 C - 主体
系中 。
§ 4 存贮体系的两个分支
一, 虚拟存贮器
1 含义,将高速辅存伪装成主存来访问的一种体系结
构, 称虚拟存贮器, 在主辅存之间的信息调进与调出
都由辅助机构自动完成 。
2 主要结构
1） 主存, 是 CPU直接访问的存贮器 。
2） 辅存：用来扩充访存空间 。
3） 地址寄存器 （ 以页式管理为例 ） 。
① 虚地址寄存器, 存放虚地址；
② 实地址寄存器, 存放实地址 。
4） 页表机构 （ 按映象规则安排 ）
① 内页表, 页面放在主存中的页表 。
② 外页表, 页面放在辅存中的页表 。
5） 替换算法机构
页面满否判别机构及 LRU替换算法机构
6） I/O通道用来实现主辅存之间的页面交换 。
3 虚拟存贮器的简单工作过程
1） 用虚地址中的 NV去查内页表, 并检查相应页表行中
装入位；
2） 当装入位 =1时, 表示该页已在主存 。
① 从该页表行中送出 nV；
② 再将 Nr→n r；即完成命中时的 NV Nr→n v nr。
3） 用变换好的 nv nr实地址访问主存；
4） 当装入位 =0时, 表示不命中 。
此时要产生失页中断, CPU也要响应此失页中断,
且可在指令执行途中响应, 若为多用户系统时还要产
生用户切换 。
5） 再用 Nv去查外页表, 并查出该页在辅存中的位置 。
6） 查主存装满页面否？
7） 当主存页面未满时 （ 主存有空页 ）, 将辅存页面经
I/O通道调入到主存的页面上 。
8） 当主存已装满时, 利用 LRU替换算法机构算出调出
主存的页面号 。
9） 再将辅存页面经 I/O通道调入到主存被替换的页面上 。
注,通常主存中的页面是辅存中某些页面的副本, 但当它
从辅存调到主存时, 若有修改, 且需保存修改, 还应先将
被替换的页面经 I/O通道调回到辅存保存, 然后再调入 。
4 性能评价
除命中率 H外, 还有存贮空间利用率 μ, μ =(Ss-Su)/Ss
其中 Ss：分配给某用户的所有存贮单元数；
Su：开销, 包括所有页表单元数及最后一页未用完
的零头, 通常用 1/2页面容量 Sp表示 。
例：某虚存空间共有 220个虚页面, 页面容量
Sp=512,若某用户占据整个虚存空间, 采用页
式管理, 全部页表均在主存, 计算存贮空间利
用率 μ 。
解：
Ss=220×512=229
Su=220+(220÷ 29)+(220÷ 29) ÷ 29+ Sp /2
=220+211+22+28
∴ μ =(Ss- Su)/ Ss
=[229-(220+211+22+28)]?229
≈ 511/512
二, Cache— 主存体系
1,与虚拟存储器相同之处
1） 都属于存储体系结构 。
2） 都有地址映象及其变换机构 。
3） 都有替换算法机构, 且都采用 LRU算法 。
4） 都要求有高的命中率 H。
2,不同之处
3,tA的计算 tA=H*tc+(1-H)*tm
tc：访问 cache的时间
tm：访问主存的时间
体系
层次地位 虚拟存贮器 Cache— 主存
层次地位 主辅存体系 Cache— 主存体系
主要目的 扩充访存空间 提高访存速度
实现方式 （辅助）软、硬件 （辅助）全硬件
存贮器连接 CPU只与主存有直接通路 CPU与两种存贮器都有通路
不命中时处理 产生失页中断，多用户时要切换用户 不产生失页中断，也不切换用户,CPU直接访问主存
评价指标 H及 μ H及 tA(等效访问时间 )
6 解,1）
主存 Nd q s Nr
q’ s’ nrCache
2）
0
1
0
1
0
1
C a c h e s ' q 'N d q s 主存
0
1
0
1
0
1
0
1
0
1
0
1
0
1 组间直接
组内全相链
0
1
2
3
4
5
6
7
主存页号
1位 1位 1位
1位 1位
3) 可放入 Cache 0组的主存块号, 0 1 4 5
可放入 Cache 1组的主存块号, 2 3 6 7
t
块流q s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 4 1 3 7 0 1 2 5 4 6 4 7 2
0 0 ① 1 1 1 1 1 1# 1 1 1 4 4 4 4 4
1 ④ 4 4 4# 0 0 0 ⑤ 5 5 5 5# 5#
1 0 ② 2 2 2# ⑦ 7 7 7# 7# 7# ⑥ 6 6 ②
1 ③ 3 3 3# ② 2 2 2# 2# ⑦ 7
失 失 失 中 失 失 失 中 失 争 争 失 中 失 争
4) 块失效,凡是不命中都属于失效 ;
块争用, 换出了不该换出的页面,
所以,即失效又争用的时刻是, t10,t11及 t15
5)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns)
李学干：
时间 t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
地址流 1 2 4 1 3 7 0 1 2 5 4 6 4 7 2
0 0 1 1 1# 1 1 1 1# 1 1 1# 4 4 4 4 4
1 4 4# 4# 4# 0 0# 0# 5 5# 5# 5# 5# 5#
1 0 2 2 2 2# 7 7 7 7# 7# 7# 6 6 6# 2
1 3 3# 3# 3# 2 2 2 2# 2# 7 7#
命中
情况 失 失 失 H 失 争 争 H 争 争 争 争 H 争 争
[例 1] 考虑一个 920个字的程序, 其访问辅存的地
址流为 20,22,208,214,146,618,370，
490,492,868,916,728。
(1)若页面大小为 200字, 主存容量为 400字,
采用 FIFO替换算法, 请按访存的各个时刻, 写
出其虚页地址流, 计算主存的命中率；
(2)若页面大小改为 100字, 再做一遍；
(3)若页面大小改为 400字，再做一遍；
[解 ] 虚页号＝ └虚地址／页面大小 ┘
(1)页面大小为 200字, 主存容量为 400字, 可知主
存页数为 2页 。 其虚页地址流为
0,0,1,1,0,3,1,2,2,4,4,3
下图给出了采用 FIFO替换算法替换时的实际
装入和替换过程 。 其中,, #”标记的是候选替换的
虚页页号, H表示命中 。
虚地址
虚页流
20 22 208 214 146 618 370 490 492 868 916 728
0 0 1 1 0 3 1 2 2 4 4 3
? 0 0# 0# 0# ③ 3 3# 3# ④ 4 4#
① 1 1 1# 1# ② 2 2# 2# ③
H=6/12=0.5
(2)页面大小为 100字, 主存容量为 400字, 可知主
存页数为 4页 。 其虚页地址流为
0,0,2,2,1,6,3,4,4,8,9,7
下图给出了采用 FIFO替换算法的时空图 。
虚地址
虚页流
20 22 208 214 146 618 370 490 492 868 916 728
H=3/12=0.25
0 0 2 2 1 6 3 4 4 8 9 7
? 0 0 0 0 0# ? 3 3 3 3# ?
? 2 2 2 2# ? 4 4 4 4#
? 1 1 1# 1# ? 8 8
? 6 6 6 6# ? 9
(3)页面大小为 400字, 主存容量为 400字, 可知主
存页数为 1页 。 其虚页地址流为
0,0,0,0,0,1,0,1,1,2,2,1
下图给出了采用 FIFO替换算法页面装入和替
换过程 。
虚地址
虚页流
20 22 208 214 146 618 370 490 492 868 916 728
H=6/12=0.5
0 0 0 0 0 1 0 1 1 2 2 1
? 0 0 0 0 ? ? ? 1 ? 2 1
由 (1),(2),(3)的结果可以看出，在分配给程序的
实存容量一定 (400字 )的条件下，页面容量 Sp过小
时，命中率 H较低；页面容量增大后，两个地址在
同页内的机会增大，使命中率 H有所上升，由于指
令之间因远距离的跳转引起命中率 H下降的因素不
起主要作用，还未出现随页面容量增大，而使命中
率 H下降的情况。如果页地址流有大量的远距离转
移，随页面容量增大，因在主存中的页面数过少，
而导致出现虚存页面被轮流替换出去的“颠簸”现
象时，命中率 H反而会下降。
[例 2] 用组相联映象的 Cache存贮器, 页的大小为 28个单
元, 主存容量是 Cache容量的 4倍 。 映象表用单体多字
按地址访问存贮器构成, 已装入内容如下表所示 。 用四
套外比较电路实现组内相联查找块号 。 各字段用四进制
编码表示 。
(1)给出四进制码表示的主存地址 3122203,问主存该
单元内容能否在 Cache中找到 。
(2)给出四进制码表示的主存地址 1210000及 2310333，
问主存该单元内容能否在 Cache中找到。若能找到，指
出相应的 Cache地址。
Nd S S’ Nd S S’ Nd S S’ Nd S S’
0 0 0 1 2 0 0 2 2 2 3 2 3
1 0 1 3 0 3 2 3 3 1 0 0 0
2 3 3 0 3 2 1 3 1 2 1 1 3
3 0 2 2 3 1 3 2 1 1 2 0 0
[分析 ] 根据题意, 主存容量是 Cache容量的 4倍, 区号 Nd
字段为 2位 。 页的大小为 28个单元, Nr字段为 8位 。 4套
外比较电路实现组内相联查找块号, 组内页号 S字段为 2
位 。 映象表的行数为组数, 所以, 表中行号 0,1,2,3，
对应于组号 q的取值, q为 2位 。 可见, 主存的二进制地
址各字段的划分和位数为：
(2位 ) (2位 ) (2位 ) (8位 )
Cache的二进制地址各字段的划分和位数为：
(2位 ) (2位 ) (8位 )
区号 组号 组内页号 页内位移
组号 组内页号 页内位移
例 2 [解 ]
(1)由主存地址中的 q＝ 1,到映象表中的第 1行里去查各个
Nd,S,在表中均未找到有 Nd＝ 3,S＝ 2 的内容, 所
以主存的该页不在 Cache中, 发生 Cache块失效, 无物
理 Cache地址 。
(2)由主存地址 (121000 )4知,q＝ 2,在映象表的第 2行中
的最右面找到 （ 命中 ） 有 Nd＝ 1,S＝ 1,S’=3
其 Cache中物理单元的地址为 q’=q=2,S’=3,nr=0000
即,2*1024+3*256+0=2048+768=2816
由主存地址 (2310333)4知,q=3,在映象表的第 3行中
的第 3部分找到有 Nd＝ 2,S＝ 1,S’=1
其 Cache中物理单元的地址为 q’=3,S’=1,nr=(0333)4
即,3*1024+1*256+(333)4=3072+256+63=3391
