《存储器管理》课件

《《存储器管理》课件》由会员分享，可在线阅读，更多相关《《存储器管理》课件（137页珍藏版）》请在装配图网上搜索。

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

2、SATA/SATA2;SCSI;IEEE1394;USB高速性 以USB为例：是12Mbps，是480Mbps，理论上是5Gbps存储密度越来越高，体积越来越小 平方英寸；20Mb/平方英寸；平方英寸；135Gb/平方英寸；620Gb/平方英寸；1Tb/平方英寸第四章 存储器管理 3第四章 存储器管理 4容量越来越大，价格越来越低 以下是近年来关于硬盘价格的趣味数字p1995年 200MB400MB 大于4000元/GBp1996年 2.1GB 1500元2000/GBp1998年 2.1GB 200元250元/GBp2000年 6.4GB 40元/GBp2002年 10GB20GB 20元/

3、GBp2004年 40GB元/GBp2005年 80GB元/GBp2006年 80GB元/GBp2008年 160GB元/GB p2009年 500GB元/GB p2010年 500GB元/GB第四章 存储器管理 5 3.存储器层次结构速度速度最快最快最慢最慢容量容量最小最小最大最大单位成本单位成本最贵最贵最廉最廉寄存器寄存器高速缓存高速缓存主存主存磁盘缓存磁盘缓存磁盘磁盘可移动存储介质可移动存储介质CPU主存辅存图4-1 计算机系统存储层次示意 第四章 存储器管理 6 4.存储管理功能存储分配与回收 本章主要内容，讨论其算法和数据结构地址变换 可执行文件生成中的链接技术；程序装入时的重定位技

4、术；进程运行时的地址变换技术和机构(软件、硬件)存储共享和保护 代码和数据共享；对地址空间的访问权限(读、写、执行)存储器扩充 由用户应用程序控制：覆盖Overlay 由OS控制：交换Swapping；请求调入和预调入On Demand&On Prefetch第四章 存储器管理 74.1.2 主存储器与寄存器主存储器与寄存器 1主存储器主存储器主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器，材质以DRAM为主。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。第四章 存储器管理 8 2

