第一章要点
体系结构概念
弗林分类法
计算机层次结构
Amdahl定律
CPU 性能及计算
计算机系统结构设计及发展作业 P23 1.12 1.14
第二章 存储系统冯?诺依曼机的改进：
运算器为中心 存储器为中心目的,存放计算机系统中所需要处理的程序与数据 。
主存储器,用以存放正在运行的程序与数据 。
辅助存储器,存放等待运行的程序与数据。
通用寄存器组,是存放那些最经常用到的数据。
存储系统,两个或两个以上的速度、容量、价格不同的存储器采用硬件，软件或软、硬件结合的办法联接成一个系统。
本章要点
存储层次的概念和性能参数（命中率、平均访问时间、加速比）
存储层次的三个特性（局部性、一致性、包含性）
CACHE引入目的、与虚拟存储器比较的特点及需要解决的问题。
CACHE-主存地址映象变换概念？几种主要方式（全相联、直接、组相联）
几种替换算法分类；简述 LRU替换算法
CACHE的写方法,CACHE的性能分析讨论
存储保护几种方法作业,P2-69 2.14 （ 1）（ 2）（ 3）（ 4）（ 6）（ 7）（ 8）
P2-70 2.16 ( 1 ) ( 2 )
2.1 存储系统概述
2.1.1 存储系统的形成以存储器为中心的计算机结构主 存缓指 存令 器缓读存器缓写存器
I/O
部件
… …
I/O
部件
CPU
存储容量 S,以字节数表示,单位为 B,KB,MB,GB、
TB等 。
存储器速度 T,存储器访问周期,与命中率有关 。
存储器价格 C,表示单位容量的平均价值单位为 ＄
C/bit或 ＄ C/KB。
计算机存储系统三个基本参数：
2.1.2 存储系统的层次结构第一层第二层第三层第四层第五层存储系统的层次结构速度提高容量增加通用寄存器 M1
高速缓冲存储器 M2
主存储器 M3
脱机大容量存储器 M5
辅助存储器 M4
每级存储器的性能参数可以表示为 Ti,Si,Ci。
存储系统的性能可表示为,Ti<Ti+1； Si<Si+1；
Ci>Ci+1。
2.1.3 存储系统的包含性，一致性包含性,在容量大的存储器中，一定能找到上层存储信息的副本。
b
a
A B
一致性,副本修改，以保持同一信息的一致性。
B A
M4
M3
M2
段 C 段 D
a
b
2.2 并行存储器
多个存储器并行工作，并用并行访问和交叉访问等方法；
设置各种缓冲存储器；
采用 Cache存储系统。
频带宽度：单位时间内所能访问的数据量。
解决频带平衡的三种方法：
2.2.1 多体并行访问存储器并行主存系统：一个主存周期内能读写多个字的主存系统。
数据寄存器数据总线地址总线地址寄存器 体号
W
W1 W2 W3 W4
m1 m2 m3 m4
b a
体内地址优点,简单,容易 。
缺点,访问的冲突大 。
主要冲突：
取指令冲突 （ 条件转移时 ）
读操作数冲突 （ 需要的多个操作数不一定都存放在同一个存储字中 ）
写数据冲突 （ 必须凑齐 n个数才一起写入存储器 ）
读写冲突 （ 要读出的一个字和要写入的一个字处在同一个存储字内时,无法在一个存储周期内完成 ） 。
2.2.2 多体并行交叉访问存储器模 M主存储器,分为 M个存储体的主存储器。
同时访问,采取同时启动，完全并行工作的方式；
交叉访问,分时启动，互相错开一个存储体存储周期的
1/M，交叉进行工作。
四个存储体交叉访问的时间关系
m=4 分时启动时间图主存周期主存周期启动 0体启动 1体启动 2体启动 3体一、高位交叉访问低位部分：体内地址
b=log2n
高位部分：存储体体号
a=log2m
m,体数
n：每个体的容量数据总线地址总线
W
MDR
0
0
1
2
3
…
n-1
MDR
1
n
n+1
n+2
n+3
…
2n-1
MAR0 MAR3
MDRm-1
n(m-1)
n(m-1)+1
n(m-1)+2
n(m-1)+3
…
n(m-1)
MARm-1
译码
a b
二、低位交叉访问低位交叉存储器结构低位部分：存储体体号
b=log2m
高位部分：体内地址
a=log2n
W
MDR0
0
m
2m
3m
…
(n-1)m
MDR1
1
m+1
2m+1
3m+1
…
(n-1)m+1
MAR0 MAR3
MDRm-1
m-1
2m-1
3m-1
4m-1
…
nm-1
MARm-1
译码
a b
数据总线地址总线分时访问例如,n=8 m=4多体并行低位交叉编址
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
b a
4个体并行
2个体并行
2.3 高速缓冲存储器 cache
2.3.1 高速缓冲存储器的功能、结构与工作原理
CPU与 Cache主存的关系
CPU
MMU
Cache
MS
D或 I D或 I
存储器管理部件
Cache的结构
·Cache存储体
·地址转换部件
·替换部件缓存地址主存
Cache
块号 块内地址
MS-Cache
地址变换块号 块内地址
Cache
替换部件
：
：
：
：
：
：
主存地址替换块装入块不命中数据或指令
2.3.2 地址映象与转换
地址映象 是指某一数据在主存中的地址与在缓存中的地址两者之间的关系。
全相联方式
直接相联
组相联三种地址映象：
全相联映象方式,
全相联的地址映象规则：
1)主存与缓存分成相同大小的数据块 。
2) 主存的某一数据块可以装入缓存的任意一块的空间中 。
B：每块大小
C,Cache容量
M：主存容量块 0
块 1
：
块 i
：
块 M/B-1
块 0
块 1
：
块 C/B-1
Cache 主存储器全相联地址转换优点：命中率较高,Cache的存储空间利用率高；
缺点：线路复杂，成本高，速度低。
块号 块内地址主存地址 块号 块内地址
Cache地址
Bi bi 1
主存块号 B Cache块号 b 有效位例：
假设在某个计算机系统中 Cache容量为 32K字节，数据块大小是 16个字节，主存容量是 1M，地址映象为全相联方式。
（ 1）主存地址多少位？如何分配？
（ 2） Cache地址多少位？如何分配？
（ 3）目录表的格式和容量？
（一） 直接相联方式
直接相联的地址映象规则
1,主存与缓存分成同样大小的块；
2,主存容量应是缓存容量的整数倍,将主存空间按缓存的容量分成区,主存中每一区的块数与缓存的总块数相等；
3,主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。
直接映象公式
b=A mod C/B
其中
b,Cache的块号
A：主存的块号
C/B,Cache的块数直接相联地址映象主存储器块 0
块 1
:
块 C/B-1
块 C/B
块 C/B+1
:
块 2C/B-1
:
块 M/B-C/B
块 M/B-C/B+1
:
块 M/B-1
区 0
区 1
区 M/C-1
块 0
块 1
:
块 C/B-1
cache
直接相联地址转换优点：简单；缺点：命中率低。
目录表存储器块失效 相等比较区号 Ei 块号 i 块内地址块号 i 块内地址主存地址
Cache地址相等
Ei 1
区号（按地址访问） 有效位访问 Cache
例：
假设在某个计算机系统中 Cache容量为 64K字节，数据块大小是 16个字节，主存容量是 4M，地址映象为直接相联方式。
（ 1）主存地址多少位？如何分配？
（ 2） Cache地址多少位？如何分配？
（ 3）目录表的格式和容量？
主存地址格式,区号 区内块号 块内地址
21 16 15 4 3 0
缓存地址格式,块 号 块内地址
15 4 3 0
目录表的格式,主存区号 有效位
6 1 0
解：
容量：应与缓存块数量相同即 212=4096
(三 ) 组相联映象方式组相联的映象规则
1,主存与缓存分成相同大小的块 ;
2,主存与缓存分成相同大小的组 ;
3,主存容量是缓存容量的整数倍,将主存空间按缓存的大小分成区,主存中每一区的组数与缓存的组数相同 。
4,组间直接相联；组内全相联 。
思考题：
当组相联映象的组内块数大到等于 Cache时，就变成什么映象？而当块数小到只有一块时就变成了什么映象？
组相联地址映象区 0
区 Me－ 1
组 1
组 0
组 C/B－ 1
块 0
块 B－ 1
块 B
块 2B－ 1
Cache
块 0
块 B－ 1
块 B
块 2B－ 1 组 1
组 C/B－ 1
组 0
组 C/B(Me－ 1)
组 C/BMe－ C/B+1
组 C/BMe－ 1
组相联映象的地址转换优点：速度快，命中率高；
相等不等
Cache地址区号 组号 组内块号 块内地址主存地址组号 组内块号 块内地址相联比较区号 E 组内块号 组内块号
EiBi bi
块表举例说明主存容量为 1MB,缓存容量为 32KB，每块为 64个字节，缓存共分 128组。
请写出：
（ 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
2.3.3 替换策略
随机法,(Random,RAND法 )
先进先出法 (First-In First-Out,FIFO法 )
近期最少使用法 (Least Recently Used,LRU法 )
最久没有使用法（ Least Frequently Used,LFU）
举例说明：
设有一道程序，有 1至 5共五页，执行时的页地址流
（即执行时依次用到的程序页页号）为：
2,3,2,1,5,2,4,5,3,2,5,2
若分配给该道程序的主存有 3页，分别采用 FIFO和 LRU替换算法表示这 3页的使用和替换过程。
说明：
（ 1）随机算法：用随机数确定要替换的块；
（ 2） FIFO算法：替换最早装入主存的页；
（ 3） LRU算法：依据各块使用的情况，选择最近最少使用的块替换。
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
页地址流 2 3 2 1 5 2 4 5 3 2 5 2
先进先出
FIFO
调进调进调进命中替换替换替换替换命中命中替换替换
2 2
3
2
3
2*
3
1
3*
1
5 5
1*
2
5*
2
4
2
4
5*
2*
4
3 3
4
2*
3
4*
5
3*
5
2
命中命中命中命中 3次近期最少使用 LRU 2
调进
2
3
调进
2
3
命中
2
3*
1
调进
2*
1
5
替换
5
1*
2
命中
2
5*
4
替换
2*
4
5
命中
5
4*
3
替换
3
5*
2
替换
3*
2
5
命中
5
2
3*
命中命中命中命中命中命中命中 5次注意：
LRU也不是理想的方法，它仅仅是根据过去访存的频率估计未来的访存情况，因而只是推测的方法；
块命中率与地址流、块的大小和块的数量有关，应具体问题具体分析，选择适当的算法；
存储单元替换时应注意防止出现颠簸现象，即调入一块时将另一块调出，紧接着又需要访问刚刚调出块的数据，而将该块调入时又将上一块调出，即颠簸。
练习 1：
对于一个容量为 3个块的全相联 Cache,假定访问的地址块号序列为 1,2,3,4,1,2,3,4,分别用
FIFO算法和 LRU算法,写出其队列变化情况,并得出结论 。
练习 2
对于一个全相联 Cache,假定访问的地址块号序列为 1,2,3,4,1,2,5,1,2,3,4,5,在先进先出替换方式下,分别写出分配给程序的主存页面是 3页和 4页的情况下,其队列的变化情况,并得出结论 。
结论：产生颠簸现象，说明命中率与页地址流有关。
结论,FIFO算法不是堆栈型算法，主存页数增加，命中率反而下降。
替换算法的实现
计数器方法主存访问块地址块 4 块 2 块 3 块 5
块号 计数器块号计数器块号计数器块号计数器
Cache块 0 1 10 1 11 1 11 5 00
Cache块 1 3 01 3 10 3 00 3 01
Cache块 2 4 00 4 01 4 10 4 11
Cache块 3 空 ×× 2 00 2 01 2 10
操作 起始状态 调入 命中 替换
寄存器栈法
比较对法缓存操作 初始状态 调入 2 命中块 4 替换块 1
寄存器 0 3 2 4 5
寄存器 1 4 3 2 4
寄存器 2 1 4 3 2
寄存器 3 空 1 1 3
4
2
3
1 T12
T24
T34
T13
T14
T23
2.3.5 Cache性能分析
Cache存储器的地址变换和块替换算法全由硬件实现；
一,Cache透明性分析
Cache-主存存储层次对应用程序员和系统程序员都是透明的；
Cache对处理机和主存之间的信息交往是透明的。
二,Cache的命中率
1,Cache的容量对命中率的影响
2.Cache块的大小对命中率的影响
3.地址映象方式对命中率的影响命中率 H 命中率 H
容量 S
1
块大小初始 最佳
Cache命中率 H与容量 S的关系 Cache命中率 H与块大小的关系三,Cache系统的加速比等效的访问周期为 T
mccc THTHT )1(
Cache系统的加速比 Sp则为
)1(
1
)1(
c
m
c
c
mccc
mm
p
H
T
THTHTH
T
T
T
S
命中率越高，加速比越大。当 Hc→ 1时，
c
m
p T
TS?
Tc,Cache的访问周期；
Tm：主存储器的访问周期；
Hc,Cache的命中率
Cache加速比与命中率的关系存储系统的访问效率：
c
m
cc
c
T
T
HHT
T
e
)1(
1
Sp
的期望值
Spmax=Tm/TcSp
10
2
4
6
8
命中率 H
2.3.4 Cache的写操作一、全写法，亦称写直达法 (WT法 —— Write
through),在对 Cache进行写操作的同时，也对主存该内容进行写入 。
二、写回法 (WB法 —— Write back),在 CPU执行写操作时，只写入 Cache，不写入主存；需要替换时，
把修改过的块写回主存 。
三、写不命中,
不按写分配法 按写分配法按写分配法不 按写分配法直接将数据写入主存,
不调入缓存数据写入主存,并将该数据调入 Cache
2.3.6 Cache的实用举例
一,Cache的分体多体存储器,分为数据体 Cache与指令体 Cache。
原因：
数据与指令不在一体可以减少多个访问源访问存储器的冲突 ；
两个体的访问操作不完全相同，数据体有读操作和写操作，而指令体只有读操作。因此在替换时，只有数据体有写回的问题。在 Cache容量相等的情况下，指令与数据分体的 Cache比一体化的 Cache命中率要高。
二,Cache的分级实例,Pentium PC的 Cache
112 11 4 2 0
微缓存地址组号 双字 字节
5
组内块号数据数据数据
0
1
0
1位标记 M
标记 E
标记 S
组号
0
1
127
标记 I
标记 S
标记 E
数据数据数据目录 1 路 1
20位 2位 32字节32字节路 0
20位 2位目录 0
主存地址：
2.4 虚拟存储器
2.4.1 概述虚空间,程序所能利用的空间 。
实地址,主存物理空间的编址；
虚地址,编程序时程序员所用的地址,在编译程序中由处理机生成 。
CPU
存储管理主存辅存
I或 D
I或 D
VA PA
外存地址虚拟存储器中 CPU,MS、辅存间关系虚拟存储器与高速缓冲存储器区别：
2.4.2 虚拟存储器的管理方式
1.段式管理
2.页式管理
3.段页式管理
Cache 虚拟存储器功能 提高了主存储器的速度扩大了主存储器的容量实现技术 硬件 以软件为主透明性 透明 不透明地址转换 简单 复杂、速度慢
2.4.3 虚拟存储器的工作过程一、快表二、虚存与外存地址的转换三、页式管理虚拟存储器工作过程
2.4.4 页面替换策略主要依据：
一是访问主存的命中率要高；
二是替换策略易于实现段式管理地址映象,将虚存空间分段，主存的空间按这种段来分配和管理 。
段,按程序的逻辑功能来划分，一个用户的程序 (或一个进程 )可以包含多个功能不同的程序段
·地址转换：
主存地址格式,段号 段内地址虚存地址格式,用户号 段号 段地址段式管理的主要优点：
程序模块化的性能好，各段在功能上是相互独立的；
便于程序与数据的共享；
程序的动态链接比较容易；
便于实现存储保护。
地址变换所需的时间比较长 。
主存的空间利用不充分 。
对辅存 (磁盘 )的管理比较困难 。
段式管理的主要缺点：
页式管理页,将主存空间与虚存空间按固定的大小划分成块,
每块称为一页 。
虚页,虚存中的页；
实页,实存中的页。
虚页与实页之间按全相联方式映象。
虚存地址格式,虚页号 页内地址主存地址格式,实页号 页内地址页式管理的优点：
主存储器的空间利用率比较高。
页表的管理比较简单，可以不考虑程序的长短，按固定块长分配，管理，调度。
地址映象与地址转换速度比较快。
按页的管理方式，与对辅存的地址格式是一致的，因而管理起来比较容易。
缺点：
占用很大的存储空间 。
程序的模块化性能不好 。
段页式管理段页式管理,将虚拟存储空间按段式管理，而主存空间按页式管理，存在虚空间的程序按逻辑关系分段，每一段又可分成固定大小的页。主存则只分成若干相同大小的页。
虚存地址格式,用户号 段号 段内虚页号 页内地址主存地址格式,实页号 页内地址地址转换：
需要三层表,记录相关信息,包括 段表基地址表,段表,页表 。
2.4.3 虚拟存储器的工作过程快表 TLB(translation lookaside buffer),采用一个小容量的、高速的相关存储部件，用来存放当前最经常用到的那一部分页表，
采取按内容相联方式进行访问。
快表的内容包括两部分即虚地址与实地址的对应关系。
优点,速度快 。
缺点,随着主存容量的增加,目录表的容量也必须增加 。 当目录表增大时,其速度也将随之下降,成本提高 。
替换策略与高速缓冲存储器相同基本上是相同的。
2.4.5 虚拟存储器的性能分析访问虚存的等效访问周期
21 )1( THTHT vvv
影响命中率的因素有下列几方面：
(一 ) 页面大小
(二 ) 主存容量
(三 ) 页面调度方式访问主存的时间访问主存的命中率磁盘存储器的访问速度
1
命 2S
中率 S
H
页面大小 S
页面大小与主存命中率的关系
P
1.0
命中率
H
主存容量 S
主存命中率 H于贮存容量 S的关系
2.5 存储保护
2.5.1 存储保护的方式
(一 )加界保护方式
A
B
a
a+n－ 1
b
b+m－ 1
上界上界下界下界
a
a+n－ 1
b
b+m－ 1
A程序界限 寄存器
B程序界限 寄存器主存
B程序
(二 ) 键保护方式
(三 ) 环保护方式
0 2
3
4
核心系统服务操作系统扩展应用
1
对内存的信息可以有三种访问操作，即读、写、执行，
访问方式
(1) 可读,可写,可以执行,（ 所谓执行,就是做为指令执行 ）
(2) 可读,可执行,不可写
(3) 只可读,不可写,不可执行
(4) 只可读,可写,不可执行,例如数据
(5)只能执行不可读写，例如专用程序
2.5.2 虚拟存储器与存储保护举例
（二） Pentium处理机的工作模式
1,实地址模式,MS-DOS操作系统,Windows3.X和它们的 16位程序采用实模式。
2,保护模式,段式、页式、段页式
3,虚拟 86模式,80386开始具备，一直延续至 Pentium
外部数据总线宽度为 64位,内部寄存器是 32位,外部地址总线为 36位 。
目前普遍的作法是使用 32位的地址空间,因此认为 Pentium
使用的是 32位地址总线,最大物理地址空间是 232=4GB。
（一） Pentium处理机：
(三 ) 地址转换
1,段式地址转换
Pentium段式地址转换虚拟地址
31 0 偏移段寄存器 TI RPL
15 3 2 1 0
TI：段表指示位
RPL：请求特权级物理地址
31 0
段地址 +偏移段号 T1 段寄存器
15 3 2 1 0
GDT全局描述符表LDT局部描述符表
01
(2) 页式地址转换
Pentium 4KB分页式地址转换
+
页目录 (10位 ) 页号 (10位 ) 偏移 (12位 )
物理地址
32位页目录表 页表页表基址页框基址
（ 20位）
拼接
(四 ) Pentium的存储保护应用程序
OS扩充
OS系统服务
OS内核级 0
级 1
级 2
级 3
Pentium的存储保护包括特权级保护和存储区域保护 。
体系结构概念
弗林分类法
计算机层次结构
Amdahl定律
CPU 性能及计算
计算机系统结构设计及发展作业 P23 1.12 1.14
第二章 存储系统冯?诺依曼机的改进：
运算器为中心 存储器为中心目的,存放计算机系统中所需要处理的程序与数据 。
主存储器,用以存放正在运行的程序与数据 。
辅助存储器,存放等待运行的程序与数据。
通用寄存器组,是存放那些最经常用到的数据。
存储系统,两个或两个以上的速度、容量、价格不同的存储器采用硬件，软件或软、硬件结合的办法联接成一个系统。
本章要点
存储层次的概念和性能参数（命中率、平均访问时间、加速比）
存储层次的三个特性（局部性、一致性、包含性）
CACHE引入目的、与虚拟存储器比较的特点及需要解决的问题。
CACHE-主存地址映象变换概念？几种主要方式（全相联、直接、组相联）
几种替换算法分类；简述 LRU替换算法
CACHE的写方法,CACHE的性能分析讨论
存储保护几种方法作业,P2-69 2.14 （ 1）（ 2）（ 3）（ 4）（ 6）（ 7）（ 8）
P2-70 2.16 ( 1 ) ( 2 )
2.1 存储系统概述
2.1.1 存储系统的形成以存储器为中心的计算机结构主 存缓指 存令 器缓读存器缓写存器
I/O
部件
… …
I/O
部件
CPU
存储容量 S,以字节数表示,单位为 B,KB,MB,GB、
TB等 。
存储器速度 T,存储器访问周期,与命中率有关 。
存储器价格 C,表示单位容量的平均价值单位为 ＄
C/bit或 ＄ C/KB。
计算机存储系统三个基本参数：
2.1.2 存储系统的层次结构第一层第二层第三层第四层第五层存储系统的层次结构速度提高容量增加通用寄存器 M1
高速缓冲存储器 M2
主存储器 M3
脱机大容量存储器 M5
辅助存储器 M4
每级存储器的性能参数可以表示为 Ti,Si,Ci。
存储系统的性能可表示为,Ti<Ti+1； Si<Si+1；
Ci>Ci+1。
2.1.3 存储系统的包含性，一致性包含性,在容量大的存储器中，一定能找到上层存储信息的副本。
b
a
A B
一致性,副本修改，以保持同一信息的一致性。
B A
M4
M3
M2
段 C 段 D
a
b
2.2 并行存储器
多个存储器并行工作，并用并行访问和交叉访问等方法；
设置各种缓冲存储器；
采用 Cache存储系统。
频带宽度：单位时间内所能访问的数据量。
解决频带平衡的三种方法：
2.2.1 多体并行访问存储器并行主存系统：一个主存周期内能读写多个字的主存系统。
数据寄存器数据总线地址总线地址寄存器 体号
W
W1 W2 W3 W4
m1 m2 m3 m4
b a
体内地址优点,简单,容易 。
缺点,访问的冲突大 。
主要冲突：
取指令冲突 （ 条件转移时 ）
读操作数冲突 （ 需要的多个操作数不一定都存放在同一个存储字中 ）
写数据冲突 （ 必须凑齐 n个数才一起写入存储器 ）
读写冲突 （ 要读出的一个字和要写入的一个字处在同一个存储字内时,无法在一个存储周期内完成 ） 。
2.2.2 多体并行交叉访问存储器模 M主存储器,分为 M个存储体的主存储器。
同时访问,采取同时启动，完全并行工作的方式；
交叉访问,分时启动，互相错开一个存储体存储周期的
1/M，交叉进行工作。
四个存储体交叉访问的时间关系
m=4 分时启动时间图主存周期主存周期启动 0体启动 1体启动 2体启动 3体一、高位交叉访问低位部分：体内地址
b=log2n
高位部分：存储体体号
a=log2m
m,体数
n：每个体的容量数据总线地址总线
W
MDR
0
0
1
2
3
…
n-1
MDR
1
n
n+1
n+2
n+3
…
2n-1
MAR0 MAR3
MDRm-1
n(m-1)
n(m-1)+1
n(m-1)+2
n(m-1)+3
…
n(m-1)
MARm-1
译码
a b
二、低位交叉访问低位交叉存储器结构低位部分：存储体体号
b=log2m
高位部分：体内地址
a=log2n
W
MDR0
0
m
2m
3m
…
(n-1)m
MDR1
1
m+1
2m+1
3m+1
…
(n-1)m+1
MAR0 MAR3
MDRm-1
m-1
2m-1
3m-1
4m-1
…
nm-1
MARm-1
译码
a b
数据总线地址总线分时访问例如,n=8 m=4多体并行低位交叉编址
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
b a
4个体并行
2个体并行
2.3 高速缓冲存储器 cache
2.3.1 高速缓冲存储器的功能、结构与工作原理
CPU与 Cache主存的关系
CPU
MMU
Cache
MS
D或 I D或 I
存储器管理部件
Cache的结构
·Cache存储体
·地址转换部件
·替换部件缓存地址主存
Cache
块号 块内地址
MS-Cache
地址变换块号 块内地址
Cache
替换部件
：
：
：
：
：
：
主存地址替换块装入块不命中数据或指令
2.3.2 地址映象与转换
地址映象 是指某一数据在主存中的地址与在缓存中的地址两者之间的关系。
全相联方式
直接相联
组相联三种地址映象：
全相联映象方式,
全相联的地址映象规则：
1)主存与缓存分成相同大小的数据块 。
2) 主存的某一数据块可以装入缓存的任意一块的空间中 。
B：每块大小
C,Cache容量
M：主存容量块 0
块 1
：
块 i
：
块 M/B-1
块 0
块 1
：
块 C/B-1
Cache 主存储器全相联地址转换优点：命中率较高,Cache的存储空间利用率高；
缺点：线路复杂，成本高，速度低。
块号 块内地址主存地址 块号 块内地址
Cache地址
Bi bi 1
主存块号 B Cache块号 b 有效位例：
假设在某个计算机系统中 Cache容量为 32K字节，数据块大小是 16个字节，主存容量是 1M，地址映象为全相联方式。
（ 1）主存地址多少位？如何分配？
（ 2） Cache地址多少位？如何分配？
（ 3）目录表的格式和容量？
（一） 直接相联方式
直接相联的地址映象规则
1,主存与缓存分成同样大小的块；
2,主存容量应是缓存容量的整数倍,将主存空间按缓存的容量分成区,主存中每一区的块数与缓存的总块数相等；
3,主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。
直接映象公式
b=A mod C/B
其中
b,Cache的块号
A：主存的块号
C/B,Cache的块数直接相联地址映象主存储器块 0
块 1
:
块 C/B-1
块 C/B
块 C/B+1
:
块 2C/B-1
:
块 M/B-C/B
块 M/B-C/B+1
:
块 M/B-1
区 0
区 1
区 M/C-1
块 0
块 1
:
块 C/B-1
cache
直接相联地址转换优点：简单；缺点：命中率低。
目录表存储器块失效 相等比较区号 Ei 块号 i 块内地址块号 i 块内地址主存地址
Cache地址相等
Ei 1
区号（按地址访问） 有效位访问 Cache
例：
假设在某个计算机系统中 Cache容量为 64K字节，数据块大小是 16个字节，主存容量是 4M，地址映象为直接相联方式。
（ 1）主存地址多少位？如何分配？
（ 2） Cache地址多少位？如何分配？
（ 3）目录表的格式和容量？
主存地址格式,区号 区内块号 块内地址
21 16 15 4 3 0
缓存地址格式,块 号 块内地址
15 4 3 0
目录表的格式,主存区号 有效位
6 1 0
解：
容量：应与缓存块数量相同即 212=4096
(三 ) 组相联映象方式组相联的映象规则
1,主存与缓存分成相同大小的块 ;
2,主存与缓存分成相同大小的组 ;
3,主存容量是缓存容量的整数倍,将主存空间按缓存的大小分成区,主存中每一区的组数与缓存的组数相同 。
4,组间直接相联；组内全相联 。
思考题：
当组相联映象的组内块数大到等于 Cache时，就变成什么映象？而当块数小到只有一块时就变成了什么映象？
组相联地址映象区 0
区 Me－ 1
组 1
组 0
组 C/B－ 1
块 0
块 B－ 1
块 B
块 2B－ 1
Cache
块 0
块 B－ 1
块 B
块 2B－ 1 组 1
组 C/B－ 1
组 0
组 C/B(Me－ 1)
组 C/BMe－ C/B+1
组 C/BMe－ 1
组相联映象的地址转换优点：速度快，命中率高；
相等不等
Cache地址区号 组号 组内块号 块内地址主存地址组号 组内块号 块内地址相联比较区号 E 组内块号 组内块号
EiBi bi
块表举例说明主存容量为 1MB,缓存容量为 32KB，每块为 64个字节，缓存共分 128组。
请写出：
（ 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
2.3.3 替换策略
随机法,(Random,RAND法 )
先进先出法 (First-In First-Out,FIFO法 )
近期最少使用法 (Least Recently Used,LRU法 )
最久没有使用法（ Least Frequently Used,LFU）
举例说明：
设有一道程序，有 1至 5共五页，执行时的页地址流
（即执行时依次用到的程序页页号）为：
2,3,2,1,5,2,4,5,3,2,5,2
若分配给该道程序的主存有 3页，分别采用 FIFO和 LRU替换算法表示这 3页的使用和替换过程。
说明：
（ 1）随机算法：用随机数确定要替换的块；
（ 2） FIFO算法：替换最早装入主存的页；
（ 3） LRU算法：依据各块使用的情况，选择最近最少使用的块替换。
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
页地址流 2 3 2 1 5 2 4 5 3 2 5 2
先进先出
FIFO
调进调进调进命中替换替换替换替换命中命中替换替换
2 2
3
2
3
2*
3
1
3*
1
5 5
1*
2
5*
2
4
2
4
5*
2*
4
3 3
4
2*
3
4*
5
3*
5
2
命中命中命中命中 3次近期最少使用 LRU 2
调进
2
3
调进
2
3
命中
2
3*
1
调进
2*
1
5
替换
5
1*
2
命中
2
5*
4
替换
2*
4
5
命中
5
4*
3
替换
3
5*
2
替换
3*
2
5
命中
5
2
3*
命中命中命中命中命中命中命中 5次注意：
LRU也不是理想的方法，它仅仅是根据过去访存的频率估计未来的访存情况，因而只是推测的方法；
块命中率与地址流、块的大小和块的数量有关，应具体问题具体分析，选择适当的算法；
存储单元替换时应注意防止出现颠簸现象，即调入一块时将另一块调出，紧接着又需要访问刚刚调出块的数据，而将该块调入时又将上一块调出，即颠簸。
练习 1：
对于一个容量为 3个块的全相联 Cache,假定访问的地址块号序列为 1,2,3,4,1,2,3,4,分别用
FIFO算法和 LRU算法,写出其队列变化情况,并得出结论 。
练习 2
对于一个全相联 Cache,假定访问的地址块号序列为 1,2,3,4,1,2,5,1,2,3,4,5,在先进先出替换方式下,分别写出分配给程序的主存页面是 3页和 4页的情况下,其队列的变化情况,并得出结论 。
结论：产生颠簸现象，说明命中率与页地址流有关。
结论,FIFO算法不是堆栈型算法，主存页数增加，命中率反而下降。
替换算法的实现
计数器方法主存访问块地址块 4 块 2 块 3 块 5
块号 计数器块号计数器块号计数器块号计数器
Cache块 0 1 10 1 11 1 11 5 00
Cache块 1 3 01 3 10 3 00 3 01
Cache块 2 4 00 4 01 4 10 4 11
Cache块 3 空 ×× 2 00 2 01 2 10
操作 起始状态 调入 命中 替换
寄存器栈法
比较对法缓存操作 初始状态 调入 2 命中块 4 替换块 1
寄存器 0 3 2 4 5
寄存器 1 4 3 2 4
寄存器 2 1 4 3 2
寄存器 3 空 1 1 3
4
2
3
1 T12
T24
T34
T13
T14
T23
2.3.5 Cache性能分析
Cache存储器的地址变换和块替换算法全由硬件实现；
一,Cache透明性分析
Cache-主存存储层次对应用程序员和系统程序员都是透明的；
Cache对处理机和主存之间的信息交往是透明的。
二,Cache的命中率
1,Cache的容量对命中率的影响
2.Cache块的大小对命中率的影响
3.地址映象方式对命中率的影响命中率 H 命中率 H
容量 S
1
块大小初始 最佳
Cache命中率 H与容量 S的关系 Cache命中率 H与块大小的关系三,Cache系统的加速比等效的访问周期为 T
mccc THTHT )1(
Cache系统的加速比 Sp则为
)1(
1
)1(
c
m
c
c
mccc
mm
p
H
T
THTHTH
T
T
T
S
命中率越高，加速比越大。当 Hc→ 1时，
c
m
p T
TS?
Tc,Cache的访问周期；
Tm：主存储器的访问周期；
Hc,Cache的命中率
Cache加速比与命中率的关系存储系统的访问效率：
c
m
cc
c
T
T
HHT
T
e
)1(
1
Sp
的期望值
Spmax=Tm/TcSp
10
2
4
6
8
命中率 H
2.3.4 Cache的写操作一、全写法，亦称写直达法 (WT法 —— Write
through),在对 Cache进行写操作的同时，也对主存该内容进行写入 。
二、写回法 (WB法 —— Write back),在 CPU执行写操作时，只写入 Cache，不写入主存；需要替换时，
把修改过的块写回主存 。
三、写不命中,
不按写分配法 按写分配法按写分配法不 按写分配法直接将数据写入主存,
不调入缓存数据写入主存,并将该数据调入 Cache
2.3.6 Cache的实用举例
一,Cache的分体多体存储器,分为数据体 Cache与指令体 Cache。
原因：
数据与指令不在一体可以减少多个访问源访问存储器的冲突 ；
两个体的访问操作不完全相同，数据体有读操作和写操作，而指令体只有读操作。因此在替换时，只有数据体有写回的问题。在 Cache容量相等的情况下，指令与数据分体的 Cache比一体化的 Cache命中率要高。
二,Cache的分级实例,Pentium PC的 Cache
112 11 4 2 0
微缓存地址组号 双字 字节
5
组内块号数据数据数据
0
1
0
1位标记 M
标记 E
标记 S
组号
0
1
127
标记 I
标记 S
标记 E
数据数据数据目录 1 路 1
20位 2位 32字节32字节路 0
20位 2位目录 0
主存地址：
2.4 虚拟存储器
2.4.1 概述虚空间,程序所能利用的空间 。
实地址,主存物理空间的编址；
虚地址,编程序时程序员所用的地址,在编译程序中由处理机生成 。
CPU
存储管理主存辅存
I或 D
I或 D
VA PA
外存地址虚拟存储器中 CPU,MS、辅存间关系虚拟存储器与高速缓冲存储器区别：
2.4.2 虚拟存储器的管理方式
1.段式管理
2.页式管理
3.段页式管理
Cache 虚拟存储器功能 提高了主存储器的速度扩大了主存储器的容量实现技术 硬件 以软件为主透明性 透明 不透明地址转换 简单 复杂、速度慢
2.4.3 虚拟存储器的工作过程一、快表二、虚存与外存地址的转换三、页式管理虚拟存储器工作过程
2.4.4 页面替换策略主要依据：
一是访问主存的命中率要高；
二是替换策略易于实现段式管理地址映象,将虚存空间分段，主存的空间按这种段来分配和管理 。
段,按程序的逻辑功能来划分，一个用户的程序 (或一个进程 )可以包含多个功能不同的程序段
·地址转换：
主存地址格式,段号 段内地址虚存地址格式,用户号 段号 段地址段式管理的主要优点：
程序模块化的性能好，各段在功能上是相互独立的；
便于程序与数据的共享；
程序的动态链接比较容易；
便于实现存储保护。
地址变换所需的时间比较长 。
主存的空间利用不充分 。
对辅存 (磁盘 )的管理比较困难 。
段式管理的主要缺点：
页式管理页,将主存空间与虚存空间按固定的大小划分成块,
每块称为一页 。
虚页,虚存中的页；
实页,实存中的页。
虚页与实页之间按全相联方式映象。
虚存地址格式,虚页号 页内地址主存地址格式,实页号 页内地址页式管理的优点：
主存储器的空间利用率比较高。
页表的管理比较简单，可以不考虑程序的长短，按固定块长分配，管理，调度。
地址映象与地址转换速度比较快。
按页的管理方式，与对辅存的地址格式是一致的，因而管理起来比较容易。
缺点：
占用很大的存储空间 。
程序的模块化性能不好 。
段页式管理段页式管理,将虚拟存储空间按段式管理，而主存空间按页式管理，存在虚空间的程序按逻辑关系分段，每一段又可分成固定大小的页。主存则只分成若干相同大小的页。
虚存地址格式,用户号 段号 段内虚页号 页内地址主存地址格式,实页号 页内地址地址转换：
需要三层表,记录相关信息,包括 段表基地址表,段表,页表 。
2.4.3 虚拟存储器的工作过程快表 TLB(translation lookaside buffer),采用一个小容量的、高速的相关存储部件，用来存放当前最经常用到的那一部分页表，
采取按内容相联方式进行访问。
快表的内容包括两部分即虚地址与实地址的对应关系。
优点,速度快 。
缺点,随着主存容量的增加,目录表的容量也必须增加 。 当目录表增大时,其速度也将随之下降,成本提高 。
替换策略与高速缓冲存储器相同基本上是相同的。
2.4.5 虚拟存储器的性能分析访问虚存的等效访问周期
21 )1( THTHT vvv
影响命中率的因素有下列几方面：
(一 ) 页面大小
(二 ) 主存容量
(三 ) 页面调度方式访问主存的时间访问主存的命中率磁盘存储器的访问速度
1
命 2S
中率 S
H
页面大小 S
页面大小与主存命中率的关系
P
1.0
命中率
H
主存容量 S
主存命中率 H于贮存容量 S的关系
2.5 存储保护
2.5.1 存储保护的方式
(一 )加界保护方式
A
B
a
a+n－ 1
b
b+m－ 1
上界上界下界下界
a
a+n－ 1
b
b+m－ 1
A程序界限 寄存器
B程序界限 寄存器主存
B程序
(二 ) 键保护方式
(三 ) 环保护方式
0 2
3
4
核心系统服务操作系统扩展应用
1
对内存的信息可以有三种访问操作，即读、写、执行，
访问方式
(1) 可读,可写,可以执行,（ 所谓执行,就是做为指令执行 ）
(2) 可读,可执行,不可写
(3) 只可读,不可写,不可执行
(4) 只可读,可写,不可执行,例如数据
(5)只能执行不可读写，例如专用程序
2.5.2 虚拟存储器与存储保护举例
（二） Pentium处理机的工作模式
1,实地址模式,MS-DOS操作系统,Windows3.X和它们的 16位程序采用实模式。
2,保护模式,段式、页式、段页式
3,虚拟 86模式,80386开始具备，一直延续至 Pentium
外部数据总线宽度为 64位,内部寄存器是 32位,外部地址总线为 36位 。
目前普遍的作法是使用 32位的地址空间,因此认为 Pentium
使用的是 32位地址总线,最大物理地址空间是 232=4GB。
（一） Pentium处理机：
(三 ) 地址转换
1,段式地址转换
Pentium段式地址转换虚拟地址
31 0 偏移段寄存器 TI RPL
15 3 2 1 0
TI：段表指示位
RPL：请求特权级物理地址
31 0
段地址 +偏移段号 T1 段寄存器
15 3 2 1 0
GDT全局描述符表LDT局部描述符表
01
(2) 页式地址转换
Pentium 4KB分页式地址转换
+
页目录 (10位 ) 页号 (10位 ) 偏移 (12位 )
物理地址
32位页目录表 页表页表基址页框基址
（ 20位）
拼接
(四 ) Pentium的存储保护应用程序
OS扩充
OS系统服务
OS内核级 0
级 1
级 2
级 3
Pentium的存储保护包括特权级保护和存储区域保护 。
