02. 操作系统

操作系统概述、进程管理、存储管理、设备管理与文件管理。

配套阅读：操作系统：课件笔记，含课程配图、例题和参考解析。

本章目录

• 操作系统概述与进程管理
• 同步、互斥与 PV 操作
• 死锁与资源分配
• 存储管理
• 磁盘访问与调度
• 设备管理
• 文件管理

专题与例题

• 信号量、PV 操作与生产者—消费者
• 死锁资源计算：最少资源数与最小需求量
• 位示图与字号计算
• 索引文件结构与容量计算
• 分页存储与地址转换

操作系统概述与进程管理

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 操作系统与进程 ## 操作系统的作用 - 管理处理器、内存、设备、文件等资源 - 控制程序执行，提供隔离、保护与共享机制 - 通过系统调用向应用提供服务，向用户提供交互接口 ## 常见类型 - 批处理：把作业成批提交，强调吞吐与资源利用 - 分时：多个任务轮流使用处理器，强调交互响应 - 实时：在规定时间约束内完成处理，区分硬实时与软实时 - 分布式：协调多台计算机的资源与服务 - 嵌入式：面向专用设备，常受资源、功耗或实时性约束 - 类型可以重叠，一个系统可能同时具有多种特点 ## 进程与线程 - 进程：程序的一次执行实例，通常是资源分配与保护的基本单位 - 线程：进程内的执行流；支持内核线程的系统通常以线程为调度单位 - 同一进程的线程通常共享地址空间、代码、全局数据、堆和打开的文件等资源 - 每个线程有自己的程序计数器、寄存器状态、栈和线程局部存储 - 线程栈逻辑上各自使用，但同进程内通常并无独立的地址空间隔离 - PCB 保存进程标识、状态、资源及调度相关信息；线程执行状态常由 TCB 保存 ## 状态与转换 - 运行：正在处理器上执行 - 就绪：具备继续执行所需条件，等待处理器 - 阻塞或等待：等待 I/O、同步事件或其他条件满足 - 就绪 → 运行：调度分派 - 运行 → 就绪：时间片耗尽或被抢占 - 运行 → 阻塞：等待事件或资源 - 阻塞 → 就绪：事件完成或条件满足，再等待调度 - 五态模型：在运行、就绪、阻塞之外，增加新建与终止 ## 并发与切换 - 并发：多个任务在一段时间内交错推进；并行：多个任务同时执行 - 上下文切换：保存当前任务状态，恢复下一个任务状态 - 切换有开销；同进程线程切换通常可避免完整地址空间切换

同步、互斥与 PV 操作

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 同步、互斥与信号量 ## 进程之间的制约 - 互斥：竞争共享资源，同一时刻只允许一个执行流进入对应临界区 - 同步：协作任务按规定的先后关系推进 - 临界资源：不能被多个执行流同时以冲突方式访问的共享资源 - 临界区：访问该临界资源的一段程序 - 仅仅读取或修改普通变量，不能自动保证并发原子性 ## 信号量与 P/V 操作 - P 或 wait：申请一个许可，暂时没有许可时等待 - V 或 signal：归还或增加一个许可，使等待者有机会继续 - P/V 必须是原子操作，不能被其他相关操作观察到中间状态 - 计数信号量初值通常等于可用资源数 - 用作互斥时初值为 1，用作事件同步时常初始化为 0 - 记录型信号量的一种约定 - P：先减 1，若结果小于 0，则阻塞调用者 - V：先加 1，若结果不大于 0，则唤醒一个等待者 - 负值的绝对值表示等待者数；并非所有信号量接口都暴露负值 - 互斥锁通常有持有者约束，不能把所有二值信号量等同于互斥锁 ## 前趋关系 - 对约束 A 完成后 B 才能开始，设置初值为 0 的信号量 s - A 完成对应动作后执行 V(s)，B 在动作前执行 P(s) - 多个前驱：后继需要等待所有相应条件 - 多个后继：需要分别发出足够的许可，单次 V 不会自动广播给所有后继 ## 有界缓冲区 - 容量为 N：empty = N，full = 0，mutex = 1 - 生产者：P(empty) → P(mutex) → 放入数据 → V(mutex) → V(full) - 消费者：P(full) → P(mutex) → 取出数据 → V(mutex) → V(empty) - 先等待空位或数据，再获取缓冲区互斥权，避免持锁等待对方才能满足的条件 - full 与 empty 表示数量条件，mutex 保护缓冲区及相关索引

