操作系统之存储管理

一、基本概念：地址重定位 1.1 需要了解的内容

• 程序装载到内存才可以运行

  通常，程序可以执行文件格式保存在磁盘上

• 多道程序设计模型

  允许多个程序同时进入内存

• 每个进程有自己的地址空间

  一个进程执行时不能访问另一个进程的地址空间

  进程不能执行不合适的操作

1.2 要解决的问题

说明： 在左边的单处理器系统中，如果一个进程想要运行，那么必须将进程地址空间装载到物理内存中才可以运行。 而右边的是多处理器系统中有多个进程需要进入物理内存执行，这里要解决的问题就是，如何将进程地址空间合理的装载到物理内存中，如何合理的分配使用内存，使得每个进程能正确执行。

1.3 复习：进程地址空间

1.4 注意

• 进程中的地址不是最终的物理地址
• 在进程运行前无法计算出物理地址

这就需要地址重定位来解决这些问题。

二、地址重定位

• 逻辑地址（相对地址、虚拟地址） 用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。
• 物理地址（绝对地址、实地址） 内存中存储单元的地址，可直接寻址

为了保证cpu执行指令时可以正确访问内存单元，需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址冲地位。

2.1 静态重定位与动态重定位

• 静态重定位 当用户程序加载到内存时，一次性实现逻辑地址到物理地址的转换。 一般可由软件完成。
• 动态重定位(重点) 在进程执行过程中进行地址变换，即逐条指令执行时完成地址转换。 支持程序浮动 需要硬件部件支持，较为常用。

2.2 动态重定位实现

三、物理内存管理 3.1 空闲内存管理

**说明：**我们对物理内存有不同的划分，一种是等长的划分，一种是不等长的划分。

• 数据结构 1、位图 对于等长划分这种我们可以使用位图的方式。每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）。对于不等长的划分可以使用下面两种分配结构。 2、空闲区表、已分配区表 表中每一项记录了空闲区（或已分配区）的起始地址、长度、标志 3、空闲块链表

3.2 内存分配算法

这里我们使用空闲区表、已分配区表为例来说明内存分配算法。

• 首次适配first fit 在空闲区表中找到第一个满足进程要求的空闲区
• 下次适配next fit 从上次找到的空闲区处接着查找
• 最佳适配best fit 查找整个空闲区表，找到能够满足进程要求的最小空闲区
• 最差适配worst fit 总是分配满足进程要求的最大空闲区

当找到满足进程需求的空闲区表后，需要将空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。

3.3 回收问题

• 内存回收算法
  • 当某一块归还后，前后空闲空间合并，修改内存空闲区表。
  • 四种情况 上相邻、下相邻、上下都相邻、上下都不相邻

3.4 伙伴系统(重点)

这是Linux底层内存管理采用的一种方法

• 一种经典的内存分配方案，是一种特殊的分离适配算法
• 主要思想：将内存按2的整数次幂进行划分，组成若干空闲块表；查找该链表找到能满足进程需求的最佳匹配块。
• 算法
  • 首先将整个可用空间看作一块：2^U
    • 假设进程申请的空间大小为s， 如果满足2^(U-1)