操作系统课件第4章.ppt

《操作系统课件第4章.ppt》由会员分享，可在线阅读，更多相关《操作系统课件第4章.ppt（191页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第四章存储器管理 第四章存储器管理 4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配方式连续分配方式4.4基本分页存储管理方式基本分页存储管理方式4.5基本分段存储管理方式基本分段存储管理方式4.6虚拟存储器的基本概念虚拟存储器的基本概念4.7请求分页存储管理方式请求分页存储管理方式4.8页面置换算法页面置换算法4.9请求分段存储管理方式请求分段存储管理方式 第四章存储器管理 在多道程序设计技术出现后，对存储管理提出了更高的要求。一方面，要使主存得到充分、有效地利用；另一方面又要为用户提供方便的使用环境。第四章存储器管理 4.1 存储器的层次结构

2、存储器的层次结构 4.1.1 4.1.1 多级存储器结构多级存储器结构对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器中间为主存最底层是辅存 根据具体的功能分工细划为:寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。第四章存储器管理 图4-1计算机系统存储层次示意快快慢慢第四章存储器管理 寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。第四章存储器管理 4.1.2 4.1.2 主存储器与寄存器主存储器与寄存器1 1主存储器主存储器

3、主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器，其容量对于当前的微机系统和大中型机，可能一般为数十MB到数GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十KB到几MB。CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。CPU与外围设备交换的信息一般也依托于主存储器地址空间。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。第四章存储器管理 2 2寄存器寄存器寄存器访问速度最快，完全能与CPU协调工作，但价

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

5、的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。第四章存储器管理 2 2磁盘缓存磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。主存也可以看做是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用；反之，数据也必须先存在主存中，才能输出到辅存。第四章存储器管理 4.1.4 4.1.4

6、 地址映射地址映射程序和数据必须装入内存，即要占用一定的内存空间才能执行和使用。暂时不执行或不用的程序和数据可放在外存中。CPU不能直接访问外存，需通过I/O设备实现内、外存信息交换。内存空间一般分为两部分：一部分是系统区，存放操作系统、标准子程序、例行程序和系统数据等；另一部分是用户区，用于存放用户的程序和数据等。第四章存储器管理 系统区系统区系统区系统区用户区用户区用户区用户区 内存分配示意图内存分配示意图内存分配示意图内存分配示意图存储管理主要是对用户区进行管理，其目的是充分利用内存，为多道程序并发执行提供存储基础，方便用户使用。第四章存储器管理 存储管理的功能:存储分配地址映射（逻辑地

7、址与物理地址的对应关系）存储保护内存扩充（虚拟存储器技术以及各种调度算法）第四章存储器管理 在多道程序设计的环境中:当有作业进入计算机系统时，存储管理应能根据当时的内存分配状况，按作业要求分配给它适当的内存。当某个作业完成不再使用内存时，应回收占用的内存空间，以便供其他用户使用。第四章存储器管理 物理地址和物理地址和逻辑逻辑地址地址1）内存空间主存储器以字节为编址单位，容量为n的主存储器中，每个单元有唯一的编号，分别为：0，1，2，n1，这个唯一的编号就是主存储器的物理地址（即绝对地址、实地址）。第四章存储器管理 内存地址的集合称为内存地址空间（或物理地址空间），简称内存空间（或物理空间），是

8、一维线性空间。例如，某个系统，有64kb内存，则其内存空间编号为：0，1，2，3，65535。第四章存储器管理 2）逻辑空间用汇编语言或高级语言编写程序时，常常用符号名来访问某一单元。把源程序中由符号名组成的程序空间称为符号名空间，简称名空间。源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址（或相对地址、虚地址）。第四章存储器管理 一个编译好的程序存在于它自己的逻辑空间中，运行

9、时，要把它装入内存空间，如图4.2所示,一个作业在编译前、编译后及装入内存后不同空间的情形。第四章存储器管理 1000b1100b1200b1299b0b100b200b299bMov R1,2006817Mov R1,data6817名名名名空间空间空间空间Mov R1,2006817 逻辑逻辑逻辑逻辑空间空间空间空间物理物理物理物理空间空间空间空间图图4.2 作业的名空间、逻辑空间和装入后的物理空间作业的名空间、逻辑空间和装入后的物理空间data:符号地址符号地址逻辑地址逻辑地址物理地址物理地址第四章存储器管理 由图4.2可以看出：该作业经过编译后，大小为300字节，逻辑地址空间为0299