死锁与资源分配

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 死锁与资源分配 ## 死锁的必要条件 - 互斥：某些资源只能由一个进程占有 - 保持并等待：已经持有资源，同时等待其他资源 - 不可剥夺：已分配资源不能被强制收回，只能由持有者释放 - 循环等待：存在进程等待链，最后一个又等待第一个持有的资源 - 四个条件是必要条件；多实例资源中仅看到环不一定能判定死锁 ## 处理方法 - 预防：破坏至少一个必要条件 - 一次性申请所需资源、允许适当剥夺、统一资源申请顺序等 - 避免：分配前检查是否仍处于安全状态 - 银行家算法利用最大需求、已分配量和可用量寻找安全序列 - 不安全状态可能导致死锁，但并不等于已经死锁 - 检测与恢复：允许死锁发生，检测后通过终止进程或回收资源解除 - 死锁不同于饥饿；饥饿可能由长期不公平的调度造成 ## 资源分配图 - 进程结点表示任务；资源结点及其内部实例表示资源 - 请求边：进程 → 资源；分配边：资源实例 → 进程 - 无环时无死锁；每种资源只有一个实例时，有环即可判定死锁 - 多实例情形需结合请求量与可用量化简 - 找到当前请求可被满足的进程，假定其完成并释放全部资源 - 删除相关边后继续化简；在标准可重用资源模型中，不能完全化简表明存在死锁 ## 单类资源的数量界限 - 设 m 个进程，各自最多需要 k 个同类、可重用、互斥资源，k ≥ 1 - 假设需求能够被满足，进程获得所需资源后能完成并释放，且无其他阻塞依赖 - 总资源数 R ≥ m(k - 1) + 1，可保证不会因争抢这类资源而死锁 - 原因：即使各进程都持有 k - 1 个资源，仍有一个资源使至少一个进程完成 - R 小于该界限只说明无法用此界限保证安全，不代表任何执行顺序都会死锁 - 多类资源或不同最大需求，须按具体分配状态分析

