第04章_存储器管理.ppt

《第04章_存储器管理.ppt》由会员分享，可在线阅读，更多相关《第04章_存储器管理.ppt（137页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 存储器管理 第四章存储器管理4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配方式连续分配方式4.4基本分页存储管理方式基本分页存储管理方式4.5基本分段存储管理方式基本分段存储管理方式4.6虚拟存储器的基本概念虚拟存储器的基本概念4.7请求分页存储管理方式请求分页存储管理方式4.8页面置换算法页面置换算法4.9请求分段存储管理方式请求分段存储管理方式 1第四章 存储器管理 4.1 存储器的层次结构存储器的层次结构4.1.1 多级存储器结构多级存储器结构1.存储器功能合理、安全、有效地保存数据2.存储器发展方向接口更新以硬盘为例：ESDI;

2、IDE/EIDE;ATA;SATA/SATA2;SCSI;IEEE1394;USB高速性以USB为例：USB1.1是12Mbps，USB2.0是480Mbps，USB3.0理论上是5Gbps存储密度越来越高，体积越来越小1.7Mb/平方英寸；20Mb/平方英寸；1.43Gb/平方英寸；135Gb/平方英寸；620Gb/平方英寸；1Tb/平方英寸2第四章 存储器管理 3第四章 存储器管理 容量越来越大，价格越来越低以下是近年来关于硬盘价格的趣味数字p1995年 200MB400MB 大于4000元/GBp1996年 1.2GB2.1GB 1500元2000/GBp1998年 1.2GB2.1GB

3、 200元250元/GBp2000年 4.3GB6.4GB 40元/GBp2002年 10GB20GB 20元/GBp2004年 40GB80GB 6.9元/GBp2005年 80GB160GB 4.5元/GBp2006年 80GB250GB 3.8元/GBp2008年 160GB1TB 1.6元/GB p2009年 500GB2TB 0.8元/GB p2010年 500GB2TB 0.6元/GB4第四章 存储器管理 3.存储器层次结构速速度度最快最快最慢最慢容容量量最小最小最大最大单单位位成成本本最贵最贵最廉最廉寄存器寄存器高速缓存高速缓存主存主存磁盘缓存磁盘缓存磁盘磁盘可移动存储介质可移动

4、存储介质CPU主存辅存图4-1 计算机系统存储层次示意 5第四章 存储器管理 4.存储管理功能存储分配与回收本章主要内容，讨论其算法和数据结构地址变换可执行文件生成中的链接技术；程序装入时的重定位技术；进程运行时的地址变换技术和机构(软件、硬件)存储共享和保护代码和数据共享；对地址空间的访问权限(读、写、执行)存储器扩充由用户应用程序控制：覆盖Overlay由OS控制：交换Swapping；请求调入和预调入On Demand&On Prefetch6第四章 存储器管理 4.1.2 主存储器与寄存器主存储器与寄存器1主存储器主存储器主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进

5、程运行时的程序和数据，也称可执行存储器，材质以DRAM为主。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。7第四章 存储器管理 2寄存器寄存器寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器通常用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。8第四章 存储器管理 4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存1

6、高速缓存高速缓存高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。9第四章 存储器管理 2磁盘缓存磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。10第四章 存储器管理 4.2程序的装入和链接程序的装入和链接在多道程

7、序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：首先是要编译编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；其次是链接链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；最后是装入装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和装入过程。11第四章 存储器管理 图4

8、-2对用户程序的处理步骤 程程序序员员编译编译Compile若干若干目标目标模块模块.OBJ源源程程序序.C链接链接Link库函数库函数Lib装入装入模块模块.EXE装入装入Load内存内存进程进程进程进程调度调度CPU12第四章 存储器管理 4.2.1程序的链接程序的链接链接：若干目标模块+库函数 可装入模块根据链接时间的不同，可把链接分成如下三种：(1)静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。(2)装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边

