第03章存储系统(4cache及虚拟存储器)

1、第三章第三章 存储系统存储系统存储器概述存储器概述随机读写存储器随机读写存储器RAMRAM半导体只读存储器半导体只读存储器ROMROM高速存储器高速存储器虚拟存储器虚拟存储器cache存储器存储器何谓程序访问的局部性原则？何谓程序访问的局部性原则？ 程序对存储空间程序对存储空间90%90%的访问局限于存储的访问局限于存储空间的空间的10%10%区域中，而另外区域中，而另外10%10%的访问的访问则分布在存储空间其余则分布在存储空间其余90%90%的区域中，的区域中，这即为访存局部性规律。这即为访存局部性规律。3.5 Cache 3.5 Cache 存储器存储器3.5.1 Cache 3.5.1

2、 Cache 基本原理基本原理 解决解决CPU和主存之间速度不匹配采用的一项重要技术和主存之间速度不匹配采用的一项重要技术 一、一、CacheCache的工作机制的工作机制 CacheCache的工作机制基于的工作机制基于程序访问的局部性程序访问的局部性原则。一个原则。一个运行程序的代码大都顺序存放在地址连续的存储器中，运行程序的代码大都顺序存放在地址连续的存储器中，与程序相关的数据在存储器中也相对集中。所以程序与程序相关的数据在存储器中也相对集中。所以程序运行时，尤其有循环程序和子程序时，在较短时间区运行时，尤其有循环程序和子程序时，在较短时间区间内，常会对局部范围的存储器频繁访问，而此范围

3、间内，常会对局部范围的存储器频繁访问，而此范围之外的地址访问甚少。这种现象称为之外的地址访问甚少。这种现象称为程序访问的局部程序访问的局部性性。把局部范围的主存内容从主存放到一个高速小容。把局部范围的主存内容从主存放到一个高速小容量存储器中，使量存储器中，使CPUCPU在这一段时间内直接访问它，以在这一段时间内直接访问它，以减少或不去访问慢速的主存，程序运行速度明显提高。减少或不去访问慢速的主存，程序运行速度明显提高。二、二、 CacheCache及特点及特点位于位于CPUCPU与主存之间；与主存之间；CacheCache容量小于主存容量；容量小于主存容量；CacheCache速度比主存速度快

4、速度比主存速度快5 51010倍倍CacheCache由快速半导体元件构成由快速半导体元件构成 ( (高速高速SRAMSRAM芯片芯片) )CacheCache是主存部分内容的复制全部功能由是主存部分内容的复制全部功能由硬件实现硬件实现, ,对程序员来说对程序员来说, Cache, Cache是透明的是透明的. .三、三、CacheCache存储器的构成存储器的构成 了解构成及工作原理必须首先了解了解构成及工作原理必须首先了解“块块”的概的概念。念。 CacheCache存储器中，把存储器中，把cachecache和主存各分成若干块。和主存各分成若干块。主存与主存与cachecache中块的数

5、目不同但块的大小相等。中块的数目不同但块的大小相等。块的大小通常以在主存的一个读块的大小通常以在主存的一个读/ /写周期中能访写周期中能访问的数据长度为限，常为几十字节。问的数据长度为限，常为几十字节。1 1、CacheCache的基本工作原理的基本工作原理CPU主主存存主存主存地址地址寄存寄存器器MA主存主存Cache地址变换地址变换机构机构Cache存储器存储器Cache地址地址寄存器寄存器替换算法控制部件替换算法控制部件ABDB单字宽单字宽多多字字宽宽不不命命中中命命中中(块块)未满未满已满已满 2.Cache 2.Cache的工作过程的工作过程 (1)CPU送出访问单元的地址由送出访问

6、单元的地址由AB打入打入Cache存储器的存储器的MA,由由主存主存-Cache地址变换机构判断该单元内容是否已在地址变换机构判断该单元内容是否已在Cache中存中存有副本有副本,如果副本已在如果副本已在Cache中中,称为称为命中命中;否则否则,称为称为不命中不命中. (2)当当命中命中时时,把访问地址变换为它在把访问地址变换为它在Cache的地址的地址,然后驱动然后驱动Cache存储体存储体,当是读操作时当是读操作时,CPU从从Cache中直接读取信息中直接读取信息,若若为写操作为写操作,应注意应注意Cache与主存数据的一致性与主存数据的一致性 (3)当当不命中不命中时时,CPU转去直接

