计算机体系结构
计算机体系结构 由 CPU 内存 I/O设备 组成
CPU 组成结构
- 寄存器 容量小
- ALU 控制逻辑
- 高速缓存 L1 L2
- MMU 内存管理单元
内存层次
- CPU
- L1缓存
- L2缓存 (以上由 MMU 内存管理单元完成)
- 高速缓存不命中 (以下由操作系统控制)
- 内存 (内存中若找不到 有可能是缺页 存到外存里了 要将它从外存中换上内存)
内存特点
内存 最小访问单位 字节 是 8 bit
32位总线 一次读写 4字节 有地址对齐的问题
操作系统内存管理
操作系统希望 各个进程有各自的内存空间 同时 它们地址应该是可以重叠的
因此有了操作系统内存管理的目标
- 抽象: 逻辑地址空间
- 保护: 独立地址空间
- 共享: 共享地址空间 (内核内存地址)
- 虚拟化: 更大的地址空间
操作系统中采用的内存管理方式
- 重定位(relocation) 修改段寄存器地址
- 分段(segmentation) 希望内存不连续 程序逻辑结构不需要连成一片 分为堆栈 代码段 数据段 三段 但是 一段里的内存还是要连续的 所以有了 下面的分页
- 分页(paging) 最小的单位 一页 4Kb 如果用一个字节的话 开销粒度太细 管理难度高
- 虚拟存储 (virtual memory) 大多数 系统 如 Linux 采用按需页式虚拟存储
内存管理实现上高度依赖硬件
- 与计算机存储架构紧耦合
- MMU 内存管理单元 处理 CPU 存储访问的硬件
地址空间和地址生成
- 物理地址空间 硬件支持的地址空间 地址唯一
- 线性地址空间 CPU看到的地址
- 逻辑地址空间 CPU运行的进程看到的地址
地址生成过程
CPU层次中所做:
- ALU: 需要逻辑地址的内存内容
- MMU 进行逻辑地址和物理地址的转换
- CPU 控制逻辑 给总线发送物理地址请求
- 内存 发送物理地址的内容给CPU 或者 接受CPU数据到物理地址
操作系统层次中所做:
- 建立逻辑地址 LA 和 物理地址PA 的映射 这是页表所做的
- 地址检查
每次访问 会检查 段偏移寄存器和段基址寄存器 它们的界限为操作系统设置的初始 base 和 最大 limit 的逻辑地址空间
从程序编写层次:
- 高级语言程序 写出函数
- 编译生成汇编源代码 此时仍然是符号来指代函数
- 汇编成二进制代码 用具体地址来代替符号
- 链接 加入函数库
- 重定位 加载程序时 视程序实际位置改变符号地址
连续内存分配
给进程分配一块不小于指定大小的连续内存空间
内存碎片
空闲内存 不能被利用
- 外部碎片
分配单元之间未被使用内存 - 内部碎片
分配单元内部未被使用的内存 由于取整导致
动态分区分配
当程序被加载完毕时 分配一个进程指定大小可变的分区(块 内存块)
分区的地址是连续的
动态分区分配策略
最先匹配(First Fit Allocation) 找第一个可用空间比 n 大的空闲块
- 空闲分区列表按地址顺序排序
- 分配过程中 搜索第一个合适的分区
- 释放分区时 检查是否可与临近空闲分区合并
最先匹配优缺点
- 优点: 简单 在高地址空间有大块的空闲分区
- 缺点: 产生外部碎片 分配大块分区 会比较慢
最佳匹配(Best Fit allocation) 所有都找一遍 找不小于需要的内存的最小空闲分区
- 空闲分区按照大小排序
- 分配时 查找一个最合适的分区
- 释放时 查找并且合并临近的空闲分区 因为是空闲分区列表按照大小排序 因此 合并的时候 先要查找 才能进行合并 花的时间会较多
最佳匹配优缺点
- 优点: 大部分分配的尺寸较小时 效果好 可避免大的空闲分区被拆分 可减少外部碎片的大小
- 缺点: 外部碎片 释放分区较慢 容易产生很多无用小碎片
最差匹配(Worst Fit Allocation)
- 使用尺寸不小于所需内存的最大空闲分区
- 空闲分区列表由大到小排序
- 分配时 选最大的分区
- 释放时 检查临近的空闲分区合并 和 最佳匹配相同 因为是按大小排序的 需要查找一遍 按照地址合并 花的时间较多
最差匹配优缺点
- 优点: 中等大小的分配较多时 效果最好 避免出现太多小碎片
- 缺点: 释放分区较慢 外部碎片 容易破坏大的空闲分区 后续难以分配大的分区
以上三种分配策略 总结
都会产生外部碎片 都不产生 内部碎片
碎片整理
通过调整进程占用的分区位置 来减少或避免分区碎片
为什么需要碎片整理?
可用内存空间已经被分配完了 只剩下一些内存碎片 此时又需要分配内存空间 就需要进行碎片整理 来获取更大的可用内存空间
碎片整理方法
- 碎片紧凑 (compaction)
通过移动分配给进程的内存分区 以合并外部碎片 - 分区对换 (Swapping in/out)
通过抢占并回收处于等待状态进程的分区 存到外存里去 以增大可用内存空间
它们都只产生内部碎片 不产生外部碎片
碎片紧凑条件
所有的应用程序可动态重定位
碎片紧凑需要解决的问题
- 什么时候移动? 当然是进程处等待状态下
- 开销
分区对换
在 Linux 或者 Unix 有个分区 叫对换区 是充分利用内存的做法
当只有一个进程能运行的时候
当前进程主动让出处理机使用权限
把它对换的外存当中 再把 外存搬回去
在早期内存很紧张的情况下 Unix 使用这种方式 实现进程的交替进行 开销超大 因为 内存和外存的速度差的很远
伙伴系统 (Buddy System)
是连续内存分配的实例
约定整个可分配的分区大小为 2 的 n 次方
伙伴系统实现
空闲块按大小和起始地址组织成二维数组
初始状态 只有 一个 2 的 n 次方的空闲块
伙伴系统分配过程
从小到大在空闲块数组中找最小的可用空闲块
如果空闲块过大 就 二等分 直到得到合适的可用空闲块
伙伴系统释放过程
把释放的块放入空闲块数组
合并满足合并条件的空闲块
伙伴系统合并条件 2 的 n 次方
大小相同 地址相邻
起始地址较低的块的起始地址必须是 2 的 i + 1 的倍数