10、。在作业的第100号单元处有指令 Mov Rl，200，即把200号单元内的数据6817送入寄存器Rl。假如把作业装入到内存第10001299号单元处。由图4.2可以看出，若只是简单地装入第10001299号单元，执行Mov Rl，200指令时，会把内存中200号单元的内容送入Rl，显然这样会出错。只有把1200单元的内容送入Rl才是正确的。所以作业装入内存时，需对指令和指令中相应的逻辑地址部分进行修改，才能使指令按照原有的逻辑顺序正确运行。第四章存储器管理 4.2程序的装入和链接程序的装入和链接 在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内

11、存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：首先是要编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(ObjectModule)；其次是链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(LoadModule)；最后是装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和装入过程。第四章存储器管理 图4-2对用户程序的处理步骤第四章存储器管理 4.2.14.2.1程序的装入程序的装入1 1绝对装入方式绝对装入方

12、式(Absolute Loading Mode)(Absolute Loading Mode)在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。例如，事先已知用户程序(进程)驻留在从R处开始的位置，则编译程序所产生的目标模块(即装入模块)便从R处开始向上扩展。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。第四章存储器管理 程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用

13、情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。第四章存储器管理 缺点：绝对装入方式只能将目标模块装入到内存中事先指定的位置。绝对装入方式只适用于单道程序环境。第四章存储器管理 2可重定位装入方式可重定位装入方式(Relocation Loading Mode)(静态重定位）在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。第四章存储器管理 图4-3作业装入

14、内存时的情况第四章存储器管理 例如，在用户程序的1000号单元处有一条指令LOAD1，2500，该指令的功能是将2500单元中的整数365取至寄存器1。但若将该用户程序装入到内存的1000015000号单元而不进行地址变换，则在执行11000号单元中的指令时，它将仍从2500号单元中把数据取至寄存器1而导致数据错误。由图4-3可见，正确的方法应该是将取数指令中的地址2500修改成12500，即把指令中的相对地址2500与本程序在内存中的起始地址10000相加，才得到正确的物理地址12500。除了数据地址应修改外，指令地址也须做同样的修改，即将指令的相对地址1000与起始地址10000相加，得到

15、绝对地址11000。通常是把在装入时对目标程序中指令和数据的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。第四章存储器管理 缺点：可重定位装入方式不允许程序运行时在内存中移动位置。第四章存储器管理 3 3动态运行时装入方式动态运行时装入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)因为，程序在内存中的移动，意味着它的物理位置发生了变化，这时必须对程序和数据的地址(是绝对地址)进行修改后方能运行。然而，实际情况是，在运行过程中它在内存中的位置可能经常要改变，此时就应采用动态运行时装入的方式

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

17、修改。在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的。在链接成一个装入模块后，原模块B和C在装入模块的起始地址不再是0，而分别是L和L+M，所以此时须修改模块B和C中的相对地址，即把原B中的所有相对地址都加上L，把原C中的所有相对地址都加上L+M。第四章存储器管理(2)变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址，如把B的起始地址变换为L，把C的起始地址变换为L+M，如图4-4(b)所示。这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。通常都不再拆开它，要运行时可直接将它装入内存。这种事先进行

18、链接，以后不再拆开的链接方式，称为静态链接方式。第四章存储器管理 图4-4程序链接示意图第四章存储器管理 2 2装入时动态链接装入时动态链接(Load-time Dynamic Linking)(Load-time Dynamic Linking)用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图4-4所示的方式来修改目标模块中的相对地址。装入时动态链接方式有以下优点：(1)便于修改和更新。对于经静态链接装配在一起的装入模块，如果要修改或更新其中的某个目标模块，则

19、要求重新打开装入模块。这不仅是低效的，而且有时是不可能的。若采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块是件非常容易的事。第四章存储器管理(2)便于实现对目标模块的共享。在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享。但采用装入时动态链接方式，OS则很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。第四章存储器管理 3 3运行时动态链接运行时动态链接(Run-time Dynamic Linking)(Run-time Dynamic Linking)这种链接方式是将对某些模块的链接推迟到程序执行时才进

20、行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。第四章存储器管理 4.3连续分配方式连续分配方式 4.3.14.3.1单一连续分配单一连续分配这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。第四章存储器管理 4.

