第三章存储系统

第三章存储系统一存储器与存储系统1.存储器存储器：计算机核心部件。存储器性能指标：容量、速度、价格存储器容量Sm Sm=W·l·mW:单体存储器的字长l:单体存储器的字数M:并行工作的存储体的个数存储器速度（存取时间TA，访问周期Tm，频带宽度Bm）频带宽度Bm:存储器被访问时，可以提供的数据传送速率，单位：KB/S或者MB/S。单体存储器Bm=W/Tm（理想情况）m个存储器并行工作时，Bm=W·m/Tm（理想情况）存储器价格Cm单位容量的价钱，单位¥/b对存储器要求：“容量大、速度快、价格低”怎样达到要求？引入并行和重叠技术，构成并行主存系统，如单体多字存储器、多体交叉存储器。改善存储器系统结构，发展存储体系（或称存储系统）。2.存储系统存储体系（存储系统、存储层次）：由多种不同的存储器构成由硬件、软件或者硬件+软件相结合完成程序定位，使之成为一个整体。CPUM1M2Mn存储系统Ci>Ci+1Ti<Ti+1Si<Si+1C≈CnT≈T1S≈Sn3.局部性原理绝大多数程序访问的指令和数据都是相对簇聚的。局部性包括：时间局部性：最近、未来用到的信息很可能就是现在正在使用的信息。这主要由程序的循环造成，即循环中的语句要被重复执行。空间局部性：最近、未来用到的信息很可能与现在正在使用的信息在程序空间上是相邻或相近的。这主要由于指令是顺序执行的，以及数据一般是以向量、阵列、表格等形式簇聚所致。存储系统构成和管理采用如下方式：Mi级一般只需存放Mi+1级中近期使用过的块和页（根据时间局部性）。在Mi+1级取所要访问的字送Mi级时，一并把该字所在的块或页整个取出来（根据空间局部性），以增大CPU在访问Mi级时的命中率。4.存储系统性能参数容量S平均位价格C访问周期T（存取周期、存储周期、存取时间）容量S≈S2存储系统的编址要求：尽可能大的地址空间，而且可随机访问。存储系统的编址空间实现：以M2地址空间作为存储系统编址空间，如Cache存储系统。另外设计一个虚拟编址空间，如虚拟存储系统。M1（S1，T1，C1）M2（S2，T2，C2）C1>C2T1<T2S1<S2平均位价格C当S1《S2时，C≈C2访问周期T命中率H在M1中访问到的概率。N1：M1访问次数N2：M2访问次数等效访问周期T

T＝HT1＋(1－H)T2当命中率H→1时，T→T1访问效率e：这是一个相对值，便于不同系统之间的比较。提高存储系统速度条件：提高命中率H两个存储器的速度不要相差太大访问效率e受H和r的影响（参见右图）：Cache预取技术对命中率的提高作用

这里所说的“预取”技术，并不是根据对程序执行的未来趋势进行猜测以提前调入数据，而仅仅是在发生不命中情况时把调入1个数据字改为调入1个数据块的策略。根据程序的局部性原理，在当前使用数据周围的其它数据未来被使用的几率大于远处数据，所以该数据块中被提前调入的邻近数据很可能成为未来的命中点，从而提高命中率。采用这种预取技术后新的命中率为：其中：H──原命中率（即按照不命中时取入1字的策略）

H’──新命中率（即按照不命中时取入1块的策略）

n──每块数据平均被访问次数。

按照定义，原不命中率，新不命中率，并且有。由于预取使得每块数据中的不命中次数由n次降低到1次，所以有。此式可改写为，整理得。H’的推导：加速比

Cache-主存层次的主要作用是提高访问速度，系统的等效速度应高于主存（即M2）的原有速度，两个速度之比称为加速比。

例：有一个109字节的程序被装入右图所示的M3准备运行。假定指令字长=1字节，程序中无转移指令和内存读/写指令。

(1)按图(a)求T和e增加中间层对e的影响(2)按图(b)推导三层体系的T公式(3)按图(b)求T和e(4)比较(1)(3)结果，有何结论？103B109B103B109BM1M3M2M1M3T1=1usTB3=100usTB2=10us106B(a)(b)并行存储器

并行存储器技术可以提高主存系统的整体等效速度，实际应用中，常将它与存储层次技术组合使用，可以互为补充，获得很高的性能。并行存储器技术的基本思想是用多个独立的存储部件组成主存系统，让它们并行工作，在一个存储周期内可以访问到多个数据，从而实现较高的存取流量。并行存储器包括多种类型，我们仅介绍提高访问速度效果最显著的低位交叉访问这一种。低位交叉访问并行存储器的结构

