物理地址
- 又称实地址、绝对地址
- 内存所看到的地址
物理寻址
- CPU直接使用物理地址访问主存储器
虚拟地址（virtual address）
- 又称逻辑地址
- CPU所生成的地址
虚拟寻址（virtual addressing）
- CPU通过虚拟地址访问主存，虚拟地址经过地址翻译转换为物理地址
- 地址翻译由CPU里的内存管理单元(MMU)负责.
程序的装入
- 绝对装入
- 用户在程序设计时直接给出物理地址
- 或程序包含符号地址，编译/汇编时转换成物理地址
- 缺点：不能加载到内存任意位置；只适合单道程序
- 可重定位装入，静态重定位
- 编译器仅产生相对地址
- 加载器在加载时将相对地址转化为绝对地址
- 缺点：不允许在运行时改变在内存中的位置；
- 动态运行时装入，动态重定位
- 加载器在加载时仍使用相对地址
- CPU在运行时将相对地址转化为绝对地址
- 需要地址转换硬件（MMU，重定位寄存器）支持
程序的链接
链接器（linker）把一组目标模块作为输入，产生一���包含完整代码和数据的加载模块（load module），传递给加载器
- 静态链接（static linking）
缺点：常用的库不能共享，库函数若更新，需重新链接 - 动态链接（static linking）
加载时动态链接
基地址-界限
分配一块连续的内存
基地址+逻辑地址实现地址转换
界限地址实现地址保护
内存分配
- 单一连续分配
- 固定分区分配
- 动态分区分配
管理动态分区分配的数据结构，要能动态跟踪每个已占用和空闲的分区情况
可用：二维数组；链表；位图(bitmap)
动态分区分配算法
- First Fit算法
分配n个字节，使用第一个可用的空间比n大的空闲块。 - Next Fit算法
分配n个字节，从上一次找到的分区向下寻找，使用下一个可用的空间比n大的空闲块。 - Best Fit
分配n字节分区时， 查找并使用大于n的最小空闲分区 - Worst Fit
分配n字节，使用尺寸不小于n的最大空闲分区
基于索引搜索的分配算法
- 快速适应
根据空闲区的容量作分类，设立大、中、小等多个链表方便索引 - 伙伴系统
分配时可能多次分割，回收时可能多次合并
时间性能和利用率折中了快速适应与顺序搜索
可以兼顾大小进程的分区需求
没有外部碎片，但有内部碎片，每块最大为2i−12^i-12i−1
分页式存储管理
基于基地址-界限的存储管理方式简单有效，可以实现内存 分配、地址转换、地址保护，但始终解决不好碎片的问题 原因在于，内存总是只能寻找一段连续的空间才能分配
解决方案：分页（Paging）管理
核心思想：离散分配，将进程打散，分到不同的空间中去
页式地址变换
虚拟地址结构：页号(page number)+页偏移量(page offset)
物理地址：物理块(frame number)+页偏移量(page offset)
页框：以页框为单位为各个进程分配内存空间，最小的一块储存单元大小
将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。相应地，将内存空间分为若干个物理块或页框（frame），页和页框大小相同。
在页表中，每一行存储的是属于那个物理页面的信息，又称为“页表项(Page Table Entry) 按位数
没有外部碎片
- 因为块是物理内存分配的最小单位
- 空闲的物理块可以用位图（bitmap）或链表（freelist）管理
- 每一块都可以分配出去，不存在浪费；回收简单
很小的内部碎片
- 每个进程最多在最后一个页产生浪费
- 内碎片最大为：页面大小 – 1Byte
存取控制字段
页表是系统为每个进程建立的页面映射表
每个页表项的结构为：页号 + 物理块号
问题
- 访问页表时间
- 基地址-界限方式，直接通过MMU的寄存器转换地址
- 页表在内存里，每次寻址多了一次内存访问
- 页表占据空间
- 随着系统位数提升，页表会占有越来越多的空间
快表
通过缓存，加速页的访问
t: 访问一次内存的时间
λ：查找快表的时间
α：快表命中率
有效访问时间：α(λ+t)+(1−a)(λ+2t)+t=2t+λ−αt
多级页表
减少直接寻址存储器的大小空间
反向页表
让页表与物理地址空间的大小相对应
基于Hash映射值查找页表对应的帧号f 用链表处理hash冲突
减少直接寻址存储器的大小空间
段式存储管理
