第五讲物理内存管理

初始化：假设初始内存大小为1MB。
分配请求：如果请求分配100KB（或128KB），系统将1MB块分为两个512KB块，再将512KB块分为两个256KB块，最终将256KB块分为两个128KB块，分配其中一个128KB块。
进一步分配：如果再请求分配240KB，系统将查找满足240KB的块，如果没有合适的块，则继续分割更大的块，直到找到合适的块。

内存释放与合并

释放内存块时，需要检查相邻的块是否也是空闲的，如果是，则将它们合并为更大的块。

合并示例

释放128KB块：释放时，检查相邻的128KB块是否也是空闲的，如果是，则将两个128KB块合并为一个256KB块。
进一步合并：如果再释放一个256KB块，则检查相邻的256KB块是否也是空闲的，如果是，则将它们合并为一个512KB块。

伙伴系统的优势

伙伴系统通过固定大小块和高效的分配与合并策略，减少了内存碎片，提高了内存利用率。

优势

减少外碎片：通过固定大小块，减少了不连续的小块空闲内存，从而减少外碎片。
快速分配和释放：利用链表和数组结构，可以快速查找、分配和释放内存块。
便于合并：固定大小块在释放时更容易合并，进一步减少碎片。

伙伴系统的缺点

尽管伙伴系统有许多优点，但也存在一些缺点，特别是内碎片问题。

缺点

内碎片：由于固定大小块的限制，分配的块可能比实际需要的大，导致内碎片。
合并复杂性：合并过程需要检查相邻块是否也是空闲的，增加了复杂性。

伙伴系统在操作系统中的应用

伙伴系统广泛应用于实际操作系统，如Linux和Windows，以实现高效的内存管理。

Linux内核中的伙伴系统

内存管理：Linux内核利用伙伴系统管理内存块，实现快速的内存分配和释放。
灵活性：Linux内核的伙伴系统支持多种内存块大小，满足不同应用的需求。

高效内存分配算法：Slab分配器

除了伙伴系统，另一个常用的高效内存分配算法是Slab分配器，特别适用于小块内存的分配。

Slab分配器

定义：Slab分配器是一种针对小块内存的高效分配算法，广泛应用于操作系统和应用程序中。
优点：减少内碎片，提高内存利用率，特别适用于频繁分配和释放的小块内存。

3. 非连续内存分配

3.1 非连续内存分配的概念

？

段式和页式内存管理

在操作系统中，内存管理的策略有多种，其中段式（Segmentation）和页式（Paging）内存管理是两种常见的方式。以下是对这两种内存管理方式的详细总结和扩展。

段式内存管理

段式内存管理是一种将内存划分为不同段的方式，每个段对应程序中的不同部分，如代码段、数据段等。

段式内存管理的基本概念

段：内存分为多个段，每个段包含一类数据，如代码段、数据段、堆栈段等。
段表：操作系统使用段表（Segment Table）来记录每个段的基址和长度信息。

段表结构

基址（Base Address）：段的起始地址。
长度（Limit）：段的长度。
访问控制信息：权限检查，用于判断访问是否合法。

段式内存管理的工作流程

地址转换：逻辑地址由段号和段内偏移组成。通过段号在段表中查找段的基址，再加上段内偏移得到物理地址。
权限检查：在访问内存时，硬件检查访问是否超出段的长度，并进行相应的权限检查。

bg right:71% 100%

操作系统的职责

段表管理：操作系统负责创建和维护段表，并在任务切换时加载正确的段表。
内存分配：操作系统根据程序的需求分配段，并在段表中记录段的信息。

优缺点

优点：段式管理可以实现内存的逻辑分段，便于程序的模块化和保护。
缺点：可能会导致外部碎片问题，内存分配和管理复杂。

页式内存管理

页式内存管理是一种将内存划分为固定大小的页的方式，每个页独立管理。

页式内存管理的基本概念

页框（Page Frame）：物理内存划分为固定大小的块，称为页框。
页（Page）：虚拟内存也划分为相同大小的块，称为页。
页表（Page Table）：操作系统使用页表记录每个虚拟页到物理页框的映射关系。