它由n个存储体组成（一般n为2的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（最低的log2n位）作为体选译码信号，而剩下的高位字段则是体内地址。如图所示（设n=4）。主存地址与结构参数的换算其中：n──存储体个数，A──主存地址，

j──体内地址，k──体序号（k=0，1，2，…，n-1）例3.1

已知n=4，问主存地址13是在几号体的几号单元？解：由于n=4，体选译码信号使用主存地址的最低log2n=2位，所以地址13（其二进制为1101B）对应的体号k=1（即01B）、体内地址j=3（即11B），也就是说，地址13位于1号体的3号单元（参看前一页插图）。 根据上式，所有k值（即体号）相同的地址之间均相差n的整倍数，称之为“模n同余”。低位交叉访问并行存储器的加速机理

我们衡量存储器件速度的常用指标是存储周期Tm，它是同一存储单元连续两次启动的最小时间间隔，数值越小表明存储器件速度越快。传统存储系统只有一套地址译码器和数据缓冲器，所以各单元必须串行工作，也就是说每个Tm周期内至多只能完成一次访问。由多个存储体构成的并行存储器中，各个存储体都有独立的地址译码器和数据缓冲器，它们可以并行工作，使得一个Tm周期内可完成多次访问，相当于加速了多倍。最好情况下一个Tm周期内可完成n次访问。当前Tm周期中只要发现有一个新的访问地址与前面地址属于同一个存储体，该地址及其后面的地址就会被阻塞（称为访存冲突）,留到下一个Tm周期访问。机器地址序列常常具有顺序性，按照低位交叉的规律分配地址可使相继出现的地址落在相同存储体的概率降到最低（参见上图）。考虑到地址总线与数据总线的拥挤问题，一个Tm周期里发送的多个访问请求最好彼此错开Tm/n时间，如P140图3.11所示，否则实现的复杂度会增加。计算平均加速倍数1.只考虑取指地址序列（假设地址顺序递增，直至出现一条转移指令）：

其中g是指令序列中出现转移指令的概率。此公式在右图中用绿线表示。2.只考虑取数地址序列（假设地址完全随机）此公式在右图中用红线表示。Kg=010.0g=0.24.463.682.00g=0.51.00g=10110n例题：P203，题5地址映象与变换基本术语：逻辑地址（相对地址、虚地址）：程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。物理地址（又称为绝对地址、实地址）：任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。地址映象：虚页集合与实页集合的对应规则，或者说是约束关系。地址变换（虚实变换）：逻辑地址到物理地址的变换过程或者算法。页失效：当前被访问存储级中没有所需的信息，也就是不命中现象。实页争用（实页冲突）：虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。4种常见的地址映象方式1、全相联全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。这种关系可用如下示意图表示。

全相联的虚实变换信息完全来自于变换表，查表过程如下图所示。全相联映象方式特点：全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入/调出的操作开销也最少，有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。由于页表必须常驻在实存中，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象方式一般用于主存-辅存层次。直接相联

直接相联是一种最强的约束关系，它规定每个虚页只对应唯一的实页。为了便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现起来非常简单，因为在二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位，如下页示意图所示。直接相联的地址映象方式与地址变换原理例3.3已知虚页号=7，实页总数=4，用直接相联求实页号。解：可用十进制形式求：7mod4=3；也可用二进制形式求：由于n=4，所以log2n=2，取7的二进制形式111B的最低2位，得11B，即3。直接相联映象方式特点：直接相联映象方式不需要借助页表来进行虚实变换，显然大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留）。由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率大大下降。这种映象方式主要用于一些对实存价格非常敏感的Cache-主存层次。组相联

组相联映象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。具体做法是先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合，对应的虚实组之间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。组相联的地址映象方式与地址变换原理

由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”。如下图所示。组相联的地址映象方式与地址变换原理组相联映象方式特点：采用组相联映象方式时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低；另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。这种映象方式性价比较好，在Cache-主存层次中被普遍使用。段相联

段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图所示（设实段数为2）。段相联的地址映象方式与地址变换原理

段相联的虚实变换与组相联类似，不过可以通过计算来确定的部分不是在段外，而是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为“段号查表、段内复制”。如如下页示意图所示。段相联的地址映象方式与地址变换原理段相联映象方式特点：段相联映象方式的虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以虚段号比实段号位数多，也就意味着“多→少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。多用户虚地址格式