9、链接的链接方式。(3)运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。13第四章 存储器管理 1静态链接方式静态链接方式(Static Linking)在生成可装入模块时(也就是在程序装入运行前)完成的链接。见图4-4特点：一次链接，n次运行得到完整的可装入模块，不可再拆不灵活：不管有用与否的模块都将链接到装入模块，同时导致内存利用率较低不利于模块的修改和升级14第四章 存储器管理 图 4-4程序链接示意图 模块 ACALL B;Return;0L-1模块 BCALL C;Return;0M-1模块 CReturn;0N-10模块 AJSR”L

10、”Return;L-1模块 BJSR”L+M”Return;LL+M-1L+ML+M+N-1模块 CReturn;(a)目标模块(b)装入模块15第四章 存储器管理 2装入时动态链接装入时动态链接(Load-time Dynamic Linking)用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图4-4所示的方式来修改目标模块中的相对地址。16第四章 存储器管理 3运行时动态链接运行时动态链接(Run-time Dynamic Linking)装入时动态链接是将

11、所有可能要运行到的模块都全部链接在一起并装入内存，显然这是低效的，因为往往会有些目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。运行时动态链接方式是对装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在程序执行过程中，当发现一个被调用模块尚未装入内存时，才立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在本次执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。17第四章 存储器管理 4动态

12、链接方式的优点动态链接方式的优点便于共享多个进程可共用一个DLL模块，节省了内存。为部分装入提供了条件(运行时动态链接)一个进程可由若干DLL模块构成，按需装入。便于模块的修改和升级只要被修改模块的接口不变，则该模块的修改不会引发其它模块的重新编译。改善了程序的可移植性可面向不同的应用环境开发同一功能模块的不同版本，根据当前的环境载入匹配的模块版本。18第四章 存储器管理 5动态链接方式的缺点动态链接方式的缺点增加了程序执行时的链接开销。(每次运行都需链接)模块数量众多，增加了模块的管理开销。19第四章 存储器管理 4.2.2程序的装入程序的装入装入：可装入模块装入：可装入模块(.EXE)内存

13、进程内存进程1绝对装入方式绝对装入方式(Absolute Loading Mode)在编译后、装入前已产生了绝对地址（内存地址），装入时不再作地址重定位，即：装入内存前的虚拟地址=装入内存后的物理地址。绝对地址的产生：（1）由编译器完成；（2）由程序员编程完成。优点：装入过程简单，无需地址映射。缺点：不适于多道程序系统；过于依赖硬件结构；不易修改、不灵活。20第四章 存储器管理 2可重定位装入方式可重定位装入方式(Relocation Loading Mode)可装入模块在被装入到内存中时，由装入程序来完成程序虚拟地址 内存物理地址的变换21第四章 存储器管理 图图4-3装入内存时的情况装入内

14、存时的情况LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000程序地址空间程序地址空间物理内存空间物理内存空间如果不进行地址变如果不进行地址变换，那么这条指令换，那么这条指令将无法取到正确的将无法取到正确的数值数值“365”，所，所以该指令中的地址以该指令中的地址应该重定位为：应该重定位为：LOAD 1,12500静态地址重定位：静态地址重定位：指令或数据的内存地址指令或数据的内存地址MA=该指令或数据的虚拟地址该指令或数据的虚拟地址VA+该程序在内存中的首地址该程序在内存中的首地址BA22第四章 存储器管理 可重定位装入的

15、优缺点：优点：p适用于多道程序系统，提高了内存利用率；由于地址映射规则简单，故在地址变换过程中无需硬件变换机构的支持。缺点：p任何进程都要求连续的内存空间；必须将全部模块都装入且装入后不能再移动位置(因为无法实现动态重定位)；不支持虚拟存储器技术；不易实现共享。23第四章 存储器管理 3动态运行时装入方式动态运行时装入方式(Dynamic Run-time Loading)出于实际情况，程序在运行过程中的内存位置可能经常要改变，此时就应采用动态运行时装入的方式。程序装入内存后并不立即进行地址变换，而是等到真正要执行时才由硬件地址变换机构来完成地址变换，从而得到内存物理地址。24第四章 存储器管

