跳到主要内容

交换技术和空闲空间管理

##container##
PixPin_2025-01-12_14-48-58.png

一、交换技术​

下面是一个交换过程:

##container##
PixPin_2025-01-12_15-02-11.png ##w600##

在系统运行的初期, 仅进程A被加载至内存中。随后, 进程B和进程C被创建或从磁盘中调入内存。在达到图d所示的状态时, 进程A被置换出内存并存储至磁盘。之后, 进程A再次被需要并重新加载回内存。值得注意的是, 在图g中, 进程A的位置已发生变化, 这意味着在加载过程中必须对其进行重新定位。这种重新定位可以通过两种方式实现: 一种是在交换程序时, 利用软件执行重定位; 另一种是在程序执行期间, 通过硬件实现动态重定位。

为了支持这种重定位机制, 通常会使用基址寄存器和变址寄存器。基址寄存器存储了程序在内存中的起始地址, 而变址寄存器则用于计算程序内部各部分的相对地址。例如, 如果进程A原本位于内存的某个位置, 但后来被置换到磁盘并在不同位置重新加载, 此时基址寄存器会更新为新的起始地址。当程序需要访问某个变量或函数时, 变址寄存器会计算出该变量或函数相对于基址寄存器的偏移量, 从而确定其在内存中的确切位置。

通过这种方式, 系统能够灵活地管理内存中的进程, 确保即使进程被置换出内存并重新加载, 也能正确地执行其代码和数据访问操作。

##container##
PixPin_2025-01-12_15-05-34.png ##w600##

交换操作在内存中会产生多个“空闲区”(holes), 为了更有效地利用这些空闲空间, 一种技术是将所有的空闲区尽可能地向低地址移动并合并成一个大的空闲区, 这一过程被称为“内存紧缩”(memory compaction)。然而, 这项技术在实际应用中并不常用, 因为它会消耗大量的CPU时间。以一台拥有16GB内存的机器为例, 如果每8纳秒复制8字节数据, 那么紧缩整个内存的过程大约需要16秒的时间, 这对于大多数实时或高性能应用来说是不可接受的。

在进程管理领域, 另一个需要仔细考虑的问题是: 当进程被创建或换入内存时, 应该为其分配多少内存空间。对于大小固定且不再改变的进程, 分配策略相对简单, 操作系统只需按照其所需的确切大小进行分配即可。

然而, 当进程的“数据段”(data segment)能够动态增长时, 问题就变得复杂了。例如, 进程可能会通过动态分配堆内存来扩展其数据段。在这种情况下, 如果操作系统在进程创建或换入时为其分配的内存空间不足, 那么进程在运行过程中可能会因为内存不足而失败。相反, 如果分配了过多的内存空间, 又会造成内存资源的浪费。

所以内存针对自动增长区域的处理方式主要有以下三种:

1.1 相邻空闲区分配​

当一个进程需要增大其内存空间, 且其相邻区域存在空闲内存时, 系统会将该空闲区分配给该进程, 以满足其增长需求。

例如, 如果进程A当前占用内存块1-4, 而内存块5是空闲的, 当进程A请求增长时, 内存块5可以被分配给进程A, 使其扩展到内存块1-5。

1.2 进程重定位或交换​

若进程相邻的是另一个进程而非空闲区, 系统有两种策略来处理增长需求:

  • 进程重定位: 将需要增长的进程移动到一个具有足够空闲内存的区域。例如, 进程B(占用内存块6-10)需要增长, 但相邻的进程C(占用内存块11-15)阻碍了其增长。此时, 系统可以将进程B移动到另一个空闲区域(如内存块20-24), 并在原位置释放足够的空间供其他进程使用。

  • 进程交换: 将一个或多个相邻的进程交换到磁盘上的交换区, 以在内存中生成一个大的空闲区。继续以进程B和C为例, 如果系统决定通过交换来释放空间, 它可能会将进程C交换到磁盘, 从而在内存中为进程B的增长腾出足够的空间。

1.3 挂起或终止进程​

在极端情况下, 如果进程在内存中无法增长, 并且磁盘上的交换区也已满, 系统将面临内存不足的问题。此时, 系统可能会采取以下措施之一:

  • 挂起进程: 将进程置于挂起状态, 等待内存资源变得可用。这通常意味着进程的执行被暂停, 直到有足够的内存空间或交换区空间为止。

  • 终止进程: 如果系统无法等待内存资源变得可用, 或者进程的增长不再被认为是必要的, 系统可能会选择终止该进程, 以释放其占用的内存资源。

