12 内存连续分配管理方式

连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续分配

内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。

这种方式的优点是简单、无外部碎片，可以釆用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。

固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区，如此循环。

固定分区分配在划分分区时，有两种不同的方法：

• 分区大小相等：用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。
• 分区大小不等：划分为含有多个较小的分区、适量的中等分区及少量的大分区。

为便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配），如图(a)所示。当有用户程序要装入时，便检索该表，以找到合适的分区给予分配并将其状态置为”已分配”；未找到合适分区则拒绝为该用户程序分配内存。存储空间的分配情况如图(b)所示。

这种分区方式存在两个问题：
一是程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存空间；
二是主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存分区空间，这样分区内部有空间浪费，这种现象称为内部碎片（已经被分配出去的的内存空间大于请求所需的内存空间）。

固定分区是可用于多道程序设计最简单的存储分配，无外部碎片，但不能实现多进程共享一个主存区，所以存储空间利用率低。固定分区分配很少用于现在通用的操作系统中，但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用。

动态分区分配

动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。

动态分区在开始分配时是很好的，但是之后会导致内存中出现许多小的内存块。随着时间的推移，内存中会产生越来越多的外部碎片（还没有分配出去，但是由于太小而无法分配给申请空间的新进程的内存空间空闲块）。

克服外部碎片可以通过紧凑(Compaction)技术来解决，就是操作系统不时地对进程进行移动和整理。但是这需要动态重定位寄存器的支持，且相对费时。紧凑的过程实际上类似于Windows系统中的磁盘整理程序，只不过后者是对外存空间的紧凑。

常见的动态分区的分配策略如下：

• 首次适应(First Fit)算法：
  空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。该算法倾向于优先利用内存中低地址的空闲部分，保留高地址部分的大空闲区，为以后到达的大作业分配大空间创造条件。其缺点在于：低地址部分由于不断被划分，会留下许多难以利用的小空闲分区，并且，每次都从低地址开始检索，将增大可用空闲区间查找的开销。

• 最佳适应(Best Fit)算法：
  空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区，即找到一个满足要求且最小的空闲分区分配给作业。孤立地看，最佳适应算法看似是最佳的，但是宏观看并非如此，存储器将留下许多难以利用的小空闲区。

• 最坏适应(Worst Fit)算法：
  又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。
  该算法优点是使剩下的空闲区不至于太小，产生碎片的几率最小，对中小作业有利，但对大作业不利。

• 循环首次适应(Next Fit)算法：
  又称邻近适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区的开销，但这样会缺乏大的空闲分区。

以上四种算法称为顺序搜索法，快速适应算法又称为分类搜索算法：

• 快速适应(Quick Fit)算法：
  该算法将空闲分区按照大小进行分类，对每一类具有相同容量的所有空闲分区，单独设置一个空闲分区链表。分类通常常用空间大小进行划分，比如2KB,4KB,8KB等。仅需要根据进程的长度检索，找到能容纳它的最小空闲区链表，进行分配。
  该算法优点是查找效率高，能够保留大的分区，满足用户对大空间的需求。缺点在于分区归还主存时算法复杂，系统开销较大，而且存在一定的空间浪费，是典型空间换时间的做法。

伙伴系统

Linux内核内存管理中采用伙伴系统解决外部碎片问题。伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求。

伙伴系统在回收空闲分区时，需要对空闲分区进行合并，其时间性能比前述分类搜索差，但比顺序搜索算法好，而其空间性能则远优于分类搜索算法，比顺序搜索算法略差。伙伴系统在多处理机系统中，仍不失为一种有效的内存分配和释放的方法，得到了大量的应用。

分配过程举例：

在最初，只有一个块，也就是整个内存，假如为1M大小，而允许的最小块为64K，那么当我们申请一块200K大小的内存时，就要先将1M的块分裂成两等分，各为512K，这两分之间的关系就称为伙伴，然后再将第一个512K的内存块分裂成两等分，各位256K，将第一个256K的内存块分配给内存，这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。

• 1 初始化时，系统拥有1M的连续内存，允许的最小的内存块为64K，图中白色的部分为空闲的内存块，着色的代表分配出去了得内存块。

• 2 程序A申请一块大小为34K的内存，对应的order为0，即2^0=1个最小内存块
  　　2.1 系统中不存在order 0(64K)的内存块，因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)
  　　2.2 仍然没有order 0的内存块，因此order 3的内存块分裂成两个order 2的内存块(256K)
  　　2.3 仍然没有order 0的内存块，因此order 2的内存块分裂成两个order 1的内存块(128K)
  　　2.4 仍然没有order 0的内存块，因此order 1的内存块分裂成两个order 0的内存块(64K)
  　　2.5 找到了order 0的内存块，将其中的一个分配给程序A，现在伙伴系统的内存为一个order 0的内存块，一个order1的内存块，一个order 2的内存块以及一个order 3的内存块

• 3 程序B申请一块大小为66K的内存，对应的order为1，即2^1=2个最小内存块，由于系统中正好存在一个order 1的内存块，所以直接用来分配

• 4 程序C申请一块大小为35K的内存，对应的order为0，同样由于系统中正好存在一个order 0的内存块，直接用来分配

• 5 程序D申请一块大小为67K的内存，对应的order为1
  　　5.1 系统中不存在order 1的内存块，于是将order 2的内存块分裂成两块order 1的内存块
  　　5.2 找到order 1的内存块，进行分配

• 6 程序B释放了它申请的内存，即一个order 1的内存块

• 7 程序D释放了它申请的内存
  　　7.1 一个order 1的内存块回收到内存当中
  　　7.2由于该内存块的伙伴也是空闲的，因此两个order 1的内存块合并成一个order 2的内存块

• 8 程序A释放了它申请的内存，即一个order 0的内存块

• 9 程序C释放了它申请的内存
  　　9.1 一个order 0的内存块被释放
  　　9.2 两个order 0伙伴块都是空闲的，进行合并，生成一个order 1的内存块
  　　9.3 两个order 1伙伴块都是空闲的，进行合并，生成一个order 2的内存块
  　　9.4 两个order 2伙伴块都是空闲的，进行合并，生成一个order 3的内存块
  　　9.5 两个order 3伙伴块都是空闲的，进行合并，生成一个order 4的内存块

内存对换

1 对换的引入

在多道程序环境下，内存中可能存在多个被阻塞的进程，占用大量内存空间，而多个作业在外存上无法进入内存，系统吞吐量下降，资源利用率低。

为解决这一问题，在操作系统中增设了对换操作。对换是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调到外存上，以便腾出足够的内存空间，把已具备运行条件的进程从赋存移入内存。

如果对换是以整个进程为单位的，便称之为“整体对换”或“进程对换”，这种对换被广泛应用于分时系统中，其目的是为了解决内存紧张问题，提高内存利用率。如果对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。“部分对换”的目的是为了支持虚拟存储系统。

2 对换空间的管理

在具有对换功能的OS中，通常把外存分为文件区和对换区。前者用户存放文件，后者用于存放从内存中换出的进程。通常，为提高文件的存储空间的利用率，文件区采用离散分配方式。为提高进程在对换区换入和换出的速度，对换区采用连续分配方式，较少考虑外存中的碎片问题。

为了对对换区中的空闲盘块进行管理，在系统中应配置相应的空闲分区表或空闲分区链，以记录外存中的使用情况。对换区的内存分配与回收方式与连续分配方式相同。