22、内存管理概述

（1）内存管理的功能

内存管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器。为此存储管理应具有以下功能：

• 内存的分配与回收 由操作系统完成内存空间的分配和管理，是程序设计人员摆脱存储空间分配的麻烦，提高编程效率。为此，系统应记住内存空间的使用情况；实施内存的分配：回收系统或用户释放的内存空间
• 地址变换 再多道程序环境下，程序中的逻辑地址与内存中的物理地址可能不一致，因此存储管理必须提供地址变换功能，将逻辑地址转换为物理地址
• 扩充内存 借助于虚拟存储技术或其他自动覆盖技术，为用户提供比内存空间大的地址空间，从而实现从逻辑上扩充内存容量的目的。
• 存储保护 保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。既要防止一道作业由于发生错误而破坏其他作业，也要防止破坏系统程序。这种保护一般由硬件和软件配合完成

（2）应用程序的编译、链接与装入

应用程序从用户编写的源文件到内存中执行的进程，大致分为三个阶段：经过编译程序compiler将源代码编译为若干个目标模块，再通过连接程序将编译好的目标模块以及所需的库函数连接到一起，形成完整的装入模块，最后通过装入程序将这些装入模块装入内存并执行。简单来说，从源程序到执行的进程，经历了编译、链接、装入三个步骤

对程序设计者来说，数据的存放地址由数据名称决定，称为名地址或符号名地址，源程序的地址空间因此称为名空间或符号名空间，源程序经过编译之后得到目标代码，由于编译程序无法得知代码驻留在内存中的实际位置，故一般总是从0号单元开始编址，并顺序分配所有地址单元，这些都不是真实的内存地址，因此称为相对地址或者虚拟地址

一个完整的程序可以由多个模块构成，这些模块都是由0号单元开始编址。当链接程序将多个模块链接为装入模块时，连接程序会按照各个模块的相对地址将其地址构成统一的从0号单元开始编址的相对地址

当转入程序将可执行代码装入内存中时，程序的逻辑地址与程序在内存中的实际地址（物理地址）通常不同，这就需要通过地址转换将逻辑地址转换为物理地址，这个过程叫做定位。

程序的链接由三种方式：

• 静态链接 在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不在拆开
• 装入时动态链接 将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式
• 运行时动态链接 直到程序运行过程中需要一些模块时，才对这些模块进行链接。这种链接方式将对某些模块的链接推迟到执行时才执行，也就是说，在执行过程中，当发现一个被调用模块尚未装入内存时，立即去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被连接到装入模块上，这样不仅可加快程序的装入过程，而且可以提节省大量的内存空间，便于修改和更新，便于实现对目标模块的共享。

程序的装入同样也有三种方式。

• 绝对装入 在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计
• 可重定位装入 根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常再装入时一次完成，之后不再改变，这种方式也成为静态重定位，静态重定位的实现很简单，当操作系统为程序分配了一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址
• 动态运行装入 允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。由于重定位过程是在程序执行期间随着指令的执行逐步完成的因此也成为动态重定位。动态重定位的实现要依靠硬件地址的变换机构。最简单的实现方法是利用一个重定位寄存器。当某个作业开始执行时，操作系统负责把该作业在主存中的起始地址送入重定位寄存器中，之后在作业的整个执行过程中，每当访问内存时，系统自动将重定位寄存器的内容加到逻辑地址中区，从而得到了与该逻辑地址对应的物理地址

静态重定位的特点是容易实现，无需增加硬件地址变换机构。但他要求为每个程序分配一个连续的存储区，如果空间不足以放下整个程序就不能分配，而且在程序执行期间不能移动，不能再申请内存空间，难以做到程序与数据的共享

动态重定位的特点是可以将程序分配到不连续的存储区中；在程序运行之前装入它的部分代码即可投入运行，然后在程序运行期间根据需要动态申请分配内存；便于程序段的共享；可以像用户提供一个比主存的存储空间大得多的地址空间、但动态重定位需要附加硬件支持，且实现存储管理的软件算法比较复杂。

在重定位中通常会设置一个重定位寄存器，用来存放进程分配的内存空间的地址，该寄存器也成为基址寄存器。当CPU需要访问内存时，将逻辑地址转化为物理地址，转化公式为：

物理地址=基址寄存器内容+逻辑地址

（3）物理地址和逻辑地址