在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从CPU发出的虚地址还需要在前面拼接上一个“当前用户号”字段，形成“多用户虚地址”，如下图所示。在虚实变换时，上面所说的各种查表操作之前还得先去查一个“段表基址寄存器组”或“页表基址寄存器组”的小表格，确定现在该查哪一张段表或页表。这个小表格建立在CPU里，读写时间很短。替换算法

上面所讲的地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。不命中时需要增加的操作就是首先调出一页，调出之后再调入称为“替换”。替换算法要解决的是选择调出对象的问题。替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。几种常用的替换算法随机算法RAND──在比较范围内任取一页作为淘汰页；先进先出算法FIFO──在比较范围内选取调入最早的一页作为淘汰页；最不经常使用算法LFU──在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；最不接近使用算法LRU──在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；最优替换算法OPT──在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页。实例：实存状况图例如LRU算法（其中*号表示被选中的淘汰页）：

这是对某些替换算法的统称。如果某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集（当容量超过虚页总数时，保留页面集合相同），则小容量下的命中点到大容量情况下仍然是命中点，并且随着容量加大，还可能会有新的命中点产生。具有这一特性的一类替换算法中成为“堆栈型算法”。例如，图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不能保证当实页数增加时，原来的命中点不丢。堆栈型替换算法实例：堆栈模拟图

研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如P167倒数第3行的PFF法），另一方面也可推导出一些分析工具，例如“堆栈模拟法”。堆栈模拟图可以通过一次作图，描述同一地址流在各种实存分区容量下的命中情况。实例：堆栈模拟图……tTm#0#1#2#n-10n2n3n1n+1N-12n-12n+13n+13n-14n-1体0体1体n-1低位交叉存储器提高速度原理无访问冲突存储器（P143）低位交叉存储器（N=4）

如何访问地址连续递增+1，那么，一个存储周期并行访问N个（N=4）不同存储体，速度提高N倍。但这只是理想情况，如果访问地址不是连续递增+1，那么就有可能出现一个存储周期内连续访问同一个存储体情况，就会发生“访问冲突”。

如何要求在一个存储周期内按地址每次递增+2（步距）访问4个单元，假如从0单元开始，即访问0、2、4、6单元，那么，由于0与4、2与6分别在同一个存储体，所以出现在一个存储周期内需要两次访问同一存储体的情况，既发生访问冲突。04260426812101415379131115体0体1体2体3怎样才能不发生冲突？

N=4时，地址每次递增+3（步距），访问情况如下：0426812101415379131115体0体1体2体3

没有发生访问冲突！为什么当N=4，步距是2会发生冲突，而步距是1或者3却不会发生冲突？原来2（步距）是N（=4）的约数，而1（步距）和3（步距）却与N（=4）互质。是不是地址递增步距与存储体数互质就能保证不会发生访问冲突？052710151217163811161318体0体1体2体3491419体4步距=2时的访问情况：当N=5时052710151217163811161318体0体1体2体3491419体4步距=3时的访问情况：052710151217163811161318体0体1体2体3491419体4步距=4时的访问情况：052710151217163811161318体0体1体2体3491419体4

所以，在低位交叉并行存储器中，为了避免发生访问冲突，存储体数N一般取质数，如我国银河计算机中N取31。更为复杂的情况：

将二维数组a00 a01 a02 a03a10 a11 a12 a13a20 a21 a22 a23a30 a31 a32 a33存放在如下低位交叉并行存储器（N=4）中，0426812101415379131115体0体1体2体3

使得数组按行、列、对角线、反对角线等方式访问时，不会发生存储体访问冲突？行列对角线反对角线

对于n×n的二维数组，假如并行存储体个数m≥n，并且取质数。设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m=22p+1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1=2p，d2=1

