1、第 7 章存 储 管 理7.1 存储管理的功能7.2 程序的装入与链接7.3 连续分配存储管理方式7.4 分页存储管理方式7.5 分段存储管理7.6 虚拟存储器7.7 存储管理实现举例习题第 7 章存 储 管 理为了弄清存储管理的功能，首先要了解存储管理要研究的对象。内存储器的存储空间一般分为两部分：系统区和用户区。系统区主要保存了操作系统和硬件相关的信息和标准子程序。用户区主要包含用户的程序和数据。存储管理的研究对象就是要对主存的用户区进行管理。计算机系统中的处理机能够直接进行数据存取的介质是内存，内存中存放的是操作系统的内核和处于执行态的作业。对于程序和数据只有放在内存中，这个程序才能够运
2、行。存储管理的功能主要包括以下几个方面：逻辑地址到物理地址的映射；主存空间的分配和回收；主存空间的共享和保护以及主存空间的扩充。7.1 存储管理的功能存储管理的功能第 7 章存 储 管 理7.1.1 地址映射地址映射地址映射指的是将用户程序的逻辑地址转换成内存中物理地址的过程。逻辑地址指的是用户编程所用的地址，逻辑地址从0开始编址。例如某个程序有100条指令，那么该程序的逻辑地址范围是099。内存是由若干个存储单元所组成的，每个存储单元就像宾馆里的每一个房间一样，进行统一编号，即每一个存储单元都有自己的编号，这个编号称为内存地址或物理地址。物理地址也是从0开始编址的，例如内存容量是128 MB
3、，那么内存的物理地址为0 B128106-1 B。第 7 章存 储 管 理引入多道程序设计技术后，在系统中可以驻留多个程序，如果要执行用户程序，必须要把它从外存调入到内存中，对于每一个用户程序又都是从0开始编址的，也就是说，每个用户程序不可能都从内存的0地址开始进行分配。因此当用户程序放入内存后，必然会存在逻辑地址和物理地址不符的情况，所以操作系统提供了地址映射的功能来完成从逻辑地址到物理地址的转换过程。第 7 章存 储 管 理如图7-1(a)所示的是一个简单的程序段。第一条指令是把数据A取到1号寄存器中，第二条指令是把数据B同1号寄存器中的内容相加，结果放在1号寄存器中，第三条指令是把1号寄
4、存器的内容送入相对地址10中去。如果这个程序原封不动地装入主存自100号单元起的存储区中，如图7-1(b)所示，就无法正确执行，因为根据指令的要求，地址6、8和10中所存放的内容已经不是程序所需要的数据A和B，数据A和B已经存放到内存106和108中。所以，为了保证程序的正确执行，程序的每条指令都要作相应的调整，需要重新进行定位，转换成如图7-1(c)所示的情况。第 7 章存 储 管 理图7-1 地址映射第 7 章存 储 管 理在一个程序装入到与其地址空间不一致的存储空间时，对有关地址部分的重新调整的过程称为地址的重定位。这个调整过程就是把程序地址空间中使用的逻辑地址变换成主存中物理地址的过程
5、。地址重定位的方式有：静态重定位和动态重定位。第 7 章存 储 管 理1静态重定位静态重定位在装入一个作业时，把作业中的指令地址和数据地址全部转换成物理地址，由于地址转换工作是在作业开始执行前集中完成的，所以在执行过程中就不需要再进行地址转换工作，这种转换方式称为“静态重定位”。静态重定位方式只要知道当前作业在内存的起始地址，装入时就可以利用起始地址和相对地址来实现重定位的过程。因此静态重定位的优点是实现比较简单，第 7 章存 储 管 理但缺点是需要为用户程序分配连续的内存空间而且程序在内存中不能进行移动。由于程序在内存中进行移动就意味着地址发生了改变，故不能取得正确的数据。如图7-1所示的程
6、序段，用户程序装入到内存100起始的存储单元，采用静态重定位方式，程序在装入时每一条指令都将进行修改，如指令Load 1,6改为Load 1,106。现在，如果将程序段移动到内存1000起始的存储单元，原来在100号单元的指令Load 1,106，移动到1000号单元后仍是Load 1,106，这样将不能取得正确的数据。因此，采用静态重定位方式，程序一旦装入内存将不能移动。第 7 章存 储 管 理2动态重定位动态重定位对于静态重定位方式，作业一旦进入主存则不能发生移动，但是程序在内存中是经常要移动的，例如，“紧凑”技术。因此引入动态重定位方式，在装入作业时，不进行逻辑地址到物理地址的转换，而是
7、直接把作业装入到分配的主存区域中，在作业执行过程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成物理地址。第 7 章存 储 管 理动态重定位是要靠硬件的地址转换机构来实现的。通常采用的方法是设置一个重定位寄存器。当系统为用户程序分配一个内存空间后，在重定位寄存器中保存用户程序在内存中的起始地址。程序在执行过程中，当需要进行地址转换时，用逻辑地址加上重定位寄存器中的地址就可以得到相对应的物理地址。这种转换过程是在指令的执行过程中完成的，所以叫动态重定位，动态重定位的过程如图7-2所示。第 7 章存 储 管 理图7-2 动态重定位第 7 章存 储 管 理如图7-2所示，用户程序
8、被装入到内存中10000开始的内存单元中，当用户程序执行到指令Load 1,3500时，系统则会将3500转换成10000+3500=13500地址。动态重定位方式的优点是用户作业不要求分配连续的存储空间，并且用户作业在执行过程中，可以动态申请存储空间和在主存中移动，只需要更改重定位寄存器中的内容即可。这样便于多个进程共享同一个程序的副本。但缺点是代价大，需要由附加的硬件地址变换机构来实现，并且实现地址转换的算法比较复杂。第 7 章存 储 管 理7.1.2 内存的分配与回收内存的分配与回收如果要执行用户程序，必须要将其加载到内存中，因为处理机只能直接和内存进行通信，即操作系统存储管理程序要提供
9、为进程分配内存的功能，当进程结束后，它还要回收进程所占有的内存空间。存储分配方式主要有静态分配和动态分配两种。第 7 章存 储 管 理1静态分配静态分配在作业装入内存时确定其在内存的位置，采用这种分配方式，在一个作业装入时必须分配满足其要求的全部内存容量；如果没有足够的存储空间，就不能装入该作业。并且，作业装入后不能在内存中移动。2动态分配动态分配作业在存储空间的位置也是在装入时确定的，但在执行过程中可以根据需要申请附加的内存空间。当一个作业已经占用的内存区不再需要时，可以归还给系统，并且作业在运行过程中可以在存储空间中移动。第 7 章存 储 管 理引起内存分配和回收的原因很多，但归纳起来有以
10、下四种原因：(1)在多道程序设计的环境中，内存为多道程序所共享，当某个程序调入内存时，要求系统分配内存；运行完成后，系统要回收所占用的内存。(2)在程序运行的过程中，它所占用的内存很有可能发生变化，例如栈的变化，当有信息进栈空间要扩大时，要向系统申请分配内存，反之，栈空间缩小，要释放所占有的内存。另外程序运行过程中，还可能产生某些中间结果，需向系统申请分配内存。第 7 章存 储 管 理(3)进程在内存和外存之间传递。由于内存空间的限制，系统中不可能容纳所有进程。有些进程还必须放在外存，当要运行这样的进程时，必须把它们的图像调入内存，这时就要为其分配内存空间。当无空闲内存时，还要从内存中淘汰某些
11、进程。第 7 章存 储 管 理(4)系统为了充分利用内存空间，有时也对内存空间进行调整，这也是内存的分配和回收的过程。例如：内存中有两个不连续的空闲区域，分别为5 KB和8 KB，如果此时需要调用作业P，其程序空间大小为10 KB，此时系统为了能够装入作业P，必须对当前的内存区域进行调整，把5 KB和8 KB的两个空闲区域连接在一起，组成一个空闲区域位为13 KB的内存空间。在进行调整的过程中，需要移动内存中运行的其他作业，才能把两个空间区域连在一起。这种对内存空间的调整过程称为内存压缩，在这个过程中涉及到内存的分配与回收。第 7 章存 储 管 理7.1.3 存储信息的保护存储信息的保护内存是
12、计算机系统中的一个很重要的硬件资源，内存的容量是有限的，因此，在多道环境下，操作系统为了提高内存的利用率和实现进程间的数据共享，提供了内存共享机制，即两个或多个进程共用内存中的相同区域。此外，由于有多个用户程序和系统软件存于主存中，为使系统能正常工作，使在内存中的各道程序只能访问它自己的区域，避免各程序间相互干扰，特别是当一道程序发生错误时，不至于影响其他程序的运行，操作系统还提供了保护机制。第 7 章存 储 管 理1防止地址越界防止地址越界 每个进程都有自己独立的内存空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。一般是通过界限寄存器来实现防止地址越界的存储保护，如图
13、7-3所示。第 7 章存 储 管 理图7-3 界限寄存器第 7 章存 储 管 理界限寄存器是被广泛使用的一种存储保护技术，机制比较简单，易于实现。其实现方法是在CPU中设置一个上界寄存器和一个下界寄存器。上、下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中，在对内存进行访问操作时首先进行访问地址合法性检查，即检查经过重定位之后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内，则访问是合法的，否则是非法的，并产生访问越界中断，由操作系统进行相应的处理。例如在图7-3中，如果要访问的地址是100K，24K100K超出了下界寄存器，发生越界中断；访问的地址是
14、23K，20K23K24K地址合法。第 7 章存 储 管 理2防止操作越权防止操作越权防止操作越权主要是针对多个进程所共享的区域进行保护的一种方式。对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。例如，假设现在有进程A和进程B，它们共享一个缓冲区，对于进程A可以对缓冲区进行写操作，而进程B可以进行读操作，如果进程B在执行过程中出现了对缓冲区进行写的操作，这时系统将提示进程B操作越权。第 7 章存 储 管 理7.1.4 虚拟存储器虚拟存储器引入多道程序设计技术后，系统总是希望能够在内存中放置尽可能多的进程，以提高系统的吞吐量
15、和资源的利用率，这样就导致了系统中多个进程竞争内存的情况，而对于内存的容量毕竟是有限的，所以随着进程对内存需要不断的增加，操作系统必须要采取某种策略来解决内存紧张的问题。虚拟存储技术则应运而生。第 7 章存 储 管 理虚拟存储技术是将内存和外存结合起来，只将进程的一部分放入内存，其余部分保留在外存里，当执行到要访问的信息不在内存中时，再将这部分内容从外存调到内存中。虚拟存储技术不需要用户去考虑内、外存的问题，一切由操作系统和硬件相配合来完成主机和外围联机存储器之间信息的动态调度。这样计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器，这个存储器称为虚拟存储器。第 7 章存 储 管
16、 理虽然虚拟存储器是为了解决主存容量不够用而提出的，但实质上是解决了程序访问地址和主存的可用地址相脱离的问题。程序访问地址称为虚地址，程序可以访问的虚地址范围叫做程序的虚地址空间。在多道程序运行环境下，操作系统把实际内存扩充成若干个虚存，系统可以为每个用户建立一个虚存。这样每个用户可以在自己的地址空间中编制程序，在各自的虚存上运行。引入虚存概念后，用户就可以不去了解实存(内存)的物理性能，而在虚存的基础上编制程序，这给程序员带来了极大的方便。第 7 章存 储 管 理实现虚拟存储器，需要有一定的物质基础。其一是需要有相当容量的辅存，以便足以存放多用户的作业地址空间。其二是要有一定容量的内存。其三
17、是要有地址变换机构。然而引进虚存后系统就必须在地址变换上花费开销。所以设计虚拟存储器时应该在可能的情况下力求地址变换能快速地进行。第 7 章存 储 管 理在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变成一个可在内存中执行的程序(进程)，通常要经过以下几步，如图7-4所示。7.2 程序的装入与链接程序的装入与链接第 7 章存 储 管 理编译：由编译程序(Compiler)将用户源程序代码编译成若干个目标模块(Object Module)，例如编写了一个C语言程序a.c，经过编译将形成a.obj目标模块；链接：由链接程序(Li
18、nker)将编译好的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块(Load Module)；装入：由装入程序(Loader)将装入模块装入内存，这时用户程序就变成了可在内存中执行的进程。第 7 章存 储 管 理图7-4 用户程序的处理步骤第 7 章存 储 管 理7.2.1 程序的装入程序的装入本节以单目标模块为例讲解装入过程，单目标模块没有链接过程，目标模块也就是装入模块，将一个装入模块装入内存一般有绝对装入、可重定位装入和动态运行时装入等几种方式。第 7 章存 储 管 理1绝对装入方式绝对装入方式 绝对装入方式是早期的适用于单道系统的一种装入方式。用户编写的程序使用的是逻辑地
19、址，如果在编译阶段能够知道该程序将放到内存的什么位置，那么编译程序就可以将逻辑地址转换成物理地址。这时装入程序就可以直接将编译好的模块装入内存，不需对程序和数据的地址进行修改。程序中所使用的绝对地址，既可以在编译或汇编时给出，也可由程序员直接赋予。第 7 章存 储 管 理但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改，就可能要改变程序中的所有地址。绝对装入方式简单、易于实现，但是从资源利用率的角度来看，缺点是很明显的，不能用于多道环境下。第 7 章存 储 管 理2可重定位装入方式可重定位装入方式 引入多道程序设计技术后，在系统中可以驻留多个程序，这时
20、编译程序不能预知所编译的目标模块将来会在内存的什么位置，这时目标模块的地址还是从0开始编址的，程序中的其他地址也是相对于起始地址进行计算的。因此不可能再用绝对装入方式，而应该用可重定位装入方式把装入模块装入内存。可重定位装入方式是根据内存的当前使用情况，将装入模块装入到内存的某个适当位置。例如，将用户程序装入到内存10 000开始的内存单元中。第 7 章存 储 管 理如图7-5所示，可以看出装入模块的起始地址是从0开始的，每条指令相对0开始，那么装入到内存10 000开始的单元后，逻辑地址和物理地址不是一一对应的。对于装入模块中1000位置的指令Load 1,2500的功能是将2500单元的3
21、65取到寄存器1中，而装入内存后，该指令被放入11 000单元中，数据365存放在12 500的单元中，如果直接将装入模块装入内存，不进行地址转换，那么当执行到11 000单元时，指令仍旧是Load 1,2500，将不会取得正确的数据365。因此，需要进行地址转换，由于在编译阶段不能进行地址转换，系统采用在装入时完成地址转换的方式即静态重定位的方式。第 7 章存 储 管 理图7-5 可重定位装入第 7 章存 储 管 理在装入模块时，将相对地址转换成相应的物理地址，如图7-5中的指令Load 1,2500在装入时由装入程序将其转换成Load 1,12 500，那么在执行时就可以找到正确的数据36
22、5了。对于可重定位装入方式，由于地址转换的过程是在装入阶段一次性完成的，那么当作业一旦装入内存后，则不允许在内存中移动，这就是可重定位方式的局限性。第 7 章存 储 管 理3动态运行时装入方式动态运行时装入方式 绝对装入方式不适用于多道环境，可重定位装入方式可以将装入模块装入到内存中任何位置，但是装入后又不允许程序在内存中进行移动，因为程序在内存中移动就表示它们的物理地址发生了改变，这时只有对其指令和数据的地址进行修改才能正确地运行，而实际上，程序在内存中是经常要发生移动的，例如在紧凑技术中，就要求将程序进行移动拼接，这时就需要使用动态运行时的装入方式。第 7 章存 储 管 理动态运行时的装入
23、方式，是把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址仍然是相对地址，动态运行时装入方式需要特殊硬件的支持。第 7 章存 储 管 理7.2.2 程序的链接程序的链接链接程序的功能是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。实现链接的方法有三种：静态链接方式(Static Linking)，装入时动态链接(Load-time Dynamic Linking)，运行时动态链接(Run-time Dynamic Linking)。第 7 章存 储 管 理1.静
24、态链接方式静态链接方式 静态链接方式是一种事先链接方式，即在程序运行之前，先将各目标模块及他们所需的库函数，链接成一个完整的装入模块(执行文件)，以后不再拆开，要运行时可直接将它装入内存。假设，现在有3个目标模块A、B、C，它们的长度分别为L、M、N，如图7-6(a)所示。在模块A中有一条调用模块B的语句CALL B，在模块B中有一条调用模块C的语句CALL C。现在要将3个目标模块链接成一个装入模块，在静态链接方式下，形成的装入模块如图7-6(b)所示。第 7 章存 储 管 理此时，需要解决如下几个问题：(1)修改相对地址。对于模块B和C的地址都是相对0开始编址的，链接成如图7-6(b)所示
25、的装入模块后，模块B的起始地址应该是L而不是0，模块C的起始地址是L+M。所以模块B中的其他地址应该是相对于L进行计算的，模块C中的其他地址是相对于L+M进行计算的。因此，当采用静态链接方式时，需要修改目标模块的相对地址。(2)变换外部调用符号。当形成如图7-6(b)所示的装入模块后，还需要修改外部调用符号，即将B的起始地址变为L，C的起始地址变为L+M。第 7 章存 储 管 理图7-6 静态链接第 7 章存 储 管 理2.装入时动态链接装入时动态链接 在装入时动态链接方式中，用户源程序经编译后所得到的目标模块是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用，将引起
26、装入程序去找出相应的外部目标模块，将它装入内存并修改目标模块中的相对地址。第 7 章存 储 管 理装入时动态链接方式有以下优点：(1)便于修改和更新。对于静态链接方式，如果某个目标模块需要修改则是非常困难的，需要将装入模块打开，再编译再链接，然后重新装入，这样的代价是很大的。而对于装入时的动态链接方式，要修改某个模块是比较容易的事情。第 7 章存 储 管 理(2)便于实现对目标模块的共享。在静态链接方式中，无法实现模块的共享，如图7-7(a)所示，模块A中有语句CALL C，模块B中也有语句CALL C，在静态方式下，形成的装入模块如图7-7(b)所示，从图中可以看出，A和B不能共享模块C，模
27、块C在内存中有两个副本。在装入时的动态链接方式下，就很容易实现对模块C的共享，对于当装入模块A时，遇到CALL C，则将模块C装入内存；装入模块B时，当遇到CALL C时，只需要修改外部调用符号，使其指向模块C在内存的位置即可。第 7 章存 储 管 理图7-7 装入时动态链接第 7 章存 储 管 理3.运行时动态链接运行时动态链接 对于装入时动态链接方式，可以将装入模块装入到内存中的任何地方，但是一旦装入到内存后装入模块的结构是静态的，每次运行时装入模块是相同的。事实上，在某些情况下，每次要运行的模块可能是不同的，由于事先很难确定每次执行的是哪些模块，在装入时动态链接方式下，只能将所有模块在装
28、入时全部链接到一起，全部装入到内存中，所以每次运行装入模块是相同的。这样，无疑会造成资源的浪费。因为，对于某些目标模块在整个运行过程中可能根本执行不到，例如，出错处理模块。如果程序在运行过程中不出现错误，那么将不会用到该模块。第 7 章存 储 管 理运行时动态链接方式是对上述装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才进行链接，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由操作系统去找到该模块并将其装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空
29、间。第 7 章存 储 管 理连续存储管理分配方式是指为一个用户程序分配一个连续的内存空间。连续分配方式主要有两种：单一连续分配和分区分配。单一连续分配是早期的、简单的、适合于单道系统的存储管理方式。分区分配是满足多道程序的最简单的存储管理方式，又分为固定分区分配和动态分区分配。7.3 连续分配存储管理方式连续分配存储管理方式第 7 章存 储 管 理7.3.1 单一连续分配单一连续分配该方式是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。使用这种存储管理方式，内存的用户区被用户程序所独占，即用户区一次只分配给一个作业使用，并且作业一旦进入主存将一直占有主存直到它运行结束才能释放
30、。如图7-8所示，一个容量为256 KB的内存，操作系统占用32 KB，剩下224 KB全部分配给用户作业，如果一个作业仅需64 KB，那么就有160 KB的存储空间被浪费了。第 7 章存 储 管 理图7-8 单一连续存储管理第 7 章存 储 管 理通过图7-8可以发现，采用单一连续存储管理方式，进行内存的分配时只需要判断系统的用户区能否装得下作业，如果作业所需要的内存空间大于用户区的容量，则作业无法装入，即作业不能运行。否则，将整个用户区全部分配给用户作业。当作业运行结束，系统将回收其占有的内存空间，根据单一连续存储管理的思想，只需要将内存中除系统区外的所有空间回收成用户区即可。第 7 章存
31、 储 管 理综上所述，使用单一连续存储管理方式进行内存的分配和回收非常简单，但是这种存储管理方式缺点也是显而易见的，它不支持多道程序，整个用户区被用户作业独占，主存的利用率不高，并且程序的运行受到主存容量的限制。第 7 章存 储 管 理7.3.2 固定分区分配固定分区分配固定分区的基本思想是系统预先将内存的用户区划分成若干个连续的区域，每一个区域称为分区。每个分区中最多只能装入一个作业，且作业也只能在它所驻留的分区中运行。分区一旦分好，每个分区的大小固定不再变化，且分区的个数也不再改变。当作业申请内存时，系统按照一定的算法为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可
32、容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，将造成存储空间浪费。系统将用户区划分成固定大小的分区，各分区的大小可以相等，也可以不相等。第 7 章存 储 管 理1分区大小相等分区大小相等分区大小相等指的是将用户区进行等距的划分，每个分区的大小相等。采用分区大小相等的方式来管理内存，如果程序太小，则会造成内存空间的浪费；如果程序过大，大到每一个分区都不能装下该程序，则该程序将无法运行。第 7 章存 储 管 理2分区大小不等分区大小不等采用分区大小相等的方式对用户区进行划分，简单、易于实现，但是没有考虑每个作业本身的特点，只是从系统的角度将用户区进行等距的划分。为了要解决对
33、于分区大小相等情况所暴露出来的问题，应使用分区大小不等来对用户区进行管理。分区大小不等指的是将用户区划分成若干个分区，每个分区的大小是固定的但并不相等。第 7 章存 储 管 理分区大小不等的划分是在内存中划分一些较小的分区，适量的中等分区和少量的大分区。对于较小的程序放入较小的分区中，大程序装入较大分区，这样，就可以解决上述问题，相对分区大小相等的情况，内存的利用率也提高了。但是，任何程序所需要的内存空间都很难和系统划分的分区正好相吻合，所以仍然会存在内存空间浪费的情况。第 7 章存 储 管 理为了便于对分区的管理，系统采用分区说明表来描述分区的使用情况。分区说明表一般包含各个分区的区号、大小
34、、起始地址以及分区是否分配的状态等信息。为了方便内存的分配，通常将分区按照大小进行排队，当有用户程序要求装入内存时，则系统将检索分区说明表，从表中找出一个能满足用户要求的、尚未分配的分区，将其分配给该程序，然后修改分区说明表中该分区的状态，将其改为已分配的状态；如果找不到满足条件的分区，则拒绝该程序进入内存。第 7 章存 储 管 理装入分区的作业执行结束后必须归还所占用的分区，存储管理根据作业名查看分区说明表，从占用标志位中的记录可以知道该作业所占用的分区，把该分区的占用标志位重新置成“0”，表示该分区现在又成了空闲区，可以用来装入新作业。通过上述分析，无论是分区大小相等还是分区大小不等的情况
35、，当我们进行内存分配的时候，将满足条件的分区全部分配给该程序，而往往分区的大小都要大于用户程序的长度，第 7 章存 储 管 理因此，对于很多用户程序实际上只占用了分区的一部分空间，使分区中有一部分空间闲置不用，这实际上影响了主存空间的利用率。这样就会造成内存浪费的情况，这时当给用户程序分配内存时，余下的不能再利用的空间就称之为碎片，对于固定分区是在分区内产生碎片，所以称为“内部碎片”。第 7 章存 储 管 理【例例7-1】如图7-9(a)所示，假设内存大小为256 KB，系统事先划分成5个分区，其中一个分区(0(32B-1)B)为操作系统占有，其余4个分区为用户程序使用。各个分区的容量为16
36、KB、32 KB、64 KB和112 KB。假设有3个作业A、B、C请求进入主存，其大小分别为6 KB、25 KB、32 KB，内存分配情况如图7-9(b)所示，其中阴影部分表示各个分区中不能再使用的空闲碎片。第 7 章存 储 管 理图7-9 固定分区第 7 章存 储 管 理7.3.3 动态分区分配动态分区分配固定分区是由系统事先划分好分区，并没有考虑到用户程序自身的特点，从而造成了内存空间的浪费，产生了内部碎片，因此系统引入了动态分区存储管理方式。动态分区的基本思想是，在初始状态下，内存的状态是除了被操作系统占去的一块分区外，其余的是一块大的没有被划分的空闲区，当有用户程序提出请求后，从空闲
37、区中划出一个与用户程序大小一致的分区装入该用户程序，剩余的部分仍然为空闲区。如果用户程序的大小超出空闲区的长度时，则该程序无法装入。如图7-10所示的进程A、进程B和进程C分别请求进入内存以及进程B运行结束后的内存分配情况。第 7 章存 储 管 理图7-10 内存分配情况 第 7 章存 储 管 理装入主存储器的用户程序执行结束后，它所占用的分区将被收回，成为一个空闲区，收回后的空闲区可用来装入新的用户程序。随着用户程序不断地被装入和执行结束后的撤离，主存储区被分成许多分区，有的分区被占用，有的分区空闲，如图7-10(e)所示。动态分区存储管理方式相对于固定分区存储管理方式提高了内存的利用率，更
38、好地适应了用户程序的需要，但是随着用户进程的动态变化，系统经过一系列的内存的分配和回收过程后，在内存中将会出现一些小的空闲区而不能再被使用，这些小的不能再被利用的空闲区将会成为碎片，对于动态分区所产生的碎片是在空闲区外，所以称为“外部碎片”。第 7 章存 储 管 理对于碎片现象，其实就是内存空间的浪费，系统在某时刻可能会出现这样的情况：当某个进程在申请内存空间时，系统中有若干个空闲区，这些空闲区的总和足可以满足用户的需要，但是每一个单个空闲区的空间都不能满足用户的需要，导致无法进行分配，进程也无法运行。【例例7-2】系统中有4个不邻接的空闲区，它们的容量分别是10 KB、30 KB、14 KB
39、和26 KB。现在有一个作业到达，要求分配40 KB的内存空间，能否分配？为什么？第 7 章存 储 管 理解解：由于作业需要一个连续的内存空间，但是系统剩余的空闲区都不能满足用户作业的需要，因而不能分配。再考虑系统剩余的空闲区的总量是80 KB，应该可以放下作业，所以需要采用另外的方法来解决。动态分区是根据用户程序的实际需要，为其分配一个连续的内存空间。在实现动态分区存储管理方式时，需要解决以下几个问题：(1)分区分配所需要的数据结构。(2)分区分配算法。(3)分区的分配和回收。第 7 章存 储 管 理1.分区分配中的数据结构分区分配中的数据结构 为了实现动态分区存储管理方式，系统必须设置相应
40、的数据结构来描述内存的使用情况，为内存的分配提供依据。常用的数据结构有空闲分区表和空闲分区链两种。1)空闲分区表采用动态分区方式管理主存时，主存储器中已占用分区和空闲分区的数目和大小都是在变化的。为了便于对主存空间的分配和回收，主存分配表可以用两张表格组成，一张是“已分配区表”，另一张是“空闲区表”，如表7-1所示。第 7 章存 储 管 理表表7-1 动态分区表格动态分区表格 (a)已分配区表 (b)空闲区表第 7 章存 储 管 理已分配区表记录已装入的作业在主存中占用分区的始址和长度，用标志位指出占用分区的作业名。空闲区表记录主存中可供分配的空闲区的始址和长度，也用标志位指出该分区是未分配的
41、空闲区。由于已占分区和空闲区的个数不定，因此，两张表格中都应设置适当的空栏目(置标志位的状态为“空”)，分别用以登记新装入主存的作业占用的分区和作业撤离后的新空闲区。当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找出一个能容纳该作业的空闲区。第 7 章存 储 管 理如果找到的空闲区正好等于该作业的长度，则把该空闲区全部分配给作业。这时应把该空闲区登记栏中的标志改为“空”状态，同时在已分配区表中找到一个标志为“空”的栏目，登记新装入的作业占用分区的始址、长度和作业名。如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分用来装作业，另一部分仍为空闲区。这时应修改空闲区的始
42、址和长度，且把新装入的作业登记到已分配表中。当有作业执行结束撤离时，同样要修改两张表格。从已分配表中找出作业占用的分区，把表中相应栏的状态改成“空”，而将归还的分区登记到空闲区表中。第 7 章存 储 管 理2)空闲分区链空闲分区表的方式是采用线性表的方式来实现对主存空间的管理，采用空闲分区表方式简单、易于实现，但是插入和删除某个分区比较困难，因此引入空闲分区链方式。空闲分区链是在每个空闲区里开辟两个单元，一个用于存放空闲区的长度(size)，一个用于存放下一个空闲区的起始地址(next)，最后一个空闲区的next设置为NULL。系统设置一个链首指针(head)，指向第一个空闲块，这样就构成了空
43、闲区链表。第 7 章存 储 管 理当有用户作业要求装入主存时，只需要从head指针开始查找是否有满足条件的空闲区，如果有则根据用户作业的大小，从该空闲区中划出一部分分配给该用户作业，余下的仍旧是空闲区，否则拒绝作业装入主存，空闲分区链的结构如图7-11所示。第 7 章存 储 管 理图7-11 空闲分区链第 7 章存 储 管 理2.分区分配操作分区分配操作 1)内存分配当用户作业请求内存空间时，动态分区存储管理方式首先是要根据某种算法在空闲分区表(链)中查找满足条件的空闲区。如果找到则根据用户的需要进行分配，余下的为空闲区。一般系统为了减少碎片的产生，还会设置一个size值作为一个标准，当进行分
44、配时如果余下的空闲区的大小size值，则将整个空闲区全部分配给用户作业，不再进行分割，以免分割后剩余的空间太小，难于利用。分配结束后将分配的内存空间的首地址返回给调用者。设用户请求的大小为u.size，空闲区的大小为m.size，分区分配过程如图7-12所示。第 7 章存 储 管 理图7-12 分配内存流程图第 7 章存 储 管 理2)内存回收 在动态分区方式管理下，当用户作业正常或非正常结束时，系统将要回收其所占有的内存空间，系统将根据要回收的内存空间的首地址，在空闲分区表(链)中查找相应的结点，这时，可能会出现以下几种情况：(1)回收区有下邻接空闲区F2。如图7-13(a)所示，回收区R有
45、一个下邻接空闲区，当回收R为空闲区时需要修改空闲分区表(或空闲分区链)：修改F2空闲区的大小为F2+R，空闲区的首址为回收区R的首址。第 7 章存 储 管 理(2)回收区有上邻接空闲区F1。如果回收区R有上邻接空闲区，如图7-13(b)所示，当回收R为空闲区时只需要将空闲区F1的大小修改为F1+R即可。(3)回收区既有上邻接空闲区又有下邻接空闲区。如果回收区R既有上邻接空闲区，又有下邻接空闲区，如图7-13(c)所示。此时，需要进行如下修改：将三个分区大小合并作为一个空闲区，此空闲区的起始地址为F1的首地址，在空闲区链中取消F2。第 7 章存 储 管 理(4)回收区既无上邻接空闲区又无下邻接空
46、闲区。如果回收区既无上邻接空闲区又无下邻接空闲区，如图7-13(d)所示。这时，回收区R则要作为一个新的空闲区进行回收，需要新建一个结点，填入回收区R的起始地址和大小，并根据要求将该结点插入到空闲区链中适当的位置。第 7 章存 储 管 理图7-13 动态分区回收空闲区第 7 章存 储 管 理3.分区分配算法分区分配算法 在动态分区存储管理方式中，当有用户提出申请内存的请求时，系统需要按照一定的分配算法，从空闲分区表或是空闲分区链中，选出一个满足用户需要的分区给该程序。常用的分配算法有：首次适应算法、最佳适应算法和最差适应算法。第 7 章存 储 管 理1)首次适应算法下面的分区分配算法均以空闲分
47、区链为例来进行说明。首次适应算法要求空闲分区链按地址递增的顺序排列。在进行分配时，从空闲分区链的head指针开始查找，直到找到能满足其大小要求的空闲分区为止。然后将该分区划出一块空间给请求者，剩余的空闲部分仍留在空闲分区链中。第 7 章存 储 管 理首次适应算法优先利用内存低地址部分的空闲区，从而保留了高地址部分的大空闲区。这样当后续到达的一些大的用户作业就可以得到分配，但是该算法对低地址端频繁进行分割，留下许多难以利用的很小的空闲分区，每次查找都要从低地址部分开始查找，这样增加了查找可用空闲分区开销。【例例7-3】系统中按地址递增的空闲区如表7-2所示：第 7 章存 储 管 理表表7-2 按
48、地址递增的空闲区按地址递增的空闲区第 7 章存 储 管 理要求：(1)按照首次适应算法画出系统空闲分区表；(2)现有三个作业分别申请内存空间100 KB、30 KB及7 KB。给出按首次适应算法的内存分配情况及分配后的空闲分区表。解：(1)空闲分区表如表7-3所示。第 7 章存 储 管 理表表7-3 空闲分区表空闲分区表(首次首次)第 7 章存 储 管 理(2)按照首次适应算法。申请作业100 KB，分配3号分区，剩下分区为20 KB，起始地址160K；申请作业30 KB，分配1号分区，剩下分区为2 KB，起始地址50K；申请作业7 KB，分配2号分区，剩下分区为1 KB，起始地址59K；其内
49、存分配图如图7-14所示，分配后的空闲分区表如表7-4所示。第 7 章存 储 管 理表表7-4 该算法分配后的空闲分区表该算法分配后的空闲分区表 第 7 章存 储 管 理图7-14 内存分配图(首次)第 7 章存 储 管 理2)最佳适应算法最佳适应算法的基本思想是当用户作业提出申请内存的请求时，每次分配满足条件的最小分区给请求者，这时要求空闲分区链按大小递增的顺序排列。在进行分配时，从空闲分区链的head指针开始查找，直到能满足其大小要求的空闲分区为止。由于空闲分区是按照大小递增的顺序排列的，则第一个满足条件的就是最小的空闲区，然后将该分区划出一块空间给请求者，剩余的空闲分区仍留在空闲分区链中
50、。第 7 章存 储 管 理最佳适应算法优先利用了大小与程序要求最接近的空闲区，保留了大空闲区。但是，最佳适应算法看似最佳，其实不然。使用此方法当满足用户请求，进行分配后剩下的空闲区就是最小的，形成难于利用的空间。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。【例例7-4】按最佳适应算法解决例7-3的问题，并画出内存分配情况及分配后空闲分区表。解：(1)空闲分区表如表7-5所示。第 7 章存 储 管 理表表7-5 空闲分区表空闲分区表(最佳最佳)第 7 章存 储 管 理(2)按最佳适应算法。申请作业100 KB，分配3号分区，剩下分区为20 KB，起始地址160K；申请作
