基本概念：地址重定位relocation（地址转换、地址映射、地址翻译）

已经了解的：
程序装载到内存才可以运行。通常，程序以可执行文件格式保存在磁盘上
多道程序设计模型
允许多个程序同时进入内存
每个进程有自己的地址空间

• 一个进程执行时不能访问另一个进程的地址空间
• 进程不能执行不适合的操作

Paste_Image.png

讨论：

• 进程中的地址不是最终的物理地址
• 在进程运行前无法计算出物理地址，因为不能确定进程被加载到内存什么地方

需要地址重定位的支持（地址转换、地址变换、地址翻译、地址映射）Translation Mapping

地址重定位
逻辑地址（相对地址，虚拟地址）
用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余地址都相对于首地址而编址。
不能用逻辑地址在内存中读取信息

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

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

Paste_Image.png

物理内存管理（位图法、空闲区表、空闲区链表）
空闲内存管理
数据结构：

• 位图： 每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）
• 空闲区表、已分配区表：表中每一项记录了空闲区（或已分配区）的起始地址、长度、标志
• 空闲块链表

内存分配算法：

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

将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区

Paste_Image.png

Paste_Image.png

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

伙伴系统 BUDDY SYSTEM
一种经典的内存分配方案，主要思想：将内存按2的幂进行划分，组成若干空闲块链表；查找该链表找到能满足进程需求的最佳匹配块
Linux底层内存管理采用，一种特殊的分离适配算法
算法：

• 首先将整个可用空间看作一块：2^U
  假设进程申请的空间大小为s，如果满足2^u-1 <s<= 2^u 则分配整个块，否则，将块划分为两个大小相等的伙伴，大小为2^u-1
  一直划分下去直到产生大于或等于s的最小块

Paste_Image.png

基本内存管理方案1：整个进程进入内存中一片连续区域

Paste_Image.png

Paste_Image.png

固定分区：

• 把内存空间分割成若干区域，称为分区
• 每个分区的大小可以相同也可以不同
• 分区大小固定不变
• 每个分区装一个且只能装一个进程

Paste_Image.png

Paste_Image.png

碎片问题解决
碎片：很小的，不易利用的空闲区，导致内存利用率下降
解决方案：紧缩技术（memory compaction）
在内存移动程序，将所有小的空闲区合并为较大的空闲区
又称：压缩技术、紧致技术、搬家技术
紧缩时要考虑的问题：系统开销，移动时机

基本内存管理方案2：一个进程进入内存中若干片不连续的区域
页式存储管理方案
设计思想

• 用户进程地址空间被划分为大小相等的部分，称为页（page）或页面，从0开始编号
• 内存空间按同样大小划分为大小相等的区域，称为页框（page frame），从0开始编号，也成为物理页面，页帧，内存块
• 内存分配（规则）：以页尾单位进行分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻
• 典型页面尺寸：4K或4M

Paste_Image.png

Paste_Image.png

Paste_Image.png

相关数据结构及地址转换：
页表

• 页表项：记录了逻辑页号与页框号的对应关系
• 每个进程一个页表，存放在内存
• 页表起始地址保存在何处？（寄存器）

空闲内存管理
地址转换（硬件支持）
CPU渠道逻辑地址，自动划分为页号和页内地址；用页号查页表，得到页框号，再与页内偏移拼接成为物理地址

段式存储管理方案
设计思想：

• 用户进程地址空间：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名
• 内存空间被动态划分为若干长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定

• 内存分配（规则）：以段位单位进行分配，每段在内存中占据连续空间，但各段之间可以不相邻

  
  
  Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

交换技术SWAPPING
内存不足时如何管理？
内存扩充技术：内存紧缩技术（例如可变分区）
覆盖技术 overlaying 交换技术 swapping 虚拟存储技术virtual memory
覆盖技术OVERLAYING
解决的问题：程序大小超过物理内存总和
程序执行过程中，程序的不同部分在内存中相互替代，按照其自身的逻辑结构，将那些不会同时执行的程序段共享同一块内存区域
要求程序各模块之间有明确的调用结构
程序员声明覆盖结构，操作系统完成自动覆盖
主要用于早期的操作系统

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png