假设aij是数组任意元素，则该元素在并行存储体中体号和体内地址分别为：存储体号：(2pi+j+k)MODm体内地址：i例如：当n=4、m=5时，m=5=22p+1=22×1+1，p=1，所以，d1=2p=2，数组元素存放情况如下：a00a13a02a10a2115a23a31a016a03a11a22a3013a32体0体1体2体34a12a20a33体4a00a13a02a10a2115a23a31a016a03a11a22a3013a32体0体1体2体34a12a20a33体4a00a13a02a10a2115a23a31a016a03a11a22a3013a32体0体1体2体34a12a20a33体4a00a13a02a10a2115a23a31a016a03a11a22a3013a32体0体1体2体34a12a20a33体4按反对角线按对角线按列：0列1列2列3列虚拟存储器VM（P146）VM位置：CPUCacheMainMemoryOnlineDiskVM三个空间：虚拟空间主存储器空间（实空间）外存磁盘空间（实空间）0磁头1磁头9磁头10磁头40柱面0扇区00000000H000000HFFFFFFFFHFFFFFFH00000FFFH000FFFH1页(4K)1页地址映象：虚地址集合与实地址集合的对应规则，或者是约束关系，就是用户在虚地址空间写的程序按照某种规则装入到主存储器中。表现形式就是段表和页表。地址变换（虚实变换）：逻辑地址到物理地址的变换过程。虚拟空间主存储器空间外存磁盘空间YYYYYYYYHZZZZZZHZZZZZZH内部地址变换柱面磁头扇区外部地址变换YYYYYYYYH多种虚拟存储系统（器）分类依据：地址映象和地址变换方法，可管理单元性质段式虚拟存储器页式虚拟存储器段页式虚拟存储器段式虚拟存储器管理单元：段段形式：函数、子程序、数组、表格、向量。说明：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。主程序

(0段)1k1段2段3段0500020002000段号段长起址01k8k150016k22009k320030k08k(02000H)9k(03000H)16k(04000H)30k虚拟空间主存储器段表0段表

长度段表

基址6As段名起始地址装入

位段长访问

方式用户号U段号S段内偏移D多用户

虚地址主存实地址432101n-1As段表基址寄存器一个用户（一道作业）的段表段式虚拟存储器的主要优点：(1)程序的模块化性能好

(2)便于程序和数据的共享

(3)程序的动态链接和调度比较容易

(4)便于实现信息保护段式虚拟存储器的主要缺点：(1)地址变换所花费的时间比较长，做两次加法运算

(2)主存储器的利用率往往比较低

(3)对辅存（磁盘存储器）的管理比较困难2K5K2K4K总的空闲空间：

2K+5K+2K+4K=13K

但不能载入一个6K的程序段，空间浪费严重。0页1页2页3页页号主存页号0123用户程序主存储器页表页式虚拟存储器的地址映象页式虚拟存储器Pa装入修改主存页号标志用户号U虚页号P页内偏移D页内偏移d2pPa页表基址页表实页号p主要优点：(1)主存储器的利用率比较高

(2)页表相对比较简单

(3)地址变换的速度比较快

(4)对磁盘的管理比较容易主要缺点：(1)程序的模块化性能不好

(2)页表很长，需要占用很大的存储空间。例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字，16MB段页式虚拟存储器对用户用来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的物理空间采用分页的方法管理。装入修改实页号标志用户号U段号S页内偏移页内偏移0/11pA实页号p虚页号PAs装入1修改0/1页表地址ApAs4、外部地址变换在操作系统中，把页面失效当作一种异常故障来处理。每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在外页表中都有对应的一个存储字。每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。装入磁盘实地址用户号页内偏移1虚页号外部地址

变换（软

件实现）磁盘号柱面号磁头号块号多用户

虚地址外页表提高虚拟存储器等效访问速度的措施因为，存储系统等效访问速度：T＝HT1＋(1－H)T2所以，提高虚拟存储器等效访问速度的措施有：由于T2远大于T1，所以需要提高主存命中率H缩短访存时间缩短访存时间提高存储器件本身的速度优化存储结构的设计存储结构可以优化设计的环节：1）内部地址变换虚地址——实地址，发生概率100%2）外部地址变换页面失效时发生，发生概率<1%3）页面的替换页面失效又页面争用时发生，发生概率<<1%4）页面的调入与调出页面替换时或者页面初始未装入时发生，发生概率不定根据Amdahl定律，加快内部地址变换速度是关键。提高内部地址变换速度的方法：1）采用单独的小容量随机存储器或寄存器组存放内页表。适合规模较小的机器，如：VM<1M字2）采用“目录表”3）增设“快表”，“快表”与“慢表”相结合4）散列函数目录表页面只存放已经装入主存储器页面的虚地址与实地址对应关系，采用相联方式访问，所以又称为相联目录表。实页号其它标志用户号U页内偏移Dp虚页号P多用户

虚地址目录表（CAM）页内偏移d实页号p多用户虚页号U,P修改0/1主存实地址相联访问快慢表由快表和慢表构成一个两级存储系统：快表：小容量(8～16个字)，高速硬件实现，采用CAM方式访问慢表：全表，按地址访问。实页号用户号U页内偏移Dp虚页号P多用户

