操作系统-Operating-System第三章03：内存管理方式（连续内存分配）
B站资源：操作系统_清华大学(向勇、陈渝)
Github资源：chyyuu/os_course_info
连续内存分配
为用户进程分配的必须是一个连续的内存空间
固定分区
在大部分的内存方案中，我们可以认为操作系统占据了主存中固定的几个分区，剩下的主存空间用于多进程的使用。最简单的方案就是将内存划分成具有固定边界的区域。
分区大小
一种可能性是充分利用等大小的分区。在这种情况下，任何所需内存大小小于或者等于分区大小的进程都可以被加载到分区中。如果所有的分区已满，并且没有任何进程处于就绪或者正在运行状态，则操作系统可以从任何一个分区中交换一个进程并加载另一个进程进该分区，这样处理器就可以进行一些工作。
对于使用等大小的固定分区，存在两点困难：
- 程序太大，无法放入分区中。这种情况下，程序员必须设计覆盖设计程序，以便在任何时候仅一部分程序需要位于主存中。当一个需要的模块不存在的时候，用户程序必须加载这个模块进入到这个程序的分区，并覆盖其中的所有数据或者数据。
- 主存利用率极低。任何程序，无论这个程序本身有多大，都需要占据一整块分区。如果一个程序只需要小于2Mb的空间，但是却占了8Mb的主存空间。这种加载的数据块小于分区，而造成分区内部空间的浪费，被称为内部碎片。
通过使用不相等大小的分区，可以解决这两个问题，尽管并不能解决（图7.2b）。 在此示例中，最大可容纳16 MB的程序而没有覆盖。 小于8 MB的分区允许以较小的内部碎片容纳较小的程序。
放置算法
对于等大小的分区，进程在内存中的放置是极其简单的。只要存在一个足够大的分区，一个进程就可以被加载到那个分区。由于所有的分区都是等大小的，所以对于进程而言，用哪个分区都是一样的。如果所有的分区都被进程占满，并且都没有准备运行或者在运行，其中一个进程必须为新进程让出空间，交换哪个进程属于调度的问题。
对于不等大小的分区，有两种可能的方法来将进程分配给分区。最简单的方法就是，将进程分配给最小的分区（大于进程所需大小）。在这种情况下，每个分区都需要一个调度队列，以保存发往该分区的换出进程。这种方法的优点是，始终以最小化分区内的内存浪费（内部碎片）的方式分配进程。
尽管从单个分区的角度来看，此技术似乎是最佳的，但是从整个系统来看，这并不是最佳的。在图7.2b中，例如，在某个时间点上，没有进程的大小是在12Mb-16Mb之间的情况。在这种情况下，即使可能已为其分配了一些较小的进程，但是该16Mb的分区将一直保持未使用状态（资源浪费）。所以，一种更好的方式是对所有的进程使用单个队列。当需要加载一个进程进主存的时候，将选择可以容纳该进程的最小可用分区。如果所有的分区都被占用了，则可以实施后续的交换策略，可能会换出最小的分区来加载新的进程。同样也需要考虑其他因素，例如优先级，或者优先换出阻塞的进程还是就绪的进程。
不等大小分区的使用为固定分区提供了一定程度的灵活性。另外可以说固定分区方案相对简单，并且需要最少的OS软件和软件开销，但同时也存在着一些缺点：
- 在系统生成时指定的分区数量限制了系统中活动（非挂起）进程的数量；
- 由于分区的大小是系统生成时预先设置的，所以小型任务将无法有效的利用分区空间。在实现知道需要加载那些进程的主存需求的环境下，这也许是合理的，但是在大多数情况下，这是一种低效的技术。
如今，几乎没有使用固定分区的方法。使用该方法的成功的操作系统案例是早期的IBM大型操作系统OS/MFT（具有固定数量任务的多重任务）。
动态分区
为了解决固定分区带来的问题，动态分区技术由此发展。同样，这种方法已经被更为复杂的内存管理技术所取代。使用该技术的典型操作系统是IBM的大型机操作系统OS/MVT（具有可变任务数量的多程序编程）。
使用动态分区时，分区的长度和数量是可变的。当一个进程被加载到主存中，主存分配的空间和进程所需的空间一致。在图7.4中，主存的大小为64Mb。初始的时候，主存是空的，除了操作系统本身。起初三个进程被加载，从操作系统的结束地址开始，并为每个进程（b,c,d）分配足够的空间。但是留给第四个进程的空间就很少。在某个时间点，主存中没有进程在就绪。操作系统就会交换出进程2（e），留给进程4（f）。由于进程4所需的空间小于进程2，所以在分区之间留下了缺口。之后，主存中的进程都未就绪，但是处于准备挂起状态的进程2可用，但是留给进程2的内存不足，因此操作系统机会将进程1换出（g），将进程2换回（h）。
这种方法一开始可以很好的进行，但是会导致内存中存在许多小漏洞，随着进程的加载换出，内存变得越来越碎片化，利用率大大降低。分区之间的内存空缺被称为外部碎片。
克服外碎片问题的一种技术是紧凑：操作系统会不时的对进程进行移位，并且可用内存都在一个内存块中。对于图7.4h，经过紧凑后，可以得到16Mb的空闲内存块，足以加载其他的进程。但这种紧凑技术是耗时的，影响处理器时间（紧凑技术需要用到重定位技术）。
放置算法
由于内存压缩是耗时的，操作系统设计者必须设计分配规则（如何填补缺口漏洞）。当需要加载或者交换一个进程进入到主存中，并且存在足够大小的空闲内存块，操作系统就会决策分配哪一个空闲内存块。
Best-fit
选择内存大小大于进程内存大小且差值最小的内存块。
First-fit
选择第一个内存大小大于进程大小的内存块。
Worst-fit
优先选择最大的空闲块
Next-fit
从最后一个放置的位置开始扫描内存，并选择下一个足够大的可用内存块
图7.5a显示了多次放置和换出操作后的主存分区。最后使用的块是一个22Mb的内存块，从中创建了14Mb的分区。图7.5b显示了在满足16Mb分配请求时，First-fit、Best-fit、Next-fit放置算法之间的差异。Best-fit搜索了整个列表中的可用内存块，并使用了18Mb的内存块，剩下2Mb的碎片。First-fit导致了6Mb的碎片。Next-fit导致了20Mb的碎片。至于哪种方法是最好的，取决于发生的进程交换的确切顺序及这些进程的大小。