7、访问主存转去直接访问主存,若为若为读读操作操作,CPU从主从主存读取信息的同时存读取信息的同时,Cache控制部件把该地址所在那块存储内容控制部件把该地址所在那块存储内容从主存一次调进从主存一次调进Cache存储器存储器.不命中时不命中时,若为若为写写操作操作,许多计算机许多计算机系统只向主存写信息系统只向主存写信息,不必同时把这个地址所在的整块存储内容不必同时把这个地址所在的整块存储内容再调入再调入Cache中中. 注意注意:CPU与与Cache之间的数据交换是以之间的数据交换是以字字为单位为单位;而而Cache与主存之间的数据交换是以与主存之间的数据交换是以块块为单位为单位.3.5.2 3

8、.5.2 主存与主存与cachecache的地址映射（映象）和地址变换的地址映射（映象）和地址变换l地址映象地址映象:将主存块按照某种规则或方法装入或定位在将主存块按照某种规则或方法装入或定位在Cache中。中。l地址变换地址变换:是将主存地址变换成是将主存地址变换成Cache地址，从而访问地址，从而访问Cache。在高速缓冲存储器当中在高速缓冲存储器当中,把把Cache和主存机械等分为相同大小的块和主存机械等分为相同大小的块,每每一块是由若干个字一块是由若干个字(或字节或字节)组成组成. 例：某机主存容量为例：某机主存容量为1MB,划分为划分为2048块块,每块每块512B; Cache容量

9、为容量为 8KB,划分为划分为16块块,每块每块512B块块0块块1块块15Cache标记标记标记标记标记标记块块0块块1块块2047主存主存m位位 块块字字0字字1字字5111.全相联映射方式全相联映射方式 允许主存中的每一个字块映象到允许主存中的每一个字块映象到Cache的任何一个字块位置上的任何一个字块位置上优点优点:块冲突概率最低块冲突概率最低,只有当只有当Cache中全部装满后中全部装满后,才有可能出现才有可能出现块冲突块冲突,灵活灵活缺点缺点:查找时间长查找时间长,速度慢速度慢块块0块块1块块15Cache块块0块块1块块2047主存主存块块0块块1块块2047主存主存11位位主存

10、块号主存块号块内地址块内地址主存地址主存地址11位位9位位块块0块块1块块15Cache0000 00011111相联存储器相联存储器主存块号主存块号Cache块号块号块内地址块内地址Cache地址地址4位位9位位全相联映射全相联映射比较比较 2.直接映象直接映象 主存第主存第j块和块和Cache第第i块有如下函数关系块有如下函数关系: i= j mod m (m为为Cache中总块数中总块数)块块0块块1块块15Cache.0组组1组组127组组块块 0 块块 1 块块15 块块0块块1 块块15 块块15主存主存优点优点:硬件简单硬件简单,成本低成本低 缺点缺点:块冲突率很高块冲突率很高块

11、块0块块1块块15Cache.0组组1组组127组组块块 0 块块 1 块块15 块块0块块1 块块15 块块15主存主存块内地址块内地址主存地址主存地址9位位主存组号主存组号7位位 块块号号7位位存储器存储器主存组号主存组号4位位块内地址块内地址Cache地址地址9位位 块块号号4位位0000 00011111比较比较直接映象直接映象例例:设一个设一个Cache中有中有8个块个块,访问主存进行读操作的块地址序列为访问主存进行读操作的块地址序列为 22、26、22、26、16、4、16、18，求每次访问后，求每次访问后Cache中的内容中的内容地址地址命中与否命中与否地址转换关系地址转换关系2

12、2 22 不命中不命中 22 22 MOD 8=6MOD 8=622 22 命中命中 22 22 MOD 8=6MOD 8=626 26 命中命中 26 26 MOD 8=2MOD 8=216 16 不命中不命中 16 16 MOD 8=0MOD 8=0 4 4 不命中不命中 4 4 MOD 8=4 MOD 8=4 16 16 命中命中 16 16 MOD 8=0MOD 8=018 18 不命中不命中 18 18 MOD 8=2 MOD 8=2 直接映象下直接映象下CacheCache访问情况访问情况26 26 不命中不命中 26 26 MOD 8=2MOD 8=2 直接映象的块分配情况直接映

