CH3 B

分页策略（Paging Policies）

1. 分页策略的分类

1.1 Fetch Strategies（获取策略）

• 定义：
• 决定何时将页面从辅助存储（如磁盘）加载到主内存中。
Definition: Determines when a page should be brought from secondary storage (e.g., disk) into primary memory.

• 常见策略： 1. 按需获取（Demand Fetching）：
◦ 只有在需要访问某页面时，才将其加载到主内存中。
Bring a page into primary memory only when it is needed. 2. 预取（Prepaging）：
◦ 在加载某个页面时，提前将相邻页面也加载到主内存中。
Bring a page into primary memory in advance, along with adjacent pages.

1.2 Replacement Strategies（替换策略）

• 定义：
• 当主内存已满且需要加载新页面时，决定移除哪个页面以腾出空间。
Definition: Determines which page in primary memory should be removed to make space for a new page when memory is full.

• 常见策略： 1. 最优算法（Optimal Algorithm）：
◦ 替换未来最长时间不会被访问的页面。
Replace the page that will not be used again for the longest time in the future. 2. 先进先出（FIFO）：
◦ 替换最早进入主内存的页面。
Replace the page that has been in primary memory the longest. 3. 二次机会（Second Chance）：
◦ FIFO 的改进版本，为页面提供“二次机会”，避免移除活跃页面。
An improved version of FIFO that gives pages a "second chance" to avoid removing active pages. 4. 时钟算法（Clock Algorithm）：
◦ 使用环形链表和引用位实现二次机会的改进版本。
An improved version of second chance using a circular list and reference bits. 5. 最近最少使用（LRU）：
◦ 替换最近最少被访问的页面。
Replace the page that has not been accessed for the longest time. 6. 最不常用（LFU）：
◦ 替换访问频率最低的页面。
Replace the page with the lowest access frequency. 7. 老化算法（Aging）：
◦ LFU 的改进版本，通过逐渐衰减访问频率计数器来减少历史访问的影响。
An improved version of LFU that gradually decays access frequency counters to reduce the impact of historical accesses. 8. 工作集算法（Working Set Algorithm）：
◦ 保留进程当前正在使用的页面，移除不在工作集中的页面。
Keep in memory the pages that the process is actively using and remove those not in the working set. 9. WSClock 算法：
◦ 工作集算法和时钟算法的结合，通过引用位和时间戳近似工作集。
A combination of the working set algorithm and clock algorithm, approximating the working set using reference bits and timestamps.

1.3 Clean Strategies（清理策略）

• 定义：
• 决定何时将主内存中的页面写回磁盘（如果页面被修改过）。
Definition: Determines when a page in primary memory should be written back to disk if it has been modified.

• 常见策略： 1. 立即写回（Write-Through）：
◦ 每次页面被修改时，立即将其写回磁盘。
Write the page back to disk immediately after it is modified. 2. 延迟写回（Write-Back）：
◦ 只有在页面被替换或显式刷新时，才将其写回磁盘。
Write the page back to disk only when it is replaced or explicitly flushed.

2. Fetch Strategies 的详细讲解

2.1 按需获取（Demand Fetching）

• 工作原理：
1. 当发生页面错误（Page Fault）时，检查虚拟地址是否有效。如果无效，终止进程。
When a page fault occurs, check if the virtual address is valid. If invalid, terminate the process. 2. 如果地址有效，检查页面是否已在内存中（可能被其他进程缓存）。如果是，直接跳转到第 7 步。
If the address is valid, check if the page is already in memory (possibly cached for another process). If so, skip to step 7. 3. 查找一个空闲页帧。
Find a free page frame. 4. 将磁盘块映射到页帧，并将磁盘块加载到页帧中，暂停用户进程。
Map the disk block to the page frame and load the disk block into the page frame, suspending the user process. 5. 磁盘读取完成后，更新页表映射。
After the disk read is complete, update the page table mapping. 6. 如果需要，重新启动进程。
Restart the process if necessary.

• 优点：
• 节省内存，只有在需要时才加载页面。
Advantage: Saves memory by loading pages only when needed.

• 缺点：
• 页面错误可能导致性能下降。
Disadvantage: Page faults can lead to performance degradation.

2.2 预取（Prepaging）

• 工作原理：
• 在加载某个页面时，提前将相邻页面也加载到主内存中。
When a page is loaded, bring adjacent pages into memory in advance.

• 优点：
1. 提高 I/O 效率，减少后续页面加载的延迟。
Improves I/O efficiency by reducing the latency of subsequent page loads. 2. 适合顺序访问模式。
Suitable for sequential access patterns.

• 缺点：
1. 基于预测，如果预取的页面很少被访问，效率较低。
Based on prediction; if prefetched pages are rarely accessed, efficiency is low. 2. 可能浪费内存。
May waste memory.

• 应用场景：
• 在加载页面时使用，尤其是顺序访问模式下。
Used when loading pages, especially in sequential access scenarios.

3. Page Replacement 的详细讲解

3.1 页面替换的目标

降低页面错误率（Main Objective）：
• 确保频繁使用的页面留在内存中。
Ensure frequently used pages stay in memory. • 替换的页面在一段时间内不会被再次访问。
Replace pages that are not needed for some time.
减少页面错误的延迟（Reduce Latency of Page Faults）：
• 使用高效的代码和算法。
Use efficient code and algorithms. • 替换不需要写回磁盘的页面。
Replace pages that do not need to be written back to disk.

3.2 页面替换算法

最优算法（Optimal Algorithm, OPT 或 MIN）
• 原理： 替换未来最长时间不会被访问的页面。
Principle: Replace the page that will not be used again for the longest time in the future.
• 优点： 理论上最优，页面错误率最低。
Advantage: Theoretically optimal with the lowest page fault rate.
• 缺点： 需要预知未来的页面访问序列，不可行。
Disadvantage: Requires knowledge of future page accesses, which is impractical.
先进先出算法（FIFO, First-In-First-Out）
• 原理： 替换最早进入内存的页面。
Principle: Replace the page that has been in memory the longest.
• 优点： 实现简单，开销低。
Advantage: Simple to implement with low overhead.
• 缺点： 可能出现 Belady 异常。
Disadvantage: May exhibit Belady's anomaly.
二次机会算法（Second-Chance Algorithm）
• 原理： FIFO 的改进版本，为页面提供“二次机会”，避免移除活跃页面。
Principle: An improved version of FIFO that gives pages a "second chance" to avoid removing active pages.
• 优点： 改进了 FIFO，避免了 Belady 异常。
Advantage: Improves FIFO by avoiding Belady's anomaly.
• 缺点： 需要额外的硬件支持（引用位）。
Disadvantage: Requires additional hardware support (reference bits).
时钟算法（Clock Algorithm）
• 原理： 使用环形链表和引用位实现二次机会的改进版本。
Principle: An improved version of second chance using a circular list and reference bits.
• 优点： 性能接近 LRU，实现相对简单。
Advantage: Performance is close to LRU and simpler to implement.
• 缺点： 需要额外的硬件支持。
Disadvantage: Requires additional hardware support.
最近最少使用算法（LRU, Least Recently Used）
• 原理： 替换最近最少被访问的页面。
Principle: Replace the page that has not been accessed for the longest time.
• 优点： 性能接近最优算法。
Advantage: Performance is close to the optimal algorithm.
• 缺点： 实现复杂，开销较高。
Disadvantage: Complex to implement with higher overhead.
最不常用算法（LFU, Least Frequently Used）
• 原理： 替换访问频率最低的页面。
Principle: Replace the page with the lowest access frequency.
• 优点： 适合访问频率差异较大的场景。
Advantage: Suitable for scenarios with large differences in access frequency.
• 缺点： 需要维护访问频率计数器，开销较高。
Disadvantage: Requires maintaining access frequency counters, which increases overhead.
老化算法（Aging）
• 原理： LFU 的改进版本，通过逐渐衰减访问频率计数器来减少历史访问的影响。
Principle: An improved version of LFU that gradually decays access frequency counters to reduce the impact of historical accesses.
• 优点： 更适合动态变化的访问模式。
Advantage: Better suited for dynamically changing access patterns.
• 缺点： 实现复杂，需要额外的硬件支持。
Disadvantage: Complex to implement and requires additional hardware support.
工作集算法（Working Set Algorithm）
• 原理： 保留进程当前正在使用的页面，移除不在工作集中的页面。
Principle: Keep in memory the pages that the process is actively using and remove those not in the working set.
• 优点： 有效减少页面错误率。
Advantage: Effectively reduces page fault rates.
• 缺点： 需要维护工作集信息，开销较高。
Disadvantage: Requires maintaining working set information, which increases overhead.
WSClock 算法
• 原理： 工作集算法和时钟算法的结合，通过引用位和时间戳近似工作集。
Principle: A combination of the working set algorithm and clock algorithm, approximating the working set using reference bits and timestamps.
• 优点： 性能接近工作集算法，实现相对简单。
Advantage: Performance is close to the working set algorithm and simpler to implement.
• 缺点： 需要额外的硬件支持。
Disadvantage: Requires additional hardware support.

4. 页面替换算法的对比

算法	原理	优点	缺点
Optimal	替换未来最长时间不会被访问的页面。	理论上最优，页面错误率最低。	需要预知未来的页面访问序列，不可行。
FIFO	替换最早进入内存的页面。	实现简单，开销低。	可能出现 Belady 异常。
Second-Chance	改进的 FIFO，使用引用位避免替换活跃页面。	改进了 FIFO，避免了 Belady 异常。	需要额外的硬件支持。
Clock	使用环形链表和引用位实现二次机会的改进版本。	性能接近 LRU，实现相对简单。	需要额外的硬件支持。
LRU	替换最近最少被访问的页面。	性能接近最优算法。	实现复杂，开销较高。
LFU	替换访问频率最低的页面。	适合访问频率差异较大的场景。	需要维护访问频率计数器，开销较高。
Aging	LFU 的改进版本，通过衰减访问频率计数器减少历史访问的影响。	更适合动态变化的访问模式。	实现复杂，需要额外的硬件支持。
Working Set	保留进程当前正在使用的页面，移除不在工作集中的页面。	有效减少页面错误率。	需要维护工作集信息，开销较高。
WSClock	工作集算法和时钟算法的结合，通过引用位和时间戳近似工作集。	性能接近工作集算法，实现相对简单。	需要额外的硬件支持。

