计算机系统结构第4章

1、第四章 存储体系,本章内容：,存储体系的形成与性能,虚拟存储器,高速缓冲存储器（Cache）,存储保护,第四章 存储体系,本章重点：,段页式和页式虚拟存储器的原理,页式虚拟存储器的地址映象,LRU、FIFO、OPT算法进行页面替换的过程,LRU算法对页地址流的堆栈处理模拟及性能分析,Cache存储器的直接和组相联地址映象,LRU算法进行块替换的硬件实现及替换过程模拟,Cache存储器的性能分析等。,本章难点：,页式和段页式虚拟存储器中，虚实地址的计算,各种页面替换算法的模拟和页命中率的计算,Cache组相联映象和块替换算法的模拟,第四章 存储体系,4.1 存储体系的形成与性能,发展存储体系的必

2、要性,本节要点：,并行主存系统频宽的分析,存储体系的形成与分支,存储体系的性能参数,一、发展存储体系的必要性,4.1 存储体系的形成与性能,在一台计算机中，通常有多种存储器，如主 存储器、高速缓冲存储器(Cache)、磁盘存储器、 磁带存储器、光盘存储器等。,存储器的主要性能：容量、速度、价格,存储器系统的主要性能：,4.1 存储系统的技术指标,1.存储系统的基本要求,高速度、大容量、低价格。,（1）容量： SM=Wlm W存储体的字长 l-存储体的字数 m-并行工作的存储体数 （2）速度：访问时间TA、存储周期TM、频宽BM； （3）有Sm位的存储器每位的价格：c=C/SM;,矛盾：大容量与

3、高速度矛盾；高速度与低价格矛盾。,一、发展存储体系的必要性,4.1 存储体系的形成与性能,存储器的容量：,存储器的容量： SM=W*l*m,一、发展存储体系的必要性,4.1 存储体系的形成与性能,存储器的速度：,用存储器访问时间、存储周期和频带宽度表示。,存储器访问时间TA：是存储器从接到访存读申请， 到信息被读到数据总线上所需的时间。这段时间 是处理机在启动访存申请后必须等待的时间。,存储器存储周期TM ：是连续启动一个存储体所需 要的时间间隔，它一般比TA大。,存储器频带宽度Bm ：是存储器可提供的数据传送 速率，一般用每秒钟传送的信息位数来衡量，是 反映主存速度的一个重要参数。,一、发展

4、存储体系的必要性,4.1 存储体系的形成与性能,存储器的速度：,存储器最大频宽：存储器连续访问时能提供的数 据传送速率。由于存储体经常发生访问冲突或空 闲等待，存储器不一定能始终满负荷地工作，因 此，主存的实际频宽一般低于主存的最大频宽。,单体存储器最大频宽：BM=W/TM,m个存储体并行工作的最大频宽：BM=m*W/TM,一、发展存储体系的必要性,4.1 存储体系的形成与性能,存储器的价格,可用总价格C或每位的价格c来表示。,存储器的价格包含了存储单元本身及该存储 器操作所必需的外围逻辑电路的价格。,一、发展存储体系的必要性,4.1 存储体系的形成与性能,计算机系统对存储器的基本要求：,计算

5、机希望在尽可能低的价格下提供尽可能 高的速度和尽可能大的容量，这样，存储器容量、 速度和价格之间就产生了矛盾。,一、发展存储体系的必要性,4.1 存储体系的形成与性能,存储器容量、速度和价格间矛盾的解决办法：,由于存储器的容量、速度和价格的要求是相 互矛盾的，只有通过不断改进存储器件的工艺、 配置多种性能价格不同的存储器(主存、辅存)组 成系统、在组成上引入并行和重叠技术，主存采 用并行交叉存取的组织方式的并行主存系统以及 发展存储体系(Memory Hierarchy)等多种途径， 才能同时满足系统对存储器的容量、速度、价格 三方面的要求。,4.1 存储体系的形成与性能,并行主存系统：,解决

6、CPU和存储器之间速度差距的一种方法。,单体多字存储器,多体单字存储器,多体多字存储器,二、并行主存系统频宽的分析,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,单体单字存储器：,存储器最大频宽：BM=W/TM,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,单体多字存储器：,存储器最大频宽： BM=m*W/TM,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字交叉存储器：,由于一个大容量的半导体主存往往是由许多 容量较小、字长较短的相同存储片子组成的，每 个存储片子都有自己的地址译码、读/写驱动等 外围电路，因此可采用多体交叉存储器。每个存 贮器都是一

7、个CPU字的宽度。,存储器最大频宽：BM=m*W/TM,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字交叉存储器：,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字交叉存储器的低位模m交叉编址：,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字交叉存储器的低位模4交叉编址：,Mj体的编址模式为：m*i+j， 其中i=0,1,2,n-1；j=0,1,2,m-1,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字交叉存储器的高位模m交叉编址：,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字交叉存储器的高位模