13、象的块分配情况 访问顺序访问顺序 1 2 3 4 5 6 7 8 地址地址 22 26 22 26 16 4 16 18块分配块分配 情况情况 22操作操作状态状态调调进进2226调调进进2226命命中中2226命命中中222616调调进进2241626调调进进2216264命命中中2216184替替换换01234567块号块号设有一个设有一个Cache的容量为的容量为2K字字,每块每块16字字,求求:(1)该该Cache可容纳多少个块可容纳多少个块?(2)如果主存的容量为如果主存的容量为256K字字,则有多少个块则有多少个块?(3)在直接映象方式下在直接映象方式下,主存的地址格式主存的地址格

14、式? Cache的地址格式的地址格式?(4)在直接映象方式下在直接映象方式下,主存中的第主存中的第I块映象到块映象到Cache中哪一块中哪一块?作业作业 3、组相联映象、组相联映象Cache与主存均分组，主存再分区，与主存均分组，主存再分区，主存中任一区主存中任一区的某一组号与的某一组号与Cache的相应组号有固定的映象关系的相应组号有固定的映象关系(组间直接映射组间直接映射)，但主存组内的块可自由映象到对，但主存组内的块可自由映象到对应的应的Cache组中任一块组中任一块(组内全相联映射组内全相联映射)块块0块块1块块1 块块0 块块0块块0块块1主存主存0组组1组组7组组块块0块块1块块0

15、块块1块块0块块1Cache0组组1组组7组组块块0 块块17组组0区区 块内地址块内地址7位位 3位位 1位位 9位位组号组号组内块号组内块号主存地址主存地址区号区号 块内地址块内地址 3位位 1位位 9位位组号组号组内块号组内块号Cache地址地址8位位07相联存储器相联存储器区号区号 块号块号8组之一组之一块块0块块1块块1 块块0 块块0块块0块块1主存主存0组组1组组7组组块块0块块1块块0块块1块块0块块1Cache0组组1组组7组组块块0 块块17组组0区区128区区比较比较块块0块块11 1、先进先出（、先进先出（First In First OutFirst In First

16、 OutFIFOFIFO）算法）算法 替换出最早进入替换出最早进入CacheCache的信息块的信息块2 2、最不经常使用（、最不经常使用（Least Frequently Used Least Frequently Used LUF LUF）算法）算法 替换掉访问次数最少的信息块替换掉访问次数最少的信息块3 3、近期最少使用（、近期最少使用（Least Recently UsedLeast Recently UsedLRULRU）算法）算法 替换掉近期最少使用的信息块替换掉近期最少使用的信息块4 4、随机（、随机（RandomRandomRANDRAND）算法）算法 用随机数发生器来产生需替

17、换的块号用随机数发生器来产生需替换的块号3.5.5 Cache3.5.5 Cache替换算法替换算法时间时间1 12 23 34 45 56 67 78 89 91010 1111 1212块地址流块地址流2 23 32 21 15 52 24 45 53 32 25 52 2FIFO2 22 22 22 25 55 55 55 53 33 33 33 33 33 33 33 32 22 22 22 22 25 55 51 11 11 14 44 44 44 44 42 2调调 调调 命命 调调 替替 替替 替替 命命 替替 命命 替替 替替LRU2 22 22 22 22 22 22 22

18、23 33 33 33 33 33 33 35 55 55 55 55 55 55 55 51 11 11 14 44 44 42 22 22 2调调 调调 命命 调调 替替 命命 替替 命命 替替 替替 命命 命命 CacheCache替换算法例：访问替换算法例：访问CacheCache的地址流顺序为：的地址流顺序为： 2 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 5 3 2 5 2，假设只有，假设只有3 3块块CacheCache3.5.4 Cache3.5.4 Cache的写操作策略的写操作策略如何保证如何保证cachecache内容与主存中内容与主存中“原本