总结

• Fetch Strategies：
• 按需获取（Demand Fetching）节省内存，但可能导致页面错误；预取（Prepaging）提高 I/O 效率，但可能浪费内存。

• Replacement Strategies：
• LRU 和其近似算法（如 Clock、WSClock）在实际系统中应用广泛，性能接近最优算法。
• LFU 和 Aging 适合访问频率差异较大的场景，但实现复杂且开销较高。

• Clean Strategies：
• 延迟写回（Write-Back）是主流策略，减少了频繁的磁盘写操作。

• 未来趋势：
• 随着硬件性能的提升，TLB 和缓存技术将进一步优化分页和替换策略的效率。
With advancements in hardware, TLBs and caching techniques will further optimize the efficiency of paging and replacement strategies.

补充说明

• 页面替换算法的硬件支持：
• 现代处理器通常提供硬件支持（如 TLB 和引用位）来加速页面替换和地址转换。
Modern processors often provide hardware support (e.g., TLBs and reference bits) to accelerate page replacement and address translation.

• 未来发展方向：
• 随着人工智能和机器学习的发展，动态调整页面替换策略可能成为趋势。
With the development of AI and machine learning, dynamically adjusting page replacement strategies may become a trend.

最优算法（Optimal Algorithm）与 FIFO 算法

以下是对最优算法（Optimal Algorithm）、FIFO 算法及其改进版本（Second Chance Algorithm）的详细讲解，包括它们的原理、优缺点、示例以及 Belady 异常的分析。

10. 最优算法（Optimal Algorithm）

10.1 描述

• 基本思想：
• 假设每个页面都可以标记为在第一次被引用之前将执行的指令数，即我们知道程序的未来引用序列（future reference string）。
Assume that each page can be labeled with the number of instructions that will be executed before that page is first referenced, i.e., we know the future reference string for a program. • 最优算法会选择在未来最长时间内不会被访问的页面进行替换。
The optimal page algorithm chooses the page with the highest label (farthest in the future) to be removed from memory.

• 优点：
• 最优算法产生的页面错误（Page Faults）数量最少，是理论上的最优算法。
This algorithm results in the fewest number of page faults and is the optimal solution theoretically.

• 缺点：
• 不切实际： 需要预知未来的页面引用序列，而这在实际系统中是不可能的。
Impractical because it requires knowledge of future references, which is not feasible in real systems.

• 适用场景：
• 提供与其他页面替换算法的比较基准。
Provides a basis for comparison with other page replacement schemes.

• 改进建议：
• 如果未来引用序列已知，则不应使用按需获取（Demand Fetching），而应使用预取（Prepaging）策略，使页面加载与计算重叠。
If future references are known, demand fetching should not be used; instead, prepaging should be used to overlap paging with computation.

10.2 最优算法的示例

• 引用序列：
• 假设引用序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. • 页面帧数：3。
Number of page frames: 3. • 页面错误：7 次。
Page faults: 7.

• 分析：
• 最优算法通过预测未来的页面访问序列，选择在未来最长时间内不会被访问的页面进行替换，从而最小化页面错误。

11. FIFO 页面替换算法

11.1 描述

• 基本思想：
• FIFO 算法维护一个按页面进入内存顺序排列的链表，链表头部是最早进入内存的页面，尾部是最新进入内存的页面。
Maintain a linked list of all pages in the order they came into memory, with the oldest page at the front of the list. • 当需要替换页面时，选择链表头部的页面进行替换。
The page at the beginning of the list is replaced.

• 优点：
1. 实现简单： 使用 FIFO 队列即可实现，开销低。
Easy to implement (FIFO queue) with low overhead. 2. 易于理解： 算法逻辑直观。
Intuitive and easy to understand.

• 缺点：
1. Belady 异常： 增加页面帧数可能导致页面错误增加。
Belady's anomaly: Adding more page frames may increase the number of page faults. 2. 可能移除活跃页面： 最早进入内存的页面可能是频繁使用的页面，移除它们会导致频繁的页面错误。
May evict frequently used pages, leading to frequent page faults.

11.2 FIFO 的示例

• 引用序列：
• 假设引用序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. • 页面帧数：3。
Number of page frames: 3. • 页面错误：9 次。
Page faults: 9.

• 分析：
• FIFO 算法简单易实现，但可能导致 Belady 异常，性能不如 LRU 或其他算法。

12. Belady 异常（Belady's Anomaly）

12.1 描述

• 定义：
• Belady 异常是指在某些情况下，增加页面帧数反而导致页面错误数量增加的现象。
Belady's anomaly occurs when adding more page frames results in an increased number of page faults.

• 发现者：
• Belady 在研究 FIFO 算法时首次发现该现象。
Discovered by Belady during his research on the FIFO algorithm.

• 原因：
• FIFO 算法可能移除频繁使用的页面，导致后续频繁访问这些页面时产生更多页面错误。
FIFO may evict frequently used pages, leading to more page faults when these pages are accessed again.

• 影响：
• Belady 异常表明，增加内存资源并不总是能提高性能，尤其是在使用不合适的页面替换算法时。
Belady's anomaly shows that adding memory resources does not always improve performance, especially when using inappropriate page replacement algorithms.

12.2 Belady 异常的示例

• 引用序列：
• 假设引用序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. • 页面帧数：
• 3 个页面帧时，页面错误为 9 次。
With 3 page frames: 9 page faults. • 4 个页面帧时，页面错误为 10 次。
With 4 page frames: 10 page faults.

• 分析：
• 增加页面帧数后，页面错误反而增加，这是 Belady 异常的典型表现。

13. 第二次机会算法（Second Chance Page Replacement Algorithm）

13.1 描述

• 基本思想：
• 第二次机会算法是 FIFO 的改进版本，为每个页面维护一个引用位（Reference Bit, R）。
The second chance algorithm is a modification of FIFO that maintains a reference bit (R) for each page. • 当需要替换页面时，检查页面的引用位：
◦ 如果引用位为 0（R = 0），则替换该页面。
If R = 0, evict the page. ◦ 如果引用位为 1（R = 1），则将其置为 0，并将该页面移到链表尾部（视为新加载的页面）。
If R = 1, set R = 0 and move the page to the end of the list (treat it as a newly loaded page).

• 优点：
1. 避免移除活跃页面： 通过引用位保护频繁使用的页面，减少页面错误。
Avoids evicting active pages, reducing page faults. 2. 实现简单： 在 FIFO 的基础上增加了引用位的检查，开销较低。
Simple to implement with a minor overhead for checking reference bits.

• 缺点：
1. 需要额外的硬件支持： 引用位需要硬件维护。
Requires additional hardware support for maintaining reference bits. 2. 性能依赖于引用位的分布： 如果引用位分布不均，可能导致性能下降。
Performance depends on the distribution of reference bits; uneven distribution may lead to suboptimal performance.

13.2 第二次机会算法的操作示例

• 页面列表：
• 假设页面列表按 FIFO 顺序排列，页面的引用位如下：
Page list sorted in FIFO order with reference bits (R):

1	Page A (R = 1), Page B (R = 0), Page C (R = 1), Page D (R = 0)

• 页面错误发生在时间 20，算法操作如下：
Page fault occurs at time 20:

1. 检查链表头部的页面 A，引用位 R = 1。  
   **Check the first page in the list (Page A, R = 1).**
    2. 将页面 A 的引用位置为 0，并将其移到链表尾部。  
   **Set R = 0 for Page A and move it to the end of the list.**
        3. 新的页面列表：  
   **New page list:**  
   1
Page B (R = 0), Page C (R = 1), Page D (R = 0), Page A (R = 0)

    4. 替换页面 B，因为它在链表头部且引用位为 0。  
   **Replace Page B as it is at the front of the list and R = 0.**

14. FIFO 与第二次机会算法的对比

特性	FIFO	Second Chance
原理	替换最早进入内存的页面。	改进的 FIFO，为页面提供“二次机会”。
优点	实现简单，开销低。	避免移除活跃页面，减少页面错误。
缺点	可能移除活跃页面，导致 Belady 异常。	需要额外的硬件支持（引用位）。
适用场景	简单场景，对性能要求不高的系统。	需要保护活跃页面的场景。
Belady 异常	存在 Belady 异常。	避免 Belady 异常。

15. 总结

• 最优算法（Optimal Algorithm）：
• 理论上最优，但需要预知未来的页面访问序列，实际中不可行。
Theoretically optimal but impractical due to the need for future knowledge of page references.

• FIFO 算法：
• 实现简单，但可能导致 Belady 异常，性能不如 LRU 或其他算法。
Simple to implement but may exhibit Belady's anomaly, making it less efficient than LRU or other algorithms.

• 第二次机会算法（Second Chance）：
• 改进了 FIFO，通过引用位保护活跃页面，减少页面错误，但需要额外的硬件支持。
Improves FIFO by protecting active pages with reference bits, reducing page faults, but requires additional hardware support.

• 未来趋势：
• 随着硬件性能的提升，LRU 和其近似算法（如 Clock、WSClock）将成为主流，结合硬件支持实现高效的页面替换策略。
With advancements in hardware, LRU and its approximations (e.g., Clock, WSClock) will become mainstream, supported by hardware for efficient page replacement.

是的，在 FIFO（First-In-First-Out）页面替换算法 中，如果已经查到了某个页面（即该页面在内存中），但它是最早进入内存的页面，并且此时需要加载新的页面而内存已满，那么 这个页面仍然会被替换掉。

原因分析

