内存管理概念

本节介绍操作系统内存管理的不同方式，可能在选择题中考察，也可能在大题中作为知识点考察。

内存管理的基本概念

共享内存（Shared Memory）是多个进程共享的内存区域。它是最快的IPC（进程间通信）机制之一，因为进程直接读写内存，无需进入内核态。但是，因为多个进程可以同时访问这些内存，所以可能需要某种同步机制（如信号量）来防止竞态条件。

  • 内存保护

内存保护是现代操作系统中的一个核心功能，用于防止一个进程访问另一个进程的内存空间。这不仅保障了系统的稳定性，而且提高了安全性，因为它可以防止恶意软件损害其他进程或篡改其数据。

可以通过如下机制实现内存保护机制：

  1. 分段与分页:
    • 分段: 内存被划分为不同的段，每个段都有其起始地址和长度。段常常用于表示高级的数据结构，如函数或对象。
    • 分页: 内存被划分为固定大小的页面，例如4KB。操作系统为每个进程维护一个页表，来映射其虚拟地址到物理地址。
  2. 访问权限: 每个段或页面都有与之相关的访问权限。例如，一个页面可能被标记为只读，这意味着任何尝试写入该页面的操作都会引发一个异常。
  3. 隔离: 由于每个进程都有其独立的地址空间，所以一个进程不能直接访问另一个进程的内存。这为每个进程提供了一种形式的隔离，确保了一个出错的进程不会影响其他进程。

连续分配管理方式

单一连续分配

内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间都由该程序独占。

这种方式的优点是简单、无外部碎片，无需进行内存保护，因为内存中永远只有一道程序。缺点是只能用于单用户、单任务的操作系统中，存储器的利用率极低。

固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该内存，如此循环。

为了方便内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包含每个分区的起始地址、大小和状态。当有用户程序需要装入时，便检索该表，以找到合适的分区基于分配并将其状态设置为“已分配”；未找到合适分区时，则拒绝为给程序分配内存。

partition number
start address/KB
size/KB
status
1
20
20
allocated
2
32
32
allocated
3
64
64
not allocated
4
128
128
allocated

动态分区分配

动态分区分配的含义就是将内存看成一整块连续的区域，每次分配的时候直接从其中的空闲区域申请一块内存即可。

申请过的内存可以释放掉，成为空闲内存的一部分，释放后的内存可以被其他进程所用。

Free Memory
Free Memory
P1
Free Memory
P1
P2
Free Memory
P1
P2
P3
Free Memory
P1
P3
allocate mem for P1
allocate mem for P2
allocate mem for P3
free mem
for P2
allocate mem for P4
Free Memory
P1
P3
P4

通过对一段连续的内存进行动态地分配，内存中的区域可以从逻辑上被划分为空闲和占用两个部分。下图中的内核内存（kernel memory）以及进程内存（process memory）就是被占用的内存。

Kernel Memory
Kernel Memory
Process 1
Memory
Process 1...
Free Memory
Free Memory
Process 2
Memory
Process 2...
Free Memory
Free Memory
Process 3
Memory
Process 3...
Free Memory
Free MemoryText is not SVG - cannot display

操作系统可以通过一个表格的形式来记录以上空闲内存的大小和起始地址：

Start Address
Size
Index
0
0x12340000
40KB
1
0x12345000
30KB
2
0x22000000
128KB
Free Block Table