通过这些策略, 操作系统能够在有限的内存资源条件下, 尽可能地保证各个进程的正常运行, 同时维持系统的稳定性和响应性。

例如, 在多任务环境中, 当用户试图打开一个大型的应用程序(如Adobe Photoshop), 而当前内存不足以支持其运行时, 系统可能会自动缩小其他非活跃应用程序的内存占用, 或者将它们暂时保存到磁盘, 以此来为新程序腾出足够的空间。

##container##
PixPin_2025-01-12_15-11-12.png ##w500##

在之前的讨论中, 我们主要关注了单个或少数进程在运行时需要增长内存的情况, 并介绍了相应的处理方式。然而, 在实际系统中, 如果大部分进程都有可能在运行时增长, 那么频繁地因内存区域不足而引起的进程交换和移动将会带来巨大的开销。为了减少这种开销, 一种高效的方法是, 在进程被换入内存或移动位置时, 为其 预先分配一些额外的内存空间, 以应对 未来 可能的增长需求。

这种方法的核心思想是, 通过预测和预留内存空间, 来减少因进程增长而导致的内存重新分配和进程移动的次数。具体来说, 当进程首次被加载到内存中时, 或者当需要移动进程以腾出更多连续空间时, 系统会为其分配一个比当前需求稍大的内存块。这个额外的内存空间被称为“增长空间”, 它允许进程在不需要立即进行内存重新分配或进程移动的情况下, 满足一定范围内的增长需求。

然而, 当进程被换出到磁盘上时, 我们并不需要将为其预留的增长空间也一并交换出去。这是因为, 交换出未使用的内存空间是一种资源浪费。因此, 在进程被换出时, 系统应该只交换出那些 实际上被进程使用的内存页面, 而保留增长空间以供未来可能的重新加载和增长使用。

为了更直观地理解这种方法, 我们可以考虑以下内存配置示例:

假设有两个进程A和B, 它们都有可能在运行时增长。在初始加载时, 系统为进程A分配了10个内存页面的空间(其中5个页面为实际使用, 5个页面为增长空间), 为进程B分配了8个内存页面的空间(其中4个页面为实际使用, 4个页面为增长空间)。

这样, 即使进程A和B在未来需要增长, 系统也可以在不需要立即进行内存重新分配或进程移动的情况下, 满足它们的增长需求。而当这两个进程中的任何一个被换出到磁盘上时, 系统只会交换出那些实际上被使用的内存页面, 从而避免了不必要的资源浪费。

通过这种方法, 系统可以更有效地管理内存资源, 减少因进程增长而引起的开销, 并提高整体系统的性能和稳定性。

| ##container## | |:--:| |PixPin_2025-01-12_15-14-58.png ##w500##|

在一个复杂的系统架构中, 进程通常会包含多个可增长的内存段, 以满足其动态的内存需求。以两个常见的内存段为例: 一个是用于变量动态分配和释放的“数据段”(通常也称为堆, 用于存储全局变量等), 另一个是存放局部变量、函数参数以及返回地址的“堆栈段”。

在图b所展示的系统架构中, 我们可以清晰地看到这种内存布局。堆栈段位于进程所占内存的顶端, 并向下增长; 而数据段则紧随其后, 位于程序段之后, 并向上增长。这种布局方式有助于系统高效地管理内存资源, 确保进程在运行时能够动态地分配和释放内存。

值得注意的是, 为了应对进程可能的增长需求, 系统通常会为这两个内存段预留一定的增长空间。在图b中, 这可以通过B堆栈的增长预留区域来体现。B堆栈不仅负责为数据段预留增长空间(如B数据所示), 还通过其增长预留机制来确保数据段在需要时能够顺利扩展。同样地, A堆栈虽然在这个场景中用于处理操作系统相关的任务(如A程序所示), 但也可能包含类似的增长预留机制来应对操作系统的内存需求。

然而, 当预留的增长空间不足以满足进程的实际增长需求时, 系统就需要采取相应的处理措施。这些措施可能包括: 重新分配内存空间、利用虚拟内存技术来扩展物理内存、或者触发内存不足的错误并提示用户进行相应的处理。这些处理方式与上面提到的“流程图(data segment 自动增长的三种处理方式)”中的策略相似, 都是系统为了应对内存增长需求而采取的有效手段。