FIFO 的核心逻辑：
• FIFO 算法只关注页面进入内存的顺序，而不考虑页面是否最近被访问过。
• 即使某个页面已经被访问过（即“命中”），只要它是链表中最老的页面（最早进入内存的页面），在需要替换页面时，它仍然会被移除。
FIFO 的缺点：
• FIFO 不区分页面的使用频率或最近访问情况，可能导致频繁使用的页面被替换掉。
• 这种行为可能导致 Belady 异常，即增加页面帧数反而导致页面错误增加。

示例说明

假设引用序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，页面帧数为 3。

步骤解析：

初始状态：
• 页面帧为空，依次加载页面 1、2、3。
Memory: [1, 2, 3]
访问页面 4：
• 页面 4 不在内存中，需要替换最早进入的页面 1。
Memory: [2, 3, 4]
访问页面 1：
• 页面 1 不在内存中，需要替换最早进入的页面 2。
Memory: [3, 4, 1]
访问页面 2：
• 页面 2 不在内存中，需要替换最早进入的页面 3。
Memory: [4, 1, 2]
访问页面 5：
• 页面 5 不在内存中，需要替换最早进入的页面 4。
Memory: [1, 2, 5]
访问页面 1：
• 页面 1 已经在内存中（命中），不需要替换。
Memory: [1, 2, 5]
访问页面 2：
• 页面 2 已经在内存中（命中），不需要替换。
Memory: [1, 2, 5]
访问页面 3：
• 页面 3 不在内存中，需要替换最早进入的页面 1。
Memory: [2, 5, 3]
访问页面 4：
• 页面 4 不在内存中，需要替换最早进入的页面 2。
Memory: [5, 3, 4]
访问页面 5：
◦ 页面 5 已经在内存中（命中），不需要替换。
Memory: [5, 3, 4]

关键点

• 在第 8 步时，页面 1 被替换掉，尽管它刚刚被访问过（命中）。
• 这是因为 FIFO 只关注页面进入内存的顺序，而不考虑页面是否最近被访问。

FIFO 的优缺点

优点：

实现简单：
• 使用链表或队列即可实现，开销低。
易于理解：
• 算法逻辑直观，适合初学者学习。

缺点：

可能移除活跃页面：
• 最早进入内存的页面可能是频繁使用的页面，移除它们会导致频繁的页面错误。
Belady 异常：
• 增加页面帧数可能导致页面错误增加。

改进方法

为了避免 FIFO 的缺点，可以使用以下改进算法： 1. 第二次机会算法（Second Chance Algorithm）：
• 为每个页面维护一个引用位（Reference Bit, R）。
• 如果页面被访问过，引用位为 1，暂时保留该页面；如果引用位为 0，则替换该页面。 2. 时钟算法（Clock Algorithm）：
• 使用环形链表和引用位实现第二次机会的改进版本，性能接近 LRU。

总结

• 在 FIFO 算法中，即使某个页面已经被访问过（命中），只要它是最早进入内存的页面，在需要替换页面时，它仍然会被替换掉。 • 这种行为可能导致频繁使用的页面被移除，从而增加页面错误率。 • 如果需要避免这种情况，可以使用改进算法（如第二次机会算法或时钟算法）。

时钟页面替换算法（Clock Page Replacement Algorithm）

时钟页面替换算法 是 第二次机会算法（Second Chance Algorithm） 的一种实现方式，旨在以更高效的方式近似 最优页面替换算法（Optimal Page Replacement Algorithm） 的行为。

未最近使用页面替换算法（NRU, Not Recently Used）

22. 描述

• 基本思想： • 每个页面有两个位： 1. 引用位（R）： 表示页面是否最近被访问过。 2. 修改位（M）： 表示页面是否被修改过（写入磁盘）。 • 这些位会定期更新： ◦ 每隔一个时钟间隔（如 20ms），R 位会被清零（R = 0）。

• 页面分类： 页面被分为四类： 1. Class 0: 未被引用，未被修改。 2. Class 1: 未被引用，已被修改。 3. Class 2: 已被引用，未被修改。 4. Class 3: 已被引用，已被修改。

• 替换策略： • NRU 随机从 最低编号的非空类 中移除页面。

优点：

简单易实现：
• 只需要维护 R 和 M 位，硬件支持简单。
公平性：
• 确保所有页面都有机会被替换，避免某些页面长期占用内存。

缺点：

随机性：
• 随机选择页面可能导致性能不稳定。
缺乏精确性：
• 无法区分同一类页面的使用历史。

最近最少使用算法（LRU, Least Recently Used）

23. 描述

• 基本思想： • 替换掉 最近最少使用 的页面。 • 假设： • 最近使用过的页面很可能在不久的将来再次被使用。

软件实现：

• 使用链表记录页面访问顺序： • 最近使用的页面在链表头部，最少使用的页面在链表尾部。 • 每次内存访问都需要更新链表（开销较大）。

硬件实现 1：

• 使用 64 位计数器： • 每次指令执行后计数器递增。 • 页面被访问时，将计数器的值存储到页表中。 • 替换计数器值最小的页面。

硬件实现 2：

• 使用 n x n 矩阵： • 当页面 K 被访问时： 1. 将第 K 行的所有位设置为 1。 2. 将第 K 列的所有位设置为 0。 • 二进制值最小的行对应的页面是 LRU 页面。

28. LRU 示例

• 引用序列： 0, 1, 2, 3, 2, 1, 0, 3, 2, 3 • 步骤： • 跟踪每个页面的计数器值。 • 替换计数器值最小的页面。

模拟 LRU 的软件算法

改进的 NFU（Not Frequently Used）：

• 基本思想： • 使用 老化算法 模拟 LRU： 1. 每次时钟中断时，将所有计数器右移一位。 2. 将 R 位添加到计数器的最高位。 3. 这样可以优先考虑最近的 R 值。

• 优点： • 模拟了 LRU 的行为，避免了“永远不忘记”的问题。

工作集页面替换算法（Working Set Page Replacement Algorithm）

30. 描述

• 基本思想： • 工作集是 最近 k 次内存访问 中使用的页面集合。 • 页面不在工作集中时，可以被替换。 • 示例： • 如果 k = 10，工作集包含最近的 10 次访问中使用的页面。

优点：

• 减少页面错误，专注于活跃页面。 • 避免替换不活跃页面。

总结

算法	核心思想	优点	缺点
Clock Algorithm	使用环形链表和引用位实现近似 LRU 的页面替换。	实现简单，性能接近 LRU。	是近似算法，可能不够精确。
NRU	根据 R 和 M 位将页面分类，优先替换最低优先级的页面。	简单高效，适合硬件支持有限的场景。	随机选择可能导致性能不稳定。
LRU	替换最近最少使用的页面，假设最近使用的页面很可能再次被使用。	性能最优，接近理论最优算法。	硬件实现复杂，软件实现开销大。
Working Set	替换不在工作集中的页面，动态调整工作集大小以适应程序的内存访问模式。	减少页面错误，专注于活跃页面。	需要额外开销来跟踪工作集。

未来改进方向

• Clock Algorithm 是 LRU 的高效替代方案，适合硬件支持有限的场景。 • LRU 的硬件实现（如计数器或矩阵）是理想的解决方案，但需要高性能硬件。 • Working Set 算法通过动态调整工作集大小，可以进一步优化页面替换策略。

模拟 LRU 的软件算法（Simulating LRU in Software）

在现代操作系统中，LRU（Least Recently Used，最近最少使用）算法 是一种理想的页面替换策略，但由于硬件实现的复杂性，通常无法直接使用硬件支持来实现 LRU。因此，操作系统通常通过 软件算法 来模拟 LRU 的行为。

26. 模拟 LRU 的软件算法

背景问题

• LRU 的硬件实现： • 理想的 LRU 实现需要硬件支持，例如： 1. 计数器方案： 每个页面维护一个 64 位计数器，每次内存访问时更新计数器为当前时间戳或指令计数器的值。 2. 矩阵方案： 使用一个 n x n 的矩阵（n 是页面帧数），通过位操作记录页面的访问顺序。 • 这些硬件实现复杂且成本高，通常只在高性能系统中使用。

• 软件实现的必要性： • 在大多数系统中，硬件不支持直接实现 LRU，因此需要通过软件算法来模拟 LRU 的行为。 • NFU（Not Frequently Used，非频繁使用）算法 是一种常见的软件实现方式，但它存在一些问题。

26.1 NFU 算法（Not Frequently Used Algorithm）

基本思想

• 每个页面维护一个计数器，用于记录页面的访问频率。 • 操作逻辑：

每次时钟中断时，将页面的 引用位（R bit） 加到计数器中。 ◦ 如果页面被访问过，引用位 R = 1，否则 R = 0。
当发生页面错误（Page Fault）时，选择计数器值最小的页面进行替换。

问题

• “永远不忘记”： • NFU 的计数器会不断累加，即使某个页面很久之前被访问过，它的计数器值可能仍然很高。 • 这会导致一些不再活跃的页面仍然保留在内存中，影响页面替换的效率。

26.2 改进的 NFU 算法（Modified NFU with Aging）

改进思想

• 为了解决 NFU 的“永远不忘记”问题，引入了 Aging（老化）机制： • 定期右移计数器： ◦ 在每个时钟中断时，将所有页面的计数器右移一位。 ◦ 这样，计数器的低位会被丢弃，高位保留，计数器的值会逐渐“老化”。 • 将引用位（R bit）加入最高位： ◦ 在右移后，将当前时钟中断时的引用位 R 添加到计数器的最高位。 ◦ 这样可以确保最近访问的页面计数器值更高。

操作步骤

初始化： • 为每个页面维护一个计数器，初始值为 0。 • 页面的引用位 R 初始化为 0。
时钟中断时： • 对于每个页面：
1. 将计数器右移一位。
2. 如果页面的引用位 R = 1，将最高位设置为 1；否则，最高位保持为 0。
3. 重置页面的引用位 R = 0（为下一次时钟中断做准备）。
页面错误时： • 选择计数器值最小的页面进行替换。

举例说明

假设条件：

• 页面帧数：3（内存中最多容纳 3 个页面）。 • 引用序列：1, 2, 3, 2, 1, 4, 2, 3, 4, 5。 • 初始状态：内存为空。