当进程申请内存时，操作系统会遍历空闲块表，根据设定的[#算法]选择出空闲块，然后为进程分配所需的内存空间。

内存碎片

由于每块进程申请的内存大小不同，所以在分配的内存之间可能出现内存碎片。

内存碎片就是大小比较小的空闲块，无法被其他进程再利用（进程不会申请这么小的空间）。

算法

内存空间中的空闲区域可能大小不一，且分布在内存中不同的位置，操作系统使用空闲块表来记录这些空闲区域的信息。

当进程申请一块新的内存时，必须从已有的空闲空间中选出一块分配给进程。动态分区的分配策略主要包含四种算法：first fit、next fit、best fit、worst fit。

  • First Fit（首次适应）：遍历空闲块表，找到第一个足够的空闲块分配给进程。
  • Next Fit（临近适应）：遍历空闲块表，找到第二个足够的空闲块分配给进程。
  • Best Fit（最佳适应）：遍历空闲块表，找到一个利用率最高的空闲块给进程。
  • Worst Fit（最坏适应）：与最佳适应的目标相反，找到一个利用率最低的空闲块给进程。
First Fit
First Fit
Next Fit
Next Fit
Worst Fit
Worst Fit
Best Fit
Best Fit
Allocated Block
Allocated Block
Free Block
Free Block
Possible New Block
Possible New Blo...
8
8
22
22
20
20
14
14
10
10
24
24
New Allocation of 16
New Allocation of 16Text is not SVG - cannot display

上图中内存中有 6 个空闲块，其大小分别为 8, 22, 20, 14, 10, 24，当进程申请一段大小为 16 的内存时，不同的算法会分别定位到不同的内存块：

  • First Fit：从上到下遍历空闲块，22 是第一个可以容纳 16 的块，选择 22。
  • Next Fit：20 是第二个可以容纳 16 的快，选择 20。
  • Best Fit：20 是能容纳 16 且利用率最高的块，利用率 = 16 / 20 = 80%，选择 20。
  • Best Fit：24 是能容纳 16 且利用率最低的块，利用率 = 16 / 24 ≈ 66.7%，选择 24。

应用场景

虽然上文举例的动态内存分配场景是进程向操作系统申请内存，但是在实际应用场景中，基本没有人这样子用。

动态内存分配最常见的场景就是进程堆上的内存分配，在 C 语言中可以通过 malloc 函数申请内存，并通过 free 函数释放内存，这里申请和释放的内存就是堆上的空闲内存块中的空间。

页式管理

页式管理的细节详见 组成原理中的对应章，这里仅给出基本的思想以与段式管理和段页式管理进行对比。

CPU
VPN
VPO
Valid
PPN
0
200
0
100
1
150
1
100
Kernel
Page 0
Virtual Address
0
1
2
3
Page Table
Main Memory
+
PBTR
PPN
VPO
Physical Address
Page 1
Page 2
Page N
Page N-1

页式内存管理的基本思想是将虚拟内存和物理内存分为若干个大小固定的页面，然后通过页表建立从虚拟页面到物理页面的映射，这样进程就可以离散地 使用物理内存中的不同页面。

段式管理

CPU
Segment Number
Offset
Base
Limit
1500
200
1800
100
1800
150
2400
100
Offset
< Limit
+
Kernel
Segment 0
Segment 1
Segment 2
Segment 3
Logical Address
0
1
2
3
NO
Trap
Segment Table
Main Memory
YES
+
SBPR

段式内存管理将程序的不同部分（例如代码、数据和堆栈）划分为不同的段（segments）。每个段在物理内存中可以不连续，但在逻辑上都被视为连续的。

段式管理的主要优点是它比较简单，有助于提供更好的保护和共享机制，在 8086 CPU 中使用的内存管理策略就是段式管理。

下文介绍一下段式内存管理中的三个关键概念：段、段表 以及 如何进行地址转化。

段定义

  • 每个段都有一个明确的角色，例如代码段、数据段或堆栈段。
  • 每个段都有一个起始地址和长度。
  • 段内的地址是连续的，但不同段之间的地址可以不连续。

段表

  • 段表是一种数据结构，用于存储每个段的基地址（在物理内存中的起始地址）和限制（段的长度或末尾地址）。
  • 当一个程序需要访问其内存段时，会使用段号和段内偏移作为地址。这个地址被称为逻辑地址或段地址。
  • 逻辑地址通过段表转换为物理地址。

地址转换

  • 为了从逻辑地址获取物理地址，首先需要从逻辑地址中提取段号，然后使用段号在段表中查找相应的基地址和限制。
  • 然后，检查逻辑地址中的偏移量是否小于该段的限制。如果偏移量超出限制，则产生段越界错误。
  • 如果偏移量有效，则将偏移量加到段的基地址上，得到物理地址。

段页式管理

段页式管理（paged segmentation）是一种将段式内存管理与分页式内存管理相结合的策略。 在段页式管理中，程序首先被划分为逻辑上的段，然后每个段进一步被划分为固定大小的页。 首先，操作系统通过段表对不同的段进行管理。 在每一个段的内部，采用分页的方式将段分为不同的页，实现虚拟页面到物理页面的映射。

Base
Page Table Base
*
*
*
*
*
*
CPU
Segment
No
Page
No
Offset
+
PTBR
+
Frame
No
Offset
Logical Address
Segment Table
Page Table 0
Page Table 1
Physical Address

在使用段页式内存管理的策略时，虚拟地址可以拆分为三个部分：段号（Segment No）、页号（Page No）、页内偏移（Offset）。

在地址翻译的过程中，首先通过虚拟地址中的段号在段表中找到页表的起始地址，接下来再通过页号在页表中找到该地址对应的物理页面号。

它结合了两者的优势，旨在提供灵活性和减少内存碎片。