内存管理
为什么要进行内存管理?
对单道系统来说,内存分配较简单。
对多道系统,如果不进行管理,容易导致数据混乱。
- 内存两部分
- 用于驻留OS:低地址内存空间
- 用于用户进程:高地址
OS对内存的划分和动态分配。因为不可能把所有用户进程和系统所需的资源、数据放入内存,需要对内存空间进行合理划分和动态管理。
- 内存管理主要功能:
- 内存空间分配、回收
- 地址转换,LA-->PA,虚拟地址-->物理地址
- 内存空间扩充。在逻辑上
- 内存共享
- 存储保护。
背景知识
逻辑地址空间、物理地址空间
ps.逻辑地址、虚拟地址不区别。
32位系统,虚拟地址范围 0到232-1
CPU生成地址:逻辑地址LA,内存单元看到的是物理地址PA(加载到内存地址寄存器的地址),用户程序看不到真实的PA,只是处理LA。
不同的进程可以有相同的LA,因为映射到不同的PA上,不冲突。
- LA-->PA映射:由内存管理单元 MMU Memory-Management Unit进行地址重定位
- 基地址寄存器:重定位寄存器,交给内存的地址=用户进程生成的地址+基地址寄存器的值(重定位寄存器的值)
动态加载
获得更好的内存空间利用率,程序A只有调用时才加载到内存中,所有程序都以可重定位加载格式保存在磁盘中。
- 调用一个程序过程:
- 判断程序是否已加载到内存
- 在内存中,执行
- 不在,利用可重定位链接程序加载到内存,更新程序地址表。
- 判断程序是否已加载到内存
动态链接、共享库
程序的链接、装入
- 编译:编译完成后,所有目标模块地址都是从0开始的相对地址,链接时对其进行修改。
- 链接:把一组目标模块and其库函数链接在一起-->完整的装入模块。有3种方式。
- 静态链接:程序运行前,把各个目标模块和其库函数链接成一个完整的装配模块(①修改相对地址、②变换外部调用符号:模块里用的外部符号改成相对地址),之后不再拆开。
- 装入时动态链接:边装入内存边链接,便于修改更新and实现对目标模块的共享。
- 运行时动态链接:程序执行过程中进行。
- 装入内存:3种方式
- 绝对装入:只适用于单道程序环境。使用绝对地址。
- 可重定位装入静态重定位:装入时一次完成地址的重定位。ps多道程序条件下,多目标模块都是用相对地址(各自从0开始)。
- 动态运行时装入动态重定位:程序在内存中发生移动需要采用这个做法。装入时都还是相对地址。到真正运行时才转换。
- 可以把程序分配到不连续的存储区。
内存保护
每个用户进程都有自己的单独的内存空间,所以要保护OS不受用户进程的影响,保护用户进程之间不相互影响。
- 两种措施:
- 在CPU中设置一对(上限寄存器,下限寄存器),每次访问一个地址时,利用这对寄存器判断地址是否合法。
- 采用重定位寄存器(基地址寄存器)Base最小PA-plus 和 界限寄存器 最大LA-compare。
- 判断CPU存的LA<界限寄存器值。若否则错误;
- 小于则加 CPU寄存器地址+重定位Base = PA
- 根据这个PA访问对应的内存单元。
覆盖与交换
主要针对同一进程,同一程序。
早期计算机系统的内存很小,把用户空间分成1固定区(常活跃),多个覆盖区(可覆盖)。
交换
对不同进程、不同程序之间的操作。增加多道程序程度。现代OS已不适用,使用其变种。
- 换出:处于等待的程序(等待I/O的不可)从内存移入备份存储(辅存),腾出内存空间。
- 换入:准备好竞争CPU的程序从备份存储移入内存中。
- 备份存储:通常是快速磁盘,要足够大,独立于文件系统。且提供对这写内存映像的直接访问。
变种:正常情况禁止交换。①内存空闲过低时启用交换/②交换进程的一部分,降低交换时间。
- 移动设备通常不支持交换。使用闪存。
1. 连续内存分配
早期方法。一个进程的空间是连续的。
- 单一连续分配:内存(系统区 低地址/用户区 高地址),用户区只有一个用户程序独占。
无外部碎片,有内部碎片,不需要内存保护,利用率低。 - 固定分区分配:用户内存空间划分成固定大小的区域,每个分区装一道作业。有空闲区域时装入新作业。有内碎片,无外碎片。
- 分区大小相等:缺乏灵活性
- 分区大小不等
- 动态分区分配:分区大小正好适合进程需要,动态分配。有外碎片,无内碎片。可以用紧凑技术减少外部碎片。
碎片
- 内部碎片:分配给进程的这个块的大小-进程自身大小。分区内部多余部分。
- 外部碎片:多个进程之间的空隙大小,因为不连续。用紧缩技术解决。
动态分区分配算法
性能:首次≈最优适应>最差适应。
- 首次适应法:空闲的孔中,第一个满足的。较快
- 最优适应法:刚好装入。
- 最差适应:分配最大的孔。-->产生最大剩余孔。
2. 分段 segment
产生外碎片、无内碎片。段内连续,段间不必连续。段的长度由实际需求决定,不固定。
- CPU存的地址格式:段的LA表示:<段号,偏移>
- 一个C语言程序的段
- 代码段
- 全局变量段
- 堆
- 每个线程使用的栈
- 标准C语言库
地址映射
- 通过段表实现:利用段号索引(CPU的LA=<段号s,段偏移d>)
- 段基地址:这个段的其实地址
- 段界限:这个段的大小or长度,
要判断段偏移d是否<段界限,超出了就是非法。
段号 | 段界限 | 段基地址 |
---|---|---|
0 | 1000 | 1400 |
1 | 400 | 6300 |
2 | 400 | 4300 |
3 | 1100 | 3200 |
4 | 1000 | 4700 |
- 例CPU<3,852>:合法,PA=3200+852=4052
- 计算各个段的PA:
- 段0:1400-2400
- 段1:6300-6700
- 段2:4300-4700
- 段3:3200-4300
- 段4:4700-5700
3. 分页 page
无外碎片、有内碎片。
- 帧/页帧 frame:将物理内存分成固定大小的块
- 页/页面 page:将逻辑内存分成同样大小的块。
一级分页
- 一般每页大小为4KB=212,需要20位做页偏移n。32位机器上,页号有32-12=20位。
(m-n)位页号,说明在系统中,一个进程最多允许有2m-n个页面,总物理内存可以更大。 - 在m=32位机器上,CPU存储的LA格式:
31 12|11 0|
页号 | 页偏移量 |
- LA映射到PA:PA=
页号*页大小+页偏移
- 一个页表:页表项:(页号)<帧号>。举例(LA 4位=2+2)
页号隐藏!!!!
页号 | 页基地址 |
---|---|
0 | 5 |
1 | 6 |
2 | 1 |
3 | 2 |
- LA=0 PA=?
- 方法1:5D 00B= 20D
- 方法2:(5X4)+0=20
- LA=3 PA=?
LA=0011,PA=(5X4)+3=23
页表项下限定几B?
(页号)<帧号> //页号不用存
e.g.32位逻辑地址空间 => 232B,一页4KB
地址空间有 232B/4KB=1M页=220页,需要20位表示全范围。
同时是字节作编址单位:页表项>=ceil(20/8)=3B
TLB 快表
因为页表一般都比较大,放在物理内存中。这样在访问字节时,要访问两次物理内存(①物理内存中找到页表,访问页表条目得知物理帧号 ②计算完之后访问具体位置取出数据)
so slow,于是在MMU中存一块页表缓存,TLB存储一些页表项,LA-->PA过程先利用TLB查找↓
- 利用TLB-->1次TLB+(1次内存)+1次物理地址访问=1or2次物理内存访问
- TLB命中。帧号可用,计算完访问物理内存。
- TLB不命中。访问页表,按照特定算法淘汰一个旧页表项。
访问TLB比内存里的页表项更快了。
分层分页页表
二级页表
顶级页表只能有1面
- 假设32位机器页面4KB=212,每项32b=4B
顶级页表最多存储(4KB/4B)=1K=210条,要用到10位地址。 - 32(总)-12(页偏移)-10(顶级页表占用) = 10b分给二级页号
两层。。三层
目录-->目录2-->目录...-->帧号
哈希页表
处理大于32位地址空间的常用方法。
- 哈希值:页码(虚拟页码)
- 哈希表:哈希表项都包含一个链表
- 链表中每个元素包含:虚拟页码,映射的帧码,
*ptr->next
- 链表中每个元素包含:虚拟页码,映射的帧码,
- 机制:LA的虚拟页码指向哈希表。在对应链表中寻找自己的node结点,用帧码得到PA。
倒置页表
整个系统只有一个页表,减少了存储页表所需的内存空间,但是增加查找时间。
- 通常情况:每个进程都有一个页表,每个虚拟页都有自己的页表项。
缺点:但这样页表很大,耗费很多物理内存。 - 倒置页表:每个条目对应真正内存位置上的页的LA,一个物理页只有一个条目。
- LA=<进程id,页码,偏移>
倒置页表HASH=<进程id,页码>
有效内存访问时间
100ns访问内存,利用TLB,命中率80%
- 命中:访问内存时间 = 100ns
- 不命中:访问内存时间=200ns
- 有效内存访问时间 =
100*0.8 + 200*0.2 = 120ns
分页机制下内存保护
保护位
通过与每个帧关联的保护位实现,通常保存在页表中。
一个位定义页的可读/可写,计算物理地址时通过保护位检查有没有越权操作。
有效位
捕捉非法地址,
- 有效:这一页在进程的逻辑地址空间中,有效页
- 无效:不在进程的逻辑地址空间内。
例进程对应着0-5页,现试图访问第6页,(有效位)=无效,OS报错:非法访问。
4. 段页式管理
一个段表--多个页表。
- 作业地址空间分成若干逻辑段,有自己的段号
- 每段再分成若干页
- 每个进程一张段表,段表项<段号,页表长度,页表初始地址>
- 每个分段一张页表,页表项<页号,帧号>
- LA结构:<段号s,页号p,页内偏移量>
- 页内偏移量由页面大小决定