16、理 动态地址重定位：动态地址重定位：指令或数据的内存地址指令或数据的内存地址MA =该指令或数据的虚拟地址该指令或数据的虚拟地址VA+重定位基址寄存器重定位基址寄存器BRLOAD 1,25003650100250050002500虚拟地址VR10000基址寄存器BRLOAD 1,250036510000101001250015000程序外存程序一侧 存储器一侧主存+12500取数地址MA25第四章 存储器管理 动态运行时装入的优缺点：优点pOS可将一个进程的不同部分分散存放在不连续的内存空间；可移动进程在内存中的位置(由重定位基址寄存器反映移动情况)；提供了实现虚拟存储器技术的基础(可实现部分

17、模块装入)；有利于实现模块共享。缺点p动态重定位需要硬件变换机构的支持；实现较复杂。26第四章 存储器管理 4.3连续分配方式连续分配方式 连续分配方式是指一个进程在内存中必须占连续分配方式是指一个进程在内存中必须占用连续的存储空间。典型的连续分配方式主要有：用连续的存储空间。典型的连续分配方式主要有：单一连续分配、固定分区分配、动态分区分配、单一连续分配、固定分区分配、动态分区分配、动态重定位分区分配等。动态重定位分区分配等。4.3.1单一连续分配单一连续分配把内存分为系统区和用户区两部分，系统区仅提供给OS使用；用户区是指除系统区以外的全部内存空间，提供给用户使用。优点：简单，易于管理缺点

18、：只能用于单用户单任务OS；内存利用率低，毫无共享性可言。早已淘汰。27第四章 存储器管理 引入：分区存储管理原理将内存分为一些大小相等或不等的分区(Partition)，每个进程可占用一个分区。适于多道程序系统，支持多个进程并发执行。出现了碎片问题I.内碎片：被占用分区的尾部未被利用的空间。II.外碎片：在两个被占用分区之间的难以利用的小空闲分区。分区管理的数据结构：分区表或分区链表。内存紧凑(Compaction)：将各个已占用分区向内存某端移动,从而使分散的各个小空闲分区能相邻,进而合并为一个稍大的空闲分区。28第四章 存储器管理 4.3.2固定分区分配固定分区分配1把内存划分为若干个固

19、定大小的分区，把内存划分为若干个固定大小的分区，分区的总数以及各个分区的大小都是恒定分区的总数以及各个分区的大小都是恒定值。值。各分区大小相等不灵活；对于小进程而言，内存利用率低，内碎片严重；对于大进程而言，分区大小可能无法满足需要，导致无法装入。各分区大小不等小分区、中等分区、大分区。适应性较强，可以有效提高内存利用率。29第四章 存储器管理 2固定分区的内存分配固定分区的内存分配为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图4-5(a)所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能

20、满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图4-5(b)所示。30第四章 存储器管理 图 4-5固定分区使用表 操作系统进程A(8K)进程B(25K)进程C(40K)20 KB32 KB64 KB128 KB256 KB分区号大小/KB起址/KB状态11220已分配23232已分配36464已分配4128128未分配(b)存储空间分配情况(a)分区说明表31第四章 存储器管理 3固定分区分配的优缺点固定分区分配的优缺点优点优点由于各分区大小固定，故易于实现，管理开销小。由于各分区大小固

21、定，故易于实现，管理开销小。缺点缺点内碎片的问题不可避免，较大程序不易装入，故内内碎片的问题不可避免，较大程序不易装入，故内存利用率较低；分区数目固定也限制了进程的并发存利用率较低；分区数目固定也限制了进程的并发度。度。32第四章 存储器管理 4.3.3动态分区分配动态分区分配在动态分区分配方式中，各个分区的大小会在OS的管理下发生改变，分区总数也会相应地发生变化。1分区分配中的数据结构分区分配中的数据结构(1)空闲分区表：记录所有空闲分区情况的二维表分区号大小/KB起址/KB状态11820未分配232242未分配3150502未分配4128750未分配33第四章 存储器管理(2)空闲分区链：