5、寄存器寄存器寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器通常用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。第四章 存储器管理 94.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存 1高速缓存高速缓存高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。根据程序执行的局部性原理(即

6、程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。第四章 存储器管理 10 2磁盘缓存磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。第四章 存储器管理 11程序的装入和链接程序的装入和链接 在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：首先是要编译编译，

7、由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；其次是链接链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；最后是装入装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和装入过程。第四章 存储器管理 12图4-2对用户程序的处理步骤 程序员程序员编译编译Compile若干若干目标目标模块模块.OBJ源源程程序序.C链接链接Link库函数库函数Lib装入装入模块模块.EXE装入装入Load内存

8、内存进程进程进程进程调度调度CPU第四章 存储器管理 13程序的链接程序的链接链接：若干目标模块+库函数 可装入模块根据链接时间的不同，可把链接分成如下三种：(1)静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。(2)装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。(3)运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。第四章 存储器管理 14 1静态链接方式静态链接方式(Static Link

9、ing)在生成可装入模块时(也就是在程序装入运行前)完成的链接。见图4-4特点：一次链接，n次运行 得到完整的可装入模块，不可再拆 不灵活：不管有用与否的模块都将链接到装入模块，同时导致内存利用率较低 不利于模块的修改和升级第四章 存储器管理 15图 4-4程序链接示意图 模块 ACALL B;Return;0L-1模块 BCALL C;Return;0M-1模块 CReturn;0N-10模块 AJSR”L”Return;L-1模块 BJSR”L+M”Return;LL+M-1L+ML+M+N-1模块 CReturn;(a)目标模块(b)装入模块第四章 存储器管理 16 2装入时动态链接装入

10、时动态链接(Load-time Dynamic Linking)用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图4-4所示的方式来修改目标模块中的相对地址。第四章 存储器管理 17 3运行时动态链接运行时动态链接(Run-time Dynamic Linking)装入时动态链接是将所有可能要运行到的模块都全部链接在一起并装入内存，显然这是低效的，因为往往会有些目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则

11、显然就不会用到该模块。运行时动态链接方式是对装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在程序执行过程中，当发现一个被调用模块尚未装入内存时，才立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在本次执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。第四章 存储器管理 18 4动态链接方式的优点动态链接方式的优点便于共享 多个进程可共用一个DLL模块，节省了内存。为部分装入提供了条件(运行时动态链接)一个进程可由若干DLL模块构成，按需装入。便于模块的修改和升

12、级 只要被修改模块的接口不变，则该模块的修改不会引发其它模块的重新编译。改善了程序的可移植性 可面向不同的应用环境开发同一功能模块的不同版本，根据当前的环境载入匹配的模块版本。第四章 存储器管理 19 5动态链接方式的缺点动态链接方式的缺点增加了程序执行时的链接开销。(每次运行都需链接)模块数量众多，增加了模块的管理开销。第四章 存储器管理 20程序的装入程序的装入 装入：可装入模块装入：可装入模块(.EXE)内存进程内存进程 1绝对装入方式绝对装入方式(Absolute Loading Mode)在编译后、装入前已产生了绝对地址（内存地址），装入时不再作地址重定位，即：装入内存前的虚拟地址=

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

14、间如果不进行地址变如果不进行地址变换，那么这条指令换，那么这条指令将无法取到正确的将无法取到正确的数值数值“365”，所以，所以该指令中的地址应该指令中的地址应该重定位为：该重定位为：LOAD 1,12500静态地址重定位：静态地址重定位：指令或数据的内存地址指令或数据的内存地址MA=该指令或数据的虚拟地址该指令或数据的虚拟地址VA+该程序在内存中的首地址该程序在内存中的首地址BA第四章 存储器管理 23可重定位装入的优缺点：优点：p适用于多道程序系统，提高了内存利用率；由于地址映射规则简单，故在地址变换过程中无需硬件变换机构的支持。缺点：p任何进程都要求连续的内存空间；必须将全部模块都装入且

15、装入后不能再移动位置(因为无法实现动态重定位)；不支持虚拟存储器技术；不易实现共享。第四章 存储器管理 24 3动态运行时装入方式动态运行时装入方式(Dynamic Run-time Loading)出于实际情况，程序在运行过程中的内存位置可能经常要改变，此时就应采用动态运行时装入的方式。程序装入内存后并不立即进行地址变换，而是等到真正要执行时才由硬件地址变换机构来完成地址变换，从而得到内存物理地址。第四章 存储器管理 25动态地址重定位：动态地址重定位：指令或数据的内存地址指令或数据的内存地址MA =该指令或数据的虚拟地址该指令或数据的虚拟地址VA+重定位基址寄存器重定位基址寄存器BRLOA

16、D 1,25003650100250050002500虚拟地址VR10000基址寄存器BRLOAD 1,250036510000101001250015000程序外存程序一侧 存储器一侧主存+12500取数地址MA第四章 存储器管理 26动态运行时装入的优缺点：优点pOS可将一个进程的不同部分分散存放在不连续的内存空间；可移动进程在内存中的位置(由重定位基址寄存器反映移动情况)；提供了实现虚拟存储器技术的基础(可实现部分模块装入)；有利于实现模块共享。缺点p动态重定位需要硬件变换机构的支持；实现较复杂。第四章 存储器管理 27连续分配方式连续分配方式 连续分配方式是指一个进程在内存中必须占连续

17、分配方式是指一个进程在内存中必须占用连续的存储空间。典型的连续分配方式主要有：用连续的存储空间。典型的连续分配方式主要有：单一连续分配、固定分区分配、动态分区分配、单一连续分配、固定分区分配、动态分区分配、动态重定位分区分配等。动态重定位分区分配等。单一连续分配单一连续分配 把内存分为系统区和用户区两部分，系统区仅提供给OS使用；用户区是指除系统区以外的全部内存空间，提供给用户使用。优点：简单，易于管理 缺点：只能用于单用户单任务OS；内存利用率低，毫无共享性可言。早已淘汰。第四章 存储器管理 28引入：分区存储管理原理将内存分为一些大小相等或不等的分区(Partition)，每个进程可占用一

18、个分区。适于多道程序系统，支持多个进程并发执行。出现了碎片问题内碎片：被占用分区的尾部未被利用的空间。外碎片：在两个被占用分区之间的难以利用的小空闲分区。分区管理的数据结构：分区表或分区链表。内存紧凑(Compaction)：将各个已占用分区向内存某端移动,从而使分散的各个小空闲分区能相邻,进而合并为一个稍大的空闲分区。第四章 存储器管理 29固定分区分配固定分区分配 1把内存划分为若干个固定大小的分区，把内存划分为若干个固定大小的分区，分区的总数以及各个分区的大小都是恒定分区的总数以及各个分区的大小都是恒定值。值。各分区大小相等 不灵活；对于小进程而言，内存利用率低，内碎片严重；对于大进程而

19、言，分区大小可能无法满足需要，导致无法装入。各分区大小不等 小分区、中等分区、大分区。适应性较强，可以有效提高内存利用率。第四章 存储器管理 30 2固定分区的内存分配固定分区的内存分配为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图4-5(a)所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图4-5(b)所示。第四章 存储器管理 31图

20、4-5固定分区使用表 操作系统进程A(8K)进程B(25K)进程C(40K)20 KB32 KB64 KB128 KB256 KB分区号大小/KB起址/KB状态11220已分配23232已分配36464已分配4128128未分配(b)存储空间分配情况(a)分区说明表第四章 存储器管理 32 3固定分区分配的优缺点固定分区分配的优缺点优点优点 由于各分区大小固定，故易于实现，管理开销小。由于各分区大小固定，故易于实现，管理开销小。缺点缺点 内碎片的问题不可避免，较大程序不易装入，故内内碎片的问题不可避免，较大程序不易装入，故内存利用率较低；分区数目固定也限制了进程的并发存利用率较低；分区数目固定

21、也限制了进程的并发度。度。第四章 存储器管理 33动态分区分配动态分区分配 在动态分区分配方式中，各个分区的大小会在OS的管理下发生改变，分区总数也会相应地发生变化。1分区分配中的数据结构分区分配中的数据结构(1)空闲分区表：记录所有空闲分区情况的二维表分区号大小/KB起址/KB状态11820未分配232242未分配3150502未分配4128750未分配第四章 存储器管理 34(2)空闲分区链：将所有的空闲分区链接成一个双向链，如图4-6所示。图4-6空闲链结构 前向指针0N个字节可用后向指针0N+2N+20：未分配：未分配1：已分配：已分配第四章 存储器管理 35 2分区分配算法分区分配算

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

23、查找，如果达到链尾则回到链首继续。特点：查找开销小；空闲分区分布更均匀；但较大分区难以保留。第四章 存储器管理 373)最佳适应BF算法(Best Fit)空闲分区链表以容量递增容量递增为序组织，每次分配时从链首查找，将第一个满足空间要求的分区分配出去。特点：最接近按需分配原则；较大的分区容易保留；但会产生很多难以利用的小碎片分区。4)最坏适应WF算法(Worst Fit)空闲分区链表以容量递减容量递减为序组织，每次分配时从链首查找，将第一个满足空间要求的分区分配出去。特点：小碎片分区的问题得到了有效的解决；但大分区也不易保留。最坏适应算法与前面所述的首次适应、循环首次适应、最佳适应算法一起，