改进的 NFU 算法的优点

动态优先级： • 通过右移计数器和引入老化机制，最近访问的页面会被赋予更高的优先级。 • 不活跃的页面会逐渐被淘汰。
避免“永远不忘记”问题： • 通过定期右移计数器，旧访问记录的影响逐渐减弱，避免了 NFU 的“永远不忘记”问题。
简单高效： • 改进的 NFU 算法在软件中实现相对简单，适合硬件不支持 LRU 的系统。

改进的 NFU 算法的缺点

近似性： • 改进的 NFU 是 LRU 的近似算法，无法完全模拟 LRU 的行为。 • 页面的访问顺序可能会被错误估计。
开销： • 每次时钟中断都需要更新所有页面的计数器，开销较大。

工作集页面置换算法（Working Set Page Replacement）笔记整理

1. 核心思想 • 目标：基于“工作集模型”（进程在一段时间内活跃访问的页面集合），优先淘汰不在工作集的页面。

• 关键机制：

• 周期性清除 R 位（每个时钟滴答时，所有页面的 R 位清零）。

• 记录页面上次使用时间（LTU）：通过 R 位判断页面是否被访问，更新 LTU。

• 淘汰策略：优先淘汰 R=0 且 (当前时间 - LTU) > τ（阈值）的页面（即长期未使用的页面）。

2. 算法步骤

周期性清除 R 位 • 每个时钟中断时，所有页面的 R 位（引用位）被清零。

• （注：R=1 表示该页面在本周期被访问过）

扫描页面表 • 当需要替换页面时，扫描物理内存中的所有页面，检查 R 位：

◦ R=1：

1
2
3

◦ 更新该页的 `LTU = 当前虚拟时间`（表示最近被访问）。  

◦ *（说明该页在工作集中，保留）*

◦ R=0：

◦ 计算页面的“年龄”（`age = 当前时间 - LTU`）。  

◦ 如果 `age > τ`：淘汰该页（不在工作集）。  

◦ 如果 `age ≤ τ`：记录该页的 `age`，后续可能淘汰年龄最大的页。

特殊情况处理 • 情况1：找到至少一个 R=0 的页面 → 淘汰其中 age 最大的页。

• 情况2：所有页面 R=1（无候选页）→ 随机选一个页面替换（优先选“干净页”，即未修改的页）。

3. 关键公式与变量 • age = current virtual time - last time used (LTU)

• 表示页面自上次访问以来的“年龄”，年龄越大，越可能被淘汰。

• 阈值 τ：

• 由系统定义的时间窗口，若 age > τ，则认为页面已不在工作集中。

4. 示例说明（结合图片） • 图片2中的页面表：

页号	R位	LTU (上次使用时间)	当前虚拟时间=2204	计算 `age`
2084	1	1980	2204 - 1980 = 224	更新 `LTU=2204`
1213	0	2014	2204 - 2014 = 190	若 `τ=200`，`age ≤ τ` → 记录年龄
1620	0	1620	2204 - 1620 = 584	若 `τ=200`，`age > τ` → 淘汰该页

• 替换决策：

• 优先淘汰 R=0 且 age > τ 的页（如页1620）。

• 若无满足条件的页，则淘汰年龄最大的 R=0 页。

WSClock Page Replacement Algorithm

36. 描述

背景问题

• 工作集算法（Working Set Algorithm）的缺点： • 工作集算法在每次页面错误时需要扫描整个页表，以找到不在工作集中的页面。 • 这种全表扫描的方式在页表较大时会导致较高的开销，影响系统性能。

• WSClock 算法的提出： • WSClock（Working Set Clock）算法是对 Clock Algorithm 和 Working Set Algorithm 的改进。 • 它结合了时钟算法的高效性和工作集算法的局部性优化，避免了全表扫描的开销。 • WSClock 算法通过维护一个 环形链表 和 引用位（R bit），以及页面的 年龄（age） 信息，实现了高效的页面替换。

37. WSClock 算法的核心思想

算法特点

基于时钟算法： • WSClock 使用一个环形链表（clock）来管理页面，类似于 Clock Algorithm。 • 页面按照环形链表的顺序依次被检查。
结合工作集信息： • 每个页面维护一个 年龄（age），表示页面最后一次被访问后经过的时间。 • 年龄用于判断页面是否仍在工作集中。
引用位（R bit）的作用： • 如果页面的 R = 1，表示页面最近被访问过，暂时保留。 • 如果页面的 R = 0，表示页面可能可以被替换。
脏页（Dirty Page）处理： • 如果页面是脏页（被修改过），需要将其写回磁盘后才能替换。 • 如果页面是干净的（未被修改过），可以直接替换。

38. WSClock 算法的操作逻辑

页面错误时的操作步骤

检查页面的引用位（R bit）： • 如果 R = 1： ◦ 将 R 置为 0，并将页面的年龄设置为当前时间。 ◦ 移动手（hand）到下一个页面，继续检查。 • 如果 R = 0： ◦ 检查页面的年龄： ◦ 如果 age ≤ t（页面仍在工作集中）： ▪ 移动手到下一个页面，继续检查。 ◦ 如果 age > t（页面不在工作集中）： ▪ 如果页面是干净的（未被修改过），直接替换该页面。 ▪ 如果页面是脏页（被修改过），将其标记为需要写回磁盘，并移动手到下一个页面。
当手回到起点时的处理： • 情况 1：至少有一个脏页被标记为需要写回磁盘： ◦ 替换第一个遇到的干净页面。 • 情况 2：没有脏页需要写回磁盘（所有页面都在工作集中）： ◦ 替换任意一个干净页面。 ◦ 如果没有干净页面，则替换当前页面，并将其写回磁盘。

39. WSClock 算法的操作示例

假设条件

• 页面帧数：3（内存中最多容纳 3 个页面）。 • 时间窗口：t = 5（单位：时钟中断次数）。 • 初始状态：内存为空。

步骤	引用序列	内存中的页面	R 位	Age	操作说明
1	1	[1]	1	1	加载页面 1，`R = 1`，`Age = 1`。
2	2	[1, 2]	1, 1	2, 2	加载页面 2，`R = 1`，`Age = 2`。
3	3	[1, 2, 3]	1, 1, 1	3, 3, 3	加载页面 3，`R = 1`，`Age = 3`。
4	2	[1, 2, 3]	1, 1, 0	4, 4, 3	页面 2 被访问，`R = 1`，`Age = 4`；页面 3 的 `R = 0`，但 `Age = 3 ≤ t`，仍在工作集中。
5	1	[1, 2, 3]	1, 0, 0	5, 5, 4	页面 1 被访问，`R = 1`，`Age = 5`；页面 2 和 3 的 `R = 0`，但仍在工作集中。
6	4	[4, 2, 3]	1, 0, 0	6, 6, 6	页面 1 被替换，页面 4 加载，`R = 1`，`Age = 6`；页面 2 和 3 的 `R = 0`，但仍在工作集中。
7	2	[4, 2, 3]	0, 1, 0	7, 7, 7	页面 4 的 `R = 0`，`Age = 7 > t`，页面 4 不在工作集中；页面 2 被访问，`R = 1`，`Age = 7`。
8	3	[4, 2, 3]	0, 0, 1	8, 8, 8	页面 4 的 `R = 0`，`Age = 8 > t`，页面 4 不在工作集中；页面 3 被访问，`R = 1`，`Age = 8`。
9	4	[4, 2, 3]	1, 0, 0	9, 9, 9	页面 4 被访问，`R = 1`，`Age = 9`；页面 2 和 3 的 `R = 0`，但仍在工作集中。
10	5	[5, 2, 4]	1, 0, 0	10, 10, 10	页面 4 被替换，页面 5 加载，`R = 1`，`Age = 10`；页面 2 的 `R = 0`，但仍在工作集中。

40. WSClock 算法的特殊情况处理

当手回到起点时的处理

情况 1：至少有一个脏页被标记为需要写回磁盘： • 替换第一个遇到的干净页面。 • 如果没有干净页面，则等待磁盘写操作完成后再替换。
情况 2：没有脏页需要写回磁盘（所有页面都在工作集中）： • 替换任意一个干净页面。 • 如果没有干净页面，则替换当前页面，并将其写回磁盘。

WSClock 算法的优缺点

优点

高效性： • WSClock 算法结合了时钟算法的高效性和工作集算法的局部性优化，避免了全表扫描的开销。 • 通过环形链表和引用位的结合，快速找到可以替换的页面。
动态适应性： • WSClock 算法能够动态调整页面的替换策略，适应进程的内存访问模式。 • 当内存访问的局部性较强时，算法倾向于保留工作集中的页面；当局部性较弱时，算法会替换不在工作集中的页面。
脏页处理： • WSClock 算法对脏页的处理更加灵活，避免了频繁的磁盘写操作。

缺点

实现复杂度： • 需要为每个页面维护 R 位和 Age，并在每次时钟中断时更新这些信息。 • 页面扫描和替换操作可能带来一定的开销。
时间窗口的选择： • 时间窗口 t 的选择对算法性能有重要影响： ◦ 如果 t 太小，可能导致频繁的页面替换。 ◦ 如果 t 太大，可能导致内存利用率下降。

WSClock 算法的改进方向

动态时间窗口： • 根据进程的内存访问模式动态调整时间窗口 t 的大小。 • 当内存访问的局部性较强时，缩小时间窗口；当局部性较弱时，扩大时间窗口。
结合其他算法： • 将 WSClock 算法与其他页面替换算法（如 LRU 或 Clock Algorithm）结合，取长补短。
硬件支持： • 如果硬件支持，可以使用硬件计数器来记录页面的访问时间和引用位，减少软件实现的复杂度。

WSClock 算法与工作集算法的对比

