内存管理
三种装入方式
逻辑地址：某一个进程中存放数据的地址，一般开头为 0
绝对地址：数据在内存中的地址，一般是起始地址 + 逻辑地址
程序员写好的程序，通过编译、链接和装入，实现最终的运行
编译：由编译程序将源代码编译成若干个目标模块（高级语言翻译为机器语言）
链接：由链接程序将目标模块和所需库函数链接在一起，形成一个完整的装入模块
装入：由装入程序将装入模块装入内存运行
在不适用存储器抽象的情况下，通过保存当前程序到磁盘，读入下一个程序到内存，来实现运行多个程序。在此时内存中只有一个程序，不会发生冲突
绝对装入：编译时，知道程序放到内存哪个地方，编译程序产生绝对地址的目标代码，将程序装入绝对地址，只适用于单道程序环境
静态重定位（可重定位装入）：编译、链接后的装入模块的地址都是从 0 开始，使用逻辑地址，根据内存情况装入到适当位置，在装入时对地址进行重定位，将逻辑地址转变为物理地址（在装入时一次完成）。在装入作业时，需要一次分配作业要求的全部内存空间，作业在运行期间不能移动，不能再申请内存空间
动态重定位（动态运行时装入）：编译、链接后的装入模块的地址都是从 0 开始，使用逻辑地址，根据内存情况装入到适当位置，调用一个基址寄存器记录起始地址，在程序真正运行时进行地址转换，运行程序在内存中发生移动
内存的离散分配管理
分页式存储管理
基本思想：把内存分为一个个大小相等的小分区，再按照分区大小把进程拆分成一个个小部分
物理块：内存中一个个大小相等的小分区，每个物理块有一个物理块号，物理块号从 0 开始
页：用户进程中按照物理块大小分割的一个个小部分，每个页有一个页号，页号从 0 开始
页大小一般为 2 的整数幂，例如
；对应的，物理块大小也是 4KB 页大小具体看操作系统设置，这里的 4KB 用作举例
进程的最后一个页面可能没有物理块那么大，放入物理块后会产生内部碎片
操作系统以物理块为单位为每个进程分配内存空间，进程的每个页被放入一个物理块中，即进程的页号与内存的物理块号相对应，页面不一定被连续存放在内存中，可以放在不相邻的物理块中
逻辑地址到物理地址的转换
算出页号
以 32 位操作系统为例，逻辑地址长度为 32 位，则一个进程最大为
。第 0-11 位表示页内偏移量，也可以得出一个页的大小为 个内存单元，第 12-32 位用作表示页号，即一个进程中最多有 个页 一个内存单元大小为 1B
通过逻辑地址的第 12~32 位，可以计算出此地址对应的页号
计算页号对应的内存中的起始地址
操作系统会为每个进程维护一张页表，页表的每一个页表项记录的是页号到物理块号的转换
一个页表项的大小需要根据页的大小来决定。一个页的大小为 4K 个内存单元，意味着表示起来用 20 位，也就是接近 3 字节
页表中实际上不需要写出页号，页号是顺序记录下来的，可以通过页表始址 + 对应页号 M * 页表项大小，找到页表项在页表中的位置，从而获得物理块号
M 号物理块在内存中的实际地址就是 M * 物理块大小
算出页内地址（页内偏移量）
根据逻辑地址的 0~11 位可以算出在物理块中的地址，也就是页内偏移量
毕竟得到的物理块地址，实际上是一个物理块的起始地址
物理地址=物理块起始地址 + 页内偏移量
页表寄存器与快表
基本地址变换机构：用于实现逻辑地址到物理地址转换的一组硬件机构
页表寄存器（PTR）：记录页表的内存起始地址和页表长度
进程未执行时，页表的始址和长度记录在 PCB 中；进程被调度后，始址和长度存放到页表寄存器中
快表，又称为联想寄存器（TLB）：是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项
- 逻辑地址计算页号和页内偏移量
- 由页表寄存器获得页表长度
- 页号 <= 页表长度，则未越界
- 查看快表，是否命中，命中则直接获得物理块号
- 快表未命中则由页表寄存器获得页表始址，找到内存中的页表，计算页号对应的物理块号（页表始址 + 页号 * 页表项长度），并存入快表
- 根据物理块号 * 物理块大小 + 页内偏移量计算物理地址，找到内存中的目标页面
查看快表不需要访问内存，查看页表需要访问内存
快表命中，全程访存一次；快表未命中，全程访存两次
二级页表
对于现代计算机，大多数是
实际上一个进程不可能需要用到这么大的内存，划分多级页表后，外层页表记录内层页表，可以做到：
- 页表可以离散存放在不同的物理块中
- 只需要将用到的页表调入到内存，用不到的放在磁盘中
- 进程不可能用到这么大的内存，外层页表可以忽略没有映射的内存页表
- 转换逻辑地址得到一级页号、二级页号和页内偏移量
- 通过页表寄存器找到页目录表始址，根据一级页号得到存放二级页表的物理块号 X
- 由 X * 物理块大小，找到物理内存中存储二级页表的地址
- 根据二级页号在二级页表中找到想要访问的物理块号 Y
- 由 Y * 物理块大小，在物理内存中找到想要访问的物理块，根据页内偏移量找到物理地址
一些注意点：
- 采用多级页表机制时，各级页表的大小不能超过一个页
- 与一级页表和快表一样，访存次数看是否命中以及访问几次页表
分段式存储管理
进程中的地址空间按照程序自身的逻辑关系划分为若干个段，每个段一个段名，每段从 0 开始
以段为单位分配内存空间，每个段在内存中占据连续空间，但各段之间可以不相邻
- 由逻辑地址计算得到段号和段内偏移量
- 由段表寄存器获得段表长度
- 段号 <= 段表长度，则未越界
- 由段表寄存器获得段表始址，找到内存中的段表，计算段号对应的段表项（段表始址 + 段号 * 段表项长度）
- 段内偏移量 <= 段长，则未越界
- 根据段基址和段内偏移量计算物理地址，找到内存中的目标段
分页式与分段式的对比
页是信息的物理单位：分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管
理上的需要，完全是系统行为，对用户是不可见的
段是信息的逻辑单位：分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻
辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名
页的大小固定且由系统决定；段的长度却不固定，决定于用户编写的程序
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址
| 优点 | 缺点 | |
|---|---|---|
| 分页式管理 | 内存空间利用率高，不会产生外部碎片，只会有少量内部碎片 | 不方便按照逻辑模块实现信息的共享和保护 |
| 分段式管理 | 方便按照逻辑模块实现信息的共享和保护 | 如果段长过大，为其分配很大的连续空间会很不方便，且会产生外部碎片 |
段页式存储管理
- 由逻辑地址计算得到段号、页号和页内偏移量
- 由段表寄存器获得段表长度
- 段号 <= 段表长度，则未越界
- 由段表寄存器获得段表始址，找到内存中的段表，计算段号对应的段表项（段表始址 + 段号 * 段表项长度）
- 页号 <= 页表长度，则未越界
- 根据段表项的页表块号（也是一个物理块），找到独属于此段的页表（块号 * 物理块大小）
- 根据页号得到物理块号 * 物理块大小 + 页内偏移量计算物理地址，找到内存中的目标页面
快表命中则访存一次，未命中则访存三次
内存紧张时如何解决？
当内存空间紧张时，有两种方式解决。一种是交换技术；一种是虚拟内存。这两种一般同时使用，以提高内存利用效率
交换技术
当内存空间紧张时，通过将内存中某些进程（阻塞态、低优先级等）暂时交换到外存中，但是保留 PCB 在内存中；将处于就绪态的进程从外存调入内存，分配 CPU 并运行
交换技术也就是处理机调度中的中级调度
保存在外存什么位置？
外存通常会划分为对换区和文件区。文件区是离散分配的（追求空间利用率），对换区是连续分配的（追求文件查找的 I/O 效率）。通常会将被交换的进程保存在对换区
什么时候交换？
当运行的进程频繁缺页，需要去外存调取时，说明内存吃紧。这时候可以发生交换
交换哪些进程？
优先换出阻塞态进程、低优先级进程。PCB 保存在内存中，不会换出
虚拟内存技术
离散式存储管理存在以下特性：
- 一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：
- 作业很大时，不能全部装入内存，导致大作业无法运行
- 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降
- 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源
虚拟内存技术在内存的离散式存储管理的基础上，做出改进。不会一次将作业全部装入内存，只会装入很快会用到的部分，其他部分留在外存；程序执行过程中，访问的信息不在内存中时，由操作系统将所需信息从外存调入内存，然后继续执行程序；如果内存空间不够用，会调出暂时不用的信息到外存
虚拟内存技术的主要特征：
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
- 对换性：在作业运行时无需一直驻留内存，而是允许作业在运行过程中，被换入或换出
- 虚拟性：从逻辑上扩充了内存的大小，使用户看到的内存容量远大于实际容量
请求分页管理方式
- 由于暂时用不到的信息会留在外存，所以页表需要记录当前准备使用的页面是否在内存中，需要有标志位来识别
- 由于需要将暂时不用的信息换出内存，操作系统需要知道通过哪些指标来换出哪些页面；有些页面没有被修改过，则不用写回外存，可以直接覆盖使用；有些页面修改过，需要写回
状态位：是否已调入内存
访问字段：记录最近被访问过几次；或最近被访问的时间。供页面置换算法参考
修改位：调入内存后是否被修改
外存地址：页面在外存中的存放位置
缺页中断机制
当需要访问的页面不在内存时，产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将进程唤醒，放回就绪队列
- 如果内存中有空闲块，为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
- 如果内存中没有空闲块，由页面置换算法选择一个页面淘汰，如果被淘汰的页面在内存中修改过，则需要写回外存，未修改的页面不需要写回外存
地址变换机构
补充：
- 只有写指令才需要修改修改位。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数
- 和普通的中断处理一样，缺页中断处理依然需要保留 CPU 现场
- 需要用某种页面置换算法来决定一个换出页面
- 换入/换出页面都需要启动慢速的 I/O 操作，可见，如果换入/换出太频繁，会有很大的开销
- 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中；所以在快表中出现的页一定在内存中
页面置换算法
缺页时未必发生页面置换，如果还有可用的空闲内存块，就不用进行页面置换
缺页率 = 缺页次数 / 页面访问次数
最佳置换算法（OPT）
每次选择淘汰的页面将是以后永不使用，或者在最长的时间内不再被访问的页面，这样可以保证最低的缺页率
最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的
先进先出置换算法（FIFO）
每次选择淘汰的页面是最早进入内存的页面
实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择对头页面即可，队列的最大长度取决于系统为进程分配了多少个内存块
最近最久未使用置换算法（LRU）
每次淘汰的页面是最近最久未使用的页面，需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
实现方法：赋予每个页面对应的页表项中，用访间字段记录该页面自上次被访问以来所经历的时间 t。当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面。
时钟置换算法（CLOCK）
简单的 CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为 1；当需要淘汰一个页面时，只需检查页的访问位。如果是 0，就选择该页换出；如果是 1，则将它置为 0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是 1，则将这些页面的访问位依次置为 0 后，再进行第二轮扫描（第二轮扫描中一定会有访问位为 0 的页面，因此简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）
改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免 I/O 操作。这就是改进型的时钟置换算法的思想
修改位为 0，表示页面没有被修改过；修改位为 1， 表示页面被修改过
为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1, 1）表示一个页面近期被访问过，且被修改过
算法规则：将所有可能被置换的页面排成一个循环队列
从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
第一优先级：最近没访问且没修改的页面
若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为 0
第二优先级：最近没访问但修改过的页面
若第二轮扫描失败，则重新扫描，查找第一个（0，0） 的帧用于替换。本轮扫描不修改任何标志位
第三优先级：最近访问过但没修改的页面
若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换
第四优先级：最近访问过且没修改过的页面
由于第二轮已将所有帧的访问位设为 0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型 CLOCK 置换算法选择一个淘汰页面最多会进行四轮扫描
页面分配策略
驻留集
指请求分页存储管理中给进程分配的物理块的集合，在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小
例子：考虑一个极端情况，若某进程共有 100 个页面，则该进程的驻留集大小为 100 时进程可以全部放入内存，运行期间不可能再发生缺页。若驻留集大小为 1，则进程运行期间必定会极频繁地缺页
若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小
页面分配、置换策略
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
局部置换：发生缺页时只能选进程自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。( 采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）
可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。
采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加
可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。
如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块
可变分配 全局 置换：只要缺页就给分配新物理块
可变分配 局部 置换：要根据发生缺页的频率来动态地增加或减少进程的物理块
一些问题
何时调入页面？
预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有 50% 左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分
即运行前调入
请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘 I/O 操作，因此 I/O 开销较大
即运行时调入
何处调入页面？
- 系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快（因为对换区是连续分配方式）。在进程运行前，需将进程相关的数据从文件区复制到对换区
- 系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入
- UNIX 方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入
抖动（颠簸）现象
- 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
- 为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率