计算机系统结构第四章学习资料

计算机系统结构第四章存贮器的速度可用访问时间TA、存贮周期TM、频宽（也称带宽）BM来描述。访问时间TA：存贮器从接到访存申请，到信息被读到数据总线上所需的时间。存贮周期TM：连续启动一个存贮体所需要的时间间隔，一般比TA大。速度2频宽存储器频宽：存储器可提供的数据传送速率，即每秒钟传送的信息位数最大频宽BM：存储器连续访问时能提供的带宽。单体最大频宽：BM=W/TMm个存储体并行工作的最大带宽：BM=W×m/TM其中W：存贮体的字长（位或字节）；m：并行工作的存贮体个数。每位价格c=C/SM其中C：总价格；SM：位数。3这三个指标相互矛盾:42.并行主存系统频宽的分析频带宽度：单位时间内所能访问的数据量。W位单体单字存贮器读出寄存器地址寄存器l字长为W位的单体主存，最大频宽BM=W/TM5W位W位W位W位W位地址寄存器单体多字（m=4）存贮器单字长寄存器l/4最大频宽BM=4W/TMm为一个主存字所包含的CPU字数。6M0主存控制部件多体（m=4）交叉存贮器地址寄存器0地址寄存器1地址寄存器2地址寄存器3M1M2M3总线控制CPUIOPCPU字在主存中可按模m交叉编址，m为分体体数。Mi体的编址模式为：m×i+j，其中i=0，1，2，…,l-1;j=0,1,2,…,m-17并行主存系统：

能并行读出多个CPU字的单体多字和多体单字或多体多字的交叉存贮系统。多体单字与单体多字比较：①前者花费的器件和总价格并不比后者多多少，但其实际频宽却可以比较高（为单体单字的m倍）。②单体多字方式要求可并行读出的m个字必须是地址顺序的且处于同一主存单元，而多体单字则可并行读出地址不连续的主存字。③多体单字方式的各存贮体可以同时启动也可以分时启动。8采用多种存贮器技术，构成存贮层次:3.存贮体系的形成与分支9

一般来说：“Cache－主存”层次：由Cache和主存贮器构成。 主要目的：提高存贮器速度。“主存－辅存”层次：由主存和磁盘存贮器构成 主要目的：扩大存贮器容量。

10“Cache-主存”层次的实现：主要借助于辅助硬件从CPU看，速度是CACHE的，容量是主存的。11

“主－辅存”层次的实现：主要借助于辅助软硬件从整体上看，速度是主存的，容量是辅存的。12主要由软件实现,硬件为辅“Cache－主存”与“主存－辅存”层次的区别几百到几千个字节存储层次CPU对第二级的

访问方式比较项目目的存储管理实现访问速度的比值

(第一级和第二级)典型的块(页)大小失效时CPU是否切换“Cache－主存”层次“主存－辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现几比一几百比一几十个字节可直接访问均通过第一级不切换切换到其他进程主要由专用软件实现几百到几千个字节134.程序局部性原理程序的局部性:时间上的局部性和空间上的局部性。时间局部性指的是：在最近的未来要用到的信息很可能是现在正在使用的信息。空间局部性指的是：在最近的未来要用到的信息很可能是与现在正在使用的信息在程序空间上是相邻或相近的。14155.存贮体系的性能参数①存贮系统的单位容量平均价格。计算公式：M1(S1,C1,T1)M2(S2,C2,T2)

总希望每位平均价格能接近于C2(辅存),为此应使：S2>>S1其中：Ci为Mi的每位价格；Si为Mi的以位计算的存贮容量。每位价格C，命中率H，等效访问时间TA16②命中率定义：在M1存贮器中访问到的概率。③存贮系统的等效访问时间：TA＝HT1＋(1－H)T2N1:M1的访问次数；N2:M2的访问次数当命中率H→1时，T→T117存贮系统的访问效率e：存贮系统的访问效率主要与命中率和两级存贮器的速度之比有关。例：假设T2=5T1，在命中率H为0.9和0.99两种情况下，分别计算存贮系统的访问效率。解：当H=0.9时,e1=1/(0.9+5(10.9))=0.72当H=0.99时,e2=1/(0.99+5(10.99))=0.96184.2虚拟存贮器（VirtualMemory）1961年英国曼彻斯特大学Kilburn等人提出。70年代广泛地应用于大中型计算机系统中。Kilburn特点：虚拟存贮器指的是“主—辅存”层次；它能使计算机具有辅存的容量,接近于主存的速度和辅存的每位成本；使得程序员可以按比主存大得多的空间来编制程序,即按虚存空间编址.19虚拟存贮器管理方式地址的映象和变换方法页面替换算法及其实现方法提高主存命中率的方法本节概述201.虚拟存贮器管理方式地址变换：在程序运行时，把虚地址变换成主存实地址。根据地址映象和变换方法不同，有三种虚拟存贮器：段式虚拟存贮器、页式虚拟存贮器、段页式虚拟存贮器。虚存通过增设地址映像表机构来实现程序在贮存中的定位。这种定位技术是把程序分割成较小的段或页，用相应的映像表机构来指明该程序的某段或某页是否装入主存。21①段式虚拟存储贮器地址映象方法：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。主程序