页表结构

页号（Page Number）：虚拟地址的高位部分，作为页表的索引。
页内偏移（Page Offset）：虚拟地址的低位部分，表示页内的具体地址。

页式内存管理的工作流程

地址转换：虚拟地址由页号和页内偏移组成。通过页号在页表中查找对应的页框号，再加上页内偏移得到物理地址。
权限检查：页表中包含访问权限信息，硬件在地址转换时进行权限检查。

操作系统的职责

页表管理：操作系统负责创建和维护页表，并在任务切换时加载正确的页表。
内存分配：操作系统根据程序的需求分配页，并在页表中记录页的映射关系。

优缺点

优点：页式管理可以有效解决外部碎片问题，内存分配灵活。
缺点：页表较大，可能导致页表管理的开销。

页表查找与内存管理单元（MMU）

页表查找

页表查找过程：通过页号在页表中查找对应的页框号，将虚拟地址转换为物理地址。
硬件支持：内存管理单元（MMU）负责实现页表查找和地址转换，操作系统提供页表内容。

快表（TLB）

快表：为了加速页表查找，使用转换后备缓冲（TLB）缓存最近的页表项。
TLB命中：如果TLB中有对应的页表项，直接使用，减少查找时间。
TLB未命中：如果TLB中没有对应的页表项，查找页表并更新TLB。

段页式内存管理

段页式内存管理结合了段式和页式管理的优点，将内存划分为段，每个段再划分为页。

段页式管理的结构

段表：记录每个段的基址和长度。
页表：每个段有一个页表，记录该段内每个页的映射关系。

段页式管理的优缺点

优点：结合了段式和页式管理的优点，实现内存的逻辑分段和灵活分配。
缺点：管理复杂度较高，页表和段表的维护开销大。

段式和页式内存管理是操作系统中两种重要的内存管理方式，各有优缺点。段页式管理结合了两者的优点，实现了更加灵活和高效的内存管理。理解这些内存管理方式的工作原理和应用场景，有助于深入掌握操作系统的内存管理机制。

bg right:71% 100%

页表性能问题与解决方案

页表（Page Table）是操作系统中管理虚拟内存的重要数据结构，它的性能和容量对系统性能有直接影响。以下是对页表性能问题及其解决方案的详细总结和扩展。

页表性能问题

性能瓶颈

内存访问延迟：由于页表位于内存中，访问页表需要额外的内存读取操作，这会导致性能下降。
页表容量大：在64位机器上，如果每页大小为4KB，单级页表的容量会非常大，存储所有的页表项需要大量内存空间。

容量计算示例

64位地址空间：假设每页大小为4KB（2^12字节），页表项大小为8字节（64位）。
单级页表：需要2^52个页表项（2^64 / 2^12），即需要2^52 * 8字节 ≈ 36PB的内存来存储单级页表。

性能提升方法

多级页表

为了减少单级页表的巨大内存需求，多级页表通过分级存储页表项，有效地减少了内存开销。

多级页表结构：通过分级存储页表项，每一级页表指向下一层的页表，从而减少了不必要的页表项存储。
示例：
- 二级页表：使用两级页表，第一级页表指向第二级页表。
- 三级页表：进一步分级，第一级页表指向第二级页表，第二级页表指向第三级页表。

多级页表的优缺点

优点：通过按需创建页表，减少了不必要的内存消耗，支持更大的虚拟地址空间。
缺点：多级页表增加了地址转换的复杂度，每次地址转换需要多次内存访问，导致性能下降。

TLB（Translation Lookaside Buffer）

为了缓解多级页表带来的性能问题，使用TLB（转换后备缓冲）来缓存最近使用的页表项。

TLB的作用：TLB是一个小型的、高速缓存，用于存储最近使用的页表项，减少频繁的内存访问。
TLB命中和未命中：
- 命中：如果TLB中存在所需的页表项，则直接使用，无需访问内存。
- 未命中：如果TLB中不存在所需的页表项，则需要访问内存中的页表，更新TLB。

w:1000

数据缓存（Cache）