22、将所有的空闲分区链接成一个双向链，如图4-6所示。图4-6空闲链结构 0：未分配：未分配1：已分配：已分配34第四章 存储器管理 2分区分配算法分区分配算法1)首次适应FF算法(First Fit)空闲分区链以地址递增地址递增的次序链接。在每次分配时，都从链首开始顺序查找，直至找到第一个大小能满足要求的空闲分区为止；然后再按照程序的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。特点：简单；高址内存可保留较大的空闲分区；但低址内存会产生很多碎片分区；查找开销大。35第四章 存储器管理 2)循环

23、首次适应NF算法(Next Fit)该算法是由首次适应FF算法演变而成的：分配空间不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，如果达到链尾则回到链首继续。特点：查找开销小；空闲分区分布更均匀；但较大分区难以保留。36第四章 存储器管理 3)最佳适应BF算法(Best Fit)空闲分区链表以容量递增容量递增为序组织，每次分配时从链首查找，将第一个满足空间要求的分区分配出去。特点：最接近按需分配原则；较大的分区容易保留；但会产生很多难以利用的小碎片分区。4)最坏适应WF算法(Worst Fit)空闲分区链表以容量递减容量递减为序组织，每次分配时从链首查找，将第一个

24、满足空间要求的分区分配出去。特点：小碎片分区的问题得到了有效的解决；但大分区也不易保留。最坏适应算法与前面所述的首次适应、循环首次适应、最佳适应算法一起，统称为顺序搜索法。37第四章 存储器管理 5)快速适应QF算法(Quick Fit)该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分。优点：查找效率高；不会对任何分区产生分割，所以

25、能保留大的分区；也不会产生内存碎片。缺点：分区归还主存的算法复杂，系统开销较大；多样化的链表造成管理开销大。38第四章 存储器管理 3分区分配操作分区分配操作1)分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者

26、。图4-7示出了分配流程。39第四章 存储器管理 图 4-7内存分配流程 从头开始查链表检索完否？m.size=u.size?m.sizeu.sizesize从该分区中划出u.size大小的分区分配给进程将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出并分配给进程YNNYYN40第四章 存储器管理 2)回收内存(1)回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。(2)回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。此时也可将两分区合并，也不必

27、分配新表项，用回收区的首址作为新空闲区的首址，大小为两者之和。(3)回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。此时将三个分区合并，使用F1的表项，F1的首址不变，F1的大小为三者之和，删除F2的表项。(4)回收区既不与F1邻接，又不与F2邻接，见图4-8(d)。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。41第四章 存储器管理 图 4-8内存回收时的情况 F1回收区回收区(a)回收区回收区F1(b)F1回收区回收区F2(c)回收区回收区(d)合并，合并，改改F1大小大小合并，合并，改改F1大小大小和首址和首址合并，合并，改改F1

28、大小，大小，删除删除F2表表项项建立一新建立一新表项表项42第四章 存储器管理 例：假设最佳适应法OS(20K)进程进程A(8K)进程进程B(16K)64K空闲区空闲区24K空闲区空闲区进程进程C(124K)0256K进入内存进入内存进程进程E(16K)进程进程D(50K)OS(20K)进程进程A(8K)进程进程B(16K)进程进程D(50K)进程进程E(16K)进程进程C(124K)0256K14K空闲区空闲区8K空闲区空闲区进入内存进入内存进程进程B完成完成进程进程C完成完成OS(20K)进程进程A(8K)16K空闲区空闲区进程进程D(50K)进程进程E(16K)0256K138K空闲区空

29、闲区8K空闲区空闲区如果改为首次适应算法？如果改为首次适应算法？43第四章 存储器管理 4.3.4伙伴系统伙伴系统(自学内容自学内容)固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。44第四章 存储器管理 假设系统的可利用空间容

30、量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。45第四章 存储器管理 当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1tasklist /m95第四章 存储器管理 4.5.4段页式存储管理方式段页式存储管理方式1基本原理基本原理页式：碎片少，内存利用率高段式：面向用户，更利于共享和保护，可动态链接，可动态增长。段页结合式