(0段)1k1段2段3段0500020002000段号段长起址01k8k150016k22009k320030k08k9k16k30k程序

空间主存储器段式虚拟存储器的地址映象220段表

长度段表

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

位段长访问

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

虚地址主存实地址432101n-1As段表基址寄存器一个用户（一道作业）的段表段式虚实地址转换①由用户程序号找到基址寄存器。

②从基址寄存器中读出段表的起始地址。

③把起始地址与多用户虚地址中段号相加得到段表地址。

④把段表中给出的起始地址与段内偏移D相加就能得到主存实地址。地址变换方法23段式虚拟存贮器的主要优点：

(1)程序的模块化性能好。

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

(3)便于实现信息保护。段式虚拟存贮器的主要缺点：

(1)地址变换所花费的时间比较长，做两次加法运算。

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

(3)对辅存（磁盘存储器）的管理比较困难。段式虚拟存贮器的主要优缺点2400.5K3K主存空间AB7K8K10KDC1K程序E2K2.5KF（a）依次调入D、E、F段6.5K主存空间D00.5K3KE4K7K8KF10KABC（b）首先分配法主存空间AE5.5K00.5K3K7K8KD9K10KCB（c）最佳分配法段式存贮分配算法:首先分配法、最佳分配法25页式虚拟存贮器把虚拟地址空间划分成一个个固定大小的块,每块称为一页,把主存贮器的地址空间也按虚拟地址空间同样的大小划分为页。页是一种逻辑上的划分，它可以由系统软件任意指定。虚拟地址空间中的页称为虚页主存地址空间中的页称为实页②页式虚拟存贮器26一个主存地址A由两部分组成，实页号p和页内偏移d。一个虚地址Av由三部分组成，程序号U、虚页号P和页内偏移D。用户号U虚页号P页内偏移D多用户虚拟地址Av的组成实页号p页内偏移d主存地址A的组成270页1页2页3页页号主存页号0123用户程序主存贮器页式虚拟存贮器的地址映象虚页号实页号页表28Pa装入修改主存页号标志程序号U虚页号P页内偏移D页内偏移d2pPa页表基址页表实页号p页式虚拟存贮器的地址变换每个程序使用一个基址寄存器,通过程序号U可找到与这个程序对应的基址寄存器，从中读出页表起始地址。访问这个页表地址，把得到的主存页号p与虚地址中的页内偏移直接拼接起来得到主存实地址。29页式虚拟存贮器的主要优点：

(1)主存贮器的利用率比较高。

(2)页表相对比较简单。

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

(4)对磁盘的管理比较容易。页式虚拟存贮器的主要缺点：

(1)程序的模块化性能不好。

(2)页表很长，需要占用很大的存储空间。例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字。30③段页式虚拟存贮器用户程序按段编写，每个程序段分成几个固定大小的页。31段页式虚拟存贮器的地址变换方法：

(1)先查段表，得到该程序段的页表起始地址和页表长度；

(2)再查页表找到要访问的主存实页号；

(3)最后把实页号p与页内偏移d拼接得到主存的实地址。装入修改实页号标志用户号U段号S页内偏移页内偏移0/11pA实页号p虚页号P’As装入1修改0/1页表地址AAs段页式虚拟存贮器的地址变换322.地址映像和变换地址映象:是指某一数据在主存中的地址与在虚存中的地址两者之间的对应关系。页面争用（实页冲突）：两个以上的虚页想要进入主存中同一页面位置的现象。映象方式的选择应考虑能否尽量减少实页冲突概率。33页面位置0２１２１．．．．．．２ny’-1２ny-1全相联映像每道程序任何虚页可映像到任何实页位置①全相联映像：每道程序的任何虚页可以映像装入到任何实页位置主存虚存34实页号其它标志程序号U页内偏移Dp虚页号P某用户