8、4交叉编址：,n为每个模体内的单元数,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体单字和单体多字比较：,最大频宽一样：BM=m*W/TM,多体单字比单体多字更易提高主存实际频宽：,单体多字方式要求访问的字不仅要连续存放， 还要让它们存放在同一个主存字中。,多体单字方式只要求访问的多个字不发生分 体冲突即可，哪怕地址之间不是顺序的，仍可并 行读出，使实际频宽提高成单体字宽的m倍。,多体单字所花费的总价格不比单体多字方式 多多少。,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,多体多字存储器：,多分体并行存取和单体多字相结合的存储器。,多体多字存储器最大频宽：BM=m

9、*W/TM,在给定的主存器件条件下，采用地址按模m 交叉编址的单体多字、多体单字或多体多字的并 行主存系统的组织方式，可以提高主存的频宽。,并行主存系统：,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,例：,Star-100巨型机存储系统采用多体多字的方式工 作，有32个存储体低位交叉，每个存储体每次并 行读写512位，存储周期为1280ns(磁心存储器)， 处理机字长32位，计算它的频带宽度Bm。,解：,因为：n32，w512，TM1280ns，,BMnw/TM32 512b/1280ns 12.8Gb/s 1.6GB/s400MW/s,但实际上存储器速度的提高要远远小于这个数字

10、,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,思考,并行主存系统的实际频宽要远远小于最大频宽？,如果程序中控制转移的概率 不很低，加上数据的分布存在一 定的离散性，使访问时会发生分 体冲突等，主存系统的实际频宽 （即实际效率）随模数m的增大就 会显著下降。最不利时，主存实 际频宽Bm的提高只是 倍。,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,思考,分体数m是否是越大越好呢？,转移概率不低，数据分布的离散性较大，所 以单纯靠增大m来提高并行主存系统的频宽是有 限的，而且性能价格比会随着m的增大而下降。,在工程实现时，总线负荷及信号的传输延迟 会因主存分体数m的增大而

11、增大，这在一定程度 上抵消了主存频宽改进的好处，使系统的性能价 格比下降。,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,思考,分体数m是否是越大越好呢？,在标量处理机上：m一般可取2-8，很少超过16。 在向量处理机上：由于大量使用了向量指令，减 少了循环分支的使用，降低了程序中的控制转移 概率；加之，因为使用了数组、向量，提高了数 据存放的顺序性，所以其主存分体数m可以超过32。,进一步采用存储体系。,4.1 存储体系的形成与性能,二、并行主存系统频宽的分析,思考,若采用并行主存系统，CPU访问主存的速度仍达不 到要求，怎么办？,4.1 存储体系的形成与性能,存储体系（存储系统

12、、存储层次）的概念：,三、存储体系的形成与分支,两个或两个以上速度、容量和价格各不相同 的存储器，配上辅助软硬件或辅助硬件，成为一 个存储体系。这个系统对应用程序员透明。,从应用程序员看，它是一个存储器，这个存储器的,速度接近速度最快的那个存储器。 存储容量与容量最大的那个存储器相等。 单位容量的价格接近最便宜的那个存储器。,4.1 存储体系的形成与性能,主、辅存存储层次：,三、存储体系的形成与分支,主存的访问时间约 为磁盘访问时间的 10-5，主存的每位 价格约为磁盘每位 价格的103。,4.1 存储体系的形成与性能,虚拟存储系统：,三、存储体系的形成与分支,应用程序员可用机器指令的地址码对

13、整个程 序统一编址，如同应用程序员具有对应于这个地 址码宽度(等于主存-辅存存储层次存储容量)的虚 (主)存空间一样，该地址空间可以比实际主存空 间大得多。 这种指令地址码称为虚地址、逻辑地址、程 序地址等，其对应的存储容量称为虚存容量或程 序空间； 实际主存的地址称为物理地址、实存地址， 其对应存储容量称为实存容量或实存空间。,4.1 存储体系的形成与性能,高速缓冲存储器（Cache）：,三、存储体系的形成与分支,为解决主存和CPU的速度上的差距，在CPU和 主存之间增加一级速度高、容量小、每位价格较 高的高速缓冲存储器(Cache)，借助于辅助硬件， 使Cache和主存构成一个整体。 Ca

14、che对应用程序员和系统程序员均是透明 的。由于CPU和主存的速度只差一个数量级，所 以信息在Cache和主存之间的传送全部由硬件实 现。,4.1 存储体系的形成与性能,高速缓冲存储器（Cache）：,三、存储体系的形成与分支,4.1 存储体系的形成与性能,多级存储层次：,三、存储体系的形成与分支,4.1 存储体系的形成与性能,存储体系(存储层次) ：,三、存储体系的形成与分支,所谓存储体系(存储层次)指的是构成存储系 统的n种不同的存储器（MM）之间，配上辅 助软硬件或辅助硬件，使之从应用程序员来看， 他们在逻辑上是一个整体。让存储层次的等效访 问速度接近于最高层M的，容量是最低层M的， 每