19、原本”内容相一致内容相一致（只有（只有“写写”操作才有的问题）操作才有的问题）n常见的写操作策略有：常见的写操作策略有：1 1、全写法、写直达法（、全写法、写直达法（Write ThroughWrite Through）：命中时，：命中时，不仅写不仅写cachecache，也同时写入主存。，也同时写入主存。2 2、回写法（、回写法（Write BackWrite Back）：命中时，只改写：命中时，只改写cachecache的的内容，而并不立即修改主存中相应单元的内容，只内容，而并不立即修改主存中相应单元的内容，只有在被改写过的块将被替换出去时才一次写回主存。有在被改写过的块将被替换出去时才一

20、次写回主存。3 3、写一次法、写一次法 处理方法和处理方法和回写法回写法基本相同基本相同, ,只是第一次写命中时只是第一次写命中时要同时写入主存。是要同时写入主存。是全写法全写法和和回写法回写法的结合。的结合。CacheCache的命中率的命中率设设Nc为为Cache 完成存取的总次数完成存取的总次数,Nm为主存完成存取的总次数为主存完成存取的总次数,h为命中率为命中率,则有则有: h=Nc/(Nc+Nm)若若tc表示命中时的表示命中时的Cache访问时间访问时间(即即Cache存储周期存储周期),tm表示未表示未命中时的主存访问时间命中时的主存访问时间(即主存存储周期即主存存储周期),1-h

