存储器管理
2021-05-07 07:13:55 11 举报AI智能生成
操作系统 存储器管理脑图
作者其他创作
大纲/内容
存储器的层次结构（三级六层）
多层结构
CPU寄存器
寄存器
主存储器访问速度远低于CPU执行指令的速度，为缓和这一矛盾，引入了寄存器和高速缓存。
主存
高速缓存
主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数
实际存在的存储器
主存储器（内存)
用于保存进程运行时的程序和数据。
磁盘缓存
磁盘的I/O速度远低于对主存的访问速度的矛盾
主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少磁盘的次数
并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出（或读入）的信息。主存可以看作是辅存的告诉缓存。
辅存
固定磁盘
可移动存储介质
可执行存储器
寄存器和主存储器又被称为可执行存储器
访问机制
可执行存储器：进程可以在很少的时钟周期内使用一条load和store指令对其进行访问。
辅存：通过I/O设备实现
操作系统的存储管理负责对可执行存储器的分配、回收以及提供 在存储层次间数据移动的管理机制
设备和文件管理则根据用户的需求，提供对辅存的管理机制
内存的基础知识
什么是内存？有何作用
存储单元、内存地址的概念和联系
按字节编址VS按字编址
进程运行的基本原理
指令的工作原理
操作码+若干参数（可能包括地址参数）
逻辑地址（相对地址）VS 物理地址（绝对地址）
从写程序到程序执行
编辑源代码文件
编译
由源代码文件生成目标模块（高级语言“翻译”为机器语言
链接
由目标模块生成装入模块，链接后形成完整的逻辑地址
装入
将装入模块装入内存，装入后形成物理地址
三种链接方式
静态链接
装入前链接成一个完整的装入模块
修改
1、对相对地址进行修改
2、变换外部调用符号
装入时动态链接
运行前边装入边链接
优点
1）便于修改和更新
2）便于实现对目标模块的共享
修改
1）对相对地址进行修改
2）变换外部调用符号
运行时动态链接
运行时需要目标模块才装入并链接
三种装入方式
绝对装入
编译时产生绝对地址
只适用于单道程序环境
可重定位装入
装入时将逻辑地址转换为物理地址
特点：一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。此外，作业一旦进入内存，整个运行期间就不能再内存中移动，也不能在申请内存空间
动态运行时装入
运行时将逻辑地址转换为物理地址，需设置重定位寄存器
特点：可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段共享，可以向用户提供一个比存储空间大得多的地址空间
内存管理的概念
内存空间的分配与回收
连续分配管理方式
单一连续分配
只支持单道程序，内存分为系统去和用户区，用户程序放在用户区
无外部碎片，有内部碎片
内部碎片：分配给某进程的内存区域中，如果有些部分没有用上
外部碎片：是指内存中的某些空闲分区由于太小而难以利用
缺点：只能用于单用户、任务的操作系统中，有内部碎片，存储器的利用率极低
硬件支持
界地址寄存器、越界检查机构
固定分区分配
支持多道程序，内存用户空间分为若干个固定大小的的分区，每个分区只能装一道 作业
无外部碎片，有内部碎片
两种分区方式
分区大小相等
适合用于一台计算机控制多个相同对象的场合
分区大小不等
分区说明表（分区的始址，大小以及状态（是否已分配））
问题
1、程序可能太大而放不进任何一个分区中，不得不使用覆盖技术
2、主存利用率低，有内部碎片
硬件支持
1、上、下限寄存器、越界检查机构
2、基地址寄存器、限长寄存器、动态地址转换机构
动态分区分配
支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区
实现
记录内存使用情况
空闲分区表
分区号、分区大小、分区起始地址..
空闲分区链
前向指针、后向指针..
多个分区可分配时，选择哪个分区进行分配
动态分区分配算法
如何进行回收
回收内存分区时，可能遇到四种情况
回收区之后有相邻的空闲分区
回收区之前有相邻的空闲分区
回收区前、后都有相邻的空闲分区
回收区前、后都没有相邻的空闲分区
无内部碎片，有外部碎片
外部碎片可用“紧凑”技术来解决
硬件支持
1、上、下限寄存器、越界检查机构
2、基地址寄存器、限长寄存器、动态地址转换机构
动态分区分配算法
基于顺序搜索（小型系统）
首次适应算法（FF）
以地址递增次序排序
只需要简单查找，无需进行对可用块排序
算法开销小
倾向于优先使用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区
缺点：1、低址部分留下很多外部碎片；2、每次查找都从低址部分开始，增加了查找开销
循环首次适应算法（NF）
邻近适应算法
只需要简单查找，无需进行对可用块排序
算法开销小
每次分配内存时从上次找到的空闲分区的下一个空闲分区进行查找
缺点：缺乏大的空闲分区
最佳适应算法（BF）
按照容量从小到大链接
需要对可用块进行排序
算法开销大
缺点：留下很多难以利用的外部碎片
最坏适应算法（WF）
按照容量从大到小链接
需要对可用块进行排序
算法开销大
产生碎片的可能性最小，对中小作业有利
缺点：缺乏大的空闲分区
基于索引搜索（大、中型系统）
快速适应算法（分类搜索法）
将空闲分区根据分区大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区链表，并设立一张管理索引表
搜索可分配的空闲分区
1、根据进程长度，从索引表中去寻找能容纳它的最小空闲分区链表
2、从链表中取下第一块进行分配
特点
1、不会对任何分区产生分割
2、不会产生内部碎片
3、查找效率高
4、为了有效合并分区，分区归还主存时算法复杂，系统开销大
伙伴系统
算法规定，无论已分配分区还是空闲分区，大小均为2的k次幂
将空闲分区根据分区大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区链表，并设立一张管理索引表
分配存储空间时
长度为n 计算一个i值， 使 2^（i-1) < n <= 2^i
在空闲分区大小为2^i 空闲分区链表中查找。
找到则分配
找不到则到空闲分区大小为2^（i+1)查找
将其分为两个2^i空闲分区
一个用于分配，一个加入到分区大小为2^i的链表
对于一个大小为2^k,地址为x的内存块，其伙伴块的地址则用buddyk（x）表示
通式buddyk（x）
x+2^k （若x MOD 2^(k+1) =0)
x-2^k（若x MOD 2^(k+1) =2^k)
哈希算法
利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张一空闲分区大小为关键字的哈希表
非连续分配管理方式
基本分页存储管理
基本概念
基本分页存储管理的思想：把进程分页，各个页面可离散地放到各个内存块中
易混概念
“页框、页帧、内存块、物理块、物理页” VS “页、页面”
“页框号、页帧号、内存块号、物理块号、物理页号” VS “页号、页面号”
页表
页表记录了页面和实际存放的内存块之间的映射关系
一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由“页号”和“块号”组成
每个页表项的大小是相同的，页号是“隐含”的
i号页表项存放地址 = 页表始址 + i * 页表项大小
逻辑地址结构---可拆分为
【页号P， 页内偏移量W】
页号 = 逻辑地址 / 页面大小； 页内偏移量 = 逻辑地址 % 页面大小
如果页面大小刚好是2的整数次幂呢？
利于逻辑地址的拆分
物理地址计算更快
如何实现地址转换
1、计算除逻辑地址对应的【页号， 页内偏移量】
2、找到对应页面在内存中的 存放位置【查页表】
3、物理地址 = 页面始址 + 页内偏移量
基本地址变换机构
页表寄存器的作用
存放页表起始地址
存放页表长度
地址变换过程
1、根据逻辑地址算出页号、页内偏移量
2、页号的合法性检查（与页表长度对比）
3、若页号合法，再根据页表起始地址、页号找到对应页表项
第一次访问内存：查页表
4、根据页表项中记录的内存块号、页内偏移量得到最终的物理地址
5、访问物理内存对应的内存单元
第二次访问内存：访问目标内存单元
其他小细节
页内偏移量位数与页面大小之间的关系（要能用其中一个条件推出另一个条件）
页式管理中地址是一维的
实际应用中，通常使一个页框恰好能放入整数个页表项
为了方便找到页表项，页表一般是放在连续的内存块中的
具有快表的地址变换机构
是基本地址变换机构的改进版本
什么是快表？（TLB）
引入快表后，地址的变化过程
局部性原理
两级页表
单级页表存在的问题
所有页表项必须连续存放，页表过大时需要很大的连续空间
在一段时间内并非所有的页面都用得到，因此没必要让整个页表常驻内存
两级页表
将长长的页表再分页
逻辑地址结构：（一级页号，二级页号，页内偏移量）
注意几个术语：页目录表、外层页表、顶级页表
如何实现地址转换
1、按照地址结构将逻辑地址拆分成三部分
2、从PCB中读出页目录表始址，根据一级页号查找目录表，找到下一级页表在内存中的存放位置
3、根据二级页号查表，找到最终想要访问的内存块号
4、结合页内偏移量得到物理地址
几个细节
多级页表中，各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级
多级页表的访存次数（假设没有快表结构） --- N级页表访问一个逻辑地址需要 N+1次访存
基本分段存储管理
分段
将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址
每个段在内存中占据连续空间，但各段之间可以不 相邻
逻辑地址结构：（段号，段内地址）
段表
记录逻辑段到实际存储地址的映射关系
每个段对应一个段表项，各段段表项长度相同，由段号（隐含）、段长、基址组成
地址变换
1、由逻辑地址得到段号、段内地址
2、段号与段表寄存器中的段长度比较，检查是否越界
3、由段表始址、段号找到对应段表项
4、根据段表中记录的段长，检查段内地址是否越界
5、由段表中的“基址+段内地址”得到最终的物理地址
6、访问目标单元
分段 VS分页
分页对用户不可见，分段对用户可见
分页的地址空间是一维的，分段的地址空间是二维的
分段更容易实现信息的共享和保护（纯代码/可重入代码可以共享）
分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中可以引入快表结构
段页式存储管理
分段+分页
将地址空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面
将内存空间分为与页面大学相等的一个个内存块，系统以块为单位为进行分配内存
逻辑地址结构：(段号、页号、页内偏移量）
优点：
分页管理
空间利用率高，不会产生外部碎片，只会有少量页内碎片
分段管理
很方便实现逻辑模块实现信息的共享和保护
缺点
分页管理
不方便实现逻辑模块实现信息的共享和保护
分段管理
如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片
段表、页表
每个段对应一个段表项。各段表项长度相等，由段号（隐含）、页表长度、页表存放地址组成
每个页对应一个页表项。各页表项长度相等，由页号（隐含）、页面存放的内存块号 组成
地址变换
1、由逻辑地址得到段号、页号、页内偏移量
2、段号与段表寄存器中的段长度比较，检查是否越界
3、由段表始址、段号找到对应段表项
4、根据段表中记录的页表长度，检查页号是否越界
5、由段表中的页表地址、页号得到查询页表，找到相应页表项
6、由页面存放的内存块号、页内偏移量得到最终的物理地址
7、访问目标单元
访问一个逻辑地址所需访存次数
第一次 -- 查段表 、第二次 -- 查页表、 第三次 -- 访问目标单元
可引入快表结构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
内存空间的扩充（实现虚拟性）
覆盖技术
一个固定区
存放最活跃的程序段
固定区中的程序段在运行过程中不会调入调出
若干覆盖区
不可能同时被访问程序段可共享一个覆盖区
覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，操作系统完成自动覆盖
缺点：对用户不透明，增加了用户编程的负担
交换技术
内存紧张时，换出某些进程以腾出内存空间，再换入某些进程（进程在内存和磁盘间动态调度）
磁盘分为文件区和对换区，换出的进程放在对换区
虚拟存储技术
传统存储管理方式的特征、缺点
一次性：作业数据必须一次全部调入内存
驻留性：作业数据在整个运行期间都回常驻内存
局部性原理
时间局部性：现在访问的指令、数据在不久后很可能会被再次访问
空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后被访问
高速缓存技术：使用频繁的数据放到更高速的存储器中
虚拟内存的定义和特征
程序不需要全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需要换出一些数据
特征
多次性：无需作业运行时一次性全部装入内存，而是允许被分成多次调入内存
最重要的特征
对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量
表现出来的最重要的特征
如何实现虚拟内存技术
访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
内存不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）
虚拟内存的实现
请求分页存储管理
分页请求系统是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。
硬件支持
请求分页的页表机制
在基本分页的基础上增加了几个表项
状态位P：表示页面是否已在内存中
供程序访问时参考
访问字段A：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
供置换算法在选择换出页面时参考
修改位M：表示页面被调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存
供置换页面时参考
外存地址：页面在外存中存放的位置
供调入该页时参考
页表项组成：页号，物理块号，状态位P,访问字段A，修改位M，外存地址
缺页中断机构
找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
缺页中断处理中， 需要将目标页面调入内存，有必要时还要换出页面
缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常
一条指令在执行过程中可能产生多次缺页中断
缺页中断与一般中断的区别
在指令执行期间产生和处理中断信号
一条指令在执行过程中可能产生多次缺页中断
地址变换机构（重点关注与基本分页不同的地方）
找到页表项是需要检查页面是否在内存中
若页面不在内存中，需要请求调页
若内存空间不够，还需换出页面
页面调入内存后，需要修改相应页表项
软件支持
实现请求调页的软件
实现页面置换的软件
页面置换算法（牺牲时间为代价）
最佳置换算法（OPT）
每次选择淘汰的页面将是以后永不使用或在最长时间内不再被访问的页面，以便保证获得最低的缺页率
先进先出置换算法（FIFO）
优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面
会产生belady异常
为进程分配的物理块数增大，缺页次数不减反增的异常现象
最近最久未使用置换算法（LRU）
每次淘汰的页面是最近最久未使用的页面
硬件支持（寄存器或者栈)
寄存器
具有最小数值的寄存器对应的页面就是最近最久未使用的页面
栈
栈顶是最新被访问的页面编号，栈底是最近最久未使用页面的页面编号
最少使用置换算法（LFU）
时钟置换算法（CLOCK）（最近未使用算法（NRU））
改进型的时钟置换算法
页面缓冲算法（PBA）
影响页面换进换出的若干因素
页面置换算法（最重要因素）
写回磁盘的频率
换出的页面（已修改），暂不写回磁盘，而是把它们挂在已修改换出页面的链表上，仅当被换出页面数目达到一定值时，再一起写回
减少已修改页面换出的开销
读入内存的频率
特点
1、显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少，因此减少了页面换进、换出的开销
2、正是由于换入换出而定开销大幅度减少，才能使其采用一种较简单的置换策略。
链表
空闲页面链表
page180
修改页面链表
page180
页面分配策略
驻留集
指请求分页存储管理中给进程分配的内存块(物理页框）的集合
页面分配、置换策略
固定分配 VS 可变分配：区别在进程运行期间驻留集大小是否可变
局部置换 VS 全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页
可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需要换出别的进程页面
可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块。直到缺页率合适
何时调入页面
预调页策略：主要用于进程的首次调入；在运行前调入
请求调页策略：进程运行时，发生缺页再调页；在运行期间调入
从何处调页
对换区--采用连续存储方式，速度更快；文件区 --- 采用离散存储方式，速度更慢
对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
对换区不够大：不会修改的数据每次都从文件区调入，以后调入时，仍从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入
影响缺页率的因素
页面大小
进程所分配物理块的数目
页面置换算法
程序固有特性
抖动（颠簸）现象
页面频繁换入换出现象。主要原因是分配给进程的物理块不够
预防方法
1、采用局部置换策略
2、把工作集算法融入到处理机调度中
3、利用“L=S"准则调节缺页率
L：缺页之间的平均时间
S:平均缺页服务时间
L与S接近时，处理机和磁盘都可达到它们的最大利用率
4、选择暂停的进程
工作集
在某段时间间隔内，进行实际访问页面的集合。
工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此，若分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页
驻留集大小一般不能小于工作集大小
请求分段存储管理
请求分段系统是在分段系统的基础上，增加了请求调段及分段置换功能后形成的段氏虚拟存储系统
硬件支持
请求分段的段表机制
段表项：段名，段长，段基址，存取方式，访问字段A，修改位M,存在位P，增补位，外存始址
增加的字段（和请求分页相比）
存取方式
字段为两位，存取属性是只执行，只读和允许读/写
增补位
请求分段特有的字段，用于表示本段在运行过程中是否做过动态增长
缺段中断机构
地址变换机构
软件支持
实现请求调段的软件
实现段置换的软件
分段的共享和保护
共享段表
共享进程计数count
记录有多少进程正在共享该分段
段号
对于同一共享段，不同的进程中可以具有不同的段号，每个进程可用自己进程的段号去访问该共享段
存取控制字段
为不同的进程赋予不同的存取权限
共享段的分配与回收
分段保护
越界检查
地址变换机构来完成
存取控制检查
以段为基本单位进行
基于硬件实现
环保护机构
规定：低编号的环具有高优先权；OS核心处于0号环内
程序访问和调用的规则
1、一个程序可以访问驻留在相同环或较低特权环（外环）中的数据
2、一个程序可以调用驻留在相同环或较高特权环（内环）中的服务
请求段页式存储管理
地址翻译：TLB->页表（TLB不命中）->Cache->主存（Cache不命中）->外存（缺页）
地址转换
操作系统负责实现逻辑地址到物理地址的转换
三种方式
绝对装入：编译器负责地址转换(单道程序阶段，无操作系统）
可重定位装入：装入程序负责地址转换（早起多道批处理阶段）
动态运行时装入：运行时才进行地址转换（现代操作系统）
内存保护
保证各进程在自己的内存空间内运行，不会越界访问
两种方式
设置上下限寄存器
分别与上、下限寄存区比较
利用重定位寄存器（又称基址寄存器）、界地址寄存器(又称限长寄存器）进行判断
重定位寄存器：存放进程的起始物理地址
界地址寄存器：存放进程的最大逻辑地址
与限长寄存器比较，与基址寄存器相加
0 条评论
下一页