特性	工作集算法	WSClock 算法
核心思想	基于内存访问的局部性，保留工作集中的页面，替换不在工作集中的页面。	结合时钟算法和工作集算法，通过环形链表和引用位高效管理页面替换。
优点	动态适应性强，减少页面错误，利用内存访问的局部性。	高效性高，避免了全表扫描的开销，适合大规模页表场景。
缺点	实现复杂，时间窗口选择对性能影响较大。	实现复杂度较高，时间窗口的选择仍然需要权衡。
适用场景	内存访问具有明显局部性的场景，或者硬件不支持复杂算法的系统。	高性能系统，硬件支持有限的场景，或者需要高效页面替换的场景。

总结

• WSClock 算法 是对 Clock Algorithm 和 Working Set Algorithm 的改进，结合了两者的优点： • 高效性： 通过环形链表和引用位快速找到可以替换的页面。 • 局部性优化： 结合工作集信息，动态调整页面替换策略。 • 它是一种简单、高效的页面替换算法，适合大规模页表场景。 • 尽管实现复杂度较高，但它在实际系统中表现出色，尤其是在硬件支持有限的情况下。

41. 页面替换算法回顾

总结与评价

以下是对常见页面替换算法的总结与评价：

算法	描述	优点	缺点
Optimal（最优算法）	替换未来最长时间内不会被访问的页面。	理论上最优，页面错误最少。	不切实际，需要预知未来的页面访问序列。
NRU（Not Recently Used，非频繁使用算法）	根据页面的引用位（R bit）和修改位（M bit）分类页面，优先替换最低优先级的页面。	简单易实现，适合硬件支持有限的场景。	缺乏精确性，可能无法区分同一类页面的使用历史。
FIFO（First-In-First-Out，先进先出算法）	替换最早进入内存的页面。	实现简单，开销低。	可能移除活跃页面（Belady 异常），性能不如 LRU 或其他算法。
Second Chance（第二次机会算法）	FIFO 的改进版本，为页面提供“第二次机会”，通过引用位保护活跃页面。	避免移除活跃页面，减少页面错误。	实现稍复杂，仍可能受到 Belady 异常的影响。
Clock（时钟算法）	使用环形链表和引用位实现近似 LRU 的页面替换。	高效，适合硬件支持有限的场景。	是近似算法，可能不够精确。
LRU（Least Recently Used，最近最少使用算法）	替换最近最少使用的页面，假设最近使用的页面很可能再次被使用。	性能最优，接近理论最优算法。	硬件实现复杂，软件实现开销大。
NFU（Not Frequently Used，非频繁使用算法）	根据页面的访问频率替换访问次数最少的页面。	简单易实现，适合硬件支持有限的场景。	缺乏对最近访问的敏感性，可能无法适应动态变化的内存访问模式。
Aging（老化算法）	NFU 的改进版本，通过右移计数器和结合引用位，动态调整页面的优先级。	动态适应性强，避免“永远不忘记”问题，适合硬件支持有限的场景。	实现稍复杂，时间窗口的选择对性能有重要影响。
Working Set（工作集算法）	替换不在工作集中的页面，动态调整工作集大小以适应程序的内存访问模式。	减少页面错误，专注于活跃页面，适合内存访问具有局部性的场景。	实现复杂，时间窗口的选择对性能有重要影响。
WSClock（工作集时钟算法）	结合时钟算法和工作集算法，通过环形链表和引用位高效管理页面替换。	高效，避免了全表扫描的开销，适合大规模页表场景。	实现复杂度较高，时间窗口的选择仍然需要权衡。

评价与推荐

• 最优算法（Optimal）： • 理论上最优，但无法实际实现，主要用于作为其他算法的性能基准。 • 工作集算法（Working Set）和 WSClock 算法： • 是实际系统中表现最好的算法之一，能够动态适应内存访问的局部性。 • WSClock 算法在高效性和实现复杂度之间取得了良好的平衡，适合大规模系统。 • 时钟算法（Clock）： • 是 LRU 的高效近似算法，适合硬件支持有限的场景。 • LRU（Least Recently Used）： • 性能最优，但硬件实现复杂，适合高性能系统。 • FIFO 和 Second Chance： • 简单易实现，但性能不如 LRU 和时钟算法，适合资源受限的系统。 • NFU 和 Aging： • 是 LRU 的近似算法，适合硬件支持有限的场景，但缺乏对最近访问的敏感性。

42. 页面分配策略的设计问题

局部分配与全局分配策略

局部分配策略（Local Page Replacement）

• 定义： • 每个进程只能替换自己的页面，不能从其他进程中获取页面。 • 优点： 1. 隔离性： ◦ 进程之间的内存访问互不干扰，系统稳定性更高。 2. 实现简单： ◦ 每个进程维护自己的页表和页面替换策略，逻辑清晰。 • 缺点： 1. 内存利用率低： ◦ 如果某个进程的内存需求较大，可能导致其他进程的内存资源被浪费。 2. 无法全局优化： ◦ 系统无法跨进程优化内存分配，可能导致整体性能下降。

全局分配策略（Global Page Replacement）

• 定义： • 系统中的所有页面都可以被任意进程替换，内存资源可以跨进程共享。 • 优点： 1. 内存利用率高： ◦ 系统可以根据全局需求动态调整内存分配，最大化内存利用率。 2. 全局优化： ◦ 系统可以优先保留活跃页面，减少整体页面错误。 • 缺点： 1. 复杂性： ◦ 需要维护全局页表和页面替换策略，实现复杂度较高。 2. 进程间干扰： ◦ 某个进程的内存需求可能导致其他进程的页面被替换，影响系统稳定性。

局部分配与全局分配的对比

特性	局部分配策略	全局分配策略
内存利用率	较低，可能导致内存资源浪费。	较高，动态调整内存分配以最大化利用率。
实现复杂度	较低，每个进程独立管理页面替换。	较高，需要维护全局页表和页面替换策略。
进程隔离性	高，进程之间的内存访问互不干扰。	低，进程之间可能相互影响。
适用场景	单用户系统或对稳定性要求较高的系统。	多用户系统或对内存利用率要求较高的系统。

43. 负载控制（Load Control）

问题描述

• 系统抖动（Thrashing）： • 即使页面替换算法设计良好，系统仍可能因为内存不足而进入抖动状态。 • 抖动的特征： ◦ 进程频繁发生页面错误，导致 CPU 利用率下降。 ◦ 系统大部分时间花费在页面交换上，无法有效执行任务。

• 原因： • 系统中某些进程需要更多内存，但没有进程释放内存。 • 内存资源分配不合理，导致多个进程竞争有限的内存资源。

解决方案：负载控制

1. 减少竞争内存的进程数量

• 方法： • 将部分进程的内存页面交换到磁盘（Swap Out）。 • 释放这些进程占用的内存资源，供其他进程使用。 • 实现： • 选择内存占用较大但活跃度较低的进程进行交换。 • 将进程的页面写入磁盘后，将其从内存中移除。

2. 调整多道程序设计的程度

• 方法： • 减少系统中同时运行的进程数量。 • 通过动态调整多道程序设计的程度，避免过多进程竞争内存资源。 • 实现： • 根据系统的内存使用情况，动态增加或减少进程数量。 • 当内存资源紧张时，优先保留活跃进程，暂停或交换非活跃进程。

负载控制的优点

提高系统稳定性： • 通过减少竞争内存的进程数量，避免系统进入抖动状态。
优化内存利用率： • 动态调整内存分配，确保内存资源被高效利用。
提升系统性能： • 减少页面错误的发生频率，提高 CPU 利用率。

负载控制的缺点

交换开销： • 将进程页面交换到磁盘需要额外的 I/O 开销，可能影响系统性能。
进程调度复杂性： • 需要动态调整进程的运行状态，增加了调度的复杂性。
用户体验： • 如果交换的进程是用户正在使用的进程，可能导致用户体验下降。

总结

页面替换算法

• 最优算法（Optimal） 和 工作集算法（Working Set） 是理论上表现最好的算法。 • WSClock 算法 是实际系统中广泛使用的算法，结合了时钟算法的高效性和工作集算法的局部性优化。

页面分配策略

• 局部分配策略 简单易实现，但内存利用率较低。 • 全局分配策略 内存利用率高，但实现复杂度较高。

负载控制

• 通过减少竞争内存的进程数量和调整多道程序设计的程度，可以有效避免系统抖动。 • 负载控制需要在系统稳定性和性能之间找到平衡点。

未来改进方向

动态分配策略： • 根据系统的内存使用情况，动态选择局部分配或全局分配策略。
智能交换机制： • 使用机器学习算法预测进程的内存需求，优化交换策略。
硬件支持： • 如果硬件支持，可以使用硬件计数器记录页面访问信息，减少软件实现的复杂度。

44. 页面大小（Page Size）

小页面大小（Small Page Size）

优点

减少内部碎片（Internal Fragmentation）： • 页面大小越小，程序分配的内存块越接近其实际需求，减少了内存的浪费。 • 公式： ◦ 内部碎片 = 页面大小 - 程序剩余未使用的空间。 ◦ 小页面大小可以显著减少这种浪费。
减少程序在内存中的浪费： • 小页面大小允许程序更精确地使用内存，避免了大页面大小可能导致的内存浪费。

缺点

程序需要更多页面： • 页面越小，程序需要更多的页面来存储其代码和数据。 • 这可能导致页表变大，增加页表管理的复杂性。
页表变大： • 每个进程都需要一个页表来记录其页面的映射关系。 • 页面数量增加会导致页表的大小显著增加，占用更多内存。

页面大小的权衡公式

公式：

\[ \text{Overhead} = \frac{s}{p} \cdot e + \frac{p}{2} \] • s = 平均进程大小（以字节为单位）。 • p = 页面大小（以字节为单位）。 • e = 每个页表项的大小（以字节为单位）。 • 公式解释： • 第一项 \(\frac{s}{p} \cdot e\) 表示页表空间的开销。 ◦ \(\frac{s}{p}\) 是页面数量，乘以每个页表项的大小 \(e\)。 • 第二项 \(\frac{p}{2}\) 表示内部碎片的平均开销。 ◦ 内部碎片的平均大小是页面大小的一半。

优化条件：