虚地址目录表（按内容访问的相联存储器）页内偏移d实页号p程序号+用户虚页号U,P修改0/1主存实地址相联访问地址变换过程：把某用户虚地址中U与P拼接起来，相联访问目录表。读出主存实页号p，把p与多用户虚地址中的D拼接得到主存实地址。如果相联访问失败，发出页面失效请求。②目录表:用一个小容量高速存贮器存放页表35目录表的主要优点：①与页表放在主存中相比，查表速度快。②不用设置装入位。目录表的主要缺点：①可扩展性比较差。

②主存储器容量增加时，目录表的造价高，速度降低。36对虚拟存储器来说这个虚地址也仅是辅存的逻辑地址,辅存的实地址如下③外部地址变换虚地址虚页号Nv页内地址NrNvdNd:磁盘机号磁头号柱面号块号块内地址虚拟存储器中还有虚拟地址到辅存实地址的转换.外页表内页表37外部地址变换过程：在操作系统中，把页面失效当作一种异常故障来处理。每个用户程序有一张外页表，虚拟地址空间中的每一页，在外页表中都有对应的一个存储字。每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。装入磁盘实地址程序号页内偏移1虚页号外部地址

变换（软

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

虚地址外页表383.页面替换算法①随机法(Random,RAND法)②先进先出法(First-InFirst-Out,FIFO法)③近期最少使用法(LeastRecentlyUsed,LRU法)④最优替换算法(OPTOPTimalreplacemantalgorithm)39页面替换发生时间：

当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。评价页面替换算法好坏的标准：

一是命中率要高。

二是算法要容易实现。40①随机算法(RANDRandomalgorithm)：用随机数确定要替换的块。特点:算法简单，容易实现；未利用历史信息，未反映程序的局部性，命中率低。②先进先出算法(FIFOFirst-InFirst-Out)：替换最早装入主存的页。特点：比较容易实现，利用了历史信息，没有反映程序的局部性。

最先调入主存的页面，很可能也是经常要使用的页面。41③近期最少使用算法(LFULeastRecentlyUsed)依据各块使用的情况，选择最近最少使用的块替换。特点：既充分利用了历史信息，又反映了程序的局部性，实现起来非常困难。④最优替换算法(OPTOptimalreplacemant)：

是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。在虚拟存储器中，一般采用FIFO和LRU两种算法42举例说明：

设有一道程序，有1至5共五页，执行时的页地址流（即执行时依次用到的程序页页号）为：2，3，2，1，5，2，4，5，3，2，5，2若分配给该道程序的主存有3页，分别采用FIFO和LRU替换算法表示这3页的使用和替换过程。43时间t123456789101112页地址流232152453252先进先出FIFO调进调进调进命中替换替换替换替换命中命中替换替换2232322*313*1551*25*24245*2*43342*34*53*52命中命中命中命中3次近期最少使用LRU2调进23调进232命中23*1调进2*15替换51*2命中25*4替换2*45命中54*3替换35*2替换3*25命中523*命中命中命中命中命中命中命中5次244存储单元替换时应注意防止出现颠簸现象，即调入一块时将另一块调出，紧接着又需要访问刚刚调出块的数据，而将该块调入时又将上一块调出，即颠簸。

例2：

一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。颠簸45在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象,说明命中率与页地址流有关。46

例3：对于一个全相联Cache，假定访问的地址块号序列为1，2，3，4，1，2，5，1，2，3，4，5，在FIFO替换方式下，分别写出分配给程序的主存页面是3页和4页的情况下，其队列的变化情况，并得出结论。47时间t123456789101112页地址流1234125123453N=31121*242*313*44*2151*21*251*2552*35*435*34命中命中命中3次N=4131214412121*231*32231*52*353*14*55*21*252*命中2次命中44444333命中命中结论：FIFO算法不是堆栈型算法，主存页数增加，命中率反而下降。484.堆栈型替换算法定义：

对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt(m)Bt(n)，则这类算法称为堆栈型替换算法。堆栈型算法的基本特点：

随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。495.虚拟存储器工作的全过程506.提高虚拟存贮器等效访问速度的措施造成虚拟存储器速度降低的主要原因：

