4 无访问冲突存储器访问数据比取指令的冲突更为严重介绍数组的无冲突访问存储器
( 一维数组（向量）的无冲突访问存储器一维数组的存储方案
0号体
1号体
2号体
3号体
体内地址0
a0
a1
a2
a3
1
a4
a5
a6
a7
2
a8
a9
a10
a11
3
…
…
…
…
按连续地址访问，没有冲突按位移量为2的变址方式访问，频带宽度降低一半，……
方法：存储体的个数取质数，且n≥向量长度。
原因：变址位移量必然与存储体个数互质例如：Burroughs公司巨型机BSP，存储体个数为17
我国研制的银河巨型计算机，存储体的个数为37
( 二维数组的无冲突访问存储器(之一)
要求：一个n×n的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。
顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突
0号体
1号体
2号体
3号体
体内地址0
a00
a01
a02
a03
1
a10
a11
a12
a13
2
a20
a21
a22
a23
3
a30
a31
a32
a33
错位存储：按行、按列访问无冲突，按对角线访问有冲突
0号体
1号体
2号体
3号体
体内地址0
a00
a01
a02
a03
1
a13
a10
a11
a12
2
a22
a23
a20
a21
3
a31
a32
a33
a30
P·Budnik和D·J·Kuck提出了一种能够实现n×n的二维数组无冲突访问的存储方案：
并行存储体的个数m≥n，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m＝22p＋1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1＝2P，d2＝1。
例如：4×4的二维数组，取并行存储体的个数m＝5，
由关系式m＝22P＋1，解得到p＝1，计算得到d1＝21＝2，d2＝1。
4×4二维数组按行、列、对角线和反对角线访问都不冲突的存储方案
0号体
1号体
2号体
3号体
4号体
体内地址0
a00
a01
a02
a03
1
a13
a10
a11
a12
2
a21
a22
a23
a20
3
a30
a31
a32
a33
n×n二维数组中的任意一个元素aij在无冲突并行存储器中的体号地址和体内地址的计算公式：
体号地址：（2P i＋j＋k） MOD m
体内地址：i
其中，0≤i，j≤n－1，k是数组的第一个元素a00所在体号地址，m是并行存储体的个数，要求m≥n且为质数；p是满足m＝22P＋1关系的任意自然数。
主要缺点：浪费存储单元在n×n二维数组的存储方案中，有（m－n）／m个存储单元浪费，
主要优点：实现简单列元素按地址顺序存储，行元素按地址取模顺序存储。
( 二维数组的无冲突访问存储器(之二)
规则：对于任意一个n×n的二维数组，如果能够找到满足n＝22P关系的任意自然数p，则这个二维数组就能够使用n个并行存储体实现按行、列、对角线和反对角线的无冲突访问。
4×4数组用4个存储体的无访问冲突存储方案
0号体
1号体
2号体
3号体
体内地址0
a00
a20
a30
a10
1
a21
a01
a11
a31
2
a32
a12
a02
a22
3
a13
a33
a23
a03
实现方法：
假设aij是4×4二维数组中的任意一个元素，其中的下标i和j都可以用两位二进制数表示，假设i和j的高位和低位分别为iH、iL、jH和jL，则aij在无冲突并行存储器中的体号地址和体内地址可以通过如下公式计算：
体号地址：2（iL ( jH）＋（iH ( iL ( jL）
体内地址：j
其中，0≤i≤3，0≤j≤3，iH、iL、jH、jL均为0或1。
当数组的维数n大于4时，可以把数组划分成多个4×4的子阵。
主要优点：没有浪费的存储单元，
主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。
3.2 虚拟存储器
1961年英国曼彻斯特大学的Kilbrn等人提出的。
到了70年代被广泛地应用于大中型计算机系统中。
目前，许多微型机也开始使用虚拟存储器。
主要内容：
3.2.1 虚拟存储器工作原理
3.2.2 地址的映象和变换方
3.3.3 加快内部地址变换速度的方法
3.3.4 页面替换算法及其实现方法
3.3.5 提高主存命中率的方法
3.2.1 虚拟存储器工作原理把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块——页，每页的大小相同。主存储器的页称为实页，虚拟存储器中的页称为虚页。
一个主存地址A由两部分组成，实页号p和页内偏移d，
一个虚地址Av由三部分组成，用户号U、虚页号P和页内偏移D，
内部地址变换：
多用户虚拟地址Av变换成主存实页号p
多用户虚拟地址中的页内偏移D直接作为主存实地址中的页内偏移d，
主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A。
用户号U
实页号P
页内偏移D
多用户虚拟地址Av的组成
实页号 p
页内偏移 d
主存地址A的组成
进行外部地址变换：
首先查外页表得到磁盘存储器的实地址，
然后再查内页表，看主存储器中是否有空页。
把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机，
把要访问数据所在的一整页都从磁盘存储器调入到主存储器。
页面替换：把主存中暂时不用的一页写回到磁盘存储器中原来的位置上
（书第148页）图3.17 图页式虚拟存储器工作原理
3.2.2 地址的映象与变换三种地址空间：虚拟地址空间，主存储器地址空间，辅存地址空间三种地址：虚拟地址、主存地址、磁盘地址地址映象：把虚拟地址空间映象到主存地址空间地址映象：在程序运行过程中，把虚拟地址变换成主存实地址因地址映象和变换方法不同，有三种虚拟存储器：
页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器
1、段式虚拟存储器地址映象方法：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。
（书第149页）图3.18 段式虚拟存储器的地址映象
段表主要包括：段的长度和起始地址。段号可以省掉。
地址变换方法：
由用户号找到基址寄存器从基址寄存器中读出段表的起始地址把起始地址与多用户虚地址中段号相加得到段表地址把段表中给出的起始地址与段内偏移D相加就能得到主存实地址。
（书第150页）图3.19 段式虚拟存储器的地址变换
段式虚拟存储器的主要优点：
(1) 程序的模块化性能好。
(2) 便于程序和数据的共享。
(3) 程序的动态链接和调度比较容易。
(4) 便于实现信息保护。
段式虚拟存储器的主要缺点：
(1) 地址变换所花费的时间比较长，做两次加法运算。
(2) 主存储器的利用率往往比较低。
(3) 对辅存（磁盘存储器）的管理比较困难。
2、页式虚拟存储器由用户号U直接找到相对应的基址寄存器从基址寄存器中读出页表起始地址把页表起始地址与多用户虚地址中虚页号相加得到页表地址，
从页表中读出主存页号p与虚地址中的页内偏移D拼接得到主存实地址
（书第152页）图3.20 页式虚拟存储器的地址映象
（书第152页）图3.21 页式虚拟存储器的地址变换
页式虚拟存储器的主要优点：
(1) 主存储器的利用率比较高。
(2) 页表相对比较简单，节省了页表的存储容量。
(3) 地址映象和变换的速度比较快。
(4) 对辅存（磁盘存储器）的管理比较容易。
页式虚拟存储器的主要缺点：
(1) 程序的模块化性能不好。
(2) 页表很长，需要占用很大的存储空间。
例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字，16MB。
3、段页式虚拟存储器用户按照程序段来编写程序，每个程序段分成几个固定大小的页。
地址映象方法：
每个程序段在段表中占一行。
在段表中给出该程序段的页表长度和页表的起始地址，
页表中给出这个程序段的每一页在主存储器中的实页号。
（书第154页）图3.22 段页式虚拟存储器的地址映象
地址变换方法：
先查段表，得到该程序段的页表起始地址和页表长度，
再查页表找到要访问的主存实页号，
最后把实页号p与页内偏移d拼接得到主存的实地址。
（书第154页）图3.23 段页式虚拟存储器的地址变换
4、外部地址变换在操作系统中，把页面失效当作一种异常故障来处理。
每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在外页表中都有对应的一个存储字。
每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。
磁盘号
拄面号
磁头号
块号
磁盘存储器的地址格式
（书第156页）图3.25 外部地址变换
3.2.3 加快内部地址变换的方法造成虚拟存储器速度降低的主要原因：
(1) 要访问主存储器必须先查段表或页表，
(2) 可能需要多级页表。
页表级数的计算公式：
其中,Nv为虚拟存储空间大小，
Np为页面的大小，
Nd为一个页表存储字的大小，
例如：虚拟存储空间大小Nv＝4GB，页的大小Np＝1KB，每个页表存储字占用4个字节。计算得到页表的级数：
页表共有256 ( 256 ( 64＝4M字，每个字存放一页（4K）的信息。
通常把1级页表驻留在主存储器中，2、3级页表只驻留一小部分在主存。
1、目录表基本思想：用一个小容量高速存储器存放页表，
方法：页表的中包括多用户虚页号、主存实页号、修改位等，
采用相联方式访问。
地址变换过程：要把多用户虚地址中U与P拼接起来，相联访问目录表。
读出主存实页号p，把p与多用户虚地址中的D拼接得到主存实地址。
如果相联访问失败，发出页面失效请求。
主要优点：与页表放在主存中相比，查表速度快。
主要缺点：可扩展性比较差。
主存储器容量增加时，目录表的造价高，速度降低。
（书第158页）图3.26 目录表法的地址变换过程
2、快慢表快表TLB(Translation Lookaside Buffer)：
小容量(几～几十个字)，高速硬件实现，采用相联方式访问慢表：当快表中查不到时，从存放在主存储器中的慢表中查找
按地址访问，用软件实现快表与慢表也构成了一个两级存储系统。
（书第159页）图3.27 采用快慢表的地址变换过程
3、散列函数目的：把相联访问变成按地址访问，从而加大快表容量散列（Hashing）函数：Ah＝H（Pv），20位左右(6～8位
（书第160页）图3.28 一种用硬件实现的散列函数
( 采用散列变换实现快表按地址访问
避免散列冲突：采用相等比较器
地址变换过程：相等比较与访问存储器同时进行
（书第161页）图3.29 采用散列变换实现快表按地址访问
( 一维数组（向量）的无冲突访问存储器一维数组的存储方案
0号体
1号体
2号体
3号体
体内地址0
a0
a1
a2
a3
1
a4
a5
a6
a7
2
a8
a9
a10
a11
3
…
…
…
…
按连续地址访问，没有冲突按位移量为2的变址方式访问，频带宽度降低一半，……
方法：存储体的个数取质数，且n≥向量长度。
原因：变址位移量必然与存储体个数互质例如：Burroughs公司巨型机BSP，存储体个数为17
我国研制的银河巨型计算机，存储体的个数为37
( 二维数组的无冲突访问存储器(之一)
要求：一个n×n的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。
顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突
0号体
1号体
2号体
3号体
体内地址0
a00
a01
a02
a03
1
a10
a11
a12
a13
2
a20
a21
a22
a23
3
a30
a31
a32
a33
错位存储：按行、按列访问无冲突，按对角线访问有冲突
0号体
1号体
2号体
3号体
体内地址0
a00
a01
a02
a03
1
a13
a10
a11
a12
2
a22
a23
a20
a21
3
a31
a32
a33
a30
P·Budnik和D·J·Kuck提出了一种能够实现n×n的二维数组无冲突访问的存储方案：
并行存储体的个数m≥n，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m＝22p＋1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1＝2P，d2＝1。
例如：4×4的二维数组，取并行存储体的个数m＝5，
由关系式m＝22P＋1，解得到p＝1，计算得到d1＝21＝2，d2＝1。
4×4二维数组按行、列、对角线和反对角线访问都不冲突的存储方案
0号体
1号体
2号体
3号体
4号体
体内地址0
a00
a01
a02
a03
1
a13
a10
a11
a12
2
a21
a22
a23
a20
3
a30
a31
a32
a33
n×n二维数组中的任意一个元素aij在无冲突并行存储器中的体号地址和体内地址的计算公式：
体号地址：（2P i＋j＋k） MOD m
体内地址：i
其中，0≤i，j≤n－1，k是数组的第一个元素a00所在体号地址，m是并行存储体的个数，要求m≥n且为质数；p是满足m＝22P＋1关系的任意自然数。
主要缺点：浪费存储单元在n×n二维数组的存储方案中，有（m－n）／m个存储单元浪费，
主要优点：实现简单列元素按地址顺序存储，行元素按地址取模顺序存储。
( 二维数组的无冲突访问存储器(之二)
规则：对于任意一个n×n的二维数组，如果能够找到满足n＝22P关系的任意自然数p，则这个二维数组就能够使用n个并行存储体实现按行、列、对角线和反对角线的无冲突访问。
4×4数组用4个存储体的无访问冲突存储方案
0号体
1号体
2号体
3号体
体内地址0
a00
a20
a30
a10
1
a21
a01
a11
a31
2
a32
a12
a02
a22
3
a13
a33
a23
a03
实现方法：
假设aij是4×4二维数组中的任意一个元素，其中的下标i和j都可以用两位二进制数表示，假设i和j的高位和低位分别为iH、iL、jH和jL，则aij在无冲突并行存储器中的体号地址和体内地址可以通过如下公式计算：
体号地址：2（iL ( jH）＋（iH ( iL ( jL）
体内地址：j
其中，0≤i≤3，0≤j≤3，iH、iL、jH、jL均为0或1。
当数组的维数n大于4时，可以把数组划分成多个4×4的子阵。
主要优点：没有浪费的存储单元，
主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。
3.2 虚拟存储器
1961年英国曼彻斯特大学的Kilbrn等人提出的。
到了70年代被广泛地应用于大中型计算机系统中。
目前，许多微型机也开始使用虚拟存储器。
主要内容：
3.2.1 虚拟存储器工作原理
3.2.2 地址的映象和变换方
3.3.3 加快内部地址变换速度的方法
3.3.4 页面替换算法及其实现方法
3.3.5 提高主存命中率的方法
3.2.1 虚拟存储器工作原理把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块——页，每页的大小相同。主存储器的页称为实页，虚拟存储器中的页称为虚页。
一个主存地址A由两部分组成，实页号p和页内偏移d，
一个虚地址Av由三部分组成，用户号U、虚页号P和页内偏移D，
内部地址变换：
多用户虚拟地址Av变换成主存实页号p
多用户虚拟地址中的页内偏移D直接作为主存实地址中的页内偏移d，
主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A。
用户号U
实页号P
页内偏移D
多用户虚拟地址Av的组成
实页号 p
页内偏移 d
主存地址A的组成
进行外部地址变换：
首先查外页表得到磁盘存储器的实地址，
然后再查内页表，看主存储器中是否有空页。
把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机，
把要访问数据所在的一整页都从磁盘存储器调入到主存储器。
页面替换：把主存中暂时不用的一页写回到磁盘存储器中原来的位置上
（书第148页）图3.17 图页式虚拟存储器工作原理
3.2.2 地址的映象与变换三种地址空间：虚拟地址空间，主存储器地址空间，辅存地址空间三种地址：虚拟地址、主存地址、磁盘地址地址映象：把虚拟地址空间映象到主存地址空间地址映象：在程序运行过程中，把虚拟地址变换成主存实地址因地址映象和变换方法不同，有三种虚拟存储器：
页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器
1、段式虚拟存储器地址映象方法：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。
（书第149页）图3.18 段式虚拟存储器的地址映象
段表主要包括：段的长度和起始地址。段号可以省掉。
地址变换方法：
由用户号找到基址寄存器从基址寄存器中读出段表的起始地址把起始地址与多用户虚地址中段号相加得到段表地址把段表中给出的起始地址与段内偏移D相加就能得到主存实地址。
（书第150页）图3.19 段式虚拟存储器的地址变换
段式虚拟存储器的主要优点：
(1) 程序的模块化性能好。
(2) 便于程序和数据的共享。
(3) 程序的动态链接和调度比较容易。
(4) 便于实现信息保护。
段式虚拟存储器的主要缺点：
(1) 地址变换所花费的时间比较长，做两次加法运算。
(2) 主存储器的利用率往往比较低。
(3) 对辅存（磁盘存储器）的管理比较困难。
2、页式虚拟存储器由用户号U直接找到相对应的基址寄存器从基址寄存器中读出页表起始地址把页表起始地址与多用户虚地址中虚页号相加得到页表地址，
从页表中读出主存页号p与虚地址中的页内偏移D拼接得到主存实地址
（书第152页）图3.20 页式虚拟存储器的地址映象
（书第152页）图3.21 页式虚拟存储器的地址变换
页式虚拟存储器的主要优点：
(1) 主存储器的利用率比较高。
(2) 页表相对比较简单，节省了页表的存储容量。
(3) 地址映象和变换的速度比较快。
(4) 对辅存（磁盘存储器）的管理比较容易。
页式虚拟存储器的主要缺点：
(1) 程序的模块化性能不好。
(2) 页表很长，需要占用很大的存储空间。
例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字，16MB。
3、段页式虚拟存储器用户按照程序段来编写程序，每个程序段分成几个固定大小的页。
地址映象方法：
每个程序段在段表中占一行。
在段表中给出该程序段的页表长度和页表的起始地址，
页表中给出这个程序段的每一页在主存储器中的实页号。
（书第154页）图3.22 段页式虚拟存储器的地址映象
地址变换方法：
先查段表，得到该程序段的页表起始地址和页表长度，
再查页表找到要访问的主存实页号，
最后把实页号p与页内偏移d拼接得到主存的实地址。
（书第154页）图3.23 段页式虚拟存储器的地址变换
4、外部地址变换在操作系统中，把页面失效当作一种异常故障来处理。
每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在外页表中都有对应的一个存储字。
每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。
磁盘号
拄面号
磁头号
块号
磁盘存储器的地址格式
（书第156页）图3.25 外部地址变换
3.2.3 加快内部地址变换的方法造成虚拟存储器速度降低的主要原因：
(1) 要访问主存储器必须先查段表或页表，
(2) 可能需要多级页表。
页表级数的计算公式：
其中,Nv为虚拟存储空间大小，
Np为页面的大小，
Nd为一个页表存储字的大小，
例如：虚拟存储空间大小Nv＝4GB，页的大小Np＝1KB，每个页表存储字占用4个字节。计算得到页表的级数：
页表共有256 ( 256 ( 64＝4M字，每个字存放一页（4K）的信息。
通常把1级页表驻留在主存储器中，2、3级页表只驻留一小部分在主存。
1、目录表基本思想：用一个小容量高速存储器存放页表，
方法：页表的中包括多用户虚页号、主存实页号、修改位等，
采用相联方式访问。
地址变换过程：要把多用户虚地址中U与P拼接起来，相联访问目录表。
读出主存实页号p，把p与多用户虚地址中的D拼接得到主存实地址。
如果相联访问失败，发出页面失效请求。
主要优点：与页表放在主存中相比，查表速度快。
主要缺点：可扩展性比较差。
主存储器容量增加时，目录表的造价高，速度降低。
（书第158页）图3.26 目录表法的地址变换过程
2、快慢表快表TLB(Translation Lookaside Buffer)：
小容量(几～几十个字)，高速硬件实现，采用相联方式访问慢表：当快表中查不到时，从存放在主存储器中的慢表中查找
按地址访问，用软件实现快表与慢表也构成了一个两级存储系统。
（书第159页）图3.27 采用快慢表的地址变换过程
3、散列函数目的：把相联访问变成按地址访问，从而加大快表容量散列（Hashing）函数：Ah＝H（Pv），20位左右(6～8位
（书第160页）图3.28 一种用硬件实现的散列函数
( 采用散列变换实现快表按地址访问
避免散列冲突：采用相等比较器
地址变换过程：相等比较与访问存储器同时进行
（书第161页）图3.29 采用散列变换实现快表按地址访问
