计算机存储以及连续内存分配

计算机内存层次

速度又高到低分别是寄存器、高速缓存、内存、外存。

处理器是从寄存器拿数据的，寄存器是从高速缓存拿数据的，但是在CPU中是看不到有高速缓存的存在，因为高速缓存是通过硬件（MMU）实现的，如果拿数据的时候高速缓存中没有，会进一步从内存中拿取。

内存中如果拿取不到数据，那就会通过操作系统的控制，从外存中拿取

操作系统的内存管理

MMU:在系统中，为了保证个进程拥有独立的存储空间，所以需要一个存储管理单元（MMU）

• 存储管理单元将线性的物理地址编号转换成抽象的逻辑地址空间
• 存储管理单元对地址空间要进行保护，保证上层进程只能访问自己的地址空间
• 在保护的同时，还要创建一块共享的存储空间，以保证相同数据不会重复存储
• 在以上的几个要求中还要实现给上层呈现出更大的地址空间

操作系统的内存管理方式

1. 重定位：即整个程序使用段地址和偏移地址实现，以保证在同类型的机器上都可以运行并不产生内存冲突
2. 分段: 将一个程序的各部分数据（代码，数据，栈等）分成块
3. 分页：将内存分成最基本的单位，使用的时候一个单位一个单位的分配
4. 虚拟存储：按页式虚拟存储，可以提供比实际内存大的虚拟存储空间

地址空间的定义

• 物理地址空间–硬件支持的地址空间
• 逻辑地址空间–在CPU的进程看到的地址（并不是真正的物理地址）

地址生成时机和限制

编译时：

• 假设起始地址已知
• 如果起始地址改变，必须重新编译

加载时：

• 如果编译时起始位置未知，编译器需生成可重定位的代码（relocatable code）
• 加载时，生成绝对地址

执行时：

• 执行时代码可移动
• 徐地址转换（映射）硬件支持

地址生成过程

1. CPU:
   
   1. ALU:需要的逻辑地址的内存内容
   2. MMU:进行逻辑地址和物理地址的转换
   3. CPU控制逻辑:给总线发送物理地址请求
2. 内存：
   
   1. 发送物理地址内容给CPU
   2. 接收CPU数据到物理地址
3. 操作系统
   
   1. 建立逻辑地址LA和物理地址PA的映射

地址检查

• 每次访问地址的时候每次检查你要访问的空间是否超过了你的段地址加偏移量，如果超过，则不允许访问并返回错误

连续内存分配

给进程分配一块不小于指定大小的连续的物理内存区域

内存碎片

空闲的内存不能被利用

• 外部碎片

  • 分配单元之间的未被使用的内存

• 内部碎片

  • 分配单元内部的未被使用的内存
  • 取决于分配单元大小是否要取整

动态分区分配

当程序被加载执行是，分配一个进程指定大小可变的分区（块、内存块）
分区的地址是连续的

操作系统需要维护的数据结构

所有进程的已分配分区
空闲分区(Empty-blocks)

动态分区分配策略

最先匹配(first-fit)

1. 内存的空闲分配信息按顺序排列
2. 分配过程时搜索第一个合适的分区
3. 释放分区时，检查是否可与临近的空闲分区合并（伙伴系统）

优点

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

缺点

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

最佳匹配(Best-fit)

1. 内存的空闲分区按照分区从小到大排列
2. 分配时从前往后找第一个大于所需空间的
3. 释放时同样查找并且合并临近的空闲分区（如果找到）（伙伴系统）

优点

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

缺点

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

最差匹配(Worst-fit)

1. 空闲分区列表由大到小排列
2. 分配时选最大的分区
3. 释放时检查是否可与临近的空闲分区合并，进行可能的合并并调整空闲分区列表（伙伴系统）

优点

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

缺点

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

碎片整理

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

碎片紧凑

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

• 碎片紧凑的条件

  • 所有应用程序可动态重定位

• 需要解决什么问题

  • 什么时候移动
  • 开销

分区对换（交换分区）

通过抢占并回收处于等待状态进程的分区，以增大可用内存空间
缺点：
&＃8211; 交换的开销可能会很大，因为内存和外存的速度差别很大，但是这种开销如果能解决多进程运行内存不够的问题的话，开销还是可以接受的。

伙伴系统

一张图讲清楚伙伴系统：