(1)要访问主存储器须先查段表或页表。

(2)可能需要多级页表。①快慢表快表TLB(TranslationLookasideBuffer)：

采用一个小容量的高速的相关存储部件，用来存放当前最经常用到的那一部分页表，采取按内容相联方式进行访问。慢表：当快表中查不到时，从存放在主存储器中的慢表中查找；按地址访问，用软件实现。快表与慢表也构成了一个两级存储系统。51经快表与慢表实现内部地址变换快表的内容包括两部分即虚地址与实地址的对应关系。

52②散列函数目的：把相联访问变成按地址访问，从而加大快表容量。采用散列变换实现快表按地址访问

避免散列冲突：采用相等比较器。

地址变换过程：相等比较与访问存储器同时进行。53经散列实现快表实页号用户号U页内偏移Dp虚页号P多用户

虚地址按地址访问的快表页内偏移d实页号p多用户虚页号Pv主存实地址散列变

换（硬

件实现）相等比较多用户虚页号查慢表快表地址Ah快表命中散列（Hashing）函数：Ah＝H(Pv)54(1)程序执行过程中的页地址流分布情况。(2)所采用的页面替换算法。

(3)页面大小。(4)主存储器的容量。(5)所采用的页面调度算法。

以下，对后三个因素进行分析。7.影响主存命中率的主要因素：55页面大小为某个值时，命中率达到最大。①页面大小与命中率的关系当页面大小增大时，造成的浪费也要增加。当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。页面大小SP命中率H1S2SS:分配给某道程序的贮存容量56②主存容量与命中率的关系主存命中率H随着分配给该程序的主存容量S的增加而单调上升。在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。命中率H主存容量S1.057③页面调度方式与命中率的关系请求式：

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

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

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

如果调入的页面用不上，浪费了调入的时间，占用了主存资源。584.3高速缓冲存贮器（Cache）基本工作原理地址映象与变换方法591基本工作原理CPU速度与主存速度差异。Cache全部用硬件调度,对所有程序员都是透明的。从CPU看，速度是CACHE的，容量是主存的。60Cache存贮器基本结构·Cache存储体

·地址转换部件

·替换部件

缓存地址主存Cache

块号块内地址MS-Cache地址变换

块号块内地址

Cache替换部件

：：：：：：主存地址替换块装入块不命中数据或指令命中612Cache-主存地址映象与变换方法地址映象：

把存放在主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。地址变换：

当程序已经装入到Cache之后，在实际运行过程中，把主存地址变换成Cache地址。在选取地址映象方法要考虑的主要因素：地址变换的硬件容易实现；地址变换的速度要快；Cache空间利用率要高；发生块冲突的概率要小。62①全相联映象全相联：主存中的任一块可以被映像到Cache中的任意一个位置。Cache常包含几百个块，主存常包含几百万个块。优点：命中率较高，Cache的存储空间利用率高；缺点：线路复杂，成本高，速度低。63②直接映象：1.主存与缓存分成同样大小的块；2.主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数与缓存的总块数相等；主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。

直接相联的地址映象规则

直接映象公式：b=AmodC/Bb：Cache的块号A：主存的块号C/B：Cache的块数64(循环分配)直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。优点：线路简单；缺点：命中率低。65③组相联映象方式

组相联的映象规则

1.主存与缓存分成相同大小的块;2.主存容量是缓存容量的整数倍，将主存空间按缓存的大小分成区，主存中每一区的组数与缓存的组数相同。3.组间直接相联；组内全相联。66组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。67组相联是直接映象和全相联的一种折衷组间直接相联；组内全相联。68组相联映象方式的优点：块的冲突概率比较低。块的利用率大幅度提高。块失效率明显降低。组相联映象方式的缺点：实现难度和造价要比直接映象方式高。69④段相联映象方式

段相联映象方式也是全相联与直接相联的一个折中方案。70由于多个用户对主存的共享,就有多个用户程序和系统软件存于主存中.要防止由于一个用户程序出错而破坏其他用户的程序和系统软件,还要防止一个用户程序不合法地访问不是分配给它的主存区域.为此,系统应提供存贮保护.4.5主存保护存贮保护主要包括两个方面:

存贮区域保护非虚拟存储区域保护虚拟存储区域保护访问方式保护71非虚拟存储区域保护对于不是虚拟存储器的主存系统可采用界限寄