24、统称为顺序搜索法。第四章 存储器管理 385)快速适应QF算法(Quick Fit)该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分。优点：查找效率高；不会对任何分区产生分割，所以能保留大的分区；也不会产生内存碎片。缺点：分区归还主存的算法复杂，系统开销较大；多样化的链表造成管理开销大。第四章 存储器管理 39 3分区分配操作分区分

25、配操作1)分配内存 系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为，表中每个空闲分区的大小可表示为。若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图4-7示出了分配流程。第四章 存储器管理 40图 4-7内存分配流程 从头开始查链表检索完否？m.size=u.size?m.sizeu.sizesize从该分区中划出u

26、.size大小的分区分配给进程将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出并分配给进程YNNYYN第四章 存储器管理 412)回收内存(1)回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。(2)回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。此时也可将两分区合并，也不必分配新表项，用回收区的首址作为新空闲区的首址，大小为两者之和。(3)回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。此时将三个分区合并，使用F1的表项，F1的首址不

27、变，F1的大小为三者之和，删除F2的表项。(4)回收区既不与F1邻接，又不与F2邻接，见图4-8(d)。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。第四章 存储器管理 42图 4-8内存回收时的情况 F1回收区回收区(a)回收区回收区F1(b)F1回收区回收区F2(c)回收区回收区(d)合并，合并，改改F1大小大小合并，合并，改改F1大小大小和首址和首址合并，合并，改改F1大小，大小，删除删除F2表表项项建立一新建立一新表项表项第四章 存储器管理 43 例：假设最佳适应法OS(20K)进程进程A(8K)进程进程B(16K)64K空闲区空闲区24