15、位的价格是接近于M的。典型的二级存储体系 是上述的虚拟存储器和Cache存储器。,4.1 存储体系的形成与性能,存储体系的透明性 ：,三、存储体系的形成与分支,虚拟存储器和Cache存储器对应用程序员都 是透明的，不需要对应用程序做任何修改就可以 在系统上运行。,4.1 存储体系的形成与性能,存储体系的透明性 ：,三、存储体系的形成与分支,在虚拟存储器中，为了降低系统的成本，让 不少功能依靠操作系统中的虚拟存储管理软件来 实现。因此，虚拟存储器对系统程序员则是不透 明的。,由于CPU与主存的速度差只有一个数量级， 主存与辅存之间的速度差却有至5个数量级， 所以，Cache存储器只能全部采用硬件

16、来实现。 这样，Cache存储器对系统程序员也是透明的。 操作系统不参予对Cache存储器的管理。,4.1 存储体系的形成与性能,存储体系依据于程序的局部性：,三、存储体系的形成与分支,为了使存储体系有效地工作，当CPU要用到 某个地址的内容时，总希望它尽可能已在速度最 快的M1中准备好，这就要求未来被访问信息的地 址在某种程度上可以预知（判）。而这种预判的 可能性是基于计算机程序的一个特性，即程序的 局部性。,4.1 存储体系的形成与性能,存储体系依据于程序的局部性：,三、存储体系的形成与分支,时间上的局部性：在最近的未来要用到的信息很 可能是现在正在使用的信息，这主要是程序循环 造成的。因

17、此M1只需存放近期使用过的块或页即 可，不必要求能存下整个程序。,程序的局部性表现在时间和空间两个方面。,4.1 存储体系的形成与性能,存储体系依据于程序的局部性：,三、存储体系的形成与分支,空间上的局部性：在最近的未来要用到的信息很 可能与现在正在使用的信息在程序空间上是相邻 或相近的，这主要因为程序中大部分指令是顺序 存储和顺序被取出来执行的，数据一般也是以向 量、数组、树、表等形式簇聚地存储在一起的。 因此，从M2级取所需访问的字送到M1时，一并把 该字所在的块或页整体地取来。,这样，就可以把目前常用或将要用到的信息 预先放在容量较小的第一级存储器M1中，从而使 CPU的访问速度可接近于

18、M1的。,以下图的二级存储体系(M1,M2)为例来分析。 假设：ci为Mi的每位价格； SMi为Mi的以位计算的存储容量； TAi为CPU访问到Mi中的信息所需要的时间。 为评价存储层次的性能，引入： 存储层次的每位价格c、 存储层次的命中率H、 存储层次的等效 访问时间TA、 存储层次的访问 效率,4.1 存储体系的形成与性能,四、存储体系的性能参数,4.1 存储体系的形成与性能,四、存储体系的性能参数,存储层次的每位价格为c：,希望 c 接近于 c2，怎么办?,使SM1 SM2 使增加的辅助软硬件价 格只能占总价格的 一个很小比例。,4.1 存储体系的形成与性能,四、存储体系的性能参数,存

19、储层次的命中率H：,CPU产生的逻辑地址能在M1中访问到(命中到) 的概率。,命中率可用实验或模拟方法来获得。即执行 或模拟一组有代表性的程序，若逻辑地址流的信 息能在M1中访问到的次数为R1，当时在M2中还未调 入到M1的次数为R2，则此命中率：,4.1 存储体系的形成与性能,四、存储体系的性能参数,存储层次的命中率H：,命中率H与程序的地址流，所采用的地址预判 算法及M1的容量有关。我们总是希望H越接近于1越 好。,存储层次的不命中率(失效率)1-H：,CPU产生的逻辑地址在M1中访问不到的概率。,4.1 存储体系的形成与性能,四、存储体系的性能参数,存储层次的等效访问时间：,TA=H*T

20、A1+(1-H)*TA2,希望TA越接近于TA1越好。,存储层次的访问效率：,e=TA1/TA，e越接近于1越好。,4.1 存储体系的形成与性能,四、存储体系的性能参数,存储层次的访问效率：,希望e接近于1，则r值越大，要求H越高；一 般r值较大，所以要求H也较高；H的提高不容易， 所以要r值降低，即降低相邻存储器的访问速度的 差距。另外，减少相邻存储器的容量差也会提高 H，但这会增加存储体系每位的价格。所以，在设 计存储体系时，需要在选择高命中率的算法、层 次相邻两级存储器之间的容量差和速度差，以及 所增设的辅助软硬件价格等多个因素之间进行综 合权衡。,4.2 虚拟存储器,不同的虚拟存储管理

21、方式,本节要点：,段式管理 页式管理 段页式管理,页式虚拟存储器构成,地址的映象与变换 替换算法 替换过程,页式虚拟存储器实现中的问题,4.2 虚拟存储器,虚拟存储器：是主存辅存存储层次的进一步 发展和完善，主要是为了克服高速的实际主存 容量满足不了大程序的容量要求而提出来的。,在虚拟存储器中，应用程序员直接用机器 指令的地址码对整个程序统一编址，这个地址 码宽度所对应的程序空间可以比实际主存的空 间大得多，就好象对应用程序员来说有一个比 实际主存大得多的，可以放下整个程序的虚 (主)存空间。程序不必作任何修改就可以以接 近于实际主存的速度在这个虚拟存储器上运行。,4.2 虚拟存储器,中央处理