源代码在经过编译后，目标程序中所用的地址就是逻辑地址，而逻辑地址的范围内即使逻辑地址空间。在编译程序对源代码进行编译时，总是从0号单元开始编址，地址空间中的地址都是相对于0开始的，因此逻辑地址也叫做相对地址。在系统中运行的多个进程可能会有相同的逻辑地址，但这些逻辑地址映射到物理地址上就变成了不同的位置

物理地址空间是指内存中物理地址单元的集合，而物理地址是逻辑地址转换得到的最终地址。进程在运行过程中需要访问存取指令或数据时，都是根据物理地址从主存中获得。物理地址对于一般的用户来说是完全透明的，用户只需要关心程序的逻辑地址就可以了。从逻辑地址到物理地址的转化过程是由硬件自动完成，这个转换过程叫做地址重定位

（4）内存保护

内存保护是为了防止一个作业有意或无意地破坏操作系统或其他作业。常用的存储保护方法由界限寄存器方法和存储保护键方法

• 界限寄存器方法 采用界限寄存器方法实现存储保护又有两种实现方式

上下界寄存器方法。采用上、下界寄存器分别存放作业的结束地址和开始地址。在作业运行过程中，将每一个访问内存的地址都同这两个寄存器内容进行比较。如超出范围便产生保护性中断

基址、限长寄存器方法 采用基址和限长寄存器分别存放作业的起始地址及作业的地址空间长度。当作业执行时，将每一个访问内存的相对地址和现场寄存器比较，如果超过了限长寄存器的值，则发出越界中断信号，并停止作业的运行

• 存储保护键方法 存储保护键方法是给每个存储块分配一个单独的保护键，它相当于一把锁。存储块不同于分区，一个分区由若干存储块组成，每个存储块大小相同，一个分区的大小必须是存储块的整数倍。此外，进入系统的每个作业也赋予了一个保护键，相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，如果二者不匹配，则系统发出保护性中断信号，停止作业运行

 

23、交换与覆盖

（1）覆盖（overlay）技术

覆盖技术主要用在早期的操作系统中，因为在早期的单用户系统中内存的容量一般很小，可用的存储空间收受到限制，某些大作业不能一次装入内存中，这就发生了大作业与小内存的矛盾，为此引入覆盖技术

所谓覆盖技术，就是把一个大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时并不要求同时装入内存的覆盖组成一组，称为覆盖段，这个覆盖段分配到同一个存储区域，这个存储区域称为覆盖区，他与覆盖段一一对应。显然，为了使一个覆盖区能被相应覆盖段中的每个覆盖在不同时刻共享，其大小应由覆盖段中的最大覆盖来确定。覆盖技术对程序员的要求较高，必须把一个程序划分为不同的程序段，并规定好执行和覆盖顺序，操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。

覆盖技术的特点时打破了必须将一个进程的全部信息装入内存后才能运行的限制。但当同时执行程序的代码两超过贮存时，仍然不能运行

（2）交换（Swapping）技术

交换技术就是把暂时不用的某个程序及数据部分（或全部）从内存移到外存中，一边腾出必要的内存空间；或把指定的程序或数据从外村督导相应的内存中，并将控制权转给她，让其在系统上运行的一种内存扩充技术。处理器三级调度就是采用了交换技术

交换技术最早在麻省理工大学的兼容分时系统CTSS中，任何时刻在该系统的内存中只有一个完整的用户作业，当其运行一段时间后，或由于需要其他资源而等待，系统就把他交换到外存上，同时把另一个作业调入内存运行。这样，可以在存储容量不大的小型机上实现分时运行，早期的一些分时系统大多采用这种交换技术

与覆盖即使相比，交换技术不要求程序员给出程序段之间的覆盖结构，而且交换主要是在进程或作业之间进行；而覆盖则主要在同一个作业或进程中进行。另外，覆盖技术只能覆盖与覆盖程序段无关的程序段。交换进程由换出和换入两个过程组成，由于覆盖技术要求给出程序段之间的覆盖结构，使得对用户不透明，所以对于贮存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术解决的，覆盖技术已经成为历史；而交换技术在现代操作系统中仍然由较强的生命力。

 

24、连续分配管理方式

（1）单一连续分配