举个例子, 如果进程在执行过程中需要动态分配更多的内存来存储全局变量, 而数据段的预留增长空间已经不足, 那么系统可能会尝试从物理内存中分配更多的空间给数据段。如果物理内存也不足, 系统可能会利用虚拟内存技术, 将数据段的一部分暂时存储在磁盘上, 以释放物理内存空间供其他进程使用。这些复杂的内存管理机制都是现代操作系统为了提供高效、稳定的内存服务而设计的。

二、空闲内存管理​

在进行内存动态分配时, 操作系统必须对其进行管理。大致上说, 有两种监控内存使用的方式:

  • 位图(bitmap)
  • 空闲列表(free lists)

2.1 使用位图的存储管理​

在探讨内存管理策略时, 我们常采用位图方法。此方法将内存划分为一系列分配单元, 这些单元的大小可能各异, 从小至几个字节到大至几千字节不等。每个分配单元均与位图中的一个特定位相对应。在位图中, 0通常代表该单元处于空闲状态, 而1则意味着该单元已被占用(当然, 也存在相反的表示方式)。

##container##
PixPin_2025-01-12_15-21-32.png ##w700##

以图a为例, 它形象地展示了一段内存, 其中包含了5个进程(由P标识)和3个空闲区(在图中以阴影部分呈现, 同时在位图中以0标记)。此图的刻度代表内存分配单元, 使我们能够清晰地看到内存的分配与使用情况。

位图(如图b所示)则提供了一种紧凑的方式来表示这种内存使用情况。每一位都对应着一个分配单元的状态, 从而使我们能够快速地了解哪些单元是空闲的, 哪些已被占用。

值得注意的是, 分配单元的大小对于位图的设计至关重要。分配单元越小, 所需的位图就越大, 因为需要更多的位来精确地表示每个单元的状态。然而, 即使分配单元的大小仅为4字节, 对于32位的内存系统而言, 也仅需位图中的1位来标记其状态。换句话说, 对于一个包含 32n32n 位的内存系统, 我们仅需要 nn 位的位图来追踪其状态。这意味着, 在位图方法中, 位图本身所占用的内存比例是相当低的, 仅为总内存的 132\frac{1}{32} 。

但是, 如果进程的大小并非分配单元的整数倍, 那么在最后一个分配单元中可能会出现内存浪费的情况。例如, 若分配单元为16字节, 而某个进程的大小为45字节, 则它在占用3个完整的分配单元后, 还会占用第四个单元的一部分, 而该单元的剩余部分则会被浪费。

位图方法因其简单性而备受青睐, 它允许我们在固定大小的内存中精确地跟踪内存的使用情况。然而, 这种方法也存在一个显著的缺点: 当需要为包含 kk 个分配单元的进程分配内存时, 内存管理器必须遍历位图, 寻找一个连续的0串(即空闲区域)来容纳该进程。这一操作可能非常耗时, 特别是在位图较大且空闲区域分布较为零散时。这可以类比为在杂乱无章的数组中查找一段连续的空闲数组单元, 是一项颇具挑战性的任务。

2.2 使用链表进行管理​

在内存管理的领域中, 除了位图方法外, 还有一种广泛采用的技术是通过维护一个链表来记录内存的使用情况。这个链表由一系列的内存段组成, 每个段可以是一个已被进程占用的内存区域, 也可以是两个进程之间的空闲内存区域。这种方法允许我们以一种灵活且动态的方式追踪内存的分配与释放情况。

##container##
PixPin_2025-01-12_15-21-32.png ##w700##

以图c为例, 它生动地展示了如何通过链表来表示内存的使用情况。在这个链表中, 每一项都承载着特定的信息, 这些信息包括: 该内存段是空闲区(H)还是进程(P)的起始标志、该段的长度以及指向链表中下一个项的指针(或引用)。

// 可能的链表结构体
struct Node {
    enum {
        Hole,
        Process,
    } flag;     // 是 Hole(空闲) 还是 Process(进程)
    int starts; // 起始位置
    int length; // 长度
    Node* next;
};
C++