虚地址快表（CAM）页内偏移d实页号p多用户虚页号U,P主存实地址实页号p装入1慢表散列函数让NV与存放内容的单元地址之间有某种散列函数关系。用户号U虚页号PNV

即：A=H（NV）为了解决散列冲突（多个虚页散列同一个快表地址），必须将虚地址中虚页号加入到快表中。实页号用户号U页内偏移Dp虚页号P多用户

虚地址按地址访问快表页内偏移d实页号p多用户虚页号PV’主存实地址A快表地址散列变换（硬件实现）相等比较快表命中查慢表多级页表一级页表二级页表三级页表虚拟空间：Nv页面大小：Np一个页表存储字大小：Nd页面级数：g则页表长度（记录数）：Nv/Np每页记录项数：Np/Nd

有等式：Nv/Np=(Np/Nd)g

取对数得P157公式：Log2Nv-Log2Np

g=Log2Np-Log2Nd影响主存命中率的主要因素：程序执行过程中的页地址流分布情况所采用的页面替换算法页面大小主存储器的容量所采用的页面调度算法提高主存命中率的方法页面大小SP命中率H1S2S页面大小与命中率的关系命中率H主存容量S1.0主存容量与命中率的关系页面调度方式与命中率的关系请求式：

当使用到的时候，再调入主存预取式：

在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。

可以避免在程序开始运行时，频繁发生页面失效的情况。

如果调入的页面用不上，浪费了调入的时间，占用了主存资源。CacheCache位置：CPUCacheMainMemory主存储器空间（虚拟空间、实空间）000000H块块号B块内地址W主存/Cache

地址变换块号b块内地址wCacheCache替

换策略储器主存替换块装入块已满未满未命中命中数据送CPU主存地址

来自CPUCache特点：为了提高CPU访问Cache速度，可以访问Cache两步操作（地址变换和取得Cache块内容）进行流水线设计。一般采用两级Cache，一个在CPU内部，一个在主板上。为了加速调块，一般将每块容量设计等于一个主存周期内由主存所能访问到的字数，因此，有Cache存储器主存系统都采用多体交叉存储器。Cache访存的优先级高于通道和CPU访存优先级，优先级次序通常是：Cache、通道、写数、取数、取指。存储系统两级存储器速度比Cache虚拟存储器要达到的目标提高速度扩大容量实现方法全部硬件软件为主硬件为辅3~10倍105倍页(块)大小1~16字1KB~16KB等效存储容量主存储器虚拟存储器透明性对系统和

应用程序员仅对应用

程序员生产工艺与CPU相同MOS工艺Cache存储系统与虚拟存储系统比较CPU、Cache、主存联系CPU与Cache、主存之间有通路CPU与主存、主存与辅存有通路，但CPU与辅存之间没有通路Cache的一致性问题（单处理机、单存储器时）造成Cache与主存的不一致的原因：(1)由于CPU写Cache，没有立即写主存

(2)由于IO处理机或IO设备写主存Cache的更新算法(1)写直达法(写通过法),Write-through：CPU在执行写操作时，把数据同时写入Cache和主存。

(2)写回法(抵触修改法)Write-Back：CPU数据只写入Cache，不写入主存；仅当替换时，才把修改过的Cache块写回到主存。CPUX’I/OXCache主存储器CPUX’I/OXCache主存储器(a)CPU写Cache(b)I/O写主存Cache与主存不一致的两种情况写回法与写直达法的优缺点比较：可靠性，写直达法优于写回法与主存的通信量,WB少于WT

例如：写操作占总访存次数的20％,Cache命中率为99%,每块4个字。当Cache发生块替换时,有30%块需要写回主存,其余的因未被修改过而不必写回主存。则对于WT法,写主存次数占总访存次数的20%。而WB法为(1-99%)×30%×4=1.2%。因此,WB法与主存的通信量要比WT法少10多倍。(3)控制的复杂性,写直达法比写回法简单(4)硬件实现的代价,写回法要比写直达法好写Cache的两种方法：

(1)不按写分配法：在写Cache不命中时，只把所要写的字写入主存。

(2)按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。

目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。Cache的预取算法预取算法有如下几种：

(1)按需取：在出现Cache不命中时，把一个块取到Cache中来

(2)恒预取：无论Cache是否命中，都把下一块取到Cache中

