操作系统中的内存管理：内存分配算法（连续内存分配） 1. 问题描述 连续内存分配是早期操作系统管理物理内存的一种方式，其核心思想是为每个进程分配一块连续的内存空间。这种分配方式需要解决三个关键问题： 内存碎片 ：分配和释放内存后，剩余的小块内存可能无法被利用。 分配效率 ：如何快速找到合适的内存块分配给进程。 内存保护 ：防止进程越界访问其他进程的内存空间。 连续内存分配通常通过 动态分区分配 实现，即系统根据进程的实际需求动态划分内存分区。 2. 关键概念与数据结构 分区表 ：系统维护一张表，记录每个内存分区的起始地址、大小和状态（已分配/空闲）。 分配算法 ：决定从哪个空闲分区分配内存给进程。常见的算法包括首次适应（First Fit）、最佳适应（Best Fit）和最坏适应（Worst Fit）。 3. 分配算法的详细过程 （1）首次适应算法（First Fit） 原理 ：从内存低地址开始扫描分区表，找到 第一个 能满足进程需求大小的空闲分区。 示例 ： 假设空闲分区按地址顺序为：[ 10KB-30KB]、[ 40KB-80KB]、[ 100KB-150KB ]。 进程申请20KB内存： 扫描到第一个分区（10KB-30KB，大小20KB）符合要求，直接分配。 剩余分区更新为：[ 40KB-80KB]、[ 100KB-150KB ]。 优点 ：分配速度快，避免频繁扫描全表。 缺点 ：低地址可能产生大量小碎片（外部碎片）。 （2）最佳适应算法（Best Fit） 原理 ：扫描所有空闲分区，找到 大小最接近 进程需求的分区（避免浪费）。 示例 ： 空闲分区：[ 5KB-10KB]、[ 15KB-30KB]、[ 40KB-100KB ]。 进程申请12KB内存： 比较所有空闲分区：5KB（太小）、15KB（符合）、60KB（过大）。 选择15KB-30KB的分区（大小15KB），分配后剩余3KB碎片。 优点 ：减少内存浪费。 缺点 ：产生大量难以利用的小碎片，扫描全表效率低。 （3）最坏适应算法（Worst Fit） 原理 ：总是选择 最大的空闲分区 进行分配，目的是减少小碎片的产生。 示例 ： 空闲分区：[ 10KB-20KB]、[ 30KB-60KB]、[ 70KB-120KB ]。 进程申请25KB内存： 最大分区为70KB-120KB（大小50KB），分配后剩余25KB的空闲分区。 优点 ：避免分区被多次分割后变成小碎片。 缺点 ：大分区可能被耗尽，导致大进程无法分配内存。 4. 碎片问题与解决思路 外部碎片 ：多个小空闲分区分散在内存中，总和足够但无法合并分配。 解决 ：通过 内存压缩 （Memory Compaction）移动进程位置，合并空闲分区（需重定位进程地址）。 内部碎片 ：分配的分区大于进程实际需求，剩余部分被浪费（如固定分区分配）。 解决 ：采用动态分区分配，按需分配内存。 5. 总结与对比 | 算法 | 分配策略 | 优点 | 缺点 | |------------|-------------------|--------------------------|--------------------------| | 首次适应 | 第一个满足的分区 | 速度快 | 低地址碎片多 | | 最佳适应 | 最接近需求的分区 | 减少内部碎片 | 产生小碎片，效率低 | | 最坏适应 | 最大的分区 | 减少小碎片产生 | 可能无法分配大进程 | 连续内存分配后来被 非连续内存分配 （如分页、分段）取代，后者通过允许进程内存分散存放，从根本上解决了外部碎片问题。