21、3.24.3.2固定分区分配固定分区分配1 1划分分区的方法划分分区的方法可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：(1)分区大小相等，即使所有的内存分区大小相等。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合，因为这些对象所需的内存空间是大小相等的。例如，炉温群控系统，就是利用一台计算机去控制多台相同的冶炼炉。第四章存储器管理(2)分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点，可把内存区划分成含有多个较小的分区、适量的中等

22、分区及少量的大分区。这样，便可根据程序的大小为之分配适当的分区。第四章存储器管理 2 2内存分配内存分配为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图4-5(a)所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图4-5(b)所示。第四章存储器管理 图4-5固定分区使用表20第四章存储器管理 固定分区存储管理的最大的优点是简单，要求的硬件支

23、持少，软件算法也简单；缺点是容易产生内部碎片，即由于分区大小是事先固定的，因而可容纳作业的大小受到限制。而且当用户作业的地址空间小于分区的存储空间时，浪费了一些存储空间。第四章存储器管理 4.3.34.3.3动态分区动态分区(可变分区可变分区)分配分配与固定分区法相比，动态分区法在作业执行前并不建立分区，而是在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等能有效解决固定式分区的内部碎片问题，是一种较为实用的存储管理方法因为在系统运行过程中，内存中分区的数目和大小都是可变的，所以也叫可变分区第四章存储器管理 0k0k40k40k256k-1256k-1操作系统操作系统操作系统操

24、作系统 空空空空 闲闲闲闲 分分分分 区区区区（a a）可变式分区运行开始可变式分区运行开始可变式分区运行开始可变式分区运行开始0k0k40k40k86k86k118k118k156k156k196k196k256k-1256k-1操作系统操作系统操作系统操作系统作业作业作业作业1(46k)1(46k)作业作业作业作业2(32k)2(32k)作业作业作业作业3(38k)3(38k)作业作业作业作业4(40k)4(40k)空闲（空闲（空闲（空闲（60k60k）（b b）作业作业作业作业1 1、2 2、3 3、4 4进入内存进入内存进入内存进入内存0k0k40k40k86k86k118k118k1

25、56k156k196k196k256k-1256k-1操作系统操作系统操作系统操作系统空闲空闲空闲空闲1(46k)1(46k)作业作业作业作业2(32k)2(32k)空闲空闲空闲空闲2(38k)2(38k)作业作业作业作业4(40k)4(40k)空闲空闲空闲空闲3(60k)3(60k)（c c）作业作业作业作业1 1、3 3释放后内存释放后内存释放后内存释放后内存图图图图4.7 4.7 可变式分区内存使用情况示意图可变式分区内存使用情况示意图可变式分区内存使用情况示意图可变式分区内存使用情况示意图第四章存储器管理 如图4.7所示，假设某系统采用可变式分区存储管理，在系统运行的开始，存储区被分为

26、操作系统分区（40kb）和可分给用户的空闲区（216kb）。当作业1（46k）进入内存后，分给作业1（46k），随着作业2、3、4的进入，分别分配32k，38k，40k，经过一段时间的运行后，作业1、3运行完毕，释放所占内存。此时，作业5进入系统，要求分配36k内存，如何为作业5分配内存呢？第四章存储器管理 如图4.7（c）所示，此时，有三种方法可给作业5分配内存：从作业1释放的46k中，分36k给作业5，即分配空闲区1；从作业3释放的38k中，分36k给作业5，即分配空闲区2；从空闲的60k中，分36k给作业5，即分配空闲区3。到底采用到底采用到底采用到底采用哪种哪种哪种哪种分配方法呢分配方

27、法呢分配方法呢分配方法呢?这时，应考虑空闲分区的这时，应考虑空闲分区的这时，应考虑空闲分区的这时，应考虑空闲分区的组织形式组织形式组织形式组织形式和采用的和采用的和采用的和采用的内存分配算法内存分配算法内存分配算法内存分配算法。第四章存储器管理 1.1.空闲空闲分区的数据结构分区的数据结构在在可可变变式式分分区区存存储储管管理理中中，常常把把空空闲闲区区组组成成空空闲闲分分区区表表或或空闲分区链表空闲分区链表的形式。的形式。空空闲闲分分区区表表的的组组织织类类似似于于固固定定分分区区的的分分区区说说明明表表，包包含含空空闲闲分分区区的的起起始始位位置置和和大大小小，因因分分区区数数目目不不定定

