虚拟内存管理
页框分配
驻留集大小
驻留集是指当前在物理内存中实际驻留的进程页面的集合。驻留集大小是表示这个集合中页面数量的指标，通常以页框（或页面框）的数量来度量。这个指标决定了进程可以直接访问的物理内存页面数量，以及在物理内存中保持的页面的范围。
驻留集大小的合理设置对系统性能至关重要。如果驻留集大小太小，进程可能经常发生页面置换，导致频繁的缺页中断，从而降低性能。如果驻留集大小太大，可能会浪费物理内存资源，并导致其他进程无法获得足够的内存。
什么是抖动
抖动（Thrashing）是指操作系统中发生的一种现象，当它花费大量时间在页面置换（将内存中的页面换入换出到磁盘）上而非执行实际的计算。这通常发生在系统的物理内存非常紧张，多个进程频繁请求的页面不在物理内存中时。
当系统为一个进程分配的物理内存不足以满足其工作集（当前活跃的页面集合）的需求时，就会频繁发生缺页中断。操作系统必须不停地从磁盘读取所需的页面到内存中，同时写出其他页面以释放空间。因为磁盘访问速度远慢于内存访问，这种频繁的磁盘I/O活动显著减慢了系统性能。
抖动的直接后果是CPU使用率下降，因为CPU在等待必要的页面从磁盘加载时处于空闲状态。系统资源被过多地用于管理内存和磁盘之间的数据交换，而非执行用户程序。抖动严重时，系统的吞吐量下降，响应时间增加，用户和应用程序都会感受到系统变得迟钝和无响应。
内存分配和置换策略
分配策略
- 固定分配
- 内存被划分为固定大小的区块。
- 每个程序或进程被分配一个或多个这样的区块，不管它们实际上需要多少内存。
- 可变分配
- 内存不是被划分为固定大小的区块，而是根据每个程序的需求动态分配。
- 当一个程序请求内存时，操作系统查看可用内存并分配足够的连续空间给该程序，这个空间刚好满足其需求。
置换策略
- 局部置换
- 每个运行的进程被分配了一定数量的内存帧（物理内存中的页面），并且仅在这些分配给它的帧中进行页面置换。
- 当一个进程需要更多的内存空间时，它只能换出自己的页面，而不能影响到其他进程的页面。
- 全局置换
- 操作系统可以从整个物理内存的范围内选择页面进行置换，不局限于特定进程的内存帧。
- 如果一个进程需要更多的内存，操作系统可以从其他进程占用的帧中换出页面。
分配和置换策略的组合
可以选择分配策略和置换策略之一进行组合，但不存在固定分配全局置换方式。
页置换算法
OPT
OPT（Optimal）页面置换算法，也称为最佳页面置换算法，是一种理论上的页面置换算法，其目标是选择最佳的页面来置换，以最大程度地减少未来的页面访问次数。
由于OPT算法需要知道未来的页面引用序列，这在实际情况下是不可能的，因此OPT算法通常用于理论研究和性能评估，以作为其他页面置换算法的性能上限的比较基准。
例子:
加入内存系统中有3个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，则置换页面如下：
| 页面引用 | 引用后内存状态 | 置换页面 | 未来页面引用 |
|---|---|---|---|
| 7 | 7 | 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2 | |
| 0 | 7, 0 | 1, 2, 0, 3, 0, 4, 2, 3, 0, 2 | |
| 1 | 7, 0, 1 | 2, 0, 3, 0, 4, 2, 3, 0, 2 | |
| 2 | 2, 0, 1 | 7 | 0, 3, 0, 4, 2, 3, 0, 2 |
| 0 | 2, 0, 1 | 3, 0, 4, 2, 3, 0, 2 | |
| 3 | 2, 0, 3 | 1 | 0, 4, 2, 3, 0, 2 |
| 0 | 2, 0, 3 | 4, 2, 3, 0, 2 | |
| 4 | 2, 4, 3 | 0 | 2, 3, 0, 2 |
| 2 | 2, 4, 3 | 3, 0, 2 | |
| 3 | 2, 4, 3 | 0, 2 | |
| 0 | 2, 0, 3 | 4 | 2 |
| 2 | 2, 0, 3 |
内存置换次数为4，缺页率为4/12 = 1/3
FIFO
FIFO（First-In-First-Out）页面置换算法是一种简单的页面置换策略，其中最早进入内存的页面被置换出去。它的工作原理类似于排队，即首先进入内存的页面也是首先离开内存的页面。
LRU
LRU（Least Recently Used）页面置换算法是一种常用的页面置换策略，它基于最近的页面访问历史来决定哪个页面应该被置换出内存。LRU算法的基本思想是，总是选择最长时间没有被访问的页面进行置换，以期望最小化未来的缺页次数。
LRU替换策略如下：
假设内存中Mem最多可以容纳N个页面（将其看成一个长度最大为N的队列），当访问一个页面P时
- 如果P在队列中出现
- 将P移动到队列末尾
- 如果P不在队列中
- 如果队列没有满的话，将P加入队列末尾
- 如果队列满的话，将队列头部的页面淘汰，并且将P加入队列末尾
例子:
加入内存系统中有3个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，则置换页面如下：
| 页面引用 | 引用后内存状态 | 置换页面 | 页面引用 | 引用后内存状态 | 置换页面 |
|---|---|---|---|---|---|
| 7 | 7 | 0 | 7, 0 | ||
| 1 | 7, 0, 1 | 2 | 0, 1, 2 | 7 | |
| 0 | 1, 2, 0 | 3 | 2, 0, 3 | 1 | |
| 0 | 2, 3, 0 | 4 | 3, 0, 4 | 2 | |
| 2 | 0, 4, 2 | 3 | 3 | 4, 2, 3 | 0 |
| 0 | 2, 3, 0 | 4 | 2 | 3, 0, 2 |
内存置换次数为6，缺页率为6/12 = 1/2
Clock
简单clock替换算法
CLOCK算法的核心思想是使用一个类似时钟的数据结构，以跟踪每个页面的访问状态。CLOCK算法维护一个环形链表，其中每个页面都有一个位（也称为访问位或引用位）。算法以时钟指针的方式扫描环形链表，查找可以被替换的页面。
Clock替换策略如下：
假设内存中Mem最多可以容纳N个页面（将其看成一个长度最大为N的循环队列），当访问一个页面P时
- 如果P在队列中出现
- 将P的引用为标记为1
- 如果P不在队列中，判断指针指向的页面引用位的数值
- 引用位为0，则替换该页面，并将指针移动到下一个位置
- 引用位为1，将该页面的引用位置为0，将指针移动到下一个位置继续判定
例子:
加入内存系统中有3个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，内存页框初始状态为 -1:0, -1:0, -1:0（粗体表示时钟指针指向的位置，引号前面的-1表示当前页面为空，引号后面的表示引用位的值）
置换页面过程如下：
| 页面引用 | 引用后内存状态 | 置换页面 | 页面引用 | 引用后内存状态 | 置换页面 |
|---|---|---|---|---|---|
| 7 | 7:1 -1:0 -1:0 | 0 | 7:1 0:1 -1:0 | ||
| 1 | 7:1 0:1 1:1 | 2 | 2:1 0:0 1:0 | 7 | |
| 0 | 2:1 0:1 1:0 | 3 | 2:1 0:0 3:1 | 1 | |
| 0 | 2:1 0:1 3:1 | 4 | 4:1 0:0 3:0 | 2 | |
| 2 | 4:1 2:1 3:0 | 0 | 3 | 4:1 2:1 3:1 | |
| 0 | 4:0 2:0 0:1 | 3 | 2 | 4:0 2:1 0:1 |
内存置换次数为5，缺页率为5/12
改进型clock算法
CLOCK-Pro算法通过引入更多的信息来更准确地确定页面是否被访问，以便更好地进行页面替换决策并且减少磁盘I/O次数。
CLOCK-Pro算法引入了两个新的位来跟踪页面的状态：
- Reference Bit (R位)：与标准CLOCK算法相同，R位用于标记页面是否最近被访问，0表示未被访问，1表示已被访问。
- Modified Bit (M位)：M位用于标记页面是否被修改，0表示未修改，1表示已修改。
- 当页面需要进入内存时，R位和M位都被设置为0，表示页面最近未被访问且未被修改。
- 当访问一个页面时，R位被设置为1，表示页面最近被访问。
- 当修改一个页面时，M位被设置为1，表示页面已被修改。
- 当需要替换页面时，CLOCK-Pro算法首先查看R位，选择R位为0的页面进行替换，这是与标准CLOCK算法相同的部分。
- 如果所有页面的R位都为1，CLOCK-Pro算法会选择M位为0的页面进行替换，以便选择一个未被修改的页面进行替换。
- 如果所有页面的R位和M位都为1，CLOCK-Pro算法会选择最早满足这两个条件的页面进行替换，以模拟LRU策略。
LFU
LFU（Least Frequently Used）算法的核心思想是：当主存没有足够的空间加载新的页面时，系统会选择那些在过去使用次数最少的页面进行置换。
基本步骤：
- 初始化：当一个页面首次加载到内存中时，为其分配一个计数器并将其设置为1（表示该页面被访问过一次）。
- 页面命中：如果要访问的页面已经在内存中，则增加该页面的访问计数。
- 页面置换：当需要为新的页面腾出空间时（也就是说，当内存中的页面已满并且需要加载一个新页面时），系统会查看所有当前在内存中的页面的访问计数，选择访问次数最少的那个页面进行置换。
内存映射文件
mmap 是一种在 Unix/Linux 操作系统中用于实现内存映射文件的系统调用。内存映射文件是一种非常有用的技术，它允许将文件映射到进程的地址空间中，使文件的内容可以像内存一样被访问。
mmap允许将文件映射到进程的虚拟地址空间，使文件的内容可以像内存一样直接访问，而不需要显式的读取或写入文件。- 这意味着当你修改映射到内存中的文件内容时，实际上是在修改物理存储设备上的文件。因此，内存映射文件对于高性能 I/O 操作非常有用，因为可以避免显式的 I/O 操作。