内存管理
一、内存概述
1、内存作用
内存作用：缓和CPU与硬盘之间的速度矛盾
程序执行前需要先放到内存中才能被CPU处理
2、编址方式
内存地址从0开始，每个地址对应一个存储单元
按字节编址：每个存储单元大小为1字节，即 1B，即 8个二进制位
按字编址：每个存储单元大小为1个字
二、进程运行的基本原理
1、写程序到程序运行
编译：把高级语言翻译为机器语言
链接：由目标模块生成装入模块，链接后形成完整的逻辑地址
装入（装载）：将装入模块装入内存，装入后形成物理地址
2、链接方式
1）静态装入
在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。
静态装入：装入前链接成一个完整装入模块
2）装入时动态链接
将各目标模块装入内存时，边装入边链接的链接方式
装入时动态链接：运行前边装入边链接
3）运行时动态链接
在程序执行中需要该目标模块时，才对它进行链接。其优点是便 于修改和更新，便于实现对目标模块的共享。
运行时动态链接：运行时需要目标模块才装入并链接
3、装入方式
1）绝对装入
如果知道程序将会放在内存的具体位置，就在编译的时候生成程序的物理地址。之后装入程序就会按照装入模块里面已经生成的物理地址放进内存进行运行。
只适用于单道程序的运行环境（单道批那时候没有操作系统，所以就是编译程序来干转换地址的事情）
编译时产生绝对地址
2）可重定位装入（静态重定位）
在多道程序的运行环境下，我们并不能预知当程序并发执行的时候会放在内存的哪个地方。
多个目标模块的起始地址通常都从0开始，其他的地址则是相对于0的相对地址。
在装入的时候对程序里面的一些指令和数据进行修改的过程叫做重定位，地址变换也在装入的时候一次完成，把逻辑地址转换成对应内存的物理地址。在装入的时候转换了以后就不会再进行修改，所以也叫静态重定位
装入时将逻辑地址转换为物理地址
3）动态运行时装入（动态重定位）
在要执行的时候，才把这一部分的目标模块进行地址转换。（此时已经在内存中等待运行了）所以在等待运行的时候，地址都是相对地址。
这种方式需要重定位寄存器的支持，重定位寄存器存放的是装入模块在内存中的起始位置，根据这个起始位置来确定指令，执行指令。
可以把程序放在不连续的存储区中，在程序运行之前装入他的部分代码就可以运行，然后再程序运行的时候根据需要动态申请内存。
运行时将逻辑地址转换为物理地址，需设置重定位奇存器
三、内存空间的分配与回收
1、连续分配
1）单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。
系统区：通常位于内存的低地址部分，用于存放操作系统相关数据。
用户区：用于存放用户进程相关数据。只能有一道用户程序，用户程序独占整个用户区空间。
优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护。
缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。
内部碎片：分配给某进程的内存区域中，如果有些部分没有用上
外部碎片：指内存中的某些空闲分区由于太小而难以利用
2）固定分区分配
将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业
分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分
分区说明表：实现各个分区的分配与回收。
优点：实现简单，无外部碎片。
缺点：当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能。会产生内部碎片，内存利用率低。
3）动态分区分配
在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。
空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息
空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息
回收分区：与相邻的合并或增加表项
动态分区分配没有内部碎片，但是有外部碎片。（通过紧凑技术来解决外部碎片）
动态分区分配算法
| 算法 | 算法思想 | 分区排列顺序 | 优点 | 缺点 |
|---|---|---|---|---|
| 首次适应 | 从头到尾找适合的分区 | 地址递增 | 综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序 | |
| 最佳适应 | 优先使用更小的分区 | 容量递增 | 会有更多的大分区被保留下来，更能满足大进程需求 | 会产生很多小碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序 |
| 最坏适应 | 优先使用更大的分区 | 容量递减 | 可以减少难以利用的小碎片 | 大分区容易被用完，不利于大进程；算法开销大，回收分区后可能需要对空闲分区队列重新排序 |
| 邻近适应 | 从上次查找结束位置开始查找 | 地址递增 | 不用每次都从低地址的小分区开始检索。算法开销小 | 会使高地址的大分区也被用完 |
2、非连续分配
1）基本分页存储管理
1. 分页存储
将内存空间分为一个个大小相等的分区，每个分区就是一个页框。每个页框有一个编号，即页框号，页框号从0开始。
页框=页帧=内存块=物理块=物理页面
页框号=页帧号=内存块号=物理块号=物理页号
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页。每个页面也有一个编号，即页号，页号也是从0开始。
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。
进程的最后一个页面可能没有一个页框那么大 ==> 分页存储有可能产生内部碎片
2. 页表
为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表
- 一个进程对应一张页表
- 进程的每个页面对应一个页表项
- 每个页表项由
页号和块号组成 - 页表记录进程页面和实际存放的内存块之间的映射关系
- 每个页表项的长度是相同的
计算机中内存块的数量 => 页表项中块号至少占多少字节
页号不占用存储空间
J 号内存块的起始地址 = J * 内存块大小
3. 逻辑地址的转换
对于十进制形式
页号 = 逻辑地址 / 页面长度
页内偏移量 = 逻辑地址 % 页面长度
对于二进制形式
"逻辑地址" = "页号" + "页内偏移量"
4. 地址转换的实现
- 根据逻辑地址算出页号、页内偏移量
- 页号的合法性检查（与页表长度对比）
- 若页号合法，再根据页表起始地址、页号找到对应页表项
- 根据页表项中记录的内存块号、页内偏移量 得到最终的物理地址
- 访问物理内存对应的内存单元
第一次访问内存：查页表
第二次访问内存：访问目标内存单元
5. 补充
页内偏移量位数与 页面大小之间的关系 （要能用其中一个条件推出另一个条件）
页式管理中地址是一维的
通常使一个页框怡好能放入整数个页表项
为了方便找到页表项，页表一般是放在连续的内存块中的
2）具有快表的地址变换机构
1. 快表的概述
快表（联想寄存器、TLB）是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加速地址变换的速度。内存中的页表常称为慢表。
TLB和普通 Cache 的区别：TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本
2. 具有快表的地址变换过程
- 算页号、页内偏移量
- 检查页号合法性
- 查快表。若命中，即可知道页面存放的内存块号，可直接进行⑤；若未命中则进行④
- 查页表，找到页面存放的内存块号，并且将页表项复制到快表中
- 根据内存块号与页内偏移量得到物理地址
- 访问目标内存单元
3）两级页表
1. 单级页表的问题
- 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
- 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
2. 两级页表的原理
页目录表：把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置
页目录表 = 外层页表 = 顶层页表
3. 两级页表的地址变换
- 按照地址结构将逻辑地址拆分成三部分
- 从PCB 中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
- 根据二级页号查表，找到最终想访问的内存块号
- 结合页内偏移量得到物理地址
4. 两级页表补充
多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级。
多级页表的访存次数（没有快表机构）：N级页表访问一个逻辑地址需要 N+1次访存
4）基本分段存储管理
1. 分段
分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。
- 段号的位数决定了每个进程最多可以分几个段
- 段内地址位数决定了每个段的最大长度是多少
2. 段表
段表：记录逻辑段到实际存储地址的映射关系
每个段对应一个段表项。各段表项长度相同，由段号（隐含）、段长、基质组成
3. 地址变换
- 由逻辑地址得到段号、段内地址
- 段号与段表奇存聚中的段长度比较，检查是否越界
- 由段表始址、段号找到对应段表项
- 根据段表中记录的段长，检耷段内地址是否越界
- 由段表中的
基址+段内地址得到最终的物理地址 - 访问目标单元
分段、分页管理的对比
1、分页对用户不可见，分段对用户可见
- 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
- 段是信息的逻辑单位。分页的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
2、分页的地址空间是一维的，分段的地址空间是二维的
- 分页的用户进程地址空间是一维的：程序员只需给出一个记忆符即可表示一个地址。
- 分段的用户进程地址空间是二维的：程序员在标识一个地址时，既要给出段名，也要给出段内地址。
3、分段更容易实现信息的共享和保护
4、分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构
- 分页（单级页表）：第一次访存（查内存中的页表），第二次访存（访问目标内存单元）。总共两次访存
- 分段：第一次访存（查内存中的段表），第二次访存（访问目标内存单元）。总共两次访存
- 分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。
5）段页式存储管理
1. 分页分段的特点分析
| 优点 | 缺点 | |
|---|---|---|
| 分页管理 | 内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片 | 不方便按照逻辑模块实现信息的共享和保护 |
| 分段管理 | 很方便按照逻辑模块实现信息的共享和保护 | 如果段长过大，为其分配很大的连续空间会很不方便。段式管理会产生外部碎片 |
分段管理中产生的外部碎片也可以用紧凑来解决，只是需要付出较大的时间代价
2. 段表和页表
段页式系统的逻辑地址结构：（段号，页号，页内偏移量）
- 段号的位数：每个进程最多可以分几个段
- 页号位数：每个段最大有多少页
- 页内偏移量：页面大小、内存块大小是多少
段页式管理的地址结构是二维的
3. 地址变换
- 由逻辑地址得到段号、页号、页内偏移量
- 段号与段表寄存器中的段长度比较，检查是否越界
- 由段表始址、段号找到对应段表项
- 根据段表中记录的页表长度，检查页号是否越界
- 由段表中的页表地址、页号得到查询页表，找到相应页表项
- 由页面存放的内存块号、页内偏移量得到最终的物理地址
- 访问目标单元
四、内存空间的扩充
1、覆盖技术
内存中分为一个“固定区”和若干个“覆盖区”。
将程序分为多个段（多个模块），需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）。不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
必须由程序员声明覆盖结构，操作系统完成自动覆盖。
缺点：对用户不透明，增加了用户编程负担。
2、交换技术
内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
暂时换出外存等待的进程状态为挂起状态
具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。对换区（连续）的I/O速度比文件区（离散）的更快。
交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。
PCB 会常驻内存，不会被换出外存
覆盖技术与交换技术的区别：覆盖是在同一个程序或进程中的，交换是在不同进程间的
3、虚拟存储技术
1）传统存储管理方式的缺点
一次性：作业必须一次性全部装入内存后才能开始运行。
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。
2）局部性原理
时间局部性：如果执行了程序中的某条指令、数据，那么不久后这条指令、数据很有可能再次执行。
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。
高速缓冲技术：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。
3）虚拟内存概述
程序不需全部装入即可运行。运行时根据需要动态调入数据，若内存不够，还需换出一些数据
访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）
4）虚拟内存的特征
多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虛拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
5）虚拟内存的实现（请求分页管理）
1. 页表机制
状态位：表示页面是否已在内存中
访问宇段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存
外存地址：页面在外存中存放的位置
2. 缺页中断机构
找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面
缺页中断属于内中断（属于内中断中的"故障"，即可能被系统修复的异常）
一条指令在执行过程中可能产生多次缺页中断
3. 地址变换机构
- 找到页表项是需要检查页面是否在内存中
- 若页面不再内存中，需要请求调页
- 若内存空间不够，还需换出页面
- 页面调入内存后，需要修改相应页表项
快表中有的页面一定是在内存中的
若某个页面被换出外存则快表中的。相应表项也要删除，否则可能访问错误的页面
4. 页面置换算法
| 算法规则 | 优缺点 | |
|---|---|---|
| 最佳置换算法OPT | 优先淘汰最长时间内不会被访问的页面 | 缺页率最小，性能最好。但无法实现 |
| 先进先出置换算法FIFO | 优先淘汰最先进入内存的页面 | 实现简单，但性能很差，可能出现Belady异常 |
| 最久最近未使用算法LRU | 优先淘汰最近最久没访问的页面 | 性能很好。但需要硬件支持，算法开销大 |
| 时钟置换算法CLOCK（NRU） | 循环扫描各页面。 第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。 若第一轮没选中，则进行第二轮扫描。 | 实现简单，算法开销小。但未考虑页面是否被修改过 |
| 改进型CLOCK（改进型NRU） | 若用（访问位, 修改位）的形式表述 第一轮：淘汰（0, 0） 第二轮：淘汰（0, 1），并将扫描过的页面访问位都置为0 第三轮：淘汰（0, 0） 第四轮：淘汰（0, 1） | 算法开销较小，性能也不错 |
Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。（只有 FIFO 算法会触发）
5. 页面分配策略
驻留集
请求分页存储管理中给进程分配的内存块的集合
页面分配、置换策略
- 固定分配、可变分配：区别在于进程运行期间驻留集大小是否可变
- 局部置换、全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页
可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面
可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块。直到缺页率合适
调页策略
预调页策略：一般用于进程运行前
请求调页策略：进程运行时，发现缺页再调页
从何处调页
对换区：采用连续存储方式，速度快
文件区：采用离散存储方式，速度慢
对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入
抖动（颠簸）现象
页面频繁换入换出的现象
主要原因：分配给进程的物理块不够
工作集
- 驻留集：指请求分页存储管理中给进程分配的内存块的集合。
- 工作集：指在某段时间间隔里，进程实际访问页面的集合。
驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
五、地址转换
1、地址转换概述
操作系统负责实现逻辑地址到物理地址的转换
2、地址转换的方式
- 绝对装入：编译时产生绝对地址
- 可重定位装入：装入时将逻辑地址转换为物理地址
- 动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位奇存器
六、存储保护
1、存储保护概述
保证各进程在自己的内存空间运行，不会越界访问
2、存储保护的方式
1）上下限寄存器
2）重定位寄存器、界地址寄存器
重定位寄存器（基址寄存器）：进程的起始物理地址
界地址寄存器（限长寄存器）：进程的最大逻辑地址