31、：将程序划分成若干个段，再把每段分成若干个页。思考：段页结合式的逻辑地址应该是什么样的？段号段内页号页内地址96第四章 存储器管理 图4-22利用段表和页表实现地址映射 97第四章 存储器管理 2地址变换过程地址变换过程在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长TL。进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若STL，表示未越界，于是基于段表始址用段号去查段表，从而得到该段的页表始址，并利用逻辑地址中的段内页号P去查该段的页表，从中读出该页所在的物理块号b，再利用块号b和页内地址（即块内地址）来构成物理地址。图4-23示出了段页式系统中

32、的地址变换机构。98第四章 存储器管理 图4-23段页式系统中的地址变换机构 99第四章 存储器管理 思考：在段页式系统中，完成一次取指或取数操作需要访问几次内存？答案：3次！p第1次：根据段号去访问段表，得到页表始址p第2次：根据段内页号去访问页表，获得物理块号后再结合页内地址计算出物理地址p第3次：根据物理地址去访问内存，完成取指或取数操作结论：更应该采用“快表”来提高内存访问效率100第四章 存储器管理 4.6虚拟存储器的基本概念虚拟存储器的基本概念背景：静态分页和静态分段都要求将程序的整体载入内存后才能运行。这将导致大程序无法运行或大量程序无法载入内存的情况。如何解决？从物理上扩充内存

33、：需要￥，不在OS的讨论范畴。从逻辑上扩充内存：虚拟存储器技术的作用。101第四章 存储器管理 4.6.1虚拟存储器的引入虚拟存储器的引入1常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性：程序必须一次性整体装入内存(2)驻留性：程序必须一次性整体卸出内存(程序在执行中途不会部分撤出内存)想想，对于程序想想，对于程序执行来说，这两执行来说，这两个特征是必需的个特征是必需的吗？吗？这两个特征的存这两个特征的存在使得内存利用在使得内存利用率很低，导致系率很低，导致系统吞吐量变小统吞吐量变小102第四章 存储器管理 2局部性原理局部性原理在一小段时间内，程序的执行仅局限于某个段落，且它所

34、访问的存储空间也局限于某个区域。时间局部性：刚访问过的马上会再度被访问。(递归调用、循环结构)空间局部性：刚访问过某处，马上会访问邻近的区域。(顺序存储结构)103第四章 存储器管理 3虚拟存储器的定义虚拟存储器的定义指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和决定，其运行速度慢于内存，而单位成本又接近于外存。由此可见：虚拟存储器技术是一种以时间来换取空间的技术。104第四章 存储器管理 4引入虚存技术的好处引入虚存技术的好处可在较小的可用内存中执行较大的用户程序可在内存中容纳更多的程序来实现并发执行不必影响编程时的程序结构提供

35、给用户可用的虚拟内存空间大于实际物理内存容量105第四章 存储器管理 4.6.2虚拟存储器的实现方法虚拟存储器的实现方法1分页请求系统分页请求系统在静态分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入少数页面的程序及数据，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把暂不运行的页面换出到外存上，同时把即将要运行的页面调入内存。置换是以页为单位进行的。为了实现请求调页和置换功能所必需的硬件和软件支持：1)硬件支持：缺页中断机构；地址变换机构。2)软件支持：请求分页的页表机制；实现请求分页和页面置换的软件。106第四章 存储器管理 2请求分段系统请

36、求分段系统在静态分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。置换是以段为单位进行的。为了实现请求分段所必需的硬件和软件支持：1)硬件支持：缺段中断机构；地址变换机构。2)软件支持：请求分段的段表机制；实现请求分段和段置换的软件。107第四章 存储器管理 4.6.3虚拟存储器的特征虚拟存储器的特征1离散性离散性一个进程在内存中非连续存放，是下面一个进程在内存中非连续存放，是下面2、3、4的基础的基础2多次性多次性一个程序被分成多