22、机只能执行已装入主存的程序块， 而为了提高主存空间的利用率，应及时释放出 主存中现已不用的那部分空间，以便装入别的 程序块。这样随着程序的运行，程序的各个部 分就会在主存和辅存之间不断调进调出。,虚拟存储管理方式：,4.2 虚拟存储器,当辅存中的程序调入主存时，必须进行程 序在主存中的定位。为了使应用程序员对其程 序不用修改就可以在虚拟存储器上运行，即应 用程序员不用考虑如何把程序地址映象和变换 成实际主存的物理地址。,这种程序的定位应当由系统提供的定位机 构来自动完成，从而使之对应用程序员透明。,虚拟存储管理方式：,虚拟存储器通过增设地址映象表机构来实 现程序在主存中的定位。,4.2 虚拟存

23、储器,虚拟存储管理方式：,这种定位技术是把程序分割成若干较小的 段或页，用相应的映象表机构来指明该程序的 某段或某页是否已装入主存。,如已装入主存，则应同时指明其在主存中 所处的开始位置；,如未装入主存，则去辅存中调段或页，并 建立起程序空间和实存空间的地址映象关系， 在程序执行时通过查映象表将程序虚地址变换 成实存地址再访主存。,4.2 虚拟存储器,虚拟存储管理方式：,根据所用的存储映象算法不同，虚拟存储 器可以有三种不同的存储管理方式：,段式虚拟管理方式,页式虚拟管理方式,段页式虚拟管理方式,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,段式存储管理：将程序按逻辑意义

24、分成段，按 段进行调进调出和管理。,段表：为了进行段式管理，每道程序在系统中 都设置段（映象）表，用表中每一行的装入位 来记录程序中各个段是否已装入主存，表中还 有地址字段、段长字段和访问方式字段。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,如果某段已装入主存，段表对应行装入位 置为“”，地址字段记录该段在主存中的起始 地址，段长字段记录该段的大小，访问方式字 段记录该段允许的访问方式，如只读、可写、 只能执行等。,如果某段未装入主存，段表对应行装入位 置为“”，其它字段的内容均无效。,段表本身也是一个段，一般常驻在主存中， 也可以在辅存中，需要时再调入主存。,4.2

25、 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,段表基址寄存器：用于记录段表在主存中的起始 地址的寄存器。,段表基址寄存器组：如果系统有道程序，就有 个段表。用个段表基址寄存器分别记录各道 程序的段表在主存中的起始地址。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,段号 地址 装入位 段长 访问方式,段表：,段号是由0开始顺序编号，与段表行号对应，省去,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,多用户虚地址：,实存地址：,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,段式存储管理地址映象方法：,N-1,段表基

26、址寄存器 (主存中最多可有N道程序),段号 地址 装入位段长 访问方式,0段,4段,实主存空间,2段,1K,2K,3K,已装入,a,A道程序的段表,段式存储管理 地址变换方法,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,段式存储管理的优点：,支持了程序的模块化设计和并行编程的要求， 缩短了程序的编制时间；,各个程序段的修改和增删相互不会影响；,便于多道程序共享主存中某些段，从而可不 必将它们在物理主存中重复存放；,便于按逻辑意义实现存储器的访问方式保护。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,段式存储器管理最主要的问题：,段映象表机构庞大，

27、程序段在主存中起点随 意，造成其地址字段和段长字段都太长；,查表进行地址变换的速度太慢；,对主存各区域的存储管理十分麻烦；,存储器内部段间零头浪费大，有时难以利用。,单纯的段式存储管理在实际系统中无法采用。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,实主存空间管理表：为了对实主存的空间进行分 配和回收，段式存储器需要为操作系统配备一个 实主存空间管理表，进行存储管理。它包括占用 区域表和可用区域表两部分。,占用区域表：其每一行用来指明主存中哪些区域 已被占用，被哪道程序的哪个程序段占用以及该 程序段在主存中的起点和长度。,可用区域表：其每一行指明每个未被占用区的基 地

28、址和区域大小。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,当一个段从辅存装入主存时，操作系统就 在占用区域表中增加一项，并修改可用区域表； 当一个段从主存退出时，就要将其在占用区域 表的项（行）的有关字段内容移入到可用区域 表中，并进行有关它是否可与其他可用区归并 的处理，修改可用区域表。,分配可用区主存空间时，可采用首先分配 算法或最佳分配算法来进行，这两种分配法各 有其优、缺点。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,首先分配算法：顺序扫描可用区域表，当找到 第一个不小于要调入段长度的可用区时，就立 即进行分配。,特点：其分配速度快，