28、K空闲区空闲区进程进程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空闲区空闲区8K空闲区空闲区如果改为首次适应算法？如果改为首次适应算法？第四章 存储器管理 44伙伴系统伙伴系统(自学内容自学内容)固定分区和动态分区方式都有不足之处。固定分区方式

29、限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。第四章 存储器管理 45 假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于

30、每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。第四章 存储器管理 46 当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1tasklist /m第四章 存储器管理 96段页式存储管理方式段页式存储管理方式 1基本原理基本原理页式：碎片少，内存利用率高段式：面向用户，更利于共享和保护，可动态链接，可动态增长。段页结合式：将程序划分成若干个段，再把每段分成若干个页。思考：段页结合式的逻辑地址应该是什么样的？段号段内页号页内地址第四章 存储器管理 97图4-22利用段表和页表实现地址映射 段号 状态 页表

31、大小 页表始址0111213041页号 状态存储块#0111213041操作系统主存页表段表段表大小 段表始址段表寄存器第四章 存储器管理 98 2地址变换过程地址变换过程在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长TL。进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若STL，表示未越界，于是基于段表始址用段号去查段表，从而得到该段的页表始址，并利用逻辑地址中的段内页号P去查该段的页表，从中读出该页所在的物理块号b，再利用块号b和页内地址（即块内地址）来构成物理地址。图4-23示出了段页式系统中的地址变换机构。第四章 存储器管理 99图4-2

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

33、法运行或大量程序无法载入内存的情况。如何解决？从物理上扩充内存：需要￥，不在OS的讨论范畴。从逻辑上扩充内存：虚拟存储器技术的作用。第四章 存储器管理 102虚拟存储器的引入虚拟存储器的引入 1常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性：程序必须一次性整体装入内存(2)驻留性：程序必须一次性整体卸出内存(程序在执行中途不会部分撤出内存)想想，对于程序想想，对于程序执行来说，这两执行来说，这两个特征是必需的个特征是必需的吗？吗？这两个特征的存这两个特征的存在使得内存利用在使得内存利用率很低，导致系率很低，导致系统吞吐量变小统吞吐量变小第四章 存储器管理 103 2局部性原理局部

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

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

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

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

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

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

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

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

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

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

44、策略 要用到某页但发现不在内存时，再去申请调入，被调入的页必定会立即使用。但每次都只调入一页，不断启动I/O使得系统开销大。2)预调页策略 预测哪些页将很快被访问到，从而预先调入这些页。准确率不够高。第四章 存储器管理 120 2确定从何处调入页面确定从何处调入页面Where对换区 采用连续分配方式，I/O速度快。适合于存放对速度要求高的进程或存放被修改过的换出页面。文件区 采用离散分配方式，I/O速度慢。适合存放大型进程或不会被修改的页面。第四章 存储器管理 121 3页面调入过程页面调入过程How每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分

45、析中断原因后转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。第四章 存储器管理 122页面置换算法页面置换算法(页面淘汰算法页面淘汰算法)页面置换算法的

46、好坏极大地影响着系统性能。页面置换算法的好坏极大地影响着系统性能。抖动抖动(Thrashing)：由于页面置换算法选择不：由于页面置换算法选择不当而导致系统的页面置换调度非常频繁当而导致系统的页面置换调度非常频繁(如刚如刚换出的页立即又被换入换出的页立即又被换入)，使访问外存时间和，使访问外存时间和I/O处理时间大大增加，反而造成处理时间大大增加，反而造成CPU因等待因等待数据而空转，导致系统性能大大下降的现象。数据而空转，导致系统性能大大下降的现象。正确的置换出发点：正确的置换出发点：未来永远不再使用的页面。未来永远不再使用的页面。未来长期不会使用的页面。未来长期不会使用的页面。过去短期内较

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

48、先进先出(FIFO)页面置换算法页面置换算法当前所有内存页中最先进入内存的页面将被淘汰，简单，易实现。但缺页率偏高，性能较低。页面走向页面走向物理块数物理块数701203042303212017013块块置换？置换？置换率置换率缺页率缺页率707107210210321032403240324032032032103210210210721072107置换率置换率=12/20=60%缺页率缺页率=15/20=75%第四章 存储器管理 125最近最久未使用最近最久未使用(LRU)置换算法置换算法 1LRU(Least Recently Used)页面置换算法页面置换算法缺页率适中，性能较好，易于