• 当页面大小 \(p\) 满足以下条件时，开销最小化： \[ p = 2 \sqrt{s \cdot e} \]

页面错误处理的性能优化目标

• 减少页面错误率： 提高页面命中率，减少中断发生频率。 • 缩短页面错误处理时间： 优化磁盘 I/O 和页表更新操作。 • 提高系统吞吐量： 确保页面错误对系统性能的影响最小化。

1. 清理策略（Cleaning Policy） • 后台进程（分页守护进程，paging daemon）

• 定期检查内存状态，确保空闲帧数量充足。

• 若空闲帧不足，根据页面置换算法（如时钟算法）选择待换出的页面。

• 时钟算法（Clock Algorithm）的改进

• 使用双指针（前指针 front hand 和后指针 back hand）优化页面扫描效率。

2. 操作系统参与分页的四个时机

进程创建时 • 确定程序大小，创建页表。
进程执行时 • 重置MMU（内存管理单元），清空TLB（快表）。
发生缺页异常时 • 定位引发异常的虚拟地址，换出目标页，换入所需页。
进程终止时 • 释放页表和占用的物理页帧。

3. 缺页异常处理流程 （1）硬件与操作系统协作阶段

硬件陷入内核，保存程序计数器（PC）到栈。
保存通用寄存器状态。
操作系统确定所需的虚拟页。
检查地址有效性，寻找空闲页帧： • 若目标页帧被修改（脏页），先写回磁盘，挂起进程。

（2）页面加载与恢复执行阶段

操作系统调度磁盘读取新页，进程保持挂起。
磁盘中断完成，更新页表。
回退故障指令到起始状态。
重新调度故障进程。
恢复寄存器状态。
程序继续执行。

52. 分段（Segmentation）—— 背景与问题

分段与分页的对比

• 分页（Paging）： • 分页是一种一维的虚拟内存管理方案，将虚拟地址空间划分为固定大小的页面。 • 虚拟地址被分为页号（Page Number）和页内偏移（Offset）。 • 分页的优点是实现简单，适合管理固定大小的内存块。 • 问题： ◦ 分页将内存划分为固定大小的页面，可能导致内存碎片（如内部碎片和外部碎片）。 ◦ 对于某些应用程序，分页无法很好地反映程序的逻辑结构。

• 分段（Segmentation）： • 分段是一种二维的虚拟内存管理方案，允许程序员根据程序的逻辑结构将内存划分为多个段（Segment）。 • 每个段的大小可以动态调整，适合管理不同大小的内存块。 • 优点： ◦ 更好地反映程序的逻辑结构（如主程序、过程、函数、符号表、栈等）。 ◦ 支持动态增长和收缩，减少内存碎片问题。

分段的应用场景

• 编译器的内存需求： • 编译器在编译过程中需要管理多个表（如源代码表、符号表、常量表、解析树和栈）。 • 这些表的大小可能动态变化，如果使用分页，可能导致某些表被分割到多个页面中，增加访问开销。 • 变量数量远大于其他内存需求的情况： • 如果程序有大量的变量，但其他内存需求（如代码段、栈等）正常，分页可能导致内存浪费。 • 分段可以更好地适应这种需求，允许变量段动态增长。

53. 分段（Segmentation）—— 一维地址空间的问题

问题描述

• 在一维地址空间中，所有表（如符号表、常量表、栈等）共享同一个地址空间。 • 问题： • 如果一个表的大小增长，可能会与其他表发生冲突（即“碰撞”）。 • 例如，符号表的增长可能导致常量表被覆盖，或者栈的增长可能导致代码段被破坏。

示例：

• 假设有两个表：符号表和常量表。 • 符号表从地址 0 开始，随着变量数量的增加，符号表不断增长。 • 常量表从地址 N 开始，如果符号表增长到超过地址 N，就会覆盖常量表，导致程序出错。

54. 分段（Segmentation）—— 解决方案

分段的核心思想

• 分段通过将虚拟地址空间划分为多个独立的段（Segment），每个段可以独立增长或收缩。 • 每个段是一个逻辑单元，具有自己的起始地址和长度。 • 分段允许程序员根据程序的逻辑结构定义内存区域，避免不同表之间的冲突。

分段的优点

逻辑独立性： • 每个段可以独立管理，避免不同段之间的干扰。
动态增长： • 每个段的大小可以动态调整，适应程序的需求。
减少内存碎片： • 分段减少了内存碎片问题，因为每个段的大小可以根据需要调整。

55. 分段（Segmentation）—— 用户视角

用户对程序的视图

• 在分段模型中，程序被看作是由多个段组成的集合。 • 每个段是一个逻辑单元，具有特定的用途，例如： • 主程序（Main Program）： 存储程序的主逻辑代码。 • 过程（Procedure）： 存储子程序或函数的代码。 • 函数（Function）： 存储特定功能的代码。 • 符号表（Symbol Table）： 存储编译过程中生成的符号信息。 • 栈（Stack）： 存储函数调用的局部变量和返回地址。

分段的优势

• 分段更好地反映了程序的逻辑结构，便于程序员理解和管理内存。 • 每个段可以根据需要动态增长或收缩，适应程序的需求。

56. 分段（Segmentation）—— 逻辑视图

分段的逻辑视图

• 程序被划分为多个段，每个段具有以下特性： 1. 段号（Segment Number）： 唯一标识一个段。 2. 段内偏移（Offset）： 表示段内的具体地址。

• **示例：**

• 主程序段：`Segment 0`
• 符号表段：`Segment 1`
• 栈段：`Segment 2`

逻辑地址的组成

• 逻辑地址由两部分组成： • 段号（Virtual Segment Number）： 标识段。 • 偏移（Offset）： 指定段内的具体地址。

57. 分段架构（Segmentation Architecture）

分段地址的组成

• 逻辑地址： • 逻辑地址由两部分组成： ◦ 虚拟段号（Virtual Segment Number）： 标识段。 ◦ 偏移（Offset）： 指定段内的具体地址。

段表（Segment Table）

• 功能： • 将二维的用户定义地址（段号 + 偏移）映射为一维的物理地址。 • 段表项（Segment Table Entry, STE）： • 每个段表项包含以下信息： 1. 基地址（Base）： 段在内存中的起始物理地址。 2. 段长度（Limit）： 段的长度，用于检查偏移是否越界。 • 段表基址寄存器（Segment Table Base Register, STBR）： • 指向段表在内存中的位置。

地址转换过程

提取段号和偏移： • 从逻辑地址中提取虚拟段号和偏移。
查找段表： • 使用虚拟段号作为索引，查找段表项。
检查偏移是否越界： • 如果偏移大于段长度（Limit），则发生段越界错误。
计算物理地址： • 物理地址 = 段基地址（Base） + 偏移（Offset）。

58. 地址转换（Address Translation）

地址转换的步骤

逻辑地址分解： • 逻辑地址分为虚拟段号（Segment Number）和偏移（Offset）。
段表查找： • 使用虚拟段号查找段表项，获取段的基地址（Base）和段长度（Limit）。
越界检查： • 如果偏移大于段长度（Limit），则触发段越界错误。
物理地址计算： • 物理地址 = 段基地址（Base） + 偏移（Offset）。

示例：

• 假设逻辑地址为 <Segment 2, Offset 50>： • 查找段表，找到段号为 2 的段表项： ◦ 基地址（Base） = 2000 ◦ 段长度（Limit） = 100 • 检查偏移是否越界： ◦ 50 < 100，未越界。 • 计算物理地址： ◦ 物理地址 = 2000 + 50 = 2050。

59. 分段的示例

假设条件

• 程序由以下段组成： • 主程序段（Segment 0）：基地址 = 1000，长度 = 500 • 符号表段（Segment 1）：基地址 = 2000，长度 = 300 • 栈段（Segment 2）：基地址 = 3000，长度 = 200 • 逻辑地址：<Segment 1, Offset 150>

地址转换过程

提取段号和偏移： • 虚拟段号 = 1 • 偏移 = 150
查找段表： • 找到段号为 1 的段表项： ◦ 基地址（Base） = 2000 ◦ 段长度（Limit） = 300
越界检查： • 150 < 300，未越界。
计算物理地址： • 物理地址 = 2000 + 150 = 2150

分段的优缺点

优点

逻辑独立性： • 每个段可以独立管理，避免不同段之间的干扰。
动态增长： • 每个段的大小可以动态调整，适应程序的需求。
减少内存碎片： • 分段减少了内存碎片问题，因为每个段的大小可以根据需要调整。
反映程序逻辑： • 分段更好地反映了程序的逻辑结构，便于程序员理解和管理内存。

缺点

段表管理复杂： • 段表需要记录每个段的基地址和长度，管理复杂度较高。
段越界检查开销： • 每次地址转换都需要检查偏移是否越界，增加了开销。
外部碎片： • 分段可能导致外部碎片问题，因为段的大小不固定。

60. 练习：分段地址转换

题目描述

• 给定分段表（Segment Table），计算以下逻辑地址对应的物理地址： 1. 段号 2，偏移 247 2. 段号 4，偏移 439

分段表

段号（Segment Number）	基地址（Base）	段长度（Limit）
0	5432	350
1	115	100
2	2200	780
3	4235	1100
4	1650	400

61. 解答：段号 2，偏移 247

步骤 1：提取段号和偏移

• 段号 = 2 • 偏移 = 247

步骤 2：查找段表

• 根据分段表，找到段号为 2 的段表项： • 基地址（Base） = 2200 • 段长度（Limit） = 780

步骤 3：检查偏移是否越界

• 比较偏移与段长度： • 偏移 247 < 段长度 780，未越界。 • 如果偏移大于或等于段长度，则会触发 段越界错误（Invalid Address Error）。

步骤 4：计算物理地址

• 物理地址 = 段基地址（Base） + 偏移（Offset） • 物理地址 = 2200 + 247 = 2447

结果：

• 段号 2，偏移 247 的物理地址为 2447。

62. 解答：段号 4，偏移 439

步骤 1：提取段号和偏移