29、分配后可用区零头少， 同时易在主存高区保留大的可用区。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段式存储管理方式：,最佳分配算法：扫视全部的可用区域表，寻找 一个可用区进行分配，使之分配后段间可用区 零头最小。,特点：段间可用区零头数较多，一旦频繁请求 分配的段长都较大时，可能会出现没有哪一个 可用区的零头可以容纳下要求调入的段，而采 用首先分配算法则仍可装入。,但并不意味 首先分配比 最佳分配好,需依次调入 D、E、F段,首先分配算法 D、E、F 全被装入,最佳分配算法 F段无法装入,4.2 虚拟存储器,一、不同的虚拟存储管理方式,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式

30、存储管理方式：,页式存储管理：是将主存空间和程序空间都机 械等分成相同大小的页面，让程序的起点必须 处在主存中某一个页面位置的起点上。,采用段式管理无法装入D模块 采用页式管理却可装入D模块,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,页表：为了进行页式管理，每道程序只需要用 一个页（映象）表来记录该程序的各个虚页是 否已经装入了主存，装入位为“0”，表示该虚页 未装入主存，表中还有实页号字段和访问方式 字段。,页表一般常驻在主存中，也可以在辅存中， 需要时再调入主存。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,如果访问了一个未装入主存的虚页（

31、即页 表中对应该虚页的装入位为“”）时，就产生 页面失效故障，此时程序换道。在CPU执行另一 道程序的同时，让I/O处理机到辅存中去调页。,如果访问到事先已装入主存的页（即页表 中对应该虚页的装入位为“1”）时，读出映象表 中对应行中的实页号，再拼上程序虚地址中页 内位移字段中的页内位移量，就可以得到访物 理主存的地址。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,页表基址寄存器（组）：如果系统有道程序， 就有个页表。用个页表基址寄存器分别记录 各道程序的页表在内存中的基地址页号。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,页表：,虚页号 实页

32、号 装入位 访问方式,虚页号是由0开始顺序编号，与页表行号对应，省去,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,多用户虚地址NS,实存地址np,页式存储管理地址映象方法：,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,指 向 X 道 程 序 页 表 始 点,多用户虚 地址NS,用户标志u 用户虚页号 页内位移,多用户虚页号NV,某道程序的地址Ni,由u转换成基号b,页表基址寄存器,nv,nr,页内位移,主存,nv,1,X道程 序的 内页 表2Nv,Y道程 序的 内页 表2Nv,已装入,主存地址寄存器,实页号,由2Nv 中选1,查不到,查到,页式管

33、理的定位映象机构及其地址的变换过程,0 b N-1,x,x,X,Nv,Nr,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,页式存储管理的好处： 主存储器的利用率比较高 页表相对比较简单 地址变换的速度比较快,页式存储管理的不足： 程序的模块化性能不好 页表很长，需要占用很大的存储空间,页式存储管理在实际中使用较多。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,页式存储管理方式：,将段式存储管理和页式存储管理加以结合， 取长补短，引出了段页式存储管理。,主存页面管理表：为了对整个空间进行管理， 系统中设置专门的主存页面管理表，以指明主 存中每个页面位置的使用状况及其他信

34、息。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,段页式存储管理：将程序按逻辑意义先分成段， 再让各段和实主存都机械等分成相同大小的页。 每道程序通过一个段表和相应的一组页表来进 行程序在主存空间中的定位。,段表：段表中的每一行对应一个段的地址映象 关系。其中，“装入位”表示该段的页表是否已 装入主存，若装入位为“1”，表示该段的页表已 装入主存；若装入位为“0”，表示该段的页表未 装入主存。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,当页表未装入主存时，访问该段将引起段 失效故障。此时，请求从辅存中调入页表，程 序换道，CPU去执行另一道

35、程序。 当页表已装入主存时，则段表中的地址字 段指出了该段的页表在主存中的起始位置（页 号）；访问方式字段指定了对该段的访问方式 控制的保护信息；段长字段指出了该段所用页 表的行数。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,页表：程序中的每一个段都有一个页表。页表 中的每一行用装入位来指明该段此页是否已装 入主存，“1”表示已装入；“0”表示尚未装入。,如果页面未装入主存，则访问到该页时， 就发出页面失效故障，请求到辅存中去调页。,如果页面已装入主存，则用地址字段来指 明该页在主存中的页号。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,段

36、表基址寄存器（组）：,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,段表：,段号 装入位 页表起点 访问方式 段长(页表的行数),4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,页表：,虚页号 实页号 装入位,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,多用户虚地址Ns ：,实存地址np ：,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,用户标志号：多道程序中的每道程序都有一个 用户标志号u。将u转换成基号b后，可找到相 应的段表基址寄存器。利用段表基址寄存器中 所存放的段表起点，就可以找到该用户的

37、段表 在存储器中存放的起点位置。通过所存放的段 表长度，可检测出程序是否越出了该段。,4.2 虚拟存储器,一、不同的虚拟存储管理方式,段页式存储管理方式：,段页式虚拟储存器地址变换方法：,先查段表，得到该程序段的页表起始地址 和页表长度，再查页表找到要访问的主存实页 号，最后把实页号p与页内偏移d拼接得到主存 的实地址。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,当页面失效后，从辅存中将一个虚页调入 主存时，由于虚存空间比主存空间大得多，必 然会出现主存页面位置已被全部占用，而发生 实页冲突的现象，这就要启用替换算法，选出 主存中的一个页，将其替换出去。,替换