除了TLB，数据缓存（Cache）用于缓存最近访问的数据，进一步提高内存访问的效率。

数据缓存的作用：缓存最近访问的数据，减少对内存的直接访问。
层级缓存：
- 一级缓存（L1 Cache）：速度最快，容量最小。
- 二级缓存（L2 Cache）：速度和容量介于一级缓存和内存之间。
- 三级缓存（L3 Cache）：速度较慢，容量较大。

操作系统的职责

操作系统需要负责页表和TLB之间的数据一致性，以及多级页表的管理。

数据一致性

一致性维护：确保页表和TLB中的数据一致，如果页表更新，需要同步更新TLB。
页表更新：操作系统在页表更新时，必须使相关的TLB条目失效，确保数据一致性。

多级页表管理

页表初始化：操作系统在进程创建时初始化页表，并在任务切换时加载正确的页表。
页表分配和回收：根据进程的内存需求，动态分配和回收页表项，优化内存使用。

解决方案总结

为了提升页表的性能和减少内存开销，操作系统采用多级页表和TLB缓存等技术。

多级页表：通过分级存储页表项，减少了不必要的内存消耗，但增加了地址转换的复杂度。
TLB缓存：通过缓存最近使用的页表项，减少了内存访问，提高了地址转换的速度。
数据缓存：通过层级缓存结构，进一步提升内存访问效率，减少了CPU对内存的直接访问。

页表性能问题是操作系统内存管理中的重要挑战，通过多级页表和TLB缓存等技术，可以有效提升页表性能和内存利用率。理解这些技术的工作原理和应用场景，有助于设计和实现高效的内存管理方案。

反置页表（Inverted Page Table）

反置页表是一种解决页表容量问题的少见方式，它通过反转查找顺序来减少页表的大小。以下是对反置页表的详细总结和扩展：

反置页表的基本概念

传统页表使用虚拟页号作为索引，查找物理地址。然而，反置页表则是使用物理页号作为索引，查找虚拟地址。

反置页表的工作原理

物理页号作为索引：反置页表将物理页号作为索引，查找虚拟页号及相关信息。
哈希机制：通过哈希机制将虚拟地址和进程ID映射到物理地址。

反置页表的查找过程

地址转换

虚拟地址和进程ID哈希：将虚拟地址和进程ID进行哈希计算，得到一个哈希值。
查找反置页表：使用哈希值作为索引，查找反置页表中的条目。
验证虚拟地址：如果找到的条目中的虚拟地址和进程ID与原始请求一致，则查找成功。
组合物理地址：将物理页号与页内偏移组合，得到物理地址。

反置页表的优势

反置页表相对于传统页表有一些明显的优势：

减少页表大小：反置页表的大小与物理内存大小相关，而不是虚拟地址空间的大小。
提高内存利用率：通过哈希机制和链表解决冲突，可以高效地管理内存。

反置页表的挑战

尽管反置页表有其优势，但也面临一些挑战：

哈希冲突：由于哈希函数的限制，不同的虚拟地址可能映射到相同的哈希值，需要处理冲突。
查找复杂性：反置页表查找涉及哈希计算和冲突处理，增加了查找的复杂性。

反置页表的查找与冲突处理

查找过程示例

初始查找：将虚拟地址和进程ID进行哈希计算，得到索引。
索引查找：使用哈希值作为索引，查找反置页表条目。
条目验证：检查条目中的虚拟地址和进程ID是否匹配，如果匹配，则查找成功。
物理地址生成：将物理页号与页内偏移组合，生成物理地址。

w:1000

冲突处理

链表解决冲突：如果哈希冲突（多个虚拟地址映射到相同哈希值），使用链表存储冲突条目。
链表查找：在冲突链表中查找匹配的虚拟地址和进程ID，找到后生成物理地址。

实例：PowerPC中的反置页表

反置页表在一些特定的架构中得到了应用，例如IBM的PowerPC 64位处理器。

PowerPC中的实现

反置页表结构：PowerPC使用反置页表来管理虚拟到物理地址的映射。
性能优化：通过硬件支持和优化的哈希函数，提高查找和冲突处理的效率。

性能优化

