存储管理ppt课件.pptx

目录目录41 存储管理的目的和功能42 存储分配4.3 重定位44 实存管理技术45 虚存管理技术n存储器是计算机系统的重要资源之一。计算机系统的存储器可以分成两类：主存储器（简称主存或内存）和辅助存储器（简称辅存或外存）。计算机的中央处理器可以直接从主存中存取指令和数据，主存容量的大小是计算机系统的一个重要性能指标。41 存储管理的目的和功能存储管理的目的和功能n n主主存存空空间间分分为为两两部部分分：系系统统区区和和用用户户区区。系系统统区区用用来来存存放放操操作作系系统统与与硬硬件件的的接接口口信信息息（例例如如，新新旧旧处处理理机机状状态态字字、定定时时时时间间、外外围围设设备备的的工工作作情情况况等等）、操操作作系系统统的的管管理理信信息息（例例如如，进进程程的的PCBPCB）和和程程序序、标标准准子子程程序序等等。其其余余的的存存储储空空间间都都属属于于用用户户区区，用用来来存存放放用用户户的的程程序序和和数数据据。存存储储管管理理就就是是对对主主存存空空间间的的用用户户区区进进行行管管理理，其其目的和功能如下：目的和功能如下：n n(1)(1)对主存空间进行分配和管理对主存空间进行分配和管理n n(2)(2)提高主存的利用率提高主存的利用率 n n(3)(3)“扩充扩充”主存容量主存容量n n(4)(4)实现地址的变换实现地址的变换42 存储分配存储分配n n所谓存储分配就是要解决多道作业之间划所谓存储分配就是要解决多道作业之间划分主存空间的问题。通常将存储器分为两分主存空间的问题。通常将存储器分为两级，即主存和辅存。因此，存储分配要确级，即主存和辅存。因此，存储分配要确定在什么时候把哪些信息放在哪一级存储定在什么时候把哪些信息放在哪一级存储器上，而这些对用户来讲都是器上，而这些对用户来讲都是“透明透明”的的（即不需要用户知道）。系统中有一个存（即不需要用户知道）。系统中有一个存储分配程序，它依照一定的算法实现内存储分配程序，它依照一定的算法实现内存分配。分配。n常用的主存分配有三种方式:n静态分配静态分配n直接方式直接方式n动态分配动态分配n n直接方式直接方式n n直接方式是早期的计算机所使用的一种直接方式是早期的计算机所使用的一种方式。当时多道程序技术还没有出现，方式。当时多道程序技术还没有出现，存储器的可用空间一般是给定的。那时存储器的可用空间一般是给定的。那时程序员在编程序时或编译程序对源程序程序员在编程序时或编译程序对源程序进行编译时，使用实际的存储器地址，进行编译时，使用实际的存储器地址，这种分配方式使用户与计算机内存直接这种分配方式使用户与计算机内存直接打交道，系统资源在某一时刻为一个用打交道，系统资源在某一时刻为一个用户所独占。户所独占。n静态分配静态分配n静态分配是在装入程序把一个静态分配是在装入程序把一个或一组目标模块进行链接装入或一组目标模块进行链接装入内存时就确定它们在主存的相内存时就确定它们在主存的相对位置。作业一旦进入主存后，对位置。作业一旦进入主存后，在运行过程中就不能在主存空在运行过程中就不能在主存空间中间中“搬家搬家”（或移动）。（或移动）。n n动态分配动态分配n n作业在存储空间的位置也是装入时确定作业在存储空间的位置也是装入时确定的，但在作业运行的过程中，允许它在的，但在作业运行的过程中，允许它在存储空间中存储空间中“搬家搬家”（也称为允许浮动（也称为允许浮动或移动），而且也允许作业临时申请附或移动），而且也允许作业临时申请附加的存储空间。加的存储空间。n n目前绝大多数计算机系统采用动态或静目前绝大多数计算机系统采用动态或静态存储分配策略，这是由于计算机硬件态存储分配策略，这是由于计算机硬件和程序设计技术的发展等方面的原因。和程序设计技术的发展等方面的原因。4.3 重定位重定位n n在多道程序环境中，各用户作业独立编程，单独编译，它们装入系统的时间也不同，因此，只有在装入时才确定存储分配问题，而在编译时是不需要考虑的，即采用动态分配或静态分配方式。为了实现这两种分配策略，则必须把逻辑地址与物理地址分开，对逻辑地址采用地址重定位技术。n n名字空间名字空间n n当用户在使用汇编语言或高级语言当用户在使用汇编语言或高级语言编写程序时，是通过符号名来访问编写程序时，是通过符号名来访问子程序和数据的。我们把程序中符子程序和数据的。我们把程序中符号名的集合称为号名的集合称为“符号名空间符号名空间”或或“名空间名空间”。符号名空间是用户所。符号名空间是用户所编写的源程序所限定的空间，源程编写的源程序所限定的空间，源程序存在的地址范围称之为名字空间。序存在的地址范围称之为名字空间。n n地址空间地址空间 n n汇编语言源程序经过汇编，或者高级语言源程序经过编译所得到的目标程序是以“0”作为参考（或相对）地址的程序。这个相对地址的目标程序是由多个目标模块由链接程序链接而成的一个具有统一地址的装配模块，以便最后装入内存运行。我们把目标模块中的地址称为逻辑地址，而把逻辑地址的集合称为地址空间。地址空间是一个目标程序所限定的地址范围。n存储空间存储空间 n主存中一系列存储信息的物理单元的集合称为存储空间。单元编号称为物理地址或绝对地址。一个计算机系统的存储空间的大小是由主存实际容量决定的。所以说：地址空间是逻辑地址的集合，存储空间是物理地址的集合，前者是“虚”的概念；后者是“实”的物体。n一个编译好的程序存在于它自己的地址空间中，当它要被运行时才装入到存储空间。程序的名字空间、地址空间、和存储空间是三个很重要的概念，理解他们对于理解下面的重定位很有帮助。n n地址重定位地址重定位地址重定位地址重定位 n n一个编译好的程序要在计算机上运行时，首先一个编译好的程序要在计算机上运行时，首先应将其指令和数据装入主存的某个区域或某几应将其指令和数据装入主存的某个区域或某几个区域，也就是说要进行存储分配。一般情况个区域，也就是说要进行存储分配。一般情况下，作业分配到的存储空间和它的地址空间是下，作业分配到的存储空间和它的地址空间是不一致的。当一个作业分配到的存储空间和它不一致的。当一个作业分配到的存储空间和它的地址空间不一致时，引起对有关地址部分的的地址空间不一致时，引起对有关地址部分的调整过程称之为调整过程称之为“地址重定位地址重定位”。或也称为。或也称为“地址变换地址变换”，它是将一个作业在地址空间中使，它是将一个作业在地址空间中使用的逻辑地址变换成主存中的物理地址的过程用的逻辑地址变换成主存中的物理地址的过程（有的也称为（有的也称为“地址映射地址映射”）。）。nn 假设用户作业的逻辑地址空间从假设用户作业的逻辑地址空间从0 0到到600600字节，字节，其中在第其中在第100100字节处有一条字节处有一条“装入装入”指令，该指令，该指令要求从第指令要求从第500500字节处取出操作数字节处取出操作数1234512345，并，并装入第装入第1 1号寄存器中。如果存储管理为该作业号寄存器中。如果存储管理为该作业分配的主存区域是从分配的主存区域是从10001000字节开始，那么，逻字节开始，那么，逻辑地址第辑地址第100100字节的指令被放在主存中的对应字节的指令被放在主存中的对应位置是位置是11001100字节的位置，逻辑地址第字节的位置，逻辑地址第500500字节中字节中的数据就被放在主存的的数据就被放在主存的15001500字节处。见下图字节处。见下图（a a）所示。如果不修改上述）所示。如果不修改上述“装入装入”指令中指令中的操作数地址的操作数地址500500，则处理器执行该指令时将，则处理器执行该指令时将从主存的从主存的500500字节中去取操作数，这显然是错字节中去取操作数，这显然是错误的。于是，应把程序中所有逻辑地址都转换误的。于是，应把程序中所有逻辑地址都转换成物理地址。上述装入指令中的操作数地址也成物理地址。上述装入指令中的操作数地址也相应改为相应改为15001500字节。这样，在执行指令时便可字节。这样，在执行指令时便可从从15001500字节处准确地取出操作数字节处准确地取出操作数1234512345。由此看。由此看来，重定位是必不可少的处理过程。来，重定位是必不可少的处理过程。主存空间地址空间6005001000LOAD 1,5001 2 3 4 5200050001600150011001000LOAD 1,5001 2 3 4 5(a)地址空间与主存空间关系主存空间地址空间6005001000LOAD 1,5001 2 3 4 5200001600150011001000LOAD 1,15001 2 3 4 5(b)静态重定位 地址空间与主存空间和静态重定位n n 重定位类型重定位类型 n n重定位（地址变换）在什么时候进行？用什么方法实现？这就是我们在此要讨论的问题。按照重定位的时间，可以将重定位分为静态重定位和动态重定位两种类型。n n静态重定位n n动态重定位n n静态重定位n n在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在作业开始执行前集中一次完成的，所以在作业执行过程中就无需再进行地址转换工作，这种地址转换方式称“静态重定位”。n n在上图（在上图（b b）中，仍假设用户作业的逻辑地址）中，仍假设用户作业的逻辑地址空间从空间从0 0到到600600字节，其中在第字节，其中在第100100字节处有一条字节处有一条装入指令：装入指令：LOAD 1,500LOAD 1,500”，该指令要求从第，该指令要求从第500500字节处取出操作数字节处取出操作数1234512345，然后装入第，然后装入第1 1号寄存号寄存器中。如果存储管理为该作业分配的主存区域器中。如果存储管理为该作业分配的主存区域是从是从10001000字节开始，那么，逻辑地址第字节开始，那么，逻辑地址第100100字节字节的指令被放在主存中的对应位置是的指令被放在主存中的对应位置是11001100字节的字节的位置，逻辑地址第位置，逻辑地址第500500字节中的数据就被放在字节中的数据就被放在主存的主存的15001500字节处。于是，采用静态重定位时，字节处。于是，采用静态重定位时，应把程序中所有逻辑地址都转换成绝对地址。应把程序中所有逻辑地址都转换成绝对地址。上述装入指令中的操作数地址也应改为上述装入指令中的操作数地址也应改为15001500字字节。这样，在执行指令时便可从节。这样，在执行指令时便可从15001500字节处准字节处准确地取到操作数确地取到操作数1234512345。n n静态重定位是由专门的重定位装入程序完成的，因此，它是由软件来实现的，无需专门的硬件地址变换机构的支持，因而可在一般的机器上实现。但是也存在着明显的缺点，由于静态重定位是在装入程序将作业装入主存时就完成了地址变换，则一个程序经过静态重定位而被装入内存后，就不能在内存中移动，而且要求程序在内存中是连续的存放，还要求程序本身是可以重定位的。n n动态重定位n n动态重定位是指在程序执行过程中，当访问指令或数据时才进行的地址变换方式。动态重定位可使地址空间中的信息不加任何修改就装入内存，在执行指令时才对相应的地址进行调整。它的实现需要专门的硬件重定位寄存器的支持才能完成。下图给出了动态重定位的示意图。n n由此可见，动态重定位是在指令执行过程中动态进行由此可见，动态重定位是在指令执行过程中动态进行的，这样做可以带来两点好处：的，这样做可以带来两点好处：n n(1)(1)目标程序装入内存时无需作任何修改，所以，在程目标程序装入内存时无需作任何修改，所以，在程序装入内存之后再移动也不会影响其正确运行（因为序装入内存之后再移动也不会影响其正确运行（因为这时只需修改重定位寄存器中的值即可），这就便于这时只需修改重定位寄存器中的值即可），这就便于用拼接的办法来紧缩内存以解决存储器的碎片问题，用拼接的办法来紧缩内存以解决存储器的碎片问题，使主存的使用更加灵活、有效。使主存的使用更加灵活、有效。n n(2)(2)一个程序由若干个相对独立的目标模块组成时，每一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以个目标模块各装入一个存储区域，这些存储区域可以是不相邻接的，只要各个模块有自己对应的重定位寄是不相邻接的，只要各个模块有自己对应的重定位寄存器就可以了。存器就可以了。n n动态重定位的缺点是动态重定位的缺点是“必须有相应的硬件支持，实现必须有相应的硬件支持，实现存储管理的软件算法也比静态重定位复杂。存储管理的软件算法也比静态重定位复杂。44 实存管理技术实存管理技术441 单一连续分区分配方式442 分区式分配443 覆盖与交换444 分页存储管理441 单一连续分区分配方式单一连续分区分配方式 这是一种最简单的存储管理方式，在早期的单道这是一种最简单的存储管理方式，在早期的单道批处理系统的小型机中常使用这种管理方案。采批处理系统的小型机中常使用这种管理方案。采用这种管理方案时，内存被分成两个区域，一个用这种管理方案时，内存被分成两个区域，一个是系统区域，仅供操作系统使用，通常设置在内是系统区域，仅供操作系统使用，通常设置在内存的低段；另一个是用户区，它是除系统区以外存的低段；另一个是用户区，它是除系统区以外的全部内存区域，这部分区域是提供给用户使用的全部内存区域，这部分区域是提供给用户使用的区域，任何时刻主存储器中最多只有一个作业。的区域，任何时刻主存储器中最多只有一个作业。所以，单一连续区存储管理只适用于单用户的情所以，单一连续区存储管理只适用于单用户的情况。况。441 单一连续分区分配方式单一连续分区分配方式 单一连续区的存储管理入口作业大小主存可用空间？给作业分配主存空间装入运行该作业输出结果信息调另一个作业本次无法运行此作业否是n n此系统的特点是：n n记住存储器的状态容易，不是全部空闲就是全部已分配；n n当作业被调度时就获得全部空间；n n全部主存空间都分配给一个作业；n n作业运行完后，全部主存空间又恢复成空闲。（以上所指的全部主存空间是全部用户区空间）n n特点：任一时刻内存只有一道作业，该任一时刻内存只有一道作业，该作业连续存放于内存中。作业连续存放于内存中。管理方法内存空间安排内存空间安排操作系统操作系统用户程序用户程序a aa+1a+1n n界地址寄存器界地址寄存器n n越界检查机构：用户程序每访问一次主用户程序每访问一次主存，越界检查机构将访问的地址与界地存，越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止址寄存器中的值比较。若越界，则终止其执行。其执行。界地址寄存器界地址寄存器主存主存A Aa acpucputruetruefalsefalse地址地址A A终止程序运行终止程序运行n n 计算机的状态分为：计算机的状态分为：CPUCPU管理方式和用户管理管理方式和用户管理方式两种，我们把方式两种，我们把CPUCPU管理方式叫做计算机在管理方式叫做计算机在管态下工作；用户管理方式叫做计算机在目态管态下工作；用户管理方式叫做计算机在目态下工作。如果计算机在目态下工作，对内存访下工作。如果计算机在目态下工作，对内存访问时硬件均进行校验，以保证保护区不被访问，问时硬件均进行校验，以保证保护区不被访问，如果出现这种访问则产生中断，控制权交给操如果出现这种访问则产生中断，控制权交给操作系统；在管态下，操作系统能访问整个存储作系统；在管态下，操作系统能访问整个存储空间。仅当控制权交给操作系统时，空间。仅当控制权交给操作系统时，CPUCPU才由才由目态变为管态。因此说，目态是用户工作方式，目态变为管态。因此说，目态是用户工作方式，而管态是管理工作方式。而管态是管理工作方式。n n单一连续区分配算法简单，操作系统也比较小，因而单一连续区分配算法简单，操作系统也比较小，因而了解使用这样的系统很容易，不需要很多经验。但这了解使用这样的系统很容易，不需要很多经验。但这种管理方案太简单以至于使得：种管理方案太简单以至于使得：n n(1)(1)存储器没有得到充分利用，往往是浪费了一部分或存储器没有得到充分利用，往往是浪费了一部分或大部分。因为，作业的大小与存储器的可用空间的大大部分。因为，作业的大小与存储器的可用空间的大小不一定一致。而且是作业的全部信息都装入主存，小不一定一致。而且是作业的全部信息都装入主存，有的信息从未使用过也白白占用了主存空间。有的信息从未使用过也白白占用了主存空间。n n(2)(2)处理机的利用率较低，因为是单道处理，一旦一个处理机的利用率较低，因为是单道处理，一旦一个作业提出作业提出I/OI/O请求则请求则 CPUCPU空闲。空闲。n n(3)(3)作业的周转时间长，当一个大作业装入系统运行后，作业的周转时间长，当一个大作业装入系统运行后，新进入系统的小作业也必须等待大作业运行完成后才新进入系统的小作业也必须等待大作业运行完成后才能装入运行。能装入运行。n n(4)(4)缺乏灵活性，要求作业的地址空间小于等于主存可缺乏灵活性，要求作业的地址空间小于等于主存可用空间，否则此作业不采用覆盖技术（虚拟存储技术）用空间，否则此作业不采用覆盖技术（虚拟存储技术）就无法运行。就无法运行。442 分区式分配分区式分配n n分区式分配是能满足多道程序设计的最简单的存储管理技术，它允许几个作业共享主存空间，这几个作业被装入不同的分区中，每个分区可用来装入一个作业。n n分区式分配又分为：固定式分区、可变式分区、可重定位分区和多重分区四种管理方案。1.固定式分区n n实现原理n n固定式分区是在处理作业之前存储器就已经被划分成为若干个分区，每个分区的大小可以相同，也可以不同。但是，一旦划分好分区后，主存储器中的分区的个数就固定了，且每个分区的大小也固定不变。n n硬件支持n n采用这种存储管理方案只需很少一点专用硬件-存储保护机构，以防止某一个作业干扰或破坏操作系统和其他作业。有两种实现方法：其一，使用两个界限寄存器框住正在使用的内存区域，但是这样做很麻烦，每当重新分配处理机时都得修改界限寄存器的内容。其二，为每个分区配上一个单独的保护锁，程序状态字中有一把钥匙，根据锁和钥匙相匹配的方法来实现存储保护。n n软件算法软件算法n n这种分区方式一般将内存的用户区分成大小不这种分区方式一般将内存的用户区分成大小不等（也可以分成大小相等）的分区，以适应不等（也可以分成大小相等）的分区，以适应不同大小的作业的需要。系统中有一张分区说明同大小的作业的需要。系统中有一张分区说明表简称为分区表，每个表目记录一个分区的大表简称为分区表，每个表目记录一个分区的大小、起始地址和分区的状态，当系统为某个作小、起始地址和分区的状态，当系统为某个作业分配主存空间时，根据所需要的内存容量，业分配主存空间时，根据所需要的内存容量，在分区表中找到一个足够大的空闲分区分配给在分区表中找到一个足够大的空闲分区分配给它，然后将此作业装入内存。如果找不到足够它，然后将此作业装入内存。如果找不到足够大的空闲分区则这个作业暂时无法分配内存空大的空闲分区则这个作业暂时无法分配内存空间，系统将调度另一个作业。间，系统将调度另一个作业。n n可变式分区可变式分区可变式分区可变式分区n n实现原理实现原理n n可变式分区是指在作业执行之前并不建立分可变式分区是指在作业执行之前并不建立分区，分区的建立是在处理作业的过程中进行区，分区的建立是在处理作业的过程中进行的，而且分区的大小可以按作业或进程对内的，而且分区的大小可以按作业或进程对内存的需求而改变。在系统初启时除了操作系存的需求而改变。在系统初启时除了操作系统中常驻内存的部分以外，给用户只提供一统中常驻内存的部分以外，给用户只提供一个空闲分区，即整个用户区。当作业装入主个空闲分区，即整个用户区。当作业装入主存时，从空闲区中划分出一块连续的区域分存时，从空闲区中划分出一块连续的区域分配给该作业，该区域就变成了已分配区域，配给该作业，该区域就变成了已分配区域，也就建立了一个分区。若还有作业要求运行，也就建立了一个分区。若还有作业要求运行，则继续将空闲区依次分配给各个作业，即在则继续将空闲区依次分配给各个作业，即在内存中建立了若干个与作业大小相等的分区内存中建立了若干个与作业大小相等的分区了了 。n n为了实现这种管理方案，使用已分配区状态表和空闲区表来记录内存的使用情况。n n表表4-3已分配区状态表已分配区状态表n n 区号 大小（k）位置 状态n n 1 8 312 已分配n n 2 32 320 已分配n n 3空白n n 4 120 384 已分配n n 5空白n n表表4-4空闲区表空闲区表n n空闲区 大小(k)位置 状态n n 1 32 352 可用 n n 2 520 504 可用n n 3空白n n 4空白n n空表目n n从上述两个表中可以看出，系统已经为三个作业分配了主存空间，内存被划分为三个分区，如下图（a）所示。现又有作业4（大小为24k）、作业5（大小为128k）和作业6（大小为256k）欲加入多道运行，在空闲区表中找到能容纳这三个作业的空闲区进行分配。分配后的主存分区情况如下图（b）所示。又过了一段时间作业2与作业3运行结束，主存的分区情况又发生了变化，如下图（c）所示。n n可变式分区分配与回收算法比较简单，分配时，可变式分区分配与回收算法比较简单，分配时，首先找到一个足够大的空闲区，即在空闲区中首先找到一个足够大的空闲区，即在空闲区中找到一个足以容纳该作业的可用空闲区，如果找到一个足以容纳该作业的可用空闲区，如果这个空闲区比所要求的大的较多，则将其分为这个空闲区比所要求的大的较多，则将其分为两部分，一部分分给作业，另一部分仍为空闲两部分，一部分分给作业，另一部分仍为空闲区，然后修改已分配区状态表和空闲区表，回区，然后修改已分配区状态表和空闲区表，回收时，须检查回收分区是否邻接空闲区，如邻收时，须检查回收分区是否邻接空闲区，如邻接空闲区则要进行合并，使之成为一个较大的接空闲区则要进行合并，使之成为一个较大的空闲区。然后也相应地修改已分配分区状态表空闲区。然后也相应地修改已分配分区状态表和空闲区表。和空闲区表。n n回收分区邻接空闲区的情况有三种：回收分区邻接空闲区的情况有三种：n n 回收分区回收分区R R与上面的空闲区与上面的空闲区F1F1邻接，如下图（邻接，如下图（a a）所）所示，这时应将回收分区与上面的空闲区合并成一个空示，这时应将回收分区与上面的空闲区合并成一个空闲区，原空闲区闲区，原空闲区F1F1的始址不变，只改变其大小。的始址不变，只改变其大小。n n 回收分区回收分区R R与下面的空闲区与下面的空闲区F2F2相邻接，如下图（相邻接，如下图（b b）所示，这时也应该将其合并成为一个较大的空闲区，所示，这时也应该将其合并成为一个较大的空闲区，但原空闲区的始址和大小都要改变。但原空闲区的始址和大小都要改变。n n 回收分区回收分区R R的上、下都邻接着空闲区的上、下都邻接着空闲区F1F1和和F2F2，此时，此时应该撤销下面的空闲区应该撤销下面的空闲区F2F2，只保留上面的那个空闲区，只保留上面的那个空闲区F1F1，其始址不变，它的大小等于原上面的空闲区，其始址不变，它的大小等于原上面的空闲区F1F1与与回收分区回收分区R R和下面的空闲区和下面的空闲区F2F2三者之和，如下图（三者之和，如下图（c c）所示。所示。n n若回收分区的上、下都无空闲区邻接，这时，若回收分区的上、下都无空闲区邻接，这时，应该在空闲区表或空闲区链中增加一个登记表应该在空闲区表或空闲区链中增加一个登记表目，表明又增加一个空闲区。目，表明又增加一个空闲区。n n上面所提到的用表格记录存储器使用状态的方上面所提到的用表格记录存储器使用状态的方法具有如下的缺点：法具有如下的缺点：n n 检查回收分区是否邻接着空闲区比较麻烦，检查回收分区是否邻接着空闲区比较麻烦，因为要查遍整个未分配分区表。因为要查遍整个未分配分区表。n n 已分配分区表和未分配分区表中的表目数取已分配分区表和未分配分区表中的表目数取决于某一时刻分区个数和空闲区的个数，因而决于某一时刻分区个数和空闲区的个数，因而表目数是不固定的，且每个分区的大小也是变表目数是不固定的，且每个分区的大小也是变化的。但是必须有足够多的空表目，用以登记化的。但是必须有足够多的空表目，用以登记新装入主存的作业占用的分区和作业撤离后的新装入主存的作业占用的分区和作业撤离后的空闲区。空闲区。n n可变式分区的管理算法可变式分区的管理算法 n n首次适应算法首次适应算法n n首次适应算法也叫作最先适应算法。这种算首次适应算法也叫作最先适应算法。这种算法在每次分配分区时，操作系统顺序查找空法在每次分配分区时，操作系统顺序查找空闲区表，把最先能够满足要求的空闲区进行闲区表，把最先能够满足要求的空闲区进行分割，这个空闲区的一部分分配给作业，另分割，这个空闲区的一部分分配给作业，另一部分仍为空闲区。一部分仍为空闲区。n n可把空闲区按照地址顺序从小到大登记在空可把空闲区按照地址顺序从小到大登记在空闲区表中。于是，在分配时总是尽量利用低闲区表中。于是，在分配时总是尽量利用低地址部分的空闲区，而使高地址部分有较大地址部分的空闲区，而使高地址部分有较大的空闲区，有利于大作业的装入。的空闲区，有利于大作业的装入。n n最佳适应算法最佳适应算法n n最佳适应算法总是按作业要求选择一个能满最佳适应算法总是按作业要求选择一个能满足作业要求的最小空闲区，这个最小空闲区足作业要求的最小空闲区，这个最小空闲区应该是所有空闲区中最合适的一个，这样就应该是所有空闲区中最合适的一个，这样就保证不会去分割一个更大的区域，使大的作保证不会去分割一个更大的区域，使大的作业比较容易得到满足。通常在实现这种算法业比较容易得到满足。通常在实现这种算法时，可按空闲区从小到大顺序登记在空闲区时，可按空闲区从小到大顺序登记在空闲区表或空闲区链中，分配时，顺序查找空闲区表或空闲区链中，分配时，顺序查找空闲区表或空闲区链，由于查找时每次总是从最小表或空闲区链，由于查找时每次总是从最小的一个空闲区开始，所以，当能够找到第一的一个空闲区开始，所以，当能够找到第一个满足作业要求的空闲区时，则一定是所有个满足作业要求的空闲区时，则一定是所有能满足作业要求的空闲区中的最小的（也是能满足作业要求的空闲区中的最小的（也是最合适的）一个空闲分区。最合适的）一个空闲分区。n n最坏适应算法最坏适应算法n n最坏适应分配算法总是挑选一个最大的空闲最坏适应分配算法总是挑选一个最大的空闲区分割一部分给作业使用，这样使剩余部分区分割一部分给作业使用，这样使剩余部分空闲区不致于太小，则就可以被再利用而分空闲区不致于太小，则就可以被再利用而分配给其他作业，这种分配算法对中小型作业配给其他作业，这种分配算法对中小型作业是有利的。是有利的。n n实现最坏分配算法时，空闲区表或空闲区链实现最坏分配算法时，空闲区表或空闲区链中的空闲区可以按照从大到小的顺序排列，中的空闲区可以按照从大到小的顺序排列，排在空闲区表或链中的第一个空闲区总是最排在空闲区表或链中的第一个空闲区总是最大的。同样，当作业归还分区时也必须把空大的。同样，当作业归还分区时也必须把空闲区表或空闲区链调整成按照空闲区的从大闲区表或空闲区链调整成按照空闲区的从大到小的顺序排列的形式，比较麻烦。到小的顺序排列的形式，比较麻烦。n n硬件支持n n采用可变分区方式进行存储管理时，一般采用动态重定位方式装入作业。因此，要有硬件的地址转换机构作支持。通常硬件设置两个专用的控制寄存器：一个是基址寄存器；另一个是限长寄存器。基址寄存器用来存放作业所占分区的起始地址，限长寄存器用来存放作业所占分区的长度。3.可重定位分区分配n n（1 1）实现原理）实现原理n n例如，有一个作业需要例如，有一个作业需要20K20K字节的分区，内存空闲字节的分区，内存空闲区的总数是区的总数是22 K22 K字节，但不连续，所以按照前面字节，但不连续，所以按照前面的分配算法就不能给这个作业分配主存空间。解的分配算法就不能给这个作业分配主存空间。解决的方法是移动所有已分配区的内容，使原来不决的方法是移动所有已分配区的内容，使原来不连续的若干个小的空闲区合并成为一个较大的空连续的若干个小的空闲区合并成为一个较大的空闲区。我们把这个过程称为闲区。我们把这个过程称为“紧缩紧缩”。n n下图给出了内存紧缩前后的情况以及给作业下图给出了内存紧缩前后的情况以及给作业7 7分配分配256K256K字节的内存空间后，内存的分区情况字节的内存空间后，内存的分区情况 。n n把作业把作业4 4从内存中的从内存中的352K352K处移至处移至320K320K，作业，作业4 4分分区中与指令相关的所有地址部分中的有效地址区中与指令相关的所有地址部分中的有效地址均减去均减去32K32K。这种程序在内存中移动所进行的。这种程序在内存中移动所进行的与位置有关的地址调整过程称之为与位置有关的地址调整过程称之为“重定位或重定位或浮动浮动”。实现方法之一是采用类似于重定位装。实现方法之一是采用类似于重定位装入程序的软件来实现，但是这种方法所花费的入程序的软件来实现，但是这种方法所花费的处理机时间太多，而且限制较大。第二种方法处理机时间太多，而且限制较大。第二种方法是采用动态重定位技术即重定位寄存器来完成。是采用动态重定位技术即重定位寄存器来完成。当一个作业在存储器中移动时，只改变重定位当一个作业在存储器中移动时，只改变重定位寄存器中的内容即可。寄存器中的内容即可。n n注意：作业4在“地址空间”中什么都没变，程序也不知道它的实际物理存储位置。分区虽然从352K移到了320K，但是，作业4的每一条指令都不用变化，仍然和在352K分区时一样。由于这种重定位的地址调整是在每条指令执行时自动完成的，所以称之为“动态重定位”。n n软件算法 n n软件算法与可变式分区管理算法基本相同。下图给出了分配算法的流程图。n n总之，可重定位分区管理算法消除了存储器的碎片，总之，可重定位分区管理算法消除了存储器的碎片，因此，存储器的利用率提高了，但是这是以牺牲处理因此，存储器的利用率提高了，但是这是以牺牲处理机的效率为代价而换来的。机的效率为代价而换来的。n n那么，什么时候进行拼接呢？一是当某个作业运行完那么，什么时候进行拼接呢？一是当某个作业运行完毕离开系统时，该作业的分区被回收后，如果它不与毕离开系统时，该作业的分区被回收后，如果它不与空闲区相邻接，则立即进行拼接。于是在存储空间中空闲区相邻接，则立即进行拼接。于是在存储空间中总是只有一个空闲区，因而不存在分散零头的问题。总是只有一个空闲区，因而不存在分散零头的问题。这样做，空闲区的管理以及给作业分配分区都特别方这样做，空闲区的管理以及给作业分配分区都特别方便，但是拼接的频率较高，花费的时间较多。便，但是拼接的频率较高，花费的时间较多。n n第二是当作业找不到足够大的空闲区时再拼接。一个第二是当作业找不到足够大的空闲区时再拼接。一个作业申请存储空间得不到满足时，而所有的空闲区的作业申请存储空间得不到满足时，而所有的空闲区的总和又足够该作业所需要的大小时进行拼接，这样做，总和又足够该作业所需要的大小时进行拼接，这样做，降低了拼接的频率，节省了处理机时间，但是空闲区降低了拼接的频率，节省了处理机时间，但是空闲区的管理不如前一种方法简单。的管理不如前一种方法简单。4.多重分区分配n n在分区式存储管理方法中采用可重定位方法需要在分区式存储管理方法中采用可重定位方法需要拼接，拼接是比较费时间的。既想利用存储器的拼接，拼接是比较费时间的。既想利用存储器的零头而又不想费时间，则可采用的另一种分区分零头而又不想费时间，则可采用的另一种分区分配方案是多重分区分配。配方案是多重分区分配。n n因为一个程序往往是由若干个相对独立的程序段因为一个程序往往是由若干个相对独立的程序段和数据段所组成（主程序和子程序等），程序段和数据段所组成（主程序和子程序等），程序段在逻辑上是连续的，但在主存中却无须连续，这在逻辑上是连续的，但在主存中却无须连续，这种给作业分配一个以上的分区的方法叫多重分区种给作业分配一个以上的分区的方法叫多重分区分配。既然作业可以被分配在多个分区中，当然分配。既然作业可以被分配在多个分区中，当然作业临时申请附加的区段也就容易实现。作业临时申请附加的区段也就容易实现。5.分区的保护措施n n对于以上四种分区管理方法都需要进行分区的保护，通常采用的分区的保护措施主要有两种，一种方法是使用界限寄存器，另一种方法是使用存储保护键。有的系统二者兼用。例如，下图表示使用界限寄存器的方法来进行分区保护，其中，下界寄存器与基址寄存器起重定位作用。多个分区的作业的保护就必须设置多个界限寄存器。n n下图是采用存储保护键的方法实现分区保护。n n综上所述，分区式分配的优点可以归纳如下：综上所述，分区式分配的优点可以归纳如下：n n（1 1）由于内存被分成多个分区，所以允许多）由于内存被分成多个分区，所以允许多道程序同时共享主存空间，这就更有效地利用道程序同时共享主存空间，这就更有效地利用了处理机和了处理机和I/OI/O设备，使系统的吞吐率和周转设备，使系统的吞吐率和周转时间都得到了相应地提高。时间都得到了相应地提高。n n（2 2）相对于以后要介绍的几种管理技术，分）相对于以后要介绍的几种管理技术，分区式分配所需要的表格较少，表格占用的空间区式分配所需要的表格较少，表格占用的空间也少，算法简单。也少，算法简单。n n（3 3）实现分区保护的手段也简单。）实现分区保护的手段也简单。n n（4 4）多重分区管理便于实现对子程序、数据）多重分区管理便于实现对子程序、数据的共享。的共享。n n缺点也可以归纳如下：缺点也可以归纳如下：n n（1 1）与后面要介绍的管理方法相比，分区式管理方法）与后面要介绍的管理方法相比，分区式管理方法主存的利用率仍不是很高，除了可重定位分区分配方主存的利用率仍不是很高，除了可重定位分区分配方法以外，都存在着严重的零头问题。法以外，都存在着严重的零头问题。n n（2 2）分区式管理方法不能实现对主存的扩充，因此，）分区式管理方法不能实现对主存的扩充，因此，作业的大小受主存可用空间的限制。作业的大小受主存可用空间的限制。n n（3 3）要求一个作业在运行前全部信息都要装入主存，要求一个作业在运行前全部信息都要装入主存，有些信息在本次运行时并不需要，它也白白占用了主有些信息在本次运行时并不需要，它也白白占用了主存空间。存空间。n n（4 4）可重定位分区分配方法所允许采用的拼接技术在可重定位分区分配方法所允许采用的拼接技术在拼接时也浪费处理机的大量时间。拼接时也浪费处理机的大量时间。n n（5 5）除了多重分区外，几个作业之间不能共享存入主）除了多重分区外，几个作业之间不能共享存入主存中的信息。存中的信息。443 覆盖与交换覆盖与交换n n1.覆盖（overlap）n n因内存小于作业的程序空间而引入覆盖，因内存小于作业的程序空间而引入覆盖，将用户空间划分成一个固定区和多个覆盖将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖则放在同一个覆盖区。操作系统提供覆盖系统调用函数，由用户编程序时考虑调用。系统调用函数，由用户编程序时考虑调用。n n什么叫覆盖n n所谓覆盖是指一个作业的若干程序段或几个作业的某些部分共享某一段主存空间。覆盖管理是由系统实施，用户只需提供一个明确的覆盖结构。我们称之为自动覆盖技术。n n本节研究两个问题:n n（1）作业内部的覆盖处理n n（2）作业之间的覆盖处理固定区固定区(4k)(4k)覆盖区覆盖区(6k)(6k)覆盖区覆盖区(10k)(10k)A(4k)A(4k)E(10k)E(10k)D(6k)D(6k)C(4k)C(4k)B(6k)B(6k