49、实现但需硬件支持 页面走向页面走向物理块数物理块数701203042303212017013块块置换？置换？置换率置换率缺页率缺页率707107210021302032403240324032302230123213021102710071107置换率置换率=9/20=45%缺页率缺页率=12/20=60%第四章 存储器管理 126 思考：对同一个算法而言，是否分配给某思考：对同一个算法而言，是否分配给某进程的物理块数越多，则其缺页率越低？进程的物理块数越多，则其缺页率越低？答案：不是！答案：不是！Belay现象：分配给进程的物理块数增多，现象：分配给进程的物理块数增多，其缺页率反而上升的一种

50、现象。主要发生其缺页率反而上升的一种现象。主要发生在在FIFO算法。算法。第四章 存储器管理 127对对LRU的改进和简化的改进和简化 1简单的简单的Clock置换算法，又称置换算法，又称NRU(Not Recently Used)最近未用算法最近未用算法只关心该页是否使用过 2改进型改进型Clock置换算法置换算法最近未访问且未被修改过(最佳淘汰页)最近未访问但已被修改过最近已访问但未被修改过最近已访问且已被修改过(最差淘汰页)入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位为0否第四章 存储器管理 128 其它页面置换算法其它页面置换算法最少使用LFU(L

51、east Frequently Used)页面缓冲PBA(Page Buffering Algorithm)第四章 存储器管理 129请求分段存储管理方式请求分段存储管理方式(动态段式管理动态段式管理)请求分段中的硬件支持请求分段中的硬件支持 1段表机制段表机制在请求分段式管理中所需的主要数据结构是段表。由于在应用程序的许多段中，只有一部分段装入内存，其余的一些段仍留在外存上，故须在段表中增加若干项，以供程序在调进、调出时参考。段名段名段长段长 段的基址段的基址 存取方式存取方式 访问字段访问字段 修改位修改位 存在位存在位 增补位增补位 外存始址外存始址与静态段式管与静态段式管理中段名、段理

52、中段名、段长和段基址的长和段基址的作用相同作用相同执行执行/读读/写写属性属性被访问被访问的次数的次数或未被或未被访问的访问的时间时间该段在该段在内存中内存中是否被是否被修改过修改过该段该段是否是否已在已在内存内存中中该段该段是否是否动态动态增长增长过过该段该段在外在外存的存的起始起始地址地址第四章 存储器管理 130 2缺段中断机构缺段中断机构在指令执行期间，一旦发现要访问的段当前不在内存，则立即产生一次缺段中断，由缺段中断机构确保缺段中断及时、有效、安全地进行。第四章 存储器管理 131图4-32请求分段系统中的中断处理过程 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S

53、修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是第四章 存储器管理 132图4-33请求分段系统的地址变换过程 访问sww段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位1形成访问主存地址(A)(主存始址)(位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否 3地地址址变变换换机机构构第四章 存储器管理 133分段的共享与保护分段的共享与保护 1共享段表共享段表为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。段名段长内存始址 状态外存始址

54、共享进程计数count状态进程名 进程号段号存取控制共享段表图4-34共享段表项 第四章 存储器管理 134 2共享段的分配与回收共享段的分配与回收1)共享段的分配共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执

55、行count+操作，以表明有两个进程共享该段。2)共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放，包括撤消在该进程段表中共享段所对应的表项，以及执行count-操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，只是取消调用者进程在共享段表中的有关记录。第四章 存储器管理 135 3分段保护分段保护1)越界检查 段表寄存器中的段表长度以及段表中的各段段长。2)存取控制检查 只读、只执行、读/写。3)环保护机构 略。第四章 存储器管理 136页式与段式的优点缺点总结页式与段式的优点缺点总结页式

56、管理优点：实现了离散存储；有效解决了碎片问题；动态请求式分页管理可部分装入，支持虚存实现；提高了内存利用率，更有利于多道程序执行。缺点：要求相应硬件支持(地址变换机构、缺页中断机构和置换机构)；不便共享；增加了系统开销(缺页中断处理)；置换算法不当会产生抖动；仍存在页内碎片。段式管理优点：除了页式的优点之外，还有：段更有逻辑意义(一定程序上减少了缺段频率)；段长可动态增长；便于段的共享和保护；便于实现动态链接。缺点：更多的硬件支持；碎片问题比页式严重；合并或紧凑及动态增长都需更大开销；也可能出现抖动。第四章 存储器管理 137第四章作业（第四章作业（P159）第第6，10，14，17，18，22，26题题 其中第其中第26题要求分别用题要求分别用FIFO和和LRU算法来算法来做做