3.1_3 连续分配管理方式_采用什么不会产生外部碎片

3.1_3 连续分配管理方式

  连续分配：指为用户进程分配的必须是一个连续的内存空间。

（一）单一连续分配

  在单一连续分配方式中，内存被分为系统区和用户区。

  系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。

  内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点

  实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护（eg：早期的PC操作系统MS-DOS）。

  因为1个用户进程独占整片用户区，所以不会发生A进程访问B进程的内存空间的情况，因此不一定需要采取内存保护。但有的系统也会采取一定的内存越界保护等。

缺点

  只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

  分配给某进程的内存区域中，如果有些部分没有用上，就是“内部碎片”。

（二）固定分区分配

  20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

  分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序）

  分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分（比如：划分多个小分区、适量中等分区、少量大分区）。

  操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。

  当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。

优点

  实现简单，无外部碎片。

缺点

  a.当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；

  b.会产生内部碎片，内存利用率低。

（三）动态分区分配

  动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。（eg：假设某计算机内存大小为64MB，系统区8MB，用户区共56MB）

问题

  1.系统要用什么样的数据结构记录内存的使用情况？

  2.当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

  例如，上图中，进程2执行完毕并离开。此时又有一个4MB的进程要进入内存，那么它是应该分配到刚刚进程2所占用的14MB空间的地方，还是最下方空闲的4MB的地方？

  3.如何进行分区的分配与回收操作？

  例如，进程2、进程3执行完毕并离开，此时，内存中会有三块空闲区域：14MB、18MB、4MB。那么这三块连续的空闲分区该如何处理、是否该进行合并？

问题1：系统要用什么样的数据结构记录内存的使用情况？

  两种常用的数据结构：a.空闲分区表；b.空闲分区链。

问题2：当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

  如上图，此时若有一个进程5（4MB）到达，则：应该用最大的分区进行分配？还是用最小的分区进行分配？又或是用地址最低的部分进行分配？

  把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。

（在下个小节中会介绍四种动态分区分配算法）

问题3：如何进行分区的分配与回收操作？

  假设系统采用的数据结构是“空闲分区表”——如何分配？

分配时-情况1

  假设此时来了一个进程5（4MB），并且打算存入20MB的空闲分区当中。

分配时-情况2

  假设此时来了一个进程5（4MB），并且打算存入4MB的空闲分区当中。

---

  假设系统采用的数据结构是“空闲分区表”——如何回收？

回收时-情况1：回收区的后面有一个相邻的空闲分区

  假设此时要回收进程4（即，要回收的进程，在它后面，有一个相邻的空闲分区）。——两个相邻的空闲分区合并为一个。

回收时-情况2：回收区的前面有一个相邻的空闲分区

  假设此时要回收进程3（即，要回收的进程，在它前面，有一个相邻的空闲分区）。——两个相邻的空闲分区合并为一个。

回收时-情况3：回收区的前、后各有一个相邻的空闲分区

  假设此时要回收进程3（即，要回收的进程，在它的前、后各有一个相邻的空闲分区）——三个相邻的空闲分区合并为一个。

回收时-情况4：回收区的前、后都没有相邻的空闲分区

  假设此时要回收进程2（即，要回收的进程，它的前、后都没有相邻的空闲分区）——新增一个表项。

  注：各表项的顺序不一定按照地址递增顺序排列，具体的排列方式需要依据动态分区分配算法来确定。

---

  动态分区分配没有内部碎片，但是有外部碎片。

  内部碎片：分配给某进程的内存区域中，有些部分没有用上。

  外部碎片：指内存中的某些空闲分区由于太小而难以利用。

---

外部碎片举例：

---

  如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。

  可以通过**紧凑（拼凑，Compaction）**技术来解决外部碎片。

  紧凑技术，就是“挪位置”，把内存中的进程位置挪到一块，腾出一块连续的大空间。

---

思考：

  1.再次回顾交换技术，什么是换入/换出？什么是中级调度（内存调度）？

  2.思考动态分区分配应使用哪种装入方式？“紧凑”之后需要做什么处理？

  应该用三种装入方式当中的——动态重定位。因为这种方式能最方便实现“进程在内存当中移动位置”这件事情。

  另外，“紧凑”之后，我们应该把各个进程的起始地址（一般存放在进程PCB当中）给修改一下。

总结