28、，故故空空闲闲分分区表区表长度不定长度不定。采采用用空空闲闲分分区区表表要要占占用用一一定定数数量量的的存存储储单单元元存存放放此此表表 增加增加了系统的开销。了系统的开销。第四章存储器管理 空空闲闲分分区区链链表表的的组组织织是是这这样样的的：在在每每个个空空闲闲分分区区的的起起始始部部分分开开辟辟出出一一个个单单元元，存存放放一一个个链链表表指指针针和和该该分分区区的的大大小小，链表指针指向链表指针指向下一个下一个空闲分区。空闲分区。系系统统中中用用一一个个固固定定单单元元作作为为空空闲闲分分区区链链表表的的链链表表头头指指针针，指指向向第第一一块块空空闲闲分分区区首首地地址址，最最后后一

29、一块块空空闲闲分分区区的的链链表表指指针针存放链尾标志存放链尾标志。因因空空闲闲分分区区链链表表组组织织时时，空空闲闲区区的的信信息息放放在在空空闲闲区区内内，因此因此不会额外增加不会额外增加系统的开销。系统的开销。所以所以使用比较广泛使用比较广泛的是空闲分区的链表组织形式。的是空闲分区的链表组织形式。30 k 100 30 k 100 10 k10 k 120 120 15 k15 k 80 80 20 k20 k 505050 120 8050 120 80第四章存储器管理（1 1）首次适应算法首次适应算法思思想想是是:把把空空闲闲分分区区按按其其所所在在存存储储空空间间中中地地址址递递增

30、增的的顺顺序序连接在一起。连接在一起。当当用用户户申申请请一一内内存存存存储储空空间间时时，从从空空闲闲区区链链表表的的头头指指针针开始查找，选择开始查找，选择第一个第一个满足要求的空闲分区。满足要求的空闲分区。算法算法如如图图4.94.9所示。所示。30 k 100 30 k 100 30 k30 k 100 100 15 k15 k 200 200 20 k20 k 505050 100 20050 100 2002 2.常用的分配算法常用的分配算法第四章存储器管理 优点：该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造

31、了条件。缺点：低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。第四章存储器管理(2)循环首次适应算法该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应

32、调整起始查寻指针。第四章存储器管理 优点：该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销缺点：但这样会缺乏大的空闲分区。第四章存储器管理（3 3）最佳适应算法）最佳适应算法这种算法把空闲分区链表按这种算法把空闲分区链表按分区大小分区大小由小到大由小到大进行组织。进行组织。当当有有作作业业申申请请内内存存时时，总总是是首首先先找找到到满满足足要要求求的的最最接接近近作作业大小的空闲分区。业大小的空闲分区。此算法此算法最节约空间最节约空间，因为它尽量不分割大的空闲区。，因为它尽量不分割大的空闲区。30 k 100 30 k 100 30 k30 k 180 180 40 k

33、40 k 100 100 50 k50 k 505050 180 10050 180 100第四章存储器管理 缺点：孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区(外部碎片)。第四章存储器管理（4 4）最最坏适应算法坏适应算法这这种种算算法法要要求求把把空空闲闲区区按按分分区区大大小小递递减减的的顺顺序序组组织织成成空闲区链表。空闲区链表。当当用用户户申申请请一一个个存存储储区区时时，总总是是检检查查空空闲闲区区链链表表的的第第一个空闲区是够满足要求，一个空闲区是够满足要求，n n若不满足，分

34、配若不满足，分配失败失败；n n若若满满足足，则则将将空空闲闲区区分分配配给给用用户户，然然后后修修改改和和调调整整空空闲区链表。闲区链表。30 k 100 30 k 100 50 k50 k 300 300 40 k40 k 150 150 30 k30 k 707070 300 15070 300 150第四章存储器管理 该算法的该算法的优优点是：可以避免形成碎片；点是：可以避免形成碎片；缺缺点点是是：它会使存储器中缺乏大的空闲分区，分分割割大大的的空闲区后，再遇到较大的申请时，无法满足的可能性较大。空闲区后，再遇到较大的申请时，无法满足的可能性较大。第四章存储器管理(5)快速适应算法该算

35、法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2KB、4KB、8KB等，对于其它大小的分区，如7KB这样的空闲区，既可以放在8KB的链表中，也可以放在一个特殊的空闲区链表中。第四章存储器管理 优点：查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何

