内存管理
原因和需求
原因
- 软件对内存的需求很大,如果不加管理,会无限制使用内存
- 快速存储器成本太高,需要好好利用内存
需求
- 支持多程序和多用户
- 充分利用空间
- 给每一个程序足够大的逻辑运行空间
- 存储保护
存储管理的功能
- 存储的分配和回收:时存储管理的重点,重点时讨论算法和相应的数据结构.
- 存储的共享和保护:可以理解成对地址空间的权限(读,写,运行).
- 地址变换: 可执行文件生成时的链接计数,程序加载时的重定位技术,进程运行时硬件和软件的地址变换技术.
- 存储的容量扩充:不是增加内存条的容量扩充,而是当需要更多内存的时候,内存的覆盖,交换,虚拟内存.
概念解析:
- 地址空间:源程序经过编译之后得到的目标地址,存在于它所限定的地址范围类,这个范围称为地址空间.简言之,地址空间就是逻辑地址的集合.
- 存储空间:主存中一系列存储信息的物理单元的集合,这些单元的编号称为物理地址或绝对地址.简言之,存储空间就是物理地址的集合.
简言之,地址空间就是进程认为自己使用的空间,是一个抽象空降,存储空间就是实际操作访问的物理空间,这二者就是CO中提到的虚拟内存技术.
- 内碎片:如果一个分区没有被完全占用,则剩下的空间被称为内碎片.该碎片在操作系统眼里已经被占用,无法整理.
- 外碎片: 占用分区之间的空闲分区,这片分区如果小于载入程序则无法利用,被浪费.该碎片可以整理后清楚,是内存系统性能下降的主要原因.
单道程序的内存管理
整个系统中出了操作系统之外只剩这一个程序,所以整个内存可以供他使用,其地址也可以固定.就像整个地区如果只有一个部落,那部落肯定找一个最好的地方发展下去.如果有多个部落互相抢占资源,那肯定存在部落被顶替掉的情况.
条件
- 在单道程序环境下,整个内存里只有两个程序,一个是用户程序,一个是操作系统.
- 操作系统占据的空间是固定的.
- 因此可以将用户程序加载到同一个地址,即用户程序永远可以从同一个地方开始运行.
静态地址翻译
因为程序的地址固定,所以可以在程序运行之前就计算出所有的物理地址.使用此方法,用户无需知道关于内存的知道,操作系统直接访问地址即可,而且因为没有其他程序,那么整个程序在这个地址就是安全的.
优缺点
- 优点:运行简单,没有地址翻译,运行速度快
- 缺点:整个内存只给一个程序,造成资源浪费.而且如果程序必内存大无法加载,则无法运行.
多道程序的内存管理–分区
空间的分配
- 把内存分成一些大小相等或者不等的分区,每个应用程序占用一个或者多个分区,操作系统占用一个分区.
- 适用于多道程序系统和分时系统,支持并发,但难以进行内存分区的共享.(每个程序共享整个内存,难以对某一些地址空间进行权限控制)
固定式分区分配
方法
- 固定(静态)式分区分配:这个方法是程序适应分区,在系统初始化之后将内存划分成若干个任意大小的区域,然后将这些区域分配给进程.
- 相同大小的分区:适用性差,只适用于多个相同程序的并发执行
- 优点:算法实现简单,方案运行开销小
- 缺点:出现了内碎片,分区数目限制之后,最大载入程序数量也确定,限制了并发执行程序的数量.
分配方式
- 单一队列的分配方式:当加载程序是,选择一个闲置且足够大的分区加载.多个程序排在同一个队列.
- 多队列的分配方式:根据程序的大小分成不同队列,排在不同大小的分区后面.
可变式分区
方法
闲置空间的管理
位图表示法
给每个分区赋予一个滋味,用来记录该分配单元是否闲置.
链表表示法
将分配单元按照是否闲置链接起来.每一个结点分别记录该空间是否空闲,空间的起止地址以及指向下一个结点的指针.
两种方法分析
位图表示法
- 空间成本固定,不依赖于内存中程序数量
- 时间成本低,只需要修改位图即可,一次改1bit
- 没有容错能力,如果存储单元出错,无法分辨该位置的1是被占用还是出错.
链表表示法
每张表的表项都可称为存储控制块MCB(Memory Control Block),包括AMCB(Allocated MCB)和FMCB(Free MCB).
空闲分区控制块按某种次序构成FMCB链表接口,但分区被分配之后,其前后项指针无意义.
分区分配操作
分配内存
- 设size是最小分区大小,不能再分割
- 如果$请求分区大小 \gt 分区大小$检索下一个表项
- 如果$请求分区大小+size \lt 分区大小$则将分区中按照相应大小划分一块,剩下的部分留在空间分区表中.
- 如果$请求分区大小+size \ge 分区大小$则将整个分区都分给程序.
回收内存
- 回收分区邻接空闲分区则将空闲分区和回收分区合并
- 回收分区不邻接空闲分区则在空闲分区表中新建表项放置回收分区
搜索算法
基于顺序搜索的分配算法
算法介绍
- 首次适应算法:每个空白区按照地址顺序排成链表,从头找到尾,分配出第一个满足条件的分区
- 下次适应算法:把空白区构成一个循环链表,每一次查询从上一次的位置出发,分配出第一个满足条件的分区
- 最佳适应算法:遍历所有空白区,分配最佳的分区
- 最坏适应算法:遍历所有空白区,分配最大的空白区
算法特点
- 首次适应算法:低地址地址会被不断划分出去,之后的查找时间开销变大
- 下次适应算法:是空间使用更加均匀
- 最佳适应算法:分配出的空间是最佳的,但是会剩下很多特别小的碎片,而且时间开销大
- 最坏适应算法:剩下比较大的碎片,不能满足之后的大程序,而且时间开销大
总结
该类方法只适用于小系统,如果系统很大,则分区很多,每次的查找开销很大
基于索引搜索的分配算法
快速适应算法
快速适应算法:将空闲分区按照容量大小分类,并把常用大小的分区单独建立链表,并对多个链条设立管理索引链表.
- 优点:查找效率高,根据长度分类,保证了内存分配结果的最优,不产生碎片
- 缺点:算法复杂,开销大,分配空间的时候以进程为单位,存在一定的浪费.
伙伴系统
在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为 “伙伴”,对于不同大小分区建立链表.伙伴系统规定分区的大小一定是2的k次幂,$n \le k \le m$,其中$2^n$是最小分区大小,$2^m$是最大分区大小,通常为整个内存
在系统运行中可能因为不断划分形成若干个不连续的空闲分区
内存管理模块保持有多个空闲块链表,空闲块大小为2的整数次幂
内存分配
- 在程序启动的时候只有一个空闲块(整个内存)
- 当一个大小为n的进程申请内存的时候向上取2的整数次幂($2^n$)寻找空闲块,如果没有空闲块,则去$2^{n+1}$去寻找.
- 对于$2^{n+1}$大小的空闲分区,分出$2^n$用于分配,另一半加入管理$2^n$的链表中,这两个分区称为伙伴
- 如果$2^{n+1}$大小的空闲分区不存在则依次类推
内存释放
将被释放块与其伙伴合并成一个更大的空闲块,然后一直合并下去
多道程序的内存管理–分页
基本思想
分区的思路怎样都会导致碎片的出现,浪费空间,影响性能.如果把一个逻辑地址连续的程序分散存放到不连续的内存区域中,但保证正常运行,则级充分利用了空间,由可减少移动带来的开销.支持分页的硬件部件通常叫做MMU.
纯分页系统
- 如果不具备页面交换功能,那么每次作业的时候必须将所有页面一次性装入到主存,如果空间不够,则必须等待.
- 优点:没有外碎片,每个内碎片也不超过页的大小
- 缺点:程序全部装入内存,空间开销大.
基本概念
- 页: 在分页存储管理系统中把每个作业的地址空间分成一些大小相等的片,称之为页面或者页(
page),从0开始编号,其大小通常是2的幂次方,常用大小为4KB. - 存储块: 在分页存储管理系统中,把主存的存储空间也分成了和页相同大小的片,这些片成为存储块,或称为页框,从0开始编号.
- 页表: 装载进程空间中的页和内存空间中页框的映射的表,每一个进程都有一个.
多级页表
一级页表的问题
如果内存很大,那么页表也会很大,占用内存多,实现复杂.
因此解决思路如下: - 动态调入页表,只调入当前需用的部分页表项
- 多级页表
两级页表
将页表再进行分页,离散的将给个页表页面存放咋i不同物理块,然后再建立一张外部页表用来记录对应的物理块号,运行时调入一级页表,再动态调入页表,因为只调入所需页表,所以占用的空间少了.多级页表
多级页表同理,每一级页表只指向下一个页表项所在地址,最后的页表指向实际的内存地址.但是页表级数增加,访存次数增加,降低效率.快表TLB
因为无论如何,页表至少需要访问两次内存,所以需要使用Cache装入部分常用页表项,这部分Cache叫做快表(TLB)
快表和Cache类似,地址转换原理和页表一样,就不赘述了.反置页表
利用反置页表进行地址变换的步骤: - 用进程标志符和页号去搜索反置页表
- 如果没有找到说明没有调入内存,产生中断.
- 如果检索到对应表项,则表项的序号i就是物理地址.
反置页表之所以交反置页表,是因为普通页表是通过序号找内容,这是匹配内容找序号.
- 缺点: 因为反置页表通过物理地址排序,而虚拟地址不一定是连续,所以查询可能需要找遍整个页表,时间场
- 优点: 页表存储空间大大减少
哈希页表
对于超过32位地址空间的常用方法是使用哈希页表,使用虚拟页号作为哈希是,哈希页表的每一条目都包裹一个链表,链表的每个结点哈希相同.每个元素包含三个域:
- 虚拟页号,也就是hash 的key
- 映射的页框号
- 指向下一个元素的指针
因为可能存在hash冲突,所以要处理冲突.检索方法
- 计算虚拟页号和进程标志符对应的
hashcode - 域虚拟页号与链表中的每一个元素的第一个域比较
- 匹配则取出页框号
- 反之继续寻找
页的保护
页式存储管理系统提供了两种方式:
优点
- 不要求连续存储
- 解决外碎片
缺点
- 内碎片浪费
- 不适合大型应用
多道程序的内存管理–分段
方便编程:
- 通常一个作业是由多个程序段和数据段组成(
.data,.bss,.text),用户一般按照逻辑关系对作业分段,并能根据名字访问程序段和数据段
信息共享:
- 共享是以信息的逻辑单位为基础.页是存储信息的物理单位,段是信息的逻辑单位.
- 页式管理中地址空间是一维的,主程序,子程序都顺序排列,共享共用子程序比较困难,一个共享过程可能需要几十个页面.(一个共享程序被多个进程共享,每个进程都有一个页表)
信息保护
- 页式管理中,一个页面可能装有两个不同的子程序段的指令代码,不能通过页面共享实现共享一个逻辑上完整的子程序或者数据块
- 段式管理中,可以以信息的逻辑单位进行保护
动态增长
- 实际应用中,某些段(数据段)会不断增长,分页能以实现
动态链接
- 动态链接在程序运行时才把主程序和要用到的目标程序链接起来
地址结构
段表
- 段表记录段与内存位置的对应关系
- 段表保存在内存中
- 段表的基址及长度由段表寄存器给出
- $|段表基址|段表长度| \quad or \quad |STbase|STlen| $
- 访问一次物理内存需要方位两次内存(段表和内存)
- 逻辑地址由段和段内地址组成
信息共享
可重入代码
可重入代码称为纯代码,是允许多个进程访问的代码,该段代码只允许读,不允许写,以保证每个进程使用的代码完全相同.
段页式存储结构
逻辑地址包含段号,页号和页内地址,先访问段表得到页表始址,再访问页表获得块号,和页内地址和块号拼接得到物理地址.
虚拟存储
局部性原理
- 时间局部性: 即一条指令的一次执行和下次执行,一条数据的一次访问和下次访问都集中在一个较短的时期内
- 空间局部性: 即当前指令和邻近的几条指令,当前访问的数据和邻近的数据都集中在一个较小的区域内
根据上述局部性原理,我们就可以在装入程序的时候,不将全部读入到内存,只需要将当前需要执行的部分页或段读入到内存,就可开始执行.如果访问缺失再从外存调入.
虚拟存储技术的特征
- 多次性:作业分成多次调入内存,因此在逻辑上,内存扩大了.
- 对换性:允许在作业运行过程中进行换进换出,提高内存利用率(暂时用不到的数据换出内存,提高内存使用效率)
- 离散型:物理内存分配的不连续,虚拟地址空间使用的不连续
- 虚拟性:通过物理内存和快速外存相结合提供大范围的虚拟地址空间
优缺点
优点:
- 可在较小的内存中执行较大的程序
- 可在内存中容纳更多程序并发执行
- 不必影响编程时的程序结构
- 提供给用户的可用虚拟内存空间大于物理内存
缺点:
- 虚拟内存实际上是外存的一部分,所以牺牲了CPU的速度
- 虚拟内存也不能无限制加大,32位的机器一次性能访问的地址最大也就4GB
总结
虚拟存储技术就是将部分外存当作内存的中转站,将部分不常用的数据放进去,需要的时候直接拿出来,逻辑上内存就扩大了.使用覆盖的方法,将一个程序化为一个个相对独立的程序单位,再使用交换技术,保证常用的部分在内存中,不常用的覆盖就交换到外存里面.
请求分页(段)系统
在分页(段)技术的基础上,增加了请求调页(段)功能,页面(段)置换功能所形成的页(段)式虚拟存储器系统.
它允许只装入若干页(段)就可运行程序,以后在硬件的支持下通过请求调页(段)功能和置换页(段)功能,陆续将要运行的页面(段)调入内存,同时把暂不运行的页面(段)交换到外存上,置换时以页(段)为单位.
请求式分页系统
在运行作业之前,只需将当前需要的一部分页面装入内存,在需要其他页的时候,自动选择一些页交换到辅存去,再调入需要的页.
页表项结构
状态位
用于指示该页是否已经进入内存,一般由操作系统来管理.如果对页表查询时,发现状态位为0,则发生缺页中断.
修改位
用于只是该页调入内存后是否被修改过,如果已经修改过,那么重新分配页框(物理内存)的时候,就必须将其写回辅存,如果没有修改过,丢弃即可.
页框号
指出该页对应的物理页框号
访问字段
当页面被访问过则置1,供后续页面置换算法再选择时作参考
禁用高速缓存
适用于内存映射I/O,如果禁用,则表示该地址对应I/O设备,CPU访问时循环等待外设的相应,而不是访问高速缓存.
保护位
指定所运行的访问,读,写,执行等,具体由设备自己决定.
页面调入策略
- 请求调页:只调入发生缺页异常时候的页面,实现简单,但不适合在初始化的时候使用,会发生多次异常,导致程序效率低下
- 预调页:在发生缺页的时候,一次性调入该页和邻近的几个页,常在程序装入的时候使用
页面置换算法
最佳算法 (OPT optimal)
选择”未来不再使用”或者”在离当前最远位置上出现的”页面置换.
这只是一个理想情况,实际很难实现,但可以作业思想知道和评估依据.
NRU 最近未使用页面置换算法
在最近的一个时钟周期内,淘汰最近没有被访问的页面.
根据修改位和访问字段来选择.
FIFO 先进先出算法
总是选择最先装入内存的一页调出.
该算法通过链表实现,链表指针指向第一个进入的页.
该方法存在将常使用的页面丢掉的情况,产生Bleady现象
二次机会页面置换算法
对FIFO算法的改进,检查最老页面的R位,如果R为0则淘汰,反之则R复位,然后将这个页面放到链表的最后(相当于修改了FIFO中页的装入时间)
时钟算法 CLOCK
该算法使用环形队列,就不需要将页放到链表末尾,直接指针向下走一位就行.
页面缓冲算法 page buffering
对FIFO算法的发展,创立缓冲区缓冲被置换页面,有机会找回刚被置换的页面.
- 对于被置换页表,根据其是否被修改,放入缓冲区中两个不同链表–空闲链表和已修改页面链表,如果被再次访问则放回内存.
- 当需要读入新的物理页面时,将新页面内容读入到空闲页面链表的第一项所指页面,然后将第一项删除
- 当已修改页面达到一定数目之后再将他们一起调入外存,,然后将他们归入空闲页面链表,减少I/O次数
相当于空闲页链表就是缓冲区,记录最近的页面交换历史,当需要访问时先去缓冲区访问.
最近最少使用算法 LRU
当需要置换一页面时，选择在最近一段时间内最久不用的页面予以淘汰.
该算法思路最接近最佳算法,但实现困难.
实现如下:
- 使用栈来维护信息,栈底是最久未使用的页面,如果页面使用则将其放置于栈顶.
- 全局保存一个自增计数器用来记录进程时间,每个页面配备一个计数器,当页面被访问,该页面的计数器被赋值成全局计数器的值,当淘汰页面的时候,淘汰最小的那个页面.
最不常用算法 NFU
与LRU类似,页面记录自己被访问次数,淘汰次数最少的页面
Aging算法
与NFU类似,但是计数器每个周期右移一位,最高位填入R位,使得最近的访问权重最大
缺页异常处理
如果在访问页表的时候,该页没有装入内存,则抛出缺页异常,异常处理如下:
- 和正常的异常处理一样,先保护重要信息于栈中,进入异常处理入口
- 找出虚拟地址对应的页地址
- 查找是否有空页框,如果有,则直接调入其中并更新页表.
- 如果没有,则使用相应算法置换出一个页框
- 恢复现场,线程重新执行
工作集与驻留集
概念
根据时间局部性原理,如果能预测未来某段时间将要访问的也米娜,并提前调入内u了,那么就能提高效率.工作集就是依据进程过去一段时间内访问的页面调整常驻集大小.
根据局部性原理,我们知道,随着访问次数的增减,内存访问的局部性区域趋向稳定,如果局部性区域改变,工作集也能逐渐过渡到下一个稳定值.
该集合的建立可以建立一个二元函数$W(\Delta,t)$其中$\Delta$为时间窗口大小,函数值表示再时间$[t-\Delta,t]$内访问的页面集合,函数$W$关于$\Delta$只增不减,$|W(\Delta,t)|$指工作集大小即页面数目.
- 监视每个进程的工作集
- 周期性地从一个进程的驻留集中移去那些不在它的工作集中的页
- 只有当一个进程的工作集在内存中时，才可以执行
算法
碰到缺页异常的时候,遍历整个页表,如果页表最近没有用过,则判断其是否在工作集内,如果在则去找下一个页面,不然就替换调.WSClock算法
Clock算法加上工作集算法,使用循环链表,就不需要遍历整个页表了.
工作流程: - 发生缺页异常,检查当前指针指向的页面
- 如果最近使用过,则不淘汰,指针向下走
- 如果没有使用过,判断其是否在工作集,不在工作集,判断是否被修改过,没有修改过则直接替换,修改过则异步写入磁盘,然后寻找下一个没有改过的老页面.
- 如果一直没有找到老的干净页面,则说明都在工作集(有不在的话,因为异步写入,则其变成干净的老页面了),则随机替换一个.
页面置换策略
全局置换
出些缺页异常且进程空闲物理块用完,测从内存中选择一块调出,该块可能属于其他进程
局部置换
出些缺页异常且进程空闲物理块用完,则从进程的物理块中选一块替换
抖动
随着进程的并发数增加,处理器的利用率先上升后下降,这种现象称为抖动.因为并发数太多,每一个进程的驻留集太小,缺页率太高,频繁抛出缺页异常,导致整个线程陷入了I/O,cpu工作占用很低.
抖动的预防和消除
- 局部置换策略 (局部置换策略不会占用其他线程的空间)
- 引入工作集算法
- 预留部分页面
- 挂起若干线程