在这个示例中, “段链表(segment list)”是按照内存地址进行排序的。这种排序方式的显著优点是, 在进程终止或被系统交换出内存时, 更新链表的操作变得相对简单。通常情况下, 一个终止的进程(除非它位于内存的顶部或底部)会有两个相邻的实体, 这些相邻实体可能是其他进程, 也可能是空闲的内存区域。具体来说, 这些相邻实体与终止进程的组合方式存在四种可能性。

  1. 两个相邻实体均为进程:

    举例: 假设进程P1(已终止)被进程P2和进程P3所包围。在这种情况下, 我们需要从段链表中移除进程P1的节点, 并可能需要调整进程P2和进程P3的相邻指针, 以确保链表的连续性。

  2. 一个相邻实体为进程, 另一个为空闲区:

    举例: 进程P1(已终止)的一侧是进程P2, 另一侧则是空闲内存区域M1。此时, 我们需要移除进程P1的节点, 并检查是否可以将进程P2与空闲区域M1合并(如果它们相邻且合并后符合内存管理的策略)。

  3. 一个相邻空闲区, 另一个为进程(与第二种情况类似, 只是空闲区和进程的相对位置不同):

    举例: 进程P1(已终止)的一侧是空闲内存区域M1, 另一侧是进程P2。处理方式与第二种情况相同, 只是合并操作可能发生在进程P2与空闲区域M1之间。

  4. 两个相邻实体均为空闲区:

    举例: 进程P1(已终止)被两个空闲内存区域M1和M2所包围。在这种情况下, 我们需要移除进程P1的节点,

##container##
PixPin_2025-01-12_15-33-23.png ##w500##

2.3 内存适配算法​

2.3.1 首次适配算法​

在内存管理中, 当进程和空闲区按照地址顺序存储在链表中时, 为创建的进程(或从磁盘换入的进程)分配内存可以采用多种算法。这里, 我们假定内存管理器已明确知道所需分配的内存大小。在这些算法中, 最简单且常用的一种是“首次适配(First Fit)”算法

首次适配算法的工作原理如下: 内存管理器会沿着空闲区的链表从头开始扫描, 直到找到一个足够大的空闲区来满足当前的内存分配请求。如果找到的空闲区大小恰好等于所需分配的空间大小, 那么整个空闲区将被分配给该进程。然而, 在大多数情况下, 找到的空闲区可能会比所需空间稍大。此时, 内存管理器会将这个空闲区分为两部分: 一部分用于满足当前进程的内存需求, 另一部分则作为新的空闲区保留在链表中。

首次适配算法之所以被认为是一种速度较快的算法, 是因为它一旦找到满足条件的空闲区就会立即停止搜索, 而无需遍历整个链表。这种“尽早停止”的策略有效减少了搜索时间, 从而提高了内存分配的效率。

2.3.2 下次适配算法​

首次适配算法的一个变体是“下次适配(Next Fit)”算法。这两种算法在寻找空闲区以分配内存时的基本工作原理是相似的, 但存在一个关键的区别: 下次适配算法在每次成功找到并分配了一个空闲区后, 会记录当前的位置(即上次搜索结束的点), 以便在下一次寻找空闲区时从该点继续搜索, 而不是像首次适配算法那样每次都从链表的头部开始搜索。

具体来说, 首次适配算法会从头开始扫描整个链表, 直到找到一个足够大的空闲区来满足当前的内存分配请求。而下次适配算法则在首次成功分配后, 利用之前记录的位置作为新的起点, 继续沿链表搜索下一个可用的空闲区。这种策略旨在减少重复搜索已经检查过的空闲区的开销, 尤其是在链表较长且空闲区分布较为均匀的情况下。

然而, 尽管下次适配算法试图通过优化搜索路径来提高效率, 但根据Bays(1997)的研究, 下次适配算法的整体性能通常略低于首次适配算法。这可能是因为下次适配算法在搜索过程中可能会陷入局部最优解, 即连续多次从同一位置开始搜索, 导致未能及时找到全局最优的空闲区。

2.3.3 最佳适配算法​

另一个广为人知且广泛应用的内存分配算法是“最佳适配(Best Fit)”算法。与首次适配算法不同, 最佳适配算法在扫描整个链表时, 会寻找能够容纳进程的最小空闲区, 以确保匹配请求和可用空闲区之间的最佳匹配。这种策略旨在避免拆分可能在未来需要用到的大空闲区。

