导图社区 内存管理
408王道操作系统的第三章详细思维导图。内存管理是指软件运行时对计算机内存资源的分配和使用的技术。其最主要的目的是如何高效，快速的分配，并且在适当的时候释放和回收内存资源。本图对计算机操作系统部分《内存管理》章节知识点进行了归纳总结，适用于计算机考研考点的复习和记忆~
数据结构与算法 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。
操作系统是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。
计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
内存管理
1.内存的基础知识
什么是内存，有何作用
存储单元
内存地址
按字节编址
按字编址
进程运行的基本原理
指令的工作原理
操作码+若干参数（可能包含地址参数）
逻辑地址 物理地址
从写程序到程序运行
编辑代码文件
编译
由源代码文件生成目标模块
链接
由目标模块生成装入模块，链接后形成完整的逻辑地址
装入
将装入模块装入内存，装入后形成物理地址
三种链接方式
静态链接
装入前链接成一个完整装入模块
装入时动态链接
运行前边装入边链接
运行时动态链接
运行时需要目标模块才装入并链接
三种装入方式
绝对装入
编译时产生绝对地址
可重定位装入
装入时将逻辑地址转换为物理地址
动态运行时装入
运行时将逻辑地址转换为物理地址，需设置重定位寄存器
2.内存管理的概念
内存空间的分配与回收
内存空间的扩充（实现虚拟性）
地址转换
操作系统负责实现逻辑地址到物理地址的转换
三种方式
编译器负责地址转换（单道程序阶段，无操作系统）
装入程序负责地址转换（早期多道批处理阶段）
运行时才进行地址转换（现代操作系统）
存储保护
保证各进程在自己的内存空间内运行，不会越界访问
两种方式
设置上下限寄存器
利用重定位寄存器、界地址寄存器进行判断
3.覆盖与交换
覆盖技术
一个固定区
存放最活跃的程序段
固定区中的程序段在运行过程中不会调入调出
若干覆盖区
不可能同时被访问程序段可共享一个覆盖区
覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，操作系统完成自动覆盖
缺点：对用户不透明，增加了用户编程负担
交换技术
内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
磁盘分为文件区和对换区，换出的进程放在对换区
覆盖与交换的区别
覆盖是在同一个程序或进程中的
交换是在不同进程（或作业）之间的
4.连续分配管理
单一连续分配
只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
无外部碎片，有内部碎片
固定分区分配
支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装入一道作业
两种分区方式
分区大小相等
分区大小不等
动态分区分配
支持多道程序，在进程装入内存时，根据进程的大小动态的建立分区
无内部碎片，有外部碎片
外部碎片可用“紧凑”技术来解决
回收内存分区时，可能遇到四种情况
回收区之后相邻的空闲分区
回收区前有相邻的空闲分区
回收区前、后都有相邻的空闲分区
回收区前、后都没有相邻的空闲分区
5.动态分区分配算法
首次适应算法
性能最好
最佳适应算法
会产生很多太小的、难以利用的碎片
最坏适应算法
大分区容易被用完，不利于大进程
邻近适应算法
会使高地址的大分区也被用完
6.基本分页存储管理的基本概念
基本分页存储管理基本思想
把进程分页，各个页面可离散的放到各个的内存块中
重要概念
页框
页帧
内存块
物理块
页
页面
页框号
页帧号
内存块号
物理块号
页号
页面号
如何实现地址转换
计算出逻辑地址对应的页号
找到对应页面在内存中的存放位置
算出逻辑地址对应的页内偏移量
物理地址=页面地址+页内偏移量
页号、页内偏移量的计算
页号=逻辑地址/页面大小；页内偏移量=逻辑地址%页面大小
或根据逻辑地址结构计算，逻辑地址=【页号P,页内偏移量W】
页表
页表记录进程页面和实际存放的内存块之间的对应关系
一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由 页号 和块号组成
每个页表项的长度是相同的，页号是 隐含的
7.基本地址变换机构
页表寄存器的作用
存放页表起始地址
存放页表长度
地址变换过程
根据逻辑地址算出页号，页内偏移量
页号的合法性检查（与页表长度对比）
若页号合法，再根据页表起始地址、页号找到对应页表项
根据页表项中记录的内存块号、页内偏移量得到最终的地址
访问物理内存对应的内存单元
其它小细节
页内偏移量位数与页面大小之间的关系（要能用其中一个推出另一个条件
页式管理中地址是一维的
实际应用中，通常使用一个页框恰好能放入整数个页表项
为了方便找到页表项，页表一般是放在连续的内存块中的
8.具有快表的地址转换机构
局部性原理
什么是快表
引入快表后，地址的变换过程
算页号、页内偏移量
检查页号合法性
查快表，若命中，即可知道页面存放的内存块号，可直接进行5
查页表，找到页面存放的内存块号，并且将页表表项复制到快表中
根据内存块号与页内偏移量得到物理地址
访问目标内存单元
若命中，1次访存，否则2次访存
9.两级页表
单级页表存在的问题
所有页表项必须连续存放、页表过大时需要很大的连续空间
在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存
两级页表
将长长的页表在分页
逻辑地址结构：（一级页号，二级页号，页内偏移量）
注意几个术语：页目录表、外层页表、顶级页表
如何实现地址变换
按照地址结构将逻辑地址拆分为三部分
从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
根据二级页号查表，找到最终想访问的内存块号
结合页内偏移量得到物理地址
几个细节
多级页表中，各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级
多级页表的访存次数（假设没有快表机构）-N级页表访问一个逻辑地址需要N+1次
10.基本分段存储管理
分段
将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址
每个段在内存中占据连续空间，但各段之间可以不相邻
逻辑地址结构：（段号，段地址）
段表
记录逻辑段到实际存储地址的映射关系
每个段对应一个段表项。各段表项长度相等、由段号、段长、基址组成
地址变换
由逻辑地址得到段号，段内地址
段号与段表寄存器中长度比较，检查是否越界
由段表始址、段号找到对应段表项
根据段表中记录的段长，检查段内地址是否越界
分页不需要这一步
由段表中的“基址+段内地址”得到最终的物理地址
访问目标单元
分段VS分页
分页对用户不可见，分段对用户可见
分页的地址空间是一维的，分段的地址空间是二维的
分页用户只需要给出一个记忆符即可表示一个地址
分段用户在标识一个地址时，既要给出段名，也要给出段内地址
分段更容易实现信息的共享和保护（纯代码/可重入代码可以共享）
分页（单页页表），分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构
11.段页式管理方式
分段+分页
将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
逻辑地址结构：（段号 页号 页内偏移量）
段表、页表
每个段对应一个段表项，各段表项长度相同，由段号、页表长度、页表存放地址组成？？？
每个页对应一个页表项，各页表项长度相同，由页号、页面存放的内存块号组成
由逻辑地址得到段号、页号、页内偏移量
段号与段表寄存器中华的段长度比较，检查是否越界
由段表始址、段号找到段表项
根据段表中记录的页表长度，检查页号是否越界
由段表中的页表地址、页号得到查询页表、找到页表项
由页面存放的内存块号，页内偏移量得到最终的物理地址
访问一个逻辑地址所需访存次数
第一次-查段表、第二次-查页表、第三次-访问目标单元
可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
12.虚拟内存的基本概念
传统存储管理方式的特征、缺点
一次性：作业数据必须一次性全部调入内存
驻留性：作业数据在整个运行期间都会常驻内存
时间局部性
现在访问的指令、数据在不久后很可能会被再次访问
空间局部性
现在访问的内存单元周围的内存空间，很可能在不久后会被访问
高速缓冲技术
使用频繁的数据放到更高速的存储器中
虚拟内存的定义个特征
程序不需要全部装入即可运行，运行时根据需要动态的调入数据，若内存不够，还需要换出一些数据
特征
多次性
无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
对换性
无需在作业运行时一直常驻内存，而是允许在作业运行期间，将作业换入，换出
虚拟性
从逻辑上扩充了内存的容量。使用户看到的内存容量，远大于实际的容量
如何实现虚拟内存技术
访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）
新增的两个功能
虚拟内存的实现
请求分页存储管理
请求分段存储管理
请求段页式存储管理
13.请求分页管理系统
页表机制
在基本分页的基础上增加了几个表项
状态位：表示页面是否已在内存中
访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位：表示页面调入内存后是否被修改过，只有修改过的页面才能在置换时写回内存
外存地址：页面在外存中存放的位置
缺页中断机构
找到页表项后检查页面是否已在内存、若没在内存，产生缺页中断
缺页中断处理中，需要将目标页面调入内存，有必要还要换出页面
缺页中断属于内中断，属于内中断中的故障，即可能被操作系统修复的异常
一条指令在执行过程中可能产生多次缺页中断
地址变换机构（重点关注与基本分页不同的地方）
找到页表项是需要检查页面是否在内存中
若页面不在内存中，需要请求页面
若内存空间不够，还需换出页面
页面调入内存后，需要修改相应页表项
14.页面置换算法
最佳置换算法OPT
优先淘汰最长时间内不会被访问的页面
缺页率最小，性能最好，但无法实现
缺页中断未必发生页面置换，只有内存块满后的缺页才会发生页面置换
先进先出置换算法FIFO
优先淘汰最先进入内存的页面
实现简单，但性能很差，可能出现Belady异常
最近最久未使用置换算法LRU
优先淘汰最近最久没访问的页面
性能很好，但需要硬件支持，算法开销大
时钟置换算法（最近未用）CLOCK
循环扫描各页面。第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1.若第一轮没选中，则进行第二轮扫描
实现简单，算法开销小，但未考虑页面是否被修改过
选择一个淘汰页面最多会经历2轮扫描
改进型的时钟置换算法
算法开销小，性能也不错
在其他条件都相同时，优先淘汰没有修改过的页面。修改位为1表示修改过
选择一个淘汰页面最多经历4轮扫描，全是（1,1）
优先级
最近没访问、没修改
最近没访问、修改
最近访问、没修改
最近访问、修改
15.页面分配策略
驻留集
指请求分页存储管理中给进程分配的内存块的概念
页面分配、置换策略
固定分配VS可变分配
区别在于进程运行期间驻留集大小是否可变
局部置换VS全局置换
区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
固定分配局部置换
进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页
可变分配全局置换
只要发生缺页就分配新物理块，可能来自空闲物理块，也可能需要换出别的进程页面
可变分配局部置换
频繁缺页的进程，多分配一些物理块，缺页率很低的进程，回收一些物理块，直到缺页率合适
何时调入页面
预调页策略：一般用于进程运行前
请求调页策略：进程运行期间，发生缺页调页
从何处调页
对换区
采用连续存储方式，速度更快；文件区-采用离散存储方式，速度更慢
对换区足够大
运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区调入
对换区不够大
不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
UNIX方式
第一次使用的页面都从文件区调入，调出的页面都写回对换区，再次使用时从对换区调入
抖动（颠簸）现象
页面频繁换入换出的现象，主要原因是分配给进程的物理块不够
工作集
在某段时间间隔里，进程实际访问页面的集合，驻留集大小一般不能小于工作集大小。最近k次访问过的页面集合。