• 段号 = 4 • 偏移 = 439

步骤 2：查找段表

• 根据分段表，找到段号为 4 的段表项： • 基地址（Base） = 1650 • 段长度（Limit） = 400

步骤 3：检查偏移是否越界

• 比较偏移与段长度： • 偏移 439 > 段长度 400，越界。 • 如果偏移大于段长度，则会触发 段越界错误（Invalid Address Error）。

步骤 4：处理越界错误

• 因为偏移超出了段的范围，系统会生成一个 段越界错误，并终止程序或采取其他错误处理措施。

结果：

• 段号 4，偏移 439 的物理地址无效，触发 段越界错误。

总结：分段地址转换的步骤

1. 提取段号和偏移

• 从逻辑地址中提取虚拟段号（Segment Number）和偏移（Offset）。

2. 查找段表

• 使用虚拟段号作为索引，查找段表项。 • 段表项包含以下信息： • 基地址（Base）： 段在内存中的起始物理地址。 • 段长度（Limit）： 段的长度，用于检查偏移是否越界。

3. 检查偏移是否越界

• 比较偏移与段长度： • 如果偏移 < 段长度，偏移有效，继续计算物理地址。 • 如果偏移 ≥ 段长度，触发 段越界错误。

4. 计算物理地址

• 物理地址 = 段基地址（Base） + 偏移（Offset）。

分段地址转换的示例总结

逻辑地址	段号	偏移	段基地址（Base）	段长度（Limit）	是否越界	物理地址
`<Segment 2, Offset 247>`	2	247	2200	780	否	2200 + 247 = 2447
`<Segment 4, Offset 439>`	4	439	1650	400	是	无效地址，错误

分段存储管理（Segmentation）笔记（中文版）

1. 分段存储的优点

动态调整段大小 • 可根据需求动态扩展或收缩段（如数据段、堆栈段）。
独立的保护机制 • 每个段可设置独立的读写/执行权限，比基于页的保护更简单高效。
简化程序链接 • 链接不同模块时，只需调整段基址（无需重定位每个指令）。
代码共享便捷 • 多个进程可共享同一代码段（如共享库），只需加载一次到内存。

2. 分段存储的缺点

程序员需感知内存模型 • 在汇编层面需显式管理段寄存器（如x86的CS、DS）。
外部碎片化问题 • 动态分配段会导致内存碎片（类似交换系统的缺点）。
大段物理内存限制 • 若段大小超过物理内存容量，需复杂处理（如覆盖技术或动态加载）。

分段与分页的对比

特性	分段（Segmentation）	分页（Paging）
地址空间结构	二维地址空间（段号 + 偏移）	一维地址空间（页号 + 页内偏移）
逻辑结构	反映程序的逻辑结构（如主程序、函数、符号表等）	不反映程序的逻辑结构，仅将内存划分为固定大小的页面
动态调整	每个段的大小可以动态调整	页面大小固定，无法动态调整
内存碎片	减少内存碎片，但可能导致外部碎片	减少内部碎片，但可能导致外部碎片
共享与保护	支持段级别的共享和保护	支持页级别的共享和保护，但粒度较粗
实现复杂度	较高，需要管理段表和段越界检查	较低，只需管理页表
性能开销	段表查找和段越界检查增加开销	页表查找开销较小，但可能需要多次页表访问（多级页表）

分段与分页的结合：段页式内存管理

段页式内存管理（Segmented Paging）

• 核心思想： • 将分段和分页结合，既支持逻辑独立性，又减少内存碎片。 • 实现方式： • 每个段被划分为多个固定大小的页面。 • 使用段表管理段的基地址和长度。 • 使用页表管理段内页面的物理地址。 • 优点： • 支持逻辑独立性（分段）。 • 减少内存碎片（分页）。 • 缺点： • 实现复杂度较高，需要同时管理段表和页表。

65. 分段的优势（Advantage of Segmentation）

1. 动态增长和收缩

• 分段的大小可以动态调整，适应程序的需求。 • 例如： • 符号表可以根据编译过程中生成的符号数量动态扩展。 • 栈可以根据函数调用的深度动态增长。

2. 更简单的保护机制

• 每个段可以独立设置保护信息（如读、写、执行权限）。 • 相比分页的细粒度保护（每页单独设置权限），分段的保护机制更简单、更高效。

3. 程序链接更简单

• 分段使得程序链接变得简单： • 每个段可以独立编译和链接。 • 链接时只需调整段的基地址，无需重新组织内存中的代码和数据。

4. 代码共享

• 分段支持代码段的共享： • 多个进程可以共享同一个代码段，只需加载一次代码段。 • 例如，多个进程运行同一个程序时，可以共享程序的代码段，减少内存占用。

66. 分段的劣势（Disadvantage of Segmentation）

1. 程序员需要了解内存模型

• 在汇编语言级别，程序员需要显式管理段的使用。 • 程序员需要了解段的划分、段的基地址和段的大小，增加了编程复杂性。

2. 内存碎片问题

• 分段可能导致 外部碎片： • 外部碎片是指内存中存在许多小块的空闲内存，这些空闲内存块无法合并成足够大的块来满足大段的需求。 • 外部碎片会导致内存利用率降低。

3. 段过大的问题

• 如果某个段的大小过大，可能无法完全加载到物理内存中。 • 解决方法： • 使用 分段交换（Segment Swapping），将部分段交换到磁盘。 • 或者结合分页技术，将段划分为固定大小的页面。

分段的改进建议

1. 结合分页技术

• 段页式内存管理（Segmented Paging）： • 将分段和分页结合，既支持逻辑独立性，又减少内存碎片。 • 每个段被划分为多个固定大小的页面，使用页表管理段内页面的物理地址。 • 优点： • 支持逻辑独立性（分段）。 • 减少内存碎片（分页）。 • 缺点： • 实现复杂度较高，需要同时管理段表和页表。

2. 动态压缩技术

• 使用动态压缩技术解决外部碎片问题： • 定期将已分配的段移动到内存的一端，合并空闲内存块。 • 优点： • 提高内存利用率。 • 缺点： • 压缩操作可能导致系统性能开销。

3. 智能段管理

• 使用机器学习算法预测段的大小需求，优化段的分配和释放。 • 优点： • 提高内存利用率，减少碎片问题。

总结

分段的核心思想

• 分段通过将虚拟地址空间划分为多个独立的段，每个段可以独立管理，避免了分页的固定大小限制。 • 分段更好地反映了程序的逻辑结构，支持动态增长和收缩。

分段的关键点

逻辑地址： • 由虚拟段号和偏移组成。
段表： • 将逻辑地址映射为物理地址，记录每个段的基地址和长度。
地址转换： • 包括段表查找、越界检查和物理地址计算。
内存分配问题： • 动态存储分配可能导致检查棋盘化和外部碎片。

分段的优势

动态增长和收缩： • 每个段的大小可以动态调整，适应程序的需求。
简单的保护机制： • 每个段可以独立设置保护信息，比分页的保护机制更简单。
程序链接更简单： • 分段使得程序链接变得简单，只需调整段的基地址。
代码共享： • 分段支持代码段的共享，减少内存占用。

分段的劣势

程序员需要了解内存模型： • 在汇编语言级别，程序员需要显式管理段的使用。
内存碎片问题： • 分段可能导致外部碎片，降低内存利用率。
段过大的问题： • 如果段的大小过大，可能无法完全加载到物理内存中。

67. 分段与分页结合（Segmentation with Paging）—— 基本概念

分段与分页结合的思想

• 分段在虚拟内存中，分页在物理内存中： • 虚拟地址空间被划分为多个段（Segment），每个段是一个逻辑单元。 • 每个段内部被进一步划分为固定大小的页面（Page），物理内存中只存储段的实际页面，而不是整个段。 • 优点： • 分段的优势： 支持逻辑独立性，每个段可以动态增长或收缩。 • 分页的优势： 减少内存碎片，提高内存利用率。

地址的三部分组成

• 在分段与分页结合的系统中，虚拟地址由三部分组成： 1. 段号（Segment Number）： 标识虚拟地址所属的段。 2. 页号（Page Number）： 标识段内的页。 3. 页内偏移（Offset）： 标识页内的具体地址。

物理内存的特点

• 物理内存中只存储段的实际页面，而不是整个段。 • 如果某个段的页面未被访问，这些页面不会加载到物理内存中。

69. 分段与分页结合（Segmentation with Paging）—— 实现细节

1. 段表（Segment Table）

• 每个进程需要一个段表，用于管理段的映射信息。 • 段表的作用： • 将虚拟段号映射到物理内存中的页表。 • 每个段表项（Segment Table Entry, STE）包含以下信息： ◦ 页表基址（Page Table Base Address）： 指向该段的页表。 ◦ 段长度（Segment Length）： 段的大小（页数）。

2. 页表（Page Table）

• 每个段有一个页表，用于管理段内页面的映射信息。 • 页表的作用： • 将段内的虚拟页号映射到物理内存中的页框号（Frame Number）。 • 每个页表项（Page Table Entry, PTE）包含以下信息： ◦ 页框号（Frame Number）： 页面在物理内存中的起始地址。 ◦ 有效位（Valid Bit）： 表示该页是否在内存中。 ◦ 访问权限（Access Rights）： 如读、写、执行权限。

3. 多级页表

• 如果段的大小较大，页表可能会占用大量内存。 • 为了解决这个问题，可以使用多级页表（Multi-Level Page Table）： • 页表被划分为多个层次，只有实际使用的部分才会加载到内存中。 • 这种方式减少了内存占用，但增加了地址转换的复杂性。

70. 地址转换（Address Translation）

地址转换的过程

提取段号、页号和偏移： • 从虚拟地址中提取虚拟段号、虚拟页号和页内偏移。
查找段表： • 使用虚拟段号作为索引，查找段表项。 • 获取该段的页表基址。
查找页表： • 使用虚拟页号作为索引，查找页表项。 • 检查页表项的有效位： ◦ 如果有效位为 1，表示该页在内存中，获取页框号。 ◦ 如果有效位为 0，触发 页错误（Page Fault）。
计算物理地址： • 物理地址 = 页框号（Frame Number） + 页内偏移（Offset）。
访问物理内存： • 使用物理地址访问物理内存中的数据。

