内部碎片的产生：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视 处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。 外部碎片的产生： 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假 设有一块一共有100个单位的连续空闲内存空间，范围是0-99。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为0-9区间。这时候你 继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为10-14区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比 如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0-9空闲，10-14 被占用，15-24被占用，25-99空闲。其中0-9就是一个内存碎片了。如果10-14一直被占用，而以后申请的空间都大于10个单位，那么0~9就 永远用不上了，变成外部碎片。

内存分配方式主要有连续型分配方式和非连续型分配方式，顾名思义，连续型分配方式就是分配连续的空间，非连续型分配方式就是分配非连续的内存空间。

-连续型分配内存方式：

单一连续分配： 最简单的分配方式，采用覆盖技术。优点是无外部碎片，缺点是只能用于单用户、有内部碎片、存储利用率低。 内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。

固定分区分配： 最简单的多道程序存储管理方式，它将用户内存空间划分为若干个固定大小（可以相等，也可以不等，同为4的倍数或其他 如图1所示），每个分区只装入一道作业。 为便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配），如图2所示。当有用户程序要装入时，便检索该表，以找到合适的分区给予分配并将其状态置为”已分配”；未找到合适分区则拒绝为该用户程序分配内存。存储空间的分配情况如图3所示。

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

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

-动态分区分配： 不预先划分内存，在程序装入内存时，根据进程的大小动态地建立分区，并使得分区的大小正好适合进程的需要，因此系统中分区的大小和数目是可变的。 如图4所示，系统有64MB内存空间，其中低8MB固定分配给操作系统，其余为用户可用内存。开始时装入前三个进程，在它们分别分配到所需空间后，内存只剩下4MB，进程4无法装入。 在某个时刻，内存中没有一个就绪进程，CPU出现空闲，操作系统就换出进程2，换入进程4。由于进程4比进程2小，这样在主存中就产生了一个6MB的内存块。之后CPU又出现空闲，而主存无法容纳进程2,操作系统就换出进程1，换入进程2。

动态分区分配内存方式刚开始是很好地，但是，之后会导致内存出现很多的小的内存块，也就是外部碎片。外部碎片可以通过紧凑来解决，就是操作系统不时地对进程进行移动和整理。 但是这需要动态重定位寄存器的支持，且相对费时。紧凑的过程实际上类似于Windows系统中的磁盘整理程序，只不过后者是对外存空间的紧凑。

在进程装入或换入主存时，如果内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略。

1）首次适应：地址递增，顺序查找，第一个能满足的即分配给进程。

2）最佳适应：容量递增，找到第一个能满足要求的空闲分区。

3）最坏适应：容量递减，找到第一个能满足要求的分区。

4）邻近适应：循环首次适应算法。

在这几种方法中，首次适应算法不仅是最简单的，而且通常也是最好和最快的。 在UNIX 系统的最初版本中，就是使用首次适应算法为进程分配内存空间，其中使用数组的数据结构 (而非链表）来实现。不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。

邻近适应算法试图解决这个问题，但实际上，它常常会导致在内存的末尾分配空间（因为在一遍扫描中，内存前面部分使用后再释放时，不会参与分配)，分裂成小碎片。它通常比首次适应算法的结果要差。

最佳适应算法虽然称为“最佳”，但是性能通常很差，因为每次最佳的分配会留下很小的难以利用的内存块，它会产生最多的外部碎片。

最坏适应算法与最佳适应算法相反，选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大的内存块，因此性能也非常差。

Kunth和Shore分别就前三种方法对内存空间的利用情况做了模拟实验，结果表明：

首次适应算法可能比最佳适应法效果好，而它们两者一定比最大适应法效果好。 另外注意,在算法实现时,分配操作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找，而首次适应法和邻近适应法只需要简单查找； 回收操作中，当回收的块与原来的空闲块相邻时（有三种相邻的情况，比较复杂)，需要将这些块合并。在算法实现时，使用数组或链表进行管理。除了内存的利用率，这里的算法开销也是操作系统设计需要考虑的一个因素。 参考文献： 1.内存分配方式及内存碎片 2.8.内存连续分配方式采用的几种算法及各自优劣