存储管理

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 内存分配与碎片 ## 地址与保护 - 逻辑地址或虚拟地址：程序使用的地址 - 物理地址：主存硬件所使用的地址 - 地址转换把程序地址映射到实际存储位置，并结合权限检查进行保护 - 静态重定位在装入等阶段完成，动态重定位在运行时由硬件配合完成 ## 连续分配 - 单一连续分配：用户区一次主要容纳一个用户程序 - 固定分区：预先划分若干固定大小的区域 - 分区内用不完的空间形成内部碎片 - 动态分区：按进程需要划分连续空间 - 分配与回收后产生分散的小空闲区，形成外部碎片 - 紧凑：移动已分配区域以合并空闲区，需要重定位支持并产生额外开销 ## 动态分区分配策略 - 首次适应：从低地址开始，选第一个足够大的空闲区 - 循环首次适应：从上次查找位置继续寻找 - 最佳适应：选能够满足请求的最小空闲区，可能留下较小碎片 - 最坏适应：选最大的空闲区，尽量留下较大的剩余区 - 性能与碎片情况依赖请求序列及空闲区管理结构 ## 回收与共享 - 回收分区后，与地址相邻的空闲区合并 - 共享内存让多个进程映射同一物理区域，访问仍需同步与权限控制 - 写时复制：初始共享页面，发生写入时再复制，以减少不必要的数据复制

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 分页、分段与地址转换 ## 分页存储 - 虚拟地址空间划为页，物理内存划为同样大小的页框 - 一个进程的各页可放在不连续页框中，页表保存映射关系 - 设页大小为 P，虚拟地址为 A - 页号 p = ⌊A / P⌋，页内偏移 d = A mod P - 查询页表获得页框号 f，物理地址为 f × P + d - 若 P = 2^k 字节，地址低 k 位为页内偏移，高位为页号 - 页号与偏移是地址字段划分，不能把页号直接与偏移作普通加法 - 分页避免按进程连续分配造成的外部碎片，但末页可能有内部碎片 ## 页表与快表 - 页表项可包含页框号、有效或驻留位、访问权限、访问位和修改位 - 多级页表：分层组织页表，减少稀疏地址空间的页表占用 - TLB：缓存近期地址转换结果，减少查页表开销 - TLB 未命中需要查询页表，不等于页面不在内存，也不等于缺页 ## 分段存储 - 按程序逻辑划分代码段、数据段、栈段等，段长可以不同 - 逻辑地址由段号 s 和段内偏移 d 组成 - 段表记录段基址 b、段长 L 与权限 - 检查 0 ≤ d < L 后，物理地址为 b + d；越界则触发保护异常 - 便于按逻辑单位共享与保护，纯分段的连续段分配可能产生外部碎片 ## 段页式存储 - 先按逻辑分段，每段内部再划分为等长页面 - 地址由段号、段内页号与页内偏移组成 - 先用段表找到该段页表，再查页表定位物理页框 - 结合逻辑分段与离散物理分配，但转换和管理更复杂

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 虚拟内存与页面置换 ## 请求调页 - 程序只需部分页面驻留内存即可执行，其他页面按需装入 - 虚拟地址空间可以大于物理内存，但受地址位数、系统实现及后备存储等约束 - 访问合法但未驻留的页面，可能触发缺页异常 - 处理过程：检查合法性 → 获取页框 → 必要时换出旧页 → 装入所需页 → 更新映射 → 重启访存指令 - 被换出的脏页通常需要写回；可重新获取的干净页可直接丢弃 - 首次访问的匿名页面也可能通过分配清零页处理，不一定每次都读磁盘 ## 页面置换算法 - OPT：淘汰未来最长时间不再访问的页 - 需要未来访问序列，通常作为理论最优基准 - FIFO：淘汰最早进入内存的页 - 某些访问序列下，增加页框反而增加缺页，称为 Belady 异常 - LRU：淘汰过去最久未使用的页 - 利用时间局部性；精确实现需维护访问历史 - Clock：环形扫描页面，依据访问位等信息近似选择淘汰页 - 理想 LRU 与 OPT 具有栈性质，不出现 FIFO 式的 Belady 异常 ## 驻留集与抖动 - 驻留集：某进程当前实际占用的物理页面集合 - 工作集：一段时间窗口内进程活跃使用的页面集合 - 页框不足以支持活跃工作集时，频繁缺页和换页可能导致抖动 - 可通过增加可用页框、调整分配或降低并发程度缓解 ## 性能影响 - 缺页开销通常远大于一次内存访问，少量缺页也可能显著拖慢执行 - 若缺页率为 p，无缺页访问总耗时为 Tₕ，缺页时含服务和重试的总耗时为 T𝒻 - 简化期望耗时：E[T] = (1 - p)Tₕ + pT𝒻 - 是否包含页表遍历、磁盘排队、脏页写回等，必须与 T𝒻 的定义保持一致

磁盘访问与调度

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 磁盘访问与调度 ## 机械磁盘访问时间 - 寻道时间：磁头移动到目标磁道 - 旋转延迟：等待目标扇区旋转到磁头下 - 数据传输时间：把数据读出或写入 - 简化访问时间 = 寻道时间 + 旋转延迟 + 传输时间 - 若计入系统整体响应，还需加上排队、控制器与软件开销 ## 旋转与传输的估算 - 转速 R 的单位为转/分钟，则一周时间为 60 / R 秒 - 请求到达相位均匀时，平均旋转延迟约为 30 / R 秒 - 数据量为 b 字节、有效传输率为 v 字节/秒，传输时间约为 b / v - 连续跨磁道读写、控制器缓存及实际布局会影响实测耗时 ## 磁头调度 - FCFS：按到达顺序处理，简单公平，但总寻道距离可能较长 - SSTF：优先处理离当前磁头最近的请求，远端请求可能饥饿 - SCAN：沿一个方向服务，到边界后反向扫描 - C-SCAN：只沿一个方向服务，到边界后回到另一端再开始 - LOOK：只到当前方向最远的待处理请求就反向 - C-LOOK：到该方向最远请求后，跳到另一端的待处理请求继续 - 总移动距离：各次相邻磁道位置差的绝对值之和 - 计算结果依赖初始磁头位置、初始方向、磁道范围和折返约定 ## 固态存储的差异 - SSD 没有机械寻道与旋转延迟，不能直接套用机械磁盘的移臂模型 - 性能更多受到闪存并行性、控制器、垃圾回收、写放大和工作负载影响