37、次调入内存运行一个程序被分成多次调入内存运行3对换性对换性同一进程的不同部分之间换入换出频繁同一进程的不同部分之间换入换出频繁4虚拟性虚拟性用户感觉的内存容量远大于物理内存容量用户感觉的内存容量远大于物理内存容量108第四章 存储器管理 4.6.4虚拟存储器的种类虚拟存储器的种类动态（请求）页式管理动态（请求）页式管理动态（请求）段式管理动态（请求）段式管理动态（请求）段页式管理动态（请求）段页式管理109第四章 存储器管理 4.7请求分页存储管理方式请求分页存储管理方式请求分页存储管理请求分页存储管理(动态分页式管理动态分页式管理)：部分装入：部分装入+动态置换动态置换4.7.1请求分页中的

38、硬件支持请求分页中的硬件支持1页表机制页表机制在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将应用程序的一部分调入内存，还有一部分仍在盘上，故须在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如下页所示：110第四章 存储器管理 页号页号 物理块号物理块号 状态位状态位 访问字段访问字段修改位修改位外存地址外存地址与静态页式管与静态页式管理中的页号和理中的页号和物理块号的作物理块号的作用相同用相同记录该记录该页是否页是否已在内已在内存中存中记录该记录该页已被页已被访问次访问次数的计数的

39、计数器或数器或未被访未被访问时间问时间的计时的计时器器记录该页记录该页在内存中在内存中是否被修是否被修改过。以改过。以决定该页决定该页被换出时被换出时是否需要是否需要重写回外重写回外存存记录该记录该页在外页在外存对应存对应的物理的物理块号块号思考：在上面思考：在上面6个字个字段中，哪些是所有页段中，哪些是所有页都有的？哪些是内存都有的？哪些是内存页才会有的？页才会有的？所有页都有的字段所有页都有的字段内存页才有的字段内存页才有的字段111第四章 存储器管理 2缺页中断机构缺页中断机构缺页：在指令执行期间，一旦发现要访问的页面当前不在内存，则称为一次缺页，必将引发一次缺页中断。缺页中断机构用于确

40、保缺页中断及时、有效、安全地进行。(注意区别“缺页”与“置换”的概念)缺页中断作为中断，它们同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别：(1)缺页中断是在指令执行期间产生和处理的。(2)一条指令在执行期间可能产生多次缺页中断。3地址变换机构地址变换机构112第四章 存储器管理 图 4-25请求分页中的地址变换过程 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表

41、否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是113第四章 存储器管理 4.7.2内存分配策略和分配算法内存分配策略和分配算法1最小物理块数的确定最小物理块数的确定这里所说的最小物理块数，是指能保证进程正常运行所需的最少物理块数。114第四章 存储器管理 2物理块的分配策略物理块的分配策略1)固定分配，局部置换(Fixed Allocation，Local Replacement)为各进程分配固定不变的物理块数，缺页时只能选择本进程的某页来置换。分析：这种方式难以

42、准确确定一个进程所需的物理块数。分配太少会导致频繁缺页，降低吞吐量；分配太多则限制了系统并发度，使资源利用率降低。115第四章 存储器管理 2)可变分配，全局置换(Variable Allocation，Global Replacement)为各进程分配若干物理块数，OS自身设置一个公共空闲物理块队列。某进程缺页时就从公共空闲物理块队列中选择一个物理块以调入缺页。若公共队列的空闲块用完则由OS选择任一进程的某页调出，从而腾出一个空闲块以载入缺页。116第四章 存储器管理 3)可变分配，局部置换(Variable Allocation，Local Replacement)为各进程分配一定数额的物

43、理块数，缺页时只能选择本进程的某页来置换。但若系统发现某进程的缺页中断过于频繁，则由系统为该进程一次性再追加若干物理块以缓解缺页率；若系统发现某进程的缺页中断过于稀少，则由系统从该进程一次性回收若干物理块。117第四章 存储器管理 3物理块分配算法物理块分配算法1)平均分配算法各进程等分所有物理块。极不合理！2)按比例分配3)考虑优先权的分配算法按比例分配+优先权策略118第四章 存储器管理 4.7.3调页策略调页策略(When、Where、How)1何时调入页面何时调入页面When1)请求调页策略要用到某页但发现不在内存时，再去申请调入，被调入的页必定会立即使用。但每次都只调入一页，不断启动