21、表示未命中率表示未命中率,则则Cache /主存系统的主存系统的平均访问时间平均访问时间ta为为: ta=htc+(1-h)tm设设r=tm/tc表示主存慢于表示主存慢于Cache的倍率的倍率,e表示访问效率表示访问效率,则有则有 : e=tc/ta=tc/htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)h 例例:已知已知Cache存储周期为存储周期为40ns,主存存储周期为主存存储周期为200ns, Cache /主存系统平均访问时间为主存系统平均访问时间为50ns,求求Cache的命中率是多少的命中率是多少? 解解: 因为因为 ta=htc+(1-h)tm 所以所以 h=(

22、ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16Cache的容量讨论的容量讨论增加增加Cache 的容量，显然会提高命中率，但的容量，显然会提高命中率，但两者之间并非成正比关系。两者之间并非成正比关系。比如：比如：VAX-11/750 4KB Cache 90%命中率命中率VAX-11/780 8KB Cache 95%命中率命中率所以所以Cache一般为几一般为几KB几十几十KB3.6 3.6 虚拟存储器虚拟存储器3.6.1 3.6.1 虚拟存储器的基本概念虚拟存储器的基本概念一、什么叫虚拟存储器（一、什么叫虚拟存储器（Virtual MemoryVirtual

23、Memory） 为了克服内存空间不足而提出。虚拟存储器为了克服内存空间不足而提出。虚拟存储器是建立在主存是建立在主存辅存物理结构的基础之上，辅存物理结构的基础之上，由附加的硬件装置及操作系统存储管理软件由附加的硬件装置及操作系统存储管理软件组成的一种存储体系。它将主存和辅存的物组成的一种存储体系。它将主存和辅存的物理空间统一编址，形成一个庞大的存储空间，理空间统一编址，形成一个庞大的存储空间，用户可在其中自由编程，感到的不再是处处用户可在其中自由编程，感到的不再是处处受主存容量限制的存储系统。但是，实质上受主存容量限制的存储系统。但是，实质上CPUCPU仍只能执行调入主存的程序，所以称这种仍只

24、能执行调入主存的程序，所以称这种存储体系为存储体系为虚拟存储器虚拟存储器。主存页号主存页号 主存地址空间主存地址空间 虚存页号虚存页号 程序地址空间程序地址空间013240127 实际的主存单元地址实际的主存单元地址叫做叫做实地址（物理地址、实地址（物理地址、主存地址）主存地址），对应的空，对应的空间叫做实存空间（物理间叫做实存空间（物理空间、主存空间）。空间、主存空间）。虚地址虚地址实地址变换实地址变换二、虚地址和实地址二、虚地址和实地址（VAVA：Virtual AddressVirtual Address，PAPA：Physical AddressPhysical Address）引入虚

25、拟存储器后用户编程时使用的指令地址叫做引入虚拟存储器后用户编程时使用的指令地址叫做虚虚地址（逻辑地址）地址（逻辑地址），该地址允许涉及的空间范围叫做，该地址允许涉及的空间范围叫做虚存空间（逻辑空间）。虚存空间（逻辑空间）。辅存的物理空间辅存的物理空间三、虚拟存储器与三、虚拟存储器与cachecache存储器比较认识存储器比较认识 是两个不同层次的存储体系。是两个不同层次的存储体系。n两者在概念上有许多共同之处：两者在概念上有许多共同之处： 1 1、程序划分为信息块；程序划分为信息块； 2 2、程序运行时，信息块自动从慢速存储器向程序运行时，信息块自动从慢速存储器向 快速存储器调度；快速存储器调

26、度； 3 3、块的调出都采用一定的替换策略；块的调出都采用一定的替换策略； 4 4、新块的调入按一定的映射关系确定调入的新块的调入按一定的映射关系确定调入的 位置。位置。n两者也有许多不同之处：两者也有许多不同之处： 1 1、CacheCache存储器采用与存储器采用与CPUCPU速度相匹配的快速存储元件弥速度相匹配的快速存储元件弥补了主存和补了主存和CPUCPU之间的之间的速度差距速度差距；而虚存的主要功能是；而虚存的主要功能是用来弥补主存和辅存之间的用来弥补主存和辅存之间的容量差距容量差距。2 2、两个存储体系均以信息块作为存储层次之间信息传送两个存储体系均以信息块作为存储层次之间信息传送

27、的单位，但的单位，但cachecache与主存每次传送的信息与主存每次传送的信息块定长块定长，常为，常为几十个字节；而主存和辅存之间即虚拟信息块的划分却几十个字节；而主存和辅存之间即虚拟信息块的划分却有多种方案：有多种方案：页、段页、段等，块长通常为几百等，块长通常为几百几百几百K K字节。字节。3 3、CPUCPU访问访问cachecache比访问慢速主存快比访问慢速主存快5 51010倍；而虚存中主倍；而虚存中主存速度比辅存快存速度比辅存快100 100 1000 1000倍；（辅存向主存调块时间倍；（辅存向主存调块时间为为msms级）。级）。4 4、主存主存-cache-cache体系中

28、，体系中，CPUCPU与二者都与二者都有直接的通路有直接的通路；而虚；而虚存中辅存与存中辅存与CPUCPU之间之间无直接通路无直接通路。5 5、CacheCache存储器存取信息、地址变换和替换策略全部用硬存储器存取信息、地址变换和替换策略全部用硬件实现件实现; ;虚存基本由操作系统的存储管理软件辅助一些虚存基本由操作系统的存储管理软件辅助一些硬件进行块的划分及主硬件进行块的划分及主- -辅间调度。辅间调度。3.6.2 3.6.2 页式虚拟存储器页式虚拟存储器以页为基本信息传送单位的虚存以页为基本信息传送单位的虚存一、页的划分及页式虚存的虚、实地址形式一、页的划分及页式虚存的虚、实地址形式将主

29、存和虚存空间分成大小相等的页，一页为将主存和虚存空间分成大小相等的页，一页为512512几几K K字节字节。例：主存容量例：主存容量64K64K，地址，地址1616位，一页长位，一页长2K2K字节，共字节，共3232页页00000 0000000000000000 0000000000000000 1111111111100000 1111111111100001 0000000000000001 0000000000000001 1111111111100001 1111111111100010 0000000000000010 0000000000000010 11111111111000

30、10 1111111111100011 0000000000000011 0000000000011110 1111111111111110 1111111111111111 0000000000011111 0000000000011111 1111111111111111 11111111111主存空间主存空间第第0 0页页第第1 1页页第第2 2页页第第3131页页2K2K2K2K2K2K2K2K实地址实地址实地址形式：实地址形式：实页号实页号页内地址页内地址类似有虚地址形式：类似有虚地址形式：虚页号虚页号页内地址页内地址二、页表（二、页表（Page TablePage Table）：）

31、：建立一张虚地址页号与实地址页号建立一张虚地址页号与实地址页号的对照表的对照表, ,记录程序的虚页面调入主存时被安排在主存的位置记录程序的虚页面调入主存时被安排在主存的位置, ,并登记一些有关页面的控制信息并登记一些有关页面的控制信息, ,这张表称为页表这张表称为页表.0虚页虚页1虚页虚页2虚页虚页.虚存空间虚存空间.4页面页面.8页面页面.19页面页面.内存空间内存空间 1 0 0 4 1 1 1 19 1 0 0 8装入位装入位修改位修改位替换位替换位其其 它它实页号实页号控制位控制位页表首地址页表首地址页表基地址页表基地址寄存器寄存器0虚页虚页1虚页虚页 2虚页虚页程程序序A A例：例：

32、程序程序A A有有3 3个虚页，其页表及虚、实空间个虚页，其页表及虚、实空间 定位如下：定位如下：三、虚三、虚- -实地址变换实地址变换+页表地址页表地址实页号实页号 页内地址页内地址页表起始地址页表起始地址页表基址页表基址寄存器寄存器变换后的实地址变换后的实地址（主存地址）（主存地址）虚页号虚页号 页内地址页内地址 程序地址程序地址(虚地址虚地址)来自来自CPU页表页表收到来自收到来自CPU的程序地址后，判断的程序地址后，判断若该页在主存中，确定其页面号若该页在主存中，确定其页面号若该页不在主存中，从辅存调入若该页不在主存中，从辅存调入控制位控制位实页号实页号四、页式虚存的特点1 1、页长固

33、定，可以顺序编号，故页表设置、页长固定，可以顺序编号，故页表设置灵活。主存只要有空页即可调度，操作灵活。主存只要有空页即可调度，操作简单。简单。2 2、页长固定会造成空间的、页长固定会造成空间的“零头零头”浪费；浪费；机械地划分页也无法顾及程序的内部结机械地划分页也无法顾及程序的内部结构，指令、数据构，指令、数据跨页跨页的状况将增加查表的状况将增加查表的次数。的次数。页表页表000100010011001111001100007H007H300H300H307H307H练习：练习：已知页式虚存中，某程序一条指令的虚地址是已知页式虚存中，某程序一条指令的虚地址是0000 0111 11111 0

34、00000000 0111 11111 00000，该程序页表起始地址为，该程序页表起始地址为00110011，页面大小为页面大小为1K1K，下列内存单元末，下列内存单元末4 4位状态如图：指出该位状态如图：指出该指令虚地址变换后的实地址。指令虚地址变换后的实地址。解：分为解：分为 2 21818/ 2/ 210= 10= 2 28 8页。即页。即虚页号虚页号( (高八位高八位): 0000 0111 ): 0000 0111 页内地址页内地址: 11111 00000: 11111 00000查表查表: :0011 0011 00000000 + 0000 011100000000 + 00

35、00 0111= 307= 307H H实地址为：实地址为：11001100 11111 00000 11111 000001212位（页表起始地址位（页表起始地址00110011后加后加8 8个个0 0）例例(P125.11):主存容量为主存容量为4MB,虚存容量为虚存容量为1GB,则虚拟地址和物理则虚拟地址和物理地址各为多少位地址各为多少位?如果页面大小为如果页面大小为4KB,则页表长度是少则页表长度是少?解解: 因为因为: 1KB=210B 1MB=220B 1GB=230B 所以所以,虚拟地址为虚拟地址为30位位,物理地址为物理地址为22位位. 如果页面大小为如果页面大小为4KB=21

36、2B,则虚存分为则虚存分为218页页,虚存地址格式虚存地址格式为为: 虚虚 页页 号号 页内地址页内地址0111229物理分为物理分为210页页,物理地址格式物理地址格式为为:页内地址页内地址实页号实页号0 111221页表长度页表长度为为:218(页表中每页要占用一行的信息描述页表中每页要占用一行的信息描述)3.7.3 3.7.3 段式管理段式管理段式管理：段式管理：以程序的逻辑结构所形成的段以程序的逻辑结构所形成的段（如过程、子程序等）作为主存的分配（如过程、子程序等）作为主存的分配单位单位l虚段：虚段：程序空间的段程序空间的段l实段：实段：主存中的段主存中的段l段表：段表：虚段与实段之间

37、关系的对照表，虚段与实段之间关系的对照表，存放在内存中存放在内存中程序段空间程序段空间(外存外存)长度长度1K2K3K1K 2K 段段 0 段段 1段段 2 段段 3 段段 4段起址段起址 装入位装入位 段长段长段号段号012341000612091922024 1 01111K3K1K2K 实主存空间实主存空间地址地址1000202320244071 未未 用用4072 61196120 9191 919210215段段 0段段 4段段 2 段段 3 未未用用 段式虚拟存储器地址变换段式虚拟存储器地址变换段表段表实段实段虚段虚段3.6 3.6 虚拟存储器虚拟存储器3.6.3 3.6.3 段式

38、管理段式管理-虚、实地址变换虚、实地址变换段表基址段表基址+段号段号 段内地址段内地址程序地址程序地址段起始段起始 装入位装入位 段长段长+主存地址主存地址由段表确定所要访问的虚段是否调入主存，判断由段表确定所要访问的虚段是否调入主存，判断未未从辅存调入从辅存调入调入调入确定其在主存的位置确定其在主存的位置段号段号012一、段式、页式管理比较一、段式、页式管理比较l 段式管理易于编译、修改和保护，页式管理相对困难段式管理易于编译、修改和保护，页式管理相对困难l 段式管理可以实现程序和数据共享段式管理可以实现程序和数据共享l 页式管理主存空间易分配，段式管理困难页式管理主存空间易分配，段式管理困

39、难二、段页式管理二、段页式管理l 程序按逻辑结构分段，每段再分成大小固定的页程序按逻辑结构分段，每段再分成大小固定的页l 每个程序有一张段表，各段有一张相应的页表每个程序有一张段表，各段有一张相应的页表l CPUCPU访存时，访存时，先查段表先查段表找该段页表地址找该段页表地址 再查页表再查页表找对应的主存地址找对应的主存地址3.7.4 3.7.4 段页式管理段页式管理(a) (a) 地址映象关系地址映象关系 段基址表段基址表 段表段表 页表页表 0 0 0 0 0 0 . . N N- -1 1 L L- -1 1 M M- -1 1 段表长度段表长度 段表基址段表基址 装入位装入位 段长段

40、长 页表地址页表地址(b) (b) 地址映象方法地址映象方法页内地址页内地址页内地址页内地址虚页号虚页号实页号实页号段号段号基号基号 1 1 M M 1 1 L L主存地址空间主存地址空间程序地址空间程序地址空间A A 段段B B 段段虚地址虚地址实地址实地址段段页页装入位装入位 . .实页号实页号3.6.5 3.6.5 虚拟存储器管理虚拟存储器管理l调度方法：调度方法： 按需调页，程序的各页仅在需要时才调入主存按需调页，程序的各页仅在需要时才调入主存l映象方式：映象方式：全相联映象、直接映象、组相联映象全相联映象、直接映象、组相联映象l替换策略：替换策略： 先进先出（先进先出（First I

41、n First OutFirst In First OutFIFOFIFO） 近期最少使用算法近期最少使用算法（Least Recently UsedLeast Recently UsedLRULRU）例例:假设主存只有假设主存只有a,b,c三个页框三个页框,组成组成a进进c出的出的FIFO队列队列,进程访问进程访问页面的序列是页面的序列是0,1,2,4,2,3,0,2,1,3,2号号,用列表法求出采用用列表法求出采用FIFO+LRU和和FIFO替换策略时的命中率替换策略时的命中率. 解解:页面访问序列页面访问序列012 4 2 3 0 2 1 3 2FIFO算法算法FIFO+LRU算法算法a

42、b c abc01021042142134 2 0342031 20312312命中率命中率2/11=18.2%命命命命 01 02 104212413240322031203122313/11=27.3%命命命命命命FIFO+LRU算法：算法：未命中时未命中时,以以“先进先出先进先出”进行淘汰进行淘汰,一旦命中一旦命中,将将命中项置到队尾。命中项置到队尾。队尾队尾队首队首3.7 3.7 存储保护存储保护 当多个用户共享主存时，应防止由于当多个用户共享主存时，应防止由于一个用户程序出错而破坏其他用户的程一个用户程序出错而破坏其他用户的程序和系统软件序和系统软件, ,以及一个用户程序不合以及一个用户程序不合法地访问不是分配给它的主存区域。法地访问不是分配给它的主存区域。在虚拟存储系统中，通常采用：在虚拟存储系统中，通常采用： 页表保护页表保护、段表保护段表保护、环保护、环保护、键保护键保护1. 1. 页表保护和段表保护页表保护和段表保护 每个程序的段表和页表本