假设我们有一个内存空闲区链表, 其中包含多个不同大小的空闲区。当我们需要为一个进程分配内存时, 最佳适配算法会找到最小的空闲区来满足请求。然而, 如果这个空闲区只比所需内存稍大, 那么分配后剩余的空闲区就会非常小, 可能无法再用于满足其他进程的内存请求, 从而造成内存浪费。

2.3.4 最差适配算法​

为了避免最佳适配算法产生大量小缓冲区的问题, 可以考虑使用最差适配算法。最差适配算法总是分配最大的内存区域给进程, 从而确保新分配的空闲区比较大, 可以继续用于满足其他进程的内存请求。然而, 仿真程序表明, 最差适配算法也并非一个完美的解决方案。因为在实际应用中, 最大的空闲区可能并不总是最适合当前进程的, 而且频繁地分配大空闲区也可能导致内存碎片化的问题。

为了提高内存分配算法的速度, 我们可以为进程和空闲区分别维护 各自独立的链表。这样做的好处在于, 算法在检查空闲区以寻找合适的内存块时, 无需再考虑进程链表, 从而提高了分配效率。然而, 这种优化方法也带来了一定的代价。具体而言, 它增加了系统的复杂度, 并可能导致内存释放速度减慢。这是因为, 在内存释放过程中, 我们必须将一个已回收的内存段从进程链表中删除, 并将其正确地插入到空闲链表中的适当位置。

为了进一步优化最佳适配算法的速度, 我们可以对空闲区链表进行 排序, 使其按照内存块的大小从小到大排列。这样, 当最佳适配算法在搜索空闲区链表时, 一旦找到一个合适的内存块, 就可以确定这个内存块是能够满足当前请求的最小空闲区, 从而实现了最佳匹配。由于空闲区链表是以单链表的形式组织的, 因此在找到合适的内存块后, 算法无需进一步搜索。

排序后, 二分; (链表怎么二分...)

2.3.5 快速匹配算法​

另一种常用的内存分配算法是“快速适配(Quick Fit)”算法。该算法的核心思想是为那些常用大小的空闲区维护单独的链表, 以便在需要时能够快速找到并分配适当的内存块。具体来说, 快速适配算法会维护一个包含多个条目的表, 每个条目都指向一个特定大小的空闲区链表的表头指针。例如, 表的第一项可能指向大小为4KB的空闲区链表, 第二项指向大小为8KB的空闲区链表, 第三项指向大小为12KB的空闲区链表, 以此类推。

这种设计使得快速适配算法在寻找指定大小的空闲区时非常高效。当需要分配一个内存块时, 算法只需根据所需内存块的大小, 在表中查找对应的链表, 并从链表中取出一个空闲区进行分配即可。这种方法的优点在于减少了搜索空闲区所需的时间, 提高了内存分配的速度。

然而, 快速适配算法也存在一些缺点。与所有将空闲区按大小排序的方案一样, 快速适配算法在合并相邻空闲区时面临挑战。当一个进程终止或被换出时, 系统需要找到它的相邻块并查看是否可以合并。这个过程可能会非常耗时, 因为系统需要遍历多个链表来找到相邻的空闲区。如果不进行合并, 内存将会很快分裂出大量无法被进程利用的小空闲区, 导致内存碎片化的问题。

为了解决这个问题, 快速适配算法可能会采用一些额外的策略, 如使用专门的链表来存放大小比较特别的空闲区, 以便在处理这些空闲区时能够更加灵活。例如, 对于像21KB这样既不是4KB、8KB、12KB等常用大小, 又大于某个阈值的空闲区, 可以将其放入一个专门存放大小比较特别的空闲区链表中。这样, 在需要分配类似大小的内存块时, 系统可以快速地从该链表中获取空闲区, 而无需遍历整个空闲区链表。

然而, 即使采用了这些额外的策略, 快速适配算法仍然需要在合并相邻空闲区时付出一定的代价。因此, 在实际应用中, 需要根据具体的应用场景和需求来选择最合适的内存分配算法。

编辑此页
最后由 Heng_Xin_666 于 更新
请作者喝奶茶:
Alipay IconQR Code
Alipay IconQR Code
本文遵循 CC CC 4.0 BY-SA 版权协议, 转载请标明出处
Loading Comments...
0%