为了提高反置页表的性能，通常会采用一些优化技术：

硬件哈希支持：利用硬件加速哈希计算，提高查找速度。
缓存机制：使用TLB（转换后备缓冲）缓存最近使用的页表项，减少内存访问。
优化哈希函数：选择高效的哈希函数，减少冲突，提高查找效率。

反置页表是一种通过反转页表查找顺序来减少页表大小的技术，具有减少页表容量、提高内存利用率的优点，但也面临哈希冲突和查找复杂性的挑战。理解反置页表的工作原理和应用场景，有助于掌握操作系统中不同内存管理策略的优缺点和实现方法。

段式和页式内存管理的总结

在操作系统中，段式（Segmentation）和页式（Paging）内存管理各有特点和应用场景。以下是对段式和页式内存管理的总结及其在实际操作系统中的应用。

段式内存管理

段式内存管理将内存划分为逻辑上的段，每个段表示程序中的不同部分，如代码段、数据段等。

特点

逻辑分段：内存根据程序逻辑分为多个段，如代码段、数据段、堆栈段等。
段表管理：段表记录每个段的基址和长度信息，用于地址转换和权限检查。

优点

模块化：段式管理便于程序的模块化和数据保护。
灵活性：不同段可以有不同的权限和属性。

缺点

外部碎片：内存分配容易产生外部碎片，影响内存利用率。
复杂性：段表的管理和维护较为复杂。

页式内存管理

页式内存管理将内存划分为固定大小的页，所有页大小相同，便于管理。

特点

固定大小页：内存和虚拟地址空间都划分为固定大小的页（Page）。
页表管理：页表记录虚拟页到物理页的映射关系，用于地址转换。

优点

减少外部碎片：固定大小的页减少了内存中的外部碎片。
简单管理：页表管理相对简单，适用于大多数操作系统。

缺点

页表大小：对于大地址空间，页表可能非常大，占用大量内存。
内存访问延迟：页表查找需要多次内存访问，增加了内存访问延迟。

段页式内存管理

段页式内存管理结合了段式和页式的优点，内存划分为段，每个段再划分为页。

特点

段页结合：内存先划分为段，每个段再划分为页，段表和页表共同管理内存。
灵活管理：既有段的逻辑分段优点，又有页的固定大小管理优势。

优点

灵活性：段页式管理结合了段式和页式的优点，提供更灵活的内存管理。
模块化和减少碎片：既能实现模块化管理，又能减少外部碎片。

缺点

复杂性：管理和维护段表和页表的复杂性较高。

例子：malloc函数的内存分配过程

以C语言中的malloc函数为例，解释内存分配过程。

内存分配过程

程序加载：操作系统将程序加载到内存中，分配堆区域用于动态内存分配。
调用malloc：程序调用malloc函数请求分配内存。
libc库处理：malloc函数由C标准库（libc）实现，libc库管理堆内存的分配和释放。
堆内存管理：libc库在堆区域中查找空闲块，如果找到合适的块，则直接分配。
系统调用：如果堆中没有足够的空闲块，libc库通过系统调用（如sbrk）请求操作系统分配新的内存区域。
内存分配完成：操作系统分配新的内存区域后，libc库将新的内存块合并到堆中，满足malloc请求。

代码示例

#include <stdlib.h>

int main() {
    // 调用malloc函数请求分配内存
    int* ptr = (int*)malloc(10 * sizeof(int));
    
    // 检查内存分配是否成功
    if (ptr == NULL) {
        // 内存分配失败，处理错误
        return -1;
    }
    
    // 使用分配的内存
    for (int i = 0; i < 10; i++) {
        ptr[i] = i;
    }
    
    // 释放分配的内存
    free(ptr);
    
    return 0;
}

段式和页式内存管理各有优缺点，页式管理由于减少外部碎片和管理简单性，在现代操作系统中应用广泛。然而，段页式管理结合了两者的优点，提供了更加灵活和高效的内存管理方式。理解这些内存管理技术和实际应用，有助于深入掌握操作系统的内存管理机制和提高程序设计的效率和性能。

| rCore Series Notebook |