38、算法的选择应当尽可能使主存的命中 率高些，算法的实现要方便，所需的软硬件要 少，成本要低。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,几种页面替换算法：,随机算法（RAND ）,先进先出算法（FIFO ）,近期最少使用算法（LRU）,最优替换算法（OPT）,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,随机算法（RAND）,优点：简单，容易实现。,缺点：没有利用历史信息，没有反映程序的局 部性，命中率低。,思想：软件或硬件的随机数生成器产生一个要 替换页的页号。,使用：无法实用。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚

39、拟存储器的页面替换算法：,先进先出算法（FIFO）,优点：较容易实现，利用了历史信息。,缺点：没有反映程序的局部性（最先调入主存 的页面，很可能也是经常使用的页面）， 主存的命中率不一定很高。,思想：选择其中最早装入主存的虚页，将其替 换出去。,使用：但由于实现成本低，目前仍有不少系统 在用。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,先进先出算法（FIFO）,主存页面表和页表是不一样的，页表是对用 户程序空间而言的，每道程序都有一个。主存页 面表是对主存而言的，整个主存只有一个。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,近

40、期最少使用算法（LRU）,优点：既充分利用了历史信息，又反映了程序的 局部性（因为当前最少使用的也，一般来 说，未来也很少使用）,缺点：实现困难（要在主存页面表中配备一个位 数极大的计数器）。,思想：选择近期使用得最少的页，将其替换出去。,使用：难以实用。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,优化替换算法（OPT）,思想：选择未来的近期里不用或很久才用的页 面，将其替换出去。这种算法是在时刻 t找出主存中每个页将要用到的时刻ti， 然后选择其中ti-t最大的那一页作为被 替换的页。,此算法虽然不实用，但它可作为评价所用替换 算法好坏的一个标准，哪种替换算

41、法的主存命 中率能接近于OPT法的，它就是好的替换算法。,在虚拟存储器中，可能采用的只有FIFO和LRU算法。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,评价页面替换算法好坏的标准：,一是命中率要高，二是算法要容易实现。,评价一个替换算法的好坏，一般可用典型 程序在运行时所产生的页地址流，通过对该算 法模拟其页面的替换过程，统计出页面命中率 来分析。,页面命中率的高低与所用的页面替换算法、 页地址流、所分配到的实页数、页面的大小等 多种因素有关。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,例:,设一道程序有1至5共5个页，执行

42、时的页地址流 (即执行时依次用到的程序页页号)为：2，3，2， 1，5，2，4，5，3，2，5，2。若分配给该道程 序的主存有3页。分别采用FIFO、LRU、OPT 这3种替换算法对这3页的使用和替换过程进行 模拟。其中用*标记出按所用算法选作下次应该 被替换掉的页号。,页面命中率与替换算法有关：,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,页面命中率与替换算法有关：,时间t 1 2 3 4 5 6 7 8 9 10 11 12,页地 址流,先进 先出 FIFO,2 3 2 1 5 2 4 5 3 2 5 2,命中3次,4.2 虚拟存储器,二、页式虚拟存储器构成

43、,页式虚拟存储器的页面替换算法：,页面命中率与替换算法有关：,时间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,近期 最少 使用 LRU,命中5次,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,页面命中率与替换算法有关：,时间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,优化 OPT,命中6次,4.2 虚拟存储器,二、页式虚拟存储器构成,页面命中率与页地址流有关：,时间t 1 2 3 4 5 6 7 8,页地址流 1 2

44、3 4 1 2 3 4,先进先出 FIFO,近期最 少使用 LRU,优化 OPT,无命中,无命中,命中3次,“颠簸” 现象,例:,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,页面命中率与分配给程序的主存页数有关：,一般分配的主存页数越多，虚页装入主存的 机会越多，命中率就越高，但这和算法有关。,FIFO算法的实页数增加，命中率反而有可能 下降。,4.2 虚拟存储器,二、页式虚拟存储器构成,页面命中率与分配给程序的主存页数有关：,时间t 1 2 3 4 5 6 7 8 9 10 11 12,页地址流 1 2 3 4 1 2 5 1 2 3 4 5,FIFO n=3

45、,命中2次,命中3次,FIFO n=4,例:,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,从衡量替换算法好坏的命中率高低来考虑， 如果对影响命中率的主存页数n取各种不同值时 都进行一次模拟，其工作量是非常大的。于是 提出了若干能优化存储体系设计，减少模拟工 作量的分析模型。,使用堆栈处理技术的分析模型就适用于采 用堆栈型替换算法的系统。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,就是替换算法具有一种特点：任何时刻t， 在n个实页中的虚页集合总是被包含在给其增 加一个实页，即n+1个实页时，