44、I/O使得系统开销大。2)预调页策略预测哪些页将很快被访问到，从而预先调入这些页。准确率不够高。119第四章 存储器管理 2确定从何处调入页面确定从何处调入页面Where对换区采用连续分配方式，I/O速度快。适合于存放对速度要求高的进程或存放被修改过的换出页面。文件区采用离散分配方式，I/O速度慢。适合存放大型进程或不会被修改的页面。120第四章 存储器管理 3页面调入过程页面调入过程How每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块，如果此时内存能容纳新页，则启动磁盘

45、I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。121第四章 存储器管理 4.8页面置换算法页面置换算法(页面淘汰算法页面淘汰算法)页面置换算法的好坏极大地影响着系统性能。页面置换算法的好坏极大地影响着系统性能。抖动抖动(Thrashing)：由于页面

46、置换算法选择不：由于页面置换算法选择不当而导致系统的页面置换调度非常频繁当而导致系统的页面置换调度非常频繁(如刚如刚换出的页立即又被换入换出的页立即又被换入)，使访问外存时间和，使访问外存时间和I/O处理时间大大增加，反而造成处理时间大大增加，反而造成CPU因等待因等待数据而空转，导致系统性能大大下降的现象。数据而空转，导致系统性能大大下降的现象。正确的置换出发点：正确的置换出发点：未来永远不再使用的页面。未来永远不再使用的页面。未来长期不会使用的页面。未来长期不会使用的页面。过去短期内较少使用的页面。过去短期内较少使用的页面。122第四章 存储器管理 4.8.1最佳置换算法和先进先出置换算法

47、最佳置换算法和先进先出置换算法1最佳最佳(Optimal)页面置换算法页面置换算法(OPT算法算法)最久不会再用到的页面将被淘汰，保证缺页率最低，但该算法仅限于理论，无法实现。页面走向页面走向物理块数物理块数701203042303212017013块块置换？置换？置换率置换率缺页率缺页率770701201201203203243243243203203203201201201201701701701置换率置换率=6/20=30%缺页率缺页率=9/20=45%123第四章 存储器管理 2先进先出先进先出(FIFO)页面置换算法页面置换算法当前所有内存页中最先进入内存的页面将被淘汰，简单，易实现

48、。但缺页率偏高，性能较低。页面走向页面走向物理块数物理块数701203042303212017013块块置换？置换？置换率置换率缺页率缺页率707107210210321032403240324032032032103210210210721072107置换率置换率=12/20=60%缺页率缺页率=15/20=75%124第四章 存储器管理 4.8.2最近最久未使用最近最久未使用(LRU)置换算法置换算法1LRU(Least Recently Used)页面置换算法页面置换算法缺页率适中，性能较好，易于实现但需硬件支持 页面走向页面走向物理块数物理块数701203042303212017013

49、块块置换？置换？置换率置换率缺页率缺页率707107210021302032403240324032302230123213021102710071107置换率置换率=9/20=45%缺页率缺页率=12/20=60%125第四章 存储器管理 思考：对同一个算法而言，是否分配给某思考：对同一个算法而言，是否分配给某进程的物理块数越多，则其缺页率越低？进程的物理块数越多，则其缺页率越低？答案：不是！答案：不是！Belay现象：分配给进程的物理块数增多，现象：分配给进程的物理块数增多，其缺页率反而上升的一种现象。主要发生其缺页率反而上升的一种现象。主要发生在在FIFO算法。算法。126第四章 存储器

50、管理 4.8.3对对LRU的改进和简化的改进和简化1简单的简单的Clock置换算法，又称置换算法，又称NRU(Not Recently Used)最近未用算法最近未用算法只关心该页是否使用过2改进型改进型Clock置换算法置换算法最近未访问且未被修改过(最佳淘汰页)最近未访问但已被修改过最近已访问但未被修改过最近已访问且已被修改过(最差淘汰页)入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位为0否127第四章 存储器管理 4.8.4其它页面置换算法其它页面置换算法最少使用LFU(Least Frequently Used)页面缓冲PBA(Page Buffer