操作系统（二）内存分配

1.操作系统与设备和程序的交互

• 系统调用：应用程序主动向操作系统发出请求。发出点是同步，返回点可能是异步
• 异常：来源于不良的应用程序。非法指令或其他坏的处理状态（如：内存出错）。是同步的。
• 中断：不同硬件的计时器和网络中断。来源于外设。是异步的

异步：当一个事件产生时，应用程序不知道什么时候发生

对以上三种情况的响应：

• 系统调用：等待和持续
• 异常：杀死进程，或重新执行引起异常的程序指令
• 中断：持续，对应用程序是透明的。由操作系统来完成

2.用户态和内核态

这种切换在发生系统调用时产生。开销：

• 建立 中断/异常/系统调用 号与对应服务例程映射关系
• 建立内核堆栈（维护）
• 验证参数（安全上考虑）
• 用户态映射到内核态地址空间（更新页面映射权限）
• 内核独自地址空间（TLB）

3.CPU的组成

运算器（ALU），寄存器，控制器，缓存，MMU

4.物理地址分配/连续内存分配（没有引入逻辑内存）

缺点：内存利用率低；有内外碎片的问题

物理地址空间——硬件支持的地址空间：内存+硬盘

逻辑地址空间——一个运行的程序所拥有的地址范围

分配策略

I 首次适配/第一匹配分配/First Fit

为了分配n个字节，使用第一个尺寸比n个字节大的空闲快

需求：1. 按照地址排序的空闲快列表。2. 分配需要寻找一个合适的分区。3.重分配需要检查，看是否有相邻的空闲区域能否合并

• 优：简单；在地址空间的结尾易于产生较大的空闲块
• 劣：外部碎片；不确定性

II 最佳适配/Best Fit

与请求分配的尺寸差最小，并比请求分配的尺寸大

为了避免分割大的空闲块，为了最小化外部碎片产生的尺寸

需求：1. 按尺寸排列的空闲块列表。2和3相同

• 优：当大部分分配是小尺寸时；比较简单
• 劣：外部碎片（拆分得比较细）；重分配慢；易产生很多没有的细小碎片

III 最差适配/Worst Fit

最大可用空闲块；为了面有太多的微小碎片

需求：1.按照尺寸排列的空闲块列表。2.分配很快（获得最大的分区）。3.重分配合并相邻空闲块

• 优：分配是中等尺寸效果最好
• 劣：易于破碎大的空闲块已至大的分区无法被分配

对碎片进一步处理

I 压缩式碎片处理/compaction

重置程序已合并孔洞；要求程序是动态可执行的（何时重置？开销？）

II 交换式内存整理

若运行的程序需要更多的内存——>抢占等待的程序并且回收它们的内存（换哪个？开销？）