第九章&第十章

第9章：虚拟内存 (Virtual Memory) —— “画饼充饥”的存储艺术

核心思想：虚拟内存将用户的逻辑内存与物理内存彻底分离 。它允许程序在只有部分被装入内存的情况下运行 。因此，逻辑地址空间可以比物理地址空间大得多 。

一、 按需调页 (Demand Paging)：吃自助餐的哲学

程序运行前不一次性全部加载，而是真正需要用到某页时才将其带入内存 。

• 优势：减少 I/O 和内存需求，响应更快，支持更多用户同时运行 。

• 有效-无效位 (Valid-Invalid Bit)：页表项中附加此位。1 表示该页在内存中，0 表示不在内存中 。如果地址转换时发现该位为 0，就会触发缺页中断 (page fault) 。

🚨 缺页中断处理全流程 (Page Fault Handling)

1. 检查内部表：若引用无效则终止程序；若只是不在内存中，则准备调页 。

2. Trap 操作系统 。

3. 操作系统在后备存储（磁盘）中找到该页 。

4. 寻找一个空闲帧 (free frame) 。

5. 将页面换入 (swap into) 该帧 。

6. 重置页表，将验证位设为 1 。

7. 重新启动刚才被打断的指令 。

• 性能评估 (EAT)：有效访问时间 （其中 为缺页率） 。

二、 进程创建优化与内核内存分配

• 写时复制 (Copy-on-Write, COW)：允许父子进程最初共享内存中相同的页面 。只有当任一进程修改共享页时，该页才会被真正复制 。这使得进程创建更加高效 。

• 内核内存分配：从独立的空闲内存池中分配 。

  • 伙伴系统 (Buddy System)：按 2 的幂次方大小分配连续的物理页面 。如果申请块小于当前块，则将当前块对半分裂（成为“伙伴”），直到大小合适 。

  • Slab 分配 (Slab Allocation)：通过缓存 (caches) 和物理连续页 (slabs) 管理固定大小的内核对象 (kernel objects) 。

三、 页面置换 (Page Replacement)：客满时的逐客令

如果没有空闲帧，操作系统必须通过算法找一个“牺牲页 (victim frame)”将其换出 。为了减少 I/O 转移开销，使用修改位（脏位）确保只有被修改过的页面才被写回磁盘 。

⚔️ 经典置换算法大比拼

1. FIFO (先进先出)：最先带入内存的页面最先被替换 。

   • ⚠️ Belady 异常：分配给进程的物理帧越多，缺页率反而可能增加 。

2. Optimal (最优算法)：替换未来最长时间内不会被使用的页面 。实际中无法实现，仅用于衡量其他算法性能的标准 。

3. LRU (最近最少使用)：利用过去预测未来，替换最久未使用的页面 。可以通过给页表项加计数器（时钟），或使用双向链表栈（每次引用移到栈顶）来实现 。

4. LRU 近似算法：

   • 二次机会 (Second-chance/Clock)：使用引用位 (Reference bit)。如果牺牲页的引用位为 1，则将其清零，给它“第二次机会”留在内存，然后检查下一个页面 。

5. 计数算法 (Counting Algorithms)：

   • LFU：替换访问计数最小的页面 。

   • MFU：替换访问计数最大的页面（逻辑是计数小的页面可能刚调入内存还需要用） 。

四、 帧的分配 (Allocation of Frames)

• 固定分配 (Fixed Allocation)：平均分配（所有进程帧数一样）或比例分配（按进程大小比例分配，） 。

• 优先级分配 (Priority Allocation)：按优先级比例分配。发生缺页时，优先替换低优先级进程的帧 。

• 全局置换 (Global) vs 局部置换 (Local)：全局置换允许一个进程抢夺另一个进程的帧；局部置换要求进程只能从自己被分配的帧集中替换 。

五、 抖动 (Thrashing)：系统的死循环

如果一个进程没有“足够”的页面，缺页率会变得极高，导致进程忙于将页面换进换出，这就叫抖动 。

• 恶性循环：抖动会导致 CPU 利用率下降 。操作系统误以为需要增加多道程序的度数，从而添加更多进程，导致问题进一步恶化 。

• 解决方案 1：工作集模型 (Working-Set Model)：观察进程在最近 个引用中的工作集（需要的页面）。如果所有工作集的总需求帧数 大于总物理帧数 ()，就会发生抖动，此时必须挂起某个进程 。