36、分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。缺点：分区归还主存时算法复杂，系统开销较大。该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此存在一定的浪费。第四章存储器管理 3 3分区分配操作分区分配操作1)分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出

37、一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图4-7示出了分配流程。第四章存储器管理 第四章存储器管理 2)回收内存当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：(1)回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。(2)回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。第

38、四章存储器管理(3)回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。(4)回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。第四章存储器管理 图4-8内存回收时的情况第四章存储器管理 动态分区存储管理的主要优缺点优点优点：有有效效地地解解决决了了固固定定式式分分区区的的内内部部碎碎片片问问题题，较较有有效效地地利用主存空间，提高了多个作业或进程对内存的共享。利用主存空间，提高了多个作业或进程对内存的共享。缺点缺点缺点缺点：容

39、易容易容易容易产生外部碎片产生外部碎片产生外部碎片产生外部碎片问题，为解决外部碎片问题，可采用问题，为解决外部碎片问题，可采用问题，为解决外部碎片问题，可采用问题，为解决外部碎片问题，可采用紧凑技术，但花费大量处理机时间。紧凑技术，但花费大量处理机时间。紧凑技术，但花费大量处理机时间。紧凑技术，但花费大量处理机时间。第四章存储器管理 4.3.44.3.4伙伴系统伙伴系统固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的

40、一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。第四章存储器管理 假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。第四章存储器管理 当需要为进程分配一个长度为n的存储空间时，首先计

41、算一个i值，使2i1n2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i1的空闲分区链表中寻找。若存在2i1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i1的空闲分区也不存在，则需要查找大小为2i2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i1的两个分区，一个用于分配，一个加入到大小为2i1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分

42、配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。第四章存储器管理 与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i1的空闲分区，若事先已存在2i1的空闲分区时，又应继续与其伙伴分区合并为大小为2i2的空闲分区，依此类推。在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收

43、空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。第四章存储器管理 4.3.64.3.6可重定位分区分配可重定位分区分配1 1动态重定位的引入动态重定位的引入在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。例如，图4-9(a)中示出了在内存中现有四个互不邻接的小分区，它们的容量分别为10KB、30KB、14KB和26KB，其总容量是80KB。但如果现在有一作

44、业到达，要求获得40KB的内存空间，由于必须为它分配一连续空间，故此作业无法装入。这种不能被利用的小分区称为“零头”或“碎片”。第四章存储器管理 图4-9紧凑的示意第四章存储器管理 若想把作业装入，可采用“拼接”或“紧凑”技术：将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区，即通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。第

45、四章存储器管理 2 2动态重定位的实现动态重定位的实现在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。第四章存储器管理 图4-10动态重定位示意图第四章存储器管理 程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。图4-10示出了动态重定位的实现原理。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当

46、系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。第四章存储器管理 3 3动态重定位分区分配算法动态重定位分区分配算法动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。图4-11示出了动态重定位分区分配算法。第四章存储器管理 图4-11动态分区分配算法流程图第四章存储器管理 4.3.74.3.7对换对换1 1对换对换(Swapping)(Swapping)的引入的引入在多道程序环境下，会出现以下情况

47、：一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。为了解决这一问题，在系统中又增设了对换(也称交换)设施。第四章存储器管理 所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。第四章存储器管理 如果对换是以整个进程为单

48、位的，便称之为“整体对换”或“进程对换”。这种对换被广泛地应用于分时系统中，其目的是用来解决内存紧张问题，并可进一步提高内存的利用率。如果对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。这种对换方法是实现后面要讲到的请求分页和请求分段式存储管理的基础，其目的是为了支持虚拟存储系统。在此，我们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进程的换出，以及进程的换入。第四章存储器管理 2 2对换空间的管理对换空间的管理在具有对换功能的OS中，通常把外存分为文件区和对换区：文件区

49、用于存放文件，由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。对换区用于存放从内存换出的进程。进程在对换区中驻留的时间是短暂的，对换操作又较频繁，故对对换空间管理的主要目标，是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。第四章存储器管理 对对换区中的空闲盘块进行管理数据结构，其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，分别用盘块号和盘块数表示。第四章存储器管理 3 3进程的换出与

50、换入进程的换出与换入(1)进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。(2)进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久(换出到磁盘上)的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。第四章存储器管理 4.4 基本分页存储管理方式目前已讨论了