单一连续分配是一种简单的存储管理方式，通常只能用于单用户、单任务的操作系统中。这种存储管理方式将内存分为两个连续存储区域，其中的一个存储区域固定地分配给操作系统使用，通常放在内存低址部分，另一个存储区域给用户作业使用。通常，用户作业只占有所有分配空间的一部分，剩下的一部分实际上浪费掉了。

单一连续分配方式采用静态分配，适合单道程序，可采用覆盖技术。作业一旦进入内存，就要等到其结束后才能释放内存。因此，这种分配方式不支持虚拟存储器的实现，无法实现多道程序共享主存。

单一连续分配方式的优点时管理简单，只要很少的软件和硬件支持，且便于用户了解和使用。缺点是只能用于单用户、单任务的操作系统中，内存中只装入一道作业运行，从而导致各类资源的利用率都很低

单一连续分配会产生内部碎片

（2）固定分区分配

固定分区分配方法时最早使用的一种可运行多道程序的存储管理方法，他将内存空间划分为若干个固定分区大小的分区，每个分区中可以装入一道程序。分区的大小可以不等，但是先必须确定，在运行时不能改变。当有空闲分区时，便从后备队列中选择一个适当大小的作业装入运行

固定分区分配中，程序通常采用静态重定位方式装入内存。

为了实现固定分区分配，系统需要建立一张分区说明表，已记录可用于分配的分区号，分区的大小、分区的起始地址及状态，通常按照分区大小顺序排序

当某个用户程序要装入内存时，由内存分配程序检索分区说明表，从表中找出一个能满足要求的尚未分配的分区分配给该程序，然后修改分区说明表中相应分区表项的状态；若找不到大小足够的分区，管理程序只需将对应分区的状态置为未分配即可

固定分区分配的优点时可用于多道程序系统最简单的存储分配，缺点时不能实现多进程共享一个主存区，利用率较低，会产生内部碎片

（3）动态分区分配

动态分区分配是一种动态划分存储器的分区方法。这种分配方法并不事先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态的建立分区，并使分区的大小正好满足作业的需要。因此，系统中分区的大小时可变的，分区的数目也是可变的

1）分区分配的数据结构

为了实现动态分区分配，系统中也必须设置相应的数据结构来记录内存的使用情况。常用的数据结构形式有：

空闲分区表：设置一个空闲分区表来登记系统中的空闲分区，每个空闲分区对应一个表项，每个表项包含分区号、起始地址、大小及状态

空闲分区链：用链头指针将内存中的空闲分区链接起来，构成空闲分区链

2）分区分配算法

为了将一个作业装入内存，应按照一定的分配算法从空闲分区表（或空闲分区链）中选出一个满足作业需求的分区分配给作业。如果这个空闲分区的容量比作业申请的空间容量要大，则该分区的一部分分配给作业，剩下的一部分仍然留在空闲分区表（或空闲分区链）中，同时需要对空闲分区表（或空闲分区链）中的有关信息进行修改。目前常用的分配算法有以下四种：
a）首次适应算法（FF）把空闲分区按照地址递增用链表传承一个队列，每次需要为一个进程分配内存的时候都从队首开始找，顺着链表直到找到足够大的空闲分区，绕后按照作业大小，从该分区划分出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区（或空闲分区链）中。如果从头到尾都不存在符合条件的分区，则分配失败。

优点：优先利用内存低地址部分的空闲分区，从而保留了高地址部分的大的空闲分区，无内部碎片

缺点：由于低地址部分被不断划分，致使低地址端留下许多难以利用的很小的空闲分区（外部碎片），而每次查找又都是从低地址部分开始的，这无疑增加了查找可用空闲分区的开销

b）循环首次适应算法（NF）：又称下次适应算法。在首次适应算法的基础上把队列改成循环队列（依然是将空闲分区按照地址递增的顺序排列、而且也不是每次从队首开始找空闲分区，而是从上次找到的空闲分区的下一个分区开始找）

优点：这样空闲分区的分布更加均匀，减少了查找空闲分区的开销

缺点：导致缺乏大的空闲分区

c）**适应算法（BF）：要求空闲分区按照容量大小递增的次序排列。每次为作业分配内存空间时，总是将能满足空间大小需要最小的空闲分区给作业。可以产生最下的内存空闲分区

优点：这种方法总能分配给作业最恰当的分区，保留大的分区

缺点：导致产生很多难以利用的碎片空间