• 解决方案 2：缺页频率方案 (Page-Fault Frequency Scheme)：设定缺页率的上下界。如果实际缺页率太高，则给进程增加帧；如果太低，则剥夺它的帧 。

六、 其他关键底层机制 (Other Considerations)

• 内存映射文件 (Memory-Mapped Files)：将磁盘块映射到内存页中，把文件 I/O 视作常规的内存访问（通过内存读写替代 read/write 系统调用），并允许多个进程共享 。

• 预调页 (Prepaging)：在进程启动前预先调入部分页面，以减少初始的缺页数量，但可能造成内存和 I/O 浪费 。

• TLB 覆盖率 (TLB Reach)：TLB 能访问的内存量（TLB 大小 页面大小）。可以通过提供多种页面大小来增加覆盖率而避免碎片 。

• 程序结构 (Program structure)：遍历二维数组时，按行遍历比按列遍历产生的缺页中断少得多 。

• I/O 互锁 (I/O Interlock)：用于 I/O 拷贝（如设备读写）的页面必须被锁定在内存中，不能被置换算法逐出 。

• 操作系统实例：

  • Windows：分配工作集最小值和最大值，使用“工作集修剪 (working set trimming)”机制在内存不足时回收多余页面 。

  • Solaris：使用 lotsfree, desfree, minfree 等阈值控制调页频率，后台扫描进程 (pageout) 的扫描速率 (scanrate) 会动态调整 。

---

📁 第10章：文件系统接口 (File-System Interface) —— 数据的超级管家

一、 文件的概念与操作

文件是连续的逻辑地址空间 。

• 常见属性：名称（Name，唯一以人类可读形式保存的信息）、类型（Type）、位置（Location）、大小（Size）、保护权限（Protection）、时间/日期及用户标识 。

• 基础操作：创建 (Create)、写入 (Write)、读取 (Read)、重新定位/寻道 (Reposition)、删除 (Delete)、截断 (Truncate) 。

  • Open (打开)：在磁盘目录结构中搜索文件项，并将其移入内存 。

  • Close (关闭)：将内存中的文件项移回磁盘目录 。

二、 文件的访问方法

1. 顺序访问 (Sequential Access)：按顺序访问（read next, write next） 。

2. 直接访问 (Direct Access)：基于相对块号的任意访问（read n, write n）。操作系统可以通过调整当前位置在直接访问的基础上模拟顺序访问 。

三、 目录结构的演变 (Directory Structure)

目录是包含所有文件信息的节点集合 。目录结构和文件本身都驻留在磁盘上 。组织目录的目的是为了效率、方便的命名和逻辑分组 。

1. 单层目录 (Single-Level)：所有用户共享一个目录。存在命名冲突和无法分组的问题 。

2. 双层目录 (Two-Level)：为每个用户分配单独的目录，引入了路径名 (Path name) 。

3. 树形结构目录 (Tree-Structured)：我们最常用的结构。支持高效搜索和强大的分组能力，使用当前/工作目录 。支持绝对或相对路径名。注意：删除一个目录，意味着删除以它为根的整个子树 。

4. 无环图目录 (Acyclic-Graph)：允许文件和子目录被共享 。

   • 会产生别名 (aliasing) 和悬空指针 (dangling pointer) 问题（文件删了但链接还在） 。

   • 解决方案：使用后向指针或“条目持有计数 (entry-hold-count)”机制 。

5. 通用图目录 (General Graph)：可能产生循环，必须使用循环检测算法或垃圾收集机制来保证安全 。

四、 文件系统安装、共享与保护

• 安装 (Mounting)：文件系统必须安装在安装点 (mount point) 之后才能被访问 。

• 共享 (Sharing)：分布式系统中，NFS（网络文件系统）是常见的文件共享方法 。

• 安全保护 (Protection)：文件所有者控制谁能做什么 。

  • 访问类型：Read, Write, Execute, Append, Delete, List 。

  • 经典权限分类：所有者 (owner)、组 (group)、公共用户 (public) 。

  • 权限计算示例：RWX 分别代表读/写/执行。权限 7 = 111（读写执行都有），6 = 110（可读写不可执行），1 = 001（仅可执行） 。