72. 分段与分页结合：MULTICS

MULTICS 的背景

• MULTICS（Multiplexed Information and Computing Service）是一个早期的多用户操作系统。 • MULTICS 是最早实现分段与分页结合的系统之一。

MULTICS 的分段与分页设计

描述符段（Descriptor Segment）： • MULTICS 使用一个特殊的段（描述符段）来存储所有段的页表信息。 • 描述符段中的每个描述符指向一个段的页表。
段描述符（Segment Descriptor）： • 每个段描述符包含以下信息： ◦ 页表基址（Page Table Base Address）： 指向该段的页表。 ◦ 段长度（Segment Length）： 段的大小（页数）。 ◦ 访问权限（Access Rights）： 如读、写、执行权限。
虚拟地址结构： • MULTICS 的虚拟地址由以下部分组成： ◦ 描述符段号（Descriptor Segment Number）： 标识描述符段。 ◦ 段号（Segment Number）： 标识虚拟地址所属的段。 ◦ 页号（Page Number）： 标识段内的页。 ◦ 页内偏移（Offset）： 标识页内的具体地址。

73. MULTICS 的虚拟地址结构

虚拟地址的字段

75. MULTICS 的 TLB（Translation Lookaside Buffer）

TLB 的作用

• TLB 是一种高速缓存，用于加速地址转换。 • TLB 存储了最近使用的段描述符和页表项的映射信息。

MULTICS 的 TLB 特点

• 两级 TLB： • MULTICS 的 TLB 分为两级： 1. 段 TLB： 存储段描述符的映射信息。 2. 页 TLB： 存储页表项的映射信息。 • 两级页表的影响： • 由于 MULTICS 使用两级页表，TLB 的设计更加复杂。 • 需要同时缓存段描述符和页表项的映射信息。

TLB 的工作流程

查找 TLB： • 首先在段 TLB 中查找段描述符。 • 如果找到，继续在页 TLB 中查找页表项。 • 如果未找到，触发 TLB 未命中（TLB Miss），需要访问内存中的描述符段和页表。
更新 TLB： • 将新访问的段描述符和页表项加载到 TLB 中。

分段与分页结合的优缺点

优点

逻辑独立性： • 分段支持逻辑独立性，每个段可以动态增长或收缩。
内存利用率高： • 分页减少内存碎片，提高内存利用率。
灵活的保护机制： • 每个段和页可以独立设置访问权限，提供更灵活的保护机制。
支持共享： • 分段支持代码段的共享，分页支持页面级别的共享。

缺点

复杂性： • 分段与分页结合增加了系统的复杂性。 • 需要管理段表、页表和 TLB。
性能开销： • 地址转换需要多次查找（段表、页表、TLB），增加了性能开销。
内存碎片： • 虽然分页减少了内存碎片，但分段可能导致外部碎片。

76. 总结（Summary）

1. 页面替换策略（Page Replacement Strategies）

页面替换策略决定了当物理内存不足时，哪些页面应该被替换出去。以下是常见的页面替换算法及其特点：

1.1 最优算法（Optimal Algorithm）

• 描述： • 替换未来最长时间内不会被访问的页面。 • 优点： • 理论上最优，页面错误最少。 • 缺点： • 不切实际，需要预知未来的页面访问序列。 • 适用场景： • 作为性能基准，用于评估其他算法的效果。

1.2 最近未使用算法（NRU, Not Recently Used）

• 描述： • 根据页面的引用位（R bit）和修改位（M bit）分类页面，优先替换最低优先级的页面。 • 优点： • 简单易实现，适合硬件支持有限的场景。 • 缺点： • 缺乏精确性，可能无法区分同一类页面的使用历史。

1.3 先进先出算法（FIFO, First-In-First-Out）

• 描述： • 替换最早进入内存的页面。 • 优点： • 实现简单，开销低。 • 缺点： • 可能移除活跃页面（Belady 异常），性能不如 LRU 或其他算法。

1.4 第二次机会算法（Second Chance）

• 描述： • FIFO 的改进版本，为页面提供“第二次机会”，通过引用位保护活跃页面。 • 优点： • 避免移除活跃页面，减少页面错误。 • 缺点： • 实现稍复杂，仍可能受到 Belady 异常的影响。

1.5 时钟算法（Clock Algorithm）

• 描述： • 使用环形链表和引用位实现近似 LRU 的页面替换。 • 优点： • 高效，适合硬件支持有限的场景。 • 缺点： • 是近似算法，可能不够精确。

1.6 最近最少使用算法（LRU, Least Recently Used）

• 描述： • 替换最近最少使用的页面，假设最近使用的页面很可能再次被使用。 • 优点： • 性能最优，接近理论最优算法。 • 缺点： • 硬件实现复杂，软件实现开销大。

1.7 频繁使用算法（NFU, Not Frequently Used）

• 描述： • 根据页面的访问频率替换访问次数最少的页面。 • 优点： • 简单易实现，适合硬件支持有限的场景。 • 缺点： • 缺乏对最近访问的敏感性，可能无法适应动态变化的内存访问模式。

1.8 老化算法（Aging）

• 描述： • NFU 的改进版本，通过右移计数器和结合引用位，动态调整页面的优先级。 • 优点： • 动态适应性强，避免“永远不忘记”问题，适合硬件支持有限的场景。 • 缺点： • 实现稍复杂，时间窗口的选择对性能有重要影响。

1.9 工作集算法（Working Set Algorithm）

• 描述： • 替换不在工作集中的页面，动态调整工作集大小以适应程序的内存访问模式。 • 优点： • 减少页面错误，专注于活跃页面，适合内存访问具有局部性的场景。 • 缺点： • 实现复杂，时间窗口的选择对性能有重要影响。

1.10 WSClock 算法（工作集时钟算法）

• 描述： • 结合时钟算法和工作集算法，通过环形链表和引用位高效管理页面替换。 • 优点： • 高效，避免了全表扫描的开销，适合大规模页表场景。 • 缺点： • 实现复杂度较高，时间窗口的选择仍然需要权衡。

2. 分页系统设计问题（Design Issues for Paging Systems）

2.1 局部分配与全局分配策略

• 局部分配策略（Local Page Replacement）： • 每个进程只能替换自己的页面，不能从其他进程中获取页面。 • 优点： 隔离性好，实现简单。 • 缺点： 内存利用率低，可能导致内存资源浪费。

• 全局分配策略（Global Page Replacement）： • 系统中的所有页面都可以被任意进程替换，内存资源可以跨进程共享。 • 优点： 内存利用率高，全局优化。 • 缺点： 实现复杂度高，进程间可能相互影响。

2.2 负载控制（Load Control）

• 问题： • 系统可能因内存不足而进入抖动状态。 • 解决方案： • 减少竞争内存的进程数量： ◦ 将部分进程的内存页面交换到磁盘，释放内存资源。 ◦ 重新考虑多道程序设计的程度。

3. 分段（Segmentation）

3.1 分段的核心思想

• 分段通过将虚拟地址空间划分为多个独立的段（Segment），每个段可以独立管理。 • 每个段是一个逻辑单元，具有自己的起始地址和长度。

3.2 分段的优势

逻辑独立性： • 每个段可以独立管理，避免不同段之间的干扰。
动态增长： • 每个段的大小可以动态调整，适应程序的需求。
减少内存碎片： • 分段减少了内存碎片问题，因为每个段的大小可以根据需要调整。
便于共享： • 不同进程可以共享某些段（如代码段），提高内存利用率。

3.3 分段的劣势

段表管理复杂： • 段表需要记录每个段的基地址和长度，管理复杂度较高。
段越界检查开销： • 每次地址转换都需要检查偏移是否越界，增加了开销。
可能产生外部碎片： • 分段可能导致外部碎片问题，因为段的大小不固定。

4. 分段与分页结合（Segmentation with Paging）

4.1 核心思想

• 分段在虚拟内存中，分页在物理内存中： • 虚拟地址空间被划分为多个段（Segment），每个段是一个逻辑单元。 • 每个段内部被进一步划分为固定大小的页面（Page），物理内存中只存储段的实际页面。

4.2 地址结构

• 虚拟地址由三部分组成： 1. 段号（Segment Number）： 标识虚拟地址所属的段。 2. 页号（Page Number）： 标识段内的页。 3. 页内偏移（Offset）： 标识页内的具体地址。

4.3 地址转换过程

查找段表： • 使用虚拟段号作为索引，查找段表项，获取页表基址。
查找页表： • 使用虚拟页号作为索引，查找页表项，获取页框号。
计算物理地址： • 物理地址 = 页框号 + 页内偏移。

4.4 MULTICS 的设计

• 描述符段（Descriptor Segment）： • 存储所有段的页表信息。 • 段描述符（Segment Descriptor）： • 包含页表基址、段长度和访问权限。 • 虚拟地址结构： • 由描述符段号、段号、页号和偏移组成。

5. 总结与对比

5.1 分页（Paging）

• 优点： • 内存利用率高，减少内存碎片。 • 实现简单，适合硬件支持。 • 缺点： • 缺乏逻辑独立性，无法反映程序的逻辑结构。 • 页面大小固定，可能导致内部或外部碎片。

5.2 分段（Segmentation）

• 优点： • 支持逻辑独立性，每个段可以动态增长或收缩。 • 更简单的保护机制，每个段可以独立设置访问权限。 • 支持代码共享，减少内存占用。 • 缺点： • 管理复杂，段表可能占用大量内存。 • 可能产生外部碎片，段过大的问题难以解决。

5.3 分段与分页结合（Segmentation with Paging）

• 优点： • 结合了分段和分页的优点，既支持逻辑独立性，又减少内存碎片。 • 提供灵活的内存管理方案。 • 缺点： • 实现复杂度高，需要同时管理段表和页表。 • 地址转换开销较大。