d）最差适应算法（WF）：要求空闲分区按照容量大小递减的次序排列。每次为作业分配内存空间时，总是将满足要求且最大的内存空间分配给作业

优点：这样使分给作业后剩下的空闲分区比较大，可以装下其他作业

缺点：由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请会得不到满足

3）分区的回收

当作业执行结束时，应回收已使用完毕的分区。系统根据回收分区的大小及首地址，在空闲分区表（或空闲分区链）中检查是否有相邻的空闲分区，如果有相邻空闲分区，则合并成一个大的空闲区，然后修改有关的分区状态信息。回收分区与已有空闲分区的相邻情况有以下四种：

回收区上邻接一个空闲分区：此时应将回收区与上邻接分区合并成一个连续的空闲分区，合并分区的首地址为空闲分区的首地址，其大小为二者之和

回收区下邻接一个空闲分区：此时应将回收区与下邻接分区合并成一个连续的空闲分区，合并分区的首地址为回收区的首地址，其大小为二者之和

回收区上、下邻接空闲分区：此时应将回收区与上、下邻接分区合并成一个连续的空闲分区，合并分区的首地址为上空闲分区的首地址，其大小为三者之和

回收区不与任何空闲分区相邻：这时单独建立表项，填写分区大小及地址等信息，加入空闲分区表（或空闲分区链）的适当位置

4）分区分配的动态管理

在分区存储管理方式中，必须把作业装入到一片连续的内存空间中，如果系统中有若干小的分区，其总容量大于要装入的作业，但由于它们不相邻接，只是作业不能装入内存。例如，内存中有四个空闲分区不相邻接，大小为20KB、30KB、15KB、25KB，总大小为90KB，但如果有一个40KB的作业到达，由于系统中所有空闲分区分配进行动态管理，目前主要有两种分区重定位技术

a）拼接技术。所谓碎片，是指内存中无法被利用的存储空间。在分区存储管理方式下，系统运行一段时间后，内存中的碎片会占据相当数量的空间。根据碎片出现的情况，可以将碎片分为内部碎片和外部碎片。内部碎片是指分配给作业的存储空间中的未被利用的部分，外部碎片是指系统中无法利用的小存储块。如固定分区分配中存在内部碎片，而动态分区分配中存在外部碎片

解决碎片的方法之一是将存储器中所有已分配分区移动到主存的一端，使本来分散的多个小空闲区连接成一个大的空闲区。这种通过移动把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑，也可称为紧缩

除了有怎样进行拼接的技术问题之外，拼接技术的实现还存在一个拼接时机的问题，这个问题有两种解决方案：

第一种方案是在某个分区回收时立即进行拼接，这样在主存中总是只有一个连续的空闲区，但拼接很费时间，拼接频率过高会使系统开销加大

第二种方案是当找不到足够大的空闲分区且总容量可以满足作业要求时进行拼接。这样拼接的频率比上一种方案要小得多，但空闲分区的管理稍微复杂一些

b）动态重定位分区分配技术。动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于：在这种分配算法中增加了拼接功能，通常是在找不到足够大的空闲分区来满足作业要求，而系统中空闲分区容量总和大于作业要求时，进行拼接

5）动态分配的优缺点

优点：实现了多道程序共用主存；管理方案相对简单、不需要更多开销；实现存储保护的手段比较简单

缺点：主存利用不够充分，存在外部碎片；无法实现多进程共享存储信息；无法实现主存额扩充。进程地址空间受实际存储空间的限制

（4）内部碎片与外部碎片

内存碎片分为内部碎片和外部碎片。前面也提到过，在分配给进程的分区中的未被利用的碎片称为内部碎片，而系统中剩余的无法利用的小块存储空间称为外部碎片

一个简单区分两种碎片的方法就是看分配过程中分区大小是否固定。在固定分区的情况下，产生的碎片称为内部碎片（例如在分页存储管理中，末尾页可能无法填满，造成剩余的空间叫做内部碎片；）在非固定分区的请款啊阁下，可能在分配的过程中伤愈的最后一点小空间无法满足任何分配需求，导致浪费，这种碎片就称为外部碎片（例如在分段存储管理中，如果内存为5K，程序需要4K，则分配之后会剩余1K的无法利用空间，这个就是外部碎片）

注意：固定分区即为内部碎片，非固定分区则为外部碎片，如果固定分区和布不固定分区同时存在（如段页式），则看成固定分区