46、在实存中的虚 页集合之内。即，它是一种满足 nLt时， nLt时， 的特点的替换算法。式中： Lt表示到t时刻已遇到的地址流中不同页的页数， Bt(n)为t时刻，在n页的主存中的虚页集合。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,LRU替换算法和OPT替换算法都属于堆栈型 的替换算法，而RAND替换算法和FIFO替换算法 则不是堆栈型的替换算法。,由于堆栈型替换算法的上述包含性质，使 命中率随主存页数的增加只可能提高，至少不 会下降。只要是堆栈型替换算法，只需采用堆 栈处理技术对地址流模拟处理一次，即可同时 获得对此地址流在不同主存页数时

47、的命中率， 从而大大节省了存储体系设计的工作量。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,用堆栈处理技术对地址流进行模拟处理时， 主存在t时间点的状况用堆栈St表示。n为分配给 该地址流的主存页面数，Lt表示到t时间点已遇 到过的地址流中相异页的页数，St是Lt个不同页 面号在堆栈中的有序集，St(1)是t时间点的St的 栈顶项，St(2)是t时间点的St的次栈顶项，依次 类推。按照堆栈型算法具有的包含性质，必有： nLt时，Bt(n)=St(1)，St(2)， St(n) nLt时，Bt(n)=St(1)，St(2)， St(Lt),4

48、.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,这样，容量为n页的主存中存放的程序页号 就由St的前n项决定。因此，对页地址流A在t时 间点的At页是否命中，只需看St-1的前n项中是否 有At，若有则命中。所以，经过一次模拟处理， 获得St(1)，St(2)， St(Lt)之后，就能同时 知道对应于各种不同的n值时的命中率，从而为 该道程序很快确定所分配的主存页数提供依据。,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,对不同的堆栈型替换算法，St各项的改变过 程是不同的。例如，LRU算法是把主存

49、中刚访问 过的页号置于栈顶，而把最久未被访问过的页号 置于栈底。确切地说，t时间点访问的页At，若 ，则把At压入堆栈使之成为St(1)，而 St-1(1)成为St(2) ， St-1(2)成为St(3)，即 St-1各项都下推一个位置；若 ，则把它由 St-1中取出，压入栈顶成为St(1)，在At之下各项 的位置不动，而At之上的各项都下推一个位置。,4.2 虚拟存储器,二、页式虚拟存储器构成,使用LRU法对页地址流进行堆栈处理：,页地址流A：2 3 2 1 5 2 4 5 3 2 5 2,St(1) St(2) St(3) St(4) St(5) St(6),时间t 1 2 3 4 5 6

50、 7 8 9 10 11 12,4.2 虚拟存储器,二、页式虚拟存储器构成,页式虚拟存储器的页面替换算法：,堆栈型替换算法 ：,各个n值的命中率表,可见，LRU法的命中率随分配给该道程序的 主存页数n的增加而单调上升，至少不会下降， 这是堆栈型算法共同具有的特点。,4.2 虚拟存储器,提高虚拟存储器等效访问速度的措施：,三、页式虚拟存储器实现中的问题,使虚拟存储器的等效访问速度提高到接近 于主存的访问速度是不容易的。这要求：,有很高的主存命中率,要求能有尽可能短的访主存时间,影响主存命中率的因素主要包括：地址流、页面 调度策略、替换算法、页面的大小、分配给程序 的页数等。,4.2 虚拟存储器,

51、影响主存命中率和CPU效率的某些因素：,三、页式虚拟存储器实现中的问题,影响主存命中率的主要因素：,程序执行的页地址流分布情况,所采用的页面替换算法,页面大小,主存储器的容量（页面数）,所采用的页面调度策略,4.2 虚拟存储器,三、页式虚拟存储器实现中的问题,影响主存命中率和CPU效率的某些因素：,页面大小Sp与命中率H的关系：,当页面大小增大时， 造成的浪费也要增加。 但调页效率高，跨页存 贮概率低，页表行数少。,当页面大小减小时， 造成的浪费少。但页表 在主存储器中所占的比 例将增加。,4.2 虚拟存储器,三、页式虚拟存储器实现中的问题,影响主存命中率和CPU效率的某些因素：,页面大小Sp

52、与命中率H的关系：,主存容量S一定时，,当Sp比较小的时候，前 一种情况是主要的， 随着Sp的增大而提高。,当Sp达到某最大值后， 后一种情况成为主要的， 随着Sp的增大而降低。,4.2 虚拟存储器,三、页式虚拟存储器实现中的问题,影响主存命中率和CPU效率的某些因素：,页面大小Sp与命中率H的关系：,在选择页面大小时要折中考虑。应当从提 高调页效率、降低跨页存储概率、减少页表行 数、增大实存空间利用率等方面综合权衡，来 确定其页面的大小。 目前大多数机器中，页面大小取在1KB到 4KB左右，随着主存容量的不断扩大，今后页 面大小将会有所增大。,4.2 虚拟存储器,三、页式虚拟存储器实现中的问

