连续内存分配算法

发表于 分类于

计算机会经常有访问内存的操作，内存最小访问单位是字节，每个字节都有自己的物理地址，MMU将程序的逻辑地址转化为物理地址后访问对应的字节。为了处理在分配过程中分配大小和实际使用大小的差异，引入了内存分配算法。内存分配分为连续内存分配和不连续内存分配两种方式，这取决于分配的物理内存空间是否连续。

计算机体系结构

计算机体系结构由CPU、内存、I/O设备、总线组成。

CPU中包括：

  • ALU、控制逻辑
  • 寄存器
  • 高速缓存：加快读写速度
  • 存储管理单元（MMU）

内存层次：
内存的特点：

  • 最小访问单位是字节（8bit）
  • 一次可以读/写4字节（32位），有地址对齐问题

操作系统的内存管理方式

操作系统内存管理特点

  • 每个字节都有自己的物理地址
  • 分为内存和外存(硬盘)
  • 每个进程都有自己的内存空间，进程间的地址可以重叠
  • MMU：将逻辑地址(虚拟地址)转换为物理地址

内存管理方式

  • 重定位（relocation）：修改段寄存器地址
  • 分段（segmentation）：程序的逻辑结构不需要连成一片，而是分成代码、数据、堆栈3段；但每段的内容是连续的。
  • 分页（paging）：分配内存以页为最小基本单位
  • 虚拟存储（virtual memory）：目前多数系统（如Linux）采用的是按需页式虚拟存储

内存管理方式的实现高度依赖硬件

  • 与计算机存储架构紧密耦合
  • MMU(memory management unit) 处理CPU存储访问的硬件

地址空间和地址生成

地址重定位

静态地址重定位

即在程序装入内存的过程中完成，是指在程序开始运行前，程序中的各个地址有关的项均已完成重定位，地址变换通常是在装入时一次完成的，以后不再改变，故成为静态重定位。
优点：无需硬件支持
缺点：1）程序重定位之后就不能在内存中搬动了；2）要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域中。

动态地址重定位

在程序执行过程中进行地址重定位。更确切的说，是在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改而装入内存，但是它需要硬件(定位寄存器)的支持。
优点：1）目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行，这对于存储器紧缩、解决碎片问题是极其有利的；2）一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位寄存器就行。
缺点：需要硬件支持。

与物理地址、线性地址、逻辑地址对应，地址空间也有以下3种：

  • 物理地址空间：硬件支持的地址空间
    • 起始地址0
    • 到MAXsys
  • 线性地址空间：CPU看到的地址
    • 起始地址0
    • 大小取决于地址线的宽度
  • 逻辑地址空间：在CPU中运行的进程看到的地址
    • 起始地址0
    • 到MAXprog
    • 用户程序可见的地址

地址生成过程

逻辑地址的生成过程:

生成地址一般有以下几种选择：

  • 编译时（优点：简单）
    • 假设起始地址已知
    • 但如果起始地址改变，就必须重新编译
    • 功能手机一般会有这种情况
  • 加载时
    • 如果加载时起始位置未知，编译器需生成可重定位的代码（relocatable code）
    • 加载时，生成绝对地址
  • 执行时（优点：灵活）
    • 执行时代码可移动
    • 需地址转换（映射）硬件支持（一般是虚拟存储）

连续内存分配

连续内存分配即给进程分配一块不小于指定大小的连续物理内存区域。但是在分配过程中，分配大小和实际使用大小之前有差距，因此会有不能被利用的内存空间，即内存碎片。

内存碎片分为

  • 外部碎片 分配单元之间未被使用内存
  • 内部碎片 分配单元内部未被使用的内存 由于取整导致

连续内存分配的使用场景为动态分区分配，动态分区分配时需要满足以下要求：

  • 当程序被加载执行时，分配一个进程指定大小可变的分区（块）

  • 分区的地址是连续的

一般来说，操作系统需要维护至少2个数据结构，里面存储的内容是：

  • 所有进程的已分配分区
  • 空闲分区（Empty-blocks）

连续内存分配策略

常见的几种连续内存分配策略包括：

  • 最先匹配（First-fit）
  • 最佳匹配（Best-fit）
  • 最差匹配（worst-fit）

最先匹配（First Fit Allocation）策略

思路：需要分配n个字节时，使用第一个可用的空间比n大的空闲块

原理和实现：

  • 空闲分区列表按地址顺序排序
  • 分配时搜索第一个合适的分区
  • 释放分区时，检查是否可与邻近的空闲分区合并

优点：

  • 简单
  • 在高地址空间有大块的空闲分区

缺点：

  • 容易产生外部碎片
  • 分配大块时较慢

最佳匹配（Best Fit Allocation）策略

思路：分配n字节内存时，查找并使用不小于n的最小空闲分区

原理和实现：

  • 空闲分区列表按照大小排序
  • 分配时，查找一个合适的分区
  • 释放时，查找并合并邻近的空闲分区（如果找到）

优点：

  • 大部分分配的尺寸较小时，效果很好
    • 可避免大的空闲分区被拆分
    • 可减小外部碎片的大小
    • 相对简单

缺点：

  • 外部碎片较多
  • 释放分区较慢
  • 容易产生很多无用的小碎片

最先匹配会越用越慢吗？

最先匹配总是先找低地址空间的内存，到后期低地址空间都是大量小的不连续的内存空间，每次都要扫描低地址空间后到达高地质空间才能得到可用的内存。

最差匹配（Worst Fit Allocation）策略

思路：分配n字节时，使用尺寸不小于n的最大空闲分区

原理和实现：

  • 空闲分区列表按由大到小排序
  • 分配时，选最大的分区
  • 释放时，检查是否可与邻近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序

优点：

  • 中等大小的分配较多时，效果最好
  • 避免出现太多的小碎片

缺点：

  • 释放分区较慢
  • 外部碎片较多
  • 容易破坏大的空闲分区，因此难以分配大的分区

以上连续分配算法均会产生外碎片，而不产生内碎片。

最差匹配的外碎片会比最优适配算法少吗？

应该会的。因为每次都找到最大的内存块进行分割，因此分割剩下的内存块也很大，往往还可以再装下一个程序。

碎片整理

通过调整进程占用的分区位置来减少或避免分区碎片

碎片紧凑 (compaction)

通过移动分配给进程的内存分区 以合并外部碎片

  • 进行碎片紧凑的条件：所有的应用程序可动态重定位
  • 需要在应用程序等待时进行移动
  • 需要考虑开销

分区对换 (Swapping in/out)

通过抢占并回收处于等待状态进程的分区 存到外存里去 以增大可用内存空间

对换和紧凑都是碎片整理技术，它们的主要区别是什么？为什么在早期的操作系统中采用对换技术？

区别是，紧凑是在内存中搬动进程占用的内存位置，以合并出大块的空闲块；对换是把内存中的进程搬到外存中，以空出更多的内存空闲块。采用对换的原因是，处理简单。不过代价也比较高，因为外存比较慢。

伙伴系统

伙伴系统（Buddy System）是一种连续存储分配的办法，它解决了分配位置和碎片的问题。

伙伴系统的内存回收流程？

当释放多页的块时，内核首先计算出该内存块的伙伴的地址。内核将满足以下条件的三个块称为伙伴：

  1. 两个块具有相同的大小，记作$b$。
  2. 它们的物理地址是连续的。
  3. 第一块的第一个页的物理地址是$2*(2^b)$的倍数。

如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。