(3)不命中预取：当Cache不命中，把本块和下一块取到Cache中综合考虑因素：命中率的提高Cache与主存之间通信量的增加题：有一个经解释实现的计算机，可按功能分成4级。各一级为了执行一条指令需要下一级的N条指令解释。若执行第1级指令要Kns时间，那么执行第2、3和4级的一条指令各需多少时间？解：执行第2、3、4级一条指令各需时间为：（K×N）ns、（K×N2）ns、（K×N3）ns题：有一个计算机系统可按功能分成4级，各级指令都不相同，每一级指令都比其下一级指令在效能上强M倍，既第i级的一条指令能完成第i-1级的M条指令的计算量。现若需第i级的N条指令解析第i+1级的一条指令，而有一段第1级的程序需运行的时间为Ks，问在第2、3和4级的一段等效的程序各需运行多长时间？解：第1级的一段程序需运行的时间为Ks，第2级等效程序指令数为第1级程序指令数的1/M，而第2级一条指令在第1级解析时需要N条第1级指令，因此第2级等效程序执行时间为（K×N）/Ms。依次类推，第3、4级等效程序执行时间分别为：（K×N2）/M2s、（K×N3）/M3s题：从机器（汇编）语言程序员的角度看，以下哪些是透明的？指令地址寄存器；指令缓冲器；条件码寄存器；乘法器；主存地址寄存器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器解：从机器（汇编）语言程序员的角度看，透明的有：指令缓冲器；乘法器；主存地址寄存器；先行进位链；移位器。题：某机器指令字长16位。设有单地址指令和双地址指令两类，若每个地址字段均为6位，且双地址指令有x条，问单地址指令最多可以有多少条？解：双地址指令格式为：操作码地址码1地址码24位6位6位操作码占4位，共有16种操作码。现双地址指令有x条，占用了16种组合中的x个码点，所以剩下（16-x）个码点均可作扩展标志。单地址指令格式为：扩展操作码地址码10位6位每个码点均可扩展6为操作码，所以单地址指令最多（16-x）×26条。题：一个二级虚拟存储器，CPU访问主存M1和辅存M2的平均时间分别为1us和1ms。经实际测定，此存储器平均访问时间为100us。试定性提出使虚拟存储器平均访问时间能从100us下降到10us的几种方法，并分析这些方法在硬件和软件上的代价。解：二级虚拟存储器等效的平均访问时间公式TA=HTA1+（1-H）TA2要想缩短虚拟存储器平均访问时间，应从提高H和减少TA1两个方面考虑。在主存命中率H=0.901的情况下，改用更高速度的主存器件，即使TA1=0，此时TA=（1-H）TA2=（1-0.901）×1ms≈99us，由于该时间»10us，所以应从提高主存命中率H着手。如果要让TA=10us，其命中率要使H提高到0.991，需要从改进替换算法、调度策略、调整页面大小以及提高主存容量等多方面综合采取措施。题：某虚拟存储器共有8个页面，每页为1024个字，实际主存为4096个字，采用页表法进行地址映像，映像表的内容如表1所示（1）列出会发生页面失效的全部虚页号（2）按以下虚地址：0，3278，1023，1024，2055，7800，4096，6800，计算对应的主存实地址。实页号装入位3111203021100100表1解：（1）发生页面失效的虚页分别为：2，3，5，7（2）由虚地址计算主存实地址情况如下虚地址虚页号页内地址装入位实页号页内地址实地址0372810231024205578004096680000365601023102776324066561011001130失效3102310失效失效2006563072无40951024无无2048656虚页号=[虚地址/页面大小]页内偏移量=虚地址-虚页号×页面大小题：一个程序由5个虚页组成，采用LFU替换算法，在程序执行过程中，依次访问的意味地址流如下：4，5，3，2，5，1，3，2，3，5，1，3可能的最高页命中率是多少？至少要分配给该程序多少个页面才能获得最高的命中率。如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元1024次，求访问存储单元的命中率。解答：（1）由于在页地址流中互不相同的页共有5页，因此可能的最高页命中率为：（2）由于LFU算法为堆栈型替换算法，即随着分配给该程序的主存页面数减少，其命中率单调递减，因此，可采用逐渐减少所分配的主存页数的方法进行推算：若分配N个页面时可获得最高命中率，但分配N-1个页面时命中率却减少，这时我们可以得出分配给N个主存页面才能获得最高命中率的结论。（3）访问存储单元的命中率为：时间页地址流LFU命中7次144进2545进33453进424*532进554*532中61153*2换731532*中8215*32中9315*32中1051*532中1111532*中1231532*中时间页地址流LFU命中3次144进254