操作系统基础31-连续内存分配
2020-12-19 03:40·重学IT的老猫
内存应容纳操作系统和各种用户进程，因此应该尽可能有效地分配内存。下面介绍一种早期方法：连续内存分配。 内存通常分为两个区域：一个用于驻留操作系统，另一个用于用户进程。操作系统可以放在低内存，也可放在高内存，这取决于中断向量的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统也放在低内存。因此，这里只讨论操作系统位于低内存的情况，其他情况的讨论也类似。 通常，我们需要将多个进程同时放在内存中。因此我们需要考虑，如何为输入队列中需要调入内存的进程分配内存空间。在采用连续内存分配时，每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。
内存保护
前面内存管理基础概念已经简单介绍过内存保护问题。结合前面操作系统基础30-内存交换，我们可以防止进程访问不属于它的内存。如果一个系统有重定位寄存器和界限寄存器，则能实现我们的目标。重定位寄存器含有最小的物理地址值，界限寄存器含有逻辑地址的范围值（例如，重定位=100040，界限=74600）。每个逻辑地址应在界限寄存器规定的范围内。MMU(内存管理单元)通过动态地将逻辑地址加上重定位寄存器的值，来进行映射。映射后的地址再发送到内存(如下图)。
重定位和界限寄存器的硬件支持
当CPU调度器选择一个进程来执行时，作为上下文切换工作的一部分，分派器会用正确的值来加载重定位寄存器和界限寄存器。由于CPU所产生的每个地址都需要与这些寄存器进行核对，所以可以保证操作系统和其他用户的程序和数据不受该运行进程的影响。 重定位寄存器方案提供了一种有效方式，以便允许操作系统动态改变大小。许多情况都需要这一灵活性。例如，操作系统的驱动程序需要代码和缓冲空间。如果一个驱动程序(或其他操作系统的服务)不常使用，可以不必在内存中保留它的代码和数据，这部分空间可以用于其他目的。这类代码有时称为暂时的操作系统代码，它们根据需要再调入或调出。因此，使用这种代码可以在程序执行时动态改变操作系统的大小。
内存分配
- 单一连续分配
内存在此方式下分为系统区和用户区。 系统区仅提供给操作系统使用，通常在低地址部分； 用户区是为用户提供的，除系统区之外的内存空间，我们平常运行的软件都在用户区里分配空间。
优点：无外部碎片，可以采用覆盖技术，不需要额外技术支持。 缺点：只能用于单用户，单任务操作系统中，有内部碎片，存储器利用率极低。
- 固定分区分配
最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后背作业队列中，选择适当大小的作业装入该分区，如此循环。
分区大小相等：用于利用一台计算机控制多个相同对象的场合，缺乏灵活性 。
分区大小不等：划分为含有多个较小的分区，适量的中等分区及少量的大分区。 优点：没有外部碎片。
缺点：程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存 空间。
主存利用率低，当程序小于固定分区大小时，也占用一个完整的内存分区空间，这样分区内部有空间浪费，这种现象称为内部碎片。
不能多个进程共享一个主存区。
- 动态分区分配
动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分配方式不会预先划分内存分区，而是在进程装入内存时, 根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
随着进程进入系统，它们将被加入输入队列。操作系统根据所有进程的内存需求和现有可用内存的情况，决定哪些进程可分配内存。当进程分配到空间时，它就加载到内存，并开始竞争CPU。当进程终止时，它将释放内存，该内存可以被操作系统分配给输入队列内的其他进程。任何时候，都有一个可用块大小的列表和一个输入队列。操作系统根据调度算法来对输入队列进行排序。内存不断地分配给进程，直到下一个进程的内存需求不能满足为止，这时没有足够大的可用块来加载进程。操作系统可以等到有足够大的空间，或者可以往下扫描输入队列，以确定是否有其他内存需求较小的进程可以被满足。 通常，如上所述，可用的内存块为分散在内存里的不同大小的块的集合。当新进程需要内存时，系统为该进程查找足够大的块。如果块太大，那么就分为两块：一块分配给新进程，另一块还回到块集合。当进程终止时，它将释放内存，该内存将还给块的集合。如果新块与其他块相邻，那么将这些块合并成大块。这时，系统可以检查，是否有进程在等待内存空间，以及新合并的内存空间是否满足等待进程等。这种方法是通用动态存储分配问题（根据一组空闲块来分配大小为 n 的请求）的一个特例。这个问题有许多解决方法。 从一组可用块中选择一个空闲块的最为常用方法包括：首次适应、最佳适应及最差适应：
- 首次适应：分配首个足够大的块。查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲块，就可以停止。
- 最佳适应：分配最小的足够大的孔。应查找整个列表，除非列表按大小排序。这种方法可以产生最小剩余块。
- 最差适应：分配最大的块。同样，应查找整个列表，除非列表按大小排序。这种方法可以产生最大剩余块，该块可能比最优适应产生的较小剩余块更为适用。
模拟结果显示，首次适应和最优适应在执行时间和利用空间方面都好于最差适应。首次适应和最优适应在利用空间方面难分伯仲，但是首次适应要更快些。
碎片
用于内存分配的首次适应和最优适应算法都有外部碎片的问题。 随着进程加载到内存和从内存退出，空闲内存空间被分为小的片段。当总的可用内存之和可以满足请求但并不连续时，这就出现了外部碎片问题：存储被分成了大量的小块，这个问题可能很严重。 在最坏情况下，每两个进程之间就有空闲(或浪费的)块。如果这些内存是一整块，那么可能可以再运行多个进程。 选择首次适应或者最优适应，可能会影响碎片的数量。(对一些系统来说，首次适应更好；对另一些系统，最优适应更好）。另一因素是从空闲块的哪端开始分配。(哪个是剩余的块，是上面的还是下面的？) 不管使用哪种算法，外部碎片始终是个问题。 根据内存空间总的大小和平均进程大小的不同，外部碎片问题或许次要或许重要。例如，采用首次适应方法的统计说明，不管使用什么优化，假定有N个可分配块，那么可能有0.5N个块为外部碎片。即1/3的内存可能不能使用。这一特性称为**50%**规则。 内存碎片可以是内部的，也可以是外部的。假设有一个18464 字节大小的孔，并采用多分区分配方案。假设有一个进程需要 18462 字节。如果只能分配所要求的块，那么还剩下一个 2 字节的块。维护这一小块的开销要比块本身大很多。因此，通常按固定大小的块为单位（而不是字节）来分配内存。采用这种方案，进程所分配的内存可能比所需的要大。这两个数字之差称为内部碎片，这部分内存在分区内部，但又不能用。
外部碎片问题的一种解决方法是紧缩。它的目的是移动内存内容，以便将所有空闲空间合并成一整块。然而，紧缩并非总是可能的。如果重定位是静态的，并且在汇编时或加载时进行的，那么就不能紧缩。只有重定位是动态的，并且在运行时进行的，才可采用紧缩。如果地址被动态重定位，可以首先移动程序和数据，然后再根据新基地址的值来改变基地址寄存器。如果能采用紧缩，那么还要评估开销。最简单的合并算法是简单地将所有进程移到内存的一端，而将所有的块移到内存的另一端，从而生成一个大的空闲块。这种方案比较昂贵。
外部碎片化问题的另一个可能的解决方案是，允许进程的逻辑地址空间是不连续的，这样，只要有物理内存可用，就允许为进程分配内存。有两种互补的技术可以实现这个解决方案：分段和分页。这两个技术也可以组合起来。 碎片是一个常见问题，当需要管理数据块时它就可能出现。