设备管理

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 设备管理与 I/O 软件分层 ## 从应用到硬件 - 用户层 I/O：应用通过库函数与系统调用提出请求 - 设备无关软件：提供统一命名、权限、缓冲、分配与通用错误处理 - 设备驱动程序：把通用请求转换为具体设备控制命令 - 中断处理程序：响应设备完成或异常事件，保存与恢复必要执行状态 - 硬件：设备控制器与实际设备完成数据传输 - 分层模型用于划分职责；具体系统中部分职责可能合并或交叉 ## 缓冲与缓存 - 缓冲：协调设备与处理器的速度差异，适应传输单位不一致 - 双缓冲或多缓冲：在条件允许时使处理与下一批传输重叠 - 缓存：保留近期或频繁访问的数据，减少重复 I/O - 缓冲关注传输协调，缓存关注数据复用，二者可以共用同一内存区域 ## 设备分配 - 独占设备：某段时间内由一个任务独占使用 - 共享设备：多个任务通过调度访问 - SPOOLing：先把任务写入磁盘队列，再由服务进程顺序提交给设备 - 典型应用是打印服务，使多个应用共享原本需串行工作的打印设备 ## 请求与完成 - 同步或异步：描述调用者如何获知完成、是否继续推进 - 阻塞或非阻塞：描述暂时无法完成时调用是否等待 - 设备异常、超时和取消需要驱动与上层协同处理

文件管理

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 文件、目录与路径 ## 文件抽象 - 文件是由名字引用、具有相关内容和属性的持久数据对象 - 常见属性：类型、大小、所有者、权限、时间戳和数据位置 - 常见操作：创建、打开、读写、定位、关闭、重命名与删除 - 文件名与文件对象并非始终一一对应，同一对象可以有多个硬链接 ## 目录与元数据 - 目录把名字映射到文件或子目录对象 - 文件控制块 FCB 或 inode 保存文件元数据及数据位置等信息 - 打开文件表保存打开实例相关的状态，例如当前偏移与访问方式 - 树形目录把命名空间按层次组织；链接可形成更复杂的关系 ## 路径 - 绝对路径：从文件系统或卷的根定位目标 - Unix 类系统如 `/home/user/a.txt` - Windows 如 `C:\Users\user\a.txt`，也有 UNC 等形式 - 相对路径：从当前工作目录或指定基准目录定位目标 - `.` 表示当前目录，`..` 表示父目录；根目录等边界遵循系统规则 - 完整路径包含定位目标所需的目录部分和末尾文件名 - 绝对路径的定义不依赖是否出现盘符 ## 访问与保护 - 顺序访问：按当前位置连续读写 - 随机访问：定位到指定偏移再读写 - 权限、访问控制列表与共享方式限制操作范围 - 文件共享不保证并发写入自动正确，需要适当的锁或原子操作

--- markmap: height: 760 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 文件分配、索引与空闲空间 ## 数据块分配方式 - 连续分配：文件占用连续数据块，定位与顺序读取简单 - 文件增长困难，可能产生外部碎片；区段 extent 可记录一段连续块 - 链接分配：各块通过指针连接，易于增长 - 顺序访问方便，随机定位通常需沿链查找 - FAT 把链接信息集中保存在分配表中 - 索引分配：索引结构记录文件的数据块位置，支持不连续分配与随机访问 ## 直接与间接索引 - 直接指针：文件元数据直接指向数据块 - 一级间接：先到索引块，再到数据块 - 二级间接：经过两层索引块 - 三级间接：经过三层索引块 - 设块大小为 B 字节，块地址占 a 字节，每个索引块可存 q = ⌊B / a⌋ 个地址 - 若元数据包含 D 个直接指针，以及一、二、三级间接指针各一个 - 理论可寻址数据块数：D + q + q² + q³ - 理论数据容量：B × (D + q + q² + q³) - 不计索引块本身；实际最大文件还受偏移位宽、实现及卷容量等限制 - 文件字节偏移 x：逻辑块号为 ⌊x / B⌋，块内偏移为 x mod B - 索引层数影响未缓存时的寻址 I/O；索引缓存命中可减少磁盘访问 ## 位示图 - 每个数据块对应一位，表示空闲或占用 - 必须先明确位值约定，如 0 为空闲、1 为占用 - 若共有 N 个块，位图至少需要 ⌈N / 8⌉ 字节 - 块号从 0 开始，每字 w 位 - 块 b 对应字号 ⌊b / w⌋，字内位号 b mod w - 字号 i、位号 j 对应块号 i × w + j - 位图中的位序、块编号起点和保留块范围由具体格式规定 ## 其他空闲空间管理 - 空闲链表：把可用块串联起来 - 空闲区间表：记录连续空闲区的起点与长度 - 分配与回收必须同步更新元数据，避免同一块被重复分配