53、题,影响主存命中率和CPU效率的某些因素：,主存储器的容量（页面数）与命中率H的关系：,主存命中率H随着分 配给该程序的主存容量S 的增加而单调上升。,在S比较小的时候， H提高得非常快。随着S的 逐渐增加，H提高的速度 逐渐降低。当S增加到某 一个值之后，H几乎不再 提高。,4.2 虚拟存储器,三、页式虚拟存储器实现中的问题,影响主存命中率和CPU效率的某些因素：,主存储器的容量（页面数）与命中率H的关系：,所以，不能过分追求 高命中率而让S增大到不 适当的程度，因为分配给 某道程序的容量S过大时， 主存的空间利用率可能会 由于程序的不活跃部分所 占的比例增大而下降。,4.2 虚拟存储器,三

54、、页式虚拟存储器实现中的问题,影响主存命中率和CPU效率的某些因素：,页面调度策略与命中率H的关系：,请求式：当使用到的时候，再调入主存。通常 大多数虚拟存储器采用该方法,预取式：在程序重新开始运行之前，把上次停 止运行前一段时间内用到的页面先调 入到主存储器，然后才开始运行程序。 运用了程序存在着局部性的特点。,4.2 虚拟存储器,三、页式虚拟存储器实现中的问题,影响主存命中率和CPU效率的某些因素：,页面调度策略与命中率H的关系：,预取式的主要优点： 可以避免在程序开始运行时，频繁发生页 面失效的情况而提高命中率。,预取式的主要缺点： 因为预取工作区的调度策略增加了预取工 作区的辅助操作时

55、间，可能会把许多不再用到 的虚页也调入了主存，所以应根据情况来决定 是否采用。,4.3 高速缓冲存储器（Cache）,本节要点：,高速缓冲存储器的基本结构,地址的映象与变换,替换算法的实现,Cache的透明性及性能分析,“Cache主存辅存”存储层次,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,高速缓冲存储器(Cache)：在处理机和主存之 间设置一个高速、小容量的缓冲存储器，构成 Cache主存存储层次。使之从CPU看，速度接 近于Cache，容量却是主存的。,Cache主要是用以弥补主存速度的不足。,将Cache和主存机械等分成相同大小的块 (或行)，每块由若干个字

56、或字节组成。,为了加速调块，一般让Cache块的大小取成 主存储器在一个主存周期里能访问到的字节数。,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache的地址映象变换过程：,每当给出一个主存地址进行访存时，都必 须通过主存-Cache地址映象变换机构判定该访 问字所在的块是否已在Cache中。,如果在Cache中，则经地址映象变换机构 将主存地址变换成Cache地址去访Cache。这时 Cache和处理机之间进行单字宽信息的交往。,如果不在Cache中，则产生Cache块失效， 这时就需要从访主存的通路中把包含该字的一 块信息通过多字节宽通路调入Cache，同时将被

57、 访问字直接从单字节宽通路送往处理机。,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache的地址映象变换过程：,如果Cache中已装不进去了，即发生Cache 块冲突，就需要按所选择的替换算法将该块替 换进Cache，并修改地址映象表中有关的地址映 象关系及修改好Cache各块使用状态标志等信息。,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache的地址映象变换过程：,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache存储器的特点：,Cache存储器一旦发生块失效时，程序是 不能换道的，CPU此时只能等着从主存

58、中将所 需的块调入物理 Cache。所以，Cache-主存 间地址映象和变换，以及替换、调度算法全 部采用专门硬件实现。对应用程序员和系统 程序员均透明。Cache存储器的地址映象规则 一般使用组相联或直接映象，不能用全相联 映象。否则，主存-Cache的地址映象表太大， 查表速度太慢，硬件无法实现。Cache存储器 的块替换算法一般采用堆栈法或比较对法的 硬件方式实现，其中用比较对法实现的最多；,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache存储器的特点：,Cache存储器一般采用与CPU类型相同的 半导体工艺构成。,让Cache在物理位置上尽量靠近处理机或

59、就放在处理机中，而不放在主存中，减少CPU 和Cache之间的传输延时。,为了减少ache调块时CPU空等的时间， 在CPU与主存之间设置有直接的数据传送通路。 这样，在ache块失效时，ache的调块与处 理机访主存字在时间上可以重叠地进行。,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache存储器的特点:,为了加速调块，一般让Cache块的大小取 成主存储器在一个主存周期里能访问到的字节 数。因此，主存储器都采用模m多分体多字交 叉并行访问的组织形式。受主存实际效率的影 响，模数m不可能很高，使得Cache块的大小一 般只有十几到几十个字节，只是虚拟存储器页 面大小的几十分之一。,4.3 高速缓冲存储器（Cache）,一、高速缓冲存储器的基本结构,Cache存储器的特点:,提高Cache访主存的优先级，一般高于通 道访主存的级别。在采用Cache存储器的系统 中，访存申请响应的优先次序由高到低通常为 Cache、通道、写数、读数、取指。,4.3 高速缓冲存储器（Cache）,地址的映象：就是让主存块能装入到物理Cache 中的哪些块位