本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。

本文是个人学习《现代操作系统》一书后的笔记，本文重点总结内存管理和置换算法两部分。

内存管理

理想的存储器（暂无法实现）：私有的、容量无限大的、速度无限快的、永久性的。

现实理念：分层存储器体系

管理分层存储器体系的部分称为存储管理器。

无存储器抽象

• 这种系统中实现并行的一种方法是使用多线程进行编程。

未被广泛使用的原因：线程无法实现同一时间运行没有关联的程序。

• 借助特殊硬件的帮助（参考IBM360的早期模型）

存储器抽象之一：地址空间

地址空间是一个进程可用于寻址内存的一套地址集合。

要使多个应用程序同时处于内存中且不相互影响，需要解决两个问题：保护和重定向

基址寄存器和界限寄存器

• 想达成的目标：给每个程序一个自己独有的地址空间
• 解决思路：动态重定位：简单把每个进程的地址空间映射到物理内存的不同部分。
• 解决方法：给每个CPU配置两个特殊硬件寄存器。

处理内存超载

• 交换技术

把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。

- 内存紧缩：将所有进程尽可能向下移动，将内存交换产生的小 空闲区 合成一大块。
（注：通常不进行，因为很耗CPU时间）

• 虚拟内存

空闲内存管理

使用位图

（一个位表示一块空间的情况，个人理解类似于嵌入式中的bit-band）

使用链表

维护一个记录已分配内存段和空闲内存段对的链表。

一些适配算法：

• 首次适配算法
• 下次适配算法

记录上次结束的位置，下次从该位置开始搜

• 最佳适配算法

搜索整个链表到结束，找出 最小 空闲区

• 最差适配算法

最大

• 快速适配算法

为常用大小的空闲区维护单独的链表

虚拟内存

思想：每个程序拥有自己的地址空间，该空间被分割为很多块，称为page，每个page有连续的地址范围，并被映射到物理内存。

• 边界如何处理：当程序引用了一部分不在物理内存中的地址空间时，由操作系统将缺失的部分装入物理内存并重新执行失败的指令。

加速分页进程

提供一个小型硬件设备(或通过软件实现），将虚拟地址直接映射到物理地址，而不访问页表。

（我记得6.s081的lab3就是在实现这个），该设备称为转换检测缓冲区(TLB)

针对大内存的页表

• 多级页表
• 倒排页表

页面置换算法

最优的情况（无法实现）

置换标记最大的页面。把因需要调入这个页面而发生的缺页中断推迟到将来，越久越好。

NRU（最近未使用）

LRU的近似

FIFO(先进先出）

队列

可能抛弃重要页面

第二次机会页面置换算法

对FIFO的改进，检查最老页面的R位，若为0；置换；为1，则清0并将其放至最后。（给它第二次机会）

时钟页面置换算法

对二次机会算法的改进，将页面保存在环形链表中，修改时不需要频繁移动链表，只需要将指针前移。

现实

LRU(least recently used)

两种方法：

• 软件法：在内存中维护一个所有页面的链表。最近最少使用的在表尾。
• 硬件法： 计数器

优秀但难实现

NFU(not frequently used)

LRU近似，相似程度比NRU大

老化算法

LRU近似，相似程度比NFU大

工作集页面置换算法

存在背景：大多数程序并不是均匀访问其地址空间的

• 工作集(Denning)：一个进程当前使用的页面的集合称为它的工作集。
• 颠簸(Denning):若每执行几条指令就发生一次缺页中断，就称程序发生颠簸。
• 工作集模型(Denning)：

多道程序设计系统中，经常会把进城转移到磁盘上（从内存中移走所有页面）。不少分页系统会设法跟踪进程的工作集，以确保在让进程运行之前，其工作集就已在内存中。这种预先装入工作集的方法也成为了预先调页(prepaging)

实现开销大

工作集时钟页面置换算法（在原有基础上加个环形）

挺好的